On the Regularization Landscape for the Linear Recommendation Models

Summary

The paper asks whether the many high-performing linear recommendation models are coincidentally similar or instances of a single framework. Through a chain of equivalences, the authors show that regularized PCA, dropout-based matrix factorization, denoising linear autoencoders (LAE), and a linear simplification of variational autoencoders all solve least-squares problems with (weighted) nuclear-norm regularizers, while EASE, DLAE, and EDLAE solve Frobenius-norm-regularized objectives. Two structural results follow. Proposition 2 proves the linear-VAE objective is equivalent to a weighted nuclear-norm problem whose weights are automatically sorted ascending, via a matrix rearrangement inequality, resolving an open problem of Bao et al. (2020). Lemma 2 shows that ∥W∥_p^* regularizers yield identical uniform singular-value shrinkage for all p≥1, explaining why only p=1,2 appear in practice. The authors argue the nuclear-norm family is rigid — estimators retain the data's singular vectors — capping predictive power, supported by a weight-ordering ablation (Table 2: ML-20M nDCG@100 drops 0.4102→0.3361). They then derive two approximate low-rank closed-form EDLAE estimators (SVD truncations with the zero-diagonal constraint relaxed) that avoid ADMM. On ML-20M, Netflix, and MSD under strong-generalization splits, LR-EDLAE-1/2 match full-rank EDLAE and the ADMM solution within about 0.002 nDCG@100 (Table 1, Fig 1). Limitations: the new solutions are approximate rather than exact low-rank optima; there is no variance or significance testing; and the delta over Jin et al. (2021) is incremental.