Accelerated directional search with non-Euclidean prox-structure

DOI10.1134/S0005117919040076MaRDI QIDQ2290400zbMATH OpenOpenAlexFDO

Authors Evgeniya A. Vorontsova, Alexander V. Gasnikov, É. A. Gorbunov

Publication date 27 January 2020

Published in Automation and Remote Control (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1710.00162

zbMATH Keywords

convex optimizationfirst-order accelerated methodslinear coupling methodnon-Euclidean prox-structureuniform measure concentration on single euclidean sphere

Mathematics Subject Classification ID

Convex programming (90C25) Derivative-free methods and methods using generalized derivatives (90C56)

Abstract: In the paper we propose an accelerated directional search method with non-euclidian prox-structure. We consider convex unconstraint optimization problem in $mathbb{R}^n$. For simplicity we start from the zero point. We expect in advance that 1-norm of the solution is close enough to its 2-norm. In this case the standard accelerated Nesterov's directional search method can be improved. In the paper we show how to make Nesterov's method $n$-times faster (up to a $logn$-factor) in this case. The basic idea is to use linear coupling, proposed by Allen-Zhu & Orecchia in 2014, and to make Grad-step in 2-norm, but Mirr-step in 1-norm. We show that for constrained optimization problems this approach stable upon an obstacle.

Recommendations

• Accelerated gradient-free optimization methods with a non-Euclidean proximal operator
• Gradient methods for minimizing composite functions
• Random gradient-free minimization of convex functions
• An accelerated directional derivative method for smooth stochastic convex optimization
• Gradient-free proximal methods with inexact oracle for convex stochastic nonsmooth optimization problems on the simplex

Cites work

• Efficiency of coordinate descent methods on huge-scale optimization problems
• Gradient-free proximal methods with inexact oracle for convex stochastic nonsmooth optimization problems on the simplex
• Gradient-free two-point methods for solving stochastic nonsmooth convex optimization problems with small non-random noises
• scientific article; zbMATH DE number 3790207 (Why is no real title available?)
• scientific article; zbMATH DE number 6982909 (Why is no real title available?)
• Katyusha: the first direct acceleration of stochastic gradient methods
• Linear coupling: an ultimate unification of gradient and mirror descent
• On lower complexity bounds for large-scale smooth convex optimization
• On the upper bound for the expectation of the norm of a vector uniformly distributed on the sphere and the phenomenon of concentration of uniform measure on the sphere
• Random gradient-free minimization of convex functions
• Stochastic online optimization. Single-point and multi-point non-linear multi-armed bandits. Convex and strongly-convex case
• Universal method for stochastic composite optimization problems

Cited in

(5)

• On the upper bound for the expectation of the norm of a vector uniformly distributed on the sphere and the phenomenon of concentration of uniform measure on the sphere
• Accelerated gradient-free optimization methods with a non-Euclidean proximal operator
• A hybrid directional step method for minimum performance target point search
• ACDS
• First-order methods for convex optimization

Describes a project that uses

Uses Software

• DiffSharp
• GitHub

This page was built for publication: Accelerated directional search with non-Euclidean prox-structure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2290400)