Revisiting the Role of Euler Numerical Integration on Acceleration and Stability in Convex Optimization
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Numerical IntegrationSimilar Papers 제목 키워드 기반
Sharpen Your Flow: Sharpness-Aware Sampling for Flow Matching
Flow matching models generate samples by numerically integrating a learned velocity field, with each integration step requiring a neural network evaluation. Fast generation therefore requires using a small fixed evaluati…
On the Role of Strain and Vorticity in Numerical Integration Error for Flow Matching
Flow matching generates data by integrating a learned velocity field, where the number of integration steps (NFE) directly determines inference cost. We analyze which properties of the velocity field govern integration e…
A Dynamical Systems Perspective on Nesterov Acceleration
We present a dynamical system framework for understanding Nesterov's accelerated gradient method. In contrast to earlier work, our derivation does not rely on a vanishing step size argument. We show that Nesterov acceler…
Continuous and Discrete-time Accelerated Stochastic Mirror Descent for Strongly Convex Functions
We provide a second-order stochastic differential equation (SDE), which characterizes the continuous-time dynamics of accelerated stochastic mirror descent (ASMD) for strongly convex functions. This SDE plays a cent…
Stochastic OptimizationA Contraction Theory Approach to Optimization Algorithms from Acceleration Flows
Much recent interest has focused on the design of optimization algorithms from the discretization of an associated optimization flow, i.e., a system of differential equations (ODEs) whose trajectories solve an associated…