Solving Linear Programs in the Current Matrix Multiplication Time

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.Source: §1 · p. 2
• Beating √n iterations for general linear programs remains one of the biggest open problems in optimization.Source: §1 · p. 2

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.Source: §1 · p. 2

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).Source: §1 · p. 2
• 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.Source: §1 · p. 2

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.Source: §1 · p. 2

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.Source: §2 · p. 3

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.Source: §2.1 · p. 4, §2.1.1 · pp. 4–5

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 ω.Source: §2.1.2 · pp. 5–6

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.Source: §2.1.2 · pp. 5–6

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.Source: §2.2 · p. 6

• The analysis assumes n ≥ 10 and no redundant constraints, implying that A is full rank and n ≥ d.Source: §3 · p. 7
• The notation eO(f) denotes f multiplied by a polylogarithmic factor, while f ≲ g means f ≤ Cg for an absolute constant C.Source: §3 · p. 7
• The relation a ≈_ε b means every coordinate of a lies within a multiplicative ε of the corresponding coordinate of b.Source: §3 · p. 7
• For vectors x and s, xs denotes coordinatewise multiplication, and X and S denote their diagonal matrices.Source: §3 · p. 8
• The matrix X^−1S is identified as an orthogonal projection matrix in the notation setup.Source: §3 · p. 8

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.Source: Algorithm 1 · p. 10

Main algorithm

• The main algorithm falls back to ClassicalStep when the potential exceeds n^3, while otherwise maintaining its stochastic update framework.Source: Algorithm 1 · pp. 10–11
• The algorithm returns an approximate solution of the original linear program after its stopping condition is reached.Source: Algorithm 1 · p. 11

Stochastic-step guarantees

• The analysis bounds expected normalized update norms by 2ε for x and s and by 4ε for the combined complementarity update.Source: §4.2 · p. 13
• With resampling, the stochastic-step success conditions always hold; without resampling, they hold with probability 1 − 2n exp(−0.003kε√n log n).Source: §4.2 · p. 14

Update bounds

• The new complementarity vector satisfies ∥µ^−1(µ_new − µ)∥∞ ≤ 0.021 log n under the stated assumptions.Source: §2 · p. 15

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.Source: §4.3 · p. 19
• During the main algorithm, Assumption 4.1 remains satisfied, and ClassicalStep occurs with probability O(1/n^2) per step.Source: §4.3 · p. 21

Runtime

• Projection maintenance contributes an amortized per-iteration cost governed by the batch-size parameter a and the dual matrix-multiplication exponent α.Source: §4.4 · p. 23

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.Source: §4.5 · p. 24
• Because t decreases by a factor 1 − ε/(3√n) per iteration, the iteration count is logarithmic in n/δ.Source: §4.5 · p. 24
• 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^ω.Source: §4.5 · p. 24

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.Source: §5 · p. 25

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.Source: §5.1 · pp. 26–27

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.Source: §5.1 · pp. 25, 27
• 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.Source: §5.1 · p. 27

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.Source: §5.3 · p. 29
• 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.Source: §5.1 · p. 27, §5.3 · p. 29

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.Source: A Appendix · p. 39

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 ω.Source: A Appendix · p. 40

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).Source: A Appendix · pp. 40, 42
• 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δ.Source: A Appendix · pp. 41–42

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.Source: B Generalized Projection Maintenance · p. 43

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.Source: B Generalized Projection Maintenance · p. 43

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).Source: B Generalized Projection Maintenance · p. 43

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.Source: B Generalized Projection Maintenance · pp. 43–44