PaperlayerView exact revision on arXiv

Source-linked AI summary

Differentially-Private "Draw and Discard" Machine Learning

Vasyl Pihur, Aleksandra Korolova, Frederick Liu, Subhash Sankuratripati, Moti Yung, Dachuan Huang, Ruogu Zeng

arXiv:1807.04369v2cs.CRcs.LGstat.ML

TL;DR

DDML addresses the challenge of training useful machine-learning models while preserving user privacy from the data collector and meeting distributed-system constraints. It combines client-side differentially private updates with random sampling and replacement among server-held models. The paper reports local privacy guarantees, variance stabilization, and practical deployment evidence, while noting that feature-level privacy can scale with the number of correlated features.

  • Problem

    Existing distributed learning approaches provide limited protection from the data collector or impose constraints that complicate locally private machine-learning deployment.

  • Method

    DDML adds calibrated Laplace noise to client-side model updates and randomly draws, updates, and replaces one of k server-held model instances.

  • Results

    DDML provides local differential privacy, variance-stabilizing model learning, asynchronous scalable training, and evidence of practical deployment viability.

  • Takeaways & Limitations

    Random draw-and-discard architecture offers a practical way to combine client-side and server-side privacy protections with scalable continuous model training.

  • Takeaways & Limitations

    The framework provides feature-level privacy, so privacy loss scales with the number of features when features are correlated.

Abstract

from arXiv · show

In this work, we propose a novel framework for privacy-preserving client-distributed machine learning. It is motivated by the desire to achieve differential privacy guarantees in the local model of privacy in a way that satisfies all systems constraints using asynchronous client-server communication and provides attractive model learning properties. We call it "Draw and Discard" because it relies on random sampling of models for load distribution (scalability), which also provides additional server-side privacy protections and improved model quality through averaging. We present the mechanics of client and server components of "Draw and Discard" and demonstrate how the framework can be applied to learning Generalized Linear models. We then analyze the privacy guarantees provided by our approach against several types of adversaries and showcase experimental results that provide evidence for the framework's viability in practical deployments.

I. INTRODUCTION

DDML is a client-centric framework for locally private machine learning that combines privacy, scalability, asynchronous communication, efficiency, and spam protection. It addresses prior limitations of trusted-curator learning and supports distributed GLM training while preserving user data locally.

  • I. INTRODUCTION: The framework randomly samples and replaces one of k server-held model instances, combining client-side privacy with a scalable cloud architecture.This strategy is intended to reduce hotspotting from excessive writes to individual data items.
  • I. INTRODUCTION: DDML focuses on Generalized Linear Models, including linear and logistic regression, because their convexity supports client-side learning without complex convergence issues.The authors state that extending the approach to neural networks and other iterative-gradient models is relatively straightforward.
  • I. INTRODUCTION: DDML provides local differential privacy by applying noisy model-weight updates on clients instead of sending raw gradients to the server.The design also strengthens protection against realistic server-side adversaries by separating pre-update and post-update model knowledge.
  • I. INTRODUCTION: DDML supports lock-free asynchronous communication and distributed spam protection without requiring access to users’ private data.The k model instances provide replicated weight distributions that can help assess whether incoming updates are fraudulent.
  • I. INTRODUCTION: The framework has been implemented for ranking and security applications, including models with approximately 50,000 weights and peak traffic of about 200 updates per second.The authors report k = 20 as a practical efficiency–scale trade-off for avoiding hotspotting.
  • II. RELATED WORK: Unlike trusted-curator approaches that collect data before private computation, DDML targets local privacy so users need not trust the data collector with their raw data.Prior local-model work largely focused on aggregate statistics rather than training more complex machine-learning models.

III. DRAW AND DISCARD MACHINE LEARNING

DDML combines client-side noisy updates with a server architecture that randomly updates one of k model instances. The paper applies this model-agnostic framework to GLMs and describes its differentially private SGD-based client procedure.

  • III. DRAW AND DISCARD MACHINE LEARNING: DDML’s core architecture combines client-side noise addition with a server that maintains and randomly updates one of k model instances.Together, these components target differential privacy and efficient client–server model training.
  • A. GLMs: The framework is model-agnostic in principle, but this work limits its detailed treatment to Generalized Linear Models, especially logistic regression.GLMs relate responses to features through a distribution-dependent link function.
  • B. DDML Client-Side Update: For GLMs, stochastic gradient descent estimates the objective gradient from a small batch of client-local observations rather than requiring all training data simultaneously.The objective is decomposed across observations, and each client computes an approximate gradient from its available batch.
  • B. DDML Client-Side Update: The client performs differentially private SGD by clipping the average gradient and adding Laplace noise before updating the model weights.The update uses locally stored observations, with normalized features and responses and a privacy budget controlling the noise scale.
  • B. DDML Client-Side Update: The client workflow requests a model, computes a clipped noisy update, and returns the updated model to the server.The server algorithm initializes k models, sends a randomly selected instance, receives its update, and replaces a random instance.

C. DDML Server-Side Draw and Discard

The Draw-and-Discard server maintains k model instances, randomly draws one for client updating, and randomly discards one on replacement. This design supports averaging and stabilizes the variance among model instances over time.

  • C. DDML Server-Side Draw and Discard: Each update draws one of k model instances for a client, then replaces a uniformly random instance with the returned model.The number of instances remains k in expectation, while concurrent requests can make exact replacement behavior only approximate.
  • C. DDML Server-Side Draw and Discard: The random replacement scheme has practical implications for performance, model quality, privacy, and spam protection.The paper presents this simple server mechanism as central to DDML’s broader systems design.
  • C. DDML Server-Side Draw and Discard: The k instances are initialized around starting weights with variance tied to the Laplace noise variance used for client updates.Correct initialization and calibrated initial noise are important for the framework’s spam-detection mechanism.
  • C. DDML Server-Side Draw and Discard: The server averages the k model instances’ weights for final predictions, while applications may instead average their predicted values.This aggregation uses the replicated models as an ensemble at prediction time.

D. Properties and Features of DDML

DDML’s properties combine variance stabilization with scalable, asynchronous model updating. Random replacement preserves expected intra-model variance while distributing load without locking.

  • 1) Variance-stabilizing Property of DDML:: DDML maintains the expected intra-model variance at k⁻²σ²_i after random replacement and mean-zero noise updates.The theorem’s setup and proof use total variance to show that same-model and different-model replacements offset one another.
  • 1) Variance-stabilizing Property of DDML:: The variance argument decomposes total variance into expected conditional variance plus variance of conditional means.The proof explicitly invokes the Law of Total Variance and accounts for replacement probabilities, including 1/k for selecting the same model.
  • 1) Variance-stabilizing Property of DDML:: Replacing a different model partitions the instance set and creates a nonzero conditional-mean variance that is included in the finite-k calculation.The derivation notes that the variance component uses k−1 rather than k because the number of instances is finite.
  • 1) Variance-stabilizing Property of DDML:: Random discarding dissipates additional intra-model variability, including after convergence when stochastic-gradient contraction becomes small or absent.This allows continued client-side Laplace-noise updates without accumulating unbounded model-instance variation.
  • D. Properties and Features of DDML: Maintaining k model instances supports thousands of asynchronous updates per second through random load distribution without locking or server-side aggregation.The architecture is described as simple to implement and able to continue learning while update requests arrive concurrently.

2) Asynchronous Learning.:

DDML uses random model-instance sampling and discarding to reduce server-retained data while supporting privacy and abuse checks. Averaging its instances can also match or exceed server-side batching under practical settings.

  • 3) Differential Privacy.:: Randomly retaining the last k client models, discarding models at random, and avoiding server-side batching limits server-retained data while strengthening privacy against weaker adversaries.The framework’s privacy analyses distinguish these protections from the local-model guarantee against the strongest adversary.
  • 4) Ability to Prevent Spam without Sacrificing Privacy.:: Replicated weight instances enable spam detection by testing whether an updated weight lies within [µ − tσ, µ + tσ] without tracking each client’s original instance.This avoids trading away server-side privacy for anti-abuse monitoring.
  • 4) Ability to Prevent Spam without Sacrificing Privacy.:: For practical k ∈ [20, 30], averaging model instances outperforms server-side batching of 1,000+ gradients in the cited real-world example.Equivalent loss and accuracy occur when k is approximately the square root of the server batching size.

5) Improved Performance.:

DDML’s privacy analysis combines clipped, noisy client updates with adversary-specific threat models. It establishes local privacy against a channel listener and stronger guarantees for weaker observers who lack update-level visibility.

  • E. Parameter Tuning and Clipping: Clipping gradients to [-1, 1] gives update sensitivity 2γ, while clipping to [-0.1, 0.1] would reduce sensitivity by a factor of 10 to γ/5.The learning rate γ controls convergence and the magnitude of the privacy-sensitive update.
  • IV. PRIVACY OF DDML: DDML analyzes feature-level privacy, with extension to model-level privacy by scaling noise by the number of features or adjusting gradient norms.The stated analyses focus on feature-level differential privacy.
  • A. Adversary Modeling: The framework distinguishes channel listeners, internal threats, and opportunistic threats by their access to communication and model snapshots.The first sees both pre- and post-update models; the second lacks source-model identity; the third observes models only after many intervening updates.
  • A. Adversary Modeling: The internal threat receives stronger privacy than the channel listener because it lacks knowledge of which server model was the update’s pre-image.This adversary can observe server instances but cannot align the source model with the latest update.
  • A. Adversary Modeling: Opportunistic observers benefit from many independent noise additions after a user update and, in expectation and with high probability, obtain significantly stronger privacy than the local model.The strength depends on the order in which the user’s data was ingested and the elapsed update window T_k.
  • A. Adversary Modeling: The privacy summary reports an expected guarantee of ϵ/(k−1) for the listed adversary analysis.The supplied table passage presents this value as the section’s expected privacy guarantee.
  • B. Privacy against Channel Listener (Adversary I): DDML guarantees ϵ-differential privacy against the channel listener through calibrated Laplace noise and sensitivity bounded by 2γ.Replacing Laplace noise with Gaussian noise is possible with calibration from the cited results.

C. Privacy against Internal Threat (Adversary II)

DDML amplifies privacy against an internal adversary by randomizing which model instance is updated or discarded, creating uncertainty about the update’s pre-image. The expected privacy loss is reduced for k models, while worst-case loss occurs when all instances are identical.

  • Privacy amplification mechanism: The expected privacy loss against adversary II is 1/k · ϵ2, averaging over the server’s random choices of model instances.
  • Privacy amplification mechanism: The discard scenario gives perfect privacy because the updated model’s pre-image is no longer observable among the k instances.For generalized linear-model updates, the returned model provides equal support for any client input when the pre-image is unknown.
  • Privacy amplification mechanism: When model instances are non-identical, uncertainty about which instance was returned and which was the pre-image provides additional privacy amplification.
  • Privacy analysis: For k = 2, case analysis yields ϵ2 = 0.5ϵ, with the maximum attained when the two model instances are identical.
  • Practical qualification: The Lemma 1 privacy-loss bound is unlikely to be realized in practice because all server instances are unlikely to be identical, but formalizing this intuition remains future work.

D. Privacy against Opportunistic Threat (Adversary III)

Against an opportunistic adversary observing a model after later updates, DDML gains privacy from both eventual discard and accumulated noise. For sufficiently large T, the resulting approximate privacy improves with the square root of the observation delay.

  • Privacy amplification sources: DDML’s privacy amplification against adversary III comes from both discarding the user’s model instance and accumulating noise through later updates.
  • Discard amplification: Each contribution has perfect privacy with probability 1/k because the model instance containing it can be discarded in the long term.
  • Privacy guarantee: With high probability, DDML provides an (ϵT, δT)-differential privacy guarantee when T is sufficiently large.Here, T counts updates to the relevant model instance between the user’s submission and adversarial observation.
  • Analysis conditions: The result assumes a sufficiently large update count and uses a contractive noisy-process argument together with Laplace-noise accumulation.
  • Quantitative bound: For δT = 10^-8, the analysis gives ϵT ≈ 3ϵ/√T against adversary III.

V. EXPERIMENTS AND RESULTS

The experiments evaluate DDML’s learning behavior, scalability-oriented update strategy, and production deployment using logistic-regression models. They compare DDML with server-side batching and alternative update schemes while also demonstrating a real-world deployment.

  • Experimental scope: The study evaluates multi-class logistic regression under varying k and privacy budgets, measuring training loss, hold-out accuracy, and convergence against server-side batching.
  • Update-scheme comparisons: Alternative DDML update schemes include sampling updates with probability 1/k, always replacing the same instance, and averaging models before overwriting them.
  • Production deployment: A production experiment demonstrates DDML training a small logistic regression in a distributed environment serving millions of daily users.

A. Experiment Configurations

The experiments use MNIST multi-class logistic regression to study model-instance count, server batching, and client privacy noise under standardized training conditions. Results indicate a practical k range, a batching comparison tied to k^2, and a performance cost for smaller privacy budgets.

  • Experiment configurations: The MNIST setup uses 60,000 training examples, 10,000 test examples, 6,000 simulated clients, γ = 0.001, and 20 passes over the data.
  • Comparing k: For k ∈ [20, 30], DDML provides scalability without a large short- to medium-term performance hit, although k = 1 performs best in the tested finite-sample setting.As sample size increases, the configurations converge theoretically on the convex objective.
  • Server-side batching: When server batch size Ns > k^2, server-side batching is empirically inferior in finite-sample performance; k = 10 and Ns = 100 produce overlapping curves.
  • Server-side batching: Using k = 20 model instances can handle high-throughput traffic without pausing learning to average gradients, unlike server-side batching.
  • Privacy parameter ϵ: For client privacy noise, ϵ > log(16) causes no substantial performance impact, whereas ϵ = log(3) has some negative impact.

B. Comparing to Alternative Server Architectures

DDML’s Draw and Discard architecture matches or exceeds the accuracy of alternative update strategies while trading some data utilization for scalability and privacy benefits.

  • The architecture accepts some short- to medium-term performance loss from partitioning updates across k model instances in exchange for scalability and privacy benefits.The reported loss is attributed to partitioning training data into k groups rather than permanently losing the data itself.
  • At k = 20, random replacement has approximately the same data utilization as accepting 1/k of model updates, confirmed by overlapping MNIST accuracy curves.The strategy rejects 19 updates and accepts 1 on average when k = 20.
  • Same Instance Replace is essentially equivalent to Draw and Discard because all k model instances receive M/k updates in expectation and reach similar optimization locations.This equivalence occurs even though Same Instance Replace does not discard updates.
  • Averaging decreases the effective learning rate and therefore reduces performance when the original learning rate is not too large.For Same Instance Replace, averaging makes the learning rate exactly half.
  • Draw and Discard performs as well or better in accuracy than the alternative update strategies considered, including averaging strategies.The comparison uses k = 20 and learning rate γ = 0.001.
  • Across k values, relative strategy performance remains similar, while reducing the learning rate by tenfold hurts Draw and Discard more than the server-side strategy.The learning rate affects performance more than the number of model instances k, so losses from k instances may be insignificant when learning-rate selection is difficult.

C. Logistic Regression With Known Weights Trained On Distributed Devices

The paper evaluates DDML on a known-weight logistic model and a production phishing-URL detector, showing close parameter recovery and practical deployment at scale.

  • C. Logistic Regression With Known Weights Trained On Distributed Devices: The known-weight deployment trained a 33-weight logistic regression model using five predictors and their two-way crosses in a production environment with millions of daily users.The model specification is controlled by the server, allowing different models to use the same underlying client data without client-side changes.
  • C. Logistic Regression With Known Weights Trained On Distributed Devices: After 983,068,969 updates, estimated logistic-model weights were very close to the true parameters, with 80% accuracy, 79% precision, and 72% recall.The experiment used k = 30 and learning rate γ = 0.005 without update noise.
  • A. Predicting Phishy URLs in Chat: The phishing application combines URL and webpage-content features, including domains, paths, query parameters, character patterns, keywords, forms, scripts, and page properties.The model targets discovery of previously unseen malicious URLs in an adversarial setting.
  • A. Predicting Phishy URLs in Chat: The production phishing model received 1,730,624,961 updates across 387 weights using k = 20, ϵ = log(32), and learning rate γ = 0.001.The model was deployed for predicting whether URLs were phishy.
  • A. Predicting Phishy URLs in Chat: The phishing model achieved very good recall but relatively low precision because attackers continually change their methods, and deployment increased discovery of new phishing URLs by orders of magnitude.The authors were exploring visual page features and potentially nonlinear models as extensions.

B. Ranking Application Based on User Text Input

DDML was deployed for large-scale ranking and discussed as a practical trade-off: modest model-training sacrifices can provide scalability, privacy, and operational simplicity, with known privacy and model-scope limits.

  • B. Ranking Application Based on User Text Input: A production ranking model covering about 7,000 items improved user engagement by single percentage points in globally deployed smaller versions.The model uses uni-grams, bi-grams, tri-grams, and selected crosses with about 50,000 weights and 1MB size.
  • VII. DISCUSSION: With k model instances, DDML provides an asynchronous and scalable client-server architecture, but sufficient serving redundancy is required because reads and writes are symmetric.The architecture was deployed at scale for millions of daily active clients.
  • VII. DISCUSSION: Replacing model instances at random can sacrifice training efficiency, but the authors frame this as a trade-off for scalability, ease of implementation, spam detection, and additional privacy.The discussion gives a 100-write-request versus 10-write-per-second example to motivate unavoidable utilization trade-offs.
  • VII. DISCUSSION: DDML extends readily to neural networks and differentiable objectives, whereas extending it to decision trees is harder and requires further distributed-optimization research.The stated extension boundary concerns models whose objectives can be written as sums of differentiable functions.
  • VII. DISCUSSION: The privacy loss can grow with repeated submissions through composition, and feature-level privacy scales with the number of correlated features.Model-level privacy would require increasing noise according to the number of included features.
  • VII. DISCUSSION: The paper focuses on pure local differential privacy and identifies Gaussian noise, refined adversary models, and Rényi or concentrated differential privacy as possible directions for tighter analyses or improved utility.The authors also hypothesize that hybrid privacy approaches combining locally private and non-local or public data could improve accuracy and privacy.
  • VIII. CONCLUSIONS: The paper’s main contribution is a random draw-and-discard server architecture intended to combine scalability, uninterrupted learning, client- and server-side privacy, and practical deployment.The empirical focus remains on simpler linear models to avoid convergence issues while studying privacy and infrastructure properties.
Loading 1807.04369v2…