Improving the Optimization Landscape of Matrix Completion with $ε$-close Surrogates

Ziye Ma

cs.LGOct 30, 2026

Improving the Optimization Landscape of Matrix Completion with $ε$ -close Surrogates

Authors: Ziye Ma

Organizations: Department of Computer Science, City University of Hong Kong

Abstract

Non-convex optimization is central to machine learning and AI, yet unlike its convex counterpart, it still lacks a general and principled framework. In this work, we try to highlight the importance of combining noisy perturbations with over-parametrization mathematically under the classic setting of matrix completion (MC). Matrix completion is an important non-convex recovery problem in which only a subset of a matrix's entries is observed, and the remaining entries must be recovered using low-rank constraints. This problem is notoriously difficult because observations are limited. However, we show that by injecting $ε$ -level perturbations into the nullspace of the observation mask, we can construct noisy matrix sensing surrogates whose solutions remain $\mathcal{O}(ε)$ -close to the ground truth with valid restricted isometry property (RIP) constants. The existence of RIP further enables powerful tensor frameworks to be applied with theoretical guarantees. This approach reflects a broader empirical trend in which stochasticity or noise improves the curvature of the optimization landscape, allowing over-parameterized (a.k.a large) models to better separate signal from noise. Assuming each matrix entry is observed independently, we establish quantitative recovery guarantees without explicit requirements on sampling rate or incoherence, and discuss how such assumptions can further strengthen our results.

Figures & tables

Approach	Conditions for recovery w.h.p.
Semi-definite Relaxation ( Ding and Chen,, 2020 )	$p\geq\mathcal{O}\left(\mu_{0}r\log(\mu_{0}r)n\log(n)/n^{2}\right)$
BM Factorization ( Zilber and Nadler, 2022a, )	$p\geq\mathcal{O}\left(\mu_{0}r\max\{\log n,\,\mu_{0}r\kappa^{2}\}/n\right)$
Nuclear Norm Lasso ( Chen et al.,, 2020 )	$p\geq\mathcal{O}\left(\mu^{2}_{0}\log(n)^{3}/n\right)$
Spectral Methods ( Chen et al.,, 2021 )	$p\geq\mathcal{O}\left(\kappa^{2}\mu_{0}r\log(n)/n\right)$
Ours	Localized identifiability and shell regularity

Table 1: Brief summary of state-of-the-art recovery guarantees of different approaches in solving ( 2 ). This assumes each entry of

M^{*}

is sampled uniformly with probability

p

\mu_{0}

and

\kappa

denotes incoherence and condition number for

M^{*}

respectively.

Panel of Figure 1 — Figure 1: We use $\epsilon=5\times 10^{-5}$ , a learning rate of $2\times 10^{-2}$ , and an initialization scale of $\xi=10^{-4}$ for ( 18 ). SDP was not deployed for (a) since the solution is not unique in the relaxed regime. For (b), the variability of $\Omega$ necessitates running 10 distinct problem instances for each size $n$ .

	$p=0.02$			$p=0.05$			$p=0.08$
Solver	MC	$\epsilon$ -MC	$\Delta$ (pp)	MC	$\epsilon$ -MC	$\Delta$ (pp)	MC	$\epsilon$ -MC	$\Delta$ (pp)
Adam	0	0	0	30	40	$\mathbf{+10}$	70	60	$\mathbf{-10}$
GNMR (reference)	0	0	0	0	0	0	0	0	0
GD (Armijo)	0	0	0	90	90	0	100	100	0
L-BFGS	0	0	0	90	90	0	100	100	0

Table 2: Direct recovery at

n=200

: perturbation changes only Adam’s success rate.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 2: Ablation studies for the lifted $\epsilon$ -MC formulation with $n=6$ , $\ell=3$ , initialization magnitude $10^{-4}$ . Top: Success rates with respect to the perturbation level $\epsilon$ , under two reconstruction criteria $\|X_{T}X_{T}^{\top}-M^{\star}\|_{F}\leq 0.05$ and $\|X_{T}X_{T}^{\top}-M^{\star}\|_{F}\leq 0.01$ , together with the BM baseline success rate (dashed line) for the structured instance ( 24 ). Success rate is polled from 100 independent trials each. Bottom: Success rates of the independently sampled problem with respect to sampling probability $p$ , comparing the BM approach and the lifted $\epsilon$ -MC method under both reconstruction criteria. For each $p$ level, 10 random masks are generated and 20 trials each are run for a total of 200 trials.

	s0	s1	s2	s3	s4	s5	s6	s7	s8	s9
$\mathrm{MSE}_{\text{obs}}$	3.26e-8	4.89e-8	9.46e-9	9.79e-9	1.35e-8	1.67e-8	1.07e-8	9.40e-9	1.41e-8	1.50e-8
$\mathrm{MSE}_{\text{unobs}}$	2.67e0	4.95e-8	2.67e0	2.67e0	8.23e-8	8.24e-8	2.67e0	2.67e0	2.67e0	2.67e0

Appendix

Table 3: Mean-squared error on observed and unobserved entries for the structured instance in problem ( 24 ) with

n=8

\ell=3

\epsilon=10^{-4}

, learning rate

0.02

, and initialization scale

10^{-4}

. Columns

s0

–

s9

correspond to independent runs ( sol_0 – sol_9 ). In most runs,

\mathrm{MSE}_{\text{obs}}

is near machine precision while

\mathrm{MSE}_{\text{unobs}}

is either of order

1

(unsuccessful completions) or of order

10^{-8}

(successful completions), highlighting that unsuccessful runs fit the observed entries but differ in their extrapolation to unobserved entries.

Panel of Figure 3 — Figure 3: Spatial distribution of squared reconstruction error for the structured instance in problem ( 24 ) with $n=8$ , $\ell=3$ , $\epsilon=10^{-4}$ , learning rate $0.02$ , and initialization scale $10^{-4}$ . The background colormap shows $(M^{\text{sol}}_{ij}-M^{\star}_{ij})^{2}$ , and white squares denote observed entries $(i,j)\in\Omega$ . In the three runs with higher global error (a)–(c), the reconstruction is essentially exact on observed entries and the error is concentrated on unobserved entries, with different spatial patterns across runs. In the successful run (d), the error is small on both observed and unobserved entries.

$n$	$\epsilon_{n}$	GD (%)	GD+SOD (%)
50	0.097980	13.2	51.4
100	0.068571	2.0	46.4
200	0.048242	0.0	52.2

Appendix

Table 4: SOD success rates over

500

paired starts per dimension, with matched GD-update budgets.

Matrix Completion

Matrix completion estimates missing entries in partially observed matrices by exploiting low-rank structure and related information.

See all 24 papers

Near-Optimal Nonconvex Matrix Completion
Sep 15, 2026Jian-Feng Cai, Xiliang Lu, Juntao YouRiemannian Optimization Nonconvex Optimization
Department of Mathematics, Hong Kong University of Science and Technology. · School of Mathematics and Statistics, Hubei Center for Applied Mathematics, and Hubei Key Laboratory of Computational Science, Wuhan University, Wuhan 430072, China. · School of Artificial Intelligence, Hubei Center for Applied Mathematics, and Hubei Key Laboratory of Computational Science, Wuhan University, Wuhan 430072, China.
Over-parameterization Is Neither Robust nor Fragile in Matrix Sensing: A Geometric Theory of Solution Robustness
Oct 13, 2026Runze Shi, Ziye MaOverparameterization Matrix Factorization
City University of Hong Kong
Sample-efficient inductive matrix completion with noise and inexact side-information
May 16, 2026Yuepeng Yang, Cong MaRobust Matrix Completion Matrix Optimization
Department of Statistics and Data Sciences, Yale University · Department of Statistics, University of Chicago

Sep 15, 2026J/K move · Enter open · S save

Near-Optimal Nonconvex Matrix Completion

Jian-Feng Cai, Xiliang Lu, Juntao You

Department of Mathematics, Hong Kong University of Science and Technology. · School of Mathematics and Statistics, Hubei Center for Applied Mathematics, and Hubei Key Laboratory of Computational Science, Wuhan University, Wuhan 430072, China. · School of Artificial Intelligence, Hubei Center for Applied Mathematics, and Hubei Key Laboratory of Computational Science, Wuhan University, Wuhan 430072, China.

Riemannian Optimization Nonconvex Optimization Matrix Completion

Open paper AskPDF arXiv

We study nonconvex methods for matrix completion, the problem of recovering a low-rank matrix from a subset of its entries. Convex methods achieve sample complexity linear in the matrix dimension and the rank, up to logarithmic factors, whereas global guarantees for commonly used nonconvex methods require a higher polynomial dependence on the rank. We close this gap by analyzing Riemannian gradient descent (RGD) and Riemannian Gauss--Newton (RGN) methods. For an

n\times n

matrix of rank

r

with incoherence parameter

μ

and condition number

κ

, the two methods achieve exact recovery with high probability from

O(μnr\log n\log(nκ))

and

O(μnr\log n\log(2μrκ))

observations, respectively. The methods use a multiscale residual initialization, while the analysis simultaneously controls the spectral error and incoherence. The resulting RGD iterates converge linearly, whereas RGN eventually converges Q-quadratically.

Abstract

Matrix Completion

Explore similar work

Near-Optimal Nonconvex Matrix Completion

Over-parameterization Is Neither Robust nor Fragile in Matrix Sensing: A Geometric Theory of Solution Robustness

Sample-efficient inductive matrix completion with noise and inexact side-information