Gradient-Free Two-Point Methods for Solving Stochastic Nonsmooth Convex Optimization Problems with Small Non-Random Noises

Abstract

We study nonsmooth convex stochastic optimization problems with a two-point zero-order oracle, i.e., at each iteration one can observe the values of the function’s realization at two selected points. These problems are first smoothed out with the well-known technique of double smoothing (B.T. Polyak) and then solved with the stochastic mirror descent method. We obtain conditions for the permissible noise level of a nonrandom nature exhibited in the computation of the function’s realization for which the estimate on the method’s rate of convergence is preserved.