Stochastic Adversarial Noise in the "Black Box" Optimization Problem

This paper is devoted to the study of the solution of a stochastic convex black box optimization problem. Where the black box problem means that the gradient-free oracle only returns the value of objective function, not its gradient. We consider non-smooth and smooth setting of the solution to the black box problem under adversarial stochastic noise. For two techniques creating gradient-free methods: smoothing schemes via L1 and L2 randomizations, we find the maximum allowable level of adversarial stochastic noise that guarantees convergence. Finally, we analyze the convergence behavior of the algorithms under the condition of a large value of noise level.