Reviews: Algorithm-Dependent Generalization Bounds for Overparameterized Deep Residual Networks

The paper describes the proof for characterizing the fully connected deep ReLU residual network's optimization and generalization properties, trained with gradient descent following Gaussian initialization.Building on the work from [5] the authors demonstrate that over-parameterization forces gradient descent-trained networks to stay in a small neighborhood of initialization where the learned networks are guaranteed to find small surrogate training error, and come from a sufficiently small hypothesis class to guarantee a small generalization gap between the training and test errors. This allows for derivation of test error guarantees. The proof's show that provided we have sufficient overparameterization, gradient descent is guaranteed to find networks that have arbitrarily high classification accuracy. In comparison with the results of Cao and Gu [5], the width m, number of samples n, step size η, and number of iterates K required for the guarantees for residual networks given in Theorem 3.5 and Corollary 3.7 all have (at most) logarithmic dependence on L. Additionally, the step size and number of iterations required for our guarantees are independent of the depth. Finally, the presence of skip connections in the network architecture removes the complications relating to the depth that traditionally arise in the analysis of non-residual architectures, and provides an explanation for why residual networks can be trained easily at all depths, unlike non-residual ones.