Acceleration of First-Order Optimization Algorithms via Inertial Dynamics with Hessian Driven Damping
Hedy Attouch (University of Montpellier)
Abstract: In a Hilbert space, for convex optimization, we report on recent advances regarding the acceleration of first-order algorithms. We rely on inertial dynamics with damping driven by the Hessian, and the link between continuous dynamic systems and algorithms obtained by temporal discretization. We first review the classical results, from Polyak's heavy ball with friction method to Nesterov's accelerated gradient method. Then we introduce the damping driven by the Hessian which intervenes in the dynamic in the form $\nabla^2f(x(t))\dot{x}(t)$. By treating this term as the time derivative of $\nabla f(x(t))$, this gives, in discretized form, first-order algorithms. As a fundamental property, this geometric damping makes it possible to attenuate the oscillations. In addition to the fast convergence of the values, the algorithms thus obtained show a rapid convergence towards zero of the gradients. The introduction of time scale factors further accelerates these algorithms. On the basis of a regularization technique using the Moreau envelope, we extend the method to non-smooth convex functions with extended real values. Numerical results for structured optimization problems support our theoretical findings. Finally, we evoke recent development concerning the extension of these results to the case of general monotone inclusions, inertial ADMM algorithms, dry friction, inexact/stochastic case, thus showing the versatility of the method.
This lecture is based on the recent collaborative article: H. Attouch, Z. Chbani, J. Fadili, H. Riahi, First-order optimization algorithms via inertial systems with Hessian driven damping, Math. Program., (2020), doi.org/10.1007/s10107-020-01591-1, preprint available at hal-02193846.
optimization and control
Audience: researchers in the discipline
Comments: The address and password of the zoom room of the seminar are sent by e-mail on the mailinglist of the seminar one day before each talk
One World Optimization seminar
Series comments: Description: Online seminar on optimization and related areas
The address and password of the zoom room of the seminar are sent by e-mail on the mailinglist of the seminar one day before each talk
Organizers: | Sorin-Mihai Grad*, Radu Ioan BoČ›, Shoham Sabach, Mathias Staudigl |
*contact for this listing |