Recommendation and clinical-dosing systems decide what to show or prescribe from feature vectors with thousands of coordinates, often more coordinates than users. The few algorithms that do this under formal differential privacy, a guarantee that no single user's data noticeably changes what the system releases, all assume the reward depends on only a handful of those coordinates. Modern features such as learned embeddings rarely look like that. The signal is spread over many coordinates, but the features themselves vary mostly along a few directions. We propose a private bandit algorithm built for this second kind of structure. It spends its privacy budget only on those few dominant directions, chooses how many directions to keep based on the privacy level, and ignores the long tail of weak directions. On that tail, privacy noise would otherwise swamp the signal.
The core observation is that the standard private recipe adds noise of the same size in every direction to the feature-correlation matrix. That recipe directly destroys the property that makes high-dimensional learning without sparsity possible. Our algorithm instead keeps the noise inside a low-dimensional subspace that is itself estimated privately. Its regret should therefore depend on a privacy-dependent "effective rank" rather than on the ambient dimension or on a sparsity level.
Background and the gap
A contextual bandit sees a user's feature vector, picks an action, and observes a reward. Regret is the reward lost relative to an oracle that knows the true model. Without privacy, two routes escape the dimension. The first assumes sparsity. The $\ell_1$-confidence-ball method of Regret Lower Bound and Optimal Algorithm for High-Dimensional Contextual Linear Bandit uses Lasso estimates and $\ell_1$ confidence sets and gets logarithmic dependence on $d$. The second assumes the feature covariance has fast-decaying eigenvalues, so it has low effective rank. High-dimensional Contextual Bandit Problem without Sparsity shows that with $p > T$ and a dense parameter, minimum-norm interpolation overfits harmlessly, and an adaptive explore-then-commit scheme (AEtC) tracks the spectrum online. That paper motivates our setting.
The private literature has followed only the sparsity route. Differentially Private Contextual Linear Bandits introduces joint differential privacy (JDP). Under JDP, a user's own recommendation may depend on their own data but must hide everyone else's. The paper proves standard DP forces linear regret, and its tree-mechanism LinUCB releases noisy Gram matrices with Wishart or Gaussian noise at a cost of $d^{3/4}$. FLIPHAT reaches $\tilde O(s^*\sqrt{T}\log d)$ under JDP using noisy iterative hard thresholding and episodic forgetting, tested to $d = 4000$. By construction, FLIPHAT zeroes all but $s^*$ coordinates, so it truncates dense signal.
The research file's Gap 3 states the mechanism of failure directly. Isotropic noise $\sigma^2 I$ added to the Gram matrix inflates exactly the tail eigenvalues whose behaviour governs benign overfitting. To our knowledge from the file, no private high-dimensional bandit operates under spectral decay without sparsity. That is the gap we target.
Two other lines constrain the design. Local privacy, where users perturb data on-device, hits a $T^{3/4}$ floor for squared-error confidence bounds, an $\Omega(T^{2/3})$ floor for input perturbation, and $2^d$ scaling in the only $\sqrt T$ method, LPLR (On the Optimal Regret of Locally Private Linear Contextual Bandit). We therefore work under JDP with a trusted learner and leave local privacy out of scope. Separately, Optimal Regret of Bandits under Differential Privacy shows forgetting is unnecessary in private multi-armed bandits. This tells us not to inherit FLIPHAT's data-discarding.
Core Claim
Under JDP with dense parameters and decaying feature spectrum, the right private estimator is principal-component regression. It has three parts:
- A private estimate of the top-$k$ eigenspace of the context covariance.
- Noisy sufficient statistics released only inside that $k$-dimensional subspace.
- An adaptively chosen $k$ that shrinks as privacy tightens.
The method needs no sparsity. It should beat isotropic-noise ridge methods because it never pays variance in the many tail directions. Within an epoch of $n$ samples, $k$ is chosen to balance three terms:
$$\hat k = \arg\min_k \; \hat B(k) + c_1\frac{k}{n} + c_2\frac{k^2}{(n\epsilon)^2}.$$
In this expression, $\hat B(k)$ is a privately estimated tail bias (the residual signal outside the top $k$ directions), $k/n$ is ordinary least-squares variance in $k$ dimensions, and $k^2/(n\epsilon)^2$ is the squared Frobenius size of Gaussian-mechanism noise of scale $1/(n\epsilon)$ on a $k\times k$ system, where $\epsilon$ is the privacy level. The ambient dimension $d$ enters only through private eigenspace estimation. There, Gaussian noise of scale $1/(n\epsilon)$ on a $d\times d$ symmetric matrix has operator norm of order $\sqrt d/(n\epsilon)$, so the head is recoverable once the $k$-th eigengap exceeds that level. We conjecture regret of order $\sqrt T$ times a quantity governed by $k_\epsilon$, the number of eigenvalues above this threshold, and we will try to prove a matching lower bound in the explore-then-commit class.
Research Program
Algorithm. We build it on AEtC's epoch structure. Batching is a limitation for non-private benign overfitting, since an anytime version is listed as open. Under privacy, batching becomes an asset. Each user's data enters only $O(\log T)$ releases across geometric epochs. This gives composition cost logarithmic in $T$ without a tree mechanism, and every epoch's release uses all past data, so nothing is forgotten.
Each epoch runs four steps:
- Release a noisy context covariance and compute its top eigenvectors.
- Project and release a noisy $k\times k$ Gram matrix and $k$-vector.
- Release a few noisy scalar residuals to estimate $\hat B(k)$ over a grid of $k$.
- Commit to the resulting estimator.
Actions for user $t$ use only $t$'s own context together with the released quantities, which satisfies JDP.
Theory. We will prove a JDP guarantee via composition across epochs. We will then prove a regret bound combining three ingredients: Davis–Kahan-type subspace perturbation under the privacy noise, the bias–variance split above, and AEtC's exploration analysis. We will also prove a lower bound separating isotropic-noise ridge from our estimator on a family with high tail effective rank. The intuition for that separation is as follows. Ridge leaves residual noise in every tail direction, and those directions' prediction error sums to roughly the tail trace times $\sigma^2/\lambda^2$. Principal-component regression pays nothing there.
Baselines
Reference points. The do-nothing reference is uniform random action selection. The non-private ceiling is AEtC from High-dimensional Contextual Bandit Problem without Sparsity at $\epsilon=\infty$, which shows how much of the gap privacy costs.
Strongest private competitor on sparse problems. This is FLIPHAT (FLIPHAT), run with its published episode schedule. Its sparsity level will be tuned over the same grid size as our $k$. The file reports only qualitative results for it: regret grows linearly in $\log d$ on synthetic data with $d\le 4000$ and $s^*\in\{5,10\}$. No reported numerical regret value was found on Lacuna for FLIPHAT, so we will rerun it ourselves.
Strongest competitor on dense problems. We expect this to be a private ridge explore-then-commit. It releases the full $d\times d$ Gram matrix and $d$-vector with Gaussian noise, in the style of Differentially Private Contextual Linear Bandits, and uses the identical epoch and privacy accounting as our method. Its ridge parameter will be tuned on the same grid and validation budget as our $k$. We also run tree-mechanism JDP LinUCB as published.
Ablations isolating the key ingredient. The first fixes $k$ instead of adapting it to $\epsilon$. The second replaces private PCA with a data-oblivious random projection to $m$ dimensions, with $m$ tuned.
All methods share data streams, seeds, total privacy budget, and wall-clock caps. We count a method as beaten if our cumulative regret is lower with non-overlapping 95% intervals across 20 seeds at $\epsilon\in\{0.5,1,2\}$ on the benign-spectrum problems.
Why not just…?
Why not just run FLIPHAT with a larger sparsity level? Hard thresholding keeps the $s$ largest coordinates. When signal is spread evenly across hundreds of coordinates, any small $s$ discards most of it, and a large $s$ makes its privacy noise scale with $s$. In the non-private setting, High-dimensional Contextual Bandit Problem without Sparsity already found AEtC significantly outperformed Lasso-based methods on its benign-decay processes. We will test whether this persists privately by sweeping FLIPHAT's $s$.
Why not just use private ridge with a well-tuned penalty? This is the real threat. A ridge penalty set near the noise level acts like a soft spectral cutoff. Our argument is that ridge still pays noise in every tail direction, while projection pays none. Whether this matters depends on how heavy the tail is, so the dense-tail synthetic processes are designed to separate the two. If tuned ridge matches us across them, the contribution reduces to the analysis and the adaptive choice of $k$, and we will say so.
Why not just project onto a random subspace, which needs no privacy budget at all? Random projections are free privacy-wise but blind to the spectrum. They need many more dimensions than $k_\epsilon$ to capture the head, and each extra dimension costs privacy noise in the regression step. Matched-budget comparisons in the ablation decide whether spending budget on private PCA pays off. If it does not at small $\epsilon$, we will adopt projection in that regime.
Why not just screen features first and then run a low-dimensional private bandit? Feature Priming in Online Linear Regression proves that such two-stage screening rules cannot reach sparse rates, because irrelevant features cheaply interpolate past labels. Screening also presumes the sparsity we reject. We will include correlation screening as a cheap baseline.
Why not just rely on Thompson sampling's built-in privacy? On The Differential Privacy of Thompson Sampling With Gaussian Prior proves this only for context-free arms. Per-round sampling accumulates privacy loss, which is why Connecting Thompson Sampling and UCB needed sampling budgets. Linear Thompson sampling also scales as $d^{3/2}$ (Doubly Robust Thompson Sampling with Linear Payoffs).
Proposed Experiments
Synthetic. We reproduce the four data-generating processes of High-dimensional Contextual Bandit Problem without Sparsity with $p>T$. Processes 1 and 3 have polynomial decay and process 2 has exponential decay. Process 4 has a flat covariance and serves as the planned negative control: our method should lose its advantage there, and we will report this. We also run FLIPHAT's sparse setting with isotropic covariance up to $d=4000$, which is again expected to favour FLIPHAT. We report regret against $T$, $p$, and $\epsilon$, and plot regret against our estimated $k_\epsilon$ to test whether it, rather than $p$, predicts regret.
Real data. We use three sources:
- Warfarin dosing, with 5,528 patients, measured by misclassification rate. Regret Lower Bound and Optimal Algorithm for High-Dimensional Contextual Linear Bandit reports only that its method beat the doctor's policy, with no number found on Lacuna.
- High-dimensional OpenML tasks from A Contextual Bandit Bake-off, whose Greedy and RegCB-opt we include non-privately for reference.
- Contexts built from frozen Qwen2.5-7B-Instruct MLP activations as in Feature Priming, which are dense and likely spectrally decaying.
Decisive checks. Three results would settle the main claims. First, on the benign-decay processes at $\epsilon\le 2$, our method must beat tuned private ridge. Second, regret must track $k_\epsilon$ rather than $p$ as $p$ grows with the spectrum fixed. Third, the adaptive-$k$ ablation must show the chosen $k$ falling as $\epsilon$ shrinks with lower regret than any fixed $k$. Failure of the first check would mean the spectral shaping adds nothing over a well-tuned ridge.
References
- Regret Lower Bound and Optimal Algorithm for High-Dimensional Contextual Linear Bandit
- High-dimensional Contextual Bandit Problem without Sparsity
- Differentially Private Contextual Linear Bandits
- FLIPHAT: Joint Differential Privacy for High Dimensional Linear Bandits
- On the Optimal Regret of Locally Private Linear Contextual Bandit
- Optimal Regret of Bandits under Differential Privacy
- On The Differential Privacy of Thompson Sampling With Gaussian Prior
- Connecting Thompson Sampling and UCB: Towards More Efficient Trade-offs Between Privacy and Regret
- Doubly Robust Thompson Sampling with Linear Payoffs
- A Contextual Bandit Bake-off