---
abstract: 'We provide a local class purity theorem for Lipschitz continuous, half-rectified DNN classifiers. In addition, we discuss how to train to achieve classification margin about training samples. Finally, we describe how to compute margin p-values for test samples.'
author:
- 'George Kesidis and David J. Miller [^1]'
title: |
     Notes on Lipschitz Margin,\
    Lipschitz Margin Training,\
    and Lipschitz Margin p-Values\
    for Deep Neural Network Classifiers
---

Introduction
============

A variety of papers have been recently produced on “robustifying" Deep Neural Networks (DNNs), particularly to adversarial Test-Time Evasion (TTE) attacks [@Tsuzuku18; @shiqi; @Madry-robust]. We discuss some of this work in Sections III.A and IV.A of [@Miller19] and argue for the need for TTE-attack detection [@MLSP18-ADA] for robustness.

In this note, we derive a [**local class purity**]{} result under the assumption of Lipschitz continuity, discuss Lipschitz margin training, and define an associated p-value. Estimation of the Lipschitz parameter for a given DNN is discussed in, [@Szegedy_seminal; @Tsuzuku18; @Weng18; @Pappas19].

Margin in DNN classifiers
=========================

Consider the DNN $f:\Reals^n\rightarrow (\Reals^+)^C$ where $C$ is the number of classes. Further suppose that for a test-time, input pattern $x\in\Reals^{n}$ to the DNN, the class decision is (x) = \_i f\_i(x), where $f_i$ is the $\th{i}$ component of the $C$-vector $f$. That is, we have defined a class-discriminant output layer of the DNN. Here assume that a class for $x$ is chosen arbitrarily among those that tie for the maximum.

Define the [**margin**]{} of $x$ as \[margin-def\] \_f(x) := f\_[(x)]{}(x)-\_[i=(x)]{} f\_i(x) & & 0. The normalized Lipschitz margin \[nlm\] can roughly be interpreted as a kind of confidence in classifying $x$ to class $\hatc(x)$, Section \[sec:margin-atypical\].

Now suppose the $\ell_{\infty}$ (max-norm) Lipschitz continuity parameter for $f$ is estimated as $L_\infty>0$ satisfying:[^2] x,y,   |f(x)-f(y)|\_& & L\_|x-y|\_.

Now consider samples in a open $\ell_\infty$ hypercube centered at $x$, $$y\in \mbox{B}_\infty(x,\varepsilon):=\{z\in\Reals^n~:~|x-z|_\infty
< \varepsilon\}$$ for $\varepsilon>0$.

The following “locally robust classification" result depends on the sample-dependent margin. This result is similar to that of [@Tsuzuku18].  \

\[thm:local-purity\] If $f$ is $\ell_\infty$ Lipschitz continuous with parameter $L_\infty >0$ and $\mu_f(x)>0$ then $$B\left( x,\frac{\mu_f(x)}{2L_\infty}\right)$$ is class pure.

 \
[**Proof:**]{} For any $y\in B(x,\frac{1}{2}\mu_f(x)/L_\infty)$ we get by the assumed Lipschitz continuity that \_f(x) & &gt;& |f(x)-f(y)|\_\
& := & \_i |f\_i(x)-f\_i(y)|\
& & \_i |f\_i(x)|-|f\_i(y)|    \
& = & \_i f\_i(x)-f\_i(y)    \
& & f\_[(x)]{}(x)-f\_[(x)]{}(y) So, \[y-bound1\] f\_[(x)]{}(y) & &gt; & f\_[(x)]{}(x) -\_f(x).

If we instead write $|f_i(y)|-|f_i(x)|$ in the triangle inequality above and then replace $\hatc(x)$ by any $i\not=\hatc(x)$, we get that \[y-bound2\] i=(x),   f\_[i]{}(y) & &lt; & f\_[i]{}(x) +\_f(x). So, by (\[y-bound1\]) and (\[y-bound2\]), i=(x),   f\_[i]{}(y) & &lt; & f\_[i]{}(x) +\_f(x)\
& & f\_[(x)]{}(x) -\_f(x)    \
& &lt; & f\_[(x)]{}(y)

Lipschitz-margin training
=========================

Robust training is surveyed in [@shiqi; @Miller19]. We focus herein on attempting to achieve a prescribed Lipschitz margin. Recall that, by Cover’s theorem [@Cover65], class separation is achieved if the DNN’s penultimate layer is sufficiently large.

Let $\theta$ represent the DNN parameters. Let $\Tcal$ represent the training dataset and let $c(x)$ for any $x\in\Tcal$ be the [*ground truth*]{} class of $x$.

To try to achieve a common Lipschitz margin of $\mu$ for all training samples, [@Tsuzuku18] suggests to add the margin “to all elements in logits except for the index corresponding to" $c(x)$. For example, train the DNN by finding: & &\
& = & \_-\_[x]{}() \[tsuzuku-obj\] For a softmax example, one could train the DNN using the modified cross-entropy loss[^3]: \_-\_[x]{}() \[cel-obj\] These DNN objectives do not guarantee the margins for training samples will be met.

Alternatively, for each training sample $x$, one could augment the training set with plural samples $y$ such that $|x-y|_\infty = \mu$ and simply train using an unmodified logit or cross-entropy loss objective.

Alternatively, one could first train an “original" DNN with an unmodified objective and unaugmented training dataset. Then the original DNN is used to produce [*adversarial examples*]{} by some strategy, [@Papernot; @Goodfellow; @CW; @MLSP18-ADA], each of bounded perturbation ($\sim\mu$) starting from training samples. The training dataset is then augmented by these adversarial examples and the DNN retrained (say starting from the parameters of the original DNN). See [@Madry-robust; @Zhang-blindspot] (and Sections III.A, IV.A of [@Miller19]).

Alternatively, one can achieve Lipschitz-margin DNN training by (dual) optimization of the weighted margin constraints, [*e.g.*]{}, \_ \_[x]{} \_x (), \[cel-dual0\] where the DNN mappings $f_i$ obviously depend on the DNN parameters $\theta$, and the weights $\lambda_x\geq 0$ $\forall x\in\Tcal$. For hyperparameter $\delta>1$, training can proceed simply as:

-   Select initially equal $\lambda_x >0$, say $\lambda_x=1$ $\forall x\in\Tcal$.

-   Optimize over $\theta$ (train the DNN).

-   If all margin constraints are satisfied then stop.

-   For all $x\in \Tcal$: if margin constraint $x$ is not satisfied then $\lambda_x \rightarrow\delta \lambda_x$.

-   Go to step 1.

Again, the parameters of the previous DNN could initialize the training of the next, and an initial DNN can be trained instead by using a logit or cross-entropy loss objective, as above. There are many other variations including also decreasing $\lambda_x$ when the $x$-constraint is satisfied, or additively (rather than exponentially) increasing $\lambda_x$ when they are not, and changing $\lambda_x$ in a way that depends on the degree of the corresponding margin violation. Clearly this approach may require frequent retraining of the DNN. Finally, let $-\sum_{x\in\Tcal} L(\theta,x,c(x))$ be a cross-entropy loss. For example, [@shiqi] discloses the training problem, \_\_[zB(x,), x]{} -\_[x]{} L(,z,c(x)), but notes that the inner maximization is NP hard [@Reluplex].

Low-margin atypicality of test samples {#sec:margin-atypical}
======================================

Given an arbitrary DNN $f:\Reals^n\rightarrow (\Reals^+)^C$ , let $\Tcal_\kappa$ be the training samples of class $\kappa\in\{1,2,...,C\}$, $\forall x\in\Tcal_\kappa$, $\hatc(x)=c(x)=\kappa$. Recall (\[margin-def\]) and suppose a Gaussian Mixture Model (GMM) is learned using the log-margins of the training dataset $$\{\log \mu_f(x)~:~x\in\Tcal_\kappa\}$$ by EM [@Dempster1977] using BIC model order control [@Schwarz1978] as, [@MLSP18-PCAD]. Let the resulting GMM parameters be $\{w_i,m_i,\sigma_i\}_{k=1}^{I_\kappa}$, where $I_\kappa\leq |\Tcal_\kappa|$ is the number of components, the $w_i\geq 0$ are their weights ($\sum_{i=1}^{I_\kappa} w_i = 1$), the $m_i$ are their means, and the $\sigma_i>0$ are their standard deviations. So, we can simply compute the [**margin p-value**]{} of any [**test sample**]{} $x$, \_f(x) & = & \_[i=1]{}\^[I\_]{} w\_i F() where $F$ is the standard normal c.d.f. That is, $\pi_f(x)$ is the probability that a randomly chosen sample from the same distribution as that of the training samples has smaller margin than the test sample $x$. So, one can use $\pi_f(x)$ to check whether a test sample $x$ has abnormally small classification margin.

Note that the margin p-value should not be based any “large perturbation" test-time evasion samples [@Papernot; @Goodfellow; @CW; @MLSP18-ADA] that may be used to augment the training dataset for purposes of robustness.

[10]{}

N. Carlini and D. Wagner. . In [*[Proc. IEEE Symposium on Security and Privacy]{}*]{}, 2017.

T.M. Cover. Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition. , EC-14:326–334, 1965.

Arthur P. Dempster, Nan M. Laird, and Donald B. Rubin. . , 39(1):1–38, 1977.

M. Fazlyab, A. Robey, H. Hassani, M. Morari, and G.J. Pappas. . https://arxiv.org/pdf/1906.04893.pdf, 2019.

I. Goodfellow, J. Shlens, and C. Szegedy. Explaining and harnessing adversarial examples. In [*[Proc. ICLR]{}*]{}, 2015.

G. Katz, C. Barrett, D.L. Dill, K. Julian, and M.J. Kochenderfer. . In [*Proc. Int’l Conf. on Computer Aided Verification (CAV)*]{}. Springer, 2017.

D.J. Miller, Z. Qiu, and G. Kesidis. . In [*Proc. IEEE MLSP*]{}, Aalborg, Denmark, Sept. 2018.

D.J. Miller, Y. Wang, and G. Kesidis. . , 2019; shorter version in [*Proc. IEEE MLSP*]{}, Aalborg, Denmark, Sept. 2018; https://arxiv.org/abs/1712.06646.

D.J. Miller, Z. Xiang, and G. Kesidis. . , 2019, http://arxiv.org/abs/1904.06292.

N. Papernot, P. McDaniel, S. Jha, M. Fredrikson, Z.B. Celik, and A. Swami. The limitations of deep learning in adversarial settings. In [*[Proc. 1st IEEE European Symp. on Security and Privacy]{}*]{}, 2016.

Gideon Schwarz. . , 6(2):461–464, 1978.

C. Szegedy, W. Zaremba, I Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus. Intriguing properties of neural networks. In [*[Proc. ICLR]{}*]{}, 2014.

D. Tsipras, S. Santurkar, L. Engstrom, A. Turner, and A. Madry. Robustness may be at odds with accuracy. In [*Proc. ICLR*]{}, 2019.

Y. Tsuzuku, I. Sato, and M. Sugiyama. . In [*Proc NIPS*]{}, 2018.

S. Wang, Y. Chen, A. Abdou, and S. Jana. . https://arxiv.org/abs/1811.02625, Nov. 2018.

T.-W. Weng, H. Zhang, H. Chen, Z. Song, C.-J. Hsieh, D. Boning, I.S. Dhillon, and L. Daniel. . https://arxiv.org/abs/1804.09699, Apr. 2018.

H. Zhang, H. Chen, Z. Song, D. Boning, I. Dhillon, and C.-J. Hsieh. The limitations of adversarial training and the blind-spot attack. https://arxiv.org/abs/1901.04684, 2019.

[^1]: The authors are with the School of EECS, Pennsylvania State University, University Park, PA, 16803, USA. This research is supported by AFOSR DDDAS grant and Cisco URP gift. Email: {gik2,djm25}@psu.edu

[^2]: Note that if $f$ is estimated to have an $\ell_2$ parameter $L_2$, then $L_\infty\leq nL_2$ since, $\forall z,  |z|_\infty \leq |z|_2\leq n|z|_\infty$.

[^3]: Note that we do not need to exponentiate as we herein assume that, $\forall x,i$, $f_i(x)\geq 0$, the DNN outputs are “half rectified" [@Szegedy_seminal].
