Fine-grained Generalisation Analysis of Inductive Matrix Completion
Year: 2022

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 inductive matrix completion: (1) In the distribution-free setting, we prove sample complexity bounds improving the previously best rate of rd to d3{2 ? r logpdq, where d is the dimension of the side information and r is the rank. (2) We introduce the (smoothed) adjusted trace-norm minimization strategy, an inductive analogue of the weighted trace norm, for which we show guarantees of the order Opdr logpdqq 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.

text: ? r logpdq, where d is
the dimension of the side information and r is the rank. (2) We introduce the (smoothed) adjusted trace-norm minimization strategy, an inductive analogue of the weighted trace norm, for which we show guarantees of the order Opdr logpdqq 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.

heading: 1 Introduction
text: Matrix completion (MC) is the machine learning problem of recovering the missing entries of a partially observed matrix. It is the go-to approach in various application domains such as recommender systems [1, 2] and social network analysis [3, 4, 5]. The SoftImpute algorithm [6, 7] is among the most popular MC methods. It solves the following convex problem encouraging low-rank solutions:
min ZPRmˆn
1 2 }PΩpZ ´ Gq}2Fr ` λ}Z}˚, (1)
where PΩ denotes the projection on the set Ω of observed entries, G is the ground truth matrix, and } .}˚ denotes the nuclear norm (i.e., the sum of the matrix’s singular values). Besides the incomplete matrix, additional information may be available in applications such as movie recommendation or drug interaction prediction [8, 9, 10, 11]. For instance in movie recommendation, one may have access to the movies’ genres, their synopsis, the gender and occupation of the users, or a friendship network between the users. Inductive matrix completion (IMC) [11, 12, 13, 14] exploits such side information. It assumes that the side information is summarized in matrices X P Rmˆd1 and Y P Rnˆd2 , with the row vectors representing the users and items, respectively. IMC then optimizes the following objective function
min MPRd1ˆd2
1 2 }PΩpXMY J ´ Gq}2Fr ` λ}M}˚. (2)
This model has been used in many domains also beyond movie recommendation [8, 10, 15].
In this paper, we contribute to a 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 (NeurIPS 2021).
loss which decreases with the number of samples. Our best results concern the distribution-free case, meaning that our bounds are valid for any sampling distribution. This is in sharp contrast to 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 [19, 20, 21], as we obtain near optimal bounds in situations where the state of the art bounds are vacuous, as is explained below.
Although for uniform sampling, near-tight exact recovery bounds of Oprd logpdq logpnqq exist1 for IMC [16, 17], the approximate recovery case (especially in a distribution-free setting) is far less understood. The state-of-the-art distribution-free results for IMC were proved in [19, 20] (and in [21] for a kernel formulation of IMC) and, expressed in terms of generalisation error bounds, scale as
O ´ xyM a 1{N ¯ , (3)
where x :“ }XJ}2,8 “ maxu }X . ,u}2 is the maximum norm of a left side information vector (row of X), N is the number of available samples, and y :“ }Y J}2,8 “ maxv }Y . ,v}2 is the maximum norm of a right side information vector (row of Y ). This implies that reaching a given loss threshold ϵ requires Opx2y2M2{ϵ2q entries, where M is a bound on the nuclear norm of M . In this case, we say that the ’sample complexity’ is Opx2y2M2q. 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, we have x “ y “ 1, yielding a sample complexity of OpM2q. Since }M}2˚ „ d2r, this yields a bound of order rd2.
Such bounds have a remarkable property: they do not depend on the size n 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 are vacuous when X “ I and Y “ I , since the required number of entries Oprd2q “ Oprn2q then grows faster than the total number of entries n2. This is despite the fact that in that situation, distribution-free bounds for standard matrix completion yield a sample complexity of Opn3{2 ? rq for the standard regulariser [22] and Opnr logpnqq for a modified regulariser (the smoothed weighted trace norm from [23]). Thus, these existing distribution-free 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] or from a wide variety of different sources). To reinforce that point, note that any side information with a strong cluster structure2 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-free bounds for IMC which combine both of the following advantages: (1) a lack of dependence in the size of the original matrices, and (2) a more refined dependence on 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-the-art MC results. More precisely, our first contribution is to provide a bound of order Opd3{2 ? r logpdqq 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, we construct analogues of the ideas of [23, 26] for the IMC setting: we begin by showing a bound of order Oprd logpdqq for a class of distributions with certain uniformity assumptions (our "uniform inductive marginals"), and then design a 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 as 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.
1with some orthogonality assumptions on the side information 2where the users and items are approximately split into ’communities’, see also Appendix A
1. We provide distribution-free generalisation bounds for the inductive matrix completion model (2) (assuming a fixed upper bound on the nuclear norm) which scale like Opd3{2 ? r logpdqq where r
is a soft relaxation of the rank.
2. In the case of uniform or approximately uniform sampling, we provide a bound of order Oprd logpdqq for approximate recovery.
3. We introduce a modified version of the IMC objective (2), which we refer to as adjusted trace norm regularsation (ATR). An empirical version E-ATR is also introduced and both achieve bounds of order Oprd logpdqq in the distribution-free setting.
4. We experimentally demonstrate on synthetic data that our adjusted regulariser outperforms the standard IMC objective (2) in many situations.
5. We incorporate our method into a model involving a non-inductive term and evaluate it on real-life datasets, demonstrating substantially improved performance.
This paper is organized as follows. In Section 2 we review some related work. In Section 3 we introduce our main results. Finally, in Section 4 we present our experimental results.

heading: 2 Related work
text: 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 distributionfree bounds. In exact recovery, the matrix is assumed deterministic, and we 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, 18, 29]. Approximate recovery theory is typically expressed in terms of uniform generalisation bounds over a function class using a 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 Opnr log2pnqq for exact recovery (proved in the series of breakthrough papers [27, 28, 30]) and Opnr logpnqq for approximate recovery [23]. In [31, 32], an improved rate of nr logpnq logprq (for exact recovery) was shown. The most closely related papers to ours are [22] and [23], which both work only on standard matrix completion without side information. In [22], a bound of order Opn3{2 ? rq was obtained in the distribution-free setting for matrix completion with the trace norm, whilst in [23], rates of Oprn logpnqq are shown for sampling with uniform marginals and for a smoothed version of the weighted trace norm regulariser in the distribution-free case. We almost perfectly extend most of the results from both papers to the inductive case, which requires many technical modifications.
Within the IMC framework the closest works are those which also deal with approximate recovery in the non uniform sampling case: [21, 33, 19, 20]. Their bounds, presented in many different contexts, translate to sample complexities of type Oprd2q. Other celebrated works in the theoretical study of IMC include: [16] and [17], which showed rates of order d2r3 logpdq and rd logpdq logpnq respectively for exact recovery with uniform sampling, together with other important contributions (see appendix). In the case of exact recovery, the rate of rd logpdq logpnq was obtained only under the assumption that the side information matrices have orthonormal columns. Some bounds use a completely different regulariser (such as the max norm) to achieve better rates [34, 35] etc. These works also do not involve side information.
In Figures 1 and 2, we summarize state-of-the-art (s.o.t.a.) results in both MC and IMC. Note the problem of exact recovery in the distribution-free case is ill-defined (hence the N/As in our table). In approximate recovery bounds, we omit a factor of 1{ϵ2, where ϵ is the tolerance threshold in terms of expected loss), as this factor is present in all approximate recovery bounds 3. In exact recovery bounds, the rate is the order of magnitude of the threshold past which exact recovery occurs with high probability.
3To our best knowledge, all results show a decline in population expected loss of the order of a
1{N where N is the sample size
Other related works include (IMCNF) [19, 20], which proposed the following model:
min 1
2
ÿ
pi,jqPΩ |Gi,j ´ pXMY J ` Zqi,j |2 ` λ1}M}˚ ` λ2}Z}˚, (4)
where λ1, λ2 are regularisation parameters, Gi,j denotes the observed entries and the predictors take the form pXMY J ` Zq. This model relies on the cross-validated hyperparameters λ1, λ2 to balance the importance of the side information. The authors also showed results based on a combination of a bound for the inductive term XMY J and a bound for the non inductive term Z. The non inductive terms in the bounds are similar to [22], whilst the bounds for the inductive term are proved from scratch and have also later appeared in a different form in [21, 33] together with a kernel formulation of IMC. In Subsection 4.2 we combine our framework with this strategy to reach competitive results.
In [36], the authors introduce a model consisting of a sum of mutually orthogonal IMC terms together with an explicit optimization strategy in the specific case where the available side information consists in partitions of the users and items into communities. In [37], the authors further extend the model to learn the community membership functions together with the ground truth matrix, based only on the sampled entries. The case of a single IMC term where the side information is in the form of a community partition is useful to develop intuition into the equivalent roles of d1, d2 in our bounds versus m,n in MC bounds. Whilst generalization bounds were proved in [36] with a similar scaling as our bound from Thm 3.1 (and in particular are better than the state-of-the-art IMC bounds if applied to this situation), they only apply to the specific case of 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 or 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 XMY J through a 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 on the side information is better in our case. 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].

heading: 3 Main results
text: Notation: We observe N entries of a ground truth matrix G P Rmˆn which are sampled i.i.d (with replacement) through an arbitrary distribution p: we draw pi, jq P t1, ..,mu ˆ t1, ..., nu with probability pi,j where ř i,j pi,j “ 1. The sampled entries ξ1, ξ2, . . . , ξN P t1, 2, . . . ,mu ˆ
t1, 2, . . . , nu form a multiset Ω: our setting allows for the observations to be noisy with a 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 : R Ñ R we will write ř
pi,jqPΩ fpGi,jq for the sum of the images of the observations, counted as many times as necessary 4. We assume we are given side information matrices X P Rmˆd1 and Y P Rnˆd2 . The maximum L2 norm of a row of X (resp. Y ) is denoted by x (resp. y). The minimums are denoted by x and y respectively. The row vectors of X (resp. Y ) are also written xi for i ď 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 }A}˚ denotes the nuclear norm of A. We have one fixed loss function l used throughout the paper which is both Lipschitz with constant ℓ and bounded by b. For convenience we also frequently write d instead of maxpd1, d2q. In the appendix, we provide a complete table of notations (Table K.1) that includes all notations introduced throughout the paper.
We now present our results, starting with the distribution-free 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 it provides.

heading: 3.1 Distribution-free guarantees for the standard IMC objective
text: For a constant M P R, we define the function class: FM “ ␣ XMY J : }M}˚ ď M (
, which contains all predictors XMY J where M has its spectral norm bounded by S. Our first main result is a uniform generalisation bound for the loss minimiser within this function class. Below we use the shorthand lpAq (resp. l̂SpAq or even lSpAq) for Epi,jq„pplpAi,j , Gi,j ` ζi,jqq (resp. ř
pi,jqPΩ lpAi,j , Gi,j ` ζi,jq{N ), the overall expected (resp. empirical) loss associated to matrix A P Rmˆn. In particular, in the noiseless setting, infZPFM lpZq “ 0 as long as }G}˚ ď M. Theorem 3.1. Fix any target matrix G and distribution p. Define ẐS “ argminpl̂SpZq : Z P FMq. For any δ P p0, 1q, with probability (w.p.) ě 1 ´ δ over the draw of the training set Ω we have
lpẐq ď inf ZPFM lpZq ` C
»
–
d ℓbxyM ? d
N Ψ ` b? N ` xyℓM ` ℓ N logp2dq
fi fl ` 4b c
logp2{δq 2N , (5)
where C is a universal constant, b is a bound on the loss, ℓ is the Lipschitz constant of the loss l, and Ψ “ „ a logp2dq ` b logpNp20M2ℓ ? drx2y2s{b ` 1q ȷ is a logarithmic quantity. Furthermore, in
expectation over the training set we have:
lpẐq ď inf ZPFM lpZq ` C
»
–
d ℓbxyM ? d
N Ψ ` b? N ` xyℓM ` ℓ N logp2dq
fi fl ` 20b c 1
N . (6)
The proof is provided in Appendix A. Assuming that ℓ, b are treated as constants, the above bound on the generalisation gap lpẐq ´ infZPFM lpZq scales like
O
¨
˝ xyM N logpdq `
d xyM ? d
N
”
a logpdq ` a logpNq ` a logpxyMq ı
˛
‚. (7)
If we further think of the maximum entry of the core matrix M as bounded by a constant, M scales like ? d1d2r where r is the rank of M . Assuming the rescaling is also set so that x,y are constants, the above yields a sample complexity of
O
˜? d1d2 ? dr logpdq ϵ2 ¸ ,
4More rigorously the observations are i.i.d of the form pξo, ξ̄oq with ξo P t1, 2, . . . ,mu ˆ t1, 2, . . . , nu and ξ̄o P R and write
řN o“1 fpξ̄oq instead of ř pi,jqPΩ fpGi,jq, and it should be assumed that the "ground truth" values G (are defined so as to) minimize EplpGξ, ξ̄qq for our loss function l over the joint distribution of ξ, ξ̄
where ϵ is the tolerance threshold. Indeed, the a
logpNq term can be treated via the following simple observation: If N ě Θ logpΘq and Θ is sufficiently large then
N logpNq ě Θ logpΘq logpΘq ` logplogpΘqq ě Θ logpΘq 2 logpΘq ě Θ{2.
Remark on the proof technique: The proof of the result in [22] relies on a lemma of Latala (lemma A.1) from [43] for random matrices with i.i.d. 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 1, the partial sums of the Rademacher variables concentrate trivially, whilst on group 2, the entries are well spread out and Lemma A.1 limits the spectral norm similarly to the uniform case. The proof is about carefully balancing those two contributions.
In our inductive situation, using the same split can only yield bounds of the type (3) which are well 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, we split between high and low energy orientations corresponding to pairs pX . ,u, Y . ,vq of columns of the side information matrices. To achieve this aim, we use the rotational invariance of the trace operator and equivalently express the Rademacher averages in inductive space (Rd1ˆd2). However, the entries of the resulting matrix are certainly not independent, which makes it impossible to apply the concentration results from [43]. Instead, we must rely again on the matrix Bernstein inequality F.4. Obtaining a covariance structure that is amenable to 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.

heading: 3.2 Generalisation bounds for the trace norm regulariser under a uniformity assumption
text: We now move to our second main contribution, which is a broad generalisation of most of the results of [23] to the inductive case. In 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 in Appendix B) is original to 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 XMY J with }M}˚ ď M. Let MS “ argmin}M}˚ďM ř
ξPΩ lppXMY Jqξ, Gξ ` ζξq be the trained matrix M and M˚ “ argmin}M}˚ďM ElppXMY
Jqξ, Gξ ` ζξq be the optimal M when M is restricted by }M}˚ ď M. Write also ZS “ XMSY J and Z˚ “ XM˚Y J.
Write K :“ max „ b d1 }XJX}
m }Y }2Fr n ,
b
d2 }Y JY }
n }X}2Fr m
ȷ
. Under uniform sampling, w.p. ě 1 ´ δ:
lpZSq ´ lpZ˚q ď 8ℓK
? rdp1 ` a
logp2dqq? N ` 12ℓ N Mxyp1 ` logp2dqq ` b c logp2{δq 2N , (8)
where ? r “ M{ ? d1d2 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"):
@i, ÿ
i,j
pi,j}yj}2 “ }Y }2Fr mn and @j, ÿ
i,j
pi,j}xi}2 “ }X}2Fr mn . (9)
Remarks: If }xi} and }yj} are constant over i and j, then the above conditions (9) reduce to a requirement of uniform marginal probabilities. Note that ? r “ pM{ ? d1d2q acts as a soft relaxation of the rank of M since if M P FM and the entries of M are bounded by 1 then rankpMq ď r. If X “ I and Y “ I , then conditions (9) reduce to the uniform marginals condition from [23]. In particular, we see that in the case of identity side information, we require Opdr logprqq samples to reach a given accuracy. However, the result above is deeper when the side information is non trivial. Indeed, the quantity maxp a
}XJX}}Y }2Fr, a }Y JY }}X}2Frq, which equals d “ maxpd1, d2q 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 ρ, then this quantity will approach ρ. We discuss this in more details in the appendix.
To prove the above result, we will show a 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 a distribution-dependent inner product x ., .yl (resp. x ., .yr) on the column space of X (resp. Y ): For two vectors u1, u2 P Rm (resp. v1, v2 P Rn) we define xu1, u2yl “ řm i“1 u 1 iu 2 i qi (resp. xv1, v2yr “ řn j“1 v 1 j v 2 jκj) where the qis and κjs are defined by
qi “ n ÿ
j“1 pi,j}yj}2 @i ď m κj “
m ÿ i“1 pi,j}xi}2 @j ď n. (10)
We now define the vector σ1 P Rd1 (resp. σ2 P Rd2 ) as the vector of singular values of the matrix X (resp. Y ) with respect to (w.r.t) the inner product x ., .yl (resp. x ., .yr). In other words, the entries of σ1 P Rd1 (resp. σ2 P Rd2) are the square roots of the eigenvalues of the symmetric matrix L :“ XJ diagpqqX P Rd1ˆd1 “ ř
i,j pi,jxix J i }yj}2 (resp. R :“ Y J diagpκqY “ ř i,j pi,jyjy J j }xi}2 P
Rd2ˆd2 ). We also write σ1˚ “ maxpσ1q and σ2˚ “ maxpσ2q. Proposition 3.2. With the same notation as in Proposition 3.1, w.p. ě 1 ´ δ over the draw of the training set Ω:
lpZSq ´ lpZ˚q ď 8ℓ? N Mmaxpσ1˚, σ2˚qp1 ` a logp2dqq ` 12ℓ N
Mxyp1 ` logp2dqq ` b c logp2{δq 2N .
Remarks: Note that both σ1 and σ2 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, rσ1˚s2 is the maximum user (marginal) probability which scales like 1{d1 for approximately uniform marginals. Similarly σ2˚ „ 1{d2, yielding a sample complexity bound of order dr logpdq as expected.

heading: 3.3 Proposed adjusted regularisers and notation
text: 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 a matrix Z is defined as } ? DZ ? E}˚ where D P Rmˆm (resp. E P Rnˆn) 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 Γ “ ř i,j pi,j}xi}2}yj}2. Our method is based on a careful distribution-dependent rescaling of the matrix M . The idea is that we must look at the principal directions (singular vectors) of the side information matrices, but computed with respect to a distribution-sensitive 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 “ XJ diagpqqX (resp. L “ Y J diagpκqY ) from above to write it P´1DP (resp. Q´1EQ). We also define empirical versions of those quantities: pΓ “ 1N ř i,j hi,j}xi}2}yj}2 where hi,j is the number of times that entry pi, jq was sampled: hi,j “ řN
o“1 1ξo“pi,jq “ #pΩ X tpi, jquq; q̂i “ ř j hi,j N }yj} 2, κ̂j “ ř i hi,j N }xi}
2, pL “ XJ diagpq̂qX , pR “ Y J diagpκ̂qY , and their diagonalisations pP´1 pD pP and pQ´1 pE pQ. We can now write our predictors
XMY J “ XP´1D 12 rD´ 12PMQ´1E´ 12 sE 12QY J “ X pP´1 pD 12 r pD´ 12M pE´ 12 s pE 12 pQY J. (11)
The simplest version of our proposed algorithm is to regularise rD´ 12PMQ´1E´ 12 s 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 D´ 1 2 and E´ 1 2 will be very large. To obtain
good bounds, we tackle this issue by forcing the entries of D, pD,E, pE to be bounded below, which
we achieve via smoothing: fixing a parameter α P r0, 1s, we define rD “ αD ` p1 ´ αqΓI{d1 and rE “ αE ` p1 ´ αqΓI{d2 where I is the identity matrix. Similarly, qD “ α pD ` p1 ´ αqpΓI{d1 and qE “ α pE ` p1 ´ αqΓ̂I{d2.
We also define accordingly M 1 “ D 12PMQ´1E 12 ; xM “ pD 12 pPM pQ´1 pE 12 ; ĂM “ rD 12PMQ´1 rE 12 ; and |M “ qD 12 pPM pQ´1 qE 12 ; as well as similarly rX “ XP´1 rD´ 12 , X 1 “ XP´1D´ 12 , pX “ X pP´1 pD´ 1 2 , qX “ X pP´1 qD´ 12 , rY “ Y P´1 rE´ 12 , Y 1 “ Y P´1D´ 12 , pY “ Y pQ´1 pD´ 12 , qY “ Y pQ´1 qD´ 1 2 . Thus XMY J “ X 1M 1rY 1sJ “ rXĂM rY J “ pXxM pY J “ qX|M qY J.
Proposed models: We then propose a variety of adjusted regularisation strategies as follows by replacing the regularisation of M by that of M 1, ĂM , xM 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 M
1
N
ÿ ξPΩ lppXMY Jqξ, Gξ ` ζξq ` λ} qD 1 2 pPM pQ´1 qE 1 2 }˚. (12)
Remark: Similarly to the matrix case the smoothing parameter α is set to 12 in all theorem statements 5. In the experiments, we vary α as indicated.
We will prove results for the empirical risk minimiser belonging to the following function classes: rFr :“ ! XMY J : }ĂM}˚ ď ? rΓ ) qFr :“ ! XMY J : }|M}˚ ď ? rpΓ ) , (13)
corresponding to the smoothed and smoothed empirical versions of our algorithm. Note that the factors of Γ are added purely for convenience in the final formula, so that we can understand the final formulae in terms of a soft concept of "rank". Indeed we have
} rD 12 }2Fr ď d1 Γ 2d1 ` 1 2 } a diagpqqX}2Fr “ p1{2qΓ ` p1{2q ÿ
i,u
X2i,u ÿ
j
pi,j}yj}2 “ Γ, (14)
and similarly } rE 12 }2 ď Γ. Thus if }PMQ´1}8 ď 1 and rankpMq ď ρ, we have }ĂM}˚ ď ? ρ}ĂM}Fr ď ? ρ b ř u,vr rD 1 2 u s2r rE 1 2 v s2rPMQ´1s2i,j ď ? ρ}PMQ´1}8 b ř u,vr rD 1 2 u s2r rE 1 2 v s2 ď ? ρΓ. Similarly, }|M}˚ À ? ρpΓ under the condition } pPM pQ´1}8 À 1.

heading: 3.4 Generalisation bounds for the smoothed adjusted trace norm
text: Although knowing the distribution is not realistic, it is instructive to see that one can obtain guarantees of order Opdr logpdqq for the function class rFr as a reasonably straightforward extension of the ideas developed for Proposition 3.2. The proof is provided in Appendix C.
Proposition 3.3. Let ĂMS “ argmin}ĂM}ď?rΓ ř ξPΩ lpp rXĂM rY Jqξ, Gξ ` ζξq be the trained matrix ĂM and rZ˚ “ argminZP rFr ElpZξ, Gξ ` ζξq be the optimal rZ when the predictors are restricted to the class rFr. Let also rZS “ rXĂMS rY J. We have w.p. ě 1 ´ δ:
lp rZSq ´ lp rZ˚q ď 16ℓ
? Γ ? r ? dp1 ` a
logp2dqq? N
` 24ℓxy ? d1d2rp1 ` logp2dqq
N ` b
c
logp2{δq 2N .

heading: 3.5 Generalisation bounds for the smoothed empirically adjusted trace norm
text: Below is a more challenging result (proof in Appendix D) which concerns the function class qFr corresponding to the empirically smoothed regulariser.
Theorem 3.2. Fix any target matrix G and distribution p. Define qZS “ argminpl̂SpZq : Z P qFrq where l̂SpZq “ 1N ř ξPΩ lpZξ, Gξ ` ζξq. For any δ P p0, 1q, w.p. ě 1 ´ δ
lp qZq ď inf ZP rFr lpZq ` C “
ℓ ? rγpx ` yq2 ` b ‰
d
γ2d logpdδ q N , (15)
5It is trivial to extend the proofs to arbitrary α at the cost of a factor of 1{minpα, 1 ´ αq.
where γ “ x 2 y2
x2y2 and C is a universal constant. In particular, in expectation over the draw of the training set we have
lp qZq ď inf ZP rFr lpZq ` 2C “
ℓ ? rγpx ` yq2 ` b ‰
c
γ2d logpdq N . (16)
The significance of this result is 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 logpdq, meaning that our distribution-dependent transformations have completely removed the negative effects of non-uniformity on the sample complexity. Note the proof requires careful technical variations compared to the proof of the comparable results in [23]. As an example, Lemma E.1 is the equivalent of Lemma 2 in page 8 of the supplementary in [23] (whose proof is far shorter).

heading: 3.6 Variations on the optimization problems
text: 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, it is also possible to modify the results (under some boundedness assumptions) to make them apply to lagrangian formulations such as (18) (1), (2). In typical contexts where the entries are known to be bounded, this can even be done with the square loss. As an example, we consider the following immediate corollary of Proposition 3.3 and its global version C.1 (appendix): Corollary 3.4. Assume that all of the entries of the ground truth are bounded by a constant C, and that they are observed without noise. Let Z# “ XM#Y J be the solution to the following optimization problem:
min M
} rD 12PMQ´1 rE 12 }˚ subject to rXMY Jsξ “ Gξ @ξ P Ω. (17)
Let ΦCpxq “ signpxqminp|x|, Cq. For any ℓ-Lipschitz loss l, we have (with probability ě 1 ´ δ)
lpΦCpZ#qq ď 8ℓ
? Γ ? drGp1 ` a
logp2dqq? N
` 12ℓxy ? d1d2rGp1 ` logp2dqq
N ` 2Cℓ
c
logp2{δq 2N .
where rG is the smallest r such that the ground truth G satisfies G P rFr.
A further result which applies in the presence of noise is provided in Appendix H.

heading: 4 Experimental verification
text: In this section, we experimentally validate the advantages of our adjusted regularisation strategies described in Subsection 3.3. In all experiments, we work with the square loss.

heading: 4.1 Experiments on synthetic data
text: We construct square data matrices in Rnˆn with a given rank r ď d for several combinations of n, d, r. 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 Λ such that Λ “ 0 yields uniform sampling (details in appendix). We compare three approaches: (1) Standard inductive matrix completion with the side information matrices X,Y (IMC) (2) Our smoothed adjusted regulariser λ}ĂM} (for several values of α) (ATR)6; and finally (3) our smoothed empirically adjusted regulariser λ}|M} (for several values of α) (E-ATR). For each n P t100, 200u we evaluate the following d, r combinations: p30, 4q, p50, 6q and p80, 10q. In order to study a meaningful data-sparsity regime, in each case we sampled drω entries where ω P t1, 2, 3, 4, 5u. 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.
6Note that in this synthetic context, it is actually possible to compute ĂM since the distribution is known.

heading: 4.2 Real data experiments
text: We evaluate the performance of our model on three real life datasets: Douban, LastFM and MovieLens (further described in the supplementary). In real data we work with the following adjusted version of the model in [19]:
min M,Z
1
N
ÿ
pi,jqPΩ lpXMY J ` Z,Gi,j ` ζi,jq ` λ1} qD 1 2 pPM pQ´1 qE 1 2 }˚ ` λ2} qD
1 2 I Z qE 1 2 I }˚ (18)
where qD, qE are defined as above based on the side information matrices X,Y , and qDI , qEI are defined as qD, qE except based on the side information matrices pI, Iq. In particular, } qD1{2I Z qE 1{2 I }˚ “ } qZ}˚ is 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.

heading: 5 Conclusion
text: In this paper, we have provided the first distribution-free bounds for approximate recovery in inductive matrix completion with the trace norm with the following two desirable properties: (1) being non vacuous for identity or 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 Opd3{2 ? r logpdqq) and our adjusted version (rate Opdr logpdqq) 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 foreseeable significant societal impact.

heading: Acknowledgements
text: The authors acknowledge support by the German Research Foundation (DFG) awards KL 2698/2-1 and KL 2698/5-1, as well as by the Federal Ministry of Science and Education (BMBF) awards 031L0023A, 01IS18051A, and 031B0770E.

Review summaries:
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.