Via operator theoretic methods, we formalize the concentration phenomenon for a given observable `$r$' of a discrete time Markov chain with `$\mu_{\pi}$' as invariant ergodic measure, possibly having support on an unbounded state space. The main contribution of this paper is circumventing tedious probabilistic methods with a study of a composition of the Markov transition operator $P$ followed by a multiplication operator defined by $e^{r}$. It turns out that even if the observable/ reward function  is unbounded, but for some for some $q>2$, $\|e^{r}\|_{q \rightarrow 2} \propto \exp\big(\mu_{\pi}(r) +\frac{2q}{q-2}\big) $ and $P$ is hyperbounded with norm control $\|P\|_{2 \rightarrow q }< e^{\frac{1}{2}[\frac{1}{2}-\frac{1}{q}]}$, sharp non-asymptotic concentration bounds follow. Transport-entropy inequality ensures the aforementioned upper bound on multiplication operator for all $q>2$.  Also, the role of reversibility in concentration phenomenon is demystified. These results are particularly useful for the reinforcement learning and controls communities by allowing for concentration inequalities w.r.t standard unbounded obersvables/reward functions where exact knowledge of the system is not available, let alone the reversibility of stationary measure.

Transportation inequalities,  Harris recurrent Markov chain, uniform ergodicity, Spectral gaps, Hyper-boundedness/contractivity, Operator theory, Sample complexity.

§ INTRODUCTION

Successful use of control theory in high stake applications stems from its rigorous theoretical foundations; properties of dynamical system under consideration can be extracted from the spectral analysis (eigenvalues/eigenvector) of an associated matrix. The last decade has seen a tremendous surge in research activity on non-asymptotic analysis/concentration phenomenon of system identification
and reinforcement learning for random dynamical systems (e.g., <cit.>); tedious probabilistic techniques are employed making analysis intractable. If not, assumptions like boundedness of obervables, discounting the cost, or discretizing the state space are

To address these limitations, there is a need to
bring concentration phenomenon for dynamical systems on a same theoretical footing with controls.

Related Literature and Outline of Paper. Whether it is a question of learning value function corresponding to a stabilizing policy for a Markov decision process (MDP)
(<cit.>) or system identification (e.g., <cit.>), the existing analysis techniques heavily rely
on mixing arguments to conclude `time-distant temporally dependent samples  behave as independent identically distributed (iid)'. However, the notion of time-distant samples being uncorrelated is equivalent to $L^2$ spectral gap or Poincare inequality (see e.g., Chapter 7 of <cit.>). Secondly, probabilistic analyses are tedious, opaque, and leading to weak results (strong results are often limited to unrealistic assumptions).

Recognizing these limitation, we focus on non-asymptotic analysis of policy evaluation for average reward-based control on continuous state spaces, where the expected value of the reward w.r.t the stationary distribution of an MDP is approximated by its empirical averages, with high probability.
Our approach is inspired from a conjecture put forth by <cit.>
regarding spectral gaps for hyperbounded Markov semi-groups, which was recently solved by <cit.> for reversible case and by <cit.> in full generality. A remarkable advantage of this approach is uplifting a nonlinear random dynamical system into an infinite dimensional space where it behaves as a linear system.

We then,
as described in Section <ref>,
employ direct sum decomposition of the underlying Banach space, as in <cit.>, to prove the uniform ergodic theorem for the Markov transition operator.

Consequently, we
show how hyperboundedness leads to the desired spectral properties (given in <cit.>) for uncorellation of Poincare Inequality).

To the best of our knowledge, <cit.> interpreted the spectral gap in Markov transition operator
into non-asymptotic concentration bounds but his analysis only works on bounded observables. In Section <ref>, we introduce Feynman-Kac semi-group related to unbounded observable, which
based on
spectral properties of the multiplication operator
allows us to derive a sufficient condition for sharp concentration: transport-entropy inequality; we then
verify our results on linear Gaussian systems. <cit.> offer an operator theoretic treatment for concentration but pertinent functional inequalities are valid only for reversibility assumption.

Finally, concluding remarks are made in Section <ref> along with discussion on future problems for consideration.

Further implications of the analysis: estimating steady state correlations via sample covariance matrices.
Let us assume that we are observing i.i.d samples $(x_{i})_{i=1}^{N}$ from a centered distribution $P_{\infty}$ on $\mathbb{R}^{n}$, where $n$ is high dimensional. For example, in finance, each $x_{i}$ could be return on $n$ stocks and $N$ the number of trading days <cit.>. One wishes to estimate $P_{\infty}$ via $\Sigma_{N}:=\frac{1}{N}\sum_{i=0}^{N-1}x_{i}x_{i}^{T}$; in order to understand most significant factors and spatial correlations between the $n$ variables. It is well known in statistics literature that for $N>>n$, empirical covariance matrix $\Sigma_{N}$ is a good approximation of $P_{\infty}$. Now, consider covariates $(x_{i})_{i=1}^{N}$ as realizations of a random dynamical system in steady state; good estimate of $P_{\infty}$ is imperative for designing reduced order models, after performing principal component analysis. However, samples are now temporally correlated, along with spatial correlations. Thus, one would expect sample complexity to be worse than in the i.i.d case. Intuitively, one needs to quantify decay of temporal correlation/spectral gaps (as we do in Section <ref>), and then average only over 'distant' samples to get an accurate estimation of the stationary covariance matrix. Analysis developed in this paper can be extended, as part of future work, to estimation of correlations where the observable would be instead $f(x)=x x^{T}$.

The space of probability measures on a metric space $(\mathcal{X},d)$ is denoted by  $\mathcal{P(\mathcal{X})}$.
$\mathbb{E}$ is used to denote expectation. For a function $r$, we use $<r>_{\mu}$ to denote the expectation of $r$ w.r.t $\mu$. Given $\mu, \nu \in \mathcal{P(X)}$, Wasserstein metric of order $p \in [1, \infty)$ is defined as:

\begin{equation}
\label{eq:WM}
\mathcal{W}_{d}^{p} (\nu,\mu)= \bigg(\inf_{(X,Y) \in \Gamma(\nu,\mu)} \mathbb{E}~d^{p}(X,Y)\bigg)^{\frac{1}{p}};
\end{equation}

here, $\Gamma(\nu,\mu) \in \mathcal{P}(\mathcal{X}^{2})$, and $(X,Y) \in \Gamma(\nu,\mu)$ denotes that random variables $(X,Y)$ follow some probability distributions on $\mathcal{P}(\mathcal{X}^{2})$ with marginals $\nu$ and $\mu$. Another way of comparing two probability distributions on $\mathcal{X}$ is via relative entropy which is defined as:

\begin{equation}
% \begin{flalign}
% Ent(v||u)= & \nonumber \int \log\bigg(\frac{d\nu}{d\mu}\bigg) d\nu, \hspace{15pt} \text{if}~ \nu << \mu,
%      \\ \label{eq:ent}
%          = & +\infty, \hspace{47pt} \text{otherwise}.
\label{eq:ent}
Ent(v||u)= \begin{cases}
\int \log\bigg(\frac{d\nu}{d\mu}\bigg) d\nu, & \text{if}~ \nu << \mu, \\
+\infty, & \text{otherwise}.
\end{cases}
% \end{flalign}
\end{equation}

§.§ Problem Statement

Under the action of some state-dependent  control policy $\pi$, we consider a closed-loop random dynamical system of the form:

\begin{equation}
\label{eq:crds}
x_{k+1}=F\big(x_k, \pi(x_k), \epsilon_k\big), \hspace{10 pt} \epsilon_k  \hspace{6 pt} \text{is}~~iid, \footnote{For the sake of brevity, from now on, we will exclude reference to $\pi$ in the state update equations as state dependent policy imlplies there exists some function $G$ such that $F\big(x_k, \pi(x_k), \epsilon_k\big)=G(x_k, \epsilon_k)$.}
\end{equation}

where $x_{k} \in \mathbb{R}^n$ for all $k \in \mathbb{N}$ and $F: \mathbb{R}^n \times \mathbb{R}^n \times \mathbb{R}^n \longrightarrow \mathbb{R}^n $. In probabilistic language, the closed-loop dynamical system is a Harris Ergodic Markov chain.
Let us assume that the Markov chain converges to a unique ergodic invariant measure $\mu_{\pi}$. A question that is of utmost importance in average reward reinforcement learning  when exact dynamics are unknown (<cit.>) is: if we have access to empirical averages of some unbounded reward function $r(x)$,
can we estimate the concentration from simulating a single trajectory – i.e., when, how, and why can we provide something similar to following exponential concentrations

\begin{align}
\label{eq:expcon}  \mu^{N} \Bigg[\bigg|\frac{1}{N} \sum_{i=1}^{N} r(x_i) - <r>_{\mu_{\pi}} \bigg| > %\frac{\mathcal{W}_{d_{\beta^*}} (\mathcal{P}(x. \cdot), \mu_{\pi})}{\sqrt{N}\sqrt{1-\gamma^2}}%
\epsilon \Bigg]  \leq 2 \exp \bigg(-\frac{N \epsilon^2}{K_{sys}(r)}\bigg)?
\end{align}

Here, $r$ can be some unbounded function (e.g., in control theoretic or (RL) framework $r(x):=\|x\|$), $K_{sys}(r)$ is a constant dependent on system properties and `smoothness' of $r$ (related to Lipschitz constant) and $\mathcal{\mu}^{N}$ denotes the probability on $N$ covariates of the Markov Chain $(x_1,\ldots,x_N)$.

§.§ Contribution and Main Results

This paper's fundamental contribution is reducing the concentration phenomenon for Harris Ergodic Markov chains to a problem of bounding operator $e^{r}P : L^{2}(\mu_{\pi}) \longrightarrow L^{2}(\mu_{\pi})$, a composition of Markov operator $P$ and a multiplication operator $e^r$. A detailed mathematical and pedagogical overview of Poincare/ Spectral gap inequality is provided; we show that the problem is equivalent to temporally dependent samples having a concentration similar to iid samples. Even though multiplication operator $e^{r}$, associated with the standard reward function (observable) used in continuous control and RL problems is unbounded, transport-entropy inequality ensures that for all $q>2$, $e^{r}: L^{q}(\mu_{\pi}) \longrightarrow L^{2}(\mu_{\pi}) $ is bounded. Combined with hyperboundedness of Markov kernel, the concentration phenomenon is achieved.

§ SPECTRAL GAPS, ERGODIC THEOREMS AND POINCARE INEQUALITY

To mathematically express the phenomenon that time-distant samples, although temporally dependent, behave as iid , we will have to go to fundamentals of ergodic theory. Let us use $\mathbb{D}$ to denote the unit disc in the complex plane and $\mathbb{T}$ represents the unit circle in the plane. Consider the Banach space, with complex field, $L^{p}(\mu_{\pi})$ of $p \in [1, \infty]$ integrable functions; i.e., all measurable functions $f$ with $\int |f(x)|^p \mu_{\pi}(dx) < \infty $. Conjugate power of $p$, $c(p)$ is defined as $c(p) \geq 1$ that satisfies $\frac{1}{c(p)} +\frac{1}{p}=1$. Every $g \in L^{c(p)}$ corresponds to a bounded linear functional on $f \in L^{p}$ and its action is captured by $\langle f, g \rangle _{\mu_{\pi}} := \int f(x)\overline{g(x)} d \mu_{\pi}(x)$.

We consider linearity in first argument of the inner product and the boundedness follows by Cauchy-Schwarz: $|\langle f, g \rangle _{\mu_{\pi}}| \leq \|f\|_{p}\|g\|_{c(p)}$. Markov transition operator $P:L^{p} \rightarrow L^{p}$ is defined as $\|Pf\|_{L^p}= \bigg(\int |Pf(x)|^{p} \mu_{\pi}(dx)\bigg)^{\frac{1}{p}}= \bigg(\int |\int f(y)p(x, dy) |^{p} \mu_{\pi}(dx)\bigg)^{\frac{1}{p}} \leq \|f\|_{L^{p}}$, where the last inequality follows from Jensen inequality. Note that $P$ acts as an identity on constant functions, i.e., $P1=1$, and it is positive, i.e., $Pf \geq 0 $ if $f \geq 0 $.

A Markov chain is reversible or satisfies detailed balance condition if Markov transition operator $P$ when viewed as an operator on Hilbert space $L^{2}(\mu_{\pi})$  is equal to its  adjoint $P^*$: $\langle Pf,g \rangle:= \langle f, P^{*}g \rangle _{\mu_{\pi}} = \langle f, Pg\rangle$. A simple observation reveals that $P, P^*, PP^*$ and $P^*P$ are all Markov operators with $\mu_{\pi}$ as invariant measure. Consider a sequence $(A_{n})_{n \in \mathbb{N}}$ of bounded operators on some Banach space, there are different topologies (uniform, strong, and weak) to study its convergence (see e.g., Chapter 6 of <cit.> for exact definitions). We also suggest the reader unfamiliar with spectral properties of operators and associated notations (particularly Hyperboundedness and Fredholm theory) to consult Appendix <ref>.

§.§ Ergodic Theorems and Consequences

In functional analytic framework, the pair $(P, \mu_{\pi})$ is said to be ergodic if for any $f \in L^{\infty}(\mu_{\pi})$ satisfies  $Pf=f$, then f is a constant.

In probabilistic language, an ergodic Markov chain has a unique invariant stationary distribution.

The pair $(P, \mu_{\pi})$ is called aperiodic if for all $\lambda \in \mathbb{T}\setminus\{1\}$, $dim[N(\lambda I-P)]=0$.

Birkhoff Pointwise Ergodic theorem: Let $(x_n)_{n \in \mathbb{N}}$, be the samples from an  ergodic Markov chain. Then,

$\frac{1}{N} \sum_{n=0}^{N-1} f(x_n) \longrightarrow \mu_{\pi}(f)$, almost every initial condition  $x_0=x$  w.r.t $\mu_{\pi},$ and $f$ integrable w.r.t $\mu_{\pi}$.

This is reminiscent of the strong law of large numbers for iid sampling from distribution $\mu_{\pi}$. However, a very natural requirement for having a concentration similar to iid setting is sharp decay of correlation – i.e., for some $C<\infty$ and $\eta \in (0,1)$

\begin{equation}
\label{eq:pointran} |Cov_{\mu_{\pi}}[f(x_n),f(x_{n+m})]| \leq C \eta^{m} Var_{\mu_{\pi}} (f), \hspace{10pt} \forall f \in L^{2}(\mu_{\pi}).
\end{equation}

Now, the first step towards formalizing the preceding phenomenon is a concept related to uniform ergodicity.

If the pair $(P, \mu_{\pi})$ is ergodic, let $U$ be the orthogonal projection on $\{f \in L^{2}(\mu_{\pi}) : Pf=f \}$. Then,

\begin{equation}
\label{eq:meanerg}
\| \frac{1}{N} \sum_{n=0}^{N-1} P^{n}- U\|_{L^{2} (\mu_{\pi})} \longrightarrow 0;
\end{equation}

i.e., the operator, $\frac{1}{N} \sum_{n=0}^{N-1} P^{n}$
converges to a bounded linear projection $U$ in  the uniform operator topology.

If the pair $(P,\mu_{\pi})$ is ergodic then so is the pair $(P^*,\mu_{\pi})$.
We first show that $Im(I-P)$ is closed using Fredholm argument – because the dimension of co-kernel is finite: $dim[L^{2}(\mu_{\pi})\setminus Im(I-P)]= dim[N(I-P^*)]= dim[N(I-P)]=1$.
Now, consider the following decomposition:

\begin{equation}
\label{eq:freddirectsum}
(I-P):N(I-P) \bigoplus N(I-P)^{\perp} \rightarrow Im(I-P) \bigoplus Im(I-P)^{\perp}.
\end{equation}

Therefore, $I-P: N(I-P)^{\perp} \rightarrow Im(I-P)$ is bijective and by inverse mapping theorem $(I-P)^{-1} \in \mathcal{B}(Im(I-P),N(I-P)^{\perp})$ so there exists a $K<\infty$ such that $\|(I-P)^{-1}\|_{Im(I-P)\rightarrow N(I-P)^{\perp} } \leq K$ implying that the pair $(P,\mu_{\pi})$ is uniformly ergodic because: given any $f \in Im(I-P)$ there exists a unique $\hat{g} \in N(I-P)^{\perp}$  such that $f=(I-P)\hat{g}$ and $\|\frac{1}{N} \sum_{n=0}^{N-1} P^{n}f \|= \|\frac{1}{N} \sum_{n=0}^{N-1} P^{n}(I-P)\hat{g} \|=\frac{\|(I-P^N)\hat{g}\|}{N}=\frac{\|(I-P^N)(I-P)^{-1}f\|}{N} \leq 2\frac{\|(I-P)^{-1}f\| }{N} \leq  \frac{2K}{N} \|f\|$. So $\frac{1}{N} \sum_{n=0}^{N-1} P^{n}$ converges to $0$ at a uniform rate on $Im(I-P)$. Notice that,
when $Im(I-P)$ is closed: $Im(I-P)=N(I-P)^{\perp}$, because regardless of $Im(I-P)$ being closed : $Im(I-P) \subset N(I-P^*)^{\perp}$ and $Im(I-P)^{\perp}=N(I-P^*)$. Therefore, $Im(I-P)^{\perp}$ corresponds to $N(I-P)$ which by ergodicity assumption only comprises of constant function and $\frac{1}{N} \sum_{n=0}^{N-1} P^{n} _{|_{N(I-P)}} =I$.

The above theorem effectively provide a stronger version of the mean ergodic theorem – i.e., `$L^2 -$ uniform ergodicity'.

It is worth noting the following:

* Under ergodicity and reversibility assumption, $I-P$ is an Fredholm operator  with index 0; effectively, it means $1$ is an isolated eigenvalue of $P$ – i.e., for some $\epsilon>0$, $\sigma(P)=[-1,1-\epsilon] \cup \{1\}$ and the dimension of space of eigenfunctions associated to $1$, is $1$ .

* We define $S:=P_{|Im(I-P)}$ (when $Im(I-P)$ is closed), and since $Im(I-P)$ is invariant under $P$, implying $S:Im(I-P) \rightarrow Im(I-P) $. Because $(I-P)^{-1} \in \mathcal{B}(Im(I-P))$, $(I-S)^{-1}$ exists as well so $1 \not \in \sigma(S)$ and from previous bullet point as $S$ will contain subset of spectrum of $P$, indeed $\sigma(S) \subset [-1,1-\epsilon]$.

If the pair $(P, \mu_{\pi})$ is reversible, ergodic and aperiodic, then

$\|P^{n}-U\|_{L^{2}(\mu_{\pi})} \longrightarrow 0,$
in uniform operator topology.

Consider the operator $I+P$, as a map

\begin{equation}
\label{eq:fredap} I+P: N(I+P) \bigoplus N(I+P)^{\perp} \rightarrow Im(I+P) \bigoplus Im(I+P)^{\perp}.
\end{equation}

$N(I+P)=\{f \in L^{2}(\mu_{\pi}):Pf=-f\}$, which corresponds to periodic behavior but by hypothesis $dim[N(I+P)]=0$ and $dim[L^{2}(\mu_{\pi}) \setminus Im(I+P)]=dim[N(I+P)]=0$ (thanks to reversibility) so $I+P$ is a Fredholm operator implying that $-1 \not \in \sigma_{ess}(P)$ (see e.g., <cit.>). Moreover, $-1 \not \in \sigma(P)$ either. Since the spectrum of a bounded operator is always closed, there exists $\delta>0$ such that $\sigma(S)\subset [-1+\delta,1-\epsilon]$. Consequently $\rho(S)$, the spectral radius of $S$,  satisfies $\rho(S) \leq max(|-1+\delta|,|1-\epsilon|)<1$ and $P^n=S^n \bigoplus I_{N(I-P)}$, but $\rho(S)<1$ implies $S^n \rightarrow 0$, because by Gelfand's formula for any $\rho \in (\rho(S),1)$ there exists $M(\rho)< \infty$ such that $\|S^n\| \leq M(\rho) \rho^{n}$.

Spectral analysis of non-reversible $P$ is more involved as it can lies inside a unit disc and this is where hyperboundedness comes into play.

Hyperboundedness(see definition <ref> in Appendix) of $L^2-L^p$, where $p =2+\epsilon$ and $\epsilon>0$ implies that (a) for all $\lambda \in \mathbb{T}$, $dim[N(\lambda I-P)_{2}]<\infty$ and $(b)$ $dim[N(\lambda I-P^*)_{2}]<\infty.$ (b) independently implies $Im(\lambda I-P)_{2}$ is closed.

* $\sigma(P) \cap \mathbb{T}$ may only comprise of a finite number of distinct eigenvalues and each distinct eigenvalue has a finite-dimensional eigenspan.

* $\sigma_{ess}(P)$ is contained inside some closed disc of radius $\alpha<1$ in the complex plane.

* $\sigma(P)$ is `gapped' – i.e., it comprises of two disjoint sets: $\sigma(P)= \{\sigma(P)\cap\mathbb{T}\} \cup \{\sigma(P) \cap \alpha \mathbb{D} \}$.

Our proof is based on a result of <cit.>: infinite dimensional $L^{p}$ spaces are not isomorphic for $p \neq q$.
If $f \in N[\lambda I-P]$, for $\lambda \in \mathbb{T}$, it must satisfy $|Pf(x)|=|f(x)|$.
$P$ is $L^{2}-L^{p:=2+\epsilon}$ hyperbounded, for some $\epsilon>0$. Then duality implies that $P^*$ is $L^{c(p)}-L^{2}$ hyperbounded, where $c(p)$ is the conjugate power of $p$. Now recall, $P \in\mathcal{B}(L^{p})$ and $dim[L^{p}\setminus Im(\lambda I-P)_{p}]= dim[N(\overline{\lambda}I-P^*)_{c(p)}]$. If $dim[N(\overline{\lambda}I-P^*)_{c(p)}]= \infty$, strict inclusion implies there exists a $\hat{g} \in L^{c(p)}\setminus L^{2}$ such that $P^* \hat{g}= \overline{\lambda} \hat{g}$ and $|P^* \hat{g}|=|\hat{g}|$ which contradicts hyperboundedness. Therefore, $dim[L^p\setminus Im(\lambda I-P)_{p}]$ is finite which implies $Im(\lambda I-P)$ is closed in $L^{p}$and as $L^2 \subsetneq L^{c(p)}$ we have $dim[L^{2}\setminus Im(\lambda I-P)_{2}  ]=dim[N(\overline{\lambda}I-P^*)_{2}]< dim[N(\overline{\lambda}I-P^*)_{c(p)}]< \infty $ and we have that $Im(\lambda I-P)$ is closed when viewed as a map in $L^{2}$. Argument for $dim[N(\lambda I-P)_{2}]$ being finite follows the same hyperboundedness argument. Consequences follow from the disjoint nature of essential and discrete spectrum (see Theorem 7.9-7.11 of <cit.>).

If the pair $(P, \mu_{\pi})$ is ergodic, $L^2 - L^p$ hyperbounded for $p=3,4$ with norm condition $\|P\|_{L^2-L^p}<2^{\frac{1}{2}-\frac{1}{p}} $, then

\begin{equation}
\label{eq:opcontoproj} \|P^{n}-U\|_{L^{2}(\mu_{\pi})} \longrightarrow 0, \hspace{3pt} \text{in a uniform operator topology}.
\end{equation}

The norm condition $\|P\|_{L^2 \rightarrow L^4} <2^{\frac{1}{2}-\frac{1}{4}}$ or $\|P\|_{L^2 \rightarrow L^3} <2^{\frac{1}{2}-\frac{1}{3}}$ ensures aperiodicity (see Theorem 5.1 and 5.3 in <cit.> ); only $\{1\} \in \sigma(P) \cap \mathbb{T}$ and corresponds to the eigenspan of constant functions. Following the argument of Theorem <ref>: $P^n=S^{n} \bigoplus I_{N(I-P)} $, where $S=P_{|Im(I-P)}$ and  $\sigma(S) \subset \alpha \mathbb{D} $ for some $\alpha \in (0,1)$. Consequently, $\rho(S) \leq \alpha$, and for all $\rho \in (\alpha,1)$ there exists an $M(\rho)<\infty$ such that $\|S^n\| \leq M(\rho)\rho^{n}$; and thus, the result follows.

A trivial corollary of  $\|P^{n}-U\|_{L^{2}(\mu_{\pi})} \longrightarrow 0$ in uniform operator topology is that for some $\rho \in (0,1)$, $C<\infty$ and for all $n \in \mathbb{N}$, it holds that

\begin{equation}
\label{eq:uopcontopoinc}
\|P^{n}\big(f-\mu_{\pi}(f)\big)\|_{L^2} \leq C \rho^{n} \|f-\mu_{\pi}(f)\|_{L^2},
\end{equation}

which is equivalent to sharp decay of correlation in (<ref>).

§ HYPERBOUNDEDNESS AND TRANSPORT-ENTROPY INEQUALITY IMPLIES CONCENTRATION

After ensuring uncorrelation for time-distant samples, it is safe to relate to the iid setting and remind ourselves that sharp concentrations heavily rely on the ability to take exponential moments of the observable w.r.t underlying measure. An attempt to analyse the uncorrelation
and exponential integrability via a single linear operator brings us to the following discussion.

Feynman-Kac semigroup plays an integral role in the study of fluctuations of time additive quantities of diffusion process in continuous time, <cit.>. The reader is referred to <cit.> for a detailed exposition on this topic in discrete-time setting. We identify with the observable/reward function $r$, a Feynman-Kac semigroup, which is a composition of the Markov transition operator followed by an exponentiated multiplication operator w.r.t observable – i.e., $e^{r}P: D_{(\cdot)} \subseteq L^{2}(\mu_{\pi}) \rightarrow L^{2}(\mu_{\pi})$,
such that for all $g \in D_{(\cdot)}$ (the domain on which semigroup operators can be viewed as bounded operator) it holds

(e^r P)^n g(x):= 𝔼_x [g(x_N) e^∑_i=0^n-1 r(x_i) ] , ∀n ∈ℕ.

Assume that $x_0 \thicksim \beta$ and $\beta << \mu_{\pi}$. We have the following upper bound on the deviation of the observable:

ℙ_β ( 1/N ∑_i=0^N-1 r(x_i) -μ_π (r) ≥ϵ)  ≤ d β/d μ_π _2  inf_s>0(e^srP)^N_L^2 - L^2e^-sN( μ_π(r)+ϵ).

Thus, the task at hand is bounding the operator $e^{r}P$  in a meaningful way to get a favorable concentration result. $P$ in itself is a positive contraction but exponentiated multiplication operator defined by unbounded observable require a short detour into its spectral analysis and transport-entropy inequality.

Multiplication operator defined by $e^r$.
The operator $\big(e^{r},D(e^r)_{p}\big)$ is closed and densely defined, see e.g., Proposition 3.10 from Chapter 1 in <cit.>. The essential range of $e^r$ with $\mu_{\pi}$ as an underlying measure is defined as $e^{r}_{ess} (\mu_{\pi}):= \bigg \{ \lambda \in [1, \infty) : \mu_{\pi} \big( |e^r -\lambda|< \epsilon \big) \neq 0, \hspace{2pt} \forall \hspace{2pt} \epsilon >0  \bigg\}$, and the essential norm of $e^r$, $\|e^r\|_{\infty}:= \sup \{ \lambda \in e^{r}_{ess} (\mu_{\pi}) \}
$. Multiplication operator $e^r$ is bounded in some and hence all $L^p$, iff  $\|e^r\|_{\infty} < \infty$. Consequently, $D(e^r)(p)=L^{p}$ and $\|e^r\|_{L^p \rightarrow L^p} = \|e^r\|_{\infty} $. If the stationary measure $\mu_{\pi}$ is not compactly supported and is absolutely continuous w.r.t Lebesgue measure then $\|e^r\|_{L^p \rightarrow L^p}= \infty$. However, not all is lost, as suggested in the previous section that we need some notion of hyperboundedness for uncorrelation. So if for some $p>2$, $P:L^{2} \rightarrow L^{p}$, in order to ensure $e^{r}P \in \mathcal{B}(L^{2})$ it is sufficient to prove $e^{r}:L^{p} \rightarrow L^{2}$. This is where the transport-entropy inequality comes into play.

Consider metric space $(\mathcal{X},d)$ and reference  probability measure $\mu \in \mathcal{P}(\mathcal{X})$. Then we say that $\mu$ satisfies Transport-Entropy(T-E) inequlaity with constant C or to be concise $\mu \in  \mathcal{T}_{1}^d (C)$ for some $C>0$ if for
all $\nu \in \mathcal{P}(\mathcal{X})$ and $\nu << \mu$, it holds that

\begin{equation}
\label{eq:t1}
\mathcal{W}_d (\mu, \nu) \leq \sqrt{2 C Ent(\nu||\mu)}.
\end{equation}

$\mu$ satisfies $\mathcal{T}_{1}^d (C)$ if and only if for all Lipschitz function $f$ with $<f>_{\mu}:= \mathbb{E}_{\mu} f$, it holds that

∫e^λ(f- <f>_μ) dμ≤exp(λ^2/2C f_L(d) ^2),  where      f_L(d):= sup_x ≠y |f(x)-f(y)|/d(x,y).

If $\mu_{\pi} \in  \mathcal{T}_{1}^d (C_{\pi})$ for some $C_{\pi}>0$ and $r$ is Lipschitz w.r.t metric $d$ then we have for all  $p>2$, $e^{r}:L^{p} \longrightarrow L^{2}$ is a bounded operator with norm:

\begin{equation}
\label{eq:ngtvhyp}
\|e^{r}\|_{L^p \rightarrow L^{2}} \leq \exp \bigg( \mu_{\pi}(r) + \frac{2p C_{\pi} \|r\|_{L(d)} ^2 }{(p-2)2} \bigg).
\end{equation}

The proof is a simple application of Cauchy-Schwarz and the exponential moment inequality for Lipschitz functions under distribution $\mu_{\pi}$ satisfying the transport-entropy inequality.

Without any assumption of reversibility, if the invariant measure $\mu_{\pi} \in  \mathcal{T}_{1}^d (C_{\pi})$ for some $C_{\pi}>0$ and $r$ is Lipschitz w.r.t metric $d$ and for some $q>2$, $P:L^{2}(\mu_{\pi}) \longrightarrow L^{q}(\mu_{\pi})$ is hyperbounded with norm $\|P\|_{L^2 \rightarrow L^q } < e^{\frac{1}{2}\big[\frac{1}{2}-\frac{1}{q}\big]}$. Given $n \in \mathbb{Z}^{+}$ and $\delta \in (0,1)$ and an initial distribution $
\beta<< \mu_{\pi}$, if   $N \geq  \ln \bigg(\big\|\frac{d \beta}{\mu_{\pi}}\big\|_{2} \frac{1}{1-\delta}\bigg) \bigg( \frac{4n^{2}q}{(q-2) -4n^{2}q \ln \|P\|_{L^2 \rightarrow L^q } } \bigg) $, we have that

\begin{align}
\label{eq:maincrux} \mathbb{P}_{\beta} \bigg( \frac{1}{N} \sum_{i=0}^{N-1} r(x_i) -\mu_{\pi} (r) \geq \frac{\sqrt{C_{\pi}}\|r\|_{L(d)}}{n}   \bigg)  < 1-\delta.
\end{align}

Since the theorem assumptions ensure $e^r P \in \mathcal{B}(L^{2}(\mu_{\pi})) $, we have that $\|(e^r P)^N\| \leq \|e^r P\|^{N}$. Let $\epsilon(n):= \frac{\sqrt{C_{\pi}}\|r\|_{L(d)}}{n} $,  where $\sqrt{C_{\pi}}\|r\|_{L(d)}$ is proportional to the square root of  variance of $r$ under distribution $\mu_{\pi}$. Notice that as opposed to standard $(\epsilon, \delta)$ probability arguments, here we have scaled $\epsilon=\epsilon(n)$ with a control variable $n$ that we can increase to make $\epsilon$ arbitrarily small. From the preceding discussion, it holds that

\begin{align}
\|(e^{sr}P)^{N}\|_{L^2 - L^2}e^{-sN( \mu_{\pi}(r)+\frac{\sqrt{C_{\pi}}\|r\|_{L(d)}}{n})} \leq \|P\|_{2-q} ^{N} e^{N\bigg( \big(\frac{2q}{q-2}\big) \frac{s^2}{2} C_{\pi} \|r\|_{L(d)}^2   - s\sqrt{C_{\pi}} \frac{\|r\|_{L(d)}}{n}\bigg)},
\end{align}

and a trivial calculation reveals

\begin{align}
\inf_{s>0} \|P\|_{2-q} ^{N} e^{N\bigg( \big(\frac{2q}{q-2}\big) \frac{s^2}{2} C_{\pi} \|r\|_{L(d)}^2   - s\sqrt{C_{\pi}} \frac{\|r\|_{L(d)}}{n}\bigg)}= e^{N \bigg( ln \|P\|_{2-q} -\frac{1}{2n^2} \big[ \frac{q-2}{2q}\big]  \bigg)},
\end{align}

which we should be able to decrease as $N$ increase; for every $n \in \mathbb{Z}^{+}$, which happens to be the case if $\|P\|_{L^2 \rightarrow L^q } < e^{\frac{1}{2}\big[\frac{1}{2}-\frac{1}{q}\big]}$ and all other results follow.

Since our norm control $\|P\|_{L^2 \rightarrow L^q } < e^{\frac{1}{2}\big[\frac{1}{2}-\frac{1}{q}\big]}$ is in harmony with the upper bound for $q=3,4$ given by <cit.>, which implies implies aperiodicity and consequently Poincare' $L^2-$ Spectral gap for Markov transition operator. We conjecture that for $q
\in (2,3)$ our upper bound might imply aperiodicity and hence $L^2-$ Spectral gap.

Assuming hypercontractivity, a stronger   theoretical result similar to  <cit.> can be directly deduced.

Without any reversibility assumption on the pair $(P,\mu_{\pi})$, if the  stationary distribution satisfies T-E inequality i.e., $\mu_{\pi} \in \mathcal{T}_{1} ^{d} (C_{\pi})$ and for some $p>2$ associated transition kernel is hypercontractive, i.e., $\|P\|_{2 \rightarrow p} \leq 1 $, then for any initial distribution $\beta << \mu_{\pi}$ and $N \in \mathbb{N}$ it holds

ℙ_β ( 1/N ∑_i=0^N-1 r(x_i) -μ_π (r) ≥ϵ)  ≤ d β/d μ_π _2  exp(-N ϵ^2 (p-2)/4 C_π r_L(d) ^2 p  ).

Consequently, given $\epsilon>0$ and $\delta \in (0,1)$, it holds that for all $N \geq \frac{\ln \bigg(\big\|\frac{d \beta}{\mu_{\pi}}\big\|_{2} \frac{1}{1-\delta}\bigg)4 C_{\pi} \|r\|_{L(d)} ^2 p }{\epsilon^2 (p-2)}$  the chain satisfies $\mathbb{P}_{\beta} \bigg( \frac{1}{N} \sum_{i=0}^{N-1} r(x_i) -\mu_{\pi} (r) \geq \epsilon \bigg) \leq 1-\delta$.

Let us verify these result on one dimensional linear Gaussian dynamical system with $|\alpha|<1$:

\begin{equation}
\label{eq:LG1}
x_{n+1}= \alpha x_n +w_n. \hspace{5pt}, w_n \thicksim \mathcal{N}(0,1) \hspace{2pt} \text{and iid}.
\end{equation}

An easy check reveals stationary distribution of (<ref>) is $\gamma_{1,\alpha} := \mathcal{N}\bigg(0, \frac{1}{1- \alpha ^2}\bigg)$.

Given $\alpha$ such that $|\alpha| <1 $, there exitst $p:=p(\alpha)>2$ such that $\|P\|_{2 \rightarrow p, \gamma_{1,\alpha}} \leq 1$  (Hypercontractivity) and $\|\big(e^{r}P\big)^{N}\| \leq e^{N \bigg( \gamma_{1,\alpha} (r) +\big(\frac{2p}{p-2}\big) \frac{\|r\|_{L(d)} ^2}{2} \bigg)} $.

A trivial application of change of variable and Stein's lemma results in

P_2 →p ≤1/(1-α^4)^1/4 1/( 1-α^2 p/(1+α^2) )^1/2p 1/e^2/p ( 1-α^2 p/(1+α^2) ) .

It is a common knowledge (see Corollary 7.2 of <cit.>), that$\gamma_{1, \alpha}  \in \mathcal{T}_{1} ^{d} (1)$ i.e., satisfies T-E
inequality with constant 1. It follows from (<ref>) that for all $g \in L^{2} \big(\gamma_{1,\alpha}\big)$ such that $\|g\|_{2} \leq 1 $, there exists  $p>2$ such that $\|Pg\|_{p} \leq 1$. By applying Cauchy-Schwarz to the powers $\frac{p}{2}$ and its' conjugate number $\frac{p}{p-2}$ we get:

(e^rP)g_2  ≤Pg_p  ( ∫e^2p/p-2 r(x) d γ_1,α (x) )^p-2/2p
≤P_2 →p   ( e^ γ_1,α (r) e^(2p/p-2) r_L(d) ^2 /2 ),

where (<ref>) follows from hypercontractivity of the transition operator and the fact that stationary distribution satisfies T-E inequality with $C=1$ and $d$ is the Euclidean metric. Conclusion follows from the trivial inequality $\|\big(e^{r}P\big)^{N}\| \leq \|\big(e^{r} P \big)\|^{N}$ and we have a sharp concentration as in Corollary <ref>.

§ CONCLUSION AND FUTURE WORK

In this work, we have narrowed down the concentration phenomenon for Harris ergodic Markov chains to a study of the composition of the Markov transition operator followed by a an exponentiated multiplication operator defined by the observable under consideration. Hyperboundedness and transport-entropy inequality suffices for  concentration phenomen. However, there are still unanswered questions that needs further exploration.
For example, the impact of aperiodicity and hyperboundedness – we believe that via continuity of the Fredholm index we can extend the norm control on $\|P\|_{L^2- L^{p}}$ that implies aperiodicity. Currently, only result for $p=3,4$ is available. Although the transport-entropy inequality can be verified via exponential-type Lyapunov function we introduced
in the accompanying paper <cit.> easily verifiable conditions for hyperboundedness on the continuous state space is still an open problem (besides the linear Gaussian case). Extending analysis to estimation of steady state correlation is also a work in progress.

§ APPENDIX

Spectral Decomposition

Let $A$ be a bounded operator on a Banach space $\mathcal{X}$, denoted by $A \in \mathcal{B}(\mathcal{X})$. $\lambda \in \mathbb{C}$ is said to be in resolvent of $A$, denoted by $\lambda \in RS(A)$, if $\lambda I -A : \mathcal{X} \rightarrow \mathcal{X}$ is bijective. Bounded inverse theorem implies that for $\lambda \in RS(A)$, $R_{\lambda}(A):=(\lambda I-A)^{-1} \in \mathcal{B}(\mathcal{X})$ . The spectrum of $A$ is denoted by $\sigma(A):= \mathbb{C} \setminus RS(A)$. Spectral radius of $A$ is denoted by $\rho(A):= \sup{|\lambda|: \lambda \in \mathbb{C}}$.  Consequently, if there exists a $v \in \mathcal{X}$ and $\lambda \in \mathbb{C}$ such that $Av= \lambda v$ (i.e., $\lambda$ is an eigenvalue with the corresponding eigenfunction $v$) then $\lambda I -A$ is not injective, which implies $\lambda \in \sigma(A)$. However, the spectrum of $A$ is not limited to eigenvalues; for a detailed monograph of spectral theory see e.g., <cit.>.

Let $A$ be a bounded operator on some Banach space $\mathcal{X}$. It is called Fredholm if: (a) $ dim[N(A)]< \infty$, (b) $ dim[\mathcal{X}\setminus Im(A)]< \infty$, and (c) $ Im(A)$ is closed. Here, $dim[N(A)]$ denotes the dimension of the null space of $A$ and $Im(A)$ means the range of $A$; $ dim[\mathcal{X}\setminus Im(A)]$ is often read as the dimension of cokernel of $A$.

Note that the condition (c) is redundant; it follows from (b).

The index of a Fredholm operator $A$ is defined as
$ind(A)=dim[N(A)]-dim[X\setminus Im(A)]$, and for some small perturbations $\Delta(A)$ to the operator $ind(A+\Delta(A))=ind(A)$.

$\lambda \in \sigma(A)$ is said to be in essential spectrum of $A$, ($\lambda \in \sigma_{ess}(A)$ )  if and only if $\lambda I- A$ is not a Fredholm operator. $\lambda \in \sigma(A)\setminus \sigma_{ess}(A) $ is said to be in discrete spectrum, ($\lambda \in \sigma_{disc}(A)$ )  if and only if (a) $\lambda$ is an isolated point of $\sigma(A)$ and (b) $\{\psi \in \mathcal{X}:A\psi=\lambda \psi \}$ is finite dimensional.

Markov operator is called hyperbounded, if for some $1\leq p<q \leq \infty$, $P$ is a bounded operator from $L^{p}(\mu_{\pi})$ to $L^{q}(\mu_{\pi})$ (we will often call it $L^{p}-L^{q}$ hyperboundedness). More stringent requirement of hypercontractivity requires $P$ to be hyperbounded with $\|P\|_{L^p \rightarrow L^q} \leq 1$.

It follows from Jensen's inequality that for all $r \geq 1$, $\|P\|_{L^{r}(\mu_{\pi})} \leq 1$, and Riesz-Thorin interpolation implies that for all $1<p<q$, $P$ is $L^{p}-L^{q}$ hyperbounded.


# A Generalization of Continuous Relaxation in Structured Pruning.

Brad Larson
Thermo Fisher Scientific
<EMAIL_ADDRESS>Bishal Upadhyaya
Thermo Fisher Scientific
<EMAIL_ADDRESS>Luke McDermott
UC San Diego
<EMAIL_ADDRESS>Siddha Ganju
NVIDIA Corporation
<EMAIL_ADDRESS>
###### Abstract

Deep learning harnesses massive parallel floating-point processing to train
and evaluate large neural networks. Trends indicate that deeper and larger
neural networks with an increasing number of parameters achieve higher
accuracy than smaller neural networks. This performance improvement, which
often requires heavy compute for both training and evaluation, eventually
needs to translate well to resource-constrained hardware for practical value.
Structured pruning asserts that while large networks enable us to find
solutions to complex computer vision problems, a smaller, computationally
efficient sub-network can be derived from the large neural network that
retains model accuracy but significantly improves computational efficiency.

We generalize structured pruning with algorithms for network augmentation,
pruning, sub-network collapse and removal. In addition, we demonstrate
efficient and stable convergence up to 93% sparsity and 95% FLOPs reduction
without loss of inference accuracy using with continuous relaxation matching
or exceeding the state of the art for all structured pruning methods. The
resulting CNN executes efficiently on GPU hardware without computationally
expensive sparse matrix operations. We achieve this with routine automatable
operations on classification and segmentation problems using CIFAR-10 [14],
ImageNet [5], and CityScapes datasets [3] with the ResNet [11] and U-NET
network architectures[24].

##  1 Introduction

Figure 1: Classification results of various models trained on ImageNet-22K. We
(CRISP) maintain accuracy on ResNet-101 while decreasing total FLOPs with
higher sparsity.

An established trend in deep learning literature is the improvement of model
accuracy with increased computation (see Figure 1). This becomes challenging
for model inference at the edge where data is abundant but compute resources
are minimal due to power, hardware size, and cost constraints. Our focus is to
reduce the inference computation of scientific and medical instruments, such
as microscopes and CT scanners with structured pruning. For example,
Transmission electron microscope (TEM) data can receive up to $4096X4096$
resolution images up to $400$ frames per second [1], well past the achievable
processing rates of large neural networks with the most advanced GPU.
Structured pruning restructures models weights at training time. A key
assumption of pruning is that larger models provide great search spaces for
pruning algorithms to find the subnetworks with optimal performance. The
availability of large, transfer-learning models and their potential to be
fine-tuned to certain tasks makes the structured pruning of larger models
efficient.

Despite its published successes [18], it is uncommon in practice to use
structured pruning to improve model computational efficiency . Barriers to
broadly adopting structured pruning as a standard part of CNN model
optimization include (1) the need to manually customize models and model
training [9], (2) published poor convergence stability , and (3) unexplored
behavioral differences between original and pruned models. Here, we generalize
the formulation of continuous relaxation in structured pruning into an
automatable procure applicable to common convolutional neural network (CNN)
architectures. Where other structured pruning methods have surpassed the
published performance of continuous relaxation in structured pruning, we
simply and and improve the continuous relaxation in structured pruning
formulation to achieve stable and direct convergence to state of the art
structured pruning performance. Finally, we evaluate the accuracy of image
segmentation vs object size of original and pruned models. This study
demonstrates similar model behavior between original and pruned models, our
desired behavior. Structured pruning did not reduce intersection over union
(IoU) accuracy irrespective of object size. Our contributions include111All
code, models, and example pipelines are available at
https://github.com/sherlj5352/crisp.:

  1. 1.

an automatable structured pruning and layer collapse algorithm applicable
across CNN architectures,

  2. 2.

simplified stiffening and multi-step pruning providing direct and stable
convergence to state-of-the-art (SOTA) computational efficiency without loss
of accuracy,

  3. 3.

IoU vs object size metric demonstrating structured pruning maintained
consistent model performance across of object sizes.

##  2 Related Work

Neural network pruning methods can be divided into two categories –
unstructured [7, 23, 20] and structured [13, 10, 9]. Unstructured pruning
removes parameters to optimize model sparsity. Specialized sparse matrix
operations implemented in software or hardware are needed to realize a partial
speedup from unstructured pruning. Structured pruning provides a direct
speedup with widely available GPU hardware and software deployments. Since its
focus is computational efficiency, structured pruning removes entire network
structures such as blocks, layers, and convolutional channels that maintain
full matrix operations. [9].

Structured pruning literature generally optimizes sparsity, in which the
objective is to reduce the model size [22]. Conversely, CNN floating point
operation (FLOP) reduction applies greater weight to removing operations
performed on larger channels that require more computations [28]. FLOP
reduction provides a hardware-independent metric of computational efficiency
that can be quickly computed during model training. FLOP reduction is
advantageous, especially for edge devices with numerous machine learning
algorithms that vie for inference compute time. Flop reduction enables a
greater batch size, reduced hardware requirements that free up space for
instrument design, easier access to high-resolution data inference and a
heightened efficiency of heterogeneous workflows.

We discuss related works along three threads:  1. the achievement of high
accuracy and sparsity through unstructured pruning and its impact on FLOPs,
2. structured pruning search metrics, and regularization with sparsity
approaching that of unstructured pruning and direct improvement in FLOPs,  3.
barriers to generalize and automate structured pruning.

The earliest works in neural network pruning show that randomly-initialized
neural networks contain subnetworks that, when trained in isolation, achieve
performance comparable to the original network [7]. To isolate the
subnetworks, Lottery Ticket Rewinding (LTR) iteratively trains a network,
prunes the smallest network parameters, [26], and rewinds the remaining
weights back to the original initialization. This and subsequent works [19,
35] demonstrate that greater than 97% sparsity can be achieved through
unstructured pruning on the classic CIFAR-10 benchmark of ResNet18. [22]. The
achievement of high sparsity exposed the bloated nature of large neural
networks. However, their parameter removal did not translate into a
proportionate improvement of computational efficiency [15]. Software
acceleration of the sparse matrix operations have achieved a respectable
fraction of the efficiency. [8, 29, 31]. Hardware-accelerated sparse matrix
operations are likely to enable future performance improvements but also do
not currently provide a speedup proportional to the sparsity achieved. [21].

To the aforementioned methods, structured pruning provides a simpler
inference-time speedup and the ability to minimize computation (i.e. FLOPs) as
an objective. The smallest element that can be pruned to accomplish this is
dependent on the architecture. For CNNs, the convolution channels are the most
frequent unit for structured pruning as it provides sufficient granularity and
search efficiency. [32]. Earlier structured pruning approaches were inspired
by unstructured pruning to identify the convolution channels to prune [30].
Then, the gradient [22] and continuous relaxation methods grew to prominence.
[12, 10]. Both approaches utilize gradient descent to select the pruned
channels. The objective of gradient pruning, in short, is to remove channels
with the smallest gradient adjustments. Continuous relaxation is our method of
choice – for which an additional relaxation parameter per convolutional
channel is required. The variable is used to continuously approximate the
necessity of the channel. Continuous relaxation algorithms also include a
method to progressively stiffen the approximation during optimization so the
trained and relaxed model is akin to the pruned model [9]. With these
approaches, structured pruning has been successfully applied to
classification, semantic segmentation, and depth estimation with an upwards of
80% FLOPs reduction while maintaining inference accuracy.

Structured pruning literature generally describe processes that require domain
experts to prepare models for pruning [10]. It may also require an iterative
train and prune cycle with a rigorous selection process for the pruned model.
[34]. We are developing a structured pruning algorithm that runs across a
range of CNNs and does not require domain expert guidance, thus making it
generalizable. We intend to integrate the pruning system within an automated
model deployment pipeline in a production setting.

[6] [27]

##  3 Method

We first discuss the mechanics of network augmentation and pruning as a graph
coloring problem. We then formalize the problem for CNNs and discuss how to
identify which channels to prune. Finally, we devise a search strategy to
minimize FLOPs while preserving accuracy.

Figure 2: CRISP method (a) Directed acyclic graph representation of a ResNet pruning network. The graph edges (colored arrows) and their surrounding convolutions represent individual subgraphs. Throughout the pruning process, each subgraph is designed to maintain channel consistency between convolutional outputs and inputs. Note that the green subgraph calibrates the pruned channels of every residual unit. (b) Training and relaxation. The CNN weights are trained while the relaxation parameters learn the importance of individual convolutional channels. In this example, the golden sub-graph does not relax, the blue and green sub-graphs become partially relaxed and the violet sub-graph relaxes completely. (c) Pruning. All convolutional channels with a relaxation parameter close to zero are pruned. The violet sub-graph is entirely pruned. (d) The final network after pruning and sub-graph collapse. Operator | Input | Output
---|---|---
Concatenation $\oplus$ | $T_{i,n}=(b,c_{n})\oplus d$ | $T_{o}=(b,\sum c_{n})\oplus d$
ReLu | $T_{i}=(b,c)\oplus d$ | $T_{o}=T_{i}$
Batch Norm | $T_{i}=(b,c)\oplus d$ | $T_{o}=T_{i}$
Sum $u+v$ |  $T_{i,u}=(b,c)\oplus d$ $T_{i,v}=(b,c)\oplus d$ | $T_{o}=(b,c)\oplus d$
Element-wise Product $u\cdot v$ |  $T_{i,u}=(b,c)\oplus d$ $T_{i,v}=(b,c)\oplus d$ | $T_{o}=(b,c)\oplus d$
Convolution $\circledast$ | $T_{i}=(b,c_{i})\oplus d_{i}$ | $T_{o}=(b,c_{o})\oplus d_{o}$
Fully Connected | $T_{i}=(b,c_{i})$ | $T_{o}=(b,c_{o})$
Table 1: Neural Network Operators with input and output dimension. $b$: batch
size, $c$: number of channels, $d$: array of image spatial dimensions, $k$:
channel mask vector, $m$: array of convolution kernel dimensions, $T$: tensor
size vector

###  3.1 Subgraph Identification and Augmentation

To generalize the network augmentation, training, and pruning procedures, we
consider the CNN to be a Directed Acyclic Graph (DAG) as illustrated in Figure
2 (a). Graph nodes are the network operators and edges are the tensor outputs
of one node and inputs go to the next node. Modeled on ResNet, each block in
Figure 2 (a) contains a 2D convolution, batch normalization, and ReLU
operator. Table 1 outlines the input and output tensor size for common neural
network operators. Most operators preserve the size of the input. For example,
a ReLU activation output is identical to its input, convolutional and fully
connected layers are the exception.

To ensure tensor shape consistency, we introduce sub-graphs to the DAG. Each
sub-graph is:  1. bound by convolutional layers and,  2. consists of operators
that must necessarily maintain equivalent input and output shapes throughout
the pruning process.  Figure 3 (a) showcase the nuances of a ResNet DAG. Its
subgraphs are represented by distinct colored edges and their associated
convolutional units. The residual sub-graph spans across ResNet blocks as the
element-wise addition of the identity function requires equivalent tensor
shapes. Each sub-graphs are candidates for augmentation, relaxation and
pruning.

An augmented subgraph $f_{a}(x,w,\sigma(s))$ is the product of the subgraph
$f_{s}(x,w)$ with the relaxation function $\sigma(s)$ as shown in Equation1

$f_{a}(x,w,\sigma(s))=f_{s}(x,w)\cdot\sigma(s)$ (1)

where the sigma function $\sigma(s)$ inputs the relaxation parameter
$s\in\mathbb{R}$ and outputs a value from 0 to 1. The relaxation function
enables a continuous optimizer to explore the discrete problem of enabling or
disabling each relaxed channel as part of model training. To prune a neural
network, the relaxation function is converted to a binary mask $m$ using a
threshold value $\tau$ and $\sigma(s)$:

$m=\begin{cases}1&\text{if }\sigma(s)>\tau\\\ 0&\text{else}\end{cases}$ (2)

The binary mask is applied to each operator within a sub-network retaining
only the candidate channels. After pruning, the unpruned relaxation function
outputs $\sigma(s)$ can be retained as a channel bias or better, merged into
adjacent operators reducing computation. If all channels are pruned then the
entire sub-graph is removed. In addition, incoming and outgoing operators are
removed from the graph until a non-zero path exists.

This procedure can be generalized to any deep learning architecture with at
least two consecutive convolutional layers. Sub-graphs that contain unknown
operators may be excluded from pruning.

###  3.2 Problem Formulation

We start with an accuracy objective that searches for convolution weights $w$
and relaxation weights $s$ to minimize the objective function
$\mathcal{L}(f(x,w,\sigma(s)))$. Second, we add in the structural pruning
objective, and scale it with an architecture weighting factor
$\mu\|\sigma(s)-t\|_{1}$, which approaches zero as the model structure
$\sigma(s)$ approaches the target structure $t$. The model structure is
expressed as two forms:

$\sigma_{p}(s)=\frac{1}{P}\cdot\sum_{i}p_{i}\cdot\cfrac{1}{1+e^{-as}}$ (3)
$\sigma_{q}(s)=\frac{1}{Q}\cdot\sum_{i}q_{i}\cdot\cfrac{1}{1+e^{-as}}$ (4)

Where $p_{i}$ is the operator parameters (see Supplementary Section), $P$ is
the total model parameters, $q_{i}$ the operator FLOPs, $Q$ being the total
model FLOPs, and $a$ as the logistic growth rate or steepness of curve.

The model structure is based on the logistic function. We formulate the
logistic function to approach $0$ for small $s$ and $1$ for large $s$
providing a bounded, differentiable range $(0,1)$ from the continuous domain
of $s\in\mathbb{R}$. $\sigma_{p}(s)$ weighs model parameters for comparison
with other structured and unstructured pruning algorithms’ sparsity whereas
$\sigma_{q}(s)$ weighs model FLOPs to improve computational efficiency.

Third, we add in the stiffening objective scaled by its weighting factor to
ensure that the relaxed model before and after pruning is similar. This is
achieved when the relaxation of the pruning weights is far from 0.

We observe smoother convergence and improved pruning performance when model
stiffening is an optimization objective. The stiffening function is:

$\delta(s)=\frac{1}{N}\sum_{i}\exp\left({\frac{-s^{2}}{2b^{2}}}\right)$ (5)

This is derived from the Gaussian probability density function:

$\exp\left({\frac{-s^{2}}{2b^{2}}}\right)\propto\mathcal{N}(s|0,b^{2})$ (6)

where  $N$ : Number of pruning weights $b$ : Gaussian Standard Deviation.

which defines a Gaussian function for each of the pruning weights.

Thus our final objective function for a given CNN $f$, model weights $w$ and
relaxation parameters $s$ becomes:

$\mathcal{T}(x,w,s)=\mathcal{L}(f(x,w,\sigma(s)))+\mu\|\sigma(s)-t\|_{1}+\lambda\cdot\delta(s)$
(7) $\min_{w,s}\sum_{x\in X}\mathcal{T}(x,w,s)$ (8)

such that,
$\mathcal{L}$ : accuracy loss,
$\mathcal{T}$ : total loss,
$f$ : convolutional neural network,
$X$ : set of input tensors,
$V$ : set of ground truth label tensors,
$w$ : network weights,
$s$ : pruning weights,
$\sigma$ : architecture minimization function,
$t$ : target architecture,
$\mu$ : architecture weighting factor,
$\|\cdot\|_{1}$ : L1 Norm,
$\lambda$ : stiffening weighting factor,
$\delta$ : stiffening function

Since our objective is to minimize model size without reducing model accuracy,
$\mu$ and $\lambda$ are chosen to be close to the minimum value of the
objective function. This results in an structured pruning without reducing
model accuracy.

A high $\lambda$ at initialization inhibits sparsity because it enforces $s$
to stay on the same side as the critical point of our Gaussian stiffening
function, $\delta$. However, waiting a few iterations in training allows the
initial search to begin, and increasing $\lambda$ later induces “confidence”
in our determined $s$-values as it pushes to positive or negative infinity. In
layman’s terms, we do not want the search to be confident of the initialized
$s$-values. Increasing $\lambda$ later results in a faster convergence of $s$.

###  3.3 Search

Algorithm 1 formulates a reliable and efficient algorithm to search for the
minimum FLOPs that preserves model accuracy.

Algorithm 1 Continuous relaxation in structured pruning

Training set $X$ and label set $V$

$f(x,w,\sigma(s))$ $\triangleright$ network with subnetworks

$w=w_{0}$ $\triangleright$ initialize/transfer network weights

$s=s_{0}$ $\triangleright$ initialize/transfer pruning weights

$W$ $\triangleright$ workflow definition

$j=j_{max}$ $\triangleright$ workflow steps

$i=i_{max}$ $\triangleright$ training epochs

while $j\geq 0$ do

if $W_{j,prune}$ then

for each $s\in\mathcal{S}$ do $\triangleright$ For each subgraph

$m=\sigma(s)>\tau_{j}$ $\triangleright$ Prune mask

$P(f_{s}(x_{s},w_{s},\sigma(s_{s})))$ $\triangleright$ Prune the subgraph

end for

end if

if $W_{j,train}$ then

while $i\geq 0$ do

$\min_{w,s}\sum_{x\in X}\mathcal{T}(x,w,s)$ $\triangleright$ Train

$i=i-1$

end while

end if

if $W_{j,test}$ then

$r=\sum_{i}\displaystyle{\|f(x_{i},w,\sigma(s)-v_{i}\|}$ $\triangleright$ Test
Accuracy

end if

$j=j-1$

end while

$f(x,w,\sigma(s))$ $\triangleright$ network with pruned sub-networks

$w$ $\triangleright$ final trained weights

$s$ $\triangleright$ final pruning weights

$r$ $\triangleright$ test results

Since continuous relaxation evaluates channels as fractionally present, it is
feasible to perform structured pruning in a single step [33, 9]. However,
Algorithm 1 implements a workflow iteration ”while $j\geq 0$ do”. This
addition to continuous relaxation is inspired by early pruning literature [26,
22]. Concerned about pruning weights early that become important only late in
training, we introduced the workflow dependent $\tau_{j}$ with an initially
small prune threshold (e.g. 0.01) that we ramp progressively towards 0.5.
Experimentally, we have not achieved superior single-step pruning results to
multi-step pruning following this approach. Both converge towards a similar
pruned structure with multi-step pruning having a smoother convergence. In
addition, early pruning speeds model training as the model size decreases. The
workflow definition variable $W$ allows us to train and test on the first pass
followed by prune, train, and test on subsequent passes.

##  4 Experiments

The premise of CRISP is to 1) train everyday neural networks into high
accuracy while minimizing computation and 2) demonstrate that this can be
achieved automatically in a model development pipeline. To establish this, we
first determine the highest sparsity attainable for various pruning algorithms
and benchmark CRISPs performance in comparison. We observe that all the models
remain under the theoretical limit specified by LTR. Then we investigate the
stability of the training convergence to determine the generalizability of the
algorithm. Our data shows a repeatedly robust convergence when optimizing for
standard cross-entropy loss, mean intersection-over-union (mIoU) and FLOPs.
Finally, the intent of CRISP is to deploy into real-world systems where class
objects vary by size and shape tremendously, especially due to data drift. To
verify the performance of pruned models on complex class objects, we carried
out a size-based analysis on the human class of the Cityscapes dataset.

We perform our experiments on standard datasets to ensure a fair comparison to
existing works so that future users can utilize the benchmarks to decide the
best methods for their use cases. We use PyTorch framework for experiments on
NVIDIA RTX 5000 and NVIDIA RTX 6000 for CIFAR10 datasets, and NVIDIA A6000 and
NVIDIA A100 for CityScapes[4] and ImageNet dataset. All the parameters,
models, and code are available at https://github.com/sherlj5352/crisp.

###  4.1 Accuracy vs Sparsity Comparison

First, we search for the highest sparsity attainable. With data provided by
structured and unstructured pruning algorithms alike, Figure 3 explores the
trade-off between network accuracy and sparsity of the ResNet-18 networks on
top-1 accuracy of the CIFAR-10 dataset. Although unstructured pruning achieves
a lower speedup at the same sparsity, it provides a theoretical upper-limit
for structured pruning sparsity. Random channel pruning (Random-S in the
figure) provides the lower bound where channels are randomly pruned followed
by iterative model retraining and testing. For all the pruning methods, we
start from the same baseline performance of 91.5% which is the off-the-shelf
performance of the ResNet-18 model on CIFAR-10. Our goal is to maintain model
accuracy (reduction of less than 1%) as sparsity increases.

Figure 3: Model accuracy vs sparsity with structured pruning. Performance
bounded by LTR unstructured pruning and random structured pruning.

We note that existing methods and CRISP exhibit an elbow-shape as the accuracy
plummets at high sparsity. CRISP has its elbow point at 96.9% sparsity with
the accuracy preserved at 90.25%, akin to the structured pruning state-of-the-
art. We define the preservation of accuracy to be within a 1% threshold of the
off-the-shelf model.

Early-CroP-S[22] (at 95% sparsity and 91% accuracy). At 94.6% sparsity, CRISP
performs with 90.87% accuracy.

Method | Accuracy | Sparsity | % FLOPS
---|---|---|---
PFEC [30] | 93.06% | - | 27.6%
LCCL [7] | 92.81% | - | 37.9%
AMC [15] | 91.90% | - | 50.0%
SFP [18] | 93.35% | - | 52.6%
FPGM [19] | 93.49% | - | 52.6%
TAS | 93.69% | - | 52.7%
PFS | 93.05% | 50 | 52.7%
HRank [16] | 93.17% | 42.4% | 50.0%
ABCPruner [17] | 93.23% | - | 54.1%
DAIS [9] | 93.53% | - | 70.9%

CIFAR-10 Resnet-56[6, 9]

###  4.2 Sparsity vs FLOPs

Whereas a sparsity objective treats all pruning weights equally, the FLOPs
objective favors CNN channels that process and propagate data of larger
resolutions. With the application of structured pruning on the U-NET [25]
image segmentation of CityScapes[3] we seek to answer the following questions:
(a) What is the trade-off in performance when optimizing for sparsity vs
FLOPs?  (b) What are the structural difference between models pruned for
sparsity vs for FLOPs?

Figure 4: Training monitoring test loss and pruning ratio through (a) no
pruning: 75.4% mIoU, Params 31.04e6, 218.9 GFLOPs, (b) sparsity objective:
75.4% mIoU, 91.0% Sparsity, 33.7 GFLOPs, and (c) FLOPs objective: 75.6% mIoU,
91.2% Sparsity, 15.5 GFLOPs

Figure 4 shows the training convergence of three training sequences: (a) no
pruning: train only to minimize standard cross-entropy loss, (b) CRISP
sparsity: a 5-step CRISP training using the sparsity objective, (c) CRISP
FLOPs: a 5-step CRISP training using the FLOPs objective. The scatterplot
shows the cross entropy loss of the validation dataset evaluated periodically
during training on left Y-axis. The black line associated with the right
Y-axis displays the sparsity in Figure 4 (b) and the FLOPs removal in Figure 4
(c). Each color represent one step of the iterative training and pruning
workflow.

As outlined in Section 3.3, the first CRISP training step (purple scatterplot
in Figure 4 (b) and (c)), seeks to minimize cross entropy, architecture and
stiffening losses. Every subsequent step prunes the model, then resumes its
training using the same loss objectives. The cross-entropy loss tends to jump
immediately after pruning especially at higher sparsity. However, the shift is
small and overall accuracy is maintained in the subsequent training steps.
This is shown in Figure 4 (b) and (c) where convergence is smooth.

For comparison, we trained three U-NET models that achieved 75% mIoU, of which
two were pruned to 91% sparsity. The pruned model in Figure 4 (b) was trained
for sparsity and has double the FLOPs of Figure 4 (c) that was trained to
minimize FLOPs. The FLOPs objective has a significant performance benefit.

The architecture reduction line plot in Figure 4 (b) and (c) illustrates our
strategy of stepping up $\mu$ and $\lambda$ in the second training step (see
Supplementary Material cityscapescrisp.yaml for training parameters).
Significantly, this reduction followed by pruning of CNN channels does not
affect the cross entropy loss that continues to slowly decrease.

Figure 5 illustrates the structure of the pruned U-Net models from Figure 4
(b) and (c) trained for sparsity (a) and FLOPs (b) after the final step of
CRISP. In Figure 4, from the left (input) to the right (output) is a column
for each of the U-Net subnetworks as defined in Section
LABEL:Network_Augmentation_and_Pruning. The original U-Net forms an isosceles
triangle. When pruned for both sparsity and FLOPs, the vast majority of the
U-Net is carved away. While the sparsity objective heavily reduced the peak
and its adjacent layers of the U-Net in Figure 5 (a), the FLOPs reduction
U-Net is well-pruned in layers toward the edge of the triangle in Figure 5
(b). This is intuitive because the U-Net peak has been downsized by 8x. There
is a greater reward for the FLOPs objective to remove channels from the outer
layers that process and propagate larger resolution data.

(a)

(b)

Figure 5:  The relaxation $\sigma(s)$ heatmaps of the U-Net models trained
with (a) Sparsity and (b) FLOPs objectives. The columns from left to right are
the U-Net subnetworks from model input to output, respectively. From top to
bottom are the architecture minimization function output of the subnetwork.
The color of each convolutional output is scaled by the relaxation function.
Blue indicates a relaxation value of 0 and is to be pruned, while red
represents 1 as a channel to be kept. The black background is negative space.
See the Supplementary Section for a larger figure.

Figure 5 indicates a clear structural different between pruning for Sparsity
and FLOPs although they share a common overall pattern. The pattern of a
compressed, rather than symmetric decoder is found in manually-optimized
networks similar to the DeeplabV3 architecture [2].

###  4.3 IoU vs Object Instance Size

Figure 6: IoU vs Object Instance Size. (a) A comparison of IoU vs sizes of the
‘human’ class instances by pixel. Object sizes are binned by rounding to the
closest log base 10 integer. Error bars represent the 1.5*IQR (interquartile
range) on either side of the mean. (b) Performance of Pruned and Unpruned
(standard) U-Net performance as the instance size changes. We observe little
to no difference for the qualitative performance between the models. Figure 7:
Comparision of ground truth, unpruned network (standard U-Net) and networks
pruned to different degrees

Finally, we analyze the effect of pruning on the segmentation of objects with
varying size. Effectively, we ask, “does the segmentation of pruned models
change when object sizes change?”. We leverage the ‘human’ class of CityScapes
with instances that vary greatly in shape and size, and train one standard
U-Net and two pruned U-Nets that converge to similar IoUs ( 0.74). We present
the results of all ‘human’ instances in the validation and test sets. Figure 6
(a) shows the performance of an unpruned U-Net model, and two models that are
pruned to 83.16% (called Pruned83) and 91.92% (called Pruned92) where these
percentages represent the FLOPs removed. We note that all the pruned models
maintain performance on all sized objects. A visualization of the effect of
pruning on the models’ segmentation output are found in 6 (b) and Figure 7.
Figure 6 (b) demonstrates variable performances by the Pruned92 and Unpruned
models and Figure 7 show the projected segmentation on one zoomed-in example
instance. As the pruning progresses, we observe slight changes in the mask
output. However, the objects are consistently segmented out.

##  5 Conclusion

Whereas large neural networks enable us to uncover increasingly better
solutions to complex computer vision problems, a smaller subnetwork within can
achieve a similar accuracy. Structured pruning provides a direct increase to
computational efficiency within a constrained search space.

We attained a 96.9% sparsity with a minimal ($<~{}1\%$) loss in accuracy with
CRISP, on the same ResNet-18 network and CIFAR-10 image classification, an
improvement over the current structured state-of-the-art Early-CroP-S
algorithm. Sparsity, however, does not represent computational efficiency.
Reformulating our objective for FLOPs, we are able to achieve a 93% FLOPs
reduction for CIFAR-10 image classification and CityScapes image segmentation
thereby demonstrating CRISPs’ extension to more complex computer vision
problems. We believe that progressive pruning is beneficial to deploying large
models in real-world systems where objects of different sizes show up at test
time. We validate performance across objects of different sizes of an
important class category and show that the performance does not vary with
object size both quantitatively and qualitatively. On ImageNet we estimate 92%
sparsity and 93% FLOPs reduction with 77% accuracy, on CityScapes we achieve
75.6% mIoU, 91.2% sparsity with 92.9% FLOPs reduction.

We hope to shine a light on structured pruning through our efforts. In
addition to the direct impact on model efficiency, we laid out a general
approach to identify, relax, and prune sub-graphs applicable to a wide variety
of neural networks used in computer vision. By combining model accuracy,
pruning, and model stiffening into continuous relaxation and optimization
regularization we only have one process to perform, which can be integrated
into a general model training pipeline. This process has stable convergence to
the target maximum sparsity without significant loss of accuracy. We believe
this is a necessary foundation to provide structured pruning as an automated
step of a production model optimization pipeline. Our future work includes the
automation of CRISP within a CI/CD pipeline, the inference time speedups of
CRISP models in a production setting, the pruning of other commonplace neural
network structures, and exploring the relationship between network pruning and
dataset covariant shift. We believe that this technique can be generally
applied to large-scale data center applications and other constrained edge
devices as well. Datacenter inference could benefit from reduced energy
consumption and server requirements while providing headroom for future
capabilities. As is the case with all algorithms, we suggest teams working to
incorporate CRISP and other optimizations to be socially considerate and aware
of potential target impacts.

## References

  * [1] Falcon 4i direct electron detector, 2022.
  * [2] Liang-Chieh Chen, George Papandreou, Florian Schroff, and Hartwig Adam.  Rethinking atrous convolution for semantic image segmentation.  arXiv preprint arXiv:1706.05587, 2017.
  * [3] Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bernt Schiele.  The cityscapes dataset for semantic urban scene understanding.  CoRR, abs/1604.01685, 2016.
  * [4] Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bernt Schiele.  The cityscapes dataset for semantic urban scene understanding.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3213–3223, 2016.
  * [5] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 248–255, 2009.
  * [6] Xuanyi Dong and Yi Yang.  Network pruning via transformable architecture search.  Advances in Neural Information Processing Systems, 32, 2019.
  * [7] Jonathan Frankle and Michael Carbin.  The lottery ticket hypothesis: Finding sparse, trainable neural networks.  2018\.
  * [8] Trevor Gale, Matei Zaharia, Cliff Young, and Erich Elsen.  Sparse gpu kernels for deep learning.  In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis, pages 1–14. IEEE, 2020.
  * [9] Yushuo Guan, Ning Liu, Pengyu Zhao, Zhengping Che, Kaigui Bian, Yanzhi Wang, and Jian Tang.  Dais: Automatic channel pruning via differentiable annealing indicator search.  IEEE Transactions on Neural Networks and Learning Systems, pages 1–12, 2022.
  * [10] Yi Guo, Huan Yuan, Jianchao Tan, Zhangyang Wang, Sen Yang, and Ji Liu.  Gdp: Stabilized neural network pruning via gates with differentiable polarization, 2021.
  * [11] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  CoRR, abs/1512.03385, 2015.
  * [12] Zih-Syuan Huang and Ching-pei Lee.  Training structured neural networks through manifold identification and variance reduction.  2021\.
  * [13] Noah James.  Gauging the state-of-the-art for foresight weight pruning on neural networks, 2022.
  * [14] Alex Krizhevsky.  Learning multiple layers of features from tiny images.  pages 32–33, 2009.
  * [15] Aditya Kusupati, Vivek Ramanujan, Raghav Somani, Mitchell Wortsman, Prateek Jain, Sham Kakade, and Ali Farhadi.  Soft threshold weight reparameterization for learnable sparsity.  In International Conference on Machine Learning, pages 5544–5555. PMLR, 2020.
  * [16] Mingbao Lin, Rongrong Ji, Yan Wang, Yichen Zhang, Baochang Zhang, Yonghong Tian, and Ling Shao.  Hrank: Filter pruning using high-rank feature map.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 1529–1538, 2020.
  * [17] Mingbao Lin, Rongrong Ji, Yuxin Zhang, Baochang Zhang, Yongjian Wu, and Yonghong Tian.  Channel pruning via automatic structure search.  arXiv preprint arXiv:2001.08565, 2020.
  * [18] Yuqiao Liu, Yanan Sun, Bing Xue, Mengjie Zhang, Gary G Yen, and Kay Chen Tan.  A survey on evolutionary neural architecture search.  IEEE transactions on neural networks and learning systems, 2021\.
  * [19] Xiaolong Ma, Minghai Qin, Fei Sun, Zejiang Hou, Kun Yuan, Yi Xu, Yanzhi Wang, Yen-Kuang Chen, Rong Jin, and Yuan Xie.  Effective model sparsification by scheduled grow-and-prune methods, 2021\.
  * [20] Michela Paganini and Jessica Forde.  On iterative neural network pruning, reinitialization, and the similarity of masks, 2020.
  * [21] Jeff Pool, Abhishek Sawarkar, and Jayi Rodge.  Accelerating inference with sparsity using the nvidia ampere architecture and nvidia tensorrt.  https://developer.nvidia.com/blog/accelerating-inference-with-sparsity-using-ampere-and-tensorrt/.  Accessed: 2022-10-27.
  * [22] John Rachwan, Daniel Zügner, Bertrand Charpentier, Simon Geisler, Morgane Ayle, and Stephan Günnemann.  Winning the lottery ahead of time: Efficient early network pruning, 2022\.
  * [23] William T. Redman, Maria Fonoberova, Ryan Mohr, Ioannis G. Kevrekidis, and Igor Mezic.  An operator theoretic view on pruning deep neural networks, 2021.
  * [24] Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-net: Convolutional networks for biomedical image segmentation.  CoRR, abs/1505.04597, 2015.
  * [25] Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-net: Convolutional networks for biomedical image segmentation.  CoRR, abs/1505.04597, 2015.
  * [26] Maying Shen, Pavlo Molchanov, Hongxu Yin, and Jose M. Alvarez.  When to prune? a policy towards early structural pruning, 2021.
  * [27] Rishabh Tiwari, Udbhav Bamba, Arnav Chavan, and Deepak K Gupta.  Chipnet: Budget-aware pruning with heaviside continuous approximations.  arXiv preprint arXiv:2102.07156, 2021.
  * [28] Stijn Verdenius, Maarten Stol, and Patrick Forré.  Pruning via iterative ranking of sensitivity statistics, 2020.
  * [29] Ziheng Wang.  Sparsert: Accelerating unstructured sparsity on gpus for deep learning inference.  CoRR, abs/2008.11849, 2020.
  * [30] Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li.  Learning structured sparsity in deep neural networks.  Advances in neural information processing systems, 29, 2016.
  * [31] Zhuliang Yao, Shijie Cao, Wencong Xiao, Chen Zhang, and Lanshun Nie.  Balanced sparsity for efficient DNN inference on GPU.  CoRR, abs/1811.00206, 2018.
  * [32] Xin Yuan, Pedro Savarese, and Michael Maire.  Growing efficient deep networks by structured continuous sparsification, 2020.
  * [33] Xin Yuan, Pedro Savarese, and Michael Maire.  Growing efficient deep networks by structured continuous sparsification.  arXiv preprint arXiv:2007.15353, 2020.
  * [34] Yulun Zhang, Huan Wang, Can Qin, and Yun Fu.  Learning efficient image super-resolution networks via structure-regularized pruning.  In International Conference on Learning Representations, 2021.
  * [35] Shaochen Zhong, Guanqun Zhang, Ningjia Huang, and Shuai Xu.  Revisit kernel pruning with lottery regulated grouped convolutions.  In International Conference on Learning Representations, 2021.

## Supplementary Material

The supplementary material section contains:  1. a channel-level visualization
of structured pruning (Figure 8),  2. the equations describing the parameter
and FLOPs computation that is shown in the problem formulation,  3. a full-
page visualization that compare the architectures of unpruned, sparsity
objective pruning, and FLOPs objective pruning (Figure 8).  4. a table of
workflows pushed to Git which can be used to replicate the experiments within
the paper

Figure 8: Channel-Level CRISP Diagrams. (a) The CRISP augmentation of an
individual convolutional channel. The relaxation parameter is squeezed by a
sigmoid function and applied to the convolutional channel’s output via
element-wise multiplication. (b) A convolutional unit is represented as a
stack of 64 convolutional channels. Fifty-six channels become fully relaxed
during the training and relaxation step and 8 channels remain after the
pruning step.

Equations 3 and 4 employ Table 3 for compute model structure $\sigma(s)$ based
on the network operator. These equations were derived from the ptflops and
fvcore python libraries.

Operator | Param | FLOPs
---|---|---
ReLu | $p=0$ |  $q=\displaystyle{\prod T_{i}}$ where $\displaystyle{T_{i}[c]=\sum\sigma(s)}$
Batch Norm | $p=2\cdot\sum\sigma(s)$ |  $q=\displaystyle{\prod T_{i}}$ where $\displaystyle{T_{i}[c]=\sum\sigma(s)}$
Sum $\sum$ | $p=0$ |  $q=\displaystyle{\prod T_{i}}$ where $\displaystyle{T_{i}[c]=\sum\sigma(s)}$
Product $v\cdot w$ | $p=0$ |  $q=\displaystyle{\prod T_{i}}$ where $\displaystyle{T_{i}[c]=\sum\sigma(s)}$
Concatenation $\oplus$ | $p=0$ | $q=0$
Convolution $\circledast$ | $p={\displaystyle c_{i}\cdot\sigma_{i}(s)\cdot c_{o}\cdot\sigma_{o}(s)\cdot\prod m}$ | $q=c_{o}\cdot\sigma_{o}(s)\cdot\prod d_{o}\cdot(\prod m\cdot c_{i}\cdot\sigma_{i}(s)+1)$
Fully Connected |  |
Table 2: Selected neural network operators with their trainable parameters,
and FLOPs. When no relaxation function is being applied to an operator,
$\sum\sigma(s)$ is replaced by the channel length.

(a) sparsity objective: 75.4% mIoU, 91.0% Sparsity, 33.7 GFLOPs

(b) FLOPs objective: 75.6% mIoU, 91.2% Sparsity, 15.5 GFLOPs

Figure 9: Larger version of Figure 5. The final results of the multi-step pruning of U-Net. The gray space indicates the unpruned U-Net channels. $\sigma(s)$ is the pruning parameter, where channels are pruned when the channel weight is less than the pruning parameter. The pruning parameter lies strictly within (0,1). For multi-step pruning, we generally start with a minimal threshold $(~{}0.01)$ to avoid pruning channels that could be important later for high accuracy. Blue indicates the lowest values of $\sigma(s)$ and the red indicates the highest value of $\sigma(s)$ when these channels have been pruned. (a) Sparsity objective and (b) FLOPS objective of pruned U-Nets that achieve a similar mIoU.  Test | Workflow | Description
---|---|---
Accuracy vs Sparsity | resnet18cifar10-dht9m | Pareto search
Accuracy vs Sparsity | resnet18cifar10-wwjrb | Pareto search
Accuracy vs Sparsity | resnet18cifar10-8cp4w | Pareto search
Accuracy vs Sparsity | resnet18cifar10-l7892 | Pareto search
Sparsity vs FLOPs | cityscapes | Unpruned model
Sparsity vs FLOPs | cityscapescrisp | Sparsity or FLOPs objective models
IoU vs Object Instance Size | cityscapes2_control | Unpruned model
IoU vs Object Instance Size | cityscapes2_prune | Pruned83 and Pruned92 models
Table 3: Experiment Argo Workflows