Source-linked AI summary
A Deterministic Linear Program Solver in Current Matrix Multiplication Time
Jan van den Brand
TL;DR
Deterministic linear-program solvers lagged behind randomized methods for large d, despite randomized near-O(n^ω) time being essentially optimal. This paper derandomizes that approach by maintaining approximate projection products directly, obtaining a deterministic O(n^ω log^2(n) log(n/δ)) solver and a shorter central-path analysis. The result closes the stated complexity gap for large d, subject to the solver’s dependence on current matrix-exponent bounds.
Problem
Deterministic linear-program solvers for d = Ω(n) remained at an Ω(n^2.5) barrier while randomized methods achieved essentially optimal eO(n^ω) time.
Method
The paper derandomizes Cohen et al.’s solver by maintaining approximate projection products directly for dense approximate vectors and adapting the short-step central-path method.
Results
O(n^ω log^2(n) log(n/δ)) time computes an approximate solution for current ω ≈ 2.38.
Takeaways & Limitations
The deterministic algorithm closes the complexity gap with randomized algorithms for linear programs in the large-d regime and roughly halves the central-path analysis length.
Takeaways & Limitations
The eO(n^ω) bound is optimal only when d = Ω(n) and cannot beat eO(n^(2+1/6)) if future matrix-multiplication exponents improve below 2 + 1/6.
Abstract
from arXiv · showhide
Interior point algorithms for solving linear programs have been studied extensively for a long time [e.g. Karmarkar 1984; Lee, Sidford FOCS'14; Cohen, Lee, Song STOC'19]. For linear programs of the form $\min_{Ax=b, x \ge 0} c^\top x$ with $n$ variables and $d$ constraints, the generic case $d = Ω(n)$ has recently been settled by Cohen, Lee and Song [STOC'19]. Their algorithm can solve linear programs in $\tilde O(n^ω\log(n/δ))$ expected time, where $δ$ is the relative accuracy. This is essentially optimal as all known linear system solvers require up to $O(n^ω)$ time for solving $Ax = b$. However, for the case of deterministic solvers, the best upper bound is Vaidya's 30 years old $O(n^{2.5} \log(n/δ))$ bound [FOCS'89]. In this paper we show that one can also settle the deterministic setting by derandomizing Cohen et al.'s $\tilde{O}(n^ω\log(n/δ))$ time algorithm. This allows for a strict $\tilde{O}(n^ω\log(n/δ))$ time bound, instead of an expected one, and a simplified analysis, reducing the length of their proof of their central path method by roughly half. Derandomizing this algorithm was also an open question asked in Song's PhD Thesis. The main tool to achieve our result is a new data-structure that can maintain the solution to a linear system in subquadratic time. More accurately we are able to maintain $\sqrt{U}A^\top(AUA^\top)^{-1}A\sqrt{U}\:v$ in subquadratic time under $\ell_2$ multiplicative changes to the diagonal matrix $U$ and the vector $v$. This type of change is common for interior point algorithms. Previous algorithms [e.g. Vaidya STOC'89; Lee, Sidford FOCS'15; Cohen, Lee, Song STOC'19] required $Ω(n^2)$ time for this task. [...]
1 Introduction
The paper closes the gap between randomized and deterministic linear-program solvers for large d by derandomizing a near-matrix-multiplication-time method. Its key idea is to maintain approximate projection products directly, enabling a deterministic solver and a shorter central-path analysis.
- Interior-point algorithms are motivated by the broad applicability of linear-program formulations and have a long history of fast-solver research.
- For d = Ω(n), randomized solvers achieve eO(n^ω) time, essentially matching the O(n^ω) cost required by known linear-system solvers.The cited randomized bound includes polylogarithmic factors and accuracy dependence.
- Deterministic solvers for d = Ω(n) remained stuck at an Ω(n^2.5) barrier, motivating the question of whether randomized complexity could be matched deterministically.The prior deterministic bounds were at least 30 years old.
- The paper answers affirmatively by derandomizing Cohen et al.’s algorithm and closing the randomized–deterministic complexity gap for large d.
- Results: Theorem 1.1 gives an approximate feasible solution in O(n^ω log^2(n) log(n/δ)) time for current ω ≈ 2.38.Here R bounds the ℓ1 norm of feasible nonnegative solutions, and δ is the relative accuracy parameter.
- Technical Ideas: The main technical contribution maintains approximate projection products directly for dense approximate vectors, rather than maintaining only the projection matrix.This avoids the dense-vector multiplication bottleneck that required Ω(n^2) time in prior data structures.
- Technical Ideas: The modified data structure and short-step central-path method yield a deterministic eO(n^ω) solver while roughly halving the central-path proof length.The central-path analysis measures progress in the ℓ∞ norm to accommodate approximate projections.
2 Outline
The outline explains how a short-step central path method reduces linear programming to repeatedly maintaining an approximate projection, and how a deterministic data structure accelerates this task under small updates. The resulting approach extends prior projection maintenance to handle the projected vector as well as the matrix, enabling a deterministic solver.
- 2.1 Short Step Central Path Method: The short-step central path method maintains a feasible primal-dual triple while repeatedly decreasing t and keeping the complementarity vector μ close to t.The method updates x, y, and s so that μ_i = x_i s_i remains near the decreasing target t.
- 2.2 Projection Maintenance: Each iteration requires solving a linear system involving the projection Pv, where P depends on changing diagonal matrices while A remains fixed.Writing U := X/S makes P depend on U, so only the diagonal matrix changes between iterations.
- 2.2 Projection Maintenance: The main result is a deterministic approximation of Pv in eO(n^ω−0.5 + n^2.5−α) amortized time, obtained by extending Cohen, Lee, and Song’s data structure to maintain ePev.The extension preserves the prior structure while adding dense-vector products, which simplifies the central-path analysis and removes randomization.
- 2.2 Projection Maintenance: Dense-vector multiplication creates an Ω(n^2) bottleneck, motivating a data structure that maintains an approximation of Pv faster than quadratic time.Breaking this bottleneck is the route to an O(n^ω)-time solver over O(√n) iterations.
- 2.2 Projection Maintenance: The data structure approximates both the changing projection matrix and the vector, using multiplicative updates that are small in ℓ2 norm.The vector is represented as f(μ/t), and the maintained quantity is ePev rather than the exact Pv.
- 2.2 Projection Maintenance: The central-path update sequence satisfies bounded relative changes, allowing the data structure to maintain approximate projections efficiently throughout the iterations.For the generated sequence, the relative change in u is bounded by a constant, with an analogous statement for μ.
3 Preliminaries
This section defines the notation for entry-wise vector operations, coordinatewise approximation, multiplicative change, and fast matrix multiplication parameters used later.
- The linear programs assume A has full row rank d with n ≥ d, and matrix multiplication and inversion use the matrix exponent ω, with current bounds ω ≈ 2.38 and α ≈ 0.31.Here α is the dual matrix exponent governing rectangular multiplication.
- For vectors, products and divisions are interpreted entry-wise, while v ≤ w means every coordinate of v is at most the corresponding coordinate of w.The notation also defines ℓp-norms and scalar entry-wise operations.
- The relation v ≈_ε w denotes a (1 ± ε)-approximation, but it is not symmetric; for ε ≤ 1/2, it implies w ≈_2ε v.
- Multiplicative change measures relative coordinate differences as ||(v − w)/w||_2, equivalently ||v/w − 1||_2.For an update v_new = v + δv, this is also ||v^-1δv||_2.
- The product of vectors with bounded ℓ2 multiplicative changes also admits a bounded multiplicative-change analysis, including reciprocal vectors.
4 Projection Maintenance
The projection-maintenance data structure deterministically maintains an approximate matrix–vector product while diagonal inputs and vectors change multiplicatively, using sparse updates and low-rank maintenance.
- 4 Projection Maintenance: The data structure maintains U f(v) approximately by (1 ± ε_mp)-approximating both the diagonal matrix U and vector v, extending earlier maintenance of U alone.
- 4 Projection Maintenance: Lemma 4.1 provides deterministic Initialize and Update operations for a full-rank matrix A, with preprocessing time O(n^2d^(ω−2)) and accuracy parameter 0 < ε_mp < 1/4.
- 4.2 Correctness: The correctness proof covers large matrix changes, large vector changes, and small changes, using low-rank updates based on the Sherman–Morrison–Woodbury identity.
- 4.1 Outline of Algorithm 1: Updates are efficient when only k coordinates change substantially, because the maintained solution can then be updated using n × k matrices and costs at most O(nk) per term.
- 4.1 Outline of Algorithm 1: The algorithm extends Cohen et al.’s strategy by maintaining the product w = M U f(v) and recomputing it when the approximate vector changes enough, rather than maintaining only M.
- 4.2 Correctness: After every update, the returned approximations satisfy the stated multiplicative guarantees for the updated vectors and the maintained product.
5 Central Path Method
The section proves that the projection-maintenance data structure yields a deterministic short-step central-path solver. The method maintains approximate primal-dual solutions while reducing t until the required accuracy is reached.
- Theorem 1.1 follows by applying the projection-maintenance algorithm to a deterministic linear-program solver.
- Central-path iteration: The central-path method repeatedly decreases t while maintaining feasible x and s with µ approximately equal to t.Once t is sufficiently small, the algorithm obtains a good approximate solution.
- Data-structure interface: The data structure approximately solves the needed linear system while requiring only small changes to its inputs between iterations.The analysis verifies approximate system solving, bounded parameter changes, and preservation of µ approximately equal to t.
- Derandomization: Deterministic approximation replaces Cohen et al.’s random sampling, eliminating the need to bound random-vector variance and simplifying the proof.
- Iteration stability: 3ε bounds the normalized changes in µ/t and u between consecutive iterations.
- Iteration stability: 1.2ε bounds the relative ℓ2 changes in both x and s during an approximate step.
- Potential maintenance: The potential remains bounded by 2n after each update when Φλ(µ/t −1) is initially at most 2n.
- Complexity and termination: O(n^ω log^2(n) log(n/δ)) is the total cost for current ω and α, written as O(n^ω log^2(n) log(n/δ)).The algorithm stops once t < δ^2/(2n), then obtains a solution through Lemma A.3.
6 Open Problems
The section identifies scope and exponent limitations of the claimed near-matrix-multiplication bound, and asks whether the techniques extend to other interior-point algorithms.
- The eO(n^ω) bound is essentially optimal only for d = Ω(n), leaving improvements for d ≪ n as an open issue.
- If future work establishes ω < 2 + 1/6, the solver’s eO(n^2+1/6) term prevents it from remaining optimal.
- A further open question is whether the techniques can speed up other interior-point solvers, such as semidefinite-programming solvers.
A Appendix
The appendix analyzes update costs for the projection-maintenance data structure and records assumptions used to transform approximate solutions into linear-program solutions.
- Update frequency: T = O((kC/ε)^2) bounds the number of coordinates undergoing sufficiently large multiplicative change.
- Update complexity: O(n^2 d^(ω−2)) is the preprocessing cost for computing M = A^T(AUA^T)^−1A.
- Update complexity: Rank-2^ℓ updates cost O(n^ω(1,1,ℓ/log n)) through the Sherman–Morrison–Woodbury identity.
- Update frequency: At least Ω(ε_mp C^−1 2^(ℓ/2) log^−1 n) calls separate rank-2^ℓ updates under bounded per-call multiplicative changes.
- Solution assumptions: The linear-program reduction assumes a bounded polytope diameter and feasible primal-dual vectors.
- Solution assumptions: The transformed solution is an approximate solution to the original linear program.
B Projection Maintenance via Dynamic Linear System Solvers
This section reduces projection maintenance to dynamic linear-system solving and explains how reset strategies extend prior data structures to achieve the required amortized behavior.
- Reduction: Existing dynamic solvers maintain M^−1b under entry changes in O(n^1.529) time, but the projection-maintenance task requires maintaining Pv.
- Reduction: A block-matrix reduction expresses the projection product through selected coordinates of C^−1b.
- Prior limitation: The San04 data structure would require Ω(n^2.529) total solver time because up to Ω(n) entries may change.
- Reset strategy: Applying Cohen et al.’s reset strategy yields the same amortized complexity as Lemma 4.1.
- Reset strategy: The resulting structures exploit the Sherman–Morrison–Woodbury identity while periodically rebuilding after sufficiently many updates.