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

convergencestrong convexityfirst-order methodellipsoid methodconvex quadraticaccelerated gradient methodgeometric descent algorithm

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

• scientific article; zbMATH DE number 5060482 (Why is no real title available?)
• Analysis and design of optimization algorithms via integral quadratic constraints
• Fast convex optimization via inertial dynamics with Hessian driven damping
• 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

(15)

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

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)