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