$\displaystyle=\left(V\cdot\nu_{E}\right)_{\mathrm{int}}\,,\quad\text{$\operatorname{Per}_{E}$-a.e.\
on $F^{(1)}$}\,,$ (5.12b) $\displaystyle\left(V\cdot\nu_{E\cap
F}\right)_{\mathrm{int}}$
$\displaystyle=\left(V\cdot\nu_{F}\right)_{\mathrm{int}}\,,\quad\text{$\operatorname{Per}_{F}$-a.e.\
on $E^{(1)}$}\,,$ (5.12c) $\displaystyle\left(V\cdot\nu_{E\cap
F}\right)_{\mathrm{int}}$
$\displaystyle=\left(V\cdot\nu_{E}\right)_{\mathrm{int}}\,,\quad\text{$\mathscr{H}^{h}$-a.e.\
on $\\{\nu_{E}=\nu_{F}\\}$}\,.$ (5.12d)

Analogous conclusions hold for the exterior normal traces and for the interior
and exterior normal traces on $E\cup F$ and on $E\setminus F$.

###### Proof.

Let us begin by proving (5.12a). We perform a blow-up argument similar to the
one in the proof of subsection 4.2 and inspired by the proof of [Co20,
Proposition 3.4.6], dealing with the Euclidean case.

We claim that $\mathscr{H}^{h}$-a.e. $x\in E^{(1/2)}\cap F^{(1/2)}$ satisfies
the following:

  * (i)

$\begin{split}&\lim_{r\to
0}\fint_{B_{r}(x)}\left\lvert(V\cdot\nu_{E})_{{\mathrm{int}}}(y)-(V\cdot\nu_{E})_{{\mathrm{int}}}(x)\right\rvert\mathop{}\\!\mathrm{d}\operatorname{Per}_{E}(y)=0\,,\\\
&\lim_{r\to
0}\fint_{B_{r}(x)}\left\lvert(V\cdot\nu_{F})_{{\mathrm{int}}}(y)-(V\cdot\nu_{F})_{{\mathrm{int}}}(x)\right\rvert\mathop{}\\!\mathrm{d}\operatorname{Per}_{F}(y)=0\,;\end{split}$

  * (ii)

$\lim_{r\to 0}\frac{r|\operatorname{div}V|((E^{(1)}\cup F^{(1)})\cap
B_{r}(x))}{\mathfrak{m}(B_{r}(x))}=0.$

The property (i) amounts to say that $x$ is a Lebesgue point for both
$(V\cdot\nu_{E})_{{\mathrm{int}}}\in L^{\infty}(|D\chi_{E}|)$ and
$(V\cdot\nu_{F})_{{\mathrm{int}}}\in L^{\infty}(|D\chi_{F}|)$. The latter hold
for, respectively, $|D\chi_{E}|$ and $|D\chi_{F}|$ almost every point as
explained after subsection 2.5. The claimed conclusion follows by recalling
that $|D\chi_{E}|$ and $|D\chi_{F}|$ are equivalent to the measure
$\mathscr{H}^{h}$ restricted, respectively, to $E^{(1/2)}$ and $F^{(1/2)}$.

We now prove that $\mathscr{H}^{h}$-a.e. $x\in E^{(1/2)}\cap F^{(1/2)}$
satisfies (ii). Assume the existence of $B\subset E^{(1/2)}\cap F^{(1/2)}$
with positive $\mathscr{H}^{h}$-measure such that $x_{i}\in B$, $r_{i}<\delta$
and

$\limsup_{r\to 0}\frac{r|\operatorname{div}V|((E^{(1)}\cup F^{(1)})\cap
B_{r}(x))}{\mathfrak{m}(B_{r}(x))}\geq\varepsilon>0\,,\quad\text{for any $x\in
B$}\,.$

We can then find a cover $B\subset\cup_{i\in\mathbb{N}}B_{r_{i}}(x_{i})$ such
that

$0<\mathscr{H}^{h}(B)\leq
C(N)\sum_{i\in\mathbb{N}}\frac{\mathfrak{m}(B_{r_{i}}(x_{i}))}{r_{i}}\,,\quad\quad\frac{r_{i}|\operatorname{div}V|((E^{(1)}\cup
F^{(1)})\cap
B_{r_{i}}(x_{i}))}{\mathfrak{m}(B_{r_{i}}(x_{i}))}\geq\varepsilon/2\quad\forall\,i\in\mathbb{N}\,.$

In particular,

$|\operatorname{div}V|((E^{(1)}\cup F^{(1)})\cap\\{y\in
X\,:\,\mathsf{d}(x,y)\leq\delta\,\,\text{for some}\,\,x\in B\\})\geq
C(N,\varepsilon)\mathscr{H}^{h}(B)>0\,,$

letting $\delta\to 0$ we get the sought contradiction

$\displaystyle 0=$ $\displaystyle\,|\operatorname{div}V|((E^{(1)}\cup
F^{(1)})\cap(E^{(1/2)}\cap F^{(1/2)}))$ $\displaystyle\geq$
$\displaystyle\,|\operatorname{div}V|((E^{(1)}\cup F^{(1)})\cap B)\geq
C(N,\varepsilon)\mathscr{H}^{h}(B)>0\,.$

Let us pick a point $x\in E^{(1/2)}\cap F^{(1/2)}$ such that there exits a
system of good coordinates $(u_{i}):B_{r}(x)\to\mathbb{R}^{n}$ for both $E$
and $F$ such that $\nu_{E}(x)=\nu_{F}(x)$ and the properties (i) and (ii)
hold. Fix a function $\varphi\in C^{\infty}(\mathbb{R}^{n})$ compactly
supported in $B_{1}(0^{n})\subset\mathbb{R}^{n}$. Then, thanks to [AH18, Lemma
2.10] we find a sequence of uniformly bounded and uniformly Lipschitz
functions $\varphi_{m}:X\to\mathbb{R}$ compactly supported in $B_{r_{m}}(x)$
such that, when considered along the sequence of scaled spaces
$X_{m}:=(X,r_{m}^{-1}\mathsf{d},\mathfrak{m}_{m},x)$ with
$\mathfrak{m}_{m}=\mathfrak{m}/\mathfrak{m}(B_{r_{m}}(x))$, they converge
strongly in $H^{1,2}$ to $\varphi$ (see [AH17, Definition 5.2]).
Let $E_{m}$ and $F_{m}$ be $E,F\subset X_{m}$ and $u_{i}^{m}$ be the good
coordinates scaled by $u^{m}_{i}(y)=(u_{i}(y)-u_{i}(x))/r_{m}$. We can assume
that $u^{m}_{i}\to x_{i}$, the $i$-th coordinate of $\mathbb{R}^{n}$, in
$H^{1,2}$ and, as a consequence of subsection 4.2, $E_{m}\to H_{\nu_{E}(x)}$
and $F_{m}\to H_{\nu_{F}(x)}$ in $L^{1}_{\text{{\rm loc}}}$.

By Theorem 5.1 it holds

$\int_{E^{(1)}}\varphi_{m}\operatorname{div}V+\int_{E}\nabla\varphi_{m}\cdot
V\mathop{}\\!\mathrm{d}\mathfrak{m}=-\int_{\mathcal{F}E}\varphi_{m}\left(V\cdot\nu_{E}\right)_{\mathrm{int}}\mathop{}\\!\mathrm{d}\operatorname{Per}_{E}\,,$
(5.13)
$\int_{F^{(1)}}\varphi_{m}\operatorname{div}V+\int_{F}\nabla\varphi_{m}\cdot
V\mathop{}\\!\mathrm{d}\mathfrak{m}=-\int_{\mathcal{F}F}\varphi_{m}\left(V\cdot\nu_{F}\right)_{\mathrm{int}}\mathop{}\\!\mathrm{d}\operatorname{Per}_{F}\,.$
(5.14)

Fix $\varepsilon>0$ and observe that

$\left\lvert\int_{E^{(1)}}\varphi_{m}\operatorname{div}V-\int_{F^{(1)}}\varphi_{m}\operatorname{div}V\right\rvert\leq|\operatorname{div}V|((E^{(1)}\cup
F^{(1)})\cap
B_{r_{m}}(x))\leq\varepsilon\frac{\mathfrak{m}(B_{r_{m}}(x))}{r_{m}}\,,$
(5.15)

for $r_{m}$ small enough, as a consequence of (ii).

Recalling that $|\nabla\varphi_{m}|\leq C(N)r_{m}^{-1}$, we get

$\left\lvert\int_{E}\nabla\varphi_{m}\cdot
V\mathop{}\\!\mathrm{d}\mathfrak{m}-\int_{F}\nabla\varphi_{m}\cdot
V\mathop{}\\!\mathrm{d}\mathfrak{m}\right\rvert\leq C(N)\left\lVert
V\right\rVert_{L^{\infty}}\frac{\mathfrak{m}(E\Delta F\cap
B_{r_{m}}(x))}{r_{m}}\leq\varepsilon\frac{\mathfrak{m}(B_{r_{m}}(x))}{r_{m}}\,,$
(5.16)

for $r_{m}$ small enough, where in the last inequality we used subsection 4.2
and $\nu_{E}(x)=\nu_{F}(x)$ to infer that

$\lim_{m\to\infty}\frac{\mathfrak{m}(E\Delta F\cap
B_{r_{m}}(x))}{\mathfrak{m}(B_{r_{m}}(x))}=\lim_{m\to\infty}\mathfrak{m}_{m}(E_{m}\Delta
F_{m}\cap B_{1}^{m}(x))=\mathscr{L}^{n}(H_{\nu_{E}(x)}\Delta
H_{\nu_{F}(x)}\cap B_{1}(0^{n}))=0\,.$

Subtracting (5.13) and (5.14), taking into account (5.15) and (5.16) we deduce

$\limsup_{m\to\infty}\left\lvert\frac{r_{m}}{B_{r_{m}}(x)}\int_{\mathcal{F}E}\varphi_{m}\left(V\cdot\nu_{E}\right)_{\mathrm{int}}\mathop{}\\!\mathrm{d}\operatorname{Per}_{E}-\frac{r_{m}}{B_{r_{m}}(x)}\int_{\mathcal{F}F}\varphi_{m}\left(V\cdot\nu_{F}\right)_{\mathrm{int}}\mathop{}\\!\mathrm{d}\operatorname{Per}_{F}\right\rvert\leq
2\varepsilon\,.$ (5.17)

On the other hand, by (i),

$\displaystyle\,\limsup_{m\to\infty}\left\lvert\frac{r_{m}}{B_{r_{m}}(x)}\int_{\mathcal{F}E}\varphi_{m}\left(V\cdot\nu_{E}\right)_{\mathrm{int}}\mathop{}\\!\mathrm{d}\operatorname{Per}_{E}-\left(V\cdot\nu_{E}\right)_{\mathrm{int}}(x)\frac{r_{m}}{B_{r_{m}}(x)}\int_{\mathcal{F}E}\varphi_{m}\mathop{}\\!\mathrm{d}\operatorname{Per}_{E}\right\rvert$
$\displaystyle\quad\leq$
$\displaystyle\,\limsup_{m\to\infty}C(N)\frac{\mathfrak{m}(B_{r_{m}}(x))}{r_{m}\operatorname{Per}_{E}(B_{r_{m}}(x))}\fint_{B_{r_{m}}(x)}\left\lvert\left(V\cdot\nu_{E}\right)_{\mathrm{int}}(y)-\left(V\cdot\nu_{E}\right)_{\mathrm{int}}(x)\right\rvert\mathop{}\\!\mathrm{d}\operatorname{Per}_{E}(y)\,=\,0\,.$

Finally, observe that

$\lim_{m\to\infty}\frac{r_{m}}{B_{r_{m}}(x)}\int_{\mathcal{F}E}\varphi_{m}\mathop{}\\!\mathrm{d}\operatorname{Per}_{E}=\lim_{m\to\infty}\fint\varphi_{m}\mathop{}\\!\mathrm{d}\operatorname{Per}_{E_{m}}=\fint_{H_{\nu_{E}(x)}}\varphi\mathop{}\\!\mathrm{d}\mathscr{H}^{n-1}\,,$

which along with (5.17) and the identity $\nu_{E}(x)=\nu_{F}(x)$ allows to
conclude that

$\left\lvert\left(V\cdot\nu_{E}\right)_{\mathrm{int}}(x)-\left(V\cdot\nu_{F}\right)_{\mathrm{int}}(x)\right\rvert\fint_{H_{\nu_{E}(x)}}\varphi\mathop{}\\!\mathrm{d}\mathscr{H}^{n-1}\leq
2\varepsilon\,.$

Since $\varepsilon>0$ is arbitrary the proof of (5.12a) is complete.

Let us now pass to the proof of (5.12b) and (5.12c). To simplify our notation
we assume that $\chi_{E}$ and $\chi_{F}$ are pointwise defined as
$\chi_{E}:=\chi_{E^{(1)}}+\frac{1}{2}\chi_{E^{(1/2)}}$ and
$\chi_{F}:=\chi_{F^{(1)}}+\frac{1}{2}\chi_{F^{(1/2)}}$.

Thanks to [BCM19, Theorem 5.3] we know that
$V_{E}:=V\chi_{E}\in\mathcal{DM}^{\infty}(X)$, for any
$V\in\mathcal{DM}^{\infty}(X)$, hence as a consequence of [BCM19, Theorem
6.20] it holds

$\displaystyle\operatorname{div}(V\chi_{E\cap F})$
$\displaystyle=\operatorname{div}(V_{E}\chi_{F})=\chi_{F^{(1)}}\operatorname{div}(V\chi_{F})+(V_{E}\cdot\nu_{F})_{{\mathrm{int}}}|D\chi_{F}|\,,$
(5.18a) $\displaystyle\operatorname{div}(V\chi_{E})$
$\displaystyle=\chi_{E^{(1)}}\operatorname{div}V+(V\cdot\nu_{E})_{{\mathrm{int}}}|D\chi_{E}|\,.$
(5.18b)

In particular, applying again [BCM19, Theorem 6.20], we deduce that

$\begin{split}(V\cdot\nu_{E\cap F})_{{\mathrm{int}}}|D\chi_{E\cap
F}|&=\operatorname{div}(V\chi_{E\cap F})-\chi_{(E\cap
F)^{(1)}}\operatorname{div}V\\\
&=\chi_{F^{(1)}}(V\cdot\nu_{E})_{{\mathrm{int}}}|D\chi_{E}|+(V_{E}\cdot\nu_{F})_{{\mathrm{int}}}|D\chi_{F}|\,,\end{split}$

which restricted to $F^{(1)}$ implies (5.12b). Arguing symmetrically we get
(5.12c).

Let us finally prove (5.12d). Thanks to Theorem 4.1 we know that
$\\{\nu_{E\cap F}=\nu_{E}\\}=\\{\nu_{E}=\nu_{F}\\}$ up to a
$\mathscr{H}^{h}$-negligible set, hence (5.12d) follows from (5.12a) applied
to $E$ and $E\cap F$. ∎

##  6\. An example

In this last section we discuss a class of sets of finite perimeter and
essentially bounded divergence measure vector fields to which the theory
developed before can be applied: level sets of distance-type functions. In
particular, section 6 below applies to distance functions from closed sets,
sufficiently far away from the closed set itself, as it follows from the
Laplace comparison theorem, see [G15, CaM20]. Similar results have been
obtained for the distance from a given point in [APP21, Proposition 2.30].

The interest towards these examples comes from some recent applications, where
level sets of distance-type functions have been used to construct variations
of sets of finite perimeter solving variational problems: in [APP21]
variations via balls (that are sublevel sets of distances from points) have
been used in the study of the isoperimetric problem on
$\operatorname{RCD}(K,N)$ spaces, while in [MS21] section 6 is exploited to
prove Laplacian bounds for the distance function from the boundary of locally
perimeter minimizing sets of finite perimeter (corresponding to vanishing of
the mean curvature in the smooth framework) in the same setting.

######  Proposition .

Let $(X,\mathsf{d},\mathfrak{m})$ be an $\operatorname{RCD}(K,N)$ metric
measure space. Let $\Omega\Subset\Omega^{\prime}\subset X$ be open domains and
let $\varphi:\Omega^{\prime}\to\mathbb{R}$ be a $1$-Lipschitz function such
that

  * i)

$\left\lvert\nabla\varphi\right\rvert=1$ $\mathfrak{m}$-a.e. on
$\Omega^{\prime}$;

  * ii)

there exists $L\leq 0$ such that $\Delta\varphi\geq L$ in the sense of
distributions on $\Omega^{\prime}$. In particular, $\varphi$ has measure
valued Laplacian on $\Omega^{\prime}$.

Then, for $\mathscr{L}^{1}$-a.e. $t$ such that
$\\{\varphi=t\\}\cap\Omega\neq\emptyset$ it holds that $\\{\varphi<t\\}$ is a
set of locally finite perimeter in $\Omega$ and

$\left(\nabla\varphi\cdot\nu_{\\{\varphi<t\\}}\right)_{\mathrm{int}}=\left(\nabla\varphi\cdot\nu_{\\{\varphi<t\\}}\right)_{\mathrm{ext}}=-1\,\quad\operatorname{Per}_{\\{\varphi<t\\}}\text{-a.e.\
in $\Omega$}\,.$

###### Proof.

By the coarea formula $\\{\varphi<t\\}$ is a set of finite perimeter for
$\mathscr{L}^{1}$-a.e. $t$.

Since $\varphi$ has measure valued Laplacian on $\Omega^{\prime}$ and
$\left\lvert\nabla\varphi\right\rvert=1$ $\mathfrak{m}$-a.e., $\nabla\varphi$
is a bounded vector field with measure valued divergence on $\Omega^{\prime}$,
i.e. $\nabla\varphi\in\mathcal{DM}^{\infty}(\Omega^{\prime})$.
Moreover, for $\mathscr{L}^{1}$-a.e. $t$,
$\left\lvert\Delta\varphi\right\rvert(\\{\varphi=t\\})=\left\lvert\operatorname{div}\,\nabla\varphi\right\rvert(\\{\varphi=t\\})=0$.
For any such $t$, thanks to [BCM19, Theorem 6.20] we have that

$\left(\nabla\varphi\cdot\nu_{\\{\varphi<t\\}}\right)_{\mathrm{int}}=\left(\nabla\varphi\cdot\nu_{\\{\varphi<t\\}}\right)_{\mathrm{ext}}\,\quad\operatorname{Per}_{\\{\varphi<t\\}}\text{-a.e.}\,.$

Therefore it is sufficient to prove that

$\left(\nabla\varphi\cdot\nu_{\\{\varphi<t\\}}\right)_{\mathrm{int}}=-1\,\quad\operatorname{Per}_{\\{\varphi<t\\}}\text{-a.e.}\,.$
(6.1)

We claim that for $\mathscr{L}^{1}$-a.e. $t$ and for
$\operatorname{Per}_{\\{\varphi<t\\}}$-a.e. $x\in\\{\varphi=t\\}$ the
following hold:

  * i)

$x$ is a regular point of $(X,\mathsf{d},\mathfrak{m})$ i.e. the unique
tangent cone of $(X,\mathsf{d},\mathfrak{m})$ is $\mathbb{R}^{n}$, for some
$1\leq n\leq N$;

  * ii)

$x$ is a regular reduced boundary point of the set of finite perimeter
$\\{\varphi<t\\}$, i.e. any blow-up of $\\{\varphi<t\\}$ at $x$ in the sense
of sets of finite perimeter (see subsection 2.5) is a half-space in
$\mathbb{R}^{n}$;

  * iii)

$x$ is a regular point for $\varphi$, i.e. any blow-up of the function
$\varphi$ at $x$ is a linear function
$\varphi_{x}:\mathbb{R}^{n}\to\mathbb{R}$;

  * iv)

if $\mathbb{H}^{n}\subset\mathbb{R}^{n}$ is the blow-up of $\\{\varphi<t\\}$
at $x$, then $\varphi_{x}=\mathsf{d}^{\pm}_{\mathbb{H}^{n}}$ is the signed
distance function from $\mathbb{H}^{n}$.

We claim that the conditions (i)–(iv) are sufficient to prove that

$\lim_{r\downarrow
0}\frac{\left(\nabla\varphi\cdot\nu_{\\{\varphi<t\\}}\right)_{\mathrm{int}}\operatorname{Per}_{\\{\varphi<t\\}}(B_{r}(x))}{\operatorname{Per}(B_{r}(x))}=-1\,.$
(6.2)

This is the consequence of a blow-up argument, similar to the one in [BNS20,
Theorem 7.4]. By the Gauss-Green integration by parts formulae, the interior
normal trace is the density w.r.t. the perimeter measure of the divergence of
the vector field $\chi_{\\{\varphi<t\\}}\nabla\varphi$, which equals
$\Delta\left(\varphi-t\right)_{-}$, here $\left(\varphi-t\right)_{-}$ is the
negative part of $\varphi-t$. Under the assumptions (i) – (iv), after blow-up
the set of finite perimeter converges to a half-space, and the function
$\varphi$ converges to the signed distance from its boundary. In that limit
case it is easily verified that

$\left(\nabla\mathsf{d}^{\pm}_{\mathbb{H}^{n}}\cdot\nu_{\mathbb{H}^{n}}\right)_{\mathrm{int}}=-1\,,$

by direct computation.
Scaling and stability of the distributional Laplacian allow then to infer
(6.2).

Let us prove now that $\mathscr{L}^{1}$-a.e. $t$ and
$\operatorname{Per}_{\\{\varphi<t\\}}$-a.e. $x$ verify the properties (i) –
(iv). Since $\left\lvert\nabla\varphi\right\rvert=1$ $\mathfrak{m}$-a.e. on
$\Omega^{\prime}$, by the coarea formula Theorem 2.3 this is equivalent to ask
that (i) – (iv) are verified $\mathfrak{m}$-a.e. on $\Omega^{\prime}$.

The properties (i) and (ii) follow from the general theory of sets of finite
perimeter over $\operatorname{RCD}(K,N)$ spaces, since for any sublevel set
$\\{\varphi<t\\}$ which has finite perimeter it holds that
$\operatorname{Per}_{\\{\varphi<t\\}}$-a.e. $x$ is a regular reduced boundary
point, where all tangents are Euclidean half-spaces, see Theorem 2.4.

It remains to prove (iii) and (iv). In order to do so we first point out that
for $\mathfrak{m}$-a.e. point any blow-up $\varphi_{x}$ of $\varphi$ at $x$ is
a linear coordinate function on the tangent $\mathbb{R}^{n}$. The argument is
classical, and originally due to Cheeger [C99], so we avoid it. Observe that
the assumption that $\left\lvert\nabla\varphi\right\rvert=1$
$\mathfrak{m}$-a.e. on $\Omega^{\prime}$ here guarantees that the blow-up is a
linear function with slope equal to $1$. Indeed

$\fint_{B_{r}(x)}\left\lvert\nabla\varphi\right\rvert^{2}\mathop{}\\!\mathrm{d}\mathfrak{m}=1\,,\quad\text{for
any $0<r<\mathsf{d}(x,\partial\Omega)$}\,.$

Therefore, $\varphi_{x}:\mathbb{R}^{n}\to\mathbb{R}$, that is obtained as
limit of $\left(\varphi-\varphi(x)\right)/r_{i}$ along the sequence of scaled
spaces $(X,\mathsf{d}/r_{i},\mathfrak{m}_{x}^{r_{i}},x)$, is a harmonic
function such that

$\fint_{B^{\mathbb{R}^{n}}_{r}(0)}\left\lvert\nabla\varphi_{x}\right\rvert^{2}\mathop{}\\!\mathrm{d}\mathscr{H}^{n}=1\,,\quad\text{for
any $r>0$}\,,$

hence it is an affine coordinate with slope $1$. See also [AHPT21, Theorem
5.4] for a proof of the almost everywhere harmonicity of blow-ups of harmonic
functions more tailored to the setting of $\operatorname{RCD}(K,N)$ metric
measure spaces.

We are left to verify that the blow-up of $\varphi$, that is a coordinate
function, hence it is the signed distance function from a certain hyperplane,
is actually the signed distance function from the boundary of the blow-up of
the set of finite perimeter.
In order to do so, observe that $\left(\varphi-t\right)_{-}\leq 0$ and

$\int_{\\{\varphi>t\\}\cap
B_{r}(x)}\left(\varphi-t\right)_{-}\mathop{}\\!\mathrm{d}\mathfrak{m}=0\,,$

for any $x\in\\{\varphi=t\\}$.
This property is stable under blow-up of the set of finite perimeter and of
the function $\varphi$, by the $L^{1}_{{\rm loc}}$ convergence of the
indicator functions of the scaled sets of finite perimeter. Hence, also
$\left(\varphi_{x}\right)_{-}$ vanishes everywhere on the complement of the
blow up of $\\{\varphi<t\\}$ at $x$.
Since the blow-up of $\\{\varphi<t\\}$ at $x$ is a half-space and the blow-up
of $\varphi$ at $x$ is an affine coordinate function, the only possibility
compatible with the observation above is that $\varphi$ blows-up to the signed
distance function from the boundary of the blow-up to $\\{\varphi<t\\}$ at
$x$, as we claimed.

To conclude, observe that by (6.2) the density of the interior normal trace of
$\nabla\varphi$ on the boundary of $\\{\varphi<t\\}$ at $x$ is $-1$ for
$\operatorname{Per}_{\\{\varphi<t\\}}$-a.e. $x$. This is sufficient to prove
(6.1) by the Lebesgue differentiation theorem, since the perimeter measure is
asymptotically doubling, see subsection 2.5. ∎

## References

  * [A01] L. Ambrosio: Some fine properties of sets of finite perimeter in Ahlfors regular metric measure spaces, Adv. Math., 159 (2001), 51–67.
  * [A02] L. Ambrosio: Fine properties of sets of finite perimeter in doubling metric measure spaces, Set-Valued Anal., 10 (2002), 111–128.
  * [ABS19] L. Ambrosio, E. Brué, D. Semola: Rigidity of the 1-Bakry-Émery inequality and sets of finite perimeter in $\operatorname{RCD}$ spaces. Geom. Funct. Anal., 19 (2019), n.4, 949-1001.
  * [ADM14] L. Ambrosio, S. Di Marino: Equivalent definitions of $\operatorname{BV}$ space and of total variation on metric measure spaces. J. Funct. Anal. 266 (2014), no. 7, 4150–4188.
  * [AGSa13] L. Ambrosio, N. Gigli, G. Savaré: Density of Lipschitz functions and equivalence of weak gradients in metric measure spaces. Rev. Mat. Iberoam. 29 (2013), no. 3, 969–996.
  * [AGSa14a] L. Ambrosio, N. Gigli, G. Savaré: Calculus and heat flow in metric measure spaces and applications to spaces with Ricci bounds from below. Invent. Math. 195 (2014), no. 2, 289–391.
  * [AGSa14b] L. Ambrosio, N. Gigli, G. Savaré: Metric measure spaces with Riemannian Ricci curvature bounded from below. Duke Math. J. 163 (2014), no. 7, 1405–1490.
  * [AH17] L. Ambrosio, S. Honda: New stability results for sequences of metric measure spaces with uniform Ricci bounds from below. Measure theory in non-smooth spaces, 1–51, Partial Differ. Equ. Meas. Theory, De Gruyter Open, Warsaw, 2017.
  * [AH18] L. Ambrosio, S. Honda: Local spectral convergence in $\operatorname{RCD}^{*}(K,N)$ spaces. Nonlinear Anal. 177 (2018), part A, 1–23.
  * [AHPT21] L. Ambrosio, S. Honda,J. Portegies, D. Tewodrose: Embedding of $\operatorname{RCD}^{*}(K,N)$ metric measure spaces in $L^{2}$ via eigenfunctions, J. Funct. Anal. 280 (2021), no. 10, 108968.
  * [ABFP21] G. Antonelli, E. Brué, M. Fogagnolo, M. Pozzetta: On the existence of isoperimetric regions in manifolds with nonnegative Ricci curvature and Euclidean volume growth, preprint arXiv:2107.07318.
  * [AnBS19] G. Antonelli, E. Brué, D. Semola: Volume bounds for the quantitative singular strata of non collapsed $\operatorname{RCD}$ metric measure spaces, Anal. Geom. Metr. Spaces, 7 2019, no. 1.
  * [AFP21] G. Antonelli, M. Fogagnolo, M. Pozzetta: The isoperimetric problems on Riemannian manifolds via Gromov-Hausdorff asymptotic analysis, preprint arXiv:2101.12711.
  * [APP21] G. Antonelli, E. Pasqualetto, M. Pozzetta: Isoperimetric sets in spaces with lower bounds on the Ricci curvature, preprint arXiv:2107.03124.
  * [An83] G. Anzellotti: Pairings between measures and bounded functions and compensated compactness, Ann. Mat. Pura Appl. (4) 135 (1983), 293–318.
  * [Br21] M. Braun: Vector calculus for tamed Dirichlet spaces, preprint arXiv:2108.12374.
  * [BNS20] E. Brué, A. Naber, D. Semola: Boundary regularity and stability for spaces with lower Ricci curvature bounds, preprint arXiv:2011.08383.
  * [BPS19] E. Brué, E. Pasqualetto, D. Semola: Rectifiability of the reduced boundary for sets of finite perimeter over $\operatorname{RCD}(K,N)$ spaces, Preprint arXiv:1909.00381.
  * [BPS20] E. Brué, E. Pasqualetto, D. Semola: Rectifiability of $\operatorname{RCD}(K,N)$ spaces via $\delta$-splitting maps, Annales Fennici Mathematici. 46, (2021), no. 1, 465–482.
  * [BS20] E. Brué, D. Semola: Constancy of the dimension for $\operatorname{RCD}(K,N)$ spaces via regularity of Lagrangian flows. Comm. Pure Appl. Math. 73 (2020), no. 6, 1141–1204.
  * [BCM19] V. Buffa, G. Comi, M. Miranda: On $\operatorname{BV}$ functions and essentially bounded divergence measure fields in metric spaces, to appear on Rev. Mat. Ibero. Preprint arXiv:1906.07432.
  * [BB11] A. Björn, J. Björn: Nonlinear potential theory on metric spaces. EMS Tracts in Mathematics, 17. European Mathematical Society (EMS), Zürich, 2011. xii+403 pp.
  * [CaM20] F. Cavalletti, A. Mondino: New formulas for the Laplacian of distance functions and applications. Anal. PDE 13 (2020), no. 7, 2091–2147.
  * [C99] J. Cheeger: Differentiability of Lipschitz functions on metric measure spaces. Geom. Funct. Anal., 9 (1999), 428–517.
  * [CJN21] J. Cheeger, W. Jiang, A. Naber: Rectifiability of singular sets of noncollapsed limit spaces with Ricci curvature bounded below. Ann. of Math. (2) 193 (2021), no. 2, 407–538.
  * [CTZ09] G.-Q. Chen, M. Torres and W. P. Ziemer: Gauss–Green theorem for weakly differentiable vector fields, sets of finite perimeter, and balance laws, Comm. Pure Appl. Math. 62 (2009), no. 2, 242–304.
  * [CN12] T.-H. Colding, A. Naber: Sharp Hölder continuity of tangent cones for spaces with a lower Ricci curvature bound and applications. Ann. of Math. (2) 176 (2012), no. 2, 1173–1229.
  * [Co20] G. Comi: Refined Gauss Green formulas and evolution problems for Radon measures, PhD thesis, available at https://cvgmt.sns.it/paper/4579/.
  * [CP20] G.-E. Comi, K.-R. Payne: On locally essentially bounded divergence measure fields and sets of locally finite perimeter. Adv. Calc. Var. 13 (2020), no. 2, 179–217.
  * [DGP21] C. Debin, N. Gigli, E. Pasqualetto: Quasi-continuous vector fields on $\operatorname{RCD}$ spaces. Potential Anal. 54 (2021), no. 1, 183–211.
  * [DG54] E. De Giorgi: Su una teoria generale della misura $(r-1)$-dimensionale in uno spazio ad $r$ dimensioni. Ann. Mat. Pura Appl. (4) 36 (1954), 191–213.
  * [DG55] E. De Giorgi: Nuovi teoremi relativi alle misure $(r-1)$-dimensionali in uno spazio ad $r$ dimensioni. Ricerche Mat. 4 (1955), 95–113.
  * [D20] Q. Deng Hölder continuity of tangent cones in $\operatorname{RCD}(K,N)$ spaces and applications to non-branching, preprint arXiv:2009.07956.
  * [D94] D. Denneberg: Non-additive measure and integral. Theory and Decision Library. Series B: Mathematical and Statistical Methods, 27. Kluwer Academic Publishers Group, Dordrecht, 1994. x+178 pp.
  * [DPMR17] G. De Philippis, A. Marchese, F. Rindler: On a conjecture of Cheeger, Measure theory in non-smooth spaces, 145–155, Partial Differ. Equ. Meas. Theory, De Gruyter Open, Warsaw, 2017.
  * [G13] N. Gigli: The splitting theorem in non-smooth context, preprint arXiv:1302.5555.
  * [G15] N. Gigli: On the differential structure of metric measure spaces and applications. Mem. Amer. Math. Soc. 236 (2015), no. 1113, vi+91 pp.
  * [G18] N. Gigli: Nonsmooth differential geometry—an approach tailored for spaces with Ricci curvature bounded from below. Mem. Amer. Math. Soc. 251 (2018), no. 1196, v+161 pp.
  * [GMSa15] N. Gigli, A. Mondino, G. Savaré: Convergence of pointed non-compact metric measure spaces and stability of Ricci curvature bounds and heat flows. Proc. Lond. Math. Soc. (3) 111 (2015), no. 5, 1071–1129.
  * [GP16a] N. Gigli, E. Pasqualetto: Behaviour of the reference measure on $\operatorname{RCD}$ spaces under charts: preprint arXiv:1607.05188, to appear on Comm. Anal. Geom.
  * [GP16] N. Gigli, E. Pasqualetto Equivalence of two different notions of tangent bundle on rectifiable metric measure spaces Preprint arXiv:1611.09645, to appear on Comm. Anal. Geom.
  * [J12] R. Jiang: Lipschitz continuity of solutions of Poisson equations in metric measure spaces. Potential Anal. 37 (2012), no. 3, 281–301.
  * [KM18] M. Kell, A. Mondino: On the volume measure of non-smooth spaces with Ricci curvature bounded below. Ann. Sc. Norm. Super. Pisa Cl. Sci. (5) 18 (2018), no. 2, 593–610.
  * [KL02] J. Kinnunen, V. Latvala: Lebesgue points for Sobolev functions on metric spaces. Rev. Mat. Iberoamericana 18 (2002), no. 3, 685–700.
  * [KM02] J. Kinnunen, O. Martio: Nonlinear potential theory on metric spaces. Illinois J. Math. 46 (2002), no. 3, 857–883.
  * [Ki19] Y. Kitabeppu: A sufficient condition to a regular set being of positive measure on $\operatorname{RCD}$ spaces. Potential Anal. 51 (2019), no. 2, 179–196.
  * [Ma12] F. Maggi: Sets of finite perimeter and geometric variational problems. An introduction to geometric measure theory. Cambridge Studies in Advanced Mathematics, 135. Cambridge University Press, Cambridge, 2012. xx+454 pp.
  * [Mi03] M. Miranda Jr.: Functions of bounded variation on "good" metric spaces, J. Math. Pures Appl. (9) 82 (2003) 975–1004.
  * [MN19] A. Mondino, A. Naber: Structure theory of metric measure spaces with lower Ricci curvature bounds. J. Eur. Math. Soc. (JEMS) 21 (2019), no. 6, 1809–1854.
  * [MS21] A. Mondino, D. Semola: Weak Laplacian bounds and minimal boundaries in non-smooth spaces with Ricci curvature lower bounds, preprint arXiv:2107.12344.
  * [NPS21] F. Nobili, E. Pasqualetto, T. Schultz: On master test plans for the space of BV functions, preprint, arXiv:2109.04980.
  * [Sa14] G. Savaré: Self-improvement of the Bakry-Émery condition and Wasserstein contraction of the heat flow in $\operatorname{RCD}(K,\infty)$ metric measure spaces. Discrete Contin. Dyn. Syst. 34 (2014), no. 4, 1641–1661.
  * [S20] D. Semola: Recent developments about Geometric Analysis on $\operatorname{RCD}(K,N)$ spaces, PhD thesis, Scuola Normale Superiore (2020), available at https://cvgmt.sns.it/paper/4820/.
  * [W00] N. Weaver: Lipschitz algebras and derivations. II. Exterior differentiation. J. Funct. Anal. 178 (2000), no. 1, 64–112.


# Pruning vs Quantization: Which is Better?

Andrey Kuzmin, Markus Nagel, Mart van Baalen, Arash Behboodi, Tijmen
Blankevoort
Qualcomm AI Research
Amsterdam, The Netherlands
{akuzmin, markusn, mart, behboodi<EMAIL_ADDRESS>Qualcomm AI
Research is an initiative of Qualcomm Technologies, Inc.

###### Abstract

Neural network pruning and quantization techniques are almost as old as neural
networks themselves. However, to date only ad-hoc comparisons between the two
have been published. In this paper, we set out to answer the question on which
is better: neural network quantization or pruning? By answering this question,
we hope to inform design decisions made on neural network hardware going
forward. We provide an extensive comparison between the two techniques for
compressing deep neural networks. First, we give an analytical comparison of
expected quantization and pruning error for general data distributions. Then,
we provide lower bounds for the per-layer pruning and quantization error in
trained networks, and compare these to empirical error after optimization.
Finally, we provide an extensive experimental comparison for training 9 large-
scale models on 4 tasks. Our results show that in most cases quantization
outperforms pruning. Only in some scenarios with very high compression ratio,
pruning might be beneficial from an accuracy standpoint. 111Code is available
at https://github.com/Qualcomm-AI-research/pruning-vs-quantization

##  1 Introduction

Recent advances in deep learning led to exceeding human-level performance in
many tasks, including computer vision, machine translation, voice recognition,
and language understanding. Real-world applications of DNNs rely heavily on
their efficiency. Both mobile and cloud platforms greatly benefit from reduced
latency and energy efficiency achieved by some form of model compression. In
this work, we consider two mainstream techniques used in practice; pruning and
quantization.

Pruning methods remove individual weights [70, 25], or sometimes groups of
weights [28, 47]. This procedure can reduce the memory footprint. Furthermore,
not having to perform the computations with weights that are zeroed out can
make network inference more efficient. On the other hand, quantization reduces
the bit-width used for both the weights and the computation used in networks,
leading to both predictable memory savings and reductions in the necessary
compute. In both scenarios, the hardware used for making use of these
optimization schemes needs to take them into account.

Depending on the availability of training data and computing budget, most
methods for pruning and quantization fall into one of two families. The first
family includes fine-tuning approaches, namely quantization-aware training
(QAT) and fine-tuning with pruning in the loop. The second family includes
post-training approaches such as post-training quantization (PTQ). Previously,
pruning techniques primarily relied on fine-tuning; however, some post-
training pruning methods appeared recently as fine-tuning is not desirable for
large language models [18].

Despite the importance of model efficiency and the plethora of approaches for
pruning and quantization, the two fields are mostly disjoint. The literature
presents little insight into which of the two techniques is more accurate. In
practice, there is only limited time to compress a network and limited energy
to spend on making deep learning inference hardware. For this reason, we ask
the question: Should one focus on quantization or pruning for compression?

We present an extensive study comparing pruning and quantization in equal
settings. First, we consider different data distributions and analyze the
conditions under which each method is preferable. We match our findings with
real weight tensors from pre-trained models. Second, we consider a post-
training scenario and evaluate single-layer output errors for both methods.
Because the comparison might depend on the specific choice of optimization
method, we compare the two with theoretical bounds that apply regardless of
the optimization method. Finally, we provide a full-model comparison for the
most common scenario of fine-tuning networks after either pruning or
quantization.

In our comparison, we intentionally avoid considering the hardware aspects of
pruning and quantization. Instead, we focus solely on the accuracy of both
methods, given similar theoretical compression ratios. A coarse discussion on
the hardware necessary for both methods can be found in section 6.

##  2 Assumptions

In our work, we assume FP16 as the basic data type and measure any gains in
compression with respect to it. Using FP16 for inference generally does not
lead to a loss in accuracy. Neural networks are also very commonly trained
with FP16, making it a common baseline. Thus, we compare 50% pruning sparsity
to INT8 quantization, 75% sparsity to INT4 quantization and so forth. We also
assume no overhead on storing the sparsity mask for pruning and relegate such
hardware-specific implementations to section 6.

For the pruning experiments, we consider magnitude pruning. It is common to do
fine-tuning after or during pruning [70]. Several works have independently
shown that despite its simplicity, it is tough to improve upon magnitude
pruning and fine-tuning [19, 4]. To our knowledge, no pruning algorithm exists
that consistently outperforms this method.

For the quantization experiments, we use symmetric uniform quantization, which
is defined by just the quantization scale factor and the bit-width. The scale
is represented as a floating-point number and is used to map floating-point
values to the integer grid. Further details on symmetric uniform quantization
can be found in [49]. Uniform quantization is the standard in the quantization
literature, and symmetric quantization is mostly employed for the weights. In
all our experiments, we use a quantization range estimator minimizing the
mean-squared error on weights by grid search [49].

##  3 Comparison on statistical distributions

---
Figure 1: Comparison for a standard normal distribution. (left) Distributions
after pruning and quantization for INT4 and 75% pruning. (middle) The squared
error weighted by probability. (right) SNR for different compression ratios.

Before diving into comparison results, we first describe theoretically what
the quantization error and pruning error are. Looking at this with a
theoretical lens helps with understanding the later experimental difference
between the two methods. We start off by describing and analyzing both methods
on simple data distributions.

In order to compare the error of pruning and quantization, we will frequently
use the signal-to-noise ratio measure defined in the log scale:
$\text{SNR}_{dB}=10\log_{10}\left(\mathbb{E}\left[W^{2}\right]/\mathbb{E}\left[(W-F(W))^{2}\right]\right)$,
where $F(W)$ is the quantization or pruning function. This measure is the same
as a scaled logarithm of an MSE measure. Both are often employed to analyze
the sensitivity of neural network layers to quantization, and they are
theoretically well-founded to correlate with network performance [41, 48].

###  3.1 Quantization error

For quantization, we consider symmetric uniform quantization, which is also
called integer quantization. Given a bit-width $b$ and the scale $\delta$, the
grid nodes are defined as $q_{i}=\delta i,i\in\\{-2^{b},\dots,0,2^{b}-1\\}$.
The quantization operation rounding-to-nearest $Q(w)$ and the corresponding
quantization error $R(w)$ are defined as:

$\displaystyle Q(w)=q_{i},\text{ }i=\operatorname*{arg\,min}_{i}|w-q_{i}|,$
$\displaystyle R(w)=Q(w)-w.$ (1)

---
Figure 2: Comparing the error of pruning and quantization for a student-t
distribution, simulating the presence of significant outliers. We plot the
results for different magnitudes of the outliers, as per the kurtosis on the
x-axis. (left) the pruning error, which does not change under the presence of
more severe outliers. (middle) the quantization SNR, which is reduced greatly
when outliers increase (right) the trade-off regions where quantization and
pruning are better.

Following [36] we model neural network weights as a random variable $W\sim
p(w)$. The expected value of the quantization MSE can be expressed as follows:

$\begin{split}{\mathbb{E}}\left[\left(Q(W)-W)^{2}\right)\right]=\int\limits_{q_{min}}^{q_{max}}R^{2}(w)p(w)dw+\int\limits_{-\infty}^{q_{min}}(w-q_{min})^{2}p(w)dw+\int\limits_{q_{max}}^{\infty}(q_{max}-w)^{2}p(w)dw,\end{split}$
(2)

where $q_{min}=\min_{i}{q_{i}}$ and $q_{max}=\max_{i}{q_{i}}$ are the
quantization range limits. The left term corresponds to the rounding error,
and the right two terms correspond to the clipping error. We use this analytic
formulation for our distribution results below, the details are given in
appendix A.

###  3.2 Pruning error

We consider magnitude pruning $T(x)=x\cdot\mathds{1}_{-t\leq x\leq t}$. This
simply sets the values closest to zero to actual zero. Given this, the
expected error of pruning is expressed as follows:

$\begin{split}{\mathbb{E}}\left[T(W)^{2}\right]=\int\limits_{-t}^{t}w^{2}p(w)dw,\end{split}$
(3)

where $t$ is the threshold value that controls how much is pruned. Given the
compression ratio $c\in(0,1)$, we find the threshold value which satisfies
$P(-t\leq W\leq t)=c$. In case of a symmetric zero-mean distribution, the
threshold can be expressed as
$t=F_{W}^{-1}\left(\frac{1}{2}+\frac{c}{2}\right)$, where $F(w)=P(W\leq w)$ is
the CDF function and $F^{-1}(p)$ is its inverse. The expected pruning error in
equation 3 is similar to the clipping error for quantization (see the second
and the third term in equation 2), and can also be computed analytically. We
also use this formulation for our results below.

###  3.3 Analytical comparison

Standard normal distribution. Let us first look at a standard normal
distribution. As many weights in neural networks are roughly Gaussian-shaped,
this distribution is useful for our understanding of the comparison. As we can
see from figure 1 (middle), the errors for both methods have very different
behavior. The quantization error oscillates between the quantization nodes and
has a moderate range. The pruning error effectively corresponds to rounding
many weights to zero and thus has a higher error. As we can see in figure 1
(right), this results in a higher SNR for quantization, e.g. 19.1 dB for INT4
quantization versus only 5.6 dB for 75% pruning. We see similar results for
different compression ratios. For this distribution, quantization achieves a
much higher signal-to-noise ratio.

---
Figure 3: (left) Comparison on all the weights from PyTorch model zoo (46
models) combined with 3 large language models (Bloom-3b, Llama-3b, OPT-2.7b).
(left) Pruning SNR versus quantization SNR for every tensor. (right) Pruning
is preferable at high compression ratios for tensors with high sample kurtosis
values.

Distributions with heavy tails. The trade-off is expected to change when more
significant outliers are introduced. The quantization grid is expected to be
effected strongly by outliers as it increases the quantization grid in size,
whereas the pruning method is expected to be hardly effected with outliers as
it only affects weights around zero. We thus analyze both quantization and
pruning errors in the presence of many outliers. To simulate a distribution
with outliers, we use a truncated Student’s-t distribution with $\nu=2$, and a
symmetric range $(-r,r)$ (the PDF is defined in appendix B). This distribution
is nice as it gives a non-trivial weight to the tail ends of the distribution
close to $r$. The wider the range $r$ is, the heavier are the tails of the
distribution.

In order to introduce a quantitative measure of the number of outliers, we
will use the distribution’s kurtosis given by
$\text{Kurt}[X]={\mathbb{E}}\left[\left(X-\mu\right)^{4}\right]/\left({\mathbb{E}}\left[\left(X-\mu\right)^{2}\right]\right)^{2}$,
where $\mu$ is the mean. We will see later that this kurtosis measure is
predictive of quantiation and pruning performance for real layers. To increase
the number of outliers, we will increase the range $r$. The results are given
in figure 2. The kurtosis range is chosen so that it includes most of the
weights from the model zoo. We see that despite the significant outliers and
high kurtosis, quantization still has higher SNR in most of the cases for
moderate compression. Pruning is better however in the region of high clipping
range and very high compression rate, e.g. 2-3 bits per value (see figure 2 on
the right).

###  3.4 Experiments on real weight tensors

The previous discussion was mostly theoretical. We set out to see happens when
we do a similar analysis on real neural network weights. In order to
investigate this, we compare the pruning and quantization SNR on the weight
tensors for all the pre-trained models from the PyTorch model zoo111
https://pytorch.org/serve/model_zoo.html. (46 models in total, the details are
give in appendix E) combined with weight tensors from 3 large language models,
namely Bloom-3b [3], Llama-3b [20], OPT-2.7b [67]. Each tensor is quantized
using an integer grid of bit widths from 2 to 8. The results are shown in the
figure 3(left). We see a similar trend to our previous discussion that pruning
becomes more beneficial for lower bitwidth/higher sparsity ratios.

In order to match the analytical results from figure 2, we consider the sample
kurtosis of every weight tensor given by
$k=\frac{1}{n}\sum_{i=1}^{n}(x_{i}-\overline{x})^{4}/\left[\frac{1}{n}\sum_{i=1}^{n}(x_{i}-\overline{x})^{2}\right]^{2}$.
See figure 3 (right). We consider a range of kurtosis values for every
quantization bit-width. Using a kernel density estimator, we compute the
probability density of encountering a tensor for which pruning has higher SNR
than quantization SNR. We compare the PDF to that for quantization and thus
determine the region where each method is preferable. The results are given in
figure 3 on the right. We see that the results from the previous theoretical
section (figure 2 on the right) hold very nicely. We can also see that as
predicted, the kurtosis is indeed a good metric for predicting if a tensor
should be quantized or pruned for optimal accuracy.

##  4 Per-layer comparison

Most PTQ methods compress the model layer by layer. Given one layer, we use
the mean-squared error of the output activations as an objective for
optimization. As [48] shows, minimizing per layer MSE on the output
activations of each layer is a computationally affordable second-order
approximation of the loss function. The local MSE objective correlates well
with the task loss and is often used in practice in DNN compression and
quantization literature [32, 40, 68]. Our experiments in appendix D confirm
this. For the experiments in this section, we will use SNR as it represents a
normalized version of MSE. As opposed to section 3 where we used SNR on
weights, in this section, we will use SNR on the output activations instead.

The goal of a PTQ method is to minimize the error in the output activations of
the compressed layer by optimizing over the quantized weights subject to
integer range constraints. Similarly, for pruning, the weights are optimized
subject to a sparsity constraint. As the underlying combinatorial optimization
problem for both methods is NP-hard [56, 14], in practice, each method relies
on some form of heuristic providing a reasonably good solution given a
realistic compute budget. This means that any practical comparison between
pruning and quantization would depend on the choice of the method for both and
would be open to debate of the optimality of the algorithm. In order to
eliminate this dependence, we provide a tight lower bound on the output errors
for quantization. For pruning we provide a way to solve the problem exactly
for moderate dimensionalities. This way, we can provide a comparison that
holds regardless of the algorithm used for each method.

###  4.1 Post-training quantization

We set out to formulate a way by which we can get relatively tight bounds for
comparison when quantizing a single layer with the MSE as the objective. The
higher bound is simple to obtain by using a solution with a heuristic
quantization algorithm, but for the lower bound, we have to reformulate the
problem. The mean-squared error of the output activations of a quantized layer
can be expressed as:

$\displaystyle\min_{\mathbold{w}}E(\mathbold{w})$
$\displaystyle\left\lVert\mathbold{X}\delta\mathbold{w}-\mathbold{X}\mathbold{w}_{orig}\right\rVert_{2}^{2}$
(4) s.t. $\displaystyle\mathbold{w}\in\mathbb{Z}^{n},$ $\displaystyle
w_{min}\leq w_{i}\leq w_{max},$

where $X$ is the input data in an unfolded form, and $w_{orig}$ are the
floating point weights. The quantized weights are computed as the product of
the quantization scale $\delta$, and the integer weights $\mathbold{w}$.
$w_{min}$ and $w_{max}$ are the integer limits. We ignore the averaging
operation to simplify the notation, as it is not important for optimization.
We also note that this problem can be solved independently for each output
channel of a convolution or every row of a fully-connected layer weight.

This problem is an instance of a mixed-integer quadratic program:

$\displaystyle\tilde{E}(\mathbold{w})=$
$\displaystyle\frac{1}{2}\mathbold{w}^{T}\mathbold{P}\mathbold{w}-\mathbold{q}^{T}\mathbold{w},$
(5) s.t. $\displaystyle\mathbold{w}\in\mathbb{Z}^{n},$ $\displaystyle
w_{min}\leq w_{i}\leq w_{max},$

where $\mathbold{P}=2\delta^{2}\mathbold{X}^{T}\mathbold{X}$,
$\mathbold{q}=2(\mathbold{w}_{orig}^{T}\mathbold{X}^{T})\mathbold{X}\delta$.
In order to simplify the objective, we can omit the constant term that is
irrelevant for the optimization
$c=\left\lVert\mathbold{X}\mathbold{w}_{orig}\right\rVert_{2}^{2}$, i.e.
$\tilde{E}(\mathbold{W})=E(\mathbold{W})-c$.

In order to find the lower bound of the objective, we follow [55] and relax
the integer constraint to $w_{i}(w_{i}-1)\geq 0$, which allows the weight to
take values within the interval from 0 to 1. In order to obtain the lower
bound, we will consider the dual version of the relaxed problem:

$\displaystyle L(\mathbold{\lambda})=$ $\displaystyle\max-\gamma,$ (6) s.t.
$\displaystyle\begin{bmatrix}\mathbold{P}-\mathbf{diag}(\mathbold{\lambda})&q+\frac{1}{2}\lambda\\\
\left(q+\frac{1}{2}\lambda\right)^{T}&\gamma\end{bmatrix}\succeq 0,$
$\displaystyle\mathbold{\lambda}\geq 0,$

where $\mathbold{\lambda}\in\mathbb{R}^{n}$, $\gamma\in\mathbb{R}$. The dual
problem is convex, and its solution can be used as a lower bound on the
solution of the original problem, i.e., $\tilde{E}(\mathbold{w})\geq
L(\mathbold{\lambda})$. The dual has a semi-definite constraint which can be
solved with a semi-definite programming (SDP) solver with $\mathcal{O}(n^{3})$
complexity. In our work, we used CVX solver [21]. As discussed in [55], this
bound is a computationally efficient alternative to branch-and-bound
approaches, while tightness is better than that for the alternative methods
introduced in [5]. We use this approach for estimating the lower bound for MSE
on the output activations for PTQ below.

###  4.2 Post-training pruning

We also need a similar lower bound for pruning for comparison. To the best of
our knowledge we are not aware of the ways to provide a tight lower bound for
this problem, therefore we formulate a way to solve a problem for moderate
dimensionalities exactly. Similar to quantization, post-training pruning of
one layer of the network can mathematically be expressed as solving the
following optimization problem:

$\displaystyle E$
$\displaystyle=\min_{\mathbold{\hat{w}}}\left\lVert\mathbold{X}\hat{\mathbold{w}}-\mathbold{X}\mathbold{w}_{orig}\right\rVert_{2}^{2}$
(7) s.t. $\displaystyle\left\lVert\hat{\mathbold{w}}\right\rVert_{0}\leq s,$

where the number of non-zero elements $s$ in the solution is theoretically
constrained by using the $L_{0}$ norm, which is non-convex and not smooth. In
order to solve the problem, we introduce the sparsity mask
$m\in\mathbb{R}^{n}$:

$\displaystyle E(\mathbold{w})=$
$\displaystyle\min_{\mathbold{w},\mathbold{m}}\left\lVert\mathbold{X}(\mathbold{m}\odot\mathbold{w})-\mathbold{X}\mathbold{w}_{orig}\right\rVert_{2}^{2},$
(8) s.t. $\displaystyle\left\lVert\mathbold{m}\right\rVert_{1}=s,$
$\displaystyle-\mathbold{m}\odot l\leq\mathbold{\hat{w}}\leq\mathbold{m}\odot
u$ $\displaystyle l,u>0,m_{i}\in\\{0,1\\},$

where $\odot$ is an element-wise product operation, and $l,u\in\mathbb{R}$ are
constants chosen such that any solution satisfies the constraint
$-\mathbold{m}\odot l\leq\mathbold{\hat{w}}\leq\mathbold{m}\odot u$. We solve
this problem using the branch-and-bound method implemented in the Gurobi
solver [23] that gives the global solution.

###  4.3 Experiments

With our algorithms in the bag, we can now compare quantization versus pruning
in the post-training settings with theoretical bounds. In each case, we
analyze individual layers of several networks. Given a batch of input data, we
optimize the pruned or quantized weights to minimize the error between the
output activations and the output of the uncompressed layer. We provide a
range between two SNR values for each method in each case. The performance of
the heuristic method gives the first value, and the second value is given by
the error lower bound or the global solution, which translates into SNR upper
bound.

As a heuristic method for pruning, we use magnitude pruning with a fixed
sparsity mask $m$ and data-optimized weights $\mathbold{w}$ given by
$\mathbold{w}=\underset{\rm\mathbold{w}}{\rm\text{argmin}}\left\lVert\mathbold{X}(\mathbold{m}\odot\mathbold{w})-\mathbold{X}\mathbold{w}_{orig}\right\rVert_{2}^{2}$.
This is a convex problem and has a unique solution. As a heuristic method for
quantization, we use the mixed-integer solver introduced in [55]. We clip
every sample in order to satisfy the integer quantization range constraint.

We chose a representative set of 10 layers, including 9 convolutional layers
(one 3x3 convolutional layer and 8 point-wise convolutions) from MobileNet-V2,
EfficientNet-lite, and Resnet-18, and one fully-connected layer from ViT. The
full details for reproducing the experiments are given in appendix F. Due to
the high computational complexity of the global solution for pruning, the
layers had to be split into chunks. The slice of 4 input channels over all
output channels was used for 3x3 convolutions. In the case of linear layers
and point-wise convolutions, slices 36 input features over all the output
features were used.

The results are shown in figure 4 grouped by bit-width. The rectangles
indicate the full range of the pruning and quantization methods between the
heuristic solution and the error lower bound or the global solution. Whenever
a rectangle for each chunk intersects the diagonal line, the ranking of the
two methods could depend on the optimization method, while in cases below or
above the diagonal, the ranking is guaranteed regardless of the optimizer. We
see that quantization mostly outperforms pruning for moderate compression,
while methods become more comparable for higher compression ratios.

##  5 Full-model comparison

---
Figure 4: Comparison in the post-training scenario. Each box corresponds to a
subset of one of 10 layers from the 4 different models that were used, with 7
different bit-width comparison points. The ranges of the box indicate the
lower and higher-bounds found by the algorithms.

Now that we have seen the comparison between the methods in the PTQ setting,
we turn to fine-tuning quantized and pruned models. This is the setting where
pruning is applied in most, and it is possible that fine-tuning can change the
models significantly enough that the performance between the two methods
changes.

In order to provide a fair comparison of pruning and quantization, we chose
the two most commonly used methods with performance competitive to state-of-
the-art. For quantization-aware training, we used the widely adapted LSQ
method suggested in [12, 2]. Following this approach, we jointly learn the
weights and quantization scales, keep the batch norm layers unfolded, and re-
estimated the batch norm statistics after training to avoid wrong running
estimates due to oscillations [51]. We use the method suggested in [70] for
pruning, which gradually increases the sparsity during fine-tuning and re-
estimates batch norm statistics after training.

In our experiments we used a set of 4 models trained for 4 tasks including
Resnet18, Resnet50 [27], MobileNet-V2 [58], MobileNet-V3-small [30],
EfficientNet-lite [60], and ViT [11] trained on ImageNet classification [57];
DeepLab-V3 [7] with MobileNet-V2 backbone trained for semantic segmentation on
Pascal VOC [13]; EfficientDet [61] trained for object detection on MS COCO
[43]; OPT-350 fine-tuned on WikiText-103.

For a fair comparison, we used the same amount of epochs of fine-tuning for
each method (full details on hyperparameters are given in appendix G). The
results given in table1 suggest that pruning almost never leads to higher
accuracy than quantization if an equal compression rate is considered. The
differences are sufficiently large enough that the small purported
improvements by some methods [59] will likely not close the gap.

To study the effect of training time, we also performed an ablation with 2
times longer fine-tuning on a subset of 3 models (Resnet50, EfficientNet, and
ViT). The results are given in appendix H. We observe that pruned models
generally benefit from fine-tuning more, and in particular pruning becomes
more beneficial for most compression ratios on Resnet50. However, for the
other models, quantization is still more beneficial due to a larger gap in
performance.

Model | Orig. | Metric | Method | 8b | 7b | 6b | 5b | 4b | 3b | 2b
---|---|---|---|---|---|---|---|---|---|---
Resnet-18 | 69.7 | acc. | quant. | 70.5 | 70.5 | 70.6 | 70.3 | 70.0 | 68.9 | 67.3
pruning | 70.3 | 70.1 | 69.9 | 69.5 | 69.3 | 68.3 | 66.8
Resnet-50 | 76.1 | acc. | quant. | 76.4 | 76.4 | 76.4 | 76.3 | 76.2 | 75.5 | 72.3
pruning | 76.6 | 76.4 | 76.2 | 76.1 | 75.9 | 75.4 | 74.3
MobileNet-V2 | 71.7 | acc. | quant. | 71.9 | 72.0 | 71.7 | 71.6 | 70.9 | 68.6 | 59.1
pruning | 68.1 | 65.6 | 61.9 | 56.3 | 48.0 | 34.0 | 21.2
EfficientNet | 75.4 | acc. | quant. | 75.2 | 75.3 | 75.0 | 74.6 | 74.0 | 71.5 | 60.9
pruning | 72.5 | 70.9 | 68.1 | 63.6 | 56.4 | 44.5 | 27.1
MobileNet-V3 | 67.4 | acc. | quant. | 67.7 | 67.6 | 67.1 | 66.3 | 64.7 | 60.8 | 50.5
pruning | 65.6 | 64.4 | 62.4 | 60.2 | 56.1 | 31.7 | 0.0
ViT | 81.3 | acc. | quant. | 81.5 | 81.4 | 81.4 | 81.0 | 80.4 | 78.4 | 72.2
pruning | 76.6 | 76.6 | 76.2 | 73.1 | 72.4 | 71.5 | 69.4
DeepLab-V3 | 72.9 | mIoU | quant. | 72.3 | 72.3 | 72.4 | 71.9 | 70.8 | 63.2 | 17.6
pruning | 65.2 | 62.8 | 56.8 | 47.7 | 32.9 | 18.6 | 10.0
EfficientDet | 40.2 | mAP | quant. | 39.6 | 39.6 | 39.6 | 39.2 | 37.8 | 33.5 | 15.5
pruning | 34.5 | 33.0 | 30.9 | 27.9 | 24.2 | 17.9 | 8.0
OPT-350m | 14.8 | perpl. | quant. | 14.8 | 14.8 | 14.9 | 15.0 | 15.3 | 15.9 | 19.9
pruning | 18.0 | 19.7 | 22.6 | 27.2 | 35.4 | 53.5 | 101.4
Table 1: Comparison of QAT and magnitude pruning with fine-tuning given equal
model size and equal number of epochs for fine-tuning.

#### Combining pruning and quantization

Another interesting questions is whether pruning is beneficial in combination
with quantization. To answer it, we perfromed an experiment on pruning
quantized Resnet-18, MobileNet-V2 and ViT with different pruning ratios. The
results are given on figure 5. On x-axis we plot the expected bit-widths which
is a product of the base bit-width and the sparsity in the pruned model
including the natural sparsity. The points marked by crosses are quantized
models with only natural sparsity and no extra pruning applied. As we can see,
mild degrees of pruning are beneficial in the combinations. However, we note
that no extra overhead was assumed for storing the pruning mask.

|
---|---
Figure 5: Combining pruning and quantization on ImageNet models. The average
bit-widths shown on x axis is computed as a product of the base bit-width and
the density of non-zero weight elements. Different pruning ratios are applied
to each base bitwidth model. Quantized models with only natural sparsity and
no extra pruning are marked with crosses.

##  6 Discussion

#### Other types of pruning

While we solely focused in our comparison on unstructured pruning in which
individual weights are removed, our results translate to semi-structured and
structured pruning. Unstructured pruning has more degrees of freedom and is a
strict superset of what can be represented by (semi-)structured pruning.
Therefore, unstructured pruning gives an upper bound of the accuracy for all
pruning methods. This means that for the cases in which quantization is better
than unstructured pruning, quantization will also be better than
(semi-)structured pruning. However, we can not make any claims for
(semi-)structured pruning for the few scenarios in which pruning is better
than quantization.

#### Natural sparsity in quantized tensors

In our comparison, we used a theoretical compression ratio for quantization,
which depends on the bitwidth. However, we also observe that quantized tensors
naturally contain many zeros; for example, 8-bit tensors from PyTorch model
zoo have an average sparsity of 13% while 4-bit tensors are 35% sparse. We
give more details on this in appendix C.

#### Representations learned in the compressed models

To provide insights into representations learned during pruning or QAT, we
studied the evolution of models during fine-tuning. We found that fine-tuning
after pruning tends to recover the original representation, while
quantization-aware training leads to learning completely new representations.
We provide further details on these experiments in appendix I.

#### Hardware implications

So far, we have deliberately avoided discussing the hardware implementations
of pruning and quantization and focused solely on the accuracy of both methods
at the same ideal compression rates. However, in practice, the hardware
considerations do matter for the usability of the methods.

The analysis above assumed an idealistic case for pruning in terms of memory
size and data transfer. Since the pruning is unstructured, in order to achieve
memory savings in practice, one would need at least 1 bit of information for
each weight indicating whether a weight is pruned or not. On top of 16-bit
weights, this gives a 6.25% storage overhead at a minimum. Quantization does
not have this overhead, as INT8 is just 8 bits smaller than 16 bits, and the
only storage overhead is a single scaling factor per tensor (or channel).

Also, in terms of the cost of computations done by the hardware, there is a
difference between the two methods. For pruning, any hardware would have to
take the densely stored weights and mask and either decompress them to the
dense format with all weights and many 0s or take the pruning into account in
the compute itself. No compute benefits are gained in the former, as the dense
calculations are done in the uncompressed number format. In the latter,
dedicated hardware to take into account the 0s is necessary. The overhead for
this is generally non-trivial, leading vendors to implement more semi-
structured pruning schemes [47]. Similarly, it is rare to see unstructured
activation compression for the same reason that this needs to happen
algorithmically on-the-fly. In contrast, quantization gives quadratic
improvements in the compute. Going from INT8 to INT4 theoretically improves
the compute performance by a factor 4, although practical gains depend on the
memory overhead (which improves by only a factor 2x) and the existence of
other formats in the same hardware compute unit.

Impact Using pruning or quantization leads to power reduction on many
architectures and enables new applications on mobile platforms. We see only a
positive impact from this on the whole. In some cases both pruning and
quantization might lead to biased predictions, a further discussion can be
found in [29].

Limitations First, our work has not extensively considered the hardware
implications of pruning or quantization. Second, we do not study combinations
of pruning and quantization apart from analyzing the inherent sparsity due to
pruning. We leave this for future work. Finally, we consider only uniform
quantization and ignore the other formats, such as low-precision floating or
logarithmic quantization, although these are not likely to change the results
presented in this paper.

##  7 Related work

#### Quantization

Integer quantization, or fixed-point quantization, is one of the most widely
used techniques for inference, allowing to reduce the latency and improved
energy efficiency. There are two main families of methods for model
quantization. The first family includes post-training quantization (PTQ)
methods [42, 52, 10, 1, 9, 6, 48, 40], which improve the model accuracy based
on per-layer optimization of the quantized weights in a data-optimized
fashion. The second family includes quantization-aware training methods [22,
34, 69, 8, 44, 12, 35, 2, 63, 51] which usually fine-tune the model with
quantization in the loop using straight-through estimator (STE) for computing
the gradient of rounding operations. A more comprehensive overview of
quantization methods can be found in [50].

#### Pruning

Neural network pruning is one of the oldest methods to compress neural
networks [37, 26]. A central problem in pruning is how to choose which weights
to prune. Approaches published in the literature include: binary gating, in
which a binary gate is learned on each individual weight [45, 46, 64];
sensitivity-based methods [39, 38, 66, 17, 18] in which sensitivity, based on
a weights’ gradient or hessian diagonal value, is used, and magnitude pruning
[24, 54, 70, 47, 59]. While conceptually simple, magnitude-based methods have
been shown to consistently outperform more intricate methods at scale [19, 4].
Weight re-initialization schemes [15, 16] or mask-reinitialization [59] yield
additional minor improvements. While most pruning approaches require fine-
tuning and yield unsatisfactory results in post-training scenarios, recent
adaptations of Hessian-based sensitivity approaches [37, 26], in which the
Hessian of a layerwise reconstruction loss is used instead of the task loss
Hessian, show good pruning results in post-training pruning of large language
models [17, 18].

#### Combining pruning and quantization

A number of works study combinations of pruning and quantization with
different levels of granularity [24, 64, 31, 65, 62, 65].

#### Comparing pruning and quantization

Despite the large amount of work on pruning, quantization, and combining them,
there is little literature comparing the two methods. To the best of our
knowledge, the closest work that performs a comparison of pruning versus non-
uniform quantization [33]. The work considers only small-scale models and
provides only an empirical comparison with no further analysis. Another
related study is [53].

##  8 Conclusion

We have seen in this paper that in several settings, unstructured pruning only
performs better than quantization in rare cases. In our theoretical analysis
of distributions and on the real-layer-data, pruning is only better than
quantization, compressing the network to an equivalent of 2 or 3 bits. This
amount of compression comes with such a degree of a drop in performance it is
rarely used in practice. The post-training quantization results are also
informative. In the setting without fine-tuning, we have shown with
theoretical bounds on many layers in neural networks that quantization is
almost always provably better than pruning. Our hypothesis is that quantized
layers are more accurate than pruned ones, as shown in the theoretical and PTQ
setting, and fine-tuning a network is still highly dependent on that. This is
in line with fine-tuning results, in which for many networks trained under the
same conditions, quantization always has higher performance than pruning.

The conclusion is clear: Quantization generally outperforms pruning for neural
networks. Taking into account the unfavorable hardware implications for
pruning described, it could be argued that the conclusion holds even stronger.
Based on this research, we recommend quantizing neural networks when
efficiency is required before pruning is explored.

##  9 Acknowledgement

We would like to thank Marios Fournarakis and Yelisei Bondarenko for their
help with performing QAT experiments.

## References

  * [1] Ron Banner, Yury Nahshan, and Daniel Soudry.  Post training 4-bit quantization of convolutional networks for rapid-deployment.  In Advances in Neural Information Processing Systems, 2019.
  * [2] Yash Bhalgat, Jinwon Lee, Markus Nagel, Tijmen Blankevoort, and Nojun Kwak.  Lsq+: Improving low-bit quantization through learnable offsets and better initialization.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, 2020.
  * [3] BigScience Workshop.  BLOOM (revision 4ab0472), 2022.
  * [4] Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag.  What is the state of neural network pruning?  Proceedings of machine learning and systems, 2:129–146, 2020.
  * [5] Christoph Buchheim, Ruth Huebner, and Anita Schoebel.  Ellipsoid bounds for convex quadratic integer programming.  SIAM Journal on Optimization, 25(2):741–769, 2015.
  * [6] Yaohui Cai, Zhewei Yao, Zhen Dong, Amir Gholami, Michael W. Mahoney, and Kurt Keutzer.  Zeroq: A novel zero shot quantization framework.  arXiv preprint arXiv:2001.00281, 2020.
  * [7] Liang-Chieh Chen, George Papandreou, Florian Schroff, and Hartwig Adam.  Rethinking atrous convolution for semantic image segmentation, 2017.
  * [8] Jungwook Choi, Zhuo Wang, Swagath Venkataramani, Pierce I-Jen Chuang, Vijayalakshmi Srinivasan, and Kailash Gopalakrishnan.  PACT: parameterized clipping activation for quantized neural networks.  arXiv preprint arxiv:805.06085, 2018.
  * [9] Yoni Choukroun, Eli Kravchik, and Pavel Kisilev.  Low-bit quantization of neural networks for efficient inference.  International Conference on Computer Vision (ICCV), 2019.
  * [10] Zhen Dong, Zhewei Yao, Amir Gholami, Michael W Mahoney, and Kurt Keutzer.  Hawq: Hessian aware quantization of neural networks with mixed-precision.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 293–302, 2019.
  * [11] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.  An image is worth 16x16 words: Transformers for image recognition at scale, 2020.
  * [12] Steven K. Esser, Jeffrey L. McKinstry, Deepika Bablani, Rathinakumar Appuswamy, and Dharmendra S. Modha.  Learned step size quantization.  In International Conference on Learning Representations (ICLR), 2020\.
  * [13] M. Everingham, L. Van Gool, C. K. I. Williams, J. Winn, and A. Zisserman.  The pascal visual object classes (voc) challenge.  International Journal of Computer Vision, 88(2):303–338, June 2010\.
  * [14] Simon Foucart and Holger Rauhut.  A Mathematical Introduction to Compressive Sensing.  Applied and Numerical Harmonic Analysis. Springer New York, New York, NY, 2013.
  * [15] Jonathan Frankle and Michael Carbin.  The lottery ticket hypothesis: Finding sparse, trainable neural networks.  arXiv preprint arXiv:1803.03635, 2018.
  * [16] Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M Roy, and Michael Carbin.  Stabilizing the lottery ticket hypothesis.  arXiv preprint arXiv:1903.01611, 2019.
  * [17] Elias Frantar and Dan Alistarh.  Optimal brain compression: A framework for accurate post-training quantization and pruning.  arXiv preprint arXiv:2208.11580, 2022.
  * [18] Elias Frantar and Dan Alistarh.  Sparsegpt: Massive language models can be accurately pruned in one-shot, 2023.
  * [19] Trevor Gale, Erich Elsen, and Sara Hooker.  The state of sparsity in deep neural networks.  arXiv preprint arXiv:1902.09574, 2019.
  * [20] Xinyang Geng and Hao Liu.  Openllama: An open reproduction of llama, May 2023.
  * [21] Michael Grant and Stephen Boyd.  CVX: Matlab software for disciplined convex programming, version 2.1.  http://cvxr.com/cvx, March 2014.
  * [22] Suyog Gupta, Ankur Agrawal, Kailash Gopalakrishnan, and Pritish Narayanan.  Deep learning with limited numerical precision.  In International Conference on Machine Learning, (ICML), 2015.
  * [23] Gurobi Optimization, LLC.  Gurobi Optimizer Reference Manual, 2023.
  * [24] Song Han, Huizi Mao, and William J Dally.  Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding.  arXiv preprint arXiv:1510.00149, 2015.
  * [25] Song Han, Jeff Pool, John Tran, and William Dally.  Learning both weights and connections for efficient neural network.  Advances in neural information processing systems, 28, 2015.
  * [26] Babak Hassibi, David G Stork, and Gregory J Wolff.  Optimal brain surgeon and general network pruning.  In IEEE international conference on neural networks, pages 293–299. IEEE, 1993.
  * [27] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Conference on Computer Vision and Pattern Recognition, 2016.
  * [28] Yihui He, Xiangyu Zhang, and Jian Sun.  Channel pruning for accelerating very deep neural networks.  In Proceedings of the IEEE international conference on computer vision, pages 1389–1397, 2017.
  * [29] Sara Hooker, Nyalleng Moorosi, Gregory Clark, Samy Bengio, and Emily Denton.  Characterising bias in compressed models.  arXiv preprint arXiv:2010.03058, 2020.
  * [30] Andrew Howard, Ruoming Pang, Hartwig Adam, Quoc Le, Mark Sandler, Bo Chen, Weijun Wang, Liang-Chieh Chen, Mingxing Tan, Grace Chu, Vijay Vasudevan, and Yukun Zhu.  Searching for mobilenetv3.  In International Conference on Computer Vision (ICCV), 2019.
  * [31] Peng Hu, Xi Peng, Hongyuan Zhu, Mohamed M Sabry Aly, and Jie Lin.  Opq: Compressing deep neural networks with one-shot pruning-quantization.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 7780–7788, 2021.
  * [32] Itay Hubara, Yury Nahshan, Yair Hanani, Ron Banner, and Daniel Soudry.  Accurate post training quantization with small calibration sets.  In International Conference on Machine Learning, pages 4466–4475. PMLR, 2021.
  * [33] Yerlan Idelbayev and Miguel Á Carreira-Perpiñán.  An empirical comparison of quantization, pruning and low-rank neural network compression using the lc toolkit.  In 2021 International Joint Conference on Neural Networks (IJCNN), pages 1–8. IEEE, 2021.
  * [34] Benoit Jacob, Skirmantas Kligys, Bo Chen, Menglong Zhu, Matthew Tang, Andrew Howard, Hartwig Adam, and Dmitry Kalenichenko.  Quantization and training of neural networks for efficient integer-arithmetic-only inference.  Conference on Computer Vision and Pattern Recognition (CVPR), 2018\.
  * [35] Sambhav R. Jain, Albert Gural, Michael Wu, and Chris Dick.  Trained uniform quantization for accurate and efficient neural network inference on fixed-point hardware.  arxiv preprint arxiv:1903.08066, 2019.
  * [36] Andrey Kuzmin, Mart Van Baalen, Yuwei Ren, Markus Nagel, Jorn Peters, and Tijmen Blankevoort.  Fp8 quantization: The power of the exponent.  arXiv preprint arXiv:2208.09225, 2022.
  * [37] Yann LeCun, John Denker, and Sara Solla.  Optimal brain damage.  Advances in neural information processing systems, 2, 1989.
  * [38] Namhoon Lee, Thalaiyasingam Ajanthan, Stephen Gould, and Philip HS Torr.  A signal propagation perspective for pruning neural networks at initialization.  arXiv preprint arXiv:1906.06307, 2019.
  * [39] Namhoon Lee, Thalaiyasingam Ajanthan, and Philip HS Torr.  Snip: Single-shot network pruning based on connection sensitivity.  arXiv preprint arXiv:1810.02340, 2018.
  * [40] Yuhang Li, Ruihao Gong, Xu Tan, Yang Yang, Peng Hu, Qi Zhang, Fengwei Yu, Wei Wang, and Shi Gu.  Brecq: Pushing the limit of post-training quantization by block reconstruction.  In International Conference on Learning Representations (ICLR), 2021\.
  * [41] Darryl Lin, Sachin Talathi, and Sreekanth Annapureddy.  Fixed point quantization of deep convolutional networks.  In International conference on machine learning, pages 2849–2858. PMLR, 2016.
  * [42] Darryl D. Lin, Sachin S. Talathi, and V. Sreekanth Annapureddy.  Fixed point quantization of deep convolutional networks.  In International Conference on Machine Learning, 2016.
  * [43] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C. Lawrence Zitnick.  Microsoft coco: Common objects in context.  In David Fleet, Tomas Pajdla, Bernt Schiele, and Tinne Tuytelaars, editors, Computer Vision – ECCV 2014, pages 740–755, Cham, 2014. Springer International Publishing.
  * [44] Christos Louizos, Matthias Reisser, Tijmen Blankevoort, Efstratios Gavves, and Max Welling.  Relaxed quantization for discretized neural networks.  In International Conference on Learning Representations (ICLR), 2019\.
  * [45] Christos Louizos, Max Welling, and Diederik P Kingma.  Learning sparse neural networks through $l\\_0$ regularization.  arXiv preprint arXiv:1712.01312, 2017.
  * [46] Christos Louizos, Max Welling, and Diederik P Kingma.  Learning sparse neural networks through $l_{0}$ regularization.  International Conference on Learning Representations (ICLR), 2018\.
  * [47] Asit Mishra, Jorge Albericio Latorre, Jeff Pool, Darko Stosic, Dusan Stosic, Ganesh Venkatesh, Chong Yu, and Paulius Micikevicius.  Accelerating sparse deep neural networks.  arXiv preprint arXiv:2104.08378, 2022.
  * [48] Markus Nagel, Rana Ali Amjad, Mart Van Baalen, Christos Louizos, and Tijmen Blankevoort.  Up or down? Adaptive rounding for post-training quantization.  In International Conference on Machine Learning (ICML), 2020.
  * [49] Markus Nagel, Marios Fournarakis, Rana Ali Amjad, Yelysei Bondarenko, Mart van Baalen, and Tijmen Blankevoort.  A white paper on neural network quantization.  ArXiv, abs/2106.08295, 2021.
  * [50] Markus Nagel, Marios Fournarakis, Rana Ali Amjad, Yelysei Bondarenko, Mart van Baalen, and Tijmen Blankevoort.  A white paper on neural network quantization.  ArXiv, abs/2106.08295, 2021.
  * [51] Markus Nagel, Marios Fournarakis, Yelysei Bondarenko, and Tijmen Blankevoort.  Overcoming oscillations in quantization-aware training.  In International Conference on Machine Learning, pages 16318–16330. PMLR, 2022.
  * [52] Markus Nagel, Mart van Baalen, Tijmen Blankevoort, and Max Welling.  Data-free quantization through weight equalization and bias correction.  In International Conference on Computer Vision (ICCV), 2019.
  * [53] Satya Sai Srinath Namburi, Makesh Sreedhar, Srinath Srinivasan, and Frederic Sala.  The cost of compression: Investigating the impact of compression on parametric knowledge in language models.  In Findings of the Association for Computational Linguistics: EMNLP 2023, pages 5255–5273, 2023.
  * [54] Sharan Narang, Erich Elsen, Gregory Diamos, and Shubho Sengupta.  Exploring sparsity in recurrent neural networks.  arXiv preprint arXiv:1704.05119, 2017.
  * [55] Jaehyun Park and Stephen Boyd.  A semidefinite programming method for integer convex quadratic minimization.  Optimization Letters, 12:499–518, 2018.
  * [56] Alberto Del Pia, Santanu S Dey, and Marco Molinaro.  Mixed-integer quadratic programming is in np.  Mathematical Programming, 162:225–240, 2017.
  * [57] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei.  ImageNet Large Scale Visual Recognition Challenge.  International Journal of Computer Vision (IJCV), 2015.
  * [58] Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen.  Mobilenetv2: Inverted residuals and linear bottlenecks.  In Conference on Computer Vision and Pattern Recognition (CVPR), 2018.
  * [59] Suraj Srinivas, Andrey Kuzmin, Markus Nagel, Mart van Baalen, Andrii Skliar, and Tijmen Blankevoort.  Cyclical pruning for sparse neural networks.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2762–2771, 2022.
  * [60] Mingxing Tan and Quoc Le.  EfficientNet: Rethinking model scaling for convolutional neural networks.  In International Conference on Machine Learning (ICML), 2019.
  * [61] Mingxing Tan, Ruoming Pang, and Quoc V. Le.  Efficientdet: Scalable and efficient object detection, 2020.
  * [62] Frederick Tung and Greg Mori.  Deep neural network compression by in-parallel pruning-quantization.  IEEE transactions on pattern analysis and machine intelligence, 42(3):568–579, 2018.
  * [63] Stefan Uhlich, Lukas Mauch, Fabien Cardinaux, Kazuki Yoshiyama, Javier Alonso Garcia, Stephen Tiedemann, Thomas Kemp, and Akira Nakamura.  Mixed precision dnns: All you need is a good parametrization.  In International Conference on Learning Representations (ICLR), 2020\.
  * [64] Mart van Baalen, Christos Louizos, Markus Nagel, Rana Ali Amjad, Ying Wang, Tijmen Blankevoort, and Max Welling.  Bayesian bits: Unifying quantization and pruning.  arXiv preprint arXiv:2005.07093, 2020.
  * [65] Haichuan Yang, Shupeng Gui, Yuhao Zhu, and Ji Liu.  Automatic neural network compression by sparsity-quantization joint learning: A constrained optimization-based approach.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2178–2188, 2020.
  * [66] Ruichi Yu, Ang Li, Chun-Fu Chen, Jui-Hsin Lai, Vlad I Morariu, Xintong Han, Mingfei Gao, Ching-Yung Lin, and Larry S Davis.  Nisp: Pruning networks using neuron importance score propagation.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 9194–9203, 2018.
  * [67] Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al.  Opt: Open pre-trained transformer language models.  arXiv preprint arXiv:2205.01068, 2022.
  * [68] Xiangyu Zhang, Jianhua Zou, Kaiming He, and Jian Sun.  Accelerating very deep convolutional networks for classification and detection.  IEEE transactions on pattern analysis and machine intelligence, 38(10):1943–1955, 2015.
  * [69] Shuchang Zhou, Zekun Ni, Xinyu Zhou, He Wen, Yuxin Wu, and Yuheng Zou.  Dorefa-net: Training low bitwidth convolutional neural networks with low bitwidth gradients.  arXiv preprint arXiv:1606.06160, 2016.
  * [70] Michael Zhu and Suyog Gupta.  To prune, or not to prune: exploring the efficacy of pruning for model compression.  arXiv preprint arXiv:1710.01878, 2017.

##  Appendix A Expected quantization error computation

The expected quantization error is a sum of two terms, the rounding error
$E_{r}$ and the clipping error $E_{c}$:

${\mathbb{E}}(W-Q(W))^{2}=E_{r}+E_{c},$ (30)

$E_{r}=\int\limits_{q_{min}}^{q_{max}}R_{q}^{2}(w)p(w)dw,$ (31)

$E_{c}=\int\limits_{-\infty}^{q_{min}}(w-q_{min})^{2}p(w)dw+\int\limits_{q_{max}}^{\infty}(q_{max}-w)^{2}p(w)dw.$
(32)

The rounding error $E_{r}$ can be split into two sub-intervals for each
interval $(q_{i},q_{i+1})$ where the first sub-interval corresponds to
rounding up and the second sub-interval corresponds to rounding down:

$\displaystyle
E_{r}=\sum_{i=1}^{|q|}\int\limits_{q_{i}}^{q_{i+1}}R^{2}(w)dw=\sum_{i=1}^{|q|}\int\limits_{q_{i}}^{(q_{i}+q_{i+1})/2}(w-q_{i})^{2}p(w)dw+$
(33)
$\displaystyle\sum_{i=1}^{|q|}\int\limits_{(q_{i}+q_{i+1})/2}^{q_{i+1}}(q_{i+1}-w)^{2}p(w)dw.$

In order to simplify the computation, we introduce the following function:

$I(a,b,w_{0})\coloneqq\int\limits_{a}^{b}(w-w_{0})^{2}p(w)dw.$ (34)

Thus we can redefine the rounding error as:

$E_{r}=\sum_{i=1}^{|q|}\left[I(q_{i},(q_{i}+q_{i+1})/2,q_{i})+I((q_{i}+q_{i+1})/2,q_{i+1},q_{i+1})\right].$
(35)

We note that the clipping error $E_{cw}$ can also be expressed using
$I_{w}(a,b,w_{0})$:

$\begin{split}E_{c}=I(w_{min},q_{min},q_{min})+I(q_{max},w_{max},q_{max}).\end{split}$
(36)

where $w_{min}$ and $w_{max}$ are the limits of a truncated distribution. The
analytical expressions for $I(w_{min},q_{min},q_{min})$ for different
distributions are given in the Appendix of [36]. Thus, given the explicit
definition of the quantization grid and the probability density function, we
can analytically compute the rounding error for different distributions, for
example, the Gaussian, Uniform, or Student’s t-distribution.

##  Appendix B Truncated Student’s-t distribution

The PDF of a truncated t-distribution with zero mean and unit variance is
given by:

$f(x,\nu,l)=\frac{p(x,\nu)}{\Phi(l)-\Phi(-l)}\mathds{1}_{-l\leq x\leq l},$
(37)

where $-l$ and $l$ are the truncation limits. $p(x,\nu)$ are the PDF and the
CDF of the non-truncated t-distribution given by:

$p(x,\nu)=\frac{1}{\sqrt{\nu}\text{B}\left(\frac{1}{2},\frac{\nu}{2}\right)}\left(1+\frac{x^{2}}{\nu}\right)^{\frac{-\nu+1}{2}},$
(38)

$\Phi(x)=\frac{1}{2}+x\Gamma\left(\frac{\nu+1}{2}\right)\times\frac{2\text{F}_{1}\left(\frac{1}{2},\frac{\nu+1}{2};\frac{3}{2},\frac{-x^{2}}{\nu}\right)}{\sqrt{\pi\nu}\Gamma\left(\frac{\nu}{2}\right)},$
(39)

where $F_{1}$ is the hypergeometric function.

Kurtosis value of this distribution depending on the symmetric truncation
range $l$ is plotted in figure 6.

---
Figure 6: Kurtosis of a symmetric truncated t-distribution as a function of
the truncation range.

##  Appendix C Sparsity in quantized tensors

As we noted in section 6, quantized tensors naturally have some sparsity. The
sparsity ratio tends to become higher if lower quantization bit-widths are
used. Below we give a table with the average sparsity for all PyTorch model
zoo tensors depending on the bit-width:

num. bits | 8 | 7 | 6 | 5 | 4 | 3 | 2
---|---|---|---|---|---|---|---
avg. quant. sparsity | 13% | 16% | 20% | 27% | 35% | 46% | 59%
Table 2: Natural sparsity in quantized tensors.

As we can see, the sparsity values become very significant, especially for low
bit-width values.

---
Figure 7: Correlation between per-layer SNR and full-model accuracy for
pruning and quantization noise.

##  Appendix D Correlation between model accuracy and per layer SNR

In this section, we measure the correlation between SNR at individual layers
of a network and the final model accuracy. It is important to study to which
degree the two measures are correlated as we used SNR for our experiments in
section 4. We note that in this section we use linear scale SNR which is a
normalized MSE in contrast to log-scale SNR used in section 4.

The results are given in figure 7. We pruned and quantized single layers of
Resnet-18 and plotted activations SNR versus the full model accuracy drop. We
observe a strong correlation between SNR and accuracy which confirms our
assumption made in section 4.

##  Appendix E Details of PyTorch model zoo tensors experiments

We quantized and pruned all the PyTorch model zoo weights tensors. All the
convolutional and fully-connected layers were considered, the list is given
below (45 models in total).

Classification models:

alexnet, resnet18, resnet34, resnet50, resnet101, resnet152, resnext50-32x4d,
resnext101-32x8d, wide-resnet50-2, wide-resnet101-2, vgg11, vgg11-bn, vgg13,
vgg13-bn, vgg16, vgg16-bn, vgg19-bn, vgg19, squeezenet1-0, squeezenet1-1,
inception-v3, densenet121, densenet169, densenet201, densenet161, googlenet,
mobilenet-v2, mobilenet-v3-large, mobilenet-v3-small, mnasnet0-5, mnasnet1-0,
shufflenet-v2-x0-5, shufflenet-v2-x1-0.

Object detection models:

fasterrcnn-resnet50-fpn, fasterrcnn-mobilenet-v3-large-320-fpn, fasterrcnn-
mobilenet-v3-large-fpn, maskrcnn-resnet50-fpn, keypointrcnn-resnet50-fpn,
retinanet-resnet50-fpn, ssd300-vgg16, ssdlite320-mobilenet-v3-large.

Semantic segmentation models:

lraspp-mobilenet-v3-large.

Video classification models:

r3d-18, mc3-18, r2plus1d-18.

##  Appendix F Details of per-layer experiments

To reduce the computational complexity of finding the global solution for
pruning, the layers had to be split into chunks. The slice of 4 input channels
over all output channels was used for 3x3 convolutions. In the case of linear
layers and point-wise convolutions, slices 36 input features over all the
output features were used.

In section, we provide details on per-layer experiments we performed in
section 4. In table 3 we give the names of the models and the layers we used
along with the sub-problem dimensionality we considered for each chunk.
Depending on the layer, the experiment took from approximately an hour up to
six CPU weeks.

Model | Layer | sub-problem dim.
---|---|---
MobileNetV2 | features.8.conv.0.0 | 32
features.8.conv.1.0 | 32
features.8.conv.0.0 | 32
features.11.conv.1.0 | 32
EfficientNet-lite | blocks.1.1.conv_pw | 32
blocks.6.0.se.conv_expand_pruning | 32
Resnet-18 | layer1.0.conv2 | 36
layer1.1.conv1 | 36
layer3.0.downsample.0 | 32
layer2.0.downsample.0 | 32
ViT | blocks.2.attn.proj | 36
Table 3: Details of per-layer experiments.

##  Appendix G Details of the full-model experiments

In our experiments we used a set of 9 models trained for 4 tasks including
Resnet18, Resnet50 [27], MobileNet-V2 [58], MobileNet-V3-small [30],
EfficientNet-lite [60], and ViT [11] trained on ImageNet classification [57];
DeepLab-V3 [7] with MobileNet-V2 backbone trained for semantic segmentation on
Pascal VOC [13]; EfficientDet [61] trained for object detection on MS COCO
[43], and OPT-350m fine-tuned on WikiText-103.

In table 4 we provide details of the full-model experiments.

Model | Batch size | Weight decay | Optimizer | FT num. epochs | Learning rate
---|---|---|---|---|---
Resnet-18 | 256 | 1.0e-4 | SGD | 20 | 1.0e-3
Resnet-50 | 128 | 1.0e-4 | SGD | 20 | 1.0e-5
MobileNet-V2 | 128 | 5.0e-5 | SGD | 20 | 1.0e-5
EfficientNet-lite | 128 | 5.0e-5 | SGD | 20 | 1.0e-5
MobileNet-V3 | 128 | 1.0e-4 | SGD | 20 | 1.0e-3
ViT | 128 | 1.0e-4 | Adam | 20 | 1.0e-4
DeepLab-V3 | 16 | 0.0 | SGD | 200 | 1.0e-6
EfficientDet | 16 | 5.0-5 | Adam | 20 | 1.0e-5
OPT-350m | 512 | 0.1 | Adam | 3 | 5.0e-5
Table 4: Details of full-model experiments.

As optimal learning for quantization and pruning depends on the compression
ratio, we performed a grid search with the step size corresponding to
multiplying the basic learning rate above by negative and positive powers of
$0.33$. For pruning of all the models except for DeepLab-V3 we gradually
increase sparsity during the first 15 epochs of fine-tuning and we use the
remaining 5 epochs to recover the accuracy with fixed sparsity. A similar
scheme is used for DeepLab-V3 with 150 epochs of gradual sparsity increase and
50 remaining epochs of fine-tuning.

For quantization experiments, we use per-tensor quantization and Adam
optimizer with a learning rate of 1.0e-5 for quantization scales optimization.
We compress weights only and do not prune or quantize activations.

##  Appendix H Full-model experiments with longer fine-tuning

In this section we report the results for QAT and magnitude pruning with twice
as longer fine-tuning compared to table 4. The results are given in table 5

Model | Orig. | Metric | Method | 8b | 7b | 6b | 5b | 4b | 3b | 2b
---|---|---|---|---|---|---|---|---|---|---
Resnet-50 | 76.1 | acc. | quant. | 76.6 | 76.6 | 76.5 | 76.3 | 76.2 | 75.5 | 72.3
pruning | 76.6 | 76.7 | 76.6 | 76.3 | 76.3 | 75.8 | 74.8
EfficientNet | 75.4 | acc. | quant. | 75.2 | 75.3 | 75.0 | 74.6 | 74.0 | 71.8 | 61.5
pruning | 73.0 | 71.9 | 69.5 | 65.8 | 60.0 | 50.7 | 34.6
ViT | 81.3 | acc. | quant. | 81.9 | 81.8 | 81.7 | 81.4 | 80.8 | 78.9 | 73.7
pruning | 80.3 | 79.7 | 79.0 | 77.7 | 76.3 | 74.3 | 71.6
Table 5: Comparison of QAT and magnitude pruning with twice as longer fine-
tuning compared to table 4.

##  Appendix I Analysis of representations learned during fine-tuning in QAT
and pruning

---
(a)
(b)
(c)
(d)
Figure 8: The evolutions of representations at different convolutional layers
of Resnet-18 during QAT and fine-tuning after pruning. We plot SNR and CKA
distances between activations of each layer of quantized/pruned model and the
original activations.

As fine-tuning significantly improves the accuracy after pruning or
quantization, it is interesting to investigate whether fine-tuning recovers
the original model. To answer this question, we study how representations at
each layer change during the course of fine-tuning by comparing them to the
original model representations.

For this purpose, we sample activations from two models, Resnet18 and ViT,
after each epoch of fine-tuning, and also directly after quantization/pruning.
We measure distances between the original activations and the corresponding
activations of the quantized and pruned models. To measure the distance
between two feature maps we consider two distance metrics, log-scale SNR and
the central kernel alignment (CKA) distance (Kornblith, et al. PMLR, 2019).

We show the results in figure 8. We observe qualitative agreement between both
metrics. Curiously, the results show different trends for pruning and
quantization. For pruning, the representations tend to become closer to the
original representation during fine-tuning. However, for quantization the
fine-tuning rather learns a representation that is different from the original
one. In order to provide more convenient visualizations, we show one-
dimensional plots of both distance metrics at the last non-classifier layer in
figure 9 (a-b). We can see that even in the cases of larger distances fine-
tuning after pruning tends to recover the representations while it is not the
case for QAT.

For ViT we observe qualitatively the same behavior, see figure 9 (c). We omit
SNR plots as this measure rapidly becomes negative both for pruning and
quantization in ViT. However, CKA evolution follows the same pattern as in the
case of Resnet-18 and confirms similar observations.

As we see, fine-tuning during QAT effectively tends to training different
representations, while fine-tuning after pruning has a tendency towards
recovering the original model.

---
(a)
(b)
(c)
Figure 9: Distances between activations of pruned/quantized models to original
activations at the last non-classification layer.