SGD Learns Over-parameterized Networks that Provably Generalize on\n Linearly Separable Data

Alon Brutzkus, Amir Globerson, Eran Malach, Shai Shalev‐Shwartz

arXiv (Cornell University) · 2017 · 34 citations · 0 references

DOIFull text

Open access

Concepts

Abstract

Neural networks exhibit good generalization behavior in the\nover-parameterized regime, where the number of network parameters exceeds the\nnumber of observations. Nonetheless, current generalization bounds for neural\nnetworks fail to explain this phenomenon. In an attempt to bridge this gap, we\nstudy the problem of learning a two-layer over-parameterized neural network,\nwhen the data is generated by a linearly separable function. In the case where\nthe network has Leaky ReLU activations, we provide both optimization and\ngeneralization guarantees for over-parameterized networks. Specifically, we\nprove convergence rates of SGD to a global minimum and provide generalization\nguarantees for this global minimum that are independent of the network size.\nTherefore, our result clearly shows that the use of SGD for optimization both\nfinds a global minimum, and avoids overfitting despite the high capacity of the\nmodel. This is the first theoretical demonstration that SGD can avoid\noverfitting, when learning over-specified neural network classifiers.\n