Title: LIPSCHITZ REGULARIZED DEEP NEURAL NETWORKS

Abstract: 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.
1 We apologize for not using the standard notation f for the last layer!

1. INTRODUCTION:

While deep neural networks networks (DNNs) give more accurate predictions than other machine learning methods (LeCun et al., 2015) , 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 set D. 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

min u:X→Y J n [u] = 1 n n 󰁛 i=1 ℓ(u(x i ; w), y i ) + λ max(Lip(u) -L 0 , 0) (1)

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. 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.

1.1. RELATED WORK AND APPLICATIONS:

Generalization bounds have been obtained previously via VC dimension analysis of neural networks (Bartlett, 1997). The generalization rates have factors of the form A k for a k-layer neural network with bounds 󰀂w i 󰀂 ≤ A for all weight vectors w i in the network. Such bounds are only applicable for low-complexity networks. Other works have considered connections between generalization and stability (Bousquet & Elisseeff, 2002; Xu & Mannor, 2012) . More recently, (Bartlett et al., 2017) proposed the Lipschitz constant of the network as a candidate measure for the Rademacher complexity, which is a measure of generalization (Shalev-Shwartz & Ben-David, 2014, Chapter 26) . Also, Cranko et al. (2018) showed that Lipschitz regularization can be viewed as a special case of distributional robustness. Unlike other recent contributions such as (Hardt et al., 2015) , our analysis does not depend on the training method. In fact, our analysis has more in common with inverse problems in image processing, such as Total Variation denoising and inpainting (Bertalmio et al., 2000; Rudin et al., 1992) . For further discussion, see Appendix C.

The estimate of Lip(u; X) provided by ( 4) can be quite different from the the Tychonoff gradient regularization (Drucker & Le Cun, 1992) ,

1 |I| 󰁛 i∈I 󰀂∇ x u(x i )󰀂 2

since (4) corresponds to a maximum of the values of the norms, and the previous equation corresponds to the mean-squared values. In fact, recent work on semi-supervised learning suggests that higher p-norms of the gradient are needed for generalization when the data manifold is not well approximated by the data (El Alaoui et al., 2016; Calder, 2017; Kyng et al., 2015; Slepcev & Thorpe, 2017) . In Figure 2 we compare to the problems in Figure 1 using Tychonoff regularization. The Tychonoff regularization is less effective at correcting errors. The effect is more pronounced in higher dimensions.

Figure 2 : Synthetic labelled data and Tychonoff regularized solution u. Left: The solution value matches the labels exactly on a large portion of the data set. Right dirty labels: 10% of the data is incorrect; the regularized solution is not as effective at correcting errors. The effect is more pronounced in higher dimensions.

1.2. RELATED WORK ON LIPSCHITZ REGULARIZATION:

An upper bound for the Lipschitz constant of the model is given by the norm of the product of the weight matrices (Szegedy et al., 2013, Section 4.3) . Let w = (w 1 , . . . , w J ) be the weight matrices for each layer. Then Lip(u; X) ≤ Π J j=1 󰀂w i 󰀂.

(2)

Regularization of the network using methods based on (2) has been implemented recently in (Gouk et al., 2018) and (Yoshida & Miyato, 2017) . Because the upper bound in (2) does not take into account the coefficients in weight matrices which are zero due to the activation functions, the gap in the inequality can be off by factors of many orders of magnitude for deep networks (Finlay & Oberman, 2018) .

Implementing (4) can be accomplished using backpropagation in the x variable on each label, which can become costly for D large. Special architectures could also be used to implement Lipschitz regularization, for example, on a restricted architecture, Liao et al. (2018) renormalized the weight matrices of each layer to be norm 1.

Lipschitz regularization may help with adversarial examples (Szegedy et al., 2013) (Goodfellow et al., 2014) which poses a problem for model reliability (Goodfellow et al., 2018) . Since the Lipschitz constant L ℓ of the loss, ℓ, controls the norm of a perturbation

󰀂ℓ(u(x i + 󰂃v)) -ℓ(u(x i ))󰀂 Y ≤ 󰂃L ℓ 󰀂v󰀂 X

maps with smaller Lipschitz constants may be more robust to adversarial examples. Finlay & Oberman (2018) implemented Lipschitz regularization of the loss, and achieved better robustness against adversarial examples, compared to adversarial training (Goodfellow et al., 2014) alone.

Lipschitz regularization may also improve stability of GANs. 1-Lipschitz networks are also important for Wasserstein-GANs (Arjovsky et al., 2017) (Arjovsky & Bottou, 2017) . In (Wei et al., 2018) the gradient penalty away from norm 1 is implemented, augmented by a penalty around perturbed points, with the goal of improved stability. Spectral regularization for GANs was implemented in (Miyato et al., 2018) .

1.3. LIPSCHITZ CONSTANTS AND IMPLEMENTATION:

Definition 1.3 (Lipschitz constants of functions and data). Choose norms 󰀂 • 󰀂 Y , and 󰀂 • 󰀂 X on X and Y , respectively. The Lipschitz constant (in these norms) of a function u :

X 0 ⊂ X → Y is given by Lip(u; X 0 ) = sup x1,x2∈X0 󰀂u(x 1 ) -u(x 2 )󰀂 Y 󰀂x 1 -x 2 󰀂 X When X 0 is all of X, we write Lip(u; X) = Lip(u).

The Lipschitz constant of the data is given by

EQUATION

Finlay & Oberman (2018) implement Lipschitz regularization as follows. The basis for the implementation of the Lipschitz constant is Rademacher's Theorem (Evans, 2018, §3.1) , which states that if a function g(x) is Lipschitz continuous then it is differentiable almost everywhere and Lip(g) = max x 󰀂∇g(x)󰀂.

Restricting to a mini-batch, we obtain the following method for estimating the Lipschitz constant. Let u(x; w) be a Lipschitz continuous function. Then

EQUATION

For vector valued functions, the appropriate matrix norm must be used, see §B.

2. LIPSCHITZ REGULARIZATION AND CONVERGENCE:



2.1. LIMITING PROBLEM:

The variational problem (1) admits Lipschitz continuous minimizers, but in general the minimizers are not unique. When L 0 = Lip(u 0 ), it is clear that u 0 , is a solution of (1): both the loss term and the regularization term are zero when applied to u 0 . In addition, any L 0 -Lipschitz extension of u 0 | Dn is also a minimizer of (1), so solutions are not unique.

Let u n be any solution of the Lipschitz regularized variational problem (1). We study the limit of u n as n → ∞. Since the empirical probability measures ρ n converge to the data distribution ρ, the continuum variational problem corresponding to (1) is min

EQUATION

where in (5) we have introduced the following notation. Definition 2.1. Given the loss function, ℓ, a map u : X → Y , and a probability measure, µ, supported on X, define

L[u, µ] = E x∼µ [ℓ(u(x), u 0 (x))] = 󰁝 X ℓ(u(x), u 0 (x))dµ(x)

to be the expectation of the loss with respect to the measure. In particular, the generalization loss of the map u :

X → Y is given by L[u, ρ]. Write L[u, D n ] := L[u, ρ n ]

for the average loss on the data set D n , where ρ n := 1 n 󰁓 δ xi is the empirical measure corresponding to D n . Remark 2.2. Generalization is defined in (Goodfellow et al., 2016, Section 5. 2) as the expected value of the loss function on a new input sampled from the data distribution. As defined, the full generalization error includes the training data, but it is of measure zero, so removing it does not change the value.

2.2. LOSS FUNCTION ASSUMPTIONS:

We introduce the following assumption on the loss function.

Assumption 2.3 (Loss function). The function ℓ:

: Y × Y → R is a loss function if it satisfies (i) ℓ ≥ 0, (ii) ℓ(y 1 , y 2 ) = 0 if and only if y 1 = y 2 , and (iii) ℓ is strictly convex in y 1 .

Example 2.4 (R D with L 2 loss). Set Y = R D , and let each label be a basis vector. Set ℓ(y 1 , y 2 ) = 󰀂y 1 -y 2 󰀂 2 2 to be the L 2 loss. Example 2.5 (Classification). In classification, the output of the network is a probability vector on the labels. Thus Y = ∆ D , the D-dimensional probability simplex, and each label is mapped to a basis vector. The cross-entropy loss ℓ KL (y, z) = -󰁓 D i=1 z i log(y i /z i ). For labels, ℓ KL (y, e k ) = -log(y k ). Example 2.6 (Regularized cross-entropy). In the classification setting, it is often the case that the softmax function softmax(z

) j = e zj 󰁓 D k=1 e z k (6)

is combined with the cross-entropy loss. In this paper, we regard softmax as the last layer of the DNN, so we assume the output u(x) of the network lies in the probability simplex. If the output, z, of the second to last layer of the DNN, which is the input to softmax in ( 6), lies in a compact set, i.e., |z j | ≤ C for all i and some C > 0, then softmax(z) j ≥ e -2C , and so the range of softmax lies in the set

A := {y ∈ R D : y i ≥ e -2C and y 1 + • • • + y D = 1},

which is strictly interior to the probability simplex. Restricted to A, the cross-entropy loss ℓ KL is strongly convex and Lipschitz continuous, which is required in Theorems 2.12 and 2.11 below.

In our analysis, it is slightly more convenient to define the regularized cross entropy loss with parameter 󰂃 > 0

ℓ KL 󰂃 (y, z) = - D 󰁛 i=1 (z i + 󰂃) log 󰀕 y i + 󰂃 z i + 󰂃 󰀖 .

For classification problems, where z = e k , we have ℓ KL 󰂃 (y, e k ) = -(1 + 󰂃) log((y k + 󰂃)/(1 + 󰂃)), which is Lipschitz and strongly convex for any 0 ≤ y i ≤ 1 within the probability simplex. Thus, the regularized cross entropy ℓ KL 󰂃 satisfies the strong convexity and Lipschitz regularity required by Theorems 2.12 and 2.11 on the whole probability simplex.

2.3. GENERALIZATION RESULT:

Here, we show that solutions of the random variational problem (1) converge to solutions of (5). We make the standard manifold assumption (Chapelle et al., 2006) , and assume the data distribution ρ is a probability density supported on a compact, smooth, m-dimensional manifold M embedded in X = [0, 1] d , where m ≪ d. We denote the probability density again by ρ : M → [0, ∞). Hence, the data D n is a sequence x 1 , . . . , x n of i.i.d. random variables on M with probability density ρ. Associated with the random sample we have the closet point projection map

σ n : X → {x 1 , . . . , x n } ⊂ X that satisfies 󰀂x -σ n (x)󰀂 X = min 1≤i≤n {󰀂x -x i 󰀂 X }

for all x ∈ X. We recall that W 1,∞ (X; Y ) is the space of Lipschitz mappings from X to Y . Throughout this section, C, c > 0 denote positive constants depending only on M, and we assume C ≥ 1 and 0 < c < 1. We follow the analysis tradition of allowing the particular values of C and c to change from line to line.

We establish that that minimizers of (5) are unique on M in Theorem A.1, which follows from the strict convexity of the loss restricted to the data manifold M. See also Figure 3 which shows how the solutions need not be unique off the data manifold.

Our first result is in the case where Lip[u 0 ] ≤ L 0 , and so the Lipschitz regularizer is not fully active. This corresponds to the case of clean labels. We state our result in generality, for approximate minimizers of (1), and specialize to the case Lip[u 0 ] ≤ L 0 in Remark 2.8. Theorem 2.7 (Convergence result). Assume inf x∈M ρ(x) > 0. For any t > 0, with probability at least 1 -Ct -1 n -(ct-1) every sequence

u n ∈ W 1,∞ (X; Y ) with zero empirical loss L[u 0 , ρ n ] = 0 satisfies 󰀂u 0 -u n 󰀂 L ∞ (M;Y ) ≤ C(L 0 + Lip[u n ]) 󰀕 t log(n) n 󰀖 1/m . Remark 2.8. If u n ∈ W 1,∞ (X; Y ) is any sequence of minimizers of (1) and Lip[u 0 ] ≤ L 0 , then J[u n ] ≤ J[u 0 ] = 0. Thus, Lip[u n ]

≤ L 0 and Theorem 2.7 applies to the sequence u n , yielding

󰀂u 0 -u n 󰀂 L ∞ (M;Y ) ≤ CL 0 󰀕 t log(n) n 󰀖 1/m .

It is important to note that Theorem 2.7 does not requires u n to be minimizers of (1)-we just require zero empirical loss, which is often achieved in practice (Zhang et al., 2016) . This allows for approximation errors in solving (1) on the whole domain X, due to the restriction that u must be expressed via a Deep Neural Network.

As an immediate corollary, we can prove that the generalization loss converges to zero, and so we obtain generalization. Corollary 2.9. Assume that for some q ≥ 1 the loss ℓ satisfies ℓ(y, y 0 ) ≤ C󰀂y -y 0 󰀂 q Y for all y 0 , y ∈ Y.

Then under the assumptions of Theorem 2.7

L[u n , ρ] ≤ C(L 0 + Lip[u n ]) q 󰀕 t log(n) n 󰀖 q/m

holds with probability at least 1 -Ct -1 n -(ct-1) .

Proof. By (7), we can bound the generalization loss as follows

L[u n , ρ] = 󰁝 M ℓ(u n (x), u 0 (x))ρ(x) dV ol(x) ≤ C󰀂u n -u 0 󰀂 q L ∞ (M;Y ) .

The proof is completed by invoking Theorem 2.7.

We now turn to the proof of Theorem 2.7, which requires a bound on the distance between the closest point projection σ n and the identity. The result is standard in probability, and we include it for completeness in Lemma 2.10 proved in §A.1. We refer the interested reader to (Penrose et al., 2003) for more details. Lemma 2.10. Suppose that inf M ρ > 0. Then for any t > 0

󰀂Id -σ n 󰀂 L ∞ (M;X) ≤ C 󰀕 t log(n) n 󰀖 1/m

with probability at least 1 -Ct -1 n -(ct-1) .

We now give the proof of Theorem 2.7.

Proof of Theorem 2.7. Since L[u n , ρ n ] = 0 we have u 0 (x i ) = u n (x i ) for all 1 ≤ i ≤ n. Thus for any x ∈ X we have

󰀂u 0 (x) -u n (x)󰀂 Y = 󰀂u 0 (x) -u 0 (σ n (x)) + u 0 (σ n (x)) -u n (σ n (x)) + u n (σ n (x)) -u n (x)󰀂 Y ≤ 󰀂u 0 (x) -u 0 (σ n (x))󰀂 Y + 󰀂u n (σ n (x)) -u n (x)󰀂 Y ≤ (L 0 + Lip[u n ])󰀂x -σ n (x)󰀂 X .

Therefore, we deduce

󰀂u 0 -u n 󰀂 L ∞ (M;Y ) ≤ (L 0 + Lip[u n ])󰀂Id -σ n 󰀂 L ∞ (M;X) .

The proof is completed by invoking Lemma 2.10.

Figure 3 : On the data manifold there is only one minimizer. Off the data manifold, there can be multiple minimizers.

2.4. CONVERGENCE FOR DIRTY LABELS:

We now consider the setting of Problem 1.1, illustrated in Figure 1 right. We assume that we only have access to a "dirty" label function, which corresponds to an additive error of the form

u 0 = u clean + u e

where u clean is the label function, and u e : X → Y is some error function, which is assumed to be zero with high probability. Assume that the error vector e has a much larger Lipschitz constant than the labels, so that Lip(u 0 ) ≫ Lip(u clean ).

We wish to fit the clean labels, while not fitting the errors, having access only to u 0 . The labels correspond to the subset of the data which generate the low Lipschitz constant L clean , while the errors correspond to pairs of labels that generate a high Lipschitz constant. Thus L clean can easily be estimated from the distribution of the pairwise Lipschitz constants of the data. With the goal in mind, we set L 0 = L clean in (1). The Lipschitz regularizer is active in (1), which can lead to the solution succeeding in avoiding the dirty labels, as in Figure 1 right.

Our main results (Theorems 2.12 and 2.11) show that minimizers of J n converge to minimizers of J almost surely as the number of training points n tends to ∞. It is beyond the scope of this work to estimate to what extent the errors are corrected, however we do know that the solution cannot fit u 0 due to the value of the Lipschitz constant, which is already an improvement over the case λ = 0.

The proofs for this section can be found in Section A.2. Theorem 2.11. Suppose that ℓ : Y × Y → R is Lipschitz and strongly convex and let L = Lip(u 0 ). Then for any t > 0, with probability at least 1 -2t -m m+2 n -(ct-1) all minimizing sequences u n of (1) and all minimizers u * of (5) satisfy

θ 2 󰁝 M 󰀂u n -u * 󰀂 2 Y ρ dV ol(x) ≤ CL 󰀕 t log(n) n 󰀖 1 m+2 .

The next result drops the assumption of strong convexity of the loss. Theorem 2.12. Suppose that inf M ρ > 0, ℓ : Y × Y → R is Lipschitz, and let u * ∈ W 1,∞ (X; Y ) be any minimizer of (5). Then with probability one

EQUATION

where u n is any sequence of minimizers of (1). Furthermore, every uniformly convergent subsequence of u n converges on X to a minimizer of (5). Remark 2.13. In Theorem 2.12 and Theorem 2.11, the sequence u n does not, in general, converge on the whole domain X. The important point is that the sequence converges on the data manifold M, and solves the variational problem (5) off of the manifold, which ensures that the output of the DNN is stable with respect to the input. See Figure 3 .

AN Tikhonov and V Ya Arsenin. 

A PROOFS:



A.1 PROOFS FOR CLEAN LABELS:

In this section we provide the proof of results stated in §2.3. Theorem A.1. Suppose the loss function satisfies Assumption 2.3. If u, v ∈ W 1,∞ (X; Y ) are two minimizers of (5) and inf M ρ > 0 then u = v on M.

Proof. Let w = (u + v)/2. Then J[w] = 󰁝 M ℓ 󰀃 1 2 u + 1 2 v, u 0 󰀄 ρ dV ol(x) + λ max 󰀃 Lip 󰀃 1 2 u + 1 2 v 󰀄 , 0 󰀄 ≤ 󰁝 M 󰀅 1 2 ℓ (u, u 0 ) + 1 2 ℓ (v, u 0 ) 󰀆 ρ dV ol(x) + λ max 󰀃 1 2 Lip (u) + 1 2 Lip (v) , 0 󰀄 ≤ 󰁝 M 󰀅 1 2 ℓ (u, u 0 ) + 1 2 ℓ (v, u 0 ) 󰀆 ρ dV ol(x) + λ 󰀅 1 2 max (Lip (u) , 0) + 1 2 max (Lip (v) , 0) 󰀆 = 1 2 J[u] + 1 2 J[v] = min u J[u].

Therefore, w is a minimizer of J and so we have equality above, which yields

󰁝 M 󰀅 1 2 ℓ (u, u 0 ) + 1 2 ℓ (v, u 0 ) 󰀆 ρ dV ol(x) = 󰁝 M ℓ 󰀃 1 2 u + 1 2 v, u 0 󰀄 ρ dV ol(x).

Since ℓ is strictly convex in its first argument, it follows that u = v on M.

Proof of Lemma 2.10 of §2.3. There exists 󰂃 M such that for any 0 < 󰂃 ≤ 󰂃 M , we can cover M with N geodesic balls B 1 , B 2 , . . . , B N of radius 󰂃, where N ≤ C󰂃 -m and C depends only on M (Györfi et al., 2006) . Let Z i denote the number of random variables x 1 , . . . , x n falling in B i . Then Z i ∼ B(n, p i ), where p i = 󰁕 Bi ρ(x) dV ol(x). Since ρ ≥ θ > 0 and V ol(B i ) ≥ c󰂃 m we have p i ≥ c󰂃 m . Let A n denote the event that at least one B i is empty (i.e., Z i = 0 for some i). Then by the union bound we deduce

P(A n ) ≤ N 󰁛 i=1 P (Z i = 0) ≤ C󰂃 -d (1 -c󰂃 m ) n = C exp (n log(1 -c󰂃 m ) -log(󰂃 m )) ≤ C exp (-cn󰂃 m -log(󰂃 m )) . Choose 0 < 󰂃 ≤ 󰂃 M in the form n󰂃 m = t log(n) with t ≤ n󰂃 m M / log(n). Then P(A n ) ≤ Ct -1 exp (-(ct -1) log(n)) .

In the event that A n does not occur, then each B i has at least one point, and so |x -

σ n (x)| ≤ C󰂃 for all x ∈ M. Therefore 󰀂Id -σ n 󰀂 L ∞ (M;X) ≤ C󰂃 = C 󰀕 t log(n) n 󰀖 1/m with probability at least 1 -Ct -1 exp (-(ct -1) log(n)). Since 󰀂Id -σ n 󰀂 L ∞ (M;X) ≤ C √ d, the result holds for t ≥ n󰂃 m

M / log(n), albeit with a larger constant C.

A.2 PROOFS FOR DIRTY LABELS:

Here, we give the proofs of results from Section 2.4. Definition A.2. We say that ℓ is strongly convex with parameter θ > 0 if

ℓ(ty 1 + (1 -t)y 2 , y 0 ) + θ 2 t(1 -t)󰀂y 1 -y 2 󰀂 2 Y ≤ tℓ(y 1 , y 0 ) + (1 -t)ℓ(y 2 , y 0 ) (9)

for all y 0 , y 1 , y 2 ∈ Y and 0 ≤ t ≤ 1.

We note that when ℓ is twice differentiable, this notion of strong convexity is equivalent to assuming ∇ 2 y1 ℓ ≥ θI. The definition in equation ( 9) is useful for non-smooth functions, such as the Lipschitz semi-norm present in J[u].

We give a proposition useful in the proof of Lemma A.4. Proposition A.3. If ℓ is strongly convex with parameter θ > 0 then

J[tu 1 + (1 -t)u 2 ] + θ 2 t(1 -t) 󰁝 M 󰀂u 1 -u 2 󰀂 2 Y ρ dV ol(x) ≤ tJ[u 1 ] + (1 -t)J[u 2 ] for all u 1 , u 2 ∈ W 1,∞ (X; Y ) and 0 ≤ t ≤ 1.

Proof. We compute

J[tu 1 + (1 -t)u 2 ] = 󰁝 M ℓ(tu 1 + (1 -t)u 2 , u 0 )ρ dV ol(x) + λ max (Lip(tu 1 + (1 -t)u 2 ), 0) ≤ tJ[u 1 ] + (1 -t)J[u 2 ] - θ 2 t(1 -t) 󰁝 M 󰀂u 1 -u 2 󰀂 2 Y ρ dV ol(x),

which completes the proof.

Before proving Theorem 2.11, we require a preliminary lemma.

Lemma A.4. If u * ∈ W 1,∞ (X; Y ) is a minimizer of (5) and u ∈ W 1,∞ (X; Y ) then θ 2 󰁝 M 󰀂u -u * 󰀂 2 Y ρ dV ol(x) ≤ J[u] -J[u * ].

Proof. We use Proposition A.3 with u 1 = u * and u 2 = u to obtain

J[tu * + (1 -t)u] + θ 2 t(1 -t) 󰁝 M 󰀂u * -u󰀂 2 Y ρ dV ol(x) ≤ tJ[u * ] + (1 -t)J[u]. Since J[tu * + (1 -t)u] ≥ J[u * ] J[u * ] + θ 2 t(1 -t) 󰁝 M 󰀂u * -u󰀂 2 Y ρ dV ol(x) ≤ tJ[u * ] + (1 -t)J[u],

and so

θ 2 t 󰁝 M 󰀂u * -u󰀂 2 Y ρ dV ol(x) ≤ J[u] -J[u * ].

Setting t = 1 completes the proof.

The proof of Theorem 2.12 requires a preliminary Lemma. Let H L (X; Y ) denote the collection of L-Lipschitz functions w : X → Y . Lemma A.5. Suppose that inf M ρ > 0, and dim(M) = m. Then for any t > 0 sup

EQUATION

)

holds with probability at least 1 -2t -m m+2 n -(ct-1) .

The estimate ( 10) is called a discrepancy result (Talagrand, 2006; Györfi et al., 2006) , and is a uniform version of concentration inequalities.

A key tool in the proof of Lemma A.5 is Bernstein's inequality (Boucheron et al., 2013) , which we recall now for the reader's convenience. For X 1 , . . . , X n i.i.d. with variance

σ 2 = E[(X i -E[X i ]) 2 ], if |X i | ≤ M almost

surely for all i then Bernstein's inequality states that for any 󰂃 > 0

P 󰀣󰀏 󰀏 󰀏 󰀏 󰀏 1 n n 󰁛 i=1 X i -E[X i ] 󰀏 󰀏 󰀏 󰀏 󰀏 > 󰂃 󰀤 ≤ 2 exp 󰀕 - n󰂃 2 2σ 2 + 4M 󰂃/3 󰀖 .

Proof of Lemma A.5. We note that it is sufficient to prove the result for w ∈ H L (X; Y ) with 󰁕 M wρ dV ol(x) = 0. In this case, we have w(x) = 0 for some x ∈ M, and so 󰀂w󰀂 L ∞ (X;Y ) ≤ CL.

We first give the proof for M = X = [0, 1] m . We partition X into hypercubes B 1 , . . . , B N of side length h > 0, where N = h -m . Let Z j denote the number of x 1 , . . . , x n falling in B j . Then Z j is a Binomial random variable with parameters n and p j = 󰁕 Bj ρ dx ≥ ch m . By the Bernstein inequality we have for each j that

EQUATION

provided 0 < 󰂃 ≤ h m . Therefore, we deduce 

EQUATION

󰁝 Bj ρ dx + CLh -m 󰂃 ≤ N 󰁛 j=1 󰁝 Bj wρ dx + CLh -m (h m+1 + 󰂃) = 󰁝 X wρ dx + CL(h + h -m 󰂃)

holds with probability at least 1-2h We sketch here how to prove the result on the manifold M. We cover M with k geodesic balls of radius 󰂃 > 0, denoted B M (x 1 , 󰂃), . . . , B M (x k , 󰂃), and let ϕ 1 , . . . , ϕ k be a partition of unity subordinate to this open covering of M. For 󰂃 > 0 sufficiently small, the Riemannian exponential map exp x : B(0, 󰂃) ⊂ T x M → M is a diffeomorphism between the ball B(0, r) ⊂ T x M and the geodesic ball B M (x, 󰂃) ⊂ M, where T x M ∼ = R m . Furthermore, the Jacobian of exp x at v ∈ B(0, r) ⊂ T x M, denoted by J x (v), satisfies (by the Rauch Comparison Theorem)

(1 + C|v| 2 ) -1 ≤ J x (v) ≤ 1 + C|v| 2 .

Therefore, we can run the argument above on the ball B(0, r) ⊂ R m in the tangent space, lift the result to the geodesic ball B M (x i , 󰂃) via the Riemannian exponential map exp x , and apply the bound 󰀏 󰀏 󰀏 󰀏 󰀏

1 n n 󰁛 i=1 w(x i ) - 󰁝 M wρ dV ol(x) 󰀏 󰀏 󰀏 󰀏 󰀏 ≤ k 󰁛 j=1 󰀏 󰀏 󰀏 󰀏 󰀏 1 n n 󰁛 i=1 ϕ j (x i )w(x i ) - 󰁝 M ϕ j wρ dV ol(x) 󰀏 󰀏 󰀏 󰀏 󰀏

to complete the proof.

Remark A.6. The exponent 1/(m + 2) is not optimal, but affords a very simple proof. It is possible to prove a similar result with the optimal exponent 1/m in dimension m ≥ 3, but the proof is significantly more involved. We refer the reader to (Talagrand, 2006) for details.

Remark A.7. The proof of Theorem 2.12 shows that (1) Γ-converges to (5) almost surely as n → ∞ in the L ∞ (X; Y ) topology. Γ-convergence is a notion of convergence for functionals that ensures minimizers along a sequence of functionals converge to a minimizer of the Γ-limit. While we do not use the language of Γ-convergence here, the ideas are present in the proof of Theorem 2.12. We refer to (Braides, 2002) for details on Γ-convergence.

Proof of Theorem 2.12. By Lemma A.5 the event that lim

EQUATION

for all Lipschitz constants L > 0 has probability one. For the rest of the proof we restrict ourselves to this event.

Let u n ∈ W 1,∞ (X; Y ) be a sequence of minimizers of (1), and let u * ∈ W 1,∞ (X; Y ) be any minimizer of (5). Then since

λ(Lip(u n ) -L 0 ) ≤ J n [u n ] ≤ J n [u 0 ] = λ(Lip(u 0 ) -L 0 ) we have Lip(u n ) ≤ Lip(u 0 ) =: L for all n.

By the Arzelà-Ascoli Theorem (Rudin, 1976) there exists a subsequence u nj and a function u ∈ W 1,∞ (X; Y ) such that u nj → u uniformly as n j → ∞. Note we also have Lip

(u) ≤ lim inf j→∞ Lip(u nj ). Since |L[u n , ρ n ] -L[u, ρ]| ≤ |L[u n , ρ n ] -L[u, ρ n ]| + |L[u, ρ n ] -L[u, ρ]| ≤ C󰀂u n -u󰀂 L ∞ (M;Y ) + sup w∈H L (X;Y ) |L[w, ρ n ] -L[w, ρ]| it follows from (12) that L[u nj , ρ nj ] → L[u, ρ] as j → ∞. It also follows from (12) that J n [u * ] → J[u * ] as n → ∞. Therefore J[u * ] = lim n→∞ J n [u * ] ≥ lim inf n→∞ J n [u n ] = lim inf n→∞ L[u n , ρ n ] + λ max(Lip(u n ) -L 0 , 0) = lim n→∞ L[u n , ρ n ] + lim inf n→∞ λ max(Lip(u n ) -L 0 , 0) ≥ L[u, ρ] + λ max(Lip(u) -L 0 , 0) = J[u].

Therefore, u is a minimizer of J. By Theorem A.1, u = u * on M, and so u nj → u * uniformly on M as j → ∞. Now, suppose that (8) does not hold. Then there exists a subsequence u nj and δ > 0 such that

max x∈M |u nj (x) -u * (x)| > δ

for all j ≥ 1. However, we can apply the argument above to extract a further subsequence of u nj that converges uniformly on M to u * , which is a contradiction. This completes the proof.

Proof of Theorem 2.11. Let L = Lip(u 0 ). By Lemma A.5

EQUATION

holds with probability at least 1 -2t -m m+2 n -(ct-1) for any t > 0. Let us assume for the rest of the proof that (13) holds.

As in the proof of Theorem 2.12, we have Lip(u n ) ≤ L and Lip(u * ) ≤ L, and so

|J n [u * ] -J[u * ]| , |J n [u n ] -J[u n ]| ≤ CL 󰀕 t log(n) n 󰀖 1 m+2 . Therefore J[u n ] -J[u * ] = J n [u n ] -J[u * ] + J[u n ] -J n [u n ] ≤ CL 󰀕 t log(n) n 󰀖 1 m+2 . By Lemma A.4 we deduce θ 2 󰁝 M 󰀂u n -u * 󰀂 2 Y ρ dV ol(x) ≤ CL 󰀕 t log(n) n 󰀖 1 m+2 ,

which completes the proof.

B INDUCED MATRIX NORMS:

In some cases, we can take advantage of explicit formulas for matrix norms, which makes the estimates in (2) an explicit function of the weights. Define the induced matrix norm by 󰀂M 󰀂 p,q = sup x 󰀂M x󰀂 q 󰀂x󰀂 p Then the following matrix norms formulas hold (see (Horn et al., 1990, Chapter 5.6.4 )) (LE) is not practical for large scale problems. There has be extensive work on the Lipschitz Extension problem, see, (Johnson & Lindenstrauss, 1984) , for example. More recently, optimal Lipschitz extensions have been studied, with connections to Partial Differential Equations, see (Aronsson et al., 2004) . We can interpret (1) as a relaxed version of (LE), where λ -1 is a parameter which replaces the unknown Lagrange multiplier for the constraint.

󰀂M 󰀂 ∞,∞ = max i 󰁛 j |m ij |, 󰀂M 󰀂 1,1 = max j 󰁛 i |m ij | 󰀂M 󰀂 1,∞ = max

Variational problems are fundamental tools in mathematical approaches to image processing (Aubert & Kornprobst, 2006) and inverse problems more generally. Without regularization inverse problems can be ill-posed. The general form of the problem is

EQUATION

which combines a loss or fidelity functional, L[u, u 0 ], which depends on the values of u and the reference image u 0 , and a regularization functional, R[∇u], which depends on the gradient, ∇u.

The parameter λ determines the relative strength of the two terms which emphasize fidelity versus regularization.

Example C.1. For example, a typical fidelity term is the standard least-squares L[u, u 0 ] = 󰀂uu 0 󰀂 2 L 2 (D) . The regularization 󰀂|∇u(x)|󰀂 2 L 2 (D) corresponds to the classical Tychonov regularization (Tikhonov & Arsenin, 1977) , R[∇u] = 󰀂|∇u(x)|󰀂 L 1 (D) is the Total Variation regularization model of Rudin, Osher and Fatemi (Rudin et al., 1992) .

Lipschitz regularization in not nearly as common. It appears in image processing in (Pock et al., 2010, §4.4 ) (Elion & Vese, 2007) and (Guillot & Le Guyader, 2009) . Variational problems of the form ( 14) can be studied by the direct method in the calculus of variations (Dacorogna, 2007) . The problem ( 14) can be discretized to obtain a finite dimensional convex convex optimization problem. The variational problem can also be studied by finding the first variation, which is a Partial Differential Equation (Evans, 1998) , which can then be solved numerically. Both approaches are discussed in (Aubert & Kornprobst, 2006) .

In Figure 4 we compare different regularization terms, in one dimension. The difference between the regularizers is more extreme in higher dimensions.

:



Figures and Tables:

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.

Figure 4: Comparison of different regularization methods. Lipschitz regularization preserves most of the labels (Figure 1). Tychonoff regularization smooths the solution (left). Total Variation regularization shifts the label values towards the mean (right).

Solutions of Ill-Posed Problems. Winston and Sons, New York,  1977.    Xiang Wei, Boqing Gong, Zixia Liu, Wei Lu, and Liqiang Wang. Improving the improved training of wasserstein gans: A consistency term and its dual effect. arXiv preprint arXiv:1803.01541, 2018.

Table content: <table><tr><td>Huan Xu and Shie Mannor. Robustness and generalization. Machine learning, 86(3):391-423,</td></tr><tr><td>2012.</td></tr><tr><td>Yuichi Yoshida and Takeru Miyato. Spectral norm regularization for improving the generalizability</td></tr><tr><td>of deep learning. arXiv preprint arXiv:1705.10941, 2017.</td></tr><tr><td>Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding</td></tr><tr><td>deep learning requires rethinking generalization. arXiv:1611.03530, 2016.</td></tr></table>

-2t -m m+2 n -(ct-1) for t ≤ n/ log(n). Since we have 󰀂w󰀂 L ∞ (X;Y ) ≤ CL, the estimate

Table content: <table><tr><td>holds with probability at least 1 sup w∈H L (X;Y ) 󰀏 󰀏 󰀏 󰀏 󰀏</td><td>1 n</td><td>n 󰁛 i=1</td><td>w(x i ) -</td><td>󰁝</td><td>M</td><td>wρ dV ol(x)</td><td>󰀏 󰀏 󰀏 󰀏 󰀏</td><td>≤ CL,</td></tr><tr><td colspan="7">trivially holds, and hence we can allow t &gt; n/ log(n) as well.</td><td/><td/></tr><tr><td colspan="9">-m exp n 󰁛 i=1 w(x i ) -󰀃 -cnh -m 󰂃 2 󰀄 󰁝 wρ dx for any 0 &lt; 󰂃 ≤ h m . Choosing 󰂃 = h m+1 󰀏 󰀏 󰀏 󰀏 󰀏 ≤ CLh X holds for all u ∈ H L (X; Y ) with probability at least 1 -2h -m exp we have that 󰀏 󰀏 󰀏 󰀏 󰀏 1 n 󰀃 -cnh m+2 󰀄 , provided h ≤ 1. By selecting nh m+2 = t log(n) sup w∈H L (X;Y ) 󰀏 󰀏 󰀏 󰀏 󰀏 1 n n 󰁛 i=1 w(x i ) -󰁝 M wρ dV ol(x) 󰀏 󰀏 󰀏 󰀏 󰀏 n ≤ CL 󰀕 t log(n) 󰀖 1 m+2</td></tr></table>

Peer review (iclr2019):
 The paper studies generalization through a general empirical risk minimization procedure with Lipschitz regularization. Generalization is measured through distance of the empirical minimizer function to a true labeling function u_0, or to the minimizer of the expected regularized loss. The approach of studying generalization through the lens of Lipschitz stability over the data is interesting, and the study directly considers minimizers of regularized optimization objectives, which is different than recent generalization bounds which often provide guarantees on a given network regardless of how it was trained. However, various aspects of the setup seem quite disconnected from practice in the context of deep neural networks, and the obtained guarantees are quite weak and not always connected to generalization: - the approach relies on a constant L_0 in the objective which is assumed known in advance (although it is usually set to 0 in practical methods), and determines the nature of convergence. In particular, the results for small L_0 (referred to as "noisy labels") only shows convergence to a minimizer u^* of the expected *regularized* loss, thus does not characterize generalization in the usual sense since u^* is biased. More generally, the distinction between *clean* and *noisy* labels is confusing and should be clarified: the paper seems to assume that the true labeling function u_0 may itself produce incorrect labels deterministically even with infinite data, which is an odd way to formulate the learning problem. - the convergence rates obtained in the paper exhibit a curse of dimensionality (O(n^{-1/m}) where m is the dimensionality of the data manifold). Given that most other bounds for neural networks do not exhibit such a dependence on dimension, this seems to be a weaker guarantee, unless the setting captures an improvement in a different setting. (edit: I removed the previous remark on parametric rates, which was inaccurate) Some of the constants also seem to grow exponentially with m. Either way, this should be discussed in the paper. - possibly related to the previous point, all the theory in the paper is agnostic to the function class considered, given that it simply considers all lipschitz functions in the variational problem (1). Given that the authors attempt to explain generalization of neural networks, this seems like a non-negligible disconnect since there could be approximation errors. In particular, even if deep networks can perfectly fit training data, it is not clear that they can achieve the best trade-off with the Lipschitz constant in the regularized objective (1). - the assumptions on the prediction space (simplex) and the used loss functions also seem disconnected from practice (the cross-entropy loss usually includes a softmax). Note that while usual networks can fit randomly labeled data (Zhang et al.), this does not mean their loss is 0. Yet the analysis seem to rely on having zero loss on training points, even in the case of *noisy labels*. Additionally, the use of covering arguments in the input space in the proposed approach is related to the study of generalization through robustness [Xu & Mannor (2010), "Robustness and Generalization"]. The authors should discuss the relationship to this work. More comments: - the term *converge* in the title is not clear. In the abstract, what does *verification* mean? - Section 2.3: m_0 == m ? How does C grow with m in Theorem 2.7 and Corollary 2.8? What is meant by *perfect generalization*? Is eq. (6) realistic for classification losses? - Section 2.4: clarify what is meant by *noisy labels*