  User-level differential privacy (DP) provides certifiable privacy guarantees
to the information that is specific to any user's data in federated learning.
Existing methods that ensure user-level DP come at the cost of severe accuracy
decrease. In this paper, we study the cause of model performance degradation in
federated learning under user-level DP guarantee. We find the key to solving
this issue is to naturally restrict the norm of local updates before executing
operations that guarantee DP. To this end, we propose two techniques, Bounded
Local Update Regularization and Local Update Sparsification, to increase model
quality without sacrificing privacy. We provide theoretical analysis on the
convergence of our framework and give rigorous privacy guarantees. Extensive
experiments show that our framework significantly improves the privacy-utility
trade-off over the state-of-the-arts for federated learning with user-level DP
guarantee.
