Are ResNets Provably Better than Linear Predictors?
  A residual network (or ResNet) is a standard deep neural net architecture,
with state-of-the-art performance across numerous applications. The main
premise of ResNets is that they allow the training of each layer to focus on
fitting just the residual of the previous layer's output and the target output.
Thus, we should expect that the trained network is no worse than what we can
obtain if we remove the residual layers and train a shallower network instead.
However, due to the non-convexity of the optimization problem, it is not at all
clear that ResNets indeed achieve this behavior, rather than getting stuck at
some arbitrarily poor local minimum. In this paper, we rigorously prove that
arbitrarily deep, nonlinear residual units indeed exhibit this behavior, in the
sense that the optimization landscape contains no local minima with value above
what can be obtained with a linear predictor (namely a 1-layer network).
Notably, we show this under minimal or no assumptions on the precise network
architecture, data distribution, or loss function used. We also provide a
quantitative analysis of approximate stationary points for this problem.
Finally, we show that with a certain tweak to the architecture, training the
network with standard stochastic gradient descent achieves an objective value
close or better than any linear predictor.
