Multi-Mode Deep Matrix and Tensor Factorization
Authors: Jicong Fan
Venue: ICLR 2022 Poster (2022)

Abstract: Recently, deep linear and nonlinear matrix factorizations gain increasing attention in the area of machine learning. Existing deep nonlinear matrix factorization methods can only exploit partial nonlinearity of the data and are not effective in handling matrices of which the number of rows is comparable to the number of columns. On the other hand, there is still a gap between deep learning and tensor decomposition. This paper presents a framework of multi-mode deep matrix and tensor factorizations to explore and exploit the full nonlinearity of the data in matrices and tensors. We use the factorization methods to solve matrix and tensor completion problems and prove that our methods have tighter generalization error bounds than conventional matrix and tensor factorization methods. The experiments on synthetic data and real datasets showed that the proposed methods have much higher recovery accuracy than many baselines.

Published as a conference paper at ICLR 2022
MULTI-MODE DEEP MATRIX AND TENSOR FACTOR- IZATION
Jicong Fan
1 School of Data Science, The Chinese University of Hong Kong (Shenzhen), China Shenzzen Research Institute Big Data, China fan Fanjico canngeekkkkk edd..cc
ABSTRACT
Recently, deep linear and nonlinear matrix factorizations gain increasing atten- tion in the of machine learning. Existing deep nonlinear matrix factorization methods can only exploit partial nonlinearity of the data and are not effective handling matrices of which the number of rows comparable to the number of columns. On the other hand, there is still a gap between deep learning and ten- sor decomposition. This paper presents a framework of multi-mode deep matrix and tensor factorizations to explore and exploit the full nonlinearity of the data in matrices and tensors. We use the factorization methods to solve matrix and tensor completion problems and prove that our methods have tighter generalization error bounds than conventional matrix and tensor factorization methods. The experi- ments synthetic data and real datasets showed that the proposed methods have much higher recovery accuracy than many baselines.
INTRODUCTION
Low-rank matrices and tensors are pervasive in sciences and engineering. Low-rank matrix com-
pletion (LRMC) (Srebro & Shraibman, 2005 Candès & Recht 2009 Recht 2011 Hu et al.] 2013)
Hardt 2014 Chen et al. 2014, Shamir Shalev-Shward Shwartz 2014
Sun & Luo 2016 Fan & Chow
2017
Fan et al.] 2020 Kümmerle & Sigl [0188 Fan al. 2019) and low-rank tensor completion
(LRT (Gandy et al. 2011 Acar et al.) 2011 1 Liu et al. 2012 Kressner et al. 2014, Yuan ZZhagg
2016 Foster & Risteski (019), shown in Figure [ aim recover the missing entries of low-
rank matrix or tensor. LRMC and LRTC are very usefully in data preprocessing, image and video inpainting, and collaborative filtering (Fan Cheng 2018 Liu et al.) 2012). For instance, in collab- orative filtering (e.g. the recommendation problem of Netflix, the rating matrix given by users on items often highly incomplete because each user can only rate a few items and each item is often rated by few users. If the unknown entries of the rating matrix are predicted, recommendation can then be made, accordingly, for users or items. Since rating matrices often have potentially low-rank structures, we can use LRMC or even LRTC to recover the missing entries for recommendation.
Completon
Completion
Figure 1: Intuitive examples of matrix and tensor completion (black square indicates missing value).
Notation Throughout the paper, 'x', 'x', 'X', and XX" denote scalar, column vector, matrix, and tensor respectively. ()> (or 'X," denotes a matrix with index j. || || denotes the Frobenius norm of matrix tensor. -| ll denotes the nuclear norm of matrix, i.e. sum of the singular values. || lao denotes the maximum absolute element in a matrix or tensor. 'C X, A' denotes the j- mode product of a tensor C with matrix A. Pa denotes the projection onto the set Ω, i.e., (Pa(X))i = [Xis (i,j) E and [Po(X)] )es 0 otherwise. [S2] denotes the cardinality of Q. g(.) denotes activation function and by denotes the number of units in layer of neural network.

---

Published as a conference paper at ICLR 2022
LRMC In the past decade, a lot of algorithms with theoretical guarantee or/and empirical success have been proposed for LRMC. For example, (aadde & Recht (2009) proved that a low-rank matrix can be recovered exactly with high probability from few entries sampled uniformly random, via nuclear norm minimization. Nie et al. (202)) proposed to minimize the Schatten-p quasi-norm for LRMC. Nuclear norm and Schatten-p quasi-norm minimizations are based on singular value decomposition and hence have high computational cost when the size of the matrix is very large. In addition, they do not incorporate the rank prior that are possibly available in practice, though could
be inaccurate. In contrast, low-rank factorization based methods (Srebro & Shraibman 2005 Srebro
& Salakhutdinov 2010; Wen et al. 2012 Hardi, 2014 Sun & Luo, 2016 Ji et al., 2016 Shang
et al. 2016) are scalable to big matrices and can provide high recovery accuracy if the factorization
size is properly determined. In fact, regularized matrix factorizations are closely related to nuclear
norm and Schatten-p quasi-norm minimizations. For example, it is known (Srebro et al., 2005
Rennie & Srebro 2005) that ||X minAB=X For LRMC, we can solve
|||] B = minAB-X
B
minimize A.B
3 1P - AB)I
À + [B
(1)
2
where A E Rm B E Rdxn and 0 d S mi, n). Interestingly, Gunasekar al. 2017 found and proved that gradient descent for ① with À and d = m = n converges to the minimum nuclear norm solution, provided that the learning rate is small enough and the initializations are close enough to the origin. Fann et al. (2019) proposed a class of rank regularizers called factor group sparse regularizer (FGSR) the variational forms for Schatten-p quasi-norms, e.g..
min 1 -| + a +aIlBll 1 =(1 + 9/(41)))+11) X
(/((+))) S4/(0+1>*
x x=AB q
where 0 and g {1, 2. J ...... When q one gets Schatten- 1/2ttennn112 quasi-norm. Later, Giampouras et al. (2020) extended the variational form to arbitrary p E (0, 1].
1/2
LRTC A few LRMC methods have been directly extended to LRTC (Acar et al. 2011 Liu al. 2012 Kressner et al. 2014). One may categorize LRTC algorithms according to the different tensor
factorization models such as CP (CANDECOMPPPARAACC) decomposition (Kolda & Bader 2009
Jain & Ohl 2014). Tucker decomposition (Xu et al. 2013, Xie et al.) 2018). tensor singular value decomposition (Kilmer et al. 2013 Zhang & Aeron 2016). and tensor ring decomposition (Zhao et al. 2016 Huang et al. (020)) Take the CP decomposition based LRTC as an example, one can just learn a CP decomposition from the partial observations (Acar et al.) 201T). Yuan & Zhang (2016) provided the sample complexity for the exact recovery of LRTC via nuclear norm minimization,
though the optimization is intractable because computing the nuclear norm of a tensor is hardard (Hillar & Lim| 2013). Barak & Moitra (2016) and Foster & Risteski 2019) exploited the sum-of- squares hierarchy for LRTC and provided theoretical guarantees for the recovery. Razin et al. (202T) studied the implicit regularization in tensor factorization and proved that gradient descent with small learning rate and near-zero initialization gives rise to a bias towards low tensor rank solutions. Liu al.) (2019) introduced convolutional neural network tensor completion. The method can model the possibly complex interactions inside tensors while preserving the desired low-rank structure.
To complete a third-order (w.l.g) tensor based on the Tucker decomposition, we may solve
X X.Ai, A,, 2
minimize
| - x A X2 A X3 Aal subject to Pa(x) = Psx()),
(3)
where we can also consider regularization or constraint on the factors A1, A2, As. and C. For instance. Xu et al.) (2013) reformulated ( all-mode matricization and solved the problem by alternating minimization. Xie et al.] (2018) proposed to minimize the number of nonzero elements of C and the ranks of the matricizations of X, addition to
Deep Matrix Factorization Recently, deep matrix factorization (DMF) (Fan & Cheng 2018 Arora et al.] 2019) gains increasing attention in machine learning. There are two types of DMF methods: linear DMF (Trigeorgis et al. 2016 Zhao et al. 2017 Arora et al. 2019) and nonlinear
DMF (Xue et al.
2017 Wang et al. 2017 Fan & Cheng 2018). A general formulation is
X R 91 (A192 (2 -LL-
(4)
2

---

Published as a conference paper at ICLR 2022
where (9. M are activation functions. When all 9, are linear, 4 is linear DMF. Otherwise, is nonlinear DMF. Arora et al. (2019) found that adding depth to a linear matrix factorization can en- hance implicit tendency towards low-rank and can provide higher recovery accuracy than depth-2 factorization, though the implicit regularization in linear DMF may not be captured using simple mathematical norms. In (Fan & Cheng, 2018), the numerical results showed that nonlinear DMF is able to recover (with high accuracy) the missing entries of a full-rank matrix of which the columns are generated by nonlinear low-dimensional latent variable model.
Contributions of this paper This paper first provides theoretical analysis for why and when non- linear DMF outperforms linear DMF in matrix completion. Second, this paper proposes a new matrix factorization method called two-mode nonlinear DMF. The method can exploit the full non- linearity of the data while classical nonlinear DMF uses only partial nonlinearity of the data. Third, the paper presents a new tensor decomposition method called multi-mode nonlinear deep tensor fac- torization, which can regarded as a high-order generalization the two-mode nonlinear DMF. Finally, the paper shows that the multi-mode deep matrix and tensor factorization methods have tighter generalization error bounds than conventional factorization methods matrix and tensor completion. Extensive numerical results verified the effectiveness of the proposed methods.
2 WHY AND WHEN DOES NONLINEAR DMF OUTPERFORM MF?
Nonlinear DMF methods can outperform linear MF methods empirically in many real tasks such collaborative filtering (Xue al., 2017: Fan & Cheng 2018), image inpainting (Fan & Cheng. 2018), and disease modeling (Wang et al. 2017). The fundamental reason is that the data matrices these tasks indeed have some nonlinear structures that cannot be exploited by linear MF methods. Nevertheless, in nonlinear DMF, the theoretical guarantee is very limited. In contrast, linear MF or even linear DMF have been well studied and guaranteed with sample complexity (Hardi, 2014 [Sun & Luo 2016; Jin et al. (016)) generalization bound (Srebro & Shraibman 2005 Fan et al., (019), or convergence (Gunasekar et al.) 2017 Arora et al.) 2019). In this section, we will provide some theoretical guarantee for nonlinear DMF in matrix completion.
Assumption 1. Suppose Y X + E, where Y R The columns of X are generated by
f().
where f Rdd - R. denotes a nonlinear mapping, d < min(n1, R2), and E RRd denotes latent variable. The entries of the noise matrix E are drawn drawnfrom o0,
Suppose we observed a few entries of Y randomly (sampling without replacement) and want to recover X from the incomplete Y. Consider the following method (Pan Cheng, 2018]:
W 2 + A Z (5)
minimize Wi....WL. Wi.Z
1P WLo(WL-1 - (W,Z) )) +
5
2
2
where Z E Rdxxa Wi R 1-= 1...., L. hy n1. ho d, and h-1 12- Au and X are regularization parameters. Here we have let all activation functions the same without loss of generality and omitted the bias terms of the neural network for simplicity. According to the universal approximation theorems (Cybenko, 1989 Pinkus 1999 Lu et al. 2017 Hanin & Sellke 2017), f can be well approximated by the neural network provided that L is sufficiently large at least one is sufficiently large. The following theorem provides the excess risk bound for (5). of hi,..., hr,-1
Theorem 1. Suppose Z and (WiJf= are given by (5) Lei X
Suppose Z IT= [|[ll K, m oc, X (|xc) S &, the Lipschitz constant of g n. Let N 122 Then with probability at least 1 2N-1 there exists numerical constant e such that
ELen hyly log(n -g---(g)))))))
1
X
<
P - X)II= +
E F + og
[22
In Theorem the last term of the RHS of the inequality equivalent to
L-1
f = -5((1) + -1-111 1111 +
Σ
hyh4 log(n) -1g-")=))
(6)
3

---

Published as a conference paper at ICLR 2022
Most major activation functions (c.g. ReLU and sigmoid) are, at worst, 1-Lipschitz with respect to lg norm, which indicates that 77' is not large. When f2 is large enough, úi is linear with the latent dimension d of the columns of X when using (5). In practice, it is difficult to know the true d in advance. But the Frohenius norm regularizations on and W1 are able to reduce the nuclear norm even the rank of W, Z theoretically, which means the d in formulation (5) and Theorem can be larger than the d (ground truth) in Assumption !
Note that classical MF (depth-1) is special case of when L and g is linear. However, because of the nonlinearity in the data generating model of Assumption [ the rank of X can be much higher than the intrinsic dimension of the data, i.e. r = rank(X) > For example, if f is q-order polynomial function, r' can be large as (d+1). For classical MF, the last term of the RHS of the inequality Theorem reduces to
4/2 = <l (E(2) + rm2) log(5-+ 1/4
Here s' may be less than the in (6) but they are in the log operator. Suppose all the Frobenius norms are the same (the worst case, may not happen because the norms of the factors in a deep factorization are usually smaller than the norms of the factors in shallow factorization), denoted by 3. Then R = =3L+1 and x = B², but r > d. In the experiments, we observed that x z (x/)1.3 when J, and K. = (x''1.7 when L = 3, which are much better than the worst cases. Now comparing 7 with (6) we conclude that the nonlinear DMF provides a tighter generalization bound than the classical MF when 12 is much larger than ŋ1 and E/= 4--1 hihh-1 is not too large. The second condition is realistic because we usually let .i,.... h1.-1 < 11 or we can just assume li,,..., <r.
Consider the case that n2 is not large compared to n.. e.g. 122 n1. In (6), suppose d = r/2, = 3, h1 = 2d, h2 = 3d, and v = 1, we have th1 = < (112) (122)= + 2r²) log(r))) 1/4 and 4/2 = =<(((2)-122ng)) (eengr))o(ge log(x')) 1/4 where 1h > 4/2. It means the upper bound given by the classical MF is tighter than that given by the nonlinear DMF. In general, the superiority of the nonlinear DMF over the classical MF increases when n2/n2, increases, which is consistent with the numerical results shown in Figure of the appendix.
3 TWO-MODE NONLINEAR DEEP MATRIX FACTORIZATION
Data matrices in many problems are square or nearly square, which restricts the capability of nonlin- ear DMF. For instance, the difference between the width and height of an image is often small. The covariance matrices and graph adjacency matrices are square matrices, In recommendation system, the number of users and the number of items may be of the same order of magnitude. covariance matrix or graph adjacency matrix may be constructed naturally by data with nonlinear latent struc- tures. Similarly, one may imagine that the rating given by a user on an item an interaction of the user's features and item's 's features and the features may have some nonlinear low-dimensional latent structures. The nonlinear DMF in (5) exploits only partial nonlinearity of the data.
Formally, make the following assumption.
Assumption 2. Suppose Y = X + E, where Y E R and X UTQV. The columns of U e m. x and V E R are generated respectively by
u ==(zz and v = [2(s),
where fi 12h + Rd and fz : 2d + Rm are nonlinear mappings, d1 < +min(m1, n1), d2 < min(my, n2), and z E Rd and E d2 denote latent variables. The entries of Q E R mmmixma and E E R xn2 are drawn from (0,, oz)) and A (0, o2g) respectively.
Suppose we have a matrix Y given by Assumption 2
we can factorize it as
Y z Ú QV, ú, (2,,), 0 (s.,), i 1, ... n1: 12 1, ......... , (8)
In 8 fo, Rd
m and fo, Rdd - Rm lalti-layer neural networks with parameter sets 0, (W ..... ((')) and 0₂ = { (w(2) ..... (2) ). where w(() denotes the weight matrix in
the i-th layer of neural network j. and L, denotes the number of layers of neural network j.j 1,2.
4

---

Published as a conference paper at ICLR 2022
W22
5
@
Figure Two-mode nonlinear deep matrix factorization
We call two-mode or two-way nonlinear deep matrix factorization. Figure 2 shows intuitive example (8) with depth-three factorizations both directions.
Suppose observed few entries of Y randomly (sampling without replacement). Based on Assumption we propose the following matrix completion method
minimize 2.Q.8.01.02
PPPaYY fe, (Z) Qfee (S) R(Z,
(9)
where
fe, g(WL.) 9 (w (1)
L1-1 (w 2).
(S) g(W(() (2)
La 9 (2) 9. (W S)...) .3...)..
and Z E Rdixni S E Rd2xns, w E R x
1, 1,..., Lgj 12, mj, 1. = dj.
h nj. j 2, and Q Xma, We have let all activation functions be the same with- out loss of generality. In 9 R(-) regularization operator to reduce overfitting. For instance,
R Z, Q. 81, 02) A1
(1Q113 + Ewee, [W])). Compared to (5), X2
7 P-
||S|
9 exploits the full nonlinearity of the data. The following theorem provides the excess risk for (9)
Theorem 2. Suppose Z. S. (w
J (w Ha and Q given by
9 Let
X
fo, (Z) (S).
Suppose ||Q|E Z || I IT', |W
||
I Ki
max ||x X ||=)) < &, and the Lipschitz constant of g n. Let N n2 Then with proba-
bility at least 1 2N there exists numerical constant such that
1 VN
X 1 <
IPr
88]1
[2
mmi + +E E.e h (
(1)
()
m-1
of
[2
In Theorem 2 the last term of the RHS of the inequality can be written as
L
4/3 (( n2d2 + m2222 Σ
-og
(10)
When the h in 66 much larger than the di in (T), we have 4/s < wh- means the two-mode provides tighter generalization bound than classical nonlinear DMF 5).
nonlinear DMF 9
worth mentioning that one may formulate DMF in a two-sided form, e.g., X g ((w(3) 9( z"
X ~ g( g( ( (z) w()) equivalently. However, this model has two shortcomings compared to the one-sides sided DMF (4) and two-mode DMF (8). First, 4 and (8) are more compact (in terms of the number of parameters) than the two-sided DMF. For example, assume the sizes of X, ZL, and ZR are 500x 500, 100 10, and 10x 100 respectively, then the number of parameters in the two-sided DMF is larger than 100,000. In the one-sided DMF 4.. let X = (W W2g(W,2 (WzZ) and let the sizes of Wi. W2. and Z be 500x 100. 100x 10, and 10x500 respectively, then the number of parameters is 56,000, which is much smaller than that of the two-sided DMF. The other shortcoming is that the two-sided DMF difficult to interpret in real applications. In contrast, 4 and 8 much easier to interpret and more realistic.
5

---

Published as a conference paper at ICLR 2022
4 MULTI-MODE NONLINEAR DEEP TENSOR FACTORIZATION
In this section, we extend the two-mode deep matrix factorization to multi-mode nonlinear deep tensor factorization. First, make the following assumption.
Assumption 3. Suppose y = -,EE, where y E R X and X x For I....,k.. k. the rows of U x are generated by u(d) = ff(z(0),, where fj Rd 7 IRm nonlinear mapping, dj m2, and 2 I2d are latent variables. The entries of core tensor C [am]xxm">xxm and noise tensor E BBixng are drawn from (N, of) and NO0, oz) respectively.
xp UR.
Although {fi})=1. C, and { j== are unknown, we can take advantage of neural networks and tensor decomposition to model the data, i.e.,
y = è X1 U1 X2 U2 ....... X ÜR. Ü, fo, (2 i....,,,
(11)
where So, Rdd Rd, xd, is neural network with parameter set 0z. Figure shows intuitive example of the proposed factorization method for a third-order tensor. Different from Tucker de- composition, we perform nonlinear DMF on the factor matrices and do not constrain the norms of the columns of the factor matrices. This factorization method can take advantage of the nonlinear structures of the tensor fully.
2,2
C
U
0j
Figure 3: Multi-mode nonlinear deep tensor factorization
To recover X from few entries of y, we propose to solve the following problem
minimize (0,,26)) - 11 -c
Cxise, ( X2 X2 ( ........Jay So, 2 )1 R((().
(12)
and 0, (W(6) 1...., R()) denotes the regularization on the parameters, e.g.,
where fe, (Z(6) g(W Lo ( (WW (61)....
w
wl
Lj |w(
\ R(10,, 20) B-
d
3 +
|101
(13)
2
The following theorem shows the excess risk bound for 12).
Theorem 3. Suppose C and (0,, Z / are given by 12 Let X = C x1 fo, (z(1)) x2
fe, (Z ... X for (Z(k)) Suppose ||[|| F S Bc. || IF S 1 I,..., Lj. |2666 || S
a(1) j 1....,k, max ||=) S S, and the Lipschitz constant of 9 is nT. Let
N = -I1 ng. Then with probability at least 1 - 2N-1, there exists numerical constant c
such that
1X - x S
Panl - -x)
VN ||||
VN
(I1 + E o (())(( log L
11; I 2for
1/4
+ of
[
Remark 1. One can obtain slightly tighter bounds in Theorems and when using spectral norms instead of Frobenius norms. But in Frobenius norms explicitly. In addition, (12 and Theorem are also applicable to CP-like decom-
55) 9 and 12 the regularizations only control the
position based tensor completion isC super-diagonal.

---

Published as a conference paper at ICLR 2022
We see that Theorem 2 is special case of Theorem when k 2. Denote 2/ the last term of the RHS of the inequality Theorem
3 Since hi)) = d2 and h- = Mij we have
1/4
A m
Ji 1 m log (n T Bc '
R III
= [0]
|
nyd
+
==1
j=1
/=1|=
j=1/=0
(14)
If g is linear and L = 0. Accordingly, tt becomes
12
degenerates into the Tucker decomposition based LRTC, e.g.
1/4
R Engms) log (5 Bc m
V/s = of
+
301 ==1
(15)
1=1
j=1
Since m2 >> dj, we have 1/s 4/4. It means the nonlinear method (12) has tighter generalization enror bound than linear tensor completion methods. Therefore, we expect that (12) outperforms linear LRTC methods when the data have nonlinear structures. For convenience, in this paper, we call and 12 multi-mode deep matrix and tensor factorizations (MTD..F).
Optimization The optimization for and 12 are non-trivial because there are high-order ten- sors and neural networks with unknown inputs and incomplete outputs. We tried alternating mini- mization, nonlinear conjugate descent, L-BFGS (Liu & Nocedal 1989). iRprop+ (Igel & Hüsken 2000), and Adam (Kingma & Ba 2014), where all variables are randomly initialized from Gaussian distribution. It is found that iRProp+ outperforms other algorithms especially on real datasets. The details of optimization and the analysis of time and space complexity are presented in Appendix
NUMERICAL RESULTS
5.1 SYNTHETIC DATA
We use the following nonlinear model to generate matrices:
U ( o (W,")) sin(W Z)).
V= ? (o S)), x= UUUV, (16)
where Z 120 ( E 100X2 w(")
E 20000 W 300020 S 22x100 w
1002 2 E 20x 10 and w!!2) E 30x020 are drawn from 4(-1,1). a denotes the sigmoid fucntion. The exact rank of X is 20 but the smallest 10 nonzero singular values are close to zero. Such a synthetic matrix is realistic because the nonlinearity in real data may not be very strong and the matrices are often low-rank. Similarly, the following nonlinear model is used to generate third-order tensors:
U = a (W, sin ( (1) z())), = =x=exp(W W
2()))
(17)
U3= = cos( (3)
(3) exp( (spW(() (3) ()))),
X C x1 U1 X2 U2 X3 Us.
where (1) 2x50 w( R1Ux2
W 200100 (2) 2x50 w 10X2 w!
10 Z (3) E g2x50 (3)
E 100x and ((( E
I 20x 10 are drawn from 1)-1,1) and
1
C E 200 are drawn from 1). The exact n-rank of X is 220,20, 20) but can be well approximated by tensor with n-rank (10, 10, 10) because here the nonlinearity is not very strong.
First, we compare the proposed method with linear matrix factorization (MF ()) nuclear norm minimization (NNM) (Candès & Recht 2009). TNNR (Hu et al.) 2013)), HM-IRLS (Kümmerle & Sigl 2018), FGSR (Fan et al. (019), (stacked) Autoencoders (SAE) Sedhain et al. 2015), and DMF (Fan & Cheng 2018). We use the tanh activation function in SAF, DMF, and M DMTF. We determine the hyper parameters of all methods via cross-validation to ensure they perform as well as possible. Details about the optimizations and parameter settings are in Appendix B We use the relative recovery error (Fan al. 2019) 1P,,(X X)I || (X)( (X)]
F to evaluate the performance of matrix completion, where 12 consists the locations of the missing entries. Figure 4(a) shows
the average performance of 20 repeated trials when the missing rate increases from 0.8 to 0.99. MF
7

---

Published as a conference paper at ICLR 2022
and NNM have much higher recovery than FGSR. This result is consistent with the results of Fan et al. 2019 Arora et al. 2019). Although SAE is a nonlinear method, still has high recovery error when the missing rate less than 0.9. The reason is that filling the missing entries of the input of the encoder with zero introduces relatively large bias, which may not be eliminated effectively by the hidden layers. DMF and FGSR have quite similar performance, which is consistent with the analysis at the end of Section 2 Our DMMF outperformed other methods significantly especially when the missing rate high. The reason is that D*DMTF is able exploit the full nonlinearity of the data and has tighter generalization bound than other methods.
Figure 4(b) shows the performance (average 20 trials) of FaLRTC (Liu 2012). TenALS (Jain & Oh 2214)) TMac (Xu et al., (2033), KBR-TC (Xie et al. 2018). TRLRF (uaan et al. 2019), CoSTCo (Liu et al. 2019), OITNN-O (Wang et al. 2020), and M'DMTE. Since the rank of the tensor is quite low, M'Mac, KBR-TC, and M-DMTF have high recovery accuracy when the missing rate less than 0.96. Note that TMac and KBR-TC slightly outperformed M2DMTF when the missing rate is less than 0.96. The reason is that the optimization of M*DMTF is more difficult. In Figure (b), when the missing rate higher than 0.97, the proposed MDDMTF outperformed all methods largely. The optimization curves of DMTF are shown in Figure 7 of Appendix B
0.45
MF AAHA TYIN HIHRUS
0.45
FaLHIC
TMdac
KBB--T
Relaive recovery ema
0.95
Reloive ressvery crdr
0.35
ExtiCC
TRUFF
DITNNO
0.3
0.3
NROMMTF
0.25
0.25
0.2
0.2
0.15
0.18
0.1
0.1
0.05
0.05
0.32
0.54
0.98
0.38
0.58
0.54
0.55
0.56
Missing rate
Missing rate
(a) Matrix completion on data given by 16
(b) Tensor completion data given
Figure 4: Performance evaluation of matrix completion and tensor completion on synthetic data.
5.2 REAL MATRICES
We consider two benchmark datasets: MovieLens-1008 and MovieLens-IN MM. They consist of the ratings (1 to for movies given by users. The sizes ussvs)) of the rating matrices in the datasets are 1682 x 943 and 3706 6040 respectively. For each matrix (highly incomplete), we randomly split the known entries to a training set and a test set. The relative recovery errors (average of 10 repeated trials) on the two datasets reported in Tables Rablessaan@rreepecttvvyy FGSR, SAE, and McDMTF outperformed MF and DMF in all cases. When the training-tsst ratio is 9/1 or 7/3, SAE has less recovery synthetic data in Section 5.1 Currently, the MovieLens data. One possible reason is that the MovieLens data are quite noisy and SAE can successfully reduce the influence of the noise when the missing rate is relatively low. When the training-test ratio smaller, i.e., 5/5, 3/7, 1/9, M DMTF outperformed SAE.
than D'MTFE. This is quite different from the results the
unknown why SAE has such a good performance on
Table 1: Relative recovery error of matrix completion on MovieLens-
Train Test
MF
FGSR
SAE
DMF
M'DMTF
9/1
0.258410.0019
0.2483+0.0020
0.2518 0.2412
0.2445
7/3
0.2666=10.0011
0.251410.0009
0.2456110.0012
0.2551100.001
0.2469-0.000
5/5
0.2095+0000100
0.2575:L0.0011
0.2527-10.0008
0.2603-10.0014
0.0519
3/7
0.3039=000000
0.2679+0000009
0.2656+10.0004
0.2738+0.0007
0.2580
1/9
0.3940=000022
0.323
0.3028+100006
0.315740.0018
0.273110.0000
8

---

Published as a conference paper at ICLR 2022
Table Relative recovery error of matrix completion on on MovieLens-IN
Train/Test
MF
FGSR
SAE
DMF
M'DMTF
9/1
0.2278 10.0003
0.22481:0.0002
0.2239-10.000
0.2266:10.0007
0.2261 0.0001
7/3
0.2315=0.0003
0.2271#0.0001
0.2278=000002
0.2276=000001 0.2291+0.0002
5/5
0.2319=:00002 000000
0.2346=0.0003
0.2333=0.0002
0.2314=0.0001 0.2419++0.0003
3/7
0.2520+-0.0003
0.2379++000003
0.2458 0.2000
0.2364 0.0002
1/9
0.3226+0000008
0.2697+000011
0.2796++00006
0.2510 0.2573++000006
5.3
REAL TENSORS
We compare the proposed method DMMF with the baselines on the following datasets: Amino acid fluorescence (Bro 1997) (5 201 61), Flow injection (Norgaard & Ridder 1994) (12 x 100 x 89), and SW-NIR kinetic data (Bijlsma & Smilde 2000) (301 x 241 x 8). More details about the experimental settings are in Appendix B.2 The relative recovery error (average of 10 trials) are reported in Table 3 The results of FaLRTC and CoSTCo are not reported because they have much higher recovery eгтor than other methods in most cases and we want fit the table the width of the page. On Amino, our 2d DMTF outperformed other methods significantly in all cases. On Flow, when the missing rate 0.95 or 0.97, MDMTFF has much lower recovery error than other methods. On SW-NIR, DMDMTF has low recovery error consistently while most baselines failed totally.
Table 3: Relative recovery error three real tensor datasets (MR denotes missing rate)
Data
MR
TenALS
TMac
KBR-TC
TRLRF
OITNN-O
M'DMTF
0.85
0.0255.10.009
0.0025-10.001
0.0318
0.0486=000180
0.0348 2..001 10.0016
0.0189 10000007
Amino
0.90
0.1317+0.0208
0.0451 +0.0063
0.0358+0.000
0. 0.1004=0.0284
0.0684+0.0096
0.0213
0.95
0.3520+0.1633 0.4027+00023
0. 0.1370=0.0131
0.3941=0.102
0.2803
0.0354+0.0009
0.97
> 0.95
0.5209 10.0926
0.3192 10.0453
o.1110
0.5651 1.0.309
0.1387 1.003466
0.85
0.00444..0004
0.0128+000001
0.0028+0.00
0.0479
0.0253
0.0206:#0.045
SW-NIR Flow
0.90
0.0359 +0,0044
0.0132
0.0041 +0.0002
0.0619=0.011
0.045 10.004
0.0198
0.95
0.3495 18.1838
0.0716:+0.022
0.0695
0.3817=0.v66
0.1369 0.0088
0.0396
0.97
0.4141 1678
0..088
0.3627
0.5985 -0998500.100 1081
0.2617 0.0016
0.0503
0.85
0.2894+0.0190
0.0409
0.6546+000174
0.2425=0.028
0. 0..4644000309
0.0593
0.90
0.3427
0.8760++01229
0.6845++000227
0.3607=00066
0.4683
0.060 +0.0078
0.95
0.4175 10.0246
> 0.95
0.8334 10.0291
0.9146=0.00
0.8881 1.002311
0.0758 10.0023
0.97
> 0.95
0.8823
>> 0.95
> 0.95
>> 0.95
0.0862 10.0057
Comparative studies were also conducted on three larger datasets. The results are reported in Ap-
pendix B.2.4
The experiments of tensor completion based recommendation system are in Section The visualization of the learned tensor and factors of DDDMTF are in Appendix B.2.6
B.2.5
6 CONCLUSION
This paper has proposed framework of multi-mode deep matrix and tensor factorization. The proposed factorization methods can explore and exploit the full nonlinearity of the data effectively. We applied the factorization methods to matrix and tensor completion and provided the generaliza- tion error bounds, which verified the superiority of the proposed methods over conventional linear and nonlinear matrix factorization methods and linear tensor completion methods. The proposed framework reduced the gap between tensor decomposition and deep learning and showed that their combinations can provide better performance in tensor recovery. On some datasets, when the miss- ing rates were low, our methods did not achieve the best performance. The reason is that the non- linearity in the data is not very strong and the problem is not difficult for the baselines methods of which the optimizations are easier than our methods. Future work may focus on improving the optimization efficiency of M2DMTE.
Coodes link: httas///aaaaaaa..////////////oo.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
The work was supported by the research funding T00120210002 of Shenzhen Research Institute of Big Data and the Youth program 62106211 of National Natural Science Foundation of China.
REFERENCES
Evrim Acar, Rasmus Bro, and Bonnie Schmidt. New exploratory clustering tool. Journal of Chemo- metrics: A Journal of the Chemometrics Society, 22(1))91-100, 2008.
Evrim Acar, Daniel M Dunlavy, Tamara G Kolda, and Morten Mørup. Scalable tensor factorizations for incomplete data. Chemometrics and Intelligent Laboratory Systems, 106(1):41-566 2011.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix fac- torization. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and Gamett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Boaz Barak and Ankur Moitra. Noisy tensor completion via the sum-of-squares hierarchy. In Conference on Learning Theory, pp. 417-445, 2016.
Sabina Bijlsma and Age K Smilde. Estimating reaction rate constants from two-step reaction: comparison between two-way and three-way methods. Journal of Chemometrics, 14(5-6):541- 560, 2000.
Rasmus Bro. Parafac. tutorial and applications. Chemometrics and intelligent laboratory systems, 38(2):149-11) 1997.
Rasmus Bro. Exploratory study of sugar production using fluorescence spectroscopy and multi- way analysis. Chemometrics and Intelligent Laboratory Systems, 46(2):133-147) 1999. ISSN
0169-7439. doi:
Emmanuel J. Candès and Benjamin Recht. Exact matrix completion via convex optimization.
Foundations of Computational Mathematicx, 96):717777 2009. ISSN 1615-3383. doi:
00.10077/10208-009-90000
Yudong Chen, Srinadh Bhojanapalli, Sujay Sanghavi, and Rachel Ward. Coherent matrix comple- tion. In Proceedings of the 31st International Conference on Machine Learning (ICMI-114, pp- 674-682. JMLR Workshop and Conference Proceedings, 2014.
George Cybenko. Approximation by superpositions of sigmoidal function. Mathematics control, signals and systems, 2(4):303-314, 1989.
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:290 305, 2017. ISSN 0031-3203.
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 32, pp. 5104-5114. Curran Associates, Inc., 2019.
Jicong Fan, Mingbo Zhao, and Tommy W.S. Chow. Matrix completion via sparse factorization solved by accelerated proximal alternating linearized minimization. IEEE Transactions on Big Data, 6(1):119-130, 2020. doi: 2LLL0///BDAAA.2111.22211
Dylan Foster and Andrej Risteski. Sum-of-squares meets square loss: Fast rates for agnostic tensor completion. In Conference Learning Theory, pp. 1280-1318. PMLR, 2019.
Silvia Gandy, Benjamin Recht, and Isao Yamada. Tensor completion and low-n low-n-rank tensor recovery via convex optimization. Inverse Problems, 27(2):25000, 201
10

---

Published as a conference paper at ICLR 2022
Paris Giampouras, Rene Vidal, Athanasios Rontogiannis, and Benjamin Haeffele. A novel varia- tional form of the schatten-p quasi-norm. H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 21453- 21463. Curran Associates, Inc., 2020.
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Guyon, U. V. Luxburg, Bengio. H. Wallach,
Boris Hanin and Mark Sellke, Approximating continuous functions by relu nets minimal width. arXiv preprint arXiv:1710. 1278, 2017.
Moritz Hardt. Understanding alternating minimization for matrix completion. In 2014 IEEE 55th Anmual Symposium on Foundations of Computer Science (FOCS),, pp. 550-660. IEEE, 2014.
Christopher J Hillar and Lek-Heng Lim. Most tensor problems are np-hard. Journal of the ACM (JACM), 60(6):1-39, 2013.
Yao Hu, Debing Zhang, Jieping Ye, Xuelong Li, and Xiaofei He. Fast and accurate matrix comple- tion via truncated nuclear norm regularization. IEEE Transactions Puttern Analysis and Ma- chine Intelligence, 317-)2217- 2013. ISSN 0162-8828. doi: http://doi. http:/dd...eeecomppuussscceeee org/10.1 109/TPAMM.2012.271
Huyan Huang, Yipeng Liu, Jiani Liu, and Ce Zhu. Provable tensor ring completion. Signal Process- ing, 171:107486, 2020.
Christian Igel and Michael Hüsken. Improving the rprop learning algorithm. In Proceedings of the second international ICSC symposium on neural compulation (NC 2000), volume 2000, pp- 115-121. Citeseer, 2000.
Prateek Jain and Sewoong Oh. Provable tensor factorization with missing data. In Advances in Neural Information Processing Systems, pp. 1431-1439, 2014.
Chi Jin, Sham M Kakade, and Praneeth Netrapalli. Provable efficient online matrix completion via non-convex stochastic gradient descent. In Proceedings of the 30th International Conference Neural Information Processing Systems, pp. 4527-4535, 2016.
Misha Kilmer, Karen Braman, Ning Hao, and Randy C Hoover. Third-order tensors as operators matrices: A theoretical and computational framework with applications in imaging. SIAM Journal on Matrix Analysis and Applications,
34(1):148-112, A4plications,344))14888811
2013.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1412 6980, 2014.
Tamara G Kolda and Brett W Bader. Tensor decompositions and applications. SIAM review, 51()): 455-500, 2009.
Daniel Kressner, Michael Steinlechner, and Bart Vandereycken. Low-rank tensor completion by riemannian optimization. BIT Numerical Mathematics, 54(2):447-468, 2014.
Christian Kümmerle and Juliane Sigl. Harmonic mean iteratively reweighted least squares for low- rank matrix recovery. The Journal of Machine Learning Research, 19(1):1815-186 2018.
Dong C. Liu and Jorge Nocedal. On the limited memory bígs method for large scale optimization. Mathematical Programming, 45(1):503-525 1989. ISSN 1436-4646. doi: FO.1007/
Hanpeng Liu, Yaguang Li, Michael Tsang, and Yan Liu. Costco: A neural tensor completion model for sparse tensors. In Proceedings of the 25th ACM SIGKDD International Conference on Knowl- edge Discovery & Data Mining, pp. 324-334, 2019.
Ji Liu, Przemyslaw Musialski, Peter Wonka, and Jieping Ye. Tensor completion for estimating missing values in visual data. IEEE transactions on pattern analysis and machine intelligence, 35(1):208-22 2012.
11

---

Published as a conference paper at ICLR 2022
Zhou Lu, Hongming Pu, Feicheng Wang. Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: a view from the width. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 2232-62400 2017.
Feiping Nie, Heng Huang, and Chris Ding. Low-rank matrix recovery via efficient Schatten p-norm minimization. In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, AAAI'12, pp. 655-661, AAAI Press, 2012.
Lars Nørgaard and Carsten Ridder. Rank annihilation factor analysis applied to flow injection anal- ysis with photodiode-are array detection. Chemometrics and Intelligent Laboratory Systems, 23(1): 107-114, 1994.
Allan Pinkus. Approximation theory of the mip model. Acta Numerica 1999: Volume 8, 8:143-1955 1999.
Noam Razin, Asaf Maman, and Nadav Cohen. Implicit regularization in tensor factorization. In International Conference on Machine Learning, pp. 8913-89999999 8924. PMLR, 2021.
Benjamin Recht. A simpler approach to matrix completion. J. Mach. Learn. Res., 12:3413-3430,
December 2011. ISSN 1532-4435.
Jasson DM Rennie and Nathan Srebro. Fast maximum margin matrix factorization for collaborative prediction. In Proceedings of the 22nd international conference Machine learning, pp. 713- 719. ACM, 2005.
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, pp. 111-112, 2015.
Robert Serfling. Probability inequalities for the sum in sampling without replacement. The Annals of Statistics, pp. 39-48, 1974.
Ohad Shamir and Shai Shalev-Shwartz. Matrix completion with the trace norm: learning, bounding, and transducing. The Journal of Machine Learning Research, 15(1):340133433, 2014.
Fanhua Shang, Yuanyuan Liu, and James Cheng. Tractable and scalable Schatten quasi-norm ap- proximations for rank minimization. In Artificial Intelligence and Statistics, pp. 620-629, 2016.
Nathan Srebro and Ruslan R Salakhutdinov. Collaborative filtering in non-uniform world: Learn- ing with the weighted trace norm. In D. Lafferty, C. I. Williams, Shawe-Taylor, R. S. Zemel, and A. Culotta Advances in Neural Information Processing Systems 23, pp. 2056- 2064. Curran Associates, Inc., 2010.
Nathan Srebro and Adi Shraibman. Rank, trace-norm and max-norm. In International Conference on Computational Learning Theory, pp. 560. Springer, 2005.
Nathan Srebro, Jason Rennie, and Tommi S. Jaakkola. Maximum-margin matrix factorization. In Advances in neural information processing systems, pp. 1329-1336, 2005.
Ruoyu Sun and Zhi-Quan Luo. Guaranteed matrix completion via non-convex factorization. JEEE Transactions Information Theory, 6211)):535-6577 6579, 2016.
George Trigeorgis, Konstantinos Bousmalis, Stefanos Zafeiriou, and Bjöm W Schuller. A deep matrix factorization method for learning attribute representations. IEEE transactions on pattern analysis and machine intelligence, 39(3):417-499, 2016.
Andong Wang, Chao Li, Zhong Jin, and Qibin Zhao. Robust tensor decomposition via orientation invariant tubal nuclear norms. In AAAI, pp. 6102-6109, 2020.
Qi Wang, Mengying Sun, Liang Zhan, Paul Thompson, Shuiwang Ji, and Jiayu Zhou. Multi- modality disease modeling via collective deep matrix factorization. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1155- 1164, 2017.
12

---

Published as a conference paper at ICLR 2022
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(4):333-36) 1613--61,,20 2012. ISSN 1867-2957. doi: 10.1007/11233--01000444-
JP Wold, Rasmus Bro, Veberg, F Lundby, AN Nilsen, and J Moan. Active photosensitizers in butter detected by fluorescence spectroscopy and multivariate curve resolution. Journal of agricultural and food chemistry, 54126):00177-10204, 2006.
Q. Xie, Q. Zhao, Meng, and 7. Xu. Kronecker-basss--eppeeennne based tensor sparsity and its applications to tensor recovery. IEEE IEEE Transactions on Pattern Analysis and Machine Intelligence, 40(8):1888-199) 2018.
Yangyang Xu, Ruru Hao, Wotao Yin, and Zhixun Su. Parallel matrix factorization for low-rank tensor completion. arXiv preprint arXiv:1312.1255 2013.
Hong-Jian Xue, Xinyu Dai, Jianbing Zhang, Shujian Huang, and Jiajun Chen. Deep matrix fac- torization models for recommender systems. In IJCAI, volume 17, pp. 3203-3209. Melbourne, Australia, 2017.
Longhao Yuan, Chao Li, Danilo Mandic, Jianting Cao, and Qibin Zhao. Tensor ring decomposi- tion with rank minimization on latent space: efficient approach for tensor completion. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 9151-9158, 2019.
Ming Yuan and Cun-Hui Zhang. On tensor completion via nuclear norm minimization. Foundations of Computational Mathematics, 16(4):1031-1063 2016.
Zemin Zhang and Shuchin Aeron. Exact tensor completion using t-svd. IEEE Transactions on Signal Processing, 65(6):1511-15222 2016.
Handong Zhao, Zhengming Ding, and Yun Fu. Multi-view clustering via deep matrix factorization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
Qibin Zhao, Guoxu Zhou, Shengli Xie, Liqing Zhang, and Andrzej Cichocki. Tensor ring decom- position. arXiv preprint 1 1606.655355 2016.
A OPTIMIZATION DETAILS AND COMPUTATIONAL COMPLEXITY
In our MDDMTF, the matrix model is a special case of the tensor model. Therefore, we only show the optimization detail and the computational complexity of the tensor case. The gradient-based optimization is shown in Algorithm [] We suggest using iRprop+ as the optimizer in the algorithm because found empirically that iRprop+ is more stable and efficient than other optimizers such as Adam in solving our D2DMTF.
Algorithm Gradient-based optimization for M (2
Input: EE T Xn. Ω2 Å1, λ2. g. network structures {m,, L,, {hr (1()) Gi ik
1=11j==1 T.
1: Initialization: Co. (Z( (w()))
(i) م A " (U.")
=fgg (()1)) } )3
2: for t -1,2, 1.,....,7 T do
3: for j = 11,,, 1,2...., do Von, V }
backprop.
Lj. where Lj 2 Pa -C
1
R((O!)) Z6)) ) Ci) and V. -U.1-1) U...)()) @ U( U(+11.
4:
end for
5: Ve - OL2/OC
6: ((O0)) z 1
Ci} - -raddd optimizer ((VDG), Vool Vc)
7: end for
Output: 5 = Cr x1 f x2 x2 x U
13

---

Published as a conference paper at ICLR 2022
Without loss of generality, here assume that in (12), nu
n
m1
my m,
L1 L = I., and hi =... nn h1, I 0, 1,..... ...., L. The time cost in each iteration of the gradient-based optimization is
o O kiinn(mn + n m== _nm + n mmm) kn E m
in which the first term is from the Tucker-like decomposition while the second term is from the forward and backward propagations of the neural networks. Since the second term is much smaller than the first one and m n,, the time complexity per iteration is about O (kn + kn*-1m**). As we need to store the observed elements of V core tensor C, latent factors z network pa- rameter, their gradients, and the values of hidden units, the space complexity is [ + m +
E h + kn Ei=1 ht), which is further simplified to O ( + m + km Σi= hy) because larger than all h4. Now we see that the time (per iteration in the optimization) and space com- plexity of our DCDMTF are slightly higher than the Tucker decomposition based tensor complction methods. However, M2DMTF requires much more iterations than the baseline methods because is composed of tensor decomposition and neural networks.
B MORE ABOUT THE EXPERIMENTS
B. MATRIX COMPLETION
In the proposed method (9), the regularization
1 ΣΣ>
R(Z,Q,5,0,,02 À (1 + |S +
A2 2
(1Q12
w (
+
1=1
We let A2 = /2n and determine X1 and X2 instead. In the optimization, S, Z, and (w initialized randomly, Q is initialized to identity matrix.
B.1.1 PARAMETER SETTING ON THE SYNTHETIC DATA
In MF (problem (1) in the main paper), the factorization dimension d is because out- performs other choices. The À is chosen from {0.01, 0.1, 1} and the optimizer is iRprop+. The maximum iteration is 2000.
In FGSR (Fan al. 2019 we use the variational form of Schatten-1/2 norm, set d 20, and choose À from (0.11,
0.13. The maximum iteration is 2000.
In SAE (Sedhain et al.) 2015), the network structure is [100, 20, 10, 5, 10, 20, 100). The weight decay parameter chosen from 0.51.
In DMF (Fan & Cheng 2018), the network structure is [3, 10, 20, 100). The weight decay parameters are chosen from f0.01,0.1
In M'DMTF, L 2, dj = dg = 3, h1 1 10, mi = mg = 20, and λ = X22
In SAE, DMF, and M D'MTFF, the activation function the hyperbolic tangent function. The opti- mizer is iRprop+ and the maximum iteration is 3000.
B.1.2 MORE RESULTS ON THE SYNTHETIC DATA
Figure compares DMF with linear MF (FGSR) in the cases of different m2/n11 We see that when n2g m1 I8 too small, FGSR outperforms DMF, When n2/nj increases, the superiority of DMF over significant. These empirical results are consistent with our theoretical analysis in Section of f the main paper.
FGSR becomes
Figure 6 shows the performance of M DMTF with different number of hidden layers and different activation function. it can be found that tanh and sigmoid functions lead to lower recovery error than ReLU in all cases. The main reason that the data were generated by smooth functions that can be
14

---

Published as a conference paper at ICLR 2022
0.
Missing 1etev1.9
0.5
Missing relev
FGSH USe
FOOn
Patto ot redette (POOPECIN)
0.30
0.4
Peative reavvry ener
0.
Dheagive RoOoe endt
0.33
3.10
0.2
0.1
0.00
0.00
2.5
Figure 5: The influence of nz/n, on FGSR and DMF
0.1
Sigmold
Relative recovery error
0.095
0.09
0.085
0.08
0.075
0.07
0.065
2
Figure 6: The performance of MTDM with different number of hidden layers and different acti- vation function. The sizes of added hidden layers are
well approximated by tanh and sigmoid functions. When the tanh function or sigmoid function is used, increasing the depth the neural networks can reduce the recovery error. But when L is too large, i.c. L = 4, the recovery error increased slightly, which might be caused by overfitting.
F the values of the objective functions and relative recovery errors against the iterations in matrix completion and tensor completion when the missing rate is 0.95. The recovery еттоr decreases slightly when the number of iterations very large. In general, the optimization efficiency is not very high because DMTF is composed of multiple neural networks with unknown inputs and incomplete outputs.
5000
Chjecivv luncion
Cepeciiv
05
8000
04
0.4
8020
0.3
03
0000
Ocpecie
4000
02
3020
0.15
1020
0.06
1030
2003
3020
4500
5000
1000
2000
4000
5500
Inration
(a) Iterative performance of D'DMTF in matrix (b) Iterative performance of M DMTF tensor pletion on given by [17
pletion on data given by (16)
Figure 7: Iterative performance of M (iRprop+) synthetic data with missing rate 0.95.
15

---

Published as a conference paper at ICLR 2022
We replace the sin, cos, exp, and in (16 and with tanh such that the nonlinearity in the data generating models are consistent with the activation functions used in our matrix and tensor completion method DMT.... The average results of 10 trials reported in Figure 8 We see that MDDMTF outperformed other methods significantly when the missing rate is high enough.
FOLRTO
NAMA
THNN
0.5
TonALS
TMbc
HMIILES
NSR-1C
Pelative recovaty anter
FOOR
0.4
SAE
04
DMV
MOOMTF
MOOMTF
0.3
0.3
Relative
0.2
0.2
0.1
0.52
0.04
0.88
0.82
0.94
0.95
0.90
0.52
0.94
0.96
0.98
Missing rate
Missing rate
(a) Matrix completion on data given by modified
[6
Tensor completion data given by modified 17
Figure 8: Performance evaluation of matrix completion and tensor completion synthetic data generated by (16) and (17 in which the nonlinear functions replaced by tanh.
B.1.3 PARAMETER SETTING ON THE MOVIELENS DATASETS
In MF (problem (1) in the main paper), we set = 10 and À = 10. stead of iRpropt, we alternating minimization because outperformed iRprop+ this case. The maximum iteration 2000.
In FGSR Fan et al. (019). we use the variational form of Schatten-1/2 norm, set d = 100, and set 0.015 or 0.007 (for MovieLens- 100k or MovieLens- IM). The maximum iteration is 2000.
In SAE Sedhain et 2015), we use single hidden layer of size 500. The weight decay parameter is 0.5.
In DMF, Fan & Cheng (018). the network structure is [10 or 20, 50, 100, 1682]. The weight decay parameters are chosen from {0.05,0.11 0.13.
In M²DMTF, we set L = 2, d = 10 or 20, h
50, mi = m2 100, and
\1 11=X-=1 1.
B.1.4 MORE RESULTS ON THE MOVIELENS DATASETS
The proposed M'DMTF outperformed MF, FGSR and DMF in all cases and outperformed SAE when the missing rate was high. Note that RMSE is monotonic transformation of the relative recovery error used in the main paper.
The RMSE (average of 10 trials) on the MovieLens- 100k are reported in Table 4
Table 4: RMSE on MovieLens-1004
Train-Test
MF
FGSR
SAE
DMF
M'DMTF
9-1
0.9565=0.0077
0,919410.0073
0.8928100.000 0063
0.9320=0.0070
0.90481000077
7-3
0.9880=0.0037
0.9318+00.028
0.9105+:00036
0.9454+0.0038
0.9159=0.0044
5-5
1.0356=00.033
0.954140.0038
0.9364+:000222
0.9692+0.0048
0.934110.0040
3-7
1.1259
0.992410.0037
0.984010.0016
1.0055+0.0025
0.0063
1-9
1.459711000993
1.1978
1.121740.0097
1.1697-0.0064
1.0019
16

---

Published as a conference paper at ICLR 2022
B.2 TENSOR COMPLETION
In the proposed method (12), the regularization is
R(10,,200) J=1,
A1
Σ 11
X2 2
| + Σ> (1))
(18)
11)=1n)) _,) m3) 1/k
and determine A and X/2 instead. In the optimization, U, is initial- ized by the singular value decomposition of the j-mode matricization of y, C initialized to zero, and {Z (W,()) are initialized randomly.
We let A2 =
B.2.1
PARAMETER SETTING ON THE SYNTIETIIC DATA
In FaLRTC (Liu et al.
2012).
011 02 0g choose jr from {0.5, 1, 1, 2, 10). 2014), the initial rank is or 10 and the max iteration is 200.
In TenALS Jain Oh
In TMac (Xu et al.
2013). the rank is initialized [10, 10, 10] or 55,5,5 5] and adjusted adaptively. The maximum iteration is 500.
In KBR-TC (Xie et al.
2018). 1.01 and 0.01. The maximum iteration is 300.
TRLRF Yuan et al. {0.01,0.1) 0.1, 10, 50).
2019), the rank set to [5, 5, 5] or [10, 10, 10). We choose À from
2019) the learning rate chosen from {0.01, 0.001, 0.001 the rank is chosen from {2, 3, 5, 10, 20). the epoch number is 50 200, and the batch size is 256 x or 256
In CoSTCo (Liu et al.
In OITNN-O (Wang al. iteration 500.
2020 choose from {0.0001, 0.001, 0.01, The max
In M2DMTF, L 2, dj d2 d3 3. A A(())
h (
10, mi m2 my 20,
and A = X/2 = 1. The optimizer is iRprop+ and the maximum iteration is 3000.
B.2.2 TIME COST COMPARISON ON THE SYNTHETIC DATA
We report the average time costs (second) and the recovery errors of methods in Table which also includes the performance of D'DMTF with different iteration numbers. We see that our method with 3000 iterations is slower than other methods. However, when we use less iterations (e.g. 1000 200), the time cost of our method is comparable with even lower than the baselines and its recovery error still much lower than the baselines.
Table Average time cost (second) on the synthetic tensor data (CoSTCo was performed in Python while all other methods were performed in MATLAB.)
FaLRTC
TenALS
TMac
KBR-TC
TRLRF
CoSTCo
OITNN-O
recovery error
0.944
0.973
0.323
0.169
0.621
0.617
0.328
time cost
3.5s
2.1s
1.4s
4.7s
4.3s
7.2s
6.8s
M²DMTF
iteration
100
200
300
500
1000
2000
3000
recovery error
0.098
0.068
0.057
0.043
0.037
0.033
0.031
time cost
1.1s
2.0s
3.1s
4.9s
9.9s
20.65
32.3s
B.2.3 EXPERIMENTAL SETTINGS ON REAL TENSORS
We normalize each tensor by X X X In M'MMFF, set L 1 and \₁ X, = 0.001.
For = 1, 2, 3, we set m, Th, de z3 Ty if n, > 10 and set m; x 0.8n,, d, z 0.7n; if n, < 10. The parameters of other methods carefully determined provide their best performance.
17

---

Published as a conference paper at ICLR 2022
B.2.4 MORE RESULTS ON TENSOR DATASETS
In addition the three datasets considered the main paper, we test the proposed method on three
more datasets: Porphyrin (Wold et al. 2006) 170 x 274 x 35, Sugar (Bro) 1999) 256 x 571 x 7, and Bonnie (Acar et al. )008) 89 97 x 549. To reduce the computational costs of all methods on Bonnie, we only consider subset of size 89 x 97 x 100. The results are reported in Table [ We see that MMDM outperforms other methods when the missing rate is high enough.
Table 6: Relative recovery еттог on more tensor datasets (MR denotes missing rate)
Data
MR
TenALS
TMac
KBR-TC
TRLRF
OITNN-O
M'DMTF
Porphyrin
0.85
0.0931 +0.0013
0.0105
0.0304:00001
0.0319=0.0180
0.01 000001
0.0184=00.007
0.90
0.0968++0.08
0.028 +000023
0.0330+0.0017
0.0451
0.0225 10.0033
0.021 +1000118
0.95
0.1091 +0.0133
0.0493-10.0169
0.0458#t.0008
0.0701=0.003
0.0522
0.0376:10.0005
0.97
0. 0.119940000 1000008
0. 4..0188
0.0569#100014
0.1606=00.178
0.1066::0.0052
0.0450110.0009
0.85
0. 0.1438+ +0.0549
0.0456:+0.0041
0.0406=000027
0.1075=00004
0.0719
0.0504
Sugar
0.90
0. 0.1554410.00 10.0019
0.0639 1..0034
0.0563 10.0039
0.1214 0.0006
0.0915 1.00059
1.056681..000
0.95
0.1 7.1749 10.0208
0..07311.0265
0. 1.109901.0000
0.2083 0.0196
0. 0.1573 10.004
0.0921 10.0043
0.97
> 0.95
0.3129110.080
0.2791 10.0306
0.6515 0.0364
0.2443 0.0221
0.1689 1:003116
0.90
0.0538
+0.0052
0.0084
0.0049 0000001
0.0407 0.0004
0.0128 0.0007
0.0110
Bonnie
0.95
0.0598 10.0126
0.0204 L..000
0.0633=0.00M5
0.0385 0.0014
0.0167
0.0167:000003 1:00013
0.97
0.3561 +0.0649
0.1451 1145110.000 +0.0386
0. 0.100 1.10005
0. 0.1187=0.n16f
0.0785 1.0008
0.0328
0.99
> 0.95
0.7354-10.067
0.95
> 0.95
0.3835 00.0032
0.1174.10.012
B.2.5
TENSOR-COMPLETTN BASED RECOMMENDATION AS A DOWNSTREAM TASK
We split the MovieLens- 100k dataset by time to form a tensor of size 943 x 1682 x 31, where 31 denotes the number of weeks as dimension of time. Since the baselines KBR-TC, TRLRF, OITNN-O, and the proposed DTDMTF have high time cost on large tensors, we reduce the size of the tensor by removing the users giving 49 or less ratings and the movies rated by 49 or less users. Then we get tensor of size 563 x 593 x 31. The relative recovery error (average of 5 trials) are reported in Table 7 Our M'DMTF outperformed other methods. In addition. comparing Table 7 with Table D we found that tensor completion methods are more effective than matrix completion methods recommendation.
Table 7: Relative recovery emrors of tensor completion methods on MovieLens-100k (MR denotes missing rate)
MR
FaLRTC
TenALS
TMac
KBR-TC
TRLRF
CoSTCo
OITNN-O
M'DMTF
0.5
0.2627
0.2813
0.3065
0.2528
0.2634
0.2696
0.2830
0.2429
0.7
0.2692
0.3097
0.3470
0.2685
0.2719
0.2724
0.2951
0.2483
0.9
0.2881
0.3356
0.3782
0.2739
0.2804
0.2763
0.3207
0.2614
B.2.6
VISUALIZATION OF FACTORS LEARNED BY M2DMTF
Here we take the 'Flow injection' tensor Norgaard & Ridder 1994) example. The data is from measuring samples with three different analytes on a flow injection analysis (FIA) system where pH--gadient is imposed. The three analytes in twelve measured samples are 2-, 3-, and --hydroxy-eezzlldehyy benzaldehyde. They have different absorption spectra depending on whether they are in their acidic basic form. The data set is 12 (samples) x 100 (wavelengths) x 89 (times) array. Figure presents the original data, incomplete data, and recovered data for the fifth horizontal slice (sample-5) of the 'Flow' tensor, where the missing rate is 0.97. We see that Fal FTTC TRLRF, and CoSTCo failed totally. TenALS, TMac, and KBR-TC have high recovery error visually. In contrast, the data recovered by our DTT very close to the original data. More importantly, the result of M 2 indicates that there are three analytes, while other methods failed to reveal the fact.
9
We analyze the characteristics of the low dimensssnional factors learned by our D'MT... Figure presents the values of U2 1000x20 and (2) E TR. 1000x10 as well as the correlation coefficients
18

---

Published as a conference paper at ICLR 2022
Original
Incomplete
FaLATC
TenALS
20
20
20
20
20
40
40
40
40
40
80
60
80
80
80
100
100
100
100
KBR-TC
TRLAF
CoSTCo
OITNN-
MºDMTF
20
20
20
40
40
40
60
80
60
60
80
80
80
80
80
80
100
100
100
100
100
20
40
60
80
20
40
80
20
40
60
80
20
40
60
80
20
40
60
80
Figure 9: Completion result visualization the fifth horizontal slice of the 'Flow" tensor (missing rate=0.97).
Unf
MutuslintajU
0.5
20
6.
0.5
688
10
10
60
04
0.5
15
15
100
64
50
2
corrcoeliZ)
concoctf2 )
Mutualinto/27
0.8
655
40
68
50
44
05
02
50
100
20
40
50
100
10
10
Figure 10: Latent factors U2 and (2) (corresponding to the wavelengths dimension of 'Flow' tensor data) given by the proposed method D'DMTF. Column 1: values of U2 and ( Column 2: correlation coefficients between the rows of U2 and 2 Column 3: correlation coefficients between the columns of U2 and (2)) Column 4: mutual information between the columns of U2 and (2)
and mutual information. In the first column, we see that the values of U2 are more chaotic than the values ()) The reason is that the 20 variables in U2 correlated mutually. In the second column
of Figure 10 see that the autocorrelation of the samples (rows) of U2 is similar to that of ( because Up relies (2)) The third column of the figure indicates that the correlation between the variables in U2 are higher than that in 22) The last column compares the mutual information that can quantify nonlinear relationship. Now comparing column 4 with column we conclude that there exist significant nonlinear relationship between the variables in U2 and it is necessary to represent U, by lower-dimensional latent factor (2) via deep factorization. These results verified that the nonlinear latent factor assumption of our M'DMTF is practical and useful.
C PROOF OF THEOREMS
First of all, we provide the following lemma.
Lemma 1. Let S be set defined over tensors of size X X ... X Let (S] be the e- covering number of S with respect the Frobenius norm. Let N I ne. Suppose X and max(1|))) X ||oc) S &. Then with probability least 2N-1, there exists constant such
19

---

Published as a conference paper at ICLR 2022
that
&85* log (ISIN) 1/4
1 VN
1
2e
sup XES
|>
xII
PP
x)11
5
ViSi
V1s2
[S2]
The proof of the lemma is in Appendix D.1
C.I PROOF FOR THEOREM
The following lemma (proved in Appendix deep factorization matrix set.
shows an upper bound for the covering number of the
Z S Bo. |illF S 31, < < L}, where Z E R Wi E RRuxh=-1, = 1...., L, h2 = ho = d and h- = n. Suppose the Lipschitz constant of g n. Then the covering numbers of with respect to the Frobenius norm satisfy
Lemma 2. Let S (X R X W
Eiso hyhy
3(L + 1)m1 11
(1,,6)
Now using Lemma and Lemma
we have
X
X
F
Y E x
VN
1
1
Y
x
+
E F
VN
2c
(8 log ((S)N)
1/4
PPaeY
X)
+
E
+
+
2
[2
1/4
3(L + 1)17
1-11-11
31
88 SEo N + Et h log
1=0
2e
PPrlY - X11
E F
+
?
N
/12
[
1
GE(L. + 1).
188* (Eg N + El=o h
10 1-1
IT 31))
1/4
|Pa(Y - x))l
| +
+
V
[22]
El hyht log(n 1
1 3))
1/4
PPnlY -X x)
F +
?
In the fourth inequality, we have set 6 = 3E(T. + 1). The last inequality holds because N is much smaller than (S and can be constant large enough. This finished the proof.
C.2 PROOF FOR THEOREM 2
The following lemma (proved in Appendix D.3 of the two-mode deep factorization matrix set.
provides an upper bound for the covering number
Lemma 3. Let S
{X
E
x
x = fo. (Z)
|Q s Bo Z S S Lj.j
||||
8 ( S ((1) <
1,2; fo. (Z)
o( L (W (1)
11
(2) S))), }. where Z E 41-1" ( Z))). (S) g(w()) Lg L2-1 1a-1""gh (w(2)
(W (2)
Rd S Id2xng, w! ( g. xh 1 = 1, ,,...., 4y. hi m.. h/") dj, h nj,
j = 1,2, and Q E Xm,x Suppose the Lipschitz constant of is Then the covering numbers of S with respect the Frobenius norm satisfy
3(k 1)(max(L1, L2) 1)s 1)s
N(S, e)
6
where p mmm2 Σ)= Els 11 1 and Bon +b bZ (T (IT 8(21).
20

---

Published as a conference paper at ICLR 2022
Similar to the proof of Theorem 1, using Lemma
|
we have
1 x 1|1
2e
(85* log ([S]N)
|PnlY X)IFF
E F +
S
V122
[S2]
where N m1.2.. Let 3E(k + ()(mmxx(L)))) I2) + 1). According to Lemma
and obtain
2 bi
L
Lg
log((81) (m1m²
ΣΣ
11))(1)) m12i) log (s
8
2
11))
j=1/=0
Now have
1
x
x
S
iPr(Y x)1(F VN
El
VN
VIS
mmmm + Σラ=1 Etz h 11)1111
log
(B 8(0h) (IT sftt)
)
1/1
+ of
[22|
This finished the proof.
C.3 PROOF FOR THEOREM 3
The following lemma (proved in Appendix D.4 provides upper bound for the covering number of the multi-mode deep factorization tensor set.
Lemma 4. Let S {X
X = C x1 (z x2 Sog (Z(2)) X "...""'WW" (W z(1)))
for (Z());; (Z)
g(Wl)) Iy ---1 ...
g(w())
I....,k: |C]| S 1 S < Lj.j = 1, 1,...,k) k,,, where z E Rdd,xs,,
9c, 11000 < 8(0)
W ( |F I 3 w E R400 x L,. h = mj, h = d, 1 n2. j = l....,k, k, and
C E pmixmm-"Xmm Suppose the Lipschitz constant of g is n. Then the covering numbers of s with respect to the Frobenius norm satisfy
(3(k 1) + +1ss)² 11)))
e
where 11, mj
j== E/z 1
1 and Bon Ein Lj 11 j= ii 300
1.
The proof is similar to that for Theorem 2. Using Lemma I and Lemma 4. we arrive
VN X 211 S
PPar 8)1E++ + VN 111111
(I m, + En Ele m 11)) log (i IT IT 122 ((50) 1/1
+ of
12
where a constant.
D PROOF FOR LEMMAS
D. PROOF FOR LEMMA I
We give the following lemma.
21

---

Published as a conference paper at ICLR 2022
Lemma 5 (Hoeffding inequality for sampling without replacement (Serfling 1974)). Let X1, X...., X, be set of samples taken without replacement from distribution { . of mean and variance o². Denote min; 24 and b = max; 2;. Then
2s1²
P
Σ
Xi
u 2
2xxp (-11- (s 1)/N) a)2
We define
((x) = [2]] PP - X11
1
((x)
N 11 X1
where N = I[[== n4 Suppose max ( || 1100 S According to Lemma 5
we have
2/2/t²
P ( [(x) 2
- 2 exp
(1
1))
where 8 452. Using union bound for all X yields
P sup
[((x) [(x)) 2 t
E
(1 - (1S2) 2/12/2
S exp
1)/N)82
Or equivalently, with probability least 1
-N
8 log (ISIN)
1
|[(x) (-(-((((
sup X
2
N|
8 log ([S[N)
A.
2/2
Since IV - V0l S v u o| holds for any non-negative and v, we have
[(x) / V((x) SVA
sup
Žes
Recall that e 2 |1 X11 2 PP(X x)(() [e, we have
v [(X) v ((X)
//2 |110 1x1 -112 -811 VN
VN
and
V ((x) v ((())
1 |PP2 - x)11= |Pa x111e s v
It follows that
[(x)) - [(x))
sup
X8s
V2(x) - / ((x)) + - 2(x)) + -(() L((x)
< sup
X
6
+VA+ + VN
V
8 log (ISIN) 1/4
2e
+
V
2/12]
This finished the proof.
22

---

Published as a conference paper at ICLR 2022
D.2 PROOF FOR LEMMA
Let X = W. T.-1- W1 )) where Z E Rdx=, W E Bluxh 1, 1 = 1,... L, and
hg d. Let Sab = ( E Boxb ||] 3}. Then there exists an e-net Sab obeying
3 ah
(S |l ()l.)))
5 S c. Now replace with e/7 and let I| Wille I _, 1, L,...:4.
such that W
n
z Z P
-
Let = (L 1)mtt 11 3r, 1= ..,,
70
|X 1
WWLgWW, 1-1 W-11" ... W2 Z)) Wi -1 W (W, 2))
W| LW ... Wo
WL L-- W W W Z))
WLL9(WL- WW111" W29 (Wz)) + WL W29( W1Z))
WLogW, L-1"
(WL11" ... (2g(W WLo( WVg(WL-L) L- (W,
S WL WW-WLL- L-1''. ( WLg(W (W L-1 Weg W; Z))lFF
+ [|WL9(W
W W; WWL-" W. 29 W)
+ [W Weg( Z)) WLO(W W29 2))
+ +|[ L9 L-1 W2g W2z) WLg(WL- LW111".
L-1
-0 (W>
WT - Well Z
Will
(19)
+ +n² "1''1I W
WLLFF
II Will
L-1
Wi
WilF= Z
II
Will
1=2
L - z II WilF
1=1
5 IL
II I=0
f-1
II 14L-
3: +
17
II
3r
n p II B1
YL-1
11 196
Yo
1y0
=e The second inequality utilized the Lipschitz continuity of g and the submultiplicatiitty of the Frobe- nius norm. Therefore, an e-cover of S. We have
NSS, || (|r,c)
L
3,9m9
hehi-1
c
1=0
3(L 1)n²
IT 31
II
I=0
hohir-
3(T. + 1) IT 33
E
D.3 PROOF FOR LEMMA 3
Lemma 3 special case of Lemma 4
23

---

Published as a conference paper at ICLR 2022
D.4 PROOF FOR LEMMA 4
Let po - ||C||p. For j = 1,...,k, k. we have
Ly
41
|U S -
II
w 1
|| = -
( -
pj.
(20)
1=1
1=U
Denote T = IT Pj. Similar values can be defined for C and Uz.
Let Sy := (w, (1) E Raxh; : | IE s 1 Then there exists an e-net Sy obeying
3,3(0
SS ll e) -
such that || - W/ || s e. Let 18") = (L3 + 1)mr's Il Si, 1 = 0,..., ,,gg and T,
(A + 1) 1) Pr. = 0, ,,...,k. k. Replace with c we have |W - w, || S r and
r(uiT""
have
1 1P
31 ( r B(,
N(S 1l |F, ppir) S
follows that
I|U,- -Ulle
9w/ 2,-1 w (( Z 2(2)) - sWW2, (w (1)
4 Wh (( 2 Me
-llo(W))) s(w(() ())
40-1 W (((()) 6) 2 ()) = (W ( W (w ( 20))))
= 9(W g(W()) (1)
1. w g( () Z z1))) ... ( g(
- W/ 1) (( z()))
(1)
= =o( L-1 W2g(WiZ) - ( (( 9 ( (0))))
(l 1-1 W g(W (1) (()1) - -(W
.. W. g(w (011 |
+ +1lo(w ()) ( 1--1 W0 ((( () (011)) -
(1) 1--1 W2 ((W(1) (1) 2,))ill
+ 1 (w
(())) (W ()
by (W(()
1 W 9 (W Z,)))lI
6)
15-1
+ +1lo(W1, 2, gW 10
s( (w
( 2(1)) -WW (W/
1y-1 9W 2())))l
L3-1
1 |
II 1
1=1
L--2
+ - 1
||
[ ||
II ||
L-1 II
w ||| |
| 11 |r
F
1=2
L
+ f
2111
Fr
1;-1
<n c
II
8
+ b
8(0) +
+ +
c
II ((5)
+ +
Il st
r
L r,
r
L-1 r
r 171
r rr 1
1=0
1911-11
(21)
24

---

Published as a conference paper at ICLR 2022
Now have
[ X1IF
-IC X1 U1 x.. X - X2 x
-IIC x1 U1 X2. X U x2 U, =
U x1 U1 X2 X X Uk-1 X Up
# .... +0 x1 U1 X2 ........................... X
U1 X2 ... X U
<|C x1 U1 X2 "x -U X2 x (Uk-1 U--1) X Unll
+...+ [C x1 (U1-01)
X2 U2. X U [C C) X1 U1 X2 ...
... X Uzlop
<| 11000-100000.0000001010000000111
- Us
+ + || F..++[[[[=10 - Uxx] - 1 || |00||F
<||||=||Ui|||>
U Tx
|C||
kk- |
U22|F
|00|| +
U ||
|121
|
Ti
To
<e
Pj
II
Ps
+
Pb
Ps
Y
Tx-1
r
To
=6
Therefore S is an e-cover of S. Then the covering number of Sank can be bounded as
(S
-11,,)
3Topp
11--1 my
R
Li
(
f=11=0
o
T my
k
by
3(Lj + 1)
1 660
j=1/=0
11 my
Lg
1 A
3(k + 1)T
3(k + 1)(L + 1)T
e
1=0
1T my
Ile a 162
3(k + 1)r
3(k + 1)(mmax + 1)T
e
Ø=1
1T my
Et= D.g M90
3(k + 1)T
33kk + 11m4max + 1)T
11 m)+E) E'2o (O)
3(k + 1)(mmax + 1)T
11 my+ m Die ((0
3(k: + 1)(Tmax + 1)po 15= (2
25


Reviews:
[{"review_id": "gFL8L1c253", "reviewer": "Reviewer_jdoi", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Overall, this is an interesting paper, providing an important theoretical analysis of deep matrix/tensor factorizations and bridging the gap between deep learning and tensor factorization models. The paper is well written and easy to follow; the theoretical analyses are delivered clearly despite the heavy notations. The two-mode design in the proposed matrix factorization is quite unique, to the best of my knowledge. Theoretical analysis and synthetic experiments show that when data is generated according to the assumption, it outperforms baselines and achieves better generalization. The idea of incorporating deep matrix factorization into Tucker decomposition is also quite interesting.\n\nMy questions/comments are:\n\n1) In Assumption 2, it is assumed that X is generated by $\\mathbf{X}=\\mathbf{U}^\\top\\mathbf{Q}\\mathbf{V}$, I wonder what motives this assumption and are there any motivating examples in the real world to justify this assumption?\n\n2) The sizes of the tensors used for experiments are quite small, how would the proposed model scale to a large tensor? Also, the running time of the proposed model and the baselines are not reported.\n\n3) There are other recent nonlinear tensor completion models, e.g. CoSTCo[1]. It would be great to see relevant discussion and comparison with those recent methods.\n\n\n[1] Liu, Hanpeng, et al. \"Costco: A neural tensor completion model for sparse tensors.\" Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2019.\n\n", "summary_of_the_paper": "This paper studies the nonlinear low-rank completion of matrices and tensors. Specifically, it first presents the theoretical results showing why nonlinear deep matrix factorization is better than the ordinary matrix factorization model. Then, it proposes a model named two-mode nonlinear deep matrix factorization to make full use of the nonlinearity of the nearly square matrices. The authors also extend this method to tensor factorization by further factorizing the factor matrices in the Tucker decomposition using the deep factorization method. Impressive results are obtained using both synthetic and real-world datasets.", "summary_of_the_review": "This well-written paper presents some interesting and important theoretical results and proposes a promising multi-mode deep matrix and tensor factorization model. Its theoretical aspect seems solid to me, yet some of the experimental settings need to be clarified and evaluation against missing baselines is needed.", "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": {}}, {"review_id": "RD2Jz-0yNmq", "reviewer": "Reviewer_BPJG", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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": "The paper discusses why and when the nonlinear DMF outperform linear MF, which is very important in practice. The proposed two-mode DMF method and its tensor variant are novel and interesting. This paper provides comprehensive experiments, including both synthetic and real matrix/tensor data sets, to show the effectiveness of the proposed framework. The results based on various optimization algorithms make the performance convincing and the comparison fair. \n\nIn addition, there are some other comments to enhance the quality of the paper: \n1. In eqn.(2), it that a typo for the half parenthesis in the last term?\n\n2. It is quite confusing for the symbol \"h\", which sometimes denotes the dimension, e.g., in (5), while sometimes represents the function in p.5. It may be better to distinguish them with different notation.\n\n3. In line -9 p.3, does it mean that one particular $h_l$ is large or all $h_l$'s are large?\n\n4. The Assumption 2 in Sec 3 is not well organized. First, the definitions for $f_{\\theta_i}$ could be moved to eqn.(8) when they first appeared. Second, should the functions $f_{\\theta_i}$ for $i=1,2$ defined from one matrix space to another, instead of $\\mathbb{R}^{d_i}\\to\\mathbb{R}^{m_i}$? Also, the mapping notation here should be $\\to$ rather than $\\mapsto$. Lastly, the parameter spaces are not clearly defined, e.g., the spaces where the parameters $\\theta_1$ and $\\theta_2$ belong to. \n\n5. Minor issues: \nline 5 p.4: What does it mean by \"d can be larger than the ground truth\"? It seems that d is the dimension of the latent variable. \nline -14 p.5: \"tighter generalization bound\" -> \"a tighter generalization bound\"\nline -10 p.5: \"could be\" -> \"are\"\nline 11 p.7: \"higher-order\" -> \"high-order\"?\n ", "summary_of_the_paper": "The paper provides a multi-mode framework for the deep learning based tensor decomposition, which could be useful for dealing with nonlinear high-dimensional data sets. In particular, it extends the deep matrix factorization (DMF) method and proposes a multi-mode deep matrix factorization method for matrix completion with convergence guarantee. Based on this, it also develops a multi-mode nonlinear deep tensor factorization method with convergence guarantee. The proposed models are solved by various optimization algorithms. Numerical experiments on synthetic and real data sets of the matrix/tensor form have shown that the proposed methods outperform other state of the arts. ", "summary_of_the_review": "Overall, I vote for acceptance. The multi-mode generalization of deep matrix factorization and its extension to tensors are insightful with detailed theoretical discussions. My major concern is about the clarity of the paper and some notational confusion. Hopefully, the authors can address my concern in the rebuttal period. ", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "LWvA7V5Rjew", "reviewer": "Reviewer_26KD", "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": "Strengths:\n(1) Strong theoretical analysis\n(2) Clearly stating the assumptions in the proposed models\n\nWeaknesses:\n(1) Optimization procedure for the proposed models is not ver clear\n(2) The applicability of the proposed models are evaluated only on matrix and tensor completion tasks which may raise doubts on usefulness of them on other downstream tasks.\n(3) The experimental evaluation is not rich and strong. It is better to provide analysis on latent factors (output of matrix and tensor factorization). Besides, only a few baselines are included in the paper. More recent methods can be included as baselines for experimental evaluation. In addition, the proposed models do not consistently outperform the existing solutions on matrix and tensor completion tasks.\n(4) Computational complexity analysis has not been performed elegantly for the proposed models.\n\n", "summary_of_the_paper": "To bridge the gap between deep learning and tensor decomposition, this paper presents two novel approaches named as two mode non-linear deep matrix factorization and multi-mode nonlinear deep tensor factorization (extension of two mode model to multi-mode scenario). The main contribution of the methods lie in full exploration of non-linearity of data in matrix and tensor factorization. To better motivate the proposed models, the authors provide theoretical analysis for why and when nonlinear deep matrix factorization outperforms linear deep matrix factorization in matrix completion. The experimental evaluation demonstrates that in some datasets, the proposed models outperform the existing models on matrix and tensor completion tasks.", "summary_of_the_review": "The proposed models built on top of meaningful assumptions for matrix and tensor factorization tasks which aim to address the gap between deep learning and factorization. However, there are several aspects in this paper that require improvement:\n\n(1) The experimental evaluation is not very strong: \n(1-1)I recommend the authors to provide in depth-analysis of the latent factors using visualization methods for downstream task of matrix and tensor completion.\n(1-2)The authors need to explain why the proposed models do not achieve the best performance on some datasets.\n(1-3)Please include more baselines for experimental evaluation\n(2) Please include more details on the optimization procedures in the paper or appendix.\n(3) I suggest the authors to put computational complexity analysis of the proposed models in the paper.\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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "AmSQXfTummi", "reviewer": "Reviewer_8BDW", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The paper analyzed the proposed non-linear multi-mode tensor factorization algorithms, and the theoretical results help to understand the gap between the linear and non-linear factorization gap. \n\nSome concerns are\n[1] When comparing equation (6) and equation (7), some assumption regarding h seems missing. it is known that h_{L} = n1 and h_{-1}=n2, are there any assumptions needed  regarding the setups of h_{i: i = 1,..., L}? Are they bounded by r?\n\n[2] There are some concerns about the synthetic data simulation used in the paper. It is okay to use complexed non-linear transformation (e.g. sin/exp) to verify the non-linear multi-mode tensor factorization works as expected. While, it would be better if the synthetic data can are generated the same way as the assumption (tanh activation function as used in the experiment) to verify how efficient of the algorithm in recovering a tensor with known factorization. \n", "summary_of_the_paper": "This paper summarizes the theoretical guarantee for the existing LRMC and LRTC algorithms, and provides the theoretical analysis for a new proposed Multi-Mode Nonlinear deep tensor factorization. The analytical results show that when n2 is larger than n1, the nonlinear DMF provides a tighter generalization bound than MF. Similar analysis has been extended to two-mode matrix factorization and multi-mode  tensor factorization. Experimental results in synthetic data and real data show better results of the proposed algorithm as compared to other algorithms in completion tasks. ", "summary_of_the_review": "Overall, the paper is a theoretical paper and the bound analysis helps to understand the gap between classical linear factorization and non-linear factorization. ", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers matrix and tensor factorization, and provides a bound on the excess risk which is an improved bound over the bounds for ordinary matrix factorization. The authors also show how to solve the model with standard gradient-based optimization algorithms, and present results showing good accuracy. The method can be a bit slow but this depends a bit on the number of iterations, and in general it achieves better accuracy in a similar amount of time to other baseline algorithms.

The reviewers raised a few points, such as jdoi noting the tensor experiments were for small tensors and should include the method Costco as well; other reviewers mentioned more methods as well.  The authors seemed to address most of these concerns in the rebuttal, adding more experiments and more details on timing.  26KD mentioned the optimization procedure was unclear, but the revision includes pseudocode in the appendix that clarifies.

Overall, the paper has both a theoretical and algorithmic contribution, and would be of interest to many ICLR readers.
Decision: Accept (Poster)