mlsanityData to 14 Oct 2026

Scalable Projection-Free Optimization

arXiv 2105.03527 ↗First posted 7 May 2021math.OC stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

As a projection-free algorithm, Frank-Wolfe (FW) method, also known as conditional gradient, has recently received considerable attention in the machine learning community. In this dissertation, we study several topics on the FW variants for scalable projection-free optimization. We first propose 1-SFW, the first projection-free method that requires only one sample per iteration to update the optimization variable and yet achieves the best known complexity bounds for convex, non-convex, and monotone DR-submodular settings. Then we move forward to the distributed setting, and develop Quantized Frank-Wolfe (QFW), a general communication-efficient distributed FW framework for both convex and non-convex objective functions. We study the performance of QFW in two widely recognized settings: 1) stochastic optimization and 2) finite-sum optimization. Finally, we propose Black-Box Continuous Greedy, a derivative-free and projection-free algorithm, that maximizes a monotone continuous DR-submodular function over a bounded convex body in Euclidean space.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 60 of its 123 references that are in the map. First posted on arXiv 7 May 2021.

Builds on

60 of 123 references.

References · 60

  1. 2019Introduction to Online Convex Optimizationcited by 803
  2. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  3. 2017ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Modelscited by 666
  4. 2018signSGD: Compressed Optimisation for Non-Convex Problemscited by 571
  5. 2018Black-box Adversarial Attacks with Limited Queries and Informationcited by 501
  6. 2018Sparsified SGD with Memorycited by 376
  7. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
  8. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
  9. 2017TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learningcited by 256
  10. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 220
  11. 2016QSGD: Communication-Efficient SGD via Gradient Quantization and Encodingcited by 147
  12. 2017Cooperative Game Theory Approaches for Network Partitioningcited by 135
38 more
  1. 2015An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedbackcited by 111
  2. 2018Stochastic Variance-Reduced Policy Gradientcited by 106
  3. 2016Variance Reduction for Faster Non-Convex Optimizationcited by 72
  4. 2016Convergence Rate of Frank-Wolfe for Non-Convex Objectivescited by 63
  5. 2017Stochastic Zeroth-order Optimization in High Dimensionscited by 63
  6. 2017Stochastic Variance Reduction Methods for Policy Evaluationcited by 58
  7. 2018On the Ineffectiveness of Variance Reduced Optimization for Deep Learningcited by 48
  8. 2018Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximizationcited by 47
  9. 2016Variance-Reduced and Projection-Free Stochastic Optimizationcited by 40
  10. 2018Zeroth-order Nonconvex Stochastic Optimization: Handling Constraints, High-Dimensionality and Saddle-Pointscited by 37
  11. 2018Online Continuous Submodular Maximizationcited by 35
  12. 2018Discrete Adversarial Attacks and Submodular Optimization with Applications to Text Classificationcited by 35
  13. 2017Gradient Methods for Submodular Maximizationcited by 33
  14. 2019Online Continuous Submodular Maximization: From Full-Information to Bandit Feedbackcited by 33
  15. 2014Near-Optimally Teaching the Crowd to Classifycited by 32
  16. 2019One Sample Stochastic Frank-Wolfecited by 32
  17. 2015Taming the Wild: A Unified Analysis of Hogwild!-Style Algorithmscited by 31
  18. 2016Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domainscited by 31
  19. 2018Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularitycited by 31
  20. 2015Submodular Functions: from Discrete to Continous Domainscited by 25
  21. 2017Conditional Gradient Method for Stochastic Submodular Maximization: Closing the Gapcited by 21
  22. 2014Distributed Submodular Maximizationcited by 20
  23. 2017Stochastic Recursive Gradient Algorithm for Nonconvex Optimizationcited by 20
  24. 2016How to be Fair and Diverse?cited by 18
  25. 2014Online Submodular Maximization under a Matroid Constraint with Application to Learning Assignmentscited by 17
  26. 2018Projection-Free Bandit Convex Optimizationcited by 17
  27. 2018Towards Gradient Free and Projection Free Stochastic Optimizationcited by 15
  28. 2018Escaping Saddle Points in Constrained Optimizationcited by 14
  29. 2017Weakly Submodular Maximization Beyond Cardinality Constraints: Does Randomization Help Greedy?cited by 13
  30. 2016Stochastic Structured Prediction under Bandit Feedbackcited by 12
  31. 2017Non-convex Conditional Gradient Slidingcited by 12
  32. 2018Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximizationcited by 12
  33. 2017Stochastic Submodular Maximization: The Case of Coverage Functionscited by 11
  34. 2018Deep Frank-Wolfe For Neural Network Optimizationcited by 11
  35. 2019Black Box Submodular Maximization: Discrete and Continuous Settingscited by 9
  36. 2016Lazifying Conditional Gradient Algorithmscited by 8
  37. 2017Robust Budget Allocation via Continuous Submodular Functionscited by 8
  38. 2018Unconstrained Submodular Maximization with Constant Adaptive Complexitycited by 8

50 most cited of 60 All 60 (JSON)

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2021Communication-Efficient Distributed Optimization with Quantized Preconditioners
  2. 2021Derivative-free Alternating Projection Algorithms for General Nonconvex-Concave Minimax Problems
  3. 2024Flattened one-bit stochastic gradient descent: compressed distributed optimization with controlled variance
  4. 2026Quantized Stochastic Primal-Dual Methods for Distributed Optimization under Relaxed Global Geometry
  5. 2026Denoising as Projection: Constrained Optimization with Gradient-Guided Diffusion
  6. 2025A Universal Banach--Bregman Framework for Stochastic Iterations: Unifying Stochastic Mirror Descent, Learning and LLM Training
  7. 2025Zeroth-Order Optimization Finds Flat Minima
  8. 2021Efficient Randomized Subspace Embeddings for Distributed Optimization under a Communication Budget