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.

Compute Efficiency and Serial Runtime Tradeoffs for Stochastic Momentum Methods
Jun 17, 2026Depen Morwani, Alexandru Meterez, Pranav Nair +1Stochastic Optimization Momentum Methods
1Harvard University · 2Kempner Institute at Harvard University · †: Work done while at Harvard.
N(CO) $^2$ : Neural Combinatorial Optimization with Chance Constraints to Solve Stochastic Orienteering
Jun 16, 2026Anas Saeed, Marcos Abel Zuzuárregui, Stefano CarpinStochastic Optimization Chance-Constrained Optimization
Department of Computer Science and Engineering, University of California, Merced, CA, USA
Decision-Weighted Flow Matching for Contextual Stochastic Optimization
Jun 15, 2026Jize Xie, Haomiao Wu, Qiang Chen +2Stochastic Optimization Conditional Flow Matching
Department of Industrial Engineering and Decision Analytics Hong Kong University of Science and Technology
Free Heavy-Tailed Lunch for Muon: A Theoretical Justification of Empirical Success
Jun 12, 2026Florian Hübler, Thomas Pethick, Suvrit SraStochastic Optimization Nonconvex Stochastic Optimization
Department of Computer Science, ETH Zurich, Switzerland · Department of Mathematics, Technical University of Munich, Germany · Munich Center for Machine Learning (MCML)
Zero-Inflated Gaussian Distributions Enable Parameter-Space Sparsity in Estimation-of-Distribution Algorithms
Jun 11, 2026Andreas Faust, Sven Nitzsche, Juergen BeckerStochastic Optimization Parameter Estimation
University of Freiburg, Freiburg, Germany · FZI Research Center for Information Technology, Karlsruhe, Germany · Karlsruhe Institute of Technology, Karlsruhe, Germany
Quantized Stochastic Primal-Dual Methods for Distributed Optimization under Relaxed Global Geometry
Jun 9, 2026Susmit Sarkar, Abhinav Raghuvanshi, Kushal Chakrabarti +1Stochastic Optimization Primal-Dual Optimization
Indian Institute of Technology Bombay, Mumbai, Maharashtra, India · Tata Consultancy Services Research, Thane, Maharashtra, India
Learning What to Remember: Observability-Safe Memory Retention via Constrained Optimization for Long-Horizon Language Agents
Jun 9, 2026Qingcan Kang, Liu Mingyang, Shixiong Kai +3Stochastic Optimization Long-Horizon LLM Agents
Department of Industrial Engineering and Decision Analytics, Hong Kong University of Science and Technology · Department of Computer Science, City University of Hong Kong · Huawei Noah’s Ark Lab
Large-scale empirical tuning and comparison of default optimizers for variational inference
Jun 5, 2026Trevor Campbell, Jonathan H. Huggins, Kyurae Kim +1Stochastic Optimization Bayesian Inference
Department of Statistics, UBC · Department of Mathematics & Statistics, Boston University · Faculty of Computing & Statistics, Boston University +1
Residual-Controlled Multiplier Learning for Stochastic Constrained Decision-Making
Jun 5, 2026Kang Liu, Jianchen Hu, Ziyu Qu +3Stochastic Optimization Primal-Dual Optimization
School of Future Technology Xi’an Jiaotong University Xi’an, China, 710049 · School of Automation Science and Engineering Xi’an Jiaotong University Xi’an, China, 710049 · School of Mathematics and Physics China University of Geosciences Wuhan, China, 430074 +2
OrderGrad: Optimizing Beyond the Mean with Order-Statistic Policy Gradient Estimation
Jun 4, 2026Paavo Parmas, Yongmin Kim, Kohsei Matsutani +5Stochastic Optimization Risk-Sensitive RL
The University of Tokyo
Diff2SP: Diffusion Models for Correlated Scenario Generation in Stochastic Programming
Jun 4, 2026Haixiang Sun, Andrew LiuStochastic Optimization Synthetic Data Generation
Purdue University
Bregman meets Lévy: Stochastic mirror descent with heavy-tailed noise in continuous and discrete time
Jun 2, 2026Pierre-Louis Cauvin, Panayotis MertikopoulosStochastic Optimization Stochastic Differential Equations
Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France.
S3TS: Stochastic Scenario-Structured Tree Search for Advanced Planning Under Uncertainty
Jun 1, 2026Fabio Pavirani, Bert Claessens, Pierre Pinson +1Stochastic Optimization Monte Carlo Tree Search
IDLab Ghent university – imec, Technologiepark Zwijnaarde 126, 9052 Gent, Belgium · Beebop.ai, Belgium · Imperial College London, London, UK
Stochastic convergence of parallel asynchronous adaptive first-order methods
Jun 1, 2026Serge Gratton, Philippe L. TointStochastic Optimization Nonconvex Stochastic Optimization
Universit´e de Toulouse, INP, IRIT, Toulouse, France · Universit´e de Toulouse, INP, IRIT, Toulouse, France, and NAXYS, University of Namur, Namur, Belgium
Information-Theoretic Lower Bounds for Bit-Constrained Stochastic Optimization via a Reduction to Compressed Gaussian Mean Estimation
May 30, 2026Munsik KimStochastic Optimization Stochastic Optimization Convergence
In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise
May 30, 2026Zijian LiuStochastic Optimization Nonconvex Stochastic Optimization
Stern School of Business, New York University
Riemannian Stochastic Optimization for Sufficient Dimension Reduction
May 29, 2026Thibault Pautrel, François PortierStochastic Optimization Riemannian Optimization
Laboratoire des Signaux et Systèmes (L2S), CentraleSupélec, Université Paris-Saclay, Gif-sur-Yvette, France · ENSAI, CREST, Bruz, France
Softsign: Smooth Sign in Your Optimizer For Better Parameter Heterogeneity Handling
May 29, 2026Dmitrii Feoktistov, Timofey Belinsky, Andrey Veprikov +2Stochastic Optimization Sign-Based Optimization
HSE University, Moscow, Russia · BRAIn Lab, Moscow, Russia · Yandex Research, Moscow, Russia +3
Wall-Clock Complexity for Zeroth-Order Optimization with Tunable Oracle Fidelity
May 29, 2026Alexandra Suvorikova, Igor Pavlov, Artem Vasin +4Stochastic Optimization Oracle Complexity
Weierstrass Institute for Applied Analysis and Stochastics, Berlin, Germany · Moscow Independent Research Institute of Artificial Intelligence, Moscow, Russia · MSU Institute for Artificial Intelligence, Moscow, Russia +3
MoSSP: A Momentum-Based Single-Loop Stochastic Penalty Method for Nonconvex Constrained DC-Regularized Optimization
May 28, 2026Luxuan Li, Chunfeng Cui, Xiao WangStochastic Optimization Nonconvex Stochastic Optimization
School of Mathematical Sciences, Beihang University, Beijing 100191, China · School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510006, China.
Runtime Analysis of a Compact Genetic Algorithm on a Truly Multi-valued OneMax Function
May 28, 2026Martin S. Krejca, Carsten WittStochastic Optimization Evolutionary Optimization
Laboratoire d’Informatique (LIX), CNRS, École Polytechnique, IP Paris, France · DTU Compute, Technical University of Denmark, Denmark
Learning to Assess the Reliability of Number-of-Runs Estimation in Stochastic Optimization
May 27, 2026Sara Gjorgjieva, Eva Tuba, Tome EftimovStochastic Optimization Black-Box Optimization
Jožef Stefan Institute, Ljubljana, Slovenia
Statistical Inference for Stochastic Gradient Descent Beyond Finite Variance
May 25, 2026Jose Blanchet, Peter Glynn, Wenhao YangStochastic Optimization Confidence Region Estimation
Management Science and Engineering, Stanford University
Estimating Mixture Distributions via Stochastic Mirror Descent
May 24, 2026Mohammadreza Ahmadypour, Tara Javidi, Farinaz KoushanfarStochastic Optimization Statistical Learning Theory
Department of Electrical and Computer Engineering University of California San Diego, San Diego, CA, USA
Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise
May 23, 2026Zhuanghua Liu, Luo LuoStochastic Optimization Gradient Clipping
LionMuon: Alternating Spectral and Sign Descent for Efficient Training
May 19, 2026Arman Bolatov, Artem Riabinin, Nikita Kornilov +4Stochastic Optimization Sign-Based Optimization
Mohamed bin Zayed University of Artificial Intelligence (MBZUAI) · Basic Research of Artificial Intelligence Laboratory (BRAIn Lab) · Applied Artificial Intelligence Institute +1
Factor Augmented High-Dimensional SGD
May 19, 2026Shubo Li, Yuefeng Han, Xiufan YuStochastic Optimization Stochastic Optimization Convergence
Department of Statistics The Pennsylvania State University University Park, PA 16802, USA · Department of Applied and Computational Mathematics and Statistics University of Notre Dame Notre Dame, IN 46556, USA
Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad
May 18, 2026Zijian LiuStochastic Optimization Nonconvex Stochastic Optimization
Stern School of Business, New York University
Tight Complexity of Muon under Heavy-Tailed Noise
May 18, 2026Jiayu Zhang, Tianyi LinStochastic Optimization Neural Network Optimization
Department of Industrial Engineering and Operations Research, Columbia University
Scalable Bi-causal Optimal Transport via KL Relaxation and Policy Gradients
May 17, 2026Haoyang Cao, Jesse Hoekstra, Renyuan Xu +2Stochastic Optimization Optimal Transport
Department of Applied Mathematics and Statistics, Data Science and AI Institute, and Mathematical Institute for Data Science, Johns Hopkins University. · Department of Statistics, Oxford-Man Institute of Quantitative Finance, and Nuffield College, University of Oxford. · Management Science & Engineering Department, Stanford University. +2

Jun 17, 2026J/K move · Enter open · S save

Compute Efficiency and Serial Runtime Tradeoffs for Stochastic Momentum Methods

Depen Morwani, Alexandru Meterez, Pranav Nair, Sham Kakade

1Harvard University · 2Kempner Institute at Harvard University · †: Work done while at Harvard.

Stochastic Optimization Momentum Methods Stochastic Optimization Convergence Accelerated Gradient Methods Stochastic Gradient Descent

Open paper AskPDF arXiv

Stochastic momentum methods such as heavy ball (HB), Nesterov momentum, and variants of Accelerated SGD (ASGD) [Kidambi et al., 2018] are widely used in modern training, but their stochastic benefits depend on two distinct quantities: serial runtime, the number of iterations needed to reach a target accuracy, and compute efficiency (CE), the inverse total gradient-query or FLOP cost. Larger batches reduce serial runtime without hurting CE only when the contraction gap grows linearly with batch size. We study stochastic HB and ASGD for consistent linear regression with Gaussian covariates and prove finite-dimensional, discrete-time lower bounds on their batch-size tradeoffs. Our first result shows that HB does not improve the CE frontier over SGD for arbitrary spectra; rather, it preserves SGD-level CE over a larger batch-size window, allowing larger batches to reduce serial runtime until HB reaches its deterministic accelerated scale. This window can be a factor

\sqrtκ

larger than the SGD critical batch size. For ASGD, the picture is more spectrum-dependent: for rapidly decaying power-law spectra, ASGD improves small-batch CE over HB/SGD, but as batch size grows it trades this CE advantage for improved serial runtime. Synthetic linear-regression experiments verify these qualitative regimes, including near-overlap of ASGD and HB for slowly decaying spectra and the predicted CE--serial tradeoff for rapidly decaying spectra.