On the Convergence of Differentially Private Federated Learning on Non-Lipschitz Objectives, and with Normalized Client Updates

Rudrajit Das, Abolfazl Hashemi, Sujay Sanghavi, Inderjit S. Dhillon

Abstract

There is a significant gap in the theoretical understanding of differentially private federated learning (DP-FL) when applied to non-Lipschitz objective functions—scenarios where gradient norms are not naturally bounded. Standard DP-FL relies on gradient clipping to bound sensitivity, but this operation introduces bias and variance trade-offs that are difficult to analyze without assuming Lipschitz continuity. This paper provides the first convergence results for DP-FL on smooth convex objectives under a general clipping threshold without assuming Lipschitzness. Furthermore, the authors propose DP-NormFedAvg, an algorithm that replaces clipping with update normalization. This approach is theoretically shown to offer superior convergence and a better signal-to-noise ratio (SNR) than clipping-based methods, a claim supported by both synthetic and real-world benchmarking experiments.

Introduction

Federated Learning (FL) enables a central server to train a global model by aggregating updates from distributed clients while keeping raw data localized. To provide formal privacy guarantees, Differential Privacy (DP) is often integrated into the FL workflow, typically by adding Gaussian noise to aggregated client updates. However, the magnitude of this noise is proportional to the sensitivity of the updates. To control sensitivity, practitioners use clipping, where any update exceeding a threshold $C$ is scaled down to $C$.

Despite its ubiquity, clipping presents three major challenges:

  1. Theoretical Mismatch: Most convergence proofs assume the objective function is Lipschitz continuous (i.e., gradients are bounded). In practice, especially in deep learning, this assumption rarely holds.
  2. The Bias-Variance Trade-off: Clipping introduces bias if the threshold $C$ is too small, while a large $C$ requires adding more noise, increasing variance.
  3. Hyperparameter Tuning: Selecting an optimal $C$ is computationally expensive and often requires extensive manual tuning.

Theoretical Framework for Non-Lipschitz Objectives

This research addresses the theoretical void by deriving convergence guarantees for smooth convex objectives under a general clipping threshold. Unlike previous works, this analysis does not rely on the assumption of bounded gradients. The framework accounts for the bias introduced by the clipping operation and the compounding effects of multiple local update steps ($E > 1$) per communication round.

One of the critical insights of this analysis is the interaction between initialization and data heterogeneity. The authors demonstrate that performing multiple local steps helps mitigate the effects of a poor initial model (initialization bias) but simultaneously amplifies errors stemming from differences in client data distributions (heterogeneity).

DP-NormFedAvg: Normalization as an Alternative to Clipping

Building on their theoretical findings, the authors propose DP-NormFedAvg. Instead of clipping—which only modifies updates that exceed a threshold—this method normalizes every client update. Each update is converted into a unit vector and then scaled by a fixed factor $C$. This process effectively discards the magnitude of the update, preserving only the directional information.

The Signal-to-Noise Ratio (SNR) Advantage

A primary contribution of this work is the identification of the "SNR Advantage" inherent in normalization. In standard clipping-based DP-FL, as the model approaches convergence, the gradients naturally shrink. However, the noise added for privacy remains constant (scaled by $C$). This leads to a decaying SNR, where the noise eventually overwhelms the signal, causing the model to wander.

In contrast, normalization ensures the signal (the update) always has a constant magnitude $C$. This maintains a healthier SNR throughout the training process, allowing for more direct convergence toward the optimum. Theoretically, as the number of communication rounds $K$ increases, the negative effects of data heterogeneity vanish, leaving normalization as the asymptotically superior method.

Experimental Evaluation

The authors validated their theoretical claims using a variety of settings:

  • Synthetic Quadratic Problem: Used to visualize training trajectories and confirm SNR improvements in a controlled environment.
  • Fashion-MNIST: Multi-class classification with 3,000 clients.
  • CIFAR-10 & CIFAR-100: To satisfy the convexity requirements of the theory while using complex image data, the authors used 512-dimensional features extracted from a pre-trained ResNet-18, applying a convex logistic regression layer for the final optimization.
  • Heterogeneity: Non-IID settings were simulated by restricting each client to a maximum of five classes.

Key Results

DP-NormFedAvg consistently outperformed standard clipping across various privacy budgets ($\epsilon$). At a privacy level of $\epsilon = 5$, the accuracy improvements were notable:

Dataset Clipping Accuracy Normalization Accuracy Improvement
CIFAR-100 56.53% 59.36% +2.83%
Fashion-MNIST 75.59% 77.72% +2.13%
CIFAR-10 82.63% 84.21% +1.58%

Qualitative analysis of training trajectories showed that DP-NormFedAvg follows a significantly more direct path to the optimal solution, whereas clipping-based updates exhibit high variance and stochastic wandering near the optimum.

Conclusion and Future Work

This paper provides a rigorous foundation for DP-FL on non-Lipschitz objectives and establishes normalization as a robust alternative to gradient clipping. By maintaining a stable SNR, DP-NormFedAvg achieves higher accuracy and more stable convergence.

Future research directions include extending these theoretical proofs to non-convex objectives, such as deep neural networks trained from scratch. Additionally, exploring adaptive scaling factors could further reduce the need for manual hyperparameter tuning, and investigating the interaction between normalization and communication-efficient techniques (like gradient compression) remains an open area of study.

Summary updated

Abstract

There is a dearth of convergence results for differentially private federated learning (FL) with non-Lipschitz objective functions (i.e., when gradient norms are not bounded). The primary reason for this is that the clipping operation (i.e., projection onto an $\ell_2$ ball of a fixed radius called the clipping threshold) for bounding the sensitivity of the average update to each client's update introduces bias depending on the clipping threshold and the number of local steps in FL, and analyzing this is not easy. For Lipschitz functions, the Lipschitz constant serves as a trivial clipping threshold with zero bias. However, Lipschitzness does not hold in many practical settings; moreover, verifying it and computing the Lipschitz constant is hard. Thus, the choice of the clipping threshold is non-trivial and requires a lot of tuning in practice. In this paper, we provide the first convergence result for private FL on smooth \textit{convex} objectives \textit{for a general clipping threshold} -- \textit{without assuming Lipschitzness}. We also look at a simpler alternative to clipping (for bounding sensitivity) which is \textit{normalization} -- where we use only a scaled version of the unit vector along the client updates, completely discarding the magnitude information. {The resulting normalization-based private FL algorithm is theoretically shown to have better convergence than its clipping-based counterpart on smooth convex functions. We corroborate our theory with synthetic experiments as well as experiments on benchmarking datasets.
BibTeX
@misc{das2021convergence,
  author = {Rudrajit Das and Abolfazl Hashemi and Sujay Sanghavi and Inderjit S. Dhillon},
  title = {{On the Convergence of Differentially Private Federated Learning on Non-Lipschitz Objectives, and with Normalized Client Updates}},
  year = {2021},
  eprint = {2106.07094},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2106.07094},
}
Figure