Matching the Universal Barrier Without Paying the Costs : Solving Linear Programs with Õ(sqrt(rank)) Linear System Solves.

Yin Tat Lee, Aaron Sidford

TL;DR

This paper introduces a "weighted path-finding" interior point method that solves linear programs in $\tilde{O}(\sqrt{rank(\mathbf{A})}L)$ iterations, finally matching a 20-year-old theoretical limit. By adaptively weighting constraints based on their geometric importance, the authors achieve the efficiency of the "universal barrier" using only standard, computationally cheap linear system solves.

What Problem Does This Paper Address?

Linear Programming (LP) is a cornerstone of computer science, used in everything from logistics to machine learning. Since the 1980s, Interior Point Methods (IPMs) have been the dominant way to solve them in polynomial time. However, for over two decades, the field hit a wall.

Standard IPMs require $O(\sqrt{m}L)$ iterations, where $m$ is the number of constraints. If you have a problem with a million constraints but only a few thousand variables, this $\sqrt{m}$ factor becomes a massive bottleneck. In 1994, Nesterov and Nemirovski proved that a "universal barrier" exists that could solve LPs in $O(\sqrt{n}L)$ iterations (where $n$ is the number of variables/rank), but this barrier was purely theoretical and NP-hard to compute. The challenge addressed here is: Can we achieve the $\sqrt{n}$ iteration count using only practical, fast linear algebra?

Methods

The authors depart from the standard "central path" approach by introducing Weighted Path Finding.

  1. Weighted Log Barrier: Instead of the standard logarithmic barrier function, they use a weighted version: $\phi(x, w) = -\sum w_i \log(s_i)$, where $s_i$ are the "slacks" (distances to constraints) and $w_i$ are adaptive weights.
  2. Leverage Score Weighting: The key innovation is how these weights are chosen. The weights are updated to reflect the "leverage scores" of the constraints—essentially a measure of how much a specific constraint defines the local geometry of the feasible region.
  3. The "Chasing 0" Game: Updating weights too aggressively can kick the algorithm off the central path. The authors formulate a strategy called the "Chasing 0" game to smooth out weight updates. This ensures the weights stay close to the ideal leverage scores while maintaining "centrality" for the optimization steps.
  4. Standard Solves: Crucially, each iteration only requires solving a small number of linear systems of the form $(\mathbf{A}^T\mathbf{D}\mathbf{A})x = y$. This makes the algorithm compatible with modern, fast linear system solvers and highly parallelizable.

Datasets

This is a theoretical paper focused on algorithmic complexity and provable bounds. No empirical datasets were used for evaluation. The results are established through rigorous mathematical proofs.

Key Insights and Ideas

  • Geometry over Counting: Standard methods treat all constraints as equally "heavy." This paper realizes that some constraints are geometrically more important than others. By weighting them, the algorithm "sees" the rank of the system rather than just the count of the constraints.
  • Approximate John Ellipsoids: The method can be viewed as a way to efficiently approximate the "John Ellipsoid"—the largest volume ellipsoid inside a polytope. This connection to convex geometry explains why the iteration count scales with rank.
  • Decoupling Computation: The authors show that you don't need exact weights to succeed. By proving that "approximate weights suffice," they allow the use of randomized techniques (like Johnson-Lindenstrauss projections) to estimate leverage scores quickly.

Key Results

  • Iteration Bound: Achieves $\tilde{O}(\sqrt{rank(\mathbf{A})}L)$ iterations, matching the theoretical limit of the universal barrier up to polylogarithmic factors.
  • Speedup: For problems where the number of constraints $m$ is much larger than the rank $n$, this provides a factor of $\tilde{\Omega}((m/n)^{1/4})$ to $\tilde{\Omega}((m/n)^{1/2})$ improvement over previous state-of-the-art methods.
  • Total Complexity: The algorithm runs in $\tilde{O}((nnz(\mathbf{A}) + rank(\mathbf{A})^\omega) \sqrt{rank(\mathbf{A})}L)$ time, where $\omega$ is the matrix multiplication constant ($< 2.3729$).
  • Parallelism: This is the first depth-efficient (parallelizable) algorithm to achieve this iteration bound.

Limitations and Future Work

  • Polylogarithmic Overhead: The "$\tilde{O}$" notation hides several logarithmic factors. While theoretically superior, these factors might make the algorithm slower than simpler methods for very small-scale problems.
  • Implementation Complexity: Implementing the "Chasing 0" weight update strategy and the approximate leverage score solver is significantly more complex than standard IPMs.
  • Practical Benchmarking: As a theoretical breakthrough, the paper does not provide an optimized C++/CUDA implementation. Future work involves seeing how these theoretical gains translate to real-world solvers like Gurobi or CPLEX.
  • Path Finding II: The authors suggest these techniques can be extended to specific combinatorial problems, such as Maximum Flow, which they explore in subsequent work.

Summary updated

Abstract

In this paper we present a new algorithm for solving linear programs that requires only $\tilde{O}(\sqrt{rank(A)}L)$ iterations to solve a linear program with $m$ constraints, $n$ variables, and constraint matrix $A$, and bit complexity $L$. Each iteration of our method consists of solving $\tilde{O}(1)$ linear systems and additional nearly linear time computation. Our method improves upon the previous best iteration bound by factor of $\tilde{\Omega}((m/rank(A))^{1/4})$ for methods with polynomial time computable iterations and by $\tilde{\Omega}((m/rank(A))^{1/2})$ for methods which solve at most $\tilde{O}(1)$ linear systems in each iteration. Our method is parallelizable and amenable to linear algebraic techniques for accelerating the linear system solver. As such, up to polylogarithmic factors we either match or improve upon the best previous running times in both depth and work for different ratios of $m$ and $rank(A)$. Moreover, our method matches up to polylogarithmic factors a theoretical limit established by Nesterov and Nemirovski in 1994 regarding the use of a "universal barrier" for interior point methods, thereby resolving a long-standing open question regarding the running time of polynomial time interior point methods for linear programming.
BibTeX
@misc{lee2013matching,
  author = {Yin Tat Lee and Aaron Sidford},
  title = {{Matching the Universal Barrier Without Paying the Costs : Solving Linear Programs with Õ(sqrt(rank)) Linear System Solves.}},
  year = {2013},
  eprint = {1312.6677},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1312.6677},
}
Figure