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, specifically for a class of problems known as Positive Semidefinite Programs (SDPs).

TL;DR

The authors present the first "width-independent" parallel algorithm for positive SDPs that matches the efficiency of the best linear programming (LP) solvers. By introducing a new matrix inequality and a randomized update strategy, they reduce the required iterations from a staggering $O(\log^{14} n)$ to a practical $O(\log^2 n)$, while simultaneously fixing theoretical flaws in previous attempts.

What Problem Does This Paper Address?

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. However, general SDP solvers are often too slow for "big data" applications.

Researchers have focused on Positive SDPs (packing and covering problems), which are a natural generalization of Linear Programs where variables are matrices rather than vectors. The goal is to find a solver that is:

  1. Parallelizable: Can run in "polylogarithmic depth" (very fast on many processors).
  2. Width-Independent: The runtime shouldn't explode based on the specific numerical values (the "width") of the input matrices.
  3. Simple: Avoiding complex "phases" or "restarts" that make algorithms hard to implement.

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

Methods

The authors propose an algorithm called PosSDPSolver based on a convex optimization framework. Their approach involves several novel technical components:

  • Optimization Framework: Instead of traditional "multiplicative weight updates," they treat the SDP as a minimization problem for a smooth, convex objective function.
  • Sign-Consistent Randomization: To handle the fact that matrix updates don't behave as predictably as vector updates, the algorithm flips a coin at each step. It chooses to either only increase or only decrease variables in a "sign-consistent" manner. This ensures that 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}$ does not equal $e^A e^B$ unless the matrices commute. This non-commutativity usually breaks convergence proofs. The authors proved a new version of the Lieb-Thirring inequality to provide the necessary bounds to guarantee the algorithm stays on track.

Datasets

Not discussed in the paper. This is a theoretical computer science paper focused on algorithmic complexity and mathematical proofs. It does not include empirical tests on specific datasets.

Key Insights and Ideas

  • The "Monotonicity" Trap: Previous researchers tried to port LP techniques directly to SDPs. In LPs, if you decrease a variable, the gradient changes predictably. In SDPs, because matrices don't commute, decreasing a variable can actually cause the gradient to fluctuate wildly. The authors realized they couldn't rely on coordinate-wise monotonicity.
  • Average Behavior Matters: Even if a single coordinate behaves badly, the authors showed that a weighted sum of the gradients maintains the correct sign. This "average" stability is enough to prove convergence.
  • Simultaneous Solving: The algorithm is "primal-dual," meaning it solves both the "Packing" (maximizing) and "Covering" (minimizing) versions of the problem at the same time with the same efficiency.

Key Results

  • Massive Speedup: The iteration complexity is improved to $O(\frac{\log n \cdot \log(nm/\epsilon)}{\epsilon^3})$. This is a massive leap over the previous best-known correct bound of $O(\log^{14} n / \epsilon^{13})$.
  • Optimal Parallelism: The algorithm achieves a parallel depth of $O(\log^2 (nm) / \epsilon)$, making it highly suitable for modern distributed computing environments.
  • Simplicity: The algorithm is significantly simpler than its predecessors, as it eliminates the need for complex "restarts" or "phases" during the optimization process.

Limitations and Future Work

  • Randomization: The algorithm provides a $(1 \pm \epsilon)$-approximation with "constant probability." While this probability can be boosted by repeating the algorithm, 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 in a footnote that this could likely be improved to $1/\epsilon^2$ using techniques from recent LP solvers, which they intended to include in future versions of the work.
  • Matrix Exponentials: Like all solvers in this class, the bottleneck is computing matrix exponentials. While this is polylogarithmic in parallel, it remains 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 log2 n/∊3 parallelizable iterations [4], the best known positive SDP solvers due to Jain and Yao [18] require log14 n/∊13 parallelizable iterations. Several alternative solvers have been proposed to reduce the exponents in the number of iterations [19, 30]. However, the correctness of the convergence analyses in these works has been called into question [30], 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 in [4] for LP solvers. Our algorithm only needs log2 n/∊3 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 [3, 4].
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},
}

Loading related content...

Figure