acceptodds
Under review as a conference paper at ICLR 2027

Comparator-Uniform Dynamic Regret under Heavy-Tailed Noise

Abstract

Existing high-probability guarantees for online convex optimization with heavy-tailed gradients fix the comparator before the interaction, may pay an adaptation logarithm in the horizon, and require the horizon as an input. We address these three issues on a bounded convex set with adaptively chosen, non-clairvoyant convex Lipschitz losses. The learner receives one stochastic gradient per round, and the noise is assumed only to have a bounded conditional -th central moment for , so its variance may be infinite. Our algorithm aggregates clipped online-gradient-descent experts on a grid of learning rates anchored at the static statistical scale. Each expert uses a threshold tied to its step size. A per-expert bias offset preserves the supermartingale property of the aggregate wealth, while an auxiliary descent sequence used only in the analysis handles the noise residuals. This sequence turns the comparator-dependent noise term into a martingale along a predictable direction without requiring an additional sample. Consequently, one event of probability covers every prefix and every comparator path, including paths chosen from the complete feedback record. The resulting regret combines a square-root term in the horizon and path-confidence complexity with a heavy-tail term scaling as and the same complexity to exponent . The bound contains no additional horizon, dimension, or path-adaptation logarithm. A doubling wrapper gives an anytime version with an iterated-logarithm cost, while the noiseless case recovers the deterministic path-length rate. Self-contained lower bounds match the heavy-tail exponents in path length and confidence and identify the remaining gap in the deterministic term.

Primary area:
learning theory
Keywords:
online convex optimization, dynamic regret, heavy-tailed gradients

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_kW5zOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper addresses online convex optimization (OCO) over a bounded convex domain with adaptively chosen, non-clairvoyant Lipschitz losses under heavy-tailed stochastic gradient noise satisfying only a bounded conditional pp-th central moment for p∈(1,2]p \in (1, 2]. The authors propose Bias-Compensated Multi-Rate Clipped OGD (BC-MW-OGD), which aggregates a geometric step-size grid of projected clipped OGD experts using a single stochastic gradient query per round, step-size-coupled clipping thresholds (τi=D/ηi\tau_i = D/\eta_i), and a per-expert bias offset (bi=Dβ(τi)b_i = D\beta(\tau_i)) inside a learning-rate-tilted Prod wealth update. By combining this bias-compensated supermartingale aggregation with an analysis-only auxiliary descent sequence and a geometric prior anchored at the static statistical scale, the paper establishes a time- and comparator-uniform high-probability dynamic regret bound of O(GDT(An+log⁡(1/δ))+σDT1/p(An+log⁡(1/δ))(p−1)/p)O\big(GD\sqrt{T(A_n + \log(1/\delta))} + \sigma D T^{1/p}(A_n + \log(1/\delta))^{(p-1)/p}\big) that holds on a single event of probability at least 1−δ1-\delta simultaneously for all prefixes and all hindsight comparator sequences, along with an oblivious doubling wrapper for anytime operation and matching lower bounds for the heavy-tailed noise term under gradient-only feedback.

Critical strengths
  1. Comparator-Uniform High-Probability Dynamic Regret via Auxiliary Descent: By introducing an analysis-only auxiliary descent recursion driven by the centered clipped noise residual, the analysis decouples the martingale noise direction from data-dependent comparator trajectories, absorbing arbitrary hindsight comparator paths into a deterministic path-length potential on a single probability-(1−δ)(1-\delta) event without incurring dimension-dependent covering numbers.

  2. Bias-Compensated Multi-Rate Aggregation Under Heterogeneous Clipping: Subtracting the exact per-expert clipping bias bound inside each expert's Prod wealth recursion elegantly restores the tilted-weight drift cancellation across heterogeneous clipping thresholds sharing a single stochastic gradient sample per round, preserving the nonnegative supermartingale property of the total wealth and avoiding a union bound over the expert grid.

  3. Elimination of Adaptation Logarithms and Parameter-Oblivious Anytime Operation: Anchoring the step-size grid at the static statistical scale with a decaying geometric prior absorbs the expert encoding cost directly into the path-confidence complexity (avoiding log⁡log⁡T\log\log T overhead and 1/(p−1)1/(p-1) blow-up as p↓1p \downarrow 1), while the coupled thresholds allow a single run to be valid across all δ∈(0,1)\delta \in (0, 1) and seamlessly wrap into an oblivious doubling schedule that recovers the deterministic minimax rate when σ=0\sigma = 0.

  4. Tight Information-Theoretic Lower Bounds and Self-Contained Rigor: The mathematical proofs are completely self-contained from first principles, and the joint path-length and confidence-level lower bound matches the heavy-tailed upper-bound term σDT1/p(AT+log⁡(1/δ))(p−1)/p\sigma D T^{1/p}(A_T + \log(1/\delta))^{(p-1)/p} up to universal constants while cleanly isolating the remaining AT+log⁡(1/δ)\sqrt{A_T + \log(1/\delta)} versus AT\sqrt{A_T} gap in the deterministic term.

Critical weaknesses
  1. Prior Knowledge of Problem Scale Parameters and Literature Comparison Nuances: Unlike parameter-free heavy-tailed methods, the proposed algorithms require prior knowledge of the scale parameters (D,G,σ,p)(D, G, \sigma, p) to calibrate the static anchor, clipping thresholds, and bias offsets; please consider highlighting this trade-off in Table 1 and Section 1, as well as refining Table 1 and Section 1 to clarify that prior deterministic universal dynamic regret methods already hold uniformly over all hindsight paths and that fixed step-size OGD achieves O(ATT)O(A_T\sqrt{T}) without tuning to PTP_T (Reference Paper: Parameter-Free Regret in High Probability with Heavy Tails, Jiujia Zhang and Ashok Cutkosky, 2022; Reference Paper: Parameter-Free Dynamic Regret under Heavy-Tailed Noise, Vaneet Aggarwal, 2026; Reference Paper: Online Convex Programming and Generalized Infinitesimal Gradient Ascent, Martin Zinkevich, 2003; Reference Paper: Adaptive Online Learning in Dynamic Environments, Lijun Zhang, Shiyin Lu, and Zhi-Hua Zhou, 2018; Reference Paper: Adaptivity and Non-Stationarity: Problem-Dependent Dynamic Regret for Online Convex Optimization, Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou, 2024).

  2. Omission of Heavy-Tailed Dynamic Baselines and the Anytime Algorithm in Experiments: The empirical evaluation compares BC-MW-OGD only against standard OGD, single-rate clipped OGD, and unclipped Ader, and only evaluates the finite-horizon Algorithm 1; the authors might consider including a recent one-query heavy-tailed dynamic OCO baseline and evaluating the proposed ANYTIME BC-MW-OGD (Algorithm 2) to empirically quantify both the advantage over heavy-tailed dynamic competitors and the practical cost of doubling restarts (Reference Paper: Parameter-Free Dynamic Regret under Heavy-Tailed Noise, Vaneet Aggarwal, 2026).

  3. Missing Generative Specifications for Synthetic Experiments and the Two-Threshold Drift Example: Although the main text and Figure 2 caption repeatedly reference an explicit two-threshold heavy-tailed distribution and closed-form uncompensated wealth drift identity, its mathematical specification is omitted from the paper, as are the exact generative formulas for the 5D symmetric/asymmetric Pareto noise and the oblivious/evasive target trajectories in Section 6; please consider providing these explicit definitions and clarifying the O(log⁡T)O(\log T) per-round projection and memory complexity of the ensemble.

Questions for authors

Please see the weaknesses.

2 comments

Thank you for recognizing the soundness of our results and the value of the comparator-uniform analysis. We address the three concerns below.

Scale knowledge and comparison with prior work

BC-MW-OGD uses D,G,σ,pD,G,\sigma,p to calibrate clipping and bias compensation. Valid upper bounds suffice for D,G,σD,G,\sigma. This calibration gives one high-probability event for every prefix and every hindsight comparator path. The anytime algorithm adapts to unknown path length and horizon, and uses no confidence input. The lower bound matches the heavy-tail term in both path length and confidence.

Zhang and Cutkosky [1] provide parameter-free high-probability static regret. Aggarwal [2] provides parameter-free expected dynamic regret. Our result provides high-probability dynamic regret uniformly over paths selected from the complete feedback record. The calibrated scales support this stronger probability guarantee.

Deterministic universal dynamic-regret bounds already hold uniformly over hindsight paths [3–5]. For OGD, choosing η≍D/(GT)\eta\asymp D/(G\sqrt T) gives O(GDATT)O(GDA_T\sqrt T) without knowing PTP_T [3]. Tuning η\eta to PTP_T sharpens this to O(GDTAT)O(GD\sqrt{TA_T}). Ader [4] achieves the sharper rate without knowing PTP_T. Our contribution extends uniform hindsight evaluation to heavy-tailed stochastic feedback through a comparator-independent probability event.

Heavy-tailed dynamic baseline and anytime evaluation

We compare directly with the restarted AdaGrad and adaptive master of Aggarwal [2], using Eqs. (4.1)–(4.7). It receives T,DT,D and uses no G,σ,pG,\sigma,p. The experiments use the same environments and noise seeds as Section 6, with T=65536T=65536, A=8A=8, and 1000 runs per setting. Entries below are 95th-percentile dynamic regret.

TargetNoiseAggarwal [2]BC-MW-OGDAnytime BC-MW-OGD
DriftingSymmetric1427.4485.1770.0
DriftingAsymmetric1702.8554.6836.3
EvasiveSymmetric793.8469.9772.7
EvasiveAsymmetric1321.9834.41118.7

BC-MW-OGD reduces the 95th-percentile regret by 36.9%–67.4% relative to [2]. The anytime version also improves on [2] in all four settings. Its 95th-percentile regret is 1.34–1.64 times that of the finite-horizon version, quantifying the observed cost of removing the horizon input. These results support both the heavy-tail aggregation mechanism and its practical anytime extension.

Exact experimental definitions, drift identity, and computational cost

For the noise, let Pr⁡(Z>z)=z−α\Pr(Z>z)=z^{-\alpha} for z≥1z\ge1, with α=1.6\alpha=1.6 and p=1.5p=1.5. Let UU be uniform on the unit sphere in R5\mathbb R^5, independently of ZZ. The symmetric noise is $ \xi=\sigma\left(\frac{\alpha-p}{\alpha}\right)^{1/p}ZU. $ For a fixed unit vector ee, define μ=α/(α−1)\mu=\alpha/(\alpha-1) and c=E∣Z−μ∣pc=\mathbb E|Z-\mu|^p. The asymmetric noise is $ \xi=\sigma c^{-1/p}(Z-\mu)e. $ Each draw is independent of the past. Both laws have conditional mean zero, pp-th moment σp\sigma^p, and infinite variance. Here σ=1\sigma=1. Methods share the same noise draws within each setting.

For the targets, let q1,q2q_1,q_2 be fixed orthonormal vectors obtained by QR decomposition of a 5-by-2 standard Gaussian matrix. Set r=0.7r=0.7, v=D(A−1)/Tv=D(A-1)/T, and ω=v/r\omega=v/r. In both environments, $ \theta_t=r(q_1\cos\phi_t+q_2\sin\phi_t), f_t(x)=G|x-\theta_t|. $ The oblivious target uses ϕt=(t−1)ω\phi_t=(t-1)\omega. For the evasive target, ϕ1=0\phi_1=0 and, for t≥2t\ge2,

\phi_t=\phi_{t-1}+\omega\operatorname{sgn}+ \bigl(\operatorname{wrap}(\phi{t-1}-\psi_t)\bigr).$$ Here $\operatorname{wrap}$ returns the principal angle and $\operatorname{sgn}_+(s)=1$ for $s\ge0$ and $-1$ otherwise. This rule uses the committed decision before drawing the current noise. Each path has total variation at most $v(T-1)$. For Figure 2, take $\mathcal X=[-1,1]$, $D=2$, $G=\sigma=1$, $p=2$, and $g_t=0$. Use thresholds $(\tau_1,\tau_2)=(4,8)$ and the centered two-point law $$\Pr(\xi=16)=\frac1{1024}, \Pr\left(\xi=-\frac{16}{1023}\right)=\frac{1023}{1024}.$$ It satisfies $\mathbb E\xi=0$ and $\mathbb E\xi^2=256/1023 < 1$. Writing $m_i=\mathbb E C_{\tau_i}(\xi)$ gives $m_1=-3/256$ and $m_2=-1/128$. For $a_i=\lambda_iw_i$, the uncompensated drift is exactly $$\mathbb E_{t-1}[W_{t+1}-W_t] =\frac{a_1a_2}{a_1+a_2}(z_1-z_2)(m_2-m_1).$$ At $z=(1/2,-1/2)$, $w=(1/2,1/2)$, and $\lambda=(1/32,1/64)$, this drift equals $1/49152>0$. The prescribed offsets $b=(1,1/2)$ change it to $-959/49152 < 0$. Starting both experts at zero, one negative observation also gives $z_1-z_2=4/1023>0$, so positive uncompensated drift occurs from common initialization as well. Finally, $N\le1+\lfloor\log_2T\rfloor$. Each round uses one stochastic gradient query, $N$ projections, and $O(dN)$ additional arithmetic. Storage is $O(dN)$. Thus the ensemble uses $O(\log T)$ projections and $O(d\log T)$ memory, or $O(\log T)$ stored $d$-dimensional vectors. The auxiliary descent sequence appears only in the proof. **References** [1] Jiujia Zhang and Ashok Cutkosky. Parameter-Free Regret in High Probability with Heavy Tails. NeurIPS, 2022. [2] Vaneet Aggarwal. Parameter-Free Dynamic Regret under Heavy-Tailed Noise. arXiv:2607.27073v3, 2026. [3] Martin Zinkevich. Online Convex Programming and Generalized Infinitesimal Gradient Ascent. ICML, 2003. [4] Lijun Zhang, Shiyin Lu, and Zhi-Hua Zhou. Adaptive Online Learning in Dynamic Environments. NeurIPS, 2018. [5] Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Adaptivity and Non-Stationarity: Problem-Dependent Dynamic Regret for Online Convex Optimization. JMLR, 2024.
Reviewer_5XWFOpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The authors propose an online optimization method called BC-MW-OGD under heavy-tailed gradient noise; a dynamic regret bound is provided and independent of the comparator with high probability. In addition, the bound does not depend on additional horizon dimension, or path-adaptation logarithm.

Critical strengths

Existing dynamic bounds assume that the comparator sequence is fixed before the interaction; the authors relax this assumption. The authors provide the dynamic regret bound under a very general setting with an almost similar order of bounds compared to more restrictive existing methods.

Critical weaknesses

I find this paper a bit hard to follow. There are a lot of notations used without introduction, especially in the related work section. The authors do not explain the meaning of the proposed method BC-MW-OGD until section 4. I think the presentation of this paper is not very clear.

Questions for authors

The meaning of downarrow is not clear., e.g., p downarrow 1 on page 7.

1 comment

Thank you for recognizing the technical soundness of our results and the value of allowing comparator paths to be chosen after the interaction. We explain the notation, method, and limiting regime below.

Notation in the related-work section

In the rate comparisons, TT is the number of rounds, DD bounds the decision-set diameter, GG bounds the true gradients, and σ\sigma measures the noise scale. The moment order is p∈(1,2]p\in(1,2]. We use dd for the dimension and τ\tau for a clipping threshold. For a comparator path u1,…,uTu_1,\ldots,u_T, $ P_T=\sum_{t=2}^T|u_t-u_{t-1}|, A_T=1+P_T/D. $ Thus PTP_T measures total comparator movement, and ATA_T is its normalized complexity. A static comparator has AT=1A_T=1. The remaining shorthand is $ h=\log(4/\delta), q=(p-1)/p, $ where δ\delta is the failure probability. These quantities describe how regret depends on comparator movement, noise, and confidence.

Meaning of BC-MW-OGD

BC-MW-OGD denotes Bias-Compensated Multi-Rate Clipped Online Gradient Descent. Each component has a specific role. Multiple step sizes adapt to unknown comparator movement. Clipping controls large gradient observations under heavy tails. Bias compensation corrects the effect of different clipping thresholds on the aggregation weights.

All experts reuse one raw gradient sample per round. The method requires neither the comparator path nor its length. The confidence level is used only in the analysis.

How the method leads to the main guarantee

Two obstacles explain the design. Different clipping thresholds introduce different biases across experts. Our compensation makes the aggregate wealth a nonnegative supermartingale, so its conditional expected value cannot increase. A comparator chosen after the run creates a second obstacle because it can depend on future noise. An auxiliary descent sequence moves this dependence into a deterministic path bound. This sequence exists only in the proof and needs no extra gradient query.

Together, these steps give one event of probability at least 1−δ1-\delta that covers every comparator path and every prefix. At the design horizon TT, the regret has the rate $ GD\sqrt{T(A_T+h)} +\sigma DT^{1/p}(A_T+h)^{(p-1)/p}. $ The first term captures tracking difficulty, and the second captures gradient noise. Theorem 1 gives explicit constants without an additional horizon, dimension, or path-adaptation logarithm. Theorem 2 removes the horizon input at an iterated-logarithm cost. The lower bound matches the path and confidence exponents of the noise term.

Meaning and significance of p↓1p\downarrow1

The notation p↓1p\downarrow1 means that pp approaches 11 from above, with p>1p>1 throughout. Values such as 1.51.5, 1.21.2, and 1.11.1 illustrate this direction. Smaller pp makes the moment assumption weaker and allows more severe noise.

On page 7, the statement means that the constants 146 and 160 remain bounded as pp approaches 11. They contain no factor such as 1/(p−1)1/(p-1). The rate still reflects the harder problem through T1/pT^{1/p}, which approaches TT. Thus the constants remain controlled even near the boundary of the assumed moment range.

Reviewer_SpS4OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

In summary, the paper studies the dynamic regret in online convex optimization under heavy-tailed losses. Concisely, the contributions are focused on a high probability bound that holds simultaneously (not individually as I understand it) for all comparator sequences. The validation is through the proofs of the theoretical findings and the experiments.

Critical strengths

The submission is clear in general, and easy to follow. It requires substantial effort only in select places.

The submission appears technically correct, with incorporations of the many existing tools from literature.

Critical weaknesses

The submission is not exactly experimentally rigorous with a glaring lack of sufficient algorithmic comparison, especially from the newer literature, although it seems reproducible.

The submission does not seem to present much novel findings (both theoretically and algorithmically), with many results seemingly very similar to the ones already existing in the literature.

Questions for authors

Can you explain the significance of your unification of the individual high probability bounds in more detail, e.g., in terms of the exact challenges involved and why it was not achieved for dynamic regret in past works.

Line 17: how is variance infinite when p=2 is bounded?

Line 93: explain why clipping makes it so that experts no longer see the same feedback, and why this is a problem.

Line 105: so your high probability bound holds for all comparator sequences simultaneously while the ones in the literature hold individually?

Line 173: what is h?

Line 264: what about the eta_- side? Why eta_J and not eta_N or eta_1?

Line 278: where is pi used?

(7): what does this inequality provide. The lower bound seems to hold with low probability.

Line 420: why did you not include newer works in the comparison?

2 comments

Equation (7): meaning of the lower-bound probability

Equation (7) gives the probability needed to test a guarantee at confidence 1−δ1-\delta. Such a guarantee must fail with probability at most δ\delta. Our lower bound constructs an instance whose regret reaches the stated threshold with probability at least 2δ2\delta. Every upper bound strictly below that threshold therefore fails more often than the confidence level permits.

This establishes the necessary heavy-tail dependence on both path complexity and log⁡(1/δ)\log(1/\delta), including linear-regret saturation. For example, at δ=0.01\delta=0.01, the lower-bound event has probability at least 0.020.02. This already rules out a uniformly smaller bound with 99% confidence.

Line 420: comparison with newer work

Section 2 and Table 1 compare recent results by their feedback assumptions, comparator class, and probability guarantee. Aggarwal [1] is the closest dynamic benchmark and establishes the heavy-tail path exponents in expectation for fixed comparator paths. Liu [2] analyzes classical OGD, dual averaging, and AdaGrad under heavy-tailed feedback, with expected static-regret guarantees. Our experiments include the OGD update, with the tuning stated in Section 6.1.

Liu [3] studies high-probability convergence for a fixed nonsmooth stochastic objective. Zhang et al. [4] study strongly convex OCO with sub-Gaussian noise. Our result addresses moving hindsight comparators under only a conditional pp-th moment, while allowing adaptive convex losses. The experimental comparisons and theoretical comparisons together identify the contribution of bias-compensated aggregation and the stronger probability guarantee.

References

[1] Vaneet Aggarwal. Parameter-Free Dynamic Regret under Heavy-Tailed Noise. 2026.

[2] Zijian Liu. Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applications. ALT, 2026.

[3] Zijian Liu. Clipped Gradient Methods for Nonsmooth Convex Optimization under Heavy-Tailed Noise: A Refined Analysis. ICLR, 2026.

[4] Wentao Zhang, Yutong Zhang, and Wentao Mo. Noise-Adaptive High-Probability Regret Bounds for Online Convex Optimization. ECML PKDD, 2026.

[5] Lijun Zhang, Shiyin Lu, and Zhi-Hua Zhou. Adaptive Online Learning in Dynamic Environments. NeurIPS, 2018.

Thank you for your answers and responses. My concerns have been generally addressed. I will keep my recommendation for now, with a possible change after the whole discussion phase.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.