When a recommender system is trained with differential privacy (a guarantee that the released model barely changes if any one user's data is removed), every training step spends part of a fixed privacy budget. The budget is usually spent by adding random noise to each update. As a result, the number of optimization steps is not just a runtime cost. It is an accuracy cost, because more steps means more noise.
This matters most when the true rating matrix is ill-conditioned, meaning its strongest and weakest signal directions differ greatly in size. On such matrices, plain gradient descent on the low-rank factors needs a number of steps that grows with the square of that spread. We propose to remove this cost with a preconditioner, a rescaling of each update that equalizes progress across strong and weak directions. The preconditioner is built from an r×r summary of the user factors that can be privatized cheaply. We also damp it at the privacy noise floor, so it never amplifies noise in directions the data cannot resolve anyway.
The short version for a colleague is this. Under privacy, ill-conditioning quietly turns into lost accuracy, because slow optimization means more noisy steps. A small, privately estimated, noise-damped rescaling matrix can make the step count independent of conditioning, and it costs almost no extra privacy.
Core Claim
The low-rank factorized approach replaces expensive convex nuclear-norm solvers. The nuclear norm is the sum of singular values, and minimizing it requires a full or truncated SVD at every iteration. The factorized approach instead writes the matrix as $X = UV^\top$ with thin factors and updates the factors directly. Park et al. show this is 10x to 20x faster than SVD-based projection solvers. Lee et al. show its loss surface has no spurious local minima.
The private version by Wang, Zhao, and Kolar splits the work in two, a setting called joint differential privacy. Users solve locally for their own profile vectors $u_i$. The server updates the shared item factors $V$ by noisy projected gradient descent. This achieves linear convergence and non-private sample complexity. However, the file notes that its rate degrades with $\kappa = \sigma_1/\sigma_r$, the ratio of the largest to the r-th singular value.
Jia et al. prove that scaled gradient descent eliminates $\kappa$ from the iteration count on the fully observed, noiseless problem. That method multiplies factor gradients by inverse Gram matrices $(U^\top U)^{-1}$ and $(V^\top V)^{-1}$. They explicitly leave open both privacy and the noisy or missing-entry setting.
Our claim is that these two results fit together cleanly, but only with one specific design. In the joint-privacy architecture, $V$ is public after each round, so the user-side preconditioner $(V^\top V)^{-1}$ costs nothing. The only private quantity the server needs is the r×r user Gram matrix $\sum_i u_i u_i^\top$. The server update becomes
$$V \leftarrow V - \eta\, \widetilde{\nabla}_V \,(\widehat{G} + \lambda I)^{-1}, \qquad \widehat{G} = \sum_i \bar u_i \bar u_i^\top + Z.$$
Here $\widetilde{\nabla}_V$ is the clipped, noised item gradient as in Wang et al. The vector $\bar u_i$ is user $i$'s profile clipped to norm $C$. $Z$ is a symmetric Gaussian r×r noise matrix. $\lambda$ is a damping level set to a high-probability bound on $\|Z\|$.
We make three predictions.
First, the preconditioned method's iteration count to a fixed accuracy should be flat in $\kappa$. Noisy gradient descent's count should grow roughly as $\kappa^2$. Under Rényi privacy accounting, per-step noise at a fixed total budget scales like $\sqrt{T}/\varepsilon$ in the number of steps $T$. So the unpreconditioned method's final error should carry an extra factor of order $\kappa$.
Second, the gain should persist only while $\sigma_r(U)^2$ stays well above the Gram noise level. Below that floor, the damping makes both methods fail in the same way. This is information-theoretic, not an optimization failure.
Third, the privacy spent on $\widehat G$ is on $r(r+1)/2$ numbers, not $n$ or $d$. It should therefore be a negligible share of the budget.
The link to eigengap sensitivity is precise and is part of what is new. Private estimates of eigenvectors blow up as consecutive eigenvalues merge. This is shown by the bounds of Tran, Vu, and Vishnoi, which scale as $\lambda_p/\delta_p$, and by the eigenvalue-collision analysis of Mangoubi et al.. A Gram-matrix inverse, by contrast, is continuous in the matrix and needs no eigenvectors. Its error depends only on the smallest eigenvalue relative to the noise, never on gaps.
The preconditioner therefore avoids the eigengap trap that makes private subspace estimation hard. Eigengaps still matter in two places: choosing the rank $r$, and the private spectral initialization. We treat both explicitly below.
Research Program
The first part is analysis. We will extend the κ-independent convergence argument of Jia et al. to the setting where the item gradient and the Gram matrix are both perturbed by bounded-variance noise. We start with fully observed factorization, then move to uniformly sampled entries as in Wang et al.
The target result has two parts. It gives an iteration count of order $\log(1/\text{accuracy})$ with no $\kappa$. It also gives an error floor expressed in $\sigma_r$, the clipping level, $\varepsilon$, and $r$. We expect the damping $\lambda$ to enter as an effective condition number $\min(\kappa, \sigma_1^2/\lambda)$. We will check that expectation rather than assume it.
The second part is two design questions.
The first design question is where the Gram noise is added. The server could noise the Gram matrix once per round. Alternatively, it could maintain a slowly updated running estimate. Since user factors change little between late rounds, the running estimate reduces privacy composition.
The second design question is choosing the rank. The rank should sit where the private spectrum shows a clear gap. Singhal et al. argue that a multiplicative gap is necessary for dimension-free private estimation. Liu et al. show that sample complexity explodes without one. We will pick $r$ using a small, separately budgeted, noisy spectrum estimate from the initialization step, and report sensitivity to that choice.
The third part is implementation. We build on the Wang et al. algorithm with identical clipping and accounting, and change only the server step. The added cost is one r×r inverse per round.
Baselines
The naive reference point has two parts, and both are run at every privacy level. The first is the non-private scaled-gradient method of Jia et al., which gives the accuracy ceiling. The second is predicting each item's mean rating, which gives the floor.
The strongest direct competitor is the differentially private low-rank matrix completion method of Wang, Zhao, and Kolar. It is the only method in the file with linear convergence and non-private sample complexity under joint privacy, and it differs from ours only in the missing preconditioner. The file contains no reported numeric Frobenius error for it on its synthetic benchmark (n=100 items, r=5, 5,000 to 15,000 users, noise level 1). It reports only that it beats the earlier alternating method at every ε. So there is no reported number on Lacuna for this baseline, and we will reproduce it.
For fairness, both methods share the same initialization, clipping level, total privacy budget, and privacy accountant. Each gets the same grid-search budget over step size, clipping, and number of rounds $T$. Tuning $T$ is essential, because an untuned $T$ would unfairly handicap the baseline.
We count as beating it any statistically reliable reduction in held-out error that grows with $\kappa$. The reduction must be at least 20 percent at the largest tested $\kappa$, while matching the baseline within noise when $\kappa$ is near 1. Matching at small $\kappa$ is required. A gain there would suggest a tuning artifact rather than the claimed mechanism.
The convex-relaxation competitor is the private Frank-Wolfe method of Jain, Thakkar, and Thakurta. It avoids full SVDs by privately computing one top singular vector per iteration with Oja's method. It converges sublinearly, and its theory needs far more users than items. The file reports that its RMSE is near non-private at ε≈0.1 on Netflix and Yahoo, but gives no numeric RMSE. We run it with the same budget and item filtering on each dataset.
For older private factorization, we include Hua, Xia, and Zhong as the reference on its own Netflix subset of 100 movies. It reports a prediction-error increase of less than 0.03 over non-private when ε ≥ 0.15.
Two ablations isolate the key ingredient. The first is our method without damping ($\lambda = 0$), which tests whether noise amplification in weak directions is real. The second uses a non-private exact Gram matrix, which measures how much accuracy the privatized preconditioner gives up.
Why not just…?
Why not just run noisy gradient descent longer with a tuned step size? This is the most serious threat. At moderate $\kappa$, careful tuning of $T$ may already absorb most of the gap. Our composition argument says that more steps at a fixed budget means proportionally larger per-step noise, so tuning cannot remove a $\kappa^2$ step requirement. That is an argument, though, not evidence. The κ-sweep experiment settles it directly. If tuned noisy gradient descent tracks our method as $\kappa$ grows, the core claim is false and we will report it as such.
Why not just truncate to a smaller, well-conditioned rank? Keeping only the top block of singular values is the hard-threshold cousin of the deflation idea of Hardt and Wootters. It shrinks $\kappa$ by fiat and also reduces privacy noise, which scales with dimension. The cost is that it discards weaker directions that are still above the noise floor. Our damping is the soft version: it keeps any direction the data can resolve. We run hard truncation at every candidate rank as a baseline. We concede the point if the best truncation matches damping on real data.
Why not just take one private SVD of the observed matrix and skip iteration altogether? A single noisy SVD pays privacy only once. For fully observed covariance matrices, Tran, Vu, and Vishnoi give tight error bounds for it. Those bounds scale with $\lambda_p/\delta_p$ and diverge as eigengaps close. With missing entries, the zero-filled SVD is also biased. We include the one-shot private SVD, which we also use as our initialization, to show how much the iterative phase adds. We expect the gap between the two to be largest on matrices with small eigengaps.
Why not just use the convex nuclear-norm route, which has no factor conditioning? The private Frank-Wolfe method avoids factor-scale ill-conditioning. However, it converges sublinearly and needs far more users than items, so every extra iteration costs privacy. It is a direct baseline, and the experiments report its accuracy at matched budget.
Proposed Experiments
The decisive synthetic experiment reuses the Wang et al. generator (n=100, r=5, 5,000 to 15,000 users, noise 1). We plant singular values so that $\kappa$ ranges from 1 to 1000, and set ε from 0.1 to 8.
For each method, we record rounds to convergence and final Frobenius error $\|UV^\top - M\|_F$ as functions of $\kappa$. The predicted signature has two parts. The first is a flat iteration curve for our method against a roughly quadratic one for tuned noisy gradient descent. The second is a divergence in error that stops once $\sigma_r^2$ falls below the Gram noise level.
A second synthetic sweep holds $\kappa$ fixed and shrinks the gap between $\sigma_r$ and $\sigma_{r+1}$. Our analysis predicts two outcomes. The preconditioned update itself should be insensitive to the gap. Initialization and rank selection should degrade as the gap closes, following the Tran et al. scaling.
On real data, we evaluate held-out RMSE against ε per user on MovieLens 100k, MovieLens 10M, Jester, and the Netflix Prize data. We use both the popular-item filtering of Jain et al. and an unfiltered long-tail setting. We also estimate each dataset's empirical $\kappa$ at the chosen rank. The prediction is that gains correlate with it.
Because the file reports throughput but no private accuracy numbers for Liu et al., we report wall-clock time alongside accuracy. That paper's Langevin-sampling approach is also sensitive to ill-conditioning. For the non-private runtime anchor on MovieLens 100k, Park et al. report 72.2% one-bit prediction accuracy in 25.4 seconds for their factorized method, against 42.3 seconds for the convex solver TFOCS. We reproduce the one-bit task to check that preconditioning keeps the factorized method's speed advantage.
The idea fails cleanly under two findings. The first is that tuned noisy gradient descent matches us across $\kappa$. The second is that the undamped and damped variants perform identically, which would mean the noise-floor reasoning is irrelevant.
References
- Finding Low-rank Solutions to Matrix Problems, Efficiently and Provably
- Matrix Completion has No Spurious Local Minimum
- Differentially Private Matrix Completion through Low-rank Matrix Factorization
- Preconditioning Matters: Fast Global Convergence of Non-convex Matrix Factorization via Scaled Gradient Descent
- Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy
- Re-Analyze Gauss: Bounds for Private Matrix Approximation via Dyson Brownian Motion
- Privately Learning Subspaces
- DP-PCA: Statistically Optimal and Differentially Private PCA
- Differentially Private Matrix Completion Revisited
- Differentially Private Matrix Factorization
- Fast matrix completion without the condition number
- Fast Differentially Private Matrix Factorization