tl;dr: vanilla residual networks are very good approximators of functions which can be represented as linear perturbations of the identity. In the linear setting, optimization is aided by a benevolent landscape having only minima in certain (interesting) regions. Finally, very simple ResNets can completely learn datasets with $\mathcal{O} (n \log n + \ldots)$ parameters. All this seems to indicate that deep and simple architectures might be enough to achieve great performance.

In general, it is hard for classical deep nets to “preserve features which are good”: initialization with zero mean and small gradients make it hard to learn the identity at any given layer. Even though batchnorm¹ seeks to alleviate this issue, it has been residual networks which have most improved upon it.² In a residual net

(…) each residual layer has the form $x + h (x)$, rather than $h (x)$. This simple reparameterization allows for much deeper architectures largely avoiding the problem of vanishing (or exploding) gradients.

Identity parametrizations improve optimization

The authors work first in the linear setting, i.e. they consider only networks which are compositions of linear perturbations of the identity:³

\[ h (x) = (I + A_{l}) \cdots (I + A_{2}) (I + A_{1}) x \]

The objective function to mimize is the population risk with quadratic loss:

\[ f (A) = f (A_{1}, \ldots, A_{l}) := \mathbb{E}_{X, Y} | Y - (I + A_{l}) \cdots (I + A_{1}) X |^2 . \]

Labels are assigned with noise, that is $Y = RX + \xi$, with $\xi \sim \mathcal{N} (0, I_{d})$. Note that the problem over the variables $A = (A_{1}, \ldots, A_{l})$ is non-convex.

The first result of the paper states that deep networks with many layers have minima of proportionally low (spectral) norm.⁴ Because of this, it makes sense to study critical points with small norm, and it turns out that there are only minima. The main result of this section is the following one, where one can think of $\tau$ as being $\mathcal{O} (1 / l)$:

Theorem 1: For every $\tau < 1$, every critical point $A$ of the objective function $f$ with \[ \underset{1 \leqslant i \leqslant l}{\max} | A_{i} | \leqslant \tau \] is a global minimum.

This is good news since, under the assumption that the model is correct, a “good” (in some sense) optimization algorithm will converge to it.⁵ The proof is relatively straightforward too: rewrite the risk as the norm of a product by the covariance: $f (A) = | E (A) \Sigma^{1 / 2} |^2 + C$, then, using that $| A_{i} |$ are small, show that if $\nabla f (A) = 0$ this can only be if $E (A) = 0$, where $E$ precisely encodes the condition of being at an optimum: $E (A) = (I + A_{l}) \cdots (I + A_{1}) - R$.

Identity parametrizations improve representation

The authors consider next non-linear simplified residual networks with each layer of the form

\begin{equation} \label{eq:residual-unit}\tag{1} h_{j} (x) = x + V_{j} \sigma (U_{j} x + b_{j}) \end{equation}

where $V_{j}, U_{j} \in \mathbb{R}^{k \times k}$ are weight matrices, $b_{j} \in \mathbb{R}^k$ is a bias vector and $\sigma (z) = \max (0, z)$ is a ReLU activation.⁶ Note that the layer size is constant. No batchnorm is applied. The problem is $r$-class classification. Assuming (the admittedly natural condition) that all the training data are uniformly separated by a minimal distance $\rho > 0$, they prove that perfectly learning $n$ data points is possible with $n \log n$ parameters:

Theorem 2: There exists a residual network with $\mathcal{O}(n \log n + r^2)$ parameters that perfectly fits the training data.

By choosing the hyperparameter $k \in \mathcal{O} (\log n)$ and $l = \lceil n / k \rceil$ the complexity stated is obtained with a bit of arithmetic. The proof consists then of a somewhat explicit construction of the network. Very roughly, the weight matrices of the hidden layers are chosen as to assign each data point to one of $r$ surrogate label vectors $q_{1}, \ldots, q_{r} \in \mathbb{R}^k$, then the last layer converts these to 1-hot label vectors for output. The main ingredient is therefore the proof that it is possible to map the inputs $x_{i}$ to the surrogate vectors in a way such that the final layer has almost no work left to do.⁷

This is achieved by showing that:

(…) for an (almost) arbitrary sequence of vectors $x_{1}, \ldots, x_{n}$ there exist [weights $U, V, b$] such that operation (1) transforms $k$ [of them] to an arbitrary set of other $k$ vectors that we can freely choose, and maintains the value of the remaining $n - k$ vectors.

Experiments

Working on CIFAR10 and CIFAR100, the authors tweaked a standard ResNet architecture in Tensorflow to have constant size $c$ of convolution, no batch norm and smaller weight initialization.⁸ Several features stand out:

• The last layer is a fixed random projection. Therefore all parameters are in the convolutioms.
• Lack of batchnorm or other regularizers seemed not to lead to serious overfitting, even though the model had $\sim 13.6 \times 10^6$ parameters.
• Both problems where tackled with the same networks and the convolutions where of constant size.

Finally, results on ImageNet were not as bright, though the authors seem confident that this is due to lack of tuning of hyperparameters and learning rate. It would be interesting to find out how true this is and how much harder this tuning becomes by having discarded regularization techniques like dropout or additional data processing.

Extensions

For further work in the non-linear case (which as of this writing is reported to be work in progress) where the model is no longer to be assumed correct but instead only (mild) regularity assumptions are made, be sure to check out Bartlett’s talk Representational and optimization properties of Deep Residual Networks .