# Concentration inequality for norm of solution to nonlinear least-squares problem

Define the piecewise-linear function $$\psi(t):=\max(t,0)$$ for all $$t \in \mathbb R$$.

• Let $$d,n,k \to \infty$$ at the same rate (i.e $$n \asymp k \asymp d$$).
• Let $$y_1,\ldots,y_n \in \{-1,1\}$$ uniformly iid.
• Let $$x_1,\ldots,x_n$$ be sampled iid uniformly on the $$(d-1)$$-dimensional unit-sphere, independently of the $$y_i$$'s.
• Let $$w_1,\ldots,w_k$$ be sampled iid from $$\mathcal N(0,(1/d)I_d)$$, and independently of the $$x_i$$'s and $$y_i$$'s.
• Let $$Z$$ be the $$n \times k$$ matrix with $$i$$th row $$z_{i,j} := \psi(x_i^\top w_j)$$ for all $$(i,j) \in [n] \times[k]$$.
• Let $$\overline{z} := Z^\top y = \sum_{i=1} y_i z_i \in \mathbb R^k$$.
• Let $$v \in \mathbb R^k$$ be the solution to the linear system $$Z v = y$$.

Note that $$Z$$, $$\overline{z}$$, and $$v$$ are all random.

Question. What are good concentration inequalities for $$\|\overline{z}\|_2$$ and $$\|v\|_2$$ ?

Note. I'm really only interested in high-probability lower-bounds for $$\|v\|_2$$. My interest in $$\|\overline{z}\|_2$$ is due to the fact that $$\overline{z}^\top v = \sum_{i=1}^n y_i z_i^\top v = \sum_{i=1} y_i^2 = n$$, and so Cauchy-Schwarz gives $$\|v\| \ge \frac{n}{\|\overline{z}\|}. \tag{*}$$

Thus, an upper-bound for $$\|\overline{z}\|$$ would give a (presumably crude) lower-bound for $$\|v\|$$.

## Empirical observations

I've run some experiments, and it seems $$\|\overline{z}\| = \Theta(\sqrt{d})$$ and $$\|v\| = \Theta(\sqrt{d})$$ w.p $$1-o(1)$$.

It turns out it is possible to prove a (very very) slightly weaker lower-bound, namely

$$\|v\| = \Omega\left(\left(\dfrac{d}{k}\right)^{1/2}n^{1/2-o(1)}\right) \text{ w.p }1-o(1).$$

Moreover, this bound is non-asymptotic, and we only need to asume $$d \le n$$ (nothing else).

Note that $$\|\overline{z}\| = \max_{\|u\| = 1}\overline{z}^\top u$$. Let $$\mathcal C_\epsilon = \{u_1,\ldots,u_{N_\epsilon}\} \subseteq \mathbb R^k$$ be an $$\epsilon$$-cover for the $$(k-1)$$-dimensional unit-sphere $$\mathbb S_{k-1}$$, with $$N_\epsilon \le (1/\epsilon)^k$$. For any $$u \in \mathbb S_{k-1}$$, there exists $$u_\epsilon \in \mathcal C_\epsilon$$ such that $$\|u-u_\epsilon\| \le \epsilon$$. A simple covering argument gives

$$\|\overline{z}\| = \sup_{\|u\| = 1}\overline{z}^\top u \le \sup_{\|u\| = 1} \overline{z}^\top u_\epsilon + \epsilon \|\overline{z}\| \le \sup_{u \in \mathcal C_\epsilon}\overline{z}^\top u + \epsilon\|\overline{z}\|.$$

Taking $$\epsilon=1/2$$, we obtain

$$\|\overline{z}\| \le 2\sup_{u \in \mathcal C_\epsilon}\overline{z}^\top u. \tag{1}$$

Now, fix a unit-vector $$u$$ in $$\mathbb R^k$$, and consider set $$f(W):=\overline{z}^\top u = \sum_{i=1}^n y_i\sum_{j=1}^k \psi(x_i^\top w_j)u_j$$. It is easy to see that $$f:\mathbb R^{d^k} \to \mathbb R$$ is $$\mathcal C^\infty$$ a.e, with gradient given by

$$\partial_{w_{j,l}} f(W) = u_j \sum_{i=1}^n y_ix_{i,l}\psi'(x_i^\top w_j) = u_j \sum_{i=1}^n y_ix_{i,l}1[\![x_i^\top w_j > 0]\!]\;\forall (j,l) \in [k] \times [d],$$ and hessian which is zero a.e. Noting that the distribution $$\mathcal N(0,1/d)$$ of the $$w_j$$'s satisfies a Logarithmic Sobolev Inequality with constant $$d^{-1/2}$$, Adamczak-Wolf theory for concentration of non-Lipschitz functions (more precisely, Theorem 1.2 with $$D=p=2$$) gives,

$$\begin{split} \mathbb P(\big||f(W)| - |\mathbb E[f(W)]|\big| \ge t) &\le \mathbb P(|f(W) - \mathbb E[f(W)]| \ge t)\\ &\le 2 \exp(-Cdt^2/\|\mathbb E[\nabla f(W)]\|^2_{Fro}), \end{split} \tag{2}$$

for an absolute constant $$C>0$$. Now, one computes $$\begin{split} \|\mathbb E[\nabla f(W)]\|^2_{Fro} &= \sum_{j=1}^k\sum_{l=1}^d (u_j \sum_{i=1}^n y_ix_{i,l}\mathbb P(x_i^\top w_j > 0))^2\\ &= \frac{1}{4}\sum_{j=1}^ku_j^2\sum_{l=1}^d(\sum_{i=1}^n y_i x_{i,l})^2 = \frac{1}{4}\|X^\top y\|^2\text{ since }\|u\| = 1. \end{split}$$

Thus, except for an event $$\mathcal E_n$$ of probability $$e^{-\Omega(d)}$$, we have

$$\|\mathbb E[\nabla f(W)]\|^2_{Fro} =\frac{1}{4}\|X^\top y\|^2 = \mathcal O(n). \tag{3}$$

On the other hand, one computes

$$\begin{split} \mathbb E[f(W)] &= \sum_{i=1}^n y_i \sum_{j=1}^k u_j \mathbb E[\psi(x_i^\top w_j)] = \sum_{i=1}^n y_i \sum_{j=1}^k u_j \dfrac{\|x_i\|}{\sqrt{2\pi d}}\\ &=\dfrac{1}{\sqrt{2\pi d}}\cdot (n^+ - n^-) \cdot \sum_{j=1}^k u_j, \end{split}$$

where $$n^+ := \#\{i \in [n] \mid y_i = 1\}$$ and $$n^- := \#\{i \in [n] \mid y_i = -1\}$$. Thus, $$|\mathbb E[f(W)]| = \dfrac{1}{\sqrt{2\pi d}}\cdot |n^+ - n^-| \cdot \left|\sum_{j=1}^k u_j\right| \le \dfrac{1}{\sqrt{2\pi d}}\cdot |n^+ - n^-| \cdot \sqrt{k}.$$

Using Hoeffding's inequality, it is easy to see that for any $$\tau \in (0,n]$$, it holds that $$|n^+-n^-| \le \sqrt{n\tau}$$ except on an event $$(y_1,\ldots,y_n) \in \mathcal E_n'$$ which occurs with probability $$e^{-\Omega(\tau)}$$. Thus, conditioned on this event, the previous computation gives w.p $$1-e^{-\Omega(\tau)}$$

$$|\mathbb E[f(W)]| = \mathcal O\left(\sqrt{\frac{kn\tau}{d}}\right). \tag{4}$$

Let $$\mathscr F_n := \mathcal E_n \cap \mathcal E'_n$$, an event which occurs with probability at most $$e^{-\Omega(d \land \tau)}$$.

Plugging the estimates (3) and (4) into (2), and taking $$t=\sqrt{kn\tau/d}$$, we obtain that conditioned on $$\mathscr F_n$$ not occurring,

$$\mathbb P(|f(W)| \ge c\sqrt{kn\tau/d}) \le 2\exp(-Ck\tau).$$

Taking $$\tau = \Omega(n^{2\delta})$$ for some small $$\delta>0$$, and conditioning on $$\mathscr F_n$$ not occurring, we have

$$\mathbb P(|f(W)| \ge c\sqrt{kn^{1+2\delta}/d}) \le 2\exp(-C'kn^{2\delta}).$$

Doing a union bound on (1) and combining with (5), we obtain that: if $$d \le n$$, then conditioned on $$\mathscr F_n$$ not occurring, we have $$\mathbb P(\|\overline{z}\| \ge c\sqrt{kn^{1+2\delta}/d}) = e^{-\Omega(kn^{2\delta})}$$. Thus, by virtue of (*),

$$\|v\| = \Omega\left(\left(\frac{d}{k}\right)^{1/2}n^{1/2-\delta}\right) \text{ w.p }1-e^{-\Omega(kn^{2\delta})}.$$

Finally, recalling that $$\mathbb P(\mathscr F_n) \le e^{-\Omega(d \land \tau)} = e^{-\Omega(d \land n^{2\delta})}=o(1)$$, we obtain (+) via Bayes' rule.