Covering number for a set of functions

187 Views Asked by At

Let $U_d$ be the unit ball in $\mathbb{R}^d$ and $f_{S,c}(x) \equiv \|x-c\|^2 \textbf{1}(x \in S)$ for $c \in \mathbb{R}^d$ fixed with $\|c\| \leq 1$

$S \in \mathcal{S}_n \equiv\{$sets which may be written as the the intersection of $n$ closed half spaces$\}$

I want to find a bound on the $\epsilon$ covering number of $\mathcal{F} \equiv \{f_{S,c} : S \in \mathcal{S}_n, \|c \| \leq 1 \}$ if there even is one.


My attempt:

I know that for a Lipschitz family with uniform constant $K$, we could subdivide the input space into $(2Kd/\epsilon)^d$ "blocks" each of length $\epsilon/2Kd$ in the $i$th input dimension so that on each block, any function in the family varies by at most $\epsilon/2$ by the Lipschitz condition.

If we then subdivide the range into intervals of length $\epsilon/2$ (there would be $4/\epsilon$ of these in this case. If we consider $\mathcal{G} \equiv$ piecewise constant functions with jumps at all of the subdivisions of the input space with values at only the subdivisions of the range, the set of balls of radius $\epsilon$ with respect to the $\| \cdot \|_\infty$ norm centered at functions in $\mathcal{G}$ contains all $f \in$ the Lipschitz family and thus the covering number is $\leq |\mathcal{G}|$

$|\mathcal{G}| \leq (2Kd/\epsilon)^{4d/ \epsilon}$ and thus we have our bound for the covering number of the Lipschitz family with uniform constant $K$.

This does not work for $\mathcal{F}$ since this is not a Lipschitz family (due to the jumps at the boundary of $S$ for any $S \in \mathcal{S}$ whose boundary intersects $U_d$. I'm very confused. Perhaps there is no bound on the covering number. Any help would be massively appreciated!