18.S995: Topics in Deep Learning Theory

Linear Algebra

Let $H \in \mathbb{R}^{d \times d}$ be symmetric and positive definite, let $w \in \mathbb{R}^d$, and define $L(w) = \tfrac{1}{2} w^\top H w$.

1. Compute the gradient $\nabla L(w)$.
2. Let $w$ follow gradient descent: $w_{t+1} = w_t - \eta \nabla L(w_t)$. Solve for $w_t$ in closed form as a function of $t$.
3. For what $\eta$ does $w_t \to 0$? What changes if $H$ is only positive semidefinite?

Analysis

Let $f:\mathbb{R}^d\to\mathbb{R}$ be differentiable and suppose that $\nabla f$ is $L$-Lipschitz with respect to a norm $\|\cdot\|$. Let $r_0,r_1,\ldots\in\mathbb{R}^d$ satisfy $\lVert r_t\rVert\leq\varepsilon$. Starting from $x_0=y_0$, define $$x_{t+1}=x_t-\eta\nabla f(x_t),\qquad y_{t+1}=y_t-\eta\qty{\nabla f(y_t)+r_t}.$$

1. Show that $$\lVert x_{t+1}-y_{t+1}\rVert\leq\qty{1+\eta L}\lVert x_t-y_t\rVert+\eta\varepsilon.$$
2. Using $1+x\leq e^x$, show that $$\lVert x_t-y_t\rVert\leq\frac{\varepsilon}{L}\qty{e^{\eta Lt}-1}.$$

Neural Networks

1. Let $x \in \mathbb{R}^d$, $W \in \mathbb{R}^{m \times d}$, $b \in \mathbb{R}^m$, and $a \in \mathbb{R}^m$. Let $\sigma \in C^1\qty{\mathbb{R}}$ be applied coordinatewise and define the two-layer neural network $f_\theta(x) = a^\top \sigma(Wx+b)$. For $y \in \mathbb{R}$, let $L = \tfrac{1}{2}\qty{y-f_\theta(x)}^2$. Compute $\nabla_W L$.
2. Now let $A \in \mathbb{R}^{k \times m}$ and define the logits $f_\theta(x) = A\sigma(Wx+b) \in \mathbb{R}^k$. For a label $y \in \{1, \ldots, k\}$, let $L = -\log\qty{\operatorname{softmax}\qty{f_\theta(x)}_y}$. Compute $\nabla_W L$.
3. Using JAX or PyTorch, train the network from question 2 on MNIST using cross-entropy loss until it interpolates the training data (100% training accuracy). Plot the train loss and train accuracy as a function of steps.

Probability

A mean-zero random variable $X$ is $\sigma$-sub-Gaussian if, for every $\lambda \in \mathbb{R}$, $$\mathbb{E}\exp\qty{\lambda X} \leq \exp\qty{\frac{\lambda^2\sigma^2}{2}}.$$

1. Let $X \sim \mathcal{N}(0,\sigma^2)$. Show that $X$ is $\sigma$-sub-Gaussian.
2. Let $X_1, \ldots, X_n$ be independent mean-zero random variables such that $X_i$ is $\sigma_i$-sub-Gaussian. Show that $\sum_{i=1}^n X_i$ is $\sqrt{\sum_{i=1}^n \sigma_i^2}$-sub-Gaussian.
3. Let $X$ be $\sigma$-sub-Gaussian. Use Markov's inequality on $\exp\qty{\lambda X}$ to show that $$\mathbb{P}\qty{|X| \geq t} \leq 2\exp\qty{-\frac{t^2}{2\sigma^2}}.$$
4. Let $W \in \mathbb{R}^{m \times d}$ have i.i.d. $\mathcal{N}(0,1)$ entries.
   1. Let $\mathcal{N}_m \subset \mathbb{S}^{m-1}$ and $\mathcal{N}_d \subset \mathbb{S}^{d-1}$ be $1/4$-nets with cardinalities at most $9^m$ and $9^d$, respectively. Show that $$\lVert W \rVert_{\mathrm{op}} \leq 2\max_{u \in \mathcal{N}_m,\,v \in \mathcal{N}_d}\left|u^\top Wv\right|.$$
   2. For each fixed $u,v$, show that $u^\top Wv \sim \mathcal{N}(0,1)$.
   3. Use a union bound to prove that, for some absolute constant $C$, with probability at least $1-\delta$, $$\lVert W \rVert_{\mathrm{op}} \leq C\qty{\sqrt{m}+\sqrt{d}+\sqrt{2\log\qty{1/\delta}}}.$$ Note: This bound actually holds with $C=1$, but proving this requires more advanced techniques.