An Agnostic Sample Compression Scheme for Squared Loss of Near-Linear Size in the Fat-Shattering Dimension

1 Introduction

• Prior bounded-size regression compression bounds use a primal–dual fat-shattering product, and the open question asks for an agnostic ℓ2 scheme using only primal fat-shattering dimension up to polylogarithmic factors.The dual dimension can be exponentially larger than the primal dimension.Source: §1 · p. 2

1.1 Main result

• The main theorem gives deterministic agnostic empirical squared-loss compression of size C fat(F, c′α) log^3(2/α), independent of sample length, with additive error α.This answers the stated open problem at the same scale in the fat-shattering dimension and removes the dual factor.Source: §1.1 · p. 2

1.2 Technique overview

• For average loss over the bounded range, accuracy on a (1 − ε)-fraction of sample points suffices, so K´egl’s margin bound limits boosting to O(log(1/ε)) rounds independent of m.This avoids the uniform-accuracy sparsification step through which prior constructions incur the dual factor.Source: §1.2 · p. 2
• The compressor boosts toward synthetic labels f∗(xi) from a near-minimizer, transmits quantized values as side information, and uses a weak-learning scale Θ(α) to control the squared-loss cross term.The cross term requires closeness to f∗ of order α, not merely √α.Source: §1.2 · p. 3

1.3 Related work

• Earlier agnostic and realizable schemes carry a primal–dual product; the paper removes the dual factor in both settings, while bypassing a conditional route through binary compression.The related-work discussion notes that the binary-compression route depends on the unresolved binary sample-compression conjecture.Source: §1.1 · p. 2, §1.3 · p. 3

Setting and compression

• The setting uses finite samples with arbitrary labels in [0, 1], and an agnostic compression scheme stores original labeled examples plus bits to reconstruct a function with empirical loss within α of the class optimum.The stored size must be finite independently of the sample length.Source: §2 · pp. 3–4

Fat-shattering dimension

• The fat-shattering dimension counts the largest set shattered at scale t using thresholds, while the dual dimension swaps the roles of points and functions.For [0, 1]-valued classes, the threshold witnesses may be taken in [0, 1].Source: §2 · p. 4

Imported results

• The imported MedBoost procedure updates distributions over sample points using weak hypotheses, while the generic tolerant weak learner supplies class members close to a target on sampled points.The paper states that its adaptations of the imported results are carried out in the analysis.Source: §2 · pp. 4–5

3.1 Parameters

• The parameters set d = fat(F, c′α), choose the learning scale and error tolerances, and bound the number of rounds through a fixed per-round contraction.The fixed components include well-orderings and quantization tie-breaking rules.Source: §3.1 · p. 5

3.2 Fixed components

• Fixed well-orderings select class members and canonicalize stored points, while fixed tie-breaking rules make tuple selection, quantization, and weighted medians deterministic.The scheme’s definition imposes no computability or measurability requirements.Source: §3.2 · p. 5

3.3 Compression map κα

• The compressor chooses a near-minimizer, boosts toward its synthetic labels, and stores original examples with quantized target values and round-incidence or weight information.Repeated draws are stored once; the synthetic target values are carried in side information rather than stored as labels.Source: §3.3 · p. 6

3.4 Reconstruction map ρα

• The reconstructor uses stored points, quantized values, incidence vectors, and weights, but not the near-minimizer, unsaved sample points, sample length, or optimum loss.Stored original labels are not used by the reconstruction map.Source: §3.4 · p. 6

4.1 The degenerate case d = 0

• When fat(F,t)=0, all class functions differ pointwise by at most 2t, allowing empty compression when d=0.The analysis uses this diameter bound to show the fixed least element achieves error below the target.Source: §4.1 · p. 7

4.2 From Lemma 2 to the MedBoost weak learner

• The restriction class has fat-shattering dimension no larger than F’s, enabling a weak hypothesis for synthetic labels with probability at least 1/2.The weak learner uses quantized values of a near-optimal f* as targets; the compressor selects a good tuple deterministically.Source: §4.2 · pp. 7–8

4.3 Explicit contraction of the K´egl factor

• The calculation establishes λ < 1, so the supported result is only that this displayed quantity is subunit; the supplied passages do not state the claimed round-count bound or bad-point fraction.Source: §4.3 · p. 9

4.4 Quantizing the normalized weights

• With N=64T, normalized boosting weights are quantized to total variation at most 1/128=γ/16 using integers that require bits independent of m.Each integer uses ⌈log2(N+1)⌉ bits.Source: §4.4 · p. 9

4.5 Quantile stability and the strict/nonstrict interface

• When total variation is below s, every quantized-weight median lies within the exact-weight quantile interval controlled by Kégl’s guarantee.In this scheme, TV(w, w̃)≤γ/16<γ/2=s.Source: §4.5 · p. 9

4.6 Empirical approximation of f∗and the agnostic closure

• The reconstruction is η/2-accurate on all points in the infinite branch and, in the finite branch, on all but at most εm points.On the remaining points, bounded [0,1] values bound the squared distance; the triangle inequality then closes the agnostic squared-loss guarantee.Source: §4.6 · p. 10

4.7 Size

• The scheme uses O(d log^3(2/α)) total size, with no dependence on sample length m in any field.The bound follows from n=O(dL), T=O(L), and bq=O(L), where L=ln(2/α).Source: §4.7 · p. 10

• Avoiding sparsification removes the dual factor even for realizable regression compression, where an ε-fraction of uncontrolled points is affordable and Kégl’s bound keeps rounds independent of m.The resulting realizable guarantee is L2( f̂, S) ≤ α.Source: §5 · p. 11
• Exact bounded-size agnostic compression is impossible for ℓp, p ∈ (1, ∞), and the proof does not extend to unbounded labels because its squared-loss cross term is uncontrolled.The scheme’s size bound also diverges logarithmically as α → 0.Source: §5 · p. 11
• The result is unconditional and at the fat-shattering scale, but it does not resolve the separate open problem on reductions for fat-shattering classes.Attias et al. (2025) give a regression-to-binary-compression reduction via pseudo-dimension, with near-linear output conditional on the binary sample compression conjecture and without preserving scale.Source: §5 · p. 11
• Stored original examples remain necessary because points in a general infinite domain have no finite-bit encoding; synthetic values must therefore travel as side information, not relabeled examples.The stored labels are never read by the reconstructor.Source: §5 · p. 11
• The scheme is information-theoretic, not necessarily computable, and its constants are large; the authors do not optimize the exponent 3 of the polylogarithm.The stated constant gives 1/(−ln λ) ≈ 122.3 and T ≥ 509 already at α = 1.Source: §5 · p. 11