Transcribed by Paxton Turner (edited by Asad Lodhia, Elchanan Mossel and Matthew Brennan)

In the Boolean circuits setup, there is a separation result based on depth of the following form:

Question: Can we prove a similar result for deep nets?

Last time we discussed the following separation result.

Today we will discuss a more elegant treatment of the 2 vs. 3 separation result which yields slightly stronger results.

Danielly’s Model

Danielly’s Model is formed as follows. Let \( x, x’ \) chosen uniformly (i.e., with respect to the Haar measure) from \(S^{d-1}\) and let \(f(x, x’) = g(\langle x, x’ \rangle) \). The nets of depth \(\ell\) are of the form:
\begin{eqnarray*}
\ell = 2 \qquad &w_2^{\text{T}} \sigma( W_1 x + W_2 x’ + b_1) + b_2 \\
\ell = 3 \qquad &w_3^{\text{T}} \sigma (W_2 \sigma(W_1 x + W_2 x’ + b_1) + b_2) + b_3 \\
\vdots \qquad &\vdots
\end{eqnarray*}
on the input \((x, x’)\). Here, we prove the following theorem.

This illustrates the “magic of 3.” Intuitively, we see the power of quadratic models over linear ones, at least for this specific context.

We begin with the following lemma which is of the flavor of universality of depth 1 nets:

Proof of Lemma (Sketch): Repartition the interval, and note that the Lipschitz condition implies the graph doesn’t deviate too far from a straight line.

Proof of the Theorem: We will prove the theorem in the following section and then show a corresponding lower bound.

Upper bound

We first show that the function can be approximated well by a depth 3 net:
\[
\langle x, x’ \rangle = \Bigg\| \frac{x+x’}{2} \Bigg\|_2^2 – \frac{1}{2} = \sum_{i=1}^d \left( \frac{x + x’}{2} \right)^2,
\]

which implies that a 2-layer network approximates \( \langle x, x’ \rangle \) well. We can also compute \( \sigma( \langle x, x’ \rangle) \) as a linear combination of the previous layers. This in combination with the lemma implies the desired result.

Lower bound

We want to show that a depth two net that approximates the function well is
very wide. For the analysis it will be useful to answer the following question:

Question: What is the distribution of \( \langle x, x’ \rangle \)?

Approximation: Rotation invariance implies that

\[
D(\langle x, x’ \rangle) = D'( \langle x, r \rangle ) = D( \langle x, e_1 \rangle) = D(x_1)
\]
Note that this is also true if \( x’ \) is deterministic and \( x \) is random.

The individual components \(\langle x, e_k \rangle\) of a uniform random vector in \( x \in S^{d-1}\) approaches a Gaussian as \(d \to \infty \). Indeed,
\begin{eqnarray*}
d \mu_d(x) &= \text{Vol}\left( (1 – x^2)^{1/2} S^{d-2} \right) \\
&= \frac{\Gamma(d/2)}{\sqrt{\pi} \Gamma((d-1)/2)} \left(1 – x^2 \right)^{\frac{d-3}{2}}
\end{eqnarray*}
which is a t-statistic distribution (and as \(d \to \infty\) converges to a gaussian). The same reasoning applies also if one of the vectors x, x’ is fixed. Therefore, if \(g = \psi ( \langle v, x \rangle, \langle v’, x’ \rangle ) \), then
\[
||g||_2^2 = ||\psi||_{L^2(\mu_d \times \mu_d)}^2,
\]
and if \(f = \phi( \langle x, x’ \rangle ) \), then
\[
||f||_2^2 = ||\phi||_{L^2(\mu_d)}^2 = \int_{S^{d-1} \times S^{d-1}} f^2(x, x’) \, d(m \times m),
\]
where \(d(m \times m)\) indicates the Haar measure.

Orthogonal Polynomials: Define \( P_0 = 1, P_1 = x,\) and
\[P_n = \frac{2n + d – 4}{n + d – 3} \cdot P_{n-1}(x) – \frac{n – 1}{n + d – 3} \cdot P_{n-2}(x)\]
We observe that
\[
||P_n||_2^2 = 1/N_{n,d} \quad \text{where} \quad N_{n,d} = \frac{(2n + d – 2) (n + d – 3)!}{n! (d – 2)!}
\]
and that \( ||P_n||_{\infty} = 1\). Now define
\[
h_n(x, x’) = \frac{P_n(\langle x, x’ \rangle)}{\sqrt{N_{n,d}}} \quad \text{and} \quad L_n^x(x) = h_n(x,x).
\]
The key fact we use is that
\[
\langle L_i^v, L_j^v \rangle = \mathbb{E}[ L_i^v(x) L_j^{v’}(x)] = \mathbb{E}[h_i(\langle v, x \rangle) h_j(\langle v’, x \rangle) ] = \delta_{i,j} P_i(\langle v, v’ \rangle),
\]
which implies
\[
\mathbb{E}[h_n(x, x’) L_i^v(x) L_j^{v’}(x)] = 1(i = j = n) N_{n_1}^{-1/2} P_n(\langle v, v’ \rangle).
\]
To flesh out the above more carefully,
\begin{align*}
\mathbb{E}[h_n(x,x’) L_i^v(x) L_j^{v’}(x’)] &= \mathbb{E}_x\left[L_i^v(x) \mathbb{E}_{x’}[h_n(x,x’) L_j^{v’}(x’)]\right] \\
&= \mathbb{E}_x[L_i^v \delta_{j = n} P_n(v’, x)] \\
&= \mathbb{E}_x\left[L_i^v(x) \frac{L_j^{v’}(x)}{\sqrt{N_{n,d}}}\right]
\end{align*}

Lower Bound Idea: We now outline how to obtain the desired lower bound. Expand \(g(x, x’) = \sum \alpha_i h_i(x,x’) \) and choose \(f\) that is “noise sensitive”, i.e., has a lot of mass at higher Fourier levels. For the rest of the argument assume that \( f = h_n \) for a large \(n\) (though \( h_n \) is not a Lip function, but we can find a Lip function that has a lot of weight on high levels).

We want \( ||g – \sum_{j=1}^m g_j ||_2^2 \) to be large when \(g_j = b_j \sigma( \langle v_j, x \rangle) \geq c \) unless either \(b_j\) is large. Otherwise, there exists \(j\) such that \( \langle g, g_j \rangle \geq \frac{c}{m} \). Note that if \(h_n\) is close to \(\sum_{j = 1}^m g_j \), then we need to have at least one \(j\) where \( \langle g_j, f \rangle \geq \frac{||f||_2^2}{4m}. \)

We now compute \( \langle g_j , f \rangle \). Observe that
\[
g_j = \sum \beta_{k, \ell} L_k^v(x) L_{\ell}^{v’}(x’)
\]
\[
g_j(x,x’) = \psi(\langle v, x \rangle, \langle v’, x’ \rangle)
\]
\[
\sum \beta_{k, \ell}^2 = ||g_j||_2^2.
\]
Therefore,
\[
|\langle g_j, h_n \rangle | = N_{n,d}^{-1/2} |\beta_{n,n} P_n( \langle v, v’ \rangle )| \leq N_{n,d}^{-1/2} |\beta_{n,n}|
\]
so \(m\) is very large or \(||g_j^2||_2^2\) is very large. Informally, we get a bad approximation of \(h_n(\langle x, x’ \rangle) \) unless

• Width \(\geq N_{n,d}^{\Omega(1)}\) or
  
• Max-weight \(\geq N_{n,d}^{\Omega(1)} \)
  

Kane-Williams Model

Threshold gates are given by

\[
\mathbf{1}\left\{\sum w_i x_i \geq t\right\}.
\]

The basic unit threshold is
\[
f(x) = \text{sgn}(w_0 + \sum_{i = 1}^n w_i x_i).
\]

We assume a distribution that is uniform over \(\{0,1\}^n\).

Meta-Question: Can we use reduction between models (eg, the previous result) to get better separation in the binary case?

Partial answer: Due to complexity-theoretic issues, better than \( \text{poly}(n) \) isn’t possible.

Question: Can we replace new activations into the previous result (or this one)?

Answer: Isn’t written down, but should be straightforward.

PAC Learning

We close this lecture with the definition of PAC-learning . We have a space \(X_n\) and are interested in functions \( f: X_n \to \{0,1\} \). Let \( \mathcal{C} \) be the class of such functions (eg, 2-layer networks).

Here, \(\delta\) is interpreted as a global parameter , and \(\epsilon\) is the probabilistic error .