Source-linked AI summary
Solving Linear Programs in the Current Matrix Multiplication Time
Michael B. Cohen, Yin Tat Lee, Zhao Song
TL;DR
The paper addresses the challenge of solving general linear programs faster than the longstanding iteration barrier. It introduces a stochastic central path method and associated data-structure techniques, achieving a runtime of O^*(n^ω log(n/δ)) for current matrix-multiplication exponents, while identifying limitations in improving the matrix-multiplication constant and an open runtime question.
Problem
General linear programming has remained bounded by an O^*(n^2.5) runtime in the generic d = Ω(n) case, while beating √n iterations remains open.
Method
The paper uses a stochastic short-step central path method that updates few coordinates and supports efficient maintenance of projection-related data structures.
Results
O^*(n^ω + n^2.5−α/2 + n^2+1/6) is achieved, simplifying to O^*(n^ω) for current ω ∼ 2.38 and α ∼ 0.31.
Takeaways & Limitations
The method reaches the best known linear-system runtime barrier for current exponents and reduces total coordinate updates to O^*(n).
Abstract
from arXiv · showhide
This paper shows how to solve linear programs of the form $\min_{Ax=b,x\geq0} c^\top x$ with $n$ variables in time $$O^*((n^ω+n^{2.5-α/2}+n^{2+1/6}) \log(n/δ))$$ where $ω$ is the exponent of matrix multiplication, $α$ is the dual exponent of matrix multiplication, and $δ$ is the relative accuracy. For the current value of $ω\sim2.37$ and $α\sim0.31$, our algorithm takes $O^*(n^ω \log(n/δ))$ time. When $ω= 2$, our algorithm takes $O^*(n^{2+1/6} \log(n/δ))$ 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}(AWA^{\top})^{-1}A\sqrt{W}$ in sub-quadratic time under $\ell_{2}$ multiplicative changes in the diagonal matrix $W$.
1 Introduction
The paper targets the long-standing O^*(n^2.5) barrier for general linear programming by reducing coordinate updates through a stochastic central path method. It achieves runtime governed by matrix multiplication, under a no-redundant-constraints assumption, and develops techniques intended to support further interior-point research.
- Motivation: O^*(n^2.5) remains the current fastest runtime for generic linear programs with d = Ω(n), a bound unchanged since Vaidya's 1989 result.The bound arises from O(n^2) work per iteration and √n iterations.
- Motivation: Beating √n iterations for general linear programs remains one of the biggest open problems in optimization.
- Contribution: O^*(n^ω + n^2.5−α/2 + n^2+1/6) is the paper's runtime, simplifying to O^*(n^ω) for current ω ∼ 2.38 and α ∼ 0.31.The result reaches the natural linear-system runtime barrier because linear systems are a special case of linear programs.
- Method: The stochastic method retains O^*(√n) steps but updates only eO(√n) coordinates per step, reducing total coordinate updates from O^*(n^1.5) to O^*(n).
- Method: The framework can take O^*(n) steps with eO(1) coordinate updates per step while maintaining O^*(n^ω) runtime for current ω ∼ 2.38.Its central-path analysis does not maintain x_i s_i close to an ideal vector in ℓ2 norm.
- Assumptions and notation: The paper assumes no redundant constraints, hence n ≥ d, and uses O^* and eO notation to hide specified accuracy- and dimension-dependent logarithmic factors.O^* hides n^o(1) and log^O(1)(1/δ) factors, while eO hides log^O(1)(n/δ) factors.
2 Results and Techniques
The paper achieves near-matrix-multiplication-time algorithms for approximate linear programming by combining a stochastic central path method with subquadratic projection maintenance. Its runtime is O^*(n^ω + n^{2.5−α/2} + n^{2+1/6}) log(n/δ), simplifying to O^*(n^ω) for current exponents under the stated assumptions.
- Main result: The main algorithm outputs a nonnegative x whose objective and constraint violations are bounded by δ·∥c∥∞R and δ·R-related error terms.The guarantee applies for 0 < δ ≤ 1 to a linear program with no redundant constraints and an ℓ1-polytope bound R.
- Central path method: The method follows a central path while decreasing the duality gap, using transformations that preserve the optimum and make the starting point easy to initialize.The central path is parameterized by t, and decreasing t reduces the duality gap, roughly proportional to nt.
- Projection maintenance: The approach departs from standard central-path algorithms by maintaining only multiplicative approximations to x and s and by not requiring x_is_i to stay close to an ideal vector in ℓ2 norm.The framework is designed to reduce iteration cost below quadratic time while retaining the same overall runtime for current ω.
- Central path method: The stochastic variant takes sparse randomized updates whose expectation matches the dense direction, reducing projection-vector multiplication costs to about n^2 overall when k is approximately √n.The sparse direction is chosen to minimize variance while preserving the expected update direction.
- Projection maintenance: Projection maintenance stores a matrix based on W = diag(x/s) and updates it lazily under multiplicative coordinate changes, achieving average per-iteration cost n^{ω−1}/2.Uniform changes can be batched over roughly √n steps, while the resulting maintenance cost is compatible with the target runtime.
3 Notations
The paper assumes n ≥ 10 and no redundant constraints, defines soft-O notation and coordinatewise approximation, and introduces diagonal-matrix notation for vectors.
- The analysis assumes n ≥ 10 and no redundant constraints, implying that A is full rank and n ≥ d.
- The notation eO(f) denotes f multiplied by a polylogarithmic factor, while f ≲ g means f ≤ Cg for an absolute constant C.
- The relation a ≈_ε b means every coordinate of a lies within a multiplicative ε of the corresponding coordinate of b.
- For vectors x and s, xs denotes coordinatewise multiplication, and X and S denote their diagonal matrices.
- The matrix X^−1S is identified as an orthogonal projection matrix in the notation setup.
4 Stochastic Central Path Method
The stochastic central path method replaces dense short-step updates with sparse randomized updates while controlling approximation, variance, and failure probability to obtain an approximate linear-program solution.
- Potential control: A soft-max potential tracks deviations of x_i s_i from t, and the step combines decreasing t with decreasing the potential.
- Main algorithm: The main algorithm falls back to ClassicalStep when the potential exceeds n^3, while otherwise maintaining its stochastic update framework.
- Main algorithm: The algorithm returns an approximate solution of the original linear program after its stopping condition is reached.
- Stochastic-step guarantees: The analysis bounds expected normalized update norms by 2ε for x and s and by 4ε for the combined complementarity update.
- Stochastic-step guarantees: With resampling, the stochastic-step success conditions always hold; without resampling, they hold with probability 1 − 2n exp(−0.003kε√n log n).
2. Var[µ−1
The analysis controls stochastic complementarity updates through expectation, variance, and potential bounds, then combines projection maintenance and iteration counts to derive the paper’s runtime and accuracy guarantees.
- Update bounds: The new complementarity vector satisfies ∥µ^−1(µ_new − µ)∥∞ ≤ 0.021 log n under the stated assumptions.
- Potential analysis: The potential is designed so that its expected change is controlled by a first-order progress term and a variance term scaling as 1/k.
- Potential analysis: During the main algorithm, Assumption 4.1 remains satisfied, and ClassicalStep occurs with probability O(1/n^2) per step.
- Runtime: Projection maintenance contributes an amortized per-iteration cost governed by the batch-size parameter a and the dual matrix-multiplication exponent α.
- Accuracy and runtime: The stopping condition yields x_i s_i ≈_0.1 t with t ≤ δ^2/(32n^3), implying a duality gap bounded by (δ/4n)^2.
- Accuracy and runtime: Because t decreases by a factor 1 − ε/(3√n) per iteration, the iteration count is logarithmic in n/δ.
- Accuracy and runtime: Choosing a = min(2/3, α) gives the promised runtime, while an ultra-short-step variant samples only polylogarithmically many coordinates with runtime still around n^ω.
5 Projection Maintenance
The section presents a projection-maintenance data structure for changing positive diagonal weights, with amortized analysis based on selectively updating coordinates and a potential function.
- Data structure: Theorem 5.1 gives a deterministic structure that approximately maintains projection matrices for positive diagonal matrices W.It supports Update and Query operations under specified tolerance and randomized update-sequence conditions.
- Update strategy: The algorithm updates only coordinates with sufficiently large relative error, enlarging the batch when nearby errors satisfy a soft-threshold condition.The implementation sorts coordinate errors and may expand the update set by factors of 1.5.
- Amortized analysis: A weighted potential assigns greater weight to larger errors, while each query increases it by a fixed amount and projection updates decrease it proportionally to their cost.This potential argument yields the amortized runtime bound.
- Amortized analysis: For the stochastic central-path setting, a smooth potential compensates for the small variance of the error vector.This allows the analysis to obtain essentially the same bound as in the zero-variance case.
- Runtime: The structure initializes in O(n^2d^(ω−2)) time and answers each Query(h) in O(n · ||h||_0 + n^(1+a)+o(1)) time.The initialization bound comes from computing A^T(AVA^T)^−1A.
- Runtime: An update affecting r coordinates costs O(rg_r n^(2+o(1))) time, where g_r is chosen from rectangular matrix-multiplication parameters.The bound follows by applying Woodbury updates and bounding the resulting rectangular matrix products.
A Appendix
The appendix supplies supporting matrix-multiplication bounds, a central-path lemma, and a reduction relating approximate solutions of a modified program to the original linear program.
- Central-path support: A central-path lemma finds new primal, dual, and constraint vectors in eO(n^2.5 log(n/ϵ)) time from approximately complementary feasible vectors.The input satisfies xs ≈ 0.1t, Ax=b, and A^Ty+s=c.
- Matrix multiplication: Rectangular products involving n × r and r × n matrices are bounded using separate cases for r ≤ n^α and r ≥ n^α.The resulting bound is expressed in terms of n, α, and ω.
- Linear-program reduction: Under bounded polytope diameter and objective coefficients, the appendix transforms the original linear program into a modified program whose approximate solution controls objective and feasibility error.The resulting feasibility deviation is bounded by 4nδ(R||A||_1 + ||b||_1).
- Linear-program reduction: A feasible modified-program point with duality gap δ^2 yields an objective bound involving δLR · OPT and δ^2.The appendix further bounds an auxiliary scalar by 4nδ.
B Generalized Projection Maintenance
The generalized structure extends projection maintenance to inverse matrices and dynamic column sets, with operation costs parameterized by abstract matrix-operation bounds.
- Generalized structure: Theorem B.1 maintains projection matrices and (AWA^T)^−1 for positive diagonal W while supporting updates, queries, insertions, and deletions.The number of columns remains O(n) throughout the algorithm.
- Assumptions: The generalized update guarantee assumes conditional expectation and variance bounds on each stochastic weight update.These conditions are stated relative to the weight before the call.
- Operation bounds: Initialization costs O(s_n + t_n), Query costs O(n · ||h||_0 + sk* + nk*), and Output costs O(t_k*).Insert and Delete each cost O(n^2).
- Analysis: The proof reuses the potential-function framework while redefining g according to the abstract costs t_k and s_n.Insertions and deletions use Sherman–Morrison updates and do not increase the potential.