Subgradient and Sampling Algorithms for `l_1` Regression
Ken Clarkson
Bell Labs, Lucent Technologies
`l_1` Regression: Points and Lines
- Given a set `S` of `n` points
- find a line fitting the points
- minimize the sum of absolute values of vertical distances
Distances: sum= 0 rms= 0
`l_1` Regression: Matrices and Vectors
- Given `n\times d` matrix `A` and `n`-vector `b`,
find `d`-vector `x` minimizing
`{:|\|Ax-b\|\| _1:} = \sum_i {:|a_{i\cdot} x - b_i|:}`
- Corresponding points are `[a_{i\cdot} b_i]`
- vertical coordinate `b_i`
- Put still another way, find the linear combination of the columns of `A`
closest to `b` in `l_1` distance
- Least-squares, or `l_2` regression minimizes
`|\|Ax-b\|\| _2`
- Chebyshev, or max-min, or `l_\infty` regresssion minimizes
`|\|Ax-b\|\| _\infty`
Who cares?
- Statistically, more "robust" than least squares
- That is, less affected by "outliers"
- Close to `l_0` norm, which counts number of non-zero entries
- Least squares is used because it's easy to compute
- In 2d, a few sums and ratios;
- In higher dim:
- Gram-Schmidt orthogonalization
- other `QR` factoring methods
- solving normal equations...
- `l_\infty` regression is a linear programming problem in low dimension
- `l_1` regression is a linear programming problem
Algorithms: Before
- Generally, considering `n gg d`, but not regarding `d` as constant.
- `l_2` optimum computable in in `O(nd^2)` time [G01][L11]
- `l_\infty` computable in `O(nd^2) + O(log n)LP(d^2, d)` [C88]
- where `LP(m,d)` is the time needed to solve an LP with `m` constraints, dimension `d`
- that is, `O(n)` in fixed dimension
- `l_1` is computable in `LP(2d+d, d)` time
- or `O({:n3^{d^2}:})` time, or possibly `O({:n3^{O(d)}:})` time [MT]
- or `LP(2d+d, d, B)` time, where `B` is the bit complexity
Algorithms: Today
- `l_1` algorithm needing `n (log n) d^{O(1)}` to get within a constant factor
- Additional `n(d//epsilon)^{O(1)}` to get within `epsilon>0` of opt
- Or, Monte Carlo algorithm needing additional `(d//epsilon)^{O(1)}log(1//gamma) ` time for error probability `gamma`
- Monte Carlo algorithm: solve problem for small random subset
Ideas
- Make columns of `A` orthogonal, and `b` orthogonal to them
- That is, solve the `l_2` problem
- Apply ellipsoid method to "condition" `A` further
- Faster because of first step
- Fast enough in `n gg d` regime
- Apply subgradient algorithm to get within a constant factor
- Two approaches for more accuracy:
- Apply more subgradient algorithm steps,
- OR, take random subset of (conditioned) points; resulting problem has opt provably close in value
- random subset corresponds to diagonal matrix `Z` with about `r` entries, minimize `|\|Z(Ax - b)\|\| _1`
Elementary column Operations
- Adding a multiple of column `a_{cdot k}` to column `a_{cdot k'}` amounts to a change of variable
- That is, we can consider `ABx`, for `d times d` matrix `B`, either as
- Changed matrix `AB`, or
- Changed variable `Bx`
- Usually talk about changed matrix `AB`, renamed to `A`, but implicitly, tracking changes
- Similarly, subtracting multiples of columns of `A` from `b` doesn't change problem
- Such operations are enough to make columns of `A`, and `b`, orthogonal
Conditioning `A` Using the Ellipsoid Method
- Purpose is to make `|\|Ax\|\| _1 approx |\|x|\| _1`
- That is, operate on the columns of `A` so that
`|\|x|\| _1 >= |\|Ax\|\| _1 >= |\|x|\| _1/{:d sqrt d:}`
- Equivalently, make the `d`-polytope `\{ x : |\|Ax\|\| _1 \le 1 \}` round or fat
Conditioning, II
- The conditioning here is an analog for the `l_1` norm, of orthogonalization
- Gradient descent after conditioning is roughly like Newton's method
- After orthogonalizing, have
`|\|Ax\|\| _2 = |\|x|\| _2`
(not just upper and lower bounded), so conditioning is to `l_1` as orthogonalization is to `l_2`
- Orthogonalizing implies "`l_1` condition" is `O(sqrt n)`
Subgradients
- The function `F(x) equiv |\|Ax - b\|\| _1` is piecewise-linear,
so it has a gradient "almost everywhere"
- That gradient is `A^T sgn(Ax-b)`
- That is, a signed combination of the rows of `A`
- At breakpoints of `F(x)`, gradient is undefined, but for any `x` and `y`,
`F(x) - F(y) \le (x-y)^T A^T sgn(Ax-b)`
- That is, `A^T sgn(Ax-b)` is a subgradient, a member of the set `\del F(x)`
Subgradient Descent
- In particular, if `hat x equiv argmin F(x)`, then
`F(x) - F(hat x) \le (x - hat x)^T A^T sgn(Ax-b)`
- So `G(x) equiv -A^T sgn(Ax-b)` points from `x` to `hat x`
- This subgradient property has been used for optimization
- Take `x_0 := 0`, and `x_{i+1} := x_i + sigma G(x_i)
- Here `sigma` is a multiplier to avoid overstepping
Subgradient Descent: Stepsize
- Often `sigma` is taken as fixed, or slowly decreasing in some simple way
- Or, `F(x)` is minimized among points on the line `x_i + t G(x_i)`
- Works good, but hard to prove a time bound
- Here, it turns out that a careful program of `sigma` values allows provable convergence
Subgradient Descent: How good is the subgradient?
- Let `theta` be the angle between `x - hat x` and `G(x)`
- How big is `cos(theta)`?
- We have
`cos(theta) |\|x-hat x|\| _2 |\| G(x)|\| _ 2 > F(x) - F(hat x)`
- How small are `|\|x-hat x|\| _2` and `|\| G(x)|\| _ 2`?
Subgradient Descent: Using conditioning
- `|\| G(x)|\| _ 2 = |\| A^T sgn (Ax-b)|\| _ 2 le sqrt d`
- `|\|x|\| _ 1 > |\|Ax|\| _ 1` implies column sums of `A` are `le 1`.
- `|\|x-hat x|\| _2 \le d sqrt{d} (F(x) + F(hat x))`
- `|\|x-hat x|\| _2 \le |\|x-hat x|\| _1 \le d sqrt{d) |\|Ax-A hat x|\| _2 \le d sqrt{d)(F(x) + F(hat x))`
- So if `alpha equiv {:F(x):}//{:F(hat x):}`, then
`cos(theta) > (F(x) - F(hat x))/((sqrt(d))d sqrt{d)(F(x) + F(hat x))) > {:1/(d^2):}(alpha-1)/(alpha+1)`
Subgradient Descent: Using the subgradient
- `cos(theta) > (alpha-1)// {:d^2 (alpha+1):}`
- When `F(x) \gg F(hat x)`, `cos(theta) approx 1`, or `theta approx 0`, good
- When `F(x) approx F(hat x)`, not so good
- Leading to running time dependence `1//{:epsilon^2:}`
- Step length `|\|x-hat x|\| _2 cos(theta) \ge F(x)(1-{:1//alpha:})//sqrt(d)`
- Depends on `F(x)`, and on `alpha`, or an estimate of it
- Enough to use estimate smaller than `alpha`
- If estimate is below `alpha`, provable improvement in `F(x)`
- If above `alpha`, know that `alpha` can be reduced
Sampling Algorithm: Preprocessing
- Condition 'A' using the ellipsoid method
- For applying subgradient algorithm, and useful for sampling
- Use subgradient algorithm to find `x'` with `|\|Ax'-b|\| _1 \le 2 |\|A hat x - b|\| _1`
- Replace `b` by `b-Ax'` (change of variable)
- Result is no "outliers"
Sampling Algorithm: Sampling and Solving
- Construct a diagonal `n times n` matrix `Z` as follows:
- `f_i equiv |b_i| + |\|a_{i cdot}|\| _1`
- `W equiv sum_i f_i`
- `p_i equiv min \{ 1, r f_i//W \}
- Choose `y_i = 1` with probability `p_i`, 0 otherwise
- `Z_{ii} = y_i/p_i`
- Minimize `|\| Z(Ax-b)|\| _1`
Sampling Algorithm: Why it works
- `EZ = I`, and `E|\| Z(Ax-b)|\| _1 = |\| Ax-b|\| _1` for any given `x`
- Expected number of nonzero `Z_{ii}` is `r`
- `sum_i E[(Z_{ii}|b_i - a_{i cdot} x|)^2] approx {:|\| Ax -b |\|:} _1 ^2`
- That is, sum of squares within a constant factor of square of expectation
- Conditioning of `A` implies `f_i = |b_i| + |\|a_{i cdot}|\| _1`
is a good estimator of `|b_i - a_{i cdot} x|`, on average
- Result is that, with high prob., `|\| Z(Ax-b)|\| _1 approx |\| Ax-b|\| _1`
Bernstein Bounds
- Use tail estimates of Maurer03, MO3:
- Given `X_i ge 0`, `i=1...n`, independent random variables
- Let `S = sum_i X_i`, then for any `t ge 0`,
`log Prob\{S ge ES -t\} \le {:-t^2:}/{:2 sum_i EX_i^2:}`
- Tail estimate of Bernstein46:
- if also for some `M`, `X_i le EX_i + M`, then
`log Prob\{S le ES + t\} \le {:-t^2//2:}/{:tM//3 + sum_i EX_i^2:}`
Coresets (motivation)
- One motivation here: are there coresets for `l_1` regression?
- Coreset for smallest ball problem:
- Given set of points `S` and `epsilon>0`
- there is `C subset S` of size ` lceiling 1//epsilon rceiling`, such that
- the smallest ball containing `C`, expanded by `1+epsilon`, contains `S`
- Independent of `|S|`, and even the dimension (!)
Coresets: uses
- Useful for `k`-center problem and others
- Similar results for approximating many geometric problems (but coresets may be larger)
- Here: sample taken by sampling algorithm is a kind of coreset
- Size `d^{O(1)}/epsilon^2`