Revisiting the Role of Euler Numerical Integration on Acceleration and Stability in Convex Optimization
This work provides a counterexample that questions a foundational framework in optimization theory, potentially impacting researchers studying accelerated methods.
The authors challenged the assumption that numerical integrator quality (e.g., symplecticity) is linked to acceleration in optimization by proposing a novel ODE where both explicit and semi-implicit Euler discretizations yield accelerated algorithms for convex programming, showing these properties do not necessarily relate to acceleration.
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.