Two Ways Privacy Distorts the Long Tail in Recommenders

Recommender systems trained with differential privacy are a natural fit for sensitive logs such as purchases, listening histories, and health-adjacent shopping. Differential privacy is a guarantee that the trained model barely changes if any one user's data is removed. The standard way to train under it is DP-SGD: gradient descent in which each user's gradient is clipped to a fixed size and Gaussian noise is added. Work on classifiers shows this training hurts rare groups most. Nobody has asked what it does to rare items, the long tail of niche products, songs, and films that diversity-oriented recommendation tries to surface.

This note argues that DP-SGD distorts tail items in two opposite ways. First, clipping pulls rarely seen items toward the "mainstream" direction that popular items already dominate, which hides them. Second, the added noise accumulates on embedding rows that receive almost no real gradient, which inflates their scores at random. Because one effect lowers tail exposure and the other raises it, coverage and diversity metrics on private models can look healthy while the tail items being shown are mostly irrelevant. The proposal is to measure this decomposition, then remove both distortions with a cheap correction applied after training. Corrections applied after training cost no extra privacy budget because they only transform the already-private model. The correction pulls each noisy item embedding toward a prediction from its public item metadata, in proportion to how much noise that item is known to carry.

Core Claim

The noise DP-SGD adds to an item's embedding is public knowledge, fixed by the noise multiplier, clipping norm, learning rate, and number of steps. The real signal in that embedding grows with the item's interaction count. The ratio of the two, the item's signal-to-noise ratio, can therefore be estimated from a cheaply privatized popularity histogram. Given that estimate, the private embedding $\tilde v_i$ of item $i$ can be repaired by

$$\hat v_i = w_i\,(\tilde v_i - a_i \bar q) + (1-w_i)\,g(c_i), \qquad w_i = \frac{\hat s_i}{\hat s_i + \sigma_i^2},$$

The terms are as follows. $\bar q$ is the mean popular-item direction and $a_i$ is item $i$'s projection on it, computed from the released embeddings. $\sigma_i^2$ is the known accumulated noise variance on row $i$. $\hat s_i$ is the signal variance predicted from the item's privately counted popularity. $g(c_i)$ maps public content features $c_i$ (genre, category, text) into the collaborative embedding space and is fitted on the head items, whose private embeddings are reliable.

The first term undoes the drag toward the mainstream. The second replaces noise with a content-based guess exactly where noise dominates. The claim that is new and testable is this: at a fixed privacy budget, this correction raises the recall of relevant tail items and genuine category coverage beyond what direction-subtraction alone or improved private optimizers achieve. It also shows that some of the apparent diversity in uncorrected private models is noise-driven.

Research Program

The work begins with a diagnostic. On MovieLens 10M and Amazon Beauty and Grocery, we train matrix factorization and LightGCN both non-privately and under user-level DP-SGD at ε ∈ {1, 2, 5, 8}. User-level means a whole user's history is protected. We release only the item table; user vectors are computed locally from each user's own history. For each popularity decile we split the deviation of private item embeddings from the non-private ones into two parts: the component along $\bar q$, and the residual. We also track how often tail items are exposed and whether the exposed items are relevant.

The diagnostic tests a three-step chain. Disparate Impact in Differential Privacy from Gradient Misalignment shows that per-sample clipping bends averaged updates toward the majority direction. Mitigating Popularity Bias in Recommendation with Unbalanced Interactions: A Gradient Perspective shows that popularity bias in recommenders is itself a directional drift toward $\bar q$. Put together, these predict that clipping should enlarge the $\bar q$ component for mid-popularity items. Separately, accumulated noise should dominate the residual for the rarest deciles. If the diagnostic finds no directional component, the $a_i$ term is dropped and the proposal reduces to noise-aware shrinkage. If it finds no noise inflation, the shrinkage term is unnecessary. Either outcome is informative.

We then build the correction. The popularity histogram is released with a small slice of the budget (Laplace noise on counts). The content map $g$ is trained on head items, following the content-to-collaborative mapping idea in Intent Disentanglement and Feature Self-supervision for Novel Recommendation. That paper learns this mapping without privacy for cold-start items; we reuse it as a prior for noise-dominated items. Because $g$ is fit on released embeddings and public metadata, it adds no privacy cost.

Finally, we place the corrected model on an accuracy-diversity frontier. We optionally run the greedy relevance-plus-coverage selection of A Framework for Recommending Relevant and Diverse Items on top. That selection relies on meaningful distances between items, which noisy tail embeddings currently corrupt.

Baselines

The naive reference points are two models. One is non-private matrix factorization or LightGCN trained on the same splits, which gives the ceiling. The other is vanilla DP-SGD with the same backbone, privacy accounting, and budget, which shows the raw privacy cost.

The strongest cheap competitor is vanilla DP-SGD followed by the post-hoc subtraction of popular and conformity directions from Mitigating Popularity Bias in Recommendation with Unbalanced Interactions: A Gradient Perspective. That paper reports roughly 37% higher Recall@20 and 51% higher NDCG@20 than standard matrix factorization on a debiased MovieLens-10M test, without privacy. Because it is pure post-processing, it costs nothing in privacy. We tune its two subtraction weights with the same validation budget as our method.

The strongest private optimizer is DPSGD-Global-Adapt from Disparate Impact in Differential Privacy from Gradient Misalignment. It replaces per-sample clipping with global scaling and lifted minority accuracy on 1%-minority MNIST from 26.3% to 65.5%. We adapt it to per-user gradients in matrix factorization. To our knowledge it has never been run on recommenders.

We include DPIMF from Differentially Private Cross-Silo Recommendation from Implicit Feedback. It avoids per-step clipping through one-time objective perturbation and reports an average 18.3% Hit Ratio gain over the earlier private method DPLCF on MovieLens 10M. We also include DP-Fair from Fairness-aware Differentially Private Collaborative Filtering. It reports NDCG 10.61 against 10.21 for vanilla DP-SGD on Etsy Home & Living at ε = 1, using user-side constraints only. No tail-item numbers are reported for any private baseline. On Lacuna we found no reported result for item-side tail metrics under DP for any method.

Three ablations isolate the key ingredient. The first removes the shrinkage term, which reduces to direction subtraction. The second removes direction subtraction. The third replaces the private popularity histogram with exact counts, which measures the cost of privatizing popularity. Every method shares data splits, ε accounting, backbone dimension, and an equal number of tuning trials.

Our method beats a baseline only if two conditions hold together at matched ε and matched overall NDCG@20 (within one standard error over five seeds). Relevant-tail Recall@20 on the debiased test must improve. Category coverage must improve without an increase in the fraction of recommended tail items that are irrelevant.

Why not just…?

Why not just subtract the popularity direction after DP training? This is the most serious threat, because it is free and already strong without privacy. If the diagnostic shows that the privacy damage is almost entirely along $\bar q$, this baseline will match us, and we will report that as the result. Our prediction is that it cannot help the rarest items. Their error is dominated by isotropic noise orthogonal to $\bar q$, so subtracting $\bar q$ leaves noise-inflated, irrelevant scores. The "shrinkage removed" ablation settles this directly.

Why not just use a better private optimizer such as global scaling or objective perturbation? Both Disparate Impact in Differential Privacy from Gradient Misalignment and Differentially Private Cross-Silo Recommendation from Implicit Feedback can reduce the directional error. Neither can supply signal for items that a handful of users touched, because some noise must still be added. Our correction is applied on top of whichever optimizer wins, so it is complementary rather than competing. The test is whether it still adds relevant-tail recall when stacked on DPSGD-Global-Adapt and on DPIMF.

Why not just reweight tail interactions or loosen ε? Differential Privacy Has Disparate Impact on Model Accuracy notes that reweighting rare examples conflicts with the bounded per-user sensitivity DP-SGD requires: upweighting either gets clipped away or forces more noise. Loosening ε leaves the regime of interest. We nonetheless include an inverse-propensity-weighted DP-SGD run at matched ε so the claim is checked empirically rather than assumed.

Proposed Experiments

The main experiment covers MovieLens 10M (genres), Amazon Beauty and Grocery (categories), and Amazon Music, at ε ∈ {1, 2, 5, 8}. The backbones are matrix factorization and LightGCN, with five seeds each. Metrics are overall NDCG@20 and Recall@20, relevant-tail Recall@20 on a popularity-debiased test split, category coverage, and the spurious-tail rate (recommended tail items with no test interaction).

The first decisive check is the diagnostic itself. Does DP-SGD raise the tail exposure of vanilla models while lowering relevant-tail recall? If so, coverage alone is a misleading diversity metric under privacy.

The second check is the frontier. For each ε we sweep each method's own trade-off knob and compare curves of relevant-tail recall against NDCG. The proposal succeeds if our curve dominates direction subtraction and DPSGD-Global-Adapt at ε ≤ 2, where noise is largest.

The third check concerns LightGCN. Mitigating the Popularity Bias of Graph Collaborative Filtering: A Dimensional Collapse Perspective reports Recall@20 of 0.0725 versus 0.0639 for LightGCN on Yelp2018 using a LogDet regularizer that keeps embeddings from collapsing into a few dimensions. That regularizer depends only on parameters, so it adds no privacy cost. We test whether it still prevents collapse under DP noise, or whether noise artificially inflates effective rank. We measure this by comparing the singular spectrum of private embeddings against the spectrum of the pure noise matrix.