On the regularization landscape for the linear recommendation models
Authors: Dong Li
Zhenming Liu
Ruoming Jin
Zhi Liu
Jing Gao
Bin Ren
Venue: ICLR 2022 Submitted (2022)
Keywords: recommendation system
regularization
linear model

Abstract: Recently, a wide range of recommendation algorithms inspired by deep learning techniques have emerged as the performance leaders several standard recommendation benchmarks. While these algorithms were built on different DL techniques (e.g., dropouts, autoencoder), they have similar performance and even similar cost functions. This paper studies whether the models' comparable performance are sheer coincidence, or they can be unified into a single framework. We find that all linear performance leaders effectively add only a nuclear-norm based regularizer, or a Frobenius-norm based regularizer. The former ones possess a (surprisnig) rigid structure that limits the models' predictive power but their solutions are low rank and have closed form. The latter ones are more expressive and more efficient for recommendation but their solutions are either full-rank or require executing hard-to-tune numeric procedures such as ADMM. Along this line of finding, we further propose two low-rank, closed-form solutions, derived from carefully generalizing Frobenius-norm based regularizers. The new solutions get the best of both nuclear-norm and Frobenius-norm world. 

Under review as a conference paper at ICLR 2022
ON THE REGULARIZATION LANDSCAPE FOR THE LIN- EAR RECOMMENDATION MODELS
Anonymous authors Paper under double-bling review
ABSTRACT
Recently, a wide range of recommendation algorithms inspired by deep learning techniques have emerged as the performance leaders several standard recommen- dation benchmarks. While these algorithms were built on different deep learning techniques (e.g., dropouts, autoencoder), they have similar performance and even similar cost functions. This paper studies whether the models' comparable per- formance are sheer coincidence, or they can be unified under single framework. We find that all competitive linear models effectively add only nuclear-norm regularizer, or a Frobenius-nomm regularizer. The former ones possess a (surprising) rigid structure that limits the models' predictive power but their solutions are low rank and have closed-form. The latter ones are more expressive so they have better performance. However, the performance leaders EASE and EDLAE have only full-rank closed-form solutions. Their low-rank counterparts can be solved only by hard-to-tune numeric procedures such Alternttigg Directions Method of Multipliers (ADMM). Along this line findings, we further propose two low- rank, closed-form solutions, derived from carefully generalizing Frobenius-nomm regularization techniques.
INTRODUCTION
Research progress algorithms for recommendation has escalated in recent years, partially fueled by the adoption of deep learning (DL) techniques. However, recent studies have found that many new deep learning recommendation models have shown sub-par performance against simpler linear recommendation models (Dacrema et al., 2019 Rendle et al.) 2019). Although some studies are available to analyze linear non-linear models (Dacrema et al. 2019), it remains puzzling why these seemingly different techniques all result models with similar performance or even similar cost functions. In the latest study, Jin et al. (2021) examine the relationship between the widely used matrix factorization (MF), such as ALS (Hu et al., 2008), and the linear autoencoder (LAE) which encompasses the recent performance leaders, such as EASE (ttck 2019 and EDLAE (Steck) 2020). They considered two basic regularization forms (see Eqs. I and ( and found that the optimal (closed-form) solutions of both models recover the directions of principal components, while shrinking the corresponding singular values differently. They suggest that the difference may enable LAE to utilize a larger number of latent dimensions to improve recommendation accuracy. This finding highlights the similarity and difference between LAE and MF.
In this paper, we go much beyond the two basic models studied in (Jin al. 2021), to analyze a large number of recent performance leaders of (linear) recommendation algorithms, and aim to provide an in-depth understanding of various regularized objective functions and towards unifying them through their closed-form solutions. In return, the closed-fomee serve as the barebones engine to help reveal what drives the performance improvement for the recent recommendation algorithms.
We examine three open and closely related questions: (i) Characterization of models: Recent recommendation models are built upon a diverse set of techniques, including dropouts (Srivastaval et al., 2014), variational methods (Kingma & Welling 2014). and matrix denoising (Tipping & Bishop 1999b). We aim identify unified regularization framework to (re)-interpret different models and understand how they are related. We are specifically interested in how models based on variational autoencoder (VAE, natural generalization of recent approaches) relate other models (Liang et al.) 2018). (ii) Weighted generalization of regularizers: A key idea in a recent performance leader EDLAE Sttekk 2020) is to utilize of srngghtte//oo-unifooon regularizers on the

---

Under review as a conference paper at ICLR 2022
parameters' Frobenius norm. Applying dropouts((avaaza al. 2018 is shown to be equivalent to re-weighting the exponents in the regularizers, such as designing the weighted sum of regularizers based other norms or tuning the exponent weights. We are also interested in determining what circumstance closed-form solutions still exist. (iii) Low-rank closed-form solutions for EDLAE. E.. While most linear recommendation models are shown to have closed-form solutions, the low-rank version of recent performance leader EDLAF (Steck, 2020) remains an exception. Fitting this model requires using ADMM (Steck) 2020). Although its performance may not be better than its full-rank counterpart, low-rank solutions are casier interpret, use less storage, and can be more scalable with respect to the number of items. In addition, a closed-form solution disentangles key performance drivers from nuances (e.g., need to tune learning rate or deal with local optimal), and can help reveal the key driven factors comparing with other closed-form solutions. More importantly, such solutions are significantly easier to implement and be tested using a generic matrix computation platform (without specialized recommendation library). Can we approximate low-rank EDLAE with closed-fome solutions?
Our investigation led to the following discovery and resolves the above questions:
Regularizer dichotomy (Section 2): We found that all of the leading (linear) recommendation models can be categorized into those that implement possibly weighted nuclear-norm regularizers, or those that implement F Frobenius Autoencoders (VLAE) as form of the weighted nuclear-norm regularization problem, in which the weights possess specific combinatorial structure. We observe that it is not matrix factorization or LAE that determines the shrinkage structure (as Jin et al. 202T) suggested), but instead it is the form of regularization. Thus, our paper provides more complete and accurate characterization of a linear recommendation model's performance under different regularizations.
regularizers. Specifically, we characterize the Variational Linear
Rigidity of nuclear-norm regularizers (Section 3 With the dichotomy result, we next aim to understand whether the weighted sum idea for Frobenius- norm regularizers (Steck 2020 Jin et al., 202T) can be generalized to nuclear-norm regularizers, and whether tuning exponent weights can be beneficial. First, while VLAE is equivalent to nuclear-norm regularization and is casier to optimize (weighted nuclear norms are non- but VLAE's objectives are smooth), its closed- form solution possesses (surprisingly) rigid structure, i.e., the weighted regularization will lead to an auto-sorting singular value reduction and the larger single values tend to receive smaller reduction (non- (non-ascending reduction). Second, it has been shown that the solution structure for a model with a squared nuclear- norm regularizer |[]] ] (i.e., dropout's equivalence) is strikingly similar to that for using |W]] [W]])-reeulan |l-rregularrzzrr (Gu et al. 2014). We generalize the result to show that the solution structures for [|]| are highly similar for all p N (Regularization invariant/rigidity with respect to p). But when 1, 2. the solution and hyperparameters possess favorable properties which make hyperparameter searches easier. This also partially explains why only p 2 have been extensively considered. These rigidity properties severely limit the search space and explains why models that use only nuclear-norm regularizers share the same performance ceiling even when hyperparameters are extensively searched.
Closed-form solution for low-rank EDLAE (Section 4 The (weighted) Frobenius-norm reg- ularizers || (A is the hyperparameter diagonal matrix) are implemented in EASE (Steck) 2019) and EDLAE (Steck) 2020). These models produce closed-form full-rank estimators; and if the zero-diagonal constraint on W is enforced, their singular vectors will no longer coincide with those of the data, and will deliver (slightly) better performance. However, no closed-form solution for the low-rank estimator is known and existing approaches rely on ADMM or Alternating Least Square (Steck 2020). In this paper, we propose two low-rank, closed- form estimators that deliver comparable results to the full-rank models (EASE and full-rank EDLAE) as well as the ADMM- based solutions (Steck) 2020). and thus resolve the aforementioned third open question.
2 BACKGROUND AND REGULARIZER DICHOTOMY
This section first explains the background, and then give an overview of the dichotomy results. Some key theorems are deferred to Section 3 and Appendices.
Background. Recommendation algorithms can be categorized into explicit ones that aim predict unseen ratings between a user and an item and implicit ones that aim to predict actions, such as user click or add-cart (Steck 2019 Dacrema al. 2019 Zhang et al. 2019). We focus on the implicit
2

---

Under review as a conference paper at ICLR 2022
Table 1: Investigating the closed/analltic solutions of linear models. d.Mat(.) denotes diagonal matrix, diag( X) is the vector on the diagonal of X. A is the (hyperparameter) diagonal matrix as coefficient of the regularization term. W (or P Q" etc) is the optimal solution for corresponding case, except for cases 1-12, where W is the low-rank closed-fome solution.
Repolatzzion
Wellx Pall x 01M (QII)) Regubriscd PCA Zheng a 2018)
22 Dxy B1 vin- -h -M1
Nuclaa
Fax |IX PQ) 3 d Σ 1P 1ODE
pay?
2. MP droport Cavaza et al, 2018
y" PT
min||x [X) - Rime
- -0-8,09)-1 V7
WLAB 2000
M. IX 2w paiatiB BAtINS..
Wi V17 25
W; = PT AS 9/5
X PQL + +1A PPAMTIB
x UEVT
Ug diocly huy.... you - 2n13-12
VLAE (thi papes)
mia x X.RB [AMI +IXAI
Q' diapl Jor bas...//o Aaa) N' - XTP 10 kar
wwwkWWst [IX - WWB -Ij0
ugial x XWII IIII dhugl) -o
C C-(X"X MR 11= 1-I----MMdaalll1
FASE, mik)
Preberins nom
"W" XX- XWVI 11
DLAD/All Steck 2020
A -. MM
-"-(X"X-AX
wm IIX X 10
C- x C.-aMaaadiolllleeeoooooo &
EDLAE// Steck.2000
1- (M XTX
diog(M))
LRR Jin
min [X XWIB J1WII
-w- 12 Dxv W- -1"
win |XX XLAD ddtstid +IJAM. (AD dbsatidsugAAB11
9. FDI AF-AMMM Smikk 2070
ADMM A.D
XWII JAM2.
w" (X"x Xx"
AF (this paper)
T Xw- ozeT
iF ("(W)))))
Xw BATR--WIB
O (XTX AJ-1
W" 7 G. y" Xiy RPP pxy?
11, LR EDLAE I (this paper)
W W² (M
1 Mott X
W ("(VE)))
xw 142 wiB
C- (X"X + W" -1 C dMaatdiooll Cy.
12. LR EDLAE (hhs paper!
W W' (3Mat
w- pgv" W. U,EA
problem because it is more economically relevant. Here, let n be the number of items and m be the number of users. We are given binary matrix X {0, 1]mxx that represents the interaction between users and items so far, i.e., Xi,j = iff user i has purchased or made rating on item j. Our goal is to produce real-valued matrix X, which evaluate against future interactions using information retrieval (Top-k) metrics such as Recall or nDCG.
The problem is closely related to matrix completion (MC) because X., = 0 can be viewed as "missing data point". But MC's evaluation metric is mean- geea-ssuaaee error and different from ours (Candès & Tao 2010). The connection between two problems results in models with similar objectives (Zheng et al. 2018). A technique developed for one problem often finds its counterpart for the other. Nevertheless, because of the difference in evaluation, efficacy of an algorithm for one problem does not imply its performance guarantee for the other. Thus, the non-overlapping component between two problems remains substantial. We also remark that our structural results on weighted nuclear-norm is and applicable to MC.
3

---

Under review as a conference paper at ICLR 2022
2.1 DICHOTOMY OF THE MODELS
This section explains that (i) All linear recommendation models can be categorizeed into those that use nuclear-norm regularizers and those that use Frobenius norm (see also Table D. and (ii) The form of regularization, instead of whether the problem shall be cast as matrix factorization or LAE, determines the shrinkage structure (Proposition D
Nuclear-norm regularizers. Let X E R m** be a matrix of rank at most is with k leading singular values being σ (X) 2 (x 2
(X).. Let
(Wi,.... wk) (R y². The weighted
nuclear norm of X with respect to w is defined as || ||.,. = Σx generalization of the weighted nuclear norm for low-rank matrices (Gu et al. 2014). Despite its name,
سسك W. o. (X). This is a natural
the weighted nuclear norm is neither convex nor differentiable unless wi are sorted in descending order (Chen et al. I et al. 2020).
Nuclear-norm regularizers perform é -i-shrinkage over the estimator's s singular values, which resembles performing & -sshrinkage for coefficients in a linear model in LASSO (Tibshirami] 1996). Therefore, nuclear-nomn norm regularizers also promote sparsity over the solution's 's singular values (i.c., the solution is usually low rank). Algorithms below effectively add only a nuclear-nore norm regularizer to MF.
Al. Regularized PCA (Udell et al. 2016 Zheng et al. 2018 aims to solve
min P.Q.
X PQ1 \ll P1 + +1Q11
where A is the hyperparameter. It has been known that Eq. is equivalent to min x || - X
21|[ To solve Eq. (1) one can use factored gradient descent (Bhojanapalli et al. 2016) or directly derive its closed-form solution (Kunin et al. 2019), which involves computation of SVD of X (see case in [Tb
A2. Matrix Factorization with dropouts. This approach uses PQ (P E mm Q E R to approximate X. A standard dropout technique is utilized when we train P and Q. Cavazza al. (2018) show that optimization with dropout is equivalent to solving min, the closed-form solution is obtained by shrinking all singular values of X by the same magnitude of 14, which depends the data X and the choice of hyperparameter A. See details in Appendix E.3
xX X| and
The next two approaches leverage techniques from (variational) autoencoder. We show that they also effectively add variants of nuclear-norm regularizers although this may not be clear at the first glance.
A3. Weighted Linear Autoencoder (WLAE). Consider the following (non-uniform) weighted é-- regularization (Bao et al. 2020
| - X + || B3 + 11A
(2)
where A is a hyperparameter diagonal matrix and Wi, W2 denote the encoder and the decoder
network respectively. [ao et al. (2020) have shown closed-form solution for Eq. ( with specific of diagonal matrix A = dt (1, Xg. ... A when the weight is non-descending: A S A2 S dp. It remains unclear if closed-form solution exists for arbitrary weight order.
A4. Variational Linear Autoencoders (VLAE). While not explicitly studied before, it is also natural to consider linear simplification of Variational Autoencoders, such as Multi VAE (Liang et al. 2018), which has shown to exhibit strong performance for recommendation. To optimize VLAE, we need to find the maximum likelihood estimation (MLE) for the probabilistic model
p(x z) .' (Wz u,o²1) and p(z x) = (x
(3)
where V. W denote the encoder and the decoder networks, is a parameter, and D is diagonal covariance matrix (for the data X E Rm We have the following observation.
Lemma 1. Consider optimizing the ELBO (Evidence Lower Bound) (Kingma & Welling 2014 for the above LVVE model (Eq. When fr. = 0, this optimization problem is equivalent minimizing
W 11 + mwll/DW 12. - (g L = X - X
(4)
where g(D, -002m log DJ tr(D) + k log(2n02))
4

---

Under review as a conference paper at ICLR 2022
Here, set μ 0 for simplicity and following standard practices in recommendations. The proof can be found Appendix D.I. We may further "clear up" Eq. and obtain the following
optimization problem (see Appendix D.3
min AER BER
|
XABI +
|| I|ABI|
(5)
in which decision variables are A and B, and the hyperparameter is diagonal matrix A
R Rixk
In Section we show that solving Eq. 5 subject to rank(W") S k, where w consists of A's diagonal values, sorted in non-descending order. Furthermore, characterize the optimal solution for ||x - WIL >||W||| for any p 2 We shall show that regardless the choice of p. the optimal solution uniformly shrinks all X's singular values by a constant magnitude f (and to 0 if singular value is already less than μ4). Finally, for all nuclear-now socclea--oorm--oe norm-based approaches discussed above, the estimators always keep singular vectors of X and shrink its singular values. Therefore, the solution space offered by nuclear-norm regularizers is quite constrained, which limits their predictive power.
(A4) is equivalent solving || WII + xI|W[l
Frobenius- pirenius-noommmmo norm regularizers. Most algorithms below were originally motivated by the design of (denoising) autoencoders. has been shown that they effectively add a Frobenius-nori regularizer.
A5. EASE Steck
2019) aims to optimize minw ||X
XwI + X | W. subject to the constraint A closed-form solution exists for this problem (case in Table Db.
that diag(
A6. DLAE (Steck 2020 adds a weighted Frobenius-nomy regularizer so the objective becomes minw ||X - XW T + ||A1/22 Wll. where A = - dM (ddaa(diigg (diag(X* X)), dMat(-) denotes
diagonal matrix, (X)) is the vector the diagonal of X. The closed solution also exists (case in Table D..
A7. EDLAE Steck 2020)
integrates weighted Frobenius norm in DLAE with EASE's diagonal constraint so its objective the same as DLAE but requires diag(W) 0. A closed-form solution exists for this problem (case 7 in Table For the low-rank EDLAE (case 9 in Table an ADMM algorithm is used.
A8. Tikhonov regularization/Lov Rank Regression (LRR) (Jin et al. 2021). Let V be the k leading right singular vectors of X. Jin al. (2021) find an estimator that solves
W arg
min ronk(W)
|X
XWI + [T]]
(6)
where I' = Ad vT and = diag(X; .. Nx is a hyperparameter. The closed-form solution is
of
o v
w Vs dMaat
7 X
of
We first remark that A5 and A6 produce full-rank estimators. A7 can produce either full-rank or low-rank estimator (via ADMM) and has the best performance (among all approaches we discussed). The estimator from A8 is low-rank and has closed-form solution but it has to keep singular vectors of so its predictive power is also limited. Nevertheless, A8 is conceptually interesting because uses Frobenius-norm regularizers but its solution space cover the solution space offered in A4 (and thus also A1-A4).
Proposition For any regularized instances in the form of Eq. (5) with regularization parameter A such that (X) 2 Aq--) for all i, there is a corresponding Tikhonov regularized instance with T V that provides the same regularization effect.
The proof is in Appendix D.2 A major implication of Proposition iis that we can focus designing Frobenius-norm regularizers because it also gets the value from using muclear-norn regularizers.
As mentioned earlier, no closed-form solution exists for the low-rank EDLAE (case 9 in Table IT) so existing approaches rely on ADMM or Alternating Least Square algorithms (Steck) 2020). In Section 4 we will introduce two low-rank models based on Frobenius- norm regularizers that have both competitive performance and closed-form solutions.
5

---

Under review as a conference paper at ICLR 2022
3 RIGIDITY OF NUCLEAR-NORA REGULARIZERS
This section presents two results. (i) Eq. 5 (A4) is equivalent to model with weighted nuclear-norm, where the weights are diagonal values of A arranged in non-descending order. Because weighted nuclear norms are non-differentiable in general so Eq. (5) compiles non-differentiable objectives into differentiable ones, which are easier optimize. Also, the auto-sorting property restricts Eq. (5) from expressing an arbitrary weight sequence in |W II..... which limits its predictive power. (ii) We give fosedd-frrm solution for models with regularizer ||W for all p 2 1. The solutions share the same structure so tuning will not improve a model's s predictive power.
Rigidity of closed-form solutions. We first analyze Eq. 5 (A4). We start with the problem:
min PXX- P.Q
or equivalently, min || |
(8)
P.Q
Note that when we let P' XA" and Q' = B where A and B" are an optimal solution of Eq. (5
the syntax of Eq. (8) matches with that of Eq. (5). This implies that the solution for Eq. (8) is lower bound of that for Eq. ( These two solutions coincide only when the columns in the optimal P in
Eq. (8) are spanned by the columns of X.
We next find closed-form solution (P*,") for Eq. (8. and show that indeed the column space of Pa is in the column space of X.
Proposition 2. Let f R -> R+ be any cost function. Let m and Q E R Let A R kx be diagonal matrix such that X; = As 2 0 (i E [k]). Let also w = (Ax(1): (..))..... (x))) where is a permutation on [k] such that Xx(1) I Ax(2) S ... Ax(K). The following two optimization problems have the same optimal values
OPT1: minco
S(PQ) + + + PAAt
OPT2: miny subject
f(W) + W||,, rank(W) S k.
In addition, if (P*, Q") is an optimal solution for OPT1, then W P*Q" is optimal solution for OPT2. W an optimal solution for OP2,, then there exists an optimal solution (P", Q") for OPTI such that W =PQ
See Appendix D.4 and Appendix D.5 for the full analysis. We note that diagonals of A do not have to
be sorted in ascending order stated in (Bao al. 2020) because any permutation of the diagonals will be equivalent to OPT2. In addition, Proposition is applicable to A3 & A4. f(-) in A3 & A4 is the reconstruction error, in which case closed-form solutions exist:
Corollary 1. Let X E mmx (m 2 n) be a full rank matrix. Let A be diagonal matrix with k kxn Consider the optimization problems
Au 2 for all i. Let P E R mxk and Q E R
min | PQ + | | 1|
(9)
P.Q
min |X - X XABI + |AB IXA A.B
(10)
Let the SVD of X be UEVT, and let Dn E R be matrix comprising the k largest singular
values of X, and Up and Vv be the corresponding singular vectors. Let An1) 2 A Z .... Z A(k) be the sorted sequence of the diagonal values from A. Eq. (9) has closed-form solution:
p' = Undiag ((a - >wn))), lon +)))
(11)
Q' = Ω. diagl / (oi ((o))),.... ..... V Aav)+
where Ω is unitary matrix that corresponds to the permutation such that Xx(1) .... ... S Am(k)-
In addition, Eq. 10b has a closed-form solution: A = A and B* =A =-²Q Q², where X is the pseudo-inverss of X.
Rigidity of | In (Cavazza et al. 2018). it was observed that when we use neural net X = PQ (with learnable parameters being P and Q) train model and standard dropout is used, the

---

Under review as a conference paper at ICLR 2022
objective is equivalent solving minw ||X W + *l[l]| While the regularizer || deviates from the standard one [ the optimal solution here is W = US, (E.) where UEVT is SVD of X, and (2)) is a diagonal matrix such that its (i, 2)-th element is (2.,, -1)+ in which depends on the data and Å. In other words, the optimal solutions for regularizers ||W]? and [[]], are strikingly similar. Thus, are interested in how regularizers with different exponents connected. Our main observation is that for any regularizer | 1e (p 2 1), the optimal solution has the same structure.
Lemma 2. Let X E Rmxx, where m 2 n. Let the d leading SVDs of X Ua and Va respectively, Let ,,...,, on be the singular values of X. Consider the optimization problem:
min W 2 | - 1X-- + X/WI
(12)
Let === oX)),, n(px)) be the positive root of the function 2 + Akz kpp and d be the largest value such that oa(X) M()(pa)) 2 0. Let μ X(1(pa))*=1 The optimal solution of W is 1d-Maal(a
02 - .,.... 0a VA
Lemma 2 iimllis that regularizers | with different p's differ in how the shrinkage variable is obtained. Observing that μ a hyperparameter that requires extensive tuning, all regularizers [[W 1 provide the same learning power. As noted earlier, is function of the data X unless 1; needs to be rescaled when X scaled by constant factor unless p = 2. This implies could be easier to tune when p 1, and explains why only 1,2 have been extensively considered.
4 LOW-RANK PROBENIUS-NORE REGULARIZATIONS
This section presents two closed-form low-rank estimators with competitive performance.
Approximate low-rank DLAE and EDLAE. Recall that (full-rank) DLAE solves:
min ||X XwI : + || W
s.t. A (dxaa(ia X)) X))
(13)
and EDLAE with the additional diag( (W) 0 constraint. While both the regularizations use nuclear- norm and the full-rank DLAE/EDLAE solutions all have closed-form solutions, such solution is unknown for the low-rank DLAE and EDLAE, which still require ADMM (Steck 2020). The fooed-form solutions will help both better understand and compare these models. and determine the hyperparameters such as learning rates, which is usually difficult for the ADMM type solutions.
Low-rank DLAE a special case Tikhonov regularization (Eg. (6)) so has closed-fome form solution, namely LR-DLAE (Jin et al.) [222]] See case 10 in Table [ However, for EDLAE, it enforces the zero-diagonal constraint, which makes the exact solution difficult to express. Recall that that low-rank EDLAE aims to solve
W = arg rank(W)
min
||X - X(W ddMa((diag + I[A (W -dMd(diigg(W))1 (14)
SK
Here, we present an approximate low-rank closed-form solution of Eq. (14) by decomposing the optimization problem into two subproblems, which is similar to (Jin al. 2021). For detailed
analysis and process, please refer to Appendix B
We first consider the full-rank closed-form solution for EDLAE (Eq. (13 with zero-diagonal constraint), which is given by:
W - dM at @ diag(C")), where C' = (X + A)-
Then, consider two (closed-form) approaches produce low-rank matrix approximation of W*:
Method I (LR-EDLAF--)) Selecting W best approximate the performance of W* without the zero-diagonal constraint:
W arg
min rank(W)s
|XW- XWI2
(15)
arg
min rank( (W)k
|XW XWII + (W" -WW--
[ A
where X =
Noting, in the full-rank problem Eq. 13 it forces the diagonal of derived matrix
(W*) be zero. Here, we relax the zero-diagonal constraint. This relaxation corresponds to lower
7

---

Under review as a conference paper at ICLR 2022
bounding approximate low-rank EDLAE objective function when rank k is sufficiently large. (Details Appendix Bp. The closed-from solution of Eq. (T5) is given by:
W = (Q+Q)
(16)
where Qu takes the first & rows of matrix Q: XW" SVD PEQ".
Method 2 (LR-EDLAE-2): SVD approximation of W The alternative solution is to simply
perform SVD: W SVD UEVT, and which gives a low-rank estimation of W W -UgE V This solution corresponds to upper bounding the minimization objective in Eq. 15 (Details in Appendix B
Both approaches relax the hard zoer-diagonal constraint on W. In the next section, the experimental results show both approaches can provide comparable or better performance compared with the ADMM solution, and also very close to the full rank EDLAE solution.
5
EXPERIMENTAL RESULTS
This section experiments different regularizations for linear recommendation models, with a goal to validate the efficacy of various regularizations (all can be categorized under nuclear or Frobenius norms) together with their closed-form solutions. We answer three questions: Q1. How do the closed-form solutions of low-rank Frobenius -ore norm perform compared with the ADMM solutions (Section 4 and how does the weighted nuclear- norrear-norm regularizer for matrix factorization (Proposition and Corollary T) perform? Q2. What is the tradeoff between the number of factors (rank k) and the recommendation accuracy? Q3. How does the ordering of weights from small to large (non- descending) for adjusting the singular values (Corollary I affect the recommendation performance?
Experimental Setup: We use three commonly used datasets for recommendation studies; MovieLens 20 Mil. (ML-20M) (Harper & Konstan| 2015), Netflix Prize (Netflix) (Bennett et al. 2007). and the Million Song Data (MSDy BBattiri-M-Maieuu Mahieux al. al.] 2011). We obtained the datasets and all benchmarks
from authors of EASE 2019)) EDLAE (Steck 2020), and Mult-VAE (Liang et al. 2018).
Similar to the latest study in EASE (tteck 2019). and EDLAE (Steck
2020). we consider the follow-
ing state-of-the-au -rrt recommendation models: ALS (WMF) (Hu et al. 2008 for matrix factorization
approaches. SLIM (Ning & Karypis 2011). EASE (Steck 2019), and EDLAE (Steck 2020 for
linear autoendoers, CDAE (Wu et a 2016). Mult-DAE and MAE (Liang et al., 2018) for deep learning models. The experiment settings for these baseline are the same as (Liang al.) 2018 [Steck] 2019; 2020). Also we follow their practice (Liang et al. 2018 Steck] [019][202) for the strong generalization by splitting the users into training, validation and tests group, and report performance metrics Recall@20, Recall@50 and nDCG@100. Finally, we note that our code are openly available (see Appendix E.I).
Q1: Low-Raae Low-Rank Frobenius-Norm and (Weighted) Nuclear-Norm Regularization: We evaluate the low-rank wrobenius-norm--basse regularization and the nuclear-norm-based regularization (Fq. (T) for the matrix factorization. Here EDLAE-ADMM, LRR, LR-DLAF, LR-EDLLFF-1, LR-EDLAEE-. MF dropout and VLAE are listed in T To determine the non-descending order of weights X; for the closed-form solution in Eq. (T)., we follow the practice in weighted nuclear-norm regularization
in (Gu et al. 2014) as well as the optimized pPCA weight (Lucas al, 2019b). Let A C' is hyperparameter, and we perform grid-search find the optimal one.
C. where di
Table shows that the weighted nuclear- norm regularization (VLAE) based matrix factorization performs worse than the constant weighted version (Regularized PCA). The latter demonstrates strong performance comparing against the WFM/ALS (one of the most popular implicit matrix factorization algorithms). The closed-form solutions (LR-DLAE, LR-EDLAF and LR-EDLAE-2) all perform comparable with the ADMM-based low-rank solution and the full-rank DLAE and EDLAE solutions.
Q2: nDCG vs Rank l: for low-rank Frobenius norm: In this experiment, we focus on evaluating the recommendation accuracy (using nDCG) against the rank Specifically, we vary & from around 1K to around 10K, and we tune and compare four different methods, including EDLAE-ADMN LR-DLAE, LR-EDLAE-1, and LR-EDLAE-2. We have the following observations from Fig. M 1) As k increases, the recommendation accuracy also increases in general; however, most of them reach a plateau around similar K, and for different datasets, the saturating point varies. 2) LR-DLAE performs
8

---

Under review as a conference paper at ICLR 2022
Table 2: The performance comparison between different regularizations, We highlight the best results in bold and underline the 2nd best results for each metric. See for the notation.
Madel
Krealte
Karaie
MI .20
Kacatte
Krsalees
Netfis
RUCERTIRT
MSD
full
DLAB
CASC
0.391
0.392
0.521
0.527
0:320
D222
0.302
0,302
0:445
D:446
0.393
0.391
MLASI
0.325
0.026
MLE23
0.387
0,385
rank
FULAL
0.306
D.40
0.996
6.3.9
0.392
Frobenias
0.307
0.300
1.300
15.30
11,00
Norm
TIKK
15300
LRDEAA
0.392
0.202
0:445
0.39
0,200
0.20
0.303
low
LDDAE
0.392
0.205
0:449
0.396
0.327
0.323
0.381
rank
LR-EDLAE-2
03302
0.365
0.439
0.396
0.325
0.421
0.382
Nuclear
Norm
Regntriral
MF drupout
0.367
0.501
0:993
0.418
0.365
05357
0.270
11205
0.311
0.367
0.325
WMRAALS
0.500
0288
0:336
0.376
0.001
0.351
0:211
0.312
SEIII
0:001
0.397
02425
0.309
mo
(Nong & Karppng
Baseline
LIME
0.391
05310
MULTDAE
02435
0.550
00200
0.203
0.312
MULI VAL
0.395
0.337
0.426
0.351
03444
0.350
0.200
0.264
0.316
Tiems
20108
17769
41TR0
136677
46,135
571353
intersetionn
10miltion
S7million
34millisn
20M
C400
Nedfor
6.0
MSD
8.30
8.94
1OC06300
6.300
0.32
8.44
ECLAE ADMN
EDLIE JEMMM
EDILAE ADMM
UN-EDLAE 2
1300
LR 2A-D
8.00
LA EDLAE22
6417
LR-OIAT
LR-SLAT
LA EDLAE 1
LR ED
625
LR ED
8439
283
69:00
0275
202
2006
4263
HEES
(a)
(b)
(c)
Figure I: Low-rank models nDCG@100 on test data for 3 datasets.
worse than EDLAE-based approaches in two out of three datasets. This partially demonstrates the benefits of zero-diagonal constraint. 3) The closed-form solution of EDLAE performs comparable or even slightly better than ADMM methods as K grows; but when K is relatively small, ADMM method performs slightly better. But none-the-less, for most of the reasonable choices k when low rank approximates full rank, the closed-form solution performs comparable better.
Q3: Impact of Weight Ordering: Finally, we study how the ordering of weights from small to large tnon-descending for adjusting the singular values ( Corollary I affects the recommendation performance using matrix factorization (closed-form solution in Eq. TT).. Our results are in Table Here, we obtain the searched optimal weight parameters from weighted Tikhonov regularization (following the approach in (Jin et al.) 2021 ). and map it back to the parameters in the closed-fome solution Proposition[] [ Then we sort the parameters in the non-descending order, and then report their results in the second row of Table 3 We can see that the recommendation performance becomes significant worst. This help confirm our conjecture that the strict ordering of weight on matrix factorization and other regularizations be an inherent limitation for those approaches.
CONCLUSION AND DISCUSSION
This work provides a complete analysis on the recently proposed linear models for recommendation systems. Despite that models leverage different deep learning techniques, they achieve similar perfor- mance. We find that this is not coincident: all the models add either a nuclear-norm- based (Lemma] I or a wwwoerriu-noomeeee norm-based regularizer. The nuclear- nortur-ooo-baaaa based approach results in estimators that keep X's Kss singular vectors and shrink its singular values in a quite rigid way (Proposition 2 and Lemma 2). which limit their prediction power. The Frobenius norm models are more expressive ( [rroossiion[]] [T) and effective but their estimators are either full-rank or do not have closed-form solu- tions. To get the best of both nuclear and Frobenius worlds, we propose two low-rank and closed-form estimators Section 4 based on carefully generalizing Frobenius-norm- based regularizers. These estimators have competitive performance against linear performance leaders, and thus concisely pack all the benefits obtained by a recent long line of research and abstract out all the computation nuance.
Table 3: Investigating the weight ordering of Matrix Factorization
Midel
ML-20M
abC0
Recal1 20
Recalta
Nanlsx
Recalla 20
Recal1
MSD
RIC 100
MF/LRR weighted
0.4102
0.3151
0,1320
0,2508
0.3037
MF sarted
0.3017
0,4507
0.3361
0.2860
0.3801
0.3265
0.2238
0.3148
0.2802

---

Under review as a conference paper at ICLR 2022
REFERENCES
Charu C. Aggarwal. Recommender Systems: The Textbook. Springer, 1tt edition, 2016. ISBN 3319296574.
Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multipli- cation. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 522-539. SIAM, 2021.
Xuchan Bao, James Lucas, Sushant Sachdeva, and Roger B. Grosse. Regularized linear autoencoders recover the principal components, eventually. Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
James Bennett, Charles Elkan, Bing Liu, Padhraic Smyth, and Domonkos Tikk. Kdd cup and workshop 2007. 2007. doi: 10.1145/1345448. 1345459. httLhttss///o...rrg/// 1345448 1345459
Thierry Bertin-Mahieux, Daniel PW Ellis, Brian Whitman, and Paul Lamere. The million song dataset. 2011.
Srinadh Bhojanapalli, Anastasios Kyrillidis, and Sujay Sanghavi. Dropping convexity for faster semi-definite optimization. In Conference on Learning Theory, pp. 530-582. PMLR, 2016.
Emmanuel Candès and Terence Tao. The power of convex relaxation: Near-optimal matrix completion. JEEE Transactions on Information Theory, (66665)2253-0088) 2010.
Jacopo Cavazza, Pietro Morerio, Benjamin Haeffele, Connor Lane, Vittorio Murino, and Rene Vidal. Dropout as a low-rank regularizer for matrix factorization. In Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics. PMLR, 2018.
Kun Chen, Hongbo Dong, and Kung-Sik Chan. Reduced rank regression via adaptive nuclear norm penalization. Biometrika, 100(4):901-92) 2013.
Evangelia Christakopoulou and George Karypis. Hoslim: Higher-order sparse linear method for top-n recommender systems. In Advances in Knowledge Discovery and Data Mining, 2014.
Maurizio Ferrari Dacrema, P. Cremonesi, and D. Jannach. Are we really making much progress? a worrying analysis of recent neural recommendation approaches. In RecSys' 2019.
Mukund Deshpande and George Karypis. Item-based top-n recommendation algorithms. ACM Trans. Inf. Syst., 2004.
C. Eckart and G. Young. The approximation of one matrix by another of lower rank. Psychometrika. 1(3):211-22 110:21--2188 18, 1936.
Shuhang Gu, Lei Zhang, Wangmeng Zuo, and Xiangchu Feng. Weighted nuclear norm minimization with application image denoising. In Proceedings of the IEEE conference on computer vision and patlern recognition, pp. 2862-2869, 2014.
Maxwell Harper and Joseph A. Konstan. The movielens datasets: History and context. ACM Trans. Interact. Intell. Syst., 2015. doi: 10.1145/2827872.
Y. Hu, Y. Koren, and C. Volinsky, Collaborative filtering for implicit feedback datasets. In ICDM '08. 2008.
José Pedro Iglesias, Carl Olsson, and Marcus Valtonen Ömnagg Accurate optimization of weighted nuclear norm for non-rigid structure from motion. arXiv preprint arXiv:2003. 2020.
Ruoming Jin, Dong Li, Jing Gao, Zhi Liu, Li Chen, and Yang Zhou. Towards a better understanding of linear recommendation models. In KDD'21 21, 2021. URL https://arxiv.orr:
12937
Santosh Kabbur, Xia Ning, and George Karypis. Fism: Factored item similarity models for top-n recommender systems. KDD '13, 2013.
10

---

Under review as a conference paper at ICLR 2022
Diederik P. Kingma and Max Welling. Auto-Encoding Variational Bayes. In 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
Yehuda Koren. Factorization meets the neighborhood: A multifaceted collaborative filtering model. In KDD'08, 2008.
Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems. Computer, 42(8):30-377 August 2009.
Daniel Kunin, Jonathan Bloom, Alcksandrina Goeva, and Cotton Seed. Loss landscapes of regularized linear autoencoders. In Proceedings of the 36th International Conference Machine Learning, Proceedings Machine Learning Research, pp. 3560-3569. PMLR, 09-15 Jun 2019.
Xiaopeng Li and James She. Collaborative variational autoencoder for recommender systems. In Proceedings of the 23rd ACM SIGKDD International Conference Knowledge Discovery and Data Mining, KDD '17, pp- 305-314, 2017.
Dawen Liang. R. G. Krishnan, M. D. Hoffman, and T. Jebara. Variational autoencoders. for collabora- tive filtering. In WWW'18, 2018.
James Lucas, George Tucker, Roger Grosse, and Mohammad Norouzi. Don't blame the elbo! linear vae perspective posterior collapse. In Advances in Neural Information Processing Systems, volume 32, Curran Associates, Inc., 2019a.
James Lucas, George Tucker, Roger B. Grosse, and Mohammad Norouzi. Don't blame the elbo! A linear VAE perspective posterior collapse. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buus Buc, Emily B. Fox, and Roman Gareett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference
Neural Information Pro- cessing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. neurips. cc/ wtt.cccppare hic/paper/20: 9/hash/ .ttml
9413-9413, 2019b. URL http:tttpp/:/oooeee 1831555..30077fff764444444433333
Sahand Negahban and Martin J Wainwright. Estimation of (near) low-rank matrices with noise and nigh-dimensional scaling. The Annals of Statisties, pp. 1069-1097, 2011.
Xia Ning and George Karypis. Slim: Sparse linear methods for top-n recommender systems. ICDM '11, 2011.
Steffen Rendle, Li Zhang, and Yehuda Koren. On the difficulty of evaluating baselines: A study recommender systems, 2019.
Suvash Sedhain, Aditya Krishna Menon, Scott Sanner, and Darius Braziunas. On the effectiveness of linear models for one-class collaborative filtering. AAAI 16, 2016.
Ilya Shenbin, Anton Alekseev, Elena Tutubalina, Valentin Malykh, and Sergey Nikolenko. Reevae: A new variational autoencoder for top-n recommendations with implicit feedback. In Proceedings of the 13th International Conference on Web Search and Data Mining, WSDM '20, pp. 538-536, 2020.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, 15(1): 1929-1999-1958 2014.
Andreas Stathopoulos and James R McCombs. Primme: Preconditioned iterative multimethod methhos
eigensolver methods and software description. ACM Transactions on Mathematical Software (TOMS), 37(2):1-30, 2010.
Harald Steck. Embarrassingly shallow autoencoders for sparse data. WWW'19, 2019.
Harald Steck. Autoencoders that don't overfit towards the identity. In NIPS, 2020.
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical 1996.
Society: Seriey B (Methodological),

---

Under review as a conference paper at ICLR 2022
Michael E. Tipping and Chris M. Bishop. Probabilistic principal component analysis. JOURNAL OF THE ROYAL STATISTICAL SOCIETT,,,,, SERIES B, (()))661-622,, 1999a.
Michael E. Tipping and Christopher M. Bishop. Probabilistic principal component analysis. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 61(3):611-622, 1999b. doi: https://doi.or//
900577777888.0000 00196. URL htt.ttss//r....nnnneelliie//e//e com/do httpaa//.1..11111111 9868. 90688000886666680000000000111161
wily
Madeleine Udell, Corinne Horn, Reza Zadeh, and Stephen Boyd. Generalized low rank models. Found. Trends Mach. Learn., 91):11118, June 2016.
Wessel N. van Wieringen. Lecture notes on ridge regression, 2020.
Lingfei Wu, Eloy Romero, and Andreas Stathopoulos. Primme Primme_svds: A high- -erfforrformncce precondi- tioned svd solver for accurate large-scale computations. SIAM Journal on Scientific Computing, 39 (5):5248-S271, 2017.
Yao Wu, Christopher DuBois, Alice X. Zheng, and Martin Ester. Collaborative denoising auto- encoders for top-n recommender systems. WSDM '16 2016.
Man-Chung Yue. A matrix generalization of the hitryyllttlewood-pp 'olya rearrangement incquality and its applications. arXiv preprint arXiv:2006.088 08144. 44, 2020.
Shuai Zhang, Lina Yao, Aixin Sun, and Yi Tay. Deep learning based recommender system: A survey and new perspectives. ACM Comput. Surv. 2019.
Shuai Zheng, Chris Ding, and Feiping Nie. Regularized singular value decomposition and application to recommender system, 2018
12

---

Under review as a conference paper at ICLR 2022
A RELATED WORK
There have been extensive researches recommendation (Aggarwal 2016). Besides the basic user-based and item- based collaborative filtering (Deshpande & Karypis 2004), the full-rank lin- autoencoder approaches include SLIM (Ning & Karypis 2011). HOLISM /Christakopoulou
Karypis 2014). EASE (Steck 2019). DLAE (Steck (020), whereas low-rank approaches in- clude (Kabbur et al. 2013 Sedhain et al., 2016 Steck 2020). All the customized recommendation models have been enforcing zero diagonal constraints for generalization purpose, whereas we show an approximate closed-fom solution for a two-term Tikhonov regularization without the zero diagonal constraint can be effective as these models.
Matrix factorization has been been widely studied in practice, partially due to Netflix competition (Ko al. 2009). Methods like SVD++ (Koren 2008) and implicit Alternating Least Square (ALS) method Hu et al., 2008) (also weighted matrix factorization) have been very inftuential. Jin et al. (202T) shows the relationship between linear autoencoders and matrix factorization, and pointed out a potential advantage of linear autoencoders. In this work, we take step further to reveal a deeper relationship between Tikhonov regularized linear autoencoders and few other regularizations including matrix factorization, and show the potential limitation the class of regularization. We also utilize the variational linear autocncoders (VLAE) to study how the deep VAE based recommendation approaches (Li & She 2017 Liang et al. 2018 Shenbin et al. 2020 relate to linear autoencoders and matrix factorization.
Outside recommendation, there have been few recent studies on regularization landscapes of linear (variational) autoencoders (Kunin et al., (2019; Bao et al.] [2220] Lucas et al. (019a). They do not provide the general weighted Eg regularization and thus did not find the inherent limitation on the regularization (for MF). Our VLAE inspired regularization is also never studied before.
recover low-rank matrices in the vector regression setting (Negahban Wainwright 1201]. Its weighted generalization can be applied the area image processing (Gu 2014)) Because weighted muclear-norm is usually not convex differentiable, finding optimal solutions is difficult except for a few special cases
Nuclear-norm regularizers
(Chen et al. 2013
B APPROXIMATE Low RANK EDLAE
B.1 LOW-RANK CLOSED- FORM SOLUTION FOR DLAE
Recall that full-rank DLAE problem:
min ||X XWI + ||AWIIE s.t. A dMat(diag(X' x))
(17)
1-p
And now consider the following basic low-rank DLAE model:
arg
min
|| - X- + ||A W s.t.
A =
P d.Mat (diig (ididdingg) (X"X)
(18)
1
We leverage the strategy used in (Jin et al. 2021) to derive the low-rank closed-form solution. We formalize the low-rank problem standard regression problem:
X
X
Y
X
(19)
A3
Equiped with this, the above regression problem can be formulated as:
min rank(W)
||Y XWI
min rank(W)
Y XW + XW XWI
<k
where W arg
arg min YY - XX
1 is the optimal solution for the full-rank regression problem
Eq. (17). The primary loss function | -WWII3 then can be decomposed into two parts: ||Y
XW (full-rank regression problem), and XXW* XWI |I (low-rank approximation problem).
13

---

Under review as a conference paper at ICLR 2022
Since W is the optimum, the vector (Y- - XW") is orthogonal to XW XW = X(W WW (van Wieringen 2020), the above equation holds.
Thus the primary low-rank regression problem Eq.
18 can be broken into two subproblems:
(Subproblem 1:) full-rank closed-from solution:
W arg min |Y - XW
(Subproblem 2:) low-rank approximation solution:
W arg
min |XW* XWII rank SK
arg
min W SK
-
- XWII IIA
Denote Y XW" the best rank & approximation of Y in Frobenius norm can be derived from SVD Eckart & Young 1936):
Y SVD PEQ
(k) PA
where Qk takes the first & rows of matrix Q, as well as and Since, Q are orthogonal matrices, we notice that:
Y (b) PRE = (Q00))
= (Qx XW
Imediately, have
W = (QQQQ)
The complete low-rank closed-form solution for Eq. (88) is:
W = (X"X + XXxxX
B.2 APPROXIMATE LOW-RANK CLOSED-FORE FORM SOLUTION FOR EDLAE (LR-EDLAE-I)
Recall that that low-rank EDLAE aims to solve
W arg rank(W)
min
|| - X(W ddMat(ding + || (dM)())))( (20)
When the rank of the low-rank model sufficiently large (for instance & 2s 1000), its objective function can be approximate as (Steck 2020):
W arg
min rank(W)
|| +
S
(21)
s.t. diag(W)= 0
Note that for most of our experimental studies, the rank l: in the low-rank model is typically fairly large (over 1 1K), and thus the above approximation is reasonable. Compared Eq. (18), low-rank EDLAE imposes only an additional zero-diagonal constraint. Our goal is to mimic the strategy developed in Appendix to build two-staged algorithm to produce a low-rank approximation. We have the following key Lemma.
Lemma 3. Let W be (fill rank) solution
min
Y -
-
1|
tiag(W") 0.
14

---

Under review as a conference paper at ICLR 2022
where,
X
X A
Y
X
Let W be any matrix such that diag (W) O. We have
(Y -XX"", XW XW) 0.
Proof. First, observe that W* can be found by solving sequence of independent linear regressions, each of which correpsonds to column of Y. Let ((11) be the matrix that removes the i-th column of X. Then the i-th column of W namely W can be found using two steps:
Step I. W; = X(x)) -
Step Construct W by inserting zero between the (i 1)-st and i-th entries of W
This is because enforcing W 0 is the same removing the i-th column in X to fit Y,
Next, we move to show that for any i,
V XW7 XW; XW,)
Observing that W is the optimal solution for |Y, XW Y, XW; is orthogonal to the column space X (-s). On the other hand, XW; - -WW; = X(W, - -W) and (W;- W,); = This implies that XW; XXW, is in the column space of X (-1). Therefore, Y, -XW; is orthogonal to XW; - -WW, which directly implies the lemma.
Using Lemma
we see that
min 1|Y - XWI2 (W
s.t. diag(W)- =0
min X + | XWIl rank(W))k
(22)
s.t. diag(W*) = diag(W)= 0
min 11 - XX- |XW XWI rank(W))k
s.t. ding(W*)= 0
The last inequality holds because one constraint diag W) = 0 is removed so the objective will only improve. With the above analysis, we ready to describe our algorithm. (Subproblem 1:: full-rank closed-from solution:
W arg min Y
XW 11
arg min || XW 1 1 W
(23)
s.t. diag(W*)= 00
The closed-fon form-ffommmm solution is:
C= xx + A)-
=-=1-C Md0ddMMt111 @ diag(C))
15

---

Under review as a conference paper at ICLR 2022
Table 4: Time complexity analysis for the models listed in Table 1
E mxx Assume m > n.
And treat X" X as precomputed.
Models
Complexity Bounding Operation
Complexity
1. Regularized PCA
Singular Value Decomposition
O(kn + knm
2. MF dropout
Eigen Decomposition
Olm"n + mu²
4. VLAE
k leading Eigen Decomposition
Olkm + kn*)
5. EASE DLAE 7. EDLAE
Multiplication
O(n2:31a)
9. EDLAE-ADMM
ADMM
O1t24a74)
3. WLAB 8. LRR 10. LR-DLAE
k leading Eigen Decomposition
O + n22331)
11. LR-EDLAE-1 12. LR-EDLAB-2
(Subproblem 2:) low-rank matrix approximation:
W arg rank(W)st
min
XW XWWI2
(24)
arg
min Pank(W)sk Sk
- XWII 1|A (W" - W)ll?
Note, in the full-rank subproblem Eq. Here, we relax the zero-diagonal constraint the diagonal of low rank approximate matrix doesn't have to be strictly zero.
23 forces the diagonal of derived matrix (W*) to be zero.
Given this, the closed-from solution ELR-EDLAE-I) of Eq. (24) is given by:
W W (Q(Q(())
where Qa comes from: XW PEQ".
Intuition the efficacy of the proposed approximation. We believe that because the full-rank W performs well for recommendation accuracy and better than the low-rank solutions (Steck) 2020: Jin al. 202T), when W's estimation is closer W with respect the final recovery of Y.X ~ XW has a comparable performance against X XW* In other words, it may not be essential for the diagonal of low-rank approximate matrix W to be zero.
B.3 SVD OF W (LR-EDLAB-2)
Furthermore, if we consider the incquality
min renk(W)sk
||X XWI12
min rank(W)sk
| IW
WII
or tighter one
min SK
XW*
X
min (W)k
X 2 1 -
Both suggest if we simply perform SVD on W we can obtain an upper bound error between XW* and XW.
Simply, the other closed-form solution W (LR-EDLAE-2) is:
W UEVT
W V.
C TIME COMPLEXITY ANALYSIS
The running time of all linear models discussed in this paper is determined by one or more of the following factors: (i) Computation of matrix multiplication and inversion. The best known theoretical bound is 2.33.333) (Alman & Williams) 2021) but to the authors' knowledge the algorithm is not implemented in any mainstream libraries. (t) Computation k. leading singular vectors. The running
16

---

Under review as a conference paper at ICLR 2022
matrix. But recent trends believe that the constant terms in the big-O O notation matter so the asymptotic analysis becomes less fashionable (Stathopoulos & McCombs 2010 WW et al. 2017). (iii) Convergence rate of gradient-based algorithm. Except for special cases, when an objective not convex (e.g., when W is decomposed into W PQ), the convergence rate of an algorithm is remarkably difficult to analyze and often has substantial discrepancies with its practical performance (Bhojanapalli et al. 2016).
time is (ke)² for
We remark that all three factors exhibit significant gaps between theory and practice, i.c., the best theoretical algorithms are not implemented, constants in big-O matter, and accurate characterization of convergence rate is difficult. Therefore:
In theory, (i) the running time for full-rank Frobenius norm models (cases 5. EASE, 6. DLAE, and 7. EDLAE in Table is (n 2-33) because they involve merely matrix inversion and multiplication operations: (it) the running time for most low-rank models (cases 3, WLAE, 8. LRR, 10. LR-DLAE, 11. LR-EELAE-LLL and 12. LR-EDLAE-2 in Table D are 2:333 + kn?) because they require computation of & leading singular vectors cigenvectors; (iii) the nuclear-norm models require the multiplication with X E mR So the running time for cases 1 (Regularized PCA), 2 (MF dropout), and 4 (VLAE) are Okn + mak)), O(m² n + mn?), O(km² + knn) respectively; and (iv) The running time 4DMM-based model (case 9, EDLAE-ADMM Table 1 is (fn223373) where is the number of iteration needed to converge. We summarize the results in Table 4
In practice, solving low-rank SVD and computing matrix multiplication require similar time especially after carefully using HPC techniques. So our proposed algorithms LR-EDLAE-1 and LR-EDLAE-2 (Section 4 neither slower nor faster than existing ones that do not use gradient algorithms (e.g. full-rank EDLAE, etc.). The clock time for gradient-based (e.g. ADMM) algorithms is usually worse than that in theory because determination of hyper-parameters such as learning rate is usually guesswork. A rule of thumb is that LR-EDLAF-- and LR-EDLAE-2 are faster for small k and slower (than e.g.. ADMM- based methods) for large k.
Finally, we would like to address again on the advantage of having any closed-form solutions: they easy to implement and use, and can be quickly tested using any standard matrix computation platform without the specialized recommendation library. They are more robust to error and bug, and can serve as the competitive baseline for recommendation evaluation tasks.
D PROOFS
D.1 PROOF OF LEMMA I
Consider X E Rmxn, Suppose latent variables E R and generate data x E RR. The Variational
Linear Autoencoder (VLAE) is defined in the same way (Lucas et al. 2019b);
p( 2) N 14, <(> x) = N(V(2 - D)
(25)
For simplification, we μ = 0 in following context. And the ELBO of VLAE is known as:
Lg K [L(((2\=)]lx<3)) Eetsle KL(g(z[=)]lp(a)
log D) + V VV + tr k
Wo= E [ogsle)logg = 20 (Ir(WDW2) x V - (26)
n 2
log 2na²
Again, the (maximizing) ELBO can be written as:
17

---

Under review as a conference paper at ICLR 2022
La
log +
-k) DD +r()) - -2 log 2TO
12
2
(t((WDW") + +x
WVx -2x- 2x''WVx + x²xx)
(27)
2n
1V=l1
1
(I
p || WV 1(D.o)
20
where o(),o) = _ log DD - tr((( + - log 2To² x E R" and 2 E IR
For whole data, it is equivalent to minimize:
||x WVX + ml W WVD + V 3/+ o() = - - w ml /D 1
(28)
+ XV 1 (D.
where g(D,o) -0²m log DI (r(D) + k n log 2TO²)
D.2 PROOF OF PROPOSITION
Note that when o; S A(k-)) the new singular value shrinks to zero, and can be removed. Basically, for any A(1) 2 ... A(k). we can build the corresponding Tikhonov regularized instance by setting
of
of A()-)) iie.A 0, A(k-1) oi
(29)
o, + X
O,
Discussion of Proposition 1 Further, the same observation holds true for the regularization (Eq. 2 and the weighted-nuciess norm regularization in when the weights are in the non non-ascending order. This observation suggests a potentially limitation of the earlier regularization as they will always try to maintain the larger singular values: when a singular value is large, the shrinkage will be small. Such regularization has shown work well in the areas such as image processing (Gu et al. 2014). But has not been studied or confirmed if it will work for the recommendation. In Section 5 we report our experimental study which shows such regularization could be too restrictive for recommendation.
D.3 "CLEAR UP" EQ. 14
Since our objective for recommendation (not purely on recovering the low rank factors of the data), we treat the covariance matrix D as hyperparameters. Thus, the term g oD,,o) becomes constant, and let A 'V B 1/oWT,, A ovmD.
we consider D as an optimization parameter, then the optimal solution of VLAE is equivalent to that of PPCA TTppping & Bishop, 1999a). this case, D o² o2 where Σ² diag(a?) are the eigen-valuce of the covariance matrix X, and の² = カーズ 2 Further, the closed-form solutions of V (A) and W (B) are characterized. However, for recommendation, the matrix D can be considered a hyperparameter (to be tuned); in this case, the closed-fome solution is not studied yet.
is easy to see we can "clear up" Eq. (4) and obtain the following optimization problem
min ACRa* BRRRKKKBBREEE
I| XAB + |X ||ABI,
(30)
BEREX
in which decision variables are and B, and the hyperparameter is a diagonal matrix E R
D.4 INTUITION FOR PROVING PROPOSITION
Here, We explain the intuition for proving Appendix D.5 Proposition (see Appendix DD3 for the full analysis). Consider OPT1 and let W = PQ. Our goal is to characterize the behaviors of P and Q with the presence of the regularizers when W = PQ is known (fixed). Let the SVD of W be Uw Ew VT. Because regularizers || à Q1 and PA I|3 are symmetric, we could "guess" P Uw Σ and Q = -. VTT, where Ω is unitary matrix. Now we have
18

---

Under review as a conference paper at ICLR 2022
| || -
| WW + |1 WW =
Now the question of finding P and Q when W is known boils down finding a unitary matrix Q that minimizes ||A & | where diagonal matrices A and Ew given. Recall that X; Ais and let o; = (Ew)s: Note that X;Ss could be unsorted and, and that a, 's are sorted in descending order.
we restrict to be only a permutation matrix, then we aim to find a permutation т E [K] that minimizes Eisk Ar(1)0 Using rearrangement inequality (Yue 2020), we see that the minimal is achieved when An(1) I >x(2) S S (m())- In this case, we indeed have ming permutation || | 11 = ||EEw|las Iw.... where
Note that because PQ = Q for any unitary matrix Ω is always beneficial to use f to shuffle the rows and columns of P and Q so that the largest o, is mapped to the smallest A etc. This "degree of freedom" " from & also explains why ordering the values along 's diagonal is irrelevant.
Appendix D.5 shows that even when Ω is allowed to be any unitary matrix, the optimal one is still permutation matrix. This conclusion can be viewed as a matrix version of re-arrangement inequality.
D.5 PROOF OF PROPOSITION 2
By slightly abusing the notation, we shall let OPT1 (OPT2) be the value of the optimal solution for OPTI (OPT2). We need to show that OPT1 = OPT2. We need two directions.
OPT2 2 OPTI: Let W be an optimal solution for OPT2. Let the SVD of W be (V*) Recall that W* needs to satisfy the rank constraint rank(W"*) S A so U E R Ex E R kxb and V* E Ra*k, Let π be a permutation on [k] such that Am(1) I Xx(2) S I Am(e) Let also f be the corresponding permutation matrix. Specifically, Ω E {0, 1xx x and there is exactly one entry in each row of Ω is 1:
Qi = {
1
otherwise.
For example, consider a case in which A1 > Ae > correspondingly,
>
d
Then we set π = (k: 1, 1.... 1). and
0
0
1 0
0
0
Next, let P U><E") and Q == ( We have W PQ and f(W*) f(PQ).
In addition,
|| Q |P
=2 2 Am100 2/ 2/
where is the i-th largest singular value of W In other words, we have found (P, Q) pair such that
S(PQ) (12 |PA+ /(W*) + +2||W* I1..- = OPT2,
which shows that OPT1 - OPT2.
OPT2 < OPTL P* and Q* be optimal solution for OPT1. Let the singular values of P be 01 (P*) 2 (P') and those of Q" be o (i(")) 2 o2((") 2 ... ... ox((")) Let also of 2 2 of be the singular values of P*Q".
| |& expressed in terms of os's. In fact, shall We shall find lower bound of ||A + show that
| I
12 2 2|
(31)
19

---

Under review as a conference paper at ICLR 2022
One can see that if Eq. 31 true, we have
OPT2 _(P)Q)) + 2 P*Q- S(P*Q)) 11 |1 OPTI.
Thus, remains to prove Eq.
31 Let A01 2 x22 2 ... 2 A(a) be a sorted sequence of X is.
A(e) (T) 1) x2)) ..... A(1) (1())
First, we show that 1A+1 2 Σi= (0+++11 (P? and Q 2 Eis xo=
We need the following Lemma (see e.g., Theorem 2 in Yue 2020
Lemma 4. Let A and B be two positive definite matrices in R
Then it holds that
S AB²))
(32)
Let the SVD of pa be Up- Ep- ViT. and that of Q" be U@ Eq- Vi... We have
|PA* =
1 1Up | = PEp- VT. ||+ = tr(E VT.Vp-- Ep.).
(33)
We now apply Lemma by setting A = VT- AVp. and B Ep.. and obtain that
k
| 2
Σ X x (PP)))
(34)
We may similarly prove that Q" Σ Di=l 1(1=++1) x07(0)) Therefore,
P
A x (d)(P))
(35)
provides a lower bound of ||A 11 + P [3 in terms of (P() and (Q("). We next aim to express the lower bound in terms of o3¹¹ 's (singular values of P'Q") directly.
The following program gives a lower bound for Q + | A
min || 1 + A
(36)
subject
W p
(W = of for i < k.
Write the SVD of W be Uw V.W. Also, let P = U p* and Q Q'V.. Noting that the columns in P* are in the column space of W and the rows in Q" are in the row space of W. we
have (i) (P() = (P) and (Q")) = (Q) for < k, and (ii) | Q" 112- + | =
||A Q + |P I|
Therefore, Eq. (36) can be equivalently written as
min ||A* + 1|
(37)
subject to
Ew = PQ
(Ew),, = for i < k.
Now PQ is positive definite. Using similar technique developed in (aao et al. 2020) (Theorem 1). can see that 5> QT. See also Lemma 5 This implies that م - Σ Ω for some unitary matrix
Q and (P*)) = o; (P) = o:((²) (²) Vo for S Together with Eq. (35) we have
\ x (P?) = Σ A x x = 2 Q' ||A P A |/2 2 2 Σ
k
20

---

Under review as a conference paper at ICLR 2022
D.6 PROOF OF COROLLARY
We first find an optimal solution for Eq. 9 Let the SVD of X be X = UxIxVX. where Ux E Rmxx, Ex E Rex*, and Vx R Ruxn Let Ux an arbitrary basis for the subspace that orthogonal X's column space so Ux E Rmx(m=n)) and [Ux, Ux] form a basis for RT We have
|| PQI1 + |P 13 + Q1
-
U UX
XVx
PQVX
| +
1(
U o 0x
PA
+ I
UX
Let P
P and Q QVx Then objective becomes
0x
(
Σx ((--))xn )
min P,Q
PQ + +1 + Q1
(38)
Vx
Let W- PQ and the singular values of W be oj 2 02 2 ... 2 of. Let also &
((m-))xn
Recall also that or is the i-th largest singular value of X. We next show that
I(
Σx ) PQ (5x 0
= -11
Σ (1-00)) 0;)²
Σ of
k=
Note first that
=
| 2(E,
(39)
Next, we have (Zheng et 2018)):
|EE W)| = |tr(EWT)
|t (t<(Ennw)) = Σ o.o
Therefore, (Σ, W) is maximized when
o if= k Otherwise.
Wa,
When we plug in this optimized W to Eq. 39 we get
E WIP 2 Σ
(a: 0;)²
+ Σ of
b=
Next, from Proposition 2 we have
1
2
Σ
Am-ittooo
Therefore, we can find a lower bound for Eq. terms of a
C(oi....,of)) = >(a, (a; - -,,-) +2 1
Σ A A4-11100 +
Σ of 2 ... ......00 of 2 0). (40) #=++1
We next find a minimal value of L (by treating of 's as decision variables). This will give us a lower bound (and is independent of o;) our optimization problem. We then show that this lower bound can be achieved by carefully constructing W (as well as P and Q). This means such W is optimal.
21

---

Under review as a conference paper at ICLR 2022
Specifically, we need to find optimal solution for the following program:
minimize subject to:
_(oj......o
(41)
of 2
o
S 02 S ... S of
(Ordering constraint)
We shall first find an optimal solution for
minimize ji Th subject to: of 20
,(,
(42)
Note here, the ordering constraint removed so the optimal value for Eq. (42 should be no more than that for Eq. 44I). We shall see that the optimal solution for Eq. (41) also satisfies the ordering constraint so indeed optimal solutions for Eq. (41) and Eq. (42) are same.
The problem Eq.
42 boils down to finding
min (a; 07)² Σ A1-111)77-
oj
We note that of's do not interact with each other
optimize each of's independently. We get
of = (a; *(R-++1))*
We can check that of 2 ... 2 of. Therefore, the optimal value for Eq. 41 is
&
(o. -a, (o +2 Au- 1=1
(a-=))(a=-u--111 A(-i+ti)
of
==1
k=++1
This is also lower bound for Eq. 9 One check that when set P and Q
p" Undiag
V (ai )(x)))), ..... V(on A(1))+
(43)
Q- S2T diag( (01 )(x))),,... (oo -
the lower bound is achieved Eq. and right singular vectors of X.
443 gives optimal solution. Here, Un and V, are leading left
Now move to analyze Eq. 10 Our goal is reduce Eq. 110 Eq. 99
Let
P XAA
Q Q= A
Then Eq. 10 becomes
minimize
||X PQII + PI I
(44)
subject to
P = XAA (Constraint P)
Q A
(Constraint Q)
Here, X and A are given, whereas P. Q, A, and B are decision variables. The (Constraint says that each column P needs to be in a column space of X (it is necessary and sufficient condition for A to exist). The (Constraint Q) simply says and B are linearly related and does not have tangible impact to the optimization problem.
But we note that when we put aside the constraints, an optimal (P, Q) is specified by Eq. 43 The columns the optimal indeed in the column space of X. So (P, Q) also an optimal solution for Eq. We may find the corresponding A and B:
4' Xip and B = A-=10-
22

---

Under review as a conference paper at ICLR 2022
D.7 SYMMETRIC LEMMA
Lemma 5. Let P. P.Q- E R be full rank, A be diagonal mairix, and Ew be diagonal matrix so that (Ew)e, = of where of are sorted in descending order. Consider the optimization problem:
min | ||PA*11
(45)
subject
Ew PQ
(Ew)ess of for i S k.
There is an optimal solution such that P = QT
Proof. Let P = PAA and Q =-= The problem Eq. 45 is equivalent to
min ||QQ1 + ||
(46)
subject
Ew PQ
(2w)),s = o for i < k.
Let the SVD of Q be V Q-1 V We can also see that P Ev
Therefore, the objective term becomes
|AU 1 UU
| EEli VE
Let us consider the stationary points Up and Va when Eg is fixed. We that they need be permutation matrices minimize both terms in the objective (using the rearrangement inequality again). Therefore, that Q - A ie., each row (column) of Q has exactly non-zero entry. We may similarly show that each row (column) of P has exactly one non-ze zero entry. In addition, the locations of non-zero entries of P and QT are identical because PQ is a diagonal matrix. We may thus write
see Q En Eg Eg for two permutation matrices Σ and Σg. This implies
P= Ep
Q = E (())
T (1))
where (Ep)., = (P) and )., o+()) (2), where is permutation on [k]. The set of Thus, we can see that there exists
(possibly unsorted) singular values for PQ thus is o, permutation स such that
|| + | Σ (o?(P"))at) + + ((()))
igk
20, (P* (2))))()()))))
One can see that we can set P QT to make all inequality becomes equality so there is an optimal solution such that p QT.
EXPERIMENTAL DETAILS
E.1 ANONYMOUS CODE
https://ant httpss///nnnmmous... 4open. sci wwtpeecce//rc..eeee/e./ 2022- 2 Secoyyyoou---------o Demo Code-ooooooooooo B9FF/
README md
23

---

Under review as a conference paper at ICLR 2022
E.2 DLAE AND HYPERPARAMETER TUNING
This section presents the hyperparameter tuning process on the validation data over three (ML-20M, Netflix, MSD) datasets for the full-rank DLAE formula (case 6 in Table which introduced by Steck 2020) yet not investigated:
min |X - XWI 11A W
A P
- dMat(diag(("
(x x + A) -)
In practical, l2 regularization (hyperparameter À) is also imposed:
=
The Tables to 7 show the results of nDG 100 over three datasets respectively. And the optimal parameters are highlighted.
Table 5: ml-20m, DLAE full rank, parameter tuning validation dataset by n nDCG@100
800
900
1000
1100
1200
1300
0.1
0.42024
0.42063
0.42073
0.42102
0.42131
0.4212
0.2
0.43132
0.43139
0.43154
0.4314
0.43147
0.43136
P
0.3
0.43203
0.43211
0.43214
0.43206
0.43203
0,43196
0.43001
0.43001
0.42995
0.42996
0.42984
0,42978
0.5
0.42754
0.42745
0.42729
0.42718
0.42715
0.42704
Table netflix, DLAE full rank, parameter tuning on validation dataset by nDCG@10 100
800
900
1000
1100
1200
1300
1400
0.2
0.3904
0.3904
0.39027
0.39024
0.3902
0.3903
0.39018
0.25
0.39247
0.39252
0.39248
0.39249
0.3925
0.3925
0.39256
0.39359
0.39359
0.39366
0.39358
0.39362
0.39368
0.39369
0.35
0,39402
0,39403
0,394
0.39405
0.39399
0.39403
0.39397
0.4
0.39399
0.39393
0.39395
0.39393
0.39389
0.39388
0.39387
0.45
0.39346
0.3935
0,39343
0.39344
0.39338
0.3933
0.39329
0.5
0.39249
0.39241
0.39247
0.39241
0.39242
0.3923
0.39224
E.3
MATRIX FACTORIZATION WITH DROPOUT AND HYPERPARAMETER TUNING
Cavazza 2018) show that optimization with dropout (allowing rank be optimized) is equivalent to solving a matrix approximation problem with nuclear norm:
1
min |X P.Q.a
PQ
P&
|
P
(47)
1 1-
min ||X - 1 y
|
Table 7: msd, DLAE full rank, parameter tuning on validation dataset by nDCG@100
10
20
30
60
0.3
0.38514
0.38515
0.38517
0.38505
0.38492
0.38474
0.4
0.38596
0.38599
0.38602
0.386
0.38597
0.38592
p
0.5
0.38556
0.38555
0.38553
0.38557
0.38553
0.38549
0.6
0.38382
0.3838
0.38381
0.38374
0.38373
0.38366
24

---

Under review as a conference paper at ICLR 2022
and the solution is given by:
X UEVT
Y P P Q"
U U. Up((E) Vr
(a max(o 14 0)
1 -
Σ (x(
= p (1 p)d
i=1
where d denotes the largest integer such that:
xx(X)
1-p P p+ (1 p)d
Σ (X)
Hence, there is only one parameter p to tuning. We present the tuning process on the validation set below, see Tables 8 to 10 Optimal parameter as well as induced rank is highlighted.
Table 8: ml-20m, matrix factorization with dropout, hyper parameter tuning by nDCG@100 on validation dataset and its induced rank
p
0.9
0.99
0.995
0.996
0.997
induced rank
200
385
467
nDCG@ 100
0.29723
0.39369
0.40045
0.40046
0.39925
Table 9: netflix, matrix factorization with dropout, hyper parameter tuning by nDCG@100 on validation dataset and its induced rank
0.9
0.99
0.996
0.997
0.998
induced rank
524
653
883
nDCG@ 100
0.26026
0.35462
0.36453
0,36495
0,36406
Table 10: msd, matrix factorization with dropout, hyper parameter tuning by nDCG@100 on validation dataset and its induced rank
0.99
0.999
0.9995
0.9999
0.99995
induced rank d
249
2054
3783
11380
19308
nDCG@ 0.18986
0.28532
0.307
0.32634
0.30995
E.4 RESOURCES
Our code are mainly implemented in Numpy 1.19, Pytorch 1.7.1 on CUDA 11.0. Our experiments are performed on nodes with two sockets, each containing 24-core Intel(R) Xeon(R) Platinum 8268 CPU @ 2.90GHz and 4 GeForce RTX 3090 24GB memory GPU.
25


Reviews:
[{"review_id": "p_BafG4uGNu", "reviewer": "Reviewer_Uxog", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well structured and easy to follow. The analyses from the perspective of regularization terms are novel. The results in Table 3 are very interesting. Although it is unknown why not ordering the singular values will lead to significant performance drop, the results can help confirm another limitation of matrix factorization-based methods.\n\nMy main concerns about this paper are as follows:\n1)\tThis paper may help researchers to understand linear recommendation methods from a new perspective, but the theoretical contributions are limited. In addition, the proposed methods are without statistically significant improvements compared to baseline methods.\n2)\tThe authors claimed that the proposed method can have closed form solutions. But in both proposed methods, SVD is required to obtain the so-called closed form solution. I am not sure if this kind of solutions are “closed form” or not.\n3)\tThere is no efficiency analysis about the proposed method. Although the proposed methods are low-rank not full-rank, the required ranks are actually very high, e.g., 2000-12000 in Figure 1. This is rarely seen in practice and might cause storage or computation issue in large datasets.\n4)\tIt will be interesting to see more insights about why ordering of weights on matrix factorization and other regularizations are so important in recommendation models.", "summary_of_the_paper": "This paper analyzed the linear models for recommendation from their regularization terms, more specifically, via nuclear norm and Frobenius norm. Based on the analyzes, this paper proposed two alternatives for linear recommendation models with closed form solutions. Experiments on three large scale datasets showed that the proposed alternatives are comparable to the state-of-the-art baseline methods.", "summary_of_the_review": "Overall, I feel that this paper makes incremental contribution by connecting existing recommendation methods both theoretically and empirically.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "dxs-n-v5M5C", "reviewer": "Reviewer_bVYo", "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": "1. My main concern about this work is that the performance of the proposed methods is not better than SOTA ones like DLAE and EDLAE. Also, the authors did not analyze or compare the computational complexity. I do not see the value of proposing a method with similar performance and unclear complexity. Specifically, the two proposed methods both require SVD approximation, which has a cubic complexity and is quite expensive. It is nontrivial to analyze the complexity of the proposed two methods and other algorithms.\n\n2. The authors claim that ‘while the syntax of this problem resembles matrix completion (MC), recommendation systems and MC have different evaluation criteria so MC’s results are not directly applicable here.’ It is better and helpful to make it clear what the evaluation criteria difference is if the authors want to discuss the relations between recommender and MC. Besides, if two problems do not share the same evaluation criteria but have the same or similar objective function to be optimized, they are still quite correlated.\n\n3. Section 3 has the same name as Section 2.1, which is confusing. The overall structure should be reorganized.\n\n4. In Section Matrix Factorization via dropouts,  the relation of mu and X and lambda should be better explained.\n\nMinor:\n1. choise—> choice\n2. Please unify ‘closed form’ and ‘’close-form’\n3. which make the —> which makes the \nPlease polish the English writing and correct all grammar errors.", "summary_of_the_paper": "The authors studied some linear recommendation algorithms and their relations and also proposed two new methods to benefit from both\nnuclear-norm and Frobenius-norm regularizations. The two new methods have similar performance as compared methods.", "summary_of_the_review": "Overall, the authors have done extensive works to analyze the SOTA linear recommendation models but some critical analysis like the computational complexity is missing. Also, the proposed methods do not perform better than SOTA ones.", "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": "QhLOmPXEN-N", "reviewer": "Reviewer_nwQT", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Note to ICLR 2022 (not the authors): next time, it would be nice to include row number in the submission template to ease the reviewing process!\n\n== STRENGTHS == \n\nThe paper is rather well written with several emphases on the different contributions of the authors. There are solid theoretical foundations accompanied by empirical evidences on three real datasets.\nThe experiments include 1) recommendation performance (NDCG) of the several considered approaches, 2) influence of low rank value on NDCG and 3) impact of weight ordering on recommendation performance.\nMoreover, the authors plan to share the code which is highly appreciable in order to provide reproducible results.\n\n== WEAKNESSES (OR SUGGESTIONS) ==\n\nThere is a certain amount of minor typos (see some below) but also a lack of some term definitions (because of late copy-paste in Appendix to observe the page limitation rule probably). \nTable 3 is actually very useful for the understanding, I would not put it in Appendix.\n\nSome things which could be clarified:\n- Reference to deep learning methods is done for state-of-the-approaches. In the paper, it seems it is more about shallow networks (max 2 layers) that are discussed.\n- p.3, A3, Eq. 2: W1 and W2 are not defined. I guess they denote the Encoder and the Decoder network.\n- p.3, A4, eq.3: W and V not defined, same as above\n- Eq. 4: N is not defined\n- p.4, A6: M not defined.\n- Eq. 13, p.7: operation dMat not defined (too late to put it in p.2 of supplementary material), same in eq. for W* (which should be indexed)\n\nAlso to help the reader, it would be nice to start Sections 2 and 3 with a summary of what the section plans to achieve/demonstrate. In particular, this is quite difficult in Section 3 to follow the objective. \nFor instance, a sentence such as \"Prop. 2 also leads to the following Corollary.\" does not help to understand the implication of such result. \n\nUnless I missed it, differences of implication between LR-EDLAE-1 and LR-EDLAE-2 (the proposed methods) are not enough carefully detailed.\n\nIn Table 1, it would be clearer for the reader to identify the best methods for instance, 1) by putting in bold the best obtained results and 2) by underlying the 2nd best result. \nTable 1 refers to Table 3 for more details: I think this is a mistake because it does not let the paper \"self-contained\".\n\nAm I missing something or Mult-VAE/DAE are used as baselines during experiments but are not discussed before (contrarily to the other approaches)? Why?\n\nSome typos :\n- in abstract : « (surprisnig) »\n- abstract: missing \"-\" for low-rank and closed form\n- p.1 in introduction: \"the linear autoencoders [...] which encompasses\"\n- missing upper case : p.2, 2nd paragraph « . we generalize the »\n- p.2 missing \"-\", \"These models produce closed form full-rank estimators\"; \"However, no closed form solutions\"; \"ADMM based solutions\"; \"the full rank W\"\n- end of p.2 : « The weighted unclear norm »\n- beginning of p. 3 : missing lower case « Therefore, Nuclear-norm regularizers »\n- inconsistency in convention naming for equations : eq. Or Eq. / eq (1) or eq. 1 ; 5 times in p. 3, same for Table or table, Proposition or Prop.\n- p.3, A2 : « This approach useS »\n- p.3, A4 : « probabolistic »\n- p.4, first row: choose between \"hyperparameter\" (p.3 after Lemma 1) and \"hyper-parameter\" (p. 4)\n- p.4, (ii): \"choices of p [...] produces\" ; \"all entries in X is\"\n- p.4, (ii): inconsistency in naming convention: nuclear-norm-based and nuclear-norm based in the same sentence, sometimes it is nuclear norm (check everywhere in the paper)\n- Before eq.7: \"Its a closed-form solution is.\"\n- choose between \"Frobenius-norm regularizer\" p.4,5 and \"Frobenius norm regularizers\" p.5\n- before Sec.3, p.5: \"two low-rank Frobenius-norm-based modelS\"\n- p.8 in Table 1: \"Frobinius\"\n- eq.8, missing \"|\" in 3rd norm, extra space to remoce: \"equivalently ,\"\n- missing \"-\" for closed form solutions after Proposition  2 p.5, in Section 4 p.7, in Section 5 p.7, in Q1 p.8, Q.2 in p.9 twice, Q.3, in conclusion ; check for low-rank everywhere also\n- p.5 choose between \"rearrangement\" and \"re-arrangement\"\n- Corollary 1, p.6: Missing Eq. before (9)\n- Section 4, p.7: missing \"-\" for state-of-the-art\n- Section 4, p.7: after ADMM: \\cite instead of \\citep, same after closed-form and EDLAE\n- Table 1: refer TO\n- p.8 in Q1: (eq. (11))\n- p8, Q1: \"one of the most popular implicit matrix factorization algorithmS\"\n- Q2: \"most of them reaches\"\n- Q2, missing \"-\" in EDLAE based approaches\n- Q2, p.9: ADMM method performS slightly better ; none-the-less\n- p.9: \"all the models add either a nuclear-norm-based [...] or a Frobenius-norm based regularizer.\" ; check also the abstract\n- p.9 \"The Frobenius-norm models are more express\" \n- Supplementary: section A autoencoder vs auto-encoder \n-Supp, section A: \\cite instead of \\citep for 2nd paragraph\n\n\n\n\n", "summary_of_the_paper": "This paper unifies under one theoretical framework the different state-of-the-art regularization approaches for linear collaborative-filtering recommendation models which leverage the user-item interaction data matrix. \n\nThe authors classify these algorithms among two families: 1) the nuclear-norm-based regularizers and 2) the Frobenius-norm-based regularizers. Both have their advantages and drawbacks. \nWhile nuclear-norm-based regularizer's solutions are low-rank (and therefore more scalable) and have a closed form, their performance is limited. \nOn the other hand, Frobenius-norm-based regularizer's solutions are full-rank or difficult to train.\nHence, focusing on generalizing Frobenius-norm-based regularizers, the authors bridge the gap between the two families by providing two new low-rank, closed-forms solutions - LR-EDLAE-1 and LR-EDLAE-2 - peforming similarly to full-rank EASE and EDLAE state-of-the-art models. \n\nTo that purpose, the authors start from the analysis work from Jin et al. (2021) about the relationship between Matrix Factorization approaches and linear autoencoders-based ones. \nBesides EASE and EDLAE algorithms, they also analyze VLAE, DLAE and LRR. They show that VLAE solves a weighted nuclear-norm regularixation problem.\nThey also generalize the result on the equivalence between dropout technique and the adding of a squared nuclear-norm regularizer to show that solution structures for ||W||^p_* are similar for all p>= 1.", "summary_of_the_review": "This paper represents an extensive work on both theoretical and experimental sides. \nHowever, the number of typos and missing notation definitions show that the manuscript has not been re-read enough to check that the fact of having moved parts from the general paper to appendix does not hurt actually the linear reading. \nI advise the authors to do another reading pass to fix the typos and problems of definitions listed above. \nI vote for a weak reject.\n\n======  AFTER REBUTTAL ======\nI read carefully the other reviews and author's responses. First of all, thank you very much to the authors for their hard work during the rebuttal period and the significative changes brought to the structure of the paper which is improving its quality a lot. \nHowever, I tend to share the concerns of some reviewers regarding the complexity of the algorithm which is actually rather similar to the state-of-the-art baselines. Hence if the designed methods bring neither substantive improvements in terms of accuracy nor in terms of complexity, the proposed theoretical framework does not seem finally enough for an acceptance. I keep my grade \"marginally below the acceptance threshold\".", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "1Ei5aNBnE41", "reviewer": "Reviewer_7nvQ", "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, I think the flow of the paper could be improved. Many things are stated/claimed in Section 2, and then the justified several pages later. Essentially, this means that the reader has to memorize many things until they get explained later. For instance, in section 2.1 on nuclear-norm regularization, various Frobenius-norm regularizations are given, and the connection to the nuclear-norm is provided 2 pages later in proposition 2. Even more confusing in section 2.1 is that A3 / Eq 2 appears to be different from A1, A2, and A4  in that L_2 norm regularization of ||W_1||^2 is used in Eq 2, i.e., without the data matrix X. In contrast, A1, A2, and A4 apply L_2 norm regularization essentially to ||X * W_1||^2, or if P= X * W_1 then ||X * W_1||^2. This is eventually justified 3 pages later in corollary 1. I wonder if one could simply swap the ordering of sections 2 and 3 to improve the flow. At the moment, I feel that the reader has to read the paper twice, as section 2.1 only makes sense after reading section 3.\n\nSection 2:\n\nThe authors categorize the various linear models according to the applied regularization (nuclear-norm vs Frobenius). To this end, they also need weighted regularization, and they generalize recent results (which seems somewhat straight forward, though).\n\nIt is not clear to me why A3 / Eq 2 is called denoising linear autoencoder, given that denoising in linear models is equivalent to applying an L_2 norm regularization of the form ||W_1 * W2||^2 (i.e. product), and not ||W_1||^2+||W_2||^2 (i.e., sum) (dropping the L_2 parameters here for concise notation). A second version of a denoising linear autoencoder appears in A6, where the correct L_2 regularization induced by denoising is used. Maybe this can be described more clearly.\n\nI wonder if  the claim that Eq 5 is equivalent to MF is actually trivial, as one can simply identify P:= XA and Q:=B to connect both formulations. The equations below Eq 11 in Jin's paper already show that MF and autoencoders are equivalent models, i.e., P*Q in MF can be equivalently rewritten as an autoencoder taking the form X*A*B--hence the only difference and the key difference is the L_2 norm regularization ||P||^2 = ||XA||^2 (in MF) vs ||A||^2 (in the autoencoder), i.e., X is included vs excluded in the L_2 norm regularization. Hence, it is obvious that one could use the regularization  ||XA||^2 in the autoencoder, which would obviously be equivalent to MF. Apart from that, it is not clear to me why the weighting is introduced, as it  does not seem to add anything to the conceptual insights gained (but I can believe that it will lead to better results in practice/experiments)\n\nIn A7 (EDLAE), the statement is incorrect that the constraint diag(W)=0 is applied to low-rank EDLAE models. Instead, the diagonal is subtracted during training, i.e., || X- X * {W-diagMat(diag(W)) } ||^2. In other words, while W is not required to have a 0 diagonal, the matrix {W-diagMat(diag(W)) } obviously has a zero diagonal. If W is low rank, then the diagonal is generally not 0, as the diagonal and off-diagonal elements are not independent of each other (due to the low-rank constraint). Only when W is full-rank, all entries in W become independent of each other, so that one can afford the freedom to constrain the diagonal to 0. \n\nSection 3:\n\nThis section provides the connection between nuclear norm and Frobenius norm regularization. The key contribution seems to be that existing results on the nuclear norm are generalized to the *weighted* nuclear norm.\n\nSection 4:\n\nBelow Eq 13, it says that diag(W)=0 in EDLAE. This is only true for the full-rank EDLAE model, while it is not true for low-rank EDLAE, which is considered here. See comment above.\n\nThis section provides 2 ways of approximating the full-rank EDLAE by a low-rank model, which somewhat seems to fall out of the blue sky, i.e., it seems unrelated to the previous parts of the paper--including the section 2.2 on Frobenius norm regularization applied to various models. While it is clearly outlined how the 2 methods work, it is not discussed *why* they can be expected to work / result in accurate approximations. The reason is that the diagonal is ignored / assumed away in both proposed methods, even though the diagonal is essential in the original EDLAE model. It would be great if the authors could provide some theoretical / intuitive justification why this approximation is valid/accurate.  The experiments show that this approach indeed works surprisingly well.\n\nIt is not clear to me what it means that the best of both  nuclear norm and Frobenius norm regularization are obtained by these 2 methods. In this generality, I think this is not true.  For instance, Jin et al. 2021 derived a closed form solution of A6, which uses Frobenious norm regularization and is a low-rank model. Hence, obtaining a closed-form solution is not a property of the nuclear-norm regularization, as suggested/implied by the authors. The authors propose 2 methods for a closed form approximation to EDLAE--which uses Frobenius norm regularization--it is hence not clear to me why there is any need to make a connection to the  nuclear norm regularization in this section. The only remaining indirect justification could be that nuclear-norm regularization induces a low-rank model, but conversely, I am not sure that a low-rank model induces the need for nuclear-norm regularization. Moreover, the full-rank EDLAE model is usually  more accurate than the low-rank EDLAE--from this perspective there may not be any need for  nuclear-norm regularization or the low-rank version of EDLAE. \n\nSection 5:\n\nThe experiments show that the 2 proposed methods achieve high accuracy.\n\nAs a suggestion, Table 1 might be easier to read if it were explicitly indicated which models are full-rank, and which are low-rank (and which rank k).\n\nAdditional points:\n\n- Given that this paper makes several contributions that are not all connected to each other, I wonder if it would make sense to split this paper up, as it would allow for more space to discuss the various contributions in more depth.\n\n- The paper contains many typos and grammatical mistakes. Also note that 'non-descending' = 'ascending'.\n\n- below Eq 8, are Q' and P' swapped? I.e., I would have expected P' = XA^*, not Q'XA^*.\n\n- Lambda in A3 and A6 seem to be different matrices--this should be reflected in the notation.\n\n++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\nUpdate based on authors' responses:\nI very much appreciate the detailed responses and improvements in the paper. As I expected that many of the improvements can be made easily, and factored them into the score (which is the highest among all the reviews), I would like to maintain my current score.\nAs an aside, I am not really convinced by the arguments for dropping the zero diagonal constraint for the low-rank model, as it is unclear to me how tight the bounds are, and hence it is unclear if optimizing the bound  really yields similar results as optimizing the original objective (with the zero diagonal). Moreover, when dropping the zero-diagonal constraint, the bound seems to be a lower (rather than an upper) one, which means that a lower bound is minimized.", "summary_of_the_paper": "This paper categorizes various linear models based on the applied regularization: nuclear norm vs Frobenius norm regularization. It is claimed that this categorization is key to understanding the prediction accuracies of the various linear model-classes. The paper also makes connections between nuclear norm regularization and Frobenius-norm regularization, and also discusses L_p norm regularization of the singular values. The paper also describes 2 methods that yield a closed-form solution of a low-rank model with Frobenius norm regularization: while it is not motivated/explained why these methods should work from a conceptual/theoretical perspective, the experiments show that they indeed work surprisingly well.\n", "summary_of_the_review": "\npostive points:\n\n- results on unweighted matrix norms are generalized to the *weighted* nuclear norm, connecting the latter to the weighted Frobenius norm.\n- various models are categorized based on the used regularization (nuclear norm vs Frobenius norm), and it is shown that this explains the differences in prediction accuracy to a large degree.\n- the proposed 2 methods / approximations work well in the experiments (but are not motivated/justified conceptually).\n\nnegative points:\n\n- the 2 methods/approximations in section 4 are not motivated / justified theoretically (but they work well in the experiments).\n- the writing and the flow of the paper could be improved considerably.\n", "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": {}}]

Author rebuttal:

Meta-review: The paper presents a new perspective on recommendation systems, categorizing them as linear predictors where the main difference between the various methods is the regularizer. The authors then propose an objective function that aims at optimizing the Frobenius norm while maintaining a low-rank solution, and present algorithm that have closed-form solutions based on the SVD.

The reviewers noted the novelty of the framework, but the overall assessment after the discussion was that the theoretical contribution was limited. The algorithm proposed by the authors does not provide any improvement on standard criteria (performance, computational complexity), which makes the algorithmic/experimental contribution limited as well.
Decision: Reject