Emmanuel Pilliat

Alexandra Carpentier

Nicolas Verzelen

Optimal rates for ranking a permuted isotonic matrix in polynomial time

. As a byproduct, our procedure is used to improve the state-of-the art for ranking problems in the stochastically transitive model (SST). Our approach is based on iterative pairwise comparisons by suitable data-driven weighted means of the columns. These weights are built using a combination of spectral methods with new dimension-reduction techniques. In order to deal with the important case of missing data, we establish a new concentration inequality for sparse and centered rectangular Wishart-type matrices.

Introduction

Ranking problems have recently spurred a lot of interest in the statistical and computer science literature. This includes a variety of problems ranging from ranking experts/workers in crowdsourced data, ranking players in a tournament or equivalently sorting objects based on pairwise comparisons.

To fix ideas, let us consider a problem where we have noisy partial observations from an unknown matrix M ∈ [0, 1] n×d . In crowdsourcing problems, n stands for the number of experts (or workers), d stands for the number of questions (or tasks) and M i,k for the probability that expert i answers question k correctly. For tournament problems, we have n = d players (or objects) and M i,k stands for the probability that player i wins against player k. Based on these noisy data, the general goal is to provide a full ranking of the experts or of the players.

Originally, these problems were tackled using parametric model for the matrix M . Notably, this includes the noisy sorting model [START_REF] Braverman | Noisy sorting without resampling[END_REF] or Bradley-Luce-Terry model [START_REF] Bradley | Rank analysis of incomplete block designs: I. the method of paired comparisons[END_REF]. Still, it has been observed that these simple models are often unrealistic and do not tend to fit well.

This has spurred a recent line of literature where strong parametric assumptions are replaced by non-parametric assumptions [START_REF] Shah | Estimation from pairwise comparisons: Sharp minimax bounds with topology dependence[END_REF][START_REF] Shah | Stochastically transitive models for pairwise comparisons: Statistical and computational issues[END_REF][START_REF] Shah | Feeling the bern: Adaptive estimators for bernoulli probabilities of pairwise comparisons[END_REF][START_REF] Shah | A permutation-based model for crowd labeling: Optimal estimation and robustness[END_REF][START_REF] Mao | Towards optimal estimation of bivariate isotonic matrices with unknown permutations[END_REF][START_REF] Mao | Breaking the 1 √ n barrier: Faster rates for permutation-based models in polynomial time[END_REF][START_REF] Liu | Better algorithms for estimating non-parametric models in crowdsourcing and rank aggregation[END_REF][START_REF] Flammarion | Optimal rates of statistical seriation[END_REF][START_REF] Bengs | Preference-based online learning with dueling bandits: A survey[END_REF][START_REF] Saad | Active ranking of experts based on their performances in many tasks[END_REF]. In particular, for tournament problems, the strong stochastically transitive (SST) model presumes that the square matrix M is, up to a common permutation π * of the rows and of the columns, bi-isotonic and satisfies the skew symmetry condition M i,k + M k,i = 1. Although optimal rates for estimation of the permutation π * have been pinpointed in the earlier paper of Shah et al. [START_REF] Shah | Stochastically transitive models for pairwise comparisons: Statistical and computational issues[END_REF], there remains a large gap between these optimal rates and the best known performances of polynomial-time algorithms. This has led to conjecture the existence of a statistical-computational gap [START_REF] Mao | Towards optimal estimation of bivariate isotonic matrices with unknown permutations[END_REF][START_REF] Liu | Better algorithms for estimating non-parametric models in crowdsourcing and rank aggregation[END_REF].

For crowdsourcing data, the counterpart of the SST model is the so-called bi-isotonic model, where the rectangular matrix M is bi-isotonic, up to an unknown permutation π * of its rows and an unknown permutation η * of its columns. This model turns out to be really similar to the SST model and the existence of a statistical-computational gap has also been conjectured [START_REF] Mao | Towards optimal estimation of bivariate isotonic matrices with unknown permutations[END_REF].

In this paper, we tackle a slightly different route and we consider the arguably more general isotonic model [START_REF] Flammarion | Optimal rates of statistical seriation[END_REF]. The only assumption is that all the columns of M are nondecreasing up to an unknown permutation of the rows, making the isotonic model more flexible than the bi-isotonic and SST models. It is in fact the most general model under which an unambiguous ranking of the experts is well-defined. In this model as well, there is a gap between the (statistical) optimal rates, and the rate obtained by the (polynomial-time) algorithm in [START_REF] Flammarion | Optimal rates of statistical seriation[END_REF].

Our main contributions are as follows. For the isotonic model, we establish the optimal rate for recovering the permutation, and we introduce a polynomial-time procedure achieving this rate, thereby settling the absence of any computational gap in this model. Besides, our procedure and results have important consequences when applied to the SST and bi-isotonic model. More specifically, we achieve the best known guarantees in these two models [START_REF] Liu | Better algorithms for estimating non-parametric models in crowdsourcing and rank aggregation[END_REF][START_REF] Mao | Breaking the 1 √ n barrier: Faster rates for permutation-based models in polynomial time[END_REF] and even improve them in some regimes.

Problem formulation

Let us further introduce our model. A bounded matrix A ∈ [0, 1] n×d is said to be isotonic if its columns are nondecreasing, that is A i,k ≤ A i+1,k for any i ∈ [n -1] and k ∈ [d]. Henceforth, we write C iso for the collection of all n × d isotonic matrices taking values in [0, 1]. In our model, we recall that we assume that the signal matrix M is isotonic up to an unknown permutation of its rows. In other words, there exists a permutation π * of [n] such that the matrix M π * -1 defined by (M π * -1 ) i,k = (M π * -1 (i),k ) has nondecreasing columns, that is

M π * -1 (i),k ≤ M π * -1 (i+1),k , (1)
for any i ∈ {1, . . . , n -1} and k ∈ {1, . . . , d}, or equivalently M π * -1 ∈ C iso . Henceforth, π * is called an oracle permutation. Using the terminology of crowdsourcing, we refer to i th row of M as expert i and to k th column as question k.

In this work, we have N partial and noisy observations of the matrix M of the form (x t , y t ) where y t = M xt + ε t t = 1, . . . , N .

For each t, the position x t ∈ [n] × [d] is sampled uniformly. The noise variables ε t 's are independent and their distributions only depend on the position x t . We only assume that all these distributions are centered and are subGaussian with a subGaussian norm of at most 1 -see e.g. [START_REF] Wainwright | High-dimensional statistics: A non-asymptotic viewpoint[END_REF]. In particular, this encompasses the typical case where the y t 's follow Bernoulli distributions with parameters M xt .

As usual in the literature e.g. [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF][START_REF] Liu | Better algorithms for estimating non-parametric models in crowdsourcing and rank aggregation[END_REF][START_REF] Mao | Towards optimal estimation of bivariate isotonic matrices with unknown permutations[END_REF], we use, for technical convenience, the Poissonization trick which amounts to assuming that the number N of observations has been sampled according to a Poisson distribution with parameter λnd. We refer to λ > 0 as the sampling effort. When λ > 1, we have, in expectation, several independent observations per entry (i, j) -and λ = 1 means that there is on average one observation per entry. In this paper, we are especially interested in the sparse case where λ is much smaller than one, i.e. the case where we have missing observations for some entries. We refer to λ = 1 as the full observation regime at it bears some similarity to the case often considered in the literature -e.g. [START_REF] Shah | Stochastically transitive models for pairwise comparisons: Statistical and computational issues[END_REF][START_REF] Flammarion | Optimal rates of statistical seriation[END_REF], where we have a full observation of the matrix,

Y = M + E ′ ∈ R n×d . ( 3
)
The entries of the noise matrix E ′ are independent, centered, and 1-subGaussian.

In this work, we are primarily interested in estimating the permutation π * . Given an estimator π, we use the square Frobenius norm M π-1 -M π * -1 2 F as the loss. This loss quantifies the distance between the matrix M reordered according to the estimator π and the matrix M sorted according to the oracle permutation π * . This loss is explicitly used in [START_REF] Liu | Better algorithms for estimating non-parametric models in crowdsourcing and rank aggregation[END_REF][START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF] and is implicit in earlier works -see e.g. [START_REF] Shah | Stochastically transitive models for pairwise comparisons: Statistical and computational issues[END_REF].

We define the associated optimal risk of permutation recovery as a function of the number n of experts, the number d of question and the sampling effort λ,

R * perm (n, d, λ) = inf π sup π * ∈Πn M ∶ M π * -1 ∈C iso E (π * ,M ) [ M π-1 -M π * -1 2 F ] , (4)
where the infimum is taken over all estimators. Here, Π n stands for the collection of all permutations of [n]. If the main focus is not only to estimate π * , but also to reconstruct the unknown matrix M , we also consider the optimal reconstruction rate

R * reco (n, d, λ) = inf M sup π * ∈Πn M ∶ M π * -1 ∈C iso E M -M 2 F . (5)
It turns out that reconstructing the matrix M is more challenging than estimating the permutation π * . Considering both risks allows to disentangle the reconstruction of the matrix M : looking at both enables to distinguish the error that is due to estimating the permutation, from the error that comes from estimating an isotonic matrix.

Past results on the isotonic model and our contributions

In, the specific case where d = 1 (a single column), our model is equivalent to uncoupled isotonic regression and is motivated by optimal transport. Rigollet and Niles-Weed [START_REF] Rigollet | Uncoupled isotonic regression via minimum wasserstein deconvolution. Information and Inference[END_REF] have established that the reconstruction error of M is of the order of n( log log(n) log(n) ) 2 . For the general case d ≥ 1, Flammarion et al. [START_REF] Flammarion | Optimal rates of statistical seriation[END_REF] have shown 1 that the optimal reconstruction error in the full observation model ( 3) is of the order of n 1 3 d + n. However, the corresponding procedure is not efficient. They also introduce an efficient procedure that first estimates π * using a score based on row comparisons on Y . Unfortunately, this method only achieves a reconstruction error of the order of n 1 3 d + n √ d which is significantly slower than the optimal one. Whether or not there is a statistical-computationnal gap was therefore an open problem.

We prove in this work that there is no computational statistical gap in this model. More precisely, we introduce estimators that are both polynomial-time and minimax optimal up to some polylog factors. To that end, we characterize the optimal risks R * perm (n, d, λ) and R * reco (n, d, λ) of permutation estimation and matrix reconstruction, for all possible number of experts n ≥ 1, number of questions d ≥ 1 and all sampling efforts λ, up to some polylog factors in nd. Table 1 summarizes our findings in the arguably most interesting cases 2 λ ∈ [1 (n∧d), 1].

n ≤ d 3 2 √ λ d 3 2 √ λ ≤ n R * perm n 2 3 √ dλ -5 6 n λ R * reco n 1 3 dλ -2 3 n λ , Table 1
Optimal rates in our model, for all possible values of n, d and λ ∈ [1 (n ∧ d), 1], up to a polylogarithmic factor in nd. These rates are achieved by polynomial-time estimators.

Implication for other models and connection to the literature

As discussed earlier, the isotonic model is quite general and encompasses both the bi-isotonic model for crowdsourcing problems as well the SST model for tournament problems.

Let us first focus on the SST model which corresponds to the case where n = d together with a bi-isotonicity and a skew-symmetry assumption. In the full observation scheme (related to the case λ = 1) where one observes the noisy matrix n × n, Shah et al. [START_REF] Shah | Stochastically transitive models for pairwise comparisons: Statistical and computational issues[END_REF] have established that the optimal rates for estimating π * and reconstructing the matrix M are of the order of n. In contrast, their efficient procedure which estimates π * according to the row sums of Y only achieves the rate of n 3 2 . In more recent years, there has been a lot of effort dedicated to improving this √ n statistical-computational gap. The SST model was also generalized to partial observations by [START_REF] Chatterjee | Estimation in tournaments and graphs under monotonicity constraints[END_REF], which corresponds to λ ≤ 1. They introduced an efficient procedure that targets a specific sub-class of the SST model, and that achieves a rate of order n 3 2 λ -1 2 in the worst case for matrix reconstruction.

Recently, a few important contributions tackling both the bi-isotonic model and the SST model made important steps towards better understanding the statistical-computational gap. We first explain how their results translate in the SST model. Mao et al. [START_REF] Mao | Towards optimal estimation of bivariate isotonic matrices with unknown permutations[END_REF][START_REF] Mao | Breaking the 1 √ n barrier: Faster rates for permutation-based models in polynomial time[END_REF] introduced a polynomial-time procedure handling partial observation, achieving a rate of order n 5 4 λ -3 4 for matrix reconstruction. Nonetheless, [START_REF] Mao | Towards optimal estimation of bivariate isotonic matrices with unknown permutations[END_REF] failed to exploit global information shared between the players/experts -as they only compare players/experts two by two -as pointed out by [START_REF] Liu | Better algorithms for estimating non-parametric models in crowdsourcing and rank aggregation[END_REF]. Building upon this remark, [START_REF] Liu | Better algorithms for estimating non-parametric models in crowdsourcing and rank aggregation[END_REF] managed to get the better rate n 7 6+o (1) with a polynomial-time method in the case λ = n o (1) .

Let us turn to the more general bi-isotonic model. Here, the rectangular matrix M ∈ R n×d is bi-isotonic up an unknown permutation π * of the rows and an unknown permutation η * of the columns. Since M is not necessarily square, this model can be used in more general crowdsourcing problems. The optimal rate for reconstruction in this model with partial observation has been established in [START_REF] Mao | Towards optimal estimation of bivariate isotonic matrices with unknown permutations[END_REF] to be of order ν(n, d, λ) ∶= (n ∨ d) λ + nd λ ∧ n 1 3 dλ -2 3 ∧ d 1 3 nλ -2 3 up to polylog factors, in the non-trivial regime where λ ∈ [1 (n ∧ d), 1]. However, the polynomial-time estimator provided by Mao et al. [START_REF] Mao | Towards optimal estimation of bivariate isotonic matrices with unknown permutations[END_REF] only achieves the rate n 5 4 λ -3 4 + ν(λ, n, d). In a nutshell, Mao et al. first compute column sums to give a first estimator of the permutation of the questions. Then, they compare the experts on aggregated blocks of questions, and finally compare the questions on aggregated blocks of experts. As explained in the previous paragraph for SST models, Liu and Moitra [START_REF] Liu | Better algorithms for estimating non-parametric models in crowdsourcing and rank aggregation[END_REF] improved this rate to n 7 6+o (1) in the square case (n = d), with a subpolynomial number of observations per entry (λ = n o (1) ). Their estimators of the permutations π * , η * were based on hierarchical clustering and on local aggregation of high variation areas. Both [START_REF] Liu | Better algorithms for estimating non-parametric models in crowdsourcing and rank aggregation[END_REF][START_REF] Mao | Towards optimal estimation of bivariate isotonic matrices with unknown permutations[END_REF] made heavily use of the bi-isotonicity structure of M by alternatively sorting the columns and rows. As mentioned for the SST model, the order of magnitude n 7 6+o (1) remains nevertheless suboptimal, and whether there exists an efficient algorithm achieving the optimal rate in this bi-isotonic model remains an open problem.

We now discuss the implications of our work concerning the bi-isotonic model and SST model. First, in the full observation setting (λ = 1) and square case for the bi-isotonic model (n = d), we reach in polynomial-time the upper bound n 7 6 up to polylog factors, for both permutation estimation and matrix reconstruction. In particular, we improve the rate in [START_REF] Liu | Better algorithms for estimating non-parametric models in crowdsourcing and rank aggregation[END_REF] by a subpolynomial factor in n, and we do not need a subpolynomial number of observation per entry. Moreover, our procedure being primarily designed for the isotonic model, it does not require any shape constraint on the rows in contrast to [START_REF] Liu | Better algorithms for estimating non-parametric models in crowdsourcing and rank aggregation[END_REF][START_REF] Mao | Towards optimal estimation of bivariate isotonic matrices with unknown permutations[END_REF]. Beyond the full observation regimes, we provide guarantees on our estimator of π * for different values of λ. In particular, in Corollary 2.5, we derive an estimator of the matrix M that achieves a maximum reconstruction risk

sup π * ,η * ,M E M -M π * -1 η * -1 2
F of order less than n 7 6 λ -5 6 up to polylogs, thereby improving the state-of-the-art polynomial-time methods in partial observation [START_REF] Mao | Towards optimal estimation of bivariate isotonic matrices with unknown permutations[END_REF]. Lastly, we perform our analysis in the general rectangular case, giving guarantees for general values of d.

The optimal risks and the known polynomial-time upper bounds for the isotonic, bi-isotonic with two permutations and SST models are summarized in Table 2. For the sake of simplicity, we focus in the table to the specific case case n = d and λ ∈

[1 n, 1]. Different models, with M ∈ R n×n Isotonic Bi-isotonic(π * , η * ) SST M π * -1 has nondecreasing columns M π * -1 η * -1 has nondecreasing columns
and rows

M π * -1 π * -1 has nondecreasing columns
and rows, and

M ik + M ki = 1

Permutation estimation

Poly. Time

n 7 6 λ -5 6 [Th 2.2] n 7 6+o(1) [8](λ = n o(1) ) n 7 6 λ -5 6 [Th 2.2] n 7 6+o(1) [8](λ = n o(1) ) n 7 6 λ -5 6 [Th 2.2]
optimal rate

n 7 6 λ -5 6 [Th 2.1] n λ [10] n λ [10]

Matrix reconstruction

Poly. Time

n 3 2 (λ = 1)[7] n 4 3 λ -2 3 [Cor 2.5] n 7 6+o(1) [8](λ = n o(1) ) n 5 4 λ -3 4 [10] n 7 6 λ -5 6
[Cor 2.5]

n 7 6+o(1) [8](λ = n o(1) ) n 5 4 λ -3 4 [10] n 7 6 λ -5 6 [Cor 2.5] optimal rate n 4 3 λ -2 3 [7] (also [Prop 2.3]) n λ [10] n λ [10]
Table 2 For the isotonic model, the optimal rate for permutation estimation (resp. matrix reconstruction) corresponds to R * perm (resp. R * reco ). For the two other columns, the optimal rates are similarly defined as minimax risk over the corresponding models. The Poly. Time rows correspond to state-of-the art rates achieved by polynomial-time methods. All the rates are given up to polylogarithmic factors in n.

Finally, we mention the even more specific model where the matrix M is bi-isotonic up to a single permutation π * acting on the rows. This corresponds to the case where η * is known in the previous paragraph [START_REF] Mao | Towards optimal estimation of bivariate isotonic matrices with unknown permutations[END_REF][START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF][START_REF] Liu | Better algorithms for estimating non-parametric models in crowdsourcing and rank aggregation[END_REF]. Equivalently, this also corresponds to our isotonic model [START_REF] Bellec | Concentration of quadratic forms under a bernstein moment assumption[END_REF] with the additional assumption that all the rows are nondecreasing, that is M i,k ≤ M i,k+1 . For this model, it is possible to leverage the shape constrains on the rows to build efficient and optimal estimators, this for all n, d, and λ -see [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF].

Overview of our techniques

In this work, we introduce the iterative soft ranking (ISR) procedure, which gives an estimator π based on the observations. Informally, this method iteratively updates a weighted directed graph between experts, where the weight between any two experts quantifies the significance of their comparison. The procedure increases the weights at each step. After it stops, the final estimator is an arbitrary permutation π that agrees as well as possible with the final weighted directed graph.

As mentioned in [START_REF] Liu | Better algorithms for estimating non-parametric models in crowdsourcing and rank aggregation[END_REF], it is hopeless to use only local information between pairs of experts to obtain a rate of order n 7 6 up to polylogs, and we must exploit global information. Still, we do it in a completely different way of Liu and Moitra [START_REF] Liu | Better algorithms for estimating non-parametric models in crowdsourcing and rank aggregation[END_REF] who were building upon the bi-isotonicity of the matrix.

One first main ingredient of our procedure is a new dimension reduction technique. At a high level, suppose that we have partially ranked the rows in such a way that, for a given triplet (P , O, I) of subsets of [n], we are already quite confident that experts in P are below those in I and above those in O. Relying on the shape constraint of the matrix M , it is therefore possible to build a high-probability confidence regions for rows in P based on the rows in O and the rows in I. If, for a question j, the confidence region is really narrow, this implies that all experts in P take almost the same value on this column. As a consequence, this question is almost irrelevant for further comparing the experts in P . In summary, our dimension reduction technique selects the set of questions for which the confidence region of P is wide enough, and in that way reduces the dimension of the problem while keeping most of the relevant information.

The second main ingredient, once the dimension is reduced, is to use a spectral method to capture some global information shared between experts. That is why our procedure makes significant use of spectral methods to compute the updates of the weighted graph. Although this spectral scheme already appears in recent works [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF][START_REF] Liu | Better algorithms for estimating non-parametric models in crowdsourcing and rank aggregation[END_REF], those are used here for updating the weight of the comparison graph rather than performing a clustering as in [START_REF] Liu | Better algorithms for estimating non-parametric models in crowdsourcing and rank aggregation[END_REF]. Moreover, the analysis of the spectral step in the partial observation regime (λ ≪ 1) leads to technical difficulties -see the discussion in Section 3.5.

Related to the latter problem, we need to establish a new tail bound on sparse rectangular matrices. More specifically, for a rectangular matrix X with centered independent entries that satisfy a Bernstein type condition, we provide a high-probability control of the operator norm of XX T -E[XX T ]. This result, based on non-commutative matrix Bernstein concentration inequality, may be of independent interest e.g. for controlling the spectral properties of a sparse bipartite random graph. We state it in Section 4, independently of the rest of the paper.

Notation

Given a vector u and p ∈ [1, ∞], we write u p for its l p norm. For a matrix A, A F and A op stand for its Frobenius and its operator norm. We write ⌊x⌋ (resp. ⌈x⌉) for the largest (resp. smallest) integer smaller than (resp. larger than) or equal to x. Although M stands for an n × d matrix, we extend it sometimes in an infinite matrix defined for all i ∈ N, k ∈ {1, . . . , d} by setting M ik = 0 when i ≤ 0 and M ik = 1 when i ≥ n + 1. The corresponding infinite matrix M π * (-1) which is obtained by permuting the n original rows is still isotonic and takes values in [0, 1]. We shall often work with submatrices M (P, Q) of M that are restricted to a subset P ⊂ [n] and Q ⊂ [d] of rows and columns. If A is any matrix in R P ×Q , we write A for the matrix whose rows are all equal to the average row of A, namely A ik = 1 P ∑ j∈P A jk .

Results

In this section, we first establish the statistical limit with a lower bound on R * perm (n, d, λ). Then, we state the existence of a polynomial-time estimator that is minimax optimal up to polylog factors. More precisely, we prove that for all integers n, d and λ ∈ [1 d, 8n 2 ], the optimal rate of permutation estimation R * perm is of the order of

ρ perm (n, d, λ) ∶= n 2 3 √ d λ 5 6 ⋀ n d λ + n λ , (6)
up to some polylog factors. As a corollary, we then establish that the optimal rate of matrix reconstruction R * reco is of order

ρ reco (n, d, λ) ∶= n 1 3 d λ 2 3 + n λ , (7)
up to polylog factors. We therefore establish that these two problems do not exhibit a computationalstatistical gap.

In the proof, we show a slightly stronger result that also covers the cases λ < 1 d and λ > 8n 2 , where R * perm (n, d, λ) is in fact respectively lower bounded by a quantity of order nd and n √ d λ. For the sake of readability, we chose to omit these arguably less interesting cases in the statement of Theorem 2.1 and of Theorem 2.2.

Optimal permutation estimation

Let us fix a quantity δ ∈ (0, 1) that will correspond to a small probability. We need to introduce some notation. We write

φ L 1 = 10 4 log 10 2 nd δ . (9)
Our procedure depends on a sequence of tuning parameters. For this reason, we introduce a subset Γ ⊂ R + , henceforth called a grid. The grid Γ is said to be valid if it contains a sequence

γ 0 ≥ ⋅ ⋅ ⋅ ≥ γ 2⌊log 2 (n)⌋+2 of length 2 ⌊log 2 (n)⌋ + 3 such that that for all u, γ u -γ u+1 ≥ γ 2⌊log 2 (n)⌋+2 + φ L 1 and γ 2⌊log 2 (n)⌋+2 ≥ φ L 1 . (10)
In light of this definition, we could simply choose the valid sequence Γ = {φ L 1 , 2φ L 1 , . . . , (2 ⌊log 2 (n)⌋+ 3)φ L 1 } with a corresponding γ 0 that is polylogarithmic. Still, for practical purpose, we consider general grids; examples of such gris are discussed in more details in Section 3.6.

For any valid subset Γ, we define γ as the smallest possible value of γ 0 over all sequences that satisfy [START_REF] Mao | Towards optimal estimation of bivariate isotonic matrices with unknown permutations[END_REF].

γ = min{γ ∶ ∃(γ u ) satisfying (10) s.t. γ 0 = γ} . (11)
Our main procedure ISR, for iterative soft ranking, will be described in detail in Section 3. The only tuning parameters are the the number of steps T and the valid grid Γ. Theorem 2.2. There exists C > 0 such that the following holds. Let λ ∈ [1 d, 8n 2 ] and δ > 0. Assume that Γ is a valid grid and that T ≥ 4γ 6 with γ defined in [START_REF] Massart | Concentration inequalities and model selection[END_REF]. For any permutation π * ∈ Π n and any matrix M such that M π * -1 ∈ C iso , the estimator π from Algorithm ISR(T, Γ) defined in the next section satisfies

M π-1 -M π * -1 2 F ≤ CT γ6 ρ perm (n, d, λ) ,
with probability at least 1 -10T δ.

In particular, if we suitably choose Γ (as discussed above) and T = 4⌈γ 6 ⌉ and δ = 1 (nd) 2 , we deduce from Theorem 2.2 that

R * perm (n, d, λ) ≤ C ′ log C ′ (nd)ρ perm (n, d, λ) ,
for some numerical constant C ′ > 0. In the case where λ = n o (1) and n = d, this bound achieves the order of magnitude n 7 6 , which aligns with the result presented in Theorem 2 of Liu and Moitra [START_REF] Liu | Better algorithms for estimating non-parametric models in crowdsourcing and rank aggregation[END_REF]. However, it is important to note that the analysis made in [START_REF] Liu | Better algorithms for estimating non-parametric models in crowdsourcing and rank aggregation[END_REF] focuses on the statistically easier bi-isotonic model, and their procedure heavily relies on the isotonicity structure imposed on the questions.

Optimal reconstruction of the matrix M

We now turn to the problem of estimating the signal matrix M . Obviously, the reconstruction of the matrix M from the observation of model in(2) is at least as hard as if we knew the permutation π * . In this favorable situation, estimating M amounts to estimating d isotonic vectors from partial and noisy observations Y ik = 1 λ ∑ t y t 1 xt=(ik) . The isotonic regression problem is already well understood, and we state the following lower bound without proof since it directly follows from [START_REF] Mao | Towards optimal estimation of bivariate isotonic matrices with unknown permutations[END_REF] (see in particular Theorem 3.1 therein). We recall that ρ reco (n, d, λ) is defined in [START_REF] Flammarion | Optimal rates of statistical seriation[END_REF].

Proposition 2.3. There exists a universal constant c > 0 such that, for any n ≥ 2, any d ≥ 1, and any λ > 0, we have

R * reco (n, d, λ) ≥ cρ reco (n, d, λ) . (12)
In particular, since ρ perm (n, d, λ) ≪ ρ reco (n, d, λ) in many regimes in n, d, λ, this proposition implies that the reconstruction of a permuted isotonic matrix is harder than the estimation of the permutation, namely that R * perm ≪ R * reco . To build an optimal estimator of M , we compute the estimated permutation π of Theorem 2.2 and estimate an isotononic matrix based on this ordering. This approach is similar to what is done in [START_REF] Mao | Towards optimal estimation of bivariate isotonic matrices with unknown permutations[END_REF][START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF], for related problems where a bi-isotonic assumption is done. For simplicity, set the tuning parameters T , Γ for Algorithm 1 so that T = 4 ⌈γ 6 ⌉ and γ6 ≤ C ′ log C ′ (nd δ). We split the samples y t defined in (2) into two independent sequences of samples (y

t ), (y

t ). First, we compute the estimator π of π * with the first sub-samples (y (1) t ). Then, we define Miso as the projection of Y (2) π onto the convex set of isotonic matrices, where Y (2) is the matrix

defined by Y (2) ik = 1 λ ∑ t y (2) t 1 x (2) t =(i,k) . More precisely, set Miso = arg min M ∈C iso M -Y (2) π-1 2 2 .
The following corollary controls the risk of Miso .

Corollary 2.4. Assume that λ ∈ [1 d, 8n 2 ].
There exists a universal constant C ′′ such that the following holds for any permutation π * ∈ Π n and any matrix M ∈ C iso .

E[ ( Miso ) π -M 2 F ] ≤ C ′′ log C ′′ (nd)ρ reco (n, d, λ) .
As a consequence, the polynomial-time estimator Miso achieves the optimal risk for all values of n and d. For λ = 1, the optimal risk ρ reco (n, d, 1) is of the order of n 1 3 d + n. In particular, our risk bound strictly improves over the one of Flammarion et al. [START_REF] Flammarion | Optimal rates of statistical seriation[END_REF] -e.g. their procedure achieves the estimation error n √ d for n ≥ d 1 3 . Their slower convergence rates are mainly due to the fact that their estimator of the permutation π * is suboptimal in this regime.

Polynomial-time reconstruction in the bi-isotonic model

We now turn our attention to the problem of estimating the matrix M when M satisfies the additional assumption of being bi-isotonic up to unknown permutations π * and η * of its rows and columns respectively. In other words, the matrix M π * -1 η * -1 has non-decreasing entries. As explained in the introduction, this model has attracted a lot of attention in the last decade and encompasses the SST model for tournament problems.

To simplify the exposition, we focus in this section on the case n = d and λ ∈ [ 1 n , 1]. Since the bi-isotonic model is a specific case of the isotonic model, we could rely on the estimator M iso introduced in the previous subsection. In fact, we can improve this estimation rate by relying on the bi-isotonicity of the matrix M π * -1 η * -1 .

As previously, we choose the tuning parameters of Algorithm 1 in such a way that T = 4 ⌈γ 6 ⌉ and γ6 ≤ C ′ log C ′ (nd δ). Then, we use the following procedure:

1. Subsample the data into 3 independent samples (y

t ), (y

t ), (y

t ). 2. Run our procedure Algorithm 1 to obtain an estimator π of the permutation π * of the rows, using the first sample. 3. Run again Algorithm 1 to obtain an estimator η of the permutation η * of the columns, using the second sample. 4. Compute the least-square estimator Mbiso = arg min

M∈C biso M -Y (3) π-1 η-1 2 2
, where C biso is the set of all bi-isotonic matrices with entries in [0, 1] and Y

(3) ik = 1 λ ∑ t y (3) t 1 x (3) t =(i,k) .
The following corollary states that Mbiso achieves a reconstruction rate of order n 7 6 λ -5 6 in the bi-isotonic model.

M ∶ M π * -1 η * -1 ∈C biso E ( Mbiso ) π η -M 2 F ≤ C ′′ log C ′′ (n)n 7 6 λ -5 6 .
Here, we have fixed n = d to simplify the exposition but we could extend the analysis to general n and d. Our risk bound improves over the rate n 5 4 λ -3 4 of Mao et al. [START_REF] Mao | Towards optimal estimation of bivariate isotonic matrices with unknown permutations[END_REF]. In [START_REF] Liu | Better algorithms for estimating non-parametric models in crowdsourcing and rank aggregation[END_REF], Liu and Moitra have introduced a procedure achieving the rate n 7 6 in the specific case where λ = n o (1) . In some way, our procedure generalizes their results for general λ, while being applicable to the more general isotonic models.

Still, we recall that the optimal risk (without computational constraints) for estimating the matrix M is of the order n λ -see e.g. [START_REF] Shah | Stochastically transitive models for pairwise comparisons: Statistical and computational issues[END_REF][START_REF] Mao | Towards optimal estimation of bivariate isotonic matrices with unknown permutations[END_REF]. This remains an open problem to establish the existence of a computational-statistical gap or to construct a polynomial-time procedure achieving this risk on SST and bi-isotonic models.

Description of the ISR procedure

Weighted directed graph W and estimator π

Our approach involves the iterative construction of a weighted directed graph W, represented by an antisymmetric matrix in R n×n . More formally, for any experts i, j in [n], we have W(i, j) = -W(j, i). In a nutshell, W(i, j) quantifies our evidence of the comparisons between expert i and expert j. If W(i, j) is large and positive (resp. negative), we are confident that the expert i is above (below) the expert j. Most of the procedure is dedicated to the construction of W. Before this, let us explain how we deduce our estimator π from W.

For a given weighted directed graph W, we define its corresponding directed graph at threshold γ > 0 as

G(W, γ) = {(i, j) ∈ [n] 2 ∶ W(i, j) > γ} . (13)
For any thresholds γ < γ ′ , it holds that G(W, γ) ⊂ G(W, γ ′ ). In other words, the function γ → G(W, γ) is nondecreasing. When γ ≥ max i,j W(i, j) , G(W, γ) = ∅ is the trivial graph with no edges. Let γ be the smallest threshold γ such that G(W, γ) is a directed acyclic graph (DAG). By monotonicity, G(W, γ) is also the largest DAG among {G(W, γ), γ ≥ γ}.

We then build the estimator π by picking any permutation that is consistent with the graph

Ĝ ∶= G(W, γ), that is if (i, j) ∈ Ĝ ∩ [n] 2 then π(i) ≥ π(j).
To put it another way, the general idea of our procedure can be summarized into these three components:

1. Construct a weighted directed graph W between the experts. 2. Compute the largest directed acyclic graph Ĝ of W.

3. Take any arbitrary permutation π that is consistent with Ĝ.

The construction of W is at the core of this paper, and the computation of Ĝ and π will be discussed in Section 3.7. Still, we already point out that the third point can be dealt in polynomial time using Mirsky's algorithm [START_REF] Mirsky | A dual of dilworth's decomposition theorem[END_REF].

Construction of W with ISR

Description of the subsampling

Let us now describe the construction of the weighted directed graph W. Let T ≥ 1 be an arbitrary integer, representing the number of steps of our procedure. In what follows, we explain how we subsample the data from (2) into 5T independent matrices (Y (s) ) s=1...5T . Recall that we are given N observations (x t , y t ), where N follows a Poisson distribution P(λnd). Let us divide the observations into 5T batches (N (s) ) s=0,...,5T -1 , aggregated into matrices of averaged observations Y (s) . To that end, we let S u be i.i.d. uniform random variables in {0, . . . , 5T -1} representing a random batch for observation u and we define

N (s) = {u ∈ {1 . . . , N } ∶ S u = s} and Y (s) ik = t∈N (s) yt r (s) ik ∨1 1{x t = (i, k)} , (14)
where, for any

(i, k) ∈ [n] × [d], r (s)
ik = ∑ t∈N (s) 1{x t = (i, k)} is the number of times the coefficient position (i, k) is observed in batch s. Y (s)
ik is equal to 0 if (i, k) is not observed in batch s and it is equal to the average of the observations y t for which x t = (i, k) otherwise. We also define the mask matrix B (s) as being equal to 0 at location (i, k) if the value is missing from batch s, and to 1 otherwise.

B (s) ik = 1{r (s) ik ≥ 1} . ( 15
)
Define λ 0 = λ 5T . In our sampling scheme, where the data is divided into 5T samples, each coefficient

B (s)
ik has a probability of 1e -λ 0 of being equal to one. It is worth mentioning that a different subsampling scheme was performed in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF], consisting in aggregating consecutive columns. However, such a scheme is not applicable in our case as we do not assume the rows of M to be nondecreasing, unlike in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF].

Neighborhoods in comparison graphs

At each step t = 0, . . . , T -1 of the procedure, we aim to enrich our knowledge of the order of the experts, which we formally do by nondecreasing the weights of W in absolute value.

At T = 0, we start with the weights W ij all being equal to zero. A meaningful update of W around a reference expert i can be done when we restrict ourselves to experts that are in a neighborhood of i. Broadly speaking, a neighborhood of i is a set made of all the experts j that are not comparable to i with respect to a given partial order.

More precisely, for any directed graph G and any experts i, j ∈ {1, . . . , n}, we say that i and j are G-comparable if there is a path from i to j or from j to i in G. The neighborhood N (G, i) of i in G can then naturally be defined as the set of experts j that are not G-comparable with i. Equipped with the concept of neighborhood, our overall strategy involves iterating over all possible thresholds γ ∈ Γ such that G(W, γ) is acyclic, as well as all possible experts i. At each iteration, we apply the soft local ranking procedure Algorithm 2 described in the next subsection. Algorithm 2 updates the weights between i and any expert j in the neighborhood N (G(W, γ), i) of i. Our approach can be summarized as follows:

1. Subsample the data -see Section 3.2.1. 2. Initialize W to be the directed graph with all weights set to 0. 3. For all t = 0, . . . , T -1 and γ ∈ Γ such that G(W, γ) is acyclic and all i ∈ [n], update W with the soft local ranking procedure Algorithm 2.

Algorithm 1 ISR(T, Γ)

Require: N and observations (xt, yt) t=1,...,N according to (2), a number of steps T and a valid grid Γ as in (10) Ensure: A weighted graph W and an estimator π 1: Aggregate the observation into 5T matrices of observation (Y (s) ) as in ( 14) 2: Initialize W(i, j) = 0 for all (i, j) ∈ [n] 2 , and γ = 0 3:

for t = 0, . . . , T -1 do 4: for γ ∈ Γ ∩ [γ, +∞) do 5:
Compute G = G(W, γ) the directed graph at threshold γ of W as in [START_REF] Pananjady | Isotonic regression with unknown permutations: Statistics, computation and adaptation[END_REF] and set P = N (G, i).

6:

Take 5 samples Y = (Y (5t) , . . . , Y (5t+4) ) 7:

for i ∈ [n] do 8:
Apply SLR(Y, W, γ, i, G, P ) to update W 9:

end for 10:

end for 11:

Set γ as the smallest γ such that G(W, γ) is acyclic 12: end for 13: Set Ĝ = G(W, γ) be the largest acyclic DAG (see ( 13)) 14: Set π to be any arbitrary permutation that is consistent with Ĝ 15: return W and π

The main Line 8 of Algorithm 1 aims to provide a soft ranking of the neighborhood P of i by setting positive (resp. negative) weights W ij to experts j ∈ P that are significantly below (resp. above) i. Line 11 together with restricting γ ≥ γ simply guarantees that all the considered graph G are acyclic. Finally, Lines 13 and 14 simply correspond to the construction of the final permutation, described in the second and third points of Section 3.1.

Description of the updating procedure

Local weighted sums

Let us describe the process of updating a given weighted graph W, which will be used twice at each call of the soft local ranking Algorithm 2. Let us fix a weighted graph W, an element s ∈ {0, . . . , 5T -1} and Y ∶= Y (s) the matrix defined in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF]. We also let i ∈ [n] be an arbitrary expert corresponding to Line 7 of Algorithm 1, and γ be any threshold in the grid Γ. We write

P ∶= N (G(W, γ), i) ⊂ [n]
for the neighborhood of i in G(W, γ), echoing the notation of the sets that are trisected in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF].

Since the matrix M is, up to a row-permutation, a column-wise isotonic matrix, it follows that, if the expert i is above j, then for any vector w ∈ R d + , we have ∑ d k=1 w ik M ik ≥ ∑ d k=1 w jk M jk . As a consequence, the crux of the algorithm is to find suitable data-driven weights w that allow to discriminate the experts. As explained in the introduction, earlier works focused on uniform weights w = 1 [d] [START_REF] Shah | Stochastically transitive models for pairwise comparisons: Statistical and computational issues[END_REF] which, unfortunately leads to suboptimal results. Before discussing the choice of the weights w in the following subsections, let us first formalize how we leverage on w to compare the experts and update the graph W.

Given a subset Q ⊂ [d] of columns and a non-zero vector w ∈ R Q + , we first check whether the following condition is satisfied:

λ 0 w 2 2 ≥ w 2 ∞ , (16)
where we recall that λ 0 = λ 5T . This condition is always verified when λ 0 ≥ 1, and it is equivalent to 16) ensures that w is not too sparse which could be harmful when many observations are lacking (λ 0 small). If this condition is not satisfied, then we leave the weights of W unchanged. Otherwise, we define the (Y, P, w)-updating weights U ∶= U(Y, P, w) around i as

λ 0 Q ≥ 1 when w = 1 Q . Condition (
U ij = 1 1 λ 0 ∧ λ 0 ⋅ ⟨Y i⋅ -Y j⋅ , w w 2 ⟩ , (17)
where, for all

w ′ ∈ R Q and a ∈ R d , we write ⟨a, w ′ ⟩ = ∑ k∈Q a k w ′ k .
We can then update the weighted directed graph around i by setting, for all i ∈ P such that

U ij ≥ W ij , W ij = U ij and W ji = -U ij . ( 18
)
As explained above, if we replace Y i⋅ and Y j⋅ by M i⋅ and M j⋅ respectively in [START_REF] Shah | Estimation from pairwise comparisons: Sharp minimax bounds with topology dependence[END_REF], then the corresponding value of the statistic is non-negative if expert i is above j. Hence, a large value for U ij provides evidence that i is above j.

Computing U(Y, P, w) for suitable directions w is the basic brick or our procedure, since it is through the update (18) that we iteratively increase the weights of W. This update shares some similarities to the pivoting algorithm introduced in [START_REF] Liu | Better algorithms for estimating non-parametric models in crowdsourcing and rank aggregation[END_REF] and also used in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF], in the sense that while we are fixing an arbitrary reference expert i to compute pairwise comparisons, they fix a set P and compute a pivot expert i 0 that would correspond to a quantile of the set {⟨Y j⋅ , w w 2 ⟩, j ∈ P } in the case λ 0 = 1. Note that the orientation of a given weighted edge (i, j) can change during the procedure if it turns out that U ij ≥ W ij and that U ij W ij ≤ 0. This simply means that if the direction w leads to a more significant weight between some experts i and j, then we are more confident to use the vector w and to revise the order between i and j. 17) amounts to compute the average of the observations over all questions in Q. We now explain in the main sections how we iteratively build adaptive weights w that allow to improve over the naive global average given by w = 1 [d] .

For Q ⊂ [d], choosing w = 1 Q in (

Definitions of a rank in a DAG

We first introduce a few definitions on directed acyclic graphs G, which we formally define as a set of directed edges (i, j) ∈ [n] 2 for which there is no cycle. We denote path(i, j) = {(k 1 , . . . , k L ) ∶ L > 0 and (i, k 1 ), . . . , (k L , j) ∈ G} as the set of all possible paths from i to j, and we write s for the length of any path s. We say that i and j are G-comparable if path(i, j) ∪ path(j, i) ≠ ∅, and we write N (i, G) for the set of all experts that are not Gcomparable with i. If i, j are G-comparable, it either holds that path(i, j) = ∅ or path(j, i) = ∅. We say in the first case that i is G-below j and that i is G-above j in the second case. we also define the relative rank from i according to G as the length of the longest path in G from i to j, or minus the longest past from j to i depending on wether i is G-above or G-below j:

rk G,i (j) = max{ s ∶ s ∈ path(i, j)} -max{ s ∶ s ∈ path(j, i)} . (19)
Here, we use the convention max ∅ = 0. With this definition, the neighborhood of a given expert i is equal to the set of experts whose relative rank is equal to 0, that is

N (G, i) = rk -1 G,i (0). Moreover, an expert j ∈ [n] is G-above (resp. G-below) i if and only if rk G,i (j) ≥ 1 (resp. rk G,i (j) ≤ -1).
Although G stands for a finite set of edges with endpoints in [n], we extend it to a set of edges with endpoints in Z 2 by putting in G every (i, j) ∈ Z 2 such that i > j and j ≤ 0 or i ≥ n + 1.

Description of the soft local ranking algorithm

To update the weighted directed graph W in Line 8 of Algorithm 1, we apply the soft local ranking procedure SLR to all experts i ∈ [n] and all thresholds γ. To define our soft local ranking procedure, let us fix W, an expert i and a threshold γ such that G(W, γ) is acyclic. As a shorthand, we write G and P respectively for the thresholded graph G(W, γ) and the neighborhood N (G, i) of i in G.

We write D for the set of all dyadic numbers: D = {2 k ∶ k ∈ Z} and we define the set H = D ∩ 1 nd , 1 . We denote y(P ) as the mean of the vectors Y j⋅ over all j ∈ P , that is

y k (P ) = 1 P ∑ j∈P Y jk , for any k ∈ [d]
. SLR relies on the following steps repeated over all height h ∈ H. It is also described in Algorithm 2.

1. Dimension reduction. Using the first sample Y (1) , we first reduce the dimension by selecting a subset Qh ⊂ [d] corresponding to wide confidence regions. Recall that rk G,i is the relative rank to i defined in [START_REF] Shah | Feeling the bern: Adaptive estimators for bernoulli probabilities of pairwise comparisons[END_REF]. For any a > 0, define the sets N a ∶= N a (G, i) (resp. N -a ∶= N -a (G, i)) of experts j which are G-above (resp. G-below) all the experts of P and whose relative rank to any i ′ ∈ P is at most a in absolute value:

N a = ⋂ i ′ ∈P rk -1 G,i ′ ([1, a]) and N -a = ⋂ i ′ ∈P rk -1 G,i ′ ([-1, -a]) . (20)
Secondly, we define for any question k ∈ [d] and a ≥ 1 the width statistic ∆k as the difference between the mean of the experts in N a and the mean of the experts in N -a . Then, âk is set to be the first value of a ≥ 1 such that any a ′ ≥ a has a corresponding width statistic of at least (λ 0 ∧ 1)h:

∆k (a) = y k (N a ) -y k (N -a ) and âk (h) = max a ≥ 1 ∶ 1 λ 0 ∧ 1 ∆k (a) < h + 1 . (21)
Finally, we define Qh ∶= Qh (G, i) as the set of indices k such that âk (h) is relatively small.

Qh = {k ∈ [d] ∶ N âk (h) ∧ N -â k (h) ≤ 1 λ 0 h 2 } . ( 22
)
Intuitively, if the experts above and below i vary by more than h on a specific question k, then this question should belong to Qh . Conversely, if the experts below and above i are nearly equal on the question k, than âk (h) will be large and k will not be selected in Qh .

2. Average-based weighted sums. Still using the first sample Y (1) , we examine the corresponding submatrix Y (1) (P, Q) restricted to questions in Q. If the row sums of Y are larger than the current edges, we update the weighted edges. More formally, we compute the (Y (1) , P, 1 Q)-updating weighted edges (U Q) around i as defined in [START_REF] Shah | Estimation from pairwise comparisons: Sharp minimax bounds with topology dependence[END_REF] and update W as in [START_REF] Shah | Stochastically transitive models for pairwise comparisons: Statistical and computational issues[END_REF]. We then also update G = G(W, γ) and P = N (G, i). 3. PCA-based weighted sums. Relying on the samples Y (2) , Y (3) , Y (4) , Y (5) , we do a slight abuse of notation and write Y (s) for the restriction of Y (s) to the subset P, Qh for s = 2, 3, 4, 5. Ideally, we would get an informative direction w from the largest right singular vector of E[Y (2) -Y

] ∈ R P × Qh . Indeed, it is known (see the proofs for more details) that the entries of the first right singular vector of an isotonic matrix all share the same sign and are most informative to compare the experts. However, computing directly the empirical right-singular vector of Y (2) -Y (2) does not lead to the desired bounds because (i) this matrix is perhaps highly rectangular (ii) the noise is possibly heteroskedastic and (iii) this matrix is perhaps sparse because of the many missing observations when λ 0 is small. Here, we use a workaround which is reminiscent of that of [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF] and discussed later. First, we compute v as a proxy for the first left singular vector

of E[Y (2) -Y (2)
].

v ∶= v(P, Qh ) = arg max

v∈R P ∶ v 2 ≤1 v T (Y (2) -Y (2)
) 2 2 -

1 2 v T (Y (2) -Y (2)
-Y (3) +Y

(3)

) 2 2 . ( 23
)
The right-hand side term in [START_REF] Wainwright | High-dimensional statistics: A non-asymptotic viewpoint[END_REF] deals with the heteroskedasticity of the noise matrix E in [START_REF] Bengs | Preference-based online learning with dueling bandits: A survey[END_REF]. v in ( 23) can be computed efficiently since it corresponds to the leading eigenvector of a symetric matrix. For technical reasons occurring in the sparse observation regime (i.e. when λ 0 is small), we then threshold the largest absolute values of the coefficients of v at √ λ 0 and define (v

-) i = vi 1{ vi ≤ √ λ 0 }.
After having calculated v-, we consider as in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF] the image ẑ = vT -(Y (4) -Y

) ∈ R Q of v-. We then threshold the smallest values of ẑ and take the absolute values of the components. Thus, we get ŵ+ ∈ R Q defined by ( ŵ+ ) l = ẑl 1{ ẑl ≥ γ λ 0 ∧ 1 λ 0 } for any l ∈ Q. Finally, we consider the last submatrix Y (5) = Y (5) (P, Q). We apply these weights ŵ+ to compute the row-wise weighted sums of Y (5) and update the weighted edges. More formally, we compute the (Y (5) , P, ŵ+ )-updating weighted edges U(Y (5) , P, ŵ) around i as defined in [START_REF] Shah | Estimation from pairwise comparisons: Sharp minimax bounds with topology dependence[END_REF]. We finally update the weighted directed graph W with U(Y (5) , P, ŵ+ ) as in [START_REF] Shah | Stochastically transitive models for pairwise comparisons: Statistical and computational issues[END_REF]. Compute Qh ∶= Q(G, i) as in [START_REF] Tsybakov | Introduction to Nonparametric Estimation[END_REF] using sample Y (1) 3:

Let U Qh be the (Y (1) , P, 1 Qh )-updating weighted edges around i as in [START_REF] Shah | Estimation from pairwise comparisons: Sharp minimax bounds with topology dependence[END_REF], using again sample Y (1)

4:

Update W with U( Qh ) as in [START_REF] Shah | Stochastically transitive models for pairwise comparisons: Statistical and computational issues[END_REF] and update G = G(W, γ), P = N (G, i) 5:

Restrict the samples (Y (s) )s=2,...,5 to P, Qh in the following remaining steps 6:

Compute the PCA-like direction v ∶= v(P, Qh ) as in [START_REF] Wainwright | High-dimensional statistics: A non-asymptotic viewpoint[END_REF] and define 4) ) and define ŵ+ by ( ŵ+

(v-)i = vi1{ vi ≤ √ λ0} 7: Compute ẑ = vT -(Y (4) -Y (
) l = ẑl 1{ ẑl ≥ γ λ0 ∧ 1 λ 0 } for any l ∈ Qh 8:
Let U(Y (5) , ŵ+ ) be the (Y (5) , P, ŵ+ )-updating weighted edges around i as in (17) 9:

Update W with U(Y (5) , ŵ+ ) as in (18) 10: end for

Toy example illustrating Algorithm 2

To understand why the steps described in Algorithm 2 are relevant, assume that π * = id and consider the following simple example where n = 204, d = 10, and where the isotonic matrix M π * -1 can be decomposed into three blocks of rows as

M π * -1 = α + h 2 ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 0 0 1 1 0 1 1 0 1 1 0 0 0 1 0 1 0 0 1 1 0 0 0 1 0 1 0 0 1 1 0 0 0 -1 0 -1 0 0 -1 -1 0 0 0 -1 0 -1 0 0 -1 -1 0 0 -1 -1 0 -1 -1 0 -1 -1 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ .
In the above matrix, α is any number in (h, 1h), and 0, 1 are the columns in R 100 whose coefficients are respectively all equal to 0 and 1. Assume that the statistician already knows that the first and the third blocks are made of experts that are respectively above and below the second block. If W, P, γ are the parameters fixed in Algorithm 2, the three blocks correspond respectively to the subsets N 1 ∪ N 2 , P and N -1 ∪ N -2 in our example. Provided that N -2 and N 2 are large enough, the set Qh only keeps columns corresponding to indices k where ∆k ( 1) is large -those are highlighted in blue.

Then, we can work on the reduced subset Qh of columns highlighted in blue. As one may check, Qh contains all the relevant columns to decipher the experts in the block P . Besides, the expected matrix of observations restricted to the block P and to Qh is of rank one:

E[Y -Y ] = h 2 ⎛ ⎜ ⎜ ⎜ ⎝ 0 1 1 0 1 1 0 1 1 0 1 1 0 -1 -1 0 -1 -1 0 -1 -1 0 -1 -1 ⎞ ⎟ ⎟ ⎟ ⎠ .
In particular, the right singular vector of this matrix is of the form (0, 1, 1, 0, 1, 1) and provides suitable weights to decipher the two largest experts from the two lowest experts in the above matrix. The PCA-based weighted sums steps above precisely aims at estimating these weights.

Comments on the procedure and relation to the literature

Finding confidence regions Q before computing weighted sums on the corresponding columns is at the core of our procedure. This idea generalizes the RankScore procedure of [START_REF] Flammarion | Optimal rates of statistical seriation[END_REF] which rather computes averages on the subsets [d] or on the singletons {1}, . . . , {d}. As mentioned in the introduction, only using the subsets of the RankScore method in [START_REF] Flammarion | Optimal rates of statistical seriation[END_REF] does not allow to reach the optimal rate for permutation estimation or matrix reconstruction. In Algorithm 2, the computation of subsets Qh is reminiscent of some aspects of the non oblivious trisection procedure used in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF] for the bi-isotonic model. In fact, the statistic ∆k corresponds to the statistic ∆(ext)

k,1 in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF]. Apart from that, the selection of subsets of questions was quite different in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF] as it mostly involved change-point detection ideas as introduced in [START_REF] Liu | Better algorithms for estimating non-parametric models in crowdsourcing and rank aggregation[END_REF]. However, those ideas are irrelevant in our setting because the rows do not exhibit any specific structure in the isotonic model.

The high-level sorting method in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF] is based on a hierarchical sorting tree with memory. In contrast, our new algorithm is based on an iterative refinement of a weighted comparison graph. This new algorithm is more natural and benefits from the fact that it is almost free of any tuning parameter. Indeed, at the end of Algorithm 1, we simply use the threshold γ corresponding to the largest acyclic Ĝ graph in W. No significant threshold needs to be chosen, since any permutation that is consistent with Ĝ is also necessarily consistent with W thresholded at values larger than γ.

The spectral step in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF] is quite similar to the third step of our procedure described in section 3.3.3, except for the first thresholding of v to obtain v-. In [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF], this workaround was not needed mainly because in the bi-isotonic model, it is possible to aggregate sparse observations by merging consecutive columns -see [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF] for further details. This is however not possible here.

As mentioned in the introduction, Liu and Moitra [START_REF] Liu | Better algorithms for estimating non-parametric models in crowdsourcing and rank aggregation[END_REF] obtain an upper bound of the permutation loss of the order of n 7 6 for the estimation of two unknown permutations in the case where M ∈ R n×n is bi-isotonic. Broadly speaking, their method involves iterating a clustering method called block-sorting over groups of rows or columns that are close with each other. Using this sorting method based on block-sorting, their whole approach alternates between row sorting and column sorting for a subpolynomial number of time. Besides, their procedure makes heavily use of bi-isotonicity of the matrix. It turns out that Algorithm 2 reaches the same rate in this bi-isotonic model by running only once on the rows, and once on the columns, as described in Section 2.4. Otherwise said, if the problem is to estimate only π * in the biisotonic model, we proved that only the isotonicity of the columns is necessary to achieve the state-of-the-art polynomial-time upper bound of order n 7 6 .

Examples of valid grids

Γ Remark that the simple set {(u+1)⋅φ L 1 , u ∈ {0, . . . , 2 ⌊log 2 (n)⌋+2}} is a valid grid of logarithmic size with γ ≤ (2 log 2 (n) + 3)φ L 1 .
This set is the smallest valid grid achieving the smallest possible value of γ. However, it depends on the quantity φ L 1 which is perhaps a bit pessimistic in practice.

An other choice can be to take R + itself, albeit infinite. Indeed, the set {G(W, γ), γ ≥ 0} is made of at most n 2 possible directed graphs for any W during the whole procedure. Choosing R + is convenient since it does not depend on the constants in φ L 1 that are likely to be overestimated. The drawback of choosing R + though is that the number of tested γ in Algorithm 2 becomes quadratic in n.

Finally, a good compromise is to take the set {(1

+ 1 log 2 (n) ) u ′ , u ′ ∈ Z}.
It is easy to check that it contains a sequence satisfying [START_REF] Mao | Towards optimal estimation of bivariate isotonic matrices with unknown permutations[END_REF] whose length is at least 2 ⌊log 2 (n)⌋ + 3 and whose maximum γ is a polylogarithmic function in nd δ.

Discussion on the computation of Ĝ and π

Once we have suitable weighted graph W, it remains to construct the permutation π, as in the second and third point of Section 3.1.

For the second point, checking that a given directed graph is acyclic can be done through depth first search with a computational complexity less than n, so that computing γ can be done with less than Γ n operations. As discussed in Section 3.3, it is possible to choose Γ to be of size of order less than log(n). If Γ is bounded and is such that any different thresholds γ, γ ′ in Γ satisfy γγ ′ ≥ η for some η > 0, the computation of γ can always be done with complexity of order less than n log(max(Γ) η).

Regarding the third point, a permutation π can be computed in polynomial time from the directed acyclic graph Ĝ using Mirsky's algorithm [START_REF] Mirsky | A dual of dilworth's decomposition theorem[END_REF] -see also [START_REF] Pananjady | Isotonic regression with unknown permutations: Statistics, computation and adaptation[END_REF]. It simply consists in finding the minimal experts i in Ĝ, removing them and repeat this process. This construction is in fact equivalent to ranking the experts according to the index rk Ĝ,0 as defined in [START_REF] Shah | Feeling the bern: Adaptive estimators for bernoulli probabilities of pairwise comparisons[END_REF].

Concentration inequality for rectangular matrices

In this section, we state a concentration inequality for rectangular random matrices with independent entries satisfying a Bernstein-type condition. This section can be read independently of the rest of the paper. Let p and q be two positive integers and X ∈ R p×q be a random matrix with independent and mean zero coefficients. Assume that there exists σ > 0 and K ≥ 1 such that for any i = 1, . . . , p and k = 1, . . . , q,

∀u ≥ 1, E[(X ik ) 2u ] ≤ 1 2 u!σ 2 K 2(u-1) . ( 24
)
This Bernstein-type condition ( 24) is exactly the same as Assumption 1 in [START_REF] Bellec | Concentration of quadratic forms under a bernstein moment assumption[END_REF] -see [START_REF] Bellec | Concentration of quadratic forms under a bernstein moment assumption[END_REF] for a discussion. Let Λ ∈ R p×p be any orthogonal projection matrix, i.e. Λ = Λ T and Λ 2 = Λ. We write r Λ for the rank of Λ.

Proposition 4.1. There exists a positive numerical constant κ such that the following holds for any δ > 0.

Λ(XX T -E[XX T ])Λ op ≤ κ (σ 4 pq + σ 2 q) log(p δ) + (σ 2 r Λ + K 2 log(q)) log(p δ) . (25)
For the sake of the discussion, consider the particular case where X ik = B ik E ik , with B ik and E ik being respectively independent Bernoulli random variable of parameter σ 2 and centered Gaussian random variable with variance 1. By a simple computation done e.g. in (77), X ik satisfies condition [START_REF] Zhang | Risk bounds in isotonic regression[END_REF] with K being of the order of a constant. Hence, if K 2 log(q) ≤ σ 2 p, applying Proposition 4.1 with the identity matrix Λ gives

XX T -E[XX T ] op ≤ 2κσ 2 pq log(p δ) + p log(p δ) , (26)
with probability at least 1δ.

Up to our knowledge, the inequality (26) is tighter than state-of-the-art result random rectangular sparse matrices in the regime where q ≫ p and σ 2 ≪ 1. In fact, most of the results in the literature concerning random matrices state concentration inequalities for the non centered operator norm XX T op -see the survey of Tropp [START_REF] Tropp | An Introduction to Matrix Concentration Inequalities[END_REF]. More specifically, Bandeira and Van Handel [START_REF] Bandeira | Sharp nonasymptotic bounds on the norm of random matrices with independent entries[END_REF] provide tight non-asymptotic bounds for the spectral norm of a square symmetric random matrices with independent Gaussian entries, and derive tail bounds for the operator norm of XX T . For instance, Corollary 3.11 in [START_REF] Bandeira | Sharp nonasymptotic bounds on the norm of random matrices with independent entries[END_REF], implies that, for some numerical constant c, E[ XX T 2 op ] ≤ c(σ 2 (p ∨ q) + log(p ∨ q)). Together with a triangular inequality, Bandeira and Van Handel imply

XX T -E[XX T ] 2 op ≤ cσ 2 ((p ∨ q) + log( p∨q δ )
) with probability higher than 1δ. While the order of magnitude σ 2 (p ∨ q) is tight for controlling the operator norm XX T 2 op of the non-centered Gram matrix with high probability, (26) implies that the right bound for

XX T -E[XX T ] 2
op is rather σ 2 √ pq which is significantly smaller in the regime p ≪ q and σ 2 ≪ 1.

In the proof of Theorem 2.2, we could have used those previous results for controlling the matrices of the form XX T -E[XX T ] 2 op . However, we would have then achieved a suboptimal risk upper bound. Indeed, Proposition 4.1 plays critical role in the proof of Theorem 2.2, when we need to handle matrices with partial observations that are possibly highly rectangular in the spectal step of the procedure [START_REF] Wainwright | High-dimensional statistics: A non-asymptotic viewpoint[END_REF].

The proof of Proposition 4.1 relies on the observation that the matrix XX T -E[XX T ] is the sum of q centered rank 1 random matrices. This allows us to apply Matrix Bernstein-type concentration inequalities for controlling the operator norm of this sum -see [START_REF] Tropp | An Introduction to Matrix Concentration Inequalities[END_REF] or Section 6 of [START_REF] Wainwright | High-dimensional statistics: A non-asymptotic viewpoint[END_REF].

Appendix A: Proof of Theorem 2.2

A.1. Notation and signal-noise decomposition

We first introduce some notation, and in particular the noise matrices on which we will apply concentration inequalities. In what follows, we define for any matrix A ∈ R n×d , and any vector

w ∈ R d : ⟨A i⋅ , w⟩ = d k=1 A ik w k . ( 27
)
If w belongs to R Q where Q is some subset of [d], we also write < A i⋅ , w >= ∑ d k∈Q A ik w k . The same notation stands for the scalar product on matrices, namely ⟨A,

A ′ ⟩ = Tr(A T A ′ ) if A ′ ∈ R n×d .
If A and A ′ are two matrices in R n×d , then we write the coordinate-wise product

(A ⊙ A ′ ) ik = A ik A ′ ik .
In what follows, we assume that π * = id. We make this assumption without loss of generality since we can reindex each expert i with i ′ = π * -1 (i). Recalling that B is defined in [START_REF] Rigollet | Uncoupled isotonic regression via minimum wasserstein deconvolution. Information and Inference[END_REF] we define

λ 1 ∶= P(B (s) ik = 1) = 1 -e -λ 0 . ( 28
) If λ 0 ≤ 1, we have λ 0 ≥ λ 1 ≥ (1 -1 e )λ 0 .
We assume in what follows that λ 0 ≤ 1, which corresponds to the case where there are potentially many unobserved coefficients. The case λ 0 ≥ 1 will be treated in Appendix F. For an observation matrix Y (s) defined in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF], we make the difference between E[Y (s) ] = λ 1 M , which is the unconditional expectation of Y (s) , and E[Y (s) B (s) ] = B (s) ⊙ M , which is the expectation of Y (s) conditionally to the matrix B. We write the noise matrix

E (s) = Y (s) -λ 1 M and Ẽ(s) = Y (s) -B (s) ⊙ M . (29)
Recall that ε t = y t -M xt is the subGaussian noise part in model [START_REF] Bellec | Concentration of quadratic forms under a bernstein moment assumption[END_REF], and that N s is defined in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF]. Each coefficient Ẽ(s)

ik can be rewritten as the average of the noise ε t . that are present in N (s) and that correspond to coefficient

x t = (i, k). Ẽ(s) ik = t∈N (s) εt r (s) ik ∨1 1{x t = (i, k)} . (30)
From now on, we often omit the dependence in s. We will extensively use the decomposition Y = λ 1 M + E, where λ 1 is defined in (28) and E in (29). Recalling that B ik = 1{r ik ≥ 1}, we often rewrite E as the sum of two centered random variables:

E ik = (B ik -λ 1 )M + B ik Ẽik .
Handling the concentration of the noise is more challenging in the case λ 0 ≤ 1 than in the full observation regime λ 0 ≥ 1 discussed in Appendix F. Indeed, while subGaussian concentration inequalities are effective in the full observation regime λ 0 ≥ 1, they lead to slower estimation rate in the case λ 0 ≤ 1, for instance in Lemma A.1. Indeed, it turns out that the variance of a coefficient ε ik is of order λ 0 ≤ 1, while the hoeffding inequality only implies that B ikλ 1 , and in particular ε ik are c-subGaussian for some numerical constant c. To overcome this issue, one of the main ideas is to use Bernstein-type bounds on the coefficients of E and on the random matrix EE T -E[EE T ]see Lemma B.1 and Proposition 4.1.

A.2. General property on W

Recall that we assume that λ 0 ≤ 1, so that 1 λ 0 ∧λ 0 = λ 0 in [START_REF] Shah | Stochastically transitive models for pairwise comparisons: Statistical and computational issues[END_REF], and that φ L 1 is defined in (9) by φ L 1 ∶= 10 4 log(10 2 nd δ). In the following, we let ξ be the event on which the noise concentrates well for all the pairs (Q, w) considered during the whole procedure. More precisely, we say that we are under event ξ, if for any s = 0, . . . , 5T -1 and for any pair (Q, w) that is used to compute a refinement as in [START_REF] Shah | Estimation from pairwise comparisons: Sharp minimax bounds with topology dependence[END_REF] we have

⟨E (s) i⋅ -E (s) j⋅ , w⟩ ≤ 1 3 φ L 1 λ 0 for any (i, j) ∈ [n] 2 . ( 31
)
Lemma A.1. The event ξ holds true with probability at least 1 -2T δ.

The idea of Lemma A.1 is to apply a bernstein-type inequality and a union bound on all the possible dot products ⟨E (s) i⋅ , w⟩, for all the 5T possible s and the at most 2T possible w. The upper bound is of the order of the square of the variance of E ik up to the polylogarithm factor φ L 1 . The crucial point is that if ⟨E (s) i⋅ , w⟩ is not λ 0 -subGaussian, it satisfies the Bernstein's Condition [ 2.15 of [START_REF] Massart | Concentration inequalities and model selection[END_REF]] with variance ν = λ 0 and scaling factor b = w ∞ . We then obtain an upper bound of order √ λ 0 since any w considered in the update step (18) must satisfy [START_REF] Saad | Active ranking of experts based on their performances in many tasks[END_REF].Recall that γ is defined in [START_REF] Massart | Concentration inequalities and model selection[END_REF]. We fix in what follows a sequence [START_REF] Mao | Towards optimal estimation of bivariate isotonic matrices with unknown permutations[END_REF]. We say that u is the level of the corresponding threshold γ u . We say W and (γ u ) satisfies the property C(W, (γ u )) if the following holds 1. consistency: For any (i, j) ∈ G(W, γ min ) it holds that π * (i) > π * (j).

γ = γ 0 > γ 1 > γ 2 > ⋅ ⋅ ⋅ > γ ⌊2 log 2 (n)⌋ = γ min in Γ satisfying property

weak-transitivity: Fix any

u ∈ {0, . . . , ⌊2 log 2 (n)⌋ -1}. For any experts i, j, k, if i is G(W, γ u )-above j and k ∈ N (G(W, γ u+1 ), j), then any i ′ ≥ i is also G(W, γ min )-above k.
The first point of the above property means that at threshold γ min , there is no mistake in the directed graph G(W, γ min ), meaning that if there is an edge from i to j in G(W, γ min ), then i is truly above j. Moreover, we only state the consistency property of the graph G(W, γ min ), but this property also implies that, for any more conservative threshold γ ≥ γ min , any (i, j) ∈ G(W, γ) satisfies π * (i) > π * (j). This is due to the fact that G(W, γ) ⊂ G(W, γ min ). The weak transitivity property states in particular that if there is a path from i to j in the more conservative graph G(W, γ u ), then there is a path from i to any k in the neighborhood of j at the less conservative threshold γ min . The following lemma states that the above property remains true for the weighted graph W ′ , after any update (18) of the whole procedure.

Lemma A.2. Under ξ, the property C(W ′ , (γ u )) holds true for any directed weighted graph W ′ obtained at any stage of Algorithm 1 and Algorithm 2.

We denote in the following W t for the directed weighted graph at the begining of step t. For any u ∈ [0, ⌊2 log 2 (n)⌋], we also write as a short hand G t,u = G(W t , γ u ) for the directed graph at begining of step t and level u and P t,u (i) = N (G t,u , i) for the set of experts that are not comparable with i according to G t,u . For any sequence of experts I, we write P t,u (I) for the sequence of subsets (P t,u (i)) i∈I . Let us now divide the T steps of the algorithm into τ max = ⌊log 2 (n)⌋ + 1 epochs of K = ⌊T τ max ⌋ steps. For any τ ∈ [0, τ max ], we also write G K τ,u = G τ K,u , P K τ,u (i) = P τ K,u (i) and P K τ,u (I) = P K τ,u (I). Now we consider for each epoch τ a sequence of experts I(τ ) = (i 1 (τ ), . . . , i Lτ (τ )) defined by induction:

• I(0) is the empty sequence • For τ ≥ 0, let (i 1 , . . . , i L ) be the sequence ordered according to π * and corresponding to the union of the already constructed sequences ⋃ τ ′ ≤τ I(τ ′ ) , and i = 0, i L+1 = n + 1. For any l ∈ [0, L], let A l be the set of experts that are G K τ +1,2τ +1 -below i l+1 but G K τ +1,2τ +1above i l . For all l such that A l is not empty, we define i ′ l as the expert of A l which is any expert closest to the median ⌊(i l + i l+1 ) 2⌋, and the new sequence

I(τ + 1) ∶= (i ′ l ).
By definition, remark that I(1) is equal to (⌊(n + 1) 2⌋). The induction step aims at building a sequence I(τ + 1) that is disjoint from ∪ τ ′ ≤τ I(τ ′ ), and that cuts each set A l of experts that are above i l and below i l+1 according to the graph at epoch τ + 1 and level 2τ + 1. Given the already constructed collections of perfectly ordered experts I(τ ′ ) for τ ′ ≤ τ , the idea of I(τ +1) is that it tends to fill the gaps between the neighborhoods in G τ +1,2τ +1 of any two successive experts in ∪ τ ′ ≤τ I(τ ′ ).

By monotonicity, it holds that for any expert i, epoch τ and level u that P K τ +1,u+1 (i) ⊂ P K τ +1,u (i) ⊂ P K τ,u (i). We say that the sets P K τ,2τ (i) and P K τ,2τ +1 (i) are the neighborhoods of i at the beginning of epoch τ and that the sets P K τ +1,2τ (i), P K τ +1,2τ +1 (i) are the neighborhood of i at the end of epoch τ . The neighborhoods at the end of a given epoch τ are obtained from the neighborhoods at the beginning the of epoch τ after K steps of the Algorithm 1. On the other hand, we say that the sets P K τ,2τ , P K τ +1,2τ are the conservative subsets at epoch τ , since they correspond to a more conservative directed graph with threshold γ 2τ ≥ γ 2τ +1 . The following lemma states that, at any epoch τ , the conservative subsets at the beginning of epoch τ are well separated according to the true order π * = id: Lemma A.3. Under event ξ, for any τ ∈ [0, τ max ], letting (i 1 , . . . , i L ) = I(τ ), we have

P K τ,2τ (i 1 ) < ⋅ ⋅ ⋅ < P K τ,2τ (i L ).
In other words, Lemma A.3 implies that, for any l < l ′ , any expert in P K τ,2τ (i l ) is π * -below any expert in P K τ,2τ (i l ′ ). As a consequence, it holds that for any l ∈ [1, L τ -2],

P K τ,2τ (i l ) G K τ,2τ ≺ P K τ,2τ (i l+2 ) . (32)
Namely, any expert in P K τ,2τ (i l ) is G K τ,2τ -below any expert in P K τ,2τ (i l+2 ). Indeed, Lemma A.3 and first point of event ξ imply that any expert j in P K τ,2τ (i l ) is G K τ,2τ -below i l+1 , since j cannot be in P K τ,2τ (i l ). On the other hand, i l+1 is itself G K τ,2τ -below any expert of P K τ,2τ (i l+2 ) for the same reason. The following lemma states that the ending less conservative subsets are covering the set of all experts.

Lemma A.4. Under event ξ, it holds that

[n] = τmax-1 ⋃ τ =0 ⋃ i∈I(τ ) P K τ +1,2τ +1 (i) .
Let π be the estimator obtained from the final weighted directed graph W at the end of the procedure, that is any permutation on [n] that is consistent with the largest acyclic graph of the form G(W, γ) for all γ > 0. For any sequence of subsets P = (P 1 , . . . , P L ) we define

SN(P) = P ∈P M (P ) -M (P ) 2 F . (33)
The following proposition that we can control the L 2 error of π by the maximum over all epoch τ of the sum over τ of the square norms of the groups in P K τ +1,2τ +1 . Proposition A.5. Under event ξ, it holds that

M π-1 -M 2 F ≤ 4 τmax-1 τ =0 SN(P K τ +1,2(τ +1) ) . (34)
Recall that γ is defined in [START_REF] Massart | Concentration inequalities and model selection[END_REF], and that Γ can be taken to be a valid grid with γ smaller than a polylogarithm in n, d, δ. The final proposition states that at any level u and any step t, any sequence of subset that can be ordered according to the already constructed graph G t,u as in (32) will either have a square norm smaller than the minimax rate ρ perm , defined in [START_REF] Chatterjee | Estimation in tournaments and graphs under monotonicity constraints[END_REF] or almost exponentially decrease its square norm with high probability.

Proposition A.6. Fix any u ∈ [0, 2τ max ] and step t < T , and assume that I = (i 1 , . . . , i L ) is a sequence of experts that satisfies P t,u (i 1 )

Gt,u ≺ . . .

Gt,u

≺ P t,u (i L ). Then on the intersection of the event ξ (defined in (31)) and an event of probability higher than 1 -5δ, it holds that

SN(P t+1,u (I)) ≤ C γ6 ρ perm (n, d, λ 0 ) ∨ 1 - 1 4γ 2 SN(P t,u (I)) ,
for some numerical constant C.

Let us fix τ ∈ {0, . . . , τ max -1}. Applying Proposition A.6 for each t = Kτ, . . . , Kτ + K -1 and u = 2(τ + 1) -the hypothesis of Proposition A.6 being satisfied by (32), we obtain with probability 1 -5(K + T )δ that

SN(P τ +1,2(τ +1) ) ≤ C γ6 ρ perm (n, d, λ 0 ) ∨ e - T 4τmax γ4 nd ≤ CT γ6 ρ perm (n, d, λ) ,
if T is larger than 4γ 6 ≥ 4 log 2 (nd)γ 4 . We conclude the proof of Theorem 2.2 with Proposition A.5, using that 4τ max ≤ γ:

M π-1 -M 2 F ≤ 4 τmax-1 τ =0 SN(P K τ +1,2(τ +1) ) ≤ CT γ7 ρ perm (n, d, λ) .
Appendix B: Proofs of the lemmas of Appendix A and of Proposition A.5

B.1. Proof of Proposition A.5

Let π be any arbitrary permutation that is consistent with the largest DAG G(W, γ), as defined in Section 3.1. Recall that we assume in this proof that π * = id. By Lemma A.4, for any i ∈ [n] there exists τ ∈ [0, τ max -1] and i 0 ∈ I(τ ) such that i ∈ P K τ +1,2τ +1 (i 0 ). Let us define the interval [a, b] as the maximal interval containing i 0 and that is included in the more conservative set P K τ +1,2τ . Now, if j > b, then by definition there exists j ′ such that j ≥ j ′ > b and j ′ ∈ P K τ +1,2τ . Summarizing the properties, we have j ≥ j ′ G τ +1,2τ ≻ i 0 , and that i is in the neighborhood of i 0 in the graph G τ +1,2τ +1 . Hence, applying the weak-transitivity property (first in C), holding true on event ξ -see Lemma A.2, we obtain that j is G(W K(τ +1) , γ min )above i. By the consistency property (second point in C), j is also necessarily G(W, γ min )-above i, and this proves that all the nb experts j satisfying j > b are G(W, γ min ) above i. Hence it holds that π(i) ≤ b. By symmetry, we also prove that π(i) ≥ a, so that

π(i) ∈ [a, b] ⊂ P K τ +1,2τ (i 0 ). (35)
Finally, we have

M π-1 -M 2 F = n i=1 M π(i)⋅ -M i⋅ 2 F ≤ τmax τ =0 i 0 ∈I(τ ) i∈P K τ +1,2τ +1 (i 0 ) M π(i)⋅ -M i⋅ 2 ≤ 2 τmax τ =0 i 0 ∈I(τ ) i∈P K τ +1,2τ +1 (i 0 ) M i⋅ -m(P K τ +1,2τ (i 0 )) 2 + M π(i)⋅ -m(P K τ +1,2τ (i 0 )) 2 ≤ 4 τmax τ =0 i 0 ∈I(τ ) i∈P K τ +1,2τ (i 0 ) M i⋅ -m(P K τ +1,2τ (i 0 )) 2 ,
where we used Lemma A.4 for the first inequality and (35) for the last inequality.

B.2. Proof of the lemmas of Appendix A

We postpone the proof of Lemma A.1 to the next subsection.

Proof of Lemma A.2. Recall that we consider the case λ 0 ≤ 1, so that λ 0 ∧ 1 λ 0 = λ 0 in [START_REF] Shah | Stochastically transitive models for pairwise comparisons: Statistical and computational issues[END_REF]. Consider any substep of the whole procedure where the current directed weighted graph is W ′ . For the first point, remark that i is G(W ′ , γ min )-above j only if there exists a previous substep during which we find out that ⟨Y i⋅ -Y j⋅ , w⟩ ≥ γ min on some direction w ∈ R Q , where Y is the sample used to refine the edges [START_REF] Shah | Estimation from pairwise comparisons: Sharp minimax bounds with topology dependence[END_REF]. Since γ min > φ L 1 , then decomposing Y = λ 1 M + E as in (29), we have

λ 1 ⟨M i⋅ -M j⋅ , w⟩ ≥ ⟨Y i⋅ -Y j⋅ , w⟩ -⟨E i⋅ -E j⋅ , w⟩ > 0 , ( 36
)
where the last inequality comes from (31), using the notation (27). Since the coefficients of w are nonegative, we have proven that i is above j. For the second point, assume that i is G(W, γ u )-above j, and take i ′ ≥ i. As before, there exists a direction w used during the procedure such that ⟨Y i⋅ -Y j⋅ , w⟩ ≥ γ u . Now consider any k ∈ N (G(W, γ u+1 ), j). On the direction w, we have under the event ξ defined in (31) that

⟨Y i ′ ⋅ -Y k⋅ , w⟩ ≥ λ 1 ⟨M i ′ ⋅ -M k⋅ , w⟩ -1 3 φ L 1 λ 0 ≥ λ 1 ⟨M i⋅ -M k⋅ , w⟩ -1 3 φ L 1 λ 0 ≥ ⟨Y i⋅ -Y j⋅ , w⟩ -⟨Y k⋅ -Y j⋅ , w⟩ -φ L 1 λ 0 ≥ (γ u -γ u+1 -φ L 1 ) λ 0 ≥ γ min λ 0 ,
where the last inequality comes from the assumption [START_REF] Mao | Towards optimal estimation of bivariate isotonic matrices with unknown permutations[END_REF]. We conclude that i ′ is G(W ′ , γ min )above k.

Proof of Lemma A.3. We proceed by induction over τ ≥ 0. The lemma is trivial for τ = 0, 1 since I(0) is empty and I(1) = (⌊(n + 1) 2⌋). Let τ ≥ 1 and i 1 , i 2 , i 3 be three experts in I(τ ) ∪ {0, n + 1} such that i 1 < i 2 < i 3 . Let A be the set of experts that are G K τ +1,2τ +1 -above i 1 and G K τ +1,2τ +1 -below i 2 , and A ′ be the set of experts that are G K τ +1,2τ +1 -above i 2 and G K τ +1,2τ +1below i 3 . Assume that both sets A and A ′ are nonempty, and let j ∈ A and j ′ ∈ A ′ . Let us apply the weak-transitivity of W, (γ u ) in Property C -which holds true under ξ from Lemma A.2 -

with u = 2τ +1. Since j is G K τ +1,2τ +1 -below i 2 , any k ∈ P K τ +1,2(τ +1) (j) is π * -below i 2 .
We also prove that any k ′ ∈ P K τ +1,2(τ +1) (j ′ ) is π * -above i 2 . We conclude that P K τ +1,2(τ +1) (j) < P K τ +1,2(τ +1) (j ′ ), and the proof of the lemma follows.

Proof of Lemma A. [START_REF] Bradley | Rank analysis of incomplete block designs: I. the method of paired comparisons[END_REF]. We prove that, by construction, any expert i ∈ [n] is at distance less than

(n + 1) 2 τ +1 of ⋃ τ τ ′ =0 ⋃ i∈I(τ ) P K τ +1,2τ +1 (i) ∪ {0, n + 1}
. This is obvious for τ = 0 since any expert is at distance less than (n + 1) 2 of 0 or n + 1. Let (i 1 , . . . , i L ) = ⋃ τ ′ ≤τ I(τ ′ ) be the collection of experts in the union of all possible I(τ ′ ) that is ordered according to π * . If j is any expert in [n], then we let l ∈ [0, L] be such that i l ≤ j ≤ i l+1 . We can assume that j ∈ P K τ +1,2τ +1 (i l ) and j ∈ P K τ +1,2τ +1 (i l+1 ) because otherwise the distance of j to ⋃ τ τ ′ =0 ⋃ L i∈I(τ ) P K τ +1,2τ +1 (i) is 0. Using property C holding true from Lemma A.2, it holds that the set A of experts that are G K τ +1,2τ +1 -above i l but G K τ +1,2τ +1 -below i l+1 contains j and therefore is nonempty. Now, let m = ⌊(i l + i l+1 ) 2⌋ and i ′ be any expert closest to m in A, as defined in the construction of I(τ + 1), and assume without loss of generality that m ≤ i ′ . We consider the following cases:

• m ≤ i ′ ≤ j: In that case, j is at distance less than (i l+1 -m) 2 of i ′ or i l+1 . • m ≤ j < i ′ : This case is not possible since i ′ is the closest expert to m in A. • j < m < i ′ : In that case, since i ′ minimizes the distance to m, we necessarily have that m ∈ P K τ +1,2τ +1 (i l ) ∪ P K τ +1,2τ +1 (i l+1 ).
Hence j is at distance less than (mi l ) 2 of m or i l . We have proved that the distance of any j to

⋃ τ +1 τ ′ =0 ⋃ L i∈I(τ ) P K τ +1,2τ +1 (i) ∪ {0, n + 1} is at most (m -i l ) 2 or (i l+1 -m) 2.
Using the induction hypothese, we have that mi l and i l+1m are both less than n 2 τ +1 , which concludes the induction.

Finally, applying this property with τ max -1 = ⌊log 2 (n)⌋ gives a distance strictly smaller than 1, which proves the result.

B.3. Proof of Lemma A.1

Let us start with the following lemma, which gives a concentration bound when λ 0 ≤ 1: Lemma B.1. For any δ ′ > 0 and for any matrix W ∈ R n×d , the following inequality holds with probability at least 1δ ′ :

⟨E, W ⟩ ≤ 4e 2 W 2 F λ 0 log 2 δ ′ + W ∞ log 2 δ ′ . ( 37
)
Now we apply Lemma B.1 with the matrix W with 0 coefficients except at line i where it is equal to the vector w w 2 as defined in ( 17) and we deduce that

⟨E i,⋅ , w w 2 ⟩ ≤ 4e 2 λ 0 log 2 δ ′ + w ∞ w 2 log 2 δ ′ ≤ 11 λ 0 log(2 δ ′ ) , (38)
where the last inequality comes from Condition ( 16) on w. Now choosing δ ′ = δ (4T n 6 ), a union bound over the at most 2n 2 T H ( Γ ∧ n 2 ) pairs (Q, w) considered during the procedure, we deduce the bound of Lemma A.1 for all λ 0 ≤ 1.

Proof of Lemma B.1.

Recall that E, Ẽ are defined in (29) and that we have in particular

E ik = (B ik -λ 1 )M ik + Ẽik .
Let x > 0. By Cauchy-Schwarz inequality, we have

E[e xE ik ] ≤ E[e 2x(B ik -λ 1 )M ik ] E[e 2x Ẽik ] ,
where we recall that λ 1 = 1e -λ 0 ≤ λ 0 . We have

E[e 2x(B ik -λ 1 )M ik ] ≤ e -2λ 1 xM ik (λ 1 (e 2xM ik -1) + 1) ≤ e λ 1 e 2 x 2 ,
and

E[e 2x Ẽik ] ≤ λ 1 (e 2x 2 -1) + 1 ≤ e λ 1 e 2 x 2 ,
where we used the inequalities e 2x 2 -1 ≤ e 2 x 2 and e 2x -1 -2x ≤ e 2 x 2 for any x ∈ [-1, 1].

In particular, if t > 0, a Chernoff bound with x =

t 2 W 2 F λ 0 e 2 ∧ 1 gives P(⟨W, E⟩ ≥ t) ≤ exp(-( t 2 4 W 2 F λ 0 e 2 ∧ t)) ,
so that with probability at least 1δ ′ :

⟨W, E⟩ ≤ 4e 2 W 2 F λ 0 log 2 δ ′ + log 2 δ ′ .
Appendix C: Proof of Proposition A.6

Step 0 : general definitions

In this proof, we fix u ∈ {0, . . . , 2 ⌊log 2 (n)⌋ + 2} and a corresponding threshold γ u in the sequence in Γ satisfying γ u ≥ φ L 1 -see ( 10) -and a step t < T . We assume that I = (i 1 , . . . , i L ) is a fixed sequence of experts that satisfies P t,u (i 1 )

Gt,u ≺ . . . Gt,u ≺ P t,u (i L ).
From now on, we ease the notation by omitting the dependence in t, u, γ u and we write G = G t,u , G ′ = G t+1,u , P = (P 1 , . . . , P L ) for P t,u and P ′ for P t+1,u . We denote Gh for the directed graph at threshold γ u of the directed weighted graph W h obtained at the end the first update Line 3 of Algorithm 2. We also write P h l = N ( Gh , i l ) and Ph = ( P h 1 , . . . , P h L ) for the corresponding sequence of subsets at height h ∈ H. By monotonicity, it holds for any h ∈ H that P ′ l ⊂ P h l ⊂ P l .

C.1. Step 1: Analysis of the selected set Q

Recall the definition of the neighborhoods (20) of the set P l in the graph G:

N a (l) = ⋂ i∈P l rk -1 G,i l ([1, a]) and N -a (l) = ⋂ i∈P l rk -1 G,i l ([-1, -a]) ,
Define for κ > 0 and l ∈ [1, L] the population version ∆ * k of the width statistic ∆k -see ( 21)as the the difference of the best and worst expert of P (i l ) if a = 0 and as the difference of the average of the experts in N a (l) and the average of the expert in N -a (l):

∆ * k (0, l) = max i,j∈P (i l ) M i,k -M j,k and ∆ * k (a, l) = m k (N a (l)) -m k (N -a (l)) if a ≥ 1. ( 39
)
We also define a * (h, l) as the minimum a ≥ 1 such that there are at least 1 λ 0 h 2 experts in N a (l) and in N -a (l):

a * (h, l) = min{a ≥ 1 ∶ N a (l) ∧ N -a (l) ≥ 1 λ 0 h 2 } . ( 40
)
Now, define for φ ≥ 1:

Q * h l (φ) ∶= {k ∈ [d] ∶ ∆ * k (0, l) ∈ [φh, 2φh]} Q * h l (φ) ∶= {k ∈ [d] ∶ ∆ * k (a * (φ -1 h, l), l) ≥ h 2} . (41)
The following lemma states that, for φ of order log(nd δ), we can sandwich Qh l between the two fixed sets Q * h l and Q * h l : Lemma C.1. Let l be a fixed index in {1, . . . , L} and h a fixed height in H. There exists a numerical constant κ 0 > 0 such that, with probability at least 1δ (L H ), we have

Q * h l (κ 0 log(nd δ)) ⊂ Qh l ⊂ Q * h l (κ 0 log(nd δ)) . (42)

C.2. Step 2 : l1-control of the intermediary sets Ph

Recall that γ u is a threshold corresponding to a sequence in Γ as defined in [START_REF] Mao | Towards optimal estimation of bivariate isotonic matrices with unknown permutations[END_REF]. For any sets

P ⊂ [n], Q ⊂ [d], we say that M (P, Q) is indistinguishable in L 1 -norm if it satisfies max i,j∈P M i⋅ (P, Q) -M j⋅ (P, Q) 1 ≤ 3γ u Q λ 0 . ( 43
)
For a fixed l ∈ {1, . . . , L}, let ξ L 1 (l, h) be the event under which

M ( P h l , Qh l ) is indistinguish- able in L 1 -norm. Lemma C.2. Let l be a fixed index in {1, . . . , L} and h ∈ H such that λ 0 Q * h l ≥ 1. The event ξ L 1 (l, h) holds true with probability at least 1 -δ (L H ).
Let κ 0 be a numerical constant given by Lemma C.1 and let φ 0 = κ 0 log(nd δ). In what follows, we write for simplicity

(Q * h l , Qh l , Q h l ) = (Q * h l (φ 0 ), Qh l (φ 0 ), Q h l (φ 0 )).
Lemma C.2 provides an upper bound only on the L 1 distance between rows of M restricted to the subsets P h l and Qh l , while the square norm of a group (33) is defined with the L 2 distance. with (43). The idea is that for any k in Q * h , and for any i ∈ P h , we have that

M ik -m k 2 ≤ 2φ 0 h M ik -m k . In particular, M i⋅ ( P h l , Q * h l ) -m ⋅ ( P h l , Q * h l ) 2 2 ≤ 2φ 0 h M i⋅ ( P h l , Q * h l ) -m ⋅ ( P h l , Q * h l ) 1 .
Hence, it holds from Lemma C.1, Lemma C.2 and a union bound over all l ∈ {1, . . . , L} and all h ∈ H satisfying λ 0 Q * h l ≥ 1 that with probability at least 1 -2δ,

i∈ P h l M i⋅ ( P h l , Q * h l ) -m ⋅ ( P h l , Q * h l ) 2 2 ≤ 6φ 0 γ u ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ h P h l Q * h l λ 0 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ , (44)
simultaneously for all l ∈ {1, . . . , L} and h ∈ H satisfying

λ 0 Q * h l ≥ 1.
Proof of Lemma C.2. Let l be a fixed index in {1, . . . , L} and h be a fixed height in H. If a ≥ 1, the subset P l is disjoint from the sets N a (l) ∪ N -a (l) so that Qh l is independent of Y (1) (P l ). Remark also that condition ( 16) is satisfied since

λ 0 Q * h l ≥ 1 and Q * h l ⊂ Qh l .
Recall that we assume that λ 0 ≤ 1. We write w = 1 Qh l and we recall that B = (B ik ) is the matrix defined in [START_REF] Rigollet | Uncoupled isotonic regression via minimum wasserstein deconvolution. Information and Inference[END_REF]. Let i, j ∈ P h l so that, by definition, we have that ⟨Y i⋅ -Y j⋅ , w⟩ ≤ γ u λ 0 Qh l . With probability at least 1δ L, for all i, j in P l we have that

λ 1 ⟨M i⋅ -M j⋅ , w⟩ ≤ ⟨Y i⋅ -Y j⋅ , w⟩ + ⟨E i⋅ -E j⋅ , w⟩ ≤ (γ u + φ L 1 2) λ 0 Qh l . (45)
where the last inequality comes from Lemma B.1 applied with δ ′ = δ n 3 and from the definition of φ L 1 [START_REF] Mao | Breaking the 1 √ n barrier: Faster rates for permutation-based models in polynomial time[END_REF]. Recalling the two inequalities λ 1 = 1e -λ 0 ≥ λ 0 2 and φ L 1 ≤ γ u , we obtain the result.

C.3. Step 3 : Local square norm reduction

Henceforth we condition to the sample Y (1) of Algorithm 2 which allows us to assume that, for any h ∈ H, the two sequences of sets Ph and Qh are fixed.

For κ 1 > 0, let ξ loc (l, h, κ 1 ) be the event holding true if the local square norm of M (P l , Qh l ) has decreased at the end of Algorithm 2, that is

M (P ′ l , Qh l ) -M (P ′ l , Qh l ) 2 F ≤ κ 1 γ 4 u 1 λ 0 P l Qh l + P l λ 0 ∨ 1 - 1 4γ 2 u M (P l , Qh l ) -M (P l , Qh l ) 2 F . (46)
The following proposition states that given the fact that the experts in P h l are indistinguishable in L 1 -norm and λ 0 ( P h l ∧ Q * h l ) ≥ 1, the event ξ loc holds true simultaneously for all l and h with high probability.

Proposition C.3. There exists a numerical constant κ 1 such that the following holds, for any fixed index l in {1, . . . , L}, and fixed height h in H. Conditionally to Y (1) , the event ξ L 1 (l) and λ 0 ( P h l ∧ Q * h l ) ≥ 1, the event ξ loc (l, h, κ 1 ) holds true with probability at least 1 -3δ (L H ). Proposition C.3 is at the core of the analysis, and its proof contains a significant part of the arguments. This proposition and its proof are similar to Proposition D.5 in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF], but the main difficulty with respect to [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF] is that we do not achieve the optimal rate in λ 0 ≤ 1 using only the subgaussianity of the coefficients of the noise E. A key step in the proof of Proposition C.3 is Proposition 4.1, which implies Lemma E.2 and gives a concentration inequality of the operator norm of EE T -E[EE T ]. Proposition 4.1 is effective in that case since the coefficients of E will be proven to satisfy [START_REF] Zhang | Risk bounds in isotonic regression[END_REF].

Then, the idea is that when a group P ′ l has a square norm of order at least 1

λ 0 P l Qh l + P l
λ 0 , the PCA-based procedure defined as in [START_REF] Wainwright | High-dimensional statistics: A non-asymptotic viewpoint[END_REF] will output a vector v that is well aligned with the first left singular vector of M ( P h l , Qh l ) -M ( P h l , Qh l ). Moreover, the isotonic structure of M ( P h l , Qh l )-M ( P h l , Qh l ) implies in fact that its operator norm is greater than a polylogarithmic fraction of its Frobenius norm (see Lemma E.1 or Lemma E.4 in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF]], so that vT (M ( P h l , Qh l )-M ( P h l , Qh l )) 2 2 is of the same order as the square Frobenius norm. Hence after updating the edges, we can prove that the experts in P h l ∖P ′ l were contributing significantly to the Frobenius norm, which enforces the contraction part in the second term of the maximum in (46). All the details of the proof can be found in Appendix E.

C.4. Step 4 : Control of the size of the sets

Q * h l For any p ∈ [n] ∩ {2 k ∶ k ∈ Z + }, let L(p)
Q * h (φ) ≤ 12φ 2 1 pλ 0 h 2 ∨ 1 d h .
The proof of Lemma C.4 is mainly implied by the fact that the coefficients of M are bounded by 1. Then, the idea is that in the case where all the sets P l are of size p, it is enough to take a number of group a of order at most 1 pλ 0 h 2 ∨ 1 above and below each P l to ensure that the corresponding neighborhood of P l has size N a (l) ∧ N -a (l) ≥ 1 λ 0 h 2 .

C.5. Step 5 : Conclusion of the previous steps

We first decompose the square norm SN(P) as defined in (33) into two terms. Assume that the event of Lemma C.1, ξ L 1 (l) and ξ loc (l, h, κ 1 ) -see Lemma C.2 and Proposition C.3 -hold true. Define L -as the sequence of indices l such that the corresponding reduced subsets P ′ l have low local square norm for all h ∈ H. More precisely, we say that l ∈ L -if for all h ∈ H we have

M (P ′ l , Qh l ) -M (P ′ l , Qh l ) 2 F ≤ κ 1 γ 4 u 1 λ 0 P l Qh l + P l λ 0 ∨ 1 2 H M (P l ) -M (P l ) 2 F . (47)
We also define the complementary L + = [1, L] ∖ L -and their corresponding subsets P ′ + , P ′ -in P ′ . We have the following decomposition:

SN(P ′ ) = SN(P ′ + ) + SN(P ′ -) . (48)
Let us now give an upper bound of SN(P ′ + ). For any l ∈ L + , there exists by definition an element h l H such that

M (P ′ l , Qh l l ) -M (P ′ l , Qh l ) 2 F > κ 1 γ 4 u 1 λ 0 P l Qh l + P l λ 0 ∨ 1 2 H M (P l , Qh l ) -M (P l , Qh l ) 2 F .
Hence applying (46) with h = h l , we have that, for any l ∈ L + ,

M (P ′ l ) -M (P ′ l ) 2 F = M (P ′ l , Qh l l ) -M (P ′ l , Qh l l ) 2 F + M (P ′ l , [d] ∖ Qh l l ) -M (P ′ l , [d] ∖ Qh l l ) 2 F ≤ M (P l ) -M (P l ) 2 F - 1 4γ 2 u M (P l , Qh l l ) -M (P l , Qh l l ) 2 F ≤ 1 - 1 γ 3 u M (P l ) -M (P l ) 2 F ,
where the third inequality comes from the second term of (47) together with P ′ l ⊂ P l and γ u ≥ φ L 1 ≥ 8 H , with φ L 1 defined in [START_REF] Mao | Breaking the 1 √ n barrier: Faster rates for permutation-based models in polynomial time[END_REF]. Hence we obtain that

SN(P ′ + ) ≤ 1 - 1 γ 3 u SN(P + ) . (49)
Finally, we give an upper bound of SN(P ′ -). Let us write

D n = {2 k ∶ k ∈ Z + } ∩ [n]
for the set of dyadic integer smaller than n. Given p ∈ D n , we write L -(p) = L(p) ∩ L -for the set of indices in L -such that P l ∈ [p, 2p), and P ′ -(p) for the corresponding sequence of subsets in P ′ -(p). Let φ 0 = κ 0 log(nd δ), where κ 0 is a numerical constant given by Lemma C.1. By definition of Q * h l , the square norm of a group P ′ l restricted to questions that do not belong the set ∪ h∈H Q * h l is smaller than φ 0 nd ⋅ min(H) ≤ φ 0 . Hence we have that

SN(P ′ -) = p∈Dn SN(P ′ -(p)) ≤ φ 0 + (p,h)∈Dn×H l∈L-(p) M (P ′ l , Q * h l ) -M (P ′ l , Q * h l ) 2 F . ( 50
) If λ 0 Q * h l ≤ 1 then we use the trivial inequality M (P ′ l , Q * h l ) -M (P ′ l , Q * h l ) 2 F ≤ P ′ l Q * h l ≤ P h l λ 0 ,since the entries of M are bounded by one. If λ 0 Q * h l ≥ 1 and P h l λ 0 ≤ 1, we have that h P h l Q * h l λ 0 ≤ P h l Q * h l λ 2 0
, using the fact that h ≤ 1. Hence, since the experts in P ′ l ⊂ P h are indistinguishable in L 1 norm by Lemma C.2, (44) holds true and we have

M (P ′ l , Q * h l ) -M (P ′ l , Q * h l ) 2 F ≤ 6φ 0 γ u ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ h P h l Q * h l λ 0 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ≤ 6φ 0 γ u ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ h 2 P h l 2 Q * h l λ 0 ∧ P h l Q * h l λ 2 0 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ≤ 12φ 0 γ u ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ (h 2 pλ 0 ∧ 1) p Q * h l λ 2 0 + p λ 0 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ . Finally, if λ 0 ( Q * h l ∨ P h l ) ≥ 1, we are in position to apply Proposition C.3. For all l ∈ L -(p) and h ∈ H that M (P ′ l , Q * h l )-M (P ′ l , Q * h l ) 2 F is either smaller than 1 2 H M (P l )-M (P l ) 2 F , or it is smaller than κ 1 γ 4 u 1 λ 0 P l Qh l + P l λ 0 . From (44), it is also smaller than 6φ 0 γ u h P h l Q * h l λ 0 .
As a consequence, we obtain the following upper bound:

M (P ′ l , Q * h l ) -M (P ′ l , Q * h l ) 2 F ≤κ 2 γ 4 u ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ (h 2 pλ 0 ∧ 1) p Q * h l λ 2 0 + p λ 0 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ∨ 1 2 H M (P l ) -M (P l ) 2 F , (51)
with κ 2 = 12(κ 0 ∨ κ 1 ), and using that φ 0 ≤ κ 0 γ u and P h l ≤ P l ≤ 2p. By the two previous cases on l, the inequality (51) is valid for any l ∈ L -(p). Now, we decompose (50) into two terms, corresponding to the maximum in (51). First, since each P l is in at most one P -(p) for p ∈ D n , we have

(p,h)∈Dn×H l∈L-(p) 1 2 H M (P l ) -M (P l ) 2 F ≤ 1 2 SN(P -) . (52)
Secondly, we have that

κ 2 γ 4 u (p,h)∈Dn×H l∈L-(p) ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ (h 2 pλ 0 ∧ 1) p Q * h l λ 2 0 + p λ 0 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ≤ κ 2 γ 6 u ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ max p,h l∈L-(p) (h 2 pλ 0 ∧ 1) p Q h * l λ 2 0 + p λ 0 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ (a) ≤ 2κ 2 γ 6 u max p,h ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ n λ 0 + (h 2 pλ 0 ∧ 1) p L(p) ∑ l∈L(p) Q h * l λ 2 0 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ (b) ≤ 4κ 2 2 γ 7 u max p,h ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ n λ 0 + (h 2 pλ 0 ∧ 1) n 2 d λ 2 0 p ∧ nd pλ 3 0 h 3 ∨ nd λ 2 0 h ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ ≤ 4κ 2 2 γ 7 u max p,h ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ n λ 0 + nh d λ 0 ∧ n 2 dh 2 λ 0 ∧ nd λ 2 0 h ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ (c) ≤ 4κ 2 2 γ 7 u ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ n λ 0 + n d λ 0 ∧ n 2 3 √ d λ 5 6 0 ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ .
where in (a) we used the Jensen inequality, in (b) we used Lemma C.4 with φ = φ 0 together with the trivial inequality ∑ l∈L(p) Q h * l ≤ nd p and in (c) the fact that x ∧ y ≤ x 2 3 y 1 3 and h ≤ 1.

Finally, combining this last inequality with (48), (49) and (52), we obtain

SN(P ′ ) = SN(P ′ + ) + SN(P ′ -) ≤ 1 - 1 γ 3 u SN(P + ) + 4κ 2 2 γ 7 u ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ n λ 0 + n d λ 0 ∧ n 2 3 √ d λ 5 6 0 ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ ∨ 1 2 SN(P -) ≤ ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ C γ7 ⎛ ⎝ n λ 0 + n d λ 0 ∧ n 2 3 √ d λ 5 6 0 ⎞ ⎠ ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ ∨ 1 - 1 γ3 SN(P) ,
where we recall that γ is defined in [START_REF] Massart | Concentration inequalities and model selection[END_REF] and satisfies γ ≥ γ u . This concludes the proof of Proposition A.6.

Appendix D: Proof of the lemmas of Appendix C

Recall that we can write

E = (B -E[B]) ⊙ M + B ⊙ Ẽ . ( 53
)
where we recall that Ẽ = Y -E[Y B] and that B is a matrix of Bernoulli random variables with parameter λ 1 .

Proof of Lemma C.1. Assume first that λ 0 ≤ 1. Let us fix l ∈ {1, . . . , L} and h ∈ H. We omit the dependence in l in this proof to ease the notation and we write P for P l . Let us define

E ′ k (a) ∶= 1 N a i∈Na E ik - 1 N -a i∈N-a E ik and ν(a) ∶= N a ∧ N -a . (54)
Using Lemma B.1 with a column matrix W with coefficient in {0, 1 Na , -1 N-a } and a union bound over all k ∈ [d] and a ∈ [n], we have with probability at least 1δ L that:

1 λ 0 E ′ k (a) ≤ κ ′ 0 log(nd δ) 1 λ 0 ν(a) + 1 λ 0 ν(a) , (55)
for some numerical constant κ ′ 0 . In what follows, we work under that (55) holds true for all a ∈ [n] and k ∈ [d].

First inclusion. Let k ∈ Q * (κ 0 log(nd δ)h) with numerical constant κ 0 to be fixed later. Let a ′ ≥ 1 be any integer such that ν(a ′ ) ≥ 1 (λ 0 h 2 ). We have

1 λ 0 E ′ k (a ′ ) ≤ 2κ ′ 0 log(nd δ)h , (56)
since we work under the event defined by (55) and since h 2 ≤ h. Then by consistency of the already constructed graph G t,u at the beginning of step t, N a ′ (resp. N -a ′ ) contains by definition [START_REF] Shah | A permutation-based model for crowd labeling: Optimal estimation and robustness[END_REF] only experts that are π * -above (resp. below) all the experts of P . Since by assumption k is in

Q * h , it holds that ∆ * k (a ′ ) ≥ ∆ * k (0) ≥ κ 0 log(nd δ)h -see the definition (41) of Q * h .
Hence, recalling the signal-noise decomposition (53), we have that

1 λ 0 ∆k (a ′ ) = λ 1 λ 0 ∆ * k (a ′ ) + 1 λ 0 E ′ k (a ′ ) ≥ log(nd δ)((1 -1 e)κ 0 -2κ ′ 0 )h . ( 57
)
Choosing κ 0 ≥ 10κ ′ 0 + 1, we obtain by definition (21) that ν(â k (h)) ≤ 1 λ 0 h 2 so that k ∈ Qh . Second inclusion. Let k ∈ Qh , and a ′ = a * ((κ 0 log(nd δ)) -1 h) be as defined in (40). By definition, it holds that ν(a ′ ) ≥ κ 0 log(nd δ) (λ 0 h 2 ) ≥ 1 λ 0 h 2 . Hence, since k ∈ Qh , we have by definition [START_REF] Tsybakov | Introduction to Nonparametric Estimation[END_REF] that ν(â k (h)) ≤ 1 λ 0 h 2 ≤ ν(a ′ ), which implies in particular that âk (h) ≤ a ′ . Then, by definition [START_REF] Tropp | An Introduction to Matrix Concentration Inequalities[END_REF] of âk (h) we have that 1 λ 0 ∆k (a ′ ) ≥ h. Using the concentration inequality (55) with h ′ = (κ 0 log(nd δ)) -1 h and the fact that λ 0 ≥ λ 1 we obtain

∆ * k (a ′ ) ≥ h - 2κ ′ 0 κ 0 h , (58)
and we get the second inclusion by also choosing κ 0 ≥ 4(κ ′ 0 + 1). Proof of Lemma C.4. For simplicity, we renumber L(p) = (1, 2, . . . , L ′ ∶= L(p) ). Let us write ν(a, l) = N a (l) ∧ N -a (l) and Λ = ⌊ φ 2 pλ 0 h 2 ⌋ + 1. We let a * ∶= a * (φ -1 h, l) be as defined in (40) so that for any l, ν(a * , l) ≥ φ 2 λ 0 h 2 . By assumption of Proposition A.6, it holds that P 1

G ≺ P 2 G ≺ . . . G ≺ P L(p)
where we recall G = G t,u is the already constructed graph -see Appendix C.1. Hence it holds that rk G,i (j) ≥ Λ for any i ∈ P l and j ∈ P l+Λ -see [START_REF] Shah | Feeling the bern: Adaptive estimators for bernoulli probabilities of pairwise comparisons[END_REF] for the definition of rk. Since there are at least pΛ ≥ φ 2 λ 0 h 2 experts in the union P l+1 ∪ ⋅ ⋅ ⋅ ∪ P l+Λ , we conclude that a * ≤ Λ, and that any expert in N a * (resp. N -a * ) is below the maximal expert of P l+Γ (resp. above) the minimal expert of P l-Λ . This implies that, upon writing ∆ * k (l) for the difference of these maximal and minimal experts, we have by definition (41

) of Q * h that ∆ * k (l) > h 2 for all k in Q * h . This implies in particular that l∈L(p) Q * h l (h, φ) ≤ d k=1 l∈L(p) 1{∆ * k (l) ≥ h 2} ≤ 2 h d k=1 l∈L(p) ∆ * k (l) ≤ (2Λ + 1) 2d h ≤ 6 Λd h , (59)
where in the last inequality we used the fact that M i,k ∈ [0, 1] and that the sequence P l-Λ , . . . , P l+Λ is of length 2Λ + 1, for any l ∈ L(p).

Now remark that since vi 2 = 1, there are at most 1 λ 0 of experts i such that vi > √ λ 0 . Hence we have that

vT -M -M 2 2 ≥ 2 γ 2 u M -M 2 F - i∈ P 1 vi > √ λ 0 M i⋅ -m 2 2 (a) ≥ 2 γ 2 u M -M 2 F - 3γ u λ 0 Q λ 0 (b) ≥ 1 γ 2 u M -M 2 F .
(a) comes from the fact that any expert in P satisfies (43) under the event of Lemma C.2. (b)

comes from Condition (60) and the assumption that λ 0 P ≥ 1.

Step 3: control of the vector ŵ

Next, we show that a thresholded version of ẑ = (Y (4) -Y

) T v-is almost aligned with

z * = λ 1 (M -M ) T v-.
We define the sets S * ⊂ Q and Ŝ ⊂ Q of questions by

S * = k ∈ Q ∶ z * k ≥ 2γ u λ 0 ; Ŝ = k ∈ Q ∶ ẑk ≥ γ u λ 0 . (64)
S * stands for the collection of questions k such that z * k is large whereas Ŝ is the collection questions k with large ẑk . Finally, we consider the vectors w * and ŵ defined as theresholded versions of z * and ẑ respectively, that is w * k = z * k 1 k∈S * and ŵk = ẑk 1 k∈ Ŝ . Note that, up to the sign, ŵ stands for the active coordinates computed in SLR, Line 7 of Algorithm 2.

Recall that we assume that λ 0 ≤ 1. We write v for any unit vector in R P . Let us apply Lemma B.1 for each column k ∈ Q of the noise matrix E with the matrix W equal to v -( 1 P ∑ i∈ P v i )1 P at column k and 0 elsewhere. We deduce that, for any fixed matrix M , any subsets P and Q, and any unit vector v ∈ R P such that v ∞ ≤ 2 √ λ 0 , we have

P max k∈Q (v T (E (3) -E (3)
)

) k ≤ 100 log(2 Q δ ′ ) λ 0 ≥ 1 -δ ′ . (65)
Observe that ẑ = z * + (E (3) -E

) T v-. Conditioning on v-, we deduce that, on an event of probability higher than 1δ ′ , we have

ẑ -z * ∞ ≤ 100 log(2 Q δ ′ ) λ 0 ≤ γ u 2 λ 0 , (66)
where the last inequality comes from γ u > φ L 1 . Hence it holds that S * ⊂ Ŝ and for k ∈ Ŝ, we have z * k ẑk ∈ [1 2, 2]. Next, we shall prove that, under this event, λ 1 vT -(M -M ) ŵ ŵ 2 is large (in absolute value):

λ 1 vT -(M -M ) ŵ = (z * ) T ŵ = k∈ Ŝ z * k ẑl ≥ 2 5 k∈ Ŝ(z * k ) 2 + (ẑ l ) 2 ≥ 2 5 [ w * 2 2 + ŵ 2 2 ] ≥ 4 5 ŵ 2 w * 2 ,
where we used in the first inequality that z * k ẑk ∈ [1 2, 2] and in the second inequality that S * ⊂ Ŝ. Thus, it holds that

λ 2 1 vT -(M -M ) ŵ ŵ 2 2 ≥ 16 25 w * 2 2 . ( 67
)
It remains to prove that w * 2 is large enough. Writing S * c for the complementary of

S * in Q, it holds that w * 2 2 = z * 2 2 - k∈S * c (z * k ) 2 , (68)
so that we need to upper bound the latter quantity. Write z * S * c = z *w * . Coming back to the definition of z * ,

k∈S * c (z * k ) 2 2 = k∈S * c λ 1 [v T -(M -M )] k z * k 2 ≤ λ 1 M -M z * S * c 2 2 = i∈ P k∈S * c λ 1 (M ik -m k )z * k 2 (a) ≤ 4γ 2 u P 2 λ 0 i∈ P ⎛ ⎜ ⎝ k∈S * c j∈ P λ 1 M ik -M jk ⎞ ⎟ ⎠ 2 ≤ 4γ 2 u P 2 λ 0 i∈ P ⎛ ⎜ ⎝ j∈ P λ 1 M i⋅ -M j⋅ 1 ⎞ ⎟ ⎠ 2 (b) ≤ 40γ 4 u λ 2 0 P Q ≤ 7γ 2 u λ 0 P Q 2 ≤ 1 2γ 2 u λ 2 0 M -M 2 F 2 .
In (a), we used the definition of S * . In (b), we used (43) that holds true since we are under the event Lemma C.1 and λ 0 Q ≥ 1. The last inequality comes from Condition (60), choosing κ 1 ≥ 14.

Recall that z * = vT -(M -M ). Combining (63) and (68), we deduce that

w * 2 2 ≥ 1 2γ 2 u λ 2 0 M -M 2 F , (69)
which, together with (67) and λ 0 ≥ λ 1 , yields

(M -M ) ŵ ŵ 2 2 2 ≥ vT -(M -M ) ŵ ŵ 2 2 ≥ 1 2γ 2 u M -M 2 F . (70)
Write ŵ(1) and ŵ(2) the positive and negative parts of ŵ respectively so that ŵ = ŵ(1)ŵ(2) and ŵ+ = ŵ(1) + ŵ(2) . We obviously have ŵ 2 = ŵ+ 2 . Besides, if the rows of M are ordered according to the oracle permutation, then (M -M ) ŵ( 1) and (M -M ) ŵ( 2) are nondecreasing vectors with mean zero. It then follows from Harris' inequality that these two vectors have a nonegative inner product. We have proved that

(M -M ) ŵ+ ŵ+ 2 2 2 ≥ (M -M ) ŵ ŵ 2 2 2 ≥ 1 2γ 2 u M -M 2 F . (71)
Step 4: Showing that ŵ satisfies Condition [START_REF] Saad | Active ranking of experts based on their performances in many tasks[END_REF] Recall that we assume for simplicity that λ 0 ≤ 1. First we upper bound w 2 ∞ by using (a) that ẑ is close to z * with (66), (b) that for any k ∈ Q, v T M ⋅k ≤ v 1 and (c) that λ 0 P ≥ 1:

ŵ 2 ∞ (a) ≤ 2 z * 2 ∞ + γ 2 u λ 0 (b) ≤ 2λ 2 0 v 2 1 + γ 2 u λ 0 (c) ≤ 3γ 2 u λ 2 0 P . (72)
Secondly, we lower bound w 2 2 by using (a) that S * ⊂ Ŝ and that z * k ẑk ∈ [1 2, 2], (b) that w * 2 2 captures a significant part of the L 2 norm -see (69), and (c) the Condition (60) with κ 1 ≥ 24:

ŵ 2 2 (a) ≥ 1 4 w * 2 2 (b) ≥ 1 8γ 2 u λ 2 0 M -M 2 F (c) ≥ 3γ 2 u λ 0 P . (73)
We deduce that ŵ 2 ∞ ≤ λ 0 ŵ 2 2 , which is exactly Condition [START_REF] Saad | Active ranking of experts based on their performances in many tasks[END_REF]. This shows that ŵ+ is considered for the update [START_REF] Shah | Stochastically transitive models for pairwise comparisons: Statistical and computational issues[END_REF] in the final step of the procedure Line 9 of Algorithm 2.

Step 5: upper bound of the Frobenius-norm restricted to P ′ Equipped with this bound, we are now in position to show that the set P ′ of experts obtained from P when applying the pivoting algorithm with ŵ+ ŵ+ 2 has a much smaller square norm. By Lemma B.1 used with the matrix W equal to 0 except at line i where it is equal to the vector ŵ+ ŵ+ 2 , there exists an event of probability higher than 1δ ′ such that

max i,j∈P ′ ⟨E i⋅ -E j⋅ , ŵ+ ŵ+ 2 ⟩ ≤ φ L 1 λ 0 ≤ γ u λ 0 ,
where we recall that φ l 1 is defined in [START_REF] Mao | Breaking the 1 √ n barrier: Faster rates for permutation-based models in polynomial time[END_REF]. Hence, since the vector ŵ is considered in the update [START_REF] Shah | Stochastically transitive models for pairwise comparisons: Statistical and computational issues[END_REF], we have max i,j∈P

′ ⟨Y i⋅ -Y j⋅ , ŵ+ ŵ+ 2 ⟩ ≤ γ u √ λ 0 and max i,j∈P ′ ⟨M i⋅ -M j⋅ , ŵ+ ŵ+ 2 ⟩ ≤ 2γ u 1 λ 0 . (74)
By convexity, it follows that (M (P ′ ) -M (P ′ ))

ŵ+ ŵ+ 2 2 2 ≤ 4γ 2 u 1 λ 0 P ′ ≤ 4γ 2 u 1 λ 0 P .
In light of Condition (60), this quantity is small compared to M -M 2 F : (M (P ′ ) -M (P ′ ))

ŵ+ ŵ+ 2 2 2 ≤ 1 4γ 2 u M -M 2 F , (75)
which together with (71) leads to

(M -M ) ŵ+ ŵ+ 2 2 2 -(M (P ′ ) -M (P ′ )) ŵ+ ŵ+ 2 2 2 ≥ 1 4γ 2 u M -M 2 F . (76)
Since P ′ ⊂ P , we deduce that, for any vector w ′ ∈ R q , we have

(M -M )w ′ 2 2 ≥ (M (P ′ ) - M (P ′ ))w ′ 2 . It then follows from the Pythagorean theorem that M -M 2 F -M (P ′ ) -M (P ′ ) 2 F ≥ (M -M ) ŵ+ ŵ+ 2 2 2 -(M (P ′ ) -M (P ′ )) ŵ+ ŵ+ 2 2 2 .
Then, together with (76), we arrive at

M (P ′ ) -M (P ′ ) 2 F ≤ 1 - 1 4γ 2 u M -M 2 F .
We have shown that if (60) is satisfied, then there is a contraction in the sense of (61). This in turn gives the upper bound (46) and it concludes the proof of Proposition C.3.

Proof of Lemma E.2. Recall that we consider the case λ 0 ≤ 1 and that the case λ 0 ≥ 1 is discussed in Appendix F. We start with the two following lemmas. To ease the notation, we assume in this proof that P = {1, . . . , p}, that Q = {1, . . . q}. We only consider the matrices restricted to the sets P , Q and we write E ∶= E( P , Q). Let us define J = 11 T ∈ R p×p the matrix with constant coefficients equals to 1 and A = (I p -1 p J) be the projector on the orthogonal of 1, so that E -E = AE ∈ R p×q . The two following lemmas are direct consequences of Proposition 4.1, and a discussion of the corresponding concenration inequality on random rectangular matrices can be found in Section 4. We state weaker concentration inequalities than what is proven in Proposition 4.1 in order to factorize the polylogarithmic factors and to ease the reading of the proof.

Lemma E.3. Assume that λ 0 ≤ 1 and that λ 0 (p ∨ q) ≥ 1. It holds with probability larger than

1 -δ ′ 4 that EE T -E[EE T ] op ≤ κ ′′ 0 log 2 (pq δ ′ ) [λ 0 √ pq + λ 0 p] .
Lemma E.4. Assume that λ 0 ≤ 1 and that λ 0 (p ∨ q) ≥ 1. With probability larger than 1δ ′ 4, one has for any orthogonal projection Λ ∈ R q×q satisfying rank(Λ) ≤ p that

ΛE T EΛ op ≤ κ ′′ 1 log 2 (pq δ ′ ) [λ 0 √ pq + λ 0 p] ,
Proofs of Lemma E.3 and Lemma E.4. First, we recall that for any i, k, we have that E ik = (B ikλ 1 )M ik + Ẽik , and that Ẽ is an average of 1-subGaussian random variables, as described in (30) For any u ≥ 0 we have

E[E 2u ik ] ≤ 3 u E B ik + λ 2u 0 + Ẽ2u ik ≤ 3 u 2λ 0 + u!E[e Ẽ2 ik ] ≤ 1 2 u!λ 0 1000 u , (77)
where for the last inequality we used the following inequalities:

E[e Ẽ2 ik ] ≤ u≥1 e -λ 0 λ u 0 u! e 1 u ≤ λ 0 e .
Hence condition ( 24) is satisfied with K = 1000 and σ 2 = λ 0 for the coefficients of E. We just apply Proposition 4.1 with X = E for Lemma E.3. For Lemma E.4, we apply Proposition 4.1 with X = E T and we remark that

ΛE T EΛ 2 op ≤ 2 ΛE T E -E[E T E]Λ 2 op + 2 E[E T E] 2 op
together with the fact that E[E T E] 2 op ≤ c ′ λ 0 p for some numerical constant c ′ . Remark that since we assume in Lemma E.2 that λ 0 p ≥ 1, it holds that √ λ 0 p ≤ λ 0 p and √ λ 0 q ≤ λ 2 0 √ pq, so that both upper bounds of Lemma E.3 and Lemma E.4 reduce -up to logarithmic factors -to λ 0 √ pq + λ 0 p. We write for short in the following

F ∶= F (p, q, λ 0 , δ ′ ) = log 2 (pq δ ′ )[λ 0 √ pq + λ 0 p] , (78)
and

κ ′′ 2 = 8(κ ′′ 0 ∨ κ ′′ 1 ). Now let us write AY = λ 1 AM + AE , so that, for any v ∈ R p , recalling that AY = Y -Y , v T AY 2 2 = λ 2 1 v T AM 2 2 + v T AE 2 2 + 2λ 1 ⟨v T AE, v T AM ⟩ , which, in turn, implies that v T AY 2 2 -λ 2 1 v T AM 2 2 -E v T AE 2 2 ≤ v T AE 2 2 -E v T AE 2 2 + 2λ 1 v T AM E T (Av) (a) ≤ A(EE T -E[EE T ])A op + 2λ 1 AM E T E(AM ) T 1 2 op ≤ EE T -E[EE T ] op + 2λ 1 AM op ΛE T EΛ 1 2 op ,
• If λ 0 > 16 log(5nd δ), we show that the event {r (s)

ik ≥ λ 0 2} holds true for all i, k, s with high probability. Working conditionally to this event, we use the decomposition Y = M + Ẽ and we show that the noise Ẽ has 2 λ 0 -subGaussian independent coefficients. The rationale behind using Ẽ when λ 0 is large is that Ẽik takes advantage of the mean of 2 λ 0 subGaussian variables with high probability. Let r (s) min = min i,k r (s) ik be the minimum number of observation at positions (i, k) in N s -see [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF]. In the case λ 0 > 16 log(5nd δ), the following lemma states that with high probability, we observe all the coefficients for all sample s in the full observation regime.

Lemma F.1. Assume that λ 0 ≥ 16 log(5nd δ). The event {r (s) min ≥ λ 0 2} holds simultaneously for all sample s with probability at least 1 -5T δ.

Proof of Lemma F.1. We apply Chernoff's inequality -see e.g. section 2.2 of [START_REF] Massart | Concentration inequalities and model selection[END_REF] -to derive that for any i, k

P(r (s) ik ≤ λ 0 2) ≤ exp(- 1 8 λ 0 ) ≤ δ (nd) , (80)
where we use the inequality (1log(2)) 2 ≥ 1 8. We conclude with a union bound over all coefficients in [n] × [d] and all 5T samples.

Let us now omit the dependence of E and Ẽ in the sample s. In what follows, use that the coefficients of E are 5-subGaussian, which is a consequence of the fact that E ik is the sum of a centered variable bounded by 1 and a 1-subgaussian random variable Ẽik , so that by Cauchy-Schwarz and the Hoeffding inequality we have

E[exp(xE ik )] ≤ exp(4x 2 8) exp(4x 2 2) = exp(5 4x 2 ) . (81)
Under the event of Lemma F.1, we use that Ẽik is λ 0 2-subGaussian, as an average of at least 2 λ 0 random variables that are 1-subGaussians:

E[exp(x Ẽik )] ≤ exp( 1 λ 0 x 2 ) , (82)

F.1. Adjustements for the general analysis

We first make the changes that should be done in Appendix A to have a proper proof in the case λ 0 ≥ 1.

If λ 0 ∈ [1, 16 log(5nd δ)], we simply replace λ 0 by 1 λ 0 in the upper bound of (31) for the event ξ in Lemma A.1. In the proof of the restated Lemma A.1, we can replace the inequality (37) by

⟨E, W ⟩ ≤ 10 W 2 F log 2 δ ′ , (83)
for any matrix W ∈ R n×d , with probability at least 1δ ′ . We can then obtain 1 λ 0 instead of λ 0 simply by using that φ L 1 √ λ 0 ≥ φ L 1 , recalling that φ L 1 is defined in [START_REF] Mao | Breaking the 1 √ n barrier: Faster rates for permutation-based models in polynomial time[END_REF]. If λ 0 > 16 log(5nd δ), we say that we are under event ξ if the event of Lemma F.1 holds and (31) holds for all pairs (Q, w), replacing E by Ẽ, and λ 0 by 1 λ 0 . The proof of the new version of Lemma A.1 lies in the Hoeffding inequality applied to Ẽ under the event of Lemma F.1, leading to the subsequent equation:

⟨ Ẽ, W ⟩ ≤ 4 W 2 F λ 0 log 2 δ ′ , (84)
for any matrix W ∈ R n×d , with probability at least 1δ ′ . This equation then replaces (37).

Since the projection of M + E ′ on isotonic matrices is equal to the columnwise projection on isotonic vectors, it holds that sup M ∈C iso (n,d)

E P iso (M +E ′ )-M 2 F = d sup M ∈C(n,1) E P iso (M ⋅1 + E ′ ⋅1 )-M ⋅1 2
F , where we also use the notation P iso for the projector on isotonic vectors. The rate of estimation in L 2 norm of an isotonic vector with bounded total variation partial observation can be found in [START_REF] Zhang | Risk bounds in isotonic regression[END_REF], with V ∶= 1 and σ 2 ∶= 1 λ. Hence, we obtain that sup M ∈C(n,1) E P iso

(M ⋅1 + E ′ ⋅1 ) -M ⋅1 2 F ≤ C 1 n 1 3 λ 2 3
. Upper bounding the first term in (86) with a quantity of order ρ perm ≤ 2ρ reco by Theorem 2.2 concludes the proof.

Proof of Corollary 2.5. We follow the same steps as in Corollary 2.4. Assume that π

* = η * = id, E ′ = Y (3)
π-1 η-1 -M , and let P biso be the projector on bi-isotonic matrices. We have that ( Mbiso

) π η -M 2 F ≤ 4 M π-1 η-1 -M 2 F + 2 P biso (M + E ′ ) -M 2 F . (87)
M is isotonic in both directions so that we can apply Theorem 2.2 in rows and columns. After the first two steps of the above procedure, we obtain two estimator π, η that satisfy

sup π * ,η * ∈Πn M ∶ M π * -1 η * -1 ∈C biso E M π-1 η-1 -M π * -1 η * -1 2 F ≤ C ′′ log C ′′ (n)n 7 6 λ -5 6 . (88)
The second term of (87) is the risk of a bi-isotonic regression by least square, and is smaller than n λ ≤ n 7 6 λ -5 6 -see e.g. [START_REF] Mao | Towards optimal estimation of bivariate isotonic matrices with unknown permutations[END_REF].

Appendix H: Proof of the minimax lower bound

Proof of Theorem 2.1. Since ρ perm (n, d, λ) is nondecreasing with n and d, we can assume without loss of generality that both n and d express as a power of 2.

The following proof is strongly related to the proof of Theorem 4.1 in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF]. While a worst case distribution is defined on the set of matrices that have nondecreasing rows and nondecreasing columns in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF], we aim here at defining a worst case distribution on matrices only have nondecreasing columns. Since the isotonic model is less constrained than the bi-isotonic model studied in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF], the permutation estimation problem is statistically harder, and the lower bound has a greater order of magnitude.

As in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF], the general idea is first to build a collection of prior ν G indexed by some G ∈ G on M , then to reduce the problem to smaller problems and finally to specify the prior in function of the regime in n, d and λ. By assumption, the data y t is distributed as a normal random variable with mean M xt and variance 1, conditionally on M and x t . We write as in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF]

P (full) G and E (full) G
the corresponding marginal probability distributions and expectations on the data (x t , y t ). Our starting point is the fact that the minimax risk (4) is higher than the worst Bayesian risk:

R * perm (n, d, λ) ≥ inf π sup G∈G E full G M π-1 -M π * -1 2 F . (89)
Step 1: Construction of the prior distribution on M Let p ∈ {2, . . . , n} and q ∈ [d] be two powers of 2 to be fixed later, and G

∶= [(ι-1)p+1, ιp],

for ι ∈ {1, . . . , n p}. The general idea is to build a simple prior distribution on isotonic matrices in R G (ι) ×d , and to derive a prior distribution on isotonic matrices in R n×d by combining n p independent simple prior distributions defined on each strip R G (ι) ×d .

Let w ∈ R n be a vector that is constant on each group G (ι) = [(ι -1)p + 1, ιp] and that has linearly nondecreasing steps:

w i = ⌊ i p ⌋ p 4n ∈ [0, 1 4] . (90)
Letting

1 [d] be constant equal to 1 in R d , we define M = w1 T [d] + υ √ pλ B (full) , (91)
where the random matrix B (full) ∈ {0, 1} n×d is defined as in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF]. We recall the definition of its distribution in what follows for the sake of completeness. Consider a collection G of subsets of [p] with size p 2 that are well-separated in symmetric difference as defined by the following lemma.

Lemma H.1. There exists a numerical constant c 0 such that the following holds for any even integer p. There exists a collection G of subsets of [p] with size p 2 which satisfies log( G ) ≥ c 0 p and whose elements are p 4-separated, that is G 1 ∆G 2 ≥ p 4 for any

G 1 ≠ G 2 .
The above result is stated as is in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF] and is a consequence of Varshamov-Gilbert's lemma -see e.g. [START_REF] Tsybakov | Introduction to Nonparametric Estimation[END_REF].

For each ι ∈ [n p], we fix a subset G (ι) from G, and its translation G t(ι) = {(ι -1)p + x ∶

x ∈ G (ι) } ⊂ G (ι) . The experts of G t(ι) will correspond the p 2 experts in G (ι) that are above the p 2 experts in G

∖ G t(ι) . We write G = (G t(1) , . . . , G t(n p) ) and G the corresponding collection of all possible G. Given any such G, we shall define a distribution ν G of B (full) , and equivalently of M by (91). For ι ∈ [n p], we sample uniformly a subset Q (ι) of q questions among the d columns. In each of these q columns, the corresponding rows of B (full) are equal to one. More formally, we have

B (full) = n p ι=1 1 G t(ι) 1 Q (ι) . ( 92
)
As mentioned above, the definition of B (full) is the same as in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF], if d is set to be equal to d. They define a block constant constant matrix when d < d to get an appropriate prior distribution for bi-isotonic matrices, but we do not need to do that here since we do not put any constraint on the rows of M .

The matrix M defined in (92) is isotonic up to a permutation of its rows and has coefficients in [0, 1], if the following inequality is satisfied.

υ √ pλ ≤ p 8n . ( 93
)
This constraint is strictly weaker than its counterpart (149) in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF], and this is precisely what makes the lower bound in the isotonic setting larger than the lower bound in the bi-isotonic setting of [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF]. Our purpose will be to wisely choose parameters p, q and υ > 0 to maximize the Bayesian risk (89) with ν G .

Step 2: Problem Reduction

In what follows, we use the same reduction arguments as in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF]. Using the notation of [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF], we write P for the probability distribution and corresponding expectation of the data (x t , y t ), when M is sampled according to ν G . Since the distribution of the rows of M in G t(ι) only depend on G t(ι) , we write ν G t(ι) for the distribution of these rows. We also write

P (full)
G t(ι) and E (full) G t(ι) for the corresponding marginal distribution and corresponding expectation of the observations (x t , y t ) such that (x t ) 1 ∈ G t(ι) . By the poissonization trick, the distribution

P (full) G
is a product measure of P (full) G t(ι) for ι = 1, . . . , n p. Let π be any estimator of π * . Let us provide more details than [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF] to prove that π can be modified into an estimator π satisfying π(G If N (π) > 0, then there exists ι 0 and i 0 ∈ G (ι 0 ) such that π(i 0 ) ∈ G (ι 1 ) with ι 1 ≠ ι 0 . Then, π being a permutation, we consider its associated cycle containing i 0 , which we denote by (i 1 , . . . , i K ). Let (i ′ 1 , i ′ 2 , . . . , i ′ L ) be the elements of this cycle such that π(i ′ l ) ∈ G (ι l ) , where ι l satisfies i ′ l ∈ G (ι l ) . Then it holds that for any l = 1, . . . , L -1, π(i ′ l ) ∈ G (ι l+1 ) , and π(i ′ L ) ∈ G (ι 1 ) .

We now define π′ (i) = π(i) for all i, except on the cycle (i ′ 1 , . . . , i ′ L ) where we set π′ (i ′ l ) = π(i ′ l-1 ). Then, we easily check that N (π ′ ) = N (π) -L < N (π), and that

M π′-1 -M π * -1 2 F ≤ M π-1 -M π * -1 2
F if condition (93) is satisfied. We can therefore restrict ourselves to estimators π such that π(G (ι) ) = G (ι) for all ι. There is however still another catch to obtain the same lines as in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF]. Indeed, the restriction π(ι)

of π to G (ι) is measurable with respect to the observation Y , but not necessarily to Y (G

).

Still, this restriction can be writen as π(ι) = π(ι) (Y (G

(ι) ), Y ([n] ∖ G (ι)
)), and, for any α > 0, there exists y * (ι) (α) such that ), y * (ι) (α)) is measurable with respect to Y (G

). Since it is possible such a stable estimator for any α > 0, we finally obtain the inequality

R * perm (n, d, λ) ≥ inf π∶ π(G (ι) )=G (ι) sup G∈G n p ι=1 E (full) G M π-1 -M π * -1 G (ι) 2 F ≥ n p ι=1 inf π(ι) sup G t(ι) E (full) G t(ι) M π(ι)-1 -M π * -1 G (ι) 2 F .
The problem of estimating the permutation π * is now broken down into the n p smaller problems of estimating the subsets G t(ι) ⊂ G (ι) . The square Euclidean distance between to experts in G (ι) of experts is 0 is they are both either in or not in G t(ι) and it is equal to qυ 2 pλ otherwise. Let us focus on the easier problem of estimating the subsets G t(ι) and define Ĝt(ι) the set of the p 2 experts that are ranked above according π(ι) . Then, we have that

M π(ι)-1 -M π * -1 G (ι) 2 F = qυ 2 pλ Ĝ(ι) ∆G t(ι) ≥ qυ 2 4λ 1{ Ĝ(ι) ≠ G t(ι) } ,
where the last inequality comes from the construction of the sets G t(ι) by Lemma H. Ĝ(1) ≠ G t (1) .

Consider the p × d matrices N and Y ↓ defined by

N ik = t 1 xt=(i,k) ; Y ↓ ik = t 1 xt=(i,k) (y t -w i ) ,
where w is defined in (90). To simplify the notation, we write henceforth G and Ĝ for G t (1) and Ĝ(1) respectively. Letting P G for the corresponding marginal distribution of N and Y ↓ , the same sufficiency argument as in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF] gives that

inf Ĝ sup G P (full) G Ĝ ≠ G = inf Ĝ sup G P G Ĝ ≠ G .
We finally obtain the following inequality:

R * perm (n, d, λ) ≥ nqυ 2 4pλ inf Ĝ sup G P G Ĝ ≠ G . (95)
Let P 0 be the distribution on N and Y ↓ corresponding to the case υ = 0. The entries of N of are independent and follow a poisson distribution of parameter λ. Conditionally to N ik , we have Y ↓ ik is a gaussian variable with mean 0 and variance N ik . Then, we deduce from Fano's inequality [START_REF] Tsybakov | Introduction to Nonparametric Estimation[END_REF] that

inf Ĝ sup G∈G P G ( Ĝ ≠ G) ≥ 1 - 1 max G∈G KL(P G P 0 ) log( G ) , (96)
where KL(. .) stands for the Kullback-Leibler divergence. The following lemma gives an upper bound of these Kullback-Leibler divergences. It can be found in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF], with the slightly stronger assumption that pλ ≥ 1.

Lemma H.2 (Lemma J.2 of [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF]). There exists a numerical constant c 1 such that the following holds true. If υ 2 ≤ 1 ∧ pλ, then for any G ∈ G, we have

KL(P G P 0 ) ≤ c 1 υ 2 q 2 d .
The proof of Lemma H.2 can be found in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF], with ñ ∶= p and d = d. The slighlty stronger assumption that pλ ≥ 1 made in Lemma J.2 in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF] is in fact not necessary. Indeed, it is only used to prove that I ∶= λp(e υ 2 (λp) -1) ≤ c ′ 1 υ 2 in the proof of Lemma J.2 in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF], and this inequality remains valid under the assumption of Lemma H.2, that is u 2 ∶= υ 2 (λp) ≤ 1.

Step 3: Choice of suitable parameters p, q and υ By combining (95), (96), with Lemma H.2 and the different constraints on the parameters (93), we directly obtain the following proposition.

Proposition H.3. There exists a numerical constant c such that if p ∈ {2, . . . , n}, q ∈ {1, . . . , d} are dyadic integers, and υ satisfy the following condition:

υ ≤ c 1 ∧ pλ ∧ √ pd q ∧ √ λ p 3 2 n , (97)
then we have

R * perm (n, d, λ) ≥ c nqυ 2 pλ . (98)
The above proposition being a direct consequence of what preceeds it, we consider that it does not require a proof. Let us now apply Proposition H.3 for different parameters p, q and υ to conclude the proof of Theorem 2.1.

First, using the lower bound in the bi-isotonic case -see Theorem 4.1 of [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF], we have for some constant c ′ that R * perm (n, d, λ) ≥ c ′ (n λ ∧ nd) .

In what follows, we write ⌊x⌋ dya for the greatest integer that is a power of two and smaller than x. Let us consider the following inequality:

λ ≥ 1 d ∨ n 2 d 3 .
(100)

In the case where (100) is not satisfied, then n d λ ∧ n 2 3 √ dλ -5 6 ≤ n λ ∧ nd and the lower bound of Theorem 2.1 is proven by (99).

We subsequently assume that (100) is satisfied.

Case 1: λn ≤ 1. In this case, we choose q = ⌊ d λ ⌋ dya and p = n 2. We have that q ∈ {1, . . . , d} since λ ≤ 1 in that case and by assumption (100), λ ≥ 1 d. We deduce from Proposition H.3 applied with v c = √ pλ = √ pd q that R * perm (n, d, λ) ≥ c ′′ n d λ .

Case 2: λ ∈ [ 1 n , 8n 2 ]. In this case, we choose q = ⌊ n

Corollary 2 . 5 .

 25 Assume that λ ∈ [1 n, 8n 2 ]. There exists a universal constant C ′′ such that sup π * ,η * ∈Πn

Algorithm 2

 2 SLR((Y (s) ) s=1,...,5 , W, γ, i, G, P ) Require: 6 samples (Y (s) )s=1,...,5, a weighted directed graph W, a threshold γ such that G(W, γ) is acyclic and an expert i ∈ [n]. G and P are shorthands for the thresholded graph G(W, γ) and the neighborhood N (G, i). Ensure: An update of W 1: for h ∈ H do 2:

  be the sets of indices l = 1, . . . , L whose corresponding group size P l belongs to [p, 2p). The two upper bounds implied by (44) and (46) both depend on the selected subset of columns, which is included in Q * h l under the event of Lemma C.1.The following lemma provides an upper bound on the sum over l ∈ L(p) of the size of the sets Q * h l (φ) defined in (41), for any φ > 0. Lemma C.4. For any φ ≥ 1 and any h ∈ H, it holds that l∈L(p)

2 F

 2 for all ι = 1, . . . , n p, and reducingthe loss M π-1 -M π * -1 2F ≤ M π-1 -M π * -1 almost surely, for all possible prior ν G . For that purpose, we introduceN (π) =

E 2 F

 2 (full) G M π(ι)-1 -M π * -1 2 F ≥ E (full) G M π(ι)-1 (α) -M π * -1α ,where π(ι) ∶= π(ι) (Y (G (ι)

√ d λ 5 6 ..

 6 from (100) that q ≤ d. Since λ ∈ [ 1 n , 8n 2 ], we also necessarily have that that q ≥ 1, p ≥ 2 and p ≤ n. Applying the above proposition with υ c = 1 = √ pd q = √ λp 3 2 n, we deduce thatR * perm (n, d, λ) ≥ c ′′ n 2 3Case 3: λ ≥ 8n 2 . When λ satisfies this condition that is out of the scope of Theorem 2.1 but discussed below Theorem 2.1, we choose q = ⌊ √ d⌋ dya and p = 2. Applying the above proposition with υ c = 1, we deduce thatR * perm (n, d, λ) ≥ c ′′ n √ d λWe have proved that for any n, d and λ, we have the lower boundR * perm (n, d, λ) ≥ c ′′ n d λ ∧ n 2 3 √ d λ 5 6 ∧ n √ d λ + n λ ∧ nd .This concludes in particular the proof of Theorem 2.1, stated for λ ∈ [1 d, 8n 2 ].

  Assume that λ ∈ [1 d, 8n 2 ] is fixed and that we are given N = P oi(λnd) independent observations under model[START_REF] Bellec | Concentration of quadratic forms under a bernstein moment assumption[END_REF]. Namely, we observe (x t , y t ) t=1,...,N where x t is sampled uniformly in [n] × [d] and y t = M xt + ε t conditionally to x t . The following theorem states that ρ perm is a lower bound on the maximum risk of permutation estimation for all n, d, λ ∈ [1 d, 8n 2 ], up to some numerical constant.

	2.1. Minimax lower bound for permutation estimation
	Theorem 2.1. There exists a universal constant c > 0 such that, for any n ≥ 2, d ≥ 1, and λ ∈ [1 d, 8n 2 ], we have
	R * perm (n, d, λ) ≥ cρ perm (n, d, λ) .

The authors consider the isotonic model as a subcase of a seriation model, where each columns of M π * -1 is only assumed to be unimodal.

We are indeed mostly interested in the more realistic sparse observation regime (meaning λ ≤ 1). The case λ ≤ 1 d leads to the trivial minimax bound of order nd for both reconstruction and estimation, as in this case we have less than one observations per expert on average. As for the case λ > 1 d but λ ≤ 1 n, we have less than one observation per question on average, and this leads to a minimax risk of order n d λ for permutation estimation and of order nd for matrix recontruction.

Appendix E: Proof of Proposition C. [START_REF] Bengs | Preference-based online learning with dueling bandits: A survey[END_REF] Let us fix any l ∈ {1, . . . , L} and h ∈ H. Since l, h and Qh l are fixed in this proof, we simplify the notation and we write (P ′ , P , Q) = (P ′ l , P h l , Qh l ) and M ∶= M ( P , Q) and M (P ′ ) ∶= M (P ′ , Q). We also fix δ ′ = δ (L H ), where we recall that L ≤ n is the number of groups.

Let us assume that

for some constant κ 1 to be fixed later. In what follows, we show that under assumption (60) for some large enough numerical constant κ 1 , we necessarily have that the square norm of P ′ is a contraction of the square norm of P , that is

Step 1: control of the vector v

First, the following lemma states that the first singular value of (M -M) is, up to polylogarithmic terms, of the same order as its Frobenius norm. This is mainly due to the fact that the entries of M lie in [0, 1] and that M -M is an isotonic matrix.

Lemma E.1 (Lemma E.4 in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF]). Assume that M -M F ≥ 2. For any sets P and Q, we have

This lemma was already stated and proved as Lemma E.4 in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF], recalling that γ u > φ L 1 ≥ 8 log(nd) -see ( 9) and [START_REF] Mao | Towards optimal estimation of bivariate isotonic matrices with unknown permutations[END_REF].

-

) 2 2 , where the argmax is taken over all v in P .

Lemma E.2. Assume that λ 0 P ≥ 1. There exists a numerical constant κ ′ 0 such that if

then, with probability higher than 1δ ′ , we have

In light of Lemma E.1 and Condition (60), the Condition (62) in Lemma E.2 is valid if we choose κ 1 in Proposition C.3 such that κ 1 ≥ 16κ ′ 0 . Consequently, there exists an event of probability higher than

Step 2: control of the vector v-

Where we define Λ ∈ R d×d as the orthogonal projector on the image of ker(AM ) ⊥ which is of rank less than p. For (a), we used the fact that A is contracting the operator norm as an orthogonal projector so that Av 2 ≤ 1. We now apply Lemma E.3 and Lemma E.4 together with the fact that λ 1 ≤ λ 0 , and we obtain with probability at least 1δ ′ 2 that

where F is defined in (78). In the same way, we have that, with probability larger than 1-δ ′ 2, sup

for some numerical constant κ ′′ 3 . Putting everything together we conclude that, on an event of probability higher than 1δ ′ , we have simultaneously for all v ∈ R p with v 2 ≤ 1 that

We deduce that on the same event:

The aim of this section is to provide an extension of the proof of Theorem 2.2 to the case λ 0 ≥ 1. Recall that we fix δ to be a small probability the proof of Theorem 2.2, and that E and Ẽ are the matrices defined in ( 29) and (30) by

In what follows, we consider the two subcases where λ 0 > 16 log(5nd δ) or λ 0 ≤ 16 log(5nd δ), which essentialy rely on the two following ideas:

• If λ 0 ≤ 16 log(5nd δ), we use the fact that the coefficients of E defined in (29) are 5-subGaussian together with the same signal-noise decomposition Y = λ 1 M + E as in the proofs when λ 0 ≤ 1. The difference from the case λ 0 ≤ 1 lies in the application of subGaussian inequalities of E ik instead of Bernstein inequalities as in (37).

F.2. Adjustments to the proofs of Proposition A.6

We now adapt the proofs in Appendix C of Proposition A.6 to the case λ 0 ≥ 1.

All the lemmas of Appendix C can be stated as is for any λ 0 ≥ 1, and the only adjustments concern the proofs of Lemma C.1, Lemma C.2 and Proposition C.3.

F.2.1. Adjustments in the proofs of Lemma C.1 and Lemma C.2

Consider the proof of Lemma C.1. First, if λ 0 ≥ 16 log(5nd δ), we place ourselves under the event Lemma F.1 and replace λ 1 by 1 and all the E by Ẽ. Instead of inequality (55), we use the fact that the coefficients of Ẽ are 2 λ 0 -subGaussian -see (82) -leading to the following inequality with probability at least 1δ:

for some numerical constant κ ′ 0 . The rest of the proof remains unchanged.

we use the fact that E has 5-subGaussians coefficients -see (81) and we do not divide by λ 0 in (57) -see the definition of ∆ [START_REF] Tropp | An Introduction to Matrix Concentration Inequalities[END_REF].

Concerning Lemma C.2, the adjustments are the same as for Lemma A.1, namely working under the event of Lemma F.1 and we replacing E by Ẽ, λ 0 by 1 λ 0 and λ 1 by 1 if λ 0 ≥ 16 log(5nd δ), and using the fact that the coefficient of E are 5-subGaussians -see (81

F.2.2. Adjustments in the proof of Proposition C.3

We now adapt the proofs in Appendix E of Proposition C.3 to the case λ 0 ≥ 1. First, Lemma E.2 can be stated as is, and its proof when λ 0 ≥ 1 is directly implied by Lemma E.5 in [START_REF] Pilliat | Optimal permutation estimation in crowdsourcing problems[END_REF] with Θ ∶= M either conditionally on Lemma F.1 with noise N ∶= Ẽ and ζ 2 ∶= 2 λ 0 when λ 0 ≥ 16 log(5nd δ) or with noise N ∶= E and ζ 2 ∶= 5 when λ 0 ≤ 16 log(5nd δ).

Secondly, remark that if λ 0 ≥ 1, it holds that v-= v and that Condition (16) on ŵ is automatically satisfied, so that step 2 and step 4 can be removed from the proof in that case. For Step 3 and 5, we do the following adjustments:

If λ 0 ∈ [1, 16 log(5nd δ)], the proof remains unchanged except that we use that the coefficients of E are 5-subGaussian -see (81).

If λ 0 ≥ 16 log(5nd δ), we work conditionnally on the event of Lemma F.1 and we replace λ 1 by 1 and E by Ẽ. The subgaussian concentration bound on Ẽ (84) allows us to replace λ 0 by 1 λ 0 in the equations from (64) to (69).

Appendix G: Proof of Corollaries 2.4 and 2.5

Proof of Corollary 2.4. Assume that π * = id for simplicity. Let P iso be the projector on the set of isotonic matrices, and

π-1 -M π-1 so that Miso = P iso (M π-1 + E ′ ). Remark that the loss can be decomposed as

F . Using the non-expansiveness of P iso and the triangular inequality as in the proof of proposition 3.3 of [START_REF] Mao | Towards optimal estimation of bivariate isotonic matrices with unknown permutations[END_REF], we deduce that

Appendix I: Proof of Proposition 4.1

Let us introduce

Lemma I.1. There exists a numerical constant κ ′′′ 3 such that for any x ∈ [0, (κ ′′′ 3 (σ 2 r Λ + K 2 log(q))) -1 ], we have

Moreover, applying the Matrix Chernoff techniques for the independent matrices P k (see lemma 6.12 and 6.13 of [START_REF] Wainwright | High-dimensional statistics: A non-asymptotic viewpoint[END_REF]), we have for any t > 0 that log(P(

Applying Lemma I.1, it holds for any x ∈ [0, (κ ′′′ 3 (σ 2 r Λ + K 2 log(q))) -1 ] that

where in the last inequality we used the fact that for any a ≥ 1 and u > 0, log(a + u) ≤ log(a) + u a.

Hence we obtain log(P(

.

We deduce that with probability at least 1δ, it holds that

for some numerical constant κ.

Proof of Lemma I.1. Since ΛX ⋅k X T ⋅k Λ op = ΛX ⋅k 2 2 , we state the following lemma controlling the moment generating function of the L 2 norm of the projection ΛX ⋅k : Lemma I.2. There exists a numerical constant κ ′′′ 0 such that for any x ≤ 1

Now we define the event ξ op ∶= {max k=1,...,d ΛX ⋅k 2 2 ≤ κ ′′′ 0 (σ 2 r Λ + K 2 log(q 3 ))}, where κ ′′′ 0 is the numerical constant given by Lemma I.2. Applying the same lemma together with the Chernoff bound, a union bound over all k = 1 . . . d gives

We consider in what follows the relation order ⪯ induced by the cone of nonegative symetric matrices S + n , namely X ′ ⪯ X ′′ if and only if X ′′ -X ′ ∈ S + n . Under the event ξ op , it holds that for any u ≥ 2,

for some numerical constant κ ′′′ 1 (depending on κ ′′′ 0 ). In the third inequality we used the definition of ξ op the fact that E[ ΛX ⋅k 2 2 ] ≤ κ ′′′ 0 σ 2 r Λ . We now give an upper bound of E[P 2 k ] op , which is the operator norm of the variance of P k as defined in section 6 in [START_REF] Wainwright | High-dimensional statistics: A non-asymptotic viewpoint[END_REF]. Remark that since any matrix U ∈ R q×q satisfies U ΛU T ⪯ U U T , we have that P

The off diagonal terms are zero, and the i th diagonal element satisfies:

By assumption [START_REF] Zhang | Risk bounds in isotonic regression[END_REF], the first term of (102) satisfies

The second term of (102) is smaller than σ 4 p, still by assumption [START_REF] Zhang | Risk bounds in isotonic regression[END_REF]. Hence we have some numerical constant κ ′′′ 2 that

. Now, by the definition of the exponential of matrices, the triangular inequality and the fact that P k is centered, we have

By definition of ξ op together with the upper bound of the variance of

for some numerical constant κ ′′′ 3 . We now control the second term of (103) under the complementary event ξ op , for any x ∈ [0, (2κ ′′′ 0 (σ 2 r Λ + K 2 log(q))) -1 ]:

where in (a) we used the cauchy-schwarz inequality for real random variables and in (b) we applied Lemma I.2.

Proof of Lemma I.2. We use the result of [START_REF] Bellec | Concentration of quadratic forms under a bernstein moment assumption[END_REF] which is a generalization of the Hanson-Wright inequality to random variables with coefficients with bernstein's moments.

[Assumption 1 of [START_REF] Bellec | Concentration of quadratic forms under a bernstein moment assumption[END_REF]] is satisfied with parameters σ 2 and K, and we have the following upper bound on the moment generating function of the quadratic form ΛX T

for any x satisfying condition (6) of [START_REF] Bellec | Concentration of quadratic forms under a bernstein moment assumption[END_REF], that is 128x Λ op K 2 ≤ 1. For the last inequality, we used the fact that Λ 2 F = rank(Λ). We obtain the result by choosing κ ′′′ 2 = κ ′′′ 1 ∨ 128.