PaperlayerView exact revision on arXiv

Source-linked AI summary

Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise

Vaneet Aggarwal

arXiv:2610.02258v1cs.LGcs.ITmath.ITmath.OC

TL;DR

Full-horizon regret can mask poor tracking on individual evaluation windows, and heavy-tailed stochastic feedback complicates interval guarantees. This paper gives a parameter-free learner for interval-dynamic regret, with a shared prior and expected calibration supporting its comparisons. Its interval cost is additive in comparator complexity, while known noise statistics reduce the cost to 1 + log(T/n).

  • Problem

    Full-horizon guarantees can obscure poor tracking on a short evaluation window, while a single stochastic observation may be arbitrarily large and noise may have infinite variance.

    Source: §I · p. 1

  • Method

    A parameter-free learner combines expected calibration with a prior-sensitive sleeping-master comparison over predictably available experts.

    Source: §I · pp. 1–2

  • Results

    The interval guarantee adds log^2(2T) to comparator complexity, while supplied statistics reduce the interval cost to 1 + log(T/n).

    Source: §I · p. 1

  • Takeaways & Limitations

    The same decisions support static comparisons and deterministic partitions, with finer partition comparisons when movement is concentrated in time.

    Source: §I · pp. 1–2

Abstract

from arXiv · show

We study online convex optimization with one unbiased stochastic subgradient per round and an unknown finite conditional $p$th noise moment, $1<p\le2$. For every fixed interval $I$ of length $n$ and comparator path with $\Lambda_I=1+P_I/D$, one learner achieves \[ E[Regret_I(u)]\le\min(GDn, C[GD\sqrt{n(\Lambda_I+\log^2(2T))} +\sigma Dn^{1/p}(\Lambda_I+\log^2(2T))^{(p-1)/p}]). \] The learner uses none of $G,\sigma,p,I,P_I$, and the constant is universal. Interval adaptation adds to comparator complexity, preserving the distinct mean-gradient and noise exponents. The analysis controls calibration in expectation and limits the cost of observation-scale changes. Its general theorem compares to distributions over predictably available experts with relative-entropy dependence on a nonuniform prior. A common prior favors long windows and long restart lengths. With the statistics supplied, the interval cost becomes $1+\log(T/n)$, including the optimal full-horizon static rate. A change-of-measure lower bound identifies the noise power of this logarithm for learners retaining a full-horizon optimal guarantee, under explicit conditions. Static comparisons and deterministic partitions follow from the same decisions.

I. INTRODUCTION

Full-horizon regret can hide poor tracking on a later evaluation window, especially with heavy-tailed stochastic feedback. The paper gives a parameter-free interval guarantee, then separates its adaptation cost from the statistical cost when noise parameters are known.

Motivation

  • A single stochastic observation can be arbitrarily large, and its noise may have infinite variance, complicating window-wise tracking.Full-horizon regret may conceal a short period of poor tracking because regret accumulated earlier can compensate for it.Source: §I · p. 1

Main result

  • The learner guarantees interval-dynamic regret with an additive log^2(2T) complexity cost, while preserving distinct mean-gradient and noise exponents.The bound is capped by GDn and uses universal constants, without requiring G, σ, p, the interval, or comparator path length.Source: §I · pp. 1–2

Statistical interval cost

  • With G, σ, and p supplied, the interval cost becomes 1 + log(T/n), equal to one at the full horizon.A lower bound identifies the corresponding logarithmic noise cost for learners retaining an optimal full-horizon static rate, under an explicit regime.Source: §I · pp. 1–2

Calibration

  • Expected calibration bounds both positive tangent excess and logarithmic defect using finite conditional moments, enabling regret analysis directly in expectation.The bound retains the finite-p term before the learning rate is optimized.Source: §I · pp. 1–2

Prior-sensitive comparison

  • A common nonuniform prior separates the costs of locating a window, selecting its duration, and choosing a restart length.The prior favors longer windows and restart lengths.Source: §I · p. 2

Additional comparisons

  • The paper also establishes static and deterministic-partition comparisons using the same learner decisions.Partitions provide finer comparisons when comparator movement is concentrated in time.Source: §I · pp. 1–2

II. RELATED WORK

Prior work addresses dynamic, interval, and heavy-tailed online learning through different feedback assumptions and comparison objectives. This paper positions its contribution as local comparisons with unknown conditional finite-p noise, alongside a statistical interval-cost analysis.

Static and dynamic regret

  • The joint full-horizon dynamic rate and parameter adaptation were established by Aggarwal [1], while this work adds window alignment to a restarted-expert comparison.The full-horizon energy argument needs only marginal moments; the local master uses conditional noise moments.Source: §II · p. 2

Interval and strongly adaptive regret

  • AOA gives the exact-gradient specialization O(BI(ΛI + L)) [17], while this work treats unknown conditional finite-p noise and separates mean-gradient and noise powers.Earlier work had already combined dynamic and interval objectives [17].Source: §II · p. 2

Problem-dependent interval guarantees

  • Xie et al. [15] refine local environmental variation under smooth nonnegative losses, exact first-order information, and function-value scheduling.Their adaptive terms retain maximum observed input scales; this paper instead uses gradient-only feedback and central noise moments.Source: §II · p. 2

Heavy tails and adaptive aggregation

  • Finite-moment expert aggregation [12] gives full-horizon guarantees under finite second moments, whereas this paper studies finite-p sleeping comparisons with localization requirements.The distinction remains relevant even at p = 2.Source: §II · p. 2

Lower-bound approach

  • The lower bound uses a ternary oracle and a null-versus-window change of measure to study the logarithmic interval cost.Its full calculation is given in Section V.Source: §II · p. 2

III. SETUP AND INFORMATION MODEL

The setup evaluates a learner on fixed intervals against deterministic comparator paths, with one stochastic subgradient per round and unknown finite conditional noise moments. The interval construction uses dyadic windows, restarted base trajectories, and a shared prior over window and restart choices.

Information model

  • The learner receives only one stochastic subgradient at its predictable decision, with conditionally unbiased noise having a bounded pth moment for unknown p in (1, 2].The domain is closed, convex, and bounded in diameter; losses have selected subgradients bounded by G.Source: §III · p. 3

Regret comparison

  • Regret is compared on each fixed interval with a deterministic comparator sequence, and the guarantee depends on interval length and comparator movement.Each fixed interval and comparator is covered on the same learner decisions; the bound does not include realized energy accumulated before the interval begins.Source: §III · p. 3

Sleeping comparisons

  • The general master compares with predictably available records, each having a feasible prediction and a positive prior mass.It also permits a fixed distribution over records with an almost-sure budget on weighted activity.Source: §III · p. 3

Windows and base trajectories

  • The interval algorithm combines dyadic windows with restarted AdaGrad trajectories, all updated using the same raw gradient and linear surrogate.Each interval has a dyadic cover with at most two untruncated windows of each size; the base comparison selects a restart index aligned to comparator movement.Source: §III · p. 4

Prior and selected costs

  • A shared nonuniform prior favors long windows and, within each window scale, long restart lengths, while separating their selection costs.For an untruncated window, its leading location cost is log(T/n); scale and restart selection add iterated logarithms.Source: §III · p. 4

A. The sleeping master

The sleeping master aggregates records that are available predictably and uses rate-specific wealths and penalty counters. Its scale adaptation changes the wealth-score scale without altering the shared base trajectories.

Wealth and rates

  • The master initializes pair-rate wealths at one and assigns each rate a penalty guess and a counter.Sleeping records retain their wealth; in the interval implementation, unborn wealths start at one and expired contributions are frozen.Source: A. The sleeping master · p. 5

Wealth updates

  • For each awake record, the master forms a prediction-relative gradient score and updates its wealth using a clipped multiplier.The score is the inner product of the observed gradient with the difference between the learner’s decision and the record’s prediction.Source: A. The sleeping master · p. 5

Calibration counters

  • Rate counters accumulate normalized excess and double their penalty guesses after crossing a threshold, without resetting wealth values.The counter update uses the round’s pre-update guesses and exposures.Source: A. The sleeping master · p. 5

Scale adaptation

  • Observation-scale changes occur only after round updates, while each AdaGrad trajectory continues to receive the raw gradient unchanged.Rescaling all observed gradients by a positive constant leaves decisions unchanged because the observation scale and normalized base updates rescale accordingly.Source: A. The sleeping master · p. 5

B. Calibration inequalities and the local theorem

The analysis combines expected calibration of a sleeping master with a pathwise potential budget to obtain prior-sensitive comparisons under finite conditional moments. The theorem retains relative-entropy dependence on the prior for predictable expert activity.

Algorithm 1

  • The learner plays the prior mixture of awake predictions, updates wealth and potential, and forms calibration increments using the old guesses.The interval instantiation updates base trajectories with the raw stochastic gradient and applies a scale change and master reset.Source: B. Calibration inequalities and the… · p. 6

Calibration inequalities

  • A pathwise counter budget bounds each phase’s log-potential by O(L2), including the potential after an unbounded trigger observation and before reset.The argument bounds the number of guess doublings without using a moment bound in the final counter-budget step.Source: B. Calibration inequalities and the… · p. 6
  • Expected calibration bounds the summed normalized penalty excess across positive-scale phases, including phases ended by observation-dependent triggers.The maximum-guess calibration remains valid when h < δ; when h = 0, the guess remains δ almost surely.Source: B. Calibration inequalities and the… · pp. 6–7

The local theorem

  • Under (III.1), the learner uses none of G, σ, p, ν, or nν; for ν=ei, the individual-record bound has nν=ni and Ki=1+log(1/πi)+L2.Source: B. Calibration inequalities and the… · p. 7
  • The master’s relative-entropy comparison preserves the benefit of prior mass shared across useful experts rather than charging the average individual prior cost.For records sharing support J, the prior-weighted average comparison has nν = |J| and KL(ν∥π) = log(1/π(A)).Source: B. Calibration inequalities and the… · p. 7

C. Dynamic regret and temporal concentration

The interval guarantee adapts to comparator movement while retaining distinct mean-gradient and noise terms. The same decisions also yield static, partition-based, and temporally localized comparisons.

Theorem IV.4

  • E Regret_I(u) is bounded by min{GDn, C[ B_I(Λ_I) + GD√n L + σDn^(1/p)L^(2ρ)]} for every fixed interval and comparator path.The same decisions support the stated comparisons without knowing G, σ, p, I, or P_I.Source: C. Dynamic regret and temporal… · p. 8

Static comparisons

  • With a constant comparator, the interval-static bound is O(B_I(1 + L2)); supplied statistics replace L2 by χ_T(n) and recover the full-horizon static scale at n = T.The interval-static specialization makes local-evaluation cost visible without comparator movement.Source: C. Dynamic regret and temporal… · p. 8

Deterministic partitions

  • For a fixed interval and comparator, deterministic partitions yield a comparison formed from the bound for each partition piece.The proof adds expected bounds over the pieces, with partition selection outside the expectation.Source: C. Dynamic regret and temporal… · p. 8

Temporal concentration

  • O(GD[m + √nL]) versus O(GDn^(5/6)) when T = n, m ≍ n^(2/3), and P_I ≍ Dm, for the stated noiseless initial-episode example.These are a comparison of the two upper bounds; local evaluation retains information about when comparator movement is concentrated.Source: C. Dynamic regret and temporal… · p. 8

V. THE STATISTICAL COST OF INTERVAL ADAPTATION

The section places interval adaptation against a fixed-window lower-bound benchmark and asks what additional cost comes from locating an unannounced evaluation window.

Fixed-window benchmark

  • Aggarwal [1, Theorem 5.1] gives a fixed-window lower bound for every fixed length n ≥ 2 and path budget P.The passage states that every learner has an admissible fixed instance with expected regret at least the benchmark, but does not supply the bound’s formula here.Source: §V · p. 8

Embedding in a longer run

  • Zero losses and observations outside the window place the benchmark construction inside a longer run.The cited exact-gradient and rare-revelation constructions satisfy conditional moments, with an independent initial seed for the entering learner state.Source: §V · p. 8

Window location

  • The section frames the remaining question as the extra cost of locating an evaluation window that was not announced in advance.This is distinguished from the fixed-window polynomial benchmark.Source: §V · p. 8

A. A full-horizon-preserving upper bound with supplied statistics

When G, σ, and p are supplied, a single predictable learner gives an interval guarantee with a window-location cost that preserves the full-horizon rate. A prior favoring long windows also supports the static comparison.

The supplied-statistics guarantee

  • Theorem V.1 gives one predictable learner an interval guarantee when G, σ, and p are supplied.The learner uses one gradient query and O(log T) projections per round; neither the interval nor comparator movement is supplied.Source: A. A full-horizon-preserving upper… · p. 9

Full-horizon preservation

Static comparison

  • A root record with prior mass at least 1/4 runs AdaGrad without restart, supporting the full-horizon static comparison uniformly over p.The passage identifies favoring long windows as relevant even for a static comparator.Source: A. A full-horizon-preserving upper… · p. 9

B. A regret–testing tradeoff

The section studies the conflict between low regret on a persistent environment and identifying an unannounced exceptional window. It establishes a moment-dependent interval cost under a full-horizon regret requirement and an explicit regime.

B. A regret–testing tradeoff

  • When null regret is zero, the exceptional-window regret is D∆n.Source: B. A regret–testing tradeoff · p. 9
  • Only the n oracle draws inside the exceptional window contribute to transcript divergence, giving divergence ncq; adaptive actions and the independent learner seed add none.The comparison adjoins a uniform round in the window and a uniform random threshold, then applies data processing to the resulting binary event.Source: B. A regret–testing tradeoff · p. 10
  • For a selected exceptional window I_j, the alternative interval regret against its constant minimizer is exactly D∆n(1−β_j).The alternative changes the loss and oracle law only within I_j; β_j is the average alternative probability of the event defined by w(x_U) in the proof.Source: B. A regret–testing tradeoff · pp. 9–10
  • The noise power ρ in the supplied-statistics interval cost O(σDn^1/pχ_T(n)^ρ) is sharp under the stated regime and full-horizon guarantee.The lower bound compares this cost with the supplied-statistics static-comparator upper bound.Source: B. A regret–testing tradeoff · p. 10
  • The lower-bound conclusion is conditional on the stated regime and a full-horizon regret guarantee, even when parameters and candidate windows are known.The theorem’s setup allows the learner to know the statistical parameters and candidate windows.Source: B. A regret–testing tradeoff · pp. 9–10

VI. CONCLUSIONS

The conclusion gives interval-dynamic guarantees with an additive log^2 T cost, while supplied statistics reduce the interval cost to 1 + log(T/n). The appendix supports the analysis with a dyadic decomposition and moment bounds for predictable selection.

VI. CONCLUSIONS

  • One learner attains heavy-tailed dynamic regret on every fixed interval with an additive log^2 T adaptation cost and universal moment constants.With supplied statistics, the interval cost becomes 1 + log(T/n); a regret–testing lower bound identifies its noise logarithm power under a full-horizon optimality requirement.Source: §VI · p. 10

A. Dyadic decomposition and moment conversion

  • The dyadic decomposition covers I with disjoint maximal untruncated intervals, selecting at most two intervals of each size.Singletons ensure coverage, and nesting ensures disjointness.Source: A. Dyadic decomposition and moment… · p. 11
  • Predictable selection with at most n selected rounds lets conditional pth-moment bounds control the selected observations’ moments.For a fixed set S, the argument takes n = |S|; predictable selection is where the general statement uses conditional moments.Source: A. Dyadic decomposition and moment… · p. 12

B. Proof of Proposition III.2

The proofs combine deterministic sleeping-window alignment, expectation-based calibration and comparison bounds, and a weighted dyadic cover to establish interval bounds that retain prior-dependent complexity. They also bound both coefficients by 40 for 0 < ρ ≤ 1/2 and complete the argument by linearization and the regret ceiling, using the same learner and oracle observations for all interval guarantees in Theorem V.1.

B. Proof of Proposition III.2

  • The sleeping-window proof aligns each interval with fresh restart blocks or prefixes and bounds the two coefficients by three, proving Proposition III.2.It adapts Aggarwal [1, Lemma 4.3]’s pathwise inequality; the deterministic block argument does not require unbiasedness at a virtual trajectory.Source: B. Proof of Proposition III.2 · p. 12

C. Exact-gradient comparison in Table I

  • The exact-gradient comparison applies Zhang et al. [17, Theorem 5] after rescaling the domain and uses one exact query to determine the affine surrogate.For G = 0, regret is zero; the construction supplies the common scaling and one-gradient surrogate interpretation used in Table I.Source: C. Exact-gradient comparison in Table I · pp. 12–13

A. The simultaneous tangent and logarithmic bounds

  • Calibration cannot assume a centered score has expectation at most one: the supplied example has EZ = 0 but EF(Z) = 7/6.Conditional centering and the conditional pth-moment bound yield (IV.7) for every predictable rate; calibration accounts for positive drift rather than treating truncation as unbiased.Source: A. The simultaneous tangent and… · p. 13

B. Complete allocation identities

  • The identities give C ≤ 3/2 and C+ ≤ d, so d = 0 implies C+ = 0 and validates the zero convention; also, 0 ≤ Z_l ≤ d_l and Σ_l Z_l = C+ ≤ 3/2 < 2.Taking conditional expectations gives E Z_l ≤ A_l h(η_l) by (IV.7).Source: B. Complete allocation identities · p. 13

APPENDIX C PROOF OF THE GENERAL SLEEPING-MASTER THEOREM

D. Relative-entropy extraction on a phase

B. Expected logarithmic potential

C. Selected prior cost and a weighted cover

  • Combining the individual-record bound, Proposition III.2, and the weighted cover proves refined bound (V.3), with separated form (V.2) obtained by bounding each piece.The cover retains prior-dependent weights and yields universal constants as p approaches one.Source: C. Selected prior cost and a weighted… · p. 18

D. Proof of Corollary V.2

Loading 2610.02258v1…