SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data
Neural networks exhibit good generalization behavior in the over-parameterized regime, where the number of network parameters exceeds the number of observations. Nonetheless, current generalization bounds for neural networks fail to explain this phenomenon. In an attempt to bridge this gap, we study the problem of learning a two-layer over-parameterized neural network, when the data is generated by a linearly separable function. In the case where the network has Leaky ReLU activations, we provide both optimization and generalization guarantees for over-parameterized networks. Specifically, we prove convergence rates of SGD to a global minimum and provide generalization guarantees for this global minimum that are independent of the network size. Therefore, our result clearly shows that the use of SGD for optimization both finds a global minimum, and avoids overfitting despite the high capacity of the model. This is the first theoretical demonstration that SGD can avoid overfitting, when learning over-specified neural network classifiers.
 Paper studies an interesting phenomenon of overparameterised models being able to learn well-generalising solutions. It focuses on a setting with three crucial simplifications: - data is linearly separable - model is 1-hidden layer feed forward network with homogenous activations - **only input-hidden layer weights** are trained, while the hidden-output layer*s weights are fixed to be (v, v, v, ..., v, -v, -v, -v, ..., -v) (in particular -- (1,1,...,1,-1,-1,...,-1)) While the last assumption does not limit the expressiveness of the model in any way, as homogenous activations have the property of f(ax)=af(x) (for positive a) and so for any unconstrained model in the second layer, we can "propagate" its weights back into first layer and obtain functionally equivalent network. However, learning dynamics of a model of form z(x) = SUM( g(Wx+b) ) - SUM( g(Vx+c) ) + d and "standard" neural model z(x) = Vg(Wx+b)+c can be completely different. Consequently, while the results are very interesting, claiming their applicability to the deep models is (at this point) far fetched. In particular, abstract suggests no simplifications are being made, which does not correspond to actual result in the paper. The results themselves are interesting, but due to the above restriction it is not clear whether it sheds any light on neural nets, or simply described a behaviour of very specific, non-standard shallow model. I am happy to revisit my current rating given authors rephrase the paper so that the simplifications being made are clear both in abstract and in the text, and that (at least empirically) it does not affect learning in practice. In other words - all the experiments in the paper follow the assumption made, if authors claim is that the restriction introduced does not matter, but make proofs too technical - at least experimental section should show this. If the claims do not hold empirically without the assumptions made, then the assumptions are not realistic and cannot be used for explaining the behaviour of models we are interested in. Pros: - tackling a hard problem of overparametrised models, without introducing common unrealistic assumptions of activations independence - very nice result of "phase change" dependend on the size of hidden layer in section 7 Cons: - simplification with non-trainable second layer is currently not well studied in the paper; and while not affecting expressive power - it is something that can change learning dynamics completely # After the update Authors addressed my concerns by: - making simplification assumption clearer in the text - adding empirical evaluation without the assumption - weakening the assumptions I find these modifications satisfactory and rating has been updated accordingly.
You are a member of the scientific community tasked with peer review. Review the following paper title and abstract.
### Title + Abstract
SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data
Neural networks exhibit good generalization behavior in the over-parameterized regime, where the number of network parameters exceeds the number of observations. Nonetheless, current generalization bounds for neural networks fail to explain this phenomenon. In an attempt to bridge this gap, we study the problem of learning a two-layer over-parameterized neural network, when the data is generated by a linearly separable function. In the case where the network has Leaky ReLU activations, we provide both optimization and generalization guarantees for over-parameterized networks. Specifically, we prove convergence rates of SGD to a global minimum and provide generalization guarantees for this global minimum that are independent of the network size. Therefore, our result clearly shows that the use of SGD for optimization both finds a global minimum, and avoids overfitting despite the high capacity of the model. This is the first theoretical demonstration that SGD can avoid overfitting, when learning over-specified neural network classifiers.
user
<think>Okay, to do a decent peer review, I should start with summarizing what the work is about. This includes novelty, contributions, clarity, and impact. I might include suggestions to issues that I find critical to the usefulness of the work. Starting with novelty, there are different types of novelty. The first aspect of novelty is scope and scale. Is the work covering a broader perspective than previous works? The second aspect is methodology. Is the proposed methodology novel compared to previous methods? Do they provide any significant advantage over previous methodologies? The third aspect is results. Are the results different compared previous work? Does this lead to any novel theories or an extension of current theories? Next is clarity, I will be reading the work in depth and analyze if any sentences can be potentially ambiguous or misleading. If any sentences are ambiguous, I will state them and give a suggestion on how to rephrase such sentence or how to make more clear to the audience. Lastly, impact is important. I will attempt to predict how such work will impact the scientific community. This might include the applications of such work and how the work might transform the way we study a certain topic. Finally, I will might only mention issues that are critical. This is to keep the review as concise and helpful as possible.</think>



 Paper studies an interesting phenomenon of overparameterised models being able to learn well-generalising solutions. It focuses on a setting with three crucial simplifications: - data is linearly separable - model is 1-hidden layer feed forward network with homogenous activations - **only input-hidden layer weights** are trained, while the hidden-output layer*s weights are fixed to be (v, v, v, ..., v, -v, -v, -v, ..., -v) (in particular -- (1,1,...,1,-1,-1,...,-1)) While the last assumption does not limit the expressiveness of the model in any way, as homogenous activations have the property of f(ax)=af(x) (for positive a) and so for any unconstrained model in the second layer, we can "propagate" its weights back into first layer and obtain functionally equivalent network. However, learning dynamics of a model of form z(x) = SUM( g(Wx+b) ) - SUM( g(Vx+c) ) + d and "standard" neural model z(x) = Vg(Wx+b)+c can be completely different. Consequently, while the results are very interesting, claiming their applicability to the deep models is (at this point) far fetched. In particular, abstract suggests no simplifications are being made, which does not correspond to actual result in the paper. The results themselves are interesting, but due to the above restriction it is not clear whether it sheds any light on neural nets, or simply described a behaviour of very specific, non-standard shallow model. I am happy to revisit my current rating given authors rephrase the paper so that the simplifications being made are clear both in abstract and in the text, and that (at least empirically) it does not affect learning in practice. In other words - all the experiments in the paper follow the assumption made, if authors claim is that the restriction introduced does not matter, but make proofs too technical - at least experimental section should show this. If the claims do not hold empirically without the assumptions made, then the assumptions are not realistic and cannot be used for explaining the behaviour of models we are interested in. Pros: - tackling a hard problem of overparametrised models, without introducing common unrealistic assumptions of activations independence - very nice result of "phase change" dependend on the size of hidden layer in section 7 Cons: - simplification with non-trainable second layer is currently not well studied in the paper; and while not affecting expressive power - it is something that can change learning dynamics completely # After the update Authors addressed my concerns by: - making simplification assumption clearer in the text - adding empirical evaluation without the assumption - weakening the assumptions I find these modifications satisfactory and rating has been updated accordingly.
assistant
 Paper studies an interesting phenomenon of overparameterised models being able to learn well-generalising solutions. It focuses on a setting with three crucial simplifications: - data is linearly separable - model is 1-hidden layer feed forward network with homogenous activations - **only input-hidden layer weights** are trained, while the hidden-output layer*s weights are fixed to be (v, v, v, ..., v, -v, -v, -v, ..., -v) (in particular -- (1,1,...,1,-1,-1,...,-1)) While the last assumption does not limit the expressiveness of the model in any way, as homogenous activations have the property of f(ax)=af(x) (for positive a) and so for any unconstrained model in the second layer, we can "propagate" its weights back into first layer and obtain functionally equivalent network. However, learning dynamics of a model of form z(x) = SUM( g(Wx+b) ) - SUM( g(Vx+c) ) + d and "standard" neural model z(x) = Vg(Wx+b)+c can be completely different. Consequently, while the results are very interesting, claiming their applicability to the deep models is (at this point) far fetched. In particular, abstract suggests no simplifications are being made, which does not correspond to actual result in the paper. The results themselves are interesting, but due to the above restriction it is not clear whether it sheds any light on neural nets, or simply described a behaviour of very specific, non-standard shallow model. I am happy to revisit my current rating given authors rephrase the paper so that the simplifications being made are clear both in abstract and in the text, and that (at least empirically) it does not affect learning in practice. In other words - all the experiments in the paper follow the assumption made, if authors claim is that the restriction introduced does not matter, but make proofs too technical - at least experimental section should show this. If the claims do not hold empirically without the assumptions made, then the assumptions are not realistic and cannot be used for explaining the behaviour of models we are interested in. Pros: - tackling a hard problem of overparametrised models, without introducing common unrealistic assumptions of activations independence - very nice result of "phase change" dependend on the size of hidden layer in section 7 Cons: - simplification with non-trainable second layer is currently not well studied in the paper; and while not affecting expressive power - it is something that can change learning dynamics completely # After the update Authors addressed my concerns by: - making simplification assumption clearer in the text - adding empirical evaluation without the assumption - weakening the assumptions I find these modifications satisfactory and rating has been updated accordingly.