Abstract:
We study scale-sensitive combinatorial dimensions for classes of bounded real-valued functions, focusing on their relationship with uniform laws of large numbers and empirical covering numbers.
Our main result gives a sharp scale-sensitive characterization of uniform laws of large numbers for real-valued function classes, improving the classical result of Bartlett and Long (1998) by removing a factor-of-two loss and achieving an equivalence at the optimal scale. The key technical ingredient is a direct bound on empirical covering numbers in terms of scale-sensitive combinatorial dimension. This yields sharp asymptotic metric-entropy bounds and resolves questions of Alon–Ben-David–Cesa-Bianchi–Haussler (1997) and Rudelson–Vershynin (2006).
The talk will present the combinatorial structure behind these results, including the role of partial concept classes, disambiguation, and scale-sensitive analogues of Sauer–Shelah type arguments.
