Gradient-free prox-methods with inexact oracle for stochastic convex optimization problems on a simplex

Understand

In the paper we show that euclidian randomization in some situations (i.e.

• for gradient-free method on a simplex) can be as good as the randomization on the unit sphere in 1-norm.
• That is on the simplex example we show that for gradient-free methods the choise of the prox-structure and the choise of a way of randomization have to be connected to each other.
• We demonstrate how it can be done in an optimal way.