Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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. 

Strength:
The idea is easy to follow and seems applicable to be adopted.
Paper is well structured and written in general.

Weakness:
1. Lack of explanations:
	(1) from reward measurement side (motivation side):
In 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.
	(2) from the update algorithm side:
The 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.
	(3)  from the updating setting side:
It 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.
	(4) re-initialize mechanism:
Re-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.
2. Evaluation:
	(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
	(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
	(3) in Fig2, it is curious why authors apply different settings on different datasets when comparing their methods	
	(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 
	(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
	(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
	(7) the authors did not mentioned how many runs which they have conduct their experiments to provide the results 
3. Some parts need to be further improved for example
	(1) Fig3, it would be good if authors can add some texts information for {1000, 5000}; 
	(2) Section3 is a little bit hard to follow need to be reorganized
	(3) Related work can be further improved to better cover most recent works
review_title: Easy to follow, and want to see more analysis and details

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary：
The 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.

Strengths:
1.  The paper is well written.
2.  The process of upper-bounding the loss difference is clear.
3.  Experiments are conducted on various datasets with various net structures to support the proposed method. 

Weakness:
My 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. 

----
The 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.   
review_title: A new application scenario with minor technical contribution

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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. 

=== pros ===

+ 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.   

+ 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.   

+ The paper is rounded out by practical items, such as encoding weight ids, a policy to determine when to retrain the network from scratch 
(re-initialization), and avoiding sending updates when validation error does not significantly change. 

+ 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".   

=== cons ===

- The overall presentation is difficult to parse.  
- 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. 
- 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%.  
- 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.  
- 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.  

=== suggestions / questions === 

Overall, I found the work interesting, useful, and complete (aside from eval sec questions above).   

It 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.  

Some 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. 

It 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.    

The 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).

Similarly Table 2 should have a column for the number of rounds that required no communication. 

DPU won't send updates if validation error doesn't decrease significantly.  It isn't clear whether you gave the same benefit to Full Updating. 

=== writing / terminology / notation ===

Overall 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.

The 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~?    

Sometimes you use L0 norms (S2 eq 2) and other times you use summation (S3.1).  

You 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).   

==== nits ==== 

Please learn the difference between that and which.   Remove "in order to."   Capitalize Figure and Section.   

Some references use name style, other use indices. But the bibliography is all by name.  #confused.   


review_title: Interesting work, hampered by presentation

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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. 

In 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. 

In 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. 

The 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? 
 
One 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. 

################ Feedback to the authors' response ###############

As the authors have addressed some of my main concerns and provided nice extra experimental results, I will raise my score to 6.

review_title: Looks a practical new approach but the justification may need improvement 

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