Title: Optimising Network Architectures for Provable Adversarial Robustness

Abstract: Existing Lipschitz-based provable defences to adversarial examples only cover the 2 threat model. We introduce the first bound that makes use of Lipschitz continuity to provide a more general guarantee for threat models based on any p norm. Additionally, a new strategy is proposed for designing network architectures that exhibit superior provable adversarial robustness over conventional convolutional neural networks. Experiments are conducted to validate our theoretical contributions, show that the assumptions made during the design of our novel architecture hold in practice, and quantify the empirical robustness of several Lipschitz-based adversarial defence methods.

1. Introduction:

The robustness of deep neural networks to adversarial attack (Szegedy et al., 2014) is an increasingly topical issue as deep models are becoming more widely deployed in practice. This paper focuses on the problem of ensuring that once a deep network trained for image classification has been deployed, one can be confident that an adversary has only a limited ability to maliciously impact model predictions when they tamper with the system inputs. Such malicious inputs, so-called adversarial examples, appear to humans as normal images, but in reality they have undergone imperceptible modifications that cause a model to make an incorrect prediction. In contrast to many empirically focused approaches to defending against adversarial interference (see Carlini & Wagner (2017) and Athalye et al. (2018) for more details), we look to the trends prevalent in cryptography research, where developing provable defences is the primary modus operandi. The analysis in this paper makes use of the Lipschitz properties of neural networks to accomplish this.

We begin by extending existing theory addressing the relationship between Lipschitz continuity and provable adversarial robustness. Using insights from the resulting bounds, it is shown how one can adjust network architectures in such a way that Lipschitz-based regularisation methods are more effective. Experimental results show that, while having little difference in empirical adversarial robustness compared to existing Lipschitz-based defences, our approach improves the level of provable robustness significantly. We also provide evidence that indicates adversarial training has only a small penalising effect on the upper bound of the Lipschitz constant of a network currently used by most works.

2. Related Work:

There are several papers in the literature on deep learning that address adversarial robustness through the use of Lipschitz continuity, however they focus solely on perturbations with bounded Euclidean norm. Tsuzuku et al. (2018) present an efficient method for determining whether an example could have been tampered with at test time or, conversely, certify that a prediction has not been influenced by an adversarial attack. They compare the prediction margin normalised by the Lipschitz constant of the network to the magnitude of the largest perturbation allowed by the threat model, allowing them to determine whether the input could be an adversarial example. Farnia et al. (2018) show how the adversarial risk can be bounded in terms of the training loss by adapting the bound of Bartlett et al. (2017) to consider perturbations to the margin, using a similar technique to Tsuzuku et al. (2018) .

The analysis in this paper takes a similar high-level strategy-making use of margins and Lipschitz constants-but we extend this theory to threat models based on arbitrary p-norms, and provide a simpler proof than Tsuzuku et al. (2018) . Huster et al. (2018) demonstrate that current methods for regularising Lipschitz constants of networks have deficiencies when used for improving adversarial robustness. Specifically, it is shown that existing approaches for regularising the Lipschitz constant may be too restrictive because the bound on the Lipschitz constant is too loose, resulting in over-regularisation. In anticipation that future work can provide improved upper bounds on the Lipschitz constant of a network, we provide theoretical and practical contributions that are compatible with arbitrary bounds.

Existing work that aims to provide theory-backed guarantees for adversarial robustness has resulted in several techniques able to certify whether a prediction for a particular example is immune to adversarial attack under a threat model based on p -norm perturbation size. Weng et al. (2018) propose a method that can only be applied to networks composed of fully connected layers with rectified linear units activation functions, and no batch normalisation. Wong & Kolter (2018) present an approach based on solving an optimisation problem. While the robustness estimates they give are considerably tighter than many other certification methods, they scale very poorly to networks with large input images or feature maps. In contrast to these methods, our approach bounds the expected adversarial generalisation error, has virtually no test-time computational overhead, and can be applied to arbitrary feed-forward architectures. Bounding the expected generalisation error enables us to give guarantees about the level of robustness a model will have once it has been deployed. Existing approaches to provable robustness do not come with such guarantees, and can only provide certification for individual instances.

3. Generalisation Under Attack:

Methods for estimating the generalisation performance of learned models typically assume examples, ( x, y), observed at both training and testing time are independently drawn from the same distribution, D. Such methods estimate or bound the expected risk, R (f ) = E ( x,y)∼D [ (f ( x), y)],

(1) of a classifier, f , with respect to some loss function, . The standard technique for estimating the expected risk in deep learning is to use an empirical approximation measured on a set of held-out data. Literature on statistical learning theory often investigates the related problem of quantifying worst-case generalisation performance. This is typically accomplished by deriving bounds expressed in terms of the empirical risk measured on the training data, and a term related to some measure of complexity of the hypothesis class.

In the adversarial setting one must consider the expected risk when under the influence of an attacker that can add perturbations to feature vectors at test time,

EQUATION

which is known as the adversarial risk (Madry et al., 2018) . In contrast to the expected risk, RL p,t (f ) cannot be reliably approximated from data when f is non-convex, as one must find the globally optimal setting of for each data point in the held-out set.

For a hypothesis, f , that produces a vector of real-valued scores, each associated with a possible class, we define the margin function as

EQUATION

where f i ( x) is the ith component of the output of f ( x). Typical loss functions for measuring the performance of a model via composition with the margin function include the zeroone loss and the hinge. These compositions result in the classification error rate and the multi-class hinge loss variant proposed by Crammer & Singer (2001) , respectively. Proposition 1. If f is k-Lipschitz with respect to the p-norm and : R → R + is a monotonically decreasing loss function, then max

EQUATION

)

where q is defined such that • q is the dual norm of • p .

Proof. Note that one can define the margin function given in Equation 3 as m f ( x, y) = m I (f ( x), y), where I is the identity function. The Lipschitz constant of m I with respect to its first argument when using the p-norm is max x ∇ x m I ( x, y) q (Shalev-Shwartz, 2012, p. 133). The gradient of m I is a vector with all elements set to zero, except for those corresponding to the largest and second largest components of x. These components of the gradient take the values of 1 and -1, respectively. Plugging these values into the definition of vector p-norms, one arrives at a Lipschitz constant of 2 1/q . From the composition property of Lipschitz functions, we can say that m f is (2 1/q k)-Lipschitz with respect to x. The Lipschitz property of m f can be used to bound the worst-case change in the output the margin function for a bounded change in the input, yielding ( min

EQUATION

From the decreasing monotonicity of , we have that

EQUATION

which concludes the proof.

This proposition bounds the worst-case change in loss for a single image in terms of prediction confidence, Lipschitz constant of the network, and the maximum allowable attack strength.

The relationship given in Proposition 1 is a more general form of the bound derived by Tsuzuku et al. (2018) , who consider only the Euclidean norm. Gouk et al. (2018) provide efficient techniques for computing upper bounds to the Lipschitz constant of feed-forward networks with respect to the 1-, 2-, and ∞-norms. Golowich et al. (2018) present a bound on the Rademacher complexity of deep networks that is primarily dependent on the same quantity that Gouk et al. (2018) show to be an upper bound on the ∞-norm Lipschitz constant. They do not make use of Lipschitz properties to prove this, so tighter bounds on the Lipschitz constant will not necessarily improve the bound on Rademacher complexity. These two pieces of related work, coupled with Proposition 1, imply that empirical risk minimisation with a Lipschitz-based regularisation method is a principled approach to controlling adversarial risk.

Proposition 1 can be extended to provide a non-trivial bound on the expected adversarial risk through the use of a held-out dataset and a simple application of McDiarmid's inequality. Although this is not a standard approach to take in learning theoretic generalisation bounds, it is a practical tool that can be used for quantifying worst-case adversarial robustness that is of great utility to practitioners. Proposition 2. If f is k-Lipschitz with respect to the p-norm, : R → [0, B) is a monotonically decreasing loss function, and {( x i , y i ) ∼ D} n i=1 is independent of f (i.e., held-out data), the following holds with probability at least 1 -δ:

EQUATION

)

where q is defined such that • q is the dual norm of • p .

Proof. Constructing a mean over loss terms applied to i.i.d. samples from D,

EQUATION

results in a Doob martingale where each term is bounded by 1 B . This allows McDiarmid's inequality to bound the probability of the difference between the summation and its expected value exceeding some threshold,

EQUATION

)

Setting δ equal to the right-hand side of Inequality 9 and solving for γ yields

EQUATION

Thus, we can say with confidence 1 -δ that

EQUATION

)

Applying Proposition 1 to each term of the summation, L, concludes the proof.

Proposition 2 extends the result of Proposition 1 from the loss on a single instance to the expected risk.

In practice, this means that a practitioner can bound the worst-case adversarial performance of their model based on its (non-adversarial) validation-set performance and its Lipschitz constant, both of which can be measured efficiently. As we show later, this can lead to non-vacuous bounds on error rate, which in turn could allow a user to deploy a model with provable confidence about its performance under adversarial attack-without the hassle and computational expense of instance-wise certification at run-time (Weng et al., 2018; Wong & Kolter, 2018) .

4. Architectures for Provable Robustness:

The analysis in Section 3 motivates a high-level strategy for improving the adversarial robustness of neural networks: maximise the prediction margin while minimising the Lipschitz constant of the model. Several papers have proposed different methods for regularising the Lipschitz constant of a network, with various motivations, including improving robustness to adversarial exmaples (Tsuzuku et al., 2018; Cisse et al., 2017) and improving generalisation performance in the non-adversarial case (Gouk et al., 2018) .

We propose a strategy for modifying network architectures to make them more amenable to Lipschitz-based regularisers: splitting a single multi-class classification network into a collection of one-versus-all (OVA) classifiers that each produce a real-valued score. Unlike the conventional OVA method, where each component classifier is trained in isolation, the networks used in our approach are still trained jointly using a softmax composed with the cross entropy loss function. The core assumption this approach is predicated on is that each of the binary classifiers needs to solve a simpler problem than the original multi-class classification task. Gouk et al. (2018) show that the Lipschitz constant is related to model capacity, so the subnetwork associated with each class should be able to achieve high accuracy with a smaller Lipschitz constant than a conventional multi-class classification network. This makes such an architecture more amenable to Lipschitz-based regularisation, and hence provable robustness via Proposition 2.

Consider the vector-valued function,

EQUATION

)

where C is the number of classes, and f i is k i -Lipschitz. We have from the Lipschitz property of each f i that

EQUATION

from which we can deduce that the Lipschitz constant of the one-versus-all classifier is the p norm of the vector of Lipschitz constants corresponding to each binary classifier. In the case of the ∞-norm, the largest Lipschitz constant associated with a single binary classifier dictates the Lipschitz constant of the entire OVA classifier.

4.1. Lipschitz Regularization Training:

We investigate two approaches to controlling the Lipschitz constant of neural networks. The first approach we use is to add the bound on the Lipschitz constant as a regularisation term to the objective function, resulting in

EQUATION

)

where d is the number of layers in the network and • p is the operator norm induced by the vector p-norm. In the case where p is two, the operator norm is the largest singular value of the matrix (i.e., the spectral norm). For p = ∞, it is the maximum absolute row sum norm (Gouk et al., 2018) ,

EQUATION

)

The other regularisation technique we consider is the method proposed by Tsuzuku et al. (2018) , which can be adapted to regularise the ∞ Lipschitz constant by using the norm in Equation 16, rather than the spectral norm.

5. Experiments:

This section presents the results of numerical experiments that demonstrate the tightness of the bounds presented in Section 3, provides evidence that the architecture proposed in Section 4 is inherently easier to optimise for provable robustness than conventional network architectures, and evaluates the empirical robustness of Lipschitz-based defence methods. The models used in these experiments were implemented using Keras (Chollet, 2015) , and the adversarial attacks were performed using the CleverHans toolkit (Papernot et al., 2016) .

5.1. Tightness of the Bound:

The bound given in Proposition 2 provides a way to estimate the worst-case performance of a model when under the influence of an adversary. In order to validate this bound empirically, we train linear support vector machines with different levels of 2 regularisation on the MNIST dataset of hand-written digits. In the case of linear SVMs, the optimisation problem solved by iterative gradient-based attacks, such as the projected gradient descent method of Madry et al. (2018) , are convex and can therefore be solved globally. This means the the empirical adversarial risk can be computed exactly. Plots indicating the tightness of the bound for linear SVMs are given in Figures 1 and 2 . These were generated by training models on the first 50,000 instances of the training set, using the other 10,000 training instances as the held-out data required for computing the bound, and using the PGD attack when evaluating the network on the test data. These plots confirm that the bound proposed in Proposition 2 is non-vacuous and has the potential to be useful in practice.

5.2. Provable Robustness:

We first experiment on MNIST to determining whether our proposed OVA networks achieve better provable robustness than conventional convolutional neural networks. To control for the potentially confounding factor of model capacity, a series of networks with different widths are trained. We define the width of a conventional convolutional network as the number of feature maps produced by the first convolutional layer. For OVA networks, the width is the number of feature maps produced by the first layer in a single binary classifier, multiplied by the number of binary classifiers. For both network types, the chosen architectures contain two convolutional layers, the second of which has twice the number of feature maps as the first. Each convolutional layer contains 5 × 5 kernels, rectified linear unit activation functions, and is followed by a 2 × 2 max pooling layer. After the convolutional layers are two fully connected layers: one with 128 hidden units, and another with either 10 units (for conventional networks), or one unit (for OVA networks). Figures 3 and 4 show how the number of feature maps in each layer of the networks impacts the provable adversarial robustness for the 2 and ∞ norms under different threat models, respectively. The models in these plots are regularised using the Lipschitz penalty method proposed in Section 4. These figures show that: (1) Regularised OVA networks exhibit superior provable robustness compared to regularized conventional CNNs at comparable model sizes, (2) The magnitude of this margin becomes more pronounced as model size increases, (3) All methods have low error rate for unperturbed examples (left plots).

To investigate how well OVANets scale, additional experiments are run on the CIFAR-10 dataset, using VGG-style networks (Simonyan & Zisserman, 2014) as the base architecture. The baseline CNN uses the VGG11 architecture, and each subnetwork of the OVANet architecture is a VGG11 network with half the number of feature maps in each layer. Table 1 provides probabilistic (95% confidence) bounds on the worst-case adversarial error rate using Proposition 2. Table 2 shows the corresponding provable robustness results for SVHN benchmark. From the results we can see that: (1) Lipschitz penalty training improves the adversarial error rate for both vanilla VGG11 and VGG11-OVANet (performance improves with λ); (2) VGG11-OVANet generally has superior provable robustness compared to vanilla VGG11 for corresponding regularisation strength, especially for strong attacks. (3) Meanwhile, regularized OVANet achieves comparable results to a regularized CNN in terms of clean data performance.

5.3. Empirical Robustness:

OVA networks exhibit superior provable robustness compared to conventional networks, but it does not immediately follow from this that their empirical robustness will also be improved. We investigate this by using the PGD attack of Madry et al. (2018) to attack networks defended with Lipschitz Margin Training (LMT), the Lipschitz penalty regulariser (LP), and no defence. For each method, the best performing architecture is chosen by measuring the empirical robustness of the validation set. The set of architectures considered are the same as those discussed Figures 3 and 4 . The results are given in Tables 3 and 4 for the 2 and ∞ norms, respectively. For the 2 norm, the OVA networks perform similarly to their conventional counterparts from an empirical standpoint, but with improved provable robustness. For the ∞ norm, we do not observe an empirical benefit from using OVA networks over conventional network architectures. However, our adaptation of Lipschitz-based regularisation to the ∞ setting does improve empirical robustness noticeably over the undefended network-particularly when using our novel penalty approach given in Equation 15, rather than LMT.

Table 5 shows the upper bound on the Lipschitz constants of each model for which we have reported empirical robustness measurements. From this table, we can see that both Lipschitz-based defences successfully limit the constant of each network-sometimes by several orders of magnitude. Using an OVA network architecture, in most cases, results in another modest decrease in the Lipschitz constant when using a Lipschitz regularisation method, and a substantial decrease when no regulariser is applied. 

6. Conclusions:



:



Figures and Tables:

Figure1: Plots demonstrating the relationship between the provable upper bound on adversarial risk, and the actual misclassification rate on the test set under adversarial attack. Linear SVM recognition on MNIST with 2 threat model and regularization strength λ.

Figure 3: Comparison of provable adversarial risk for conventional CNN versus OVANet trained with Lipschitz penalty regularization over a range of model sizes. The 2 Lipschitz constant is used for regularisation and computing the bound. OVANet shows superior provable robustness, especially at larger model sizes.

This paper presents a p-norm-agnostic theoretical analysis of provable adversarial robustness via Lipschitz regularisation. A new architecture, the OVA network, is proposed, motivated by insights of how Lipschitz constants can be bounded for different architecture design choices. It is shown that OVA networks achieve similar empirical robustness to conventional neural Bounds on the error rate for VGG models trained on CIFAR-10 with the Lipschitz penalty regulariser. The bounds were computed with Proposition 2 at the 95% confidence level and the 2 threat model.

Table content: <table><tr><td colspan="4">Under review as a conference paper at ICLR 2020</td><td/><td/><td/></tr><tr><td/><td/><td/><td colspan="3">Perturbation Size ( 2 )</td><td/></tr><tr><td>Model</td><td colspan="6">λ Clean 1/255 2/255 3/255 4/255</td></tr><tr><td/><td colspan="6">0 14.50 100.00 100.00 100.00 100.00</td></tr><tr><td>VGG11-CNN</td><td colspan="2">0.0001 14.22 0.0005 16.00</td><td>47.61 29.00</td><td>79.22 42.74</td><td colspan="2">95.87 100.00 56.49 69.84</td></tr><tr><td/><td colspan="2">0.001 17.64</td><td>26.80</td><td>35.60</td><td>44.75</td><td>53.66</td></tr><tr><td/><td colspan="6">0 17.18 100.00 100.00 100.00 100.00</td></tr><tr><td>VGG11-OVANet</td><td colspan="2">0.0001 15.58 0.0005 15.86</td><td>44.54 27.68</td><td>73.49 39.01</td><td>93.11 51.85</td><td>99.99 63.68</td></tr><tr><td/><td colspan="2">0.001 17.09</td><td>25.00</td><td>32.54</td><td>40.35</td><td>48.53</td></tr><tr><td/><td/><td/><td colspan="3">Perturbation Size ( 2 )</td><td/></tr><tr><td>Model</td><td colspan="6">λ Clean 1/255 2/255 3/255 4/255</td></tr><tr><td/><td>0</td><td colspan="5">7.29 100.00 100.00 100.00 100.00</td></tr><tr><td>VGG11-CNN</td><td>0.0001 0.0005</td><td>7.15 8.46</td><td>13.16 11.38</td><td>21.86 14.84</td><td>33.59 19.33</td><td>47.10 24.49</td></tr><tr><td/><td>0.001</td><td>9.41</td><td>11.76</td><td>14.95</td><td>17.76</td><td>21.48</td></tr><tr><td/><td>0</td><td colspan="5">7.69 100.00 100.00 100.00 100.00</td></tr><tr><td>VGG11-OVANet</td><td>0.0001 0.0005</td><td>7.45 8.25</td><td>12.10 10.64</td><td>19.19 13.02</td><td>28.38 16.11</td><td>39.17 19.82</td></tr><tr><td/><td>0.001</td><td>9.02</td><td>10.92</td><td>12.86</td><td>15.05</td><td>17.81</td></tr></table>

Bounds on the error rate for VGG models trained on SVHN with the Lipschitz penalty regulariser. The bounds were computed with Proposition 2 at the 95% confidence level and the 2 threat model. networks when Lipschitz-based defences are used. However, as network size increases, OVA networks are able to achieve significantly better certifiable robustness. This is a useful result for practitioners, who can use our LP regulariser and bound in order to train models with quantitatively certifiable degree of robustness against adversarial attack.

Table content: <table><tr><td/><td/><td colspan="3">Perturbation Size ( 2 )</td><td/></tr><tr><td>Model</td><td>Clean</td><td>0.5</td><td>1.0</td><td>1.5</td><td>2.0</td></tr><tr><td>CNN</td><td colspan="5">0.80 2.87 14.90 49.64 74.73</td></tr><tr><td>CNN + LMT</td><td colspan="5">1.37 2.97 10.24 29.94 65.22</td></tr><tr><td>CNN + LP</td><td colspan="5">1.72 3.51 10.94 29.66 61.80</td></tr><tr><td>OVANet</td><td colspan="5">0.90 3.63 17.91 55.88 82.82</td></tr><tr><td>OVANet + LMT</td><td colspan="5">1.34 3.23 11.18 32.55 65.49</td></tr><tr><td>OVANet + LP</td><td colspan="5">1.90 3.44 11.42 30.51 58.50</td></tr></table>

Error rates (lower is better) of models trained with different regularisers when attacked with the projected gradient descent method ofMadry et al. (2018). The 2 threat model and regularisers are used. While our OVANet architecture does not improve empirical robustness, our LP training does benefit both model architectures.

Table content: <table><tr><td/><td/><td colspan="3">Perturbation Size ( ∞ )</td></tr><tr><td>Model</td><td>Clean</td><td>0.1</td><td>0.2</td><td>0.3</td></tr><tr><td>CNN</td><td colspan="3">0.80 26.72 94.66</td><td>99.34</td></tr><tr><td>CNN + LMT</td><td colspan="3">1.13 16.51 85.90</td><td>99.03</td></tr><tr><td>CNN + LP</td><td colspan="3">1.52 14.40 79.34</td><td>98.94</td></tr><tr><td>OVANet</td><td colspan="3">0.90 36.42 97.52</td><td>99.37</td></tr><tr><td>OVANet + LMT</td><td colspan="3">1.00 21.48 93.01</td><td>99.29</td></tr><tr><td>OVANet + LP</td><td colspan="3">1.25 17.32 88.63</td><td>99.10</td></tr></table>

Empirical error rates (lower is better) of models trained with different regularisers when attacked with the projected gradient descent method ofMadry et al. (2018). The ∞ threat model and regularisers are used. While our OAVNet architecture does not improve empirical robustness, our LP training does benefit both model architectures.

Table content: <table><tr><td/><td colspan="2">Lipschitz Constant</td></tr><tr><td>Model</td><td>2</td><td>∞</td></tr><tr><td>CNN</td><td>361.0</td><td>148,886.8</td></tr><tr><td>CNN + LMT</td><td>23.2</td><td>711.7</td></tr><tr><td>CNN + LP</td><td>11.3</td><td>261.2</td></tr><tr><td>OVANet</td><td>190.9</td><td>21,957.0</td></tr><tr><td>OVANet + LMT</td><td>22.7</td><td>741.3</td></tr><tr><td>OVANet + LP</td><td>9.4</td><td>215.8</td></tr></table>

Lipschitz constants for different architecture and regulariser combinations.

Table content: <table/>

Peer review (iclr2020):
1. Contributions: A) Extension of robustness bound based on margin and Lipschitz constant of the network to arbitrary l_p norms. Significance: Low. B) High probability bound on adversarial robustness based on A) and McDiarmid*s inequality. Significance: Low. C) Lipschitz constant bound for one-versus-all networks (OVAs). Significance: Low. D) Experimental evaluation. Significance: Low 2. Detailed comments: Originality: Contribution A) is a simple extension of previously known bounds for the l_2 norm which is rather technical. As such It has questionable novelty and limited potential impact. The same goes for B) which is a simple application of a well-known concentration bound that holds for many statistical estimators based on averaging. Also C) is a well-known alternative for multiclass classification (one-vs-all approach) and somehow defeats the purpose of representation reuse from intermediate layers of the network to perform classification. In OVAs the prediction for each class depends on entirely independent values of hidden layers. As such it is not surprising that. a slightly tighter estimate of robustness can be obtained, as one does not have to worry about interactions between features from each independent sub-network. Quality: The paper is in general well written, but lacks any depth or clear important contribution. The propositions are rather technical and/or simple extensions. The proposal of OVA networks and the bound on the adversarial risk are two parallel ideas that could be explored and hopefully find a significant contribution. For example, what could the authors say about local Lipschitz constant estimates? are they easy/difficult to compute? what new bounds could be derived in term of such constants? For OVA networks can there be some intermediate reuse of hidden layers and still get some improvement in certified robustness? perhaps only the final layers require a split to see the empirical improvement, in this way reducing the burden of training one network from scratch for each different class (ImageNet has 1000 classes so OVAs could be quite expensive to train). Or maybe for OVAs the complexity of each subnetwork can be substaintially less (e.g., less layers) to obtain the same accuracy/robustness?? It looks from the experiments that this is true but some theoretical insights about why it is the case can yield a strong paper. Clarity: The paper could see some improvements in notation and some erroneous claims: 1. Authors claim that the robustness can not be assessed when f is non-convex. This is in general, false. There is a constrained maximization procedure. constrained maximization of convex functions is a hard problem. Not to be confused with certain instances of constrained minimization of convex functions that can be solved efficiently. The same in section 5.1. The true statement is that for SVM the problem becomes optimization of a linear function with some simple constraint. 2. In section 3 it is not clear if the loss l depends on the label y or not. sometimes it appears as an argument, and sometimes it disappears. see for example equation (4). 3. In proposition 2 the assumption is that l is monotonically decreasing and its range is [0, B). Does this mean that B is negative?? this makes the claims in this section seem weird. There is some problem here. Also McDiarmids does not require the Doob Martingale concept, which is not even defined or referenced. Significance: I find the significance low as the work is incremental and has technical rather than theoretical statements, and lacks a clear contribution. I vote for rejecting this submission.