Venue: ICLR 2018 conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: Summary:
This paper considers the problem of classifying linearly separable data with a two layer \alpha- Leaky ReLU network, in the over-parametrized setting with 2k hidden units. The algorithm used for training is SGD which minimizes the hinge loss error over the training data. The parameters in the top layer are fixed in advance and only the parameters in the hidden layer are updated using SGD. First result shows that the loss function does not have any sub-optimal local minima. Later, for the above method, the paper gives a bound proportional to ||w*||^2/\alpha^2, on the number of non-zero updates made by the algorithm (similar to perceptron analysis), before converging to a global minima - w*. Using this a generalization error bound independent of number of hidden units is presented. Later the paper studies ReLU networks and shows that loss in this case can have sub-optimal local minima. 

Comments:

This paper considers a simpler setting to study why SGD is successful in recovering solutions that generalize well even though the neural networks used are typically over-parametrized. While the paper considers a simpler setting of classifying linearly separable data and training only the hidden layer, it nevertheless provides a useful insight on the role of SGD in recovering solutions that generalize well (independent of number of hidden units 'k'). 

One confusing aspect in the paper is the optimization and generalization results hold for any global minima w* of the L_s(w). There is a step missing of taking the minimum over all such w*, which will give the tightest bounds for SGD, and it will be useful to clear this up in the paper. 

More importantly I am curious how close the updates are when, 1)SGD is updating only the hidden units  and 2) SGD is updating both the layers. Simple intuition suggests SGD might update the top layer "more" that the hidden layer as the gradients tend to decay down the layers. It is useful to discuss this in the paper and may be have some experiments on linearly separable data but with updates in both layers.
review_title: Good paper on understanding the role of SGD in generalization

final_score: rating: 7: Good paper, accept
review_content: This paper shows that on linearly separable data, SGD on a overparametrized network (one hidden layer, with leaky ReLU activations) can still lean a classifier that provably generalizes. The assumption on data and structure of network is a bit strong, but this is the first result that achieves a number of desirable properties
``1. Works for overparametrized network
2. Finds global optimal solution for a non-convex network.
3. Has generalization guarantees (and generalization is related to the SGD algorithm).
4. Number of samples need not depend on the number of neurons. 

There have been several papers achieving 1 and 2 (with much weaker assumptions), but they do not have 3 and 4. The proof of the optimization part is very similar to the proof of perceptron algorithm, and really relies on linear separability. The proof of generalization is based on a compression argument, where if an algorithm does not take many nonzero steps, then it must have good generalization. Ideally, one would also want to see a result where overparametrization actually helps (in the main result the whole data can be learned by a linear classifier). This is somewhat achieved when the activation is replaced with standard ReLU, where the paper showed with a small number of hidden units the algorithm is likely to get stuck at a local minima, but with enough hidden units the algorithm is likely to converge (but even in this case, the data is still linearly separable and can be learned just by a perceptron). 

The main concern about the paper is the possibility of generalizing the result. The algorithm part seems to heavily rely on the linear separable assumption. The generalization part relies on not making many non-zero updates, which is not really true in realistic settings (where the data is accessed in multiple passes) [After author response: Yes in the linearly separable case with hinge loss it is quite possible that the number of updates is sublinear. However what I meant here is that with more complicated data and different loss functions it is hard to believe that this can still hold.]. The related work section is also a bit unfair to some of the other generalization results (e.g. Bartlett et al. Neyshabur et al.): those results work on more general network settings, and it's not completely clear that they cannot be related to the algorithm because they rely on certain solution specific quantities (such as spectral/Frobenius norms of the weight matrices) and it could be possible that SGD tends to find a solution with small norm (which can be proved in linear setting and might also be provable for the setting of this paper) [This is addressed in the author response].

Overall, even though the assumptions might be a bit strong, I think this is an interesting result working towards a good direction and should be accepted.
review_title: The paper proves interesting properties of SGD on linearly separable data, first result on a interesting direction although the assumption/techniques seem a bit limited.

final_score: rating: 7: Good paper, accept
review_content: 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. 

review_title: Interesting result for generalisation guarantees of overparametrised 1-hidden layer network with fixed output layer.

Meta-review: This is a high quality paper, clearly written, highly original, and clearly significant. The paper gives a complete analysis of SGD in a two layer network where the second layer does not undergo training and the data are linearly separable.  Experimental results confirm the theoretical suggestion that the second layer can be trained provided the weights don't change sign and remain bounded. The authors address the major concerns of the reviewers (namely, whether these results are indicative given the assumptions). This line of work seems very promising.
Decision: Accept (Poster)