Stochastic Optimization
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
226 papers11 papers in the last four weeks, down 69% on the four weeks before. 0.1% of all new papers.
Bias-Reduced and Parallel Heavy-Tailed Stochastic Convex Optimization in Geometries
Muon Attains Iteration Complexity under Shuffling
Simultaneous Near-Optimal Region Identification in Continuous Simulation Optimization: Minimax Complexity and Adaptive Sampling
Descending Everest, Part II: Oracle Complexity of Minimizing a Sum of Convex -Smooth Functions
Beyond Monotonicity: Stochastic Online Optimization under Semi-Bandit Feedback
Robustness Starts with the Objective: Designing and Certifying Robust LLM-Generated Heuristics
Near-Optimal Second-Order Convex Finite-Sum Optimization under Individual Smoothness
Riemannian Optimization on Unknown Manifolds via Stochastic Proximal Refinement
Rennala NSGD: Asynchronous Stochastic Optimization Beyond Euclidean Geometry
Non-Ergodic Markovian Mirror Descent with Unbounded Noise
Agent-Based Transport Model Calibration via Online Stochastic Batch Optimization
When Momentum Helps Polyak--Ruppert Averaging
Stochastic optimization methods through statistical whitening
Near-Optimal Regret for Semi-Bandit Learning of Monotone Stochastic Problems
monotone'' stochastic problems, including prophet inequality, Pandora's box, series testing, stochastic knapsack and stochastic matching. We obtain $\tilde{O}(\sqrt{nkT})$ regret for weakly'' monotone problems and regret for strongly'' monotone problems, where $T$ is the number of periods, $n$ is the problem dimension (number of random variables) and $k$ is the maximum support size of any random variable. This improves over previous regret bounds by a $\sqrt{n}$ factor. In fact, our dependence on $n$ and $T$ is the best-possible due the $Ω(\sqrt{nT})$ lower bound for multi-armed-bandits. Our main technique is the use of Hellinger distance in bounding the error'' between the true and learned distributions, and the use of a constant-factor chain rule for the Hellinger distance of dependent random variables.