ML Hub Seminar | Restarting Accelerated First-Order Methods without Knowing Error Bound Condition Number

Mar 21 2019 02:00 PM - Mar 21 2019 03:00 PM


Many convex optimization problems arising from the context of machine learning and signal processing satisfies the so-called local quadratic growth condition, which can be understood as a generalization of strong convexity. When solving such problems, classical (non-accelerated) gradient and coordinate descent methods automatically have a linear rate of convergence, whereas one needs to know explicitly the strong convexity (or error bound) parameter in order to set accelerated gradient and accelerated coordinate descent methods to have the optimal linear rate of convergence. Setting the algorithm with an incorrect parameter may result in a slower algorithm, sometimes even slower than if we had not tried to set an acceleration scheme. We show that restarting accelerated proximal gradient algorithms at any frequency gives a globally linearly convergent algorithm. Then, as the rate of convergence depends on the match between the frequency and the quadratic error bound, we design a scheme to automatically adapt the frequency of restart from the observed decrease of the norm of the gradient mapping. Restarting accelerated coordinate descent type methods, as well as accelerated stochastic variance reduced methods, also leads to a geometric rate of convergence, under the more restrictive assumption that the objective function is strongly convex. We propose a well-chosen sequence of restarting times to achieve a nearly optimal linear convergence rate, without knowing the actual value of the error bound.


Z. Qu obtained her Ph.D. in 2013 at Centre des Mathematiques Appliquees, Ecole Polytechnique, France. From 2014 to 2015 she was a postdoc in the Department of Mathematics at the University of Edinburgh. Since 2015 she holds a position of Assistant Professor at the University of Hong Kong.

More Information

For more info contact: Professor Panagiotis Kalnis

Date: Thursday 21st Mar 2019

Time: 02:00 PM - 03:00 PM

Location: Building 9 - Hall 1

Refreshments will be served at 13:45