Linear Convergence of a Frank-Wolfe Type Algorithm over Trace-Norm Balls

2017/08/07 by Zeyuan Allen-Zhu, Elad Hazan, Allen-Zhu, Zeyuan +5 · 4 citations
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1708.02105

openalex publication_date 2017/08/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We propose a rank-k variant of the classical Frank-Wolfe algorithm to solve convex optimization over a trace-norm ball. Our algorithm replaces the top singular-vector computation (1-SVD) in Frank-Wolfe with a top-k singular-vector computation (k-SVD), which can be done by repeatedly applying 1-SVD k times. Alternatively, our algorithm can be viewed as a rank-k restricted version of projected gradient descent. We show that our algorithm has a linear convergence rate when the objective function is smooth and strongly convex, and the optimal solution has rank at most k. This improves the convergence rate and the total time complexity of the Frank-Wolfe method and its variants.

Citations

• Smooth minimization of non-smooth functions
• Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets
• Randomized Block Krylov Methods for Stronger and Faster Approximate\n Singular Value Decomposition
• Faster Projection-free Convex Optimization over the Spectrahedron
• LazySVD: Even Faster SVD Decomposition Yet Without Agonizing Pain

Cited by

• Accelerated Frank-Wolfe Algorithms: Complementarity Conditions and Sparsity
• Quantum Algorithms for Projection-Free Sparse Convex Optimization
• First-Order Sparse Convex Optimization: Better Rates with Sparse Updates
• Adaptive Open-Loop Step-Sizes for Accelerated Convergence Rates of the Frank-Wolfe Algorithm

Related

• Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets
• Linear Convergence of Frank-Wolfe for Rank-One Matrix Recovery Without Strong Convexity
• The Frank-Wolfe algorithm: a short introduction
• The Frank-Wolfe Algorithm: A Short Introduction
• On the Convergence of Projected-Gradient Methods with Low-Rank Projections for Smooth Convex Minimization over Trace-Norm Balls and Related Problems