# Leverage Score Sampling for Faster Accelerated Regression and ERM

arXiv: https://arxiv.org/abs/1711.08426 · HTML: https://mlsanity.com/paper/1711.08426/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Nov 2017.

## Built on by (most cited first, 7 of 7)

- [Provably Accurate Shapley Value Estimation via Leverage Score Sampling](https://mlsanity.com/paper/2410.01917/) (2024)
- [Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods](https://mlsanity.com/paper/2202.04640/) (2022)
- [Fast John Ellipsoid Computation with Differential Privacy Optimization](https://mlsanity.com/paper/2408.06395/) (2024)
- [Structured Semidefinite Programming for Recovering Structured Preconditioners](https://mlsanity.com/paper/2310.18265/) (2023)
- [How to Inverting the Leverage Score Distribution?](https://mlsanity.com/paper/2404.13785/) (2024)
- [Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure](https://mlsanity.com/paper/2507.11724/) (2025)
- [Accelerated Gradient Algorithms with Adaptive Subspace Search for Instance-Faster Optimization](https://mlsanity.com/paper/2312.03218/) (2023)

## Abstract (arXiv)

Given a matrix A∈ℝn× d and a vector b ∈ℝd, we show how to compute an ε-approximate solution to the regression problem  min_x∈ℝdfrac12 |A x - b|22  in time  tildeO ((n+√d·kappasum)· s·logε-1)  where kappasum=trleft(AtopAright)/λmin(ATA) and s is the maximum number of non-zero entries in a row of A. Our algorithm improves upon the previous best running time of  tildeO ((n+√n ·kappasum)· s·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.