Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP Solver

Zeyuan Allen Zhu, Yin Tat Lee, Lorenzo Orecchia

This paper, authored by Zeyuan Allen-Zhu, Yin Tat Lee, and Lorenzo Orecchia, represents a significant theoretical breakthrough in the field of continuous optimization. It focuses on a class of problems known as Positive Semidefinite Programs (SDPs), providing the first "width-independent" parallel algorithm that matches the efficiency of the best linear programming (LP) solvers.

The Challenge of Positive SDPs

Semidefinite Programming is a powerful tool used to model complex problems in machine learning (like sparse PCA), combinatorial optimization (like Max-Cut), and quantum information theory. Researchers have specifically focused on Positive SDPs (packing and covering problems), which are a natural generalization of Linear Programs where variables are matrices rather than vectors.

Ideally, a solver for these problems should be:

  1. Parallelizable: Capable of running in "polylogarithmic depth."
  2. Width-Independent: Runtime should not explode based on the numerical values (the "width") of the input matrices.
  3. Simple: Avoiding complex "phases" or "restarts" that hinder implementation.

While Positive LPs were solved efficiently years ago, the SDP version lagged behind. Previous "fast" SDP solvers were either extremely slow in practice—requiring $O(\log^{14} n)$ iterations—or relied on mathematical assumptions about "monotonicity" that are true for numbers but false for matrices, leading to questionable convergence analyses.

Methodology: A New Optimization Framework

The authors propose an algorithm called PosSDPSolver based on a convex optimization framework rather than traditional "multiplicative weight updates." Their approach involves several novel technical components:

  • Sign-Consistent Randomization: In LPs, decreasing a variable changes the gradient predictably. In SDPs, because matrices don't commute, decreasing a variable can cause the gradient to fluctuate wildly. The authors introduced a randomized update strategy that flips a coin at each step to either only increase or only decrease variables. This ensures the objective function decreases "in expectation."
  • The Extended Lieb-Thirring Inequality: This is the paper's mathematical "secret sauce." In matrix algebra, $e^{A+B} \neq e^A e^B$ unless the matrices commute. The authors proved a new version of the Lieb-Thirring inequality to provide the necessary bounds to guarantee the algorithm stays on track despite non-commutativity.
  • Simultaneous Solving: The algorithm is "primal-dual," meaning it solves both the "Packing" (maximizing) and "Covering" (minimizing) versions of the problem simultaneously with the same efficiency.

Key Results and Comparison

The primary contribution of this work is a massive leap in iteration complexity. By reducing the required iterations from $O(\log^{14} n)$ to $O(\log^2 n)$, the authors have brought SDP solvers in line with the performance of the best LP solvers.

Comparison of iteration complexity and parallel depth between various LP and SDP solvers. The red text highlights the improvements made by this paper.

As shown in the table above, the iteration complexity is improved to $O(\frac{\log^2 (nm)}{\epsilon^3})$. This achieves optimal parallelism with a parallel depth of $O(\log^2 (nm) / \epsilon)$, making it highly suitable for modern distributed computing environments. Furthermore, the algorithm is significantly simpler than its predecessors, eliminating the need for complex restarts or phases.

Limitations and Future Work

While this paper marks a major advancement, some areas for future exploration remain:

  • Randomization: The algorithm provides a $(1 \pm \epsilon)$-approximation with constant probability. A purely deterministic version with the same complexity remains an open challenge.
  • The Epsilon Factor: The current paper achieves a $1/\epsilon^3$ dependence. The authors note that this could likely be improved to $1/\epsilon^2$ using techniques from recent LP solvers.
  • Matrix Exponentials: The bottleneck remains the computation of matrix exponentials. While polylogarithmic in parallel, it is still a computationally heavy task for very large matrices.

Summary updated

Abstract

We study the design of polylogarithmic depth algorithms for approximately solving packing and covering semidefinite programs (or positive SDPs for short). This is a natural SDP generalization of the well-studied positive LP problem. Although positive LPs can be solved in polylogarithmic depth while using only $\tilde{O}(\log^{2} n/\varepsilon^2)$ parallelizable iterations, the best known positive SDP solvers due to Jain and Yao require $O(\log^{14} n /\varepsilon^{13})$ parallelizable iterations. Several alternative solvers have been proposed to reduce the exponents in the number of iterations. However, the correctness of the convergence analyses in these works has been called into question, as they both rely on algebraic monotonicity properties that do not generalize to matrix algebra. In this paper, we propose a very simple algorithm based on the optimization framework proposed for LP solvers. Our algorithm only needs $\tilde{O}(\log^2 n / \varepsilon^2)$ iterations, matching that of the best LP solver. To surmount the obstacles encountered by previous approaches, our analysis requires a new matrix inequality that extends Lieb-Thirring's inequality, and a sign-consistent, randomized variant of the gradient truncation technique proposed in.
BibTeX
@inproceedings{zhu2016using,
  author = {Zeyuan Allen Zhu and Yin Tat Lee and Lorenzo Orecchia},
  title = {{Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP Solver}},
  booktitle = {SODA},
  year = {2016},
  url = {https://openreview.net/forum?id=enR17rrw2tA},
}
Figure