Double Momentum and Error Feedback for Clipping with Fast Rates and Differential Privacy

• URL: http://arxiv.org/abs/2502.11682v1
• Date: Mon, 17 Feb 2025 11:16:21 GMT
• Title: Double Momentum and Error Feedback for Clipping with Fast Rates and Differential Privacy
• Authors: Rustem Islamov, Samuel Horvath, Aurelien Lucchi, Peter Richtarik, Eduard Gorbunov,
• Abstract summary: existing algorithms do not achieve Strong Differential Privacy (DP) and Optimization guarantees at once. We propose a new method called Clip21-SGD2M based on a novel combination of clipping, heavy-ball momentum, and Error Feedback.
• Score: 11.356444450240799
• License:
• Abstract: Strong Differential Privacy (DP) and Optimization guarantees are two desirable properties for a method in Federated Learning (FL). However, existing algorithms do not achieve both properties at once: they either have optimal DP guarantees but rely on restrictive assumptions such as bounded gradients/bounded data heterogeneity, or they ensure strong optimization performance but lack DP guarantees. To address this gap in the literature, we propose and analyze a new method called Clip21-SGD2M based on a novel combination of clipping, heavy-ball momentum, and Error Feedback. In particular, for non-convex smooth distributed problems with clients having arbitrarily heterogeneous data, we prove that Clip21-SGD2M has optimal convergence rate and also near optimal (local-)DP neighborhood. Our numerical experiments on non-convex logistic regression and training of neural networks highlight the superiority of Clip21-SGD2M over baselines in terms of the optimization performance for a given DP-budget.

Related papers

• Smoothed Normalization for Efficient Distributed Private Optimization [54.197255548244705]
  Federated learning enables machine learning models with privacy of participants. There is no differentially private distributed method for training, non-feedback problems. We introduce a new distributed algorithm $alpha$-$sf NormEC$ with provable convergence guarantees.
  arXiv  Detail & Related papers  (2025-02-19T07:10:32Z)
• MARINA-P: Superior Performance in Non-smooth Federated Optimization with Adaptive Stepsizes [57.24311218570012]
  We extend the non-smooth convex theory of EF21-P (Anonymous 2024) and MARINA-P (arXiv:2402.06412) in the non-size convex setting. We provide theoretical guarantees under constant, decreasing, and adaptive (aktypetype) steps.
  arXiv  Detail & Related papers  (2024-12-22T16:18:34Z)
• Improved Communication-Privacy Trade-offs in $L_2$ Mean Estimation under Streaming Differential Privacy [47.997934291881414]
  Existing mean estimation schemes are usually optimized for $L_infty$ geometry and rely on random rotation or Kashin's representation to adapt to $L$ geometry. We introduce a novel privacy accounting method for the sparsified Gaussian mechanism that incorporates the randomness inherent in sparsification into the DP. Unlike previous approaches, our accounting algorithm directly operates in $L$ geometry, yielding MSEs that fast converge to those of the Gaussian mechanism.
  arXiv  Detail & Related papers  (2024-05-02T03:48:47Z)
• Differentially Private Optimization with Sparse Gradients [60.853074897282625]
  We study differentially private (DP) optimization problems under sparsity of individual gradients. Building on this, we obtain pure- and approximate-DP algorithms with almost optimal rates for convex optimization with sparse gradients.
  arXiv  Detail & Related papers  (2024-04-16T20:01:10Z)
• Differentially Private SGD Without Clipping Bias: An Error-Feedback Approach [62.000948039914135]
  Using Differentially Private Gradient Descent with Gradient Clipping (DPSGD-GC) to ensure Differential Privacy (DP) comes at the cost of model performance degradation. We propose a new error-feedback (EF) DP algorithm as an alternative to DPSGD-GC. We establish an algorithm-specific DP analysis for our proposed algorithm, providing privacy guarantees based on R'enyi DP.
  arXiv  Detail & Related papers  (2023-11-24T17:56:44Z)
• Differentially Private Federated Clustering over Non-IID Data [59.611244450530315]
  clustering clusters (FedC) problem aims to accurately partition unlabeled data samples distributed over massive clients into finite clients under the orchestration of a server. We propose a novel FedC algorithm using differential privacy convergence technique, referred to as DP-Fed, in which partial participation and multiple clients are also considered. Various attributes of the proposed DP-Fed are obtained through theoretical analyses of privacy protection, especially for the case of non-identically and independently distributed (non-i.i.d.) data.
  arXiv  Detail & Related papers  (2023-01-03T05:38:43Z)
• Decentralized Nonconvex Optimization with Guaranteed Privacy and Accuracy [34.24521534464185]
  Privacy protection and nonity are two challenging problems in decentralized optimization learning sensitive data. We propose an algorithm that allows both privacy protection and avoidance. The algorithm is efficient in both communication and computation.
  arXiv  Detail & Related papers  (2022-12-14T22:36:13Z)
• Efficient Private SCO for Heavy-Tailed Data via Averaged Clipping [40.69950711262191]
  We consider differentially private convex optimization for heavy-tailed data with the guarantee of being differentially private (DP) We establish new convergence results and improved complexity bounds for the proposed algorithm called AClipped-dpSGD for constrained and unconstrained convex problems.
  arXiv  Detail & Related papers  (2022-06-27T01:39:15Z)
• On Private Online Convex Optimization: Optimal Algorithms in $\ell_p$-Geometry and High Dimensional Contextual Bandits [9.798304879986604]
  We study the Differentially private (DP) convex optimization problem with streaming data sampled from a distribution and arrives sequentially. We also consider the continual release model where parameters related to private information are updated and released upon each new data, often known as the online algorithms. Our algorithm achieves in linear time the optimal excess risk when $1pleq 2$ and the state-of-the-art excess risk meeting the non-private lower ones when $2pleqinfty$.
  arXiv  Detail & Related papers  (2022-06-16T12:09:47Z)
• Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimization [44.52870407321633]
  holy grail of these settings is to guarantee the optimal trade-off between the privacy and the excess population loss. We provide a general framework for solving differentially private minimax optimization (DP-SMO) problems. Our framework is inspired from the recently proposed Phased-ERM method [20] for nonsmooth differentially private convex optimization (DP-SCO)
  arXiv  Detail & Related papers  (2022-06-01T10:03:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.