Stochastic Optimization

Follow this topic Ask about this topic

Stochastic optimization seeks good decisions when exact objectives or gradients are unavailable, observations are noisy, or the environment changes, making it central to machine learning, planning, and resource allocation. Common approaches include stochastic gradient descent and adaptive optimizers, variance reduction, mirror and proximal methods, and online or bandit algorithms; robust and risk-sensitive methods address heavy-tailed noise and costly failures. Researchers evaluate these methods through convergence, sample-complexity, and regret guarantees, as well as experiments in deep-model training, constrained planning, and simulation. A continuing challenge is to make guarantees hold under realistic noise, dependence, and changing data while keeping computation, communication, and tuning costs manageable.

Latest papers

210 papers34 papers in the last four weeks, up 70% on the four weeks before. 0.2% of all new papers.

May 15, 2026

The Privacy Price of Tail-Risk Learning: Effective Tail Sample Size in Differentially Private CVaR Optimization

Differential privacy changes the effective sample size governing CVaR learning. For tail mass

τ

, the privacy-relevant sample size is not

n

, but

nτ

; equivalently, the effective private tail sample size is

εnτ

. Private CVaR excess risk decomposes into ordinary tail-risk statistical error and a privacy price. This decomposition is complete for scalar estimation and finite classes: scalar estimation has rate

Θ(B \min\{1,(nτ)^{-1/2}+(εnτ)^{-1}\})

, and finite classes of size

M

have rate

Θ(B \min\{1,\sqrt{\log(2M)/(nτ)}+\log(2M)/(εnτ)\})

. These complete rates hold under pure DP, and their lower bounds extend to approximate DP in the stated small-

δ

regimes. For convex Lipschitz learning, modular upper and lower reductions show that the CVaR-specific privacy term necessarily scales as

1/(εnτ)

, with dimension dependence inherited from private stochastic convex optimization. Together, these results identify ordinary private learning on

Θ(nτ)

informative tail records as the canonical hard subproblem inside private CVaR learning.

El Mustapha Mansouri

School of Engineering, Institute of Science Tokyo, Yokohama, Kanagawa 226-8501, Japan

Stochastic Optimization Differential Privacy Statistical Learning Theory Conditional Value-at-Risk Privacy-Utility Tradeoff

May 15, 2026

Stochastic Non-Smooth Convex Optimization with Unbounded Gradients

Much of the existing theory on first-order non-smooth optimization is built on a restrictive assumption that the gradients of the objective function are uniformly bounded. We introduce a much more realistic class of generalized Lipschitz functions, where the gradient norms are bounded by an affine function of the optimality gap. We then ask a natural question: what algorithm achieves the best global convergence rates for solving convex stochastic generalized Lipschitz optimization problems? To address this, we develop a new convergence analysis for several existing algorithms and find that AdamW with clipped updates, provably outperforms other popular stochastic optimization methods, such as SGD and AdaGrad. Moreover, our analysis establishes the critical role of AdamW's exponentially weighted gradient accumulation, as opposed to simple averaging. We further show that clipped AdamW is universal and achieves improved rates under the popular generalized smoothness assumption, analyze the convergence of clipped AdamW with diagonal and matrix preconditioners, and extend our results to the quasar-convex setting.

Dmitry Kovalev

Yandex Research

Stochastic Optimization Gradient Clipping Stochastic Optimization Convergence Adaptive Gradient Methods Nonsmooth Convex Optimization

May 14, 2026

Unified High-Probability Analysis of Stochastic Variance-Reduced Estimation

Stochastic estimators are fundamental to large-scale optimization, where population quantities must be inferred from noisy oracle observations. Although influential methods such as momentum, SPIDER, STORM, and PAGE have been highly successful, their analyses are largely estimator-specific and expectation-based, obscuring the structural tradeoffs that determine reliability. In this paper, we develop a unified framework for stochastic variance-reduced estimation based on a recursion with three components: memory retention, reset probability, and a correction term for iterate movement. This framework recovers several classical estimators, motivates new second-order variants, and yields a bias-variance decomposition of estimation error. Our main result is a unified high-probability bound proved using a new dimension-free vector-valued Freedman inequality, valid for smooth normed spaces involving random sums of vector martingales. The result applies in both Euclidean and non-Euclidean settings, including the analysis of mirror-descent-based methods in Banach spaces. As applications, we obtain high-probability oracle complexities for unconstrained optimization with mirror descent, establishing the logarithmic dependence on the confidence level. We also derive the first

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

oracle-complexity bounds for stochastic optimization with expectation constraints, improving upon the existing

\tilde{\mathcal{O}}(\varepsilon^{-4})

complexity by leveraging variance-reduced estimation for the first time in this setting.

Zhankun Luo, Antesh Upadhyay, M. Berk Sahin +3

School of Electrical and Computer Engineering and Purdue University West Lafayette, IN 47907 · Department of Computer Science Purdue University West Lafayette, IN 47907

Stochastic Optimization Variance Reduction

May 14, 2026

Stochastic Compositional Optimization via Hybrid Momentum Frank--Wolfe

Stochastic compositional optimization minimizes

F(f(x), x)

over a compact convex set when the inner map

f

is available only through noisy samples. We propose Hybrid Momentum Stochastic Frank--Wolfe, a projection-free method for outer functions

F

that are jointly convex and Lipschitz but not necessarily differentiable, such as maxima, CVaR, and norms. The method tracks the Jacobian and the value of

f

with momentum, using a Taylor correction for the value, and passes the tracked linearization to a generalized linear minimization oracle. Under finite-variance noise, it attains an expected generalized Frank--Wolfe gap of order

K^{-1/4}

for non-convex objectives and, when the linearized models minorize the objective, a last-iterate primal error of order

K^{-1/3}

. The analysis extends to heavy-tailed noise without clipping, with separate moment orders for values and Jacobians. With an exact oracle, the method reduces to the deterministic method of Vladarean et al. (2023).

El Mahdi Chayti, Mohamad Fakhouri

Machine Learning and Optimization Laboratory (MLO) EPFL, Switzerland

Stochastic Optimization Momentum Methods Nonconvex Stochastic Optimization Constrained Optimization

May 14, 2026

Scalable Solution of the Stochastic Multi-path Traveling Salesman Problem via Neural Networks

The multi-path Traveling Salesman Problem with stochastic travel costs arises in hybrid vehicle routing applications designed for Smart City and City Logistics, where multiple paths exist between each pair of locations. Travel times along these paths are typically affected by real-time traffic conditions and therefore modeled as stochastic. The objective of the problem is to determine a Hamiltonian tour that minimizes the expected total travel cost under uncertainty. In this work, we adopt a two-stage stochastic programming formulation. In the first stage, a predefined route specifying the sequence of locations to be visited is determined, while taking into consideration a second-stage recourse problem that selects the optimal path from the feasible set of alternative paths for each pair of locations, once real-time traffic conditions are realized. To reduce the computational burden imposed by the large number of scenarios required to capture travel time uncertainty, the innovation of this work is the integration of neural network-based surrogate models to approximate the expected value of the second-stage recourse problem. Different architectures and training strategies for the neural networks are proposed and analyzed, with performance evaluated in terms of computation time, solution quality, and generalization capability. Preliminary findings demonstrate the enhanced scalability and practical applicability of the approach for complex vehicle routing problems under uncertainty.

Xiaochen Chou, Ludovica Di Marco, Enza Messina

Department of Informatics, Systems and Communication, University of Milano-Bicocca, Viale Sarca 336, Milan, 20125, Italy.

Neural Surrogate Modeling Stochastic Optimization Traveling Salesperson Problem Combinatorial Optimization Vehicle Routing

May 13, 2026

Stochastic global optimization of continuous functions via random walks on Grassmannians

We introduce a stochastic global optimization method based on random walks on Grassmannian manifolds. To minimize a continuous objective

\ell:\mathbb{R}^d\rightarrow\mathbb{R}

, the method repeatedly samples random

k

-dimensional linear subspaces (with

k\ll d

), solves the resulting low-dimensional restrictions of these problems to these subspaces using an arbitrary black-box optimizer, and updates the iterate (which monotonically improves upon the previous iterate). Unlike classical optimization analyses that rely on convexity, smoothness, Lipschitz bounds, or Polyak-Lojasiewicz-type conditions, our convergence guarantees depend only on the geometric distribution of restricted minima across the

k

-dimensional subspaces passing through a given point in

\mathbb{R}^d

. We identify a gap parameter -- an analogue of a spectral gap for random walks -- that controls the rate at which the iterates approach the global minimum value. Finally, we argue that the same analysis yields a blind-spot robustness property: sufficiently narrow, deep dips of the loss function (small-measure regions where

\ell

spikes downward) have limited influence on the algorithm's trajectory, since they are unlikely to be encountered by random subspace sampling.

Kartik Gupta, Stephen D. Miller, Pradeep Ravikumar +1

Stochastic Optimization Subspace Optimization Black-Box Optimization Global Optimization Stochastic Optimization Convergence

May 13, 2026

Regret Equals Covariance: A Closed-Form Characterization for Stochastic Optimization

Regret is the cost of uncertainty in algorithmic decision-making. Quantifying regret typically requires computationally expensive simulation via Sample Average Approximation (SAA), with complexity

\mathcal{O}(Bn^{2}d^{3})

in the number of scenarios

B

, variables

n

, and constraints

d

. % This paper proves that expected regret in any stochastic optimization problem admits the exact decomposition % \begin{equation*} \mathrm{Regret}(c) = \mathrm{Cov}(c,,π^{}(c)) + R(c), \end{equation} % where

c

is the vector of uncertain parameters,

π^{*}(c)

is the optimal decision, and

R(c)

is a residual whose magnitude we bound explicitly under Lipschitz, smooth, and strongly convex conditions. % For linear programs and unconstrained quadratic programs, including the classical Markowitz portfolio problem, we prove

R(c)=0

exactly, so that

\mathrm{Regret}(c) = \mathrm{Cov}(c,π^{*}(c))

holds without approximation. % When historical cost-decision pairs

\{(c_i, π^*(c_i))\}

are available, the covariance can be estimated in

\mathcal{O}(nd^{2})

time, which is orders of magnitude faster than SAA. The estimation is performed by a single pass through the data. % We derive concentration bounds, a central limit theorem, and an asymptotically unbiased residual estimator, and we validate all results on synthetic LP, QP, and integer programming instances and on a rolling-window portfolio experiment using ten years of CRSP equity data.

Irene Aldridge

Stochastic Optimization Regret Minimization

May 13, 2026

Adam-SHANG: A Convergent Adam-Type Method for Stochastic Smooth Convex Optimization

We propose Adam-SHANG, a Lyapunov-guided Adam-type method that couples momentum, adaptive preconditioning, and a curvature-aware correction through a more stable lagged-preconditioner update. For stochastic smooth convex optimization, we prove convergence in expectation under an admissible stepsize condition that can always be satisfied by a conservative spectral bound, without imposing global monotonicity on the second-moment sequence. To obtain a less conservative practical rule, we introduce a computable trace-ratio stepsize, motivated by a local coordinatewise alignment condition. The same structural update is also tested beyond the convex setting with simplified parameters. Experiments validate the predicted stochastic decay and show competitive training performance against Adam and AdamW on deep learning tasks.

Yaxin Yu, Long Chen, Minfu Feng

School of Mathematics Sichuan University Chengdu, China · Department of Mathematics University of California, Irvine Irvine, CA, USA

Stochastic Optimization Momentum Methods Stochastic Optimization Convergence Adaptive Gradient Methods

May 13, 2026

NeuroRisk: Physics-Informed Neural Optimization for Risk-Aware Traffic Engineering

In production Wide-Area Networks (WANs), correlated failures dominate availability losses, forcing operators to reserve large safety margins that leave substantial capacity underutilized. Achieving high utilization under strict availability targets therefore requires risk-aware Traffic Engineering (TE) over dozens to hundreds of probabilistic failure scenarios-yet solving this problem at operational timescales remains elusive. We demonstrate that existing risk-aware formulations can be unified under an embedded Sort-and-Select structure, exposing a fundamental trade-off between expressiveness and tractability: classical optimizers either restrict scenario selection for efficiency or incur prohibitive decomposition costs. While deep learning appears promising, prior Deep TE methods mainly target maximum link utilization and rely on scaling-based feasibility, which fundamentally breaks under explicit capacity constraints and scenario-dependent risk. We present NeuroRisk, a physics-informed deep unrolled optimizer that exploits the structure of Sort-and-Select. NeuroRisk enforces feasibility via gated edge-local reservations and represents scenario sets through permutation-invariant, gradient-aligned cues. Evaluations on production-style WANs show that NeuroRisk achieves small optimality gaps relative to the solver with orders of magnitude speedup

(10^2- 10^5 \times)

on risk objectives, while outperforming neural baselines on nominal throughput.

Yingming Mao, Ximeng Liu, Jingyi Cheng +8

Xi’an Jiaotong University · Shanghai Innovation Institute · Shanghai Jiao Tong University +2

Stochastic Optimization Neural Network Optimization Learning to Optimize Risk-Sensitive Planning

May 12, 2026

Adaptive Multi-Round Allocation with Stochastic Arrivals

We study a sequential resource allocation problem motivated by adaptive network recruitment, in which a limited budget of identical resources must be allocated over multiple rounds to individuals with stochastic referral capacity. Successful referrals endogenously generate future decision opportunities while allocating additional resources to an individual exhibits diminishing returns. We first show that the single-round allocation problem admits an exact greedy solution based on marginal survival probabilities. In the multi-round setting, the resulting Bellman recursion is intractable due to the stochastic, high-dimensional evolution of the frontier. To address this, we introduce a population-level surrogate value function that depends only on the remaining budget and frontier size. This surrogate enables an exact dynamic program via truncated probability generating functions, yielding a planning algorithm with polynomial complexity in the total budget. We further analyze robustness under model misspecification, proving a multi-round error bound that decomposes into a tight single-round frontier error and a population-level transition error. Finally, we evaluate our method on real-world inspired recruitment scenarios.

Yuqi Pan, Davin Choo, Haichuan Wang +3

Harvard University · University of Witwatersrand · Wits Health Consortium +1

Stochastic Optimization Sequential Decision Making Dynamic Programming

May 12, 2026

Gradient Clipping Beyond Vector Norms: A Spectral Approach for Matrix-Valued Parameters

Gradient clipping is a standard safeguard for training neural networks under noisy, heavy-tailed stochastic gradients; yet, most clipping rules treat all parameters as vectors and ignore the matrix structure of modern architectures. We show empirically that data outliers often amplify only a small number of leading singular values in layer-wise gradient matrices, while the rest of the spectrum remains largely unchanged. Motivated by this phenomenon, we propose spectral clipping, which stabilizes training by clamping singular values that exceed a threshold while preserving the singular directions. This framework generalizes classical gradient norm clipping and can be easily integrated into existing optimizers. We provide a convergence analysis for non-convex optimization with spectrally clipped SGD, yielding the optimal

\mathcal{O}\left(K^{\frac{2 - 2α}{3α- 2}}\right)

rate for heavy-tailed noise. To minimize hyperparameter tuning, we introduce layer-wise adaptive thresholds based on moving averages or sliding-window quantiles of the top singular values. Finally, we develop efficient implementations that clip only the top

r

singular values via randomized truncated SVD, avoiding full decompositions for large layers. We demonstrate competitive performance across synthetic heavy-tailed settings and neural network training tasks.

Alexander Yukhimchuk, Mladen Kolar, Martin Takáč +1

MBZUAI · University of Southern California

Stochastic Optimization Gradient Clipping Nonconvex Stochastic Optimization Heavy-Tailed Stochastic Optimization Stochastic Gradient Descent

May 11, 2026

Muon is Not That Special: Random or Inverted Spectra Work Just as Well

The recent empirical success of the Muon optimizer has renewed interest in non-Euclidean optimization, typically justified by similarities with second-order methods, and linear minimization oracle (LMO) theory. In this paper, we challenge this geometric narrative through three contributions, demonstrating that precise geometric structure is not the key factor affecting optimization performance. First, we introduce Freon, a family of optimizers based on Schatten (quasi-)norms, powered by a novel, provably optimal QDWH-based iterative approximation. Freon naturally interpolates between SGD and Muon, while smoothly extrapolating into the quasi-norm regime. Empirically, the best-performing Schatten parameters for GPT-2 lie strictly within the quasi-norm regime, and thus cannot be represented by any unitarily invariant LMO. Second, noting that Freon performs well across a wide range of exponents, we introduce Kaon, an absurd optimizer that replaces singular values with random noise. Despite lacking any coherent geometric structure, Kaon matches Muon's performance and retains classical convergence guarantees, proving that strict adherence to a precise geometry is practically irrelevant. Third, having shown that geometry is not the primary driver of performance, we demonstrate it is instead controlled by two local quantities: alignment and descent potential. Ultimately, each optimizer must tune its step size around these two quantities. While their dynamics are difficult to predict a-priori, evaluating them within a stochastic random feature model yields a precise insight: Muon succeeds not by tracking an ideal global geometry, but by guaranteeing step-size optimality.

Zakhar Shumaylov, Nathaël Da Costa, Peter Zaika +6

University of Cambridge · University of Tübingen · University of Oxford

Stochastic Optimization Deep Learning Optimization Muon Optimizer

May 11, 2026

Optimistic Dual Averaging Unifies Modern Optimizers

We introduce SODA, a generalization of Optimistic Dual Averaging, which provides a common perspective on state-of-the-art optimizers like Muon, Lion, AdEMAMix and NAdam, showing that they can all be viewed as optimistic instances of this framework. Based on this framing, we propose a practical SODA wrapper for any base optimizer that eliminates weight decay tuning through a theoretically-grounded

1/k

decay schedule. Empirical results across various scales and training horizons show that SODA consistently improves performance without any additional hyperparameter tuning.

Thomas Pethick, Wanyun Xie, Roman Machacek +1

Independent Researcher · EPFL (LIONS) · University of Bern

Stochastic Optimization Deep Learning Optimization

May 10, 2026

Adversary-Robust Learning from Fully Asynchronous Directional Derivative Estimates

We propose FAR-SIGN (Fully Asynchronous Robust optimization via SIGNed directional projections) for adversary-resilient learning in parameter-server--worker systems. FAR-SIGN achieves robustness through sign-based updates along carefully designed directions and mitigates the resulting bias via a two-timescale mechanism. It admits both first-order and zeroth-order implementations and enables fully asynchronous execution without requiring a private reference dataset at the server. We establish almost-sure convergence of FAR-SIGN to the set of stationary points for smooth, nonconvex objectives. Moreover, we prove the near-optimal rate of

O(n^{-1/4+ε})

in the first-order setting and the standard

O(n^{-1/6+ε})

in the zeroth-order setting, where

n

is the iteration count and

ε>0

can be chosen arbitrarily small. Experiments on MNIST show that FAR-SIGN outperforms robust aggregation-based methods in both accuracy and wall-clock time.

Anik Kumar Paul, Nibedita Roy, Nagesh Talagani +3

Computer Science and Automation, Indian Institute of Science, Bengaluru · Edwardson School of Industrial Engineering, Purdue University · Department of Computer Science, IMT Atlantique

Stochastic Optimization Sign-Based Optimization Distributed Optimization Zeroth-Order Optimization Stochastic Optimization Convergence

May 9, 2026

Rennala MVR: Improved Time Complexity for Parallel Stochastic Optimization via Momentum-Based Variance Reduction

Large-scale machine learning models are trained on clusters of machines that exhibit heterogeneous performance due to hardware variability, network delays, and system-level instabilities. In such environments, time complexity rather than iteration complexity becomes the relevant performance metric for optimization algorithms. Recent work by Tyurin and Richtárik (2023) established the first time complexity analysis for parallel first-order stochastic optimization, proposing Rennala SGD as a time-optimal method for smooth nonconvex optimization. However, Rennala SGD is fundamentally a modification of SGD, and variance reduction techniques are known to improve the iteration complexity of SGD. In this work, we investigate whether variance reduction can also improve time complexity in heterogeneous systems. We show that, under a mean-squared smoothness assumption, variance reduction can improve time complexity in relevant parameter regimes. To this end, we propose Rennala MVR, a variance-reduced extension of Rennala SGD based on momentum-based variance reduction, and analyze its oracle and time complexity. We establish lower bounds for time complexity under these assumptions. On a stochastic quadratic benchmark, experiments with the exact method support the theory, while neural-network experiments with a practical inexact variant show similar empirical gains over Rennala SGD.

Zhirayr Tovmasyan, Artavazd Maranjyan, Peter Richtárik

KAUST

Stochastic Optimization Distributed Optimization Nonconvex Stochastic Optimization Variance Reduction

May 8, 2026

Convergent Stochastic Training of Attention and Understanding LoRA

Transformers have revolutionized machine learning and deploying attention layers in the model is increasingly standard across a myriad of applications. Further, for large models, it is common to implement Low Rank Adaptation (LoRA), whereby a factorized parameterization of them is trained, to achieve a surprisingly beneficial accuracy-size trade-off. In this work, via a unified framework we rigorously establish trainability of such models under stochastic methods. We prove that for any mild regularization, the empirical regression loss on a attention layer and LoRA on a shallow neural net, both induce Poincaré inequality for the corresponding Gibbs' measure. Then it follows via invoking recent results that a certain SDE, which mimics the SGD, minimizes the corresponding losses. In both the cases, our first-of-its-kind results of trainability on attention and nets, do not rely on any assumptions on the data or the size of the architecture.

Zhengkai Sun, Dibyakanti Kumar, Alejandro F Frangi +2

Stochastic Optimization Low-Rank Adaptation Transformer Attention Neural Network Training Dynamics

May 8, 2026

Robust stochastic first order methods in heavy-tailed noise via medoid mini-batch gradient sampling

We consider a first order stochastic optimization framework where, at each iteration,

K

independent identically distributed (i.i.d.) data point samples are drawn, based on which stochastic gradients can be queried. We allow gradient noise to be heavy-tailed, with possibly infinite variances. For the considered heavy-tailed setting, many algorithmic variants have recently been proposed based on gradient clipping or other nonlinear operators (e.g., normalization) applied over noisy gradients. In this paper, we take an alternative approach and propose a novel stochastic first order method dubbed Robust Stochastic Gradient Descent with medoid mini-batch gradient sampling, R-SGD-Mini for short. The core idea of R-SGD-Mini is to split the

K

-sized data batch into

M

distinct data chunks, form for each chunk the stochastic gradient, and update the solution estimate with respect to the stochastic gradient direction of the chunk that is medoid of gradients of all data-chunks. Under a general class of symmetric heavy-tailed gradient noises and a standard non-convex setting, we establish explicit bounds on the expected time-averaged squared gradient norm. More precisely, we show that the latter quantity converges at rate

\mathcal{O}(T^{-1})

to a small neighborhood of zero; we explicitly characterize this neighborhood in terms of noise and algorithm's parameters. Moreover, if the time horizon is known in advance, we establish the rate of

\mathcal{O}(T^{-\frac{1}{2}}).

Furthermore, when clipping is incorporated, we obtain convergence guaranties in the high-probability sense and recover the same rate. Experimental results indicate that R-SGD-Mini and its clipped variant consistently perform favorably compared to SGD, clipped SGD and Median-of-Means based methods.

Manojlo Vukovic, Dusan Jakovetic

Faculty of Technical Sciences, University of Novi Sad, Novi Sad, Serbia · Faculty of Sciences, University of Novi Sad, Novi Sad, Serbia

Stochastic Optimization Nonconvex Stochastic Optimization Heavy-Tailed Noise Stochastic Optimization Convergence Heavy-Tailed Distributions Heavy-Tailed Stochastic Optimization+1

May 8, 2026

Sample Complexity of Stochastic Optimization with Integer Variables

We establish sample complexity results for stochastic optimization over the integers, especially with a view to understand the complexity with respect to the corresponding continuous optimization problem. We show that integer optimization can sometimes require strictly more samples and sometimes strictly smaller number of samples, depending on the structure of the objective and constraints. 1. For Lipschitz objectives over subsets of the

\ell_\infty

ball, the statistical complexity of general stochastic mixed-integer, nonlinear, nonconvex optimization is exactly the same as stochastic linear optimization with just bound constraints. 2. For Lipschitz objectives over subsets of the

\ell_2

ball, we show that integer optimization can require strictly smaller sample size compared to the continuous setting in a certain regime. To get to this result, we also establish tight sample complexity results for nonconvex continuous stochastic optimization which, to the best of our knowledge, do not appear in prior work. 3. For strongly convex, smooth objectives, integer optimization has high statistical complexity compared to the continuous setting. In particular, we show that integer optimization requires

Ω(1/ε^2)

samples to report an

ε

-approximate solution, compared to the well-known

O(1/ε)

sample complexity from the continuous optimization literature.

Hongyu Cheng, Yinghao Zheng, Marco Molinaro +1

Dept. of Applied Mathematics & Statistics Johns Hopkins University Baltimore, MD 21218 · Microsoft Research (Redmond) · Dept. of Computer Science, PUC-Rio

Stochastic Optimization Sample Complexity Nonconvex Stochastic Optimization

May 7, 2026

Muon with Nesterov Momentum: Heavy-Tailed Noise and (Randomized) Inexact Polar Decomposition

Most first-order optimizers treat matrix-valued parameters as vectors, ignoring the intrinsic geometry of hidden-layer weights in neural networks. Muon addresses this mismatch by updating along the polar factor of a momentum matrix, but its theoretical understanding has lagged behind practice. In particular, practical implementations incorporate Nesterov momentum, compute the polar factor only approximately, and operate with stochastic gradients that may be heavy-tailed. We close this gap by developing a convergence theory for Muon with Nesterov momentum and inexact polar decomposition in non-convex matrix optimization under heavy-tailed noise. Our analysis builds on a unified framework for inexact polar decomposition that captures practical iterative approximations such as Newton-Schulz and quantifies how their errors propagate through the optimization dynamics. Under this framework, we establish an optimal iteration and sample complexity of

O \left(\varepsilon^{\frac{-(3α-2)}{(α-1)}} \right)

for finding an

\varepsilon

-stationary point, where

α\in(1,2]

denotes the heavy-tail index. For the inexact-polar setting with

σ_1=0

, we also provide guarantees that do not require prior knowledge of

α

. We analyze a randomized low-rank polar decomposition that is substantially more efficient than full-space methods while remaining compatible with our theory. Numerical experiments further demonstrate the effectiveness of the proposed inexact and randomized variants.

Sayantan Choudhury, Xiaoran Cheng, Martin Takáč +2

MBZUAI · Penn State University · Georgia Institute of Technology +1

Stochastic Optimization Momentum Methods Gradient Descent Nonconvex Stochastic Optimization Muon Optimizer Matrix Optimization+1

May 7, 2026

Learning to Cut: Reinforcement Learning for Benders Decomposition

Benders decomposition (BD) is a widely used solution approach for solving two-stage stochastic programs arising in real-world decision-making under uncertainty. However, it often suffers from slow convergence as the master problem grows with an increasing number of cuts. In this paper, we propose Reinforcement Learning for BD (RLBD), a framework that adaptively selects cuts using a neural network-based stochastic policy. The policy is trained using a policy gradient method via the REINFORCE algorithm. We evaluate the proposed approach on a two-stage stochastic electric vehicle charging station location problem and compare it with vanilla BD and LearnBD, a supervised learning approach that classifies cuts using a support vector machine. Numerical results demonstrate that RLBD achieves substantial improvements in computational efficiency and exhibits strong generalization to problems with similar structures but varying data inputs and decision variable dimensions.

Haochen Cai, Xian Yu

Department of Integrated Systems Engineering The Ohio State University Columbus, OH, USA, 43210 · Department of Integrated Systems Engineering The Ohio State UniversityMay Columbus, OH, USA, 43210

Stochastic Optimization

May 7, 2026

On Time, Within Budget: Constraint-Driven Online Resource Allocation for Agentic Workflows

Agentic systems increasingly solve complex user requests by executing orchestrated workflows, where subtasks are assigned to specialized models or tools and coordinated according to their dependencies. While recent work improves agent efficiency by optimizing the performance--cost--latency frontier, real deployments often impose concrete requirements: a workflow must be completed within a specified budget and before a specified deadline. This shifts the goal from average efficiency optimization to maximizing the probability that the entire workflow completes successfully under explicit budget and deadline constraints. We study constraint-driven online resource allocation for agentic workflows. Given a dependency-structured workflow and estimates of success rates and generation lengths for each subtask--model pair, the executor dynamically allocates models and parallel samples across simultaneously executable subtasks while managing the remaining budget and time. We formulate this setting as a finite-horizon stochastic online allocation problem and propose Monte Carlo Portfolio Planning (MCPP), a lightweight closed-loop planner that directly estimates constrained completion probability through simulated workflow executions and replans after observed outcomes. Experiments on CodeFlow and ProofFlow demonstrate that MCPP consistently improves constrained completion probability over strong baselines across a wide range of budget--deadline constraints.

Xinglin Wang, Zishen Liu, Shaoxiong Feng +9

School of Computer Science, Beijing Institute of Technology · Xiaohongshu Inc

Stochastic Optimization Cost-Aware Inference Agentic Workflows Inference-Time Compute Allocation Online Resource Allocation

May 5, 2026

Adapt or Forget: Provable Tradeoffs Between Adam and SGD in Nonstationary Optimization

We provide a theoretical analysis of Adam under non-stationary stochastic objectives, separating two regimes: Euclidean tracking under adaptive strong monotonicity of the Adam-preconditioned mean-gradient operator, and high-probability projected stationarity guarantees under general

L

-smooth objectives. In the tracking regime, we derive finite-time expected and high-probability bounds that decompose sharply into four components: initialization, objective drift, a first-moment tracking error governed by

\beta_1

, and a preconditioner perturbation governed by

\beta_2

. We characterize the burn-in time required for the transient terms to decay to the asymptotic tracking bound under constant and step-decay schedules. We also prove a high-probability bound on the average projected stationarity gap for Adam under distribution shift. Across both analyses, our bounds reveal a noise--drift tradeoff: in noise-dominated regimes, first-moment averaging and adaptive preconditioning can yield favorable upper guarantees, whereas in drift-dominated regimes, stale first-moment information and preconditioner perturbations can enlarge Adam's tracking guarantee, potentially allowing vanilla SGD to attain a smaller tracking error. Our explicit

(\beta_1,\beta_2,\epsilon)

-dependent bounds identify mechanisms through which adaptive step-sizing can help or hurt under nonstationarity and provide theoretical explanations consistent with Adam's empirical instability and stabilization under distribution shift.

Sharan Sahu, Abir Sarkar, Cameron J. Hogan +1

Department of Statistics and Data Science Cornell University

Stochastic Optimization Stochastic Optimization Convergence Adaptive Gradient Methods Stochastic Gradient Descent

Apr 30, 2026

Cost-Aware Learning

We consider the problem of Cost-Aware Learning, where sampling different components of a finite-sum objective incurs different costs. The objective is to reach a target error while minimizing the total cost. We propose Cost-Aware SGD, which uses a distribution based on gradient norms and costs to sample components. We provide a thorough analysis of this algorithm, including cost-improvement bounds over baselines, a characterization of distribution proxy sub-optimality, and a lower bound. We apply our theoretical insights to reinforcement learning with language models, where the computational cost of sequence-level policy gradients varies with length. We find that the advantage magnitude serves as a high-fidelity proxy for gradient norms, and use this to introduce Cost-Aware GRPO. Empirical results on 1.5B, 4B, and 8B LLMs demonstrate that this algorithm significantly reduces the tokens used in policy optimization while matching or exceeding baseline accuracy.

Clara Mohri, Amir Globerson, Haim Kaplan +2

Kempner Institute · Harvard University · Google Research +1

Stochastic Optimization RL for Language Models Group Relative Policy Optimization Policy Gradient Methods

Apr 28, 2026

Variational Neural Belief Parameterizations for Robust Dexterous Grasping under Multimodal Uncertainty

Contact variability, sensing uncertainty, and external disturbances make grasp execution stochastic. Expected-quality objectives ignore tail outcomes and often select grasps that fail under adverse contact realizations. Risk-sensitive POMDPs address this failure mode, but many use particle-filter beliefs that scale poorly, obstruct gradient-based optimization, and estimate Conditional Value-at-Risk (CVaR) with high-variance approximations. We instead formulate grasp acquisition as variational inference over latent contact parameters and object pose, representing the belief with a differentiable Gaussian mixture. We use Gumbel-Softmax component selection and location-scale reparameterization to express samples as smooth functions of the belief parameters, enabling pathwise gradients through a differentiable CVaR surrogate for direct optimization of tail robustness. In simulation, our variational neural belief improves robust grasp success under contact-parameter uncertainty and exogenous force perturbations while reducing planning time by roughly an order of magnitude relative to particle-filter model-predictive control. On a serial-chain robot arm with a multifingered hand, we validate grasp-and-lift success under object-pose uncertainty against a Gaussian baseline. Both methods succeed on the tested perturbations, but our controller terminates in fewer steps and less wall-clock time while achieving a higher tactile grasp-quality proxy. Our learned belief also calibrates risk more accurately, keeping mean absolute calibration error below 0.14 across tested simulation regimes, compared with 0.58 for a Cross-Entropy Method planner.

Clinton Enwerem, Shreya Kalyanaraman, John S. Baras +1

Department of Electrical & Computer Engineering and Institute for Systems Research, University of Maryland, College Park, MD, USA

Belief-Space Planning Stochastic Optimization Robotic Grasping Risk-Sensitive Planning Variational Inference Decision-Making under Uncertainty

Apr 28, 2026

Categorical Optimization with Bayesian Anchored Latent Trust Regions for Structural Design under High-Dimensional Uncertainty

Categorical structural optimization under aleatoric uncertainty is challenging because each design variable must be selected from a finite catalog of admissible instances, while each candidate design may require expensive stochastic finite-element evaluations. Existing latent-space optimization strategies can reduce the dimensionality of catalog attributes, but they often treat the reduced space as a continuous search domain. The resulting continuous optimum must then be rounded off to a nearby catalog instance, which may alter the objective value, constraint status, or physical interpretation of the design. To address this issue, this paper proposes the Categorical Optimization with Bayesian Anchored Latent Trust Regions (COBALT) framework for high-dimensional categorical Optimization Under Uncertainty. COBALT first embeds the physical catalog into a low-dimensional latent representation and locks the mapped instances as a discrete anchored graph. A data-independent random tree decomposition is then used to provide bounded-complexity additive modeling over high-dimensional categorical variables. On this anchored domain, an additive SAAS-GP surrogate is fitted to heteroscedastic MC-FEA observations, and a trust-region discrete graph acquisition search selects the next admissible catalog configuration without continuous relaxation or rounding-off. The proposed strategy is applied to robust design optimization of complex bar structures, considering structural weight, strain energy, and local buckling performance. By evaluating only valid catalog designs through the MC-FEA oracle, COBALT preserves physical admissibility throughout the active learning loop and improves the efficiency of robust categorical structural optimization.

Zhangyong Liang, Jie Hou, Huanhuan Gao +1

National Center for Applied Mathematics, Tianjin University, Weijin Road 92, 300072, Tianjin, China · School of Mechanical Engineering, Northwestern Polytechnical University, Youyixi Road 127, 710072, Xi’an, China · School of Mechanical and Aerospace Engineering, Jilin University, Renmin Street 5988, 130025, Changchun, China +1

Stochastic Optimization Surrogate-Assisted Optimization Structural Mechanics Bayesian Optimization

Apr 27, 2026

Stochastic simultaneous optimistic optimization

We study the problem of global maximization of a function f given a finite number of evaluations perturbed by noise. We consider a very weak assumption on the function, namely that it is locally smooth (in some precise sense) with respect to some semi-metric, around one of its global maxima. Compared to previous works on bandits in general spaces (Kleinberg et al., 2008; Bubeck et al., 2011a) our algorithm does not require the knowledge of this semi-metric. Our algorithm, StoSOO, follows an optimistic strategy to iteratively construct upper confidence bounds over the hierarchical partitions of the function domain to decide which point to sample next. A finite-time analysis of StoSOO shows that it performs almost as well as the best specifically-tuned algorithms even though the local smoothness of the function is not known.

Michal Valko, Alexandra Carpentier, Rémi Munos

INRIA Lille - Nord Europe, SequeL team, 40 avenue Halley 59650, Villeneuve d’Ascq, France · Statistical Laboratory, CMS, Wilberforce Road, CB3 0WB, University of Cambridge, United Kingdom

Stochastic Optimization Multi-Armed Bandits Global Optimization UCB Algorithms

Apr 22, 2026

Robust Out-of-Distribution Stochastic Optimization

Data-driven decision-making under uncertainty typically presumes the collection of historical data from an unknown target probability distribution. However, one may have no access to any data from the target distribution prior to decision-making. To address this challenge, we propose robust out-of-distribution stochastic optimization, a novel data-driven framework that effectively utilizes relevant data distributions for robust decision-making under unseen distributions. A key feature of our framework is that all data distributions are assumed to be randomly generated from a meta-distribution over distributions. To describe uncertainty in distribution generation, we propose to learn a data-driven uncertainty set in a reproducing kernel Hilbert space (RKHS) from relevant data distributions, with adjustable conservatism. We then incorporate this set into a min-max stochastic program to derive robust decisions. Notably, under randomness of distribution generation, we establish rigorous out-of-distribution generalization guarantees for the uncertainty set as well as the solution. To ease problem-solving in RKHS, an approximate parametrization with a provably bounded suboptimality and a row generation strategy are presented. Extensive numerical experiments on multi-item newsvendor and portfolio optimization demonstrate the superior out-of-distribution performance of our decision-making framework under unseen data distribution, even when only a small or moderate number of relevant sources are available.

Xianyu Li, Huan Xu, Xiaolin Huang +1

Department of Automation, Tsinghua University · Antai College of Economics & Management, Shanghai Jiao Tong University · Institute of Image Processing and Pattern Recognition, Shanghai Jiao Tong University

Stochastic Optimization OOD Generalization Distributionally Robust Optimization Decision-Making under Uncertainty

Apr 21, 2026

TESO: Online Tracking of Essential Matrix by Stochastic Optimization

Maintaining long-term accuracy of stereo camera calibration parameters is important for autonomous systems' perception. This work proposes Online Tracking of Essential Matrix by Stochastic Optimization (TESO). The core mechanisms of TESO are: 1) a robust loss function based on kernel correlation over tentative correspondences, 2) an adaptive online stochastic optimization on the essential manifold. TESO has low CPU and memory requirements, relies on a few hyperparameters, and eliminates the need for data-driven training, enabling the usage in resource-constrained online perception systems. We evaluated the influence of TESO on geometric precision, rectification quality, and stereo depth consistency. On the large-scale MAN TruckScenes dataset, TESO tracks rotational calibration drift with 0.12 deg precision in the Y-axis (critical for stereo accuracy) while the X- and Z-axes are five times more precise. Tracking applied to sequences with simulated drift shows similar precision with respect to the reference as tracking applied to no-drift sequences, indicating the tracker is unbiased. On the KITTI dataset, TESO revealed systematic inconsistencies in extrinsic parameters across stereo pairs, confirming previous published findings. We verified that intrinsic decalibration affected these errors, as evidenced by the conflicting behavior of the rectification and depth metrics. After correcting the reference calibration, TESO improved its rotation precision around the Y-axis 20 times to 0.025 deg and its depth accuracy 50 times. Despite its lightweight design, direct optimization of the proposed TESO loss function alone achieves accuracy comparable to that of neural network-based single-frame methods.

Jaroslav Moravec, Radim Šára, Akihiro Sugimoto

Czech Technical University · in Prague, Czech Republic · National Institute of Informatics +1

Stochastic Optimization Stereo Vision Camera Calibration

Apr 18, 2026

Towards Fully Parameter-Free Stochastic Optimization: Grid Search with Self-Bounding Analysis

Parameter-free stochastic optimization aims to design algorithms that are agnostic to the underlying problem parameters while still achieving convergence rates competitive with optimally tuned methods. While some parameter-free methods do not require the specific values of the problem parameters, they still rely on prior knowledge, such as the lower or upper bounds of them. We refer to such methods as partially parameter-free''. In this work, we target achieving fully parameter-free'' methods, i.e., the algorithmic inputs do not need to satisfy any unverifiable condition related to the true problem parameters. We propose a powerful and general grid search framework, named Grasp, with a novel self-bounding analysis technique that effectively determines the search ranges of parameters, in contrast to previous work. Our method demonstrates generality in: (i) the non-convex case, where we propose a fully parameter-free method that achieves near-optimal convergence rate, up to logarithmic factors; (ii) the convex case, where our parameter-free methods are competitive with strong performance in terms of acceleration and universality. Finally, we contribute a sharper guarantee for the model ensemble, a final step of the grid search framework, under interpolated variance characterization.

Yuheng Zhao, Yu-Hu Yan, Amit Attia +3

National Key Laboratory for Novel Software Technology, Nanjing University, China · School of Artificial Intelligence, Nanjing University, China · Tel Aviv University

Stochastic Optimization Nonconvex Stochastic Optimization Nonconvex Optimization

Apr 17, 2026

Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance

Analysis of Stochastic Gradient Descent (SGD) and its variants typically relies on the assumption of uniformly bounded variance, a condition that frequently fails in practical non-convex settings, such as neural network training, as well as in several elementary optimization settings. While several relaxations are explored in the literature, the Blum-Gladyshev (BG-0) condition, which permits the variance to grow quadratically with distance has recently been shown to be the weakest condition. However, the study of the oracle complexity of stochastic first-order non-convex optimization under BG-0 has remained underexplored. In this paper, we address this gap and establish information-theoretic lower bounds, proving that finding an

ε

-stationary point requires

Ω(ε^{-6})

stochastic BG-0 oracle queries for smooth functions and

Ω(ε^{-4})

queries under mean-square smoothness. These limits demonstrate an unavoidable degradation from classical bounded-variance complexities, i.e.,

Ω(ε^{-4})

and

Ω(ε^{-3})

for smooth and mean-square smooth cases, respectively. To match these lower bounds, we consider Proximally Anchored STochastic Approximation (PASTA), a unified algorithmic framework that couples Halpern anchoring with Tikhonov regularization to dynamically mitigate the extra variance explosion term permitted by the BG-0 oracle. We prove that PASTA achieves minimax optimal complexities across numerous non-convex regimes, including standard smooth, mean-square smooth, weakly convex, star-convex, and Polyak-Lojasiewicz functions, entirely under an unbounded domain and unbounded stochastic gradients.

Arda Fazla, Ege C. Kaya, Antesh Upadhyay +1

School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN 47907, USA.

Stochastic Optimization Oracle Complexity Nonconvex Stochastic Optimization Stochastic Optimization Convergence