Share Your Representation Only: Guaranteed Improvement of the Privacy-Utility Tradeoff in Federated Learning
Authors: Zebang Shen
Jiayuan Ye
Anmin Kang
Hamed Hassani
Reza Shokri
Venue: ICLR 2023 poster (2023)
Keywords: Differential Privacy
Representation Learning
Federated Learning

Abstract: Repeated parameter sharing in federated learning causes significant information leakage about private data, thus defeating its main purpose: data privacy.  Mitigating the risk of this information leakage, using state of the art differentially private algorithms, also does not come for free.  Randomized mechanisms can prevent convergence of models on learning even the useful representation functions, especially if there is more disagreement between local models on the classification functions (due to data heterogeneity). In this paper, we consider a representation federated learning objective that encourages various parties to collaboratively refine the consensus part of the model, with differential privacy guarantees, while separately allowing sufficient freedom for local personalization (without releasing it).  We prove that in the linear representation setting, while the objective is non-convex, our proposed new algorithm \DPFEDREP\ converges to a ball centered around the \emph{global optimal} solution at a linear rate, and the radius of the ball is proportional to the reciprocal of the privacy budget.  With this novel utility analysis, we improve the SOTA utility-privacy trade-off for this problem by a factor of $\sqrt{d}$, where $d$ is the input dimension.  We empirically evaluate our method with the image classification task on CIFAR10, CIFAR100, and EMNIST, and observe a significant performance improvement over the prior work under the same small privacy budget. The code can be found in this link, https://github.com/shenzebang/CENTAUR-Privacy-Federated-Representation-Learning.

Published as a conference paper at ICLR 2023
SHARE YOUR REPRESENTATION ONLY: GUARANTEED IMPROVEMENT OF THE PRIVACY-UTILITY TRADEOFF IN FEDERATED LEARNING
Zebang Shen
Jiayuan Ye, Anmin Kang
ETH Zürich zebang Scen@innf... ethe. ch
National University of Singapore
{jiayuanye, anmin. kang) @u nus , edu
Hamed Hassani
Reza Shokri
University of Pennsylvania
National University of Singapore re reza@ comp, nus edu. sg
hassani @seas. upenn. edu
ABSTRACT
Repeated parameter sharing in federated learning causes significant information leakage about private data, thus defeating its main purpose: data privacy. Mitigat- ing the risk of this information leakage, using state of the art differentially private algorithms,, also does not come for free. Randomized mechanisms can prevent convergence of models on learning even the useful representation functions, es- pecially if there is more disagreement between local models on the classification functions (due to data heterogeneity). In this paper, we consider a representation federated learning objective that encourages various parties to collaboratively re- fine the consensus part of the model, with differential privacy guarantees, while separately allowing sufficient freedom for local personalization (without releas- ing it). We prove that in the linear representation setting, while the objective is non-convex, our proposed new algorithm CENTAUR converges to ball centered around the global optimal solution at a linear rate, and the radius of the ball is proportional to the reciprocal of the privacy budget. With this novel utility anal- ysis, we improve the SOTA utility-privace trade-off for this problem by factor of dd, where d is the input dimension. We empirically evaluate our method with the image classification task on CIFAR10, CIFAR and EMNIST, and observe a significant performance improvement over the prior work under the same small privacy budget. The code can be found in this link
INTRODUCTION
In federated learning (FL), multiple parties cooperate to learn a model under the orchestration of central server while keeping the data local. However, this paradigm alone is insufficient provide rigorous privacy guarantees, even when local parties only share partial information (e.g. gradients) about their data. An adversary (e.g. one of the parties) can infer whether particular record is in the training data set of other parties (Nasr et al. 2019). even precisely reconstruct their training data (Zhu et al., 2019). To formally mitigate these privacy risks, we need to guarantee that any information shared between the parties during the training phase has bounded information leakage about the local data. This can be achieved using FL under differential privacy (DP) guarantees.
FL and DP are relatively well-studied separately. However, their challenges multiply when conduct- ing FL under a DP constraint, in real-world settings where the data distributions can vary substan- tially across the clients (Li al. 2020b Acar al. 2020 Shen al. (022). A direct consequence of such data heterogeneity is that the optimal local models might vary significantly across clients and differ drastically from the global solution. This results in large local gradients (Tiang al.) 2019). However, these large signals leak information about the local training data, and cannot be "The work done when Zebang Shen was post-doctoral researcher University of Pennsylvania.

---

Published as a conference paper at ICLR 2023
communicated such when we need to guarantee DP. We require clipping gradient values (usually by a small threshold (De et al. 2022)) before sending them to the server, to bound the sensitivity of the gradient function with respect to changes in training data AAbai et al. (2016). As the local per- sample gradients (due to data heterogeneity) tend to be large even at the global optimum, clipping per-example gradient by small threshold and then randomizing it, will result in a high error in the overall gradient computation, and thus degrading the accuracy of the model learned via FL.
Contributions. In this work, we identify an important bottleneck for achieving high utility in FL under tight privacy budget: There exists a magnified conflct between learning the representation function and classification head, when we clip gradients to bound their sensitivity (which is required for achieving DP). This conflict causes slow convergence of the representation function and dispro- portional scaling of the local gradients, and consequently leads to the inevitable utility drop in DP FL. To address this issue, we observe that in many FI. classification scenarios, participants have minimal disagreement on data representations (Bengio et al.) [013] Chen et al. [020) Collins al.) 2021). but possibly have very different classifier heads (e.g., the last layer of the neural network). Therefore, instead of solving the standard classification problem, we borrow ideas from the literature of model personalization and view the neural network model composition of representation extractor and a small classifier head, and optimize these two components in different manners. In the train single differentially private global representation extractor
proposed scheme, CENTAUR, while allowing each participant to have a different personalized classifier head. Such a decompo- sition has been considered in previous arts like (Collins al. 202I) and (Singhal et al., 202I). but only in a non-DP setting, and also in (Jain et al., 2021). but only for a linear embedding case.
Due to low heterogeneity in data representation (compared to the whole model), the DP learned representation in our new scheme outperforms prior schemes that perform DP op-
timization over the entire model. In the setting where both the representation function and the classifier heads are lin-
Tooing acauacy %
50
ear w.r.t. their parameters, we prove a novel urility-privacy trade-off for an instance of CENTAUR, yielding a significant O(vā) improvement over previous art, where d is the in- put dimension (Corollary 5.1 ) A major algorithmic novelty of our proposed approach is a cross-validation scheme for boosting the success probability of the classic noisy power spectral analysis.
CENTAUR
Stand-a -o-
PEEGD
PMTL-It Ft
40-
DP De-kegkg--fb
0.25
0.5
<in (1.6 - 10 "idifferemial privacy bound
method for privacy-preservie
Figure Privacy utility trade-off for models trained under CENTAUR and other algorithms on CIFAR10 (500 clients, 5 shards per user). Error bar de- notes the std. across 3 runs.
We present strong empirical evidence for the superior per- formance of CENTAUR over the prior work, under the small DP budget of 50-1 in variety of data-heterogeneity settings on benchmark datasets CIFAR10. CIFAR 100, and EMNIST. Our method outperforms the prior work in all set- tings. Moreover, we showcase that CENTAUR uniformly enjoys better utility-privacy trade-off over its competitors on the CIFARIO dataset across different privacy budget (Figure [T.. Importantly, CENTAUR outperforms the local stand-alone training even with, 0.5, thus justifying the benefit of collaborative learning compared to stand-alona training for a larger range of privacy budget.
1.1 RELATED WORK
Federated learning with differential privacy has been extensively studied since its emergence (Shkrri & Shmatikov 2015 McMahan et al. 2017a).. Without any trusted central party, the local DP model requires each client randomize its messages before sending them to other (malicious) parties. Consequently, the trade-off' between local DP and accuracy is significantly worse than that for cen- tralized setting and requires huge amount of data for learning even simple statistics (Duchi et al., 2014 Erlingsson et al. 2014; Ding et al., (007).. By using secure aggregation protocol. recent works (McMahan et al. 2017b; Agarwal et 2018 [evy et al. 2021 Kairouz et al. 2021 study user- DP under Billboard model to enable utility. We also focus on such lserl DP setting.
Model personalization approaches (Smith et al. 2017 Fallah et al. 2020 Li et al. 2020b: Arivazha-
gan et al. 2019: Collins et al. |021 Pillutla et al. 2022) enable each client to learn different (while related) model, thus alleviating the model drifting issue due to data heterogeneity. Recent works further investigate whether model personalization approaches enable improved privacy accu- racy trade-off for federated learning. Hu et al. (202I) propose private federated multi-task learning algorithm by adding task-specific regularization to each client's optimization objective. However,
2

---

Published as a conference paper at ICLR 2023
the regularization has limited ability to deal with data heterogeneity. Bietti et al. (2022) propose the PPSGD algorithm that enables training additive personalized models with user- DP. However, their generalization guarantees crucially rely on the convexity of loss functions. On the contrary, study the convergence of CENTAUR algorithm under more general non-convex objectíves.
The closest work to our approach in the literature is Jain al. (202T), who also propose differen- tially privately learning shared low-dimensional linear representation with individualized classifica- tion head. However, their algorithm relies on solving the least square problem exactly at server side, by performing SVD on perturbed noisy representation matrix. Hence, the generalization guarantee of their algorithm intrinsically has an expensive d dependency on the data dimension d. By con- trast, we perform noisy gradient descent at server side and improve upon this error dependency by a factor of vd. Their algorithm is also limited to the linear representation learning problem, unlike our CENTAUR algorithm which enables training multiple layers of shared representations. Our work builds the FedRep algorithm (Collins et al. 2021), which also relies on learning shared representations between clients but does not consider privacy, In contrast, our work provides a novel private and federated representation learning framework. Moreover, a major different ingredient of our algorithm is the initialization procedure, which requires performing differentially private SVD to the data matrix. We the noisy power method (Hardt & Pricel (014) crucial tool to enable constant probability for utility guarantee. We then perform cross- vross-validation to further boost success probability arbitrarily large (inspired by Liang al. (2014).
2 NOTATIONS AND BACKGROUND ON PRIVACY
Notations. We denote the clipping operation by clip(æ; () = x mi.(11//||=11] and denote the Gaussian mechanism as GMç (f=,) k-1) 1 ! clip(z;: + o<W) where N(O, I).
Define Rényi Differential Privacy (RDP) on a dataset space D equipped with distance d as follows.
Definition 2.1 (RDP). For measures v, v' over the same space with v & v', their Rényi divergence Ru, v') = -- log (v, v'), where Ea(,, = 5 (dv ) dv', A randomized algorithm M D + O satisfies (ox,))-RDP, if DD' E D with d(D, < 1, we have (o(M(TD).
1
S
User-level-RDP. Let D be the space of all of tuples of local datasets {S where each local dataset consists of m data points, i.e. D { | S, (zig mm The distance d is the Hamming distance in the dataset level, i.e. d ( (8 = Σn_ 18, We refer to the privacy guarantce recovered by this choice of dataset space user-levei-RDr
In Appendix AA.3] we further describe the Gaussian Mechanism and the composition of RDP, the standard notion of Differential Privacy (DP), and the conversion Lemma from RDP to DP.
We aim to protect the privacy of each user against potential adversarial other clients, i.e., any cavesdropper will not be able tell whether one users has participated in the collaborative learning procedure, given the information released during training phase. We establish user-level RDP guarantees under the billboard model, which is communication protocol that particularly compatible with algorithms in the federated setting and has been adopted in many previous works (Jain al.) 202T, Hu al. 202T Bietti et al., 2022). In this model, trusted server (either a trusted party or one that uses cryptographic techniques like multiparty computation) aggregates information subject to DP constraint, which is then shared as public messages with all the n users. Then, each user computes its own personalized model based on the public messages and its private data (Hsu et al. 2014), Our RDP guarantces only hold for releasing the shared representations br, in Al- gorithm and the guarantees are equivalent to (R)Dt guarantees Kearns et al. (2014) if all the personalized models w?Ti of individual users were additionally released as outputs of Algorithm
Threat Models.
PROBLEM FORMULATION
Consider a Federated Learning (FL. setting where there are n agents interacting with a central server mh and the ith agent holds m. local data points S. {( ) Here (æij JRy)) Rd x IR denotes pair of an input vector and the corresponding label. Suppose that each local dataset S; is sampled from an underlying joint distribution ( y) of the input and response pair. We consider the data- heterogenous setting where potentially p: # Pj for i + j. We further consider a hypothesis model
3

---

Published as a conference paper at ICLR 2023
0(:0) R + R which maps an input æ the predicted label y. Here 0 R' is the trainable parameter of the model f. Let & R x IR - I be a loss function that penalizes the error of the prediction f(x; 0) given the true label y. The local objective on client i is defined as
m, e(s(a,;; 0).
1(0; 8.)=
Σ
mi
/=1
The standard FL formulation seeks a global consensus solution, whose objective is defined as
arg min ((0)=
n Σ (()
(2)
While this formulation is reasonable when the local data distributions are similar, the obtained global solution may be far from the local optima arg min 1( S,) under diverse local data distributions, a
phenomenon known as statistical heterogeneity in the FL literature (Li al.) 2020a Wang et al.
2019 Malinovskiy et al. 2020 Mitra et al., 2021 Charles & Konečný [202] Acar et al. 2020
Karimireddy et al.) 2020). Such (potentially sigmificant) mismatch between local and global opti- mal solutions limits the incentive for collaboration. and cause extra difficulties when DP constraints are imposed (Remark 3.T. These considerations motivate us to search for personalized solutions that can be learned in federated fashion, with less utility loss due to the DP constraint.
Federated representation learning with differential privacy. It is now well-documented that in some common and real-world FL tasks, such as image classification and word prediction, clients have minimal disagreement on data representations (Chen et al. 2020] Collins et al. 2021). Based on this observation, a more reasonable alternative to the FL objective equation 2 should focus on learning the data representation, which is the information that is agreed on among most parties, while also allowing each client to personalize its learning on information that the other clients disagree on. To formalize this, suppose that the variable 0 E R2 can be partitioned into pair [w, bj E R x R with y = 41 +2 and the parameterized model admits the composition ʃ f= hoo where & Rd - R is the representation extractor that maps d-dimensional data points to lower dimensional space of size k and h: H + IR is a classifier head that maps from the lower dimensional subspace to the space of labels. An important example is bottom and top layers of the neural network model. We use w and to denote the parameters that determine h and Φ, respectively. With the above notation, we consider the following federated representation learning (FRL) problem
Σ min I((us, B):S.) == Σ E(h(blaryy b): w:)) wis)
min DEB
(3)
where we maintain single global representation extraction function o(- b) subject to the constraint b E IB C R while allowing each client to use its personalized classification head h(-; w;) locally. The constraint B is included so that equation also covers the linear case studied in section
The choice of the FRL formulation in equation 3 entails considerations from both DP and optimiza- tion perspectives: From the DP standpoint, the phenomenon of statistical heterogeneity introduces additional difficulties for federated learning under DP constraint (see Remark 3.1 below). If the clients collaborate to train only a shared representation function, then the aforementioned disad- vantages can be alleviated; From the optimization standpoint, we typically have h < d, i.e. the dimension of the extracted features is much smaller than that of the original input. Hence, for a fixed representation function o(: b), the client specific heads h(: w.) are in general easy to opti- mize locally as the number of parameters, kt is typically small.
Remark 3.1 (Statistical heterogeneity makes DP guarantee harder establish.). To establish DP guarantees for gradient based methods, e.g. DP-SGD, a common choice is the Gaussian mechanism, which comprised of the gradient clipping step and the noise injection step. It empirically observed that to achieve better privacy-utility trade-off. a small clipping threshold is preferred, since it limits the large variance due to the injected noise (De et al. (0022.. Moreover, the effect of the bias (due to clipping) subsides the per-sample gradient norm diminishes during the centralized training, a phenomenon known as benign overfitting in deep learning (Bartlett et al. 2020 Li et al. 2021 Bartlett et al.) 2021). However, due to the phenomenon of distribution shift, the local (per- sample) gradients in the standard FL setting (described in equation 2 remain large even at the global optimal solution, and hence setting small (per-sample) gradient clipping threshold will
4

---

Published as a conference paper at ICLR 2023
Algorithm SERVER procedure of CENTAUR
procedure SERVER(b". Pg. Tg. 7gs gg. So)
2:
// DO is obtained from the INITIALIZATION procedure.
3: for & + 0 to T. do
4:
Sample set (C of active clients using Poisson sampling with parameter Pa- Broadcast the current global representation parameter b' to active clients. Receive the local update directions {gî Jec from the CLIENT procedures. Compute the update direction gà = GMc, ((g/he)))
5:
6:
7:
8:
Update the global representation function b AGGREGATION( g'. mga)
9:
The AGGREGATION procedure depends on the feasible set equation
10:
return bea.
Algorithm CLIENT procedure of CENTAUR in the general case (for client i)
1: procedure CLIENT(b', m. Ti, m))
2: [Phase Local classifier update.] w w = arg min 1(bb,, w.)
3: [Phase 2: Local representation function update.] Set b = bb:
4: for f 0 Ti do
5: Sample a subset S of size mn from the local dataset S, without replacement
6: Update the local representation function 6.:*+1 Di mp ((b , w
):)).
7: [Phase Summarize the local update direction.] return g == b ba.
result in large and non- non-diminishing bias in the overall gradient computation. In contrast, for tasks where the representation extracting functions are approximately homogeneous, the local and global optimal of the FRI. formulattnonn 3 are close and hence the gradients w.r.. the representation function vanishes at the optimal, which is amiable to small clipping threshold.
4 DIFFERENTIAL PRIVATE FEDERATED REPRESENTATION LEARNING
In this section we present the proposed CENTAUR method solve the FRL problem in equation
SERVER procedure (Algorithm 1 takes the following quantities as inputs: 50 denotes the initializer for the pa- rameter of the global representation function, obtained from a procedure INITIALIZATION; Pd denotes the portion of the clients that will participate in training per global com- munication round; T, denotes the total number of global communication rounds; 77 denotes the global update step size; (ag: Sg) stand for the noise multiplier and the clipping threshold of the Gaussian mechanism (that ensures user- level RDP). Note that this section, we consider random INTTIALIZATION over unconstrained space | 1R and the procedure AGGREG ATION (b', g m1y) = b' + +g -g.. Under these configurations, SERVER follows the standard FL pro- tocol: After broadcasting the current global representation function the activate clients, aggregates the information
server
b+
GMipa
(1eihicc))
g dal
Dnffa
b
h++
w
shared b'
shared b'
clicnt
client
Figure 2: The t-th global round the CENTAUR algorithm, where clients keep their classification head wn secret while updating shared representation b' b based perturbed gradients gi from sampled clients E Cr. returned from the CLIENT procedure to update the global representation function.
CLIENT procedure (Algorithm 2 takes the following quantities as inputs: b' denotes the pa- rameter of the global representation function received from the server; m denotes the number of local data points used as mini-batch to update the local representation function; Ti denotes the number of local update iterations; Y denotes the local update step size. CLIENT can be divided the representation function
into three phases: 1. After receiving the current global parameter from the server, the client update the local classifier head to the minimizer of the local objective w arg min,, [(b', w|: S,). This is possible since the local objective / usually admits very simple structure, e.g. it is
w.r.t. w, once the representation function is fixed. In prac-

---

Published as a conference paper at ICLR 2023
tice, we would run multiple SGD epochs to approximately minimize I with b' fixed. This is computationally cheap since the dimension of w is much smaller compared to the whole variable o [w, b). 2. Once the local classifier head is updated to w the client optimizes its local representation function with multiple SGD steps, starting from the current global consensus b'. 3. Finally, each client calculate its local update direction for representation via the difference between its latest local representation function and the previous global consensus, b::7! b'.
Remark 4.1 (Privacy guarantee). By the composition theorem for subsampled Gaussian Mecha- nism Mironov et al. (2019), we prove that Algorithm 7 and Algorithm satisfies user-level (a, c)- Rényi differential privacy T.. (p (g), where S. (pg 0g) Ro (O, (0) + (LL, og)) In the special case full gradient descent with Ps 1, we have that Tg/ (20g)
GUARANTEED IMPROVEMENT OF THE UTILITY- PRIVVAY TRADE-OFF
In the previous section, we present CENTAUR for the general FRL problems B}. Due to the lack of structure information, for a general non-convex optimization problem we cannot expect any utility guarantee beyond the convergence instance of the FRL problems where both the representation function & and the local classifiers h are linear w.r.t. their parameters and wt. This model has been commonly used in the analysis of representation learning (Collins et al. 2021 2022), meta learning (Tripuraneni et al. [021] Du jet al. 2020 [hckumparampil et al.J 2021 Sun et al. 202I), model personalization (Jain et al. 202 multi-task learning (Maurer et al. 2016). For this (still nonconvex) instance, prove that
a stationary point. In this section, we consider a specific
CENTAUR converges to a ball centered around the global minimizer in a linear rate where the size of the ball depends on the required RDP parameters (a:, c). Let ca be the utility and let Cdp be the DP- parameter (CENTAUR is an (Cáp. 5)-DP mechanism). We obtain the improved privacy-utility tradeoff
6a Fdd 2 Od/nn, which is O(vd) better than the current SOTA result, <a Edp 2 O(d'.5/n) by (Jain et al.) 202T). >. In the following, we will first review objective (3) the linear representation setting, and analyse CENTAUR to show the improved utility-privann tradeoff.
Federated Linear Representation Learning (LRL) Recall the problem formulation in Section 3
For simplicity, we assume my for all i E {1, {1,...,m) ,n) for some constant Consider the
LRL setting, where given the input Øij the response Yi R satisfies Vij ", B mij- Here B" E Rd is column orthonormal global representation matrix and w,," RR is agent-specific optimal local linear classifiers. In terms of the notations, B corresponds to the parameter b in the general formulation 3 but is capitalized since it is now regarded as matrix. The feasible domain B is the set of column orthonormal matrices O&, = {B E RRdc B B B.).
Given a local dataset S (could be St or its subset), define
1(w, B):
1
Σ EB
2
B w
x
(4)
Our goal is recover the ground truth representation matrix B' using the collection of the local datasets [m via solving the following linear instance of the FRL problem equation 3
min
min B):
(L-FRL)
B B I
w.
in federated and DP manner. Here, equation L-FRL is an instance of the general FRL problem (3 with h and Φ set to linear functions and set to the least square loss. Note that, despite the (relatively) simple structure of equation L-RRL, it is still non-conver w.r.t. the variable B.
Methodology for the LRL case. To establish our novel privacy and utility guarantees, we need to specify INTTIALIZATION and AGGREGATION in the procedures SERVER and we also need to slightly modify the CLIENT procedure, which are elaborated as follows.
1. To obtain the novel guarantee of converging the global minimizer for the LRL case, the ini- tializer 8 needs to be within a constant distance to the global optimal B" which requires a more
A similar problem is considered in (Jain et al. 2021 but the measurement yı suffers from an extra white noise with variance dp. In paper, we consider the noiseless case and hence when comparing with (Jain al. 202T), treat the or in their results for fair comparison.

---

Published as a conference paper at ICLR 2023
Algorithm 3 INITIALIZATION procedure for CENTAUR in the LRL case.
procedure INTTILIZATIONCZO e;, Lo, ro. Co)
2:
Run To independent copies of PPM Fo Co) obtain To candidates [B,)
3:
// PPM stands for private power method and is presented in Algorithm S
in the appendix.
4:
Boost this probability to n * via cross validation.
5:
Find è in [To] such that for at least half of E [To], s, [B BB) 2 2e vi E [k].
6: Il s.).) denotes the jth singular value of a matrix.
7: return B3.
Algorithm 4 CLIENT procedure for CENTAUR in the LRL case
1: procedure CLIENT(B', m)
2: Sample without replacement two subsets S/ and S from S. both with cardinality m.
3: [Phase 1:] Update the local head w arg min I(w, :
4: [Phase 2:] Compute the local gradient of the representation G. = 0n(((w By):s)
5: [Phase 3:] return G
sophisticated procedure than the simple random initialization. We show that this requirement can be ensured by running modified instance of the private power method (PPM) by (Hardt & (rice|2011) but the utility guarantee only holds with constant probability (Lemma F.T). A key contribution of our work is to propose novel cross-validation scheme to boost the success probability of the PPM with a small extra cost. Our scheme only takes as input the outputs of independent PPM trials, and hence can be treated post-processing, which is free of privacy risk (Lemmal 1:3) The proposed INTTIALIZATION procedure is presented in Algorithm
3 The analyses are deferred to Appendix 2. As discussed earlier, the feasible domain IB is the set of column orthonormal matrices. In order to ensure the feasibility of B we set AGGREGATION B' G Mggg = QR(B' - "l G)), where QR(-) denotes the QR decomposition and only returns the Q matrix.
We make a small modification in line 2 where two subsets S. and s.? of the local dataset are sampled without replacement from S; and are used to replace S; in Phases 1 and 2. This change is required to establish our novel utility result, which ensures that clipping threshold of the Gaussian mechanism (line in the SERVER procedure is never reached with a high probability (Lemmal
5.1 ANALYSIS OF CENTAUR IN THE LRL SETTING
Use (A) to denote the ith largest singular value of a matrix A. Let W E R be the collection of the local optimal classifier heads with W w.. We use s; as shorthand for (W*/vn) and use s1/5k to denote the condition number of the problem. We choose the scaling 1/ VT such that remains meaningful as + xc. We make the following assumptions.
Assumption 5.1. Vij is zero mean, Ia-covariance, 1-subgaussian (defined in Appendix A.7.
Assumption 5.2. There exists a constant > 0 such that maxie(x) || [l2 S py/esk
Assumption 5.3. The number of local data points is sufficiently large: Tra max(k? k.d/n)) Here čia hides the dependence on K, p. and the log factors.
These assumptions are standard in literature (Collins et al. 2021 Jain al. 2021). An elaborated discussion is provided in Appendix K While Problem (L-FRL) is non-convex, we show that the consensus representation B' converges to a ball centered around the ground truth solution B" in a linear rate. The size of the ball is controlled by the noise multiplier ag. which will be the free parameter that controls the utility-privacy tradeoff.
High level idea. For Problem (L.FRL.. we find an initial point close to the ground truth solution via the method of moments. Given this strong initialization, CENTAUR converges linearly to the vicinity of the ground truth since it can be interpreted as an inexact gradient descent method with a fast decreasing bias term. One caveat that requires particular attention is the clipping step in the Gaussian mechanism (line (5 in Algorithm 4 will destroy the above interpretation if the threshold parameter C, is set too small. To resolve this, we set So to be a high probability upper bound of | so that the clipping step only takes effect with negligible probability.
7

---

Published as a conference paper at ICLR 2023
In the utility analysis of the LRL case, we use the principal angle distance to measure the conver- gence of the -otunnoothooormal variable B towards the ground truth B". We also refer to this quantity as the utility of the algorithm. Let 1 be the orthogonal complement of B. We define
dist(B, B²) == II(Ta BB B
B B 1225
To simplify the presentation of the result, we make the following assumptions: The dimension of the input is sufficiently large d 2 x² k log n and the number of clients is sufficiently large n 2 m. The proof of the following theorem can be find in Appendix C
Theorem 5.1 (Utility Analysis). Consider the instance of CENTAUR for the LRL setting with its CLIENT and INITIALIZATION procedures defined in Algorithms f and 3 respectively. Suppose that the matrix Bd returned by INITIALIZATION satisfies dist B B")
cn = 0.2, and suppose that the mini-batch size parameter m. satisfies m. 2 Cm max (k. R2 lo k2d/n). Set the clipping threshold of the Gaussian mechanism Sg = equkks V Vdkkloogr n, the global step size Tl = 1/445 the number of global rounds Tg = crk² (ong gdd/n)) Assuming that the noise multiplier in the Gaussian mechanism is sufficiently small P] og I conk* conk*//p2 /(22 d/klonn.. Let cm. cc, OT Ca. Co and ca be universal constants. We have with probability at least - e,mil n n- dist( BT,, "²) S can ShogSaV = Eagyp2 d/n.
Since the SERVER procedure remains exactly the same as Algorithm [ in the LRL. case, the main body (anything after INITIALIZATION) of the resulting CENTAUR instance has the same privacy guarantee as described in remark [4.] However, we still need to account for the privacy leakage of the INITIALIZATION procedure in Algorithm 3 as it is data-dependent. This will be deferred to where we show that Algorithm 3 is an (a:, Cinit) mechanism, with Cyntt defined in Combining this fact with the RDP analysis for the main body leads to the following
Appendix F
Corollary
F.
privacy guarantee for CENTAUR in the LRL case (see Appendix AA.4).
Theorem 5.2 (Privacy Bound), Consider the instance of CENTAUR with its CLIENT procedure defined in Algorithm f and its INITIALIZATION procedure defined in Algorithm 3 Suppose that the INTIIAIZATIONN procedure is an (ax &mma) -RDP mechanism (proved in Corvllary F.l Let a g' the noise multiple in the CLIENT procedure, be a free parameter that controls the privacy uutiity trade-off. By setting the inputs to SERVER as Py = 1, T, = CTK² log(KngSSg o the instance of CENTAUR under consideration is an (ax, Einst + (rdp:/2)-RU
mechanism, where Erdp = 4aT, Moreover, when 0g = Ö(n/ (122 (d)),, we have Finst S Erdp/ in which case CENTAUR is an (a, -rap)-DDP mechanism and is also (Adp: 6)-DP mechanism with Cap 2 T, log(1/5)/ogg
Overall Privicy-Privacy Trade-off We now combine the utility and privacy analyses of CENTAUR in the LRL setting to obtain the overall
trade-off in the following sense: According to Theorem 5.1 to achieve high utility, i.e. small ca. we need to choose a small noise multiplier 0g while Theorem 5.2 states that the smaller 0g is, the larger the privacy cost.
Corollary 5.1. Use ca to denote a target utility, iee dis S Ga where BT is the output of CENTAUR and use Edp denote a privacy budget, iee. CENTAUR is an (Cdp: 8)-DP mechanism. Suppose that Edp 2 &2d2d/// (=")))) which is a restriction due to the requirement on og in Theorem 5.1 Under Assumptions 1o. 5.3 CENTUAR oulputs a solution that provably achieves the ta utility within the Edp budget, under the condition that the tuple (Ca: Cdp) satisfies čakkk 1.5 ppp /dd/n n S ca Edp
where y and č2 hide the constants and log terms.
When focusing on the input dimension d and the number of clients n and treating other factors as constants, the restriction on Edp and the trade-off of the tuple (Ea, <dp) can be simplified to Edp > (d/nn) and O(d/n) I ca Cdp- Recall that in the previous SOTA result of the LRL setting (Jain et al. 2021), the restriction on the DP budget is <dp > (dd-5/ /n) (point ii in Assumption 4.1
therein) and the utility-privacy tradeoff can be interpreted as (dd /n) S E. Edp (Lemma 4.4
"The intuition behind this requirement is that convergence analysis requires the iterates stay within ball centered around the ground truth, with constant radius (measured terms the principal angle distance). Adding a large noise will break this argument. Similar requirements are made in TTipuraneni et al. (2021).
"Note that Jain et al. (202)) use the Frobenius norm (instead of the spectral norm) of B B" optimality metric. However, since rank B B¹) < k we can always bound || B" | < <VVVVol Vidist B, B²). With this extra factor, Theorem 5. quadraaticlll depends on k same as Lemma 4.4 in (Jain et al. 202T), while the dependency d is substantially reduced, from d to d.
R g as the
8

---

Published as a conference paper at ICLR 2023
Table 1: Testing accuracy (%) on augmentation is used for training the representations. n stands for the number clients and S stands for the number classes per client. The ó parameter of DP is fixed to 10 as a common choice in the literature. The budget parameter of DP is fixed to small value of 1 for results in this table, i.c. Edp = 1.
with various data allocation settings. No data
SLand-
Methods
DP-FedAvg fb
PMTL- ft
PPSGD
CENTAUR
alone-no-FL.
CIFARTO, n=500, $=5
50.03 (1.59)
46.17 (0.12)
49.35 (0.44)
48, (1.44)
53.23 (0.92)
CIFARIO,
1=1000
74.06 (0.45)
57.02 (1.36)
67.79 (1.77)
71.52 (2.30)
76.23 (0.48)
CI 1=0000
44.60 (1.30)
37.15 (1.22)
35.99 (1.79)
44.61 (2.68)
49.92 (0.71)
CIFARIO0 100, 5=1000,S=5
39.20 (1.12)
22.17 (2.12)
24.17 (1.43)
32.97 (1.48)
44.54 (1.05)
EMNIST, 5=1000,5=5
93.47 (0.14)
91.32 (0.22)
92.32 (0.22)
93.44 (0.20)
94.17 (0.19)
EMNIST. 5
90.67 (0.46)
86.85 (1.11)
88.81 (2.08)
88.96 (1.93)
92.79 (0.25)
therein). Hence, we obtain @(vd) improvement in both regards, which means that CENTAUR delivers the utility-privacy guarantees for much wider range of combinations of Edp). Please an elaborated discussion of this result in Appendix!]
6 EXPERIMENTS
In this section, we present the empirical results that show the significant advantage of the proposed CENTAUR over previous arts Four baselines are included: St paned--aone--nee -n-FL which stands for local stand-alone training: DD-FedAvg
which stands for DP-FedAvg with local fine tuning Yu et al. 2020); PPSGD proposed by BBettti et al. (202); and PMTL-ft which stands for PMTL proposed by Hu et al. (202T) with local fine tuning. Note that Standdalone----------aa
does not volve any global communications, therefore no privacy mechanism is added to its implementation. This makes Stand-al private competing methods are affected by gradient clipping and noise injection, especially when the DP budget is small, c.g. Edp = 1. Another advantage of St podd-alone-noo no-FL setting is that, the local stand-alone models are highly flexible, i.c. the model on one client and be completely different from the one on others. On the contrary, while the models of all other non-local methods share a common representation part, which takes up the major portion of the whole model.
momee-noFFL. a strong baseline as the utility of all included differentially
We focus on the task of image classification and conduct experiments on three representative datasets, namely CIFARIO, CIFARI00, and EMNIST. In terms of architecture of the neural net- work, we use LeNet for CIFARIO/CIFAR federated learning literature, the details of which are discussed in Appendix. In terms of data aug- mentation, we do not perform any data augmentation for training the representation, as we observe that classic data augmentation for DP training leads to worse accuracy, as also reported in [De et al. (022). We also tried new type of data augmentation suggested by De et al. (2022), which does not consistently improve the classification (validation) accuracy in our experiments neither. CENTAUR Has the Best Privacy Utility Trade-off. We first present the utility (lesting accuracy) of models trained with CENTAUR and other baselines algorithms under a fixed small privacy budget Edp = 1, for variety of heterogeneous FL settings. To simulate the data- hatt--heterogenetty phenomenon ubiquitous in the research of federated learning, we follow the data allocation scheme of (Collins eet al., (202T): Specifically, we first split the original dataset into training part (90%) and a valida- tion part (10%) and we then allocate the training part equally to n clients while ensuring that each client has at most data from S classes. In Table I we observe that, under this small privacy budget, our proposed CENTAUR enjoy better performance than all the included bascline algorithms. Impor- tantly, CENTAUR is the only method that consistently outperforms the strong local-only baseline, and therefore justifies the choice of collaborative learning as opposed of local stand-alone training. Finally, we further demonstrate that CENTAUR enables superior privacy utility trade-off uniformly across different privacy budget e, for the setting of EMNIST dataset (n 2000, S = 5) in Figure
and use MLP for EMNIST, as commonly used in the
Conclusion. In this work, we point out that the phenomenon of statistical heterogeneity, one of the major challenges of federated learning, introduces extra difficulty when DP constraints are im- posed. To alleviate this difficulty, we consider the federated representation learning where only the representation function is to be globally shared and trained. We provide rigorous guarantee for the uuility-privae trade-off of the proposed CENTAUR method in the linear representation setting, which is O(Vd) better than the SOTA result. We also empirically show that CENTAUR provides better utility uniformly on several vision datasets under various data heterogeneous settings.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENT
The work of Zebang Shen was supported by SBF-CPSS-1832255 Hamed Hassani acknowledges the support from the NSF Institute for CORE Emerging Methods in Data Science (EnCORE), under award CCF-2217058. The research of Reza Shokri is supported by Google PDPO faculty research award, Intel within the www.private-ai.oor center, Meta faculty research award, the NUS Early Career Research Award (NUS ECRA award number NUS ECRA FY19 P16), and the National Research Foundation, Singapore under its Strategic Capability Research Centres Funding Initiative. Any opinions, findings and conclusions recommendations expressed in this material are those of the author(s) and do not reflect the views National Research Foundation, Singapore. In addition, Zebang Shen thanks Prof. Hui Qian from Zhejiang University for providing the computational resource, who is supported by National Key Research and Development Program of China under Grant 2020A AA0107000 The authors would like to thank Hongyan Chang for helpful discussions on earlier stages of this paper.
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Durmus Alp Emre Acar, Yue Zhao, Ramon Matas, Matthew Mattina, Paul Whatmough, and Venkatesh Saligrama. Federated learning based on dynamic regularization. In International Con- ference Learning Representations, 2020.
Naman Agarwal, Ananda Theertha Suresh, Felix Xinnan X Yu, Sanjiv Kumar, and Brendan McMa- han. cpsgd: Communiccation-eficieett and differentially-priee distributed sgd. Advances in Neural Information Processing Systems, 31, 2018.
Manoj Ghuhan Arivazhagan, Vinay Aggarwal, Aaditya Kumar Singh, and Sunav Choudhary, Fed- erated learning with personalization layers. arXiv preprint arXiv:19/2.00818, 2019.
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117744):30033-30070 2020.
Peter L Bartlett, Andrea Montanari, and Alexander Rakhlin. Deep learning: a statistical viewpoint. Acta numerica, 30:87-201, 2021.
Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE transactions on pattern analysis and machine intelligence, 35(8):1798-1822 2013.
Alberto Bietti, Chen-Yu Wei, Miroslav Dudik, John Langford, and Steven Wu. Personalization im- proves privacy-accuracy tradeoffs in federated learning. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.). Proceedings of the 39th Inter- national Conference Machine Learning, volume 162 of Proceedings of Machine Learning mmlr.
Research, pp. 1962-1962, PMLR, 17-23 Jul 2022. URL fweess/v12/biettee
html
Zachary Charles and Jakub Konečný. Convergence and accuracy trade-offs in federated learning and meta-learning In International Conference on Artificial Intelligence and Statistics, pp. 2575- 2583. PMLR, 2021.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference machine learning. pp. 1597-1607. PMLR, 2020.
Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai. Exploiting shared repre- sentations for personalized federated learning. In International Conference on Machine Learning, pp. 2089-2099. PMLR, 2021.
10

---

Published as a conference paper at ICLR 2023
Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai. Fedavg with fine tuning: Local updates lead to representation learning. NeurIPS, 2022.
Soham De, Leonard Berrada, Jamie Hayes, Samuel Smith, and Borja Balle. Unlock- ing high-accuracy differentially private image classification through scale. arXiv preprint orXiv:2204.13633 2022.
Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. Ad- vances Neural Information Processing Systems, 30, 2017.
Simon Du, Wei Hu, Sham M Kakade, Jason D Lee, and Qi Lei. Few-shot learning via learning the representation, provably. arXiv preprint arXiv:2002.09434, 2020.
John C Duchi, Michael I Jordan, and Martin Wainwright. Privacy aware learning. Journal of the ACM (JACM), (1)):11557, 2014.
Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacy-preserving ordinal response. In Proceedings of the 2014 ACM SIGSAC conference on computer and communications security, pp. 1054-1067, 2014.
Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized federated learning with the- oretical guarantees: A aggosti meta-learning approach. Advances in Neural Information Processing Systems, 33:3557-35663 2020.
Moritz Hardt and Eric Price. The noisy power method: A meta algorithm with applications. Ad- vances in neural information processing systems, 27, 2014.
Justin Hsu, Zhiyi Huang, Aaron Roth, Tim Roughgarden, and Zhiwei Steven Wu. Private match- ings and allocations. In Proceedings of the Forty-Sixth Annual ACM Symposium The- ory of Computing, STOC '14, pp. 21-30, New York, NY, USA, 2014. Association for Com- puting Machinery. ISBN 978 4703270777 doi: 10.1145/2591996.559 1826.
URL https:
//doi. www.orgg1..... 1145//191199 259182599888
Shengyuan Hu, Zhiwei Steven Wu, and Virginia Smith. Private multi-task learning: Formulation and applications to federated learning. arXiv preprint arXiv:2108. 12978, 2021.
Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi. Low-rank matrix completion using alter- nating minimization. In Proceedings of the forty-fifth annual ACM symposium Theory of computing, pp. 665-674, 2013.
Prateek Jain, John Rush, Adam Smith, Shuang Song, and Abhradeep Guha Thakurta. Differentially private model personalization. Advances in Neural Information Processing Systems, 34, 2021.
Yihan Jiang, Jakub Konečný, Keith Rush, and Sreeram Kannan. Improving federated learning per- sonalization via model agnostic meta learning. arXiv preprint 1rXiv:1909.12444 2019.
Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu.
Practical and private (deep) learning without sampling or shuffling. International Conference Machine Learning. pp. 5213-522 5225.. PMLR, 2021.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pp. 5132-5143. PMLR, 2020.
Michael Kearns, Mallesh Pai, Aaron Roth, and Jonathan Ullman. Mechanism design in large games: Incentives and privacy. In Proceedings of the 5th conference on Innovations in theoretical com- puter science, pp. 403 410, 2014.
Daniel Levy, Ziteng Sun, Kareem Amin, Satyen Kale, Alex Kulesza, Mehryar Mohri, and Ananda Theertha Suresh. Learning with user-level privacy. Advances in Neural Information Processing Systems, 34:12466-12479, 2021.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEFE Signal Processing Magazine, 37(3):50-60) 2020a.
11

---

Published as a conference paper at ICLR 2023
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Sys- tems, 2:429 250,9-450, 2020b.
Zhu Li, Zhi-Hua Zhou, and Arthur Gretton. Towards an understanding of benign overfitting neural networks. arXiv preprini arXiv:2106.0322 106.0321, 2021.
Yingyu Liang, Maria-Florina F Balcan, Vandana Kanchanapally, and David Woodruff, Improved distributed principal component analysis. Advances in neural information processing systems, 27, 2014.
Grigory Malinovskiy, Dmitry Kovalev, Elnur Gasanov, Laurent Condat, and Peter Richtarik. From local sgd to local fixed-point methods for federated learning. In International Conference on Machine Learning, pp. 6692-6701. PMLR, 2020.
Andreas Maurer, Massimiliano Pontil, and Bernardino Romera-Paredes. The benefit of multitask representation learning. Journal of Machine Learning Research, 17(81):1-32, 2016.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-effieie learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282. PMLR, 2017a.
Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. arXiv preprint arXiv:1710.0696. 2017b.
Ilya Mironov, Kunal Talwar, and Li Zhang. R Reenyi differential privacy of the sampled gaussian mechanism. arXiv preprint arXiv: 1908. 10530, 2019.
Aritra Mitra, Rayana Jaafar, George J Pappas, and Hamed Hassani. Achieving linear convergence in federated learning under objective and systems heterogeneity. NeurlPS, 2021.
Milad Nasr, Reza Shokri, and Amir Houmansadr. Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning. In 2019 IEEE symposium on security and privacy (SP), pp. 739-753. IEEE, 2019.
Krishna Pillutla, Kshitiz Malik, Abdel-Rahman Mohamed, Mike Rabbat, Maziar Sanjabi, and Lin Xiao. Federated learning with partial model personalization. In International Conference on Machine Learning, pp. 17716- 17758. PMLR, 2022.
Mark Rudelson and Roman Vershynin. The littlewood problem and invertibility of random matrices. Advances in Mathematics, 218(2):600-63) 2008.
Zebang Shen, Hamed Hassani, Satyen Kale, and Amin Karbasi. Federated functional gradient boost- ing. In International Conference on Artificial Intelligence and Statistics, pp. 7814-7840, PMLR, 2022.
Reza Shokri and Vitaly Shmatikov. Privacy-preserving deep learning. In Proceedings of the 22nd ACM SIGSAC conference on computer and communications security, pp. 1310-1321,2015
Karan Singhal, Hakim Sidahmed, Zachary Garrett, Shanshan Wu, John Rush, and Sushant Prakash. Federated reconstruction: Partially local federated learning. Advances in Neural Information Processing Systems, 34:1122000111 1220112011111 1132, 2021.
Virginia Smith, Chao- Kai Chiang, Maziar Sanjabi, and Ameet S Talwalkar. Federated multi-task learning. Advances neural information processing systems, 30, 2017.
Yue Sun, Adhyyan Narang, Ibrahim Gulluk, Samet Oymak, and Maryam Fazel. Towards sample- efficient overparameterized meta-learning. Advances in Neural Information Processing Systems, 34:28156-22 1166288666 168. 2021.
Kiran K Thekumparampil, Prateck Jain, Pranceth Netrapalli, and Sewoong Oh. Statistically and computationally efficient linear repeesepprssnntttton learning. Advances in Neural Information Processing Systems, 34:18487-18500, 2021.
12

---

Published as a conference paper at ICLR 2023
Nilesh Tripuraneni, Chi Jin, and Michael Jordan. In International Conference on Machine Learning, pp. 10434-10443, PMLR, 2021.
Provable meta-learning of linear representations.
Roman Vershynin. High-dimensionn probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018
Kangkang Wang, Rajiv Mathews, Chloé Kiddon, Hubert Fichner, Françoise Beaufays, and Daniel Ramage. Federated evaluation of on-device personalization. arXiv preprint arXiv:19/00 10252, 2019.
Tao Yu, Eugene Bagdasaryan, and Vitaly Shmatikov. Salvaging federated learning by local adapta- tion. arXiv preprint arXiv:2002.04756. 2020.
Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients. Advances in neural infor- mation processing systems, 32, 2019.
A MORE ON PRELIMINARIES
A.1 SUBGAUSSIAN RANDOM VARIABLE
Let E R be subgaussian random variable. We use ||x|| inf(s 0|E[exp(x²/s{) 2) denote subgaussian norm and say is ||xllyg- -ullau--uubausssian. For random vector E Rd, say is subgaussian if (z, x) is subgaussian for any weight vector Rd and the subgaussian norm of the random vector x is defined as ||x| suPaeRd ||=//==1 (æ, x)ll We refer to x as ||x||e> -sugauusiinn.
A.2 A USEFUL IDENTITY
Note that I, B B B Bi]
B B B B T and hence
inin (B B*) 8min (B B" B)= min a B Ba |
min a =
(I- T B B B T B)
Smax B BBBBA B T B) (dist(B", B))²
(5)
A.3 MORE ON PRIVACY PRELIMINARIES
Lemma A.1 (Gaussian Mechanism of RDP). Let Ry be the Rényi divergence defined in Definition
2.1 we have R, (N(,0 N,,,,, app (20²) Here N stands for the standard Gaussian distribution.
Lemma A.2 (Composition of RDP), Recall the definition of D in Definition 2.1 and let R₁ and R be some abstract space. Lei Mi: + Rí and M1 D Rí > R₂ (a, 61 RDDP and (o,, e2)- RDP respectively, then the mechanism defined as (X,Y) Y), where X ~ (i) and Y ~ M2(S, X), satisfies (a, E1 +ot+ -DD..
Definition A.1 (DP). Let θ be an abstract output space. randomized algorithm M D θ is (e, d)-differential private for all ID, ID' E D with d(D, D') < 1, we have that for all subset of the range, C θ, the algorithm M satisfies: Pr(M(DB) E S} S exp())
S) Theorem A.1 (Conversion from RDP to DP). If M is (a, ()DD) mechanism, it also satisfies
(c
log 1/8 - diffferrrtiia privacy for any 0 < 1. a-1
A.4 PROOF OF THEBRREM 5.2
Proof. Recall the definition of the Gaussian mechanism
GMç )im)) )=
clip(=; () + a(W)
13

---

Published as a conference paper at ICLR 2023
Stand- alone conn-nn-FFF
Edp
CENTAUR
DP-FedAvg fb
PPSGD
PMTL ft
0.25
no clip
0.01
0.01
0.01
0.01
0.5
clip
0.01
0.01
0.01
0.04
1
no clip
0.01
0.04
0.01
0.04
2
no clip
0.04
0.06
0.04
0.04
4
no clip 0.04
0.06
0.04
0.06
Table 2: Clipping threshold Ço to reproduce the results Figure
where W ~ NN0 I). Lemma A.1 states that GM2, So is (a, 20/0 RDP mechanism for 2 (the sensitivity is /5 while the variance of the noise is (gg5g/mu .) Using the composition of RDP again over all the iterates E [2], we obtain that Algorithm is an (a,, Cinit + 2aT, -RDP mechanism.
B DETAILS ON EXPERIMENTS SETUP AND MORE RESULTS
Models. use LeNet-5 for datasets CIFARIO and CIFARIO0. LeNer-5 consists of two convolution layers with (64, 64) channels and two hidden fully-connected layers. For CIFARIO, the number of hidden neurons are (384, 32) while for CIFAR100, the number of hidden neurons are (128, 32). We use ReLU for activation. No batch normalization dropout layer used. We use MI.P for experiments on EMNIST. It consists of three hidden layers with size (256, 128, 16). We use ReLU for activation. No batch normalization dropout layer is used.
Hyperparameters. All of our experiments are conducted in the fully participating setting, i.e. Pe = 1. According our experiments, the following hyperparameters are most important to the performance of CENTAUR: the clipping threshold of the Gaussian mechanism Sy, the global step size 'g. the local step size Tıt the number of global rounds Tg. For CIFAR10, to reproduce the clipping threshold C, in the set (0.01, 0.02, 0.04, 0.06} for every combination of privacy budget and baseline. The resulting optimal clipping threshold is listed in the Table 2 For other parameters, set 7/1 = 0.01, Tg 200 uniformly.
tradeoff presented in Figure we grid search the
To reproduce the utility results in Table T for CIFARIO, uniformly set C. 0.01. " 0.01,
77 = 1, T. = 200; for CIFAR100, we uniformly set S = 0.02, mi = 0.01, Tg = 100, 7l 1. Note that once the privacy budget Edp is given, determine the noise multiplier dg. given Tg- For EMNIST, uniformly set S 0.25, Tht 0.01, T 40, 73
the privacy engine from the package of Opacus to
There are also some algorithm-specificc parameters: For PPSGD, we set the step size for the local correction to 7) 0.1 and ratio between the global and the local step size 0.1. For PMTL-ft, we set X, the regularization parameter to 1.
For baselines that require local fine tuning, perform 15 local epochs to fine tine the local head with fixed step size of 0.01.
About data augmentation. In the Non-DP setting, the technique of data augmentation usually significantly improves the testing accuracy in CV tasks. However, in the DP setting, as reported in the previous work De et al.) (2022), directly utilizing data augmentation leads to inferior perfor- mance. In the same work, the authors proposed an alternative version of the data augmentation tech- nique which would improve the testing accuracy on various CV tasks in the centralized DP training setting. We tried their strategy in the federated representation learning setting under consideration, which however does not improve the utility in our case.
On the other hand, since the fine tuning of the local classification head does not require DP protection (recall that CENTAUR, the head is kept private), we employed the standard data augmentation in this phase (optimizing the local classification head), which improves the testing accuracy for
14

---

Published as a conference paper at ICLR 2023
Table 3: Testing accuracy (%) CIFARIO with various data allocation settings given larger communication budget I 400. No data augmentation used training the representations. stands the number clients and S stands for the number classes per client. The parameter of DP is fixed to 10 as a common choice in the literature. The budget parameter of DP is fixed to a small value of Edp = for results in this tablc.
Stand- alone-no-FL
Methods
DP- De-FedAvg-ER fb
PMIL-ft
PPSGD
CENTAUR
CI n= ==000,5==
74.06 (0.45)
63.97 (0.98)
67.71 (0.78)
74.63 (0.76)
77.80 (0.52)
CIFARIO, n= m=1000,S=5
44.60 (1.30)
41.12 (0.40)
45.75 (0.81)
48.29 (1.79)
51.05 (0.35)
0.8
0.5
testing accuracy
testing accuracy
0.7
0.5
0.3
DP-FedAvg-ft CENTAUR
DP-FedAvg-ft
0.2
CENTAUR
PMTL
PMTL
PPSGD
PPSGD
0.1
0.1
as
09 1.0
epsilon_ dp (cifarl0 N1000 S2)
epsilon_dh dp (cifarl0 N1000 S5)
Figure 3: Testing accuracy vs cap during training.
CENTAUR. We also tried the same technique for the fine tuning part other baselines, but actually leads to worse performance. Hence in the reported results, data augmentation is only used for the fine tuning the local classification head in CENTAUR and is not used in any other cases.
B. MORE EMPIRICAL RESULTS
To study the performance of different baselines given larger communication budget, i.c. larger Tg, we conduct additional experiments on CIFARI0 and report the results in Table 3 We can observe that CENTAR AUR has the best performance among all the included methods, uniformly in all configurations. In Figure 3 we further show the testing accuracy (utility) vs the privacy cost edp during the training. We observe that CENTAUR quickly converges to a high utility can consistently outperforms the included baselines.
C UTILITY ANALYSIS OF THE CENTAUR INSTANCE FOR THE LRL CASE
To present the utility analysis the CENTAUR instance for the LRL case, Problem L-FRL is equivalently formulated standard matrix sensing problem. By setting the clipping threshold Sy to a high probability upper bound of the norm of the local gradient G; (see Lemma C.1 we show that CENTAUR can be regarded mini-batch size parameter, is sufficiently large and that the initializer B is sufficiently close the ground truth B", we establish high probability one-step contraction lemma that controls the utility dist( Ba, B*), which directly leads to the main utility theorem 5.1
inexact gradient descent method. Given that the
Matrix Sensing Formulation Consider a reparameterrization of the local classifier w; /no,
Fl
Problem FRLL can be written as
min
Σ ==1 P.ERY
min
1
Vnlv, B
x.y) BTx.) y15)2
(6)
'We consider this rescaling of w. that the corresponding linear operator in equation is isometric operator in expectation (see more discussion below).
15

---

Published as a conference paper at ICLR 2023
Further, denote V Ro*k the collection of local classifiers, V..: vs The collection of optimal local classifier heads W can also be rescaled as W = VnV* and the responses Vij E R satisfy
Vij = V Fijs V
Define the rank-1 I matrices Aij x.)e(()))))) E Rddx (e E I2) and define the operators A₁ R R and A : Rdxx + RRV
(x) (vn(A.j. X) [jejm] ER", A(X) = (A, E ERY,
(8)
where we use N = nm to denote the total number of data points globally. Note that VN isometric operator in expectation w.r.t. the randomness of { i.e. for any X E Rddx
A is an
m
E [ 16 A(X,,
ne
(i)
X [1.) (e()
==1
1 N
ΣΣ
nX x
1
ΣΣ
m
n2 X
|
=
N
where we use Assumption 5.1 in the second equality. With the notations defined above, we can rewrite Problem (L-RRL as a standard matrix sensing problem with the operator A
min B B= VERTXE
min
F(B,V:A)
A(BVV = 2N - ))F.
(MSP)
Since CENTAUR only uses a portion of the data points from S; to compute the local gradient G;; (see
line
2 in Algorithm 4 it is useful to define the operators Atd and A²²² that corresponds to s and 2.2 respectively, and their globally aggregated versions A and Ar..
A 1 (X)= = (Vi(zz)ee()
xx) E ER A.A = {A (X))ev()))) ERA,- -,,1111,,, 1,2, (9)
where we denote - mn.
Clippings are inactive with high probability The following lemma shows that by properly setting the clipping thresholds Cg. the clipping step of the Gaussian mechanism in Algorithm takes no effect with a high probability.
Lemma C.1. Consider the LRI. setting. Under the assumptions 5.2 and 5.1 bility at least 1 mn k,
we have with proba-
|| S = dk logn,
where G is computed in line of Algorithm and Sg is some universal constant.
Proof. The detailed expression of G. in line of Algorithm can be calculated as follows:
G 0g B'):
Σ (IB*) Fijy w - yis) æ w -I.
(10)
m
(201 (ea))My)ee Jest? )ESt
Using the triangle inequality of the matrix norm, Ç high probability upper bound of |[ the incquality
((B' Zzy. w) yos) xi w +11 1FSC
(11)
holds with high probability. In the following, show that the inequalities (B Tıj. w) S1, Iynil Sy. |aaelll S Cur and 11| Çw. hold jointly with probability at least 5n which together with (Gu + Caw I C, and the union bound leads to the result of the lemma.
Choice of Gy Recall that in Assumption 5.1
with |atyylls = 1. Using the definition of a assume that Dij is a sub-Gaussian random vector random vector, we have
P( 2 Cy) < 2 2exp( (1, < exp( logn).
(12)
with the choice Cy pV/ / (k + log 2)/c, / n) since || ll I uvbss Here Co is some constant and recall that s is shorthand for su (W' /vn)
16

---

Published as a conference paper at ICLR 2023
Choice of &e Recall that zij is uab-Gaussian random vector with |ayllees 1 and therefore with probability at least 6,
[asll 4vd 2
2 logg
(13)
Therefore by taking ó exp(-k n)), we have that Sa 4vd+ 2
= O(vo).
Choice of Se We can show that S. = ksy is a high probability upper bound of w Proving this bound requires detailed analysis FedRep and is discussed later equation 663
Choice of S The following event is conditioned on the event 1 S 2pykss. We will then bound the probability of both events happen simultancously using the union bound. Since æy is sub-Gaussian random vector with | llv 1, using the definition of sub-Gaussian random vector, we have
Pl((Bwttt m.yi) 2 (i) S
1|1) I exp(-klogg))
(14)
with the choice Ç1 = 2pvkssk V log n + log 2)/c, Oluskkylog since u ll2 S 2pykss Here is some constant and we recall that sy is a shorthand for sy (W*/v/)) Using the union bound, we have that w.p. least eexp( log n), the upper bound (i is valid.
IT
The idea behind the proof To present the intuition of the utility analysis of CENTAUR, define
V(B:A) arg min F(B, V:
(15)
VER=XE
where A is some matrix sensing operator and F is defined in Problem MSP)) Under the event that the clipping steps the Gaussian mechanism in Algorithm takes no effect, the average gradient G E== G admits the following compact form
G = OBF(BB :
(16)
Suppose that A ~ A ~ A (recall that all these linear operators comprised of iid. data points Vij and are hence similar when m is large). Further define the objective
A(
min F(B.V:A) VERnxk
(17)
We have G ~ (G(B",A) since
3BF(BB, A)B:;A)::
where Jv denotes the Jacobian matrix of V (B; with respect to B and the second equality holds due the optimality of V (B': A). Consequently, conditioned the event that all the clipping operation are inactive, CENTAUR behaves similar to the noisy gradient descent on the objective ((B:A) (up to the difference between A A and A). In the following, we show that while the objective G(B; A) is non-convex globally, but we can show that CENTAUR converges locally within a region around the underlying ground truth.
present our theory, we first establish the following properties that the operators A and .4 (defined in equation 9) satisfy, Recall that N mi Ei= 1. The proof' are deferred to Appendix
One-step contraction
Lemma C.2. Under Assumption probability at least cxp(-c1k n):
5.1 the linear operator A satisfies the following property with
(BV),
8(1.
sup VER=xk [.amx*/||V|l== [
Here, the factor 8(1) Vklog 1i m
17

---

Published as a conference paper at ICLR 2023
Lemma C.3. Under Assumption 5.1 the linear operator A satisfies the following property with probability at least exp(-o2k log For V1, V22 E R"*;;
N (1"' LBB'V A (B'V S dist (
sup I I==
Here, the factor 8(2) = /k log n/ vm.
Lemma C.4. Under Assumptions 5.1 and 5.2 the linear operator Ar. satisfies the following prop- erty with probability at least exp( Ozk logn): m): For E RR., E R
(A4 (B'v B'V (ab v M>| 83)) sf (iddist(B' (B', B²).
sup
[a.|
Here, the factor 8(3) 4( (vd + V // (Vmnk*).
We now present the one-step contraction lemma of CENTAUR in the LRL setting. The proof can be found in Appendix [.I]
Lemma C.5 (tne-step contraction). Consider the instance of CENTAUR for the LRL setting with its CLIENT and INITIALIZATION procedures defined in Algorishms 4 and respectively. Suppose that
the matrix B returned by INTIIALIZATION satisfies dist B. S 0.2 and suppose that the mini-batch size parameter satisfies
A2d - 1- log
2 Cm max{x²K 222 log n.,
for some universal constant Cm- Set the clipping threshold of the Gaussian mechanism So according to Lemma and set the global step size nlg 1/4s/. Suppose that the level of manually injected noise is sufficiently small: For some universal constant Co. satisfies
Co
Og
n)logn)
min
1:2 logn'
v log
(18)
We have the following one-step contraction from single iteration of CENTAUR
BB)/1-EEE + 3CN no Vd.
dist (attBB,. B B++ <
(19)
holds with probability least cpmnn where cp is some universal constant. Moreover, with the same probability, we also have
dist(B' B¹) S dist(B",, BO).
(20)
Remark C.1. The lower bound of the mini-batch size parameter m is derived to satisfy the following inequalities:
8k2) (812))2k
(1-
max
5(1) (1- 8(1)2 800)
36s
which is required to establish the above one-step contraction lemma. The upper bound of the noise
multiplier 0g is derived to satisfy the following inequalities:
T <
VI-
8k 8x²En
mmn
(21)
VFlon 3CNVdd..
Proof of Theorem 5.1 Denote Eo /1 - eg. Using the recursion
19
we have
dist(B", B') (1 En/8k 2/2 B") 3CN Mg vd/(1 VI Eo/ SK?)
n
dist d B²) v8C With the choice of T specified in the theorem, have that
< (1 E 8k 2/2
g Vd/Eo- En-
(22)
n
dist (Bs((B"B")) B') S cak" Og Vd. for some universal constant Ca. By plugging the choices of ng So- we obtain the simplified bound , < 00 2 k.5d/nn
(23)
where ča hides the constant and log terms.
18

---

Published as a conference paper at ICLR 2023
D PROOF OF THE ONE-STEP CONTRACTION LEMMA
D.1 PROOF OF LEMMA
Proof. The following discussion will be conditioned on the event that all the clipping operations are inactive, whose probability is proved to be at least 1 - 5n in Lemma C.I Using union bound to
combine the following result and Lemma C.1 leads the result.
Recall that the average gradient G
Σ>= G. and denote Q' = B'V - BVV*T Denote
B
B² + 1lg G
(24)
Recall that C = {l,...,, n) given Pg = 1. Since the clipping operations are inactive, we have
B = B' 7/
+ Q't
(Q'v++1 -G) 18g w
(25)
n
where W denotes the noise added by the Gaussian mechanism in the thh global round. Note that
B Q' B B'v and denote the QR decomposition B B R
We have
Bi B
g wt) (
=Bi
B' BB' - 11-199 Q'V + + (Q'V411- - G
n
= -i B' [1 -la-nya Vetec (B(+1)-1
T (Q'V+t1 G³) (R(-1)-- LoogLo B ('+ + n
n
Recall the definition dist B B") = = B¹1 We bound
dist(B", Bist(B",B'tt BB+)) < dist B'] 7l v v (R
11
+ -
Bi W (R++1=11) (26)
n
In the following, we show that the factor || - fg V || to a contraction in the principal angle distance and treat the rest two terms controllable noise for sufficiently small constants (8(1) ((2), 5(3)) (see Lemma C.1 and sufficiently smaller noise multiplier og (see equation 18).
< which leads
Bound 1
79 V V*+1||.
Recall that f19 1/4s/. Using Lemma D.5 we have
28(2) dist B" ,²))) < 1 - ny Eost - 0.75, (27)
[ 7g v y
$ 51-1 - 7g (Eos?
1-8(1)
where we use the following inequality in Remark C.I
(6 of 1 5()) dist Bd) <
o 8(1)
S /
(28)
Bound ||(
With the choice of m stated in the lemma, the tuple (8(1), ((2),8(3))
8(3) satisfies
the requirements in Remark C.I Using Lemma D.7 we have with probability at least 4n
||(**+))-11 < 1/ / no Eo/2
(29)
Combining equation 27 and equation 29 have the contraction
- n Eu 0.75 n1 n Eg 0.5
14 7g V
y
(R -
1.
/1
We now bound the last two terms of equation 26
19

---

Published as a conference paper at ICLR 2023
Bound |Q Gl Using Lemma D.6 have
IQQ' G" - 5 s
. .B') dist BB", -0.25,
(30)
where we use condition in Remark
C.1 ((3)
Eo
Bound Ui T W Due to the rotational invariance of independent Gaussian random variables, ery entry in Bi W R(n-kjxk is distributed as NO0, 1). Using Lemma L.1 we have with probability least 1 n
B W Cwlvd-ki vi= II(kklgg)) S 3CNvd,
(31)
where we assume d O(log log to simplify the above bound.
Final Result. Combining the above bounds, we conclude that the following one-step contraction holds under the assumptions stated in the theorem.
1 fg E (0.75 1175-0.20 0.25)
no Vd
dist(B', B", B²,B' S dist( (B" BB')
+3CN
V1 fg Fost 0.5
n
S dist(BB, B¹) 11 Fo 0.5 + 3CN 10 vd
D.2 LEMMAS FOR THE UTILITY ANALYSIS
Lemma D.1. Use vec(.) and @ to denote the standard vectorization operation and Kronecker prod- v
uct respectively. Recall that V++1 == arg minl gRaxE. F(B", V:A'+.),, ). We have
vec(V(+1) vec ( (B -
(32)
where
f = -B tt H:x)) vec(V") H==1 B² B Ia) H
rec(V*).
(33)
Here we denote
H
bec(A,) vec(AA], B*) Rukxnk
(34)
jEStI
n H
vecl (ec(AA)/") veel (., Buknnk
(35)
JEB
use F E Baak denote the matrix satisfying f vec(F").
Proof. Recall that N mn. For the simplicity of notations, we use the collection (A,), 1,..., to denote {Ai). i E [n]. St (there exists a one-to-one mapping between the indices I and (i,j)). Compute that for any B lRd and V Baxk
vec(OyF(B, V))
(vco(A) A, B) vec(V) vec(A, BT) vec(V*)) vec(A, B)
vecl AT B) veel Ae B)T vec(V)
1
vec B) vec(A] By)T) vec(V").
N
l=1
20

---

Published as a conference paper at ICLR 2023
Since V++
arg VER F(B', V: V:Al),, we have FvF(BB, V ;A"!!) 0 and hence
N
N
nee vea(Ve+))
Σ
vea A B¹) veel
vec( vec(A B²)T
veal A B¹) vecl BT)T] vec(V~)
N
N
E=1
1=1
=H" H vec(V"),
where we denote
NV N
H
Dea Ai B¹) (ec(A] B²) E Runxnn
H vec A B*) vec(A] B²) Rnkxnn
Use to denote the Kronecker product of matrices. Recall that
(B' A) xec(X) Dec(AXX).
(36)
We have
vec (BB'VT)TBB TB)) = vec (V-B*BB) ( B" 8 la) vec VVc(
(37)
Lemma D.2. Recall the definition of H in equation 35 and that Smin denotes the minimum sin- gular value of a matrix. Suppose that the matrix sensing operator A satisfies Condition C.2 with constant 8(1. We can bound
mmin (H 2 8(1)
Proof. From the definition of 8min, we have
1 min vec(P) H vec(P) - (B"")" A B T )) 211 21-60 (0)) (B'P
Smin (H
Eanx
Lemma D.3. Recall the definitions of H and H in equation 35
35 and equation 34 and recall that
dist(B', B") is the principal angle distance between the current variable B and the ground truth
B Suppose that the matrix sensing operator A satisfies Condition can bound
C.3 with constant ((2)
H B" &
H S 8(2) dist B*).
(38)
the collection (A.). 1,..., N to denote (Aij,i i [n].. E St (there be a one-to-one mapping between the indices
Proof. Recall that Ñ mn. For the simplicity of notations,
I and (i,))). For arbitrary W BRink P Rank with |W]|r ||]| 1, we have
1 N Ñ
wee w) H B' 8 (P) =
Σ
(ec(W)T (cc(A] B¹) A B¹) vec PB* B²)
1
Σ
(A,, B' (A, B B'P
N (A'' A B+P"))
where we use (B A) vec(X) vec(AXB) in the first equality. Similarly, we can compute that
1
vec(W)] H vec()-
N (B
(39)
21

---

Published as a conference paper at ICLR 2023
and hence
vec(W)) (B'
[
B ② Ia) H vec( PP)
1 N
A (B'B" BI ))))
(40)
Using Condition
C.3 and the definition of Smax, we have the result.
Lemma D.4. Recall the definitions of F and f in equation
33 and recall that dist B B*) is
the principal angle distance between the current variable B and the ground truth B Suppose
that the matrix sensing operator A satisfies Conditions C.2 and C.3 with constants 8(1) and 8(2) respectively. We can bound
81 V 8(2)
11 <
dist ,
(41)
8(1)
and
8(9) s V | S Vksi + - 8(1) dist(B" BD) < 81 V VkV11 - -00) + (()
(42)
1 1-1
Proof. The bound on F || a direct consequence of Lemmas D.1 to D.3 and the fact that the matrix norms are sub-multillicative The bound on ||++||| is due to the fact that the matrix norms are sub-additive.
Lemma D.5. Suppose that the matrix sensing operator A satisfies Conditions constants ((1) and ((2) respectively. Further, suppose that max
C.2 and C.3
with
(02) VT
(8
Eg
For
1-0
1-8011721
36s
sufficiently small step size fl $ 1/(4s/). we have I bound
77
V
V
> O. Moreover, we can
28(2) si
[ 7l V T
v 1 S 1 (Fo
dist B", B²)).
(43)
1 1 5(1)
Proof. We first show that the matrix 1 Mg V V is positive semi-definite for sufficiently
small step-size 77.- Note that following the idea of the seminal work Jain et al. (2013), the update of g AAB';AA'1 can be regarded as a noisy power iteration, as detailed in Lemma D.1 This allows us compute
|| T = B' F s 2 B" T + 2|
812) T-)(1)
2 dist (B", B') S 487
$ 26 +2
where we use Lemma D.4 in the first inequality and use
/ T-80J in the last. Consequently, for
My S a.7. It v Vt+1 > O.
Given the positive semi defintefintssness of the matrix I& ny V T v we can bound
1 77 vt+IT vi+ill2 112 S 1 m (V++1 v(tl).
By using Lemma D.I again. We have
V T Vt+1_
(V.B*T B' - -Fi) (V. B' F')
B' BB B'V' B' B'- V B B² B'V F++ F² F F
Note that F²t F² is PSD which makes nonnegative contribution to smin ( (V++1T VL+l) and hence
Smin (V+1 v( 2 smin (BeT B B' V T B² -B B. Ft)
Smin (B') T B* B') 28 ( FF' " V
2 (B:T B')
2 (V*) 2| F'1 S (V*)
(44)
22

---

Published as a conference paper at ICLR 2023
To bound the first term of Eq. equation 44 recall that smin (B' B*) (dist (B", BB')² from
Eq. equation 5 and dist(BB, B²) I dist( B from the induction, we have s (B' B*) 2
Eg. To bound the last term of Eq. equation 44 we use Lemma D.4 to obtain | 2 S
|F || S
a dist B², B¹). Combining the above results, we have
I-80:
20(2) 5()
14 7l V V 12 S1 -Eg
dist B", B))).
(45)
Lemma D.6. Recall that V++1 V (1.2) (see the definition of ((; in Eq. equation
15
Q'= B' - -B'V* G² -² Gi is the global average of local gradient, and recall that ( B²) is the principal angle distance belween the current variable B and the ground truth B". Suppose that the matrix sensing operator A satisfies Condition
C.4 with constant
813). We have
G - Q'V 122 S 813) (kddsisstt(BB (B*, BB).
(46)
Proof. Recall that N mnn. For the simplicity of notations, 1,... N to denote {A,j,i i [m].j E S. (there can be a one-to-one mapping between the indices 1 and (1,j)). With this notation, we can compactly write G as
the collection (Ai).
Ñ
G
Σ A A
(47)
From the definition of smax, for any E Rdd with |all2 = 1 and any b E R with ||bl|2 1, we have
we
N
8
Ar, -
a T
(A., Q') - b.
max
|all= 1b1l==1
N
1=1
We obtain the result from Condition
C.4
1 N (B'
B'V* A Tv+tT M>| s (13) kkddsttss B").
(48)
Lemma D.7. Recall that B*+1 B R²+1
is the QR decomposition of B Denote Eo 1-
and gg n. Suppose that Conditions C.2 C.4 are satisfied with constants 5(1), 5(2), and
g(3), Further, suppose that max g(3) o
(8 T
819)
k}
En
and the level of manually injected log n)
1-8
36s
noise is sufficiently small o S (CxxPykloge
We have with probability least 1
1
I[(R++)) S
(49)
V1 - ng9
Proof. We now focus on bounding Smin (R)+1), Recall that G¹ = (B VL+1, A4,2) with
Vi+l V(B", (see the definition of V(:AA) in equation 15) and recall that B++1 == B*
ng G oW. Compute
R-+17 R BL+1 B++1
= 1s + G T G² +o2 T W - yy B² T G² tob' w' +ow B' G W² - noww G.
Therefore, we have
Smin (R--1 R R(+))2 1-
BB' G¹) ( -20s max BB' - osaa (G' w.) (50)
We now bound the last three terms of the R.H.S. of the above inequality.
23

---

Published as a conference paper at ICLR 2023
1. Smax B' BB)
To bound Smax
B
T G*
compute that
B² B² G' Q'V B (G' - -Q'V++)..
(51)
where we recall the definition of Qi as Q' B'V++1T BV Note that the spectral norm of second term in Eq. equation 5 bounded by Lemma D.6 and we hence focus on the spectral norm
of the first term B Q'Vi+I, Recall the noisy power interpretation of Vi+1 in Lemma D.l We can write
B Q'V Bd (B BV - -F F²)) B.V.T) VLt = F T VL+1 V
FCT (V'B* B' Fr))
(52)
where use B follows
(''B'T - -Ia) B-V.T 0. Consequently, we can bound Smax
B Gt as
G²)
81 F - | G - Q'V 112
max
5(2) v
(5(2))
Fo
+ 810) 5 -
8(1)
(1 11))
12
where we use the assumptions that max for the last inequality.
1 vk
(8(2)
83))
S
+ Fg and 364
$
1-80)
(1-5
Bd (TT): Due to the rotational invariance of independent Gaussian random variables, every entry in B' W E gexk is distributed as NN 1). According to Theorem 4.4.5 in Vershynin
2. 8 maxx
2018), with probability at least 1 exp( (app-ki log n), we have the bound || || W < some universal constant Cy.
Cwy/klogn
48v2
3. Smax
Let G¹ = ScV be the compact singular value decomposition of G' such that UG E Baxk and UdUG In. We can bound
Smax (G' < ||Sa|||UG W/
(53)
Due to the rotational invariance of independent Gaussian random variables, every entry in U ' E R is distributed as (/ 1) and hence with probability at least 1 - 2 exp( log n), we have the bound ||U W'll < Cx log for some universal constant Cy. We now focus on 48v/
bounding || ||'' 2| Note that
G = Q'V (G' - Q'V
(54)
where the spectral norm of second term in Eq. equation [4 bounded by Lemma D.6 Recall the noisy power interpretation of Vi+1 in Lemma D.I We write
Q'vi+1= = (B'(BT B -F F BVV+T) V4+1
(B' IBB - -. -B'F'T)
(V'B*T B" BBBBBB
and therefore we can bound
2 dist B BD) ) < <407,
812) (12)s
IIQ' 1/2 S (8)
12)
81 +
(55)
1 8(1)
since we assume that
8 1-500
<
Combining the above three points, we have with probability least 1 expp(pkkllo
Smin ( R 2 Fo/6 Cx k logn/6 1g0 CN k 2/66. (56)
24

---

Published as a conference paper at ICLR 2023
Hence, if we choose such that (recall that Mg 1/4s])
Fg
a Crrkllogn I ng fffFa Eo and ogo CN lovkloon of I Fg = o
(57)
4Cxx² V logn'
have
Smin RR/ R(11) 2 1 - E0/2 + Smax ( (R 5
(58)
na En/2
E ESTABLISH LEMMAS C.2 TO C.4FFR FOR THE LRL CASE
E.1 PROOF OF LEMMA
For the simplicity of the notations, we omit the superscript of At and A Moreover, recall that v V,, E &R denotes the ith row of the matrix V.
While we can directly use an c-net argument to establish the desired property on the set of matrices V Rn*k || = 1, it leads to a suboptimal bound since the size of the E-net is O((2 + +1)=).. In the following, we show that by exploiting the special structure of the operator A. i.e. V is row-wise separable A(B'V T), VT) we can reduce the size of the e-net to O((2 + 1)²): Compute that
A(B'VT) A(B'V
(A((''r AB''
VN
n
m
If for any E R l 1, we have (A T can show
A )) n n11n(1111 0(8())) we
(i) T
A, B uie(1)
ABVV), 1 A(B'VT))
1 (A,
|1:12 ))
10:112
m
10l13 (1 ((00)))) = = 0(8()), V E R [
which is the desired result (note that (B'VT, B'VT) B'V |F 1). We now establish
1 (A(e'ee () (.A, 11 "..
1 m Σ n((2 T
u)² = n (1=0
holds for any v E IR* ||0||2 1. Let Sk-1 be the sphere in the k-dimensional Fuclidean space and let Mr be the 1/4-net of cardinality 9 (see Corollary 4.2.13 in Vershynin (2018)) Note that
Eラ= n(( B¹) v)² nw ('
Ef=1 Dij 2 B' I and we have
sup T vest-1
B
v < 2 sup T B Is
B
Σ 1=1
B
Is
U,
NE
(59)
where we use Lemma 4.4.1 in Vershynin (011). In the following, we prove
m
sup T vENa
T Bt
aija B¹ Ix 1 0 80)/2
m
j=1
so that we have 1 m.
Σeh m( B T3) n 0(8(1)).
For any fixed index i, denote Z, B' = B' and note that Ex, [Zyy] Since
Diy 's are independent subgaussian variables, Z,j 's are independent subexponential variables. Recall
that ||- lle, and Il denote the subgaussian norm and subexponential norm respectively and
25

---

Published as a conference paper at ICLR 2023
have [XY]] ti || |Y for subgaussian random variables X and Y (see Lemma 2.2.7 Using the centering property (see Exercise 2.7.10 of Vershynin (2188) and Bernstein's 's inequality (see Theorem 2.8.1 of Vershynin 2018)) of the zero mean subexponential variables, can bound, for every Z 0
in Vershynin 2018)), Therefore, we can bound Laylles S <n
m
m²n227
Pr( Σ m ==1
Zi - n| 2 nT) - exxp
--miin
mit
12gllle }
Ez=1 || 11 maxxeemm
2 exp (-cmin ( mT))
TH
exxp (-cmT²)
where c >> is absolute constant. Using the union bound over Wi. and set 7 V log ni nn//m Vm. We obtain g(1) Vologry /mm with probability at least 1 exp(-c'k: log for constant d' Similarly, we can show that Σ==1 n((x)) B²) TT)z n (6)1).. We therefore have the result.
E.2 PROOF OF LEMMA
Recall that E I denotes the ith row of the matrix V and denote W = (B'B' Ba)
Following similar argument Lemma C.2 simply need to focus showing for any 11 U2 R |elll = |/2l|| = 1, we have i. (Wr (B'rze)) )) =0(n(()) (Note that
(War oi (6)) (''ze(()) 0). Let S be the sphere in the k-dimensional Euclidean space and let N₁ be the 1/4-net of cardinality g (see Corollary 4.2.13 in Vershynin (2018). Note that
(A e() (B'
nv
W
B c B
U2
(60)
Moreover, according to Exercise 4.4.3 in Vershynin (008),, we have
1 m
sup ES
W
Bigay B'
122 2 sup oi M.
W
Biy m.
B'
222
In the following, we prove that the quantity the RHS is bounded by 5(2) /2 that have the desired result.
For any fixed index i, denote Zi n(x;, We (2))) (x.,, B2)) and note that Ex,, [Zg]] 0. Since Piy's are independent subgaussian variables, Zij 's are independent subexponential variables. We can bound || /Zzy S n We, vn BB 022 ndist(B', B*). Using the centering property (see
Exercise 2.7.10 of Vershymim 2018)) and Bernstein's 's inequality (see Theorem 2.8.1 1 of Vershynin (2018) of the zero mean subexponential variables, we can bound, for every / 2
1 Pr(
m?n
Mnt
Zag 2 nT) 2exp -eminf ===1
12
maxje(m) Zzgllen
==1
m
2cxp
-emin|
(dist(B' Ba, 2² dist B (B',B.)) BB))
where e > 0 is an absolute constant. Use the union bound over N2, set 8(2) S Vklogn/ Vm and set = dist B', (2)))) We show that Condition C.3 is satisfied with parameter 8(2) with probability least 1 exp(- log n) for some constant
E.3 PROOF OF LEMMA
Denote Q B' V and recall that V., I denotes the ith row of the matrix V. For simplicity, denote W N Einlj= (Aij, A,, y++1 and note that Eg;; [ Q'+++1
We use an e-net argument to establish the desired property on the set of vectors a E R4 b e
R* |a||| |bb|| 1. Let - and Sd-1 be the spheres in the k-dimensional and d-dimensional
26

---

Published as a conference paper at ICLR 2023
Euclidean spaces and let Mi. and Na be the 1/4-net of cardinality 9 and 9d respectively (see Corol- lary 4.2.13 in Vershynin (2018) ). Note that
(A(Q') A(ab V =a Wb.
(61)
Moreover, according to Exercise 4.4.3 Vershynin (018), we have sup aES4-1.bSt--
aT(ww (W Q' Q'V++1)6 2 sup aENa.DEM
In the following, prove that the quantity on the RHS is bounded by 5(3) sj B/2 so that we have the desired result. We first bound ||Q l21e and 1, ||2 they will be used in our concentration argument.
Bound || | 2- Using Lemma D.I we can write V = -VB-TT B - F and therefore 1.
V = B BV F.. Using Assumption 5.2 we have |V S pVksk/ Vn. Further, we
compute that
Fl.
B' B.janly B'
B'
2.y (B' (
Ia)
V
(62)
m
m
Using the variational formulation spectral norm and Conditions 812) V logn/ n/ Vm), we have | <
C.2 and
C.3 (note that 5(1)
dist B",
pyRas vn
Therefore obtain
1-5
1/2 S 2/V/Tss/V
(63)
The high probability upper bound of wt in Lemma C.I noting that wt VnV...
can be derived from the above inequality by
Bound
(''e(0))
||2-
Recall the definition of Q' B'V -B.V-T
Using Lemma D.I
obtain
Q' = BVV B B F BV = (B'B" L' - FB"
(64)
We can bound ||Q'e(t) 2| S (B'B'T Ia) 12l10/112 + | S 2dist B¹, B" B') Vn.
Denote Zi nα
;j Q' (() ab V and note that 1 Σn E.g [Zy nb V Q'a. Since Zzy" are independent subgaussian variables, Ziy 's are independent subexponential variables. We can bound | 7 | < nn|(Q (1)())
n,
2 lab v < 4ky2sgdis disisst(B' (B', B*). Using the centering property (see Exercise 2.7.10 of Vershynin 2018) ) and Bernstein's 's inequality (see Theorem 2.8.1 1 of Vershynin (2018) of the zero mean subexponential variables, can bound, for every t 2 0
Pr(
Σ
Zij a 1Q 2T}
i=1j=
m7. ??n
MAnT
< exxp
femin
71,7
|| 11
ZZg 11
Li=lf==1
mmn
2exp
-ominn
2 B-y)
(Akp2s?ddis((B! (B, B'),
Set 5(3) 5(3))))kdist(BB B*). We have that when ((3)
4(v [oggg Vinngz
Pr(l
Zg - a ( 22/ exp (-e(d h log
(65)
i=1jj=
Use the union bound over No. x Na. have that with probability least exp(pc"kk log Condition holds with ((3) 4(vd+ (og
/ Vmnna
27

---

Published as a conference paper at ICLR 2023
F ANALYSIS OF THE INITIALIZATION PROCEDURE
In this section, we present the privacy and utility guarantees of the INITIALIZATION procedure (Algorithm 3 when the local data points 2i are Gaussian variables. Recall that to establish the utility guarantee for CENTAUR in the LRL setting, a column orthonormal initialization B E Bd such that the initial enror dist B B*) I co = 0.2 is required. While such requirement can be ensured by the private power method (PPM, presented in Algorithm [ the utility guarantee only holds with constant probability, e.g. 0.99.
key contribution of our work is to propose cross-validation type scheme boost the success probability of PPM to 1 O(n +) with a small extra cost of Ok log n). Note that boosting the success probability has small cost of utility and hence we need a higher target accuracy e; = 0.0 for PPM compared
cu 0.2. The most important novelty of our selection scheme is that only takes as input the results of O log n) independent PPM runs, which hence can be treated as post-pro post-processing and is free of privacy leakage.
F.1 UTILITY AND PRIVACY GUARANTEES OF THE PPM PROCEDURE
In this section, we present the guarantees for the PPM procedure, under the additional assumption that Tiy are Gaussian variables. One can prove that the choice of Ço described in Lemma F.1 is a high probability upper bound of || (see Lemma G.1 in the appendix). Therefore, with the same high probability, the clipping operation in the Gaussian mechanism will not take effect.
Conditioned on the above event (clipping takes no effect), to establish the utility guarantee of Algo- specific instance of the perturbed power method presented in Algorithm 6 Suppose that the level of perturbation is sufficiently small, we can exploit the analysis from (Hardt & Price 2014) to prove the following lemma.
rithm 5 we view PPM Hardt & Price (2014)
Lemma F.1 (Utility Guarantee of a Single PPM Trial). Consider the LRL setting. Suppose that Assumptions 5.2 2and hold and æij are Gaussian variables. Let e = 0.01 be the target accuracy.
For PPM presented in Algorithm 5 set Ço do12211.5 s logn (Vlog n + Vk), L = en (s) + Σ/=1 /3)/ log(kd/Ea). Suppose that is sufficiently large so that there exists my such that
log" 6 min 2 cq d log d 1. 122
mn
E
(66)
8k
2
Choose a noise multiplier au Co L. We have with probability least 0.99, we have dist B B²) S Es.
Remark F.1. If we focus on the dependence on the problem dimension and the number clients n, treat other quantities, e.g. the rank k; as constant, and ignore the logarithmic terms, have i 2 (d/n), which is the same as the requirement on m. in Lemma C.5
The following RDP guarantee of PPM can be established using the Gaussian mechanism of RDP and the RDP composition lemma.
Lemma F.2 (Privacy Guarantee). Consider PPM presented in Algorithm 5 Set inputs L., the number of communication rounds, og, the noise multiplier according to Lemmal (a, -DDP mechanism with
We have that PPM is an
aL (c&Sok 2)2 = =Ō = n2st
anak 27
'nit
(67)
n²
where Ô hides the constants and the log terms and we treat (o? + Eje (5-18))/88 33/
F.2 BOOST THE SUCCESS PROBABILITY WITH CROSS- VOLIAAAN
The following lemma shows that if the output of PPM has utility at least 6,, e.g. = 0.01, with probability p, e.g. p- 0.99, then any candidate that passes the test (68) has utility no less than 6p.
e.g. = 0.2, with a high probability (1 -)) 8). The proof is provided in Appendix H
'The choice of e should satisfy equation 69 e, 01.01 is valid example.
28

---

Published as a conference paper at ICLR 2023
Algorithm 5 PPM: Private Power Method (Adapted from Hardt & Price (2014)
1: procedure PPM(L, on, So. sito)
2: Choose X E Rdxk to be a random column orthonormal matrix;
3:
for [ = 1 L do
4:
for i = 1 to do
5:
Sample without replacement subset s from S, with cardinality mo- Denote M + Ejesto 1z
6:
7:
Compute Y == X
8:
Let X (Y where Y GMc (+)))
9:
// QR(-) denotes the QR decomposition and only returns the Q matrix.
Algorithm NPM: Noisy Power Method (Adapted from Hardt & Price (014
1: procedure NPM(A, L) I/ A is the target matrix
2:
3: Choose X E Rdxk to be a random column orthonormal matrix;
4: for I 1 L do
5:
Let X = QR(YY), where Y -x'-1 + G
6:
G is some perturbation matrix.
7:
I/ (R(()) denotes the QR decomposition and only returns the Q matrix.
Lemma F.3. Use en denote the accuracy required by CENTAUR in the LRL setting and use e; to denote the accuracy of single PPM trial. Recall that p 0.99 is the probability of success of PPM Use Bu,e to denote the output of PPM in the ch trial and set To 8p 8p 1/8 in the procedure INTTIALIZAIIN (Algorithm(3) 3). We have with probability at least 1 - 5 that there exists one element in (1.....Tr, Tob such that for least half of E (T....,To).
(. Bo,E) 2 1 - 2c, Vi E [k]. s; (B
(68)
Moreover, Bo, must satisfy dist B B)) S co with a sufficiently small e, E [0, 1] such that
2 + v 11- e + + 26
(69)
One valid example e; = 0.01 and = 0.2, which is the one chosen in previous discussions. Corollary F.1. Consider the INITIALIZATION procedure presented in Algorithm | By setting To = log log n,, E, 0.01, and setting Lo. do and Ço according to Lemma F.1 we have with probability at least - n the output Bg satisfies dist Ba, B²) S 6n 0.2. Moreover the INITIALIZATION procedure is an (ar, RDD mechanism with
Cnii To Ō akk 2k2k2 1
Cinit
(70)
n²
The idea of boosting the success probability is inspired by Algorithm 5 of (Liang et al. 2014). The major improvement requires access to the dataset and hence can be treated postprocessing, while (Liang et al. 2014) requires an extra data-dependent SVD operation which violates the purpose of DP protection in the first place.
our approach is that given the outputs of O log PPM trials, no long
G GUARANTEES FOR THE PPM PROCEDURE
In this section, we present the analysis to establish the guarantees for the PPM procedure. We first show that the choice of So described in Lemma F.1 is a high probability upper bound of ||Y:'|| F. Therefore, with the same high probability, the clipping operation in the Gaussian mechanism will not take effect.
Lemma G.I. Consider the LRL setting, Under the assumptions 5.2 and 5.7 bility at least 3mn 100
we have with proba-
|1/l|e I| & 2 2 (log ()oog))((/oog) Togn + (8)g Vi)
29

---

Published as a conference paper at ICLR 2023
where Y is computed in line of Algorithm 5 and co is some universal constant.
Proof. The detailed expression of Y in line of Algorithm
can be calculated as follows:
Y M m
Σ JES
Vi C X
(71)
Using the triangle inequality of the matrix norm, is high probability upper bound of || the following inequality holds with a high probability,
I aayar.y X
||=
|uny | || m. X S Co-
(72)
To bound |ysyl recall that in Assumption 5.1 we assume that Zij a sub-Gaussian random vector with | Il 1. Using the definition of a Suub-Gaussian random vector, have
P( 2 7} - 2 22ep((cc,_)11e_ (13) 2
n).
(73)
with the choice pvksk v (100 log + log 2)/c, since ||w, ll S wVKss. Here C2 some constant and recall that 8 shorthand for s (WW/VvV /vn).
To bound |æ ||. recall that Eiy a sub-Gaussian random vector with |وام|los = and therefore with probability at least 6,
| < 4v + 2 log 8
(74)
Therefore by taking d exp(-100 n),, we have that 4 4vd + 2 log 4vd + 2,/00 log Sa.
To bound | |,o]]x[-_ x note that due to the rotational invariance of the Gaussian random vector Zij (recall that x is an column orthonormal matrix), the l norm |=x,|x/-- is distributed like the lg norm a Gaussian random vector drawn from (o0 It). Therefore, w.p. at least - n -100 ||xT]xx--1 X I c(VT= + /logn)-G
Using the union bound and the fact that C2955 S Ço leads to the conclusion.
Conditioned on the above event (clipping takes no effect), to establish the utility guarantee of Algorithm 5 we view PPM as a specific instance of the noisy power method (NPM) presented in Algorithm Hardt & Price (2014), where the target matrix A (2r + trace(T)Aa) with
I = V V B and the perturbation matrix G' P' + P is the sum of the noise matrix added by the Gaussian mechanism, P One can easily check that with these choices, we recover line 8 of Algorithm
W and the error matrix p (M' (
-'I- G x ToCo W
Co w
M X
(75)
Suppose that the level of perturbation is sufficiently small, we can exploit the following analysis of NPM from (Hardt & Price 2014).
Theorem G.1 (Adapted from Corollary 1.1 of Hardt & Price (2014)). Consider the noisy power method (NPM) presented in Algorithm 6 Ler Raxs represent the top-k eigenvectors of the input matrix A E Rddd Suppose that the perturbation matrix G' satisfies for all I E {I....,L)
C
5||G'|| S (((ss(A) 84+1 (A), G²ll (sa(A) 84+ (A))
(76)
TVkd
for some fixed parameter T and < 1/2. Then with all but 1/T + e ((() probability, there exists an L = O (c(A)) log bog(kdr/c)) so that after L steps we have that [| x__x,,X'3 x--xxXX)UU Sc.
(A(
Here C > 0 is constant defined in Lemma 1.3
30

---

Published as a conference paper at ICLR 2023
To prove that the perturbation matrix G' satisfies the conditions required by the above theorem, bound M' - A and CoSa W individually, both with high probabilities.
Proof of Lemma F.1 Recall that A = 21 + (race(L')) and note that rank(T) = k and that its singular values are sf....,.sf S Therefore s; (A) = 2s + E)= sÿ for i S ls and s, (;()) = Σ プソ 1=1 $j for i > k.
In this proof, will show that for both matrices Pf (M' A)x and P following inequalities hold for all / E {I,..., L), which is a sufficient condition for Lemma G.1 to hold
مجCa W the
C
10 P'l = (A) Sx+1(A)), 10 P'Il S (sx(A) Sk+1(A)) rvkd
(77)
Control terms related to Pl. 1. We first bound P| By the independence between M' and X we have that
E (M' A)X* M A E X
To bound the norm term E [I[(M* A)I we begin by controlling the norms of Ziy- X where Zi
u.... By the proof for Lemma G.1 with a probability at
least - 6, we have that || Z/j X--11| - o ((vá + log 1/6) (Vl + log 1/6) || I?)
O ((vă + log 1/6) (vT + log (8))kkkfk since || S ju bound on the matrix variance term
We then compute an upper
E
1| S |E Ui || (2 x TE
m. x X|1 || 2
(78)
[|
4 Mig
||
x X
(79)
Due to isotropy of the Gaussian, by (Tripuraneni et al. 2021 Lemma 5), we have that
E
|, | ((2d + e (3d + 15)
(80)
By plugging equation 80 into equation 79 prove the following inequality.
|| (Z')x1-11T
S || + 75) TeieT x + (3d + 1x)
(81)
<(d|w < (d ks
(82)
By combining both the norm bound and the matrix variance bound and using the modified Bernstein matrix incquality (Tripuraneni et al. 2021 Lemma 31), we have
IIM - 1|X < log mn log d. o (1 dpekot
Ei= of
vkdypkis
(83)
mi
mn
2. We then proceed to bound the term IU Pill 10T (M' A)X By using proof of Lemma G.I we first bound the norms of IIU - < O((Vk + log 1/0) +
log p/8)p²ks where Z = v. We then compute an upper bound on the matrix vari- ance term.
[U Z x
U - < E [
(UTTA
(U
T. x x'-1)TTT
T.yoT X X|II||
(84)
= -1(X"~1)
M U Lisll
Paaaeee x x"1111
(85)
=I((X-1)TE
(w)) B T
"i I æ; 11 aa
x x!-11|
(86)
=I((X-1)TE
(w) T T x. 1 Byy Pojay
x!-111
(87)
31

---

Published as a conference paper at ICLR 2023
where the last equality is because by definition, have B* U. We now perform variable trans- formation and denote Day = V Zij where V [U, based on U. Therefore, equivalently write the above equation 87 to the following inequality.
U*] is an orthogonal matrix that is extended
(U TE (w) T (vi) ... Uy 1 ( Σ
Z "II
(88)
x T
V x
(89)
where Biyla] means the a-th coordinate of the k-dimensional vector Vij, which is also distributed as Gaussian. Due to the isotropy of the Gaussian it suffices to compute the expectation assuming
wo x l|w;lle where (1, 0,...... ,0) Then following the proof for (Tripuraneni et al. 2021
Lemma 5), by combinatorics, we have the following equation.
B[(w; T (err[4),
... (b
Diy payla)) 0iy 1.
(
(90)
= -||w;|| (wy (w,,(1))*
Diy [a|
u.
(91)
o=1
Therefore, by plugging the above equation into equation
89
we prove the following inequality.
I] < Okk|lo < Okp ksg
(92)
By combining both the norm bound and the above matrix variance bound and using the matrix Bernstein inequality (Tripuraneni et al. 2021 Lemma 31), we have
k2p2 k Σ of
p
I (M' AIX' s log" mn log d-
(93)
mnn
17A1I
Therefore, to ensure that equation holds, it suffices to use min sufficiently large such that
(1 dupket E
o²
/kdjkkst mn
log mmn log² d. O
(((s(A) (8+1(A))
(94)
mn
1:21225 k
1.2
Σ i== s
12 mn
C
log" mn log d.O
< (sx(A) sk+I(A))
(95)
mn
TVkd
dp Ete
vkdu ke and ca 2 1/TVkd. The above inequali-
For simplicity, assume that ties can be simplified as follows, with e₁ being some constant.
mn
d. log d 33
112
Σ+
-1=1 $
logo
6 mn
C1
ot
(96)
Control terms related to P/. Recall that P ~ NN o2yax with JoLo/n. Using Lemma I.2 we have with probability 1
maxie[4]
| S CvolVV++ vD + Vn x));
maxietu | P C2 (2( +x)).
Consequently, we can obtain bound the terms related to P/ by setting ou sufficiently small such that the following inequalities hold with x 100 log
10CwolVd Vi Vln(2L x)) < c. 12C vn((2+ +)) s / (rVdk).
32

---

Published as a conference paper at ICLR 2023
To simplify the above inequalities, suppose that ea is a constant and neglect the log log terms. We obtain
C20uCo
(97)
Tk do
for some constant C2.
Having established equation 77 for both Pf and Pa we can then use Lemma G.1 I to obtain the target result.
H PROOF OF LEMMA H3
Proof. In the following, first show that 1. the index è exists with high probability and we then show that 2. any candidate Bg that passes the test equation 68 has utility no less than b, i.c. dist(Be Bg, B") S
Existence of Suppose that both Bar and Beg are successful, i.c. dist Be. B*) S a for i = 1,2 or equivalently Smin Compute that
B*) 2 v1 - a² for = 1.2. Recall that B* + B B Id-
8min
[ Boz)
B (B' B" B + BB
Smin
Smin B'B Bo,) smax B BiB Bey)
19 Smin
B B²)smi (B* Be,)) Smax [ B mmax (B
Be,)21 202
(98)
Define the binomial random variable X 1B, is succesfull
We have that E[Xe]
P(B, is successful} 2 p.
Using the concentration of the binomial random variable, we have
To
P
X. S To B[X.] +) s exp(-
(99)
Therefore, with the choice t 2 and To 2 8p log 1/6, we have with probability least 1 6, at least half of the outputs of To independent NPM runs are successful. Consequently, there exists at least To/2 2 pairs of Be, and Ba, such that Eq. equation 98 holds, which shows the existence of à.
Utility of Ba We now show that the candidate B, that passes the test Eq. equation 68 must satisfy We prove via contradiction. Suppose that there exists a candidate B that passes the test, but with dist B, B*) > b. This means that there exists á RR and ú E R* with || ||ا l2 = achieving the minimum singular value of B B", such that (Bá, B* S - E2
dist(B, B*) S
Let B, be a successful candidate, i.e. dist (ist B*) S a (note that with a high probability they are in the majority according to the discussion above). We have
B B;) = smin B B + Bi 7) B,) S Smin ( BBBB B,) + Smax B B B,).
Smin
1.a S a To bound the first term, recall the variational formulation of the minimum singular value Smin (A) Ay and hence
For the second term, we have Smax BB B"
T TB,) Smax BB Smax B B,)
min = ---lll=1 =1 x
B BBB'B T B,) S B
B B = T B B B B
B B
8mi
S V - & B B
-1 12 + I - B
+1 11-1-------------------
where we recall the definitions of i and ÿ in the above paragraph. Combining the above bounds, we obtain Smin [BT B₂) < V1- + /1 a² + a which strictly smaller than - 2a² for a sufficiently small and sufficiently large b. e.g.
0.01 and b 0.2. To put it in other words, we obtain that B will fail test (68). This leads to a contradiction and hence we have proved that any candidate that passes the test 68) must satisfy dist (B,, B²) b.
33

---

Published as a conference paper at ICLR 2023
1 PRELIMINARY ON MATRIX CONCENTRATION INEQUALITIES
Lemma I.1 (Theorem 4.4.5 in Vershynin (018 Let GI...... GG ~ N(O, 02) 0d)dxn There exists
constant Cy such that with probability at least e
max [e
Grll S Cya vd+ V (21(22++
(100)
Lemma 1.2 (Lemma A.2 Hardt & Price 2014)). Let U E Rdxx be matrix with orthonormal
columns. Let Gt....,
......,Gr. GL (0, ga)upp with 0 S p S d. There exists a constant Cy such that
with probability at least 1 - E
max U0 Gill CNo(2VP + Vln(2L + 2)). L
(101)
Lemma I.3 (Minimum Singular Value of a Square Gaussian Matrix (Theorem 1.2 of Rudelson & Vershynin (2008)) )). Let A R be Gaussian random matrix, i.e. Aij A/00, 1). Then, for
every 0, we have
Pr(Smin S c Cc Cc.
(102)
where and c E 10, are absolute constants.
J AN ELABORATED DISCUSSION ON THE UTILITY-PRIVACY TRADEOFF IN COROLLARY 5.1
Consider the result stated in Corollary 5.1
Suppose that the left hand side 2 p/d/ is fixed, then for a target accuracy ca. we cannol establish the theoretical guarantee that CENTAUR achieves the accuracy <a within a DP budget of < Eund""-ydd (this is natural since smaller DP budget edp requires a larger noise multiplier og which jeopardizes the convergence analysis of CENTAUR). However, need to emphasize that, budget Edp is achieved, since the privacy guarantee that we are establishing is just an upper bound. Hence we not establishing a lower bound.
not ruling out the possibility that such DP
Now suppose that all factors other than the number of clients n is fixed. Corollary 5.1 implics that for an n that sufficiently large, i.c. n 2 "xid" we can establish the guarantee that the output of CENTAUR achieves an Ca utility within an cdp budget. This interpretation also allows us understand the benefit of having a better dependence on d: A better dependence on d means that a smaller n is sufficient to achieve the same utility- privacy guarantee.
K DISCUSSION ON THE REQUIRED ASSUMPTIONS
In this section, we show that the requirements we made Assumption 5.1
5.3 are similar the
assumptions made in (Collins et al. 2021) and (Jain et al. 2021
the same as Assumption 1 in (Collins et al. 2021). and is similar to point (i) of Assumption 4.1 in (Jain et al. 2021) where Zij is assumed to be exactly Gaussian.
Discussion on Assumption 5.1 We note that our Assumption 5.1
Discussion on Assumption 5.2 We note that our Assumption 5.2 is the same as the definition of the
incoherence parameter y in (Jain al. 2021) (the parameter X therein equivalent to of in our
paper), and is similar to Assumption 3 (Collins et al. 2021 where the incoherence parameter
as well as σ is assumed to be 1.
Discussion Assumption 5.3 We focus on the dependence on the parameters d and while treat- ing log terms and the other parameters like the rank & and the incoherence parameter as constants. In this case, Assumption 5.3 can be simplified as
R(d/n). We note that, under this setting Assumption is the same as the requirement (12) in (Collins et al., (02T) and Lemma 4.6 in (Jain)
al. 2021) The equivalence to the requirement (12) in (Collins et al. 2021) is straight forward.
34

---

Published as a conference paper at ICLR 2023
To see the equivalence to Lemma 4.6 in Jain al. 2021 note that in order for the convergence analysis of the main procedure to hold, the initializer U iins in (Jain et al. 2021) should satisfy
||U Unini | (1). To achieve this, the R.H.S. of Lemma 4.6 in JJin et al. 2021 should be bounded by a constant, which means that m = Q(d/n).
35


Reviews:
[{"review_id": "q0mtvGZxY7", "reviewer": "Reviewer_Usxb", "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": "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.", "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. \n\n\\-----\n\nAfter 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.", "strength_and_weaknesses": "Major strengths: \n1. This idea is intuitive and the empirical performance is very good.\n2. The theoretical statements are very detailed.\n\nMajor weaknesses: \n1. 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.\n2. 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.\n3. In the experiments, the authors said 'we do not perform any data augmentation, as we observe that naive data augmentation\nfor 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\nper-example gradients across multiple augmentations of the same image before the clipping operation\n(Hoffer et al., 2019) ...' This needs further explanations.\n\nMinor weaknesses:\nThe writing can be improved. There are many cases that one notation is used before it is introduced. For example,\n1. The first paragraph of Page 7 refers to Algorithm 3 which has $s_i$ but it is introduced in Section 5.1. \n2. 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$. \n3. On Page 7, the authors said 'line 5 in Algorithm 4 uses Gaussian mechanism' twice, but this is not shown in the algorithm.\n\nOn page 16, there is a missing remark. Similar in Remark F.1.\n\nOn 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.\n\nThe proof for Lemma D.4 and Lemma F.1 is missing.\n\n\n\nSome typos:\n1. Page 5, Algorithm 1, Line 4, I guess $p_c$ should be $p_g$.\n2. Page 6, Remark 4.1, $S_\\alpha(p_c, \\sigma_g)=\\ldots$ needs to be corrected.\n3. Page 10, references, there are duplicates for 'Durmus Alp Emre Acar, et al. (2020, 2021)'.\n4. Appendix A.4, the sensitivity is $2\\zeta_g/n$.\n5. 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.\n6. 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$\n7. Appendix Eq (42), I guess $F_t$ is $F^t$.\n8. On page 24, the first line in Section E.2, I think $I_k$ is $I_d$.\n9. On page 26, the second last line, Hardt & Price (2014) does not have Algorithm 6.\n\n----------------------------\nUpdate: 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.\n1. 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. \n2. 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.\n3. 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.\n\n---\nUpdate-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. \n\nI 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.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Nv4SjvlqFdm", "reviewer": "Reviewer_4btx", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "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.", "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.", "strength_and_weaknesses": "Strengths:\n- The idea of separately training representation and classification heads is intuitively nice. \n- 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.\n- Theoretical results demonstrate significant improvement for linear networks.\n\n\nWeakness:\n- The experiment results would be more convincing if more experiments on done on larger datasets like ImageNet.\n- 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?\n\n\n=== Update ===\n\nAfter 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.\n\n=== Update ===\nThe 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. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "GfGHQY91vg", "reviewer": "Reviewer_CCKF", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "The paper considers the (federated) private model personalization problem, and provides a utility guarantee in the bilinear case.\nThe 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$.", "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).", "strength_and_weaknesses": "## Strengths\n- The presentation is crisp.\n- The $O(\\sqrt d)$ improvement upon the method of Jain et al. is interesting (though the comparison may not be fair).\n- The empirical results are promising.\n\n## Weaknesses\n\nMy 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.\n\nThe 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.\n\nThe contribution of the paper is much more narrow than what the paper claims:\n1) 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).\n2) Good empirical results on CIFAR and EMNIST.\n\nI 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.\n\nOn the technical side: the statement of results lacks rigor at times.\n- The privacy guarantee should be stated more carefully. The rigorous guarantee should use the joint-(R)DP notion.\n- 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.\n- 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.\n\n#### Experiments:\nThe experimental results are promising. I have a few questions/suggestions:\n- 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.\n- 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?\n\n\n==== Post-discussion update ====\nThe 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.\nOther improvements have been made, including discussions about the technical assumptions, and empirical support for the claims made in remark 3.1.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "1jowgbYT3jk", "reviewer": "Reviewer_hVPm", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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": "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. ", "summary_of_the_review": "The paper makes progress for the problem model personalization under user level differential privacy and federated learning constraints. ", "strength_and_weaknesses": "Strengths:\n\n- The paper provides a substantial rate improvement over existing work for the problem of LRL\n- The paper provides sound empirical reasoning for their method (i.e. that data representations are less prone to distribution shift)\n- The paper supports its results empirically\n\nWeakness:\n- 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.\n- The proposed algorithm is not incredibly novel compared to prior work. \n- 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.\n- Given the rate improvement, an investigation into what DP lower bounds suggest is necessary would be nice.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster