Private Model Personalization Revisited

We thank the reviewer for their detailed comments. We respectfully disagree with several conclusions and clarify key contributions and motivations below.

On the Practical Significance of the Low-Dimensional Embedding Assumption:
The 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.

The 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.

On the Role of FedRep and Comparison to Prior Work:
While we build on FedRep (Collins et al., 2021), our contributions go significantly beyond:

• 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.
• 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.
• Our utility bound improves over the centralized approach of Jain et al. (2021) by a factor of $\tilde{O}(dk)$ in key regimes.
• Unlike Jain et al. (2021), our algorithm is fully federated, avoiding the need for centralization or exact minimization—making it more scalable and practical. These results constitute both conceptual and analytical innovations and establish state-of-the-art privacy-utility trade-offs in this setting.

On Regression vs. Classification:
Classification 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.

On the Significance of Extending to Sub-Gaussian Distributions:
The 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.

Our 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.

On Citation Formatting: We will ensure citation formatting consistency.

We thank the reviewer for their thoughtful and constructive comments and for their appreciation of our work.

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.

On the other comments of the reviewer:

1. 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$.
2. 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.
3. 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.

We thank the reviewer for their positive feedback.

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.

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.