An optimal first order method based on optimal quadratic averaging

DOI10.1137/16M1072528MaRDI QIDQ4603040zbMATH OpenOpenAlexFDO

Authors Maryam Fazel, Scott Roy, D. Drusvyatskiy

Publication date 14 February 2018

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

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

zbMATH Keywords

accelerated gradient methodconvergenceconvex quadraticellipsoid methodfirst-order methodgeometric descent algorithmstrong convexity

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25)

Abstract: In a recent paper, Bubeck, Lee, and Singh introduced a new first order method for minimizing smooth strongly convex functions. Their geometric descent algorithm, largely inspired by the ellipsoid method, enjoys the optimal linear rate of convergence. We show that the same iterate sequence is generated by a scheme that in each iteration computes an optimal average of quadratic lower-models of the function. Indeed, the minimum of the averaged quadratic approaches the true minimum at an optimal rate. This intuitive viewpoint reveals clear connections to the original fast-gradient methods and cutting plane ideas, and leads to limited-memory extensions with improved performance.

Recommendations

• Optimized first-order methods for smooth convex minimization
• Optimizing first-order methods for smooth convex minimization of gradient Q-linearly convergence
• An optimal gradient method for smooth strongly convex minimization
• An acceleration procedure for optimal first-order methods
• On the convergence analysis of the optimized gradient method

Cites work

• Analysis and design of optimization algorithms via integral quadratic constraints
• Fast convex optimization via inertial dynamics with Hessian driven damping
• scientific article; zbMATH DE number 5060482 (Why is no real title available?)
• Introductory lectures on convex optimization. A basic course.
• Linear coupling: an ultimate unification of gradient and mirror descent
• On the convexity of a class of quadratic mappings and its application to the problem of finding the smallest ball enclosing a given intersection of balls
• The Cutting-Plane Method for Solving Convex Programs

Cited in

(17)

• The condition number of a function relative to a set
• Fast and safe: accelerated gradient methods with optimality certificates and underestimate sequences
• Generalized Nesterov's accelerated proximal gradient algorithms with convergence rate of order o(1/k^2)
• Understanding the acceleration phenomenon via high-resolution differential equations
• Efficient first-order methods for convex minimization: a constructive approach
• Perturbed Fenchel duality and first-order methods
• Convergence rates of proximal gradient methods via the convex conjugate
• The approximate duality gap technique: a unified theory of first-order methods
• Gradient methods with memory
• Exact gradient methods with memory
• Potential Function-Based Framework for Minimizing Gradients in Convex and Min-Max Optimization
• The common-directions method for regularized empirical risk minimization
• An acceleration procedure for optimal first-order methods
• Generalized momentum-based methods: a Hamiltonian perspective
• No-regret dynamics in the Fenchel game: a unified framework for algorithmic convex optimization
• Nesterov's acceleration at the limit: first-order schemes
• A boosted proximal point method for difference of convex functions in multiobjective optimization and the growth of multiproduct firms

Describes a project that uses

Uses Software

• LIBSVM

This page was built for publication: An optimal first order method based on optimal quadratic averaging

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