Orateur
Description
This talk will showcase new results about the Stochastic Gradient Descent (SGD) algorithm for solving convex and smooth stochastic problems. After introducing the algorithm and its main features (convergence rates vs complexity, notion of interpolation) we will present two new results.
In the first part, we ask ourselves: what are the best possible complexity bounds one can hope for SGD? This question was -up to now- completely open, and we will provide a partial first answer under the form of new bounds which are provably optimal, in a certain sense.
We will not inflict a proof to the audience, but will discuss how we were led to this result with two main tools: a new Lyapunov analysis and the use of computer assistance (namely: the PEP framework).
In a second part, we will show that SGD enjoys "last iterate" complexity, a property which was thought to be a distinctive feature of the SGD+Momentum algorithm.
