Shallow Learning Tends to Ridgelet Transform

4 Structure of the minimizers: the null-space effect

Section 3 of the paper: the structure of the Gibbs minimizer of the free energy (thm:m1: Gaussian conditional amplitudes whose mean is the regularized ridgelet transform with respect to the learned hidden marginal, kernel ridge regression of the learned kernel), the structure of the stationary points of the noiseless finite-width gradient flow with weight decay (thm:m1prime) and the fixed-feature flow without amplitude regularization, whose endpoint keeps the null-space component of the initialization (prop:no-regularization, cor:necessity-amplitude).

4.1 Gibbs minimizer of the free energy

Let \(s\) be measurable with \(|s|\le C\), \(W_s(\theta )=a\, s(z)\) and \(\rho _s:=\hat\mu _{W_s}\) relative to \(\mu _U\). Then \(\rho _s(\, \mathrm da\, \mathrm dz)=\nu [s](\, \mathrm dz)\, {\mathcal N}(-s(z)/\lambda ,\beta /\lambda )(\, \mathrm da)\) with \(\nu [s](\, \mathrm dz)=Z_*^{-1}e^{s(z)^2/(2\lambda \beta )}\nu _0(\, \mathrm dz)\), \(Z_*=\int e^{s^2/(2\lambda \beta )}\, \mathrm d\nu _0\). (Completing the square, \(a s+\frac\lambda 2a^2=\frac\lambda 2(a+s/\lambda )^2-\frac{s^2}{2\lambda }\).)

Proof ▶

Under the hypotheses of Lemma 218, \(\nu _{\rho _s}=\nu [s]\), i.e. \(\nu _{\rho _s}(\, \mathrm dz)=Z_*^{-1}e^{s(z)^2/(2\lambda \beta )}\nu _0(\, \mathrm dz)\).

Proof ▶

Under the hypotheses of Lemma 218, \(m_{\rho _s}(z)=-s(z)/\lambda \) for \(\nu _{\rho _s}\)-a.e. \(z\).

Proof ▶

Under the hypotheses of Lemma 218, \(F_{\rho _s}(x)=\int _Z\bigl(-s(z)/\lambda \bigr)\varphi _z(x)\, \nu _{\rho _s}(\, \mathrm dz) =(S_{\nu _{\rho _s}}(-s/\lambda ))(x)\) for every \(x\).

Proof ▶
Theorem 222
✓

Let \(s\) be measurable with \(|s|\le C\) and \(c:=C^2/(2\lambda \beta )\). Then \(\nu [s]=w\, \nu _0\) with \(w=Z_*^{-1}e^{s^2/(2\lambda \beta )}\), \(1\le Z_*\le e^c\), hence \(e^{-c}\le w\le e^{c}\) everywhere; in particular \(\nu [s]\) and \(\nu _0\) are mutually absolutely continuous.

Proof ▶

Under the hypotheses of Lemma 218, \(\int |a|\, \mathrm d\rho _s\le \int |s/\lambda |\, \mathrm d\nu _{\rho _s}+\sqrt{2\beta /(\pi \lambda )} \le C/\lambda +\sqrt{2\beta /(\pi \lambda )}\) (the Gaussian bound \({\mathbb E}|X|\le |\mu |+\sigma \sqrt{2/\pi }\) for \(X\sim {\mathcal N}(\mu ,\sigma ^2)\)).

Proof ▶

Step 1: the inner Gaussian moment bound.

Step 2: integrate against the hidden marginal.

Under the hypotheses of Lemma 218, \(\int a^2\, \mathrm d\rho _s=\int (s/\lambda )^2\, \mathrm d\nu _{\rho _s}+\beta /\lambda \) (the Gaussian identity \({\mathbb E}X^2=\mu ^2+\sigma ^2\)).

Proof ▶

Let \(\rho ^*\) be the minimizer of \({\mathcal F}\) on \({\mathcal D}\), \(s^*:=S^*r_{\rho ^*}\) and \(\nu ^*:=\nu _{\rho ^*}\). Then \(\rho ^*(\, \mathrm da\, \mathrm dz)=\nu ^*(\, \mathrm dz)\, {\mathcal N}\bigl(-s^*(z)/\lambda ,\beta /\lambda \bigr)(\, \mathrm da)\).

Proof ▶

With the notation of Theorem 225, \(\nu ^*(\, \mathrm dz)=Z_*^{-1}\exp \bigl(\frac{s^*(z)^2}{2\lambda \beta }\bigr)\nu _0(\, \mathrm dz)\) with \(Z_*=\int _Z\exp \bigl(\frac{s^*(z)^2}{2\lambda \beta }\bigr)\nu _0(\, \mathrm dz){\lt}\infty \); with \(\nu _0=Z_0^{-1}e^{-V/\beta }\, \mathrm dz\) this is \(\nu ^*(\, \mathrm dz)\propto \exp \bigl(\frac{s^*(z)^2}{2\lambda \beta }-\frac{V(z)}\beta \bigr)\, \mathrm dz\).

Proof ▶

The measures \(\nu ^*\) and \(\nu _0\) are mutually absolutely continuous.

Proof ▶

\(m_{\rho ^*}(z)=-s^*(z)/\lambda \) for \(\nu ^*\)-a.e. \(z\) (the conditional law of \(a\) given \(z\) is \({\mathcal N}(-s^*(z)/\lambda ,\beta /\lambda )\)).

Proof ▶

\(\Pi \rho ^*=m_{\rho ^*}\, \nu ^*\) with \(m_{\rho ^*}=-s^*/\lambda \), i.e. \(\Pi \rho ^*(A)=\int _A\bigl(-s^*(z)/\lambda \bigr)\nu ^*(\, \mathrm dz)\) for measurable \(A\subseteq Z\).

Proof ▶

Step 1: transport the set integral through the disintegration.

Step 2: the inner integral is the Gaussian mean ‘−s(z)/λ‘.

In \(L^2(\nu ^*)\), \(m_{\rho ^*}=-\lambda ^{-1}S_{\nu ^*}^*r^*\in \operatorname {ran}S_{\nu ^*}^* \subseteq (\ker S_{\nu ^*})^\perp \).

Proof ▶

With \(K^*:=K_{\nu ^*}\),

\[ r^*=-\lambda (K^*+\lambda )^{-1}f,\qquad F_{\rho ^*}=K^*(K^*+\lambda )^{-1}f,\qquad m_{\rho ^*}=S^*(K^*+\lambda )^{-1}f=R_{\lambda ,\nu ^*}f\ (\nu ^*\text{-a.e.}),\qquad s^*=-\lambda R_{\lambda ,\nu ^*}f . \]

(Proof: \(F_{\rho ^*}=S_{\nu ^*}m_{\rho ^*}=-\lambda ^{-1}K^*r^*\) by Lemma 221 and Theorem 230, so \((K^*+\lambda )r^*=-\lambda f\), and \(K^*+\lambda \) is invertible.)

Proof ▶

Step 1: ‘F_ρ* = S_ν* (−s*/λ) = −λ⁻¹ K* r*‘.

Step 2: ‘(K* + λ) r* = −λ f‘, hence ‘r* = −λ (K* + λ)⁻¹ f‘.

Step 3: ‘F_ρ* = f + r* = K* (K* + λ)⁻¹ f‘.

Step 4: ‘s* = −λ R f‘ and ‘m* = R f‘.

With \(\| f\| :=\| f\| _{L^2(P_X)}\), \(\| r^*\| \le \| f\| \), \(\sup _z|s^*(z)|\le \| f\| \), \(|m_{\rho ^*}|\le \| f\| /\lambda \) and \(\| m_{\rho ^*}\| _{L^2(\nu ^*)}\le \| f\| /(2\sqrt\lambda )\).

Proof ▶

‘‖r*‖ = ‖λ (K* + λ)⁻¹ f‖ ≤ ‖f‖‘ by ‘lem:operators‘ (5).

‘‖m*‖_L²(ν*) = ‖S_ν** (K* + λ)⁻¹ f‖ ≤ ‖f‖/(2√λ)‘ by ‘lem:operators‘ (4).

\(\int |a|\, \mathrm d\rho ^*\le \frac{\| f\| }\lambda +\sqrt{\frac{2\beta }{\pi \lambda }}\) and \(\int a^2\, \mathrm d\rho ^*=\| m_{\rho ^*}\| _{L^2(\nu ^*)}^2+\frac\beta \lambda \le \min \bigl\{ \frac{\| f\| ^2}{\lambda ^2},\frac{\| f\| ^2}{4\lambda }\bigr\} +\frac\beta \lambda \).

Proof ▶

‘‖m*‖² = ∫ (s*/λ)² dν*‘.

The two bounds on ‘‖m*‖‘: ‘‖f‖/λ‘ (sup bound) and ‘‖f‖/(2√λ)‘.

With \(c:=\| f\| ^2/(2\lambda \beta )\), \(\frac{\, \mathrm d\nu ^*}{\, \mathrm d\nu _0}(z)=\frac{Z_0}{Z_*}\exp \bigl(\frac{s^*(z)^2}{2\lambda \beta }\bigr)\) and \(e^{-c}\le \frac{\, \mathrm d\nu ^*}{\, \mathrm d\nu _0}(z)\le e^{c}\) for all \(z\).

Proof ▶
Proof ▶

The self-consistency equation \(s=-\lambda \, S^*(K_{\nu [s]}+\lambda )^{-1}f\), \(\nu [s](\, \mathrm dz)\propto \exp \bigl(\frac{s(z)^2}{2\lambda \beta }\bigr)\nu _0(\, \mathrm dz)\), has exactly one bounded measurable solution, namely \(s^*\): \(s^*\) solves it by Theorems 226 and 231, and any bounded measurable solution \(s\) satisfies \(s=s^*\). (Proof: \(\rho _s:=\hat\mu _{W_s}\) with \(W_s=a\, s(z)\) has \(\nu _{\rho _s}=\nu [s]\), \(F_{\rho _s}=K_{\nu [s]}(K_{\nu [s]}+\lambda )^{-1}f\) and \(S^*r_{\rho _s}=s\), so \(\rho _s\) solves the self-consistency equation of Lemma 210 and is the minimizer.)

Proof ▶

Step 1: ‘F_ρ_s = S_ν[s] R_λ,ν[s] f = K_ν[s] (K_ν[s] + λ)⁻¹ f‘.

Step 2: ‘r_ρ_s = −λ (K_ν[s] + λ)⁻¹ f‘ and ‘S* r_ρ_s = s‘.

Step 3: ‘ρ_s‘ solves the self-consistency equation, hence is the minimizer.

4.2 Stationary points of the gradient flow with weight decay

Theorem 237
✓

Under (A3), for every \(x\in {\mathbb R}^m\) the map \(z=(w,b)\mapsto \varphi _z(x) =\tanh (w^\top x-b)\) is differentiable on \(Z={\mathbb R}^m\times {\mathbb R}\).

Proof ▶

Under (A3) and (A6), \(J_N\in C^1(\Theta ^M)\); in Lean: \(J_N\) is (Fréchet) differentiable on \(\Theta ^M=({\mathbb R}\times Z)^M\) whenever \(z\mapsto \varphi _z(x)\) and \(V\) are differentiable.

Proof ▶

(Gradient of \(J_N\).) Under (A3) and (A6), \(J_N\in C^1(\Theta ^M)\) and, with \(r_i=F_\theta (x_i)-y_i\), \(\partial _{a_\ell }J_N(\theta )=\frac1M\bigl[(S_N^*r)(z_\ell )+\lambda a_\ell \bigr]\), \(\nabla _{z_\ell }J_N(\theta )=\frac1M\bigl[a_\ell \nabla _z(S_N^*r)(z_\ell )+\nabla V(z_\ell )\bigr]\). In Lean the two partial derivatives are packaged as the Fréchet derivative applied to a direction \(v=(v^a_\ell ,v^z_\ell )_\ell \): \(\partial J_N(\theta )v=\frac1M\sum _\ell \bigl([(S_N^*r)(z_\ell )+\lambda a_\ell ]v^a_\ell +[a_\ell \, \partial (S_N^*r)(z_\ell )+\partial V(z_\ell )]v^z_\ell \bigr)\).

Proof ▶

Let \(\theta ^\circ \) be a stationary point of \(J_N\) (\(\nabla J_N(\theta ^\circ )=0\)), \(r^\circ _i:=F_{\theta ^\circ }(x_i)-y_i\) and \(s^\circ :=S_N^*r^\circ \). Then \(a_\ell ^\circ =-s^\circ (z_\ell ^\circ )/\lambda \) for \(\ell =1,\dots ,M\).

Proof ▶

In the setting of 240, with \(\rho _M^\circ =\frac1M\sum _\ell \delta _{\theta _\ell ^\circ }\) and \(\nu _M^\circ =\frac1M\sum _\ell \delta _{z_\ell ^\circ }\), \(\Pi \rho _M^\circ =\frac1M\sum _\ell a_\ell ^\circ \delta _{z_\ell ^\circ } =-\lambda ^{-1}s^\circ \, \nu _M^\circ \); in Lean: for every measurable \(A\subset Z\), \(\Pi \rho _M^\circ (A)=-\lambda ^{-1}\frac1M\sum _{\ell :z_\ell ^\circ \in A} s^\circ (z_\ell ^\circ )\).

Proof ▶

In the setting of 240, each \(z_\ell ^\circ \) is a critical point of \(\Psi ^\circ (z):=\frac{s^\circ (z)^2}{2\lambda }-V(z)\): \(\nabla \Psi ^\circ (z_\ell ^\circ )=\frac{s^\circ (z_\ell ^\circ )\nabla s^\circ (z_\ell ^\circ )}\lambda -\nabla V(z_\ell ^\circ )=0\).

Proof ▶

In the setting of 240, with \(K^\circ :=K_{N,\nu _M^\circ }\), the residual satisfies \((K^\circ +\lambda )r^\circ =-\lambda y\).

Proof ▶

In the setting of 240, with \(K^\circ :=K_{N,\nu _M^\circ }\), \(r^\circ =-\lambda (K^\circ +\lambda )^{-1}y\).

Proof ▶

In the setting of 244, \((F_{\theta ^\circ }(x_i))_i=y+r^\circ =K^\circ (K^\circ +\lambda )^{-1}y\).

Proof ▶

In the setting of 244, \(a_\ell ^\circ =\bigl[S_N^*(K^\circ +\lambda )^{-1}y\bigr](z_\ell ^\circ )\), the value at \(z_\ell ^\circ \) of \(R^{(N)}_{\lambda ,\nu _M^\circ }y:=S_N^*(K^\circ +\lambda )^{-1}y\).

Proof ▶

In the setting of 244, for every \(x\in {\mathcal X}\), \(F_{\theta ^\circ }(x)=\frac1N\sum _{i=1}^Nk_{\nu _M^\circ }(x,x_i)\, \alpha _i^\circ \) with \(\alpha ^\circ :=(K^\circ +\lambda )^{-1}y\) and \(k_{\nu _M^\circ }(x,x'):=\frac1M\sum _\ell \varphi _{z_\ell ^\circ }(x) \varphi _{z_\ell ^\circ }(x')\).

Proof ▶

In the setting of 244, \(L_N(\theta ^\circ )=\frac{\lambda ^2}2\bigl\| (K^\circ +\lambda )^{-1}y\bigr\| _N^2\).

Proof ▶

Along a solution of the gradient flow ??, \(t\mapsto J_N(\theta _t)\) is nonincreasing on \([0,\infty )\), since \(\frac{\, \mathrm d}{\, \mathrm dt}J_N(\theta _t)=-M\| \nabla J_N(\theta _t)\| ^2\le 0\).

Proof ▶

Along a solution of the gradient flow ??, for all \(t\ge 0\), \(\frac\lambda {2M}\sum _\ell a_\ell (t)^2+\frac1M\sum _\ell V(z_\ell (t))\le J_N(\theta _0)\). (With \(V\ge 0\) and (A6) this bounds the trajectory in a compact set.)

Proof ▶

Assume (A3), (A6) and (A7): \(z\mapsto \varphi _z(x)\) and \(V\) are real analytic, \(V\ge 0\) is coercive and \(Z\) is finite dimensional. For every \(\theta _0\in \Theta ^M\) the gradient flow ?? has a unique solution on \([0,\infty )\), which is bounded, has finite length and converges to a stationary point \(\theta ^\circ \): \(\int _0^\infty \| \dot\theta _t\| \, \mathrm dt{\lt}\infty \), \(\lim _{t\to \infty }\theta _t=\theta ^\circ \), \(\nabla J_N(\theta ^\circ )=0\).

Proof ▶

4.3 Without amplitude regularization the null-space component survives

\(S_NS_N^\dagger y=P_{\operatorname {ran}S_N}y\).

Proof ▶

For \(\lambda \ge 0\) and a solution \(\gamma _t\) of ??, \(P_{\ker S_N}\gamma _t=e^{-\lambda t}P_{\ker S_N}\gamma _0\) for all \(t\).

Proof ▶

For \(\lambda =0\) and a solution \(\gamma _t\) of ??, \(P_{\ker S_N}\gamma _t=P_{\ker S_N}\gamma _0\) for all \(t\ge 0\): the null-space component is conserved by the flow.

Proof ▶

For \(\lambda {\gt}0\) and a solution \(\gamma _t\) of ??, \(\gamma _t=\gamma _\lambda +e^{-t(B+\lambda )}(\gamma _0-\gamma _\lambda )\) with \(\gamma _\lambda =(B+\lambda )^{-1}S_N^*y\in (\ker S_N)^\perp \); the endpoint does not depend on \(\gamma _0\).

Proof ▶

For \(\lambda {\gt}0\) and a solution \(\gamma _t\) of ??, \(\| \gamma _t-\gamma _\lambda \| _M\le e^{-\lambda t}\| \gamma _0-\gamma _\lambda \| _M\) for \(t\ge 0\).

Proof ▶

\(B=S_N^*S_N\) is invertible on \((\ker S_N)^\perp \): there is \(\sigma {\gt}0\) (the smallest positive eigenvalue \(\sigma _{\min }\) of \(B\) is the largest such) with \(\sigma \| u\| ^2\le \langle u,Bu\rangle \) for all \(u\in (\ker S_N)^\perp \).

Proof ▶

For \(\lambda =0\) and a solution \(\gamma _t\) of ??, \(\gamma _t=S_N^\dagger y+P_{\ker S_N}\gamma _0 +e^{-tB}\bigl(P_{(\ker S_N)^\perp }\gamma _0-S_N^\dagger y\bigr)\) ??.

Proof ▶

For \(\lambda =0\), a solution \(\gamma _t\) of ??, \(\gamma _\infty :=S_N^\dagger y+P_{\ker S_N}\gamma _0\) and any \(\sigma {\gt}0\) with \(\sigma \| u\| ^2\le \langle u,Bu\rangle \) on \((\ker S_N)^\perp \) (in particular \(\sigma =\sigma _{\min }\)), \(\| \gamma _t-\gamma _\infty \| _M\le e^{-\sigma t}\| P_{(\ker S_N)^\perp }\gamma _0-S_N^\dagger y\| _M\) for \(t\ge 0\).

Proof ▶

For \(\lambda =0\) and a solution \(\gamma _t\) of ??, \(\gamma _\infty :=\lim _{t\to \infty }\gamma _t=S_N^\dagger y+P_{\ker S_N}\gamma _0\).

Proof ▶

For \(\gamma _\infty =S_N^\dagger y+P_{\ker S_N}\gamma _0\), \(S_N\gamma _\infty =P_{\operatorname {ran}S_N}y\).

Proof ▶

For \(\gamma _\infty =S_N^\dagger y+P_{\ker S_N}\gamma _0\), \(\| \gamma _\infty -S_N^\dagger y\| _M=\| P_{\ker S_N}\gamma _0\| _M\), and \(\gamma _\infty =S_N^\dagger y\) if and only if \(P_{\ker S_N}\gamma _0=0\).

Proof ▶

For \(\sigma {\gt}0\) with \(\sigma \| u\| ^2\le \langle u,Bu\rangle \) on \((\ker S_N)^\perp \) and \(\lambda {\gt}0\), \(\| \gamma _\lambda -S_N^\dagger y\| _M\le \lambda \| S_N^\dagger y\| _M/\sigma \); in particular \(\gamma _\lambda \to S_N^\dagger y\) as \(\lambda \downarrow 0\).

Proof ▶

For \(\lambda {\gt}0\), \(\gamma _\lambda =(B+\lambda )^{-1}S_N^*y=S_N^*(K_{N,\nu _M}+\lambda )^{-1}y\), the values at the particle positions of \(R^{(N)}_{\lambda ,\nu _M}y\).

Proof ▶
Theorem 265
✓

\(\operatorname {rank}S_N\le N\), hence \(\dim \ker S_N\ge M-N\); in particular \(\dim \ker S_N\ge 1\) if \(M{\gt}N\).

Proof ▶
Theorem 266
✓

If the components of \(\gamma _0\) are centered, pairwise uncorrelated with variance \(\tau ^2\) (e.g. i.i.d.) and independent of \(z_1,\dots ,z_M\), then \({\mathbb E}\bigl[\| P_{\ker S_N}\gamma _0\| _M^2\, \big|\, z\bigr]=\frac{\tau ^2\dim \ker S_N}{M} \ge \tau ^2\bigl(1-\frac NM\bigr)\) ??.

Proof ▶
Theorem 267
✓

Under the assumptions of 266, for every fixed test vector \(q\in {\mathcal{H}}_M\), \({\mathbb E}\bigl[\langle q,P_{\ker S_N}\gamma _0\rangle _M^2\, \big|\, z\bigr] =\frac{\tau ^2}M\| P_{\ker S_N}q\| _M^2\le \frac{\tau ^2\| q\| _M^2}M\) ??.

Proof ▶

(Necessity of amplitude regularization.) For \(\lambda =0\), \(\beta =0\) and frozen hidden parameters, the endpoint of the fixed-feature flow is \(\gamma _\infty =S_N^\dagger y+P_{\ker S_N}\gamma _0\): the canonical empirical ridgelet transform plus the \(\ker S_N\) component of the initialization, which is data independent, invisible to the training loss and conserved by the flow. With amplitude regularization \(\lambda {\gt}0\) the \(\ker S_N\) component decays like \(e^{-\lambda t}\): \(P_{\ker S_N}\gamma _t=e^{-\lambda t}P_{\ker S_N}\gamma _0\).

Proof ▶