Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper presents a new algorithm for DP federated learning (with trusted central server) under model personalization assumptions. The algorithm (CENTAUR) works by having the clients only send a subset of their parameters to the central server to be trained privately. The final (classification) layer is trained on each client non-privately. The authors provide rigorous analysis for the specific problem of linear representation learning (LRL) and further support the efficacy of their algorithm empirically with experiments. 
strength_and_weaknesses: Strengths:

- The paper provides a substantial rate improvement over existing work for the problem of LRL
- The paper provides sound empirical reasoning for their method (i.e. that data representations are less prone to distribution shift)
- The paper supports its results empirically

Weakness:
- The $O(d/n)$ rate is stated is for the matrix 2-norm but Jain et al. 2021 provide convergence guarantees for the Frobenious norm, making the comparison to existing work less clear.
- The proposed algorithm is not incredibly novel compared to prior work. 
- The presentation of the analysis for the theoretical results is a bit verbose. Theorem 5.1 and 5.2 are not easily interpreted on their own and it seems more useful instead to provide a more direct statement of Corollary 5.1.
- Given the rate improvement, an investigation into what DP lower bounds suggest is necessary would be nice.
clarity,_quality,_novelty_and_reproducibility: The paper makes precise statements and provides adequately detailed proofs. The experiments are likewise well documented. 
summary_of_the_review: The paper makes progress for the problem model personalization under user level differential privacy and federated learning constraints.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors propose to solve the statistical heterogeneity problem in federated learning with differential privacy by separating the model into two parts, one part for each client is personalized and different while the other part on the server is shared for all the clients. The communication between the client and the server is the non-private gradient for updating the part on the server, and privacy is guaranteed by using the Gaussian mechanism on the server. The authors proved rates for their method on a linear setting for the utility-privacy tradeoff which improves the SOTA by $\sqrt{d}$. The empirical performance is also very good.
strength_and_weaknesses: Major strengths: 
1. This idea is intuitive and the empirical performance is very good.
2. The theoretical statements are very detailed.

Major weaknesses: 
1. The LRL problem assumes that the true model is $y_{ij}=(w_{i}^*)^T (B^*)^T x_{ij}$ where there is no noise in $y_{ij}$. This is different from Jain et al. (2021). I know that you can set the $\sigma_F=0$ in Jain et al. (2021) Lemma 4.4, but this is not mentioned in the current paper, so the comparison may not be fair. Another problem is that the rate in Jain et al. (2021) Lemma 4.4 is for $\\|\cdot\\|_F$ while the rate in Theorem 5.1 in this paper is for $\\|\cdot\\|_2$. As we know $\\|\cdot\\|_2 \leq \\|\cdot\\|_F$ for matrices, this comparison is not fair.
2. Corollary 5.1 is not solid. It claims a lower bound but we only have an upper bound for the utility in Theorem 5.1. This can be revised and needs to be corrected.
3. In the experiments, the authors said 'we do not perform any data augmentation, as we observe that naive data augmentation
for DP training leads to worse accuracy, as also reported in De et al. (2022).' But I think De et al. (2022) actually recommends doing augmentation in the correct way '... leveraging the benefits of data augmentation by averaging
per-example gradients across multiple augmentations of the same image before the clipping operation
(Hoffer et al., 2019) ...' This needs further explanations.

Minor weaknesses:
The writing can be improved. There are many cases that one notation is used before it is introduced. For example,
1. The first paragraph of Page 7 refers to Algorithm 3 which has $s_i$ but it is introduced in Section 5.1. 
2. The 'AGGREGATION' method set on Page 7 needs further explanation on how to transform $\\{G_i^t\\}_{i\in\mathbb{C}^t}$ to $G^t$. 
3. On Page 7, the authors said 'line 5 in Algorithm 4 uses Gaussian mechanism' twice, but this is not shown in the algorithm.

On page 16, there is a missing remark. Similar in Remark F.1.

On page 18, Equation (29) is based on Remark C.1 but I do not see how. By the way, I guess $\mathrm{dist}(B^*, B^t)\leq 1$ is from a property of $\mathrm{dist}$, but please make it clear somewhere.

The proof for Lemma D.4 and Lemma F.1 is missing.



Some typos:
1. Page 5, Algorithm 1, Line 4, I guess $p_c$ should be $p_g$.
2. Page 6, Remark 4.1, $S_\alpha(p_c, \sigma_g)=\ldots$ needs to be corrected.
3. Page 10, references, there are duplicates for 'Durmus Alp Emre Acar, et al. (2020, 2021)'.
4. Appendix A.4, the sensitivity is $2\zeta_g/n$.
5. Appendix C, the equation above (MSP) should be $E_{x_{ij}}[\langle \frac{1}{\sqrt{N}}A(X),\frac{1}{\sqrt{N}}A(X) \rangle ]$. Similar problem in Page 23 last equation.
6. Appendix Page 18, the first equation, the second line, the last part $\eta_g\sigma_g \zeta_g W^t$ should be $\eta_g\sigma_g \zeta_g W^t/n$
7. Appendix Eq (42), I guess $F_t$ is $F^t$.
8. On page 24, the first line in Section E.2, I think $I_k$ is $I_d$.
9. On page 26, the second last line, Hardt & Price (2014) does not have Algorithm 6.

----------------------------
Update: The major weaknesses listed above are all solved by the authors. However, I have new concerns (listed below) about this paper, which made me change my score to 5 since those concerns are not easily addressable in the camera-ready version of this paper if it is accepted.
1. The writing of this paper is a bit misleading since the proposed framework, CENTAUR, is very similar to existing methods where the only difference is in the implementation of the special setting, Linear Representation Learning. Therefore, the introduction of this paper needs rewriting. 
2. The question raised by reviewer CCKF about the comparison to DP-FedAvg-fb is unanswered. The authors have compared their method to DP-FedAvg-*ft*, which uses local fine-tuning of the full model. However, the *fb* variant fine-tunes the last layer only, which follows almost the same idea as the newly proposed method in this paper, therefore it is more valuable to compare with the *fb* variant.
3. Although the empirical experiment shows good results in the given settings with $\varepsilon\in \{0.25, 0.5, 1, 2, 4\}$ for DP, there could be more settings (e.g., more choices of $\varepsilon$) for a more detailed comparison between CENTAUR and other methods. The current results may be surprising to the experts in federated learning since other FL methods are mostly worse than the non-FL baseline even when $\varepsilon=4$. Adding experiments with $\varepsilon > 4$ or even $\varepsilon \rightarrow \infty$, which deactivates the effect from DP, may help address this issue.

---
Update-2: The new responses from the authors include the code (which solves the name issue about 'DP-FedAvg-fb' and makes the results reproducible) and some experimental support for Remark 3.1. 

I would change my recommendation score to 6 since this paper points out a reasonable and promising direction of federated learning with differential privacy with theoretical and experimental evidence. I choose not to give an 8 because the theoretical analysis only covers the noiseless setting, which is much narrower than Jain et al. (2021), and the major theoretical contribution, 'the cross-validation based initialization scheme', is not used in the deep learning experiments.

clarity,_quality,_novelty_and_reproducibility: The paper is easy to read and the overall quality is good. It is not super novel in terms of the main algorithm (Figure 2 by Collins et al. (2021) looks almost the same as the Figure 2 in this paper), but the authors' insight is clear, and the analysis of utility and privacy guarantee is kind of solid. I believe the results are reproducible but the code is not provided so I cannot try it by myself.
summary_of_the_review: The authors propose to use a sharing-representation-only method to solve the FL+DP problem in deep learning, and they provide theoretical guarantees along with good empirical results. I would raise my recommendation score if the problems above are corrected and explained. 

\-----

After reading other reviewers' comments, I agree that this paper is misleading regarding its contributions. On Page 2, the authors said, 'In our scheme, we train a single differentially private global representation extractor while allowing each participant to have a different personalized classifier head.' However, such a scheme is already described in the existing literature, not a novel one. Remark 3.1 could be novel but needs further theoretical and experimental verification.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper considers the (federated) private model personalization problem, and provides a utility guarantee in the bilinear case.
The technical contribution is to prove a utility bound when using DPSGD to learn the shared representation, which improves upon the best known bound (that uses sufficient statistics perturbation instead) by a factor of $\sqrt d$.
strength_and_weaknesses: ## Strengths
- The presentation is crisp.
- The $O(\sqrt d)$ improvement upon the method of Jain et al. is interesting (though the comparison may not be fair).
- The empirical results are promising.

## Weaknesses

My main concern is that the vast majority of ideas, which are presented as novel, are not new at all, they have been studied both in the federated learning literature and under differential privacy.

The idea of learning shared representations differentially privately while learning a personalized model for each user/client is exactly the setting of private model personalization (Jain et al. and others). In fact, they describe a general alternating minimization algorithm (their Algorithm 1), and explicitly mention DP-SGD as one possible way of solving the server-side problem, which is what Algorithm 1-2 in this paper does. Granted, their analysis is carried only for sufficient statistics perturbation and not gradient descent, so the utility bound in Theorem 5.1 is new in this setting. But the framework and ideas presented in the paper are well-established, for example arguments made in Sections 1-3 are well known.

The contribution of the paper is much more narrow than what the paper claims:
1) Proving a utility bound (which includes a \sqrt d improvement upon the SOTA) in the linear case, *in the low-privacy regime* (more discussion would help here, to understand how restrictive this condition is, for example some estimate of how large epsilon has to be in realistic scenarios).
2) Good empirical results on CIFAR and EMNIST.

I believe the presentation is misleading, and should be significantly updated to reflect the real contributions. All discussion up to and including Section 3 should be presented as a review of existing ideas.

On the technical side: the statement of results lacks rigor at times.
- The privacy guarantee should be stated more carefully. The rigorous guarantee should use the joint-(R)DP notion.
- Corollary 5.1 should be clearly stated -- how should one interpret statements such as "we have the following trade-off"? It is unclear, as stated, what conditions should hold, what parameters are fixed, what parameters need to be known for running the algorithm, etc.
- As pointed out by other reviewers, the assumptions for the main result are not the same as Jain et al., this must be further discussed.

#### Experiments:
The experimental results are promising. I have a few questions/suggestions:
- Did the authors compare to DP-FedAvg-fb of Yu et al.? (i.e. fine-tuning the last layer instead of the entire model)? This appears closer to the setting under consideration.
- It is always worrisome to see that all competing methods are worse than even the non-FL baseline. Does one really expect all these other methods to fail in practice? Surely there is a regime in which isolated training would fail (say in the extreme case of one example per client). Can the authors give a more nuanced discussion?


==== Post-discussion update ====
The authors acknowledged that the idea of learning shared DP representation while learning a personalized classifier per client, is not new, and promised to rephrase their contributions to reflect this, and to better place the work in the context of existing work.
Other improvements have been made, including discussions about the technical assumptions, and empirical support for the claims made in remark 3.1.
clarity,_quality,_novelty_and_reproducibility: Summary (see previous section for details):
- Clarity: well-written, but misleading presentation.
- Quality: some minor technical issues. Expanding the discussion of utility bound and/or empirical results can help.
- Novelty: limited.
summary_of_the_review: Ideas are not new. The improvement of utility bound is interesting (but the low privacy condition needs to be a clear caveat) and the empirical results are promising (but need a perhaps more nuanced discussion).
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This work proposes studies federated learning under differential privacy with heterogeneous users, where the goal is to learn simultaneously learn good global and local models. The authors propose to only share weights of the representation networks and locally train the user-specific heads for personalization. Theoretical analysis is provided for linear networks, and experiment results verify the effectiveness of the approach.
strength_and_weaknesses: Strengths:
- The idea of separately training representation and classification heads is intuitively nice. 
- The experiment results look promising. The proposed algorithm outperforms the DP-FedAvg and existing personalized FL baselines, and is the only method that outperforms local training.
- Theoretical results demonstrate significant improvement for linear networks.


Weakness:
- The experiment results would be more convincing if more experiments on done on larger datasets like ImageNet.
- This is just a curious question: how would the size of the classification head and representation network affect the performance, and what is a good way to select these parameters in practice? Would it depend on the training task, e.g. for simple classification it suffices to use a small head, but for more complicated tasks larger head is needed?


=== Update ===

After reading other reviewers' comments, it seems that there is a mismatch between the error metric used in this work (matrix L2 norm) and Jain et.al (Frobenius norm). Therefore, the theoretical improvement is unclear. I'm adjusting my score to 6 accordingly.

=== Update ===
The authors have addressed my concern about the mismatch in the error metric. I also believe the authors have adequately addressed most concerns of other reviewers. Thus I will change back to my original score of 8. 
clarity,_quality,_novelty_and_reproducibility: The ideas and results are clearly presented.

The algorithmic ideas and experiment results are promising and exceed previous works.

It seems that the code is not provided via link nor in the supplementary materials. 
summary_of_the_review: This work proposes a framework for DP federated learning that separately trains the representation network and local heads. The performance surpasses previous works. The theoretical results for linear networks intuitively prove the effectiveness of the idea. I only have some minor issues stated in the weakness part.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studies privacy-preserving federated learning (FL) with a trusted central server. The authors give a new differentially private (DP) FL algorithm under model personalization assumptions. Their algorithm follows a general paradigm, where a shared representation is globally learned under DP guarantee, then each client locally train a personalized model using their own data and the learned shared representation.

The authors analyze their algorithm for the specific problem of linear representation learning (LRL) and prove formal privacy and accuracy guarantees. They show $O(\sqrt{d})$ improvement in the accuracy guarantee over the prior work by [Jain et al. 2021]. This is a substantial quantitative improvement for the LRL problem. The authors complement their formal results with empirical evaluation that further supports their findings. 

The authors have also made several improvements to their paper during the discussion phase including clarifying their contributions, discussing their technical assumptions, and elaborating on some of the important claims in the paper. 

The general consensus is that the paper makes progress on an important problem. The authors formally prove a quantitative improvement over prior work and support their results with empirical evaluation. 

justification_for_why_not_higher_score: The contributions are above the bar of acceptance but the level of impact is not high enough to merit an oral or spotlight presentation. 
justification_for_why_not_lower_score: The paper is above the bar for acceptance. It makes progress on an important problem and formally shows a clear, quantitative improvement over prior work.
Decision: Accept: poster