Gradient-free methods for non-smooth convex stochastic optimization with heavy-tailed noise on convex compact

Computational Management Science. 2023. Article 37.

Kornilov N., Gasnikov A., Dvurechensky P., Dvinskikh D.

We present two easy-to-implement gradient-free/zeroth-order methods to optimize a stochastic non-smooth function accessible only via a black-box. The methods are built upon efficient first-order methods in the heavy-tailed case, i.e., when the gradi- ent noise has infinite variance but bounded (1 + 𝜅)-th moment for some 𝜅 ∈ (0, 1]. The first algorithm is based on the stochastic mirror descent with a particular class of uniformly convex mirror maps which is robust to heavy-tailed noise. The second algorithm is based on the stochastic mirror descent and gradient clipping technique. Additionally, for the objective functions satisfying the r-growth condition, faster algorithms are proposed based on these methods and the restart technique.

Keywords: heavy tails, stochastic optimization, Stochastic mirror descent, derivative-free optimization, Gradient clipping, Non-smooth problems