PaperlayerView exact revision on arXiv

Source-linked AI summary

Practical and Private (Deep) Learning without Sampling or Shuffling

Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, Zheng Xu

arXiv:2103.00039v3cs.CRcs.LG

TL;DR

DP-SGD’s strongest trade-offs depend on exact sampling or shuffling, which can be difficult in federated and other distributed settings. The paper introduces DP-FTRL, a privacy-amplification-free online-learning algorithm, and finds competitive trade-offs theoretically and empirically, including parity with amplified DP-SGD at modest extra computation and better accuracy at larger privacy budgets.

  • Problem

    DP-SGD’s reliance on exact uniform sampling or shuffling makes its best privacy/utility/computation trade-offs difficult to obtain in practical settings such as federated learning.

  • Method

    The paper develops DP-FTRL, a differentially private online-learning algorithm that supports arbitrary data-access order without privacy amplification.

  • Results

    DP-FTRL matches amplified DP-SGD with a modest batch-size increase and can outperform it at larger privacy budgets, while outperforming unamplified DP-SGD across privacy levels.

  • Takeaways & Limitations

    Privacy amplification is not required for DP-FTRL to achieve competitive privacy/utility/computation trade-offs with amplified DP-SGD.

  • Takeaways & Limitations

    With longer training, the ε crossover point where DP-FTRL outperforms amplified DP-SGD shifts to a larger value, although it remains below 15 in the reported experiments.

Abstract

from arXiv · show

We consider training models with differential privacy (DP) using mini-batch gradients. The existing state-of-the-art, Differentially Private Stochastic Gradient Descent (DP-SGD), requires privacy amplification by sampling or shuffling to obtain the best privacy/accuracy/computation trade-offs. Unfortunately, the precise requirements on exact sampling and shuffling can be hard to obtain in important practical scenarios, particularly federated learning (FL). We design and analyze a DP variant of Follow-The-Regularized-Leader (DP-FTRL) that compares favorably (both theoretically and empirically) to amplified DP-SGD, while allowing for much more flexible data access patterns. DP-FTRL does not use any form of privacy amplification. The code is available at https://github.com/google-research/federated/tree/master/dp_ftrl and https://github.com/google-research/DP-FTRL .

1 Introduction

DP-SGD offers strong privacy-utility trade-offs but depends on uniformly sampled or shuffled mini-batches, which can be impractical in large-scale and federated settings. DP-FTRL avoids privacy amplification while providing competitive theoretical and empirical trade-offs, with extensions to composite losses and deep learning.

  • 1 Introduction: DP-SGD relies on privacy amplification from perfectly uniform sampling or shuffling, creating practical deployment challenges for large datasets and federated learning.Federated systems may provide little control over which data subset is available at each time step.
  • 1 Introduction: DP-FTRL is an online-learning-based differentially private algorithm that does not rely on privacy amplification.It is designed to permit arbitrary data-access order while retaining competitive privacy, utility, and computation trade-offs.
  • 1.2 Our Contributions: DP-FTRL provides tighter regret guarantees, including extensions to unconstrained and composite-loss settings such as ℓ1-regularized objectives.The composite-loss extension preserves the regularizer within the optimization formulation rather than treating it through a more complicated approximation.
  • 1.2 Our Contributions: For linear and least-squared losses, DP-FTRL achieves optimal population risk, while providing the best known single-pass guarantee for general Lipschitz convex losses.The single-pass property contrasts with methods requiring multiple passes over the dataset.
  • 1.2 Our Contributions: A correlated-noise DP-SGD variant is equivalent to DP-FTRL in the unconstrained setting, and traditional DP-SGD has asymptotically similar per-step noise once t = ω(n).This connection helps explain the empirical relationship between the two approaches.

2 Errata and Fixes for the ICML 2021 version

The authors corrected privacy accounting for the no-tree-restart case because the earlier analysis understated a user’s contributions across tree nodes and epochs. Corrected empirical evaluations show that the crossover behavior depends on the number of training epochs.

  • 2 Errata and Fixes for the ICML 2021 version: The prior privacy analysis incorrectly computed complete-binary-tree sensitivity when DP-FTRL ran across multiple training epochs.A user can contribute to multiple leaf nodes and more than once to a single non-leaf node.
  • 2 Errata and Fixes for the ICML 2021 version: Corrected MNIST, CIFAR-10, and EMNIST evaluations show that more training epochs shift the ε crossover point to a larger value.For small numbers of epochs, the crossover point remains unchanged.

3 Background

The background introduces differential privacy, DP-SGD, privacy amplification, and tree-based aggregation. These tools establish the privacy mechanisms and data-access assumptions that motivate DP-FTRL.

  • Differential Privacy: Approximate DP and Rényi DP are used throughout, with meaningful guarantees assuming small constant ε and δ ≪ 1/|D|.The paper considers both example-level and user-level privacy, though empirical federated-learning results use user-level privacy.
  • DP-SGD and Privacy Amplification: DP-SGD clips individual gradients and adds Gaussian noise to minibatch gradients before performing stochastic-gradient updates.Its privacy analysis commonly uses sampling or shuffling amplification.
  • DP-SGD and Privacy Amplification: Uniform random sampling or Poisson sampling can reduce the noise required for each DP-SGD step through privacy amplification.The amplification benefit depends on the minibatch-selection mechanism.
  • Tree-based Aggregation: Tree-based aggregation privately releases prefix sums by representing a data stream with a complete binary tree and summing O(log(t)) nodes for time t.Each stream element appears in log(T) tree nodes, so Gaussian noise is calibrated through composition.

4 Private Follow-The-Regularized-Leader

DP-FTRL adapts Follow-The-Regularized-Leader to private online learning using tree aggregation, supporting arbitrary data order without privacy amplification. Its momentum variant improves empirical trade-offs for non-convex models, while the method can match amplified DP-SGD up to logarithmic factors in relevant regimes.

  • Core algorithm: DP-FTRL provides privacy guarantees for data processed in arbitrary, even adversarially chosen, order without requiring convex losses.Its utility guarantees still require convex losses.
  • Core algorithm: The algorithm linearizes each loss at the current model and privately maintains prefix sums of clipped gradients through tree aggregation.GetSum returns the prefix sum privately, with noise added to the aggregate.
  • Privacy and noise: The tree-aggregation prefix-sum error is bounded with high probability by a quantity scaling with Lσ and logarithmic factors in n and 1/β.The bound applies simultaneously over time steps with probability at least 1 − β.
  • Momentum variant: Momentum DP-FTRL has superior empirical privacy/utility trade-offs for training non-convex models, although the paper gives no formal regret guarantee for this variant.The authors conjecture that momentum smooths jumps caused by changing tree-aggregation noise.
  • Computation and memory: DP-FTRL requires the same minibatch-gradient computation as DP-SGD but stores up to log2(t)+2 past gradient/noise information vectors.These stored vectors are precomputed objects that can remain in memory.
  • Comparison with DP-SGD: When t = Ω(n), amplified DP-SGD and DP-FTRL have comparable noise up to a polylog(n) factor, and experiments find DP-FTRL competitive with amplified DP-SGD.The comparison concerns the same privacy level and an ε = O(1) setting.

5 Regret and Population Risk Guarantees

The paper establishes high-probability regret and population-risk guarantees for DP-FTRL under convex losses, with tighter results for linear and least-squares losses. In restricted linear and least-squares settings, the method achieves optimal population risk up to logarithmic factors.

  • Guarantee scope: DP-FTRL’s guarantees cover adversarial regret for general convex losses, tighter stochastic regret for linear and least-squares losses, and population risk via online-to-batch conversion.All guarantees are high-probability over the algorithm’s randomness.
  • Adversarial regret: The regret theorem handles a fully adaptive adversary choosing losses from previous model outputs without access to the algorithm’s internal randomness.The guarantee is stated for Algorithm AFTRL with optimally selected regularization and privacy-calibrated noise.
  • Composite losses: Composite-loss guarantees accommodate convex data-independent regularizers such as the ℓ1 norm, without requiring additional assumptions on those regularizers.The algorithm linearizes the losses rather than the regularizers.
  • Least-squares losses: For least-squares losses on i.i.d. data, AFTRL-LS provides differential privacy together with a high-probability stochastic-regret guarantee.The setting uses losses of the form (y_i − ⟨x_i, θ⟩)^2.
  • Population risk: For least-squares and linear losses, online-to-batch conversion yields optimal population risk up to logarithmic factors.The paper presents this as a consequence of the tighter stochastic-regret guarantee.

6 Practical Extensions

The paper extends DP-FTRL to minibatches and repeated data participation, addressing practical training patterns beyond its single-sample, single-epoch formulation. These extensions trade sensitivity and privacy-accounting complexity against computation and utility.

  • Minibatch DP-FTRL: Minibatch DP-FTRL estimates each update gradient over a batch instead of a single data sample.This changes the number of steps per epoch to ⌈n/q⌉ for batch size q.
  • Minibatch DP-FTRL: Using batches scales the per-batch ℓ2-sensitivity from L to L/q, which is incorporated into the privacy accounting.The reduced sensitivity accompanies the increased batch size.
  • Multiple participations: DP-FTRL-TreeRestart supports multiple epochs by using separate aggregation trees and composing their privacy costs with strong composition.It is described as the simplest repeated-participation approach.
  • Multiple participations: DP-FTRL-NoTreeRestart uses one aggregation tree across multiple epochs and can process data in arbitrary order when each example appears at most E steps.Repeated appearances increase sensitivity because a user can affect multiple leaves and interior nodes.
  • Multiple participations: DP-FTRL-SometimesRestart combines shared trees within epoch blocks with strong composition across blocks to improve privacy/utility trade-offs.The example uses 100 epochs, resetting the tree every 20 epochs and composing five blocks.

7 Empirical Evaluation

The evaluation compares DP-FTRL with amplified and unamplified DP-SGD across privacy, utility, and computation, including centralized and federated settings. DP-FTRL generally improves over unamplified DP-SGD and can match or exceed amplified DP-SGD with modestly higher computation.

  • Evaluation setup: The study evaluates privacy, test accuracy, and computation cost across MNIST, CIFAR-10, EMNIST, and StackOverflow.StackOverflow uses user-level privacy in a federated-learning setting; the image tasks use example-level privacy.
  • Privacy/utility trade-offs: DP-SGD without amplification remains substantially worse than amplified DP-SGD, even after a fourfold computation increase on the image datasets.At its highest ε, unamplified DP-SGD is worse than the amplified baseline at its lowest ε.
  • Privacy/utility trade-offs: At fixed computation, DP-FTRL improves relative to the amplified DP-SGD baseline as ε increases and can outperform it at larger ε.This pattern is reported across the image datasets and also for StackOverflow.
  • Privacy/utility trade-offs: With a fourfold batch-size increase, DP-FTRL almost always matches or outperforms amplified DP-SGD, including at the lowest ε on CIFAR-10.The experiments use minibatch size, training iterations, and epochs as computation proxies.
  • Federated evaluation: In StackOverflow experiments, unamplified DP-SGDM nearly matches amplified DP-SGDM only after a fourfold report-goal increase, while DP-FTRL performs better at that cost.At the original cost, DP-FTRL outperforms the baseline for larger ε.

8 Conclusion

The paper concludes that DP-FTRL provides strong theoretical guarantees and competitive empirical privacy/utility/computation trade-offs without privacy amplification. It also identifies unresolved questions about general convex-loss optimality and smaller-ε performance.

  • Conclusion: DP-FTRL has the tightest known DP regret guarantees and the best known excess population-risk guarantees for a single-pass algorithm on non-smooth convex losses.For linear and least-squared losses, it achieves optimal population risk.
  • Conclusion: On benchmark datasets, DP-FTRL can outperform amplified DP-SGD at large ε and remain competitive across ε with a modest batch-size computation increase.The comparison does not rely on privacy amplification for DP-FTRL.
  • Open questions: The paper leaves open whether DP-FTRL achieves optimal excess population risk for all convex losses in a single pass.It also asks whether a better tree-based gradient-sum estimator can narrow the empirical gap at smaller ε.

B.2 Proof of Theorem 4.1

The proof establishes privacy by analyzing the tree aggregation structure through which DP-FTRL accesses private information. It also relates the DP-FTRL update to noisy SGD under specified parameter and noise choices.

  • Privacy proof: Because all private-information access occurs through the tree, the privacy proof reduces to analyzing tree initialization, updates, and sum queries.Each data vector affects at most ⌈lg(n + 1)⌉ tree nodes.
  • Update equivalence: The non-private FTRL and SGD updates coincide under the stated regularization and learning-rate parameterization.The noisy case extends this comparison by incorporating Gaussian noise terms.
  • Update equivalence: The DP-FTRL update can be expressed using tree-aggregation noise b_t, with the corresponding incremental noise represented by a_t = b_t − b_{t−1}.The proof compares this form with the noisy-SGD recurrence under matched choices of parameters.

C.1 Proof of Theorem 5.1

The proof establishes privacy and regret guarantees for DP-FTRL and its least-squares adaptation using tree-aggregated noisy updates, regularization, and concentration bounds.

  • General DP-FTRL regret: Theorem 5.1 provides a high-probability regret guarantee for AFTRL outputs against any comparator θ∗.The guarantee is stated over the algorithm's randomness and assumes an ℓ2-Lipschitz loss bound L.
  • General DP-FTRL regret: The proof compares private AFTRL models with hypothetical non-private FTRL models on the same linearized loss sequence.It then combines deviation bounds with standard FTRL regret analysis.
  • General DP-FTRL regret: Optimizing λ and substituting the privacy-calibrated noise scale σ yields the theorem's final regret bound.The argument combines bounds for the regularization term and the privacy-induced noise term.
  • Least-squares adaptation: Algorithm 2 adapts DP-FTRL to least-squared losses by maintaining noisy tree aggregates for bias vectors and covariance matrices.The covariance aggregation uses p × p matrices, and its privacy proof measures covariance sensitivity in Frobenius norm.
  • Least-squares adaptation: Theorem C.3 gives Algorithm 1 a differential privacy guarantee under bounded feature norms and labels, while Theorem C.4 states stochastic regret for least-squared losses.The least-squares result assumes i.i.d. data and bounded quantities specified in the theorem statement.
  • Multi-epoch variants: Tree-restart variants obtain privacy guarantees through per-epoch composition, while tree completion adds virtual zero samples to reduce the final pre-restart noise.The completion trick changes the tree structure without increasing sensitivity from the virtual samples.

D.3.1 A Binary Tree Completion Trick and the Privacy Analysis

Binary-tree completion reduces noise in the last prefix sum before a restart by adding virtual zero steps, but the improvement must be weighed against extra privacy cost.

  • Noise dependence: Prefix-sum noise in the original tree aggregation scales with the number of set bits in the queried leaf's binary representation.This makes the noise depend on the prefix-sum location within the tree.
  • Tree completion: For CIFAR-10 with 50,000 examples and batch size 2,000, seven virtual steps complete the 25-node tree to 32 nodes.The virtual steps represent fixed zero samples rather than additional private gradients.
  • Tree completion: The last-step noise improves by a factor of 3 under original tree aggregation and roughly 4 with the cited tree-completion trick, from approximately 2.05 to 0.51.The text identifies the final pre-restart noise as especially important because future models depend on it.
  • Privacy accounting: Virtual samples do not increase sensitivity because they are fixed to zero, although adding tree nodes still has a privacy cost.The construction appends virtual leaves and ignores them in sensitivity computation.
  • Privacy accounting: The completion trick has a scale-versus-privacy trade-off: gains may be outweighed when the tree is far from the next power of two.The text expects greater benefit when the tree is already nearly complete.

E.2 Comparison of Optimizers with their Momentum Variants

The experiments compare original and momentum variants of DP-SGD and DP-FTRL across centralized image classification and federated StackOverflow training. Momentum improves DP-FTRL consistently and improves DP-SGD in the smaller-epoch CIFAR-10 setting, while efficient tree aggregation further improves DP-FTRL.

  • Centralized learning: DP-SGDM outperforms DP-SGD for smaller-epoch CIFAR-10 training, while DP-SGD is better for larger-epoch training; other settings are similar.
  • Centralized learning: DP-FTRLM is always at least as accurate as DP-FTRL and sometimes performs better.
  • Federated learning: Momentum improves StackOverflow performance for both SGD and FTRL at relatively small noise and stabilizes DP-FTRL at relatively large noise.
  • Federated learning: DP-FTRLM converges faster and performs better than vanilla DP-FTRL on StackOverflow training curves.
  • Efficient tree aggregation: Efficient tree aggregation always outperforms vanilla tree aggregation for FTRLM in the centralized image-classification experiments.
  • Efficient tree aggregation: Efficient tree aggregation raises the DP-FTRLM noise multipliers meeting 23% and 24.5% StackOverflow test-accuracy targets from (0.268, 0.067) to (0.387, 0.149).

F.2 Centralized Training with Large Number of Epochs by Interleaving Restarting and Non-restarting

The large-epoch experiments evaluate restarting and tree completion for DP-FTRL on CIFAR-10 and EMNIST. Intermediate restart schedules are most effective, but tree completion helps or hurts depending on the schedule and dataset.

  • CIFAR-10: Restarting every epoch or not restarting produces accuracy incomparable to DP-SGD, whereas restarting every 20 epochs performs much better without tree completion.
  • CIFAR-10: Tree completion helps restarting every 5 epochs but hurts restarting every 20 epochs, demonstrating a schedule-dependent trade-off.
  • CIFAR-10: Without tree completion, restarting every 5 epochs with tree completion gives the best accuracy and crosses over with DP-SGD near ε ≈18; with completion, restarting every 20 epochs is best and crosses over near ε ≈14.
  • CIFAR-10: DP-FTRL is always better than DP-SGD without amplification in the evaluated large-epoch settings.
  • EMNIST: On EMNIST, restarting every 5 epochs with tree completion achieves the best accuracy and outperforms amplified DP-SGD starting from ε ≈5.

G.1 Details of Hyperparameter Tuning

The StackOverflow tuning procedure fixes selected hyperparameters before searching noise multipliers and evaluates larger report goals. Increasing report goal and noise proportionally slightly improves utility but requires a much larger report goal for nontrivial privacy.

  • Noise tuning: DP-FTRLM test accuracy decreases from 25.15% at ε = ∞ to 20.22% at ε = 8.5 when 100 clients per round are fixed.
  • Noise tuning: The tuning procedure fixes clip norm to 1 and client learning rate to 0.5 based on Figure 11 before searching server learning rates.
  • Report goal: Increasing report goal from 100 to 1000 while proportionally increasing noise multipliers slightly improves test accuracy to 25.19% for DP-SGDM and 24.67% for DP-FTRLM.
  • Report goal: Both report goals 100 and 1000 provide trivial privacy guarantees for the target utility; DP-FTRLM requires report goal 2.06e4 to obtain ε < 10 with a population of 3.42e5.
Loading 2103.00039v3…