Sparse Linear Programming via Primal and Dual Augmented Coordinate Descent

Ian En-Hsu Yen, Kai Zhong, Cho-Jui Hsieh, Pradeep Ravikumar, Inderjit S. DhillonNeurIPS 2015 · OpenReview

The Bottleneck in Traditional Linear Programming

Linear Programming (LP) is a foundational tool in optimization, underpinning everything from Support Vector Machines (SVMs) to Markov Decision Processes. However, traditional "gold standard" algorithms like the Simplex method and Interior-Point Methods (IPM) struggle to scale with the massive datasets common in modern machine learning.

The core issue is computational complexity. Traditional solvers scale quadratically ($O(n^2)$) with the number of variables or constraints because they must solve a large linear system of equations at every step. In contrast, most machine learning algorithms aim for linear complexity ($O(n)$). When dealing with millions of variables, a quadratic bottleneck makes optimization prohibitively slow. To address this, researchers need a tractable alternative that scales linearly with the number of non-zero entries in the data.

The AL-CD Approach

To bypass the need for exact linear system solves, this paper introduces a two-layered approach called Primal and Dual Augmented Coordinate Descent (AL-CD). The method relies on four key pillars:

  1. Augmented Lagrangian Method (ALM): Instead of solving the LP directly, ALM transforms it into a sequence of bound-constrained quadratic subproblems. Unlike Interior-Point Methods, where subproblems become increasingly ill-conditioned (and thus harder to solve) as they approach the solution, ALM subproblems remain numerically stable.
  2. Coordinate Descent (CD): To solve these quadratic subproblems, the authors employ Coordinate Descent. Instead of updating all variables simultaneously—which requires an expensive linear system solve—CD updates one variable at a time. This is computationally inexpensive and allows the algorithm to naturally exploit the sparsity of the constraint matrix $A$.
  3. Active-Set Strategy: The algorithm maintains an "active set" of variables that are likely to be non-zero. By ignoring variables that are expected to stay at zero, the solver drastically reduces the work required per iteration.
  4. Hybrid Convergence: For high-precision solutions, the authors transition from Coordinate Descent to a Projected Newton-CG method. This uses the Conjugate Gradient method to find the optimal direction more quickly once the algorithm is near the solution.
Algorithms for RCD and PN-CG

Key Insights

  • Breaking the Quadratic Barrier: For many machine learning problems, the "perfect" precision of a Simplex solver is unnecessary. By using iterative methods (CD) inside a proximal framework (ALM), AL-CD achieves "good enough" precision ($10^{-3}$) in linear time.
  • Sparsity as a Feature: Traditional solvers often lose the benefits of sparsity during the factorization step of solving linear systems. AL-CD works directly with the sparse matrix, ensuring the cost per iteration is strictly proportional to the number of non-zero entries ($nnz(A)$).
  • Theoretical Guarantees: The authors prove that AL-CD achieves global linear convergence. This is mathematically significant because the subproblems are not "strongly convex" (a standard requirement for such proofs). The authors bypass this hurdle using a mathematical tool known as Hoffman’s bound.

Experimental Results

The authors evaluated their solver on large-scale LP instances derived from three common machine learning tasks: L1-regularized Multi-class SVM, Sparse Inverse Covariance Estimation, and Nonnegative Matrix Factorization (NMF). These datasets represent problems with millions of variables and constraints, featuring highly sparse constraint matrices.

The performance gains over CPLEX (a top-tier commercial solver) were dramatic:

  • Speed: On the rcv1 SVM task, AL-CD found a solution in roughly 50 minutes (3,155 seconds), while CPLEX (using Simplex, Dual Simplex, or Barrier methods) failed to finish within 48 hours.
  • Efficiency: For Sparse Inverse Covariance tasks, the proposed method was often 10 to 100 times faster than the CPLEX Barrier method.
  • Precision: While AL-CD is designed for moderate precision ($10^{-3}$)—which is usually sufficient for machine learning—it reached these targets orders of magnitude faster than traditional methods reached their own convergence criteria.
Performance on L1-regularized Multi-class SVM datasets

Limitations and Future Directions

While highly effective for large, sparse machine learning problems, AL-CD has some limitations. If an application requires extremely high precision (e.g., $10^{-12}$), traditional Interior-Point Methods might still be more robust, as Coordinate Descent can slow down significantly when very close to the optimum. Additionally, the algorithm is specifically optimized for "primal-sparse" or "dual-sparse" problems; if a problem is dense (most variables are non-zero at the optimum), the active-set strategy provides little benefit.

Looking forward, the authors suggest that further research into parallelizing the Coordinate Descent steps could lead to even greater speedups on multi-core systems, pushing the boundaries of large-scale linear programming even further.

Summary updated

Abstract

Over the past decades, Linear Programming (LP) has been widely used in different areas and considered as one of the mature technologies in numerical optimization. However, the complexity offered by state-of-the-art algorithms (i.e. interior-point method and primal, dual simplex methods) is still unsatisfactory for problems in machine learning with huge number of variables and constraints. In this paper, we investigate a general LP algorithm based on the combination of Augmented Lagrangian and Coordinate Descent (AL-CD), giving an iteration complexity of $O((\log(1/\epsilon))^2)$ with $O(nnz(A))$ cost per iteration, where $nnz(A)$ is the number of non-zeros in the $m\times n$ constraint matrix $A$, and in practice, one can further reduce cost per iteration to the order of non-zeros in columns (rows) corresponding to the active primal (dual) variables through an active-set strategy. The algorithm thus yields a tractable alternative to standard LP methods for large-scale problems of sparse solutions and $nnz(A)\ll mn$. We conduct experiments on large-scale LP instances from $\ell_1$-regularized multi-class SVM, Sparse Inverse Covariance Estimation, and Nonnegative Matrix Factorization, where the proposed approach finds solutions of $10^{-3}$ precision orders of magnitude faster than state-of-the-art implementations of interior-point and simplex methods.
BibTeX
@inproceedings{yen2015sparse,
  author = {Ian En-Hsu Yen and Kai Zhong and Cho-Jui Hsieh and Pradeep Ravikumar and Inderjit S. Dhillon},
  title = {{Sparse Linear Programming via Primal and Dual Augmented Coordinate Descent}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=Hkbl2DZd-r},
}
Figure