# An Accelerated Method for Derivative-Free Smooth Stochastic Convex Optimization

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Feb 2018.

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

- [Decentralized Local Stochastic Extra-Gradient for Variational Inequalities](https://mlsanity.com/paper/2106.08315/) (2021)
- [Heavy-tailed Streaming Statistical Estimation](https://mlsanity.com/paper/2108.11483/) (2021)
- [Leveraging Coordinate Momentum in SignSGD and Muon: Memory-Optimized Zero-Order](https://mlsanity.com/paper/2506.04430/) (2025)
- [Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithm](https://mlsanity.com/paper/2102.05198/) (2021)
- [First-Order Methods for Convex Optimization](https://mlsanity.com/paper/2101.00935/) (2021)
- [Zero-Order One-Point Estimate with Distributed Stochastic Gradient-Tracking Technique](https://mlsanity.com/paper/2210.05618/) (2022)
- [Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms](https://mlsanity.com/paper/2410.02559/) (2024)
- [Gradient-Free Approaches is a Key to an Efficient Interaction with Markovian Stochasticity](https://mlsanity.com/paper/2601.01160/) (2026)

## Abstract (arXiv)

We consider an unconstrained problem of minimizing a smooth convex function which is only available through noisy observations of its values, the noise consisting of two parts. Similar to stochastic optimization problems, the first part is of stochastic nature. The second part is additive noise of unknown nature, but bounded in absolute value. In the two-point feedback setting, i.e. when pairs of function values are available, we propose an accelerated derivative-free algorithm together with its complexity analysis. The complexity bound of our derivative-free algorithm is only by a factor of √n larger than the bound for accelerated gradient-based algorithms, where n is the dimension of the decision variable. We also propose a non-accelerated derivative-free algorithm with a complexity bound similar to the stochastic-gradient-based algorithm, that is, our bound does not have any dimension-dependent factor except logarithmic. Notably, if the difference between the starting point and the solution is a sparse vector, for both our algorithms, we obtain a better complexity bound if the algorithm uses an 1-norm proximal setup, rather than the Euclidean proximal setup, which is a standard choice for unconstrained problems