Solving Empirical Risk Minimization in the Current Matrix Multiplication Time

Abstract

Many convex problems in machine learning and computer science share the same form: \begin{align*} \min_{x} \sum_{i} f_i( A_i x + b_i), \end{align*} where $f_i$ are convex functions on ${\mathbb{R}}^{n_i}$ with constant $n_i$, $A_i\in {\mathbb{R}}^{n_i\times d}$, $b_i\in {\mathbb{R}}^{n_i}$ and ${\sum }_i{n}_i=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 \begin{align*} O^* ( ( n^ω + n^{2.5 - α/2} + n^{2+ 1/6} ) \log (n / δ) ) \end{align*} where $\omega$ is the exponent of matrix multiplication, $\alpha$ is the dual exponent of matrix multiplication, and $\delta$ 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 $\delta$. For the current bound $\omega \sim 2.38$ [Vassilevska Williams'12, Le Gall'14] and $\alpha \sim 0.31$ [Le Gall, Urrutia'18], our runtime $O^{\ast }(n^{\omega }\log (n/\delta ))$ 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 $\omega$ 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.

References in corpus (14)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• A Universal Catalyst for First-Order Optimization
• Finding Linear Structure in Large Datasets with Scalable Canonical Correlation Analysis
• SDCA without Duality, Regularization, and Individual Convexity
• On the Local Minima of the Empirical Risk
• Doubly Accelerated Stochastic Variance Reduced Dual Averaging Method for Regularized Empirical Risk Minimization
• Fast Rates for Empirical Risk Minimization of Strict Saddle Problems
• A General Distributed Dual Coordinate Optimization Framework for Regularized Loss Minimization
• Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice
• Constant Step Size Least-Mean-Square: Bias-Variance Trade-offs and Optimal Sampling Distributions
• Leverage Score Sampling for Faster Accelerated Regression and ERM
• Limits on the Universal Method for Matrix Multiplication
• (Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless
• Data Sampling Strategies in Stochastic Algorithms for Empirical Risk Minimization

Cited by in corpus (13)

• Quantum algorithms for Second-Order Cone Programming and Support Vector Machines
• Solving Linear Programs in the Current Matrix Multiplication Time
• Minimum Cost Flows, MDPs, and ${\ell }_1$-Regression in Nearly Linear Time for Dense Instances
• Solving Tall Dense Linear Programs in Nearly Linear Time
• Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs
• Space-Efficient Interior Point Method, with applications to Linear Programming and Maximum Weight Bipartite Matching
• A Deterministic Linear Program Solver in Current Matrix Multiplication Time
• Indivisible Mixed Manna: On the Computability of MMS + PO Allocations
• Minimizing Convex Functions with Rational Minimizers
• A near-optimal algorithm for approximating the John Ellipsoid
• A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Path
• Barriers for rectangular matrix multiplication
• Solving SDP Faster: A Robust IPM Framework and Efficient Implementation