SEDONA: Search for Decoupled Neural Networks toward Greedy Block-wise Learning
Authors: Myeongjang Pyeon
Jihwan Moon
Taeyoung Hahn
Gunhee Kim
Venue: ICLR 2021 Poster (2021)
Keywords: AutoML
Neural Architecture Search
Greedy Learning
Deep Learning

Abstract: Backward locking and update locking are well-known sources of inefficiency in backpropagation that prevent from concurrently updating layers. Several works have recently suggested using local error signals to train network blocks asynchronously to overcome these limitations. However, they often require numerous iterations of trial-and-error to find the best configuration for local training, including how to decouple network blocks and which auxiliary networks to use for each block. In this work, we propose a differentiable search algorithm named SEDONA to automate this process. Experimental results show that our algorithm can consistently discover transferable decoupled architectures for VGG and ResNet variants, and significantly outperforms the ones trained with end-to-end backpropagation and other state-of-the-art greedy-leaning methods in CIFAR-10, Tiny-ImageNet and ImageNet.

Published as a conference paper at ICLR 2021
SEDONA: SEARCH FOR DECOUPLED NEURAL NET- WORKS TOWARD GREEDY BLOCK-WISE LEARNING
Myeongjang Pyeon, Jihwan Moon, Taeyoung Hahn, and Gunhee Kim
Seoul National University, Seoul, Korea
(mipyeon, mnmjh1215, taeyounhhhnnn gunhee @snu. .ac.aac.... kr https://vvl /wt.//iiiiiiiiionn/eioe/ooo.onns www..nnn..nnu.............
snu. aon.acc... wttp.a..kr/prrjects/eeeeeeee
ABSTRACT
Backward locking and update locking are well-known sources of inefficiency in backpropagation that prevent from concurrently updating layers. Several works have recently suggested using local error signals to train network blocks asyn- chronously to overcome these limitations. However, they often require numerous iterations of trial-and-error to find the best configuration for local training, includ- ing how to decouple network blocks and which auxiliary networks to use for each block. In this work, we propose differentiable search algorithm named SEDONA to automate this process. Experimental results show that our algorithm can consis- tently discover transferable decoupled architectures for VGG and ResNet variants, and significantly outperforms the ones trained with end-to-end backpropagation and other ofate-of-the-art greedy-leaning methods CIFAR-10, ImageNet and ImageNet.
INTRODUCTION
Backpropagation (Rumelhart et al. 1986) has made a significant contribution to the success of deep learning as the core learning algorithm for SGD-based optimization. However, backpropagation is sequential in nature and supports only synchronous weight updates. Specifically, the limited con- currency in backpropagation breaks down into two locking problems (Jaderberg et al.) [007)). First, update locking a forward pass must complete first before any weight update. Second, backward locking - gradient computation of upper layers must precede that of lower layers. Also, backpropa- gation may be biologically implausible since the human brain prefers local learning rules without the global movement of error signals (Crick 1989 Marblestone et al. (2016); Lillicrap et al. (022
Greedy block-wise learning is a competitive alternative to backpropagation that overcomes these limitations. It splits layers into a stack of gradient-isolated blocks, each of which trained with local error signals. Therefore, it is possible simultaneously compute the gradients for different network components with more fine-grained locks. Limiting the depth of error propagation graphs also reduces the vanishing gradient and increases memory efficiency. Recently, [Belilovsky et al. (2019), Nokkland & Eidnes] (2019), |Belilossky et al.] (2020), and [owwe et al.] (2019) empirically demonstrated that greedy block-wise learning could yield competitive performance to end-to-end backpropagation.
However, greedy block-wise learning introduces a group of architectural decisions. Let us consider a case where we want to decouple an L-layer network into K blocks for given K e {I..... L}. Then, the number of all possible groupings is (k=1). If we want to choose one of M candidates of auxiliary networks to generate local error gradients, we would have to consider (k=)) MK-1 different configurations. If local signals are not representative of the global goal, then the final performance would be damaged significantly.
In this work, we introduce novel search method named SEDONA (SEarching for DecOupled Neu- ral Architectures) which allows efficient search of decoupled neural architectures toward greedy block-wise learning. Given base neural network, SEDONA optimizes the validation loss by group- ing layers into blocks and selecting the best auxiliary network for each block. Inspired by DARTS LLu al. 2019), we first relax the decision variables representing propagation graphs and

---

Published as a conference paper at ICLR 2021
Block
Block
Classifier
Aux
Classiffer
Layer
Layer
Layer
Layer
Layer
Layer
Layer
Layer
(a) End-to-End Backpropagation
(h) Greedy Block-wise Learning
Figure I: Conceptual comparison of the backward computation graph between (a) end-to-end back- propagation and (b) greedy block-wise learning with K 2.
auxiliary networks to continuous domains. We then formulate bilevel optimization problem for the decision variables, which is solved via gradient descent.
Our key contributions summarized as follows.
1. To the best of our knowledge, this work is the first attempt to automate the discovery of decoupling neural networks for greedy block-wise learning. We propose an efficient search method named SEDONA, which finds decoupled enror propagation graphs and auxiliary heads suitable for successful greedy training.
2. Through extensive experiments on image classification tasks, we show that our locally optimized networks outperform not only the ones trained with end-to-end backpropagation but also two statc-of-theaar greedy-leaming methods of DGL (Belilovsky et al. (020) and PredSim (Nokland & Eidnes 2019) in CIFAR-IO, Tiny-ImageNet and ImageNet.
3. SEDONA discovers decoupled architectures for VGG (Simonyan & Zisserman, 2015) and ResNet (He et al. 2016) variants with only 0.25x width on CIFAR-IO. 10. The discovered net- works are transferable to Siny-ImaeNNet and ImageNet in which they are high-pen performing enough beat backpropagation and other greedy-leaning methods. It means that no search is required for every pair of a network and a dataset.
4. Finally, based experimental results, analyze the common characteristics among the architectures that are favorable to greedy-learning, such as avoiding the shallow first block and using deeper auxiliary networks for lower blocks.
2 PROBLEM STATEMENT AND MOTIVATION
In typical neural network training, backpropagation computes the gradients of weights with respect to the global loss by the chain rule (Rumelhart al. 1986). On the other hand, in greedy block-wise learning (Löwe et al. 2019 (Belilovsky et al.) 2020), the network is split into several subnetworks (i.e. blocks), each of which consists of one or more consecutive layers. Next, each block is attached to small neural network called the auxiliary network that computes its own objective (i.e. local loss), from which layer weights are optimized by propagating error signals within the block. Naturally, each block can independently perform parameter updates even while other blocks process forward passes. Figure T illustrates the high-level overview of greedy block-wise learning.
For successful greedy block-wise learning, one make two design decisions beforehand: (i) how to split the original network into a set of subnetworks, and (ii) which auxiliary network to use for each subnetwork. Finding the best configuration both problems requires significant time and effort from human experts. We empirically show that the performance of greedy block-wise learning is critically sensitive to these two design choices in Appendix [ This sensitivity introduces paradox of replacing backpropagation with greedy block-wise learning. If one has to put significant cost and time through series of experiments to discover a workable configuration, then the benefit of greedy learning (e.g. reduction of training time) is diluted. Unfortunately, there has not been generally acceptable practice to answer these two design choices.
Therefore, this work aims to propose an automated search method for the discovery of the best configuration, which has not been discussed so far. Although there have been several works on mod- ifying backward computation graphs (Bello et al. 2017 Alber et al. 2018 Xu et al. 2018), they still rely on global end-to-end learning and focus on finding new optimizers, weight update formulas, or error propagation rules, assuming that the backward computation graphs never discontinuous. In this work, we instead concern ourselves with making backward computation graphs discontinuous, L.e. finding optimal points where we stop gradient flow and use local gradients instead.
2

---

Published as a conference paper at ICLR 2021
Block
Block
Block
L
(2)
(8)
(
c
(
Aux
Aux
Aux
1800
[B
B
(1)
(1)
(3)
(3)
(1)
Layer
Layer
Layer
Layer
Layer
Layer
Layer
Layer
(a) Before Search
(h) After Search
Figure 2: An illustration of our search problem when 4, K 3 and M A search procedure should make two types of categorical choices at each layer: whether to stop the gradient flow and which auxiliary network use. These two decision choices are represented by meta-variables a and 33 respectively. Dashed lines represent possible decision choices, and gray ones are not chosen.
3 SEDONA: SEARCHING FOR DECOUPLED NEURAL ARCHITECTURES
We begin by describing the search space (Section 3.1 and present a continuous relaxation strat- egy that allows searching for the decoupled architecture using stochastic gradient descent the validation loss (Section 3.2). Finally, we propose a bilevel optimization that makes SEDONA com- putationally efficient (Section 3.3) and the discretization relaxed decision variables (Section 3.4
3.1 THE SEARCH SPACE
Our goal is to vertically split an input network into a set of blocks to enable greedy block-wise training. This task is equivalent to solving the following two problems (Figure 2): (i) finding layers at which we discontinue the gradient flow and (ii) assigning the most appropriate auxiliary network to each of those layers for generating local error signals.
We assume that an input network consists L convolutional layers, each of which may contain normalization and pooling layers. If the network has residual connections, regard each residual block as a single layer to simplify our notation. We focus on splitting the convolutional layers only and treat the last fully connected (FC) layers as the last block's auxiliary network.
To facilitate our exposition, we introduce two binary variables for every layer. First, the signal vari- able (9) E {0.1] denotes whether layer should utilize local gradients (i.e. the last layer a block) or backpropagated gradients (i.e. the inside layer). In other words, (!) = 1, the layer / is trained using local gradients, hence becoming the last layer in gradient-isolated block. Otherwise, the layer is trained with backpropagated gradients, therefore becoming the inside layer in a block. Second, the auxiliary type variable 3() E {0, 1 denotes one-hot encoding of which auxiliary is chosen out of M possible candidates for layer l. We here assume that every layer selects its own auxiliary network; later, we leave only for the last layer of each block. Note that the last layer of the whole network does need these variables because the final classifier acts its auxiliary head.
Now, we can formulate the loss for layer I as follows:
M Σ 30)) m=1
( train Cl (0,0,))=
Σ e (v. where 0 (I; (F.N)E
(a 0 (1)
D
D is the training data, (()) is the loss function, { are M candidates for auxiliary networks, and (!)) is the activations, is the network layer weights, and @m the m-th auxiliary network weights.
(1)
The error gradients at each non-last layer are calculated as
(I+
80)) = =a)) 80
(1 a (1) (0) where ((0) local
V a
(1) Crrain+ 0
8(++))
Ball) (2)
which is equivalent choosing between local and backpropagated error gradients.
3

---

Published as a conference paper at ICLR 2021
Algorithm 1: SEDONA
Searching for Decoupled Neural Architectures
Initialize signal variables a and auxiliary type variables / as O.
Pretrain layer and auxiliary network weights (0, ()) with Eq. 5 6 with the best validation accuracies in memory M.
and store N sets of weights
while (a, 3) not converged do
Sample one set of layer and auxiliary network weights (0, 6) from M
Calculate (Or, ④T) by performing 7" gradient steps on (0, Φ) with Eq. 5
6
Update (a, 3) by descending V V(a..) ((c) (0r, ΦT, a, 3) with Eq
Calculate (01, Φ1) by performing single gradient step on (0, () with Eq 6
Evict the oldest weights in M and save the updated weights (01, Φ1) into M.
end
Obtain decoupling by discretizing a and 3
3.2 CONTINUOUS RELAXATION
We optimize over a and / after relaxing them to a continuous domain, in a similar way to DARTS (Liu al. 2019). It enables gradient-based optimization, which is significantly faster than directly optimizing over the discrete domain using reinforcement learning or evolutionary algorithms. This benefit accelerates especially when the search space is large, i.e. when the input network is deep. Henceforth, let ( R and 3 E RM As result, relax the categorical choice of an auxiliary head to a weighted mixture of all possible auxiliary networks by replacing (q.(T) with
M
softmax(3()) m f1 (a
(a":o!)) 60!0
(3)
m=1
Also, replacing 2 the gradients for layer become a mix of local and backpropagated gradients:
g() = (1)) ((1)
+ 522 (1)
(4)
which is the affine combination between oforat = Vam ((l) softmax(a!") and J(L) Vacu,
train and 5() Da 011)
51++)
We use
bp
0a
3.3
BILEVEL OPTIMIZATION
We solve our search problem via bilevel optimization (Anandalingam & Friesz 1992 Colson al.
2007 Liu et al. 2019). In the inner level, network weights (6, Φ) are optimized with error gradients of Eq. 4). To be specific, with fixed (a, B), we take T gradient steps from initial weights (fu. du)
for all layers I E (1,.... ...,,, L} with a learning rate yp:
(a, 3) - (o, B) 50h (0, (a, ia
(5)
a00)*
3) - (a, (2 0
(a, (a,
V (i ( (0--1, Φ1-1,
(6)
In the outer level, we update the meta variables (a. 3) by propagating gradients with respect to the final classifier's loss c(L) (OT, (OT, a, 3) back through the T steps:
a --a-nV.cly (L) (Or, ΦT, ax B), 3- - (Or, (OTT,OT, 3).
Finally, we update (0, Φ) by taking a single gradient step with updated (a, 3). We repeat this process until (a, (8) converge. We outline algorithm in Algorithm I We empirically find that single inner step is not sufficient to measure the effect of the meta variables on the validation loss. So, we set T for all experiments. Since
only interested in (a, :) in this stage, we discard (0, Φ) after the search. (0, Φ) are learned again after the the final (a, 9) are discretized (Section 3.4.
Additionally, we apply the following techniques for stabilizing the bilevel optimization.
Pretraining, Before starting the optimization of (a, 3). we pretrain weights (8, Φ) with (a, B) fixed to zeros for sufficiently long 40K iterations. This technique avoids poor evaluation of (ax, 3) caused
4

---

Published as a conference paper at ICLR 2021
Table Relative parameter and FLOP counts (%) the auxiliary networks over the ResNet-101 on ImageNet. Our Aux i heads much more efficient than the previous MLP-SR (Belilovsky et al. 2020 and PredSim (Nokland & Eidnes 2019).
MLP-SR
PredSim
Aux
Aux 2
Aux 3
Aux 4
Rel. FLOPs
1.34
23.63
1.02
1.35
1.43
1.68
Rel. Param.
129.33
23.48
6.38
7.59
9.68
12.37
by bad initialization of (0, o). Such a warm start technique is not as it is adopted in Yan et al. (2019) and Chen et al. (2019). During pretraining, we store N sets of (0, Φ) with the best validation accuracies so far in memory for the purpose of weight sampling, which we will explain below. We use N = 50 as the size of memory.
Weight Sampling. In bilevel optimization, meta variables (a, B) depend the learning trajectory of layer and auxiliary weights (6, Φ) (i.e. a sequence values of (6, ø) during inner optimization), As consequence, there exists risk of overfitting the meta variables
a specific episode (Zela eet al. 22020] Chen & Hsieh| 2020). To alleviate such risk, we adopt a weight sampling scheme so that meta variables (a, 3) are optimized considering various learning trajectories, not a specific one. We sample one set of weights from memory with uniform probability at each outer optimization step, run an optimization step, and then store the updated weight back to the memory. When the memory is full, we evict the oldest one.
3.4 DISCRETIZATION
Equipped with and B optimized in continuous domain, make categorical decisions for de- coupling as in Section 3.1 It is straightforward; given K, we split the network into K blocks by selecting K 1 layers with the highest learned values of 01. Then, for each selected layer choose the auxiliary head with the largest value among 210 "/.
This discretization procedure shows additional advantage of continuous relaxation. Without tinuous relaxation, would be pre-defined hyperparameter for finding a decoupling configuration; therefore, one should search for every possible K. On the other hand, SEDONA makes a decision based on the learned values of a and B; thus, it can choose any K from a sorted list of āj to find the best decoupling configurations.
4 EXPERIMENTS
We experiment the proposed SEDONA in two stages of search and evaluation. In the search stage, SEDONA searches for the best decoupling configuration for given neural network on CIFAR- 10 to minimize the validation loss. In the evaluation stage, split the networks according to the searched configuration, and evaluate their greedy block-wise learning performance for classification in CIFAR-10 (Krizhevsky & Hinton 2009),, Tiny- Einy-ImaeeNe"" and ImageNet (Russakovsky et al. 2013). This setting will clearly show the efficiency and transferability of SEDONA since no search required for every pair of base network and dataset.
4.1 EXPERIMENTAL SETTINGS
Base Architectures. We use VGG-19 and ResNet-50/101/152 as base networks, following experi- ments of previous literature greedy learning (Nokland & Eidnes 2019, Belilovsky et al. 2020). We take the dataset complexity into account by setting the width 0.25x of the original networks for CIFAR-10 10 and 1x for Tiny-ImageNe and ImageNet. It also verifies that SEDONA can search for the configuration with network of the reduced width on a small dataset first and apply the discovered decouplings the ones with the original width large datasets. We detail the base architectures in Appendix(D.1
Auxiliary Network Pool. Reducing the size of auxiliary heads is crucial to retain the benefit of greedy block-wise learning; otherwise, the throughput gain by parallelization is diluted by the over- head of additional auxiliary heads. Thus, we heavily use depth-wise and point-wis wise convolution to
http:/ pett:://ting /tti:///iiiiii/itt maganett www.:aett...rooup....oo hww.hhapp..ccooo
5

---

Published as a conference paper at ICLR 2021
Table Error rates (%) on CIFAR-I0 and Tiny-ImageNer with backprop, PredSim (Nøkland Ei- dnes 2019), DGL (Belilovsky et al. 2020) and SEDONA (ours). For PredSim, DGL and SEDONA, we set K 4. For CIFAR- 10, we use 0.25x width the original networks.
(a) CIFAR-I0
(b) Tiny-Imagen Ima-eee
Architecture
Backprop
PredSim
DGL
SEDONA
Architecture
Backprop
PredSim
DGL
SEDONA
VGG-19
12.31
13.87
12.19
11.58
VGG-19
47.11
55.30
48.70
43.44
ResNet-50
7.99
8.93
8.27
7,53
ResNet-50
46.54
52.22
46.04
45.60
ResNet-101
7.14
7.93
8.30
ResNet-101
44,50
46.08
46.20
40.88
155
6.35
7.41
6.39
6.13
ResNet-
39.18
48.24
42.36
35.90
error
CIFAR 10
e01or
Tiay lenage/Nes
etror
CIFAR 10
error
Tiny ImnggeNes
0.11
PredSin
0.50
0.50
DCL
0.54
0.42
0.06
0.51
0.06
0.61
0.38
0.55
0.00
0.00
0.42
0.00
12
K
K
(a) ResNet-101
(b) ResNet-112
Figure 3: Comparison of classification errors of ResNet-101/152 when learning with increasing K.
let auxiliary networks in the pool be computationally lightweight. Inspired by the structure of Mo- bileNetv2 blocks (Sandler et al. 2018), we design four auxiliary candidates called Aux 1 - from the shallowest the deepest. Aux i consists of point-wise convolution, a depth-wise convolu- tional layer, (i - 1) inverted residual blocks and a point-wise convolution followed by an AvgPool and FC layer. More details of auxiliary heads can be found in Appendix [.2] Table I shows that all four auxiliary heads have much fewer parameters and FLOPs compared to the ones from other greedy-leamingg methods.
Baselines. We compare the performance of decoupled architectures found by SEDONA with those of two state-of-the-an
methods. We detail the optimization in Appendix F
DGL (Belilovsky et al. 2020) splits the network uniformly for given K and trains with greedy block-wise learning. Its auxiliary network is called MLP-SR, consisting of an Avg- Pool and 3 posnt-wise convolutional layers followed by an AvgPool and a 3-layer MLP.
PredSim (Nokland Eidnes 2019) mixes two losses, which require two different auxiliary networks, AvgPool + FC layers and convolutional layer, respectively. Since PredSim is originally designed for greedy layer-wise learning, we split the network uniformly as in DGL for block-wise training.
4.2 RESULTS ON 10 AND TINY-IMAGENET
Table 2 summarizes the classification results on CIFAR-10 and Tiny-ImageNet. DGL and PredSim perform worse than backpropagation in almost all cases. Especially, PredSim shows performance degradation on Tiny-ImageNet. Since the similarity loss of PredSim depends on supervised cluster- ing (Nokland & Eidnes 2019), the local error signals could be noisy when using large number of classes and small batch sizes. On the other hand, SEDONA enables greedy block-wise learning outperform end-to-end backpropagation. Since the widths of the base architectures change from CIFAR-10 10 to Tiny-Iman Inn-ImageNet, the results show that the decoupling found by SEDONA is success- fully transferable an architectural variant with a larger width. Interestingly, SEDONA beats back- propagation by large margins Tiny-ImageNer which has only 500 images per class. It implies that well-configured greedy learning could be a great learning option under data scarcity.
Figure [egureedepicc depicts the results of greedy block-wise learning with various K. Overall, the enrors grow as increases. DGL and PredSim underperform backpropagation with large gaps when K 2 12, whereas SEODNA still yields better or comparable performances to backpropagation even when K 16. This result shows that SEDONA can find workable configurations for sufficiently large K. The quick escalation of errors with increasing K hints that the block-wise wise training could be better than layer-wise training (i.e. = L) for performance. Moreover, increase of significantly inflates the overhead of auxiliary heads (See Table 1 for memory and computation overheads per head).

---

Published as a conference paper at ICLR 2021
Table 3: Error rates (%) on ImageNet with backprop, DGL and SEDONA (ours). Aux. Ens, denotes the ensemble of last two blocks' auxiliary networks.
(a) ResNet-101
(b) ResNet-152
Aux. Ens.
Top-1
Top-5 Em())
Aux. Ens.
Top-1 Em(S)
Top-5 Bm())
Method
K
Em(()
Speedup
Method
K
Speedup
Backprop
1
21.34
5.86
1
Backprop
21.22
5.79
2
21.53
5.84
1.42
2
21.45
5.86
1.51
DGL
DGL
23.13
6.82
22.89
6.80
4
1.92
4
2.23
22.35
6.44
22.20
6.39
2
20.72
5.39
1.67
20.69
5.58
1.61
SEDONA
SEDONA
21.32
5.83
21.09
5.74
2.01
2.02
21.00
5.52
20.20
5.13
Table 4: Comparison of error rates (%) on CIFAR-10 between (learned a, learned (3, (random a,
learned B) and (learned a, random () when K = 4.
ResNet-101
ResNet-152
SEDONA
random a
random 3
SEDONA
random a
random /
6.59 0.17
7.49 = 0.51
7.07 + 0.37
6,13 + 0.11
7.46 + 0.69
7.22 + 0.45
We detail found decouplings in Appendix D33
4.3 LARGE-SCALE EVALUATION ON IMAGENET
We also evaluate the decouplings learned on CIFAR-10 on the large-scale ImageNet dataset. We present the classification errors on the validation split and training speedup in Table Unlike DGL, SEDONA slightly outperforms backpropagation with 2x speedup maximum. When auxiliary networks are ensembled, SEDONA further expands the performance gaps from backpropagation. For ensembling, we sum the log log-softmax outputs from the last two blocks' auxiliary headers (i.e. auxiliary headers of block K and K - and use it for prediction. Note that the top-1 validation error of 20.20% by SEDONA is the state-of-the-arr result greedy block-wise learning. DGL. achieves the speedup of maximum x, which means that the uniform split of the network may be good policy for the throughput gain by parallelization. However, the speedup may be gained at the expense of accuracy. The reported speedup is the ratio of wall-clock training time of backprop over DGL or SEDONA. Following Huo et al. (2018)) and (eeiilossyy et al. (2020), we measure the speedup by spreading blocks into K GPUs and do not use data parallelism.
More implementation details can be found in Appendix
4.4 ABLATION STUDIES AND DISCUSSIONS
Effeets of learned a and B. SEDONA automates two types of decisions for greedy block-wise training: how to split the network and which auxiliary network to use. The signal variable and the auxiliary type variable 3 reflect each decision. A natural question here may be which variable is more important. To answer this, we measure the performance after modifying learned a 8 with random values. Table dessciiiss the results. Interestingly, a is more critical to the performance than B, meaning that the decision for how to split is crucial for successful greedy block-wise learning.
Importance of lower blocks. Surprisingly, SEDONA yields much more confident values of a (i.e. close to either 1 or 0) at lower layers than upper layers, shown in Figure 4 It may be because learning the meta variables for upper layers is more difficult than for lower layers. However, with sufficiently large K that can split the upper layers more, the accuracy does not harm much (see Figure 3) We speculate that the difference in confidence indicates finding appropriate lower blocks is a key to success for greedy block- learning.
Avoid the shallow first block. Another interesting observation is that SEDONA prevents the first block from being too shallow, the learned values of ai)) are smallest at several early layers (see Figure 4. It is known that the complexity of input regions that are represented by a neural network exponentially increases with its depth (Montufar al.) 2014), and thus a shallow neural network (with a finite width) may learn only too coarse features to classify complex images, which may be less meaningful representations for upper layers.
7

---

Published as a conference paper at ICLR 2021
0/
1.0
1.0
0.8
0.0
0.1
0.4
0.2
0.0
5
15
10
35
(a) 100
(b) ResNet-152
Figure 4: Learned values of aj on CIFAR-I0. 10. 01 are the smallest at first few layers but large and rather invariant at upper layers. Red indicates the split layers at K 4 and green indicates additionally split layers K = 8.
Assi 4
Aisx
Aiss 4
Clveeifer
Auax 4
Aux
Aix
Aux
Aua
Aux
Auxx
Classifer
Layer 1-11
Layer 12-13
Layer 14-17
Layer 18-50
Layer 1-11
Layer 12-13
Layer 14-17
Layer 18-19
Layer 20-22
Layer 23
Layer 24-25
Layer 26-50
(a)
K
4
(b) K 8
Figure Decoupled structures of ResNet-157 searched by SEDONA with K = (4,8).
Use deeper auxiliary heads for lower blocks. F the decoupled structure of ResNet- 152 discovered by SEDONA with K {4,8). While upper layers tend to choose various auxiliary heads, lower layers prefer Aux 4, which is the deepest one in our pool. This tendency is in agreement with our intuition that a deeper auxiliary network would help lower layers learn more complex features that are more helpful for upper layers.
Additional experimental results and discussions can be found in Appendix C
RELATED WORKS
Greedy learning. Greedy learning was first applied to DNNs as a pretraining step (Hinton et al. 2006). Traditionally, it solved the local optimization problems sequentially: optimization of an up- per layer starts only after that of a lower layer is finished (Hinton et al. 2006 Bengio et al. 2007 Belilovsky et al. 2019). However, recent works have shown that it is possible to solve the local opti- mization problems jointly, with a convergence guarantee. In doing so, backward and update locking problems alleviated (Nøkland & Eidnes 2019 Belilovsky et al. (020)) Moreover, forward un- locking can also be achieved if each block makes use of a replay bufter (Belilovsky et al. 2020).
Gradient approximation. Another branch of research that tackles backward and update unlocking gradient approximation. DNI (Jaderberg et al., 2017) trains a parametric model to output synthetic gradients from local information, removing the reliance on backpropagation dients. However, training with synthetic gradients often results in suboptimal accuracy, especially when neural networks are very deep. DDG (Huo et al. 2018b) and Feature Replay (Huo et al. 2018a) use time-delayed gradients or activations to ease the backward locking. Yet, they require large amounts of memory to store the activations and gradients of earlier steps. Contrarily, greedy block-wise learning achieves backward and update unlocking without storing any old information.
calculate true gra-
Optimizing optimization. Several works have attempted to employ automatic search methods to discover a variant of neural network optimization. Neural Optimizer Search (Bello et al.) (017) builds a new mathematical update equation from a set of primitive functions such as gradients or running average of gradients. Backprop Evolution (Alber et al.) 2018) searches for new error propagation rule, intending to improve standard backpropagation. AutoLoss (Xu et al. 2018) auto- matically determines the optimization schedule by selecting the loss function, scope of optimization, and duration. All of the previous works depend on continuous backward graphs. In this work, we take different direction by splitting the backward graphs into multiple blocks.
8

---

Published as a conference paper at ICLR 2021
6 CONCLUSION
We presented SEDONA, a novel efficient search method for finding decoupled neural architectures for successful greedy block-wise learning. Multiple state-of-the-art performances in various base networks and datasets for image classification demonstrated that the discovered architectures out- perform previous human-designed greedy learning methods well as end-to-end backpropagation. There are several interesting directions for improving SEDONA further. First, it would be interesting to automatically design local loss functions for each block, replacing the well-known cross-entropy. Second, for efficiency reasons, used predefined set of auxiliary heads, but searching the chitectures auxiliary networks may improve the performance and reveal each block's 's role, which are yet to realize. Finally, although we assumed that the input neural network has a fixed archi- tecture, combining SEDONA with an architecture search method such as DARTS can optimize the architecture in both forward and backward directions, which may yield intriguing results.
Acknowledgement. This work was supported by Samsung Advanced Institute of Technology, Insti- tute of Information & communications Technology Planning & Evaluation (ITTP) grant (No.2019- 0-01082, SW ab) and Basic Science Research Program through National Research Foundation of Korea (NRF) funded by the Korea government (MSIT) (NRF-202OR 1AB-20020RLA22B58300555555555 Gunhee Kim is the corresponding author.
REFERENCES
Maximilian Alber, Irwan Bello, Barret Zoph. Pieter-Jan Kindermans, Prajit Ramachandran, and Quoe Le. Backprop evolution. ICML AutoML Workshop, 2018.
G Anandalingam and Terry L Friesz. Hierarchical optimization: An introduction. Annals of Opera- tions Research, 34(1):1-11, 1992.
Peter J Angeline, Gregory M Saunders, and Jordan B Pollack. An evolutionary algorithm that constructs recurrent neural networks. IEEE Transactions on Neural Networks, 5(1):54-65, 1994.
Eugene Belilovsky, Michael Eickenberg, and Edouard Oyallon. Greedy layerwise learning can scale to imagenet. In ICML., 2019.
Eugene Belilovsky, Michael Fickenberg, and Edouard Oyallon. Decoupled greedy learning of cnns. In ICML, 2020.
Irwan Bello, Barret Zoph, Vijay Vasudevan, and Quoe Le. Neural optimizer search with rein- forcement learning. In ICML, 2017.
Yoshua Bengio, Pascal Lamblin, Dan Popovici, and Hugo Larochelle. Greedy layer-wise training of deep networks. In NeurlPS, 2007.
Xiangning Chen and Cho-Jui Hsieh. Stabilizing differentiable architecture search via perturbation- based regularization. In /CML, 2020.
Yukang Chen, Tong Yang, Xiangyu Zhang, Gaofeng Meng, Xinyu Xiao, and Jian Sun. Detnas: Backbone search for object detection. NeurlPS, 2019.
Benoît Colson, Patrice Marcotte, and Gilles Savard. An overview of bilevel optimization. Annals of operations research, 153(1):235-256, 2007.
Francis Crick. The recent excitement about neural networks. Nature, (37(6203) 1989.
Stephen Grossberg. Competitive learning: From interactive activation to adaptive resonance. Cog- nitive science, 11(1):23-63. 1987.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. CVPR, 2016.
G. E. Hinton, S. Osindero, and Y. W. Teh. A fast learning algorithm for deep belief nets. Neural Computation, 2006.

---

Published as a conference paper at ICLR 2021
Zhouyuan Huo, Bin Gu, and Heng Huang. Training neural networks using features replay. In NeurIPS, 2018a.
Zhouyuan Huo, Bin Gu, Qian Yang, and Heng Huang. Decoupled parallel backpropagation with convergence guarantee. In ICML, 2018b.
Sergey loffe and Christian Szegedy, Batch normalization: Accelerating deep network training by reducing internal covariate shift. In ICML, 2015.
Max Jaderberg, Wojciech Marian Czamecki, Simon Osindero, Oriol Vinyals, Alex Graves, David Silver, and Koray Kavukcuoglu. Decoupled neural interfaces using synthetic gradients. ICML, 2017.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. ICLR, 2015.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Tech- nical report, University of Toronto, 2009.
Dong-Hyun Lee, Saizheng Zhang, Asja Fischer, and Yoshua Bengio. Difference target propagation. In ECML-PKDD, 2015.
Timothy P Lillicrap, Daniel Cownden, Douglas Tweed, and Colin Akerman. Random feedback weights support learning deep neural networks. arXiv preprint arXiv:1411.0247, 2014.
Timothy Lillicrap, Adam Santoro, Luke Marris, Colin Akerman, and Geoffrey Hinton. Back- propagation and the brain. Nature Reviews Neuroscience, pp. 1-12, 2020.
Chenxi Liu, Barret Zoph, Maxim Neumann, Jonathon Shlens, Wei Hua, Li-Jia Li, Li Fei-Fei, Alan Yuille, Jonathan Huang, and Kevin Murphy. Progressive neural architecture search. In ECCV, 2018.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. In ICLR, 2019.
Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. In ICLR, 2017.
Sindy Löwe, Peter O' O'Connor and Bastiaan Veeling. Putting end end-to-end: Gradient-isolated learning of representations. In NeurIPS, 2019.
Renqian Luo, Fei Tian, Tao Qin, En-Hong Chen, and Tie-Yan Liu. Neural architecture optimization. In NeurlPS, 2018.
Adam H Marblestone, Greg Wayne, and Konrad P Kording. Toward an integration of deep learning and neuroscience. Frontiers in computational neuroscience, 10:94, 2016.
Geoffrey F Miller, Peter M Todd, and Shailesh U Hegde. Designing neural networks using genetic algorithms. In ICGA, volume 89, pp. 379-384, 1989.
Guido F Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. In NeurlPS, 2014.
Arild Nøkland. Direct feedback alignment provides learning in deep neural networks. In NeurIPS, 2016.
Arild Nøkland and Lars Hiller Eidnes. Training neural networks with local error signals. In JCMI,, 2019.
Hieu Pham, Melody Guan, Barret Zoph, Quoe Le, and Jeff Dean. Efficient neural architecture search via parameter sharing. In ICML. 2018.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le. Regularized evolution for image classifier architecture search. In AAAI, 2019.
10

---

Published as a conference paper at ICLR 2021
David E Rumelhart, Geoffrey Hinton, and Ronald J Williams. Learning representations by back- propagating errors. Nature, 323(6088):533-533 1986.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei- Fei. ImageNet Large Scale Visual Recognition Challenge. IJV, 115(3):211-52, 2015. doi:
10.1007/111266--55--81111
Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chied Chen. Mo- bilenetv2: Inverted residuals and linear bottlenecks. In ICCV, 2018.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In ICLR, 2015.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 15(():1929-1958 2014.
Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. In CVPR, 2016.
Haowen Xu, Hao Zhang, Zhiting Hu, Xiaodan Liang, Ruslan Salakhutdinov, and Eric Xing. Au- toLoss: Learning discrete schedule for alternate optimization. In ICLR, 2018.
Shen Yan, Biyi Fang, Faen Zhang, Yu Zheng, Xiao Zeng, Mi Zhang, and Hui Xu. Hm-nas: Efficient neural architecture search via hierarchical masking. In ICCV-W, 2019.
Arber Zela, Thomas Elsken, Tonmoy Saikia, Yassine Marrakchi, Thomas Brox, and Frank Hutter. Understanding and robustifying differentiable architecture search. In ICLR, 2020.
Muhan Zhang, Shali Jiang, Zhicheng Cui, Roman Garnett, and Yixin Chen. D-vae: variational autoencoder for directed acyclic graphs. In NeurlPS, 2019.
Barret Zoph and Quoe V Le. Neural architecture search with reinforcement learning. In ICLR, 2017.

---

Published as a conference paper at ICLR 2021
A IMPORTANCE OF BLOCK CONFIGURATIONS
0.17
As mentioned in Section 2 greedy block-wise learning is very sensitive to the choice of how to split the network into a set of blocks and the choice of the auxiliary head for each sub- network. To support our claim, we conduct a preliminary ex- and randomly
0.16
0.14
periment depicted in Figure We set K sample 30 configurations. For comparison, we also depict the results of backprop and SEDONA with 10 random seeds. Our experiment shows that difference in these two design choices can result in 6.01 %pp difference at maximum in terms of clas- sification error rate on CIFAR-10, which is larger than the performance gap between VGG-19 and ResNet.
0.13
random
backprop
SEDONA
Figure 6: Classification emross of VGG-19 (0.25x width) with 30 random configurations on CIFAR- 10 at K = 4.
B ADDITIONAL RELATED WORKS
Feedback without Weight Symmetry. Another biological implausiblity backpropagation is that it uses the same weights for both forward and backward passes, often coined as the weight transport problem (Grossberg, 1987). group of researches aim overcome this problem. Target Propagation eLee al. 2015) uses auxiliary auto-encoders to propagate optimal activations rather than gradients. Feedback Alignment (Lillicrap al.) 2014) replaces symmetric weights of the backward pass with random weights, which extended to variant named Directed Feedback Alignment (Nokland, 2016) without backward locking. However, aforementioned methods still suffer from update lock- ing (Belilovsky et al.] 2020). Moreover, there has been result that they can yield comparable performances to backpropagation on large-scale datasets such as ImageNet. On the other hand, our work shows that greedy block-wise learning without update locking.
outperform backpropagation ImageNet
Differentiable Architecture Search. DARTS (Liu et al. 2019) provides efficient way for neural architecture search (NAS) than previous methods based on reinforcement learning (Zoph & Lej 2017 Pham et al., [2018] Liu et al., 2018) and evolutionary algorithms (Miller et al., 1989] Angellne et al. 1994 Real et al. 2019). Moreover, it is more efficient than other gradient-basee NAS methods (Luo et al. 2018] Zhang et 2019). However, it often fails due overfitting to network weights, and thus several works have been proposed to overcome this limitation. Zela et al. (2020) relate the failure of DARTS with large dominant eigenvalues of Vna and suggest modifying the landscape of inner optimization by adding regularization to flatten the learning landscape for outer variables. Chen Hsieh (2020) also try to obtain smoother landscape of outer variables by injecting random or adversarial perturbations the inner optimization objective. Our pretraining and weight sampling strategies share the motivation of these works. Rather than monitoring the Hessian or injecting noise, regularize outer variables by taking the inner optimization multiple weights.
C ADDITIONAL EXPERIMENTS AND DISCUSSIONS
C.1 COMPARISON TO FEATURES REPLAY
We compare greedy learning methods (i.e. Predsim, DGL and SEDONA) to Features Replay (Huo al. (018a) with R00 on CIFAR-10. Features Replay suffers from more severe performance degradations when K 2 12 than greedy block-wise learning methods, For Features Replay, we use the same optimization setting as in backpropagation.
C.2 ADDITIONAL RESULTS ON IMAGENET
We also test ResNet- 152 using setting of Belilovsky et al. (2020) when K = Results can be found in Table We find that the SEDONA still achieves lower test errors. However, the training setting of Belilovsky et al. 2020), which trains only for 50 epochs. does not allow backprop to fully converge, and thus the reported performance of backprop in (Beliloosky et al. (2020) is significantly worse than that of ours, which trains for 600,000 iterations (i% 120 epochs) in me al. (2016).
12

---

Published as a conference paper at ICLR 2021
0.17
Backprop
0.16
ProfSim
0.15
0.14
SEDONA
0.13
0.12
Poplay
0.11
0.10
0.09
0.08
0.00
0.00
4
12
16
Figure 7: Comparison of classification errors of ResNet-101 when learning with increasing K, in- cluding Features Replay (Huo et 2018a).
Table 5:
Error rates (%) ImageNet with setting of Belilovsky al. (020) when K 2. The
results of Backprop and DGL are cited from Belilovsky et al. (2020).
Method
Top-1 Error (%)
Top-5 Error (%)
Backprop
25.6
DGL.
25.5
SEDONA
24.95
7.64
C.3 THE EFFECT OF DISCRETIZATION
SEDONA discretizes (a, 3) after optimizing them in continuous domain. Then, the natural ques- tion is how much performance loss the discretization procedure induces. Interestingly, we find that the discretization gap is not significant in a reasonable range K. When trained on CIFAR-10, continuous versions of VGG-19 19 and ResNet variants achieve similar test errors compared to the dis- cretized ones. We describe the test errors in Table may be because discretization does not affect much on both lower and upper layers for the following reasons:
As shown in Figure 4 the values â1 of lower layers are very close to or 1, so dis- cretization has little effect the training of these layers.
2. For upper layers, the local eлror signal and the global error signal are similar in terms of their contribution reducing the final validation loss.
SEDONA optimizes a, which the relative weight local and global gradients, to direction that minimizes the final validation loss. So, SEDONA learns O₁ close to 0.5 in upper layers (Figure4) implying that there is no significant difference between using local and global gradients for minimizing the global loss.
One possible counterargument is that SEDONA may have learned ã1 close 0.5 because it is better to mix local and global gradients with equal weights. However, this counterargu- ment can be easily refuted by the fact that the discretization gap is still insignificant, even with sufficiently large K that can split the upper layers more (Figure 3).
C.4 REGULARIZATION BY GREEDY LEARNING
We show that well-configured greedy learning can outperform backprop on various datasets Sec- 4 As the reason of that, we conjecture that greedy block-wise learning, in general, has a regu- larization effect.
Table 7 shows that the training errors of DGL and SEDONA on ImageNet are smaller than that of backpropagation. However, SEDONA achieves smaller validation errors than backprop, while DGL does not. So, the decoupling configurations found by SEDONA may better control the regularization effect of greedy block-wise learning.
In fact, gradient directions with decouplings by SEDONA more aligned to gradients by back- propagation. Figure shows the average cosine similarities for each timestep interval as well as the overall cosine similarity. While both the gradients of SEDONA and DGL correlate positively with
13

---

Published as a conference paper at ICLR 2021
Table 6: Error rates (%) on CIFAR-10 with Backprop, SEDONA (Cont.) and SEDONA (K = 4). Cont, denotes using (a, 3) learned in continuous domains without discretization.
Architecture
Backprop
SEDONA (Cont.)
SEDONA (K 4)
VGG-19
12.31
12.02
11.58
ResNet-50
7.99
7.60
7.53
ResNet-101
7.14
6.77
6,59
ResNet-152
6.35
6.24
6.13
Table 7: Error rates (%) on train and validation splits of ImageNet with Backprop, DGL and SE- DONA. For DGL. and SEDONA, we set K = 4.
Architectures
Method
train error
val error
Backprop
5.24
21.34
ResNet-101
DGL
7.60
23.13
SEDONA
7.19
21.32
Backprop
4.11
21.22
ResNett1152
DGL
5.56
22.89
SEDONA
4.13
21.09
0.825
0.800
0.750
0.725
0.790
DGL
SEDONA
SEDONA
DGL average
0.4
DGL sverage
0.650
SEDONA average
SEDONA average
(0. 12
[12 25
[25.k 10.60
[RAAK 243
(51.2 64d
12.22.4]]
(12.8L 25
[25.6 38.44)
[19.4 51.244
(51 F4d
interval
Interval
(a) VGG-19
(b) ResNet-50
0.90
akg codtte Siilboky
0.75
0.63
0.60
0.65
aNg
0.55
DGL
DSL
SEDORA
SEDONA
0.50
DGL
0.55
SEDONA
SEDONA
0.45
10. 12.228)
[12 25 mkl
1258k. SEAC
1354k.51.00 (SL24 544)
12
112.b 25 skl
125.k. 29.4
(1.44 (5124 54d
Uime interval
Uime interval
(c) ResNet-101
(d) ResNet-152
Figure 8: Comparison of the average cosine similarities for each timestep interval. We compute the cosine similarity between backprop gradients and DGL/SEDONA gradients of 3x3 convolution kernel each layer on CIFAR-10, 100, while training with DGL and SEDONA, respectively.
the backprop gradients, the correlation in SEDONA is higher than in DGL all time step intervals across all architectures.
One reason for appropriate regularization of SEDONA may be because SEDONA directly minimizes the final classifier's &s validation loss for optimizing a and 3.
C.5 THE TRADEOFF BETWEEN PERFORMANCE AND SEARCH TIME.
While decoupling configurations found by SEDONA outperforms PredSim, DGL and backprop, requires extra search cost. The search cost could be reduced at the cost of performance by removing
14

---

Published as a conference paper at ICLR 2021
Table 8: Performances and search costs of SEDONA after removing some key components one by one. Without pretraining, we 8K additional iterations for convergence.
Top-1 Error Rates (%)
GPUs
Search Time (GPU days)
Method
CIFAR-10
Miny-lmageNet
Pretraining
Bilevel Opt.
SEDONA (K 4)
6,59
40.88
6
10.1
extra inner steps
6.62
41.04
2
1.3
weight sampling
6.76
42.70
pretraining
6.89
43.86
2
1.9
Backprop
7.14
44.50
PredSim (K 4)
7.93
46.08
DGL (K 1)
8.30
46,20
Table 9: Architecture of Aux 4 on ImageNet. For Aux i < 4, we remove final invertied residual blocks. N₂ denotes the number of channels at the convolutional layer on which the auxiliary head is augmented.
PwiseConv, ReLU No, BN
DwiseConv x 3, ReLU N. stride padding BN
InvResidual, ReLU N, stride 1. expansion ratio
InvResidual, ReLU 1.5 N, stride expansion ratio
InvResidual, ReLU 1.5 No stride 1, expansion ratio 4
PwiseConv ReLU 2048, BN
AdaptiveAvgPool x
FC 1000
some key components of SEDONA such as extra inner optimization steps, weight sampling and pretraining. Table shows that all the components effective for accuracy. Without both extra inner steps and weight sampling, we can still achieve the better performance than backprop with only the search cost of 0.8 GPU days.
D ARCHITECTURAL DETAILS
D. BASE ARCHITECTURES
ResNet-50/101/152. For CIFAR-10 and Tiny-ImageNet, we remove the MaxPool layer after the initial convolutional layer in ResNet variants. For CIFAR-10, we also use kernel size and stride of 1 at the initial convolutional layer. In SEDONA, we regard each residual block in ResNets as layer and the first convolutional layer included the first layer. The final AvgPool+FC layers are used as the final block's auxiliary head.
VGG-19. We add batch normalization layer (loffe Szegedy 2015) after every convolutional
layer, and do not use Dropout (Srivastava et al. 2014). We regard the final 3-layer MLP as the final block's auxiliary head.
D.2 AUXILIARY HEADS
As mentioned in Section 4.1 Aux i consists of point-wise convolution, depth-wise convolutional layer, (i - 1) inverted residual blocks and a point-wise wise convolution followed by an AvgPool and a FC layer. We describe the detailed architectures in Table 9 For CIFAR-10, For PredSim, we use the feature dimension of 2048 on Tiny- Ima-emm and ImageNet and 512 on CIFAR-10.
the 0.25x width.
15

---

Published as a conference paper at ICLR 2021
Table 10: ResNet-152: 16 layers with the highest learned values of di and their corresponding auxiliary headers.
Layer Index
11
13
17
19
22
23
25
26
28
29
49
31
48
38
37
36
Aux. Header
4
4
4
3
2
4
2
2
4
2
4
4
4
4
Table 11: ResNet-101: 16 layers with the highest learned values of @ auxiliary headers.
and their corresponding
Layer Index
7
11
12
22
25
27
28
29
19
32
31
30
26
24
23
20
Aux. Header
4
4
4
4
4
4
4
3
2
4
4
4
(1)
Table 12: ResNet-50: 15 layers with the highest learned values of 0i auxiliary header.
and their corresponding
Layer Index
10
12
11
13
15
14
9
6
2 8
3 1 7
Aux. Header
4
4
2
1
Table 13: VGG-19: 15 layers with the highest learned values of o and their corresponding auxil- iary header.
Layer Index
6
13
14
15
12
11
9
7
10 4
5
2
1
3
Aux. Header
1 4 1
1
D.3
FOUND DECOUPLINGS
Table 10
shows layers with the largest values of σi and their corresponding auxiliary headers with the largest value of 3 for each architecture. For ResNet-101/152, show 16 layers with largest values of ai for better readability.
E OPTIMIZATION DETAILS
E.1 OPTIMIZATION AT SEARCH STAGE
We search for decouplings for VGG-19 and ResNet-50/101/152 CIFAR-10. We 40% of CIFAR- 10 training split as a validation set. For the outer optimization, we use Adam optimizer (Kingma & Ba 2013) with a fixed learning rate of 0.01 and weight decay of 0.000001. For the inner optimization, we use SGD with a momentum of 0.9 and weight decay of 0.001. We use an initial learning rate of 0.1 and decay it down 0.001 with the cosine annealing learning rate decay (Loshchilov & Hutter (0177). Label smoothing (Szegedy et al.) 2016) of 0.1 is also used. We repeat bilevel optimization steps for iterations. As mentioned in Section 3.3 we pretrain weights for 40K iterations with outer variables fixed zero and store 50 sets of weights with the best validation accuracies. For pretraining, we use the same setting as in the inner optimization. During pretraining, evaluate weights the validation set every 80 iterations. For pretraining and the inner optimization, we use the standard data augmentation strategy of padding, random crop and random flip.
E.2 OPTIMIZATION EVALUATION STAGE
In all experiments, bel smoothing (Szegedy et al. 2016) of 0.1 is used for Backprop, DGL and SEDONA. For PredSim, 0.99 is used coefficient of similarity loss in Nøkland & Eidnes (2019).
the cosine annealing learning rate decay (Loshchilov & Hutter 2017). La-
CIFAR-10. For evaluation on CIFAR-11 10 dataset, we train all our models for 64K iterations with a batch size of 128 using SGD with momentum of 0.9. For all experiments CIFAR-10, an initial learning rate of 0.1 and decay it down to 0.001. For VGG-19 and R0s1et-50/101, we use weight decay of 0.0001 while weight decay of 0.0002 is used for ResNet- 10% of train data
16

---

Published as a conference paper at ICLR 2021
Table 14: Search costs of SEDONA.
GPUs
Search Time
Architecture
Pretraining (days)
Bilevel Opt. (days)
Total
Pretraining
Bilevel Opt.
(GPU days)
VGG-19
0.1
0.5
2.1
ResNet-50
0.2
3.8
ResNet-101
6
0.3
1.6
10.1
ResNet-152
6
0.5
2.5
15.5
Table 15: Wall-clock training times (hours) of Backprop, DGL and SEDONA (ours) on ImageNet.
DGL
SEDONA
Architecture
Backprop
K
K
K
K
ResNet-100
113.5
80.2
59.2
67.3
56.5
ResNet-112
158.5
104.8
71.2
98.5
78.3
used the validation set. We follow the standard data augmentation strategy padding, random crop and random flip in Nøkland & Eidnes (2019).
Imag-Ne. For evaluation on Imny-ImageNet dataset, we train all our models for 30K iter- ations with batch size of 256. For Backprop, DGL and SEDONA, an initial learning rate is 0.1, which is decayed down to 0.001 with cosine annealing, and SGD with a momentum 0.9 is used. A weight decay of 0.0001 is used for VGG-19, ResNet-50/101, and weight decay of 0.0002 is used for ResNet-152. However, we fail to train well with the momentum optimizer for PredSim. So, Adam optimizer (Kingma & Bal 2015) instead. We which is decayed down to 0,000001, and a weight decay of 0.0001 for all architectures for PredSim. In addition, subsample 40 classes per batch until 15K iterations following Nøkland & Hidnes) (211)). We use the standard data augmentation strategy of padding, random crop, random rotation and random flip.
initial learning rate of 0.0005,
ImageNet. For ImageNet dataset, we train all our models for 600K iterations with a batch size of 256 using SGD with momentum 0.9, A weight decay of 0.00005 is used for both ResNet-101 and ResNet-152 We use an initial learning rate of 0.1 decayed down to 0.0001 for ResNet-101 101, and 0.05 down 0.00001 for ResNet-152.. We use the standard data augmentation of random resized crop and random flip. We report the accuracy in the single-crop setting.
F IMPLEMENTATION & COMPUTING ENVIRONMENTS
F.1 IMPLEMENTATION DETAILS
For implementation, we use Python 3.8 and PyTorch 1.6.0. At the search stage, we use the higher library" to enable differentiable weight updates in PyTorch computational graphs. For evaluation, we implement asynchronous updates of blocks by introducing queues between blocks. For PredSim, DGL and Features Replay implementations, refer to their official PyTorch implementations We use mixed precision training with Apex on Tiny-ImageNet and ImageNet.
F.2 COMPUTING ENVIRONMENTS
We report our search cost and wall-clock training time in Table 14 and 15| respectively. All experi- ments are conducted with total 8 NVIDIA Quadro 6000 GPU cards and 2 2-core Intel Xeon E5-2620 v4 processors with 256 GB RAM. For search, we use 4 GPUs VGG-19 and ResNet-50 and GPUs for ResNett101/152.
http:tes///hiiooco///aaatttrrera DGL: http::ttaa/tgthbb.ccmm
eugenium/ Features hettrnnssoooooooottss/////taoood
https://g http:///tt.hhu.cccoo/////ii/taa/ http::/:///tttuuub.om//aa/a/a htt.://..ccccooolloo//////eeeeee
17


Reviews:
[{"review_id": "pTAZCT9X2CI", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary Of Contributions: This paper proposes to automate the design of auxiliary network and its allocation under decoupled neural network scheme, a design that speeds up network training and potentially boost model accuracy. The approach is validated with leading performance on ResNet and VGGNet under various datasets.\n\n\nStrengths:  The idea to search auxiliary network for decoupled neural network is novel, and the proposed method is verified on multiple widely used datasets.\n\nWeaknesses: \n\n1.\tIt’s unclear if the proposed differentiable search algorithm works better than DARTs with direction comparison, as the proposed method is basically DARTs with some changes (e.g. weight sampling, extra inner optimization steps per outer optimization), that are also applied to typical NAS tasks, a comparison with DARTs is needed to validate how much of the gain is from the proposed method rather than the fact of automating network design itself.\n\n2.\tIt seems that the decoupled neural network scheme has nearly no gains in terms of Top-1 without the auxiliary heads ensembled as shown in Table 3. The details should be provided on how the ensemble works, are ensembled auxiliary heads kept during the testing stage? If so, Table 3 cannot tell if the gain is from the ensembled aux heads or decoupled neural network scheme. Network trained with Backprop method and identical extra aux head for ensemble might reach the same level of performance.\n\n3.\tExperiment with DGL in Table3 (b) is problematic, DGL in its original paper only provides ResNet-152 result with K=2, and it is better than Backprop according to their experiment. Yet the authors set K=4 in Table 3 and got a contrary result. This brought up the suspect of cherry picking of hyperparameters and can only be addressed with stricter comparison.\n\n4.\tOne of the advantages to adopt a decoupled neural network scheme is training speedup, while the network based on compared methods is instantly available, the proposed method requires extra time to search before training. With this extra cost, how much the training speedup benefit is still left? The search cost should be indicated and the overall time cost should be discussed.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "F09Fqn5y7b6", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a method for decoupled training of neural networks called SEDONA. In the spirit of recent trends in greedy layer-wise and indirect training, SEDONA allows gradient information to flow either from the next layer as in backpropagation or from an auxiliary head, trying to make a prediction using the current layer's output. Since a direct search for the best decoupled configuration results into probing a combinatorial number of splits, authors propose a continuously relaxed formulation which they later discretize. Transferring the found decoupled configurations to datasets different from the \"pretraining\" ones shows improvements in terms of validation accuracy and training time.\n\nI find the overall topic of asynchronous or backpropagation-free training of neural networks very interesting and the submitted paper particularly relevant to this topic. The proposed search algorithm is novel to my knowledge and may be found useful in the community. However, I think authors should have put more effort into understanding SEDONA. \n\nThe major points are the following:\n1. The effect of discretization is not studied. I would be interested in seeing how well does a continuous configuration perform and what kind of accuracy loss (if any) is caused by discretization. \n2. I wonder why SEDONA performs better than backprogation (sometimes much better as in Tiny ImageNet)? Is it because not following the true (stochastic) gradient acts as regularization? One way of assessing this would be to also provide training loss or accuracy values. Why is your top1 error value for ResNet-152 is about two percent higher that in the original paper by He et al, 2015?\n3. If the update directions configured by SEDONA lead to such a good performance, how do they correspond to the true gradients? Do they correlate positively? To what extent can such decoupled feedback implement credit assignment in a neural network?\n\nI believe that addressing these questions is very important prior to publication of the method.\n\nMinor comments:\n1. $\\theta$ does not appear on the RHS of (1).\n2. Auxiliary head ensembling is not explained very clearly. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "39YsHS1puue", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Summary\n\nThis paper proposes a differentiable architecture search approach for splitting a deep network into locally-trained blocks to achieve training speedup. The approach achieves better performance than using backprop on small datasets (CIFAR10 and TinyImageNet), and comparable or slightly improved performance on ImageNet with 2x claimed training speedup. Learned network architecture choices seem to transfer between datasets.\n\n### Strong points\n\nS1: The method outperforms comparable baselines, and significantly improves performance over standard backprop for small datasets (CIFAR10 and TinyImageNet)\n\nS2: The learned network architectures transfer between tasks.\n\nS3: On ImageNet, the method achieves slightly improved performance with claimed 2x training speedup.\n\n### Weak points\n\nW1: This seems like a pretty complicated approach to only get 2x speedup in training, and besides slight improvement in performance, that seems like the only benefit this method achieves for realistically large datasets like ImageNet.\n\nW2: \"Speedup\" is not really defined. i assume this is the wall-clock time to achieve convergence, but I couldn't find a definition of convergence or stopping criterion, or how speedup is measured.\n\nW3: Complicated optimization tricks seem necessary to get the bilevel optimization to work (Section 3.3: \"In bilevel optimization, meta variables (α, β) depend on the learning trajectory of layer and auxiliary weights (θ, φ) (i.e. a sequence of values of (θ, φ) during inner optimization). As a consequence, there exists a risk of overfitting the meta variables to a specific episode\"). If I have the choice between 2x training time with straight-forward optimization, versus 1x training time with complicated bilevel optimization that needs to be tuned, I would probably choose the former option, since I need to spend a lot less time debugging and tuning parameters.\n\n### Recommendation\n\nI think this paper is marginally below the acceptance threshold. The results seem decent, though a little underwhelming (see W1), but the biggest concern for me is that key concepts are unclear or ambiguous (e.g. definition of speedup is unclear, see W2, \"confidence of \\alpha at lower layers\", see C2, and how the \"backprop\" gradients are computed and used in equation (2), see Q2).\n\nIf these issues were clarified I would be inclined to increase my score. But as it stands, this feels like a complicated method without much payoff (only 2x training speedup with slightly improved performance). It's possible that I'm missing something or not understanding the potential impact of the results, and explicit discussion of this and/or improved clarity of the description and evaluation of the method may help.\n\n### Questions\n\nQ1: What is the absolute wall-clock time for training that the speedup is reported on?\n\nQ2: Given that the gradients used to train each block are a combination of local and backpropped gradients, how does this method avoid the locking problem, and thus provide speedup? \n\n### Other comments\n\nC1: The \"2.02x\" speedup number looks a little funny; are two decimal places justified? Perhaps better to just say \"2x speedup\"?\n\nC2: In Section 4.4, the paper says, \"Surprisingly, SEDONA yields much more confident values of $\\alpha_1^{(l)}$ (i.e. close to either 1 or 0) at lower layers than upper layers,\", but when I look at Figure 4, at first glance I thought that \\alpha is _less_ confident at lower iterations, according to the provided definition, compared to later iterations (which are all at 1). But then I realized the plot uses a log scale. Consider using a linear scale here instead? Or at least describe the confidence in terms of the log scale.\n\nC3: I find the usage of all-caps CONV to be a little odd, at least I've never seem that before. Maybe just say \"convolution\"? Doesn't seem like CONV saves much space.\n\nC4: I find this key statement to be unclear: \"denotes whether layer l should utilize local gradients (i.e. the last layer of a block) or backpropagated gradients (i.e. the inside layer).\" Is this saying that if a local gradient is used for a layer, then it is a candidate for being the last layer of a block, and if backpropped gradient is used, then it is a candidate for being the inside layer of a block? Some rewording of this sentence should help.\n\nC5: Typos, in Appendix B: \"to flat the learning landscape\" -> \"to flatten the learning landscape\", Section 4.1: \"to let auxiliary networks in the pool computationally lightweight\" -> \"to let auxiliary networks in the pool be computationally lightweight\", Section 3.3: \"Such warm start\" -> \"Such a warm start\", Section 1: \"If local signals are lousy representative of the global goal\" -> \"If local signals are not representative of the global goal\"", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a novel method for greed layer-wise training by considering the learning signal from either backprop or from the additional auxiliary losses. SEarching for DecOupled Neural Architecture learns to identify the decoupled blocks by learning the gating parameters similar to gradient-based architecture search algorithms, such as DARTs.  The empirical experiments demonstrated the effectiveness of SEDONA on CIFAR and TinyImageNet using various ResNet architectures. Several issues of clarity and the correctness of the main theoretical result were addressed during the rebuttal period in the way that satisfied the reviewers. The ideas in this paper are interesting and are broadly applicable. Additional experiments / discussions on the tradeoff between initial search cost and accuracy should be included in the final version. 
Decision: Accept (Poster)