Source-linked AI summary
A stochastic subgradient method with optimal failure exponent
Bart P. G. van Parys
TL;DR
The paper asks how to minimize the worst-case probability of missing a fixed accuracy target when stochastic subgradient noise is only known to be conditionally sub-Gaussian. It uses a uniformly averaged harmonic schedule and an exponential supermartingale certificate, and proves that the resulting failure exponent is optimal. In the small-noise limit, the setting reduces to an adversarial-error model.
Problem
The paper seeks algorithms that minimize the worst-case probability of a suboptimality gap reaching fixed accuracy ε when the noise law is unknown but conditionally sub-Gaussian.
Source: §1 · pp. 1–2Method
A uniformly averaged harmonic step schedule is analyzed using an adapted exponential supermartingale certificate.
Source: §1 · p. 3, §3.1 · p. 12Results
The stochastic harmonic schedule attains exponent ε^2N(1+o(1))/(2R^2s^2), and no algorithm exceeds this leading order.
Source: §1 · p. 3, §4 · p. 19, §7 · p. 24Takeaways & Limitations
At fixed horizon, the small-noise limit becomes the adversarial-error model, where the adversarial harmonic schedule is near-optimal within the stated cone-constrained methods.
Source: §7 · pp. 24–25The analysis is for nonsmooth optimization; smooth convex optimization and noise variance that grows with gradient size remain open directions.
Source: §7 · p. 25
Abstract
from arXiv · showhide
Fix a target accuracy $\varepsilon$, a gradient-noise level $s$, and a horizon $N$. We wish to design algorithms which minimize the probability of observing a suboptimality gap which exceeds the target accuracy, i.e., $\mathcal{E}_N = -\log \sup_{f,P} \mathbb{P}_P(f(x_A) - f_\star \ge \varepsilon)$, with the noise law $P$ known only to be sub-Gaussian. We single out a uniformly averaged schedule which is harmonic (of the form $h_k = R^2/(\varepsilon (N+m-k))$) and prove, via an optimized exponential supermartingale argument, that it attains the optimal exponent $\mathcal{E}_N^\star = \varepsilon^2 N (1+o(1))/(2R^2 s^2)$. Optimality is certified by a matching impossibility result: under Gaussian noise, a gradient-masking change of measure caps the exponent of every algorithm at the same leading order. In a small-noise limit, our setting degenerates into the adversarial-error model of G\"osgens and van Parys (2025) for subgradient methods.
1 Introduction
The paper studies worst-case failure probabilities at a fixed target accuracy under conditionally sub-Gaussian stochastic subgradients. It identifies a uniformly averaged harmonic schedule with an optimal failure exponent, relates its small-noise limit to an adversarial-error model, and contrasts this objective with expected-gap analysis.
1 Introduction
- The design objective is to maximize the exponent governing the worst-case probability that the returned point's suboptimality gap reaches the fixed target ε, rather than minimize expected gap.The noise law is unknown but must obey the stated conditional sub-Gaussian assumption.Source: §1 · pp. 1–2
- Constant-step schedules can be suboptimal for this criterion: the cited constant schedule has a linear exponent guarantee, while constant schedules reach at most 3/4 of the optimum.The introduction distinguishes exponent optimization from expected-gap optimization, for which a constant schedule can be minimax-optimal up to constants.Source: §1 · pp. 2–3
- The uniformly averaged stochastic harmonic schedule uses steps proportional to R^2/(ε(N+m−k)) and attains the optimal exponent at every fixed noise level.An adapted exponential supermartingale with recursively generated tilts certifies the guarantee.Source: §1 · p. 3
- At fixed horizon, the small-noise limit reduces the stochastic problem to the adversarial-error model of [13], with its rate determined by the most likely corruption path.The introduction compares the stochastic harmonic schedule with a related adversarial harmonic schedule matched to the target accuracy.Source: §1 · pp. 4–5
1.1 Related work
- Related work differs in regime: studies a last iterate for smooth strongly convex objectives under one known noise law, while [3] [2] study fixed-threshold non-convex problems.The paper also translates exponent guarantees into confidence-level query bounds; its harmonic schedule achieves the stated leading query constant, while no algorithm can improve that constant.Source: §1.1 · p. 5
1.2 Outline
- The paper's roadmap pairs the supermartingale achievability proof with a Gaussian gradient-masking impossibility result, then establishes the fixed-horizon adversarial small-noise limit.The impossibility result caps every algorithm at the same leading exponent attained by the stochastic harmonic schedule.Source: §1.2 · p. 6
2 Classical schedules
The classical schedules considered here do not attain the optimal failure exponent: constant steps with uniform averaging face a universal leading-order cap, while the anytime schedule incurs an additional logarithmic factor. Their negative results use simple one-dimensional objectives and noise laws tailored to the algorithm.
Lower-bound approach
- The negative results use one-dimensional absolute-value objectives and algorithm-tailored noise, transferring failure to the honest Gaussian law by change of measure.The resisting instances have slope at most L and a minimizer within distance R of the starting point.Source: §2 · pp. 6–8
Constant schedules
- For sufficiently small fixed scaling h, a constant schedule can have zero failure exponent on a resisting instance, even with a noiseless oracle.The construction yields an averaged-iterate gap of ε/(2h), which is at least ε when h ≤ 1/2.Source: §2 · p. 8
- Every constant step size with uniform averaging has a failure-exponent cap of 3/4 of the leading optimal coefficient, uniformly over the step size.The cap applies even when the step size may depend on the horizon and problem parameters.Source: §2 · p. 10
Anytime schedule
- The anytime schedule retains an O(N) exponent barrier and incurs an additional log(N + 1) factor relative to the expectation-optimal step sizes.Its steps decay as h/(k + 1).Source: §2 · p. 10
3 An optimized schedule
The stochastic harmonic schedule with uniform output weights attains the leading-order exponent ceiling. An optimized exponential supermartingale certificate proves the guarantee, and the schedule's expected gap remains on the scale of the target even without noise.
3 An optimized schedule
- For N ≥ 2, the stochastic harmonic schedule (5) with uniform output weights attains exponent ε^2N/(2R^2s^2)(1 + o(1)) asymptotically for every noise law obeying (1).Source: §3 · p. 12
3.1 An exponential supermartingale certificate
- An exponential supermartingale combines pathwise subgradient inequalities with conditional noise moment bounds, using freely chosen multipliers to certify the failure exponent.A Chernoff reduction first converts the failure probability into an exponential moment of accumulated suboptimality gaps.Source: §3.1 · pp. 12–14
- The certificate's schedule-independent ceiling is ε^2(N + 1)/(2R^2s^2), and the stochastic harmonic schedule matches it to leading order.The optimized schedule therefore asymptotically optimizes the certificate; the paper later establishes a matching impossibility result.Source: §3.1 · p. 16
3.2 Expected suboptimality gap
- Even with zero noise, the harmonic schedule's gap is Ω(ε) on a resisting instance, so it does not drive expected suboptimality below the target scale.The result is shown for f(x) = ε/(2R)|x − x⋆| with x⋆ = x0 + R.Source: §3.2 · p. 17
4 A gradient masking impossibility result
A Gaussian gradient-masking construction yields an impossibility bound for every algorithm in the oracle model. Together with the stochastic harmonic schedule's guarantee, it pins down the optimal leading-order failure exponent.
Gradient masking
- The masking construction makes observations have the same joint law on two opposing instances, so the output carries no information about which instance is present.A change of measure transfers the resulting failure probability from the masking law to the honest Gaussian noise law.Source: §4 · p. 18
Matching impossibility bound
- Under independent Gaussian noise, no algorithm exceeds the leading-order exponent ε^2N/(2R^2s^2), which the stochastic harmonic schedule attains.The theorem assumes ε ≤ RL; its bound includes lower-order terms beyond the leading constant.Source: §4 · pp. 18–19
5 The small–noise limit s ↓0
At fixed horizon, the small-noise regime makes failure a rare event whose exponent is governed by the least-energy corruption that causes failure. The adversarial harmonic schedule nearly attains the best such corruption threshold among algorithms satisfying the cone condition.
5 The small–noise limit s ↓0
- At fixed N as s decreases to zero, failure becomes rare and its exponent grows like Λ(ε)^2/(2s^2).The relevant perturbations are the most likely noise paths capable of causing failure.Source: §5 · p. 19
- At a fixed horizon, the adversarial setting is precisely the small-noise limit of the stochastic one.The noise level determines how improbable a path of a given energy is.Source: §5 · p. 20
- Λ(ε) is the least energy of a corruption path that makes the algorithm fail, linking its small-noise exponent to an adversarial threshold.Proposition 3 reduces the stochastic exponent question to the adversarial setting.Source: §5 · p. 20
- The adversarial harmonic schedule is optimal among methods satisfying the cone condition up to a relative O(log N/N) loss in guaranteed budget and small-noise rate.The conclusion applies to methods satisfying condition (20).Source: §5 · p. 24
6 Numerical illustration
A Monte Carlo experiment on a resisting instance compares four schedules with the theorem certificate and universal failure-probability floor. The stochastic harmonic schedule decays most steeply among the tested schedules, close to the predicted exponent.
6 Numerical illustration
- On a logarithmic scale, the stochastic harmonic schedule’s failure probability decays linearly in N at a rate close to ε^2/(2R^2s^2), stays below Theorem 1’s certified probability, and runs roughly parallel to Theorem 2’s worst-case floor at larger horizons.Source: §6 · p. 24
- The two constant-step schedules decay at visibly flatter rates than the stochastic harmonic schedule and run close together over the tested horizon.The schedules compared are expectation-optimal constant steps and matched constant steps.Source: §6 · p. 24
- The anytime schedule decays at the flattest rate in the experiment.The experiment uses independent Gaussian noise on the resisting instance with x0 = 0 and x⋆ = R.Source: §6 · p. 24
7 Conclusion
The stochastic harmonic schedule achieves the optimal asymptotic failure exponent for the stated nonsmooth setting. In the small-noise limit, the problem reduces to an adversarial model, while gradient-scaled noise and smooth optimization remain future directions.
7 Conclusion
- The stochastic harmonic schedule’s failure exponent is ε^2N/(2R^2s^2)(1 + o(1)), optimal among adaptive or randomized algorithms.The conclusion concerns nonsmooth convex functions with bounded subgradients corrupted by sub-Gaussian noise.Source: §7 · p. 24
- In the small-noise limit, the stochastic problem collapses to the adversarial model of [13], whose harmonic schedule attains the best corruption budget up to relative O(log N/N) among methods satisfying a natural cone condition.The adversarial budget is the largest corruption budget for which an algorithm can keep the gap below ε.Source: §7 · pp. 24–25
- The analysis leaves gradient-scaled noise and convex smooth optimization open; in the noiseless smooth setting, the optimal method uses momentum outside the memoryless iterate class.Source: §7 · p. 25
AI Use Statement
The manuscript used Claude for copy editing and brainstorming, while the author takes responsibility for all results, proofs, and their verification.
AI Use Statement
- Claude was used for copy editing and brainstorming, while the author remains responsible for all results, proofs, and their verification.Source: AI Use Statement · p. 25