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

2024/02/04 by Kornilov, Nikita, Dorn, Yuriy, Lobanov, Aleksandr +5
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2402.02461

Abstract

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 κ-th moment with κ∈ (1,2], our results allow even heavier noise with any κ> 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 ε our methods with Lipschitz oracle require O(d²ε^-2) iterations for any κ> 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 O(√(dT)) regret. We demonstrate the performance of our zeroth-order and MAB algorithms for various κ∈ (0,2] on synthetic and real-world data. Our methods do not lose to SOTA approaches and dramatically outperform them for κ≤ 1.

Related

• Fast UCB-type algorithms for stochastic bandits with heavy and super heavy symmetric noise
• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise
• Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping
• Clipped Gradient Methods for Nonsmooth Convex Optimization under Heavy-Tailed Noise: A Refined Analysis