When people give feedback ("I prefer answer A over answer B"), their tastes change over time, and a system that learns from that feedback has to forget old judgments at roughly the rate tastes change. Today, the methods that handle this drift reweight the entire stored history of comparisons, and the methods that protect individual comparisons with differential privacy (a formal guarantee that no single person's answer noticeably changes what the system releases) assume tastes never change. We propose a small estimator that does both. It keeps a fixed-size memory, independent of how long the stream runs. It discounts old comparisons exponentially. It publishes an updated preference model after every new comparison, and the whole published sequence carries a privacy guarantee.
The core idea is simple. With frozen features, a discounted linear-loss learner's model is a decayed running sum of gradients. Releasing that sum privately at every step is a "continual counting" problem with exponentially decaying weights. The standard way to add privacy noise to such a sum is a correlated-noise construction, which normally needs memory that grows with stream length. We replace it with a handful of recursive noise filters that use constant memory. The intended outcome is error that grows only logarithmically with the effective window. The obvious alternative, adding fresh independent noise every step, has error that grows like the square root of that window. That difference decides how fast a private system can afford to forget.
Core Claim
The research file frames naive exponential decay of a private sketch as causing a "noise explosion." That framing is not quite right. If each incoming statistic $z_t$ gets independent Gaussian noise of scale $\sigma$ and the running sum is multiplied by $\gamma$ each step, the accumulated noise variance is bounded by $\sigma^2/(1-\gamma^2)$. Privacy holds, because every comparison touches exactly one noise draw. The real cost is the rate. The decayed sum
$$S_t=\sum_{i\le t}\gamma^{\,t-i} z_i$$
has signal of size about $n_{\text{eff}}=1/(1-\gamma)$ and noise of size about $\sigma\sqrt{n_{\text{eff}}}$. Its relative error therefore shrinks only like $1/\sqrt{n_{\text{eff}}}$, the rate of noising each sample. The central-model rate of Differentially Private Reward Estimation with Preference Feedback, $\Theta(\sqrt d/(\epsilon n))$, shrinks like $1/n$.
Drift caps how large $n_{\text{eff}}$ can usefully be. The privacy noise rate therefore directly sets the best achievable tradeoff between staleness and noise. A noisier mechanism forces a longer window, and a longer window means slower recovery after a preference shift.
We claim the following. Releasing $S_t$ through a factorization mechanism, written as $A = LR$ where $A$ is the lower-triangular matrix with entries $\gamma^{t-i}$, attains error that scales roughly like $\sigma\log n_{\text{eff}}$ rather than $\sigma\sqrt{n_{\text{eff}}}$. This is an expectation by analogy with the logarithmic error of square-root factorizations for plain counting, and the project must establish it. A factorization mechanism adds noise $LRz$-style correlated across time instead of independently.
We further claim that the factor $L$ can be approximated by a sum of $m$ geometric filters, each maintained by a one-line recursion. Here $m$ is logarithmic in $n_{\text{eff}}$ and in the target accuracy. The total state is then $O(md)$ numbers for a $d$-dimensional model, with no dependence on stream length $T$. This combination does not exist in the file's literature: drift-aware, private under continual release, and fixed memory.
Relation to Prior Work
Three papers motivate the gap from the drift side.
- Right Now, Wrong Then: Non-Stationary Direct Preference Optimization under Preference Drift introduces NS-DPO, which discounts each comparison by $\gamma^{T-t_i-1}$ and survives preference flips that send standard DPO to near-chance accuracy. It stores all $T$ comparisons and is not private.
- PAL: Sample-Efficient Personalized Reward Modeling for Pluralistic Alignment represents each user as a small weight vector over $K$ prototypes on a frozen backbone.
- A Shared Low-Rank Adaptation Approach to Personalized RLHF gives each user a low-rank adapter.
Both personalization methods are offline, stationary and non-private. We borrow PAL's frozen-feature, low-dimensional user representation, so that the per-user state stays small enough to stream.
Two papers supply method.
- Differentially Private Reward Estimation with Preference Feedback defines label privacy for Bradley–Terry comparisons and gives minimax rates. Bradley–Terry is the model in which the chance of preferring A over B is a sigmoid of a reward difference. That paper releases a model once, from a fixed batch, under a fixed reward. We keep its privacy unit and its local and central rates as reference points.
- Improved Accuracy for Private Continual Cardinality Estimation in Fully Dynamic Streams via Matrix Factorization shows that casting a continual-release problem as a private matrix factorization improves accuracy. We apply the same lens to the decayed-sum matrix and add a memory constraint that work does not impose.
The sliding-window line both motivates and constrains the design.
- Sublinear Space Private Algorithms Under the Sliding Window Model proves that hard expiry can give summaries arbitrarily large sensitivity, and gets $\tilde O(w^{3/4}/\epsilon)$ heavy-hitter error in $\tilde O(\sqrt w)$ space.
- A Framework for Private Matrix Analysis in Sliding Window Model handles covariance matrices but carries large polynomial factors in $d$.
Exponential decay sidesteps the expiry problem entirely. Nothing is ever subtracted, so a comparison's influence on any release is bounded by its weight. This is why we choose decay over windows, and why we track a $d$-vector rather than a $d\times d$ covariance.
Finally, Keeping a Secret Requires a Good Memory: Unconditional Streaming Lower-Bounds for Differentially Private Algorithms shows that protecting a whole user history in a stream forces substantial memory. We therefore target privacy of each individual comparison and state plainly that per-user guarantees over unbounded histories are out of scope.
Continual Learning with Differential Privacy is a cautionary data point. Its noisy replay loses heavily on Permuted MNIST, and its memory grows with the number of tasks. Our design keeps no replay buffer at all.
Research Program
The learner. Fix a frozen encoder (as in PAL), so that each comparison becomes a feature difference $\Delta x_t\in\mathbb R^d$ with bounded norm and a binary label $y_t$. The learner is discounted follow-the-regularized-leader on linearized logistic losses. Concretely, $\theta_t = -\eta\, \tilde S_t$, where $\tilde S_t$ is the privately released decayed sum of clipped gradients $g_i = (\sigma(\langle\theta_{i-1},\Delta x_i\rangle)-y_i)\Delta x_i$. Here $\eta$ is a step size, and $\tilde S_t$ differs from $S_t$ only in that it is released through the privacy mechanism. Because $\theta_{i-1}$ is itself a private release, the gradients are adaptively chosen. We will rely on the known validity of factorization mechanisms under adaptive inputs and verify that it covers this case.
For multi-user personalization, the same construction runs on PAL-style per-user weights $w^{(u)}\in\mathbb R^K$, with a shared, slowly decayed prototype update.
The mechanism. We first compute the optimal factorization $A=LR$ for the decay matrix numerically, at moderate $T$, as a function of $\gamma$. This gives an unrestricted-memory reference. We then fit $L$'s Toeplitz coefficients with a sum of $m$ exponentials. Each exponential is a recursive filter, so noise is generated online with $m$ state vectors, and the approximation error is folded into the privacy accounting through the actual (approximate) factorization used.
Theoretical deliverables. We will derive error as a function of $(\gamma,\epsilon,d,m)$. We will then derive the resulting dynamic-regret tradeoff under a bounded total variation of the true reward trajectory, following NS-DPO's analysis, together with a lower bound showing what independent-noise decay cannot beat.
Unknown drift rate. NS-DPO's $\gamma$ depends on an unknowable variation budget. We will test running a small grid of $\gamma$ values in parallel, which multiplies memory by the grid size. A single privately selected choice will be picked by the noisy recent prediction loss of each candidate, with the extra privacy cost accounted. This is a secondary contribution and will be reported separately so that it cannot mask the main result.
Baselines
The first reference point is a stationary private learner, the do-nothing option for drift. It is the same streaming learner with $\gamma=1$ and the same factorization noise, which amounts to private continual learning with no forgetting. Alongside it we run the central objective-perturbation estimator of Differentially Private Reward Estimation with Preference Feedback, retrained on the full accumulated log at the same release schedule, with privacy composed across releases. Under abrupt flips we expect this baseline to stall near chance, mirroring the DPO collapse reported for TV-HH. Beating it means higher post-shift accuracy at every $\epsilon$.
The strongest competitor on the actual question is independent-noise decay: the identical learner with identical clipping, $\gamma$ grid, privacy budget and memory, except that each gradient receives fresh independent Gaussian noise. It is strong because it is trivially fixed-memory and correctly private. The file's argument against it is mistaken, as explained above. We count our method as beating it only if it achieves lower tracking error at matched $\epsilon$ and matched state size, across the range of $n_{\text{eff}}$ that the best $\gamma$ actually selects on each benchmark. We also count it as beating this baseline if it reaches the same accuracy at a meaningfully smaller $\epsilon$.
The memory-unbounded private competitor stores a first-in-first-out window of the last $W$ comparisons and reruns central private estimation periodically, with composition accounted. It is tuned over $W$ and over the retraining period, using the same budget of tuning runs as our method. We report its memory honestly; beating it means matching its accuracy with orders of magnitude less state. A local-privacy variant, randomized response with the debiased loss from the same paper plus decay, is reported for deployments without a trusted curator.
For the non-private ceiling, no reported result was found on Lacuna for any private streaming preference learner on these benchmarks. The strongest cited number is non-private: on TV-HH, Right Now, Wrong Then: Non-Stationary Direct Preference Optimization under Preference Drift reports NS-DPO reward accuracy "above 60-70%" under mid-dataset flips, versus about 50–55% for standard DPO, using full fine-tuning of Llama models. Because our learner uses frozen features, we also run a non-private discounted logistic regression on the same features with full history. That is the proper ceiling, and the gap to it is the price of privacy plus memory.
Two ablations isolate the key ingredients. The first compares exact factorization noise, which needs $O(T)$ memory, with the $m$-filter approximation, which isolates what the memory restriction costs. The second compares factorization noise with independent noise at equal memory, which isolates the correlated-noise ingredient itself.
Why not just…?
Why not just decay a counter and add fresh noise each step? This is the real threat. When drift is fast and the useful $n_{\text{eff}}$ is only a few dozen, $\sqrt{n_{\text{eff}}}$ and $\log n_{\text{eff}}$ are close, and the simpler method may be just as good. Our claim is specifically that the gap opens as $n_{\text{eff}}$ grows: in slowly drifting or multi-user settings with sparse per-user feedback, and at small $\epsilon$. The experiments sweep drift speed precisely to locate this crossover. If no benchmark sits on our side of it, we will report that the simple method suffices.
Why not just keep a sliding window of raw comparisons and retrain privately? It uses $O(Wd)$ memory plus stored text. It also composes privacy over many overlapping releases, and Sublinear Space Private Algorithms Under the Sliding Window Model shows that hard expiry interacts badly with sensitivity. It is nonetheless a fair accuracy competitor when memory is free, and we include it at its best-tuned window. We expect it to lose on accuracy at fixed $\epsilon$, because composition dominates, and certainly on memory.
Why not just run NS-DPO with DP-SGD? That would require storing the full discounted history, $O(T)$, and composing privacy over repeated passes. It also differs from what we test, since it fine-tunes the whole model rather than tracking a reward on frozen features. Our frozen-feature restriction is a genuine limitation: it cannot capture drift that the encoder does not represent. We measure this through the gap to the non-private full-history ceiling.
Why not just privatize labels locally with randomized response? It removes the trusted curator, but its error carries the factor $1/(e^\epsilon-1)\sqrt{d/n}$ from Differentially Private Reward Estimation with Preference Feedback, which is far worse at small $\epsilon$. We run it as a baseline so that the cost of moving to the local trust model is visible, not argued.
Proposed Experiments
The streams are built from benchmarks with explicit drift. These are TV-HH, UltraFeedback-RM with its injected change points, and 2C NSGO, all from Right Now, Wrong Then: Non-Stationary Direct Preference Optimization under Preference Drift, each ordered by its timestamps. Comparisons are encoded with a frozen encoder through the PAL codebase (RamyaLab/pluralistic-alignment).
For personalization under drift, we use Reddit TL;DR and Pick-a-Filter. On Reddit TL;DR the reported stationary references are 74.65% for P-ShareLoRA on Llama-3 8B and PAL's 36% gain on unseen users. On Pick-a-Filter we schedule each group's color preference to switch partway through the stream, which creates controlled sudden and gradual drift per user.
The metrics are:
- accuracy over time on held-out comparisons drawn from the current-time distribution;
- recovery time, measured as the number of comparisons after a change point until accuracy returns to within a fixed margin of its pre-shift level;
- cumulative dynamic regret;
- bytes of state;
- the privacy level $\epsilon$ at a fixed $\delta$.
The decisive check is a two-dimensional sweep over drift speed and $\epsilon$, at matched state size, comparing factorization noise with independent noise. The proposal succeeds if the factorization advantage grows with the selected $n_{\text{eff}}$ in the way predicted by $\log n_{\text{eff}}$ versus $\sqrt{n_{\text{eff}}}$. It must also show that the $m$-filter approximation stays within a small fraction of the exact factorization's error, with $m$ in the single or low double digits.
A second check measures the measured noise standard deviation of the released sum against $n_{\text{eff}}$ on purely synthetic streams, against the two predicted curves. A third tests whether privately adapting $\gamma$ recovers most of the oracle-$\gamma$ accuracy on the flip benchmarks.
References
- Differentially Private Reward Estimation with Preference Feedback
- Right Now, Wrong Then: Non-Stationary Direct Preference Optimization under Preference Drift
- PAL: Sample-Efficient Personalized Reward Modeling for Pluralistic Alignment
- A Shared Low-Rank Adaptation Approach to Personalized RLHF
- Improved Accuracy for Private Continual Cardinality Estimation in Fully Dynamic Streams via Matrix Factorization
- Sublinear Space Private Algorithms Under the Sliding Window Model
- A Framework for Private Matrix Analysis in Sliding Window Model
- Keeping a Secret Requires a Good Memory: Unconditional Streaming Lower-Bounds for Differentially Private Algorithms
- Continual Learning with Differential Privacy