Timezone: »

 
Poster
Gradient Descent Is Optimal Under Lower Restricted Secant Inequality And Upper Error Bound
Charles Guille-Escuret · Adam Ibrahim · Baptiste Goujaud · Ioannis Mitliagkas

Wed Nov 30 02:00 PM -- 04:00 PM (PST) @ Hall J #312
in Poster Session 4 »

The study of first-order optimization is sensitive to the assumptions made on the objective functions.These assumptions induce complexity classes which play a key role in worst-case analysis, includingthe fundamental concept of algorithm optimality. Recent work argues that strong convexity andsmoothness—popular assumptions in literature—lead to a pathological definition of the conditionnumber. Motivated by this result, we focus on the class of functionssatisfying a lower restricted secant inequality and an upper error bound. On top of being robust tothe aforementioned pathological behavior and including some non-convex functions, this pair ofconditions displays interesting geometrical properties. In particular, the necessary and sufficientconditions to interpolate a set of points and their gradients within the class can be separated intosimple conditions on each sampled gradient. This allows the performance estimation problem (PEP) to be solved analytically, leading to a lower boundon the convergence rate that proves gradient descent to be exactly optimal on this class of functionsamong all first-order algorithms.

Keywords: Restricted Secant Inequality · Deterministic · Error Bounds · Gradient Descent · Non-Convex · First-Order Optimization
[ Paper]  [ Poster]  [ OpenReview] 

Author Information

Charles Guille-Escuret (Université de Montréal, Mila)
Adam Ibrahim (Mila)
Baptiste Goujaud (Ecole Polytechnique)
Ioannis Mitliagkas (University of Montreal)

More from the Same Authors