Alexandra Carpentier

Olga Klopp

Matthias Löffler

Richard Nickl

Adaptive confidence sets for matrix completion

Keywords: Low rank recovery, confidence sets, adaptivity, matrix completion, unknown variance, minimax hypothesis testing

come   L'archive ouverte pluridisciplinaire

Introduction

In matrix completion we observe n noisy entries of a data matrix M = (M ij ) ∈ R m1×m2 , and we aim at doing inference on M . In a typical situation of interest, n is much smaller than m 1 m 2 , the total number of entries. This problem arises in many applications such as recommender systems and collaborative filtering [START_REF] Bennett | The netflix prize[END_REF][START_REF] Goldberg | Using collaborative filtering to weave an information tapestry[END_REF], genomics [START_REF] Chi | Genotype imputation via matrix completion[END_REF] or sensor localization [START_REF] Singer | A remark on global positioning from local distances[END_REF]. Two statistical models have been proposed in the matrix completion literature: the trace-regression model (e.g. [START_REF] Cai | Matrix completion via max-norm constrained optimization[END_REF][START_REF] Klopp | Noisy low-rank matrix completion with general sampling distribution[END_REF][START_REF] Koltchinskii | Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion[END_REF][START_REF] Negahban | Restricted strong convexity and weighted matrix completion: Optimal bounds with noise[END_REF][START_REF] Rohde | Estimation of high-dimensional low-rank matrices[END_REF] ) and the 'Bernoulli model' (e.g. [START_REF] Candès | Exact matrix completion via convex optimization[END_REF][START_REF] Chatterjee | Matrix estimation by universal singular value thresholding[END_REF][START_REF] Klopp | Matrix completion by singular value thresholding: sharp bounds[END_REF]).

In the trace-regression model we observe n pairs (X i , Y tr i ) satisfying

Y tr i = X i , M + ǫ i = tr(X T i M ) + ǫ i , i = 1, . . . , n, (1.1)
where (ǫ i ) is a noise vector. The random matrices X i ∈ R m1×m2 are independent of the ǫ i 's, chosen uniformly at random from the set B = e j (m 1 )e T k (m 2 ), 1

≤ j ≤ m 1 , 1 ≤ k ≤ m 2 , (1.2)
were the e j (s) are the canonical basis vectors of R s . In this model Y tr i returns the noisy value of the entry of M corresponding to the random position X i .

In the Bernoulli model each entry of M + E, where E = (ǫ ij ) ∈ R m1×m2 is a matrix of random errors, is observed independently of the other entries with probability p = n/(m 1 m 2 ). More precisely, if n ≤ m 1 m 2 is given and B ij are i.i.d. Bernoulli random variables of parameter p independent of the ǫ ij 's, we observe

Y Ber ij = B ij (M ij + ǫ ij ) , 1 ≤ i ≤ m 1 , 1 ≤ j ≤ m 2 .
(1.3)

1 Institut für Mathematik, carpentier@maths.uni-potsdam.de 2 MODALX, kloppolga@math.cnrs.fr 3 Statistical Laboratory, Centre for Mathematical Sciences, m.loffler@statslab.cam.ac.uk, r.nickl@statslab.cam.ac.uk

The major difference between these models is that in the trace-regression model multiple sampling of a particular entry is possible whereas in the Bernoulli model each entry can be sampled at most once. A further difference is that in the trace regression model the number of observations, n, is fixed whereas in the Bernoulli model the number of observations n := ij B ij is random with expectation E n = n. Despite these differences, the results on minimax optimal recovery using computationally efficient algorithms for these two models in the literature are very similar and from a 'parameter estimation' point of view the models appear to be effectively equivalent (see, e.g., [START_REF] Cai | Matrix completion via max-norm constrained optimization[END_REF][START_REF] Candès | The power of convex relaxation: near-optimal matrix completion[END_REF][START_REF] Candès | Matrix completion with noise[END_REF][START_REF] Candès | Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements[END_REF][START_REF] Chatterjee | Matrix estimation by universal singular value thresholding[END_REF][START_REF] Gross | Recovering low-rank matrices from few coefficients in any basis[END_REF][START_REF] Keshavan | Matrix completion from noisy entries[END_REF][START_REF] Klopp | Noisy low-rank matrix completion with general sampling distribution[END_REF][START_REF] Koltchinskii | Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion[END_REF][START_REF] Negahban | Restricted strong convexity and weighted matrix completion: Optimal bounds with noise[END_REF][START_REF] Recht | A simpler approach to matrix completion[END_REF]). A key insight of the present paper is that for the construction of optimal confidence sets, these models are in fact fundamentally different, at least when the noise variance σ 2 is unknown.

When investigating questions that go beyond mere 'adaptive estimation' of a high-dimensional parameter, such as about the existence of adaptive confidence sets, one can expect to encounter surprising phenomenaand various recent results (see e.g. [START_REF] Baraud | Confidence balls in Gaussian regression[END_REF][START_REF] Bull | Adaptive confidence sets in L 2[END_REF][START_REF] Cai | An adaptation theory for nonparametric confidence intervals[END_REF][START_REF] Giné | Confidence bands in density estimation[END_REF][START_REF] Hoffmann | On adaptive inference and confidence bands[END_REF][START_REF] Juditsky | Nonparametric confidence set estimation[END_REF][START_REF] Low | On nonparametric confidence intervals[END_REF][START_REF] Nickl | A sharp adaptive confidence ball for self-similar functions[END_REF][START_REF] Nickl | Confidence sets in sparse regression[END_REF][START_REF] Robins | Adaptive nonparametric confidence sets[END_REF][START_REF] Szabó | Frequentist coverage of adaptive nonparametric Bayesian credible sets[END_REF] and Chapter 8.3 in [START_REF] Giné | Mathematical Foundations of Infinite-Dimensional Statistical Methods[END_REF]) show that the answers depend on a rather subtle interaction of certain 'information geometric' properties of the model -the material relevant for the present paper is reviewed in Section 2. Many of these results reveal limitations by showing that confidence regions that adapt to the whole parameter space do not exist unless one makes specific 'signal strength' assumptions. For example, Low [START_REF] Low | On nonparametric confidence intervals[END_REF] and Giné and Nickl [START_REF] Giné | Confidence bands in density estimation[END_REF] investigated this question in nonparametric density estimation and Nickl and van de Geer [START_REF] Nickl | Confidence sets in sparse regression[END_REF] in the sparse high-dimensional regression model.

Next to the challenge of adaptation, the construction of confidence sets in the matrix completion setting is difficult mainly due to two reasons. Firstly, the Restricted Isometry Property (RIP) does not hold, requiring a more involved analysis than in a standard trace regression setting such as in [START_REF] Carpentier | Uncertainty Quantification for Matrix Compressed Sensing and Quantum Tomography Problems[END_REF]. Moreover, in most practical applications of matrix completion such as movie recommender systems [START_REF] Bennett | The netflix prize[END_REF][START_REF] Goldberg | Using collaborative filtering to weave an information tapestry[END_REF] the variance of the errors is not known. Typical constructions of confidence sets in high-dimensions such as χ 2 -confidence sets (e.g. [START_REF] Nickl | Confidence sets in sparse regression[END_REF][START_REF] Carpentier | Uncertainty Quantification for Matrix Compressed Sensing and Quantum Tomography Problems[END_REF]) require explicit knowledge of the variance and are thus not feasible. Particularly in the 'Bernoulli model', the problem of unknown variance can be expected to be potentially severe: for the related standard normal means model (without low rank structure and without missing observations) Baraud [START_REF] Baraud | Confidence balls in Gaussian regression[END_REF] has shown that in the unknown variance case honest confidence sets of shrinking diameter do not exist, even if the true model is low dimensional. Similarly, in high-dimensional regression Cai and Guo [START_REF] Cai | Accuracy assessment for high-dimensional linear regression[END_REF] prove the impossibility of constructing adaptive confidence sets for the l q -loss, 1 ≤ q ≤ 2, of adaptive estimators if the variance is unknown.

Our main contributions are as follows: in the trace regression model, even if only an upper bound for the variance of the noise is known, it is shown that practical honest confidence sets exist that have Frobeniusnorm diameter that adapts to the unknown rank of M . Contrary to this we prove that such confidence regions cannot exist in the Bernoulli model when the noise variance is unknown, and to complement our findings we also prove that in the Bernoulli model with known variance, adaptive confidence regions do exist. So while recovery algorithms for matrix completion are not sensitive to the choice of model, the task of uncertainty quantification for these algorithms is, and crucially depends on the statistician's ability to estimate the noise variance. For the Bernoulli 'normal means' model our results imply that the lack of availability of 'repeated samples' induces an information-theoretic 'barrier' for inference even in the presence of low rank structure.

This paper is organized as follows: in Subsection 1.1 we formulate the assumptions and collect notation which we use throughout the paper. Then, in Section 2, we review and present general results about the existence of honest and adaptive confidence sets in terms of some information-theoretic quantities that determine the complexity of the adaptation problem at hand. Afterwards we review the literature on minimax estimation in matrix completion problems. In Section 4 we give an explicit construction of honest and adaptive confidence sets in the trace-regression case, adapting a U-statistic approach inspired by Robins and van der Vaart [START_REF] Robins | Adaptive nonparametric confidence sets[END_REF] (see also [START_REF] Giné | Mathematical Foundations of Infinite-Dimensional Statistical Methods[END_REF], Section 6.4, and [START_REF] Carpentier | Uncertainty Quantification for Matrix Compressed Sensing and Quantum Tomography Problems[END_REF]). Finally, we present our results for the Bernoulli model in Section 5. First, we derive an upper bound for the minimax rate of testing a low rank hypothesis and deduce from it the existence of honest and adaptive confidence regions in the known variance case. We then derive a lower bound for this testing rate in the unknown variance case, from which we can deduce that honest and adaptive confidence sets over the whole parameter space cannot exist in general. Sections 7-8 contain the proofs of our results.

Notation & assumptions

By construction, in the Bernoulli model (1.3) the expected number of observations, n, is smaller than the total number of matrix entries, i.e. n ≤ m 1 m 2 . To provide a meaningful comparison we will assume throughout that n ≤ m 1 m 2 also holds in the trace regression model (1.1). In many applications of matrix completion, such as recommender systems (e.g. [START_REF] Bennett | The netflix prize[END_REF][START_REF] Goldberg | Using collaborative filtering to weave an information tapestry[END_REF]) or sensor localization (e.g. [START_REF] Biswas | Semidefinite programming based algorithms for sensor network localization[END_REF][START_REF] Singer | A remark on global positioning from local distances[END_REF]) the noise is bounded but not necessarily identically distributed. This is the assumption which we adopt in the present paper. More precisely, we assume that the ǫ ι are independent random variables that are homoscedastic, have zero mean and are bounded: Assumption 1.1. In the models (1.1) and (1.3) with index ι = i and ι = (i, j), respectively, we assume E(ǫ ι ) = 0, E(ǫ 2 ι ) = σ 2 , ǫ ι ⊥ ⊥ ǫ η for ι = η and that there exists a positive constant U > 0 such that almost surely max

ι |ǫ ι | ≤ U.
We denote by M = (M ij ) ∈ R m1×m2 the unknown matrix of interest and define

m = min(m 1 , m 2 ), d = m 1 + m 2 .
For any l ∈ N we set [l] = {1, . . . , l}. Let A, B be matrices in R m1×m2 . We define the matrix scalar product as A, B := tr(A T B). The trace norm of the matrix A is defined as A * := σ j (A), the operator norm as A := σ 1 (A) and the Frobenius norm as

A 2 F := i σ 2 i = i,j A 2 ij
where (σ j (A)) are the singular values of A arranged in decreasing order. Finally A ∞ = max i,j |A ij | denotes the largest absolute value of any entry of A. Given a semi-metric D we define the diameter of a set S by

|S| D := sup{D(x, y) : x, y ∈ S}.
Furthermore, for k ∈ N 0 we define the parameter space of rank k matrices with entries bounded by a in absolute value as A(a, k) := {A ∈ R m1×m2 : A ∞ ≤ a and rank(A) ≤ k}.

(1.4)

Finally, for a subset Σ ⊂ (0, U ] we define

A(a, k) ⊗ Σ := {(A, σ) : A ∈ A(a, k), σ ∈ Σ}.
As usual, for sequences a n and b n we say a n b n if there exists a constant C independent of n such that a n ≤ C • b n for all n. We write P M,σ (and E M,σ for the corresponding expectation) for the distribution of the observations in the models (1.1) or (1.3), respectively.

Minimax theory for adaptive confidence sets

In this section we present results about existence of honest and adaptive confidence sets in a general minimax framework. To this end, let Y = Y n ∼ P n f on some measure space (Ω n , B), n ∈ N, where f is contained in some parameter space A, endowed with a semi-metric D. Let r n denote the minimax rate of estimation over A, i.e. inf fn:Ωn→A

sup f ∈A E f D( f , f ) ≍ r n (A).
We consider an 'adaptation hypothesis' A 0 ⊂ A characterised by the fact that the minimax rate of estimation in A 0 is of asymptotically smaller order than in A: r n (A 0 ) = o(r n (A)) as n → ∞. In our matrix inference setting we will choose for D the distance induced by • F , for A 0 , A the parameter spaces A(a, k 0 ) ⊗ Σ, A(a, k) ⊗ Σ from above, k 0 = o(k) as min(n, m) → ∞, and data (Y i , X i ) or (Y ij , B ij ) arising from equation (1.1) or (1.3), respectively.

Definition 2.1 (Honest and adaptive confidence sets). Let α, α ′ > 0 be given. A set

C n = C n (Y, α) ⊂ A is a honest confidence set at level α for the model A if lim inf n inf f ∈A P n f (f ∈ C n ) ≥ 1 -α. (2.1)
Furthermore, we say that C n is adaptive for the sub-model A 0 at level α ′ if there exists a constant K = K(α, α ′ ) > 0 such that sup

f ∈A0 P n f (|C n | D > Kr n (A 0 )) ≤ α ′ (2.2)
while still retaining sup

f ∈A P n f (|C n | D > Kr n (A)) ≤ α ′ . ( 2
H 0 : f ∈ A 0 against H 1 : f ∈ A, D(f, A 0 ) ≥ ρ n (2.4)
where (ρ n : n ∈ N) is a sequence of non-negative numbers. We say that ρ n is the minimax rate of testing for (2.4) if

(i) ∀β > 0 ∃ a constant L = L(β) > 0 and a test Ψ n = Ψ n (β), Ψ n : Ω n → {0, 1} such that sup f ∈A0 E f [Ψ n ] + sup f ∈A, D(f,A0)≥ Lρn E f [1 -Ψ n ] ≤ β. (2.5)
We say that such a test Ψ n is β-uniformly consistent.

(ii) For some β 0 > 0 and any sequence ρ * n = o(ρ n ) we have

lim inf n→∞ inf Ψn:Ωn→{0,1} sup f ∈A0 E f [Ψ n ] + sup f ∈A, D(f,A0)≥ρ * n E f [1 -Ψ n ] ≥ β 0 > 0. (2.6)
Theorem 2.1. Let ρ n be the minimax rate of testing for the testing problem (2.4) and suppose that β 0 > 0 is as in (2.6). Suppose that

r n (A 0 ) = o(ρ n ).
Then a honest and adaptive confidence set C n that satisfies (2.1)-(2.3) for any α, α ′ > 0 such that 0 < 2α + α ′ < β 0 does not exist. In fact if 3α < β 0 , then for any honest confidence set C n that satisfies (2.1) we have that sup

f ∈A0 E f |C n | D ≥ cρ n .
(2.7)

for a constant c = c(α) > 0.
The first claim of this theorem is Proposition 8.3.6 in [START_REF] Giné | Mathematical Foundations of Infinite-Dimensional Statistical Methods[END_REF]. The lower bound (2.7) also follows from that proof, arguing as in the proof of Theorem 4 in [START_REF] Carpentier | On signal detection and confidence sets for low rank inference problems[END_REF].

A converse of Theorem 2.1 also exists, as can be extracted from Proposition 8.3.7 in [START_REF] Giné | Mathematical Foundations of Infinite-Dimensional Statistical Methods[END_REF] and an observation in Carpentier (see [START_REF] Carpentier | Honest and adaptive confidence sets in L p[END_REF], proof of Theorem 3.5 in Section 6). For this we need the notion of an oracle-estimator. Definition 2.3 (Oracle estimator). Let β > 0 be given. We say that an estimator f satisfies an oracle inequality at level β if there exists a constant C such that for all f ∈ A we have with P n f -probability at least

1 -β, D( f , f ) ≤ C inf Ã∈{A,A0} D(f, Ã) + r n ( Ã) . (2.8)
This is a typical property of adaptive estimators, and is for example in the trace-regression setting fulfilled by the soft-thresholding estimator proposed by Koltchinskii et.al. [START_REF] Koltchinskii | Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion[END_REF]. The following theorem proves that if the minimax rate of testing is no larger than the minimax rate of estimation in the adaptation hypothesis, then honest adaptive confidence sets do exist. The proof is constructive and yields a confidence set of non-asymptotic coverage at least 1α. Theorem 2.2. Let α, α ′ > 0 be given. Let ρ n be the minimax rate of testing for the problem (2.4) such that a min(α/2, α ′ )-uniformly consistent test exists. Assume that ρ n ≤ C ′ r n (A 0 ) for some constant C ′ = C(α, α ′ ) > 0. Moreover, assume that an oracle estimator f at level α/2 fulfilling (2.8) exists. Then there exists a confidence set C n that adapts to the sub-model A 0 at level α ′ satisfying (2.2), (2.3) and that is honest at level α, i.e., sup

f ∈A P n f (f / ∈ C n ) ≤ α.

Minimax matrix completion

Noisy matrix completion has been extensively studied in several papers starting from Candes and Plan [START_REF] Candès | Matrix completion with noise[END_REF], see e.g. [START_REF] Candès | Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements[END_REF][START_REF] Keshavan | Matrix completion from noisy entries[END_REF][START_REF] Koltchinskii | Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion[END_REF][START_REF] Negahban | Restricted strong convexity and weighted matrix completion: Optimal bounds with noise[END_REF][START_REF] Klopp | Noisy low-rank matrix completion with general sampling distribution[END_REF][START_REF] Chatterjee | Matrix estimation by universal singular value thresholding[END_REF][START_REF] Cai | Matrix completion via max-norm constrained optimization[END_REF][START_REF] Klopp | Matrix completion by singular value thresholding: sharp bounds[END_REF][START_REF] Recht | A simpler approach to matrix completion[END_REF]). Optimal rates have been achieved under various sets of assumptions.

For instance the construction of the estimator (and the resulting upper bound) in [START_REF] Negahban | Restricted strong convexity and weighted matrix completion: Optimal bounds with noise[END_REF] requires knowledge of the 'spikiness' ratio of the unknown matrix and leads to sub-optimal rates in the case of sparse matrices. The bounds due to Keshavan et. al. [START_REF] Keshavan | Matrix completion from noisy entries[END_REF] are also only optimal for certain classes of matrices, namely almost square matrices that have a condition number bounded by a constant and fulfil the incoherence condition introduced by [START_REF] Candès | Exact matrix completion via convex optimization[END_REF]. Optimal convergence rates for the classes A(a, k) of matrices under consideration in the present paper have been obtained by Koltchinskii. et. al. [29] and Klopp [START_REF] Klopp | Noisy low-rank matrix completion with general sampling distribution[END_REF] for the trace-regression model and by Klopp [28] for the Bernoulli model. For example, in the trace-regression setting, Klopp [START_REF] Klopp | Noisy low-rank matrix completion with general sampling distribution[END_REF] shows that a constrained Matrix Lasso estimator M := M (a, σ) satisfies with P M0,σ -probability at least 1

-2/d M -M 0 2 F m 1 m 2 ≤ C kd log(d) n and M 0 -M ∞ ≤ 2a (3.1)
as long as m log(d) ≤ n ≤ d 2 log(d) and where C = C(σ, a) > 0. Similarly, in the Bernoulli model with noise bounded by U it has been shown in Klopp [28] that an iterative soft thresholding estimator M := M (a, σ) satisfies with P M0,σ -probability at least 1

-8/d M -M 0 2 F m 1 m 2 ≤ C kd n and M 0 -M ∞ ≤ 2a (3.2)
for n ≥ m log(d) and for a constant C = C(σ, a, U ) > 0. Matching lower bounds have also been shown by Koltchinskii. et a. [START_REF] Koltchinskii | Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion[END_REF] and Klopp [START_REF] Klopp | Matrix completion by singular value thresholding: sharp bounds[END_REF]. In the trace-regression model with Gaussian noise we have for constants β ∈ (0, 1) and

c = c(σ, a) > 0 that inf M sup M0∈A(a,k) P M0,σ M -M 0 2 F m 1 m 2 > c kd n ≥ β.
A similar lower bound can be obtained in the Bernoulli setting (see Klopp [START_REF] Klopp | Matrix completion by singular value thresholding: sharp bounds[END_REF]). These lower and upper bounds imply that for the Frobenius loss and the parameter space

A(a, k) the minimax rate r n,m (A(a, k)) is (at most up to a log-factor) of order m 1 m 2 kd/n. (3.3)

Trace Regression Model

We first consider the trace regression model. For the sake of precision we sometimes write M 0 for the 'true parameter' M that has generated the equation (1.1).

For notational simplicity we assume that n is even. Then we can split our observations in two independent sub-samples of equal size n/2. In what follows all probabilistic statements are under the distribution P (with corresponding expectation written E) of the first sub-sample (Y tr i , X i ) i≤n/2 of size n/2 ∈ N, conditional on the second sub-sample (Y tr i , X i ) i>n/2 , i.e. we have P(.

) = P M0,σ ( • |(Y tr i , X i ) i>n/2 ).
4.1 A non-asymptotic confidence set in the trace regression model with known variance of the errors.

In this case we can adapt the construction of [START_REF] Carpentier | Uncertainty Quantification for Matrix Compressed Sensing and Quantum Tomography Problems[END_REF]: we first unbiasedly estimate the risk M -M 0 2 F /(m 1 m 2 ) of a minimax optimal estimator M computed from an independent sample (e.g., via sample splitting) by a natural χ 2 -statistic (see (4.1)). The construction of an unbiased estimate requires knowledge of σ 2 , but when available this estimate, enlarged by natural quantile constants, serves as a good proxy for the diameter of the confidence set C n centred at M . More precisely, using only the second sub-sample (Y tr i , X i ) i>n/2 we compute the matrix lasso estimator from Klopp [START_REF] Klopp | Noisy low-rank matrix completion with general sampling distribution[END_REF] which achieves the bound (3.1) with probability at least 1 -2/d. Then, we freeze M and the second sub-sample. We define the following residual sum of squares statistic:

Rn = 2 n i≤n/2 (Y tr i -X i , M ) 2 -σ 2 . (4.1) Given α > 0, let ξ α,σ,U = √ 2σU log(α), z α = log(3/α
) and, for a z > 0, a fixed constant to be chosen, define the confidence set

C n = A ∈ R m1×m2 : A -M 2 F m 1 m 2 ≤ 2 Rn + z d n + z + ξ α,σ,U √ n , (4.2)
where

z2 = z2 (α, d, n, σ, z) = z α σ 2 max 3 A -M 2 F m 1 m 2 , 4zd/n . It is not difficult to see (using that x 2 y + x/ √ n implies x 2 y + 1/n) that E M0,σ |C n | 2 F m 1 m 2 M M -M 0 2 F m 1 m 2 + zd + σ 2 z α/3 n + ξ α,σ,U √ n . (4.3)
Markov's inequality, (4.3) and that M is minimax optimal (up to a log-factor) with P M0,σ -probability of at least 1 -2/d as long as m log(d) ≤ n ≤ d 2 log(d) imply that C n has an adaptive and up to a log-factor minimax optimal squared diameter with probability 1α ′ for any α ′ > 2/d. The following theorem shows that C n is also a honest confidence set:

Theorem 4.1. Let α > 0, α ′ > 2/d and suppose that m log(d) ≤ n ≤ d 2 log(d), that Assumption 1.1 is satisfied and that σ > 0 is known. Let C n = C n (Y, α ,
σ) be given by (4.2) with z > 0. Then, for every n ∈ N and every M 0 ∈ A(a, m),

P M0,σ (M 0 ∈ C n ) ≥ 1 - 2α 3 -2e -zd/(11a 2 ) .
Hence, for any 1 ≤ k 0 < k ≤ m, C n is a honest and (up to a log-factor) adaptive confidence set at the level α for the model A(a, k) ⊗ {σ} and adapts to the sub-model A(a, k 0 ) ⊗ {σ} at level α ′ .

The proof of Theorem 4.1 follows the lines of the proof of Theorem 2 in [START_REF] Carpentier | Uncertainty Quantification for Matrix Compressed Sensing and Quantum Tomography Problems[END_REF] and we omit it here as the unknown variance results considered in the next section straightforwardly imply the known variance results.

A non-asymptotic confidence set in the trace regression model with unknown error variance.

In this subsection we assume, that the precise knowledge of the noise variance σ is not available, although the quantities a, U are available to the statistician (i.e. upper bounds on the matrix entries and on the noise). More precisely we assume that σ belongs to a known set Σ ⊂ (0, U ]. In applications of matrix completion this is usually a realistic assumption since the entries of M 0 are bounded: For example in a movie recommender system (e.g. [START_REF] Bennett | The netflix prize[END_REF][START_REF] Goldberg | Using collaborative filtering to weave an information tapestry[END_REF]) the entries of the observations Y and consequently M 0 and ǫ i are bounded from above by the best possible rating and below from the worst possible rating.

As the variance is now assumed to be unknown the construction from (4.2) is not feasible anymore since we can not compute the test statistic (4.1). Instead we use a U-statistic approach: As in the previous section, we use the second half of the sample, (Y tr i , X i ) n/2<i≤n , for constructing a minimax optimal estimator M of M that fulfills M ∞ ≤ a. We use again the matrix lasso estimator from Klopp [START_REF] Klopp | Noisy low-rank matrix completion with general sampling distribution[END_REF] (with σ replaced by its upper bound U ) which achieves (3.1) with probability at least 1 -2/d. In order to construct the confidence set, we will be interested in all pairs of observations (Y tr l , X l ) and (Y tr s , X s ) in the first sub-sample with 1 ≤ l < s ≤ n/2 such that X l = X s (that is, independent measurements of the same matrix entry). For each (i, j) ∈ [m 1 ] × [m 2 ], let S (i,j) = {k ∈ {1, . . . , n/2} : X k = e i (m 1 )e T j (m 2 )} =: {a 1 < ... < a p (i,j) } where p (i,j) is the number of times that we observe the entry (i, j). For all indices (i, j) such that S (i,j) = ∅, we form the ⌊p (i,j) /2⌋ couples (X a1 , X a2 ), (X a3 , X a4 ), . . . etc. We denote by N the set of all these pairs and let |N | = N be their number. Re-ordering, we can write ( Xk , Z k , Z ′ k ) k≤N where Xk = X l = X s for some couple (X l , X s ) ∈ N and Z k = Y tr l and Z ′ k = Y tr s . That is, using two different samples of the same entry Xk = X l = X s we form the observation triples ( Xk , Z k , Z ′ k ). We use ( Xk , Z k , Z ′ k ) k≤N to construct a U-Statistic to estimate the squared Frobenius loss. Contrary to the construction in (4.1) this does not require knowledge of the variance of the errors. We define:

RN := 1 N N k=1 (Z k -M , Xk )(Z ′ k -M , Xk ), (4.4)
and we set RN = 0 if N = 0. Note that

E M0,σ RN M , N ≥ 1 = M -M 0 2 F m 1 m 2 . (4.5)
We define the confidence set

C n := A ∈ A(a, m) : A -M 2 F m 1 m 2 ≤ RN + z α,N (4.6)
where the random quantile constant z α,N is defined as

z α,N := U 2 + 4a 2 √ N α if N = 0 and z α,N = 4a 2 if N = 0.
The quantity N is random but we can bound it from below with high probability by n 2 /(64m 1 m 2 ) as proven in the following lemma.

Lemma 4.1. For n ≤ m 1 m 2 we have with probability at least 1exp -n 2 /(372m 1 m 2 ) that:

N ≥ n 2 64m 1 m 2 .
Markov's inequality, (4.5), Lemma 4.1 and that M achieves the nearly optimal rate (3.1) with P M0,σprobability of at least 1 -2/d imply for any k ≤ m, any

M 0 ∈ A(a, k), any σ ≤ U , any α ′ > 2/d + exp(-n 2 /(372m 1 m 2 )) and a large enough constant C = C(α, α ′ , σ, a, U ) > 0 that P M0,σ |C n | 2 F m 1 m 2 > C kd log(d) n ≤ α ′ . (4.7)
Since k is arbitrary this implies that C n is a confidence set whose • 2 F -diameter adapts to the unknown rank of M 0 without requiring the knowledge of σ ∈ Σ. The following theorem implies that C n is also a honest confidence set. Note that our result is non-asymptotic and holds for any triple (n, (4.6). Then C n satisfies for any M 0 ∈ A(a, m) and any σ ∈ Σ

m 1 , m 2 ) ∈ N 3 as long as m log d ≤ n ≤ m 1 m 2 . Theorem 4.2. Let α > 0 be given, assume m log(d) ≤ n ≤ m 1 m 2 and that Assumption 1.1 is fulfilled. Let C n = C n (Y, α) as in
P M0,σ (M 0 ∈ C n ) ≥ 1 -α.
Hence, for any α ′ > 2/d + exp(-n 2 /(372m 1 m 2 )) and any 1 ≤ k 0 < k ≤ m, C n is a honest confidence set at level α for the model A(a, k) ⊗ Σ that adapts (up to a log-factor) to the rank k 0 of any sub-model A(a, k 0 ) ⊗ Σ at level α ′ .

Bernoulli Model

In this section we consider the Bernoulli model (1.3). As before we let P M,σ (and E M,σ for the corresponding expectation) denote the distribution of the data when the parameters are M and σ, and we sometimes write M 0 for the 'true' parameter M for the sake of precision.

5.1 A non-asymptotic confidence set in the Bernoulli model with known variance of the errors.

Here we assume again that σ > 0 is known. In case of the Bernoulli model we are not able to obtain two independent samples and cannot use the risk estimation approaches from the trace-regression setting.

Instead we use the duality between testing and honest and adaptive confidence sets laid out in Section 2.

We first determine an upper bound for the minimax rate ρ = ρ n,m of testing the low rank hypothesis

H 0 : M ∈ A(a, k 0 ) against H 1 : M ∈ A(a, k), M -A(a, k 0 ) 2 F ≥ ρ 2 , (5.1)
and then apply Theorem 2.2. As test statistic, we propose an infimum-test which has previously been used by Bull and Nickl [START_REF] Bull | Adaptive confidence sets in L 2[END_REF] and Nickl and van de Geer [START_REF] Nickl | Confidence sets in sparse regression[END_REF] in density estimation and high-dimensional regression, respectively (see also Section 6.2.4. in [START_REF] Giné | Mathematical Foundations of Infinite-Dimensional Statistical Methods[END_REF]). Since σ 2 = Eǫ 2 ij is known we can define the statistic

T n := inf A∈A(a,k0) 1 √ 2n i,j B ij (Y ij -A ij ) 2 -σ 2 = inf A∈A(a,k0) 1 √ 2n i,j (Y ij -B ij A ij ) 2 -B ij σ 2 (5.2)
and choose the quantile constant u α such that

P σ   1 √ 2n i,j B ij (ǫ 2 ij -Eǫ 2 ij ) > u α   ≤ α/3. (5.3)
For example, using Markov's inequality, we obtain

P σ   1 √ 2n i,j B ij (ǫ 2 ij -σ 2 ) > u α   ≤ 1 2nu 2 α i,j Var σ B ij (ǫ 2 ij -σ 2 ) ≤ σ 2 (U 2 -σ 2 ) 2u 2 α so u α = σ 3(U 2 -σ 2 ) /(2α
) is an admissible choice.

Theorem 5.1. Let α ≥ 12 exp(-100d) be given. Consider the Bernoulli model (1.3) and the two parameter spaces A(a, k) and A(a, k 0 ), 1 ≤ k 0 < k ≤ m. Furthermore assume that Assumption 1.1 is fulfilled, that σ > 0 is known, that n ≥ m log(d) and consider the testing problem (5.1). Suppose

ρ 2 ≥ C m 1 m 2 k 0 d n ≍ r 2 n,m (A(a, k 0 ))
where C = C(α, a, U, σ) > 0 is a constant. Then the test Ψ n := 1 {Tn>uα} where u α is the quantile constant in (5.3) and T n is as in (5.2) fulfills sup M∈A(a,k0)

E M,σ [Ψ n ] + sup M∈A(a,k), M-A(a,k0) 2 F ≥ρ 2 E M,σ [1 -Ψ n ] ≤ α.
Now in order to apply Theorem 2.2 we use the soft-thresholding estimator proposed by Koltchinskii et. al. [START_REF] Koltchinskii | Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion[END_REF] which satisfies the oracle inequality (2.8) up to a log-factor in the trace regression model. That this holds in the Bernoulli-model as well with P M0,σ -probability of at least 1 -1/d can be proven in a similar way and we sketch this in Proposition 8.3, removing the log-factor by using stronger bounds on the spectral norm of the stochastic term (B ij ǫ ij ) i,j .

This and Theorem 5.1 imply, using Theorem 2.2, that there exist honest and adaptive confidence sets in the Bernoulli model if the variance of the errors is known.

Corollary 5.1. Let α ≥ 2/d and α ′ ≥ 12 exp(-100d) be given. Suppose that σ > 0 is known, that Assumption 1.1 is fulfilled and that n ≥ m log(d). Then, for any 1 ≤ k 0 < k ≤ m, there exists a honest confidence set C n at the level α for the model A(a, k) ⊗ {σ}, i.e., for any M 0 ∈ A(a, k),

P M0,σ (M 0 ∈ C n ) ≥ 1 -α,
and C n adapts to the sub-model A(a, k 0 ) ⊗ {σ} at level α ′ .

The case of the Bernoulli model with unknown error variance.

In this subsection we assume again, as in Subsection 5.2, that the precise knowledge of the error variance σ is not available. Whereas in this case for the trace-regression model the construction of honest and adaptive confidence set was seen to be possible, we will now show that this is not the case for the Bernoulli model. We use again the duality between testing and confidence sets, this time applying Theorem 2.1. The next theorem gives a lower bound for the minimax rate of testing for the composite null hypothesis H 0 : M ∈ A(a, k 0 ) of M having rank at most k 0 against a rank-k alternative. To simplify the exposition we will consider only square matrices (but see the remark below) and also an asymptotic 'high-dimensional' framework where min(n, m) → ∞ and k 0 = o(k). We formally allow for k 0 = 0, thus including the 'signal detection problem' when H 0 : M = 0, σ 2 = 1.

Theorem 5.2. Suppose that Assumption 1.1 is satisfied for some U ≥ 2 and assume m = m 1 = m 2 . Furthermore, let k = k n,m → ∞ be such that 0 < k ≤ m 1/3 and k 1/4 m/n < min(1, a)/2. For 0 ≤ k 0 < k satisfying k 0 = o(k) and a sequence ρ = ρ n,m ∈ (0, 1/2) consider the testing problem

H 0 : M ∈ A(a, k 0 ), σ 2 = 1 vs H 1 : M ∈ A(a, k), M -A(a, k 0 ) 2 F ≥ m 2 ρ 2 , σ 2 = 1 -4ρ 2 .
(5.4)

If as min(n, m) → ∞, ρ 2 = o √ km n , (5.5)
then for any test Ψ we have that

lim inf min(n,m)→∞ sup M∈A(a,k0) E M,1 [Ψ] + sup M∈A(a,k), M-A(a,k0) 2 F ≥m 2 ρ 2 E M, √ 1-4ρ 2 [1 -Ψ] ≥ 1.
(5.6)

In particular, if Σ ⊂ (0, U ] contains the interval [ √ 1 -4τ , 1] where τ = lim sup n,m k 1/4 m/n, then (2.6) holds for the choices A 0 = A(a, k 0 ) ⊗ Σ, A = A(a, k) ⊗ Σ and β 0 = 1, ρ * = ρ.
Using Theorem 2.1 this implies the non-existence of honest and adaptive confidence sets in the model (1.3) if the variance of the errors is unknown and

k 0 = o( √ k).
In particular adaptation to a constant rank

k 0 , k 0 = O(1), is never possible if k → ∞ as min(m, n) → ∞.
Corollary 5.2. Assume that the conditions of Theorem 5.2 are fulfilled and that k 0 = o( √ k). Then for any α, α ′ > 0 satisfying 0 < 2α + α ′ < 1 a honest confidence set for the model A(a, k) ⊗ Σ at level α that adapts to the sub-model A(a, k 0 ) ⊗ Σ at level α ′ does not exist. In fact if α < 1/3, we have for every honest confidence set C n for the model A(a, k) ⊗ Σ at level α and constant c = c(a, U, α) that

sup (M0,σ)∈A(a,k0)⊗Σ E M0,σ |C n | 2 F ≥ c m 3 √ k n .
The above results are formulated for square matrices (m 1 = m 2 ) to keep the technicalities in the proof at a reasonable level. One can adapt the proof of Theorem 5.2 to obtain a lower bound of the order ρ 2 √ km 1 m 2 /n which likewise leads to non-existence results for adaptive confidence sets for non-square matrices in relevant asymptotic regimes of k 0 , k, m 1 , m 2 .

Conclusions

We have investigated confidence sets in two matrix completion models: the Bernoulli model and the trace regression model. In the trace regression model the construction of adaptive confidence sets is possible, even if the variance is unknown. Contrary to this we have shown that the information theoretic structure in the Bernoulli model is different; in this case the construction of adaptive confidence sets is not possible if the variance is unknown.

One interpretation is that in practical applications (e.g. recommender systems such as Netflix [START_REF] Bennett | The netflix prize[END_REF]) one should incentivise users to perform multiple ratings, to justify the use of the trace regression model and the proposed U-statistic confidence set.

Our proof only shows that one can not adapt to general low rank hypotheses if the variance is unknown. This covers the key cases where k 0 = 1 or more generally k 0 = o( √ k). It remains an interesting open (and difficult) question whether the lower bound ρ in Theorem 5.2 is tight, but the answer to this question does not affect the main conclusions of our results on the existence of adaptive confidence sets in matrix completion problems.

Proofs

Proof of Theorem 2.2

Proof. Let Ψ n be a test that attains the rate ρ with error probabilities bounded by min(α/2, α ′ ) and let L = L(min(α/2, α ′ )) be the corresponding constant in (2.5). Let f denote an estimator that satisfies the oracle inequality (2.8) with probability of at least 1α/2. Define a confidence set

C n := {f ∈ A : D( f , f ) ≤ K (r n (A)Ψ n + r n (A 0 )(1 -Ψ n ))}
where K > 0 is a constant to be chosen. We first prove that C n is adaptive: If f ∈ A\A 0 there is nothing to prove, and if f ∈ A 0 we have

P n f (|C n | D > Kr n (A 0 )) = P n f (Ψ n = 1) ≤ α ′ .
For coverage we investigate three distinct cases and note that sup

f ∈ Ã P n f D( f , f ) > Cr n ( Ã) ≤ α/2 (7.1)
where C > 0 is as in (2.8) and where à ∈ {A 0 , A}. Hence f is, by the oracle inequality, an adaptive estimator.

Then for f ∈ A 0 , by (7.1)

P n f (f / ∈ C n ) ≤ P n f D( f , f ) > Kr n (A 0 ) ≤ α/2 ≤ α for K ≥ C. If f ∈ A\A 0 and D(f, A 0 ) ≥ Lρ n , then for K ≥ C P n f (f / ∈ C n ) = P n f (D( f , f ) > Kr n (A), Ψ n = 1) + P n f (D( f , f ) > Kr n (A), Ψ n = 0) ≤ P n f (D( f , f ) > Kr n (A)) + P n f (Ψ n = 0) ≤ α.
If f / ∈ A\A 0 but D(f, A 0 ) < Lρ n , then by the oracle inequality and since ρ n ≤ C ′ r n (A 0 ) we have with probability at least 1α/2 for such f that

D( f , f ) ≤ C(D(f, A 0 ) + r n (A 0 )) ≤ CLρ n + Cr n (A 0 ) ≤ C(LC ′ + 1)r n (A 0 ).
Thus we still have

P n f (f / ∈ C n ) = P n f (D( f , f ) > Kr n (A 0 )) ≤ α/2 ≤ α for K ≥ C(LC ′ + 1).

Proof of Theorem 4.2

Proof. Recall that

E M0,σ RN |N, N > 0 = M -M 0 2 F m 1 m 2 =: r. (7.2)
Thus using Markov's inequality we have for N > 0 that

P M0,σ (M 0 / ∈ C n |N, N > 0) ≤ P M0,σ | RN -r| > z α,N |N, N > 0 ≤ Var M0,σ RN N, N > 0 z 2 α,N . (7.3)
Using equation ( 7.2) we compute

Var M0,σ RN N, N > 0 = 1 N E M0,σ (Z k -M , Xk )(Z ′ k -M , Xi ) -r 2 N, N > 0 ≤ 1 N E M 0 -M , X 1 4 + 2σ 2 r + σ 4 = 1 N M -M 0 4 L 4 m 1 m 2 + 2σ 2 r + σ 4 ≤ U 4 + 8U 2 a 2 + 16a 4 N = αz 2 α,N
since M -M 0 ∞ ≤ 2a and where we define M -M 0 4 4 . Hence (7.3) implies

L 4 := i,j ( Mij -M ij )
P M0,σ (M 0 / ∈ C n |N > 0) ≤ α.
Moreover, as M -M 0 ∞ ≤ 2a and z α,0 = 4a 2 , we have that P (M 0 / ∈ C n |N = 0) = 0.

Proof of Theorem 5.1

Proof. If M ∈ A(a, k 0 ), then by definition of the infimum and u α we have

E M,σ [Ψ] = P M,σ (T n > u α ) ≤ P σ   1 √ 2n ij B ij (ǫ 2 ij -σ 2 ) > u α   ≤ α/3.
The case M ∈ A(a, k), M -A(a, k 0 ) 2 F ≥ ρ 2 requires more elaborate arguments. Let A * be a minimizer in (5.2). Then

E M,σ [1 -Ψ] = P M,σ (T n < u α ) = P σ   ij B ij [(A * ij -M ij ) 2 -2ǫ ij (A * ij -M ij ) + (ǫ 2 ij -σ 2 )] < √ 2nu α   . (7.4)
For ρ ≥ 8072a k 0 d/p = 8072a m 1 m 2 k 0 d/n we can apply Lemma 8.1 which yields a weaker version of the Restricted Isometry Property (RIP). Namely, Lemma 8.1 implies that the event

Ξ :=    i,j B ij (A ij -M ij ) 2 ≥ p 2 A -M 2 F ∀A ∈ A(a, k 0 )    , M ∈ H 1 ,
occurs with probability of at least 1 -2 exp(-100d). We can thus bound (7.4) by

P σ   sup A∈A(a,k0)   2 i,j B ij ǫ ij (A ij -M ij ) - i,j B ij (A ij -M ij ) 2 2   > - √ nu α , Ξ   (7.5) +P σ   i,j B ij (ǫ 2 ij -σ 2 ) > i,j B ij (A * ij -M ij ) 2 2 - √ nu α , Ξ   + 2 exp(-100d). (7.6)
The stochastic term (7.6) can be bounded using d 2 ≥ 3n and that ρ is large enough. Indeed, on the event Ξ we have that

i,j B ij (A * ij -M ij ) 2 2 ≥ pρ 2 /4 ≥ (1 + √ 2)/ √ 3du α ≥ (1 + √ 2) √ nu α
for ρ ≥ 2 u α d/p which implies together with the definition of u α in (5.3) that (7.6) can be bounded by α/3 + 2 exp(-100d). For the cross term (7.5) we use the two following inequalities which, just as before, hold on the event

Ξ ∀ A ∈ A(a, k 0 ) i,j B ij (A ij -M ij ) 2 4 ≥ √ nu α and i,j B ij (A ij -M ij ) 2 8 ≥ p A -M 2 F 16 .
Hence, using also a peeling argument, (7.5) can be bounded by

s∈N: pρ 2 /2≤2 s <∞ P σ   sup A∈A(a,k0), 2 s ≤p A-M 2 F ≤2 s+1 i,j B ij ǫ ij (A ij -M ij ) p A -M 2 F > 1 16   ≤ s∈N: pρ 2 /2≤2 s <∞ P σ   sup A∈A(a,k0), p A-M 2 F ≤2 s+1 i,j B ij ǫ ij (A ij -M ij ) > 2 s 16   = s∈N: pρ 2 /2≤2 s <∞ P σ Z(s) > 2 s 16 (7.7)
where we set the corresponding probability to 0 if the supremum is taken over an empty set and where we define

Z(s) := sup A∈A(a,k0), p A-M 2 F ≤2 s+1 i,j B ij ǫ ij (A ij -M ij ) .
Lemma 8.2 (with choices z = 16 2 , ξ ij = ǫ ij , t = 2 s and q = 1 there ) implies for ρ ≥ 16144U k 0 d/p and for 2 s ≥ pρ 2 /2 that

P σ Z(s) > 2 s 16 ≤ exp -2 s 2097152U 2 + 517120aU
Hence, (7.7) can be upper bounded by

s∈N: pρ 2 /2≤2 s <∞ exp -2 s 2097152U 2 + 517120aU ≤2 exp - pρ 2 2097152U 2 + 517120aU (7.8) ≤2 exp(-100d)
for ρ ≥ 16169U (a ∨ U ) d/p. Consequently (7.4) can be bounded by α/3 + 4 exp(-100d) ≤ 2α/3 since α ≥ 12 exp(-100d).

Proof of Theorem 5.2

Proof.

Step I : Reduction to an easier testing problem between two distributions Assume without loss of generality that m is divisible by k. Suppose

ρ = ρ n,m = vk 1/4 √ m √ n (7.9)
where v = v n,m is a sequence such that v = o(1), and assume w.l.o.g. that 0 < v ≤ 1. Moreover we denote u = 2ρ. For 1

≤ i ≤ m, 1 ≤ κ ≤ k, 1 ≤ j ≤ m let B ij i.i.d. ∼ B(p) and U κ i i.i.d. ∼ R and V j i.i.d. ∼ R,
where B(p) is a Bernoulli distribution of parameter p = n/m 2 and R is the standard Rademacher distribution Pr(V 1 = ±1) = 1/2. Let P be a uniform random partition of {1, . . . , m} in k groups of size m/k, and denote by K j , K j ∈ {1, ..., k}, the label of element j of P. Consider the following testing problem:

H ′ 0 : M = 0 and ǫ ij i.i.d. ∼ R against H ′ 1 : M ij = uU Kj i V j (7.10) and ǫ ij ∼ δ {1-Mij } (1 + M ij )/2 + δ {-1-Mij } (1 -M i,j )/2
Note that the variance of ǫ ij under H 0 is 1 and the variance of the noise under

H 1 is (1 -M ij ) 2 (1 + M ij )/2 + (-1 -M ij ) 2 (1 -M ij )/2 = (1 -M ij )(1 + M ij ) = 1 -4ρ 2 ,
so the noise variables are homoscedastic across the (i, j)'s and |ǫ ij | ≤ 2 ≤ U . Let π be the distribution of M under H ′ 1 and write ν 0 and ν 1 for the distribution of Y under H ′ 0 and H ′ 1 , respectively. Since the prior M in (7.10) consists of k i.i.d. scaled Rademacher vectors that each form m/k columns of M we have rank(M ) ≤ k and M ∞ = u = 2ρ ≤ a for v small enough and since k 1/4 m/n ≤ a/2. Thus M ∈ A(a, k). Then, reordering the columns of M we have

M -A(a, k 0 ) 2 F = M ord -A(a, k 0 ) 2 F
where M ord is a m × m matrix with the (((i -1)m/k) + 1)-th to the (im/k)-th columns each given by ur i where r i are i.i.d Rademacher vectors of length m, i = 1, ..., k. Then (as in the proof of Theorem 1 in [START_REF] Carpentier | On signal detection and confidence sets for low rank inference problems[END_REF]) we transform M ord into the m × k matrix M ord P = u m/kR consisting of k column vectors u m/kr i , i = 1, ..., k. The m × k projection matrix P consists of k column vectors, the i-th having zero entries except for the indices s ∈ [((i -1)m/k) + 1, . . . , im/k] where it equals k/m. Hence P is an orthonormal projection matrix and we obtain

M -A(a, k 0 ) 2 F ≥ (M ord -A(a, k 0 ))P 2 F = u m/kR -A(a m/k, k, k 0 ) 2 F where we define A(a, k, k 0 ) := {A ∈ R m×k : A ∞ ≤ a and rank(A) ≤ k 0 }.
Therefore, if σ min (A) denotes the minimal singular value of a matrix A, we have that

M -A(a, k 0 ) 2 F ≥ m 2 k uR/ √ m -A(a/ √ m, k, k 0 ) 2 F ≥ m 2 u 2 k (k -k 0 )(σ min (R/ √ m)) 2 ≥ m 2 u 2 2 (σ min (R/ √ m)) 2 ≥ m 2 u 2 4 = m 2 ρ 2 (7.11)
with probability going to 1, where we have used that kk 0 ≥ k/2 for m large enough (recall k 0 = o(k)) as well as the variational characterisation of minimal eigenvalues combined with Corollary 1 in [START_REF] Nickl | Confidence sets in sparse regression[END_REF] (with choices n = m, p = k 1 = k, θ = 0 and Λ min = 1 there) to lower bound σ 2 min (R/ √ m) by 1/2. To conclude, π is concentrated on H 1 and the primed testing problem above is, asymptotically, strictly easier than the testing problem (5.4) since H ′ 0 is contained in H 0 and H ′ 1 is asymptotically contained in H 1 . Thus, we have for any test Ψ by a standard lower bound (as, e.g., in (6.23) in [START_REF] Giné | Mathematical Foundations of Infinite-Dimensional Statistical Methods[END_REF]) that for all η > 0

E H0 Ψ + sup H1 E H1 (1 -Ψ) ≥ E H ′ 0 Ψ + E H ′ 1 (1 -Ψ) -o(1) ≥ (1 -η) 1 - d χ 2 (ν 0 , ν 1 ) η -o(1),
where d χ 2 (ν 0 , ν 1 ) denotes the χ 2 -distance between ν 0 and ν 1 , which remains to be bounded.

Step II : Expectation over censored data We define I = [m] × [m] and observe that the likelihood of the data under ν 0 is

L(Y 1 , ...Y m,m ) = (i,j)∈I (1 -p)1 {Yij =0} + p 2 1 {Yij =1} + p 2 1 {Yij =-1}
and that the likelihood of the data under ν 1 is

L(Y 1 , ...Y m,m ) = E M∼π (i,j)∈I (1 -p)1 {Yij =0} + p(1/2 + M ij /2)1 {Yij =1} + p(1/2 -M ij /2)1 {Yij =-1} .
Thus, the likelihood ratio L between these two distributions is given by

L = E M∼π (i,j)∈I 1 {Yij =0} + (1 + M ij )1 {Yij =1} + (1 -M ij )1 {Yij =-1} .
So we have that

d χ 2 (ν 0 , ν 1 ) 2 + 1 = E Y ∼ν0 L 2 = E Y ∼ν0 E M∼π (i,j)∈I 1 {Yij =0} + (1 + M ij )1 {Yij =1} + (1 -M ij )1 {Yij =-1} 2 = E M,M ′ ∼π i,j 1 -p + p 2 (1 + M ij )(1 + M ′ ij ) + p 2 (1 -M ij )(1 -M ′ ij ) = E M,M ′ ∼π i,j 1 + pM ij M ′ ij . (7.12)
where M ′ is an independent copy of M .

Step III : Conditioning over the cross information Let N r,r ′ be the number of times where the couple

K j = r, K ′ j = r ′ occurs. That is, N r,r ′ := m j=1 1 {Kj=r,K ′ j =r ′ } .
We enumerate the elements inside these groups from 1 to N r,r ′ . We write Ṽ r,r ′ j for the corresponding enumeration of the V j . Setting N = (N r,r ′ ) r,r ′ and using the definition of the prior, we compute

E M,M ′ ∼π i,j 1 + pM ij M ′ ij = E N,U, Ṽ ,U ′ , Ṽ ′ m i=1 r,r ′ ∈{1,...,k} 2 N r,r ′ j=1 1 + pu 2 U r i Ṽ r,r ′ j (U r ′ i ) ′ ( Ṽ r,r ′ j ) ′ =: E N r,r ′ ∈{1,...,k} 2 I(N r,r ′ ) (7.13)
where we define for any N = N r,r ′ > 0

I(N ) = E X,W,X ′ ,W ′ m i=1 N j=1 1 + pu 2 X i W j X ′ i W ′ j
and where (X i ) i≤m , (X ′ i ) i≤m , (W i ) j≤N , (W ′ i ) j≤N are i.i.d. Rademacher random variables. Moreover, we set I r,r ′ (0) = 0.

Step IV : Bound on E N r,r ′ ∈{1,...,k} 2 I(N r,r ′ ). In order to bound I(N ) we use the following lemma proved below Lemma 7.1. Let N = N r,r ′ . There exist constants C 1 , C 2 , C 3 > 0 such that for v small enough

I(N ) ≤ exp C 1 v 4 N/m exp C 2 v 4 k 2 N m 2 exp C 3 v 4 N 2 k 2 /m 2 . (7.14)
Using (7.12), (7.13) and (7.14) we have that

d χ 2 (ν 0 , ν 1 ) 2 + 1 = E N r,r ′ ∈{1,...,k} 2 I(N r,r ′ ) (7.15) ≤ E N     exp   C 2 v 4 k 2 m 2 r,r ′ N r,r ′       exp   C 1 v 4 m r,r ′ N r,r ′       r,r ′ ∈{1,...,k} 2 exp C 3 v 4 N 2 r,r ′ k 2 /m 2     = exp C 2 v 4 k 2 m + C 1 v 4 E N   r,r ′ ∈{1,...,k} 2 exp C 3 v 4 N 2 r,r ′ k 2 /m 2   , (7.16)
since r,r ′ N r,r ′ = m. We bound the expectation of the stochastic term in (7.16) using the following lemma proved below:

Lemma 7.2. There exists a constant C ′ > 0 such that for v small enough we have

E N r,r ′ exp C 3 v 4 N 2 r,r ′ k 2 /m 2 ≤ 1 + 2C ′ v 4 + exp -m/k 2 . (7.17)
Inserting (7.17) into (7.16) and summarizing all the steps we obtain

0 ≤ d χ 2 (ν 0 , ν 1 ) 2 ≤ C v 2 + exp -m/k 2 = o(1)
for a constant C > 0 and therefore, letting η → 0,

E 0 [Ψ] + sup H1 E H1 [1 -Ψ] ≥ (1 -η) 1 - d χ 2 (ν 0 , ν 1 ) η -o(1) = 1 -o(1).
Proof of Lemma 7.1. Note that, by construction of P, we have that

N = N r,r ′ ≤ m/k
since the number of j where M .,j corresponds to K j = r is bounded by m/k. As the product of two independent Rademacher random variables is again a Rademacher random variable, we have

I(N ) = E R,R ′ m i=1 N j=1 1 + pu 2 R i R ′ j , where R = (R i ) m i=1 , R ′ = (R ′ i ) N i=1
are independent Rademacher vectors of length m and N , respectively. The usual strategy to use 1 + x ≤ e x and then to bound iterated exponential moments of Rademacher variables (as in the proof of Theorem 1 of [START_REF] Carpentier | On signal detection and confidence sets for low rank inference problems[END_REF]) only works when k = const, and a more refined estimate is required for growing k, as relevant here. We now bound I(N ) for a fixed N, m/k ≥ N > 0. Using the binomial theorem twice we have

I(N ) = E R ′ 1 2 N j=1 1 + pu 2 R ′ j + 1 2 N j=1 1 -pu 2 R ′ j m = 1 2 m m s=1 m s 1 2 1 + pu 2 s 1 -pu 2 m-s + 1 2 1 -pu 2 s 1 + pu 2 m-s N = 1 2 m 2 N m s=1 m s N q=1 N q 1 + pu 2 sq+(m-s)(N -q) 1 -pu 2 (m-s)q+s(N -q) = E Q,S 1 + pu 2 SQ+(m-S)(N -Q) 1 -pu 2 (m-S)Q+S(N -Q) with independent Binomial random variables S ∼ B(1/2, m), Q ∼ B(1/2, N ). If A := 1-pu 2 1+pu 2
, we obtain

I(N ) = E Q,S 1 + pu 2 mN 1 -pu 2 1 + pu 2 SN +mQ-2SQ = 1 + pu 2 mN E Q A mQ E S A S(N -2Q) = 1 + pu 2 mN E Q A mQ 2 -m A (N -2Q) + 1 m = 1 + pu 2 mN E Q A N m/2 1 2 A (N/2-Q) + 1 2 A (-N/2+Q) m = 1 -p 2 u 4 mN/2 E Q 1 2 A Q-N/2 + 1 2 A N/2-Q m .
Now, we denote x := pu 2 = 4vk 1/2 /m ≤ 1/2 for v small enough. Furthermore, we Taylor expand log(A) about 1 up to second order, i.e.

log(A) = log(1 -x) -log(1 + x) = -2x - 1 2 1 ξ 2 1 - 1 ξ 2 2 x 2 =: -2x -c(x)x 2 for ξ 1 ∈ [1/2, 1], ξ 2 ∈ [1, 3/2]
and where c(x) ∈ [0, 16/9] since x ≤ 1/2. Hence, using also the inequality e x ≤ 1 + x + x 2 /2 + x 3 /6 + 2x 4 we deduce

I(N ) ≤ exp -mN x 2 /2 E Q 1 2 exp -2x(Q -N/2) -c(x)(Q -N/2)x 2 ) + 1 2 exp -2x(N/2 -Q) -c(x)(N/2 -Q)x 2 ) m ≤ exp -mN x 2 /2 • E Q 1 2 1 -2x(Q -N/2) -c(x)(Q -N/2)x 2 + (-2x(Q -N/2) -c(x)(Q -N/2)x 2 ) 2 /2 + (-2x(Q -N/2) -c(x)(Q -N/2)x 2 ) 3 /6 + 2(-2x(Q -N/2) -c(x)(Q -N/2)x 2 ) 4 + 1 2 1 -2x(N/2 -Q) -c(x)(N/2 -Q)x 2 + (-2x(N/2 -Q) -c(x)(N/2 -Q)x 2 ) 2 /2 + (-2x(N/2 -Q) -c(x)(N/2 -Q)x 2 ) 3 /6 + 2(-2x(N/2 -Q) -c(x)(N/2 -Q)x 2 ) 4 m .
Since x ≤ 1/2 and |N/2 -Q|x ≤ 1/4 there exist two constants c 2 = c 2 (x) = c(x)/2 + c(x) 2 /32 ≤ 1 and c 1 = c 1 (x) = 32 + 32c(x) + 12c(x) 2 + 2c(x) 3 + c(x) 4 /8 ≤ 140 such that the last equation above can be bounded by

≤ exp -mN x 2 /2 E Q 1 + 2x 2 (Q -N/2) 2 + c 1 |Q -N/2| 4 x 4 + c 2 |Q -N/2|x 2 m ≤ exp -mN x 2 /2 E Q exp mx 2 (N -2Q) 2 /2 + c 1 m(Q -N/2) 4 x 4 + c 2 m|Q -N/2|x 2 = E Q exp m 2 x 2 (2Q -N ) 2 -N x 2 exp c 1 m(Q -N/2) 4 x 4 + c 2 m|Q -N/2|x 2 .
Using the Cauchy-Schwarz inequality twice, this implies that

I(N ) ≤ E Q exp mx 2 N (2Q -N ) 2 /N -1 E Q exp c 1 mx 4 (N -2Q) 4 /4 • E Q exp 2c 2 m|2Q -N |x 2 1/4 =: (I)(II) 1/4 (III) 1/4 .
Step 1 : Bound on term (III) Since Q ∼ B(1/2, N ), since (2Q -N ) is symmetric and since 2c 2 mx 2 ≤ 1/2 we have that

(III) = E Q exp 2c 2 m|2Q -N |x 2 ≤ 2E Q exp 2c 2 m(2Q -N )x 2 = 2 exp 2c 2 mx 2 + exp -2c 2 mx 2 N ≤ 2 1 + 8c 2 2 m 2 x 4 N ≤ exp 8c 2 2 m 2 x 4 N ≤ exp C 2 v 4 k 2 N m 2 . ( 7.18)
Step 2 : Term (II) We use mN 2 x 4 ≤ 64v 4 /m, (N -2Q) 2 ≤ N 2 and N ≤ m/k to obtain

(II) ≤ E Q exp 64c 1 v 4 N/m • (N -2Q) 2 /N .
Since Q ∼ B(1/2, N ) the Rademacher average Z = (N -2Q)/ √ N is sub-Gaussian with sub-Gaussian constant at most 1. It hence satisfies (e.g., equation (2.24) in [START_REF] Giné | Mathematical Foundations of Infinite-Dimensional Statistical Methods[END_REF]) for c > 2

E exp{Z 2 /c 2 } ≤ 1 + 2 c 2 /4 -1 ≤ e c3c -2 ,
which for v small enough and the choice c -2 = 64c 1 v 4 N/m implies for some constant

C 1 that (II) ≤ exp 4C 1 v 4 N m .
Step 3 : Term (I)

We have that

(I) = E Q exp mN x 2 (2Q -N ) 2 N -1 = E   exp   16v 2 N k m   1 N N i=1 ε i 2 -1       = E   exp   16v 2 k m i =j,i,j≤N ε i ε j     ,
where ε i are i.i.d. Rademacher random variables. If A = (a ij ) is a symmetric matrix with all elements on the diagonal equal to zero, then for the Laplace transform of an order-two Rademacher chaos Z = i,j a ij ε i ε j we have the inequality

Ee λZ ≤ exp 16λ 2 A 2 F 2 (1 -64 A λ) , λ > 0,
see, e.g., Exercise 6.9 on p.212 in [START_REF] Boucheron | Concentration inequalities[END_REF] with T = {A}. Now take A = (δ i =j ) i,j≤N so that we have A ≤ N and for v small enough 16v 2 kN/m ≤ 16v 2 ≤ 1/128.

E exp 16v 2 k m i =j,i,j≤N ε i ε j ≤ exp 16 3 v 4 k 2 A 2 F 2m 2 (1 -1024v 2 k A /m) ≤ exp 16 3 v 4 k 2 N 2 m 2
and therefore we conclude for a constant C 3 > 0 that

(I) ≤ exp 2C 3 v 4 k 2 N 2 /m 2 . (7.19)
Step 4 : Conclusion on I(N ) Combining the bounds for (I), (II) and (III) with the bound on I(N ) we have that

I(N ) ≤ exp C 2 v 4 k 2 N/m 2 exp C 1 v 4 N/m exp C 3 v 4 k 2 N 2 /m 2 .
Proof of Lemma 7.2. We bound the expectation by bounding it separately on two complementary events. For this we consider the event ξ where all N r,r ′ are upper bounded by τ := 15m/k 2 , assumed to be an integer (if not replace it by its integer part plus one in the argument below). More precisely we define

ξ = ∀r ≤ k, ∀r ′ ≤ k : N r,r ′ ≤ τ .
Note that {N r,r ′ > τ } occurs only if the size of the intersection of the class r of partition P with the class r ′ of partition P ′ is larger than τ . This means that at least τ elements among m/k elements of the class r ′ , must belong to the class r. The positions of these τ elements can be taken arbitrarily within the m/k elements.

For the first element, among those τ , the probability to belong to the class r is m/k m . For the second element this probability is m/k m-1 or (m/k)-1

m-1 and so on. All these probabilities are smaller than (m/k)/(mm/k + 1). Therefore we have

P N (N r,r ′ > τ ) ≤ m/k τ m/k m -m/k + 1 τ ≤ (m/k) τ τ ! (2/k) τ ≤ 2 τ (m/k 2 ) τ τ -τ e τ ≤ e -τ ,
where we use m/k τ ≤ (m/k) τ τ ! and Stirling's formula. Using a union bound this implies that the probability of ξ is lower bounded by 1k 2 exp(-15m/k 2 ). We have on the event ξ

E N 1{ξ} r,r ′ ∈{1,...,k} 2 exp C 3 v 4 N 2 r,r ′ k 2 /m 2 ≤ exp C 3 v 4 k 2 • 15 2 (m/k 2 ) 2 k 2 /m 2 ≤ exp C ′ v 4 ≤ 1 + 2C ′ v 4 .
for C ′ = 225C 3 and for v small enough. Moreover, by definition of N r,r ′ , we have that N r,r ′ ≤ m/k and

r,r ′ N r,r ′ = m. Hence r,r ′ N 2 r,r ′ ≤ km 2 /k 2 = m 2 /k which implies that on ξ C E N 1{ξ C } r,r ′ ∈{1,...,k} 2 exp C 3 v 4 N 2 r,r ′ k 2 /m 2 ≤ P N (ξ C ) exp C 3 v 4 k ≤ k 2 exp -15m/k 2 + C 3 v 4 k ≤ k 2 exp -3m/k 2 ≤ exp -m/k 2 ,
for v small enough and since k 3 ≤ m. Thus, combining the bounds on ξ and ξ C , we have that

E N r,r ′ exp C 3 v 4 N 2 r,r ′ k 2 /m 2 ≤ 1 + 2C ′ v 4 + exp -m/k 2 .
8 Auxiliary results

P(X i ∈ S) ≥ n 8m 1 m 2 , n/4 < i ≤ n/2.
Furthermore, when sampling an element from S we have to remove this element from S as we have to use the entry that is stored in S to form a pair of entries. Hence the probability to sample another element from S decreases and is bounded by

P(X j ∈ S\{X i } X i ∈ S) ≥ n -1 8m 1 m 2 for n/4 < i < j < n/2. We deduce by induction for j > i + k and k ≤ n/2 -i -1 that P(X j ∈ S\{X i , ..., X i+k } X i , ..., X i+k ∈ S) ≥ n -k 8m 1 m 2 which yields P N ≥ n 2 64m 1 m 2 ≥ P   n/4<i≤n/2 1 {Xi∈S} ≥ n 2 64m 1 m 2   ≥ P   n/4<i≤n/2 Z i ≥ n 2 64m 1 m 2   (8.1)
where Z i can be taken to be Bernoulli random variables with success probability

p ′ = n -n 2 64m1m2 8m 1 m 2 .
Then, Bernstein's inequality for bounded random variables (see e.g. Theorem 3.1.7 in [START_REF] Giné | Mathematical Foundations of Infinite-Dimensional Statistical Methods[END_REF]), (8.1) and the estimates

E   n/4<i≤n/2 Z i   ≥ n 2 33m 1 m 2 which holds for n ≤ m 1 m 2 and Var   n/4<i≤n/2 Z i   ≤ n 2 32m 1 m 2 imply that P N ≥ n 2 64m 1 m 2 ≥ 1 -P   n/4<i≤n/2 Z i -E   n/4<i≤n/2 Z i   ≤ -n 2 72m 1 m 2   ≥ 1 -exp n 2 372m 1 m 2 .
(B ij -p)(A ij -M ij ) 2 - p 2 M 0 -A 2 F   ≤ 0
where C = 8072.

Proof. We have, using a union bound, that

P   sup A∈A(a,m), M-A F ≥Ca √ (rank(A)∨1)d/p   i,j (B ij -p)(A ij -M ij ) 2 - p 2 M 0 -A 2 F   > 0   ≤ m k=1 P   sup A∈A(a,k), p M-A 2 F ≥C 2 a 2 kd   i,j (B ij -p)(A ij -M ij ) 2 - p 2 A -M 2 F   > 0   . (8.2)
Then, using a peeling argument each of the terms in (8.2) can be bounded by

s∈N: C 2 a 2 kd/2≤2 s <∞ P   sup A∈A(a,k), 2 s ≤p A-M 2 F ≤2 s+1 i,j (B ij -p)(A ij -M ij ) 2 > 2 s /2   ≤ s∈N: C 2 a 2 kd/2≤2 s <∞ P   sup A∈A(a,k), p A-M 2 F ≤2 s+1 i,j (B ij -p)(A ij -M ij ) 2 > 2 s /2   (8.3)
with the convention that if the supremum is taken over an empty set the corresponding probability is set equal to 0. For the cases where the supremum is not taken over an empty set, we apply Lemma 8.2 (with choices ξ ij = 1, q = 2, z = 4, U = 1 and t = 2 s there ) and obtain for

Z(s) : = sup A∈A(a,k), p A-M 2 F ≤2 s+1 i,j (B ij -p)(A ij -M ij ) 2
that we can bound

P (Z(s) > 2 s /2) ≤ exp -2 s 260352a 2
Hence, (8.3) can be upper bounded by

s∈N: Ca 2 kd/2≤2 s <∞ exp -2 s 260352a 2 ≤2 exp - C 2 kd 260352 ≤ 2 exp(-101d).
The result then follows by noting that log(m) ≤ d.

Z(t) := sup A∈A(a,k0), p A-M 2 F ≤2t i,j [(B ij ξ ij -EB ij ξ ij )(A ij -M ij ) q ]
is not empty. Then,

P Z(t) > t √ z ≤ exp -t 32 2 (8(2a) 2q-2 U 2 z + 505(2a) q U √ z/32) (8.4)
Proof. We first bound EZ(t) and then apply Talagrand's [START_REF] Talagrand | New concentration inequalities in product spaces[END_REF] inequality. Using symmetrization (e.g. Theorem 3.1.21 in [START_REF] Giné | Mathematical Foundations of Infinite-Dimensional Statistical Methods[END_REF]) and two contraction inequalities (e.g. Theorems 3.1.17 and 3.2.1 in [START_REF] Giné | Mathematical Foundations of Infinite-Dimensional Statistical Methods[END_REF]), we obtain that

EZ(t) ≤ 2U E   sup A∈A(a,k0), p A-M 2 F ≤2t i,j B ij ε ij (A ij -M ij ) q   ≤ 2(4a) q-1 U E   sup
A∈A(a,k0), p A-M 2 F ≤2t i,j

B ij ε ij (A ij -M ij )   ≤ 2(4a) q-1 U E sup A∈A(a,k0), p A-M 2 F ≤2t | Σ R , A -A 0 | + 2(4a) q-1 U E | Σ R , A 0 -M | ≤ 8(4a) q-1 U k 0 t/pE Σ R + 2(4a) q-1 U E | Σ R , A 0 -M | . (8.5)
where ε ij are independent Rademacher random variables, Σ R := B ij ε ij ij and where A 0 is an arbitrary element in A(a, k 0 ) such that p A 0 -M 2 F ≤ 2t. Such an A 0 exists as soon as the supremum is not taken over an empty set. An extension of Corollary 3.6 in [START_REF] Bandeira | Sharp nonasymptotic bounds on the norm of random matrices with independent entries[END_REF] to rectangular matrices by selfadjoint dilation (e.g. section 3.1. in [START_REF] Bandeira | Sharp nonasymptotic bounds on the norm of random matrices with independent entries[END_REF]) implies (with choices

ξ ij = B ij ε ij / √ p, b ij = √ p,
E| Σ R , A 0 -M | ≤ (Var( Σ R , A 0 -M )) 1/2 = p A 0 -M 2 F 1/2 ≤ √ 2t.
Hence, for C 2 z(4a) 2q-2 U 2 k 0 d/2 ≤ t and since C = 1009 we have that EZ(t) ≤ 688(4a) q-1 U k 0 td + 2(4a) q-1 U √ 2t ≤ 31t/(32 √ z). (8.6)

We now make use of the following inequality due to Talagrand [START_REF] Talagrand | New concentration inequalities in product spaces[END_REF], which in the current form with explicit constants can be obtained by inverting the tail bound in Theorem 3.3.16 in [START_REF] Giné | Mathematical Foundations of Infinite-Dimensional Statistical Methods[END_REF].

Theorem 8.1. Let (S, S) be a measurable space and let n ∈ N. Let X k , k = 1, . . . , n be independent Svalued random variables and let F be a countable set of functions f = (f 1 , ..., f n ) : S n → [-K, K] n such that Ef k (X k ) = 0 for all f ∈ F and k = 1, ..., n. Set

Z := sup f ∈F n k=1 f k (X k ).
Define the variance proxy

V n := 2KEZ + sup f ∈F n k=1 E (f k (X k )) 2 .
Then, for all t ≥ 0, P (Z -EZ ≥ t) ≤ exp -t 2 4V n + (9/2)Kt .

The functional A → A -M 2 F is continuous on the compact set of matrices {A ∈ A(a, k 0 ) : A -M 2 F ≤ 2t}, hence by continuity and compactness the supremum is attained over a countable subset. Thus we may apply Talagrand's inequality to Z(t). We have for our particular case, since sup f ∈F |f (X)| = sup f ∈{F {-F }} f (x), that

X ij = B ij ξ ij -EB ij ξ ij , S = [-2U, 2U ] F = f : S m1×m2 → [-2(2a) q U, 2(2a) q U ] m1×m2 , f ij (X ij ) = (-1) l X ij (A ij -M ij ) q , A ∈ A(a, k 0 ), p A -M 2 F ≤ 2t, l ∈ {0, 1}
and moreover sup (A,l), A∈A(a,k0), p A-M 2 F ≤2t, l∈{0,1} i,j

E (-1) l (B ij ξ ij -EB ij ξ ij )(A ij -M ij ) q 2
≤(2a) 2q-2 sup A∈A(a,k0), p A-M 2 F ≤2t i,j

Var(B ij ξ ij )(A ij -M ij ) 2 ≤(2a) 2q-2 U 2 sup A∈A(a,k0), p A-M 2 F ≤2t i,j p(A ij -M ij ) 2 ≤ 2(2a) 2q-2 U 2 t.
Therefore, using our previous estimate in (8.6) for EZ(t) as well, we have for the variance proxy V m1m2 that

V m1m2 ≤ 2(2a)

An oracle estimator in the Bernoulli model

Here we prove that the soft-thresholding estimator proposed by Koltchinskii et. al. [START_REF] Koltchinskii | Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion[END_REF] for the traceregression setting fulfills the oracle inequality (2.8) in the Bernoulli model. Their estimator is defined as M ∈ arg min

A∈R m 1 ×m 2 A 2 F m 1 m 2 - 2 n Y, A + λ A * (8.7)
where λ is a tuning parameter which we choose as

λ = 3 3 √ 2σ + √ 2CU √ mn (8.8)
where C > 0 is the constant in Corollary 3.12 in [START_REF] Bandeira | Sharp nonasymptotic bounds on the norm of random matrices with independent entries[END_REF]. Proof. Going through the proof of Theorem 2 and Corollary 2 in [START_REF] Koltchinskii | Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion[END_REF] line by line we see that we only need to bound the spectral norm of the matrix

Σ := 1 n (B ij ǫ ij ) i,j
by λ/3 with high probability. Using self-adjoint dilation to generalize Corollary 3.12 and Remark 3.13 in [START_REF] Bandeira | Sharp nonasymptotic bounds on the norm of random matrices with independent entries[END_REF] for rectangular matrices (with choices ε = 1/2, σ * = U and σ = max

  max j m1 i=1 E σ B 2 ij ǫ 2 ij , max i m2 j=1 E σ B 2 ij ǫ 2 ij   = σ n/m
there) we obtain

P σ n i=1 ε i X i > 3 √ 2σ n m + t ≤ d exp - -t 2 C 1 U 2
for a constant C 1 > 0. Choosing t = √ 2C 1 U n m and using that n ≥ m log(d) yields that Ξ occurs with P σ -probability at least 1 -1/d.

8. 2 1 Lemma 8 . 1 .

 2181 Lemma 8.Consider the Bernoulli model (1.3) and assume n ≥ m log(d). Then, with probability at least 1 -2 exp(-100d) we have for any given M ∈ A(a, m) that sup A∈A(a,m), M-A F ≥Ca √

  α = 3 andσ = max max j m1 i=1 b 2 ij , max i m2 j=1 b 2 ij ≤ √ pd there ) that E Σ R ≤ e 2/3 (2 pd + 42 log(d)) ≤ 86 pd since m log(d) ≤ n.For the second term in (8.5) we have

Proposition 8 . 3 .M -M 0 2 F m 1 m 2 ≤ inf A∈R m 1 ×m 2 M 0 -A 2 F

 83222 Consider the Bernoulli model(1.3). Assume n ≥ m log(d) and that Assumption 1.1 is fulfilled. Let M be given as in (8.7) with a choice of λ as in (8.8). Then, with P M0,σ -probability of at least 1 -1/d we have for any M 0 ∈ A(a, m) that C = C(a, σ, U ) > 0.

  Proof. Assume that among the first n/4 samples we have less than n/8 entries that are sampled twiceotherwise the result holds since n/8 ≥ n 2 /64m 1 m 2 for n ≤ m 1 m 2 . Then, among the first n/4 samples, there are at least n/8 distinct elements of B, the set of all standard basis matrices in R m1×m2 , that have been sampled at least once. We write S for the set of distinct elements of {X i } i≤n/4 and obviously have |S| ≥ n/8. Hence, by definition of the sampling scheme, we have that

	8.1 Proof of Lemma 4.1

  Lemma 8.2. Consider the Bernoulli model(1.3). Suppose that ξ ij are independent random variables with max ij |ξ ij | ≤ U and that m log(d) ≤ n. Let z > 0, q ∈ {1, 2}, M ∈ A(a, m) and 1 ≤ k 0 < m be given. Finally, for C = 1009 suppose that t ∈ R + is such that t ≥ C 2 z(4a) 2q-2 U 2 k 0 d/2 and that the supremum in

	8.3 Lemma 8.2

  2q-2 U 2 t + 31(2a) q U t/(8 √ z).

	Hence, using (8.6) and Talagrand's inequality, we obtain
	P Z(t) >	t √ z	≤ P Z(t) -EZ(t) >	t 32 √ z	≤ exp	-t 32 2 (8(2a) 2q-2 U 2 z + 505(2a) q U	√ z/32)	.

Acknowledgements

The work of A. Carpentier is supported by the DFGs Emmy Noether grant MuSyAD (CA 1488/1-1). The work of O. Klopp was conducted as part of the project Labex MME-DII (ANR11-LBX-0023-01). The work of M. Löffler was supported by the UK Engineering and Physical Sciences Research Council (EPSRC) grant EP/L016516/1 and the European Research Council (ERC) grant No. 647812. The latter ERC grant also supported R. Nickl, who is further grateful to A. Tsybakov and ENSAE Paris for their hospitality during a visit in April 2016 where part of this research was undertaken.


Vincent V Planche
email: planche.vincent@gmail.com

Aurélie Ruet

Pierrick S Coupé

Delphine Lamargue-Hamel

Mathilde Deloire

Bruno Pereira

José S Manjon

Fanny Munsch

Nicola Moscufo

Dominik S Meier

José V Manjon

Charles R G Guttmann

Vincent Dousset

Bruno Brochet

Thomas Tourdias

Hippocampal microstructural damage correlates with memory impairment in clinically isolated syndrome suggestive of multiple sclerosis

Keywords: multiple sclerosis, clinically isolated syndrome, hippocampus, memory impairment, diffusion tensor imaging

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Cognitive impairment is frequent in multiple sclerosis (MS) [START_REF] Chiaravalloti | Cognitive impairment in multiple sclerosis[END_REF][START_REF] Rocca | Clinical and imaging assessment of cognitive dysfunction in multiple sclerosis[END_REF] and strongly impacts quality of life and vocational status [START_REF] Ruet | Cognitive impairment, health-related quality of life and vocational status at early stages of multiple sclerosis: a 7-year longitudinal study[END_REF]. The two most frequently affected domains are information processing speed (IPS) and episodic memory [START_REF] Chiaravalloti | Cognitive impairment in multiple sclerosis[END_REF]. While IPS impairment is usually explained by disconnections due to demyelinating lesions and diffuse brain damage [START_REF] Dineen | Disconnection as a mechanism for cognitive dysfunction in multiple sclerosis[END_REF], several groups have reported that memory impairment could be more specifically related to hippocampal atrophy [START_REF] Sicotte | Regional hippocampal atrophy in multiple sclerosis[END_REF][START_REF] Benedict | Memory impairment in multiple sclerosis: correlation with deep grey matter and mesial temporal atrophy[END_REF][START_REF] Longoni | Deficits in memory and visuospatial learning correlate with regional hippocampal atrophy in MS[END_REF][START_REF] Koenig | Hippocampal volume is related to cognitive decline and fornicial diffusion measures in multiple sclerosis[END_REF].

Significant memory impairment is already present at the stage of clinically isolated syndrome (CIS) [START_REF] Achiron | Cognitive impairment in probable multiple sclerosis[END_REF][START_REF] Feuillet | Early cognitive impairment in patients with clinically isolated syndrome suggestive of multiple sclerosis[END_REF], the first clinical episode suggestive of MS. However, hippocampal damage is typically not detected at this early stage of MS because atrophy is not yet observed or still confined to few locations such as the thalamus or the striatum [START_REF] Henry | Regional grey matter atrophy in clinically isolated syndromes at presentation[END_REF][START_REF] Rocca | Clinically Isolated Syndrome Suggestive of Multiple Sclerosis: Dynamic Patterns of Gray and White Matter Changes-A 2-year MR Imaging Study[END_REF][START_REF] Calabrese | The predictive value of gray matter atrophy in clinically isolated syndromes[END_REF][START_REF] Audoin | Atrophy mainly affects the limbic system and the deep grey matter at the first stage of multiple sclerosis[END_REF]. To the best of our knowledge, only one study has reported hippocampal atrophy in a CIS group with high T2-lesion load [START_REF] Bergsland | Subcortical and cortical gray matter atrophy in a large sample of patients with clinically isolated syndrome and early relapsing-remitting multiple sclerosis[END_REF]. Therefore, there is a need for imaging biomarkers more sensitive than atrophy, especially at the stage of CIS, which could reflect clinically relevant hippocampal alterations to help the development and validation of future neuroprotective strategies.

Diffusion tensor imaging (DTI) has been efficiently used to reveal widespread white matter damages from the stage of CIS [START_REF] Preziosa | Intrinsic damage to the major white matter tracts in patients with different clinical phenotypes of multiple sclerosis: a voxelwise diffusion-tensor MR study[END_REF] but less consistently within grey matter [START_REF] Cappellani | Diffusion tensor MRI alterations of subcortical deep gray matter in clinically isolated syndrome[END_REF][START_REF] Deppe | Early silent microstructural degeneration and atrophy of the thalamocortical network in multiple sclerosis[END_REF]. Specifically, there is no report of altered DTI within the hippocampus of persons with CIS and no strong imaging correlate of memory impairment at this stage. Outside the field of MS, DTI has revealed subtle and early hippocampal alterations in Alzheimer's disease [START_REF] Douaud | Brain microstructure reveals early abnormalities more than two years prior to clinical progression from mild cognitive impairment to Alzheimer's disease[END_REF], but it's currently unknown whether this technique can also be sensitive enough to capture clinically relevant modifications at the very early stage of MS.

In this study, we hypothesized that microstructural damage contributing to early memory impairment could occur in the hippocampus at the stage of CIS and that it might be measurable with DTI while there is no hippocampal atrophy. To test this hypothesis, we measured hippocampal volume and DTI metrics within the hippocampus of persons with CIS (PwCIS) to look for correlations with episodic memory scores and to test their ability to discriminate between memory-impaired and memorypreserved PwCIS. A group of healthy subjects and a group of persons with MS (PwMS) were used as negative and positive controls, respectively.

Methods

Participants

All subjects were prospectively enrolled from 2011 to 2014 at our MS center. Written informed consent was obtained prior to participation.

The main population of interest consisted of thirty-seven persons with CIS (PwCIS) enrolled prospectively after approval by the local institutional ethics review board (NCT01865357) between 2 to 6 months after a first clinical event compatible with a demyelinating inflammatory syndrome. At least two clinically silent lesions with 3 mm minimum diameter were needed for inclusion. One had to be cerebral (ovoid or periventricular), while the other could be located in spine or brain. Exclusion criteria: contraindications to MRI, presence of other neurologic, psychiatric or systemic diseases, steroid treatment within one month, starting or stopping antidepressants or anxiolytic treatments within 2 months of MRI and neuropsychological examination.

We pooled these data with data from a MS study (NCT01207856) to analyze patients with long lasting disease as a positive control. Thirty-two persons with MS (PwMS) diagnosed according to the 2005revised McDonald criteria [START_REF] Polman | Diagnostic criteria for multiple sclerosis: 2005 revisions to the 'McDonald Criteria[END_REF] were included (27 relapsing-remitting, 3 secondary progressive and 2 primary progressive form of MS). Exclusion criteria were dementia (Mini Mental State Examination <27), other neurologic or psychiatric disorders, drug or alcohol abuse, relapse and/or steroid treatment within 2 months, or severe depression (Beck Depression Inventory >27).

A total of seventy-six healthy control (HC) subjects, included as negative controls, were free of neurologic, psychiatric, or systemic diseases, and drug or alcohol abuse. Fifty-four subjects were tightly matched for age, sex and educational level to PwCIS, to calculate cognitive z-score (see below).

The twenty-two additional subjects were matched for age, sex and educational level to PwMS.

Neuropsychological testing

All patients and controls performed the Symbol Digit Modalities Test (SDMT) to assess IPS and the forward digit span subtest of the WAIS-III to assess attention/working memory. In order to assess hippocampal functions (verbal learning and recall), PwCIS and matched controls performed the Selective Reminding Test (SRT) while PwMS and matched controls performed the California Verbal Learning Test (CVLT). Indeed, the SRT was frequently used in previous studies of CIS [START_REF] Achiron | Cognitive impairment in probable multiple sclerosis[END_REF][START_REF] Feuillet | Early cognitive impairment in patients with clinically isolated syndrome suggestive of multiple sclerosis[END_REF] and is part of the brief repeatable battery of neuropsychological testing [START_REF] Boringa | The brief repeatable battery of neuropsychological tests: normative values allow application in multiple sclerosis clinical practice[END_REF] while the CVLT was the most common validated task used to assess episodic verbal memory in previous MS studies [START_REF] Benedict | Memory impairment in multiple sclerosis: correlation with deep grey matter and mesial temporal atrophy[END_REF][START_REF] Koenig | Hippocampal volume is related to cognitive decline and fornicial diffusion measures in multiple sclerosis[END_REF]. The SRT-LTS (Long Term Storage) and the CVLT-immediate recall were considered as measures of learning performance, and DR-SRT (Delayed Free Recall) and DR-CVLT as measures of long term recall performance. Each subject also completed a standard questionnaire concerning depressive symptoms (Beck Depression Inventory, BDI). Each PwCIS or PwMS was compared with the appropriate control group (n=54 and n=22 respectively), tightly matched for age, sex and educational level to calculate a z-score for each test: z = (patient's score -mean value of the matched control group)/standard deviation of the matched control group.

Lower z-score indicates lower performance. A patient was considered impaired in a given cognitive domain if his/her z-score was < -1.5, according to agreed-upon threshold [START_REF] Benedict | Reliability and validity of neuropsychological screening and assessment strategies in MS[END_REF].

MRI acquisition

All

MRI analyses

Lesion load was determined using co-registered T1 and FLAIR sequences and a semi-automated segmentation pipeline based on local thresholding [START_REF] Van Leemput | Automated segmentation of multiple sclerosis lesions by model outlier detection[END_REF] followed by manual correction by a blinded expert (V.P., a neurologist with 4 years of experience).

For volumetric analyses of brain structures, T1-weighted images were processed using the volBrain system (http://volbrain.upv.es). After denoising [START_REF] Manjón | Adaptive non-local means denoising of MR images with spatially varying noise levels[END_REF], images were affine-registered [START_REF] Avants | A reproducible evaluation of ANTs similarity metric performance in brain image registration[END_REF] into the Montreal Neurological Institute (MNI) space and the total brain volume was estimated. Hippocampus was automatically segmented with a patch-based multi-templates method described in details elsewhere [START_REF] Coupé | Patch-based segmentation using expert priors: application to hippocampus and ventricle segmentation[END_REF] that uses expert manual segmentations in MNI space as priors. Anatomical boundaries of the hippocampus were defined according to the EADC-ADNI Harmonized Protocol [START_REF] Frisoni | The EADC-ADNI Harmonized Protocol for manual hippocampal segmentation on magnetic resonance: Evidence of validity[END_REF]. Every mask was then blindly checked and manually corrected (V.P.) for inappropriate inclusion of parahippocampal T1-hypointense lesions, choroidal plexus and/or CSF "pockets". To control for variations in head size, total brain volumes and hippocampal volumes were scaled using the volumetric scaling factor determined through the affine registration to the MNI brain template.

An in-house pipeline (dtiBrain) was used to process diffusion weighted images (DWI). First, images

were denoised [START_REF] Manjón | Diffusion weighted image denoising using overcomplete local PCA[END_REF] in order to improve signal-to-noise ratio. Then, head displacement and distortions induced by eddy currents were corrected by performing affine registration [START_REF] Avants | A reproducible evaluation of ANTs similarity metric performance in brain image registration[END_REF] of all DWI to the b0 images. The direction table was updated with the estimated motion matrices. To compensate for EPI distortion, a non-rigid registration of DWI to the subject's T1-weighted images in MNI space was performed by using ANTs [START_REF] Avants | A reproducible evaluation of ANTs similarity metric performance in brain image registration[END_REF]. For that purpose, we found that registration of mean diffusivity map, derived from DWI, to CSF probability map, derived from T1, provided the most accurate strategy by visual inspection of the hippocampal areas. Then, a diffusion tensor model was fitted at each voxel using FSL 5.0 (http://fsl.fmrib.ox.ac.uk/fsl) to measure mean fractional anisotropy (FA) and mean diffusivity (MD) within the hippocampal masks previously generated from T1-weighted images (Fig.

1A, B and C).

Statistical Analyses

Right All tests were two-tailed, with a type I error set at α=0.05.

Results

Clinical characteristics and general MRI features

A total of 37 PwCIS, 32 PwMS and 36 HC assessed with MRI were included (Table 1). Groups were comparable for age, sex ratio and educational level. PwCIS and PwMS showed significantly higher depression scores than controls but they were not significantly different from each other (p=ns; d=0.39). As expected, EDSS and T2-lesion load were significantly lower in PwCIS than in PwMS.

PwCIS presented no global brain atrophy compared to HC whereas PwMS did.

Cognitive assessment

Median z-scores and percentages of impaired PwCIS and PwMS (z-score < -1.5) are reported in table 2. Regarding mean or median z-scores, as expected, PwMS performed significantly worse than pwCIS for all the tests. Verbal episodic memory performance was the most frequently affected domain in PwCIS (27.0%) whereas slowing of IPS was the most frequently affected domain in PwMS (78.1%).

Hippocampal volume and DTI measures

Hippocampal volumes normalized for head size were not significantly different between groups (p=0. [START_REF] Douaud | Brain microstructure reveals early abnormalities more than two years prior to clinical progression from mild cognitive impairment to Alzheimer's disease[END_REF]). PwMS showed slightly lower volumes compared to HC even though this difference didn't reach significance (mean volume 9.72 ml and 9.99 ml respectively, d=0.31, Fig. 1D). Interestingly, PwCIS and HC were thoroughly similar for their hippocampal volumes (mean volume 10.06 ml and 9.99 ml respectively, d=0.09, Fig. 1D).

Hippocampal

Correlations between MRI measures and cognitive performance (table 3)

In the CIS group, in univariate analyses, the hippocampal MD was the only metric strongly correlated with long-term recall (r=-0.57, p=0.0002); a correlation that remains significant even after correction for the 32 multiple comparisons run between MRI and clinical data (p=0.0050). By contrast, hippocampal volume and T2-lesion load were not correlated with episodic memory. In multivariate analysis, after adjusting for age, gender, depression and T2-lesion load, the correlation between hippocampal MD and performances on long term recall remained significant with an odds ratio of 0.058 (95%CI=0.0057-0.59, p=0.016).

In the MS group, the performances on learning trials were correlated with hippocampal volumes (r=0.44, p=0.01 and β=1.23, 95%CI=0.12-2.34, p=0.032 after adjustments). IPS measures were correlated with T2-lesion load (r=-0.51, p=0.004 and β=-3.5x10 -5 , 95%CI=-6.8x10 -5 --3.12x10 -6 , p=0.033 after adjustments) but also with both hippocampal FA and MD (respectively r=0.36, p=0.04, non-significant after adjustments and r=-0.52, p=0.002; β=-8.95, 95%CI=-15.77--2.13, p=0.012 after adjustments).

Hippocampal MD discriminates between memory-impaired and memory-preserved PwCIS

Regarding the strong association between hippocampal MD and long-term recall memory performances, we tested whether this parameter could discriminate memory-impaired PwCIS from those with normal long-term recall. PwCIS were dichotomized in two subgroups according to their long-term memory performances (i.e. DR-SRT z-score <-1.5). Using ROC analysis we showed that a threshold MD value (MD=1.278x10 -3 mm 2 /s) was discriminating these two subgroups with 90.0% sensitivity, 70.3% specificity, 52.9% positive predictive value (PPV) and 95.0% negative predictive value (NPV) (area under the curve = 0.77, 95%CI=0.62-0.92, p=0.013, Fig. 2A). Hippocampal MD was the only demographical, clinical or radiological characteristic significantly different between memory-impaired and memory-preserved PwCIS (p=0.011, Fig. 2B andtable 4).

Discussion

In this study, hippocampal microstructural alterations measured by DTI appear to be already present in the early stages of MS (PwCIS), while no significant hippocampal or global brain atrophy compared to HC is evident. Furthermore, increased hippocampal MD was associated with early memory impairment in these PwCIS.

A quarter of our population of PwCIS showed episodic verbal memory impairment in learning and retrieval tasks which is consistent with previous studies using the same test [START_REF] Achiron | Cognitive impairment in probable multiple sclerosis[END_REF][START_REF] Feuillet | Early cognitive impairment in patients with clinically isolated syndrome suggestive of multiple sclerosis[END_REF]. Interestingly, memory impairment was more frequent than slowing of IPS in PwCIS. This observation suggests that a neurodegenerative process starts early within the hippocampus contributing to memory decline, even at a stage where IPS is relatively preserved because complete disconnection phenomena due to widespread demyelination are generally lower at the CIS stage than later on [START_REF] Dineen | Disconnection as a mechanism for cognitive dysfunction in multiple sclerosis[END_REF]. Furthermore, our PwCIS were not treated with disease modifying therapies, avoiding bias linked to heterogeneous therapeutic response.

Our data support the concept that early memory deficit in MS could be related to specific hippocampal vulnerability, independent of the extent of focal white matter lesions. Hippocampal FA was significantly decreased in the CIS group and even more in the MS group, in which a significant increase of hippocampal MD was also observed. In previous work assessing PwCIS, deep grey matter DTI changes were detected, while no hippocampal DTI changes were apparent [START_REF] Cappellani | Diffusion tensor MRI alterations of subcortical deep gray matter in clinically isolated syndrome[END_REF]. However, the sensitivity to DTI changes in the hippocampus might have been hampered by partial voluming effects due to a larger voxel size (3.33mm x 3.33mm x 3.00mm) [START_REF] Cappellani | Diffusion tensor MRI alterations of subcortical deep gray matter in clinically isolated syndrome[END_REF], compared with our 1.6mm 3 voxel size.

We also believe that applying a denoising procedure further increased our sensitivity towards microstructural alterations detected by DTI, enabling our findings [START_REF] Manjón | Diffusion weighted image denoising using overcomplete local PCA[END_REF].

In support of the clinical relevance of our finding of early hippocampal damage in PwCIS, we were able to show a strong and independent correlation of hippocampal MD with a hippocampus-dependent task (DR-SRT), but not with cognitive tasks that are not reliant on hippocampal function (i.e, IPS and attention/working memory, even though some authors argue for a continuum between working memory and long term memory encoding [START_REF] Leszczynski | How does hippocampus contribute to working memory processing? Front[END_REF]). Hippocampal MD in PwCIS was correlated to hippocampal-dependent long-term recall in the absence of significant hippocampal volume loss, suggesting that hippocampal MD reflects an earlier pathophysiological process that likely precedes atrophy. Interestingly, and despite smaller differences between groups, the increase in MD appears to be more clinically relevant than the decrease in FA in the explored context. MD might be more stable and reproducible than FA in the hippocampus (i.e. smaller dispersion of the values, even in the control group), which can be reasonably expected in such a grey matter structure where diffusion tends to be more isotropic and therefore imperfectly represented by FA as a measure of fiber orientation.

Therefore either FA and MD measure different underlying histological substrate or, more likely, FA is less reliable than MD in grey matter which is in line with previous results [START_REF] Preziosa | Intrinsic damage to the major white matter tracts in patients with different clinical phenotypes of multiple sclerosis: a voxelwise diffusion-tensor MR study[END_REF][START_REF] Cappellani | Diffusion tensor MRI alterations of subcortical deep gray matter in clinically isolated syndrome[END_REF]. Higher MD might correspond to a mixture of hippocampal demyelination, neuronal or synaptic loss together with inflammatory cells as described in post-mortem studies of MS brains [START_REF] Dutta | Demyelination causes synaptic alterations in hippocampi from multiple sclerosis patients[END_REF].

We also showed that hippocampal MD discriminates memory-impaired from memory-preserved patients with a sensitivity of 90%, a specificity of 70.3% and a NPV of 95.0%. Among clinical and other MRI criteria, hippocampal MD was the only predictor of memory impairment in this group.

Therefore, stabilization of low hippocampal MD might be an interesting candidate endpoint (surrogate marker with a very good NPV) in future proof-of-concept phase II clinical trials in CIS and early MS.

Unambiguous monitoring of cognitive performances in the context of a neuroprotective agent in clinical trials is complicated by the length of the cognitive testing, the test/retest effect and confounding factors such as participation of the subject, fatigue or depression [START_REF] Benedict | Risk factors for and management of cognitive dysfunction in multiple sclerosis[END_REF]. In this context, stabilization of low hippocampal MD might provide a complementary and unbiased endpoint. DTI of the hippocampus might also help to improve patient selection by stratifying those with and without hippocampal damage, therefore powering future neuroprotective trials by including more homogeneous population in comparison groups.

In contrast, in PwMS, episodic memory correlated with hippocampal volume, but the correlation between hippocampal MD and memory scores was not significant. This finding suggests that at a more advanced stage, assessing the microstructure of the hippocampus with DTI might no longer be sensitive and relevant. Furthermore, T2-lesion load and hippocampal DTI metrics were correlated with IPS scores. These findings can suggest that hippocampus is involved in IPS but also that hippocampal DTI at the stage of clinically definite MS reflects more general brain damage and in turn correlate better with IPS that has been associated to global cerebral damage [START_REF] Rocca | Clinical and imaging assessment of cognitive dysfunction in multiple sclerosis[END_REF]. This is consistent with data in the literature showing that cognitive impairment is associated with several imaging metrics in more advanced MS [START_REF] Daams | Multi-parametric structural magnetic resonance imaging in relation to cognitive dysfunction in long-standing multiple sclerosis[END_REF] because cognitive impairment is probably the result of a complex interplay between several alterations at this stage [START_REF] Preziosa | Structural MRI correlates of cognitive impairment in patients with multiple sclerosis: A Multicenter Study[END_REF].

We acknowledge an important shortcoming of this meta-analysis of our data, namely that the cognitive testing was different for the CIS and MS groups, limiting our ability to directly compare PwCIS to PwMS. Nevertheless, a previous paper reported no difference in sensitivity between SRT and CVLT [START_REF] Strober | Sensitivity of conventional memory tests in multiple sclerosis: comparing the Rao Brief Repeatable Neuropsychological Battery and the Minimal Assessment of Cognitive Function in MS[END_REF] and furthermore, we believe that the insights gained by separately comparing these groups of patients to matched HC explored with the same tests maintain full validity. We also acknowledge that the sample size of each group is relatively small and therefore these results can be viewed as preliminary and need confirmation in a larger cohort of PwCIS. Another limitation is that we didn't acquire 3D-double inversion recovery MRI, limiting our ability to detect focal hippocampal lesions [START_REF] Calabrese | Imaging distribution and frequency of cortical lesions in patients with multiple sclerosis[END_REF]. Therefore, our DTI findings might reflect focal, as well as more diffuse alterations in the hippocampus. Because the PPV was only 52.9%, it will be of great interest for future studies to assess whether PwCIS with increased hippocampal MD but preserved memory functions display compensatory mechanisms measured by hippocampal activation and functional connectivity, as demonstrated in PwMS [START_REF] Hulst | Memory impairment in multiple sclerosis: Relevance of hippocampal activation and hippocampal connectivity[END_REF]. Similarly, longitudinal data should identify whether those patients are likely to show memory alterations in long-term follow-up. DTI could also be combined with susceptibility weighted imaging that could also reveal subtle alterations because it has been demonstrated that iron deposition is present within the hippocampus at the stage of CIS [START_REF] Hagemeier | Iron deposition on SWI-filtered phase in the subcortical deep gray matter of patients with clinically isolated syndrome may precede structurespecific atrophy[END_REF].

In conclusion, episodic memory impairment was correlated with hippocampal DTI changes at the stage of CIS, in the absence of a significant effect of global lesion volume or atrophy on any of the cognitive measures. This argues for a clinically relevant neurodegenerative process occurring in the hippocampus in the early stages of MS, and suggests that DTI measurement in this structure might provide a sensitive indicator of early neurodegenerative changes.

Figures captions

Figure 1 :

 1 Figure 1: Hippocampal volumes and DTI measures in patients and controls.

Figure 2 :

 2 Figure 2: Hippocampal MD discriminates between memory-impaired and memory-preserved

  Sidak's correction was used to reduce the risk of type I error. Lastly, Receiver Operating Characteristic (ROC) analysis was performed to test the value of DTI to discriminate between memory-impaired PwCIS (z-score DR-SRT < -1.5) versus those with normal memory performance.

and left hippocampal values were averaged. Statistical analyses were performed with Stata software 12 (StataCorp) and Prism software 6 (Graphpad). The distribution of all continuous data was tested with the Shapiro-Wilk test. We first compared clinical and imaging characteristics between the three groups (HC, CIS, MS) by using the Chi-squared test for categorical variables, and ANOVA or Kruskal-Wallis test (when assumptions of ANOVA were not met) for ordinal variables followed by appropriate post-hoc tests (Tukey-Kramer or Dunn test, respectively), and adjustment on age and gender. If only two groups had to be compared, Student's t-test or Mann-Whitney test was used as appropriate. Cohen's d was used to measure the effect size. Then, relationships between clinical scores and quantitative imaging variables were assessed using correlation coefficients (Pearson or Spearman according to statistical distribution) for CIS and MS groups respectively. The associations were further tested in multivariate context to take into account adjustment on covariables fixed according to univariate results and clinical relevance: age, gender, depression and T2 lesion load. For that purpose, cognitive performances (dependent variables) were predicted with regression models. Linear regression model was used whenever possible while logistic regression was seen as the appropriate alternative for categorical outcome variables by dichotomizing the performances; a log transformation was applied when needed to achieve normality. Considering the issue of multiple comparisons,

  FA and MD were significantly different between groups (p<0.0001 for both measures, Post-hoc analyses showed that FA was significantly decreased in PwCIS compared to HC (p=0.050, adjusted for age and gender; d=0.53), as well as in PwMS compared to HC (p<0.0001; d=1.05) and compared to PwCIS (p=0.007; d=0.70). In PwMS, MD was significantly increased compared to HC (p<0.0001; d=1.21) and compared to PwCIS (p=0.004; d=0.65). The difference in MD between PwCIS and HC did not reach a statistically significant level (p=0.093; d=0.41), but the graphical distribution of hippocampal MD values in the CIS group showed a sub-group with distinctly higher MD values compared to HC.

adjusted for age and gender: FA=0.171, 0.162 and 0.149; MD=1.269, 1.281 and 1.319 x10 -3 mm 2 /s for HC, CIS and MS groups respectively; Fig.

1E and F

).

Table 1 : Clinical and general MRI features. BDI

 1 = Beck Depression Inventory; CIS = Clinically Isolated Syndrome; MS = Multiple Sclerosis; EDSS = Expanded Disability Status Scale. § Education level was considered as high or low according to French baccalaureate (equivalent to A-level). ** p<0.01 and ***p<0.001, patients vs controls.

	Controls with MRI (n=36)	CIS (n=37)	MS (n=32)	p-value

Table 2 : Neuropsychological performances of persons with CIS and persons with MS

 2

	CIS (n=37)	T2 Lesion load	Hippocampal Volume	Hippocampal FA	Hippocampal MD
	Information processing speed	r=-0.13, p=0.45	r=0.04, p=0.84	r=0.10 p=0.54	r=-0.23, p=0.18
	Attention/Working memory	r=-0.16, p=0.36	r=-0.11, p=0.53	r=-0.17, p=0.31	r=-0.01, p=0.98
	Episodic verbal memory (learning trials)	r=-0.24, p=0.14	r=0.02, p=0.93	r=-0.07, p=0.67	r=-0.29, p=0.08
	Episodic verbal memory (long term recall)	r=-0.07, p=0.68	r=0.02, p=0.89	r=0.01, p=0.96	r=-0.57, p=0.0002 (p=0.016) #
	MS (n=32)	T2 Lesion load	Hippocampal Volume	Hippocampal FA	Hippocampal MD
	Information processing speed	r=-0.51, p=0.004 (p=0.033) †	r=0.25, p=0.18	r=0.36, p=0.04 (n.s.) #	r=-0.52, p=0.002 (p=0.012) #
	Attention/Working memory	r=-0.16, p=0.38	r=0.17, p=0.35	r=0.16, p=0.40	r=-0.05, p=0.76
	Episodic verbal memory (learning trials)	r=-0.15, p=0.41	r=0.44, p=0.01 (p=0.032) #	r=0.19, p=0.31	r=-0.30, p=0.09
	Episodic verbal memory (long term recall)	r=-0.10, p=0.60	r=0.29, p=0.10	r=0.12, p=0.52	r=-0.12, p=0.52

. CIS = Clinically Isolated Syndrome; MS = Multiple Sclerosis. The threshold to dichotomize impaired/non impaired patients was set at z-score < -1.5 (z-scores were computed relative to appropriate control groups for CIS and MS, see method).

Table 3 : Correlations between MRI measures and neuropsychological

 3

z-scores. CIS = Clinically Isolated Syndrome; FA = Fractional Anisotropy; MD = Mean Diffusivity; MS = Multiple Sclerosis. #, adjusted on age, gender, depression and T2-lesion load; †, adjusted on age, gender and depression. To explore multiple leads, p values of univariate correlations were uncorrected for multiple comparisons in this table.

Acknowledgments

The authors thank Julie Charré-Morin and Aurore Saubusse (Bordeaux University Hospital) for neuropsychological testing.

0.011

Table 4: Clinical and MRI characteristics of memory-impaired vs memory-preserved patients with

CIS. CIS = Clinically Isolated Syndrome; FA = Fractional Anisotropy; MD = Mean Diffusivity.

Study funding

This study was supported by the ARSEP Fondation, Bordeaux University Hospital and TEVA and Merck-Sereno laboratories. The work was further supported by public grants from the French Agence Nationale de la Recherche within the context of the Investments for the Future program referenced ANR-10-LABX-57 named TRAIL (project IBIO-NI and HR-DTI) and ANR-10-LABX-43 named BRAIN (Project MEMO-MS). This study has also been carried out with financial support from the "Investments for the future" Programme IdEx Bordeaux -CPU (ANR-10-IDEX-03-02) and the CNRS multidisciplinary project "Défi ImagIn" HL-MRI. The sponsors did not participate in any aspect of the design or performance of the study, including data collection, management, analysis, and interpretation or the preparation, review, and approval of the manuscript.

Disclosures

VP received travel expenses from ARSEP Fondation, Biogen, Teva-Lundbeck and Merk-Serono. AR received research grants and/or consulting fees from Novartis, Biogen, Merck-Serono, Bayer Healthcare, Roche, Teva, and Genzyme unrelated to the submitted work. BB serves on scientific advisory boards for and has received honoraria or research support for its institution from Biogen-idec, Merck-Serono, Novartis, Genzyme, Teva, Roche, Medday and Bayer outside the submitted work.

CRGG is the recipient of a grant from Sanofi, and holds shares in Roche, Novartis, GSK, Alnylam, Protalix, Agenus, Arrowhead, and Cocrystal.