Consider a function family $$\ell(x)=\max_{1\leq k\leq K} a_k^\top x + b_k,$$ where $a_k,b_k \in \mathbb{R}^d$ are bounded in the sense of some norm and $K\geq 2$. What is the best upper bound on the capacity (e.g., Rademacher complexity, etc) of such a family, in terms of dependence on dimension $d$, number of pieces $K$ and sample size $n$?

  • This is not exactly that, as your function is real-valued (no $\mathrm{sign}()$ taken), but without this distinction you'd get the union of $K$ bounded-weight halfspaces. That may be something to look into. – Clement C. Aug 9 at 17:08
up vote 3 down vote accepted

Since we're talking about real-valued functions, rather than VC-dimension, you probably want the fat-shattering one. The $\gamma$-fat-shattering of linear functions with $\ell_2$ norm bounded by $B$ is of order $(B/\gamma)^2$. For a $k$-fold maximum of such functions, the bound grows as $O((B/\gamma)^2k\log k)$, as shown here: https://www.cs.bgu.ac.il/~karyeh/rademacher-max-hyperplane.pdf

This translates immediately into a Rademacher bound, given therein.

The $\log(k)$ factor cannot be removed in this case, as recently shown in https://arxiv.org/abs/1807.07924

Edit: I had originally neglected to mention that the fat-shattering bound of $(B/\gamma)^2$ implicitly assumes that the instance space is confined to the Euclidean ($\ell_2$) unit ball. More generally, if the linear functions have $\ell_p$ norm at most $B$ and the data is confined to an $\ell_q$ ball of radius at most $R$, the bound becomes $BR/\gamma^2$, where $1/p+1/q=1$, $p,q\ge1$. This readily follows from the classic Rademacher analysis of "fat" hyperplanes: in the step where Cauchy-Schwarz is invoked, invoke instead Hölder.

  • See related mathoverflow question mathoverflow.net/questions/266457/… – Aryeh Aug 9 at 22:05
  • Thanks! What if we change the norm on $w$ in your notes? – O. Richard Aug 10 at 2:00
  • Change the norm to what? You need some bound on the norm. – Aryeh Aug 10 at 2:05
  • Instead of the 2-norm, consider 1-norm or inf-norm. – O. Richard Aug 10 at 2:56
  • Addressed in the edit. – Aryeh Aug 10 at 13:04

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.