An Optimal First Order Method Based on Optimal Quadratic Averaging

DOI10.1137/16M1072528zbMath1382.65169arXiv1604.06543OpenAlexW2964093568MaRDI QIDQ4603040

Maryam Fazel, Scott Roy, Dmitriy 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

convergencefirst-order methodstrong convexityellipsoid methodconvex quadraticaccelerated gradient methodgeometric descent algorithm

Mathematics Subject Classification ID

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

Related Items (13)

Gradient methods with memory ⋮ Exact gradient methods with memory ⋮ Potential Function-Based Framework for Minimizing Gradients in Convex and Min-Max Optimization ⋮ No-regret dynamics in the Fenchel game: a unified framework for algorithmic convex optimization ⋮ Perturbed Fenchel duality and first-order methods ⋮ Efficient first-order methods for convex minimization: a constructive approach ⋮ Convergence Rates of Proximal Gradient Methods via the Convex Conjugate ⋮ The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods ⋮ 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 ⋮ Generalized Momentum-Based Methods: A Hamiltonian Perspective

Uses Software

• LIBSVM

Cites Work

• Unnamed Item
• Fast convex optimization via inertial dynamics with Hessian driven damping
• 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
• Introductory lectures on convex optimization. A basic course.
• The Cutting-Plane Method for Solving Convex Programs
• Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints
• Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent

This page was built for publication: An Optimal First Order Method Based on Optimal Quadratic Averaging