PaperlayerView exact revision on arXiv

Source-linked AI summary

FLAME: Differentially Private Federated Learning in the Shuffle Model

Ruixuan Liu, Yang Cao, Hong Chen, Ruoyang Guo, Masatoshi Yoshikawa

arXiv:2009.08063v4cs.LGcs.CRstat.ML

TL;DR

High-dimensional federated aggregation challenges shuffle-model privacy because local-noise error can grow with dimension. FLAME combines local randomization, shuffling, and protocols using subsampling and private Top-k selection; SS-Topk reports a 33.94% accuracy improvement over curator-model-based FL.

  • Problem

    Existing shuffle protocols for basic tasks may not be viable for multi-dimensional FL aggregation, where local-noise error can grow with dimension.

    Source: Introduction · p. 1

  • Method

    FLAME uses shuffling for privacy amplification, with SS-Double adding subsampling and SS-Topk using gradient sparsification with private dimension selection.

    Source: Introduction · p. 1, Utility Boosting with Top-k (SS-Topk) · p. 6, Index Privacy · p. 6

  • Results

    33.94% accuracy improvement over curator-model-based FL; SS-Topk loses 1.48% accuracy versus non-private FL under (2.348, 5e−6)-DP per epoch.

    Source: Introduction · p. 2

  • Takeaways & Limitations

    The authors conclude that privacy amplification and private Top-k selection improve testing accuracy under high-dimensional settings without relying on a trusted server.

    Source: Conclusion · p. 8

    SS-Simple’s central privacy amplification diminishes with dimension, while per-dimension randomization with a negligible privacy budget incurs large noise.

    Source: Limitation of SS-Simple · p. 4

Abstract

from arXiv · show

Federated Learning (FL) is a promising machine learning paradigm that enables the analyzer to train a model without collecting users' raw data. To ensure users' privacy, differentially private federated learning has been intensively studied. The existing works are mainly based on the \textit{curator model} or \textit{local model} of differential privacy. However, both of them have pros and cons. The curator model allows greater accuracy but requires a trusted analyzer. In the local model where users randomize local data before sending them to the analyzer, a trusted analyzer is not required but the accuracy is limited. In this work, by leveraging the \textit{privacy amplification} effect in the recently proposed shuffle model of differential privacy, we achieve the best of two worlds, i.e., accuracy in the curator model and strong privacy without relying on any trusted party. We first propose an FL framework in the shuffle model and a simple protocol (SS-Simple) extended from existing work. We find that SS-Simple only provides an insufficient privacy amplification effect in FL since the dimension of the model parameter is quite large. To solve this challenge, we propose an enhanced protocol (SS-Double) to increase the privacy amplification effect by subsampling. Furthermore, for boosting the utility when the model size is greater than the user population, we propose an advanced protocol (SS-Topk) with gradient sparsification techniques. We also provide theoretical analysis and numerical evaluations of the privacy amplification of the proposed protocols. Experiments on real-world dataset validate that SS-Topk improves the testing accuracy by 60.7\% than the local model based FL.

Introduction

The paper addresses the difficulty of applying shuffle-model privacy to high-dimensional federated aggregation, where local-noise error can grow with dimension. It introduces FLAME and protocols that use shuffling, subsampling, and gradient sparsification to improve privacy amplification and learning accuracy.

Introduction

  • FLAME uses shuffle-model privacy amplification: anonymized local outputs provide stronger central-view privacy, requiring less local noise for the same privacy level.The framework is intended to combine curator-model accuracy with strong privacy without relying on a trusted party.Source: Introduction · p. 1
  • High-dimensional local-noise error can grow with dimension, and existing shuffle protocols for basic tasks may not work for multi-dimensional FL aggregation.The paper notes that participating users per iteration typically number only a few thousand, making aggregation high-dimensional.Source: Introduction · p. 1
  • 33.94% accuracy improvement over curator-model-based FL; SS-Topk loses 1.48% accuracy versus non-private FL under (2.348, 5e−6)-DP per epoch.The authors report these results for the proposed protocols on a real-world dataset.Source: Introduction · p. 2
  • SS-Simple extends one-dimensional randomization and aggregation to each update dimension, while its amplification diminishes as dimensionality grows.SS-Double adds subsampling and dummy padding; SS-Topk uses private dimension selection to improve utility, especially in high-dimensional settings.Source: Introduction · p. 2

Preliminaries

The preliminaries define the privacy models and shuffle protocol used by FLAME, then introduce composition and subsampling properties for the later analysis.

Preliminaries

  • The preliminaries establish the trust boundaries and properties needed to formalize the paper’s problem.The section first clarifies trust boundaries, then introduces properties used throughout the paper.Source: Preliminaries · p. 2

The Curator and Local Models

  • In the curator model, a trusted analyzer sees raw data; local differential privacy instead has users randomize data before sending it to the server.Under the stated LDP condition, observing the collected results or their sum implies the corresponding DP guarantee.Source: The Curator and Local Models · p. 2

The Shuffle Model

  • A shuffle protocol composes local randomization, permutation by a shuffler, and analysis; shuffling can amplify privacy so central ϵc is below local ϵl.The single-message setting has each user send one locally randomized message, which the shuffler uniformly permutes before analysis.Source: The Shuffle Model · pp. 2–3

Composition and Subsampling Properties

  • The section presents adaptive composition bounds and privacy amplification by subsampling m records from n, with the latter scaling the privacy parameters by m/n.It also notes that the privacy blanket decomposes outputs into data-dependent and uniform-random components, and gives a tighter amplification bound through numerical evaluation.Source: Composition and Subsampling Properties · p. 3, The Shuffle Model · p. 3

FLAME Framework

FLAME separates users, a shuffler, and an analyzer so shuffled, randomized local updates can be aggregated without placing full trust in one party. Its SS-Simple protocol extends one-dimensional randomization across dimensions, but its privacy amplification weakens as dimension grows.

FLAME Framework

  • FLAME assigns users to randomize local updates, a shuffler to permute messages, and an analyzer to estimate their mean and update the global model.The update is θt ← θt−1 + z.Source: Parties · p. 3, FLAME Framework · p. 3
  • By introducing a shuffler, FLAME avoids placing full trust in any single party while aiming for better utility than LDP-FL.In DP-FL the trust boundary lies between analyzer and observer; in LDP-FL it lies between each user and the other parties.Source: Trust Boundaries · p. 3
  • FLAME separates indexes, values, and user identity: indexes should be selected data-obliviously, true gradient values remain hidden from the shuffler, and shuffled messages satisfy (ϵc, δc)-DP against the analyzer.The shuffler still needs users’ implicit identities to distribute model parameters and receive messages.Source: Trust Separation · pp. 3–4
  • The framework uses encoding, shuffling, and analysis, with protocol variants implementing different randomization and shuffling strategies.The analyzer and shuffler are assumed not to collude; otherwise FLAME reduces to LDP-FL, and the cryptographic primitives are assumed safe.Source: Trust Separation · p. 4, Security Assumptions · p. 4
  • SS-Simple applies one-dimensional randomization independently to each dimension using ϵld = ϵl/d, then composes the dimension-level privacy guarantees.Its central privacy level depends on dimension, and allocating a negligible privacy budget per dimension incurs large noise.Source: Simple Protocol (SS-Simple) · p. 4, Limitation of SS-Simple · p. 4

Double Amplification (SS-Double)

SS-Double strengthens shuffle-model privacy amplification by subsampling dimensions, while dummy padding enables shuffling and subsampling to be composed for multidimensional FL. Its analysis also identifies a privacy–noise trade-off as the padded size increases.

Double Amplification (SS-Double)

  • SS-Double samples k ≪ d dimensions, giving each perturbed dimension a larger local budget ϵ_l/k, and combines subsampling with shuffling for double amplification.The authors state that stronger amplification could allow fewer noises under the same central privacy level.Source: Intuition · p. 4
  • Because subsampling can make neighboring multidimensional datasets different sizes, its privacy amplification may not compose with shuffling directly; dummy padding fills each dimension to size n_p with blanket-distribution values.The shuffler then shuffles the padded messages.Source: Challenge · p. 4
  • A larger padded size n_p yields a smaller central privacy parameter ϵ_cd, but also implies more injected noise.The noise implication is stated in the analysis alongside the privacy effect.Source: Privacy and Utility Analysis · p. 5
  • The analysis composes the padded, dimension-level privacy guarantees into vector-level DP and derives an amplified central-privacy bound for SS-Double.The sample rate is β = k/d.Source: Privacy and Utility Analysis · p. 5
  • At d = 75755, SS-Double raises the privacy-amplification ratio from ×2.55 to ×137.36 compared with SS-Simple under the same per-dimension local budget.Figure 3 compares the amplification effect; the text reports the numerical ratios.Source: Simulation of Privacy Amplification · pp. 5–6, Figure 3 · p. 5

Utility Boosting with Top-k (SS-Topk)

SS-Topk uses magnitude-based gradient sparsification to improve utility in high-dimensional FL while limiting the privacy cost of revealing selected indexes. Its index-privacy parameter ν controls how much observing an index can increase the shuffler’s chance of identifying a Top-k dimension.

Utility Boosting with Top-k (SS-Topk)

  • Magnitude-based Top-k selection can improve convergence over random sampling, but revealing data-dependent indexes threatens user privacy.The challenge is to preserve index privacy while maintaining utility.Source: Utility Boosting with Top-k (SS-Topk) · p. 6
  • Index privacy bounds the shuffler’s Top-k prediction success to at most ν times the random-guessing rate k/d.The shuffler is the primary index-privacy adversary because it knows which user sent which indexes.Source: Index Privacy · p. 6
  • SS-Topk selects k Top-k dimensions and k(l − 1) non-top dimensions, perturbs the true values, pads the others with blanket draws, then permutes the dimensions into l messages.The per-dimension privacy budget is ϵ_lk = ϵ_l/k.Source: SS-Topk Protocol · p. 6
  • The strongest index privacy, ν = 1, is achieved when l = ⌈1/β⌉; SS-Topk’s valid l range depends on ν.The protocol’s shuffled padded results preserve the same double amplification effect as SS-Double for a given n_p.Source: Privacy Analysis · p. 7
  • Even at the no-index-privacy extreme, SS-Topk still provides a strong privacy guarantee because the shuffler knows only the Top-k indexes.A cited study reports that privacy attacks are significantly impaired even when Top-k indexes and values are known.Source: Privacy Analysis · p. 6

Evaluations

The evaluations compare SS protocols with private and non-private FL baselines and examine privacy amplification and parameter effects. SS-Topk exceeds DP-FL accuracy under matched central privacy, while the authors report that both double amplification and Top-k boosting are needed for this result.

Evaluations

  • 55.5% utility gain: SS-Topk improves over SS-Double at the same central privacy, while double amplification changes privacy from (0.91, 5 × 10−6)-DP to (0.24, 5 × 10−6)-DP.With n/np = 3, the maximum index privacy is ν = 3.125 with l = 16.Source: Comparison of Our Protocols · p. 7
  • 33.94% higher accuracy: SS-Topk exceeds DP-FL under the same central privacy of (0.24, 5 × 10−6)-DP.The authors contrast this with traditional one-dimensional results that place shuffle between LDP and DP.Source: Comparison with DP/LDP-FL · p. 7
  • Both double amplification and Top-k boosting are necessary to outperform DP-FL; without subsampling amplification, SS-Topk has (20.53, 5 × 10−6)-DP.The authors report that SS-Double cannot exceed DP-FL at (0.24, 5 × 10−6)-DP, whereas SS-Topk does.Source: Comparison with DP/LDP-FL · p. 7, Comparison under Variant Parameters · p. 7
  • A higher local privacy budget per dimension and a larger β improve testing accuracy, while a higher n/np ratio means less dummy-padding noise.The authors identify np as the key privacy-utility tuning parameter; at β = 1/10, the reported loss versus NP-FL is 1.48% for two epochs at (2.348, 5e−6)-DP per epoch.Source: Comparison under Variant Parameters · p. 7
  • Numerical evaluations with the Bennett inequality for the Laplace mechanism support the authors’ amplification results for generic local randomizers when bounds are available in closed form or by numerical evaluation.The evaluation refers to Figures 9 and 10.Source: Figure 9 · p. 7, Figure 10 · p. 7, Privacy Amplification · p. 8

Conclusion

FLAME is a shuffle-model differentially private federated learning framework intended to improve utility without a trusted server.

Conclusion

  • FLAME is a differentially private federated learning framework in the shuffle model that seeks better utility without a trusted server.The conclusion attributes improved testing accuracy in high-dimensional settings to privacy amplification and private Top-k selection.Source: Conclusion · p. 8
  • Privacy amplification and private Top-k selection are reported to boost testing accuracy in high-dimensional settings.Source: Conclusion · p. 8
  • The framework’s stated goal is better utility without relying on a trusted server.Source: Conclusion · p. 8

Related Works

The section contrasts curator and local differential privacy in federated learning, then reviews shuffle-model work and its potential for multi-dimensional aggregation. It situates this paper’s single-message approach among prior protocols and related federated-learning frameworks.

Private-preserving Federated Learning

  • Curator-model DP-FL protects whether a user participates through distributed model parameters, but assumes an honest analyzer that follows the private mechanism.Splitting the required noise among users gives central DP, but only weak local privacy against an untrusted analyzer unless heavy cryptography is used or εc is extremely small.Source: FL in the Curator Model (DP-FL) · p. 8
  • Local DP-FL perturbs each user’s vector before transmission, but its mean-estimation error has a dimension curse that can require looser privacy or many more users.Additional noise for stricter model-publishing privacy can further reduce utility.Source: FL in the Local Model (LDP-FL) · p. 8
  • The shuffle model generalizes local and central privacy through a non-colluding shuffler, with amplification proved initially for interactive protocols under a limited privacy-budget regime.Later work specialized amplification to one-bit randomized response and proposed the Privacy Blanket framework for stronger bounds.Source: Shuffle Model · p. 8
  • Prior shuffle protocols show more accurate real-summation estimation than the local model, while multi-message protocols can improve estimation over single-message protocols at greater communication cost.This work uses a single-message protocol and identifies extension to multi-message settings as a possible route to better accuracy.Source: Shuffle Model · p. 8
  • Other federated-learning work uses the general ESA framework or combines client and record subsampling with shuffling, but has different trust assumptions or orthogonal sampling choices.The latter approach samples clients and local records; its trust model for the shuffler differs from this work’s.Source: Shuffle Model · p. 8

Ethics Statement

The statement frames FLAME for privacy-preserving cross-device learning while flagging underexamined governance and robustness risks in deployment.

Ethics Statement

  • The paper introduces FLAME as a shuffle-model framework for differentially private federated learning without trusted parties.The statement names next-word prediction, fraud detection, and epidemic prediction as possible federated-learning applications.Source: Ethics Statement · p. 8
  • The discussion focuses on cross-device learning over personal data from small devices, with the aim of better performance under strong privacy guarantees.It connects this setting to information flow across millions of mobile devices and users’ data-privacy rights.Source: Ethics Statement · pp. 8–9
  • The statement flags unclear privacy-budget rules across iterative rounds and warns that local-update privacy could make user-side attack detection harder, biasing the global model.It calls for transparent privacy-budget settings so users can feel safe and be safe.Source: Ethics Statement · p. 9
  • It encourages robustness research for settings where prediction accuracy is highly sensitive.Source: Ethics Statement · p. 9

Related papers

Loading 2009.08063v4…