Fast and safe: accelerated gradient methods with optimality certificates and underestimate sequences

DOI10.1007/S10589-021-00269-4MaRDI QIDQ2044479zbMATH OpenOpenAlexFDO

Authors Majid Jahani, Naga Venkata C. Gudapati, Chenxin Ma, Rachael Tappenden, M. Takáč

Publication date 9 August 2021

Published in Computational Optimization and Applications (Search for Journal in Brave)

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

zbMATH Keywords

accelerated algorithmscomposite minimizationestimate sequencelower boundsquadratic averagingsmooth minimizationstrongly convexunderestimate sequence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Convex programming (90C25) Minimax problems in mathematical programming (90C47)

Abstract: In this work we introduce the concept of an Underestimate Sequence (UES), which is motivated by Nesterov's estimate sequence. Our definition of a UES utilizes three sequences, one of which is a lower bound (or under-estimator) of the objective function. The question of how to construct an appropriate sequence of lower bounds is addressed, and we present lower bounds for strongly convex smooth functions and for strongly convex composite functions, which adhere to the UES framework. Further, we propose several first order methods for minimizing strongly convex functions in both the smooth and composite cases. The algorithms, based on efficiently updating lower bounds on the objective functions, have natural stopping conditions that provide the user with a certificate of optimality. Convergence of all algorithms is guaranteed through the UES framework, and we show that all presented algorithms converge linearly, with the accelerated variants enjoying the optimal linear rate of convergence.

Recommendations

• An optimal gradient method for smooth strongly convex minimization
• On the convergence analysis of the optimized gradient method
• Gradient methods for minimizing composite functions
• Accelerated first-order methods for large-scale convex optimization: nearly optimal complexity under strong convexity
• Fast gradient methods for uniformly convex and weakly smooth problems

Cites work

• A flexible coordinate descent method
• A Stochastic Approximation Method
• Accelerated, parallel, and proximal coordinate descent
• Accelerating the cubic regularization of Newton's method on convex problems
• Adaptive restart for accelerated gradient schemes
• An accelerated communication-efficient primal-dual optimization framework for structured machine learning
• An optimal first order method based on optimal quadratic averaging
• Efficiency of coordinate descent methods on huge-scale optimization problems
• Gradient methods for minimizing composite functions
• scientific article; zbMATH DE number 3850830 (Why is no real title available?)
• Inexact coordinate descent: complexity and preconditioning
• Introductory lectures on convex optimization. A basic course.
• Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
• Minimizing finite sums with the stochastic average gradient
• On the complexity analysis of randomized block-coordinate descent methods
• Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: A Generic Algorithmic Framework
• Smooth minimization of non-smooth functions
• The approximate duality gap technique: a unified theory of first-order methods

Cited in

(1)

• New analysis of linear convergence of gradient-type methods via unifying error bound conditions

Describes a project that uses

Uses Software

• LIBSVM
• Adam

This page was built for publication: Fast and safe: accelerated gradient methods with optimality certificates and underestimate sequences

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