$\ell_{\infty}$ Vector Contraction for Rademacher Complexity

Alexander Rakhlin; Dylan J. Foster

arxiv: 1911.06468 · v1 · pith:SQEJVPQJnew · submitted 2019-11-15 · 💻 cs.LG · math.ST· stat.ML· stat.TH

ell_(infty) Vector Contraction for Rademacher Complexity

Dylan J. Foster , Alexander Rakhlin This is my paper

classification 💻 cs.LG math.STstat.MLstat.TH

keywords complexityfunctionrademacherclassinftyalongboundedcomposed

0 comments

read the original abstract

We show that the Rademacher complexity of any $\mathbb{R}^{K}$-valued function class composed with an $\ell_{\infty}$-Lipschitz function is bounded by the maximum Rademacher complexity of the restriction of the function class along each coordinate, times a factor of $\tilde{O}(\sqrt{K})$.

This paper has not been read by Pith yet.

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Infinite-Dimensional Spherical Kernel ridge Regression
stat.ME 2026-05 unverdicted novelty 6.0

An intrinsic spherical kernel ridge regression framework is introduced for non-linear responses on spheres, reducing infinite-dimensional estimation to finite via the representer theorem with convergence rates shown.