Partial Matrix Completion
Authors: Elad Hazan
Adam Tauman Kalai
Varun Kanade
Clara Mohri
Y. Jennifer Sun
Venue: NeurIPS 2023 poster (2023)
Keywords: matrix completion
online learning

Abstract: The matrix completion problem involves reconstructing a low-rank matrix by using a given set of revealed (and potentially noisy) entries. Although existing methods address the completion of the entire matrix, the accuracy of the completed entries can vary significantly across the matrix, due to differences in the sampling distribution. For instance, users may rate movies primarily from their country or favorite genres, leading to inaccurate predictions for the majority of completed entries.

We propose a novel formulation of the problem as Partial Matrix Completion, where the objective is to complete a substantial subset of the entries with high confidence. Our algorithm efficiently handles the unknown and arbitrarily complex nature of the sampling distribution, ensuring high accuracy for all completed entries and sufficient coverage across the matrix. Additionally, we introduce an online version of the problem and present a low-regret efficient algorithm based on iterative gradient updates. Finally, we conduct a preliminary empirical evaluation of our methods.

Partial Matrix Completion
Elad Hazan
Adam Tauman Kalai
Princeton University
Microsoft Research
Google DeepMind
Varun Kanade University Oxford
Clara Mohri Harvard University
Y. Jennifer Sun Princeton University Google DeepMind
Abstract
The matrix completion problem aims to reconstruct a low-rank matrix based on a revealed set of possibly noisy entries. Prior works consider completing the entire matrix with generalization error guarantees. However, the completion accuracy be drastically different framework of partial matrix completion, where the goal is to identify a large subset of the entries that can be completed with high confidence. We propose efficient algorithm with the following provable guarantees. Given access to samples from an unknown and arbitrary distribution, guarantees: (a) high accuracy over completed entries, and (b) high coverage of the underlying distribution. We also consider an online learning variant of this problem, where we propose low-regret algorithm based on iterative gradient updates. Preliminary empirical evaluations are included.
different entries. This work establishes
Introduction
In the classical matrix completion problem, a subset of entries of a matrix are revealed and the goal is reconstruct the full matrix. This is in general impossible, but if the matrix is assumed to be low rank and the distribution over revealed entries is uniformly random, then it can be shown that reconstruction is possible. A common application of matrix completion is in recommendation systems. For example, the rows of the matrix can correspond to users, the columns to movies, and an entry of the matrix is the preference score for the user over the corresponding movie. The completed entries can then be used to predict user preferences over unseen movies. The low rank assumption in this case is justified if the preference of users over movies is mostly determined by a small number of latent factors such as the genre, director, artistic style, and so forth.
However, in many cases, it is both infeasible and unnecessary to complete the entire matrix. First consider the trivial example of movie recommendations with users and movies coming from two countries A and B, where each user rates random movies only from their country. Without any cross ratings of users from country A on movies from country B vice versa, is impossible accurately complete these entries. A solution here is straightforward: partition the users and movies into their respective groups and then complete only the part of the matrix corresponding to user ratings of movies from their own country.
In reality, many users have categories of movies with few or no ratings based on genre, language, or time period. For such users, is difficult to accurately complete unrated movie categories which they do not like to watch from those which they have not even been exposed to. Thus it may be preferable abstain from making rating predictions for such users on these unpredictable categories. This is
Authors ordered alphabetically
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

further complicated by the fact that such categories are not crisply defined and relevant categories may vary across user demographics like country and age.
Latent observations
Actual observations
Completions
Unpermuted completions
π
Comedies Horror movies
Figure 1: A simple example where some users rate only comedies and some rate only horror movies. However, these two groups are unknown and the rows and columns are permuted according to TC πR. The partial completions made by algorithm, shown simulated data, correspond to completing the ratings for the half of the matrix as one would like. Note that our algorithms can handle arbitrary revealed subsets, not only stochastic block models. The experimental setup and more preliminary experiments are described in Section
This motivates
identify subset of the matrix that be completed by the existing observations with high confidence? We call this problem partial matrix completion. Let M be target matrix. A non-convex formulation would be to find matrix M and a set of entries C [m]] x [n] which maximizes:
general question:
max C[Im]x(n]
C| s.t.
(M - -M,))² S. (KJ))C
Σ
(1)
|C|
This is non-convex because the set C' is discrete and also because the choice of A interacts C. Fortunately, there are already several matrix completion algorithms which output M that guarantee low "generalization error" with respect to future examples from the same distribution of entries as those from the training distribution, though they are not accurate over the entire matrix. We will fix any one of these completions M.
We thus relax the goal of partial matrix completion to identify a matrix C which gives a confidence score for each entry between 0 and 1. A value of O indicates that this entry should not be completed, whereas indicates we have absolute confidence. We call this matrix the confidence matrix. Ideally, we would like that the confidence matrix to have value of on all entries that are well supported by the observation distribution.
We formalize this problem through the following definitions. The precise definitions of some of the terms will be introduced in subsequent sections. Let M be a target matrix and M be completion given by matrix completion algorithm that guarantees low generalization eтror over future examples from the same entry distribution (formal definition given Def. g and let 0. The coverage of
C' is defined to be ||C|]| def Σe, |Ciyl-
Definition (Partial matrix completion problem). Let M* a target matrix and M a full completion (Def. 8), and e >>> 0 be an error tolerance. Find confidence matrix C E [0, 1|mxx with maximal coverage, i.e.
arg max mm
||C||| s.L.
Σ
Ci - Ma)) Se.
(E(m),E[()
The matrix C' that solves the above optimization problem has following property: Ciy indicates whether the (i. entry shall be completed, and a fractional value can be interpreted as either fractional completion or a probability of completion. C provides the largest coverage among all that satisfy the property that the average error is at most over the completed entries.

---

Challenges of partial matrix completion. The above formulation is intuitive and convex, but notice that we do know M and thus cannot apply convex optimization directly.
Key challenges are illustrated by intuitive, but naive approaches. First, consider completing just those matrix entries (i, j) where all rank-k completions have nearly the same value Myj. Even in simple case where all revealed entries are 1, any single entry could be 1 for some rank 2 completion of the matrix. Based on this, one often will not be able complete any entries whatsoever.
Second, consider the generalization of our previous example where the sampling distribution is uniform over an arbitrary subset U of m x possible indices. For simplicity, think [t] = mn/ 2 as covering half the matrix. It follows from previous generalization bounds matrix completion that one could accurately complete all entries in U. However, in general is unknown and arbitrarily complex. The second naïve approach would be to try to learn U, but this requires R |U| -mn22 2 > m observations.
1.1 Our contribution
We present an inefficient algorithm and its efficient relaxation to solve the partial matrix completion problem with provable guarantees over arbitrary sampling distributions. In particular, if μ is uniform over some arbitrary subset U S [m] x [n]] of a rank-k matrix M E [-1, _|mxx" the theoretical results obtained in this work have the following implications. The first, is an inefficient algorithm that solves the partial matrix completion problem for uniform distribution:
Corollary 2 (Inefficient algorithm, uniform sampling distribution). For any E, 8 > O, with probability
8 over N 2 Co co. Algorithm (ecc.
#(m+n)++og(() revealed entries from M drawn from μ., for some constant
8² outputs M and C' E [0, [0.1]"xx. such that
(1): ||]|| 2 [U}
(2) || (E(m)]J[M)
Σ
Ci My)) Se.
Next, we describe the guarantees of an efficient algorithm? 2 It has a worse sample complexity, up to polynomial factors in k The advantage is that it runs in polynomial time. Otherwise, its guarantees are similar to that of the first algorithm.
Corollary 3 (Efficient algorithm, uniform sampling distribution). For any s, > O, with probability S 1 5 over N 2 co - (k(m + n) log(1/8)) revealed entries from M drawn from p. for some constant co, Algorithm (Sec. outputs M and E [o, 1jaxm, such that
(1) [|C| 2 U..
(2) | (eIm)JE(M)
Σ
Co Se.
Corollary 2 is a simplification of Theorem 10 and Corollary Blis a simplification of Theorem
The results can be extended to the setting where the observed entries are noisy with zero-mean bounded noise. remarkable feature of our algorithms that once the full completion M is obtained using existing procedures, they only rely on the locations of observed entries and not the values. Thus, the decisions regarding which entries to complete, i.e., to add to is completely agnostic to the actual values of the revealed entries. Our framework is able to handle arbitrary sampling distributions, which captures scenarios such as overlapping groups or idiosyncratic rating habits.
The online setting. We formulate the partial matrix completion problem in the online learning setting and propose an iterative gradient based online algorithm with provable guarantees. Corollary is special case of Theorem 22, A simple simulation of the online algorithm in this special case of uniform sampling over a subset of entries is demonstrated in Fig. I
Corollary 4 (Online algorithm, uniform sampling distribution). Suppose M E [-1, 1jnx is bounded matrix with max-norm (Eq. 2 bounded by K. The sampling distribution μ is uniform over a fraction 0 < of the n² entries. For any d 0, after T 0(8-2 k2)) iterations, the
3

---

confidence matrix C' E [0, 1|mxx output by the online algorithm ODD satisfies with probability at least 1 o1 exp(-c202T) for some universal constants C1 C2 > 0,
(1): : ||C|| (c yn2
(2) I MEV (E(m).JE(M)
1
sup
Σ
Mi - M2)
c- 6-///6'
81/6
where V is the set of all matrices M E [-1, 1| with max-norm bounded by K satisfying that Eag M; - 8.
1.2 Related work
Matrix completion and recommendation systems. The common approach to collaborative filtering is that of matrix completion with trace norm minimization [Srebro] 2004). It was shown that the trace norm regularization requires (2((n + m) m)3/3) observations to complete the matrix under arbitrary distributions, even when the rank of the underlying matrix is constant, and this suffices even in the more challenging agnostic online learning setting [Hazan al. 2012a Shamir and Shalev Shwartz, 2014). [Srebro and Shraibman (2005) study matrix completion with the max-norm, which behaves better under arbitrary distributions, namely for low-rank matrices, On + m) observations suffice.
Matrix completion and incoherence assumptions. A line of works in the matrix completion literature considered the goal of finding a completion of the ground truth matrix with low Frobenius
norm error guarantee [Candès and Recht 2009, Candès and Tao 2010 Keshavan et al. 2010, Gross
2011 Recht, 2011 Negahban and Wainwright [2012] Jain et al. 2013 Chen et al., 2020 Abbe
al. 2020]. Such guarantee strong but usually requires two restrictive assumptions on sampling distribution of observations and the ground truth matrix structure: (1) the sampling of observations is uniform across all entries, and (2) the ground truth matrix M satisfies some incoherence conditions. The incoherence condition is an assumption imposed on the singular vectors of M = UΣVT, which ensures the vectors ui, 0y's 's to be sufficiently spread out on the unit sphere. The main reason the incoherence condition is necessary in establishing meaningful guarantees in low-rank matrix completion that without such assumptions, there might exist multiple low-rank matrices that could explain the observed entries equally well but differ substantially on unobserved entries. When the incoherence condition satisfied, it implies that the observed entries capture enough information about the low-rank structure, making it possible to recover the original matrix with sufficiently well. However, uniform sampling and incoherence assumptions do not hold in many realistic scenarios.
Subsequently, to circumvent these restrictive assumptions, another line of work evaluates the general- ization error as an alternative metric for completion performance [Srebro et al.] 2004 Shamir and Shalev-Shwartz 2014]. To formalize, consider the task of completing M with an arbitrary observa- lion sampling distribution j over [m] x [n]]. This can be conceptualized as predicting a hypothesis mapping from the domain [m] [n] to the codomain [-1, 1]. The goal characterize the guarantees on the expected prediction error, quantified for given completion M as [E(L))=
- Mt) ))-
When j is the uniform distribution over [m]] x [n]. the generalization error bound translates to a guarantee over the average error across all entries. However, if is arbitrary (e.g. supported over
fraction of the entries), then no guarantee could be established for entries that lie in the complement of the support of p. This prohibits the use of A in settings where abstention is imperative.
Our work takes an alternative approach to this fundamental limitation in matrix completion. The focus of our work is to identify entries where we can predict with high confidence to guarantee low completion error weighted by evaluated confidence. We provide formulation of the problem, its convex relaxation, and efficient gradient-based online algorithm due to a formulation of the problem as an online two-player game.
Randomized rounding and semi-definite relaxations. For the efficient algorithm, the main anal- ysis technique we deploy is based on randomized rounding solutions of semi-definite programming, due to the seminal work of Goemans and Williamson [1995]. These were originally developed the context of approximation algorithms for MAX-CUT and other combinatorial problems. Here, we use this analysis technique for analyzing inner products of high dimensional vectors, but in a different context and to argue about a convex relaxation of continuous optimization problem.

---

Abstention in classification and regression. Abstaining from prediction has a long history in other learning problems such as binary classification Chow [195]]. There are several notable similarities. First, many of the algorithms work as ours does, by first fitting complete classifier and then deciding afterwards where to abstain [e.g., Hellman 1970. Goldwasser et al. 2020]. Second, numerous abstention models have been considered, including fixed cost for abstaining re.g,,Chow, 1957
Kalai and Kanade 2021]. as well as fixing the error rate and maximizing the coverage Geiffman and El- (1-Yaniv| 2017] as in our work, and fixing the coverage rate while minimizing the error [e.g.. Geifman and El-va 2019]. Third, there are algorithmic similarities, in particular the observation that worst-case performance guarantees do not depend knowing the underlying distribution Kalai and Kanade [202T]. Online models of abstention have also been considered [e.g., Li et al. 2011 For
detailed survey on selective classification see EI Yaniv and Wiener 2010
2 Problem Setup and Preliminaries
For a natural number n, let [n] = 21, n).
Consider a fixed set of indices X' = [m] x [n]]
throughout. Thus, in this paper x E X' is x (i,j) where i E [m],] E [nx]. The set of m n real-valued matrices is thus written as R* We will thus view matrix M over index set X function from X' + R, and for x E X. by slight abuse of notation denote by both M2 and M (x) the entry of M at index 2.
We focus on the squared loss in this paper, though it may be interesting to consider other loss functions in future work. Suppose v is a distribution over X, for matrices, M, M', we denote by {(v, M, M') der Exwr ((M(()))))) )²) we will also use the shorthand || M1 def E(v, M,M') M').
When E X is a sequence of elements of X' of length N, we denote by E(T, M, M') del N (M 2²) and the shorthand || - M
del ((T, M,).
2.1 Matrix Classes, Version Space and Generalization
Matrix Norms. Given a matrix M, we denote by || the maximum row norm of M. We denote by [|M]lmax the max-norm of M defined as,
M max
def
min TVT=M
|0||,,>0
|V
The trace norm of matrix M, denoted by [MM]ue is the sum of its singular values. The Frobenius norm a matrix M, denoted by || ftc is the square root of the sum of its squared entries.
We will restrict attention to matrices with entries in [-1, The following three classes of matrices with restrictions on respectively the rank, max-norm and trace-norm are of interest in this work. Formally, let K (M [[1,1]] 1 and define,
M def (Ma s k3} nR, MR (IIM) max S KKNK M def [IMI S SR
The standard assumption in matrix completion is that the target matrix is low-rank; however, most completion algorithms exploit convex optimization methods and optimize over max-norm or trace- norm bounded matrices. It is known that |M [II[mme max S / /rank(M) if M E [-1, 1ax [cf. Linial et al. 2007 Lemma 4.2] and it is easy to see that || ler S rank(M)
for M E [|1, Thus, ME C M and ME C _M kv/mn Hence, we will work with the latter two classes which satisfy the following lemma which is proved in Appendix A
Vk
Lemma 5. The classes, M and M are closed under negations and are convex.
Version Space. We define the notion of version spaces that are used in our key results. For a sequence 7 E N for any class of matrices M, a matrix M E M and 3 > O, define the version space around M of radius B based on T w.r.t. M as
V(M,B.T:M) = {M's E M L(T,M, M') < B}.
(3)
Intuitively, version space is the set of matrices in particular matrix class that are "close" to a given matrix with respect to T'.
5

---

Generalization Bounds. For a general class of matrices M, we define notion of sample complex- ity that will guarantee the proximity of empirical and population measures of interest for all matrices in the class; we denote this notion by sc(s, 6, M)..
Definition 6 (Sample Complexity). For E, and class of matrices M, denote by sc(e, 6, M). the sample complexity, to be the smallest natural number No, such that for any distribution μ over X' for S ~ NN,o, and for any fixed M E .M (possibly depending on S), with probability at least 1 8,
((S.M, M) - E(p, M, MM) SE.
sup MEM
If no such No exists, 6, def DC.
Bounds on the sample complexity for matrix completion can derived in terms of rank, max-norm and nrrce-oorm using standard results in the literature, and the fact that the squared loss is 2-Lipschitz and bounded by 4 when both its arguments take values in [-1, 17. In the proposition below, the
max-norm result follows from Theorem in (Srebro and Shraibman 2005 and the trace-norm result
follows from Theorem 4 in [Shamir and Shalev-Shwartz 2014].
Proposition 7. For the classes, MR M the following hold,
1. sc(e, 8, M. 0 ( (K² + n) + log 4))
2. (.(,,8.M)) O (3zz (rvm + n + log 1)).
It is worth comparing the two bounds in Proposition 7 above. Consider the matrix M* consisting of all I's from a matrix completion point of view this is particularly easy as every "user" likes every "movie". Note however that |M m and ||M' er = /mn. For this example, ignoring the dependence on E, 6, the sample complexity bound obtained using the trace-norm result would be O((m - n. m + +2), while that using max-norn would be O(m + n). In general. it is always the case that || ||+/ //rm S | so may seem that the bounds terms of trace-norm are weaker. However, there are matrices for which this gap can be large and the sample complexity bound terms of trace-norm shown to be tight in general (see (Srebro and Shraibman, 2005 Shamir and Shalev-Shwartz 2014] for further details).
2.2 Full Completion Problem (with Noise)
We now define the matrix completion problem with zero-mean noise, in fact matrix estimation problem in the noisy case. Let 'D be a distribution supported on X' x [-1, 1]: the results in the paper can all be easily extended when D is supported on X [- B). increasing squared error by a B factor. Let μ be the marginal distribution of D over X. Let Sxy = ((I,, )t)) be an iid sample drawn from DN Note here that 2, = (be- ji) denotes the index of the matrix and y the observed value. We let S = (æ1.... xxy) denote the sequence of x; 's from Sxy (with repetitions allowed); note that S distributed as μº Let M E [-1, 1| be the matrix where M. ED|Y|X (i.j)).
We say that M is an s-accurate completion of A1*, if E(u, M M) S.
Definition 8 (Full Completion Algorithm). We say that FullComp(SSx: e, 6, M)) a full completion algorithm with sample complexity SCFC(E, M) for M, if provided Sxy ~ D-N for some D over X' x 1, 1] with M E M, N SCFC(e, 6, M), FullCoop(SSxyee. 6, outputs M .M that with probability at least 8 satisfies, E(1, M M) S E.
The following result follows from [Srebro and Shraibman 2005 Shamir and Shalev-Shward 2014 (see also Prop.[7).
Proposition 9. There exists polynomial time (in mn/e) full completion algorithms for Miaa and M (e.g. ERM methods) with the following sample complexity bounds:
1. SCFC(E, 8, S.M.aaa) = =0 ( (K2 - n) + log :))
2. scMy (s, M. = O ( (rVm m n log t))
2.3 The Partial Matrix Completion Problem
Recall the definition of the (fractional) partial matrix completion in Eq. and Def. we will assume that full completion matrix M is already obtained. The focus of the present work
1 In this work,

---

is finding a completion matrix C' E {0,11* (or C' E [0, for fractional coverage) with large coverage. The coverage in both cases are defined as: |C] def Exex Cz, and a low loss, defined as:
((C, M M) def 1
E C. M2)² IC
Note that C E [0, 1 can be viewed as "fractional" set and we are overloading the notation to allow that. Such fractional coverage can be randomly rounded to set whose size is within 1 of [C]. In ideal world, we would have at most loss measured over the cells we complete as defined above, and large or even full coverage |C| = mm..
Note that although the requirement in the optimization problems in Eq. (I) and Def. Tis is to guarantee E(C, M M) S s, as we don't ' know M the only guarantee we have by using full completion some version space,
algorithm (and generalization bounds) is that (with high probability) M say V, centered at M. So we actually show stronger guarantee that, sup {(C, M, M) S
A second observation is that if M is version space around M, then by convexity of the matrix classes, the matrix (M MM/2, must be in some version space, say Vo. centered around the zero matrix, Ox- Thus, we will actually find a C' that guarantees, &(C,, M, 0x) S for every M E Vo- This means that for maximizing coverage our algorithm has the remarkable property only need to know the locations of the revealed entries as indicated by S.
Section presents a computationally inefficient but statistically superior algorithm in terms sample complexity for the coverage problem and its consequences for partial matrix completion. Section 4 presents a computationally efficient algorithm at the cost of a slightly worse sample complexity when using the class M
3 An Inefficient Algorithm
The main novelty in the partial matrix completion problem is that of finding an optimal coverage, defined as the matrix C in the formulation in Def. In this section we give an (inefficient) algorithm for finding the optimal coverage, and the generalization error bounds for Partial Matrix Completion that arise from it. the next section we give an efficient approximation algorithm for doing the same, with slightly worse sample complexity bounds and more complex analysis. This differs substantially from prior work on abstention classification and regression [Kalai and Kanade, 2021 optimal solution
where the
be found in polynomial time.
Let C E J0, 1|x be target confidence matrix. For such C. we will denote by the probability distribution where (x) C=/I|Cila for x E X. Let yr8 be sample obtained from the target distribution We output a C which is an optimal solution to the following optimization problem, inspired by similar problem studied by Kalai and Kanade [202T] for classification with abstention.
Parameters and inputs : S,
maximize
||C'|]2 subject to C' [0, 1] and
(4)
VM V(0x, ((v,, S
Algorithm
1: Inputs: Sxy ((rr, v.)) ~ DN e, 6, M, FullComp (cf. Def.
2: Obtain M E M using FullComp(Sxx. e/4, 543,
3: Obtain C using 4P with y def del
e/4. g E/8. S (21, 2..,,, AN) from Sxy.
4: return (M, C).
MP 4 defines a family of optimization problems; we will typically use M to be Miax or M!r The above optimization problem in fact linear program. The only unknowns are C2 for X. However, the set of constraints is infinite and it is unclear how separation oracle for the constraint set
7

---

may be designed. Such an oracle could be designed by solving the following optimization problem:
max E(UC, M, 0x)-
(5)
MEV(0x.9,S.MM
This optimization problem requires maximizing quadratic function, and we prove it to be NP-hard with the additional PSD and symmetric constraints in Appendix[A.2
The following result subsumes Corollary We defer the proof of this theorem to Appendix A as the proof is similar to that of our efficient algorithm in the next section.
Theorem 10. Let M be either M or M Let 'D be distribution over X x [-1.1], I the marginal of 'D over X, pmax maxi, IP ((), is sampled). Suppose that M defined (i,j)l satisfies that M* E M. Furthermore, suppose that Sxy ~ DD and that FullComp is full completion algorithm as in Defn. g Then, provided N 2 max(scFc(E/44 8/3,M), sc,s sc(s/8, 0/3, M (M, C)) output by Alg. it holds that:
as Mij = Exx,yr>DDD
1. ||||| 2 1/ Mmax
1 Σ
2.
C.MM, 2 Se.
|C
ZEX
4 An Efficient Algorithm
In this section, show how the result from Proposition [4 can be achieved using an efficient algorithm at a modest cost in terms of sample complexity when using the matrix class MMax In partieular, we consider the optimization problem defined in MP where the constraint || S Y for all M V(Ox,, 3, S; MM from MP 4 is replaced by Ex-ve [Mz]] S 7. The efficiency comes from the fact that we can now implement a separation oracle for the constraint set by solving, for given C, the problem,
max MEV(O S.S.M
BeNUe [Ma].
Mathematical program is a convex optimization problem since the constraint set is convex and the objective function is linear. However, it is not immediately clear how this relaxed optimization problem relates to the original, which the main technical contribution of this section.
Parameters and inputs :,, S.M.
maximize ||C||| subject to e [0, and VM E 1,00,,,5;MM Eewve [Ma] S
(6)
Algorithm 2 (Elficient) Offline Algorithm for Partial Matrix Completion
1: Inputs: Sxy ((1,, ye ) DN, FullComp (ef. Def.
8) e, 6. 2 K2), 8/3, MBax).
2: Obtain M E _M using FullComp(Sxy, //m
Obtain O using MP with y <2(2 B def
def
e² 128 K2), S (I1, (2... from Sxy.
4: return (M, C).
The following result subsumes Corollary
Theorem 11. Let be a distribution over X [-1,1], I the marginal of over X, Pmax maxi, IP, ((, ji is sampled). Suppose that M*, defined Mij = -E(XyY)=D = (i,j) sat- isfies that M E MMRax. Furthermore, suppose that Sxy DN and that FullComp is a full completion algorithm as in Defn. g Then, provided N max max{scrc(E" (orrc("//<>>>33" K2), 8/3, M sc(E? (8x= K2), 5/3, MB)x)) }r for (M, C`) output by Alg. 2 it holds that:
1. ||C|| 1/ pmax.
1
2.
Σ
Ca -M)) S.
||C||

---

Online Setting
The previous section introduces the offtine setting for the partial matrix completion problem. In Appendix B we describe the online version of the problem, which is motivated by two important considerations. First, in many applications, the observation pattern is more general than a fixed distribution. It can be a changing distribution or be comprised of adversarial observations. Second, online algorithm incrementally updates the solution via iterative gradient methods, which is more efficient than the offline methods. For space considerations, details are deferred to Appendix B which contains the setting, definitions, algorithm specification, and main results, and Appendix C which details the proofs. In particular, the online algorithm, called Online Dual Descent (ODD), is described in Algorithm [] and its regret guarantee in Theorem T8 The online regret guarantee implies the statistical learning guarantees of the previous sections when the support size is a constant fraction of the full matrix, and this implication is spelled out preciscly in Corollary 22
6 Experiments and Implementation
The MovieLens dataset (Harper and Konstan 2015)) consists of, among other data, a set of users with their rankings of set of movies. It is common benchmark for matrix completion because some of the rankings are missing, and one can make predictions on the rankings of user preferences.
We used the dataset differently, aiming to test online algorithm on generating satisfying confidence matrix. The experimental procedure is outlined as follows: we used training data from 250 users and their ratings on 250 movies, giving us total of 5189 completed samples from the incomplete matrix of size 250 x 250. We ran our algorithm, ODD (Algorithm 3). to get a confidence matrix C. In parallel, we used another standard matrix completion tool, fancy iicctte (Rubiintteyn and Feldman 2016). fill in the missing entries of the matrix and obtain completion My. After C and M are obtained, we reveal the true ratings at the missing entries using the validation set and computed the mean squared error of the predicted rating and true rating each entry. The following plots show the distribution of the mean squared error with respect to the confidence score C assign at the particular entry.
Koerage ETE
6.
60
2.6
00
022
Figure 2: (a) ODD heuristic on 250 x 250 user-movie rating data from the MovieLens Dataset. Squared error in entry-wise prediction and entry-wise confidence level estimated by the ODD heuristic. (b) The average squared error over various confidence levels suggests that a higher confidence level is correlated with lower squared error.
7 Conclusion
In this work define the setting of partial matrix completion, with our high-level contributions outlined as the following:
A new framework. We propose a new framework called partial matrix completion. In this problem, one is given possibly noisy observations from low-rank matrix, and the goal identify entries that can be predicted with high confidence. The partial matrix completion problem answers two key questions:
Based possibly noisy samples from an arbitrary unknown sampling distribution μ., how many entries can be completed with & error?
How can we efficiently identify the entries that can be accurately completed?

---

When the underlying matrix has low rank k, we show that it is possible to complete a large fraction of the matrix using only (kk(m + r)) observations while simultancously guarantecing high accuracy over the completed set. We then study the complexity of identifying the optimal completion matrix. We show that a naive mathematical programming formulation of the problem is hard. However, we propose relaxation that gives rise efficient algorithms, which results in a slightly worse dependence on & for the sample complexity. These guarantees are outlined both in Corollary Lnd and Theorem 10 and Theorem I for their more general versions.
Corollary 3
Online game formulation. Furthermore, we consider the partial matrix completion problem in the online setting, where the revealed observations are not required to follow any particular fixed distribution. The goal henceforth to minimize regret, the gap between the algorithm's performance and the single best decision in hindsight. This is more general setting, as when imposed with distribution assumptions, regret guarantees in online learning algorithms naturally translate to statistical guarantees.
Our proposed online partial matrix completion algorithm is derived from an online repeated game. The version space the set of all valid completions with low generalization error. High confidence should be assigned to entries where all completions in the version space are similar. Therefore, we formulate the problem as two-player online game. One player iteratively updates confidence matrix, and the other learns the version space. We gave an iterative gradient-based method with provable regret guarantees and concluded with preliminary experimental evidence of the validity of our framework.
Acknowledgements
Elad Hazan acknowledges funding from the Office of Naval Research grant N000142312156, the NSF award 2134040, and Open Philanthropy. This work was done in part when Clara Mohri was visiting and supported by Princeton University.
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.
Emmanuel J Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foun- dations of Computational mathematics, 9())7717-772, 2009.
Emmanuel Candès and Terence Tao. The power of convex relaxation: Near-optimal matrix
completion. IEEE Transactions on Information Theory, 56(5):0053-200888 2010.
Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, and Yuling Yan. Noisy matrix completion:
Understanding statistical guarantees for convex relaxation via nonconvex optimization. SIAM journal on optimization, 30(4):3098-3121, 2020.
Chi-Keung Chow. An optimum character recognition system using decision functions. IRE Transac- fions on Electronic Computers, 4:247-254, 1957.
Ran El- -aniv and Yair Wiener. On the foundations of noise-free selective classification. Journal of Machine Learning Research, 11(53):1605-1641 2010. UKLhttpp://jmrr.or////e
vi hal/el-yanivll htmll.ll..llmmm.mm
Yoav Freund and Robert E Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1-2):79-103 1999.
Yonatan Geifman and Ran El-Yaniv. Selective classification for deep neural networks. Advances in neural information processing systems, 30, 2017.
Yonatan Geifman and Ran El-ia..v. Selectivenet: A deep neural network with an integrated reject option. Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 2151-2159. PMLR, 2019.
10

---

Michel X Goemans and David P Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6); 1115-1145, 1995.
Shafi Goldwasser, Adam Tauman Kalai, Yael Tauman Kalai, and Omar Montasser. Selective classification algorithms provably robust arbitrary adversarial examples. In Advances Neural Information Processing Systems, 2020.
David Gross. Recovering low-rank matrices from few coefficients in any basis. IEEE Transactions on Information Theory, 57(3):1548-155 2011.
Martin Grötschel, László Lovász, and Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1(2):169-197, 1981.
F. Maxwell Harper and Joseph A. Konstan. The movielens datasets: History and context. ACM Trans. Interuct. Intell. Syst., 5(4), dec 2015. ISSN 2160-6455. doi: 10.1144//827872.
Johan Hastad. Clique is hard to approximate within n/sup 1-/spl epsiv. In Proceedings of 37th Conference on Foundations of Computer Science, pages 627-636. IEEE, 1996.
Elad Hazan, Satyen Kale, and Shai Shalev-Shwariz. Near-optimal algorithms for online matrix prediction. In COLT, pages 38.1 3-.1-38.11 13, 2012a.
Elad Hazan, Satyen Kale, and Shai Shalev-Shwartz. Near-optimal algorithms for online matrix prediction. In Conference on Learning Theory, pages 38-1. JMLR Workshop and Conference Proceedings, 2012b.
Elad Hazan et Introduction to online convex optimization. Foundations and Trends@ in Optimiza- tion, 2(3-4):157-322 2016.
Martin E. Hellman. The nearest neighbor classification rule with reject option. IEEE Transactions on Systems Science and Cyhernetics, 6(3):199-185, 1970. doi: 10. 10.10097SSSC.19903333339
Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi. Low-rank matrix completion using alternating minimization. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 665,674,77 2013.
Adam Kalai and Varun Kanade. Towards optimally abstaining from prediction with ood test exam- ples. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 12774-12785. Curran As- sociates, Inc., 2021. URL httpp::://ppocseeett 6a22677d6aa 75133377744455554444 71lc:/6666cccaaaa444454222222222 Paper. pdf
neuri ps cccppaper/2221/111..
Raghunandan Keshavan, Andrea Montanari, and Sewoong Oh. Matrix completion from a few entries. IEEE transactions information theory, 5666))2980-2998, 2010.
Lihong Li, Michael L Littman, Thomas J Walsh, and Alexander L Strehl. Knows what it knows: framework for self-aware learning. Machine learning, 82(3):399-443, 2011.
Nati Linial, Shahar Mendelson, Gideon Schechtman, and Adi Shraibman. Complexity measures of sign matrices. Combinatorica, 27(4):439 2007.
Mehrdad Mahdavi, Rong Jin, and Tianbao Yang. Trading regret for efficiency: online convex optimization with long term constraints. The Journal of Machine Learning Research, 13(1): 2503-2528, 2012.
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.
Benjamin Recht. A simpler approach to matrix completion. Journal of Machine Learning Research, 12(12), 1011.
Alex Rubinsteyn and Sergey Feldman. fancyimpute: imputation library for python, 2016. URI
https: ttte://giite /github. com//Lkaand/faaeyinnnnno

---

Ohad Shamir and Shai Chalev-Shwartz Matrix completion with the trace norm: Learning, bounding. and transducing. Journal of Machine Learning Research, 15(1):3401-3423, 2014.
Nathan Srebro. Learning with Matrix Factorizations. PhD thesis, Massachusetts Institute of Technol- ogy, 2004.
Nathan Srebro and Adi Shraibman. Rank, trace-norm and max-norm. In International Conference Computational Learning Theory, pages 545-560. Springer, 2005.
Nathan Srebro, Noga Alon, and Tommi Jaakkola. Generalization error bounds for collaborative prediction with low-rank matrices. Advances In Neural Information Processing Systems, 17, 2004.
Manfred K Warmuth. The blessing and the curse of the multiplicative updates. In International Conference on Discovery Science, pages 382-382. Springer, 2010.
12


Reviews:
[{"review_id": "dGcRpQVoWn", "reviewer": "Reviewer_Hbwc", "summary": "The authors discuss the Partial Matrix completion and present an algorithm for completing a large subset of the entries with high confidence. They also aim to find the number of entries that can be completed (coverage) with a small error where the samples are from an unknown sampling distribution.", "questions": "1. How did the authors select the data? How did they decide which user and which items to consider? Which exact Movie Lens dataset is used? There are multiple versions of the same dataset. Some further clarification would be appreciated.\n\n2. What are some practical domains that the presented algorithms can be useful? How is the time complexity reflected in the larger experimental settings? How much time does it take for your algorithm to run to find the coverage?", "limitations": "No direct negative societal impact exists. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Identifying the entries which have high confidence without the incoherence assumption is an important problem and the problem is described well by the authors, including the relevant citations.\n\n- Two alternative methods are presented. An inefficient (but stronger) algorithm, as well as an efficient (but worse sampling bounds), for finding the optimal coverage for partial matrix completion. Their limitations and disadvantages are discussed honestly. (i.e. The inefficient algorithm requires solving a quadratic function as an optimization function which is also shown to be NP-hard. ) \n\n", "weaknesses": "- The online formulation of the \"partial matrix completion\" is said to be one of the main contributions of the paper however it is only discussed in the appendix. It would be nice to see the main contribution in the main paper. \n- Experimental support is missing significantly. The experiments can be enriched to support the claims of the authors, further baselines are missing. Time analysis is missing. Performance could be highlighted and leveraged more. \n- The guarantees are discussed before introducing the algorithms.\n- The definition of \"Partial\" could have been emphasized more, since the paper is directly built on that term.\n\nMinor :\n\n- The Figures are not numbered and not addressed in detail. \n- The organization of the paper could be further adjusted. Some terms are used before they were defined, the styling is not appropriate which makes it difficult to follow the paper. i.e. Algorithm 1, \"FullComp\", or the styling of the function (3).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for taking the time to read and review our paper. We note that despite the score you gave us, your comments are generally positive, and you recognize the contribution and soundness of our work. Out of the four weaknesses you pointed out, three seem to be stylistic issues, and we are happy to try to improve the presentation based on your suggestions. We will address your concerns and hopefully these responses can give you a chance to reevaluate our work! \n\n\nWeaknesses:\n\nMajor: \n\n1. The online formulation of the \"partial matrix completion\" is said to be one of the main contributions of the paper however it is only discussed in the appendix. It would be nice to see the main contribution in the main paper.\n\n**Response**: if the paper is accepted, we will have an additional page for the camera ready version which we will use to discuss the online version in the paper body.  \n\n2. Experimental support is missing significantly. The experiments can be enriched to support the claims of the authors, further baselines are missing. Time analysis is missing. Performance could be highlighted and leveraged more.\n\n**Response**: Our contribution is mainly conceptual and theoretical, and therefore the experimental section was added to elucidate and support the framework and theory, rather than to give an extensive evaluation or comparison as in applied papers. Significantly more experiments would thus be out of scope, but we are very happy to compare to other methods (we don’t know any since it’s a new framework, please refer us if you have anything in mind), or add more experiments that would help explain the framework, can you please suggest such? We want to emphasize that there exists no baseline we can compare to as partial matrix completion is a completely new framework, which is part of the novelty of our work. This is also why we use a standard matrix completion package to compare the squared error of that package with the test values with respect to our obtained confidence matrix. We are not sure what you mean by time analysis.\nCan you elaborate on an experiment that would help the reader understand the main concepts we introduce? We would be happy to add any other evaluation, time permitting (space limitations would mean this would go in the appendix in any case, since we have so many other contributions in the paper).\n\n3. The guarantees are discussed before introducing the algorithms.\n\n**Response**: Thank you for the suggestion. We chose to qualitatively discuss the guarantees first because we felt it was more intuitive. It is generally common to present the guarantees of an algorithm before its implementation details, however, if you feel that the inputs or the setting is not clear early enough, please let us know. \n\n4. The definition of \"Partial\" could have been emphasized more, since the paper is directly built on that term.\n\n**Response**: Thank you for the suggestion. We have added a sentence emphasizing this in the introduction. \n\n\n**Response to minor weaknesses**: Thank you for your suggestions. We will change according to your suggestions. \n\nQuestions:\n\n1. How did the authors select the data? How did they decide which user and which items to consider? Which exact Movie Lens dataset is used? There are multiple versions of the same dataset. Some further clarification would be appreciated.\n\n**Response**: We use the MovieLens 100K dataset. We use a 250x250 submatrix from the 943x1682 matrix. We chose to select the MovieLens dataset because it is a classic dataset used for matrix completion problems. We use a simplified version of the ODD as outlined in Appendix D. \n\n2. What are some practical domains that the presented algorithms can be useful? How is the time complexity reflected in the larger experimental settings? How much time does it take for your algorithm to run to find the coverage?\n\n**Response**: While our results are mainly theoretical, we believe they have meaningful applications as well. Specifically, the online algorithm is designed to be efficient and can be used to evaluate to what extent entries can reliably be completed in a matrix, which is an important problem in any scenario where decisions should only be made if there is high confidence. For example, in datasets which pertain to hospital patients and their features, one would only want to make predictions for patients which can be made with high confidence. Even in low stakes settings, such as movie recommendations, companies, such as Netflix seem to be already abstaining from making predictions on some movies today, as discussed in the paper. This is only a first step and we are hoping later papers will find even more applications.\n \n\n\nIn light of our changes and rebuttal, would you consider adjusting your score? We are more than happy to answer any further questions. \n"}, {"review_id": "dvpmyeUF7q", "reviewer": "Reviewer_n6bT", "summary": "This paper considers a twist on the standard matrix completion problem where one is required to only\ncomplete a subset of entries (not the whole matrix) that includes the entries shown. This allows them to consider\nsubstantially more observation patterns unlike the standard missing-at-random response. In this context\nthe paper makes the following contributions:\n\n1. Propose a computationally-inefficient algorithm that with high probability recovers a subset of entries\nthat is at least as large as the revealed set, with low target accuracy.\n2. Develop a computationally-efficient relaxation of this algorithm that has worse statistical dependence\non the target accuracy than the inefficient algorithm.\n3. Provide an online variant of the algorithm that is iterative/gradient based that applies to adversarial\nonline matrix completion.\n", "questions": "1. The algorithmic viewpoint here is to separate the coverage computation from the completion method. This is advantageous in some ways (notably the generality and e.g. obtaining an essentially free proof of the risk), but potentially disallows using structure in the completion. E.g. in the causal inference setting of (say) row $1$ being partially revealed from columns $1, 2\\ldots, K \\leq \\text{dim}(M)$.\n2. What is $\\mu_\\max$? It is defined in the appendix (and easy to guess) but is not in the text (unless I missed)\n", "limitations": "No significant limitations, addressed previously.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "In my view the main strengths of the paper are:\n\n1. Posing an interesting partial matrix completion setting \n2. Leveraging existing matrix completion work and separating the problem of matrix completion from that of obtaining good coverage (possibly fractional)\n3. Generalizing to the online and adversarial setting \n\n", "weaknesses": "Some weaknesses, though these are better understood as interesting avenues for future work:\n\n1. The proposed algorithms provide noisy completion even when the observations are noiseless (i.e. no obvious notion of completion to the inherent noise level). \nThis does seem inherent to the algorithm/proof techniques used here, it is unclear to me that this can be overcome here. \n2. There is an obvious sample complexity gap between the efficient and inefficient algorithms. Is this inherent, or a result of the proof technique here?\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time and efforts in reading and reviewing our work! Here are our responses to your concerns:\n\nWeaknesses:\n\n1. The proposed algorithms provide noisy completion even when the observations are noiseless (i.e. no obvious notion of completion to the inherent noise level). This does seem inherent to the algorithm/proof techniques used here, it is unclear to me that this can be overcome here.\n\n**Response**: This is correct. It is currently inherent to our algorithm and proof techniques.  It is also interesting to us to explore whether we can have an algorithm that completes missing entries without noise when the observations are noiseless. \n\n\n2. There is an obvious sample complexity gap between the efficient and inefficient algorithms. Is this inherent, or a result of the proof technique here? \n\n**Response**: Great point, yes: we conjecture that the computational hardness of the nonconvex formulation is inherent, and it may be computationally hard to get the optimal statistical complexity. Such results are known in, for example, sparse recovery (LASSO), and it would be very interesting to research this direction further. \n\nIn general, yes, there is a lot more investigation to be done here, and these are good points. We believe we have only initialized research in this direction. We’ll add it to the future works section.\n\nQuestions:\n\n1. The algorithmic viewpoint here is to separate the coverage computation from the completion method. This is advantageous in some ways (notably the generality and e.g. obtaining an essentially free proof of the risk), but potentially disallows using structure in the completion. E.g. in the causal inference setting of (say) row $1$ being partially revealed from columns $1,2,\\dots,K\\leq\\mathrm{dim}(M)$.\n\n**Response**: Note that the offline algorithms do separate the coverage computation from the completion method, but the online algorithm does not as clearly do this through online computation of a version space for the completion. Thus, in effect we are showing that both can be done.\n\n2. What is $\\mu_{\\max}$? It is defined in the appendix (and easy to guess) but is not in the text (unless I missed). \n\n**Response**: Yes, $\\mu_{\\max}$ is the maximum entry over all entries in $\\mu$. We will add this definition earlier.\n"}, {"review_id": "fQA4dckFMj", "reviewer": "Reviewer_PBAT", "summary": "Typical matrix completion methods aim to recover the whole matrix, based on strong conditions on the matrix itself as well as the sampling distribution. In contrast, this paper proposes a method to complete a subset of the entries with high confidence, which can bypass the need of these conditions. More specifically, the proposed approach builds on top of existing matrix completion methods, and identifies which completed entries can be recovered well. A computational efficient algorithm (as well as an inefficient one) is proposed. Corresponding theoretical guarantees are also provided.", "questions": "- Corollary 2 (Section 1.1): is this $|C|$ the cardinality or the sum as defined later in Section 2.3?\n- The explanation after \"The Partial Matrix Completion Problem\" is unclear. In line 227, what is $C$ ? Based on the explanation, I think we can guarantee that for $C=\\mu$ , but I am not sure if it works for all $C$ .\n- The authors specify \"the partial matrix completion problem\" in line 223 as finding a *specific* $C$ . I am curious if the proposed algorithms has any guarantee about finding such $C$ defined in 223. Note that the theoretical results (Theorems 8 and 10) provide guarantee in terms of $\\frac{1}{C}\\sum_{x\\in\\mathcal{X}}C_x(\\hat{M}_x - M_x^\\star)^2$ . This type of guarantee looks good to me. I just want to see the relationship with the *target* as specified in \"The Partial Matrix Completion Problem\".\n- How does misspecification in rank (in the MC step) affect the performance  of the proposed method?\n- How to choose the tuning parameters in practice?", "limitations": "The authors do not provide an explicit discussion on the limitations of their work. I think more extensive numerical experiments would improve this work. I am particular interested in how the proposed methods perform under different sampling distributions (ranging from some easy settings where completion of the whole matrix is possible, to ill-posed settings.)", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- This paper studies an important and interesting problem, as certain necessary conditions (on matrix structure and sampling distribution) required for matrix recovery are not always guaranteed to hold. In such ill-posed settings, partial guarantee is useful. I am not aware of any prior work for partial matrix completion, so it is a novel contribution to this area.\n- This work provides strong theoretical guarantee for the proposed methods.", "weaknesses": "The authors define the \"Partial Matrix Completion Problem\" (Line 223) as finding a specific $C$; but the theoretical guarantee does not seem to align directly.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time and efforts in reviewing our work! Here are the resonses to your concerns:\n\nWeaknesses:\n\n1. The authors define the \"Partial Matrix Completion Problem\" (Line 223) as finding a specific $C$; but the theoretical guarantee does not seem to align directly.\n\n**Response**: Our definition is not saying that there is a unique $C$ in particular which satisfies the problem. Hence, we find such a $C$ which is sufficiently good. Although our result is not strictly maximizing $|C|$, we provide a meaningful lower bound guarantee. Later in the online section we even give an agnostic guarantee: we compete with the best C, even though such a (optimal) C may have high loss. This is common in online and agnostic learning. \n\nQuestions:\n\n1. Corollary 2 (Section 1.1): is this $|C|$ the cardinality or the sum as defined later in Section 2.3?\n\n**Response**: Note that in Section 1.1, these two are the same as $C\\in \\\\{0,1\\\\}^{m\\times n}$. We will make sure to clarify this. \n\n2. The explanation after \"The Partial Matrix Completion Problem\" is unclear. In line 227, what is $C$? Based on the explanation, I think we can guarantee that for $C=\\mu$, but I am not sure if it works for all $C$.\n\n**Response**: $C$ in this case is the solution to problem (2) in line 223. The guarantees are spelled out in Theorem 8 and 10. This is just a summary of the result. We will make sure to clarify this. \n\n3. The authors specify \"the partial matrix completion problem\" in line 223 as finding a specific $C$. I am curious if the proposed algorithms has any guarantee about finding such $C$ defined in 223. Note that the theoretical results (Theorems 8 and 10) provide guarantee in terms of \n\n$\\frac{1}{C} \\sum_{x \\in {\\cal X} } C_x (\\hat{M}_{x} - M^*_{x})^2$.\n\nThis type of guarantee looks good to me. I just want to see the relationship with the target as specified in \"The Partial Matrix Completion Problem\".\n\n**Response**: Note that  $\\frac{1}{C} \\sum_{x \\in {\\cal X}} C_x (\\hat{M}_{x}-M^*_{x})^2$ is exactly the constraint in line 223 defined in line 218. Yet it is interesting to explore other types of guarantees.\n\n4. How does misspecification in rank (in the MC step) affect the performance of the proposed method?\n\n**Response**: While we haven’t explored this, our conjecture is that the theoretical guarantee should translate in the natural way (scale with the rank/complexity measure scale in the guarantee). In practice, we have not explored this yet. It is interesting to explore this direction.\n\n\n5. How to choose the tuning parameters in practice? \n\n**Response**: Possible tuning methods include hyperparameter sweep, and it is possible that more sophisticated methods can help, such as hypergradient descent and meta optimization. \n\nLimitations:\n\nThe authors do not provide an explicit discussion on the limitations of their work. I think more extensive numerical experiments would improve this work. I am particular interested in how the proposed methods perform under different sampling distributions (ranging from some easy settings where completion of the whole matrix is possible, to ill-posed settings.) \n\n**Response**: We agree and thank the reviewer for  this suggestion—we will attempt to do this by the final version of the paper (or in future work, if that’s needed).\n"}, {"review_id": "YYrNeMyxwk", "reviewer": "Reviewer_wLHP", "summary": "This paper introduces the learning problem of simultaneously estimating an unknown ground truth matrix based on the observed entries and providing a set of weights/confidence scores for each unknown entry with two properties: (1) the RMSE, weighted by the confidence scores, satisfies generalization bounds analogous to the standard results in the classic setting, (2) the confidence scores have sufficient *coverage*, i.e. sufficiently many entries have sufficiently high confidence scores. Thus, in light of the existing distribution-free results, this can be viewed as a targeted joint estimation of the ground truth matrix and the ground truth sampling distribution over entries. The main theorems in this first direction are Theorems 8 and 10: \n\nTheorem 8 shows that Algorithm 1, which relies on the intractable optimization problem \"MP 3\", achieves a sample complexity similar to existing state-of-the-art distribution-free results for both the max norm and the trace norm constraints, with the coverage of the matrix of confidence scores $C$ being at least as large as that of the ground truth sampling distribution. The key aspect of the algorithm is to solve the dual problem involved in MP3, which utilizes the following powerful observation (cf. lines 534 and 227-230): if a matrix of confidence scores $C$ guarantees that any matrix with small empirical $L^2$ norm (over the i.i.d. training sample) must also have small weighted $L^2$ norm w.r.t. $C$ will also guarantee that any matrix with small empirical $L^2$-deviation from a ground truth matrix will also have small $C$-weighted $L^2$ distance to the ground truth matrix. This simple observation is enough to ensure that the construction of the confidence scores $C$ only depends on the sampled entries, and not on the observed ratings. The algorithm from Theorem 8 is shown to be NP-hard. \n\nTheorem 10 shows a slightly worse guarantee  ($1/\\epsilon^4$ instead of $1/\\epsilon^2$ due to going back and forth between $L^2$ and $L^1$ losses via Jensen's inequality as well as novel results) for an improved algorithm which replaces the $L^2$ loss in MP3 by a linear loss function. The proof of the result relies on a remarkable and original result which is proved in the main text via the probabilistic method (c.f. Proposition 11). The algorithm is tractable, but the result only applies to the max norm, not the trace norm. \n\nIn the next part of the paper (i.e., Appendix B which is naturally part of the main paper and whose own appendix is Appendix C), the authors study the online learning setting, providing sublinear regret bounds for both algorithms in Theorems 18 and 19 (summarized in Corollary 17). Those results are valid under an adversarial sampling regime and apply to regret as defined by the loss function $h_t$ defined in line 656. The results are more favorable in terms of dependence on the size of the matrix than the results of [1], but not immediately comparable due to subtle differences in the definition of regret. Note that function $h_t$ is not uniquely defined. Rather, it has two possible definitions based on the choice of function $H(C)$, which lead to a different treatment (c.f. point 1.a and 1.b in lines 658 to 660). The proof techniques are a mix of techniques modified from [1] and [2] and more completely original methods (e.g. the proof of Theorem 23 (which is an analog of Proposition 11 in the online context, and the proof of Lemma 25). \n\nFinally, the authors empirically evaluate their method on a small-scale semi-synthetic dataset consisting of $250$ most popular users and items in MovieLens by comparing the 'confidence level' with the test error. Although it is not explicitly stated, the confidence level most likely refers to $\\sum_{x\\in\\mathcal{X}} C_x$ (the sum of all the confidence scores at all entries). \n\n\n\n\n\n\n========Post-rebuttal========\n\nThe authors have satisfactorily addressed most of my concerns, and I am still convinced that the paper is very high quality and I will keep my score. For the benefit of the community, I hope the authors polish the issues raised.  \n\n\n=========\n\n\n\n**References**\n\n[1] Elad Hazan, Satyen Kale, and Shai Shalev-Shwartz, \"Near-optimal algorithms for online matrix prediction\", COLT 2012. \n\n[2] Elad Hazan et al. \"Introduction to online convex optimization.\" Foundations and trends in optimization, 2016. \n\n[3] Nathan Srebro, \"Rank, Trace-Norm and Max-Norm\", COLT 2005. \n\n[4] Prateek Jain, Soumyabrata Pal Online Low Rank Matrix Completion. ICLR 2023.\n\n\n[5]  Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, Yuling Yan. Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization.  SIAM journal of Optimization, 2020.", "questions": "In decreasing order of importance: \n\n**1.** The proof of NP-hardness contains some confusing elements for me. I apologize in advance if this is due to my lack of familiarity with the related results: \n\n**1.a** I  don't understand why problem (7) is equivalent to problem MP 3. Indeed, I can't see why the PSD condition appears. I have a feeling this comes from the ($\\beta$,$\\tau$) decomposability, but there is definitely an argument missing.\n\n**1.b** The first argument in the \"soundness\" part which states that we can assume $X$ is rank one w.l.o.g. I also don't understand this argument: why is it the case that the matrix $\\tilde{X}$ achieves value $k^2$ if the matrix $X$ does. This is absolutely not obvious to me. \nI agree with the rest of the proof assuming this is correct.\n\n\n**2** Can you clarify whether the expectation in the equation on line 603.5 (bottom of page 18) refers only to the randomness in the choice of the loss function $h_t$ (which is assumed to be \"stochastically i.i.d.). In that case, shouldn't there also be an expectation on the right hand side in front of the regrets? \n\n**2.2** The lengthy discussion at the beginning of Section B culminating in the equation from line 603.5 seems to mostly justify the validity of the Game-Regret (see line 679) as a measure of performance of the algorithm by linking it to the minimax regret. Why not apply the result from line 603.5 and make a self-contained theorem which applies to the minimax regret in the paper's setting? \n\n\n**3** On lines 786-788, why do you assume $T\\geq \\tilde{O}(m+n)$ (first) and then $T=\\tilde{O}(m+n)$ (also as in the statement of the lemma) rather than $T\\geq O(m+n)$? Firstly, the result is only interesting if the condition is a lower bound on $T$ only (I am confident this holds but it is not stated as such. Secondly and more importantly, it doesn't seem like the tilde is required since there are no log terms. In particular, if we interpret the tilde notation as possibly involving dividing factors of log terms (since we want a lower bound on $T$ not an upper bound),  the second to last inequality on the sequence of inequalities in line 788.5 could be incorrect (though the last inequality with $\\tilde{O}(\\alpha \\sqrt{T})$ remains correct where the log terms are $\\log(mn)$.\n\n\n**4** Could you include a more detailed comparison to the existing results in [1] and [4]? \n\n\n\n\n**References**\n\n[1] Elad Hazan, Satyen Kale, and Shai Shalev-Shwartz, \"Near-optimal algorithms for online matrix prediction\", COLT 2012. \n\n[2] Elad Hazan et al. \"Introduction to online convex optimization.\" Foundations and trends in optimization, 2016. \n\n[3] Nathan Srebro, \"Rank, Trace-Norm and Max-Norm\", COLT 2005. \n\n[4] Prateek Jain, Soumyabrata Pal Online Low Rank Matrix Completion. ICLR 2023.\n\n[5]  Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, Yuling Yan. Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization.  SIAM journal of Optimization, 2020.", "limitations": "1. The experiments section is very preliminary. No attempt is made to evaluate the online learning setting or to compare with other baselines. This is also an extremely small artificial dataset most likely constructed to be able to run experiments very fast on a laptop. \n\n2. See \"weaknesses\".", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "This is an outstanding contribution:\n\n1. To the best of my knowledge, the results presented in this paper are **highly original and impactful**. Many of the proofs require significant innovation and are non-trivial. The setting presented in the first part of the paper is an exciting new paradigm and the observations implicit in the results are very deep. I find it especially fascinating how the function class restriction on the set of predicted matrices is enough to allow us to construct the matrix $C$ (which is, after all, an estimate of the sampling distribution) without making any explicit assumptions or restrictions on the class to which the sampling distribution belongs. This is presumably because there is some implicit equivalence relation between distributions in terms of how their corresponding generalization gaps are evaluated on ground truth matrices inside a restricted class. \n\n2. The online learning results are of great theoretical and practical importance and are **highly nontrivial** to prove.", "weaknesses": "Note: Overall, this is still an **extremely interesting and impactful paper** despite the limitations in terms of clarity described below.\n\n\n**Main weaknesses/Summary:**\n My main problem with the paper is that it is not very self-contained and could be presented better/more polished:  \n\n **1** There are several minor errors in the supplementary. In particular, to the best of my knowledge, the **proof of Lemma 3** in Appendix A1 is **wrong**: the equation on line 476.5 is incorrect as it ignores cross-terms. The result is still correct, for different reasons: in the case of the nuclear norm, this is a classic result that can be shown without recourse to the factorized decomposition of the matrix. In the case of the max norm, it follows from the expression of the ball w.r.t. the max norm as the convex envelope of the set of rank 1 matrices (c.f. [3]).\n(*Please fix this*)\n\n **2**.  The explanations are not always perfectly self-contained and assumptions are not always well introduced.\n\n**2.a**  For instance, Theorem 18 requires a condition on the learning rate $\\eta$ which is not stated in the theorem. It is clearly needed from applying what the authors call \"standard Online Mirror Descent analysis\", and it appears in line 763.  It wouldn't hurt to add a complete citation and a restatement of the known result with more detailed calculations. (I found one at https://www.cs.cornell.edu/courses/cs6783/2019fa/lec17.pdf for instance). Note also that it seems that $\\|.\\|_t^{*}$ is undefined and $\\tilde{C}$ doesn't appear in the formula below line 757 which makes it strange that it is introduced when presenting this equation. The same problem is on line \n\n**2.b** It is also not immediately apparent whether Corollary 21 (appendix, page 21) requires the sampling distribution to be uniform (as stated in the preamble to the Corollary (lines 702 to 703) or if it is an arbitrary distribution $\\mu$ as stated in the first line of the corollary itself. \n\n\n**2.c** I found the proof of the NP-hardness somewhat confusing. See questions.\n\n**3** It seems like the matrix relative entropy from line 860 is not actually used in the paper (and certainly not in the definition of the regret/loss function $h_t$ in line 656 (even in the entropy case 1.a, this is an elementwise entropy.  I am not sure but I think it is used in [1]. A more detailed comparison of the definitions of regret in both places would be nice. \n\n\n\n\n**Minor issues/mathematical typos:** \n\n1. In Theorem 8, $\\mu_{\\max}$ is used in line 517 but is only defined later in Proposition 16 on page 16.\n\n2. In line 65 in the main paper, I it should be $\\tilde{O}(|U|)$ rather than $\\simeq |U|$ since there is definitely a log term involved.\n\n3.(minor) Algorithm 3 is only understandable when considered in combination with the algorithms that define $\\mathcal{A}_C$ (line 751 page 24) and $\\mathcal{A}_M$ (line 799 page 27). Algorithm 4 (definition of $\\mathcal{A}_C$ itself depends on the quantity $R$ which is only defined later in line 756. In particular, algorithm 3 requires some hyperparameters such as $\\eta$ from Algorithm 5 and $\\theta$ from algorithm 3, making it difficult to read in the order in which it is presented. \n\n4. It seems like the initialization of $\\hat{C}$ in line 4 of Algorithm 4 is incorrect (missing normalization step to make the matrix belong to the simplex). \n\n5. The notion of Bregman projection and the associated notation $B_R$ is not defined. It would help the reader a lot to finish line 8 with an additional  $=argmin_{c\\in\\mathcal{C}'} R(C) -R( {\\hat{C}}_{t+1})$ $-\\langle$  $\\nabla$ $ R(\\hat{C}_{t+1}),C-\\hat{C}_{t+1}\\rangle $ [ apologies about the markdown not working properly], which probably can be done without adding a line. \n\n6. It seems like the settings 1.a and 1.b are described in the wrong order (swapped) on lines 753 and 754. \n\n7. In the caption of Figure 1, stochastic block models are mentioned in a somewhat tangential way. \n\n8.It seems like the \"matrix completion and recommendation system\"  part of the related works is missing relevant works. Probably most notably [5] and [4].\n\n9. I think there is a factor of 2 missing in equation (6) (line 300.5). This error is not present  (the factor of 2 is there) in the proof of Theorem 23 in line 732.\n\n10. Iines 684 and 744, there are missing references (\"see section ?? for an example\")\n\n11. In line 149, I think the expectation should not run over $x\\sim\\mathcal{X}$ but instead over $x\\sim \\nu$. \n\n\n12. There is an equal sign missing in the equation on line 867.5\n\n13. There is a missing $\\leq \\epsilon$ at the end of line 207\n\n\n\n14. Line 179, I think the square loss is actually 4-Lipschitz, not 2-Lipschitz, when both of its arguments are in $[-1,1]$\n\n\n15. I think there is a factor of $\\alpha$ missing in the right hand side of the inequality in Lemma 25. \n\n\n\n\n**Typos and extremely minor issues:**\n\n\n1. I found the use of \"$\\Delta$-inequality to mean triangle inequality in line 764 quite confusing given that $\\nabla$ is a loaded notation: cf. the set $\\nabla_{\\chi}^\\beta$ and perhaps more confusingly the matrix relative entropy from line 860 on page 32. \n\n2. Line 755 is not a complete sentence. \n\n4. It would be nice to define \"negations\" in lemma 3 (in addition to fixing the proof). \n\n5. There shouldn't be a capital letter at \"Let\" at the top of page 15. \n\n6. it would be nice to mention again the stability w.r.t. negations in line 534 as the argument is somewhat key. \n\n7. Missing periods in equations (8) and (9)  and in line 782. \n\n8. Extra \"and\" in line 723. \n\n9. An extra \"That\" at the beginning of the first sentence of the proof of Theorem 23 on page 23 is required to make a sentence. \n\n10. Missing determinant in line 744. \n\n11. Line 764 \"approximately same performance\", missing \"the\". \n\n12. Line 788 \"assume\" should be \"assuming\"\n\n13. 812: \"notation convenience\" should be \"notational convenience\"\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n**References**\n\n[1] Elad Hazan, Satyen Kale, and Shai Shalev-Shwartz, \"Near-optimal algorithms for online matrix prediction\", COLT 2012. \n\n[2] Elad Hazan et al. \"Introduction to online convex optimization.\" Foundations and trends in optimization, 2016. \n\n[3] Nathan Srebro, \"Rank, Trace-Norm and Max-Norm\", COLT 2005. \n\n[4] Prateek Jain, Soumyabrata Pal Online Low Rank Matrix Completion. ICLR 2023.\n\n[5]  Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, Yuling Yan. Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization.  SIAM journal of Optimization, 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your very detailed review of our work!\n\nWeaknesses:\n\n1.  Lemma 3 in Appendix A1: Thank you for pointing out the mistake. We will change this. In fact, the convexity of the constraint set follows directly from the (non-trivial) fact that max-norm is a well-defined norm. \n\n2. The explanations are not always perfectly self-contained and assumptions are not always well introduced.\n\n2.a: Thank you for pointing this out. Yes, we should remove the $\\tilde{C}$. \n\n2.b: Thank you for pointing this out. There is a mistake in  the preamble. Corollary 21 holds for arbitrary distributions. We will change the writing accordingly. \n\n\n3. Thank you for your suggestions. We will improve our writing. Matrix entropy is used in Algorithm 5. \n\nAll minor issues and typos we will fix accordingly. Thank you very much for your very detailed feedback.\n\nQuestions:\n\n1.a I don't understand why problem (7) is equivalent to problem MP 3. Indeed, I can't see why the PSD condition appears. I have a feeling this comes from the $(\\beta, \\tau)$ decomposability, but there is definitely an argument missing.\n\n**Response**: Indeed it is not immediately equivalent, and there are subtleties here. Thanks for pointing this out. We made changes to the appendix accordingly.  In fact, we could show that with added symmetric PSD condition, the problem is NP-hard. We add this as only an indication of computational hardness in a special case. We will clarify this in the appendix of the final version. \n\n1.b The first argument in the \"soundness\" part which states that we can assume is rank one w.l.o.g. I also don't understand this argument: why is it the case that the matrix achieves value if the matrix  does. This is absolutely not obvious to me. I agree with the rest of the proof assuming this is correct.\n\n**Response**: The proof shows that given a solution, we can construct a rank-1 solution with the claimed objective value, which is sufficient for our proof. The construction is simply taking the rank-1 matrix ww^T for w_i = root(X_{ii}). The objective value of this rank-1 matrix is at least the objective value of $X$ since $X_{ii}X_{jj}\\geq X_{ij}^2$ for symmetric psd $X$. \n\n2. Can you clarify whether the expectation in the equation on line 603.5 (bottom of page 18) refers only to the randomness in the choice of the loss function $h_t$ (which is assumed to be \"stochastically i.i.d.). In that case, shouldn't there also be an expectation on the right hand side in front of the regrets?\n\n**Response**: Indeed. Here the regret is the expected regret. We will make sure to clarify this. \n\n2.2 The lengthy discussion at the beginning of Section B culminating in the equation from line 603.5 seems to mostly justify the validity of the Game-Regret (see line 679) as a measure of performance of the algorithm by linking it to the minimax regret. Why not apply the result from line 603.5 and make a self-contained theorem which applies to the minimax regret in the paper's setting?\n\n**Response**: Line 603.5 holds for bilinear shared objectives. The shared objective function in the online PMC setting is not bilinear. However, it still motivates the use of Game-Regret as a measure of performance (also indicated by the Corollary 21). \n\n3 On lines 786-788, why do you assume $T\\geq \\tilde{O}(m+n)$ (first) and then $T= \\tilde{O}(m+n)$ (also as in the statement of the lemma) rather than $T\\geq \\tilde{O}(m+n)$? Firstly, the result is only interesting if the condition is a lower bound on $T$ only (I am confident this holds but it is not stated as such. Secondly and more importantly, it doesn't seem like the tilde is required since there are no log terms. In particular, if we interpret the tilde notation as possibly involving dividing factors of log terms (since we want a lower bound on $T$ not an upper bound), the second to last inequality on the sequence of inequalities in line 788.5 could be incorrect (though the last inequality with $\\tilde{O}(\\alpha\\sqrt{T})$ remains correct where the log terms are $\\log(mn)$.\n\n**Response**: \nThanks for pointing this out. First of all, tilde is not needed, and we are upper bounding $T$ here. The more accurate statement is that the LHS is bounded by Te^{-\\beta}mn. The range of parameters we are interested in, is T ~ poly(mn). We can therefore choose the constants in \\beta to be as we need. We will clarify this in the later version. All we are trying to say is that by restricting to the constrained simplex, we do not lose much in the optimal point of the objective. For every $t$, the objective functions of the two $C$’s differ by order of magnitude $1/mn$. When summing over $T$ iterations, the difference between the two optimums is bounded by $\\alpha T/mn$ (constant omitted). Since to achieve $\\epsilon$-error in regret, we only need $T$ to be of magnitude linear (up to logarithmic terms) of dimension $m+n$, this difference is small. In fact, since our regret is dominated by $\\sqrt{T}$, we might only need this sum of differences to be bounded by $\\sqrt{T}$, i.e. $T/mn \\leq \\sqrt{T}$, which is clearly true as we at most need to see all $mn$ entries to complete the matrix.  \n\n4 Could you include a more detailed comparison to the existing results in [1] and [4]?\n\n**Response**: We are happy to do it in the full version. The main difference is that we are tackling a partial completion problem, whereas these papers consider full completion. However, we make extensive use of their techniques, especially in the online algorithm and its analysis. Notice that, however, we have a different primal-dual definition of regret. We are happy to elaborate more in the full version. \n"}]

Author rebuttal:

Meta-review: The reviewers are unanimous that this interesting twist on the matrix completion problem deserves publication. The reviews are high quality and demonstrate detailed understanding of the paper, and the discussion was vigorous.
Decision: Accept (poster)