Phase Transitions in Approximate Ranking

arXiv:1711.11189v1 [] 30 Nov 2017

Chao Gao
University of Chicago
chaogao@galton.uchicago.edu
December 1, 2017
Abstract
We study the problem of approximate ranking from observations of pairwise interactions. The goal is to estimate the underlying ranks of n objects from data through
interactions of comparison or collaboration. Under a general framework of approximate
ranking models, we characterize the exact optimal statistical error rates of estimating
the underlying ranks. We discover important phase transition boundaries of the optimal
error rates. Depending on the value of the signal-to-noise ratio (SNR) parameter, the
optimal rate, as a function of SNR, is either trivial, polynomial, exponential or zero. The
four corresponding regimes thus have completely different error behaviors. To the best of
our knowledge, this phenomenon, especially the phase transition between the polynomial
and the exponential rates, has not been discovered before.
Keywords: minimax rate, permutation, sorting, pairwise comparison, latent space.

1

Introduction

Given data {Xij }1≤i6=j≤n , we study recovery of the underlying ranks of the n objects in the
paper. The observation Xij can be interpreted as the outcome of an interaction between i
and j. For example, in sports, Xij can be the match result of a game between team i and
team j. In a coauthorship network, Xij can be the number of scientific papers jointly written
by author i and author j. We consider a very general approximate ranking model in the
paper. It imposes the mean structure
EXij = µr(i)r(j) .
Here r(i) ∈ {1, 2, ..., n} is the rank of object i. The interaction outcome µr(i)r(j) is only
determined by the latent positions of i and j, and Xij is thus a noisy measurement of µr(i)r(j) .
The goal of approximate ranking is to recover the underlying r(i) for each i ∈ {1, 2, ..., n}.
In the literature, the problem of exact ranking is a well studied topic, especially in the
settings of pairwise comparison with Bernoulli outcomes. The goal of exact ranking assumes
that the underlying r is a permutation, and therefore estimating r is equivalent to sorting the
1

n objects, which gives an alternative name “noisy sorting” to such a problem [3]. We refer
the readers to [14, 16, 15, 12] and references therein for recent developments in this area.
In contrast, this paper studies the approximate ranking problem. We do not impose
the constraint that r must be a permutation. More generally, we allow any r that satisfies
r(i) ∈ {1, 2, ..., n} for each entry plus some moment conditions. This allows possible ties in
the rank, and the ranks of the n objects do not necessarily start from 1 or end at n. The
number r(i) should instead be interpreted as a discrete latent position of object i. Such
an approximate ranking setting is more natural for many applications. For example, it is
conceivable in certain situations that there is a subset of objects that may behave very
similarly through pairwise interactions. As a consequence, we can allow the same value r(i)
for all i in the group in such a scenario. Moreover, the numbers r(i)’s in the approximate
Phase
Transitions
in Approximate
Ranking
ranking
setting not
only reflect the
order of the n objects, but they also carry information
about their relative
differences
through the interpretation of latent positions. These features
Chao
Gao
Phase TransitionsPhase
in Approximate
TransitionsRanking
in Approximate Ranking
and advantages distinguish the approximate ranking problem from the exact ranking problem
University of Chicago
Chao Gao
studied inchaogao@galton.uchicago.edu
the literature.
Chao Gao
Phase
Transitions
in Approximate
Ranking
The mainUniversity
contribution
of the
paper is the
exact
characterization
of the optimal
statistical
of Chicago
University of Chicago
Phase
Transitions
in
Approximate
Ranking
chaogao@galton.uchicago.edu
error of the
approximate
ranking
problem.
Given
an
estimator
r̂,
we
measure
the error
November 26, 2017chaogao@galton.uchicago.edu
Chao Gao
Phase Transitions in Approximate
1 Pn Ranking
2
through the loss function `2 (r̂, r) = n i=1 (r̂(i) − r(i))
. With the signal parameter β 2 and
Chao Gao
University
of Chicago
November
26,
2017
November
26, 2017
Chao
the noise level σ 2Abstract
definedPhase
laterGao
in (3) and
(2),
we show
that
the optimal rate of `2 (r̂, r) is
Transitions
in Approximate
Ranking
chaogao@galton.uchicago.edu
University of Chicago
2
abstract. a function of the signal-to-noise ratio parameter SNR = β 2 . Our results are summarized
chaogao@galton.uchicago.edu
University of Chicago
4σ
Abstract
Keywords: minimax rate, permutation, sorting, pairwise comparison,
latent
space.
Chao
Gao
chaogao@galton.uchicago.edu
in Figure 1. According
to the plotAbstract
in Figure
1,
the optimal
error
exhibits interesting and
November
26, 2017
abstract.

abstract.

University ofNovember
Chicago 26, 2017

Keywords: minimax rate, permutation, sorting, pairwise comparison, latent space.
Introduction
Keywords: minimax rate, permutation,
sorting, pairwise comparison, latent space.
chaogao@galton.uchicago.edu

1

November 26, 2017

1

1
SNR
1 Introduction
abstract.
1
Abstract
c1 SNR)
c2 exp(
SNR
Keywords:
c1
abstract.

Introduction

c1

Abstract

Abstract

abstract.

Novemberminimax
26, 2017
Keywords:
rate, permutation, sorting, pairwise comparison, latent space.

1
minimax rate, permutation, sorting, pairwise comparison, latent space.
SNR

1 Introduction
Abstractlatent space.
Keywords: minimax rate, permutation, sorting,
pairwise comparison,
c2 exp( SNR)
1
1

c2 exp( SNR)
abstract.Introduction

error

1
c1
1
SNR
Keywords: minimax rate, permutation, sorting, pairwise
comparison, latent space.
1 Introduction
c1
1
SNR
n 2
1
1
c2 exp( SNR)
c1
SNR
1 Introduction
c2 exp( SNR)
n 2
log n
1
n 2
c1
1
c2 exp( SNR)
SNR
1
log n
0
log n c exp( SNR)
n 2
1
2
The paper is organized as follows. In Section 2, we introduce the approximate ranking n 2
0
model, and then present the main results on optimal rates and phase transitions. In Section
0
log n
1ranking
n 2model,
The
paper
is
organized
as
follows.
In
Section
2, ranking
we introduce
theand
approximate
3, we consider two special cases of the approximate
derive optimal
prolog n
model,and
and adaptive
then present
the The
mainthat
results
optimal
and phase
transitions.
Inintroduce
Section
paper
is on
organized
asoptimal
follows.
In Section
2, we
cedures
algorithms
can
achieve
therates
rates.
We then
discuss
a fewthe approximate ranking
SNR
3, we consider
cases
of the
ranking
model, on
andoptimal
derive optimal
promodel,
and
then
present
main
results
rates
phase transitions. In
related
topics totwo
ourspecial
paper
in Section
4.approximate
All
proofsthe
are
given
0 Section
n 2and
log nin Section 5.
cedures and adaptive algorithms
that can
achieve
optimal
rates.
We then ranking
discuss amodel,
few and
0 derive optimal pro3, we consider
two
specialthe
cases
of the
approximate
The
paper
is organized
as follows.
In discuss
Section a2,few
we introduce the approximate ranking
related topics to our paper
inFigure
Section
4.1:
AllOptimal
proofs
are given
in Section
5.
cedures
and adaptive
algorithms
that
can
achieve
the
optimal
rates.
then
rate
with
to
`2We
(r̂,
r)
as
a function
of SNR.ranking In Section
Theerror
paper
is organized
asrespect
follows.
In
Section
2,
we
introduce
the approximate
model,
and
then
present
the
main
results
on
optimal
rates
and phase transitions.
log
n
0
related topics to our paper
in Section
4. All
proofs
are
given
in Section
5.
model,
and then
present
the
main
results
on
optimal
rates
and
phase
transitions.
In Section
3, we consider two special cases of the approximate ranking model, and
derive optimal proThe paper is organized as follows.
In Section
wespecial
introduce
ranking
3, we
consider2,two
casesthe
of approximate
the approximate
ranking model, and derive optimal procedures and
adaptive algorithms
that
can achieve
the optimal
rates. We rate
then discuss
delicate
phase
transition
phenomena.
Depending
on
the
value
of
SNR,
the
optimal
falls a few
model, and then present the main
on and
optimal
ratesalgorithms
and phase 0that
transitions.
In Section
cedures
adaptive
can achieve
the optimal rates. We then discuss a few
1 results
related topics to our paper in Section 4. All proofs are given in Section
5.
−2
fourtwodifferent
regimes.
Intopics
thetofirst
regime
where
the
SNR
isgiven
smaller
than
, the rate of
related
our
paper
in Section
Section
4. we
All
proofs
are
in Section
5. n
3, weinto
consider
special cases
ofpaper
the
approximate
ranking
model,
and
derive
optimal
proThe
is organized
as
follows.
In
2,
introduce
the
approximate
ranking
1and
2
cedures
and
adaptive
algorithms
that
can
achieve
the
optimal
rates.
We
then
discuss
a
few
model,
then
present
the
main
results
on
optimal
rates
and
phase
transitions.
In
Section
`2 (r̂, r) trivially takes the order of Θ(n ), which is the largest possible value of `2 (r̂, r). Next,
related topics to our paper
All special
proofs cases
are given
Section 5. ranking model, and derive optimal pro1 theinapproximate
3, in
weSection
consider4.two
of
cedures and adaptive algorithms that can achieve the optimal rates. We then discuss a few
related topics to our paper in Section 4. All proofs are given in Section 5.
1
2
1

1
1

as long as the SNR is greater than n−2 , the optimal rate starts to decrease polynomially
fast. After the SNR passes the threshold of 1, the optimal error accelerates to an exponential
rate. In the final regime where SNR > log n, we achieve exact recovery and `2 (r̂, r) = 0 with
high probability. The dashed curve in the final regime is the error in expectation, which
still decreases at the rate of exp (−SNR). Besides the loss function `2 (r̂, r), optimal rates and
P
similar phase transition boundaries are also derived for the loss `1 (r̂, r) = n1 ni=1 |r̂(i) − r(i)|.
The phase transition between the polynomial rate and the exponential rate is remarkable. To the best knowledge of the author, this is a new phenomenon first discovered in
the approximate ranking problem. Mathematically speaking, the polynomial rate is driven
by an entropy calculation argument, and when SNR < 1, estimating r is like estimating a
continuous parameter in Rn . In comparison, when SNR > 1, the discrete nature of r starts
to come into effect, and we have sufficient information thanks to a high SNR to distinguish
between r(i) and its neighboring values for each i, which contributes to the exponential rate.
The paper is organized as follows. In Section 2, we introduce the approximate ranking
model, and then present the main results on optimal rates and phase transitions. In Section
3, we consider two special cases of the approximate ranking model, and derive optimal procedures and adaptive algorithms that can achieve the optimal rates. We then discuss a few
related topics to our paper in Section 4. All proofs are given in Section 5.
We close this section by introducing notations that will be used later. For a, b ∈ R, let
a ∨ b = max(a, b) and a ∧ b = min(a, b). For an integer m, [m] denotes the set {1, 2, ..., m}.
Given a set S, |S| denotes its cardinality, and IS is the associated indicator function. We
use P and E to denote generic probability and expectation whose distribution is determined
from the context. For two positive sequences {an } and {bn }, we use the notation an . bn if
an ≤ Cbn for all n with some consntant C > 0 independent of n. Finally, for two probability
R
dP
measures P and Q, the Kullback-Leibler divergence is defined as D(PkQ) = log dQ
dP.

2

Main Results

2.1

The Approximate Ranking Model

Consider n objects with ranks r(1), r(2), ..., r(n) ∈ [n]. We observe {Xij }1≤i6=j≤n that follow
the generating process
Xij = µr(i)r(j) + Zij .
(1)
In other words, the outcome Xij is determined by a noisy version of µr(i)r(j) , which solely
depends on the ranks of i and j. In this paper, we consider Zij ’s with sub-Gaussian tails. In
particular, we assume that for any t > 0,




X
X
t2
2


P
vij Zij > t ≤ exp − 2 , for all
vij
= 1.
(2)
2σ
1≤i6=j≤n

1≤i6=j≤n

The goal of this paper is to recover the underlying ranks r = (r(1), r(2), ..., r(n)) from the

3

observations {Xij }1≤i6=j≤n . We consider the following space of ranks
(
)
n
n
X
X
n
R = r ∈ [n] :
r(i) −
i ≤ cn ,
i=1

i=1

√
where the number cn satisfies 1 ≤ cn = o( n). The flexibility of the space R allows ties.
To be more precise, an r ∈ R should be interpreted as discrete latent positions of the n
objects. Therefore, we refer to the problem as approximate ranking. Three loss functions are
considered in this paper. We define
n

`0 (r̂, r) =

1X
I{r̂(i) 6= r(i)},
n

`1 (r̂, r) =

n
1X
|r̂(i) − r(i)|,
n

`2 (r̂, r) =

n
1X
(r̂(i) − r(i))2 .
n

i=1

i=1

i=1

The loss function `0 (r̂, r) is the normalized Hamming distance between r̂ and r. It measures
the proportion of objects that are given incorrect ranks. Compared with `0 (r̂, r), the other
two loss functions `1 (r̂, r) and `2 (r̂, r) also measure the magnitude of the incorrectness of
each r̂(i). It is easy to see that for r̂, r ∈ R,
p
`0 (r̂, r) ≤ `1 (r̂, r) ≤ min{`2 (r̂, r), `2 (r̂, r)}.
Our model µr(i)r(j) is quite general. It characterizes the pairwise relation between the two
objects i and j through their ranks. The literature is popularized with pairwise comparison
models. In such a setting, the value of µr(i)r(j) is an increasing function of the difference
between r(i) and r(j). We are also interested in the pairwise collaboration setting, where a
larger value of µr(i)r(j) is implied by either or both of the values of r(i) and r(j). Without
specifying a particular setting, we impose the following general assumption. There exists a
number β ∈ R, such that for any r, r̃ ∈ R,
X
2
µr̃(i)r̃(j) − µr(i)r(j) ≥ 2nβ 2 kr̃ − rk2 .
(3)
1≤i6=j≤n

Later in Section 3, various examples will be given to satisfy this condition.

2.2

Minimax Rates

With the observations {Xij }1≤i6=j≤n and the knowledge of µr(i)r(j) , we consider a least-squares
estimator
X
2
r̂ = argmin
Xij − µr(i)r(j) .
(4)
r∈R

1≤i6=j≤n

4

This estimator may not be computationally efficient and it depends on the model parameters,
but it serves as an important benchmark of approximate ranking. Adaptive procedures with
unknown model parameters will be discussed in Section 3.
Use Pr and Er to denote the distribution of (1), and the performance of the least-squares
estimator r̂ is characterized by the following theorem.
Theorem 2.1. Under the conditions (2) and (3), we have


nβ 2
sup Er `0 (r̂, r) . exp −(1 + o(1)) 2 ,
4σ
r∈R



2

−(1 + o(1)) nβ
,

2
exp
4σ
s

 2 −1
 2 −1 
sup Er `1 (r̂, r) .
nβ

r∈R

log nβ
∧ n,

4σ 2
4σ 2
and




nβ 2

exp −(1 + o(1)) 4σ2 ,


−1
−1 
sup Er `2 (r̂, r) .
nβ 2
nβ 2

r∈R
log 4σ2
∧ n2 ,
 4σ2

nβ 2
4σ 2

> 1,

nβ 2
4σ 2

≤ 1,

nβ 2
4σ 2

> 1,

nβ 2
4σ 2

≤ 1,

where o(1) denotes a vanishing sequence as n → ∞.
Theorem 2.1 reveals an important quantity of signal-to-noise ratio. It is in the form of
2
When nβ
> 1, all the three loss functions converges to zero exponentially fast. In
4σ 2

nβ 2
.
4σ 2

2

comparison, when nβ
≤ 1, the three loss functions have polynomial rates capped at the
4σ 2
2
order of 1, n and n for `0 (r̂, r), `1 (r̂, r) and `2 (r̂, r), respectively.
Both the loss functions `1 (r̂, r) and `2 (r̂, r) involve a logarithmic factor in the polynomial
regime. This factor can be removed with an extra assumption on the model. Given a constant
M that satisfies 1 < M = O(1), we assume that for any r, r̃ ∈ R,
X
2
µr̃(i)r̃(j) − µr(i)r(j) ≤ 2M nβ 2 kr̃ − rk2 .
(5)
1≤i6=j≤n

The following theorem gives this improvement.
Theorem 2.2. Under the conditions (2), (3) and (5), we have


nβ 2
sup Er `0 (r̂, r) . exp −(1 + o(1)) 2 ,
4σ
r∈R



2
2
exp −(1 + o(1)) nβ
, nβ
> 1,
4σ 2
4σ 2
sup Er `1 (r̂, r) .  2 −1/2
nβ 2
 nβ
r∈R
∧ n,
≤ 1,
4σ 2
4σ 2
and




2
exp −(1 + o(1)) nβ2 ,
4σ
sup Er `2 (r̂, r) .  2 −1
nβ

r∈R
∧ n2 ,
4σ 2

where o(1) denotes a vanishing sequence as n → ∞.
5

nβ 2
4σ 2

> 1,

nβ 2
4σ 2

≤ 1,

The rates given by Theorem 2.2 are sharp, and they cannot be further improved. We give
matching lower bounds in the next theorem.
Theorem 2.3. There exists a distribution of (1) that satisfies (2), (3) and (5), such that


nβ 2
inf sup Er `0 (r̂, r) & exp −(1 + o(1)) 2 ,
r̂ r∈R
4σ



2
2
exp −(1 + o(1)) nβ
, nβ
> 1,
4σ 2
4σ 2
inf sup Er `1 (r̂, r) &  2 −1/2
nβ 2
 nβ
r̂ r∈R
∧ n,
≤ 1,
4σ 2
4σ 2
and




2
exp −(1 + o(1)) nβ2 ,
4σ
inf sup Er `2 (r̂, r) &  2 −1
2
 nβ
r̂ r∈R
∧n ,
4σ 2

nβ 2
4σ 2

> 1,

nβ 2

≤ 1,

4σ 2

where o(1) denotes a vanishing sequence as n → ∞.

2.3

Exact Recovery and Phase Transitions

According to Theorem
2.1 and Theorem
2.2, the convergence rates for all the three loss


2
nβ 2
nβ 2
> log n, then the
functions are exp −(1 + o(1)) 4σ2 when 4σ2 > 1. Therefore, suppose nβ
4σ 2

convergence rate will be smaller than n−1 . Since the loss functions that we consider do not
take any value in the interval (0, n−1 ), a convergence rate smaller than n−1 is expected to
imply exact recover of the underlying r. This intuition is made rigorous by the following
theorem.
Theorem 2.4. Under the conditions (2) and (3), if we further assume that lim inf n
1, then the LSE (4) satisfies
inf Pr (r̂ = r) → 1,

nβ 2
4σ 2 log n

>

r∈R

as n → ∞.
Moreover, the next result shows that the condition in Theorem 2.4 is necessary for exact
recover.
Theorem 2.5. Assume lim supn
(2), (3) and (5), such that

nβ 2
4σ 2 log n

< 1. There exists a distribution of (1) that satisfies

1
lim inf inf sup Pr (r̂ 6= r) ≥ .
n
r̂ r∈R
2
The results in Theorem 2.2, Theorem 2.3, Theorem 2.4 and Theorem 2.5 together give us
a very good picture of the optimal error behavior. Interesting phase transitions are revealed
2
for the approximate ranking problem. Depending on the signal-to-noise ratio nβ
, the optimal
4σ 2
error rates have different behaviors. A graphical illustration for the loss function `2 (r̂, r) is
given by Figure 1. We summarize the phase transitions in the following table.

6

`0 (r̂, r)
`1 (r̂, r)
`2 (r̂, r)

trivial

non-trivial

nβ 2
= O(1)
4σ 2
nβ 2
= O(n−2 )
4σ 2
2
nβ
= O(n−2 )
4σ 2

nβ 2
1
4σ 2
nβ 2
 n−2
4σ 2
2
nβ
 n−2
4σ 2

consistent
nβ 2
4σ 2
nβ 2
4σ 2
nβ 2
4σ 2

1
1
1

strongly consistent
nβ 2
4σ 2
nβ 2
4σ 2
nβ 2
4σ 2

> log n
> log n
> log n

We call a rate trivial if it is at the same order of the maximal value of the loss. The maximum
of the three loss functions `0 (r̂, r), `1 (r̂, r) and `2 (r̂, r) are of orders 1, n and n2 , respectively.
A rate is consistent if the loss converges to zero. We refer to exact recovery as being strongly
consistent. Then, for each loss function, there are four different regimes: the trivial regime,
the non-trivial regime, the consistent regime and the strongly consistent regime. The only
exception is that for the loss `0 (r̂, r), its non-trivial regime is identical to the consistent
regime. For all the three loss functions, the rates in the consistent regime are exponential
and the rates in the non-trivial regime are polynomial.

3

Adaptive Procedures

Our paper considers a very general framework of the approximate ranking model in the form
of µr(i)r(j) . Though we are able to characterize the exact minimax rates of the problem under
various regimes of the signal-to-noise ratio, the least-squares procedure (4) that can achieve
the statistical optimality is usually infeasible in practice. In fact, similar optimization problems as (4) have been considered in the literature of graph matching/isomorphism problem
[19], which is believed very unlikely to be solved by a polynomial-time algorithm [10].
In this section, we consider some special cases of the general model µr(i)r(j) , and then
discuss possible adaptive procedures that can take advantage of the additional model structures to achieve the optimal statistical rates. Inspired by the latent space model in network
analysis [9], we consider examples in the form

µr(i)r(j) = f θr(i) , θr(j) .

(6)

Here, θr(i) stands for the latent ability parameter of the position r(i). In particular, we will
analyze a differential comparison model and an additive collaboration model, both of which
are in the form of (6). Interestingly, we will show for these two models, the approximate
ranking problem is reduced to a feature matching problem considered by [6], for which efficient algorithms are available. When the latent parameters {θi } are unknown but admits
a linear relation with respect to the underlying ranks, we show that a profile least-squares
procedure, which can be solved by iterative feature matching, can adaptively achieve the
optimal statistical rates.

3.1

Differential Comparison

We first consider a differential comparison model, which imposes the structure
µij = θi − θj .
7

(7)

Therefore, the mean of the observation Xij is given by θr(i) − θr(j) , the difference between the
abilities of i and j. We propose the following signal conditions. For any r, r̃ ∈ R, we assume
n
X
i=1

(θr(i) − θr̃(i) )2 ≥ β 2 kr̃ − rk2 ,

max
r∈R

n
X
i=1

θr(i) −

n
X

(8)

√
θi = o( nβ).

(9)

i=1

It is easy to check that the general condition (3) is implied by (8) and (9). We remark that
the condition (9) is coherent with the definition of the space R.
In the current setting, the ability parameters {θi } are given but the correspondence between {i} and {θi } is linked by unknown ranks {r(i)}. Our general strategy to find ranks is
based on the idea of feature matching [6]. We first define the score of i by
1
Si =
2n

n

X

1X
θj .
(Xij − Xji ) +
n

(10)

j=1

j∈[n]\{i}

Then, the estimator of ranks is defined by
r̂ = argmin
r∈R

n
X
(Si − θr(i) )2 .

(11)

i=1

This optimization can be efficiently solved by feature matching algorithms discussed in [6].
Its statistical performance is given by the following theorem.
Theorem 3.1. Under the conditions (2), (8) and (9), we have


nβ 2
sup Er `0 (r̂, r) . exp −(1 + o(1)) 2 ,
4σ
r∈R



2
2
exp −(1 + o(1)) nβ
, nβ
> 1,
4σ 2
4σ 2
sup Er `1 (r̂, r) .  2 −1/2
nβ 2
 nβ
r∈R
∧ n,
≤ 1,
4σ 2
4σ 2
and




2
exp −(1 + o(1)) nβ2 ,
4σ
sup Er `2 (r̂, r) .  2 −1
nβ
2

r∈R
∧n ,
4σ 2

nβ 2
4σ 2

> 1,

nβ 2

≤ 1,

4σ 2

where o(1) denotes a vanishing sequence as n → ∞. Moreover, when lim inf n
we have r̂ = r with probability 1 − o(1).

nβ 2
4σ 2 log n

> 1,

It is easy to check that the distribution constructed to prove the lower bound results in
Theorem 2.3 satisfies the conditions (8) and (9). This implies that the rates achieved by the
computationally efficient estimator r̂ in Theorem 3.1 is optimal under the differential comparison model. It is interesting that we do not have any logarithmic factor in the convergence
2
rates when nβ
≤ 1 even without any condition similar to (5). This is a consequence by the
4σ 2
special structure in the differential comparison model (7).
8

3.2

Additive Collaboration

Since our framework is quite general, we can also consider an additive collaboration model.
It imposes the structure
µij = θi + θj .
(12)
Compared with (7), the collaboration model assumes that the mean µij is increasing with
respect to both the abilities of i and j. Despite the difference in interpretation, the two
models have very similar mathematical structures. We will adopt the signal condition (8)
here, but we do not need to assume the second condition (9). With the additive structure,
the condition (8) alone implies (3). We also use the feature-matching estimator (11), with
the score of each i defined as


X
X
1
1

Si =
Xij  .
(Xij + Xji ) −
(13)
2(n − 2)
n−1
1≤i6=j≤n

j∈[n]\{i}

The performance of the estimator r̂ is given by the following theorem.
Theorem 3.2. Under the conditions (2) and (8), we have


nβ 2
sup Er `0 (r̂, r) . exp −(1 + o(1)) 2 ,
4σ
r∈R



2
2
exp −(1 + o(1)) nβ
, nβ
> 1,
4σ 2
4σ 2
sup Er `1 (r̂, r) .  2 −1/2
nβ 2
 nβ
r∈R
∧ n,
≤ 1,
4σ 2
4σ 2
and




2
exp −(1 + o(1)) nβ2 ,
4σ
sup Er `2 (r̂, r) .  2 −1
nβ
2

r∈R
∧n ,
4σ 2

nβ 2
4σ 2

> 1,

nβ 2

≤ 1,

4σ 2

where o(1) denotes a vanishing sequence as n → ∞. Moreover, when lim inf n
we have r̂ = r with probability 1 − o(1).

nβ 2
4σ 2 log n

> 1,

We obtain the same rates as in Theorem 3.1 for the differential comparison model. Note
that the same argument in the lower bound proof of Theorem 2.3 can easily be adapted for
the additive collaboration model in this section. This implies the rates in Theorem 3.2 are
all optimal.

3.3

Applications in a Parametric Model

In this section, we consider both the comparison and the collaboration models with θi = α+ β̃i
for some α ∈ R and β̃ > 0. That is, the ability parameter θi is a linear function of its
latent position. It is easy to check that both conditions (8) and (9) are satisfied with some
β = (1 + o(1))β̃.

9

Since α and β̃ are unknown, we cannot directly use the feature matching estimator (11).
Instead, we propose the following profile least-squares objective,
PL(r) = min

n 
X

a,b

i=1

Ŝi − a − br(i)

2

.

(14)

Then, the estimator is found through minimizing PL(r). Note that we use a linear model
a + br(i) as a surrogate for θr(i) in the definition of (14). The feature matching procedure
and the linear model fit of θr(i) are done simultaneously. An equivalent way of writing PL(r)
is by
n 
2
X
PL(r) =
Ŝi − âr − b̂r r(i) ,
i=1

where
b̂r =

1
n

Pn

1 Pn
1 Pn
i=1 Ŝi r(i) − n
i=1 r(i)
i=1 Si
n

P
P
2
n
n
1
1
2
i=1 r(i) − n
i=1 r(i)
n




and âr =

n

n

i=1

i=1

1X
1X
Si − b̂r
r(i). (15)
n
n

For the differential comparison model, we use the score
Ŝi =

1
2n

X
j∈[n]\{i}

(Xij − Xji ).

For the additive collaboration model, we use
Ŝi =

1
2(n − 2)

X

(Xij + Xji ).

j∈[n]\{i}

Therefore, the estimator r̂ is fully data-driven.
Optimizing over PL(r) can be done in a iterative fashion. At each iteration, one first
2
P 
optimize ni=1 Ŝi − ârt−1 − b̂rt−1 r(i) over r. Then, one can update the parameters ârt−1

and b̂rt−1 using the least-squares formula (15). In other words, feature matching and linear
regression are run in turn iteratively. In this section, our focus is on the study of the statistical
property of the global optimizer of PL(r). The convergence analysis of the iterative algorithm
will be studied in a much more general framework of profile least-squares optimization in the
future.
To study the statistical error of the profile least-squares estimator, we consider the following space of approximate ranks. Define
)
(
n
n
X
X
r(i)2 −
i2 ≤ c0n ,
R0 = r ∈ R :
i=1

i=1

P
where c0n = o(n3 ). The set R0 is a subset of R with an additional constraint on ni=1 r(i)2 .
This extra constraint does not make the problem easier, and the same minimax lower bound
results also hold for the set R0 with a simple modification of the proof of Theorem 2.3.
10

Theorem 3.3. Consider the estimator r̂ = argminr∈R0 PL(r). Under the conditions (2) for
the differential comparison model or the additive collaboration model with θi = α + β̃i for
some β̃ = (1 + o(1))β, we have


nβ 2
sup Er `0 (r̂, r) . exp −(1 + o(1)) 2 ,
4σ
r∈R0



2
2
exp −(1 + o(1)) nβ
, nβ
> 1,
4σ 2
4σ 2
sup Er `1 (r̂, r) .  2 −1/2
nβ 2
 nβ
r∈R0
∧ n,
≤ 1,
4σ 2
4σ 2
and




2
exp −(1 + o(1)) nβ2 ,
4σ
sup Er `2 (r̂, r) .  2 −1
nβ
2

0
r∈R
∧n ,
4σ 2

nβ 2
4σ 2

> 1,

nβ 2

≤ 1,

4σ 2

where o(1) denotes a vanishing sequence as n → ∞. Moreover, when lim inf n
we have r̂ = r with probability 1 − o(1).

4
4.1

nβ 2
4σ 2 log n

> 1,

Discussion
Comparison with Community Detection

Our approximate ranking model shares some similarity with the stochastic block model that
is widely studied in the problem of community detection. The relation between ranking and
clustering was previously discussed in the paper [4]. Our discussion here is from a different
aspect. The goal of community detection is to partition the set [n] into k clusters. In the
setting of stochastic block model, the observation can be written as
Xij = µτ (i)τ (j) + Zij ,

(16)

where µτ (i)τ (j) is the expectation of Xij , and it characterizes the interaction level between i
and j. The value of µτ (i)τ (j) is determined by the clustering labels τ (i) and τ (j). Note that
the form (16) is exactly the same as (1). The literature usually studies stochastic block models
with Bernoulli observations. However, to make comparison more intuitive, we consider the
same sub-Gaussian setting as in (2).
Just like in the approximate ranking model, the goal here is to estimate the clustering
labels τ ∈ Ck . In the most basic setting, the class Ck is considered as a subset of [k]n that
consists of clustering labels that induce roughly equal-sized clusters. Recently, the minimax
rate of estimating τ was derived by [20]. They impose the condition that
µτ (i)τ (j) = pI{τ (i) = τ (j)} + qI{τ (i) 6= τ (j)}.

(17)

The numbers p and q represent the within-cluster and the between-cluster interaction levels.
In fact, we can write down an alternative condition in the style of (3). Assume that for any
τ, τ̃ ∈ Ck ,
X
(µτ (i)τ (j) − µτ̃ (i)τ̃ (j) )2 ≥ 2β 2 n2 `˜0 (τ, τ̃ ),
(18)
1≤i6=j≤n

11

when `˜0 (τ, τ̃ ) = o(n/k). The loss function `˜0 (τ, τ̃ ) is defined in the same way as `0 (τ̃ , τ )
up to a permutation of clustering labels, so that it is more appropriate to measure the
difference between two clustering structures. One can check that (17) implies (18) with
2
β 2 = (1 + o(1)) 2(p−q)
. With similar techniques used in this paper, it can be shown that
k
there is an estimator τ̂ that achieves


n(p − q)2
˜
.
Eτ `0 (τ̂ , τ ) ≤ exp −(1 + o(1))
4kσ 2
This is essentially the same result in [20] by replacing σ 2 with the variance parameter
 √ √ 2
p+ q
in the their Bernoulli setting. Moreover, it shares the same form of exponen2
2

tial rates in Theorem 2.1 in view of the relation β 2 = (1 + o(1)) 2(p−q)
.
k
On the other hand, we also point out some major differences between approximate ranking
and community detection. First of all, the ranking labels are ordered numbers, while the
clustering labels have no ordering. Therefore, one can only measure whether the estimation
of τ (i) is right or wrong by an indicator function. In comparison, one can not only measure
whether each r(i) is correctly estimated, but one can also measure the deviation in terms
of the distance or the squared distance between r̂(i) and r(i). Secondly, the approximate
ranking model naturally has n latent positions, and each r(i) has n possible values, while for
the stochastic block model, there are only k latent positions, and usually k is assumed to be
a constant or grow with n very slowly in the literature. These two differences lead to the
interesting phase transitions for the approximate ranking problem in our paper, and such a
new phenomenon did not appear in community detection or in any other problems before.

4.2

Results for Poisson Distributions

In this section, we consider a natural Poisson model for discrete observations. We assume
Xij ∼ Poisson(µr(i)r(j) ) independently for all 1 ≤ i 6= j ≤ n. Note that µr(i)r(j) models
both mean and variance of the observation Xij . Thus, it is more appropriate to consider
the following condition instead of (3). We assume there exists a β ∈ R, such that for any
r, r̃ ∈ [n]n ,
2
X p
p
µr̃(i)r̃(j) − µr(i)r(j) ≥ 2nβ 2 kr̃ − rk2 .
(19)
1≤i6=j≤n

√
Compared with the condition (3), the condition for the Poisson model involves µr(i)r(j) .
The square-root transformation can be dated back to the famous variance-stabilizing transformation [1].
Instead of using the least-squares estimator (4), we propose the maximum likelihood
estimator
Xij
Y µr(i)r(j)
e−µr(i)r(j)
r̂ = argmax
.
Xij !
r∈R
1≤i6=j≤n

12

Theorem 4.1. Under the condition (19), we have

sup Er `0 (r̂, r) . exp −(1 + o(1))nβ 2 ,

r∈R




exp −(1 + o(1))nβ 2 ,
r
h
i
sup Er `1 (r̂, r) .
−1
−1

r∈R
∧ n,
 (nβ 2 ) log (nβ 2 )
and

nβ 2 > 1,
nβ 2 ≤ 1,


exp −(1 + o(1))nβ 2  ,
h
sup Er `2 (r̂, r) . n

 io
 nβ 2 −1 log nβ 2 −1 ∧ n2 ,
r∈R

nβ 2 > 1,
nβ 2 ≤ 1,

where o(1) denotes a vanishing sequence as n → ∞.
Again, Theorem 4.1 exhibits different behaviors of the ranking errors depending on the
regime of nβ 2 . Here, the signal-to-noise ratio is nβ 2 , and it plays the same role as that of
nβ 2
in Theorem 2.1.
4σ 2
We also give a complementary lower bound.
Theorem 4.2. There exists a Poisson distribution that satisfies (19), such that

inf sup Er `0 (r̂, r) & exp −(1 + o(1))nβ 2 ,
r̂ r∈R

(

exp −(1 + o(1))nβ 2 ,
inf sup Er `1 (r̂, r) &
−1/2
r̂ r∈R
nβ 2
∧ n,

nβ 2 > 1,
nβ 2 ≤ 1,

and
(

exp −(1 + o(1))nβ 2 ,
inf sup Er `2 (r̂, r) &
−1
r̂ r∈R
nβ 2
∧ n2 ,

nβ 2 > 1,
nβ 2 ≤ 1,

where o(1) denotes a vanishing sequence as n → ∞.
The lower bound results imply that the rates that we obtain in Theorem 4.1 are optimal
up to a logarithmic factor in the polynomial regime where nβ 2 ≤ 1. Different from what we
have for the model (1), it is not clear whether such a logarithmic factor can be removed in
the upper bounds with some extra condition for the Poisson model.
To close this section, we give sufficient and necessary conditions for exact recovery in the
following theorem.
Theorem 4.3. Under the condition (19), if we further assume that lim inf n
the MLE satisfies
inf Pr (r̂ = r) → 1,

nβ 2
log n

> 1, then

r∈R

as n → ∞. Moreover, when lim supn
(19), such that

nβ 2
log n

< 1, there exists a Poisson distribution that satisfies

lim inf inf sup Pr (r̂ 6= r) ≥
n

r̂ r∈R

13

1
− o(1).
2

4.3

Other Ranking Models

Our paper gives a general analysis of the optimal rates of the approximate ranking model
(1). Adaptive procedures are discussed for two special cases of differential comparison and
additive collaboration. We expect the analysis can be extended to derive exact optimal rates
and phase transitions for many other models. For example, the popular Bradley-Terry-Luce
θ
model [2, 11] considers the form µr(i)r(j) = θ r(i)
, a special case of (6). Ranking problems
r(i) +θr(j)
under this setting were studied by [14] and references therein. Besides the parametric models,
an interesting nonparametric stochastically transitive model was proposed and analyzed in
[15, 16]. Finally, a simple noisy sorting model that assumes µr(i)r(j) ≥ 12 + γ if r(i) < r(j)
was considered in [3]. The minimax rate for this model was recently derived by [12].
We remark that all of these models proposed in the literature can be written in some
modified versions of (3). However, since these papers all consider Bernoulli observations and
the space of permutations, our noise condition (2) and the setting of approximate ranking
may not be appropriate. Despite these differences, we still believe all the phase transition
boundaries discovered in our paper have analogous correspondence in these Bernoulli models.
This will be an immediate interesting project to follow in the future.

5

Proofs

In this section, we give proofs of all the results in the paper. From Section 5.1 to Section 5.5,
we state the proofs of the main results, with the help of some technical lemmas. The proof
of these auxiliary lemmas will be given in Section 5.6.

5.1

Proofs of Theorem 2.1 and Theorem 2.2

Before stating the proofs, we need some lemmas. We use L(r) to denote the objective function
P
2
i6=j (Xij − µr(i)r(j) ) . For a fixed r, we define

Rm = r̃ ∈ R : kr̃ − rk2 = m .

(20)

In other words, the set Rm collects those r̃’s that have errors m in terms of the squared `2
norm. This results in a partition of R, which is
R = ∪m Rm .
The following two lemmas are important to prove the main results, and their proofs will be
given in Section 5.6.
Lemma 5.1. Assume the conditions (2) and (3). For any m such that Rm 6= ∅, we have


nβ 2 m
.
max Pr (L(r̃) ≤ L(r)) ≤ exp −
r̃∈Rm
4σ 2

14

Lemma 5.2. For each m, the cardinality of Rm is bounded as

m
e5/2 n


, 1 ≤ m ≤ n,

 m n
6
e m
|Rm | ≤
,
n ≤ m ≤ n2 ,
n



nn ,
m > n2 .
Now we are ready to prove Theorem 2.1.
Proof of Theorem 2.1. We first give a bound for Er kr̂ − rk2 . Different arguments will be
2
given depending on the value of nβ
.
4σ 2
nβ 2
4σ 2

≥ log(e5/2 n). In this regime, we have
X
Er kr̂ − rk2 =
mPr (kr̂ − rk2 = m)

Case 1:

m≥1

≤

X
m≥1

m

X
r̃∈Rm

Pr (L(r̃) ≤ L(r))



nβ 2 m
≤
m|Rm | exp −
4σ 2
m≥1
!m




n
X
X
e5/2 n
nβ 2 m
nβ 2 m
n
≤
m
+
n
m
exp
−
.
exp −
2
m
4σ 2
4σ
m>n
X

(21)

(22)

m=1

In the above derivation, we use Lemma 5.1 for (21) and Lemma 5.2 for (22). Now we will
give bounds for the two terms in (22) separately. The first term has bound

 X

 2

n
n
X
nβ 2 m
nβ
5/2 m
5/2
(e n) exp −
=
exp −m
− log(e n) .
4σ 2
4σ 2
m=1

m=1

nβ 2

Under the condition 4σ2 ≥ log(e5/2 n), we have

  2




 2
n
X
nβ
nβ 2
nβ
5/2
5/2
− log(e n)
. exp −
− log(e n)
= n exp −(1 + o(1)) 2 .
exp −m
4σ 2
4σ 2
4σ
m=1

The second term of (22) has bound




 2
X
X
nβ 2 m
nβ
n
n
n
m exp −
≤ n
exp −m
−1
4σ 2
4σ 2
m>n
m>n

 2

nβ
n
. n exp −n
−1
4σ 2

 2

nβ
= exp −n
− log(en)
4σ 2
  2

nβ
≤ exp −
− log(en)
4σ 2


nβ 2
= n exp −(1 + o(1)) 2 .
4σ
15

Therefore, in this regime, we have


nβ 2
Er kr̂ − rk2 . n exp −(1 + o(1)) 2 .
4σ
Case 2: 2 log(2e6 ) <
Er kr̂ − rk2

nβ 2
4σ 2

< log(e5/2 n). In this regime, we have
X

Pr kr̂ − rk2 ≥ m
≤ m0 +
m>m0



nβ 2 m
m|Rm | exp −
4σ 2
m>m0
!m


n
X
nβ 2 m
e5/2 n
≤ m0 +
exp −
m
m
4σ 2
X

≤ m0 +

(23)
(24)

m=m0 +1

2

+

n
X


m

m=n+1

e6 m
n

n





X
nβ 2 m
nβ 2 m
n
exp −
+n
m exp −
.
4σ 2
4σ 2
2
m>n

Again, Lemma 5.1 and Lemma 5.2 are used to derive (23) and (24). There are four terms in
(24) that we need to bound. For the first term, we take




nβ 2
nβ 2
5/2
m0 = 2 exp − 2 + log(2e n) . n exp −(1 + o(1)) 2 .
4σ
4σ
We remark that for this choice of m0 , we have m0 & 1 under the condition
Then, the second term can be bounded by
!m


n
X
e5/2 n
nβ 2 m
m
exp −
m
4σ 2
m=m0 +1
!m


n
X
2e5/2 n
nβ 2 m
≤
exp −
m
4σ 2
m=m0 +1

 m

nβ 2
5/2 n)
exp
−
+
log(2e
X
4σ 2


≤
m0
m≥m0 +1
X
=
2−m . 1 . m0 .

nβ 2
4σ 2

< log(e5/2 n).

m≥m0 +1

The third term can be bounded by
 6 n


n2
X
nβ 2 m
e m
m
exp −
n
4σ 2
m=n+1



 6 n
n2
X
2e m
nβ 2 m
≤
exp −
n
4σ 2
m=n+1



 6 m
X
mnβ 2
2e m
nβ 2
n
≤
exp −
exp − 2 + log
.
2
8σ
8σ
m
n
m>n
16

(25)

nβ 2
,
4σ 2

Note that under the condition 2 log(2e6 ) <
nβ 2
n
− 2 + log
8σ
m



2e6 m
n


≤−

nβ 2
+ log(2e6 ) < 0,
8σ 2

for all m > n. Thus,(25) can be bounded by




X
nβ 2
mnβ 2
. exp − 2 . 1 . m0 .
exp −
8σ 2
8σ
m>n
For the last term, we have the bound



 2

X
X
nβ 2 m
nβ
n
n
n
m exp −
≤ n
exp −m
−1
4σ 2
4σ 2
m>n2
m>n2


 2
n
2 nβ
−1
. n exp −n
4σ 2
. 1 . m0 .

(26)

Hence, in this regime, we have
nβ 2
Er kr̂ − rk . n exp −(1 + o(1)) 2
4σ


2


.

2

Case 3: logn n < nβ
≤ 2 log(2e6 ). For the this regime, we use a similar argument that is
4σ 2
used in the previous two, and we obtain the following bound
2

n
X

2

Er kr̂ − rk ≤ m0 +


m

m=m0 +1

e6 m
n

n





X
nβ 2 m
nβ 2 m
n
exp −
+
n
m
exp
−
.
4σ 2
4σ 2
2
m>n

There are three terms to bound. For the first term, we choose
"
 2 −1
−1 #
nβ
nβ 2
,
m0 = Cn
log
4σ 2
4σ 2
for some large constant C > 0. Note that m0 & n under the condition
Then, the second term is bounded by
2

n
X

≤ 2 log(2e6 ).

n



nβ 2 m
exp −
4σ 2
m=m0 +1



 6 m
X
mnβ 2
nβ 2
n
2e m0
≤
exp −
exp
−
+
log
.
2
2
8σ
8σ
m
n
0
m>m


m

e6 m
n

nβ 2
4σ 2

0

2

By the choice of m0 , − nβ
+ mn0 log
8σ 2



2e6 m0
n



≤ 0 for some sufficiently large C > 0. This gives
17

X
m>m0

mnβ 2
exp −
8σ 2





 6 m

X
nβ 2
n
2e m0
mnβ 2
exp − 2 +
. m0 .
log
exp −
≤
8σ
m0
n
8σ 2
m>m
0

The third term can be bounded in the same way as the bound (26). Hence, in this regime,
we have
"
 2 −1
−1 #
nβ
nβ 2
2
Er kr̂ − rk . n
.
log
4σ 2
4σ 2
Case 4:

nβ 2
4σ 2

≤

log n
n .

For this regime, we have the bound
2

Er kr̂ − rk ≤ m0 + n

n

Choose

m0 = Cn

X
m>m0

nβ 2
4σ 2



nβ 2 m
.
m exp −
4σ 2

−1

log n,

for some large constant C > 0. Then, we can bound both terms. This gives
"
−1 #
 2 −1
nβ 2
nβ
2
log
,
Er kr̂ − rk . n
4σ 2
4σ 2
2

by using the condition nβ
≤ logn n .
4σ 2
Finally, we can summarize our results obtained in the four regimes above.
 We note that
nβ 2
nβ 2
when 4σ2 is at a constant level, both the bound n exp −(1 + o(1)) 4σ2 and the bound

−1 
 2 −1
nβ
nβ 2
n 4σ2
log 4σ2
are of order n, and thus they can be used interchangeably. With
the relation `2 (r̂, r) = kr̂ − rk2 /n, we have



nβ 2

exp −(1 + o(1)) 4σ2 ,



 
Er `2 (r̂, r) .
2 −1
2 −1
nβ
nβ

log 4σ2
∧ n2 ,
 4σ2

nβ 2
4σ 2

> 1,

nβ 2

≤ 1,

4σ 2

where the bound Er `2 (r̂, r) . n2 is automatically satisfied by the definition of the loss. When
nβ 2
> 1, the results for the other two loss functions are immediately implied by the relation
4σ 2
`0 (r̂, r) ≤ `1 (r̂, r) ≤ `2 (r̂, r). When

nβ 2
4σ 2

≤ 1, one can use Jensen’s inequality and get
p
√
Er kr̂ − rk/ n ≤ Er kr̂ − rk2 /n.

√
Then, by the inequality `1 (r̂, r) ≤ kr̂ − rk/ n and the fact that `1 (r̂, r) . n, we obtain the
desired bound for Er `1 (r̂, r). The proof is complete by taking supreme over r ∈ R.
Now we will prove Theorem 2.2. The following lemma that uniformly controls the comparison between objective functions is important. Its proof will be given in Section 5.6.
18

Lemma 5.3. Assume (2), (3) and (5). For any r ∈ R, and t > 0 and any l ≥ 1, we have




2 2 2
0β t l
min
L(r̃) ≤ L(r) . exp −C
Pr
,
M σ2
{r̃∈R:tl<kr̃−rk≤t(l+1)}
where C 0 > 0 is some universal constant, and M is the same constant in (5).
Proof of Theorem 2.2. In view of Theorem 2.1, we only need to improve the polynomial rate
2
2
≤ 1. In other words, it suffices to prove Ekr̂ − rk2 . βσ2 .
in the regime nβ
4σ 2
For a given t > 0, we will derive a bound for Pr (kr̂ − rk > t). Define the set
R̃l = {r̃ ∈ R : tl < kr̃ − rk ≤ t(l + 1)} .
Then, we have
Pr (kr̂ − rk > t) ≤

∞
X
l=1





Pr r̂ ∈ R̃l ≤

∞
X


Pr

l=1


inf L(r̃) ≤ L(r) .

r̃∈R̃l

Using Lemma 5.3, we have




 X

∞
∞
2 2
X
β 2 t2 l 2
0β t
.
exp
−C
.
Pr inf L(r̃) ≤ L(r) .
exp −C 0
M σ2
M σ2
r̃∈R̃l
l=1

Choosing t2 =

l=1

M σ2 τ
,
β2

we obtain the bound

Pr

kr̂ − rk2
>τ
(M σ 2 )/β 2




. exp −C 0 τ .
2

Integrate up the tail over τ > 0, we get Ekr̂ − rk2 . βσ2 . The desired bound for Er `2 (r̂, r) is
implied by `2 (r̂, r) = kr̂ − rk2 /n and `2 (r̂, r) . n2 . For the loss `1 (r̂, r), we use the inequality
p
`1 (r̂, r) ≤ kr̂ − rk2 /n, and then get



`1 (r̂, r) √
Pr  q 2 > τ  . exp −C 0 τ .
Mσ
nβ 2

The desired bound for Er `1 (r̂, r) is obtained by integrating up the tail and the fact that
`1 (r̂, r) . n. The proof is complete by taking supreme over r ∈ R.

5.2

Proof of Theorem 2.3

We first show the lower bound in the regime of
inequality. The version we give here is from [18].

nβ 2
4σ 2

≤ 1. We need the following Fano’s

Proposition 5.1. Let (Ξ, `) be a metric space and {Pξ : ξ ∈ Ξ} be a collection of probability
measures. For any totally bounded T ⊂ Ξ, define the Kullback-Leibler diameter by
dKL (T ) = sup D(Pξ ||Pξ0 ).
0
ξ,ξ ∈T

19

Then

 
 2 
d (T ) + log 2
2 ˆ
≥ 1 − KL
inf sup Pξ ` ξ(X), ξ ≥
,
4
log M(, T, `)
ξ̂ ξ∈Ξ

for any  > 0, where the packing number M(, T, `) is the largest number of points in T that
are at least  away from each other with respect to `(·, ·).
We also need the following Varshamov-Gilbert bound. The version we present here is due
to [13, Lemma 4.7].
Lemma 5.4. There exists a subset {ω1 , ..., ωN } ⊂ {0, 1}d such that
||ωi − ωj ||2 ≥

d
,
4

for any i 6= j ∈ [N ],

(27)

for some N ≥ exp (d/8).
2

≤ 1. We consider the distribution Xij ∼ N (β̃(r(i)−r(j)), σ 2 ),
Proof of Theorem 2.3 when nβ
4σ 2
which clearly satisfies (2). Then, for any two different r, r̃ ∈ R,


X
1≤i6=j≤n

2
β̃(r(i) − r(j)) − β̃(r̃(i) − r̃(j))

X

= β̃ 2

1≤i6=j≤n


(r(i) − r̃(i))2 + (r(j) − r̃(j))2 − 2(r(i) − r̃(i))(r(j) − r̃(j))
n
X

= 2(n − 1)β̃ 2 kr − r̃k2 + 2β̃ 2 kr − r̃k2 − 2β̃ 2
= 2nβ̃ 2 kr − r̃k2 − 2β̃ 2

n
X
i=1

i=1

!2
(r(i) − r̃(i))

!2
(r(i) − r̃(i))

.

P
Note that ( ni=1 (r(i) − r̃(i)))2 = O(c2n ) = o(n), and therefore


X
1≤i6=j≤n

2
β̃(r(i) − r(j)) − β̃(r̃(i) − r̃(j)) = 2n(1 + o(1))β̃ 2 kr − r̃k2 .

The conditions (3) and (5) are satisfied with β = (1 + o(1))β̃. We first translate the Fano’s
inequality in Proposition 5.1 into the following version,

dKL (T ) + log 2
m
√
inf sup Pr kr̂ − rk2 ≥
,
≥1−
r̂ r∈R
4
log M( m, T, k · k)
and we need to construct a subset T ⊂ R. For simplicity of notation, we assume that n/6 is
an integer, and otherwise simple modification of the proof can be made. Consider a vector
t ∈ [n]n . We set t(i) = 0 if 1 ≤ i < n/3 or 2n/3 < i ≤ n. For the entries between n/3 and
p
p
2n/3, each t(i) takes value from {d m/ne, 2d m/ne} for n/3 ≤ i ≤ n/2, and t(i) = t(n − i)
for all n/2 < i ≤ 2n/3. For any such t, we define rt ∈ [n]n by rt (i) = i + t(i). Since
20

P
P
P
= ni=1 i + ii=1 t(i) = ni=1 i, we have rt ∈ R as long as m ≤ n3 /32. Moreover,
for any two t, t0 , we have
n/2
X
2
(t(i) − t0 (i))2 .
krt − rt0 k = 2
Pn

i=1 rt (i)

i=n/3

Therefore, by Lemma 5.4, there exists a set T ⊂ R that collects those rt ’s, such that for any
two different rt , rt0 ∈ T , krt − rt0 k2 ≥ c1 m and |T | ≥ ec2 n . We bound the Kullback-Leiber
diameter by
X
2
dKL (T ) =
sup
µrt (i)rt (j) − µrt0 (i)rt0 (j) /(2σ 2 )
rt ,rt0 ∈T 1≤i6=j≤n

≤

sup
rt ,rt0 ∈T

nβ̃ 2 krt − rt0 k2
nβ̃ 2 m
≤C
.
2
σ
σ2

The Fano’s inequality then implies
2

inf sup Pr



r̂ r∈R

C nβ̃σ2m + log 2
c1 m 
≥1−
.
kr̂ − rk ≥
4
c2 n
2

 2

We take m = c βσ2 ∧ n3 for some sufficiently small constant c > 0, and then we get the
desired lower bound for inf r̂ supr∈R Er `2 (r̂, r) by applying a Markov inequality.
A similar construction of T also works for inf r̂ supr∈R Er `1 (r̂, r). Consider a vector t ∈
n
[n] . We set t(i) = 0 if 1 ≤ i < n/3 or 2n/3 < i ≤ n. For the entries between n/3 and
2n/3, each t(i) takes value from {dm/ne, 2dm/ne} for n/3 ≤ i ≤ n/2, and t(i) = t(n − i)
for all n/2 < i ≤ 2n/3. For any such t, we define rt ∈ [n]n by rt (i) = i + t(i). Since
Pn
Pi
Pn
Pn
2
i=1 i, we have rt ∈ R as long as m ≤ n /4. Moreover,
i=1 t(i) =
i=1 i +
i=1 rt (i) =
for any two t, t0 , we have
n
X
i=1

|rt (i) − r (i)| = 2
t0

n/2
X
i=n/3

|t(i) − t0 (i)|.

Therefore, by Lemma 5.4, there exists a set T ⊂ R that collects those rt ’s, such that for
Pn
c2 n . We bound the
any two different rt , rt0 ∈ T ,
i=1 |rt (i) − rt0 (i)| ≥ c1 m and |T | ≥ e
Kullback-Leiber diameter by
dKL (T ) ≤ sup

rt ,rt0 ∈T

nβ̃ 2 krt − rt0 k2
nβ̃ 2 m2
≤
C
.
σ2
σ2

Apply Fano’s inequality to the loss k · k1 , and we get
2

inf sup Pr
r̂ r∈R



2

C nβ̃σ2m + log 2
c1 m 
≥1−
.
kr̂ − rk1 ≥
4
c2 n

q

nσ 2
2 for some sufficiently small constant c > 0, and then we get the
We take m = c
∧
n
2
β
desired lower bound for inf r̂ supr∈R Er `1 (r̂, r) by applying a Markov inequality.
21

2

Proof of Theorem 2.3 when nβ
> 1. We consider the distribution Xij ∼ N (β̃(r(i)−r(j)), σ 2 )
4σ 2
as in the previous part of the proof. The β̃ is chosen as (1 + o(1))β so that (2), (3) and (5)
are satisfied. Since
inf sup Er `2 (r̂, r) ≥ inf sup Er `1 (r̂, r) ≥ inf sup Er `0 (r̂, r),
r̂ r∈R

r̂ r∈R

r̂ r∈R

we only need to prove the lower bound for inf r̂ supr∈R Er `0 (r̂, r). Define
(
)
n
n
X
X
R̃ = r ∈ R :
r(i) −
i ≤1 .
i=1

i=1

Then, we have
inf sup Er n`0 (r̂, r) ≥ inf sup Er n`0 (r̂, r) ≥ inf
r̂ r∈R

r̂ r∈R̃

r̂

n
X
1 X
Pr (r̂(i) 6= r(i)) .
|R̃|
i=1

(28)

r∈R̃

For an i ∈ {2, 3, ..., n − 1}, any r ∈ R̃ can be written as r = (ri , r−i ) with some slight abuse
of notation, where we use ri to denote the ith entry of r and r−i to denote the remaining
entries. Then, the set R̃ has the following decomposition
R̃ = ∪r−i Rr−i ,
where all the elements in Rr−i have the same entries except for the ith one. It is easy to see
that
X
|Rr−i |.
|R̃| =
r−i

P
According to the definition of R̃, for any r ∈ R̃, the sum ni=1 r(i) only takes three posP
P
P
sible values in {( ni=1 i) − 1, ni=1 i, ( ni=1 i) + 1}. Therefore, for each possible r−i with
i ∈ {2, 3, ..., n − 1}, we have |Rr−i | = 3. We then take a subset R̃r−i ⊂ Rr−i with |R̃r−i | = 2
so that the two elements in R̃r−i satisfy kr − r0 k2 = 1. We continue to lower bound (28) by
inf
r̂

i=2

≥ inf
r̂

≥ inf
r̂

n−1
X

n−1
X
i=2

1 X
Pr (r̂(i) 6= r(i))
|R̃|
r∈R̃

X
1 X
1
|Rr−i |
Pr (r̂(i) 6= r(i))
|R| r
|Rr−i |
r∈Rr−i

−i

n−1
X
1X 1 X
|Rr−i |
Pr (r̂(i) 6= r(i))
3
|R| r
i=2

r∈R̃r−i

−i

≥

n−1
X
1X 1 X
|Rr−i | inf
Pr (r̂(i) 6= r(i))
3
|R| r
r̂(i)

=

n−1
X
1X 1 X
|Rr−i | inf
Pr (r̂ 6= r).
r̂
3
|R| r

i=2

i=2

r∈R̃r−i

−i

r∈R̃r−i

−i

22

Now it is sufficient to lower bound each inf r̂

P

r∈R̃r−i

Pr (r̂ 6= r). We denote the two elements

in R̃r−i by r and r̃. Then, by Neyman-Pearson lemma, we have
inf

X

r̂

r∈R̃r−i

Pr (r̂ 6= r) = Pr (L(r̃) ≤ L(r)) + Pr̃ (L(r) ≤ L(r̃)) = 2P N (0, 1) >

√

n − 1β̃
√
2σ

!
,

where the last identity above is using the fact that kr − r̃k2 = 1. By a standard normal tail
bound argument, we have
!
!
√


(n − 1)β̃ 2
n − 1β̃
nβ 2
& exp −
=
exp
−(1
+
o(1))
.
P N (0, 1) > √
4σ 2
4σ 2
2σ
Therefore,
inf sup Er `0 (r̂, r) ≥
r̂ r∈R

n−1
X
1 X 1 X
Pr (r̂ 6= r)
|Rr−i | inf
r̂
3n
|R| r
i=2

−i

r∈R̃r−i



nβ 2
& exp −(1 + o(1)) 2 ,
4σ
and the proof is complete.

5.3

Proofs of Theorem 2.4 and Theorem 2.5

The proof of Theorem 2.4 is a simple application of Markov inequality.
Proof of Theorem 2.4. Under the assumption, there exists a small positive constant δ > 0,
such that
nβ 2
≥ (1 + δ) log n,
4σ 2
for any sufficiently large n. Then, we have


1
Pr (r̂ 6= r) = Pr `0 (r̂, r) ≥
n
≤ nEr `0 (r̂, r)


nβ 2
≤ n exp −(1 + o(1)) 2
4σ
≤ n−(1+o(1))δ .
The proof is complete by letting n tend to infinity.
To prove Theorem 2.5, we needs the following bound for the maximum of dependent
Gaussian random variables, which is a result in [8].

23

Lemma 5.5. Consider zero-mean Gaussian random variables W1 , ..., Wn with covariance
matrix of minimum eigenvalue λ and maximum eigenvalue Λ. Then, for n ≥ 70,


1
1/2
P max Wi ≥ λ (2 log n − 2.5 − log(2 log n − 2.5)) − 0.68Λ ≥ .
1≤i≤n
2
Proof of Theorem 2.5. We again consider the distribution Xij ∼ N (β̃(r(i) − r(j)), σ 2 ) as in
the proof of Theorem 2.3. The β̃ is chosen as (1 + o(1))β so that (2), (3) and (5) are satisfied.
In the proof, we assume that n is an even number, otherwise a simple modification of the
argument can be done. Note that
inf sup Pr (r̂ 6= r) ≥ inf
r̂ r∈R

r̂

1 X
1 X
Pr (r̂ 6= r) =
Pr (r̂ 6= r),
|R|
|R|
r∈R

r∈R

where r̂ = argminr∈R L(r) is the MLE. Therefore, it suffices to give a lower bound for each
Pr (r̂ 6= r). Without loss of generality, we consider r with r(i) = i. Then, for each j ∈ [n], we
choose an rj ∈ R that differs with r only at the jth position and krj − rk2 = 1. We have the
lower bound


Pr (r̂ 6= r) ≥ Pr

min L(rj ) < L(r) .

j∈[n]

After some rearrangement, we have

Pr



min L(rj ) < L(r) = Pr  min

j∈[n]


X

j∈[n]

(Zij − Zji ) ≤ −(n − 1)β/σ  ,

i∈[n]\{j}

where Zij = Xij − β̃(i − j) ∼ N (0, σ 2 ). The above probability equals
!
√
n − 1β̃
,
P max Wj > √
j∈[n]
2σ
where Wj ∼ N (0, 1) and EWi Wj = (n − 1)−1 for all i 6= j. Using a similar argument, we can
show the same lower bound for Pr (r̂ 6= r) with any other r ∈ R. Therefore,
!
√
1 X
n − 1β̃
Pr (r̂ 6= r) ≥ P max Wj > √
.
|R|
j∈[n]
2σ
r∈R
Under the assumption that lim supn

nβ 2
4σ 2 log n

< 1, there exists a small δ > 0, such that

nβ 2
4σ 2

< (1 − δ) log n for any sufficiently large n. To use Lemma 5.5, it is easy to check that
n−2
the smallest and the largest eigenvalues of the covariance matrix of W1 , ..., Wn are n−1
and
2, respectively. Therefore, by Lemma 5.5, we have
!
√
n − 1β̃
1
P max Wj > √
≥ ,
2
j∈[n]
2σ
for any sufficiently large n. Hence, the proof is complete.
24

5.4

Proofs of Theorem 3.1, Theorem 3.2 and Theorem 3.3

Before the proof of each theorem, we state one or two auxiliary lemmas. The proofs of these
lemmas will be given in Section 5.6.
Lemma 5.6. Consider the differential comparison model that satisfies (2), (8) and (9). For
any m such that Rm 6= ∅, we have
!


n
n
X
X
nβ 2 m
2
2
max Pr
(Si − θr̃(i) ) ≤
,
(Si − θr(i) )
≤ exp −(1 + o(1))
r̃∈Rm
4σ 2
i=1

i=1

where Si and Rm are defined in (10) and (20).
2

Proof of Theorem 3.1. For the exponential rate in the regime nβ
> 1, the proof is the
4σ 2
same as that of Theorem 2.1. One only needs to replace Lemma 5.1 by Lemma 5.6. Now
2
we give the proof of the polynomial rate in the regime nβ
We use the notation
2 ≤ 1.
4σ
Pn
Pn
√
∆r = j=1 θr(j) − j=1 θj . By (9), we have maxr∈R |∆r | = o( nβ). Note that for each i,
Er Si = θr(i) − ∆r /n. Using the condition (8), we have
kr̂ − rk2 ≤

n
1 X
(θr̂(i) − θr(i) )2
β2
i=1

≤

n
n
2 X
2 X
2
(θ
−
S
)
+
(Si − θr(i) )2
i
r̂(i)
β2
β2

≤

4
β2

≤

8
β2

i=1
n
X
i=1
n
X
i=1

i=1

(Si − θr(i) )2

(29)

(Si − θr(i) − ∆r /n)2 +

8∆2r
,
nβ 2

(30)

where the inequality (29) is by the definition of r̂ in (11). We use the notation Zij =
Xij − µr(i)r(j) . For each i ∈ [n], we have

E(Si − θr(i) − ∆r /n)2 = E 

1
2n

2
X

(Zij − Zji ) .

j∈[n]\{i}

σ2
,
n

by using the condition (2). Therefore, the bound (30) implies
Er `2 (r̂, r) .
where the second term

∆2r
n2 β 2

∆2r
σ2
+
,
nβ 2 n2 β 2

is negligible given the condition (9) and
σ2
2
nβ
p

n2 .

nβ 2
4σ 2

≤ 1. Hence, we

∧
The bound for Er `1 (r̂, r) is immediately implied
obtain the bound Er `2 (r̂, r) .
p
by Er `1 (r̂, r) ≤ Er `2 (r̂, r) ≤ Er `2 (r̂, r). The exact recovery result follows a simple application of Markov inequality as is done in the proof of Theorem 2.4. Thus, the proof is
complete.
25

Lemma 5.7. Consider the additive collaboration model that satisfies (2) and (8). For any
m such that Rm 6= ∅, we have
!


n
n
X
X
nβ 2 m
2
2
,
max Pr
(Si − θr̃(i) ) ≤
(Si − θr(i) )
≤ exp −(1 + o(1))
r̃∈Rm
4σ 2
i=1

i=1

where Si and Rm are defined in (13) and (20).
2

Proof of Theorem 3.2. For the exponential rate in the regime nβ
> 1, the proof is the same
4σ 2
as that of Theorem 2.1. One only needs to replace Lemma 5.1 by Lemma 5.7. For the
2
polynomial rate in the regime nβ
≤ 1, we use the same argument that leads to (29), and we
4σ 2
have
n
4 X
kr̂ − rk2 ≤ 2
(Si − θr(i) )2 .
β
i=1

By the definition (13) and the condition (2),

Er (Si − θr(i) )2 = Er 



1

2(n − 2)

X

j∈[n]\{i}

(Zij + Zji ) −

1
n−1

2
X
1≤i6=j≤n

Zij  .

σ2
.
n

q
p
p
σ2
σ2
2 and E ` (r̂, r) ≤ E
This implies Er `2 (r̂, r) . nβ
∧
n
`
(r̂,
r)
≤
E
`
(r̂,
r)
.
∧ n.
r
1
r
2
r
2
2
nβ 2
The exact recovery result follows a simple application of Markov inequality as is done in the
proof of Theorem 2.4. Thus, the proof is complete.
Lemma 5.8. Consider either the differential comparison model or the additive collaboration
model with θi = α + β̃i for some β̃ = (1 + o(1))β. Assume the condition (2). For any m such
that Rm 6= ∅, we have


nβ 2 m
max Pr (PL(r̃) ≤ PL(r)) ≤ exp −(1 + o(1))
,
r̃∈R0m
4σ 2
where R0m = Rm ∩ R0 and Si is defined in Section 3.3.
Lemma 5.9. Consider either the differential comparison model or the additive collaboration
model with θi = α + β̃i for some β̃ = (1 + o(1))β. Assume the condition (2). For any r ∈ R0 ,
and t > 0 and any l ≥ 1, we have



 0 2 22

Cβ t l
Pr
min
PL(r̃) ≤ PL(r) ≤ 2 exp −n
−
5
,
σ2
{r̃∈R0 :tl<kr̃−rk≤t(l+1)}
where C 0 > 0 is some universal constant.
Proof of Theorem 3.3. The exponential rate is by the same proof of Theorem 2.1 with the
help of Lemma 5.2 and Lemma 5.8. For the polynomial rate, we define the set
R̃0l = {r̃ ∈ R : tl < kr̃ − rk ≤ t(l + 1)} .
26


 P


∞
0 ≤
P
r̂
∈
R̃
P
inf
PL(r̃)
≤
PL(r)
. By
0
l=1 r
l=1 r
l
r̃∈R̃

P∞

Then, we have Pr (kr̂ − rk > t) ≤
Lemma 5.9, we have the bound
2

∞
X
l=1

l



 0 2 2


 0 2 22
Cβ t
Cβ t l
−5
. exp −n
−5
.
exp −n
σ2
σ2

Therefore, there are some constants C, C1 > 0, such that


σ2
2
Pr kr̂ − rk > C 2 (1 + x) . exp (−C1 nx) ,
β
for any x > 0. Integrating up the tail, we obtain the desired polynomial convergence rate
p
for Er `2 (r̂, r). The result for Er `1 (r̂, r) is by the inequality Er `1 (r̂, r) ≤ Er `2 (r̂, r) ≤
p
Er `2 (r̂, r). The exact recovery result follows a simple application of Markov inequality as
is done in the proof of Theorem 2.4. The proof is complete.

5.5

Proofs of Theorem 4.1, Theorem 4.2 and Theorem 4.3

We first give a lemma to facilitate the proof of Theorem 4.1.
Lemma 5.10. Assume (19). For any m such that Rm 6= ∅ that is defined in (20), we have


Xij
Xij
Y µr̃(i)r̃(j)
Y µr(i)r(j)
e−µr̃(i)r̃(j)
e−µr(i)r(j)

 ≤ exp −nβ 2 m .
max Pr 
≥
r̃∈Rm
Xij !
Xij !
1≤i6=j≤n

1≤i6=j≤n

Proof of Theorem 4.1. The proof is essentially the same as that of Theorem 2.1. The only
difference is that we use Lemma 5.10 instead of Lemma 5.1. Therefore, we only need to
2
replace all the nβ
in the proof of Theorem 2.1 by nβ 2 and obtain the desired result.
4σ 2
Proof of Theorem 4.2. We consider the distribution Xij ∼ Poisson(µr(i)r(j) ), where
2α + β̃(i + j). We set α = β̃n2 . Note that for any r, r̃ ∈ R,
X
1≤i6=j≤n

µij =

p
2
p
µr̃(i)r̃(j) − µr(i)r(j)

X

= β̃ 2

√

1≤i6=j≤n

(r̃(i) + r̃(j) − r(i) − r(j))2


= β̃ 2 2(n − 2)kr̃ − rk2 + 2

n
X
i=1

!2 
(r(i) − r̃(i)) 

= 2(1 + o(1))nβ̃ 2 kr̃ − rk2 .
Therefore, the condition (19) is satisfied with some β = (1+o(1))β̃. We first derive polynomial
lower bounds when nβ 2 ≤ 1. We use the same argument in the proof of Theorem 2.3. The

27

only difference is the calculation of dKL (T ). For any rt , rt0 ∈ T ⊂ R,

D ⊗1≤i6=j≤n Poisson(µr(i)r(j) )k ⊗1≤i6=j≤n Poisson(µr̃(i)r̃(j) )

X 
µr(i)r(j)
µr(i)r(j) log
=
− µr(i)r(j) + µr̃(i)r̃(j)
µr̃(i)r̃(j)
1≤i6=j≤n

≤

X
1≤i6=j≤n

(µr(i)r(j) − µr̃(i)r̃(j) )2
µr̃(i)r̃(j)

= 4(1 + o(1))

X
1≤i6=j≤n

(µr(i)r(j) − µr̃(i)r̃(j) )2
,
√
√
( µr(i)r(j) + µr̃(i)r̃(j) )2

where the last inequality is because maxi,j,i0 ,j 0

q

µij
µi0 j 0

= 1 + o(1). This leads to the bound

dKL (T ) . max nβ̃ 2 krt − rt0 k2 .
rt ,r 0 ∈T
t

Therefore, the same argument in the proof of Theorem 2.3 will go through if we replace every
nβ̃ 2
by nβ̃ 2 . This leads to the desired lower bounds inf r̂ supr∈R `1 (r̂, r) & (nβ 2 )−1/2 ∧ n and
4σ 2
inf r̂ supr∈R `2 (r̂, r) & (nβ 2 )−1 ∧ n2 when nβ 2 ≤ 1.
Now we give exponential lower bounds when nβ 2 > 1. By the same argument in the proof
of Theorem 2.3, the lower bounds are determined by the following quantity


Xij
Xij
Y µr̃(i)r̃(j)
Y µr(i)r(j)
e−µr̃(i)r̃(j)
e−µr(i)r(j)
,
Pr 
>
(31)
Xij !
Xij !
1≤i6=j≤n

1≤i6=j≤n

for some r and r̃ that satisfy kr̃−rk2 = 1. Without loss of generality, We assume |r̃(1)−r(1)| =
1 and r̃(i) = r(i) for all i > 1. Then, the above probability can be written as
!
n
n
Y

 Y


Pr
p X1i |µr̃(1)i p Xi1 |µir̃(1) >
p X1i |µr(1)i p Xi1 |µir(1) ,
i=2

i=2

where we use p(X|µ) to denote the probability mass function of Poisson(µ). For any t ∈ (0, 1),
we use the following general argument




q
q
(X) > 1
≥ P 0 < t log (X) < L
P
p
p
Z
=
p(x)
{0<t log pq (x)<L}

t

Z
=

{0<t log pq (x)<L}

p(x)t

R

p1−t q t

p1−t q t

Z
p1−t q t e−L pt (x)
 Z
 

q
1−t t
= exp log p q − L Pt 0 < t log (X) < L ,
p
≥

Z

q(x)
p(x) p(x)
t
q(x)t R

28

where the distribution Pt has density function
to p1−t q t . In general, we choose
r  proportional

2
R
t to minimize log p1−t q t and L = t Pt log pq . For P = ⊗i Poisson(µi ) and Q =
⊗i Poisson(µ̃i ), direct calculation gives
Z
X

− log p1−t q t =
tµ̃i + (1 − t)µi − µ̃ti µi1−t .
i

√
√
| µ − µ̃ |

i
t
√i
Moreover, Pt = ⊗i Poisson(µ1−t
i µ̃i ). Under the current setting, maxi min(√µi , µ̃i ) = o(1).
Therefore, a Taylor expansion argument gives the bound
X
X √
p 2

tµ̃i + (1 − t)µi − µ̃ti µi1−t ≤ 2(1 + o(1))t(1 − t)
µi − µ̃i .

i

i

This leads to
max

t∈(0,1)

X

tµ̃i + (1 − t)µi − µ̃ti µi1−t

i



≤

p 2
1 + o(1) X √
µi − µ̃i
2

=

n
n 
2 1 + o(1) X
2
1 + o(1) X p
p
p
p
µr(1)i − µr̃(1)i +
µir(1) − µir̃(1)
2
2

i

i=2

i=2

2

= (1 + o(1))nβ .
On the other hand, it is easy to see that lower bound
max

t∈(0,1)

X
i

p 2
 1 X √
tµ̃i + (1 − t)µi − µ̃ti µ1−t
≥
µ
−
µ̃i .
i
i
2
i

R
Therefore, the t that minimizes log p1−t q t satisfies t = 12 (1 + o(1)). We give a bound for L.

2


R
Since t minimizes log p1−t q t , we have Pt log pq = VarPt log pq . Note that

 X

p 2
q
µi 2 1−t t X √
VarPt log
=
log
µi µ̃i .
µi − µ̃i . nβ 2 ,
p
µ̃i
i

where we have used the fact maxi

i

q

µi
µ̃i

= 1 + o(1). Therefore, we have

 Z



p
exp log p1−t q t − L ≥ exp −(1 + o(1))nβ 2 − Cnβ 2 ,

for some constant C > 0. Next, we need to lower bound Pt 0 <

t
L


log pq (X) < 1 . Since

log pq (X) is sum of independent random variables, and it is properly standardized, we
only need to establish a central limit theorem for L1 log pq (X). Thus, it is sufficient to check
Lyapunov’s condition. Under the current setting, Lyapunov’s condition is easily satisfied
1
L

29

by maxi

q


≤ 1 + o(1). Hence, Pt 0 <

µi
µ̃i

t
L


log pq (X) < 1 ≥ c for some constant c > 0.

Therefore, up to a constant, we have obtained the following lower bound for (31),
!!
!


p
1
nβ 2 .
exp −(1 + o(1))nβ 2 − Cnβ 2 = exp −(1 + o(1)) 1 + O p
nβ 2


2 .
For the case nβ 2 = O(1), this
is
of
a
constant
order,
which
is
of
the
same
order
as
exp
−(1
+
o(1))nβ
p
For the case nβ 2 → ∞, Cnβ 2 is of a smaller order compared with nβ 2 , and the bound

exp −(1 + o(1))nβ 2 still holds. The proof is complete.
Proof of Theorem 4.3. The upper bound follows the simple argument of Markov inequality
as is done in the proof of Theorem 2.4. We give the proof of the lower bound by following
the same argument in the proof of Theorem 2.5. Consider r with r(i) = i. Then, for each
l ∈ [n], we choose an rl ∈ R that differs with r only at the jth position and krl − rk2 = 1.
By the same argument used in the proof of Theorem 2.5, the lower bound is determined by
the following probability,


Y
Y
Pr max
p(Xij |µrl (i)rl (j) ) >
p(Xij |µr(i)r(j) ) ,
l∈[n]

1≤i6=j≤n

1≤i6=j≤n

where we use p(X|µ) to denote the probability mass function of Poisson(µ). By the construction of rl ’s, the probability above equals


Y p(Xil |µr (i)r (l) ) p(Xli |µr (l)r (i) )
l
l
l
l
Pr max
> 1 .
(32)
p(Xil |µr(i)r(l) ) p(Xli |µr(l)r(i) )
l∈[n]
i∈[n]\{l}

Since maxi,l

µrl (i)rl (l) −µr(i)r(l)
µr(i)r(l)

= o(1), a Taylor expansion argument leads to

µr(i)r(l)
+ µrl (i)rl (l) − µr(i)r(l)
µrl (i)rl (l)
i∈[n]\{l}
2
X p
p
= 2(1 + o(1))
µrl (i)rl (l) − µr(i)r(l)
X 



µr(i)r(l) log

i∈[n]\{l}

= 2n(1 + o(1))β 2 .
Therefore,
log

Y
i∈[n]\{l}

p(Xil |µrl (i)rl (l) )
=
p(Xil |µr(i)r(l) )

X

(Xil − µr(i)r(l) ) log

i∈[n]\{l}

µrl (i)rl (l)
− 2n(1 + o(1))β 2 ,
µr(i)r(l)

and thus we can lower bound (32) by


√
Pr max Yl > 2n(1 + o(1))β ,
l∈[n]

30

where


1

X


Yl = p
2(n − 1) i∈[n]\{l}

Xil − µr(i)r(l)
µr (i)r (l)
log l l +
2β
µr(i)r(l)

X
i∈[n]\{l}


Xli − µr(l)r(i)
µrl (l)rl (i)
.
log
2β
µr(l)r(i)

Note that

Var

Xil − µr(i)r(l)
µr (i)r (l)
log l l
2β
µr(i)r(l)



µr(i)r(l)
=
4β 2



µrl (i)rl (l) 2
log
= 1 + o(1),
µr(i)r(l)

where the last equality is by a Taylor expansion argument. Moreover, the Poisson tail of
µr (i)r (l)
Xil −µr(i)r(l)
log µ l l is well behaved. Therefore, we can apply a high-dimensional Gaussian
2β
r(i)r(l)
approximation result by [5], and obtain




√
√
Pr max Yl > 2n(1 + o(1))β − Pr max Wl > 2n(1 + o(1))β = o(1),
l∈[n]

l∈[n]

where W1 , ..., Wn are jointly Gaussian with zero mean, and the covariance structure is determined by EWl2 = o(1) and maxj≤l EWj Wl = O(n−1 ). Therefore, by Lemma 5.5 and the
nβ 2
condition lim supn log
n < 1, we have


√
1
Pr max Yl > 2n(1 + o(1))β ≥ − o(1),
2
l∈[n]
which implies the desired result. The proof is complete.

5.6

Proofs of Auxiliary Lemmas

Proof of Lemma 5.1. We first bound Pr (L(r̃) ≤ L(r)) for any r̃, r ∈ R. Direct calculation
gives
Pr (L(r̃) ≤ L(r))

X
= Pr 2
(µr(i)r(j) − µr̃(i)r̃(j) )(Xij − µr(i)r(j) ) ≤ −
1≤i6=j≤n


X

(µr̃(i)r̃(j) − µr(i)r(j) )2  .

1≤i6=j≤n

By the condition (2), the above probability is upper bounded by


X
1
(µr̃(i)r̃(j) − µr(i)r(j) )2  ,
exp − 2
8σ
1≤i6=j≤n



2
2 according to the condition (3). Therefore,
which is further bounded by exp − nβ
kr̃
−
rk
4σ 2
we have




nβ 2
nβ 2 m
2
sup Pr (L(r̃) ≤ L(r)) ≤ sup exp − 2 kr̃ − rk = exp −
.
4σ
4σ 2
r̃∈Rm
r̃∈Rm
The proof is complete.
31

Proof of Lemma 5.2. To get an element in Rm , we can first pick l ∈ [m] and then only
focused on those r̃ that differs with r at l positions. Next, we pick l positions from [n]. The
error at each position is defined as n1 , ...nl , respectively. They must satisfy n21 + · · · + n2l = m.
This gives the bound
min(m,n) 

|Rm | ≤

n
l

X
l=1



X
n21 +···+n2l =m

n1 · · · nl .

Note that under the constraint n21 + · · · + n2l = m, we have





1
1
m
2
2
log n1 + · · · log nl
≤ exp
,
n1 · · · nl = exp
l log
2
2
l
by Jensen’s inequality. This leads to the bound






X
m−1
1
m
3
em
n1 · · · nl ≤
exp
l log
≤ exp
l log
.
l−1
2
l
2
l
2
2
n1 +···+nl =m

For 1 ≤ m ≤ n, we have
|Rm | ≤ e

3
m
2

m  
X
n
l=1

l


≤ exp

 en 
3
m + m log
2
m


=

e5/2 n
m

!m





.

For n < m ≤ n2 , we have
|Rm | ≤ 2

n

n
X


exp

l=1

3
em
l log
2
l



n

≤2 e

3
n
2

n
X


exp

l=1

9
m
+ l log
4
l

≤

e6 m
n

n
.

Finally, for m > n2 , we have |Rm | ≤ |R| ≤ nn , and the proof is complete.
Proof of Lemma 5.3. We first introduce some notation. For any r ∈ R, we use µ(r) to
denote an n × n matrix whose diagonal entries are all 0 and off-diagonal entries are given by
µ(r)ij = µr(i)r(j) . Moreover, for any matrix that appears in this proof, its off-diagonal entries
are all 0. In this way, we can write L(r) = kZk2F and L(r̃) = kX − µ(r̃)k2F . We give a lower
bound for L(r̃),
L(r̃) = kZ + µ(r) − µ(r̃)k2F

= kZk2F + kµ(r) − µ(r̃)k2F + 2 hZ, µ(r) − µ(r̃)i
≥ kZk2F + 2nβ 2 l2 t2 + 2 hZ, µ(r) − µ(r̃)i ,

where the last inequality is by
kµ(r) − µ(r̃)k2F ≥ 2nβ 2 kr̃ − rk2 ≥ 2nβ 2 l2 t2 ,
according to the condition (3) and kr̃ − rk ≥ lt. Therefore, we have
min

{r̃∈R:tl<kr̃−rk≤t(l+1)}

L(r̃) − L(r) ≥ 2nβ 2 l2 t2 + 2
32

min

{r̃∈R:kr̃−rk≤t(l+1)}

hZ, µ(r) − µ(r̃)i ,

and we obtain the bound


min
L(r̃) ≤ L(r)
Pr
{r̃∈R:tl<kr̃−rk≤t(l+1)}


2 2 2
≤ P
max
|hZ, µ(r) − µ(r̃)i| ≥ nβ l t
{r̃∈R:kr̃−rk≤t(l+1)}

n2 β 4 l 4 t 4
. exp −C
max{r̃∈R:kr̃−rk≤t(l+1)} |hZ, µ(r) − µ(r̃)i|


2
ψ2



2

The norm k · kψ2 is the Orlicz norm with function ψ2 (x) = ex − 1.
2
Now it is sufficient to bound max{r̃∈R:kr̃−rk≤t(l+1)} |hZ, µ(r) − µ(r̃)i| ψ . We let the truth
2
r be fixed. Then, for any r̃ ∈ R, define Z(r̃) = hZ, µ(r) − µ(r̃)i, a sub-Gaussian process on
R. Note that for any r̃1 , r̃2 , we have


t2
P (|Z(r̃1 ) − Z(r̃2 )| > t) ≤ 2 exp − 2
(33)
2σ kµ(r̃) − µ(r̃)k2F


t2
≤ 2 exp −
,
(34)
4M nσ 2 β 2 kr̃1 − r̃2 k2
where the inequality (33) is by (2), and the inequality (34) is by (5). Therefore, by Lemma
2.2.1 of [17], the natural semimetric between Z(r̃1 ) and Z(r̃2 ) is
p
d(r̃1 , r̃2 ) = 12M nσ 2 β 2 kr̃1 − r̃2 k2 .
We use Corollary 2.2.5 of [17], and get
max

{r̃∈R:kr̃−rk≤t(l+1)}

≤

|hZ, µ(r) − µ(r̃)i|

√max

{r̃∈R:d(r̃,r)≤

12M nσ 2 β 2 t2 (l+1)2 }

ψ2

|hZ, µ(r) − µ(r̃)i|

Z √12M nσ2 β 2 kr−r0 k2 q

log 1 + N (, R̄l , d) d,
.

ψ2

0

where N (, R̄l , d) denotes the covering number of
p
R̄l = {r̃ ∈ R : d(r̃, r) ≤ 12M nσ 2 β 2 t2 (l + 1)2 }
with respect to the distance d and radius . A standard volume ratio argument gives
Z √12M nσ2 β 2 t2 (l+1)2 q
p

log 1 + N (, R̄l , d) d . M n2 σ 2 β 2 t2 (l + 1)2 .
0

Finally, the exponent has lower bound
n2 β 4 l 4 t 4
max{r̃∈R:kr̃−rk≤t(l+1)} |hZ, µ(r) − µ(r̃)i|
which completes the proof.
33

2
ψ2

&

β 2 t2 l 2
,
M σ2

P
Pn
θr(j) − nj=1 θj . By (9), we have
Proof of Lemma 5.6. We use the notation ∆r =
j=1
√
maxr∈R |∆r | = o( nβ). Note that for each i, Er Si = θr(i) − ∆r /n. With some direct
P
P
calculation, the event ni=1 (Si − θr̃(i) )2 ≤ ni=1 (Si − θr(i) )2 is equivalent to
2

n
X
i=1

(θr(i) − θr̃(i) )(Si − θr(i) + ∆r /n) ≤ −

n
X
i=1

(θr(i) − θr̃(i) )2 + 2∆r (∆r − ∆r̃ )/n.

Using the conditions (8) and (9), we get the bound
−

n
X
i=1

(θr(i) − θr̃(i) )2 + 2∆r (∆r − ∆r̃ )/n ≤ −(1 + o(1))

n
X
i=1

(θr(i) − θr̃(i) )2 .

Therefore, it suffices to bound
Pr

2

n
X
i=1

n
X
(θr(i) − θr̃(i) )(Si − θr(i) + ∆r /n) ≤ −(1 + o(1))
(θr(i) − θr̃(i) )2

!
.

i=1

By (2), we get the bound
exp −(1 + o(1))

n

Pn

i=1 (θr(i)
4σ 2

− θr̃(i) )2

!
.

Finally, using (8), we obtain the desired rate, and the proof is complete.
Proof of Lemma 5.7. Note that for the Si defined in (13), we have Er Si = θr(i) . Some direct
calculation gives
!
n
n
X
X
Pr
(Si − θr̃(i) )2 ≤
(Si − θr(i) )2
≤ Pr

i=1
n
X

2

i=1

i=1

(θr(i) − θr̃(i) )(Si − θr(i) ) ≤ −

n
X
i=1

!
2

(θr(i) − θr̃(i) )

.

Using (2) and (8), we obtain the bound
!
P


n ni=1 (θr(i) − θr̃(i) )2
nβ 2 kr̃ − rk2
≤ exp −(1 + o(1))
,
exp −(1 + o(1))
4σ 2
4σ 2
and the proof is complete.
Proof of Lemma 5.8. We use 1 ∈ Rn to denote a column vector with entries all 1. Given an
r ∈ R0 , define the hat matrix by


I − n1 11T rrT I − n1 11T
1 T
Hr = 11 +
.
(35)
 2
n
I − 1 11T r
n

Using basic facts of linear regression, we get
PL(r) = k(I − Hr )Ŝk2 .
34

Then, with some rearrangement, the inequality PL(r̃) ≤ PL(r) is equivalent to
D
E
2 (I − Hr̃ )Er Ŝ, Ŝ − Er Ŝ ≤ − (I − Hr̃ )Er Ŝ
Note that

2

.

(36)

Er Ŝ = β̃r + C 1,

where the value of C depends on whether it is the comparison model or the collaboration
model. According to the definition of the projection matrix I − Hr , we have (I − Hr )1 = 0,
so that (36) can be equivalently written as
D
E
2β̃ (I − Hr̃ )r, Ŝ − Er Ŝ ≤ −β̃ 2 k(I − Hr̃ )rk2 .
(37)
Using (2), we get
 D
E

Pr (PL(r̃) ≤ PL(r)) = Pr 2β̃ (I − Hr̃ )r, Ŝ − Er Ŝ ≤ −β̃ 2 k(I − Hr̃ )rk2
!
nβ 2 k(I − Hr̃ )rk2
.
≤ exp −(1 + o(1))
4σ 2
Now it is sufficient to study k(I − Hr̃ )rk2 . Define




1 T
1 T
x = I − 11
r and y = I − 11
r̃.
n
n
Then,
yT x
y
k(I − Hr̃ )rk = x −
kyk2

2

2

Since

1 T
1
11 r − 11T r̃
n
n

2

1
=
n

n
X
i=1

= kx − yk2 −

r(i) −

n
X



(38)

!2
r̃(i)

= O(c2n /n) = o(1),

i=1

we have
kx − yk2 = (r − r̃) −

|(x − y)T y|2
.
kyk2

1 T
1
11 r − 11T r̃
n
n



2

= (1 + o(1))kr − r̃k2 .

Moreover,
|(x − y)T y|2
kyk2

≤
=

2
2 (x − y)T x−y
2 (x + y)T
2
+
kyk2
kyk2
kx − yk2 |kxk2 − kyk2 |2
+
.
2kyk2
2kyk2

x−y  2
2

(39)

Note that kyk2 & n3 . Thus, the first term of (39) is bounded by o(1)kr̃ − rk2 . The second
term of (39) is bounded by o(1) according to the definition of R0 . Therefore,
k(I − Hr̃ )rk2 ≥ (1 + o(1))kr̃ − rk2 ,
35

(40)

and thus we have
nβ 2 kr̃ − rk2
Pr (PL(r̃) ≤ PL(r)) ≤ exp −(1 + o(1))
4σ 2



.

Take maximum over r̃ ∈ R0m , and the proof is complete.
Proof of Lemma 5.9. We will borrow arguments and notations from the proof of Lemma 5.8.
Recall the hat matrix defined in (35). By (38), we have
k(I − Hr̃ )rk2 ≤ kr − r̃k2 .
Then using (40), we obtain
k(I − Hr̃ )rk2 = (1 + o(1))kr − r̃k2 .
Using the same argument that derives (37), we have
PL(r̃) − PL(r)
 D
E

=
min
2β̃ (I − Hr̃ )r, Ŝ − Er Ŝ + β̃ 2 k(I − Hr̃ )rk2
{r̃∈R0 :tl<kr̃−rk≤t(l+1)}
D
E
≥
min
2β̃ (I − Hr̃ )r, Ŝ − Er Ŝ + (1 + o(1))β̃ 2 t2 l2
{r̃∈R0 :kr̃−rk≤t(l+1)}
D
E
≥
min
2β̃ v, Ŝ − Er Ŝ + (1 + o(1))β̃ 2 t2 l2 .
min

{r̃∈R0 :tl<kr̃−rk≤t(l+1)}

{v∈Rn :kvk≤2t(l+1)}

Therefore,

max

Pr

≤ Pr
≤ Pr

{r̃∈R0 :tl<kr̃−rk≤t(l+1)}


PL(r̃) ≤ PL(r)


D
E
v, Ŝ − Er Ŝ ≥ (1 + o(1))|β̃|t2 l2 /2
{v∈Rn :kvk≤2t(l+1)}
!
D
E
|β̃|tl
.
max
v, Ŝ − Er Ŝ ≥ (1 + o(1))
8
{v∈Rn :kvk≤1}
max

(41)

A standard discretization argument in [7, Lemma A.1] gives
D
E
D
E
max
v, Ŝ − Er Ŝ ≤ 2 max vj , Ŝ − Er Ŝ ,
1≤j≤J

{v∈Rn :kvk≤1}

Rn

where {vj }1≤j≤J is a subset of {v ∈
: kvk ≤ 1} such that for any v ∈ Rn with kvk ≤ 1,
there is some j ∈ [L] that satisfies kvj − vk ≤ 1/2, and a covering number argument gives
the bound J ≤ e5n . By union bound, we can bound (41) by
!
D
E
|β̃|tl
Pr max vj , Ŝ − Er Ŝ ≥ (1 + o(1))
1≤j≤J
16
!
J
D
E
X
|β̃|tl
vj , Ŝ − Er Ŝ ≥ (1 + o(1))
≤
Pr
16
j=1


nβ 2 t2 l2
≤ 2 exp 5n − C 0
,
σ2
36

for some constant C 0 > 0, and the last inequality above is by (2). Therefore, the proof is
complete.
Proof of Lemma 5.10. For any r̃ ∈ Rm , we have


Xij
Xij
Y µr(i)r(j)
Y µr̃(i)r̃(j)
e−µr(i)r(j)
e−µr̃(i)r̃(j)

≥
Pr 
Xij !
Xij !
1≤i6=j≤n
1≤i6=j≤n


Y  µr̃(i)r̃(j) Xij
e−µr̃(i)r̃(j) +µr(i)r(j) ≥ 1
= Pr 
µr(i)r(j)
1≤i6=j≤n
s

Y
µr̃(i)r̃(j) Xij −µ
≤
Er
e r̃(i)r̃(j) +µr(i)r(j)
µr(i)r(j)
1≤i6=j≤n




X
2
1
p
p
= exp −
µr̃(i)r̃(j) − µr(i)r(j)  .
2
1≤i6=j≤n


By (19), we have obtain the upper bound exp −nβ 2 kr̃ − rk2 . The proof is complete by
taking maximum over r̃ ∈ Rm .

Acknowledgements
The author thanks Qiyang Han for suggesting the proof of Theorem 2.2. The research is
supported in part by NSF grant DMS-1712957.

References
[1] Francis J Anscombe. The transformation of poisson, binomial and negative-binomial
data. Biometrika, 35(3/4):246–254, 1948.
[2] Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: I.
the method of paired comparisons. Biometrika, 39(3/4):324–345, 1952.
[3] Mark Braverman and Elchanan Mossel. Noisy sorting without resampling. In Proceedings
of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, pages 268–276.
Society for Industrial and Applied Mathematics, 2008.
[4] Yuxin Chen, Changho Suh, and Andrea J Goldsmith. Information recovery from pairwise
measurements. IEEE Transactions on Information Theory, 62(10):5881–5905, 2016.
[5] Victor Chernozhukov, Denis Chetverikov, and Kengo Kato. Gaussian approximations
and multiplier bootstrap for maxima of sums of high-dimensional random vectors. The
Annals of Statistics, 41(6):2786–2819, 2013.

37

[6] Olivier Collier and Arnak S Dalalyan. Minimax rates in permutation estimation for
feature matching. The Journal of Machine Learning Research, 17(1):162–192, 2016.
[7] Chao Gao, Yu Lu, and Harrison H Zhou. Rate-optimal graphon estimation. The Annals
of Statistics, 43(6):2624–2652, 2015.
[8] JA Hartigan. Bounding the maximum of dependent random variables. arXiv preprint
arXiv:1312.1207, 2013.
[9] Peter D Hoff, Adrian E Raftery, and Mark S Handcock. Latent space approaches to
social network analysis. Journal of the american Statistical association, 97(460):1090–
1098, 2002.
[10] Johannes Kobler, Uwe Schöning, and Jacobo Torán. The graph isomorphism problem:
its structural complexity. Springer Science & Business Media, 2012.
[11] R Duncan Luce. Individual choice behavior: A theoretical analysis. Courier Corporation,
2005.
[12] Cheng Mao, Jonathan Weed, and Philippe Rigollet. Minimax rates and efficient algorithms for noisy sorting. arXiv preprint arXiv:1710.10388, 2017.
[13] Pascal Massart. Concentration inequalities and model selection, volume 1896. Springer,
2007.
[14] Sahand Negahban, Sewoong Oh, and Devavrat Shah. Iterative ranking from pair-wise
comparisons. In Advances in Neural Information Processing Systems, pages 2474–2482,
2012.
[15] Nihar Shah, Sivaraman Balakrishnan, Aditya Guntuboyina, and Martin Wainwright.
Stochastically transitive models for pairwise comparisons: Statistical and computational
issues. In International Conference on Machine Learning, pages 11–20, 2016.
[16] Nihar B Shah and Martin J Wainwright. Simple, robust and optimal ranking from
pairwise comparisons. arXiv preprint arXiv:1512.08949, 2015.
[17] Aad W Van Der Vaart and Jon A Wellner. Weak convergence. In Weak Convergence
and Empirical Processes, pages 16–28. Springer, 1996.
[18] Bin Yu. Assouad, fano, and le cam. Festschrift for Lucien Le Cam, 423:435, 1997.
[19] Mikhail Zaslavskiy, Francis Bach, and Jean-Philippe Vert. A path following algorithm
for the graph matching problem. IEEE Transactions on Pattern Analysis and Machine
Intelligence, 31(12):2227–2242, 2009.
[20] Anderson Y Zhang and Harrison H Zhou. Minimax rates of community detection in
stochastic block models. The Annals of Statistics, 44(5):2252–2280, 2016.
38

