Accelerated Directional Search with Non-Euclidean Prox-Structure

Abstract

We consider smooth convex optimization problems whose full gradient is not available for their numerical solution. In 2011, Yu.E. Nesterov proposed accelerated gradient-free methods for solving such problems. Since only unconditional optimization problems were considered, Euclidean prox-structures were used. However, if one knows in advance, say, that the solution to the problem is sparse, or rather that the distance from the starting point to the solution in 1-norm and in 2-norm are close, then it is more advantageous to choose a non- Euclidean prox-structure associated with the 1-norm rather than a prox-structure associated with the 1-norm. In this work we present a complete justification of this statement. We propose an accelerated descent method along a random direction with a non-Euclidean prox-structure for solving unconditional optimization problems (in further work, we propose to extend this approach to an accelerated gradient-free method). We obtain estimates of the rate of convergence for the method and show the difficulties of transferring the above-mentioned approach to conditional optimization problems.