Deep Partial Updating
Authors: Zhongnan Qu
Cong Liu
Junfeng Guo
Lothar Thiele
Venue:  (2021)
Keywords: Partial updating
communication constraints
server-to-edge
deep neural networks

Abstract: Emerging edge intelligence applications require the server to continuously retrain and update deep neural networks deployed on remote edge nodes to leverage newly collected data samples. Unfortunately, it may be impossible in practice to continuously send fully updated weights to these edge nodes due to the highly constrained communication resource. In this paper, we propose the weight-wise deep partial updating paradigm, which smartly selects only a subset of weights to update at each server-to-edge communication round, while achieving a similar performance compared to full updating. Our method is established through analytically upper-bounding the loss difference between partial updating and full updating, and only updates the weights which make the largest contributions to the upper bound. Extensive experimental results demonstrate the efficacy of our partial updating methodology which achieves a high inference accuracy while updating a rather small number of weights.

Under review as a conference paper at ICLR 2021
DEEP PARTIAL UPDATING
Anonymous authors Paper under double-blind review
ABSTRACT
Emerging edge intelligence applications require the server to continuously retrain and update deep neural networks deployed on remote edge nodes to leverage newly collected data samples. Unfortunately, it may be impossible in practice to continuously send fully updated weights to these edge nodes due to the highly constrained communication resource. In this paper, we propose the weight- wise deep partial updating paradigm, which smartly selects only a subset of weights to update at each server-to-edge communication round, while achieving a simi- lar performance compared to full updating. Our method is established through analytically upper-bounding the loss difference between partial updating and full updating, and only updates the weights which make the largest contributions to the upper bound. Extensive experimental results demonstrate the efficacy of our partial updating methodology which achieves a high inference accuracy while updating a rather small number of weights.
INTRODUCTION
To deploy deep neural networks (DNNs) on resource-constrained edge devices, extensive research has been done to compress a well-trained model via pruning (Han et al., 2016) Renda et al., 2020) and quantization (Courbariaux et al., 2015 Rastegari et al., 2016). During on-device inference, compressed networks may achieve a good balance between model performance (e.g., prediction accuracy) and resource demand (e.g., memory, computation, energy). However, due the lack of relevant training data or an unknown sensing environment, pre-trained DNN models may not yield satisfactory performance. Retraining the model leveraging newly collected data (from edge devices or from other sources) is needed for desirable performance. Example application scenarios of relevance include vision robotic sensing in an unknown environment (e.g., Mars) (Meng et al.) (017). local translators mobile phones (Bhandare et al. 2019), and acoustic sensor networks deployed in Alpine environments (Meyer et al. 2019).
[Rnda
It is mostly impossible to perform on-device retraining edge devices due to their resource- constrained nature. Instead, retraining often occurs on a remote server with sufficient resources. One possible strategy to continuously improve the model performance
edge devices is a two-stage iterative process: (i) at each round, edge devices collect new data samples and send them to the server, and (iz) the server retrains the network using all collected data, and then sends the updates each edge device (Brown& & Sreenan 2006). An essential challenge herein is that the transmissions in the second stage are highly constrained by the limited communication resource (e.g., bandwidth, energy) in comparison to the first stage. Statc-of-the-art DNN models always require tens or even hundreds of mega-Bytes (MB) to store parameters, whereas single batch of data samples (a number of samples that can lead to reasonable updates in batch training) needs a relatively smaller amount of data. For example, for CIFAR dataset (Krizhevsky et al. (209).. the weights of a popular VGGNet require 66MM storage, while one batch of 128 samples only uses around 0.40MB (Simonyan & Zisserman 2015 Rastegari et al., 2016). As an alternative, the server sends a full update once or rarely. But in this case, every node will suffer from low performance until such update occurs.
Besides, edge devices could decide on and send only critical samples by using active learning schemes (Ash et al. 2020). The server may also receive training data from other sources, e.g., through data augmentation or new data collection campaigns. These considerations indicate that the updated weights which are sent to edge devices by the server at the second stage become a major bottleneck.
To resolve the above challenges pertaining to updating the network, we propose to partially update the network through changing only small subset of the weights each round. Doing so can significantly

---

Under review as a conference paper at ICLR 2021
reduce the cerver-to-device communication overhead. Furthermore, fewer parameter updates also lead to less memory access on edge devices, which in turn results in smaller energy consumption related to (compressed) full updating (Horowitz) 2014). Our goal of performing partial updating is to determine which subset of weights shall be updated at each round, such that a similar accuracy can be achieved compared to fully updating all weights.
Our key concept for partial updating is based on the hypothesis, that a weight shall be updated only if it has a large contribution to the loss reduction given the newly collected data samples. Specially, we define binary mask m to describe which weights are subject update, Le., m, 1 implies updating this weight and m; = 0 implies fixing the weight to its initial value. For any m, we establish an analytical upper bound on the difference between the loss value under partial updating and that under full updating. We determine an optimized mask m by combining two different view points: (i) measuring the "global contribution" of each weight to the upper bound through computing the Euclidean distance, and (it) measuring each weight's ' "local contribution" within each optimization step using gradient-related information. The weights be updated according to m will be further sparsely fine-tuned while the remaining weights are rewound to their initial values.
Related Work, Although partial updating has been adopted in some prior works, it is conducted in fairly coarse-grained manner, e.g., layer-wise or neuron-wise, and targets at completely different objectives. Especially, under continual learning settings, (Yoon et al., 2018 Jung et al. 2020) propose to freeze all weights related the neurons which are more critical in performing prior tasks than new ones, to preserve existing knowledge. Under ad adversarial attack settings, (Shokri & Shmatikov 2015) updates the weights the first several layers only, which yield a dominating impact on the extracted features, for better attack efficacy. Under architecture generalization settings, (Chatterji et al.) 2020) studies the generalization performance through the resulting loss degradation when rewinding the weights of each individual layer to their initial values. Unfortunately, such techniques cannot be applied in our problem setting which seeks a fine-grained, i.e., weight-wise, partial updating given newly collected training samples in an iterative manner.
The communication cost could also be reduced through some other techniques, egg., quantiz- ing/encoding the updated weights and the transmission signal. But note that these techniques are orthogonal to our approach and could be applied in addition. Also note that our defined partial updating setting differs from the communication-efficee (Lin et al. 2018; Kairouz et al. 2019), which study how to compress multiple gradients calculated on different sets of non-i.i.d. local data, such that the aggregation of these (compressed) gradients could result in similar convergence performance as centralized training all data.
distributed (federated) training settings
Traditional pruning methods (Han et al., 2016 Frankle & Carbin 2019 Renda et al.) 2020 aim at reducing the number of operations and storage consumption by setting some weights to zero. Sending pruned network (non-zero's 's weights) may also reduce the communication cost, but to much lesser extent as shown in the experimental results, see Section 4.4 In addition, since our objective namely reducing the server-to-edge communication cost when updating the deployed networks is fundamentally different from pruning, we can leverage some learned knowledge by retaining previous weights (i.e., partial updating) instead of zero-outing (i.e., pruning).
Contributions. Our contributions can be summarized as follows.
We formalize the deep partial updating paradigm, i.e., how to iteratively perform weight- wise partial updating of deep neural networks on remote edge devices if newly collected training samples are available at the server. This substantially reduces the computation and communication demand on the edge devices.
We propose a new approach that determines the optimized subset of weights that shall be selected for partial updating, through measuring each weight's contribution to the analytical upper bound on the loss reduction.
Experimental results on three popular vision datasets show that under the similar accuracy level, our approach can reduce the size of the transmitted data by 91.7% average (up to 99.3%), namely can update the model averagely 12 times more frequent than full updating.
2 NOTATION AND SETTING
In this section, we define the notation used throughout this paper, and provide a formalized problem setting, i.e., deep partial updating. We consider a set of remote edge devices that implement on-device
2

---

Under review as a conference paper at ICLR 2021
inference. They connected to host server that is able to perform network training and retraining. We consider the necessary amount of information that needs to be communicated to each edge device to update its inference network.
Assume there are in total rounds of network updates. The network deployed in the 7 round is represented with its weight vector w". The training data used to update the network for the y round is represented as D = 5D" U Dr In other words, newly collected data samples 6D" are made available to the server in round r
To reduce the amount of information that needs to be sent to edge devices, only partial weights of w"-1 shall be updated when determining w". The overall optimization problem for weight-wise partial updating in round r - 11 can thus be formulated as
min 8w"
é (w"" + "ww";
s.t.
|ów0)lo S k-I
(2)
where l denotes the loss function, I1-llo denotes the LO-norm, & denotes the defined updating ratio which is closely related to the communication demand between server and edge devices. and ow" denotes the increment of w--1 Note that both w""1 and dww" are drawn from R', where I denotes the total number of weights.
In this case, only a fraction of k 7 weights and the corresponding index information need to be communicated to each edge device for updating the network in round namely the partial updates ow". It is worth noting that the index information is relatively small in size compared to the partially updated weights (see Section 4 On each edge device, the weight vector is updated as w" = w--1 + 6w". To simplify the notation, we will only consider a single update, i.e., from weight vector (corresponding to w" to weight vector i (corresponding w²) with
+ 8w
3 PARTIAL UPDATING
We develop a two-step approach for resolving the partial updating optimization problem in Eq (). The final implementation used for the experimental results, see Section con- tains some minor adaptations that do not change the main principles as explained next. In the first step, we compute subset of all weights with only k I weights. These weights will be al- lowed to change their values. In the second step, we optimize the weights in the chosen subset (considering the constraint of Eq. (b) to mini- mize the loss function in Eq. (). The overall
w
w
w
Aw
w
w 1
W
5w
w
w (w"
w) @ m
Figure 1: The figure depicts the overall approach that consists of two steps. The first step is depicted with dotted arrows and starts from the deployed network weights w. In Q steps, the network is op- timized which results in weights wf, Based on the collected information, mask m is determined that characterizes the set of weights that are rewound to the ones of w. Therefore, the initial solution for the second step has weights + dw m. This initial solution is further optimized to the new weights w by only changing weights that are al- lowed according to the mask, i.e., dw has only nonzero elements where the mask is 1.
approach is depicted in Figure I
The approach for the first step not only deter- mines the subset of weights but also computes the initial values for the second (sparse) opti- mization step. In particular, we first optimize the loss function Eq. from initial weights w with a standard optimizer, e.g., SGD or its vari- ants. As result, we obtain the minimized loss (w-) with w' w + ów:, where the super- script f denotes "full updating". To consider the constraint Eq. 2). the information gathered during this optimization is used to determine the subset of weights that will be changed and therefore, that need to be communicated to the edge devices.
3

---

Under review as a conference paper at ICLR 2021
the mask with E {0, to describe which weights are subject to change and which ones are not. The weights with m, = are trainable, whereas the weights with m, 0 will be rewound from the values in w to their initial values in w, Le., unchanged. Obviously, we find ||m||lo~ = Σ, m; = k J. In summary, the purpose of this first step is to determine an optimized mask
In the explanation of the method in Section 3.1
In the second step we start a weight optimization from a network with weights from the optimized network wf and (1 k) weights from the previous, still deployed network w. In other words, the initial weights for this optimization are w + ow & m. where @ denotes an element-wise multiplication. We still use standard optimizer. To determine the final solution w + Ew, we conduct a sparse fine-tuning, i.e,, we keep all weights with m, = 0 constant during the optimization. Therefore, Ew is zero wherever m, = 0, and only weights where m, are updated.
3.1 METRICS FOR REWINDING
We will now describe new metric that allows us determine the weights that should be kept constant, Le., those whose masks satisfy my = 0. Like most learning methods, we focus on minimizing a loss function, since the loss is a more general metric than, for example, accuracy and perplexity, which are the metrics only used for classification and language modeling respectively. But we still report the other metrics in the evaluation. The two-step approach relies on the following assumption: the better the loss E(w + 8w O m. of the initial solution for the second step, the better the final loss ((w). Therefore, the first step in the method should select a mask m such that the loss difference [(w + dw @ m) ((w!) is small as possible.
We will determine an optimized mask m by combining two different view points. The "global contribution" uses information contained in the difference dw between the initial weights w and the optimized weights wf by the first step, namely the norm of incremental weights. The "local contribu- tion" takes into account some gradient-based information that is gathered during the optimization in the first step, i.e., in the path from w to w.. Both kinds of information will be combined to determine an optimized mask m.
The two view points are based on the concept of smooth differentiable functions, see for example (Nesterov 1998). A function ((x) with f Rdd R is called T-smooth if it has Lipschitz continuous gradient g(z):: [1g(x) - s ll S Tl| - yll2 for all x; Note that Lipschitz continuity of a gradient is essential ensuring convergence of many gradient-based algorithms. Under such condition, one can derive the following bounds, see also (Nesterov) 1998):
If f(x) 9(x)² (y x)1 S L/2 ll x112 Vz,y
(3)
This basic relation is used to justify the global and the local contributions, ie., the rewinding metrics.
Global Contribution. Following some state-of-the oftee-of-the-att methods for pruming, one would argue that a large absolute value in ow = w - w indicates that this weight has moved far from its initial adopt the widely used unstructured magnitude pruning to solve
value in w. This motivates the problem of determining an optimized mask m. Magnitude pruning prunes the weights with the lowest magnitudes in network, which is the current dest-performett pruning method aiming the trade-off between the model accuracy and the number of zero's 's weights (Renda et al. 2020).
Using a b la b), Eg. can be reformulated as f() f(x) g(x) (y x) 1f(y)
f(x) 9(z) (y- - x) < L/2 lly - x Thus, we can bound the relevant difference in the loss E(w + ow 3 m) - (n)-(w")
as
(4) where (ww)) denotes the gradient of the loss function at wf, and 1 is vector whose elements are all 1. As the loss is optimized at wf, i.e., g(w") ss O. we can assume that the gradient term is much smaller than the norm of the weight differences in Eq. Therefore,
[(w + ow c m) f(w") S g( (owl @ (m 1)) + L/2 11öw @ (m 1)
obtain approximately
f(w + sw @ m) ((w S L/2 11ó o (1 114-mm m)]l
(5)
The right hand side is clearly minimized if m, = 1 for the largest absolute values of dw This information captured the contribution vector
global ow @ du
(6)
4

---

Under review as a conference paper at ICLR 2021
as 1T (celobal ② (1 m)) 11ó2 (1 m2
In summary, the k weights with the largest values in calobal are assigned to mask values my 1 and are further fine-tuned in the second step, whereas all others are rewound from w and keep their initial values in w. The pseudocode of Alg. in Appendix A.I shows this first approach.
Local Contribution. As experiments show, one can do better when using in addition some gradient- based information gathered during the first step, i.e., optimizing the initial weights in Q traditional optimization steps, w w
+ w + w + + w = w..
Using + b < la b/. (3 can be reformulated [(x) f(y) + g(x)" 2) < 1f(y) f(x) - ((0) F (y x) 1/22 yy 2112. This leads us to bound each optimization step as
(ww9~1 ((wa) S -e Aw + L/2 ||
where Aw = w w For a conventional gradient descent optimizer with a small learning rate we can use the approximation Ig (( Awol ||w" [ and obtain ((w9-1) ((w9) S -(w=~1iT Aw". Summing up over all optimization iterations yields approximately
((w' - -ww') {((w') x Σ 9=1
g(w 1 Aw
(8)
Note that we have w = wt - ow and di = E Aws. Therefore, with m we reformulate Eq.88 as (w + ow @ @m)) ((ww) U(m) with the upper bound U(m)
-Eq= (0=19(w"-17) (Aw" @ (1 - m)) where we suppose that the gradients are approximately constant for small m. Therefore, an approximate incremental contribution of each weight dimension to the upper bound on the loss difference é (w + dw @ m) L(w") can be determined by the negative gradient vector at m = 0, denoted as
local @m(m)
Q Σ E 2 Aw!
dm
This term used model the accumulated contribution of each weight to the overall loss reduction.
Combining Global and Local Contribution. So far, we independently calculate the global and local contributions calobal and clocall respectively. To avoid the impact due the scale, first normalize each contribution by its significance in its own set (either global contribution set or local contribution set). We conduct experiments on how combine both normalized contributions, e.g., taking the minimum. Interestingly, the most straightforward combination (i.e., the sum of both normalized metrics) yields better and more stable performance. Intuitively, local contribution can better identify critical weights w.r.t. the loss during training, while global contribution may be more robust for a highly non-convex loss landscape. Both metrics may be necessary when selecting weights to rewind. Therefore, the total contribution is computed as
global
IT glocal local
(10)
T oglobal
and m; for the A largest values of e and m; corresponding algorithm is shown in Alg, 2 in Appendix A.2
otherwise. The pseudocode of the
3.2 (REE)INIIIAALIZATION OF WEIGHTS
In this section, we discuss the initialization of our method. DD denotes the initial dataset used to train the network w from a randomly initialized network wa. D corresponds to the available dataset before deployment, or collected the 9th round if there are no data available before deployment. (6D").L denotes newly collected samples in each subsequent round.
Experimental results show (see Appendix D.I) that starting from a randomly initialized network can yield higher accuracy after several rounds, compared to always training from the last round with weights w" -1 As a possible explanation, the optimizer could end in a hard to escape region of the search space if always trained from the last round for long sequence of rounds. Thus, propose
5

---

Under review as a conference paper at ICLR 2021
re-initialize the weights after certain number of rounds. In such case, Alg. does not start from the previous weights w" but from randomly initialized weights. The re-initialized random network can be efficiently sent to the edge devices via single random seed. The device can determine the weights by means of a random generator. This is communication-efii from hard to escape region of the search space in comparison other alternatives, such as learning to increase the loss or using the (averaged) weights in the previous rounds, as these fully changed weights need to be sent to each node. Each time the network is randomly re-initialized, the new partially updated network may suffer from an accuracy drop. However, we can simply avoid such an accuracy drop by not updating the network if the validation accuracy does not increase compared to the last round, see more details in Appendix D.2 Note that the learned knowledge thrown away by the re-initialization can be re-learned afterwards, since any newly collected samples are continuously stored and accumulated in the server. This also makes our setting different from continual learning, which aims at avoiding catastrophic forgetting without accessing (at least not all) old data.
way of a random shift
To determine after how many rounds the network needs to be re-initialized, we conduct extensive experiments on different partial updating settings, see more discussions and results in Appendix [.2] In conclusion, the network is randomly re-initialized long the number of total newly collected data samples exceeds the number of samples when the network was re-initialized last time. For example, assume that round the model is randomly (re-)initialized and partially updated from this random network on dataset DD Then, the model will be re-initialized at round r + n, if |D'+*] >> 2 |. I. In the following, we use Deep Partial Updating (DPU) to present rewinding according the combined contribution to the loss reduction (i.e., Alg. 2 with the above re-initialization scheme.
EVALUATION
We implement DPU with Pytorch (Paszke et al. 2017). and evaluate its performance on multiple
vision datasets, including MNIST (LeCun & Cortes 2010), CIFARIO (Krizhevsky et al. 2009).
IISVRRC12 (lmageNet) (Russakovsky et al., 2015) using multilayer perceptron (MLP), VGGNet
(Courbariaux et al., 2015; Rastegari et al. 2016), ResNet34 (He et al. (016), respectively. We randomly select 30% of each original test dataset (original validation dataset for ILSVRC12) as the validation dataset, and the remainder as the test dataset. Let| |.| denote the number of samples in the dataset. Let | |6D' |} represent the available data samples along rounds, where |0D" is supposed to be constant along rounds. Both D and 8D" are randomly drawn from the original training dataset (only for evaluation purposes). For all precpessesingg and random initialization, we apply the tools provided in Pytorch. We use the average cross-entropy as the loss function without a regularization term for better studying the effect on the training error caused by newly added data samples. We use Adam variant of SGD as the optimizer, except that Nesterov SGD is used for ResNet34 following the suggestions in (Renda al. 2020). The test accuracy is reported, when the validation dataset achieves the highest Top-1 accuracy. When the validation accuracy does not increase compared to the last round, the model will not be updated to reduce communication overhead. This strategy is applied in all methods for a fair comparison. More implementation details are provided in Appendix C We will open- source the code upon acceptance.
One-shot Rewinding vs Iterative Rewinding, Based on previous experiments on pruning (Renda jt al.] 2020), iterative pruning with retraining may yield a higher accuracy compared to one-shot pruning. yet requiring several times more optimization iterations and also extra handcrafted hyperpa- rameters (e.g., pruning ratio schedule). This paper focuses on comparing the performance of DPU with other baselines including full updating given the same number of optimization iterations per round. Thus, we conduct one-shot rewinding at each round, i.e., the rewinding is executed only once to achieve the desired sparsity (as shown in Alg. 2).
Indexing. DPU generates a sparse tensor. In addition to the updated weights, the indices of these weights also need to be sent to each edge device. A simple implementation is to send the mask m. m is a binary vector with I elements, which are assigned with I if the corresponding weights are updated. Let S., denote the bitwidth of each single weight, and S, denote the bitwidth of each index. Directly sending m yields an overall communication cost of I k Sw + I 5z with S.- = 1.
To save the communication cost on indexing, we further encode m. Suppose that is random binary vector with a probability of & to contain 1. The optimal encoding scheme according to Shannon yields S_ (k) = k. log(1/k) (1 - -k) log (1((1 - k)). Coding schemes such as Huffman

---

Under review as a conference paper at ICLR 2021
block coding can come close to this bound. Partial updating results in smaller communication data size than full updating, if S. I >> Sw k- I + S (k) -L Under the worst case for indexing cost, yield a smaller
i.e., (k 0.5) I. as long k < (32 1)/32 0.97, partial updating communication data size with S., = 32-bit weights. In the following experiments, we will use report the size of data transmitted from server each node each round, contributed by the partially updated weights plus the encoded indices of these weights.
Sw k I (z)
4.1 ABLATION STUDY OF REWINDING METRICS
Settings. We first conduct a of ablation experiments regarding different metries of rewinding discussed in Section 3.1 We compare the influence of the local and glohal contributions as well as their combination, terms of the incremental training loss caused by rewinding. The original VGGNet and ResNet34 are fully trained on a randomly selected dataset of 10 and 4 x 10 samples, respectively. We execute full updating, i.e., the first step of our approach, after adding 10 and 2 x 10 new randomly selected samples, respectively. Afterwards, we conduct one-shot rewinding with all three metrics, i.e., global contribution, local contribution, and combined contribution. Each experiment is conducted for a single round. We report the results over five runs.
Results. The training loss (mean standard deviation) after full updating (i.e., f(w")) and after rewinding (i.e., {(w + ,w @ m)) with three metrics is reported in Table Note that these loss values are only intermediate results during partial updating. As seen the table, the combined contribution always yields lower or similar training loss after rewinding compared to the other two metrics. The smaller deviation also indicates that adopting the combined contribution yields more robust results. This validates the effectivenesss of our proposed metric, i.e., the combined contribution to the analytical upper bound on loss reduction.
Table 1 Comparing the training loss after rewinding according to different metrics.
Training loss
Benchmark
k
Full updating
Global
Local
Combined
0.01
3.042 + 0.068
2.588 + 0.084
2,658 1 0.086
VGGNet
0.05
2.509 = 0.056
1.799 : 0.104
1.671 + 0.062
0.086 + 0.001
(CIFAR1O)
0.1
2.031 = 0.046
+
0.994 0.034
0.2
1.196 = 0.049
0.739
0.417=0.000
0.01
3.340 = 0.109
0.156
+.179+00.052
ResNet34
0.05
2.005 = 0.064
1.84440.000
1.016 - 0.000
(ILSVRC12)
0.1
1.632 + 0.044
2.662 + 0.048
1.609 + 0.025
0.2
1.331 + 0.016
3.626 + 0.062
1.327 + 0.008
4.2 EVALUATION ON DIFFERENT BENCHMARKS
Settings. To the best of our knowledge, this the first work on studying weight-wise partial updating network using newly collected data iterative rounds. Therefore, we developed three baselines for comparison, including (i) full updating (FU), where at each round the network is fully updated with a random initialization (i.e., training from scratch, which yields a better performance as discussed in Section 3.2): (ii) random partial updating (RPU), where the network is trained from w"-1, while we randomly fix each layer's weights with a ratio of (1 k) and sparsely fine-tune the rest; and (it) global contribution partial updating (GCPU), where the network is trained with Alg. [ without re- initialization described in Section 3.2 Note that (iil) is extended from a state-of-the -hrt unstructured pruning method (Renda et al. 2020). The experiments are conducted with different types of networks on different benchmarks as mentioned earlier.
We report the test accuracy of the network w" along rounds in Figure 2 All methods start from the same w an entirely randomly initialized network. As seen in this figure, DPU clearly yields the highest accuracy in comparison to the other partial updating schemes on different benchmarks. For example, DPU can yield a final Top-1 accuracy of 92.85% on VGGNet, even exceeds the accuracy (92.73%) of full updating, while GCPU and RPÚ only acquire 91.11% % and 82.21% 1% respectively. In addition, we compare three partial updating schemes in terms of the accuracy difference related to full updating averaged over all rounds, and the ratio of the communication cost over all rounds related
Results.
7

---

Under review as a conference paper at ICLR 2021
to full updating in 2 As seen in the table, DPU reaches a similar even higher accuracy as full updating, while incurring sigmificantly fewer transmitted data sent from the server to each edge node. Specially, DPU saves around 99.3%. 98.2% and 77.7% of transmitted data on MLP, VGGNet, and ResNet34, respectively (91.7% in average). The communication cost ratios shown in Table 2 differ a little even for the same updating ratio k. This is because if the validation accuracy does not increase compared to the last round, the model will not be updated to reduce the communication overhead (also see the first paragraph of Section 4p. We also report the number of updated rounds in Table 2
We further investigate the benefit due to DPU in terms of the total communication cost reduction, as DPU has no impact on the edge-to-serve server communication involving newly collected data samples. This experimental setup assumes that all data samples in 8D" are collected by N edge nodes during all rounds and sent to the server on a per-round basis. For clarity, let Sa denote the data size of each training sample. During round r. we define per-node communication cost under DPU as Sa . 1 |8D"|/N + (S... k I T (k) T). Due to space constraints, the detailed results are shown the total
in Appendix D.3.1 We observe that DPU can still achieve significant reduction communication cost, egg., reducing up to 88. 88.2% on updating MLP and VGGNet even for the worst case (i.e., single node). Moreover, DPU tends be more beneficial when the size of data transmitted by each node to the server becomes smaller. This is intuitive because in this case the server-to-edge communication cost (thus the reduction due to DPU) dominants in the entire communication cost.
MLP on MNISE, (1000, 2000), 0.005
VGGNNt on CHPARLD, (AUU, 1000),
0,01
10 1LSVICH2, (4 10" 10%) A-22
0.9
aco.Rzy
0.05
0.85
DPU
0.9
0.75
GCPU
0.7
RPU
20
10
P0
50
round
round
round
Figure 2: DPU is compared with other baselines on different benchmarks in terms of the test accuracy.
Table 2: The average accuracy difference over all rounds, the ratio of communication cost over all rounds related to full updating, and the number of rounds that are required to send partial updating.
Average accuracy difference
Ratio of communication cost (Updating rounds)
Method
MLP
VGGNet
ResNet34
MLP
VGGNet
ResNet34
DPU
-0.17%
+0.33%
-0.12%
0.0071 (22)
0.0183 (35)
0.2226 (5)
GCPU
-0.72%
-1.51%
-1.01%
0.0058 (18)
0.0198 (38)
0.2226 (5)
RPU
-4.04%
-11.35%
-4.64%
0.0096 (30)
0.0167 (32)
0,2226 (5)
4.3 IMPACT DUE TO VARYING NUMBER OF DATA SAMPLES AND UPDATING RATIOS
Settings. In this set of experiments, we demonstrate that DPU outperforms other baselines under varying number of training samples and updating ratios. We also conduct an ablation study concerning the re-initialization of weights discussed in Section 3.2 We implement DPU with and without re- initialization, GCPU with and without re-initialization and RPU (see Section 4.2p on VGGNet using CIFAR1O dataset. We compare these methods with different amounts of samples {[D*), and different updating ratios k. Each experiment runs three times using random data samples.
Results. We compare the difference between the accuracy under each partial updating method and that under full updating. The mean accuracy difference (over three runs) is plotted in Figure 3 A comprehensive set of results including the standard deviations of the accuracy difference is provided in Appendix D.4 Note that the green curves in Figure discussed in the next section. As seen in Figure DPU (with re-initialization) always achieves the highest accuracy. The dashed curves and the solid curves with the same color can be viewed as the ablation study of our re-initialization scheme. Particularly given a large number of rounds, it is critical to re- re-initialize the start point w' after performing several rounds (as discussed in Section 3.2)
3 represent pruning methods that will be
In the first few rounds, partial updating methods (including random partial updating) almost always yield higher test accuracy than full updating, i.e., the curves are above zero. This is due to the fact
8

---

Under review as a conference paper at ICLR 2021
{1000, 5000)
(5000, 10003
{1000, 1000)
0.04
0.04
0.00
DPU with reinit.
DPU reinit.
0.02
3azzuracy (meaa))
0.02
Jascuracy (mesn)
0.04
GCPU with rainit.
GCPU w/o reinit.
RPU
0.1
3accurscy
0.02
Pruning
-0.02
6
10
12
10
20
30
40
50
-0.04
10
20
80
40
50
round
round
round
Aacouracy (msan)
Anvaracy (mean)
Auccuracy (mean)
0.01
0..6
-0.05
00.05
-01-
-0.1
.0.1
0
10
10
20
30
40
50
20
40
round
round
round
Figure 3: Comparison w.r.t the mean accuracy difference (full updating as the reference) under different { |0)"") (representing the available data samples along rounds, see in Section and updating ratio (k = 0.1, 0.01) settings.
that the amount of available samples is relatively small in the first few rounds and partial updating may avoid some co-adaptation of weights which happens in full updating. This results in higher validation/test accuracy. Note that the three partial updating methods perform almost randomly in
the first round compared to each other, because the limited sample size (i.e., (D+I) is not sufficient to distinguish between critical weights. This fact also motivates us to (partial) updating the first deployed model when new data are available.
4.4 COMPARING PARTIAL UPDATING WITH PRUNING
Settings. We compare the partial updating methods mentioned in Section 4.3 with a state-of-the-ar pruning method proposed in (Renda et al. 2020). where the network is first trained from a random initialization at each round, then conducts one-shot magnitude pruning (set weights as zero), and finally, is sparsely fine-tuned with learning rate rewinding. The ratio of non-zero's 's weights in the pruning method is set to the same as the updating ratio to ensure the same communication cost.
Results. We compare the difference between the accuracy under each method and that under full updating. The mean accuracy difference (over three runs) is plotted in Figure 3 As seen, DPU outperforms the pruning method in terms of accuracy by large margin, especially under small updating ratio. Note that we preferred a smaller updating ratio in our context because it explores the limits of the approach and it indicates that with the same accumulated server-to-edge communication cost.
improve the deployed network more frequently
Note that one of our chosen baselines, global contribution partial updating (GCPU, Alg. D. could be viewed as counterpart of the pruning method, i.e., pruning the incremental weights with the largest magnitudes. By comparing GCPU (with without re-initialization) with "pruning", we conclude that retaining previous weights yields better performance than zero-outing the weights (pruning).
5 CONCLUSION
In this paper, we present the weight-wise deep partial updating paradigm, motivated by the fact that continuous full weight updating may be impossible in many edge intelligence scenarios. We present DPU, which is established through analytically upper-boundigg updating and full updating, and only updating the weights which make the largest contributions the upper bound. Extensive experimental results demonstrate the efficacy of DPU which achieves a high inference accuracy while updating a rather small number of weights.
the loss difference between partial

---

Under review as a conference paper at ICLR 2021
REFERENCES
Jordan T. Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. International Confer- ence on Learning Representations, 2020. httpp:::://pppeeee.eeeeee net forum? id=
Lych2JBKPS
Aishwarya Bhandare, Vamsi Sripathi, Deepthi Karkada, Vivek Menon, Sun Choi, Kushal Datta, and Vikram Saletore. Efficient 8-bit quantization transformer neural machine language translation model. In Proceedings of the 34th International Conference Machine Learning, Joint Workshop on On- On-Device Muchine Learning & Compact Deep Neural Network Representations, 2019.
S Brown and CJ Sreenan. Updating software in wireless sensor networks: A survey. Dept. of Computer Science, National Univ. of Ireland, Maynooth, Tech. Rep, pp. 1-14, 2006.
Niladri Chatterji, Behnam Neyshabur, and Hanie Sedghi. The intriguing role of module criticality in the generalization deep networks. In International Conference on Learning Representations, 2020. URL htttps::/ppeerii..erttr. wwtp://rttttoommmmmemmmmmm -iw.:mmmmi--eeeeee
Yunjey Choi. Pytorch tutorial on language model, 2020. 2020. URL https: httpp::/ggtptub..... ctm. http://ggttuu.bommmmnjj/ee////
model
Accessed: 2020-03-17.
Matthieu Courbariaux, Yoshua Bengio, and Jean-Pierre David. Binaryconnect: Training deep
neural networks with binary weights during propagations. In Proceedings of Advances Neural Information Processing Systems, pp. 3123-3131,2011
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable
neural networks. In International Conference on Learning Representations, 2019. |
//openreview. net/
Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. In Proceedings of International Conference on Learning Representations, 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, 2016.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
Mark Horowitz. 1.1 computing's energy problem (and what we can do about it). In 20/4 IEEE International Solid-State Circuits Conference Digest of Technical Papers (ISSCC), 2014.
Sangwon Jung, Hongjoon Ahn, Sungmin Cha, and Taesup Moon. Adaptive group sparse regulariza- tion for continual learning. CORR, 2020.
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet. Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings. Rafael D'Oliveira, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečny, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateck Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramer, Praneeth Vepakomma, Jianyu Wang. Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. 2019.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar10 (camadian institute for advanced research), 2009. URL http:: http:://wwww www.. toronto. wdw.-kriz/iiif.. hhtm]
10

---

Under review as a conference paper at ICLR 2021
Yann LeCun and Corinna Cortes. MNIST handwritten digit database, 2010. URL http://yann lecun. wttp/etcmeeccecccctctttto....eet
Yujun Lin, Song Han, Huizi Mao, Yu Wang, and William Dally. Deep gradient compression: Reduc-
ing the communication bandwidth for distributed training. In International Conference Learning Representations, 2018. URL StLLhttp//// htttt::////pent httt:::://ppenrevieee
net/forum net/ forum? ?idiiiiiii---e 1d=
Mitchell P Marcus, Mary Ann Marcinkiewicz, and Beatrice Santorini. Building a large annotated corpus english: The penn treebank. Computational Linguisties, 19(2):313-33, 1993.
Z. Meng. H. Qin, Z. Chen, X. Chen, H. Sun, F. Lin, and M. H. Ang. A two-stage optimized next-view planning framework for 3-d unknown environment exploration, and structural reconstruction. IEEE Robotics and Automation Letters, 2(3): 1680-1687, 2017.
Matthias Meyer, Timo Parei-Campagna Akos Pasztor, Reto Da Forno, Tonio Gsell, Jérome Faillettaz, Andreas Vieli, Samuel Weber, Jan Beutel, and Lothar Thicle. Event-triggered natural hazard moni- toring with convolutional neural networks on the edge. In Proceedings of the 18th International Conference on Information Processing in Sensor Networks, IPSN 19. Association for Computing Machinery, 2019.
Yurii Nesterov. Introductory lectures convex programming volume i: Basic course. Lecture notes, 1:25, 1998.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary Detito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. In Proceedings of NIPS Autodiff Workshop: The Future of Gradient-based Machine Learning Software and Techniques, 2017.
Pytorch. Pytorch example on resnet, 2019. htt.http:://iichubbo http:////ggttttbccoo///oorrr//// on/ b /lob/mastter//orcciiiis on /ooodeeeeeeeeeeeme/eeoooooooooe s/resntt. Accessed: 2019-10-15.
Mohammad Rastegari, Vicente Ordonez, Joseph Redmon, and Ali Farhadi. Xnor-net: Imagenet classification using binary convolutional neural networks. In Proceedings of European Conference on Computer Vision, pp. 525-542, 2016.
Alex Renda, Jonathan Frankle, and Michael Carbin. Comparing fine-tuning and rewinding in neural network pruning. In International Conference on Learning Representations, 2020. URL
https://cpenreview net/ forumridd-ioooo /to
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bemnstein, Alexander C. Berg, and Li Fei-Fei. Imagenet large scale visual recognition challenge. International 2015.
Jounnaan Journal of Computer Vision, 115(3):211-252,
Reza Shokri and Vitaly Shmatikov, Privacy-preserving deep learning. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, CCS '15, 2015, doi: 10.114558100003221136,, URL/attps: / org http://111115/2111100100 211.3888137777
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In Proceedings of International Conference on Learning Representations, 2015.
Jachong Yoon, Eunho Yang, Jeongtae Lee, and Sung Ju Hwang. Lifelong learning with dynamically expandable networks. In International Conference on Learning Representations, 2018. URL https::/openrest net/ 1d=
11


Reviews:
[{"review_id": "t7gtu0tlTVd", "reviewer": "AnonReviewer3", "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": "This paper proposes a deep partial updating paradigm that can reduces the computational and communication cost on the edge devices by only updating most important weights in each round instead of a full update.  It also proposes metrics to select weights by global and local contributions and the experiment results show the efficacy of the proposed methods. \n\nIn summary, the method proposed in this paper looks practical and easy to implement, but the theoretical justification needs further clarification. I'm not sure about the significance of this paper as I'm not an expert in this area, so I prefer to leave this to other reviewers to decide. \n\nIn general, the paper is well written and easy to follow, and the motivation is sound.  However, the justification of the global and local contributions need to be clarified further. The inequality of Eq.(3) can hold only if f is L-smooth and convex,  which indicates the loss function is assumed L-smooth and convex. So what's the justification of the definition of global and local contributions  when the loss is non-convex which is the most common case in the experiments?  Without the theoretical justification, the global contribution that selects weights with largest values is basically as the same as pruning,  and the local contribution basically measures the changed loss caused by the update of a weight.  Although they may be still practical but the novelty is limited. \n\nThe experiment results show that the proposed method can obtain similar performance with the full updating but costs much less communication overhead.  It seems a very practical method in this area and the paper provides an interesting empirical study. The simple combination of global and local contributions outperforms each individual contribution, I'm wondering if authors have tried more other ways to combine them? And why this way is better? \n \nOne minor comment regarding the structure of the paper: as the initialization strategy plays an role in this method, it would be better to put the experimental results of comparing different initializations to the formal content, and the appendix can be put after the bibliography in one file. \n\n################ Feedback to the authors' response ###############\n\nAs the authors have addressed some of my main concerns and provided nice extra experimental results, I will raise my score to 6.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "n2PiTrWYmb9", "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": "In this paper, the authors have proposed a new approach to determine the optimized subset of weights instead of simply conduct full weights updating. In order to better update the weights, they measure each weight's contribution to the analytical upper bound on the loss reduction from two sides (global and locally). After evaluation, a weight will be updated only if it has a large contribution to the loss reduction given the newly collected data samples. The experimental results show that their method can achieve a high inference accuracy while updating a rather small number of weights. \n\nStrength:\nThe idea is easy to follow and seems applicable to be adopted.\nPaper is well structured and written in general.\n\nWeakness:\n1. Lack of explanations:\n\t(1) from reward measurement side (motivation side):\nIn the introduction, the authors did not explain why they pick the loss as the weight measurement criteria instead of others (e.g., accuracy). While they report the accuracy in the evaluation part as one evaluation results.\n\t(2) from the update algorithm side:\nThe paper did mention their weights updating method is determined via both global and local contributions, and they talked in 3.1 'It turns out experimentally, that a simple sum of both contributions leads to sufficiently good and robust final results'. however, it is not convincing that those two facts can have the equal impacts on the final prediction.\n\t(3)  from the updating setting side:\nIt seems that the defined updating ratio is one important factor as discussed in section2, not  enough contents are provided in the paper to describe how to calculate this ratio.\n\t(4) re-initialize mechanism:\nRe-initialize is also another important factor in the weight updating as discussed in section 3.2 'trained from the last round for a long sequence of rounds. Thus, we propose to re-initialize the weights after a certain number of rounds', however, the computation of how many rounds the network needs to be re-initialized seems not plausible.\n2. Evaluation:\n\t(1) lack of comparison: It would be good if authors can apply their method on some recent works (or models), which can also show others how flexible their method can be adopted or applied\n\t(2) there is no contents in the paper showing how authors decide their experiment settings, for example, why authors always select k (weight changing ratio) as very small 0.01, 0.05, 0.1, 0.2 instead of 0.5\n\t(3) in Fig2, it is curious why authors apply different settings on different datasets when comparing their methods\t\n\t(4) for section 4.2, it would be good if the authors can also try other initialization ways, for example using the average weights in each round window instead of directly using the latest round weights \n\t(5) in Table 1, it seems full updating still can beat the combined method, however, in Fig2, authors did not explain why DPU has better performance than other settings even compare with the full update\n\t(6) in Fig3, while DPU with re-init can achieve best performance than others, there is no explain about why it did not perform well in the first few rounds\n\t(7) the authors did not mentioned how many runs which they have conduct their experiments to provide the results \n3. Some parts need to be further improved for example\n\t(1) Fig3, it would be good if authors can add some texts information for {1000, 5000}; \n\t(2) Section3 is a little bit hard to follow need to be reorganized\n\t(3) Related work can be further improved to better cover most recent works", "extra_scores": {}, "extra_text": {}}, {"review_id": "hiBqWalxLy", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "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：\nThe paper proposes a weight-wise partial updating paradigm which adaptively selects a subset of weights to update at each training iteration while achieving comparable performance to full training. Experimental results demonstrate the effectiveness of the proposed partial updating method.\n\nStrengths:\n1.  The paper is well written.\n2.  The process of upper-bounding the loss difference is clear.\n3.  Experiments are conducted on various datasets with various net structures to support the proposed method. \n\nWeakness:\nMy major concern is about novelty and contribution. Although the paper show some application scenarios of partial updating, I still think that pruning would be more proper. Furthermore, the metric of global contribution and local contribution is quite like choosing two similar weight norms to select top-k weight, which is very similar to pruning tasks. So I suggest rejecting this paper. \n\n----\nThe authors’ rebuttal and the revised version have not fully addressed my concerns. It is not surprise that partial updating outperforms pruning by a large margin, as the inference of small updating still uses the whole weights of the network. Comparing to pruning, the technical contribution of this work is limited, so I would like to keep my original rating.   ", "extra_scores": {}, "extra_text": {}}, {"review_id": "RaICKq1iSD3", "reviewer": "AnonReviewer4", "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:  This paper presents a method to reduce the bandwidth required to update DNN models on edge devices.   The key insight is that model updates typically incorporate new data (training samples), and that after doing so, a minority of weights capture the majority of change due to retraining.  The authors propose a method by which to identify this weight subset, and compare the relative size (and test accuracy) of that update to that of other solutions (such as sending the entire network or sending a random subset of the weights on each retraining round).  Experiments with a number of existing data sets and models illustrate that the approach reduces update size more than 77% while maintaining reasonable test accuracy. \n\n=== pros ===\n\n+ Paper is sufficiently motivated.  As edge devices use more (and larger) models and as their count increases, the relevance of partial update techniques to accomodate model decay will remain.   \n\n+ The proposed technique provides a \"sister\" technique to pruning, not identifying nodes with greatest weights to retain, but identifying weights with the greatest changes to retain.  The policy is informed by choosing weights that minimize the difference in loss between the fully retrained network and its partially updated version.   \n\n+ The paper is rounded out by practical items, such as encoding weight ids, a policy to determine when to retrain the network from scratch \n(re-initialization), and avoiding sending updates when validation error does not significantly change. \n\n+ The evaluation looks at a variety of angles, the ratio of initial training set to update size, different data sets and architectures, and compares to a random partial update strategy as well as a simplified version of their approach \"GCPU\".   \n\n=== cons ===\n\n- The overall presentation is difficult to parse.  \n- The technique owes much to pruning methods and methodologies.   The technical approach (choosing weights, iterative rewinding) follows from recent work on pruning.  It would be great to have that discussion in related work, moving it out of Section 3.1 and Section 4. \n- Ultimately, existing pruning techniques can reduce networks by 90%.  By Amdahl's law, this implies that these techniques reduce communication by 7-10%, not 70-99%.  \n- Equally important, does the technique work well on pruned networks?  Unimportant updates may not be as available in such networks.  On the other hand, if you do the comparison and all updates are important, then over the course of the lifetime of the installed NN, using DPU instead of pruning would be the winner.  \n- Experiments in key graphs aren't clear: is there re-initialization in Figure 2?  Figure 3 performance never falls relative to full updating during re-initialization.  While the text (S3.2) makes it seem that the nodes reset all weights, using only 1% of the weights would impact test accuracy relative to full updating.  \n\n=== suggestions / questions === \n\nOverall, I found the work interesting, useful, and complete (aside from eval sec questions above).   \n\nIt would be useful to introduce a metric that combines update size with accuracy loss at the beginning of the paper.  The evaluation does this, but consider pulling it forward and defining it explicitly.  Each round incurs a communication cost in bytes and experiences some accuracy, so, for example, one can capture changes in accuracy per byte, i.e. model improvement by update size.  Since you are comparing to other techniques that can reduce the bandwidth similarly, we want to optimize this ratio.  \n\nSome networks work very well with small k.   But how low can you go?   I.e., how does one choose k?   Perhaps the accuracy/bytes metric could be informative. \n\nIt would be interesting to discuss on why winning lottery ticket theory gets us 80-90% reductions, but this technique admits 99% reductions by retaining information in the rest of the network.    \n\nThe startup procedure is not clear.  The graphs and discussion in S3.2 make it sound like the entire network re-initializes.  Can we be clear about what the first network looks like?  I'd assume all the weights.  But if we start from random values (sending the seed), the first round only updates $kI$ weights.  Can the test performance of the network with only 1% of its weights be 65% (Figure 2)?  Similarly, if DPU is re-initializing, why is the test accuracy monotically increasing -- the installed network would go back to ground zero.  Clearly I'm missing something, or your measuring the performance of the network at the server (w^f) and not the installed network (w^r).\n\nSimilarly Table 2 should have a column for the number of rounds that required no communication. \n\nDPU won't send updates if validation error doesn't decrease significantly.  It isn't clear whether you gave the same benefit to Full Updating. \n\n=== writing / terminology / notation ===\n\nOverall the presentation is difficult to get through.   For instance, Section 3 has many awkward constructions.  It seems like there's a simple picture here, similar to the Train, Prune, Retrain flow of pruning work.  It seems deeply analogous, with the exception that rewinding replaces pruning.  The evaluation section refers to Alg 1 and Alg 2, but Section 3.0 refers only to \"step 1\" and \"step 2\".   Are there better words than step?  This section also refers to the second step as an \"optimization\" step.   You end P1 by saying you're optimizing eq 1 in step 2, then you say step 1 optimizes the same equation.  The last sentence of the S3.0P3 re-iterates what was said in P1.  I'm sorry, but it's a bit of a slog.\n\nThe use of notation is consistent.  There are a couple of things that felt like speed bumps.   I kept wanting to parse \\delta W and \\delta D using \\delta as a variable, like $kI$.  At the end of section 2, introducing a new form of w^r as w~, was confusing.  Do we need w~?    \n\nSometimes you use L0 norms (S2 eq 2) and other times you use summation (S3.1).  \n\nYou use curly braces S4P1 for the sizes of the initial training and updates.  It looks like a set, not a configuration.  The text says the two sizes \"represent the available data samples.\"  But here it's just a configuration -- it's not the set of samples at all (and it wouldn't be b/c not all updates R are present).   \n\n==== nits ==== \n\nPlease learn the difference between that and which.   Remove \"in order to.\"   Capitalize Figure and Section.   \n\nSome references use name style, other use indices. But the bibliography is all by name.  #confused.   \n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes an approach to selectively update the weights of neural networks in federated learning. This is an interesting and important problem. As several reviewers pointed out, this is highly related to pruning although with a different objective.  It is an interesting paper but is a marginal case in the end due to the weakness on presentation and evaluation. 


Decision: Reject