- 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 -th central moment for . 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 (), and a per-expert bias offset () 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 that holds on a single event of probability at least 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
-
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- event without incurring dimension-dependent covering numbers.
-
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.
-
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 overhead and blow-up as ), while the coupled thresholds allow a single run to be valid across all and seamlessly wrap into an oblivious doubling schedule that recovers the deterministic minimax rate when .
-
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 up to universal constants while cleanly isolating the remaining versus gap in the deterministic term.
Critical weaknesses
-
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 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 without tuning to (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).
-
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).
-
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 per-round projection and memory complexity of the ensemble.
Questions for authors
Please see the weaknesses.
2 comments
Exact experimental definitions, drift identity, and computational cost
For the noise, let for , with and . Let be uniform on the unit sphere in , independently of . The symmetric noise is $ \xi=\sigma\left(\frac{\alpha-p}{\alpha}\right)^{1/p}ZU. $ For a fixed unit vector , define and . 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, -th moment , and infinite variance. Here . Methods share the same noise draws within each setting.
For the targets, let be fixed orthonormal vectors obtained by QR decomposition of a 5-by-2 standard Gaussian matrix. Set , , and . 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 . For the evasive target, and, for ,
\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.
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,σ,p to calibrate clipping and bias compensation. Valid upper bounds suffice for D,G,σ. 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) gives O(GDATT) without knowing PT [3]. Tuning η to PT sharpens this to O(GDTAT). Ader [4] achieves the sharper rate without knowing PT. 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,D and uses no G,σ,p. The experiments use the same environments and noise seeds as Section 6, with T=65536, A=8, and 1000 runs per setting. Entries below are 95th-percentile dynamic regret.
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.