PaperlayerView exact revision on arXiv

Source-linked AI summary

Reconciling Universal and Uniform Learning with $Q$-Aggregation

Mikael Møller Høgsgaard, Patrick Rebeschini, Tobias Wegel

arXiv:2609.05041v1math.STstat.ML

TL;DR

The paper studies whether minimax uniform guarantees and exponential universal rates can be achieved by the same learning algorithm. It uses Q-aggregation to establish this compatibility for finite dictionaries and characterizes an unavoidable trade-off for countably infinite dictionaries. The results also identify structural and algorithmic boundaries for universal learning with squared loss.

  • Problem

    The central question is whether minimax uniform guarantees and exponential universal rates can coexist in one algorithm despite favoring different principles.

  • Method

    The paper analyzes aggregation algorithms and Q-aggregation across finite and countably infinite dictionaries, including structural results for universal rates.

  • Results

    For finite dictionaries, Q-aggregation is minimax optimal along the tail and achieves zero excess risk with exponential probability; for countably infinite dictionaries, no algorithm can achieve both guarantees in general.

  • Takeaways & Limitations

    Finite dictionaries permit best-of-both-worlds learning, whereas countably infinite dictionaries require trading off universal and uniform performance.

  • Takeaways & Limitations

    Some infinite-class exponential-rate results rely on excluding distributions used in the lower-bound construction, so the corresponding theorems concern different distribution classes.

Abstract

from arXiv · show

We study regression under bounded responses in terms of excess mean squared error. When the comparator class is finite, this setting is known as model selection aggregation, and achieving minimax excess risk requires improper learning algorithms. Contrary to this, in the universal learning framework no improperness is needed, as simple empirical risk minimization achieves the best-possible exponential learning rate. Hence, the two frameworks suggest different optimal algorithmic principles. This poses the question of best-of-both-worlds guarantees: Are minimax and universal exponential rates achievable by the same algorithm? For finite hypothesis classes, we answer this question in the affirmative by showing that the $Q$-aggregation estimator - which is known to achieve minimax optimal tails - achieves exponential universal rates. A wide range of other estimators and algorithmic principles (ERM, sequential averaging, pruning, and star estimation) do not achieve both. For countably infinite hypothesis classes, we answer the question in the negative by showing that there is an inherent trade-off between achieving exponential universal and minimax uniform rates. This trade-off is exactly traced by combining optimal algorithms from each world using $Q$-aggregation. Besides these results, we prove several additional structural results about universal rates in learning with squared loss.

1 Introduction

The paper asks whether one algorithm can simultaneously achieve minimax uniform guarantees and exponential universal rates. It shows that Q-aggregation does so for finite dictionaries, while countably infinite dictionaries exhibit an inherent trade-off.

  • ERM achieves zero excess risk with exponential probability, but proper learning does not generally attain minimax deviation guarantees.
  • Q-aggregation achieves universal exponential rates without compromising uniform performance for finite dictionaries.
  • Finite dictionaries admit an algorithm that is minimax optimal along the tail and achieves zero excess risk with exponential probability.
  • Among finite-dictionary estimators, pruning, online-to-batch averaging, and star estimation each fail to achieve at least one of the two target guarantees, whereas Q-aggregation achieves both.
  • For countably infinite dictionaries, some problems allow separate minimax-optimal and exponential-rate algorithms, but no algorithm can achieve both guarantees.
  • The infinite-class trade-off can be parameterized by functions φ and matched by an algorithm achieving the corresponding universal and uniform rates up to constants along a subsequence.
  • Countably infinite classes can have arbitrarily slow universal rates, and exponential rates may require outputs outside convex or finite combinations of class functions.

2 Finite Hypothesis Spaces

Finite-hypothesis learning exposes a tension between exponential universal guarantees and minimax-optimal tails: pruning and ERM achieve the former but miss part of the latter, while averaging and star estimation fail to achieve exponential rates. Q-aggregation is presented as the method that achieves both properties.

  • Warm-up: ERM and exponential weights: ERM achieves zero excess risk with exponential probability, while exponential weights achieves only exponential rates with exponential probability.ERM selects a single empirically best model; exponential weights averages across models, including suboptimal ones.
  • Pruning with a threshold: Pruning-based estimators achieve exponential rates but cannot achieve minimax optimality along the whole tail.This limitation applies even though some pruning procedures satisfy pointwise minimax guarantees.
  • Online-to-batch conversion by averaging: Sequential averaging cannot achieve exponential rates when its burn-in time is independent of sample size.The progressive mixture, Bernstein online aggregation, and shifted-loss sequential estimators have polynomial lower bounds: 1/[8(n+1)^2], 1/[8(n+1)^2], and 1/(16n^2), respectively.
  • Star estimation: The star estimator achieves minimax optimality along the whole tail but not any exponential universal learning rate.A supplied lower bound gives expected excess risk 1/(8n).
  • Q-aggregation: For finite dictionaries, Q-aggregation with ϕ ≡ 1 and a uniform prior achieves both minimax-optimal tails and exponential universal rates.The paper identifies this configuration as the finite-dictionary method achieving both properties.

3 Countably Infinite Hypothesis Spaces: Structural Results

For countably infinite hypothesis spaces, universal and minimax learnability can diverge sharply: exponential universal rates may coexist with constant or arbitrarily slow minimax rates, and unrestricted exponential learning is generally impossible. The results also show that finite-combination methods can fail even when another algorithm achieves both rate goals.

  • Universal-rate limits: Exponential universal learning is not generally possible over all countably infinite hypothesis classes and distributions; unrestricted distributions require substantial class restrictions.The paper also gives a countable class learnable only at arbitrarily slow rates, with the infimum risk unattained.
  • Problem formulation: These structural gaps motivate defining learnability through the existence of separate algorithms for vanishing minimax and exponentially concentrated universal rates.The paper restricts attention to problem subsets where exponential rates are achievable before analyzing the infinite-case trade-off.
  • Structural conditions for exponential rates: An infinite class can admit exponential rates for every distribution when its possible constant predictors have only 0 as an accumulation point.Projecting the sample mean onto {0} ∪ {2^-k} yields zero excess risk near the true mean, and Hoeffding’s inequality gives exponential decay.
  • Universal versus minimax learnability: For infinite classes, minimax excess risk can remain constant at 1/4 even when nearly exponential universal rates are attainable.The constant minimax rate is achieved by the trivial predictor outputting 1/2, while a separate algorithm attains the nearly exponential universal rate.
  • Algorithmic principles: Finite convex or finite combinations can achieve only arbitrarily slow rates on some countably infinite problems, although another algorithm achieves both exponential universal and fast minimax rates.The limitation applies to algorithms satisfying the stated combination conditions, while the same problem classes admit an algorithm with simultaneous guarantees.

4 Best of Both Worlds for Infinite Hypothesis Classes?

For countably infinite hypothesis classes, separate attainability of uniform and exponential universal guarantees does not ensure one algorithm can achieve both. The paper proves an impossibility result and shows that Q-aggregation attains the sharp trade-off between these guarantees.

  • Setup: The paper defines “learnability in both worlds” as having separate algorithms for uniform learning and exponential universal learning over a distribution family.The uniform rate must vanish, while the universal algorithm achieves zero excess risk with exponential probability.
  • Impossibility: A distribution family can be learnable in both worlds while no single algorithm achieves both guarantees simultaneously.This establishes an inherent trade-off in the infinite setting rather than merely a limitation of a particular estimator.
  • Impossibility: Theorem 11 constructs such families with optimal uniform rate rn(δ) ≍ min{1, log(1/δ)/n}, but not faster rates.The construction assumes a sequence of hypotheses and points satisfying the theorem’s interpolation conditions, with constants ε and γ controlling the instance.
  • Scope: The apparent tension with exponential lower bounds is avoided because the distribution family in Theorem 11 excludes the distributions used in the other lower-bound result.Thus, the exponential universal guarantee and the impossibility theorem concern different distribution classes.
  • Impossibility: The construction uses hypotheses that fit previously specified observations while differing at a new point, making samples compatible with competing hypotheses.In the concrete example, the assumptions are nonvacuous with ε = 1/2 and γ = 1/2.
  • Q-aggregation: Q-aggregation combines separate uniform and exponential learners and achieves the best possible universal–uniform trade-off permitted by Theorem 11.Its trade-off is controlled by the prior and temperature; extreme prior choices favor one guarantee while weakening the other.

5 Conclusion

The paper studies whether one algorithm can achieve both universal exponential rates and uniform minimax guarantees. It finds compatibility for finite classes through Q-aggregation, but an exact trade-off for countably infinite classes.

  • Q-aggregation is optimal under both universal and uniform notions for finite hypothesis classes.
  • Pruning, averaging-based online-to-batch conversion, and star estimation each fail to be optimal for at least one notion in finite dictionaries.
  • For countably infinite dictionaries, some settings permit both exponential rates and uniform learning, but no single algorithm can achieve both.
  • Q-aggregation combines minimax-optimal and exponential-rate algorithms to attain the exact trade-off between universal and uniform guarantees.
  • Open questions include characterizing agnostic squared-loss universal rates, trade-off instances, general universal-rate costs, and extensions beyond squared-loss regression.

A Proofs of the Preliminary Lemmata

These preliminary proofs establish links between tail and expectation guarantees, show exponential rates are unavoidable for nontrivial finite classes, and analyze pruning-based estimators.

  • Integrating a minimax-optimal tail bound yields minimax optimality in expectation with an explicit constant.
  • An exponential-probability excess-risk bound implies an exponentially vanishing expected excess risk through the layer-cake representation.
  • For any nontrivial finite hypothesis class, a two-distribution construction forces excess risk of order exp(-n log 2) infinitely often.
  • The pruning-based algorithms split the data, prune hypotheses using one subsample, and optimize over their convex hull using the other.
  • Pruned-convex ERM and the midpoint estimator satisfy the required threshold condition, with the threshold tending to zero for fixed class size and confidence.

B.2 Proof of Theorem 2

The proof of Theorem 2 constructs a two-function Bernoulli problem and lower-bounds the probability that pruning removes the optimal function. The argument relies on binomial-tail estimates and normal approximation tools.

  • A binomial upper-tail lower bound controls the probability of this event using constants κ1 and κ2.
  • The construction uses F = {f1, f2}, with f1 ≡ 0, f2 ≡ 1, deterministic X, and Bernoulli responses.
  • The optimal function has zero excess risk while the other has excess risk 2µ, and empirical risks are determined by the sample mean.
  • On the event that the empirical-risk gap exceeds the pruning threshold, pruning removes f1 and the estimator equals f2.
  • Combining the cases yields the theorem after taking the supremum over distributions.
  • Berry–Esseen and McKay-type estimates supply the approximation and tail bounds needed to complete the probability lower bound.

C.3 Proof of Theorem 5

Theorem 5 is proved by splitting the Q-aggregation analysis into two cases. Both cases use the same concentration result to show that the aggregate matches or improves on the best dictionary risk.

  • The proof uses the positive semidefinite matrix G and KKT characterizations of the empirical and population minimization problems.
  • If a population Q-aggregation solution has objective below the best hypothesis risk, the empirical aggregate eventually has strictly smaller risk with exponentially high probability.
  • If no population solution improves on the best hypothesis risk, the empirical aggregate eventually has risk no larger than that benchmark with exponentially high probability.
  • The two lemmas combine to give RP(f̂ρQ) ≤ minj RP(fj) with probability at least 1 − CM^2 exp(−cn/M^2).

C.4 Proof of Lemma 10

The proof establishes Lemma 10 by combining a population-risk improvement with high-probability control of empirical deviations. This shows the empirical Q-aggregation solution retains a strict risk improvement for sufficiently large samples.

  • Lemma 12 shows that Ψ(ρQ) < RP(fM) implies RP(fρQ) < RP(fM).
  • Lemma 13 controls empirical quantities simultaneously with probability at least 1 − CM^2 exp(−cε^2n/M^2).
  • For sufficiently large n, the empirical minimizer has risk strictly below RP(fM) with probability at least 1 − CM^2 exp(−cn/M^2).The argument defines the positive population gap cgap and bounds the empirical risk perturbation by fractions of that gap.
  • The proof applies KKT conditions to compare the population and empirical Q-aggregation solutions.The comparison uses complementary slackness, empirical deviations, and simplex constraints.

C.5 Proof of Lemma 11

The proof of Lemma 11 treats the case where the population objective has no strict improvement over the best hypothesis. It shows that the zero population solution leads to nonpositive empirical excess risk through KKT and structural case analysis.

  • Lemma 15 characterizes strict population improvement by the existence of a simplex weight vector with a strictly negative linear excess-risk term.The proof uses a small convex combination toward a candidate mixture and the positive semidefiniteness of the Gram matrix.
  • When no simplex point satisfies Ψ(ρQ) < RP(fM), the zero vector is a population minimizer because Ψ(0) = RP(fM).
  • KKT conditions force empirical weights to vanish for hypotheses in the strictly separated index set I>.
  • The remaining risk decomposition bounds every indexed sum by zero, yielding RP(fbρQ) ≤ RP(fM).Equal-risk hypotheses contribute zero through identical functions, while strictly worse hypotheses are controlled by the deviation bounds.
  • The proof partitions hypotheses according to risk and distance margins, then selects ε so empirical deviations remain below those margins.The resulting high-probability event has probability at least 1 − CM^2 exp(−cn/M^2).

D.1 Proof of Theorem 6

The proof constructs a countable binary-valued class with an infinite VCL tree and uses it to exhibit a distribution whose infimum risk is zero but is unattained, supporting universal-learning lower bounds.

  • An injective indexing map constructs an infinite VCL tree satisfying the required realization condition for every finite path.The construction assigns distinct points to tree nodes and defines hypotheses that realize arbitrary binary labels along paths.
  • The class is countable because it is a countable union of finite hypothesis sets.
  • The constructed class has infimum risk zero under a suitable distribution, but every individual hypothesis has strictly positive risk.Finite prefixes can match the distribution’s labels while leaving only a tail of vanishing mass, whereas every fixed hypothesis misses a positive-mass labeled point.
  • The infinite VCL tree yields a universal lower bound for any learning algorithm along infinitely many sample sizes.The proof transfers a classification lower bound to squared loss for binary-valued hypotheses.

D.2 Proof of Theorem 7

The proof constructs distributions sharing finite-sample behavior across Bayes regressors and uses them to establish a lower bound for arbitrary learning algorithms. A measure-construction lemma supplies the required conditional label distributions.

  • The proof defines distributions P0 and Pi whose conditional means agree with different hypotheses on successive portions of the support.Under P0, g0 is a Bayes regressor; under Pi, fi is a Bayes regressor.
  • Lemma 16 constructs a probability measure with prescribed mean y while assigning at least αi mass to each specified ai.The construction adds residual mass at 0 and 1 and verifies total mass, support, and mean.
  • The argument compares algorithmic behavior under these distributions using events determined by prefix and tail labels.Conditional independence allows the relevant events to be related despite differing conditional label laws.
  • Chernoff bounds control the number of tail observations, producing an exponentially small probability term for suitable sample-size indices.
  • The resulting choice of rate function satisfies the required lower-bound behavior while remaining sublinear in n.The proof uses in ≤ √n to show in log 2 = o(n).

D.3 Proof of Theorem 10

The proof constructs a realizable distribution under which broad aggregation rules incur excess risk at least proportional to an arbitrary vanishing rate infinitely often, while an explicit learner achieves both target rates.

  • Lower-bound construction: An arbitrary rate function R(n) tending to zero is embedded into distributions and subsequences so that the learner’s excess risk is at least a universal constant times R(n) infinitely often.The construction uses probabilities p_i, increasing sequences (n_ℓ) and (i_ℓ), and c_0R(n_ℓ) masses.
  • Aggregation lower bound: Convex combinations and finite combinations cannot simultaneously avoid the constructed unseen-coordinate errors, yielding a constant lower bound at the selected sample sizes.For finite combinations, the width is k(n_ℓ), while the construction sets b_i accordingly; the proof obtains a lower-bound constant below 1/64.
  • Lower-bound construction: The constructed distributions remain finitely realizable almost surely, so they belong to the realizable distribution class used in the theorem.Samples are generated from levels and labels determined by z, yielding P_z^n(Real_n(F))=1 for every n.
  • Lower-bound construction: Every fixed hypothesis f_I has positive risk under P_z because a sufficiently deep level exceeds its finite index length and receives positive mass.Choosing ℓ with i_ℓ greater than the length of I forces f_I to take γ_I on that level.
  • Matching upper bound: The learner A⋆ outputs the zero predictor when all labels are zero and otherwise identifies a matching f_I from the first nonzero label.For every P in the realizable class, this learner either has zero excess risk or identifies a hypothesis realizing P.
  • Matching upper bound: A⋆ achieves zero excess risk with exponential probability and a uniform rate controlled by log(1/δ)/n.The proof splits according to q=P(Y≠0), bounding risk by q when q is small and failure probability by exp(−qn) otherwise.

D.4 Proof of Theorem 8

The proof uses randomly labeled finite domains to show that no deterministic learner can uniformly attain vanishing excess risk, while a constant predictor supplies a matching upper bound.

  • Lower bound: For each finite domain, the construction chooses a uniformly random binary labeling and defines a realizable distribution whose optimal hypothesis has zero risk.The target labeling z determines both the distribution and a comparator f_z in the class.
  • Lower bound: A sample reveals labels only on observed domain points, leaving unseen labels independent and unpredictable to the learner.The proof compares the learner’s output on samples generated from U and random labels Z.
  • Lower bound: Averaging over unseen labels forces a nontrivial prediction error for every deterministic learner, without requiring a union bound over hypotheses.The construction controls the learner’s predictions on coordinates outside the observed set O(U).
  • Lower bound: The lower bound applies for every learner and sample size, after choosing the domain size and labeling distribution appropriately.The constructed pairs remain in the realizable class, and the resulting bound holds uniformly over the learner and n.
  • Upper bound: The constant algorithm A_1/2 predicts 1/2 everywhere and achieves the matching upper bound for every distribution and function class.Its worst-case squared-loss comparison establishes the claimed universal upper bound.

D.5 Proof of Theorem 9

The proof constructs a truncated, margin-based scan of a countable class that eventually selects the first optimal hypothesis, establishing universal learnability under squared loss.

  • Countable-class control: The countable-class proof avoids a union bound over the entire infinite class by restricting comparisons to the growing prefix ψ(n).This truncation is the key distinction from a finite-class argument.
  • Algorithm: The algorithm scans only ψ(n)=max{1,⌈φ(n)⌉} hypotheses, where φ(n) diverges but remains o(n).It replaces the current candidate when an empirical-risk margin τ_n separates the new hypothesis from every earlier one.
  • Eventual selection: For each distribution-class pair, the first optimal hypothesis f⋆ appears within the scanned prefix for all sufficiently large n.Because ψ(n) tends to infinity, the scan eventually reaches the first optimal index i⋆.
  • Eventual selection: Empirical-risk concentration ensures that f⋆ defeats every earlier suboptimal candidate and is not replaced by later candidates with nonnegative excess risk.The proof uses Hoeffding bounds and a union bound over the scanned hypotheses.
  • Distribution construction: The construction of distributions P∞ and P_j,ℓ makes designated hypotheses Bayes optimal on their respective supports.Under P∞, f∞ is Bayes optimal; under P_j,ℓ, the prefix condition makes f_j agree with the conditional mean.

E.2 Learnability in Both Worlds

Two learners separately achieve exponential universal and minimax uniform rates, while lower-bound constructions show that both rate scales are optimal up to constants.

  • Exponential universal rate: Aexp outputs the hypothesis indexed by the largest observed certificate and otherwise returns the Bayes rule f∞.Under P∞ it always returns f∞; under P_j,ℓ, observing the certificate causes output of f_j.
  • Exponential universal rate: The exponential universal rate has constant ω_ℓ/Z_j,ℓ depending only on the fixed distribution.The certificate’s appearance probability determines the failure exponent.
  • Uniform minimax rate: Amini uses observed certificates and the largest observed ordinary index to achieve the uniform minimax rate 24 log(1/δ)/n.Its case analysis controls excess risk under P∞ and each P_j,ℓ.
  • Lower bounds: No learner can improve the exponential scale uniformly: for infinitely many n, either P∞ or P_2,1 yields exponential-order failure probability for zero excess risk.The indistinguishability argument compares the learner’s prediction at x_2 under the two distributions.
  • Lower bounds: The minimax rate log(1/δ)/n cannot be improved up to constants.A pair of neighboring distributions yields excess risk of order log(1/δ)/n with probability at least δ.

F Proof of Theorem 12

The proof establishes universal and minimax guarantees for the Q-aggregation estimator by analyzing its convex objective and combining concentration arguments with a two-function aggregation result.

  • Proof ingredients: Theorem 13 supplies the finite-class Q-aggregation guarantee used as a key ingredient in the proof.It applies to bounded regression with squared loss, positive priors, and sufficiently large β.
  • Objective analysis: The Q-aggregation objective is analyzed as a convex quadratic in ρ, with the constrained solution obtained by projecting the unconstrained minimizer onto [0, 1].The proof separately handles strictly convex and affine cases, including tie-breaking and degenerate coefficients.
  • Risk control: Convexity shows that when the estimator’s mixture parameter lies in the relevant interval, its population risk does not exceed the target comparator risk.The proof uses the quadratic risk along the segment joining the exponential and minimax candidates.
  • Universal-rate guarantee: The universal-rate argument bounds the empirical comparison between the minimax and exponential candidates using a combined random variable and Bernstein’s inequality.The proof controls the variable’s range and variance, then derives an exponentially small failure probability through a constant-factor comparison.
  • Minimax guarantee: The minimax guarantee combines an event controlling the exponential candidate with Theorem 13 on the two-function class and a union bound over independent samples.The resulting intersection completes the minimax proof for the Q-aggregation estimator.
Loading 2609.05041v1…