# Rademacher complexity for piecewise-linear convex function

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 '18 at 17:08

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 '18 at 22:05
• Thanks! What if we change the norm on $w$ in your notes? – O. Richard Aug 10 '18 at 2:00
• Change the norm to what? You need some bound on the norm. – Aryeh Aug 10 '18 at 2:05
• Instead of the 2-norm, consider 1-norm or inf-norm. – O. Richard Aug 10 '18 at 2:56
• Addressed in the edit. – Aryeh Aug 10 '18 at 13:04