Training a large recommendation or extreme-classification model with differential privacy (DP: a guarantee that the trained model barely changes whether or not any one person's data was used) usually ruins the sparsity that makes these models cheap. Each example touches only a handful of rows of a huge embedding table, but the standard private training algorithm adds noise to every row. Recent work restores sparsity by updating only the rows that clear a noisy popularity threshold. Those surviving rows, however, are scattered across the table, and GPUs cannot run scattered single-row updates efficiently. Their matrix engines need small dense tiles. The fix from the sparse-kernels literature is to reorder rows so that rows active at the same time sit next to each other. That reordering is computed from which rows co-occur in users' data, which is exactly the private information DP is meant to protect.
We propose to compute this row ordering privately. Each row is summarized by a noisy MinHash sketch, a short fingerprint whose collision rate estimates the overlap between the sets of examples that touch two rows. Rows are then clustered into GPU-sized blocks, and private sparse training selects and updates whole blocks rather than individual rows. The claim goes beyond speed. If rows that co-occur share a block, each example touches far fewer blocks, so the contribution bound that private selection must enforce becomes cheaper, and that can recover utility. The cost of the approach is also visible in advance. Rows that sit in a selected block but received no real gradient still get noise, and the privacy budget spent on the layout is unavailable for training.
Core Claim
A row layout computed once, cheaply and under a small explicitly accounted privacy budget, from private co-occurrence similarity changes private sparse training in two ways. It makes block-level updates dense enough to run as tiled matrix operations on GPU Tensor Cores. It also lowers the number of distinct blocks each example touches, which reduces the noise needed for private block selection. Whether the second effect outweighs the noise added to padding rows and the budget spent on the layout is the central empirical question. We expect a net gain at moderate privacy levels and give a test that could refute this.
Two quantities govern the trade-off. Let $L_b$ be the maximum number of distinct blocks any single example touches after layout. Let the fill rate $f$ be the fraction of rows inside selected blocks that carry a nonzero true gradient. Private block selection bounds each example to $L_b$ blocks instead of $L$ rows, so a good layout shrinks the selection sensitivity. Gradient noise, meanwhile, is spread over a $1/f$ times larger set of rows than the truly active ones. The total budget, written in zero-concentrated DP (a version of DP whose privacy costs simply add across steps), splits as
$$\rho_{\text{total}} = \rho_{\text{layout}} + \rho_{\text{select}} + \rho_{\text{grad}},$$
where $\rho_{\text{layout}}$ pays for the noisy MinHash sketches, $\rho_{\text{select}}$ for the per-step noisy block thresholding, and $\rho_{\text{grad}}$ for the Gaussian noise on block gradients. A layout helps only if the savings it creates in the last two terms exceed what it costs in the first.
Where This Sits in Prior Work
The motivating result is Sparsity-Preserving Differentially Private Training of Large Embedding Models. Its DP-AdaFEST method keeps only embedding rows whose noisy per-batch contribution clears a threshold, cutting nonzero gradient entries by $10^6\times$ relative to standard private training. It reports a simulated $150\times$ wall-clock speedup on accelerators with dedicated sparse-lookup units and accuracy comparable to dense private training. Its sparsity is row-unstructured, and its speedup assumes TPU SparseCore-style hardware. We keep its noisy-threshold selection but apply it to blocks of rows placed together for GPU execution.
The method we reuse comes from High Performance Unstructured SpMM Computation Using Tensor Cores. SMaT reorders rows by Jaccard similarity of their sparsity patterns and packs them into blocked compressed sparse row tiles (e.g. $16\times 8$ in FP16). It reports up to $125\times$ over cuSPARSE, $2.6\times$ over the next-best library, and an $8.4\times$ reduction in per-row block imbalance on the matrix mip1. SMaT reorders static public matrices in plaintext as costly preprocessing. We compute a similar ordering privately, once per training run, from sketches rather than exact sets. The ordering must then serve a sparsity pattern that changes every step.
The similarity primitive has a precedent in EsPRESSo. That work estimates Jaccard similarity from length-$k$ MinHash signatures exchanged through a cryptographic set-intersection-size protocol, reporting about 9% average error at $k=100$. Its guarantees are cryptographic and hold against semi-honest parties, not DP, and it never feeds a learning system. Two other papers use locality-sensitive hashing (random projections that map similar items to similar short codes) to estimate similarity inside learning systems. Large-Scale Distributed Learning via Private On-Device Locality-Sensitive Hashing does so for neuron selection, and FedProp does so for building a cross-client data graph. Neither has formal DP, and FedProp names DP as open. Our proposal is the first in this file to put a similarity sketch under an explicit DP accountant and spend it on hardware layout.
Three papers show that sparsifying updates helps privacy by shrinking sensitivity or noise footprint. Gradient sparsification for efficient wireless federated learning with differential privacy uses random masks and a $\sqrt{s}C$ clipping threshold. Constrained differentially private federated learning for low-bandwidth devices uses a static top-$K$ set chosen on public data. Differentially Private Iterative Gradient Hard Thresholding for Sparse Learning uses noisy hard thresholding for linear models. All three produce unstructured masks, and none addresses how the surviving coordinates are laid out in memory.
Two papers constrain the design. Learning N:M Fine-grained Structured Sparse Neural Networks From Scratch obtains a real $2\times$ speedup from 2:4 patterns, meaning two nonzeros in every four consecutive entries. That density is far above what row-sparse embedding updates have, so N:M is the wrong structure here, and blocks of rows are the right one. Minimum Variance Unbiased N:M Sparsity for the Neural Gradients warns that biased gradient pruning can collapse training (ResNet-18 falling from 70.6% to 48.2%). Thresholded block selection is biased in the same way that DP-AdaFEST is biased, so we track and, where needed, correct that bias. The correction is an unbiased variant that keeps low-contribution blocks with a small probability and reweights them.
Research Program
The first component is the private layout mechanism. For each embedding row $r$, let $S_r$ be the set of training examples that touch it. Every example is first restricted to at most $L$ rows, which bounds its influence. We then compute a $k$-entry one-bit MinHash signature per row and release it under randomized response, which flips each bit with a calibrated probability. Under the bound, one example changes at most $Lk$ signature bits, which fixes the noise level for a given $\rho_{\text{layout}}$. Rows below a noisy frequency cutoff are excluded from the sketch and assigned to blocks at random. This saves budget on rows that would rarely be selected anyway. From the noisy signatures we estimate pairwise Jaccard similarity and run a greedy SMaT-style clustering into blocks of $B$ rows. The mechanism has three design levers: $k$, $B$, and the head-row cutoff. We will derive the variance of the debiased Jaccard estimate as a function of $\rho_{\text{layout}}$, because the clustering needs only coarse neighbor rankings, not accurate similarities.
The second component is block-level private training. Each step clips per-example gradients and counts, per block, how many examples touch it, with each example capped at $L_b$ blocks. It then adds noise to the counts and updates only blocks above a threshold, adding Gaussian noise to all rows of each selected block. We will analyze how $L_b$ and $f$ enter the noise-to-signal ratio. This gives a predicted crossover block size beyond which padding noise dominates the selection savings, and the prediction can be checked against measurement.
The third component is the kernel. We will adapt a blocked-sparse update in the SMaT style to a mask that changes every step but a row order that stays fixed. Because the layout is frozen, no per-step reordering is needed, and the remaining overhead is building the per-step block index list.
Baselines
The naive reference point is dense DP-SGD, which adds noise to every row. Where the table is too large to run this, we report its cost analytically. It anchors both ends: it is the utility target and the speed floor.
The strongest existing method is DP-AdaFEST from Sparsity-Preserving Differentially Private Training of Large Embedding Models. We run it at row granularity on the same GPU, with its selected rows executed through the best available unstructured sparse kernel. We use the same total $\rho$, the same models and data, and the same hyperparameter search budget over threshold, clipping norm, and noise split. The file reports a $10^6\times$ reduction in nonzero gradient entries, a simulated $150\times$ speedup, and accuracy comparable to dense DP-SGD. No reported Criteo AUC or log-loss value was found on Lacuna for DP-AdaFEST, so we reproduce it ourselves. Beating it means matching its utility within noise across seeds while running at least several times faster on a GPU. The stronger outcome would be better utility at equal $\rho$ at strict privacy levels, which would mean the $L_b$ reduction helps privacy, not just speed.
Three layout ablations isolate the key ingredient, each run with the identical block-level trainer and budget. A random layout shows what blocking costs without any similarity information. A layout sorted by noisy frequency is the cheap heuristic, placing popular rows together. A layout computed from a disjoint public or held-out split, in the spirit of the public-proxy selection in Constrained differentially private federated learning for low-bandwidth devices, spends no privacy budget. A non-private oracle that computes the exact plaintext Jaccard layout measures the ceiling, and the gap between it and our layout is the price of privatizing the layout. Our method must beat the frequency-sorted layout to justify itself.
Why not just…?
Why not just sort rows by noisy frequency and skip similarity altogether? This is the most serious threat. Popular rows co-occur partly because they are popular, and frequency sorting costs almost no budget. It does not group mid-frequency rows that co-occur within a topic or user segment. Those rows decide the fill rate outside the head of the table. The frequency-sorted ablation answers this directly. If it matches the private Jaccard layout on $f$, $L_b$, utility, and speed, we will report that the similarity mechanism is unnecessary and that the contribution is the block-level private trainer.
Why not just compute the layout on public data, as FL-TOP does for parameter selection? Constrained differentially private federated learning for low-bandwidth devices shows public proxies can work well, reaching 0.81 accuracy on Fashion-MNIST at a 0.5% update ratio versus 0.56 for standard private federated learning. That works only when a matching public dataset exists. For item co-occurrence in recommendation logs, such data is rarely available. Sparsity-Preserving Differentially Private Training of Large Embedding Models found that static selection lags adaptive selection under distribution shift. We test this by building the public layout from a temporally earlier slice of Criteo, which mimics realistic drift.
Why not just run DP-AdaFEST and let an SMaT-style kernel reorder the surviving rows each step? SMaT's Jaccard reordering is a heavy one-time preprocessing step on static matrices. Rerunning it on every step's freshly selected rows would cost more than the update it accelerates. Reordering on the actual selected set would also make the layout depend on per-step private data with no accounting. We measure the per-step reordering time against the update time to show the gap.
Why not just use 2:4 structured gradient sparsity, which already has hardware support? Embedding updates touch a tiny fraction of rows. Forcing exactly two of every four entries to be nonzero would densify them by orders of magnitude, and the MVUE result shows that keeping such patterns unbiased requires stochastic selection that is not private. N:M remains appropriate for the dense layers of the same model, and we leave those under standard DP-SGD.
Proposed Experiments
The main testbed is Criteo click-through prediction, the benchmark DP-AdaFEST uses. We evaluate AUC and log-loss at several privacy levels from strict to loose, together with measured A100 step time, fill rate $f$, and the empirical distribution of blocks touched per example. The second testbed is the output layers of extreme multi-label models on Delicious-200K and Amazon-670K from Large-Scale Distributed Learning via Private On-Device Locality-Sensitive Hashing, using precision-at-k. Their label rows co-occur strongly, so the layout should matter most there. As a kernel sanity check, we reproduce SMaT's reordering gain on SuiteSparse matrices, including mip1. That confirms our blocked kernel behaves as reported before we put it inside private training.
The decisive check is a sweep over block size $B$ and layout budget $\rho_{\text{layout}}$ at fixed total $\rho$. Three outcomes are possible. If the private Jaccard layout beats row-level DP-AdaFEST in utility at strict privacy, the contribution-bound argument holds. If it only matches utility while speeding up, the contribution is engineering and the paper says so. If utility falls below the frequency-sorted or random layouts, then padding noise and layout cost dominate, and the claim is refuted. A second check compares the measured crossover block size with the one predicted from $f$ and $L_b$. A third tracks gradient bias by comparing thresholded block selection with its unbiased reweighted variant. This tests whether the training-collapse risk documented for biased gradient pruning appears in this regime.
References
- Sparsity-Preserving Differentially Private Training of Large Embedding Models
- High Performance Unstructured SpMM Computation Using Tensor Cores
- EsPRESSo: Efficient Privacy-Preserving Evaluation of Sample Set Similarity
- Large-Scale Distributed Learning via Private On-Device LSH
- FedProp: Cross-client Label Propagation for Federated Semi-supervised Learning
- Gradient sparsification for efficient wireless federated learning with differential privacy
- Constrained differentially private federated learning for low-bandwidth devices
- Differentially Private Iterative Gradient Hard Thresholding for Sparse Learning
- Learning N: M Fine-grained Structured Sparse Neural Networks From Scratch
- Minimum Variance Unbiased N:M Sparsity for the Neural Gradients