Relative Deviation Margin Bounds
We present a series of new and more favorable margin-based learning guarantees that depend on the empirical margin loss of a predictor. We give two types of learning bounds, both distribution-dependent and valid for general families, in terms of the Rademacher complexity or the empirical $\ell_\infty$ covering number of the hypothesis set used. Furthermore, using our relative deviation margin bounds, we derive distribution-dependent generalization bounds for unbounded loss functions under the assumption of a finite moment. We also briefly highlight several applications of these bounds and discuss their connection with existing results.
Code (0)
등록된 구현이 없습니다.
Tasks
Generalization BoundsvalidSimilar Papers 제목 키워드 기반
Differentially Private Learning with Margin Guarantees
We present a series of new differentially private (DP) algorithms with dimension-independent margin guarantees. For the family of linear hypotheses, we give a pure DP learning algorithm that benefits from relative deviat…
Model SelectionImproving Generalization Bounds for VC Classes Using the Hypergeometric Tail Inversion
We significantly improve the generalization bounds for VC classes by using two main ideas. First, we consider the hypergeometric tail inversion to obtain a very tight non-uniform distribution-independent risk upper bound…
Generalization BoundsSimple Relative Deviation Bounds for Covariance and Gram Matrices
We provide non-asymptotic, relative deviation bounds for the eigenvalues of empirical covariance and Gram matrices in general settings. Unlike typical uniform bounds, which may fail to capture the behavior of smaller eig…
Relative Deviation Learning Bounds and Generalization with Unbounded Loss Functions
We present an extensive analysis of relative deviation bounds, including detailed proofs of two-sided inequalities and their implications. We also give detailed proofs of two-sided generalization bounds that hold in the …
Generalization BoundsregressionOn the Complexity of Linear Prediction: Risk Bounds, Margin Bounds, and Regularization
We provide sharp bounds for Rademacher and Gaussian complexities of (constrained) linear classes. These bounds make short work of providing a number of corollaries including: risk bounds for linear prediction (including …