Ridge Regression and Deterministic Ridge Leverage Score Sampling
summary
Greedy selection ranks columns by deterministic ridge leverage scores and picks the top set so that the sampled column matrix C satisfies an additive–multiplicative spectral bound C C^T ≼ AA^T ≼ C C^T + ελ I, enabling multiplicative control of ridge regression risk (bias and variance). For matrices whose leverage scores follow a power law with exponent >2, the deterministic algorithm selects O(k) columns; in genomic experiments it reduces ~70,000 features to ~1,500 and preserves predictive performance.
AI-written summary · about
chapters (10)
- 0:00Start
- 1:46Motivation
- 4:32Outline
- 4:52Classical Leverage Scores
- 9:19Omit: Rank-k subspace leverage scores
- 10:54Dilute: Ridge leverage scores
- 15:22Deterministic sampling algorithm
- 16:40Returning to our challenge
- 18:56Spectral bound
- 26:32Ridge Regression Risk
related talks
48mRandomized Numerical Linear Algebra
33mRandomized Least Squares Optimization and its Incredible Utility for Large-Scale Tensor Decomp...
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
44mActive Regression via Linear-Sample Sparsification
37mLow-rank Matrix Completion: Adaptive Sampling Can Help When, How?
01h 02mSampling for Linear Algebra, Statistics, and Optimization II
01h 04mSketching for Linear Algebra III: Randomized Hadamard, Kernel Methods
01h 27mPast, Present and Future of Randomized Numerical Linear Algebra I