Optimal Affine-Invariant Smooth Minimization Algorithms

DOI10.1137/17M1116842MaRDI QIDQ5376450zbMATH OpenFDO

Authors Alexandre d'Aspremont, Cristóbal Guzmán, Martin Jaggi

Publication date 18 September 2018

Published in SIAM Journal on Optimization (Search for Journal in Brave)

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

zbMATH Keywords

affine invarianceconvex optimizationcomplexity theoryoptimal methods

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60)

Abstract: We formulate an affine invariant implementation of the accelerated first-order algorithm in Nesterov (1983). Its complexity bound is proportional to an affine invariant regularity constant defined with respect to the Minkowski gauge of the feasible set. We extend these results to more general problems, optimizing H"older smooth functions using $p$-uniformly convex prox terms, and derive an algorithm whose complexity better fits the geometry of the feasible set and adapts to both the best H"older smoothness parameter and the best gradient Lipschitz constant. Finally, we detail matching complexity lower bounds when the feasible set is an $el{l}_p$ ball. In this setting, our upper bounds on iteration complexity for the algorithm in Nesterov (1983) are thus optimal in terms of target precision, smoothness and problem dimension.

Recommendations

• Optimal methods of smooth convex minimization
• Smooth Optimization Methods for Minimax Problems
• An optimal gradient method for smooth strongly convex minimization
• Minimization methods for smooth nonconvex functions
• Affine-invariant contracting-point methods for convex optimization
• Optimized first-order methods for smooth convex minimization
• Smoothing methods for nonsmooth, nonconvex minimization
• Min-Max-Min Optimization with Smooth and Strongly Convex Objectives
• scientific article; zbMATH DE number 4079168
• Generalizing the optimized gradient method for smooth convex minimization

Cites work

• scientific article; zbMATH DE number 439380 (Why is no real title available?)
• scientific article; zbMATH DE number 3850830 (Why is no real title available?)
• scientific article; zbMATH DE number 3790207 (Why is no real title available?)
• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions
• First-order methods of smooth convex optimization with inexact oracle
• Introductory lectures on convex optimization. A basic course.
• Linear coupling: an ultimate unification of gradient and mirror descent
• Martingales with values in uniformly convex spaces
• On lower complexity bounds for large-scale smooth convex optimization
• Optimal methods of smooth convex minimization
• Robust Stochastic Approximation Approach to Stochastic Programming
• Sharp uniform convexity and smoothness inequalities for trace norms
• Smooth minimization of non-smooth functions
• Universal gradient methods for convex optimization problems

Cited in

(7)

• Optimal Algorithms for Stochastic Complementary Composite Minimization
• On lower complexity bounds for large-scale smooth convex optimization
• Mirror descent algorithms with nearly dimension-independent rates for differentially-private stochastic saddle-point problems
• Complementary composite minimization, small gradients in general norms, and applications
• scientific article; zbMATH DE number 7626799 (Why is no real title available?)
• Affine-invariant contracting-point methods for convex optimization
• Lower bounds for parallel and randomized convex optimization

Describes a project that uses

Uses Software

• NESUN
• CVX

This page was built for publication: Optimal Affine-Invariant Smooth Minimization Algorithms

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