Fine-grained Generalization Analysis of Inductive Matrix Completion
Authors: Antoine Ledent
Rodrigo Alves
Yunwen Lei
Marius Kloft
Venue: NeurIPS 2021 Poster (2021)
Keywords: Inductive Matrix Completion
Statistical Learning Theory
Nuclear Norm Regularisation

Abstract: In this paper, we bridge the gap between the state-of-the-art theoretical results for matrix completion with the nuclear norm and their equivalent in \textit{inductive matrix completion}: (1) In the distribution-free setting, we prove bounds improving the previously best scaling of $O(rd^2)$ to $\widetilde{O}(d^{3/2}\sqrt{r})$, where $d$ is the dimension of the side information and $r$ is the rank. (2) We introduce the (smoothed) \textit{adjusted trace-norm minimization} strategy, an inductive analogue of the weighted trace norm, for which we show guarantees of the order $\widetilde{O}(dr)$ under arbitrary sampling. In the inductive case, a similar rate was previously achieved only under uniform sampling and for exact recovery. Both our results align with the state of the art in the particular case of standard (non-inductive) matrix completion, where they are known to be tight up to log terms. Experiments further confirm that our strategy outperforms standard inductive matrix completion on various synthetic datasets and real problems, justifying its place as an important tool in the arsenal of methods for matrix completion using side information. 

Fine-grained Generalisation Analysis of Inductive Matrix Completion
Antoine Ledent TU Kaiserslautern ledent@es estrreess.uii us.uni-kl.de
Rodrigo Alves TU Kaiserslautern
Yunwen Lei University of Birmingham y.lei @ bham.ac.uk
Marius Kloft TU Kaiserslautem kloft es. uni-kl.dde
Abstract
In this paper, bridge the gap between the state-of-the-un theoretical results for matrix completion with the nuclear norm and their equivalent inductive prove sample complexity
matrix completion: (1) In the distribution-fre setting, bounds improving the previously best rate of rd? to d (og((d) where d is the dimension of the side information and r is the rank. (2) We introduce the (smoothed) adjusted trace-norm minimization strategy, inductive analogue of the weighted trace norm, for which we show guarantees of the order O(dr log( d)) under arbitrary sampling. In the inductive case, similar rate previously achieved only under uniform sampling and for exact recovery. Both our results align with the state of the art in the particular case of standard (non-inductive) matrix completion, where they are known to be tight up to log terms. Experiments further confirm that our strategy outperforms standard inductive matrix completion on various synthetic datasets and real problems, justifying its place as an important tool in the arsenal of methods for matrix completion using side information.
Introduction
Matrix completion (MC) is the machine learning problem of recovering the missing entries of partially observed matrix. is the go-to approach in various application domains such as recommender systems 2 and social network analysis 3 3. The Softlmpute algorithm 66 7 is among the
most popular MC methods. It solves the following convex problem encouraging low-rank solutions:
min ZER
-
Al|Z
(1)
where Pa denotes the projection on the set Ω of observed entries, G' is the ground truth matrix, and I| denotes the nuclear norm (i.c., the sum of the matrix's 's singular values).
Besides the incomplete matrix, additional information may be available applications such as movie recommendation or drug interaction prediction 8 99 10 II]. For instance in movie recommendation.
one may have access to the movies' genres, their synopsis, the gender and occupation of the users, or friendship network between the users. Inductive matrix completion (IMC) [1 12
B3
14 exploits
such side information. It assumes that the side information is summarized in matrices X m and Y nxd2, with the row vectors representing the users and items, respectively. IMC then optimizes the following objective function
} I G) + A|MMI 2
min Kdg
(2)
This model has been used in many domains also beyond movie recommendation g 10
15
In this paper, contribute to better theoretical understanding of IMC and related methods in the approximate recovery case. In this setting we obtain guarantees in terms of a bound on the expected
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

loss which decreases with the number of samples. Our best results concern the distribution case, meaning that our bounds are valid for any sampling distribution. This sharp contrast the vast
areas of literature where one assumes the distribution is uniform 16
17 18
Our analysis leads
to substantial gains compared to the state of the art results [99 20
as we obtain near optimal bounds in situations where the state of the art bounds are vacuous, as is explained below.
21
Although for uniform sampling, near-tight exact recovery bounds of O(rdlog(d) log(n)) exis for
IMC 16 17]. the approximate recovery case (especially in a distribution-free setting) is far less
understood. The sfae-oo-thee-as distribution- results for IMC were proved [99 20 (and in 211
for a kernel formulation of IMC) and, expressed in terms of generalisation error bounds, scale as
o (xyMV1/NN)
where x := |X = max, [x.,,]| is the maximum norm of a left side information vector (row of X), N is the number of available samples, and y := |Y |2.0 = max, |Y,,| is the maximum norm of a right side information vector (row of Y). This implies that reaching a given loss threshold requires 0(x2y2M2²/ /2²) entries, where .M is a bound on the nuclear norm of M. In this case, we say that the 'sample complexity' is O(x²y" M²). To understand how those bounds scale with the matrix dimensions, consider the simple case where X and Y are made up of blocks of identity matrices. In that case, have x y 1, yielding a sample complexity of O(M²). Since |M drr, this yields a bound of order rd?
2
Such bounds have a remarkable property: they do not depend on the size of the matrix and instead depend only on the size d of the side information. This means that they capture the fact that valuable information can be extracted even for users and items for which no ratings are observed. On the other hand, these bounds have a strong dependence on the size d of the side information. As an illustration, consider that they vacuous when X I and Y = I, since the required number of entries Ordd)) = Orr²²) then grows faster than the total number of entries n²? This is despite the fact that in that situation, distribution-free bounds for standard matrix completion yield sample complexity of ( vF) for the standard regulariser (22] and O(nr log(n)) for modified regulariser (the smoothed weighted trace norm from (23) Thus, these existing distribution-fie IMC bounds are very far from tight. In fact, they are only meaningful when the size of the side information is negligible compared to the general scale of the problem, which is a significant limitation in terms of the elegance of the theory (mismatch with MC bounds, separate proof techniques for separate regimes) and in practice (real-life side information could be very high-dimensional. especially if it is extracted from a neural network (24) from wide variety of different sources). To reinforce that point, note that any side information with a strong cluster structure would exhibit similar failings to the above mentioned identity side information case.
In this work, we bridge the gap between the state-of-the art in matrix completion and inductive matrix completion with the trace norm by providing distribution-fee bounds for IMC which combine both of the following advantages: (1) a lack of dependence in the size of the original matrices, and (2) more refined dependence the size of the side information: the dependence on d in our bounds is almost the same as the dependence on n (the size of the matrix) for the state-of -ft--offtheheee the MC results. More precisely, our first contribution is to provide a bound of order O(da/2 log(d)) for the standard regulariser (2). The proof builds on techniques from 22 25 but is substantially more involved due to the complicated dependence structure generated by the side information. As our second contribution, construct analogues of the ideas of (23 26 for the IMC setting: we begin by showing bound of order (rd log(d) for a class of distributions with certain uniformity assumptions (our "uniform inductive marginals"), and then design new "adjusted trace norm regulariser" for the problem (2) with similar properties to the weighted trace norm [26] 23 in MC. Instead of simply renormalising rows and columns of M in previous work, our method requires rescaling the core matrix M along data-dependent orientations that capture interplay between the sampling distribution and the side information matrices X, Y.
Our contributions are summarised as follows.
I with some orthogonality assumptions on the side information
where the users and items are approximately split into 'communities', see also Appendix
2

---

1. We provide distribution-Fi free generalisation bounds for the inductive matrix completion model 2 (assuming a fixed upper bound on the nuclear norm) which scale like O vr log(d) where a soft relaxation of the rank.
2. In the case of uniform or approximately uniform sampling, we provide bound of order (rdd (og()) for approximate recovery.
3. We introduce modified version of the IMC objective (2), which we refer to adjusted trace norm regularsation (ATR). An empirical version E-ATR is also introduced and both achieve bounds of order Orrdlog(d) d)) in the distribution-fres setting.
4. We experimentally demonstrate on synthetic data that our adjusted regulariser outperforms the standard IMC objective in many situations.
5. We incorporate our method into a model involving non-inductive term and evaluate it on real-life datasets, demonstrating substantially improved performance.
This paper organized as follows. In Section 2
we review some related work. In Section we we present our experimental results.
introduce our main results. Finally, in Section
2
Related work
In both MC and IMC, the existing literature consists of several main branches differing in their main assumptions: exact recovery versus approximate recovery and uniform sampling versus distribution- free bounds. In exact recovery, the matrix is assumed deterministic, and want to recover its missing entries exactly [17 16,
27] 28]. In approximate recovery, the matrix is assumed noisy, and we want to recover its missing entries only approximately, within some interval around their expectation 19 20 21
uniform generalisation bounds Approximate recovery theory is typically expressed in terms of a function class using matrix-norm constraint. Assuming that the entries are sampled from a specific distribution (e.g.. uniform), one typically can achieve much faster rates than distribution free theory regardless of the distribution. The typical sample complexity of standard MC under uniform sampling is O nr log"(n)) for exact recovery (proved in the series of breakthrough papers 28, (0) and ( log(n)) for approximate recovery [23]. In [1], an improved rate of nr log(n) ) log(r) (for exact recovery) was shown.
I8 22)
The most closely related papers to ours are 22 and 23 which both work only on standard matrix completion without side information. In in the distribution-fii Orn (rgnoo((n) are shown for sampling with uniform marginals and for smoothed version of the weighted trace norm regulariser in the distribution-fies case. We almost perfectly extend most of the results from both papers to the inductive case, which requires many technical modifications.
bound of order On /T) was obtained setting for matrix completion with the trace norm, whilst in 23, rates of
Within the IMC framework the closest works are those which also deal with approximate recovery in the non uniform sampling case: [2]
33 19 20). Their bounds. presented in many different contexts, translate to sample complexities of type O(rd²). Other celebrated works in the theoretical study of IMC include: [16] and [17,, which showed rates of order d log(d) and rd log( d) log(n) respectively for exact recovery with uniform sampling, together with other important contributions (see appendix). In the case of exact recovery, the rate of rd log(d) log(n) was obtained only under the assumption that the side information matrices have orthonormal columns. Some bounds use
completely different regulariser (such as the max norm) to achieve better rates [34 35) works also do not involve side information.
etc. These
In Figures and 2 we summarize state-of-the (s.o.t..) results in both MC and IMC. Note the problem of exact recovery in the distribution- case is ill-defined (hence the N/As in our table). In approximate recovery bounds, we omit a factor of 1/e², where e the tolerance threshold in terms of expected loss), as this factor is present in all approximate recovery bounds In exact recovery bounds, the rate the order of magnitude of the threshold past which exact recovery occurs with high probability.
"To our best knowledge, all results show decline in population expected loss of the order of VI/N where N is the sample size
3

---

Table Matrix completion results (trace norm form-based only)
MC
Unif.Sampling
Distr.-free
Weighted version
Exact
wr orloo"()) (127 28
30
N/A
N/A
arlog(n) log (r)
Approx.
nr log(1)))) (n) 23 22
3/
22
rn molo(())
(3
Table 2:
Inductive matrix completion results (trace norm-based only)
IMC
Unif Uampliggg
Distr.-free
Weighted version
Exact
rdlog(d) (n) r log d'
11
18
N/A
N/A
16
Approx. (s.o.t.a.)
rd [11 33
19
rd 21 33
191
None
Approx. (ours)
rd log d) (Ours)
d
Vr log dd) (Ours)
rdlog(1) (d) (Ours)
Other related works include (IMCNF) 19 20). which proposed the following model:
min
Gug (X + 2)sz1 A >21 (R,))R
Σ
(4)
where Å1, A2 are regularisation parameters, G.j denotes the observed entries and the predictors take the form (XMYT + Z). This model relies on the cross-validated hyperparameters λ 22 to balance the importance of the side information. The authors also showed results based on combination of bound for the inductive term XMY and a bound for the non inductive term Z. The non inductive similar to [22], whilst the bounds for the inductive term are proved from
terms in the bounds scratch and have also later appeared in a different form in [21 33 together with a kernel formulation of IMC. In Subsection 4.2 combine our framework with this strategy reach competitive results.
[36], the authors introduce a model consisting of sum of mutually orthogonal IMC terms together with an explicit optimization strategy in the specific case where the available side information consists model
partitions of the users and items into communities. In (37), the authors further extend to learn the community membership functions together with the ground truth matrix, based only the sampled entries. The case a single IMC term where the side information is in the form of community partition is useful to develop intuition into the equivalent roles of d2 d2 in our bounds versus m, in MC bounds. Whilst generalization bounds were proved in 36 with a similar scaling bound from Thm 3.1 (and in particular are better than the state-of-the-an IMC bounds if applied to this situation), they only apply to the specific case community side information. In this work (Theorem 3.1 we achieve the first IMC bounds which cover the whole range of possible side information matrices X, Y, whilst providing the correct scaling (up to log terms) in the case of identity community side information. Community side information has also been studied in other discrete contexts where individual behaviour is assumed to be a noisy realisation of community side
information 38 39
Another work is [18] which introduces a joint model that imposes a nuclear norm-based constraint on both M and T through modification of the objective. The authors prove bounds for their method which match the state of the art in IMC [17] 19 and MC [22] when the side information is perfect and useless respectively. The dependence
the side information is better in
Further discussion of that paper is included in the appendix. Of course, there are also many other works which propose modified optimization problems for the Recommender Systems task through other rank-sparsity inducing regularisers (35 34 40 and even exploiting other ground truth structure
besides the low-rank property 41 42
3 Main results
We observe N entries of a ground truth matrix G E Rmxn which are sampled i.i.d (with replacement) through an arbitrary distribution p. we draw (i,j) (1...,m) m) (1,..., n) with probability Pi.j where Σx, Pij 1. The sampled entries {l 2
Notation:
...., , (1,2..... ......... m) x

---

(1.2...., n) form multiset Ωt: our setting allows for the observations to be noisy with different noise distribution for each entry. but purely for notation convenience we often treat the issue as if there is no noise when no ambiguity is possible. When written explicitly, the noise is denoted by Ç. For a function f observations, counted as many times as necessary We assume we are given side information matrices X E IR and Y E Rgaxd,, The maximum 1,2 norm of row of X (resp. Y) is denoted by (resp. y). The minimums Y) are also writtenn zj for & m (resp. Yj for j & n ). For any matrices A, B, A & B means that B - A is positive semi-definite, ||A|] denotes the spectral norm of A and || denotes the nuclear norm of A. We have one fixed loss function used throughout the paper which is both Lipschitz with constant e and bounded by b. For convenience also frequently write instead of max (d1, d2)- In the appendix, we provide complete table of notations (Table K.I) that includes all notations introduced throughout the paper.
we will write (ingen ((G,)) for the sum of the images of the
denoted by I and y respectively. The row vectors of X (resp.
We now present our results, starting with the distribution- bound for the standard regulariser, then moving on to the improved bounds under uniform sampling, and finally to our adjusted trace norm regulariser and the theoretical improvements provides.
3.1 Distribution-free guarantees for the standard IMC objective
For a constant M E R, we define the function class: FM {XMYT: IIM < MM. which contains all predictors X where M has its spectral norm bounded by S. Our first main result is uniform generalisation bound for the loss minimiser within this function class. Below we use the shorthand ((4) (resp. (s(A) or even (A)) for B(i.))=(((AA.) G.y + (ay)) (resp. E(idee (Ai. G.j + (r,j)/ N), the overall expected (resp. empirical) loss associated matrix A e R" xn, In particular, in the noiseless setting, infzeF ((2) = 0 as long as || & M.
Theorem 3.1. Fix any target matrix G and distribution Define 2ς arg min([s (Z) Z E FM). For any 5 E (0, 1), with probability (w.p.) >
6 over the draw of the training set Qt we have
[
1(2) & inf ((Z) + Bbxy.Va T N
xyLM + log(2d) b
log 2/0)
+ 4bl
(5)
ZeFM
VN
N
2N
where C a universal constant, b is a bound on the loss, is the Lipschitz constant of the loss 1, and (2og(2)) +
V
1) is a logarithmic quantity. Furthermore, in
expectation over the training set we have:
Lbxy Bbxy M
b
xyeM+1 +
I
12) inf ((Z) + C ZeFM
(2d)
+ 206
(6)
N
VN
N
N
The proof is provided in Appendix A Assuming that f, b are treated as constants, the above bound on the generalisation gap ((2) inf zeF ((Z) scales like
XyM N
xyMVd N
log(d)
Vlog(d) + Iog(NN) + vlog(xyMM)
(7)
we further think of the maximum entry of the core matrix M as bounded by a constant, M scales like /d where is the rank of M. Assuming the rescaling also set that x. y constants, the above yields a sample complexity of
Viidov dr log(d)) 2
"More rigorously the observations are i.i.d of the form (E", (o) with E" (1,2....,m)) 21, m) and T" E I and write ΣN ((E.) instead of E g) and it should be assumed that the "ground truth" values G (are defined to) minimize E(I(Gs, {)) for our loss function over the joint distribution of E
5

---

where is the tolerance threshold. Indeed, the / log((N NN) observation: If N è (og(@) and è is sufficiently large then
term can be treated via the following simple
N
+ (
+ log +
2 log( ( 0/2.
log( N)
log(E) ( + log(log(O))
Remark on the proof technique: The proof of the result in 122 relies lemma of Latala (lemma A.II from [3] for random matrices with i..dd entries and an elegant decomposition of the entries into two groups: (1) entries that have been sampled many times, and (2) entries that have not been sampled too often. On group I, the partial sums of the Rademacher variables concentrate trivially, whilst group 2, the entries well spread out and Lemma limits the spectral norm similarly to the uniform case. The proof is about carefully balancing those two contributions.
In our inductive situation, using the known and vacuous when the side information is of comparable size to the matrix. Our key idea to fix this issue is that instead of distinguishing frequently and less frequently sampled entries, split between high and low energy orientations corresponding to pairs (X. Y.,) of columns of the side information matrices. To achieve this aim, use the rotational invariance of the trace operator and equivalently express the Rademacher averages in inductive space (R xd2). However, the entries of the resulting matrix are certainly not independent, which makes it impossible apply the concentration results from 43 Instead, we must rely again on the matrix Bernstein inequality [F44] Obtaining covariance structure that is amenable application of this result requires performing an iterative procedure involving series of distribution dependent rotational transformations of the side information and other estimates at each step.
split can only yield bounds of the type 3 which are well
3.2 Generalisation bounds for the trace norm regulariser under uniformity assumption
We now move to our second main contribution, which is broad generalisation of most of the results of (23) the inductive case. this direction, we begin with a result for approximate recovery in inductive matrix completion with the standard nuclear norm regulariser. Although this first result (proved Appendix B original the best of our knowledge, it is not surprising since a similar result is known in the exact recovery case. However, it is an excellent way to introduce notation which will be necessary in the rest of the paper.
Proposition 3.1. Let us write FM for the function class corresponding to matrices of the form X with [M]|& & M. Let Ms = arg min EgEn I((MMY )g. Gg + <e)) be the trained matrix M and M, = arg min |M &M EI((MMY )), Ge (e) be the optimal M when M is restricted by x & .M. Write also 2s = X and Z. = XM,Y
Write K. == max
Vdl X
d2
Y
XI
Under uniform sampling, w.p. > 1-160
m
n
m
SEKVrd(1 log(2d)
12 N
Mxy(1 log(2d)) + by 1og(2/0)
1(2s) - 1(7x)
VN
2N
where M/=M//duu and b is a bound on the loss. Furthermore, the above result holds under the following more general "uniform inductive marginals" condition (analogous to the "uniform marginals"):
Y and Vj, Epislas12
X
Vi, Epsslosl
Fr
Remarks: If ||ara|| and ||اا|| are constant over and j, then the above conditions 9 reduce
requirement of uniform marginal probabilities. Note that /r (M/vdjjs) acts as soft relaxation of the rank of M since M FM and the entries of M are bounded by 1 then rank M) & r. X and Y I, then conditions (9) reduce the uniform marginals condition from 23
In particular, we see that the case of identity side information, we require O(dr log(r)) samples to reach a given accuracy. However, the result above is deeper when the side information is non trivial. Indeed, the quantity max(v [ X Y
Fr. Y X which equals d max d1, de) in the

---

case of identity (or equal-size community) side information, is sensitive to the relative orientation of the columns of X and Y: if the side information X and Y are properly scaled and approximately of rank p. then this quantity will approach p. We discuss this in more details in the appendix.
To prove the above result, will show slightly more general result below (Prop 3.2). In order to capture the interaction between the side information and the data-distribution, we must define distribution-ddependent inner product (.,-) (resp. <-, +),) on the column space of X (resp. Y):
For two vectors u², u² E IR" (resp. o², v² E IT") we define (u', u²)) = E u uzufa (resp.
(v), -00) د (5))) where the qes and KiSs are defined by
m Σ
Q: Σ Pusllusll Vi m
Ki
Pasllaul
Ej n.
(10)
We now define the vector a¹ Rd (resp. o² E (dd) as the vector of singular values of the matrix X (resp. Y) with respect (w.r.) the inner product (., (resp. (.,-))) In other words, the entries of o² E Rd (resp. o² E Ied))) are the square roots of the eigenvalues of the symmetric matrix I ==
X diag(g) E Rdixdd= = E., 21, 1y (resp. R := Y diag(k)) = Lis Pi.ji, |=::|² Rd2xds). We also write a = max(a") and o² max(
Proposition 3.2. With the same notation as in Proposition training set Q2:
w.p. R 1 - over the draw of the
8l M 01) + log(2d)) Mxy(1 + +lg((2)) + +by
128
log log (2
((ss) - ((2))
2N
Note that both of and o² scale as the product of the scaling of X and Y. The above result shows that if the distribution is only approximately uniform (sampling probabilities within a given ratio), then the bound is only penalised proportionately to this ratio: for identity side information, [o]]² is the maximum user (marginal) probability which scales like 1/dj for approximately uniform marginals. Similarly of 1/d2, yiclding sample complexity bound of order dr log(d) as expected.
Remarks:
3.3 Proposed adjusted regularisers and notation
In this section, we introduce our adjusted trace norm regulariser and its variants. We first recall that in standard (non- inductive) matrix completion, the weighted trace norm (26] 23 of matrix Z is defined as IV DDVE + where D E Ra (resp. E E I²**") are diagonal matrices whose diagonal entries contain the marginal row (resp. column) sampling probabilities. Regularising the weighted trace norm instead of the standard trace norm increases performance (26 and leads to better
theoretical guarantees. In this work we extend those advantages to the setting where side information is available.
Notation: Recall r Ei, Pi.j [a:/>>/////3 2, Our method is based on careful distribution-dependent rescaling of the matrix M. The idea is that we must look the principal directions (singular vectors) of the side information matrices, but computed with respect to a distribution senssiiiii inner product: when computing inner products of vectors in the column space of x. components corresponding to highly users which are more likely to be sampled must be weighted more. Accordingly, we diagonalise the matrix L X diag(g)X (resp. L Y diag(x) from above write P DP (resp. Q-'EQ) We also define empirical versions of those quantities: f = 2/4 En, his |=.l?
where ha,j is the number of times that entry (i, was sampled: his5 N (c.=(t)) = #(2 [(i,j))); 9. Σ, hesi N | 21 Rg =E hid N' ||2,1]2 2, f. = X diag(g) R Y diag(R)Y, and their
diagonalisations P D and --Q We can write our predictors
= T = XP A PMQ-'E - 3 1 - 3 (11)
The simplest version of our proposed algorithm to regularise [ 10-1PMQ-LE+ instead of M.
However, some extra technical modifications may be necessary: If some users or items have extremely small sampling probability, the corresponding entries of 2 and E- will be very large. To obtain good bounds, we tackle this issue by forcing the entries of D, D, E, É to be bounded below, which
7

---

= we achieve via smoothing: fixing parameter a é [o, 11. we define D = aD (1 T//d and
E = o.E + a where I is the identity matrix. Similarly, D - aD +1 a//h/d and
E = au (1-a)///d
We also define accordingly M' = - M =
and M- = D. PMa2 - E:: as well as similarly X = XP Dp-1D-1, X' = = 2,
x D- = XP-1D y = YP- E Y -PP y= YQ Dー Y
-Q- D-.. Thus XMY = X = XMY
=
Proposed models: We then propose a variety of adjusted regularisation strategies as follows by
replacing the regularisation of M by that of M', M, M or M depending on whether the ground truth distribution is known and whether smoothing is desired. For instance, in the smoothed, empirical case, we will solve the following optimization problem:
min N
Σ 2(((MMYT) G5 + (e) + + 1 EEN
(12)
Remark:
Similarly to the matrix case the smoothing parameter or is set to & in all theorem statements In the experiments, we vary a as indicated.
We will prove results for the empirical risk minimiser belonging to the following function classes:
F. : XMYY || & vir] -. XMYT || < vFf
(13)
corresponding to the smoothed and smoothed empirical versions of our algorithm. Note that the factors of I are added purely for convenience in the final formula, so that we can understand the final formulae in terms of soft concept of "rank". Indeed we have
B & di 2d1
r
+
Vl diag(1) (g) 1 = (1/2)T + (1/2) 2
E Σ 1,16
Σ p
r, (14)
1,0
and similarly | 112 & r. Thus if PMMQ 1o & 1 and rank(M) & p. we have | & &
Ml & woy2.... 2m D /pr. Similarly, ||M]| & vpf under the condition PMMQ21 lc $ 1.
& VPIPMQ 108 &
3.4 Generalisation bounds for the smoothed adjusted trace norm
Although knowing the distribution is not realistic, it is instructive to see that one can obtain guarantees of order O(dr Ooglog (d) for the function class F, a reasonably straightforward extension of the ideas developed for Proposition 3.2 The proof is provided in Appendix C
Proposition 3.3. Let Mg = arg min M | Egen I(MMY )g. G5 + (c) be the trained matrix
M and Z, arg min ZeF, El(,e, Ge + Ge) be the optimal Ž when the predictors are restricted to the class F,. Let also Zs = XM We have w.p. 2 1 1-6: 6:
I(2s) 1(2,)) 166 16E/TVFVd(1 + vlog(2d))
(ixyydd/do(1111 + log(2d)) + by
(2/(2/)) 2N
N
3.5 Generalisation bounds for the smoothed empirically adjusted trace norm
Below is a more challenging result (proof in Appendix corresponding to the empirically smoothed regulariser.
D which concerns the function class F,
Theorem 3.2. Fix any target matrix G and distribution p. Define ns arg argmin((s(Z)) : 7007000 7 F,)
where ist (z) = 1/2 Egen UZe, Gg + (e). For any E 1), w.p. 2 1-8 8
(ž) < inf ((2) + C[VT7(x++V))) + +b] ZeF.
(15)
N
'It is trivial extend the proof's arbitrary the cost of factor of L/ min(a, 1 a).
8

---

y and C is universal constant. In particular, in expectation over the draw of the 21 training set we have
where
ZeF. (()) E inf ((2) 2C 2C + +b] 72
(16)
The significance of this result that even in the case of an arbitrary distribution, minimizing the smoothed empirical adjusted nuclear norm |M| results in sample complexity bounds of order dr log(d), meaning that distribution-dependenn transformations have completely removed the negative effects of non-onnnonee non-uniformity on the sample complexity. Note the proof requires careful technical variations compared to the proof of the comparable results in [23. As example, Lemma[E.] the
equivalent of Lemma in page 8 of the supplementary in 23 (whose proof is far shorter).
3.6 Variations on the optimization problems
As in the related literature [19 22 etc.), we worked with a bounded loss, and expressed our results for the loss minimizer within a function class defined by explicit norm constraints. However, is also possible to modify the results (under some boundedness assumptions) to make them apply to lagrangian formulations such as 18) I 2 In typical contexts where the entries are known to be bounded, this can even be done with the square loss. As example, we consider the following immediate corollary Proposition 3.3 and its global version C.T (appendix):
Corollary 3.4. Assume that all of the entries of the ground truth are bounded by constant C, and that they are observed without noise. Let Z# = XM Y be the solution to the following optimization problem:
min M
IDD E3
subject to [XMY = Vg
(17)
Let (x(x) sign(x) min((o)), C). For any E-Lipschitz loss 1, we huve (with probability > 1 8)
SevT + 22o)(2d)) (()c(Z+)) &
12 didzral1 + log(2d)) + +2C2/
log(2/8)
VN
N
2.N
where TG the smallest r such that the ground truth G satisfies F,..
A further result which applies in the presence of noise is provided in Appendix H
Experimental verification
In this section, experimentally validate the advantages of our adjusted regularisation strategies described in Subsection 3.3 In all experiments, we work with the square loss.
4.1 Experiments on synthetic data
We construct square data matrices in Rax* with a given rank r & d for several combinations of n, d. We provide each model with d-dimensional side information spanning the row and column spaces. The sampling distribution is a power-type law depending on A such that A = 0 yields uniform sampling (details in appendix). We compare three approaches: (I) Standard inductive matrix completion with the side information matrices X, Y (IMC) (2) Our smoothed adjusted regulariser A|M (for several values of a) (ATR 6 and finally (3) smoothed empirically adjusted regulariser ||M (for several values of a) (E-ATR). For each n E {100, 200) we evaluate the following d, combinations: (30, 4), (50, 6) and (80, 10). In order to study meaningful data-sparsity regime, in each case we sampled drw entries where w E {1, 2, 3, 4, 5). We show the most representative results here. More comprehensive results are provided in the supplementary material.
We observe that our methods outperform standard inductive matrix completion by significant margins in many regimes, even in the case of uniform sampling. Furthermore, the empirical version of our model actually often performs better than the exact one, which matches the observations made in 23 in the case of standard matrix completion. More detailed results are reported in the appendix.
'Note that in this synthetic context, it is actually possible compute M since the distribution is known.

---

ATR-005 ATR-10 ATR E-ATR-10
-
0.5
0.15
0.5
Weighted RMSE
68
0.10
03
044
0.05
02
00
(n.d) 0.00
2
(100,30)
(100,50
2000.00
1200000
(100 500
(100.00 00)
1200 000
(200 80)
(100
(200.
(200
(100.
Figure 1: Left: performance as a function of the data sparsity parameter w for n, d, 200, 80, 10.
Right: Performance on different n, d, combinations for
Legend: parameter to the right a.
Table 3: Results of real-world datasets (RMSE)
SoftImpute [6
IMCNF [19]
E-ATR-0.5
E-ATR-0.75
E-ATR-L.
Douban
0.9582
0.8197
0.7691
0.7614
0.8779
LastFM 2,4109
1.7612
1.6159
1.6943
2.3371
MovieLens 0.9280
0.9252
0.9056
0.9139
0.9262
Real data experiments
We evaluate the performance of our model three real life datasets: Douban, LastFM and MovieLens (further described in the supplementary). real data we work with following adjusted version of the model in [19]:
min M.Z N
Σ I(XMY + Z,, + G.g) + A D PM -E A2 (EJ)ER
AalD +
(18)
where D. É are defined as above based the side information matrices X, Y. and D1 E, are defined as D. except based on the side information matrices (7, 7). In particular, 2
7
the smoothed weighted trace norm of Z in the sense of (23]. We report results in Table 3 and note our method outperforms both SoftImpute and IMCNF, especially with appropriate smoothing.
Conclusion
In this paper, have provided the first distribution-fii ffree bounds for approximate recovery in inductive matrix completion with the trace norm with the following two desirable properties: (1) being non vacuous for identity community side information and (2) being completely independent of the size of the matrix. We further presented an adjusted regularisation strategy which relies on a careful rescaling along distribution-dependent directions that captures the interaction between the side information matrices and the sampling distribution. Our bounds, which concern both the standard regulariser (rate (d3/2 / log(d)) and our adjusted version (rate (drr log(d)) are almost exactly what one would obtain by replacing the size of the matrix with the size of the side information in the standard matrix completion bound. Thus, we have bridged the large gap between the theoretical guarantees for matrix completion and inductive matrix completion.
Broader impact
The work in this paper is theoretical and without any foresecable significant socictal impact.
Acknowledgements
The authors acknowledge support by the German Research Foundation (DFG) awards KI. 2698/2-1 and 2698/5-1, 1, as well as by the Federal Ministry of Science and Education (BMBF) awards 03 100033, 011S1800 MISS805AA and 03 B000EE..
10

---

References
[1] Zhao Kang, Chong Peng, and Qiang Cheng. Top-n recommender system via matrix completion. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
[2] Y. Koren, R. Bell, and C. Volinsky, Matrix factorization techniques for recommender systems. Computer, 42(8):30-37, 2009.
[3] Cho-Jui Hsieh, Yang Chiang, and Inderjit S. Dhillon. Low rank modeling of signed networks. Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '2, page 507-515, New York, NY, USA, 2012.
[4] Vassilis Kalofolias, Xavier Bresson, Michael Bronstein, and Pierre Vandergheynst. Matrix Completion on Graphs, arXiv e-prints, page arXiv:1408.11 1717, August 2014.
[5] Hao Ma, Dengyong Zhou, Chao Liu, Michael Lyu, and Irwin King. Recommender systems with social regularization. In Proceedings of the fourth ACM international conference Web search and data mining, pages 287-296, 2011.
[6] Rahul Mazumder, Trevor Hastie, and Robert Tibshirani. Spectral regularization algorithms for learning large incomplete matrices. Journal of Machine Learning Research, 11:2287-2322, August 2010.
[7] Trevor Hastie, Rahul Mazumder, Jason D. Lee, and Reza Zadeh. Matrix completion and low-rank svd via fast alternating least squares. Journal of Machine Learning Research, 16(104):3367- 3402, 2015.
[8] Rong Li, Yongcheng Dong, Qifan Kuang, Yiming Wu, Yizhou Li, Min Zhu, and Menglong Li. Inductive matrix completion for predicting adverse drug reactions (adrs) integrating drug-target interactions.
Chemometrics and Intelligent Laboratory Systems, 144:71 79, 2015.
[9] H. Wang. Y. Wei, M. Cao, M. Xu, W. Wu, and E. P. Xing. Deep inductive matrix completion for biomedical interaction prediction. In 2019 IEEE International Conference on Bioinformatics and Biomedicine (BIBM), pages 520-527, 2019.
[10] Nagarajan Natarajan and Inderjit S. Dhillon. Inductive matrix completion for predicting gene and disease associations. Bioinformatics, 30(12):600-ig 06 2014.
[11] Mark Herbster, Stephen Pasteris, and Lisa Tse, Online matrix completion with side information. Advances in Neural Information Processing Systems, 33, 2020.
[12] Xiao Zhang, Simon Du, and Quanquan Gu. Fast and sample efficient inductive matrix comple- tion via multi-phase procrustes flow. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 5756-5765, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
[13] Aditya Krishna Menon and Charles Elkan. Link prediction via matrix factorization. In Machine Learning and Knowledge Discovery in Databases, pages 437-452, Springer Berlin Heidelberg, 2011.
[14] Tianqi Chen, Weinan Zhang, Qiuxia lu, Kailong Chen, Zhao Zheng, and Yong Yu. Svdfeature: toolkit for ceature-based collaborative filtering. The Journal of Machine Learning Research, 2012.
[15] Fabian Jirasek, Rodrigo A. S. Alves, Julie Damay, Robert Vandermeulen. Robert Bamler, Michael Bortz, Stephan Mandt, Marius Kloft, and Hans Hasse. Machine learning in thermo- dynamies: Prediction of activity coefficients by matrix completion. The Journal of Physical Chemistry Letters, 11(3):981-98) 2020.
[16] Prateek Jain and Inderjit S. Dhillon. Provable inductive matrix completion. CoRR, abs/1306.0626, 2013.

---

[17] Miao Xu, Rong Jin, and Zhi-Hua Zhou. Speedup matrix completion with side information: Application to multi-label learning. Proceedings of the 26th International Conference on Neural Information Processing Systems- Volume 2, NIPS' 13, page 2301-2309, Red Hook, NY, USA, 2013. Curran Associates Inc.
[18] Jin Lu, Guannan Liang, Jiangwen Sun, and Jinbo Bi. A sparse interactive model for matrix completion with side information. In D. Lee, M. Sugiyama, U. Luxburg, Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
[19] Kai- Yang Chiang, Inderjit S. Dhillon, and Cho-Jui Hsieh. Using side information to reliably learn low-rank matrices from missing and corrupted observations. Journal of Machine Learning Ressearch, 2018.
[20] Kai- Yang Chiang, Cho-Jui Hsieh, and Inderjit Dhillon. Matrix completion with noisy side information. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28, Curran Associates, Inc., 2015.
[21] P. Giménez-Febrer, A. Pagès-Zamora, and G. B. Giannakis. Generalization error bounds for kernel matrix completion and extrapolation. IEEE Signal Processing Letters, 27:326-330, 2020.
[22] Ohad Shamir and Shai Shalev-Shwarzz. Collaborative filtering with the trace norm: Learning, bounding, and transducing. Proceedings of the 24th Annual Conference on Learning Theory, volume 19 of Proceedings of Machine Learning Research, pages 661-675 PMLR, 2011.
[23] Rina Foygel, Ohad Shamir, Nati Srebro, and Russ R Salakhutdinov. Learning with the weighted trace-norm under arbitrary sampling distributions. In Shawe-Taylor, R. S. Zemel, P. L. Bartlett, Pereira, and K. Q. Weinberger, editors, Advances Neural Information Processing Systems 24, pages 2133-2141. Curran Associates, Inc., 2011.
[24] Kai Zhong, Zhao Song, Prateek Jain, and Inderjit S Dhillon. Provable non-linear inductive matrix completion. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neurul Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[25] Ohad Shamir and Shai Shalev-Shwartz. Matrix completion with the trace norm: Learning, bounding, and transducing. Journal of Machine Learning Research, 15:3401-3423, 2014.
[26] Nathan Srebro and Russ R Salakhutdinov. Collaborative filtering a non-uniform world: Learning with the weighted trace norm. In J. D. Lafferty, C. I. Williams, J. Shawe-Taylor, R. S. Zemel, and A. Culotta, editors, Advances in Neural Information Processing Systems 23, pages 2056-2064 Curran Associates, Inc., 2010.
[27] Emmanuel J. Candès and Terence Tao. The power of convex relaxation: Near-optimal matrix completion. IEEE Transactions Information Theory, 56(5): -0800, May 2010.
[28] Benjamin Recht. A simpler approach to matrix completion. Journal of Machine Learning Research, 12muull:3411-3440 December 2011.
[29] Raghunandan Keshavan, Andrea Montanari, and Sewoong Oh. Matrix completion from noisy entries. In Y. Bengio, D. Schuurmans, J. D. Lafferty, C. K. I. Williams, and A. Culotta, editors, Advances in Neural Information Processing Systems 22, pages 952-960. Curran Associates, Inc., 2009.
[30] Emmanuel J. Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 966):717, 2009.
[31] Yudong Chen. Incoherence-optimal matrix completion. Information Theory, IEEE Transactions 61. 10 2013.
[32] Lijun Ding and Yudong Chen. Leave-one-out approach for matrix completion: Primal and dual analysis. IEEE Transactions Information Theory, 66:7274-7301, 2020.
12

---

[33] P. Giménez-Febree A. Pagès-Zamora and G. B. Giamnakis. Matrix completion and extrapolation via kernel regression. IEEE Transactions on Signal Processing, 67(19))5004-5000 2019.
[34] Tony Cai and Wen-Xin Zhou. Matrix completion via max-norm constrained optimization. Electronic Journal of Statistics, 10(1):1493 1525, 2016.
[35] Nathan Srebro and Adi Shraibman. Rank, trace-norm and max-norm. In Peter Auer and Ron Meir, editors, Learning Theory, pages 545-560, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.
[36] Antoine Ledent, Rodrigo Alves, and Marius Kloft. Orthogonal inductive matrix completion. IEEE Transactions on Neural Networks and Learning Systems, pages 1-12, 2021.
[37] Rodrigo Alves, Antoine Ledent, Renato Assunção, and Marius Kloft. An empirical study of the discreteness prior in low-rank matrix completion. NeurlPS 2020 Workshop on Pre- registration in Machine Learning, volume 148 of Proceedings of Machine Learning Research, pages 111-125. PMLR, Dec 2021.
[38] Qiaosheng Zhang, Vincent Tan, and Changho Suh. Community detection and matrix completion with social and item similarity graphs. IEEE Transactions on Signal Processing, 69:917-931, 01 2021.
[39] Qiaosheng Eric Zhang, Geewon Suh, Changho Suh, and Vincent Y. F. Tan. MC2G: an efficient algorithm for matrix completion with social and item similarity graphs CoRR, abs/2006.04373, 2020.
[40] Rina Foygel, Nathan Srebro, and Russ R Salakhutdinov. Matrix reconstruction with the local max norm. F. Pereira, C. J. C. Burges, L. Bottou, and Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012.
[41] Muhan Zhang and Yixin Chen. Inductive matrix completion based on graph neural networks. In International Conference on Learning Representations, 2020.
[42] Qitian Wu, Hengrui Zhang, Xiaofeng Gao, Junchi Yan, and Hongyuan Zha. Towards open-world recommendation: An inductive model- based collaborative filtering approach. In International Conference on Machine Learning, pages 1132--1139, PMLR, 2021.
[43] Rafal Latala. Some estimates of norms of random matrices. Proceedings of the American Mathematical Society, 1273-112233 2005.
13


Reviews:
[{"review_id": "IFUe1vDZ1u4", "reviewer": "Reviewer_FcbJ", "summary": "This paper develops theoretical results for IMC in a uniform and distribution free setting. It also develops an algorithm for the adjusted regularisation in (11). ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think the paper is solid. Below I have a few questions and would like to hear the authors' responses. \n1. From line 43 to 45, they mentioned the sample complexity in a approximate recovery setting. This guarantees has epsilon ^2 dependence. Is all the results mentioned in the paper (Table 1 and 2) has this epsilon dependence? \n\n2. The formulation (1) (2) (4) and (11) are all penalized optimization problem. Yet theorems and propositions in Section 3 are all constraint version, e.g., min sth subject to some constraints. Even though there is a general relation between the two via the lagrangian multiplier, the multiplier will depend on the data in general rather than a fixed choice. Can the author comment on how to choose the parameter lambda in (1)(2)(4) and (11) in order to achieve meaningful theoretical results? \n\n3. Most of the theorem requires the loss to be bounded and Lipschitz. But the loss in (1) (2) and (4) are not lipschitz and bounded if we consider the whole space of the matrices M or Z. With the constraint set in theorems and propositions in Section 3, can the author comment on how large the bounded parameter b of the loss l and the lipschitz constant of the loss l will be if we use the square loss? Will the results in section 3 become very bad if we use square loss?\n\n4. What is the weighted version in Table 2? Is it the setting in Section 3.4 and 3.5? Can I understand it as the case that this is also the distribution free setting but we use a different optimization problem to recover the matrix?\n\n5.In line 54 what is O(r^2)? or you mean rd^2? \n\n6. In the tables, I think it worth mentioning the following results \nChen, Yudong. \"Incoherence-optimal matrix completion.\" IEEE Transactions on Information Theory 61, no. 5 (2015): 2909-2923.\nThis paper discusses the MC and IMC setting with a better incoherence dependence. \n\nDing, Lijun, and Yudong Chen. \"Leave-one-out approach for matrix completion: Primal and dual analysis.\" IEEE Transactions on Information Theory 66, no. 11 (2020): 7274-7301.\nThis one has the best sample complexity O(drlog(d)log(r)) for exact matrix completion, which is better than the results in  Table 1. So this is the state-of-art.  \n\n7. Why r = M/(Sd1d2) is considered as the relaxation of rank in line 165?  I think r = M/S in general is the rank. And in line 168, why |M|_*/S<=sqrt(d1d2*r)? You defined rho in line 167 and it is not used.\n\n8. Perhaps in Line 244, you can mention q and kappa are defined in (9)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some future work is mentioned in the conclusion. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "FSoXu6yoDKI", "reviewer": "Reviewer_N3AC", "summary": "The paper improves convergence rates for Inductive Matrix completion in the distribution-free setting. Authors introduced a new version of the IMC objective and experimentally demonstrate that it may performs better than the standard one.", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written and many explanations are displayed to readers that are not familiar with the domain. The paper is outside of my area of expertise and I cannot speak confidently about its correctness.\n\nThe empirical section seems to be light.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "DiT_8hsvseu", "reviewer": "Reviewer_7dax", "summary": "This paper studies generalisation bounds of Inductive Matrix Completion (IMC), a variant of the classic matrix completion (MC) problem. The main contribution of the paper is improved bounds in the distribution-free setting. Moreover, the authors introduce the (smoothed) adjusted trace-norm minimization strategy, for which they show non-trivial guarantees under arbitrary sampling. These two results generalize similar results previously proved for standard matrix completion to IMC. ", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n1. The problem studied is fundamental and well-motivated.\n2. Interesting theoretical results are proved, and the proof techniques seems quite non-trivial.\n3. Empirical results show that the proposed methods outperform previous IMC on various synthetic datasets and real problems.\n\nWeakness:\nThe notation and technical proofs are quite dense, and the theoretical results are not as clean as those for standard matrix completion/sensing problems. Thus I think potential audience of this paper might be limited.\n\nI am not familiar with the literature of generalization bounds of IMC, so it’s difficult for me to give a precise evaluation on the technical novelty and depth of the proofs. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "86W_sfz0AuD", "reviewer": "Reviewer_XdTE", "summary": "This paper analyzes inductive matrix completion theoretically and conducts numerical experiments to demonstrate the results. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. In the first paragraph of Section 3, it says \"We have one fixed loss function $l$ used through the paper which is both Lipschitz with constant $\\ell$ and bounded by $b$\". This choice of loss function $l$ seems quite unusual since the commonly used squared loss function does not satisfy this condition clearly. What's more, in Section 4, it says square loss is adopted in all experiments. But square loss does not fit in the theoretical results proved in this paper. There seems no explanations about this in the paper. \n\n2. Regarding the choice of loss function $l$, can you give some examples of practical and popular choices?\n\n3. There are some typos. For example, on page 2 below equation (3), since $\\boldsymbol{x}$ is defined to be the maximum norm of row of $X$, the definition of $\\boldsymbol{x}$ should be $\\boldsymbol{x}:=\\Vert X\\Vert_{2,\\infty}$ rather than $\\boldsymbol{x}:=\\Vert X^{\\top}\\Vert_{2,\\infty}$.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper focuses on theoretical analysis. It's expected that the paper does not have direct negative societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies inductive matrix completion with side information. They provide distribution-free bounds that improve upon previous work. New guarantees are also obtained for weighted nuclear norm minimization under arbitrary sampling. The reviewers agree that this paper makes solid contributions and involves interesting techniques. On the other hand, the reviewers also find that the authors should better explain the Lipschitz/boundedness assumptions as well as the novelties for the weighted trace norm. and the clarity of the presentation can be improved.
Decision: Accept (Poster)