Accelerated Directional Search with Non-Euclidean Prox-Structure

Ускоренный спуск по случайному направлению с неевклидовой прокс-структурой

Evgeniya Vorontsova (1, 2) , Alexander Gasnikov (3) , Eduard Gorbunov (3)

1 CVGI - Calcul des Variations, Géométrie, Image
2 FEFU - Far Eastern Federal University
3 MIPT - Moscow Institute of Physics and Technology [Moscow]

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.

Рассматриваются задачи гладкой выпуклой оптимизации,. для численногорешения которых полный градиент недоступен. В 2011 г. Ю.Е. Нестеровымбыли предложены ускоренные безградиентные методы решения таких задач.Поскольку рассматривались только задачи безусловной оптимизации, то ис-пользовалась евклидова прокс-структура. Однако если заранее знать, например,что решение задачи разреженно, а точнее, что расстояние от точки старта дорешения в 1-норме и в 2-норме близки, то более выгодно выбирать не евклидовупрокс-структуру, связанную с 2-нормой, а прокс-структуру, связанную с 1-нормой. Полное обоснование этого утверждения проводится в статье. Предла-гается ускоренный метод спуска по случайному направлению с неевклидовойпрокс-структурой для решения задачи безусловной оптимизации (в дальней-шем подход предполагается расширить на ускоренный безградиентный метод).Получены оценки скорости сходимости метода. Показаны сложности переносаописанного подхода на задачи условной оптимизации.

Mots clés: first-order accelerated methods; convex optimization; linear coupling method; uniform measure concentration on a single Euclidean sphere; non-Euclidean prox-structure

Mots clés: ускоренные методы первого порядка; выпуклая оптимизация; методлинейного каплинга; концентрация равномерной меры на единичной евклидовойсфере; неевклидова прокс-структура

Domaines: Optimisation et contrôle [math.OC]

Evgeniya Vorontsova, Alexander Gasnikov, Eduard Gorbunov. Ускоренный спуск по случайному направлению с неевклидовой прокс-структурой. Automation and Remote Control / Avtomatika i Telemekhanika, 2019, 80 (4), pp.126-143. ⟨10.1134/S0005117919040076⟩. ⟨hal-02321617⟩