Encoding orders and trees in real-valued functions

We study the optimal scale at which real-valued function classes exhibit uniform convergence and learnability. Our main result establishes a scale-sensitive generalization of the fundamental theorem of PAC learning: for every bounded real-valued class and every $γ>0$, uniform convergence at scale $γ$, agnostic learnability at scale $γ/2$, and finiteness of the fat-shattering dimension at every scale $γ'>γ$ are equivalent. This resolves a question by Anthony and Bartlett (Cambridge Univ. Press 1999) on the precise scales governing learnability, refuting a conjecture attributed there to Phil Long that a multiplicative 2-factor gap is unavoidable, and improves the upper bounds of Bartlett and Long (JCSS 1998), which incur such a loss. The key technical ingredient is a direct bound on empirical $\ell_\infty$ covering numbers, avoiding the standard detour through packing numbers. As a consequence, we obtain sharp asymptotic metric-entropy bounds in terms of the fat-shattering scale $γ$: an $O(\log^2 n)$ bound holds already at scale $γ/2$, while an $O(\log n)$ bound holds at scale $2γ$. We further show that the $O(\log^2 n)$ bound is sometimes tight. These results resolve open questions by Alon et al. (JACM 1997) and Rudelson and Vershynin (Ann. of Math. 2006). As an application, we establish a sharp dichotomy for bounded integral probability metrics: every such IPM is either estimable or cannot be weakly evaluated within any multiplicative factor $c<3$, while $3$-weak evaluability always holds, resolving an open question from Aiyer et al. (ICML 2026). We also highlight several open questions on quantitative sample complexity and evaluability.

In learning theory, the sign rank of a binary concept class captures the smallest dimension in which it can be represented by points and halfspaces. Despite tremendous interest, lower bounds on sign rank are notoriously difficult to come by. Two recent approaches to the problem establish lower bounds on sign rank by measures that are easier to analyze: the $\mathbb{Z}_2$-index and the list replicability number. We order these measures, showing that the $\mathbb{Z}_2$-index is upper-bounded by a linear function of the list replicability number. As a main consequence, we obtain a strong separation between sign rank and $\mathbb{Z}_2$-index, thereby resolving a question of Frick, Hosseini, and Vasileuski. This motivates a thorough study of list replicability, the stronger of the two lower-bounding measures. We establish upper bounds on the list replicability number by two combinatorial measures: height and minimum star number. We also prove a fundamental composition result, showing that the product of two concept classes has list replicability number bounded by the sum of the list replicability numbers of the two classes.

This paper answers the one-dimensional local root anti-concentration questions posed by Balcan, Pegden, and Sharma in the context of online optimization of piecewise-Lipschitz functions. For a homogeneous feature curve and coefficients whose density relative to the uniform law on a symmetric convex body $K$ is bounded by $A$, we show that the worst-case interval-hitting constant equals $A$ times a section-averaged projective incidence speed. For cube-supported coefficients, this speed is equivalent, up to universal constants, to the projective Lipschitz constant. This yields a sharp, dimension-free characterization and removes the previous $\sqrt N$ loss. For monic degree-$d$ polynomials under arbitrary coefficient laws, we prove that the interval-hitting constant is finite if and only if the ordered real-root laws have bounded densities, with a factor-$d$ comparison that is sharp. Conditional and joint coefficient-space area formulas, together with a two-chart certificate, make this criterion verifiable for dependent and singular coefficient laws. We also give two graph-learning applications that complete the transition-to-regret chain. A cost-sensitive Gaussian-RBF harmonic classifier uses the projective incidence theorem and achieves expected regret $\widetilde O((An^2D e^{BD}/\ell+1)\sqrt T)$. A common-offset polynomial-kernel model uses rigid translation of the ordered roots and achieves $\widetilde O((qn^2κ+1)\sqrt T)$ regret, even when the induced coefficient law is singular in the ambient coefficient space.