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$?

  • $\begingroup$ 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. $\endgroup$
    – Clement C.
    Commented Aug 9, 2018 at 17:08

1 Answer 1


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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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