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

El Mahdi Chayti; Mohamad Fakhouri

math.OCFeb 6, 2026

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

Authors: El Mahdi Chayti, Mohamad Fakhouri

Organizations: Machine Learning and Optimization Laboratory (MLO) EPFL, Switzerland

Abstract

Second-order momentum corrects the lag of momentum behind the current gradient with a Hessian-vector product (HVP), but existing corrections need either a Lipschitz Hessian or extra forward and backward passes at an auxiliary point. We show that randomizing the step length removes this trade-off: if the step is exponentially distributed with mean $η$ , a Stein-type identity makes $η$ times one HVP at the new iterate an estimate of the gradient change that is unbiased in expectation over the step, and this HVP shares its forward pass with the next gradient. The resulting method, RanSOM-E, works with normalized, sign, and Muon-type steps, and a Beta-distributed variant, RanSOM-B, keeps Frank-Wolfe iterates feasible. For objectives with Lipschitz gradient and heavy-tailed gradient and Hessian noise with tail indices $p, q \in (1,2]$ , RanSOM-E attains the optimal oracle-complexity exponents for every pair $(p,q)$ , including $p \neq q$ , without a Lipschitz Hessian or clipping ( $\mathcal{O}(\varepsilon^{-3})$ for $p = q = 2$ ). On CIFAR-10 with ResNet-20, we detect no accuracy difference from existing second-order momentum methods, and its mean update time is lower than that of the auxiliary-point method.

Figures & tables

Panel of Figure 1 — Figure 1: The momentum $m_{t}$ averages gradients from earlier iterates and approximates $\nabla f(x_{t})$ . After the step to $x_{t+1}$ , it differs from the new gradient by the change ( 1 ), which the correction $\delta_{t+1}$ estimates.

Method	Correction $\delta_{t+1}$	Evaluated at	Smoothness beyond $\nabla f$ Lipschitz	AD passes
STORM	$\nabla f_{\xi}(x_{t+1})-\nabla f_{\xi}(x_{t})$	$x_{t+1}$ and $x_{t}$	mean-squared smoothness of $f_{\xi}$	$2F+2B_{g}$
SOM	$\eta_{t}\,\nabla^{2}f_{\xi}(x_{t+1})\,d_{t}$	$x_{t+1}$	Lipschitz $\nabla^{2}f$	$F+B_{g}+B_{h}$
SOM-Unif	$\eta_{t}\,\nabla^{2}f_{\xi}(\hat{x}_{t})\,d_{t}$ , $\hat{x}_{t}\in[x_{t},x_{t+1}]$	$\hat{x}_{t}$	none	$2F+2B_{g}+B_{h}$
RanSOM-E	$\eta_{t}\,\nabla^{2}f_{\xi}(x_{t+1})\,d_{t}$	$x_{t+1}$	none	$F+B_{g}+B_{h}$

Table 1: Estimators of the gradient change ( 1 ) used in ( 2 ). For SOM and SOM-Unif the step is deterministic,

x_{t+1}-x_{t}=\eta_{t}d_{t}

; for RanSOM-E it is

s_{t}d_{t}

with

s_{t}\sim\mathrm{Exp}

of mean

\eta_{t}

. The published analyses of the four methods give

\mathcal{O}(\varepsilon^{-3})

under bounded variance and their respective assumptions. The last column counts automatic-differentiation passes per step for the gradient and the correction in a reverse-over-reverse implementation:

F

is a forward pass,

B_{g}

a backward pass that builds the gradient graph, and

B_{h}

the backward pass through that graph that returns the HVP ( Pearlmutter, 1994 ) . SOM-Unif needs a second forward and gradient pass at

\hat{x}_{t}

. Measured times are in Figure 4 and Table 9 .

Figure 2: CIFAR-10 train accuracy (left) and test accuracy (right) for ResNet-20. Curves show the mean over ten seeds; shading shows one sample standard deviation. Colors identify algorithm families; Muon-geometry curves are dashed, normalized and reference curves are solid. Insets show epochs 80–100. RanSOM-E labels are bold. Settings are selected on validation data; Table 2 reports epoch-100 results.

Method	Train $\uparrow$	Test $\uparrow$
Muon reference	$\mathbf{99.87\pm 0.03}$	$\mathbf{91.09\pm 0.21}$
SOM (Muon)	$99.82\pm 0.02$	$90.74\pm 0.33$
AdamW	$99.58\pm 0.04$	$90.71\pm 0.17$
RanSOM-E (Muon)	$99.79\pm 0.01$	$90.69\pm 0.17$
SGD-Nesterov	$99.54\pm 0.03$	$90.66\pm 0.22$
SOM-Unif (Muon)	$99.76\pm 0.03$	$90.44\pm 0.26$

Table 2: CIFAR-10 accuracy (%) with ResNet-20 at epoch 100: mean

\pm

sample standard deviation over ten seeds. Bold values mark the highest mean in each column. Both columns evaluate the final model on fixed normalized images without crop or flip. Training curves use augmented batches during updates.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Method	Selected settings
Muon reference	$\mathrm{lr}=0.02$ , $\mathrm{wd}=0.01$
SOM (Muon)	$\gamma=0.01$ , $\beta=0.1$
AdamW	$\mathrm{lr}=0.003$ , $\mathrm{wd}=0.05$
RanSOM-E (Muon)	$\gamma=0.01$ , $\beta=0.1$
SGD-Nesterov	$\mathrm{lr}=0.03$ , $\mathrm{wd}=0.0005$
SOM-Unif (Muon)	$\gamma=0.01$ , $\beta=0.1$

Appendix

Table 3: Selected CIFAR-10 settings, held fixed across the ten final seeds. Corrections are applied without additional scaling.

Method	Train cross-entropy	Test cross-entropy
Muon reference	$\mathbf{0.0045\pm 0.0005}$	$0.4887\pm 0.0102$
SOM (Muon)	$0.0061\pm 0.0004$	$0.5616\pm 0.0181$
AdamW	$0.0147\pm 0.0007$	$0.4111\pm 0.0074$
RanSOM-E (Muon)	$0.0069\pm 0.0003$	$0.5490\pm 0.0151$
SGD-Nesterov	$0.0192\pm 0.0006$	$\mathbf{0.3615\pm 0.0092}$
SOM-Unif (Muon)	$0.0078\pm 0.0006$	$0.5615\pm 0.0169$

Appendix

Table 4: CIFAR-10 cross-entropy at epoch 100, mean

\pm

sample standard deviation over ten seeds. Bold values mark the lowest mean in each column.

Figure 3: CIFAR-10 train cross-entropy (left) and test cross-entropy (right). Curves show ten-seed means, with one sample standard deviation as shading. Both panels use the same linear loss scale. Insets show epochs 80–100. Colors and line styles match Figure 2 . Training metrics use augmented batches during updates; test metrics use evaluation after each epoch.

Figure 4: Average CUDA-event time per update on CIFAR-10, in milliseconds. Each seed averages all updates over 100 epochs; bars and error bars show the mean and one sample standard deviation across ten seeds. Data loading and evaluation are excluded.

Geometry	Reference	Mean $\Delta$ (pp)	95% interval (pp)
Normalized	SOM	$+0.181$	$[-0.058,+0.420]$
Normalized	SOM-Unif	$+0.216$	$[-0.091,+0.523]$
Muon	SOM	$-0.057$	$[-0.275,+0.161]$
Muon	SOM-Unif	$+0.243$	$[-0.001,+0.487]$

Appendix

Table 5: Paired final test accuracy differences for RanSOM-E versus SOM and SOM-Unif over ten seeds. Values are in percentage points. Positive differences favor RanSOM-E. Intervals are 95% Student-

t

intervals with nine degrees of freedom.

Figure 5: Full MovieLens log-cosh replication. Solid curves show means and bands show sample SD over ten fresh paired seeds. The panels show training and validation losses.

Method	Test log-cosh
Polyak	$\mathbf{0.371480\pm 0.000640}$
SOM	$0.372084\pm 0.000367$
SOM-Unif	$0.372117\pm 0.000363$
RanSOM-B	$0.372287\pm 0.000369$

Appendix

Table 6: Constrained MovieLens with log-cosh loss: final test loss, mean

\pm

sample standard deviation over ten paired seeds. Lower is better; bold marks the lowest mean.

Method	Train log-cosh	Validation log-cosh
Polyak	$0.239764\pm 0.000313$	$0.363331\pm 0.000507$
SOM	$0.240586\pm 0.000197$	$0.363965\pm 0.000477$
SOM-Unif	$0.240613\pm 0.000240$	$0.364014\pm 0.000475$
RanSOM-B	$0.240795\pm 0.000328$	$0.364172\pm 0.000251$

Appendix

Table 7: Epoch-100 training and validation log-cosh, mean

\pm

sample SD over ten fresh paired seeds.

Comparator	Metric	Difference	95% interval
SOM	Log-cosh	2.027	$[-0.453,4.508]$
SOM-Unif	Log-cosh	1.691	$[-0.236,3.618]$

Appendix

Table 8: Paired final test differences, RanSOM-B minus comparator. All numbers use units of

10^{-4}

. Positive values favor the comparator. Intervals use Student-

t

with nine degrees of freedom and ten pairs. They are exploratory and have no multiple-comparison adjustment.

Method	Update (ms)	Oracle (ms)	Step SD (ms)
Polyak	$69.77\pm 25.53$	$50.70\pm 19.05$	28.73
SOM	$73.44\pm 26.94$	$52.55\pm 19.83$	30.76
SOM-Unif	$81.39\pm 29.64$	$52.54\pm 19.84$	33.51
RanSOM-B	$70.29\pm 26.01$	$52.45\pm 19.79$	29.25

Appendix

Table 9: MovieLens log-cosh update and oracle times in milliseconds. Update and oracle columns give means

\pm

sample SD across ten seeds. Step SD uses the pooled individual update duration moments. The oracle cost is part of the update.

Explore similar work

Randomized Momentum Transport with Cheap Predictors
Oct 9, 2026El Mahdi Chayti, Martin JaggiMomentum Methods Stochastic Optimization Convergence
Machine Learning and Optimization Laboratory (MLO), EPFL
Second-Moment Memory in Coordinatewise Adam
Aug 16, 2026Jeonseong KimAdaptive Gradient Methods Stochastic Optimization Convergence
Convergence rates for the RMSprop optimizer with full control of the hyperparameters
Aug 31, 2026Steffen Dereich, Arnulf JentzenStochastic Approximation Stochastic Optimization Convergence

Oct 9, 2026, cs.LGJ/K move · Enter open · S save

Randomized Momentum Transport with Cheap Predictors

El Mahdi Chayti, Martin Jaggi

Machine Learning and Optimization Laboratory (MLO), EPFL

Momentum Methods Stochastic Optimization Convergence Gradient Descent Dynamics Variance Reduction

Open paper AskPDF arXiv

Momentum methods such as STORM and second-order momentum track the gradient by adding a transport correction to momentum, at the cost of an extra oracle call per iteration. We introduce randomized momentum transport, which evaluates the correction with probability

q

and otherwise uses a cheap prediction, with importance weighting that preserves the conditional mean and adds

(q^{-1}-1)

times the prediction loss to the variance. Under transport-bias, second-moment, and residual-control assumptions, linear minimization oracle (LMO) updates, including normalized, sign, and exact spectral (Muon) directions, retain an

O(T^{-1/3})

stationarity bound for each fixed

q>0

with a single-gradient initialization. For unnormalized STORM, some

q<1

lowers the leading coefficient of our sufficient gradient budget if and only if the gradient-difference noise modulus exceeds the smoothness constant, by at most about

10\%

. An online diagonal predictor admits a regret-to-convergence guarantee. At approximately equal oracle cost, querying a quarter of the corrections lowers the final training loss by

18

43\%

on MNIST1D and raises the test accuracy of Hessian-vector transport on CIFAR-10 by

1.5

points.

Abstract

Explore similar work

Randomized Momentum Transport with Cheap Predictors

Second-Moment Memory in Coordinatewise Adam

Convergence rates for the RMSprop optimizer with full control of the hyperparameters