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.

Nov 17, 2026

An inexact stochastic variance-reduced gradient method for constrained convex finite-sum optimization

In this paper, we study a class of constrained convex finite-sum optimization problems. In many practical applications, all or some of the constraints are hard constraints that represent imperative requirements. Consequently, any desirable approximate solution must (nearly) satisfy these constraints. Motivated by this, we focus on computing an εε-surely feasible stochastic optimalsurely\ feasible\ stochastic\ optimal (εε-SFSO) solution, in which the constraint violation is deterministically bounded by εε, and the expected optimality gap is at most εε. While a recently proposed stochastic variance-reduced first-order penalty method can compute an εε-SFSO solution, there remains a significant gap between its first-order oracle complexity for computing an εε-SFSO solution and that for computing an εε-expected feasible stochastic optimalexpected\ feasible\ stochastic\ optimal solution, where both the expected constraint violation and the expected optimality gap are bounded by εε. To narrow this gap, we propose an inexact stochastic variance-reduced gradient (SVRG) method that significantly improves the previously best-known first-order oracle complexity for computing an εε-SFSO solution. Furthermore, when the objective consists of a single function, the proposed method reduces to a novel deterministic first-order method for solving standard convex conic optimization. It achieves a significantly lower gradient evaluation complexity with respect to the objective function compared to existing methods, and can outperform them when computing constraint gradients and projections onto the associated cone is cheaper than evaluating the objective gradient. Preliminary numerical results are presented to illustrate the performance of the proposed method.
Nov 16, 2026

Bias-Reduced and Parallel Heavy-Tailed Stochastic Convex Optimization in ℓp\ell_p Geometries

We consider the fundamental problem of parallel stochastic convex optimization (SCO), whose aim is to approximately minimize a convex objective when given the ability to query a moment-bounded stochastic gradient oracle multiple times in parallel per round. Whereas most previous results have focused on the variance-bounded Euclidean (ℓ2\ell_2-norm) setting, meaning the objective is Lipschitz with respect to the ℓ2\ell_2-norm over an ℓ2\ell_2-bounded feasible set in Rd\mathbb{R}^d, in this work we study parallel SCO in ℓp\ell_p settings for 2≤p<∞2 \le p < \infty under a heavy-tailed noise model. We begin by introducing a new class of ℓp\ell_p-optimal-distance-convergence (ODCp_p) algorithms, drawing on prior stochastic bias-reduced techniques [ACJ+21], which combine with multilevel Monte Carlo methods to efficiently estimate the optimum of uniformly convex objectives. As a consequence of our ODCp_p algorithms, we first establish rates for projection-efficient ℓp\ell_p-Lipschitz optimization, composite convex minimization, and efficient ℓp\ell_p-proximal point estimation. Combining our ODCp_p algorithms with a new ℓp\ell_p-generalized Gaussian-based stochastic gradient estimator (pp-GREG), we provide two efficient ℓp\ell_p parallel algorithms, EpochDA and ℓp\ell_p-AC-SA, which achieve optimization error ε>0ε> 0 with at most O~(dp2p+2ε−pp+1)\tilde{O}(d^{\frac{p}{2p + 2}} ε^{-\frac{p}{p + 1}}) query depth, improving upon the sequential heavy-tailed stochastic query depth of O(ε−p)O(ε^{-p}) for ε≤O~(d−1/(2p))ε\leq \tilde{O}(d^{-1/(2p)}). We also establish dimension-dependent lower bounds of Ω(min⁡{ε−p,dp/(3p−2)})Ω\bigl(\min\{ε^{-p},d^{p/(3p-2)}\}\bigr) adaptive rounds for nonsmooth convex optimization over a subset of the unit ℓp\ell_p ball. Our results improve upon the Ω(min⁡{ε−p,ε2/3d1/3})Ω(\min\{ε^{-p},ε^{2/3}d^{1/3}\}) bounds of [DG19], when adapted to the same feasible set.
Nov 13, 2026

Muon Attains O(ε−3)\mathcal{O}(\varepsilon^{-3}) Iteration Complexity under Shuffling

Muon is a stochastic first-order optimizer for matrix-valued parameters. It maintains an exponential moving average of stochastic gradients in a momentum buffer with coefficient ββ, and orthogonalizes the buffer to obtain the update direction. Muon has been reported to accelerate and stabilize the training of large language models. In practice, it is often used with shuffling (sampling without replacement), where each epoch visits the components of a finite-sum objective in a permuted order. However, its iteration complexity in this setting remains open. We analyze Muon under shuffling, with the momentum buffer orthogonalized by the polar map. For smooth nonconvex finite-sum problems, we establish an O(ε−3)\mathcal{O}(\varepsilon^{-3}) iteration complexity for finding an ε\varepsilon-stationary point. This guarantee holds for every sequence of permutations, covering random reshuffling, shuffle once, and the incremental gradient method. This complexity matches that of stochastic gradient descent under shuffling in its dependence on ε\varepsilon, and improves on Muon's O(ε−4)\mathcal{O}(\varepsilon^{-4}) complexity under sampling with replacement. Our guarantee requires a problem-dependent ββ that approaches one as the number of components grows. In contrast, no fixed ββ guarantees convergence to stationarity for every number of components. We show this by constructing a family of smooth convex problems on which, for any fixed β∈[0,1)β\in[0,1), Muon remains bounded away from stationarity once the number of components is sufficiently large. This failure occurs for every sequence of permutations and persists even with small stepsizes. These results suggest two practical tuning rules: if the training loss stops decreasing even after reducing the stepsize, increase ββ; when increasing ββ, reduce the stepsize accordingly.
Nov 10, 2026

Simultaneous Near-Optimal Region Identification in Continuous Simulation Optimization: Minimax Complexity and Adaptive Sampling

Simulation optimization typically returns a single estimated optimal point. When decisions also depend on criteria evaluated independently of simulation, such as resource cost, the decision maker instead needs the set of designs whose expected performance lies within a tolerance of the optimum, often choosing the tolerance only after seeing the tradeoffs. We study how to identify these near-optimal regions on a continuous design space, simultaneously for all tolerances up to a prescribed maximum TT, with region estimation error at most ηη. We show that region identification is not a by-product of optimization. Specifically, when α>να>ν, any procedure, even one given the optimal design in advance, needs at least Ω(η−(2+d/ν)min⁡{1,KTd/α})Ω\bigl(η^{-(2+d/ν)}\min\{1,KT^{d/α}\}\bigr) simulation evaluations, where dd is the dimension, νν the smoothness, and (K,α)(K,α) the covering parameters that describe the geometry of the near-optimal designs. We propose SASORI, which returns an estimated optimal point and the regions for all tolerances from the same evaluations, matching this lower bound up to logarithmic factors. SASORI also achieves the optimal tradeoff between region estimation error and cumulative regret, and reduces to a minimax-optimal simulation optimization procedure at zero tolerance. Numerical experiments illustrate the effectiveness of our proposed method.
Nov 3, 2026

Descending Everest, Part II: Oracle Complexity of Minimizing a Sum of Convex (L0,L1)(L_0,L_1)-Smooth Functions

We study the minimization of the average of nn convex (L0,L1)(L_0,L_1)-smooth functions: the Hessian norm of each function is bounded by an affine function of its gradient norm. We assume known upper bounds RR on the distance from the starting point to a minimizer and δδ on the difference between the minimum of the average and the average of the infima of the components. We derive upper and lower bounds on the oracle complexity of reaching accuracy ε\varepsilon in function value in expectation. Up to logarithmic factors, both bounds are of order n(1+(L1R)2/3)+n(L0+L12δ)R2ε+n(L1R)2n(1+(L_1R)^{2/3}) +\sqrt{\frac{n(L_0+L_1^2δ)R^2}{\varepsilon}+n(L_1R)^2}. The upper bound is attained by the proposed method YETI. The method combines ideas of accelerated proximal methods and variance reduction methods with a heuristic for choosing additional points. The number of oracle calls made by the heuristic is bounded, which preserves the upper bound on the total number of queries needed to reach the target accuracy. In the experiments, YETI is compared with first-order methods on synthetic problems and Poisson regression problems. We also examine the stopping criterion and the effect of the heuristic separately. The lower bound is obtained by an explicit construction of families of instances that are hard for any first-order method.
Nov 2, 2026

Beyond Monotonicity: Stochastic Online Optimization under Semi-Bandit Feedback

We study stochastic online optimization (SOO) under semi-bandit feedback: in each of TT rounds, a policy adaptively observes nn independent random variables with unknown distributions, learning only from observed values. First-order stochastic dominance (FSD) monotonicity enables general reductions for learning SOO, but can fail when observations change future feasibility, resource use, or reference points. Our algorithm runs the dynamic program for the optimal policy, replacing each expectation by its most optimistic value over a confidence set of distributions. Its regret depends on the level-set complexity sis_i of the computed values as functions of the iith variable: the number of intervals needed to describe their superlevel sets. For rewards in [0,1][0,1], the regret is O~(ST)\tilde{O}(\sqrt{ST}) without this monotonicity, where S=∑i=1nmin⁡{si,ki}S=\sum_{i=1}^n\min\{s_i,k_i\} and kik_i is the support size of the iith distribution, which may be infinite when sis_i is finite. For constant level-set complexities, regret is O~(nT)\tilde{O}(\sqrt{nT}), even for continuous distributions. The algorithm requires no knowledge of sis_i, kik_i, or the supports, and it also achieves regret O~(nkT)\tilde{O}(\sqrt{nkT}) for supports of size at most kk without any level-set condition, which improves the previous bound O~(n(kT+k))\tilde{O}(n(\sqrt{kT}+k)) for FSD-monotone problems. We also prove a lower bound of Ω(min⁡{T,ST})Ω(\min\{T,\sqrt{ST}\}) for all positive integers s1,…,sns_1,\ldots,s_n with ki=2si+1k_i=2s_i+1, which holds even under full feedback and matches the upper bound up to logarithmic factors. We obtain O~(nT)\tilde{O}(\sqrt{nT}) regret for these problems, all nonmonotone under FSD: stochastic Boolean function evaluation, the full-information secretary problem, optimal stopping with loss aversion, scheduling with deadlines and correlated stochastic knapsack with unimodal rewards, and overbooking with group reservations.
Oct 31, 2026

Robustness Starts with the Objective: Designing and Certifying Robust LLM-Generated Heuristics

LLMs are increasingly used to design heuristics for computer systems. However, most synthesis frameworks evaluate candidates by their average performance, which can mask severe regressions on specific workloads. Even adding adversarial training inputs doesn't eliminate these regressions, and percentile objectives (e.g., optimizing for the 95th percentile) overlook how severe regressions can be beyond the selected threshold. We present TAILOR, a framework that guides LLM synthesis using the Conditional Value at Risk (CVaR) of the cost difference between each candidate and an existing baseline on the same workload. This paired CVaR measures the average difference over the worst fraction of workloads. We show that a negative paired CVaR guarantees improvements in both average performance and tail optimality gap relative to the unknown optimum, without ever computing that optimum. We find that TAILOR achieves the best mean--tail trade-off among the synthesis objectives we evaluate across three case studies: Azure GPU batch admission, Azure VM packing, and server placement. Tested across seven diverse optimization benchmarks, TAILOR produces heuristics that are certified with 99% confidence to improve both average performance and tail optimality gaps over the baseline in six of them. On these six benchmarks, TAILOR also outperforms known robust, human-designed alternatives in the tail while achieving better or comparable average-performance improvement over the baseline.
Oct 30, 2026

Near-Optimal Second-Order Convex Finite-Sum Optimization under Individual Smoothness

We study the stochastic second-order oracle complexity of solving smooth convex finite-sum optimization with nn components. Very recently, Tsedenov & Kovalev (2026) showed that the minimax optimal complexity under averaged smoothness and convexity is Θ~(n+n6/7ε−2/7)\tildeΘ(n + n^{6/7} ε^{-2/7}) by establishing nearly matching upper and lower bounds. In this paper, we show that individual smoothness and convexity provably enable further acceleration, where the lower complexity bound is Ω(n+n5/7ε−2/7)Ω(n+ n^{5/7} ε^{-2/7}) under this stronger assumption. Then, by establishing a novel second-order self-bounding inequality, we design a new Taylor-corrected lazy Newton method, which can lead to a better complexity of O~(n+n5/7ε−2/7)\tilde{\mathcal{O}}(n + n^{5/7} ε^{-2/7}) by applying the optimal Monteiro-Svaiter acceleration, matching our lower bound up to only logarithmic factors.
Oct 30, 2026

Riemannian Optimization on Unknown Manifolds via Stochastic Proximal Refinement

We study Riemannian optimization on an unknown manifold accessed only through feasible samples. The central challenge is to turn feasible samples into optimization steps, i.e., the samples are drawn from the unknown feasible manifold, but do not directly provide the tangent spaces, projections, or retractions required by classic Riemannian methods. Moreover, regions with low objective values may be sparsely represented in the data, so directly sampling from a distribution fitted to these observations can require many draws to find better feasible solutions. We introduce Proximal Refinement on Implicit Smooth Manifolds (PRISM), which turns feasible-sample access into an iterative optimization procedure by repeatedly sampling an objective-aware proximal distribution conditioned on the current iterate. Theoretically, we show that PRISM recovers the effect of Riemannian-gradient refinement, leading to provable objective descent, feasibility (manifold adherence), and convergence toward first-order stationarity. We demonstrate the effectiveness of our approach through synthetic experiments illustrating its geometric properties and applications to data-driven building control and diverse real world optimization tasks, highlighting its potential as a general framework for data-driven optimization across scientific and engineering domains.
Oct 28, 2026

Rennala NSGD: Asynchronous Stochastic Optimization Beyond Euclidean Geometry

The empirical success of matrix-aware optimizers, such as Muon (Jordan et al., 2024) and Shampoo (arXiv:1802.09568), highlights the potential of non-Euclidean geometry for deep learning, including large language model (LLM) training. Despite this progress, the theoretical understanding of stochastic optimization in general normed spaces remains limited, particularly in distributed settings. We analyze minibatch stochastic gradient descent (SGD) for smooth nonconvex optimization with respect to an arbitrary norm on a finite-dimensional space. Using the framework of κκ-regular normed spaces (arXiv:0809.0813), we derive high-probability oracle complexity bounds under a light-tail condition stated directly in the dual norm induced by the update norm. The bounds make the dependence on geometry explicit through the regularity constant κκ of the dual space. In the Euclidean case, our bound recovers the standard minibatch SGD rate up to logarithmic factors. For some non-Euclidean geometries and noise models, it is sharper than bounds obtained by converting a Euclidean noise assumption, reducing a linear dimension dependence to a logarithmic one. Building on this framework, we introduce Rennala NSGD, a semi-asynchronous distributed algorithm, and establish wall-clock time complexity guarantees under fixed, heterogeneous worker computation times. In the Euclidean case (κ=1κ=1), our bound matches the parameter dependence of classical Rennala SGD up to logarithmic factors.
Oct 25, 2026

Non-Ergodic Markovian Mirror Descent with Unbounded Noise

We analyze stochastic mirror descent for minimizing a convex objective expressed as an expectation under the stationary distribution of a Markov chain, using noisy subgradient observations along a single sample path. Through Poisson's equation, we decompose the Markovian noise and control its contribution under regularity and moment conditions that allow the stochastic subgradients and the Poisson solution to be unbounded across the state space. We establish an O(T−1/2)O(T^{-1/2}) bound on the expected suboptimality gap of the weighted-average iterate for an appropriately chosen step size. The analysis does not require aperiodicity or convergence of the chain's marginal distributions to stationarity. For irreducible finite-state chains, we verify the required conditions on the Poisson solution and derive explicit bounds that quantify the effect of periodicity. For irreducible countable-state chains, we verify the required regularity and moment conditions under a geometric Lyapunov drift condition and suitable growth bounds on the stochastic subgradients.
Oct 23, 2026

Agent-Based Transport Model Calibration via Online Stochastic Batch Optimization

Calibrating agent-based models (ABMs) is computationally demanding, as traditional black-box optimization typically requires hundreds or thousands of independent simulation runs. To reduce this burden, we introduce an online calibration framework that estimates parameters within a single simulation run. The approach combines black-box optimization with stochastic batch optimization, a method widely applied in machine learning but not yet explored in ABM calibration. Using MATSim as a case study, we treat each simulation iteration as a stochastic batch, enabling incremental parameter updates as agents make decisions. This online calibration paradigm allows model parameters and agent behaviors to co-evolve, achieving convergence without restarting the simulation. We demonstrate the effectiveness of our method by calibrating utility function parameters in MATSim for a large-scale transportation scenario of Switzerland. Results show that mode shares align closely with observed data within a typical simulation timeframe, confirming the feasibility and efficiency of the approach. By embedding calibration directly into the simulation loop, our method opens new possibilities for real-time, scalable, and efficient calibration of complex ABMs.
Oct 20, 2026

When Momentum Helps Polyak--Ruppert Averaging

Polyak--Ruppert averaging gives SGD and momentum methods the same asymptotic covariance. We characterize how fast finite runs reach it and how far they can be parallelized. For strongly convex quadratics with additive noise, we prove an online--offline bridge: the empirical risk minimizer on the samples of a tail average is one Newton step from the tail-averaged query point of any online procedure. For SGD, heavy ball, and Nesterov's method with constant momentum, this step is a boundary term at the two ends of the tail and splits the gap to the offline estimator into center, covariance, and shape errors. Necessary and sufficient conditions show that, on the least curved direction, the center error sets the pace: SGD needs m≫κ2m\ggκ^2 rounds but momentum only m≫κm\ggκ, where κκ is the condition number, so at sample size NN the critical batch size grows from Θ(N/κ)Θ(\sqrt{N}/κ) to Θ(N/κ)Θ(\sqrt{N/κ}). The covariance error separates the momentum methods: heavy ball has relative variance excess Θ(κ3/2/m)Θ(κ^{3/2}/m) along the stiffest direction, whereas Nesterov has relative error O(κ/m)O(\sqrtκ/m) in every direction. The shape error is method-independent by a Berry--Esseen bound uniform in κκ and batch size, so confidence intervals are valid when the other two errors vanish. We further examine how the conclusions change under heavy-tailed or state-dependent noise and clipping, and establish a first-order comparison with ERM for nonlinear Nesterov averaging under explicit conditions.
Oct 17, 2026

Stochastic optimization methods through statistical whitening

We provide new statistical insights into designing stochastic optimization methods. By modeling the gradient via a normal distribution, we argue that the stochastic gradient should be whitened using its covariance. We give an online method for estimating the mean and variance of the gradients based on regularized likelihood or, equivalently, through a maximum a posteriori estimate. We then show how to use structured approximations to the covariance within this same framework, which includes diagonal and Kronecker-factored approximations. The diagonal approximation results in a method that is very closely related to Adam and performs as well in practice. The Kronecker approximation results in the new MN method, which is a variant of Shampoo and KL-Shampoo. We also recover Muon by applying this same statistical framework to the gradient direction rather than the full gradient. By combining this with a whitening step, we arrive at MN-Muon, a novel preconditioned version of Muon. Our experiments on GPT-2-type models at Chinchilla scale indicate that MND, the diagonal implementation of MN, outperforms both the Distributed Shampoo and the KL-Shampoo implementations in terms of stability, final validation loss and time taken. MND-Muon, the diagonal implementation of MN-Muon, improves on Muon in 21 of 24 paired GPT-small runs and achieves a lower best validation loss on GPT-medium, where it remains stable over the six tested learning rates. However, we found that NorMuon was comparable to MND-Muon and achieved a slightly lower validation loss on GPT-medium and at GPT-small batch 512 on FineWeb.
Oct 17, 2026

Near-Optimal Regret for Semi-Bandit Learning of Monotone Stochastic Problems

We consider the task of learning an (approximately) optimal policy for stochastic optimization problems where the true distributions are unknown. In each period, the algorithm plays a policy for the stochastic problem and observes semi-bandit feedback, i.e., it only receives new samples from the random variables that were selected by the policy. We obtain an algorithm that works for a large class of 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 O~(nT)\tilde{O}(\sqrt{nT}) 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.
Oct 16, 2026

A general recipe for data-adaptive anytime-valid envelopes for iterative algorithms

Most convergence guarantees for iterative stochastic algorithms are stated at a fixed iteration count and do not justify stopping at a data-dependent time. Recent anytime-valid envelopes do, but deterministic ones are typically too conservative for practical stopping, and existing data-adaptive ones are derived case-by-case, each concerned with a specific algorithm and a specific noise model and boundary construction. This paper provides a general recipe for sharp, data-adaptive anytime-valid envelopes for a large class of iterative algorithms. Our approach has two key steps: an optimization module derives a one-step recursion that performance measures of many such algorithms satisfy, reducing the error analysis to time-uniform concentration for predictably weighted sums of noise. Then, a statistical module ports the sub-ψψ condition to vector-valued processes, uniformly over predictable weights, and derives off-the-shelf boundaries via mixtures, stitching, and product betting martingales. Combining the two yields readymade envelopes for many iterative algoithms including but not limited to stochastic gradient descent (SGD), Oja's algorithm, temporal difference learning, Q-learning, and Bures-Wasserstein SGD, many with no prior data-adaptive anytime-valid guarantees. Specifically, for SGD, our framework recovers, often under weaker conditions, or significantly sharpens every existing envelope we are aware of. Our constructions come with explicit implementation details and are substantiated by numerical experiments.
Oct 16, 2026

Non-Parametric Optimization for Scalable Learning in Stochastic Decision Problems

Stochastic optimization (SO) plays a central role in decision-making under uncertainty. Among SO problems, time-varying stochastic optimization (TV-SO) is particularly important due to its applications in adaptive control and machine learning. Non-parametric approaches have been proposed for time-varying deterministic optimization; however, they have not been developed for their stochastic counterparts. This work addresses that gap by developing a stochastic variational framework based on Malliavin calculus. This framework yields non-parametric optimality conditions for SO problems with stochastic decisions and supports the design of a scalable deep-learning algorithm that is insensitive to the parameterization dimension. This algorithm, called the Stochastic Path Follower (SPF), is applied to two important problems under distribution drift, namely least-squares recovery and logistic regression. Experimental results show that the proposed approach outperforms state-of-the-art learning-based and gradient-based methods in both performance and scalability.
Oct 15, 2026

When is a better LLM worth paying for? Stochastic Optimization with Switching Mixed-Fidelity Oracles

Large language models (LLMs) are increasingly used upstream of decision-making to clean data, detect label errors, and reconstruct missing values. Yet LLM-assisted data curation creates a new operational tradeoff: higher-fidelity models and richer prompts can be substantially more expensive, while the value of this additional fidelity depends on the downstream optimization accuracy. This raises the central question of this work: when should one pay for a better LLM, given a specific downstream task at hand? We study this question through stochastic optimization with mixed-fidelity first-order oracles, which can have systematic bias and state-dependent variance. We develop two cost-aware algorithmic frameworks that allow adaptive switching between stochastic oracles. With known bias, the first meta-algorithm applies a restarted, cost-aware policy that adaptively selects oracle fidelity across optimization stages. Its cumulative cost is no larger than that of the best fixed oracle in hindsight and can be substantially smaller. With unknown bias, we develop a budgeted certification scheme that uses occasional trusted-gradient evaluations to certify the optimization progress and eliminate unsuccessful oracle sources, and show an explicit tradeoff between certification cost and delayed detection of biased sources. We provide concrete realizations of these meta-algorithms by applying biased stochastic gradient extrapolation (SGE) and recursive regularization under state-dependent noise as subroutines. Synthetic and LLM-completion experiments illustrate the qualitative switching behavior predicted by the theory: the adaptive policy skips several expensive LLM oracles and substantially reduces cumulative cost relative to fixed high-fidelity alternatives while achieving comparable accuracy.
Oct 14, 2026

Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent

Random reshuffling stochastic gradient descent (RR-SGD) is widely used for finite-sum optimization in machine learning. For convex LL-smooth components, recent work establishes convergence guarantees for an averaged iterate with component stepsizes as large as order 1/L1/L. However, the final iterate is a natural output in practice, and existing last-iterate guarantees in this setting require stepsizes that scale inversely with the number of components nn. We establish an expected objective-gap bound for the last iterate of standard RR-SGD on unconstrained problems with a constant component stepsize satisfying 0<η≲1/(L(1+log⁡(nK)))0<η\lesssim 1/(L(1 + \log(nK))), where KK is the number of epochs. By retaining the sampling bias at random comparison points, we remove the explicit 1/n1/n factor from the stepsize restriction. Combined with existing small-step bounds, our result matches the corresponding averaged-iterate convergence rate up to logarithmic factors.
Oct 13, 2026

Optimization for One, Feasibility for Most: Decoupling Optimization from Feasibility in Chance-Constrained Programs

Chance-constrained stochastic programs (CCSPs) require solutions that satisfy uncertain constraints with high probability. Standard approaches either embed scenarios directly into optimization by considering sample average approximation (SAA)-based reformulations, growing prohibitively expensive and often failing to find feasible solutions; or employ conservative reformulations that guarantee feasibility but sacrifice objective quality by design. We propose ACCESS (Adaptive Chance-Constrained Exploration via Structured Sampling), a structured sampling framework that decouples optimization from feasibility evaluation. First, high-quality candidate solutions are generated by solving many inexpensive single-scenario subproblems, avoiding sampling directly in the constrained high-dimensional solution space. Second, feasibility is assessed separately via large-scale batched simulation over a massive number of scenarios, which is naturally amenable to GPU parallelism. That reduces the search from a high-dimensional solution space to a two-dimensional parameter space controlling conservatism and scenario diversity; while concentrating on candidates near the feasibility boundary, where high-quality feasible solutions lie. We also introduce a variant, ACCESS(δδ), which provides certified feasibility guarantees with probability 1−δ1-δ. Experiments across three benchmark classes and five scenario distributions show that ACCESS matches or exceeds the best objective found by any method in nearly every setting, while ACCESS(δδ) is empirically feasible on every instance. The conservative reformulations remain several percent worse in objective, and SAA is frequently infeasible while taking an order of magnitude longer on the harder benchmarks.
Oct 13, 2026

Steering the Fidelity in State Preparation on Noisy Bosonic Systems with Risk-Seeking Optimization

In order to execute quantum algorithms on bosonic quantum computers, it is necessary to encode their inputs into a desired target quantum state, with a process called state preparation. In real settings, state preparation methods operate in stochastic scenarios, where the prepared state is represented as a mixed state, that is a probabilistic ensemble of pure states. Therefore, existing state preparation methods optimize a variational ansatz by averaging over all possible sequences of photon loss events contained in the prepared ensemble, yielding an output state which approximates the desired target with a certain average fidelity. Such an approach, however, does not take into account directly the distribution of fidelities across states in the ensemble. In this work, we aim to maximize the fidelity of only a subset of pure states sampled from the prepared ensemble, at the cost of reducing the average fidelity overall. This trade-off is relevant when the goal is to obtain high-fidelity states with a certain probability, rather than maximizing the average fidelity of the prepared ensemble. We borrow and adapt objective functions from risk-sensitive optimization, a framework that optimizes specific characteristics of a distribution rather than only its expectation, and that has been successfully applied in Reinforcement Learning. In the considered experimental settings, our results show that the infidelities of some pure states in the prepared ensemble can be reduced by up to four orders of magnitude when using risk-seeking objectives, compared to those achieved using the standard optimization of the average fidelity. Furthermore, we show that it is possible to control the trade-off between the probability of obtaining high-fidelity states and the lowest infidelity threshold reached, providing the flexibility to select the operating point that best suits a certain application.
Oct 13, 2026

Principled Design of Expected Improvement for Continuous Simulation Optimization

Expected improvement based on stochastic kriging (SK) surrogate is widely used in continuous simulation optimization, but unknown heteroscedastic noise makes three basic design choices consequential: the incumbent to define improvement, replication allocation, and final recommendation. Existing methods typically either assume the noise levels are known or choose these components separately through heuristic rules or empirical calibration. We instead derive a high-probability upper bound on the simple regret and systematically choose the three components within general rule classes to tighten this bound. We first establish a finite-sample confidence bound for the SK predictor as a foundation for the three design choices. Within general posterior-quantile rule classes, tightening the regret certificate selects a lower-quantile incumbent and an upper-quantile recommendation among sampled designs. The opposing quantiles reflect the different roles of exploratory experiments and the final implemented decision. Under mild conditions satisfied by common kernels, minimizing a tractable kernel-specific bound yields a logarithmic replication order. Based on these design choices, the resulting simple regret matches the existing results under known homoscedastic noise up to logarithmic factors. To our knowledge, this is the first simple-regret guarantee of this form for a continuous-domain EI-type simulation optimization method that learns unknown heteroscedastic variances through replications.
Oct 13, 2026

Bayesian Optimization of CVaR with Unknown Hyperparameters

We study Bayesian optimization of the Conditional Value-at-Risk (CVaR) of an expensive black-box function that depends on a decision and an environmental variable. Existing no-regret algorithms assume that the correct Gaussian process (GP) kernel and its hyperparameters are known. In practice, however, they must be estimated from limited data, often yielding a misspecified surrogate. This is especially damaging for CVaR because misspecification can distort the estimated tail-risk and thus lead to catastrophic decisions. We propose HE-CV-UCB, the first no-regret algorithm for CVaR Bayesian optimization with unknown GP hyperparameters. Given a finite candidate set containing a well-specified model, HE-CV-UCB adaptively eliminates those inconsistent with the observed data, actively queries where the survivors disagree, and returns a design that is robust across the surviving candidates. We prove that it attains cumulative regret matching the oracle rate of CV-UCB up to a factor depending only on the candidate set's size. Across synthetic benchmarks and three real-world applications, HE-CV-UCB achieves competitive performance and frequently outperforms existing CVaR Bayesian optimization methods.
Oct 13, 2026

Risk-Averse Inference-Time Diffusion Model Alignment with Finite-Sample Guarantees

Inference-time alignment steers diffusion models toward downstream objectives without costly fine-tuning, but existing methods typically optimize expected cost (or reward) without explicitly controlling tail risk. In this work, we propose a risk-averse framework for inference-time alignment of diffusion models that balances expected cost and Conditional Value-at-Risk (CVaR) under trajectory-level Kullback-Leibler regularization. We characterize the optimal path distribution and reverse transitions as functions of the CVaR threshold, reducing the alignment problem to a one-dimensional optimization problem over the threshold. We show that this one-dimensional optimization problem can be nonconvex in general, establish sufficient conditions for convexity, and introduce quadratic regularization to enable efficient derivative-free ternary search. Under suitable assumptions, we provide finite-sample guarantees for threshold optimization and value estimation, and combine them into a terminal total-variation bound relative to the regularized target under exact resampling. Experiments on synthetic data and image generation using Stable Diffusion demonstrate improved tail performance over risk-neutral baselines while maintaining competitive average cost.
Oct 12, 2026

Near-Optimal Regret Bounds for Monotone Stochastic Optimization under Semi-Bandit Feedback

Stochastic optimization models sequential decision-making under uncertainty, typically assuming known input distributions. When these distributions are unknown, \citet{agarwal2026semibandit} give an online-to-offline reduction for monotone stochastic optimization under semi-bandit feedback, where only probed variables are observed. Its expected regret relative to the offline guarantee is O~(nT)\widetilde O(n\sqrt T), where nn is the number of variables and TT the horizon. For optimal stopping and Pandora's box, \citet{liu2025improved} achieve O~(nT)\widetilde O(\sqrt{nT}) using problem-specific algorithms. Can a general online-to-offline reduction achieve this improved rate? We give such a reduction for strongly monotone stochastic optimization, answering the corresponding open question. Strong monotonicity is defined relative to the chosen offline algorithm. Our oracle-efficient reduction achieves O~(nT)\widetilde O(\sqrt{nT}) expected regret while preserving approximation guarantees for oracles satisfying the same condition. It combines Bernstein-type optimistic distribution estimates with a Hellinger stability bound for adaptive policy transcripts, aggregating squared marginal errors weighted by the executed policy's probing probabilities. The rate is optimal up to logarithmic factors for T≥nT\ge n, even under full feedback. Under monotonicity and uniformly bounded coordinate-wise variation, the same algorithm achieves O~(n3/4T)\widetilde O(n^{3/4}\sqrt T) expected approximation regret, improving the previous linear dependence on nn. The exponent 3/43/4 is sharp for its ordinary regret over instances and exact oracle choices. Our framework applies to prophet inequality, Pandora's box, best-of-KK selection, stochastic knapsack, stochastic orienteering, and stochastic submodular maximization.
Oct 12, 2026

Minimax Optimality of Shampoo for Nonstationary Stochastic Optimization

We develop a comprehensive theoretical analysis of Matrix Shampoo for tracking time-varying optima in nonstationary stochastic optimization. We derive finite-horizon high-probability bounds for average tracking error that disentangle initialization, optimizer drift, momentum-induced drift penalty, stochastic noise, and adaptive preconditioning, with explicit dependence on momentum parameter β1β_1 and stabilization parameter ε\varepsilon. These bounds reveal an explicit drift--noise and stability--geometry tradeoffs: noise-dominated regimes favor larger β1β_1, which provides stronger first-moment averaging and greater suppression of gradient noise, whereas drift-dominated regimes favor smaller β1β_1, allowing faster adaptation to moving optimizer. Larger ε\varepsilon reduces the preconditioner-perturbation term while weakening Shampoo's ability to exploit matrix geometry, thereby reducing adaptivity. We establish a matching minimax lower bound under squared path-variation constraint, proving the information-theoretic optimality of Shampoo over the class of causal optimization procedures. Under a constant stepsize, we establish high-probability bounds for the average projected stationarity gap along general nonstationary nonconvex objectives. We validate our theoretical findings on both synthetic and multiple real-world problems.
Oct 12, 2026

Efficient Preconditioned Optimization Methods with Frequent Directions

Adaptive optimization methods have received considerable attention in recent years due to their strong empirical performance. However, they generally require maintaining a preconditioning matrix, which incurs prohibitive computational overhead in large-scale applications. To address these limitations, we investigate the acceleration of preconditioned optimization methods through frequent directions (FD), a widely used matrix sketching technique. We first propose FTSL by integrating FD with adaptive subgradient methods under the primal-dual framework and adding back the cumulative information discarded by FD. FTSL obtains a tighter regret bound than existing state-of-the-art results. We then apply a doubling trick that further reduces the time complexity of FTSL, while maintaining the same regret guarantee. We also consider optimization over matrix-valued decision variables and exploit their structural properties to construct sketched preconditioners. We develop FTSL-Shampoo by adapting FD to Shampoo and give a novel analysis under the primal-dual framework. To further mitigate its computational complexity, we design one-sided variants of FTSL-Shampoo under both mirror descent and primal-dual frameworks. Our algorithms not only reduce the computational cost of FTSL-Shampoo, but also achieve tighter regret bounds. We extend our methods to offline stochastic convex optimization and exploit smoothness to achieve faster convergence rates. Finally, we introduce practical variants of our algorithms and empirically demonstrate their efficiency and effectiveness across a broad range of tasks.
Oct 9, 2026

Partially Informed Stochastic Optimization via Zeroth-Order Residual Tracking

Many optimization problems provide direct access to only part of the gradient, while the remaining component must be inferred from function evaluations. This structure arises in performative prediction, performative reinforcement learning, and bilevel optimization with a black-box lower level. We introduce Partially Informed Stochastic Optimization (PISO), which combines the available gradient component with a running estimate of the residual. By centring each zeroth-order observation on this estimate, PISO makes the variance due to random probing depend on the tracking error rather than the residual's magnitude. This yields a randomized sketch iteration with an explicit contraction mechanism and a principled interpretation of momentum. For smooth nonconvex objectives, we establish convergence guarantees that depend on the residual's variation and initial magnitude, without requiring a uniform bound on the unavailable gradient component. With independently sampled function evaluations and Gaussian or spherical probes, PISO attains leading function-evaluation complexities of O(d2ε−6)O(d^{2}\varepsilon^{-6}) under Lipschitz gradients and O(d2ε−5)O(d^{2}\varepsilon^{-5}) under an additional Lipschitz-Hessian assumption. These rates require only one probe direction, two function samples, and one known-component sample per update. The analysis also quantifies how batching trades observations for fewer deployments. Across five settings, PISO variants improve on the tested baselines with comparable oracle access in three, reach a comparable solution faster in bilevel routing, and perform best among methods without response-model derivatives in performative reinforcement learning.
Oct 9, 2026

Geometry-Aware Multi-Objective Optimization: Norm-Constrained Oracles with Entropic Weight Updates

Multiple-gradient descent is typically formulated in Euclidean geometry, whereas matrix-aware optimizers use directions induced by other norms. We analyze a single-loop multi-objective method combining a norm-constrained linear minimization oracle with entropic updates of task weights. For any finite-dimensional norm pair, we establish an O(T−1/2)O(T^{-1/2}) ergodic stationarity rate in the deterministic setting, deriving the required trajectory gradient bound from smoothness and lower-boundedness in the unregularized case. With stochastic gradients and a bounded-gradient assumption, one persistent blended-gradient momentum buffer yields an O(T−1/4)O(T^{-1/4}) rate whose leading term has no explicit dependence on the number of tasks. We also establish static regret for the inner weighting objective on arbitrary bounded gradient sequences and, with entropy regularization and a weight floor, iteration-wise inner-gap control after burn-in while retaining ergodic stationarity, conditional on a trajectory gradient bound. The optimal blended gradient can be nonunique in spectral and sign geometries, motivating a selection-independent inner gap. Our analysis extends the spectral construction studied by concurrent MOON to general norms. Experiments compare the method with existing multi-task optimizers and examine its oracle, weighting, and momentum choices.
Oct 9, 2026

Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets

Recent results [arXiv:2602.04378, arXiv:2602.22608] establish lower bounds for optimization over strongly convex sets, covering specified Frank-Wolfe updates and unrestricted deterministic first-order linear minimization oracle (LMO) methods, respectively. Neither establishes a lower bound for unrestricted randomized methods. We close this gap by proving an Ω(Ldiam⁡(S)2/T2)Ω(L\operatorname{diam}(S)^2/T^2) distributional lower bound after TT oracle calls for randomized first-order LMO methods over strongly convex sets, with final outputs required to be feasible on every instance and seed. While our construction reuses the family of [arXiv:2602.22608], our proof characterizes the conditional distribution of the hidden permutation after adaptive queries and bounds the expected decrease of a combinatorial statistic controlling optimizer variance. We also show that the same error threshold holds with probability at least 3/43/4 and yields a stopping-time tail bound. Our construction uses the same curvature-diameter coupling as [arXiv:2602.22608]. Comparisons with the upper bound [arXiv:1406.1305] must account for this coupling. Separately, we show that prescribed slow exact-line-search Frank-Wolfe trajectories can locally amplify sufficiently small initialization errors, corresponding to roughly one extra bit of initialization accuracy per iteration, and that initializations satisfying a particular eventual slow envelope have planar measure zero.