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

arXiv:2602.06824 · math.OC, cs.LG · Submitted 2026-02-06 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "RanSOM: Second-Order Momentum with Randomized Scaling for Constrained and Unconstrained Optimization".

Jane: The gist: RanSOM recovers optimal convergence rates for non-convex stochastic optimization by replacing deterministic step sizes with randomized steps drawn from distributions with mean ηt,

Tom: First, who's behind it and why it matters.

Title and authors: Tom: So we're looking at RanSOM today, which is this paper about second-order momentum with randomized scaling for constrained and unconstrained optimization. It addresses that big problem where standard momentum methods get biased because of the curvature in non-convex settings.

Jane: Exactly. They show that these traditional methods limit convergence to a suboptimal O(epsilon minus four) rate, and they point out that fixing this bias usually means you either need expensive auxiliary sampling or you have to assume strong smoothness conditions on the function or the Hessian itself.

Lu: What’s really interesting is how they replace those fixed step sizes with randomized steps drawn from distributions with mean eta sub t. That randomization lets them use Stein-type identities to get an exact, unbiased estimate of that momentum bias using just one Hessian-vector product computed jointly with the gradient, which avoids those extra queries.

Meng: So it’s trying to fix the bias without adding new computational overhead or demanding heavy mathematical assumptions on the function's smoothness. That sounds like a big win for practical AI training setups where you can't always guarantee perfect smoothness or cheap auxiliary computations.

Lalam: It really feels like they are building a framework that is robust across different optimization scenarios, whether you’re in an unconstrained setting or dealing with constraints. They introduce two specific algorithms, RanSOM-E for unconstrained optimization and RanSOM-B for constrained optimization, using exponentially distributed steps and beta-distributed steps respectively to keep things feasible.

Tom: Right, so the paper is proposing this unified framework called RanSOM to eliminate that lag in the estimator between your historic momentum vector and the current gradient. They show that by treating step size st as a random variable where Est equals eta sub t, you can use Stein’s Lemma to get an unbiased estimate of the curvature bias using just one Hessian-vector product at the next iterate.

Jane: The core mechanism involves two Stein-type identities, one for unconstrained optimization and one for constrained optimization. For unconstrained problems, they use an Exponential Identity where scaling the Hessian-vector product at xt plus one by eta sub t yields an unbiased estimator of the gradient difference.

Lu: And for constrained optimization, they employ a Beta Identity where the Hessian-vector product needs to be reweighted by that term (one minus s over k) to make it unbiased. This shows how they adapt the correction mechanism based on whether you are dealing with a standard unconstrained problem or one with constraints.

Meng: I see how that relates to their efficiency claim too. They avoid auxiliary queries, which is usually a headache in these kinds of corrections, and they only need one Hessian-vector product at xt plus one, which is already computed for the next gradient step. That sounds much more practical for large scale systems.

Lalam: It’s also important to note what they say about their performance guarantees under generalized assumptions. They confirm that RanSOM achieves the optimal O(epsilon minus three) sample complexity under standard bounded variance assumptions, and they extend this robustness even when you move into heavy-tailed gradient noise, specifically for p in (one two] <ref:2602.06824#pg2>.

Title and authors: Tom: That extension is significant because it means you don't necessarily need the Hessian to be Lipschitz continuous to get these good convergence rates. The analysis relies on pointwise L0 smoothness and Affine Heavy–Tailed Noise assumptions, which capture a lot of the complexity we see in deep learning dynamics.

Jane: But what about real-world training? The paper tests RanSOM-E variants on benchmarks like MNIST1D, where RanSOM-E with Muon steps outperformed STORM by achieving a peak accuracy of ninety-one point nine zero percent with significantly lower variance compared to STORM.

Lu: And for constrained tasks, they tested RanSOM-B on MovieLens and found that the beta-distributed steps effectively navigate complex constraint geometries better than those deterministic step sizes, leading to the lowest final average RMSE in those scenarios.

Meng: So practically speaking, this means if you're trying to solve a complex constrained problem without using gradient clipping for stability, this framework offers a way to do it more reliably. That’s a big deal for deployment on things that have real-world constraints.

Lalam: The generalization part is also strong; they show that RanSOM naturally aligns with modern optimization paradigms. For instance, with an L2-ball Linear Minimization Oracle, you recover Normalized SGD, and with an L infinity-ball oracle, you recover SignSGD based on spectral constraints.

Tom: It really shows how this single framework can adapt to different geometric constraints just by changing the oracle you plug in. The main point of the RanSOM paper is that it gives us a way to correct second-order bias without needing those restrictive smoothness assumptions or incurring those extra query costs that other methods demand.

Jane: To wrap up, RanSOM provides a unified framework for non-convex optimization by treating step sizes as random variables to enable robust second-order bias correction without Lipschitz assumptions on the Hessian or the typical computational overhead of auxiliary sampling.

Lu: It’s about achieving optimal rates by balancing the drift against three candidate error sources—main variance, constraint, and smoothness—and setting the step size eta to minimize that drift. This leads to a convergence bound that matches the optimal O(T minus one over three) scaling for p equals q equals two.

Meng: I just want to emphasize that this works even under heavy-tailed noise without requiring gradient clipping, which is something we've struggled with before. That’s a practical win for training stability and generalization.

Lalam: This RanSOM paper really shows how we can extend the benefits of randomized second-order corrections to projection-free optimization settings, confirming its effectiveness on complex non-convex tasks like Matrix Completion.

Tom: So, in short, RanSOM gives us a way to get optimal convergence rates by replacing deterministic step sizes with randomized steps drawn from distributions with mean eta sub t. We're looking at this as a powerful tool for getting better results from momentum methods in deep learning.

The paper's summary: Tom: So, to recap, RanSOM is this new method for optimization that fixes the bias in momentum using randomized step sizes instead of fixed ones, which cuts out those extra queries you usually have to make.

Jane: Exactly. They’re taking this concept and making it work both for unconstrained problems and constrained problems with two different approaches: one using exponential distributions and one using beta distributions for the steps.

Lu: The core idea they use is Stein-type identities, which are mathematical tools that let them estimate the curvature bias exactly, without needing to assume the function or its Hessian is perfectly smooth everywhere.

Meng: So it’s about replacing those fixed step sizes with random variables whose average value matches what you want, but the randomness itself helps correct for how curvy the landscape is in a non-convex setting.

Tom: And here's where it gets practical: they show that this approach achieves the optimal convergence rate of O of epsilon minus three under standard conditions, which is pretty good for deep learning training.

Jane: But what really catches my eye is how they handle the "heavy-tailed noise" part, showing that this works even when your gradient noise isn't nice and clean, like it can have fat tails.

Lu: They manage to do this without needing any of those strong assumptions you usually have to make about the Hessian being Lipschitz continuous, which is a big win for real-world scenarios where we don't know the exact shape of the model landscape.

Meng: From an engineering standpoint, avoiding auxiliary look-ahead points and only needing one Hessian-vector product at each step is a massive relief for computational efficiency.

Tom: And they show that it works with these different geometric constraints too, meaning you can use this same framework to recover things like Normalized SGD or SignSGD just by plugging in a different type of oracle.

Jane: It’s really about unifying the correction mechanism so that you don't have to switch between methods just because your problem suddenly gets constrained or noisy.

Lu: The implication here is that we can get more robust convergence guarantees for non-convex optimization without having to spend weeks analyzing every single function we use.

Tom: So, if you’re training something complex and you’re worried about momentum getting stuck in the wrong direction because of the local curvature, RanSOM offers a way to fix that bias efficiently and robustly.

The paper's improvements: Tom: So, we’re looking at what they suggest to improve RanSOM itself—basically how they can make the whole system even better than it already is.

Jane: They are focusing on making sure that the step size eta is chosen in a way that balances three different error sources: the main variance, any constraint issues, and the smoothness of the function.

Lu: The paper suggests optimizing that step size eta to minimize that total drift across all those error sources at every single iteration.

Meng: So instead of just picking a standard step size, RanSOM would dynamically adjust it based on how noisy or curvy things are right then and there to keep the convergence path as direct as possible.

Tom: And this dynamic adjustment helps them hit that optimal convergence rate we talked about earlier, matching that big O of T minus one over three scaling for p equals q equals two.

Jane: But they also show how this dynamic choice makes the method more robust against different types of noise, even when the gradient noise has those heavy tails we mentioned.

Lu: This means the framework isn't just good under perfect conditions; it keeps working well in real-world deep learning scenarios where things are messy.

Meng: From an engineering view, this means less hyperparameter tuning because the method is self-correcting for the step size, which is a huge practical win.

Tom: And they point out that by choosing eta this way, you get better results even in those tricky constrained environments where deterministic steps just struggle to navigate the geometry.

Jane: It really suggests that you don’t have to rely on external methods like gradient clipping if you use a framework like RanSOM because it handles those issues internally through the step size adjustment.

Lu: The implication here is that we can build more reliable optimization algorithms for complex tasks without needing incredibly strict assumptions about the underlying function's smoothness or structure.

Meng: So, this isn't just a theoretical fix for a paper; it’s an architectural improvement that makes AI systems training more stable and predictable across different problem types.

Tom: It sounds like they are pushing toward a system where the optimization process adapts to the data landscape in real time, rather than sticking to one fixed strategy.

Conclusion: Tom: So we’ve covered RanSOM, which is this paper about second-order momentum using randomized scaling to fix estimation bias in optimization without needing extra queries or strict smoothness assumptions on the function.

Jane: It really boils down to treating step sizes as random variables drawn from specific distributions, like exponential or beta distributions, and then using Stein’s Lemma to correct the curvature bias accurately.

Lu: The authors show that this leads to optimal convergence rates, specifically O of T minus one over three when p equals q equals two.

Meng: From an engineering standpoint, the biggest thing is that you get these strong theoretical guarantees without needing expensive auxiliary samples or worrying about the Hessian being Lipschitz continuous.

Tom: And they also show it works well even when you’re dealing with heavy-tailed gradient noise, which is a major hurdle in deep learning training today.

Jane: It changes how we think about optimization because it provides a unified framework that handles both unconstrained and constrained problems effectively with the same underlying logic.

Lu: The vision here is that we can build more robust AI systems for complex tasks without having to constantly worry about the exact mathematical smoothness of the model landscape.

Meng: For practical deployment, this means we can trust our optimization trajectories more because the method is designed to be self-correcting for those common instabilities.

Tom: So, in summary, RanSOM gives us a way to get better convergence rates by replacing deterministic step sizes with randomized steps drawn from distributions with mean eta sub t.

Jane: It’s a powerful tool that avoids the usual computational overhead and the need for auxiliary queries when dealing with second-order corrections in non-convex settings.

Lu: This work opens up possibilities for developing more stable and reliable AI training algorithms across a wider variety of complex models.

Meng: If we can make optimization this robust, it really lowers the barrier for deploying large, complex AI systems into real-world applications with tight constraints.

Tom: RanSOM is a significant step forward in making second-order methods more practical and generalizable than they’ve ever been before.

El Mahdi Chayti

EPFL

math.OC, cs.LG

Submitted: 2026-02-06

Updated: 2026-10-09

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 83/100

The gist: The gist: RanSOM recovers optimal convergence rates for non-convex stochastic optimization by replacing deterministic step sizes with randomized steps drawn from distributions with mean ηt, which

Key concepts

Curvature-Induced Bias: Standard momentum methods suffer because the historic momentum vector becomes a poor estimate of the current geometry due to function curvature. This leads to estimation errors proportional to $\nabla^2 f(x_{t-1} + \tau (x_t - x_{t-1}))$, which biases the optimization path away from the true minimum.
Randomized Second-Order Momentum: RanSOM treats the step size as a random variable, $s_t$, instead of a fixed value. By using distributions with mean $\eta_t$, it allows for 'statistical integration' of the Hessian using Stein's Lemma to calculate an unbiased estimate of the curvature bias without needing extra look-ahead points.
Stein-Type Identities: These mathematical identities are used to relate the expected change in gradients along a path to a single point-derivative. They allow RanSOM to compute exact, unbiased estimates of the Hessian's effect on the gradient using only one Hessian-Vector Product (HVP) at each step.
Universal Geometric Framework: This framework unifies the randomized correction with Linear Minimization Oracle (LMO) updates. It allows RanSOM to generalize standard optimizers like Normalized SGD and SignSGD by coupling them with spectral constraints, making it applicable across different optimization settings.

Terminology

Unified Framework — 1× in this paper · explained in 5 episodes

Summary

The gist: RanSOM recovers optimal convergence rates for non-convex stochastic optimization by replacing deterministic step sizes with randomized steps drawn from distributions with mean ηt, which eliminates curvature-induced bias using Stein-type identities and avoids auxiliary queries.

How it works

RanSOM addresses the fundamental flaw in standard momentum methods where the historic momentum vector mt becomes a stale estimator of the current geometry due to curvature, which leads to estimation bias proportional to Z 1 0 ∇2 f(xt−1 + τ (xt − xt−1))(xt − xt−1)dτ<ref:2602.06824#pg6>. The framework introduces Randomized Second-Order Momentum by treating the step size st as a random variable, such that xt+1 = xt + stdt, where E[st] = ηt<ref:2602.06824#pg14>. This randomization allows for statistical integration of the Hessian using Stein’s Lemma to compute an exact, unbiased estimate of the curvature bias using a single Hessian-Vector Product (HVP) at the next iterate xt+1<ref:2602.06824#pg16>.

The core mechanism involves two Stein-type identities that relate the expected change in gradients along the path to a single point-derivative, g′(s) = ∇2f(xt + sdt)dt<ref:2602.06824#pg20>. For unconstrained optimization, an Exponential Identity is used where E[g(s) − g(0)] = 1/λ E[g'(s)], implying that scaling the HVP at xt+1 by ηt = 1/λ yields an unbiased estimator of the gradient difference. For constrained optimization, a Beta Identity is employed where E[g(s) − g(0)] = E [(1-s)/K g'(s)], requiring the HVP to be re-weighted by (1−s)/K.

Key Advantages and Unification

RanSOM offers three distinct advantages over prior corrections, as summarized in Table 1<ref:2602.06824#pg4> The first is a Universal Geometric Framework, which couples the randomized correction with Linear Minimization Oracle (LMO) updates, allowing it to generalize optimizers like Normalized SGD (L2-ball LMO), SignSGD (L∞-ball LMO), and Muon-style updates via spectral constraints<ref:2602.06824#pg14>. The second is Optimal Rate and Generalized Robustness, as the analysis confirms that RanSOM achieves the optimal O(ϵ−3) sample complexity under standard bounded variance assumptions, and it extends robustness to heavy-tailed gradient noise (p ∈ (1, 2]) without requiring the Hessian to be Lipschitz continuous<ref:2602.06824#pg14>.

Computational Efficiency

A significant practical benefit is the avoidance of auxiliary query overhead. Unlike methods such as SOM-Unif which require sampling auxiliary look-ahead points, RanSOM evaluates the HessianVector Product at xt+1—the same point required for the subsequent gradient step<ref:2602.06824#pg14>. While this incurs a computational cost of roughly 2× that of a standard forward pass (similar to STORM), it avoids the additional data loading and forward pass overhead associated with auxiliary queries, which raises the cost to 3× or more<ref:2602.06824#pg14>.

Convergence Analysis and Assumptions

The theoretical analysis establishes convergence under generalized assumptions that capture modern deep learning dynamics. The analysis relies on Pointwise (L0, L1)–Smoothness (Assumption 4.2), which models the exploding gradient problem prevalent in Transformers<ref:2602.06824#pg15>. Furthermore, Assumption 4.4 models Affine Heavy–Tailed Noise, unifying affine variance growth with heavy-tailed noise (p, q. The convergence proofs establish the optimal rate under standard bounded variance and show that RanSOM converges robustly even under generalized (L0, L1)-smoothness and heavy-tailed gradient noise without requiring the Hessian to be Lipschitz continuous<ref:2602.06824#pg14>.

Performance on Benchmarks

Numerical experiments validate the framework's superiority. On the MNIST1D benchmark, RanSOM-E (Muon) outperforms all baselines, achieving a peak accuracy of 91.90% with significantly lower variance than STORM. In constrained settings, RanSOM-B outperformed SFW baselines on MovieLens, suggesting that Betadistributed steps effectively navigate complex constraint geometries better than deterministic step sizes.

Conclusion

RanSOM provides a unified, assumption-light framework for non-convex optimization by treating step sizes as random variables to enable robust second-order bias correction without Lipschitz assumptions on the Hessian or the typical computational overhead of auxiliary sampling<ref:2602.06824#pg4> By treating step sizes as random variables, it enables robust second-order bias correction without Lipschitz assumptions on the Hessian or the typical computational overhead of auxiliary sampling.

How it works (Detailed Mechanics)

Randomized Integration by Parts: The bias is estimated using Stein’s Lemma to relate the finite difference of gradients to a single point-derivative evaluated at a random endpoint<ref:2602.06824#pg4>
Joint Efficient Computation via Automatic Differentiation: The correction term requires evaluating the Hessian-Vector Product (HVP) at xt+1, which is computed in a single combined backward pass with the gradient computation, avoiding auxiliary point evaluations<ref:2602.06824#pg4>
Algorithm 1: RanSOM-E (Unconstrained / Normalized): This algorithm employs the Exponential Identity and uses an LMO to determine the update direction dt, which recovers Normalized SGD in the L2 case.
Algorithm 2: RanSOM-B (Constrained): This algorithm uses a Beta distribution for step sizes to ensure feasibility, employing a Frank-Wolfe Direction derived from the LMO<ref:2602.06824#pg6>.

Theoretical Analysis Details

The convergence analysis relies on Lemma B.19, which bounds the averaged error by relating it to initialization error, gradient noise terms, and Hessian bias terms<ref:2602.06824#pg4> The final convergence theorem shows that for p = q = 2, RanSOM-E recovers the optimal O(T−1/3) scaling for non-convex stochastic optimization<ref:2602.06824#pg4>

Constrained Optimization Details

For constrained problems, RanSOM-B uses the Frank–Wolfe gap G(x) as a convergence criterion, and the analysis shows that it recovers the optimal O(T−1/3) scaling for projection-free methods.

Final Summary of Results

RanSOM achieves optimal rates by balancing the drift against three candidate error sources—main variance, constraint, and smoothness—and setting the step size η to minimize this drift<ref:2602.06824#pg4> This leads to a convergence bound that matches the optimal O(T−1/3) scaling for p=q=2 and is robust under heavy-tailed noise settings. The framework successfully extends the benefits of randomized second-order corrections to projection-free optimization settings, confirming its effectiveness on complex non-convex tasks like Matrix Completion.

How it works (Detailed Proof Steps)

Telescope the descent: The analysis starts by telescoping the descent inequality from t = 0 to T − 1 using f(xT) ≥ f∗<ref:2602.06824#pg6>.
Substitute error bound: The averaged momentum error is bounded using Lemma B.19, which relates it to the initialization term, gradient noise terms, and Hessian bias terms<ref:2602.06824#pg4>
Optimize β and η: The optimal step size η is chosen by balancing the drift against three candidate error sources—main variance, constraint, and smoothness—to minimize the overall convergence rate<ref:2602.06824#pg6>.

Conclusion on Robustness

The framework handles heavy-tailed noise directly, generalizing the normalization benefits observed in first-order methods Hübler et al. (2025)<ref:2602.06824#pg14>. The analysis confirms that RanSOM achieves optimal convergence rates without the need for gradient clipping<ref:2602.

Improvements for AI systems

Bold momentum bias correction via randomized step sizes enables optimal convergence rates by replacing deterministic step sizes with randomized steps drawn from distributions with mean ηt. This allows for an exact, unbiased estimate of the curvature bias using a single Hessian-vector product computed jointly with the gradient, avoiding auxiliary queries.
RanSOM-E (Unconstrained) can achieve optimal O(ϵ−3) convergence rates under standard bounded noise and is robust even under generalized (L0, L1)-smoothness and heavy-tailed gradient noise (p ∈ (1, 2]). This means the system can train deep networks with ReLU activations without requiring individual sample smoothness or Lipschitz Hessian assumptions.
RanSOM-E variants can achieve superior stability compared to STORM in non-convex classification tasks like MNIST1D, maintaining high precision and low variance, which is crucial for reliable deployment in real-world applications where training instability is a major issue.
RanSOM-B (Constrained) can navigate complex constraint geometries better than deterministic step sizes, as seen by achieving the lowest final average RMSE in constrained matrix completion tasks like Nano MovieLens. This allows AI systems to solve non-convex constrained problems effectively without needing gradient clipping for stability.
The framework naturally generalizes modern optimization paradigms: With an L2-ball LMO, we recover Normalized SGD, and With an L∞-ball LMO, we recover SignSGD, enabling the system to adapt its update direction based on desired geometric constraints (Euclidean, Coordinate-Wise, or Spectral).

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 not equal to q, without a Lipschitz Hessian or clipping (O(epsilon-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.