Research map / Learning theory and algorithms / Sample complexity

Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale

NeurIPS 2026 · Learning theory and algorithms › Sample complexity · approach: Robust and surrogate-loss learning bounds · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proves that for bounded real-valued classes, uniform convergence at scale γ, agnostic learnability at γ/2, and finite fat-shattering at all larger scales are equivalent, sharpens covering-number bounds, and derives a sharp 3-factor evaluability dichotomy for bounded IPMs.

Problem

Determine the optimal scale at which real-valued function classes exhibit uniform convergence and learnability in terms of fat-shattering dimension, tighten empirical covering-number bounds, and characterize evaluability of IPMs.

Approach

Bounds empirical ℓ∞ covering numbers directly (via disambiguation of partial concept classes and iterative refinement) instead of through packing numbers, avoiding the factor-2 scale loss; this yields uniform convergence at the optimal scale γ and the sharp log^2 / log entropy regimes.

Key results

• Uniform convergence at scale γ is equivalent to agnostic learnability at γ/2 and finite fat-shattering at all γ'>γ; sample complexity improves to Õ(d/ε^2) from Long's Õ(d/ε^3).
• Empirical entropy H(F,γ,n) is Θ(n) for γ<γ*/2, O(log^2 n) on (γ*/2, 2γ*], and O(log n) above 2γ*, with an Ω(log^{2-o(1)} n) lower bound on the middle regime.
• Every bounded IPM is either estimable or weakly evaluable with optimal scale c=3.

Surprising findings

• The O(log^2 n) covering bound is tight (up to lower-order terms) in the intermediate regime, not just an upper bound.

Limitations

• Logarithmic factors in the sample complexity remain (removal left open).
• Intermediate regime γ* < γ ≤ 2γ* entropy characterization left open.
• Covering results only for ℓ∞ metric; other ℓp metrics open.

Experimental setup

Metrics: sample complexity metric entropy growth H(F,γ,n) weak evaluability factor c

Baselines: Long's O(d/ε^3) learnability bound Alon et al. O(log^2 n) entropy bound Rudelson-Vershynin O(log^{1+ε} n) bound

Builds on: Long (COLT 01) fat-shattering learnability Alon et al. (JACM 97) covering bounds Rudelson and Vershynin (2006) Aiyer et al. (ICML 26) evaluability Bartlett and Long

Closest papers by meaning

• Transductive Learning is Compact (NeurIPS 2024 · similarity 0.87)
• Learning Distributions from Multiple Data Providers (NeurIPS 2026 · similarity 0.86)
• Strategic PAC Learnability via Geometric Definability (NeurIPS 2026 · similarity 0.85)
• Testably Learning Polynomial Threshold Functions (NeurIPS 2024 · similarity 0.85)
• On Agnostic PAC Learning in the Small Error Regime (NeurIPS 2025 · similarity 0.85)
• Learning High-Degree Parities: The Crucial Role of the Initialization (ICLR 2025 · similarity 0.85)