Over-fitting Control in Deep Nonlinear Matrix Completion via Gradual Nonsmooth Regularization

Sajad Faramarzi; Farzan Haddadi; Sajjad Amini; Masoud Ahookhosh; Symeon Chatzinotas

cs.ITMar 15, 2024

Over-fitting Control in Deep Nonlinear Matrix Completion via Gradual Nonsmooth Regularization

Authors: Sajad Faramarzi, Farzan Haddadi, Sajjad Amini, Masoud Ahookhosh, Symeon Chatzinotas

Organizations: School of Electrical Engineering, Iran University of Science & Technology, Tehran, Iran. · Electronics Research Institute (ERI) at Sharif University of Technology, Tehran, Iran. · College of Information and Computer Sciences, University of Massachusetts Amherst, Amherst, MA, USA. · Department of Mathematics at the University of Antwerp, Antwerp, Belgium. ·

Abstract

Conventional matrix completion methods exploit the underlying low-rank structure of a target matrix to recover its missing entries, but may be inadequate for capturing complex nonlinear dependencies. Deep neural networks have therefore been increasingly adopted for nonlinear matrix completion (NLMC). However, their high representational capacity, particularly in deep fully connected neural networks (FCNNs), can lead to over-fitting when training is restricted to incomplete observations. In this paper, we propose a Deep Neural Network with Nonsmooth Regularization (DNN-NSR) framework to address this issue by incorporating two complementary structural priors: sparsity of intermediate representations and low-rankness of layer-wise weight matrices. Specifically, the $\ell_1$ -norm of hidden representations promotes sparse latent features, while the nuclear norm of weight matrices encourages low-rank layer-wise transformations. To optimize the resulting nonsmooth and nonconvex objective, we develop an extrapolated proximal gradient algorithm that employs soft-thresholding and singular-value thresholding to handle the two regularization terms, respectively. We further introduce a gradual regularization strategy that progressively increases the influence of these structural penalties during training. Under suitable assumptions, we establish convergence properties of the proposed algorithm toward a critical point of the training objective. The effectiveness of DNN-NSR is evaluated through extensive experiments on synthetic matrix recovery, single-image inpainting, and recommender systems using the MovieLens 100K and MovieLens 1M datasets. Comparisons with representative linear and nonlinear matrix completion methods demonstrate the potential of the proposed framework to improve recovery performance by jointly exploiting sparse latent representations and low-rank network transformations.

Figures & tables

$\rho(\%)$	Metric	IALM	NCARL	AEMC	DLMC	BiBNN	LeRMC	DNN-NSR
$10$	PSNR	$24.5461$	$28.0245$	$29.7751$	$33.4047$	$35.1094$	$35.8012$	$\mathbf{{\color[rgb]{0.75,0,0.25}36.3523}}$
	SD	$0.8544$	$0.7311$	$\mathbf{{\color[rgb]{0.75,0,0.25}0.5079}}$	$0.5659$	$0.6021$	$0.6242$	$0.6071$
	MSE	$18.7516$	$6.0520$	$6.1220$	$4.7950$	$3.9784$	$2.8456$	$\mathbf{{\color[rgb]{0.75,0,0.25}1.1040}}$
$30$	PSNR	$19.1643$	$22.9383$	$23.7157$	$27.8859$	$31.4614$	$32.1214$	$\mathbf{{\color[rgb]{0.75,0,0.25}33.2218}}$
	SD	$1.1022$	$1.1880$	$1.1918$	$1.2249$	$1.0837$	$0.9435$	$\mathbf{{\color[rgb]{0.75,0,0.25}0.6140}}$
	MSE	$25.0865$	$10.8373$	$7.2170$	$5.9620$	$4.1327$	$3.7168$	$\mathbf{{\color[rgb]{0.75,0,0.25}2.6990}}$

TABLE I: PSNRs, SDs, and MSEs on synthetic matrix

\mathbf{X}_{1}\in\mathbb{R}^{100\times 200}

with

\rho=10\%,30\%,50\%

, and

80\%

$\rho(\%)$	Metric	IALM	NCARL	AEMC	DLMC	BiBNN	LeRMC	DNN-NSR
$10$	PSNR	$26.1469$	$30.3217$	$30.5333$	$32.5475$	$35.2654$	$36.2145$	$\mathbf{{\color[rgb]{0.75,0,0.25}37.3565}}$
	SD	$0.6883$	$0.6617$	$0.6655$	$0.6592$	$0.7553$	$0.6784$	$\mathbf{{\color[rgb]{0.75,0,0.25}0.5672}}$
	MSE	$15.4390$	$4.8132$	$4.5421$	$3.7843$	$3.2200$	$2.5647$	$\mathbf{{\color[rgb]{0.75,0,0.25}1.9130}}$
$30$	PSNR	$20.5052$	$24.4008$	$24.0187$	$27.4959$	$32.9584$	$33.5687$	$\mathbf{{\color[rgb]{0.75,0,0.25}35.1072}}$
	SD	$0.8169$	$0.6915$	$0.6056$	$0.7185$	$0.7552$	$0.7225$	$\mathbf{{\color[rgb]{0.75,0,0.25}0.6594}}$
	MSE	$18.2639$	$6.8739$	$6.4113$	$4.3082$	$3.4340$	$3.0214$	$\mathbf{{\color[rgb]{0.75,0,0.25}2.7940}}$

TABLE II: PSNRs, SDs, and MSEs on synthetic matrix

\mathbf{X}_{2}\in\mathbb{R}^{300\times 200}

with

\rho=10\%,30\%,50\%

, and

80\%

Panel of Figure 3 — Fig. 1 : RGB images for the experiment.

Panel of Figure 4 — Fig. 2 : Masked and inpainted results for Images $\mathrm{I}$ and $\mathrm{II}$ with $50\%$ random masked pixels, (a): masked Image $\mathrm{I}$ , (b) masked Image $\mathrm{II}$ , (c) inpainted Image $\mathrm{I}$ , (d) inpainted Image $\mathrm{II}$ .

$\rho(\%)$	Metric	IALM	NCARL	AEMC	DLMC	BiBNN	LeRMC	DNN-NSR
$30$	PSNR	$16.7313$	$27.6908$	$28.4982$	$29.6249$	$30.4575$	$30.5142$	$\mathbf{{\color[rgb]{0.75,0,0.25}30.8723}}$
$30$	SSIM	$0.3434$	$0.7838$	$0.8269$	$0.8629$	$0.8736$	$0.8755$	$\mathbf{{\color[rgb]{0.75,0,0.25}0.8774}}$
$40$	PSNR	$16.7342$	$26.6660$	$27.9642$	$29.3363$	$29.7862$	$29.9431$	$\mathbf{{\color[rgb]{0.75,0,0.25}30.2301}}$
$40$	SSIM	$0.3310$	$0.7606$	$0.7946$	$0.8488$	$0.8597$	$0.8610$	$\mathbf{{\color[rgb]{0.75,0,0.25}0.8656}}$
$50$	PSNR	$16.7315$	$25.9480$	$27.4329$	$28.7921$	$28.9233$	$29.1411$	$\mathbf{{\color[rgb]{0.75,0,0.25}30.0301}}$
$50$	SSIM	$0.3169$	$0.7466$	$0.7221$	$0.8009$	$0.8342$	$0.8411$	$\mathbf{{\color[rgb]{0.75,0,0.25}0.8521}}$

TABLE III : PSNRs and SSIMs on Image

\mathrm{I}

in Fig. 1 with

30\%

40\%

, and

50\%

randomly masked pixels as examples.

$\rho(\%)$	Metric	IALM	NCARL	AEMC	DLMC	BiBNN	LeRMC	DNN-NSR
$30$	PSNR	$19.5454$	$26.7432$	$27.5896$	$28.0446$	$\mathbf{{\color[rgb]{0.75,0,0.25}30.0519}}$	$29.0135$	$29.7962$
$30$	SSIM	$0.4912$	$0.9177$	$0.9364$	$0.9501$	$\mathbf{{\color[rgb]{0.75,0,0.25}0.9797}}$	$0.9587$	$0.9693$
$40$	PSNR	$19.5414$	$25.6884$	$26.7736$	$27.3264$	$29.0604$	$29.0847$	$\mathbf{{\color[rgb]{0.75,0,0.25}29.1035}}$
$40$	SSIM	$0.4904$	$0.8891$	$0.9084$	$0.9291$	$0.9600$	$0.9615$	$\mathbf{{\color[rgb]{0.75,0,0.25}0.9643}}$
$50$	PSNR	$19.5241$	$25.4958$	$27.0324$	$26.6429$	$27.9312$	$28.1475$	$\mathbf{{\color[rgb]{0.75,0,0.25}28.8465}}$
$50$	SSIM	$0.4894$	$0.8429$	$0.8691$	$0.9010$	$0.9407$	$0.9424$	$\mathbf{{\color[rgb]{0.75,0,0.25}0.9488}}$

TABLE IV : PSNRs and SSIMs on Image

\mathrm{II}

in Fig. 1 with

30\%

40\%

, and

50\%

randomly masked pixels as examples.

Dataset	$\#$ Users	$\#$ Films	$\#$ Rating	$\#$ Rating range
MovieLens $100$ k	943	1682	$10^{5}$	1-5
MovieLens $1$ M	6040	3952	$10^{6}$	1-5

TABLE V : Information of MovieLens

100

k and

1

Dataset	$\rho(\%)$	IALM	NCARL	AEMC	DLMC	BiBNN	LeRMC	DNN-NSR
MovieLens $100$ k	$30\%$	$19.69$	$19.01$	$18.87$	$18.39$	$17.23$	$16.85$	$\mathbf{{\color[rgb]{0.75,0,0.25}15.54}}$
MovieLens $100$ k	$50\%$	$20.22$	$19.61$	$19.06$	$18.75$	$18.12$	$17.74$	$\mathbf{{\color[rgb]{0.75,0,0.25}17.07}}$
MovieLens $1$ M	$30\%$	$18.51$	$18.25$	$18.18$	$18.03$	$17.02$	$16.94$	$\mathbf{{\color[rgb]{0.75,0,0.25}16.82}}$
MovieLens $1$ M	$50\%$	$18.95$	$18.78$	$18.36$	$18.31$	$17.78$	$17.56$	$\mathbf{{\color[rgb]{0.75,0,0.25}17.16}}$

TABLE VI : NMAE(%) of recommender system on MovieLens

100

k and MovieLens

1

M datasets.

Panel of Table 9 — TABLE VII : PSNRs for two synthetic data with $\rho=50\%$ and $80\%$ and Images $\mathrm{I}$ and $\mathrm{II}$ in Fig. 1 with random masked pixels $40\%$ and $50\%$ for different values of $\mu_{\max}$ and $\mu_{\min}=1$ .

Panel of Figure 10 — Fig. 3 : Variation of loss function for (a) $300\times 200$ synthetic matrix with $\rho=80\%$ ; (b) $300\times 200$ synthetic matrix with $\rho=30\%$ , and (c) Image $\mathrm{I}$ in Fig. 1 with $\rho=50\%$ .

Matrix Completion

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

See all 24 papers

Sep 15, 2026

Near-Optimal Nonconvex Matrix Completion

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.

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

Ask PDF

Mar 5, 2026

Implicit Bias and Loss of Plasticity in Matrix Completion: Depth Promotes Low-Rankness

We study matrix completion via deep matrix factorization (a.k.a. deep linear neural networks) as a simplified testbed to examine how network depth influences training dynamics. Despite the simplicity and importance of the problem, prior theory largely focuses on shallow (depth-2) models and does not fully explain the implicit low-rank bias observed in deeper networks. We identify coupled dynamics as a key mechanism behind this bias and show that it intensifies with increasing depth. Focusing on gradient flow under block-diagonal observations, we prove: (a) networks of depth

\geq 3

exhibit coupling unless initialized diagonally, and (b) convergence to rank-1 occurs if and only if the dynamics is coupled -- resolving an open question by Menon (2024) for a family of initializations. We also revisit the loss of plasticity phenomenon in matrix completion (Kleinman et al., 2024), where pre-training on few observations and resuming with more degrades performance. We show that deep models avoid plasticity loss due to their low-rank bias, whereas depth-2 networks pre-trained under decoupled dynamics fail to converge to low-rank, even when resumed training (with additional data) satisfies the coupling condition -- shedding light on the mechanism behind this phenomenon.

Baekrok Shin, Chulhee Yun

Kim Jaechul Graduate School of AI, KAIST

Implicit Bias Neural Network Training Dynamics Matrix Completion Deep Linear Networks Low-Rank Matrix Decomposition Loss of Plasticity

Ask PDF

Oct 30, 2026

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

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.

Ziye Ma

Department of Computer Science, City University of Hong Kong

Matrix Completion Nonconvex Optimization Inverse Problems

Ask PDF

Abstract

Matrix Completion

Explore similar work

Near-Optimal Nonconvex Matrix Completion

Implicit Bias and Loss of Plasticity in Matrix Completion: Depth Promotes Low-Rankness

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

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