Online Learning and Optimization from Continuous to Discrete Time

Tuesday, April 5, 2016 - 11:00am

Event Calendar Category

Other LIDS Events

Speaker Name

Walid Krichene


University of California, Berkeley

Building and Room Number



Many discrete algorithms for convex optimization and online learning can be interpreted as a discretization of a continuous-time process. Perhaps the simplest and oldest example is gradient descent, which is the discretization of the ODE $\dot X = -\nabla f(X)$. Studying the continuous-time process offers many advantages: the analysis is often simple and elegant, it provides insights into the discrete process, and can help streamline the design of new algorithms (by performing the design in the continuous domain then discretizing).

In this talk, I will present two such examples: In the first, I will show how some (stochastic) online learning algorithms can be obtained by discretizing an ODE on the simplex, known as the replicator dynamics. I will review properties of the ODE, then give sufficient conditions for convergence of the discrete process, by relating it to the solution trajectories of the ODE. In the second example, I will show how we can design a family of ODEs for accelerated first-order optimization of smooth convex functions. The continuous-time design relies on an "inverse" Lyapunov argument: we start from an energy function which encodes the constraints of the problem and the desired convergence rate, then design dynamics tailored to that energy function. Then, by carefully discretizing the ODE, we obtain a family of accelerated algorithms with optimal rate of convergence.


Walid Krichene received his Bachelor's degree in 2008, and his Master's degree in Applied Mathematics in 2010, both from the Ecole des Mines Paristech, France. He is currently pursuing his Ph.D. in Electrical Engineering and Computer Sciences at the University of California, Berkeley, advised by Professor Alexandre Bayen. His research focuses on online learning and convex optimization, with applications to cyber-physical systems, in transportation in particular. His previous research includes collaboration with INRIA and the CDC department at Caltech, and a researcher position at Criteo labs where he worked on CTR prediction. Walid has received multiple awards including a Bronze medal at the Pan African Mathematics Olympiads, two Outstanding Graduate Student Instructor awards, and the Leon Chua Award from UC Berkeley EECS.