# Solving Empirical Risk Minimization in the Current Matrix Multiplication Time

Preprint · Yin Tat Lee, Zhao Song, Qiuyi Zhang

- Archive id: arxiv:1905.04447
- Published: 2019-05-11
- arXiv: https://arxiv.org/abs/1905.04447
- Source URL: https://arxiv.org/abs/1905.04447
- PDF: https://arxiv.org/pdf/1905.04447
- Provenance: arxiv

## 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 $ω$ 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 $ω\\sim 2.38$ \[Vassilevska Williams'12, Le Gall'14\] and $α\\sim 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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.