LazyDP: Co-Designing Algorithm-Software for Scalable Training of Differentially Private Recommendation Models

Juntaek Lim, Youngeun Kwon, Ranggi Hwang, Kiwan Maeng, G. Edward Suh and Minsoo Rhu

Recommender systems that pick your ads are trained on deeply personal data, so companies want to train them with differential privacy — but the standard method forces adding random noise to every entry of a table that can be terabytes large, on every single step, which is ruinously slow; this work from KAIST and Meta observes that almost all of that table sits untouched for long stretches, so it lazily postpones the noise until an entry is actually needed and then adds it all in a single draw using a fact about Gaussian math, training the exact same private model about 119 times faster.

The argument in one glance

Problem

Private training turns a sparse recommender update into a dense one

Recommender systems train on private user data, so differential privacy matters, but its standard method, DP-SGD, must add Gaussian noise to every entry of a giant embedding table on every iteration. This turns the normally sparse, cheap embedding update into a dense, table-wide "noisy" update, creating a compute bottleneck (sampling noise for every entry) and a memory-bandwidth bottleneck (writing the whole table).
What people did

Run standard DP-SGD on the recommender

Apply DP-SGD as it is used for vision and language models: add noise to the whole embedding table each iteration and write the dense noisy gradient back.
Why it fell short

On terabyte tables, this is ruinously slow

Embedding tables reach tens of gigabytes to terabytes, so noise sampling (a Gaussian value, via trigonometric and logarithmic operations, for every entry) is enormously compute-heavy, and writing the dense table-sized noisy gradient is limited by memory bandwidth. Both scale with the huge table, so private recommender training suffers massive overheads.
This paper's idea

Be lazy about the noise, and aggregate the sampling (LazyDP)

LazyDP is an algorithm-software co-design with two ideas. Lazy noise update: because most embeddings are untouched for many iterations, delay their noise updates until just before an embedding is actually accessed, removing most of the memory traffic. Aggregated noise sampling: instead of sampling many delayed noise values and summing, use the fact that a sum of Gaussians is a single Gaussian to draw one, cutting the sampling compute by orders of magnitude. It trains a mathematically equivalent private model about 119 times faster.

Why this problem is worth solving

The models that decide which ads and items you see are trained on some of the most sensitive data there is, which is exactly why private training matters.

Differential privacy is the widely accepted standard for protecting individual privacy in machine learning. Informally, it guarantees that the trained model behaves almost the same whether or not any single person’s data was included, so an adversary who can inspect the model cannot tell whether a particular individual’s example was used to train it. The standard way to achieve this when training a neural network is DP-SGD, a variant of the usual training algorithm that does two things: it clips each training example’s gradient so no single example can push the model too far, and it adds carefully calibrated random noise, drawn from a Gaussian (normal) distribution, to the gradients. The noise is what mathematically masks any individual’s contribution. DP-SGD has been studied extensively for computer vision and natural language models, and it works, at a cost. But recommender systems — the models hyperscalers use to power personalized ads, trained on private records of what users visited and bought — badly need privacy too, and their computational challenge under DP-SGD had not been explored, which is the gap this work fills.

Recommender systems have a structure that private training punishes far more harshly than a vision or language model.

A modern recommender combines a dense neural network with a sparse embedding layer, and the embedding layer is the crux. It stores embedding tables: enormous arrays holding one embedding vector per item in a category — and a category can have millions to billions of items, like every video on a platform — so a single table can be tens or hundreds of gigabytes, and large recommenders reach terabytes. To make a prediction, the model gathers only the few embedding vectors matching the current input and pools them together. This is naturally sparse: each training step touches only a handful of the table’s entries, so ordinary training does a cheap, sparse gradient update that modifies just those entries. DP-SGD destroys this. To provide its privacy guarantee, it must add Gaussian noise to every embedding in the table, on every iteration, whether or not that embedding was gathered. That transforms the sparse update into a dense noisy update that rewrites the entire, gigantic table each step. The result is two severe bottlenecks. Noise sampling is compute-bound: a Gaussian value must be drawn for every table entry, and each draw involves trigonometric and logarithmic operations. And the noisy gradient update is memory-bandwidth-bound: it writes back a dense tensor the size of the whole table. On terabyte-scale tables, both are crippling.

What people did before, and where it broke

Apply DP-SGD as-is to recommenders. Add Gaussian noise to the whole embedding table each iteration, as done for vision and language models. Where it broke. Sampling noise for every entry is compute-bound and writing the dense table-sized noisy gradient is memory-bandwidth-bound, and both scale with tables that reach terabytes.
Study private training only for vision and language. Rely on the extensive prior work optimizing DP-SGD for those domains. Where it broke. Those models lack the huge sparse embedding tables that make DP-SGD’s dense noise the dominant cost, so their optimizations do not address the recommender bottleneck.
Accept the overhead as the price of privacy. Train privately at whatever cost DP-SGD imposes. Where it broke. The overhead is so large on terabyte tables that private recommender training becomes impractical at scale.
The gap. No approach removed DP-SGD’s compute and memory bottlenecks for recommender embedding layers while keeping the exact same privacy. Doing that through algorithm-software co-design is what LazyDP contributes.

How LazyDP works

From dense per-step noise to lazy, aggregated noise

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Delay the noise for the embeddings nobody is using. LazyDP’s first move is to stop writing noise to embeddings that are not being accessed: because gathers are sparse, most of the table sits untouched for many iterations, only accumulating noise updates that change values no one is about to read, so LazyDP delays those updates until an embedding is actually scheduled to be accessed, skipping the vast majority of the dense table-wide writes. Refusing to perform an update whose result will not be observed yet, and deferring it until the moment it is actually needed, is the same discipline the redundant-writeback work covered elsewhere on this site follows, declining to push data out to memory until doing so is genuinely required rather than paying the cost on every step.

Collapse many delayed noise draws into one. Delaying the writes still leaves the compute of eventually sampling all the skipped noise, so LazyDP’s second move exploits a property of normal distributions: the sum of many independent Gaussian samples is itself a single Gaussian sample with the combined variance, so instead of drawing one noise value per delayed iteration and adding them up, it draws a single aggregated value, cutting the noise-sampling cost by orders of magnitude. Combining many deferred contributions into one operation, rather than performing each separately when they finally come due, is the same efficiency the edge-training work covered elsewhere on this site captures with delayed aggregation, letting work accumulate and then be resolved in a single combined step instead of paying for each piece on its own.

Optimize aggressively while producing the identical model. What makes both moves safe is that LazyDP is engineered to yield a result mathematically equivalent to baseline DP-SGD: the delayed, aggregated noise applied just before each access is exactly the noise the unoptimized algorithm would have added, so the trained model, and therefore its privacy guarantee, is unchanged. Transforming a computation drastically for speed while guaranteeing the output is provably identical to the original is the same standard the verified-circuit-rewrite work covered elsewhere on this site holds itself to, reshaping the computation only in ways proven to preserve exactly what it produces, so correctness is never traded for performance.

Following an embedding through LazyDP

Tracing one embedding vector through lazy, aggregated noise

A trace of LazyDP handling a single embedding under private training, following the paper's two optimizations.

Step 1 of 5

A giant table that DP-SGD would noise in full

A recommender is trained privately. Under baseline DP-SGD, its huge embedding table would get Gaussian noise added to every entry every iteration and be written back in full.

Tables reach terabytes, so this is enormously expensive.

Why it works

Privacy forces dense work onto a sparse layer. Because DP-SGD must add noise to every embedding every iteration → the embedding layer’s naturally sparse, low-memory access becomes a dense, table-wide update → so private recommender training is dominated by noise-related compute and memory traffic that plain training never incurs.
Most embeddings are idle for long stretches. Because embedding gathers are sparse, most vectors are not accessed in a given iteration and very likely not soon after → their noise updates change values no one is about to read → so those updates can be safely delayed until just before access.
Delaying the writes kills the memory bottleneck. Because the noisy gradient update is a memory-bandwidth-bound write of a table-sized tensor → skipping the writes for untouched embeddings removes the bulk of that traffic → so the memory bottleneck largely disappears.
A sum of Gaussians is one Gaussian. Because the total delayed noise is a sum of independent normal samples, which is itself a single normal sample of larger variance → one aggregated draw replaces many individual ones → so the noise-sampling compute drops by orders of magnitude.
Equivalence preserves the guarantee. Because the delayed, aggregated noise is applied exactly before each access → the model LazyDP trains is mathematically identical to baseline DP-SGD → so the speedup comes with no loss of accuracy or privacy.

What it costs (trade-offs and scope)

The threat model is slightly weaker. LazyDP protects an arbitrary training example against an adversary who has access to the final trained model and all other training data. The paper notes this adversary is slightly weaker than the one baseline DP-SGD assumes, though it provides the same level of protection against most practical adversaries. The equivalence is to DP-SGD’s training outcome under this threat model.
It requires bookkeeping of update times. Delaying noise means tracking, per embedding, when its noise was last applied, so the right amount of aggregated noise can be added before access. This bookkeeping is far cheaper than the writes it avoids, but it is added state and logic.
The benefit depends on sparsity. Lazy noise update wins because most embeddings are untouched for many iterations. A workload with dense access patterns, where most of the table is gathered frequently, would have less to delay and would benefit less.
It targets the embedding layer. The optimizations address the noise sampling and noisy gradient update of private embedding-table training. The dense neural-network parts of a recommender, and other DP costs, are outside this specific contribution.
The speedup is against a specific baseline. The average 119 times improvement is measured over a state-of-the-art DP-SGD training system on representative recommender models; other systems, models, and privacy settings would shift the figure.
Correctness rests on the aggregation being exact. The privacy guarantee holds only if the aggregated noise is statistically identical to the sum it replaces; the design relies on that mathematical equivalence being precise, not approximate.

The evaluation

Three ways to train a recommender's embedding layer

Property	Non-private SGD	LazyDP
Differential privacy
Embedding update
Noise-sampling cost	None
Memory traffic	Low
Training throughput		About 119 times faster than DP-SGD

Three ways to train a recommender's embedding layer, as framed by the paper. Non-private SGD does a cheap sparse update but offers no privacy. Baseline DP-SGD provides differential privacy but must add Gaussian noise to every entry of a table that can reach terabytes each iteration, making noise sampling compute-bound and the dense table-sized noisy gradient write memory-bandwidth-bound. LazyDP keeps the exact same privacy through an algorithm-software co-design: lazy noise update delays the noise for the many untouched embeddings until just before they are accessed, removing most of the memory traffic, and aggregated noise sampling replaces the many delayed noise draws with a single Gaussian draw of the combined variance (since a sum of Gaussians is a Gaussian), cutting the sampling compute by orders of magnitude. Because the delayed, aggregated noise applied before each access equals what DP-SGD would have added, the trained model is mathematically equivalent. Over a state-of-the-art DP-SGD system on representative recommender models, LazyDP delivers an average 119 times training throughput improvement, under a threat model the paper notes is slightly weaker than baseline DP-SGD but equivalent against most practical adversaries.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

LazyDP is a satisfying piece of algorithm-software co-design, the kind where a careful look at a workload’s structure plus a small mathematical insight yields an enormous speedup with no loss of what matters. The problem is real and specific: recommender systems are trained on deeply private data and increasingly need differential privacy, but DP-SGD’s requirement to add Gaussian noise to every entry of a terabyte-scale embedding table on every iteration turns the embedding layer’s natural sparsity into a dense, table-wide update, creating a compute bottleneck in noise sampling and a memory-bandwidth bottleneck in writing the noisy gradient. LazyDP attacks both. Lazy noise update observes that most embeddings sit untouched for long stretches and simply defers their noise until just before they are accessed, eliminating most of the memory traffic. Aggregated noise sampling then uses the fact that a sum of independent Gaussians is a single Gaussian to replace the many deferred draws with one, collapsing the sampling compute. Crucially, the design guarantees a model mathematically equivalent to baseline DP-SGD, so accuracy and the privacy guarantee are untouched, and the payoff is an average 119 times training speedup. Read the scope precisely. The equivalence holds under a threat model the paper acknowledges is slightly weaker than original DP-SGD, though the same in practice against most adversaries. The lazy scheme requires per-embedding bookkeeping of update times, its benefit depends on the access pattern being sparse, it targets the embedding layer specifically, and the headline number is relative to a particular baseline and set of models. The durable idea is that a privacy or correctness constraint that appears to force expensive dense computation can often be satisfied far more cheaply by exploiting the workload’s sparsity and the algebra of the operation — deferring work no one is waiting on, and combining what must eventually be done into a single step.

Background

Why exploiting sparsity and algebra beats brute force

It helps to see LazyDP within a recurring lesson in systems for machine learning: when a constraint seems to demand dense, brute-force computation, the biggest wins usually come from noticing that most of that computation is either unnecessary right now or algebraically collapsible. Here the constraint is privacy, which naively demands touching every entry of a giant table every step, and the two escapes are classic — defer the work that no one is about to observe, and use a mathematical identity to do many operations as one. The warehouse-scale memory-traffic work covered elsewhere on this site distills the first half of that lesson: the transfers a system manages not to make are where the efficiency lives, and much of what looks like required data movement is avoidable once the system recognizes it changes nothing anyone will read. The common thread is that the dominant cost in these workloads is moving data, and that both laziness (not moving what is not yet needed) and aggregation (moving or computing many things as one) are powerful because they cut that movement at its source rather than merely making each operation faster. As models and their tables keep growing, and as privacy and other correctness constraints spread, the systems that stay affordable will be the ones that look past the naive dense formulation to the sparse, deferrable, and algebraically compressible computation hiding underneath.

If you remember only three things

1. Recommender systems power personalized ads and are trained on intimate user data, so differential privacy matters, but its standard method, DP-SGD, is uniquely brutal for them. A recommender's core is a sparse embedding layer with enormous embedding tables (one vector per item, reaching tens of gigabytes to terabytes) that are normally accessed sparsely — each step gathers a handful of vectors and does a cheap sparse update. DP-SGD requires adding Gaussian noise to every table entry on every iteration to guarantee privacy, turning the sparse update into a dense, table-wide noisy update. This creates two bottlenecks: noise sampling is compute-bound (a Gaussian value, via trigonometric and logarithmic operations, for every entry) and the noisy gradient update is memory-bandwidth-bound (writing a dense table-sized tensor).
2. LazyDP is an algorithm-software co-design with two ideas that remove both bottlenecks while keeping the exact same privacy. Lazy noise update exploits sparsity: because most embeddings are untouched for many iterations and only accumulate noise no one reads, LazyDP delays their noise updates until just before an embedding is actually accessed, skipping the vast majority of the dense noise-update writes and removing most memory traffic; it tracks per-embedding when noise was last applied so the right amount is added before access. Aggregated noise sampling then handles the remaining compute: instead of sampling one Gaussian per delayed iteration and summing, it exploits that a sum of independent Gaussians is itself a single Gaussian of the combined variance, drawing one aggregated value and cutting the noise-sampling compute by orders of magnitude.
3. Because the delayed, aggregated noise applied before each access is exactly what baseline DP-SGD would have added, LazyDP trains a mathematically equivalent, differentially private model — no accuracy or privacy is sacrificed — while delivering an average 119 times training throughput improvement over a state-of-the-art DP-SGD system on representative recommender models. Scope: the equivalence holds under a threat model the paper notes is slightly weaker than original DP-SGD but the same against most practical adversaries; the benefit depends on sparse access patterns; it targets the embedding layer; and the number is relative to a particular baseline. The durable lesson is that a privacy or correctness constraint that appears to force expensive dense computation can often be met far more cheaply by exploiting the workload's sparsity and the algebra of the operation — deferring work no one is waiting on and combining what must be done into a single step.

Check yourself

Check your understanding

1. Why is DP-SGD so much more expensive for recommender systems than for vision or language models?
2. What is the "lazy noise update" idea?
3. What is "aggregated noise sampling," and why does it work?
4. LazyDP is 119 times faster than baseline DP-SGD. Why can it be trusted not to weaken the model or its privacy?

Sources

The paper is “LazyDP: Co-Designing Algorithm-Software for Scalable Training of Differentially Private Recommendation Models” by Juntaek Lim, Youngeun Kwon, Ranggi Hwang, Kiwan Maeng, G. Edward Suh, and Minsoo Rhu, published at ASPLOS 2024, DOI 10.1145/3620665.3640384. The authors are at KAIST, Meta, Cornell University, and Pennsylvania State University.

This explainer is based on the full text of the paper, obtained from the authors’ arXiv version (arXiv:2404.08847). The problem framing (recommender systems trained on private data, differential privacy and DP-SGD adding Gaussian noise, the sparse embedding layer with terabyte-scale embedding tables, and the transformation of the sparse gradient update into a dense noisy update that adds noise to the whole table each iteration), the identification of the two bottlenecks (noise sampling as compute-bound because a Gaussian value drawn via trigonometric and logarithmic operations is needed for every entry, and the noisy gradient update as memory-bandwidth-bound because it writes a dense table-sized tensor), the two optimizations (lazy noise update that delays noise for untouched embeddings until just before access to reduce memory traffic while ensuring delayed updates are applied before an embedding is accessed, and aggregated noise sampling that replaces many delayed Gaussian draws with a single Gaussian draw of the combined variance by exploiting that a sum of Gaussians is a Gaussian, reducing sampling compute by orders of magnitude), the threat model (protecting an arbitrary training example against an adversary with access to the final model and all other training data, slightly weaker than original DP-SGD but equivalent against most practical adversaries), and the result (an average 119 times training throughput improvement over a state-of-the-art DP-SGD system while training a mathematically equivalent, differentially private model) are all drawn directly from the paper. Background explanations of differential privacy, DP-SGD, embedding tables, sparse access, and the Gaussian distribution are standard and provided to make the paper’s contribution understandable.