An Improved Uniform Convergence Bound with Fat-Shattering Dimension
The fat-shattering dimension characterizes the uniform convergence property of real-valued functions. The state-of-the-art upper bounds feature a multiplicative squared logarithmic factor on the sample complexity, leaving an open gap with the existing lower bound. We provide an improved uniform convergence bound that closes this gap.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Fat Shattering, Joint Measurability, and PAC Learnability of POVM Hypothesis Classes
We characterize learnability for quantum measurement classes by establishing matching necessary and sufficient conditions for their PAC learnability, along with corresponding sample complexity bounds, in the setting wher…
Prediction, Learning, Uniform Convergence, and Scale-sensitive Dimensions
We present a new general-purpose algorithm for learning classes of $[0,1]$-valued functions in a generalization of the prediction model, and prove a general upper bound on the expected absolute error of this algorithm in…
PredictionComputing the Shattering Coefficient of Supervised Learning Algorithms
The Statistical Learning Theory (SLT) provides the theoretical guarantees for supervised machine learning based on the Empirical Risk Minimization Principle (ERMP). Such principle defines an upper bound to ensure the uni…
Learning TheoryScale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale
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 …
Sample Complexity Result for Multi-category Classifiers of Bounded Variation
We control the probability of the uniform deviation between empirical and generalization performances of multi-category classifiers by an empirical L1 -norm covering number when these performances are defined on the basi…