Risk minimization by median-of-means tournaments

1 Introduction

• An accuracy is achievable when a procedure attains it with constant probability for every admissible target, and the accuracy edge is the smallest such accuracy.Source: §1 · p. 3
• The procedure achieves the best possible accuracy/confidence tradeoff almost up to the achievable accuracy edge under minimal assumptions.The reservation “almost” reflects that the edge is often unknown; the procedure also attains the optimal tradeoff for larger errors.Source: §1 · p. 3

1.1 ERM–the wrong choice

• ERM can attain optimal confidence near the accuracy edge with sub-Gaussian tails, but its performance weakens substantially when functions or targets are heavy-tailed.The paper attributes this sensitivity to atypical sample points distorting the empirical-loss minimizer.Source: §1.1 · p. 4
• In contrast, the proposed procedure achieves the optimal accuracy/confidence tradeoff in heavy-tailed settings and is insensitive even to many atypical sample points.Source: §1.1 · p. 4
• In the linear-regression example, the proposed method attains optimal confidence at accuracy proportional to the accuracy edge under the same assumptions.The paper contrasts this with ERM, for which edge-proportional accuracy offers only constant confidence.Source: §1.1 · p. 5
• For non-convex classes, the results apply to favorable targets of the form Y = f0(X) + W, where f0 is in the class and W is symmetric and independent of X.Source: §1.1 · p. 6

2 The accuracy edge and the accuracy/confidence tradeoff

• For convex centrally symmetric classes, λQ lower-bounds the accuracy edge for noise-free targets, while λM provides a lower bound for targets with independent Gaussian noise.For learning problems with minimal target sets, a further lower bound constrains the accuracy-confidence tradeoff.Source: §2 · pp. 7–8
• The lower estimate on the accuracy edge need not be sharp; the true edge may be larger, so the benchmark can be optimistic.The authors describe a more realistic conjecture based on global parameters that account for fine structure at arbitrarily small scales.Source: §2 · pp. 7–8
• The benchmark r* combines class-complexity parameters, while rE measures empirical oscillation and rM captures the interaction between the class and target.The target-dependent parameter uses an a-priori distance bound σ to restrict the centers considered, with a moment condition on the resulting multipliers.Source: §2 · pp. 8–9
• Theorem 2.10 gives the optimal accuracy-confidence tradeoff for any r ≥ 2r*, although the usable threshold must account for the unknown f*.The theorem's procedure selects a function from the data and, when independent additive noise is assumed, optimal tradeoffs still hold under assumptions close to those needed for the problem to be well defined.Source: §2 · pp. 9–10
• Theorem 2.11 relaxes the requirements for independent additive noise: it drops convexity and norm equivalence, retaining an Lq-to-L2 norm bound for q > 2 and mean-zero independent noise with finite variance.Its conclusion still gives the optimal accuracy-confidence tradeoff under these assumptions.Source: §2 · p. 10

2.1 State of the art

• Prior ERM guarantees based on a small-ball condition have a poor accuracy-confidence tradeoff under heavy tails; high confidence requires sub-Gaussian tails for both the class and residual.The paper characterizes ERM as falling short of the stated benchmarks in heavy-tailed settings.Source: §2.1 · p. 11

Regression in Rn revisited

• The linear-regression setting uses F = {⟨t, ·⟩: t ∈ Rn}, isotropic X, and target Y = ⟨t0, ·⟩ + W, with symmetric independent noise W in L2.The derivation assumes Lq and L2 norms are equivalent on span(F).Source: Regression in Rn revisited · p. 11
• When N ≥ cn, the procedure achieves the optimal accuracy-confidence tradeoff for any r ≥ c3σ n/N in isotropic linear regression with independent symmetric L2 noise.The stated accuracy edge has a lower bound proportional to σ n/N.Source: Regression in Rn revisited · pp. 11–12
• Two further examples obtain previously unknown optimal tradeoffs: regression on a convex centrally symmetric subset of Rn with sub-Gaussian design and possibly heavy-tailed targets, and regression in ρBn_1 under weaker assumptions on the underlying measure.The paper notes the relevance of the latter setting to sparse recovery, basis pursuit, and LASSO.Source: Regression in Rn revisited · p. 12

3 The median-of-means tournament

• With finite variance alone, median-of-means achieves high (sub-Gaussian) confidence even when sample observations may be atypical.It partitions observations into blocks, computes a mean per block, and takes the median of those means.Source: §3 · p. 12
• Rather than median-estimating each candidate's risk, the tournament compares pairwise risk differences and splits the sample across distance estimation, qualification, and final selection.The third round is unnecessary under Theorem 2.11's conditions, where mean squared error equals excess risk.Source: §3 · p. 13

3.1 The ‘referee’: the distance oracle

• With probability at least 1 − 2 exp(−cN), the distance oracle distinguishes pairs involving f*: proceeding implies distance at least r, while abandonment implies distance at most (β/α)r.Its guarantees are designed for matches involving f*, not necessarily every pair in F.Source: §3.1 · p. 14

3.2 The preliminary round

• Blockwise majority matches produce a qualifier set containing f*, with every qualifier within (β/α)r of f*.A match proceeds only when the distance oracle permits it; a player winning more than half the blocks wins the match.Source: §3.2 · p. 15

3.3 Champions league

• In the third-sample champions league, f* wins all its home matches, while any other champion must satisfy the stated lower bound on EΨ.The round's goal is to select a champion with small excess risk.Source: §3.3 · pp. 15–16

4 Examples

• Sharp estimates for the complexity parameters may require covering numbers for nearly arbitrary sets under arbitrary L2(μ) metrics, and are not simple to characterize in every example.The relevant process-oscillation estimates are also not completely understood.Source: §4 · p. 17
• The first example treats convex, centrally symmetric linear-regression sets with L-sub-Gaussian design and potentially heavy-tailed noise; the second uses a weaker design moment condition for sparse recovery.The sparse-recovery design condition follows the one used to guarantee basis pursuit's optimal measurement count.Source: §4 · p. 17
• In ρB1, the optimal accuracy-confidence tradeoff reaches a level proportional to the accuracy edge, even with heavy-tailed X and Y, unlike ERM.The estimates improve known bounds, and the optimal tradeoff extends down to that level.Source: §4 · p. 17, §4.1 · p. 22

4.1 Coverings and Gaussian processes

• For convex, centrally symmetric T and isotropic L-sub-Gaussian X, the tournament has optimal accuracy-confidence behavior for s ≥ cs* under the stated Lq-to-L2 residual condition.Theorem 4.5 improves on ERM, which requires sub-Gaussian residuals and gives the guarantee only at accuracy s*.Source: §4.1 · p. 20
• For sparse recovery sets, moment growth only up to order κ log n suffices for optimal Gaussian behavior, even when X and the regression noise are heavy-tailed.The design coordinates need not be independent, and some linear functionals may have no higher moments beyond p = κ log n.Source: §4.1 · p. 21
• Under Assumption 4.1, the multiplier- and empirical-process scales can be controlled as in the L-sub-Gaussian case, enabling the sparse-set bounds.The remaining covering and Gaussian mean-width quantities are described as well-understood.Source: §4.1 · p. 21
• The sparse-set bounds give optimal confidence for accuracies above a constant multiple of max{vQ, vM}, up to a level proportional to the lower estimate λ* on the accuracy edge.No procedure in ρB1 can attain accuracy below c3 max{vQ, vM} with confidence higher than 3/4.Source: §4.1 · p. 22

5 Proofs

• The proof replaces suprema over possible centers with the larger index set star(F−F,0)∩rD and uses star-shaped scaling to control parameter regularity across radii.The fixed-point constants depend only on q and L; Theorem 2.10 uses q=4, while Theorem 2.11 allows q arbitrarily close to 2 at the price of worse constants.Source: §5 · pp. 23–24

5.1 The preliminary round–proof

• With probability at least 1−2 exp(−cn), if ∥f−f*∥L2≥r, f* wins its match against f; equivalently, Bf,f*(j)>0 on a majority of blocks in any such match.Source: §5.1 · p. 24
• The signal term is positive on a fixed fraction of blocks because the Lq-L2 norm equivalence yields a small-ball property, which is uniformized using separated nets.The block argument gives at least (1−τ/6)n blocks with many coordinates of size at least κ0r, then extends the control from the net to F1.Source: The quadratic component · pp. 25–26
• Under E(f*(X)−Y)(f(X)−f*(X))≥0 for every f∈F, the noise term is at least −C1r²/2 on at least (1−τ/8)n blocks with probability at least 1−2exp(−C2τ²n).This location condition holds for closed convex F with f* the L2-nearest point to Y, and when Y=f0(X)+W with mean-zero W independent of X.Source: The multiplier component · pp. 28–29
• The preliminary-round proof bounds the centered empirical process by symmetrization, the Bernoulli contraction theorem for φ(t) = |t|, and de-symmetrization.The passage cites for these standard techniques.Source: The multiplier component · p. 32

5.2 Champions league–proof

• Conditioned on preliminary success, qualifiers lie within (β/α)r of f*, and the proof targets one with the prediction bound using C = 16(β/α)^2.The text distinguishes estimation—finding a function close to f*—from prediction, which requires choosing a qualifier with almost optimal statistical performance.Source: §5.2 · pp. 32–33
• The auxiliary empirical-process argument uses norm equivalence, symmetrization, contraction, de-symmetrization, and bounded differences to obtain an exponentially likely bound.Lemma 5.5 is stated under Theorem 2.10’s conditions with probability at least 1 − 2 exp(−cn).Source: §5.2 · pp. 33–34
• With probability at least 1 − 2 exp(−cn), any champions-league choice bf satisfies EΨ_{f*,bf} ≥ −2r_1^2, because f* wins its home matches and functions with worse comparisons lose to f*.The proof concludes that this bound suffices, by Lemma 3.6, to establish the stated prediction guarantee.Source: §5.2 · pp. 33–34

Additional remarks

• The identity of the accuracy edge remains open; it is unclear whether the gap between λ* and r* can close beyond sub-Gaussian classes with independent noise.The authors leave this question for future study.Source: Additional remarks · p. 35
• A net-based modification can attain accuracy proportional to λ* for convex L-sub-Gaussian classes with independent, potentially heavy-tailed noise.The authors do not pursue this special case further because it shifts attention from the accuracy-confidence tradeoff to the accuracy edge.Source: Additional remarks · p. 35
• Computationally finding the tournament winner is highly nontrivial and is outside the paper's scope.The authors note that derivative-free optimization with a function comparison oracle may be useful.Source: Additional remarks · p. 35

• Averaging a small number of independent copies yields a high-probability small-ball bound, even when the original norm-equivalence constants do not give probability 0.9.The number of copies and the resulting constants depend only on q and L; the argument uses norm equivalence and a Berry–Esseen-type bound.Source: A The distance oracle – outline of the… · p. 39
• Partitioning observations into blocks and applying a binomial estimate ensures at least 0.7k block averages satisfy the relevant bound with probability at least 1 − 2 exp(−c1k).The proof also invokes a Chebyshev-based bound with probability at least 0.8.Source: A The distance oracle – outline of the… · p. 39
• Finite ηr-nets control estimates on star(F − f∗, 0) ∩ rS simultaneously, with failure probability at most 2 exp(−c1k/2).The net cardinality is bounded by exp(c1k/2), and the proof controls deviations from net points across blocks.Source: A The distance oracle – outline of the… · pp. 39–40
• Positive homogeneity extends the isomorphic estimate from elements of norm r to larger norms because star(F − f∗, 0) is star-shaped around 0.The second claim is a one-sided upper estimate on Medℓ(v) over the corresponding star-shaped set.Source: A The distance oracle – outline of the… · p. 40
• With k = c(q, L)N, the estimates hold with probability at least 1 − 2 exp(−cN), for c depending only on q and L.This is the claimed probability for the estimates developed in the proof.Source: A The distance oracle – outline of the… · p. 40