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

enter image description hereenter image description here


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.