When a recommender system fills in a ratings matrix, deleting one observed rating should barely change its predictions. The standard way to test this, average sensitivity, removes one observed entry chosen uniformly at random and measures how much the output moves. Average sensitivity is simply the expected change in an algorithm's output when one input element is removed at random. That test quietly assumes every observation is equally typical. Real rating matrices are sampled very unevenly: popular items and active users account for most observed entries. A uniform draw over observed entries is therefore almost always a draw from a dense hub, where one deletion does nothing. Entries from sparse, long-tail rows are rarely drawn. Yet those are exactly the entries whose removal can swing a user's entire predicted profile. Low average sensitivity can coexist with severe instability for the users who have the least data.
This note proposes to measure, bound, and reduce that hidden instability. We treat the uniform-deletion average as an instance of the same uniform-sampling assumption that matrix completion theory has spent a decade removing. The claim has three parts. The usual average sensitivity of low-rank completion stays nearly flat as sampling becomes more skewed. A row-balanced version, which weights each user equally rather than each rating, grows sharply with skew. The smoothed reweighting schemes already used to fix accuracy under non-uniform sampling also act as stability filters for the tail, and they do so at a better accuracy/stability trade-off than simply regularizing harder.
Core Claim
Let $\mathcal{A}$ be a completion algorithm mapping an observed index set $\Omega$ (with values) to an estimate $\hat M$. Let $\Omega_i$ denote the observed entries in row $i$ of a $d_1 \times d_2$ matrix. We compare two quantities. The first is the standard average sensitivity. The second is the row-balanced sensitivity, which first averages within a row and then averages over rows:
$$ S_{\text{unif}} = \mathbb{E}_{e \sim \mathrm{Unif}(\Omega)} \big\| \mathcal{A}(\Omega) - \mathcal{A}(\Omega\setminus\{e\}) \big\|_F, \qquad S_{\text{row}} = \frac{1}{d_1}\sum_{i} \mathbb{E}_{e \sim \mathrm{Unif}(\Omega_i)} \big\| \mathcal{A}(\Omega) - \mathcal{A}(\Omega\setminus\{e\}) \big\|_F . $$
The standard metric follows the discrete definitions of Average Sensitivity of Graph Algorithms, which average over uniformly random edge deletions. We will also report the row-restricted change $\|\hat M_{i\cdot} - \hat M^{(-e)}_{i\cdot}\|$, because a user's own predictions are what the user experiences.
Our conjecture has a simple heuristic basis. For spectral and projected-gradient estimators, the influence of entry $(i,j)$ on row $i$'s estimated factor scales roughly like the inverse of that row's observation count. This is the familiar leave-one-out picture in which each entry is one of $|\Omega_i|$ equations determining row $i$'s factor. Under a rank-one sampling profile $P = uv^\top$ with heavy-tailed $u$, the two metrics then behave differently. $S_{\text{unif}}$ is a frequency-weighted average of these influences and stays near $O(1/\text{typical degree})$. $S_{\text{row}}$ is governed by the low-degree tail. The gap between them should widen as the tail grows heavier.
We also claim that the smoothed empirical weighting of Learning with the weighted trace-norm under arbitrary sampling distributions reduces $S_{\text{row}}$ in a controllable way. That method mixes observed row and column frequencies with a uniform distribution through a parameter $\alpha$. Its role here mirrors the coreset "stability filter" of Average Sensitivity of Euclidean k-Clustering: in both, importance weighting stops a single element from dominating a rarely-represented part of the input.
Relation to Prior Work
The sensitivity literature supplies both the definitions and the stabilizing mechanisms. Average Sensitivity of Graph Algorithms shows that algorithms making local decisions have low average sensitivity. Average Sensitivity of Spectral Clustering shows that spectral partitions are stable under random edge removal when the Laplacian eigengap is large. Average Sensitivity of Euclidean k-Clustering shows that coresets built by importance sampling make any clustering routine stable on average. All three average over deletions that are uniform over input elements, and none studies inputs whose elements come from a skewed observation process. This proposal questions that averaging choice rather than reusing it.
The non-uniform completion literature motivates the problem and supplies the estimators. Learning with the weighted trace-norm under arbitrary sampling distributions, Weighted matrix completion from non-random, non-uniform sampling patterns, and Universal Matrix Completion show how reweighting or a well-connected, expander-like observation pattern restores accurate recovery without uniform sampling. Entry-Specific Bounds for Low-Rank Matrix Completion under Highly Non-Uniform Sampling shows that completing a local submatrix per entry (SVT-sub) beats whole-matrix thresholding. All of these measure error against ground truth, and none measures how estimates move when data are removed.
The closest technical relative is Leave-One-Out Approach for Matrix Completion: Primal and Dual Analysis. It already constructs leave-one-entry-out and leave-one-row-out iterate sequences for gradient descent with projection and for nuclear-norm minimization, and bounds their distance to the true iterates. It does so only as a proof device under uniform Bernoulli sampling. We reuse its machinery as the method for our bounds, with per-entry probabilities $p_{ij}$, and turn its intermediate perturbation bounds into the object of study.
Truncated Matrix Completion - An Empirical Study constrains the design. Under value-dependent missingness, convex solvers fail while the non-convex solver GNMR recovers. Any stability claim must therefore be checked separately for non-convex solvers and must not assume the convex picture transfers.
Research Program
The theoretical part targets two estimators whose leave-one-out analysis is tractable. The first is the debiased rank-one-weighted projection of Weighted matrix completion from non-random, non-uniform sampling patterns. The second is gradient descent with projection, analyzed with the Leave-One-Out Approach for Matrix Completion: Primal and Dual Analysis machinery. Both are studied under rank-one probability masks. We aim to prove a per-entry influence bound that scales with the inverse row and column observation counts. From it we will derive matching upper bounds on $S_{\text{unif}}$ and lower bounds on $S_{\text{row}}$ as functions of the tail of $u$. The same bound will be applied to the smoothed-weighted objective, with $\alpha$ as the smoothing parameter.
We do not expect the $\kappa^6 r^6$ dependence of the existing gradient-descent analysis to survive with good constants. The target is the correct dependence on degree skew, not tight polynomial factors. As a side question, following the spectral-gap view in Universal Matrix Completion, we ask whether deleting an entry from a low-degree node lowers the observation graph's spectral gap more than deleting a hub entry. Comparing spectral gap before and after deletion is a cheap diagnostic that could predict which entries are fragile.
The computational part builds a measurement harness. For a sample of deletions it computes sensitivity exactly by warm-started refitting, and it checks a first-order influence approximation against those exact refits. The harness stratifies deletions by row degree so that both metrics, and the full degree-to-sensitivity curve, come from the same runs.
Baselines
The naive reference point is the unweighted trace-norm estimator, alongside SVT-whole, the whole-matrix singular value thresholding compared against in Entry-Specific Bounds for Low-Rank Matrix Completion under Highly Non-Uniform Sampling. Each is tuned for held-out error only, with no concern for stability. It represents what practitioners deploy, and it is the estimator we predict to have the largest gap between $S_{\text{unif}}$ and $S_{\text{row}}$.
The strongest existing method is smoothed weighted trace-norm from Learning with the weighted trace-norm under arbitrary sampling distributions. It reports a Netflix qualification RMSE of 0.9096 at $\alpha = 0.9$, beating unweighted trace-norm and max-norm regularization. Our first sanity check is to reproduce a number in that range on Netflix before any sensitivity measurement. On MovieLens 10M the file gives no RMSE for this method: no reported result found on Lacuna for smoothed weighted trace-norm RMSE on ML-10M. We will therefore report our own reproduction there. It is the strongest competitor because it is already the accuracy-optimal answer to skewed sampling. If it is also already stable on the tail, our stabilization story reduces to a measurement contribution.
For the local alternative we use SVT-sub from Entry-Specific Bounds for Low-Rank Matrix Completion under Highly Non-Uniform Sampling. It reports average relative improvements over SVT-whole of 12.7%, 21.3%, and 14.5% on the top-left, off-diagonal, and bottom-right blocks of block-constant masks, and 17.7% on rank-one masks. We test whether its locality buys tail stability in the way the locality principle of Average Sensitivity of Graph Algorithms predicts.
For value-dependent missingness we use GNMR and R2RILS, run as in Truncated Matrix Completion - An Empirical Study. We keep its failure criterion: a run with normalized RMSE of $10^{-4}$ or higher counts as failed. Trimming from Keshavan et al. is the standard preprocessing baseline.
The key ablation isolates reweighting from plain shrinkage. We take the unweighted estimator and raise its regularization strength until its held-out RMSE matches the smoothed-weighted model. We then compare $S_{\text{row}}$ between the two. All methods get the same masks, the same rank grid, and the same number of hyperparameter trials on the same validation split. Sensitivity is measured on the same sampled deletion set for every method.
Beating the strongest baseline has a specific meaning. At equal held-out RMSE, within the reproduction's run-to-run spread, a method must achieve lower $S_{\text{row}}$ and lower tail-decile row-restricted change, and the reduction must be larger than the seed-to-seed variation of the sensitivity estimate.
Why not just…?
Why not just use worst-case perturbation bounds? Worst-case bounds for singular value decomposition and projection are available. They are dominated by the single most fragile entry, which under skewed sampling is always some row with one or two ratings. Such bounds therefore say every estimator is unstable and cannot separate good estimators from bad ones. The same failure appears for clustering, where a single outlier forces $\Omega(1)$ worst-case sensitivity against $O(1/n)$ average sensitivity (Average Sensitivity of Euclidean k-Clustering). Our row-balanced metric sits between the worst case and the uniform average, and the experiments show whether it ranks estimators differently from both.
Why not just regularize more strongly? Heavier shrinkage lowers sensitivity everywhere, and this is the most serious threat to the proposal. If a tuned ridge or trace-norm penalty traces the same accuracy-versus-tail-stability curve as smoothed weighting, then reweighting adds nothing beyond regularization. The matched-RMSE ablation decides this directly. We commit in advance to reporting it as the headline result whichever way it comes out.
Why not just trim high-degree rows and columns? Trimming discards hub observations, which makes the degree profile more even and can make $S_{\text{unif}}$ look more like $S_{\text{row}}$. It does nothing for low-degree rows, whose few entries remain their only evidence. Its accuracy cost under non-uniform sampling is visible in the gains that reweighting reports on Netflix in Learning with the weighted trace-norm under arbitrary sampling distributions. We include trimming so that the claim "trimming does not help the tail" is measured, not assumed.
Why not just retrain and measure empirically, without theory? The empirical harness is part of the proposal. Theory adds a prediction of how sensitivity scales with degree skew, which tells practitioners which users to worry about without running thousands of refits. The theory is falsified if the measured degree-to-sensitivity slope departs from the predicted inverse-degree scaling.
Proposed Experiments
The synthetic study uses rank-10 Gaussian matrices of the $500 \times 500$ scale used in Universal Matrix Completion. We generate rank-one probability masks $P = uv^\top$ with power-law $u, v$ whose exponent is swept from near-uniform to highly skewed. We add the block-constant masks and the rank-one masks of Entry-Specific Bounds for Low-Rank Matrix Completion under Highly Non-Uniform Sampling, and the three truncation schemes of Truncated Matrix Completion - An Empirical Study: observing only non-negative entries, observing only entries near the mean, and observing mostly strongly liked or disliked entries.
The real-data study uses MovieLens 100K, MovieLens 10M, and Netflix, all of which already carry heavy-tailed observation patterns. On each we report held-out RMSE, $S_{\text{unif}}$, $S_{\text{row}}$, and sensitivity broken down by degree decile.
The first decisive check targets the measurement claim. As skew increases on synthetic masks, $S_{\text{unif}}$ for the naive baseline should stay within a small factor of its near-uniform value while $S_{\text{row}}$ grows. The same divergence should appear on MovieLens and Netflix. If the two metrics track each other, the core claim is wrong and the project reduces to bounding a quantity that nobody is misreading.
The second decisive check is the matched-RMSE comparison of smoothed weighting against stronger regularization. It is described in the baselines and decides whether reweighting is a stabilizer or merely a regularizer.
The third check tests whether locality helps the tail: does SVT-sub reduce tail-decile sensitivity relative to SVT-whole? It also tests whether GNMR's reported recovery under truncation is accompanied by low sensitivity or hides unstable tail rows. Finally, we test whether the change in spectral gap after deletion predicts per-entry sensitivity, measured by rank correlation on the synthetic masks. A strong correlation would give a cheap diagnostic for fragile users that needs no refitting.
References
- Average Sensitivity of Graph Algorithms
- Learning with the weighted trace-norm under arbitrary sampling distributions
- Average Sensitivity of Euclidean k-Clustering
- Average Sensitivity of Spectral Clustering
- Weighted matrix completion from non-random, non-uniform sampling patterns
- Universal Matrix Completion
- Entry-Specific Bounds for Low-Rank Matrix Completion under Highly Non-Uniform Sampling
- Leave-One-Out Approach for Matrix Completion: Primal and Dual Analysis
- Truncated matrix completion-an empirical study
- Matrix completion from a few entries