4

Let $\mathcal F := \{f_\theta\mid\theta\in\mathbb R^p\}$ be a parametric family of real-valued, continuous functions defined on $[0,1]^d $, such that for all $\theta\in\mathbb R^p$, $$|f_\theta(x)| \le F<\infty \,\,\forall x\in[0,1]^d, $$

for some $F>0$. Now let $\rho$ be a probability distribution on $[0,1]^d\times \{-1,1\} $, $(x_i,y_i)_{i=1}^\infty$ a sequence of i.i.d. random variables with distribution $\rho$ and define for all $n\ge 1$ : $$\hat R_n(\theta):=\frac1n\sum_{i=1}^n (f_\theta(x_i)-y_i)^2 $$ and the corresponding minimum-norm solution set : $$\hat\Theta_n := \arg\min_{\theta\in\arg\min\hat R_n}\|\theta\|_2$$

Lastly, let $B$ be the supremum of all of these vectors' magnitude : $$B:=\sup_{n\ge 1}\ \{\|\theta\|_2\mid \theta\in\hat\Theta_n\} $$

Question : is B finite ? If so, how to prove it ? If not, what assumptions would be sufficient to ensure its finiteness ? (Bonus : can it be upper bounded by a non-random quantity ?)


My idea was to proceed by contradiction : if we assume that $B=\infty$ then we can construct (passing to a subsequence if necessary) a sequence $\hat\theta_1,\hat\theta_2,\ldots $ of minimizers of respectively $\hat R_1,\hat R_2,\ldots $ with norm going to $\infty$.

However, if we assume that the Rademacher complexity of $\mathcal F$ vanishes as $n\to\infty$, we get by the uniform law of large numbers that $(\hat R_n)$ (as a sequence of real-valued functions defined on $\mathbb R^p$) converges uniformly to $R:\theta\mapsto \mathbb E_{(x,y)\sim\rho}\left[f_\theta(x)-y)^2\right]$.

I'm not sure of how to go on from here. I thought I could adapt the argument given here, to find a sequence of minimizers of $\hat R_n$ which converges to a minimizer of $R$, but it doesn't seem to work ($\mathbb R^p$ is not compact)...

I'll be grateful for any help.

0 Answers0