mlsanityData to 7 Oct 2026

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

arXiv 1708.02105 ↗First posted 7 Aug 2017cs.LG cs.DS math.OCcited by 15

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 15 papers in the map (data through 7 Oct 2026). First posted on arXiv 7 Aug 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 3; 2023: 0; 2024: 1; 2025: 5; 2026: 1.

15 papers.

Sort:

  1. 2024Chain of LoRA: Efficient Fine-tuning of Language Models via Residual Learningcited by 80
  2. 2021Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structurescited by 19
  3. 2022Iterative Hard Thresholding with Adaptive Regularization: Sparser Solutions Without Sacrificing Runtimecited by 9
  4. 2021Frank-Wolfe with a Nearest Extreme Point Oraclecited by 8
  5. 2021Heavy Ball Momentum for Conditional Gradientcited by 7
  6. 2022Frank-Wolfe-based Algorithms for Approximating Tyler's M-estimatorcited by 3
  7. 2022Faster Projection-Free Augmented Lagrangian Methods via Weak Proximal Oraclecited by 3
  8. 2025First-Order Sparse Convex Optimization: Better Rates with Sparse Updatescited by 1
  9. 2021Generating Structured Adversarial Attacks Using Frank-Wolfe Methodcited by 0
  10. 2021Approximate Frank-Wolfe Algorithms over Graph-structured Support Setscited by 0
  11. 2025An Enhanced Zeroth-Order Stochastic Frank-Wolfe Framework for Constrained Finite-Sum Optimizationcited by 0
  12. 2025A Randomized Linearly Convergent Frank-Wolfe-type Method for Smooth Convex Minimization over the Spectrahedroncited by 0
3 more
  1. 2025Quantum Algorithms for Projection-Free Sparse Convex Optimizationcited by 0
  2. 2025Accelerated Frank-Wolfe Algorithms: Complementarity Conditions and Sparsitycited by 0
  3. 2026Complexities of Weak Proximal Oracle Methods for Composite Convex Optimizationcited by 0