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

Abstract

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. It is important that we consider inexact oracle.

26 pages, in Russian, Avtomatika i Telemekhanika. 2016

References in corpus (2)

• Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions
• Simple Complexity Analysis of Simplified Direct Search

Cited by in corpus (3)

• An Accelerated Directional Derivative Method for Smooth Stochastic Convex Optimization
• Recent theoretical advances in decentralized distributed convex optimization
• Zeroth-Order Algorithms for Smooth Saddle-Point Problems