Reconciling Universal and Uniform Learning with $Q$-Aggregation

1 Introduction

• Minimax tail optimality requires hedging through aggregation, whereas ERM achieves zero excess risk with exponential probability for every fixed finite-dictionary problem.Squared-loss strong convexity makes averaging beneficial through a non-positive Jensen gap.Source: §1 · pp. 2–3

1.1 Definitions and Preliminaries

• The formal framework distinguishes minimax expectation, fixed-confidence, and tail guarantees, with tail optimality strictly stronger than the other two.For universal learning, zero excess risk with exponential probability implies exponential rates with exponential probability and in expectation.Source: §1.1 · pp. 4–5

1.2 Summary of Main Results

• For finite dictionaries, Q-aggregation achieves zero excess risk with exponential probability while remaining minimax optimal along the whole tail.This resolves the best-of-both-worlds question affirmatively in the finite setting.Source: §1.2 · p. 6
• For countably infinite dictionaries, no algorithm can simultaneously achieve minimax optimality and zero excess risk with exponential probability.Q-aggregation combines algorithms optimized for each regime and attains matching trade-off bounds when the trade-off function satisfies φ(n) ≲ n.Source: §1.2 · pp. 6–7
• For infinite dictionaries, the paper further establishes arbitrarily slow universal rates, frequent failure of truly exponential rates, and cases where exponential learning requires outputs beyond convex or finite combinations.These structural results contrast with finite-dictionary aggregation and complement the uniform–universal trade-off.Source: §1.2 · p. 7

1.3 Related Work and Background

• Other aggregation procedures trade off guarantees: progressive mixture is minimax optimal in expectation but not deviation, whereas star estimation and pruned-convex ERM attain minimax deviation rates, with some methods requiring the evaluation confidence level [5, 6, 7, 13, 20, 22, 37, 38, 42, 43, 47, 48, 59, 60, 62].Earlier exponential-weights methods are also minimax-suboptimal in some regimes, while Bernstein online aggregation and shifted-loss sequential procedures achieve minimax-optimal tails [1] [17] [19] [35] [55] [59].Source: §1.3 · p. 7
• Q-aggregation uses a prior and is minimax optimal in both expectation and deviation, while its local risk bound remains a uniform oracle inequality rather than a universal instance-wise rate [17] [51].Computational aspects are discussed in [17].Source: §1.3 · p. 7
• Data-dependent dictionaries form a related aggregation literature, with sharp oracle inequalities and, for finite affine estimators, no additional minimax cost under data dependence [16] [18] [55].The universal setting instead requires the dictionary to remain fixed across sample sizes, which is central to the paper’s best-of-both-worlds results.Source: §1.3 · p. 8
• Prior universal-learning work established exponential rates for ERM on finite classes and extended the framework across several settings, but regression with agnostic squared loss had not been studied to the authors’ knowledge [2, 4, 10, 11, 26, 27, 28, 29, 30, 31, 32, 39, 40, 41].The closest regression work treated cut-off and absolute loss, including realizable settings and characterizations of universal rates.Source: §1.3 · p. 8
• The paper asks whether universal and uniform learning rates are compatible when both are achievable, focusing on dictionary learning with squared loss.This differs from the usual universal-learning goal of characterizing achievable rates through combinatorial or geometric dimensions.Source: §1.3 · p. 8

2 Finite Hypothesis Spaces

• Empirical risks separate every suboptimal hypothesis from an optimal one with exponentially high probability, enabling universal exponential-rate guarantees through empirical comparisons.The separation event follows from Hoeffding’s inequality and a union bound over the finite dictionary.Source: §2 · pp. 8–9

2.1 Warm-up: Empirical Risk Minimization and Exponential Weights

• ERM achieves zero excess risk with exponential probability, whereas exponential weights achieves only exponentially small excess risk with exponential probability and may retain suboptimal weight.ERM is proper and eventually selects an optimal hypothesis; exponential weights hedges across the dictionary and achieves minimax expectation rates [35], but not zero excess risk with exponential probability.Source: §2.1 · pp. 9–10

2.2 Pruning with a Threshold

• Every pruning-based estimator with a vanishing threshold achieves zero excess risk with exponential probability, including pruned-convex ERM and the midpoint estimator [43, 42].The guarantee depends on hyperparameters such as α, M, and δ; the cited algorithms are also pointwise minimax optimal for the supplied confidence.Source: §2.2 · p. 11
• Pruning-based estimators with vanishing thresholds are nevertheless minimax-suboptimal on part of the tail, so pointwise minimax optimality does not extend uniformly.For thresholds of order at most B_M(δ)/√m, this suboptimality can occur at a confidence level independent of sample size; pruned-convex ERM and midpoint estimation therefore fail along the tail.Source: §2.2 · pp. 11–12

2.3 Online-to-Batch Conversion by Averaging

• A broad class of online-to-batch estimators formed by averaging sequential predictors cannot achieve exponential rates, covering progressive mixture, exponential weights, and Bernstein online aggregation forms.The class uses deterministic predictors independent of n and fixed averaging parameters; the supplied discussion motivates it with estimators having differing minimax guarantees.Source: §2.3 · p. 13
• Fixed-burn-in online-to-batch averaging cannot achieve exponential rates; progressive mixture, Bernstein online aggregation, and shifted-loss estimators incur lower bounds of 1/[8(n+1)^2], 1/[8(n+1)^2], and 1/[16n^2], respectively.A sample-dependent burn-in such as b = n/2 can recover exponential rates for progressive mixture, but its minimax expected-risk optimality remains open.Source: §2.3 · pp. 13–14

2.4 Star Estimation

• Star estimation is minimax optimal along the tail but has excess risk 1/(8n) on some (P, F), so it achieves no exponential universal learning rate.Its failure arises because it cannot reliably commit to a single dictionary element even when evidence is overwhelming.Source: §2.4 · pp. 14–15

2.5 Q-aggregation

• Q-aggregation with ϕ ≡1 and a uniform prior achieves zero excess risk with exponential probability on Θ_M, while retaining minimax tail optimality.Among the estimators considered, only this Q-aggregation variant achieves both properties, establishing no trade-off for finite dictionaries.Source: §2.5 · p. 16
• The Q-aggregation proof exploits population margins: unfavorable directions are eliminated, while harmless directions leave the estimator no worse than the best dictionary element with exponential probability.Depending on the population geometry, the estimator either asymptotically improves on or is asymptotically no worse than the optimal dictionary element.Source: §2.5 · pp. 16–17, Figure 4 · p. 16
• Q-aggregation is implicitly sparse: it remains dense mainly where excess risk is small or mixing benefits outweigh the associated excess risk.This sparsity supports both its minimax and universal guarantees.Source: §2.5 · p. 17

3.1 Lower Bounds for Arbitrarily Slow and Nearly Exponential Rates

• Unlike finite classes, countably infinite classes may permit only arbitrarily slow universal rates, while unrestricted distributions can force substantial restrictions on the function class for exponential learning.Theorem 6 establishes arbitrarily slow rates, and Theorem 7 formalizes restrictions needed when distributions remain unrestricted.Source: §3 · p. 17, §3.1 · p. 18

3 Countably Infinite Hypothesis Spaces: Structural Results

• Together, these results motivate defining learnability by the existence of two algorithms: one with a vanishing minimax rate and another with zero excess risk with exponential probability.This formulation isolates the two guarantees that need not be delivered by the same algorithm in countably infinite settings.Source: §3 · p. 17

3.2 Universal Learnability does not Imply Uniform Learnability

• Universal learnability need not imply uniform learnability: for countable classes with an attained risk infimum, minimax excess risk can remain constant at 1/4 even when nearly exponential universal rates are achievable.The constant minimax value 1/4 is attained by the trivial predictor outputting 1/2, whereas Theorem 9 provides nearly exponential universal rates for any φ(n)→∞ with φ(n)=o(n).Source: §3.2 · p. 19

3.3 Arbitrarily Slow Rates for Convex and Finite Aggregation

• There are countably infinite dictionaries where one algorithm achieves exponential universal and fast minimax rates, but every convex or finite combination rule achieves only arbitrarily slow rates.This separation applies even to finite combinations whose width depends on sample size; the favorable algorithm and the lower bounds are optimal up to constant factors.Source: §3.3 · pp. 19–20

4 Best of Both Worlds for Infinite Hypothesis Classes?

• The section defines “learnable in both worlds” as having both an exponential universal learner and a uniformly consistent learner with minimax-rate guarantees.This is the minimal setting for asking whether one algorithm can attain both guarantees whenever each is separately attainable.Source: §4 · p. 20

4.1 An Impossibility Result

• Theorem 11 constructs spaces learnable in both worlds with optimal uniform rate rn(δ) ≍ min{1, log(1/δ)/n}, yet no algorithm can achieve both guarantees simultaneously.The construction remains compatible with exponential universal learning because its distribution family excludes the distributions used for the nearly exponential lower bound in Theorem 7.Source: §4.1 · p. 21

4.2 Best-of-Both-Worlds Q-aggregation

• QBOB splits the data, runs the uniform and exponential learners, and Q-aggregates their outputs to achieve a prior- and temperature-parameterized trade-off between the two guarantees.Choosing πexp/πmini = Θ(e^n) yields exponential universal learning but a vacuous uniform guarantee, whereas equal prior weights yield a minimax-optimal uniform bound but constant universal failure probability.Source: §4.2 · pp. 22–23

4.3 Tightness of Theorems 11 and 12

• For any prescribed uniform rate 1/eφ(n), QBOB attains the optimal universal exponent n/eφ(n), up to constants and along the lower-bound subsequence, making it Pareto-optimal.Theorem 11 supplies matching lower bounds, so improving the universal rate necessarily sacrifices the uniform rate.Source: §4.3 · pp. 23–24

5 Conclusion

• For finite hypothesis classes, Q-aggregation is optimal under both universal exponential and uniform minimax notions.The conclusion contrasts this result with several aggregation strategies that fail to be optimal for at least one notion.Source: §5 · p. 25
• For countably infinite classes, exponential universal rates and uniform learning may both be possible, yet no algorithm can achieve both simultaneously.Combining minimax-optimal and exponential-rate algorithms through Q-aggregation realizes the exact trade-off.Source: §5 · p. 25
• Pruning with a threshold, online-to-batch averaging, and star estimation each fail to be optimal for at least one universal or uniform guarantee.These failures show that the finite-class compatibility result is not shared by many common aggregation principles.Source: §5 · p. 25
• Open problems include characterizing agnostic squared-loss universal rates, identifying all hypothesis-space and distribution-family trade-offs, and extending the analysis beyond exponential rates, regression, and squared loss.Theorem 11 supplies one trade-off class, but whether examples outside it exist remains open.Source: §5 · p. 25
• The broader motivation is an algorithmic account of when designers must choose between competing notions of optimality, with decision-theoretic admissibility as a possible alternative perspective.This frames the aggregation problem around compatibility between different optimality criteria.Source: §5 · p. 25

Appendix Contents

• The appendix includes a table of notation.Table 2 is identified as the appendix’s notation table.Source: Table 2 · p. 30

A Proofs of the Preliminary Lemmata

• Minimax tail optimality implies minimax optimality in expectation by integrating the tail bound, with constant C′ = 2C(1 + c + |log(c)|).The argument uses the simultaneous tail bound over δ and a layer-cake representation.Source: A Proofs of the Preliminary Lemmata · p. 30
• An exponential high-probability rate implies an exponential expectation rate, with the bound 2Ce^−cn obtained by choosing δ = Ce^−cn.The proof applies the layer-cake representation to the positive part of the excess risk and uses E(P,F)(bf) ≤ 1.Source: A Proofs of the Preliminary Lemmata · pp. 30–31
• A two-point construction shows that any algorithm has strictly positive risk with probability at least 2^−n under at least one distribution for infinitely many n.The distributions differ only on an unobserved point, while the algorithm outputs the same value on the event that all sampled inputs coincide.Source: A Proofs of the Preliminary Lemmata · p. 31
• The same two-point construction yields an expectation lower bound of (∆2/8)e^−n log 2 for infinitely many n.The result uses the separation ∆ = |y1 − y2| between the two candidate responses.Source: A Proofs of the Preliminary Lemmata · p. 31

B.1 Pruned-convex ERM and Midpoint Estimators

• Pruned-convex ERM splits the data, prunes the dictionary using the first half, and minimizes second-half empirical risk over the resulting convex hull.Its threshold satisfies lim sup_m→∞ τm,M(δ) = 0 for every fixed M and δ, so the estimator satisfies Definition 4.Source: §B.1 · pp. 31–32
• The midpoint estimator averages the empirical risk minimizer with a selected pruned candidate and likewise satisfies Definition 4 with a threshold vanishing for fixed M and δ.The construction places both averaged components in the pruned set’s convex hull.Source: §B.1 · p. 32
• For both estimators, the vanishing-threshold property permits applying Theorems 1 to 3 with BM(δ) = C1 log(2M/δ), as stated in Corollaries 1 and 2.The shared conclusion follows after verifying the pruning and convex-hull conditions for each procedure.Source: §B.1 · p. 32

B.2 Proof of Theorem 2

• The binomial-tail lemma underlying Theorem 2 is established uniformly for p,q ∈ (1/4,3/4), with q>p, by combining McKay’s bound, KL-divergence control, and constant absorption.The argument first derives a nonstrict inequality and then obtains strictness by perturbing q; small m is handled separately.Source: §B.2 · pp. 33–35
• Theorem 2 follows from a two-function Bernoulli construction in which pruning removes the optimal hypothesis with a binomial-tail probability, yielding the claimed lower bound.The proof uses f1 ≡ 0, f2 ≡ 1, deterministic X, and a sufficiently large sample regime; the event forces the estimator to select f2.Source: §B.2 · pp. 33–34

B.3 Proof of Theorem 3

• Theorem 3 uses the same two-function Bernoulli family to show that, on a threshold event, empirical pruning removes f1 and forces any convex-combination estimator to equal f2.Here E(P,F)(f1)=0, E(P,F)(f2)=2µ, while the empirical risks are Ȳ1 and 1−Ȳ1; Berry–Esseen lower-bounds the event probability.Source: §B.3 · p. 36

C.1 Summary of Relevant Quantities

• For the analysis, hypotheses are ordered by decreasing risk, with fM optimal, and the paper introduces population and empirical risks plus geometric quantities relative to fM.These definitions provide the coordinates used in the subsequent simplex reformulations.Source: §C.1 · p. 37

C.2 Rewriting the Minimization Problems

• Q-aggregation’s simplex problem is equivalent to an inequality-constrained simplex problem: solutions map one-to-one, and objective values remain unchanged.The analysis therefore works primarily with the reduced vector and reconstructs the final simplex coordinate as one minus the others’ sum.Source: §C.2 · p. 37
• The population formulation is convex and differentiable, satisfies Slater’s condition, and therefore admits strong duality and KKT characterization; the empirical estimator satisfies analogous KKT conditions.The Q-aggregation estimator is defined as a solution to the empirical problem, with nonnegative multipliers and complementary slackness.Source: §C.2 · pp. 38–39

C Proof of Theorem 5

• The proof of Theorem 5 distinguishes two cases treated by Lemmas 10 and 11, while the same concentration result, Lemma 13, supports both cases.Figure 6 summarizes this proof structure.Source: Figure 6 · p. 39

• The proof relies on the positive-semidefinite square-root decomposition of G, KKT characterizations, and attainment from compactness of the simplex and continuity of the objectives.The overall proof structure is summarized in Figure 6.Source: §C.3 · p. 39
• If a population solution ρ_Q satisfies Ψ(ρ_Q) < R_P(f_M), then f̂_ρQ eventually has strictly smaller risk than f_M with the stated high probability.The constants c and C depend only on F, P, and the fixed choice of ρ_Q.Source: §C.3 · p. 39
• If no population solution improves on R_P(f_M), then f̂_ρQ eventually satisfies R_P(f̂_ρQ) ≤ R_P(f_M) with the stated high probability.Here, the constants c and C depend only on F and P.Source: §C.3 · p. 39
• Theorem 5 follows by combining Lemmas 10 and 11 to obtain R_P(f̂_ρQ) ≤ min_j R_P(f_j) for all sufficiently large n.The argument uses R_P(f_M) = min_j R_P(f_j).Source: §C.3 · p. 39

Proof of Lemma 12

• If Ψ(ρQ) < RP(fM), then the corresponding aggregate satisfies RP(fρQ) < RP(fM).This follows from the nonnegative excess-risk and penalty terms under the simplex constraint.Source: §C.4 · pp. 40–41

Proof of Lemma 13

• Lemma 13 uses uniform concentration of empirical risks, Gram quantities, and distances to establish its claims with probability at least 1 − CM^2 exp(−c ε^2 n / M^2).The concentration events are obtained using Hoeffding’s inequality and a union bound for bounded fj and Y.Source: §C.4 · pp. 40–41
• KKT optimality conditions for ρQ and bρQ yield an inequality controlling their difference through the population and empirical Gram matrices.Subtracting the KKT equations, multiplying by bρQ,j − ρQ,j, and summing exploits complementary slackness and simplex constraints.Source: §C.4 · pp. 41–42
• The empirical deviation bound is combined with the simplex constraints to control the summed error and complete the proof of Lemma 13.The relevant coordinate sums are bounded by 2 because both vectors lie in the simplex.Source: §C.4 · p. 42

C.5 Proof of Lemma 11

• Lemma 11 shows that if the population objective has no improving simplex mixture, the empirical Q-aggregation weights assigned to sufficiently suboptimal coordinates vanish.The proof takes the zero population minimizer, chooses ε from positive risk gaps, and uses KKT conditions to force bρQ,j = 0 for j ∈ I>.Source: §C.5 · pp. 43–44
• The proof of Lemma 11 relies on a high-probability event controlling empirical-population deviations, with ε chosen using finitely many strictly positive margins.The resulting event has probability at least 1 − CM^2 exp(−c n/M^2), with c absorbing dependence on ε.Source: §C.5 · p. 43
• The remaining risk decomposition bounds each coordinate sum by zero, yielding RP(f̂ρQ) ≤ RP(fM) and completing Lemma 11.Coordinates in I> vanish, while coordinates corresponding to equal-risk hypotheses coincide with fM almost everywhere and contribute zero.Source: Conclusion · p. 44
• Lemma 15 characterizes improvement over the best hypothesis by equivalence between an improving simplex mixture and a population objective value below RP(fM).One direction uses a small convex combination and the quadratic expansion; the converse follows because the Gram-matrix quadratic term is nonnegative.Source: Conclusion · pp. 45–46

C.6 Proof of Proposition 4

• Proposition 4 applies the empirical KKT conditions and Lemma 13’s deviation bounds to show that coordinates violating the required margin condition receive zero Q-aggregation weight.The argument bounds |(G(bρQ−ρQ))j| by √ε and concludes bρQ,j = 0 under the stated condition.Source: §C.6 · pp. 46–47
• The Proposition 4 proof is invariant to the selected best hypothesis: choosing any f⋆ ∈ F⋆ rewrites the gaps and Gram terms relative to f⋆ before applying polarization.The reduction from the simplex with M−1 coordinates back to the full simplex preserves the relevant coordinates.Source: §C.6 · p. 47

D.1 Proof of Theorem 6

• The constructed class F is countable and admits an infinite VCL tree.F is a countable union of finite sets, and the explicitly constructed tree satisfies the VCL realization condition at every finite depth.Source: §D.1 · pp. 47–48
• A distribution on N × {0,1} has infimum risk zero over F, but no hypothesis in F attains it.Each fI vanishes outside a finite initial segment and therefore has positive risk, while hypotheses matching longer initial segments have risk converging to zero.Source: §D.1 · pp. 48–50
• The infinite VCL tree yields a binary distribution producing the theorem’s classification lower bound for infinitely many sample sizes.The proof invokes [11, Theorem 5.11] and sets c = c0/4 to transfer the classification lower bound to the desired result.Source: §D.1 · p. 49
• The required distribution is obtained by an independent Bernoulli construction whose supported levels almost surely contain label-one points at infinitely many positive-mass locations.Borel–Cantelli shows that all but finitely many supported levels contain a one, enabling both strict positivity of every hypothesis’s risk and approximation of the zero infimum.Source: §D.1 · pp. 49–50

Proof of Theorem 7

• Lemma 16 constructs a probability measure on {a1, ..., am, 0, 1} with mean y and mass at least αi on each ai, provided Σi αi ≤ ε.The conditions are ε ∈ (0, 1/2], y ∈ [ε, 1 − ε], ai ∈ [0, 1], and αi ≥ 0.Source: §D.2 · pp. 50–51
• Applying Lemma 16 pointwise, the proof constructs P0 and Pi so that g0 is Bayes-optimal for P0, while fi is exactly the conditional mean and Bayes regressor under Pi.The construction uses Qj supported on the first j hypothesis values at xj together with 0 and 1, and assigns deterministic labels fi(xj) on the tail j ≥ i under Pi.Source: §D.2 · p. 51
• The lower-bound argument splits into two cases: persistent positive asymptotic error yields the claim directly, while vanishing error under some alternatives is handled by comparing P0 with Pi.For the second case, disagreement at xi creates excess risk under Pi, whereas under P0 the algorithm cannot distinguish the relevant samples on suitable events.Source: §D.2 · pp. 51–52
• Conditional independence between prefix and tail labels, together with a binomial Chernoff bound, controls the comparison events and produces the required infinitely-often lower bound.The selected index satisfies i_n → ∞ and i_n ≤ √n, implying log 2 · i_n = o(n) and completing the proof.Source: §D.2 · pp. 52–53

Proof of Theorem 10

• Lemma 17 supplies probability masses and increasing subsequences satisfying piℓ=c0R(nℓ), enabling the construction to force excess risk proportional to R(nℓ) infinitely often.The argument handles convex combinations and finite combinations separately, choosing widths biℓ=2k(nℓ) in the finite-combination case and using local averaging to obtain the constant lower bound.Source: §D.3 · pp. 53, 56
• The distribution Pz is realizable for every sample size, has infimum risk zero, yet every finite hypothesis incurs positive risk at a later level of mass c0R(nℓ).Source: §D.3 · p. 55

Optimal algorithm A⋆

• The explicit learner A⋆ achieves zero excess risk with exponential probability on PF and, with probability at least 1−δ, excess risk at most log(1/δ)/n.A⋆ outputs the zero predictor when all labels vanish and otherwise identifies the unique realizing hypothesis from the first nonzero label; its exponential exponent is q when q>0 and can be 1 when q=0.Source: §D.3 · pp. 57–58

Lower bounds on universal and minimax rates

• A deterministic learner cannot improve the universal lower bound exp(−n log(2)) with excess risk at least 1/32, nor the minimax lower bound log(1/δ)/(64n).The proof uses two realizable distributions that are indistinguishable on an all-zero sample event, choosing q=1/2 for the universal bound and q=1−log(1/δ)/(2n) for the minimax bound.Source: §D.3 · p. 58

Class construction

• A countable class of binary predictors is constructed by indexing finite binary sequences and extending them with value 1 outside their indexed coordinates.The class is countable because it is a countable union of finite sets.Source: §D.4 · p. 58

Lower bound construction

• For any finite m and binary vector z, P_z samples a uniformly random coordinate J in [m] and labels it z_J, while f_z has zero risk.Thus every constructed instance belongs to the relevant class of problems and has infimum risk 0.Source: §D.4 · p. 58

Lower bound argument

• Averaging over random z shows that predictions on coordinates unseen in the sample incur unavoidable error, with at most n coordinates observed.The argument uses independence of unseen labels, the inequality a^2 + (a − 1)^2 ≥ 1/2, and |O(U)| ≤ n.Source: §D.4 · pp. 58–59

Lower bound conclusion

• Because the averaged lower bound holds for some z(m) and m can be arbitrarily large, it yields the claimed lower bound for every deterministic algorithm and sample size.The witness distribution is selected from the finite binary family after averaging over z.Source: §D.4 · p. 59

Matching upper bound

• The constant algorithm A_1/2, predicting 1/2 everywhere, provides the matching upper bound for every distribution and function class.Combining this upper bound with the lower bound proves the theorem.Source: §D.4 · p. 59

D.5 Proof of Theorem 9

• Theorem 9’s algorithm scans the first ψ(n) hypotheses and replaces the current index when a later hypothesis empirically improves by at least τ_n, returning f_bi.Here ψ(n)=max{1,⌈φ(n)⌉} for φ(n)→∞ and φ(n)=o(n).Source: §D.5 · p. 59
• For sufficiently large n, the scan returns the first optimal hypothesis f⋆ because ψ(n) reaches its index and τ_n is below the preceding optimality gap.After reaching f⋆, the proof shows that no later candidate replaces it under the stated empirical-risk events.Source: §D.5 · pp. 59–60
• Hoeffding’s inequality and union bounds over the scanned hypotheses control the failure probability, while ψ(n)=o(n) yields the claimed bound for all n.The argument treats hypotheses before and after the first optimum separately and adjusts constants to cover finite n.Source: §D.5 · p. 60

E Proof of Theorem 11

• Theorem 11’s proof proceeds by constructing the dictionary and distributions, establishing learnability in both worlds, and then proving a lower bound for any learner.The cited proof roadmap assigns these steps to Appendices E.1, E.2, and E.3.Source: E Proof of Theorem 11 · p. 60

E.1 Construction of the Distributions

• The construction starts from a measurable noiseless target f∞, an injection indexing auxiliary points z_j,ℓ, and distributions Q_i supported on two cases.The coefficients defining Q_i are nonnegative, sum to one, and have conditional mean y_i; the mass on f_i(x_i) is at least ε.Source: §E.1 · pp. 60–61
• The family P={P∞}∪{P_j,ℓ:j,ℓ∈N} combines a base distribution with alternatives whose conditional laws are assigned across the indexed support.Under P∞, X has masses p_i and Y|X=x_i follows Q_i.Source: §E.1 · p. 61
• Under P∞, the conditional mean at xi equals yi = f∞(xi), making f∞ Bayes optimal for squared loss; each fk has risk at least f∞’s risk.Source: §E.1 · p. 61
• Under each P_j,ℓ, the prefix condition and the assignments at x_j and z_j,ℓ make f_j agree with the conditional mean on the support, so f_j is Bayes optimal.Thus the alternatives designate different dictionary elements as optimal in their respective distributions.Source: §E.1 · p. 61

E.2 Learnability in Both Worlds

• Aexp achieves the exponential universal rate by outputting the Bayes rule f∞ when no certificate appears and fj when a certificate for index j is observed.Under P∞ it always outputs f∞, while under Pj,ℓ observing zj,ℓ makes it output fj.Source: §E.2 · p. 61
• Amini achieves the uniform minimax rate 24 log(1/δ)/n by combining certificate-based selection with the largest observed prefix index.Its analysis handles both the no-certificate case under P∞ and certificate or prefix observations under Pj,ℓ.Source: §E.2 · pp. 61–62
• The exponential probability scale is unavoidable for zero excess risk: any learner fails with exponential-order probability under either P∞ or P2,1 for infinitely many n.The indistinguishable conditional samples force a learner to be wrong at x2 under one of the two distributions.Source: §E.2 · pp. 62–63
• The minimax rate log(1/δ)/n cannot be improved up to constants, because adjacent distributions with the same conditional sample law force failure with probability at least δ.The construction compares Pt,ℓ and Pt+1,ℓ and yields the stated lower bound in either learner-prediction case.Source: §E.2 · p. 63

E.3 Lower Bound for Any Learner

• The E.3 lower bound selects tn and ℓn so that certificate absence is likely while the learner’s behavior can be compared under P∞ and Ptn,ℓn.The construction uses tn = ⌈log2(φ(n))⌉, ℓn = max{1, ⌈log2 n⌉}, and likelihood comparisons on certificate-free events.Source: §E.3 · p. 64
• For infinitely many sample sizes, one alternative yields a nontrivial excess-risk lower bound under P∞ when the learner’s prediction favors the wrong Bayes value.The first alternative is explicitly identified with P = P∞.Source: §E.3 · p. 64
• The complementary alternative yields the lower bound under Ptn,ℓn, so no learner can avoid the trade-off across the two worlds.The second case uses the Bayes value at xtn under Ptn,ℓn and completes the two-distribution lower-bound argument.Source: §E.3 · p. 64

F Proof of Theorem 12

• The proof invokes Theorem 13, which gives Q-aggregation a high-probability minimax guarantee for bounded squared-loss regression over finite classes with positive prior weights and sufficiently large β.The theorem applies to any function class F ⊆ M of cardinality M and any distribution over X × [0,1].Source: F Proof of Theorem 12 · p. 65
• The constrained aggregation parameter is characterized as the projection of the unconstrained quadratic minimizer onto [0, 1], with degenerate affine cases handled through the tie-breaking rule.This reduction supplies the parameter representation used in both guarantee proofs.Source: F Proof of Theorem 12 · p. 66

F.1 Universal Exponential-Rate Guarantee for QBOB

• The universal-rate proof conditions on a realization where the exponential-rate candidate has risk at most the best comparator risk, then studies the interpolation between the exponential and minimax candidates.Convexity directly handles one case, while the other uses continuity to locate an interpolation parameter attaining the comparator risk.Source: §F.1 · p. 66
• The proof shows that the selected aggregation parameter lies within the admissible interpolation range, ensuring the aggregated predictor has risk no larger than the comparator risk.The argument treats the zero-discrepancy case separately and otherwise bounds the unconstrained minimizer by the rightmost quadratic root.Source: §F.1 · p. 67
• Bernstein’s inequality controls the empirical condition governing that parameter, after bounding the range and variance of a combined random variable built from the two candidate predictors.A constant-factor comparison of the relevant terms completes the exponential-rate guarantee.Source: §F.1 · pp. 67–69

F.2 Minimax Guarantee for QBOB

• Independence of the auxiliary and training samples permits a union bound, yielding simultaneous occurrence of both events and completing the minimax guarantee for QBOB.The two events each have failure probability at most δ/2, giving overall probability at least 1 − δ.Source: §F.2 · p. 69
• For the minimax guarantee, QBOB is identified with Q-aggregation on the two-function class consisting of the exponential-rate and minimax candidates, so Theorem 13 applies to its sample-based output.The argument uses β ≥ c2 and combines the resulting event with the exponential-rate event.Source: §F.2 · p. 69