We show that if the usual training loss is augmented by a Lipschitz regularization term, then the networks generalize. We prove generalization by first establishing a stronger convergence result, along with a rate of convergence. A second result resolves a question posed in Zhang et al. (2016): how can a model distinguish between the case of clean labels, and randomized labels? Our answer is that Lipschitz regularization using the Lipschitz constant of the clean data makes this distinction. In this case, the model learns a different function which we hypothesize correctly fails to learn the dirty labels.
The paper gives convergence guarantees to the true neural network classifier for the networks that are explicitly regularizing the (exact) Lipschitz constant of the network. The bound stated decays as ( log(n)/n )^{1/m}, where n is the number of training points and m is the dimension of the data manifold. Thus the decay rate is pretty slow when the data lies on a high-dimensional manifold. I believe it should also depend on the volume of the data manifold.
Computing the exact Lipschitz constant of the network is intractable. All the theorems apply to minimization problem defined in (1) with the exact Lip(u,X) being regularized, and not to the minimization problem of the lower bound (2). I believe there are also no convergence guarantees how quickly this lower bound on the Lipschitz constant approaches Lip(u,X), unless some assumptions are made on the smoothness of the data manifold (comments and insights would be appreciated). Thus in my opinion the current results have little practical importance. Nevertheless, it’s still interesting to see some ideal-setting guarantees being established.
Theorem 2.7: Is m == m_0 (the dimension of the data manifold)? Shouldn’t the bound be 2*C*L_0….? (assuming lemma 2.9 is correct)
Cor 2.8: Where does the volume Vol(M) of the manifold disappear? Is C in equation (6) the same C as in Theorem 2.7? Also, it looks like the bound should bound should have C^2 (assuming theorem 2.7 is correct, and the C’s are the same).
Introduction: I assume u(x,w) is not the last layer map, but a map from the input space to the labels (i.e., the whole neural network function and not just the map from the last hidden layer to the labels). If I am correct, it’s misleading to refer to u(x,w) as the last layer map. And if it is the last layer map, please justify why it is enough to consider the Lipschitz constant of the last layer.
The term “clean data” is never defined. My guess is that “clean data” refers to the realizable  setting, and “noisy” to agnostic, where the hypothesis space consist of neural networks of arbitrary size.
“Our analysis can avoid the dependence on the weights because we make the assumption that there are enough parameters so that u can perfectly fit the training data. The assumption is justified by Zhang et al. (2016).”
Note, that the network used in practice achieve zero classification error, as demonstrated by Zhang et al, but I doubt the cross entropy loss (that is usually being minimized) is exactly zero.
Remark 1.4 “will result in an expected loss..”  (there is also a typo here) should specify that you are talking about empirical error (0-1 loss), since I don’t think the loss function is fixed anywhere earlier in the text.
Remark 2.2 : Just wanted to note, that it is more common to call L(u,\rho) risk. The gap between L(u,\rho) and the empirical risk L(u,\rho_n) is usually called the generalization error (and only in the case of zero empirical risk, L(u,\rho) is equal to the generalization error). I did check the reference in Goodfellow et al. book, and I see that it is consistent with your definition.
Just below Remark 2.2:
“We would also expect the sequence of generalization losses L[u_n ; \rho] to converge to zero in the case of perfect generalization.”
Once again, this is true only in the realizable setting.
Could the authors comment on the connection to Cranko et al. 2018 work?
Typos:
In the abstract, no which: “..corrupted labels which we prove convergence to...”
“...a candidate measure for the Rademacher complexity, which a measure of generalization...”.
“1-Lipschitz networks with are also important for Wasserstein-GANs”
Section 2.1 “is it clear that u0, is a solution of “, should be “it is”
---------
[UPDATE]
Regarding the comment "Our paper resolves the question posed in ICLR Best paper 2017 "Understanding deep learning requires rethinking generalization"", I don't think that analyzing networks with explicit regularization resolves the questions stated in Zhang et al paper. As other reviewers mentioned, there are a number of other papers that formally define quantities that correlate with the generalization error, and are larger for random vs true labels. There are also other papers showing that one can tune some parameters of the optimization algorithm to avoid overfitting on random labels (while it is a modification to the algorithm, it is still similar to explicitly regularizing the Lipschitz constant of the network) (see e.g., Dziugaite et al work on SGLD).
Therefore, the claim in the abstract "A second result resolves a question posed in Zhang et al. (2016): how can a model distinguish between the case of clean labels, and randomized labels?" needs to be toned down a bit.
In my opinion, the work presented in this paper is a valuable contribution to learning theory. The new version of the paper is easy to read. Therefore, I recommend acceptance if the authors change the claim about resolving  the questions posed by Zhang et al.
Another typo:
 - for convergence, we require that the network also grow(s),