On the Rademacher Complexity of Linear Hypothesis Sets
- URL: http://arxiv.org/abs/2007.11045v1
- Date: Tue, 21 Jul 2020 19:08:21 GMT
- Title: On the Rademacher Complexity of Linear Hypothesis Sets
- Authors: Pranjal Awasthi, Natalie Frank, Mehryar Mohri
- Abstract summary: We present a tight analysis of the empirical Rademacher complexity of the family of linear hypothesis classes with weight vectors bounded in $ell_p$-norm for any $p geq 1$.
This provides a tight analysis of generalization using these hypothesis sets and helps derive sharp data-dependent learning guarantees.
- Score: 45.06091849856641
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Linear predictors form a rich class of hypotheses used in a variety of
learning algorithms. We present a tight analysis of the empirical Rademacher
complexity of the family of linear hypothesis classes with weight vectors
bounded in $\ell_p$-norm for any $p \geq 1$. This provides a tight analysis of
generalization using these hypothesis sets and helps derive sharp
data-dependent learning guarantees. We give both upper and lower bounds on the
Rademacher complexity of these families and show that our bounds improve upon
or match existing bounds, which are known only for $1 \leq p \leq 2$.
Related papers
- Equivalence of the Empirical Risk Minimization to Regularization on the
Family of f-Divergences [49.853843995972085]
The solution to empirical risk minimization with $f$-divergence regularization (ERM-$f$DR) is presented.
Examples of the solution for particular choices of the function $f$ are presented.
arXiv Detail & Related papers (2024-02-01T11:12:00Z) - Adversarial Contextual Bandits Go Kernelized [21.007410990554522]
We study a generalization of the problem of online learning in adversarial linear contextual bandits by incorporating loss functions that belong to a Hilbert kernel space.
We propose a new optimistically biased estimator for the loss functions and reproducing near-optimal regret guarantees.
arXiv Detail & Related papers (2023-10-02T19:59:39Z) - Prediction, Learning, Uniform Convergence, and Scale-sensitive
Dimensions [39.97534972432276]
We present a new general-purpose algorithm for learning classes of $[0,1]$-valued functions.
We prove a general upper bound on the expected absolute error of this algorithm.
We show how to apply both packing bounds to obtain improved general bounds on the sample complexity of learning.
arXiv Detail & Related papers (2023-04-21T15:51:35Z) - Generalization Analysis for Contrastive Representation Learning [80.89690821916653]
Existing generalization error bounds depend linearly on the number $k$ of negative examples.
We establish novel generalization bounds for contrastive learning which do not depend on $k$, up to logarithmic terms.
arXiv Detail & Related papers (2023-02-24T01:03:56Z) - Robust Linear Predictions: Analyses of Uniform Concentration, Fast Rates
and Model Misspecification [16.0817847880416]
We offer a unified framework that includes a broad variety of linear prediction problems on a Hilbert space.
We show that for misspecification level $epsilon$, these estimators achieve an error rate of $O(maxleft|mathcalO|1/2n-1/2, |mathcalI|1/2n-1 right+epsilon)$, matching the best-known rates in literature.
arXiv Detail & Related papers (2022-01-06T08:51:08Z) - Localization, Convexity, and Star Aggregation [0.0]
Offset Rademacher complexities have been shown to imply sharp, linear-dependent upper bounds for the square loss.
We show that in the statistical setting, the offset bound can be generalized to any loss satisfying certain uniform convexity.
arXiv Detail & Related papers (2021-05-19T00:47:59Z) - Bilinear Classes: A Structural Framework for Provable Generalization in
RL [119.42509700822484]
Bilinear Classes is a new structural framework which permits generalization in reinforcement learning.
The framework incorporates nearly all existing models in which a sample complexity is achievable.
Our main result provides an RL algorithm which has sample complexity for Bilinear Classes.
arXiv Detail & Related papers (2021-03-19T16:34:20Z) - Relative Deviation Margin Bounds [55.22251993239944]
We give two types of learning bounds, both distribution-dependent and valid for general families, in terms of the Rademacher complexity.
We derive distribution-dependent generalization bounds for unbounded loss functions under the assumption of a finite moment.
arXiv Detail & Related papers (2020-06-26T12:37:17Z) - Adversarial Learning Guarantees for Linear Hypotheses and Neural
Networks [45.06091849856641]
We give upper and lower bounds for the adversarial empirical Rademacher complexity of linear hypotheses.
We extend our analysis to provide Rademacher complexity lower and upper bounds for a single ReLU unit.
Finally, we give adversarial Rademacher complexity bounds for feed-forward neural networks with one hidden layer.
arXiv Detail & Related papers (2020-04-28T15:55:16Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.