Past works have shown that, somewhat surprisingly, over-parametrization can help generalization in neural networks. Towards explaining this phenomenon, we adopt a margin-based perspective. We establish: 1) for multi-layer feedforward relu networks, the global minimizer of a weakly-regularized cross-entropy loss has the maximum normalized margin among all networks, 2) as a result, increasing the over-parametrization improves the normalized margin and generalization error bounds for deep networks. In the case of two-layer networks, an infinite-width neural network enjoys the best generalization guarantees. The typical infinite feature methods are kernel methods; we compare the neural net margin with that of kernel methods and construct natural instances where kernel methods have much weaker generalization guarantees. We validate this gap between the two approaches empirically. Finally, this infinite-neuron viewpoint is also fruitful for analyzing optimization. We show that a perturbed gradient flow on infinite-size networks finds a global optimizer in polynomial time.
The authors claim to prove three things: (1) Under logistic loss (with a vanishing regularization), the normalized margin (of the solution) converges to the max normalized margin, for positive homogenous functions. This is an asymptotic result: the amount of regularization vanishes. (2) For one hidden layer NN, the max margin under l_2 norm constraint on weights in the limit, is equivalent to the l_1 constraint (total variation) on the sign measure (specified by infinite neurons) for the one hidden layer NN. (3) Show some convergence rate for the mean-field view of one hidden layer NN, i.e., the Wasserstein gradient flow on the measure (of the neurons). The author show some positive result for a perturbed version.
The problem is certainly interesting. However, my main concerns are: (1) the novelty of the main theorems given the literature, and (2) the carefulness of stating what is known in the literature review.
In summary:
1. Theorem 2.1, Theorem 3.1, and Theorem 3.3 are anticipated, or not as critical, given the literature (detailed reasons in major comments).
2. The construction in Theorem 3.5 is nice, but, it is only able to say an upper bound of the generalization of kernel is not good (comparing upper bounds is not enough). In addition, For Theorem 4.3. [Mei Montanari and Nguyen 2018] also considers similar perturbed Wasserstein gradient flow, with many convergence results. One needs to be more careful in stating what is new.
Major comments:
1. Theorem 3.3 (and Theorem 3.2) seems to be the most interesting/innovative one.
However, I would like to argue that it might be natural in one line proof, with the following alternative view:
--
l_2 norm constraint normalized margin, one hidden layer NN, with infinite neurons
gamma^star, infty :=
\max \min_i y_i int_{neuron} w || u || ReLU( x_i \bar{u}) dS^{d-1} -- integral over normalized neurons over sphere
under the constraint
int_{neuron} (w^2 + ||u||^2) dS^{d-1} \leq 1
This is equivalent to the l_1 constraint margin (variation norm), one hidden layer NN,
gamma_l_1 :=
\max \min_i y_i int_{neuron} rho(u) ReLU( x_i \bar{u}) dS^{d-1} -- integral over normalized neurons over sphere
under the constraint
int_{neuron} |rho(u)| dS^{d-1} \leq 1/2
here rho(u) is the sign measure represented by neurons. Simply because at the optimum
w || u || = 1/2 ( w^2 + || u ||^2) := rho(u)
therefore
gamma^star, infty =  gamma_l_1
So one see the factor 1/2 exactly.
--
In addition, [Bach 18, JMLR:v18:14-546] discuss more in depth the l_1 type constraint
(TV of sign measure) rather then l_2 type constraint (RKHS) for one hidden layer NN with infinite neurons. The authors should cite this work.
It is clear that l_1(neuron) < l_2(neuron) therefore
l_2 constraint margin is always smaller than l_1 constraint margin.
2. Theorem 2.1. I think the proof is almost a standard exercise given [Rosset, Zhu, and Hastie 04].
The observation for it generalizes to positive homogenous function beyond linear is a nice addition, but not crucial enough to stand out as an innovation.
Much of the difficulty in related paper lies in achieving non asymptotic convergence rate to max margin solution, for logistic loss [Soudry, Hoffer and Srebro 18], or what happens when data is not perfectly separable [Ji and Telgarsky 18].
3. Generalization result Theorem 3.1. Maybe it is better to state as a corollary, given the known results in the literature, in my opinion. This generalization is standard result from margin-based bounds available
[Koltchinskii and Panchenko 02, Bartlett and Mendelson 02].
In addition, the authors remark that the limit for (3.3) may not exist. You can change to limsup, your footnote[4]
is essentially the limsup definition.
4. Theorem 3.5. This construction of the data distribution is the part I like. However, you should remind the reader that
having a small margin for the kernel only implies the the upper bound for generalization is bad.
Comparing the upper bound doesn't mean kernel method is performing bad for the instance.
From a logic view, it is unclear the benefit of Theorem 3.5.
I do agree one can try to see in simulation if kernel/RKHS approach (l_2) is performing worse for generalization, for one hidden layer NN. But this is separate from the theory.
5. Theorem 4.3. This result should be put in the context of the literature. Specifically
[Mei Montanari and Nguyen 2018], Eqn 11-12. The perturbed wasserstein flow the authors considered
looks very close to [Mei Montanari and Nguyen 2018], Eqn 11-12, admittedly with the logistic loss instead of the square loss.
Right now, as stated in the current paper, it is very hard for the general audience to understand the contribution. A better job in comparing the literature will help.
For the technical crowd, maybe emphasize on why the "simga" can help you achieve a positive result.
Minor Comments:
6. One additional suggestion: seems to me Section 4 is a bit away from the central topic of the current paper.
I can understand that the optimization/convergence result will help complete the whole picture. However, to contribute to the "margin theme", it would be better to state with the "small vanishing regularization", how it affects the convergence of Theorem 4.3.
Even with this, it is unclear as one don't know how to connect different part of the paper: with what choice of vanishing regularization will generate a solution with a good margin, using the Wasserstein gradient flow.