Faster Projection-free Convex Optimization over the Spectrahedron

2016/05/20 by Dan Garber, Garber, Dan · 4 citations
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1605.06203

openalex publication_date 2016/05/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Minimizing a convex function over the spectrahedron, i.e., the set of all positive semidefinite matrices with unit trace, is an important optimization task with many applications in optimization, machine learning, and signal processing. It is also notoriously difficult to solve in large-scale since standard techniques require expensive matrix decompositions. An alternative, is the conditional gradient method (aka Frank-Wolfe algorithm) that regained much interest in recent years, mostly due to its application to this specific setting. The key benefit of the CG method is that it avoids expensive matrix decompositions all together, and simply requires a single eigenvector computation per iteration, which is much more efficient. On the downside, the CG method, in general, converges with an inferior rate. The error for minimizing a β-smooth function after t iterations scales like β/t. This convergence rate does not improve even if the function is also strongly convex. In this work we present a modification of the CG method tailored for convex optimization over the spectrahedron. The per-iteration complexity of the method is essentially identical to that of the standard CG method: only a single eigenvecor computation is required. For minimizing an α-strongly convex and β-smooth function, the expected approximation error of the method after t iterations is: O(min\(β)/(t) ,(\fracβ√\textrmrank(X^*)α^1/4t)^4/3, (\fracβ√αλ_min(X^*)t)²\) , where X^* is the optimal solution. To the best of our knowledge, this is the first result that attains provably faster convergence rates for a CG variant for optimization over the spectrahedron. We also present encouraging preliminary empirical results.

Citations

• A Simpler Approach to Matrix Completion
• Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets
• On the Global Linear Convergence of Frank-Wolfe Optimization Variants
• Fast and Simple PCA via Convex Optimization

Cited by

• Simplex Frank-Wolfe: Linear Convergence and Its Numerical Efficiency for Convex Optimization over Polytopes
• Linear Convergence of a Frank-Wolfe Type Algorithm over Trace-Norm Balls
• Quantum Algorithms for Projection-Free Sparse Convex Optimization
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum

Related

• A Linearly Convergent Frank-Wolfe-type Method for Smooth Convex Minimization over the Spectrahedron
• Spectral Frank-Wolfe Algorithm: Strict Complementarity and Linear Convergence
• Accelerated Frank-Wolfe Algorithms: Complementarity Conditions and Sparsity
• On the Efficient Implementation of the Matrix Exponentiated Gradient Algorithm for Low-Rank Matrix Optimization
• Splitting the Conditional Gradient Algorithm