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.

Apr 17, 2026

Stein Variational Black-Box Combinatorial Optimization

Combinatorial black-box optimization in high-dimensional settings demands a careful trade-off between exploiting promising regions of the search space and preserving sufficient exploration to identify multiple optima. Although Estimation-of-Distribution Algorithms (EDAs) provide a powerful model-based framework, they often concentrate on a single region of interest, which may result in premature convergence when facing complex or multimodal objective landscapes. In this work, we incorporate the Stein operator to introduce a repulsive mechanism among particles in the parameter space, thereby encouraging the population to disperse and jointly explore several modes of the fitness landscape. Empirical evaluations across diverse benchmark problems show that the proposed method achieves performance competitive with, and in several cases superior to, leading state-of-the-art approaches, particularly on large-scale instances. These findings highlight the potential of Stein variational gradient descent as a promising direction for addressing large, computationally expensive, discrete black-box optimization problems.

Thomas Landais, Olivier Goudet, Adrien Goëffon +2

LERIA, Université d’Angers, 2 Boulevard Lavoisier, Angers 49045, France

Stochastic Optimization Black-Box Optimization Combinatorial Optimization Multimodal Optimization Stein Variational Gradient Descent

Apr 16, 2026

StoSignSGD: Unbiased Structural Stochasticity Fixes SignSGD for Training Large Language Models

Sign-based optimization algorithms, such as SignSGD, have garnered significant attention for their remarkable performance in distributed learning and training large foundation models. Despite their empirical superiority, SignSGD is known to diverge on non-smooth objectives, which are ubiquitous in modern machine learning due to ReLUs, max-pools, and mixture-of-experts. To overcome this fundamental limitation, we propose StoSignSGD, an algorithm that injects structural stochasticity into the sign operator while maintaining an unbiased update step. In the regime of (online) convex optimization, our theoretical analysis shows that StoSignSGD rigorously resolves the non-convergence issues of SignSGD, achieving a sharp convergence rate matching the lower bound. For the more challenging non-convex non-smooth optimization, we introduce generalized stationary measures that encompass prior definitions, proving that StoSignSGD improves upon the best-known complexity bounds by dimensional factors. Empirically, StoSignSGD exhibits robust stability and superior efficiency across diverse large language model (LLM) training regimes. Notably, in low-precision FP8 pretraining -- a setting where AdamW fails catastrophically -- StoSignSGD remains highly stable and yields a remarkable 1.44

\times

to 2.14

\times

speedup relative to established baselines. Furthermore, when fine-tuning 7B LLMs on mathematical reasoning tasks, StoSignSGD delivers substantial performance gains over both AdamW and SignSGD. Finally, to dissect the mechanisms driving its success, we develop a sign conversion framework capable of transforming any general optimizer into its unbiased, sign-based counterpart. Utilizing this framework, we deconstruct the core components of StoSignSGD and present a comprehensive ablation study to empirically validate our algorithmic design choices.

Dingzhi Yu, Rui Pan, Yuxing Liu +1

University of Illinois Urbana-Champaign

Stochastic Optimization Sign-Based Optimization Nonconvex Stochastic Optimization Stochastic Optimization Convergence LLM Training

Apr 16, 2026

CLion: Efficient Cautious Lion Optimizer with Enhanced Generalization

Lion optimizer is a popular learning-based optimization algorithm in machine learning, which shows impressive performance in training many deep learning models. Although convergence property of the Lion optimizer has been studied, its generalization analysis is still missing. To fill this gap, we study generalization property of the Lion via algorithmic stability based on the mathematical induction. Specifically, we prove that the Lion has a generalization error of

O(\frac{1}{Nτ^T})

, where

N

is training sample size, and

τ>0

denotes the smallest absolute value of non-zero element in gradient estimator, and

T

is the total iteration number. In addition, we obtain an interesting byproduct that the SignSGD algorithm has the same generalization error as the Lion. To enhance generalization of the Lion, we design a novel efficient Cautious Lion (i.e., CLion) optimizer by cautiously using sign function. Moreover, we prove that our CLion has a lower generalization error of

O(\frac{1}{N})

than

O(\frac{1}{Nτ^T})

of the Lion, since the parameter

τ

generally is very small. Meanwhile, we study convergence property of our CLion optimizer, and prove that our CLion has a fast convergence rate of

O(\frac{\sqrt{d}}{T^{1/4}})

under

\ell_1

-norm of gradient for nonconvex stochastic optimization, where

d

denotes the model dimension. Extensive numerical experiments demonstrate effectiveness of our CLion optimizer.

Feihu Huang, Guanyi Zhang, Songcan Chen

College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing, China · MIIT Key Laboratory of Pattern Analysis and Machine Intelligence, Nanjing, China

Stochastic Optimization Sign-Based Optimization Neural Network Generalization Deep Learning Optimization Nonconvex Stochastic Optimization

Apr 15, 2026

Multistage Conditional Compositional Optimization

We introduce Multistage Conditional Compositional Optimization (MCCO) as a new paradigm for decision-making under uncertainty that combines aspects of multistage stochastic programming and conditional stochastic optimization. MCCO minimizes a nest of conditional expectations and nonlinear cost functions. It has numerous applications and arises, for example, in optimal stopping, linear-quadratic regulator problems, distributionally robust contextual bandits, as well as in problems involving dynamic risk measures. The naïve nested sampling approach for MCCO suffers from the curse of dimensionality familiar from scenario tree-based multistage stochastic programming, that is, its scenario complexity grows exponentially with the number of nests. We develop new multilevel Monte Carlo techniques for MCCO whose scenario complexity grows only polynomially with the desired accuracy.

Buse Şen, Yifan Hu, Daniel Kuhn

EPFL, Switzerland · Rutgers University, USA

Stochastic Optimization Decision-Making under Uncertainty

Apr 15, 2026

Greedy Approaches for Packing While Travelling with Deterministic and Stochastic Constraints

The travelling thief problem (TTP) is a well-known multi-component optimisation problem that captures the interdependence between two components: the tour across cities and the packing of items. The packing while travelling problem (PWT) is an NP-hard subproblem of TTP where the packing of items should be optimised for a given fixed tour. In many solvers, the packing component is often addressed using greedy heuristics. Here, the use of suitable greedy functions is essential for the success of greedy algorithms. In this paper, we introduce new reward functions tailored to the PWT and extend them to a hyper-heuristic framework to achieve further advantage. Furthermore, we investigate the chance constrained PWT for greedy approaches and adopt the newly introduced reward functions for stochastic weights. The experimental results clearly demonstrate the benefit of the tailored heuristics over the standard heuristics in both deterministic and stochastic constraints.

Thilina Pathirage Don, Aneta Neumann, Frank Neumann

Optimisation and Logistics, School of Computer Science and Information Technology, Adelaide University, Adelaide, Australia

Greedy Optimization Combinatorial Optimization Metaheuristic Optimization Stochastic Optimization Chance-Constrained Optimization

Apr 15, 2026

On the use of evolutionary optimization for the dynamic chance constrained open-pit mine scheduling problem

Open-pit mine scheduling is a complex real-world optimization problem that involves uncertain economic values and dynamically changing resource capacities. Evolutionary algorithms are particularly effective in these scenarios, as they can easily adapt to uncertain and changing environments. However, uncertainty and dynamic changes are often studied in isolation in real-world problems. In this paper, we study a dynamic chance-constrained open-pit mine scheduling problem in which block economic values are stochastic and mining and processing capacities vary over time. We adopt a bi-objective evolutionary formulation that simultaneously maximizes expected discounted profit and minimizes its standard deviation. To address dynamic changes, we propose a diversity-based change response mechanism that repairs a subset of infeasible solutions and introduces additional feasible solutions whenever a change is detected. We evaluate the effectiveness of this mechanism across four multi-objective evolutionary algorithms and compare it with a baseline re-evaluation-based change-response strategy. Experimental results on six mining instances demonstrate that the proposed approach consistently outperforms the baseline methods across different uncertainty levels and change frequencies.

Ishara Hewa Pathiranage, Aneta Neumann

Machine Learning and Optimisation, School of Computer Science and Information Technology, Adelaide University, Adelaide, Australia

Stochastic Optimization Chance-Constrained Optimization Multi-Objective Evolutionary Optimization

Apr 14, 2026

Classical and Quantum Speedups for Non-Convex Optimization via Energy Conserving Descent

We present the first analytical study of ECD, focusing on the one-dimensional setting for this first installment. We formalize a stochastic ECD dynamics (sECD) with energy-preserving noise, as well as a quantum analog of the ECD Hamiltonian (qECD), providing the foundation for a quantum algorithm through Hamiltonian simulation in a tractable model where the barrier-crossing mechanism can be computed explicitly. For one-dimensional double-well objectives in the under-guessing regime, we compute the expected dynamical hitting times from a local minimum to the global minimum. We prove that both sECD and qECD exhibit exponential improvements in continuous hitting time relative to their respective gradient-based baselines, stochastic gradient descent (SGD) and quantum tunneling walk (QTW). For objectives with tall barriers, qECD admits a further hitting time improvement over sECD. Mechanistically, ECD sidesteps the exponential cost associated with rare-escape events of SGD from local minima by moving from dissipative to energy-conserving dynamics.

Yihang Sun, Huaijin Wang, Patrick Hayden +1

Department of Management Science and Engineering, Stanford University. · Leinweber Institute for Theoretical Physics, Stanford University. · Leinweber Institute for Theoretical Physics, Stanford University and Google DeepMind.

Nonconvex Optimization Global Optimization Stochastic Optimization

Apr 13, 2026

Obtaining Partition Crossover masks using Statistical Linkage Learning for solving noised optimization problems with hidden variable dependency structure

In optimization problems, some variable subsets may have a joint non-linear or non-monotonical influence on the function value. Therefore, knowledge of variable dependencies may be crucial for effective optimization, and many state-of-the-art optimizers leverage it to improve performance. However, some real-world problem instances may be the subject of noise of various origins. In such a case, variable dependencies relevant to optimization may be hard or impossible to tell using dependency checks sufficient for problems without noise, making highly effective operators, e.g., Partition Crossover (PX), useless. Therefore, we use Statistical Linkage Learning (SLL) to decompose problems with noise and propose a new SLL-dedicated mask construction algorithm. We prove that if the quality of the SLL-based decomposition is sufficiently high, the proposed clustering algorithm yields masks equivalent to PX masks for the noise-free instances. The experiments show that the optimizer using the proposed mechanisms remains equally effective despite the noise level and outperforms state-of-the-art optimizers for the problems with high noise.

M. W. Przewozniczek, B. Frej, M. M. Komarnicki +2

Wroclaw Univ. of Science and Techn. Wroclaw, Poland · University of São Paulo Ribeirão Preto, Brazil

Evolutionary Optimization Black-Box Optimization Stochastic Optimization

Apr 10, 2026

Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size

We study last-iterate convergence of SGD with greedy step size over smooth quadratics in the interpolation regime, a setting which captures the classical Randomized Kaczmarz algorithm as well as other popular iterative linear system solvers. For these methods, we show that the

t

-th iterate attains an

O(1/t^{3/4})

convergence rate, addressing a question posed by Attia, Schliserman, Sherman, and Koren, who gave an

O(1/t^{1/2})

guarantee for this setting. In the proof, we introduce the family of stochastic contraction processes, whose behavior can be described by the evolution of a certain deterministic eigenvalue equation, which we analyze via a careful discrete-to-continuous reduction.

Michał Dereziński, Xiaoyu Dong

University of Michigan · National University of Singapore

Last-Iterate Convergence Stochastic Optimization Stochastic Gradient Descent

Apr 10, 2026

Offline Local Search for Online Stochastic Bandits

Combinatorial multi-armed bandits provide a fundamental online decision-making environment where a decision-maker interacts with an environment across

T

time steps, each time selecting an action and learning the cost of that action. The goal is to minimize regret, defined as the loss compared to the optimal fixed action in hindsight under full-information. There has been substantial interest in leveraging what is known about offline algorithm design in this online setting. Offline greedy and linear optimization algorithms (both exact and approximate) have been shown to provide useful guarantees when deployed online. We investigate local search methods, a broad class of algorithms used widely in both theory and practice, which have thus far been under-explored in this context. We focus on problems where offline local search terminates in an approximately optimal solution and give a generic method for converting such an offline algorithm into an online stochastic combinatorial bandit algorithm with

O(\log^3 T)

(approximate) regret. In contrast, existing offline-to-online frameworks yield regret (and approximate regret) which depend sub-linearly, but polynomially on

T

. We demonstrate the flexibility of our framework by applying it to three online stochastic combinatorial optimization problems: scheduling to minimize total completion time, finding a minimum cost base of a matroid and uncertain clustering.

Gerdus Benadè, Rathish Das, Thomas Lavastida

Boston University, MA, USA. · University of Houston, TX, USA. · University of Texas at Dallas, TX, USA.

Combinatorial Multi-Armed Bandits Stochastic Optimization Local Search

Apr 9, 2026

Analysis of Search Heuristics in the Multi-Armed Bandit Setting

We consider the classic Multi-Armed Bandit setting to understand the exploration/exploitation tradeoffs made by different search heuristics. Since many search heuristics work by comparing different options (in evolutionary algorithms called "individuals"; in the Bandit literature called "arms"), we work with the "Dueling Bandits" setting. In each iteration, a comparison between different arms can be made; in the binary stochastic setting, each arm has a fixed winning probability against any other arm. A Condorcet winner is any arm that beats every other arm with a probability strictly higher than

1/2

. We show that evolutionary algorithms are rather bad at identifying the Condorcet winner: Even if the Condorcet winner beats every other arm with a probability

1-p

, the (1+1) EA, in its stationary distribution, chooses the Condorcet winner only with constant probability if

p=Ω(1/n)

. By contrast, we show that a simple EDA (based on the Max-Min Ant System with iteration-best update) will choose the Condorcet winner in its maintained distribution with probability

1-Θ(p)

. As a remedy for the (1+1) EA, we show how repeated duels can significantly boost the probability of the Condorcet winner in the stationary distribution.

Jasmin Brandt, Barbara Hammer, Timo Kötzing +1

University of Bielefeld Bielefeld, Germany · Hasso Plattner Institute University of Potsdam Potsdam, Germany

Dueling Bandits Multi-Armed Bandits Exploration-Exploitation Tradeoff Stochastic Optimization Evolutionary Optimization

Apr 8, 2026

Anytime Analysis on BinVal: Adaptive Parameters Help

While most theoretical run time analyses of discrete randomized search heuristics provide bounds on the expected number of evaluations to find the global optimum, we consider the anytime performance of evolutionary and estimation-of-distribution algorithms. For this purpose, we analyze the fixed-target run time of various algorithms using BinVal as fitness function and bound the run time to optimize the most significant

k \in o(n)

bits of a bit string with length

n

. We analyze the run times such that they hold not only for a fixed

k

, but simultaneously for all

k \in o(n)

. For the standard (1+1) EA with fixed mutation rate

1/n

, we show that the fixed-target run time for all

k \in o(n)

is in

Θ(n \log k)

. Using an EDA instead, we get an expected number of evaluations of

Θ(k \log n)

for the sig-cGA. Replacing in the standard (1+1) EA the fixed mutation rate with a self-adjusting rate, we show that the fixed-target run time for

k \in o(n)

and a constant

\varepsilon >0

arbitrarily close to zero is in

\mathcal{O}\left(k^{1+\varepsilon}\right)

for this algorithm. In particular, this run time is independent of

n

, holds simultaneously for all

k \in o(n)

, and is close to the run time of

Θ(k \log k)

for the (1+1) EA with the best fixed mutation rate if

k

is known.

Timo Kötzing, Jurek Sander

Hasso Plattner Institute University of Potsdam Potsdam, Germany

Runtime Analysis of Evolutionary Algorithms Evolutionary Optimization Stochastic Optimization

Apr 7, 2026

Stochastic Auto-conditioned Fast Gradient Methods with Optimal Rates

Achieving optimal rates for stochastic composite convex optimization without prior knowledge of problem parameters remains a central challenge. In the deterministic setting, the auto-conditioned fast gradient method has recently been proposed to attain optimal accelerated rates without line-search procedures or prior knowledge of the Lipschitz smoothness constant, providing a natural prototype for parameter-free acceleration. However, extending this approach to the stochastic setting has proven technically challenging and remains open. Existing parameter-free stochastic methods either fail to achieve accelerated rates or rely on restrictive assumptions, such as bounded domains, bounded gradients, prior knowledge of the iteration horizon, or strictly sub-Gaussian noise. To address these limitations, we propose a stochastic variant of the auto-conditioned fast gradient method, referred to as stochastic AC-FGM. The proposed method is fully adaptive to the Lipschitz constant, the iteration horizon, and the noise level, enabling both adaptive stepsize selection and adaptive mini-batch sizing without line-search procedures. Under standard bounded conditional variance assumptions, we show that stochastic AC-FGM achieves the optimal iteration complexity of

O(1/\sqrt{\varepsilon})

and the optimal sample complexity of

O(1/\varepsilon^2)

.

Yao Ji, Guanghui Lan

H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, 225 North Ave, Atlanta, GA 30332, USA

Stochastic Optimization Accelerated Gradient Methods

Apr 6, 2026

Optimizing Service Operations via LLM-Powered Multi-Agent Simulation

Service system performance depends on how participants respond to design choices, but modeling these responses is hard due to the complexity of human behavior. We introduce an LLM-powered multi-agent simulation (LLM-MAS) framework for optimizing service operations. We pose the problem as stochastic optimization with decision-dependent uncertainty: design choices are embedded in prompts and shape the distribution of outcomes from interacting LLM-powered agents. By embedding key numerical information in prompts and extracting it from LLM-generated text, we model this uncertainty as a controlled Markov chain. We develop an on-trajectory learning algorithm that, on a single simulation run, simultaneously constructs zeroth-order gradient estimates and updates design parameters to optimize steady-state performance. We also incorporate variance reduction techniques. In a sustainable supply chain application, our method outperforms benchmarks, including blackbox optimization and using LLMs as numerical solvers or as role-playing system designers. A case study on optimal contest design with real behavioral data shows that LLM-MAS is both as a cost-effective evaluator of known designs and an exploratory tool that can uncover strong designs overlooked by traditional approaches.

Yanyuan Wang, Xiaowei Zhang

Department of Industrial Engineering and Decision Analytics, The Hong Kong University of Science and Technology, Clear Water Bay, Hong Kong SAR

Stochastic Optimization Decision-Making under Uncertainty Multi-Agent LLM Systems Large Language Model-Based Social Simulation Zeroth-Order Optimization

Mar 31, 2026

Finite-time analysis of Multi-timescale Stochastic Optimization Algorithms

We present a finite-time analysis of two smoothed functional stochastic approximation algorithms for simulation-based optimization. The first is a two time-scale gradient-based method, while the second is a three time-scale Newton-based algorithm that estimates both the gradient and the Hessian of the objective function

J

. Both algorithms involve zeroth order estimates for the gradient/Hessian. Although the asymptotic convergence of these algorithms has been established in prior work, finite-time guarantees of two-timescale stochastic optimization algorithms in zeroth order settings have not been provided previously. For our Newton algorithm, we derive mean-squared error bounds for the Hessian estimator and establish a finite-time bound on

\min\limits_{0 \le m \le T} \mathbb{E}\| \nabla J(θ(m)) \|^2

, showing convergence to first-order stationary points. The analysis explicitly characterizes the interaction between multiple time-scales and the propagation of estimation errors. We further identify step-size choices that balance dominant error terms and achieve near-optimal convergence rates. We also provide corresponding finite-time guarantees for the gradient algorithm under the same framework. The theoretical results are further validated through experiments on the Continuous Mountain Car environment.

Kaustubh Kartikey, Shalabh Bhatnagar

Stochastic Optimization Stochastic Optimization Convergence Two-Timescale Stochastic Approximation Second-Order Optimization Zeroth-Order Optimization

Mar 25, 2026

Adaptive decision-making for stochastic service network design

This paper addresses the Service Network Design (SND) problem for a logistics service provider (LSP) operating in a multimodal freight transport network, considering uncertain travel times and limited truck fleet availability. A two-stage optimization approach is proposed, which combines metaheuristics, simulation and machine learning components. This solution framework integrates tactical decisions, such as transport request acceptance and capacity booking for scheduled services, with operational decisions, including dynamic truck allocation, routing, and re-planning in response to disruptions. A simulated annealing (SA) metaheuristic is employed to solve the tactical problem, supported by an adaptive surrogate model trained using a discrete-event simulation model that captures operational complexities and cascading effects of uncertain travel times. The performance of the proposed method is evaluated using benchmark instances. First, the SA is tested on a deterministic version of the problem and compared to state-of-the-art results, demonstrating it can improve the solution quality and significantly reduce the computational time. Then, the proposed SA is applied to the more complex stochastic problem. Compared to a benchmark algorithm that executes a full simulation for each solution evaluation, the learning-based SA generates high quality solutions while significantly reducing computational effort, achieving only a 5% difference in objective function value while cutting computation time by up to 20 times. These results demonstrate the strong performance of the proposed algorithm in solving complex versions of the SND. Moreover, they highlight the effectiveness of integrating diverse modeling and optimization techniques, and the potential of such approaches to efficiently address freight transport planning challenges.

Javier Durán-Micco, Bilge Atasoy

Maritime and Transport Technology (MTT), Mechanical Engineering (ME), Delft University of Technology/ Mekelweg 2, 2628CD, Delft, The Netherlands.

Stochastic Optimization Metaheuristic Optimization Surrogate-Assisted Optimization

Mar 22, 2026

On the Role of Batch Size in Stochastic Conditional Gradient Methods

We study the role of batch size in stochastic conditional gradient methods under a

μ

-Kurdyka-Łojasiewicz (

μ

-KL) condition. Focusing on momentum-based stochastic conditional gradient algorithms (e.g., Scion), we derive a new analysis that explicitly captures the interaction between stepsize, batch size, and stochastic noise. Our study reveals a regime-dependent behavior: increasing the batch size initially improves optimization accuracy but, beyond a critical threshold, the benefits saturate and can eventually degrade performance under a fixed token budget. Notably, the theory predicts the magnitude of the optimal stepsize and aligns well with empirical practices observed in large-scale training. Leveraging these insights, we derive principled guidelines for selecting the batch size and stepsize, and propose an adaptive strategy that increases batch size and sequence length during training while preserving convergence guarantees. Experiments on NanoGPT are consistent with the theoretical predictions and illustrate the emergence of the predicted scaling regimes. Overall, our results provide a theoretical framework for understanding batch size scaling in stochastic conditional gradient methods and offer guidance for designing efficient training schedules in large-scale optimization.

Rustem Islamov, Roman Machacek, Aurelien Lucchi +3

University of Basel, Switzerland · MBZUAI, UAE · University of Bern, Switzerland +2

Stochastic Optimization Neural Network Optimization Stochastic Optimization Convergence

Mar 19, 2026

Uniform a priori bounds and error analysis for the Adam stochastic gradient descent optimization method

The adaptive moment estimation (Adam) optimizer proposed by Kingma & Ba (2014) is presumably the most popular stochastic gradient descent (SGD) optimization method for the training of deep neural networks (DNNs) in artificial intelligence (AI) systems. Despite its groundbreaking success in the training of AI systems, it still remains an open research problem to provide a complete error analysis of Adam, not only for optimizing DNNs but even when applied to strongly convex stochastic optimization problems (SOPs). Previous error analysis results for strongly convex SOPs in the literature provide conditional convergence analyses that rely on the assumption that Adam does not diverge to infinity but remains uniformly bounded. It is the key contribution of this work to establish uniform a priori bounds for Adam and, thereby, to provide -- for the first time -- an unconditional error analysis for Adam for a large class of strongly convex SOPs.

Steffen Dereich, Thang Do, Arnulf Jentzen

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

Stochastic Optimization Stochastic Optimization Convergence Adaptive Gradient Methods Stochastic Gradient Descent

Mar 18, 2026

Stochastic set-valued optimization and its application to robust learning

In this paper, we develop a stochastic set-valued optimization (SVO) framework tailored for robust machine learning. In the SVO setting, each decision variable is mapped to a set of objective values, and optimality is defined via set relations. We focus on SVO problems with hyperbox sets, which can be reformulated as multi-objective optimization (MOO) problems with finitely many objectives and serve as a foundation for representing or approximating more general mapped sets. Two special cases of hyperbox-valued optimization (HVO) are interval-valued (IVO) and rectangle-valued (RVO) optimization. We construct stochastic IVO/RVO formulations that incorporate subquantiles and superquantiles into the objective functions of the MOO reformulations, providing a new characterization for subquantiles. These formulations provide interpretable trade-offs by capturing both lower- and upper-tail behaviors of loss distributions, thereby going beyond standard empirical risk minimization and classical robust models. To solve the resulting multi-objective problems, we adopt stochastic multi-gradient algorithms and select a Pareto knee solution. In numerical experiments, the proposed algorithms with this selection strategy exhibit improved robustness and reduced variability across test replications under distributional shift compared with empirical risk minimization, while maintaining competitive accuracy.

Tommaso Giovannelli, Jingfu Tan, Luis Nunes Vicente

Department of Mechanical and Materials Engineering, University of Cincinnati, Cincinnati, OH 45221, USA · Department of Industrial and Systems Engineering, Lehigh University, Bethlehem, PA 18015-1582, USA

Stochastic Optimization Distribution Shift Robustness Multi-Objective Optimization

Mar 17, 2026

Shuffling the Stochastic Mirror Descent via Dual Lipschitz Continuity and Kernel Conditioning

The global Lipschitz smoothness condition underlies most convergence and complexity analyses via two key consequences: the descent lemma and the gradient Lipschitz continuity. How to study the performance of optimization algorithms in the absence of Lipschitz smoothness remains an active area. The relative smoothness framework from Bauschke-Bolte-Teboulle (2017) and Lu-Freund-Nesterov (2018) provides an extended descent lemma, ensuring convergence of Bregman-based proximal gradient methods and their vanilla stochastic counterparts. However, many widely used techniques (e.g., momentum schemes, random reshuffling, and variance reduction) additionally require the Lipschitz-type bound for gradient deviations, leaving their analysis under relative smoothness an open area. To resolve this issue, we introduce the dual kernel conditioning (DKC) regularity condition to regulate the local relative curvature of the kernel functions. Combined with the relative smoothness, DKC provides a dual Lipschitz continuity for gradients: even though the gradient mapping is not Lipschitz in the primal space, it preserves Lipschitz continuity in the dual space induced by a mirror map. We verify that DKC is widely satisfied by popular kernels and is closed under affine composition and conic combination. With these novel tools, we establish the first complexity bounds as well as the iterate convergence of random reshuffling mirror descent for constrained nonconvex relative smooth problems.

Junwen Qiu, Leilei Mei, Junyu Zhang

Industrial Systems Engineering and Management, National University of Singapore

Random Reshuffling Stochastic Optimization Stochastic Optimization Convergence Nonconvex Optimization

Mar 16, 2026

Unbiased and Biased Variance-Reduced Forward-Reflected-Backward Splitting Methods for Stochastic Composite Inclusions

This paper develops new variance-reduction techniques for the forward-reflected-backward splitting (FRBS) method to solve a class of possibly nonmonotone stochastic composite inclusions. Unlike unbiased estimators such as mini-batching, developing stochastic biased variants faces a fundamental technical challenge and has not been utilized before for inclusions and fixed-point problems. We fill this gap by designing a new framework that can handle both unbiased and biased estimators. Our main idea is to construct stochastic variance-reduced estimators for the forward-reflected direction and use them to perform iterate updates. First, we propose a class of unbiased variance-reduced estimators and show that increasing mini-batch SGD, loopless-SVRG, and SAGA estimators fall within this class. For these unbiased estimators, we establish a

\mathcal{O}(1/k)

best-iterate convergence rate for the expected squared residual norm, together with almost-sure convergence of the iterate sequence to a solution. Consequently, we prove that the best oracle complexities for the

n

-finite-sum and expectation settings are

\mathcal{O}(n^{2/3}ε^{-2})

and

\mathcal{O}(ε^{-10/3})

, respectively, when employing loopless-SVRG or SAGA, where

ε

is a desired accuracy. Second, we introduce a new class of biased variance-reduced estimators for the forward-reflected direction, which includes SARAH, Hybrid SGD, and Hybrid SVRG as special instances. While the convergence rates remain valid for these biased estimators, the resulting oracle complexities are

\mathcal{O}(n^{3/4}ε^{-2})

and

\mathcal{O}(ε^{-5})

for the

n

-finite-sum and expectation settings, respectively. Finally, we conduct two numerical experiments on AUC optimization for imbalanced classification and policy evaluation in reinforcement learning.

Quoc Tran-Dinh, Nghia Nguyen-Trung

Department of Statistics and Operations Research The University of North Carolina at Chapel Hill 318 Hanes Hall, UNC-Chapel Hill, NC 27599-3260.

Stochastic Optimization Stochastic Optimization Convergence Variance Reduction

Mar 16, 2026

POLCA: Stochastic Generative Optimization with LLM

Optimizing complex systems, ranging from LLM prompts to multi-turn agents, traditionally requires labor-intensive manual iteration. We formalize this challenge as a stochastic generative optimization problem where a generative language model acts as the optimizer, guided by numerical rewards and text feedback to discover the best system. We introduce Prioritized Optimization with Local Contextual Aggregation (POLCA), a scalable framework designed to handle stochasticity in optimization -- such as noisy feedback, sampling minibatches, and stochastic system behaviors -- while effectively managing the unconstrained expansion of solution space. POLCA maintains a priority queue to manage the exploration-exploitation tradeoff, systematically tracking candidate solutions and their evaluation histories. To enhance efficiency, we integrate an

\varepsilon

-Net mechanism to maintain parameter diversity and an LLM Summarizer to perform meta-learning across historical trials. We theoretically prove that POLCA converges to near-optimal candidate solutions under stochasticity. We evaluate our framework on diverse benchmarks, including

τ

-bench, HotpotQA (agent optimization), VeriBench (code translation) and KernelBench (CUDA kernel generation). Experimental results demonstrate that POLCA achieves robust, sample and time-efficient performance, consistently outperforming state-of-the-art algorithms in both deterministic and stochastic problems. The codebase for this work is publicly available at https://github.com/rlx-lab/POLCA.

Xuanfei Ren, Allen Nie, Tengyang Xie +1

University of Wisconsin-Madison, Madison, WI · Google DeepMind, Mountain View, CA · Google Research, Kirkland, WA

Large Language Model-Guided Optimization Stochastic Optimization LLM Agent Workflow Optimization

Mar 13, 2026

Probabilistic Gaussian Homotopy: A Probability-Space Continuation Framework for Nonconvex Optimization

We introduce Probabilistic Gaussian Homotopy (PGH), a probability-space continuation framework for nonconvex optimization. Unlike classical Gaussian homotopy, which smooths the objective and uniformly averages gradients, PGH deforms the associated Boltzmann distribution and induces Boltzmann-weighted aggregation of perturbed gradients, which exponentially biases descent directions toward low-energy regions. We show that PGH corresponds to a log-sum-exp (soft-min) homotopy that smooths a nonconvex objective at scale

λ>0

and recovers the original objective as

λ\to 0

, yielding a posterior-mean generalization of the Moreau envelope, and we derive a dynamical system governing minimizer evolution along an annealed homotopy path. This establishes a principled connection between Gaussian continuation, Bayesian denoising, and diffusion-style smoothing. We further propose Probabilistic Gaussian Homotopy Optimization (PGHO), a practical stochastic algorithm based on Monte Carlo gradient estimation, and demonstrate strong performance on high-dimensional nonconvex benchmarks and sparse recovery problems where classical gradient methods and objective-space smoothing frequently fail.

Eshed Gal, Samy Wu Fung, Eldad Haber

University of British Columbia, Vancouver, BC, Canada · Colorado School of Mines, Golden, CO, USA

Nonconvex Optimization Stochastic Optimization

Mar 13, 2026

Convergence Rate of a Functional Learning Method for Contextual Stochastic Optimization

We consider a stochastic optimization problem involving two random variables: a context variable

X

and a dependent variable

Y

. The objective is to minimize the expected value of a nonlinear loss functional applied to the conditional expectation

\mathbb{E}[f(X, Y,β) \mid X]

, where

f

is a nonlinear function and

β

represents the decision variables. We focus on the practically important setting in which direct sampling from the conditional distribution of

Y \mid X

is infeasible, and only a stream of i.i.d. observation pairs

\{(X^k, Y^k)\}_{k=0,1,2,\ldots}

is available. In our approach, the conditional expectation is approximated within a prespecified parametric function class. We analyze a simultaneous learning-and-optimization algorithm that jointly estimates the conditional expectation and optimizes the outer objective. Using a specially designed measure of non-optimality, combining the squared norm of the objective function's gradient and the mean square error of the auxiliary parametric model, we establish that the method achieves a convergence rate of order

\mathcal{O}\big(1/\sqrt{N}\big)

, where

N

denotes the number of observed pairs.

Noel Smith, Andrzej Ruszczynski

Department of Management Science and Information Systems, Rutgers University

Stochastic Optimization Stochastic Approximation Stochastic Optimization Convergence

Mar 12, 2026

Adaptive Conditional Residual Sampling for Spectral Risk Optimisation under Decision-Dependent Uncertainty

We consider minimising a spectral risk objective, the expected cost plus a weighted conditional value-at-risk, when the distribution of the uncertain parameters depends on the decision and can only be sampled through a stochastic simulator under a fixed budget of draws. We propose adaptive conditional residual sampling (ACRS). It takes one simulator draw at each point of a space-filling design, fits a heteroscedastic regression model of the decision-dependent distribution and reuses the standardised residual vectors as scenarios to construct a deterministic surrogate. ACRS searches this surrogate for several local optima, adds draws around the most promising ones, ranks the candidates on the simulator with common random numbers and finishes with sample-path local refinement using tail importance sampling. We show that the optimality gap of the surrogate minimiser is bounded by the Wasserstein error of the scenario distribution and that the refinement estimator is consistent. In the experiments, all methods share the budget accounting, the design sampler and the local refinement routine, and solutions are scored by normalised regret against reference optima. On 60 random instances of an analytic family with a closed-form objective, ACRS attains a mean regret of 11.8% against 22.3-42.3% for Bayesian optimisation, cross-entropy, kernel-density, stochastic-gradient and refinement-only baselines; its lead is largest at small budgets and, relative to the kernel-density method, tends to grow with the dimension. ACRS also has the lowest mean regret on two six-dimensional benchmarks and three development problems, and performs comparably to pure local refinement on three held-out problems frozen before testing.

Marcell T. Kurbucz

Institute for Global Prosperity, The Bartlett, University College London, 9–11 Endsleigh Gardens, London, WC1H 0EH, United Kingdom

Stochastic Optimization Decision-Making under Uncertainty Conditional Value-at-Risk

Mar 10, 2026

A Trust-Region Interior-Point Stochastic Sequential Quadratic Programming Method

In this paper, we propose a trust-region interior-point stochastic sequential quadratic programming (TR-IP-SSQP) method for solving optimization problems with a stochastic objective and deterministic nonlinear equality and inequality constraints. In this setting, exact evaluations of the objective function and its gradient are unavailable, but their stochastic estimates can be constructed. In particular, at each iteration our method builds stochastic oracles, which estimate the objective value and gradient to satisfy proper adaptive accuracy conditions with a fixed probability. To handle inequality constraints, we adopt an interior-point method (IPM), in which the barrier parameter follows a prescribed decaying sequence. Under standard assumptions, we establish global almost-sure convergence of the proposed method to first-order stationary points. We implement the method on a subset of problems from the CUTEst test set, as well as on logistic regression problems, to demonstrate its practical performance.

Yuchen Fang, Jihun Kim, Sen Na +2

Department of Mathematics, University of California, Berkeley · Department of IEOR, University of California, Berkeley · School of Industrial and Systems Engineering, Georgia Tech +1

Constrained Optimization Stochastic Optimization Stochastic Optimization Convergence Trust-Region Optimization

Mar 10, 2026

Stabilizing Bandits using Regularization: Precise Regret and A Quantitative Central Limit Theorem

Statistical inference with bandit data presents fundamental challenges owing to adaptive sampling, which violates the independence assumptions underlying classical asymptotic theory. Recent work has identified stability~\citep{laiwei82} as a sufficient condition for valid inference under adaptivity. This paper first provides a refined stability condition, stated in terms of the iterates of an online algorithm, and shows that a large class of regularized stochastic-mirror-descent-style algorithms satisfy it. This refined condition allows us to strengthen the asymptotic results of~\citet{laiwei82} in several ways. First, we derive a non-asymptotic Berry--Esseen bound for the empirical reward estimates under adaptive sampling. Second, we derive matching non-asymptotic upper and lower bounds on the regret of the proposed algorithm, yielding a precise characterization of its regret. Third, we show that these regularized algorithms preserve asymptotic normality and valid inference under a prescribed level of adversarial corruption. Finally, we show that regularization is necessary rather than incidental: Lai--Wei stability is incompatible with the optimal

O(\sqrt{T})

regret rate -- the rate attained by unregularized algorithms such as EXP3 -- so that a controlled, polylogarithmic inflation in regret is the price of valid inference.

Budhaditya Halder, Ishan Sengupta, Koustav Chowdhury +2

Department of Statistics, Rutgers University · Indian Statistical Institute, Kolkata

Multi-Armed Bandits Algorithmic Stability Adaptive Sampling Stochastic Optimization

Mar 10, 2026

OptEMA: Adaptive Exponential Moving Average for Stochastic Optimization with Zero-Noise Optimality

Exponential moving averages (EMAs) are a central component of widely used adaptive optimizers such as Adam. However, existing analyses of Adam-style methods often yield suboptimal guarantees in the zero-noise regime, rely on open-loop parameter schedules, or require prior knowledge of smoothness constants. Motivated by these limitations, we introduce OptEMA and analyze two complementary variants: OptEMA-M, which applies an adaptive, decreasing EMA coefficient to the first moment with a fixed second-moment decay, and OptEMA-V, which swaps these roles. At the heart of these variants is a Corrected AdaGrad-Norm coefficient schedule. This formulation renders OptEMA algorithmically closed-loop and Lipschitz-free, meaning its effective stepsizes are trajectory-dependent and require no parameterization via the Lipschitz constant. Under lower-boundedness, unbiasedness, bounded variance, average smoothness, and a bounded stochastic-gradient condition used to control the adaptive normalizers, we prove that both variants achieve the unified noise-adaptive rate

\tilde{\mathcal{O}} \left(T^{-1/2}+σ^{1/2}T^{-1/4}\right)

for the averaged gradient norm. In the zero-noise regime, these bounds automatically reduce to the nearly optimal deterministic rate

\widetilde{\mathcal{O}}(T^{-1/2})

without manual hyperparameter retuning.

Ganzhao Yuan

Shenzhen University of Advanced Technology (SUAT), China

Stochastic Optimization Adaptive Gradient Methods Nonconvex Stochastic Optimization

Mar 9, 2026

Multi-Objective Evolutionary Optimization of Chance-Constrained Multiple-Choice Knapsack Problems with Implicit Probability Distributions

The multiple-choice knapsack problem (MCKP) is a classic combinatorial optimization with wide practical applications. This paper investigates a significant yet underexplored extension of MCKP: the multi-objective chance-constrained MCKP (MO-CCMCKP) under implicit probability distributions. The goal of the problem is to simultaneously minimize the total cost and maximize the confidence level of satisfying the capacity constraint, capturing essential trade-offs in domains like 5G network configuration. To address the computational challenge of evaluating chance constraints under implicit distributions, we first propose an order-preserving efficient resource allocation Monte Carlo (OPERA-MC) method. This approach adaptively allocates sampling resources to preserve dominance relationships while reducing evaluation time significantly. Further, we develop NHILS, a hybrid evolutionary algorithm that integrates specialized initialization and local search into NSGA-II to navigate sparse feasible regions. Experiments on synthetic benchmarks and real-world 5G network configuration benchmarks demonstrate that NHILS consistently outperforms several state-of-the-art multi-objective optimizers in convergence, diversity, and feasibility. The benchmark instances and source code will be made publicly available to facilitate research in this area.

Xuanfeng Li, Shengcai Liu, Wenjie Chen +2

Guangdong Provincial Key Laboratory of Brain-Inspired Intelligent Computation, Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China · School of Information Management, Central China Normal University, Wuhan 430079, China · Centre for Frontier AI Research, Institute of High Performance Computing, Agency for Science Technology and Research, Singapore 138632 +1

Chance-Constrained Optimization Combinatorial Optimization Stochastic Optimization Multi-Objective Evolutionary Optimization

Mar 6, 2026

Adaptive Lipschitz-Free Conditional Gradient Methods for Stochastic Composite Nonconvex Optimization

We propose ALFCG (Adaptive Lipschitz-Free Conditional Gradient), the first adaptive projection-free framework for stochastic composite nonconvex minimization that requires neither global smoothness constants nor line search. Unlike prior conditional gradient methods that use openloop diminishing stepsizes, conservative Lipschitz constants, or costly backtracking, ALFCG maintains a self-normalized accumulator of historical iterate differences to estimate local smoothness and minimize a quadratic surrogate model at each step. This retains the simplicity of Frank-Wolfe while adapting to unknown geometry. We study three variants. ALFCG-FS addresses finite-sum problems with a SPIDER estimator. ALFCG-MVR1 and ALFCG-MVR2 handle stochastic expectation problems by using momentum-based variance reduction with single-batch and two-batch updates, and operate under average and individual smoothness, respectively. To reach an

ε

-stationary point, ALFCG-FS attains

\mathcal{O}(N+\sqrt{N}ε^{-2})

iteration complexity, while ALFCG-MVR1 and ALFCG-MVR2 achieve

\tilde{\mathcal{O}}(σ^2ε^{-4}+ε^{-2})

and

\tilde{\mathcal{O}}(σε^{-3}+ε^{-2})

, where

N

is the number of components and

σ

is the noise level. In contrast to typical

\mathcal{O}(ε^{-4})

or

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

rates, our bounds reduce to the optimal rate up to logarithmic factors

\tilde{\mathcal{O}}(ε^{-2})

as the noise level

σ\to 0

. Extensive experiments on multiclass classification over nuclear norm balls and

\ell_p

balls show that ALFCG generally outperforms state-of-the-art conditional gradient baselines.

Ganzhao Yuan

Shenzhen University of Advanced Technology (SUAT), China

Nonconvex Stochastic Optimization Stochastic Optimization Stochastic Optimization Convergence