swMATH ID: 31742
Software Authors: Vorontsova, E. A.; Gasnikov, A. V.; Gorbunov, E. A.
Description: Accelerated directional search with non-Euclidean prox-structure. 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.
Homepage: https://arxiv.org/abs/1710.00162
Source Code: https://github.com/evorontsova/ACDF
Keywords: first-order accelerated methods; convex optimization; linear coupling method; uniform measure concentration on single euclidean sphere; non-Euclidean prox-structure
Related Software: GitHub; BRENT; DiffSharp
Cited in: 3 Publications

Citations by Year