RanSOM: Second-Order Momentum with Randomized Scaling for Constrained and Unconstrained Optimization

arXiv:2602.06824v2 Announce Type: replace-cross Abstract: Momentum methods, such as Polyak's Heavy Ball, are the standard for training deep networks but suffer from curvature-induced bias in stochastic settings, limiting convergence to suboptimal O(epsilon^{-4}) rates. Existing corrections typically require expensive auxiliary sampling or restrictive smoothness assumptions. We propose extbf{RanSOM}, a unified framework that eliminates this bias by replacing deterministic step sizes with randomized steps drawn from distributions with mean eta_t. This modification allows us to leverage Stein-type identities to compute an exact, unbiased estimate of the momentum bias using a single Hessian-vector product computed jointly with the gradient, avoiding auxiliary queries. We instantiate this framework in two algorithms: extbf{RanSOM-E} for unconstrained optimization (using exponentially distributed steps) and extbf{RanSOM-B} for constrained optimization (using beta-distributed steps to strictly preserve feasibility). Theoretical analysis confirms that RanSOM recovers the optimal O(epsilon^{-3}) convergence rate under standard bounded noise, and achieves optimal rates for heavy-tailed noise settings (p in (1, 2]).

Source: arXiv cs.LG | 2026-05-18