Conic Descent Redux for Memory-Efficient Optimization

Bingcong Li, Georgios B. Giannakis

Introduction

Conic programming serves as a foundational framework for modern machine learning and signal processing, underpinning applications ranging from community detection to multi-task learning. Despite its utility, solving these problems at scale remains a significant challenge. Standard first-order methods, such as the Frank-Wolfe (FW) algorithm, often struggle with the "non-compact" nature of conic constraints, which extend to infinity. Traditional remedies involve manually bounding the constraint set, a process that risks excluding the optimal solution. Alternatively, Projected Gradient Descent (PGD) requires computationally expensive operations like Full Singular Value Decomposition (SVD), creating a bottleneck as dimensionality increases.

Furthermore, for Semidefinite Programming (SDP), memory consumption is a critical constraint. Storing an $n \times n$ matrix requires $O(n^2)$ space, which quickly exceeds the capacity of modern hardware for large-scale problems. This paper introduces Momentum Conic Descent (MOCO), a first-order optimization algorithm designed to address these scalability and memory issues while maintaining rigorous theoretical guarantees.

Methodology

MOCO revitalizes the recently proposed Conic Descent (CD) framework by integrating several key innovations aimed at speed and efficiency:

1. Momentum Integration

MOCO incorporates "heavy-ball" momentum into the search process. Rather than relying solely on the current gradient, the algorithm utilizes a weighted average of historical gradients. This smoothing of the search direction leads to more stable trajectories and faster convergence, particularly in landscapes where standard methods might stall.

2. Geometric Interpretation: Ray Search and Minimization

The authors reframe conic optimization as a two-step alternating process:

  • Ray Search: Identifying the optimal direction (ray) within the cone.
  • Ray Minimization: Determining the optimal point along that specific ray.

This geometric decomposition allows for more targeted updates compared to standard projection-based methods.

3. Memory-Efficient Sketching

To circumvent the $O(n^2)$ memory requirement in SDPs, MOCO employs vectorized representations and random sketching. Instead of materializing the full $n \times n$ variable $X$, the algorithm maintains a low-rank sketch. This allows the solution to be reconstructed efficiently without ever exhausting the system's RAM.

4. Greedy Heuristics

The framework incorporates the Burer-Monteiro (BM) factorization, a popular heuristic that exploits the low-rank structure inherent in many high-dimensional SDP solutions. This "greedy" variant, MOCOg, further accelerates convergence in practical scenarios.

Theoretical Insights

A pivotal contribution of this work is the discovery of a formal connection between the geometric "ray search" and dual theory. The authors demonstrate that the ray search step is mathematically equivalent to projecting the gradient onto the dual cone. This provides a rigorous foundation for the algorithm's intuitive search mechanism.

Additionally, the paper introduces a "magical" step size heuristic ($\theta_k$) that allows the algorithm to bypass expensive line searches. While this heuristic requires an estimate of the optimal solution's norm ($\|X^*\|$), it significantly reduces runtime. The authors prove that MOCO achieves a convergence rate of $O(1/k)$ for both primal and dual objectives, with momentum providing a tighter constant factor than its non-momentum predecessors.

Empirical Evaluation

The researchers evaluated MOCO across two primary benchmarks:

  • Matrix Completion: Using synthetic data to recover low-rank positive semidefinite matrices (dimensions $n=100$ to $n=1600$). MOCOg consistently achieved lower primal errors than standard Conic Descent within the same runtime, demonstrating superior scalability.
  • Phase Retrieval: Reconstructing images from quadratic measurements using the CIFAR-10 dataset. This task involves "lifting" a vector problem into a higher-dimensional matrix space. MOCO variants produced significantly clearer image reconstructions compared to the standard Frank-Wolfe algorithm.

Conclusion and Future Work

MOCO represents a significant step forward in making conic programming viable for large-scale applications. By combining momentum with memory-efficient sketching and a deep understanding of dual cone geometry, the authors provide a solver that is both fast and theoretically sound.

Future research directions include the development of universal preconditioning methods to further accelerate dual convergence and refining heuristics for estimating the optimal solution norm to reduce parameter sensitivity. The integration of the Burer-Monteiro step also suggests that further optimization of the unconstrained subproblems could yield even greater performance gains.

Summary updated

BibTeX
@inproceedings{li2023conic,
  author = {Bingcong Li and Georgios B. Giannakis},
  title = {{Conic Descent Redux for Memory-Efficient Optimization}},
  booktitle = {ACSSC},
  year = {2023},
  doi = {10.1109/ieeeconf59524.2023.10476894},
}
Figure