# On Zeroth-Order Stochastic Convex Optimization via Random Walks

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Feb 2014.

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

- [Problem Dependent View on Structured Thresholding Bandit Problems](https://mlsanity.com/paper/2106.10166/) (2021)

## Abstract (arXiv)

We propose a method for zeroth order stochastic convex optimization that attains the suboptimality rate of tildeO(n7T-1/2) after T queries for a convex bounded function f:mathbb Rn→mathbb R. The method is based on a random walk (the Ball Walk) on the epigraph of the function. The randomized approach circumvents the problem of gradient estimation, and appears to be less sensitive to noisy function evaluations compared to noiseless zeroth order methods.