# Solving Empirical Risk Minimization in the Current Matrix Multiplication Time

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

## Key facts

- Cited by 53 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 May 2019.

## Built on by (most cited first, 30 of 53)

- [H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models](https://mlsanity.com/paper/2306.14048/) (2023)
- [Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time](https://mlsanity.com/paper/2310.17157/) (2023)
- [Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time](https://mlsanity.com/paper/2112.07628/) (2021)
- [Attention Scheme Inspired Softmax Regression](https://mlsanity.com/paper/2304.10411/) (2023)
- [Solving Regularized Exp, Cosh and Sinh Regression Problems](https://mlsanity.com/paper/2303.15725/) (2023)
- [Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension](https://mlsanity.com/paper/2304.04397/) (2023)
- [LazyDiT: Lazy Learning for the Acceleration of Diffusion Transformers](https://mlsanity.com/paper/2412.12444/) (2024)
- [An Iterative Algorithm for Rescaled Hyperbolic Functions Regression](https://mlsanity.com/paper/2305.00660/) (2023)
- [Fast Sketching of Polynomial Kernels of Polynomial Degree](https://mlsanity.com/paper/2108.09420/) (2021)
- [Does Preprocessing Help Training Over-parameterized Neural Networks?](https://mlsanity.com/paper/2110.04622/) (2021)
- [Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time](https://mlsanity.com/paper/2302.11068/) (2023)
- [InfoPrompt: Information-Theoretic Soft Prompt Tuning for Natural Language Understanding](https://mlsanity.com/paper/2306.04933/) (2023)
- [A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time](https://mlsanity.com/paper/2309.07418/) (2023)
- [A Mathematical Abstraction for Balancing the Trade-off Between Creativity and Reality in Large Language Models](https://mlsanity.com/paper/2306.02295/) (2023)
- [Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerability](https://mlsanity.com/paper/2210.08371/) (2022)
- [Differentially Private Attention Computation](https://mlsanity.com/paper/2305.04701/) (2023)
- [GradientCoin: A Peer-to-Peer Decentralized Large Language Models](https://mlsanity.com/paper/2308.10502/) (2023)
- [Training Overparametrized Neural Networks in Sublinear Time](https://mlsanity.com/paper/2208.04508/) (2022)
- [A Sublinear Adversarial Training Algorithm](https://mlsanity.com/paper/2208.05395/) (2022)
- [Solving Attention Kernel Regression Problem via Pre-conditioner](https://mlsanity.com/paper/2308.14304/) (2023)
- [Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures](https://mlsanity.com/paper/2111.15139/) (2021)
- [A Tighter Complexity Analysis of SparseGPT](https://mlsanity.com/paper/2408.12151/) (2024)
- [Federated Adversarial Learning: A Framework with Convergence Analysis](https://mlsanity.com/paper/2208.03635/) (2022)
- [Dynamic Tensor Product Regression](https://mlsanity.com/paper/2210.03961/) (2022)
- [Lifelong Learning with Sketched Structural Regularization](https://mlsanity.com/paper/2104.08604/) (2021)
- [Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing](https://mlsanity.com/paper/2105.08285/) (2021)
- [A General Algorithm for Solving Rank-one Matrix Sensing](https://mlsanity.com/paper/2303.12298/) (2023)
- [Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summations](https://mlsanity.com/paper/2212.11408/) (2022)
- [A Nearly-Optimal Bound for Fast Regression with ℓ_∞ Guarantee](https://mlsanity.com/paper/2302.00248/) (2023)
- [Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Acceleration](https://mlsanity.com/paper/2305.08367/) (2023)

## Abstract (arXiv)

Many convex problems in machine learning and computer science share the same form: beginalign* minx sumi fi( Ai x + bi), endalign* where fi are convex functions on ℝni with constant ni, Ai ∈ ℝni × d, bi ∈ ℝni and sumi ni = n. This problem generalizes linear programming and includes many problems in empirical risk minimization. In this paper, we give an algorithm that runs in time beginalign* O^* ( ( nω + n2.5 - α/2 + n2+ 1/6 ) log (n / δ) ) endalign* where ω is the exponent of matrix multiplication, α is the dual exponent of matrix multiplication, and δ is the relative accuracy. Note that the runtime has only a log dependence on the condition numbers or other data dependent parameters and these are captured in δ. For the current bound ω ~ 2.38 [Vassilevska Williams'12, Le Gall'14] and α ~ 0.31 [Le Gall, Urrutia'18], our runtime O^* ( nω log (n / δ)) matches the current best for solving a dense least squares regression problem, a special case of the problem we consider. Very recently, [Alman'18] proved that all the current known techniques can not give a better ω below 2.168 which is larger than our 2+1/6. Our result generalizes the very recent result of solving linear programs in the current matrix multiplication time [Cohen, Lee, Song'19] to a more broad class of problems. Our algorithm proposes two concepts which are different from [Cohen, Lee, Song'19] : bullet We give a robust deterministic central path method, whereas the previous one is a stochastic central path which updates weights by a random sparse vector. bullet We propose an efficient data-structure to maintain the central path of interior point methods even when the weights update vector is dense.