On the Complexity of Linear Prediction: Risk Bounds, Margin Bounds, and Regularization

By Sham M. Kakade, Karthik Sridharan, Ambuj Tewari. 2008

412 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Statistical Learning Theory

Citations in the corpus

Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, background): “…include the VC dimension, covering numbers, algorithmic stability, Rademacher complexity, or flat minima (see, for instance, Srebro et al., 2010; Kakade et al., 2009; Zhou, 2002; Schapire et al., 1998; Koltchinskii et al., 2002; Bousquet and Elisseeff, 2002; Vapnik and Chervonenkis, 1971); the…”
Private federated learning on vertically partitioned data via entity resolution and additively homomorphic encryption (2017, background): “(201) When it comes to linear classifiers, two parameters are fundamental to bound the empirical Rademacher complexity: the maximum norm of the classifier and the maximum norm of an observation [Kakade et al., 2008, Patrini et al., 2016a].”
Smoothness, Low Noise and Fast Rates (2010, background): “Thus, Theorem 1 along with Rademacher complexity bounds from [11] gives us,”
Balanced Policy Evaluation and Learning (2017, background): “, for linear policies b Rn(F) = O(1/ p n) [19].”
A Reductions Approach to Fair Classification (2018, background): “We note that α = 1 / 2 in the vast majority of classiﬁer families, including norm-bounded linear functions (see Theorem 1 of Kakade et al., 2009), neural networks (see Theorem 18 of Bartlett & Mendelson, 2002), and classiﬁer families with bounded VC dimension (see Lemma 4 and Theorem 6 of Bartlett…”
Norm-Based Capacity Control in Neural Networks (2015, background): “The upper bounds presented here are particularly similar to generalization bounds in Kakade et al. (2009) and Balcan and Berlind (2014).”
Policy Evaluation and Optimization with Continuous Treatments (2018, background): “Assuming that ‖Xi‖2 ≤ X2, [10] shows that the Rademacher complexity of this class is bounded as R̂n(T ) ≤ W2X2 n .”
Regularization Techniques for Learning with Matrices (2009, methodology): “More recently, Kakade et al. [2008] showed how to use the very same duality for bounding the Rademacher complexity of classes of linear predictors.”
Implicit Bias of Gradient Descent on Linear Convolutional Networks (2018, background): “Such minimum norm or maximum margin solutions are of course very special among all solutions or separators that ﬁt the training data, and in particular can ensure generalization Bartlett and Mendelson [2003], Kakade et al. [2009].”
Entity Resolution and Federated Learning get a Federated Resolution (2018, positive): “(202) It is well-known that we have for linear classifiers whose L2 norm is bounded by θ∗ [17] (Theorem 3): Rm ≤ X∗θ∗ √ m .”
Comparing human-centric and robot-centric sampling for robot deep learning from demonstrations (2016, background): “Understanding how much data is needed to learn a function, is known as sample complexity analysis [4], [6], [13], [28].”
A study in Rashomon curves and volumes: A new perspective on generalization and model simplicity in machine learning (2019, background): “In other words, the Rashomon set benefits from having multiple similar models, while Rademacher complexity treats them as equivalent.”