# An Accelerated Directional Derivative Method for Smooth Stochastic Convex Optimization

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

## Key facts

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

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

- [Gradients without Backpropagation](https://mlsanity.com/paper/2202.08587/) (2022)
- [Leveraging Coordinate Momentum in SignSGD and Muon: Memory-Optimized Zero-Order](https://mlsanity.com/paper/2506.04430/) (2025)
- [First-Order Methods for Convex Optimization](https://mlsanity.com/paper/2101.00935/) (2021)
- [Gradient-Free Approaches is a Key to an Efficient Interaction with Markovian Stochasticity](https://mlsanity.com/paper/2601.01160/) (2026)
- [From Cursed to Competitive: Closing the ZO-FO Gap via Input-to-State Stability](https://mlsanity.com/paper/2604.25372/) (2026)

## Abstract (arXiv)

We consider smooth stochastic convex optimization problems in the context of algorithms which are based on directional derivatives of the objective function. This context can be considered as an intermediate one between derivative-free optimization and gradient-based optimization. We assume that at any given point and for any given direction, a stochastic approximation for the directional derivative of the objective function at this point and in this direction is available with some additive noise. The noise is assumed to be of an unknown nature, but bounded in the absolute value. We underline that we consider directional derivatives in any direction, as opposed to coordinate descent methods which use only derivatives in coordinate directions. For this setting, we propose a non-accelerated and an accelerated directional derivative method and provide their complexity bounds. Our non-accelerated algorithm has a complexity bound which is similar to the gradient-based algorithm, that is, without any dimension-dependent factor. Our accelerated algorithm has a complexity bound which coincides with the complexity bound of the accelerated gradient-based algorithm up to a factor of square root of the problem dimension. We extend these results to strongly convex problems.