Research map / Optimization / Implicit bias and generalization
Symmetric Matrix Completion with ReLU Sampling
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.
Studies symmetric PSD low-rank matrix completion when only positive (ReLU) or above-threshold entries are observed, proving local geodesic strong convexity near the planted matrix and proposing a tailored spectral initialization for gradient descent.
Problem
Low-rank symmetric PSD matrix completion where the observation pattern depends deterministically on entry values (only non-negative entries observed under ReLU sampling), where global landscape is not benign and standard random initialization fails.
Approach
Shows that under ReLU or threshold sampling, the factorized objective is geodesically strongly convex on the quotient manifold in a neighborhood of the planted matrix, with an entry-dependent spectral initialization (observed entries kept, missing entries set to negative magnitudes) that lets gradient descent reach the global optimum.</ntml:parameter>
Key results
- Gradient descent with the tailored initialization converged to the ground truth in noiseless experiments (n=200, r=5), with completion error on the order of 1e-11, while random-imputation and random spectral initializations got stuck at spurious critical points (completion error about 0.5).
- The proposed method achieved completion error comparable to ADMM, ScaledGD, PAM, MPAM and GNMR at n=1000, r=20 while being faster than ADMM and GNMR.
- Completion remained successful well beyond the theoretical rank bound, breaking down only around r=45 for n=200.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the tailor-designed initialization instead of RI initialization (ablation) | GD for ReLU matrix completion · ReLU MC, σ = 0 | completion error γ_T: 0.5 ± 0.13 -> (7.6 ± 0.7) · 10^{-11} | Helped |
| Use the tailor-designed initialization instead of RS initialization (ablation) | GD for ReLU matrix completion · ReLU MC, σ = 0 | completion error γ_T: 0.45 ± 0.24 -> (7.6 ± 0.7) · 10^{-11} | Helped |
| Use the tailor-designed initialization instead of RI initialization (ablation) | GD for ReLU matrix completion · ReLU MC, σ = 10^{-4} | completion error γ_T: 0.51 ± 0.13 -> (4.4 ± 0.13)·10^{-5} | Helped |
| Use the tailor-designed initialization instead of RS initialization (ablation) | GD for ReLU matrix completion · ReLU MC, σ = 10^{-4} | completion error γ_T: 0.51 ± 0.13 -> (4.4 ± 0.13)·10^{-5} | Helped |
Surprising findings
- The objective landscape under ReLU sampling is not globally benign: gradient descent with random initialization generally converges to non-global critical points.
- Empirical completion succeeds at ranks far beyond the theoretical bound r <= (1/2) log2 n.
Limitations
- Analysis assumes known rank and rank-r symmetric PSD matrices; extension to rectangular matrices and unknown rank is open.
- Theory requires a strong connectivity assumption (Assumption d) on off-diagonal blocks, and the rank bound r <= (1/2) log2 n arises from the proof technique.
- Initialization explicitly exploits knowledge of the ReLU sampling scheme.
Experimental setup
Benchmarks: synthetic symmetric PSD matrices synthetic Euclidean distance matrices
Metrics: gradient norm function value relative completion error CPU time
Baselines: ADMM ScaledGD PAM MPAM GNMR random imputation spectral initialization random spectral initialization
Builds on: low-rank matrix completion via factorization quotient manifold optimization
Closest papers by meaning
- Rank-1 Matrix Completion with Gradient Descent and Small Random Initialization (NeurIPS 2023 · similarity 0.93)
- A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samples (ICML 2021 · similarity 0.92)
- RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees (NeurIPS 2025 · similarity 0.90)
- Generalization Analysis of Deep Non-linear Matrix Completion (ICML 2024 · similarity 0.90)
- Semi-Random Matrix Completion via Flow-Based Adaptive Reweighting (NeurIPS 2024 · similarity 0.90)
- Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time (ICLR 2024 · similarity 0.90)
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.