# Median Clipping for Zeroth-order Non-Smooth Convex Optimization and Multi-Armed Bandit Problem with Heavy-tailed Symmetric Noise

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

## Key facts

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

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

- [Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2605.24513/) (2026)

## Abstract (arXiv)

In this paper, we consider non-smooth convex optimization with a zeroth-order oracle corrupted by symmetric stochastic noise. Unlike the existing high-probability results requiring the noise to have bounded kappa-th moment with kappa ∈ (1,2], our results allow even heavier noise with any kappa > 0, e.g., the noise distribution can have unbounded expectation. Our convergence rates match the best-known ones for the case of the bounded variance, namely, to achieve function accuracy varepsilon our methods with Lipschitz oracle require tildeO(d2varepsilon-2) iterations for any kappa > 0. We build the median gradient estimate with bounded second moment as the mini-batched median of the sampled gradient differences. We apply this technique to the stochastic multi-armed bandit problem with heavy-tailed distribution of rewards and achieve tildeO(√dT) regret. We demonstrate the performance of our zeroth-order and MAB algorithms for various kappa ∈ (0,2] on synthetic and real-world data. Our methods do not lose to SOTA approaches and dramatically outperform them for kappa ≤ 1.