Neuron-Enhanced AutoEncoder Matrix Completion and Collaborative Filtering: Theory and Practice
Authors: Jicong Fan
Rui Chen
Zhao Zhang
Chris Ding
Venue: ICLR 2024 poster (2024)
Keywords: autoencoder
matrix completion
collaborative filtering
Primary area: general machine learning (i.e., none of the above)

Abstract: Neural networks have shown promising performance in collaborative filtering and matrix completion but the theoretical analysis is limited and there is still room for improvement in terms of the accuracy of recovering missing values. This paper presents a neuron-enhanced autoencoder matrix completion (AEMC-NE) method and applies it to collaborative filtering. Our AEMC-NE adds an element-wise autoencoder to each output of the main autoencoder to enhance the reconstruction capability. Thus it can adaptively learn an activation function for the output layer to approximate possibly complicated response functions in real data. We provide theoretical analysis for AEMC-NE as well as AEMC to investigate the generalization ability of autoencoder and deep learning in matrix completion, considering both missing completely at random and missing not at random. We show that the element-wise neural network has the potential to reduce the generalization error bound, the data sparsity can be useful, and the prediction performance is closely related to the difference between the numbers of variables and samples. The numerical results on synthetic data and benchmark datasets demonstrated the effectiveness of AEMC-NE in comparison to many baselines.

Published as a conference paper at ICLR 2024
NEURON-ENHANCED AUTOENCODER MATRIX COM- PLETION AND COLLABORATIVE FILTERING: THEORY AND PRACTICE
Jicong Fan Rui Chen Zhao Zhang Chris H.Q. Ding'
1 School of Data Science, The Chinese University of Hong Kong, Shenzhen, China Shenzhen Research Institute of Big Data, Shenzhen, China
"School of Computer Science & Information Engineering, Hefei University of Technology, China fan jicngee cuhk. edu. en 1160100188 Belink. cuhk. edu. cn es2 aszzhange gmail. com chrisdingseuhk. edu. cn
ABSTRACT
Neural networks have shown promising performance in collaborative filtering and matrix completion but the theoretical analysis is limited and there is still room for improvement in terms of the accuracy of recovering missing values. This paper presents a neuron-enhaneee and applies it to collaborative filterin.. Our AEMC-NE adds an element- au- toencoder to each output of the main autoencoder enhance the reconstruction capability. Thus it can adaptively learn an activation function for the output layer approximate possibly complicated response functions in real data. We provide theoretical analysis for AEMC-NE as well as AEMC to investigate the general- ization ability of autoencoder and deep learning matrix completion, considering both missing completely at random and missing not at random. We show that the element- wise neural network has the potential reduce the generalization error bound, the data sparsity can be useful, and the prediction performance is closely related to the difference between the numbers of variables and samples. The nu- merical results on synthetic data and five benchmark datasets demonstrated the effectiveness of AEMC-NE comparison to many baselines.
autoencoder matrix completion (AEMC-NE) method
INTRODUCTION
Recommendation systems (Adomavicius & Tuzhilin 2005) aim to provide personalized recommen-
dations based various information such user purchase records, social networks, user features, and item (or product) features. One important technique used by recommendation systems is collab-
orative filtering (Billsus& & Pazzani 1998; Mnih & Salakhutdinoy 2008 Koren et al.) 2009 Zhhng
et al. 2019) based on matrix factorization or matrix completion (Srebro Shraibman 2005: Candès
& Recht] 2009 Hu et al. 2012) Vandereycken 2013] Shamir & Shaley-Shwartz] 2014 Chen al.
2014 Sun & Luo 2015;
Nie et 2015] Fan et al. 2019; Fan 20226). In collaborative filtering (CF) problems or recommendation problems more generally, the rating matrices are usually highly
incomplete (Resnick et al. 1994 Breese et al., 1998 Koren et al., (009) and the missing rates are
as high as 0.95, due the naturally scarce interaction between users and items. Matrix factorization or completion based CF methods usually exploit the potential low-rank structure of the incomplete rating matrix to recover the missing values. The low-rankness can be obtained by low-rank factor- ization (Koren et al. 2009), nuclear norm minimization (Candès & Rechi 2009). or Schatten-p quasi norm minimization Faan et al.) 2019). Particularly, [Lee et al. (2016) proposed a method I.LRRMA that approximates the rating matrix as weighted sum of few low-rank matrices. LLORMA outper- formed low-rank matrix completion methods collaborative filtering, which indicates that rating matrices in real applications may have more complicated structures rather than single low-rank structure. There have been a few works of high-rank matrix completion (Eriksson et al. [012 Yang al. 2015 Elhamifar] 2016 Fan & Chow 2017;; Ongie et al. [017 Fan & Udell] 2019 Fan al. Fan 2022a). These works often assume that the columns of a given data matrix are generated
2020
* *Corresponding author

---

Published as a conference paper at ICLR 2024
from union of subspaces low-dimensional manifolds. However, these works haven't 't shown the effectiveness of high-rank matrix completion methods in CF.
The success of neural networks and deep learning in computer vision and natural language process- ing inspired researchers to design neural networks for CF (Salakhutdinov et al,, 2007|] Dziugaite &
Roy 2013 Sedhain et al. 2015
Wu et al. 2016 Zheng et al.] [ |ee et al. 2017 van den Berg et al. (020). For instance, Salakhutdinov et al. (2007) proposed restricted Boltzmann machines (Hinton et al. 2006) based CF method called RBM-CF, which
et al. 2017 Fan & Cheng, 2018
showed high performance in the Netflix challenge (Bennett & Lanning 2007]. Sedhain et al. (2015)
proposed AutoRec, an autoencoder (Hinton & Salakhutdinov/ [2006] Bengio et al.] (007) based CF method, which predicts unknown ratings by an decoder model a W20 (WI)), where a denotes the incomplete ratings on one item or of one user and W1, W2 are weight matrices to
optimize. AutoRec can be regarded as an autoencoder-baset matrix completion (AEMC) method. AutoRec, or AEMC equivalently, outperformed I.LORMA slightly on several benchmark datasets (Sedhain et al.) 2015). Zheng al. (2016) proposed method called CF-NADE, in which parameters are shared between different ratings, and it achieved promising performance in several benchmarks. He et al. ( proposed to use a neural network to learn the interaction function between users and items. The method showed some improved performance over the baselines in the setting of implicit feedback (Rendle et al., 2009) but its performance in the setting of explicit feedback of benchmark datasets is still unknown even today (Rendle et al., 2020) Xu et al.] (002T) Muller et al. (2018) proposed a kernel-based reparametrized neural network, in which the weight between two units is set to be a weighted kernel function of the location vectors. The method works well in data visualization and collaborative filtering. Interestingly, Yi et al. (2020) found that the ex- pected value of the output layer of a neural network depends on the sparsity of the input data. They proposed a simple yet effective method called sparsity normalization to improve the performance of neural networks with sparse input data such as the highly incomplete rating matrices.
similarity
worth mentioning that existing autoencoder-baa based CF or matrix completion methods such as (Sedhain et al. 2015 Wu et al.] 2016; Muller et al. 2018 Yi et al. (0200) use linear activation function in the output of the decoder, i.c., E = WL W where WL denotes the weights of the output layer and h denotes the features given by the last hidden layer. Thus, these methods are under the assumption that the ratings are linear interactions between user features and item features, though the features can be nonlinear. Such an assumption may not be true not optimal in real problems, especially when the data are bounded (e.g. images) or are collected by sensors (e.g. medical and chemical sensors) with nonlinear response functions. We suspect that the rating values given by users on items are from some nonlinear response functions because humans have complex emotion or decision curves (LeDoux 2000 Baker 2001). A naive method to incorporate nonlinear interaction is using nonlinear activation functions such as the sigmoid function (with rescaling) in the output layer of the decoder, which however has much lower performance than using a linear activation function. That's why existing autoencoder- baseed CF methods use only linear activation function. Note that a pre-specified activation function for the output layer of the decoder may work on specific data but may be far away from the possible optimal choice.
Note that collaborative filtering is a special case of the general missing data imputation problem that also covers many other tasks such as image or video inpainting and missing value imputation as a preprocessing step for further data analysis. Although neural networks and deep learning have shown promising performance in collaborative filtering and other missing data imputation tasks YYon et al.) 2018, Mattei & Frellsen 2019), the theoretical analysis is very limited. It is very necessary and crucial to provide theoretical guarantees for neural networks and deep learning based collaborative filtering and missing data imputation.
Contribution. We present novel matrix completion method AEMC-NE, which is enhanced autoencoder approach to matrix completion and collaborative filtering. AEMC-NE is composed of two different neural networks, one is an autoencoder reconstruct the incomplete rating matrix, while the other is an element-wise neural network to learn an activation function adaptively for the output layer of the first autoencoder. We provide theoretical analysis for AEMC-NE as well as AEMC, considering both missing completely at random and missing not at random. Specifically, we prove that the element- wise neural network has the potential reduce the upper bound of the prediction error for the unknown ratings. We also prove that the data sparsity is not problematic but useful. Further, we demonstrate the effectiveness of our AEMC-NE on synthetic data and five benchmarks including MiriieLens-1O0Ks MovieLens- 1M, MovieLens 10M, Douban, and Flixster.
2

---

Published as a conference paper at ICLR 2024
2 NEURON-ENHANCED AEMC
Suppose we have an incomplete data matrix X = (x], (0,, .2,..... .,)) E RR (e.g. a rating matrix), where m is the number of variables, n is the number of samples, and the index set of observed entries is denoted as S. Our goal is to predict the missing entries of X, i.e. {Xij (i, E [m] [n]] s).. One approach is to fill the missing entries with some values (e.g.. mean or zero) temporarily and then construct an imputation model. Specifically, let X be the temporarily imputed matrix, where X,, Xij for all
(i,j) E S, we learn a nonlinear function f R R such that
Σ 8 3 (z.- [ā,)) || is small as possible, where 8; is a binary vector denoting whether the corresponding element in æ; is observed or not. The problem is formulated as
minimize fEF
S @ (X (xx-((x)) f(x))
(1)
where S = ($1, .nn)...8)). C denotes the Hadamard product, f is performed on each column of X separately, and F denotes a hypothesis set of functions. We have infinite choices for F. For example, F can be set of functions in the form of neural network with some parameters W E W, where W denotes a set of matrices under some constraints. In this case, problem (1) defines denoising autoencoder or stacked denoising autoencoders (Vincent et al. 2010), where the noises are introduced by filling the missing ratings with zeros. Note that f can be general neural network and is not necessarily an encoder-decoder architecture.
Let be autoencoder with linear activation function in the output layer. Then becomes
minimize W1.W2
||S @
X W20 (Wi + A (IIW1 [12- + 1| 1?-),
where W1 E Rd and W2 E mxd are weights matrices to learn and is a nonnegative constant to control the strength of regularization. We have omitted the bias terms for simplicity. a denotes an activation function such as ReLU (xr) max(x, 0) and Sigmoid o (xx) 1/(1 + exp(-xr)
Note that (2) is exactly the basic model considered by (Sedhain al. 2015 Wu et al.) 2016 Muller et al. 2018 Yi et al. 2020). Once ( is used and d is much smaller than min m, n.), the following assumption is made implicitly: X can be well approximated by the low-rank matrix W2 (W However, this assumption does not always hold in real applications. Consider data generating model X = h ('), where h R² + IR' is an element-wise nonlinear function and A' E Ig B' E Rdxn may be generated by some nonlinear functions. If the nonlinearity of h is high, X cannot be well approximated by rank-d matrix. This analysis indicates that if the element-wise nonlinearity in generating X is strong, 2 should use a large to ensure a small training error.
The element-wise nonlinearity widely exists in real data. For example, in imaging science, the intensity of pixels are nonlinear responses of photoelectric element to the spectrum. In chemical engineering, many sensors have nonlinear responses. In biomedical engineering, the dose-responses are often nonlinear curves. Hence, in collaborative filtering, the ratings may be nonlinear responses to some latent values, according the studies on response curves in neuroscience and psychology [LeDoux 2000) Baker 2001). Therefore, instead of (2). one may consider the following problem
minimize W,
||S o (x (W
+ > WI + 11222)
(3)
where h should be determined beforehand. A naive approach to determining h is choosing a bounded or partially bounded nonlinear function according to the range of the data. For example, the data image pixels within [0, 1]. one may Sigmoid. If the data are nonnegative, one may ReLU. However, such choices only considered the range of the data, which is just small portion of the nonlinearity. Within the range, the true response functions not necessarily linear (ReL.U) or related to exponential (Sigmoid), and can be much more complicated.
As it is difficult determine h in advance, we propose to learn h from the data adaptively. We have different approaches to learning h. The first approach is combining various activation functions, i.e.. ho(=) Σ (2), where a.(.) are different activation functions and 0 = (01..... O&) T are parameters to estimate. However, is not clear whether this is able to approximate a wide range of nonlinear functions. The second approach is using polynomial functions, i.e.. ha(2) = >h 0z* It is a k-order polynomial function and can well approximate any smooth functions provided that k
3

---

Published as a conference paper at ICLR 2024
Input Layer
Hidden Layer
Output Layer
Figure 1: Example schematic of AEMC-NE with one hidden layer in each of the two networks. Users (variables) and items (samples) are represented by rows and columns of the matrix, in which observed ratings are colored and unobserved ratings are left white. Each target rating being predicted is marked with a question mark. The element-wist network shared for all output nodes. The roles of users and items can be exchanged, namely, users could be samples and items could be variables.
sufficiently large. Another approach is using a neural network, i.e.,
0g he = L (ge Lo (0(@)=)
(4)
are matrices, and ar is fixed activation function. Ac- cording to the universal approximation theorems (Pinkus) 1999; [Sonoda & Murata 2017] Lu et al.) 2017). can approximate any continuous functions when the network is wide or deep enough. As is more flexible than other choices in function approximation, we propose to solve
where 1, reg are vectors, 2,...., θ P.g
Lw
Le
minimize Weo ||S @ (X- - now (x)) + Aw
W + xe
1
(5)
where W = (WI..... Wh J. θ = 10,,..... 11 and gw (X) = Wiw (ow (W Wiw- (Wiv-1ow( ow (W (WIX)....)))
(6)
In addition, we assume Wi E R xd, 1. [Lw]. and O E RM 2, E [Le]. Note that do dra m and Po Pre 1. Comparing (5) with (I)
that have replaced by he gw with Frobenius-norm constrained weight matrices. Model (5) is exactly our neuron- enhanced autoencoder-based matrix completion (AEMC-NE) method. There two different neu- ral networks. The first one is an autoencoder defined by he gw. which is to learn a contraction map from the incomplete data matrix X to itself or its observed entries more precisely. The second neural network is performed in element-wise manner learn an activation function adaptively for the output layer of the autoencoder. Figure shows an example schematic of AEMC-NE.
It is worth noting that, shown in Figure 1, the network architecture of the proposed method cannot be easily adapted for new users because we need to, at least, change the size of the output layer of the main neural network. new user and train the weights between the last but one layer and the new output nodes using the ratings of these new users, where we are not considering the cold-start problem. noting that (5) does not make any assumption or take advantage of the prior knowledge about the missing mechanism of X. When the mechanism is missing not at random, supposing the entries are observed with different probabilities (c.g., Pty for Xij. (i,3) S), better approach is to replace S with Q, where Qij = P.j -1/2 and Púj denotes an estimation for pij-
the output layer of the main network, we add one node for each
also worth
Optimization and complexity analysis AEMC-NE can be solved by various optimizers such as gradient descent and Adam (Kingma & Ba 2015). We analyze the time and space complexity of AEMC-NE with a gradient-bases optimizer. In each iteration (suppose the batch size is 6), the time complexity is O Lo dıdz-1 + mb Ete 11) in which the first part is from the main neural network and the second part from the element-wise neural network. The space complexity is Ob di + E/v did;- + mb Ete pt + - pI) The element-wise neural network increased the time and space complexity some extent. Considering the single hidden layer spe- cial case, the time and space complexity of AEMC-NE are (dmb + pmb) and Omm + pmb) respectively. Note that p is usually much smaller than d, then the element- wise neural network just increased the time complexity slightly. Although the space complexity became p times of the main network, it is still acceptable & n. See the time costs in Table
4

---

Published as a conference paper at ICLR 2024
3 THEORETICAL GUARANTEE
3.1 MISSING COMPLETELY AT RANDOM
In this section, we analyze the capability of AEMC-NE in predicting the missing values of X. Note that [S] 1S o xx X) | S (X x)1 Ls. where X (e (X)). We have
Cs = [S] EnJeES ((Xi,, Xiz), where ((Xij, Xig) = (Xiy- X.y) Note that instead of the square
loss, we may use other functions such as iX X-yl- In the remainder of this paper, ((Xij, Xiz) denotes a general loss. Let S be the set of missing values of X, i.e., S mm] x [n]],S. The
generalization error is quantified by Ls= |S4 E(..ess- ((xi,,X,)) We have
Theorem 3.1. Suppose a set S of elements of X E mm are observed uniformly and randomly, which results in an incomplete matrix X with unknown ratings replaced by some values such as zero. Let X = helgw(X (X)), where he is defined by (4) and gw is defined by (6). Suppose Will 2 ap |ill2.1 I or E [Lw], d == max maxx(d1..... .,,d...,.....) < m, and Tillz S by 1
I by 1 [L). Suppose the Lipschitz constants of ow and de are p and respectively. Suppose supr,3 |e(X,j. jj Xij)l S Te, is ne-Lipschitz and
|1 I μ.. Then with
probability at least 8 over the random sampling S,
Cinevian In (mn) + (3mpp(mmn)8/244 ln
Cg. Ls S
S1
S1
(7)
117mmn min ([S), (Sc)
mn |
+
+ 3
In
S
d 2/3
3/2
b' bi
where ÓVInm
Elnr
U2 Ele PIPL-1, 03 &Leu
maxt
1, Φ
1 I a:) (I bi), and C1, C2 some absolute constants.
First, let's show that the bound is non-trivial. Since activation functions are often at most 1-Lipschitz, let p = 0 == 1. Suppose 01
aLw and b
bLe 1. Since df I di-1, 3/2 d. In addition, max; b//bi mmax /pi-
Elw (a/a, 2/3 3/2
have
L max; a/a, < L
3/2
For convenience, hereinafter, we assume that |SS 2 \S). Then the bound in Theorem 3.1 becomes
nemn 3/2 al (e
gep(mm) 3/2 Ei pipe
Lse SCs +
A
[8
18|18
where As
117man + 3TT
In
Note that | S Vmn maxy (.,.). If |S||S9
|S'1//
C3 max (LW2d(mm) 3/2 max;; [1yl 3/2 V Ele piPi-1) holds for some constant C3, the bound is non-trivial. Obviously, the condition holds if is not too large and [S] is close to |S%].
3/2
Particularly, Theorem 3.1 provides the following results.
A. The element-wise network is helpful
Let Cg = IST S (X gw (x)) and Ls [st IS O (X ho (x) be the training
errors of AEMC (AEMC-NE with the element-wise network ablated) and AEMC-NE respectively. he can be reformulated as he
(z) where re suitable neural network. Then
Ls = |st || (x 9w (X) re (Z. Thus, we always have ATE == Ls C3 S theoretically, though difficult to quantify ATE because it depends on unknown data generating model. According to Theorem 3.1] the increase of complexity, denoted by Aept. introduced by the
element-wii network of AEMC-NE depends ghe-1 . bi. and Camu(mmn /02 ln which
T.e
[S]]s]]
GGivnn a matrix Z, use Z|2 |2 := Σ, || and 2 oc = maxis 77y to denote the spectral norm, l21 norm, and Eo respectively.
5

---

Published as a conference paper at ICLR 2024
small. Suppose the nonlinearity of the response function existing in X is strong enough, we have ATE + cppl < O. It means AEMC-NE guarantees a tighter upper bound of test error than AEMC.
On the other hand, suppose we add more (Le, to be more precise) layers to the de- coder of AEMC and obtain an +EMC+ that has the same expressive ability as AEMC-NE. Then AEMC+ and AEMC-NE have the same training error and we only need to compare the model complexity. As explained in Appendix [ compared with AEMC-NE, AEMC+
has 2m(m - 1)P + (Le - 2)m(m - 1)p² - Apar more parameters. where P = min mink -1 pt- Obviously, Apar large number. More formally, for AEMC+, in Theo- (IT221
rem 3.1 Φ becomes ø' = -p'w-1p'e-ll
L ai) (II/2tt42 ai) and V1 becomes t/ =
( 2//3) 3/2 Since the element-wise network (width p) in AEMC-NE is much smaller than the added layers (width pm, see Figure 3 in AEMC+, we have of > U1, which means AEMC+ has looser generalization error bound than AEMC-NE.
6' In
Elarthe
B. Filling the missing values with zeros is helpful.
Suppose we have two methods to fill the unknown ratings, one is zero filling and the other is method different from zero filling (e.g. random filling or mean filling). Suppose based on the two methods, we get the same training errors, i.e., L3 Lather Using Theorem 3.1 and the fact
| 4ero P < ||X other [r, we conclude that the upper bound of L is less than the upper bound of Cother This result has been empirically verified by many previous work (e.g., (Sedhain et al. 2015 Muller et al.] 2018 Yi et al. (0200) in which the missing values are filled by zeros rather than the means or other values. is worth noting that although the zero-filling, compared with some other weak imputation methods, may lead to larger training error C the in equation / can be much smaller, which finally leads to a tighter bound of L However, we have a perfect imputation (e.g., filling the missing values with the true values), the training error C can be very small, though the corresponding e1 is larger, which eventually leads to a tight bound of Lg
o
C. Increasing reduces the upper bound.
Let the sampling rate
ISl Ç and network structures be fixed. Then 8 becomes 12E
Ls SCs
SCs+ + Ō ne me max., X..l) + Ō <(-C)mn/d
TEA Ele pipi-1 ((1-C)/m
+
1 In 8" 11r + 3TeV (1- (1-0)mm (1-()aam
Therefore, when n increases, the bound becomes tighter. In addition, Ls S Ls when In real applications, if there are more users than items, we construct a neural network such that the input is a vector of each user's rating, where items correspond to features and users correspond to samples. In other words, a larger difference between the number of users and the number of items (or the number of variables and the number of samples more generally) leads tighter upper bound, because we can construct the autoencoder along the smaller size of the matrix.
3.2 MISSING NOT AT RANDOM
should be pointed out that Theorem 3.1 is based on the assumption of missing completely at ran- dom (MCAR). The MCAR assumption has been widely used in previous work of matrix completion
(Srebro & Shraibman 2005| Candès & Recht 2009; Shamir Shalev-Shwartz 2014] Fan et al.)
2019) and missing data imputation (Yoon et al.) 2018 Mattei & Frellsen, 2019). However, it has been found that in collaborative filtering, the data entries may be missing not at random (MNAR) (Mariin et al.) 2007 Marlin & Zeme] 2009; (Schnabel et al. 2016: Wang et al. 2019 Ma & Chen,
2019). Hence, in addition to Theorem 3.1 we propose a generalization error bound under the as- sumption of MNAR, in which the entries of the matrix are observed with different probabilities.
Theorem 3.2. Suppose a set S of elements of X E <Rmxx are observed, where Xsj is observed with he(sw(X) Based on the same definitions of X, he, gw, 3.1 with probability at least
probability Pij, V(i,j) E S. Let
T& n6 Un U2 vg used in Theorem
Σ
E(X,, Xx)
Σ Pig
mn
mn
(1.) []]]
(1.)s
E Emnnss Pij 17293
(Cinvi + CyTEV 02 l1
+ Tr 7mn
1
y Easnes Pig

---

Published as a conference paper at ICLR 2024
where C1 and C22 are some absolute constants.
In the theorem, V E(sjees Pij (mm) is at the scale of 1/v VSS, provided that the variance of Pij
not too large. The RHS of the bound comparable to that in Theorem 3.2 Therefore, the
conclusions A, B, C for Theorem 3.1 also hold for Theorem 3.2 In reality, Pij are unknown but
can be estimated via some approaches (Schnaell et al. 2016 Wang et al. 2019 Ma & Chen 2019).
Based the estimation (denoted by Psy), we can obtain a bound for ven _ (1.))(mm) {(Xej, X1y)
TI7 E(s))ss ((xsj; Xij), which shown by Theorem A.1 in the supplementary material.
CONNECTION WITH PREVIOUS WORK
The element-wiss neural network of AEMC-NE can be regarded
activation function adaptively learned from data. It is related to the previous work on adaptive activation functions such (Lin al. 2013 Agostinelli al. 2014 Hou et al. 2017 Goyal et al. 2019). For instance, [Hou et al. (217 showed that applying adaptive activation functions in the regression (second-to-last) layer of a neural network can significantly decrease the bias. Their adaptive activation function in the form of piece-wise polynomials. We found that, empirically, in AEMC-NE, the improvement given by polynomials (Hou et al., 2017) not significant, possibly due to the unboundedness of polynomials.
The theoretical study for autoencoder and deep learning based collaborative filtering is very limited. Recently few researchers studied the generalization ability or sample complexity of deep neural networks (Bartlett et al., ( et al. 2018 Golowich et al. 2018) but their results do not apply to autoencoder- CF or missing data imputation as well as our AEMC-NE.
Shamir & Shalev-Shwartz (2014) provided the following generalization bound for nuclear norm minimization based CF: L.s. S Ls + + [=ll|(ll(ymm-v + R, where X denotes the recovered [S]
matrix given by nuclear norm minimization and R stands for the remainder of their result (Theorem
6). Suppose the rank of X is d. Then the term related to the nuclear norm can be large as or 0 (TEuN
o / Çmn
d (mm (em)) where we have assumed m n. According to the
Ci <d result C of Theorem 3.1 the dominating term in our bound can be Ō (NERy/ 5 n
Note that
with the same d, the training error of our AEMC-NE is less than the training error of nuclear norm minimization because we are using neural networks. Now we conclude that when n is sufficiently large (compared (d), our bound tighter than that of (Shamir & Chalev-Shwartz 2014).
NUMERICAL RESULTS
5.1 EXPERIMENTS ON SYNTIETIC DATA
We generate a synthetic data matrix X of size 300 x 3000 using a latent (10 dimension) variable model with nonlinear response function (detailed in Appendix []. We randomly drop certain portion of the elements of X and aim to recover the missing values. This setting is MCAR. We compare our AEMC-NE with AEMC as well as its variants under the evaluation of the following
metric relative recovery error [I(X- X) @ S||e/||X S The results (average of 10 runs) are reported in Figure 2 We see that, in Figure aaa), AEMC-NE outperforms AEMC and its variants (with more hidden layers) in all cases when the missing rate increases from 0.1 to 0.8 and the superiority of AEMC-NE is significant when the missing rate is not too high. Importantly, this result is consistent with the conclusion A given by Theorem 3.1 Figure ( shows that AEMC-NE is not sensitive the size of the clement-wise network provided that it is not too small. Figure 2(c) shows that both AEMC and AEMC-NE are not sensitive to the width of the middle layer of the autoencoder. Figure dd indicates that relatively small weight decays have little impact.
Besides MCAR, we also conduct some experiments of MNAR. The relative recovery errors (over five runs) are reported in Table where the missing probability varies along the locations of the en- tries in the matrix. The detailed setting is in Appendix C the baseline AEMC significantly in all cases. We can compare this table (MNAR) with the results in Figure (MCAR) and find that the performances similar. These results verify that method
We see that AEMC-NE outperformed
7

---

Published as a conference paper at ICLR 2024
12
04
10
05
0.5
ABMC AEVOHIC
0.9
AEVONEC
AOVC-AE
Nelative recorvey AFTIC
0.2
0.4
0:15
04000009
0.1
0.2
0.3
0.4
0.5
D.5
0.7
0.3
10
30
20
43
50
100
6 6 12
00 40 50 00 70
03
1e-05 0.000 0.001 2011 D.1
Maxing mihe
Witth edemertt-woo reteert ABMC--N
With (m/00 00/07 m73 networr
Weight ORCRy
Figure 2: Recovery performance on synthetic data in the setting of MCAR. (a) Influence of miss- ing rate. Network structure: AEMC 300-1000 100-100000-00--0000 AEMC+
10003001000-00---0 AEMC+ 300- 100-10003-110 100-100-100-300, AEMC-NE 100-100-30-100-300 for the main network 1 for the clement-wise network, where
and 1 ent width (w) of the hidden layers in the element-wise network. (c) Influence of the width (middle
20. (b) AEMC-NE with differ-
layer) of the main network. The missing rate is 0.5 and 20. (d) Influence of the weight decay (Aw = Xg). The missing rate is 0.5 and w 20.
works well for both MCAR and MNAR, AEMC-NE outperforms AEMC, and the element-wise network of AEMC-NE is indeed effective in improving recovery accuracy.
Table 1: Rcovery performance synthetic data in the setting of MNAR
Missing rate
0.2
0.3
0,4
0.5
0.6
0.7
AEMC
0.17120.001 0.17020.002
0.180_o.003
0.187
0.211 000003
0.268
AEMC-NE
0.101
0. 0.10640.oms
0.109
0. 0.124
0.153
0.243
5.2 EXPERIMENTS ON MOVIELENS DATASETS
In this section, we evaluate the proposed method AEMC-NE on 100ielens-100K, Movielens- IM, and Movielens- 10M (Harper Konstan 2013). These datasets contain real-world ratings for 1682, 3900, and 10000 movies given by 943, 6040, and 72000 users respectively. We randomly sample 90% of the known ratings as training set, leaving the remaining 10% as the test set. Among the training set, 5% are held out for hyperparameter tuning. The model performance is evaluated by the
[ E(is)Es (Xij X,y)2. where S denotes the set of test ratings. In our AEMC-NE, the main neural network has one hidden layer. The numbers of hidden units are 500, 900, and 1000 for Moviel.ens: 100k, MovieLens-11 M and MovieLens-100 respectively. The clement-wise neural network has one hidden layer, of which the size is 200. The regularization parameters Aw and Àe were chosen from {0.01, 0.1, 1, 10, 50, 100, 200, 500]. The optimizer for AEMC-NE is Adam (Kingma & Ba 2015
root mean squared error defined as RMSE
In Table 2 we report the mean RMSE of our AEMC-NE in comparison few baselines based on 20 random splits. Our AEMC-NE outperformed all baselines on MovieLens 100k and MovieLens: 1M. We have tried increase the depth of the main neural network and the element-wise neural network, but the improvements in terms of RMSE are not significant.
5.3 EXPERIMENTS ON DOUBAN AND FLIXSTER
We use the preprocessed subsets and splits provided by Monti et al. (2017). The datasets both contain 3000 users and 3000 items. Douban contains 136,891 ratings with density 0.0152 on a rating scale (1, 2, 3, 4,5). Flixster contains 26,173 ratings with density 0.0029 on rating scale (0.5, 1, 1.5, ..., 5). Five percent the training samples are used for hyperparameter tuning. In AEMC-NE, the main network has one hidden layer, of which the size is 500, for both datasets. The structure of the element- wise network is the same as that used for the MovieLens datasets. In Table 3. show the mean RMSE on repeated experiments. AEMC-NE outperforms other baselines both datasets. Note that some compared methods include extra content like the side information of users and items into the model, while AEMC-NE does not require extra content.
8

---

Published as a conference paper at ICLR 2024
Table 2: RMSE results on the three MovicLens datasets
Model
ML-100k
ML-1M
MI-IOM
BiasMF (Koren al. 2009)
0.911
0.845
0.803
NNMF (Zuugarle Roy
2015)
0.903
0.843
LLORMA Lee el al.
2016
0.8881
0,833
0.782
GC-MC (van den Berg cf al.
2017
0,905
0,832
0.777
Vu+
VD++ (Zhang ct al. 2017
0.904
0.848
Vu (Zhang et al.
0.901
0.86
CF-NADE iZheng et 2016
0.829
0.771
DMF+ (Yi et al. 2019)
0.8889
0.8321
IMC-GAF: (Shen et al.
2021
0.897
0.829
GHRS Zamanzadeh Darban & Valipour 2022
0.8887
0.833
0.782
AEMC (AutoRec) (Sedhain et al. 2015)
0.831 0.003
0.782-+ 0.003
AEMC (AutoRec, reproduced)
0.8818 + 0.0082
0.8291 + 0.0021
0.7780+ 0.0024
AEMC (ReLU output)
0.8807 + 0.0092
0.8276 0.0025
0.7851 + 0.0029
AEMC-NE (ours)
0.8767 0.0089
0.8248 + 0.0024
0.7723 0.0025
Table 3:
RMSE result AEMC-NE and compared methods on Douban and Flixster dataset Model
Douban
Flixster
PMF (Mnih Salakhutdinov 2008
0.7492
0,9809
GRALS RRa et al. 2015)
0.8326
1.245
sRGCNN Monti et al. [2017
0,801
0.926
GC-MC (van den Berg al. 2017
0.734
0.917
Factorized (Harfford et al. 2018
0.738
0.908
GRAEM (Strahl ct al. 2020)
0.7497
0.8857
AEMC (AutoRec, reproduced)
0.7325 0.0009
0.957 0.0003
AEMC (ReLU output)
0.7306 + 0.0010
0.9610 + 0.0005
AEMC-NE (ours)
0.728611 0.0007
0.88161
0.0003
5.4 ADDITIONAL ANALYSIS FOR CF EXPERIMENTS
Note that in Tables and the improvement given by AEMC-NE is not very significant compared with the linear models such as LLORMA. The reason is that the rating matrices of these datasets are square or nearly square. Our theoretical results have shown that the superiority of AEMC-NE is more significant when the rating matrix is very fat or tall. Here we consider subset of Moviel 1M consisting of only 500 users who rated most. Then the size of the rating matrix is 3706 x 500 and the train-test ratio is 1. The RMSEs (average of 10 runs) of SVD, SVD++, AEMC, AEMC*, AEMC+ (one or two more hidden layers compared to AEMC) and AEMC-NE are reported in Table AEMC-NE outperformed the three baselines largely, especially when compared to the results in Tables and This result is consistent with our theoretical analysis.
Table 4: RMSES MovieLens- IM subset
Method RMSE
SVD
SVD++
AEMC AEMC
AEMC*
AEMC-NE
AEMC -NE
0.8713
0.8591
0.8265
0.8294
0.8308
0.8182
0.8207
More results The time cost comparison, results of NDCG metric, experiments of CF in the case of MNAR, and missing data imputation on UCI datasets are in Appendices and respectively.
6 CONCLUSION
This paper presented a novel collaborative filtering method called AEMC-NE, which is composed of two neural networks: one is layer-wise network and the other is an element-wise network that able to learn an activation function for the output layer adaptively. We also analyzed the gener- alization enror bounds for AEMC-NE, which verified the effectiveness of AEMC-NE theoretically. AEMC-NE outperformed many baselines on a few benchmark datasets of collaborative filtering. Note that method can be extended to the scenarios of implicit feedback if we negative sam- pling and ranking loss functions such as the BPR loss (Rendle et al. 2009). addition, AEMC-NE applicable to more general missing data imputation problems.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
This work was supported by the National Natural Science Foundation of China under Grants No.62106211 I and No.62072151, the research funding T00120210002 of Shenzhen Research In- stitute of Big Data, the funding UDF01001770 of The Chinese University Hong Kong. Shenzhen, Anhui Provincial Natural Science Fund for the Distinguished Young Scholars (2008085130), Open Foundation of Yunman Key Laboratory of Software Engineering (2023SE103), CCF-Baidu Open Fund, and CAAl-Huawei MindSpore Open Fund.
ETHICS STATEMENTS
The authors of this work have read and commit to adhering to the ICLR Code of Ethics.
REFERENCES
G. Adomavicius and A. Tuzhilin. Toward the next generation of recommender systems: survey of the state-of-the-art and possible extensions. IEEE Transactions on Knowledge and Data Engi- neering, 17(6):734-749, 2005.
Forest Agostinelli, Matthew Hoffman, Peter Sadowski, and Pierre Baldi. Learning activation func- tions to improve deep neural networks. arXiv preprint arXiv: 1412.6830, 2014.
Frank B Baker. The basics of item response theory. ERIC, 2001.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normalized margin bounds for neural networks. I. Guyon, U. Luxburg. S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Yoshua Bengio, Pascal Lamblin, Dan Popovici, and Hugo Larochelle. Greedy layer-wise training of deep networks. In Advances in neural information processing systems, pp. 153-160, 2007.
Bennett and S. Lanning. The netflix prize. In Proceedings of the KDD Cup Workshop 2007, pp- 3-6, New York, August 2007. ACM.
Daniel Billsus and Michael J. Pazzani. Learning collaborative information filters. pp. 46-54, 1998. wwtp:///ttttioo.ooo
URL http::t/tpttall.t..e. http:p/tw.....cc..reeeattttttt.o http:/ooonncccmm.dd6665555 657311
John Breese, David Heckerman, and Carl Kadie. Empirical analysis of predictive algorithms for collaborative filtering. In Proceedings of the 14th Conference on Uncertainty in Artificial Intelli- gence, pp. 43-52. Morgan Kaufmann, 1998.
Emmanuel J Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foun- dations of computational mathematics, 96):717-772, 2009. ISSN 1615-3375.
Yudong Chen, Srinadh Bhojanapalli, Sujay Sanghavi, and Rachel Ward. Coherent matrix comple- tion. In Proceedings of the 31 International Conference on Machine Learning (ICML-14), pp- 674-682. JMLR Workshop and Conference Proceedings, 2014.
Gintare Karolina Dziugaite and Daniel M. Roy. Neural network matrix factorization. CoRR, abs/1511 111064443 2015.
Ran El- Yaniv and Dmitry Pechyony. Transductive rademacher complexity and its applications. Journal of Artificial Intelligence Research, 35:193-255 234, 2009.
Ehsan Elhamifar. High-rank matrix completion and clustering under self-expressive models. In Advances in Neural Information Processing Systems 29, pp. 73-81, 2016.
Brian Eriksson, Laura Balzano, and Robert Nowak. High-rank matrix completion. In Artificial Intelligence and Statistics, pp. 373-381, 2012.
Jicong Fan. Dynamic nonlinear matrix completion for varying data imputation. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pp. 6587-6596, 2022a.
10

---

Published as a conference paper at ICLR 2024
Jicong Fan. Multi-mode deep matrix and tensor factorization. In International Conference Learning Representations, 2022b.
Jicong Fan and Jieyu Cheng. Matrix completion by deep matrix factorization. Neural Networks, 98: 34 41, 2018.
Jicong Fan and Tommy W.S. Chow. Matrix completion by least-square, low-rank, and sparse self- representations. Pattern Recognition, 71 71:290-305, 2017.
Jicong Fan and Madeleine Udell. Online high rank matrix completion. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 8690-8698, 2019.
Jicong Fan, Lijun Ding, Yudong Chen, and Madeleine Udell. Factor group-sparse regularization for efficient low-rank matrix recovery. In Advances in Neural Information Processing Systems, pp. 5104-51 14, 2019.
Jicong Fan, Yugian Zhang, and Madeleine Udell. Polynomial matrix completion for missing data imputation and transductive learning. In Proceedings of the AAAI Conference on Artificial Intel- ligence, volume 34, pp. 3842 3842-3849 2020.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Conference On Learning Theory, pp. 297-299. PMLR, 2018.
Mohit Goyal, Rajan Goyal, and Brejesh Lall. Learning activation functions: A new paradigm for understanding neural networks. arXiv preprint
09529, 2019.
Maxwell Harper and Joseph Konstan. The MovieLens datasets: History and context. ACM Transactions Interactive Intelligent Systems, 5(4):1-19, December 2015.
Jason S. Hartford, Devon R. Graham, Kevin Leyton-Brown, and Siamak Ravanbakhsh. Deep Models of Interactions Across Sets. In Proceedings of the 35th International Conference on Machine Learning, pp. 1914 1923. PMLR, 2018.
Xiangnan He, Lizi Liao, Hanwang Zhang, Liqiang Nie, Xia Hu, and Tat-Seng Chua. Neural col- laborative filtering. In Proceedings of the 26th international conference on world wide web, pp- 173-182, 2017.
Geoffrey E Hinton and Ruslan R Salakhutdinov. Reducing the dimensionality of data with neural networks. science, 313(5786):504-507, 2006.
Geoffrey E Hinton, Simon Osindero, and Yee-Whye Teh. A fast learning algorithm for deep belief nets. Neural computation, 1877)1127-1554, 2006.
Wassily Hoeffding. Probability inequalities for sums bounded random variables. Journal of the American Statistical Association, 58(301):13-30) 1963.
Le Hou, Dimitris Samaras, Tahsin Kure, Yi Gao, and Joel Saltz. Convnets with smooth adaptive activation functions for regression. In Artificial Intelligence and Statistics, pp. 430-439. PMLR, 2017.
Yao Hu, Debing Zhang, Jieping Ye, Xuelong Li, and Xiaofei He. Fast and accurate matrix com- pletion via truncated nuclear norm regularization. IEEE transactions on pattern analysis and machine intelligence, 35 2012.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd Interna- tional Conference on Learning Representations, 2015.
Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems. Computer, 42(8):30-37, 2009. doi: 10. 00.1009/CC2000.2226
Joseph E. LeDoux. Emotion circuits in the brain. Annual Review of Neuroscience, 23(1):155-184, 2000.
Joonseok Lee, Seungyeon Kim, Guy Lebanon, Yoram Singer, and Samy Bengio. Llorma: Local low-rank matrix approximation. Journal of Machine Learning Research, 17(15):1-24, 2016.
11

---

Published as a conference paper at ICLR 2024
Min Lin, Qiang Chen, and Shuicheng Yan. Network in network. arXiv preprint arXiv:1312.4400, 2013.
Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: view from the width. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 6232-62222222 6240, 2017.
Wei Ma and George H Chen. Missing not at random in matrix completion: The effectiveness of estimating missingness probabilities under a low nuclear norm assumption. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Buee Buc, Fox, and R. Garnett (eds.), Advances Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Benjamin Marlin and Richard S Zemel. Collaborative prediction and ranking with non-random missing data. In Proceedings of the third ACM conference Recommender systems, pp. 5-12, 2009.
Benjamin M. Marlin, Richard S. Zemel, Sam Roweis, and Malcolm Slaney, Collaborative filtering and the missing at random assumption. In Proceedings of the Twenty-Third Conference on Un- certainty in Artificial Intelligence, UAI'07, pp. 267-275, Arlington, Virginia, USA, 2007. AUAT Press. ISBN 0974903930.
Pierre-Alexandre Mattei and Jes Frellsen. MIWAF: Deep generative modelling and imputation of incomplete data sets. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 4413-4423, PMLR, 09-19 Jun 2019. URL https: UtLhtpss:://pp h/tp:s/:/ppcccednggss mlr. www.pp.es//.. v9 httm///aaeeeleee. html
Andriy Mnih and Russ Salakhutdinov. Probabilistic matrix factorization. In Platt, D. Koller, Y. Singer, and S. Roweis (eds.), Advances in Neural Information Processing Systems, volume 20, 2008.
Federico Monti, Michael Bronstein, and Xavier Bresson. Geometric matrix completion with re- current multi-graph neural networks. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Lorenz Muller, Julien Martel, and Giacomo Indiveri. Kernelized synaptic weight matrices. In Proceedings of the 35th International Conference on Machine Learning, pp. 3654-3663, 2018.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. pac-bayesian approach to spectrally-norrmaiieed margin bounds for neural networks. In International Conference on Learn- ing Representations, 2018
Feiping Nie, Hua Wang, Heng Huang, and Chris Ding. Joint Schatten p-norm and Ip-norm robust matrix completion for missing value recovery. Knowledge and Information Systems, 42(3):525- 544, 2015. ISSN 0219-3116. doi: 10007//1111--01--01
Greg Ongie, Rebecca Willett, Robert D. Nowak, and Laura Balzano. Algebraic variety models for high-rank matrix completion. In Proceedings of the 34th International Conference on Machine Learning, pp. 2691-2700. PMLR, 2017.
Allan Pinkus. Approximation theory of the mlp model in neural networks. Acta numerica, 8:143 195, 1999.
Nikhil Rao, Hsiang-Fu Yu, Pradeep K Ravikumar, and Inderjit S Dhillon. Collaborative filtering with graph information: Consistency and scalable methods. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems, vol- ume 28. Curran Associates, Inc., 2015.
Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, and Lars Schmidt-Thieme. Bpr: Bayesian personalized ranking from implicit feedback. In Proceedings the Twenty-Fifht Conference Uncertainty in Artificial Intelligence, UAI '09, pp. 452 461, Arlington, Virginia, USA, 2009. AUAT Press. ISBN 9780974903958.
12

---

Published as a conference paper at ICLR 2024
Steffen Rendle, Walid Krichene, Li Zhang, and John Anderson. Neural collaborative filtering matrix factorization revisited. In Proceedings of the 14th ACM Conference on Recommender Systems, RecSys '20, pp. 240-248, New York, NY, USA, 2020. Association for Computing Ma- chinery. ISBN 97814508 450375833. doi: 10.1145/33831133441222
Paul Resnick, Neophytos lacovou, Mitesh Suchak, Peter Bergstrom, and John Riedl. Grouplens: an open architecture for collaborative filtering of netnews. In CSCW '94: Proceedings of the 1994 ACM conference on Computer supported cooperative work, pp. 175-186, New York, NY, USA, 1994. ACM Press.
Ruslan Salakhutdinov. Andriy Mnih, and Geoffrey Hinton. Restricted boltzmann machines for collaborative filtering. In ICML '07: Proceedings the 24th international conference on Machine learning, pp. 791-798, 2007.
Tobias Schnabel, Adith Swaminathan, Ashudeep Singh, Navin Chandak, and Thorsten Joachims. Recommendations as treatments: Debiasing learning and evaluation. In international conference machine learning, pp. 1670-1679. PMLR, 2016.
Nicolas Schreuder. Bounding the expectation of the supremum empirical processes indexed by hölder classes. arXiv preprint arXiv:2003. 13530, 2020.
Suvash Sedhain, Aditya Krishna Menon, Scott Sanner, and Lexing Xie. Autorec: Autoencoders meet collaborative filtering. In Proceedings of the 24th International Conference on World Wide Web Companion. pp. 111-112, 2015.
Ohad Shamir and Shai Shalev-Shwartz Matrix completion with the trace norm: Learning, bounding. and transducing. Journal of Machine Learning Research, 15(99)3340133423 2014.
Wei Shen, Chuheng Zhang, Yun Tian, Liang Zeng, Xiaonan He, Wanchun Dou, and Xiaolong Xu. Inductive matrix completion using graph autoencoder. In Proceedings of the 30th ACM Inter- national Conference on Information &amp Knowledge Management. ACM, October 2021. doi: 10. 10.1145//45963733482266 URL
Sho Sonoda and Noboru Murata. Neural network with unbounded activation functions is universal approximator. Applied and Computational Harmonic Analysis, 43(2):233-268, 2017.
Nathan Srebro and Adi Shraibman. Rank, trace-norm and max-norm. In International Conference on Computational Learning Theory, pp. 545-560. Springer, 2005.
Jonathan Strahl, Jaakko Peltonen, Hiroshi Mamitsuka, and Samuel Kaski. Scalable probabilistic matrix factorization with graph-based priors. The Thirty-Fourth AAAI Conference Artificial Intelligence, AAAI, pp. 5851-5858 AAAI Press, 2020.
Ruoyu Sun and Zhi-Quar Luo. Guaranteed matrix completion via nonconvex factorization. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 270-289, 2015.
Rianne van den Berg, Thomas N. Kipf, and Max Welling. Graph convolutional matrix completion. abs/1706.0226n 02263,, 2017.
Bart Vandereycken. Low-rank matrix completion by riemannian optimization. SIAM Journal on Optimization, 23(2):1214-123 2013. doi: 10.1 10845768.
Pascal Vincent, Hugo Larochelle, Isabelle Lajoie, Yoshua Bengio, Pierre-Antoine Manzagol, and Léon Bottou. Stacked denoising autoencoders: Learning useful representations in deep network with a local denoising criterion. Journal of machine learning research, 11(12), 2010.
Xiaojie Wang, Rui Zhang, Yu Sun, and Jianzhong Qi. Doubly robust joint learning for recommen- dation on data missing not at random. International Conference on Machine Learning, pp- 6638-6647. PMLR, 2019.
Yao Wu, Christopher DuBois, Alice X. Zheng, and Martin Ester. Collaborative denoising auto- encoders for top-n recommender systems. In Proceedings of the Ninth ACM International Con- ference Web Search and Data Mining, pp. 153-162, 2 2016.
13

---

Published as a conference paper at ICLR 2024
Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Rethinking ral vs. Conference Machine Learning, pp. 11514-11524. PMLR, 2021.
collaborative filtering: The theoretical perspectives. In International
Congyuan Yang, Daniel Robinson, and Rene Vidal. Sparse subspace clustering with missing entries. In International Conference on Machine Learning, pp. 2463-226222 2472, 2015.
Baolin Yi, Xiaoxuan Shen, Hai Liu, Zhaoli Zhang, Wei Zhang, Sannyuya Liu, and Naixue Xiong. Deep matrix factorization with implicit feedback embedding for recommendation system. IEEE Trans. Ind. Informatics, 15(8):4591 460144156-66,, 2019.
Joonyoung Yi, Juhyuk Lee, Kwang Joon Kim, Sung Ju Hwang, and Eunho Yang, Why not to use zero imputation? correcting sparsity bias training neural networks. In 8th International Conference on Learning Representations, 2020.
Jinsung Yoon, James Jordon, and Mihaela van der Schaar. GAIN: Missing data imputation using generative adversarial nets. In Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5689-5698. PMLR, 10-15 Jul 2018.
Zahra Zamanzadeh Darban and Mohammad Hadi Valipour. Ghrs: Graph-based hybrid recommen- dation system with application to movie recommendation. Expert Systems with Applications, 200: 11650, 2022. ISSN 0957-4474. doi: htt.a//c......eee...........eooa
116850. URL https:
www. www.sciencedirecc.
Shuai Zhang, Lina Yao, and Xiwei Xu. Autosvd++: An efficient hybrid collaborative filtering model via contractive auto-encoders. In SIGIR, pp. 957-960. ACM, 2017.
Shuai Zhang, Lina Yao, Aixin Sun, and Yi Tay. Deep learning based recommender system: A survey and new perspectives. ACM Comput. Surv, 52(1):1-38, 2019.
Yin Zheng, Bangsheng Tang, Wenkui Ding, and Hanning Zhou. A neural autoregressive approach to collaborative filtering. In Proceedings of the 33nd International Conference on Machine Learn- ing, volume 48, pp. 764-773, 2016.
A MORE THEORETICAL RESULT
The following theorem provides generalization error bound for missing data imputation when the missing pattern is missing not at random and the propensities are estimated.
Theorem A.1. Suppose
S of elements of X m observed, where Xij is observed
with probability Pij. v(i.j) E S. Suppose the estimated propensities are Pig. v(i,)) () E S. Let
X = he (gw( (X))
Based on the same conditions or definitions of X, has gw, Tb TJ,, V2. V3
used Theorem 3.1
with probability at least
van
1
Σ
e(Xaj, {1)
Σ (tS))S
Pij (X X1z)
mn
mi
((x))[m]x(x)
E E(seesP
V
Eussesp'
(Cine + Ca u2 + T
1
(10)
mn
Vmn
mn
Tt mH (L.))[(]((()
Σ
Pij Pij
where C₁ and C22 are some absolute constants.
14

---

Published as a conference paper at ICLR 2024
B CONNECTION BETWEEN THE NETWORK STRUCTURES OF AEMC AND AEMC-NE
Figure shows example of the network architecture of AEMC-NE. We that adding the orange connections forms new neural network without an element-wise network. The new network can be regarded as an extension of AEMC (denoted by AEMC+), of which the decoder has more layers. indicates that adding more layers to the decoder of AEMC and ensuring sparse and shared weights yield AEMC-NE.
In Figure B intuitively, the number of orange connections is much larger than the number of black connections. To be more precise and general, suppose the element-win network AEMC-NE has k hidden layers of width p and the decoder of AEMC+ has & additional hidden layers, then AEMC+ has 2m((m - 1)pp+
1)mmm 1)y² more parameters than AEMC-NE. Compared with AEMC, AEMC+ introduces an additional multiplication p*+1 I Lw++++1 (which could be much larger than one) to the Φ in Theorem 3.1 Thus, AEMC+ has higher generalization error bound than AEMC-NE.
Lw
Z
*
ghv
Figure 3: Network structure of AEMC-NE or AEMC (with more layers in the decoder)
C EXPERIMENTAL SETTING ABOUT THE SYNTHETIC DATA
We generate synthetic data using the following nonlinear latent variable model
X W BacchhWW/2Z W2T W.TonnbWWTTonbWW (),
X (Cosine X) +
where Wi E 5050000 W2 E IR 100 W E 3000000000 100 are drawn from the uniform distribution of [-1, 1], and Z E R 100 is random Gaussian matrix.
X1
X₂ In block X;,
For MNAR, we partition the data matrix into four blocks, i.e., X
X3
X,
the elements are missing with probability pa, = 1,2,3,4. We let < P2 <
P3 P4. The
correspondence between the total missing rate and ps in Table 5 between the missing rates are large. For instance, when the total missing rate is 0.2, 0.2,pa/P, 21.
We see that the differences
Table 5: Details of MNAR setting on the synthetic data 0.2
total missing rate
0.3
0.4
0.5
0.6
0.7
P1,P2
0.02, 0.13
0.12, 0.22
0.23, 0.33
0.33, 0.42
0.42, 0.53
0.53, 0.63
P3, P4
0.23, 0.43
0.33, 0.53
0.43, 0.62
0.52, 0.72
0.63, 0.83
0.73, 0.93
P4/P1
21.5
4.42
2.70
2.28
1.98
1.75
D THE INFLUENCE OF HIDDEN UNITS NUMBER IN AEMC-NE
Figure shows the influence of the number of hidden units in each the neural networks of NE- AEMC MovieLens-II M. In the left plot, the number of hidden units of the clement-wise neural
15

---

Published as a conference paper at ICLR 2024
network is fixed as 200. In the right plot, the number of hidden units of the main neural network fixed as 900. We see that NE-AEMC, the main neural network with 900 hidden units and the element-wise neural network with 200 hidden units provide the best performance.
RMSS
10:30
8:455
00235
300 1750
780
Number of Units In Neural Natwork
Number Liita Secoond Neural
aetwork
Figure 4: Influence the number of hidden units in each of the neural networks of NE-AEMC on Moviel.ens-IMM
E TIME COSTS COMPARISON AND NDCG RESULTS
We compare the time costs AEMC-CF AEMC (Sedhain et al. 2015) in Table 6 each of the five datasets, the time cost of our NE-AEMC is sligtly higher than that of AEMC, which is consistent with the theoretical time complexity we analyzed the end of Section
Table 6: Running time (second) of AEMC and NE-AEMC
Dataset
AEMC
AEMC-NE
Douban
12.1
17.8
Flixster
10.0
15.1
ML- 100k
1.2
2.5
ML-IM
11.1
21.0
ML-10m 10M
1820
2135
Besides RMSE results reported in the main paper, here show the results in terms of the Nor- malized Discounted Cumulative Gain (NDCG) accumulated a particular rank position which defined as
DCGs
NDCG@K = IDCG
(11)
where DCG; = - (1+1) IDCG, is the ideal discounted cunulative gain, and rel; is the graded relevance of the result at position i. It is obvious that
rel:
RMSE=1
NDCG@k = 1 Vk.
(12)
This implies that a good RMSE often corresponds to good NDCG. In recommendation systems, one may concern more about the top & recommendations. That's why here we consider NDCG, in addition to RMSE.
The results NDCG@k (k= 1,5, 10, 50) are reported in Table We see that the proposed AEMC- NE outperformed AEMC in all cases. The improvement given by AEMC-NE is more significant when & is smaller.
Table 7: Results of NDCG@ 10 and NDCG@50 on ML-100k and ML-IM.
NDCG@
NDCG@5
NDCG@ 10
NDCG@50
AEMC 0.9059=t0.0441
0.9313+0.0020
0.9451+0.0013
0.9678+0.0010
ML-100k
AEMC-NE 0.9106+0.0054
0.9328+00.025
0.9462+0.0014
0.9686+:00009
AEMC
0.9197=0.0019 0.9325-0.0009
0.9441+000006
0.967810.0004
ML-IM
AEMC-NE
0.9222+00.0133
0.9339-1000077
0.9446+10.0006
0.9681 +0.000
It should be pointed out that in this paper, considering explicit feedback (ratings range from 1 to 5 or 10) rather than implicit feedback (binary feedback or 1). So our results of NDCG cannot be compared with the results reported by many previous papers.
16

---

Published as a conference paper at ICLR 2024
F EXPERIMENTS ABOUT MISSING NOT AT RANDOM
We also test AEMC (AutoRec) and AEMC-NE the case of MNAR in comparison to MCAR. For MCAR, follow the definition such that each element has 10% probability of being missing. For MNAR, we consider that higher ratings are more likely to be missing. The missing probability is set as p(r) Sigmoid(r) 0.15, where is the rating value. The results (a single trial) are reported We see our AEMC-NE outperforms AEMC in all cases.
in Table
Table 8: MCAR vs MNAR on MovieLens datasets
missing
data
AEMC
AEMC-NE
mechanism
ML- 1O0K
MCAR
0.886
0.878
ML- 100K
MNAR
0.988
0.920
ML- IM
MCAR
0.828
0,825
ML-IM
MNAR
0.902
0.853
1L-10M
MCAR
0.780
0.773
ML-10M
MNAR
0.830
0.815
G EXPERIMENTS OF MISSING DATA IMPUTATION ON UCI DATASETS
Here we consider general missing data imputation on four UC datasets, "Breast" 3) "Letter" "Credit" and "News". The results are reported in Table 9 where the missing rate is 20% and the results of MissForest, MICE, EM, Auto-encoder, and GAIN are all from (Yoon et al. 2018
We see that our AEMC-NE outperforms all other methods on the Credit data and outperforms Auto- encoder in all cases. Note that in this study, we just set the numbers hidden units in the two neural networks of AEMC-NE as 100 and 50 respectively and the data preprocessing is the same as that of (Yonn et al. 2018 is expected that the performance of AEMC-NE can be further improved by tuning the numbers of hidden layers and hidden units.
Table 9: Experiment result on UCI datasets
RMSE
Breast
Letter
Credit
News
MissForest
0,0608
0.1605
0.1976
0.1623
MICE
0.0646
0.1537
0.2585
0.1763
EM
0,0634
0.1563
0.2604
0.1912
Auto-encoder
0.0697
0.1351
0,2388
0.1667
GAIN (Yoon et al. 2018
0.0546
0.1198
0.1858
0.1441
AEMC-NE
0.0634
0.1328
0.1775
0.1551
H PROOF FOR THEOREM 3.
First of all, we give the following lemmas.
)..)) (),)))(((...))) [m]] x [n]: θ X xP 1, 0illz < bi, 1 S b₁, AI E [Lo]: E Z, Z S $z). where the Lipschitz constant of a is &. Suppose the covering number of with respect to || IE is upper- bounded by Ke and c 12 ( b.
Lemma H.1. Let
{H mmxn h2 θ Lo 0 (0
Then the cover covering number of H with respect
to || || is bounded
Le
3/220 'e (Le + 1)8. [ by
PIPI
NHH, 11 < Ke II
1=1
17

---

Published as a conference paper at ICLR 2024
Proof. See Section K.1
Lemma
H.1 provides an upper bound the covering number of the seeennt-wise neural network. The following lemma shows upper bound of the covering number of the main neural network.
Lemma H.2 (Theorem 3.3 of (Bartlett et al. 2017). reformulated). Let Z WLw (Wiw- (W,
where Wi E Rd-id, 1 E [Lw], and
max(m, di...., dLw) I D. Denote the Lipschitz constant of by Suppose the reference matrices (M....., MLw) are given. Define
C= (Fw(X)) WW= (W1..... WLW) W|Will I at IW Millo S d. E [Lw]]- The for any 6 0,
X 2n
Lw II
2/3
(C, e, I| [|])
Σ
22
Now we can get an upper bound for the covering number of the entire neural network in NE-AEMC.
Lemma H.3. The covering number Hw.e = -He (Fe(FFm))) Fwix))) with respect to
||
|| satisfies
(H,, -1. (...)l)))))) s A02 p( 11)
2n
Lw
2/3
II
II bf
Σ
22
1=1
bi (IT by maxt bt
6Loghe-1pp --w- ||
||||
(Mer Lw ai)
Σ
PiPl-1 In
Proof. See Section
K.2
Now calculate the upper bound of the Rademacher complexity of Hwwe via using Lemma H.3 and Dudley entropy integral bound.
2/3
Lemma H.4. Let 11 4p2(Lw-11) -1) 20 In2D2 (II Faw
of)
Σ
of
(II' bp).
Li=l
0i
U/2 = Elee PIPI-1, and V3 6Lep -1 -' | (II
Lw ai
[ by
max b/b,
Sup-
pose llh (X) n. The Rademacher complexity of Hw.e is bounded as
4u 12 + 4200 In + 12p U2 Iu -23
Rs(Hw.)) s
(13)
S
S
VS
Proof. See Section K.3
Collaborative filtering is transductive learning problem. The following lemma provides sample complexity bound for transductive learning, which consistent with the objective function and evaluation metric (RMSE) widely used in collaborative filtering.
Lemma H.5 (Theorem 1 of (El- Ganyvniv & Pechyony 2009), reformulated). Let H be a fixed hypoth- esis set and suppose X [e (Yij, Xiz) 1 S тi. Suppose a fixed set S of distinct indices is uniformly and randomly split to two subsets Sunin and Steat Then with probability at least 1 8 over the random split, we have
Σ (L.)
eYYsg X1x)
Σ (f
e(Vig Xis) + R Rysmiit IS (6 H)
SSeal
Surinl
117 (|Strinl + Stest /min( Suriin S
+
(14)
Staii Steal
(|Srain + S
1
+ 3
In
Swain |Seatl 6
18

---

Published as a conference paper at ICLR 2024
It should be pointed out that according YEl-Yaniv & Pechyony 2009), the transductive Rademacher complexity R1 has the following relationship with the inductive complex- ity Rs (to be computed later)
([Serinn + |tessl) Stain Stessl
R HS (e H)
Rs H).
(15)
Then Theorem 3.1 can be proved as follows.
Accoding to the Rademacher contraction property, we have Rs(E H) < neRs(H), where Ne denotes the lipschitz constant of f. Using Lemma H.5] with a slightly different notation and Lemma (let = mn) where μ u² < V1 provided that the element -iie neural network is small enough, we have
Proof.
Σ (t,))s*
XXxx
Σ e Xxx)
|Sq
|s|
(WJES
4u
+ 12 21 + u2 In (mn)
12 02 In pt 2
1/3
+ nel
mn
mn
Vmn
+ 11T
+ +151+199) v min (1S), (89)
(15) + 154t)
1
+ 3TT
In
|S||50
|S||59
5
1
Σ 8 (Xir
|
+ Cymev' minuimmlie In (mn)
C2mpp(mn))82 SS
v 02 In In
|
11 /min (1S), (S+1)
mn |S
+ 3T/
In
S S
5'
(16)
where Cj and C2 are some fixed constants,
Jaw II aq
La
2/3
3/2
of = (1) |X| X||=VInD D
a1
(1.) sSoD2
0/g Lej - (T Lw ox) m²n²
(ITLa bi) max of
and
b
|c||Sc]
| Note that v/ > holds trivially because || F (II ai) (II b1) 1. Rename
of and v/g as and respectively, we finish the proof.
I PROOF FOR THEOREM 3.2
Proof. For convenience, let ((X) 11
Easeem x(x) P(X,,, 2g(X)
mm
E(iees Pij 1(( 81j). L(X')
mn En.eeem x(m) ((Ni,. X(y), and CX(X')
E E(id)s mappy
[S] ((X X1y) 1. E(ieess Pij ((X,,, 81)).
19

---

Published as a conference paper at ICLR 2024
[x()) - ((X')
Σ
(((X,), X1)) - ((Xig, 833))
mn (u)e(m]]x(o)
1
Σ
((Xij. Xzj) e(Xij, (tx)
(17)
(m.))
n
Σ
Xis X
(k.)) x[1]
I de
| 1
Vmn
1 -
Σ Pij
(8(X1,, X11) ((Xis X.i))
mn
(KJ)SS
Σ
Pij
((Xig,
X()) e(xu, {10
(KS))
Pij
X1j
X1
(18)
(3,))S
Tl mn
-2 Σ
Σ (1.))S
X13 - Xis -X:s
Pij
(1J)SS
Ne Σ E(.i)ss Pij
| -x-II
mn
According to the definitions of 45
(X')') and ((X'), we have Es [5((')) = -(X'). We also
have
|8|
((Xix- X17)
Te
A Taj-
manpis
mmpps
Lemma 1.1 Hoeffding 1963)). h Let X = (I1, I2......... 2N) be a finite population of N points and
X1, X2, Xn be random sample drawn without replacement from X, where a, Xx by i == 1,2, n. Then for all = 2 O,
1
2n²E²
P
x.
s exp
(19)
1= (b; ax)
where μ 1 Ei Tt is the mean of X.
According to Lemma
we have
18
P c(x) -
-5 cx((') 20] S2exp
(20)
2 2 DiSseess 73
Using union bound for all X' S', we get
1
(- 2 E0.)) 7i
P sup X'ES!
((X') - 2 (X)) 26 21/S0
(21)
Letting
2 " + In(mn)('(), then with probability at least [Sp
2 we have
2 Einees T
sup X'
((X') (X''' <
|5|2
In(mn]())).
(22)
20

---

Published as a conference paper at ICLR 2024
Now with probability at least 2 have
[(x) (X)
sup
Ess
(Xx) - ((X') + ((()) -3 +
(3 -
< sup
EEs
2 2 EisiEs T
me vey Liidess Pij
S sup
n Xes vmn
X 1 1
In(mn)
sup XEs
| 111
|S|2
mn
V EisesssPi =2
EG.iEss Pi5
Tt
Snpe
v (nn(m))
\mn
mn
mm
(23)
Note that In |'|
IN,
[]m,e), then In S'
2²
V1
02
In
where
2/3
3
((10--1) X 1 In 2D (II' fow oi)
Lar
q
Te b1).
"1
U2
ai
Ee p1pt-1, and by 6wep/w-1pl 1llllpp ||
(II bw
ai)
(T bi)
max b/b,
Then we
rive at
sup ((X) - CS (X)
Aes
ELSEESSP Pij
Tey Euiees Psp
20 2 (ln(mm)
Smpe
20g In
Vmn
mi
mn
6²
Σ ELsnES Pij mn
Pij Tey Euses Pij
(V2ln(mm) + /201 + 200 In 1/3
Sipe
Vmn
mn
EGSnES Pij
TE Euiees Pij
(Civii + C2y un
SnEc
Vmn
mn
mn
E Eisies Pij
Cinyy Eusess' Pig Voi
C2TON Eiisess'
1
17
Ste
+
122 In
Vmn
mn
mn
mn
TV
EGSees Pij
Σ
ThE Eones Po Pij Po o
C Easees Pij PT) mn
1
ne2l
STe
+
U/ In
Vmn
mn
mn
Te
(24)
where we have let c
C₁. CT, C2 and C Then we rename v/. v/g Cf, and C as Un Vs. C₁ and C%2, respectively. This finished the
numerical constants, v/ -ei U/s
a - U3. proof.
PROOF FOR THEOREM A.
Proof. Note that
IC(X) - (x)) [(() Es (Xx + (x) - EsIC (x))l
(25)
Then need bound |((X) Es and | (x) Es respectively.
21

---

Published as a conference paper at ICLR 2024
We have
[C(X) - Es(c5(X))
1
Σ
((Xij,
Xis)
E
Pu P X.1)
mn
min (4.)) x(m]
Pig
(26)
Σ
Pij
((Nu;; Xis)
mn
Pij
(t.))(mm) x mx)
Σ
Pij
mn (1.))(m]x((l
Pis
It is worth noting that the procedures of bounding (x) - EE(C5( are the same as that of [C(X) (X)) in the previous section. Therefore, we have
(x) - (=s(c(()))
Eiwees Prg mn
Eanes PTj
(27)
(Cinev + C.T V u2 vn T
Vnn
mi
where meanings of C₁ Cj U1 12, and n3 are the same as those in Theorem 3.2
Now combining equation 26 and equation 27 arrive at
[x(X) cf(())
Σ E(JJ)E 2-2
/mn + V Eusys Prj
(Ciner + CGRVezlnn +
(28)
+ Tt.
Σ
Pij
mm [m
Pij
which holds with probability least
2.
This finished the proof.
mn
K PROOF FOR LEMMAS
K.1 PROOF FOR LEMMA
H.
Proof. Let So. (0, E R
|0/12 b, |rll I 8)) VI E [Te]. It known that there
exists an ei-net So, obeying
W(Se. (1,9)) < 35/ P-P--1
22

---

Published as a conference paper at ICLR 2024
such that | Orl|s 2 qt-
We have
hij hig [4j hig
=10LG 0 Lo
Lo
(- ))}
= 10L00 (1
1 L0 4ij) ...)
+ 1LD ( (00-
O Le (14)) ...)) +...
+ O0. (0.0
(1 (14)) ...))
O Le
+ Le
(0.--(1-..0 ...)) |F
< 1 0 (0.-1
θ Le (0
+
O
(01-1(--00000)) ...) +
θ (
O (0..-1(-..00
OOO σ ( Lo-o-11 (0)))) ...)
θ Lo
La-1
|yyl
L Le OLol1
|
Le-2
+ o Lo- |لرد||
|| 1
||||
1 2 LL- 1|
O +
Le ||| 2
+ 0 1-11 |ayl
0illr
1-2
+ 0 _ 1||zij Aاgle FF II Or1l2
Les
Les
8513 Le
II
bi + 85y LL--
II by 82, f
|| - -Esgl1
lift
1/T.-11
If1
(29)
In (a), we used the facts |Xyllr It follows that
S ||a1lll and (|o S el| YI1F recursively.
[ H|F
Σ (his h2g)2
2
(a)
Le
Les II by 1=1
S 0
-1
Σ 2
$zij
2
CLo II b + CLa-1
II L
by +
6
bt
+
||
- 23
ij
I#L
1=1
La
Lo
2
= -220-o-1
CLe II lfLe
bi + CLo 1
II
b +
|| 1- +
II by 1=1
2 213
1
Le
Le
2
<V20-0-1
ELe
II bi + ELe-1
II 1-
bi + ........
b1
52 +
by
e
Lf
1
(30)
c/(vDLo)
In (a), we used the fact (x + 3) < 2(x² + v²) Let c =
vI E [Le]. Let
V2
II bk
2/V2
E V20
We arrive at
1=1 by
H - - Sc.
(31)
23

---

Published as a conference paper at ICLR 2024
It means that H is c-cover of H. Then the covering number of H. is bounded as
N(H, ()
Le
SN(2,1 -1I,,
II
(S -IE,,e)
1=1
L
6. Los=b, IIA bk))
Pm--1
<ig
II
(32)
lm1
Lo
Le be PIPI-1 6
Ni
1=1
Ce
Ei= PIPI-1
Sig
where Cg = 6g-e--111- Les
7
I1 by and y maxi BibT" This finished the proof.
K.2
PROOF FOR LEMMA
Proof.
It is easy show that 8= be determined by the following derivation
Z r
W Low
(ow
ow (W, ... ...
(33)
Lw
S ppw X
ag
$2
(34)
1=1
Combining Lemma H.l and Lemma H.2
we have
In.(H, || (r,c)
Li
Ce
< <Inke +
Σ Pipi-1
In
402(Lw -1) 1) 12 (elleo-1)1 1)|| |X| In 2D2
Law
Lw
2/3
II
af
a
II b²
(35)
22
Le
11
F
I at)
(I by
maxi
Σ pipt
ln
K.3 PROOF FOR LEMMA
Before proof, give the following lemma, which is variant of the Dudley entropy integral bound on Rademacher complexity. Before proof, we give the following lemma, which a variant of the Dudley entropy integral bound Rademacher complexity.
Lemma K.1 (Theorem 3 of (Schreuder) 2020)). Let F. C {f ; - RR} be any class of measurable functions containing the uniformly zero function and Bs(F) =supjez (lf() Then
12
Bz(F)
Rs(F) < inf a>0
4a
(36)
VSJ.
In Schreuder 2020). [fflag(P))) is defined as / [1 = E f(X,) which implics
(TFa))(P)).)) N(F, |1r, -
(37)
24

---

Published as a conference paper at ICLR 2024
It follows that
12
(B(FF)
Rs(F) & inf a>0
4a
V Vog 11 (ill-llll 11.,, vs(ids
VS
(38)
Bs(Fivs
4a
12
inf a20
/logA(FF,11 || e)de
VS
Now prove Lemma H.4
Proof. For convenience, let
Lw
Lw
2/3
3
Le
2 = ()) In 2
II af
Σ
11
1=1
02 = Els
Lis P:PI-1, and vy
6Leptu- g
|
||
[
Lw ai)
(T bi)
max, b₁6,
Then
In (H, ()r
In
from (35). Let f maxHEH
H oo. According to equa-
2
tion
38 we have
4a
12
PVS
14 /=-103 D3
RH) < inf
+ 02 In
de
VS
S
6
1 1-
IVB
4a
12
MW5
+ 11202
inf
U2 In
Dyy de
V
5
22
(6)
4a
12
WWS
V11 + 1222
inf
v In 10s de
VS
S
J.
(39)
4a
12
Vei + 1222 u22 In HVS Vuz In In los (av5-a))
inf
V
5
(c)
12 12 01 + 1220
12 1) 02 11
S 5
+
In
S
SVS
4t
12 01 + u In
12 In 1v3
S S
S
VS
In (a), we used the fact In S
xr. The inequality (b) holds according to va + S v + vv. In (c), we have let a = which though may not be the best choice. We arrive at
V5.
4p + 12 01 + 2 In + 12p U2 In In Inp
Rs (sH.) &
s
S
VS
25


Reviews:
[{"review_id": "Ovk9apkArL", "reviewer": "Reviewer_uVGT", "summary": "This work proposes a neuron-enhanced autoencoder matrix completion (AEMC-NE) method and applies it to collaborative filtering. AEMC-NE can adaptively learn an activation function for the output layer to approximate possibly complicated response functions in real data. The theoretical analysis and numerical results demonstrate the effectiveness of AEMC-NE in comparison to other methods.", "questions": "1. As shown in Fig.1, for the autoencoder, items correspond to samples while users correspond to features. Can we exchange the roles of items and users? What is the possible impact on the recommendation performance?\n2. On page 4, it is stated that when the mechanism is missing not at random, the $Q$ in the objective function should be replaced by $S$. How to achieve $S$?\n3. On page 7, is it possible that $\\sqrt{\\frac{L_W^3 \\zeta \\bar{d}}{n}}$ is larger than 1? It would be much better if the authors can provide an example of the value of $L_W^3 \\zeta \\bar{d}$.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. The proposed algorithm is interesting and effective. It has lower RMSE than the compared method in the experiments of many benchmark datasets.\n2. The theoretical results are rich and nontrivial. Theorem 3.1 and Theorem 3.2 shows the generalization error bounds of matrix completion in the settings of MCAR and MNAR respectively. An appealing theoretical result is that ‘Filling the missing values with zeros is helpful’. This is an important result for collaborative filtering.", "weaknesses": "Please refer to my questions.", "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": "", "extra_scores": {}}, {"review_id": "Ov6RbQGggB", "reviewer": "Reviewer_fbH8", "summary": "The paper studies the problem of matrix completion with neural network, which is quite different from classical low-rank matrix completion. The authors proposed a new method as well as theoretical analysis. The experiments on synthetic data and real data demonstrated showed the usefulness of the proposed method.", "questions": "* Do the two theorems provide any guidance for determine the architectures of the two autoencoders?\n* According to the formulation of the proposed method, both the layer-wise network and the element-wise network can be any MLPs, not necessarily autoencoders. Right?\n* In Analysis B of Section 3.1, is it possible that mean filling is better than zero filling for $\\tilde{X}$?\n* In Analysis C of Section 3.1, the authors only discussed the impact of $n$ on the generalization bound. What is the impact of $m$? A larger $m$ leads to a tighter bound?\n* In Section 5.1, the latent dimension of the data generating model is 10, but as shown by the caption of Figure 2, the latent dimension of the layer-wise autoencoder was set to 30. What is the motivation of this setting? \n* How to apply the proposed method to the collaborative filtering problem in the case of implicit feedback?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The theory of neural network based collaborative filtering hasn’t been well-studied in literature. This paper proposed a new autoencoder matrix completion method and analyzed the generalization ability for different missing mechanisms. The strengths of the paper are as follows.\n* The paper is well-organized. The literature review and related work are complete.\n* The paper provided two theorems. The analysis and results are solid.\n* The experiments are sufficient. The new method has been compared with more than five baselines on synthetic data, MovieLens 100k/1M/10, Doban and Flixter. And the performance is good.", "weaknesses": "Several minor issues are as follows.\n* It is not very clear how to determine the architectures of the two autoencoders. Is there a rule of thumb?\n* Some claims should be explained more detailedly. For instance, in the discussion for Theorem 3.2, more explanation about ‘$\\sqrt{\\sum_{(i, j) \\in S} p_{i j}^{-2}} /(m n)$ is at the scale of $1 / \\sqrt{|S|}$’ should be provided. In Table 2, a few results are missing. Why?", "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": "", "extra_scores": {}}, {"review_id": "ONwSzVJSd5", "reviewer": "Reviewer_fr12", "summary": "The paper presented a neuron-enhanced autoencoder based method for matrix completion. The main idea is to adds an element-wise autoencoder to each output of the main autoencoder to enhance the reconstruction. The paper has both theoretical results (generalization bounds) and numerical results (collaborative filtering).", "questions": "1. In Eq.(2), the loss function is the square loss. Has the authors tried other loss functions such as the absolute loss? Is the proposed method applicable to the setting of implicit feedback?\n\n2. In Figure 1, is there an activation function in the output layer of the main network?\n\n3. In Theorem 3.1, when $|S|$ or $|S^c|$ is close to zero, the bound is very loose. How to explain this phenomenon?\n\n4. The results in Figure 2 look nice. But the motivation for the specific network architectures such as 300-100-30-100-300 should be illustrated.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The proposed network architecture is composed of a main autoencoder and an element-wise. The idea is new.\n\n2. There are two theorems of generalization analysis. One is for the case of missing completely with random, and the other is for the case of missing not at random. They verified the effectiveness of the proposed method theoretically.\n\n3. The paper included a lot of experiments and the proposed method outperformed many baselines in most cases.", "weaknesses": "1. The writing style could be improved. Currently, the section of experimental evaluation focuses on collaborative filtering. To be consistent, the section of introduction should provide more information or discussion about collaborative filtering rather than matrix completion. \n\n2. The time costs haven’t been compared, though the theoretical analysis was provided at the bottom of page 4.", "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": "", "extra_scores": {}}, {"review_id": "jsdPi24iB8", "reviewer": "Reviewer_THxa", "summary": "The paper proposed an autoencoder method for matrix completion and applied it to collaborative filtering. The corresponding generalization error bounds are also provided. The experiments showed the superiority of the proposed method over the baselines.", "questions": "1. According to equation (1), is the model $f$ actually a denoising autoencoder, with a partial reconstruction loss, not a classical autoencoder?\n2. How does the data dimension $m$ affect the generalization error bounds? The authors only discussed $n$, the number of samples.\n3. Regarding Theorem 3.2, if $p_{ij}$ is close to zero, is the bound useless? Could the authors give more explanation about the roles of $p_{ij}^{-2}$?\n4. Are the values in Table 1 RMSEs?\n5. In Figure 2, it seems that if the middle layer width of the main network is set to 10, the true latent dimension of the data, the performance of AEMC-NE is not better than those with larger width. What is the possible reason?\n6. As shown by Table 2 and Table 3, the proposed AEMC-NE outperformed AEMC with ReLU output. Did the authors test AEMC with other activation function, such as sigmoid, in the output layer? How about their performance?\n7. In Table 5, as the observation probabilities are known, what objective function have the authors used in the proposed method? The one in (9) or (7)?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* This is a good work with new method, theory, and extensive experiments (many datasets, settings, baselines, and figures). \n* The motivation is clear and the theoretical analysis, such as the bounds related to MCAR and MNAR, are insightful and practical for the recommendation systems.\n* The proposed AEMC-NE is able to outperform SVD++, LLORMA, AutoRec, DMF+, etc.", "weaknesses": "* The time cost of the proposed method AEMC-NE is higher than that of AEMC.\n* The motivation of conducting the experiments of Table 4 is not clear.\n* Some important results (e.g., time costs comparison, Theorem A.1) are presented in the appendix, not the main paper. Theorem A.1 is more useful than Theorem 3.2 because the former is based on the estimated probability.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)