Online Low Rank Matrix Completion
Authors: Soumyabrata Pal
Prateek Jain
Venue: ICLR 2023 poster (2023)
Keywords: Matrix Completion
Online Learning
Recommendation System

Abstract:   We study the problem of online low-rank matrix completion with $\mathsf{M}$ users, $\mathsf{N}$ items and $\mathsf{T}$ rounds. In each round, the algorithm recommends one item per user, for which it gets a (noisy) reward sampled from a low-rank user-item preference matrix. The goal is to design a method with sub-linear regret (in $\mathsf{T}$) and nearly optimal dependence on $\mathsf{M}$ and $\mathsf{N}$. The problem can be easily mapped to the standard multi-armed bandit problem where each item is an independent arm, but that leads to poor regret as the correlation between arms and users is not exploited. On the other hand, exploiting the low-rank structure of reward matrix is challenging due to non-convexity of the low-rank manifold. We first demonstrate that the low-rank structure can be exploited  using a simple  explore-then-commit (ETC) approach that ensures a regret of $O(\mathsf{polylog} (\mathsf{M}+\mathsf{N}) \mathsf{T}^{2/3})$. That is, roughly only $\mathsf{polylog} (\mathsf{M}+\mathsf{N})$ item recommendations are required per user to get a non-trivial solution. We then improve our result for the  rank-$1$ setting which in itself is quite challenging and encapsulates some of the key issues. Here, we propose OCTAL (Online Collaborative filTering using iterAtive user cLustering) that guarantees nearly optimal regret of $O(\mathsf{polylog} (\mathsf{M}+\mathsf{N}) \mathsf{T}^{1/2})$. OCTAL is based on a novel technique of clustering users that allows iterative elimination of items and leads to a nearly optimal minimax rate. 

Published as conference paper at ICLR 2023
ONLINE Low RANK MATRIX COMPLETION
Prateek Jain Google Research Bangalore, India prajainegoogle. com
Soumyabrata Pal Google Research Bangalore, India
soumyabrata@googge.cco
ABSTRACT
We study the prohlem ontine low-rank matrix completion with users, items and T rounds. In each round, the algorithm recommends one item per user, for which it gets a (noisy) reward sampled from a low low-rank user-item preference matrix. The goal is to design a method with sub-linear regret (in T) and nearly optimal dependence on M and N. The problem can be easily mapped to the standard multi-armed bandit problem where each item is an independent arm, but that leads to poor regret as the correlation between arms and users is not exploited. On the other hand, exploiting the low-rank structure of reward matrix is challenging due to non-convexity of the low-rank manifold. We first demonstrate that the low-rank structure can be exploited using simple explore-thn--oomii (ETC) approach that ensures regret (ppoyycgg(M M + N)T2/3). That roughly only polylog(M N) item recommendations are required per user to get a non-trivial solution. We then improve our result for the rank-1 setting which in itself is quite challenging and encapsulates some of the key issues. Here, we propose OCTAL (Oaline Collaborative filTering using iterAtive user cLustering) that guarantees nearly optimal regret of (polyyog(M + /9). OCTAI is based on novel technique of clustering users that allows iterative elimination of items and leads to ncarly optimal minimax rate.
1 INTRODUCTION
Collaborative filtcring hased on low-rank matrix compliciionfacctoriaaiio techniques are the corner- stone of most modern recommendation systems (Koren, 2008). Such systems model the underlying user-item affinity matrix as a low-rank matrix, use the acquired user-item recommendation data to estimate the low-rank matrix and subsequently, use the matrix estimate to recommend items for cach user. Several existing works study this offline sotting (Candès & Recht 2009 Deshpande & Montanari 2012) Jain et all 2013 Chen et al. 2019 Abbe et al. (2020). However, typical recom- mendation systems are naturally online and interactive they recommend items to users and need to adapt quickly based on users' feedback. The goal of such systems is to quickly identify each user's ss preferred set of items, so it is necessary to identify the best items for each user instead of estimating the entire uffinity matrix. Morcover, items/users routinely added to the system, so it should be able to quickly adapt to new items/users by using only a small amount of recommendation feedback.
In this work. we study this problem of the online recommendation system. In particular, we study the online version of low-rank matrix completion with the goal of identifying top few items for each user using say only logarithmic many exploratory recommendation rounds for cach user. In each round (out of T rounds) we predict one item (out of N items) for each user (out of M users) and obtain feedback/reward for each of the predictions- e.g. did the users view the recommended movie. The goal is to design a method that has asymptotically similar reward to method that can pick best items for each user. As mentioned earlier, we are specifically interested in the setting where T < N i.. the number of recommendation feedback rounds is much smaller than the total number of items.
Moreover, we assume that the expected reward matrix is low-rank. That is, if R is the reward obtained in the 4h round for predicting item-j for user-i, then ER! (1) P.j. where P c RB is low-rank matrix. A similar low rank reward matrix setting has been studied in online multi- dimensional learning problems (Katariya et al. 701 Kveton al. [017 Trinh et al. 2020). But in

---

Published as conference paper at ICLR 2023
these problems, the goal is to find the matrix entry with the highest reward. Instead, our goal is to recommend gond items to all users which is significantly harder challenge. A trivial approach is to ignore the underlying low-rank structure and solve the problem using standard multi-arm bandit methods. That is, model each (user, item) pair almost all the items for each user, which is also reflected in the regret bound (averaged over users) of O(VNT) (Remark D). That is, as expected. the regret bound is vacuous when the number of recommendation rounds T < N.
arm. Naturally, that would imply exploration of
In contrast, most of the existing online learning techniques that leverage structure amongst arms assume a parametric form for the reward function and require the reward function be convex in the parameters Shalev-Shwartz
al.] [00 Bubeck 2011). Thus, due the non-convexity of the manifold of low-rank matrices, such techniques do not apply in our case. While there are some exciting recent approaches for non-convex online learning (Agarwal et al, 2019; [Suggala & Netrapalli 2020). they do not apply to the above mentioned problem.
Our Techniques and Contributions: We first present a method bascd the pollor-then-coomii (ETC) approach (Algorithm 2). For first few rounds, the algorithm runs a pure exploration strategy by sampling random items cach user. We use the data obtained by pure exploration learn good estimate of underlying reward matrix P: this result requires a slight modification the standard matrix completion result in Chen al. (2019). We then run the exploitation rounds based on the current estimate. In particular, for the remaining rounds, the algorithm commits to the arm with the highest estimated reward for each user. With the ETC algorithm, we achieve a regret bound of Oppolylog(M M + N)T2/3) (Thm. Db. This bound is able to get rid of the dependence on N, implying non-trivial guarantees even when T < N. That is, we require only polylog(M + N) exploratory T is sub-optimal. To
recommendations per user. However. the dependence of the algorithm address this, we study the special but critical case of rank-one reward matrix. The rank-1 setting is itself technically challenging (Katuriya al. (2017b) and encapsulates many key issues. We provide novel algorithm OCTAL in Algorithm Bjand modified version in Algorithm [8 achieves nearly optimal regret bound of (poolyo (M 1/2 (see Theorems 2 and E. The key insight that in rank-one case, we need to cluster users based on their true latent representation to ensure low regret.
Our method OCTAL consists of multiple phases of exponentially increasing number of rounds. Each phase refines the current estimate of relevant sub-matrices of the reward matrix using standard matrix completion techniques. Using the latest estimate, we jointly refine the cluster of users and the estimate of the hest items for users in cach cluster. We can show that the regret in each phase decreases very quickly and since the count of phases required to get the correct clustering small, we obtain our desired regret bounds. Finally, we show that our method achieves regret guarantce that scales as O(T1/2) with the number of rounds T. We also show that the dependence on T is optimal (see Theorem Fo. Below we summarize our main contrihutions (Ō)-) hides logarithmic factors):
We formulate the online low rank matrix completion problem and define the appropriate notion of regret to study. We propose Algorithm 2 based on the explore-heen-comii approach that suffers regret of ((T3/3). (Thm.
We propose novel algorithm OCTAL (Online Collaborative filTering using iterAtive user cLuster- ing) and a modified version (Alg. [add Alg. (respectivelly) for the special case of rank-1 reward matrices and guarantee a regret of ((2)/2). Importantly, guarantees in the practical regime of M >> T and N >> T i. when the number of and items is much larger than the number of recommendation rounds. Morcover, OCTAL docs not suffer issue of large coad-start time (possibly large exploration period) as the ETC algorithm.
algorithms provide non-trivial regret
We conducted detailed empirical study of our proposed algorithms (sec Appendix A) on synthetic and multiple real datasets, and demonstrate that our algorithms can achieve signtficantly lower regret than methods that do not use collaboration between users. Furthermore, we show that for rank-1 I case, while it critical to tune the exploration period in ETC (as function of rounds and sub-optimality gaps) and is difficult in practice (Lattimore Szepesvári [C20) 61, OCTAL still suffers lower regret without such side-information (see Figures| aaland 2b).
Technical Challenges: For rank-1 case, i.c., P uvT one cluster users in two bins: ones with O and ones with 0. Cluster-2 users dislike the best items for Cluster-1 users and vice-versa. Thus, require algorithms that can learn this cluster structure and exploit the fact that within the same cluster, relative ranking of all items remain the same. This is a challenging information to
2

---

Published as a conference paper at ICLR 2023
exploit, and requires learning the latent structure. Note that an algorithm that first attempts to cluster all users and then optimize the regret will suffer the same T4/3 dependence the worst case as in the ETC algorithm; this is because the difficulty of clustcring the users are widely different. Instcad, our proposed OCTAL algorithm (Algorithms B [ in each iteration/phase performs two tasks: i) it tries to eliminate some of the items similar to standard phase elimination method (Lattimore & Szzeesvári [020][Ch 6, Ex 6.8] for users that are already clustered, ii) it simultancously tries to grow the set of clustcred users. For partial clustering, we first apply low rank matrix completion guarantees over carefully constructed reward sub-matrices each which correspond to a cluster of users and a set of active items that have high rewards for all users in the same cluster, and then use the partial reward matrix for eliminating some of the items in each cluster.
1.1 RELATED WORKS
To the best of our knowledge, we provide first rigorous online matrix completion algorithms. But, there are several closely related results/rechniques in the literature which we briefly survey below.
A very similar setting was considered in SSeen et al. (2117) where the authors considered a multi-armed bandit problem with contexts and K arms with context dependent reward distributions. The authors assumed that the L K reward matrix is low rank and can be factorized into non-negutive components which allowed them to use recovery guarantees from non-negative matrix factorization. Moreover. the authors only showed ETC algorithms that resulted T2/3 regret guarantees. Our techniques can be used to improve upon the existing guarantees in [Sen et al. (017)) in two ways 1) Removing the assumption of the low rank components being non-negative as we use matrix completion with entry-wise error guarantees. 2) The dependence on T can be improved from T2/3 to T1/2 when the reward matrix P is rank-1.
Nulti-dimensional online decision making problems namely stochastic rank-1 matrix bandits was introduced in Katariya et al. (201 a); TTrinh et al. (2020). In their scttings, at cach round / TT, the lcarning agent can choose one row and one cnlumn and observes a reward corresponding to an entry of a rank-1 matrix. Here, the regret is defined in terms of the best (row,colum colamn) pair which
corresponds to the best arm. This setting was extended to the rank setting (Kveton et al. (2017), rank
multi-dimensional tensors (Hao et al. 2020). bilinear bandits (Jun et al. 2019 Huang et al. (021) and generalized lincar bandits (Lu et al. they cannot be translated to our problem. This is because, we solve a significantly different problem with an underlying rank-1 reward matrix P where we need to minimize the regret for all users (rows of P) jointl. Hence, it is essential to find the entries (columns) of P with large rewards for each user(row) of P; contrast this with the moult-diimnnionaa online learning problem where it is sufficient to infer only the entry ((row.colun)) pair) in the matrix/tensor with the highest reward. Since the rewards for each user have different gaps. the analysis becomes involved for our OCTAL algorithm. Finally. (Dadkhahi & Negahban 2018 Zhou et al. 2020) also consider our problem setting but they only provide heuristic algorithms without any thcoretical guarantees.
2021). Although these papers provide tight regret guarantces,
Another closcly related line of work is the thcoretical model for User-hased Collaborative Filtering (CF) studied in |Bresler et al. (2014) (016): [Heckel & Ramchandran (2017): [resler& & Karzand Huleihel
[ et al. (2021) 1). In particular, these papers were the first motivate and theoretically analyze the collaborative framework with the restriction that the same item cannot be recommended more than once to the same user. Here significantly stricter cluster structure assumption is made over users where users in same cluster have similar preferences. Such models are restrictive they provide thcoretical guarantees only on very relaxed notion of regret (termed aseudo-regrett
In the past decade, several papers have studied the problem of offline low rank matrix completion on its own (Mazumder et al., 2010 Negahhan & Wainwright 2012 Chen et al. 2019 Deshpande & Montanari 2012] Abbe ct al. 2020 Jain ct al.] 2013) Jain Jain & Kar, 201 7) and also in the presence of
side information such as social graphs or similarity graphs (Xu ct al. (2013) 3,, Ahnn ct al. 2018 [021]
Elmahdy et al. 2020 Jo & Lee 202 I; Zhhang et al. (2022). Some of these results namely the ones that provide ||- Il norm guarantees on the estimated matrix can be adapted into
(ETC) style algorithms (see Sec. Aec. Finally, there is significant amount of related thcoretical work
for online non-convex learning (Suggala & Netrapalli 2020) Yang et al, 20188 [Huang et al., (020)
and empirical work for online Collahorative Fittering (Huang al. [2020] Luu al. 2013 (013
Zhang
al. 2015) but they do not study the regret in online matrix completion setting.
3

---

Published as conference paper at ICLR 2023
2 PROBLEM DEFINITION
Notations: We write [m]] denote the set 21.2....,,7 For a vector v R V, denotes the 5th element; for any set Ld S [m]. let vy denote vector restricted to the indices in M. A, denotes the 7th row of and Agg denotes the --thh element of matrix A. [m] denotes the set {1, 2, ..... .......... n). For any set 24 C [m], V C Au,y denotes the matrix A restricted to the rows in and columns in V. Also, let || 2- be the maximum Eg norm of the rows of A and | be the absolute value of the largest entry in A. We write E.X to denote the expectation of a random variable X.
Consider a system with set of M users and items, Let UVT RMXN the unknown reward matrix rank r < min(M, N) where U R and V RNxr denote the latent embeddings corresponding to users and items respectively. In other words, we can denote P:; {u:, v5) where u, V. E I" denotes the r-dimensional embeddings of i-th user and the j-th item, respectively. Often, will also use SVD decomposition of P U.V where Ú RM V RNKr are orthonormal matrices i... U = and V I and Σ - diag(A1, (1, ,2...,,,. dr) E R is diagonal matrix. We will denote the condition number of matrix by & (max: (mi A,)-
Consider system that recommends one item to every user, in cach round / E (T]. Let, R!t) the reward for recommending item (t( E [N] for user u. Also, let:
spu(() be
P (upu(t)
E (pu(t)
(1)
(P)
where ((0)
(P) denotes the unhiased additive noisc. Each element of [E(0) t0) IeeM)) is assumed
to be i.i.d zero mean uub-gaussian random variables with variance proxy o². That is. E B/E =
and [[exp(=E (e) ) S exp(o?s²/2) for u E MM] E [T]. The goal is to minimize the expected regret where the expectation is over randomness in rewards and the algorithm:
EE())
Reg(T)=
& M
Σ ME
uF
R [E[
Σ GC[M
R
up_ to)l
JEIN]
M
In this problem, the interesting regime is (N, M) >> T as is often the case for most practical recommendation systems. Here, treating each user separately will lead to vacuous regret bounds each item needs to be observed at least once by cach user find the best item for cach user. However, low-rank structure of the rewards can help share information about items across users.
Remark T N. then can treat each user separate multi-armed bandit problem. In that case, in setting, the well-studied Upper Confidence Bound (UCB) algorithm achieves expected regret of most O( /NT log T) (Theorem 2.1 in Bubeck Cesa-Bianchi 2012
3 PRELIMINARIES
Let us introduce a different observation model from (I) Consider an unknown rank r matrix P E MMN For each entry e [M].] e [N]. we observe:
Pt. + Bay with probability p. 0 with probability P.
(4)
where Eg are independent zero We introduce the following result from Chen al. (2019):
sub-gaussian random variables with variance proxy o² 0.
Lemma (Thcorem in Chen et al. (2019)). Let rank
O(1) matrix e Rdxd with SVD decomposition P = ΟΣV satiefy U & Vur/dd [V I uur/d and condition 2 p 2 Cu-d "oodd-oog' for some sufficientl large constant > 0, loga Pllx)) Suppose we observe noisy entries of P according to observation model
number O(1). pul
in
Then, with probability exceeding O(d-3) 3), we can compute a matrix P by using Algorithm (Appendix B with paraneters (M = [M, V [N]. rr,) s.t.,
||P
Plloo 5 50 o
Jullge d
Pllse)
(5)
mins As p

---

Published as conference paper at ICLR 2023
Algorithm ESTIMATE
Require:
Set users S MM] set items C [N] total rounds n., set indices Q C 4 x V, rounds in cach iteration 6 = max,cu l y (u. v) Q regularization parameter A. Index of
round relative to first round when the algorithm is invoked; hence 1, 2,.,..,,
= 1, 2, ................................ m//......//........... do
2: For all (8. E Q, set Mask., = 0.
3: for 1,2,..., do
4:
for each user a E 4 in round h = (f 1)b + 8 Recommend an item pt,(t) in {j V (u, E Q, Mask., = 0} and set Mask 1.
5:
If not possible then recommend any item Pr (f) in V s.t. (u, & Ω2 Observe R (1)
upul()"
end for end for
end
9: For cach (u.j) E Ω compute Zug to be average [m/b] observations corresponding to user u being recommended item j i.c. Zuj = avg avg(R upute) t [m] Pt())) = j}. Discard all other observations corresponding to indices not Q
10: Without loss of generality, assume [4] [V]. For each i V, independently set 6, to he value in the set [[[ [[]]] uniformly at random. Partition indices V into V(U) yx(2,.... ..... v(k) where k = [[]]/44] and Vie) = [i c V & q) for each c [b). Set ((9) c- an (21 x Vio)) for
all o E [k]. #ff [o4] [V], we partition the indices in L.
11: for q E [4: do
12: Solve convex program
min Qleegluuxiion)
Σ (Kn)n)
Z,)² +11
(3)
where ||(()]. denotes nuclear norm matrix Q and x(j) index j in set vio).
13: end
14: Return Q E BMNN s.l. Qu,y91 Q(9) for y [K] and for every (1.j) & 4 x V. Q., 0.
Note there are several difficulties in using Lemma T directly in our setting which are discussed below:
Remark 2 (Matrix Completion for Rectangular Matrices). Lemma 7 is described for square matrices and trivial approach to use Lemmal
Sommaaaor for rectangular matrices with M rows and N colunns (say N 2 Mj by appending N M zero rows leads an undesirable (N/My 1/2 factor (Lemma S the error bound (the /M/ factor does not arise if we care about spectral/Froenius norm instead of Lo norm). One way to resolve the issue is to partition the columns into N/M groups by assigning each column into one of the groups uniformly at random. Thus, we create N/M matrices which are almost square and apply Lemma [To to recover an estimate that is close in La norm. Thus we can recover an estimate of the entire marrix which is close in Loc norm up to the desired accuracy without suffering the undesirable (N/M)l2 122 factor (Lemmn ( and Steps 10-12 in Algorithu!) 1
Remark 3 (Observation Models), The observation model in equation 4 is significantly different from equation In the former, noisy version of each element of P is observed independently with probability p while the latter, in each round [T]. for each user [M]. observe noisy version of chosen element Ptl Our approach resolve this discrepancy theoretically is Q indices according equation 4 Andd subsequently the indices in ft (see Steps 3-6 in Algoritium [ aand Corollary 7 Of course, this implies obtaining observations corresponding
first sample
equation 7 to observe
indices a super-set of Q (see Step 5 in Algoritho 7 and only using the observations Q for obtaining an estimate of the underlying marii. In practice, this not necessary and we can use all the observed indices to obtain the estimate in Step 12 of Algorithm D
Remark 4 (Repetition and Median Tricks), The smallest error that is possible to achieve by us- ing Lemma is by substinuting
and thereby obtaining |P P Ploo S O a(min, Aa)-1
vdd log d |lls)) and moreover, the probabiliry faiture is polynomially small in the dimension d; however, this is insufficient when d is not large enough. Two simple tricks allow us to resolve this issue: 1) First we can obtain repeated observations from the same entry of the reward matrix and take its average; repetitions can bring down the noise variance d² 2/s 2) Second, we use the
5

---

Published as conference paper at ICLR 2023
median trick where obtain several independent estimates of the reward matrix and compute the element-wise median to boost the success prohability (see proof of Lemma 2
We address all these issues (see Appendix Bor detailed proofs) and arrive at the following lemma:
Lemma 2. Let rank r = (11) reward matrix RM with SVD decomposition P UEVI
satisfy || S v fur//M II o1,,cc S v prr/N and condition number K O(1). Let d1 max(M, N), d2 = min(M, N) such that d2 = Dipr log(rdz)) and 1 2 p 2 Cyâdg log" d2 for sufficiently large constant > O. Suppose we observe noisy entries of P according to observation
model in AlV. For any positive integer 0 satisfying V: = 00(
pdz 1r logid
[P|| there exists
algorithm A with parameters s,p, that uses m 0 (ssll
(No v Ny log Mo M6-1) 1)
rounds to compute a matrix P such that with probability exceeding - O log(MMN-1))
P- S O( or
1 log d2
Vada
P
times: 1) sample subset of indices Q S [M [N] such that every (i, [M] x [N] inserted into independently with probubility p. 2) By setting max;e[M] lá [N] (6.5) 91, Algorithu A invokes Alg. [ with total rounds bs, number of rounds in each iteration b set L set of users [M], items [N] and regularization parameter
Remark Alg. AA repeats the following process O(log(
O(log(MN6-)) (N)-1))
X =x0 /min(M, Nyp suitable constant Cx > in order compute an estimate of P. The final estimate P is computed by laking an entry-wise median of each individuul estimate obtained outpu from several invocations Alg. Aliernatively, Alg, A is detailed in Alg. Zin Appendix [
Note that the total number of noisy observations made from the matrix P is m M 2 MN pp- Therefore, informally speaking, the average number of observations per index is p. which results in error of Ó(a/ /SP) ignoring other terms (contrast with error Ö(ar/ /p) in equation 5)
Remark (Setting parameters s.p in lemma 2 Lemma 2 has three input parameters namely 2,0 p and S 1. For any set of input parameters (1) 1/), our goal is set s, as functions of known r, d2 such that we can recover
P - Plls S with probability 1 1-
for which the conditions on a and p are satisfied. From 117. we must have /5p = cgr V for some appropriate constant e > O. Ifr
vils
((1) and f |p then an appropriate choice
of e also satisfies the condition 7
O
vul log
[Plss))- More precisely, we are going to set
p Cy²d5' log d2 and s
/ y log da
order to obtain the desived guarantee.
4 EEPLORE-THEN-COMEE (ETC) ALGORITHM
In this scction, we present an Explore- matrix completion. The algorithm two disjoint phases exploration and exploitation. We will first jointly explore
(ETC) based algorithm online low-rank
set items for all users for certain number of rounds and compute an estimate P of the reward matrix P. Subsequently, we commit to the estimated best item found for each user and sample the reward of the hest item for the remaining rounds in the exploitation phase for that user. Note that the exploration phase involves using matrix completion estimator in order to estimate the entire reward matrix P from few observed entries. Our regret guarantees in this framework derived by carefully balancing exploration phase length and the matrix estimation error (detailed proof provided Appendix C
Theorem 1. Consider the rank-r online matrix completion problem with M users, N items, T recommendation rounds. Set d2 = min(M, N). Let R. Ru (1) he the reward in each round, defined as in equation | Suppose d2 B(rr log(rdz)). )). Let P E RMXN be the expected reward matrix that satisfies the conditions stated in Lemma 2] and let o² be the noise variance in rewards. Then, Algorithme applied to the online rank-r matrix completion problem guarantees the following regret:
(t)
Reg(T) = (0"r )1
log d2 d2
1/3
NP/||[P|loo d2
log"(MN)) (MNT)
||||
(7)
T2
6

---

Published as conference paper at ICLR 2023
Algorithm 2 ETC ALGORITHM
Require: users M, items N. rounds T, noise o², rank y upper bound on magnitude expected
rewards |||ss no, estimates f = (log(MNNT).
2/3 Set CyPd2 log" d2.
Set d2 = min(M, N) and (l]) 2/3
Tas
V log log
vdl
= [up-1] and À A= Cxa dap for some constants C, Cx > O.
2: for 1x=11 1,2,,...... /d
3: For each tuple of indices (i.j) [M] x [N), independently set by 1 with probability and
6,- 1) with probahility
4: Denote ? = ((tj)) E [M] [N] & = 11 and b max.g|| L [N] (f.,)) E Q to be
the maximum number of index tuples in a particular row. Set total number of rounds to be bs.
5: Compute the h estimate pik) = ESTIMATE([M], [N], bs, 52, b, A). # (Algorithm 1 used to
recommend items to every user for bs rounds.
6: end for
7: Compute final estimate estimate P by tuking the entry-wise median of (()) p(.)
8: for each of remaining rounds do
9: Recommend je Ny Pip for each user [M]. Number of remaining rounds bs
10: end for
Remark 7 (Non-trivial regret bounds), Theorem provides non-trivial regret guaraniees the key regime when N 3o T and M N where the regret scales only logarithmically M, N. This is intuitively satisfying since in each round we obtaining M observations. so more translate to more information which in-turn allows better understanding of the underlying reward matrix. However, the dependence of regret (namely T2/3) is sub-optimal. In the subsequent section, we provide novel algorithm obtain regret guarantees with T1/2 for rank-1 P.
Remark 8 (Gap dependent bounds). Define the minimun gap to be A
min M] [P (unT(1) 12: where (.),), (2()) (2) corresponds to the items with the highest and second highest reward for user respectively. the quantity A is known then it is possible to design ETC algoritimss where length of the exploration phase is tuned accordingly in order to obwain regret bounds that scale logarithmiccaly with the number of rounds T.
5 OCTAL ALGORITHM
In this section we present our algorithm OCTAL (Algorithm33 for online matrix completion where the reward matrix P is rank 1. The set of users is described by latent vector E RM and the set of items is described by latent vector v RR.. Thus P uv with SVD decomposition P = Auv
Our first key observation is that as P is rank-one, we can partition the set of users into two disjoint clusters C₁. C2 where C₁ = (2 E [M] u, 2 0} and C2 [M] \ C₁. Clearly, for all users a E C, the item that results in maximum reward is jmax = argmax+cIN Ve. On the other hand, for all users E Cz the item that results in maximum reward is juin argmin (e Va. Thus, if we can identify C,, C2 and estimate items with high reward (identical for users in the same cluster) using few recommendations per user, we can ensure low regret.
Algorithm Overview:
But, initially C2.Ca are unknown, all users are unlabelled i.c., their cluster unknown. In each phase (the outer loop indexed by (). Algorithm Juiis to label at least few unlabelled users correctly. This is achieved by progressively refining estimate Q of the reward matrix P restricted to the unlabelled users and all items (Step 12). Subsequently, unlabelled users for which the difference in maximum and minimum reward (inferred from estimated reward matrix) is large are labelled (Step 19). At the same time, in Step 13 users labelled in previous phases are partitioned into two elusters (denoted by M((7) and (4.2)) and for cach of them, the algorithm refines estimate of two distinct sub-man aub-matrices the reward matrix by recommending items only from a refined (NV(e.L) and (/(22) respectively) containing the best item (jmnc of jmin). We also identify a small set of good items for each labelled user (including users labelled in previous phases), which correspond to large estimated rewards. We partition all these users into two clusters (MM(F and M 1.2)) such that the set of good items for users in different clusters disjoint. We can prove that such partitioning possible; users in same cluster have same sign of user embedding.
7

---

Published as conference paper at ICLR 2023
Algorithm 3 OCTAL (ONLINE COLLABORATIVE FILTERING USING ITERATIVE USER CLUSTERING)
Require: Number of users items N. rounds noise o², bound on the entry-wise magnitude of expected rewards ||P|| se. incoherence jr.
1: Set M(I.) = ( Φ and B()) [M]. Aet = A((.2) = o. Set f (llgg(MNT))
and suitable constants a, C, C", Cx O.
2: for 8 f 1,2...., do
3: Set Ar = C²2 min (||Plss
Tvt log
4: for l: = 1.2....... do
5:
for each pair of non-null sets (B(9, N). (Mea), (M442) Denote (T(1) 7(3)) to be the considered pair of sets and i E (0.1, 2) to be its index.
[M] x [N] do
pe, Cp²dz, log" d2,, and s2,, 3, dag For cach tuple of indices (u. v) E ( xx(2), independently set bn = with probability Pe, and 6ue = with probability 1 Pt.á-
Set d2. (uin(7")///
//
2-
8:
9:
Denote 2 {(u, v) T (2)) 6ue 1} and be,, = maxueti |o E V (u,e)= é QJ. Set total numher rounds my.; be.881.
10:
end for Set max [0.1.2] mg.i.
11:
12:
Compute ((e.)) ESTIMATE([BCC) [N], my, 22 br.p, = Cxo / Aogpp)) # Algorithm
iii used recomumend items every user in 8 for my rounds.
13:
(iea),, my, 200 be,,, Cxovdd2.pp # Algorithm recommends items every user Ml5. for my rounds. end for
For i E (1,2), compute p(c.if) = ESTIMATE([MM*
14:
15:
Compute Q =Entrywise Median ((Â (Q(.M)) PIc.1) Entrywise Median (PIC)A))
for E {1,2)
16: Set ( (1)) 1) = { (uc. B( Imaxaciy Q min 8 2 20de] }
17:
Compute (e(+1) = (j E [N]] 8 + Ar > max
( for all u B( \ BB++1),
18: For i E (1,2). for all users u (f.))), compute (1+1) = Li E NO ple.) + D
(a P(f
Set u to be any user ((+H), Set M((t..)) = [u (i) 1) To (e T2 (141) * #).. M = [M] (B(++1) (((+..))
19:
Compute (/(+1.11) Muemanaa T((41) A/14112) = NNEMCHLL ((tt))
20:
21:
Fori (1, if (M vT.
M then set BB( +- B (UMEn and Mie11 <-
22:
end for
Wc also prove that the set of good items contain the best item for each lahelled user Gmax fmin). So, after each phase, for each cluster of users, compute the intersection of good items over all users in the cluster. This subset of items (joint good items) must contain the best item for that cluster and therefore we discard the other items (Step 20). We show that all items the of joint good items ()((+1,)3 and A A11++1.3) have rewards which is close to the reward of the best item. Therefore the algorithm suffers small regret from the set of joint good items (Step 13) in the next phase. We can further show that for the set of unlabelled users, the difference in rewards between the best item and worst item is small and hence the regret for such users is small, irrespective of the recommended item (Step 12). Note that until the number of labelled users is sufficiently large, we do not consider them separately (Step 21). A crucial part of our analysis is to show that for any subsct of users and items considered in Step 5, the number of rounds sufficient to recover good estimate of the expected reward sub-matrix is small irrespccivee of the number of considered items (if the number of users is sufficiently large).
each group labelled users, the algorithm recommends items
Remark 9 (Practical considerations) In general OCTAL (Alg. 3 is computationally faster than the ETC Algorithum (Alg. 2 with higher exploration length. This is because OCTAL eliminates large chanks of items in every phase and therefore has to solve easier optinization problems; on the other hand, ETC has to solve a low rank matrix completion problem in MN variables that becomes slower with the exploration length (datapoints). Moreover, OCTAL algorithun runs in phases with the initial
8

---

Published as conference paper at ICLR 2023
phases being very small; hence the users do not have to wait for long time even get personalized reconunendations like in ETC. These features make OCTAL much more practical than ETC.
To summarize, in 3lgorithm the entire set of rounds [T] is partitioned into phases of exponentially increasing length. In each phase, for the set of unlabelled users, do pure exploration and recommend random items from the of all possihle items (Step 12). The of lahelled users are partitioned into two clusters; for each, follow semi- eemi-exploration strategy where we recommend random items from set of joint good items (Steps 13). We now introduce the following definition:
Definition 3 ((a, ,c)- Locao Incoherence), For 0 S a S 1, a vecior E Ih is (ax, j)) -locl incoherent if all sets 2 C [m]] satisfying [M4] 2 arn, have || S |Ival
Local incoherence for a vector implies that any sub-vector of having significant size must he incoherent well. Note that the local incoherence condition trivially satisfied if the magnitude of each vector entry bounded from helow. We now ready to state our main result:
Theorem 2. Consider the rank-1 online mutrix completion problem with T rounds, M users s.I. M 2 VT and N items, Denote d2 = min(M, N). Let R!!) (p.lt) be the reward in each round, defined as in equation 1 Let o² be the noise variance in rewards and let P E BMMx be the expected reward matrix with SVD decomposition P Auv T such that is (T- 1/2 (11) (o)-locally incoherent, || S ///N. dg Miplog (ogg)) and Viinl
Smne Then, by suitably choosing parameters Aete positive integers (ScE.))=((E.3)) S(E,2)) and 1 2 (P(e.o)- P(E,): Pie.2)) 2 as described in Algorithm can ensure regret guarantee of Reg(T) O(vT Pllx + JVTV) where "vT log
J 0= log
W min (I|P]be:
and V maxx No/T ) log (MNT)).
Similar to Algorithm Algorithm 3 allows non-trivial regret guarantees even when the number of users significuntly large as well i.e. M R(NvT).
provided
Remark 10. Under slightly stronger local incoherence conditions on the vector ú, we can analyze a modified version of OCTAL (Alg. (5 without requiring users M to be large. When [Ca] z [C]2, the
regret guarantee (Thm. E scales as Ö( /NT/M). Due space limitations, details of Algoritim 8
and the proof of Theorem can be found in Appendix L
Finally, we show that the above dependence on N, M. T matches the lower bound that we obtain by reduction to the well-known multi-armed bandit problem.
Theorem 3. Let P E [o, 1|MxN be rank 1 reward matrix and the noise variance o² = 1. In that case, any algorithm for online matrix completion problem will suffer regret of (D( 1).
6 CONCLUSIONS
We studied the problem of online rank-one matrix completion in setting of repeated item recom- mendations and blocked item recommendations, which should be applicable for several practical recommendation systems, We analyzed an explore-teen-comme (ETC) style method which is able to get the regret averaged over users to he nearly independent numher of items. That is, per user, we require only logarithmic many item recommendations to get non non-trivial regret bound. But, the dependence on the number of rounds T is sub-optimal. We further improved this dependence by proposing OCTAL that carefully combines exploration, exploitation and clustering for different users/items. Our methods iteratively refines estimate of the undcrlying reward matrix, while also identifying users which can he recommended certain items confidently. Our algorithms and proof techniques are significantly different than cxisting bandit lcarning literature. We believe that our work only scratches the surface of an important problem domain with several open problems. For example, Algorithm requires rank-1 reward matrix. Generalizing the result to rank-r reward matrices would be interesting. Furthermore, relaxing assumptions on the reward matrix like stochastic noise or additive noise should be relevant for several important settings. Finally, collaborative filtering can feed users related items, hence might exacerhate their hiases. Our method might actually help mitigate the bias due to explicit exploration, but further investigation into such challenges is important.
9

---

Published conference paper at ICLR 2023
REFERENCES
Emmanuel Abbe, Jianqing Fan, Kaizheng Wang, and Yiqiao Zhong. Entrywise eigenvector analysis of random matrices with low expected rank. Annals of statistics, 48(3):1452, 2020.
Naman Agarwal, Alon Gonen, and Flad Hazan, Learning non-convex games with an optimization oracle. Conference on Learning Theory, pp. 18-29. PMLR, 2019.
Junhyung Ahn, Adel Elmahdy, Soheil Mohajer, and Changho Suh. On the fundamental limits of matrix completion: leeeeraging hierarchical similarity graphs. arXiv preprint arXiv:2 2021.
Kwangjun Ahn, Kangwook Lec, Hyunscung Cha, and Changho Suh. Binary rating estimation with graph side information. Advances in neural information processing systems, 31, 2018.
Guy Bresler and Mina Karzand. Regret bounds and regimes of optimality for user-user and item-item collaborative filtering. arXiv:1711.00 1.2111102111 1.02198, 2019.
Guy Bresler, George H. Chen, and Devavrat Shah. A latent source model for online collaborative filtering. In Proceedings of the 27th International Conference on Neural Information Processing Systems Volume 2. NIPS' 14, pp. 3347-3355, 2014.
Guy Bresler, Devavrat Shah, and Luis Filipe Voloch. Collaborative filtering with low regret. In Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling Computer Science, SIGMETRICS '1,, pp. 207-220, New York, NY, USA, 2016. ACM.
Séhastien Buheck. Introduction to online optimization. Lecture Notes, 2, 2011.
Séhastien Bubeck and Nicolo Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi- armed bandit problems. arXiv preprint arXiv: /20M.571, 2012.
Emmanuel J Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foun- dations of Computational mathematics, 96):717-77,, 2009.
Yuxin Chen, Yuejie Chi. Jianqing Fan, Cong Ma, and Yuling Yan. Noisy matrix completion: Understanding statistical guarantces for convex relaxation nonconvex optimization. arXiv preprint arXiv: /90. 07698, 2019.
Hamid Dadkhahi and Sahand Negahban. Alternating lincar bandits for online fattii-factooization recommendation. arXiv preprint 18Iiv:18100 09401, 2018
Yash Deshpande and Andrea Montanari. Lincar bandits high dimension and recommendation systems. Allerton Conference on Communication. Control, and Computation, pp. 1750-1754, October 2012.
Adel Elmahdy, Junhyung Ahn, Changho Suh, and Sohcil Mohajer. Matrix complction with hierarchi- cal graph side information. Advances in neural information processing systems, 33:9061-9019 2020.
Goldberg, Theresa Roeder, Dhruv Gupta, Chris Perkins. Eigentaste: constant time collaborative filtering algorithm. information retrieval, 4(2):133-151, 2001.
Botao Hao. Jie Zhou, Zheng Wen, and Will Wei Sun. Low-rank tensor bandits. arXiv preprint arXiv:2007.1 15788, 2020.
Reinhard Heckel and Kannan Ramchandran. The sample complexity of online one-class collaborative filtering. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML'17, 17, pp. 1452-1460. JMLR.org, 2017.
Baihe Huang, Kaixuan Huang. Sham Kakade, Jason D Lee. Qi Lei, Runzhe Wang, and Jiaqi Yang. Optimal gradient-based algorithms for non-concave handit optimization. Advances in Neural Information Processing Systems, 34:29101-29) 29115, 2021. 2021.
10

---

Published as conference paper at ICLR 2023
Xiao- Yu Huang, Bing Liang, and Wubin Li. Online collaborative filtering with local and global consistency. Information Sciences, 506:366-382, 2020)
Wasim Huleihel, Soumyabrata Pal, and Ofer Shayevitz. Learning user preferences non-stationary environments. In International Conference on Artificial Intelligence and Statistics, pp. 1432-1444 1440.
PMLR, 20/21.
Prateck Jain and Purushottam Kar. Non-convex optimization for machine learning, arXiv preprint arXiv: 1712.07777 2017.
Prateck Jain, Pranceth Netrapalli, and Sujay Sanghavi. Low-rank matrix complction using altemating minimization. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pp. 665-674, 2013.
Changhun Jo and Kangwook Lec. Disuuete-valued latent preference matrix estimation with graph side information. In International Conference Machine Learning, pp. 5107-5117. PMLR, 2021.
Kwang-Sune Jun, Rebecca Willett, Stephen Wright, and Robert Nowak. Bilinear bandits with low-rank structure. International Conference on Machine Learning, pp. 3163-3172. PMLR, 2019.
Sumeet Katariya, Branislav Kveton, Csaba Szepesvári, Claire Vemade, and Zheng Wen. Bemoulli rank-1 bandits for click feedback. arXiv preprint arXiv:17030065/1 2017a.
Sumeet Katariya, Branislav Kveton, Csaba Szepesvari, Claire Vernade, and Zheng Wen. Stochastic rank-1 bandits. Artificial Intelligence and Statistics, pp. 392-401. PMIR, 2017b.
Yehuda Koren. Factorization meets the neighborhood: A multifaceted collaborative filtering model. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Duta Mining, KDD '08. pp. 426 434, New York, NY, USA. 2008, ACM.
Branislav Kveton, Csaba Szepesvári, Anup Rao, Zheng Wen, Yasin Abbasi Abbasi-Yadkori, and Muthukr- ishnan. Stochastic low-rank handits, arxiv preprint arxiv: 1712.04644, 2017.
Tor Lattimore and Csaba Szepesvári. Bandit algorithmms. Cambridge University Press, 2020.
ling Lui, Steven Hoi, Jialei Wang. Second order online collaborative filtering. In Asian Conference on Machine Learning, pp. 225-340. PMIR, 2013.
Yangyi Lu, Amirhossein Meisami, and Ambuj Tewari. Low-rank generalized lincar bandit problems. In International Conference on Artificial Intelligence and Statistics, pp. 460-468. PMLR, 2021.
Rahul Mazumder, Trevor Hastie, and Robert Tibshirani. Spectral regularization algorithms learning large incomplete matrices. The Journal of Machine Learning Research, 11:2287-2322. 2010.
Sahand Negahban and Martin J Wainwright. Restricted strong convexity and weighted matrix completion: Optimal bounds with noise. The Journal of Machine Learning Research, 13(1): 1665-1697, 2012.
Rajat Sen, Karthikeyan Shanmugam, Murat Kocaoglu, Alex Dimakis, and Sunjay Shakkottai. Con- textual bandits with latent confounders: An nmf approach. In Artificial Intelligncee and Statistics, pp. 518-527. PMLR, 2017.
Shai Sawwar-S al. Online learning and online convex optimization. Foundations and trends in Machine Learning, 4(2):107-194, 2011.
Arun Sai Suggala and Pranceth Netrapalli, Online non-convex learning: Following the perturbed leader is optimal. In Algorithmic Learning Theory, pp. 845 861. PMLR, 2020.
Cindy Trinh, Emilie Kaufmann. Claire Vernade, and Richard Combes. Solving bernoulli rank-one handits with unimodal thompson sampling. In Algorithunic Learning Theory, pp. 862-889. PMIR, 2020.

---

Published conference paper at ICLR 2023
Joel A Tropp. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12(4):389-433 2012.
Miao Xu, Rong Jin, and Zhi-Hua Zhou. Specdup matrix completion with side information: Applica- tion multi-label learning. Advances neural information processing systems, 26, 2013.
Lin Yang, Lei Deng. Mohammad Hajiesmaili, Cheng Tan, and Wing Shing Wong. An optimal algorithm for online non-convex learning. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1-2):125,, 2018.
Feng Zhang, Ti Gong. Victor Lee, Gansen Zhao, and Guangzhi Qu Simple is beautiful: An online collaborative filtering recommendation solution with higher accuracy. In Asia-Puciffe Web Conference, pp. 497-508. Springer, 2015.
Qiaosheng Zhang, Geewon Suh, Changho Suh, and Vincent YF Tan. Mc2g: An efficient algorithm for matrix completion with social and item similarity graphs. IEEE Transactions on Signal Processing, 2022.
Jie Zhou, Botao Hao, Zheng Wen, Jingfei Zhang, and Will Wei Sun. Stochastic low-rank tensor bandits for multi-dimennional online decision making. arXiv e-prints, pp. arXiv-2007, 2020.
Cai-Nicolas Ziegler. Sean M McNee. Joseph A Konstan, and Georg Lausen. Improving recommen- dation lists through topic diversification. In Proceedings of the 14th international conference World Wide Web, pp. 22-32, 2005.
12


Reviews:
[{"review_id": "oa80uXlFWN2", "reviewer": "Reviewer_cVaQ", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "This paper provides some regret bounds for *online* matrix completion: at each round, a recommendation is made for each of the M users and the reward is observed. The reward distribution is unchanged through time (this is therefore a contextual bandit scenario). \nIn the simplest approach (Sections 3, 4, B and C), the authors provide an ETC (explore then commit) approach which roughly consists in making uniformly random (see details in “weaknesses”) predictions until sufficient data has been collected, and then sticking to the optimal strategy (recommending the “best” item according to the current estimate of the matrix) for the rest of the time. The estimation procedure is based on nuclear norm regularization. A regret bound of $\\widetilde{O}(T^{2/3})$ is provided for this setting.  \n\nIn the next approach, the specific case where the ground truth data is rank one is studied via an ingenious algorithm called OCTAL which leverages the fact that the users and items can be clustered based on the sign of their latent representations. Regret bounds are proved for this setting and experiments demonstrate the efficiency of the method \n\n", "summary_of_the_review": "It is a **very interesting and impactful paper**. The *proofs are still quite sloppy*, though they improved since the last time I reviewed this paper two conferences ago. \n\nFortunately, ICLR is openreview and there is unlimited space for rebuttals and for updated versions of the manuscript, so we will definitely get to the bottom of this. I will raise my score to 8 if the next revision uploaded contains *clean proofs*. \n\n\n\n\n\n[**BEGINNING OF POST REBUTTAL UPDATE AND SUMMARY**]\n\n\nI have previously reviewed this paper. This is a highly technical and complex paper that I am guessing required a lot of work from the authors. The original version had both minor typos and significant technical issues with a lot of vaguely phrased statements in between, around 60 percent of which eventually turned out to be correct and 40 percent of which could be fixed with modifications to the assumptions or calculations.  After discussions and rebuttals, we managed to fix all issues and improve the readability of the proofs and the versions of the manuscript are converging. Therefore I think the current version of the paper is ready for publication and is a very interesting and worthy piece of work, with **substantially above average quality and impact compared to other ICLR accepted papers.** Therefore, I am raising my score from 5 to 8. **I would put a score of 9 if it was possible.**\n\nI have also increased my correctness score from 2 to 4. However, there are some parts of the paper I didn't have time to look at in much detail during this round of review (mainly Appendix D), so I highly encourage the authors to proofread this before the camera-ready version. \n\nIn general, I wish authors would write more details in calculations in other submissions. Otherwise, if there are errors (which is almost unavoidable in such highly technical papers), reviewers will end up (legitimately) questioning the correct parts of the papers as well. \n\n\n[**END OF POST REBUTTAL UPDATE AND SUMMARY**]\n\n\n\n\n==========================Miscellaneous extra comments (**Minor**)============================\n\n\n\nYou might want to cite [4] when talking of the nuclear norm regularisation strategy as this is the usual reference from a practical point of view.\n\nIn the paragraph starting with “In the past decade, …” on page 3, the authors mention “inductive matrix completion”, i.e. the problem of matrix completion in the presence of side information.  It is usual to cite at least [3] there. \n\n\nTheorem 1 from [1] is correctly cited in page 17 of the supplementary (as “Lemma 4”) but not as “lemma 1” in the main paper, where there is an arbitrary constant c there. I agree with remark 11 that the result can probably be extended this way but that is not the statement of the main theorem (1.3) in that reference as is (though there is an extension in the same paper which is formulated similarly and the “for a constant c” is still lying around in the theorem statement in that reference without being used). In addition, it doesn’t seem that the authors need this strengthened result here  as the most likely place where this could be needed would be the end of the proof of Lemma 6, but there is an independent failure probability there which means it is not necessary. \n\n\n\n\n\n==============================References===================\n\n\n[1] Yuxin Chen, Yuejie Chi, Jiangqing Fan, Cong Ma, Yuling Yan. “Noisy matrix completion: understanding statistical guarantees for convex relaxation via convex optimization”.  SIAM J. Optimization, 2020. \n\n[2] Rajat Sen, Karthikeyan Shanmugam, Murat Kocaoglu, Alex Dimakis, Sanjay Shakkottai. “Contextual Bandits with latent confounders: an nmf approach”. Artificial Intelligence and Statistics, PMLR 2017. \n\n[3] Miao Xu, Rong Jin, Zhi-Hua Zhou. Speedup Matrix Completion with Side Information: Application to Multi-Label Learning. \n\n[4] Rahul Mazumder, Trevor Hastie, Robert Tibshirani. Spectral Regularization Algorithms for Learning Large Incomplete Matrices. JMLR 2010.\n\n\n", "strength_and_weaknesses": "\n\n\n\n**Strengths**:\n\nThis is a fantastically interesting and under-researched topic. \nThere is a lot of material in the paper and the results are non trivial and impactful \nThere is some progress since the last time I reviewed this paper (ICML): some attempt at fixing the issues I mentioned has been made. In particular, I appreciate that the authors now included the actual optimization problem involved in the estimation of the matrix  (line 12, page 5). I also appreciate that the authors are now conscious of the issue of different sampling regimes (see remark 3), and have attempted to adapt the algorithms to take this into account as per my suggestion. The problems with non square matrices has been much better explained and seems correct now. The case of a large number of observations leading to the same entries being sampled many times is at least attempted. \n\n\n**Weaknesses**:\n\nThe proofs are still very far from clean. Whilst I now agree that all the issues can be fixed “along the lines” sketched in this paper, it has not been done properly yet. In particular, the supplementary is very vague in how it refers to the algorithms is uses, the proof of corollary 1 (which used to be corollary 2 in the previous draft) is still incorrect and largely forgets about all the issues (which are now mentioned in the main paper).  \n\nI am not sure, but I remain somewhat sceptical that the resampling procedure proposed in algorithm 2 is the correct one. It might work, but as far as I am concerned, the closest correct version of the (still incorrect) proof of Lemma 7 would use a different strategy. \n\n\n\n\n\n\n\n\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "d7pOla4pQB", "reviewer": "Reviewer_qsQL", "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": "", "summary_of_the_paper": "This paper considers online low-rank matrix completion problem, where in each round the algorithm recommends one item per user, for which it gets a noisy reward sampled from a low-rank user-item preference matrix. The authors proposed two algorithms, ETC and OCTAL. ETC obtains a sub-optimal $T^{2/3}$ rate but the OCTAL only works for rank-1 case. ", "summary_of_the_review": "This paper considers online low-rank matrix completion problem, which can be viewed as a special contextual low-rank matrix bandit. In spite that there are some new results, the technical contribution beyond existing literature is limited. In addition, there are a few unclear parts in the practical implementations. \n\n", "strength_and_weaknesses": "Strength:\n\n1. In spite of a theoretical paper, it is generally easy to follow.\n\n2. The considered online low-rank matrix completion problem is interesting and has received increasing attentions recently. \n\n\nWeaknesses:\n\n1. Technical novelty & related work: My major concern is its technical contribution beyond existing literature. There have been a few recent developments in contextual low-rank matrix/tensor bandit. The considered online low-rank matrix completion can be viewed as a contextual low-rank matrix bandit setting where the user side is the context and the item side is the action/arm. However, none of the following recent works was compared in the experiments. In my personal opinion, the technical novelty beyond these references are limited. \n\nSen et al. (2017) considered the same contextual low-rank matrix bandit problem. The authors claim that the proposed work is better as the rate of $T$ is improved from $T^{2/3}$ in Sen et al. (2017) to $T^{1/2}$. However, this improvement is only for rank-1 case. The proposed OCTAL only works for rank-1 and the proposed ETC algorithm has the same $T^{2/3}$ as in Sen et al. (2017). \n\nLu et al. (2018) used ensemble sampling for the low-rank matrix bandit problem and their framework can be easily adapted to contextual matrix bandit setting. This paper was not mentioned. \n\nJun et al. (2019) and Huang et al. (2021) considered bilinear bandits that can also be viewed as contextual low-rank matrix bandits. However, the authors just briefly mentioned these references and claimed that \"they cannot be translated to our problem\".\n\nZhou et al. (2020) even considered more general low-rank tensor bandit and contextual low-rank tensor bandit settings. In their contextual low-rank tensor bandit settings, some mode of the tensor is context and is given, while other modes of the tensor are arms to be decided. It is a higher-order generalization of the considered online low-rank matrix completion in this paper. Importantly, Zhou et al. (2020) also used ETC-type algorithm and proved $T^{2/3}$, and proposed ensemble sampling-type algorithm for contextual low-rank tensor bandit. Their algorithm can be directly used for the considered problem in this paper. \n\nLu, X., Wen, Z., and Kveton, B. (2018), “Efficient online recommendation via low-rank ensemble sampling,” Proceedings of the 12th ACM Conference on Recommender Systems, 460–464.\n\nKwang-Sung Jun, Rebecca Willett, Stephen Wright, and Robert Nowak. Bilinear bandits with low-rank structure. In International Conference on Machine Learning, pp. 3163–3172. PMLR, 2019.\n\nBaihe Huang, Kaixuan Huang, Sham Kakade, Jason D Lee, Qi Lei, Runzhe Wang, and Jiaqi Yang. Optimal gradient-based algorithms for non-concave bandit optimization. Advances in Neural Information Processing Systems, 34:29101–29115, 2021.\n\nZhou, J., Hao, B., Wen, Z., Zhang, J. and Sun, W.W., 2020. Stochastic Low-rank Tensor Bandits for Multi-dimensional Online Decision Making. arXiv e-prints, pp.arXiv-2007.\n\n\n2. Although the proposed OCTAL achieves the optimal rate $T^{1/2}$ in time horizon, the algorithm only works for rank-1 case. This is a very limited scenario. In the literature, Katariya et al. (2017) considered rank-1 matrix bandit because their work was the first one to consider such-type problem. Given that there have been many new developments in general-rank matrix bandit setting, it would be important to extend the current OCTAL algorithm and its theory to general-rank case.  \n\n\n3. In practice, how do you estimate rank in the ETC algorithm? In offline matrix completion, we can use cross-validation to tune the rank. However, it is unclear how to tune the rank in online matrix completion case.\n\n\n4. Related to Question 3, how do you decide other unknown input parameters, e.g., noise \\sigma^2, \\|P\\|_{\\infty}, a, c, C, C', C_{\\lambda}, in Algorithm 2 and 3?\n\n\n5. Compared to OCTAL, the proposed ETC has a worse regret bound and a worse numerical performance. What's the motivation of proposing Algorithm 2?\n\n", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "blxmbMVpZxu", "reviewer": "Reviewer_qZSG", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "This paper considers the online low-rank matrix completion problem for recommendation systems. An expected regret formulation, as the core analysis goal of the proposed problem, is defined and then minimized via the proposed ETC algorithm and a further OCTAL algorithm for special case of rank-one reward matrices. It provides rigorous regret guarantees for the proposed algorithms and supplementary experiments are conducted to verify its superiority over the baselines.  ", "summary_of_the_review": "This work formulates an interesting online low-rank matrix completion problem for recommendation systems, and designs several specific algorithms with theoretical guarantees. This work provides lots of solid analysis and proofs, and its originality and novelty are clear enough.", "strength_and_weaknesses": "Strengths: This work proposed a novel and interesting online low-rank matrix completion problem closely extracted from the application of recommendation systems. The analysis of the proposed method is very inspiring and solid, which utilized the very recent advanced fine-grained theoretical analysis technique in the noisy matrix completion field. \n\n-Weaknesses: This work lacks sufficient experimental comparison with other methods for the recommendation systems application like one or two more offline algorithms besides the baseline UCB. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster