Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Computational Geometric Mechanics Research Seminar

Valentin Duruisseaux

UCSD

Accelerated Optimization via Geometric Numerical Integration

Abstract:

Efficient optimization has become one of the major concerns in machine learning, and there has been a lot of focus on first-order optimization algorithms because of their low cost per iteration. In 1983, Nesterov's Accelerated Gradient method (NAG) was shown to converge in $\mathcal{O}(1/k^2)$ to the minimum of the convex objective function $f$, improving on the $\mathcal{O}(1/k)$ convergence rate exhibited by the standard gradient descent methods, which is the phenomenon referred to as acceleration. It was shown that NAG limits to a second order ODE, as the time-step goes to 0, and that the objective function $f(x(t))$ converges to its optimal value at a rate of $\mathcal{O}(1/t^2)$ along the trajectories of this ODE. In this talk, we will discuss how the convergence of $f(x(t))$ can be accelerated in continuous time to an arbitrary convergence rate $\mathcal{O}(1/t^p)$ in normed spaces, by considering flow maps generated by a family of time-dependent Bregman Lagrangian and Hamiltonian systems which is closed under time rescaling. We will then discuss how this variational framework can be exploited together with the time-invariance property of the family of Bregman dynamics using adaptive geometric integrators to design efficient explicit algorithms for accelerated optimization. We will then discuss how these results and computational methods can be generalized from normed spaces to Riemannian manifolds. Finally, we will discuss some practical considerations which can be used to improve the performance of the algorithms. 

October 25, 2022

9:30 AM

APM 6402

****************************