Skip to main content
1 of 2

Bound on covering number for overparametrized manifold

I am trying to wrap my head around the following problem:

I have $p$ real parameters $\boldsymbol{\theta} \in \Theta = [0, 2\pi)^p$ that parametrize functions $f(\boldsymbol{\theta}) \in f(\Theta)$ via a mapping that is Lipschitz in the following sense: $$ \lVert f(\boldsymbol{\theta}) - f(\boldsymbol{\theta}')\rVert_{\infty} \leq L \lVert \boldsymbol{\theta} - \boldsymbol{\theta}'\rVert_1. $$ I now want to compute the covering number of the manifold $f(\Theta)$, which is equivalent to counting how many elements an $\epsilon$-net for $f(\Theta)$ has. I can get an upper bound by first constructing an $\epsilon$-netfor the set of parameters $\Theta$ that has $$ \mathcal{N}(\Theta, \lVert \cdot \rVert_1, \epsilon) \sim \left(\frac{2\pi}{\epsilon}\right)^p $$ elements, and then can use this together with the Lipschitz property to infer that the maximal number of points to construct an $\epsilon$-net for the set of parametrized functions, $f(\Theta)$, is upper bounded as $$ \mathcal{N}(f(\Theta), \lVert \cdot \rVert_{\infty}, \epsilon) \lesssim \left(\frac{2\pi L}{\epsilon}\right)^p. $$

But I also have the information that the dimension of the manifold $f(\Theta)$ is bounded independently of $p$, say $\dim(f(\Theta)) \leq q$. Can I use this knowledge to improve my bound on the covering number for $f(\Theta)$?

I would hope for something along the lines of $$ \mathcal{N}(f(\Theta), \lVert \cdot \rVert_{\infty}, \epsilon) \overset{?}{\lesssim} \left(\frac{2\pi L}{\epsilon}\right)^{\min(p, q)}, $$ eventually with some sort of pre-factor, but I do not know how to prove this. Of the things I was thinking about to solve this, the following is the only one I'm left with that seems sensible to me:

Effectively, we can always find $q$ independent parameters to parametrize $f(\Theta)$ given the bound on the dimension. Can I then use this information to pick a subset of the parameters that I denote $\boldsymbol{\vartheta}$ (e.g. the first $q$ parameters) and make the rest of the parameters a function of these parameters via the implicit function theorem, i.e. $\boldsymbol{\theta} = \boldsymbol{\theta}(\boldsymbol{\vartheta})\colon [0,2\pi)^q \to [0,2\pi)^p$. If I could show that this mapping is $l$-Lipschitz, i.e. $$ \lVert \boldsymbol{\theta}(\boldsymbol{\vartheta})-\boldsymbol{\theta}(\boldsymbol{\vartheta}')\rVert_1 \leq l \lVert \boldsymbol{\vartheta} - \boldsymbol{\vartheta}'\rVert_1, $$ I could use this together with the formula for the generalized arc length (see here) to upper bound the volume of the set of parameters $\boldsymbol{\theta}([0,2\pi)^q) \subseteq \Theta$ $$ \operatorname{Vol}(\boldsymbol{\theta}([0,2\pi)^q)) \leq \sqrt{1+l^2}(2\pi)^q, $$ which should allow me to relate a covering of $[0,2\pi)^q$ to a covering of $f(\Theta)$.