Revisiting the Role of Euler Numerical Integration on Acceleration and Stability in Convex Optimization

Peiyuan Zhang (1) , Antonio Orvieto (1) , Hadi Daneshmand (2) , Thomas Hofmann (1) , Roy Smith (1)

1 ETH Zürich - Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology [Zürich]
2 SIERRA - Statistical Machine Learning and Parsimony

Viewing optimization methods as numerical integrators for ordinary differential equations (ODEs) provides a thought-provoking modern framework for studying accelerated first-order optimizers. In this literature, acceleration is often supposed to be linked to the quality of the integrator (accuracy, energy preservation, symplecticity). In this work, we propose a novel ordinary differential equation that questions this connection: both the explicit and the semi-implicit (a.k.a symplectic) Euler discretizations on this ODE lead to an accelerated algorithm for convex programming. Although semi-implicit methods are well-known in numerical analysis to enjoy many desirable features for the integration of physical systems, our findings show that these properties do not necessarily relate to acceleration.

Domaines: Informatique [cs]; Statistiques [stat]; Apprentissage [cs.LG]; Machine Learning [stat.ML]

Peiyuan Zhang, Antonio Orvieto, Hadi Daneshmand, Thomas Hofmann, Roy Smith. Revisiting the Role of Euler Numerical Integration on Acceleration and Stability in Convex Optimization. AISTATS 2021 - 24th International Conference on Artifi-cial Intelligence and Statistics, Apr 2021, Virtual, Unknown Region. ⟨hal-03454377⟩