Leverage Score Sampling for Faster Accelerated Regression and ERM
This work provides a faster algorithm for regression and ERM problems, which is incremental but offers practical speed-ups in computational optimization.
The paper tackles the problem of computing an ε-approximate solution to linear regression and extends it to empirical risk minimization (ERM), achieving a faster running time of ̃O((n+√(d·κ_sum))·s·log ε⁻¹) compared to the previous best of ̃O((n+√(n·κ_sum))·s·log ε⁻¹), with improvements when leverage scores are small.
Given a matrix $\mathbf{A}\in\mathbb{R}^{n\times d}$ and a vector $b \in\mathbb{R}^{d}$, we show how to compute an $ε$-approximate solution to the regression problem $ \min_{x\in\mathbb{R}^{d}}\frac{1}{2} \|\mathbf{A} x - b\|_{2}^{2} $ in time $ \tilde{O} ((n+\sqrt{d\cdotκ_{\text{sum}}})\cdot s\cdot\logε^{-1}) $ where $κ_{\text{sum}}=\mathrm{tr}\left(\mathbf{A}^{\top}\mathbf{A}\right)/λ_{\min}(\mathbf{A}^{T}\mathbf{A})$ and $s$ is the maximum number of non-zero entries in a row of $\mathbf{A}$. Our algorithm improves upon the previous best running time of $ \tilde{O} ((n+\sqrt{n \cdotκ_{\text{sum}}})\cdot s\cdot\logε^{-1})$. We achieve our result through a careful combination of leverage score sampling techniques, proximal point methods, and accelerated coordinate descent. Our method not only matches the performance of previous methods, but further improves whenever leverage scores of rows are small (up to polylogarithmic factors). We also provide a non-linear generalization of these results that improves the running time for solving a broader class of ERM problems.