ACDS 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 Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year Accelerated directional search with non-Euclidean prox-structure. Zbl 1434.90143Vorontsova, E. A.; Gasnikov, A. V.; Gorbunov, E. A. 2019 Cited by 4 Authors 3 Gasnikov, Alexander V. 3 Gorbunov, E. A. 3 Vorontsova, Evgeniya Alexeevna 1 Dvurechensky, Pavel E. Cited in 2 Serials 2 Automation and Remote Control 1 Mathematical Notes Cited in 3 Fields 2 Operations research, mathematical programming (90-XX) 1 Calculus of variations and optimal control; optimization (49-XX) 1 Probability theory and stochastic processes (60-XX) Citations by Year