Abstract
In private federated learning (FL), a server aggregates differentially private updates from a large number of clients in order to train a machine learning model. The main challenge in this setting is balancing privacy with both classification accuracy of the learnt model as well as the number of bits communicated between the clients and server. Prior work has achieved a good trade-off by designing a privacy-aware compression mechanism, called the minimum variance unbiased (MVU) mechanism, that numerically solves an optimization problem to determine the parameters of the mechanism. This paper builds upon it by introducing a new interpolation procedure in the numerical design process that allows for a far more efficient privacy analysis. The result is the new Interpolated MVU mechanism that is more scalable, has a better privacy-utility trade-off, and provides SOTA results on communication-efficient private FL on a variety of datasets.
Introduction
Federated Learning (FL) faces a fundamental trilemma: maximizing model accuracy while ensuring data privacy via Differential Privacy (DP) and minimizing communication costs. Existing solutions often struggle to balance these three pillars. For instance, the original Minimum Variance Unbiased (MVU) mechanism, while theoretically sound, relies on "randomized dithering" to maintain unbiasedness. In high-dimensional settings typical of modern neural networks, this approach leads to exploding update norms, necessitating expensive rejection sampling and resulting in overly conservative privacy guarantees.
Methodology: The I-MVU Mechanism
The Interpolated MVU (I-MVU) mechanism addresses these limitations by shifting away from the "unbiasedness at all costs" philosophy. The core innovation lies in how the mechanism is constructed and analyzed using numerical design.
Natural Parameter Interpolation
Unlike the original MVU, which interpolates between probabilities of discrete outputs, I-MVU treats the mechanism as a categorical distribution within the exponential family. It performs linear interpolation on the natural parameters ($η$) of this distribution. This approach avoids the scaling issues that plague probability-space interpolation in high dimensions, allowing the mechanism to scale to modern deep learning models.
Relaxing Unbiasedness
I-MVU introduces a small amount of bias for values between grid points. However, in the context of FL, where the global model is an average of thousands of client updates, this local bias is negligible and does not hinder convergence. The gain in efficiency and scalability from this relaxation is substantial. As the bit budget ($B_{in}$) increases, the mechanism's expectation approaches the unbiased diagonal.
Fisher Information and Privacy Analysis
To provide rigorous privacy guarantees, the authors utilize Fisher Information to bound the Rényi Differential Privacy (RDP). This provides a significantly tighter analysis for $L_2$-bounded vectors compared to previous methods. Additionally, a $β$-scaling factor is introduced to optimize the mechanism's range for gradients concentrated near zero.
Experimental Results
The authors evaluated I-MVU against baselines such as SignSGD, Skellam, and standard Gaussian/Laplace mechanisms across several datasets: MNIST, CIFAR-10 (using WideResNet-28-10), and FEMNIST (3,500 simulated clients).
- Performance Parity at 1-Bit: On MNIST and CIFAR-10, I-MVU at just 1 bit per parameter achieved test accuracy nearly identical to the non-compressed 32-bit Gaussian mechanism across all privacy budgets ($ε$).
- Superior Scalability: I-MVU successfully handled the high-dimensional gradients of a WideResNet-28-10, a feat that previous numerical mechanisms struggled with due to the curse of dimensionality.
- Communication Efficiency: On the FEMNIST dataset, I-MVU outperformed the Skellam mechanism while requiring 16x less bandwidth, demonstrating its practical utility in large-scale federated systems.
Conclusion
I-MVU demonstrates that strict unbiasedness is not a requirement for effective private FL. By designing discrete distributions numerically and using natural parameter interpolation, I-MVU achieves state-of-the-art results at extremely low bitrates. This work effectively eliminates the utility gap usually seen when compressing private updates, paving the way for more efficient and private large-scale machine learning.
Summary updated