{'fraction_non_alphanumeric': 0.05309125111271604, 'fraction_numerical': 0.016191068039436336, 'mean_word_length': 3.7253968253968255, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 16, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 1, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 24, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Matrix estimation by Universal Singular Value Thresholding

Consider the problem of estimating the entries of a large matrix, when the observed entries are noisy versions of a small random fraction of the original entries. This problem has received widespread attention in recent times, especially after the pioneering works of Emmanuel Cand\`{e}s and collaborators. This paper introduces a simple estimation procedure, called Universal Singular Value Thresholding (USVT), that works for any matrix that has"a little bit of structure."Surprisingly, this simple estimator achieves the minimax error rate up to a constant factor. The method is applied to solve problems related to low rank matrix estimation, blockmodels, distance matrix completion, latent space models, positive definite matrix completion, graphon estimation and generalized Bradley--Terry models for pairwise comparison.


Introduction
Consider a statistical estimation problem where the unknown parameter is not a single value or vector, but an m × n matrix M . Given an estimator M , one choice for a measure of the error in estimation is the mean-squared error, defined as Herem ij and m ij denote the (i, j)th elements ofM and M , respectively. If we have a sequence of such problems, and M n andM n denote the parameter and the estimator in the nth problem, then by usual statistical terminology we may say that the sequence of estimatorsM n is consistent if The problem of estimating the entries of a large matrix from incomplete and/or noisy entries has received widespread attention ever since the proliferation of large data sets. Early work using spectral analysis was done by a number of authors in the engineering literature, for example by Azar et al. [9] and Achlioptas and McSherry [1]. This was followed by a sizable body of work on spectral methods, the main pointers to which may be found in the important recent papers of Keshavan, Montanari and Oh [62,63]. Non-spectral methods also appeared, e.g. in [83].
In a different direction, statisticians have worked on matrix completion problems under a variety of modeling assumptions. Possibly the earliest works are due to Fazel [46] and Rudelson and Vershynin [87]. The emergence of compressed sensing [43,26] has led to an explosion in activity in the field of matrix estimation and completion, beginning with the work of Candès and Recht [25]. The pioneering works of Emmanuel Candès and his collaborators [25,27,24,23] introduced the technique of matrix completion by minimizing the nuclear norm under convex constraints, which is a convex optimization problem tractable by standard algorithms. This method has the advantage of exactly, rather than approximately, recovering the entries of the matrix when a suitable low rank assumption is satisfied, together with a certain other assumption called 'incoherence'.
Since the publication of [25], a number of statistics papers have attacked the matrix completion problem from various angles. Some notable examples are [74,75,65,84,64,38]. In a different direction, a paper that seems to have a close bearing on the analytical aspects of this paper is a manuscript of Oliveira [79].
In addition to the theoretical advances, a large number of algorithms for matrix completion and estimation have emerged. The main ones are nicely summarized and compared in [75].
The purpose of this paper is to introduce a new estimator that is capable of solving a variety of matrix estimation problems that are not tractable by existing tools (at least in a mathematically provable sense). The estimator and its properties are described in this introductory section. Section 2 focuses on applications, which include applications to low rank matrices, stochastic blockmodels, distance matrices, latent space models, positive definite matrices, graphons, and generalized Bradley-Terry models. All proofs are in Section 3. An expanded version (version 5) of the paper containing more theorems, examples and simulation results, is available on arXiv at the URL: http://arxiv.org/pdf/1212.1247v5.pdf For interesting new developments that appeared after the first draft of this paper was posted on arXiv, see [35,44,76]. Further references and citations are given in subsequent sections.
1.1. The setup. Suppose that we have a m × n matrix M , where m ≤ n and the entries of M are bounded by 1 in absolute value. Let X be a matrix whose elements are independent random variables, and E(x ij ) = m ij for all i and j (where, as usual, x ij and m ij denote the (i, j)th entries of X and M respectively). Assume that the entries of X are also bounded by 1 in absolute value, with probability one. A matrix such as X will henceforth be called a 'data matrix with mean M '. The matrix M will sometimes be called the 'parameter matrix'. Let p be a real number belonging to the interval [0, 1]. Suppose that each entry of X is observed with probability p, and unobserved with probability 1 − p, independently of the other entries.
The above model will henceforth be referred to as the 'asymmetric model'. The 'symmetric model' is defined in a similar manner: Take any n and let M be a symmetric matrix of order n, whose entries are bounded by 1 in absolute value. Let X be a symmetric random matrix of order n whose elements on and above the diagonal are independent, and E(x ij ) = m ij for all 1 ≤ i ≤ j ≤ n. As before, assume that the entries of X are almost surely bounded by 1 in absolute value. Take any p ∈ [0, 1] and suppose that each entry of X on and above the diagonal is observed with probability p, and unobserved with probability 1 − p, independently of the other entries.
Similarly, one can define the 'skew-symmetric model', where the difference X−M is skew-symmetric, with independence on and above the diagonal as in the symmetric model. This model is used for analyzing the non-parametric Bradley-Terry model in Section 2.7.
1.2. The USVT estimator. In the above models, we construct an esti-matorM of M based on the observed entries of X along the following steps. Tentatively, I call this the Universal Singular Value Thresholding (USVT) algorithm.
1. For each i, j, let y ij = x ij if x ij is observed, and let y ij = 0 if x ij is unobserved. Let Y be the matrix whose (i, j)th entry is y ij . 2. Let Y = m i=1 s i u i v T i be the singular value decomposition of Y . (In the symmetric and skew-symmetric models, m = n.) 3. Letp be the proportion of observed values of X. In the symmetric and skew-symmetric models, letp be the proportion of observed values on and above the diagonal. 4. Choose a small positive number η ∈ (0, 1) and let S be the set of "thresholded singular values", defined as (Note: (a) In simulations, the method described below seemed to work even if η was taken to be exactly equal to zero; but the mathematical proof that I have requires η to be positive. In practice, one may choose η a priori to be some arbitrary small positive number, say, 0.01; but a datadependent choice is not allowed. (b) If it is known that Var(x ij ) ≤ σ 2 for all i, j, where σ is a known constant ≤ 1, then the threshold (2 + η) √ np may be improved to (2 + η) √ nq, whereq :=pσ 2 +p(1 −p)(1 − σ 2 ).) 5. Define 6. Let w ij denote the (i, j)th element of W . Definê 7. LetM be the matrix whose (i, j)th entry ism ij . 8. If the entries of M and X are known to belong to an interval [a, b] instead of [−1, 1], then subtract (a + b)/2 from each entry of X and divide by (b − a)/2, so that the entries are forced to lie in [−1, 1], then apply the above procedure, and finally multiply the end-result by (b − a)/2 and add (a + b)/2 to get the estimate of M . 9. If m > n, then one should work with M T and X T instead of M and X, so that the number of rows is forced to be ≤ the number of columns.

Main result.
Recall that the nuclear norm of M , written M * , is defined as the sum of the singular values of M . Recall also the definition (1) of the mean squared error of a matrix estimator. The following theorem gives an error bound for the estimatorM in terms of the nuclear norm of M . This is the main result of this paper.
Theorem 1.1. LetM and M be as above. Let MSE(M ) be defined as in (1). Suppose that p ≥ n −1+ for some > 0. Then where C and c are positive constants that depend only on the choice of η and C( ) depends only on and η. The same result holds for the symmetric and skew-symmetric models, after putting m = n. Moreover, if in the same setting as above, we know that Var(x ij ) ≤ σ 2 for all i, j for some known σ 2 ≤ 1, and the threshold is set at (2 + η) √ nq (see Step 4 of the algorithm), the same result holds under the condition that q ≥ n −1+ , where q := pσ 2 +p(1−p)(1−σ 2 ). In this case the exponential term in the error changes to C( )e −cnq and the term M * /(m √ np) improves to Incidentally, the proof shows that the condition p > n −1+ may be improved to p > n −1 (log n) 6+ (see Theorem 3.4), but I prefer to retain the present version for aesthetic reasons, especially considering that it is not a real improvement from any practical point of view.
It should be emphasized that although singular value thresholding has been used in a number of papers on matrix completion and estimation (see e.g. [9,1,23,62,63] and references therein), the above algorithm has the unique feature that the threshold is universal. In the literature, it is usually assumed that the matrix M has a rank r that is known, and uses the value of r while thresholding. The USVT algorithm manages to cut off the singular values at the 'correct' level, depending on the structure of the unknown parameter matrix. The adaptiveness of the USVT threshold is somewhat similar in spirit to that of the SureShrink algorithm of Donoho and Johnstone [45]. SureShrink performs function estimation by estimating Fourier coefficients in some suitable basis, and then thresholds the coefficients at a threshold that automatically adapts to the smoothness of the unknown function. Analogously, the USVT algorithm computes the eigenvalues of the observed matrix, and then thresholds the eigenvalues at a universal threshold that is automatically adaptive in nature, because it picks out as much 'structure' as is available and throws out all the randomness. This point will become more clear from the examples discussed in Section 2.
One limitation of USVT is the requirement that the entries should lie in a bounded interval. One may relax this requirement by assuming, for example, that the errors x ij − m ij are distributed as normal random variables with mean zero and variance σ 2 . If σ 2 is known, then I believe that one can modify the USVT algorithm by thresholding at (2 + η)σ √ n and obtain the same theorems. The rationale behind this belief is as follows: If A is a large symmetric random matrix whose entries on and above the diagonal are independent, have zero mean, and are bounded by 1 in absolute value, then the spectral norm of A is less than 2 + η with high probability. This is the key ingredient in the proof of Theorem 1.1. But such a result continues to be true, after replacing 2 + η with (2 + η)σ, if the entries are normally distributed with mean zero and variance bounded by σ 2 . Therefore it is conceivable that the proof of Theorem 1.1 may be modified to accommodate this altered situation. However if σ 2 is unknown, I do not know how to proceed. In reality σ 2 will not be known; this is why I have not worked with the normality assumption. Also, the situation of normally distributed entries but with a large proportion missing, seems to be trickier.
1.4. Minimax lower bound. It is not difficult to prove that for an m × n matrix M with entries bounded by 1 in absolute value, where m ≤ n, the nuclear norm is bounded by m √ n. Given a number δ ∈ [0, m √ n], one may take an arbitrary estimatorM and try to find the M among all M satisfying M * ≤ δ for which MSE(M ) is maximum. Recall that an estimator that minimizes this maximum error is classically known as a minimax estimator. The following theorem shows that our estimatorM is minimax up to a constant multiplicative factor and an exponentially small additive discrepancy.
Theorem 1.2. Consider the general matrix estimation problem outlined in the beginning of this section. Given any estimatorM and any δ ∈ [0, m √ n], there exists M satisfying M * ≤ δ and a data matrix X with mean M , such that for this M and X, the estimatorM satisfies where c is a positive universal constant. Moreover, if p < 1/2 then X and M may be chosen such that X = M . The same lower bound holds in the symmetric case and in the skew-symmetric case.
It is worth noting that the exponentially small discrepancy is necessary. For example, if δ = 0, then the minimax error is obviously zero. However, there is still an exponentially small chance thatM may be nonzero. It is also worth noting that if δ is not too small (e.g. if δ > m/p), then the exponential discrepancy does not matter, and the combination of Theorems 1.1 and 1.2 gives the correct minimax error up to a universal multiplicative constant.
An examination of the proof of Theorem 1.1 indicates that with slight modifications, one may obtain bounds on tail probabilities instead of an upper bound on the mean squared error. I have retained the present version for aesthetic reasons.
Incidentally, two notable recent papers, namely, Koltchinskii et al. [65] and Davenport et al. [38], have suggested matrix estimation by nuclear norm penalization and proved minimax optimality results that match up to logarithmic factors. Davenport et al. [38,Theorem 3] show (in the notation of our Theorem 1.2) that if the entries of X belong to {−1, 1} and if δ ≥ 4 √ mn, then the minimax error is bounded below by a universal constant times min{δ/(m √ np), 1}, provided that this quantity is bigger than δ 2 /(m 2 n). This is almost the same as the conclusion of Theorem 1.2, except that it does not cover the case of δ smaller than 4 √ mn. Section 3.1 of [38] gives a matrix estimation algorithm based on nuclear norm penalization that achieves this minimax rate up to a logarithmic factor. However, the implementation of this algorithm requires that the user has a reasonable estimate for the nuclear norm of the unknown matrix M , since that is used as the regularization parameter. USVT has no such requirement. Another advantage that USVT has over the algorithm of [38] is that it may be easier to implement, especially for very large matrices, because it does not involve convex optimization.
The estimator of Koltchinskii et al. [65] is also based on nuclear norm penalization: translating to our notation, they estimate M by minimizing X −M 2 F + λ M * over allM , where · F is Frobenius norm, · * is nuclear norm, and λ is a regularization parameter. It is shown in [65] that this problem is actually equivalent to soft singular value thresholding, where the threshold depends on the parameter λ. A conservative choice of λ (albeit with an unspecified constant) and a minimax lower bound that matches the upper bound up to a logarithmic factor are given in [65]. The minimax bound is computed over the set of all matrices with rank less than a given number, and therefore is not directly comparable to the minimax bound in Theorem 1.2. With a suitable choice of λ -but again with unspecified constants -the upper bound in [65,Theorem 3] becomes (up to a logarithmic factor) essentially equal to M * /(m √ np). Note that this is the same as the main term in Theorem 1.1. However if we additionally know that M has low rank, then the upper bound in [65,Theorem 3] becomes substantially better (see Section 2.1).
1.5. Practical issues and warnings. I do not consider the USVT algorithm as presented above to be in a form that may implemented 'as is'. This is mainly for the following reasons: (a) USVT is minimax optimal only up to a constant factor. In fact, it is very likely that one may be able to build a better estimator by taking into account the ratio m/n, and getting improved bounds when this ratio is small. Although Theorem 1.2 shows that the improvement will be limited to multiplication by a constant factor, such an improvement may be important for practical purposes. The recent paper [44] has explored the issue of attaining the minimax error all the way up to the correct constant.
(b) The number η is a "tuning parameter" for this algorithm, that may be chosen by the implementer. The theorem is valid with any choice of η in the interval (0, 1), although the constants in the error bounds blow up as η tends to zero. I have noticed in simulations that taking η = 0 works quite well, but I do not know how to prove that. Choosing η to be a small but fixed positive number such as 0.01 is consistent with the requirements of Theorem 1.1 and seemed to give good results in simulations. Choosing η in a data-dependent manner is, however, not covered by Theorem 1.1.
(c) Note that in practice, any data matrix may be centered and scaled so that the entries are forced to lie in the interval [−1, 1]. However if the centering and scaling are done in a data-dependent manner, then the assertion of Theorem 1.1 is no longer guaranteed to be true.
1.6. An impossibility theorem for error estimates. Theorem 1.1 gives an upper bound on the mean squared error ofM . The estimate involves the nuclear norm of parameter matrix M . A natural question is: Is it possible to estimate the true MSE ofM from the data?
A straightforward approach is to use parametric bootstrap. Having estimated M usingM , one may choose a large number K, generate K copies of the data usingM as the parameter matrix, compute the estimatesM (i) , i = 1, . . . , K for the K simulations, and estimate the MSE ofM using the bootstrap estimator For the validity of the bootstrap estimate of the MSE, it is essential that the originalM is an accurate estimate of M . In other words, we need to know a priori that MSE(M ) is small to be able to claim that the bootstrap estimator of MSE(M ) is accurate. Theorem 1.1 implies that if we know that M * is small enough from assumptions, this is true.
But is it possible to somehow determine whether MSE(M ) is small or not from the data, if we do not make any assumption about M to start with? We will now show that it is impossible to do so, not only for the estimator M but for any 'non-trivial' estimatorM .
The definition of a non-trivial estimator is as follows. Given a parameter matrix M and a data matrix X satisfying the conditions of Section 1, the trivial estimator of M based on X is simply X itself. We will denote the trivial estimator asM Trv . Now suppose we are given some estimatorM . We will say that the estimatorM is non-trivial if there exists a sequence of parameter matrices M n and data matrices X n such that MSE(M Trv n ) → 0 as n → ∞, but lim n→∞ MSE(M n ) = 0. In other words,M n solves a non-trivial estimation problem. The USVT estimator is clearly non-trivial, as demonstrated by the examples from Section 2.
Suppose that we have a non-trivial estimatorM and a procedure P that gives an estimate MSE P (M ) of the MSE ofM . The MSE estimate is computed using only the data. The procedure will be called 'good' if the following two conditions hold: (a) Whenever M n is a sequence of parameter matrices and X n is a sequence of data matrices such that MSE(M n ) tends to zero, the estimate MSE P (M n ) also tends to zero in probability. (b) Whenever M n is a sequence of parameter matrices and X n is a sequence of data matrices such that MSE(M n ) does not tend to zero, MSE P (M n ) also does not tend to zero in probability. In the above setting the following theorem establishes the impossibility of the existence of a good estimator for the MSE. Theorem 1.3. There cannot exist a good procedure for estimating the mean squared error of a non-trivial estimator.

Applications
Throughout this section, m, n, M , X, p andM will be as in Section 1. Just to remind the reader, M is an m × n matrix where 1 ≤ m ≤ n. The entries of M are assumed to be bounded by 1 in absolute value. The matrix X is a random matrix whose entries are independent, and the (i, j)th element x ij has expected value equal to m ij , the (i, j)th entry of M . Moreover, they satisfy |x ij | ≤ 1 with probability one. In particular, X may be exactly equal to M , with no randomnness. Each entry of X is observed with probability p and unobserved with probability 1 − p, independently of other entries. Occasionally, we will assume the symmetric model, where m = n, and the matrices M and X are symmetric. In the special case of the Bradley-Terry model in Section 2.7, we will assume the skew-symmetric model, where X − M is skew-symmetric.
We will now work out various specific cases where Theorem 1.1 gives useful results.
where C and c depend only on η and C( ) depends only on and η. Moreover, the same result holds when M and X are symmetric.
The term 1/np in the error bound is necessary to take care of the case r = 0. Even if M is identically zero, the estimatorM will incur some error due to the (possible) randomness in X.
Let us now inspect how the condition r mp compares with available bounds. In a notable sequence of papers, Keshavan, Montanari and Oh [62,63] obtain the same condition but only if m and n are comparable and the rank is known. Theorem 2.1, on the other hand, works even for 'very rectangular' matrices where m n and the rank is unknown. Candès and Tao [27] obtain the condition r mp with an extra polylogarithmic term in the error. Moreover they too require that m and n be comparable, and additionally they need the so-called 'incoherence condition'. However, as noted before, the incoherence condition allows exact recovery, while our approach only gives approximate recovery.
The recent important work of Davenport et al. [38] gives an estimator with an error bound that is almost the same as that given by Theorem 2.1, but with a complicated optimization algorithm. Theorem 2.1, however, is probably not an optimal result. It has been shown by Koltchinskii et al. [65, Theorem 3 and Theorem 5] that the true minimax error rate for a closely related problem is actually r/mp, up to a logarithmic factor.
The following theorem shows that the condition r mp is necessary for estimating M .
Theorem 2.2. Given any estimatorM , there exists an m × n matrix M of rank r with entries bounded between −1 and 1, such that when the data is sampled from M , where C is a positive universal constant and [m/r] is the integer part of m/r.

The stochastic blockmodel.
Consider an undirected graph on n vertices. A stochastic blockmodel assumes that the vertices 1, . . . , n are partitioned into k blocks, and the probability that vertex i is connected to vertex j by an edge depends only on the blocks to which i and j belong. As usual, edges are independent of each other. Let M be the matrix whose (i, j)the element is the probability of an edge existing between vertices i and j. The matrix X here is the adjacency matrix of the observed graph. Here all elements of X are observed, so p = 1. This is commonly known as the stochastic blockmodel. It was introduced by Holland, Laskey and Leinhardt [56] as a simple stochastic model of social networks. It has become one of the most successful and widely used models for community structure in networks, especially after the advent of large data sets.
Early analysis of the stochastic blockmodel was carried out by Snijders and Nowicki [91,77], who provided consistent parameter estimates when there are exactly two blocks. This was extended to a finite but fixed number of blocks of equal size by Condon and Karp [37]. Bickel and Chen [15] were the first to give consistent estimates for finite number of blocks of unequal size. It was observed by Leskovec et al. [67] that in real data, the number of blocks often seem to grow with the number of nodes. This situation was rigorously analyzed for the first time in Rohe et al. [85], and was followed up shortly thereafter by [16,36,73,33] with more advanced results.
However, all in all, I am not aware of any estimator for the stochastic blockmodel that works whenever the number of blocks is small compared to the number of nodes. The best result till date is in the very recent manuscript of Rohe et al. [86], who prove that a penalized likelihood estimator works whenever k is comparable to n 'up to log factors'. The following theorem says that the USVT estimatorM gives a complete solution to the estimation problem in the stochastic blockmodel if k n, with no further conditions required. (The method will not work very well for sparse graphs, however; for recent advances on estimation in sparse graphs, see [34].) Theorem 2.3. For a stochastic blockmodel with k blocks, where C is a constant that depends only on our choice of η.
Note that estimating the stochastic blockmodel is a special case of low rank matrix estimation with noise. It is not difficult to prove that the estimation problem is impossible when k is of the same order as n. We will not bother to write down a formal proof.
2.3. Distance matrices. Suppose that K is a compact metric space with metric d. Let x 1 , . . . , x n be arbitrary points from K, and let M be the n × n matrix whose (i, j)th entry is d(x i , x j ). Such matrices are called 'distance matrices'. Since K is a compact metric space, the diameter of K with respect to the metric d must be finite. Scaling d by a constant factor, we may assume without loss of generality that the diameter is bounded by 1, so that the entries of M are bounded by 1 as required by Theorem 1.1.
Completing a distance matrix with missing entries has been a popular problem in the engineering and social sciences for a long time; see, for example, [92,10,6,17,89,90]. It has become particularly relevant in engineering problems related to sensor networks. It is also an important issue in multidimensional scaling [18]. For some recent theoretical advances, see [78,60].
In general, distance matrices need not be of low rank. Therefore much of the literature on matrix estimation and completion does not apply to distance matrices. Surprisingly, Theorem 1.1 gives a complete solution of the distance matrix completion and estimation problem.
where c depends only on η, C( ) depends only on and η, and C(K, d, n) is a number depending only on K, d, n and η such that The above theorem is not wholly satisfactory, since it does not indicate how fast p can go to zero as n → ∞ so thatM is still consistent. To understand that, we need to know more about the structure of the space K.
The following theorem gives a quantitative estimate.
Theorem 2.5. Suppose that for each δ > 0, N (δ) is a number such that K may be covered by N (δ) open d-balls of radius δ. Then where C and c depend only on η and C( ) depends only on and η.
To see how Theorem 2.5 may be used, suppose that K is a compact subset of the real line and d is the usual distance on R, scaled by a factor to ensure that the diameter of K is ≤ 1. Then N (δ) increases like 1/δ as δ → 0. Consequently, given n, the optimal choice of δ is of the order n −1/3 , which gives the bound (Note that the exponential term need not appear because the main term is bounded below by a positive constant if p < n −2/3 .) Thus,M is a consistent estimate as long as p goes to zero slower than n −2/3 as n → ∞.

2.4.
Latent space models. Suppose that β 1 , . . . , β n are vectors belonging to some bounded closed set K ⊆ R k , where k is some arbitrary but fixed dimension. Let f : K → [−1, 1] be a continuous function. Let M be the n × n matrix whose (i, j)th element is f (β i , β j ). Then our data matrix X has the form where ij are independent errors with zero mean, satisfying the restriction that |x ij | ≤ 1 almost surely. For example, X may be the adjacency matrix of a random graph where the probability of an edge existing between vertices i and j is f (β i , β j ). This is one context where latent space models are widely used, starting with the work of Hoff, Raftery and Handcock [55]. A large body of work applying the latent space approach to real data has grown in the last decade. On the theoretical side, it was observed in [15,16] that the latent space model arises naturally from an exchangeability assumption due to the Aldous-Hoover theorem [5,57]. Note that distance matrices and stochastic blockmodels are both special cases of latent space models.
There have been various attempts to estimate parameters in the latent space models (e.g. [55,53,4]). Almost all of these approaches rely on heuristic arguments and justification through simulations. The problem is that in addition to the vectors β 1 , . . . , β n , the function f itself is an unknown parameter. If either β i 's are known, or f is known, the estimation problem is tractable. For example, when f (x, y) is of the form e x+y /(1 + e x+y ), the problem was solved in [30]. However when both f and β i 's are unknown, the problem becomes seemingly intractable. In particular, there is an identifiability issue because f (x, y) may be replaced by h(x, y) := f (g(x), g(y)) and β i by g −1 (β i ) for any invertible function g without altering the model.
In view of the above discussion, it is a rather surprising consequence of Theorem 1.1 that it is possible to estimate the numbers f (β i , β j ), i, j = 1, . . . , n from a single realization of the data matrix, under no additional assumptions than the stated ones.
Theorem 2.6. Suppose that p ≥ n −1+ . If M is as above, then where c depends only on η, C( ) depends only on and η, and C(K, k, f, n) depends only on K, k, f , n and η such that The problem with Theorem 2.6, just like Theorem 2.4 in Section 2.3, is that it does not give an explicit error bound, which makes it impossible to determine how fast p can go to zero with n so that consistency holds. Again, this is easy to fix by assuming smoothness properties of f and applying Lemma 3.6. As a particular example, suppose that f is Lipschitz with Lipschitz constant L, in the sense that for all x, y, x , y ∈ K.
Theorem 2.7. In the above setting, where C(K, k, L) is a constant depending only on K, k, L and η. Completing positive definite matrices with missing entries has received a lot of attention in the linear algebra literature [51,61,14], although most of the techniques are applicable only for relatively small matrices or when a sizable fraction of the entries are observed. In the engineering sciences, estimation of covariance matrices from a small subset of observed entries arises in the field of remote sensing (see [24,25,27] for brief discussions).
The statistical matrix completion literature cited in Section 1 applies only to low rank positive definite matrices. It is therefore quite a surprise that the completion problem may be solved for any positive definite matrix whenever we get to observe a large number of entries from each row.
where C and c depend only on η and C( ) depends only on and η.
What if p is of order 1/n or less? The following theorem shows that it is impossible to estimate M in this situation. Theorem 2.9. Given any estimatorM , there exists a correlation matrix M such that when the data is sampled from M , where C is a positive universal constant.
In the graph limits literature, graphons arise as limits of graphs with increasing number of nodes. Conversely, graphons are often used to generate random graphs in a natural way. Take any n and let U 1 , . . . , U n be i.i.d. Uniform[0, 1] random variables. Construct a random undirected graph on n vertices by putting an edge between vertices i and j with probability f (U i , U j ), doing this independently for all 1 ≤ i < j ≤ n. This procedure is sometimes called 'sampling from a graphon' (see [20,Section 4.4]).
The statistical question is the following: Suppose that we have a random graph on n vertices that is sampled from a graphon. Is it possible to estimate the graphon from a single realization of the graph? More precisely, is it possible to accurately estimate the numbers f (U i , U j ), 1 ≤ i < j ≤ n, from a single realization of the random graph? The question is similar to the one investigated in Section 2.3, but the difference is that here we are not allowed to assume any regularity on f except measurability.
Taking things back to our usual setting, let M be the matrix whose (i, j)th element is f (U i , U j ). Note that unlike our previous examples, M is now random. So the definition of MSE should be modified to take expectation over M as well.
Theorem 2.10. In the above setting, where C(f, n) is a constant depending only on f , n and η, such that lim n→∞ C(f, n) = 0.
Incidentally, after the first version of this paper was put up on arXiv, several papers (e.g. [95,96]) on graphon estimation, advocating a number of different techniques and demonstrating applications in the statistical study of networks, have appeared in the literature.

2.7.
Non-parametric Bradley-Terry model. Suppose there are n teams playing against each other in a tournament. Every team plays against every other team at least once (often, exactly once). Suppose that p ij is the probability that team i wins against team j in a match between i and j. Then The Bradley-Terry model [22], originally proposed by Zermelo [97], assumes that p ij is of the form a i /(a i + a j ) for some unknown nonnegative numbers a 1 , . . . , a n . It is known how to estimate the parameters a 1 , . . . , a n if we assume that the outcomes of all games are independent -which, in this case, is a reasonable assumption.
The Bradley-Terry model has found great success among practitioners. For an old survey of the literature on the model dating back to 1976, see [40]. Numerous extensions and applications have been proposed, for example [54,3,82,80,71,72,58]. The monographs of David [39] and Diaconis [41,Chapter 9] explain the statistical foundations of these models. More recently, several authors have proposed to perform Bayesian inference for (generalized) Bradley-Terry models [2,48,49,50,52,28].
For the basic Bradley-Terry model, it is possible to find the maximum likelihood estimate of the a i 's using a simple iterative procedure [97,59,66]. The maximum likelihood estimate was shown to be jointly consistent for all n parameters by Simons and Yao [88].
We now generalize the Bradley-Terry model as follows. Suppose, as before, that p ij is the probability that team i beats team j. Suppose that the teams have a particular ordering in terms of strength that is unknown to the observer. Assume that if team i is stronger than team j, then p ik ≥ p jk for all k = i, j. Do not assume anything else about the p ij 's; in particular, do not assume any formula for the p ij 's in terms of hidden parameters. This is what we may call a 'non-parametric Bradley-Terry model'. Note that the usual Bradley-Terry model is a special case of the non-parametric version.
In the non-parametric Bradley-Terry model, is it possible to estimate all the p ij 's from a tournament where every team plays against every other exactly once? Is it possible to estimate the p ij 's if only a randomly chosen fraction of the games are played? How small can this fraction be, so that accurate estimation is still possible? The following theorem provides some answers.
Theorem 2.11. Consider the non-parametric Bradley-Terry model defined above. Let M be the matrix whose (i, j)th entry is p ij if i = j and 0 if i = j. Let X be the data matrix whose (i, j)th entry is 1 if team i won over team j, 0 if team j won over team i and recorded as missing if team i did not play versus team j. If team i has played against team j multiple times, let the (i, j)th entry of X be the proportion of times that i won over j. (Draws are not allowed.) Let all diagonal entries of X be zero. Given p ∈ [0, 1], suppose that for each i and j, the game between i and j takes place with probability p and does not take place with probability 1 − p, independent of other games. LetM be the estimate of M based on the data matrix X. Then where C depends only on our choice of η. In particular, the estimation problem is solvable whenever p n −1/2 .
A natural question is whether the threshold p n −1/2 is sharp. I do not know the answer to this question. Matrix norms. Let A = (a ij ) 1≤i≤m, 1≤j≤n be an m × n real matrix with singular values σ 1 , . . . , σ k , where k = min{m, n}. The following matrix norms are widely used in this proof.
The nuclear norm or the trace norm of A is defined as The Frobenius norm, also called the Hilbert-Schmidt norm, is defined as By the Cauchy-Schwarz inequality, The sup-norm is defined as The spectral norm or the operator norm of A is defined as The spectral norm may be alternatively expressed as where S m−1 and S n−1 are the Euclidean unit spheres in R m and R n respectively. The above representation implies that the spectral norm satisfies the triangle inequality. Consequently, for any two m × n matrices A and B, In particular, the spectral norm is a Lipschitz function of the matrix entries (with Lipschitz constant 1), if the entries are collectively considered as a vector of length mn. The triangle inequality for the spectral norm also implies that the map A → A is convex. Indeed, for any 0 ≤ t ≤ 1, For more on matrix norms, see [13].
Perturbation of singular values. The following perturbative result from matrix analysis is used several times in this manuscript. Let A and B be two m × n matrices. Let k = min{m, n}. Let σ 1 , . . . , σ k be the singular values of A in decreasing order and repeated by multiplicities, and let τ 1 , . . . , τ k be the singular values of B in decreasing order and repeated by multiplicities. Let δ 1 , . . . , δ k be the singular values of A − B, in any order but still repeated by multiplicities.
The above result follows, for example, from a combination of Theorem III.4.4 and Exercise II.1.15 in [13]. It may also be derived as a consequence of Wielandt's minimax principle [ Bernstein's inequality. The following inequality is known as 'Bernstein's inequality'.
Theorem 3.2. Suppose that X 1 , . . . , X n are independent random variables with zero mean, and M is a constant such that |X i | ≤ M with probability one for each i. Let S := n i=1 X i and v := Var(S). Then for any t ≥ 0, This inequality was proved by Bernstein [12]. For a discussion of Bernstein's inequality and improvements, see Bennett [11].
Talagrand's concentration inequality. Recall that a median m of a random variable Y is a real number such that P(Y ≤ m) ≥ 1/2 and P(Y ≥ m) ≥ 1/2. The median may not be unique.
The following concentration inequality is one of the several striking inequalities that are collectively known as 'Talagrand's concentration inequalities'.
For a proof of Theorem 3.3, see [93,Theorem 6.6]. It is easy to modify Theorem 3.3 to have concentration around the mean instead of the median. Just observe that by Theorem 3.
By the definition of a median, this shows that E(Y )−16L ≤ m ≤ E(Y )+16L. Together with Theorem 3.3, this implies that for any t ≥ 0, The above inequality has a number of uses in the proof of Theorem 1.1.
Spectral norms of random matrices. The following bound on spectral norms of random matrices is a crucial ingredient for this paper. The proof follows from a combinatorial argument of Vu [94] (which is itself a refinement of a classical argument of Füredi and Komlós [47]), together with Talagrand's inequality (4).
Theorem 3.4. Take any two numbers m and n such that 1 ≤ m ≤ n. Suppose that A = (a ij ) 1≤i≤m, 1≤j≤n is a matrix whose entries are independent random variables that satisfy, for some σ 2 ∈ [0, 1], E(a ij ) = 0, E(a 2 ij ) ≤ σ 2 , and |a ij | ≤ 1 a.s. Suppose that σ 2 ≥ n −1+ for some > 0. Then for any η ∈ (0, 1), where C 1 ( ) depends only on and η and C 2 depends only on η. The same result is true when m = n and A is symmetric or skew-symmetric, with independent entries on and above the diagonal, all other assumptions remaining the same. Lastly, all results remain true if the assumption σ 2 ≥ n −1+ is changed to σ 2 ≥ n −1 (log n) 6+ .
Proof. First assume that m = n and A is symmetric. Note that for any even number k, Consider i 1 , i 2 , . . . , i k−1 , i k , i 1 as a closed tour of a subset of the vertices of the complete graph on n vertices (with self-edges included). From the given assumptions about the a ij 's, it follows that the term E(a i 1 i 2 a i 2 i 3 · · · a i k i 1 ) is zero if there is an edge that is traversed exactly once. Suppose that each edge in the tour is traversed at least twice. Let p be the number of distinct vertices visited by the tour. Then the number of distinct edges traversed by the tour is at least p − 1. Since σ 2 ≤ 1, |a ij | ≤ 1, and E|a ij | l ≤ σ 2 for any l ≥ 2, this shows that Thus, if W (n, k, p) is the number of tours of length k that visit exactly p vertices and traverse each of its edges at least twice, then Vu [94, equation (5)] proves that if p > k/2 then W (n, k, p) = 0 and if p ≤ k/2 then Using this bound, one can proceed as in [94,Section 2] to arrive at the conclusion that if k is largest even number ≤ σ 1/3 n 1/6 , then Consequently, This shows that if σ 2 ≥ n −1+ (or if σ 2 ≥ n −1 (log n) 6+ ), then there is a constant C( ) depending only on and η such that if n ≥ C( ) then Since a ij are independent and |a ij | ≤ 1 almost surely for all i, j, and the spectral norm is a convex Lipschitz function of matrix entries with Lipschitz constant 1 (by the discussion about matrix norms at the beginning of this section), therefore one can apply Talagrand's inequality (Theorem 3.3 and inequality (4)) together with (8) and the assumption that σ 2 ≥ n −1+ to conclude that there is a constant C( ) such that if n ≥ C( ) then where C 1 and C 2 depend only on η. Replacing C 1 by a large enough constant C 1 ( ), the condition n ≥ C( ) may be dropped. It is clear from the argument that it goes through in the skew-symmetric case as well.
Let us now drop the assumption of symmetry, but retain the assumption that m = n. Let a ij := a ji . Then the inequality (5) must be modified to say that for any even k, As before, the term inside the sum is zero for any tour that traverses an edge exactly once. (In fact, there are more terms that are zero now; a term may be zero even if a tour traverses all of its edges at least twice.) Similarly, the inequalities (6) and (7) continue to hold and therefore so does the rest of the argument.
Lastly, consider the case m < n. Augment the matrix A by adding an extra n − m rows of zeros to make it an n × n matrix that satisfies all the conditions of the theorem. Clearly, the new matrix has the same spectral norm as the old one. This completes the proof.
The key lemma. Suppose that A and B are two m × n matrices, where m ≤ n. Let a ij be the (i, j)th entry of A and b ij be the (i, j)th entry of B. It is easy to see from definition that Thus if A − B is small enough, then the entries of A are approximately equal to the entries of B, on average. In other words, the matrix A is an estimate of the matrix B.
The goal of this section is to show that if in addition to the smallness of A − B , we also know that the nuclear norm B * is not too large, it is possible to get a better estimate of B based on A.
i be the singular value decomposition of A. Fix any δ > 0 and definê Note that by the definition ofB, the largest singular value of A −B is bounded above by (1 + δ) A − B . In other words, On the other hand, by Theorem 3.1, In particular, for i ∈ S, and for i ∈ S, By (11), By (10) and (13), we have SinceB and G both have rank ≤ |S|, the differenceB − G has rank at most 2|S|. Using this and (14), we have Next, observe that by (11), Combining (15) and (16), we have Next, note that by (12), Combining (17) and (18), the proof is complete.
Finishing the proof of Theorem 1.1. We will prove the theorem only for the asymmetric model. The only difference in the proofs for the symmetric model and the skew-symmetric model is that we need to use the symmetric and skew-symmetric parts of Theorem 3.4 instead of the asymmetric part.
Throughout this proof, C( ) will denote any constant that depends only on and η, and C and c will denote constants that depend only on η. The values of C( ), C and c may change from line to line or even within a line. We will use the fact that η ∈ (0, 1) without mention on many occasions.
Note that for all i and j, E(y ij ) = pm ij , and Letp be the proportion of observed entries. Define two events E 1 and E 2 as P(E 1 ) ≥ 1 − C( )e −cnp . By Bernstein's inequality (Theorem 3.2), for any t ≥ 0, In particular, Let δ be defined by the relation If E 1 and E 2 both happen, then Let K(δ) be the constant in the statement of Lemma 3.5. It is easy to see that there is a constant C depending only on η such that if δ ≥ η/5, then K(δ) ≤ C √ 1 + δ. Therefore by Lemma 3.5, if E 1 and E 2 both happen, then By the definition ofM , it is obvious that |m ij − m ij | ≤ |w ij − m ij | for all i and j. Together with (22), this shows that under E 1 ∩ E 2 , Note that E(p − p) 2 = p(1 − p)/mn and that M − M 2 F ≤ 4mn. Thus by (20) and (21), Dividing throughout by mn, we arrive at the inequality The next goal is to show that First, suppose that M * > η n/p/20. Then and so (24) follows from (23). Therefore assume that M * ≤ η n/p/20. Then in particular, M ≤ η n/p/20. Therefore if E 1 ∩ E 2 happens, then This implies that there is no singular value of Y that exceeds (2 + η) √ np, and thereforeM = 0. Consequently, Thus, if M * ≤ η n/p/20, then by (20) and (21), Combining the above steps and observing that MSE(M ) ≤ 1 due to the boundedness of the entries of M andM , we get To remove the 1/np term, note that if that term indeed matters, then we are in a situation where But this inequality, on the other hand, implies that Therefore, the 1/np term can be removed from the above bound. This completes the proof of Theorem 1.1 if no nontrivial bound on Var(x ij ) is known. If σ 2 ≤ 1 is a known constant such that Var(x ij ) ≤ σ 2 for all i, j, then the estimate (19) may be improved to where R is the quadrilateral region The maximum must be attained at one of the four vertices of R. An easy verification shows that the maximum is always attained at the vertex (1 − σ 2 , σ 2 ), which gives the upper bound This allows us to replace the threshold (2 + η) √ np by (2 + η) √ nq, wherê q =pσ 2 +p(1 −p)(1 − σ 2 ). As before we need that q ≥ n −1+ . The rest of the proof goes through with the following modifications: Replace √ np by √ nq in the definition of E 1 , keep E 2 the same, and define an event If E 1 ∩ E 2 ∩ E 3 happens, then the subsequent steps remain the same, but with some suitable modifications that replace the term M * /(m √ np) by the improved term M * √ q/(m √ np).

3.2.
Proof of Theorem 1.2 (Minimax optimality). Throughout this proof, C will denote any positive universal constant, whose value may change from line to line. Take any δ ∈ [0, m √ n] and let θ := δ/(m √ n). We will first work out the proof under the assumption that p < 1/2. Under this assumption, three situations are considered. First, suppose that (25) θ/ √ p ≤ 1 and mθ √ p ≥ 1.  (2), Let X = M . Let D be our data, that is, the observed values of X. One can imagine D as a matrix whose (i, j)th entry is x ij if x ij is observed, and a question mark if x ij is unobserved. For any (i, j) belonging to the nonzero portion of the matrix M , M contains [1/p] copies of m ij . Since the X-value at the location of each copy is observed with probability p, independent of the other copies, and p < 1/2, therefore the chance that none of these copies are observed is bounded below by a positive universal constant. If none of the copies are observed, then the data contains no information about m ij . Using this, it is not difficult to write down a formal argument that shows On the other hand, sincem ij is a function of D, the definition of variance implies that Combining the last two displays, we see that The argument that led to the above lower bound is a typical example of the classical Bayesian argument for obtaining minimax lower bounds, and will henceforth be referred to as the 'standard minimax argument' to avoid repetition of details.
Let M be an m × n matrix whose first row consists of i.  (2), On the other hand, a standard minimax argument as before implies that for any estimatorM , In particular, under (27), there exists M with M * ≤ δ such that Lastly, suppose that Let M be an m × n matrix whose first [mp] rows consist of i.i.d. random variables uniformly distributed over [−1, 1], and this block is copied [1/p] times. Then the rank of M is ≤ [mp], and so by (28) and (2), Again by a standard minimax argument, it is easy to conclude that for any estimatorM , there exists M with M * ≤ δ such that This completes the proof when p < 1/2. Next suppose that p ≥ 1/2. The only place where the assumption p < 1/2 was used previously was for proving that E(Var(m ij |D)) ≥ C. This can be easily taken care of by inserting some randomness into the data matrix X, as follows. First replace M by 1 2 M in all three cases above. This retains the condition M * ≤ δ. Given M , let X be the data matrix whose (i, j)th entry x ij is uniformly distributed over the interval [m ij − 1/2, m ij + 1/2], whenever (i, j) is the 'main block' of M ; and this value of x ij is copied [1/p] times in the appropriate places.
Since the entries of M are now guaranteed to be in [−1/2, 1/2], this ensures that the entries of X are in [−1, 1]. Now note that even if x ij or one of its copies is observed, it gives only limited information about m ij . In particular, it is easy to prove that E(Var(m ij |D)) ≥ C and complete the proof as before.
This Suppose, without loss of generality, that all the data matrices are defined on the same probability space. Then taking a subsequence if necessary, we may assume that in addition to (29) and (30), we also have Let M n := X n and X n := X n for all n. Consider M n as a (random) parameter matrix and X n as its data matrix. Given M n , the expected value of X n is M n ; so it is okay to treat M n as a parameter matrix and X n as its data matrix. We will denote the estimate of M n constructed using X n asM n . Note that since M n is random, the mean squared error ofM n is a random variable. Now, since the estimatorM n is computed using the data matrix only, and X n = X n , it is clear thatM n =M n . There is no randomness inM n when M n is given, since X n = M n . Thus, if r n and c n denote the number of rows and columns of M n , then where the last step follows from the inequality (a + b) 2 ≤ 2a 2 + 2b 2 and the triangle inequality for the Frobenius norm. Taking expectation on both sides gives . Therefore by (29) and (30), In particular, since mean squared errors are uniformly bounded by 1, Again since MSE P is computed using the data matrix only, therefore for all n, MSE P (M n ) = MSE P (M n ). Therefore by (31), (33) P lim n→∞ MSE P (M n ) = 0 = 1.
The equations (32) and (33) demonstrate the existence of a sequence of parameter matrices M n and data matrices X n such that MSE(M n ) → 0 but MSE P (M n ) → 0 in probability. This contradicts the goodness of MSE P .
3.4. Proof of Theorem 2.1 (Upper bound for low rank matrix estimation). Inequality (2) implies that The result now follows from Theorem 1. Let D be our data, that is, the observed values of M . One can imagine D as a matrix whose (i, j)th entry is m ij if m ij is observed, and a question mark if m ij is unobserved. For any (i, j) belonging to the nonzero portion of the matrix M , M contains [m/r] copies of m ij . Since the M -value at the location of each copy is observed with probability p, independent of the other copies, the chance that none of these copies are observed is equal to (1 − p) [m/r] . If none of the copies are observed, then the data contains no information about m ij . Using this, it is not difficult to write down a formal argument that shows where C is some universal constant. On the other hand, sincem ij is a function of D, the definition of variance implies that Combining the last two displays, we see that The proofs of Theorems 2.4 and 2.5 follow from a more general lemma that will also be useful later for other purposes. Suppose that S = {x 1 , . . . , x n } is a finite set and f : S × S → [−1, 1] is an arbitrary function. Suppose that for each δ > 0, there exists a partition P(δ) of S such that whenever x, y, x , y are four points in S such that x, x ∈ P for some P ∈ P(δ) and y, y ∈ Q for some Q ∈ P(δ), then |f (x, y) − f (x , y )| ≤ δ. Let M be the n × n matrix whose (i, j)th element is f (x i , x j ). Lemma 3.6. In the above setting, where C and c depend only on η, and C( ) depends only on and η.
Proof. Fix some δ > 0. Let T be a subset of S consisting of exactly one point from each member of P(δ). For each x ∈ S, let p(x) be the unique element of T such that x and p(x) belong to the same element of P(δ). Let N be the matrix whose (i, j)th element is f (p(x i ), p(x j )). Then By the triangle inequality for the nuclear norm, the inequality (2) and the above inequality, Now, if x i and x j belong to the same element of P(δ), then p(x i ) = p(x j ) and hence the ith and jth rows of N are identical. This shows that N has at most |P(δ)| distinct rows and therefore has rank ≤ |P(δ)|. Therefore by the inequality (2), The proof is completed by applying Theorem 1.1.
Using Lemma 3.6, it is easy to prove Theorems 2.4 and 2.5.
Proof of Theorem 2.5. Let all notation be as in Theorem 2.5. To apply Lemma 3.6, let S be the set {x 1 , . . . , x n }. From the definition of N (δ), it is easy to see that there is a partition P(δ) of S of size ≤ N (δ/4), such that any two points belonging to the same element of the partition are at distance ≤ δ/2 from each other. Consequently, if x, x ∈ P and y, y ∈ Q for some P, Q ∈ P(δ), then by the triangle inequality for the metric d, Putting f = d in Lemma 3.6, the proof is complete.
Proof of Theorem 2.4. Since K is compact, there exists a finite number N (δ) for each δ > 0 such that K may be covered by N (δ) open d-balls of radius δ. By Theorem 2.5, this shows that for any sequence δ n decreasing to zero, To complete the proof, choose δ n going to zero so slowly that N (δ n /4) = o(n) as n → ∞.
3.8. Proof of Theorem 2.6 (Latent space models: general case). We will apply Lemma 3.6. Let S be the set {β 1 , . . . , β n }. Since f is continuous on K and K is compact, f must be uniformly continuous. This shows that for each δ > 0 we can find a partition P(δ) of S satisfying the condition required for Lemma 3.6, such that the size of P(δ) may be bounded by a constant N (δ) depending only on K, k, f and δ. Choosing δ n → 0 slowly enough so that N (δ n /4) = o(n) and applying Lemma 3.6 completes the proof.
3.9. Proof of Theorem 2.7 (Latent space models: Lipschitz functions). Let S = {β 1 , . . . , β n }. Take any δ > 0. From the Lipschitzness condition, it is easy to see that we can find a partition P(δ) of S whose size may be bounded by C(K, k, L)δ −k , where C(K, k, L) depends only on K, k and L. Choosing δ = n −1/(k+2) and applying Lemma 3.6 completes the proof. Note that the exponential term need not appear since the main term is bounded below by a positive constant if p < n −2/(k+2) . 3.11. Proof of Theorem 2.9 (Lower bound for positive definite matrix estimation). Throughout this proof, C will denote any positive universal constant, whose value may change from line to line. Let U 1 , . . . , U n be i.i.d. Uniform[0, 1] random variables. Let M be the random matrix whose (i, j)th element m ij is equal to U i U j if i = j and 1 if i = j. It is easy to verify that M is a correlation matrix. Suppose that we observe each element of M on and above the diagonal with probability p, independent of each other. Let D be our data, represented as follows: D is a matrix whose (i, j)th element is m ij if the element is observed, and a question mark otherwise. Now, the probability that no element from the ith row and the ith column is observed is exactly equal to (1 − p) n . If we do not observe any element from the ith row and ith column, we have no information about the value of U i . From this, it is not difficult to write down a formal argument to prove that for any j = i, Var(m ij | D, (U k ) k =i ) = U 2 j Var(U i | D, (U k ) k =i ) ≥ C(1 − p) n U 2 j . IfM is any estimator, thenm ij is a function of D. Therefore by the above inequality and the definition of variance, j , and thus E(m ij − m ij ) 2 ≥ C(1 − p) n . Since this is true for all i = j, the proof is complete.
3.12. Proof of Theorem 2.10 (Graphon estimation). Here all entries of the adjacency matrix are visible, so p = 1. Define a sequence of functions f 1 , f 2 , . . . according the following standard construction. For each k, let P k be the kth level dyadic partition of [0, 1) 2 , that is, the partition of the unit square into sets of the form [(i − 1)/2 k , i/2 k ) × [(j − 1)/2 k , j/2 k ). Let f k be the function that is equal to the average value of f within each square of the partition P k . If F k denotes the sigma-algebra of sets generated by the partition P k , then the sequence f k is a martingale with respect to the filtration F k . Moreover, f k = E(f |F k ). Finally, observe that the sequence f k is uniformly bounded in L 2 . Combining all these observations, it is evident that f k → f in L 2 . Now fix some > 0 and an integer n. Take a large enough k = k( ) such that f − f k L 2 ≤ . Let N be the n × n matrix whose (i, j)th element is f k (U i , U j ). Then Now note that if U i and U j belong to the same dyadic interval [r/2 k , (r + 1)/2 k ), then the ith and jth rows of N are identical. Hence N has at most 2 k distinct rows, and therefore has rank ≤ 2 k . Therefore by (2), Consequently, by the inequality (2), Combining (34) and (35) gives E M * ≤ (2 k/2 + 1)n + n 3/2 . Choosing a sequence n going to zero so slowly that 2 k( n)/2 = o(n −1/2 ), we can now apply Theorem 1.1 to complete the proof.
3.13. Proof of Theorem 2.11 (Bradley-Terry models). Throughout the proof C will denote any constant that depends only on η, whose value may change from line to line.
Recall that the definition of the skew-symmetric model stipulates that X − M is skew-symmetric, which is true for the non-parametric Bradley-Terry model. There is nothing to prove if p < n −2/3 , so assume that p ≥ n −2/3 . This allows us to drop the exponential term in Theorem 1.1 and conclude that (36) MSE(M ) ≤ C M * n 3/2 √ p .
Let k be an integer less than n, to determined later. For each i, let Note that each t i belongs to the interval [0, n]. For l = 1, . . . , k, let T l be the set of all i such that t i ∈ [n(l − 1)/k, nl/k). Additionally, if t i = n, put i in T k .
For each l, let r(l) be a distinguished element of T l . For each 1 ≤ i, j ≤ n, if i ∈ T l and j ∈ T m , let n ij := p r(l)j . Let N be the matrix whose (i, j)th element is n ij . Note that if i, i ∈ T l for some l, then n ij = n i j for all j. In particular, N has at most k distinct rows and therefore has rank ≤ k. Thus by inequality (2), Now take any 1 ≤ i ≤ n. Suppose that i ∈ T l . Let i = r(l). Suppose that team i is weaker than team i. Then p i j ≤ p ij for all j = i, i . Thus, Similarly, if team i is stronger than team i, By (37), (38), (39) and (2) we have Choosing k = [n 1/2 ], we get M * ≤ Cn 5/4 . Combined with (36), this proves the claim.
Department of Statistics, Stanford University, Stanford, CA 94305 E-mail address: souravc@stanford.edu