Solving Linear Programs in the Current Matrix Multiplication Time

Abstract

This paper shows how to solve linear programs of the form ${\min }_{Ax=b,x\ge 0}{c}^{\top }x$ with $n$ variables in time $$O^{\ast }((n^{\omega }+n^{2.5-\alpha /2}+n^{2+1/6})\log (n/\delta ))$$ where $\omega$ is the exponent of matrix multiplication, $\alpha$ is the dual exponent of matrix multiplication, and $\delta$ is the relative accuracy. For the current value of $\omega \sim 2.37$ and $\alpha \sim 0.31$, our algorithm takes $O^{\ast }(n^{\omega }\log (n/\delta ))$ time. When $\omega =2$, our algorithm takes $O^{\ast }(n^{2+1/6}\log (n/\delta ))$ time. Our algorithm utilizes several new concepts that we believe may be of independent interest: $\bullet$ We define a stochastic central path method. $\bullet$ We show how to maintain a projection matrix $\sqrt{W}{A}^{\top }(AW{A}^{\top }{)}^{-1}A\sqrt{W}$ in sub-quadratic time under ${\ell }_2$ multiplicative changes in the diagonal matrix $W$.

arXiv commentSTOC 2019, JACM 2020

References in corpus (3)

• Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
• Powers of Tensors and Fast Matrix Multiplication
• Solving Empirical Risk Minimization in the Current Matrix Multiplication Time

Cited by in corpus (9)

• Finding Angles for Quantum Signal Processing with Machine Precision
• Solving Linear Programs with Sqrt(rank) Linear System Solves
• A Deterministic Linear Program Solver in Current Matrix Multiplication Time
• Higher-Order Accelerated Methods for Faster Non-Smooth Optimization
• Feature Relevance Determination for Ordinal Regression in the Context of Feature Redundancies and Privileged Information
• Minimizing Convex Functions with Rational Minimizers
• Limits on the Universal Method for Matrix Multiplication
• Doubly-Efficient Pseudo-Deterministic Proofs
• Decentralized Detection with Robust Information Privacy Protection