Many recommender and sensing systems recover a large matrix (for example, users by items) from a few observed entries by assuming the matrix is low-rank, meaning it can be written as the product of two thin factor matrices $U V^T$. Methods that also guarantee differential privacy, a formal promise that no single user's data noticeably changes the output, have so far assumed that the analyst knows the true rank and sets the factor width exactly to it. In practice the rank is unknown, and guessing it on private data spends privacy budget. The safe choice is to over-parameterize, picking a width $k$ well above the true rank $r$. That choice causes a known problem. With extra width, plain gradient descent slows from linear to sublinear convergence, because the unneeded directions lose their gradient signal. Under privacy the slowdown is worse: noise must be added at every step, so more steps mean more noise.
We propose a privately trained version of preconditioned gradient descent, a method that rescales each update by the inverse of the factor's damped Gram matrix $(X^T X + \eta I)^{-1}$ so that flat directions still move. The claim is that one design choice makes privacy and preconditioning compatible. The gradient is clipped and noised first, and the result is then preconditioned using only quantities that are already private or public, so preconditioning costs no extra privacy. The damping $\eta$ is decayed geometrically but never allowed below a floor tied to the privacy noise scale. Without the floor, the preconditioner divides injected noise by near-zero eigenvalues in the unneeded directions and blows it up. With it, we expect accuracy and convergence speed that stay essentially flat as $k$ grows from $r$ to many times $r$, matching the private method that is told the exact rank.
Where this sits
The method comes from the non-private over-parameterization literature. Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization shows that the damped preconditioner restores linear convergence when $k>r$, with damping that shrinks as the error shrinks. It also shows that undamped scaling, ScaledGD from The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing, can blow up near singular points. Fast and Accurate Estimation of Low-Rank Matrices from Noisy Measurements via Preconditioned Non-Convex Gradient Descent replaces the error-tied damping with a geometric schedule $\eta_{t+1}=\beta\eta_t$ and reaches minimax error under observation noise. We reuse both mechanisms. Our departure is that their noise is fixed observation noise. Ours is injected into every update, so the damping must stop decaying at a level set by that injected noise.
The direct gap is Differentially Private Matrix Completion through Low-rank Matrix Factorization (DPLMC). DPLMC trains private factorized completion under joint differential privacy, a setting where each user keeps a personal embedding and only the server's item factor $V$ must be private. It uses row clipping, Gaussian noise, and a private SVD (singular value decomposition) initialization, and it proves linear convergence with $O(r^2 m)$ samples, where $m$ is the number of users. It assumes $k=r$ in both theory and experiments ($r=5$) and uses no preconditioning. We keep its privacy architecture, initialization and benchmark, and change the update rule and the rank regime.
Two other papers are adjacent but differ in what they do. Differentially Private Federated Low Rank Adaptation Beyond Fixed-Matrix (FedASK) shows that noising both factors of a low-rank adapter multiplies noise terms. It avoids this with randomized sketching rather than through optimization geometry, and it treats rank as fixed. Adaptive Clipping for Differential Private Federated Learning in Interpolation Regimes shrinks one scalar clipping radius as gradients vanish. We argue that a single scalar cannot fix gradients that vanish in some directions but not others.
Parameters or Privacy: A Provable Tradeoff Between Overparameterization and Membership Inference shows that extra parameters, and even ridge regularization, raise membership-inference leakage in linear regression. Membership inference is an attack that guesses whether a record was in the training data. This paper constrains our evaluation more than our method. Formal privacy bounds the leakage regardless, but it motivates checking empirically whether extra width and damping change measured attack success at fixed $\epsilon$.
Core Claim
The server updates the item factor with
$$V_{t+1} = V_t - \alpha\,\big(\textstyle\sum_i \mathrm{clip}_C(g_i) + \xi_t\big)\,\big(\widetilde{G}_t + \eta_t I\big)^{-1}, \qquad \eta_t=\max(\beta^t\eta_0,\ \eta_{\min}).$$
The symbols are as follows:
- $g_i$ is user $i$'s contribution to the gradient with respect to $V$.
- $\mathrm{clip}_C$ rescales that contribution to norm at most $C$.
- $\xi_t$ is Gaussian noise calibrated by Rényi differential privacy accounting.
- $\widetilde{G}_t$ is a privatized estimate of the $k\times k$ user Gram matrix $U^T U$, released with a small slice of the budget. This is cheap because only $k^2$ numbers are released.
- $\alpha$ is the step size, $\beta<1$ is the decay factor, and $\eta_{\min}$ is the damping floor.
Users update their own embeddings locally, preconditioning by $(V^T V+\eta_t I)^{-1}$, which is computed from the already-released $V$. All preconditioning is therefore post-processing and adds no privacy cost beyond the Gram release.
The floor follows from a one-line argument. Along an unneeded direction, the Gram eigenvalue is near zero, so the noise step is amplified by about $1/\eta$. Along a signal direction, the amplification is about $1/(s_r^2+\eta)$, where $s_r$ is the smallest true singular value. The floor must be large enough that the amplified noise in unneeded directions stays below the residual error in signal directions. The floor must also exceed the spectral error of $\widetilde{G}_t$ so that the damped matrix stays positive definite. This gives $\eta_{\min}$ proportional to the per-step noise standard deviation times $\sqrt{k}$. The $\sqrt{k}$ comes from the norm of a $k$-column Gaussian matrix. With this floor, $\eta$ does double duty: it stabilizes the preconditioner and absorbs noise in the released Gram matrix.
The prediction has two parts. Error decays linearly to a privacy-limited plateau whose height grows at most mildly with $k$. Unpreconditioned private descent instead stalls at a worse error for the same number of steps and the same $\epsilon$, by an amount that grows with $k$.
Research Program
The analysis extends the DPLMC proof to $k>r$ under the uniform-sampling and incoherence assumptions DPLMC already uses. The aim is a per-step contraction in the signal subspace together with a bound showing that the energy in unneeded directions saturates at roughly the noise level divided by $\eta_{\min}$. Beyond the proof, three empirical questions matter.
The first is noise placement. The alternatives to our clip-noise-then-precondition order are to precondition each user's gradient before clipping, or to precondition with the un-noised Gram matrix while paying its privacy cost separately. Gap 2 of the research file argues that preconditioning before clipping makes the clipping bound depend on how ill-conditioned the factor is. We test this directly.
The second is the floor. We compare floored geometric damping against error-tied damping (with the error estimated privately), against pure geometric decay to zero, and against fixed damping.
The third is the approximately low-rank regime. Here the target matrix has a decaying spectrum rather than an exact rank, and "the right $k$" is ill-defined. This is where we expect over-parameterization with preconditioning to beat any rank-selection scheme.
Baselines
The naive reference is DPLMC run unchanged at over-specified width $k\in\{2r,4r,10r,20r\}$. This is what a practitioner gets by guessing large. The oracle is DPLMC at $k=r$. It is the strongest existing private method and is the target to match, not beat. It is also the strongest competitor because its sample complexity is already optimal. Its paper compares it to DPALS, a private alternating least squares method, and reports lower relative Frobenius error at every $\epsilon$ (Figure 2). That comparison is only plotted, so there is no reported result found on Lacuna for a scalar DPLMC error value. We will reproduce DPLMC on its own synthetic setup and use our reproduced numbers.
The most dangerous practical baseline is private rank selection: threshold the singular values from DPLMC's private SVD initialization, then run DPLMC at the estimated rank. We give it the same total $\epsilon$, so any budget it spends on selection comes out of training. We also run private gradient descent with small random initialization following Convergence of Gradient Descent with Small Initialization for Unregularized Matrix Completion, and DPLMC with adaptive clipping as in AdaptDP-FedAvg. The ablations are our method without the floor, with preconditioning before clipping, and with a non-private Gram matrix. Non-private preconditioned gradient descent serves as a utility ceiling.
All methods use the same data, the same total $(\epsilon,\delta)$ including the Gram release, the same number of iterations, and the same hyperparameter grid size. Tuning is reported both non-privately (an upper bound for every method) and with tuning cost charged to the budget. Beating the field means two things. First, at every $k\ge 2r$, error is within a small margin of oracle DPLMC and clearly below DPLMC at the same $k$. Second, on approximately low-rank matrices, error is below rank-selection plus DPLMC.
Why not just…?
Why not just estimate the rank privately and run DPLMC at that rank? This is the real threat. When the spectrum has a clean gap and many users, the private SVD may reveal $r$ almost for free, and our method then offers little. We expect it to fail in two places. With few users or small $\epsilon$, the noisy singular values blur the gap. With decaying spectra, no single cutoff is right: cutting too low discards signal, and cutting too high brings back the slowdown. The experiments sweep the spectral gap and the user count so that the region where rank selection suffices is mapped explicitly rather than argued away.
Why not just use small initialization, which already ignores extra width? Its guarantee relies on unneeded directions staying near zero while signal directions grow. Per-step Gaussian noise pushes all directions off zero from the first iteration. Its proof also needs $\Omega(dr^9)$ samples, compared with DPLMC's $O(r^2 m)$. We include it as a baseline and track the energy in unneeded directions over iterations to see whether noise destroys the separation it depends on.
Why not just use adaptive clipping? Shrinking a single clipping radius lowers noise uniformly. Over-parameterized factorization, however, has gradients that vanish only in the unneeded directions, as Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization shows. Adaptive clipping should therefore improve the plateau but not the sublinear rate. The convergence curves of DPLMC with adaptive clipping at large $k$ will test this.
Why not just solve the convex nuclear-norm problem privately? Convex relaxation avoids rank choice entirely. As DPLMC's comparison summarizes, however, private convex and Frank–Wolfe methods need $O(r^6 m)$ samples and converge sublinearly, and they must store the full matrix. We cite this rather than rerun it, except on the smallest synthetic size.
Proposed Experiments
Experiment 1, DPLMC's synthetic benchmark. This uses $n=100$ items, $m\in[5000,15000]$ users, observation noise $\nu=1$, and true rank $r=5$. We extend it to widths up to $k=100$ and to decaying spectra. The metric is relative Frobenius error $\|\hat M-M^\star\|_F/\|M^\star\|_F$ against $\epsilon$ and iteration count.
Experiment 2, extreme over-parameterization. We adopt the $100\times100$, rank-3 setup of Convergence of Gradient Descent with Small Initialization for Unregularized Matrix Completion, with search rank from 10 to 100, and add privacy.
Experiment 3, real data. On MovieLens-100K and MovieLens-1M, using the loaders in newlei/FDA, we report held-out RMSE against $\epsilon$ and $k$. The file lists no reported MovieLens numbers, so all comparisons there are internal.
Membership-inference audit. For non-private and private variants, we run a loss-threshold attack on held-out versus training entries as $k$ and $\eta_{\min}$ vary. This tests whether the regularization paradox of Parameters or Privacy carries over to factorization, where damping plays the role of ridge.
Decisive checks. The proposal fails if any of the following holds. Error at $k=20r$ is not close to oracle DPLMC at fixed $\epsilon$. Removing the floor does not cause measurable noise blow-up in unneeded directions. Rank-selection plus DPLMC matches us on decaying spectra.
References
- Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization
- The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing
- Fast and Accurate Estimation of Low-Rank Matrices from Noisy Measurements via Preconditioned Non-Convex Gradient Descent
- Differentially Private Matrix Completion through Low-rank Matrix Factorization
- Differentially Private Federated Low Rank Adaptation Beyond Fixed-Matrix
- Adaptive Clipping for Differential Private Federated Learning in Interpolation Regimes
- Parameters or Privacy: A Provable Tradeoff Between Overparameterization and Membership Inference
- Convergence of Gradient Descent with Small Initialization for Unregularized Matrix Completion