On approximations of the PSD cone by a polynomial number of smaller-sized PSD cones

Dogyoon Song, Pablo A. ParriloMath. Program 2023 · DOI · OpenReview

TL;DR

This paper investigates how well we can approximate the cone of positive semidefinite (PSD) matrices using smaller PSD constraints. The authors prove that to achieve a good approximation, you need an exponentially large number of smaller PSD constraints if the constraint size is significantly smaller than the matrix size. This has implications for the scalability of semidefinite programming.

What Problem Does This Paper Address?

Semidefinite programming (SDP) is a powerful optimization technique, but solving large-scale SDPs can be computationally expensive due to the size of the PSD cone constraints. Researchers are interested in approximating the PSD cone with simpler structures that are easier to handle computationally. This paper tackles the question: "How closely can we approximate the set of $n \times n$ PSD matrices (specifically, those with unit trace) using at most $N$ constraints of size $k \times k$?" This is crucial for developing more efficient algorithms for large-scale SDPs.

Methods

The paper explores two main avenues for constructing approximations and then proves lower bounds on the number of smaller PSD constraints ($N$) required.

  1. k-PSD Approximations: This involves restricting the PSD condition to $k$-dimensional subspaces of $\mathbb{R}^n$. The authors define a cone $S_k^n(V)$ based on a set of $N$ such subspaces $V$. They then derive a lower bound on $N$ needed for $S_k^n(V)$ to be a "dual-average $\epsilon$-approximation" of the PSD cone. This bound is exponential in $n$ for $k = o(n)$.
  2. Approximate Extended Formulations: This approach allows for introducing auxiliary variables to describe the approximation. The authors introduce the concept of "$S_+^k$-extension complexity," which measures the minimum number of $k \times k$ PSD constraints needed in an extended formulation. They prove superpolynomial lower bounds on this complexity for any set that approximates the PSD cone within a constant ratio.

The proofs rely on advanced techniques from convex geometry, Gaussian processes, and probability theory, including Gaussian width, Slepian's lemma, and hypercontractivity inequalities.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Fundamental Trade-off: There's a fundamental trade-off between the size of the smaller PSD constraints ($k$) and the number of constraints ($N$) needed for a good approximation. If $k$ is much smaller than $n$, you need a lot of constraints.
  • "Bad" Directions Matter: The paper highlights that even if an approximation is good "on average" (in terms of Gaussian width), it might still be poor in specific directions. This motivates the use of different notions of approximation (e-approximation, average e-approximation, dual-average e-approximation).
  • Extension Complexity is Key: The concept of $S_+^k$-extension complexity provides a powerful tool to understand the inherent difficulty of approximating the PSD cone, even when allowing for more complex formulations.
  • Generalization of Prior Work: The results generalize previous work on approximating the PSD cone using linear programming (which corresponds to $k=1$).

Key Results

  • For $k = o(n)$, approximating the $n \times n$ PSD cone requires at least an exponentially large number of $k \times k$ PSD constraints when using $k$-PSD approximations.
  • Any set that approximates the PSD cone within a constant ratio needs an $S_+^k$-extension complexity of at least $\exp(C \cdot \min\{\sqrt{n}, n/k\})$.
  • These results imply that the $n \times n$ PSD cone cannot be approximated by a polynomial number of $k \times k$ PSD constraints for any $k = o(n / \log^2 n)$.

Limitations and Future Work

  • Tightness of Bounds: The authors acknowledge that their lower bounds on extension complexity might not be tight and leave it as an open problem to achieve stronger bounds through more sophisticated analysis.
  • Specific Approximations: While the paper provides general hardness results, it also analyzes the "sparse $k$-PSD approximation" as a specific example, showing tailored hardness results for it.
  • Data-Dependent Approximations: The current work focuses on global, data-independent approximations. The authors mention that exploiting problem data ($C, A_i, b_i$) might allow for good approximations with fewer constraints, as evidenced in prior empirical work.

Summary updated

Abstract

We study the problem of approximating the cone of positive semidefinite (PSD) matrices with a cone that can be described by smaller-sized PSD constraints. Specifically, we ask the question: “how closely can we approximate the set of unit-trace $$n \times n$$ n × n PSD matrices, denoted by D, using at most N number of $$k \times k$$ k × k PSD constraints?” In this paper, we prove lower bounds on N to achieve a good approximation of D by considering two constructions of an approximating set. First, we consider the unit-trace $$n \times n$$ n × n symmetric matrices that are PSD when restricted to a fixed set of k-dimensional subspaces in $${\mathbb {R}}^n$$ R n . We prove that if this set is a good approximation of D, then the number of subspaces must be at least exponentially large in n for any $$k = o(n)$$ k = o ( n ) . Second, we show that any set S that approximates D within a constant approximation ratio must have superpolynomial $${\varvec{S}}_+^k$$ S + k -extension complexity. To be more precise, if S is a constant factor approximation of D, then S must have $${\varvec{S}}_+^k$$ S + k -extension complexity at least $$\exp ( C \cdot \min \{ \sqrt{n}, n/k \})$$ exp ( C · min { n , n / k } ) where C is some absolute constant. In addition, we show that any set S such that $$D \subseteq S$$ D ⊆ S and the Gaussian width of S is at most a constant times larger than the Gaussian width of D must have $${\varvec{S}}_+^k$$ S + k -extension complexity at least $$\exp ( C \cdot \min \{ n^{1/3}, \sqrt{n/k} \})$$ exp ( C · min { n 1 / 3 , n / k } ) . These results imply that the cone of $$n \times n$$ n × n PSD matrices cannot be approximated by a polynomial number of $$k \times k$$ k × k PSD constraints for any $$k = o(n / \log ^2 n)$$ k = o ( n / log 2 n ) . These results generalize the recent work of Fawzi (Math Oper Res 46(4):1479–1489, 2021) on the hardness of polyhedral approximations of $${\varvec{S}}_+^n$$ S + n , which corresponds to the special case with $$k=1$$ k = 1 .
BibTeX
@article{song2023approximations,
  author = {Dogyoon Song and Pablo A. Parrilo},
  title = {{On approximations of the PSD cone by a polynomial number of smaller-sized PSD cones}},
  journal = {Math. Program.},
  year = {2023},
  doi = {10.1007/s10107-022-01795-7},
}
Figure