AI & ML
Exact (Non-)Accelerations of Heavy-Ball Discretizations
arXiv cs.NA0 views
arXiv:2611.13584v1 Announce Type: cross Abstract: Momentum methods with the same slow dynamics can have different worst-case rates on smooth strongly convex functions. We identify a half-step phase barrier in the gradient query that governs this difference. For momentum with extrapolation $\tau_\kappa\to\tau$, $\beta=1-\theta/\sqrt\kappa+o(\kappa^{-1/2})$ and $hL\to y$, where $\kappa=L/\mu$ and $\theta,y>0$, the exact uniform distance factor is $1-c/\sqrt\kappa+o(\kappa^{-1/2})$, with $c=\min\{\theta/3,c_Q(\theta,y)\}$, when $\tau>1/2$ and $y(1+2\tau)<4$; $c_Q$ is the slowest quadratic decay exponent. Quadratically accelerated families with $\limsup\tau_\kappa<1/2$ have divergent trajectories on the full function class. Upper bounds use finite-lag certificates: nonnegative combinations of inequalities for values and gradients at finitely separated query points, together with comparisons to the minimizer. For any prescribed accuracy, spiral mixtures or quadratic trajectories of one finite-dimensional objective give matching lower bounds at all iteration horizons. We resolve the parameter layer near $\tau=1/2$ and classify all tunings of this family attaining the optimal leading constant 1. The flow also bounds the leading constant of every second-order stationary linear family with the same slow parameters $(\theta,y)$ and fixed finite memory.
Source:https://arxiv.org/abs/2611.13584PreviousParallel Broyden Methods for Efficiently Evaluating Nonlinear State Space ModelsNextMultifidelity Operator Inference for Non-intrusive Model Reduction under Data Scarcity
Related posts
How Many Demonstrations Does a VLA Need? On the Sample Efficiency of VLA Finetuning
0arXiv cs.RO
Altitude-Adaptive UAV-to-Map Image Matching for Aerial Geo-Localization
0arXiv cs.RO
OASIS: Optimization-Aware Subgoal Inference with Safety Constraints for Autonomous Mobile Robot Navigation
0arXiv cs.RO
Fade to... Red? Scheduling Coloured Noise Exploration Supports Efficient Robot Learning with Reduced Movement Jerk
0arXiv cs.RO
DexForesight: Grounding Dexterous Policies with Implicit Spatial Foresight
0arXiv cs.RO
Control-Aware Command Generation for Asynchronous Control and Action Inference with Vision-Based Policies towards Fast Execution
0arXiv cs.RO