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

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.
Implicit Bias and Loss of Plasticity in Matrix Completion: Depth Promotes Low-Rankness
Mar 5, 2026Baekrok Shin, Chulhee YunImplicit Bias Neural Network Training Dynamics
Kim Jaechul Graduate School of AI, KAIST
Improving the Optimization Landscape of Matrix Completion with $ε$ -close Surrogates
Oct 30, 2026Ziye MaMatrix Completion Nonconvex Optimization
Department of Computer Science, City University of Hong Kong

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

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