Certifying Distributional Robustness using Lipschitz Regularisation
Authors: Zac Cranko
Zhan Shi
Xinhua Zhang
Simon Kornblith
Richard Nock
Venue:  (2020)
Keywords: kernel method
adversarial learning
distributionally robust optimization

Abstract: Distributional robust risk (DRR) minimisation has arisen as a flexible and effective framework for machine learning. Approximate solutions based on dualisation have become particularly favorable in addressing the semi-infinite optimisation, and they also provide a certificate of the robustness for the worst-case population loss. However existing methods are restricted to either linear models or very small perturbations, and cannot find the globally optimal solution for restricted nonlinear models such as kernel methods. In this paper we resolved these limitations by upper bounding DRRs with an empirical risk regularised by the Lipschitz constant of the model, including deep neural networks and kernel methods. As an application, we showed that it also provides a certificate for adversarial training, and global solutions can be achieved on product kernel machines in polynomial time.

Under review as a conference paper at ICLR 2020
CERTIFYING DISTRIBUTIONAL ROBUSTNESS USING LIPSCHITZ REGULARISATION
Anonymous authors Paper under double-blind review
ABSTRACT
Distributional robust risk (DRR) minimisation has arisen as flexible and effective framework for machine learning. Approximate solutions based on dualisation have become particularly favorable addressing the semi-infinite optimisation, and they also provide a certificate of the robustness for the worst-case population loss. However existing methods are restricted to either linear models or very small perturbations, and cannot find the globally optimal solution for restricted nonlinear models such as kernel machines. general class of kernel space, and our approach is based on new upper bound of DRRs using an empirical risk regularised by the Lipschitz constant of the model, e.g., deep neural networks and kernel methods. As an application, we showed that it also provides a certificate for adversarial training, and global solutions can be achieved product kernel machines in polynomial time.
this paper we resolve these limitations for a
INTRODUCTION
Regularised risk minimisation has been the workhorse of learning nonlinear hypotheses such as deep neural networks and kernel machines. Recently, distributional robust risk (DRR) minimization has emerged as promising instance with marked efficacy and flexibility. Instead of perturbing the observed data points. DRRs consider perturbations to the empirical distribution, constituting an ambiguity set P that lives in the space of data distributions. Let f2 be an outcome space with (true) distribution μl, e.g., the joint space of input and output. Given a loss function E, a model f suffers loss value (ww over an outcome w, and the risk of f under I is riske (d) == [2 In DRR minimisation, a model f is sought that minimises the expectation of loss over an ambiguity set P, i.e. that minimises suPrep iiske(f. v) (Delage Ye, 2010; Goh & Sim, 2010; Wiesemann et al., 2014). The ambiguity sets can be constructed by moment matching (Bhattacharyya et al., 2005; Farnia Tse. 2016), divergence balls (Ben- Tal et al., 2013; Duchi et al., 2016; Hu & Hong. 2016), or Wasserstein distance balls (Kantorovitch, 1958). In this work we focus on the last due to its favorable properties in statistics and computation, along with extensive applications in DRR (Esfahani & Kuhn, 2018; Gao & Kleywegt, 2016; Zhao & Guan, 2018).
Despite the generality of DRR, its computational efficiency remains a challenge, since the supremum over (typically) uncountably infinite dimension space. Tractable equivalent convex programs can be derived only for a limited range of loss functions along with linear hypothesis spaces (Blanchet al., 2016; El Ghaoui Lebret, 1997: Shafieezadch- aaaaeeezadh---bahhhhhh Abadeh al., 2015; 2017: Xu et al., 2009a:b). Although Shafieezadeh-Abeee Abaaehh et al. (2017) developed lifted variants for reproducing kernel Hilbert spaces (RKHS) accommodate nonlinear hypotheses, the perturbation was applied to ((w), where Φ is the implicit feature map. This still falls short of robustness with respect to distributions over 52.
more promising technique for optimizing DRRs over nonlinear hypothesis spaces- inreuuiinicuniinggg deep neural networks and kernel machines is by dualising it to a form that is amenable to (approximate) optimisation (Esfahani & Kuhn, 2018). The fundamental strong duality result was established independently by Blanchet & Murthy (2019) and Gao & Kleywegt (2016), and has been applied to various tasks such as specification of regularisation parameter (Blanchet et al., 2016), design of transport cost (Blanchet et al., 2017), and selection of ambiguity region size for optimal confidence interval (Duchi et al., 2016). In particular, Sinha et al. (2018) used to construct an efficiently computable certificate methods are still subject to marked restrictions when applied to smooth nonlinear models. First, Sinha et al. (2018) restricts the perturbation to be small, which despite the common interest of
the level of robustness for the worst-case population loss. However, these

---

Under review as a conference paper at ICLR 2020
imperceptible perturbations, leaves unaddressed the equally interesting regimes of medium to large perturbations; see discussions in Openreview (2018). Moreover, although the global solvability of the inner Lagrangian penalty problem (robust surrogate loss) can be ensured by small enough perturbation, there is no practical procedure to compute the threshold. Finally, the overall optimisation of the nonlinear model is still subject nonconvexity, precluding tractable global solutions for restricted but still general classes of nonlinear models such as kernel methods.
The first goal of this work, therefore, is to develop novel certificate on distributional robustness that dispenses with these restrictions ($3). Specifically, we will leverage the McShane-Whiin Whitney extension theorem (McShane, 1934; Whimey, 1934) to upper bound DRRs by the empirical risk regularized with the Lipschitz constant of the model f. while additionally accounting for the underlying transport cost and the loss f. The result vastly generalises the vector norm regularisation in linear binary classification (Shafieczadeh-Abane -badeh et al., 2017, Thm. 3.11) I) to nonlinear models and extended real-valued cost functions that encode constraints, along with an arbitrary metric space of labels that is general enough for multiclass problems. Appealing to any magnitude of perturbation, it also enjoys improved computational efficiency compared with the robust surrogate loss in Sinha et al. (2018).
A particularly effective domain to apply this new certificate is adversarial learning (Szegedy et al., 2014), where models are trained to be resilient to malicious distortions on the data. Although Lipschitz regularisation has been popular recipe for robustness (c.g., Anil et al., 2019; Cisse et al., 2017: Farnia et al., 2019; Gouk et al., 2018; Huster et al., 2018; Scaman & Virmaux, 2018) 8) and generalisation accuracy (Miyato et al., 2018; Yoshida & Miyato, 2017), it remains heuristic and therefore our second major contribution is to reveal in $3.1 that adversarial risks (Goodfellow et al., 2015; Madry al., 2018: Shaham et al., 2018) can be bounded by a DRR. Such a rigorous justification has hitherto been restricted to logistic loss (Suggala et al., 2019, Thm. 9), and a similar tightness result has been established only for linear models (Shafieezadeh- -baadee et al., 2017. Thm. 3.20). As result, our new certificate amounts to a new bound on the worst-case risk under attacks, complementing the existing certificates (Raghunathan et al., 2018; Tsuzuku et al., 2018; Weng et al., 2018; Wong & Kolter, 2018; Wong et al., 2018) with a more computationally efficient approach. It further achieved statc-of-the-ar accuracy under a range of attacks on standard benchmark datasets ($5).
In practice, however, the evaluation of Lipschitz constant L is NP-hard for neural networks (Scaman & Virmaux, 2018), compelling approximations of it, or explicit engineering of layers to respect Lipschitz while analyzing the expressiveness in specific cases (e.g.. &oo norm in Anil et al. (2019)). We, instead, pursue a new path and explore the following question: does there exist a hypothesis space which: a) is expressive enough in modeling; b) allows the exact value of T. to be computed efficiently; c) enforcing the Lipschitz constant leads to a convex constraint that renders efficient optimisation.
Interestingly, y, kernel machines satisfy all these requirements for some kernels. For example, Gaussian kernels are universal, whose RKHS can approximate any continuous function on a compact set in a uniform sense (Micchelli et al., 2006). The RKHS of multi-layer inverse kernels compactly encom- passes E e-reeularizedd neural networks (Shalev-Shwartz et al., 201 1), degrading the generalisation performance by only polynomial constant (Zhang et al., 2016; 2017). Similar results have been conjectured for Gaussian kernels (Shalev-Shae -Shwart-S et al., 2011). Our third contribution proves that b) can be achieved for product kernels such as Gaussian kernels with high probability by using the Nyström approximation (Drineas & Mahoney, 2005; Williams& & Seeger, 2000), and approximation error of L requires only ( samples ($4). Empirically this approximation is also effective for non-product kernels like inverse kernels. Such sampling based approach also leads to a single convex constraint, making it scalable to 60k examples with even an interior-point solver ($5). The convenience in evaluating L renders certificate of DRR even more favorable than those based on robust surrogate losses (Blanchet & Murthy, 2019; Gao & Kleywegt, 2016; Sinha et al., 2018).
PRELIMINARIES
The vast majority of our technical results and proofs are deferred to Appendix A, for which theorem- like statements numbered be consistent. The extended real line is R = [-o0, +o0), Rzo
[0, oo). and [n] == 21,2.... n]. For topological spaces X,Y Y. the Borel subsets are B (X), and the Borel probability measures are (()). The universal sigma algebra is (X) =- )x) L (X) where B8 (X) is the completion of the Borel sets with respect to μ B(X). Let Lo(X, Y) denote the Borel measurable mappings X + Y. and LL (X, 11) denote the Borel functions f E Lo( R) with f'I du < oc for μ E (X).
2

---

Under review as a conference paper at ICLR 2020
For two measures μ1, V (S2) the set of (H, couuplinng is
[( = { E B( 22) μ - [T( ,dw); v = (dws, }]
Let e E Lo(? x S2 R). The c-transportation cost of μ4, 1/ E ((2), and c-transportation cost ball of radius r 2 0, centred at μ (12) are respectively
cost. 2) = inf { cdw n M( v)} and B,( == {v E T( cost, () rr.. (1)
function f f2 + is L-pisschitz there exists 2 0 such that
Yur, w2 E dom f: IS(w)) - ((22)) & Lc(w),w2).
(2)
The least c-Lipschitz constant of f (cf. Cranko et al., 2019) is the infimum over L 2 0 satisfying metric space lipa(f) agrees with the usual
(2), and denoted by lip,(f), so that when (X,d) Lipschitz notion. When c X - R (e.g., when is a norm), we take c(2, y) == cxx y) for all x, X in (1) and (2).
CERTIFICATE FOR DISTRIBUTIONAL ROBUSTNESS
While elegant concept, the DRR suffers from lack of tractability. That is, in order to effectively minimise it, we first need to be able to compute or estimate it. When the loss function is convex with respect the input space this is straight-forward, however in general approximations are necessary. Our first contribution is an upper bound for it.
For a function f X + there is another function c X + R. called the convex en- velope of f. It is the greatest closed convex function that minorises f. The quantity p(f) == supzex (fx) co fx)) was first suggested by Aubin & Ekeland (1976) to quantify the lack of convexity of function, and has since shown to be of considerable interest for variety of nonconvex applications (Askari et al., 2019; Kerdreux et al., 2019; Lemaréchal Renaud, 2001; Udell & Boyd, 2016). When X R there are well-known ways to compute both to f and p(.)) and brief discussion on these appears in the appendix (Remark 2 on p. 18). p(f) = when f is closed convex.
Theorem 1. Assume X a separable Fréchet space and fix μ E B(X). Assume e : X - Rzo sublinear and continuous, and L L,,,,
XX p1) is upper semicontinuous. Then for all 2 0,
sup riske(f.v) rrlip((f)) riske(f.1). DRR vEBa(p.r)
(3)
The tightness of the bound can be quantified as follows. Let A(p) (ipp + riske(f.
suPveB.(u.r) riske(J.v). (J) < oc: then
A(n) S r <r((ii(())) -
(4)
where [-] max ,0 and 1/0 oo, so that when & is closed convex there is equality in (3).
Clearly (4) is tight for convex Ey- Furthermore, Proposition 1 shows that (4) is also tight for large family of nonconvex functions and distributions - particularly the upper-semiicontimuuus loss functions on compact set Xo S X, with the collection of probability distributions supported on Xo-
Proposition 1. Assume X is a separable Fréchet space with Xo C X. Assume X R>o is sublinear and continuous, and l E &[uerp(x,) (X, μ)) is upper semicontimuous, has (e,) < co.
and attains its maximum on Xo. Then all 2 0 with 1/0 = cc,
1 sup A(p) - (lip. - (60 - p((r) - (e)(
Theorem I subsumes many existing results (viz. Gao & Kleywegt, 2016, Cor. 2 (iv), Cisse et al., 2017, $3.2, Sinha et al., 2018, Shafiezzadeh-Abadhh et al., 2017, Thm. 3.20) with a great deal more generality, applying to a very broad family of models, loss functions, and outcome spaces. It is the first time to our knowledge that the slackness in (3) has been characterised tightly.
The extension of Theorem for robust classification in the absence of label noise is straight-forward.
Corollary 1. Assume X is a separable Fréchet space and Y is a topological space. Fix e X x Y). Assume e: (X x Y) (X xY) - R. satisfies c(ar, y, x' v') ex (x - x') whenever
3

---

Under review as a conference paper at ICLR 2020
y and c(z, V. x. v/) )== whenever + v'. where cx X R. is symmetric, sublinear, and continuous, and f E L1(X x p.) upper semicontimuous. Then for all r 2 0 there is (3).
To the tightness of the bound, if lip)(er) so there is (4), where the closed convex hull is interpreted as (o(,))(z, ,,,.) y) == coley( (x). If additionally Eg( ,y) is closed convex for all y E Y, there is equality in (3).
3.1 DISTRIBUTIONAL ROBUSTNESS ADVERSARIAL ROBUSTNESS
We next show how Theorem can useful for adversarial learning. The following objective function has been proposed to build robust classifier. Let X and Y be topological spaces, fix 8 x Y) and let d be a metric on X. The following objective has been proposed (viz Goodfellow et al., 2015; Madry et al., 2018; Shaham et al., 2018) as a means of learning models that are robust adversarial perturbations
adversarial risk =
(y V)u(dr dy) = sup (((W))((w)) BEBa(E.r)
sup
(5)
@EBg(w.))
where in the equality we extend dl to metric on x Y with
d((x, v), (a' ,')) == (1,2 + 00 1u .1.
We refer to (5) as the adversarial risk.
Theorem 2. Assume (X,c) is a separable Banach space. Fix μ E B(X) and let Rp(r) =
{g E Lo(X, Rgo) f gd sr). Then for J E Lo(O, R),, r there is
/ (((ww sup
variable-radius risk == sup
eg(W') S sup riske - = DRR. (6)
ge ge
('EB,(
vEBa(u.r)
The equality holds (6) if p non-atomically concentrated on a compact subset of X, on which continuous with the subspace topology.
We refer to the left-hand side (LHS) of (6) as the variable-radius risk. The variable-rading risk has appeared in various forms in similar results, usually formulated using empirical distributions, that is, an average of Dirac masses, (viz. Gao & Kleywegt, 2016; Shafieezadeh- Abadeh et al., 2017). Of course any finite set is compact, and any empirical distribution satisfies the concentration assumption. Likewise the subspace topology on a finite set is the discrete topology, which makes the continuity assumption trivial.
Both the adversarial risk and the variable-radius risk imply an uncertainty set over a collection of adversaries that may perturb the data. Figure in the appendix (on p. 20) shows the practical difference between the kinds of adversaries in these uncertainty sets. Immediately there is corollary similar Corollary for Theorem 2.
It is easy to see that the variable-radius risk upper bounds the adversarial risk (5) by observing that the constant function Or = r is included in the supremum over (r. in (6). As result,
(a)
(b)
adversarial risk < variable-radius risk DRR
<
Lipschitz regularised risk (RHS of (3)), (7)
where (a) by Theorem 2 and (b) by Theorem
In general, it is difficult to characterise the tightness of the upper bounds in Theorem 1 and 2. So resorted empirical demonstration that the of all the three gaps in (7) is relatively low.
We randomly generated 100 Gaussian kernel classifiers f >100 7k(("", .). with of sampled from the MNIST dataset and % sampled uniformly from 2- 2]. The bandwidth was set to the median of pairwise distances. In Figure the z-axis the adversarial risk (5) where the perturbation is
bounded in fp ball and computed by PGD. The y-axis is the Lipschitz regularised empirical risk. The scattered dots lie closely to the diagonal, demonstrating that the above bounds are tight in practice.
PROVABLE LIPSCHITZ REGULARISATION FOR KERNEL METHODS
Theorems and 2 open up a new path to optimising the adversarial risk (5) by Lipschitz regularisation (RHS of (4)), where the upper bounding relationship is established through DRR. In general. however, it is still hard compute the Lipschitz constant for a nonlinear model. However, will show that
4

---

Under review as a conference paper at ICLR 2020
20
11l smpis sto (bxx())
80
I1/il sm ue -ipx(
RHS of BBq (3)
10
REHS of Biq (3)
60
2220
10-
-00
10
26
0
0
10
0
10
20
0
20
40
60
80 lipx(f)
10
30 cy12 ((px(())
20
Adversarial risk Eq (5)
Adversarial risk in Eq (5)
(a) ||61|2 I
(b) ||8| - 0.3
(a) 5-layer inverse kemell (b) Gaussian kernel (a=3)
Figure 1: Empirical evaluation of the sum of the gaps from Theorems and 2. The Lipschitz constants su V fx=)ll (left: p = 2, right: p- 1//+ 1/1=1) 1) were estimated by BFGS.
Comparison of Dmax G) and the RHS of (8), as upper bounds for the Lipschitz con- stant. Smaller values are tighter. 100 functions sampled in the same way as in Figure 1.
Figure 2:
for some types of kernels, this can be done efficiently on functions in its RKHS. Thanks to the known connections between kernel method and deep learning, this technique will also potentially benefit the latter. For example, l f1-regularised neural networks are compactly contained in the RKHS of multi-layer inverse kernels k(2, y) (2 - x x= y) -1 with | S 1 and ||y/| I (Zhang et al., 2016, Lemma 1 and Theorem 1) and SShalev-Shwart. et al., 2011 I; Zhang et al., 2017), and even possibly Gaussian kernels k(z y) exp(- || y/l² (2)²)) (Shalev-Shwarke et al., 2011, $5).
Let us consider a Mercer's kernel k on a convex domain X S RR, with the corresponding RKHS denoted as H. The standard kernel method seeks discriminant function / from H with the conventional form of finite kernel expansion f(x) = t E "ak(2 +), such that the regularised empirical risk can be minimised with the standard (hinge) loss and RKHS norm. We start with real-valued for univariate output such binary classification, and later extend to multiclass.
Our goal here is to additionally enforce, while retaining a convex optimisation in y == {7 J. that the Lipschitz constant of f falls below a prescribed threshold L >> O, which is equivalent to supxex f || < L thanks to the convexity of X. A quick but primitive solution is to piggyback back on the standard RKHS norm constraint || S C, in view that it already induces an upper bound on [[V((z)), as shown in Example 3.23 of Shafieezadeh-Ablee Abadhh et al. (2017),
sup [[]]( & IIʃ IH sup = ''(=), where g(2) 2 sup 2,2'EX:1l-='11,==
|M( .) - k(x' Il (8)
xEX
=>0
For Gaussian kernels, g(2) = max fo- 1]2. For exponential and inverse kernels, g(2) (Bietti & Mairal, 2019). Bietti et al. (2019) justified that the RKHS norm of neural network may serve as surrogate for Lipschitz regularisation. But the quality of such an approximation, i.e., the gap in (8), can be loose
will see later in Figure 2. Besides, C' and L are independent parameters.
How can we tighten the approximation? A natural idea is to directly bound the gradient norm at n random locations {w*}= >== sampled i..dd from X. These are obviously convex constraints 7. But how many samples are needed in order to ensure V f=)]l2 S L + e for all x E X? Unfortunately, as shown in Appendix A. n may have to grow exponentially by 1/e" for a d-dimensional space, Therefore seek a more efficient approach by first slightly relaxing [ [x)]ll) Let getg,( (x) == 0¹ (x) be the partial derivative with respect to the j-th coordinate of x. and 0 k( v) be the partial derivative to D; and yj- or j being means no derivative. Assuming suprex k(2, x) = 1 and 9j H (true for various kernels considered by Assumptions 1 and 2 below), get new bound
sup (x))2 =EX
sup Σ (g), k(x, )) S sup Σ #EX
(0)- 4) Amax (G G), (9)
e:l|el|==1 -
where Amax evaluates the maximum eigenvalue, and G := (g).....gH). The "matrix" is only notation because each column is function in H. and obviously the (i, entry of G G is (aaxxGGTTr (GT G') delivers significantly lower (i.e., tighter) value in approximating
(gt, 0z) Interestingly, Amaxe
giz) from (8). Figure the Lipschitz constant supaex [z))2) compared with ||5f| max,>0 8
compared these two approximants, where Amax (GT G) was computed from (11) derived below, and the landmarks {w") consisted of all training examples; drawing more samples led to little difference.
Such a positive result motivated us to develop refined algorithms to address the only remaining obstacle to leveraging "G G): analytic form for computation. Interestingly, it is readily approximable in both theory and practice. Indeed, the role of g, can be approximated by ğj. where Øj R is the Nyström approximation (Drineas & Mahoney, 2005; Williams & Seeger, 2000):
5

---

Under review as a conference paper at ICLR 2020
= -12) 9j (noting 93 (x²)) = (9), k(w", (o(w"..))) ;.)) k(w",)) where K = [k(w", w²) Mas,, 7: (k(w*, ",u, :)), G= ,..
-)) (10)
So to ensure (G G) I,2 te, intuitively we can resort to enforcing Amaa (G σ) S L,2, which also retains the convexity in the constraint in 7. However, to guarantee & error, the number of samples (n) required is generally exponential (Barron, 1994). Fortunately, we will next show that n can be reduced to polynomial for quite a general class of kernels that possess some decomposed structure.
4.1 COORDINATE- WISE NYSTROM APPROXIMATION FOR PRODUCT KERNELS
A number of kernels factor multiplicatively over the coordinates, such periodic kernels (MacKay, 1998), Gaussian kernels, and Laplacian kernels. We will consider k( y) IT (o(z).))) My) where X = X66 and ko is a base kernel on Xo. Let the RKHS of Ko be Ho. and let poo be a finite Borel measure with sup Xo. Periodic kernels have ko Vj) exp sin (zy /20))
The key benefit of this decomposition is that the derivative g0. (0.tk(a, y) can be written as go. Ko v1) II ko(z), Mz). Since (o(z,, 9s) can be easily dealt with, approximation will be needed only for 10.1 (o0 Applying this idea to 91 = i 7a00.1 ha("), :). we can derive
|1 l1 = 1 E
767 (00 ko .) 1 ko (o(xf .)) Ho II, xf) (11)
a,b=1
(01,92) = 11 E' a. To 00. 1 ko (zf, at 0 ko(ag 222 II, ho(a3. x5))
So the off-diagonal entries of G G can be computed exactly. To approximate the diagonal, we sample {wi...., wx) from Na, set Zi = (ko(w):)), ,)..,, (o :)), and apply Nyström approximation:
(ol.1ko 0), go.2ko(zi. -)) 1))10 = ko -) Z1 (2 -1) 1 z au, ko
(12)
where z, 0 ho (xf, = (00.1 (ool w/). , 80h ko (z9. w²)))
(13)
and analogously for ZJ go.l ku (2) We will denote this approximation of G G as Pg. Clearly,
Amax ( (PG) S T.2 is convex constraint on y, based on i.i.d. samples {wf : [m], E [d]] from μro- is now important to analyse how many samples wf are needed, such that
Amax Amax(Pa) S 1,2
Amax (G G) S 1,2 + with high probability.
4.2 GENERAL SAMPLE COMPLEXITY AND ASSUMPTIONS ON THE PRODUCT KERNEL.
Fortunately, product kernels only require approximation bounds for each coordinate, making the sample complexity immune to the exponential growth in the dimensionality d. Specifically, we first consider base kernels kn with a scalar input, i.c., Xo S R. Recall from Steinwart & Christmann (2008, Chapter 4) that the integral operator for ko and pAo is defined by
The - (Xoo po) + L2(Xo, mo)
where S L2 4O) + C(Xo), (sf))z) = -f |Lo(E, ( ()d()dpo(v)) f E L2(,,,
and T: C(Xp) - To2 Tx2(Xo; /b0) is the inclusion operator. By the spectral theorem, if Tko is compact, then there is an at most countable orthonormal set (ēybieJ of [2(Xo- Ho) and (Xiljes with A 2
A2 2 ... such that 5 Σjer A3 (f, E5) La(Xoipo) éj for all f E L2(Xo, po). It is easy to see that , = VAze, is an orthonormal basis of Ho (Steinwart & Christmann, 2008).
Our proof is built upon the following two assumptions on the base kernel. The first one asserts that fixing x, the energy of ku(z,)) -) and go.1 ko Az( "concentrates" on the leading eigenfunctions.
Assumption 1. Suppose ko(æ, x) and go. kol :) E Ho for all Xo- For all e > there exists N₂ E IN such that the tail energy of 00.1 ko(2.)) -) beyond the Nt eigenpair is less than uniformly for all x E Xo. That is, denoting 4m =
pm))
Ne = inf ( [1000_ko(r..
D To g0.2 ko(a,, 11xo < for all x E Xo and
[ 2n To (z, .) Mmm < for all E Xo} < <0.

---

Under review as a conference paper at ICLR 2020
The second assumption asserts the smoothness and range of eigenfunctions in a uniform sense. Assumption 2. Under Assumptioo I. fez(x)) j Ne) is uniformed bounded over Xu, and the RKHS inner product of 00.' with {ej j E Ne} is also uniformly bounded over x: E Xo:
M = sup max =EX]JE[N.]
(00.)Ko(tz (), 03)
< 0o,
and
Q= = sup max leg(1)) < co. SEX,JE(NS
Theorem 3. Suppose ko. Xo. and pa satisfy Assumptions 1 and 2. Let {wz iSE [m].] E [d] be sampled i.i.d. from po- Then for any I whose coordinate- wise Nyström approximation (11) and (12) satisfy Amax (Pa)= S LL2, the Lipschitz condition >aaax G) S L22 + E is met with probability 1 8. as long as n 2 O ( N? log dNx)) almost independent of d. Here θ hides all poly-log terms.
Satisfaction of Assumptions.
Appendix A.4 and A.5, we will show that for periodic kernel and Gaussian kernel, Assumptions 1 and hold true with Õ(1) values of Ne. MM., and Q.. It remains open whether non- crn-product kernels such as inverse kernel also enjoy this polynomial sample complexity. Appendix A.6 suggests that the complexity is quast-polynomial for inverse kernels.
EXPERIMENTAL RESULTS
We studied the empirical robustness and accuracy of the proposed Lipschitz regularisation technique for adversarial training of kernel methods, under both Gaussian kernel and inverse kernel. Comparison will be made with ofte-of-the-an defense algorithms under effective attacks.
Datasets. We tested on three datasets: MNIST, Fashion-MNIST. and CIFAR1O. The number of /aiining/vlldaationnesst examples for the three datasets are 54k/6k/10k, 54k/6k/10k 45k/5k/1 1kk, respectively. Each image in MNIST and Fashion-MNIST is represented as a 784-dimensional feature vector, with each feature/pixel normalised to [0, 1]. For CIFARIO, we trained on a residual network to obtain 512 512-dimensional feature embedding, which were subsequently normalised to [0, 1]. They were used as the imput for training all the competing algorithms and were subject to attack.
Attacks. To evaluate the robustness of the trained model, we attacked them on test examples using the random initialized Projected Gradient Descent method with 100 steps (PGD, Madry al., 2018) under two losses: cross-entropy and C& W loss (Carlini & Wagner, 2017). The perturbation 5 was constrained in an &a or foo ball. To evaluate robustness, we scaled the perturbation bound 5 from 0.1 to 0.6 for foo norm, and from 1 to 6 for lg norm (when 8 = 6, the average magnitude per coordinate 0.214).
Algorithms. We compared four training algorithms. The Parseval network orthonormalises the weight matrices to enforce the Lipschitz constant (Cisse et al., 2017). We used three hidden layers of 1024 units and ReLU activation (Par-ReLU). Also considered is the Parseval network with MaxMin activations (Par-MaxMin), which enjoys much improved robustness (Anil et al., 2019). Both algorithms can be customised for la or loo attacks, and were trained under the corresponding norms. Using multi-class hinge loss, they constitute strong baselines for adversarial learning.
Both Gaussian and inverse kernel machines applied Lipschitz regularisation by randomly and greedily selecting {w*}. }, and they will be referred to as Gauss-Lip and Inverse-Lip, respectively. In practice, Gauss-Lip with the coordinate-wise Nyström approximation (Amax: (Pa) from Eq (12)) can approxi- mate Amaxx (GT G) with a much smaller number of sample than if using the holistic approximation as in (10). Furthermore, we found an even more efficient approach. Inside the iterative training algorithm, we used L-BFGS to find the input that yields the steepest gradient under the current solution, and then added to the set {w") (which was initialized with 15 random points). Although L-BFGS is only a local solver, this greedy approach empirically reduces the number of samples by an order of magnitude. See the empirical convergence results in Appendix A.9. Its theoretical analysis is left for future investigation. We also applied this greedy approach to Inverse-Lip.
Extending binary kernel machines to multiclass. The standard kernel methods learn discrim- inant function f := Σ. (x"")"..) for each class c E [10), based on which a large supply of multiclass classification losses can be applied, e.g.. CS (Crammer & Singer, 2001) which was used in our experiment. Since the Lipschitz constant of the mapping from {f (f"} to a real-valued loss is typically at most 1, it suffices to bound the Lipschitz constant of + (z), (x)) by
7

---

Under review as a conference paper at ICLR 2020
100 ax 60 Testscurscy
100
Test Tectaauuneyy (%)
TacMeafa PCD Par P (P5--A)
40
Testaccussey
40
43
6g ball rodius
Eg ball radius 5
ball radios
(a) MNIST
(b) Fashion-MNIST
(c) CIFARIO
Figure 3: Test accuracy under PGD attacks on the C&W approximation with &g norm bound
100
100
108
00
SALOE pille weoee iropiet
Toxt accuracy (S)
Saarn DURGB OF Maslin
80
Testacuracy
Test acconncy
an ap PeDion
60
42-
6.
2.7
5.1
6.4
05
0.6
03
0.7
0.
0.6
03
07
04
0.5
Eop
ball pullion
ball radiue
Ex
ball radius 6
(a) MNIST
(h) Fashion MNNST
(c) CIFAR10
Figure 4: Test accuracy under PGD attacks on the C& W approximation with Lo norm bound
max Amax (G(z)G(x))) S max =1 Ammax E C. Go) 1.2,
10
(14)
where G(z)= = (z), [x)] = ((z, .).... Glok(z,) -]] with Ge == (gf..... ........ga T.). The last term in (14) can be approximated using the same technique as in the binary case. Furthermore, the principle can be extended to lo attacks, whose details are relegated to Appendix A.
Parameter selection. We used the same parameters as in Anil et al. (2019) for training Par-ReLU and Par-MaxMin. To defend against & attacks, we set L = 100 for all algorithms. Gauss- the validation set with bandwidth
Lip achieved high accuracy and robustness FashionMNIIST and CIFAR-10, and a = 2 for MNIST. To defend against lo attacks, we set L = 1000 for all the four methods in Anil et al. (2019). The best a for Gauss-Lip is for all datasets. Inverse-Lip used 5 stacked layers.
1.5 for
Results. Figures 3 and 4 show how the test accuracy decays as an increasing amount of perturbation (8) in lg and Lo norm is added the test images, respectively. Clearly Gauss-Lip achieves higher accuracy and robustness than Par-ReLU and Par-MaxMin on the three datasets, under both & and lx bounded PGD attacks with C&W loss. In contrast, Inverse-Lip only performs similarly to Par-ReLU. Interestingly, we noticed that & based Par-MaxMin are only slightly better than Par-ReLU under & attacks, although the former does perform significantly better under for attacks.
For the sake of space, the results for cross-entrop PGD attacks are deferred to Figures 8 and 9 in Appendix 11 Here cross-entropy PGD attackers find stronger attacks to Parseval networks but not to our kernel models. Our Gauss-Lip again significantly outperforms Par-MaxMin on all the three datasets and under both & and fo norms. The improved robustness Gauss-Lip does not seem to be attributed to the obfuscated gradient (Athalye et al., 2018), because shown Figures 3, 4. 8, 9, increased distortion bound does increase attack success, and unbounded attacks drive the success rate to very low. In practice, we also observed that random sampling finds much weaker attacks, and taking 10 steps of PGD is much stronger than just one step.
Visualization. The gradient with respect to inputs is plotted in Figure 10 (in the appendix on p. 31) for & trained Par-MaxMin and Gauss-Lip Lip. The i-th row and j-th column corresponds to the targeted attack of turning the original class j into a new class i, hence the gradient is on the cross-entropy loss with class as the ground truth. These two figures also explained why Gauss-Lip is more robust than Par-MaxMin: the attacker can easily reduce the targeted cross-entropy loss by following the gradient as shown in Figure 10a, and hence successfully attack Par-MaxMin. In contrast, the gradient shown in Figure 10b does not provide much information on how to flip the class.
Conclusion. In this paper, we derived a new certificate for distributional robust risk minimization by using Lipschitz regularization. Application to adversarial learning based on kernel methods exhibited superior robustness, with provably polynomial sample complexity for product kernels. We will apply this function space to GANs to witness the difference between probability distributions, leading to a more stable training scheme as the inner level optimization becomes convex.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Cem Anil, James Lucas, and Roger Grosse. Sorting out Lipschitz function approximation. In International Conference Machine Learning (ICML), 2019.
Armin Askari, Alexandre d' Aspremont, and Laurent El Ghaoui. Naive feature selection: Sparsity in 09884.
naive bayes. 2019. URL http: http///axvvv... wwt./oogg/aaaaaaee.ee..eeeeeessa
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. In International Conference on Machine Learning (ICML), 2018.
Pean-Pieree Aubin and Ivar Ekeland. Estimates of the duality gap in nonconvex optimization. Mathematics of Operations Research, 1(3):225-245, 1976. ISSN 0364765X, 15265471. doi: 10/d6r3xf.
A. R. Barron. Approximation and estimation bounds for artificial neural networks. Machine Learning, 14:115-133, 1994.
Aharon Ben-Tal, Dick den Hertog, Anja De Waegenaere, Bertrand Melenberg, and Gijs Rennen. Robust solutions of optimization problems affected by uncertain probabilities. Management Science, 59(2):341-357 2013.
C. Bhattacharyya, K. S. Pannagadatta, and A. J. Smola. A second order cone programming formula- tion for classifying missing data. In Advances in Neural Information Processing Systems (NIPS), pp. 153-160, 2005.
Alberto Bietti and Julien Mairal. Group invariance, stability to deformations, and complexity of deep convolutional representations. Journal of Machine Learning Research, 20(25):1-49, 2019.
Alberto Bietti, Gregoire Mialon, Dexiong Chen, and Julien Mairal. A kernel perspective for regular- izing deep neural networks. In International Conference on Machine Learning (ICML), 2019.
Jose Blanchet and Karthyek Murthy. Quantifying distributional model risk via optimal transport. Mathematics of Operations Research, 2019. doi: 10.1228/moor.2018... 8.0936..
Jose Blanchet, Yang Kang, and Karthyek Murthy. Robust Wasserstein profile inference and applica- tions to machine learning. 16Xiv:1610.05022 2016.
Jose Blanchet, Yang Kang, Fan Zhang, and Karthyek Murthy. Data-driven optimal transport cost selection for distributionally robust optimization.
2017.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017
IEEE Symposium Security and Privacy (SP), pp. 39-57. IEEE, 2017.
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval networks: Improving robustness to adversarial examples. In International Conference on Machine Learning (ICML), 2017.
Koby Crammer and Yoram Singer. On the algorithmic implementation multiclass kernel-based vector machines. Journal of machine learning research, 2(Dec)::26-299 2001.
Zac Cranko, Aditya Menon, Richard Nock, Cheng Soon Ong, Zhan Shi, and Christian Walder. Monge blunts Bayes: Hardness results for adversarial training. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 1406-1415. PMLR, 2019. URL http: http://prcceeding. mll. malr.pee www.sppeessvvve crankol 9a. html.
Erick Delage and Yinyu Ye. Distributionally robust optimization under moment uncertainty with application to data-driven problems. Operations Research, 58(3).595-612, 2010.
Drineas and M. Mahoney, On the nystr om method for approximating a gram matrix for improved kernel-based learning. JMLR, 6:2153-2175, 2005.

---

Under review as a conference paper at ICLR 2020
John Duchi, Peter Glynn, and Hongseok Namkoong. Statistics of robust optimization: A generalized empirical likelihood approach. arXiv:1610:03425, 2016.
Gregory E Fasshauer, Positive definite kernels: Past, present and future. Dolomite Res. Notes Approx., 01 2011.
Laurent Ghaoui and Hervé Lebret. Robust solutions to least-squares problems with uncertain data. SIAM J. Matrix Anal. Appl, 18(4):1035-106) 1997.
Peyman Mohajerin Esfahani and Daniel Kuhn. Data-driven distributionally robust optimization using the Wasserstein metrie: Performance guarantees and tractable reformulations. Mathematical Programming, 171(1-2):115-666 2018.
Farzan Farnia and David Tse. A minimax approach to supervised learning. Advances in Neural Information Processing Systems (NIPS), 2016.
Farzan Farnia, Jesse Zhang, and David Tse. Generalizable adversarial training via spectral normaliza- tion. In International Conference on Learning Representations (ICLR), 2019.
G. Fasshauer and M. McCourt. Stable evaluation of Gaussian radial basis function interpolants. SIAM Journal on Scientific Computing, 34()):7777A762,, 2012.
Rui Gao and Anton J Kleywegt. Distributionally robust stochastic optimization with Wasserstein distance. arXiv:1604.02. 2016.
Emmanuel Giner. Necessary and sufficient conditions for the interchange between infimum and the symbol of integration. Set- Val-Va and Variational Analysis, 17(4):321, 2009.
Joel Goh and Melvyn Sim. Distributionally robust optimization and its tractable approximations. Operations Research, 58(4):902 917, 2010.
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv:/412.6572, 2015.
Henry Gouk, Eibe Frank, Bernhard Pfahringer, and Michael Cree. Regularisation of neural networks by enforcing Lipschitz continuity. / 04368, 2018.
J. Hiritrt-Urnuty. A general formula on the conjugate of the difference of functions. Canadian Mathematical Bulletin, 29(4):482-485 1986. ISSN 0008-4395, 1496-4287. doi: 10/cc3fs2.
Jean-Bape -aptiste Hrriart-Uruuy. From convex optimization to nonconvex optimization. necessary and sufficient conditions for global optimality. In Francis H. Clarke, V. F. Dem'yanon and F. Giannessi (eds.), Nonsmooth Optimization and Related Topics, pp. 219-239. Springer US, 1989. ISBN 978- http://ooi.oooo 13. URL http::::://ooooggggggo
1-4757-6019-4. doi: 10.
978 978-1-10 1778-14775 475--7777-2- 077777777--7777 13.
Jean-Bane -aptittt Hiriart-Urruty and Claude Lemaréchal. Convex Analysis and Minimization Algorithms II. Springer- Verlag, 2010. ISBN 978-3-642-08162-00 OCLC: 864385173.
Zhaolin Hu and Jeff Liu Hong. Kullback-Leible divergence constrained distributionally robust optimization, 2016. Available from Optimization Online.
Todd Huster, Cho-Yo Yu Jason Chiang, and Ritu Chadha. Limitations of the Lipschitz constant as a defense against adversarial examples. 1807.0807 2018.
L. Kantorovitch. On the translocation of masses. Management Science, 5(1):1-4, 1958.
Thomas Kerdreux, Igor Colin, and Alexandre d' Aspremont. An approximate Shapley-Folkman theorem. 2019. URL http::tp/// /ttp/aaxvvvv/...///vv//ee///aaaa
08559.
H. König. Figenvalue Distribution of Compact Operators. Birkhäuser, Basel, 1986.
John Lafferty and Guy Lebanon. Diffusion kernels on statistical manifolds. Journal of Machine Learning Research, 6:129-163, 01 2005.
10

---

Under review as a conference paper at ICLR 2020
C. Lemaréchal and A. Renaud. A geometric study of duality gaps, with applications. Mathematical Programming, 90(3):399 427, 2001. ISSN 0025-5610. doi: 10/d7sn64.
Shao-Bo Lin, Xin Guo, and
Zhou. Distributed learning with regularized least squares. Journal of Machine Learning Research, 18(92): 1-31, 2017.
D. J. C. MacKay. Introduction to Gaussian processes. In C. M. Bishop (ed.), Neural Networks and Machine Learning, pp. 133-165. Springer, Berlin, 1998.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. International Conference on Learning Representations (ICLR), 2018.
E. J. McShane. Extension of range of functions. Bull. Amer. Math. Soc., 40((1))837-84) 842, 1934.
Charles A. Micchelli, Yuesheng Xu, and Haizhang Zhang. Universal kernels. Journal of Machine Learning Research, 7:2651-2667, 2006.
Ha Quang Minh. Some properties of Gaussian reproducing kernel Hilbert spaces and their implica- tions for function approximation and learning theory. Constructive Approximation, 32(2):307-333, 2010.
Ha Quang Minh. Partha Niyogi, and Yuan Yao. Mercer's theorem, feature maps, and smoothing. In Gábor Lugosi and Hans Ulrich Simon (eds.), Conference on Computational Learning Theory (COLT), pp. 154-168, 2006.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. In International Conference on Learning Representations (ICLR), 2018.
Openreview.
OpenReview comments on "Certifying some distributional robustness with princi- pled adversarial training" by Aman Sinha, Hongseok Namkoong, and John Duchi. https: /oppnrevieww...../// net forum? i d 2018.
Jean-Paul Penot. On the minimization of difference functions. Journal of Global Optimization, 12 (4):373-382, 1998. ISSN 09255001. doi: 10/c59j7n.
Aldo Pratelli. On the equality between Monge's infimum and Kantorovich's minimum in optimal mass transportation. Annales de l'Institut Henri Poincare (B) Probability and Statistics, 43(1): 1-13, 2007.
Aditi Raghunathan, Jacob Steinhardt, and Perey Liang. Certified defenses against adversarial examples. In International Conference on Learning Representations (ICLR), 2018.
C. F. Rasmussen and C. K. I. Williams. Gaussian Processes for Machine Learning. MIT Press, Cambridge, MA, 2006.
Kevin Scaman and Aladin Virmaux. Lipschitz regularity of deep neural networks: analysis and efficient estimation. Advances in Neural Information Processing Systems (NIPS), 2018.
Hans Schneider. An inequality for latent roots applied to determinants with dominant principal diagonal. Journal of the London Mathematical Society, s1 -1-28(1):8-22) 1953.
Soroosh Shafieezadeh-Abee Peyman Mohajerin Mohajerin Esfahani. and Daniel Kuhn. Distribu- tionally robust logistic regression. In Advances in Neural Information Processing Systems (NIPS), 2015.
Soroosh Shafieezadeh-Abalae Daniel Kuhn, and Peyman Mohajerin Esfahani. Regularization via mass transportation. arXiv:1710. 10016, 2017.
Uri Shaham, Yutaro Yamada, and Sahand Negahban. Understanding adversarial training: Increasing
local stability of supervised models through robust optimization. Neurocomputing. 307:195-200 2018.
11

---

Under review as a conference paper at ICLR 2020
S. Shalev-Shwarte O. Shamir, and K. Sridharan. Learning kernel-based halfspaces with the 0-1 loss. SIAM Journal on Computing, 40(6); 1646, 2011.
Z.-C. Shi and B.-Y. Wang. Bounds for the determinant, characteristic roots and condition number of certain types of matrices. Acta Math. Sinica, 15(3):32-334, 1965.
Aman Sinha, Hongseok Namkoong, and John Duchi. Certifying some distributional robustness with principled adversarial training. In International Conference Learning Representations (ICLR), 2018.
Ingo Steinwart and Andreas Christmann. Support vector machines. Springer Science & Business Media, 2008.
Arun Sai Suggala, Adarsh Prasad, Vaishnavh Nagarajan, and Pradeep Ravikumar. Revisiting ad- versarial risk. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2019.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In International Conference Learning Representations (ICLR), 2014.
John F. Toland. A duality principle for non-convex optimisation and the calculus of variations. Archive for Rational Mechanics and Analysis, 71(1):41661, 1979. ISSN 0003-9527, 1432-0673. doi: 10/eprjrs.
Joel A. Tropp. An introduction matrix concentration inequalities. Foundations and Trends in Machine Learning, 8(1-2):1-230, 2015.
Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Lipschitz-margin training: Scalable certification of perturbation invariance for deep neural networks. In Advances in Neural Information Processing Systems (NIPS), 2018.
Madeleine Udell and Stephen Boyd. Bounding duality gap for separable problems with linear constraints. Computational Optimization and Applications, 64(2):355 -78,, 2016. ISSN 1573- 2894. doi: 10/f8pmnq.
Cédric Villani. Optimal transport: old and new, volume 338. Springer Science & Business Media, 2008.
Tsui- Wei Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsich, Luca Daniel, Duane S. Boning, and Inderjit S. Dhillon. Towards fast computation of certified robustness for relu networks. In International Conference on Machine Learning (ICML), 2018.
Hassler Whitney, Analytic extensions of differentiable functions defined in closed sets. Transactions of the American Mathematical Society, 36( 1)x63-89, 1934.
Wolfram Wiesemann, Daniel Kuhn, and Melvyn Sim. Distributionally robust convex optimization. Operations Rexearch, 62(6): 1358-1333 2014.
C. K. Williams and M. Seeger. Using the Nyström method to speed up kernel machines. In Advances in Neural Infommtion Processing Systems (NIPS), 2000.
R. C. Williamson, A. J. Smola, and B. Schölkopf. Generalization bounds for regularization networks and support vector machines via entropy numbers of compact operators. IEEE Transactions on Information Theory, 47(6):25162255 2532, 2001.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning (ICML), 2018.
Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and J. Zico Kolter. Scaling provable adversarial defenses. In Advances in Neural Information Processing Systems (NIPS), 2018.
Huan Xu, Constantine Caramanis, and Shie Mannor. Robust regression and lasso. In Advances in
Neural Information Processing Systems (NIPS), 2009a.
12

---

Under review as a conference paper at ICLR 2020
Huan Xu, Constantine Caramanis, and Shie Mannor. Robustness and regularization of support vector machines. Journal of Machine Learning Research, 10:1485-1510, 2009b.
Yuichi Yoshida and Takeru Miyato. Spectral norm regularization for improving the generalizability of deep learning. arXiv: 10941, 2017.
Yuchen Zhang, Jason D Lee, and Michael Jordan. é1-reularized neural networks are improperly learnable in polynomial time. In International Conference on Machine Learning (ICML), 2016.
Yuchen Zhang, Percy Liang, and Martin Wainwright. Convexified convolutional neural networks, In International Conference on Machine Learning (ICML), 2017.
Chaoyue Zhao and Yongpei Guan, Data-driven risk-averse stochastic optimization with Wasserstein metric. Operations Research Letters, (6(()):6222261, 2018.
Ding-Xuat Xuan Zhou. The covering number learning theory. Journal of Complexity, 18(3):739-767 2002.
H Zhu, C. K.I Williams, R. J Rohwer, and M Morciniec. Gaussian regression and optimal finite dimensional linear models. C. M. Bishop (ed.), Neural Networks and Machine Learning. Springer-Verlag. Berlin, 1998.
Constantin Zälinescu. Convex Analysis in General Vector Spaces. World Scientific, 2002. ISBN 778-981-238-067 OCLC: 845511462.
13

---

Under review as a conference paper at ICLR 2020
Appendix
The pseudo-code of training binary SVMs by enforcing Lipschitz constant is given in Algorithm
Algorithm 1: Training binary SVMs by enforcing Lipschitz constant L
Initialise the constraint set S by some random samples from X. for 1,2,... do
Train SVM using one of the following constraints: [V/(2))] < 1,2, A w S
Brute-force:
Nyström holistic: Amax (G S L2 using as the set {w ...., w") in Eq (10)
Nyström coordinate wise: Amax (Pc) S L using S as the set fw', ..... w")
Eq (12)
Let the trained SVM be f(()
5
Find new w add to by one of the following methods:
Random: randomly sample from X.
Greedy: find argmax, || ( (x:) (local optimisation) by L-BFGS with 10
random initialisations. Add the distinct results upon convergence to S.
Return if L max
V (x)
falls below L.
used local maximum found by L--BGG with random initialisations as the Lipschitz constant of the current solution f()) (I,(0) in step 6). The solution found by L-BFGS is also used as the new greedy point added in step 5b.
Finding the exact argmax, V f (x)
is intractable,
Furthermore, the kemnel expansion f(x) ; E Tak(=" .) can lead to high cost in optimisation (our experiment used / = 54000), and therefore we used another Nyström approximation for the kernels. We randomly sampled 1000 landmark points, and based them computed the Nyström approximation for each ((xx,,, denoted as ((x")) E R 1000 Then f(x) can be written as "G=17a((""" ((x). Defining = E (a)((=)) we equivalently optimise w, and the RKHS norm bound on f can be equivalently imposed as the fo-norm bound on w.
To summarise, Nyström approximation is used in two different places: for approximating the kernel function, and one for computing [lg; l1x, either holistically or coordinate wise. For the former, randomly sampled 1000 landmark points; for the latter, used greedy selection option b in step 5 of Algorithm 1.
Detailed algorithm for multiclass classification. It is easy to extend Algorithm to multiclass. For example, with MNIST dataset, we solve the following optimisation problem to defend l attacks:
min 10.00
Σ ((F(x),)) v), where F
rk koz ....
Σ
a 10
10 Σ
s.t.
sup S1 S1
Amax
PT Ge
Amax |ا||
sup
Σ c=1
G vo TG
< I2
where ((F(x). y) is the Crammer & Singer loss, and the constraint is derived from (14) by using its Nyström approximation G. = [of -i...... ., T2], which depends on { linearly. Note that constraint itself is supremum problem:
10
10
vo vo Go G..yu.
sup |1
Amax
Σ G TovTTGG
sup |
"
T
Σ
G
Since there is only one constraint, interior point algorithm efficient. requires the gradient of the constraint, which can be computed by Danskin's theorem. In particular, alternates between
14

---

Under review as a conference paper at ICLR 2020
updating v and u, until they converge to the optimal and u4. Finally, the derivative of the constraint with respect to {-r) can be calculated from Ee= (u. Go v.)?. function of {-/}.
To defend & attacks, we need to enforce the Lo norm of the Jacobian matrix:
sup x
[g (z)........"""
sup max (x))l
w Ises10
max sup (x)]11 1se =ex
G. P,
I max
sup
u
ises S1 $1
where the last inequality is due sup ||(( = sup sup uI g(x) S =ex 51
TT c.
sup
Therefore, the overall optimisation problem to defense Loo attacks is
min 7' .'...777 1=1
Σ ((F(x))))
where F
y k :); :....:
10 ((((,)))))) )
s.t.
sup $1,
C.USL L, TT uTd.
Vc (L,...,10}
(15)
For each c, we alternatively update and u in (15), converging to the optimal v, and u. Finally, the derivative of Supp],l,, u Go v with respect to 7d can be calculated from u. G u. as a function of e
A PROOFS OF RESULTS
The following appendix contains the complete set of proof' and auxiliary results.
PROOFS FOR $3: CERTIFICATE FOR DISTRIBUTIONAL ROBUSTNESS
Duality results like Lemma have been the basis of a number of recent theoretical efforts in the theory of adversarial learning (Blanchet et al., 2016; Gao & Kleywegt, 2016; Shafieezadeh-Abade et al., 2017; Sinha et al., 201 8), the results of Blanchet & Murthy (2019) being the most general to date.
Lemma (Blanchet & Murthy (2019, Thm. 1)), Assume Ω is a Polish space and fix μ E ((2).
Let 1 x Ω Rzo be lower semicontinuous with c(w, = O for all Ω, and f E L1(2 is upper semicontinuous. Then for all r 2 0 there is
[ fdv= = inf Ar + gro (Dody) X20
sup (EB.(R
(16)
The necessity for such duality results like Lemma 1 is because while the supremum on the left hand side of (16) over a (usually) infinite dimensional space, the right hand side only involves only a finite dimensional optimisation. The generalised conjugate in (16) also hides optimisation, but when the outcome space s2 is finite dimensional, this too a finite dimensional problem.
The following is sometimes stated consequence of or in the proof of the McShane-Whitney extension theorem, but is immediate to observe.
Lemma 2 (MeShane-Whine Whitney). Let X be set. Assume e: X X + R20 satisfies c(z,x)) 0 for all x E X, and f X + R. Then
V X fxx f(y) s Ac(x,y) = X f(v)
sup (f(x) Ac(x, v)).
zex
Lemma 3. Assume X is locally convex Hausdorff topological vector space. Let c: X + I be lower semicontinuous, sublinear. and continuous at 0. let X - R be closed convex. Then for > there is
((()
0f(x) C dAc(0) 0f(X) g a)c(0).
Vy X sup (f(z) Ac(2 v) weX
x
15

---

Under review as a conference paper at ICLR 2020
Proof. Because f is closed convex, it is equal to its biconjugate (Zälinescu, 2002, Thm. 2.3.3),
because с is sublinear and lower semicontinuous Ac(r) = sup, =aAc0))) (z, x²) for all x E X (Zälinescu, 2002. Thm. 2.4.14 (iv)). It follows that
sup (f(#) -x(x=- - v)) zEX
sup sup inf =eX ( (00A((() -f - -6g v1 (1r -") + (v. -
sup sup =EX (af(x))) o EBAc(0)
inf
- f (x'))
Because e is continuous at 0, Ōc(0) is weak -compact and convex (Zälinescu, 2002, Thm. 2.4.9), and so we can apply a minimax theorem (Zälinescu, 2002, Thm. 2.10.2) to produce
(1x, - (1x,""-9") -3") + (v.g") - (aa))
sup sup inf zex (0f(x) g*E
sup inf sup (1r 9²) + (v.g") (x)))
E0X())) ZEX
(U,,")) - (x*(x* 9" x¹
sup
inf
='Ef((X) 9 E0)c(() 100
9" 4 x x²' E 0Ac(0)
(g.x*) - (x*)
sup
='E((())
0
x²' $ (Ac(0)
f(()
0f(X) S 0Ac(0) x 05(X) g @)c(0),
as claimed.
Remark 1. The minimisation of of g-g-h, h, where g and h are convex functions, is called difference convex (DC) programming (Hiriart- Uunutty 1989). The condition in Lemma 3 bears striking resemblance to the common necessary condition (e.g. Hiriart-Urruty 1989; Penot, 1998) for such problems
I E arginf f(x' = 0h(x) S 0g(z).
s'ex
Likewise there are similar sufficient conditions. The proof of Lemma 4 is also quite similar to the proofs of the Toland (1979) duality formula (viz. Hiriart-Uruuty 1986)
inf (g(x)) h(z)) inf x-xx- rex
- - (x)",,)
which suggests that the principles of Lemma 4 may be more general. A generalisation to a general convex function satisfying c(0) O, would remove the positive homogeneity requirement of Lemma 4, and allow any translation invariant metric in place of c. The assumptions we have made compatible with metries which arise from norms, that is, the translation invariant and positively homogencous metrics.
Lemma 4. Assume X a topological vector space. Let X + Rzo, and f X - R. Then for X > 0 there is
Vx,y X: f(x) f(y) I Ac(r - y) + 0f(x) S @Ac(O).
Proof. Suppose À > is such that f(x) - (vv S Ac(x - 4) for all x, E X. Let x* E 0S(X).
Then there is x E X with
V (y - x,x") (y=x,x²)
S f(y) - f(x) S Acly - x) VE E X: (y,x*) S fly + - -(()) s Ac(y), satisfies 0f(X) S @)c((). Then
this shows x' E ())(O). Next assume Vx X, E 0.(()), Vy X f(x) fly) s (x -v,x²) Ac(x - v), where the second inequality is because x aAc(0) for all x 0f(z).
Theorem 1. Assume X is a separable Fréchet space and fix E B(X). Assume c: X - Rzo is sublinear and continuous, and f E EL1(X, ()) is upper semicontinuous. Then for all r 2 0,
DRR = sup riske(s.v) S (ls) + (f.k.
rEBe(ur))
16

---

Under review as a conference paper at ICLR 2020
The tightness of the bound can be quantified as follows. Let A(H) rlipo(ef) + rfske(f.
suPveB.(u.r) riske(f. If (f) < oc then
A(1) S r (1ppa(eg) [Tipa(co(g) [(e,- (ol-)))))) du) {.)
where| [. = max ,0 and 1/0 := oo, that when & is closed convex there is equality in (3).
Proof. Because is assumed sublinear, is positively homogeneous and there is c(z, x) c(x x))
c(0) = 0 for all x E X. Therefore we can apply Lemma and Lemma 2 to obtain
sup (u.)) / ,
rd ʃ eg du
dv=
inf A20
rx+ / /
S ini
inf
x2tip_(es)
= =el) / e ey
Observing that Cō / s ey. applying Lemma and Lemma 4 we find for all x E
sup (er(x) - (x) (1) r2) = sup xE)0,20)
(er(a) sup (ef(v) - Ae(s y)) - r2)
xE(0,00)
yEX
sup inf (f)(x)) eg(v) + Aelo - v) - -r2)
I sup inf (f)(x) cτ (v) + Ac(x - V) Xr)
(l)(x) ( 0τ (xx) - x [lip, Eg) \l - Xr)
= sup
xE(0,00)
= (x) co cot r (cok
(1)
Similarly, for all x E X there is
sup xE xx(0,0c) (e)(z) - 17)(x) - r2)) s sup
(e)(z) - -e7((z)) + sup -rd
AE(0,00)
xE(0,00)
(4/(z) - -13((0)
sup
AE(0,00)
inf (e/(z) (v(()) + Ac(x v))
sup
AE(0,,0) veX
I inf yEX xe(0,0o)
sup
(4((x) - (v) + Ac(x - 5)
c(x > 0
inf yeX
1
c(x y) = 0
0.
(2)
Then, using (1) and (2) we find
(rlipo((s)+ + f e eydu)
inf xE(0,00)
rd - lja dp)
ffef
/ (Eg (lg-230 - >r) du
- + sup
xE(0),0)
Srlip.(f)) + /
(f-- >r)) du
sup xE(0,00)
(1.22)
rlip. (e,) + min /
col dp - lip, (o0,(.))
The proof is complete.
17

---

Under review as a conference paper at ICLR 2020
Proposition 1. Assume X is separable Fréchet space with Xo S X. Assume X Ryu is sublinear and continuous, and f E <Neep(x.) L1(X, P1) upper semicontimuous, has lipa(fy) () < co. and attains its maximum on Xo. Then for all 2 0 with 1/0 = oc,
A(p) r ripp lip. ( p((r))
sup ())(X))
Proof. Let z0 Xo be be the point at which (z(z)) supzexo (z(x). Then
/ l dō A(8m)) = r lip)(l)) lg ljdd (EB.(5.0.t))
sup
= =rlipd(ey) + / 1,
/ - - dō20
-rlipo(ly).
(3)
Then there is
(3) r (e)) S
(4) (iap((e)-max(iipppll maxxlippccoolp)) - 1 (((())))) S srlip,
A(r) S r (lip(le))
sup (c
which completes the proof.
Remark When f: RD + R satisfies f * and f is minorised by an affine function, there is (cf. Hiriart-Urruty & Lemaréchal, 2010, Prop. 1.5.4)
Ve R": fτ)(x) inf Σ axf(x))
Σ a; 0,
Σ
iE(++1
(E(n+1]
(E
where the infimum is over all sequences (ag)ie(n+1) and (I))ie(at1) S RR" satisfying the conditions above. Consequentially there is the common expression
p(f) sup f
Σ 1E[++1]
agds)
axf(x;) (a, R20 RR, (E(n+1]
Σ
Σ a 0,=1 EE
In Lemma 5, by the weak" topology on ((?) we mean the coarsest topolgoy on ((2) that makes the bounded continuous functions s its topological dual space. Likewise _ denotes convergence in this topology.
Lemma 5. Assume (2,c) is compact Polish space and μ E ((2) is non-atomic. For any o² E P(2) and r > O there is a sequence (fi)ie S. Ar(()) = {f E Lo(2,, 92) fdd(id, f) S r} with (f:) 4 v*.
Proof. Let P(u,v) ( Lo(,, f#j v.. Since μ is non-atomic and is continuous Pratelli (2007, Thm. B) shows
/ cd(id, f) = cost, (H, SEP(u.))
VV E B(!):
inf
Let r* == coste v*), obviously x* S r. Assume y* > O, otherwise the lemma trivial. Fix let vuu)
sequence (Ex)KeN C (0, r*)) with EN 0. For
u(v" u). Then
costa(p, (())) = 0 and cost. v(1) = =
and because cost, metrises the weak" topology on ( (Villani, 2008, Thm. 6.9), the mapping u + (o, v()) is continuous. Then by the intermediate value theorem for every A E N there is some Uy with cost, v(u)) = ER. forming sequence (ux Men) [0, 1]. Then for every there is a sequence (fzk)SEN C P(p,v(ux)) so that (fzk) =v(k) and
/ odlid, faz)#1= inf jen
/ cd(id, fa) costo v(k)) r² Ek.
lim
SEP(aN(())
18

---

Under review as a conference paper at ICLR 2020
Therefore for every & E N there exists ja that for every 2 jkc
i cd(id, f5k) S r
(3)
Let us pass directly to this subsequence of (Jik)jeN for every ho N so that (3) holds for all j. k E N.
Next by construction we have vl(xx) + v². Therefore (fAR)ARNN has subsequence in l so that (f) - v². By ensuring (3) satisfied, the sequences (fja)JeN Ar(r) for every & N.
Theorem 2. Assume (X is separable Banach space. Fix μ E P(X) and let Ry(r) to E (o((X)22)) J gdp S r.. Then for I E LolO, R), 0 there is
/ (((dw) sup
variable-radius risk == sup gER,(r)
e((W) S sup riske (f. v) DRR. vEBe(urr)
('EB.(w.(W)))
The equality holds in (6) if y is non-atomically concentrated on compact subset of X, on which is continuous with the subspace topology.
Proof. Inequality (6). For (r(r), let I, x denote the set-valued mapping with
Tg(x)= = Be(r, g(x)). Let Lo( X, gg) denote the set of Borel a X - so that a(x) E (x) for j-almmst all X. Let (r) UMER, (r) Lo(X, rg): Clearly for every (r( there is
r 2 / dx ((ta((1)) a(x)) di = =
ed a)
which shows faupl E (r) S Be(H, r). Then if there equality in (4), we have
S f dd
sup (ER
sup z'E(((x)
f(z) sup gER,(() nE
sup
(4)
aEA,(r) / f dazp
sup
/ f dayy,
sup vEB.(ur)
which proves the inequality (6).
Equality (4). To complete the proof we will now justify the exchange of integration and supremum in
(4). The set S o(,, K ) is trivially decomposable (Giner, 2009, see the remark at the bottom of p. 323, Def. 2.... By assumption is Borel measurable. Since f is measurable, any decomposable subset of ( X, X) f-decomposable (Giner, 2009, Prop. 5.3) and f-linked (Giner, 2009, Prop. 3.7 (i)). Giner (2009, Thm. 6.1 (c)) therefore allows to exchange integration and supremum in (4).
Equality (6). Under the additional assumptions there exists 5* E P(?2) with (via Blanchet & Murthy, 2019, Prop. 2)
[sav== sup vEB.(ar)
/ ddv.
The compact subset where is concentrated and non-atomic is a Polish space with the Banach metric. Therefore Using Lemma there a sequence (ft) S Ar(rr so that
/ fidu = iEN
/ fdv'= sup veBolur)
/ f dv,
lim
proving equality (6).
19

---

Under review as a conference paper at ICLR 2020
W
92
Figure 5: In the classical adversarial risk (5) the perturbation size at each point most (blue), however with the variable-radius risk the expected perturbation size is at most
PROOFS FOR $4: PROVABLE LIPSCUITZ REGULARISATION FOR KERNEL METHOSS
Theorem 3. Suppose ko Xo, and vo satisfy Assumptions 1 and 2. Let {wi E [m], E [d] be sampled i...d from Vo- Then for any f whose coordinate-wis Nyström approximation (11) and (12) satisfy Amax (Pc) < <L2, the Lipschitz condition (G G) L2 + is met with probability 1-6 as long as n 2 O (2 log dN: ). almost independent of d. Here θ hides all poly-log terms.
PROOFS AND MORE RESULTS FOR $4: KERNEL APPROXIMATION
A.1 RANDOM SAMPLING REQUIRES EXPONENTIAL COST
The most natural idea of leveraging the samples is to add the constraints [lg("")] S L. For Gaussian kernel, we may sample from N (O, o² r) while for inverse kernel we may sample uniformly from B. This leads to our training objective:
A |l
min FEW
loss( (as(f())),))))))))
loss
s.t. (l((w))l L,
Vs [m].
Unfortunately, this method may require 0 samples to guarantee 2111 S. L2 + w.h.p. This is illustrated in Figure 6, where k is the polynomial kernel with degree 2 whose domain X is the unit ball B, and f(x) 1 (o r²) We seek to test whether the gradient g(x) (uTx) =)) y has norm
bounded by for all B, and are only allowed to test whether (g(l)) < 1 for samples w
that are drawn uniformly at random from B. This is equivalent to testing ||^|| S 1, and to achieve it least one w must be from the ball around v/ ||v|| or -v/ ||w|| intersected with B. But the probability of hitting such region decays exponentially with the dimensionality d.
The key insight from the above counter-example is that in fact ||e||| be easily computed by E. ? where {d the orthonormal basis computed from the Gram-Sclin Schmmit process on random samples (w" Id (n = d). With probability 1, n samples drawn uniformly from B d, i.e., rank(W) d where W (wl ...., w²). The Gram-Schmidt
must span Rd long process can be effectively represented using pseudo-inverse matrix (allowing n > d) as
||ا|| = ( w) -w)-1/2p1 1/2
2'
where ( T W the square root of the pseudo-inverse of W W. This is exactly the intuition underlying the Nyström approximation that we will leveraged.
A.2 SPECTRUM OF KERNELS
Let be a continuous kernel on a compact metric space X, and μ be a finite Borel measure on X with supplu] = X. We will re-describe the following spectral properties in general way than
20

---

Under review as a conference paper at ICLR 2020
W2
W1 W
polynomial kernel with degree 2, and f(z) x) for B. Then g(z) (u z)u. want to test whether supzeB 119(z) S by evaluating [[g(w)]|z on that is randomly sampled from B such as wh and 1/2, we must sample within the balls around the intersection of B and the ray along (both directions). See the blue shaded area. The problem, however, becomes trivial if we use the orthonormal basis {w1, (22)
Figure 6: Suppose
in $4. Recall from Chapter 4 of Steinwart Christmann (2008) that the integral operator for and Jr is defined by
To o 1 - (2(X,1)
where S (x( - C(X), (*+))=) = { - JE L2(,
4 C(X) + L2(X;u), inclusion operator.
By the spectral theorem, if Ty is compact, then there is an at most countable orthonormal set (ONS) (éyhies of L2(X,p) p) and {Xi bee with À 2 X2 2 .... such that
Tf
A (F. Es JEJ
fE p).
In particular, we have (ē,, Ex) Lx(x:)) dig (i.e., equals 1 i j, and otherwise), and Tē; A Since ēj is equivalent class instead of single function, assign set of continuous functions ej = x Skéz C(X), which clearly satisfies
(es, (2 = -ōj. Te, = Ayej-
We will call Ay and e, as eigenvalues and eigenfinntions respectively, and {eybee clearly forms an ONS. By Mercer's 's theorem,
k(x,8) = Σ (e),
(5)
JEJ
and all functions in H can be represented by Ejer where {a./ E (J). The inner product in H. is equivalent to (Eje Ejer byes Ejes Therefore it is easy to see that
= VTyej,
jEJ
an orthonormal basis of H. with Moreover, for all f E H with f Ejerajej, we have (f. (f.e,) az/>j, (f.4s) = a, VAy, and
f f= (f.eh) - Es
Most kernels used in machine learning are infinite dimensional, iec,, IN. For convenience, we define &.,, (491 (.P1...., Pm, and An diag(A,, ..,,g(...,,..........
21

---

Under review as a conference paper at ICLR 2020
A.3 GENERAL SAMPLE COMPLEXITY AND ASSUMPTIONS ON THE PRODUCT KERNEL
In this section, we first consider kernels ho with scalar input, i.e., Xo _ R. Assume there is a measure M4 on Xo. This will serve as the basis for the more general product kernels in the form of k<x,y) = [T= ko( Mjy defined over Xg.
With Assumptions and we now state the formal version of Theorem by first providing the sample complexity for approximating the partial derivatives. In the next subsection, we will examine how three different kernels satisfylunsatisfy the Assumptions I and 2, and what the value of N₂ is. For each case, we will specify po on Xo, and the measure on X6 is trivially je = 10-
Theorem Suppose {w=)==1
1==1 are drawn iid from (l0 on Xo. where Po is the uniform dis- tribution 1-v/2, u/2] for periodic kernels or periodized Gaussian kernels. Let Z (ko(w', .), koww? .)...., ku(w", :)), and 91 = = " X6 - R, where I I Sa and
vy (0- (y) (11 II j=2
Ko k1) with m9(-) == 80:1 ko ko (29..))
Given E (0. 1}. let nm ....... Pm) where No. Then with probability 8, the following holds when the sample size n max(Ne 5 N N. log 2N
8 ):
362
11 - p K17 + 3c1
1 2/ NoMo)
(6)
where (Ki)a,6 (hf) z(Z Z)- 1Z 2T M II 20(
Then we obtain the formal statement of sample complexity, as stated in the following corollary, by combining all the coordinates from Theorem 4.
Corollary 1. Suppose all coordinates share the same set of samples {w"}a= -==1- Applying the results in (6) for coordinates from I to d and using the union bound. we have that with sample size max N N.Q2 log 2N=), the following holds with probability 1- dõ,
Amax
(G Amax(G
S Amax (Pa) + 3e, (1+ 11+2/NA N.)..........
(7)
Equivalently, if Ne, Ms and Qe are constants or poly-log terms of E which we treat as constant, then to ensure Amaxx (G G) S Amax (Pa) + s with probability 1 - 8, the sample size needs to be
15 n n= Ee (
2 N. log 2dN
Remark 1. The first term on the right-hand side of (7) is explicitly upper bounded by L2 in our training objective. In the case of Theorem the values of Qs, Ng, and M, lead ( sample complexity. If we further zoom into the dependence on the period v, then note that N₂ is almost universal constant while M yFn (Ne 1). So overall. depends surprising because smaller period means higher frequency, hence more samples are needed.
by 3.2 This is not
Remark 2. Corollary 1 postulates that all coordinates share the same set of samples {w" )==1- When coordinates differ in their domains, we can draw different sets of samples for them. The sample complexity hence grows by times as we only use a weak union bound. More refined analysis could save us factor of d as these sets of samples are independent of each other.
Proof of Theorem 4. Let e' = (1+2//MM)) Since (9%, (h4, hi)m 1I (0(29.2)) and [ko(=]. ,B)l < 1, it suffices to show that for all a, b E [?].
(M) 14) (b 7 - n1 < 36'.
Towards this end, it is sufficient show that for any h(-) 9,, go. kn(w, -) + 8 g.) ko where xr E Xo and [0zl + |0,1 < 1, we have
h z(Z 2) -Z h |1/11200 SE
(8)
22

---

Under review as a conference paper at ICLR 2020
This is because, if so, then
(hi (1) Ho (h9) Z(ZTZ)-Z2''
(1 + Aill ||4 - -1147|1 (4.)) - 1
TT Z(Z z)- (11 + +1))
-(A9) T Z(Z (((zZ))-2
z) zT hi -(h) 7(2 T 2 All
1 < <7(1<' + +E') = =3'.
The rest of the proof is devoted to (8). Since 2 the SVD of Am 1/1 Φ where UU T U = VTV Im (m--y-m identity matrix), and
Z can be written as U EV,
Define
a 1/2V 1 1/1 T
h.
m
Consider the optimization problem o(a) : 1 hl] Ho objective value is o" == 1 | Ho.
It is easy to see that its minimal
1n T Z(T 2) - h. So
-7Th
2
0 M 20 = || Ho h -(==())=
2)-12 S 20(a))
Therefore to prove (8), it suffices to bound o(a) = 1Za -llxx. Since / f'm H T hi we can decompose 7 - h11 by
1Z h1 S [[ 2n T 2) 2) Ho + (00 - vrdl 1//2 )a
(9)
Ho
+ || TT - hilmo.
The last term |1 h - h1 hl11o Ho is clearly below e because by Assumption and m No
|| 2 h 1ol1zeo
< |00 (m m
kio(x, 0 go. kol,) + +10y1 TT m 0o.1 ko - g0.1 ko((,,) 1 Ho
<(10xr 10y))s Se.
We will next bound the first two terms on the right-hand side of (9).
(i) By Assumption || "m & TT (00www))) :))l S c, hence || F $ TT. ax Ho S
evnl ||x||2 To bound ||a]||2. note all singular values of VUT and so Assumption 2 implies that for all E [m].
| 1/2 (p)) Mm
= |ee, him (e,, )x, + 00000 ko(y, 00000.ko00 m)
(10)
(ez, 10,1,,201 -)= $ MM.
S sup x
As result,
[1 - D m
2) 2)a,) 11 Sent/2 n 1/2
-1120 To
1
S SEvmMe.
(ii) We first consider the concentration of the matrix R = 11 11-1/22 7.7 $m Am1mm 1/2 E RRmxm. Clearly,
R
E (w.)
(ws)e,
(1)))e =ōig-
{w.)
By matrix Bernstein theorem (Tropp. 2015, Theorem 1.6.2), we have Pr [|R- Im S$) 2
when 2 O(). This is because ... em < mQ? (ww,))) [RR"!1bgp S mm2 222//n and
-
Pr R Imlllpp $c) 2 21- 3-2mm -2mexp
2m exp
> 1
mQ2 (1 + +
5mQ2
23

---

Under review as a conference paper at ICLR 2020
where the last step is by the definition of n. Since R UT this means with probability 1 1 5, UUT Im lp So for all [m],
1 - - Se n
-1 +
which implies
Vn 0
-
1
<
S.
(1I)
n
Moreover, A I since xn) 1. then follows that
@ $ Z - v
not m 2/
)a
Mo
-UT
1m 1/2
vol 1/T VUT 1/220
Vn
m
Vn
140
1 Σ Im
U
1/2 A
(because TT = Im)
Vn
2
A1 max ic|m]
vn 01 1
<eVmM
(by (10), and A S 1).
Combining (i) and (ii), we arrive at the desired bound in (6).
Proof of Corollary Since Pg approximates GT G only on the diagonal, PG GT G a diagonal matrix which we denote as diag(61....., 68). Let u E R the leading eigenvector of Pg. Then
Amaxe (Pa) Amax (GT G) s u Pau u T Gu u T - G = E
(by (6)) 3c (1+2
The proof is completed by applying the union bound and rewriting the results.
A.4 CASE 1: CHECKING ASSUMPTIONS AND 2 ON PERIODIC KERNELS
Periodic kernels on Xo : are translation invariant, and can be written as ko(a, v) = <(x - y) where & IR + IR is a) periodic with period v; b) even, with x(-() = <<{); and c) normalized with x<0) = 1. A general treatment was given by Williamson et al. (2001), and an example was given by David MacKay in MacKay (1998):
lo v) = (xxpp220 1
sin sin(" (x -xxxx10 v) w))²)
(12)
202
We define No be a uniform distribution on [- 5. and let wi 2n /v.
Since R is symmetric, we can simplify the Fourier transform of r(t)) where (t( = 1 if t [-w/2, 2/2), and 0 otherwise:
v/2
F(w)= = 2T
1 x()) cos(wit) dt.
24

---

Under review as a conference paper at ICLR 2020
It is now easy to observe that thanks to periodicity and symmetry of k, for all E Z.
r/2
1 f k(x y) cos(jwov) dy
ko(z, v) cos(jway) dy v J//2
2/2
rt//2
x(z) cos(jwa(z 2)) dz (note cos(jwn( 2)) also has period v)
1/1122
/ x(=)[cos(jwoo) cos()woz) + sin(jwax) sin(jwoz)) dz (by periodicity)
12/
o/2
cos(jwor) /
12/2 x(2) cos(jauz) da (by symmetry of x)
2 F(jwo) cos(jwar))
And similarly,
1 12 | ko y) sin(jwoy) dy F(joo) sin(jwor).
22n
-n/2
Therefore the eigenfunctions of the integral operator T. are
cσ(x) 1, e;(x) = /2 cos(
e-j(x) == /2 sinn(wa) ( 2 1)
and the eigenvalues are X, V2= F(jwo) for all j E Z with A_, = >y. An important property our proof will rely on is that
c)(x) = j--ne- for all j E Z.
Applying Mercer's theorem in (5) and noting x(0) = 1, we derive >j Σjez>; 1.
Checking the Assumptions and 2. The following theorem summarizes the assumptions and conclusions regarding the satisfaction of Assumptions and 2. Again we focus on the case of X R.
Theorem 1. Suppose the periodic kernel with period has eigenvalues X3 that satisfies
2y(1 + 5)2 max(1,5²) + 8(j 1)) S ' for all j 2 0, where e4 > and cs > 0 are universal constants. Then Assumption holds with
(13)
v²2 2.cco max 1, 4T
N 1 + [me where ne -10%c
(14)
In addition, Assumption holds with Qe = /2 and Me = 2v/2a [na]
22a (N₂ - 1).
For example, if we set == and o² = 1 2/2 in the kernel in (12), elementary calculation shows that the condition (13) satisfied with C4 2 and Cs 1.6.
Proof of Theorem I. First we show that h(x) = 00.1 (o-koo is in Ho for all xo E Xo- Since ko(zo, x)) Ejez (o0) we derive
h(x)) Σ Aee, ez(x)
Σ - wp Σ A (15) jEZ
jEZ
jez
h(x)) is in H. if the sequence Ayje (zoo/ VAg is square summable. This can be easily seen by (13):
|1:111200 = Σ 2:12222 Σ 2,3222,(200
JEZ
Σ N to + Σ j244 <
204
=
-
JEZ
j21
25

---

Under review as a conference paper at ICLR 2020
Finally to derive Ng. we reuse the orthonormal decomposition of h(x) in (15). For given set of values A where A _ Z, we denote as & the "matrix" " whose columns enumerate the (yy over j E A. Let us choose
A j: A (1 (2) 8(j 2 1)) min w6 3) E²
2.1
If j E A, then
-j E A. Letting No = 10, J. we note Σjer, I+j 2.1. So
|| x 1 Pdo
= Σ
JEZiA
= = Σ
N31
(CG(()))+__(0001)2) 1)+ 0)
JENo'A
= Σ
X1 + 8(j 2 1))
JENo
=
Σ
(1 + 8) + +0 2 11) 1+
1
JEND
8²
1
62
Σ
1 1+ =
1
2.1
12
2.1
JENN
JENN
Similarly, we can bound (zo. .) - A 1 (20: 11 by
| -) - 1 /u 111
Σ 2se)(z0)
Σ
JEZiA
jEZIA
=
Σ Xa
2) 0)]
jENoiA
1
Σ
Xg max mmxx(,, 1)) 1 j2
jeNo\A
1
f2 S
2.1
JENO
To upper bound the cardinality of A, we consider the conditions for j & A. Thanks to the conditions in (13), we know that any j satisfying the following relationship cannot be in A:
8²
4x min 1,
C6 C4 1ll min(1, 2)
+
e²
2.1
2.1 co
D2
bi| < ). which yields the conclusion (14). Finally Qe S /2, and to bound Mg. simply reuse (15). For any j with |ا| ng,
So A C [j=
(h,, (/h, S wo (jee S 2T V2 [nc]]= = V2n (Ne - 1).
A.5 CASE 2: CHECKING ASSUMPTIONS 1 AND 2 ON GAUSSIAN KERNELS
Gaussian kernels k(x,y) = exp( |r y/ 2 (200)) are obviously product kernels with ku ku(#1, v1) = x(21 /1) exp(-(2)
/ (20 )). It also translation invariant. The spectrum
of Gaussian kernel kn on R is known; see, e.g., Chapter 4.3.1 of Rasmussen & Williams (2006) and
Section 4 of Zhu et al. (1998). Let y be Gaussian distribution (0,0 Setting e² =o² 22
26

---

Under review as a conference paper at ICLR 2020
in Eq 12 and 13 of E Fasshauer (2011), the eigenvalue and eigenfunctions are (for j 2 0):
' = Co
-j-1/2
where
Co
2 v5)
=
(3+
(x(x) 25/2 exp
52/8
V5
1
x²2
1
Hj
(V1.25 ))
4
0²
Vj!
where Hij is the Hermite polynomial of order j.
Although the eigenvalues decay exponentially fast, the eigenfunctions are not uniformly bounded in the Loo sense. Although the latter can be patched if we restrict 2 to bounded set, the above closed-form of eigen-pairs will no longer hold, and the analysis will become rather challenging.
To resolve this issue, resort to the period-ization technique proposed by Williamson et al. (2001). Consider k(z)) = exp(-x" / )2 when x E [-0/2, v/2), and then extend k to R as a periodic function with period Again let μ be the uniform distribution on [-v/2, As can be seen from the discriminant function / - 1 > :). as along as our training and test data both lie in [-v/4, v/ v/4 the modification of и outside [-v/2, v/2] does not effectively make any difference. Although the term 0 ko (xq, wi) in (13) may possibly evaluate x outside [-0/2, v/2), it is only used for testing the gradient norm bound of
With this periodized Gaussian kernel, it is easy to see that Q- = v2. If we standardize by = 1 and set v = 5e as an example, is not hard to see that (13) holds with Cq = 1.25 and cg = 50. The expressions of Ng and M, then follow from Theorem I directly.
A.6 CASE 3: CHECKING ASSUMPTIONS AND 2 ON NON-PRODUCT KERNELS
The above analysis has been restricted product kernels. But in practice, there are many useful kernels that are not decomposable. A prominent example is the inverse kernel: A(x, y) = (2-r' y) In general, it is extremely challenging to analyze eigenfunctions, which are commonly not bounded (Lafferty & Lebanon, 2005; Zhou, 2002), i.e., sup supg [ex(z)] oc. The opposite was (incorrectly) claimed in Theorem 4 of Williamson al. (2001) by citing an incorrect result in König (1986, p. 145), which was later corrected by Zhou (2002) and Steve Smale. Indeed, uniform boundedness is not known even for Gaussian kernels with uniform distribution on [0, 1] Lin et al. (2017), and (Minh et al., 2006, Theorem 5) showed the unboundedness for Gaussian kernels with uniform distribution on the unit sphere when d 2 3.
Here only present the limited results that have obtained on the eigenvalues of the integral operator of inverse kernels with a uniform distribution on the unit ball. The analysis of eigenfunctions is left for future work. Specifically, in order drive the eigenvalue X, below e, must be least d logg 1 +1 This is quasi--uaaratic bound if we view d and 1/s as two large variables.
It is quite straightforward to give an explicit characterization of the functions in H. The Taylor expansion of 2 at 2 is 2 -:=o(= )"xx". Using the standard multi-index notation with a = (01, aa) E (NU {0])d, |ax| Di= Ois, and x x
....T we derive
Bd ...
k(xx y) 2 y
1
Σ
2 (-x 4)* Σ 2-
oc
Ch a a:ja|=
Σ
k=
Σ
|a| -clll
a
where C*
k!
So we can read off the feature mapping for æ
I1 a.!
x = {waxa : a), where wa = 2 (1a +1) clol
and the functions in H are
dawa :100le }
H
(16)
Note this is just an intuitive "derivation" while a rigorous proof for (16) can be constructed in analogy to that of Theorem I in Minh (2010).
27

---

Under review as a conference paper at ICLR 2020
A.7 BACKGROUND EIGENVALUES OF KERNEL
We now use (16) to find the eigenvalues of inverse kernel.
Now specializing to our inverse kemeel case, let endow uniform distribution over the unit ball B: p(x) =V where Va I + 1)-1 is the volume of B, with I' being the Gamma function. Then À is an cigenvalue of the kernel if there exists f = Ea ta wa such that [yEB k(x, ())(y) dy = >f(x). This translates to
V
/
Σ
w a y
Σ 3
dauay dy = EawwaR V
WEB
α
Since B is open set, that means
Wa
uala+aU2 = Alla Va,
B
where
2 ( (2art))
V/ /
if all as are even
qa
yd dy
Va.(la|+d). [/101+
MEB
otherwise In other words, À the eigenvalue of the infinite dimensional matrix Q [Wa")ll++
A.8 BOUNDING THE EIGENVALUES
To bound the eigenvalues of Q, we resort to the majorization results in matrix analysis. Since k is a PSD kernel, all its eigenvalues are nonnegative, and suppose they are sorted decreasingly as À 2 A 2 .... Let the row corresponding to have & norm and let them be sorted as
Tn 2 [(2] 2 .... Then by Schneider (1953); Shi & Wang (1965), we have
n
1
II
VU 1.
So our strategy is to bound la first. To start with, we decompose qa+ into qa and qa via Cauchy- Schwartz:
Catp V==² (1
2
y ya dy S V
y 20x dy
y 23 dy = Q2a 92,3
yEB
yEB
yEB
To simplify notation, we consider without loss of generality that an even number, and denote
+ d k
d
the integer b = d/2. Now Va = n²' /bl. Noting that there are
values of 3 such that
( +d
+ 1 ). need
| k proceed by (fix below by changing because the former upper bounds the latter)
into
k
k
00
r2 wa 2 Σ
w
w39a+0
S w 224
Σ
w0g20 w
Σ
2 k-
C2q2
B
B:1B/=k
< w 12
2 k-1 (
k d d
C923 [13 =k
max Ihk
km0
+ d d
k!
I1 T(3: + +
= w
uaa2 12
2 k-1
max p
I == 3A
Va (2k: + +d) l'k + 4
k=0
k: 1
k!
r(3, + 2)
W (2a
3
V-1
2
d
(2k + d) + 9) |8|=
BA
k=0
b!
(k+ dd! (k + bJ!
<
2
12
7 bd!
2 k-1
(since r(3; + 1)) < r(8: + B.1).
k=0
28

---

Under review as a conference paper at ICLR 2020
The summation over can be bounded by
Σ
(k d)!
1
2d (122
bl
+
d (6))²} (bt2d + +20) s 6124
(A: + b)!
2
Σx=1 2- ( d k ) =22. Letting == |ax,, we can
(d+th
where the first equality used the identity continue by
24.
bl
1!
2 I'(a; + 5)) (b1)
bl2d = 2-1111
Ta
< w. 12a
I1 ag! Va (21 d) T(1 + b) x'd!
1!(bb)a
< 2
l+d π
(since I la; + + < I(a; + +) = a.!))
d!(l + b - 1)!(21 + d)
$ 2 14b 22-14b-1,
2b
1 1+b b
(since (bl)²
S b-
d!
1 d-1 (1+d-1) and N₂ -E=o 14
This bound depends on a, not directly Letting ni
(
d + L
) it follows that
L
E
1(1 d)! (d 1) Σ
(1+ d)!
Σ 1=0
In
d! 11
(d+ 1)(1-11
1=1
1=1
1 1+d d+1
) = =(d+1)
L [++++1 (1+t()) 2 )
=(d+1)
Σ
Now we can bound AN, by
N
L
2 1-1bb-1 I -26 (+bb] (1+))²)
<
1m1
[=0
-(1 - b+ log 2 - 2b log log ( 1 b
))
log ANz S N
Σ
l
1=0
S --N logg Σ ln
(since log 2 < 2log и as the coefficients of b)
d 1++++1
logg2 (d (d+11 ( d+
)
d+1
d+2
d+1 1
L, log 2
2+2
2
AN. 52-
This means that the eigenvalue X, S provided that Nr where [lgg 21. Since N₂ S db+11 that means it suffices to choose i such that
loka 17+1.
This a quasi-puoooe polynomial bound. seems tight because even in Gaussian RBF kernel, the eigenvalues follow the order of A.z O(c-lal) for some >> 1 (Fasshauer & McCourt, 2012, p.A742).
29

---

Under review as a conference paper at ICLR 2020
Max lipschitz constant (L-Bntt(LBBB)) (L-BFGS)
Nystrom (greedy)
Brute-force (greedy)
102
Nystrom (random)
Brute-force (random)
10a
3
100
10
10
102
Sample size
Figure 7: Comparison of efficiency in enforcing Lipschitz constant by various methods
EXPERIMENTS
A.9 EFFICIENCY OF ENFORCING LIPSCHITZ CONSTANT DIFFERENT METHODS
The six different ways to train SVMs with Lipschitz regularisation are summarized in Algorithm 1. Figure plots how fast the regularisation on gradient norm becomes effective when more and more points are added to the constraint set. We call them "samples" although it is not so random in the greedy method, modulo the random initialization of BFGS within the greedy method. The horizontal axis is the loop index in Algorithm and the vertical axis ( therein, which is the estimation of the Lipschitz constant of the current solution f(0) We used 400 random examples (200 images of digit and 200 images of digit 0) in the MNIST dataset and set = and RKHS norm ||/|| S oo
for all algorithms. Inverse kernel used, hence no results are shown for coordinate-we -wie Nyström.
Clearly the Nyström algorithm is more efficient than the Brute-force algorithm, and the greedy method significantly reduces the number of samples for both algorithms. In fact, Nyström with greedy selection eventually fell below the prespecified L, because of the gap in (9).
10 EXTENSION TO loo NORM ATTACKS FOR OUR KERNEL BASED METHOD
We now extend our kernel based approach for norm ball attacks. Since most multiclass losses are 1 1-Lipschitz continuous with respect to for norm on (x) ...., (1))))), f
we will seek
sup sup
[9 (z)
(x)
u L, where gx(x) : Vf
x u: [xll
The left-hand side (LHS) can be bounded by
sup max LHS
[1))(
< max
sup |. el1
# 1se510
1se5 |
Given the Nyström approximation G. Ge, we can enforce the convex constraint of
G 0/
max 1se5
sup [|l|2
I L.
30

---

Under review as a conference paper at ICLR 2020
A.11
MORE RESULTS ON CROSS-ENTRONE ATTACKS
Cemaly PODG 126) mererrt
Cemake (G2anae miseo
Cano (fGorsod exsred)
Tesaccraay
62
80
Testacuurary
69
liveee 156 poot-moott
Parless copeemeri
Test Testaccurary
40
80
20-
20
bg
Fg ball radius
(a) MNIST
(b) Fashion-MNIST
(c) CIFAR1O
Figure 8: Test accuracy under PGD attacks on cross-entropy approximation with &g norm bound
100
103
1.0
Tesaacinsy
C P.O COMMEEE
Text accunicy (%)
invess 146 3-nnsee
PED-mmar ParMadlee
accuuecyyy
40
83
83
42-
6.1
0.2
0.3
0.4
05
0.6
03
0.2
0.3
0.
0.5
0.
03
02
0.3
04
0.5
Fro
ball raclics
ball madiias
Ax
ball radins 5
(a) MNIST
(b) Fashion-MNIST
(c) CIFARIO
Figure 9: Test accuracy under PGD attacks on cross-entropy approximation with ex norm bound
A.12
VISUALIZATION OF GRADIENT
2
3
4
5
6
7
8
9
O
(
2
3
4
5
6
7
8
9
8
7
>
i
7
7
8
x
8
3
7
x
8
7
i
5
7
5
>
>
(a) E2 trained Par-MaxMin
Gauss-Lip with 2
Figure 10: Gradients of targeted cross-entropy loss with respect to imput images. One image per class (0-9) was sampled randomly from the test set, shown the first row. A black pixel is encoded by and white pixel by 1. The 10 rows below show the gradient for different class targets. For example, row 7 column shows the gradient of f" evaluated the image of digit shown at the top row. Red and blue stand for positive and negative pixel values, respectively.
A gradient-based based attacker tries to decrease the targeted loss by following the negative gradient in Figure 10b, i.c., reduce the pixel value in red area and increase pixel value in blue area.
In order to verify that the robustness of Gauss-Lip is not due to obfuscated gradient, we visualised "large perturbation" adversarial examples, with the lg norm upper bounded by 6. Figure 11 shows how the PGD attacker uses the gradients to perturb the images step by step. At the end of PGD, there are 46 cases where the original image was successfully attacked, i.c., turned into the target class. This over 50% of the total of 90 cases, and the resulting images look realistic.
31

---

2
3
4
5
6
7
8
4
0
2
4
5
6
7
4
0
2
3
5
8
0
/
2
3
4
5
8
4
/
2
3
4
5
6
7
9
6
Q
La
Lub
L
4
5
4
8
9
0
2
3
4
5
4
7
4
0
2
3
5
7
8
9
2
3
4
5
4.
8
4
2
3
4 4
5
4
7
8
4
4
2
4
5
1
7
2
3
5
3
5
6
8
6
4
7
2
4 4
4
8
4
O
2
3
7 7 6 6 5
5
O
2
3
5
7 7
8
O
3
4 4
5
8
2
3
1 4
6
7
9
4
3
5
O
2
2
4
1 5 5
5
9
0
2
2
5 5
1
9
0
2
2
5 5
4
8
9
O
2
2
5
7
8
4
45476
8
R
4
0
0
7
4
8
3
4 4
7
/
2
3
566
0
2
3
0
2
3
5
4
0
(
2
2
5
4
8
4
O
E
2
9
5
7
/
R
4
6
R
> 7
0
3
0
3
6
8
5
5
6
7 7
/ /
2 2
3 3
4
5
7
8
0
2
3 3
4 4
4
0
2
3
5
7
8
0
2
3
5
7
8
4
6
2 7
3
5
0
6
4
0
7 8
4
8
0
7
3
6
99
0
3
5
4
8
0
7
6
8
5 5
7 7
0
8
3
5
7
3
5
8
7
4
0
/
2
3
8
0
(
Q
3
8
O
3
5
7
8
0
9
3
5
l
8
3
9
5
1:
7
0
iteration
iteration
iteration 3
iteration 4
iteration 5
2
8
4 4
0
2
5
7
4
O
2
3
8
0
/
3
5
8
(
2
4
6
7
8
IR
#
4
0
1.0%
H
1p
M
4
1
7
8
4
0
2
4
5
1
7
9
0
2
3
5
7
8
(
3
4
5
7
8
9
(
2
3
4
5
11
7
8
2
4
5
6
0
4
2
3
4
5
1
7
9
8
2
3
5
1
4
6
2
6
5
4
0
9
2
3
0
5
6
7 2 4 4
4
4
2
5
>
O
3
5
3
8
1
4
7
O 2
2
2
5
2
8 4
O
2
2
5
2
2
0 4
O
2
5
2
2 > 7
8
0
2
2
2
5
2
8
2
O
2
2
2
5
2
2
7
R
3
R
5
6 4
> 7
O
3
R
5
0
3
3
5
6
3
3
2
3
6
3
( R
9
9
0
R
9
5
4
O
4 S
9
5
4
O
4
5
4
7
4
4
4
7
O
/ 7
3
5
4
7
5
0
3
5
7 >
5
6
3 3
5
4
5
6
5
S
3
5
4
7
5
5 6
S
3
5
6
7
5
4
6 R
4 7
7 4
0
R
6
5
0
4
6
5
7
0
3
5
6
6
7
0 7 7
7
5
8
0
7
7 8
7
4
8 4
0
7
7
1
8
0
7
7
5
8
4
O
7
7
5
0
8
8
4
5
0
8
5
0
8
8
5
8
8
8
/ 3 4
9
>
8
0
9
3
5
6
>
O
9
2
5
> 8
0
9
3
5
6
>
8
9
3
9
5
7
9
iteration 6
iteration
iteration 8
iteration 9
iteration 10
2
3
4
8
9
3
2
2
5
0
2
3
5
3
3
9
4
5
4
7
9
0
8
8
8
5
8
8
prediction of Gauss-Lip
Figure 11: Gradients and perturbed images at each iteration in a 10-step PGD attack using (targeted) cross-entropy approximation, with the l norm upper bounded by 6. Here the classifier is Gauss-Lip (a = 2). The table in the bottom right presents the final predictions of our trained Gauss-Lip on the perturbed images.

---

Under review as a conference paper at ICLR 2020
2
3
5
7
8
0
2
3
4
5
6
7
8
9
0
0
3
>
0
0
0
0
0
6
7
0
0
2
3
5
6
7
9
2
6
8
O
2
2
A
5
2
2 3
2
0
2
2
2
5
2
2
2
2
O
3
3
3
3
3
3
3
3
3
3
3
O
+ H 4
4 5
4
0
4
4
4
5
4
4
4
4
5
5
$255
5
5
5
5
5
5
7
5
5
6
6
5
766
6
6
6
6
6
5
7
6
6
Q 7
3
5
7
0
7
7
7
7
5
7
7
8
8
8 9
8
8
8
8
8
8
8
8
8
8
Q
9
9
9
5
9
Figure 12: Left: perturbed images the end of 100-step PGD attack using (targeted) cross-entropy approximation. Right: classification on the perturbed image given by the trained Gauss-Lip Lipuss--p.... They quite consistent with human's perception the left images.
2
3
4
5
6
7
8
9
9
2
5
5
4
8
5
4
8
9
2
5
5
4
8
5
4
8
9
2
5
5
4
8
5
4
6
8
9
2
5
5
4
8
5
4
5
8
9
2
5
5
4
8
5
4
5
8
9
2
5
5
4
8
5
4
5
8
9
2
5
5
4
8
5
4
5
8
9
2
5
5
4
8
5
4
5
8
9
3
5
5
4
8
5
4
5
8
9
2
5
5
4
8
5
4
Figure 13:
Perturbed images at the end of 100-step PGD attack using (untargeted) C&W approxi-
mation. The 11 rows show the images after 0, 10, 20, 100 steps of PGD.
To further look into the attack result, increased PGD to 100 iterations. As shown in Figure 12, now the number of misclassified cases (i.e., unsuccessful attacks that failed to turn an image into the targeted class) drops from 46 to 22, of 90 cases. The final images are quite realistic. We will further study these remaining cases in the future.
In the above experiments for Figures 11, 12, and 14, PGD was run on the cross-entropy objective. For example, the row corresponding to class 4 tries to promote the likelihood of the target class 4. Naturally the diagonal is not meaningful, hence left empty.
We further ran PGD for 100 iterations on C&W approximation (an untargeted attack used in Figure 3), and the resulting images after every 10 iterations are shown in Figure 13. Here out 10 images were eventually turned into a different but untargeted class, and the final images are very realistic.
Another random set of images. To test if the above result is due to the particularly hard images selected, we randomly selected another set of images and its results for 100-step PGD on cross- entropy objective and C&W objective are shown in Figures 14 and 15, respectively. Interestingly, C& W attack succeeds on all these images, and cross-entropy attack was only unsuccessful in turning 0 into 1.
33

---

Under review as a conference paper at ICLR 2020
0
2
3
4
5
6
0
2
3
4
5
6
7
8
9
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
1
1
1
2
2
2
2
2
2
2
2
a
2
2
2
2
2
2
2
2
2
3
3
3
3
3
3
3
3
3
3
3
3
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
5
5
5
5
5
5
5
5
5
5
5
6
6
6
6
6
6
6
6
6
7
7
7
7
7
7
7
7
7
7
7
7
8
8
8
8
8
8
8
8
8
8
8
8
8
9
9
9
9
9
4
9
9
9
9
9
9
9
9
9
Figure 14: (Another random trial) Left: perturbed images the end of 100-step PGD attack using (targeted) cross-entropy approximation, Right: classification on the perturbed image given by the trained Gauss-Lip. They are quite consistent with human's 's perception the left images.
0
2
3
4
5
7
6
9
0
5
5
5
3
5
5
$
7
2
8
5
5
5
3
5
5
5
7
2
8
5
5
5
3
5
5
5
2
8
5
5
5
3
5
5
57
2
8
5
5
5
3
5
5
5
2
8
5
5
5
3
5
5
5
2
8
5
5
5
3
5
5
5
2
8
5
5
5
3
5
5
57
2
8
5
5
5
3
5
5
5
2
8
5
5
5
3
5
5
5
7
Figure 15: (Another random trial) Perturbed images at the end of 100-step PGD attack using (untargeted) C&W approximation. The 11 rows show the images after 0, 10, 20, ..., 100 steps of PGD.
Please note that despite the commonality in using the cross-entropy objective, the setting of targeted attack in Figures 11, 12, and 14 is not comparable to that Figure 8a, where to enable batch test mode, untargeted attacker was employed by increasing the cross-entropy loss of the correct class, ie., decreasing the likelihood the correct class. This is a common practice.
34


Reviews:
[{"review_id": "rkgBsPb3tS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors propose a distributional robust risk minimization method using Lipschitz regularization and give an approach to approximate the Lipschitz constant for product kernels efficiently.\n\nMy major concerns are as follows.\n1. The result in Theorem 1 is similar to Theorem 3 in [1]. The authors use McShane–Whitney extension theorem [2] to generalize the previous result, which is a trivial derivation.\n2. Although the proposed method is theoretically applicable for a wide class of models, it is hard to use in practice, since the Lipschitz constant is too hard to compute exactly. To address the problem, the authors give an approach to approximate the Lipschitz constant for product kernels efficiently. However, the applicability of the method is still limited if it can be used only for product kernels.\n3. In the abstract, the authors claim that this paper resolves the previous methods' limitations for deep neural networks. However, there is no corresponding theoretical analysis.\n4. Some notations are confusing. For example, in the second paragraph on Page 3, there are two different sets denote $cost_c$; in the definition of $cost_c(\\mu,\\nu)$, the meaning of the symbol $\\Pi$ is unclear; in Theorem 2, the symbol $|\\cdot|$ is not defined.\n\n[1] Aman Sinha, Hongseok Namkoong, and John Duchi. Certifying some distributional robustness with principled adversarial  training. In International Conference on Learning Representations (ICLR), 2018.\n[2] Iosif Petrakis. Mcshane-Whitney extensions in constructive analysis. arXiv preprint arXiv:1804.06757, 2018.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "SJllbcg0KH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper uses results from distributional robustness to provide bounds of p-norm-constrained adversarial risk which depend on the Lipschitz constant of the underlying classifier. The bulk of the paper focuses on sample-efficient mechanisms to approximate the Lipschitz constants of kernel methods so that a constraint on this Lip constant can be enforced during training. Empirically, the kernel methods are compared to existing deep learning approaches and are shown to be competitive at this scale.\n\nOverview:\n\nThis is a technical paper which draws on theoretical results in Kernel methods, distributional robustness, and numerical approximation. I have been unable to verify the correctness of results from all of these areas but to the best of my knowledge the results seem reasonable. Despite the technical depth, the paper is well-written and largely easy to follow.\n\n1) In section 3.1 you should emphasize the threat model more clearly. Distributional robustness may provide tools to evaluate very general forms of adversarial risk but in this work only the p-norm ball threat model is considered. This is a fine restriction and theoretical statements are made correctly but this does not encompass all forms of adversarial risk.\n\n2) I had a hard time understanding Figure 1. The adversarial risk (Eqn 3) is upper-bounded by the variable-radius risk (Eqn 4 LHS) but Figure 1 shows that the adversarial risk of radius $r$ may permit larger perturbations than the variable-radius risk. Could you please explain how this Figure should be interpreted? The caption and main-text description of the Figure are very slim.\n\n3) I like Figures 2 and 3 as they clearly highlight the benefits of both DRR and the proposed approximations in this work. This paper already presents thorough theoretical analysis but a further analysis into the conditions required for $\\lambda_{max}(G^T G)$ to guarantee tighter bounds on the Lipschitz constant would be a valuable addition.\n\n4) Unfortunately I was unable to follow the analysis in Section 4.1 due to a lack of prior knowledge. To my understanding, the per-dimensional product factorization allows cheap exact computation of the off-diagonal elements of $G^T G$. This means that only the diagonal elements need be computed by the Nystr\\\"om approximation. However, I cannot see intuitively how this prevents the sample complexity from scaling with the dimensionality (the number of diagonal elements still grows with $d$).\n\n5) The experimental set-up is mostly standard with the exception that the CIFAR-10 robustness is measured with respect to a learned representation. This is a reasonable setting for validating the theoretical contributions of this work but is not a realistic interpretation of the adversarial threat model considered. The Lipschitz constant of the embedding function (the pre-trained ResNet) is not known and will likely lead to vacuous bounds (for robustness with respect to the input-space).\n\n6) The deep learning experiments utilize the Parseval networks regularization scheme. What is the regularization constant ($\\beta$) used for this method? Typically, a small $\\beta << 1$ value is chosen which enables easier learning but prevents the Lipschitz constant from being tightly enforced during training. Is the final Lipschitz constant upper-bound computed from the learned weight matrices to ensure that the orthogonality constraint is not violated?\n\n7) There is some disparity between the experimental results presented and the theory in the paper. In particular, this paper explores methods to provide robustness certificates to Lipschitz bounded classifiers but does not compute and validate these certificates empirically.\n\n8) The gradient visualizations were surprising to me. The Par-MaxMin model has interpretable gradients in that the target class is visible through the gradients. However, for the Gauss-Lip model the gradients seem to only depend on the images current class and are suggestive of a form of gradient obfuscation. It may be useful to visualize \"large perturbation\" adversarial examples for the Gauss-Lip classifier --- what characteristics do these images have? Similarly, one could generate so-called \"Distal Adversarials\" which are generated by sampling random noise and optimizing them towards a target class. Does the Gauss-Lip model generate realistic looking images or is noise classified accurately?\n\n9) Overall, the experiments seem sufficient to conclude that the Gauss-Lip model is a promising approach to adversarial learning. It is not clear how this method could be scaled to high dimensional data (while there are more obvious avenues for the deep learning alternatives).\n\n\nMinor:\n\n- In Theorem 1 statement, \"If additionally if $\\ell_f$ is convex\".", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1gwSPq6KH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Through the lens of Distributional Robust Risk (DRR), this work draws a link between adversarial robustness and Lipschitz constant regularisation. The authors first provide an upper bound of the DRR (with a Wasserstein ball as the ambiguity set) in terms of the true risk and the Lipschitz constant of the loss function under the current model. They show that the standard adversarial risk can be upper bounded by the DRR, emphasizing that the Lipschitz constant regularised loss can be used as a proxy for adversarially robust training.\n\nThe authors then apply this idea to kernel methods and aim to minimise the true risk under a Lipschitz constant constraint. By using a bound between the Lipschitz constant and the largest eigenvalue of the Gram matrix, and by approximating the Gram matrix using Nystrom approximation, they express the Lipschitz constant constraint as a convex constraint. In the case of multiplicative kernels, this approach is shown to be efficient when only using a polynomial number of sample points for the Nystrom approximation.\n\nThis method is tested on 3 standard datasets and is shown to outperform state-of-the-art deep learning based approaches over a wide range of perturbation in both l_2 and l_infinity norm. \n\nI have concerns about the novelty of the two main contributions of this work, which are Theorems 1 and 2:\n* Theorem 1 is a direct implication of Kantorovich duality, well known in optimal transport.\n* Theorem 2 is a rewriting of Proposition 3.1 in [1], which is not cited.\n\nMy second concern is that the value of n (number of sample points used in Nystrom approximation) has not been specified for the presented experiments (unless I missed it). This is an important parameter to specify since the algorithm requires to invert an n by n matrix when applying Nystrom approximation, and scalability is usually the main criticism to kernel methods.\n\nWhen comparing the methods, would it be possible to estimate the Lipschitz constants of the models trained by the various algorithms ? This would enable to observe the true effect of the methods on the Lipschitz constant.\n\nDue to these two concerns above, I tend to reject this submission.\n\nA few comments about clarity:\n\n* It would help to provide the full kernel method algorithm (with more detail than Algorithm 1 in Appendix), e.g., explicit the convex constraint on gamma when training the SVM.\n\n* epsilon notation is used both for the accuracy in the Lipschitz constraint (as in Theorem 3) and the adversarial perturbation (as in equation 3 or Figures 4 and 5). In page 7, paragraph 'Attacks', delta is used once for denoting the perturbation, but epsilon is reused just after. More consistency in the notation would be greatly appreciated.\n\n* It is not clear in the main text that L is a bound on the gradient norms at sample points. It is made clearer in the appendix, so one sentence from the appendix should be added to the main text.\n\n\nTypos:\n* p.6 top: \"and analogously for ...(x_1^a,.)\" instead of '(x_1^b,.)'\n\n[1] Distributionally Robust Deep Learning as a Generalization of Adversarial Training, M. Staib, S. Jegelka, NIPS, 2017", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This works relates adversarial robustness and Lipschitz constant regularization. After the rebuttal period reviewers still had some concerns. In particular it was felt that Theorem 1 could likely be deduced from known results in optimal transport, and it would be nice to make this connection explicit. There were still concerns about scalability. The authors are encouraged to continue with this work, considering the above points in future revisions.

Decision: Reject