Stochastic Optimization

Ask about this topic

Overview

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

CardsList

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

Jun 17, 2026

Compute Efficiency and Serial Runtime Tradeoffs for Stochastic Momentum Methods

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.

Depen Morwani, Alexandru Meterez, Pranav Nair +1

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

Stochastic OptimizationMomentum MethodsStochastic Optimization ConvergenceAccelerated Gradient MethodsStochastic Gradient Descent
AskPDF
Jun 16, 2026

N(CO)2^2: Neural Combinatorial Optimization with Chance Constraints to Solve Stochastic Orienteering

Neural combinatorial optimization (NCO) offers a promising alternative to traditional heuristic-based methods for solving complex graph optimization problems by proposing to learn heuristics through data. This class of problems frequently arises in automation, as it can be used to model a variety of applications. While NCO has been extensively studied for deterministic combinatorial optimization problems, there are only a few works that aim to solve stochastic combinatorial optimization problems. In this work, we present N(CO)2^2: Neural Combinatorial Optimization with Chance cOnstraints to solve the Stochastic Orienteering Problem (SOP) without the use of hand-crafted heuristics. By integrating a reinforcement learning (RL) framework, the model optimizes path selection under uncertainty, effectively balancing exploration and exploitation. Empirical results demonstrate that our method generalizes well across diverse SOP instances, achieving competitive performance compared to the state-of-the-art mixed-integer linear program (MILP) for the task. The proposed approach reduces human effort in heuristic design while enabling adaptive and efficient decision-making in uncertain environments.

Anas Saeed, Marcos Abel Zuzuárregui, Stefano Carpin

Department of Computer Science and Engineering, University of California, Merced, CA, USA

Stochastic OptimizationChance-Constrained OptimizationCombinatorial OptimizationRL for Combinatorial OptimizationNeural Combinatorial Optimization
AskPDF
Jun 15, 2026

Decision-Weighted Flow Matching for Contextual Stochastic Optimization

Conditional generative models are increasingly used as scenario generators for stochastic optimization, but standard training objectives emphasize uniform distributional fit rather than the downstream decisions induced by generated scenarios. This creates an objective mismatch: errors in statistically common regions may have little effect on decision regret, whereas errors in decision-sensitive regions can substantially change the optimal action. We propose Decision-Weighted Flow Matching (DW-FM), a regret-aligned training framework that preserves the simplicity of standard flow matching while reweighting its velocity-regression objective using decision-sensitive endpoint information. Theoretically, we connect downstream regret to pathwise velocity mismatch through a loss-induced decision discrepancy and an adjoint transport argument, yielding an ideal regret-aligned surrogate and practical endpoint-weighted objectives with regret guarantees. Empirically, we demonstrate the effectiveness of DW-FM on three CVaR-based contextual stochastic optimization benchmarks spanning synthetic portfolio, semi-real financial, and traffic-CVaR tasks, where DW-FM improves downstream regret over standard baselines.

Jize Xie, Haomiao Wu, Qiang Chen +2

Department of Industrial Engineering and Decision Analytics Hong Kong University of Science and Technology

Stochastic OptimizationConditional Flow MatchingDecision-Focused LearningFlow-Based Generative Modeling
AskPDF
Jun 12, 2026

Free Heavy-Tailed Lunch for Muon: A Theoretical Justification of Empirical Success

Non-Euclidean optimisation methods with matrix-valued updates, such as Muon and Scion, have recently shown strong empirical performance for training Transformer models, yet their theoretical advantages over Euclidean methods remain poorly understood. We address this gap in the heavy-tailed non-convex regime, where stochastic gradients have bounded pp-th central moments, p∈(1,2]p \in (1,2]. We show that certain non-Euclidean methods achieve optimal sample complexity under stronger stationarity measures, while Euclidean methods incur additional dimension-dependent costs. As a consequence, for m×nm \times n matrices, Muon finds an ε\varepsilon-stationary point in nuclear norm within O(min⁡{m,n}Δ1Lε2(σε)pp−1)\mathcal{O}\left(\min\{m, n\} \frac{Δ_1 L}{\varepsilon^2} \left(\frac σ\varepsilon \right)^{\frac p {p-1}}\right) samples, absorbing heavy-tailed noise without extra dimension dependence, unlike Euclidean methods. We further prove this sample complexity, including its dimension dependence, is optimal for all first-order methods under nuclear-norm stationarity. Experiments on large language models support our theory. Surprisingly, our results suggest that other Schatten geometries beyond the spectral geometry of Muon can perform competitively in certain settings.

Florian Hübler, Thomas Pethick, Suvrit Sra

Department of Computer Science, ETH Zurich, Switzerland · Department of Mathematics, Technical University of Munich, Germany · Munich Center for Machine Learning (MCML)

Stochastic OptimizationNonconvex Stochastic OptimizationHeavy-Tailed NoiseMuon OptimizerStochastic Optimization ConvergenceMatrix Optimization+1
AskPDF
Jun 11, 2026

Zero-Inflated Gaussian Distributions Enable Parameter-Space Sparsity in Estimation-of-Distribution Algorithms

Estimation-of-distribution algorithms (EDAs) are a powerful class of evolutionary methods for black-box optimization, especially when little is known about the structure of the objective. Whereas classical evolutionary algorithms rely on hand-designed mutation and crossover operators, hard to devise for unknown problem structures, and a source of bias, EDAs sidestep operator design entirely: they fit a probability distribution to the best individuals and sample the next generation from it. EDAs are well established on continuous parameter spaces, but they have not previously been generalized to sparse ones, in which most coefficients of a good solution are exactly zero. Existing sparse black-box optimizers therefore reintroduce exactly what EDAs were designed to avoid: hand-crafted sparsity operators, bi-level schemes alternating between support set and active values, zeroing thresholds, and other baked-in assumptions. We close this gap by proposing multivariate zero-inflated Gaussian (ZIG) distributions as EDA sampling laws. A latent Gaussian model with separate indicator and value dimensions represents sparsity patterns, correlations among active parameters, and the interactions between the two, so sparsity patterns and active values are optimized jointly, hierarchy-free. We show that the latent parameters of this model are identifiable from observed samples, unlike in the missing-data settings where related constructions originate, and introduce practical amortized inversion-based estimators for them. The estimators accurately recover latent correlation structures, and on the Lunar Lander benchmark the resulting ZIG-EDA converges faster and reaches higher final returns than a dense Gaussian EDA, a hand-crafted sparse evolutionary algorithm, and an ad-hoc sparse EDA, while finding controllers with only a small fraction of parameters active.

Andreas Faust, Sven Nitzsche, Juergen Becker

University of Freiburg, Freiburg, Germany · FZI Research Center for Information Technology, Karlsruhe, Germany · Karlsruhe Institute of Technology, Karlsruhe, Germany

Stochastic OptimizationParameter EstimationLatent Variable ModelsBlack-Box Optimization
AskPDF
Jun 9, 2026

Quantized Stochastic Primal-Dual Methods for Distributed Optimization under Relaxed Global Geometry

We study distributed optimization with stochastic gradients and finite-bit communication modeled by random (unbiased) quantization. We propose q-PDGD, a quantized stochastic primal-dual method, and analyze it under relaxed global geometry. Under restricted secant inequality (RSI), a constant step-size yields linear contraction to an explicit neighborhood determined by gradient noise, quantization distortion, and network connectivity, while a diminishing step-size achieves O(1/k) convergence without shared-minimizer assumptions. Under Polyak-Lojasiewicz (PL) inequality, we obtain linear-to-neighborhood convergence in the same stochastic quantized setting. Our results match the best-known centralized stochastic rates in oracle complexity, and are supported by experiments demonstrating the predicted tradeoffs between quantization level, step-size choice, and graph structure.

Susmit Sarkar, Abhinav Raghuvanshi, Kushal Chakrabarti +1

Indian Institute of Technology Bombay, Mumbai, Maharashtra, India · Tata Consultancy Services Research, Thane, Maharashtra, India

Stochastic OptimizationPrimal-Dual OptimizationOptimization Convergence AnalysisDistributed Optimization
AskPDF
Jun 9, 2026

Learning What to Remember: Observability-Safe Memory Retention via Constrained Optimization for Long-Horizon Language Agents

Long-horizon language agents accumulate observations, reasoning traces, and retrieved facts exceeding context windows, making memory retention a fundamental resource-allocation problem. Existing systems treat retention as local and do not model long-term consequences under observability constraints. To fill this gap, we formulate memory retention as a constrained stochastic optimization with budget feasibility, evidence utility, and delayed costs including miss, reacquisition, and stale penalties. We show this multi-step problem is NP-hard, making exact solution intractable. Moreover, deployment decisions must be made under partial observability. To address these challenges, we propose OSL-MR (Observability-Safe Learning for Memory Retention), a learning-augmented framework that enforces a strict separation between online-observable features and offline-available supervision. OSL-MR combines an evidence learner trained from realized evidence with a Mixed-Score heuristic that serves as a deployable online-safe baseline and an inductive prior. The policy learns query-conditioned evidence from interaction data and remains deployable under the same constraints. Experiments on LoCoMo and LongMemEval show OSL-MR outperforms recency-based, Generative Agents-style, and other heuristic baselines, especially under tight budgets. The Mixed-Score prior improves precision and recall, and sensitivity analysis shows robustness across cost settings. On small solvable instances, single-step optimization is insufficient to anticipate future demand shifts, while OSL-MR stays significantly closer to the dynamic-programming optimum, confirming the necessity of the sequential formulation and reinforcing our learning-guided approximation. These results establish constrained stochastic optimization and optimization-guided learning as a principled foundation for memory management in long-horizon agents.

Qingcan Kang, Liu Mingyang, Shixiong Kai +3

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

Stochastic OptimizationLong-Horizon LLM AgentsAgent Memory Management
AskPDF
Jun 5, 2026

Large-scale empirical tuning and comparison of default optimizers for variational inference

Black-box variational inference (BBVI) is a methodology for posterior approximation that relies on stochastic optimization. In practice, the stochastic optimizers underpinning BBVI generally require extensive problem-specific tuning, which undermines its promise as a truly "black box" inference algorithm. However, over the past decade, many new adaptive stochastic optimization algorithms have been developed that reduce or remove entirely the need for tuning. In this work, we investigate this new collection of adaptive methods in the context of BBVI, with the goal of establishing the current state of the art in tuning-free optimization-based inference. In particular, we present a large-scale empirical evaluation of 56 stochastic gradient-based optimization algorithms applied to 1092 Bayesian inference optimization problems, involving over 550,000 individual optimization runs and 15 core-years of compute. The optimization algorithms we evaluate are chosen to represent a wide spectrum of recent approaches and the benchmark problems are chosen to span a range of difficulty, with posterior target dimension 1-10^4, condition number 1-10^8, and a range of variational families. Our results show that no single method dominates, but running a selection of 5 algorithms suffices to reliably get close to the best-possible observed performance. We thus provide a strong baseline for applications where expert tuning is not possible and for comparison when developing new stochastic optimization algorithms.

Trevor Campbell, Jonathan H. Huggins, Kyurae Kim +1

Department of Statistics, UBC · Department of Mathematics & Statistics, Boston University · Faculty of Computing & Statistics, Boston University +1

Stochastic OptimizationBayesian InferenceAdaptive Gradient MethodsVariational Inference
AskPDF
Jun 5, 2026

Residual-Controlled Multiplier Learning for Stochastic Constrained Decision-Making

Stochastic constrained decision-making requires optimizing performance objectives while enforcing statistical requirements such as safety or fairness. However, standard primal--dual methods struggle to update multipliers robustly under stochastic mini-batch feedback, as the noise of mini-batch gradients and constraint estimates can be directly accumulated into the multiplier memory. To address this issue, we propose Residual-Controlled Multiplier Learning (RCML), which reformulates multiplier updating as projected-pressure feedback. The central idea is to decompose the projected multiplier into an effective pressure signal for primal descent and a pressure-memory residual for finite-gain multiplier tracking. To handle heterogeneous and noisy observations, we further augment this residual-integral backbone with modular stochastic stabilization components. For the convex-affine backbone, we establish finite-gain convergence, derive a stochastic residual bound under mini-batch feedback, and show that the residual feedback law admits a local KKT-residual interpretation near regular KKT points of nonconvex problems. Experiments across optimization, allocation, and fair-ranking tasks show that RCML improves feasibility control and multiplier stability while maintaining competitive objective performance. Code is released at https://anonymous.4open.science/r/RCML-3114/.

Kang Liu, Jianchen Hu, Ziyu Qu +3

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

Stochastic OptimizationPrimal-Dual OptimizationConstrained Optimization
AskPDF
Jun 4, 2026

OrderGrad: Optimizing Beyond the Mean with Order-Statistic Policy Gradient Estimation

Policy-gradient methods usually optimize expected return, but many real world applications care about distributional properties of returns: tail risk, outlier robustness, or best-of-K discovery. We introduce OrderGrad, a family of likelihood-ratio and reparameterization gradient estimators for order-statistic objectives. OrderGrad optimizes finite-sample L-statistics, i.e., weighted averages of sorted rewards or costs, recovering objectives such as VaR, CVaR, trimmed means, medians, and top-m/best-of-K criteria by changing only the rank weights. For any fixed sample size and rank-weight vector, OrderGrad provides an unbiased gradient estimator for the corresponding order-statistic objective. The method is implemented as a simple reward transformation that can then be used in an otherwise standard policy-gradient or reparameterized update. We study the resulting estimator's variance behavior and evaluate it on tasks where mean optimization is mismatched to the deployment objective, including LLM math post-training and other tasks. OrderGrad provides a unified, plug-and-play route to risk-averse, robust, and exploratory learning. Code: https://github.com/paavo5/ordergrad

Paavo Parmas, Yongmin Kim, Kohsei Matsutani +5

The University of Tokyo

Stochastic OptimizationRisk-Sensitive RLPolicy Gradient MethodsRL for Generative ModelsPolicy Learning
AskPDF
Jun 4, 2026

Diff2SP: Diffusion Models for Correlated Scenario Generation in Stochastic Programming

Scenario generation is a critical component in stochastic programming (SP), as it directly influences the quality of decision-making under uncertainty. Existing approaches predominantly rely on either sampling-based techniques or supervised learning using neural networks. Sampling-based techniques often struggle to capture complex dependencies and rare but plausible events, while supervised learning requires fixed input-output pairs for training and is limited in its ability to generate a wide variety of realistic scenarios that are not restricted by predefined patterns or rules. To address these limitations, we introduce Diff2SP, a diffusion-based generative framework that incorporates downstream optimization objectives directly into scenario generation. Unlike conventional methods that treat scenario generation and decision-making as separate steps, Diff2SP embeds stochastic optimization into the training process, enabling the generation of scenarios that are both statistically coherent and decision-aware. To formally justify this optimization-aware design, we establish a regret bounds that link distributional accuracy to decision quality, and establish sample complexity guarantees showing faster convergence than traditional generative models such as GANs. Empirical results on both synthetic and power-system datasets validate these theoretical insights, demonstrating that Diff2SP consistently improves both statistical fidelity and downstream optimization outcomes.

Haixiang Sun, Andrew Liu

Purdue University

Stochastic OptimizationSynthetic Data GenerationGenerative Modeling
AskPDF
Jun 2, 2026

Bregman meets Lévy: Stochastic mirror descent with heavy-tailed noise in continuous and discrete time

We study the robustness of stochastic mirror descent (SMD) under heavy-tailed noise, focusing on whether the method retains its convergence guarantees when run with infinite-variance stochastic gradient input. To address this question in a principled manner, we begin by introducing a continuous-time model of SMD as a stochastic differential equation (SDE) driven by a centered Lévy noise process with finite pp-th order moments, 1<p≤21 < p \leq 2. This scheme -- which we call the Lévy mirror flow (LMF) -- arises naturally as the scaling limit of SMD in the presence of heavy-tailed noise. In particular, when p<2p < 2 -- the heavy noise regime -- the trajectories of LMF generically exhibit jump discontinuities of arbitrary magnitude which, if frequent enough, lead to infinite variance. Nonetheless, despite this highly singular behavior, we show that LMF attains εε-optimality within O(ε−p/(p−1))\mathcal{O}(ε^{-p/(p-1)}) time in the convex case, and within O~(ε−1/(p−1))\mathcal{\tilde O}(ε^{-1/(p-1)}) time for (relatively) strongly convex objectives. These guarantees provide a transparent characterization of the impact of frequent long jumps on the convergence of the process, and percolate to a series of matching discrete-time guarantees for several variants of SMD under heavy-tailed noise.

Pierre-Louis Cauvin, Panayotis Mertikopoulos

Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France.

Stochastic OptimizationStochastic Differential EquationsHeavy-Tailed NoiseMirror DescentStochastic Optimization ConvergenceHeavy-Tailed Distributions+1
AskPDF
Jun 1, 2026

S3TS: Stochastic Scenario-Structured Tree Search for Advanced Planning Under Uncertainty

Effective scheduling in the energy sector is essential to ensure the reliable operation of electrical grids and their connected assets by, for instance, optimizing the dispatch of generation units and storage systems. An effective planning strategy must (a) accommodate advanced and potentially non-linear system models -- exploiting the increasing data availability of modern grids, and (b) explicitly handle uncertainties arising, for instance, from the integration of renewable energy sources. While existing approaches can address either non-linearity (e.g., Monte Carlo Tree Search) or uncertainty (e.g., stochastic mathematical optimization), there is a lack of planning techniques capable of addressing both challenges simultaneously. To bridge this gap, we propose a Stochastic Scenario-Structured Tree Search (S3TS) algorithm that explicitly represents uncertainty through scenario trees while enabling the integration of advanced non-linear models. We evaluate S3TS on a simulated demand response signal publication problem, largely mimicking the imbalance settlement mechanism in Belgium. The results demonstrate near-optimal performance in linear, analytically tractable settings, with costs within 14% of the mathematically optimal solution conditioned to the scenario trees. In highly non-linear scenarios, S3TS significantly outperforms baseline methods, achieving cost reductions of up to 51% and 5.4% compared to a myopic algorithm and deterministic MCTS, respectively.

Fabio Pavirani, Bert Claessens, Pierre Pinson +1

IDLab Ghent university – imec, Technologiepark Zwijnaarde 126, 9052 Gent, Belgium · Beebop.ai, Belgium · Imperial College London, London, UK

Stochastic OptimizationMonte Carlo Tree SearchDecision-Making under Uncertainty
AskPDF
Jun 1, 2026

Stochastic convergence of parallel asynchronous adaptive first-order methods

A new class of asynchronous adaptive first-order optimization methods is introduced, comprising asynchronous variants of several popular algorithms. Versions of these methods using momentum and/or inexact normalization are also considered. The convergence of methods in the class on non-convex functions is analyzed in a fully stochastic setting, and is shown to be (up to logarithmic factors) of order O(1/sqrt{t}) under reasonable assumptions. Numerical experiments suggest that such asynchronous adaptive algorithms are very relevant in heterogeneous large-scale machine learning systems.

Serge Gratton, Philippe L. Toint

Universit´e de Toulouse, INP, IRIT, Toulouse, France · Universit´e de Toulouse, INP, IRIT, Toulouse, France, and NAXYS, University of Namur, Namur, Belgium

Stochastic OptimizationNonconvex Stochastic OptimizationStochastic Optimization ConvergenceAdaptive Gradient Methods
AskPDF
May 30, 2026

Information-Theoretic Lower Bounds for Bit-Constrained Stochastic Optimization via a Reduction to Compressed Gaussian Mean Estimation

Low-precision pretraining (FP8, MXFP4, NVFP4) is now standard for frontier language models, yet the literature is almost entirely achievability -- algorithms and empirical scaling laws -- with no matching characterization of what is information-theoretically possible. We study a B-bit quantized stochastic first-order oracle: an optimizer interacts for T rounds and receives, each round, a B-bit adaptive public-coin description of its stochastic gradient. Our main contribution is an exact reduction from optimizing a strongly convex quadratic family to interactively compressed Gaussian mean estimation -- under the B-bit oracle the query carries no information, so optimization collapses exactly onto a sequential distributed-estimation problem. This yields two unconditional lower bounds, a communication bound TB = Omega(d) and a statistical bound T = Omega(sigma^2 d / eps^2), and the sharp product-form bound T = Omega((sigma^2 d / eps^2) max{1, d/B}). The product form is also unconditional: a B-bit transcript carries at most O(TB / sigma^2) of Fisher trace about the mean, so bits rather than dimension limit the recoverable information, and combined with the multivariate van Trees inequality this gives the bound directly, without bounded-likelihood-ratio truncation. We give a near-matching achievability result with exact per-round bit accounting under a bounded-dynamic-range oracle, tight up to a logarithmic factor; the lower bound is for truly Gaussian (unbounded) gradients, and closing this oracle gap is left open. A sequential rate-distortion perspective extends the reduction to correlated and drifting oracles and corrects an earlier conjecture: positive noise correlation raises the bound by (1+rho)/(1-rho) rather than relaxing it. The bounds give an information-theoretic baseline for any low-bit gradient path, not an optimality claim about deployed FP4 systems.

Munsik Kim

Stochastic OptimizationStochastic Optimization ConvergenceCommunication ComplexityInformation-Theoretic Lower Bounds
AskPDF
May 30, 2026

In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise

Many stochastic gradient methods are believed not to converge when the noise in stochastic gradients has only a finite pp-th moment for p∈(1,2)p\in\left(1,2\right), a setting known as the heavy-tailed noise assumption. However, some recent studies have found that Stochastic Gradient Descent (SGD\textsf{SGD}), without any modification to its update rule, can surprisingly converge in expectation for convex problems with bounded domains, highlighting the potential of classical stochastic gradient methods. Inspired by this recent progress, we provide a comprehensive study of stochastic optimization under heavy-tailed noise and establish new in-expectation convergence results for Stochastic Mirror Descent (SMD\textsf{SMD}) and Accelerated Stochastic Mirror Descent (ASMD\textsf{ASMD}) in convex optimization, and for SGD\textsf{SGD} and Stochastic Gradient Descent with Momentum (SGDM\textsf{SGDM}) in nonconvex optimization. Notably, our results not only hold without algorithmic changes but also avoid restrictive assumptions, such as bounded domains, imposed in prior work. More importantly, our analysis provides a new, elegant, and powerful framework for studying heavy-tailed stochastic optimization, opening a new route to understanding first-order stochastic gradient methods.

Zijian Liu

Stern School of Business, New York University

Stochastic OptimizationNonconvex Stochastic OptimizationStochastic Optimization ConvergenceHeavy-Tailed Stochastic OptimizationStochastic Gradient Descent
AskPDF
May 29, 2026

Riemannian Stochastic Optimization for Sufficient Dimension Reduction

Sufficient dimension reduction (SDR) makes high-dimensional regression tractable by projecting the covariates onto a low-dimensional subspace that preserves the conditional mean of the response. Existing gradient-based estimators either operate in the ambient space and suffer from the curse of dimensionality, or localize in the reduced space at a per-outer-iteration cost at least quadratic in the sample size. We show that minimizers of the population Minimum Average Variance Estimation (MAVE) risk approximate the same Grassmannian target as the Outer Product of Gradients (OPG), and recast the empirical criterion as a smooth maximization on the Stiefel manifold with closed-form Riemannian gradient. The resulting algorithm, SMAVE, combines sparse projected-space nearest-neighbor localization with Riemannian stochastic gradient ascent. A simplified version comes with almost-sure convergence and a non-asymptotic rate matching the standard non-convex stochastic first-order scaling. Empirically, SMAVE matches or improves on RMAVE's synthetic subspace recovery at moderate-to-high ambient dimension, and on four real datasets it uniformly improves over OPG and is competitive with or outperforms RMAVE at orders of magnitude lower runtime.

Thibault Pautrel, François Portier

Laboratoire des Signaux et Systèmes (L2S), CentraleSupélec, Université Paris-Saclay, Gif-sur-Yvette, France · ENSAI, CREST, Bruz, France

Stochastic OptimizationRiemannian OptimizationInverse Dimensionality ReductionDimensionality Reduction
AskPDF
May 29, 2026

Softsign: Smooth Sign in Your Optimizer For Better Parameter Heterogeneity Handling

Sign-based and LMO-inspired optimizers have recently attracted substantial attention in deep learning due to their strong performance and low memory footprint. However, their fixed-magnitude updates can hurt terminal convergence: they decouple update mechanisms from gradient magnitudes and fail to account for parameter heterogeneity, often leading to oscillation rather than convergence. We propose SoftSignum, a smooth relaxation of sign-based optimization that replaces the hard sign map with a temperature-controlled soft-sign transformation, enabling a parameter-wise transition from sign-like updates to magnitude-sensitive SGD-like steps. We complement it with an adaptive quantile-based temperature schedule and extend the same principle to matrix-valued optimizers, obtaining SoftMuon. We also develop a generalized geometry-relaxation framework based on strongly convex regularizers and Fenchel conjugates, proving convergence in stochastic non-convex setting. Experiments on diverse deep learning tasks, including LLM pretraining, show that SoftSignum and SoftMuon consistently improve over their hard sign-based counterparts and standard AdamW.

Dmitrii Feoktistov, Timofey Belinsky, Andrey Veprikov +2

HSE University, Moscow, Russia · BRAIn Lab, Moscow, Russia · Yandex Research, Moscow, Russia +3

Stochastic OptimizationSign-Based OptimizationDeep Learning OptimizationNonconvex Stochastic OptimizationMuon Optimizer
AskPDF
May 29, 2026

Wall-Clock Complexity for Zeroth-Order Optimization with Tunable Oracle Fidelity

Zeroth-order (black-box) optimization is applied when gradients are unavailable and objective evaluations rely on expensive simulations. In many such applications, the oracle fidelity is tunable: higher-accuracy queries reduce noise but incur higher computational costs. To capture this trade-off, we study an accuracy-aware wall-clock model where each query with fidelity δδ has a cost c(δ)c(δ), and we minimize the total time Ttotal=∑k=1Nc(δk)T_{\mathrm{total}} = \sum_{k=1}^{N} c(δ_k), subject to a target accuracy constraint. We show how the choice of oracle type, noise model, and optimization scheme induces explicit wall-clock-optimal choices for the algorithmic parameters. For instance, we demonstrate that accelerated methods can be wall-clock inferior to non-accelerated schemes. Furthermore, we characterize the conditions under which a constant fidelity strategy is optimal in the Big-O sense. Our framework provides a unified methodology to translate convergence guarantees into practical fidelity and batching recommendations.

Alexandra Suvorikova, Igor Pavlov, Artem Vasin +4

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

Stochastic OptimizationOracle ComplexityZeroth-Order OptimizationDerivative-Free Optimization
AskPDF
May 28, 2026

MoSSP: A Momentum-Based Single-Loop Stochastic Penalty Method for Nonconvex Constrained DC-Regularized Optimization

In this paper, we study a structured class of nonconvex constrained stochastic problems with difference-of-convex (DC) regularization, where the feasible set is possibly nonconvex and the concave part of the DC regularizer is allowed to be nonsmooth. The fundamental challenge lies in maintaining feasibility for nonconvex constraints while achieving favorable oracle complexity. Although single-loop algorithms efficiently solve unconstrained DC optimization problems, their potential for constrained optimization with DC structure remains largely unexplored. To address this gap, we develop MoSSP, a Momentum-based Single-loop Stochastic Penalty method for such problems with provable complexity guarantees. The key idea is to apply a single stochastic proximal-gradient step to the Moreau envelope of the penalty plus the convex DC part, with the concave part's proximal mapping computed in parallel. We derive two algorithm variants: a Polyak-momentum version with O(ε−4)O(\varepsilon^{-4}) oracle complexity for finding stochastic ε\varepsilon-KKT points, and an improved O(ε−3)O(\varepsilon^{-3}) version incorporating recursive momentum. Experimental results demonstrate the effectiveness of the proposed algorithms.

Luxuan Li, Chunfeng Cui, Xiao Wang

School of Mathematical Sciences, Beihang University, Beijing 100191, China · School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510006, China.

Stochastic OptimizationNonconvex Stochastic OptimizationNonconvex Optimization
AskPDF
May 28, 2026

Runtime Analysis of a Compact Genetic Algorithm on a Truly Multi-valued OneMax Function

Recently, the runtime analysis of multi-valued estimation-of-distribution algorithms in the framework of Ben Jedidia et al. (TCS 2024) has made significant advancements. However, almost all existing analyses are limited to multi-valued objective functions that in each dimension only distinguish between two types, also called categories, of values and hence can be treated with similar methods as pseudo-Boolean problems. Only recently, Adak and Witt (GECCO 2025) have presented a first runtime analysis of a multi-valued compact genetic algorithm (cGA) on the multi-valued OneMax function G-OneMax ⁣:{0,…,r−1}n→N\colon \{0,\dots,r-1\}^n \to \mathbf{N} defined by G-OneMax(x1,…,xn)=∑i=1nxi(x_1,\dots,x_n)=\sum_{i=1}^n {x}_i and truly depending on all rr categories. We improve their runtime result from O(nr3log⁡2(n)log⁡(r))\textrm{O}\bigl(n r^3 \log^2( n)\log (r)\bigr) to O(nrlog⁡3(n)log⁡3(r))\textrm{O}\bigl(n r \log^3(n)\log^3(r)\bigr), both for an optimal choice of the update strength KK. Our result matches, up to polylogarithmic factors, the existing bound for the simpler rr-valued OneMax function depending essentially only on two values and analyzed in several previous works. To show the new bound, we use improved drift theorems for processes with high self-loop probabilities and specifically derived concentration inequalities to analyze how probability mass in the multi-valued cGA moves into successively smaller and smaller intervals of the rr-valued frequency matrix.

Martin S. Krejca, Carsten Witt

Laboratoire d’Informatique (LIX), CNRS, École Polytechnique, IP Paris, France · DTU Compute, Technical University of Denmark, Denmark

Stochastic OptimizationEvolutionary OptimizationCombinatorial OptimizationRuntime Analysis of Evolutionary AlgorithmsGenetic Algorithms
AskPDF
May 27, 2026

Learning to Assess the Reliability of Number-of-Runs Estimation in Stochastic Optimization

In large-scale benchmarking of stochastic optimization algorithms, the key challenge is no longer whether repeated runs are needed for reliability, but how to determine when sufficient evidence has been collected without incurring unnecessary computational cost. We study a learning-based extension of a recent empirical online heuristic that adaptively estimates the required number of runs using outlier handling and skewness-based symmetry checks. Using annotated outcomes from 132{,}000 Nevergrad runs on COCO (24 problems in 20 dimensions, 10 instances each, 11 optimizers), we train classifiers on 23 statistical, energy-free, and shape and stability features to predict whether a run-number estimate is reliable, prioritizing detection of incorrect estimates via minority-class recall. We evaluate reliability prediction using a within-configuration learning setup, where models are trained and tested on data sharing the same optimizer. The results show that run-number reliability can be learned in a within-configuration scenario, enabling detection of unreliable estimates with high minority-class recall, although performance remains limited by the restricted data diversity within fixed configurations.

Sara Gjorgjieva, Eva Tuba, Tome Eftimov

Jožef Stefan Institute, Ljubljana, Slovenia

Stochastic OptimizationBlack-Box Optimization
AskPDF
May 25, 2026

Statistical Inference for Stochastic Gradient Descent Beyond Finite Variance

Stochastic gradient descent (SGD) is a foundational algorithm for large-scale statistical learning and stochastic optimization. However, statistical inference based on SGD iterates remains challenging when stochastic gradients have infinite variance, as the relevant limiting distributions depend on unknown nuisance parameters. In this paper, we develop an efficient, model-agnostic methodology for constructing confidence regions from SGD trajectories that applies in both finite- and infinite-variance regimes. The procedure is based on a joint weak convergence result for the Polyak-Ruppert averaged estimator and an empirical second-moment normalizer constructed from stochastic gradients along the SGD trajectory. This joint limit yields a self-normalized statistic in which the leading tail-dependent scaling terms cancel. We then use a subsampling calibration scheme to estimate the relevant critical values, avoiding explicit estimation of tail indices, slowly varying functions, or stable-law parameters. The resulting confidence regions are straightforward to implement and are asymptotically valid under both the finite- and infinite-second-moment regimes. Simulation studies show reliable coverage in various settings, supporting the proposed method as a practical tool for uncertainty quantification in stochastic optimization.

Jose Blanchet, Peter Glynn, Wenhao Yang

Management Science and Engineering, Stanford University

Stochastic OptimizationConfidence Region EstimationUncertainty QuantificationStochastic Gradient Descent
AskPDF
May 24, 2026

Estimating Mixture Distributions via Stochastic Mirror Descent

We revisit the classical problem of estimating an unknown distribution from its samples by fitting a mixture model that minimizes cross-entropy loss. Framing the task as a stochastic convex optimization problem over the space of MM-component mixture distributions, we propose a family of estimators derived from the stochastic mirror descent (SMD) algorithm. This optimization-based approach provides a principled and flexible framework that generalizes traditional estimators and proposes a variety of novel estimators through the choice of Bregman divergences. A key advantage of our method is that it scales efficiently with the number of candidate components fif_i; that is, one can employ a large set of basis distributions in the mixture model without incurring significant computational overhead. This enables richer approximations and improved estimation accuracy. Moreover, in the case of categorical distribution (discrete outcomes) our estimators do not require a strict lower bound, in other words our framework does not require the precise knowledge of the support of the distribution. We demonstrate that, under mild conditions, the proposed φ\varphi-SMD estimators achieve near-optimal convergence rates in both Kullback-Leibler (KL) divergence and ℓ2\ell_2-norm and offer practical benefits when computation is expensive. Our numerical analysis highlights improved performance guaranties over classical estimators, particularly in terms of sample efficiency and scalability.

Mohammadreza Ahmadypour, Tara Javidi, Farinaz Koushanfar

Department of Electrical and Computer Engineering University of California San Diego, San Diego, CA, USA

Stochastic OptimizationStatistical Learning TheoryDensity Estimation
AskPDF
May 23, 2026

Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise

This paper considers the nonconvex nonsmooth problem in which the objective function is Lipschitz continuous. We focus on the stochastic setting where the algorithm can access stochastic function value evaluations with heavy-tailed noise, which is prevalent in many popular machine learning applications. We propose a stochastic zeroth-order algorithm that refines the framework of online-to-nonconvex conversion by clipping the two-point gradient estimator. The theoretical analysis shows that our algorithm can find a (δ,ε)(δ, ε)-Goldstein stationary point with zeroth-order oracle complexity of O(dp2(p−1)δ−1ε−2p−1p−1){\mathcal O}(d^{\frac{p}{2(p-1)}}δ^{-1}ε^{-\frac{2p-1}{p-1}}), where dd is the problem dimension and p∈(1,2]p\in(1,2] is the order of bounded moments. Note that our dependence on dimension dd matches the best-known results of stochastic zeroth-order optimization for finding the sub-optimal solution of a stochastic convex nonsmooth problem. In addition, our dependence on accuracy parameters δδ and εε is consistent with that of the best-known stochastic first-order algorithms for stochastic nonconvex nonsmooth problems. Finally, we conduct numerical experiments to demonstrate the effectiveness of the proposed method.

Zhuanghua Liu, Luo Luo

Stochastic OptimizationGradient ClippingZeroth-Order OptimizationHeavy-Tailed NoiseNonconvex OptimizationNonsmooth Convex Optimization+1
AskPDF
May 19, 2026

LionMuon: Alternating Spectral and Sign Descent for Efficient Training

In large-scale optimization, the cheapness and effectiveness of update steps are the most crucial factors for a successful optimizer. Sign-based optimizers like Lion or Signum produce cheap per-step updates, whereas Muon's spectral matrix-sign update gives a much stronger direction at a substantially higher per-step cost. In this work, we propose LionMuon, which retains the effectiveness of Muon steps while considerably cutting the averaged iteration cost, similar to sign-based methods. It alternates between Lion's and Muon's updates on a fixed period P, sharing a single dual-EMA momentum buffer between them. The optimizer state memory therefore matches Lion and is exactly half of AdamW's. A simpler single-EMA variant, SignMuon, by itself already outperforms pure Muon. At P = 2, LionMuon Pareto-dominates Muon, Lion, Signum, and AdamW on every dataset and architecture we tested at 124M model size, reaching lower validation loss at lower compute, and the same advantage persists at 355M and 720M scale. On the theory side, we prove sharp complexity bounds under heavy-tailed noise which are governed by period-averaged smoothness and noise that interpolate between Muon's and Lion's constants. These bounds predict the compute-optimal period and the conditions under which LionMuon outruns Muon and Lion. Code: https://github.com/brain-lab-research/lion-muon

Arman Bolatov, Artem Riabinin, Nikita Kornilov +4

Mohamed bin Zayed University of Artificial Intelligence (MBZUAI) · Basic Research of Artificial Intelligence Laboratory (BRAIn Lab) · Applied Artificial Intelligence Institute +1

Stochastic OptimizationSign-Based OptimizationMomentum MethodsNeural Network OptimizationMuon OptimizerStochastic Optimization Convergence
AskPDF
May 19, 2026

Factor Augmented High-Dimensional SGD

Stochastic gradient descent (SGD) is a fundamental optimization algorithm widely used in modern machine learning. In this paper, we propose Factor-Augmented SGD (FSGD), a new optimization method that leverages latent factor representations in high-dimensional learning tasks. Unlike standard two-stage dimension reduction approaches that rely on offline representation learning and full data storage, a key novelty of FSGD is that it operates purely on streaming data, making it scalable to large-scale and high-dimensional problems. Furthermore, we establish the first theoretical framework that explicitly incorporates latent factor estimation error into the analysis of SGD, and provide moment convergence in ℓs\ell^s norm under decaying step sizes and mini-batch updates. Our results provide a new foundation for employing SGD reliably and scalably in high-dimensional machine learning systems.

Shubo Li, Yuefeng Han, Xiufan Yu

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

Stochastic OptimizationStochastic Optimization ConvergenceOnline LearningStochastic Gradient Descent
AskPDF
May 18, 2026

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

Many tasks in modern machine learning are observed to involve heavy-tailed gradient noise during the optimization process. To manage this realistic and challenging setting, new mechanisms, such as gradient clipping and gradient normalization, have been introduced to ensure the convergence of first-order algorithms. However, adaptive gradient methods, a famous class of modern optimizers that includes popular Adam\mathtt{Adam} and AdamW\mathtt{AdamW}, often perform well even without any extra operations mentioned above. It is therefore natural to ask whether adaptive gradient methods can converge under heavy-tailed noise without any algorithmic changes. In this work, we take the first step toward answering this question by investigating a special case, AdaGrad\mathtt{AdaGrad}, the origin of adaptive gradient methods. We provide the first provable convergence rate for AdaGrad\mathtt{AdaGrad} in non-convex optimization when the tail index pp satisfies 4/3<p≤24/3<p\leq2. Notably, this result is achieved without requiring any prior knowledge of pp and is hence adaptive to the tail index. In addition, we develop an algorithm-dependent lower bound, suggesting that the existing minimax rate for heavy-tailed optimization is not attainable by AdaGrad\mathtt{AdaGrad}. Lastly, we consider AdaGrad-Norm\mathtt{AdaGrad}\text{-}\mathtt{Norm}, a popular variant of AdaGrad\mathtt{AdaGrad} in theoretical studies, and show an improved rate that holds for any 1<p≤21<p\leq2 under an extra mild assumption.

Zijian Liu

Stern School of Business, New York University

Stochastic OptimizationNonconvex Stochastic OptimizationHeavy-Tailed NoiseStochastic Optimization ConvergenceHeavy-Tailed DistributionsAdaptive Gradient Methods+1
AskPDF
May 18, 2026

Tight Complexity of Muon under Heavy-Tailed Noise

A growing lesson from neural network optimization is that optimizer design should respect how the model is parametrized. The layerwise input-output structure of neural networks motivates Muon and Scion, whose updates also support hyperparameter transfer. At the same time, stochastic gradient noise in deep learning is often far from sub-Gaussian and may exhibit heavy tails. These observations have shaped recent algorithmic principles for training neural networks, yet their joint theoretical consequences are underexplored. In particular, it is unclear what dimension dependence is unavoidable for gradient-based methods when the problem class is defined using an input-output norm and the stochastic gradient noise is heavy-tailed, and if higher-order smoothness can accelerate optimization. We study these questions through nonconvex smooth stochastic optimization over Rm×n\mathbb{R}^{m\times n} equipped with general norms and under pthp^\mathrm{th}-moment heavy-tailed noise, where the goal is to achieve an εε-stationary point in the dual norm. Our first contribution is a dimension-dependent lower bound: when max⁡{m,n}\max\{m,n\} is large enough, any method using only the stochastic gradients requires Ω(min⁡{m,n}ε−3p−2p−1)Ω(\min\{m, n\}ε^{-\frac{3p-2}{p-1}}) oracle calls for the problem class defined by the spectral norm, which is a common input-output matrix norm. We prove that a batched Muon method with the spectral norm can achieve the matching upper bound of O(min⁡{m,n}ε−3p−2p−1)O(\min\{m, n\}ε^{-\frac{3p-2}{p-1}}). To exploit higher-order smoothness, we propose a transported Muon method and improve the bound to O(min⁡{m,n}ε−5p−32p−2)O(\min\{m, n\}ε^{-\frac{5p-3}{2p-2}}) when the norm is spectral and the Hessian is Lipschitz. Finally, we incorporate practical heuristics into our transported method and evaluate it across multiple architectures and model sizes, showing its compatibility with neural network training.

Jiayu Zhang, Tianyi Lin

Department of Industrial Engineering and Operations Research, Columbia University

Stochastic OptimizationNeural Network OptimizationNonconvex Stochastic OptimizationHeavy-Tailed NoiseStochastic Optimization ConvergenceHeavy-Tailed Stochastic Optimization
AskPDF
May 17, 2026

Scalable Bi-causal Optimal Transport via KL Relaxation and Policy Gradients

Bi-causal optimal transport (OT) is a natural framework for comparing and coupling stochastic processes under nonanticipative information constraints, with important applications in robust finance, sequential uncertainty quantification, and multistage stochastic optimization. In particular, a learned bi-causal coupling naturally serves as a simulator for generating joint sample paths that respect both prescribed marginal laws and the underlying information flow. Its practical use, however, is limited by the computational difficulty of enforcing bi-causal coupling constraints over path space, especially for continuous distributions and long horizons. We develop a scalable stochastic-optimization framework for computing bi-causal OT couplings under general marginals. Our approach introduces a Kullback--Leibler (KL)-penalized relaxation that replaces hard marginal constraints with tractable divergence penalties while preserving the recursive structure of the problem. We establish dynamic programming principles for both the original and relaxed formulations, prove that the relaxed problem converges to the original bi-causal OT problem as the penalty grows, and derive explicit policy-gradient representations for the relaxed objective. Building on these results, we propose a practical policy-gradient algorithm with unbiased mini-batch estimators, variance reduction, and nonasymptotic regret guarantees. Numerical experiments show that the method accurately captures marginal laws and temporal dependence, and performs well in applications including robust subhedging and time series statistical downscaling. These results provide a scalable computational approach to bi-causal OT and broaden its applicability in settings where nonanticipative information constraints are essential.

Haoyang Cao, Jesse Hoekstra, Renyuan Xu +2

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

Stochastic OptimizationOptimal Transport
AskPDF