NDLI: Smooth strongly convex interpolation and exact worst-case performance of first-order methods

Content Provider	Springer Nature Link
Author	Hendrickx, Julien M. Glineur, François Taylor, Adrien B.
Copyright Year	2016
Abstract	We show that the exact worst-case performance of fixed-step first-order methods for unconstrained optimization of smooth (possibly strongly) convex functions can be obtained by solving convex programs. Finding the worst-case performance of a black-box first-order method is formulated as an optimization problem over a set of smooth (strongly) convex functions and initial conditions. We develop closed-form necessary and sufficient conditions for smooth (strongly) convex interpolation, which provide a finite representation for those functions. This allows us to reformulate the worst-case performance estimation problem as an equivalent finite dimension-independent semidefinite optimization problem, whose exact solution can be recovered up to numerical precision. Optimal solutions to this performance estimation problem provide both worst-case performance bounds and explicit functions matching them, as our smooth (strongly) convex interpolation procedure is constructive. Our works build on those of Drori and Teboulle (Math Program 145(1–2):451–482, 2014) who introduced and solved relaxations of the performance estimation problem for smooth convex functions. We apply our approach to different fixed-step first-order methods with several performance criteria, including objective function accuracy and gradient norm. We conjecture several numerically supported worst-case bounds on the performance of the fixed-step gradient, fast gradient and optimized gradient methods, both in the smooth convex and the smooth strongly convex cases, and deduce tight estimates of the optimal step size for the gradient method.
Ending Page	345
Page Count	39
Starting Page	307
File Format	PDF
ISSN	00255610
e-ISSN	14364646
Journal	Mathematical Programming
Issue Number	1-2
Volume Number	161
Language	English
Publisher	Springer Berlin Heidelberg
Publisher Date	2016-05-17
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Semidefinite programming Theoretical, Mathematical and Computational Physics First-order methods Convex programming Worst-case analysis Analysis of algorithms and problem complexity Mathematical Methods in Physics Rates of convergence Calculus of Variations and Optimal Control; Optimization Mathematics of Computing Numerical Analysis Smooth convex minimization Nonlinear programming Abstract computational complexity for mathematical programming problems Combinatorics Smooth convex interpolation
Content Type	Text
Resource Type	Article
Subject	Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Optimized first-order methods for smooth convex minimization

Exact Worst-Case Performance of First-Order Methods for Composite Convex Optimization

Performance of first-order methods for smooth convex minimization: a novel approach

Generalizing the Optimized Gradient Method for Smooth Convex Minimization

First-order methods of smooth convex optimization with inexact oracle

Iteration-complexity of first-order augmented Lagrangian methods for convex programming

Iteration-complexity of first-order penalty methods for convex programming

Primal-dual first-order methods with $${\mathcal {O}(1/\epsilon)}$$ iteration-complexity for cone programming

Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methods

Smooth strongly convex interpolation and exact worst-case performance of first-order methods

Similar Documents

Optimized first-order methods for smooth convex minimization

Exact Worst-Case Performance of First-Order Methods for Composite Convex Optimization

Performance of first-order methods for smooth convex minimization: a novel approach

Generalizing the Optimized Gradient Method for Smooth Convex Minimization

First-order methods of smooth convex optimization with inexact oracle

Iteration-complexity of first-order augmented Lagrangian methods for convex programming

Iteration-complexity of first-order penalty methods for convex programming

Primal-dual first-order methods with $${\mathcal {O}(1/\epsilon)}$$ iteration-complexity for cone programming

Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methods

Smooth strongly convex interpolation and exact worst-case performance of first-order methods