Fat Shattering / VC dimension / Statistical Complexity of piecewise linear functions

Question

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

Answer 1

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:

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.