mlsanityData to 7 Oct 2026

Shuffle Private Stochastic Convex Optimization

arXiv 2106.09805 ↗First posted 17 Jun 2021cs.LG cs.CR cs.DScited by 17

Not on the map. Why?

Abstract (arXiv)

In shuffle privacy, each user sends a collection of randomized messages to a trusted shuffler, the shuffler randomly permutes these messages, and the resulting shuffled collection of messages must satisfy differential privacy. Prior work in this model has largely focused on protocols that use a single round of communication to compute algorithmic primitives like means, histograms, and counts. We present interactive shuffle protocols for stochastic convex optimization. Our protocols rely on a new noninteractive protocol for summing vectors of bounded ℓ2 norm. By combining this sum subroutine with mini-batch stochastic gradient descent, accelerated gradient descent, and Nesterov's smoothing method, we obtain loss guarantees for a variety of convex loss functions that significantly improve on those of the local model and sometimes match those of the central model.

Key facts. Cited by 17 papers in the map (data through 7 Oct 2026). Builds on 24 of its 46 references that are in the map. First posted on arXiv 17 Jun 2021.

Builds on

24 of 46 references.

References · 24

  1. 2019Advances and Open Problems in Federated Learningcited by 3,021
  2. 2014Convex Optimization: Algorithms and Complexitycited by 569
  3. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  4. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 183
  5. 2021Practical and Private (Deep) Learning without Sampling or Shufflingcited by 169
  6. 2018Amplification by Shuffling: From Local to Central Differential Privacy via Anonymitycited by 163
  7. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 152
  8. 2020The Discrete Gaussian for Differential Privacycited by 134
  9. 2021The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregationcited by 127
  10. 2018Distributed Differential Privacy via Shufflingcited by 115
  11. 2014Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Boundscited by 104
  12. 2016Minimax Optimal Procedures for Locally Private Estimationcited by 103
12 more
  1. 2020Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shufflingcited by 96
  2. 2017Prochlo: Strong Privacy for Analytics in the Crowdcited by 51
  3. 2020Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluationcited by 39
  4. 2021Differentially Private Multi-Armed Bandits in the Shuffle Modelcited by 24
  5. 2019Scalable and Differentially Private Distributed Aggregation in the Shuffled Modelcited by 20
  6. 2019Separating Local & Shuffled Differential Privacy via Histogramscited by 16
  7. 2019The Role of Interactivity in Local Differential Privacycited by 15
  8. 2020Connecting Robust Shuffle Privacy and Pan-Privacycited by 12
  9. 2019Differentially Private Summation with Multi-Message Shufflingcited by 9
  10. 2019Pan-Private Uniformity Testingcited by 6
  11. 2019Element Level Differential Privacy: The Right Granularity of Privacycited by 6
  12. 2020On the Round Complexity of the Shuffle Modelcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 6; 2023: 4; 2024: 3; 2025: 3; 2026: 1.

17 papers.

Sort:

  1. 2022Shuffle Private Linear Contextual Banditscited by 27
  2. 2022Private Non-Convex Federated Learning Without a Trusted Servercited by 26
  3. 2022Differentially Private Stochastic Linear Bandits: (Almost) for Freecited by 19
  4. 2022Distributed Differential Privacy in Multi-Armed Banditscited by 14
  5. 2023On Differentially Private Federated Linear Contextual Banditscited by 14
  6. 2024A Huber Loss Minimization Approach to Mean Estimation under User-level Differential Privacycited by 11
  7. 2022Differentially Private Linear Bandits with Partial Distributed Feedbackcited by 8
  8. 2024Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messagescited by 5
  9. 2022Private Stochastic Optimization With Large Worst-Case Lipschitz Parametercited by 3
  10. 2023(Private) Kernelized Bandits with Distributed Biased Feedbackcited by 3
  11. 2024Private and Federated Stochastic Convex Optimization: Efficient Strategies for Centralized Systemscited by 3
  12. 2023Concurrent Shuffle Differential Privacy Under Continual Observationcited by 2
5 more
  1. 2023Multi-Message Shuffled Privacy in Federated Learningcited by 2
  2. 2025Learning from End User Data with Shuffled Differential Privacy over Kernel Densitiescited by 1
  3. 2025PREAMBLE: Private and Efficient Aggregation via Block Sparse Vectorscited by 1
  4. 2025Privacy-Preserving Federated Convex Optimization: Balancing Partial-Participation and Efficiency via Noise Cancellationcited by 1
  5. 2026Shuffle and Joint Differential Privacy for Generalized Linear Contextual Banditscited by 0