Covering Number Bounds of Certain Regularized Linear Function Classes

By Tong Zhang. 2002

303 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.

Citations in the corpus

Spectrally-normalized margin bounds for neural networks (2017, methodology): “…and positive integer p be given, along with matrix X ∈ R n × d with The proof of Lemma 3.4 relies upon the Maurey sparsiﬁcation lemma (Pisier, 1980) which is stated in terms of sparsifying convex hulls, and in its use here is inspired by covering number bounds for linear predictors (Zhang, 2002).”
Machine learning with operational costs (2011, methodology): “Using the output of this algorithm within our generalization bound will yield a much tighter bound than in previous works (for example, the bound in Zhang, 2002, Theorem 3), especially when (r, q) = (∞, 1); this is true simply because we are counting more carefully.”
Regularization in reinforcement learning (2011, background): “For instance, Theorem 4 of Zhou [2003] shows its validity for a large class of RKHS with sufficiently smooth kernel functions.”
Max-Margin Markov Networks (2003, methodology): “[14] where in Step 3 (derandomization) we substitute the vector-valued FM and the metric (cid:26)M .”
On combining machine learning with decision making (2011, background): “ independently according to XY . Then for any >0, P(9lf 2lF: jR(f;fxi;yigm1) R(f)j>) 4E[N(=16;lF;kkL 1(m XY ) )]exp m2 128M2 bound : Proof See Theorem 24 in Pollard (1984) (also in Zhang, 2002, Theorem 1). Note that the constants have been rened in other works since the rst result and we hav”
Feature selection, L1 vs. L2 regularization, and rotational invariance (2004, methodology): “Some other well-known properties of covering numbers (e.g., Anthony and Bartlett, 1999; Zhang, 2002; Haus-sler, 1992) include that and that given a class of functions G with domain R , if F is a class of functions R (cid:2) Y 7!”
(Near) Dimension Independent Risk Bounds for Differentially Private Learning (2014, background): “We also note that the doubling dimension of regularized linear learning models can be shown to be either independent or logarithmically dependent on p (Zhang, 2002).”
Finite-Time Bounds for Fitted Value Iteration (2008, methodology): “In this case the bounds due to Zhang (2002) can be used.”
Regularized Policy Iteration with Nonparametric Function Spaces (2016, methodology): “This result might be obtained using Corollary 5 of Zhang (2002) as Assumption A4.”
On the Complexity of Linear Prediction: Risk Bounds, Margin Bounds, and Regularization (2008, methodology): “For all γ > 0, w ∈ W , L(w) ≤ Kγ(w) + 4 XW1 γ √ 2 log(d) n + √ log(log2 4XW1 γ ) n + √ log(1/δ) 2n The following result improves the best known results of the same kind, [Langford et al., 2001, Theorem 5] and [Zhang, 2002, Theorem 7], by removing a factor of √ log n.”
Compressed Least-Squares Regression (2009, background): “Truncation after the computation of the parameter α̂ ∈ R , which is the solution of an unconstrained optimization problem, is easier than solving an optimization problem under the constraint that ||α|| is small (which is the approach followed in [23]) and allows for consistency results and predictio”
Tight Sample Complexity of Large-Margin Learning (2010, background): “When‖X‖∞ ≤ 1, upper bounds on learning with L1 regularization guarantee a sample complexity of O(log(d)) for anL1-based learning rule [21].”
An Information Theoretic Framework for Multi-view Learning (2008, methodology): “Note that if the prediction space is bounded then it can be shown using covering number arguments (Zhang [2002]) where c is some constant (which depends of λ co and K ).”
Structure compilation: trading structure for features (2008, methodology): “Theorem 1 of Zhang (2002) (originally due to Pollard 11It su.ces to consider nonzero eigenvalues because zero eigenvalues correspond to non-identi.able directions, which are the same for all parameters .. (1984)) applied to M: With probability = 1 - d, * l Psup |E(p ,p.) -”
The Implicit and Explicit Regularization Effects of Dropout (2020, background): “Next, by Theorem 4 of (Zhang, 2002), for all choices of 1, a ą 0, there exists a set s Up 1, aq Ă tu P R : }u}2 ď au such that for any u P R, }u}2 ď a, there exists s u P s Up 1, aq such that |u xi ́s uxi| }xi}2 ď 1 @i “ 1, .”
Multi-View Intact Space Learning (2015, methodology): “We proceed to bound the Rademacher complexity of F by ﬁrst bounding its covering number [50], [51].”