<p>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:
<a href="https://www.cs.bgu.ac.il/~karyeh/rademacher-max-hyperplane.pdf" rel="nofollow noreferrer">https://www.cs.bgu.ac.il/~karyeh/rademacher-max-hyperplane.pdf</a></p>

<p>This translates immediately into a Rademacher bound, given therein.</p>

<p>The $\log(k)$ factor cannot be removed in this case, as recently shown in
<a href="https://arxiv.org/abs/1807.07924" rel="nofollow noreferrer">https://arxiv.org/abs/1807.07924</a></p>

<p>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.</p>

CC BY-SA 4.0
2018-08-09T22:05:54.840Z
See related mathoverflow question https://mathoverflow.net/questions/266457/rademacher-average-involving-minima
Aryeh
CC BY-SA 4.0
2018-08-10T02:00:43.947Z
Thanks! What if we change the norm on $w$ in your notes?
O. Richard
CC BY-SA 4.0
2018-08-10T02:05:39.997Z
Change the norm to what? You need some bound on the norm.
Aryeh
CC BY-SA 4.0
2018-08-10T02:56:51.390Z
Instead of the 2-norm, consider 1-norm or inf-norm.
O. Richard
CC BY-SA 4.0
2018-08-10T13:04:29.370Z
Addressed in the edit.
Aryeh
CC BY-SA 4.0
2018-08-09T20:54:48.877Z
2018-08-10T13:04:00.813Z
2018-08-10T13:04:00.813Z
Aryeh
<p>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$?</p>

CC BY-SA 4.0
2018-08-09T17:08:10.313Z
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.
<reference-request><lg.learning><vc-dimension>
Rademacher complexity for piecewise-linear convex function
O. Richard
# Rademacher complexity for piecewise-linear convex function

(Asked by: username_0 on 2018-08-09)

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

**Tags:** reference-request, lg.learning, vc-dimension

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2018-08-09. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_2**: See related mathoverflow question https://mathoverflow.net/questions/266457/rademacher-average-involving-minima  
> **username_0**: Thanks! What if we change the norm on $w$ in your notes?  
> **username_2**: Change the norm to what? You need some bound on the norm.  
> **username_0**: Instead of the 2-norm, consider 1-norm or inf-norm.  
> **username_2**: Addressed in the edit.  

---

