Oracle-Efficient and Parameter-Free Agnostic Smoothed Online Learning

1 Introduction

• The paper’s goal is to retain statistical learning’s distribution-free appeal while relaxing independence through online learning.In classical statistical learning, ERM succeeds in realizable and agnostic settings without knowledge of the data distribution.Source: §1 · pp. 1, 3
• Online learning allows dependent data and processes that adapt to the learner, but this generality carries statistical and computational costs.In binary classification, Littlestone dimension may be infinite even for simple classes, and ERM-oracle access alone does not make general online learning tractable.Source: §1 · p. 2
• Smoothed online learning limits how much probability mass the adversary can place on small sets while retaining temporal dependence.Its smoothness parameter σ interpolates between independent covariates at σ = 1 and increasingly permissive constraints as σ decreases.Source: §1 · p. 2
• Prior oracle-efficient methods generally require a known, sampleable base measure; whether efficient learning remains possible in the agnostic setting was open.A cited exception establishes sublinear regret for ERM only in the realizable setting, where labels come from a fixed hypothesis.Source: §1 · p. 3

Main results.

• Gaussian FTPL gives the first oracle-efficient sublinear-regret guarantee for agnostic smoothed online learning without knowing the base measure.The learner also needs no knowledge of the smoothing parameter or horizon and uses a weighted ERM oracle.Source: Main results · p. 3
• The guarantee has optimal dependence on T and σ, with a remaining factor-d gap from the statistical optimum.In the realizable case, the d factor can be removed, matching the ERM guarantee up to logarithmic factors.Source: Main results · p. 3
• The algorithm extends to classes in [-1, 1] with convex 1-Lipschitz losses, with rates stated for parametric and nonparametric classes.For fixed σ, the nonparametric rate is sublinear for every α > 0 and matches leading horizon and smoothness exponents from Blanchard (2025).Source: Main results · p. 4
• The analysis compares FTPL predictions with an auxiliary exponential-weights learner over a cover, then bounds that learner’s regret.The auxiliary learner need not be efficient; Gaussian perturbations provide the stability needed for a low-regret bound despite the constant learning rate.Source: Main results · pp. 4–5

2 Preliminaries and Related Work

• The section defines VC dimension through shattering: every binary labeling of a set must be realized by some class member.VC dimension is the largest size of a shattered set, or infinite if no largest size exists.Source: §2 · p. 6
• For binary classes, fat-shattering dimension equals VC dimension at every scale ε in (0, 1].Fat-shattering dimension is defined through ε-shattering and is nonincreasing as ε increases.Source: §2 · p. 6
• The computational model assumes a weighted agnostic ERM oracle for weighted convex label losses or linear losses on covariates.The oracle is used to compute a solution to the stated optimization problem.Source: §2 · p. 6
• The paper presents its approach as the first oracle-efficient algorithm with sublinear regret for an agnostic setting and an arbitrary unknown base measure.Prior work either did not provide oracle-efficient algorithms or imposed additional assumptions.Source: §2 · pp. 6–7

3 Main Results

• The binary-class theorem gives a regret guarantee for every horizon and every σ-smooth covariate process, and its learner requires no knowledge of μ, σ, or T.The algorithm can be implemented with one weighted ERM-oracle call per round.Source: §3 · p. 7
• For real-valued classes with convex 1-Lipschitz losses, the theorem extends the guarantee using an additional averaging step.The stated bound is expressed in terms of fat-shattering dimension.Source: §3 · p. 7
• For parametric classes with fatε(F) ≲ d log(1/ε) at sufficiently small scales, the theorem gives an explicit rate; the dependence on d is suboptimal by a factor of √d.The supplied passage states the class condition and dimension-factor comparison but does not include the full rate expression.Source: §3 · pp. 7–8
• For nonparametric classes with fatε(F) ≲ ε^-α, choosing ε ≍ α T^-1/(2α+2) yields the stated rate.The passage specifies this choice for α > 0.Source: §3 · p. 8
• For every α > 0, the nonparametric-class bound is sublinear in T for fixed σ, although its T exponent is larger than the i.i.d. optimal exponent.The result matches the leading horizon and smoothness exponents of Blanchard (2025, Theorem 4), while controlling regret rather than only pseudo-regret.Source: §3 · p. 8
• The framework recovers the qualitative picture of statistical learnability while retaining oracle efficiency and requiring no knowledge of the base measure.Source: §3 · p. 8

4 Analysis Techniques

• The proof overview identifies three ingredients: a sharper surprise lemma, a reduction to exponential weights, and a regret bound for Gaussian-perturbed exponential weights.The binary case presents these ideas before the paper’s general-case proofs.Source: §4 · p. 8

4.1 Surprise Lemma

• The surprise lemma controls expected absolute test-function values using their past second moments, for predictable functions in conv(±F).The proof first obtains a bound on a tangent sequence and then uses a norm-comparison inequality to transfer it to realized covariates.Source: §4.1 · pp. 8–9

4.2 Reduction to exponential weights

• Gaussian FTPL predictions are close to those of an auxiliary exponential-weights learner over a cover of F, enabling the analysis to reduce to that learner’s regret.The cover has log |G| ≲ d log(2T/σ), and the reduction uses the surprise lemma to transfer past-data closeness to current covariates.Source: §4.2 · pp. 9–10

4.3 Regret of Gaussian-perturbed exponential weights

• The exponential-weights reference receives a regret bound by controlling its cumulative variance, with Gaussian perturbations keeping past-covariate variances small despite a constant learning rate.The analysis adapts variance-based exponential-weights bounds and transfers the variance control to current covariates using the surprise lemma.Source: §4.3 · p. 11

5 Conclusion and Discussion

• The algorithm is parameter-free and requires no knowledge of the base measure, smoothness parameter, or horizon, while achieving oracle-efficient learning on agnostic smooth data.The conclusion says the remaining gap to the statistical optimum is a factor involving d.Source: §5 · p. 12
• The paper says the remaining distance from its guarantee to the statistical optimum is a d-related gap, and that its results essentially close the question of oracle-efficient learning from smooth data.The conclusion frames this claim within the agnostic, unknown-base-measure setting.Source: §5 · p. 12
• Concurrent work studies the same form of Gaussian FTPL with a horizon-dependent perturbation scale, but its guarantee is for i.i.d. covariates and adversarial labels.Its analysis relies heavily on the i.i.d. assumption; general smooth processes may retain intricate covariate dependencies.Source: §5 · p. 12

Statement on the use of AI

• The authors report using generative AI to develop arguments, formulate and refine claims, propose proof ingredients, write and revise proofs, interpret results, and edit manuscript text.They state that all mathematical claims in the manuscript were independently verified by the authors, who take responsibility for the final work.Source: Statement on the use of AI · p. 12
• The authors describe an earlier regret-bound proof for an adaptation of Wu et al. (2024), followed by a Gaussian FTPL modification proposed with GPT 6 Astra.The earlier bound extended the original i.i.d.-covariate guarantee to the general σ-smooth setting.Source: Statement on the use of AI · p. 12

A Additional preliminaries

• The preliminary material collects smoothed online learning, variance-based exponential-weights regret bounds, Gaussian integration by parts, and Maurey’s empirical method.Source: A Additional preliminaries · p. 17

A.1 Covers under smoothed processes

• For binary classes of VC dimension d, a cover on n points has log |G| ≤ d log(Cn), and can match each class function on those points.For smoothed covariate processes, Proposition 4.2 gives log |G| ≲ d log(2T/σ) with an approximation guarantee along the trajectory.Source: §A.1 · p. 17

A.2 Variance-based regret bounds

• The appendix presents a one-round Bernstein bound as a tool for analyzing exponential weights.The bound applies to a finite class with weights and a loss whose range is bounded.Source: §A.2 · p. 20

A.3 Gaussian geometry

• Stein’s lemma is introduced as a way to relate gradients of potentials to their correlations with Gaussian variables.The appendix also states a bound on correlations for functions taking values in the convex hull of a finite class.Source: §A.3 · pp. 20–21

A.4 Convex hull approximations

• Maurey’s empirical method approximates a function in conv(±F) using a finite collection of functions from ±F on specified points.Source: §A.4 · p. 21

A.5 Log-partition functions and their derivatives

• The log-partition-function lemma gives derivative identities and a specialization for linear functions ψi(θ) = ai + ⟨θ, zi⟩.The proof uses differentiability almost everywhere for Lipschitz functions and the chain rule.Source: §A.5 · p. 22

B Proofs for the binary case

• The binary-case proof combines a surprise lemma, a reduction to exponential weights, and a regret bound for the exponential-weights reference.Source: B Proofs for the binary case · p. 22

B.1.1 Surprise lemma with tangent sequence

• The surprise-lemma argument first bounds predictable test-function values using second moments on a tangent sequence, then compares tangent moments with realized ones.The appendix restates the tangent-sequence result in its notation and gives a proof.Source: §B.1 · p. 22, §B.1.1 · p. 22, §B.1.2 · p. 24

B.1.2 Comparison inequality for signed convex hulls

• The signed-convex-hull comparison proof reduces to binary functions using the layer-cake identity and Maurey’s empirical method, then invokes Block et al. (2024b, Theorem 10).Source: §B.1.2 · p. 24

B.1.3 Proof of the surprise lemma

• The surprise-lemma argument handles the case σT < 1 directly and otherwise combines a change-of-measure bound with a uniform norm comparison on each prefix.The supplied statement gives no explicit bound value.Source: §B.1.3 · pp. 25–26
• The same proof strategy extends from VC classes to finite real-valued classes because it uses VC dimension only to count restrictions to finitely many points.Source: §B.1.3 · p. 26

B.2 Comparing predictions on the past

• For the FTPL and exponential-weights comparison, the proof counts functions in a difference class and applies a Gaussian tail bound with a union bound.It differentiates the two potentials and uses Stein’s lemma; the failure event contributes at most O(1) to expected squared prediction discrepancy.Source: §B.2 · pp. 26–27

B.3 Proof of the reduction to exponential weights

• Lemma 4.3 gives a bound for the difference between FTPL and exponential-weights predictions for a binary VC class.Source: §B.3 · p. 28
• The proof applies the surprise lemma to the difference of the two predictable predictions, bounding the expected double sum by O(d^2T log^2(2T/σ)).Source: §B.3 · p. 28

B.4 Regret of Gaussian-perturbed exponential weights

• For binary loss, Proposition 4.6 reduces regret to cumulative prediction variance, which the proof controls using predictable disagreement-class tests and the surprise lemma.Source: §B.4 · pp. 28, 30, 31
• Lemma 4.5 establishes a regret bound for exponential weights, and Theorem 3.1 follows by combining it with Lemma 4.3.Source: §B.4 · pp. 30–31

C Proofs for the real-valued loss case

• The real-valued proof uses a modified exponential-weights reference algorithm that selects clipped functions within cover cells to improve comparison with FTPL and keep cell potentials near cover-center scores.Source: C Proofs for the real-valued loss case · p. 31

C.1 Finite-scale surprise bounds

• The finite-scale surprise bound replaces VC dimension with fat-shattering dimension at scale cε, at the cost of an additive Tε log(2T)/σ term.The term pays for replacing functions by cover elements that are within 2ε except at a limited number of covariates.Source: §C.1 · p. 32

C.2 Proof of the prediction comparison on the past

• The real-valued prediction comparison uses clipped functions in the potential analysis and bounds differences on past covariates using the finite cover and its entropy.Source: §C.2 · pp. 34–35

C.3 Proof of the reduction to exponential weights

• The reduction applies the finite-scale surprise lemma to the difference between the two predictable prediction mixtures.Source: §C.3 · p. 36
• The expected double sum is O(T fat_cε(F)^2 log^5(CT/(σε)) + T^2ε^2 + T).Source: §C.3 · p. 36

C.4 Regret of Gaussian-perturbed exponential weights

• Lemma C.7 establishes a regret bound for the modified exponential-weights algorithm by combining the variance-based regret reduction with a bound on comparator differences.Source: §C.4 · pp. 38–39
• The proof expresses variance terms as predictable tests in the convex hull of a squared-difference class and applies Corollary B.3 to control them.Source: §C.4 · p. 39

• Under σ-smooth covariates and convex 1-Lipschitz losses, learner (7) satisfies Theorem 3.2’s regret bound, with c a universal constant.Source: §C.5 · p. 40
• The proof handles either 1 + fat_cε(F) > T or T < 1/σ directly; otherwise, it constructs a fixed cover and modified exponential-weights algorithm.Source: §C.5 · p. 40
• The finite average of oracle predictions has conditional variance at most 1/t, and Cauchy–Schwarz with Lipschitzness bounds its prediction discrepancy.Source: §C.5 · p. 40
• The proof decomposes Gaussian-mean regret, bounds its first sum with Lemma C.4 and second bracket with Lemma C.7, then combines the prediction and reference-regret bounds.Source: §C.5 · pp. 39–40
• The final simplification uses T ≥ 1/σ and σ ≤ 1, then takes the infimum over ε because the learner does not depend on ε.Source: §C.5 · p. 40

• Gaussian FTPL adapts its regret bound to the best comparator’s number of mistakes in binary classification.Source: D L⋆-dependent regret · p. 41
• Theorem D.1 gives a regret guarantee for binary classes of VC dimension d under σ-smooth covariates, using learner (3).Source: D L⋆-dependent regret · p. 41
• The learner does not require L⋆; when L⋆ = 0 almost surely, it recovers a realizable-case bound that is optimal up to logarithmic factors.Source: D L⋆-dependent regret · p. 41
• The proof first bounds expected mistakes on past covariates, then applies the surprise lemma to obtain a guarantee on current prediction loss.Source: D L⋆-dependent regret · pp. 41–42