Research map / Optimization / Optimizers
Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use non-convex SGD with a warm-start initialization for online matrix completion | Online matrix completion · General matrix completion | sample complexity: Our result: \widetilde{O}\left(\mu d k \kappa^4 \left(k + \log \frac{1}{\epsilon}\right)\right); Alternating minimizatio | Helped |
| Use non-convex SGD with a warm-start initialization for online matrix completion | Online matrix completion · General matrix completion | total runtime: Our result: \widetilde{O}\left(\mu d k^4 \kappa^4 \log \frac{1}{\epsilon}\right); Alternating minimization: \widetilde{O | Mixed |
| Use larger stepsizes in the SGD analysis | Online SGD for matrix completion · Online matrix completion | total runtime: each update step in online phase is \order{k^3} | Helped |
| Maintain a warm start and control incoherence so SGD stays in the local region | Online SGD for matrix completion · General matrix completion | error convergence: \fnorm{\mat{U}_t\mat{V}_t^{\top} - \mat{M} }^2 \le \left(1-\frac{1}{2}\eta\cdot\sigma_{\min}(\mat{M})\right)^t\left(\fra | Helped |
| Renormalize the two factor matrices using their product's SVD at each step | Online SGD for general matrix completion · General matrix completion | per-update runtime: O(k^3) | Mixed |
| Use the PSD-only online SGD result | Online matrix completion · Symmetric PSD matrix completion | sample complexity: d·\text{poly}(\mu, k, \kappa) | Helped |
Closest papers by meaning
- Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completion (NeurIPS 2022 · similarity 0.93)
- Rank-1 Matrix Completion with Gradient Descent and Small Random Initialization (NeurIPS 2023 · similarity 0.92)
- Symmetric Matrix Completion with ReLU Sampling (ICML 2024 · similarity 0.91)
- No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis (ICML 2017 · similarity 0.91)
- RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees (NeurIPS 2025 · similarity 0.90)
- Semi-Random Matrix Completion via Flow-Based Adaptive Reweighting (NeurIPS 2024 · similarity 0.89)
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.