On the Rademacher Complexity of Linear Hypothesis Sets
This work offers a theoretical foundation for deriving sharp data-dependent generalization guarantees in machine learning, addressing a gap in existing analyses for broader norm constraints.
The paper tackles the problem of analyzing the empirical Rademacher complexity for linear hypothesis classes with weight vectors bounded in ℓ_p-norm for any p ≥ 1, providing tight upper and lower bounds that improve or match existing results limited to 1 ≤ p ≤ 2.
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$.