RECORD
Leverage Score Sampling for Faster Accelerated Regression and ERM
Machine Learning · Submitted 22 Nov 2017
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim 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 $\epsilon$-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\kappa_{\text{sum}}})\cdot s\cdot\log\epsilon^{-1}) $ where $\kappa_{\text{sum}}=\mathrm{tr}\left(\mathbf{A}^{\top}\mathbf{A}\right)/\lambda_{\min}(\mathbf{A}^{T}\mathbf{A})$ and $s$ is the maximum number of non-zero entries in a row of $\mathbf{A}$.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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 $\epsilon$-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\kappa_{\text{sum}}})\cdot s\cdot\log\epsilon^{-1}) $ where $\kappa_{\text{sum}}=\mathrm{tr}\left(\mathbf{A}^{\top}\mathbf{A}\right)/\lambda_{\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\kappa_{\text{sum}}})\cdot s\cdot\log\epsilon^{-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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | 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 $\epsilon$-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\kappa_{\text{sum}}})\cdot s\cdot\log\epsilon^{-1}) $ where $\kappa_{\text{sum}}=\mathrm{tr}\left(\mathbf{A}^{\top}\mathbf{A}\right)/\lambda_{\min}(\mathbf{A}^{T}\mathbf{A})$ and $s$ is the maximum number of non-zero entries in a row of $\mathbf{A}$. | result 0.66 | 0.95 | 0.79 | asserted 1.00 |
| s1 | Our algorithm improves upon the previous best running time of $ \tilde{O} ((n+\sqrt{n \cdot\kappa_{\text{sum}}})\cdot s\cdot\log\epsilon^{-1})$. | result 0.73 | 0.76 | 0.33 | asserted 1.00 |
| s2 | We achieve our result through a careful combination of leverage score sampling techniques, proximal point methods, and accelerated coordinate descent. | method 1.00 | 0.92 | 0.07 | asserted 1.00 |
| s3 | Our method not only matches the performance of previous methods, but further improves whenever leverage scores of rows are small (up to polylogarithmic factors). | result 0.50 | 0.88 | 0.17 | asserted 0.99 |
| s4 | We also provide a non-linear generalization of these results that improves the running time for solving a broader class of ERM problems. | contribution 0.95 | 0.94 | 0.12 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
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 $\epsilon$-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\kappa_{\text{sum}}})\cdot s\cdot\log\epsilon^{-1}) $ where $\kappa_{\text{sum}}=\mathrm{tr}\left(\mathbf{A}^{\top}\mathbf{A}\right)/\lambda_{\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\kappa_{\text{sum}}})\cdot s\cdot\log\epsilon^{-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.
Human review
How the literature uses it
5 arXiv papers cite this in 5 sentences
Papers citing it · 1 sentence without a confident label
Uses its method or tool 1 paper
-
And when $d≤n$, using a leverage score sampling technique [ref] , the algorithm has data access complexity is $𝒪̃( n + d^5/6ϵ^-1/3 )$.
Accelerated Gradient Algorithms with Adaptive Subspace Search for Instance-Faster Optimization · What We Do · 1.00
Cites it as background 3 papers
-
Leverage score sampling is a non-oblivious sketching technique that is widely used in numerical linear algebra and has been successfully applied to speed up different problems such as linear regression [ref] , row sampling [ref] , spectral approximation [ref] , low rank approximation [ref] , cutting plane methods [ref] , linear programming [ref] , computing John Ellipsoid [ref] .
Sketching Transformed Matrices with Applications to Natural Language Processing · Application to Low Rank Approximation · 0.84
-
We will refer to functions of this form as structured convex quartics, as we are given an explicit decomposition of the fourth-order term, i.e., [equation] While fast minimization of convex quadratic functions $f(x) = c^⊤x + x^⊤x$ has been an area of significant research efforts [ref] , the structured convex quartic case has been less explored.
Fast minimization of structured convex quartics · Introduction · 0.97
-
There are a huge number of papers that have considered this topic [ref] as almost all convex optimization machine learning can be phrased in the ERM framework [ref] .
Solving Empirical Risk Minimization in the Current Matrix Multiplication Time · Introduction · 0.98
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.