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.   While deep neural networks networks (DNNs) give more accurate predictions than other machine learning methods BID30 , they lack some of the performance guarantees of these other methods. One step towards performance guarantees for DNNs is a proof of generalization with a rate. In this paper, we present such a result, for Lipschitz regularized DNNs. In fact, we prove a stronger convergence result from which generalization follows.We also consider the following problem, inspired by (Zhang et al., 2016) . Problem 1.1. [Learning from dirty data] Suppose we are given a labelled data set, which has Lipschitz constant Lip(D) = O(1) (see (3) below). Consider making copies of 10 percent of the data, adding a vector of norm to the perturbed data points, and changing the label of the perturbed points. Call the new, dirty, data setD. The dirty data has Lip(D) = O(1/ ). However, if we compute the histogram of the pairwise Lipschitz constants, the distribution of the values on the right hand side of (3), are mostly below Lip(D) with a small fraction of the values being O(1/ ), since the duplicated images are apart but with different labels. Thus we can solve (1) with L 0 estimate using the prevalent smaller values, which is an accurate estimate of the clean data Lipschitz constant. The solution of (1) using such a value is illustrated on the right of Figure 1 . Compare to the Tychonoff regularized solution on the right of Figure 2 . We hypothesis that on dirty data the solution of (1) replaces the thin tall spikes with short fat spikes leading to better approximation of the original clean data.In Figure 1 we illustrate the solution of (1) (with L 0 = 0), using synthetic one dimensional data. In this case, the labels {−1, 0, 1} are embedded naturally into Y = R, and λ = 0.1. Notice that the solution matches the labels exactly on a subset of the data. In the second part of the figure, we show a solution with dirty labels which introduce a large Lipschitz constant, in this case, the solution reduces the Lipschitz constant, thereby correcting the errors.Learning from dirty labels is studied in §2.4. We show that the model learns a different function than the dirty label function. We conjecture, based on synthetic examples, that it learns a better approximation to the clean labels.We begin by establishing notation. Consider the classification problem to fix ideas, although our restuls apply to other problems as well. Definition 1.2. Let D n = x 1 , . . . , x n be a sequence of i.i.d. random variables sampled from the probability distribution ρ. The data x i are in X = [0, 1] d . Consider the classification problem with D labels, and represent the labels by vertices of the probability simplex, Y ⊂ R D . Write y i = u 0 (x i ) for the map from data to labels. Write u(x; w) for the map from the input to data to the last layer of the network.1 Augment the training loss with Lipschitz regularization DISPLAYFORM0 The first term in (1) is the usual average training loss. The second term in (1) the Lipschitz regularization term: the excess Lipschitz constant of the map u, compared to the constant L 0 .In order to apply the generalization theorem, we need to take L 0 ≥ Lip(u 0 ), the Lipschitz constant of the data on the whole data manifold. In practice, Lip(u 0 ) can be estimated by the Lipschitz constant of the empirical data. The definition of the Lipschitz constants for functions and data, as well as the implementation details are presented in §1.3 below.Figure 1: Synthetic labelled data and Lipschitz regularized solution u. Left : The solution value matches the labels exactly on a large portion of the data set. Right : dirtly labels: 10% of the data is incorrect; the regularized solution corrects the errors.Our analysis will apply to the problem (1) which is convex in u, and does not depend explicitly on the weights, w. Of course , once u is restricted to a fixed neural network architecture, the corresponding minimization problem becomes non-convex in the weights. Our analysis can avoid the dependence on the weights because we make the assumption that there are enough parameters so that u can exactly fit the training data. The assumption is justified by Zhang et al. (2016) . As we send n → ∞ for convergence, we require that the network also grow, in order to continue to satisfy this assumption. Our results apply to other non-parametric methods in this regime.
We prove generalization of DNNs by adding a Lipschitz regularization term to the training loss. We resolve a question posed in Zhang et al. (2016).
{"src": "scitldr-AIC_train", "paper_id": "r1l3NiCqY7"}