0.25pt 20

# OTOv3: Automatic Architecture-Agnostic Neural Network Training and
Compression from Structured Pruning to Erasing Operators

Tianyi Chen<EMAIL_ADDRESS>
Microsoft
Redmond, WA 98052, USA Tianyu Ding<EMAIL_ADDRESS>
Microsoft
Redmond, WA 98052, USA Zhihui Zhu<EMAIL_ADDRESS>
The Ohio State of University
Columbus, OH 43210, USA Zeyu Chen<EMAIL_ADDRESS>
Microsoft
Redmond, WA 98052, USA HsiangTao Wu<EMAIL_ADDRESS>
Microsoft
Redmond, WA 98052, USA Ilya Zharkov<EMAIL_ADDRESS>
Microsoft
Redmond, WA 98052, USA Luming Liang<EMAIL_ADDRESS>
Microsoft
Redmond, WA 98052, USA

###### Abstract

Compressing a predefined deep neural network (DNN) into a compact sub-network
with competitive performance is crucial in the efficient machine learning
realm. This topic spans various techniques, from structured pruning to neural
architecture search, encompassing both pruning and erasing operators
perspectives. Despite advancements, existing methods suffers from complex,
multi-stage processes that demand substantial engineering and domain
knowledge, limiting their broader applications. We introduce the third-
generation Only-Train-Once (OTOv3), which first automatically trains and
compresses a general DNN through pruning and erasing operations, creating a
compact and competitive sub-network without the need of fine-tuning. OTOv3
simplifies and automates the training and compression process, minimizes the
engineering efforts required from users. It offers key technological
advancements: (i) automatic search space construction for general DNNs based
on dependency graph analysis; (ii) Dual Half-Space Projected Gradient (DHSPG)
and its enhanced version with hierarchical search (H2SPG) to reliably solve
(hierarchical) structured sparsity problems and ensure sub-network validity;
and (iii) automated sub-network construction using solutions from DHSPG/H2SPG
and dependency graphs. Our empirical results demonstrate OTOv3’s effectiveness
across various benchmarks in structured pruning and neural architecture
search. OTOv3 produces sub-networks that match or exceed the state-of-the-
arts. The source code will be available at
https://github.com/tianyic/only_train_once.

Keywords: DNN Training and Compression, Architecture Agnostic, Structured
Pruning, Erase Operator, Structured Sparse Optimization, AutoML.

OTOv3 Library Usage

1 from only_train_once import OTO

2 # Target general DNN

3 oto = OTO(dnn, compress_mode)

4 # Structurally prune operators

5 optimizer = oto.dhspg()

6 # Erase operators

7 optimizer = oto.h2spg()

8 # Train as normal

9 optimizer.step()

10 # Construct sub-network

11 oto.construct_subnet()

Figure 1:  Overview of OTOv3. OTOv3 is the first to support two modes of
architecture-agnostic and automated training and compression, i.e., pruning
and erase modes, to deliver high-performing compact sub-networks starting from
a predefined DNN. (i) Pruning mode slims the operators via eliminating the
inherent redundant structures, yet keeps the presence of operators and
connections. (ii) Erasing mode removes the redundant operators entirely to
dramatically simplify the DNN architecture. The library is user-friendly that
requires minimal engineering efforts from the end-users.

##  1 Introduction

Large-scale Deep Neural Networks (DNNs) have proven to be highly effective
across various applications (He et al., 2016). However, deploying these
substantial networks in environments with limited resources presents
significant challenges. As a result, both academic and industry increasingly
focus on compressing DNNs into more compact versions with minimal performance
loss. Despite a decade of research in the compression field, the complete
resolution remains an ongoing endeavor.

From the view of computational graph, the compression of DNNs could be largely
considered as either pruning or erasing the existing operators to construct
high-performing compact sub-networks. The former one is mainly studied via the
structured pruning realm, which preserves the pre-defined architecture, yet
slims each operator (Chen et al., 2021b, 2023b; Fang et al., 2023). The latter
one is mainly studied via the gradient-based and several zero-shot Neural
Architecture Search (NAS) methods that identify less important operators from
a super-network that covers all candidate operators and connections (Liu et
al., 2018; Yang et al., 2020; Xu et al., 2019; Chen et al., 2021d).

Despite the advancements in both structured pruning and NAS methods, their
usage is still limited due to certain inconvenience. In particular, these
methods predominantly rely on manually determining the search space (see
formal definitions in Section 3) for a pre-specified DNN beforehand, and
require the manual establishment of the whole searching / pruning pipeline.
The whole process necessitates significant domain-knowledge and engineering
efforts, thereby being inconvenient and time-consuming for users. Therefore,
it is natural to ask whether we could reach an

Objective. Given a general DNN that covers all candidate operators and
connections, automatically generate its search space, train it once, and
construct a high-performing compact sub-network.

Achieving the objective is severely challenging in terms of both engineering
developments and algorithmic designs, consequently rarely achieved by the
existing structured pruning and NAS works to our knowledge111For automatic
pruning, OTOv2 (Chen et al., 2023b) and DepGraph (Fang et al., 2023) are
arguably the first two works which appeared almost at the same time to achieve
architecture-agnostic structured pruning.. We now build the third generation
of Only-Train-Once (OTOv3) that first reaches the objective from both pruning
and erasing manners. Given a DNN that covers all operation and connection
candidates, OTOv3 automatically generates search spaces for either pruning or
erasing operator mode, trains and identifies redundant minimally removal
structures, then builds a sub-network that achieves both high performance and
compactness, as Figure 1. The whole procedure is automatically proceeded,
dramatically reduce human efforts, and fits general DNNs and applications.

| OTOv3 | Other Pruning | Other NAS⋆
---|---|---|---
General DNNs |  TextRenderingMode=FillStroke, LineWidth=.5pt, ✓ | ✓ – | ✓ –
Autonomy |  TextRenderingMode=FillStroke, LineWidth=.5pt, ✓ |  ✗† |  ✗‡
Prune Operations |  TextRenderingMode=FillStroke, LineWidth=.5pt, ✓ |  TextRenderingMode=FillStroke, LineWidth=.5pt, ✓ | ✗
Erase Operations |  TextRenderingMode=FillStroke, LineWidth=.5pt, ✓ | ✗ |  TextRenderingMode=FillStroke, LineWidth=.5pt, ✓
⋆ Refer to gradient-based and a subset of zero-shot NAS.
† Except Torch-Pruning (Fang et al., 2023).
‡ Require manually construct search space.

Technologically, this paper serves as a non-trivial and significant extension
of OTOv2 (Chen et al., 2023b) (automated structured pruning) to present a
unified framework, enables architecture-agnostic DNN training and compression
from both pruning and erasing operator perspectives. Compared with OTOv2,
OTOv3 explores an entirely new application domain to automatically erase
redundant operators, which presence are preserved in structured pruning, along
with significant novel technical and practical contributions from both
algorithmic designs and infrastructure developments. OTOv3 also bridges to the
gradient-based NAS field and resolves one of their main pain points of
handcrafting search space beforehand upon a pre-defined DNN. In the remaining
of the paper, we will summarize the main context from OTOv2 with more
insights, yet concentrate and highlight more on the novel takeaways in the
erasing operator feature. Our main contributions can be summarized as follows.

  * •

Infrastructure for Automated Architecture-Agnostic DNN Training and
Compression. We propose OTOv3 that is the first to automatically train and
compress a general DNN to deliver a compact sub-network by pruning and erasing
redundant operations in the one-shot manner. As the previous OTO versions,
OTOv3 trains the DNNs only once without the need of pre-training and fine-
tuning, and is pluggable into various deep learning applications.

  * •

Automated Search Space Generation via Dependency Graph Analysis. We propose
distinct novel graph algorithms to automatically exploit the architecture and
establish pruning and erasing dependency graphs for separate compression
purpose given a predefined DNN. The dependency graphs analyze the hierarchy
and dependency across different operators to form search spaces for different
compression modes. The search spaces consist of the pruning or erasing
minimally removal structures that could be removed without interrupting the
functionality of the sub-networks.

  * •

Dual Half-Space Projected Gradient (DHSPG) for Pruning Mode. We propose a
novel sparse optimizer DHSPG, to train and structurally prune a general DNN.
DHSPG formulates a constrained structured sparse optimization problem and
solves it by modular redundant identification and a hybrid training schema.
Compared with HSPG in OTOv1 and other sparse optimizers, DHSPG outperforms
them in terms of more reliably sparsity control and better generalization.

  * •

Hierarchical Half-Space Projected Gradient (H2SPG) for Erasing Mode. We
further propose a novel H2SPG for erasing operators. H2SPG is perhaps the
first optimizer, that solves a hierarchical structured sparsity problem for
general DNN applications. Compared to DHSPG and other sparse optimizers, H2SPG
conducts a dedicated hierarchical search phase over the generated erasing
search space to ensures the validness of the sub-network after erasing
redundant operators.

  * •

Automated Sub-Network Construction. We propose novel graph algorithms to
automatically construct sub-networks upon the solution of DHSPG or H2SPG for
pruning and erasing operator perspectives. The resulting sub-network returns
the exact same outputs as the full networks thereby being no need of further
fine-tuning.

##  2 Related Works

#### Structured Pruning.

To compress DNN architectures, structured pruning shrinks the operators while
preserves their presence via identifying and removing redundant inherent
structures (Gale et al., 2019; Han et al., 2015; Lin et al., 2019; Wen et al.,
2016). The general procedure (Li et al., 2023b) can be largely summarized as:
(i) train a full model; (ii) identify and remove the redundant structures to
construct a slimmer DNN based on various criteria, including sparsity (Lin et
al., 2019; Wen et al., 2016; Li et al., 2020b; Zhuang et al., 2020; Chen et
al., 2017, 2018, 2021a, 2020a; Gao et al., 2020; Zhuang et al., 2020; Meng et
al., 2020; Yang et al., 2019; Frantar and Alistarh, 2023; Idelbayev and
Carreira-Perpiñán, 2022), Bayesian pruning (Zhou et al., 2019; van Baalen et
al., 2020), ranking importance (Li et al., 2020a; Hu et al., 2016; Li et al.,
2019; Zhang et al., 2018), grouped kernel search Zhong et al. (2023), spectral
graph analysis (Laenen, 2023), reinforcement learning (He et al., 2018b; Chen
et al., 2019a), lottery ticket (Frankle and Carbin, 2018; Frankle et al.,
2019; Renda et al., 2020), etc.; (iii) retrain the pruned model to regain the
accuracy regression during pruning if needed with(out) knowledge distillation
(Ham et al., 2023). These methods have to conduct a complicated and time-
consuming procedure to trains the DNN multiple times and requires a good deal
of domain knowledge to manually proceed every individual step. OTOv1 (Chen et
al., 2021b) is then proposed to avoid fine-tuning and end-to-end train and
compress the DNN once. However, these methods requires numerous handcrafting
efforts on discovering the removal structures and constructing slimmer model
for specific DNNs in advance, thereby is not convenient. Recent methods such
as OTOv2 (Chen et al., 2023b) and DepGraph (Fang et al., 2023) made progress
in automating the structure pruning process for general DNNs. OTOv2 is a one-
shot training and pruning framework that does not need pre-training or fine-
tuning. DepGraph focuses on pruning, hence requires integrating with a multi-
stage training pipeline. In this work, we propose the third-generation version
of OTO that significantly enhances the existing pruning mode of OTOv2 from the
engineering perspective and extends it to a new application domain to
automatically erase redundant operators entirely.

#### Neural Architecture Search (NAS) for Erasing Operators.

Erasing redundant operators in a pre-defined DNN to search an optimal sub-
network has been studied as a pivotal topic in the NAS realm. There exists
gradient-based methods (Liu et al., 2018; Chen et al., 2019b; Xu et al., 2019;
Yang et al., 2020; Hosseini and Xie, 2022) and zero-shot methods (Chen et al.,
2021c; Li et al., 2023a) that start with a network covering all possible
connection and operation candidates to find important operators to form a sub-
network. However, similarly to the structured pruning realm, these methods
require a significant amount of handcraftness from users in advance to
manually establish the search space, introduce additional architecture
variables, and build the multi-level training pipeline. The sub-network
construction is also network-specific and not flexible. All requirements
necessitate remarkable domain-knowledge and expertise, making it difficult to
extend to broader scenarios.

#### Automated Search Space Generation.

One main pain-point of the existing structured pruning and NAS methods is the
need of manually establishing the search space. The definition of search space
is varying upon different scenarios. In our scenario, we aim to automatically
discovering a high-performing compact sub-network given a heavier general DNN.
The starting DNN is assumed to cover all operation and connection candidates,
and the resulting sub-network serves as its sub-computational-graph.
Therefore, the search space of our scenario is defined as a set of minimally
removal structures of the given DNN in distinct compression modes (see
Definition 3).

There exists orthogonal search-space definitions, along with works in
automation. In the context of (Cai et al., 2019; Munoz et al., 2022;
Radosavovic et al., 2020; Calhas et al., 2022), the presence of operators in
DNNs is preserved, yet their inherent hyperparameters, such as stride and
depth for convolution, are searchable. Consequently, the inherent
hyperparameters of the operators constitute their search spaces. Zhou et al.
(2021) defines the search space as the network that encompasses all candidate
operations and investigates to automatically generate high-quality super-
networks that include optimal sub-networks. OTOv3 studies the automation for
two distinct and important search spaces to prune and erase operators. It
stays complementary to other methods and softwares and could operate jointly
to form the landscape of automated search-space generation and automated
machine learning (Liu et al., 2020; Xu et al., 2021; Pedregosa et al., 2011;
Kolter et al., 2021).

##  3 Preliminaries

We review preliminary concepts used throughout the paper. To compress a DNN,
we need to identify or search a set of redundant structures, removing them to
construct a compact high-performing sub-network. Due to the complicated
connectivity of DNNs, removing an arbitrary structure may result in an invalid
DNN. Consequently, the first concept is so-called removal structure.

######  Definition 1 (Removal Structure)

Given a deep neural network $\mathcal{M}$, a structure is said removal
structure if and only if the neural network without it is still functioning
normally.

One removal structure may contain multiple individually instances. Searching
redundancy over a large removal structure may result in sub-optimal sub-
network. To enlarge search space, we further introduce the minimally removal
structure that describes the minimal units of one removal structure.

######  Definition 2 (Minimally Removal Structure)

Given a deep neural network $\mathcal{M}$, a minimally removal structure is a
removal structure that can not decompose into multiple removal structures.

Now, we formally define the search space of compressing DNN via pruning and
erasing operators.

######  Definition 3 (Search Space for DNN Compression)

Given a DNN $\mathcal{M}$, the search space for training and compression
$\mathcal{M}$ via pruning and erasing operators is the set of minimally
removal structures.

The definition of search space is varying upon distinct scenarios (see more in
Section 2). In our compression context, the search space is defined as the set
of minimally removal structures that can be omitted from the given DNN while
ensuring that the remaining network continues to function normally.
Furthermore, to train only once without the need of fine-tuning after
compression, we introduce the zero-invariant group (ZIG) in OTOv1 (Chen et
al., 2021b).

######  Definition 4 (Zero Invariant Group)

The trainable variables of one minimally removal structure form a zero-
invariant group if and only if these trainable variables being zero results in
the minimally removal structure always returning output tensors as zero given
arbitrary inputs.

ZIG describes a class of minimally removal structures such that their
variables parameterized as zero ensure the output tensors as zero, thereby
contributing none to the DNN outputs. During DNN compression, the redundant
ZIGs are eventually projected onto zero, which structures could be further
removed without affecting the model output, thereby avoiding the need of
further fine-tuning.

#### Remark.

Upon different compression purpose, the form of minimally removal structure is
varying and requires distinct dedicately designed graph algorithms to
automatically discover. For clarification, we introduce pruning minimally
removal structures and erasing minimally removal structures for the pruning
and erasing compression modes, respectively. Similarly, we have pruning search
space and erasing search space along with pruning zero-invariant groups
(PZIGs) and erasing zero-invariant groups (EZIGs) to distinguish separate
compression modes.

##  4 Overview of OTOv3

Algorithm 1 Outline of OTOv3.

1:Input: A DNN $\mathcal{M}$ to be trained and compressed (no need to be
pretrained), a compression mode $\in\\{\text{prune},\text{erase}\\}$, and a
target sparsity level $K$.

2:Automated Search Space Generation. Create dependency graphs for
$\mathcal{M}$, generate a search space upon the compression mode, and
partition the trainable variables into a set of groups $\mathcal{G}$.

3:Train $\mathcal{M}$ by DHSPG or H2SPG. Select the sparse optimizer upon the
predefined compression mode. Then seek a high-performing solution with desired
(hierarchical) group sparsity $K$.

4:Automated Sub-Network Construction. Construct a sub-network
$\mathcal{M}^{*}$ upon solution of DHSPG or H2SPG and the selected compression
mode.

5:Output: Constructed sub-network $\mathcal{M}^{*}$. (Post fine-tuning is
optional).

Given a deep neural network $\mathcal{M}$, OTOv3 establishes a unified
paradigm to conduct training and compression via both structured pruning and
erasing operators as diagrammed in Figure 1. As outlined in Algorithm 1, the
end-users firstly need to select a compression mode via either pruning or
erasing. Upon the selected mode, OTOv3 then automatically analyzes the
relationships among the operators via distinct dependency graph algorithms to
establish corresponding search space (Section 5.1 or 6.1). The search spaces
consist of minimally removal structures (Definition 3) for different purposes.
Their trainable variables are then partitioned into different sets of groups
(including zero-invariant groups (ZIGs) and the complementary)
$\mathcal{G}_{\text{prune}}$ and $\mathcal{G}_{\text{erase}}$ for pruning or
erasing mode, respectively.

To identify redundant minimally removal structures and train the important
ones for high-performance, separately distinct structured sparsity
optimization problems are formulated for pruning and erasing mode over
$\mathcal{G}_{\text{prune}}$ and $\mathcal{G}_{\text{erase}}$, respectively.
For pruning mode, the optimization problem is a disjoint group sparse problem
and solved via a Dual Half-Space Projected Gradient (DHSPG) method to yield a
solution $\bm{x}^{*}_{{\text{DHSPG{}}}}$ with competitive performance as well
as high group sparsity in the view of $\mathcal{G}_{\text{prune}}$ (Section
5.2). For erasing mode, the problem becomes a more challenging hierarchical
group sparse problem, wherein the sparsity must be yielded obeying the
hierarchy to ensure the validity of the remaining network. We propose a novel
Hierarchical Half-Space Projected Gradient (H2SPG) to effectively solve it and
return a solution $\bm{x}^{*}_{{\text{H2SPG{}}}}$ with both high-performance
and desired hierarchical sparsity (Section 6.2). In the end, sub-networks
$\mathcal{M}^{*}_{\text{prune}}$ and $\mathcal{M}^{*}_{\text{erase}}$ are
automatically constructed by removing corresponding redundant structures upon
the selected mode and the solutions $\bm{x}^{*}_{{\text{DHSPG{}}}}$ and
$\bm{x}^{*}_{{\text{H2SPG{}}}}$ from DHSPG and H2SPG (Section 5.3 and 6.3).
Post fine-tuning is optional and typically no needed especially if all
variable groups are all zero-invariant groups. The whole procedure is
proceeded automatically and easily employed onto various DNN applications, and
consumes almost minimal engineering efforts from the users.

Figure 2: A demo DNN (DemoNet) to be trained and compressed.

##  5 OTOv3 for Structured Pruning

The first application domain of OTOv3 is to automatically train a general DNN
only once and simultaneously structurally prune the operators to deliver a
high-performing compact sub-network. The main context has been covered in
OTOv2 (Chen et al., 2023b). In this section, we reorganize the method
presentation with deeper insights and more elaborations.

###  5.1 Automatic Pruning Search Space Generation for Pruning Mode

(a) During constructing pruning dependency graph.

(b) Pruning dependency graph.

(c) Pruning zero-invariant groups (PZIGs) and the complementary.

Figure 3: Automated PZIG partition. $\widehat{\bm{\mathcal{K}}}_{i}$ and
$\bm{b}_{i}$ are the flatten filter matrix and bias vector of Conv$i$, where
the $j$th row of $\widehat{\bm{\mathcal{K}}}_{i}$ represents the $j$th 3D
filter. $\bm{\gamma}_{i}$ and $\bm{\beta}_{i}$ are the weighting and bias
vectors of BN$i$. $\bm{\mathcal{W}}_{i}$ is the weighting matrix for
Linear$i$. PZIGs are present in Figure 3(c). Since the output tensors of Conv5
and Conv6 are added together, both layers associated with BN5 must remove the
same number of filters from $\widehat{\bm{\mathcal{K}}}_{5}$ and
$\widehat{\bm{\mathcal{K}}}_{6}$ and scalars from
$\bm{\gamma}_{5},\bm{\beta}_{5}$ to keep the addition valid. Since BN6
normalizes the concatenated outputs along channel from Conv2-BN2 to Conv4-BN4,
the corresponding scalars in $\bm{\gamma}_{6},\bm{\beta}_{6}$ need to be
grouped into these node groups accordingly.

As described in Section 4, the foremost step is to establish a search space
for structured pruning that consists of pruning minimally removal structures.
Unlike the existing works that manually find them out, we propose a graph
algorithm to achieve automated construction, stated in Algorithm 2. We
elaborate the algorithm over a shallow yet complex DemoNet depicted in Figure
2.

#### Roles of Vertices / Operators.

We begin by constructing the trace graph $(\mathcal{E},\mathcal{V})$ for the
target DNN. In this graph, each vertex in $\mathcal{V}$ represents a specific
operator, while the edges in $\mathcal{E}$ illustrate the connections between
these operators (line 3 in Algorithm 2). The vertices are categorized into
four types: stem, joint, accessory, and unknown. Stem vertices, equipped with
trainable parameters, are capable of transforming input tensors into different
shapes. Examples include operators like Conv and Linear. Joint vertices, such
as Add, Mul, and Concat, combine multiple input tensors into a single output.
Accessory vertices manipulate a single input tensor to produce a single output
and may also have trainable parameters, like BatchNorm and ReLu. Lastly,
unknown vertices perform unseen operations. Notably, stem vertices constitute
the majority of the DNN’s parameters. Joint vertices, on the other hand,
create connections across different vertices, adding hierarchy and complexity
to the DNN. To maintain the integrity of the joint vertices, minimal removal
structures must be meticulously devised. Moreover, joint vertices are further
categorized based on their dependency on input shape. Vertices requiring
inputs of identical shapes, such as Add, are labeled as shape-dependent (SD),
otherwise being shape-independent (SID) such as Concat along the channel
dimension for multiple Conv layers as input.

Algorithm 2 Automated Pruning Search Space Construction.

1:Input: A DNN $\mathcal{M}$ to be trained and compressed.

2:Construct the trace graph $(\mathcal{V},\mathcal{E})$ of $\mathcal{M}$.

3:Find node groups $\mathcal{N}$ over all accessory, shape-dependent joint and
unknown vertices.

4:Grow $\mathcal{N}$ till incoming nodes are either stem or shape-independent
joint vertices.

5:Merge node groups in $\mathcal{N}$ if any intersection.

6:Group pairwise parameters of stem vertices in the same node groups
associated with parameters from affiliated accessory vertices if any as one
PZIG into $\mathcal{G}_{\text{PZIG}}$.

7:Group parameters in the remaining vertices into
$\mathcal{G}_{\text{PZIG}}^{C}$.

8:Return variable groups partitions
$\mathcal{G}_{\text{prune}}\leftarrow\mathcal{G}_{\text{PZIG}}\cup\mathcal{G}_{\text{PZIG}}^{C}$.

#### Pruning Dependency Graph.

To identify the pruning minimal removal structures in the pruning mode of the
target DNN, we begin by analyzing the dependencies between the vertices. Our
first step is to connect accessory, shape-dependent (SD) joint, and unknown
vertices that are adjacent to form a set of node groups $\mathcal{N}$ (line 3
of Algorithm 2). This step lays the foundation for identifying interdependent
vertices when contemplating the removal of hidden structures. The rationale
behind this step is threefold: (i) the adjacent accessory vertices operate and
are subject to the same ancestral stem vertices if any; (ii) SD joint vertices
force their ancestral stem vertices dependent on each other to yield tensors
in the same shapes; and (iii) unknown vertices introduce uncertainty, making
it essential to identify potentially affected vertices. Following this, we
expand $\mathcal{N}$ to include all incoming vertices that are either stem or
shape-independent (SID) joint vertices (lines 4-5). Remark here that the newly
incorporated stem vertices are associated with the accessory vertices. For
example, in Figure 3(a), Conv2 is affiliated with BN2, and Conv3 is affiliated
with BN3. Furthermore, SID joint vertices play a significant role in
establishing dependencies. They not only link their affiliated accessory
vertices but also connect with incoming components. For instance, Concat-BN6’s
dependency on Conv2-BN2, Conv3-BN3, and Conv4-BN4 arises because BN6
normalizes the concatenated tensors along the channel dimension. Finally, the
pruning dependency graph is constructed as Figure 3(b), wherein the vertices
in the same node group (marked as the same color) imply the interdependency
during structured pruning to ensure the validity of produced subnetwork.

#### Pruning Zero-Invariant Group Partition.

We finally partition the trainable variables upon the pruning minimally
removal structures into pruning zero-invariant groups (PZIGs) based on the
pruning dependency graph. The process begins by grouping together the pairwise
trainable variables of all individual stem and accessory vertices within the
same node group (marked by the same color in Figure 3(c)). Some accessory
vertices like BN6 may rely on multiple groups due to their connections with
SID joint vertices. Consequently, the trainable variables are divided and
added separately into the corresponding groups, e.g.,
$(\bm{\gamma}_{6}^{2},\bm{\beta}_{6}^{2})-(\bm{\gamma}_{6}^{4},\bm{\beta}_{6}^{4})$.
Furthermore, we exclude node groups adjacent to DNN output from forming PZIGs
to preserve the output shapes, as exemplified by Linear2. For safety and to
ensure the framework generality when applied to DNNs with custom operators,
node groups containing unknown vertices are also excluded due to the
uncertainty associated with these vertices. Finally, the pruning zero-
invariant groups $\mathcal{G}_{\text{PZIG}}$ are unioned with the remaining
unprunable variable groups $\mathcal{G}_{\text{PZIG}}^{C}$ to form the overall
variable partition $\mathcal{G}_{\text{prune}}$ in the pruning mode.

###  5.2 Dual Half-Space Projected Gradient (DHSPG)

#### Target Problem.

Given the variable partition $\mathcal{G}_{\text{prune}}$ by Algorithm 2, the
next is to jointly search which groups in $\mathcal{G}_{\text{PZIG}}$ are
redundant to be removed and train the remaining groups to achieve high
performance. To tackle it, we construct a structured sparsity optimization
problem formulated as (1). Besides minimizing the objective function $f$, we
introduce an additional sparsity constraint to yield $K$ of the PZIGs being
zero, wherein the zero groups refer to the redundant structures, and the non-
zero groups exhibit the prediction power to maintain competitive performance
to the full model.

${\displaystyle\mathop{\operator@font{minimize}}_{\bm{x}\in\mathbb{R}^{n}}}\
f(\bm{x}),\ \ \text{s.t.}\ \text{Cardinality}\\{g\ |\
[\bm{x}]_{g}=\bm{0},g\in\mathcal{G}_{\text{PZIG}}\\}=K.\vspace{-1mm}$ (1)

Problem (1) is solved via a novel DHSPG (outlined as Algorithm 3). Compared
with HSPG (Chen et al., 2020b, 2021b), DHSPG employs saliency-driven redundant
identification and a hybrid training paradigm to more reliably control the
sparsity and achieve better generalization performance.

Algorithm 3 Dual Half-Space Projected Gradient (DHSPG)

1:Input: initial variable $\bm{x}_{0}\in\mathbb{R}^{n}$, initial learning rate
$\alpha_{0}$, warm-up steps $T$, target group sparsity $K$, group partition
$\mathcal{G}_{\text{prune}}$, and the optimization variant $\mathcal{OPT}$.

2:Warm up $T$ steps via the selected $\mathcal{OPT}$.

3:Separate $\mathcal{G}_{\text{redundant}}$ and
$\mathcal{G}_{\text{important}}$ given $\mathcal{G}_{\text{prune}}$ and $K$.

4:for $t=T,T+1,T+2,\cdots,$ do

5: Compute gradient estimate $\nabla\\!f(\bm{x}_{t})$ based on
$\mathcal{OPT}$.

6: Update $[\bm{x}_{t+1}]_{\mathcal{G}_{\text{important}}}$ as
$[\bm{x}_{t}-\alpha_{t}\nabla\\!f(\bm{x}_{t})]_{\mathcal{G}_{\text{important}}}.$

7: Select proper $\lambda_{g}$ for $g\in\mathcal{G}_{\text{redundant}}$.

8: Compute $[\tilde{\bm{x}}_{t+1}]_{\mathcal{G}_{\text{redundant}}}$ via
subgradient descent of $\psi$.

9: Perform Half-Space projection over
$[\tilde{\bm{x}}_{t+1}]_{\mathcal{G}_{\text{redundant}}}$.

10: Update
$[\bm{x}_{t+1}]_{\mathcal{G}_{\text{redundant}}}\leftarrow[\tilde{\bm{x}}_{t+1}]_{\mathcal{G}_{\text{redundant}}}$.

11: Update $\alpha_{t+1}$.

12:Return the final iterate $\bm{x}^{*}_{\text{DHSPG{}}}$.

Initiation and Warm-Up. Initially, users are required to configure an
optimization variant for gradient estimation (with supported options including
SGD, Adam, and AdamW). This requirement stems from the anticipation that users
might already possess a well-established training pipeline. In such pipelines,
the baseline optimization consistently yields high performance for the full
model. Therefore, we recommend users to select the same optimization variant
as their existing setup, promoting generality and facilitating ease of
integration. Afterwards, DHSPG undergoes $T$ steps of a warming-up process.
This stage gathers gradient signals, which are instrumental in distinguishing
between redundant and important variable groups.

Redundant Identification. After the warm-up phase, we classify the groups
$\mathcal{G}_{\text{prune}}$ into redundant groups
$\mathcal{G}_{\text{redundant}}$ and important groups
$\mathcal{G}_{\text{important}}\leftarrow\mathcal{G}_{\text{prune}}/\mathcal{G}_{\text{redundant}}$.
To construct this partition, various criteria based on salience scores can be
applied. One could use the cosine similarity $\cos{(\theta_{g})}$ between the
projection direction $-[\bm{x}]_{g}$ and the negative gradient or its
estimation $-[\nabla\\!f(\bm{x})]_{g}$. Higher cos-similarity over
$g\in\mathcal{G}_{\text{PZIG}}$ indicates that projecting the group of
variables in $g$ onto zeros is more likely to make progress to the optimality
of $f$ (considering the descent direction from the perspective of
optimization). Therefore, we identify $\mathcal{G}_{\text{redundant}}$ by
selecting the PZIGs with bottom-$K$ least salience scores and
$\mathcal{G}_{\text{important}}$ as its complementary as (2),

$\mathcal{G}_{\text{redundant}}=(\text{Bottom-K})\mathop{\text{argmax}}_{g\in\mathcal{G}_{\text{PZIG}}}\text{salience-
score}(g)\ \text{and}\
\mathcal{G}_{\text{important}}=\mathcal{G}_{\text{prune}}/\mathcal{G}_{\text{redundant}}.\vspace{-2mm}$
(2)

Figure 4:  Search direction in DHSPG.

Hybrid Training. We then propose a hybrid training schema that applies
distinct update mechanisms to important and redundant variable groups,
diverging from the standard optimization approaches where the same update
schema is uniformly applied to all variables. For the important variable
groups $\mathcal{G}_{\text{important}}$, we seek to achieve competitive
performance, thereby adopt gradient descent using the selected gradient
estimation method like Adam (Kingma and Ba, 2014), i.e.,
$[\bm{x}_{t+1}]_{\mathcal{G}_{\text{important}}}\leftarrow[\bm{x}_{t}-\alpha_{t}\nabla\\!f(\bm{x}_{t})]_{\mathcal{G}_{\text{important}}}$.
For the redundant groups $\mathcal{G}_{\text{redundant}}$, our goal is to
project these redundant variables towards zero for removing the corresponding
pruning minimally removal structures. However, direct projection can disrupt
progress towards the optimum. This issue becomes particularly severe in
applications like Large Language Models (LLMs) (Ding et al., 2023), where
redundant groups may still hold substantial knowledge (Chen et al., 2023a).
Direct projection risks entirely losing this knowledge, which could be
challenging to regain. To address this, we advocate for a progressive approach
that gradually diminishes their magnitudes and projects them onto zero without
impairing the objective to the largest extent. This strategy is termed as
inherent knowledge transfer. Then the update over the redundant groups is
formulated as a non-constrained subproblem as (3).

${\displaystyle\mathop{\operator@font{minimize}}_{[\bm{x}]_{\mathcal{G}_{\text{redundant}}}}}\
\psi([\bm{x}]_{\mathcal{G}_{\text{redundant}}}):=f\left([\bm{x}]_{\mathcal{G}_{\text{redundant}}}\right)+\sum_{g\in\mathcal{G}_{\text{redundant}}}\lambda_{g}\left\|[\bm{x}]_{g}\right\|_{2},$
(3)

where $\lambda_{g}$ is a group-specific regularization coefficient and needs
to be dedicately chosen to guarantee the decrease of both the variable
magnitude for $g$ as well as the objective $f$. In particular, we compute a
negative subgradient of $\psi$ as the search direction
$[\bm{d}(\bm{x})]_{\mathcal{G}_{\text{redundant}}}:=-[\nabla\\!f(\bm{x})]_{\mathcal{G}_{\text{redundant}}}-\sum_{g\in\mathcal{G}_{\text{redundant}}}\lambda_{g}{[\bm{x}]_{g}/\max\\{\left\|[\bm{x}]_{g}\right\|_{2}},\tau\\}$
with $\tau$ as a safeguard constant. To ensure $\bm{d}(\bm{x})$ as a descent
direction for both $f$ and $\left\|\bm{x}\right\|_{2}$, $[\bm{d}(\bm{x})]_{g}$
needs to fall into the intersection between the dual half-spaces with normal
directions as $-[\nabla\\!f]_{g}$ and $-[\bm{x}]_{g}$ for any
$g\in\mathcal{G}_{\text{redundant}}$ as shown in Figure 4. In other words,
$[\bm{d}(\bm{x})]_{g}^{\top}[-\nabla\\!f(\bm{x})]_{g}$ and
$[\bm{d}(\bm{x})]_{g}^{\top}[-\bm{x}]_{g}$ are greater than 0. It further
indicates that $\lambda_{g}$ locates in the interval
$(\lambda_{\text{min},g},\lambda_{\text{max},g}):=\left(-\cos(\theta_{g})\left\|[\nabla\\!f(\bm{x})]_{g}\right\|_{2},-\frac{\left\|[\nabla\\!f(\bm{x})]_{g}\right\|_{2}}{\cos{(\theta_{g})}}\right)$
if $\cos{(\theta_{g})}<0$ otherwise can be an arbitrary positive constant.
Such $\lambda_{g}$ brings the decrease of both the objective and the variable
magnitude. We then compute a trial iterate
$[\tilde{\bm{x}}_{t+1}]_{g}\leftarrow[\bm{x}_{t}-\alpha_{t}\bm{d}(\bm{x}_{t})]_{g}$
via the subgradient descent of $\psi$ as line 8. The trial iterate is fed into
the Half-Space projector (Chen et al., 2021b; Dai et al., 2023) which
outperforms proximal operators to yield group sparsity more productively
without deteriorating the objective as line 15. In the end, we return the
final or the best iterate that reaches target group sparsity $K$ and high-
performance as the solution $\bm{x}_{\text{DHSPG}}^{*}$.

###  5.3 Automatic Structurally Pruned Network Construction

Figure 5: Automated pruned model construction.
$\mathcal{G}=\\{g_{1},g_{2},\cdots,g_{5}\\}$ and
$[\bm{x_{\text{DHSPG{}}{}}}^{*}]_{g_{2}\cup g_{3}\cup g_{4}}=\bm{0}$.

Ultimately, having derived the solution $\bm{x}^{*}_{\text{DHSPG{}}{}}$ that
achieves both high performance and group sparsity, we now move to the
automated construction of a compact model, which is a manual step with
unavoidable substantial engineering efforts in most of structured pruning
works. From an engineering perspective, in OTOv2 (Chen et al., 2023b), the
pruned model is produced in ONNX (developers, 2021) format, which is not
conveniently for the further usage such as quantization if needed. In OTOv3,
we have made a significant engineering achievement to re-design, re-factorize
and re-develop the whole library to produce the pruned model directly in
Pytorch format, which greatly enhance the generality, flexibility, and
coverage. From the algorithmic view, we traverse all vertices with trainable
parameters, then remove the structures in accordance with PZIGs being zero,
such as the dotted rows of
$\widehat{\bm{\mathcal{K}}}_{1},\widehat{\bm{\mathcal{K}}}_{2},\widehat{\bm{\mathcal{K}}}_{3}$
and scalars of $\bm{b}_{2},\bm{\gamma}_{1},\bm{\beta}_{1}$ as illustrated in
Figure 5. Next, we erase the redundant parameters that affiliate with the
removed structures of their incoming stem vertices to keep the operations
valid, e.g., the second and third channels in $g_{5}$ are removed though
$g_{5}$ is not zero. The automated algorithm is promptly complete in linear
time via performing two passes of depth-first-search and manipulating
parameters to produce a more compact model $\mathcal{M}^{*}_{\text{prune}}$.
Based on the property of PZIGs, $\mathcal{M}^{*}_{\text{prune}}$ returns the
same inference outputs as the full $\mathcal{M}$ parameterized as
$\bm{x}^{*}_{\text{DHSPG{}}{}}$, thus no further fine-tuning is necessary.

##  6 OTOv3 for Erasing Operator

The second fresh application domain of OTOv3 is the erasing mode, which aims
at training a general DNN and automatically finding an optimal sub-network via
erasing redundant operators entirely. The resulting sub-network is not only
high-performing but also has a remarkably compact architecture, making it
well-suited for various deployment environments. The erasing mode is closely
related to a popular sub-realm in neural architecture search (NAS) to find an
optimal sub-network given a network that covers all candidate operations and
connections. Compared with these NAS methods (Liu et al., 2018), OTOv3
resolves one of their main pain-points that requires significant handcraftness
and engineering efforts to determine the architecture specific search spaces.
The erasing mode in OTOv3 provides an end-to-end automated solution,
dramatically reduces the necessity for human intervention, and is compatible
with a wide range of DNNs and applications.

#### New Challenges Compared to Pruning Mode.

The erasing mode operates orthogonally to the pruning mode in Section 5 which
preserves all operators yet slims them. Such major difference poses several
new challenges to the erasing mode. First of all, the erasing dependency
across vertices differs from the pruning dependency, requiring a distinct
dependency graph analysis to discover the erasing minimally removal
structures. Secondly, the hierarchy among the discovered erasing minimally
removal structures needs to be additionally taken account, which is crucial to
ensure the validity of the resulting sub-networks, yet discarded in the
pruning mode. Thirdly, topological structure of sub-network in the erasing
mode is dramatically changed, which brings significant challenges into the
sub-network construction component. As a result, each component in the erasing
mode necessitates distinct algorithmic design and engineering developments to
the pruning mode. This makes it not only a substantial extension to a new
application domain but also represents a significant dive in terms of
algorithmic innovation, distinguishing it from the existing works.

###  6.1 Automatic Erasing Search Space Generation for Erasing Mode

Given a pre-defined DNN $\mathcal{M}$, as outlined in Algorithm 1, the initial
step of the erasing mode in OTOv3 is to automatically generate a search space
which is defined as a set of minimally removal structures for the erasing
purpose (see Definition 3). The automated generation of erasing search space
involves two main phases. The first phase explores the trace graph of the DNN
$\mathcal{M}$ and establishes a erasing dependency graph. This graph is
notably different from the pruning dependency graph discussed in Section 5.1
due to the distinct dependent relations in separate compression modes as
presented in Figure 6(a). The second phase leverages the erasing dependency
graph to find out erasing minimally removal structures, then partitions their
trainable variables to a set of erasing zero-invariant groups (EZIGs) and
their unsearchable complementary. For intuitive illustrations, we still use
the DemoNet depicted as Figure 2 to elaborate the erasing search space
generation.

(a) Erasing dependency versus pruning dependency.

(b) Dependency graph for erasing operator.

(c) Trainable variable partition.

Figure 6:  Automated Search Space Generation. Given the DemoNet to be trained
and compressed in the erasing mode, (a) the constructed dependency graph for
erasing mode; and (b) the trainable variable partition, where
$\mathcal{G}_{s}$ represents the variable groups corresponding to removal
structures. $\bm{\widehat{\mathcal{K}}}_{i}$ and $\bm{b}_{i}$ are the flatten
filter matrix and bias vector for Conv-i, respectively. $\bm{\gamma}_{i}$ and
$\bm{\beta}_{i}$ are the weight and bias vectors for BN-i.
$\bm{{\mathcal{W}}}_{i}$ is the weight matrix for Linear-i. The columns of
$\bm{\widehat{\mathcal{K}}}_{6}$ are marked in accordance to its incoming
segments.

#### Erasing Dependency versus Pruning Dependency.

The erasing dependency is distinct from the pruning dependency. As drawn in
Figure 6(a), the same operators may behave distinctly regarding dependency in
different modes. For example, in pruning mode, the joint operators, e.g., Add
and Mul, introduce dependency across their incoming stem vertices to be pruned
together, whereas in the erasing mode, their incoming stem vertices could
operate independently. Another difference is in the treatment of consecutive
stem vertices along the single path. In the pruning mode, these vertices need
to form separate node groups. In contrast, during the erasing mode, they must
be considered as a unified group. This is because erasing any of these
vertices would result in the remaining ones being disconnected from either the
input or the output of the DNN, thereby rendering the network invalid.

#### Erasing Dependency Graph.

Algorithm 4 Automated Erasing Search Space Generation.

1:Input: A neural network $\mathcal{M}$ to be trained and compressed via
erasing operators.

2:Erasing dependency graph construction.

3:Construct the trace graph $(\mathcal{E},\mathcal{V})$ of $\mathcal{M}$.

4:Initialize an empty graph
$(\mathcal{V}_{\text{erase}},\mathcal{E}_{\text{erase}})$.

5:Initialize queue
$\mathcal{Q}\leftarrow\\{\mathcal{S}(v):v\in\mathcal{V}\text{ is adjacent to
the input of trace graph}\\}$.

6:while $\mathcal{Q}\neq\emptyset$ do

7: Dequeue the head segment $\mathcal{S}$ from $\mathcal{Q}$.

8: Grow $\mathcal{S}$ in the depth-first manner till meet either joint vertex
or multi-outgoing vertex $\hat{v}$.

9: Add segments into $\mathcal{V}_{\text{erase}}$ and connections into
$\mathcal{E}_{\text{erase}}$.

10: Enqueue new segments into the tail of $\mathcal{Q}$ if $\hat{v}$ has
outgoing vertices.

11:Find erasing minimal removal structures.

12:Get the incoming vertices $\widehat{\mathcal{V}}$ for joint vertices in the
$(\mathcal{V}_{\text{erase}},\mathcal{E}_{\text{erase}})$.

13:Group the trainable variables in the vertex $v\in\widehat{\mathcal{V}}$ as
$g_{v}$.

14:Form $\mathcal{G}_{\text{EZIG}}$ as the union of the above groups, i.e.,
$\mathcal{G}_{\text{EZIG}}\leftarrow\\{g_{v}:v\in\widehat{\mathcal{V}}\\}$.

15:Form $\mathcal{G}_{\text{EZIG}}^{C}$ as the union of the trainable
variables in the remaining vertices.

16:Return variable partition
$\mathcal{G}=\mathcal{G}_{\text{EZIG}}\cup\mathcal{G}_{\text{EZIG}}^{C}$ and
erasing dependency graph
$(\mathcal{V}_{\text{erase}},\mathcal{E}_{\text{erase}})$.

To track the dependency in erasing mode, we design a novel graph algorithm
stated as line 2-10 in Algorithm 4. We start from the trace graph
$(\mathcal{V},\mathcal{E})$ of the target DNN $\mathcal{M}$ as Figure 2 and
line 3, then analyze it to create the erasing dependency graph
$(\mathcal{V}_{\text{erase}},\mathcal{E}_{\text{erase}})$, wherein each vertex
in $\mathcal{V}_{\text{erase}}$ serves as a potential erasing minimally
removal structure candidate.

To proceed, we use a queue container $\mathcal{Q}$ to track the erasing
minimally removal structure candidates (line 5). The initial elements of this
queue are the vertices that are directly adjacent to the input of
$\mathcal{M}$, such as Conv1. We then traverse the graph in the breadth-first
manner, iteratively growing each element (segment) $\mathcal{S}$ in the queue
until a valid minimally removal structure candidate is formed. The growth of
each candidate follows the depth-first search to recursively expand
$\mathcal{S}$ until the current vertices are considered as endpoints. An
endpoint vertex is determined by whether it is a joint vertex or has multiple
outgoing vertices, as indicated in line 8. Intuitively, a joint vertex has
multiple inputs, which means that the DNN may be still valid after removing
the current segment. This suggests that the current segment may be removable.
On the other hand, a vertex with multiple outgoing neighbors implies that
removing the current segment may cause some of its children to miss the input
tensor. For instance, removing Conv1 would cause Conv2, MaxPool and AvgPool to
become invalid due to the absence of input in Figure 2. Therefore, it is risky
to remove such candidates. Once the segment $\mathcal{S}$ has been grown, new
candidates are initialized as the outgoing vertices of the endpoint and added
into the container $\mathcal{Q}$ (line 10). Such procedure is repeated until
the end of traversal and returns the erasing dependency graph
$(\mathcal{V}_{\text{erase}},\mathcal{E}_{\text{erase}})$ as Figure 6(b).

#### Erasing Zero-Invariant Group Partition.

We now identify the erasing minimally removal structures upon
$(\mathcal{V}_{\text{erase}},\mathcal{E}_{\text{erase}})$ to form the erasing
search space. The qualified instances are the vertices in
$\mathcal{V}_{\text{erase}}$ that have trainable variables and all of their
outgoing vertices are joint vertices. This is because a joint vertex has
multiple inputs and remains valid even after removing some of its incoming
structures, as indicated in line 12 in Algorithm 4. Consequently, their
trainable variables are grouped together into erasing zero invariant groups
$\mathcal{G}_{\text{EZIG}}$ (line 13-14 and Figure 6(c)). The remaining
vertices are considered as either unremovable or belonging to a large removal
structure, which trainable variables are grouped into the
$\mathcal{G}_{\text{EZIG}}^{C}$ (the complementary to
$\mathcal{G}_{\text{EZIG}}$). As a result, for the given DNN $\mathcal{M}$,
all its trainable variables are encompassed by the union
$\mathcal{G}_{\text{erase}}\leftarrow\mathcal{G}_{\text{EZIG}}\cup\mathcal{G}_{\text{EZIG}}^{C}$.
The corresponding erasing minimally removal structures to the variable groups
$\mathcal{G}_{\text{EZIG}}$ constitute the erasing search space.

###  6.2 Hiearachical Half-Space Projected Gradient (H2SPG)

Given the target DNN $\mathcal{M}$ and its variable group partition
$\mathcal{G}_{\text{erase}}=\mathcal{G}_{\text{EZIG}}\cup\mathcal{G}_{\text{EZIG}}^{C}$,
the next is to jointly search for a valid sub-network $\mathcal{M}^{*}$ that
exhibits the most significant performance and train it to high performance.
Searching a sub-network is equivalent to identifying the redundant EZIGs in
$\mathcal{G}_{\text{EZIG}}$, erasing the corresponding operators, and ensuring
the remaining network still valid. Training the sub-network becomes optimizing
over the remaining important groups in $\mathcal{G}_{\text{erase}}$ to achieve
high performance. Structured sparsity problem is a natural choice to
accomplish both tasks. However, compared to the pruning mode, the erasing mode
needs to additionally consider the hierarchy across the erasing minimally
removal structures, leading to a more challenging a hierarchical structured
sparsity problem formulated as (4), which has not been addressed for the deep
learning application.

${\displaystyle\mathop{\operator@font{minimize}}_{\bm{x}\in\mathbb{R}^{n}}}\
f(\bm{x}),\ \ \text{s.t.}\ \text{Cardinality}(\mathcal{G}^{0})=K,\ \text{and}\
(\mathcal{V}_{\text{erase}}/\mathcal{V}_{\mathcal{G}^{0}},\mathcal{E}_{\text{erase}}/\mathcal{E}_{\mathcal{G}^{0}})\
\text{is valid},$ (4)

where $f$ is the prescribed loss function,
$\mathcal{G}^{=0}:=\\{g\in\mathcal{G}_{\text{EZIG}}|[\bm{x}]_{g}=0\\}$ is the
set of zero groups in $\mathcal{G}_{\text{EZIG}}$, which cardinality measures
its size. $K$ is the target hierarchical group sparsity, indicating the number
of erasing minimally removal structures that should be identified as
redundant. A larger $K$ dictates a higher sparsity level that produces a more
compact sub-network with fewer FLOPs and parameters. The trainable variables
in the redundant structures are projected onto zero, while the trainable
variables in the important structures are preserved as non-zero and optimized
for high performance.
$(\mathcal{V}_{\text{erase}}/\mathcal{V}_{\mathcal{G}^{0}},\mathcal{E}_{\text{erase}}/\mathcal{E}_{\mathcal{G}^{0}})$
refers to the sub-graph removing vertices and edges according to zero groups
$\mathcal{G}^{0}$. It being valid requires the zero groups distributed obeying
the hierarchy of the erasing dependency graph to ensure the resulting sub-
network functions correctly.

Algorithm 5 Hierarchical Half-Space Projected Gradient (H2SPG)

1:Input: initial variable $\bm{x}_{0}\in\mathbb{R}^{n}$, initial learning rate
$\alpha_{0}$, target group sparsity $K$, warm-up steps $T$, optimization
variant $\mathcal{OPT}$, erasing dependency graph
$(\mathcal{V}_{\text{erase}},\mathcal{E}_{\text{erase}})$ and group partition
$\mathcal{G}_{\text{erase}}=\mathcal{G}_{\text{EZIG}}\cup\mathcal{G}_{\text{EZIG}}^{C}$.

2:Hierarchical Search Phase.

3:Initialize the group set for redundant erasing minimally removal structures
$\mathcal{G}_{\text{redundant}}\leftarrow\emptyset$.

4:Initialize remaining sub-graph
$(\widehat{\mathcal{V}},\widehat{\mathcal{E}})\leftarrow(\mathcal{V}_{\text{erase}},\mathcal{E}_{\text{erase}})$.

5:Calculate the saliency score via modular proxy for each
$g\in\mathcal{G}_{\text{EZIG}}$ and sort them.

6:for $g\in\mathcal{G}_{\text{EZIG}}$ ordered by saliency scores ascendingly
do

7: Find the vertex $v_{g}$ for $g$ and the adjacent edges $\mathcal{E}_{g}$.

8: if
$(\widehat{\mathcal{V}}/\\{v_{g}\\},\widehat{\mathcal{E}}/\mathcal{E}_{g})$ is
valid and $|\mathcal{G}_{\text{redundant}}|<K$ then

9: Update
$\mathcal{G}_{\text{redundant}}\leftarrow\mathcal{G}_{\text{redundant}}\cup\\{g\\}$.

10: Update
$(\widehat{\mathcal{V}},\widehat{\mathcal{E}})\leftarrow(\widehat{\mathcal{V}}/\\{v_{g}\\},\widehat{\mathcal{E}}/\mathcal{E}_{g})$.

11:Hybrid Training Phase.

12:for $t=0,1,\cdots,$ do

13: Compute gradient estimate $\nabla\\!f(\bm{x}_{t})$ by the selected
$\mathcal{OPT}$.

14: Update $[\bm{x}_{t+1}]_{\mathcal{G}_{\text{redundant}}^{C}}$ as
$[\bm{x}_{t}-\alpha_{t}\nabla\\!f(\bm{x}_{t})]_{\mathcal{G}_{\text{redundant}}^{C}}.$

15: Perform Half-Space projection over
$[\bm{x}_{t}]_{\mathcal{G}_{\text{redundant}}}$.

16:Return the final or the best iterate as $\bm{x}^{*}_{\text{H2SPG{}}{}}$.

Figure 7: Check validness of redundant candidates. Target group sparsity
$K=3$. Conv7 has smaller salience score than Conv2-BN2. Dotted vertices are
marked as redundant candidates.

#### Related Sparse Optimizers.

Problem (4) is difficult to solve due to the non-differential and non-convex
sparsity constraint and the graph validity constraint. Existing sparse
optimizers such as HSPG (Chen et al., 2020b; Dai et al., 2023) and proximal
methods (Deleu and Bengio, 2021; Klopfenstein et al., 2023) overlook the
architecture evolution and hierarchy during the sparsity exploration, which is
crucial to (4). In fact, they are mainly applied for the pruning tasks,
wherein operations are preserved yet become slimmer. Consequently, employing
them onto (4) usually produces invalid sub-networks.

#### Outline of H2SPG.

To effectively solve problem (4), we propose a novel H2SPG to consider the
hierarchy and ensure the validness of graph architecture after removing
redundant vertices during the optimization process. To the best of our
knowledge, H2SPG is the first optimizer that successfully solves such
hierarchical structured sparsity problem, which outline is stated in Algorithm
5.

H2SPG is a hybrid multi-phase optimizer, distinguished by its dedicated
designs catering to the hierarchical constraint, positioning it significantly
apart from its non-hierarchical counterparts within the HSPG sparse optimizer
family (Chen et al., 2020b, 2023b; Dai et al., 2023). Initially, H2SPG
classifies variable groups into important and redundant segments through a
novel hierarchical search phase. The hierarchical search phase considers the
topology of erasing dependency graph
$(\mathcal{V}_{\text{erase}},\mathcal{E}_{\text{erase}})$ to ensure the
validness of the resulting sub-network. Subsequently, it applies the hybrid
training phase proposed in Section 5.2 to employ separate updating mechanisms
onto different segments to achieve a solution with both desired hierarchical
group sparsity and high performance.

#### Hierarchical Search Phase.

H2SPG first computes the saliency scores for each erasing zero-invariant
groups (EZIGs) (line 5 in Algorithm 5). The saliency score measures the
importance of each erasing minimally removal structures to form an optimal
sub-network. It design and calculation are modular to varying proxies, e.g.,
gradient-based proxies or training-free zero-shot proxies (Lin et al., 2021;
Chen et al., 2021c; Li et al., 2023a) upon the need of downstream tasks. If
fidelity is the main focus, the score should measure from the optimization
perspective. If efficiency on hardware is the main focus, the score should
favor more on hardware acceleration (Li and Meng, 2023; Ghimire et al., 2022).
We by default use the gradient-based proxy due to its generality. In
particular, we first warm up all variables by conducting SGD or its variants.
During the warm-up, a salience score of each group
$g\in\mathcal{G}_{\text{EZIG}}$ is computed. Smaller salience score indicates
the group exhibits less prediction power, thus may be redundant. By default,
we consider both the cosine similarity between negative gradient
$-[\nabla\\!f(\bm{x})]_{g}$ and the projection direction $-[\bm{x}]_{g}$ as
well as the average magnitude as DHSPG in Section 5.2. The former one measures
the approximate degradation of the objective function over the projection
direction. The latter one measures the distance to the origin.

The next is to form a set of redundant erasing minimally removal structure
candidates $\mathcal{G}_{\text{redundant}}$ and ensures the validity of
remaining DNN after erasing these candidates (line 6-10 in Algorithm 5). To
proceed, we iterate each group in $\mathcal{G}_{\text{EZIG}}$ in the ascending
order of salience scores. A remaining sub-graph
$(\widehat{\mathcal{V}},\widehat{\mathcal{E}})$ is constructed by iteratively
removing the vertex of each group along with the corresponding adjacent edges
from $(\mathcal{V}_{\text{erase}},\mathcal{E}_{\text{erase}})$. The sanity
check verifies whether the graph
$(\widehat{\mathcal{V}},\widehat{\mathcal{E}})$ is still connected after the
erasion. If so, the variable group for the current vertex is added into
$\mathcal{G}_{\text{redundant}}$; otherwise, the subsequent group is turned
into considerations. As illustrated in Figure 7, though Conv7 has a smaller
salience score than Conv2-BN2, Conv2-BN2 is marked as potentially redundant
but not Conv7 since there is no path connecting the input and the output of
the graph after removing Conv7. This mechanism largely guarantees that even if
all redundant candidates are erased, the resulting sub-network is still
functioning as normal. The complementary groups with higher salience scores
are marked as important groups and form
$\mathcal{G}_{\text{important}}\leftarrow\mathcal{G}_{\text{erase}}/\mathcal{G}_{\text{redundant}}$.

#### Hybrid Training Phase.

H2SPG then engages into the hybrid training phase to produce desired
hierarchical sparsity over $\mathcal{G}_{\text{redundant}}$ and optimize over
$\mathcal{G}_{\text{important}}$ for pursuing excellent performance till the
convergence. This phase has been described in Section 5.2, and is briefly went
through for completeness. In general, for the important groups
$\mathcal{G}_{\text{important}}$, the vanilla SGD or its variant is employed
to minimize the objective function (line 13-14 in Algorithm 5). For redundant
group candidates in $\mathcal{G}_{\text{redundant}}$, a Half-Space projection
step introduced in (Chen et al., 2020b) is proceeded to progressively yield
sparsity without sacrificing the objective function to the largest extent.
Finally, a high-performing solution $\bm{x}_{\text{H2SPG{}}}^{*}$ with desired
hierarchical sparsity is returned.

(a) Identified redundant structures.

(b) Redundant erasing zero-invariant groups.

(c) Constructed sub-network.

Figure 8: Redundant erasing minimally removal structures and sub-network
construction.

###  6.3 Automatic Erased Network Construction

We finally construct a sub-network $\mathcal{M}^{*}_{\text{erase}}$ upon the
given DNN $\mathcal{M}$ and the solution $\bm{x}_{\text{H2SPG{}}}^{*}$ by
H2SPG. The solution $\bm{x}_{\text{H2SPG{}}}^{*}$ should attain desired target
hierarchical group sparsity level and achieve high performance. As illustrated
in Figure 8, we first traverse the graph to remove the vertices and the edges
corresponding to the redundant erasing removal structures parameterized as
zero. For example, Conv2-BN2, MaxPool-Conv3-BN3 and Conv8 are removed due to
their variable groups being zero. Then, we traverse the graph in the second
pass to adjust the affiliated structures that are dependent on the removed
vertices to keep the remaining operations valid, e.g., the first and second
columns in $\bm{\widehat{\mathcal{K}}_{6}}$ are erased since its incoming
vertices Conv2-BN2 and MaxPool-Conv3-BN3 have been removed (see Figure 8(b)).
Next, we recursively erase unnecessary vertices and isolated vertices.
Isolated vertices refer to the vertices that have neither incoming nor
outgoing vertices. Unnecessary vertices refer to the skippable operations,
e.g., Concat and Add (between Conv7 and AvgPool) become unnecessary.
Ultimately, a compact sub-network $\mathcal{M}^{*}$ is constructed as shown in
Figure 8(c). Fine-tuning the constructed sub-network
$\mathcal{M}^{*}_{\text{erase}}$ is optional and often not necessary.

##  7 Numerical Experiments

In this section, we demonstrate the autonomy, generality, and high-performance
of the proposed OTOv3 in both pruning and erasing modes. We cover a wide range
of benchmark DNN architectures, including Bert (Vaswani et al., 2017), CARN
(Ahn et al., 2018), ConvNeXt (Liu et al., 2022), DemoNet, DARTS (Liu et al.,
2018), DenseNet (Huang et al., 2017), RegNet (Radosavovic et al., 2020),
ResNet (He et al., 2016), StackedUnets (Ronneberger et al., 2015) and VGG16
(Simonyan and Zisserman, 2014). The applications are ranging from popular
image classification, low-level computer vision, to natural language
processing. OTOv3 proceeds end-to-end training and compression in separate
modes along with the minimization of human manual efforts and achieves
competitive even superior performance to the state-of-the-arts.

###  7.1 Library Implementation

OTOv3 makes a significant leap in engineering achievements compared to its
predecessor, OTOv2. A primary limitation of OTOv2 was its reliance on ONNX
(developers, 2021), which restricted the use of structurally pruned models,
such as post-training or quantization if needed. OTOv3 addresses this issue by
redesigning and refactoring the pruning mode to directly produce the pruned
models in the Torch format. This enhancement markedly improves the generality
and flexibility of OTOv3. The end-users can now input a Torch-based DNN, train
and compress it via DHSPG, and ultimately receive a pruned Torch model
suitable for various applications, as presented in Figure 1. The entire
process is automated, and requires minimally manual adjustments to the
original training pipeline. Furthermore, the erasing mode in OTOv3 explores a
brand new application domain regarding automatically erasing redundant
operators from DNNs. This mode is facing more significant engineering
challenges due to the dramatic topological transformation on the DNN
architecture compared with the pruning mode. At present, we support generating
the sub-network in ONNX format, and aim to push the engineering boundaries to
produce Torch-based sub-networks in future iterations.

###  7.2 Experimental Setup

Given a full DNN, we typically expect that the end-users should already have a
stable training pipeline including an optimizer and a learning rate scheduler
to reliably train the full DNN to high-performance. OTOv3 is designed to
seamlessly plug into varied DNN training tasks. Consequently, we used the same
gradient estimation / optimizer variant and learning rate scheduler as each
baseline training pipeline into DHSPG and H2SPG throughout the below
experiments. We recommend to identify redundancy at initialization stage yet
after a fair enough warm-up steps. Therefore, the warm-up phase of DHSPG in
the pruning mode is empirically set as about 1/10 of total training steps. For
the erasing mode, H2SPG follows the existing gradient-based NAS works (Liu et
al., 2018) by performing 50 epochs for the hierarchical search phase. In the
end, it is noteworthy that OTOv3 supports training from either scratch or a
pre-trained checkpoint, e.g., Bert (Vaswani et al., 2017).

###  7.3 Structurally Pruning Operators

Table 1: Structurally pruning CARNx2.

Method | Optimizer | FLOPS | # of Params | PSNR
---|---|---|---|---
Set14 | B100 | Urban100
Baseline | Adam | 100% | 100% | 33.5 | 32.1 | 31.5
OTOv3 Pruning Mode | DHSPG | 24.3% | 24.1% | 33.2 | 31.9 | 31.1
|  |  |  |  |  |

#### CARNx2 on Super-Resolution.

We first select a popular architecture CARN (Ahn et al., 2018) for the super-
resolution task with the scaling factor as two, referring as CARNx2. We use
benchmark DIV2K dataset (Agustsson and Timofte, 2017) for training and Set14
(Zeyde et al., 2010), B100 (Martin et al., 2001) and Urban100 (Huang et al.,
2015) datasets for evaluation. OTOv3 automatically discovers the pruning
minimally removal structures and partitions the variables into PZIGs.
Following (Agustsson and Timofte, 2017), we use Adam as the optimization
variant into DHSPG which leverages both first and second order momentums to
estimate gradient. Under the same learning rate scheduler and training steps
as the baseline as well as a target group sparsity as 50%, OTOv3 could
dramatically reduce about 76% FLOPs and parameters with negligible PSNR
degradation as presented in Table 1.

####  VGG16-BN on CIFAR10.

We then focus on VGG16-BN, using one popular dataset CIFAR10 (Krizhevsky and
Hinton, 2009). VGG16-BN is a modified version of the original VGG16,
incorporating a batch normalization layer after each convolutional layer.
Similarly to CARNx2, OTOv3 automatically identifies the redundant pruning
minimal removal structures, and simultaneously trains the important PZIGs to
high performance from scratch without fine-tuning. As the results shown in
Table 2, OTOv3 effectively structurally prunes VGG16-BN, maintains the
baseline accuracy while using only 5.0% of the parameters and 26.6% of the
FLOPs. It’s noteworthy that, although SCP and RP achieve higher accuracy
levels, they require significantly more computational resources, demanding
43%-102% more FLOPs compared to OTOv3.

Table 2: Structurally pruning VGG16-BN on CIFAR10. Convolutional layers are in
bold.

Method | BN | Architecture | FLOPs | # of Params | Top-1 Acc.
---|---|---|---|---|---
Baseline |  TextRenderingMode=FillStroke, LineWidth=.5pt, ✓ |  64-64-128-128-256-256-256-512-512-512-512-512-512-512-512 | 100% | 100% | 93.2%
EC (Li et al., 2016) |  TextRenderingMode=FillStroke, LineWidth=.5pt, ✓ |  32-64-128-128-256-256-256-256-256-256-256-256-256-512-512 | 65.8% | 37.0% | 93.1%
Hinge (Li et al., 2020b) |  TextRenderingMode=FillStroke, LineWidth=.5pt, ✓ | – | 60.9% | 20.0% | 93.6%
SCP (Kang and Han, 2020) |  TextRenderingMode=FillStroke, LineWidth=.5pt, ✓ | – | 33.8% | 7.0% | 93.8%
RP (Li et al., 2022) |  TextRenderingMode=FillStroke, LineWidth=.5pt, ✓ | – | 47.9% | 42.1% | 93.9%
CPGCN (Di Jiang and Yang, 2022) |  TextRenderingMode=FillStroke, LineWidth=.5pt, ✓ | – | 26.9% | 6.9% | 93.1%
OTOv3 Pruning Mode |  TextRenderingMode=FillStroke, LineWidth=.5pt, ✓ |  14-51-77-122-183-146-92-41-16-13-8-11-14-107-183 | 26.6% | 5.0% | 93.4%
|  |  |  |  |

####  DenseNet121 on CIFAR100.

We next consider DenseNet121 (Huang et al., 2017) on the benchmark dataset
CIFAR100 (Krizhevsky and Hinton, 2009). As presented in Table 3, with target
group sparsity as 70%, the pruning mode in OTOv3 could train and compress from
scratch, and dramatically reduce 79.2% FLOPs with competitive top-1 accuracy
to the baseline full model.

Table 3: Structurally Pruning DenseNet and ConvNeXt. Method | Backend | Dataset | FLOPs | # of Params | Top-1 Acc.
---|---|---|---|---|---
Baseline | DenseNet121 | CIFAR100 | 100% | 100% | 77.0%
OTOv3 Pruning Mode | DenseNet121 | CIFAR100 | 20.8% | 26.7% | 75.5%
Baseline | ConvNeXt-Tiny | ImageNet | 100% | 100% | 82.0%
OTOv3 Pruning Mode | ConvNeXt-Tiny | ImageNet | 52.8% | 54.2% | 81.1%
|  |  |  |  |

#### ConvNeXt-Tiny on ImageNet.

To validate the compliance of OTOv3 with popular training tricks such as TIMM
(Wightman, 2019), we employed the pruning mode onto ConvNeXt-Tiny for
ImageNet, which baseline was trained underneath TIMM. The results reported in
Table 3 indicate that under the target group sparsity level as 50%, the pruned
ConvNeXt-Tiny could reduced about 47.2% FLOPs and 45.8% parameters with only
0.9% top-1 accuracy regression.

####  ResNet50 on ImageNet.

Figure 9: ResNet50 on ImageNet.

We now employ OTOv3 to ResNet50 on ImageNet. Under a similar procedure, OTOv3
first automatically partitions the trainable variables of ResNet50 into PZIGs,
and then trains it once by DHSPG to automatically construct slimmer models
without fine-tuning. We report a performance portfolio under various target
group sparsities ranging from 40% to 70% and compare with other state-of-the-
art methods in Figure 9. Notably, OTOv3 appears to a Pcareto frontier in terms
of balancing top-1 accuracy and FLOPs reduction across different group
sparsities. Specifically, at 70% group sparsity, OTOv3’s pruned ResNet50 model
achieves a significant FLOP reduction 85.5% while maintaining a competitive
top-1 accuracy of 70.3%, comparable to SFP (He et al., 2018a) and RBP (Zhou et
al., 2019), but with 3x fewer FLOPs. The variant with 72.3% top-1 accuracy at
60% group sparsity rivals CP (He et al., 2017), DDS-26 (Huang and Wang, 2018),
and RRBP (Zhou et al., 2019) in accuracy, yet is 2-3 times more efficient. The
slimmer ResNet50 models at 40% and 50% group sparsity both achieve an accuracy
milestone of around 75%, outperforming most state-of-the-art models in FLOP
reduction. While methods like ResRep (Ding et al., 2021b), Group-HS (Yang et
al., 2019), and GBN-60 (You et al., 2019) attain over 76% accuracy, they
consume more FLOPs than OTOv3 and lack the automated generality for diverse
DNNs.

####  Bert on SQuAD.

In the end, we compare DHSPG versus HSPG on pruning a transformer Bert
(Vaswani et al., 2017), evaluated on SQuAD, a question-answering benchmark
(Rajpurkar et al., 2016). In OTOv2 (Chen et al., 2023b), the transformer
architecture is not supported due to some ONNX compliance issues. Now, OTOv3
could support it due to the recent engineering refactorization of the pruning
mode. The results are reported in Table 4, showing that DHSPG significantly
outperforms HSPG and ProxSSI (Deleu and Bengio, 2021) by achieving 83.8%-87.7%
F1-scores and 74.6%-80.0% exact match rates. In constrast, HSPG and ProxSSI
reach 82.0%-84.1% F1-scores and 71.9%-75.0% exact match rates. Such noticeable
improvement by DHSPG is driven due to the hybrid training schema in DHSPG to
employ distinct updating mechanisms onto separate groups of variables, which
avoids trapping around an sub-optimum. In contrast, both ProxSSI and HSPG
equip with a unified training schema to penalize the magnitude of all
variables, which deteriorates the performance significantly in this
experiment. The results well validate the effectiveness of the hybrid training
design in DHSPG for typical better generalization.

Table 4: Structurally pruning Bert on SQuAD.

Method | # of Params | Exact | F1-score | Inference SpeedUp
---|---|---|---|---
Baseline | 100% | 81.0% | 88.3% | $1\times$
ProxSSI (Deleu and Bengio, 2021) |  83.4%† | 72.3% | 82.0% | $1\times$
HSPG (Chen et al., 2021b) | 91.0% | 75.0% | 84.1% | $1.1\times$
HSPG (Chen et al., 2021b) | 66.7% | 71.9% | 82.0% | $1.3\times$
DHSPG (10% group sparsity) | 93.3% | 80.0% | 87.7% | $1.1\times$
DHSPG (30% group sparsity) | 80.1% | 79.4% | 87.3% | $1.2\times$
DHSPG (50% group sparsity) | 68.3% | 78.1% | 86.2% | $1.3\times$
DHSPG (70% group sparsity) | 55.0% | 74.6% | 83.8% | $\bm{1.4\times}$
† Approximate value based on the group sparsity reported in (Deleu and Bengio,
2021).

###  7.4 Erasing Operators

In this section, we employ the erasing mode of OTOv3 to one-shot automatically
train and search within general DNNs to construct compact sub-networks with
high performance via erasing redundant operators. The numerical demonstrations
cover extensive DNNs including DemoNet shown in Section 6, RegNet (Radosavovic
et al., 2020), StackedUnets (Ronneberger et al., 2015), SuperResNet (He et
al., 2016; Lin et al., 2021), and DARTS (Liu et al., 2018), over benchmark
datasets, including CIFAR10 (Krizhevsky and Hinton, 2009), Fashion-MNIST (Xiao
et al., 2017), ImageNet (Deng et al., 2009), STL-10 (Coates et al., 2011) and
SVNH (Netzer et al., 2011).

Table 5: Erasing operators on extensive DNNs.

Method | Backend | Dataset | FLOPs (M) | # of Params (M) | Top-1 Acc. (%)
---|---|---|---|---|---
Baseline | DemoNet | Fashion-MNIST | 209 | 0.82 | 84.9
OTOv3 Erasing Mode | DemoNet | Fashion-MNIST | 107 | 0.45 | 84.7
Baseline | StackedUnets | SVNH | 184 | 0.80 | 95.3
OTOv3 Erasing Mode | StackedUnets | SVNH | 115 | 0.37 | 96.1
Baseline | DARTS (8 cells) | STL-10 | 614 | 4.05 | 74.6
OTOv3 Erasing Mode | DARTS (8 cells) | STL-10 | 127 | 0.64 | 75.1
|  |  |  |  |

####  DemoNet on Fashion-MNIST.

We first experiment with the DemoNet depicted as Figure 2 on Fashion-MNIST.
OTOv3 automatically establishes the erasing search space of DemoNet and
partitions its trainable variables into EZIGs. H2SPG then trains DemoNet from
scratch and computes a solution of high performance and hierarchical group-
sparsity, which is further utilized to construct a compact sub-network as
presented in Figure 8(c). As shown in Table 5, compared to the full network,
the sub-network utilizes 54% of parameters and 51% of FLOPs to achieve a Top-1
validation accuracy 84.7% which is negligibly lower than the full network by
0.2%.

####  StackedUnets on SVNH.

We then consider a StackedUnets over SVNH. The StackedUnets is constructed by
stacking two standard Unets (Ronneberger et al., 2015) with different down-
samplers together, as depicted in Figure 13(a) in Appendix B. We employ OTOv3
to automatically build the erasing search space and train by H2SPG. H2SPG
identifies and projects the redundant EZIGs onto zero and optimizes the
remaining important groups to attain excellent performance. As displayed in
Figure 14(a), the right-hand-side Unet is disabled due to
node-72-node-73-node-74-node-75 identified as redundant. The path regarding
the deepest depth for the left-hand-side Unet, i.e.,
node-13-node-14-node-15-node-19, is marked as redundant as well. The results
by OTOv3 indicate that the performance gain brought by either composing
multiple Unets in parallel or encompassing deeper scaling paths is not
significant. OTOv3’s erasing mode also validates the human design since a
single Unet with properly selected depths have achieved remarkable success in
numerous applications (Ding et al., 2021a, 2022; Weng et al., 2019; Geng et
al., 2022). Furthermore, as presented in Table 5, the sub-network built by
OTOv3 uses 0.37M parameters and 115M FLOPs which is noticeably lighter than
the full StackedUnets meanwhile significantly outperforms it by 0.8% in
validation accuracy.

####  DARTS (8-Cells) on STL-10.

We next employ OTOv3 on DARTS over STL-10. DARTS is a complicated network
consisting of iteratively stacking multiple cells (Liu et al., 2018). Each
cell is constructed by spanning a graph wherein every two nodes are connected
via multiple operation candidates. STL-10 is an image dataset for the semi-
supervising learning, where we conduct the experiments by using its labeled
samples. DARTS has been well explored in the recent years. However, the
existing NAS methods studied it based on a handcrafted search space beforehand
to locally pick up one or two important operations to connect every two nodes.
We now employ OTOv3’s erasing mode on an eight-cells DARTS to automatically
establish its search space, then utilize H2SPG to one shot train it and search
important structures globally as depicted in Figure
LABEL:fig:darts_8cells_dependancy_graph of Appendix B. Afterwards, a sub-
network is automatically constructed as drawn in Figure
LABEL:fig:darts_8cells_subnetwork. Quantitatively, the sub-network outperforms
the full DARTS in terms of validation accuracy by 0.5% by using only about
15%-20% of the parameters and the FLOPs of the original network (see Table 5).

Table 6: Erasing operators over SuperResNet on CIFAR10. Method | Type | Search Space | Top-1 Acc (%) | FLOPs (M) | # of Params (M)
---|---|---|---|---|---
Zen-Score-1M(Lin et al., 2021) | Zero-Shot | ResNet Pool | 96.2 | 159 | 0.99
Synflow† (Tanaka et al., 2020) | Zero-Shot | ResNet Pool | 95.1 | – |  $\sim$1.0
TE-NAS† (Chen et al., 2021c) | Zero-Shot | ResNet Pool | 96.1 | – |  $\sim$1.0
NASWOT† (Mellor et al., 2021) | Zero-Shot | ResNet Pool | 96.0 | – |  $\sim$1.0
Zen-Score-2M (Lin et al., 2021) | Zero-Shot | ResNet Pool | 97.5 | 481 | 1.98
OTOv3 Erasing Mode | Gradient | SuperResNet | 96.3 | 161 | 1.00
OTOv3 Erasing Mode | Gradient | SuperResNet | 97.5 | 477 | 1.97
† Reported in (Lin et al., 2021). |  |

####  SuperResNet on CIFAR10.

We switch to a ResNet search space inspired by ZenNAS (Lin et al., 2021),
referred to as SuperResNet. ZenNAS (Lin et al., 2021) uses a ResNet pool to
populates massive ResNet candidates and ranks them via zero-shot proxy. We
independently construct SuperResNet by stacking several super-residual blocks
with varying depths. Each super-residual blocks contain multiple Conv
candidates with kernel sizes as 3x3, 5x5 and 7x7 separately in parallel.
SuperResNet includes the optimal architecture derived from ZenNAS and aims to
discover the most suitable sub-networks using H2SPG over the automated erasing
search space. The sub-network produced by OTOv3 could reach the benchmark over
97% validation accuracy.

Table 7: OTOv3 over DARTS on ImageNet and comparison with state-of-the-art
methods.

Architecture | Test Acc. (%) | # of Params (M) | FLOPs (M) | Search Method
---|---|---|---|---
Top-1 | Top-5
DARTS (2nd order) (CIFAR10) (Liu et al., 2018) | 73.3 | 91.3 | 4.7 | 574 | Gradient
SNAS (mild) (Xie et al., 2018) | 27.3 | 91.2 | 4.3 | 522 | Gradient
P-DARTS (CIFAR10) (Chen et al., 2019b) | 75.6 | 92.6 | 4.9 |  yellow!40557 | Gradient
PC-DARTS (CIFAR10) (Xu et al., 2019) | 74.9 | 92.2 | 5.3 | 586 | Gradient
ISTA-NAS (CIFAR10) (Yang et al., 2020) | 74.9 | 92.3 | 4.8 | 550 | Gradient
SANAS (CIFAR10) (Hosseini and Xie, 2022) | 75.2 | 91.7 | – | – | Gradient
ProxylessNAS (ImageNet) (Cai et al., 2018) | 75.1 | 92.5 | 7.1 |  red!40465 | Gradient
PC-DARTs (ImageNet) (Xu et al., 2019) | 75.8 | 92.7 | 5.3 | 597 | Gradient
ISTA-NAS (ImageNet) (Yang et al., 2020) |  orange!4076.0 |  orange!4092.9 | 5.7 | 638 | Gradient
MASNAS (ImageNet) (Lopes et al., 2023) | 74.7 | – |  red!402.6 | – | Multi-Agent
MixPath (ImageNet) (Chu et al., 2023) |  red!4077.2 |  red!4093.5 |  yellow!405.1 | – | Gradient
OTOv3 on DARTS (ImageNet) |  yellow!4075.9 |  yellow!4092.8 |  orange!404.9 |  orange!40552 | Gradient
(CIFAR10) / (ImageNet) refer to using either CIFAR10 or ImageNet for searching
architecture. .

####  DARTS (14-Cells) on ImageNet.

We now present the benchmark DARTS network stacked by 14 cells on ImageNet.
OTOv3 automatically figures out the erasing search space, trains by H2SPG to
figure out redundant erasing minimally removal structures, and constructs a
sub-network. (The depictation is ommitted in arxiv version due to exceeding
page limit, yet could be found at our github repository.) We observe that the
sub-network produced by OTOv3 achieves competitive top-1/5 accuracy compared
to other state-of-the-arts as presented in Table 7. Remark that it is
engineeringly difficult to automatically inject architecture variables and
build a multi-level optimization upon the automatic search space.
Consequently, our accuracy achieved by single-level optimization does not
outperform MixPath and ISTA-NAS. We leave further improvement over automated
multi-level optimization pipeline as future work.

#### Ablation Study (RegNet on CIFAR10).

We finally conduct ablation studies over RegNet (Radosavovic et al., 2020) on
CIFAR10 to demonstrate the necessity and efficacy of hierarchical sparse
optimizer H2SPG compared to the existing non-hierarchical sparse optimizers,
which is the key to the erasing mode. Without loss of generality, we employ
OTOv3 over the RegNet-800M which has accuracy 95.01% on CIFAR10, and compare
with the latest variant of HSPG, i.e., DHSPG (Chen et al., 2023b). We evaluate
them with varying target hierarchical group sparsity levels in problem (4)
across a range of $\\{0.1,0.3,0.5,0.7,0.9\\}$. As other experiments, OTOv3
automatically constructs its search space, trains via H2SPG or DHSPG, and
establishes the sub-networks without fine-tuning. The results are from three
independent tests under different random seeds, and reported in Table 8.

Table 8: OTOv3 on RegNet on CIFAR10.

Backend | Method | Optimizer | Target | # of Params (M) | Top-1 Acc. (%)
---|---|---|---|---|---
Sparsity
|  |  | 0.1 | $5.56\pm\ 0.02$ | $95.26\pm\ 0.13$
|  |  | 0.3 | (3.40, ✗, ✗) | (95.01, ✗, ✗)
RegNet-800M | OTOv3 | DHSPG | 0.5 | (✗, ✗, ✗) | (✗, ✗, ✗)
|  |  | 0.7 | (✗, ✗, ✗) | (✗, ✗, ✗)
|  |  | 0.9 | (✗, ✗, ✗) | (✗, ✗, ✗)
|  |  | 0.1 | $5.58\pm\ 0.01$ | $95.30\pm\ 0.10$
|  |  | 0.3 | $3.54\pm\ 0.15$ | $95.08\pm\ 0.14$
RegNet-800M | OTOv3 | H2SPG | 0.5 | $1.83\pm\ 0.09$ | $94.61\pm\ 0.19$
|  |  | 0.7 | $1.16\pm\ 0.12$ | $91.92\pm\ 0.24$
|  |  | 0.9 | $0.82\pm\ 0.17$ | $87.91\pm\ 0.32$
|  |  |  |  |

blackSub-networks by OTOv3 versus Full Networks. The sub-networks under
varying hierarchical group sparsity levels computed by OTOv3 with H2SPG
exhibits the Pareto frontier comparing with the benchmark RegNets. Notably,
the sub-networks under sparsity levels of 0.1 and 0.3 outperform the full
RegNet-800M. Furthermore, the ones with 0.5 sparsity level outperforms the
RegNet(200M-600M), despite utilizes significantly fewer parameters while
achieves higher accuracy.

blackH2SPG versus Other Sparse Optimizers. DHSPG often fails when confronts
with reasonably large target sparsity levels, denoted by the symbol ✗. The
underlying reason lies in its design, which solely treats problem (4) as an
independent and disjoint structured sparsity problem. By disregarding the
hierarchy within the network, DHSPG easily generates invalid sub-networks.
Conversely, H2SPG takes into account the network hierarchy and successfully
addresses problem (4). We also compare with a proximal method equipping with
our hierarchical search phase, i.e., ProxSG+. Its performance is not
competitive to H2SPG due to their ineffective sparse exploration ability (Dai
et al., 2023).

##  8 Conclusions

We propose OTOv3, a pioneering framework, that automatically trains a general
DNN only once and compress it into a more compact counterpart by either
structurally pruning or erasing operators. For different compression mode,
OTOv3 automatically generates the corresponding search spaces along with
distinct and novel dependency graph analysis and zero-invariant group
partitions. Later on, two novel sparse optimizers DHSPG or H2SPG are employed
to jointly identify redundant structures and train the important ones to high-
performance. Remarkably, H2SPG also stands as the first optimizer to address
the hierarchical structured sparsity problems for deep learning applications.
OTOv3 significantly reduces the human efforts upon the existing structured
pruning and NAS works, opens new directions, and establishes benchmarks
regarding the automated general DNN compression.

Acknowledgments and Disclosure of Funding

We thank Microsoft LLC for supporting the series of Only-Train-Once (OTO)
framework. Zhihui Zhu acknowledges support from NSF grant CCF-2240708.

## References

  * Agustsson and Timofte (2017) E. Agustsson and R. Timofte.  Ntire 2017 challenge on single image super-resolution: Dataset and study.  In _Proceedings of the IEEE conference on computer vision and pattern recognition workshops_ , 2017.
  * Ahn et al. (2018) N. Ahn, B. Kang, and K.-A. Sohn.  Fast, accurate, and lightweight super-resolution with cascading residual network.  In _Proceedings of the European conference on computer vision (ECCV)_ , pages 252–268, 2018.
  * Cai et al. (2018) H. Cai, L. Zhu, and S. Han.  Proxylessnas: Direct neural architecture search on target task and hardware.  _arXiv preprint arXiv:1812.00332_ , 2018.
  * Cai et al. (2019) H. Cai, C. Gan, T. Wang, Z. Zhang, and S. Han.  Once-for-all: Train one network and specialize it for efficient deployment.  _arXiv preprint arXiv:1908.09791_ , 2019.
  * Calhas et al. (2022) D. Calhas, V. M. Manquinho, and I. Lynce.  Automatic generation of neural architecture search spaces.  In _Combining Learning and Reasoning: Programming Languages, Formalisms, and Representations_ , 2022.
  * Chen et al. (2019a) J. Chen, S. Chen, and S. J. Pan.  Storage efficient and dynamic flexible runtime channel pruning via deep reinforcement learning.  2019a.
  * Chen et al. (2017) T. Chen, F. E. Curtis, and D. P. Robinson.  A reduced-space algorithm for minimizing $\ell_{1}$-regularized convex functions.  _SIAM Journal on Optimization_ , 27(3):1583–1610, 2017.
  * Chen et al. (2018) T. Chen, F. E. Curtis, and D. P. Robinson.  Farsa for $\ell_{1}$-regularized convex optimization: local convergence and numerical experience.  _Optimization Methods and Software_ , 2018.
  * Chen et al. (2020a) T. Chen, B. Ji, Y. Shi, T. Ding, B. Fang, S. Yi, and X. Tu.  Neural network compression via sparse optimization.  _arXiv preprint arXiv:2011.04868_ , 2020a.
  * Chen et al. (2020b) T. Chen, G. Wang, T. Ding, B. Ji, S. Yi, and Z. Zhu.  Half-space proximal stochastic gradient method for group-sparsity regularized problem.  _arXiv preprint arXiv:2009.12078_ , 2020b.
  * Chen et al. (2021a) T. Chen, T. Ding, B. Ji, G. Wang, Y. Shi, J. Tian, S. Yi, X. Tu, and Z. Zhu.  Orthant based proximal stochastic gradient method for $\ell_{1}$-regularized optimization.  In _Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2020, Ghent, Belgium, September 14–18, 2020, Proceedings, Part III_ , pages 57–73. Springer, 2021a.
  * Chen et al. (2021b) T. Chen, B. Ji, T. Ding, B. Fang, G. Wang, Z. Zhu, L. Liang, Y. Shi, S. Yi, and X. Tu.  Only train once: A one-shot neural network training and pruning framework.  In _Advances in Neural Information Processing Systems_ , 2021b.
  * Chen et al. (2023a) T. Chen, T. Ding, B. Yadav, I. Zharkov, and L. Liang.  Lorashear: Efficient large language model structured pruning and knowledge recovery.  _arXiv preprint arXiv:2310.18356_ , 2023a.
  * Chen et al. (2023b) T. Chen, L. Liang, T. Ding, Z. Zhu, and I. Zharkov.  OTOv2: Automatic, generic, user-friendly.  In _The Eleventh International Conference on Learning Representations_ , 2023b.
  * Chen et al. (2021c) W. Chen, X. Gong, and Z. Wang.  Neural architecture search on imagenet in four gpu hours: A theoretically inspired perspective.  _arXiv preprint arXiv:2102.11535_ , 2021c.
  * Chen et al. (2019b) X. Chen, L. Xie, J. Wu, and Q. Tian.  Progressive differentiable architecture search: Bridging the depth gap between search and evaluation.  In _Proceedings of the IEEE/CVF international conference on computer vision_ , pages 1294–1303, 2019b.
  * Chen et al. (2021d) X. Chen, L. Xie, J. Wu, and Q. Tian.  Progressive darts: Bridging the optimization gap for nas in the wild.  _International Journal of Computer Vision_ , 129:638–655, 2021d.
  * Chu et al. (2023) X. Chu, S. Lu, X. Li, and B. Zhang.  Mixpath: A unified approach for one-shot neural architecture search.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 5972–5981, 2023.
  * Coates et al. (2011) A. Coates, A. Ng, and H. Lee.  An analysis of single-layer networks in unsupervised feature learning.  In _Proceedings of the fourteenth international conference on artificial intelligence and statistics_ , pages 215–223. JMLR Workshop and Conference Proceedings, 2011.
  * Dai et al. (2023) Y. Dai, T. Chen, G. Wang, and D. Robinson.  An adaptive half-space projection method for stochastic optimization problems with group sparse regularization.  _Transactions on Machine Learning Research_ , 2023.
  * Deleu and Bengio (2021) T. Deleu and Y. Bengio.  Structured sparsity inducing adaptive optimizers for deep learning.  _arXiv preprint arXiv:2102.03869_ , 2021.
  * Deng et al. (2009) J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE conference on computer vision and pattern recognition_ , pages 248–255. Ieee, 2009.
  * developers (2021) O. R. developers.  Onnx runtime.  https://onnxruntime.ai/, 2021.
  * Di Jiang and Yang (2022) Y. C. Di Jiang and Q. Yang.  On the channel pruning using graph convolution network for convolutional neural network acceleration.  2022\.
  * Ding et al. (2021a) T. Ding, L. Liang, Z. Zhu, and I. Zharkov.  Cdfi: Compression-driven network design for frame interpolation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 8001–8011, 2021a.
  * Ding et al. (2022) T. Ding, L. Liang, Z. Zhu, T. Chen, and I. Zharkov.  Sparsity-guided network design for frame interpolation.  _arXiv preprint arXiv:2209.04551_ , 2022.
  * Ding et al. (2023) T. Ding, T. Chen, H. Zhu, J. Jiang, Y. Zhong, J. Zhou, G. Wang, Z. Zhu, I. Zharkov, and L. Liang.  The efficiency spectrum of large language models: An algorithmic survey.  _arXiv preprint arXiv:2312.00678_ , 2023.
  * Ding et al. (2021b) X. Ding, T. Hao, J. Tan, J. Liu, J. Han, Y. Guo, and G. Ding.  Lossless cnn channel pruning via decoupling remembering and forgetting.  _Proceedings of the IEEE International Conference on Computer Vision_ , 2021b.
  * Fang et al. (2023) G. Fang, X. Ma, M. Song, M. B. Mi, and X. Wang.  Depgraph: Towards any structural pruning.  _arXiv preprint arXiv:2301.12900_ , 2023.
  * Frankle and Carbin (2018) J. Frankle and M. Carbin.  The lottery ticket hypothesis: Finding sparse, trainable neural networks.  _arXiv preprint arXiv:1803.03635_ , 2018.
  * Frankle et al. (2019) J. Frankle, G. K. Dziugaite, D. M. Roy, and M. Carbin.  Stabilizing the lottery ticket hypothesis.  _arXiv preprint arXiv:1903.01611_ , 2019.
  * Frantar and Alistarh (2023) E. Frantar and D. Alistarh.  Sparsegpt: Massive language models can be accurately pruned in one-shot.  In _International Conference on Machine Learning_ , pages 10323–10337. PMLR, 2023.
  * Gale et al. (2019) T. Gale, E. Elsen, and S. Hooker.  The state of sparsity in deep neural networks.  _arXiv preprint arXiv:1902.09574_ , 2019.
  * Gao et al. (2020) S.-H. Gao, Y.-Q. Tan, M.-M. Cheng, C. Lu, Y. Chen, and S. Yan.  Highly efficient salient object detection with 100k parameters.  In _European Conference on Computer Vision_ , pages 702–721. Springer, 2020.
  * Geng et al. (2022) Z. Geng, L. Liang, T. Ding, and I. Zharkov.  Rstt: Real-time spatial temporal transformer for space-time video super-resolution.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 17441–17451, 2022.
  * Ghimire et al. (2022) D. Ghimire, D. Kil, and S.-h. Kim.  A survey on efficient convolutional neural networks and hardware acceleration.  _Electronics_ , 11(6):945, 2022.
  * Ham et al. (2023) G. Ham, S. Kim, S. Lee, J.-H. Lee, and D. Kim.  Cosine similarity knowledge distillation for individual class information transfer.  _arXiv preprint arXiv:2311.14307_ , 2023.
  * Han et al. (2015) S. Han, H. Mao, and W. J. Dally.  Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding.  _arXiv preprint arXiv:1510.00149_ , 2015.
  * He et al. (2016) K. He, X. Zhang, S. Ren, and J. Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016.
  * He et al. (2017) Y. He, X. Zhang, and J. Sun.  Channel pruning for accelerating very deep neural networks.  In _The IEEE International Conference on Computer Vision (ICCV)_ , Oct 2017.
  * He et al. (2018a) Y. He, G. Kang, X. Dong, Y. Fu, and Y. Yang.  Soft filter pruning for accelerating deep convolutional neural networks.  _arXiv preprint arXiv:1808.06866_ , 2018a.
  * He et al. (2018b) Y. He, J. Lin, Z. Liu, H. Wang, L.-J. Li, and S. Han.  Amc: Automl for model compression and acceleration on mobile devices.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , pages 784–800, 2018b.
  * Hosseini and Xie (2022) R. Hosseini and P. Xie.  Saliency-aware neural architecture search.  _Advances in Neural Information Processing Systems_ , 35:14743–14757, 2022.
  * Hu et al. (2016) H. Hu, R. Peng, Y.-W. Tai, and C.-K. Tang.  Network trimming: A data-driven neuron pruning approach towards efficient deep architectures.  _arXiv preprint arXiv:1607.03250_ , 2016.
  * Huang et al. (2017) G. Huang, Z. Liu, L. Van Der Maaten, and K. Q. Weinberger.  Densely connected convolutional networks.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 4700–4708, 2017.
  * Huang et al. (2015) J.-B. Huang, A. Singh, and N. Ahuja.  Single image super-resolution from transformed self-exemplars.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2015.
  * Huang and Wang (2018) Z. Huang and N. Wang.  Data-driven sparse structure selection for deep neural networks.  In _Proceedings of the European conference on computer vision (ECCV)_ , pages 304–320, 2018.
  * Idelbayev and Carreira-Perpiñán (2022) Y. Idelbayev and M. Á. Carreira-Perpiñán.  Exploring the effect of $\ell_{0}/\ell_{2}$ regularization in neural network pruning using the lc toolkit.  In _ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pages 3373–3377. IEEE, 2022.
  * Kang and Han (2020) M. Kang and B. Han.  Operation-aware soft channel pruning using differentiable masks.  In _International Conference on Machine Learning_ , pages 5122–5131. PMLR, 2020.
  * Kingma and Ba (2014) D. P. Kingma and J. Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Klopfenstein et al. (2023) Q. Klopfenstein, Q. Bertrand, A. Gramfort, J. Salmon, and S. Vaiter.  Local linear convergence of proximal coordinate descent algorithm.  _Optimization Letters_ , pages 1–20, 2023.
  * Kolter et al. (2021) J. Kolter, P. Ravikumar, and C. M. University.  Xrl: Explainable reinforcement learning for ai autonomy.  2021\.
  * Krizhevsky and Hinton (2009) A. Krizhevsky and G. Hinton.  Learning multiple layers of features from tiny images.  _Master’s thesis, Department of Computer Science, University of Toronto_ , 2009.
  * Laenen (2023) S. Laenen.  One-shot neural network pruning via spectral graph sparsification.  In _Topological, Algebraic and Geometric Learning Workshops 2023_ , pages 60–71. PMLR, 2023.
  * Li et al. (2020a) B. Li, B. Wu, J. Su, and G. Wang.  Eagleeye: Fast sub-net evaluation for efficient neural network pruning.  In _European Conference on Computer Vision_ , pages 639–654. Springer, 2020a.
  * Li et al. (2023a) G. Li, Y. Yang, K. Bhardwaj, and R. Marculescu.  Zico: Zero-shot nas via inverse coefficient of variation on gradients.  _arXiv preprint arXiv:2301.11300_ , 2023a.
  * Li and Meng (2023) H. Li and L. Meng.  Hardware-aware approach to deep neural network optimization.  _Neurocomputing_ , 559:126808, 2023.
  * Li et al. (2016) H. Li, A. Kadav, I. Durdanovic, H. Samet, and H. P. Graf.  Pruning filters for efficient convnets.  _arXiv preprint arXiv:1608.08710_ , 2016.
  * Li et al. (2019) Y. Li, S. Lin, B. Zhang, J. Liu, D. Doermann, Y. Wu, F. Huang, and R. Ji.  Exploiting kernel sparsity and entropy for interpretable cnn compression.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 2800–2809, 2019.
  * Li et al. (2020b) Y. Li, S. Gu, C. Mayer, L. V. Gool, and R. Timofte.  Group sparsity: The hinge between filter pruning and decomposition for network compression.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 8018–8027, 2020b.
  * Li et al. (2022) Y. Li, K. Adamczewski, W. Li, S. Gu, R. Timofte, and L. Van Gool.  Revisiting random channel pruning for neural network compression.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 191–201, 2022.
  * Li et al. (2023b) Z. Li, H. Li, and L. Meng.  Model compression for deep neural networks: A survey.  _Computers_ , 12(3):60, 2023b.
  * Lin et al. (2021) M. Lin, P. Wang, Z. Sun, H. Chen, X. Sun, Q. Qian, H. Li, and R. Jin.  Zen-nas: A zero-shot nas for high-performance deep image recognition.  In _2021 IEEE/CVF International Conference on Computer Vision, ICCV 2021_ , 2021.
  * Lin et al. (2019) S. Lin, R. Ji, Y. Li, C. Deng, and X. Li.  Toward compact convnets via structure-sparsity regularized filter pruning.  _IEEE transactions on neural networks and learning systems_ , 31(2):574–588, 2019.
  * Liu et al. (2018) H. Liu, K. Simonyan, and Y. Yang.  Darts: Differentiable architecture search.  _arXiv preprint arXiv:1806.09055_ , 2018.
  * Liu et al. (2020) Z. Liu, Z. Xu, S. Rajaa, M. Madadi, J. C. S. J. Junior, S. Escalera, A. Pavao, S. Treguer, W.-W. Tu, and I. Guyon.  Towards automated deep learning: Analysis of the autodl challenge series 2019.  In _Proceedings of the NeurIPS 2019 Competition and Demonstration Track_ , Proceedings of Machine Learning Research. PMLR, 2020.
  * Liu et al. (2022) Z. Liu, H. Mao, C.-Y. Wu, C. Feichtenhofer, T. Darrell, and S. Xie.  A convnet for the 2020s.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 11976–11986, 2022.
  * Lopes et al. (2023) V. Lopes, F. M. Carlucci, P. M. Esperança, M. Singh, A. Yang, V. Gabillon, H. Xu, Z. Chen, and J. Wang.  Manas: Multi-agent neural architecture search.  _Machine Learning_ , pages 1–24, 2023.
  * Martin et al. (2001) D. Martin, C. Fowlkes, D. Tal, and J. Malik.  A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics.  In _Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001_ , volume 2, pages 416–423. IEEE, 2001.
  * Mellor et al. (2021) J. Mellor, J. Turner, A. Storkey, and E. J. Crowley.  Neural architecture search without training.  In _International Conference on Machine Learning_ , pages 7588–7598. PMLR, 2021.
  * Meng et al. (2020) F. Meng, H. Cheng, K. Li, H. Luo, X. Guo, G. Lu, and X. Sun.  Pruning filter in filter.  _arXiv preprint arXiv:2009.14410_ , 2020.
  * Munoz et al. (2022) J. P. Munoz, N. Lyalyushkin, C. W. Lacewell, A. Senina, D. Cummings, A. Sarah, A. Kozlov, and N. Jain.  Automated super-network generation for scalable neural architecture search.  In _International Conference on Automated Machine Learning_ , pages 5–1. PMLR, 2022.
  * Netzer et al. (2011) Y. Netzer, T. Wang, A. Coates, A. Bissacco, B. Wu, and A. Y. Ng.  Reading digits in natural images with unsupervised feature learning.  2011\.
  * Pedregosa et al. (2011) F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, et al.  Scikit-learn: Machine learning in python.  _the Journal of machine Learning research_ , 12:2825–2830, 2011.
  * Radosavovic et al. (2020) I. Radosavovic, R. P. Kosaraju, R. Girshick, K. He, and P. Dollár.  Designing network design spaces.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 10428–10436, 2020.
  * Rajpurkar et al. (2016) P. Rajpurkar, J. Zhang, K. Lopyrev, and P. Liang.  Squad: 100,000+ questions for machine comprehension of text.  _arXiv preprint arXiv:1606.05250_ , 2016.
  * Renda et al. (2020) A. Renda, J. Frankle, and M. Carbin.  Comparing rewinding and fine-tuning in neural network pruning.  _arXiv preprint arXiv:2003.02389_ , 2020.
  * Ronneberger et al. (2015) O. Ronneberger, P. Fischer, and T. Brox.  U-net: Convolutional networks for biomedical image segmentation.  In _International Conference on Medical image computing and computer-assisted intervention_ , pages 234–241. Springer, 2015.
  * Simonyan and Zisserman (2014) K. Simonyan and A. Zisserman.  Very deep convolutional networks for large-scale image recognition.  _arXiv preprint arXiv:1409.1556_ , 2014.
  * Tanaka et al. (2020) H. Tanaka, D. Kunin, D. L. Yamins, and S. Ganguli.  Pruning neural networks without any data by iteratively conserving synaptic flow.  _Advances in neural information processing systems_ , 33:6377–6389, 2020.
  * van Baalen et al. (2020) M. van Baalen, C. Louizos, M. Nagel, R. A. Amjad, Y. Wang, T. Blankevoort, and M. Welling.  Bayesian bits: Unifying quantization and pruning.  _arXiv preprint arXiv:2005.07093_ , 2020.
  * Vaswani et al. (2017) A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin.  Attention is all you need.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.
  * Wen et al. (2016) W. Wen, C. Wu, Y. Wang, Y. Chen, and H. Li.  Learning structured sparsity in deep neural networks.  _arXiv preprint arXiv:1608.03665_ , 2016.
  * Weng et al. (2019) Y. Weng, T. Zhou, Y. Li, and X. Qiu.  Nas-unet: Neural architecture search for medical image segmentation.  _IEEE access_ , 7:44247–44257, 2019.
  * Wightman (2019) R. Wightman.  Pytorch image models.  https://github.com/rwightman/pytorch-image-models, 2019.
  * Xiao et al. (2017) H. Xiao, K. Rasul, and R. Vollgraf.  Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms, 2017.
  * Xie et al. (2018) S. Xie, H. Zheng, C. Liu, and L. Lin.  Snas: stochastic neural architecture search.  _arXiv preprint arXiv:1812.09926_ , 2018.
  * Xu et al. (2019) Y. Xu, L. Xie, X. Zhang, X. Chen, G.-J. Qi, Q. Tian, and H. Xiong.  Pc-darts: Partial channel connections for memory-efficient architecture search.  _arXiv preprint arXiv:1907.05737_ , 2019.
  * Xu et al. (2021) Z. Xu, W.-W. Tu, and I. Guyon.  Automl meets time series regression design and analysis of the autoseries challenge.  In _Machine Learning and Knowledge Discovery in Databases._ , pages 36–51. Springer, 2021.
  * Yang et al. (2019) H. Yang, W. Wen, and H. Li.  Deephoyer: Learning sparser neural network with differentiable scale-invariant sparsity measures.  _arXiv preprint arXiv:1908.09979_ , 2019.
  * Yang et al. (2020) Y. Yang, H. Li, S. You, F. Wang, C. Qian, and Z. Lin.  Ista-nas: Efficient and consistent neural architecture search by sparse coding.  _Advances in Neural Information Processing Systems_ , 33:10503–10513, 2020.
  * You et al. (2019) Z. You, K. Yan, J. Ye, M. Ma, and P. Wang.  Gate decorator: Global filter pruning method for accelerating deep convolutional neural networks.  _arXiv preprint arXiv:1909.08174_ , 2019.
  * Zeyde et al. (2010) R. Zeyde, M. Elad, and M. Protter.  On single image scale-up using sparse-representations.  In _International conference on curves and surfaces_. Springer, 2010\.
  * Zhang et al. (2018) T. Zhang, S. Ye, K. Zhang, J. Tang, W. Wen, M. Fardad, and Y. Wang.  A systematic dnn weight pruning framework using alternating direction method of multipliers.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , pages 184–199, 2018.
  * Zhong et al. (2023) S. Zhong, Z. You, J. Zhang, S. Zhao, Z. LeClaire, Z. Liu, D. Zha, V. Chaudhary, S. Xu, and X. Hu.  One less reason for filter pruning: Gaining free adversarial robustness with structured grouped kernel pruning.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.
  * Zhou et al. (2021) D. Zhou, X. Jin, X. Lian, L. Yang, Y. Xue, Q. Hou, and J. Feng.  Autospace: Neural architecture search with less human interference.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 337–346, 2021.
  * Zhou et al. (2019) Y. Zhou, Y. Zhang, Y. Wang, and Q. Tian.  Accelerate cnn via recursive bayesian pruning.  In _Proceedings of the IEEE International Conference on Computer Vision_ , pages 3306–3315, 2019.
  * Zhuang et al. (2020) T. Zhuang, Z. Zhang, Y. Huang, X. Zeng, K. Shuang, and X. Li.  Neuron-level structured pruning using polarization regularizer.  _Advances in Neural Information Processing Systems_ , 33, 2020.

##  Appendix A Visualization for Pruning Dependency Graph

Figure 10: Pruning dependency graph for CARNx2. Figure 11: Pruning dependency
graph for ResNet50. Figure 12: Pruning dependency graph for VGG16-BN.

##  Appendix B Visualization for Erasing Mode

In this appendix, we present visualizations generated by the erasing mode of
OTOv3 library to provide more intuitive illustrations of the architectures
tested in the paper. The visualizations include trace graphs, erasing
dependency graphs, identified redundant erasing minimally removal structures,
and constructed sub-networks. To ensure clear visibility, we highly recommend
zooming in with an upscale ratio of 500% to observe finer details and gain a
better understanding of the system.

(a) StackedUnets trace graph. Figure 13: StackedUnets illustrations drawn by
OTOv3. (a) StackedUnets erasing dependency graph with identified redundant
removal structures. Figure 14: StackedUnets illustrations drawn by OTOv3. (a)
Constructed sub-network upon StackedUnets. Figure 15: StackedUnets
illustrations drawn by OTOv3. (a) RegNet trace graph. Figure 16: RegNet
illustrations drawn by OTOv3. (a) RegNet erasing dependency graph with
identified redundant removal structures. Figure 17: RegNet illustrations drawn
by OTOv3. (a) Constructed sub-network upon RegNet. Figure 18: RegNet
illustrations drawn by OTOv3.