Show and Tell
Ken Clarkson
Activities
- Subgradient and sampling algorithms for `l_1` Regression
- Algorithms for geometric set cover
- Randomized appproximation algorithms for matrix problems
- Sparsity as a deletion estimate of risk
Algorithms for geometric set cover
- With Kasturi Varadarajan
- Given collection S of regions, region U
- Cover U with as few regions from S as possible
- One approach gives constant-factor approximation algorithms for covering by:
- Fat triangles and polygonal regions
- "Guarding" a 1-d terrain
- Unit cubes in 3d
- Approach uses small `epsilon`-nets, Davenport-Schinzel sequences
`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
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 min-max, or `l_\infty` regression 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
sum= 0 rms= 0
Algorithms
- 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(2n, n+d)` time
- or `O({:n3^{d^2}:})` time, or possibly `O({:n3^{O(d)}:})` time [MT]
- or `LP(2n, n+d, B)` time, where `B` is the bit complexity
Algorithms: Mine
- `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
Overview
- Make columns of `A` orthogonal, and `b` orthogonal to them
- That is, solve the `l_2` problem
- A "folk" algorithm
- Apply ellipsoid method to "condition" `A` further
- Linear transformation, finds Loewner-John ellipsoid pair
- Faster because of first step
- Fast enough in `n gg d` regime
Overview: `1+epsilon` Approximation
- 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
- Another "folk" algorithm?
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 of orthogonalization ,for the `l_1` norm
- After orthogonalizing, have `|\|Ax\|\| _2 = |\|x|\| _2`
- Motivation similar to that for Newton's method
- Orthogonality before conditioning 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(y) \ge F(x) + (y-x)^T A^T sgn(Ax-b)`
- That is, `A^T sgn(Ax-b)` is a subgradient, a member of the set `\del F(x)`
- Gradient for least squares is `A^T(Ax-b)`; setting this to zero gives "normal equations"
Subgradient Descent Method
- In particular, if `hat x equiv argmin _x F(x)`, then
`F(x) - F(hat x) \le (x - hat x)^T A^T sgn(Ax-b) = (hat x - 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
- This way, clearly not necessarily a descent method
Subgradient Method: 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
- Can't just check for improvement: closer in `l_2`, but maybe not in function value
- Best stepsize depends on unknown ratio `{:F(x):}//{:F(hat x):}`
Subgradients Animation
sum= 0 rms= 0
Sampling and Solving
- (After some preprocessing)
- 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`
- Apply tail estimates, `X_i = Z_{ii}{:|b_i - a_{i cdot} x|:}`
- `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 probability, `{:|\| Z(Ax-b)|\|:} _1 approx {:|\| Ax-b|\|:} _1`
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 (!)
Conclusion
- Provable results, plausible algorithms
- Can the ellipsoid method be avoided?
- Repeatedly apply subgradient algorithm to columns of `A`
- Remove linear comnbinations to make `l_1` residual small
- Apply to other regression schemes?
- Remove `log n` term?