Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies personalized sparse training for federated learning. The proposed method FedSpa is a novel personalized federated learning scheme that employs personalized sparse masks to customize sparse local models on the edge.  The authors provide the theoretical result with regard to the error bound and empirical results with several personalized federated learning methods.
main_review: Strengths:

1: This paper proposes a novel personalized federated learning scheme by incorporating sparse-to-sparse searching techniques.

2: Extensive experiments are conducted to verify the superiority of the proposed algorithm.

3: This paper is well-written and easy to follow. The background knowledge is presented well. The readers can easily understand the paper.

Weaknesses:

1: The theoretical analysis in Theorem 1 is unclear and weak. It is unclear that what the error bound in Theorem 1 means. The authors need to analyze and compare the theoretical results to other comparable methods. 

2: The title is ambiguous and may lead to inappropriate reviewers.

3: I see no code attached to this submission, which makes me a bit concerned about reproducibility.


summary_of_the_review: I marginally accept this paper mainly due to its novelty and better experimental results. 

After reading the response, I keep my score at 6.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This submission proposes federated learning with personalized sparse mask (FedSpa) to apply sparse masks to the local models in training and communication, hence to make the model adaptive to its local data and also to reduce communication cost.

main_review: Strengths: Addressing the data heterogeneity and reducing communication cost are an important problems in federated learning. Using one architecture for all local models and different sparse masks seems a new idea in the field.

Weaknesses: 1) At every iteration, the Algorithm 1 FedSpa requires new masks to be computed, which highly increases the computational time on local machines. The experiments results only report the communication time without the total running time. It is not clear whether the wall clock time can be reduced or the contrary. Also the FedSpa requires communication every iteration which causes more communication cost.
 
2) One merit of using sparse masking is that it reduces the communication memory size and the Table 1 measures the communication cost in terms of GB, so a natural baseline would be FedAvg with compression techniques. A lack of such comparison makes the true effect of sparse masking questionable. 
summary_of_the_review: This paper has proposed a new method to address the heterogeneously distributed data problem in federated learning. However, the algorithms has some impractical components and the effects over state-of-the-art is not convincing enough due to lack of some baselines.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work studies personalized federated learning through sparse local masks. For each client, the local model is subset of the global model. The paper proposes and analysis a new method, named FedSpa, which trains sparse local models for all clients reducing communication size, the amount of computation and memory cost.
main_review: **1.** The idea of using sparse masks to model personalization for federated learning is not novel in this work. Prior works utilize this idea with other techniques (Li et al., 2020) (Vahidian et al., 2021). Moreover, several side-benefits such as low communication cost, cheaper computation, and fewer memory requirements should also be attributed to those original works where sparse masks are used, and the same side-benefits of sparsity were mentioned.

**2.** As far as I can see, the idea of current work that differs from the above two mentioned papers is how the sparse masks are handled throughout the training process. However, there does not seem to be done much progress in this direction neither. The authors nominate two heuristics on how to evolve sparse masks over the iterates, one of which is simply fixing the same mask for all clients and iterations. However, isn’t it the same as initially training the smaller model for all clients?

**3.** It was mentioned in the contributions that the problem of sparse PFL is rigorously formulated (I guess this refers to the last part of section 3, Sparse PFL problem (P4)). However, you do not provide a deeper understating of this formulation, e.g., How well it models personalization compared to other formulations? Why it makes sense to use a small subset of the global model (i.e., sparse masks) as the local, personalized model beyond what was heuristically proposed by (Li et al., 2020) (Vahidian et al., 2021)? Can the formulation (P4) be regarded as a particular case of regularized PFL (P3), say with $l_1$ norm?

**4.** The algorithm FedSpa seems to directly apply FedAvg (LocalSGD with partial participation) to the problem (P4). What is the novelty in the algorithm itself?

**5.** Theoretical analysis is very weak. Let us ignore the first two terms in the rate (5) and consider the third non-vanishing term $\Upsilon$. Using only Assumption 4 and running any method, one can upper bound the left-hand side of (5) by $d B^2$.

**6.** The title is somehow vague and does not describe the work well. The paper is on personalized federated learning, which is not reflected in the title.

summary_of_the_review: The level of originality is low given the prior works. A new formulation lacks deeper understanding and theoretical analysis is weak.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes an interesting approach to FL with heterogeneous client data. The main idea is 
to learn a common weight vector for all clients but allow them to individually mask this global weight vector. 

****
I appreciate the effort that authors put into adressing my concerns which have been partially covered. Thus, i have slighltly raised the grade of my recommendation. However, i would ask the area chair to verify if the authors have addressed all my concerns satisfactorily. In particular, im still not sure about the relation between (P4) and regularized PFL (P3) which is quite generic and also allows for reguarlizers that are indicator functions of sets. 


main_review: My main comments are : 

* The level or rigour needs to be improved. As a case in point, already the title suggests that the notion of "sparsity" 
is crucial for the proposed approach. However, i was not able to find a rigorous definition of the quantity "sparsity". 

* In my opinion the novelty of the proposed approach is limited. First of all, the sparse FPL problem is a special 
case of the regularized FPL problem (3) using a specific choice for the regulariser (requiring the non-zero entries 
of the i-th weight to agree for all clients. The regularised FPL has been studied in a sparse model context recently e.g. in 

* M.Yamada, T. Koh, T. Iwata, J. Shawe-Taylor and S. Kaski, "Localized Lasso for High-Dimensional Regression", Proc. AISTATS 2017 
* A. Jung, “Networked Exponential Families For Big Data over Networks,” in IEEE Access, Oct. 2020. doi: 10.1109/ACCESS.2020.3033817.
* Y. Sarcheshmehpour, M. Leinonen, A. Jung, “Federated Learning from Big Data over Networks,” to be presented at IEEE Int. Conf. on Acoustics, Speech and Sig. Proc., 2021.

it might be useful to compare your approach with the (generalised linear model based) methods proposed in above papers. 

* The FedSpa algorithm seems to be a straightforward combination of existing techniques (stochastic gradient descent and masking search techniques 
for sparse deep net training). 

* The relevance and usefulness of Theorem 1 is unclear. How did you use Theorem 1 for applying FedSpa (e.g., choice of hyper-parameters) 
in the numerical experiments of Section 5? Im also not sure if (5) can be referred to as "error bound" as it actually 
bounds the gradient of the objective function along the trajectory of the algorithm. However, the numerical experiments do not 
use this gradient as the figure of merit but the resulting accuracy. How is (5) relevant for bounding the accuracy of FedSpa? 

* The clarity or presentation and use of language needs significant improvement: 

- what are "fully dense PFL models" ? 
- what is "consistently cheap communication"? 
- "The Non-IID data distribution makes the training process prohibitively difficult, and the obtained global model may not fit all the local data." 
try to be more specific 
- ".. is another challenging problem that remains mysterious." 
- "FedSpa does not deploy a single global model, but allows each client to own its unique sparse model..." this is a bit confusing as FedSpa actually tightly couples 
the sparse model parameters of each client. as i understood, they must have the same non-zero weight value for each individual feature. 
- what is a "evolutionary sparse model" ?
- "... which is agnostic to all kinds of network architectures ..." with is meant by "being agnostic" here ? i believe that at least the assumptions on the loss 
function somehow interact with the particular network architecture. 

- "Experimental results ... also coincides with the theoretical conclusion." Pls explain more precisely what you mean by "theoretical conclusion".  

- "We emphasize that three main progresses are made towards the interpretable and SOTA compression-based PFL..." interpretability is a hot topic in machine learning. 
However, it is not clear how your approach ensures interpretability. Why is FedSpa interpretable?

- The masks appearing in (P4) need more discussion. Are these fixed but unknown (ground truth), or just some estimate. 

- "Mimicking the data-parallel solution ..." which solution are you referring here exactly? 

- "The framework of FedSpa is extensible ..."

- would it be possible to avoid "dist(m1,m2)" by using the ell0 norm (which is already used elsewhere). 

- what is "cosine annealing " ? 

- pls explicitly state any input/hyperparamter used in Algorithm 1,2 3 E.g. Algorithm 3 might have a random seed as its input. 

- "Our main focus of analysis is on the second and third non-vanished terms while communication round..."

- " The result in Eq. (5) is highly related to setting of sparse volume,..." ?

- " ... to perform update." which update ? 

summary_of_the_review: My main comments are : 

* The level or rigour needs to be improved. As a case in point, already the title suggests that the notion of "sparsity" 
is crucial for the proposed approach. However, i was not able to find a rigorous definition of the quantity "sparsity". 

* In my opinion the novelty of the proposed approach is limited. First of all, the sparse FPL problem is a special 
case of the regularized FPL problem (3) using a specific choice for the regulariser (requiring the non-zero entries 
of the i-th weight to agree for all clients. The regularised FPL has been studied in a sparse model context recently e.g. in 

* M.Yamada, T. Koh, T. Iwata, J. Shawe-Taylor and S. Kaski, "Localized Lasso for High-Dimensional Regression", Proc. AISTATS 2017 
* A. Jung, “Networked Exponential Families For Big Data over Networks,” in IEEE Access, Oct. 2020. doi: 10.1109/ACCESS.2020.3033817.
* Y. Sarcheshmehpour, M. Leinonen, A. Jung, “Federated Learning from Big Data over Networks,” to be presented at IEEE Int. Conf. on Acoustics, Speech and Sig. Proc., 2021.


it might be useful to compare your approach with the (generalised linear model based) methods proposed in above papers. 

* The FedSpa algorithm seems to be a straightforward combination of existing techniques (stochastic gradient descent and masking search techniques 
for sparse deep net training). 

* The relevance and usefulness of Theorem 1 is unclear. How did you use Theorem 1 for applying FedSpa (e.g., choice of hyper-parameters) 
in the numerical experiments of Section 5? Im also not sure if (5) can be referred to as "error bound" as it actually 
bounds the gradient of the objective function along the trajectory of the algorithm. However, the numerical experiments do not 
use this gradient as the figure of merit but the resulting accuracy. How is (5) relevant for bounding the accuracy of FedSpa?
review_title: null

Meta-review: Dear authors,

I have carefully read the reviews, rebuttals and the subsequent discussion. The review scores are mixed (5, 5, 6, 6). Let me comment on some of the key issues raised by the reviewers. I will elaborate on some of them with my own insights.

1) You insist that (P4) cannot be regarded as a particular case of (P3). But this is trivially incorrect. The hard constraint in the reformulation (P6) you mention in the discussion can be written as a regularizer: *indicator function* of the constraint set. Indeed, let  $\cal C$ be the set of points $W=(w_1,\dots,w_K)$ for which there exists $w$ such that $w_k = m_k^* \circ w$ for all $k$. Then the regularizer defined by ${\cal R}(W) = 0$ if $W\in {\cal C}$ and ${\cal R}(W) = +\infty$ if otherwise does the job. This is a well defined regularizer. Such regularizers are routinely used in optimization to model hard constraints. So, the formulation you consider is a special case of (P3).  Moreover, as pointed out by Reviewer Zg2F, and acknowledged by the authors, "The idea of using sparse masks to model personalization for federated learning is not novel in this work. Prior works utilize this idea with other techniques (Li et al., 2020) (Vahidian et al., 2021). Moreover, several side-benefits such as low communication cost, cheaper computation, and fewer memory requirements should also be attributed to those original works where sparse masks are used, and the same side-benefits of sparsity were mentioned." The claim that one of the novel contributions of FedSpa is "we formulate a clear optimization problem for FedSpa" is weak, especially in the light of the above comment, and the "moral" existence of the formulation in prior work, albeit not expressed in a mathematical notation. The fact that previous works did not formulate this properly is a major issue with those works, and not a major contribution of this work. A clear mathematical formulation of what one wants to achieve should be a standard requirement. In any case, I appreciate the clarity nevertheless. 

2) The same reviewer states that the key idea of the paper that differs from the above two mentioned papers is how the sparse masks are handled. One of the two ideas proposed is trivial and is equivalent to standard non-personalized FL (if all masks are the same, the submodes they defined can be considered a global model). The second idea does not seem to have any interesting/distinctive theoretical support. 

3) Sparse-to-sparse training in FedSpa may be novel, but the claim that "the masks continue to evolve (towards the optimal masks) in the training process" is not supported by theory nor experiments. If indeed you can show that the local masks evolve to some meaningful notion of an optimal mask, this would be interesting. 

4) I also agree with the other points raised by this reviewer. I have read the author response to these comments. (BTW: Language such as "you bet" is inappropriate). While some of them make sense, they do not reduce the severity of the concerns by a large enough margin. 

5) The comment about the weakness of the main theorem is particularly concerning. Indeed, the main theorem may be vacuous, and the authors need to do a thorough explanation of the result and its importance (on its own and in comparison with existing literature and rates). I do not believe such a comparison could be advantageous to the proposed method though. The expressions are complicated. It seems that for any meaningful mask size, the non-vanishing term will be too large. The theorem is not a valid convergence result as the authors do not show that the right hand side can indeed be provably made arbitrarily small by some choice of the parameters of the method. For instance, it is not guaranteed that $dist(m_{k,t}, m_k^*)$ will converge to zero. In this sense, calling this theorem "Convergence of personalized models" is incorrect and misleading. This is a fatal issue, unfortunately. The authors should make it absolutely clear that the result does not prove convergence. 

6) Assumptions 1, 2, and 4 are very strong. For example, Assumption 2 is not provably satisfied for lower bounded nonconvex smooth functions when subsampling (=minibatching) is used to produce the stochastic gradient. Assumption 3 is also quite strong: it is not satisfied by convex quadratics. Assumption 1 is also strong - most recent works on FL do not require any similarity assumptions. 

In summary, while this direction of research is interesting, the level of contributions in this work is marginal at best. The key theoretical result is misleading in that it does not imply convergence while it is marketed as such. Moreover, strong assumptions (relative to what is achieved in the latest papers) are used to obtain it. Because of these concerns, and other concerns raised by the reviewers, I do not have any other choice but to reject the paper.

Area Chair
Decision: Reject