<p>I will address the &quot;VC&quot; part. Let <span class="math-container">$F_{d,k}$</span> be the collection of all <span class="math-container">$k$</span>-piecewise linear functions from <span class="math-container">$\mathbb{R}^d$</span> to <span class="math-container">$\mathbb{R}$</span>. Let
<span class="math-container">$H_{d,k}=\mathrm{sign}(F_{d,k})$</span> be this class thresholded at zero
<span class="math-container">$$
H_{d,k}=\{h=\mathrm{sign}(f) : f\in F_{d,k}\}.
$$</span>
I claim that each <span class="math-container">$h\in H_{d,k}$</span> can be computed by a Boolean circuit realized by a directed acyclic graph with <span class="math-container">$k$</span> internal nodes, where each node is labeled with an element of <span class="math-container">$H_{d,1}$</span>. This is described in detail in the Kearns-Vazirani book, Section 3.7
<a href="https://mitpress.mit.edu/books/introduction-computational-learning-theory" rel="nofollow noreferrer">https://mitpress.mit.edu/books/introduction-computational-learning-theory</a>
; here is the accompanying figure:</p>
<p><a href="https://i.sstatic.net/n202D.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/n202D.png" alt="enter image description here" /></a></p>
<p>Theorem 3.6 therein states that <span class="math-container">$\mathrm{VC}(H_{d,k})\le 2k\log(ek)\mathrm{VC}(H_{d,1})$</span>. Since <span class="math-container">$\mathrm{VC}(H_{d,1})=d+1$</span>, this yields an estimate of
<span class="math-container">$O(kd\log k)$</span> -- worse by a factor of <span class="math-container">$\log k$</span> than yours. Intuitively, one might imagine that this <span class="math-container">$\log k$</span> factor accounts for the fact that the break points are not fixed.</p>
<p>As for the fat-shattering dimension of <span class="math-container">$F_{d,k}$</span>, that is indeed an excellent question, one that I shall have to think about.</p>

CC BY-SA 4.0
2022-07-15T09:45:45.270Z
Very interesting! I guess the issue of generalising the proof to fat shattering dimension is that two states are no longer enough, as you need a state for points that lie in the margin $\gamma$.
Nick Bishop
CC BY-SA 4.0
2022-07-15T11:27:38.040Z
I can express a $k$-piecewise linear function as a min-max circuit (i.e., a layered DAG as in the figure) where each "gate" is either a min or a max, and the internal nodes are linear functions. But there is no analogous fat-dim result. The max-only case was non-trivial enough -- I devoted a whole paper to it!
https://arxiv.org/abs/2110.04763

If this is sufficiently interesting, I'll be happy to work on it. Is it?
Aryeh
CC BY-SA 4.0
2022-07-15T13:38:45.820Z
I have updated the question with some discussion as to its motivation.
Nick Bishop
CC BY-SA 4.0
2022-07-15T13:56:58.307Z
Interesting, thanks!
Aryeh
CC BY-SA 4.0
2022-07-14T20:53:30.520Z
2022-07-14T20:53:30.520Z
Aryeh
<p>I am trying to establish a bound on the VC dimension of piecewise linear continuous functions with <span class="math-container">$k$</span> pieces. I am aware of an <a href="https://cstheory.stackexchange.com/questions/17477/vc-dimension-of-intersection-of-half-spaces">earlier question</a> which tackles this problem in the case of <em>convex</em> piecewise linear functions. However, the fundamental argument seems to rely on the fact that the concept class induced by a convex piecewise linear function is given by the intersection of the concepts induced by its component hyperplanes - this doesn't apply in the general case.</p>
<p>When the <span class="math-container">$k$</span> breakpoints are fixed in place it seems obvious that the VC dimension would be <span class="math-container">$(k+1)(d+1)$</span>. However, when the breakpoints are free to vary I am not sure how to establish a bound.</p>
<p>EDIT: I thought I would express why I am interested in such a result. I am studying the following learning setting, known as a Stackelberg prediction game.</p>
<p>As is standard, data is sampled from some underlying distribution <span class="math-container">$\mathcal{D}$</span>. However, instead of sampling from the distribution directly the learner receives samples from an intermediary agent. Additionally each input example sampled comes with two labels <span class="math-container">$y$</span> and <span class="math-container">$z$</span>.The label <span class="math-container">$y$</span> represents what the learner would like to predict, whilst the label <span class="math-container">$z$</span> represents what prediction the intermediary prefers.</p>
<p>At test time, the intermediary may modify input examples, with full knowledge of the predictor chosen by the learner, with the aim of getting a better prediction. More formally, instead of submitting an input example <span class="math-container">$\mathbf{x}$</span>, the agent submits <span class="math-container">$\mathbf{x}^{\star}$</span>:</p>
<p><span class="math-container">$$
\mathbf{x}^{\star} \in \arg\min_{\tilde{\mathbf{x}}} \ell_{+1}(h(\tilde{\mathbf{x}}), z) + \lambda c(\mathbf{x}, \tilde{\mathbf{x}})
$$</span></p>
<p>where <span class="math-container">$\ell_{+1}$</span> is the loss function of the intermediary and <span class="math-container">$c$</span> is a cost function which characterises the cost incurred by the intermediary for changing <span class="math-container">$\mathbf{x}$</span> to <span class="math-container">$\tilde{\mathbf{x}}$</span>.</p>
<p>Meanwhile the learner wants to minimise their own risk with respect to the labels <span class="math-container">$y$</span> given that the intermediary will modify incoming input examples optimally:
<span class="math-container">$$
\arg\min_{h \in \mathcal{H}} \mathbb{E}[\ell_{-}(h(x^{\star}), y)]
$$</span>
where <span class="math-container">$\ell_{-}$</span> is the loss function of the learner. Now assume that <span class="math-container">$\mathcal{H}$</span> is the class of linear predictors, <span class="math-container">$\ell_{-}$</span> and <span class="math-container">$\ell_{+}$</span> are the square loss, and that <span class="math-container">$c(x, \tilde{x}) = \|x - \tilde{x}\|_{1}$</span>. Then it can be shown that</p>
<p><span class="math-container">$$
\mathbf{x}^{\star} = 
\begin{cases}
\mathbf{x} &amp; \text{if } \mathbf{w} = 0 \text{ or } \|\mathbf{w}\|_{\infty}|z - \mathbf{w}^{\top}\mathbf{x}| \leq \gamma/2 \\
\mathbf{x} + \|\mathbf{w}\|_{\infty}(z - \mathbf{w}^{\top}\mathbf{x}) - \frac{\gamma}{2\|\mathbf{w}\|_{\infty}} &amp; \text{if } \|\mathbf{w}\|_{\infty}(z - \mathbf{w}^{\top}\mathbf{x}) &gt; \gamma/2\\
\mathbf{x} + \|\mathbf{w}\|_{\infty}(z - \mathbf{w}^{\top}\mathbf{x}) + \frac{\gamma}{2\|\mathbf{w}\|_{\infty}} &amp; \text{if } \|\mathbf{w}\|_{\infty}(z - \mathbf{w}^{\top}\mathbf{x}) &lt; \gamma /2
\end{cases}
$$</span></p>
<p>Thus given a sample <span class="math-container">$(x, y, z)$</span>, the actual prediction made by <span class="math-container">$\mathbf{w} \in \mathbb{R}^{n}$</span> after modification is:</p>
<p><span class="math-container">$$
h_{\mathbf{w}}(\mathbf{x}, z) = 
\begin{cases}
\mathbf{w}^{\top}\mathbf{x} &amp; \text{if } \mathbf{w} = 0 \text{ or } \|\mathbf{w}\|_{\infty}|z_{i} - \mathbf{w}^{\top}\mathbf{x}| \leq \gamma/2 \\
z - \frac{\gamma}{2\|\mathbf{w}\|_{\infty}} &amp; \text{if } \|\mathbf{w}\|_{\infty}(z - \mathbf{w}^{\top}\mathbf{x}) &gt; \gamma/2\\
z + \frac{\gamma}{2\|\mathbf{w}\|_{\infty}} &amp; \text{if } \|\mathbf{w}\|_{\infty}(z - \mathbf{w}^{\top}\mathbf{x}) &lt; -\gamma/2
\end{cases}
$$</span></p>
<p>In other words, minimising the risk is equivalent to minimising the risk in a standard risk minimisation problem in which hypothesis are piecewise linear functions on <span class="math-container">$(\mathbf{x}, z)$</span> with three components.</p>
<p>Now assume that I have a training dataset <span class="math-container">$S = \{(x_{i}, y_{i}, z_{i})\}^{m}_{i=1]}$</span> of uncorrupted data points (for example, maybe I got these by going through some verification process). Then I can perform empirical risk minimisation:
<span class="math-container">$$
\arg\min_{h_{\mathbf{w}}} \sum_{i=1}^{m}\ell_{-1}(h_{\mathbf{w}}(\mathbf{x}_{i}, z_{i}), y_{i})
$$</span></p>
<p>I want to know two things about this ERM procedure:</p>
<ol>
<li>Is this optimisation tractable?</li>
<li>Does the resulting hypothesis found generalise well?</li>
</ol>
<p>For question 2, note that <span class="math-container">$h_{\mathbf{w}}$</span> is a piecewise linear function, therefore if the hypothesis class of piecewise continuous linear functions with a fixed number of components has bounded complexity, then one would get generalisation guarantees for the ERM procedure above.</p>
<p>This is a rather brute force approach, which avoids specific details regarding the functions being optimised over, but may be a good starting point.</p>

<machine-learning><lg.learning><vc-dimension><pac-learning>
Fat Shattering / VC dimension / Statistical Complexity of piecewise linear functions
Nick Bishop
# Fat Shattering / VC dimension / Statistical Complexity of piecewise linear functions

(Asked by: username_0 on 2022-07-14)

I am trying to establish a bound on the VC dimension of piecewise linear continuous functions with $k$ pieces. I am aware of an [earlier question](https://cstheory.stackexchange.com/questions/17477/vc-dimension-of-intersection-of-half-spaces) which tackles this problem in the case of *convex* piecewise linear functions. However, the fundamental argument seems to rely on the fact that the concept class induced by a convex piecewise linear function is given by the intersection of the concepts induced by its component hyperplanes - this doesn't apply in the general case.

When the $k$ breakpoints are fixed in place it seems obvious that the VC dimension would be $(k+1)(d+1)$. However, when the breakpoints are free to vary I am not sure how to establish a bound.

EDIT: I thought I would express why I am interested in such a result. I am studying the following learning setting, known as a Stackelberg prediction game.

As is standard, data is sampled from some underlying distribution $\mathcal{D}$. However, instead of sampling from the distribution directly the learner receives samples from an intermediary agent. Additionally each input example sampled comes with two labels $y$ and $z$.The label $y$ represents what the learner would like to predict, whilst the label $z$ represents what prediction the intermediary prefers.

At test time, the intermediary may modify input examples, with full knowledge of the predictor chosen by the learner, with the aim of getting a better prediction. More formally, instead of submitting an input example $\mathbf{x}$, the agent submits $\mathbf{x}^{\star}$:

$$
\mathbf{x}^{\star} \in \arg\min\_{\tilde{\mathbf{x}}} \ell\_{+1}(h(\tilde{\mathbf{x}}), z) + \lambda c(\mathbf{x}, \tilde{\mathbf{x}})
$$

where $\ell\_{+1}$ is the loss function of the intermediary and $c$ is a cost function which characterises the cost incurred by the intermediary for changing $\mathbf{x}$ to $\tilde{\mathbf{x}}$.

Meanwhile the learner wants to minimise their own risk with respect to the labels $y$ given that the intermediary will modify incoming input examples optimally:
$$
\arg\min\_{h \in \mathcal{H}} \mathbb{E}[\ell\_{-}(h(x^{\star}), y)]
$$
where $\ell\_{-}$ is the loss function of the learner. Now assume that $\mathcal{H}$ is the class of linear predictors, $\ell\_{-}$ and $\ell\_{+}$ are the square loss, and that $c(x, \tilde{x}) = \|x - \tilde{x}\|\_{1}$. Then it can be shown that

$$
\mathbf{x}^{\star} =
\begin{cases}
\mathbf{x} & \text{if } \mathbf{w} = 0 \text{ or } \|\mathbf{w}\|\_{\infty}|z - \mathbf{w}^{\top}\mathbf{x}| \leq \gamma/2 \\
\mathbf{x} + \|\mathbf{w}\|\_{\infty}(z - \mathbf{w}^{\top}\mathbf{x}) - \frac{\gamma}{2\|\mathbf{w}\|\_{\infty}} & \text{if } \|\mathbf{w}\|\_{\infty}(z - \mathbf{w}^{\top}\mathbf{x}) > \gamma/2\\
\mathbf{x} + \|\mathbf{w}\|\_{\infty}(z - \mathbf{w}^{\top}\mathbf{x}) + \frac{\gamma}{2\|\mathbf{w}\|\_{\infty}} & \text{if } \|\mathbf{w}\|\_{\infty}(z - \mathbf{w}^{\top}\mathbf{x}) < \gamma /2
\end{cases}
$$

Thus given a sample $(x, y, z)$, the actual prediction made by $\mathbf{w} \in \mathbb{R}^{n}$ after modification is:

$$
h\_{\mathbf{w}}(\mathbf{x}, z) =
\begin{cases}
\mathbf{w}^{\top}\mathbf{x} & \text{if } \mathbf{w} = 0 \text{ or } \|\mathbf{w}\|\_{\infty}|z\_{i} - \mathbf{w}^{\top}\mathbf{x}| \leq \gamma/2 \\
z - \frac{\gamma}{2\|\mathbf{w}\|\_{\infty}} & \text{if } \|\mathbf{w}\|\_{\infty}(z - \mathbf{w}^{\top}\mathbf{x}) > \gamma/2\\
z + \frac{\gamma}{2\|\mathbf{w}\|\_{\infty}} & \text{if } \|\mathbf{w}\|\_{\infty}(z - \mathbf{w}^{\top}\mathbf{x}) < -\gamma/2
\end{cases}
$$

In other words, minimising the risk is equivalent to minimising the risk in a standard risk minimisation problem in which hypothesis are piecewise linear functions on $(\mathbf{x}, z)$ with three components.

Now assume that I have a training dataset $S = \{(x\_{i}, y\_{i}, z\_{i})\}^{m}\_{i=1]}$ of uncorrupted data points (for example, maybe I got these by going through some verification process). Then I can perform empirical risk minimisation:
$$
\arg\min\_{h\_{\mathbf{w}}} \sum\_{i=1}^{m}\ell\_{-1}(h\_{\mathbf{w}}(\mathbf{x}\_{i}, z\_{i}), y\_{i})
$$

I want to know two things about this ERM procedure:

1. Is this optimisation tractable?
2. Does the resulting hypothesis found generalise well?

For question 2, note that $h\_{\mathbf{w}}$ is a piecewise linear function, therefore if the hypothesis class of piecewise continuous linear functions with a fixed number of components has bounded complexity, then one would get generalisation guarantees for the ERM procedure above.

This is a rather brute force approach, which avoids specific details regarding the functions being optimised over, but may be a good starting point.

**Tags:** machine-learning, lg.learning, vc-dimension, pac-learning


---

## 1 answers

### Answer by username_1 on 2022-07-14. Score: 1 | Accepted answer

I will address the "VC" part. Let $F\_{d,k}$ be the collection of all $k$-piecewise linear functions from $\mathbb{R}^d$ to $\mathbb{R}$. Let
$H\_{d,k}=\mathrm{sign}(F\_{d,k})$ be this class thresholded at zero
$$
H\_{d,k}=\{h=\mathrm{sign}(f) : f\in F\_{d,k}\}.
$$
I claim that each $h\in H\_{d,k}$ can be computed by a Boolean circuit realized by a directed acyclic graph with $k$ internal nodes, where each node is labeled with an element of $H\_{d,1}$. This is described in detail in the Kearns-Vazirani book, Section 3.7
<https://mitpress.mit.edu/books/introduction-computational-learning-theory>
; here is the accompanying figure:

[![enter image description here](https://i.sstatic.net/n202D.png)](https://i.sstatic.net/n202D.png)

Theorem 3.6 therein states that $\mathrm{VC}(H\_{d,k})\le 2k\log(ek)\mathrm{VC}(H\_{d,1})$. Since $\mathrm{VC}(H\_{d,1})=d+1$, this yields an estimate of
$O(kd\log k)$ -- worse by a factor of $\log k$ than yours. Intuitively, one might imagine that this $\log k$ factor accounts for the fact that the break points are not fixed.

As for the fat-shattering dimension of $F\_{d,k}$, that is indeed an excellent question, one that I shall have to think about.

> **Comments:**
> **username_0**: Very interesting! I guess the issue of generalising the proof to fat shattering dimension is that two states are no longer enough, as you need a state for points that lie in the margin $\gamma$.  
> **username_1**: I can express a $k$-piecewise linear function as a min-max circuit (i.e., a layered DAG as in the figure) where each "gate" is either a min or a max, and the internal nodes are linear functions. But there is no analogous fat-dim result. The max-only case was non-trivial enough -- I devoted a whole paper to it! https://arxiv.org/abs/2110.04763  If this is sufficiently interesting, I'll be happy to work on it. Is it?  
> **username_0**: I have updated the question with some discussion as to its motivation.  
> **username_1**: Interesting, thanks!  

---

