Research map / Learning theory and algorithms / Matrix and tensor methods
Generalization Analysis of Deep Non-linear Matrix Completion
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives uniform and distribution-free generalization bounds for Schatten-p quasi-norm matrix completion (equivalent to deep matrix factorization), weighted variants, and a Functionally Rescaled Matrix Completion (FRMC) model that adds only a negligible sample-complexity term.
Problem
Sample complexity / generalization of matrix completion with Schatten p quasi-norm constraints (equivalently deep matrix factorization) and non-linear extensions, which had little uniform-convergence analysis.
Approach
Derive Rademacher-complexity bounds for Schatten-p constrained matrix completion via a parametric interpolation between rank-restricted and nuclear-norm regimes, plus multi-class chaining lemmas; extend to FRMC by applying a learnable Lipschitz function entrywise, which adds only a term independent of matrix size.
Key results
- Theory: uniform-sampling sample complexity of order rO(rn) with r the Schatten-scaled rank proxy; distribution-free bound rO(r^{1-p/2} n^{1+p/2}), reducing to rO(sqrt(r) n^{3/2}) at p=1.
- On real data FRMC variants reach test RMSE 0.7627 on Douban vs 0.8042 for nuclear norm baseline S2 (d=2), and 1.0327 vs 2.5885 on LastFM.
- Experiments find p=2/3 (Schatten 2/3) generally outperforms p=1 and weighted versions slightly outperform unweighted.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add a trainable rescaling function with a nuclear norm constraint | S2 · Douban test | RMSE: 0.8042 -> 0.7627 | Helped |
| add a trainable rescaling function with a nuclear norm constraint | S2 · LastFM test | RMSE: 2.5885 -> 1.0327 | Helped |
| add a trainable rescaling function with a nuclear norm constraint | S2 · MVL25 test | RMSE: 0.8047 -> 0.7795 | Helped |
| use weighted-norm regularization (ablation) | FRMC-FS2 · Douban test | RMSE: 0.7627 -> 0.7626 | Helped |
| use weighted-norm regularization (ablation) | FRMC-FS2 · LastFM test | RMSE: 1.0327 -> 1.0091 | Helped |
| use weighted-norm regularization (ablation) | FRMC-FS2 · MVL25 test | RMSE: 0.7795 -> 0.7776 | Helped |
| use depth d=3 instead of d=2 (ablation) | FRMC-FS · Douban test | RMSE: 0.7627 -> 0.7674 | Hurt |
| use depth d=3 instead of d=2 (ablation) | FRMC-FS · LastFM test | RMSE: 1.0327 -> 0.9952 | Helped |
| use depth d=3 instead of d=2 (ablation) | FRMC-FS · MVL25 test | RMSE: 0.7795 -> 0.7711 | Helped |
| use weighted-norm regularization (ablation) | FRMC-FS3 · Douban test | RMSE: 0.7674 -> 0.7616 | Helped |
| use weighted-norm regularization (ablation) | FRMC-FS3 · LastFM test | RMSE: 0.9952 -> 0.9904 | Helped |
| use weighted-norm regularization (ablation) | FRMC-FS3 · MVL25 test | RMSE: 0.7711 -> 0.7799 | Hurt |
Surprising findings
- Weighted Schatten quasi-norm restores the sample complexity to rO(rn) in the distribution-free setting.
Limitations
- Results are polylog-hidden and mainly for bounded Lipschitz losses; excess risk result only holds for p=2/d.
- Real-data experiments are limited to three datasets and a small set of baselines.
Experimental setup
Datasets: DOUBAN LastFM MovieLens 25M synthetic low-rank matrices with non-uniform sampling
Benchmarks: DOUBAN LastFM MovieLens 25M synthetic matrices
Metrics: test RMSE recovery error vs observed fraction
Baselines: nuclear norm regularized matrix completion (S2) weighted Schatten 2/3 (SW3) SW2 S3 FRMC-FS2 FRMC-FSW2 FRMC-FS3 FRMC-FSW3
Builds on: weighted trace norm Shamir & Shalev-Shwartz matrix completion bounds Dudley entropy chaining Foygel et al. 2011 weighted trace norm
Closest papers by meaning
- Fine-grained Generalization Analysis of Inductive Matrix Completion (NeurIPS 2021 · similarity 0.93)
- Generalization Bounds for Inductive Matrix Completion in Low-Noise Settings (AAAI 2023 · similarity 0.92)
- Symmetric Matrix Completion with ReLU Sampling (ICML 2024 · similarity 0.90)
- Generalization Bounds for Rank-sparse Neural Networks (NeurIPS 2025 · similarity 0.89)
- RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees (NeurIPS 2025 · similarity 0.88)
- Connectivity Shapes Implicit Regularization in Matrix Factorization Models for Matrix Completion (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.