# State-driven Implicit Modeling for Sparsity and Robustness in Neural
Networks

Alicia Y. Tsai1, Juliette Decugis2, Laurent El Ghaoui1, Alper Atamtürk3
Corresponding author

###### Abstract

Implicit models are a general class of learning models that forgo the
hierarchical layer structure typical in neural networks and instead define the
internal states based on an “equilibrium” equation, offering competitive
performance and reduced memory consumption. However, training such models
usually relies on expensive implicit differentiation for backward propagation.
In this work, we present a new approach to training implicit models, called
State-driven Implicit Modeling (SIM), where we constrain the internal states
and outputs to match that of a baseline model, circumventing costly backward
computations. The training problem becomes convex by construction and can be
solved in a parallel fashion, thanks to its decomposable structure. We
demonstrate how the SIM approach can be applied to significantly improve
sparsity (parameter reduction) and robustness of baseline models trained on
FashionMNIST and CIFAR-100 datasets.

## Introduction

Conventional neural networks are built upon a hierarchical architecture, where
input information is processed through several recursive layers (Goodfellow,
Bengio, and Courville 2016). Canonical examples of this include standard feed-
forward networks or convolutional networks used to perform image
classification (Krizhevsky, Sutskever, and Hinton 2012; Simonyan and Zisserman
2015). Recent work has proposed a more general perspective, where the internal
states are implicitly defined through an “equilibrium” equation (Bai, Kolter,
and Koltun 2019; Chen et al. 2018; El Ghaoui et al. 2021), allowing for loops
in the model’s computational graph. As illustrated in Bai, Koltun, and Kolter;
Gu et al., implicitly-defined models are able to match state-of-the-art
performance of explicitly-defined models on several tasks. In fact, the
implicit framework is a more general model with greater capacity to possibly
model novel architectures and prediction rules for deep learning that are not
necessarily tied to any notion of “layers.”

The forward pass of an implicit model usually relies on solving an algebraic
equation using methods such as fixed-point equations (El Ghaoui et al. 2021),
ODE solvers (Dupont, Doucet, and Teh 2019), or root-finding methods (Bai,
Koltun, and Kolter 2020). The backward pass involves differentiating through
the implicit equation, which usually relies on expensive black-box solvers,
projected gradient descent or approximate gradients (Geng et al. 2021). The
costly backward computation remains a challenge in training and evaluation of
implicit models. In this work, we develop a novel method to circumvent
computing the backward pass. We start from a baseline model (e.g., a pre-
trained layered neural network) and constrain the states and outputs of the
implicit model to match those baseline states. The SIM training problem is
strictly feasible and convex by construction, and thus can be solved
efficiently, bypassing the expensive implicit differentiation. Additionally,
the method is very scalable: it can be implemented in parallel provided that
the objective is decomposable across its internal state, which is usually the
case.

We find that with our approach, the number of training samples required to
efficiently and effectively train an implicit model is significantly reduced.
For example, using 20%-30% of total training data is enough to train an
implicit model on CIFAR-100 dataset. Our method can also be combined with
additional objectives such as sparsity (parameter reduction) or improving
robustness, making it a versatile training scheme.

Our main contributions are summarized as follows. First, we introduce the
general State-driven Implicit Modeling (SIM) training scheme to efficiently
learn an implicit model by matching the internal state and outputs of a
baseline model. In addition, we present simple ways to obtain the internal
state and outputs from either a standard (layered) neural network or an
implicit model. Third, we demonstrate how to apply SIM for parameter reduction
and robustness. Our experimental results display a competitive performance of
our method on both FashionMNIST and CIFAR-100 datasets. Finally, we study the
visualization of the trained models and observe interesting properties of
implicit models, motivating future directions of research.

## Related Work

#### Implicit Models.

Recent works (Bai, Kolter, and Koltun 2019; Chen et al. 2018; El Ghaoui et al.
2021; Winston and Kolter 2020) have proposed an emerging “implicitly-defined”
structure in deep learning, where the intermediate hidden states are defined
via a “equilibrium” (fixed-point) equation, and the outputs are determined
only implicitly by the equilibrium solution of such underlying equilibrium
equation. Researchers have developed different classes of implicit models and
demonstrated their potential in graph neural networks (Gu et al. 2020),
differential equation models (Chen et al. 2018), physical control (de Avila
Belbute-Peres et al. 2018), and many others (Amos et al. 2018). Ta et al.
(2022) show that these implicitly-defined models can be successfully pruned,
reducing their training and inference complexity.

#### Sparsity.

The growing size and computational cost of deep learning have motivated the
property of sparsity, in order to reduce the size of networks by selectively
zeroing out unnecessary model parameters (pruning). This leads to a more
efficient model that operates in the same high-dimensional feature space, but
with a reduced representational complexity. One of the popular approaches is
to remove parameters with the smallest magnitude, a technique called magnitude
pruning (Han et al. 2015; Han, Mao, and Dally 2016; Karnin 1990; Zhu and Gupta
2018; Molchanov et al. 2017). Magnitude pruning eliminates weights based on a
learned magnitude or criterion of parameters with an a priori threshold (Yeom
et al. 2019), which requires trial-and-error or heuristics. Others have
considered a more principled way of determining the importance of parameters,
including structured pruning (Sui et al. 2021; Chen et al. 2021) and
directional pruning (Chao et al. 2020). Recent works have also explored the
problem using optimization techniques, such as convex pruning (Aghasi, Abdi,
and Romberg 2020) or the perspective reformulation technique in (Frangioni and
Gentile 2006; Atamtürk and Gómez 2020).

#### Robustness.

Starting with Szegedy et al., a large number of works have shown that state-
of-the-art deep neural networks (DNNs) are vulnerable to adversarial samples
(Goodfellow, Shlens, and Szegedy 2015; Kurakin, Goodfellow, and Bengio 2017;
Papernot et al. 2016a). The vulnerability of DNNs has motivated the study of
building models that are robust to such perturbations (Madry et al. 2018;
Papernot et al. 2016b; Raghunathan, Steinhardt, and Liang 2018; Gowal et al.
2018). Defense strategies against adversarial examples have primarily focused
on training with adversarial examples (Tramèr et al. 2017; Madry et al. 2018)
or with a carefully designed penalty loss (Qin et al. 2019; Dhillon et al.
2018).

## Preliminaries

#### Notations.

Throughout the paper, we use $n,m,p,q$ to denote the number of internal
states, the number of input samples, the dimension of input vectors, and the
dimension of output vectors, respectively. For a matrix $V$, $|V|$ denotes its
absolute value (i.e. $|V|_{ij}=|V_{ij}|$); $\left\lVert V\right\rVert_{0}$ is
its cardinality, i.e., the number of non-zero entries of $V$; $\left\lVert
V\right\rVert_{\infty}$ is the max-row-sum matrix operator norm; $\left\lVert
V\right\rVert_{F}$ is the Frobenious norm. Finally, $\lambda_{\text{pf}}(M)$
denotes the Perron-Frobenius (PF) eigenvalue of a square non-negative matrix
$M$ (Berman and Plemmons 1994).

######  Assumption 1 (component-wise non-expansive).

A function $\phi$ is component-wise non-expansive (CONE) if

$\forall\;u,v\in{\mathbb{R}}^{n}~{}:~{}|\phi(u)-\phi(v)|\leq|u-v|,$

with inequality and absolute value taken component-wise.

We are given a data set with input matrix $U\in{\mathbb{R}}^{p\times m}$ and
output matrix $Y\in{\mathbb{R}}^{q\times m}$, where each column represents an
input or output vector. An implicit model consists of an equilibrium equation
in a “state matrix” $X\in{\mathbb{R}}^{n\times m}$ and a prediction equation:

$\displaystyle X=\phi(AX+BU)\quad\mbox{(equilibrium equation)}$ (1a)
$\displaystyle\hat{Y}(U)=CX+DU\quad\mbox{(prediction equation)}$ (1b)

where $\phi:{\mathbb{R}}^{n\times m}\rightarrow{\mathbb{R}}^{n\times m}$ is a
nonlinear activation that is strictly increasing and satisfies Assumption (1),
such as ReLU, tanh, or sigmoid. While the above model seems very specific, it
covers as special cases most known architectures arising in deep learning.
Matrices $A\in{\mathbb{R}}^{n\times n}$, $B\in{\mathbb{R}}^{n\times p}$,
$C\in{\mathbb{R}}^{q\times n}$ and $D\in{\mathbb{R}}^{q\times p}$ are model
parameters. In equation (1a), the input feature matrix
$U\in{\mathbb{R}}^{p\times m}$ is passed through a linear transformation by
weight matrix $B$ and the internal state matrix $X\in{\mathbb{R}}^{n\times m}$
is obtained as the fixed-point solution to equation (1a). The output
prediction $\hat{Y}$ is then obtained by feeding the state $X$ through the
prediction equation (1b). The structure is illustrated in Figure 1, where the
“pre-activation” and “post-activation” state matrices $Z,X$ are shown; in
those matrices, each column corresponds to a single data point.

pt$\scaleto{\begin{bmatrix}A&B\\\
C&D\end{bmatrix}}{65pt}$$\scaleto{\phi}{20pt}$$\scaleto{U}{15pt}$$\scaleto{\hat{Y}=CX+DU}{20pt}$$\scaleto{X=\phi(Z)}{20pt}$$\scaleto{Z=AX+BU}{15pt}$

Figure 1: A block-diagram view of an implicit model, where $Z$ is the pre-
activation state “before” passing through the activation function $\phi$ and
$X$ is the post-activation state “after” passing through $\phi$.

The forward pass of an implicit model relies on the fixed-point solution of
the underlying equilibrium equation, while a backward pass requires one to
differentiate this equation with respect to the model parameters $(A,B,C,D)$.
The solution to the equilibrium equation (1a) does not necessarily exists nor
be unique. We say that an equilibrium equation with activation map $\phi$ is
well-posed if the following well-posedness condition is satisfied (El Ghaoui
et al. 2021).

######  Definition 1 (well-posedness).

The $n\times n$ matrix $A$ is said to be well-posed for $\phi$ if, for any
$b\in{\mathbb{R}}^{n}$, the solution $x\in{\mathbb{R}}^{n}$ of the following
equation

$x=\phi(Ax+b)$ (2)

exists and is unique.

#### Scaling the network.

Consider a standard layer-based neural network
$\mathcal{N}:{\mathbb{R}}\times{\mathbb{R}}\rightarrow{\mathbb{R}}\times{\mathbb{R}}$
with activation $\phi$ that satisfies Assumption (1) and maps input feature
matrix $U\in{\mathbb{R}}^{p\times m}$ to outputs $Y=\mathcal{N}(U)$ via hidden
layers. As shown in El Ghaoui et al., for such networks, there exists an
equivalent implicit model,
$(A_{\mathcal{N}},B_{\mathcal{N}},C_{\mathcal{N}},D_{\mathcal{N}},\phi)$ as in
(1). Without loss of generality, we may re-scale the original weight matrices
of $\mathcal{N}$ to obtain a strongly well-posed implicit model,
$(A^{\prime}_{\mathcal{N}},B^{\prime}_{\mathcal{N}},C^{\prime}_{\mathcal{N}},D^{\prime}_{\mathcal{N}},\phi)$,
by Theorem (2), in the sense that $\left\lVert
A^{\prime}_{\mathcal{N}}\right\rVert_{\infty}<1$. This result also allows us
to consider the convex constraint $\left\lVert A\right\rVert_{\infty}<1$ as a
sufficient condition as opposed to the non-convex PF sufficient condition, in
light of the bound $\lambda_{\text{pf}}(A)\leq\left\lVert
A\right\rVert_{\infty}$.

######  Theorem 1 (PF sufficient condition for well-posedness).

Assume that $\phi$ satisfies Assumption (1). Then, $A$ is well-posed for any
such $\phi$ if $\lambda_{\text{pf}}(|A|)<1$. Moreover, the solution $x$ of
equation (1a) can be computed via the fixed point iterations
$x\rightarrow\phi(Ax+b)$, with initial condition $x=0$.

######  Theorem 2 (Rescaled implicit model).

Assume that $\phi$ is CONE and positively homogeneous, i.e., $\phi(\alpha
x)=\alpha\phi(x)$ for any $\alpha\geq 0$ and $x$. For a neural network
$\mathcal{N}$ with its equivalent implicit form
$(A_{\mathcal{N}},B_{\mathcal{N}},C_{\mathcal{N}},D_{\mathcal{N}},\phi)$,
where $A_{\mathcal{N}}$ satisfies PF sufficient condition for well-posedness
of Theorem (1), there exists a linearly-rescaled equivalent implicit model
$(A^{\prime}_{\mathcal{N}},B^{\prime}_{\mathcal{N}},C^{\prime}_{\mathcal{N}},D^{\prime}_{\mathcal{N}},\phi)$
with $\left\lVert A^{\prime}_{\mathcal{N}}\right\rVert_{\infty}<1$ that gives
the same output $\hat{Y}$ as the original $\mathcal{N}$ for any input $U$.

The proofs of Theorem (1) and (2) are given in the appendices.

## State-driven Implicit Modeling

The State-driven Implicit Modeling (SIM) framework trains an implicit model
with a constraint: it should match both the state $X$ and outputs $\hat{Y}$ of
another “baseline” (implicit or layered) model, when the same inputs $U$ are
applied. For a given baseline model, the state matrix $X$ can be obtained by
running a set of fixed-point iterations (if the baseline is implicit), or a
simple forward pass (if the baseline is a standard layered network). In both
cases, we can extract the pre-activation state matrix $Z$, such that the post-
activation state matrix satisfies $X=\phi(Z)$. Each column of matrices $Z$ and
$X$ corresponds to a single data point; when the baseline is a layered
network, these matrices are constructed by stacking all the intermediate
layers into a long column vector, where the first intermediate layer is at the
bottom and the last intermediate layer is on top.

We give a simple example of how to construct $X,Z$ from a 3-layer fully-
connected network of the form:

$\hat{y}(u)=W_{2}x_{2},\;x_{2}=\phi(W_{1}x_{1})\;x_{1}=\phi(W_{0}x_{0}),\;x_{0}=u,$

where $u$ is a single vector input. For notational simplicity, we exclude the
bias terms, which can be easily accounted for by considering the vector
$(u,1)$ instead of $u$. Each column of $Z$ and $X$ corresponds to the state
from a single input. The column $z$ is formed by stacking all the intermediate
layers before passing through $\phi$ and the column $x$ is formed by stacking
all the intermediate layers after passing through $\phi$:

$z=\begin{pmatrix}W_{1}x_{1}\\\
W_{0}x_{0}\end{pmatrix},\;\;x=\phi(z)=\begin{pmatrix}x_{2}\\\
x_{1}\end{pmatrix}.$

In this example, we can easily verify that its equivalent implicit from is as
follows:

$\left(\begin{array}[]{c|c}A&B\\\ \hline\cr
C&D\end{array}\right)=\left(\begin{array}[]{cc|c}0&W_{1}&0\\\ 0&0&W_{0}\\\
\hline\cr W_{2}&0&0\end{array}\right).$

For a more complicated network, finding an equivalent implicit form may be a
non-trivial task. The SIM framework allows us to consider any baseline deep
neural networks without ever having to address this challenge: we simply need
to extract the pre- and post-activation state matrices.

With matrices $X,Z$ fixed, we now consider the training problem, where the
model parameters are encapsulated in a partitioned matrix
$M\in{\mathbb{R}}^{(n+q)\times(n+p)}$ and we define $\tilde{Y},\tilde{U}$ as
follows:

$M:=\begin{pmatrix}A&B\\\ C&D\end{pmatrix},\;\tilde{Y}:=\begin{pmatrix}Z\\\
\hat{Y}\end{pmatrix},\;\tilde{U}:=\begin{pmatrix}X\\\ U\end{pmatrix}$

The condition $\tilde{Y}=M\tilde{U}$ characterizes the implicit models that
match both the state and outputs of the baseline model. We then solve a convex
problem to find another well-posed model, with a desired task in mind, with
the matching condition $\tilde{Y}=M\tilde{U}$:

$\displaystyle\min_{M}\;\;$ $\displaystyle f(M)$ (3a) s.t. $\displaystyle
Z=AX+BU,$ (3b) $\displaystyle\hat{Y}=CX+DU,$ (3c)
$\displaystyle\|A\|_{\infty}\leq\kappa.$ (3d)

Here, $f$ is an user-designed objective function chosen for a desired task,
such as encouraging sparsity, and $\kappa\in(0,1)$ is a hyper-parameter. Note
that for a given input matrix $U\in{\mathbb{R}}^{p\times m}$, we have
generically $U^{T}U\succ 0$, when $m>p$. The matrix equation
$\tilde{Y}=M\tilde{U}$ involves $(n+p)m$ scalar equations in $(n+p)(n+q)$
variables, it is thus natural to require that $n>m-p$, which is generally true
for over-parameterized models.

The state-matching constraint (3b) ensures that the implicit model determined
by the weight matrices $A,B,C,D$ achieves the same representational power as
the baseline model $\mathcal{N}$ by having the same internal state. The
outputs-matching constraint (3c) ensures that the model achieves the same
predictive performance by obtaining the same predictions as $\mathcal{N}$.
Finally, the well-posedness constraint (3d) is added to ensure that the well-
posedness condition is satisfied.

For a given baseline layered neural network model, we can always rescale the
state matrices $X,Z$ by Theorem (2), so that the problem is strictly feasible.
Denoting by $W_{\ell}$ the network’s matrix corresponding to layer $\ell$, we
divide it by the largest max-row-sum norm of the weights among all the layers:

$W^{\prime}_{\ell}=\frac{W_{\ell}}{\gamma\cdot\max_{\ell}\left\lVert
W_{\ell}\right\rVert_{\infty}},\;\ell\in[L],\;\gamma>1,$

where $L$ is the total number of layers and $\gamma$ is a scaling factor. The
corresponding state matrices $X,Z$ will then be appropriately rescaled after
running a single forward pass.

### State-driven Training Problem

SIM is a general training scheme and various kinds of tasks can be achieved by
including an appropriately designed objective and setup. We show two such
possibilities: one aims for improved sparsity and the other for improved
robustness.

#### Training for sparsity.

To learn a sparse implicit model, we consider the SIM training problem where
we sparsify the weight matrix $M$ by minimizing its cardinality, while
satisfying $\tilde{Y}=M\tilde{U}$:

$\displaystyle\min_{M}\quad\left\lVert
M\right\rVert_{0}~{}:~{}\mbox{(\ref{eq:sim-state-constraint})-(\ref{eq:sim-wp-
constraint})}.$ (4)

In general, solving the optimization problem (4) directly is not
computationally efficient, and therefore a common alternative is to consider a
convex relaxation. We consider the perspective relaxation that is a
significantly stronger approximation (Frangioni and Gentile 2006; Atamtürk and
Gómez 2019; Atamturk, Gomez, and Han 2021) than the popular $\ell_{1}$-norm
relaxation, and has recently been used for pruning neural networks (Cacciola
et al. 2022). This leads to the following training problem:

$\min_{M,t}\;\;\sum_{ij}\frac{M^{2}_{ij}}{t_{ij}}+\sum_{ij}t_{ij}~{}:~{}\mbox{(\ref{eq:sim-
state-constraint})-(\ref{eq:sim-wp-constraint})},\;t_{ij}\in[0,1].$ (5)

The perspective terms $\frac{M^{2}_{ij}}{t_{ij}}$ are typically replaced with
auxiliary variables $s_{ij}$ along with rotated cone constraints
$M^{2}_{ij}\leq s_{ij}\cdot t_{ij}$ (Aktürk, Atamtürk, and Gürel 2009),
leading to a second-order cone problem:

$\displaystyle\min_{M,t,s}\;\;\alpha\sum_{ij}s_{ij}~{}:~{}$
$\displaystyle\mbox{(\ref{eq:sim-state-constraint})-(\ref{eq:sim-wp-
constraint})},\;t_{ij}\in[0,1],$ (6a) $\displaystyle M^{2}_{ij}\leq
s_{ij}\cdot t_{ij},\;s_{ij}\geq 0,$ (6b)

where $\alpha$ is a hyper-parameter that controls the degree of sparsity.
Problem (6) can be easily solved with conic quadratic solvers.

#### Training for robustness.

To promote robustness, we consider regularizing the $\ell_{1}$-norm of the
weight matrix $M$. The use of norm-based regularization (e.g. $\ell_{2}$ or
$\ell_{1}$-norm) for training neural networks has been widely adopted. It has
also been shown that there exists an intrinsic relationship between
regularizing the $\ell_{1}$-norm of the weight matrices and their robustness
against $\ell_{\infty}$-bounded perturbations (Guo et al. 2018; Alizadeh et
al. 2020). The set of $\ell_{\infty}$-bounded perturbations yields the worst-
case scenario since it includes all other $\ell_{p}$-bounded perturbations.
Controlling the $\ell_{1}$-norm, therefore, guarantees robustness to
$\ell_{\infty}$-perturbations and thereby to all other $\ell_{p}$-bounded
perturbations. Note that we are minimizing the vectorized $\ell_{1}$-norm of
$M$, i.e. $\sum_{ij}|M_{ij}|$, instead of the matrix operator norm. The
resulting training problem:

$\displaystyle\min_{M}\quad\sum_{ij}|M_{ij}|~{}:~{}\mbox{(\ref{eq:sim-state-
constraint})-(\ref{eq:sim-wp-constraint})},$ (7)

is convex and can be solved efficiently by a standard optimization solver.

#### Relax state and outputs matching.

We do not have to insist on matching the state and outputs exactly, which
allows us to relax the state-matching and output-matching constraints (3b) and
(3c) by introducing penalty terms into the objective function:

$\displaystyle\min_{M}\quad f(M)+\lambda_{1}\left\lVert
Z-(AX+BU)\right\rVert^{2}_{F}$ (8a)
$\displaystyle+\lambda_{2}\left\lVert\hat{Y}-(CX+DU)\right\rVert^{2}_{F}~{}:~{}\mbox{(\ref{eq:sim-
wp-constraint})},\;\mathcal{C},$ (8b)

where $f$ and $\mathcal{C}$ are user-defined objective function and set of
constraints on model parameters, respectively, and $\lambda_{1}$ and
$\lambda_{2}$ are hyper-parameters that control the degree of state- and
output-matching.

#### Parallel training.

The SIM training problem can be decomposed into a series of parallel, smaller
problems, each involving a single row, or a block of rows, if $f$ is
decomposable. This is usually the case, including in the sparsity and
robustness examples seen before. For a single row $(a^{T},b^{T})$ of $(A,B)$,
and with $z^{T}$ the corresponding row in $Z$, the problem takes the form of a
basis pursuit problem:

$\mbox{Find vectors
}a,b~{}:~{}z=\begin{pmatrix}X^{T}&U^{T}\end{pmatrix}\begin{pmatrix}a\\\
b\end{pmatrix},\|a\|_{1}\leq\kappa.$ (9)

where $\left\lVert a\right\rVert_{1}\leq\kappa$ is the well-posedness
condition since $\left\lVert A\right\rVert_{\infty}$ is separable in terms of
rows. The problem of finding $C,D$ is independent of that relative to $A,B$
and takes the same form as problem (9) without the well-posedness condition:

$\mbox{Find vectors
}c,d~{}:~{}\hat{y}=\begin{pmatrix}X^{T}&U^{T}\end{pmatrix}\begin{pmatrix}c\\\
d\end{pmatrix}.$ (10)

The decomposibility is applicable to the perspective relaxation and the
$\ell_{1}$-norm objective that we consider, with appropriate constraint set
$\mathcal{C}$. The parallel SIM training algorithm is summarize in Algorithm
1. More implementation details on parallel training can be found in the
appendices.

Algorithm 1 Parallel State-driven Implicit Modeling (SIM)

Input: Input feature matrix $U$; A standard neural network or an implicit
model
$\mathcal{N}:{\mathbb{R}}\times{\mathbb{R}}\rightarrow{\mathbb{R}}\times{\mathbb{R}}$;
Well-posedness hyper-parameter $\kappa$.
Design choices: Convex minimization objective $f$; Convex constraint set
$\mathcal{C}$; Hyper-parameters for $f$.
Output: Weight matrices $A$, $B$, $C$, $D$.

1: if $\mathcal{N}$ is a standard (layered) neural network then

2: Run a single forward pass on $\mathcal{N}$ with $U$ to obtain outputs
$\hat{Y}$, i.e., $\hat{Y}=\mathcal{N}(U)$.

3: Collect all intermediate layers before and after passing through $\phi$.

4: Construct $Z$ and $X$ by stacking all intermediate layers.

5: else

6: Run fix-point iteration until converge for (1a) to obtain $X$ and $Z$.

7: Run prediction equation (1b) to obatin $\hat{Y}$.

8: end if

9: Put $X,U$ into shared memory.

9:

9:

10: Let $A\leftarrow\mathbf{0}\in{\mathbb{R}}^{n\times
n},B\leftarrow\mathbf{0}\in{\mathbb{R}}^{n\times p}$
$C\leftarrow\mathbf{0}\in{\mathbb{R}}^{q\times
n},D\leftarrow\mathbf{0}\in{\mathbb{R}}^{q\times p}$.

11: Distribute rows of $Z$ or $\hat{Y}$ to each processor.

12: for each processor, in parallel do

13: Solve one of the following convex optimization problem:
$\displaystyle\min_{a,b}f(a,b)~{}:~{}z=\begin{pmatrix}X^{T}&U^{T}\end{pmatrix}\begin{pmatrix}a\\\
b\end{pmatrix},\;\left\lVert a\right\rVert_{1}\leq\kappa,\;\mathcal{C}$
$\displaystyle\min_{c,d}f(c,d)~{}:~{}\hat{y}=\begin{pmatrix}X^{T}&U^{T}\end{pmatrix}\begin{pmatrix}c\\\
d\end{pmatrix},\;\mathcal{C}$

14: end for

15: Update rows of $A,B$ or $C,D$

15:

## Numerical Experiments

We demonstrate the capability of SIM on effectively sparsifying and
robustifying an implicit model from a given standard (layered) network
baseline. We test our method on FashionMNIST (Xiao, Rasul, and Vollgraf 2017)
and CIFAR-100 (Krizhevsky 2009) datasets. These experiments were performed on
$60$ Intel Xeon processors and solved using Mosek (ApS 2022) optimization
solvers. The test set performance is reported. More details on the numerical
experiments can be found in the appendices.

#### FanshionMNIST.

We choose a 4-layer fully-connected network of size $784\times 64\times
32\times 16\times 10$, denoted as $\mathcal{N}_{fc}$, for constructing the
state matrices $X,Z$ and the outputs $\hat{Y}$ for FashionMNIST dataset. A
Mini batch of size 64 were used for training $\mathcal{N}_{fc}$. The baseline
model is trained on a single Nvidia Tesla K80 GPU, achieving an $80\%$ test
performance.

#### CIFAR-100.

For CIFAR-100, we use a ResNet-20 convolutional neural network, denoted as
$\mathcal{N}_{res}$. We follow the hyper-parameter settings in Devries and
Taylor (2017) with a mini batch of size 128. The model is trained on a single
Nvidia Titan V GPU for 200 epochs, with a $75.8\%$ test performance.

#### Training for sparsity

In these experiments, we solve the SIM training problem using the perspective
relaxation and $\ell_{1}$-norm objectives with relaxed state and output
matching penalties as in problem (8), allowing us to control the trade-off
between parameter reduction, state-matching, and outputs-matching through
hyper-parameters. Throughout the rest of the paper, we use the following
hyper-parameters for experiments if not explicitly specified: $\kappa=0.99$
for well-posedness condition, $\lambda_{1}=\lambda_{2}=0.1$ for state-matching
and output-matching condition, $\alpha=$1\text{\times}{10}^{-3}$$ for
sparsity. To evaluate the performance of parameter reduction, we define
sparsity as the percentage of zero parameters of the trained weight matrix $M$
of the total number of non-zero parameters of the baseline model
$\mathcal{N}$:

$\mbox{Sparsity (\%)}:=\left(1-\frac{\left\lVert
M\right\rVert_{0}}{\left\lVert\mathcal{N}\right\rVert_{0}}\right)\times
100\cdot$

Figure 2 shows the trade-off curve for sparsity and test accuracy drop for
FashionMNIST and CIFAR-100 datasets. The experiments show that using
perspective relaxation as objective yields a 28% reduction and a 41% reduction
of the parameters with no accuracy drop for FashionMNIST and CIFAR-100
datasets respectively. Although $\ell_{1}$-norm is a more widely used
objective for learning sparse models, it is less effective as compared to the
perspective relaxation, which is a stronger relaxation for $\ell_{0}$.
Moreover, the perspective relaxation further increases the test performance on
both FashionMNIST and CIFAR-100 while reducing 15% and 10% of the parameters.

Figure 2: Trade-off curve for sparsity and test accuracy drop for FashionMNIST
and CIFAR-100 datasets. Perspective relaxation performs better than
$\ell_{1}$-norm at parameter reduction.

In solving problem (8), the input matrix $U\in{\mathbb{R}}^{p\times m}$ does
not have to be the full training dataset. We test how many number of samples
are required to sufficiently train a sparse implicit model. Figure 3 shows the
effect of the number of samples on sparsity for both datasets. Higher
percentage of total training samples means higher $m$ for input matrix $U$.
Negative sparsity means that the trained implicit models contain more
parameters than the baseline model. We see that for FashionMNIST (50,000 total
training samples), we can train a dense model with less than 4% of the total
training data ($\approx$ 2,000 samples) and a sparse model with less than 2%
of the total training data ($\approx$ 1,000 samples). For CIFAR-100 (50,000
total training samples), more data is required as it is a much challenging
dataset. Nevertheless, with around 20% of total training data ($\approx$
10,000 samples), we are already able to learn a model using perspective
relaxation with 10% fewer parameters. The results indicate that the state
matrix $X$ is a high-quality representation that captures a large number of
the underlying semantic information, and hence it is sufficient to train a
model with significantly fewer training samples. Although the state matrix $X$
is obtained from a standard neural network, we see that in Figure 2 we are
still able to increase the test performance further with fewer parameters
using implicit models. This suggests that implicit models could provide a
better representation as compared to a standard layered neural network.

Figure 3: The effective of the number of samples on sparsity for FashionMNIST
and CIFAR-100 datasets. Perspective relaxation outperforms the $\ell_{1}$-norm
at parameter reduction for the same number of samples.

Finally, we compare our method (denoted as SIM) on CIFAR-100 with other
parameter reduction methods, including SSS (Huang and Wang 2018), SPR
(Cacciola et al. 2022), and MLA (Hu et al. 2019). SSS and SPR both formulate
the task of pruning as a sparse regularized optimization problem similar to
ours, where SSS uses $\ell_{1}$-relaxation while SPR uses perspective
relaxation. MLA considers aligning the semantic information of the
intermediate outputs and overall performance of the baseline model and the
pruned model by introducing a feature and semantic correlation loss and a
classification loss, similar to our state-matching and outputs-matching
conditions. SSS and SPR both uses ResNet-20 and MLA uses ResNet-18. We report
results of each method as they were reported in the original papers. For SSS,
we use the results reported by Cacciola et al., where the data points are
approximated from figures 3(c) of the paper and denoted as P1 and P2. Table 1
shows that SIM achieves less accuracy drop while reducing a larger amount of
parameters. With around 30% of sparsity, SIM has a much lower accuracy drop as
compared to MLA and maintains a similar accuracy drop as SPR. With around 45%
of sparsity, SIM outperforms all three methods with a lower accuracy drop and
more parameter reduction. It is also likely that additional parameter tuning
may lead to more competitive results.

Table 1:  Comparison with other parameter reduction methods on CIFAR-100. Method |  Setting |  Acc. Drop (%) |  Sparsity (%)
---|---|---|---
SSS |  P1 Fig. 3(c) |  -3.7 |  44.4
SSS |  P2 Fig. 3(c) |  -1.3 |  14.8
SPR |  $\lambda=1.0,\alpha=0.1$ |  -2.3 |  45.9
SPR |  $\lambda=1.3,\alpha=0.3$ |  -0.2 |  31.5
MLA |  ResNet-18 |  -3.0 |  50.0
MLA |  ResNet-18 |  -2.5 |  30.0
SIM |  Perspective |  -1.0 |  48.1
SIM |  Perspective |  -0.2 |  29.7

#### Training for robustness.

To test for robustness, we perform $\ell_{\infty}$ attacks using the fast
gradient sign method (FGSM), presented by Goodfellow, Shlens, and Szegedy, on
the FashionMNIST dataset to evaluate their adversarial robustness. FGSM
generates adversarial examples, $\check{u}$, by taking a step of size
$\epsilon$ in the direction of the sign of its gradient taken with respect to
the input, $\check{u}=u+\epsilon\cdot\mbox{sgn}(\nabla\mathcal{N}_{fc}(u))$.
In our experiments, we set $\epsilon=\frac{1}{255}\approx 0.004$, and
$\frac{2}{255}\approx 0.008$. For each batch of the test set, we perturb 50%
of pixels and leave 50% unperturbed. We evaluate robustness using the
prediction accuracy on adversarial examples,
$\mathbf{E}_{\check{u},y}(\mathbf{1}_{y=\mbox{sgn}(f(\check{u}))})$, which
measures the ability of a model resisting them. Figure 4 illustrates the
adversarial robustness with respect to different weight sparsity. In both
cases, we observe that $\ell_{1}$-norm leads to a more robust model as
compared to perspective relaxation, and continues to maintain robustness with
approximately 45% fewer parameters. Moreover, the $\ell_{1}$-norm approach
exhibits more robustness than the original baseline network $\mathcal{N}_{fc}$
with higher model sparsity, until the sparsity reaches an over-sparsified
threshold that leads to an inevitable capacity degradation.

Figure 4: Trade-off curve for robustness with varying weight sparsity. The
$\ell_{1}$-norm is more robust under adversarial attack than the perspective
relaxation and the baseline model.

#### Visualization of trained models.

Figure 5: Visualization of the sparsity pattern for the 4-layer fully-
connected network $\mathcal{N}_{fc}$ in its equivalent implicit form and a
trained sparse implicit model ($\approx$ 30% less parameters) on FashionMNIST.
The weight matrices $A,B,C,D$ correspond to the top left, top right, bottom
left, and bottom right location, separated by the read lines. Non-zero
parameters are colored in black.

To better understand the properties of the learned model, we plot the weight
matrices of the original baseline model versus the sparse implicit model
trained on FashionMNIST dataset. Figure 5 shows the sparsity pattern for the
4-layer fully-connected network $\mathcal{N}_{fc}$ in its equivalent implicit
form and a trained sparse implicit model ($\approx$ 30% less parameters) on
FashionMNIST dataset. We stack the weight matrices in the same way as $M$,
where $A,B,C,D$ correspond to the top left, top right, bottom left, and bottom
right location respectively. In the visualization, the weight matrices are
separated by the red vertical and horizontal lines. The diagonal blue line of
the $A$ matrix separates the feed-forward (upper-triangular area) and feedback
(lower-triangular area) connections. As shown in Figure 5, a standard layered
neural network exhibits a clear hierarchical feed-forward structure,
corresponding to upper-diagonal blocks. In contrast, an implicit model allows
feedback connections, i.e. loops in the computational graph. This example
illustrates how allowing such loops offers room for marked improvement of the
baseline model.

Moreover, we observe that there exists a low-rank structure for the sparse
implicit model, where approximately 40% of the $A$ matrix’s dimensions are
redundant. This suggests that various dimension reduction methods can be
explored to compress the model further; we leave this for future work.

Next, we observe that the $B\in{\mathbb{R}}^{112\times 784}$ matrix of the
sparse implicit model also exhibits a sparse pattern where some of the columns
are completely zeroed-out. Lastly, for the fully-connected neural network
$\mathcal{N}_{fc}$, the large white area on top of the $B_{\mathcal{N}_{fc}}$
matrix indicates there is no connections between the subsequent layers and the
input, requiring all low-level information to be effectively captured by the
intermediate layers. Nevertheless, allowing the low-level information from the
input to pass through directly across the model is desirable and such shortcut
connections (or skip connections) have become a common practice in designing
deep learning architectures (Huang et al. 2017; He et al. 2016). Implicit
models allow such skip connections to be learned based on training data
without hand engineering the model architecture in advance.

## Conclusion

In this work, we present the state-driven implicit modeling, a flexible convex
optimization scheme for training an implicit model without expensive implicit
differentiation, based on fixing the the internal state and outputs from a
given baseline model. We describe the convex training problem and parallel
algorithms for training. By introducing an appropriate objective and setup, we
demonstrate how state-driven implicit modeling can be applied to train sparse
models that are consistently more robust under adversarial attacks. Our
results validate the effectiveness of our approach and highlight promising
directions for research that bring convex optimization, sparsity, and
robustness inducing techniques into implicit modeling.

## References

  * Aghasi, Abdi, and Romberg (2020) Aghasi, A.; Abdi, A.; and Romberg, J. K. 2020.  Fast Convex Pruning of Deep Neural Networks.  _SIAM J. Math. Data Sci._ , 2: 158–188.
  * Aktürk, Atamtürk, and Gürel (2009) Aktürk, M. S.; Atamtürk, A.; and Gürel, S. 2009.  A strong conic quadratic reformulation for machine-job assignment with controllable processing times.  _Operations Research Letters_ , 37: 187–191.
  * Alizadeh et al. (2020) Alizadeh, M.; Behboodi, A.; van Baalen, M.; Louizos, C.; Blankevoort, T.; and Welling, M. 2020.  Gradient Regularization for Quantization Robustness.  _CoRR_ , abs/2002.07520.
  * Amos et al. (2018) Amos, B.; Jimenez, I.; Sacks, J.; Boots, B.; and Kolter, J. Z. 2018.  Differentiable MPC for End-to-end Planning and Control.  In Bengio, S.; Wallach, H.; Larochelle, H.; Grauman, K.; Cesa-Bianchi, N.; and Garnett, R., eds., _Advances in Neural Information Processing Systems_ , volume 31.
  * ApS (2022) ApS, M. 2022.  _The MOSEK Optimizer API for Python 9.3.21_.
  * Atamtürk and Gómez (2019) Atamtürk, A.; and Gómez, A. 2019.  Rank-one Convexification for Sparse Regression.  _arXiv preprint arXiv:1901.10334_.
  * Atamtürk and Gómez (2020) Atamtürk, A.; and Gómez, A. 2020.  Safe screening rules for L0-regression from Perspective Relaxations.  In III, H. D.; and Singh, A., eds., _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , 421–430. PMLR.
  * Atamturk, Gomez, and Han (2021) Atamturk, A.; Gomez, A.; and Han, S. 2021.  Sparse and Smooth Signal Estimation: Convexification of L0-Formulations.  _Journal of Machine Learning Research_ , 22(52): 1–43.
  * Bai, Kolter, and Koltun (2019) Bai, S.; Kolter, J. Z.; and Koltun, V. 2019.  Deep Equilibrium Models.  In Wallach, H.; Larochelle, H.; Beygelzimer, A.; d'Alché-Buc, F.; Fox, E.; and Garnett, R., eds., _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc.
  * Bai, Koltun, and Kolter (2020) Bai, S.; Koltun, V.; and Kolter, J. Z. 2020.  Multiscale Deep Equilibrium Models.  In Larochelle, H.; Ranzato, M.; Hadsell, R.; Balcan, M.; and Lin, H., eds., _Advances in Neural Information Processing Systems_ , volume 33, 5238–5250. Curran Associates, Inc.
  * Berman and Plemmons (1994) Berman, A.; and Plemmons, R. J. 1994.  _Nonnegative Matrices in the Mathematical Sciences_.  Society for Industrial and Applied Mathematics.
  * Cacciola et al. (2022) Cacciola, M.; Frangioni, A.; Li, X.; and Lodi, A. 2022.  Deep Neural Networks pruning via the Structured Perspective Regularization.  _arXiv:2206.14056 [cs.LG]_.
  * Chao et al. (2020) Chao, S.-K.; Wang, Z.; Xing, Y.; and Cheng, G. 2020.  Directional Pruning of Deep Neural Networks.  In _Proceedings of the 34th International Conference on Neural Information Processing Systems_ , NIPS’20. Red Hook, NY, USA: Curran Associates Inc.  ISBN 9781713829546.
  * Chen et al. (2018) Chen, R. T. Q.; Rubanova, Y.; Bettencourt, J.; and Duvenaud, D. K. 2018.  Neural Ordinary Differential Equations.  In Bengio, S.; Wallach, H.; Larochelle, H.; Grauman, K.; Cesa-Bianchi, N.; and Garnett, R., eds., _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc.
  * Chen et al. (2021) Chen, T.; Ji, B.; Ding, T.; Fang, B.; Wang, G.; Zhu, Z.; Liang, L.; Shi, Y.; Yi, S.; and Tu, X. 2021.  Only Train Once: A One-Shot Neural Network Training And Pruning Framework.  In _Advances in Neural Information Processing Systems_.
  * de Avila Belbute-Peres et al. (2018) de Avila Belbute-Peres, F.; Smith, K.; Allen, K.; Tenenbaum, J.; and Kolter, J. Z. 2018.  End-to-End Differentiable Physics for Learning and Control.  In Bengio, S.; Wallach, H.; Larochelle, H.; Grauman, K.; Cesa-Bianchi, N.; and Garnett, R., eds., _Advances in Neural Information Processing Systems_ , volume 31.
  * Devries and Taylor (2017) Devries, T.; and Taylor, G. W. 2017.  Improved Regularization of Convolutional Neural Networks with Cutout.  _CoRR_ , abs/1708.04552.
  * Dhillon et al. (2018) Dhillon, G. S.; Azizzadenesheli, K.; Bernstein, J. D.; Kossaifi, J.; Khanna, A.; Lipton, Z. C.; and Anandkumar, A. 2018.  Stochastic activation pruning for robust adversarial defense.  In _International Conference on Learning Representations_.
  * Dupont, Doucet, and Teh (2019) Dupont, E.; Doucet, A.; and Teh, Y. W. 2019.  Augmented neural odes.  _Advances in Neural Information Processing Systems_ , 32.
  * El Ghaoui et al. (2021) El Ghaoui, L.; Gu, F.; Travacca, B.; Askari, A.; and Tsai, A. 2021.  Implicit Deep Learning.  _SIAM Journal on Mathematics of Data Science_ , 3(3): 930–958.
  * Frangioni and Gentile (2006) Frangioni, A.; and Gentile, C. 2006.  Perspective cuts for a class of convex 0–1 mixed integer programs.  _Mathematical Programming_ , 106: 225–236.
  * Geng et al. (2021) Geng, Z.; Zhang, X.-Y.; Bai, S.; Wang, Y.; and Lin, Z. 2021.  On training implicit models.  _Advances in Neural Information Processing Systems_ , 34: 24247–24260.
  * Goodfellow, Bengio, and Courville (2016) Goodfellow, I.; Bengio, Y.; and Courville, A. 2016.  _Deep Learning_.  MIT Press.
  * Goodfellow, Shlens, and Szegedy (2015) Goodfellow, I. J.; Shlens, J.; and Szegedy, C. 2015.  Explaining and Harnessing Adversarial Examples.  In _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_.
  * Gowal et al. (2018) Gowal, S.; Dvijotham, K.; Stanforth, R.; Bunel, R.; Qin, C.; Uesato, J.; Arandjelovic, R.; Mann, T. A.; and Kohli, P. 2018.  On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models.  _CoRR_ , abs/1810.12715.
  * Gu et al. (2020) Gu, F.; Chang, H.; Zhu, W.; Sojoudi, S.; and El Ghaoui, L. 2020.  Implicit Graph Neural Networks.  In _Proceedings of the 34th International Conference on Neural Information Processing Systems_ , NIPS’20. Red Hook, NY, USA: Curran Associates Inc.  ISBN 9781713829546.
  * Guo et al. (2018) Guo, Y.; Zhang, C.; Zhang, C.; and Chen, Y. 2018.  Sparse DNNs with Improved Adversarial Robustness.  In _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc.
  * Han, Mao, and Dally (2016) Han, S.; Mao, H.; and Dally, W. J. 2016.  Deep Compression: Compressing Deep Neural Network with Pruning, Trained Quantization and Huffman Coding.  In Bengio, Y.; and LeCun, Y., eds., _4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings_.
  * Han et al. (2015) Han, S.; Pool, J.; Tran, J.; and Dally, W. 2015.  Learning both Weights and Connections for Efficient Neural Network.  In Cortes, C.; Lawrence, N.; Lee, D.; Sugiyama, M.; and Garnett, R., eds., _Advances in Neural Information Processing Systems_ , volume 28. Curran Associates, Inc.
  * He et al. (2016) He, K.; Zhang, X.; Ren, S.; and Sun, J. 2016.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 770–778.
  * Hu et al. (2019) Hu, Y.; Sun, S.; Li, J.; Zhu, J.; Wang, X.; and Gu, Q. 2019.  Multi-Loss-Aware Channel Pruning of Deep Networks.  _2019 IEEE International Conference on Image Processing (ICIP)_ , 889–893.
  * Huang et al. (2017) Huang, G.; Liu, Z.; Van Der Maaten, L.; and Weinberger, K. Q. 2017.  Densely connected convolutional networks.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 4700–4708.
  * Huang and Wang (2018) Huang, Z.; and Wang, N. 2018.  Data-Driven Sparse Structure Selection for Deep Neural Networks.  _ECCV_.
  * Karnin (1990) Karnin, E. 1990.  A simple procedure for pruning back-propagation trained neural networks.  _IEEE Transactions on Neural Networks_ , 1(2): 239–242.
  * Krizhevsky (2009) Krizhevsky, A. 2009.  Learning Multiple Layers of Features from Tiny Images.
  * Krizhevsky, Sutskever, and Hinton (2012) Krizhevsky, A.; Sutskever, I.; and Hinton, G. E. 2012.  ImageNet Classification with Deep Convolutional Neural Networks.  Red Hook, NY, USA: Curran Associates Inc.
  * Kurakin, Goodfellow, and Bengio (2017) Kurakin, A.; Goodfellow, I. J.; and Bengio, S. 2017.  Adversarial examples in the physical world.  In _5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Workshop Track Proceedings_. OpenReview.net.
  * Madry et al. (2018) Madry, A.; Makelov, A.; Schmidt, L.; Tsipras, D.; and Vladu, A. 2018.  Towards Deep Learning Models Resistant to Adversarial Attacks.  In _International Conference on Learning Representations_.
  * Meyer (2000) Meyer, C. D. 2000.  _Matrix Analysis and Applied Linear Algebra_.  USA: Society for Industrial and Applied Mathematics.  ISBN 0898714540.
  * Molchanov et al. (2017) Molchanov, P.; Tyree, S.; Karras, T.; Aila, T.; and Kautz, J. 2017.  Pruning Convolutional Neural Networks for Resource Efficient Inference.  In _5th International Conference on Learning Representations, (ICLR) 2017_.
  * Papernot et al. (2016a) Papernot, N.; McDaniel, P. D.; Jha, S.; Fredrikson, M.; Celik, Z. B.; and Swami, A. 2016a.  The Limitations of Deep Learning in Adversarial Settings.  In _IEEE European Symposium on Security and Privacy, EuroS &P 2016, Saarbrücken, Germany, March 21-24, 2016_, 372–387. IEEE.
  * Papernot et al. (2016b) Papernot, N.; McDaniel, P. D.; Wu, X.; Jha, S.; and Swami, A. 2016b.  Distillation as a Defense to Adversarial Perturbations Against Deep Neural Networks.  In _IEEE Symposium on Security and Privacy, SP 2016, San Jose, CA, USA, May 22-26, 2016_ , 582–597. IEEE Computer Society.
  * Qin et al. (2019) Qin, C.; Martens, J.; Gowal, S.; Krishnan, D.; Dvijotham, K.; Fawzi, A.; De, S.; Stanforth, R.; and Kohli, P. 2019.  Adversarial Robustness through Local Linearization.  In Wallach, H.; Larochelle, H.; Beygelzimer, A.; d'Alché-Buc, F.; Fox, E.; and Garnett, R., eds., _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc.
  * Raghunathan, Steinhardt, and Liang (2018) Raghunathan, A.; Steinhardt, J.; and Liang, P. 2018.  Semidefinite relaxations for certifying robustness to adversarial examples.  In _Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada_ , 10900–10910.
  * Simonyan and Zisserman (2015) Simonyan, K.; and Zisserman, A. 2015.  Very Deep Convolutional Networks for Large-Scale Image Recognition.  In _ICLR_.
  * Sui et al. (2021) Sui, Y.; Yin, M.; Xie, Y.; Phan, H.; Aliari Zonouz, S.; and Yuan, B. 2021.  CHIP: CHannel Independence-based Pruning for Compact Neural Networks.  In Ranzato, M.; Beygelzimer, A.; Dauphin, Y.; Liang, P.; and Vaughan, J. W., eds., _Advances in Neural Information Processing Systems_ , volume 34, 24604–24616. Curran Associates, Inc.
  * Szegedy et al. (2014) Szegedy, C.; Zaremba, W.; Sutskever, I.; Bruna, J.; Erhan, D.; Goodfellow, I.; and Fergus, R. 2014.  Intriguing properties of neural networks.  In _International Conference on Learning Representations_.
  * Ta et al. (2022) Ta, T.-A.; Long, T.-T.; Pham, H.; Nguyen, T.; and Le, D. 2022.  Pruning Deep Equilibrium Models.  In _Proceedings of the 2022 Workshop on Sparsity in Neural Networks, 39th International Conference on Machine Learning_.
  * Tramèr et al. (2017) Tramèr, F.; Kurakin, A.; Papernot, N.; Goodfellow, I.; Boneh, D.; and McDaniel, P. 2017.  Ensemble Adversarial Training: Attacks and Defenses.
  * Winston and Kolter (2020) Winston, E.; and Kolter, J. Z. 2020.  Monotone operator equilibrium networks.  In _Advances in Neural Information Processing Systems_ , volume 33, 10718–10728. Curran Associates, Inc.
  * Xiao, Rasul, and Vollgraf (2017) Xiao, H.; Rasul, K.; and Vollgraf, R. 2017.  Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms.  _arXiv preprint arXiv:1708.07747_.
  * Yeom et al. (2019) Yeom, S.; Seegerer, P.; Lapuschkin, S.; Wiedemann, S.; Müller, K.; and Samek, W. 2019.  Pruning by Explaining: A Novel Criterion for Deep Neural Network Pruning.  _CoRR_ , abs/1912.08881.
  * Zhu and Gupta (2018) Zhu, M.; and Gupta, S. 2018.  To Prune, or Not to Prune: Exploring the Efficacy of Pruning for Model Compression.  In _6th International Conference on Learning Representations, ICLR 2018_.

##  Appendix A Proofs

#### Proof of Theorem 1

We first prove the existence of a solution $x\in{\mathbb{R}}^{n}$ to the
equation $x=\phi(Ax+b)$ if $\lambda_{\text{pf}}<1$. Since $\phi$ satisfies
Assumption (1), we have that for $t\geq 1$, the picard iteration

$x_{t+1}=\phi(Ax_{t}+b),\;x_{0}=0,\;t=0,1,\cdots$

satisfies

$\displaystyle|x_{t+1}-x_{t}|$
$\displaystyle=|\phi(Ax_{t}+b)-\phi(Ax_{t-1}+b)|$
$\displaystyle\leq|A(x_{t}-x_{t-1})|\leq|A||x_{t}-x_{t-1}|$
$\displaystyle\leq|A|^{t}|x_{1}-x_{0}|.$

Hence, for every $t,\tau\geq 1$, we have

$\displaystyle|x_{t+\tau}-x_{t}|=\left|\sum_{i=t+1}^{t+\tau}(x_{i}-x_{i-1})\right|\leq\sum_{k=t}^{t+\tau}|A|^{k}|x_{1}-x_{0}|$
$\displaystyle\leq|A|^{t}\sum_{k=0}^{\tau}|A|^{k}|x_{1}-x_{0}|\leq|A|^{t}\sum_{k=0}^{\infty}|A|^{k}|x_{1}-x_{0}|$
$\displaystyle=|A|^{t}(I-|A|)^{-1}|x_{1}-x_{0}|.$

The inverse of $I-|A|$ exists as $\lambda_{\text{pf}}(|A|)<1$. Since
$\lim_{t\to\infty}|A|^{t}=0$, we have

$0\leq\lim_{t\to\infty}|x_{t+\tau}-x_{t}|\leq\lim_{t\to\infty}|A|^{t}(I-|A|)^{-1}|x_{1}-x_{0}|=0.$

We obtain that $x_{t}$ is a Cauchy sequence, and thus the sequence converges
to some limit point, $x_{\infty}$, which by continuity of $\phi$ can be
obtained by $x_{\infty}=\phi(Ax_{\infty}+b)$, thus establishes the existence
of a solution to $x=\phi(Ax+b)$.

For uniqueness, consider two solutions $x_{a},x_{b}\in{\mathbb{R}}^{n}_{+}$ to
the equation, the following inequality holds,

$0\leq|x_{a}-x_{b}|\leq|A||x_{a}-x_{b}|\leq|A|^{k}|x_{a}-x_{b}|.$

As $k\to\infty$, we have that $|A|^{k}\to 0$, and it follows that
$x_{a}=x_{b}$, which establishes the unicity of the solution.

#### Proof of Theorem 2

Consider a neural network $\mathcal{N}$ in its equivalent implicit form
$(A_{\mathcal{N}},B_{\mathcal{N}},C_{\mathcal{N}},D_{\mathcal{N}},\phi)$,
since the matrix $|A_{\mathcal{N}}|$ is strictly upper triangular, all of its
eigenvalues are zeros, automatically satisfying the PF sufficient condition
for well-posedness. From the Collatz-Wielandt formula (Meyer 2000), the PF
eigenvalue of a well-posed implicit model can be represented as

$\lambda_{\text{pf}}(|A|)=\inf_{s>0}\left\lVert\mbox{{diag}}(s)|A|\mbox{{diag}}(s)^{-1}\right\rVert_{\infty}.$

The scaling factor $s$ such that
$\left\lVert\mbox{{diag}}(s)|A|\mbox{{diag}}(s)^{-1}\right\rVert_{\infty}<1$
can be obtained by solving

$s_{i}=1+\sum_{j=i+1}^{n}|A_{i,j}|s_{j},\;i\in[n],$

which can then be solved by backward substitution. The new model matrices
$(A^{\prime},B^{\prime},C^{\prime},D^{\prime},\phi)$, are obtained by

$\left(\begin{array}[]{c|c}A^{\prime}&B^{\prime}\\\ \hline\cr
C^{\prime}&D^{\prime}\end{array}\right)=\left(\begin{array}[]{c|c}SAS^{-1}&SB\\\
\hline\cr CS^{-1}&D\end{array}\right)$

where $S=\mbox{{diag}}(s)$, with $s>0$ a PF eigenvalue of $|A|$. More
generally, provided that $\lambda_{\text{pf}}(|A|)<1$, we simply set
$s=(I-|A|)^{-1}\mathbf{1}$, which can be obtained as the limit point of fixed-
point iterations.

##  Appendix B More on Parallel Training

#### Data structure.

Fitting all the weight matrices into memory requires a substantial amount of
storage space. However, we can leverage the high-sparsity property of the
problem to reduce the memory consumption when storing the weight matrices. In
the high-sparsity regime, schemes known from high-performance computing such
as compressed sparse row (CSR) and compressed sparse column (CSC) can store
indices of matrices, respectively. Since in this problem, we operate in a row-
wise fashion, we choose to store the weight matrices in CSR format. CSR
represents the indices in an $n=n_{r}\times n_{c}$ matrix using row and column
index arrays. The row array is of length $n_{r}$ and store the offsets of each
row in the value array in $\lceil\log_{2}m\rceil$ bits, where $m$ is the
number of non-zero elements. The column array is of length $m$ and stores the
column indices of each value in $\lceil\log_{2}n_{c}\rceil$ bits. The total
storage space required is therefore
$n_{r}\times\lceil\log_{2}m\rceil+m\times\lceil\log_{2}n_{c}\rceil$.

#### Multiprocessing.

Given state matrices from a neural network, the basis pursuit problem of (9)
and (10) can be paralleled, each involving a single or a block of rows. Each
block is trained independently by a child processor with an auxiliary
objective, and returns the solutions back to the main processor. We implement
our parallel training algorithm with the multiprocessing package using Python.
The multiprocessing
package111https://docs.python.org/3/library/multiprocessing.html supports
spawning processes and offers both local and remote concurrency. In Python,
its Global Interpreter Lock (GIL) only allows one thread to be run at a time
under the interpreter, which means we are unable to leverage the benefit of
multi-threading. However, with multiprocessing, each process has its own
interpreter and the instructions are executed by its own interpreter, which
allows multiple processes to be run in parallel, side-stepping the GIL by
using sub-processes instead of threads. In multiprocessing, a process is a
program loaded into memory to run and does not share its memory with other
processes. The decomposability of the training problem can be viewed as data
parallelism where the execution of a function, i.e. solving the convex
optimization problem, is parallelized, and the input values are distributed
across processes. We use the `Pool` object to offer a means of defining a
function in a module so that child processes can each import the module and
execute it independently.

#### Memory sharing.

In multiprocessing, data in the arguments are pickled and passed to the child
processors by default. In the basis pursuit problem, the state matrix $X$ and
the input data matrix $U$ remain unchanged during task execution across all
the processors, and thus only need read-only access to $X$ and $U$. Passing
$X$ and $U$ to each processor whenever a new task is scheduled consumes a
significant amount of memory space and increases the communication time. As a
result, instead of treating them as data input to the function, we put $X$ and
$U$ into a shared memory, providing direct access of the shared resources
across processes.

#### Ray.

We also implement our parallel algorithm using Ray222https://www.ray.io/, an
open-source and general-purpose distributed compute framework for machine
learning and deep learning applications. By transforming the execution of the
convex training problems into ray `actors`, we are able to distribute the
input values to multiple ray actors to run on multiple ray nodes. Similar to
the memory sharing in the multiprocessing approach, we use `ray.put()` to save
objects into the ray object store, saving memory bandwidth by only passing the
object ids around. We run our experiments on the Cori
clusters333https://docs.nersc.gov/systems/cori/ hosted by National Energy
Research Scientific Computing (NERSC) Center and use the slurm-ray-cluster
scripts444https://github.com/NERSC/slurm-ray-cluster for running multi-nodes.

#### Performance benchmark.

Figure 6 show the run-time for our serial and parallel implementation using
both multiprocessing and Ray. We observe that multiprocessing provides the
best speedup as compared to Ray. We hypothesize that since Ray is a general-
purpose distributed compute framework, it contains more overhead than solving
the training problem directly using multiprocessing.

Figure 6: Performance benchmark for serial, multiprocessing (parallel), and
Ray (parallel) implementation on FashionMNIST dataset using 8 processors.

##  Appendix C More on Numerical Experiments

Table 2 and Table 3 shows the number of training samples, hyper-parameters,
and adversarial test accuracy for perspective relaxation and $\ell_{1}$-norm
objective functions with state and outputs matching penalties as in problem
(8). For perceptive relaxation, we solve the following problem:

$\displaystyle\min_{M,t,s}\;\;$
$\displaystyle\alpha\sum_{ij}s_{ij}+\lambda_{1}\left\lVert
Z-(AX+BU)\right\rVert^{2}_{F}$ (11a)
$\displaystyle+\lambda_{2}\left\lVert\hat{Y}-(CX+DU)\right\rVert^{2}_{F}$
(11b) s.t. $\displaystyle\mbox{(\ref{eq:sim-wp-
constraint})},\;t_{ij}\in[0,1],M^{2}_{ij}\leq s_{ij}\cdot t_{ij},\;s_{ij}\geq
0.$ (11c)

For the $\ell_{1}$-norm problem, we solve the following problem:

$\displaystyle\min_{M}\quad$
$\displaystyle\beta\sum_{ij}|M_{ij}|+\lambda_{1}\left\lVert
Z-(AX+BU)\right\rVert^{2}_{F}$ (12a)
$\displaystyle+\lambda_{2}\left\lVert\hat{Y}-(CX+DU)\right\rVert^{2}_{F}~{}:~{}\mbox{(\ref{eq:sim-
wp-constraint})},$ (12b)

where $\beta$ controls the degree of regularizing for robustness.

Table 2:  Experimental settings for perspective relaxation on Fashion-MNIST. |  |  |  |  | Test Acc. (%)
---|---|---|---|---|---
# Train Samples |  Sparsity (%) |  $\lambda_{1}$ |  $\lambda_{2}$ |  $\alpha$ |  $\epsilon=0.004$ |  $\epsilon=0.008$
700 |  15 |  0.1 |  0.1 |  0.01 |  78.7 |  75.4
500 |  23 |  0.1 |  0.1 |  0.01 |  77.3 |  73.8
400 |  28 |  0.1 |  0.1 |  0.01 |  76.6 |  72.8
300 |  36 |  0.1 |  0.1 |  0.01 |  74.9 |  72.4
200 |  54 |  0.1 |  0.1 |  0.01 |  73.7 |  70.1
100 |  77 |  0.1 |  0.1 |  0.01 |  57.2 |  49.5
Table 3:  Experimental settings for $\ell_{1}$-norm on Fashion-MNIST. |  |  |  |  | Test Acc. (%)
---|---|---|---|---|---
# Train Samples |  Sparsity (%) |  $\lambda_{1}$ |  $\lambda_{2}$ |  $\beta$ |  $\epsilon=0.004$ |  $\epsilon=0.008$
600 |  20 |  0.1 |  0.1 |  0.001 |  79.6 |  76.2
1000 |  47 |  0.01 |  0.01 |  0.001 |  79.3 |  76.2
500 |  26 |  0.01 |  0.01 |  0.01 |  78.3 |  75.0
2000 |  6 |  0.01 |  0.01 |  0.01 |  77.6 |  74.6
900 |  65 |  0.01 |  0.01 |  0.001 |  74.9 |  69.9
400 |  76 |  0.01 |  0.01 |  0.001 |  72.3 |  68.4


# Pseudo-Labeling for Massively Multilingual Speech Recognition

Loren Lugosch1 Tatiana Likhomanenko2† Gabriel Synnaeve2 Ronan Collobert2
1McGill University / Mila, 2Facebook AI Research Work done during an
internship at FAIR. †Currently at Apple.

###### Abstract

Semi-supervised learning through pseudo-labeling has become a staple of state-
of-the-art monolingual speech recognition systems. In this work, we extend
pseudo-labeling to massively multilingual speech recognition with 60
languages. We propose a simple pseudo-labeling recipe that works well even
with low-resource languages: train a supervised multilingual model, fine-tune
it with semi-supervised learning on a target language, generate pseudo-labels
for that language, and train a final model using pseudo-labels for all
languages, either from scratch or by fine-tuning. Experiments on the labeled
Common Voice and unlabeled VoxPopuli datasets show that our recipe can yield a
model with better performance for many languages that also transfers well to
LibriSpeech.

##  1 Introduction

One of the long-term goals of automatic speech recognition (ASR) research is a
single system that can transcribe speech in any language [1, 2]. Such a
multilingual system would be simpler to maintain than a collection of
monolingual models, enable users to comfortably speak any language without
needing to tell the system which language to expect in advance, and share
knowledge between all languages for improved performance.

A key ingredient of modern state-of-the-art monolingual ASR missing from
current multilingual models is pseudo-labeling [3], a technique for harnessing
unlabeled datasets that has recently begun consistently yielding performance
gains even for ASR tasks with large labeled datasets like LibriSpeech [4, 5,
6]. In pseudo-labeling, a model trained on a labeled dataset is used to
generate labels for an unlabeled dataset, and those pseudo-labels (PLs) are
then used to train a model. Many variants of pseudo-labeling exist: for
instance, the same model used to generate PLs can also be trained on those PLs
[7, 8, 9], or PLs generated by a teacher model can be used to train a new
student model [4, 6, 10, 11].

In this work, we go beyond the monolingual setting and demonstrate the use of
pseudo-labeling to improve a massively multilingual speech recognizer trained
on all 60 languages of the Common Voice dataset [12] simultaneously. First, we
show that self-training on all unlabeled data in the multilingual VoxPopuli
dataset [13] at once tends to produce poor PLs for low-resource languages, and
instead propose a simple recipe (Fig. 1) in which the model is first fine-
tuned for a particular language before pseudo-labeling. Next, we compare a
number of methods for training with the generated PLs, and find that training
a larger model from scratch on all labeled and pseudo-labeled data works best.
Finally, we show that the use of pseudo-labeled data improves out-of-domain
generalization through experiments on LibriSpeech [14]. Unlike much previous
work on this topic, our experiments use only open-source data, and we plan to
release the model for those who would like to experiment with it
further.111(Link to model checkpoints to be added later.)

Figure 1: Illustration of our method: to produce better pseudo-labels for a
given language, we first fine-tune the multilingual model on that language.

##  2 Model

The model used in our experiments (Fig. 2) is identical to the neural network
used for LibriSpeech in [9], except for the output layer(s). The input to the
encoder is a sequence of 80-dimensional log mel filterbank frames, extracted
using 25 ms Hamming windows every 10 ms from the 16 kHz audio signal. The
encoder has a single convolutional layer with a filter length of 7 and a
stride of 3, followed by 36 transformer layers with 4 heads, feedforward
dimension 3072, and self-attention dimension 768, using the relative position
embeddings of [15]. The output of the encoder is fed to a CTC [16] head and a
language identification (LID) head. The CTC head is a linear layer with 8065
outputs: one for each character (most of which are Chinese characters),
including punctuation, space, and the CTC <blank> symbol. The CTC head is
shared across all languages: it is a “joint” multilingual model, using the
terminology of [2]. The LID head is a linear layer with 60 outputs (one per
language), followed by mean-pooling to aggregate the variable-length sequence
of output vectors into a single vector of logits. The LID head outputs are
only used during training: during inference, standard decoding algorithms can
be applied to the CTC head outputs. The model is implemented and trained using
Flashlight222https://github.com/flashlight/flashlight.

Figure 2: Illustration of the model used in our experiments, with optional
language identification head (Sec. 4) shown in grey.

While we do not perform explicit empirical comparisons with other multilingual
models in the literature (as the focus of this work is on pseudo-labeling), it
is worth noting that our model is significantly simpler than existing
multilingual models, forgoing the use of language- or language-family-specific
parameters, decoders, and tokenizers. We are not the first to use an encoder-
only CTC architecture for multilingual ASR [17, 18, 19], but we believe we are
the first to demonstrate this for massively multilingual end-to-end ASR.
Previous work on this topic [20, 21, 22, 23, 24] has instead used more
sophisticated sequence transduction models with autoregressive decoder
networks [25, 26, 27, 28, 29], citing the flaw of CTC’s conditional
independence assumption. In practice, CTC models implemented using modern
neural network architectures are able to learn strong implicit language models
[4, 9] and achieve state-of-the-art results for the low-resource setting [30,
9]. For those reasons, we focus on CTC models in this paper.

##  3 Data

The model is trained using the December 2020 release (6.1) of Common Voice
(CV) [12], which has 3.6k hours of training data. CV is a continuously growing
multilingual speech dataset recorded online by volunteer speakers. The 60
constituent languages vary greatly in the amount of available data: 7
languages have more than 100h of data, and 10 languages have less than 1h of
data. We do not remove punctuation and capitalization from the CV transcripts,
as this makes it easier to replicate our setup333While there have been
attempts to standardize the formatting of transcripts for Common Voice for
English [31], most reported results use an ad-hoc normalization scheme, and so
cannot readily be compared. and learning speed was not noticeably impacted. We
downsample all audio to 16 kHz.

In addition to CV, we use VoxPopuli (VP) [13], a very large scale (384k hours)
unlabeled multilingual dataset of European languages. The dataset is split
into 23 languages. 19 of the 23 VP languages are in CV (Czech, German, Greek,
English, Spanish, Estonian, Finnish, French, Hungarian, Italian, Lithuanian,
Latvian, Maltese, Dutch, Polish, Portuguese, Romanian, Slovenian, and
Swedish): we use only those 19 languages for semi-supervised learning.

##  4 Supervised training

We train supervised models on CV for $\sim$500k updates. The hyperparameters
and training procedure are identical to those used in [9], except we use 2
SpecAugment [32] time masks instead of 10 (using 10 masks was found to cover
too much of the shorter CV audio), and the learning rate is halved just once,
at 250k updates. We do not use the language balancing technique of [21, 2] to
sample languages evenly (which we found easily overfit to the low-resource
languages), or curriculum learning as in [2]. In addition to the base model
(275M params), we also train larger models (1.06B params) by doubling the
feedforward and self-attention dimensions. The base models are trained on 16
GPUs with dynamic batching using 200s of audio per batch per GPU, and the
large models are trained using 64 GPUs with 50s of audio per GPU, resulting in
the same effective batch size.

Following [33], we add an LID loss, so that the loss $\ell$ used for training
is $\ell=\ell_{\text{CTC}}+\gamma\cdot\ell_{\text{LID}},$ where
$\ell_{\text{CTC}}$ represents the CTC loss, $\ell_{\text{LID}}$ represents
the LID loss (the cross-entropy between the LID head outputs and the one-hot
language label for a given utterance), and $\gamma$ is a hyperparameter. We
trained models on CV with $\gamma\in\\{0,0.1,1,10\\}$: $\gamma=1$ yielded the
best results, with 2.6% absolute improvement in average validation character
error rate (CER) over the baseline with $\gamma=0$ (no LID), using greedy
decoding. Some examples of greedy decoding outputs for the base supervised
model are shown in Fig. 3 and Fig. 4.

Figure 3: Example greedy decoding outputs from the base supervised model for 6
utterances from the validation sets of some of the higher-resource CV
languages: English, Chinese (China), Russian, Kinyarwanda, French, and German.
Figure 4: Examples of LibriSpeech dev-clean outputs with greedy decoding for
base supervised model, trained only on CV, not on LibriSpeech. (Substitutions
are colored: red = genuine error, blue = punctuation/truecasing counted as
error.) Note that the model almost correctly transcribes the unusual Italian
sentence in dev-clean, unlike a typical LibriSpeech model (cf. [30, Table
12]).

##  5 Semi-supervised training

To train on the unlabeled data in VP, we use slimIPL [9], an iterative
approach in which a model is trained for a number of updates on labeled data,
followed by continuous training using labeled data and pseudo-labeled data
stored in a dynamic cache which is periodically updated with pseudo-labels
(PLs) re-generated by the current model state using greedy decoding without an
external language model (LM). We use a cache size of 1000, replacement
probability 0.1, and $\lambda=10$ (ratio of unlabeled batches to labeled
batches).

###  5.1 Fine-tuning before pseudo-labeling

The simplest way to perform semi-supervised learning would be to pool the
unlabeled data for all languages, as we do for the labeled data, and run
slimIPL. We found that doing so led to poor PLs for low-resource languages,
such as Greek, which has only 2.75h of training data (see top of Fig. 5 — the
transcript has a mix of Greek and Latin characters).

Figure 5: Pseudo-labels for an utterance from the Greek subset of VP with
basic slimIPL (top) or with slimIPL after monolingual fine-tuning (bottom).
Red letters are Latin characters.

Instead, to produce PLs for a VP language, we first fine-tune the trained
multilingual model by training only on CV data for that language for 10k
updates, and then run slimIPL using the corresponding VP data (bottom of Fig.
5). The same effect could also be achieved by generating PLs using a
monolingual model, but our proposed approach yields better results by taking
advantage of multi-task learning (Table 1).

Table 1: (Semi-)supervised learning results with slimIPL for the CV Greek data given different training sets. Labeled | Unlabeled | Valid CER | Test CER
---|---|---|---
CV All |  – | 53.2 | 47.8
CV Greek |  – | 30.6 | 33.6
CV Greek | VP Greek | 23.9 | 25.1
CV Greek | VP English444See Sec. 8 for a more detailed discussion of semi-supervised learning with language mismatch. | 24.3 | 28.4
CV All $\to$ CV Greek |  – | 9.9 | 9.6
CV All $\to$ CV Greek | VP Greek | 8.7 | 8.5

After training slimIPL models for all 19 languages in (CV languages $\cap$ VP
languages), we generate a final set of PLs for all unlabeled VP utterances
using the appropriate slimIPL models. We filter out all utterances for which
the PL length is 0 or >630 (maximum label length supported by the CTC loss
implementation). The PLs for all languages can then be pooled and used either
by continuing training the non-fine-tuned multilingual model checkpoint with
all available CV and VP data, or by training a new model on that data from
scratch. When training a model from scratch, we found it necessary for
convergence to lower the learning rate from 0.03 to 0.01 and to delay the use
of SpecAugment until 50k updates; we also lower the learning rate when using
VP data to fine-tune the base model already trained on CV.

Distilling the per-language fine-tuned models’ knowledge back into a single
final model is similar to the recently proposed multi-task self-training
(MuST) [34]. In MuST, a separate teacher model is trained for each task and
used to pseudo-label every available training example, and a general student
model with one head for each task is then trained on all the pseudo-labels.
The difference here is that our final model only performs one “task”, since we
use a single shared CTC head over all languages, and the model itself must
determine which language is being spoken.

###  5.2 Avoiding collapse: cropping warmup period

Another difficulty arose from the fact that the utterances of VP (average
duration of 30s) are much longer than those of CV (average duration of 5.3s).
The model trained only on CV generates mostly empty transcripts for VP, a
commonly observed failure mode for out-of-domain audio or utterances longer
than those observed during training [8, 35, 36]. Semi-supervised learning
failed as a result, usually collapsing to generating all blanks even for the
labeled data. To acclimate the model to the longer VP utterances, we use a
warmup period of 10k updates during which we crop unlabeled audio into 10s
segments before running the acoustic model, then stitch the resulting logit
sequences back together and decode to obtain PLs. The model is then trained on
the original uncropped utterance using those PLs. Cropping the utterances
results in poor pseudo-labels, so after a number of updates, we stop cropping
the unlabeled utterances during pseudo-labeling. This warmup period approach
works better than simply always cropping (Fig. 6).

$4.8$$5$$5.2$$5.4$$5.6$$5.8$$6$$\cdot 10^{5}$$10$$12$$14$#
updatesCERSupervisedslimIPL (always crop)slimIPL (cropping warmup period)
Figure 6: Validation CER for CV Greek (after training on CV All) with
supervised fine-tuning or semi-supervised fine-tuning with VP Greek via
slimIPL, using either a cropping warmup period or always cropping.

##  6 Performance on Common Voice

Table 2 lists the performance of the multilingual model averaged over all CV
languages in various settings.555Detailed per-language training logs and
decoded outputs for all 60 languages can be found at (link to be added later).
Table 3 reports the same information for CV languages that are in VP. All
results for CV are reported using greedy decoding in terms of character error
rate (CER), as suggested in [12].

In addition to the base model (trained only on CV), we report performance when
the VP audio with the final set of PLs is added back into the training set,
either by fine-tuning the model already trained on CV (“+ all PLs (fine-
tune)”) or by training a model from scratch on CV+VP (“+ all PLs (from
scratch)”). We only report results for the large model when training it from
scratch on CV+VP, as the large model overfit to CV after a few epochs (see
Fig. 7, “CV (large)”). Test CER is measured by selecting the checkpoint with
the best average validation CER across all languages. While performance is
degraded on average (Fig. 7), it is greatly improved for the VP languages
(Fig. 8(a)), with the best results achieved training a larger model from
scratch.

The degradation for CV languages on average can be explained by the fact that
VP is much larger than CV, leading to an imbalance in favor of the 19
languages in (CV languages $\cap$ VP languages). If we then fine-tune the
models trained on CV+VP on only CV (“$\hookrightarrow$ fine-tune on CV only”),
they not only still have improved performance over the base model when
averaging over the VP languages, but also close the gap when averaging over
all CV languages.

We also train a monolingual model for each language separately using the same
hyperparameters as the multilingual model, and report the performance of those
models along with the performance of the multilingual model when fine-tuned
using only labeled data for that language (“supervised fine-tuning”) or, when
unlabeled data is available (Table 3), using both labeled and unlabeled data
for that language (“slimIPL fine-tuning”). For monolingual models, or
multilingual models with monolingual fine-tuning, the test CER is measured
using the checkpoint with the best validation CER. There is still a large gap
between the base model and fine-tuned models (see e.g. Greek in Table 1), but
the gap is reduced for the VP languages when training on the pseudo-labeled
data.

Table 2: CER averaged over all CV languages. Model | Valid CER | Test CER
---|---|---
Base model | 26.8 | 28.8
\+ all PLs (fine-tune) | 27.6 | 29.7
\+ all PLs (from scratch, base) | 38.0 | 39.9
$\hookrightarrow$ fine-tune on CV only | 26.6 | 28.2
\+ all PLs (from scratch, large) | 35.4 | 37.1
Monolingual baseline | 33.8 | 35.5
Supervised fine-tuning | 10.6 | 11.4
Table 3: CER averaged over languages in (CV languages $\cap$ VP languages). Model | Valid CER | Test CER
---|---|---
Base model | 24.4 | 24.8
\+ all PLs (fine-tune) | 17.5 | 17.9
\+ all PLs (from scratch, base) | 15.0 | 15.6
$\hookrightarrow$ fine-tune on CV only | 13.8 | 14.0
\+ all PLs (from scratch, large) | 11.7 | 12.2
Monolingual baseline | 25.1 | 26.8
Supervised fine-tuning | 7.7 | 8.3
slimIPL fine-tuning | 6.9 | 7.5
$0$$0.2$$0.4$$0.6$$0.8$$1$$\cdot 10^{6}$$30$$40$$50$$60$$70$$80$# updatesCERCV
(base)$\hookrightarrow$ fine-tune on CV+VPCV (large)CV+VP from scratch
(base)$\hookrightarrow$ fine-tune on CV onlyCV+VP from scratch (large) Figure
7: Validation CER curves for CV averaged over all languages for various
training settings.

$0$$0.2$$0.4$$0.6$$0.8$$1$$\cdot 10^{6}$$10$$20$$30$$40$$50$# updatesCERCV
(base)$\hookrightarrow$ fine-tune on CV+VPCV (large)CV+VP from scratch
(base)$\hookrightarrow$ fine-tune on CV onlyCV+VP from scratch (large) (a) CV
languages $\cap$ VP languages.

$0$$0.2$$0.4$$0.6$$0.8$$1$$\cdot 10^{6}$$30$$40$$50$$60$$70$$80$# updatesCERCV
(base)$\hookrightarrow$ fine-tune on CV+VPCV (large)CV+VP from scratch
(base)$\hookrightarrow$ fine-tune on CV onlyCV+VP from scratch (large) (b) CV
languages \VP languages.

Figure 8: Validation CER curves for CV when averaging over the subset of
languages in VP (left) and the subset of languages not in VP (right).

$0$$0.2$$0.4$$0.6$$0.8$$1$$\cdot 10^{6}$$20$$40$$60$$80$$100$#
updatesCERCV$\hookrightarrow$ CV+VPCV+VP$\hookrightarrow$ CV (a) Greek — 2.75h

$0$$0.2$$0.4$$0.6$$0.8$$1$$\cdot 10^{6}$$20$$40$$60$$80$$100$#
updatesCERCV$\hookrightarrow$ CV+VPCV+VP$\hookrightarrow$ CV (b) Finnish —
0.55h

$0$$0.2$$0.4$$0.6$$0.8$$1$$\cdot 10^{6}$$20$$40$$60$$80$$100$#
updatesCERCV$\hookrightarrow$ CV+VPCV+VP$\hookrightarrow$ CV (c) Lithuanian —
1.18h

Figure 9: Validation CER curves for the base multilingual models’ performance
on three low-resource CV languages with a corresponding subset in VP.

$0$$0.2$$0.4$$0.6$$0.8$$1$$\cdot 10^{6}$$0$$20$$40$$60$$80$$100$#
updatesCERCV$\hookrightarrow$ CV+VPCV+VP$\hookrightarrow$ CV (a) English —
897h

$0$$0.2$$0.4$$0.6$$0.8$$1$$\cdot 10^{6}$$0$$50$$100$#
updatesCERCV$\hookrightarrow$ CV+VPCV+VP$\hookrightarrow$ CV (b) Catalan —
444h

$0$$0.2$$0.4$$0.6$$0.8$$1$$\cdot 10^{6}$$20$$40$$60$$80$$100$#
updatesCERCV$\hookrightarrow$ CV+VPCV+VP$\hookrightarrow$ CV (c) Kabyle — 109h

Figure 10: Validation CER curves for the base multilingual models’ performance
on three high-resource CV languages: English ($\in$ VP), Catalan ($\not\in$
VP), Kabyle ($\not\in$ VP).

Fig. 9 shows the performance of the multilingual model being improved by
pseudo-labeled data for three low-resource CV languages. In Fig. 10, in
contrast, the opposite occurs for three high-resource languages: performance
is worse when fine-tuning on CV+VP and much worse when training a new model
from scratch on CV+VP.

There is a straightforward explanation for why the model trained from scratch
on CV+VP initially performs so much worse on Catalan and Kabyle, before the
model is fine-tuned only on CV: those languages are not in VP, so the amount
of training data observed by the model for those languages is dwarfed by the
amount of training data observed for the VP languages. However, English is
among the VP languages, so it is surprising that the performance of English is
also worse for the model trained from scratch on CV+VP, and that performance
becomes worse when the model trained on CV is fine-tuned on CV+VP. It is worth
noting that VP data is somewhat noisy: much of it is spoken by interpreters
attempting to translate, in real-time, what is being said by another speaker
in another language—sometimes stumbling over a word or repeating themselves.
The domain mismatch between this type of speech, as opposed to the prompted
speech in CV, may explain the performance gap. Even though performance is
degraded for the English subset of CV, the use of VP data does improve the
model’s ability to process English in a new domain, as we show in the next
section.

##  7 Transferring to LibriSpeech

To see how well the multilingual models perform on out-of-domain audio, we
evaluate them on LibriSpeech in Table 4. Word error rate (WER) is reported
both using greedy decoding and using a beam search for

$\underset{{\mathbf{y}}}{\operatorname{argmax}}~{}\log
p_{\theta}({\mathbf{y}}|{\mathbf{x}})+\alpha\log
p^{\text{LM}}({\mathbf{y}})+\beta|{\mathbf{y}}|,$ (1)

where $p_{\theta}({\mathbf{y}}|{\mathbf{x}})$ is the probability of transcript
${\mathbf{y}}$ given input audio ${\mathbf{x}}$ according to the acoustic
model, $p^{\text{LM}}({\mathbf{y}})$ is the probability of ${\mathbf{y}}$
according to an external 4-gram word-level LM trained on the LibriSpeech LM
corpus, $|{\mathbf{y}}|$ denotes the length of ${\mathbf{y}}$, and
$\alpha,\beta$ are set using a small grid search on the dev sets. We find that
the multilingual model fine-tuned with all VP PLs performs much better on
LibriSpeech across all settings. It can be seen from Table 5, in which test-
other is split by the duration of utterances, that the improvement is due
mostly to the model’s ability to process longer sequences acquired from
training on the longer VP utterances (see Sec. 5.2).

We also demonstrate the base model’s transfer capability by fine-tuning it
either on the 100h or 960h subset of LibriSpeech (Table 4, “CV $\to$
LS-{100,960}”). During fine-tuning, instead of 2 SpecAugment masks (Sec. 4),
we use 10 masks, as in [9], which we found yielded better performance. With
fine-tuning on LibriSpeech, performance is greatly improved for the 100h setup
over the 100h-only training, while with 960h performance is similar or
slightly worse. We have not yet made these comparisons for the CV+VP models,
but our other results suggest that similar benefits may be observed.

Table 4: LibriSpeech WER for different training sets. Data | LM | Dev WER | Test WER
---|---|---|---
clean | other | clean | other
CV | - | 59.7 | 60.1 | 62.0 | 62.8
4-gram | 33.7 | 34.3 | 37.6 | 37.7
CV | - | 34.1 | 41.7 | 33.5 | 42.5
$\to$ CV+VP | 4-gram | 8.8 | 15.9 | 9.0 | 16.8
CV+VP | - | 39.7 | 47.9 | 39.0 | 49.4
$\to$ CV | 4-gram | 10.1 | 17.8 | 10.4 | 19.5
CV | - | 4.8 | 13.7 | 5.1 | 13.6
$\to$ LS-100 | 4-gram | 3.3 | 9.7 | 3.8 | 9.9
CV | - | 3.0 | 7.5 | 3.1 | 7.4
$\to$ LS-960 | 4-gram | 2.1 | 5.3 | 2.6 | 5.8
LS-100 | - | 6.2 | 16.8 | 6.2 | 16.8
4-gram | 4.1 | 12.4 | 4.5 | 12.7
LS-960 | - | 2.7 | 6.8 | 2.8 | 6.9
4-gram | 2.0 | 5.1 | 2.6 | 5.7
Table 5: WERs for test-other split over audio duration. Data | LM | Duration
---|---|---
<10s | 10-15s | 15-20s | >20s
CV | - | 46.6 | 83.6 | 99.1 | 99.9
4-gram | 15.6 | 54.7 | 93.3 | 98.7
CV | - | 43.5 | 38.6 | 41.3 | 47.7
$\to$ CV+VP | 4-gram | 17.0 | 15.2 | 17.2 | 20.8
CV+VP | - | 48.2 | 47.3 | 52.8 | 63.5
$\to$ CV | 4-gram | 17.9 | 18.8 | 23.0 | 33.3

##  8 Pseudo-labeling the wrong language

To our surprise, we found that training a monolingual speech recognizer by
pseudo-labeling the wrong language could also improve test performance. Fig.
11 shows the validation CER of CV Greek when no unlabeled data, unlabeled data
in the right language (VP Greek), and unlabeled data in the wrong language (VP
English) is used.

$0$$0.5$$1$$1.5$$2$$\cdot 10^{5}$$20$$40$$60$# updatesCERLabeled = CV Greek,
Unlabeled = —Labeled = CV Greek, Unlabeled = VP GreekLabeled = CV Greek,
Unlabeled = VP English Figure 11: Validation CER for CV Greek for purely
supervised monolingual training on CV Greek, using VP Greek as unlabeled data
for slimIPL, or using VP English as unlabeled data.

This result may not currently be of much practical interest, since we can
easily train a better monolingual Greek speech recognizer through other
methods (Table 1). Still, we believe it may be useful for understanding how
and why semi-supervised learning works, and we hope to explore the phenomenon
for more language pairs in the future.

##  9 Conclusion

We have demonstrated the use of pseudo-labeling to improve an end-to-end joint
model for massively multilingual ASR with Common Voice. Fine-tuning a
multilingual model with semi-supervised learning on each language of VoxPopuli
separately, and then training on all VoxPopuli pseudo-labels combined, i)
significantly improves the performance of the model for those 19 languages,
ii) helps the model generalize to a new domain (LibriSpeech), and iii) enables
training a larger model than was possible with Common Voice alone without
overfitting. Many interesting questions and problems remain, such as reducing
the gap between the performance of the multilingual model on its own and after
fine-tuning on a particular language, improving performance for languages
without unlabeled data, integrating language models into the PL generation
process, and running iterative pseudo-labeling instead of a single round with
all languages. The method we have employed requires knowledge of which
language is spoken in the unlabeled audio: overcoming this requirement, so
that even more data in the wild can be used, would also be worth exploring.

## References

  * [1] Tanja Schultz et al.,  “Multilingual and crosslingual speech recognition,”  in DARPA BNTU Workshop, 1998.
  * [2] Vineel Pratap et al.,  “Massively multilingual ASR: 50 languages, 1 model, 1 billion parameters,”  Interspeech, 2020.
  * [3] Dong-Hyun Lee,  “Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks,”  in ICML Workshop on Rep. Learning, 2013.
  * [4] Gabriel Synnaeve et al.,  “End-to-end ASR: from supervised to semi-supervised learning with modern architectures,”  ICML SAS Workshop, 2020.
  * [5] Yu Zhang et al.,  “Pushing the limits of semi-supervised learning for automatic speech recognition,”  arXiv, 2020.
  * [6] Qiantong Xu et al.,  “Self-training and pre-training are complementary for speech recognition,”  in ICASSP, 2021.
  * [7] Qiantong Xu et al.,  “Iterative pseudo-labeling for speech recognition,”  Interspeech, 2020.
  * [8] Yosuke Higuchi et al.,  “Momentum pseudo-labeling for semi-supervised speech recognition,”  Interspeech, 2021.
  * [9] Tatiana Likhomanenko et al.,  “slimIPL: Language-Model-Free Iterative Pseudo-Labeling,”  Interspeech, 2021.
  * [10] Jacob Kahn et al.,  “Self-training for end-to-end speech recognition,”  in ICASSP, 2020.
  * [11] Daniel S Park et al.,  “Improved noisy student training for automatic speech recognition,”  Interspeech, 2020.
  * [12] Rosana Ardila et al.,  “Common Voice: A Massively-Multilingual Speech Corpus,”  LREC, 2020.
  * [13] Changhan Wang et al.,  “VoxPopuli: A large-scale multilingual speech corpus for representation learning, semi-supervised learning and interpretation,”  ACL, 2021.
  * [14] V. Panayotov et al.,  “LibriSpeech: an ASR corpus based on public domain audio books,”  in ICASSP, 2015.
  * [15] Peter Shaw et al.,  “Self-attention with relative position representations,”  NAACL, 2018.
  * [16] Alex Graves et al.,  “Connectionist temporal classification: labelling unsegmented sequence data with recurrent neural networks,”  in ICML, 2006, pp. 369–376.
  * [17] Markus Müller et al.,  “Phonemic and graphemic multilingual CTC based speech recognition,”  arXiv, 2017.
  * [18] Sibo Tong et al.,  “Cross-lingual adaptation of a CTC-based multilingual acoustic model,”  Speech Communication, vol. 104, pp. 39–46, 2018.
  * [19] Alexis Conneau et al.,  “Unsupervised cross-lingual representation learning for speech recognition,”  arXiv, 2020.
  * [20] Oliver Adams et al.,  “Massively multilingual adversarial speech recognition,” 2019.
  * [21] Anjuli Kannan et al.,  “Large-scale multilingual speech recognition with a streaming end-to-end model,”  Interspeech, 2019.
  * [22] Jaejin Cho et al.,  “Multilingual sequence-to-sequence speech recognition: architecture, transfer learning, and language modeling,” 2018.
  * [23] Bo Li et al.,  “Bytes are all you need: End-to-end multilingual speech recognition and synthesis with bytes,” 2018.
  * [24] Wenxin Hou et al.,  “Large-scale end-to-end multilingual speech recognition and language identification with multi-task learning,”  in Interspeech, 2020.
  * [25] Rohit Prabhavalkar et al.,  “A comparison of sequence-to-sequence models for speech recognition.,”  in Interspeech, 2017, pp. 939–943.
  * [26] Jan Chorowski et al.,  “Attention-based models for speech recognition,”  NeurIPS, 2015.
  * [27] William Chan et al.,  “Listen, attend and spell: A neural network for large vocabulary conversational speech recognition,”  in ICASSP, 2016.
  * [28] Alex Graves,  “Sequence transduction with recurrent neural networks,”  ICML Rep. Learn. Workshop, 2012.
  * [29] Yanzhang He et al.,  “Streaming end-to-end speech recognition for mobile devices,”  in ICASSP, 2019.
  * [30] Alexei Baevski et al.,  “wav2vec 2.0: A framework for self-supervised learning of speech representations,”  NeurIPS, 2020.
  * [31] Tatiana Likhomanenko et al.,  “Rethinking evaluation in ASR: Are our models robust enough?,”  Interspeech, 2021.
  * [32] Daniel S Park et al.,  “SpecAugment: A simple data augmentation method for automatic speech recognition,”  Interspeech, 2019.
  * [33] Shubham Toshniwal et al.,  “Multilingual speech recognition with a single end-to-end model,”  in ICASSP, 2018.
  * [34] Golnaz Ghiasi et al.,  “Multi-task self-training for learning general representations,”  in Proceedings of the IEEE/CVF International Conference on Computer Vision, 2021, pp. 8856–8865.
  * [35] Tatiana Likhomanenko et al.,  “CAPE: Encoding relative positions with continuous augmented positional embeddings,”  NeurIPS, 2021.
  * [36] Chung-Cheng Chiu et al.,  “RNN-T models fail to generalize to out-of-domain audio: Causes and solutions,”  in SLT Workshop, 2021.