CREST Olga Klopp

Modal'x

Alexandre B Tsybakov

Oracle inequalities for network models and sparse graphon estimation

Inhomogeneous random graph models encompass many network models such as stochastic block models and latent position models. We consider the problem of statistical estimation of the matrix of connection probabilities based on the observations of the adjacency matrix of the network. Taking the stochastic block model as an approximation, we construct estimators of network connection probabilities -the ordinary block constant least squares estimator, and its restricted version. We show that they satisfy oracle inequalities with respect to the block constant oracle. As a consequence, we derive optimal rates of estimation of the probability matrix. Our results cover the important setting of sparse networks. Another consequence consists in establishing upper bounds on the minimax risks for graphon estimation in the L2 norm when the probability matrix is sampled according to a graphon model. These bounds include an additional term accounting for the "agnostic" error induced by the variability of the latent unobserved variables of the graphon model. In this setting, the optimal rates are influenced not only by the bias and variance components as in usual nonparametric problems but also include the third component, which is the agnostic error. The results shed light on the differences between estimation under the empirical loss (the probability matrix estimation) and under the integrated loss (the graphon estimation).

Introduction

Consider a network defined as an undirected graph with n nodes. Assume that we observe the values A ij ∈ {0, 1} where A ij = 1 is interpreted as the fact that the nodes i and j are connected and A ij = 0 otherwise. We set A ii = 0 for all 1 ≤ i ≤ n and we assume that A ij is a Bernoulli random variable with parameter (Θ 0 ) ij = P(A ij = 1) for 1 ≤ j < i ≤ n. The random variables A ij , 1 ≤ j < i ≤ n, are assumed independent. We denote by A the adjacency matrix i.e., the n × n symmetric matrix with entries A ij for 1 ≤ j < i ≤ n and zero diagonal entries. Similarly, we denote by Θ 0 the n × n symmetric matrix with entries (Θ 0 ) ij for 1 ≤ j < i ≤ n and zero diagonal entries. This is a matrix of probabilities associated to the graph; the nodes i and j are connected with probability (Θ 0 ) ij . The model with such observations A ′ = (A ij , 1 ≤ j < i ≤ n) is a special case of inhomogeneous random graph model that we will call for definiteness the network sequence model 1 , to emphasize a parallel with the gaussian sequence model.

Graphons and sparse graphon models

Networks arise in many areas such as information technology, social life, genetics. These real-life networks are in permanent movement and often their size is growing. Therefore, it is natural to look for a well-defined "limiting object" independent of the network size n and such that a stochastic network can be viewed as a partial observation of this limiting object. Such objects called the graphons play a central role in the recent theory of graph limits introduced by Lovász and Szegedy [START_REF] Lovasz | Limits of dense graph sequences[END_REF]. For a detailed description of this theory we Comment citer ce document : Klopp, O., Tsybakov, A. B., Verzelen, N. (2017). Oracle inequalities for network models and sparse graphon estimation. Annals of Statistics, 45 [START_REF] Aldous | Exchangeability and related topics[END_REF], 316-354. DOI : 10.1214/16-aos1454 refer to the monograph by Lovász [START_REF] Lovász | Large networks and graph limits[END_REF]. Graphons are symmetric measurable functions W : [0, 1] 2 → [0, 1]. In the sequel, the space of graphons is denoted by W. The main message is that every graph limit can be represented by a graphon. This beautiful theory of graph limits was developed for dense graphs, that is, graphs with the number of edges comparable to the square of the number of vertices.

Graphons give a natural way of generating random graphs [START_REF] Lovász | Large networks and graph limits[END_REF][START_REF] Diaconis | Graph limits and exchangeable random graphs[END_REF]. The probability that two distinct nodes i and j are connected in the graphon model is the random variable

(Θ 0 ) ij = W 0 (ξ i , ξ j ) (1)
where ξ 1 , . . . , ξ n are unobserved (latent) i.i.d. random variables uniformly distributed on [0, 1]. As above, the diagonal entries of Θ 0 are zero. Conditionally on ξ = (ξ 1 , . . . , ξ n ), the observations A ij for 1 ≤ j < i ≤ n are assumed to be independent Bernoulli random variables with success probabilities (Θ 0 ) ij . For any positive integer n, a graphon function W 0 defines a probability distribution on graphs of size n. Note that this model is different from the network sequence model since the observations A ij are no longer independent. If W 0 is a step-function with k steps, we obtain an analog of the stochastic block model with k groups. More generally, many exchangeable distributions on networks [START_REF] Diaconis | Graph limits and exchangeable random graphs[END_REF], including random dot product graphs [START_REF] Tang | Universally consistent vertex classification for latent positions graphs[END_REF] and some geometric random graphs [START_REF] Penrose | Random geometric graphs[END_REF] can be expressed as graphons.

Given an observed adjacency matrix A ′ sampled according to the model [START_REF] Aldous | Exchangeability and related topics[END_REF], the graphon function W 0 is not identifiable. The topology of a network is invariant with respect to any change of labelling of its nodes. Consequently, for any given function W 0 (•, •) and a measure-preserving bijection τ : [0, 1] → [0, 1] (with respect to the Lebesgue measure), the functions W 0 (x, y) and W τ 0 (x, y) := W 0 (τ (x), τ (y)) define the same probability distribution on random graphs. The equivalence classes of graphons defining the same probability distribution are characterized in a slightly more involved way based on the following result.

Proposition 1.1 [START_REF] Lovász | Large networks and graph limits[END_REF]Sect.10]). Two graphons U and W in W are called weakly isomorphic if there exist measure preserving maps φ, ψ: [0, 1] → [0, 1] such that U φ = W ψ almost everywhere. Two graphons U and W define the same probability distribution if and only if they are weakly isomorphic. This proposition motivates considering the equivalence classes of graphons that are weakly isomorphic. The corresponding quotient space is denoted by W.

It is easy to see that the expected number of edges in model ( 1) is a constant times the squared number of vertices, which corresponds to the dense case. Networks observed in the real life are often sparse in the sense that the number of edges is of the order o(n 2 ) as the number n of vertices tends to infinity. The situation in the sparse case is more complex than in the dense case. Even the almost dense case with n 2-o (1) edges is rather different from the dense case. The extremely sparse case corresponds to the bounded degree graph where all degrees are smaller than a fixed positive integer. It is an opposite extreme to the dense graph. Networks that occur in the applications are usually between these two extremes described by dense and bounded degree graphs. They often correspond to inhomogeneous networks with density of edges tending to 0 but with the maximum degree tending to infinity as n grows.

For a given ρ n > 0, one can modify the definition [START_REF] Aldous | Exchangeability and related topics[END_REF] to get a random graph model with O(ρ n n 2 ) edges. It is usually assumed that ρ n → 0 as n → ∞. The adjacency matrix A ′ is sampled according to graphon W 0 ∈ W with scaling parameter ρ n if for all j < i,

(Θ 0 ) ij = ρ n W 0 (ξ i , ξ j ) ( 2
)
where ρ n > 0 is the scale parameter that can be interpreted as the expected proportion of non-zero edges. Alternatively, model (2) can be considered as a graphon model (1) that has been sparsified in the sense that its edges have been independently removed with probability 1ρ n and kept with probability ρ n . This sparse graphon model was considered in [START_REF] Peter | A nonparametric view of network models and newman-girvan and other modularities[END_REF][START_REF] Peter | The method of moments and degree distributions for network models[END_REF][START_REF] Wolfe | Nonparametric graphon estimation[END_REF][START_REF] Xu | Edge label inference in generalized stochastic block models: from spectral theory to impossibility results[END_REF].

Our results

This paper has two contributions. First, we study optimal rates of estimation of the probability matrix Θ 0 under the Frobenius norm from an observation A ′ = (A ij , 1 ≤ j < i ≤ n) in the network sequence model. We estimate Θ 0 by a block-constant matrix and we focus on deriving oracle inequalities with optimal rates

Comment citer ce document : Klopp, O., Tsybakov, A. B., Verzelen, N. (2017). Oracle inequalities for network models and sparse graphon estimation. Annals of Statistics, 45 [START_REF] Aldous | Exchangeability and related topics[END_REF], 316-354. DOI : 10.1214/16-aos1454 (with possibly non-polynomial complexity of estimation methods). Note that estimating Θ 0 by a k × k block constant matrix is equivalent to fitting a stochastic block model with k classes. Estimation of Θ 0 has already been considered by [START_REF] Chatterjee | Matrix estimation by universal singular value thresholding[END_REF][START_REF] Xu | Edge label inference in generalized stochastic block models: from spectral theory to impossibility results[END_REF][START_REF] Chan | A consistent histogram estimator for exchangeable graph models[END_REF] but convergence rates obtained there are far from being optimal. More recently, Gao et al. [START_REF] Gao | Rate-optimal graphon estimation[END_REF] have established the minimax estimation rates for Θ 0 on classes of block constant matrices and on the smooth graphon classes. Their analysis is restricted to the dense case (1) corresponding to ρ n = 1 when dealing with model [START_REF] Peter | A nonparametric view of network models and newman-girvan and other modularities[END_REF]. In this paper, we explore the general setting of model [START_REF] Peter | A nonparametric view of network models and newman-girvan and other modularities[END_REF]. In particular, our aim is to understand the behavior of least squares estimators when the probabilities (Θ 0 ) ij can be arbitrarily small. This will be done via developing oracle inequalities with respect to the block constant oracle. Two estimators will be considered -the ordinary block constant least squares estimator, and its restricted version where the estimator is chosen in the ℓ ∞ cube of a given radius. As corollaries, we provide an extension for the sparse graphon model of some minimax results in [START_REF] Gao | Rate-optimal graphon estimation[END_REF] and we quantify the impact of the scaling parameter ρ n on the optimal rates of convergence.

Second, we consider estimation of the graphon function W 0 based on observation A ′ . In view of Proposition 1.1, graphons are not identifiable and can only be estimated up to weak isomorphisms. Hence, we study estimation of W 0 in the quotient space W of graphons. In order to contrast this problem with the estimation of Θ 0 , one can invoke an analogy with the random design nonparametric regression. Suppose that we observe (y i , ξ i ), i = 1, . . . , n, that are independently sampled according to the model y = f (ξ) + ǫ where f is an unknown regression function, ǫ is a zero mean random variable and ξ is distributed with some density h on [0, 1]. Given a sample of (y i , ξ i ), estimation of f with respect to the empirical loss is equivalent to estimation of the vector (f (ξ 1 ), . . . , f (ξ n )) in, for instance, the Euclidean norm. On the other hand, estimation under the integrated loss consists in constructing an estimator f such that the integral ( f (t)f (t)) 2 h(t)dt is small. Following this analogy, estimation of Θ 0 corresponds to an empirical loss problem whereas the graphon estimation corresponds to an integrated loss problem. However, as opposed to nonparametric regression, in the graphon models (1) and ( 2) the design ξ 1 , . . . , ξ n is not observed, which makes it quite challenging to derive the convergence rates in these settings.

In Section 3, we obtain L 2 norm non-asymptotic estimation rates for graphon estimation on classes of step functions (analogs of stochastic block models) and on classes of smooth graphons in model [START_REF] Peter | A nonparametric view of network models and newman-girvan and other modularities[END_REF]. This result improves upon previously known bounds by Wolfe and Olhede [START_REF] Wolfe | Nonparametric graphon estimation[END_REF]. For classes of step function graphons, we also provide a matching minimax lower bound allowing one to characterize the regimes such that graphon optimal estimation rates are slower than probability matrix estimation rates. In a work parallel to ours, Borgs et al. [START_REF] Borgs | Private graphon estimation for sparse graphs[END_REF] have analyzed the rates of convergence for estimation of step function graphons under the privacy model. Apart from the issues of privacy that we do not consider here, their results in our setting provide a weaker version of the upper bound in Corollary 3.3, with a suboptimal rate, which is the square root of the rate of Corollary 3.3 in the moderately sparse zone. We also mention the paper by Choi [START_REF] Choi | Co-clustering of nonsmooth graphons[END_REF] devoted to the convergence of empirical risk functions associated to the graphon model.

Notation

We provide a brief summary of the notation used throughout this paper.

• For a matrix B, we denote by B ij (or by B i,j , or by (B) ij ) its (i, j)th entry.

• For an integer m, set [m] = {1, . . . , m}.

• Let n, k and n 0 be integers such that 2 ≤ k ≤ n, n 0 ≤ n. We denote by Z n,k,n0 the set of all mappings z from [n] to [k] such that min a=1,...,k |z -1 (a)| ≥ n 0 (the minimal size of each "community" is n 0 ). For brevity, we set Z n,k = Z n,k,1 .

• We denote by R k×k sym the class of all symmetric k × k matrices with real-valued entries. • The inner product between matrices D, B ∈ R n×n will be denoted by D, B = i,j D ij B ij .

• Denote by B F and by B ∞ the Frobenius norm and the entry-wise supremum norm of matrix B ∈ R n×n respectively.

• We denote by ⌊x⌋ the maximal integer less than x ≥ 0 and by ⌈x⌉ the smallest integer greater than or equal to x.

Comment citer ce document : Klopp, O., Tsybakov, A. B., Verzelen, N. (2017). Oracle inequalities for network models and sparse graphon estimation. Annals of Statistics, 45 (1), 316-354. DOI : 10.1214/16-aos1454

• We denote by E the expectation with respect to the distribution of A if we consider the network sequence model and the expectation with respect to the joint distribution of (ξ, A) if we consider the graphon model.

• We denote by C positive constants that can vary from line to line. These are absolute constants unless otherwise mentioned.

• We denote by λ the Lebesgue measure on the interval [0, 1].

Probability matrix estimation

In this section, we deal with the network sequence model and we obtain optimal rates of estimation in the Frobenius norm of the probability matrix Θ 0 . Fixing some integer k > 0, we estimate the matrix Θ 0 by a block constant matrix with k × k blocks.

Least squares estimator

First, we study the least squares estimator Θ of Θ 0 in the collection of all k × k block constant matrices with block size larger than some given integer n 0 . Recall that we denote by Z n,k,n0 the set of all possible mappings z from

[n] to [k] such that min a=1,...,k |z -1 (a)| ≥ n 0 . For any z ∈ Z n,k,n0 , Q ∈ R k×k sym , we define the residual sum of squares L(Q, z) = (a,b)∈[k]×[k] (i,j)∈z -1 (a)×z -1 (b), j<i (A ij -Q ab ) 2
and consider the least squares estimator of (Q, z):

( Q, ẑ) ∈ arg min Q∈R k×k sym , z∈Z n,k,n 0 L(Q, z)
The block constant least squares estimator of (Θ 0 ) ij is defined as

Θ ij = Q ẑ(i)ẑ(j) for all i > j. Note that Θ ij ∈ [0, 1]
. Finally, we denote by Θ the symmetric matrix with entries Θ ij for all i > j and with zero diagonal entries. According to the stochastic block models terminology, Q stands for the estimated connection probabilities whereas ẑ is the estimated partition of the of nodes into k communities. The only difference between this estimator and the one considered in [START_REF] Gao | Rate-optimal graphon estimation[END_REF] is the restriction |z -1 (a)| ≥ n 0 . This prevents the partition z from being too unbalanced. A common choice of n 0 is of the order n/k, which is referred to as balanced partition. Taking larger n 0 when we have additional information allows us to obtain simpler estimators since we reduce the number of configurations.

Restricted least squares estimator

Given r ∈ (0, 1], consider the least squares estimator restricted to the l ∞ ball of radius r, ( Qr , ẑr ) ∈ arg min

Q∈R k×k sym : Q ∞ ≤r, z∈Z n,k L(Q, z).
The estimator Θ r of matrix Θ 0 is defined as the symmetric matrix with entries Θ r ij = ( Q r ) ẑr (i)ẑr (j) for all i > j, and with zero diagonal entries. Note that here we consider any partitions, including really unbalanced ones (n 0 = 1).

Oracle inequalities

Let Θ * ,n0 be the best Frobenius norm approximation of Θ 0 in the collection of matrices

T n0 [k] = {Θ : ∃ z ∈ Z n,k,n0 , Q ∈ R k×k sym such that Θ ij = Q z(i)z(j)
, i = j, and Θ ii = 0 ∀i}. In particular, T 1 [k] is the set of all probability matrices corresponding to k-class stochastic block models without group size restriction. For brevity, we write

T 1 [k] = T [k],
≥ 2, E 1 n 2 Θ -Θ 0 2 F ≤ C 1 n 2 Θ 0 -Θ * ,n0 2
F + C 2 Θ 0 ∞ log(k) n + k 2 n 2 + C 3 log(n/n 0 ) n 0 log(k) n + k 2 n 2 . (3)
To discuss some consequences of this oracle inequality, we consider the case of balanced partitions.

Corollary 2.2. Consider the network sequence model. Let n 0 ≥ Cn/k for some C > 0 (balanced partition), n 0 ≥ 2, and Θ 0 ∞ ≥ k log(k) n . Then, there exist positive absolute constants C 1 , C 2 , such that

E 1 n 2 Θ -Θ 0 2 F ≤ C 1 n 2 Θ 0 -Θ * ,n0 2
F + C 2 Θ 0 ∞ log(k) n + k 2 n 2 . (4)
In particular, if Θ 0 ∈ T n0 [k] (i.e., when we have a k-class stochastic block model with balanced communities), the rate of convergence is of the order

Θ 0 ∞ log(k) n + k 2 n 2 .
In [START_REF] Gao | Rate-optimal graphon estimation[END_REF], the rate log(k)

n + k 2 n 2
is shown to be minimax over all stochastic block models with k blocks, with no restriction on Θ 0 ∞ except the obvious one, Θ 0 ∞ ≤ 1. We prove in the next subsection that the rate

Θ 0 ∞ log(k) n + k 2 n 2
obtained in Corollary 2.2 exhibits the optimal dependency on Θ 0 ∞ . Before doing this, we provide an oracle inequality for the restricted least squares estimator Θ r .

Proposition 2.3. Consider the network sequence model. There exist positive absolute constants C 1 and C 2 such that the following holds.

If Θ 0 ∞ ≤ r, then E 1 n 2 Θ r -Θ 0 2 F ≤ C 1 n 2 Θ 0 -Θ * 2 F + C 2 r log(k) n + k 2 n 2 . (5)
As opposed to Corollary 2.2, the risk bound ( 5) is applicable for unbalanced partitions and for arbitrarily small values of Θ 0 ∞ . However, this restricted least squares estimator requires the knowledge of an upper bound of Θ 0 ∞ . Whereas the mean value of (Θ 0 ) ij is easily inferred from the data, the maximal value Θ 0 ∞ is difficult to estimate. If the matrix Θ 0 satisfies the sparse graphon model [START_REF] Peter | A nonparametric view of network models and newman-girvan and other modularities[END_REF], one can set r = r n = u n A where A = 2 j<i A i,j /(n(n -1)) is the edge density of the graph and u n is any sequence that tends to infinity (for example, u n = log log n). For n large enough, A/ρ n is close to [0,1] 2 W 0 (x, y)dxdy in the sparse graphon model [START_REF] Peter | A nonparametric view of network models and newman-girvan and other modularities[END_REF] with probability close to one, and therefore r n is greater than Θ 0 ∞ . The price to pay for this data-driven choice of r n is that the rate in the risk bound [START_REF] Chan | A consistent histogram estimator for exchangeable graph models[END_REF] is multiplied by u n .

Stochastic block models

Given an integer k and any ρ n ∈ (0, 1], consider the set of all probability matrices corresponding to k-class stochastic block model with connection probability uniformly smaller than ρ n :

T [k, ρ n ] = {Θ 0 ∈ T [k] : Θ 0 ∞ ≤ ρ n } . (6)
Gao et al. [START_REF] Gao | Rate-optimal graphon estimation[END_REF] have proved that the minimax estimation rate over

T [k, 1] is of order the k 2 n 2 + log(k) n .
The following proposition extends their lower bound to arbitrarily small ρ n > 0.

< ρ n ≤ 1, inf T sup Θ0∈T [k,ρn] E Θ 0 1 n 2 T -Θ 0 2 F ≥ C min ρ n log(k) n + k 2 n 2 , ρ 2 n ( 7
)
where E Θ 0 denotes the expectation with respect to the distribution of A when the underlying probability matrix is Θ 0 and inf T is the infimum over all estimators.

If ρ n ≥ log(k) n + k 2 n 2 , the minimax rate of estimation is of the order ρ n log(k) n + k 2 n 2 .
This rate is achieved by the restricted least squares estimator with r ≍ ρ n and by the least squares estimator if the partition is balanced and ρ n ≥ k log(k)/n. For really sparse graphs (ρ n smaller than log(k) n + k 2 n 2 ), the estimation problem becomes rather trivial since both the null estimator T = 0 and the constant least squares estimator Θ with all entries Θ ij = A achieve the optimal rate ρ 2 n .

Comment citer ce document : Klopp, O., Tsybakov, A. B., Verzelen, N. (2017). Oracle inequalities for network models and sparse graphon estimation. Annals of Statistics, 45 (1), 316-354. DOI : 10.1214/16-aos1454

Smooth graphons

We now use Propositions 2.1 and 2.3 to obtain rates of convergence for the probability matrix estimation when Θ 0 satisfies the sparse graphon model (2) and the graphon W 0 ∈ W is smooth. For any α > 0, L > 0, define the class of α-Hölder continuous functions Σ(α, L) as the set of all functions W :

[0, 1] 2 → [0, 1] such that |W (x ′ , y ′ ) -P ⌊α⌋ ((x, y), (x ′ -x, y ′ -y))| ≤ L(|x ′ -x| α-⌊α⌋ + |y ′ -y| α-⌊α⌋ )
for all (x ′ , y ′ ), (x, y) ∈ [0, 1] 2 , where ⌊α⌋ is the maximal integer less than α, and the function (x ′ , y ′ ) → P ⌊α⌋ ((x, y), (x ′x, y ′y)) is the Taylor polynomial of degree ⌊α⌋ at point (x, y). It follows from the standard embedding theorems that, for any W ∈ Σ(α, L) and any (x ′ , y ′ ), (x, y)

∈ [0, 1] 2 , |W (x ′ , y ′ ) -W (x, y)| ≤ M (|x ′ -x| α∧1 + |y ′ -y| α∧1 ) ( 8
)
where M is a constant depending only on α and L. In the following, we will use only this last property of W ∈ Σ(α, L).

The following two propositions give bounds on the bias terms

Θ 0 -Θ * ,n0 2
F and Θ 0 -Θ * 2 F .
Proposition 2.5. Consider the graphon model (2) with W 0 ∈ Σ(α, L) where α, L > 0. Let n 0 ≥ 2 and k = ⌊n/n 0 ⌋. Then,

E 1 n 2 Θ 0 -Θ * ,n0 2 F ≤ CM 2 ρ 2 n 1 k 2 α∧1 . (9)
We will also need the following proposition proved in [START_REF] Gao | Rate-optimal graphon estimation[END_REF], Lemma 2.1.

Proposition 2.6. Consider the graphon model (2) with W 0 ∈ Σ(α, L) where α, L > 0. Then, almost surely,

1 n 2 Θ 0 -Θ * 2 F ≤ CM 2 ρ 2 n 1 k 2 α∧1 . (10)
Corollary 2.7. Consider the graphon model (2) with W 0 ∈ Σ(α, L) where α, L > 0 and 0 1+α∧1) and there exists n 0 ≥ 2 such that k = ⌊n/n 0 ⌋. Then there exists a positive constant C depending only on L and α such that the least squares estimator Θ constructed with this choice of n 0 satisfies

< ρ n ≤ 1. Set k = ρ 1/2 n n 1 1+α∧1 . (i) Assume that ρ n ≥ n -2(α∧1) 1+2(α∧1) (log n) 2 (
E 1 n 2 Θ -Θ 0 2 F ≤ C ρ 2+α∧1 1+α∧1 n n -2(α∧1) 1+α∧1 + ρ n log n n . ( 11
) (ii) Assume that r ≥ ρ n ≥ Cn -2 .
Then there exists a positive constant C depending only on L and α such that the restricted least squares estimator

Θ r satisfies E 1 n 2 Θ r -Θ 0 2 F ≤ C r 2+α∧1 1+α∧1 n -2(α∧1) 1+α∧1 + r log n n . ( 12
)
Corollary 2.7 extends the results obtained in Gao et al. [START_REF] Gao | Rate-optimal graphon estimation[END_REF] to arbitrary ρ n ∈ (0, 1]. To simplify the discussion assume that α ≤ 1. There are two ingredients in the rates of convergence in Corollary 2.7, the nonparametric rate ρ . The smoothness index α has an impact on the rate only if α ∈ (0, 1) and only if the network is not too sparse, that is if

ρ n ≥ Cn α-1 (log n) 1+α .
In [START_REF] Gao | Rate-optimal graphon estimation[END_REF], Gao et al. prove a lower bound showing that the rate n -2(α∧1) 1+α∧1 + log(n) n is optimal if ρ n = 1. Following the same lines as in Proposition 2.4, one can readily extend their result to prove that the rate in [START_REF] Lovasz | Limits of dense graph sequences[END_REF] is minimax optimal for ρ n ≥ n -2+ǫ with an arbitrarily small ǫ > 0.

Comment citer ce document : Klopp, O., Tsybakov, A. B., Verzelen, N. (2017). Oracle inequalities for network models and sparse graphon estimation. Annals of Statistics, 45 (1), 316-354. DOI : 10.1214/16-aos1454

Graphon estimation problem

In this section, our purpose is to estimate the graphon function W 0 (•, •) in the sparse graphon model (2).

From probability matrix estimation to graphon estimation

We start by associating a graphon to any n × n probability matrix Θ. This provides a way of deriving an estimator of

f 0 (•, •) = ρ n W 0 (•, •) from an estimator of Θ 0 .
Given a n × n matrix Θ with entries in [0, 1], define the empirical graphon f Θ as the following piecewise constant function:

f Θ (x, y) = Θ ⌈nx⌉,⌈ny⌉ (13)
for all x and y in (0, 1]. The empirical graphons associated to the least squares estimator and to the restricted least squares estimator with threshold r will be denoted by f and f r respectively:

f = f Θ , f r = f Θ r .
They will be used as graphon estimators. For any estimator f of f 0 = ρ n W 0 , define the squared error

δ 2 ( f , f 0 ) := inf τ ∈M (0,1) 2 |f 0 (τ (x), τ (y)) -f (x, y)| 2 dxdy ( 14
)
where M is the set of all measure-preserving bijections τ : [0, 1] → [0, 1]. It has been proved in [START_REF] Lovász | Large networks and graph limits[END_REF]Ch.8,[START_REF] Penrose | Random geometric graphs[END_REF] that δ(•, •) defines a metric on the quotient space W of graphons.

The following lemma is a simple consequence of the triangle inequality.

Lemma 3.1. Consider the graphon model [START_REF] Peter | A nonparametric view of network models and newman-girvan and other modularities[END_REF]. For any W 0 ∈ W, ρ n > 0, and any estimator T of Θ 0 such that T is an n × n matrix with entries in [0, 1], we have

E δ 2 ( f T , f 0 ) ≤ 2 E 1 n 2 T -Θ 0 2 F + 2 E δ 2 f Θ 0 , f 0 . ( 15
)
The bound on the integrated risk in ( 15) is a sum of two terms. The first term containing T -Θ 0 2 F has been considered in Section 2 for T = Θ and T = Θ r . It is the estimation error term. The second term containing δ 2 ( f Θ0 , f 0 ) measures the distance between the true graphon f 0 and its discretized version sampled at the unobserved random design points ξ 1 , . . . , ξ n . We call it the agnostic error. The behavior of δ 2 ( f Θ 0 , f 0 ) depends on the topology of the considered graphons as shown below for two examples, namely, the step function graphons and the smooth graphons.

Step function graphons

Define W[k] the collection of k-step graphons, that is the subset of graphons W ∈ W such that for some

Q ∈ R k×k sym and some φ : [0, 1] → [k], W (x, y) = Q φ(x),φ(y) for all x, y ∈ [0, 1] . ( 16
) A step function W ∈ W[k] is called balanced if λ φ -1 (1) = . . . = λ φ -1 (k) = 1/k where λ is the Lebesgue measure on [0, 1]
. The agnostic error associated to step function graphons is evaluated as follows.

Proposition 3.2. Consider the graphon model [START_REF] Peter | A nonparametric view of network models and newman-girvan and other modularities[END_REF]. For all integers k ≤ n, W 0 ∈ W[k] and ρ n > 0 we have

E δ 2 f Θ 0 , f 0 ≤ Cρ 2 n k n .
Combining this result with Lemma 3.1 and Propositions 2.1 and 2.3 we obtain the following risk bounds for the least squares and restricted least squares graphon estimators.

(i) If ρ n ≥ k log(k) n
, n 0 = ⌊n/2k⌋, and the step function W 0 is balanced, then the least squares graphon estimator f constructed with this choice of n 0 satisfies

E δ 2 f , f 0 ≤ C 1 ρ n k 2 n 2 + log(k) n + ρ 2 n k n .
(ii) If ρ n ≤ r, the restricted least squares graphon estimator f r satisfies

E δ 2 f r , f 0 ≤ C 2 r k 2 n 2 + log(k) n + ρ 2 n k n . ( 17
)
As an immediate consequence of this corollary, we get the following upper bound on the minimax risk:

inf f sup W0∈W[k] E W0 δ 2 f , f 0 ≤ C 3 ρ n k 2 n 2 + log(k) n + ρ 2 n k n ∧ ρ 2 n ( 18
)
where C 3 is an absolute constant. Here, E W0 denotes the expectation with respect to the distribution of observations A ′ = (A ij , 1 ≤ j < i ≤ n) when the underlying sparse graphon is ρ n W 0 and inf f is the infimum over all estimators. The bound (18) follows from ( 17) with r = ρ n and the fact that the risk of the null estimator f ≡ 0 is smaller than ρ 2 n . The next proposition shows that the upper bound ( 18) is optimal in a minimax sense (up to a logarithmic factor in k in one of the regimes). Proposition 3.4. There exists a universal constant C > 0 such that for any sequence ρ n > 0 and any positive integer

2 ≤ k ≤ n, inf f sup W0∈W[k] E W0 δ 2 f , f 0 ≥ C ρ n k 2 n 2 + 1 n + ρ 2 n k -1 n ∧ ρ 2 n , ( 19
)
where E W0 denotes the expectation with respect to the distribution of observations

A ′ = (A ij , 1 ≤ j < i ≤ n)
when the underlying sparse graphon is ρ n W 0 and inf f is the infimum over all estimators.

The proof is given in Section 4.9. Showing the rate ρ 2 n (k -1)/n relies on two arguments. First, we construct a family of graphons that are well separated with respect to the δ(•, •) distance. The difficulty comes from the fact that this is not a classical L 2 distance but a minimum of the L 2 distance over all measure-preserving transformations. Second, we show that the behavior of the Kullback-Leibler divergences between the graphons in this family is driven by the randomness of the latent variables ξ 1 , . . . , ξ n while the nature of the connection probabilities can be neglected. This argument is similar to the "data processing" inequality. Proposition 3.4 does not cover the case k = 1 (Erdős-Rényi models). In fact, in this case the constant graphon estimator f = f A achieves the optimal rate, which is equal to ρ n /n 2 . The suboptimality of the bound of Proposition 3.2 for k = 1 is due to the fact that the diagonal blocks of f and f r are all equal to zero. By carefully defining the diagonal blocks of these estimators, we could have achieved the optimal bound ρ 2 n (k -1)/n but this would need a modification of the notation and of the proofs. The bounds (18) and (19) imply that there are three regimes depending on the sparsity parameter ρ n :

(i) Weakly sparse graphs: (iii) Highly sparse graphs:

ρ n ≥ log(k) √ kn ∨ ( k n ) 3/2 .
(k) n ∨ k n 2 ≤ ρ n ≤ log(k) √ kn ∨ k n 3/2 .
ρ n ≤ log(k) n ∨ k n 2 .
The minimax risk is of the order ρ 2 n , and it is attained by the null estimator.

In a work parallel to ours, Borgs et al. [START_REF] Borgs | Private graphon estimation for sparse graphs[END_REF] provide an upper bound for the risk of step function graphon estimators in the context of privacy. If the partitions are balanced, Borgs et al. [START_REF] Borgs | Private graphon estimation for sparse graphs[END_REF] obtain the bound on the agnostic error as in Proposition 3.2. When there is no privacy issues, comparing the upper bound of [START_REF] Borgs | Private graphon estimation for sparse graphs[END_REF] with that of Corollary 3.3, we see that it has a suboptimal rate, which is the square root of the rate of Corollary 3.3 in the moderately sparse zone. Note also that the setting in [START_REF] Borgs | Private graphon estimation for sparse graphs[END_REF] is restricted to balanced partitions while we consider more general partitions.

Smooth graphons

We now derive bounds on the mean squared error of smooth graphon estimation. The analysis will be based on the results of Section 2 and on the following bound for the agnostic error associated to smooth graphons. Proposition 3.5. Consider the graphon model (2) with W 0 ∈ Σ(α, L) where α, L > 0 and ρ n > 0. Then

E δ 2 ( f Θ 0 , f 0 ) ≤ C ρ 2 n n α∧1 (20)
where the constant C depends only on L and α.

Combining Proposition 3.5 with Lemma 3.1 and with Propositions 2.1 and 2.3 we obtain the following risk bounds for the least squares and restricted least squares graphon estimators. 1+α∧1) , and there exists n 0 ≥ 2 such that k = ⌊n/n 0 ⌋. Then, there exists a positive constant C 1 depending only on L and α such that the least squares graphon estimator f constructed with this choice of n 0 satisfies

< ρ n ≤ 1. Fix k = ρ 1/2 n n 1 1+α∧1 . (i) Assume that ρ n ≥ n -2(α∧1) 1+2(α∧1) (log n) 2(
E δ 2 f , f 0 ≤ C 1 ρ 2+α∧1 1+α∧1 n n -2(α∧1) 1+α∧1 + ρ n log n n + ρ 2 n n α∧1 . ( 21
) (ii) Assume that r ≥ ρ n ≥ Cn -2 .
Then, there exists a positive constant C 2 depending only on L and α such that the restricted least squares graphon estimator f r satisfies

E δ 2 f r , f 0 ≤ C 2 r 2+α∧1 1+α∧1 n -2(α∧1) 1+α∧1 + r log n n + ρ 2 n n α∧1 . ( 22
)
For the purpose of the discussion, assume that r ≍ ρ n . If ρ n ≤ n α-1 log(n), the rate of convergence is of the order ρ n log(n)/n, the same as that of the probability matrix estimation risk E Θ r -Θ 0 2 F /n 2 , cf. Corollary 2.7. Observe that the above condition is always satisfied when α ≥ 1. If ρ n ≥ n α-1 log(n), the rate of convergence in (22) for α ≤ 1 is of the order ρ 2 n /n α due to the agnostic error. This is slower than the optimal nonparametric rate ρ 2+α 1+α n n -2α 1+α for probability matrix estimation. We conjecture that this loss is unavoidable when considering graphon estimation with the δ 2 (•, •) error measure. We also note that the rates in (22) are faster than those obtained by Wolfe and Olhede [START_REF] Wolfe | Nonparametric graphon estimation[END_REF] for the maximum likelihood estimator. In some cases, the improvement in the rate is up to n -α/2 .

Comment

Proofs

In this section, we will repeatedly use Bernstein's inequality that we state here for reader's convenience: Let X 1 , . . . , X N be independent zero-mean random variables. Suppose that |X i | ≤ M almost surely, for all i. Then, for any t > 0,

P    N i=1 X i ≥ 2t N i=1 E(X 2 i ) + 2M 3 t    ≤ e -t . (23)
In the proofs of the upper bounds, to shorten the notation, we assume that instead of the n(n -1)/2 observations A ′ we have the symmetrized observation matrix A, and thus

L(Q, z) = 1 2 (a,b)∈[k]×[k] (i,j)∈z -1 (a)×z -1 (b), j =i (A ij -Q ab ) 2 .
This does not change the estimators nor the results. The changes are only in the values of constants that do not explicitly appear in the risk bounds.

Proof of Proposition 2.1

Since Θ is a least squares estimator, we have

Θ -Θ 0 2 F ≤ Θ 0 -Θ * 2 F + 2 Θ -Θ 0 , E + 2 Θ 0 -Θ * , E (24)
where E = A -Θ 0 is the noise matrix. The last summand on the right hand side of (24) has mean zero. So, to prove the proposition it suffices to bound the expectation of Θ -Θ 0 , E . For any z ∈ Z n,k,n0 , denote by Θ z the best Frobenius norm approximation of Θ 0 in the collection of matrices

T z := {Θ : ∃Q ∈ R k×k sym such that Θ ij = Q z(i)z(j)
, i = j, and Θ ii = 0 ∀i}.

We have the following decomposition:

Θ -Θ 0 , E = Θ ẑ -Θ 0 , E + Θ -Θ ẑ , E = (I) + (II) .
In this decomposition, (I) is the error due to misclustering and (II) is the error due to the Bernoulli noise.

We bound each of these errors separately. Control of (I). We apply Bernstein's inequality (23) together with the union bound over all z ∈ Z n,k,n0 and we

use that Θ z -Θ 0 , E = 2 1≤j<i≤n Θ z -Θ 0 ij E ij . Since the variance of E ij satisfies Var(E ij ) ≤ Θ 0 ∞ while E ij ∈ [-1, 1]
, and the cardinality of Z n,k,n0 satisfies |Z n,k,n0 | ≤ k n , we obtain

P Θ ẑ -Θ 0 , E ≥ 2 Θ ẑ -Θ 0 F Θ 0 ∞ (n log(k) + t) + 4 3 Θ ẑ -Θ 0 ∞ (n log(k) + t) ≤ e -t ,
for all t > 0. Since the entries of Θ ẑ are equal to averaged entries of Θ 0 over blocks, we obtain that

Θ ẑ -Θ 0 ∞ ≤ Θ 0 ∞ . Using this observation, decoupling the term 2 Θ ẑ -Θ 0 F Θ 0 ∞ (n log(k) + t)
via the elementary inequality 2uv ≤ u 2 + v 2 and then integrating with respect to t we obtain

E Θ ẑ -Θ 0 , E - 1 8 Θ ẑ -Θ 0 2 F ≤ C Θ 0 ∞ n log(k) . ( 25
)
Control of (II). The control of the error due to the Bernoulli noise is more involved. We first consider the intersection of T z with the unit ball in the Frobenius norm and construct a 1/4-net on this set. Then, using the union bound and Bernstein's inequality, we can write a convenient bound on Θ, E for any Θ from this net. Finally we control (II) using a bound on Θ, E on the net and a bound on the supremum norm A ẑ -Θ ẑ ∞ . We control the supremum norm A ẑ -Θ ẑ ∞ using the definition of ẑ and Bernstein's inequality.

Comment citer ce document : Klopp, O., Tsybakov, A. B., Verzelen, N. (2017). Oracle inequalities for network models and sparse graphon estimation. Annals of Statistics, 45 (1), 316-354. DOI : 10.1214/16-aos1454

For any z ∈ Z n,k,n0 , define the set T z,1 = {Θ ∈ T z : Θ F ≤ 1} and denote by A z the best Frobenius norm approximation of A in T z . Then,

E z = A z -Θ z is the projection of E onto T z . Notice that Az -Θz Az-Θz F = Ez Ez F maximizes Θ ′ , E over all Θ ′ ∈ T z,1 .
Denote by C z the minimal 1/4-net on T z,1 in the Frobenius norm. To each V ∈ C z , we associate V ∈ arg min

Θ ′ ∈Tz,1 ∩ B • F (V ,1/4) Θ ′ ∞ ,
which is a matrix minimizing the entry-wise supremum norm over the Frobenius ball B • F (V , 1/4) of radius 1/4 centered at V . Finally, define

C z := { V : V ∈ C z }.
A standard bound for covering numbers implies that log | C z | ≤ Ck 2 , where |S| denotes the cardinality of set S. By Bernstein's inequality combined with the union bound, we find that with probability greater than 1e -t ,

Θ, E ≤ 2 Θ 0 ∞ (n log(k) + k 2 + t) + 4 3 Θ ∞ (n log(k) + k 2 + t)
simultaneously for all Θ ∈ Cz with any z ∈ Z n,k,n0 . Here, we have used that Θ F ≤ 1 for all Θ ∈ Cz . Assume w.l.o.g. that A ẑ -Θ ẑ = 0. By the definition of Cz , there exists Θ ∈ C ẑ , such that

Θ -A ẑ -Θ ẑ A ẑ -Θ ẑ F F ≤ 1 2 and Θ ∞ ≤ A ẑ -Θ ẑ ∞ A ẑ -Θ ẑ F .
Note that for this Θ, the matrix 2

Θ -A ẑ -Θ ẑ A ẑ -Θ ẑ F belongs to T z,1 . Thus, A ẑ -Θ ẑ A ẑ -Θ ẑ F , E ≤ Θ, E + 1 2 max Θ ′ ∈T ẑ,1 Θ ′ , E = Θ, E + 1 2 A ẑ -Θ ẑ A ẑ -Θ ẑ F , E since A ẑ -Θ ẑ A ẑ -Θ ẑ F maximizes Θ ′ , E over all Θ ′ ∈ T ẑ,1 .
Using the last two displays we obtain that

A ẑ -Θ ẑ , E ≤ 4 A ẑ -Θ ẑ F Θ 0 ∞ (n log(k) + k 2 + t) + 8 3 A ẑ -Θ ẑ ∞ (n log(k) + k 2 + t) (26)
with probability greater than 1e -t .

Next, we are looking for a bound on

A ẑ -Θ ẑ ∞ . Since A ẑ -Θ ẑ = E ẑ we have A ẑ -Θ ẑ ij = l ′ =l: ẑ(l ′ )=ẑ(i),ẑ(l)=ẑ(j) E l ′ l |(l ′ , l) : l ′ = l, ẑ(l ′ ) = ẑ(i), ẑ(l) = ẑ(j)|
for all i = j. Consequently, we have A ẑ -Θ ẑ ∞ ≤ sup m=n0,...,n sup s=n0,...,n X ms where

X ms := sup V1:|V1|=m sup V2:|V2|=s (i,j)∈V1×V2: i =j E ij ms -|V 1 ∩ V 2 | . Since n 0 ≥ 2, we have ms -|V 1 ∩ V 2 | ≥ ms -m ∧ s ≥ ms/2 for all m, s ≥ n 0 . Furthermore |{V 1 : |V 1 | = m}| ≤ n m ≤ (en/m) m .
Therefore, Bernstein's inequality combined with the union bound over V 1 , V 2 leads to

P X ms ≤ C Θ 0 ∞ m log(en/m) + s log(en/s) + t ms + m log(en/m) + s log(en/s) + t ms ≥ 1 -2e -t
for any t > 0. From a union bound over all integers m, s ∈ [n 0 , n], we conclude that

P A ẑ -Θ ẑ ∞ ≤ C Θ 0 ∞ + log(n/n 0 ) + t n 0 ≥ 1 -2e -t . ( 27
A ẑ -Θ ẑ , E ≤ A ẑ -Θ ẑ 2 F 16 + C Θ 0 ∞ (n log(k) + k 2 + t) + log(n/n 0 )(n log(k) + k 2 ) + t(n log(k) + k 2 + t) n 0
with probability greater than 1 -3e -t . Integrating with respect to t leads to

E A ẑ -Θ ẑ , E - A ẑ -Θ ẑ 2 F 16 ≤ C Θ 0 ∞ (n log(k) + k 2 ) + log(n/n 0 )(n log(k) + k 2 ) n 0 . (28)
Now, note that Θ = A ẑ , and hence

Θ ẑ -Θ 0 F ≤ Θ -Θ 0 F by definition of Θ ẑ . Thus, A ẑ -Θ ẑ F = Θ -Θ ẑ F ≤ 2 Θ -Θ 0 F
. These remarks, together with ( 25) and (28), imply

E Θ -Θ 0 , E ≤ 3 8 E Θ -Θ 0 2 F + C Θ 0 ∞ (n log(k) + k 2 ) + log(n/n 0 )(n log(k) + k 2 ) n 0 .
The result of the proposition now follows from the last inequality and (24).

Proof of Proposition 2.3

We first follow the lines of the proof of Proposition 2.1. As there, we have

Θ r -Θ 0 2 F ≤ Θ 0 -Θ * 2 F + 2 Θ ẑr -Θ 0 , E + 2 Θ r -Θ ẑr , E + 2 Θ 0 -Θ * , E .
Here, E Θ 0 -Θ * , E = 0, and analogously to (25),

E Θ ẑr -Θ 0 , E - 1 8 Θ ẑr -Θ 0 2 F ≤ C Θ 0 ∞ n log(k). (29)
It remains to obtain a bound on the expectation of Θ r -Θ ẑr , E , which corresponds to the term (II) in the proof of Proposition 2.1 (the error due to the Bernoulli noise). To do this, we consider the subset A of matrices in T ẑr such that their supremum norm is bounded by 2r and Frobenius norm is bounded by Θ r -Θ ẑr F . As Θ r -Θ ẑr belongs to this set it is enough to obtain a bound on the supremum of Θ, E for Θ ∈ A. To control this supremum, we construct a finite subset C * z that approximates well the set A both in the Frobenius norm and in the supremum norm.

Consider the set

A = {Θ ∈ T ẑr : Θ ∞ ≤ 2r, Θ F ≤ Θ r -Θ ẑr F }. Then, Θ r -Θ ẑr , E ≤ max Θ∈A Θ, E := T , E F ( 30
)
where T is a matrix in A that achieves the maximum. If T F < 2 r we have a trivial bound T , E F ≤ 2rn since all components of E belong to [-1, 1]. Thus, it suffices to consider the case T F ≥ 2r. In order to bound T , E F in this case, we construct a finite subset of T ẑr that approximates well T both in the Frobenius norm and in the supremum norm.

For each z ∈ Z n,k , let C z be a minimal 1/4-net of T z,1 in the Frobenius norm. Set ǫ 0 = r and ǫ q = 2 q ǫ 0 for any integer q = 1, . . . , q max , where q max is the smallest integer such that 2rn ≤ ǫ qmax . Cearly, q max ≤ C log(n). For any V ∈ C z , any q = 0, . . . , q max , and any matrix U ∈ {-1, 0, 1} k×k , define a matrix V q,U ,z ∈ R n×n with elements V q,U ,z ij such that V q,U ,z ii = 0 for all i ∈ [n], and for all i = j,

V q,U ,z ij = sign(V ij ) (|ǫ q V ij | ∧ (2r)) (1 -|U z(i)z(j) |) + rU z(i)z(j) . (31)
Finally, denote by C * z the set of all such matrices: C * z := {V q,U ,z : V ∈ C z , q = 0, . . . , q max , U ∈ {-1, 0, 1} k×k }.

Comment citer ce document : Klopp, O., Tsybakov, A. B., Verzelen, N. (2017). Oracle inequalities for network models and sparse graphon estimation. Annals of Statistics, 45 (1), 316-354. DOI : 10.1214/16-aos1454

For any z ∈ Z n,k we have log

|C * z | ≤ C(k 2 + log log(n)) while log |Z n,k | ≤ n log(k). Also, the variance of E ij satisfies Var(E ij ) ≤ Θ 0 ∞ ≤ r, and E ij ∈ [-1, 1]
. Thus, from Bernstein's inequality combined with the union bound we obtain that, with probability greater than 1e -t ,

V , E ≤ 2 V F r(k 2 + n log(k) + t) + 4 3 r(k 2 + n log(k) + t)
simultaneously for all matrices V ∈ C * z and all z ∈ Z n,k . Here, we have used that V ∞ ≤ 2r for all V ∈ C * z , cf. (31). It follows that, with probability greater than 1e -t ,

V , E - 1 50 V 2 F ≤ Cr(k 2 + n log(k) + t) (32)
simultaneously for all matrices V ∈ C * z and all z ∈ Z n,k . We now use the following lemma proved in Subsection 4.10.

Lemma 4.1. If T F ≥ 2r there exists a matrix V in C * ẑr , such that

• T -V F ≤ T F /4, • T -V ∞ ≤ r.
Thus, on the event T F ≥ r, as a consequence of Lemma 4.1 we obtain that 2( T -V ) ∈ A. This and the definition of T imply T -V , E ≤ T , E F /2, so that T , E F ≤ 2 V , E , and thus

Θ r -Θ ẑr , E /2 ≤ V , E . Furthermore, by Lemma 4.1 V F ≤ 5 T F /4 ≤ 5 Θ r -Θ ẑr /4.
These remarks (recall that they hold on the event T F ≥ r), and (32) yield

P Θ r -Θ ẑr , E - Θ r -Θ ẑr 2 F 16 1 { T F ≥r} ≥ Cr(k 2 + n log(k) + t) ≤ e -t
for all t > 0. Integrating with respect to t and using that Θ r -Θ ẑr , E ≤ rn for T F < r we obtain

E Θ 0 Θ r -Θ ẑr , E - Θ r -Θ ẑr 2 F 16 ≤ Cr(n log(k) + k 2 ).
In view of this inequality and (29) the proof is now finished by the same argument as in Proposition 2.1.

Proof of Proposition 2.4

The proof follows the lines of Theorem 2.2 in [START_REF] Gao | Rate-optimal graphon estimation[END_REF]. So, for brevity, we only outline the differences from that proof. The remaining details can be found in [START_REF] Gao | Rate-optimal graphon estimation[END_REF]. First, note that to prove the theorem it suffices to obtain separately the lower bounds of the order ρ n (k/n) 2 ∧ ρ 2 n and of the order ρ n log(k)/n ∧ ρ 2 n . Next, note that the Kullback-Leibler divergence K(ρ n p, ρ n q) between two Bernoulli distributions with parameters ρ n p and ρ n q such that 1/4 < p, q < 3/4 satisfies

K(ρ n p, ρ n q) = ρ n q log q p + (1 -ρ n q) log 1 -ρ n q 1 -ρ n p (33) ≤ ρ n q(q -p) p + ρ n 1 -ρ n q 1 -ρ n p (p -q) = ρ n (q -p) 2 p(1 -ρ n p) ≤ 16 3 ρ n (q -p) 2 .
The main difference from the proof in [START_REF] Gao | Rate-optimal graphon estimation[END_REF] is that now the matrices Θ 0 defining the probability distributions in the Fano lemma depend on ρ n . Namely, to prove the ρ n (k/n) ρ n ω ab with suitably chosen ω ab ∈ {0, 1} and c 1 > 0 small enough (for ρ n = 1 this coincides with the definition of elements Q ω ab in [START_REF] Gao | Rate-optimal graphon estimation[END_REF]). Then the squared Frobenius distance between matrices Θ 0 in the corresponding set is of the order n 2 (ρ n (k/n) 2 ∧ ρ 2 n ), which leads to the desired rate, whereas in view of (33) the Kullback-Leibler divergences between the probability measures in this set are bounded by Cn 2 ρ n k 2 n 2 ρn ∧ 1 ≤ Ck 2 . Thus, the lower bound of the order ρ n (k/n) 2 ∧ ρ 2 n follows. The argument used to prove the lower bound of the order ρ n log(k)/n ∧ ρ 2 n is quite analogous. To this end, we modify the corresponding construction of [START_REF] Gao | Rate-optimal graphon estimation[END_REF] only in that we take the connection probabilities of

the form ρn 2 + c 2 √ ρ n log(k) n ∧ √
ρ n ω a with suitably chosen ω a ∈ {0, 1} and c 2 > 0 small enough (for ρ n = 1 this coincides with the definition of probabilities B a in the proof of [START_REF] Gao | Rate-optimal graphon estimation[END_REF]).

Proof of Proposition 2.5

We prove that there exists a random matrix Θ measurable with respect to ξ 1 , . . . , ξ n and with values in

T n0 [k] satisfying E 1 n 2 Θ 0 -Θ 2 F ≤ CM 2 ρ 2 n 1 k 2 α∧1 . (34)
Obviously, this implies [START_REF] Diaconis | Graph limits and exchangeable random graphs[END_REF]. To obtain such Θ we construct a balanced partition z * where the first k -1 classes contain exactly n 0 elements and the last class contains nn 0 (k -1) elements. Then we construct Θ using block averages on the blocks given by z * . Let n = n 0 k + r where r is a remainder term between 0 and n 0 -

1. Define z * : [n] → [k] by (z * ) -1 (a) = i ∈ [n] : ξ i = ξ (j) for some j ∈ [(a -1)n 0 + 1, an 0 ]
for each a ∈ {1, . . . , k -1} and

(z * ) -1 (k) = i ∈ [n] : ξ i = ξ (j) for some j ∈ [(k -1)n 0 + 1, n]
where ξ (j) denotes the jth order statistic. Note that with this partition the first k -1 classes contain n 0 elements and the last class contains n 0 + r elements. We define

n * ab =        n 2 0 , if a = b, a = k, b = k, (n 0 + r)n 0 , if a = k or b = k and a = b, (n 0 -1)n 0 , if a = b and a = k, (n 0 + r)(n 0 + r -1), if a = b = k.
Using the partition z * , we define the block average

Q * ab = 1 n * ab i∈(z * ) -1 (a),j∈(z * ) -1 (b),i =j ρ n W (ξ i , ξ j ).
Finally, the approximation Θ of Θ 0 is defined as a symmetric matrix with entries

Θ ij = Q * z * (i)z * (j)
for all i = j and Θ ii = 0 for all i. We have

E 1 n 2 Θ 0 -Θ 2 F = 1 n 2 a∈[k],b∈[k] E i∈(z * ) -1 (a),j∈(z * ) -1 (b),i =j (Θ ij -Q * ab ) 2 = 1 n 2 a∈[k],b∈[k] E i∈(z * ) -1 (a),j∈(z * ) -1 (b),i =j ρ n W (ξ i , ξ j ) - u∈(z * ) -1 (a),v∈(z * ) -1 (b),u =v ρ n W (ξ u , ξ v ) n * ab 2 .
Comment citer ce document : Klopp, O., Tsybakov, A. B., Verzelen, N. (2017). Oracle inequalities for network models and sparse graphon estimation. Annals of Statistics, 45 (1), 316-354. DOI : 10.1214/16-aos1454

Define J a = [(a -1)n 0 + 1, an 0 ] if a < k and J k = [(k -1)n 0 + 1, n]. By definition of z * we have E 1 n 2 Θ 0 -Θ 2 F = ρ 2 n n 2 a∈[k],b∈[k] E i∈Ja,j∈J b ,i =j W (ξ (i) , ξ (j) ) - u∈Ja,v∈J b ,u =v W (ξ (u) , ξ (v) ) n * ab 2 ≤ ρ 2 n n 2 a∈[k],b∈[k] i∈Ja,j∈J b ,i =j   1 n * ab u∈Ja,v∈J b ,u =v E W (ξ (i) , ξ (j) ) -W (ξ (u) , ξ (v) ) 2   . (35)
Using ( 8) and Jensen's inequality we obtain

E W (ξ (i) , ξ (j) ) -W (ξ (u) , ξ (v) ) 2 ≤ M 2 E |ξ (i) -ξ (u) | α ′ + |ξ (j) -ξ (v) | α ′ 2 ≤ 2M 2 (E |ξ (i) -ξ (u) | 2 ) α ′ + (E |ξ (j) -ξ (v) | 2 ) α ′
where we set for brevity α ′ = α ∧ 1. Note that by definition of z * we have |i -u| < 2n 0 and |j -v| < 2n 0 . Therefore, application of Lemma 4.10 (see Section 4.10) leads to

E W (ξ (i) , ξ (j) ) -W (ξ (u) , ξ (v) ) 2 ≤ C(n 0 /n) 2α ′ ≤ C(1/k) 2α ′
where we have used that k = ⌊n/n 0 ⌋. Plugging this bound into (35) proves the proposition.

Proof of Proposition 3.2

For any W 0 ∈ W[k], we first construct an ordered graphon W ′ isomorphic to W 0 and we set f ′ = ρ n W ′ . Then we construct an ordered empirical graphon f ′ isomorphic to f Θ0 and we estimate the δ(•, •)-distance between these two ordered versions f ′ and f ′ . Consider the matrix Θ ′ 0 with entries (Θ ′ 0 ) ij = ρ n W (ξ i , ξ j ) for all i, j. As opposed to Θ 0 , the diagonal entries of Θ ′ 0 are not constrained to be null. By the triangle inequality, we get

E δ 2 f Θ 0 , f 0 ≤ 2 E δ 2 f Θ 0 , f Θ ′ 0 + 2 E δ 2 f Θ ′ 0 , f 0 . ( 36
)
Since the entries of Θ 0 coincide with those of Θ ′ 0 outside the diagonal, the difference f Θ 0f Θ ′ 0 is null outside of a set of measure 1/n. Also, the entries of Θ ′ 0 are smaller than

ρ n . It follows that E[δ 2 ( f Θ 0 , f Θ ′ 0 )] ≤ ρ 2 n /n. Hence, it suffices to prove that E[δ 2 ( f Θ ′ 0 , f 0 )] ≤ Cρ 2 n k/n.
We prove this inequality by induction on k. The result is trivial for k = 1 as δ 2 f Θ ′ 0 , f 0 = 0. Fix some k > 1 and assume that the result is valid for

W[k -1]. Consider any W 0 ∈ W[k] and let Q ∈ R k×k
sym and φ : [0, 1] → [k] be associated to W 0 as in definition [START_REF] Wolfe | Nonparametric graphon estimation[END_REF]. We assume w.l.o.g. that all the rows of Q are distinct and that

λ a := λ(φ -1 (a)) is positive for all a ∈ [k], since otherwise W 0 belongs to W[k -1]. For any b ∈ [k], define the cumulative distribution function F φ (b) = b a=1 λ a and set F φ (0) = 0. For any (a, b) ∈ [k] × [k] define Π ab (φ) = [F φ (a -1), F φ (a)) × [F φ (b -1), F φ (b)
Obviously, f ′ = ρ n W ′ is weakly isomorphic to f 0 = ρ n W 0 . Let λ a = 1 n n i=1 1 {ξi∈φ -1 (a)}
be the (unobserved) empirical frequency of group a. Here, ξ 1 , . . . , ξ n are the i.i.d. uniformly distributed random variables in the graphon model [START_REF] Peter | A nonparametric view of network models and newman-girvan and other modularities[END_REF]. Note that the relations

(i) ψ(x) = a for all a ∈ [k] and x ∈ [F φ (a -1), F φ (a -1) + λ a ∧ λ a ), (ii) λ(ψ -1 (a)) = λ a for all a ∈ [k].
Such a function ψ exists. Indeed, for each a such that λ a > λ a , conditions (i) and (ii) are trivially satisfied if we take ψ -1 (a) = [F φ (a -1), F φ (a -1) + λ a ), and there is an interval of Lebesgue measure λ aλ a left non-assigned. Summing over all such a, we see that there is a union of intervals with Lebesgue measure m + := a:λa> λa (λ aλ a ) left non-assigned. On the other hand, for a such that λ a < λ a , we must have

ψ(x) = a for x ∈ [F φ (a -1), F φ (a -1) + λ a )
to satisfy (i), while to meet condition (ii) we need additionally to assign ψ(x) = a for x on a set of Lebesgue measure λaλ a . Summing over all such a, we need additionally to find a set of Lebesgue measure m -:= a: λa>λa (λ aλ a ) to make such assignments. But this set is readily available as a union of non-assigned intervals for all a such that λ a > λ a since m + = m -by virtue of (37). Finally define the graphon f ′ (x, y) = Q ψ(x),ψ(y) . Notice that in view of (ii) f ′ is weakly isomorphic to the empirical graphon f Θ 0 . Since δ(•, •) is a metric on the quotient space W,

δ 2 ( f Θ0 , f 0 ) = δ 2 ( f ′ , f ′ ) ≤ [0,1] 2 | f ′ (x, y) -f ′ (x, y)| 2 dxdy ≤ ρ 2 n [0,1] 2 1 {f ′ (x,y) = f ′ (x,y)} dxdy.
The two functions f 0 (x, y) and f (x, y) are equal except possibly the case when either x or y belongs to one of the intervals [F φ (a -1) + λ a ∧ λ a , F φ (a -1) + λ a ) for a ∈ [k]. Hence, the Lebesgue measure of the set {(x, y) :

f ′ (x, y) = f ′ (x, y)} is not greater than 2m + = m + + m -= k a=1 |λ a -λ a |. Thus, δ 2 ( f Θ ′ 0 , f 0 ) ≤ ρ 2 n k a=1 |λ a -λ a |.
Since ξ 1 , . . . , ξ n are i.i.d. uniformly distributed random variables, n λ a has a binomial distribution with parameters (n, λ a ). By the Cauchy-Schwarz inequality we get

E[|λ a -λ a |] ≤ λa(1-λa) n
. Applying again the Cauchy-Schwarz inequality, we conclude that

E δ 2 ( f Θ ′ 0 , f 0 ) ≤ ρ 2 n √ n k a=1 λ a ≤ ρ 2 n k n .

Proof of Proposition 3.5

Arguing as in the proof of Proposition 3.2, we have where we recall that Θ ′ 0 is defined by (Θ ′ 0 ) ij = ρ n W (ξ i , ξ j ) for all i, j. Hence, it suffices to prove that

E δ 2 f Θ 0 , f 0 ≤ 2ρ 2 n n + 2 E δ 2 f Θ ′ 0 ,
E δ 2 f Θ ′ 0 , f 0 ≤ C ρ 2 n n α∧1 .
We have

δ 2 f Θ ′ 0 , f 0 = inf τ ∈M n i,j=1 j/n (j-1)/n i/n (i-1)/n |f 0 (τ (x), τ (y)) -(Θ ′ 0 ) ij | 2 dxdy.
The infimum over all measure-preserving bijections is smaller than the minimum over the subclass of measurepreserving bijections τ satisfying the following property

j/n (j-1)/n i/n (i-1)/n W (τ (x), τ (y))dxdy = σ(j)/n (σ(j)-1)/n σ(i)/n (σ(i)-1)/n W (x, y)dxdy
for some permutation σ = (σ(1), . . . , σ(n)) of {1, . . . , n}. Such τ correspond to permutations of intervals [(i -1)/n, i/n] in accordance with σ. For (x, y) ∈ [(σ(i) -1)/n, σ(i)/n] × [(σ(j) -1)/n, σ(j)/n] we use the bound

|ρ n W 0 (x, y) -ρ n W 0 (ξ i , ξ j )| ≤ ρ n W 0 (x, y) -ρ n W 0 σ(i) n+1 , σ (j) n+1 (38)
+ ρ n W 0 σ(i) n+1 , σ(j) n+1 -ρ n W 0 ξ (σ(i)) , ξ (σ(j)) + ρ n W 0 ξ (σ(i)) , ξ (σ(j)) -ρ n W 0 (ξ i , ξ j )
where ξ (m) denotes the mth largest element of the set {ξ 1 , . . . , ξ n }. We choose a random permutation

σ = (σ(1), . . . , σ(n)) such that ξ σ -1 (1) ≤ ξ σ -1 (2) ≤ • • • ≤ ξ σ -1 (n) . With this choice of σ, we have that ξ (σ(i)) , ξ (σ(j)) = (ξ i , ξ j ) and ρ n W 0 ξ (σ(i)) , ξ (σ(j)) -ρ n W 0 (ξ i , ξ j ) = 0 almost surely.
For the first summand in (38), as W 0 (•, •) satisfies ( 8) and

σ(i) n+1 , σ(j) n+1 ∈ [(σ(i) -1)/n, σ(i)/n] × [(σ(j) -1)/n, σ(j)/n]
we get

W 0 (x, y) -W 0 σ(i) n+1 , σ(j) n+1 ≤ 2Ln -α ′ , (39)
where we set for brevity α ′ = α ∧ 1. To evaluate the contribution of the second summand on the right hand side of (38) we use that

W 0 σ(i) n+1 , σ(j) n+1 -W 0 ξ (σ(i)) , ξ (σ(j)) ≤ M σ(i) n+1 -ξ (σ(i)) α ′ + σ(j) n+1 -ξ (σ(j)) α ′ . (40)
Squaring, integrating and taking expectation we obtain

E   i,j σ(j)/n (σ(j)-1)/n σ(i)/n (σ(i)-1)/n σ(i) n+1 -ξ (σ(i)) 2α ′ dxdy   = 1 n E n m=1 m n+1 -ξ (m) 2α ′ ≤ max m=1,...,n E m n+1 -ξ (m) 2α ′ ≤ max m=1,...,n Var(ξ (m) ) α ′ ≤ Cn -α ′ (41)
where we have used the relations E(ξ (m) ) = m n+1 , Var(ξ (m) ) ≤ C/n, and Jensen's inequality. The contribution corresponding to the second summand on the right hand side of (40) is evaluated analogously. Combining (39) -( 41) with (38) we get

E δ 2 f Θ ′ 0 , f 0 ≤ Cρ 2 n n -α ′ .
Comment citer ce document : Klopp, O., Tsybakov, A. B., Verzelen, N. (2017). Oracle inequalities for network models and sparse graphon estimation. Annals of Statistics, 45 (1), 316-354. DOI : 10.1214/16-aos1454

Proof of Corollary 2.7

To prove the first part of the corollary, notice that its assumptions imply that the partition is balanced and ρ n ≥ k log(k)/n. Thus, similarly to Corollary 2.2, we obtain from Proposition 2.1 that

E 1 n 2 Θ -Θ 0 2 F ≤ C n 2 Θ 0 -Θ * ,n0 2
F + Cρ n log(k) n + k 2 n 2 .
Using Proposition 2.5 to bound the expectation of the first summand on the right hand side we get

E 1 n 2 Θ -Θ 0 2 F ≤ C ρ 2 n k 2(α∧1) + ρ n log(k) n + k 2 n 2 . ( 42
)
Now [START_REF] Lovasz | Limits of dense graph sequences[END_REF] follows from (42) by taking k = ρ n n 2 1 2(1+α∧1) . Bound [START_REF] Lovász | Large networks and graph limits[END_REF] for the restricted least squares estimator follows from Propositions 2.3 and 2.6.

Proof of Corollary 3.3

To prove part (i) of the corollary, we control the size of each block of Θ 0 . For any a in [k], the number N a of nodes belonging to block a is binomial random variable with parameters (n, 1/k) since the graphon W is balanced. By Bernstein's inequality,

P N a - n k ≤ -t ≤ exp - t 2 /2 n/k + t/3 .
Taking t = n/(2k) in the above inequality, we obtain

P N a ≤ n 2k ≤ exp[-Cn/k].
This inequlity and the union bound over all a ∈ [k] imply that the size of all blocks of Θ 0 is greater than n 0 with probability greater than 1k exp(-Cn/k). Together with Propositions 2.1 and 3.2, this yields

E δ 2 f , f 0 ≤ C ′ ρ n k 2 n 2 + ρ n log(k) n + ρ 2 n k n + k exp(-Cn/k) ,
where the last summand is negligible. The second part of the corollary is a straightforward consequence of Propositions 2.1 and 2.3.

Proof of Proposition 3.4

It is enough to prove separately the following three minimax lower bounds.

inf f sup W0∈W[k] E W0 [δ 2 ( f , ρ n W 0 )] ≥ Cρ 2 n k -1 n , (43) inf
f sup W0∈W[k] E W0 [δ 2 ( f , ρ n W 0 )] ≥ C ρ n k 2 n 2 ∧ ρ 2 n , (44)
inf

f sup W0∈W[2] E W0 [δ 2 ( f , ρ n W 0 )] ≥ C ρ n n ∧ ρ 2 n . (45)
4.9.1 Proof of (43)

Without loss of generality, it suffices to prove (43) for k = 2 and for all k = 16 k with integer k large enough. Indeed, for any k > 2, there exists k ′ ≤ k such that kk ′ ≤ 15 and k ′ is either a multiple of 16 or equal to 2, so that inf

f sup W0∈W[k] E W0 δ 2 f ; f 0 ≥ inf f sup W0∈W[k ′ ] E W0 δ 2 f ; f 0 ≥ Cρ 2 n k ′ -1 n ≥ C 4 ρ 2 n k -1 n .
Comment citer ce document : Klopp, O., Tsybakov, A. B., Verzelen, N. (2017). Oracle inequalities for network models and sparse graphon estimation. Annals of Statistics, 45 (1), 316-354. DOI : 10.1214/16-aos1454 Lemma 4.5. For all u, v ∈ C such that u = v, the graphons W u and W v are well separated in the δ(•, •) distance:

δ 2 (W u , W v ) ≥ η 2 0 kǫ/2, so that δ 2 (ρ n W u , ρ n W v ) ≥ ρ 2 n η 2 0 kǫ/2, ∀ u, v ∈ C : u = v. (49)
Now, choose ǫ such that ǫ 2 = 3 (16) 3 nk . Then it follows from Lemmas 4.3 and 4.4 that

K(P Wu , P Wv ) ≤ 1 16 log |C|, ∀ u, v ∈ C : u = v. (50)
In view of Theorem 2.7 in [START_REF] Alexandre | Introduction to nonparametric estimation[END_REF], inequalities (49) and (50) imply that inf

f sup W0∈W[k] E W0 [δ 2 ( f , ρ n W 0 )] ≥ Cρ 2 n k n
where C > 0 is an absolute constant. This completes the proof for the case when k is a large enough multiple of 16.

Let now k = 2. Then, we reduce the lower bound to the problem of testing two hypotheses. We consider the matrix B = 1 1 1 -1 and the two corresponding graphons W u1 and W u2 with u 1 = (ǫ, -ǫ) and u 2 = (-ǫ, ǫ). Adapting the argument of Lemma 4.5, one can prove that δ 2 (ρ n W u1 , ρ n W u2 ) ≥ ρ 2 n ǫ. Moreover, exactly as in Lemma 4.3, the Kullback-Leibler divergence between P Wu 1 and P Wu 2 is bounded by Cnǫ 2 . Taking ǫ of the order n -1/2 and using Theorem 2.2 from [START_REF] Alexandre | Introduction to nonparametric estimation[END_REF] we conclude that inf

f sup W0∈W[2] E W0 [δ 2 ( f , ρ n W 0 )] ≥ Cρ 2 n 1 n
where C > 0 is an absolute constant.

Proof of Lemma 4.2. Let B be a k × k symmetric random matrix such that its elements B a,b , a ≤ b ∈ [k], are independent Rademacher random variables. It suffices to prove that B satisfies properties (46) and (47) with positive probability. Fix a = b. Then, B a,• , B b,• is distributed as a sum of k independent Rademacher variables. By Hoeffindg's inequality

P [| B a,• , B b,• | ≥ k/4] ≤ 2 exp[-k/32].
By the union bound, property (46) is satisfied for all a = b with probability greater than 1 -2k 2 exp[-k/32]. For k larger than some absolute constant, this probability is greater than 3/4.

/2 since π 1 ([η 0 k]) ∩ π 2 ([η 0 k]) = ∅.
Thus, T π1,π2 /8 is stochastically greater than a binomial random variable with parameters η 0 k(η 0 k -1)/2 and 1/2. Applying again Hoeffding's inequality, we find

P T π1,π2 /8 ≤ η 2 0 k 2 8 - η 0 k 4 ≤ exp - η 2 0 k 2 32 .
For k large enough we have η 0 k/4 ≤ η 2 0 k 2 /16 so that T π1,π2 ≥ η 2 0 k 2 /2 with probability greater than 1exp(-η 2 0 k 2 /32). There are less than k 2η0k such maps (π 1 , π 2 ) so that property (47) is satisfied with probability greater than 1exp(2η 0 k log(k)η 2 0 k 2 /32). Again, this probability is greater than 3/4 for k large enough. Applying once again the union bound we find that properties (46) and ( 47

E e λ(S k -k/4) ≤ E e λ(η-k/4) ≤ e λ 2 k/16 ,
where the last bound is due to Hoeffding's inequality. Applying the exponential Markov inequality and choosing λ = 1, we obtain

P S k - k 4 ≥ k/8 ≤ exp [-k/16]
and, in view of (51), we conclude that |C| ≥ exp[k/16].

Proof of Lemma 4.5. Let u and v be two different vectors in C and let τ be a measure preserving bijection [0, 1] → [0, 1]. We aim to prove that, for any τ ,

|W u (x, y) -W v (τ (x), τ (y))| 2 dxdy ≥ η 2 0 kǫ/2 , (52)
where we recall that η 0 = 1/16.

If x and x ′ correspond to two different classes of W u , that is x ∈ [F u (a -1), F u (a)) and x ′ ∈ [F u (b -1), F u (b)) for some a = b, then the inner product between W u (x, •) and W u (x ′ , •) satisfies

(W u (x, y) -1/2)(W u (x ′ , y) -1/2)dy = 1 4 k c=1 1 k + u c B ac B bc ≤ 1 4k B a,. , B b,. + 1 4 kǫ ≤ 1/8 , (53)
h u,a -k v,b1 2 2 + h u,a -k v,b2 2 2 ≥ k v,b1 -k v,b2 2
|W u (x, y) -W v (τ (x), τ (y)| 2 dxdy ≥ a1∈A a2∈A ω a1,π(a1) ω a2,π(a2) [Q a1,a2 -Q π(a1),π(a2) ] 2 ≥ 1 4k 2 a1∈A a2∈A [B a1,a2 -B π(a1),π(a2) ] 2 ,
where the last inequality follows from the facts that Q = (J + B)/2 and ω a,π(a) ≥ 1/k. Finally, we apply the property (47) of B to conclude that

|W u (x, y) -W v (τ (x), τ (y))| 2 dxdy ≥ η 2 0 /8 ≥ η 2 0 kǫ/2.
This proves (52) and thus the lemma. p Aa α a (u) log a p Aa α a (u) a p Aa α a (v) where the sums in a are over [k] n and the sum in A is over all triangular upper halves of matrices in {0, 1} n×n . Since the function (x, y) → x log(x/y) is convex we can apply Jensen's inequality to get

K(P Wu , P Wv ) ≤ a α a (u) log α a (u) α a (v) = n a∈[k] (1/k + u a ) log 1/k + u a 1/k + v a (54)
where the last equality follows from the fact that α a (u) are n-product probabilities. Since the Kullback-Leibler divergence does not exceed the chi-square divergence we obtain

a∈[k] (1/k + u a ) log 1/k + u a 1/k + v a ≤ a∈[k] (u a -v a ) 2 1/k + v a ≤ 16k 2 ǫ 2 /

Proof of (44)

As in the proof of Proposition 2.4, we use here Fano's method. The main difference is that the graphon separation in δ(•, •) distance is more difficult to handle than the matrix separation in the Frobenius distance.

First, note that it is sufficient to prove (44) for k > k 0 where k 0 is any fixed integer. Indeed, if k ≤ k 0 , the lower bound (44) immediately follows from (45).

Let C 0 denote the set of all symmetric k × k matrices with entries in {-1, 1}. The graphon hypotheses that we consider in this proof are generated by matrices of intra-class connection probabilities of the form Q B := (J + ǫB)/2 where B ∈ C 0 , ǫ ∈ (0, 1/2), and J is a k × k matrix with all entries equal to 1. Given a matrix Q B , define the graphon W B ∈ W[k] by the formula

W B (x, y) = (a,b)∈[k]×[k] (Q B ) ab 1 [(a-1)/k,a/k)×[(b-1)/k,b/k) (x, y).
As in the previous proof, we use the following combinatorial result in the spirit of the Varshamov-Gilbert lemma [15, Chapter 2] that grants the existence of a large subset C of C 0 such that the matrices B ∈ C are well separated in some sense. Given any two permutations π and π ′ of [k] and any matrix B, we denote by B π,π ′ a matrix with entries B π,π ′ ab = B π(a)π ′ (b) .

Lemma 4.6. Let k 0 be an integer large enough. For any k > k 0 , there exists a subset C of C 0 satisfying log |C| ≥ k 2 /32 and such that

B 1 -B π,π ′ 2 2 F ≥ k 2 2 (55)
for all permutations π, π ′ and all

B 1 = B 2 ∈ C.
We assume in the rest of this proof that k is greater than k 0 . As noticed above, it is enough to prove (44) only in this case. We choose a maximal subset C satisfying the properties stated in Lemma 4.6. The next lemma shows that the separation between matrices B in C translates into separation between the corresponding graphons W B . Lemma 4.7. Let C be a maximal set satisfying the properties stated in Lemma 4.6. For any two distinct

B 1 and B 2 in C, we have δ 2 (ρ n W B1 , ρ n W B2 ) ≥ ρ 2 n ǫ 2 /8. (56)
Finally, in order to apply Fano's method, we need to have an upper bound on the Kullback-Leibler divergence between the distributions P WB for B ∈ C. It is given in the next lemma. Lemma 4.8. For any B 1 and B 2 in C, we have

K(P WB 1 , P WB 2 ) ≤ 3n 2 ρ n ǫ 2 .
Choosing now ǫ = k n √ ρn ∧ 1 /32 we deduce from Lemmas 4.8 and 4.6 that

K(P WB 1 , P WB 2 ) ≤ 1 10 log |C|, ∀ B 1 , B 2 ∈ C : B 1 = B 2 . (57)
In view of Theorem 2.7 in [START_REF] Alexandre | Introduction to nonparametric estimation[END_REF], inequalities (56) and (57) imply that inf

f sup W0∈W[k] E W0 [δ 2 ( f , ρ n W 0 )] ≥ C ρ n k 2 n 2 ∧ ρ 2 n
where C > 0 is an absolute constant. This completes the proof of (44).

Comment citer ce document :

-k(k+1)/2 |B[B, k(k + 1)/8, d H ]| ≤ |C ′ | -1 ≤ e -k(k+1)/16
where C ′ is a maximal subset of matrices B that are k(k+1)

4

-separated with respect to the Hamming distance. We then conclude that

|C| ≥ |C 0 | k! 2 |B[B, k(k + 1)/2, • F ]| ≥ exp [k{(k + 1)/16 -2 log(k)}] ,
which is larger exp(k 2 /32) for k large enough. , is doubly stochastic. For any permutation π of [k], denote H(π) the corresponding permutation matrix. By the Birkhoff-von Neumann theorem [START_REF] Chvtal | Linear programming. A Series of books in the mathematical sciences[END_REF], kω is a convex combination of permutation matrices, that is there exist positive numbers γ such that π γ π = 1/k, and ω = π γ π H(π) where the summation runs over all permutations. Using these remarks we obtain Aa for a matrix Θ 2 depending on B 2 in the same way as Θ 1 depends on B 1 . The Kullback-Leibler divergence between P WB 1 and P WB 2 has the form .

|W B 1 (x, y) -W B 2 (τ (x), τ (y))| 2 dxdy = ǫ 2 4 a1,a2,b1,b2∈[k] ω a1a2 ω b1b2 (B 1 ) a1b1 -(B 2 ) a2b2 2 = ǫ 2 4 π1,π2 a1,a2,b1,b2∈[k] γ π1 γ π2 H(π 1 ) a1a2 H(π 2 ) b1b2 (B 1 ) a1b1 -(B 2
K(P WB 1 , P WB 2 ) = A a α a p (
Here, the sum in A for fixed a is the Kullback-Leibler divergence between two n(n-1)/2-products of Bernoulli measures, each of which has success probability either ρ n (1 + ǫ)/2 or ρ n (1ǫ)/2. Thus, for p = (1 + ǫ)/2 and q = (1ǫ)/2 we have

K(P WB 1 , P WB 2 ) ≤ n(n -1) 2 ρ n κ(p, q), (59)
where κ(p, q) is the Kullback-Leibler divergence between the Bernoulli measures with success probabilities p and q. Since the Kullback-Leibler divergence does not exceed the chi-square divergence we obtain κ(p, q) ≤ (pq) 2 (p -1 + q -1 ) = 4ǫ 2 /(1ǫ 2 ) ≤ 16ǫ 2 /3 for any ǫ < 1/2. The lemma now follows by substitution of this bound on κ(p, q) into (59).

Proof of (45)

We use here a reduction to the problem of testing two simple hypotheses by Le Cam's method. Fix some 0 < ǫ ≤ 1/4. Let W 1 be the constant graphon with W 1 (x, y) ≡ 1/2, and let W 2 ∈ W[2] be the 2-step graphon with W 2 (x, y) = 1/2 + ǫ if x, y ∈ [0, 1/2) 2 ∪ [1/2, 1] 2 and W 2 (x, y) = 1/2ǫ elsewhere. Obviously, we have

δ 2 (ρ n W 1 , ρ n W 2 ) = ρ 2 n ǫ 2 . ( 60
)
We have inf where χ 2 (P W2 , P W1 ) is the chi-square divergence between P W2 and P W1 . In the last inequality we have used (2.24) and (2.26) from [START_REF] Alexandre | Introduction to nonparametric estimation[END_REF], and (60). Finally, the following lemma allows us to conclude the proof by setting ǫ = Proof of Lemma 4.9. Let L(A ′ ) be likelihood ratio of P W2 with respect to P W1 . Since χ 2 (P W2 , P W1 ) = E W1 [L(A ′ ) 2 ] -1 it remains to prove that E W1 [L(A ′ ) 2 ] ≤ 5/4.

f max W0∈{W1,W2} E W0 [δ 2 ( f , ρ n W 0 )] ≥ 1 2 δ 2 ( f , ρ n W 1 ) + δ 2 ( f ,
For the sake of brevity, we write in what follows E[•] = E W1 [•]. We also set p 0 := ρ n /2, p 1 := ρ n (1/2 + ǫ) and p 2 := ρ n (1/2ǫ).

As the graphon ρ n W 2 is a 2-step function, we may assume that the components of ξ = (ξ 1 , . . . , ξ n ) are i.i.d. uniformly distributed on {0, 1}. Given ξ, define the collection S := {{a, b} : ξ a = ξ b } of subsets of indices with identical position. For {i, j} in S (resp. S c ), A i,j follows a Bernoulli distribution with parameter p 1 (resp. p 2 ). Denote µ the distribution of S and n (2) = n(n -1)/2 the number of subsets of size 2 of Using the definition of p 0 , p 1 and p 2 , we find

E L S1 (A ′ )L S2 (A ′ ) = 1 + ρ 2 n ǫ 2 p 0 (1 -p 0 ) |S1∩S2|+|S c 1 ∩S c 2 | 1 - ρ 2 n ǫ 2 p 0 (1 -p 0 ) |S1∆S2| ≤ 1 + ρ 2 n ǫ 2 p 0 (1 -p 0 ) |S1∩S2|+|S c 1 ∩S c 2 |-|S1∆S2| ≤ exp 2|S 1 ∩ S 2 | + 2|S c 1 ∩ S c 2 | -n (2) 4ρ n ǫ 2 .
Thus, to bound the second moment of L(A ′ ), it suffices to control an exponential moment of

T := |S 1 ∩ S 2 | + |S c 1 ∩S c 2 |
where S 1 and S 2 are independent and distributed according to µ. To handle this quantity, we denote by ξ = (ξ 1 , . . . , ξ n ) and by ξ ′ = (ξ ′ 1 , . . . , ξ ′ n ) the positions for the first and second sample corresponding to S 1 and S 2 , respectively. Next, for any i, j ∈ {0, 1} 2 , define Plugging this identity into the expression for E[L 2 (A ′ )], we conclude that

E[L 2 (A ′ )] ≤ E exp 8ρ n ǫ 2 Z 2 ,
where E[•] stands for the expectation with respect to the distribution of Z. By Hoeffding's inequality, Z has a subgaussian distribution with subgaussian norm smaller than n 1/2 . Consequently, E[L 2 (A ′ )] ≤ 5/4 as soon as 8ρ n nǫ 2 is smaller than some numerical constant.

Proposition 2 . 4 .

 24 Consider the network sequence model. For all k ≤ n and all 0

  1+α and the clustering rate ρn log n n

Corollary 3 . 3 .

 33 Comment citer ce document : Klopp, O., Tsybakov, A. B., Verzelen, N. (2017). Oracle inequalities for network models and sparse graphon estimation. Annals of Statistics, 45 (1), 316-354. DOI : 10.1214/16-aos1454 Consider the graphon model (2) with W 0 ∈ W[k]. There exist absolute constants C 1 and C 2 such that the following holds.

Corollary 3 . 6 .

 36 Consider the graphon model (2) with W 0 ∈ Σ(α, L) where α, L > 0 and 0

)

  Comment citer ce document : Klopp, O., Tsybakov, A. B., Verzelen, N. (2017). Oracle inequalities for network models and sparse graphon estimation. Annals of Statistics, 45 (1), 316-354. DOI : 10.1214/16-aos1454 Decoupling (26) by use of the inequality 2uv ≤ u 2 + v 2 and combining the result with (27) we obtain

) where 1 A

 1 (•) denotes the indicator function of set A. Finally, we consider the ordered graphonW ′ (x, y) = k a=1 k b=1 Q ab 1 Π ab (φ) (x, y) .Comment citer ce document : Klopp, O., Tsybakov, A. B., Verzelen, N. (2017). Oracle inequalities for network models and sparse graphon estimation. Annals of Statistics, 45 (1), 316-354. DOI : 10.1214/16-aos1454

  λa (λ aλ a ) = a: λa>λa ( λaλ a ). (37)Consider a function ψ : [0, 1] → [k] such that:

f 0 ,

 0 Comment citer ce document : Klopp, O., Tsybakov, A. B., Verzelen, N. (2017). Oracle inequalities for network models and sparse graphon estimation. Annals of Statistics, 45 (1), 316-354. DOI : 10.1214/16-aos1454

  Fix any two subsets X and Y of [k] such that |X| = |Y | = η 0 k and X ∩ Y = ∅. Let π 1 and π 2 be any two labelings of X and Y . Then, define T π1,π2 := η0k a,b=1 [B π1(a),π1(b) -B π2(a),π2(b) ] 2 . By symmetry of B, T π1,π2 /8 is greater than a<b [B π1(a),π1(b) -B π2(a),π2(b) ] 2 /4 (we have put aside the diagonal terms) where all the summands [B π1(a),π1(b) -B π2(a),π2(b) ] 2 /4 are independent Bernoulli random variables with parameter 1

since we assume that 4kǫ ≤ 1 .

 1 For any a, b ∈ [k], define ω ab the Lebesgue measure of [F u (a -1), F u (a)] ∩ τ ([F v (b -1), F v (b)]). Since τ is measure preserving, b ω ab = 1/k + u a and a ω ab = 1/k + v b . For any a and b ∈ [k] define h u,a (y) = W u (F u (a -1), y) -1/2 and k v,b (y) = W v (F v (b -1), τ (y)) -1/2. Then, we have |W u (x, y) -W v (τ (x), τ (y))| 2 dxdy = b |h u,a (y)k v,b (y)| 2 dy.Let •, • 2 and • 2 denote the standard inner product and the Euclidean norm in L 2 ([0, 1]). By definition of W u we have that |k v,a (y)| = 1/2 for all y ∈ [0, 1] and any a ∈ [k] which implies k v,a 2 = 1/2. Now for b 1 = b 2 , k v,b1k v,b2 2 2 ≥ 1/2 -1/4 = 1/8 by (53). By the triangle inequality, this implies that

2 2 ≥ 1 / 16 .

 2116 Comment citer ce document : Klopp, O., Tsybakov, A. B., Verzelen, N. (2017). Oracle inequalities for network models and sparse graphon estimation. Annals of Statistics, 45 (1), 316-354. DOI : 10.1214/16-aos1454 As a consequence, for any a ∈ [k] there exists at most one b ∈ [k] such that h u,ak v,b 2 < 1/32. If such an index b exists, it is denoted by π(a). Exactly the same argument shows that for any b ∈ [k] there exists at most one a∈ [k] such that h u,ak v,b2 < 1/32 which implies that there exists no a = a ′ such that π(a) = π(a ′ ). Thus, it is possible to extend π to a permutation of[k]. We get|W u (x, y) -W v (τ (x), τ (y))| 2 dxdy ≥ + u aω a,π(a) .If the sum k a=1 1/k + u aω a,π(a) is greater than kǫ/16, then (52) is satisfied. Thus, we can assume in the sequel that k a=1 1/k + u aω a,π(a) ≤ kǫ/16. Using that ω a,b ≤ (1/k + u a ) ∧ (1/k + v b ) and the cardinality of the collection {a ∈ [k] : u a > 0} is k/2 we deduce that the collection {a ∈ [k] : u a > 0, v π(a) > 0 and ω a,π(a) ≥ 1/k} has cardinality greater than 7k/16. Since for u = v ∈ C, |A u ∩ A v | ≤ 3k/8 (Lemma 4.4), there exist subsets A ⊂ A u and B ⊂ A v of cardinality η 0 k (recall that η 0 = 1/16) such that π(A) = B, A ∩ B = ∅, and ω a,π(a) ≥ 1/k for all a ∈ A. Hence, |W u (x, y) -W v (τ (x), τ (y))| 2 dxdy ≥ a1∈A a2∈A [Fu(a1-1),Fu(a1))×[Fu(a2-1),Fu(a2))

Proof of Lemma 4 . 3 .

 43 For u ∈ C 0 , let ζ(u) = (ζ 1 (u), . . . , ζ n (u)) be the vector of n i.i.d. random variables with the discrete distribution on [k] defined by P[ζ 1 (u) = a] = 1/k + u a for any a ∈ [k]. Let Θ 0 be the n × n symmetric matrix with elements (Θ 0 ) ii = 0 and (Θ 0 ) ij = ρ n Q ζi(u),ζj (u) for i = j. Assume that, conditionally on ζ(u), the adjacency matrix A is sampled according to the network sequence model with such probability matrix Θ 0 . Notice that in this case the observations A ′ = (A ij , 1 ≤ j < i ≤ n) have the probability distribution P Wu . Using this remark and introducing the probabilities α a (u) = P[ζ(u) = a] and p Aa = P[A ′ = A|ζ(u) = a] for a ∈ [k] n , we can write the Kullback-Leibler divergence between P Wu and P Wv in the form K(P Wu , P Wv ) = A a

Proof of Lemma 4 . 7 .

 47 Let B 1 and B 2 be two distinct matrices in C and let τ be a measure preserving bijection [0, 1] → [0, 1]. Our aim is to prove that, for any such τ , |W B1 (x, y) -W B2 (τ (x), τ (y))| 2 dxdy ≥ ǫ 2 /8. (58) For any a, b ∈ [k], let ω ab denote the Lebesgue measure of [(a -1)/k, a/k] ∩ τ ([(b -1)/k, b/k]). Since τ is measure preserving, b ω ab = 1/k and a ω ab = 1/k. Hence, the k × k matrix kω, where ω = (ω ab ) a,b∈[k]

) a2b2 2 ((B 1 ) 2 = ǫ 2 4 γ π1 γ π2 ǫ 2 k 2 8 = ǫ 2 8 , 1 )

 212481 ab -(B 2 ) π1(a)π2(b) π1,π2 γ π1 γ π2 B 1 -B π1,π2 Comment citer ce document : Klopp, O., Tsybakov, A. B., Verzelen, N. (2017). Oracle inequalities for network models and sparse graphon estimation. Annals of Statistics, 45 (1), 316-354. DOI : 10.1214/16-aos1454 where we have used Lemma 4.6 and the property π γ π = 1/k. Proof of Lemma 4.8. The proof is quite similar to that of Lemma 4.3. Fix two matrices B 1 and B 2 in C. Let ζ = (ζ 1 , . . . , ζ n ) be the vector of n i.i.d. random variables with uniform distribution on [k]. Let Θ 1 be the n × n symmetric matrix with elements (Θ 1 ) ii = 0 and (Θ 1 ) ij = ρ n [1 + (B 1 ) ζi,ζj ]/2 for i = j. Assume that, conditionally on ζ(u), the adjacency matrix A is sampled according to the network sequence model with such probability matrix Θ 1 . Notice that in this case the observations A ′ = (A ij , 1 ≤ j i ≤ n) have the probability distribution P WB 1 . Using this remark, we introduce the probabilities α a = P[ζ = a] and p (Aa = P[A ′ = A|ζ = a] for a ∈ [k] n . Next, we introduce the analogous probabilities p

c0 nρn ∧ 1 4 .

 4 Comment citer ce document : Klopp, O., Tsybakov, A. B., Verzelen, N. (2017). Oracle inequalities for network models and sparse graphon estimation. Annals of Statistics, 45 (1), 316-354. DOI : 10.1214/16-aos1454

-p 1 1 -p 0 |S| 1 p 1 ( 1 -

 10111 [n]. Then, the likelihood has the formL(A ′ ) = L S (A ′ )dµ(S) , L S (A ′ ) := 1 p 0 ) p 0 (1p 1 ) A ab {a,b}∈S c p 2 (1p 0 ) p 0 (1p 2 )A ab.By Fubini theorem, we may writeE[L 2 (A ′ )] = E L S1 (A ′ )L S2 (A ′ ) dµ(S 1 )dµ(S 2 ), whereE L S1 (A ′ )L S2 (A ′ ) = 1p 1 1 -

N

  ij := | a : ξ a = i and ξ ′ a = j | . Then we have 2|S 1 ∩ S 2 | + n = N 2 00 + N 2 01 + N 2 10 + N 2 11 and 2|S c 1 ∩ S c 2 | = 2N 00 N 11 + 2N 01 N 10 so that 2T + n = (N 00 + N 11 ) 2 + (N 01 + N 10 ) 2 .Define the random variable Z := N 00 + N 11n/2. It has a centered binomial distribution with parameters n and 1/2. We have2Tn (2) = (n/2 + Z) 2 + (n/2 -Z) 2nn (2) = 2Z 2n/2 .

  and Θ * ,1 = Θ * . Consider the network sequence model. There exist positive absolute constants C 1 , C 2 , C 3 such that for n 0

	Proposition 2.1.
	Comment citer ce document :
	Klopp, O., Tsybakov, A. B., Verzelen, N. (2017). Oracle inequalities for network models and
	sparse graphon estimation. Annals of Statistics, 45 (1), 316-354. DOI : 10.1214/16-aos1454

  The risk bound (18) is driven by the probability matrix estimation error. The upper bound (18) is of the order ρ n of probability matrix estimation, cf. Proposition 2.4. Due to (19), it is optimal up to log(k) factor with respect to the δ(•, •) distance.

	k 2 n 2 + log(k) n	, which is
	the optimal rate

  ) are satisfied with probability greater than 1/2. Comment citer ce document : Klopp, O., Tsybakov, A. B., Verzelen, N. (2017). Oracle inequalities for network models and sparse graphon estimation. Annals of Statistics, 45 (1), 316-354. DOI : 10.1214/16-aos1454 Proof of Lemma 4.4. Let C be a maximal subset C 0 of points u such that the corresponding A u are k/4separated with respect to the measure of symmetric difference distance. By maximality of C, the union of all balls in the Hamming distance centered at u ∈ C with radii k/4 covers C 0 . Denoting by B[u, k/4] such a ball, we obtain by a volumetric argument |B[u, k/4]|/|C 0 | ≥ |C| -1 .(51)If we endow C 0 with the uniform probability, then|B[u, k/4]| |C 0 | -1 is the probability to draw a point from B[u, k/4]. Note that a point v is in B[u, k/4] if |A v \ A u | ≤ k/8.One can construct the set A v doing k/2 sampling without replacement from the set [k]. We call an a ∈ [k] a success if a ∈ A u . There are k/2 of them. Let S k denotes the number of success, then S k follows an hypergeometric distribution with parameters Now we only have to bound the deviations of S k . It follows from [1, p.173] that S k has the same distribution as the random variable E[η|B] where η is a binomial random variable with parameters (k/2, 1/2) and B is some suitable σ-algebra. Thus, by a convexity argument, we obtain that, for any λ > 0,

	(k, k/2, k/2) and we have
	|B[u, k/4]| |C 0 |	= P[S k ≥ 3k/8] .

3 ,

 3 Comment citer ce document : Klopp, O., Tsybakov, A. B., Verzelen, N. (2017). Oracle inequalities for network models and sparse graphon estimation. Annals of Statistics, 45 (1), 316-354. DOI : 10.1214/16-aos1454 where last inequality uses that |v a | ≤ ǫ ≤ 1/(4k), and |u av a | ≤ 2ǫ. Combining this with (54) proves the lemma.

  Klopp, O., Tsybakov, A. B., Verzelen, N. (2017). Oracle inequalities for network models and sparse graphon estimation. Annals of Statistics, 45 (1), 316-354. DOI : 10.1214/16-aos1454 Proof of Lemma 4.6. Define the pseudo-distance d Π on C 0 by d Π (B 1 , B 2 ) := min π,π ′ B 1 -B π,π ′ 2 F , where the minimum is taken over all permutations of [k]. Let C be a maximal subset C 0 of matrices B that are k(k + 1)/2-separated with respect to d Π . By maximality of C, the union of all balls in d Π distance centered at B ∈ C with radii k(k + 1)/2 covers C 0 . Denoting by B[B, k(k + 1)/2, d Π ] such a ball, we obtain by a volumetric argument B[B, k(k + 1)/2, d Π ] /|C 0 | ≥ |C| -1 . Since d Π (B 1 , B 2 ) is the infimum over all k! 2 permutations of the distance B 1 -B π,π ′ • F ] is the ball centered at B with respect to the Frobenius distance. Given B 1 and B 2 in C 0 , B 1 -B 2 2 F /4 is equal to the Hamming distance between B 1 and B 2 . Consider the ball B[B, k(k + 1)/8, d H ] centered at B with respect to the Hamming distance. As matrices in C 0 are symmetric, C 0 is in bijection with {0, 1} k(k+1)/2 . Using Hamming bound and Varshamov-Gilbert lemma [15, Chapter 2] we obtain 2

	2	F , we have
	B[B, k(k + 1)/2, d Π ] ≤ k! 2 B[B, k(k + 1)/2, . F ] ,
	where B[B, k(k + 1)/2,

  1) Aawhere the sums in a are over [k] n and the sum in A is over all triangular upper halves of matrices in {0, 1} n×n . Since the function (x, y) → x log(x/y) is convex we can apply Jensen's inequality to get K(P WB 1 , P WB 2 ) ≤

			Aa log	a α a p a α a p	(1) Aa (2)
	a	α a	A	p	(1) Aa log	p p	(1) Aa (2) Aa

  ρ n W 2 ) min(d P W1 , d P W2 ) ≥ δ 2 (ρ n W 1 , ρ n W 2 ) 4 min(d P W1 , d P W2 )

	≥	ρ 2 n ǫ 2 8	exp -χ 2 (P W2 , P W1 )	(61)

In some recent papers, it is also called the inhomogeneous Erdös-Rényi model, which is somewhat ambiguous since the words "Erdös-Rényi model" designate a homogeneous graph.

Acknowledgement The work of O. Klopp was conducted as part of the project Labex MME-DII (ANR11-LBX-0023-01). The work of A.B. Tsybakov was supported by GENES and by the French National Research Agency (ANR) under the grants IPANEMA (ANR-13-BSH1-0004-02), and Labex ECODEC (ANR -11-LABEX-0047). The work of N. Verzelen was partly supported by the ANR under the grant ANR-2011-BS01-010-01, project Calibration. This research benefited from the support of the "Chaire Economie et Gestion des Nouvelles Données", under the auspices of Institut Louis Bachelier, Havas-Media and Paris-Dauphine.

Comment citer ce document : Klopp, O., Tsybakov, A. B., Verzelen, N. (2017). Oracle inequalities for network models and sparse graphon estimation. Annals of Statistics, 45 [START_REF] Aldous | Exchangeability and related topics[END_REF], 316-354. DOI : 10.1214/16-aos1454

We first consider k which is a multiple of 16. The case k = 2 is sketched afterwards.

The proof follows the general scheme of reduction to testing of finite number of hypotheses (cf., e.g., [START_REF] Alexandre | Introduction to nonparametric estimation[END_REF]). The main difficulty is to obtain the necessary lower bound for the distance δ(•, •) between the graphons generating the hypotheses since this distance is defined as a minimum over all measure-preserving bijections. We start by constructing a matrix B from which the step-function graphons will be derived. Lemma 4.2. Fix η 0 = 1/16 and assume that k is a multiple of 16 and is greater than some constant. There exists a k × k symmetric {-1, 1} matrix B satisfying the following two properties.

• For any (a, b) ∈ [k] with a = b, the inner product between the two columns B a,• , B b,• satisfies

• For any two subsets X and

Note that any Hadamard matrix satisfies condition (46) since its columns are orthogonal. Unfortunately, the second condition (47) seems difficult to check for such matrices. This is why we adopt a probabilistic approach in the proof of this lemma showing that, with positive probability, a symmetric matrix with independent Rademacher entries satisfies the above conditions.

The graphon "hypotheses" that we consider in this proof are generated by the matrix of connection probabilities Q := (J + B)/2 where B is a matrix from Lemma 4.2 and J is a k × k matrix with all entries equal to 1.

Fix some ǫ < 1/(4k). Denote by C 0 the collection of vectors u ∈ {-ǫ, ǫ} k satisfying k a=1 u a = 0. For any u ∈ C 0 , define the cumulative distribution F u on {0, . . . , k} by the relations F u (0) = 0 and

) and define the graphon

The graphon W u is slightly unbalanced as the weight of each class is either 1/kǫ or 1/k + ǫ.

Let P Wu denote the distribution of observations A ′ := (A ij , 1 ≤ j < i ≤ n) sampled according to the sparse graphon model [START_REF] Peter | A nonparametric view of network models and newman-girvan and other modularities[END_REF] with W 0 = W u . Since the matrix Q is fixed the difficulty in distinguishing between the distributions P Wu and P Wv for u = v comes from the randomness of the design points ξ 1 , . . . , ξ n in the graphon model (2) rather than from the randomness of the realization of A ′ conditionally on ξ 1 , . . . , ξ n . The following lemma gives a bound on the Kullback-Leibler divergences K(P Wu , P Wv ) between P Wu and P Wv .

Technical lemmas

Lemma 4.10. Let X 1 , . . . , X n be i.i.d. uniformly distributed variables on [0, 1] and X (i) is the ith element of the ordered sample X

Proof. Note that X (i) -X (i+s) ∼ Beta(s, ns + 1). For Y ∼ Beta(β, γ) we have

which implies the lemma.

Proof of Lemma 4.1. Since T ∞ ≤ 2r, the definition of q max and the fact that T F ≥ r imply ǫ 0 ≤ T F ≤ ǫ qmax . Denote by q the integer such that 2 -1 ǫ q ≤ T F < ǫ q . Let V 0 be a matrix minimizing T / T F -V F over all V in C ẑr . Then, take V = V q, Û ,ẑr

where Û is a minimizer of T -V q,U ,ẑr 0 F over all U ∈ {-1, 0, 1} k×k . Notice that Û is also a minimizer of T -V q,U ,ẑr 0 ∞ over all U ∈ {-1, 0, 1} k×k since both T and V q,U ,ẑr 0 are block-constant matrices with the same block structure determined by ẑr . Denoting by 0 the zero k × k matrix we have

Next, since V = V q, Û ,ẑr

where U * is the matrix with elements defined by the relation U * ab = sign( T ij ) if i ∈ ẑ-1 r (a), j ∈ ẑ-1 r (b) for (a, b) ∈ [k] × [k]. Thus, all the entries of V q,U * ,ẑr 0 in each block are either equal to r or to -r depending on whether the value of T on this block is positive or negative respectively. Since T ∞ ≤ 2r we obtain that T -V q,U * ,ẑr 0 ∞ ≤ r.