# Accelerated Stochastic Gradient-free and Projection-free Methods

arXiv: https://arxiv.org/abs/2007.12625 · HTML: https://mlsanity.com/paper/2007.12625/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jul 2020.

## Built on by (most cited first, 12 of 12)

- [Enhancing Sharpness-Aware Optimization Through Variance Suppression](https://mlsanity.com/paper/2309.15639/) (2023)
- [Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithm](https://mlsanity.com/paper/2102.05198/) (2021)
- [Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained Optimization](https://mlsanity.com/paper/2107.06534/) (2021)
- [Adaptive Sampling Quasi-Newton Methods for Zeroth-Order Stochastic Optimization](https://mlsanity.com/paper/2109.12213/) (2021)
- [Adaptive Zeroth-Order Optimisation of Nonconvex Composite Objectives](https://mlsanity.com/paper/2208.04579/) (2022)
- [Gradient-Free Method for Heavily Constrained Nonconvex Optimization](https://mlsanity.com/paper/2409.00459/) (2024)
- [Adaptive Lipschitz-Free Conditional Gradient Methods for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/2603.06369/) (2026)
- [Using Taylor-Approximated Gradients to Improve the Frank-Wolfe Method for Empirical Risk Minimization](https://mlsanity.com/paper/2208.13933/) (2022)
- [Adaptive Stochastic Optimisation of Nonconvex Composite Objectives](https://mlsanity.com/paper/2211.11710/) (2022)
- [How to Boost Any Loss Function](https://mlsanity.com/paper/2407.02279/) (2024)
- [An Enhanced Zeroth-Order Stochastic Frank-Wolfe Framework for Constrained Finite-Sum Optimization](https://mlsanity.com/paper/2501.07201/) (2025)
- [Mirror Descent Linearized Augmented Lagrangian Methods for Nonconvex Constrained Stochastic Zeroth-Order Optimization](https://mlsanity.com/paper/2504.09409/) (2025)

## Abstract (arXiv)

In the paper, we propose a class of accelerated stochastic gradient-free and projection-free (a.k.a., zeroth-order Frank-Wolfe) methods to solve the constrained stochastic and finite-sum nonconvex optimization. Specifically, we propose an accelerated stochastic zeroth-order Frank-Wolfe (Acc-SZOFW) method based on the variance reduced technique of SPIDER/SpiderBoost and a novel momentum accelerated technique. Moreover, under some mild conditions, we prove that the Acc-SZOFW has the function query complexity of O(d√nε-2) for finding an ε-stationary point in the finite-sum problem, which improves the exiting best result by a factor of O(√nε-2), and has the function query complexity of O(dε-3) in the stochastic problem, which improves the exiting best result by a factor of O(ε-1). To relax the large batches required in the Acc-SZOFW, we further propose a novel accelerated stochastic zeroth-order Frank-Wolfe (Acc-SZOFW*) based on a new variance reduced technique of STORM, which still reaches the function query complexity of O(dε-3) in the stochastic problem without relying on any large batches. In particular, we present an accelerated framework of the Frank-Wolfe methods based on the proposed momentum accelerated technique. The extensive experimental results on black-box adversarial attack and robust black-box classification demonstrate the efficiency of our algorithms.