Private Model Personalization Revisited
Authors: Conor Snedeker
Xinyu Zhou
Raef Bassily
Venue: ICML 2025 poster (2025)
Keywords: Differential Privacy
Model Personalization
Federated/Multi-task Learning
Representation Learning
Statistical Heterogeneity
Primary area: social_aspects->privacy
TL;DR: We propose model personalization algorithms under user-level differential privacy via shared representation learning.

Abstract: We study model personalization  under user-level differential privacy (DP) in the shared representation framework. In this problem, there are $n$ users whose data is statistically heterogeneous, and their optimal parameters share an unknown embedding $U^* \in\mathbb{R}^{d\times k}$ that maps the user parameters in $\mathbb{R}^d$ to low-dimensional representations in $\mathbb{R}^k$, where $k\ll d$. Our goal is to privately recover the shared embedding and the local low-dimensional representations with small excess risk in the federated setting.  We propose a private, efficient federated learning algorithm to learn the shared embedding based on the FedRep algorithm in  (Collins et al.,
2021). Unlike  (Collins et al., 2021), our algorithm satisfies differential privacy, and our results hold for the case of noisy labels. In contrast to prior work on private model personalization (Jain et al., 2021), our utility guarantees hold under a larger class of users' distributions (sub-Gaussian instead of Gaussian distributions). Additionally, in natural parameter regimes, we improve the privacy error term in (Jain
et al., 2021) by a factor of $\widetilde{O}(dk)$. Next, we consider the binary classification setting. We  present an information-theoretic construction to privately learn the shared embedding and derive a  margin-based accuracy guarantee that is independent of $d$. Our method utilizes the Johnson-Lindenstrauss transform to reduce the effective dimensions of the shared embedding and the users' data. This result shows that dimension-independent risk bounds are possible in this setting under a margin loss.

Private Model Personalization Revisited
Conor Snedeker"
Xinyu Zhou
Raef Bassily?
Abstract
1
Introduction
The rapid advances in machine learning have revolution- ized domains such as healthcare, finance, and personalized services. However, this progress relies heavily on the avail- ability of user data, which presents two critical challenges. First, user data is often statistically heterogeneous, that is, individual users have distinct data distributions. This het- erogeneity hinders the training of single global model that performs well for all users. Second, the reliance on sensitive user data raises significant privacy concerns, necessitating robust mechanisms that offer strong privacy protections.
We study model personalization under user-level differential privacy (DP) in the shared representa- tion framework. In this problem, there are n users whose data statistically heterogeneous, and their optimal parameters share an unknown embedding U E Rd that maps the user parameters in dd to lwwdiimeniional representations in iR where k < d. Our goal is to privately recover the shared embedding and the local low-dimensional repre- sentations with small excess risk in the federated setting. We propose a private, efficient federated learning algorithm learn the shared embedding based on the FedRep algorithm in (Collins et al., 2021). Unlike (Collins et al., 2021), our algo- rithm satisfies differential privacy, and our results hold for the case of noisy labels. In contrast to prior work on private model personalization (Jain et al., 2021), ) our utility guarantees hold under a larger class of users' distributions Asub-Gaussiin instead of Gaussian distributions). Additionally, in natural parameter regimes, we improve the pri- vacy error term in (Jain et al., 2021) by factor of Ö(dk). Next, we consider the binary classifica- tion setting. We present an information-theoretee construction to privately learn the shared embed- ding and derive a margin-baac based accuracy guaran- tee that is independent of d. Our method utilizes transform to reduce the effective dimensions of the shared embed- ding and the users' data. This result shows that dimension-indepeeddent risk bounds are possible in this setting under a margin loss.
Model personalization has emerged as key strategy to ad- dress the challenge of statistical heterogeneity by adapting models to individual users, rather than relying on a single global model that may perform suboptimally across diverse data distributions. A widely used framework for personal- ization is shared representation learning, where users collab- orate learn a low-dimensional embedding that captures commonalities in their tasks. This shared embedding allows users train their local models more efficiently, leveraging the embedding to complement their unique data.
However, despite its effectiveness in handling heterogeneity, model personalization introduces additional privacy con- cerns, as learning shared representations involves user col- laboration, which can inadvertently expose sensitive infor- mation. Ensuring rigorous privacy protections in this setting requires formal guarantees, such as user-level differential privacy (DP) (Dwork et al., 2006), which prevents adver- saries from inferring an individual's presence in the training dataset based on the trained model. Existing approaches to private model personalization suffer from limitations such as restrictive assumptions about data distributions, central- ized processing requirements, and suboptimal privacy-utility tradc-offs.
the
In this work, we study model personalization under user- level differential privacy via shared representation learn- ing. In this problem, there are n users, where user i E [n] is associated with data distribution D; and a dataset S. (21.... 2m) D. The optimal parameter of user is denoted w Rdd We aim at learning a shared low-dimensional embedding U* E Baxk, where A < d, and user-specific parameters ......, S E R² such that : = U" u. for cach user i E [nz]. under user-level DP. We
'qqual contribution 'Department of Computer Science Engi- neering, The Ohio State University 'Department of Computer Science & Engineering and the Translational Data Analytics Institute (TDAI), The Ohio State University. Correspondence to: Conor Snedeker <snedeker.31 @ buukeyemail.osu.coer Xinyu Zhou <zhou.3542 @eroou3552@bucccccc wwwcccyymail.oou..coom
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Private Model Personalization Revisited
propose novel private federated algorithm for model per- sonalization via shared representation that achieves superior privacy-utility trade-off under relaxed assumptions. Our contributions are summarized as follows:
duce the effective dimensionality of the embedding space. This leads to margin-based risk bound independent of the input dimension d. This result holds for arbitrary distribu- tions where the feature vectors are bounded in the Euclidean norm.
1.1 Contributions
1.2 Related Work
Efficient private federated algorithm for regression: We extend the FedRep algorithm of (Collins et al., 2021) to ensure user-level DP while addressing the case of noisy labels in statistically heterogeneous user data. The algo- rithm is iterative, where in each iteration t, it alternates between local updates by the users to their local vectors "1,t.-.... Vn,t R and private aggregated gradient update to the shared embedding U,_ E [gd Previous work (Jain et al., 2021) required performing exact minimization with re- spect to both the local vectors and the shared embedding in a centralized manner. Since the embedding update in (Jain et al., 2021) involves a minimization over data from all the users. transforming their algorithm to federated algorithm is not directly feasible. Meanwhile, ours is naturally feder- ated algorithm since the gradient is computed by each user locally, which the server privately aggregates. In natural pa- rameter regimes, we show that our algorithm attains excess k where minn, is k-th largest singular value of /n V*. Compared to (Jain et al., 2021), under the same parameter regimes, this reduces the privacy error term by factor of Ö(dk)).
Our work builds on and extends several lines of research in federated learning, model personalization, and differential privacy:
Federated personalization via shared representations: Shared representation learning has proven effective in ad- dressing user heterogeneity (Collins et al., 2021; Jain et al., 2021). Additionally, centralized subspace recovery methods (Tripuraneni et al., 2021: Duchi et al., 2022) may be used to provide a good initialization for the shared representation for better federated personalization guarantees. While prior work focuses on non-private or centralized settings, our ap- proach incorporates user-level DP in a federated framework and achieves better utility guarantees.
Differentially private model personalization: (Jain et al., 2021) introduced a private algorithm for model personal- ization with centralized processing and restrictive Gaussian assumptions. Our method improves excess risk guarantees and extends applicability to sub- Gaussian data distributions. There are other prior works studying private model person- alization like (Bietti al., 2022: Hu et al., 2021), but these works are not under the representation learning framework and their results are not comparable to ours.
population risk of Ō n
d&
min.
nmo
Robustness to broader data distributions: Unlike prior work (Jain et al., 2021) that assumes Gaussian data, the util- ity guarantees of our private federated algorithm apply to a broader class of sub- Gausssssian distributions. Moreover, our results apply statistically heterogeneous users in the sense that individual users may have distinct Sab-Gaussian distri- butions, while the work of (Jain et al., 2021) assumes that the features of all the users are standard Gaussian. Moreover, we extend the results of (Collins et al., 2021) not only to the private case but also to the non-realizable case of noisy labels.
Optimization methods for representation learning: Rele- vant optimization techniques include alternating exact min- imization frameworks (Thekumparampil et al., 2021) and gradient-based optimization, which has also been widely used for personalization (c.g., (Collins et al., 2021; Raghu et al., 2019; Lee et al., 2019; Tian et al., 2020)). Our al- ternating minimization framework adapts these gradient techniques to a privacy-preserving federated setting with noisy labels.
Improved initialization under privacy constraints: We introduce private initialization algorithm for our feder- ated algorithm. Our initialization algorithm is based on the subspace recovery approach of (Duchi et al., 2022). Our algorithm leverages a top-k singular value decomposition (SVD) with added Gaussian noise. This ensures a feasible starting point for the shared embedding, even under relaxed data assumptions.
Dimensionality reduction with DP guarantees: The use of the has been explored in recent work (e.g.. (Lê Nguyen et al., 2020; Bassily et al., 2022; Arora et al., 2022)). We adapt this technique for federated personalization, deriving margin- based risk guarantees independent of the data dimension d.
transform in private learning
2 Preliminaries
Dimension-independdee independent risk guarantees for classifica- tion: We provide an information -hhooreticteeecccccco construction for the binary classification setting under the margin loss and derive an risk bound that benefits from margin guarantees. We incorporate the Johnson Johnson-L.nndenstaane Lindenstrasss transform to re-
We consider a setting of users, where each user i E [n] is associated with distribution D; observed by a dataset S: (111,8),.. (Im, Bm))) ~ D where x; E gd and E R. Given a low dimensional embedding matrix U E Rdxk
2

---

Private Model Porsonalization Revisited
with orthonormal columns and local vector v E R the loss incurred by the parameter (U, o) over data point (s, y) is defined &(U, v, (z, v)) = (v (xz, Ut)). Suppose k < d. It is useful conceptually to think of the matrix U as a transformation x + U x that maps x E Rd onto the low-dimensional space IR* In addition, we assume that < m. This assumption is necessary to attain useful utility guarantees as in prior work (Jain al., 2018).
Note that we can instantiate the matrix M1 with laxd Mj M, This is used many times in our analysis. We show how to bound the excess risk with the principal angle in Lemma 35 in Appendix B.
Definition 3 (User-level Differential Privacy (Dwork et al., 2006)). A randomized algorithum A is (e, 8) ---user-level dif- ferentially private (user-level DP) if for any pair of neigh- boring collections of datasets S, E Rum(d+1) differing in a single user dataset and any event in the ouiput range of A, we have
Given collection of data sets S (S1,..., S,)) E Ram((+11, embedding matrix U E Rdd and collection of local vectors V = [[l..... average empirical risk of (U, V) over S as
E Ruxk, we write the
IP P[A(S) EJ S| E B)
Billboard Model. In this paper, we adopt the billboard model of differential privacy (Hsu et al., 2014; Kearns et al., 2014). In this model, there are n users and a central com- puting server. The server first runs a differentially private algorithm using the sensitive data from the users. The output of the algorithm is then broadcast to all users. Each user will independently train their own model using the broad- cast output and the user's own data. The results of these individual computations will be kept to each user and never shared with other users.
1 nm Σ Σ
E(U, ui (x.
(2.
We also define the average population loss of (U, V) over the data distributions D = (D), ) as
1 n Σ E (x,g),,, [e(U, us (2,1
(;D)
Given any (U*, V*) E Radk x Rank for U with orthonor- mal columns, our goal is to minimize the excess population risk w.r.t (U+, V*) defined as
Personalization via Representation Learning. We de- note the the optimal parameters of user as wf. and we assume all user parameters { {wi,... :......)) share a low dimen- sional embedding matrix U E Rxd with k < d such that w = U oz with a local vector wa E R for i E [n]. Given a dataset collection S = (S1..... S,,,, the goal is to privately find a shared low dimensional embedding matrix U E dxck and local vectors V = [e]] compared with U and V [uj..... "T]T_ Throughout this work, we assume U has orthonormal columns, hence the shared matrix U effectively maps d-dimensional fea- ture vectors E IRd to low-dimensional representations UT E R that ease local demands on each user. Given parameter spaces 2, V, the objective can be formulated as a minimization problem written as mingeu.vev L(U,V;;
E)U.V) L(U. D)
Let M E Bddk be any matrix. Recall our setting in which k < n. Denote the spectral norm of M with ||M la and its Frobenius norm with ||M] We denote by mmax and (M) the largest and k-th largest singular values of M, respectively. Further, suppose that Q E dd is a matrix with orthonormal columns and P E R an upper triangular matrix where QP M is the QR decomposi- tion of M. We take QR( -)) ) to be the function that maps M to (Q, P). Finally, given a subspace B, we denote its orthogonal subspace as B,
e,] with low excess risk
Definition 1. Let X E R be a random variable. We call X a centered R-sub-Gaussian if X satisfies E. [eAX] S x² R²
for all X E IR. Furthermore, we denote the distribution of
3 Private FedRep Algorithm
X as SG(R2).
In this section, we propose an efficient federated private model personalization algorithm based on the FedRep algo- rithm in (Collins et al., 2021) for regression problems. Our algorithm is based on an alternating minimization frame- work where the algorithm alternates between the updates of user local vectors and the shared embedding by first finding an empirical minimizer for each user, followed by comput- ing a gradient with respect the embedding. After we compute the private shared representation, each user will in- dependently solve for their user-specific local model, which will be kept to each user. We provide rigorous utility and privacy guarantees for our algorithm and give a detailed comparison with prior work.
We now introduce a quantity that is commonly used in ma- trix completion (Jain et al., 2013) and shared representation learning (Jain et al., 2021; Collins et al., 2021) as a measure of distance between subspaces of Rdd It is conceptually use- ful to think of this distance as measuring the dissimilarity of span and alignment between two subspaces.
Definition 2. We define the principal angle between the column spaces of matrices M1, M22 E Bdda via dist(Mr, M2) = MM where MT,,, are ma- trices with orthonormal columns that satisfy (p)n()))T1) span(M)) L and span(M2) = span(M2).
3

---

Private Model Personalization Revisited
We make several modifications to the original FedRep al- gorithms and its analysis. First, sample disjoint data batches in each iteration to update the local vectors and shared embedding separately while the original FedRep uses the same data batches for both. This use of disjoint data batches enables us to give a tighter bound on the Frobe- nius norm of the computed gradients, which turn reduces the amount of noise required for privacy preservation. More- over, we consider the setting of noisy labels, as opposed to the original FedRep analysis. Incorporating label noise introduces unique technical challenges into the analysis. Roughly speaking, without label noise, we can show the distance between the computed embedding with the ground truth decreases geometrically with high probability across iterations. However, such monotonic distance decrease is no longer guaranteed in the presence of label noise. Instead, we employ induction-basee based argument upper bound the distance.
is sub- Saub-iasssinn in the sense of [elowu) S e c= for all u E Rd.
1
Assumption 6. Lel SG(R) be any centered R-sub- Gaussian distribution over R. Sample ( SG(R). For all i E [n] and any data points (I, y) ~ Dj we generate the label y for the i-th user via y x U + S where Ç is independent for all x ~ Di
Unless stated otherwise, in this section, we assume that Assumptions 4, 5, and 6 hold. However, we note that our al- gorithms not require knowledge of Assumptions and 6.
3.2 Main Algorithm
Algorithm uses alternating minimization for convergence to an approximate minimizer of the excess population risk in parameters U E R with orthonormal columns and V E R simultaneously. At each iteration of the in- ner loop each user samples b data points without replace- ment from their data set S,. The users then split this sam- ple into disjoint batches BL,, B3,, for use in the comput- ing parameters in iteration t. Our inner loop uses par- allel execution at iteration to locally compute a mini- mizer UG, E arg min L(U,, v; Ba,)) and gradient Vi. = (v Up: Bi,,) for each user i. The server then aggregates clipped gradients (clip(V.... hem for its gradient step and then returns U241 to the users where dip(M,r7 r) and E TR.
Before we introduce the Private FedRep algorithm, we first give some definitions and assumptions that hold for the entire section.
3.1 Problem Setting and Assumptions
In this section, we focus on quadratic loss defined E(U, 0, (v, y)) (y- - (a, Uu))² for all U E mRdak o E R (z, v) E 1d411 Define I' = max,e[n]]lo]]] ll2. Denote
m = mmin Vn V+* and m = mmax (= respectively. In our setting, we assume that the rank of Vn L E Bank is k which implies min,, the k-th largest singular value of 1 V*, is greater than O. The values Vn
M 1
min
|MT P for any M E Rdx
Each iteration Algorithm ensures that U2+1 has orthonor- mal columns. Due to orthonormality, the noise injected during the aggregation of (Vi,))e(j)) does not affect the norm of Vi for each i, f. This lack of noise propagation, D having a covariance matrix Iaxd, and the use of disjoint batches BA, Bi,, ensure the following bound on the size of ViA-
T, ma and min, are important in this setting and ap- pear in our final bounds. We additionally define the condi- tion number to be y
Zmaxa
min..
The guarantees of our algorithm will rely on the following assumptions.
Lemma 7. With probability at least 1 - O(T nn- we have
Assumption 4 (Client Diversity). There are known A, > such that A 2 Tmax, 2 Omin, 2 X.
Vull S ( (
The assumption that Tmin. > is made explicitly or im- plicitly in prior work (Collins et al., 2021; Jain et al., 2021). Observe that Assumption 4 implies y I A X- In this sense, X is an estimate of the condition number 7.
for all E [n]] and all E [T] simultaneously.
We use Lemma to choose the clipping parameter & in Algorithm 1 in later results.
To make our analysis tractable, we will introduce some standard data assumptions similar to those invoked in prior works (Collins et al., 2021; Du et al., 2020; Jain al., 2021; Thekumparampil al., 2021; Tripuraneni al., 2021). Al- though we make these assumptions, our algorithm can be used for wider range of data sources than what is shown here.
Theorem 8. Algorithm I is (c, -user-lvvel DP in the bill- board model by setting = C /VTT log(1/8) for some abso- lute constant > O.
We define A,,8 = C. C for any e and 8 E [0,1]. 1].
For the following result, recall the definition of J and Assumption 4, where we assume there exists À > such that mmin, 2 X.
Assumption 5. Let i E [n] and x ~ D,. For all i E [n] the feature distribution DD has covariance matrix Taxa and
4

---

Private Model Porsonalization Revisited
Algorithm I Private FedRep for linear regression
Note that dist(Ug; U*) in the right-hand side of the bound in Lemma 9 is bounded from above by v c.
Require: S { 3t.1)..... (z Ht.m)) data for users E [ni, learning rate 7, iterations T, privacy noise parameters o, clipping parameters vi maa batch size b < [m/2T]], initial embedding Unn E [
Given Lemma 9, we may obtain our main excess population risk bound. Let Urei be the final shared embedding returned from Algorithm 1. The intuition behind this result that small principal angle between the two matrices U U* implies U approximates U* transformation R + R Our choice of ui arg min L(UPiv v; St) for S independent
Let 5 - [ Ma.) :j [m/2]] Vi E [r]
Let S + S; \ S Vi [n]]
1: Initialize: Un + Unit
2: for i. ...., T
do
Upei means w; = U of reliably transforms a fresh feature vector I ~ D. into a scalar x wy that close to the noisy label x of + when n, m are sufficiently large.
3: Server sends U, clients [x]]
4: for Clients E [na] in parallel do
5: Sample two disjoint batches B and Bi each of
size b, without replacement from 5
6: Update b/ as V4, < arg min T(U,, u; Be,) Compute the gradient w.r.t
Recall in Assumption 4 assume there exist A
such that A 2 Fmax, 2 m 2 X.
7:
Theorem 10. Suppose all conditions of Lemma 9 hold with 2A T= A
Vi + Vo U1,e Bi,))
( (A² #log(nn) and that Assumption 4 holds
X²
8: Send Vi, to server
as well. Then, Uni and Vpny the outputs of Algorithm 1, satisfy
9: end for
Server aggregates the client gradients
L(U
VarNe D) L(U",
(15
(R²
(R² (
Ütt1 U2 U2-1)
(res Eet1
n i=1
nr 1 min, A2
nmo! min, A²
ULt1: Po+11 + (R((++1)
R2K
where E++1 < (0,
1I: end for
with probability at least 1 - O(T n 10). Furthermore, Algorithm 1 is (e, ( 8)-user-leeel DP in the billboard model.
12: Server sends Upav + UT to all clients
13: for clients E [n] independently do
Note our results in Theorem 10 can also be extended to the case where new clients share the same embedding U This is formally presented in the following corollary.
Vi E [n] 14: o, < arg min LU ur 5
15: end for
16: Return: Upriv Vpav + priv
Un prie
Corollary 11. Suppose all conditions of Theorem 10 hold. Consider a new client with a dataset S,+1 ~ Dm where Assumptions and 6 hold with 11% S Т. Let UpiN be the output of Algorithm I and ,,dv Sn+1), if 2 kloommm We have arg min L(Uriv, ux
Lemma 9. Letr S max."
Suppose d-sist (Uo: U*) 2 c Set the clipping pa- (R+T)IVdk) Assume T =
for some constant rameter &b
log nA
amA? = δ min max/A. (R+T))d do
L(UPrV 1n11 (Dn+)) - L(U" 2 (h41;Dutt))
20
(R² + +T2
(R² + r
and Assump-
max,He 1) mmax (1
n min, A2
nmo min, X2 min,
tions and hold for all user data. Set & as in Theorem and batch size = ]m/2T]. Then, Upay, the first output of Algorithm 1, satisfies
R2 m'
Σ dist(U,, U*)
(1
c min.+
with probability at least 1 - O(T 11 + m00100).
dist(UUiiv UU (UTTTIN,U**++
4
Initialization. We require dist(U,, U*) in Lemma 9 to be bounded away from 1 otherwise the bound is trivial since the first term becomes 1 when c = 0. By definition of the principal angle (2), dist(Ug, U*) = when the column space of Ug and U are orthogonal. For now, we assume
+ (R+ (R+T)TUVKT
R2 + PTT
2 min,+
4 n min,*
with probability at least O(T 110)
5

---

Private Model Porsonalization Revisited
such a Up whose column space overlaps modestly with that of U in the sense of dist(Un, U*) < v1 c be found with reasonable effort. In the next subsection we give
achieve the same utility guarantee Theorem 10 without any assumptions dist(Uinia, U*).
Comparison with (Jain et al., 2021): Under conventional assumptions in prior work (Tripuraneni et al., 2021) to nor- malize V and (G) so that both and R are ()), the Priv-AltMin algorithm in (Jain et al., 2021) achieves an d²k²
efficient algorithm that guarantees such an initialization.
3.3 Private Initialization Algorithm
In this section, we introduce initialization algorithm for our private FedRep algorithm (Algorithm 1). Our initial- ization algorithm is based on the estimator in (Duchi et al., 2022) and the privacy guarantee is achieved by adding Gaus- sian noise to the estimator before using top-k-SVD. Our private initialization algorithm achieves the same conver- gence rate the one in (Jain al., 2021). But unlike (Jain et al., 2021), which is limited to i..dd standard Gaussian feature vectors, the guarantee for our algorithm holds in a broader class of sub-Gaussian feature vectors. The detailed steps of the algorithm are provided in Algorithm 2, while its privacy and utility guarantees are established in Lemma 12.
excess risk bound of Ō " win.e and miin.
d
for m
Gaussian data. Meanwhile, our Private FedRep algorithm
achieves a rate of δ n min, X
dRAA
dAa
A
win
X
When X (an upper bound the condition number of vn VT) is O(1), which is regime considered in (Jain et al., 2021) and assumed in (Collins et al., 2021), we improve the privacy enror term in (Jain et al., 2021) by a factor of O(d)).
More Ö min dkem
generally, in the regime
where n
V e eomm, X² our bound is
d'mA²
tighter than the bound of (Jain et al., 2021) by factor of
[dbx² A2 when A = =Ö(Vdk)). Meanwhile, in the regime
Algorithm 2 Private Initialization for Private FedRep
Require: St { Vi.1)........... (Zi,m/2 Hi,m/2)} data for users i [m], privacy parameters e, clipping
where n = ō 6 min
AA ko min,
X
bound Vhinits rank k
and Ω dkm ex
achieve bound tighter than that when n
1: Let Oinit / 2log
of (Jain et al., 2021) by factor of Ö (d À = Ō dk VT) Additionally, our work improves over that of (Jain et al., 2021) in two important respects. First, it requires less re- strictive data assumptions (sub-Gaussian instead of Gaus- sian feature vectors). Second, our algorithm can be naturally written federated algorithm while the algorithm in (Jain et al., 2021) requires centralized processing and transform- ing it to federated algorithm is infeasible.
ne
2: Let Sinit + --Adxd(0, (0, 2
3: for Clients E [n] in parallel do
4: Send Z4 m(m 1) En Vo
server
5: end for
6: Server aggregates Zi and add noise for privatization
n 2
Σ
(Z,, vmmaa) + Emi
n
3.4 Synthetic Data Experiment
7: Server computes
The results in Figure are obtained via data features from (0, Ia) with problem parameters = 20, 000, d = 50, k: = 2, and m = 10. Our data labels are generated as in Assumption 6 given label noise sampled from (N R²) with R = 0.01. We use local GD and non-private FedRep as baselines for our comparison. See Appendix B.4 for details!.
Uni ini + rank---SVD(22)
8: Return: Uni
Lemma 12. Suppose that Assumptions 5 and 6 hold. Let Unma be the output of Algorithm 2. Then, by setting thmi = Ō(1I2= 12))d,, we have
(R2 (R+
RR2 + (P++12rr2d
4 Margin-based Dimension Reduced Construction for Classification
fist 5Ō
neo2 min.*
mno min.
We now introduce our information-theerrtie guarantees for private representation learning for classification problem with margin loss. Our approach is based on the observation that learning a shared linear representation can be framed as
with probability at least 1 O(n-10). Furthermore, Algo- rithum 2 is () user-level DP.
By using Lemma 12 in conjunction with Theorem 10 and A² log( R2 a/k) we are able to
an iteration count T = θ
Note as well this Gubllb repository with copy of our code.
X²
6

---

Private Model Personalization Revisited
Rdd x [-1,1] any data point. We define the margin loss as (, v2 [v(r, Uo) S and denote the 0-1 loss ((U,v,2) ((U,t,))= =o(U,,,z) = 1 [y(2, Uv) - O).
2,00
1.75
1.50
Let U E,, RR* and 5' = (z...., , 2m)) 2mh We de- fine [,, v; S') Eÿ= (U, v,2, for any U, V. Suppose V [ui,-.., [n]] E V and let 5 = (Si...., be a sequence of datasets S. E z for all E [n]. We further define (U, V) = +o4 Ei= (U, ey; St) for all U,V,S. Our goal is to privately optimize the population loss L(U, V) = A - Ezz,D, [L(U, v1, 2,)] over U, V with personalization of V. We accomplish this via an ap- plication of the exponential mechanism over cover of a dimension-reduced version of
Eopuation NSE
1.25
Local optimization
1.00
Non-privae Redftep
Padifipg ir AltMin
0.75
0.25
Usenlevel Epsilon
Figure 1: Graph of population MSE over choice of privacy parameter [1, 8] for synthetic data comparing Algo- rithm I to Priv-AltMin in (Jain et al., 2021).
Definition 14. Let G C IRd be any of vectors. Fix B E (0, 1). We call the random matrix M E B (t, J.-.ohhnoon-iinddesrrass (JL) transform for any u, w E G
training a 2- 2-layer linear neural network, enabling the use of (JI.) transform (Johnson, 1984) for dimensionality reduction.
KMu, Mu') - (u, w²)l S / ///u||2a|uu||
the
with probability at least over M.
We demonstrate this utility guarantee as follows. First, we introduce the assumptions and definitions that hold for this section. This includes the definition for the Johnson- Lindenstrauss transform along with randomized instan- tiation. Subsequently, we describe the score function and covering argument required to combine dimension reduc- tion with the exponential mechanism. We then introduce Algorithm 3 that exploits the margin loss to attain our main result of the section, Theorem 17. Finally, we discuss the relevance of the main result and its independence from the data dimension d.
The JL transform is a popular and efficient method of dimension reduction whose existence is ensured by the Johnson-Lindenstraaus lemma (Johnson, 1984; Nelson, 2020; Woodruff et al., 2014). Via a JL transform M we are able to preprocess a feature vector x into a low-dimensional vector Ma E RRK for use in our federated learning problem. This preprocessing showcased in Algorithm 3 effectively reduces the dimension of our learning problem.
Lemma 15. (Bassily et al., 2022) Let T, E (0. Take
G Fd to be any set of t vectors. Setting k' O (los(t) for k' x d matrix M with entries drawn
Let K' < d. By applying linear transformation of the data via an appropriately chosen matrix M E IR xd we show that learning personalized parameters can support fur- ther dimension reduction. This is done by first learning U E & over the linearly transformed data in R& then constructing the final shared embedding M Ü e Rd We obtain utility guarantees independent of the data dimen- sion d via this process of first learning low-dimensional embedding then mapping it to Rdxk
uniformly and independently from { ( is (t, T, 3)L transform.
1) implies that M
Suppose M E IR xd is a random matrix with entries drawn Define Un = {MU : U E UJ. Let Bp be the k' k-dimensional Frobenius ball of radius v /2k. We define ~ to be Frobenius norm 7-cover of Bp. Assuming that 7 1, we have Uy S BF with high probability. That is, for any U" E Uss there exists U e N K'N
uniformly from { }
In this section, we study the classification setting. Let X be the d d-dimensional Euclidean ball with constant radius > centered at the origin and y 1) Define that data space Z X x V. Let U C ka be the space of d x k matrices with orthonormal columns and V C R be the space of matrices with rows bounded in Euclidean norm by a universal constant I > O. The data distributions for ........2
((
where UIU - Ü'll S 7. Moreover, |
VT
Algorithm first takes as input the user data sequence S and score function f. It then constructs JL transform M in the sense of Lemma 15. Algorithm 3 reduces the dimensionality of the users' data in S by applying M to each feature vector in each user's ' dataset. The exponential mechanism is run over a cover A using a score function f( -,, f(,,SM) which will be defined shortly, to obtain a now-dimensional shared
our n users Di,..., Dn are possibly distinct distributions over X' x y. We further define the distribution sequence D (D....., D,).
Definition 13. Let (U,v) v) E TRdk x k and (x. v) E
7

---

Private Model Personalization Revisited
embedding Ü E R This MTÜ E Rdxk is used by Algorithm 3 where the final embedding Univ M U and local vectors Vpniv 1o ux are computed by the users via C
Key obtaining this result is that y is both the error pa- rameter of the JL. transform and the radius of the sets in cover N
Lemma 16. F, > 0,3 E (0, 1). Algorithm 3 is (c. 0}- user-level DP. Sample S ~ D Then, Algorithm 3 returns Updv from input S such that
Our algorithm functions as an improper learner in the sense that the learned shared representation Upev is not necessarily an orthonormal matrix. However, this does not affect the performance of the final user-specific classi- fiers in terms of expected loss. In particular, Theorem 17 establishes that the expected loss incurred by our algorithm remains close to that of an optimal orthonormal shared rep- resentation, ensuring that the lack of orthonormality does not degrade utility.
Remark:
min MU V:59)= VEV
min (V.V)uux
T.,(U, 59)
+ +ō
cppn
with probability at least 1 - 3 over the randomness of S and the internal randonness of the algorithm.
Assume for simplicity that m is even. We partition
Theorem 17. Fix > 0, E (0, 1). Algorithm: 3 is (c. 0}- user-level DP in the billboard model. Sample user data S ~ D Then, Algorithum 3 returns Upiv, Vpei from input S such that
St S U St where S f 24. and S (.y+t.:...;,mm
for each i [m]- Fur- S)) where E {0.1}.
ther, we denote St Suppose that S = (S,....,,s))
gmm(d+1) is quence of n datasets with m samples each. Let Sas (S))),,.. aS,) where (S:)M= = {(Mx... vi.) [m]} for all E [n]. The score function for Algorithm 3 is (UU,SM) - + mil (U,
L(UDiV vpiv, S
min (U,V))UX
r nepp
r²T2
+
mp²
(U,,,; my ())) for Ü E N Since we provide a user-level privacy guaran- tee, we must bound the sensitivity of f over neighboring sequences S, S" where S" differs from S by most a single user's entire dataset. can be shown that the sensitivity is bounded 1, which follows casily from the fact that the margin loss is bounded by 1.
with probability at least 1 33 over the randomness of and the internal randomness of the algorithm.
To the best of our knowledge, the above bound is the first margin-based population loss bound that is independent of the data dimension in private personalization with shared embedding.
Algorithm 3 Private Representation Learning for Per- sonalized Classification
5 Conclusion
Require: dataset sequences 8 and S' of equal size, score function f(U",
In this work, revisit the problem of model personal- ization under user-level differential privacy (DP) in the shared representation framework. We propose a novel pri- vate federated personalization algorithm that extends the FedRep method while ensuring rigorous privacy guarantees. Our approach efficiently learns a low-dimensional shared embedding and user-specific local models while providing strong privacy-utility trade-off', even under noisy labels and broader sub-Gaussian data distributions. A key contribution of our work is demonstrating that private model personal- ization can be achieved in a federated setting with improved risk bounds. Specifically, we show that our approach re- duces the privacy error term by a factor ((dk) in a natu- parameter regime, leading to a higher accuracy in high- dimensional settings. Moreover, our private initialization technique ensures good starting point for learning shared representations, even under privacy constraints. Addition- ally, for binary classification, we provide an information- theoretic construction for private model personalization that leverages dimensionality reduction techniques, and hence, derive margin- based cimensionninneeendeen risk bound.
minvey TU, V; ) over matrices U' E BR privacy parameter e > 0, target 2r" (8g(mm/8)
dimension k/' 0
g²
1: Sample M E RR4'xx xd with entries drawn i.d uniformly
from + VF
2: Let SM
(S.)))) where (St)ar {MMx v) y). E 5 for i [n]
3: A/" be Frobenius norm 7-cover of Br
4: Run the exponential mechanism over \ privacy pa- rameter e, sensitivity n
1 and score function (M),
to select Ú ENY
5: Let Upriv +- .M
6: Each user i E [n] independently computes of arg mills L(UPiiv U. ST-)
7: Return: Uprriv yrrv = luf .... P
The lemma below is an extension of a fundamental result for the exponential mechanism (MeSherry & Talwar, 2007).
8

---

Private Model Porsonalization Revisited
While our work provides significant advancements in private federated personalization, several open directions remain for future research: (i) Relaxing the identity covariance sumption: Current results assume sub- nab-Gaussian feature dis- tributions with identity covariance. While this assumption simplifies the analysis and aligns with prior work, it does not hold in many real-world applications. A key challenge extending our methods to handle arbitrary covariance matrices. This could involve leveraging adaptive precon- ditioning techniques or covariance-awars mechanisms to improve learning under more general feature distributions. (ii) Extending beyond quadratic loss functions: Most of effi- cient private personalization algorithms, including ours, rely on quadratic loss (i.e., least-squares regression) due to its analytical convenience. Developing gradient- baseed methods for more general loss functions, such as logistic hinge losses, remains an important open problem. Current tech- niques for private optimization in these settings are either computationally expensive or lack strong utility guarantees.
35:22505-22517, 2022.
Bassily, R., Mohri, M., and Suresh, A. T. Differentially pri- vate learning with margin guarantees, Advances in Neural Information Processing Systems, 35:32127-32141, 2022.
Bietti, A., Wei, C.-Y., Dudik, M., Langford, J., and Wu, S. Personalization improves privacy-accuracy tradeoffs in federated learning. In International Conference on Machine Learning, pp. 1945-1962. PMLR, 2022.
Bun, M. and Steinke, Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of cryplography conference, pp. 635-658. Springer. 2016.
Collins, L., Hassani, H., Mokhtari, A., and Shakkottai, Exploiting shared representations for personalized feder- ated learning. In International conference on machine learning, pp. 1089-2099) PMLR, 2021.
Du, S. S., Hu, W., Kakade, S. M., Lee, J. D., and Lei, Q. Few-shot learning via learning the representation, provably, arXiv preprint 4rX1v:2002.09434, 2020.
Acknowledgment
The authors' research is supported by NSF Award 2112471 and NSF CAREER Award 2144532.
Duchi, J. C., Feldman, V., Hu, I.., and Talwar, K. Subspace recovery from heterogeneous data with non-isotropic noise. Advances in Neural Information Processing Sys- tems, 35:5854-5866, 2022.
Impact Statement
This work advances the theoretical and algorithmic foun- dations of privacy-preserving personalized learning, a key challenge in the deployment of trustworthy machine learn- ing systems. In domains such healthcare, education, and mobile applications, users' data are often sensitive and highly personalized-mmainnn it critical to ensure privacy while delivering individualized models.
Dwork, C.. McSherry, F., Nissim, K., and Smith, A. Cal- ibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pp. 265-284. Springer, 2006.
Hsu, J., Huang, Z., Roth, A., Roughgarden, T., and Wu, Z. S. Private matchings and allocations. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pp. 21-30, 2014.
Our contributions demonstrate that personalization and strong privacy guarantees can coexist in federated learn- ing systems, without compromising accuracy. The proposed algorithms address limitations in prior work by supporting broader range of user data distributions and operating in realistic federated environments. Importantly, we show that the accuracy of learned models can remain robust even in high-dimensiona settings or under label noise, which frequently arise in practice.
Hu, S., Wu, Z. S., and Smith, V. Private multi-task learning: Formulation and applications to federated learning. arXiv preprint arXiv: 208. 12978, 2021.
Jain, P., Netrapalli, P., and Sanghavi, S. Low-rank matrix completion using alternating minimization. In Proceed- ings of the forty-fifth annual ACM symposium on Theory of computing, pp. 565-674, 2013.
By enabling theoretically sound, privacy-preserving person- the design of secure
alization, this research can help guide and reliable machine learning solutions across a wide array of socially impactful applications.
Jain, P., Thakkar, O. D., and Thakurta, A. Differentially private matrix completion revisited. In International Con- ference on Machine Learning, pp. 2215-2224 PMI.R, 2018.
References
Jain, P., Rush, J., Smith, A., Song, S., and Guha Thakurta, A. Differentially private model personalization. Advances in neural information processing systems, 11299733-99733 2021.
Arora, R., Bassily, R., Guzmán, C., Menart, M., and Ullah, E. Differentially private generalized linear models revis- ited. Advances in neural information processing systems,

---

Private Model Personalization Revisited
Johnson, W. B. Extensions of lipshitz mapping into hilbert space. In Conference modern analysis and probability, 1984, pp. 189-206, 1984.
Kearns, M., Pai, M., Roth, A., and Ullman, Mechanism design in large games: Incentives and privacy. In Proceed- ings of the 5th conference on Innovations in theoretical computer science, pp. 403-410, 2014.
Lå Nguyen, H., Ullman, J., and Zakynthinou, I.. Efficient private algorithms for learning large-margin halfspaces. In Algorithmic Learning Theory, pp. 704-724. PMLR, 2020.
Lee, K., Maji, S., Ravichandran, A., and Soatto, S. Meta- learning with differentiable convex optimization. In Pro- ceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 10657-10665, 2019.
McSherry, and Talwar, K. Mechanism design via dif- ferential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), pp. 94- 103. IEEE, 2007.
Nelson, J. Sketching algorithms, 2020.
Raghu, A., Raghu, M., Bengio, S., and Vinyals, O. Rapid learning or feature reuse? towards understanding the effectiveness of maml. arXiv preprint arXiv:1909.0915: 2019.
Stewart, G. Matrix perturbation theory. Computer Science and Scientific Computing/Academic Press, Inc, 1990.
Thekumparampil, K. K., Jain, Netrapalli, P., and Oh, S. Sample efficient linear meta-learning by alternating minimization. arXiv preprint 2rXiv: 10t.::005.00300 2021.
Tian, Y., Wang, Y., Krishnan, D., Tenenbaum, J. B., and Isola, P. Rethinking few-shot image classification: good embedding is all you need? In Computer Vision-ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XIV 16, pp. 266-282. Springer, 2020.
Tripuraneni, N., Jin, C., and Jordan, M. Provable meta- learning of linear representations. In International Con- ference on Machine Learning, pp. 10434-10443. PMLR, 2021.
Vershynin, R. High-dimensional probability: An introduc- tion with applications in data science, volume 47, Cam- bridge university press, 2018.
Woodruff, D. et al. Sketching as a tool for numerical linear algebra. Foundations and Trends@ in Theoretical Computer Science, 10(1-2):1-157, 2014.
10

---

Private Model Personalization Revisited
Appendix
Technical Lemmas
12
Missing Proofs for Section 3
14
B.1 Main algorithm results
14
B.2 Private initialization results
26
B.3 Auxiliary lemmas
28
B.4 Private FedRep experiments
45
Missing Proofs for Section 4
46

---

Private Model Personalization Revisited
A Technical Lemmas
Proposition 18. Let X (X X.) E Re be random vector. Assume that Xp is fo-ssub-Guussiar for each p E [a] and that Xp. Xg are uncorrelated for p # q. Ler (Ri...., Ra). Then, for each v E R the random variable (v. X) (1lv/12 maxpeia] Sub--Gaaaassnn
Proof. Fix an arbitrary X E R. Observe
E
Mexx)
= E
(pp
IE ((uu))Xp)))
p=1
A P x
I < A1uu11 maxpela| R
where the second equality holds by uncorrelatedness, the first inequality from the definition Gaussaan and the final inequality from definition of |12.122
Proposition 19. Let X (X,...., X₂) E R be random vector with [ Ô. Assume Xp: X, are uncorrelated for p p q. Suppose that v, π E I= with (v, x) 0. Then, (v, X) and (T,, X) are uncorrelated.
Proof. By the assumptions the above proposition
E ER X) (T, XX
Xp Σ TpXp
p=
E
Xpp
P-PE(al
E
Σ
X?
E Σ
Up up XpXX
Up
+ Σ
Up [Xp]E
p=1
ppg
E [M4 XX| E [ X)]
where the last three equalities hold by (1, x) = 0, the uncorrelatedness of the components of X, and the linearity of expectation.
Lemma 20 (McDiarmid's inequality). Let f RR + where, for all T1,...,, Fn
R be measurable function. Assume there exists a constant c; >>
sup (Z 1. 2i41, x.,) f(z R4-1, 24
Innil S
EE
for each E [n]. Suppose Xi...., Xx IR is sequence of i.i.d. random variables. Then, for all 0
2.2
P[f(X1,..... X,) EEf(( X,)) 2 s) Se E1-
12

---

Private Model Personalization Revisited
Definition 21. We say that random variable X is R-sub-exponential
E
Mxx S SEAR
for all À such that 0 S 1/R
For the definition above, we call the smallest such R the sub-exponential norm of exponnnaponetiial random variable. Lemma 22 (Bernstein inequality). Let , Xn E I& be sequence of ii.d. R-sub-exponenticl random variables. Then, for any > 0
n
min 2
P
X
8
R2.
for some constant e 0.
Lemma 23 (Lemma 4.4.1 (Vershynin, 2018)). Let M E Baab be any matrix. Take Sa-1,5" to be the unit spheres in R" RR respectively. Suppose that No are Euclidean e-covers over 1,-11 Then
||ll S I- WEN"
max V Mu'.
Definition 24. centered random vector X I2e with covariance matrix E is isotropic if
Σ E [ -Ia La.
Definition 25. centered random vector X R2 is Sauub-Guussia if
E (X,
I n2
for all E IR.
Note that when centered vector X E Ra is 1-sub- Gaussian and has covariance matrix Ia, the components of X are Gaus-Gasssin. We use this fact our results in conjunction with Assumption 5.
Theorem 26 (Theorem 4.6.1 (Vershynin, 2018)). Let M be an a b matrix whose rows are independent mean-zero K-sub-Gaussin isotropic random vectors in TR. Then, for any z 0, there exists >> O where
- (Vb+ a) s (M) < Tmax mma S Vo ck2 (Vb+a)
with probability 2e nn²
Corollary 27. Let M be b matrix whose rows are independently drawn from N(, 02 laxa). Then, for any 0, have
(Va- (Va--(bbou (Vb+a)) < Tmin m I Tmax {max(MM) S o (Va+ (vb+a))
with probability at least - 2e -a²
Proof. Observe that we have M = M for a matrix M ~ Naxb((,) 1). As well, note that M satisfies Theorem 26 with K since its rows are standard Gaussians.
For any matrix A R we also have that (c'A) dop((A) for c' > 0 constant and (A) the p-th singular value of A. Combining the above reasoning and Theorem 26, there exists constant e >> 0 such that
Va - cc-c(Vb cobbv(bb +0)+ ax) S Sminn (M) S mmax (M) S Va + (vb+ +x))
implies
(Vā- e ( (vb < Tmin 0min(M (M) < max (M) S (Va+ (bb+a))
with probability at least - 2e -a Furthermore, for standard Gaussians we have e c= 1.
Note that one could simply apply Theorem 26 directly to the matrix M from Corollary 27 by using = ô, but this does not give the desired result. In particular, we require that scale both terms of the upper bound of Tmax (MM ) in our later analysis of the Gaussian mechanism.
13

---

Private Model Personalization Revisited
B
Missing Proofs for Section 3
B.1 Main algorithm results
We first restate algorithm and main assumptions.
Assumption (Restatement of Assumption 4). There are known A, A 0 such that A 2 0uxx, 2 m X.
Assumption (Restatement of Assumption 5), Let i E [n] and x ~ Dj. For all i E [n] the feature distribution DD has covariance matrix Ia and is sub-Gaussian in the sense of (e(*.)) S s for all E Rd.
!ullž
Assumption (Restatement of Assumption 6). Let SG(R) be any centered R-sub-Garrt Gaussian distribution over R. Sample <~ (GG). For all E [m]] and any data points (x, y) ~ DD we generate the label f.ror the i-th user via
x U +
where Ç independent for all D
Unless stated otherwise, in this section, we assume that Assumptions 4, 5, and 6 hold. Furthermore, throughout our proofs we assume [d(kk).. This assumption is reasonable in the context of our work since 52(ck) is required for non-trivial results in our final bounds.
Algorithm Private FedRep for linear regression
Require: S { B5,1)..... (Zim }i.m)} data for users E [n], learning rate iterations T,, privacy noise parameter 8, clipping parameters vi, Plinits batch size b S [m/2T'], initial embedding Unnit E Bdxk Let S. -- {(Ta,j Vr.j) : E mm/2]} Vi E [n]
Let S - 5; \ 5 Vi E [n]
Initialize: Ug + U
for O,... T do
Server sends Ug clients [n|]
for Clients E [n]] in parallel do
Sample two disjoint batches Bi, and Bi each of size b, without replacement from S
Update U/ as
U1tt f- arg min T.,,, U; B,,)) eERt
Compute the gradient w.r.t
Vi VU, Bl,))
Send V to server
end for Server aggregates the client gradients as
n
0.t1 t U, Un-1
clip( Vi,, 1) + Ee+1
U141, + QR(U++1)
where Eot1 <- Ndxx (0,62)
end for
Server sends Upriv UT all clients for Clients i [n] independently do
of +- arg min L( vr S!) Vi [n]
end for
Return: Uriv Vpriv
Lemma (Restatement of Lemma 7), With probability at least 1 - O(T -n -11), we have
|Vaoll s δ (
14

---

Private Model Porsonalization Revisited
for all i [r]] and all E [T] simultaneously.
Proof. The privacy guarantee directly follows from the the privacy guarantee of Gaussian mechanism and advanced
composition. In the following, we prove high probability bound for V|V,ell Let B¹ ((rk,) Vay) : [6]} be data batch of user sampled iteration as in Algorithm 1. Then we have
(1 U00,411 - UT + G1.)) o "
Denote UQUi,e+1 U. Throughout the proof we condition on the event
8 8- Kesl Kisl < Ry 26 log(nb), (u, x1,5 < ||wl2 v 26 log(nb), and |/0,0+1122 S r for all (i, E [x] x [6]] 8-
which holds by the sub- sub-Gaussianity of 2',5, the independence between 24 and U Un, and Proposition 42 with probability least 1 O(nb n -114) 2 O(n-1)). Given event &, we have
5 (z/ Upus,c+1 - - Cod S
log(nb)).
2
Mcanwhile, the (p. eeeement of 2/, v,,t1 has
(1,5))(1,,01d)))) 7 TV 26 log(nb)
(1)
for all i,j with probability least O(bb n 11) by the sub-Gaussianity of the components of x'4, and conditioning on E. Therefore, taking union bound on q, t without conditioning, we have, with probability at least - O . n n12)
|V F - 82( + T)T dl log(nb)
for all i, simultancously. Finally, we bound - O n 1 2 1 - OTT n2-
Theorem (Restatement of Theorem 8). Algorithm 1 is (c, uuserlllllllleel DP in the billboard model by setting ô
W. / [1g((188) for some absolute constant C' 0.
ne
Proof. Since the computation of Vpriv is performed by each user independemtly, is sufficient to show that the computation of (Jpix satisfies centralized user-level DP.
Given the definition of the clipping function, for each i E [n]], we have [Vclip(V R) S vb which implies that the sensitivity for each update of the Ug is bounded by tb. By taking = C TToo//oo/// we obtain the privacy cost of each iteration t is = 0 2²
Tlm(1/85) under zero-concentrated differential privacy (z-CDP, (Bun & Steinke, 2016)). By the
composition property of z- z-D,, we obtain the total privacy cost p = -IT Pt = =0 in(1/4)) Then, we can convert the z-CDP guarantee DP guarantee with the privacy parameter being p + vpln(1/5) O(e) with sufficiently small 8. Therefore, the computation of Upriv is (c, 5DP and the algorithm is (c, 8DDP in the billboard model.
For the rest of our proof condition the event of clipping does not affect the original gradient norm in Algorithm 1. By Lemma 7, this event has probability at least 1 - (T-r -10) for all i, simultaneously when selecting & = Ö (R + r)r r)r
Let 01,1. Ungt be the sequence of local user parameters generated iteration of Algorithm 1. Define the matrix Ev, = 1 - ". Take B₁- (Bi,.-..., :.. B to be the sequence of batches from of Algorithm used to update U, iteration for each user Assume that we re-index the batches By, {( vi j E [6]] for each i, t. Let U4+1, Pt+1 be the matrices from the QR decomposition, and
n
6
Vu Ures (1/ v(,)) Rddk
n
nb
j=1
15

---

Private Model Personalization Revisited
the aggregated gradient, all computed in Algorithm 1. For ease of notation we also drop the iteration index the data points j ). Recall that vj is the fixed stepsize for Algorithm 1.
Lemma 28. Pe+1 invertible, then
disi(U++1, 2 |Ptzllla (114- - n1v,, ll2 di, U*) + v/| - EBg [Ve]la + 7
Proof. Let U2t1 be the 1-th iterate of Algorithm before QR decomposition. Observe
((0")\) = [[V))]( - vv. + m
S - s II(U>I(( " (V.)
- vV. + + V n V.) ll2 + n/lE
+ 77l V
EB; V + 7lll/l22
since [[(U*)]ll2 1. Then, since the data has covariance matrix b7 and label noise Si that satisfies B[G,,] 0
EB [.]
EB (( (T + (.
Tu
nbb
EBg |24 (2(e)) (Urvi yuu
EBG (UGUU Un (707)
nb
U - 0,
n
==
where the second equality holds because that By independent of U,, Vg. Hence
(1/5)) of + Gi.j a scalar and the fourth equality by the fact
- nb i= j=1
Σ>
( ( (U")TU, Σ
0 T
nb i=
1=1
since (U*) = 0. Then, for Ev, = 1 En 1.
II(*)) - B [V)))l22 1(0*) -E:))ll S 14 1/Ev, UUll2.
Hence
< 4 |1 w/V - ER,,, /Vll22 + 7/lEel22-
(2)
Now, assuming that P4t is invertible
Prllle < [1P
So
s | (urall
(3)
Combining (2) and (3) finishes the proof.
Our proof for our main result follows from bounding the terms and factors on the right-hand side of the inequality in Lemma 28; namely
dist(U+41, S |P (1 - v/E,v, (ladist(U,, + v// Ee; [V.]le 7l(eell2)
(4)
16

---

Private Model Personalization Revisited
The above inequality has four important components. The term || -B [V e la is the deviation of the aggregated gradient from its and hence be bounded via concentration inequalities (see Proposition 30) and the term ||Ce||2 is the magnitude of the Gaussian noise added for privacy, which is not difficult to bound as well (see Proposition 29).
Deriving bounds on [PP+1ll lla and ||4 v (l, U*) in (4) is less obvious and require some extra work. We can understand | - vv ll2 as a measurement ......... U are evenly distributed in I with no bias in any direction. For example, v1,e. Un,t are independent with Vt,r (0, II>) for each the matrix Is- Evv, Ix Ei=1 Bi,eV, will concentrate around the (d k) dimenssionll zero matrix.
how close Σv, is to 1) T-- So, when || Tx - n)Ev, la small, the vectors
The quantity ||P=|l|2 is more subtle. This quantity is result of relating dist(Ur+1, U*) and dist(U,, U*) via II(U)) || as in our proof of Lemma 28. We can interpret [|P ll2 as quantifying how far Üs41 is from having orthonormal columns. As well, we require that P exists in general because the principal angle has dist(M, M') = 1 whenever rank(M) * rank(MM).
Recall that & is the gradient clipping parameter Algorithm 1. Proposition 29. For all t, we have
( (WVd (WVdTlog(m) log(n) log(1/0)
1lell2 0o with probability at least 1 Onn-1o).
Proof. Let G 2/ 2./22long log(1..22 1125/8) as in the statement of Theorem 8, Let a > O. Then, by Corollary 27
ne
② (vd (Vi (vi+ +a)) S mmin (Ex) S max (Ee) S & (vd+ (vk-o)) -
with probability at least a0 Choosing a / Tod gives us
1kEel12 S & Vd++ Vi 10d
1b Vd + V log
2T log (1255/8)
2 / log(n) (oegnnlog((//)))) log 1/5)
0
with probability at least - 2e 10d Proposition 30. For any t. we have
(1PPLRR + r2)
|V. EBG /ell22 5ō
nb
with probability at least 1 10)
Proof. Let Ard and ^ be Euclidean 1 -oveess of the and k-dimensional unit spheres, respectively. Then, by Lemma 23 we have
4 max a (V:- - EBG [v.])
IV. -FF [Vell2 S
aEE'
Now
a (V, Es; [v.))
2
(lrk - + Cas) (a, o (era,
nb
n
b Σ
Epg [[(rl.g) Uni, Utuf) + Ceo) (a, Mus
mb
17

---

Private Model Personalization Revisited
We condition ||u, S [ for each i, which has probability at least -O(n by Proposition 42. Then, have that
2 nb (((2) Ueer, UT) (as) (a, (oL,, 6) - EB;
-, + (ads (a, x1 (or,,)))))
centered, independent sub-exponential random variables when also conditioning on U.. The sub-exponential norm of these random variables (2)² 3(R+T)F Then, given Uz, Vi are independent of Bú, and assuming nb 20( + k) log n, get from Lemma 22
nb
(2
+
a (V--
- Eng v.l)bs
nb
with probability at least 1 - O(n-10). This bound holds unconditionally since wayt are bounded with probability at least
1 1nO(n Onn ) for each Thus
(V
+
VV. EBG V.ll2 26(
nb
with probability at least - O(n (0) by the union bound.
In Lemma and Theorem 10, assume there exist co, ei such that
T = log n 112
nmx
S min
C1 ma DJD km log (nm) + R2 min, log(nm)
(6)
2 max.
Cg Gamax(R3, 1} max 1) 2D log n + R2ko? max,+ log(nm)
This relationship between and the problem parameters equivalent setting
T log
nda
along with assuming the following two conditions on m and n: Assumption 31. Let Eg = 1 - dist (Uo, U*) > 0. We assume there exists some constant cp >
where
2 max R2, 1 117
R2k
log(nu)) T. T
(8)
E
Assumption 32, Let Dc,b C (10g(1225/8) assume, for some constant C1 >
for some constant C > 0 and Eg - dist dist?(Uo, U*). For the count
max (A., () (R++)+))) D))Thooooooooo (nm)
R T.
n 2 C1
E
Our Assumptions 31 and 32 are used repeatedly throughout Appendix B. These conditions are easily leveraged individual assumptions on m and n, unlike the upper bound T. Including the equality (7) allows us contain all required conditions on T, m, and to convenient setting.
Lemma 33. Let Eg = 1 dist (Uo, U*) and 1b Ō Õ( ((R+ Suppose Assumption 31 and 32 hold. Then, for any iteration i, we have that P4t is invertible and
noo min, Eo
P
2 log n1
with probability at least Onn-10).
18

---

Private Model Personalization Revisited
The proof of Lemma 33 is deferred to Appendix B.3. Lemma 34, Let Tj S 2r E Eo and 32 hold along with T
dist (Uo, U*), and - = = Suppose Assumptions 31 Then, for all i, we have
log n 1o min.-
17o 2
Eg
1T 1/V V
min,
with probability at least - Onnn11n))
Proof. We will show that
[ nTEv, 1 no min (
1
no min,+ En
1
with high probability for each f. Then selecting n 2 ex and using Lemma 33 implies the product || P211l12114 - n 12 satisfies the lemma statement.
Note that Vi, V V + E. v. and define V/ Omin (tt V.).
Given V v*(U*)TTi F by
Lemma 39 and V and UU*)TU are full rank, we have
1 V1
(2 ('
1
Omin
Vi
2
miin
Vn
mmax
/n=
min
v ((U))
mmin
mmax
F
n2
Now, via the argument of Lemma 39, we have, with probability at least -un)
26/22 log(nb)
max
(
m +
V (1 2b
(10)
Tk
for 7h C 35k Recall that 7 Tmaxi
and
Then, there exists constant è such that, by
miin.
Assumption 31 with 2 1667, we have
VTk 1 Tk
0B muxx,.
o Umax, Eo
Tuin, Eo 4 4vTog n
mmax, I C1
(11)
co7 logn
4 logn
and
26R log(nb)
Fmax Fu
Omin, F. 4vTog
< 8V
(12)
(1 26
c logn
4 4
max It, max (r3 ,1) " "klogg I' a'dnd 7 2
since m 2 co
Fif o
max..
Furthermore
mmin ((U)) 2 / 1-
= v1 dist (Uz, U*)
Therefore, we obtain
1
1
Tmin, 2 Omin
V'
mmiu ((U))TUi)
-max
Vn
Vn
(VI dist? (iis??( U+)
Fo
mmin,
2 2 ni
19

---

Private Model Personalization Revisited
with probability at least On (1)) Thus
- no min, I no min, (V (V1- dist (U,,
Eо 2Vlog
(13)
Claim 1: We have
[1 D1, 122 1 -no min,
with probability at least - O(n ((n= We prove Claim 1 by showing 20max.
2
which implies
mmax, min,
1 rvVvlle & max {11 finx,vibll - no vili S - no
First, reuse
26122 log(nb)
VTR
max T
max,
V
(1 -1-17 Th )b
as in (10). By Lemma 39 and the triangle inequality along with the submultiplicatiiity of the spectral norm
0 m,
= -max
Vn
V
- (U))
1 Vn
S Tmax
+ max
F.
S Tmax, + maxx
Vn
So
mi S maxx, + Tmax
F
(14)
By (11) and (12), we have
m
maxx
nh
2
and thus via (14)
min.V. Vv S 20 max,t
Since min, max,V, by definition, we have o min, V. + 0² iuax, S 4o max,+ This gives us 20 max. maxx mann with the required probability. This proves Claim 1.
<
Next, we will prove the following claim using induction.
Claim 2: Let 51' / (ug(mm)
2
We have V 1- dist di, (1-top
(1- Eo for each iteration E [T'.
257=1)g(am)
Base case: when f = 0, the inequality
dist (Us, U*) 2 Eg is clearly true since F. 1 dist (Uo, U*).
Inductive hypothesis: we assume V I Z v Fo for some / E [T].
Inductive Step: note la < 1 for any / [T]. Our assumption on v1 (11-1((U)] I|2, (13), and assuming 2 E imply
min,, (Va-
Ep
o Min,V Vi
22
(15)
2
Now, since 77 S 20 max.-
<
Weyl's incquality and (15) give us
mnne, v,, mmm.
l -v, 112 51 2 min, V2 E - -o (V(1-ta) to)
Eg 2 T
20

---

Private Model Personalization Revisited
By Lemma 33
PP 11 S (1
n0 min, Eo
2 log n
with probability at least - On This event is superset of the probabilistic bounds from earlier in this lemma.
Then
1o min, Eu
Eo 2 n )²)
2
1-no min,
no
to
1(00))
22 log nt
(16)
1) ( ((++T]
112 ( + +2)rdd
+0
nE
nb
with probability at least - -0n 110). Assuming 2 /Bo/(v2-1/22) we have
1 no min,
ta)
Eo
< 1 nomin.
(VEo12-
Eg
<
110 2
min,
Eo
llog
2
4
As well, if 2 20, we have
-
170 min,+ Fo
(V1- ((1-la)Eb la)
Eu
1 min.
V2 log ni
2Vlog n2
110 min,+ Eo
(VEo/2
Eu
2
min,+
V2 log
2 2/log
1102 min, Eu
no min, Eu
v2 log
-
17 min,+ Eo no min, Eo
no min,* Eg
We now use the lower bound assumptions of the user count n and data sample count m. Recall the exact statements of Assumption 31 and 32. That is, there exist Cu, Cj > 1 such that
m 2 co max R², 1) max(T2 1)
R² log(nm) T
+
F3 max.+
r2
and
max (Ar,8 13 TR log2
R² log(n)) T.
n 2 Ci
E
m
The problem parameters that lower bound m, n now come into use during this proof. Furthermore, recall that by Assump- tion 4 we know some À > 0 such that À S Omin... Then, by Assumptions and 32 along with e and T n
there
7x²
21

---

Private Model Personalization Revisited
exists constant è O such that
1/2 [(
Ei no min,+
S 1
4
((1
17 no min, Eu V2 n
(R+1))dd/TK log (/6) log(nb)
+0
no 2 min, Fo
(RR2 + 1 logn
v2 log
nb
110 min,+ 1
2
Eo
I[("))U +0
[n(R+ D(Rd+)Tdd
/ Tk log(1 (1/5) log(nb)
4
716
(IR + 12 log(mm)
nb
(17)
1/2 II +0
no
Eo
n>²E3 VT T log(mm)
min,+
4
E + D)ro maxe APT
COC1 m 11
max max 1) x 7 log log(ne) log 2
1/2
|1(U*) [Uell) +0 no min, Eu
Vijo min, Eg
4
C T log(nm)
E L''o'o max, log n
COc1 max (R?, 1} max 1 T log log(mm) log 2 n
(1- no min,+ Eo
CE
Ed egc1 1k 2 log(nm) log
CITT IUell +
4
(log(nm
since 1) < 20 m
RRecall and x S min, Recall that y, k 2 1. Using the choice of co. G1
102 in (17), have
[(U")\U S 1 170 miin Eo
E
Ed 100 & 7 log (mm) log n
[ +
10yT / log(nm)
E
< [l(U0)\
5T (og(nm)
Thus, given Eg S 1
2
EB
1 1- 1-110U' 113 21 1
5T /lg (nm)
2E
TUI
E
II(U*)
5T
log nm))
257 2552logg log nm)
2
1
2 21 11-1100 II Eo
5T Tog(nm)
257 log(nm)
Then, by our assumptions that / 1 ||( 2 ((1-to) - Eo, we have
1- 1-I(U*)[U++
/ 11111100 11-1 aF 2 (1 to aFo = (1 - (t + 1).
22

---

Private Model Personalization Revisited
Thus, by inductive hypothesis
mii (1))) 2 V (U, ((1-ta) Eo
for any & 2 O. This proves Claim 2.
10T y [og(mm)) Observe that to S Ta T
for all t. Using this, Claim 2 implies
257 1og (1mm)))))))))
mmin ((U)) 2 V dist( U*) 2 v(1- ((1-ta)Eo 2 v Eo/2
(18)
for each 2 0. Via (18) and
eº along with 17 I 20tuux.
no
Eo
|P - nT., l12 S V min,
4
with probability at least 1-0 0nn for any E [T - 1]. This proves the lemma.
Lemma (Restatement of Lemma 9). Let S 20 max."
Suppose 1 - dist (Vo, U*) 2 c.for some constant >> 0. Set
the clipping parameter v = Ō (R+ F)J Assume T log y²²
Ō min
umX
(m.x(A. (R do
m max.. max [I) max 1 Rekka )
and Assumptions 5 and 6 hold for all user data. Set ē as in Theorem 8 and batch
size b = [m/2T]. Then, Updy the first oulput of Algorithm 1, satisfies
$
dist(Unir, ,U*) (U0) (1 erjo min,+
(R+T)TUVET need min,.
RR p2)DRTT
dist(Uo, U*)
4
nmno min,*
with probability at least 1 O(T 11-1).
Proof. By Lemma 28
((U")U+++l Ulllla < |IPzilla (114, m) Illl <//,, Ep; /v.l22 + 7ll3r112)
(19)
We must bound all three terms on the right-hand side of (19). Combining (19) and Proposition 30
1P(1e + I( < 117tilla [14- (ITa- - (Il=-nEnllll (
+
+ mlllAlla
(20)
nb
with probability at least - O(n -1)). Combining choice of 1 with Proposition 29, via the union bound
|14e-nEn,len -iv ( + nRR (n(++1)) 1'E+TT
(H + 12)lTe
I < |Pttlll
(21)
nb
for all [T - simultaneously with probability least 1 O(T 10).
To bound the right-hand side of the above inequality, we need to bound | 12. By Lemma 33, with probability at least
1- O(T n 19), we have || 2 < no min.. Eg /2 log
O(1) for all f simultancously, where the last equality follows from the fact that I 2amax. Eo I 1, and logn 2 (assuming, without loss of generality, that n > 2). Further, by Lemma 33
1
no min.
Foo I1(-)) +
T2 + +
(22)
4
nb
23

---

Private Model Personalization Revisited
for all simultaneously with probability at least O(T ((T.n 10).
Now, what remains is to obtain the tightest possible bound on the recursion from Lemma 22 via the summation of geometric sum. Since dist(U",, U [I("*) Uulll S 1, we have, for all t simultaneously
dist(U", (Ust()))
no 2 min,a
Bu
((++
1P re)r2d
dist(U", .U,) +
TEE
nb
no min, Eu
dist(U", ,U,)
yo min,+ Fg
n( m ((R+I)ddVR KT
+0
1E
nb
f
n1 min. En
dist(U",U
1
q(R+1) (RR+T)IVKT
1722 + 12)1ed nbb
+0
1
no min, Eu/4
116
cnjo 2
(R+T)TUVIT
RR + r2
min.*
dist(U" (U)) +
nEO min.
nbo min,*
with probability at least 1 -OTT-n-- given that 1-V1-- S for any x > and since there exists > 0 such that Fo 2 Selecting batch size b = [m/2T] completes the proof of the lemma.
Lemma 35 (Adaptation of Theorem 4.2 (Jain et al., 2021)). Let X be matrix with rows sampled from Dr and the vector of its labels generated according to Assumption 6. Suppose that (x, y) with x ~ DD is data point independent of X with label vector Take Ü to be any matrix with orthonormal columns and E arg min || T Ü X 10--13 Vl2.. Then
R²K
E ((, ( (x, < -
m
Proof. Assume that X D is data matrix with label vector generated as in Assumption 6 using noise vector T~ (G Let D, be a data point that is independent of By definition of our loss function and data generation method
E EANDI (f(v, U, (a, (x, = EEND, (ITUO Uv T + +)
(Uv U²O²) BLyDD [xx J] (Uv - U+***+++(((
| 0
o01l +E(
for any fixed U BRdxk u E R. Since arg min, TT X v1 we have w= (OTXXTO)-1 ØT XT,, UTXT where this
T
24

---

Private Model Personalization Revisited
inverse exists by our assumption that < m. Then
E -
-
=
0 [
E (U 0 U + +0 -0
0 x 2
[11UTU00 - -000 [12] R²k
s E | U20
m
= 100 -0" R.Kk
< - rIu 1 1-= R2k
m
where the first inequality follows from the fact that (X"XXTT))-OXXXT (OT O x.x by orthonormality of the columns of U and the expected mean square estimation error of sub- Gaussian noise. Combining two inequalities with E [e(v", U (x, B[ç2] completes the proof.
I implies U
Theorem (Restatement of Theorem 10). Suppose all conditions of Lemma 9 hold with 17 2λ. T θ [ that Assumption 4 holds well. Then, Univ and V the outputs of Algorithm I, satisfy
(2 (og(n))
and
L(U VpiN ;D) -(U)
(R² + T
(R2
+
I Ō
n min, X2
nmo 4
min, X2
R
m
with probability at least 1 O(T n -n1)). Furthermore, Algorithm is Juserreellll DP.
Proof. Via Lemma 9 and 1) 20 maxx
copiin min.
(R+T)TUVET T3602 minl+
R + +T
Pist(Upriv ,U*) <
dist(U,, U*) +0
4
nma min.
with probability least O 10), Note that dist(UT, [|(UTU] 1)U*ll2. Applying Lemma 35 and plugging choice of T in this bound finishes the proof.
with dataset Sn+1 of size m2 whose elements sampled from distribution D where assumptions 6 and 5 hold with [| S r. Then if dist(Uriiv ,U*) < 8 and m2 2 & mo,, m2, let u = arg min LU Uy Sn+1), then we have
Theorem 36. (Theorem 4 (Tripuraneni al., 2021)) Given
10"0" Upriv priv 11 5 (r20+
R2k m2
with probability at least 1 - 0m, 100)
Corollary (Restatement of Corollary 11). Suppose all conditions of Theorem hold. Consider a new client with a datasel Sn+1 ~ Dm' Dmt11 where Assumptions 5 and 6 hold with ||o7+1ll2 Г. Let Upev be the output of Algorithm I and priv m41 arg min L(UPONy v. Sn41), m' Z k logm''. m'. We have
L(UPav untii Dn+1) L(U" Uitti
RR² - (R² r2r R2 ml
+
22 "iinn
amo min, min,.
X2
with probability at least O(T n -10 m 1000.
25

---

Private Model Personalization Revisited
Proof. From the proof in Lemma 35, we have
P( n41 Dn+1) LIU", Unt1i Dn+1) - un+z UptiN u 112 16(r²1 16[7²²1 n+1
1 - Upiin n+11 112
Then by Lemma and our choice of T, we obtain
dist(UTe S=) (R+P)TdAVE neo min,
+R)
+ nmo min, X2
Then plug the bound of dist(Upri,, U*) into Theorem 36, and obtain
L(UDiV untii Pn+1) L(U", Th+1:2n+) s 1 UiDiV u 1111l1
RR² + A2
(R² -2) nmo min, X2
ReK
n2co0 min, 12
m2
B.2 Private initialization results
Theorem 37 (Theorem 2.1 (Duchi et al., 2022)). Let M, M E gdxd be symmetric matrices. Suppose p E [k] for k a positive integer with < d. Denote by Xp the p-th largest eigenvalue of M. Let A, À be matrices with columns the top-k eigenvectors of M, M, respectively. Then, 2y- Ax+1 > implies
M Mlle
dist <
d Ak+1
Proof. The theorem holds trivially when 2 AR-AR+1
> 1. So, we focus the case M la A AR+1
< 1.
Let Ap be the p-th largest eigenvalue of M. By Weyl's inequality and
M I 1, we have b ARt1
A Ak+1
d4t1 Act1 S II M11a 5
2
This and the assumption As- - Ax+1 > 0 imply
Act1 Se+1 ds A 0.
(23)
By the Davis- Kahan theorem (Stewart, 1990)
M - M112
|A <
(24)
d d1t1
Combining (23) and (24) along with ||A]A||2 = dist( A, Å) finishes the proof.
We use a slight adaptation of Theorem L.11 from (Duchi et al., 2022). The statement of the result below is different from the original result by a single step. This step is where the authors use the Ravis-Kahan theorem to obtain a bound on the principal angle. We instead state their Theorem L.1 before applying Mavis-Kahan for use in our private initialization guarantee.
Theorem 38 (Adaptation of Theorem L.1 (Duchi et al., 2022)). Let S = (Si,..., Sa) be a sequence of datasets where S: (II,,,,; (F2,m/2) //2m are sampled according to Assumptions 5 and 6 for each i E [n). Define Z; = Σ Jon Vi.h Vi.jo Fi.j TT.p 7 Σn 7ú, and 7 = n Σ E [Zi]. Then, we have
2 m(m
1| 21/2 5 0 [og' (105"(udl
RR -T2)De2d
mn
with probability at least On1)
26

---

Private Model Personalization Revisited
Algorithm 2 Private Initialization for Private FedRep
Require:
S { (6.,1,).6111.... ..... (m/ M/,m/2)) data for users [x], privacy parameters clipping bound Winits rank
k
1: Let Onnit f Vini log( 1.6
2: Let Sinit f- A0 o init)
3: for Clients E [n]] in parallel do
4: Send Z t m(m-1) Lu Vi.h Ms.ja Pa.j Figja to server
5: end for
6: Server aggregates Zi and add noise for privatization
7
clip(Zz; thinit) Sinit
71
Server computes
Uni DU init rank-I-SVD(22)
8: Return: Unit
Lemma (Restatement of Lemma 12). Suppose that Assumptions 5 and 6 hold. Let Uina be the output of Algorithm Then, by setting Vinit = O(RR² + d)),), we have
(R² +12) neO min.
RR +2+112113
dist(Uinits U*) S
mino min,
with probability at least 1 19)- Furthermore, Algorithm 2 is (c. 8) user-level DP.
Proof. The privacy guarantee follows directly from the guarantee of Gaussian mechanism. For our utility guarantee, we condition on the event
E 8= (wuss & O((T + R) log(m))), | s O (Viog dmm) dmn) for all (i,j.p) E [m] x [m] x [d] simultaneously }
where =²,,, represents the p-th entry of Tiy. The condition E holds with probability at least 1 - ((). Conditioning on event E, we obtain
7 r s ( + rd
and the clipping will not change the gradient norm. Let Z = 1 Σ Zi, 2 = Σr E [Z). Via Corollary 27 and the fact that the clipping does not affect the bound, we have
(112 + 122) 6/12
Tog logg?(mmn) (dmn)
2 Z1|2
|[ 5 20 =0(Vdoin) 0
(25)
116
with probability at least 10
By Theorem 38, we have
| -z- 2 50 log (nd)
(R2 - r2)r2d
(26)
mn
with probability over 1 O(n-1(n)) Therefore, by (25) and (26), we have
2 - 2-22 5 2 2 - 2
00 (1I2 + 122 Vlog n (dmm) + log"(nd) (nd)
(12 + 122
(27)
nc
mn
27

---

Private Model Personalization Revisited
with probability at least 1 O(n-19) via the union bound. Finally, using Theorem 37 and the fact that 2 (U> with (27), obtain
dist(Umn: U*) 2 2
min,
RR² + /d2 Vlg n (dmm)
(R² + r
0
log (nd))
nEo min
mno min.+
with probability at least On)-
B.3
Auxiliary lemmas
The results this section include multiple adaptations of those from (Collins et al., 2021) such as Lemma 43 and Lemma 33, Our proofs, when they are adaptations, are substantially more complex due the addition of label noise and differential privacy to design Private FedRep (Algorithm 1).
This section has the following structure. We first characterize the solution of the local minimization step of Algorithm in Lemma 39, Next, we introduce in Proposition 40 terms quantifying the label noise terms that periodically appear throughout our proofs. Using this proposition, we give bound on the етгоr from estimating ......, V, incurred during the local minimization step of Algorithm in Lemma 41. Using similar methods, in Lemma 43 we bound the spectral distance of the linear operator that defines the gradient step of Algorithm from the identity operator. Finally, using these intermediate results allows us prove Lemma 33, a key lemma our main proof of Section B.1.
Take I, IV to be the index sets of our batches in Algorithm 1. Let B,,; {(mij) Fi.j) j Ie) and By, [[ V(.)) j 7j). We omit iterations l on our quantities for ease of notation. Further, we reindex the elements of B B to
a = {(z1,) Jk.5): j E [b]} and B {( V(y) j E [b]] Let A. e. Ai, e,2' igj for each (i. E [n] Iz Define A Raxd - Rub where A(M) ((Aig, M) (t.)) for all matrices M Ruxd We analogously define the operator A' with respect to the matrices A
Denote (A')t R Raxd the adjoint operator of A' defined (M') = EE M)A In this sense (A)TA: nxd + Raxd a single operator. Furthermore, recall that & ~ NN,, 02),d) and choose ā Ō [R+ Define the following recursion from Algorithm 1.
Algorithm recursion
v(U))) +/ o/3
V4+ + arg min VeRTxi nb
0z+1 + U. - " nb ((A)) -V((0)))))) V4+1
(28)
2n ( 77E.
nb
U241, + QR(U.+1).
We will now state theorem that gives an analytic form for V4+1 Suppose p. g E [d], Let uytt, ug be the q-th column of
28

---

Private Model Personalization Revisited
Ug, U", respectively. Define
Gp.-
(A E R
1=1 f=1
1 n
Cp.9
Σ
b
(29)
i=1
Dp.a = (Up.ts Wyllnxn E guxn
W
Ai CR.
Take C, D be nk x nk block matrices with blocks Gy.gs Cpeps Cp.9 and W an wk-dimensional vector created by concatenating W, for each p E [R:. Denote 8"' = Vec(V*), a column vector of dimension nk:
For the following lemma define
= [[G - C) + 1.......G . - Cyū + W))a] Ba
(30)
where (G (GD C) + w))p is the p-th n-dimensional block of the nk-dimensional vector G-
Lemma 39. The matrix V441 satisfies
-===v(0)
at each iteration t + for the enoor matrix F E Rank
Proof. Note that V minimizes the function F(V,U)) = 2 - v(U))T) + clls and so V., F(V+1, U,) for Up the p-th column of V for each p E [k:]. Recall our definition A.,; = e, for e, the i-th n-dimensional standard basis vector. Given that
A(V* V(U.) -VC)))"")VVVVV))+++
|A(V*(U*) V(U.) + (UA( -V + ICII
we have for Uhgt the q-th column of Uz
0 V F(V+1,))
2 ΣΣΣ (Ais) Ugg411 Tuy.e1 (G))((i)))) (i) Aigup + nb
4 (A(" Ve+1 (U.)))))) ().
nb
Let (M),p be the p-th column of a matrix M. Then
V (UV - (V.(( -V-
=vV,, (A(V++( 3.5)
-V,, (UA) 5)
=-Vor Σ
G.s(Ass, Ve+1 V++1 (U:)
(M
-
Σ
Su (U+)(U))
-
Σ
Sug Vi+1
((J)
F
Σ
G.AA
(K.))(M) x(6]
+
29

---

Private Model Personalization Revisited
the y-th column of the matrix E(dDEEnn Saz As.UUe Ronk Hence
k
(A Mq.t+1 b
(Aigup.e((ug) (Ais) (Aiis) 1/2 +
2
Sig Up.
b
b =
Then, for u141 (vi,4+1....... 11+11) R and 8* ((1)) ....., (U,))) E Ran we have
C)u² T+11 = G + W) = De CCG + W)
conditioned on the event that exists. We denote F [GG C) + ....... (GD (GD CJ + W))x Bu where (G- C'ü + W))p is the p-th n-th dimensional block of the nk-diieesiional vector (GD CY + WW) Recalling the definition of D, we have that Vi+1 V (U*) F.
In order to evaluate the final bounds with label noise included must bound the following terms
Vv (UVV
and
1
Vu (U.)).)
nb
in spectral norm.
Proposition 40. With probability 1 - O(n we have
26 log(nb)
(1)
(1.) s
Furthermore, with probability at least O(n - 10), we have
1 (U(V <
4
2
ed
(2)
nb
3
nb
Proof. Claim 1:
With probability 1 11 log(nb) we have
1 v Vv (V) S
26R2n 26R2nlog(nbb
b
b
Note that for any given p E [n] and q E [k]]
p.q
p.g
1 Σ
V. VV-1 F)
b
((d))(m))(mm
P.g
Σ
Ve Un Von))))
b
P.g
b Σ
Giserat
P-g
Sos (opls
30

---

Private Model Personalization Revisited
for "gt the y-th column of Uz- Observe that Sp independent of both zp.. and Ug.e for all [m]] Condition the event
3 = - - Rv 26 log(nb) for all (i.j) E [n]] x [m]]}
which has probability at least 1 - 1-e--3log(nb)) Via this conditioning the random variable Spld (Tpu Mq.s) is RV 26 (og(r sub-Guut Gaussian given that (1ps My,t) is Ssub-Gaussian. Note as well (p. (Tp.5 Uy.e) is mean zero and independent for each So, 1 Σi= Sp.s (Tps Ug,1) is centered, v
26 log(ub) -uu--uu-uuu Suub-aussiin, and independent for every p.
Let 6² be the variance of : Ee Snu (Tnni Uqa), which has S has covariance matrix k.- By the one-sided version of Theorem 26
26 (og(nb)
Then, ( ma Ei= Sns ( Unst))
b
gE(a]
Vv (VV((V))) So 10s ( Vk vk+
imax
mo
with probability at least e Multiplying through by and setting a = v we have
26 26 log(nb)
v (V(A(V+2(U))))) V
with probability at least e conditioned on the event E. So, in general
26 log(nb)
Vv VV(A(V S
with probability at least e - e-2 lug(nb) 2 - ---ell log(bb), This proves our first claim.
Claim 2:
With probability at least 1 - O(n -00), we have
1
4
2 dd
Vu (AVV=
nb
3
nb
Note that
1
Vo (U.V Vo
Si A Vi+I(UI)T
nb
nb
1
Vu
Si (Ve+2) Aag. (U))
nb
1=1
F
Vū
Sed ( Ve+i Ue
nb
1=1
n
b
Se, (A
V
nb
Observe that since (T is matrix with one non-zero column T/.3- we have (Ais) (VLLt)) where 6,,+1 is the i-th row of Ve+1. Let Ard and A be Euclidean + -covers of the and k-dimensional unit spheres, respectively. Then, by Lemma 23
Seg (Ar Vi4
Saga
nb
nb
4
T
nb Σ
3 REN' bENE
4
Sez 2 (Vx.c..)))
3 oEN
nb 1=1
31

---

Private Model Personalization Revisited
Let 104411122 S [ for all i with probability at least O(n=14) via Proposition 42. As well, condition the event
5 T for all i simultaneously
3
|lo.ttllle 5 4
which has probability P [|E] 2 O( 13))
Since (0,,++1, b) S T by Cauchy-Schwarz, the random variable C. (a, (11,41 b) is sub-exponential. Furthermore,
the variable Sty (a, و (vi,1+1 b) has sub-exponential norm bounded by 125RT I from Lemma 22 conditioned on & and for nh 2 15d n, we have
2RT and is mean zero. Following nd
4 3
2.
2i S
3nb
nb
with probability at least - e 15d log Via the union bound over No
b
b
1
Σ max
Ses (a, (ora4..) b)
nb 1=
3 DENE nb
2
2 15R
3
nb
with probability at least log
gettee
logn
Let be the event
4 2 1dR
E
(A,() Vi+1 V
nbb
nb
Applying the fact that P
< E[
+ P|e
I
10d log n + +Onn = OO 10) finishes the second claim.
Recall the following definitions given prior to Lemma 39 where Av.s = e.p.y
Denote
Gp-9-
(e E Rx"
b
1
Cp.
(Aig (Ais)na(y)) (Ais)) E B
b
(31)
i=1
j=1
Dp.4 = -uup,es Inxn E Raxn
W
Aspuppp ER".
1=1
Take G.C, D be nk x nk block matrices with blocks Gp.g Cp.gs Cpgg and W an nkkdimennional vector created by concatenating W, for each p [b). Let GO C,,C D' be the l x k matrices formed by taking the i-th diagonal element from each Gp.q Cp.q. p.q. respectively.
Let
Lemma 41 Let Th C+
35k logn for some e 0. Then
1
(1) ||-
1|2 <
1- 7
with probability at least 1 O(n 13).
Furthermore,
VTk
26 26 log(nb)
(2)
|| S 1 Tk
rd 12iss [ddist(U,, (U, +
(1-Tx)24
with probability at least
-I1)
32

---

Private Model Personalization Revisited
Proof.
Claim 1: We have
| S
1 - Th
with probability at least e 13k log
Let be a normalized vector in nk dimensions. Define ot E I to be the sub-vector of a constructed by choosing each ((p 1)n + i)-th component for p 1, I,..., k. Observe that
min [G) min a Ga
a:]|e||2=1
Σ a Gia 1=1
min ai]|e]|2=1
2 min mmin (G").
iE(n
Let II' "T' Eyn By our definition below (31), we have G U. UT Note that U. #ig vB and independent for each i,j. Assume 2 k. Then, using a one-sided form of Theorem 26, there exists constant e, >> 0 where
1 Su-uuGaaussaan
miin (U, ITU,) 2 1 - cr
(vb.
h
w
vb
with probability at least e Setting v44 log gives
Mmin (G') 2 1 Tk
with probability 1 - -14k a for as in the lemma statement. Via the union bound over E [n]]
min (G) 2 -
with probability at least 13k no
Claim 2: We have
[F p S
UTk IV
(2dist(U, +
26 26 log(nb) (1 2b
1 Tk
with probability at least - 2e 13k-13klom logn e -111 log(nb)
The proof follows from bounding H G Dd for each E [n]] spectral norm with Lemma and exploiting the definition of our parameter maX:e]|] |0]
Gwas.
Let X; be the design matrix for m Fi Note that, by the definitions below (31), have
1 (U.) TxT X.(U.(U)) -2) G'D' - C' -U)) - UTUU -
Then
[[GD - Ceec Σ 11 (x;)
H 11
||V*13 Σ
11
1=1
and
[GD - Vec
|
Σ
H...
(32)
1=1
33

---

Private Model Personalization Revisited
We now bound each H' using concentration inequalities. Define A X,U and B J8 XUUUUU Ia)U We denote the rows of A and B with at,j w (U,))) zi, and b.j (Ui(U)) - Ia)aa.s. respectively. Note that, for for. Mo a Euclidean -cover of the unit sphere in lo dimensions, we have
|B All2 2 max u TB AT EN
Σ bes uf
T a.N'EN'
max
b Σ
max EN
(u, (aiss vl)
via Lemma 23. Now, fix some (u, E No x * Then, at, = 1 (U)) Lij and b,, = U.,(U) - -a) So, (u, (ig) is - Gaussian and (big, u') 5 dist(U,, U*)su,---)ssuaaaaaae Gauussaan. This means their product 165 dist U*}- AvB
vb
TVb
sub-exponential.
Now, from Lemma 22, there exists d' > such that
IP H 23} SP
Σ
Yn, be (ar u²)
u, WN E
g2 e
-d' -cbmiin 2.s0uR(tie [1*) (
Let satisfy 16dis(U,.Ur) max(T; (A,((TTT)) 72) Then
2² min
8 2.5dist 2.5dist U-) 1.6dist(U,, U*)
Picking 72 14k logn and assuming that b 2 11 log n ensures ob
35dist (U,, y* log n
P 11'12 2
< log
(33)
for any fixed [n]. So
k llg n
PP
[GD - Vec
35 [| (U,, U+*)
22
llg
S
P
H 35v 1 | | ||dist (U,, U+)
n
b
2
k log n
<
H' 35 dist (U, U*)
n
35dist (U., U+) A logg n
< nl
|
Se e
13k log m
where the first inequality follows from (32) and the last inequality follows from (33). The rest of the proof follows from
the fact that = [ [G- ((GD C-s + W)), ... (G- C)Y" + W))]] That is, we bound G G-I(W, |W...., Wi
via an application of Claim 1 along with Proposition 40 part (1). This gives bound on the norm F = [G GGD
C)ū')...GG1((I1 - G-l W&] by the union bound.
34

---

Private Model Porsonalization Revisited
Let fa be the i-th row of F in row vector form. Also, recall that G", C',CK, D' are the k k matrices formed by taking the i-th diagonal element from each Gp.q: Cp.g: ppg as in (31).
Proposition 42, Suppose Assumption 31 holds. For all & [T [ 11, have that vi++1 from Algorithm I satisfies
110441122 S 5 r
with probability at least 1 O(n all i E [n].
Proof. By Lemma 39, we have (as row vectors) Ui,++1 = (U*) ft. This implies
10,,41122 S [[[Tlal((U*) Uill
"TTall(U"TTTlll + llfelle
and so ||o,e+ill 2l2 S r + 1|Al22. Fix E [n] and assume that LTk. < 1. This is not difficult to achieve when using
Assumption 31. Recall that we defined 7 cr 35k log log Now, denoting the i-th row of matrix with (M)s,
11112 = G
+
Si
A1JU2
1=
j=1
b
s | G DD))))) + ||G ||G+
1
i
j=1
2,0
VTk
40R k log n
|| dist(Ue, U*) +
7k
)bb
VTk
40 logn
r +
1 Tk
(1 (I-Tx)²2 Jb
with probability at least 1 - 2e -14k log(n)
e 14 log(nb) via the argument of Lemma 41 part (1), and the same arguments as
Lemma 41 part (2) and Proposition 40 part (1) applied to the vectors G "G - -D))(u))
and ( Σ {,,
Now, assuming that m 2 4000c² max (R2 .) (mx.)xmmmmm1....) (1))
log" "R Eo
"T and m 2 4000 R** lom,m)), we have
VTK T+
40R*klogn r
S
1-Th (1-Th)² )b
Taking the union bound over all finishes the result.
Lemma 43. Let Th = -5113
/
log wh
Suppose Assumption 31 holds. Then, we have, for any iteration t, that
-
V++1
n
2
3RI /15.
15. 24dk log(n) log(nb)
(nb) 4
with probability at least 1 1nn-1))
Proof. Take W = (WI,..., Ws) E Ruk where W, = -'''E''' AijAijup.. Recall that F = 1I- C)J* + W)).... (G- + W))x E Raxk by (30). Define W- =
Let Q, be the matrix
defined via rows q, where
q UU( U.()) - T
35

---

Private Model Personalization Revisited
Finally, define by Qe the matrix with rows T..r = qt,t 1.4--Wi (U)) where W is the i-th row of W. Note that
-V -V()))) -V++ -V((r)))) T
V++1
(34)
((u))aa))))))) ã.) -.)" V4+1
+ -
T
Ve+1
2
The lemma follows from bounding the right-hand terms individually.
Let o = 15
log
nb
Claim 1: We have
( (()))
V++1
S { U*)
with probability at least - e 10d log
2c
133 log
Note that
10:l2 - ([U)(U)) (r) ( (IU((A)) - U.(W:) 1/2
< [dist(U,, U*) + 1-11/--ii (01--Wy W:ll2.
Now
Ilf -:ll = |
lle
vTTH
I d U*)
Th
with probability least 2e log via an argument identical to Lemma 41 part (2) without the label noise term. Choose
cu 2 1000c² in Assumption 31 to ensure VTx I J. Then IIfe - Wlllz N dusst(U, U*) and hence 11% S dU, U*)
with probability at least 2e 13A 134 logn.
By Proposition 42, have ||0,,411122 & Ir with probability at least O( (11) for each i. Observe
nb ( Va++1 = nbb
1
1
Σ
(1 (1..), (.o(().e+1)))
We first condition the event
8 = || S 2TdistUU,,U) and ||us,e-1l12 S T for all E [ml]
4
which has probability at least - Onn-1) by the union bound. Define the Euclidean f-covers of the d and k-dimensional unit spheres Ard and A respectively. Via Lemma 23
(11)) - -(e((s))1
nb
b
4
(1 (a aeg b) - (a, (u.)eu b)).
max
3
N bEA' nb
The variable (oly. R..) is 21 dist(U,, -'o--""*"-GGussiiii and (a, ) is 4-sub-Gaussian via Proposition 18. This means (.l,,- (a, o( is sub-exponential with norm d U*). Then, the variable d (2 q1.)) (a, 2( (vr,44, b) is sub-exponential with norm
5r dist(U,,
5 < dist(U,, U*)
nb
nb
36

---

Private Model Personalization Revisited
given that have conditioned on & Note that the variables ((4 W.)) (v(441) (. are centered.
Furthermore, due conditioning concentrate these variables with respect the randomness 2 since they independent of Ri 04 So, by Lemma 22 there exists constant c' >> 0 where
P
2 2s E
nb
(35)
2
5² 50L dis U+)
s gdth exp
I min
From (35) we denote 7² min
U,, (r
a and further set 72
13(d+&)oog c'ub
nb
13(d+k) log
then
Midlog nb
P
26V13dis(U1
== S gott ε -13(d+)) log n < log
Recall that P[E] 2 1 - O0n-1)). Therefore, we have
I'glog n
2 25v13dis(Ur,.7 U*)
nb ==
nb
(36)
2
+ O0n = O(n-10).
This proves Claim 1. Claim 2: We have
-
3R1 /15 24dk log(n) log(nb)
15
Ve+1
(nb)
2
with probability at least O(n
Observe
(i(U:)T) (AA')t'(W,(U))) -W.())) T nb
V4+1
n
6
(oh.s) W.(U.) (ol - W.(U.) (T.C))(( (ou)))))
nb
Note that the random variables (x W.(U.) (1 (w,,,))) T have mean zero since s/, and (U.))
are independent along with E (U.) = Using a covering argument identical to Claim 1, we have
- W.(U.) ( W.(U.) - (vLo+i)))
(37)
n
(ol Ma. (a, W,(U)) (o....))))
max aeA \* " nb
Recall that W.
1 Tub
EE Eラ=1 Gi (1EA))))))))))))
+ Conditioning || || S T, we have |Wila
1,x
by the union bound on the components of W. Multiplication by U.T on the right does not change this bound given orthonormality.
5/T (og( with probability at least ke 12 log(6)))
> 1 e 11 log(nb)
4vub
37

---

Private Model Personalization Revisited
We thus condition on the new event
5RT v 24k log(nb) ع ビ= W.UU 1125
4 4vmb and le S I for all E [n]
4
which has probability at least 1 - O via our above work and Proposition 42. The variable (11 (U,) is -sub-Gaassian via conditioning on E. This means
5RT /24k log(nb)
4//b
1 (wig) (.ll))W(U.)" W.(U.) Xa, (1g) (vart,))) - (a, (V.
nb
3RI V 24h (og(b)) Vn
is
-ub-exponential. Using argument identical to how we showed (36), the inequality (37) implies
wi(t)) -
(
3 V 15 24dk log(n) log(nb)
V
(38)
(nb)
with probability at least On - -10). Combining (36) and (38) via the union bound finishes the second claim.
Combining (34) with Claims 1 and 2 via the union bound finishes the proof.
Recall the exact statements of Assumption 31 and 32. That is, there exist co. 01 > 1 such that
m R² 1) max 1 1) log" R
log(rm)) T
m co
+ T
F.g max,
and
max (De,s, 6, 1) (R + T)Tdyklogg
R R
ci
E
m
T.
Lower bounds on the constants co, Ci are used many times in the proof for the following lemma.
Lemma (Restatement of Lemma 33). Let Eg = 1 - dist (Co, U*) and vi = Ō and 32 hold, Then, for any iteration we have that Po+1 is invertible and
Suppose Assumption 31
11 min,
2
Eo
| 2
1
v2 log
n1
with probability at least 1- Onn-n(nn)))
Proof. Recall that F = GGD - CYV* + VV and let To = C
35k log
15 15/13// podlogn for some constant c > 0. Letting 2 2000c² in Assumption 31, we have I-Th S 4
1
and noting
nh
3
||G 112 S 1-Th by Lemma 41 part (1), we have
4 |P S 3 /TT + 47 log(nb)
(39)
b
with probability at least 1 0(n (11) via the argument Lemma 41 part (2) for the spectral norm.
Recall that Qi (U)) V*(U*)T and V2 (U F by Lemma 39. Now, denote H (Q.)) + nbe, H. = (AA')t and W. = 3/ Vu (A(V+. T), C). By Recursion 28, we have
P = 0,41
= =U.)) U.
2 (UU)) T Hi + UU) + ((U.) W, + (W.) U.) - [((()) ((W.)TH H (.W.)) W.)
n1
122 + //2 (H)) T H² + (W.).w. W
38

---

Private Model Personalization Revisited
By Weyl's inequality, the above implies
" min (P2+1) 21 Xmmx((UU)) H.V++1 (H.)) U.) (min)(U)) (.U,))We>) + (Wi)
n
? Amax ((W.) 11V441 (V++1) (11) ((l,))T(,, W.) Amxx((Us) E + +c Us)
n
n n²
Amax ((W)) &e + se Wi) + Amin((H))) H1) + Amin ((W) Ws) (Wa)
" 2 Xmaxx((U) V441+ + (V411 (H)) UU) + Amin ((U)) T W; + (W))TU) W)) - Amax ((U)) T & + E, Un) Xmax(((W)) (WW))H&Ve+ + (V4+1) (H,, (
n
?
H.V4+1
n
Amax((W)) & + W.).
To complete this proof we must bound each of these terms individually. That is, we upper bound
? Amaxx ((U:) ((U.)TH.Vi+ H,V4+1 + (V++2) (H.) (H))T,,)
(40a)
Amax
(UG) + U.)
(40b)
Amax
(Wa) Ee + El Wo)
(40c)
?
Amax
((Wi) HHV4+1 + (V++1) (HH,))((H)) (H.)TW)
(40d)
n
and lower bound These bounds follow from our previous propositions and lemmas.
Amin ((U)) We + (Wa) (W,) U.).
(41)
Term (40a) has
Amax ((U.) HeVe+ + (V--1) (Ho)
"a (U,) " H.V+11 + (HH) Uua
max ||a||==1 n
2m T (V+++) HHUsa
max ||e||a=|
2111 a [VV++2) ((4))1((Q)-0))) -Q.) U max
2n T Q,Uaa TVUUa) ||l|z=1 n
< max [|a]|==1 n
We have
2n T (V-I)T ((())))())) Q. Usa s 20rté
3RI2 /15 24dk log(n) log (nb)
lal2==1 n
(nb) i
by Lemma 43. We are able to drop the second term on the right-hand side above later due to its very fast rate of decay in
n, b. Now
21 T
2n (Q,, Vi+1aa (U;))a((UT))) (U:)T)
max || |0||=11
(VVeu))QQquaa=
QQUha= = max
||
2m
2n (Qu Faa T (U.) ))p)
(Q,, V*(U)) (U,)T)
max
|
m
n
We bound the first term above via
39

---

Private Model Personalization Revisited
29
(Qn, " U,aa" (U,)))p
2m
tr (U1) (
n
20
(*())) Usaa" ((aT(()))
n
201 tr
27 tr (U))
21 tr (())
21/ tr (U))
(42)
π
20 (aT((F)TT))
(U))
n
217
20 ||
n
8
VTk
2 max,+ +
2 R max, log(nb)
3
3
with probability at least 1 O(n (1) by (39), where equalities 3 and hold by the cycling property of the trace and (UU)), = 0. Then
29 (Qr, Faa ((i))(())
21 tr
-((())- - Faa T (U,)
2n ir -T) Faa (U,) F(U)())))))))
2g tr (Faa" (U,) U.(F)T)
n
2m1 ((F)
(43)
Fa
Y1.
< 211 1
16
154n² R² log(nb)
< 17 (1 )2
maxx, +
with probability least 1 - Onn where the third equality follows from the cycling property of the trace and (UU))U)) = 0. Combining (42) and (43) gives us
VTk 21 (V(++) S 81 72)
1547² R² log(nb)
max ||l|a== 1 n
o max,*
b
given that 7h 5 Tx by selecting co 35c in Assumption 31. Define we have
UTk +
Letting Co, Ca 4000, for (40a).
Xmax ((U.) H.Ve+1 + (V-1) (H.)TT) < 2nT + 811 (1 Tx) )2 max."
UTk
154r/² R2 log(nb)
47n² 2 R² 0 o log(nb)
3RI V15. 24dk log(n) log(nb)
+
(nb) $
Tk
17m2 R2 max
1) log(nb)
< 817
4
7xk )2
max,,
b
40

---

Private Model Personalization Revisited
Note that (U2) Ee in (40b) is k x l Gaussian matrix with independent columns. Now, by equivalent statement as Corollary 27 for l x k matrix
Amxx
max a (U,)) & Ura
a:||e||a=1
=2 2 max a (U.)) Eea
a=||1|211
- 211(U)) Erll2
- 22v + w)
for w with probability least 2e- 2e-a" for some constant d' > We select a /10k logn, n, which means
Amax ((x)((U))))))) Ee + +T z 4nō / 10k log
with probability at least - 10)-
Now, for (40c)
Amax (WW) E, Wi) max a ((W)) & + E, Wi)a aa|===
max a T E: Wia ||l|a==1
< 2||5r|l2||Wall
4 2-
T log log
< v 10d
31
nbb
with probability at least 1 - O(n-1())))))))) via Corollary 27 and Proposition 40 part (1). Now we bound the term (40d). Note that
7 Amax ((W,) H.Ve+1 (W.) + (V,)))((H,) <
27
[(A) A'
||oll2
n
27 (1((614)/4100)) - -Q: Ve+1 + +1Q.Ve+alle) I1aal22
(44)
dist U*) + 2T n |QQV++all2 ||ill2
by Lemma 43 and taking co 4000c and c1 4000 from Assumptions 31 and 32 2 U*) is dominant over the noise term. Then
7 Amax (W.))H..Ve4 H.V+1 (V++1) (H.) W.) < UT) U*)
2n
(1Q.Venlla)) ||all2.. (45)
n
n
Note that 2T. U*) < 1 by taking co 2 4000c² and e₁ > 4000 from Assumptions and 32 since 7 loggn Then, by (39), the orthonormality of U., U" and the definition of Q+
5v 13
1QQ < (U)) (U - -
Fll2
< (2/1V" + || [11 + [1112)
47R² log(nb)
47R2n log(nb)
(2+ 2 V +
(1+2
b
47(2 + 2UTH 2 V n log(nb)
47 47R2 log(nb)
$ (2) + 20TH) ) 1
b
Then
27
Q.V441112 S 2nn(2 + 2
+ 5
39
471 R22 02 maxx, log (nb)
154n R2 log(nb)
(46)

---

Private Model Personalization Revisited
by selecting the constant co in Assumption 31 have co 4000c such that WTk S 1
Recall that
10
4 2 15 Rog Wall2 S
nb
with probability at least On 10) by Proposition 40. So, combining (45) and (46)
Ama ((W)) (.WW))THVee... H4Ve+1 + (V++1) (Hl)) W;)
2 122 lo
2 15 + VTA
R max, lnb)
V
nb
3
nb
2. 15n/ 2
39
47122 R2 o max,+ log(nb) 154n log(nb)
+ 3V
nb
5
with probability at least
O(n -1). Recall UTB
S
since co 2 4000c Moreover, for e 2 4000
10
2 15n² 2 log
dox 2 12 + 2nTx) 2 R do max. log(nb)
3
nbb
31
nb
2 15n R 2d log n
39
47 R max, log(nb)
154n log(nb)
+
V
3
nbb
5
2 RP12 max ( 1 log(nb)
<
3
nb
by Assumptions and 32.
Observe that for (41)
Amin ((Un(( W. + UW) 2 2Amin ((U)) Wx) 2 ((Am)((UU;) Wa)l
((U))
and
2 mmnn (U,)) 2 20 ((U,) W.)) 2 -22 (U,) W2))-
(W,))
Note that concentration inequalities hold for the sum of uncorrelated sub-Gaussian random variables and U,T having orthonormal rows. Then, by a modified version Lemma 40 part (2) for a k x k-dimensional version of W.
o m (UU)) TW))
max a (U,)TWC W,a ||a||==1
S II(()) TWalla
4
15r/2 (2
3/
nb
with probability at least O(n (19). Notice that our upper bound is independent of the data dimension d. Thus
8 2 15n2 R log(nb)
Amin ((U,) + (W.) U.) S 31
nb
Via the above work we have, simultaneously by the union bound, there exists a constant è such that
2 max naxa 1 log(nb)
! Amax ((U)) H.V++ + (V++1) (H.) (H.)TU, (H.)) Amax Xmax((U;) (UU)) + {TU,)) < Enj / logn
TU.) S c max.*
b
R2 1e log n
Amax ( ((W)) & + E, W.) < èفف / dlgg
nb
(47)
R2 max (oaax. 13 log(nb)
17
*masx((Wi HAV4+1 + (V++1) (H.) W.) sa/
n
nb
Amann ((U,) W, + (W,) (W))T,,) s <./
nb
42

---

Private Model Personalization Revisited
with probability at least On 10). The value of may change between lines. Its precise value does matter and this constant is used simplify proof. By our choice of 1b, we have 5 0 [R+r)rvTa (ogb ) Putting together the bounds in (47) and selecting cu 2 4000c, and c1 4000 in Assumptions 31 and 32
ne
0 min (Pz+1) 2 B - Enjō v log
11 R² max imax, 1 log(nb) ēnj /dlogn
R2n) nab
-éV
1) Ro[2)) EV
R m 1 log(nb)
nb
nb
21
Onpik = 22n0 V dlogn
R max [ 13 log(nb)
112 Re max maxx. 1 log(nb)
eV
b
nb
with probability at least
On 10). Via our choice of 6, there constant è such that
267 R + d)dd
Th (1122122))) (nb)))))
2 (P(+1) 21 ENTRO max,.
ne
n R2 max [T2 1) log(nb)
1 R 2dd max m max. 1) log(nd)
-20
8V
nb
Recall again that T Cr
35k logn
Thk 5v
rldlog and mb
Omax, > 1. Then
TfT max,*
YuPRO max,+
" + TIT
35k log
dlog n nb
c-nvo max,+
+ 5v 13m3222 max,+
Recall the exact statements of Assumption 31 and 32, That is, there exist co, ci 1 such that
maxx R2 1) (1x log" + I
R2
cu
log(nm))
T
and
max {A 6. (R+)) (mm))
do
ci
EEA2 X2
T.
The problem parameters that lower bound m, now come into use during the following steps. Furthermore, recall that by Assumption we know some À > 0 such that À < amin... Then, there exists a constant > 0 such that
onpinn Eo
2 E3
O max,
Vco log
coc1 2 2k2
(nm) logn
and thus
ono min. Fo
E3 c001 2 log" (nm) logn
Eno 2
min.
(48)
Vco log
43

---

Private Model Personalization Revisited
since X S min,. Further, this same constant satisfies
2on( R + r
Tllog(1.25/00 log (nb)
11 R2 max(T², 1 log(nb)
+ BV
b
1f R { ( + lJ log(nb)
cV
nb
20n22E3 E
+ eno min, Eog max } log n
C1 v log(nm))
max(xmaxx. 1} co0 max 1}k2 2 log (n) (o))
+ Amin Eug
and thus
Tk log((1.22//0) log"(nb) 28n( R + r)
2 R2 max 13 log(nb)
+ 8V
b
R max
maxx 1 log(nb)
cV
nb
(49)
20n0 min.*
1 + èng min, min, Fo co max (T2 1] logn
a AVog((m)) (nm)
max m
+ Enjo min,
E
COci max 1) log" (n))og(mm))
since X S m Note that FB < Eb since Fo E (0, 1). Then, combining co, c1 2 max(10v22, 10/222 40000,, 4000) with (48) and (49) gives us
min, Eu
iin (P++1) 21
(50)
2 log
with probability at least 10n-
44

---

Private Model Personalization Revisited
B.4 Private RedRep experiments
In this subsection describe the synthetic data experiments we designed to compare our Private FedRep (Algorithm 1) the Private Alternating Minimization Meta-Algorithm (Priv-AltMinn of (Jain al., 2021). Our comparison is described in Figure 2 as graph of population mean square error (MSE) over choice of privacy parameter 0. Note that also experimented with non-private AltMin, which performs similarly to the non-private FedRep in Figure 2.
2.00
1.75
1.50
Population MSE
1.25
Local optimization
Non-private FedRep
Private FedRep
Priv-AltMin
0.75
0.25
0.00
8
User-level Epsilon
Figure 2: Graph of population MSE over choice of privacy parameter E [1, Local optimization is done via non- non-private gradient descent on each user's data separately and their population MSEs averaging over users.
The features E Rdd of our synthetic data are sampled from standard normal Gaussian distribution. We select optimal parameters U - vi...., by sampling U from a d x k-dimensional Gaussian distribution then generating an orthonormal matrix U via (U", P) = QU) and sampling o." ~ (0, I&) for all E [n]. Labels are generated as Assumption and we choose Gaussian noise with standard deviation R 0.01. Further, both Private FedRep and Priv-AltMa are initialized using an implementation Algorithm 2.
Our problem is instantiated with d = 50, 1: deciding T 5 and learning rate 1 2.5 with clipping parameter vi 10. Similarly, Priv-AltMin with iterations optimized for T = 5 and clipping parameter 10 The Gaussian mechanism variance for both algorithms is calculated
10, and 20, 000. For FedRep prune hyperparameters,
using the privacy parameter A.,5 /16 (1.2/
with ò 10-6
45

---

Private Model Personalization Revisited
C
Missing Proofs for Section 4
first restate our algorithm along with some initial definitions and results.
Define Bp {U Rddk | v2k}. Assume for simplicity that m is even. We also partitioned S; S U S (mm.) (24+1.)...;;a : for each i [n). Further, we denote S ( ........... 5%
where 5 (.1.j....,
) ( and S {2
where & E {0,1], Suppose that S = (Si...., Sa) C Iam(d+1) is a sequence of n datasets with m samples each. Let SM ((S)) (Sn)ar) where (S)) M = ((Mai.j 9h.5) : [m]] for all E [x]
Algorithm 3 Private Representation Learning for Personalized Classification
Require: dataset sequences 5 and S of equal size, score function f(U', -)= minvey (U", SUU,VV V; over matrices U E R xk privacy parameter > 0, target dimension k' = ,- log(mm/m/
1: Sample M E IR xd with entries drawn i.i.d uniformly from {
{+ 111
V
2: Let S. = ((Si)ar,.... (s) where (S,) {(Ma,y) : (x,, y) E ( for i [n]
3: Let A be Frobenius norm 7-cover of BF
4: Run the exponential mechanism over N privacy parameter sensitivity n. and score function f(U", Sar), ) to select
U E
5: Let UTiiv + -U
6: Each user i [ni] independently computes qtth <- arg pelle T(URi ,. (!)
7: Return: UTaav Vpav [
priv
Definition (Restatement of Definition 13). Let (U, v) E paxk x R& and (I, E Rd x {-1,1} any data point. We define the margin loss as
ED(U,u,2) 1 (v) S
and denote the 0-1 loss
A(U, u,) (o(U, = [u(a, Uv) S 0]
Definition (Restatement of Definition 14). Let G C Id be any set of t vectors. Fix 3 E 1). We call the random matrix (JL) transform if for any w' E
M E R x'x (t,,,8)-Johhn (0,r))))oonnson-indeeess [Muu Mu') (u, w')l S T|lu||2||ul|1
with probability at least - |3 over M. Proposition 44 ((Woodruff et al., 2014)). Let C R9 be any set of vectors. Fix r, E (0, 1). For M e Rkx (t, (,)- transform for any G
(1-t) S - (1+
with probability at least 1 3 over M, which holds simultaneously with Definition 14.
Lemma (Restatement of Lemma 15). Let t, B E (0, Take G C Rdd to be any set of vectors. Setting k' O log(
for a W' x matrix M with entries drawn uniformly and independently from { VK transform.
111 implies that M is a (t, T, JLL
Lemma 45 (Lemma D.1 (Bassily al., 2022)). Fix B E (0, 1). Suppose U Baxk and that 2i,j Rd., Us R for all (i.j) in] [m]. Let M e gx'd xd be ((n 1)m, 7. -I transform in the sense of Proposition 44. Then, there exists constant 2 1 such that, with probability least 3 over the randomness of M, we have
log (nm/3)
|M 5
1 o
||
(1)
(1 1 op
log (rmm/ 33)
MMUIE S
(2)
k
46

---

Private Model Personalization Revisited
U M TOTTMMAN Mans of U UTris S c||UvillalIza log (nm//
k'
for all (i,5) E [n]] x [m]] simultaneously.
Recall that U is the space of orthonormal d matrices and V the set of k matrices with columns whose Euclidean norms are bounded by r > 0. Throughout the following results we assume that r I cV /log(wm/)) for some constant k'
2 1 and target dimension k for a JL transform. Furthermore, whenever define JL transform M, we assume that it preserves the norm of data points 2 for all (i, E [m] x [m] and some fixed matrix in U E U. Let W be Frobenius y-cover of the -2k-radius Frobenius ball By. By cover mean that contains the center points of Frobenius balls of r-radius whose union contain BF. Note as well that N'T C. BF.
Proposition 46. Let M E øk'xd xd be a ((n + L)m, 3/2/2)-LL transform in the sense of Proposition 44. Assume e log (nm//B) S W and that Ti is a sequence of r-bounded feature vectors for each (i.j) E [n] x [m]. Suppose No is a Frobenius norm "y-cover of the k x k-dimensional 22k radius ball. Moreover, let U E u and Ú N where I MMU S 7. Then, there exists constant 2 1 where, with probability at least - 3 over the randomness of M, we have
log (nm/3)
MXis - Ui U 2in s <VV2+ 1erryV oo UTUMMaY
+V2+1)crTV
W
for any V= [uu va] V and all (i, E [m) [m] simultaneously.
Proof. Note that since U has orthonormal columns, we have ||Uball2 110/ll2 I I for all j. So
log (nm/3)
U T M MMMs of U anal sorVy
(47)
k
with probability at least - 3 by part (3) of Lemma 45. Recall that 7 S log(nmm/ R²
for some constant e 2 1. Assume
2 log (nm/3) S K', which implies 7 S 1. Let Bp be the k' x k-dimensional Frobenius ball of radius v2k. We define No to be a Frobenius norm 7-cover of Br. Note ||MU|| S /2k with probability least 1 by part (2) of Lemma 45, That is, with probability at least 3. there exists Ü E N such that I|Ù MU S 5. Let Ü E N be within y Frobenius-distance of MU conditioned on the event ||MU]| $ v2k.
Now, there exists constant e 2 such that
0 Ü Mzza- TT M M
- <1evlla| UT MZ2, - U M M.Masll12
- ||wallali MU]
S V2rl'
s /Verr /log (nm/B)
where the third inequality holds by part (1) of Lemma 45 along with our choice of U and the fourth inequality by our choice of y. Hence
0. Ū MXx is U M Mass| s /
log (nm/3)
(48)
le
with probability at least proof.
f.. Combining (47) and (48) with the union bound and triangle inequality completes the
Lemma (Restatement of Lemma 16). e, > 0 E (0, 1). Algorithm 3 is (c, -useer-eevlll DP. Sample S ~ D Then, Algorithm 3 returns Upev from input S such that
(,2T21
min L(vo VeV
V:5"s
min (U. +Ö
(u.V)euxV
cp2n
with probability at least over the randomness of and the internal randomness of the algorithm.
47

---

Private Model Personalization Revisited
Proof. Let M& Re'xd be ((n + 1),, -/ transform in the sense of Proposition 44. Further, let Bp C R be the Frobenius ball of radius 22k. Recall that y S ev 10
log(nm/ for a constant 2 1. Assume c² log (nm/3) (3) S k', which
implies I 1.
Define Vir E orgminyer L, V; S) for each U E Bd and fix U E arg minyreu L,,, Vo;; Denote the columns of Vy U1...., On Let N be a Frobenius norm y-cover over By. We have ||MU|| S /2k with probability at op
least 1 - 3 by part (2) of Lemma 45. Choose 7
(v2+1)erT for some constant a E (0, along with Ü E EN> within
Frobenius distance y of MU conditioned the event | S V2k. Then, by Proposition 46, for all (ž, [na] x [m] simultaneously, we have
D Ū MNnj - u U Fijj S ap
with probability at least
2.3. Assuming ap 2 0, the above implies, with probability at least 2, that
i(M Ú, VTT:: = i(M U, Vu:S") S LU, Vo;
(49)
where the left-hand inequality holds by VI being minimizer for L(MTÚ, S.).
Let U E arg mingree i(MTU' U", VMTw;S S.). Then, by definition of Ü and the fact that No CB, have
T(MTU, VM S T(MTŪ, S,NTU,,TTTT 5T)
(50)
Let (8 {MMri :r.):: [m/2] for all i [m] and SM ((S)) This definition and the characterization of our losses in Definition 13 imply [(U VI Shr = L(MTÜ, VM Via the exponential mechanism over N given score function - -Ī-(U', VM for U E N and the usual empirical loss guarantees for the exponential mechanism, we obtain Upri Raxk where Updvv T Ū for some Ü A such that
/ogg/\71 en
[(PPA SU)= L(Ū, V. MT Sh) s L(U, V S +0
with probability at least
3. This gives
p2
rTvE (nnm/3))
log
L( Voww S S o:
p
(51)
6p2n
(( k'k and K' 0 2r log((nm/33) by our choice of Combining (49), (50), and (51) via the
since = union bound along with recalling our definition Vir E arg minver (U", vV))) finishes the proof.
Theorem (Restatement of Theorem 17). Fix c.p 0, E (0, 1). Algorithm (c, -)-user-leve DP the billboard model. Sample user data S D Then, Algorithm returns Upriv Venv from input such that
2
r2?
L(UIii Vriv, <
min (U.V)EuXV
(U, +ō
nep2
mp²
with probability at least - over the randomness of S and the internal randomness of the algorithm.
Proof. Let Vpiv E be the matrix with columns Tith E arg min j T(UDiiv ur St) and V. e with columns i arg min sr [(Uprrv v; SQ) for each i [n]. We first that
L(UDiv ypiv; D)
min (U.V)ElXX
In(U,V;S)
(L(UURIV ypiv, L(UNiV , V:D)) + (I(URRN [LUDDN,V;D) ε(VPiv, v,,5)) {(UPi,, (52)
(EACOPIn (, min (0.V)EuxV
C (U.
48

---

Private Model Porsonalization Revisited
Let M E R be ((n + 1),, 7, 8/6))- transform in the sense of Proposition 44. Let y = cV
logt (1m / for constant
0 and O (.+). Assume c² log (nm/8)= s k', which implies 7 S 1. Denote by By the k' x k Frobenius ball of radius V2k. Let N be a c-vover of Bp. Using Lemma 16, we have
(r9 Eppn
[(U V:
min L. =0 (U.V)El
(53)
with probability at least 1 - 133 over the randomness of M.
Claim 1: We have
L(UPiV, ; L(UNdV V:D) =0 (v
with probability at least 3. By the definition of Vpriv, we have
i v S L V':").
(54)
Our proof strategy is to obtain generalization error bounds for the parameters (UPRy, Vpec) and (U V) with respect to the loss L(- S'), which we leverage to prove the claim. We first analyze the generalization properties with respect to f, 'D of our 2-layer linear networks induced by the matrix product Ue for any U e By and v E TR with ||u]|2 I Г. We denote the family of 2-layer linear networks induced by the matrix product Uv as and define Br S IR to be the centered -2kT-radius Euclidean ball. Let Ho be the space of binary classifiers induced by taking the sign of the functionals (., Uu) with Uv E Similarly, define H to be the space of binary linear classifiers induced by functions (,,w) for all w E Br.
Since L Br each functional ( Uv) must also be contained in the space of functionals (,, .w) with E Br. This naturally implies Ho C H. Hence, the VC dimension of Ha is no larger than the VC dimension of H, i.e. at most k' + 1. Recall No C BF and that, by the description of Algorithm 3, there is a particular Ú E N such that U = M U. Then, we have Ú E Br and thus the binary classifier induced by Ue is in Ho for any u with ||ul12 S T.
To garner a generalization guarantee, we use the fact that the VC dimension of Ho is O(k). Recall that (S.) = {(Ma.g. ((.)) : (Ii,), 31.)) Si} for each e [n]. Denote SM ((S,)az as) ( and define the sequence of distributions DM ((Di)a,.-.. (D)) where for, each i E [n], we have that x' (D,) has the same distribution as Mæ with D,. Thus, we obtain, from the VC dimension generalization error bounds on H that, for each E [n]. the following
(1
k''
L(Ü, (D.)aa)) - Ż tf :S:))as)))))))))))))))))))))): s Eō
m
and
k
L(ū 0: (D.)M) - LÜÜ 02 (S))a)) <
with probability at least
1. 3. Then, by the union bound and taking the arithmetic mean over the n users Gn
kv'
[(Ü, ; - L(Ü, ypiv ; 5
m
and
5
with probability at least 1- - 1.9. Via the inner product that characterizes our losses in Definition 13, we have L(ū, ((U,V;Di) V;DM) L.UDaiv V; D) and L(U ypdv, DM) = T.(UDdv Vpnv; :D). Using the above inequalities and (54), we obtain
LUUi Vpix; D) LLUNL, V:D) < {0
k'
m
49

---

Private Model Personalization Revisited
with probability at least 1 3, which proves Claim 1.
Another application of the VC bound and the union bound gives with probability at least 33 that
L( V:D) L(U V =ō
(V
K'
(55)
m
Combining (53), Claim 1, and (55) via the union bound, and recalling that = (=F(o0((mm/0) finishes the proof.
by our choice of y
50


Reviews:
[{"review_id": "w4VEwuALMA", "reviewer": "Reviewer_CiH8", "summary": "The authors study model personalization under user-level differential privacy in a shared representation framework for the federated learning setting. Specifically, there are $n$ users, and the data for user $i\\in[n]$ is generated using $y = x^Tw^\\star_i + \\zeta$ where $\\zeta$ is sub-gaussian noise and $w_i^\\star = U^\\star v_i^\\star$ for some shared representation $U^\\star\\in \\mathbb{R}^{d\\times k}$ where $k<<d$. This setting was popularized by works such as [this one](https://arxiv.org/pdf/2002.11684) studying representation learning for meta-learning and other applications. This representation learning model has been previously shown to be useful for understanding the effectiveness of [Federated averaging](https://arxiv.org/pdf/2205.13692) and proposing a new algorithm called [FedRep for personalized federated learning](https://arxiv.org/pdf/2102.07078). \n\nIn this paper, the authors propose a federated algorithm that extends the FedRep method to ensure user-level differential privacy while including a private initialization step. Their algorithm accommodates sub-Gaussian feature distributions, noisy labels, and heterogeneous user data. In comparison to the [most closely related work](https://proceedings.neurips.cc/paper/2021/hash/f8580959e35cb0934479bb007fb241c2-Abstract.html) on private model personalization this paper relaxes the gaussian data assumption and allows federated training (i.e., without exchanging raw data and only sharing privatized model updates). The authors also improve the utility guarantee provided by this prior work in a reasonable low data regime. Overall, the theory in the paper and one small toy experiment show that the new approach improves the balance between privacy and utility for linear regression and matches or exceeds earlier methods’ performance.\n\nThe paper also addresses the binary classification setting with a margin-based loss. It uses a Johnson-Lindenstrauss transform to reduce dimensionality and obtain a margin-based risk bound that does not depend on the original feature dimension.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "We thank the reviewer for their thoughtful and constructive comments and for their appreciation of our work.\n\n**On the scope of the experimental evaluation**: We would like to emphasize that the primary contribution of our work is theoretical, and the experimental section is designed to validate our theoretical findings and demonstrate the concrete advantages of our algorithm. Our experiments follow the same setup as (Jain et al., 2021), allowing for a direct and meaningful comparison that highlights the improved privacy-utility trade-off achieved by our method. While our focus is not on empirical benchmarking across datasets, we believe the current results effectively showcase the key strengths of our approach. Extending the empirical evaluation to additional datasets and broader personalization settings is a valuable direction for future work and will further complement the strong theoretical foundation established in this paper.\n\nOn the other comments of the reviewer:\n1. **Definition of $u$**: The reviewer is correct about the definition of $u$. We will correct the oversight and define the clipping function more clearly. Indeed, $u$ represents the normalized direction of the gradient; namely, it is the matrix $M$ normalized by its Frobenius norm, $M/\\left\\lVert M \\right\\rVert_F$. \n2. **Utility guarantee for new users**: We agree that a utility corollary for new users using the learned shared representation is valuable. Indeed, the bound on the distance to $U^*$ (given by Lemma 9) can be used to bound the excess risk of new users. We will add this result as a corollary of Theorem 10 as suggested by the reviewer.\n3. **Co-variate heterogeneity**: Our analysis does allow for a certain degree of co-variate heterogeneity among users. In particular, our results hold when user distributions differ as long as they are sub-Gaussian and share a common covariance structure. Note that the prior work of (Jain et al., 2021) lacks co-variate heterogeneity altogether as it requires all the data features to be i.i.d. standard Gaussian. We agree that extending the framework to handle more general co-variate and label shifts is an important direction for future work.", "claims_and_evidence": "Yes, this is a technically solid paper.", "methods_and_evaluation_criteria": "Yes, this is a theoretical paper, and the central guarantees in Theorems 10 and 16 make sense.", "theoretical_claims": "I checked some proofs just to understand what is happening in the paper, but not every proof.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "See the summary.", "essential_references_not_discussed": "No references I can think of.", "other_strengths_and_weaknesses": "The paper is very well written, with explicit assumptions and theoretical results. It relaxes assumptions required by prior work by allowing sub-Gaussian feature distributions and improving over the existing centralized results in reasonable regimes.\n\nIf I were to nitpick, the paper could benefit from additional empirical evaluations that measure performance on more diverse datasets and compare implementation complexities with other approaches. The paper focuses primarily on the strongly convex quadratic loss, so researchers who work with other loss functions might find the scope somewhat narrow. Having said that, the authors deliver a technically solid paper, and I am inclined to accept it.", "other_comments_or_suggestions": "1. $u$ was not defined while defining the clipping function in lines 193-194. I suppose it is the unit Frobinus norm version of the Matrix?\n\n2. In terms of presentation, it would also be good to state the utility guarantee for a new user using the algorithm's learned shared representation. This can be stated in a corollary after Theorem 10.", "questions_for_authors": "1. Have the authors thought about co-variate heterogeneity? We often see a combination of covariate and label shifts in a distributed setting. It would be nice to see how these different sources of heterogeneity affect the final personalization guarantee.", "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": "", "extra_scores": {}}, {"review_id": "A2xsMRkqgh", "reviewer": "Reviewer_qvLQ", "summary": "The authors present a novel technique to unlock differently private personalised models in the shared representation framework in a federated setting.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We thank the reviewer for their positive feedback. \n\n**On the scope of the experimental evaluation**: We would like to emphasize that the primary contribution of our work is theoretical, and the experimental section is designed to validate our theoretical findings and demonstrate the concrete advantages of our algorithm. Our experiments follow the same setup as (Jain et al., 2021), allowing for a direct and meaningful comparison that highlights the improved privacy-utility trade-off achieved by our method. While our focus is not on empirical benchmarking across datasets, we believe the current results effectively showcase the key strengths of our approach. Extending the empirical evaluation to additional datasets and broader personalization settings is a valuable direction for future work and will further complement the strong theoretical foundation established in this paper.\n\n**On the privacy guarantee after composition**: Indeed, we take into account the privacy loss over the iterations of the algorithm. We leverage the adaptive composition guarantee of zero-concentrated differential privacy (zCDP) to bound the overall privacy loss of our algorithm and ensure it satisfies $(\\epsilon, \\delta)$-DP (see the proof of Theorem 8, Appendix B.1). Specifically, we show that the privacy cost for each iteration is $O\\left(\\frac{\\epsilon^2}{T\\log(1/\\delta)}\\right)$-zCDP. By applying composition over $T$ iterations, we obtain an overall privacy cost of $O(\\epsilon^2/\\log(1/\\delta))$-zCDP, which implies an $(\\epsilon, \\delta)$-DP guarantee. Also, note that, after $U^\\text{priv}$ is computed and sent to the users, each user $i$ will compute their own final local vectors $v_i^\\text{priv}$ independently via this $U^\\text{priv}$ matrix and a reserved set of fresh local data. The vector $v_i^\\text{priv}$ will be kept by user $i$ (for each $i$) and never shared; thus, computing $v_i^\\text{priv}$ will not lead to any additional privacy loss.", "claims_and_evidence": "The claims are sufficient and well supported.", "methods_and_evaluation_criteria": "While the paper is focused on theory the experiments are rather light and only compare with a base method using only synthetic datasets. It would be great to have an expanded experiment section applying it to real-world datasets and for additional methods to raise convition about its applicability.", "theoretical_claims": "The theoretical claims appear to be sound.", "experimental_designs_or_analyses": "The design of experiments seems to be sufficient for the domain of the paper (albeit the actual experiments are few, as mentioned previously).", "relation_to_broader_scientific_literature": "The authors address a very important problem, especially in the case of federated computing. Unlocking the ability to have user personalised models is not only novel but really important for a variery of applications.", "essential_references_not_discussed": "Nothing of note.", "other_strengths_and_weaknesses": "It is highly appreciated that the authors shared the code and hope, if their work gets published, to be attached as an artefact to this submission to enhance dissemination.", "other_comments_or_suggestions": "Nothing of note.", "questions_for_authors": "I would like to ask the authors how they can ensure that the model remains private after iterations, surely assuming they use composition under differential privacy to preserve the DP under aggregation only weakens over time as results are \"revealed\" and propagated.\n\nIt would be great to expand on this and address this concern.w", "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": "", "extra_scores": {}}, {"review_id": "qSqVShHVOF", "reviewer": "Reviewer_hcg6", "summary": "The paper addresses the problem of model personalization under user-level differential privacy (DP) in the federated learning setting. The authors propose a novel private federated learning algorithm based on the FedRep framework, which learns a shared low-dimensional embedding and user-specific local models while ensuring DP. The main contributions include: (1) an efficient private federated algorithm that handles noisy labels and sub-Gaussian data distributions, (2) improved privacy-utility trade-offs compared to prior work, (3) a private initialization algorithm for the shared embedding, and (4) dimension-independent risk guarantees for binary classification using the Johnson-Lindenstrauss transform. The paper claims to improve the privacy error term by a factor of $\\tilde{O}(dk)$ in certain parameter regimes and extends the applicability to broader data distributions compared to prior work.\n\n## update after rebuttal\nThe authors have addressed two of my concerns, and I am generally satisfied with the rebuttal, so I have raised my score. While I raised my score, I remain somewhat unenthusiastic about the paper overall.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We thank the reviewer for their detailed comments. We respectfully disagree with several conclusions and clarify key contributions and motivations below.\n\n**On the Practical Significance of the Low-Dimensional Embedding Assumption**:\\\nThe *low-dimensional* shared representation assumption is widely adopted in both theoretical and practical work on model personalization and federated learning, including Collins et al. (ICML 2021), Jain et al. (NeurIPS 2021), Tripuraneni et al. (ICML 2021), and Duchi et al. (NeurIPS 2022). It reflects practical scenarios (e.g., in multitask/meta-learning) and enables rigorous analysis and tractable algorithms. \n\nThe *linear* shared representation setting captures a **fundamental learning problem** that has attracted significant recent interest in the literature, including the works referenced above. Many influential works explore it to understand key statistical and computational challenges in learning from heterogeneous data. Despite its apparent simplicity, this setting remains **analytically challenging and far from fully understood**, as even recent works require structural assumptions (e.g., Gaussianity, identity covariance, boundedness) to obtain formal guarantees. These challenges are magnified under differential privacy, which introduces additional technical hurdles such as sensitivity control and dealing with noise accumulation while ensuring good convergence behavior. While neural-network-based personalization has shown empirical success, it is generally **infeasible to derive formal risk guarantees** in such settings due to their non-convexity. As a result, most works rely on empirical evaluation. Our work, by contrast, focuses on providing **rigorous theoretical insights** in a meaningful and analyzable setup—paving the way for future extensions to more complex models.\n\n**On the Role of FedRep and Comparison to Prior Work**:\\\nWhile we build on FedRep (Collins et al., 2021), our contributions go significantly beyond:\n- We extend FedRep to satisfy **user-level differential privacy** in a federated setting, while also handling **noisy labels**—an important practical case not previously addressed. The addition of noisy labels requires substantial changes to the utility analysis.  \n- Compared with the original FedRep algorithm, we make several modifications that are crucial to our analysis. For instance, we modify the algorithm to use **disjoint batches** for updating $U$ and $V$, unlike FedRep. This crucial change allows tighter control of gradient norms, reduces the noise required for DP, and leads to **improved convergence rates** and sharper utility bounds. \n- Our **utility bound** improves over the **centralized approach of Jain et al. (2021)** by a factor of $\\tilde{O}(dk)$ in key regimes.\n- Unlike Jain et al. (2021), our algorithm is **fully federated**, avoiding the need for centralization or exact minimization—making it more scalable and practical.\nThese results constitute both conceptual and analytical innovations and establish state-of-the-art privacy-utility trade-offs in this setting.\n\n**On Regression vs. Classification**:\\\nClassification with margin loss requires a different analytical and algorithmic approach from regression with quadratic loss. The regression analysis benefits from the structure of the quadratic loss, which enables deriving risk bounds through optimization and concentration arguments that are tied to the sub-Gaussianity and covariance structure of data. In contrast, margin-based losses lack these convenient analytical properties, requiring distinct analysis strategy and algorithmic approach. In our work, we develop a tailored approach for the classification setting—leveraging dimensionality reduction and margin-based analysis—to obtain the **first dimension-independent risk bound under user-level DP** in this framework.\n\n**On the Significance of Extending to Sub-Gaussian Distributions**:\\\nThe extension from Gaussian to sub-Gaussian data is **not a minor technical change**. Gaussianity permits powerful simplifications due to properties such as rotational invariance and moment equivalence. For example, (Jain et al. 2021) explicitly leverages rotational invariance (spherical symmetry) for their initialization analysis. Further, the proof of their main bound hinges upon several results from (Thekumparampil et al., 2021) that rely on the said properties for the case of independent, standard Gaussian features. In contrast, sub-Gaussian distributions are much more general (e.g., bounded or light-tailed features) and lack such symmetries.\n \nOur extension beyond Gaussian data required a **new analysis** that leverages concentration inequalities (e.g., Vershynin, 2018) to handle sub-Gaussian data with heterogeneous, non-identical feature distributions, significantly broadening the applicability of our private personalization algorithm.\n\n**On Citation Formatting**: We will ensure citation formatting consistency.", "claims_and_evidence": "The main claims are supported by proofs.", "methods_and_evaluation_criteria": "The proposed methodology is well-explained and aligns with intuitive expectations. The evaluation criterion used is MSE, which is appropriate for the vector estimation problem.", "theoretical_claims": "The proofs are reviewed but not rigorously verified.", "experimental_designs_or_analyses": "The empirical evaluation includes a simple privacy-utility trade-off analysis in terms of MSE.", "relation_to_broader_scientific_literature": "The paper extends previous work (Jain et al., 2021). I am not familiar with the task of model personalization, so I do not have a strong opinion on this point.", "essential_references_not_discussed": "I have not read any paper about model personalization.", "other_strengths_and_weaknesses": "I feel the practical significance of the work is rather limited. The current low-dimensional embedding assumption seems applicable only to limited scenarios. Moreover, the methodology relies heavily on the low-dimensional embedding assumption and does not appear to extend to neural network-based methods. Could the authors provide some discussion on this point? \n\nAdditionally, the contribution does not appear significant enough to me. The algorithm builds largely on FedRep, and the theoretical contribution seems to be an extension of Jain et al., 2021.", "other_comments_or_suggestions": "Please ensure the correct usage of \\cite, \\citep, and \\citet. Note that the formatting of citations may vary depending on the LaTeX template used.", "questions_for_authors": "The paper is written in a highly technical manner, presenting theoretical assumptions and results. I suggest the authors provide more high-level discussions, particularly regarding the following points. I would be happy to raise my score if these questions are addressed well:\n\n- Intrinsic Difference Between Classification and Regression: What is the fundamental difference between classification and regression? If they are both treated as supervised problems, are there conclusions that hold for one but not the other? The authors treat these two problems separately in two sections, but I am somewhat confused about their differences beyond the technical aspects (e.g., different scores, target spaces). Could the authors comment on this?\n\n- Intrinsic Difference Between Gaussian and Sub-Gaussian Assumptions: What is the fundamental difference between Gaussian and sub-Gaussian distribution assumptions? In previous literature (Jain et al., 2021), is the Gaussian distribution necessary due to its unique properties (e.g., rotation invariance, equivalence between independence and uncorrelatedness), or is it merely about tail probabilities? If the latter, I do not see a significant improvement. The paper emphasizes the improvement from Gaussian to sub-Gaussian assumptions as a main contribution multiple times, but there seems to be no detailed discussion on this point.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper studies model personalization with user-level differential privacy. In this problem, each user wants to learn a different parameter in R^d. These parameters share an unknown embedding that reduces the dimensions from d to k i.e. each parameter vector is the product of a k-dimensional vector and the embedding. The goal is to learn the embedding and the parameter vectors for all users. The paper gives a private algorithm based on previous work in the non-private setting. The new algorithm works for all subgaussian data, generalizing previous work for only gaussian data. Additionally, the privacy error is reduced in certain settings. All reviewers are positive about the paper. The technical content is significant though the reviewers also note that the result only applies to the somewhat limited setting of a linear model with quadratic loss functions (this is common to a lot of work in the area).
Decision: Accept (poster)