AIR-Net: Adaptive and Implicit Regularization Neural Network for matrix completion
Authors: Zhemin Li
Hongxia Wang
Venue: ICLR 2022 Submitted (2022)

Abstract: Conventionally, the matrix completion (MC) model aims to recover a matrix from partially observed elements. Accurate recovery necessarily requires a regularization encoding priors of the unknown matrix/signal properly. However, encoding the priors accurately for the complex natural signal is difficult, and even then, the model might not generalize well outside the particular matrix type. This work combines adaptive and implicit low-rank regularization that captures the prior dynamically according to the current recovered matrix. Furthermore, we aim to answer the question: how does adaptive regularization affect implicit regularization? We utilize neural networks to represent Adaptive and Implicit Regularization and named the proposed model \textit{AIR-Net}. Theoretical analyses show that the adaptive part of the AIR-Net enhances implicit regularization. In addition, the adaptive regularizer vanishes at the end, thus can avoid saturation issues. Numerical experiments for various data demonstrate the effectiveness of AIR-Net, especially when the locations of missing elements are not randomly chosen. With complete flexibility to select neural networks for matrix representation, AIR-Net can be extended to solve more general inverse problems.

Under review as a conference paper at ICLR 2022
AIR-NET: ADAPTIVE AND IMPLICIT REGULARIZA- TION NEURAL NETWORK FOR MATRIX COMPLETION
Anonymous authors Paper under double-blind review
ABSTRACT
Conventionally, the matrix completion (MC) model aims to recover a matrix from partially observed elements. Accurate recovery necessarily requires regulariza- tion encoding priors of the unknown matrix/signal properly. However, encoding the priors accurately for the complex natural signal is difficult, and even then, the model might not generalize well outside the particular matrix type. This work combines adaptive and implicit low-rank regularization that captures the prior dy- aim
namically according the current recovered matrix. Furthermore, swer the question: how does adaptive regularization affect implicit regularization? We utilize neural networks to represent Adaptive and Implicit Regularization and named the proposed model ATR-Net. Theoretical analyses show that the adaptive part of the AIR-Net enhances implicit regularization. In addition, the adaptive regularizer vanishes at the end, thus can avoid saturation issues. Numerical ex- periments for various data demonstrate the effectiveness of AIR-Net, especially when the locations of missing elements are not randomly chosen. With complete flexibility select neural networks for matrix representation, AIR-Net can be ex- tended to solve more general inverse problems.
INTRODUCTION
The matrix completion (MC) problem, which aims to recover matrix X mmxx from its par- tially observed elements, has arisen numerous domains, ranging from computer vision (Wen al.) 2012), recommender system (Netfli 2009), and drug-target interaction (DTI) (Mongia & Majum- dar (020). This fundamental problem ill-posed without assumptions on X since we have many completions. So it is essential to impose additional information or priors on the unknown ma- trix/signal.
To describe the prior for natural signal, restrict the solution in the corresponding space is diffi- cult. Classical methods for MC are mainly based on low-rank, sparsity or piece-wise smoothness
assumption (Rudin et al.) 1992. Buades et al. 2005 Romano al. 2014 Dabov al.) 2007).
These priors describe simple structural signal well, but may lead to a poor approximation of X"
with complex structures (Radhakrishnan et al., 2021) especially when the observed entries not sampled uniformly at random. Recently, deep neural networks (DNN) have shown a strong ability in extracting complex structures from large datasets al. 20188] Mukherrjee al.) 2021 How- ever, such large number of data sets cannot be obtained in many scenarios. Fortunately, DNN also works in solving some inverse problems without any extra training set (Ulyanov et al. 2018)
Over Over-parametric DNN performs well on single matrix is mysterious phenomenon. One of the explanations is there exists implicit regularization during training (Arora et al.) 2019) Xu et al.) 2019 Rahaman et al. 2019 Chakrabarty & Maji 2019). Although DNN with implicit regulariza- tion outperforms some classical methods,
insufficient to describe the space of complex X Extra-explicit regularization can improve its performance in signal recovery (Metzler et al.) 2018 Boyarski et al., 2019aa, Liu et al. 2019:: Li et al.) 2020). However, such explicit priors are often valid only for specific data sampling patterns. more flexible regularization is required to meet practical MC problems.
We introduce flexibility in this paper by firstly representing the explicit regularization using DNN without any extra training set. The explicit regularization we begin with Dirichlet Energy (DE), which is formulated as tr( X LX), with L Laplacian matrix describing the similarity between

---

Under review as a conference paper at ICLR 2022
columns. Note that L in DE is fixed during iteration. Building exact L based incomplete observation is very challenging. Therefore, we parameterize L with DNN, and revise L iteratively during training. Furthermore, We combine the learned DE, which is adaptive regularizer, with implicit regularization to form new regularization method for MC named AIR-Net. The interaction between explicit regularization and implicit regularization in solving MC problems is further stud- ied. The results show that combining the two can obtain a new, more flexible regularization model and enhance the low-rank preference of implicit regularization. In many examples, AIR-NET has more vital feature representation ability and more comprehensive application range and shows state-of-art performance.
2
ADAPTIVE AND IMPLICIT REGULARIIZATION NEURAL NETWORK
Our model is proposed as follow:
min X.W;
Call = Lv (A(X)) + Σ A Rw. (Ti ==1
(I)
X (i,j) E and S2 are the observed coordinates set, and the 0, (1,3) E
where ( = X le
other entries are missing. Different from other regularization models for MC, here X is represented by neural network which tends to be low-rank implicitly (Section 2.1). and Rw, is an adaptive regularization with a forward neural network represented Laplacian matrix(Section 2.2). The de- tailed notations will be introduced in the corresponding sections. A specific case of Equation 1 for matrix completion is given in Section 2.3
2.1 DMF AS AN IMPLICIT REGULARIZATION
In order to make the model suitable for more matrix types, we need more general data prior. The low-rank is a very general prior in various matrix types. There are two main ways to encode the low-rank prior into model: (a) Adding an explicit regularization term such as rank and nuclear norm
(Candès & Recht 2009; Lin et al. 2010). (b) Using low-dimensional latent variable model to represent X. including matrix factorization (MF) and its varieties (Koren et al. 2009 Fan & Cheng. 2018). The first case suffers from the saturation issue, which is induced by explicit regularization. The second one faces the problem of estimating proper latent variable dimension.
Unlike the existing MF model, which constricts the size of the shared dimension of the factorized matrix, DMF can take a large shared dimension and still preserve the low-rank property without explicit regularization. This is the so-called implicit low-rank regularization of DMF:
X(t) w(--i| (t)
(t))()))l)))
(t) R
where L is the depth of MF. wll(t) represents the (-th matrix at the step t during training. The results are given under a mild assumption Tin Section This property helps avoiding dimension estimation and saturation issues. As for the details of the implicit low-rank we will discuss in Section A.2
2.2 ADAPTIVE REGULARIZER
Apart from the low-rank prior, self-similarity is also typical prior. The patch in the image and the rating behavior of users are all examples of self-similarity. For example, there is always a certain degree of self-similarity between the blocks in the image. A classical way to encode the similarity prior to X is Dirichlet Energy (DE) which is formulated as tr(X' LX). But DE will face two problems in applications: (a) is unknown in MC problem, construct L based on incomplete X may induce worse prior. (b) The formulation of DE only encodes the similarity of the columns of X. Other similarities such as block similarity cannot be captured. To address both of these issues, we parameterize L with DNN and replace X by transformed T, (X) to capture the self-similaris flexibly.
The adaptive regularization is defined as
Rw; (T (X)) = Ir (X) L. (W.. , ;;= 1,2, 1,2,,....,
2

---

Under review as a conference paper at ICLR 2022
where L; E Rm is parameterized by W; e Rm To keep the Laplacian prop- erties L, special design for the parameterized structure is important. We design a for- ward neural network which encodes the properties of Laplacian matrix in structure. The de- tails are discussed in A.4 T : TRmxx + mm. transforms X into special domain, which makes the AIR-Net possible to capture various relationships embedded in data. The common choice can be T/ (x) = X which captures the relationship between columns. Regulariza- tion captures the relationship between rows when T: (X) X Especially if (:(X) [vec (block(XX), vec (block(X)), ...... the vectorization of j-th block in X row by row, then the similarity among blocks can be obtained. A natural problem that arises is what the L; looks like during training.
(block(X)),,. where vec (block(X)), E R is
Obviously, Rw, reaches minimum when L, O, and this is called trivial solution. The most citing thing is that when we minimize Equation with the gradient descent algorithm, (L,(W:(t)) converges non-trivial solution. Another expected phenomenon is that Rw; vanishes at the end and will not cause the so-called saturation issue. The saturation issue is a bias term that dominates the overall estimation error due to explicit regularization. We illustrate these phenomena both by theoretical analysis (Theorem in Section 3.2) and numerical experiments (Section 4).
2.3 AIR-NET FOR MC
In this subsection, we will focus our model on the MC problem. We select Ti (X) = X, (x
X , N capture the relationship both in rows and columns of X. Overall, the theoretical
analyses for general inverse problem is based on Equation
min X,W,,,W.
Call = Lv (A(X)) A(X) + X, Rw. (X) + d Rw. (x (xT),
(2)
where X = W w I' w Rw, (X) = XL, (W,)x Rw: (X]
X (W.) X. Specially, our experiments focus on the MC problem which can reform Equation
as follows:
min wW.. W.
Call
Σ (n
Xi
X + A Rw. (X) + de Rw. (x
with 0. 0. algorithm or its variations. We stop the iteration until Rw,(T+11> Rw. < 6 and 8. The recovered matrix is X = w wll- (.)
The parameters Equation
updated by gradient descent
- (actrti)-Rwaccre
Some works which combine implicit and explicit regularization also can be regarded special case of Equation Both the Total Variation (TV) and DE can be regarded as a fixed L. Therefore, the framework of Equation [ also contains DMF+TV (Li al. 2020). DMF+DE (Boyarski al.) 2019a). So far, we cannot see any essential difference between Equation and these models. We will illustrat the amazing properties of the model in the next section.
3 THEORETICAL ANALYSIS
In this section, we will analyze the properties based on the dynamics of Equation 3 Theorem shows that our proposed regularization enhances the implicit low-rank regularization of DMF. The- orem@]show shows that the adaptive regularization will converge to minimum while capturing the inner structure of data flexibly. Although this paper focus on MC problem, the following theoretical ana- lyzes is satisfied for the general inverse problems. As A and A (X*) are fixed during optimization, simplify Ly (A (X*) A (X)) as L (X) below. U., is the (i,j) th entry of U, U. and Uk.: are the k-th column and the k-th row of U respectively.
3.1 AIR-NET ENHANCES THE IMPLICIT LOW-RANK REGULARIZATION
To simplify the analysis, we keep L, and L. fixed. Then the Rw, i = r, e only varies with X. We will demonstrate what the adaptive regularizer brings to the implicit low-rank regularization.
3

---

Under review as a conference paper at ICLR 2022
Theorem 1. Consider the following dynamics with initial data satisfying the balance initialization Assumption I see A.2):
②
(1) OW! Call Cxll((((()) (X(1), t20, 1= 1=0....,
where Call (X) = (x(X) + Xr -ww (X) + Ao -Rw. (X). Then for k = 1.2.... we have
ōx(t) L (oî(t)) 1- (VW)
(4)
2T. (of(()) 3 7c(1).
where X(t) U(t) (t) is the SVD for X (t), W [wio], will w X o. V., 79 (1) U.U. + Lo V 20.
Proof. Directly calculate the gradient of Call at W and utilize Equation 4 will obtain the result. The details of proof can be found in A.3
Compared with the results of vanilla DMF whose order of (t) is 2 2. This Theorem demon-
strates that AlR-Net's 's gT (t) has higher dynamics order which is 3 7. Notice that the adaptive
regularizer keeps (4) 2 ent singular values or than vanilla DMF. Therefore, the AIR-Net enhances the implicit tendency of DMF toward low-rank.
this way, a bigger convergence speed gap appears between differ-
3.2
THE DYNAMICS OF ADAPTIVE REGULARIZER
Now suppose X given and fixed. We focus on the converge property of (T:(W) based on the evolutionary of the dynamics of L, RT.W) vanishes at the end and avoids AIR-Net suffering from saturation issues.
Theorem 2. Consider the gradient flow model, where To (X) k.: = and Te (X)xx > If we
initialize W; (0) = mlm, xma, then W (1) will keep symmetric during optimization. We can get the following element-wise convergence relationship
(m² + +2k;)
(k, E C₁ (k, C2 k=l
Lx(u,)(t) IiNA. $
exp (-D.
(m: 1) .m,; + 2k:s) exp(-pDD.pp
where C1 (Ks,)) | (xT(()).... i # To Tx)
(x))..) } C2 ((x.1) (,, ).. TT: (X).
0,
(k,1) E C1
(k,l) C2 k=1
7,
-E - Karr
LicKn (t) is (ke, 1)-th the element of L,(t), 1 xm; is a matrix of all-one.
2
2
HC,,500]
mk-2k,
D is constant defined in A.4 which equals zero if and only X Imxxn
Proof. We prove this theorem in A.4
This Theorem gives the limit point L and convergence rate of (t).). (k. E C1 (; 0. unless T, (X), = To (X),, or k = I, that is to say, in the end, L; will only think that the exact same columns in T, (X) are related. (ick,)(tt) converges faster when (k, E C2 than (k, () E C, In another word, adaptive regularizer captures the similarity first. This convergence rate gap products a multi-scale similarity which will be discussed in Section 4.1 Additionally, it's not difficult to find Rw: = O, the convergence rate given as follow:
Corollary 1. In the setting of Theorem 2 we further have 2 (m: 2k:) (m; - 1) 1); "anxeexp[-> (D)( 1,2, ...... N.
Rw. (t)
4

---

Under review as a conference paper at ICLR 2022
Proof. We prove this theorem in appendix A.5
According to Corollary lim Rw. + 0. Therefore, the regularization will vanish at the end b++
and not induce the saturation issue.
Remark 1. Notice that we have no restriction on specific T, A or representation of X in the above proof. Therefore, the conclusion in this subsection is general result for inverse problem.
In this subsection, we demonstrate AIR-Net's fantastic theoretical properties. It can both enhance the implicit low-rank and avoid saturation issues. We will verify these properties and the effectiveness of AIR-Net in applications experimentally.
4 EXPERIMENTAL ANALYSIS
Now we demonstrate the adaptive properties of AIR-Net by numerical experiments: (a) L, and Le capture the structural similarity in data from large scale to small scale (Section 4.1); (b) The com- prehensive similarity in all scales contribute to successful MC, therefore the adaptive regularizer is necessary (Section : (c) Because AIR-Net adaptive to data, it avoids over-fitting and achieves good performance. (Section 4.3).
Data type and sampling pattern Three types of matrices considered: gray-scale image, movie rating matrix, and drug-target interaction (DTI) data. Three standard test gray images of size 240 240(Monti et al., 2017) > are included the image type (Baboon, Barbara, and Cameraman). The user-movie rating matrix is Syn-Netflix which is of 150 x 200, and the DTI data has lon chan- nels (IC) and G coupled receptor (GPCR) are shaped 210 x 204 and 223 x respectively (Boyarski et al., 2019b, Mongia & Majumdar 2020). The sampling patterns include random miss- ing, patch missing and textural missing, which are listed in Figure The random missing rate varies in different experiments, and the default is 30%.
X - X ensure the fidelity and the regularization are m. in the same order magnitude, where X and iinn are maximum and minimum of X The d is threshold which we set as 1000 by default. All the parameters in AIR-Net are initialized with Gaussian distribution, which owns zero mean and 10-1 5 as its variance. The Adam is chosen as the optimization algorithm by default (Kingma & Ba 2015).
Parameter seftings We À μ
4.1 AIR-NET CAPTURE RELATIONSHIP ADAPTIVE TO BOTH SPATIAL AND TIME DOMAIN
In this section, will verify the previously proposed theorems. This section provides a few slices of Lp and L. during training to demonstrate what AIR-Net can learn. The heatmap of (,( and La(t) for Baboon / 4000, 7000, 10000 respectively are shown in Figure 1 The according results for Syn-Netflix are shown in Figure 5 in A.I The first row shows the heatmap of (t) and the second one shows the heatmap of (t).
As Figure [ shows, both (t) and Le(t) first appear many blocks (f = 4000). Specially, we sigh two of Lt 4000) out. These blocks indicate that these corresponding blocks columns are highly related. These blocks correspond to columns in which the eyes of Baboon are located, which are indeed highly similar. However, the slight difference between these columns induces the relationship captured by adaptive regularizer focusing the related columns (1 7000), which is similar TV (udiin al., [992). The columns of Baboon are not fully the same. The regularization gradually vanishes (t 10000). which matches the results of Theorem 2 (Figure I Except the gray-scale images, the results on Syn-Netflix give similar conclusion.
These results illustrate that AIR-Net captures the similarity from large scale to small scale. Mean- while, a natural question is raised: does there exist a moment that both L, and L, are captured accurately? If yes. train AIR-Net with these fixed L, and L. to obtain better recovery per- formance. The experiments below show that the L, and L, captured by AIR-Net are necessary for MC.
5

---

Under review as a conference paper at ICLR 2022
0.00
-0
0.00
-0
4.00
-0
(a) Baboon
(b) t=4000
(c) t-700
(d) t=10000
Figure 1: First (column) shows the heatmap of L, (Le) at different t. A darker color indicates a stronger similarity captured by the adaptive regularizer. The (i,j)-th element the heatmap of (I) has darker color than the (i,j")-th element indicate that the /-th is more related to j-th row compared with j'-th row. The area in the middle of the dotted line corresponding to the small block in the figure represents the part of the adaptive positive that considered similar.
4.2 THE NECESSITY OF UTILIZING AN ADAPTIVE REGULARIZER
In this section, the necessity of adaptive updating L, and Le is explored. Let AIR-Net have fixed regularizer, which is adaptive regularizer learned at specific step. The Normalized Mean Absolute Error (NMAE) is adopted to measure the distance between the recovered matrix X and the actual matrix X*:
NMAE
Σ
X
X
X max
X min
(K))eñ
where Si is the complement of Ω. We utilize the regularization captured by AIR-Net at 4000, 7000, 9000 respectively. All of the training hyper-parameters keep the same as AIR-Net. The Baboon under all the three missing patterns are tested.
Figure shuurssshows how the NMAE changes with the epoch of training. AIR-Net, which updates the reg- ularization during training, achieves the best performance all missing patterns. The fixed regular- ization can accelerate the convergence speed of the algorithm. In random missing case, Rw: (9000) and Rw. (9000) is the best fixed regularizer among three time steps while other missing cases are Rw. (7000) and Rw, Rw,(7000) Fixed regularizer based methods will face two problems: (a) How to determine the best step? (b) How to estimate the regularization based on the partially observed matrix before training? These problems are not easy to solve. AIR-Net solves these problems from another perspective by updating the regularization during training. The adaptive property AIR- Net is essential to the effectiveness of AIR-Net.
4.3 AIR-NET ADAPTIVE TO BOTH VARIES DATA AND MISSING PATTERN
Now apply AIR-Net for matrix completion three data types under different missing patterns.
Peered methods The peered methods include KNN et al.
2004), SVD Troyanskaya RDMF(Li et al. 2020) in
et al. 2001), PNMC(MPC (MMCCYYng & Xu 2020). Arraa et al. 2019) and
image type. Here RDMF is replaced by DMF+DD((oyarrs et al. 2019a because it is more suitable in the Syn-Netflix experiment.
Avoid Over-iit F how the NMAE of DMF and AIR-Net changes with the training step. Compared with vanilla DMF, AIR-Net avoids over-fitting and achieves better performance

---

Under review as a conference paper at ICLR 2022
AltAN,, jandom
AlMel, Food
AR let, patch
4x
dinp- 7000 random
deep 4030 random
slcpm4000 Juee
dopp-7000 fioed
step 7000, patch
stop 4000 putch
atop-00000
atop-33000 feedd
step 5000 patch
10
2000
4000
6000
0000
2000
3000
opoch
opoch
(a) Random 30%
(b) Texture missing
(c) Patch missing
Figure 2: Compare adaptive regularizer with fixed regularizer. The NMAE of recovered Baboon under three types of sampling, including random missing 30% pixels, patch missing, and texture missing, respectively. The blue line indicates the NMAE during training vanilla AIR-Net. Take the (t) and (t) out, t equals 3000, 7000, 9000 respectively. The remind three lines in each figure indicate replacing the L, and L. with fixed (t) and Lt(
all the three data types and missing patterns. The Syn-Netflix and DIT data can be found in Figure A
8.42
AR Met
0.40
0.7
0.35
8.30
0.25
0.5
0.5
DNF
8:5
833
030
62
8.5
2008
4033
0300
5000
10000
6243
10000
opoch
apoch
spech
(a)
(b)
(c)
0.00
0.34
0.7
30-1
0:2
0.0
0:0
DMP
20-1
0:08
0:06
30
DMT
2000
02.00
2000
4000
spoch
6003
5033
2000
(C)
Figure 3: NMAE during training of DMF and AIR-Net. All the figures show the NMAE changes with the training step. The first row shows the results of Cameraman with (a) random missing (The proportion of different percentage figures show that the random missing) (b) textural missing (c) patch missing. The second row shows the remind data type with random missing respectively, including (d) Syn-Netflix, (e)IC and (f) GPCR.
Adaptive to data. Our proposed method achieves the besovreed performance most tasks. [ the efficacy of AIR-Net on the various data types. More surprising is that our meth- ods perform better than other methods, which are well designed for the particular data type. The recovered results are shown in Figure|4 In this figure, the existing methods perform well on specific missing pattern data. Such as the RDMF achieved good performance on the random missing case but performed not OK on reminding missing patterns. PNMC completed the patch missing well while obtaining worse results on texture missing. Thanks to the proposed model's adaptive properties, our method achieves promising results both visually and by numerical measures.
7

---

Under review as a conference paper at ICLR 2022
Table 1: NMAE values of compared algorithms with different missing patterns in differ- ent images. The bold font-type indicates the best performance. KNN(Goldberger et al.
2004), SyDeTroyankkaya et al. 200T), PNMC(Yang & Xu 2020), DMF(Aror et al.) 2019).
DMF+DD(Boyyrski al. (2019)), RDMF(Li et al. 2020). AIR-N AIR-Ne((rroposed) Some elements
without value are not suitable for that data type.
Data
Missing
KNN
SVD
PNMC
DMF
RDMF
DMF+DE
Proposed
30%
0.083
0.0621
0.0622
0.0613
0.0494
0.0471
Barbara
Patch
0.1563
0.2324
0.2055
0.7664
0.3025
0.1195
Texture
0.0712
0.1331
0.1100
0.3885
0.1864
0.0692
30%
0.0831
0.1631
0.0965
0.2134
0.0926
0.0814
Baboon
Patch
0.1195
0.1571
0.1722
0.8133
0.2111
0.1316
Texture
0.1237
0.1815
0.1488
0,5835
0.2818
0.1208
70%
0.0032
0.0376
0.0003
0.0008
0.0002
Syn-Netflix
75%
0.0046
0.0378
0.0004
0.0009
0.0003
80%
0.0092
0.0414
0.0014
0.0012
0.0007
IC
20%
0.0169
0.0547
0.0773
0.0151
0.0134
GPCR
20%
0.0409
0.0565
0.1513
0.0245
0.0271
Observed
KNN
SVD
PNMC
DMF
RDMI
Proposed
(a) Random missing
(b) Texture Missing
(c)
Patch Missing
Figure 4: Compared KNN al. 2004 STooTroyaskkaya 2001 PNMC(Yang & Xu 2020), (MrrArora el al., 2019). RDM et al. 2020), AIR-Nee(proposed) on Babara with
three types of data respectively.
8

---

Under review as a conference paper at ICLR 2022
5 CONCLUSION
We have proposed AIR-Net which aims to solve the MC problem without knowning the prior in advance. We show that our AlR-Net can adaptively learn the regularization according to different data at different training steps. In addition, we demonstrate that AIR-Net can avoid the saturation issue and over-fitting issue simultaneously. In fact, the AIR-Net is general framework for solving the inverse problem. In the future work, we will combine other implicit regularization such as F- Principle(Xu et al. 2019) with more flexible Ti for other inverse problems.
REFERENCES
Sanjeev Arora, Nadav Cohen, W. Hu, and Yuping Luo. Implicit regularization in deep matrix fac- torization. In NeurIPS, 2019.
A. Boyarski, Sanketh Vedula, and A. Bronstein. Deep matrix factorization with spectral geometric regularization. arXiv: Learning, 2019a.
A. Boyarski, Sanketh Vedula, and A. Bronstein. Spectral geometric matrix completion. 2019b.
A. Buades, B. Coll, and J. Morel. A non-local algorithm for image denoising. 2005 IEEE Computer Society Conference on Computer Vision and Puttern Recognition (CVPR'05), 2:60-65 vol. 2, 2005.
Emmanuel J. Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foun- dations of Computational Mathematics, 9:717-772, 2009.
Prithvijit Chakrabarty and Subhransu Maji. The spectral bias of the deep image prior. ArXiv, abs/2107.01 125,, 2019.
Kostadin Dabov, A. Foi, V. Katkovnik, and K. Egiazarian. Image denoising by sparse 3-d transform- domain collaborative filtering. IEEE Transactions on Image Processing. 16:2080-2000 2007.
Jicong Fan and Jieyu Cheng. Matrix completion by deep matrix factorization. Neural networks the official journal of the International Neural Network Sociery, 98:34 41, 2018.
Jacob Goldberger, Sam T. Roweis, Geoffrey E. Hinton, and Ruslan Salakhutdinov. Neighbourhood components analysis. In NIPS, 2004.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization.
CoRR,
1es,/14,,,,90,, 2015.
Yehuda Koren, Robert M. Bell, and Chris Volinsky. Matrix factorization techniques for recom- mender systems. Computer, 42, 2009.
Housen Li, Johannes Schwab, Stephan Antholzer, and M. Haltmeier. Nett: Solving inverse problems with deep neural networks. ArXiv, abs/1803.00092, 2018.
Zhemin Li, Zhi-Qin John Xu, Tao Luo, and Hongxia Wang. A regularized deep matrix factorized model of matrix completion for image restoration. ArXiv, abs/2007. 14581, 2020.
2020.
Zhouchen Lin, Minming Chen, and Yuliang Ma. The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices. ArXiv,
2010.
Jiaming Liu, Yu Sun, Xiaojian Xu, and U. Kamilov. Image restoration using total variation regular- ized deep image prior. ICASSP 2019 2019 IEEE International Conference on Acoustics. Speech and Signal Processing (ICASSP), pp- 7715-7719, 2019.
Christopher A. Metzler, A. Mousavi, Reinhard Heckel, and Richard Baraniuk. Unsupervised learn- ing with stein's unbiased risk estimator. ArXiv, 00s//885..153..1 2018.
Aanchal Mongia and A. Majumdar. Drug-targer interaction prediction using multi graph regularized nuclear norm minimization. PLoS ONE, 15, 2020.

---

Under review as a conference paper at ICLR 2022
Federico Monti, Michael M. Bronstein, and Xavier Bresson. Geometric matrix completion with recurrent multi graph neural networks. In NIPS, 2017.
Subhadip Mukherjee, Marcello Carioni, O. Öktem, and C. Schönlieb. End-to-end reconstruction meets data-driven regularization for inverse problems. ArXiv, ab//2100.0333333 2021.
Netflix. Netflix prize rules, 2009. pdf
Adityanarayanan Radhakrishnan, G. Stefanakis, Mikhail Belkin, and Caroline Uhler. Simple, fast, and flexible framework for matrix completion with infinite width neural networks. ArXiv, abs/2108.00131, 2021.
Nasim Rahaman, A. Baratin, D. Arpit, Felix Dräxler, Min Lin, F. Hamprecht, Yoshua Bengio, and Aaron C. Courville. On the spectral bias of neural networks, In ICML, 2019.
Yaniv Romano, M. Protter, and Michael Elad. Single image interpolation via adaptive nonlocal sparsity-based modeling. IEEE Transactions on Image Processing, 23:3085-3098, 2014.
L. Rudin, S. Osher, and E. Fatemi. Nonlinear total variation based noise removal algorithms. Physica
D: Nonlineur Phenomena, 60:259-268, 1992.
O. Troyanskaya, M. Cantor, G. Sherlock, P. Brown, T. Hastie, R. Tibshirani, D. Botstein, and R. Alt- man. Missing value estimation methods for dna microarrays. Bioinformatics, 17 6:520-5, 2001.
Dmitry Ulyanov, Vedaldi, and V. Lempitsky. Deep image prior. 2018 IEEE/CVF Conference on Computer Vision and Pullern Recognition, pp. 9446-9454, 2018.
Zaiwen Wen, Wotao Yin, and Yin Zhang. Solving low-rank factorization model for matrix com- pletion by nonlinear successive over-relaxation algorithm. Mathematical Programming Com- putation, 4:333-361, 2012.
Zhi John Xu, Yaoyu Zhang, Tao Luo, Yanyang Xiao, and Ma. Frequency principle: Fourier analysis sheds light on deep neural networks. ArXiv, abs/1901 06523,65333 2019.
Mingming Yang and Songhua Xu. A novel patch-based nonlinear matrix completion algorithm for image analysis through convolutional neural network. Neurocomputingg 389:56-82, 2020.
A APPENDIX
A.1 EXPERIMENTS RESULTS
In this section, place the experiments mentioned before. Figure J/hwss shows the heatmap of L, and Le learned by adaptive regularizer. Eventually, adaptive regularizer obtain the L, and Le which are highly similar to real L, and L. in first column.
Figurer]shor shows the NMAE of Syn-Netflix, IC and GPCR during training, respectively. This experi- ment result also shows the ability to avoid over-fitting.
A.2 INTRODUCTION OF DMF
Assumption 1. Factor matrices are balanced at initialization, i.e..
wi++] (0)wl++1(0)) w w (o) (0), 1= 1=0,.., 2.
Under this assumption, Arora al. studied the gradient flow of the non-regularized risk function Ly, i.e.,
a
w(((()) Llee Lx (X))). 120. 0. 1= O....,
.....,,L L
(5)
10

---

Under review as a conference paper at ICLR 2022
Realistic relationship
Step-5000
Step=7000
Step= 1tep=10000 10000
34
6004
uSCTS
RATRR PROODEE REBRERR
-12
items
-03
Figure 5: The first column shows the realistic relationship among columns and rows respectively.
The remind three columns are the Laplacian matrix learned by AIR at different step.
Syn-Netflix
Ion channels
protein-coupled receptors
244
120
144
178
122
204
NERTRRR 2ORCE3
3.1
0.9
3.16
0.5
3.10
OFF
0:55
3.00
694
300
633
306
687
45-NKC
10000
20008
300000
40000
500CE
4005
0830
8000
10000
4300
5008
8000
20099
opcch
Figure 6: The first row shows the real data of Syn-Netflix, IC and GPCR respectively. The second row shows the corresponding NMAE during training.
11

---

Under review as a conference paper at ICLR 2022
where the empirical risk Cy can be any analytic function of (t). According to the analyticity of Cy, (t) has the following singular value decomposition where each matrix is an analytic function of t:
(() = U()S(VV) (1):
where (t) E R.m.min(m..), S(()) E mmin(m.n).minff mmm and V(t) E mmmin(m,,).. are analytic functions of i; and for every i, the matrices (t) and (tt) have orthonormal columns, while S(t) is diagonal (its diagonal entries may be negative and may appear in any order). The diagonal entries of Stt), which we denote by (t)....... m'iufmmn (t), are signed singular values of X (t). The columns of (t) and (t),, denoted by U. miin(m..) (t) and Vi (t), (t),.... V (m..) (t), are the corresponding left and right singular vectors respectively. Based on these notation, Arora derive the following singular values evolutionary dynamics equation.
Proposition 1 ((Arora et al. 2019, Theorem 3)), Consider the dynamics Equation 3 with initial data satisfying Assumption
Then the signed singular values on of the product matrix X X()) evolve
by:
o% (t) = - (o2(t)) 1- UXC k == 1 min nm.
(6)
If the matrix factorization is non non- -on-eeenerrte,, i.e., has depth L 2 2, the singular values need not be signed (we may assume (t) 2 0 for all t
Arora et al. claimed the terms (o2(t)) - enhance the movement of large singular values, and on the other hand, attenuate that of small ones. The enhhancemen//tteemaation becomes more significant as L grows.
A.3 PROOF OF THEOREM 1
We first give the details of the proposed adaptive regularizer with a iterative definition:
Rw; (Ti()) = ir (x) (x):
L; (A) 1m, xm,)) ) Im. - A
A₁ A, (1m, xm, Im.))
crp(W; + W
A; = [eexp( WWill
Theorem 1. Consider the following dynamics with initial parameters satisfying Assumption 7
w OWN fall (X()), 12 0, 1=
where faul (X) = Lx X) + X, Rw. (X) + + Rw. (X). Then we have for any h: 1, 2,
(f)) dx(()= = L (o)(t)) 1- (V))x(X()), U.NV)
2T. (o((1))) 3 Tx(1);
where X(t) ((t)))())(())) (t), X === E,, V.T (t()) U. U
V.L.V. 2
Proof. This is proved by direct calculation:
Otr (2, -X L, X + de XL,XT)
Vw (A, Rr + da Re)
0X
= = L,, X + 2). XL.
=2dr. L, Σ o Un V + 2>c
Jo.U.N D.....VV......
Note that
V V₂) = (U... Uz} = 5as { 1, = s
0. 8 +
12

---

Under review as a conference paper at ICLR 2022
Therefore
U. (Vw (Ar RR + do Rc)) V = =20x(1, U, Ao V.
=20x7k(t),
where the term (t) (0x U. L, de V.I.L.V.A. 2 Furthermore, according to Equation 6 we have V - 1-1 (V)
Finally, according to (t) owN Lalil (x
(x(t) (t)), have
dx(t)= - -L 1-1 (W (X) ( 2L (o2(1)) 3-2 (x(t).
A.4 PROOF OF THEOREM 2
Proposition 2. Vw. (Rw; (X)) = 2C O A; -0-22 2tr (CA() A where A
exp W.
A.
Tepp Woll
A + A! and C = mm;xm (x))))(((x)) の Im:) (X) (x)
Proof. We denote X = (X) E xm,, then we consider trr (X L,X)
(X)
d tr X [
=tr [d L; XX
=tr [(dA, 2 (1m;xm; 1m,) 1m, Xm, 1 In Xxx
dA, 2 (1m;xm; - -m,)) XX
=tr (xXT)² (Im, & (dA; ④ (Im mi Xmpxm; Imm)) xm,,))
(xXT)" ((1mixm; - Lm,) ④ dA.))
=tr (XXT O Im.)' dA; (100mmm Im:) Xm;
(xx (1mixmi Imm)) dA,
=tr ((XX Im..) Impxmm) (dA, @ (Im;xm; m),))
-XXT (1m;xm, Im.)) dA.
=tr [((xx) Im.) xmx) (mmxxm Imm)) - (1mxxm, (mm) )) dA,
=tr [(xx ② 1mm) 1mxxm. XX dA:]
13

---

Under review as a conference paper at ICLR 2022
We denote C (XX) o Im:) 1mxxm XX" 1 =1m, exp (W,) 1m then
d d(tr [xX)]
=tr (CdA),
tr [C (Sw. exp(W, W;)) o dWW + +W())
SW:
-C (ITh, (ex @ dW;) 1m.) exp( + W.
=tr (r([ (A, @ (W; + W]
tr [mm (exp(W,) o dW;)l tr [C eap (W; + W:))
W:
-ir CC (A, 0 W
1
Ir 1r((1mm Xm;; 3 exp (xp( ir [C erp (W; W;
Sw.
=tr (C (A, + W/ )) ir A:) A,dW,
=ir ((CT @ A:) + + @ tr A,) A (W,
Therefore,
Ww, L,X) = (CT , A.) + CC O A, - tr (C A
= 2C A, 2tr (CA.) A
Notice that X = (X) Rm, the proposition is proved.
Theorem 2. Consider the gradient flow model, assume
(x ki 1 and Te (X)),, k. > O, we we
initialize W; (0) = mm, then W (f) will keep symmetric during optimization. We can get the element-wise convergence relationship
L((k,)(()) Li(Aoo {
(m, + 2k:) exp(-D exp (-D.
(k,1) E C₁ (k, C2 k=
t).
(m+ -1-1 1)- (m² + 2k:s exp( (DD -D.t),
where C1 { (1,,0) | 1K l To (X) C2 { (k. 1, (X) , = (X)
0,
(k,1) E C1
(
7:
E L Li
k=l
(() is the element of Li(l) at the k-th now and 1-th column, 1m; xm, is all one elements matrix. 7 Ko. 2k," D is constant defined in A.4 which equals to zero if and only
2
X 1,,xn,
Proof. We rewritten the gradient in proposition 2 with element wise formulation:
WTaak (t) (2Ca(t) 4C*,) (t),)))).
where Ca(t) = (CA() and the sub index denote the element in matrix.
With the assumption that (x))
> 0, we have 0 To (X) (x) k.l < 1. Therefore Ck (x) k. -TT (x)
ki
and (x()) kil
A. 20
exp(W...) and specially Ck.k = 0, as A(((.)) Toxp(W:)ll.
> we have
Ca(t) = (C((
Σ (L)4(())))))
k=1.E1
14

---

Under review as a conference paper at ICLR 2022
Denote Cj min C.,I, we have C₁,i S Cka and then consider 1.l
WTaee, (1) WT
= =2Ca(t) (A (t) A ((k))(t)) 4 (Cr,AA(a,))))))) - Ca.A((..)
As we initialize (0) = Elmixms therefore A A1,1) (0) = 1 I, Therefore WT.. (0)
mi
WTO. (0) = -4
=4 -C -Cas) (l(),)(0) = m. (ap Cz.) 2 O. Then we have
WTALL (1) 2 WT (1) and A' A ((h.f) (1) 2 A'(x,1(()) (t), the equal is token and only if =
or Cz.1 = Cx.I- Furthermore, WTi (1) - WT (1) 2 - (Ca. Cr..) Al (0), then
WT.. (t) - WTa., (t) 2 Disix."" t, where Diii, = -4 (Cas Ok.) AlCx.D) (0) 2 0. Next, we consider
exp(W ((R.)))
A (R..)) (1) = Texp( W WT... II
exp( ( (((k.))
Σ (W (WTTa.
Texp(WT.nak WT kJ
k.
Σ
eap k,1
(-DRRAa
As CR 0 and Cx, 2 0, therefore Ck, mmn Cx,==0. It is not difficult to show that Ct,1 0 if R,l
and only if Tx i. Ti (X) If {
C =0
m, + 2k, then when Cg.i 0, A' s(k.i) (t) 2
m,+2k,+ where Eg, (+0)) = 0. Notice that
Σ
Al (t) 1, we have
k,
1 m; + 2k, + (t)
S
(k..)) (t) 1
m; + 2k:
Therefore, A ((A.)) (+00) {
(X) iM # To (X) ).
Furthermore, A =
.T (X), ).k = (X).
mc+2k,
{
0 To (X)., # Te (X)...
2 .k..) .m;+2k; 7/ Ai(u.)) (+00)=
2
AAcording to the defini-
7 Ti (X).x = T+ =X))
tion of Lis
l: + 1, To (X)
1 + T (X)) .
((0 = (++))=
1: + L, T. X ) T (X). )
E 1 ((ge)
k: ==1
Until now, we have prove that the adaptive regularization part of AIR-Net will convergence at the end. That is the upper bound of Lix.,) L (() Next we will focus on the convergence rate of AIR-Net. We discuss the rate under the three cases in the aforementioned formulation separately.
We simplify the notation
C (k; k k (T,T(()),. + (X))..) C2 = {(k, ( To (X)
furthermore
before continue.
Then
the formulation is simplified as
0
E Ci (k, (k, E Cz
?
k=1
15

---

Under review as a conference paper at ICLR 2022
If (k, C2 or k denote D min Da.,, according the definition of Et,((), have (t) 1 exp(-D-1
Aiuu - A((K))(t =2 m4 + 2k:
m, + 2k; + (t,
Et,,(t)
- mm + 2kx))
(m(m-11) --pp--D.1
2 2
(m, + 2k;)
eepp (-D.
Specially, when (k, C2 we have
Lick,) [(( = Aijk.1 Asc,,((t) se S cc
If E
Lin (t( = -Aii Asu..)(t) = (t)
W
E
(t)
Σ
(()
Y (m: + +kkk)
E
A
(I' (')cecc
Σ (W)D))C
(7 (i())r((()
Σ
h (s))
Σ
Ai A s (m, + 2k.) exx(-xx t)
(MPD)CC
kf== 1
Lann Ls(k))(0
Σ
(Eiree) - Latha)((1) S (m;-1) - 1) (m; + 2k;) exp(-D
=
I' 1A
A.5 PROOF OF COROLLARY
Corollary 1. In the setting of Theorem 2 (m, 2kx) (m; 1) m, exp(-Dt).
we further have
s Rw, (t) S
Proof.
Rw:(t) = Σ (t)(n)) [TT( xx())
22 Σ LigD (1)(t) $ my (m: - 1) (m4 2k:) exp(-Dt)
16


Reviews:
[{"review_id": "UXhTTSlYCw", "reviewer": "Reviewer_B6ib", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Quality:**\n\n- Strengths: - The proposed method works fairly well empirically, beating other baselines using implicit regularization and also more traditional approaches.\n\n- Weaknesses: - The paper can be quite hard to follow, see the clarity section below. -  Overall, the framework seems incremental. There does not seem to be a big distinction from [1], aside from parameterizing the dirichlet energy with learnable weights. The theoretical contributions appear minor and mirror those previously established in [2]. \n\n**Clarity:** The paper was hard to read and contained a number of typos. I have noted some here, but the manuscript contains others:\n- page 1 abstract: “requires a regularization” -> “requires regularization”\n- page 1: “over-parametric” -> “overparameterized”\n- page 2: “The low-rank” -> “Low-rankness”\n- page 2: “Furthermore, We” -> “Furthermore, we”\n- page 3: The functionals $\\mathcal{R}_{W_i}$ are missing the trace $\\text{tr}( \\cdot )$.\n- page 3: “Another expected” -> “Another unexpected”\n- page 5: “Specialy, we sigh two of $L_c(t=4000)$ out”\n- page 6: “Air-Net Adaptive to Both Varies Data” should “varies” be “varying”?\n- page 6 Figure 1: “the $t$-th row” -> “the $i$-th row”\n- page 7: “reminding missing” -> “remaining missing”\n\n**Novelty and significance:** The work seems to be an extension of [1], which also employed a deep matrix factorization approach to solve matrix completion problems and incorporated the dirichlet energy as an explicit regularizer. In that case, however, the laplacian was not learned, which seems to be the crucial difference. Some components of the theory is also borrowed from Arora et al [2].\n\n**General comments:**\n\n- At the top of page 3, it says that the structure of the network parameterizing the Laplacian matrix is discussed in A.4, but it appears to actually be in A.3. There is also no discussion on why the network is chosen in this particular fashion. It would be good to talk about why this network structure is used, e.g. the use of a softmax-type parameterization. Also, under this parameterization, is it even possible for the learned $L_i = 0$, the trivial solution?\n- It feels misleading to say in Remark 1 that Theorem 2 requires no restriction on $\\mathcal{T}_i$ or $X$. The first assumption is that all columns of $\\mathcal{T}_i(X)$ are unit normed and the entries are positive. If, for example, $\\mathcal{T}_i(X) := X$, then this means that for the result to hold, the columns of $X$ are unit normed and all of its entries are non-negative.\n- The matrix $C_{k,l}$ should be defined in Theorem 2, since it arises in the definition of $\\gamma$.\n- I am a bit puzzled by Figure 1. This seems to indicate that as time progresses, the network learns that there should be less and less similarity between rows/columns, as indicated by the lack of dark regions as $t$ increases. What is the intuition for this? Shouldn't some notion of self-similarity be learned instead?\n\n[1] Amit Boyarski, Sanketh Vedula, and Alex Bronstein. Spectral geometric matrix completion. MSML 2021\n\n[2] Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. NeurIPS 2019", "summary_of_the_paper": "In this manuscript, the authors consider matrix completion problems. Leveraging recent advances on implicit regularization in (deep) matrix factorization problems, a new architecture for matrix completion is proposed. Specifically, the authors parameterize the unknown low-rank matrix as a deep linear network, which has been shown to exhibit a low-rank bias when learned via gradient descent. Additional regularization terms based on the Dirichlet energy are added to encourage other structural priors in the recovered solution, such as self-similarity between columns or blocks. The underlying Laplacian matrix is parameterized by learnable weights. The authors analyze the dynamics of gradient flow applied to their optimization problem and show empirically that this approach improves performance in certain settings.", "summary_of_the_review": "Overall, while the proposed work shows empirical promise, it seems to be an incremental improvement over previous work. The readability of the manuscript can also be significantly improved. Based on these factors, my current score is a 5. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Rk1emqKK0lT", "reviewer": "Reviewer_Bmxi", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- A general framework is proposed for studing matrix completion problems with regularization\n- A good specific choice of implicit regularization based on the Dirichlet Energy with neural networks is proposed\n- Theoretical analysis of the proposed algorithm indicates the expected system dynamcis\n- Experimental evidence shows improvement on a variety of matrix completion tasks\n\nPros:\nThe results are interesting and compelling; indeed, there is clear improvement in a variety of tasks, and the dynamics of the reconstruction match the expectation in theory. It is also useful to draw links to other works through the more general formulation. Effective heuristics for regularization parameters are chosen so that they do not need to be tuned. The DE regularization has an intuitive impact.\n\nCons:\nThe experiments are rather limited to a small set of test cases (three images only) and it is not clear if the results are consistent across a larger data set.\n\nThere are also details missing, for example, a better explanation of the construction of the Laplace matrix in the DE regularization, and why it was chosen. Also, it is not clear that the experiment using fixed L at different iterations is so useful. Could instead the ideal L be used calculated from the fully sampled matrix?\n\nIt is also not entirely clear what value is added by generalizing other methods based on a very generic optimization equation (that essentially can capture any optimization problem). In particular, the main focus of the paper seems to be in the specific choice to regularize the DE of both the rows and the columns. However, no comparison is made to a situation where only one or the other is used. It is also not clear if overfitting can become an issue with enough iterations.\n\nAs a general comment, the writing is not always clear and could be improved to help clarity. There are also small errors, for example I believe \"t-th row\" in Figure 1 caption should say \"i-th row\".\n\nBased on the preliminary results, I believe the paper is marginally below the acceptance threshold.\n\nThe justifications for this decision is the limited set of experiments justifying the choices made. Specifically, the value of adding the row- and column- DE regularizers, and the interplay with deep matrix factorization. In addition, the justification and explanation of the construction of Lr and Lc.\n\n", "summary_of_the_paper": "This paper studies the problem of matrix completion using neural networks and deep matrix factorization as implicit and explicit regularization. The paper proposes a general framework and studies a specific case, namely, when the regularization is a form of Dirichlet Energy on the rows and columns of the matrix, and the matrix is formed as a product of L matrices. The results indicate improved performance of matrix completion under a variety of corruption methods and for a number of data sets.\n", "summary_of_the_review": "In summary, the paper proposes a nice combination of implicit and explicit regularization for matrix completion using a deep matrix factorization and penalty on the DE of the rows and columns. The results are compelling, but some of the choices made are not fully justified or analyzed.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "HwZE6mqbJCY", "reviewer": "Reviewer_MBKQ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "##########################################################################\nSummary:\n\nThis paper proposes a generalization and extension to deep matrix factorization as presented in the former paper from [Arora et al, NeurIPS 2019]. The extension allows more complex model which include inverse problems. The generalization part is build on a \"vanishing\" regularization which leads to better dynamics and convergence. These results are given by a theoretical analysis which highlight the effect of the proposed model. Finally the experiments illustrate the advantage of the model compared to state-of-art methods.\n\n\n##########################################################################\nReasons for score: \n\nDespite the interesting results in both theory and experiments, the presentation of the paper is too confused for publication (see cons below). Too many important details are in the appendix.\n\n##########################################################################\nPros: \n\n* The theoretical results are very interesting as they greatly improve the previous ones on deep matrix factorization.\n\n* The Dirichlet Energy regularization term leading \"vanishing\" prior on the data is intriguing and a theoretically sound.\n\n* The model is extensive to inverse problems and others. Important for application in image processing...\n\n* The experiments shows clearly the advantage of the proposed model.\n\n##########################################################################\nCons: \n\n* Eq. (1) is an optimization problem not a model. The true model is hidden in the different part of the appendix (A.2 for the matrix factorization, A.3 for the regularization). Thus it is hard to understand (or even read) most of the paper since we have to switch between all the pages to catch the important pieces of the model.\n\n* The theorems are very difficult to read as important information are in the appendix. Theorem 1 rely in on assumption which should be add to the text (I think there some place left). Theorem 2 is based on a regularization model which is only described in the A.3.\n\n\n##########################################################################\nQuestions during rebuttal period: \n\nPlease address and clarify the cons above \n\n#########################################################################\nSome typos and others: \n\n* Some sentences are confusing or need to be reshaped.\n    - At the end of section 2.1, the details of the implicit low-rank are presented. It not a discussion.\n    - In Theorem 2 at the end, I would rather write: \"D is a constant which equals [...]\".\n    - End of page 4, \"it's not difficult to find $R_{W_i^*}=0$\" is confusing, I would rather write that \"$R_{W_i^}(t)$ converge to 0\".\n", "summary_of_the_paper": "This paper proposes a generalization and extension to deep matrix factorization as presented in the former paper from [Arora et al, NeurIPS 2019]. The extension allows more complex model which include inverse problems. The generalization part is build on a \"vanishing\" regularization which leads to better dynamics and convergence. These results are given by a theoretical analysis which highlight the effect of the proposed model. Finally the experiments illustrate the advantage of the model compared to state-of-art methods.\n", "summary_of_the_review": "This paper presents interesting results in both theory and experiments. Howeever the presentation of the paper is too confused for publication. Too many important details are in the appendix.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6GCzRaDB_Vg", "reviewer": "Reviewer_Untt", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strengths: \n1. Theoretically analyzing the gradient flow of the training loss to understand the properties of the proposed approach\n2. good experimental results.\n\n## Weaknesses\n1. The paper is not easy to follow due to complicated notations. Also, it lacks a detailed description of some important concepts. For example, the end of the introduction mentions that $L$ in the adaptive regularizer is parameterized with DNN. However, I didn't find any detailed description for this except for the formulation $L_i(W_i)$ right after eq. (2). What is $L_i(W_i)$? \n\n2. Without the detailed expression of $L_i(W_i)$  for the adaptive regularizer, the training loss in eq. (2) appears not well-posed. Particularly, the regularizers $trace(X L_r(W_r) X^\\top)$ and $trace(X L_l(W_l) X^\\top)$ are not bounded, i.e., they can go to negative infinity. Right after eq. (2), it says $R_{W_r}(X) = X L_r(W_r) X^\\top$ which I think is not correct. \n\n3. Theorem 1 analyzes the gradient flow when the regularizers are fixed, while Theorem 2 analyzes the gradient flow when the matrix is fixed. However, in practice, the entire training loss is minimized simultaneously, but no theoretical analysis is provided for this case.  With the regularizers fixed, Theorem 1 is similar to the existing results on analyzing the dynamic flow of deep matrix factorization, e.g., [Arora et al. 2019]. Difference and novelty compared to the existing work should be discussed.\n\n4. The two theorems lack sufficient discussion to help the readers understand the main results. For example, what is the role of $L_r$ and $L_c$ in Theorem 1? How do they affect the results? The set $C_2$ in Theorem 2 consists of identical rows or columns, which seems empty in practice. If this is the case, Theorem 2 implies that the adaptive regularizer $L_i$ becomes a diagonal matrix. What is the role of the regularizer in this case? \n\n5. Theorem 2 requires the matrix $X$ has positive elements, which is a very strong assumption and may not hold in practice. ", "summary_of_the_paper": "This paper studies the matrix completion problem where the goal is to recover the matrix from partially observed elements.  The proposed approach involves parameterizing the unknown matrix by deep matrix factorization and adaptive regularizers that are parameterized with deep neural networks. The authors studied the Adaptive and Implicit Regularization of the proposed approach which is called AIR-Net. Experiments are provided to demonstrate the effect of the proposed approach. ", "summary_of_the_review": "Overall, based on the detailed description above, the main contribution of this paper seems limited as the gradient flow of deep matrix factorization has already been studied. Also, the form of the adaptive regularize is not clear and the main results lack sufficient explanation. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: There is a consensus that the contribution is not strong enough to effectively
argue for an important novel lead which would justify publication at ICLR. 

Authors have also not engaged with the reviewers.

For these rejections, this paper cannot be endorsed for publication at ICLR 2022.
Decision: Reject