Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: In this paper, the authors formalize a notion of task-level differential privacy using joint differential privacy, a concept known in the differentially private mechanism design literature. They formulate the problem of multitask learning under differential privacy under this relaxed definition. The motivation is that there is no need for privacy of the data of a particular task from the task itself, but since you are sharing information in multitask learning, you want to protect against other tasks learning about your private information. They provide an algorithm with convergence guarantees to do multitask learning in this framework and perform some experiments to test this algorithm in the application of federated learning
main_review: Strengths:
This paper proposes a new idea of using a relaxation of differential privacy in the multitask learning framework.
It motivates work in the direction of looking at application specific relaxations of differential privacy, to give more realistic algorithms which perform better than the ones which satisfy the strong differential privacy constraint.

Weaknesses/Questions:

	
1. Is $x_i$ the data? Is $l_k(w_k)$ in eq. (7) the population loss or the empirical loss?

2. Some more results like comparison of rates to algorithms that are not only joint differentially private, but differentially private would be useful. Are the improvements only in constant factors or are the improvements in terms of dimension dependent or number of samples dependent terms?

3. Can the authors give some sense of what are the best rates you can under joint differential privacy and how does that compare with the given algorithm?

4. Is there any motivation as to why the number of local optimization steps was chosen to be 1? In more realistic scenarios, each task would take multiple descent steps to personalize better, right?

5. Can you show a short calculation to ensure the constant multiplying the exponentially decaying term is always positive?

6. The last two terms in equation (13) seem fishy, does it mean the error doesn’t decay by increasing the number of iterations?

7. The values of epsilon in figure 2, seem very high for the loss to decay enough.

8. It’s not surprising that private MTL does better than the private global models, by the sheer number of parameters that private MTL allows (it’s ~m times the private global model parameters). A more fair comparison would be to compare against an algorithm that is globally differentially private instead of joint differentially private.

summary_of_the_review: The idea to use joint differential privacy instead of differential privacy in MTL is interesting. The privacy analysis and the convergence rates presented are fairly standard. The theory doesn’t seem to stand on it’s own and more experiments can be done to rigorously test the introduction of this idea. Hence, I believe in it’s current form the paper is not ready for publication.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Many problems in machine learning rely on multi-task learning (MTL), in which the goal is to solve multiple related machine learning tasks simultaneously. In this work, authors formalize notions of task-level privacy for MTL via joint differential privacy (JDP). They propose an algorithm for mean-regularized MTL, an objective commonly used for applications in personalized federated learning, subject to JDP. Then analyze objective and solver, providing certifiable guarantees on both privacy and utility. The method allows for improved privacy/utility trade-offs relative to global baselines across common federated learning benchmarks. 
main_review: They give a task-level private algorithm for multi-task learning, which is very important in machine learning, and show the theoretical convergence analysis. The structure is clear and writing is good. The experiment results can also support their theory.
Typo. Section 5.3 “common” rather than “commons”

summary_of_the_review: The work is complement, although only one algorithm for one problem, the analysis and experiments are sufficient.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper considers the problem of multi-task learning  (MTL) with task-level differential privacy (TLDP) constraints. The authors propose using joint differential privacy (JDP) for MTL and provide a JDP MTL algorithm, which is a DP variation of FedAvg. They prove the privacy of their algorithm and provide convergence results for smooth nonconvex and strongly convex losses. They then provide numerical experiments. 
main_review: Overall, I find Sections 1-3 to be strong: the paper is well-written and the problem is well-formulated and nicely described. My main problem is with the convergence results, which are difficult to interpret due to too many parameters and no informal bound is provided. Additionally, it is not clear that the bounds are even non-trivial (see below for more discussion). My other main point of confusion is that the authors say they consider JDP as a relaxation of TLDP to provide better utility, but then their algorithm actually appears to provide the stronger (by Billboard Lemma) notion of TLDP (due to Theorem 1); so what is the role of JDP in their results? 

Detailed Review: 
p.1: 

is task-level DP essentially the same as user-level DP/client-level DP (which is considered in McMahan et al 2018)? If so, state that--these terms are more familiar to the DP community than task-level DP. 

emphasize "as long as client k keeps their data private" 

p.3 

Motivate Eq (1). Goal is to train a model that has small average loss over all tasks, right? So why use a regularizer? 

Define $\ell_k$ and $x_i$ 

Missing parentheses in Eq (2)

p. 4

clarify that strong guarantee of JDP hinges on each client keeping its own model private 

I believe Kearns et al 2014 is wrong citation for Lemma 1. Shouldn't it be Hsu et al? 

Lemma 1: $D_k$ ->  $D_i$

p.6

Theorem 1: missing restriction on $\epsilon$. Proof of Abadi et al (2016) Theorem 1 shows that some restriction (roughly $\epsilon \leq \ln(1/\delta)$) is needed; also, you should refer to what you provide as TLDP or user-level/client-level DP (in Theorem 1 and in Definition 1)--DP is too vague, as there are many notions of DP 

**Why study JDP if your algorithm satisfies the stronger notion of TLDP?**

p.7

If you assume $\gamma \geq \| \nabla f_k(w) \|$ (i.e. loss is effectively Lipschitz), then it seems you do not need to clip the gradients (and clipping will never actually occur in the algorithm)--am I right? 

Why assume loss is $L + \lambda$-smooth and not $L$ smooth? 

Should replace min by inf unless you are assuming compactness of domain; are you? I don't the domain was formally defined. I don't remember seeing $d$ defined either. 

**Convergence bounds: if $f_k \leq 1$ so $B_t = 1$, then the second term in Eq (11) becomes essentially trivial $O(L + \lambda + ...)$** And that is the non-private case, so the DP bounds can only get "worse". 

Also, **the bounds in (8)-(10) and (12) are too complicated: should provide simplified version with dependence on key parameters m, d, epsilon, delta displayed**; and even the formal version should not be simplified to include only the key parameters as well as the smoothness and boundedness parameters, and non-dominant terms should be omitted. 


 
summary_of_the_review: The paper considers/formulates an interesting problem and is generally well-written. Unfortunately, the convergence results do not appear to be strong (or clear). Additionally, there is confusion about the notion of privacy that their algorithm provides and the role that JDP is playing in the paper. For these reasons I cannot recommend acceptance for the current form of the paper.
review_title: null

Meta-review: Many problems in machine learning rely on multi-task learning (MTL), in which the goal is to solve multiple related machine learning tasks simultaneously. In this work, authors formalize notions of task-level privacy for MTL via joint differential privacy (JDP). They propose an algorithm for mean-regularized MTL, an objective commonly used for applications in personalized federated learning, subject to JDP. Then analyze objective and solver, providing certifiable guarantees on both privacy and utility. The main results, namely the convergence rate results, are hard to parse and hard to interpret. For example, as one reviewer pointed out, it is bounded below by a constant which is not properly explained. Further, comparisons to the literature in user-level privacy (which is equivalent as the task-level privacy) is not provided enough. Significant improvement in the presentation of the main results, along with an interpretable explanation of the contribution, is necessary for this manuscript.
Decision: Reject