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.

Aug 10, 2026

A Tight Lower Bound for Smooth Nonconvex Stochastic Optimization with Bounded Gradient Noise

We prove a sharp lower bound for smooth nonconvex stochastic optimization with uniformly bounded gradient noise. In the

K=1

fresh-sample model, every randomized adaptive algorithm requires

Ω\left( \frac{ΔL}{ε^2} + \frac{ΔLσ^2}{ε^4} \right)

queries to find a point with expected gradient norm at most

ε

. This matches the standard upper bound and, to the best of our knowledge, resolves the question raised by [Arjevani et al. 2023] of whether almost-surely bounded oracle error permits a better rate than bounded variance. The proof was independently generated with GPT-5.6 Sol in Codex's Ultra mode during a two-hour session. The human author supplied the prompt and was responsible only forchecking the proof and revising and polishing the manuscript.

Jikai Jin

Stochastic Optimization Nonconvex Stochastic Optimization Stochastic Optimization Convergence

Aug 6, 2026

On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalities

We study stochastic extragradient (SEG) methods for solving monotone variational inequality problems (VIPs) over a feasible set. Although extragradient is a foundational algorithm for VIPs and its deterministic convergence theory is well developed, its stochastic counterpart remains less understood. Most existing analyses focus on independent-sample SEG (I-SEG) and assume either that the domain is compact or that the variance of the stochastic operator is uniformly bounded. The behavior of same-sample SEG (S-SEG), a natural variant with materially different properties, has received far less attention. In this work, we address these gaps in the literature. We first show that S-SEG is sensitive to samplewise Lipschitz parameters: mean Lipschitzness and bounded variance alone do not ensure convergence, even on a compact set. Then, for possibly unbounded domains, we establish a high-probability restricted-gap convergence for each SEG variant under a relaxed set of assumptions, and show that certain fundamental improvements to these results are impossible in general. Finally, we show that a known asymmetric double step-size selection that guarantees almost sure last-iterate convergence for I-SEG can fail for S-SEG: there exists a stochastic monotone VIP for which S-SEG diverges almost surely even under the modified step-sizes.

TaeHo Yoon, Nicolas Loizou

Department of Applied Mathematics and Statistics & Mathematical Institute for Data Science, Johns Hopkins University.

Stochastic Optimization Last-Iterate Convergence Stochastic Optimization Convergence

Aug 5, 2026

A proximal subgradient method for nonconvex stochastic optimization under the Kurdyka-Łojasiewicz condition

This work introduces a proximal stochastic subgradient method for minimizing the sum of an expected cost, whose integrand is potentially nonsmooth and nonconvex, and a lower semicontinuous, prox-bounded function. We target a broad class of integrands obeying a nonsmooth, localized variant of the descent lemma in the decision variable, a structural assumption that simultaneously covers smooth losses with Lipschitz gradient and differences of such losses with convex functions. At each iteration the expected cost is replaced by a sample average that is progressively refined, and the proximal-subgradient stepsize is selected by an Armijo-type line search enforcing a sufficient-decrease property up to stochastic errors induced by the sample-based approximation. This framework accommodates substantially more general problem formulations than existing methods, in particular, it requires neither (weak) convexity of the regularizer nor a uniform bound on the variance of the stochastic oracle, and our analysis yields convergence guarantees that are new even in the smooth setting. Specifically, we establish almost sure convergence of the sequence of function values and stationarity of every accumulation point of the trajectories under the relaxed requirement that the sample-size sequence be merely nondecreasing and unbounded, with no prescribed growth rate. Leveraging the Kurdyka-Lojasiewicz (KL) property, we further upgrade this subsequential guarantee to convergence of the whole trajectory to a single stationary point. Finally, for exponential-type KL desingularizing functions and polynomially growing sample sizes, we derive explicit polynomial convergence rates, up to a logarithmic factor, for both the function values and the iterates.

Felipe Atenas, Alejandro Jofré, Pedro Pérez-Aros +1

Centro de Modelamiento Matem´atico (CNRS IRL2807), Universidad de Chile, Santiago, Chile · Departamento de Ingenier´ıa Matem´atica and Centro de Modelamiento Matem´atico (CNRS IRL2807), Universidad de Chile, Santiago, Chile · Department of Mathematics, University of Alicante, Alicante, Spain

Stochastic Optimization Nonconvex Stochastic Optimization Stochastic Optimization Convergence

Aug 5, 2026

On MUON optimization: From non-convergence to an error analysis with Polar Express and the Newton-Schulz polynomial from implementations

Stochastic gradient descent (SGD) optimization methods are the standard instruments for the training of deep neural networks (DNNs). In many relevant artificial intelligence (AI) systems - such as popular large language models (LLMs)-not the standard SGD scheme is used as the optimization method but instead suitable accelerated variants of SGD are employed. One of the most popular methods of such accelerated SGD variants is the momentum orthogonalized by Newton-Schulz (MUON) optimizer proposed by Jordan et al. in 2024. The MUON optimizer exploits the special matrix structure of the weight parameters in the training of the DNNs and, in its original form, employs five Newton-Schultz (NS) matrix steps in each MUON iteration. In this work we propose and study a generalized variant of the MUON optimizer involving an arbitrary number of generalized NS steps with polynomials of possibly arbitrary high degree. The considered optimizer covers MUON with the original NS polynomial as well as MUON combined with the recently proposed Polar Express method as special cases. For a simple class of stochastic optimization problems (SOPs) we show for almost every mini-batch size that MUON fails to converge to the solution of the SOP as the number of gradient steps converges to infinity. We also establish an error analysis for MUON with the generalized NS steps that provides convergence rates in terms of the number of gradient steps and in terms of the size of the mini-batch. We illustrate our general error analysis for MUON in the case of several concrete examples including quadratic stochastic optimization problems (SOPs) as well as

\ell_2

regularized logistic regression for binary classification.

Thang Do, Steffen Dereich, Arnulf Jentzen

School of Data Science, The Chinese University of Hong Kong, Shenzhen (CUHK-Shenzhen), China · Department of Probability and Statistics, Institute of Mathematics, Vietnam Academy of Science and Technology, Vietnam · Institute for Mathematical Stochastics, Faculty of Mathematics and Computer Science, University of Münster, Germany +2

Stochastic Optimization Newton-Schulz Iteration Muon Optimizer Second-Order Optimization Stochastic Optimization Convergence Accelerated Gradient Methods

Aug 4, 2026

Robust General Utility for Reinforcement Learning

Reinforcement learning (RL) with general utility extends classic RL by optimizing an arbitrary utility functional of the policy-induced occupancy measure, thereby enabling a broader range of applications. However, previous work on general utility RL typically assumes the evaluation utility is fixed and correctly specified. In practice, the utility used at deployment can deviate from the training one, creating a robustness gap that prior work does not address. Motivated by this, we propose robust general-utility RL, a minimax learning framework that trains policies against utility misspecification within a prescribed uncertainty set. Our framework strictly generalizes standard general-utility RL while also providing a unified view of many existing RL frameworks, including reward-robust RL and constrained RL, through appropriate choices of the utility uncertainty set. We further develop provably convergent stochastic algorithms for two regimes. For concave utilities, we develop a projected stochastic gradient descent-ascent method and establish stationarity guarantees. For the more challenging nonconcave regime, we propose a stochastic prox-extragradient algorithm that mitigates ill-posed behavior induced by nonconcavity, with convergence guarantees to approximate first-order stationarity. Experiments on LLM safety alignment and exploration maximization tasks further corroborate the convergence behavior consistent with our theory.

Zixuan Liu, Fangzheng Wu, Brian Summa +1

Department of Computer Science, Tulane University, New Orleans, LA, 70118, USA

Stochastic Optimization Reinforcement Learning Robust RL

Aug 4, 2026

Stochastic Saddle Avoidance Beyond Unit Excitation and Smoothness: A Pathwise Lyapunov-Perron Framework

Unit excitation (UE) is a common assumption in stochastic saddle avoidance: the stochastic error must have a uniformly positive component along every direction, in expectation. This condition gives a direct way to rule out convergence to strict saddles, but it also oversimplifies the actual noise structure, and does not match many stochastic optimization regimes. In overparameterized or interpolation models, the noise may vanish near stationarity. In finite-sum problems, the stochastic gradient noise may lie in a low-dimensional, data-dependent subspace. In these (common) scenarios, UE is naturally not satisfied. In this paper, we prove an abstract almost sure avoidance theorem for stochastic recursions without UE. The theorem replaces UE-type requirements by verifiable pathwise conditions. In applications, these conditions follow, e.g., from local smoothness and finite-moment assumptions under standard i.i.d. sampling, or from the finite-sum structure under without-replacement sampling. Since the stochastically sampled maps generally do not share a fixed point, the celebrated center-stable manifold argument used in deterministic analyses is not directly applicable. Instead, we use a path-dependent change of variables together with a pathwise Lyapunov--Perron-based proof strategy. As applications, we obtain strict saddle avoidance for stochastic mirror descent (including SGD) and for random reshuffling. For nonsmooth composite objectives, we prove avoidance results for a proximal-type stochastic gradient method. Combining these insights with suitable iterate convergence guarantees, this allows establishing convergence to local minimizers of the original objective function.

Junwen Qiu, Bohao Ma, Andre Milzarek +1

Industrial Systems Engineering and Management, National University of Singapore, Singapore. · School of Data Science, The Chinese University of Hong Kong, Shenzhen, China.

Stochastic Optimization Nonconvex Stochastic Optimization Random Reshuffling Stochastic Gradient Descent

Aug 3, 2026

Particle-based Generalised Stochastic Optimisation

We develop a class of general diffusion-based stochastic particle optimisation methods for loss functions with intractable gradients. Specifically, we consider problems in which the loss gradient is an integral with respect to a parameter-dependent distribution, a structure that includes training generative models, fine-tuning, and learning latent-variable models. We introduce mean-field dynamics and its interacting-particle approximations, which contain several existing algorithms as special cases and provide a route to constructing new methods. Under well-posedness and joint contractivity assumptions, we prove exponential convergence and show that the continuous-time particle system admits a non-asymptotic error bound. We illustrate our framework by developing higher-order Langevin and momentum optimisers and evaluating them on maximum marginal-likelihood estimation and energy-based-model training.

Jiechen Jackie Zhang, O. Deniz Akyildiz

Department of Mathematics, Imperial College London

Stochastic Optimization Langevin Dynamics Stochastic Optimization Convergence

Aug 3, 2026

Accelerating Evolutionary Strategy via Rao-Blackwellizing Realization of Uncertain Input

We investigate Optimization under Input Uncertainty (OIU), in which the input to the objective function, rather than the objective function itself, is subject to uncertainty. OIU appears in manufacturing processes with production tolerance, control of physical systems with actuation noise, Mixture of Experts, and Reinforcement Learning (RL). Most of the existing approaches solve OIU by using the value of the objective function but discard the information of the realized input, even though the realized input is observable in various applications. The question here is whether the discarded information of the realized input is useful to accelerate the optimization process. We affirmatively answer this question for Evolutionary Strategy (ES) by theoretically showing that the information of the realized input can reduce the variance of the gradient estimator via Rao-Blackwellization. Using the Rao-Blackwellized gradient estimator, we propose Phenotype-Accelerated Evolutionary Strategy (PAES), which is a refinement of ES for OIU. Numerical experiments show that PAES converges faster than the usual ES from simple continuous optimization problems to RL benchmarks.

So Nakashima, Tetsuya J. Kobayashi

Institute of Industrial Science The University of Tokyo · Institute of Industrial Science, The University of Tokyo · Universal Biology Institute, The University of Tokyo

Stochastic Optimization Evolution Strategies Variance Reduction

Aug 3, 2026

Heterogeneous Multi-Agent Reinforcement Learning for Radio Resource Management under Coupled Finite-Horizon Constraints

Maximizing throughput under proportional fairness in dense wireless networks requires jointly managing user association, scheduling, base station (BS) activation, and handover control under hard finite-horizon energy and handover budgets, which induces a fundamental tension between BS-side energy management and user-side handover regulation. While multi-agent reinforcement learning (MARL) is a natural framework for such distributed sequential control, its application here faces two difficulties: finite-horizon budget constraints cannot be evaluated at each time slot, and the nonlinear proportional fairness utility admits no principled per-slot decomposition. We propose HeLyMARL, a Lyapunov-embedded heterogeneous MARL framework that resolves both via drift-plus-penalty decomposition with virtual queues. The energy and handover constraint pressures are internalized directly into a unified per-slot reward, converting the constrained finite-horizon problem into an unconstrained MARL problem. Comparison against two Lagrangian-based alternatives reveals a timescale separation: Lagrangian relaxation regulates constraints only across training episodes, whereas the virtual queues of HeLyMARL bound cumulative budget consumption at every partial horizon within an episode, a pacing guarantee beyond the reach of greedy Lyapunov-based control. Simulations show that HeLyMARL is the only method that sustains the throughput-fairness balance together with uninterrupted service throughout the horizon, outperforming conventional MARL, Lyapunov-based, and constrained MARL benchmarks without premature budget exhaustion.

Yeonseo Jeong, Wonhyeok Ko, Sungweon Hong +1

Department of Electronic Engineering, Hanyang University, Seoul, Korea · Department of AI-Semiconductor, Hanyang University, Seoul, Korea

Stochastic Optimization Fair Resource Allocation Constrained RL Wireless Resource Allocation Multi-Agent Reinforcement Learning Heterogeneous MARL

Jul 31, 2026

Adaptivity via a Parallel Architecture for Stochastic Gradient Methods

We develop a parallel framework that assembles static gradient methods to achieve better adaptivity. A static gradient method, denoted by

\mathrm{GD}(x_0,T)

, takes as input an initial point

x_0\in\mathbb{R}^n

and

T\in \mathbb{R}^+

specifying the number

\floor{T}

of iterations. The step size is chosen as

s=S(T)

, where

S(\cdot)

is a predetermined function of

T

. The method then performs the iterations

x_{i+1}=x_i-\fracη{s}\cdot g_i,

where

g_i

is a stochastic gradient evaluated at

x_i

, and

η

is a scaling factor. For an integer

p\ge1

, the

p

processors in the proposed parallel framework search for an appropriate value of

T

according to a geometric sequence so that the resulting gradient descent satisfies the desired convergence conditions. Each processor executes an infinite sequence of stages indexed by

i=1,2,\ldots

. At stage

i

, processor

j

is assigned

T_{j,i}=h(j,i),

where

h:\mathbb{N}\times\mathbb{N} \rightarrow\mathbb{R}^{+}

is a prescribed function. Processor

j

(j=0,1,\ldots,p-1)

executes

\mathrm{GD}(x_0, T_{j,i})

at stage

i

.

Bin Fu

University of Texas Rio Grande Valley

Stochastic Optimization Stochastic Optimization Convergence Adaptive Gradient Methods Stochastic Gradient Descent

Jul 29, 2026

On the robustness of noisy solutions in non-convex neural networks

Optimization in non-convex neural network models is strongly influenced by the geometry of the solution space: sparse, isolated, point-like clusters are typically algorithmically inaccessible, whereas wide and flat regions can be found efficiently despite being relatively rare. At zero temperature this picture has been formalized in binary perceptrons through the overlap gap property (OGP), which limits algorithmic access to configurations with zero training error above a critical constraint density

α_{\rm OGP}

. Here we extend this description to finite temperature, where a positive training error is allowed and statistically penalized. We first show that the frozen one-step replica-symmetry-breaking solution, dominating the zero temperature equilibrium measure, survives at any finite temperature. We furthermore derive a general criterion, based on the smoothness of the single-pattern Gibbs weight near the decision boundary, that determines when a finite-temperature relaxation of the loss removes freezing. We then extend the OGP construction to finite temperature and show that dense, algorithmically accessible regions of finite-energy configurations persist beyond

α_{\rm OGP}

, up to a threshold

α_{\rm OGP}(ε)

that grows with the allowed training error

ε

. Finally, in the teacher-student setting, we show that these wide, finite-energy regions still retain good generalization. Using a finite energy message-passing algorithm, we demonstrate numerically that thermal noise enables effective generalization in the regime of constraint densities where both recovering the teacher and finding a zero temperature solution are computationally hard.

Enrico M. Malatesta, Alessandra Passalacqua, Riccardo Zecchina

Department of Computing Sciences, Bocconi University, Milano, Italy · Bocconi Institute for Data Science and Analytics (BIDSA)

Stochastic Optimization Neural Network Generalization Nonconvex Optimization

Jul 28, 2026

Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimization

We study stochastic composite nonconvex optimization over a compact convex set when gradient samples arrive along a single trajectory of a fixed ergodic Markov chain. Existing single-trajectory variance-reduction theory covers smooth unconstrained objectives; we address the projection-free composite setting using the generalized Frank-Wolfe gap. We propose MC-ALFCG, which combines a momentum conditional-gradient method with coupled capped multilevel Monte Carlo estimation and per-iteration clipping. The deepest nested average uses consecutive states from the same trajectory, yielding conditional bias

O(τ_{\mathrm{mix}}/T)

uniformly over the starting state, while coupling controls the gradient-difference second moment through the iterate displacement. Clipping enforces the pathwise bounds needed by the adaptive analysis. We reduce the Markovian recursion to its independent-sampling counterpart under

σ^2\mapsto 2ΛG_σ^2

and

L^2\mapsto 2ΛL^2

, where

Λ=O(τ_{\mathrm{mix}}\log T)

. For positive centered noise, the tuned method achieves expected sample complexity

\widetilde{O}((τ_{\mathrm{mix}}^2G_σ+τ_{\mathrm{mix}}^{5/2}G_σ^2)\varepsilon^{-3}+τ_{\mathrm{mix}}^5\varepsilon^{-2})

. The exactly noiseless specialization achieves

\widetilde{O}(\varepsilon^{-2})

with mixing-time-free constants, while a mixing-time-oblivious variant achieves

\widetilde{O}(τ_{\mathrm{mix}}^6\varepsilon^{-3}+τ_{\mathrm{mix}}^3\varepsilon^{-2})

. All guarantees are in expectation under a fixed transition kernel. Controlled numerical studies examine dependence sensitivity, a nonconvex composite instance, and clipping behavior.

Zhaojun Peng

School of Computer Science Nanjing University of Information Science and Technology

Stochastic Optimization Nonconvex Stochastic Optimization Nonconvex Optimization Stochastic Optimization Convergence Variance Reduction

Jul 24, 2026

Closed-Loop Generative Selection: Convergence, Memory, and Noisy Oracles

Closed-loop generative selection has become a workhorse of computational drug discovery: a learned generative model proposes candidate molecules, a fitness oracle scores them, the best are kept, and the model is retrained on this elite set before the next round. Despite its wide use, the method has lacked a rigorous convergence theory, largely because retraining the model each round breaks the Markov property on which classical evolutionary-algorithm analysis relies. We develop a self-contained theory of convergence and expected running time for this class of algorithms. By recovering a Markov structure on an enlarged state space, we show that elitism makes the search absorbing, and we prove almost-sure convergence together with a runtime bound that decomposes the search into the time spent escaping each fitness level. We then analyse the role of the model's memory---how much of the past it is trained on. When learning improves steadily with more data, deeper memory never hurts; when it does not, an exit-time analysis pinpoints the optimal memory depth and shows that excess memory can actually slow convergence. The theory extends to multi-objective search and to noisy oracles: we quantify how many repeated evaluations certify progress under light-tailed noise, and how robust estimators restore guarantees under heavy tails. Recast in terms of oracle evaluations - the true bottleneck in drug design - the analysis yields a concrete, evaluation-minimal strategy. Areproducible study confirms the predictions, including the surprising cost of excess memory. We close with three open problems.

Konstantin Fackeldey, Christof Schütte

Zuse Institute Berlin, Takustraße 7, 14195 Berlin, Germany · Institute for Mathematics, Technical University Berlin, Fasanenstr 89,10623 Berlin, Germany · Department of Mathematics and Computer Science, Freie Universität Berlin, Arnimallee 6, 14195 Berlin, Germany

Stochastic Optimization Runtime Analysis of Evolutionary Algorithms Drug Discovery

Jul 20, 2026

Weak-to-Strong Learning in Decision Making

Many operational decisions rely on predictive models that estimate uncertain outcomes conditional on observable contexts. Training such models, however, often faces a fundamental data asymmetry: labeled outcomes are scarce or costly to obtain, while contextual covariates are abundant. Motivated by this data asymmetry, we develop a decision-aware weak-to-strong (W2S) framework that leverages both labeled and unlabeled data to improve contextual stochastic optimization. Specifically, we first train a weak model using limited labeled data and then use it to generate predicted outcome distributions on unlabeled contexts. These distributions provide soft supervision for training a strong model. We establish a non-asymptotic upper bound on the excess decision risk of W2S and a complementary lower bound for a strong-only benchmark. Their comparison yields explicit sufficient conditions under which W2S improves downstream decision performance. The key quantity is the correlation dimension between the weak and strong feature representations: when it is small, abundant unlabeled data reduce the effect of teacher errors along non-overlapping directions. A synthetic newsvendor experiment and a comment moderation experiment based on real-world data provide empirical evidence consistent with the theory.

Jingwei Ji, Renyuan Xu

Management Science and Engineering, Stanford University

Stochastic Optimization Decision-Focused Learning Weak-to-Strong Generalization Semi-Supervised Learning Decision-Making under Uncertainty

Jul 20, 2026

Task-Space Constrained Stochastic Trajectory Optimization for Time-Optimal Forestry Crane Motion Planning

Efficient, collision-free, and time-optimal motion planning is a fundamental requirement for autonomous forestry cranes operating under hydraulic pump-flow constraints. The Via-Point-based Stochastic Trajectory Optimization (VP-STO) algorithm has demonstrated near-time-optimal hybrid motion planning in this domain, but requires a fixed terminal joint configuration specified prior to optimization. For kinematically redundant manipulators such as forestry cranes, this pre-commitment to a single inverse kinematics solution restricts the planner's ability to exploit redundancy, particularly under the nonlinear, globally coupled pump-flow constraint where admissible joint velocities depend on their combined hydraulic demand. This paper presents TSC-VP-STO, a task-space-constrained extension of VP-STO that replaces the strict terminal joint-space constraint with a task-space constraint, jointly optimizing the trajectory and the redundant degrees of freedom of the terminal configuration. This enables the planner to adapt end configurations to the environment-dependent motion and hydraulic flow allocation, yielding more balanced pump utilization and shorter trajectory durations. We formalize the approach through a configuration space decomposition and derive a concrete reachability constraint for the forestry crane kinematics. Experimental evaluations across multiple planning targets and via-point configurations demonstrates a reduction on trajectory durations by 12-15% on average and improved pump-flow utilization compared to the baseline VP-STO. The practical applicability of TSC-VP-STO is validated through real-world deployment on a forestry crane, including a full log-loading cycle.

Marc-Philip Ecker, Christoph Fröhlich, Bernhard Bischof +2

Automation & Control Institute (ACIN), TU Wien, 1040 Vienna, Austria · Center for Vision, Automation & Control, AIT Austrian Institute of Technology GmbH, 1210 Vienna, Austria

Stochastic Optimization Constrained Motion Planning Trajectory Optimization Motion Planning

Jul 11, 2026

Is Model Instability just Noise to be Tolerated or a Property that can be Managed?

In software analytics, rerunning the same analysis twice often yields different models and conclusions. This reduces trust in the model and limits its use. We find that model instability is a major problem. Across 127 multi-objective SE optimization problems (12,700 test cases), repeated runs of a state-of-the-art optimizer agree on only 13.7% of test cases, even under improved settings. We argue that this instability is not merely noise to tolerate, but a property that can be measured and managed. By adjusting how labels are spent, how complex the models become, and how splits are scored, we obtain models that agree 4.8 times as often as the default configuration. The standard deviation of optimization error falls by 22% on average (mean std 17.4 to 13.6), while recommendation quality improves rather than degrades. In terms of quality, the refined settings are statistically top-ranked on 119 of 127 datasets, compared to 74 for the defaults. We then test causal and data-locality interventions and find that they help only partially, suggesting a residual stability floor. Our evidence suggests there are fundamental limits to stability set by the data itself (noise, scarce labels, proxy objectives, and the many near-equivalent models a dataset admits). We conclude that instability should be treated as a standard evaluation axis in SE optimization, which should be routinely measured, reported alongside performance, and used to calibrate trust in any single run. The methods in this paper provide a baseline against which future efforts to reduce SBSE instability can be judged. To support open science, we offer the following reproduction package: https://tinyurl.com/Model-Instability

Amirali Rayegan, Lunxiao Li, Tim Menzies

North Carolina State University Raleigh, North Carolina, USA

Stochastic Optimization Automated Software Engineering ML Reproducibility Multi-Objective Optimization

Jul 11, 2026

MAGE: Understanding Stability-Performance Trade-offs in Multi-component Prompt Optimization

How do different components of iterative prompt optimization interact, and what happens when they are combined? We investigate this through MAGE (Memory-Augmented Goal-directed Prompt Evolution), a controlled analysis framework for studying component interaction in prompt optimization. MAGE is not proposed as a superior optimizer in absolute terms; it integrates episodic memory, multi-objective Pareto selection, and adaptive evaluation as a platform for controlled ablation. Our experiments uncover a previously unreported phenomenon, the Prompt Optimization Coupling Effect (POCE): when multiple stochastic optimization signals operate within a closed reflective loop, they interact in ways that simultaneously improve performance and amplify variance, behavior that cannot be predicted by analyzing components in isolation. Three main findings emerge. First, failure-grounded reflection is essential: methods relying only on scores (OPRO) or abstract critique (Self-Refine) fail to improve prompts. Second, MAGE achieves 46.4% versus GEPA's 34.0% on GSM8K-Hard (+12.4%, P(MAGE>GEPA)=0.998, 5 seeds on gpt-4o-mini), with comparable variance (7.3% vs. 7.0%). Third, increasing candidate diversity reveals the clearest POCE signal: expanding the candidate pool from n=3 to n=5 improves mean accuracy by +21.6% while increasing variance by 3.7x. We further validate on Llama 3.1 8B and show POCE is headroom-dependent: when the base model already achieves high accuracy, variance amplification disappears. Finally, in low-data regimes (Ntrain=30), well-designed fixed prompts outperform all reflective optimizers, indicating that scaffold choice dominates optimizer choice. Our results suggest prompt optimization systems behave as coupled stochastic processes and should be evaluated in terms of both performance and stability, not just peak accuracy.

Prateek Singh

Stochastic Optimization Large Language Model-Guided Optimization Automatic Prompt Optimization

Jul 11, 2026

How much Data do We Need? Sequential Data Collection for Stochastic Programming

Data-driven optimization often requires collecting data to estimate uncertain model parameters before solving the underlying decision problem. In practice, however, data acquisition may incur non-negligible costs, making it critical to determine when to stop additional data collection. In this paper, we study an optimal stopping problem for sequential data collection in stochastic optimization under parameter uncertainty. We propose a benefit-driven stopping framework that balances information gain and sampling cost. We model the unknown distribution parameter within a Bayesian learning framework and update beliefs sequentially as new observations are collected. At each iteration, the decision maker evaluates the expected marginal benefit of additional data relative to the unit sampling cost and determines whether to continue sampling or stop and implement the optimization decision. Based on this framework, we develop several stopping policies. The proposed policies are evaluated through a newsvendor problem with exponentially distributed demand. Numerical experiments compare the policies with fixed-budget and hindsight benchmark strategies. The results show that benefit-driven stopping rules can substantially reduce unnecessary data collection while achieving near-optimal decision performance, demonstrating the effectiveness of adaptive stopping in data-driven optimization.

Xin Li, Juergen Branke, Xuan Vinh Doan

University of Warwick

Stochastic Optimization Sequential Decision Making Optimal Stopping Adaptive Sampling

Jul 2, 2026

Decentralized Stochastic Subgradient-type Methods with Communication Compression for Nonsmooth Nonconvex Optimization

In this paper, we consider the nonsmooth nonconvex decentralized optimization problem, where inter-agent communication is compressed. We propose a general framework that unifies various decentralized stochastic subgradient-type methods with unbiased compression and contractive compression with error compensation. By relating the consensus-error iterates and the averaged iterates to the trajectories of continuous-time differential inclusions, we establish global convergence for all methods encompassed by our framework when the objective functions are nonsmooth and lack Clarke regularity. Based on our framework, we further develop several compression-based methods, including decentralized stochastic subgradient methods utilizing sign-based regularization and gradient-tracking momentum. Preliminary numerical experiments empirically support our theoretical results and highlight the communication-accuracy trade-off of the newly developed methods.

Siyuan Zhang, Nachuan Xiao, Xin Liu

Stochastic Optimization Nonconvex Optimization Stochastic Optimization Convergence Nonsmooth Convex Optimization Decentralized Optimization

Jun 28, 2026

Optimizer Memory Makes Shuffle Order a First-Order Source of Fine-Tuning Noise

Shuffle order can be a larger source of fine-tuning noise than a memoryless analysis predicts: fixed-clock optimizer memory makes local equal-multiset contrasts first order in the learning rate rather than second order, and the resulting order channel can be large enough for a single seed to flip a close A/B comparison. We isolate this mechanism and derive a fit-free way to size the noise it produces. For a memoryless optimizer, reordering an equal multiset has no first-order endpoint term; the leading local contrast is the

O(η^2)

gradient bracket. Fixed-clock optimizers such as AdamW are different. Their moment buffers, preconditioner state, and de-biasing counters advance with the step index rather than with the learning-rate-scaled time

τ=ηk

, so the same gradient can receive a position-dependent endpoint weight. For any fixed finite measurement window, a lifted-state expansion gives an

O(η)

equal-multiset contrast whenever the first-order replay coefficient is nonzero, while regular and clock-matched controls remain

O(η^2)

; a bare fixed-

β

momentum buffer is already enough. A bitwise-deterministic replay from one warmed optimizer state isolates the mechanism, giving order-variance slopes 1.83 for AdamW, 2.00 for fixed-

β

momentum, and 4.00 for SGD; matching the memory clock to

τ

restores the regular exponent. For AdamW with a frozen preconditioner, the same impulse-weight kernel gives a closed-form asymptotic order-variance floor after the local potentials are measured, with no fitted coefficients. The result is local to the measurement window (independent reshuffling can average the channel across windows), but it yields order-noise error bars, positional attribution weights, and a seed-budget criterion for fine-tuning comparisons.

John Sweeney

Stochastic Optimization Fine-Tuning Adaptive Gradient Methods

Jun 27, 2026

Analysis of Adam Algorithms for Stochastic Dynamic Systems

The adaptive moment estimation algorithm, known as Adam, is widely used in modern machine learning, owing to its low per-iteration complexity and strong empirical performance. Despite its prevalent use, the theoretical foundation of Adam remains largely unexplored for time-varying and nonstationary systems. In fact, the existing theoretical analyses of Adam-type algorithms are primarily concerned with time-invariant model parameters and explicitly or implicitly rely on independent and identically distributed (i.i.d.) data assumptions, under which the learning taskcan be formulated as minimizing a fixed expected objective with a static minimizer. However, such assumptions are often violated in time-varying and nonstationary systems, thereby calling for a theoretical investigation beyond the conventional yet idealized i.i.d. setting. The main objective of this paper is to solve this challenging problem by establishing a general theory of Adam for time-varying and nonstationary stochastic systems. We will introduce some new techniques for analyzing the products of nonstationary and dependent random matrices induced by Adam's coupled first- and second-moment recursions, and will construct a new stochastic Lyapunov function that blends these two moment dynamics. Under a stochastic excitation condition that allows nonstationary and dependent data, we will derive both parameter tracking and output prediction error bounds explicitly, quantifying the effects of stepsize, first- and second-momentum parameters, gradient noise and parameter drift. These bounds not only provide guarantees for Adam performance, but also provide guidelines for hyperparameter selection. Experiments on both synthetic and real-world data validate our theory and design guidelines.

Xin Zheng, Yifei Jin, Lei Guo

State Key Laboratory of Mathematical Sciences, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China · School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China · School of Advanced Interdisciplinary Sciences, University of Chinese Academy of Sciences, Beijing 101408, China

Stochastic Optimization Stochastic Optimization Convergence Adaptive Gradient Methods

Jun 25, 2026

Random Walk on Bézier Curves for Global Optimization

Balancing exploration and exploitation remains a central challenge in metaheuristic optimization. To address this issue, this paper proposes Bézier Walk Evolution (BWE), a geometry-driven optimization framework that reformulates evolutionary search as adaptive trajectory construction in the decision space. BWE integrates Bézier curve modeling with a distance-aware random walk mechanism to generate topology-guided search trajectories. By adaptively varying the curve order during evolution, the proposed method enables a smooth transition from diversified global exploration to refined local exploitation. Higher-order Bézier curves leverage multiple population-derived control points to enhance search diversity, while lower-order curves generate near-linear trajectories to improve convergence efficiency. This adaptive geometric search mechanism provides an interpretable alternative to conventional nature-inspired designs. Extensive experiments on 41 benchmark functions from the CEC2017 and CEC2022 suites, spanning dimensions from 10 to 100, show that BWE achieves strong overall performance and favorable scalability compared with 7 classical and 6 state-of-the-art optimizers, including L-SHADE and CMA-ES. Additional evaluations on five constrained engineering design problems further demonstrate the practical applicability and robustness of BWE.

Jinpeng Wang, Xingguo Xu, Yujing Sun +3

aSchool of Computer Science, Northwestern Polytechnical University, Xi’an, 710129, China · bSchool of Mathematical Sciences, Dalian University of Technology, Dalian, 116024, China · cSchool of Mathematics, Hefei University of Technology, Hefei, 230601, China +3

Stochastic Optimization Evolutionary Optimization Metaheuristic Optimization Global Optimization

Jun 24, 2026

High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependence

We study first-order methods for smooth objectives satisfying the Polyak-Łojasiewicz (PL) condition when gradient samples are generated by an exogenous Markov chain. In the light-tailed setting, prior uniform-in-time high-probability bounds for ordinary Stochastic Gradient Descent (SGD) under a standard growth envelope scale as

\widetilde{O}(t_{mix}^2/k)

, leaving a gap with the

\widetilde{O}(t_{mix}/k)

expectation bounds. We close this gap using a lag-blocking argument to establish a uniform high-probability guarantee with a leading stochastic term of

\widetilde{O}(t_{mix}/(k+K_0))

under geometric mixing. We prove this linear dependence on the mixing time is optimal via a matching

Ω(σ^2 t_{mix}/k)

lower bound on a quadratic objective driven by a persistent two-state chain. We then extend this framework to heavy-tailed Markovian gradients satisfying a stationary finite-

p

-moment condition,

p \in (1,2]

. We design an all-samples clipped block method that uses every Markov transition while mitigating Markovian bias. Under a transition budget

T

, this algorithm achieves a high-probability stochastic error of

\widetilde{O}(σ_p^2(t_{mix}/T)^{2(p-1)/p})

. We establish a matching lower bound by reducing PL optimization to heavy-tailed mean estimation for a sticky Markov chain. Ultimately, this work tightly characterizes the optimal polynomial dependence on mixing time for light-tailed PL-SGD, and the optimal heavy-tail exponent and effective-sample-size dependence in the robust regime.

Dhruv Sarkar, Aprameyo Chakrabartty, Vaneet Aggarwal

Indian Institute of Technology Kharagpur · Mohamed bin Zayed University of Artificial Intelligence · Purdue University

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

Jun 24, 2026

Is Variational Monte Carlo Robust? Sharp Moment Thresholds and Heavy-tailed Stochastic Optimization

Variational Monte Carlo (VMC) is a central algorithm in electronic structure theory and has gained renewed importance through modern neural-network ansätze such as FermiNet. At its core, VMC seeks ground states by minimizing the Rayleigh quotient by stochastic optimization. In this work, we show that the resulting stochastic optimization problem is intrinsically governed by the nodal geometry of the underlying wave function. More precisely, we establish that properties of the nodal set determine the integrability of the local energy and gradient estimators that drive VMC. For broad and practically relevant ansatz classes, including Slater-Jastrow wave functions with variable-exponent Slater-type orbitals, we prove that these estimators are generically heavy-tailed and fail to admit higher moments. At the same time, for general analytic ansätze, we prove weak moment bounds for the relevant estimators and identify precise low-moment regimes, showing how generic and degenerate nodal structures lead to different integrability thresholds. Building on this analysis, we introduce a new robust variant of VMC

\unicode{x2013}

coined PS-Clip-VMC

\unicode{x2013}

which is based on clipping both the local energy and the gradient random variable. We prove that PS-Clip-VMC converges both in expectation and with high probability in the weak moment regime of VMC. Preliminary experiments for training FermiNet on Atoms with up to 18 electrons suggest that PS-Clip-VMC is significantly more robust than standard methods.

Philipp Grohs, Davide Nobile

Faculty of Mathematics, University of Vienna · RICAM, Austrian Academy of Sciences

Stochastic Optimization Variational Monte Carlo Quantum Chemistry Quantum Many-Body Physics Heavy-Tailed Stochastic Optimization

Jun 24, 2026

Learning Optimization Proxies for Sequential Contextual Stochastic Programs: An Order Fulfillment Application

Sequential contextual stochastic programs model real-time decision systems in which each time epoch commits to an action under uncertainty whose consequences propagate into future decisions. In many practical contexts, these programs require obtaining solutions rapidly as new information becomes available. These problems can be represented through scenario approximations to be solved by off-the-shelf optimization solvers, which achieve high decision quality offline but typically run in seconds to minutes per instance, falling short of the sub-second responses that peak periods of planning require. This paper develops a learning-based optimization proxy: a scenario-embedded neural network trained offline on solver-generated labels, paired online with a decoder that enforces feasibility, replacing the per-epoch solve with a single forward pass. The framework is specialized to omnichannel order fulfillment, where each arriving order requires a sub-second assignment of products to distribution centers and carrier services under stochastic delivery times and future demand. A two-stage contextual stochastic program is introduced to formulate this problem, and its contextual sample average approximation (C-SAA) supplies the offline labels, while a composite training loss combines label imitation, a constraint-violation penalty, and self-supervised cost alignment. In a calibrated simulator built from JD.com transactional records, a detailed computational study is provided. The proxy reduces decision latency by roughly 2800x relative to the online finite-sample C-SAA reference and improves over it by 3.3% in realized fulfillment cost. Relative to established fulfillment policies, the proxy lowers total realized cost by at least 10.7% and roughly halves the late-delivery rate.

Tinghan Ye, Shuaicheng Tong, Changkun Guan +2

H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332 · Tippie College of Business, University of Iowa, Iowa City, IA 52242

Stochastic Optimization Learning to Optimize Supply Chain Management Supply Chain Optimization

Jun 23, 2026

New Bounds for the Last Iterate of the Stochastic subGradient Method

We study the last iterate of the stochastic subgradient method for one-dimensional convex Lipschitz objectives. For a fixed horizon

n

, we consider the standard fixed stepsizes

η=Θ(1/\sqrt n)

. We prove that, for such stepsize policies, under additive i.i.d. subgradient noise with uniformly bounded variance, the last iterate features an optimization error of order

1/\sqrt n

, thereby removing the extra

(\log n)

factor present in existing generic bounds. On the other hand, we show that without the i.i.d. assumption, the optimization error can be of order

(\log n)/\sqrt n

. Thus, under the uniformly bounded variance assumption alone, the last iterate of SsGM is suboptimal even in dimension one, resolving negatively an open problem posed in Koren and Segal, COLT, 2020.

Guglielmo Beretta, Tommaso Cesari, Roberto Colomboni +1

Department of Computer Science, Aarhus University, Aarhus, Denmark · School of Electrical Engineering and Computer Science, University of Ottawa, Ottawa, Canada · School of Mathematics, University of Bristol, Bristol, United Kingdom

Stochastic Optimization Last-Iterate Convergence Convergence Analysis Stochastic Optimization Convergence Nonsmooth Convex Optimization

Jun 22, 2026

Open Problem: Is AdamW Effective Under Heavy-Tailed Noise?

AdamW is the de facto optimizer for training large language models (LLMs), yet the theory behind it still lives mostly in finite-variance regimes. This is increasingly unsatisfying, as empirical evidence indicates that stochastic gradient noise in LLM pretraining is typically heavy-tailed. Recent work shows that sign-based optimizers such as Lion and Muon achieve sharp heavy-tailed rates, and that AdaGrad can also converge under heavy-tailed noise. However, no rigorous convergence theory for AdamW has yet been established in this regime. Can AdamW converge under the same heavy-tailed assumptions, or does its second-moment accumulator create a genuine obstruction? We formulate this as an open problem, prove a positive weighted-metric benchmark, and give a corridor lower-bound mechanism showing how denominator memory can hide large gradients.

Dingzhi Yu, Hongyi Tao, Yuanyu Wan +2

1Nanjing University · 2Zhejiang University · 3Fudan University

Stochastic Optimization Heavy-Tailed Noise Stochastic Optimization Convergence Heavy-Tailed Distributions Adaptive Gradient Methods Heavy-Tailed Stochastic Optimization

Jun 21, 2026

Clipping the Price of Adaptivity at the Tail

Adaptive stochastic convex optimization (SCO) methods face a fundamental ``price of adaptivity'' barrier: under the standard set of assumptions, they cannot efficiently adapt to large uncertainty in both the initial distance to optimality and the Lipschitz constant. We circumvent this barrier by requiring a small amount of additional structure common to many learning problems. Specifically, we assume that the objective decomposes into a model and a loss function, enabling us to intervene by modifying the model's output before it passes to the loss function. Under this assumption, we design a method that clips the learned model output in tail events where it deviates too much from the output of a fixed reference model. Our method matches the optimal bounds for known-parameter SCO up to logarithmic factors in the uncertainty in the distance and Lipschitz parameters, thus efficiently adapting to large uncertainty in both.

Itai Kreisler, Yair Carmon, Oliver Hinder

Tel Aviv University · University of Pittsburgh

Stochastic Optimization Stochastic Optimization Convergence

Jun 21, 2026

Federated learning with heavy-tailed gradient noise and communication noise: a variance-reduction based algorithm

Federated learning (FL) is an emerging distributed machine learning paradigm that enables local devices to jointly train a global model while keeping data decentralized and private. We propose a variance-reduction based algorithm, VRA-FedSGD, for FL in the presence of heavy-tailed gradient noise and communication noise, where these noises are prevalent in large-scale machine learning over wireless networks and Internet of Things deployments. VRA-FedSGD employs a momentum variance reduction technique together with a nonlinear mapping to mitigate heavy-tailed gradient noise, and uses a variance-reduced aggregation mechanism to suppress heavy-tailed communication noise. In the mean sense, VRA-FedSGD achieves a convergence rate of {\small

\mathcal{O}\left(K^{-(p-1)/(2p-1)}\right)

} for nonconvex objective functions, where

p

is the tail index of heavy-tailed noise. In the almost sure sense, VRA-FedSGD achieves a convergence rate of

\tilde{\mathcal{O}}\left(K^{-(1-1/(p-ε))}\right)

for strongly convex objective functions, where

ε

is an arbitrarily small constant. Simulated experiments on a logistic regression problem with real-world data verify the effectiveness of VRA-FedSGD.

Shengchao Zhao, Yongchao Liu

School of Mathematics, China University of Mining and Technology, Xuzhou, China · School of Mathematical Sciences, Dalian University of Technology, Dalian, China

Stochastic Optimization Nonconvex Stochastic Optimization Heavy-Tailed Noise Variance Reduction Heavy-Tailed Stochastic Optimization Federated Learning

Jun 21, 2026

Distribution-Aware Robust Bilevel Optimization: Quantile-Guided Huber Updates in Two-Timescale Stochastic Approximation

Bilevel optimization (BLO) is fundamental to hierarchical decision-making but suffers from critical instability under heavy-tailed stochastic noise. Existing variance-reduction techniques typically rely on myopic magnitude checks, which fail to distinguish informative geometric signals from impulsive outliers. To resolve this, we propose RQ-TTSA (Robust Quantile-guided TTSA), a distribution-aware framework that leverages historical gradient buffers to estimate rolling quantiles for adaptive Huber-style clipping, effectively preserving local optimization geometry while strictly bounding effective variance. Theoretically, we provide a convergence analysis for quantile-guided TTSA under nonconvex-strongly convex assumptions with infinite-variance noise (

p \in (1,2]

), deriving a rate of

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

that recovers optimal dependence on the heavy-tailed parameter. Empirically, across six diverse tasks, spanning heterogeneous vision benchmarks, dynamic games under momentum poisoning, and offline reinforcement learning, RQ-TTSA consistently outperforms state-of-the-art baselines by eliminating divergence spikes and ensuring stable convergence. Our method demonstrates significant robustness to hyperparameter variations and incurs negligible computational overhead (

\approx 2.7\%

increase), validating distribution-aware gradient control as a practical and necessary component for reliable bilevel learning.

Zhiyu Li, Xi Xuan, Davide Carbone

University of Science and Technology of China Hefei, China · City University of Hong Kong Hong Kong SAR, China · Laboratoire de Physique de l’École Normale Supérieure, Université PSL, CNRS, Sorbonne Université, Université de Paris Paris, France

Stochastic Optimization Stochastic Approximation Bilevel Optimization Two-Timescale Stochastic Approximation Heavy-Tailed Stochastic Optimization Stochastic Bilevel Optimization