# Centralizers of Jacobian derivations

D.I.Efimov, A.P.Petravchuk, M.S.Sydorov  D.I.Efimov: Department of Algebra and
Computer Mathematics, Faculty of Mechanics and Mathematics, Taras Shevchenko
National University of Kyiv, 64, Volodymyrska street, 01033 Kyiv, Ukraine
<EMAIL_ADDRESS>A.P.Petravchuk: Department of Algebra and Computer
Mathematics, Faculty of Mechanics and Mathematics, Taras Shevchenko National
University of Kyiv, 64, Volodymyrska street, 01033 Kyiv, Ukraine
<EMAIL_ADDRESS><EMAIL_ADDRESS>M.S.Sydorov: Department of Algebra and
Computer Mathematics, Faculty of Mechanics and Mathematics, Taras Shevchenko
National University of Kyiv, 64, Volodymyrska street, 01033 Kyiv, Ukraine
<EMAIL_ADDRESS>
(Date: August 28, 2024)

###### Abstract.

Let $\mathbb{K}$ be an algebraically closed field of characteristic zero,
$\mathbb{K}[x,y]$ the polynonial ring in variables $x$, $y$ and let
$W_{2}(\mathbb{K})$ be the Lie algebra of all $\mathbb{K}$-derivations on
$\mathbb{K}[x,y]$. A derivation $D\in W_{2}(\mathbb{K})$ is called a Jacobian
derivation if there exists $f\in\mathbb{K}[x,y]$ such that $D(h)=\det J(f,h)$
for any $h\in\mathbb{K}[x,y]$ (here $J(f,h)$ is the Jacobian matrix for $f$
and $h$). Such a derivation is denoted by $D_{f}$. The kernel of $D_{f}$ in
$\mathbb{K}[x,y]$ is a subalgebra $\mathbb{K}[p]$ where $p=p(x,y)$ is a
polynomial of smallest degree such that $f(x,y)=\varphi(p(x,y)$ for some
$\varphi(t)\in\mathbb{K}[t]$. Let $C=C_{W_{2}(\mathbb{K})}(D_{f})$ be the
centralizer of $D_{f}$ in $W_{2}(\mathbb{K})$. We prove that $C$ is the free
$\mathbb{K}[p]$-module of rank 1 or 2 over $\mathbb{K}[p]$ and point out a
criterion of being a module of rank $2$. These results are used to obtain a
class of integrable autonomous systems of differential equations.

###### Key words and phrases:

Lie algebra, Jacobian derivation, differential equation, centralizer,
integrable system

###### 2000 Mathematics Subject Classification:

Primary 17B66; Secondary 17B80

##  1\. Introduction

Let $\mathbb{K}$ be an algebraically closed field of characteristic zero,
$\mathbb{K}[x,y]$ the polynomial ring in variables $x$, $y$ and
$R=\mathbb{K}(x,y)$ the field of rational functions. Recall that a
$\mathbb{K}$-linear map
$D:\mathbb{K}[x,y]\mathbb{\longrightarrow}\mathbb{K}[x,y]$ is called a
$\mathbb{K}$-derivation (or a derivation if $\mathbb{K}$ is fixed) if
$D(fg)=D(f)g+fD(g)$ for any $f,g\in\mathbb{K}[x,y]$. All the
$\mathbb{K}$-derivations on $\mathbb{K}[x,y]$ form a Lie algebra over
$\mathbb{K}$ (denoted by $W_{2}(\mathbb{K})$) with respect to the operation
$[D_{1},D_{2}]=D_{1}D_{2}-D_{2}D_{1}$. Every element $D\in W_{2}(\mathbb{K})$
can be uniquely written in the form $D=f(x,y)\partial_{x}+g(x,y)\partial_{y}$,
where $\partial_{x}:=\frac{\partial}{\partial
x},\partial_{y}:=\frac{\partial}{\partial y}$ are partial derivatives on
$\mathbb{K}[x,y]$. The latter means that $W_{2}(\mathbb{K})$ is a free module
of rank $2$ over $\mathbb{K}[x,y]$ and $\\{\partial_{x},\partial_{y}\\}$ is a
free basis of this module. The Lie algebra $W_{2}(\mathbb{K})$ is, from the
geometrical point of view, the Lie algebra of all polynomial vector fields on
$\mathbb{K}^{2}$ and was studied intensively from many points of view (see,
for example, [5], [4], [10]).

Let $f\in\mathbb{K}[x,y]$. The polynomial $f$ defines a derivation $D_{f}\in
W_{2}(\mathbb{K})$ by the rule: $D_{f}(h)=\det J(f,h)$ for any
$h\in\mathbb{K}[x,y]$ (here $J(f,h)$ is the Jacobian matrix for $f$ and $h$).
The derivation $D_{f}$ is called the Jacobian derivation associated with the
polynomial $f$. The kernel $\operatorname{Ker}D_{f}$ in $\mathbb{K}[x,y]$ is
an integrally closed subalgebra of $\mathbb{K}[x,y]$ and
$f\in\operatorname{Ker}D_{f}$. By [7],
$\operatorname{Ker}D_{f}=\mathbb{K}[p]$, where $p$ is a generative closed
polynomial for $f$.

We study the structure of the centralizer $C_{W_{2}(\mathbb{K})}(D_{f})$. This
centralizer is of interest because from viewpoint of theory of ODE with any
derivation $D=f(x,y)\partial_{x}+g(x,y)\partial_{y}$ one can associate an
autonomous system of ordinary differential equations

$\frac{dx}{dt}=f(x,y),\ \frac{dy}{dt}=g(x,y)$

and elements from $C_{W_{2}(\mathbb{K})}(D)$ give information about solutions
of this system.

We give a criterion for a Jacobian derivation $D_{f}$ to have the centralizer
of rank 2 over $\operatorname{Ker}D_{f}$ (Theorem 1). We also prove that
$C_{W_{2}(\mathbb{K})}(D_{f})$ is a free module over the subalgebra
$\mathbb{K}[p]$ of rank 1 or 2 (Theorem 2). We point out an example of
integrable system of differential equations associated with a Jacobian
derivation of special type.

We use standard notations. If $T=P\partial_{x}+Q\partial_{y}$ then the
divergence $\operatorname{div}T$ is defined as for a vector field with
components $P,Q$: $\operatorname{div}T=P_{x}^{\prime}+Q_{y}^{\prime}$. If
$T=P\partial_{x}+Q\partial_{y}$ is divergence-free (i.e.,
$\operatorname{div}T=0$), then $T=D_{f}$ for a polynomial $f$ that is a
“potential” for the vector field determined by $T$. A polynomial
$f\in\mathbb{K}[x,y]$ is called a closed polynomial if the subalgebra
$\mathbb{K}[f]$ is integrally closed in the polynomial algebra
$\mathbb{K}[x,y]$. For any polynomial $f\in\mathbb{K}[x,y]$ there exists a
closed polynomial $p(x,y)$ such that $f=\varphi(p)$ for some polynomial
$\varphi\in\mathbb{K}[x,y].$ This polynomial $p(x,y)$ will be called a
generative closed polynomial for $f(x,y).$ If $L$ is a subalgebra of the Lie
algebra $W_{2}(\mathbb{K})$ then $\dim_{R}RL$ will be called the rank of $L$
and denoted by ${\rm rk}_{\mathbb{K}[x,y]}L$ or simply by ${\rm rk}L.$

##  2\. A criterion for centralizers to have rank $2$

Some properties of derivations on polynomial rings are collected in the next
lemma.

######  Lemma 1.

(1) Let $D_{1},D_{2}\in W_{2}(\mathbb{K})$ and $f,g\in\mathbb{K}[x,y]$. Then

$[fD_{1},gD_{2}]=fD_{1}(g)D_{2}-gD_{2}(f)D_{1}+fg[D_{1},D_{2}].$

(2) If $f\in\mathbb{K}[x,y]$ and $p$ is a generative closed polynomial for
$f$, then $\operatorname{Ker}D_{f}=\mathbb{K}[p]$.

(3) If $T\in W_{2}(\mathbb{K})$ and ${\rm div}T=0$, then $T=D_{g}$ for some
polynomial $g\in\mathbb{K}[x,y].$

###### Proof.

(1) Direct calculation. (2) See, for example, [9]. (3) See, for example, [8].
∎

######  Lemma 2.

Let $T\in W_{2}(\mathbb{K})$ and $T(f)=\lambda f$ for some polynomials
$f,\lambda\in\mathbb{K}[x,y]$. Then $[T,D_{f}]=D_{\lambda
f}-(\operatorname{div}T)D_{f}$.

###### Proof.

Let us write down the derivation $T$ in the form
$T=P\partial_{x}+Q\partial_{y}$ for some polynomials $P,Q\in\mathbb{K}[x,y]$.
Then the condition $T(f)=\lambda f$ can be written in the form

(1) $Pf^{\prime}_{x}+Qf^{\prime}_{y}=\lambda f$

Let us differentiate the equality (1) on $x$ and then on $y$. We obtain

(2)
$P^{\prime}_{x}f^{\prime}_{x}+Pf^{\prime\prime}_{x^{2}}+Q^{\prime}_{x}f^{\prime}_{y}+Qf^{\prime\prime}_{yx}=\lambda^{\prime}_{x}f+\lambda
f^{\prime}_{x},$ (3)
$P^{\prime}_{y}f^{\prime}_{x}+Pf^{\prime\prime}_{xy}+Q^{\prime}_{y}f^{\prime}_{y}+Qf^{\prime\prime}_{y^{2}}=\lambda^{\prime}_{y}f+\lambda
f^{\prime}_{y}.$

Further, write down the product of derivations $T$ and $D_{f}$ in terms of
their components:

(4)
$[T,D_{f}]=(P^{\prime}_{x}f^{\prime}_{y}-P^{\prime}_{y}f^{\prime}_{x}-Pf^{\prime\prime}_{yx}-Qf^{\prime\prime}_{y^{2}})\partial_{x}+\\\
(Pf^{\prime\prime}_{x^{2}}+Qf^{\prime\prime}_{xy}+f^{\prime}_{y}Q^{\prime}_{x}-f^{\prime}_{x}Q^{\prime}_{y})\partial_{y}.$

Let us denote for convenience
$\alpha=-P^{\prime}_{y}f^{\prime}_{x}-Pf^{\prime\prime}_{yx}-Qf^{\prime\prime}_{y^{2}}$
and
$\beta=Pf^{\prime\prime}_{x^{2}}+Qf^{\prime\prime}_{xy}+f^{\prime}_{y}Q^{\prime}_{x}$.
Then using (3) and (2) we see that

(5) $\alpha=Q^{\prime}f^{\prime}_{y}-\lambda^{\prime}_{y}f-\lambda
f^{\prime}_{y},\ \beta=\lambda^{\prime}_{x}f+\lambda
f^{\prime}_{x}-P^{\prime}_{x}f^{\prime}_{x}.$

The equality (4) can be rewritten in the form

$[T,D_{f}]=(P^{\prime}_{x}f^{\prime}_{y}+\alpha)\partial_{x}+(\beta-f^{\prime}_{x}Q^{\prime}_{y})\partial_{y}.$

Inserting in the last equality instead $\alpha$ and $\beta$ their expressions
from (5) we see that

$[T,D_{f}]=(P^{\prime}_{x}f^{\prime}_{y}-\lambda^{\prime}_{y}f-\lambda
f^{\prime}_{y}+Q^{\prime}_{y}f^{\prime}_{y})\partial_{x}+(\lambda^{\prime}_{x}f+\lambda
f^{\prime}_{x}-P^{\prime}_{x}f^{\prime}_{x}-f^{\prime}_{x}Q^{\prime}_{y})\partial_{y}.$

After rearranging the summands in the right part of this equality we get

$[T,D_{f}]=((\operatorname{div}T)f^{\prime}_{y}-(\lambda
f)^{\prime}_{y})\partial_{x}+((\lambda
f)^{\prime}_{x}-(\operatorname{div}T)f^{\prime}_{x})\partial_{y}$

The latter means that

$[T,D_{f}]=(\operatorname{div}T)(f^{\prime}_{y}\partial_{x}-f^{\prime}_{x}\partial_{y})+D_{\lambda
f}=D_{\lambda f}-(\operatorname{div}T)D_{f}.$

The proof is complete.

∎

######  Remark 1.

The direct calculation shows that $D_{\lambda f}=\lambda D_{f}+fD_{\lambda}$.
Therefore

$[T,D_{f}]=\lambda
D_{f}+fD_{\lambda}-(\operatorname{div}T)D_{f}=fD_{\lambda}+(\operatorname{div}T-\lambda)D_{f}.$

######  Lemma 3.

Let $T\in W_{2}(\mathbb{K}),f\in\mathbb{K}[x,y]$ be such that $[T,D_{f}]=0$.
If $T(f)=c$ for some $c\in\mathbb{K}$, then $T=D_{g}$ for some polynomial
$g\in\mathbb{K}[x,y]$.

###### Proof.

Let us write down the derivation $T$ in the form
$T=P\partial_{x}+Q\partial_{y}$ for some $P,Q\in\mathbb{K}[x,y]$. Then
$Pf^{\prime}_{x}+Qf^{\prime}_{y}=c$ by conditions of the lemma.
Differentiating this equality first on $x$ and then on $y$, we obtain the next
equalities

(6)
$P^{\prime}_{x}f^{\prime}_{x}+Pf^{\prime\prime}_{x^{2}}+Q^{\prime}_{x}f^{\prime}_{y}+Qf^{\prime\prime}_{yx}=0,$
(7)
$P^{\prime}_{y}f^{\prime}_{x}+Pf^{\prime\prime}_{xy}+Q^{\prime}_{y}f^{\prime}_{y}+Qf^{\prime\prime}_{y^{2}}=0.$

We see from (6) that

$Pf^{\prime\prime}_{x^{2}}+Q^{\prime}_{x}f^{\prime}_{y}=-P^{\prime}_{x}f\\_x-
Qf^{\prime\prime}_{xy}$

and anagously from (7)

$P^{\prime}_{y}f^{\prime}_{x}+P_{x}f^{\prime\prime}_{xy}=-Q^{\prime}_{y}f^{\prime}_{y}-Qf^{\prime\prime}_{y^{2}}.$

Therefore it follows from (4) that

$[T,D_{f}]=(-Q^{\prime}_{y}f^{\prime}_{x}-P^{\prime}_{x}f^{\prime}_{x})\partial_{y}+(P^{\prime}_{x}f^{\prime}_{y}+Q^{\prime}_{y}f^{\prime}_{y})\partial_{x}=$
$=f^{\prime}_{y}(P^{\prime}_{x}+Q^{\prime}_{y})\partial_{x}-f^{\prime}_{x}(P^{\prime}_{x}+Q^{\prime}_{y})\partial_{y}=\operatorname{div}T\cdot(-D_{f}).$

Since $[T,D_{f}]=0$ by conditions of the lemma, we see from the equality
$[T,D_{f}]=-(\operatorname{div}T)D_{f}$, that $\operatorname{div}T=0$. It
follows from Lemma 1 that $T=D_{g}$ for some polynomial $g\in\mathbb{K}[x,y].$

∎

######  Corollary 1.

(1) Let $T\in C_{W_{2}(\mathbb{K})}(D_{f}).$ If $T(f)=0,$ then $T=\varphi
D_{f}$ for some rational function $\varphi\in\mathbb{K}(x,y)$ such that
$\varphi\in\operatorname{Ker}D_{f}.$ (2) If $T(f)=c$ for some
$c\in\mathbb{K}^{*}$, then $T=D_{g}$ for some $g\in\mathbb{K}[x,y]$ such that
$f,g$ form a Jacobian pair, i.e., $D_{g}(f)=-D_{f}(g)=c$.

###### Proof.

(1) Take any polynomial $h\in\mathbb{K}[x,y]$ such that $f,h$ are
algebraically independent over $\mathbb{K}$ and put
$g_{1}=D_{f}(h),g_{2}=T(h)$. Then $g_{1}\neq 0$ because in other case
$\operatorname{Ker}D_{f}$ would be of transcendence degree 2 in
$\mathbb{K}(x,y)$ which is impossible. Note that $(g_{2}D_{f}-g_{1}T)(h)=0$
and $(g_{2}D_{f}-g_{1}T)(f)=0$. Since $f,h$ form a transcendence basis of the
field $\mathbb{K}(x,y)$, the next equality holds: that $g_{2}D_{f}-g_{1}T=0$.
Therefore $T=(g_{2}/g_{1})D_{f}$. It follows from the equality $[T,D_{f}]=0$
that $D_{f}(g_{2}/g_{1})=0$, that is $g_{2}/g_{1}\in\operatorname{Ker}D_{f}$.
Denoting $\varphi=g_{2}/g_{1}$ we get the proof of part (1) of the corollary.

(2) Since $T(f)=c$ we have by Lemma 1 that $T=D_{g}$ for some polynomial
$g\in\mathbb{K}[x,y]$. But then $T(f)=D_{g}(f)=\det
J(g,f)=c\in\mathbb{K}^{*}$. The latter means that the polynomials $f,g$ form a
Jacobian pair.

∎

######  Theorem 1.

Let $f\in\mathbb{K}[x,y],f=\theta(p)$ for a generative closed polynomial
$p\in\mathbb{K}[x,y]$ with $\deg\theta\geq 1$. A derivation $T\in
W_{2}(\mathbb{K})$ commutes with $D_{f}$ if and only if $T(p)=\psi(p)$ for
some polynomial $\psi(t)\in\mathbb{K}[t]$ and
$\theta^{\prime\prime}(p)\psi(p)=\theta^{\prime}(p)(\operatorname{div}T-\psi^{\prime}(p)).$

###### Proof.

Let $[T,D_{f}]=0.$ By Lemma 1, $\operatorname{Ker}D_{f}=\mathbb{K}[p]$,
therefore $T(\mathbb{K}[p])\subseteq\mathbb{K}[p].$ Then $T(p)=\psi(p)$ for
some polynomial $\psi(t)\in\mathbb{K}[t].$ Let us prove the equality

(8)
$\theta^{\prime\prime}(p)\psi(p)=\theta^{\prime}(p)(\operatorname{div}T-\psi^{\prime}(p)).$

First, let $\deg\psi(t)\geq 1$. Write
$\psi(t)=a_{0}(t-\lambda_{1})\dots(t-\lambda_{k})$, where $k\geq 1$ and
$\lambda_{i}\in\mathbb{K}$ (recall that $\mathbb{K}$ is algebraically closed).
Therefore $T(p)=a_{0}(p-\lambda_{1})\dots(p-\lambda_{k})$. This equality can
be written in the form

$T(p-\lambda_{1})=a_{0}(p-\lambda_{1})\dots(p-\lambda_{k})$

and taking $p-\lambda_{1}$ instead of $p$ we can write the last equality as
$T(p)=a_{0}p(p-\mu_{2})\dots(p-\mu_{k})$ for some $\mu_{k}\in\mathbb{K}$ (note
that the polynomial $p-\lambda_{1}$ is also closed and
$\mathbb{K}[p]=\mathbb{K}[p-\lambda_{1}]$). The last equality can be written
in the form

$T(p)=\psi(p)=p\mu(p)\text{ for}\ \mu(p)=a_{0}p(p-\mu_{2})\dots(p-\mu_{k}).$

By Lemma 2, we have

(9)
$[T,D_{p}]=D_{\psi(p)}-(\operatorname{div}T)D_{p}=(\psi^{\prime}(p)-\operatorname{div}T)D_{p}.$

But, on the other hand, it follows from the equality

$[T,D_{f}]=[T,\theta^{\prime}(p)D_{p}]=0$

that $T(\theta^{\prime}(p))D_{p}=-\theta^{\prime}(p)[T,D_{p}]$ and therefore

(10) $[T,D_{p}]=-\frac{T(\theta^{\prime}(p)}{\theta^{\prime}(p)}D_{p}$

(note that $\theta^{\prime}(p)\neq 0$ because $f=\theta(p)$ and $f\neq
const$).

It follows from (9) and (10) that

$-\frac{T(\theta^{\prime}(p)}{\theta^{\prime}(p)}=\psi^{\prime}(p)-\operatorname{div}T.$

Therefore it holds the desired equality
$\theta^{\prime\prime}(p)\psi(p)=\theta^{\prime}(p)(\operatorname{div}T-\psi^{\prime}(p))$
because $T(\theta^{\prime}(p))=\theta^{\prime\prime}(p)\psi(p).$

Now let $\deg\psi(t)<1$. The latter means that $\psi(t)=c\in\mathbb{K}$.

By Lemma 3, $T=D_{g}$ for some polynomial $g\in\mathbb{K}[x,y]$ and therefore
$\operatorname{div}T=0$. If $c=0$, that is $\psi(t)\equiv 0$, then obviously
(8) holds. Let $c\neq 0$. Then $D_{g}(p)=c$ and the polynomials $p,g$ form a
Jacobian pair. Let us show that $\deg\theta=1$ in this case. Indeed, in other
case

$[T,D_{f}]=[D_{g},D_{f}]=[D_{g},\theta^{\prime}(p)D_{p}]=\theta^{\prime\prime}(p)\cdot
c\cdot D_{p}+\theta^{\prime}(p)[D_{g},D_{p}].$

By Lemma 1, $[D_{g},D_{p}]=D_{c}=0$ (recall that $D_{g}(p)=c$) and therefore

$[T,D_{f}]=\theta^{\prime\prime}(p)\cdot c\cdot D_{p}=0.$

The latter contradicts our choice of the derivation $T$ because $c\not=0,$ and
$\theta^{\prime\prime}\not=0$ by our assumption. Therefore $\deg\theta(t)=1$.
Taking into account the relations $\theta^{\prime\prime}(p)=0$,
$\operatorname{div}T=0$, $\psi^{\prime}(p)=0$ we see that the equality (8)
holds.

Let now $T(p)=\psi(p),f=\theta(p)$ for some closed polynomial $p$, and let the
equality (8) hold. Let us show that $[T,D_{f}]=0$, i.e.
$[T,\theta^{\prime}(p)D_{p}]=0$. The last equality is equivalent to the
equality

(11) $T(\theta^{\prime}(p))D_{p}=-\theta^{\prime}(p)[T,D_{p}].$

First, consider the case $\deg\psi(t)\geq 1$. Then as above one can assume
without loss of generality that $\psi(t)=t\lambda(t)$ for some polynomial
$\lambda(t)\in\mathbb{K}[t]$. By Lemma 2, we get

$[T,D_{p}]=(\psi^{\prime}(p)-\operatorname{div}T)D_{p}.$

Using (11) one can easily show that the latter equality is equivalent to the
equality (8):

$\theta^{\prime\prime}(p)\psi(p)D_{p}=\theta^{\prime}(p)(\operatorname{div}T-\psi^{\prime}(p))D_{p},$

which holds by our assumptions. So, we have $[T,D_{f}]=0$ in the case
$\deg\psi(t)\geq 1$.

Consider the case $\deg\psi(t)<1$, i.e., $\psi(t)=c$ for some $c\in\mathbb{K}$
. If $\psi(t)\equiv 0$, then $\operatorname{div}T=0$ by the equality (8).
Therefore (by Lemma 1) $T=D_{g}$ for some polynomial $g\in\mathbb{K}[x,y]$ and
$T(p)=0=D_{g}(p).$ Thus $D_{p}(g)=0$, i.e., $g\in\operatorname{Ker}D_{p}$. It
follows from the equality $\operatorname{Ker}D_{p}=\mathbb{K}[p]$ that
$g=\mu(p)$ for some polynomial $\mu(t)\in\mathbb{K}[t]$. But then
$T=D_{g}=\mu^{\prime}(p)D_{p}$. Taking into account the equality
$D_{f}=D_{\theta(p)}=\theta^{\prime}(p)D_{p}$ we get

$[T,D_{f}]=[\mu^{\prime}(p)D_{p},\theta^{\prime}(p)D_{p}]=0$

because $\mu^{\prime}(p),\theta^{\prime}(p)\in\operatorname{Ker}D_{p}.$ Let
now $\psi(t)=c,c\in\mathbb{K}^{*}$. Then $T(p)=c$ and from the conditions of
the theorem we have $\theta^{\prime\prime}(p)\cdot
c=\theta^{\prime}(p)\operatorname{div}T$. The latter equality implies that
$\operatorname{div}T=0$ because $\operatorname{div}T$ is a polynomial and
$\deg\theta^{\prime\prime}(p)<\deg\theta^{\prime}(p).$ But then $T=D_{g}$ for
some polynomial $g(t)\in\mathbb{K}[t]$. It follows from the conditions of the
theorem that $\theta^{\prime\prime}(p)=0$ and hence $\theta(p)=\alpha p+\beta$
for some $\alpha,\beta\in\mathbb{K},\alpha\neq 0$. Without loss of generality
one can assume that $f=\theta(p)=p$. We have $T(p)=c$ and $T=D_{g}$. Then
$D_{p}(g)=-c$ and therefore the polynomials $p,g$ form a Jacobian pair. The
latter means that

$[T,D_{f}]=[D_{g},D_{f}]=D_{[p.g]}=D_{c}=0$

that is $T$ and $D_{f}$ commute. The proof of the theorem is complete. ∎

######  Corollary 2.

Let $f\in\mathbb{K}[x,y]$ be a closed (in particular, irreducible) polynomial.
A derivation $T\in W_{2}(\mathbb{K})$ commutes with $D_{f}$ if and only if
$T(f)=\psi(f)$ for some polynomial $\psi(t)\in\mathbb{K}[t]$ and
$\operatorname{div}T=\psi^{\prime}(f)$.

###### Proof.

Since $f$ is closed we can take without loss of generality thet $\theta(t)=t.$
Then $\theta^{\prime\prime}(t)=0$, and one can easily show that (8) is
equivalent to the equality $\operatorname{div}T=\psi^{\prime}(f)$. ∎

In [12], a class of Jacobian derivations was studied that was induced by
weakly semisimple polynomials $f\in\mathbb{K}[x,y]$ (a polynomial $f$ is
called weakly semisimple if the corresponding Jacobian derivation $D_{f}$ has
an eigenfunction $g\in\mathbb{K}[x,y]$ with nonzero eigenvalue
$\lambda\in\mathbb{K}$, i.e. if $D_{f}(g)=\lambda g$). In [3], such
polynomials were described in some cases and some examples were pointed out.
Using some results from [3] one can construct Jacobian derivations whose
centralizers are of rank $2$ over their the ring of constants.

######  Example 1.

Let $f(x,y),g(x,y)\in\mathbb{K}[x,y]$ be nonzero polynomials such that
$D_{f}(g)=g.$ Then

$[fD_{g}-gD_{f},D_{g}]=-D_{g}(f)D_{g}-g[D_{f},D_{g}]=gD_{g}-gD_{g}=0,$

(here we use the equality $[D_{f},D_{g}]=D_{h},$ where $h=D_{f}(g)$). The
latter means that the Jacobian derivation $D_{g}$ has the centralizer in
$W_{2}(\mathbb{K})$ of rank $2$ over its ring of constants. This centralizer
contains two linearly independent (over $\mathbb{K}[x,y]$ ) derivations
$D_{g}$ and $fD_{g}-gD_{f}.$ Let us choose, for example, the polynomials $f$
and $g$ of the form:

$f(x,y)=x(x-1)y,\ \ g(x,y)=x^{3}(x-1)y^{2}.$

One can easily check that $D_{f}(g)=g.$ So, the derivation
$D_{g}=-2yx^{3}(x-1)\partial_{x}+(4x^{3}-3x^{2})y^{2}\partial_{y}$ has the
centralizer in $W_{2}(\mathbb{K})$ of rank $2$ over $\mathbb{K}[p]$ and the
corresponding system of differential equations

$\frac{dx}{dt}=-2yx^{3}(x-1),\ \frac{dy}{dt}=(4x^{3}-3x^{2})y^{2}$

is integrable (see, for example, [6]).

##  3\. On structure of centralizers of Jacobian derivations

######  Theorem 2.

Let $f\in\mathbb{K}[x,y]$ be a nonconstant polynomial and $D_{f}$ the
corresponding Jacobian derivation. Let $p$ be a generative closed polynomial
for $f$. Then the centralizer $C_{W_{2}(\mathbb{K})}(D_{f})$ is a free module
of rank $1$ or $2$ over the subring $\mathbb{K}[p]$ of $\mathbb{K}[x,y].$

###### Proof.

Since $p$ is a generative closed polynomial for $f$ we have $f=\theta(p)$ for
some polynomial $\theta(t)\in\mathbb{K}[t].$ Obviously
$D_{f}=\theta^{\prime}(p)D_{p}$ and, by Lemma 1, ${\rm ker}D_{f}={\rm
ker}D_{p}.$ Let us denote for brevity $C=C_{W_{2}(\mathbb{K})}(D_{f})$.
Obviously $C$ is a module over the subring $\mathbb{K}[p]$ of
$\mathbb{K}[x,y]$. Denote $C_{1}=\mathbb{K}[x,y]C$, it is obvious that $C_{1}$
is a $\mathbb{K}[x,y]$-module and ${\rm rk}_{\mathbb{K}[x,y]}C_{1}\leq 2$
(recall that $W_{2}(\mathbb{K})$ is a free $\mathbb{K}[x,y]$-module of rank
$2$).

First, let ${\rm rk}_{\mathbb{K}[x,y]}C_{1}=1.$ Let us show that in this case
${\rm rk}_{\mathbb{K}[p]}C=1$ and $D_{p}$ is a free generator of the module
$C$. Take any $T\in C,T\not=0.$ By our assumptions on $C_{1}$, there exist
polynomials $g,h\in\mathbb{K}[x,y]$ such that $gD_{p}+hT=0$, and at least one
of the polynomials $g,h$ is nonzero. Since $D_{p}\not=0$ we have $h\not=0$ and
therefore $T=-(g/h)D_{p}.$ But then $D_{f}(g/h)=0$. The latter means that the
rational function $g/h$ belongs to ${\rm ker}_{R}D_{f},$ where ${\rm
ker}_{R}D_{f}$ is the kernel of the extension of $D_{f}$ on
$R=\mathbb{K}(x,y).$ Since ${\rm ker}_{R}D_{f}=\mathbb{K}(p)$ (see, for
example [9]) we have $g/h=a(p)/b(p)$ for some polynomials
$a(t),b(t)\in\mathbb{K}[t]$ that can be chosen to be coprime. Thus, we obtain
the equality $a(p)D_{p}+b(p)T=0$ and $a(p),b(p)$ are coprime. From the latter
equality we see that $b(p)$ divides $D_{p}$, i.e. $D_{p}=b(p)D_{1}$ for some
derivation $D_{1}\in W_{2}(\mathbb{K}).$ But then $b(p)=const$ because
$D_{p}=-p^{\prime}_{y}\partial_{x}+p^{\prime}_{x}\partial_{y}$ and $b(p)$ does
not divide $p^{\prime}_{y},p^{\prime}_{x}$ if ${\rm deg}b(t)>0.$ Thus, we have
$T=(-a(p)/b(p))D_{p}$ and $D_{p}$ is a free generator for the centralizer
$C=C_{W_{2}(\mathbb{K})}(D_{f})$ as a $\mathbb{K}[p]$-module.

Let now ${\rm rk}_{\mathbb{K}[x,y]}C_{1}=2.$ Choose any $T\in C$ such that $T$
and $D_{p}$ are linearly independent over $\mathbb{K}[x,y]$. It follows from
the equality $[T,D_{p}]=0$ that $T({\rm ker}(D_{f}))\subseteq{\rm
ker}(D_{f})$, so $T(\mathbb{K}[p])\subseteq\mathbb{K}[p].$ Therefore
$T(p)=\mu(p)$ for some polynomial $\mu(t)\in\mathbb{K}[t].$ Choose among all
such $T\in C$ a derivation $T_{0}$ such that ${\rm deg}\mu_{0}(t)$ is minimum,
where $\mu_{0}(t)$ is the corresponding polynomial for $T_{0}$. One can easily
show that for any $T\in C$ its polynomial $\mu(t)$ is divisible by
$\mu_{0}(t)$. Really, let

$\mu(t)=q(t)\mu_{0}(t)+r(t)$

with ${\deg}r(t)<{\rm deg}\mu_{0}(t)$. Then $T-q(p)T_{0}\in C$ and
$(T-q(p)T_{0})(p)=r(p).$ By our choice of $T_{0}$ we have $r(t)=0$. So, every
$T\in C$ can be written in the form $T=q(p)T_{0}+T_{1}$, where
$T_{1}=T-q(p)T_{0}$ satisfies the equality $T_{1}(p)=0.$ Since
$[T_{1},D_{p}]=0$ we can show using Corollary (1) that $T_{1}=\delta(p)D_{p}$
for some polynomial $\delta(t)\in\mathbb{K}[t]$. Therefore
$T=q(p)T_{0}+\delta(p)D_{p}.$ The latter means that the derivations $T_{0}$
and $D_{p}$ are free generators of the $\mathbb{K}[p]$-module $C.$ The proof
is complete. ∎

## References

  * [1] L.P.Bedratyuk, Ie.YU.Chapovsky, A.P.Petravchuk _Centralizers of linear and locally nilpotent derivations_ , Ukrainian Math. J., issue 75, N.8, 2023, pp.1043–1052, doi:10.3842/umzh.v75i8.7529 (in Ukrainian)
  * [2] Y.Chapovskyi, D.Efimov, A.Petravchuk, _Centralizers of elements in Lie algebras of vector fields with polynomial coefficients_ , Proceedings of the International Geometry Center, 14 (4), 2021, pp.257–270.
  * [3] Gavran V.S.,Stepukh V.V., _On weakly semisimple derivations of the polynomial ring in two variables_ , Algebra and Discrete mathematics, Vol. 18. N.1, 2014, pp.50–58.
  * [4] A. González-López, N. Kamran, P.J. Olver, _Lie algebras of vector fields in the real plane_ , Proc. Lond. Math. Soc. (3) 64 (2), 1992, pp.339–368.
  * [5] S. Lie, _Theorie der Transformationsgruppen_ , vol. 3, B.G. Teubner, Leipzig, 1893.
  * [6] Joel Nagloo, Alexey Ovchinnikov, Peter Thompson. _Commuting planar polynomial vector fields for conservative newton systems_ , Communications in Contemporary Mathematics, 22(04), 2020, pp.195–225.
  * [7] A.Nowicki, M.Nagata, _Rings of constants for k-derivations in $k[x_{1},\ldots,x_{n}]$_, J. Math. Kyoto Univ., Vol. 28, N.1, 1988, pp.111-118.
  * [8] A.Nowicki, _Polynomial derivations and their rings of constants_ , Uniwersytet Mikolaja Kopernika Torun, 1994.
  * [9] Anatoliy Petravchuk, Oleksandr Iena, _On closed rational functions in several variables_ , Algebra and Discrete Mathematics, N.2, 2007, pp.115–124,
  * [10] A.P.Petravchuk, O.G.Iena, _On centralizers of elements in the Lie algebra of the special Cremona group ${\rm SA}_{2}(k)$_, J. Lie Theory, v.16, no.3, 2006, pp.561–567.
  * [11] Andrzej Schinzel, _Polynomials with special regard to reducibility_ , volume 77. Cambridge University Press, 2000.
  * [12] Y. Stein, _Weakly nilpotent and weakly semisimple polynomials on the plane_ , Int. Math. Research Notices, 13, 2000, pp.681-698.


# General Lipschitz: Certified Robustness Against Resolvable Semantic
Transformations via Transformation-Dependent Randomized Smoothing

Dmitrii Korzh1, Mikhail Pautov1, Olga Tsymboi2, 4, Ivan Oseledets1, 3

###### Abstract

Randomized smoothing is the state-of-the-art approach to construct image
classifiers that are provably robust against additive adversarial
perturbations of bounded magnitude. However, it is more complicated to
construct reasonable certificates against semantic transformation (e.g., image
blurring, translation, gamma correction) and their compositions. In this work,
we propose _General Lipschitz (GL),_ a new framework to certify neural
networks against composable resolvable semantic perturbations. Within the
framework, we analyze transformation-dependent Lipschitz-continuity of
smoothed classifiers w.r.t. transformation parameters and derive corresponding
robustness certificates. Our method performs comparably to state-of-the-art
approaches on the ImageNet dataset.

## Introduction

Deep neural networks show remarkable performance in a variety of computer
vision tasks. However, they are drastically vulnerable to specific input
perturbations (called adversarial attacks) that might be imperceptible to the
human eye as it was initially shown in (Szegedy et al. 2013; Biggio et al.
2013) for additive perturbations. Namely, suppose a deep neural network
$f:\mathbb{R}^{n}\to[0,1]^{C}$ maps input images $x$ to class probabilities.
Then, given the classification rule $\hat{f}(x)=\operatorname*{argmax}_{i\in
Y}f_{i}(x)$, where $Y=\\{1,2,\dots,C\\}$, it is possible to craft an
adversarial perturbation $\delta$ such that $x$ and $x+\delta$ are assigned by
$\hat{f}$ to different classes. For some applications, such as self-driving
cars (Tu et al. 2021; Chernikova et al. 2019; Tu et al. 2020) and
identification systems (Kurakin, Goodfellow, and Bengio 2018; Komkov and
Petiushko 2021; Pautov et al. 2019; Chen et al. 2019; Kaziakhmedov et al.
2019), this vulnerability to the small change in the input data is a serious
concern.

Recently, many approaches to create adversarial perturbations were proposed,
as well as defense techniques to counteract these approaches, causing an
attack-defense arms race (Akhtar and Mian 2018; Chakraborty et al. 2018; Xu et
al. 2020). This race, however, barely affected those applications of neural
networks where the provably correct behavior of models is required. As a
result, more research was conducted in the field of certified robustness,
where the goal is to provide provable guarantees on the models’ behavior under
different input transformations. Randomized smoothing (Lecuyer et al. 2019;
Cohen, Rosenfeld, and Kolter 2019) is among the most effective and popular
approaches used to build provably robust models. Initially developed as a
certification tool against norm-bounded additive perturbations, it was later
extended to the cases of semantic perturbations (Li et al. 2021; Fischer,
Baader, and Vechev 2020; Hao et al. 2022), such as brightness shift and
translations. In the case of additive perturbations, this approach is about
replacing the base classifier $f$ with a smoothed one in the following form:

$g(x)=\mathbb{E}_{\varepsilon\sim\mathcal{N}(0,\sigma^{2})}f(x+\varepsilon).$
(1)

As it is shown in prior works (Lecuyer et al. 2019; Cohen, Rosenfeld, and
Kolter 2019; Salman et al. 2019), if the base classifier predicts well under
Gaussian noise applied to input $x$, then the smoothed one is guaranteed not
to change predicted class label in some $l_{2}-$ neighborhood of $x$ (however,
even if the base classifier makes an incorrect prediction, the smoothed one
might predict the correct class and be certified). Lately, it was shown (Li et
al. 2021; Hao et al. 2022) that if the input is subjected to semantic
transformation with the parameters sampled from a particular distribution,
then it is possible to derive the robustness guarantees for a smoothed model
against corresponding semantic transformation.

In this work, we focus on resolvable (Li et al. 2021) semantic transformations
and their compositions and develop a new framework for certified robustness of
classifiers under these perturbations. In a nutshell, we approach smoothing
from a different angle and show that a smoothed classifier is Lipschitz
continuous with respect to parameters of compositions of resolvable
transformations.

Previous works on certified robustness against semantic perturbations are
either non-scalable to large datasets or based on analytical derivations for a
particular transformation (Hao et al. 2022). In contrast, our method is
derived with no assumptions for semantic transformation and smoothing
distribution (except for resolvability and smoothness, respectively) and
provides a constructive numerical procedure for building a certification
procedure against a particular transformation.

Our contributions are summarized as follows:

  * •

We propose a universal certification approach against compositions of
resolvable transformations based on randomized smoothing;

  * •

We suggest a novel numerical procedure to verify the smoothed model’s
robustness with little to no computation overhead;

  * •

Our experimental study shows that the proposed approach provides state-of-the-
art guarantees in the majority of considered experimental setups.

Figure 1: Schematic illustration of the certification procedure: given an
input image $x$ of class $c$ and parametric transformation $\phi$, we sample
$N_{\text{max}}$ augmented images
$\\{\phi(x,\alpha^{1}),\dots,\phi(x,\alpha^{N_{\text{max}}})\\}$ and compute a
lower bound on $h_{c}(x)$ using Clopper-Pearson test in form
$\hat{h}_{c}(x)=B(\alpha^{*}/2,n,N_{\text{max}}-n+1),$ where $B$ is Beta
distribution and $n$ is the number of augmented images $\phi(x,\alpha^{j})$
for which the value of the base classifier (He et al. 2016)
$f_{c}(\phi(x,\alpha^{j}))>\frac{1}{2}$. Then, the certification condition
from theorem (1) is verified for the value $\hat{h}_{c}(x).$

## Preliminaries

In this work, we focus on the task of image classification. Given
$X\subset\mathbb{R}^{n}$ as the set of input objects and
$\mathcal{Y}=\\{1,2,\dots C\\}$ as the set of classes, the goal is to
construct a mapping $\hat{f}:X\to\mathcal{Y}$ assigning a label to each input
object. Following the convenient notation, this mapping may be represented as

$\hat{f}(x)=\operatorname*{argmax}_{i\in\mathcal{Y}}f_{i}(x),$ (2)

where $f:X\to[0,1]^{C}$ is a classification model and $f_{i}(x)$ refers to
$i-$ th predicted component.

Suppose that there exists a parametric mapping $\phi:X\times\Theta\to X$ that
corresponds to a semantic perturbation of the input of the classification
model, where $\Theta$ is the space of parameters of the perturbation. The goal
of this paper is to construct the framework to certify that a classifier is
robust at $x\in X$ to the transformation $\phi(x,\cdot)$ for some set of
parameters $\mathcal{B}(\beta_{0})$, where $\phi(x,\beta_{0})=x$ for all $x\in
X$.

A transform $\phi:X\times\Theta\to X$ is called resolvable (Li et al. 2021) if
for any parameter $\alpha~{}\in~{}\Theta$ there exists a continuously
differentiable function $\gamma_{\alpha}:\Theta\to\Theta,$ such that
$\phi(\phi(x,\alpha),\beta)=\phi(x,\gamma_{\alpha}(\beta)),\
\forall(x,\beta)\in X\times\Theta.$ An example of resolvable translation is
presented in the Figure 2. In this work, we analyze Lipschitz properties of
randomized smoothing to certify classification models against compositions of
resolvable transformations.

(a) Original image

(b) Translated image

Figure 2: An example of resolvable transformation. Note that the translation
with reflection padding is a revolvable with additive parameters, i.e.
$\phi(\phi(x,a),b)=\phi(x,a+b)$ holds for the composition of two translations.

## Proposed method

This section is devoted to the proposed certification approach for generalized
smoothing and its theoretical analysis.

### Randomized smoothing for semantic transformations

For the given baseline model $f:X\subset\mathbb{R}^{n}\to[0,1]^{C}$, input
image $x\in X$, resolvable transformation $\phi:X\times\Theta\to X$, and
perturbed image $y$, we construct the smoothed classifier $h(x)$ in the form
of expectation over $\rho(y|x)$ perturbation density conditioned on the
observed sample $x$:

$h(x)=\int_{\mathbb{R}^{n}}f(y)\rho(y|x)dy,$ (3)

The goal of this paper is to present a procedure that guarantees a smoothed
model to be robust to semantic perturbations, that is

$\operatorname*{argmax}_{i\in\\{1,2,\dots
C\\}}h_{i}(x)=\operatorname*{argmax}_{i\in\\{1,2,\dots
C\\}}h_{i}(\phi(x,\beta)),$ (4)

for all $\beta\in\mathcal{B}_{r}(\beta_{0})$, where $\phi(x,\beta_{0})=x.$ One
way to achieve robustness to parametric perturbation is to bound the Lipschitz
constant of the classifier (3) with respect to the smoothing parameters. It is
worth mentioning that the density $\rho(y|x)$ has to be continuously
differentiable with respect to perturbation parameters, otherwise, this
problem becomes ill-posed. To overcome this issue, we introduce additional
Gaussian smoothing.

Assuming that the perturbed sample has the form $\hat{x}=\phi(x,\beta)$, we
redefine an auxiliary variable $y=\phi(\hat{x},\alpha)+\varepsilon$,
$\varepsilon\sim\mathcal{N}(0,\sigma^{2}I_{n})$ and the overall conditional
probability density $\rho(y|\hat{x})$ in the form:

$\rho(y|\hat{x})=\frac{1}{(2\pi\sigma^{2})^{\frac{d}{2}}}\int_{R^{d}}\exp\left\\{-\frac{\|y-\phi(\hat{x},\alpha)\|_{2}^{2}}{2\sigma^{2}}\right\\}\tau(\alpha)d\alpha,$
(5)

where $\tau(\alpha)$ is the smoothing distribution of the transfromation.
Without loss of generality, it is assumed that
$\alpha\sim\mathcal{N}(0,I_{d})$ and $d=\mathrm{dim}(\Theta)$ is the number of
perturbation parameters, otherwise the smooth mapping $\psi$ from
$\mathcal{N}(0,I_{d})$ to the desired distribution should be established and
composed with the resolvable one, that is
$y=\phi(\hat{x},\psi(\alpha))+\varepsilon$.

### Robustness guarantee

In this section, we discuss the main theoretical result. Prior works are
mainly concentrated on estimating global Lipschitz constants, which may lead
to loose guarantees. Instead, we provide certification condition based on
local directional properties.

Let $x\in X$ be the input object of class $c$ and assume that the smoothed
classifier $h$ defined in (3) correctly classifies $x$, i.e.
$h_{c}(x)>\frac{1}{2}.$ Then the following result holds.

######  Theorem 1.

Certification condition.

Let $\beta(t):[0,1]\to\Theta$ be a smooth curve such that $\beta(0)=\beta_{0}$
and $\beta(1)=\beta$. Then there exist mappings
$\xi:\left[0,1\right]\to\mathbb{R}$ and $\hat{g}(\beta):\Theta\to\mathbb{R}$
such that if $\hat{g}(\beta)<-\xi(1-h_{c}(x))+\xi(1/2)$, then $h$ is robust at
$x$ for all $\beta\in\beta(t),$ where $t\in[0,1]$.

######  Remark.

The proof of the Theorem is moved to Appendix due to the limited space. The
procedure of computing the functions $\xi$ and $\hat{g}$ is described in the
numerical evaluation section (8). This theorem might be obviously applied for
multi-class setting, considering top class and ”runner-up” class behaviour as
in binary classification (Cohen, Rosenfeld, and Kolter 2019).

The theorem states that smoothed classifier is robust at the point $x$ to
transformation $\phi$ for all parameter values $\beta\in\beta(t),$ here
$t\in[0,1]$ if the certification condition is verified for a single parameter
value. Note that the certified set of parameters is not necessarily a ball-
vicinity of the initial parameter value. This is _the first approach for non-
ball-vicinity certification_ to our knowledge.

It is worth mentioning that $\xi$ might be derived analytically, for example,
for additive transformations with $\tau(\alpha)\sim\mathcal{N}(0,\kappa^{2})$,
$d=1$

$\xi(h)=\sqrt{\sigma^{2}+\kappa^{2}}\Phi^{-1}(h),$ (6)

where $\Phi^{-1}$ is a standard Gaussian distribution’s inverse cumulative
density function. This result coincides with the ones from (Cohen, Rosenfeld,
and Kolter 2019; Li et al. 2021) if $\sigma=0$.

### Numerical evaluation

The Theorem 1 anticipates a numerical procedure to compute certification
functions $\xi,~{}\hat{g}$. In this section, we describe this procedure in
detail.

Here and below, we assume that the input sample $x$ is fixed and treat
smoothed model $h$ as the function of the perturbation parameter $\beta$,
namely $h(\phi(x,\beta))\equiv h(\hat{x})\equiv h(x,\beta)\equiv h(\beta)$ for
simplicity. Within our framework, functions $\xi,~{}\hat{g}$ are derived as
the ones bounding the smoothed classifier’s directional derivative with
respect to the perturbation parameter:

$\langle\nabla_{\beta}h(\beta),\beta\rangle\leq w(h(\beta),\beta)\leq
p(h)g(\beta),$ (7)

where $w(h(\beta),\beta)$ is an upper bound on the directional derivative that
also has a bound as a product of a function of $h$ and the function of
$\beta$. If the functions $p(h)$ and $g(\beta)$ are known, the mappings from
Theorem 1 has the following form:

$\xi(h)=\int\frac{1}{p(h)}dh,\quad\hat{g}(\beta)=\int^{1}_{0}g(\beta(t))dt.$
(8)

#### Bounding the directional derivative

As it was mentioned, a local bound for the directional derivative in the form
from (7) is used to compute functions $\xi,\hat{g}$ from Theorem 1. However,
in case of complicated form of conditional density in (5), it may be
unfeasible to construct an exact bound. Instead, we propose to use a numerical
procedure to bound directional derivatives of smoothed model:

$\displaystyle\nabla_{\beta}h=\int f(y)\nabla_{\beta}\rho(y\mid\hat{x})dy$ (9)
$\displaystyle=\int
f(y)\eta(y,\hat{x})\rho(y\mid\hat{x})dy,\quad\eta(y,\hat{x})=\nabla_{\beta}\log\rho(y\mid\hat{x})$

One way to do so is to find the worst base classifier in (10), i.e., the one
with the largest bound. Without loss of generality, the search for the worst
classifier may be formulated as the scalar problem:

$\displaystyle\operatorname*{argmax}_{q\in\mathcal{Q}}\int
q(y)\eta(y,\hat{x})\rho(y\mid\hat{x})dy,$ (10) $\displaystyle\text{s.t.}\quad
h(\hat{x})=\int q(y)\rho(y\mid\hat{x})dy,$

where $\mathcal{Q}=\\{q|q:X\to[0,1]\\}$ and $h$ is the fixed smoothed model of
$f$. Otherwise, one can suggest using a projection onto an arbitrary unit
vector $u$ as an objective in the optimization problem (10), namely,
$\langle\nabla_{\beta}h,u\rangle$, $\|u\|=1$. Under the specific choice of
resolvable transform $\phi$ and perturbation distribution $\tau(\alpha)$, (10)
admits an analytical solution.

In general, if the density evaluation $\rho(y|\hat{x})$ is available, the
solution of (10) could be obtained semi-analytically. Indeed, (10) is linear
with the respect to $q$, hence using finite-sample estimations

$\displaystyle\int
q(y)\rho(y|\hat{x})dy\approx\frac{1}{M}\sum_{k=1}^{M}q_{k},$ (11)
$\displaystyle\int
q(y)\eta(y,\hat{x})\rho(y|\hat{x})dy\approx\frac{1}{M}\sum_{k=1}^{M}q_{k}\eta_{k},$

and, consequently, additional constraints $0\leq q_{k}\leq 1,\forall k\in
1,\ldots,M$, the solution is given either by $q_{k}=0$ or $q_{k}=1$, selection
$\lfloor hM\rfloor$ largest or smallest $\eta_{k}$ depending on bound we need
to obtain.

This provides the numerical scheme to construct arbitrary tight bound
$w(h,\beta)$ on the directional derivative $\nabla_{\beta}h$ (9). Moreover,
since $h(\beta)$ is a smooth function over $\beta$, it has zero gradient in
points of global minima and maxima, which corresponds to $h=0$ and $h=1$.

#### Log-density estimation

Since the exact evaluation of the expectation from (5) is challenging, we
emulate sampling from the conditional density $\rho(y|\hat{x})$ by estimating
the derivative of the log-density $\eta(y,\hat{x})$ from (9) with respect to
perturbation parameters $\beta$.

Thus, using the first-order approximation for the resolvable transform:

$\phi(\hat{x},\alpha)\approx\phi\left(\hat{x},\alpha_{0}\right)+J(\alpha_{0})\left(\alpha-\alpha_{0}\right),\quad
J(\alpha)=\frac{\partial\phi}{\partial\alpha}$

we establish Laplace’s posterior log-density estimation:

$\log\rho(y\mid\hat{x})\approx\log
C-\frac{\|\mu\|^{2}}{2\sigma^{2}}+\left(M\alpha_{0},\alpha_{0}\right)-\frac{1}{2}\log\det
M,$ (12)

where $M=J^{T}J+\sigma^{2}I$ and $\mu=y-\phi(\hat{x},\alpha)+J\alpha$.
Finally, an approximation to the initial point of the expansion above is given
via one iteration of the Gauss-Newton method:

$\alpha_{0}\approx\left(J^{\top}J+\sigma^{2}I\right)^{-1}(y-\phi(\hat{x},\alpha)+J\alpha),$
(13)

which is an accurate approximation.

While the above derivation admits an arbitrary attack transform $\phi$, for
the resolvable one, there exists a closed-form limit when $\sigma\to 0$. The
last is summarized in the Lemma 1, allowing us either to compute log-density
analytically or through automatic differentiation tools.

######  Lemma 1 (Gradient of log-density for resolvable transformations).

If we have the log-density (5)
$\log\rho(y|\hat{x})=z(\alpha,\beta)=z(\alpha(\beta),\beta)$, then

$\nabla_{\beta}z=\frac{\partial z}{\partial\beta}-\frac{\partial
z}{\partial\alpha}\left(\frac{\partial\gamma}{\partial\alpha}\right)^{\dagger}\frac{\partial\gamma}{\partial\beta},$

where $\gamma$ is a resolving function of the transform:
$\phi(\phi(x,\beta),\alpha)=\phi(x,\gamma(\alpha,\beta))$.

The overall procedure is presented in Algorithms 1, 2

Algorithm 1 Numerical Estimation of $\xi$ and $\hat{g}$ for the Resolvable
Transform $\phi$

0: $\phi$ – type of transformation, $N_{s}$ \- number of samples, $\gamma$ –
resolving function for the transform, $\beta_{0}$ – identity parameters of
$\phi$, $B$ – parametric grid of $d_{b}$ points to estimate bounds on, $d$ –
dimension of transform, $x$ – random point.

1:
$\\{p_{i}\\}_{i=0}^{N_{s}},\\{g_{j}\\}_{j=0}^{d_{b}}\leftarrow\textsc{ComputeNormedBounds}(\gamma,\beta_{0},B,N_{s},\phi,d,x)$

2:
$\\{\xi_{i}\\}_{i=0}^{N_{s}}\leftarrow\frac{1}{N_{s}}\textsc{cumsum}\left(p_{i}^{-1}\right)$

3: $\xi\leftarrow\textsc{Interpolate}(\textsc{linspace}(0,1,N_{s}),\xi_{i})$

4: $z\leftarrow\textsc{Interpolate}\left(B,\\{g_{j}\\}_{j=0}^{d_{b}}\right)$

5: for $\beta_{j}\in B$ do

6: $\hat{g}_{j}=\int_{0}^{1}z((1-t)\beta_{0}+t\beta_{j})dt$

7: end for

8: $\hat{g}=\textsc{Interpolate}(B,\\{\hat{g}_{j}\\})$

9:

10: return $\xi(h),\hat{g}(\beta)$

Algorithm 2 Compute Normed Bounds

0: $\phi$ – type of transformation, $N_{s}$ – number of samples, $\gamma$ –
resolving function for the transform, $\beta_{0}$ – identity parameters of
$\phi$, $B$ – parametric grid of $d_{b}$ points to estimate bounds on, $d$ –
dimension of transform, $x$ – random point.

1: for $\beta_{j}\in B$ do

2: $c_{j}=\mathcal{N}(0,I_{d})$

3: $z\leftarrow\textsc{ComputeLogRho}(x,\gamma,\beta,c_{j},\phi,N_{s})$
{Equation (12)}

4:
$\eta\leftarrow\textsc{ComputeGradLogRho}(x,\gamma,\beta_{j},\alpha,\phi,N_{s},z)$
{Equation (12), Lemma 1}

5: $t\leftarrow(\beta_{j}-\beta_{0})/\|\beta-\beta_{0}\|$

6: $\eta\leftarrow\eta~{}t$

7: $\eta\leftarrow\eta-\textsc{Mean}(\eta)$

8: $\eta\leftarrow\textsc{Sort}(\eta,\text{reverse})$

9: $\text{bound}_{j}\leftarrow\textsc{Cumsum}(\eta)/N_{s}$

10: $g_{j}\leftarrow\max(\text{bound}_{j})\cdot\|\beta_{0}-\beta_{j}\|$

11: $\text{bound}_{j}\leftarrow\text{bound}_{j}/\max(\text{bound}_{j})$

12: end for

13: $p_{i}=\max_{j}{\text{bound}_{ji}}$

14: return $\\{p_{i}\\},\\{g_{j}\\}$

## Experiments

We conducted experiments with ResNet-50 (He et al. 2016) model with an
additional normalization layer as in (Cohen, Rosenfeld, and Kolter 2019; Li et
al. 2021). The proposed approach was assessed on a large-scale ImageNet
dataset (Russakovsky et al. 2015). For a fixed type of semantic transformation
$\phi$, we train base classifier $f$ with corresponding augmentation with the
parameters sampled from the distribution mentioned in the table 1 to make $f$
more empirically robust to this transformation. Depending on the
transformation type, the fine-tuning of the pre-trained models with
augmentations takes from $3$ to $18$ hours on a $1$ Nvidia V-100 16GB GPU. The
combination of the cross-entropy and consistency losses (Jeong and Shin 2020)
is chosen as an optimization objective, and the fine-tuning is conducted for
$2$ epochs using SGD (learning rate is $10^{-3}$, momentum is $0.95$).

To evaluate our approach, we compute _certified robust accuracy_ (CRA) of the
smoothed classifier. Certified robust accuracy is a fraction of correctly
predicted images $x_{i}$ from the test set on which the certification
condition is met.

CRA is evaluated on $500$ images sampled randomly from the test dataset. To
estimate the prediction of the smoothed classifier $h$, we compute the lower
bound of the Clopper-Pearson confidence interval (Clopper and Pearson 1934)
over the sample size $N_{\text{max}}=1000$ and confidence level
$\alpha^{*}=10^{-3}$ for each initial image $x.$ To estimate mappings
$\xi,\hat{g}$, we sample parameters $\alpha$ from Normal distribution and map
them to the desired distribution (see table 1) using the numerical scheme.

We evaluate our approach against (Li et al. 2021) and (Muravev and Petiushko
2021) and present the results in table 1. Our method performs comparably to
main competitors or better. Our method achieves state-of-the-art robustness
certificates for some transformations, such as Gamma-Contrast and Contrast-
Translation. In our experiments, we sample parameters of additive
transformations from Normal distribution, for multiplicative transformations –
from LogNormal and Rayleigh distributions, for exponential transformations –
from Rayleigh distribution. For Contrast-Brightness transformation
($\phi(x,(c,b))=cx+b$), our approach performs comparably to the state-of-the-
art.

We did not compare with GSmooth (Hao et al. 2022) as they do not provide
results on ImageNet and require two model setup. Additionally, we did not
compare results on 1D attacks, such as brightness, blur, or contrast as our
primary focus revolves around certifying combinations of attacks. Our
framework does not support non-resolvable transforms, for example, rotation.
TSS (Li et al. 2021) presents certification results for brightness-contrast,
brightness-translation, and translation, thus we compare their results with
those obtained with our approach.

Transformations | $\beta$ | $R_{l}$ | $R_{r}$ | Distribution | CRA (ours) | CRA-TSS | CRA-MP
---|---|---|---|---|---|---|---
Contrast | $c$ | 0.5 | 2.0 |  LogNorm(0, 0.6) | 0.34 | 0.28 | –
Brightness | $b$ | -0.4 | 0.4 | $\mathcal{N}(0,0.6)$
Gamma | $\gamma$ | 0.8 | 1.4 | ${\rm Rayleigh}(0,0.1)$ | 0.33 | – | –
Contrast | $c$ | 0.6 | 2.0 | ${\rm LogNorm}(0,0.1)$
Brightness | $b$ | -0.2 | 0.2 | $\mathcal{N}(0,0.4)$ | 0.26 | 0.02 | –
Translation | $T_{x},T_{y}$ | -56 | 56 | $\mathcal{N}(0,30)$
Contrast | $c$ | 0.5 | 2.0 | ${\rm LogNorm}(0,0.4)$ | 0.02 | – | –
Translation | $T_{x},T_{y}$ | -56 | 56 | $\mathcal{N}(0,30)$ |  |
Translation | $T_{x},T_{y}$ | -56 | 56 | $\mathcal{N}(0,50)$ | 0.25 | 0.15 | –
Contrast | $c$ | 0.8 | 1.5 | ${\rm LogNorm}(0,0.8)$ | 0.02 | – | –
Brightness | $b$ | -0.2 | 0.2 | $\mathcal{N}(0,0.8)$
Translation | $T_{x},T_{y}$ | -25 | 25 | $\mathcal{N}(0,50)$
Translation | $T_{x},T_{y}$ | -3 | 3 | $\mathcal{N}(0,30)$ | 0.20 | – | –
Blur | $r_{b}$ | 1 | 3 | ${\rm Rayleigh}(2)$
Brightness | $b$ | -0.1 | 0.1 | $\mathcal{N}(0,0.8)$
Contrast | $c$ | 0.95 | 1.05 | ${\rm LogNorm}(0,0.8)$
Gamma | $\gamma$ | 1.0 | 2.0 | ${\rm Rayleigh}(0.1)$ | 0.36 | – | 0.33
Gamma | $\gamma$ | 0.5 | 1.0 | ${\rm Rayleigh}(0.1)$ | 0.36 | – | 0.35
Table 1:  Quantitative results on ImageNet dataset. We report smoothing
distributions and certified robust accuracy for given transformations for our
approach and competitors’ methods. Symbol ${}^{\prime\prime}-^{\prime\prime}$
in the table corresponds to the transformation that a method does not certify
the model against the given distribution parameters. For each transformation
type, we calculate smoothed classifier using unbounded smoothing distribution
and measure the CRA within fixed attack range
$R_{l}~{}\leq~{}\beta~{}\leq~{}R_{r}$.
$c,~{}b,~{}\gamma,~{}(T_{x},T_{y}),~{}r_{b}$ represent contrast, brightness,
gamma-correction, translations and Gaussian blur attacks’ parameters,
respectively. CRA-TSS and CRA-MP correspond to the certified accuracy of the
methods from (Li et al. 2021) and (Muravev and Petiushko 2021), respectively.

(a) Contrast and Brightness

(b) Gamma and Contrast

(c) Translation

Figure 3: Visualization of certified robust accuracy for the subset of
parameter space for different transformations. For the points from a parameter
subset, certified robust accuracy is computed; the values of CRA are presented
in the corresponding colorbars.

## Limitations

This section is devoted to a discussion of the limitations of the proposed
approach. We only discuss the limitation of our method to a particular type of
transformations and the probabilistic nature of the robustness certificates it
yields.

### Non-resolvable transformations

The major limitation of the proposed approach is the narrow set of
perturbations it is suitable to certify the models against. It is worth
mentioning that in the case of non-resolvable transformation, the conditional
density (5) either does not exist when $\sigma\to 0$ or is not a continuously
differentiable function with respect to transformation parameter.

### Probabilistic certification

Recall that our approach is based on the randomized smoothing technique, and,
hence, the certified model can not be exactly evaluated. In our experimental
setting, for the sample $x$ of class $c$, the true value of the smoothed
classifier $h(x)$ is estimated as the lower bound of the Clopper-Pearson
confidence interval (Clopper and Pearson 1934) over $N_{\text{max}}$ samples
for some confidence level $\alpha^{*}$. Namely,
$\hat{h}(x)=B(\alpha^{*}/2,n,N_{\text{max}}-n+1),$ where $B$ is Beta
distribution, $N_{\text{max}}$ is the sample size and $n$ is the number of
perturbations for which $f(\phi(x,\alpha^{j}))>\frac{1}{2}$. Thus, our
approach produces certificates with probability $p\geq 1-\alpha^{*},$ where
$\alpha^{*}$ is the upper bound on the probability to return an overestimated
lower bound for the value $h(x).$ In our settings, $\alpha^{*}=10^{-3}$ and
$N_{\text{max}}=1000.$

Assessing the error of empirical cumulative distribution functions (ECDFs)
derived from numerical methods lies beyond the focus of our study. While
certain transformations admit analytical solutions, numerical schemes
inherently carry errors. However, it’s feasible to attain the desired
precision by augmenting the sample size and refining the approximation with
additional points.

## Related Work

### Adversarial attacks and empirical defenses

The vulnerability of deep learning models to specifically-crafted
imperceptible additive transformations was accidentally discovered in prior
works (Szegedy et al. 2013; Biggio et al. 2013). In (Goodfellow, Shlens, and
Szegedy 2014), the fast gradient sign method (FGSM) was proposed, and the
empirical effectiveness of adversarial training against such transformations
was discussed. Lately, several ways to exploit this vulnerability in the
white-box setting were proposed, such as projected gradient descent (Madry et
al. 2017), DeepFool (Moosavi-Dezfooli, Fawzi, and Frossard 2016), Carlini-
Wanger attack (Carlini and Wagner 2017), as well as plenty of black-box
approaches (Ilyas et al. 2018; Guo et al. 2019; Andriushchenko et al. 2020;
Dong et al. 2019; Bhambri et al. 2019; Uesato et al. 2018; Brendel, Rauber,
and Bethge 2017). Many applications of adversarial attacks were lately
studied, especially in the real-world setting: face recognition (Eykholt et
al. 2018; Komkov and Petiushko 2021; Pautov et al. 2019; Sharif et al. 2019),
detection (Kaziakhmedov et al. 2019; Bose and Aarabi 2018), segmentation
(Hendrik Metzen et al. 2017; Ma et al. 2021; Kaviani, Han, and Sohn 2022) and
other supervised settings were shown to be affected by this vulnerability. At
the same time, empirical defenses (Madry et al. 2017; Uesato et al. 2018;
Athalye, Carlini, and Wagner 2018) against such attacks were proposed. Mainly
they are narrowed to a specific attack setting or to crafting the worst-case
examples and including ones in the training set. However, such defenses did
not provide enough guarantees to unseen attacks, and consequently, new
adaptive attacks were created to overcome previously suggested defenses,
causing an arms race.

### Certification against additive attacks

Recent research in the field of certified robustness incorporates plenty of
verification protocols (Li et al. 2020). There are two major approaches to
certify classifiers against additive transformations: deterministic (Gowal et
al. 2018; Wei and Kolter 2022) and probabilistic (Cohen, Rosenfeld, and Kolter
2019; Lecuyer et al. 2019; Salman et al. 2019). The deterministic approach
guarantees that the model is robust at some point $x$ if there is no point
from the vicinity of $x$ such that it is classified differently from $x$. In
contrast, probabilistic approaches are mainly based on randomized smoothing
and utilize global (Gouk et al. 2021; Tsuzuku, Sato, and Sugiyama 2018; Anil,
Lucas, and Grosse 2019) or local (Wong and Kolter 2018; Wong et al. 2018;
Dvijotham et al. 2018) Lipschitz properties of the smoothed classifier.
However, since a smoothed model can not be exactly evaluated, all the
robustness guarantees hold with some probability depending on the finite
sample estimation of the smoothed model (Cohen, Rosenfeld, and Kolter 2019).

Among the deterministic methods, the ones using solver-based approaches verify
the model’s robustness entirely but are not scalable due to computation
complexity and usually are restricted to simple architectures (Pulina and
Tacchella 2010; Cheng, Nührenberg, and Ruess 2017; Katz et al. 2019; Tjeng,
Xiao, and Tedrake 2017). In contrast, approaches that utilize linear
relaxation do not provide the tightest possible robustness certificates but
are model-agnostic and applicable for large datasets (Gowal et al. 2019; Zhang
et al. 2018; Singh et al. 2019b; Wong and Kolter 2018). The other
deterministic methods usually are based on particular properties of neural
networks, such as Lipschitz continuity (Weng et al. 2018; Lee, Lee, and Park
2020; Levine and Feizi 2021; Tsuzuku, Sato, and Sugiyama 2018) or curvature of
the decision boundary (Singla and Feizi 2020). On the other hand,
probabilistic approaches usually utilize an assumption about the smoothness of
the model. The majority of them, although they produce the certificates that
hold with some probability, are among the state-of-the-art methods to certify
neural networks against additive transformations (Cohen, Rosenfeld, and Kolter
2019; Lecuyer et al. 2019; Levine et al. 2020; Mohapatra et al. 2020a).

### Certification against semantic transformations

Semantic transformations are proved to fool deep learning models easily
(Hosseini and Poovendran 2018; Ghiasi, Shafahi, and Goldstein 2020; Joshi et
al. 2019), and, consequently, empirical studies of robustness against such
transformations appeared (Hendrycks and Dietterich 2019; Tsai et al. 2022).
However, certified robustness under semantic transformations is still an open
issue (Mohapatra et al. 2019; Li et al. 2021; Hao et al. 2022). Recently,
quite a few approaches to tackle semantic transformations were proposed that
are based on enumeration (Pei et al. 2017), interval bound propagation
(Balunovic et al. 2019; Singh et al. 2019a; Mohapatra et al. 2020b), and
randomized smoothing (Fischer, Baader, and Vechev 2020; Li et al. 2021; Hao et
al. 2022). While efficient enumeration is applicable only to discrete
transforms, linear relaxation provides worse results when compared to
smoothing. On the other hand, when deterministic guarantees are infeasible,
probabilistic approaches (Pautov et al. 2022; Weng et al. 2019; Wicker et al.
2020) to estimate the probability of the model to fail when an attack is
parameterized provide some insights about the model’s robustness. It is worth
mentioning that empirical robustness may be improved by incorporating
adversarial training. However, the training procedure on large-scale datasets
is time-consuming (Tsai et al. 2022).

A promising way to tackle the certified robustness is based on transformation-
specific randomized smoothing (Li et al. 2021; Hao et al. 2022). The idea of
transformation-specific smoothing is to consider Lipschitz continuity of a
smoothed model with respect to the transformation parameters. According to (Li
et al. 2021), this type of smoothing may be applied to two categories of
transformations: resolvable and differentially resolvable, where the last
implies taking into account interpolation errors. However, previous attempts
to apply transformation-specific smoothing to certify classifiers against
semantic transformations either might be infeasible for more complicated
transformations (Li et al. 2021) or require a surrogate network to represent
the transformation and not scalable to large datasets (Hao et al. 2022). As a
separate application of transformation-dependent smoothing, (Muravev and
Petiushko 2021) specifically studied Gamma correction as a multiplicative
transformation. This work provides asymmetrical guarantees and estimates the
certification quality, considering realistic image compression into 8-bit RGB.

## Conclusion and future work

In this paper, we propose General Lipschitz, a novel framework to certify
neural networks against resolvable transformations and their compositions.
Based on transformation-dependent randomized smoothing, our approach yields
robustness certificates for complex parameterized subsets of parameter space.
One of the advantages of the framework is the numerical procedure that
produces certificates for a whole parameters subset by verifying certification
condition in a single point of parameter space. Our experimental study shows
that the proposed method achieves certified robust accuracy comparable to the
state-of-the-art techniques and outperforms them in some experimental
settings. It is important that our approach allows to certify models against
resolvable transformations only, so one possible direction for the future work
is to extend it to the case of differentially resolvable transformations.

## References

  * Akhtar and Mian (2018) Akhtar, N.; and Mian, A. 2018.  Threat of adversarial attacks on deep learning in computer vision: A survey.  _Ieee Access_ , 6: 14410–14430.
  * Andriushchenko et al. (2020) Andriushchenko, M.; Croce, F.; Flammarion, N.; and Hein, M. 2020.  Square attack: a query-efficient black-box adversarial attack via random search.  In _European Conference on Computer Vision_ , 484–501. Springer.
  * Anil, Lucas, and Grosse (2019) Anil, C.; Lucas, J.; and Grosse, R. 2019.  Sorting out Lipschitz function approximation.  In _International Conference on Machine Learning_ , 291–301. PMLR.
  * Athalye, Carlini, and Wagner (2018) Athalye, A.; Carlini, N.; and Wagner, D. 2018.  Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples.  In _International conference on machine learning_ , 274–283. PMLR.
  * Balunovic et al. (2019) Balunovic, M.; Baader, M.; Singh, G.; Gehr, T.; and Vechev, M. 2019.  Certifying geometric robustness of neural networks.  _Advances in Neural Information Processing Systems_ , 32.
  * Bhambri et al. (2019) Bhambri, S.; Muku, S.; Tulasi, A.; and Buduru, A. B. 2019.  A survey of black-box adversarial attacks on computer vision models.  _arXiv preprint arXiv:1912.01667_.
  * Biggio et al. (2013) Biggio, B.; Corona, I.; Maiorca, D.; Nelson, B.; Šrndić, N.; Laskov, P.; Giacinto, G.; and Roli, F. 2013.  Evasion attacks against machine learning at test time.  In _Joint European conference on machine learning and knowledge discovery in databases_ , 387–402. Springer.
  * Bose and Aarabi (2018) Bose, A. J.; and Aarabi, P. 2018.  Adversarial attacks on face detectors using neural net based constrained optimization.  In _2018 IEEE 20th International Workshop on Multimedia Signal Processing (MMSP)_ , 1–6. IEEE.
  * Brendel, Rauber, and Bethge (2017) Brendel, W.; Rauber, J.; and Bethge, M. 2017.  Decision-based adversarial attacks: Reliable attacks against black-box machine learning models.  _arXiv preprint arXiv:1712.04248_.
  * Carlini and Wagner (2017) Carlini, N.; and Wagner, D. 2017.  Towards evaluating the robustness of neural networks.  In _2017 ieee symposium on security and privacy (sp)_ , 39–57. Ieee.
  * Chakraborty et al. (2018) Chakraborty, A.; Alam, M.; Dey, V.; Chattopadhyay, A.; and Mukhopadhyay, D. 2018\.  Adversarial attacks and defences: A survey.  _arXiv preprint arXiv:1810.00069_.
  * Chen et al. (2019) Chen, S.-T.; Cornelius, C.; Martin, J.; and Chau, D. H. 2019.  Shapeshifter: Robust physical adversarial attack on faster r-cnn object detector.  In _Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2018, Dublin, Ireland, September 10–14, 2018, Proceedings, Part I 18_ , 52–68. Springer.
  * Cheng, Nührenberg, and Ruess (2017) Cheng, C.-H.; Nührenberg, G.; and Ruess, H. 2017.  Maximum resilience of artificial neural networks.  In _International Symposium on Automated Technology for Verification and Analysis_ , 251–268. Springer.
  * Chernikova et al. (2019) Chernikova, A.; Oprea, A.; Nita-Rotaru, C.; and Kim, B. 2019.  Are self-driving cars secure? evasion attacks against deep neural networks for steering angle prediction.  In _2019 IEEE Security and Privacy Workshops (SPW)_ , 132–137. IEEE.
  * Clopper and Pearson (1934) Clopper, C. J.; and Pearson, E. S. 1934.  The use of confidence or fiducial limits illustrated in the case of the binomial.  _Biometrika_ , 26(4): 404–413.
  * Cohen, Rosenfeld, and Kolter (2019) Cohen, J.; Rosenfeld, E.; and Kolter, Z. 2019.  Certified adversarial robustness via randomized smoothing.  In _International Conference on Machine Learning_ , 1310–1320. PMLR.
  * Dong et al. (2019) Dong, Y.; Su, H.; Wu, B.; Li, Z.; Liu, W.; Zhang, T.; and Zhu, J. 2019.  Efficient decision-based black-box adversarial attacks on face recognition.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 7714–7722.
  * Dvijotham et al. (2018) Dvijotham, K.; Stanforth, R.; Gowal, S.; Mann, T. A.; and Kohli, P. 2018.  A Dual Approach to Scalable Verification of Deep Networks.  In _UAI_ , volume 1, 3.
  * Eykholt et al. (2018) Eykholt, K.; Evtimov, I.; Fernandes, E.; Li, B.; Rahmati, A.; Xiao, C.; Prakash, A.; Kohno, T.; and Song, D. 2018.  Robust physical-world attacks on deep learning visual classification.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 1625–1634.
  * Fischer, Baader, and Vechev (2020) Fischer, M.; Baader, M.; and Vechev, M. 2020.  Certified defense to image transformations via randomized smoothing.  _Advances in Neural Information Processing Systems_ , 33: 8404–8417.
  * Ghiasi, Shafahi, and Goldstein (2020) Ghiasi, A.; Shafahi, A.; and Goldstein, T. 2020.  Breaking certified defenses: Semantic adversarial examples with spoofed robustness certificates.  _arXiv preprint arXiv:2003.08937_.
  * Goodfellow, Shlens, and Szegedy (2014) Goodfellow, I. J.; Shlens, J.; and Szegedy, C. 2014.  Explaining and harnessing adversarial examples.  _arXiv preprint arXiv:1412.6572_.
  * Gouk et al. (2021) Gouk, H.; Frank, E.; Pfahringer, B.; and Cree, M. J. 2021.  Regularisation of neural networks by enforcing lipschitz continuity.  _Machine Learning_ , 110(2): 393–416.
  * Gowal et al. (2018) Gowal, S.; Dvijotham, K.; Stanforth, R.; Bunel, R.; Qin, C.; Uesato, J.; Arandjelovic, R.; Mann, T.; and Kohli, P. 2018.  On the effectiveness of interval bound propagation for training verifiably robust models.  _arXiv preprint arXiv:1810.12715_.
  * Gowal et al. (2019) Gowal, S.; Dvijotham, K. D.; Stanforth, R.; Bunel, R.; Qin, C.; Uesato, J.; Arandjelovic, R.; Mann, T.; and Kohli, P. 2019.  Scalable verified training for provably robust image classification.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 4842–4851.
  * Guo et al. (2019) Guo, C.; Gardner, J.; You, Y.; Wilson, A. G.; and Weinberger, K. 2019.  Simple black-box adversarial attacks.  In _International Conference on Machine Learning_ , 2484–2493. PMLR.
  * Hao et al. (2022) Hao, Z.; Ying, C.; Dong, Y.; Su, H.; Song, J.; and Zhu, J. 2022.  Gsmooth: Certified robustness against semantic transformations via generalized randomized smoothing.  In _International Conference on Machine Learning_ , 8465–8483. PMLR.
  * He et al. (2016) He, K.; Zhang, X.; Ren, S.; and Sun, J. 2016.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 770–778.
  * Hendrik Metzen et al. (2017) Hendrik Metzen, J.; Chaithanya Kumar, M.; Brox, T.; and Fischer, V. 2017.  Universal adversarial perturbations against semantic image segmentation.  In _Proceedings of the IEEE international conference on computer vision_ , 2755–2764.
  * Hendrycks and Dietterich (2019) Hendrycks, D.; and Dietterich, T. 2019.  Benchmarking neural network robustness to common corruptions and perturbations.  _arXiv preprint arXiv:1903.12261_.
  * Hosseini and Poovendran (2018) Hosseini, H.; and Poovendran, R. 2018.  Semantic adversarial examples.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops_ , 1614–1619.
  * Ilyas et al. (2018) Ilyas, A.; Engstrom, L.; Athalye, A.; and Lin, J. 2018.  Black-box adversarial attacks with limited queries and information.  In _International conference on machine learning_ , 2137–2146. PMLR.
  * Jeong and Shin (2020) Jeong, J.; and Shin, J. 2020.  Consistency regularization for certified robustness of smoothed classifiers.  _Advances in Neural Information Processing Systems_ , 33: 10558–10570.
  * Joshi et al. (2019) Joshi, A.; Mukherjee, A.; Sarkar, S.; and Hegde, C. 2019.  Semantic adversarial attacks: Parametric transformations that fool deep classifiers.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 4773–4783.
  * Katz et al. (2019) Katz, G.; Huang, D. A.; Ibeling, D.; Julian, K.; Lazarus, C.; Lim, R.; Shah, P.; Thakoor, S.; Wu, H.; Zeljić, A.; et al. 2019.  The marabou framework for verification and analysis of deep neural networks.  In _Computer Aided Verification: 31st International Conference, CAV 2019, New York City, NY, USA, July 15-18, 2019, Proceedings, Part I 31_ , 443–452. Springer.
  * Kaviani, Han, and Sohn (2022) Kaviani, S.; Han, K. J.; and Sohn, I. 2022.  Adversarial attacks and defenses on AI in medical imaging informatics: A survey.  _Expert Systems with Applications_ , 116815.
  * Kaziakhmedov et al. (2019) Kaziakhmedov, E.; Kireev, K.; Melnikov, G.; Pautov, M.; and Petiushko, A. 2019.  Real-world attack on MTCNN face detection system.  In _2019 International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON)_ , 0422–0427. IEEE.
  * Komkov and Petiushko (2021) Komkov, S.; and Petiushko, A. 2021.  Advhat: Real-world adversarial attack on arcface face id system.  In _2020 25th International Conference on Pattern Recognition (ICPR)_ , 819–826. IEEE.
  * Kurakin, Goodfellow, and Bengio (2018) Kurakin, A.; Goodfellow, I. J.; and Bengio, S. 2018.  Adversarial examples in the physical world.  In _Artificial intelligence safety and security_ , 99–112. Chapman and Hall/CRC.
  * Lecuyer et al. (2019) Lecuyer, M.; Atlidakis, V.; Geambasu, R.; Hsu, D.; and Jana, S. 2019.  Certified robustness to adversarial examples with differential privacy.  In _2019 IEEE Symposium on Security and Privacy (SP)_ , 656–672. IEEE.
  * Lee, Lee, and Park (2020) Lee, S.; Lee, J.; and Park, S. 2020.  Lipschitz-certifiable training with a tight outer bound.  _Advances in Neural Information Processing Systems_ , 33: 16891–16902.
  * Levine et al. (2020) Levine, A.; Kumar, A.; Goldstein, T.; and Feizi, S. 2020.  Tight second-order certificates for randomized smoothing.  _arXiv preprint arXiv:2010.10549_.
  * Levine and Feizi (2021) Levine, A. J.; and Feizi, S. 2021.  Improved, deterministic smoothing for L_1 certified robustness.  In _International Conference on Machine Learning_ , 6254–6264. PMLR.
  * Li et al. (2020) Li, L.; Qi, X.; Xie, T.; and Li, B. 2020.  Sok: Certified robustness for deep neural networks.  _arXiv preprint arXiv:2009.04131_.
  * Li et al. (2021) Li, L.; Weber, M.; Xu, X.; Rimanic, L.; Kailkhura, B.; Xie, T.; Zhang, C.; and Li, B. 2021.  Tss: Transformation-specific smoothing for robustness certification.  In _Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security_ , 535–557.
  * Ma et al. (2021) Ma, X.; Niu, Y.; Gu, L.; Wang, Y.; Zhao, Y.; Bailey, J.; and Lu, F. 2021.  Understanding adversarial attacks on deep learning based medical image analysis systems.  _Pattern Recognition_ , 110: 107332.
  * Madry et al. (2017) Madry, A.; Makelov, A.; Schmidt, L.; Tsipras, D.; and Vladu, A. 2017.  Towards deep learning models resistant to adversarial attacks.  _arXiv preprint arXiv:1706.06083_.
  * Mohapatra et al. (2019) Mohapatra, J.; Chen, P.-Y.; Liu, S.; Daniel, L.; et al. 2019.  Towards verifying robustness of neural networks against semantic perturbations.  _arXiv preprint arXiv:1912.09533_.
  * Mohapatra et al. (2020a) Mohapatra, J.; Ko, C.-Y.; Weng, T.-W.; Chen, P.-Y.; Liu, S.; and Daniel, L. 2020a.  Higher-order certification for randomized smoothing.  _Advances in Neural Information Processing Systems_ , 33: 4501–4511.
  * Mohapatra et al. (2020b) Mohapatra, J.; Weng, T.-W.; Chen, P.-Y.; Liu, S.; and Daniel, L. 2020b.  Towards verifying robustness of neural networks against a family of semantic perturbations.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 244–252.
  * Moosavi-Dezfooli, Fawzi, and Frossard (2016) Moosavi-Dezfooli, S.-M.; Fawzi, A.; and Frossard, P. 2016.  Deepfool: a simple and accurate method to fool deep neural networks.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2574–2582.
  * Muravev and Petiushko (2021) Muravev, N.; and Petiushko, A. 2021.  Certified robustness via randomized smoothing over multiplicative parameters of input transformations.  _arXiv preprint arXiv:2106.14432_.
  * Pautov et al. (2019) Pautov, M.; Melnikov, G.; Kaziakhmedov, E.; Kireev, K.; and Petiushko, A. 2019.  On adversarial patches: real-world attack on arcface-100 face recognition system.  In _2019 International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON)_ , 0391–0396. IEEE.
  * Pautov et al. (2022) Pautov, M.; Tursynbek, N.; Munkhoeva, M.; Muravev, N.; Petiushko, A.; and Oseledets, I. 2022.  CC-Cert: A probabilistic approach to certify general robustness of neural networks.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 36, 7975–7983.
  * Pei et al. (2017) Pei, K.; Cao, Y.; Yang, J.; and Jana, S. 2017.  Towards practical verification of machine learning: The case of computer vision systems.  _arXiv preprint arXiv:1712.01785_.
  * Pulina and Tacchella (2010) Pulina, L.; and Tacchella, A. 2010.  An abstraction-refinement approach to verification of artificial neural networks.  In _Computer Aided Verification: 22nd International Conference, CAV 2010, Edinburgh, UK, July 15-19, 2010. Proceedings 22_ , 243–257. Springer.
  * Russakovsky et al. (2015) Russakovsky, O.; Deng, J.; Su, H.; Krause, J.; Satheesh, S.; Ma, S.; Huang, Z.; Karpathy, A.; Khosla, A.; Bernstein, M.; Berg, A. C.; and Fei-Fei, L. 2015.  ImageNet Large Scale Visual Recognition Challenge.  _International Journal of Computer Vision (IJCV)_ , 115(3): 211–252.
  * Salman et al. (2019) Salman, H.; Li, J.; Razenshteyn, I.; Zhang, P.; Zhang, H.; Bubeck, S.; and Yang, G. 2019.  Provably robust deep learning via adversarially trained smoothed classifiers.  _Advances in Neural Information Processing Systems_ , 32.
  * Sharif et al. (2019) Sharif, M.; Bhagavatula, S.; Bauer, L.; and Reiter, M. K. 2019.  A general framework for adversarial examples with objectives.  _ACM Transactions on Privacy and Security (TOPS)_ , 22(3): 1–30.
  * Singh et al. (2019a) Singh, G.; Gehr, T.; Püschel, M.; and Vechev, M. 2019a.  An abstract domain for certifying neural networks.  _Proceedings of the ACM on Programming Languages_ , 3(POPL): 1–30.
  * Singh et al. (2019b) Singh, G.; Gehr, T.; Püschel, M.; and Vechev, M. 2019b.  Boosting robustness certification of neural networks.  In _International conference on learning representations_.
  * Singla and Feizi (2020) Singla, S.; and Feizi, S. 2020.  Second-order provable defenses against adversarial attacks.  In _International conference on machine learning_ , 8981–8991. PMLR.
  * Szegedy et al. (2013) Szegedy, C.; Zaremba, W.; Sutskever, I.; Bruna, J.; Erhan, D.; Goodfellow, I.; and Fergus, R. 2013.  Intriguing properties of neural networks.  _arXiv preprint arXiv:1312.6199_.
  * Tjeng, Xiao, and Tedrake (2017) Tjeng, V.; Xiao, K.; and Tedrake, R. 2017.  Evaluating robustness of neural networks with mixed integer programming.  _arXiv preprint arXiv:1711.07356_.
  * Tsai et al. (2022) Tsai, Y.-Y.; Hsiung, L.; Chen, P.-Y.; and Ho, T.-Y. 2022.  Towards compositional adversarial robustness: Generalizing adversarial training to composite semantic perturbations.  _arXiv preprint arXiv:2202.04235_.
  * Tsuzuku, Sato, and Sugiyama (2018) Tsuzuku, Y.; Sato, I.; and Sugiyama, M. 2018.  Lipschitz-margin training: Scalable certification of perturbation invariance for deep neural networks.  _Advances in neural information processing systems_ , 31.
  * Tu et al. (2021) Tu, J.; Li, H.; Yan, X.; Ren, M.; Chen, Y.; Liang, M.; Bitar, E.; Yumer, E.; and Urtasun, R. 2021.  Exploring adversarial robustness of multi-sensor perception systems in self driving.  _arXiv preprint arXiv:2101.06784_.
  * Tu et al. (2020) Tu, J.; Ren, M.; Manivasagam, S.; Liang, M.; Yang, B.; Du, R.; Cheng, F.; and Urtasun, R. 2020.  Physically realizable adversarial examples for lidar object detection.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 13716–13725.
  * Uesato et al. (2018) Uesato, J.; O’donoghue, B.; Kohli, P.; and Oord, A. 2018.  Adversarial risk and the dangers of evaluating against weak attacks.  In _International Conference on Machine Learning_ , 5025–5034. PMLR.
  * Wei and Kolter (2022) Wei, C.; and Kolter, J. Z. 2022.  Certified robustness for deep equilibrium models via interval bound propagation.  In _International Conference on Learning Representations_.
  * Weng et al. (2019) Weng, L.; Chen, P.-Y.; Nguyen, L.; Squillante, M.; Boopathy, A.; Oseledets, I.; and Daniel, L. 2019.  PROVEN: Verifying robustness of neural networks with a probabilistic approach.  In _International Conference on Machine Learning_ , 6727–6736. PMLR.
  * Weng et al. (2018) Weng, L.; Zhang, H.; Chen, H.; Song, Z.; Hsieh, C.-J.; Daniel, L.; Boning, D.; and Dhillon, I. 2018.  Towards fast computation of certified robustness for relu networks.  In _International Conference on Machine Learning_ , 5276–5285. PMLR.
  * Wicker et al. (2020) Wicker, M.; Laurenti, L.; Patane, A.; and Kwiatkowska, M. 2020.  Probabilistic safety for bayesian neural networks.  In _Conference on uncertainty in artificial intelligence_ , 1198–1207. PMLR.
  * Wong and Kolter (2018) Wong, E.; and Kolter, Z. 2018.  Provable defenses against adversarial examples via the convex outer adversarial polytope.  In _International Conference on Machine Learning_ , 5286–5295. PMLR.
  * Wong et al. (2018) Wong, E.; Schmidt, F.; Metzen, J. H.; and Kolter, J. Z. 2018.  Scaling provable adversarial defenses.  _Advances in Neural Information Processing Systems_ , 31.
  * Xu et al. (2020) Xu, H.; Ma, Y.; Liu, H.-C.; Deb, D.; Liu, H.; Tang, J.-L.; and Jain, A. K. 2020\.  Adversarial attacks and defenses in images, graphs and text: A review.  _International Journal of Automation and Computing_ , 17: 151–178.
  * Zhang et al. (2018) Zhang, H.; Weng, T.-W.; Chen, P.-Y.; Hsieh, C.-J.; and Daniel, L. 2018.  Efficient neural network robustness certification with general activation functions.  _Advances in neural information processing systems_ , 31.