Nearly-Linear Time Packing and Covering LP Solver with Faster Convergence Rate Than $O(1/\varepsilon^2)$

Zeyuan Allen Zhu, Lorenzo OrecchiaarXiv 2014 · OpenReview

Authors: Zeyuan Allen-Zhu and Lorenzo Orecchia

Abstract

Packing and covering linear programs (PC-LPs) form an important class of linear programs (LPs) across computer science, operations research, and optimization. In 1993, Luby and Nisan constructed an iterative algorithm for approximately solving PC-LPs in nearly linear time, where the time complexity scales nearly linearly in $N$, the number of nonzero entries of the matrix, and polynomially in $\varepsilon$, the (multiplicative) approximation error. Unfortunately, all existing nearly linear-time algorithms for solving PC-LPs require time at least proportional to $\varepsilon^{-2}$. In this paper, we break this longstanding barrier by designing a packing solver that runs in time $\tilde{O}(N \varepsilon^{-1})$ and covering LP solver that runs in time $\tilde{O}(N \varepsilon^{-1.5})$. Our packing solver can be extended to run in time $\tilde{O}(N \varepsilon^{-1})$ for a class of well-behaved covering programs. At high level, these two algorithms can be described as linear couplings of several first-order descent steps.

The Problem: Scaling Optimization for Big Data

Linear Programming (LP) is a cornerstone of computer science, used for everything from scheduling to network flow. However, general LP solvers, such as Interior Point methods, often scale poorly with the number of variables and constraints, making them unsuitable for massive datasets.

To handle such scale, researchers utilize iterative approximate solvers. These algorithms aim for an approximate solution within an error margin ($\varepsilon$) rather than an exact one. For the specific class of Packing and Covering LPs (where all matrix coefficients are non-negative), an ideal algorithm must be:

  1. Nearly Linear-Time: Running time scales linearly with the number of non-zero entries ($N$).
  2. Width-Independent: Performance does not degrade based on the magnitude of the matrix values (the "width").
  3. Fast Converging: The error $\varepsilon$ shrinks rapidly as iterations progress.

Prior to this work, all width-independent, nearly linear-time solvers were limited to a convergence rate of $O(1/\varepsilon^2)$. For high-precision requirements (e.g., $\varepsilon = 0.01$), this necessitated $10,000$ iterations, creating a significant computational bottleneck.

Methodology: The Linear Coupling Framework

The authors achieve this breakthrough by moving away from traditional "Dantzig-Wolfe" type algorithms, instead utilizing a framework called Linear Coupling.

  • Linear Coupling: This technique combines Gradient Descent (effective for local progress) with Mirror Descent (superior for global convergence). By coupling these steps, the algorithm achieves "acceleration" similar to Nesterov’s accelerated gradient method, but tailored for the non-negativity constraints of PC-LPs.
  • Smoothing and Truncation: The authors transform hard constraints into a smooth objective function using entropy regularization (exponential penalty functions). To maintain stability against the massive gradient values these penalties can produce, they introduce Truncated Gradients, allowing the solver to make aggressive progress without overshooting.
  • Randomized Coordinate Descent: To ensure nearly linear-time performance, the algorithm updates random coordinates rather than the entire variable set at once, minimizing the work required per iteration.

Results and Comparison

The primary contribution of this research is the theoretical proof of algorithms that finally break the $1/\varepsilon^2$ barrier. The packing solver achieves a rate of $1/\varepsilon$, while the general covering solver reaches $1/\varepsilon^{1.5}$.

Comparison of the proposed algorithms (Theorems 3.4, 5.3, 6.6) against historical state-of-the-art solvers, highlighting the improvement in $\varepsilon$ dependence and width independence.

As shown in the table above, the proposed theorems provide the first instances of solvers that are simultaneously width-independent, nearly linear-time, and possess a convergence rate faster than $O(1/\varepsilon^2)$. Notably, the packing solver matches the efficiency of the best-known combinatorial algorithms for approximate maximum weight bipartite matching using a purely convex optimization approach.

Insights and Future Directions

The paper highlights a curious asymmetry: packing problems are inherently easier to accelerate ($1/\varepsilon$) than general covering problems ($1/\varepsilon^{1.5}$) due to the geometry of their feasible regions. While follow-up work has suggested reductions to bring covering down to $1/\varepsilon$, a direct algorithm for general covering at that rate remains an open challenge.

Furthermore, while these algorithms offer superior theoretical complexity, they are more intricate to implement than standard Multiplicative Weight Update (MWU) methods. Future research may focus on simplifying these accelerated methods or extending them to "mixed" packing and covering problems, which remain significantly more difficult to solve efficiently.

Summary updated

Abstract

Packing and covering linear programs (PC-LPs) form an important class of linear programs (LPs) across computer science, operations research, and optimization. In 1993, Luby and Nisan constructed an iterative algorithm for approximately solving PC-LPs in nearly linear time, where the time complexity scales nearly linearly in $N$, the number of nonzero entries of the matrix, and polynomially in $\varepsilon$, the (multiplicative) approximation error. Unfortunately, all existing nearly linear-time algorithms for solving PC-LPs require time at least proportional to $\varepsilon^{-2}$. In this paper, we break this longstanding barrier by designing a packing solver that runs in time $\tilde{O}(N \varepsilon^{-1})$ and covering LP solver that runs in time $\tilde{O}(N \varepsilon^{-1.5})$. Our packing solver can be extended to run in time $\tilde{O}(N \varepsilon^{-1})$ for a class of well-behaved covering programs. In a follow-up work, Wang et al. showed that all covering LPs can be converted into well-behaved ones by a reduction that blows up the problem size only logarithmically. At high level, these two algorithms can be described as linear couplings of several first-order descent steps. This is an application of our linear coupling technique to problems that are not amenable to blackbox applications known iterative algorithms in convex optimization.
BibTeX
@misc{zhu2014nearly,
  author = {Zeyuan Allen Zhu and Lorenzo Orecchia},
  title = {{Nearly-Linear Time Packing and Covering LP Solver with Faster Convergence Rate Than $O(1/\textbackslash\{\}varepsilon^2)$}},
  year = {2014},
  eprint = {1411.1124},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1411.1124},
}

Loading related content...

Figure