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

Question

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

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