Optimization over the positive semidefinite (PSD) cone is a cornerstone of modern machine learning, appearing in everything from matrix completion to phase retrieval. Traditionally, if you wanted to use "projection-free" methods like the Conditional Gradient (CG) algorithm, you faced a frustrating hurdle: these methods require the feasible set to be bounded. Since a cone is inherently unbounded, researchers often had to slap on an artificial constraint like $\|x\| \le R$.
But how do you choose $R$? If it's too small, you exclude the optimal solution. If it's a gross overestimate, the algorithm slows to a crawl. In their NeurIPS 2020 paper, Duchi et al. introduce Conic Descent (CD), a method that solves these problems directly on the cone, ditching the need for artificial bounds entirely.
TL;DR
Conic Descent (CD) extends the conditional gradient method to work directly on unbounded convex cones without requiring artificial bounding constraints. By combining this with randomized matrix sketching and a Burer-Monteiro-style greedy step, the authors provide a memory-efficient algorithm for large-scale PSD optimization that offers global convergence guarantees and superior practical performance.
What Problem Does This Paper Address?
The authors target optimization problems of the form: $$\text{minimize } f(x) \text{ subject to } x \in K$$ where $K$ is a proper convex cone (like the PSD cone) and $f$ is a differentiable function.
The standard tool for "projection-free" optimization is the Conditional Gradient (CG) algorithm (also known as Frank-Wolfe). CG is beloved because it avoids expensive projections by solving a linear subproblem at each step. However, CG only works on compact (bounded) sets. To apply it to a cone, you must assume $\|x^*\| \le R$ for some $R$.
The gap here is twofold:
- The "R" Problem: In practice, $R$ is rarely known. Overestimating $R$ significantly degrades CG's performance.
- Memory Bottlenecks: For problems involving $n \times n$ matrices, storing the full matrix variable requires $O(n^2)$ memory, which is prohibitive when $n$ is large.
Methods
The paper introduces Conic Descent (CD). Instead of the standard CG step, CD performs two main actions at each iteration:
- Rescaling: It finds an optimal scaling factor $\eta_k$ for the current iterate, essentially moving toward or away from the origin.
- Descent Direction: It finds a new direction $v_k$ within the cone $K$ (with $\|v_k\| \le 1$) that minimizes the gradient and takes a step in that direction.
Memory Efficiency and Sketching
For the specific case of the PSD cone ($K = S^n_+$), the authors present a memory-efficient version. They avoid storing the full $n \times n$ matrix by:
- Tracking an auxiliary variable: They only store $y = \mathcal{G}(X) - g$, which lives in a much smaller $m$-dimensional space.
- Randomized Sketching: They maintain a "sketch" of the matrix (a much smaller $n \times r$ matrix) that can be used to reconstruct the low-rank optimal solution upon convergence.
The Greedy Step
Perhaps the most practical addition is the optional greedy step. They incorporate the Burer-Monteiro (BM) factorization heuristic—a popular but non-convex approach that is fast but prone to getting stuck in local minima. By using BM as a "greedy step" within the globally convergent CD framework, they get the best of both worlds: the speed of BM and the reliability of CD.
Key Insights and Ideas
- Independence from $R$: CD's convergence rate depends on the norm of the actual optimal solution $\|x^*\|^2$, rather than an arbitrary and potentially massive $R^2$.
- Duality-Based Analysis: The proof of convergence is simplified by using convex duality, showing that if CD cannot find a descent direction, it has found an optimality certificate.
- Hybridization is Key: The "aha moment" for practitioners is that you don't have to choose between global guarantees (CD) and local speed (Burer-Monteiro). The algorithm shows they can be fused effectively.
- Conditioning: The rescaling step in CD often leads to a better-conditioned subproblem compared to standard CG, making it easier to find the minimum eigenvalue.
Key Results
The experimental results demonstrate significant gains in both efficiency and accuracy across two primary tasks: Phase Retrieval (reconstructing CIFAR-10 images) and Matrix Completion.
Phase Retrieval: In tests on 50 images from CIFAR-10, CD consistently outperformed CG. As shown in the histogram below, CD typically required less than half the matrix-vector multiplications that CG needed to reach the same objective value.
Matrix Completion: The results for matrix completion show that "CD with greedy" converges much faster than pure CD. Crucially, it also outperforms pure Burer-Monteiro (PBM) approaches, especially when the rank $r$ is small. PBM often gets stuck in local minima, while CD's global framework pushes the solution toward the true optimum.
Limitations and Future Work
While CD removes the need for a bound $R$, the authors note that if a very tight bound $R$ is known, standard CG might still be competitive. Additionally, the greedy step requires solving a non-convex subproblem at each iteration; while this was efficient in their tests using conjugate gradient methods, it adds implementation complexity.
Future work could involve extending these conic descent principles to other types of cones beyond the PSD cone and further refining the sketching techniques for even higher-dimensional problems.
Summary updated