1

Asymptotically optimal private estimation
under mean square loss

arXiv:1708.00059v1 [] 31 Jul 2017

Min Ye

Alexander Barg

Abstract
We consider the minimax estimation problem of a discrete distribution with support size k under
locally differential privacy constraints. A privatization scheme is applied to each raw sample independently, and we need to estimate the distribution of the raw samples from the privatized samples. A
positive number ǫ measures the privacy level of a privatization scheme.
In our previous work (arXiv:1702.00610), we proposed a family of new privatization schemes and
the corresponding estimator. We also proved that our scheme and estimator are order optimal in the
regime eǫ ! k under both ℓ22 and ℓ1 loss. In other words, for a large number of samples the worst-case
estimation loss of our scheme was shown to differ from the optimal value by at most a constant factor. In
this paper, we eliminate this gap by showing asymptotic optimality of the proposed scheme and estimator
under the ℓ22 (mean square) loss. More precisely, we show that for any k and ǫ, the ratio between the
worst-case estimation loss of our scheme and the optimal value approaches 1 as the number of samples
tends to infinity.

C ONTENTS
I

Introduction
I-A
Existing results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
I-B
Our contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
I-C
Organization of the paper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2
3
3
3

II

Problem formulation and existing results
II-A
Problem formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
II-B
Previous results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3
4
5

III

Overview of the results and the main ideas of the proof
III-A
Main result of the paper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
III-B
Main ideas of the proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6
6
6

IV

Sketch of the proof of Theorem III.1
IV-A
Output alphabet reduction . . . . . . . .
IV-B
Gaussian approximation of the posterior
IV-B1
Approximation . . . . . . . .
IV-B2
Large deviations . . . . . . .

V

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

7
9
9
9
10

Asymptotically tight lower bound: Proof of Theorem III.1
V-A
Output alphabet reduction . . . . . . . . . . . . . . .
V-B
Approximating gpu, y n q . . . . . . . . . . . . . . . .
V-C
Gaussian approximation to the posterior distribution
V-D
Case 1: δ ě δ0 . . . . . . . . . . . . . . . . . . . .
V-D1
Proof of (57) . . . . . . . . . . . . . . . .
V-D2
Proof of (58) . . . . . . . . . . . . . . . .
V-E
Case 2: δ ă δ0 . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

12
12
14
17
18
19
25
26

. .
pdf
. .
. .

. . . .
fU|Y n
. . . .
. . . .

The authors are with Dept. of ECE and ISR, University of Maryland, College Park, MD 20742. Emails: yeemmi@gmail.com
and abarg@umd.edu. Research supported by NSF grants CCF1422955 and CCF1618603.

2

VI

Outlook: Open questions
VI-A
Uniqueness of the optimal privatization scheme . . . . . . . . . . . . . . . . . . . . . . . . .
VI-B
Asymptotically tight lower bound for the ℓ1 loss . . . . . . . . . . . . . . . . . . . . . . . .

28
28
29

Appendix A: A calculus inequality

30

Appendix B: Proof of Proposition V.5

30

Appendix C: Proof of Proposition V.7

31

Appendix D: Proof of Proposition V.8

32

Appendix E: Proof of Step (b) in Eq. (72)

33

Appendix F: Proof of (74)

34

Appendix G: Bounding the integral in (76)

35

Appendix H: Proof of Proposition V.12

37

Appendix I: Proof of (80)

38

Appendix J: Relation to Local Asymptotic Normality and Fisher information matrix

39

References

41

I. I NTRODUCTION
This paper continues our work [13]. The context of the problem that we consider is related to a major
challenge in the statistical analysis of user data, namely, the conflict between learning accurate statistics
and protecting sensitive information about the individuals. As in [13], we rely on a particular formalization
of user privacy called differential privacy, introduced in [1], [2]. Generally speaking, differential privacy
requires that the adversary not be able to reliably infer an individual’s data from public statistics even
with access to all the other users’ data. The concept of differential privacy has been developed in two
different contexts: the global privacy context (for instance, when institutions release statistics related to
groups of people) [3], and the local privacy context when individuals disclose their personal data [4].
In this paper, we consider the minimax estimation problem of a discrete distribution with support size
k under locally differential privacy. This problem has been studied in the non-private setting [5], [6],
where we can learn the distribution from the raw samples. In the private setting, we need to estimate the
distribution of raw samples from the privatized samples which are generated independently from the raw
samples according to a conditional distribution Q (also called a privatization scheme). Given a privacy
parameter ǫ ą 0, we say that Q is ǫ-locally differentially private if the probabilities of the same output
conditional on different inputs differ by a factor of at most eǫ . Clearly, smaller ǫ means that it is more
difficult to infer the original data from the privatized samples, and thus leads to higher privacy. For a
given ǫ, our objective is to find the optimal privatization scheme with ǫ-privacy level to minimize the
expected estimation loss for the worst-case distribution. In this paper, we are mainly concerned with the
scenario where we have a large number of samples, which captures the modern trend toward “big data”
analytics.

3

A. Existing results
The following two privatization schemes are the most well-known in the literature: the k-ary Randomized Aggregatable Privacy-Preserving Ordinal Response (k-RAPPOR) scheme [7], [8], and the k-ary
Randomized Response (k-RR) scheme [9], [10]. The k-RAPPOR scheme is order optimal in the high
privacy regime where ǫ is very close to 0, and the k-RR scheme is order optimal in the low privacy regime
where eǫ « k [11]. Very recently, a family of privatization schemes and the corresponding estimators were
proposed independently by Wang et al. [12] and the present authors [13]. In [13], we further showed that
under both ℓ22 and ℓ1 loss, these privatization schemes and the corresponding estimators are order-optimal
in the medium to high privacy regimes when eǫ ! k.
Duchi et al. [14] gave an order-optimal lower bound on the minimax private estimation loss for the
high privacy regime where ǫ is very close to 0. In [13], we proved a stronger lower bound which is
order-optimal in the whole region eǫ ! k. This lower bound implies that the schemes and the estimators
proposed in [12], [13] are order optimal in this regime. Here order-optimal means that the ratio between
the true value and the lower bound is upper bounded by a constant (larger than 1) when n and k{eǫ both
become large enough.
B. Our contributions
In this paper, we focus on the ℓ22 (mean square) loss. We prove an asymptotically tight lower bound
on the minimax private estimation loss for all values of k and ǫ. In other words, for every k and every ǫ,
the ratio between the true value and our lower bound goes to 1 when n goes to infinity. This is a huge
improvement over the lower bounds in [13] and [14] for the following two reasons: First, although the
lower bounds in [13] and [14] are order-optimal, they differ from the true value by a factor of several
hundred. In practice, an improvement of several percentage points is already considered as a substantial
advance (see for instance, [11]). So these order-optimal bounds are far from satisfactory. Second, the
bounds in [13] and [14] only hold for certain regions of k and ǫ while the lower bound in this paper
holds for all values of k and ǫ.
Furthermore, as an immediate consequence of our lower bound, we show that the schemes and the
estimators proposed in [12], [13] are asymptotically optimal! In other words, the ratio between the lower
bound and the worst-case estimation loss of these schemes and estimators goes to 1 when n goes to
infinity.
C. Organization of the paper
In Section II, we formulate the problem and give a more detailed review of the existing results.
Section III is devoted to an overview of the main results of this paper and to illustrating the main ideas
behind the proof. Since the proof is very long and technical, we include a short Section IV, where
we explain the argument in formal terms, while skipping many details. The complete proof is given in
Section V which (with Appendices) takes the most of the length of the paper. In Section VI, we point
out two possible directions for future research.
II. P ROBLEM

FORMULATION AND EXISTING RESULTS

Notation: Let X “ t1, 2, . . . , ku be the source alphabet and let p “ pp
ř1 , p2 , . . . , pk q be a probability
distribution on X. Denote by ∆k “ tp P Rk : pi ě 0 for i “ 1, 2, . . . , k, ki“1 pi “ 1u the k-dimensional
probability simplex. Let X be a random variable (RV) that takes values on X according to p, so that
pi “ P pX “ iq. Denote by X n “ pX p1q , X p2q , . . . , X pnq q the vector formed of n independent copies of
the RV X.

4

A. Problem formulation
In the classical (non-private) distribution estimation problem, we are given direct access to i.i.d. samples
tX piq uni“1 drawn according to some unknown distribution p P ∆k . Our goal is to estimate p based on
the samples [6]. We define an estimator p̂ as a function p̂ : Xn Ñ Rk , and assess its quality in terms of
the worst-case risk (expected loss)
sup nE n ℓpp̂pX n q, pq,
pP∆k X „p

where ℓ is some loss function. The minimax risk is defined as the solution of the following saddlepoint
problem:
ℓ
:“ inf sup nE n ℓpp̂pX n q, pq.
rk,n
p̂ pP∆k X „p

In the private distribution estimation problem, we can no longer access the raw samples tX piq uni“1 .
Instead, we estimate the distribution p from the privatized samples tY piq uni“1 , obtained by applying
a privatization mechanism Q independently to each raw sample X piq . A privatization mechanism (also
called privatization scheme) Q : X Ñ Y is simply a conditional distribution QY |X . The privatized samples
Y piq take values in a set Y (the “output alphabet”) that does not have to be the same as X.
The quantities tY piq uni“1 are i.i.d. samples drawn according to the marginal distribution m given by
mpSq “

k
ÿ

i“1

QpS|iqpi

(1)

for any S P σpYq, where σpYq denotes an appropriate σ -algebra on Y. In accordance with this setting,
the estimator p̂ is a measurable function p̂ : Yn Ñ Rk . We assess the quality of the privatization scheme
Q and the corresponding estimator p̂ by the worst-case risk
ℓ
pQ, p̂q :“ sup
rk,n

E ℓpp̂pY n q, pq,

n
n
pP∆k Y „m

where mn is the n-fold product distribution and m is given by (1). Define the minimax risk of the
privatization scheme Q as
ℓ
ℓ
pQ, p̂q.
(2)
pQq :“ inf rk,n
rk,n
p̂

Definition II.1. For a given ǫ ą 0, a privatization mechanism Q : X Ñ Y is said to be ǫ-locally
differentially private if
QpY P S|X “ xq
ď eǫ for all x, x1 P X.
(3)
sup
1q
Q
pY
P
S|X
“
x
SPσpYq
Denote by Dǫ the set of all ǫ-locally differentially private mechanisms. Given a privacy level ǫ, we seek
to find the optimal Q P Dǫ with the smallest possible minimax risk among all the ǫ-locally differentially
private mechanisms. Accordingly, define the ǫ-private minimax risk as
ℓ
ℓ
pQq.
:“ inf rk,n
rǫ,k,n
QPDǫ

(4)

As already mentioned, we will limit ourselves to ℓ “ ℓ22 .
Main Problem: Suppose that the cardinality k of the source alphabet is known to the estimator. We
ℓ22
as n Ñ 8 and to construct an asymptotically
would like to find the asymptotic growth rate of rǫ,k,n
optimal privatization mechanism and a corresponding estimator of p from the privatized samples.
It is this problem that we address—and resolve—in this paper. Specifically, we prove a lower bound
ℓ22
, which implies that the mechanism and the corresponding estimator proposed in [13] are
on rǫ,k,n
asymptotically optimal for the private estimation problem.

5

B. Previous results
In this section we briefly review known results that are relevant to our problem. In Sect. I-A
mentioned several papers that have considered it, viz., [7]–[12], [14]. In this section we discuss only
results of [13] since they subsume the (earlier) results of the mentioned references, and since they
formulated in the form convenient for our presentation.
Let Dǫ,F be the set of ǫ-locally differentially private schemes with finite output alphabet. Let
"
*
Qpy|xq
ǫ
Dǫ,E “ Q P Dǫ,F :
P t1, e u for all x P X and all y P Y .
minx1 PX Qpy|x1 q

we
the
are

(5)

In [13, Theorem IV.5], we have shown that

ℓ2

ℓ2

2
2
pQq.
“ inf rk,n
rǫ,k,n

(6)

QPDǫ,E

As a result, below we limit ourselves to schemes Q P Dǫ,E in this paper. For such schemes, since the output
ř
alphabet is finite, we can write the marginal distribution m in (1) as a vector m “ p kj“1 pj Qpy|jq, y P Yq.
We will also use the shorthand notation m “ pQ to denote this vector.
In [13], we introduced a family of privatization schemes which are parameterized
ř by the integer
d P t1, 2,`. .˘. , k ´ 1u. Given k and d, let the output alphabet be Yk,d “ ty P t0, 1uk : ki“1 yi “ du, so
|Yk,d | “ kd .
Definition II.2 ([13]). Consider the following privatization scheme:
eǫ yi ` p1 ´ yi q
Qk,ǫ,dpy|iq “ `k´1˘
`k´1˘
ǫ
d´1 e `
d

(7)

for all y P Yk,d and all i P X. The corresponding empirical estimator of p under Qk,ǫ,d is defined as
follows:
´ pk ´ 1qeǫ ` pk´1qpk´dq ¯ T
pd ´ 1qeǫ ` k ´ d
i
d
pˆi “
´
,
(8)
pk ´ dqpeǫ ´ 1q
n
pk ´ dqpeǫ ´ 1q
ř
pjq
where Ti “ nj“1 Yi is the number of privatized samples whose i-th coordinate is 1.

It is easy to verify that Qk,ǫ,d is ǫ-locally differentially private. The estimation loss under Qk,ǫ,d and
the empirical estimator is calculated in the following proposition.
Proposition II.3. [13, Prop. III.1] Suppose that the privatization scheme is Qk,ǫ,d and the empirical
estimator is given by (8). Let m “ pQk,ǫ,d. For all ǫ, n and k, we have that
k

E ℓ22 pp̂pY n q, pq
Y n „mn

1 ´ pdpk ´ 2q ` 1qe2ǫ
2pk ´ 2qeǫ pk ´ 2qpk ´ dq ` 1 ÿ 2 ¯
“
pi .
`
`
´
n pk ´ dqpeǫ ´ 1q2
peǫ ´ 1q2
dpeǫ ´ 1q2
i“1

(9)

ř
The sum i p2i is maximized for pU “ p1{k, 1{k, . . . , 1{kq, so the worst-case distribution is the uniform
one. Substituting pU in (9), we obtain
ℓ2

2
pQk,ǫ,d , p̂q “
rk,n

Given k and ǫ, define

E
n

ℓ2 pp̂pY n q, pU q “
n 2

Y „mU

pk ´ 1q2 pdeǫ ` k ´ dq2
.
nkpeǫ ´ 1q2
dpk ´ dq

pdeǫ ` k ´ dq2
,
dpk ´ dq
1ďdďk´1

d˚ “ d˚ pk, ǫq :“ argmin

(10)

(11)

where the ties are resolved arbitrarily. We obtain
ℓ2

2
rk,n
pQk,ǫ,d˚ , p̂q “

min

1ďdďk´1

ℓ2

2
rk,n
pQk,ǫ,d , p̂q.

(12)

6

By differentiation in (11) we find that d˚ can only take two possible values given in the next proposition.
Proposition II.4.
d˚ “ rk{peǫ ` 1qs or tk{peǫ ` 1qu.

Therefore, when k{peǫ ` 1q ď 1, d˚ “ 1; when k{peǫ ` 1q ą 1, a simple comparison can determine
the value of d2 ˚ .
ℓ22
ℓ2
. In [13], we also proved an order optimal
pQk,ǫ,d˚ , p̂q serves as an upper bound on rǫ,k,n
Clearly, rk,n
ℓ2

2
in the regime eǫ ! k and n large enough. Combining the upper and lower bounds,
lower bound on rǫ,k,n
we obtain the following theorem.

Theorem II.5. [13] Let eǫ ! k. For n large enough,
¯
´
keǫ
ℓ22
.
“Θ
rǫ,k,n
npeǫ ´ 1q2
III. OVERVIEW

OF THE RESULTS AND THE MAIN IDEAS OF THE PROOF

A. Main result of the paper
Let
M pk, ǫq :“
ℓ2

pk ´ 1q2 pd˚ eǫ ` k ´ d˚ q2
kpeǫ ´ 1q2
d˚ pk ´ d˚ q

(13)

2
pQk,ǫ,d˚ , p̂q “ n1 M pk, ǫq.
where d˚ is defined in (11). Note that rk,n

Theorem III.1. For every k and ǫ, there are a positive constant Cpk, ǫq ą 0 and an integer N pk, ǫq
such that when n ě N pk, ǫq,
Cpk, ǫq
1
ℓ22
ě M pk, ǫq ´ 14{13 .
rǫ,k,n
(14)
n
n
This result together with (12) and (10) implies that
ℓ2

ℓ2

2
2
pQk,ǫ,d˚ , p̂q ´ Opn´14{13 q.
“ rk,n
rǫ,k,n

(15)

ℓ2

2
. It also gives an upper bound on
This theorem completely determines the dominant term of rǫ,k,n
the order of the remainder term. Moreover, this theorem also implies that our scheme Qk,ǫ,d˚ and the
empirical estimator p̂ defined in (8), both proposed in [13], are asymptotically optimal for the Main
Problem.

B. Main ideas of the proof
ℓ2

2
.
In this subsection we illustrate the main ideas that lead to determining the dominant term of rǫ,k,n

ℓ2

ℓ2

ℓ2

2
2
2
pQk,ǫ,d˚ , p̂q
ď rk,n
“ M pk, ǫq. Clearly, rǫ,k,n
In view of (10)–(12) we need to show that limnÑ8 nrǫ,k,n

ℓ2

2
ď M pk, ǫq. Therefore, we only need to show the lower
for all n ě 1, implying that lim supnÑ8 nrǫ,k,n
bound
ℓ22
ℓ22
pQq ě M pk, ǫq.
(16)
“ lim inf n inf rk,n
lim inf nrǫ,k,n

nÑ8

ℓ22

nÑ8

QPDǫ,E

Lower bounds on rǫ,k,n can be derived using Assouad’s method; see [13], [14]. More specifically,
we can choose a finite subset of the probability simplex and assume that the probability distributions
only come from this finite set, thereby reducing the original estimation problem to a hypothesis testing
ℓ22
; see Theorem II.5. Deriving
problem. This approach enables us to derive the correct scaling order of rǫ,k,n
the correct constant in front of the main term is more problematic because Assouad’s method relies on
reducing a continuous domain (the probability simplex) to a finite set.

7

In this paper, we use a different approach to obtain an asymptotically tight lower bound in (16). Since
the worst-case estimation loss is always lower bounded by the average estimation loss, the minimax
ℓ22
can be bounded below by the Bayes estimation loss. More specifically, we assume that the
risk rǫ,k,n
probability distributions are chosen uniformly from a small neighborhood of the uniform distribution pU .
Surprisingly, the lower bound on the Bayes estimation loss turns out to be asymptotically the same as
the worst-case estimation loss of our scheme and estimator. In other words, the ratio between these two
quantities goes to 1 when n goes to infinity.
In order to obtain the lower bound on the Bayes estimation loss, we refine a classical method in
asymptotic statistics, namely, local asymptotic normality (LAN) of the posterior distribution [15]–[17].
We briefly describe the implications of LAN for our problem and explain why the classical approach
does not directly apply to our problem. Our objective is to estimate p from the privatized samples Y n .
In the Bayesian setup, we assume that p is drawn uniformly from P, a very small neighborhood of pU .
Let P “ rP1 , P2 , . . . , Pk s denote the random vector that corresponds to p. Applying the LAN method
of [15]–[17], one can show that when the radius of P is of order n´1{2 , with large probability the
conditional distribution of P given Y n approaches a jointly Gaussian distribution as n goes to infinity,
and the covariance matrix Σ “ Σpn, Qq of this Gaussian distribution is completely determined by n and
the privatization scheme Q. Note that Σ is independent of the value of Y n . We further note that the
top-left pk ´ 1q ˆ pk ´ 1q submatrix of Σ is the inverse of the Fisher information matrix computed with
respect to the parameters p1 , p2 , . . . , pk´1 (a detailed discussion of this issue appears in Appendix J).
ℓ22
pQq. At the same time, for all
It is clear that the trace of Σ serves an asymptotic lower bound on rk,n
Q P Dǫ,E , we can show that
ℓ22
pQk,ǫ,d˚ , p̂q,
trpΣq ě rk,n
where Qk,ǫ,d˚ and p̂ are given respectively in (7) and (8). Therefore,
ℓ2

2
pQq ě M pk, ǫq for all Q P Dǫ,E .
lim inf nrk,n

nÑ8

This inequality gives a strong intuition of why (16) should hold. However, it does not imply (16) because
a pointwise asymptotic lower bound does not imply a uniform asymptotic lower bound. For this reason,
we cannot directly use the classical approach and must develop more delicate arguments that prove (16)
and (15). Another feature of our approach worth mentioning is that, unlike the methods in [15]–[17], our
proof is completely elementary.
IV. S KETCH

OF THE PROOF OF

T HEOREM III.1

In the previous section we explained a general approach to the proof of (16). The formal proof that
we will present is rather long and technical. For this reason, in this section we outline a “road map” to
help the readers to follow our arguments.
For reader’s convenience we made a short table of our main notation; see Table I. Most, although not
all, definitions from this table are also given in the main text.
The following conventions about our notation are made with reference to Table I. The vector u is
chosen to be pk ´ 1q-dimensional (u is a function of p, but we omit the dependence for notational
řk´1
simplicity). At the same time, using the normalization condition, we define uk “ uk puq :“ ´ j“1
uj .
Clearly, uk “ pk ´ 1{k. The same convention is used for the random vector U and for the vector ũ both
of which appear later in the paper.
The following obvious relations will be repeatedly used in the proof:
L
ÿ

i“1

qi “

L
ÿ

i“1

qij “ 1 for all j P rks,

k
ÿ

j“1

uj “ 0,

L
ÿ

i“1

ti py n q “ n.

(17)

8

TABLE I: Main notation

X “ t1, 2, . . . , ku
p “ pp1 , . . . , pk q
Dǫ,E
u “ pu1 , . . . , uk´1q
uj :“ pj ´ k1 , j “ 1, . . . , k ´ 1
řk´1
uj
uk “ uk puq :“ ´ j“1
L1
Y
L
tA1 , A2 , . . . , AL u
Q “ pQpi|jqqiPrL1 s,jPrks
qij , i P rLs, j P rks
qi :“

1
k

ř

j

qij , i P rLs

pti py n q, i “ 1, . . . , Lq
v “ pv1 , . . . , vL q
vi :“ ti py n q ´ nqi , i P rLs
w “ wpv, Qq P Rk´1
U “ pU1 , U2 , . . . , Uk´1 q
řk´1
Uj
Uk “ Uk pUq :“ ´ j“1
V “ pV1 , . . . , VL q
Bpαq

source alphabet
distribution on X, where pj “ P pX “ jq
set of privatization mechanisms of the form (5)
difference between the first k ´ 1 coordinates of p
and the uniform distribution
by definition uk “ pk ´ 1{k
cardinality of the original output alphabet
original output alphabet. WLOG we assume Y “
t1, 2, . . . , L1 u
the number of equivalence classes tA1 , A2 , . . . , AL u in Y
equivalent output alphabet after symbol merging
privatization mechanism (conditional distribution)
conditional probability of observing output symbols in Ai
if the raw sample is j
by definition qi “ P pY P Ai q when p is the uniform
distribution over X
composition of the observed vector, ti py n q is the number
of occurrences of symbol Ai in y n
ř
ik qvi
, m “ 1, . . . , k ´ 1
vector with coordinates Li“1 pqim ´q
qi
random vector corresponding to u “ pu1 , . . . , uk´1q
random variable corresponding to uk
random vector corresponding to v “ pv1 , . . . , vL q
ellipsoid (18) of “radius” α;
B1 :“ Bpn´5{13 q, B2 :“ Bpn´5{13 ´ 3n´6{13 {δ0 q

Below we study distributions supported on ellipsoids, and we use the following generic notation: Given
α ą 0, let us define an ellipsoid
k´1
)
´ k´1
!
ÿ
ÿ ¯2
u2i `
ui ă α2 .
Bpαq “ u P Rk´1 :
i“1

(18)

i“1

For future use we note that u P Bpαq if and only uT pI ` Jqu ă α2 , where I is the identity matrix and
J is the all-ones matrix.
On account of (6), to prove (14) it suffices to show that for every k and ǫ, there are a positive constant
Cpk, ǫq ą 0 and an integer N pk, ǫq such that when n ě N pk, ǫq,
ℓ2

2
pQq ě
inf rk,n

QPDǫ,E

1
Cpk, ǫq
M pk, ǫq ´ 14{13
n
n

(19)

In the rest of this paper we will prove (19). It is important to note that, because of the infimum on the
distribution Q, the constants Cpk, ǫq and N pk, ǫq should not depend on it. It is for this reason that the
classical LAN approach does not directly apply. Below we provide more details about this.

9

A. Output alphabet reduction
ℓ2

2
below, and we assume that the
As mentioned above, we use Bayes estimation loss to bound rǫ,k,n
probability distributions are chosen uniformly from a small neighborhood of the uniform distribution
pU . Recalling the definition of the vector u and uk in Table I, we note that estimating p is equivalent
to estimating pu1 , . . . , uk q. Let U be the random vector that corresponds to u. We assume that U is
uniformly distributed over the ellipsoid
´ 1 ¯
(20)
B1 “ B 5{13 .
n
Suppose that the size of the original output alphabet Y is some integer L1 , which is independent of k and
ǫ, and can take an arbitrarily large value. Recall that our objective is (19). If L1 enters the estimates of the
estimation loss, then we can not bound it by a function of k and ǫ, which is something we would like to
avoid. This can be done using the following simple observation. Without loss of generality, we assume that
Y “ t1, 2, . . . , L1 u. Since Q P Dǫ,E (see (5)), for every i P t1, . . . , L1 u, the vector pQpi|jq, j “ 1, . . . , kq
is proportional to one of the vectors in the set t1, eǫ uk . It is easy to see that we can merge into one symbol
all the output symbols that correspond to proportional vectors, thereby reducing the size of the output
alphabet without affecting the Bayes estimation loss. Suppose that, upon merging all such symbols, the
size of the output alphabet becomes L. Clearly, L ď 2k , and we will henceforth assume that the output
alphabet is tA1 , A2 , . . . , AL u and let qij denote the conditional probability of observing Ai if the raw
sample is j P rks.

B. Gaussian approximation of the posterior pdf fU |Y n

ř
1) Approximation: For i “ 1, 2, . . . , L, let qi :“ k1 kj“1 qij , and let ti “ ti py n q be the number of
times that symbol Ai appears in y n . Define vi :“ vi py n q “ ti py n q ´ nqi for i “ 1, . . . , L. Then for
u P B1 , we have
fU|Y n pu|y n q 9

k
L
ÿ
ź
uj qij qti
pqi `
j“1

i“1

k
´
´
ÿ
uj qij ¯¯¯
.
pnqi ` vi q log 1 `
9 exp
qi
j“1
i“1

´

L
ÿ

(21)

Since our objective is to estimate u1 , u2 , . . . , uk , we view all the factors that do not contain u as constants
in the formula above. Let us introduce a notation for the exponent of the right-hand side:
n

gpu, y q “

L ´
ÿ

i“1

k
´
ÿ
uj qij ¯¯
pnqi ` vi q log 1 `
.
qi
j“1

Let V be a random vector corresponding to the vector v “ pv1 , . . . , vL q. Since P pY “ Ai q “
the expectation of Vi equals
E Vi “ n

k
ÿ

j“1

pj qij ´

k
k
ÿ
n ÿ
nuj qij .
qij “
k j“1
j“1

(22)
řk

j“1 pj qij ,

Assuming that u P B1 , we therefore conclude that EVi “ Opn8{13 q. By definition, VarpVi q “ Varpti pY n qq
for all i. According to the Central Limit Theorem, when n is large, VarpVi q “ Opnq. As a consequence,
when n is large, with large probability, Vi “ Opn8{13 q. This fact together with the relation
k
k
k
´
ÿ
1 ´ ÿ uj qij ¯2
uj qij ¯ ÿ uj qij
«
´
log 1 `
qi
qi
2 j“1 qi
j“1
j“1

10

gives us the following approximation of gpu, y n q:
gpu, y n q «

L
ÿ

i“1

vi

k
L
L
k
´ÿ
ÿ
ÿ
1
uj qij
1ÿ
vi2
uj qij ¯2
“ ´ hv puq `
´
nqi
,
qi
2 i“1
qi
2
2nqi
j“1
i“1
j“1

where for v “ pv1 , v2 , . . . , vL q, the function hv : Rk´1 Ñ R is defined as
hv puq “

k
L
ÿ
vi ¯ 2
n´ ÿ
uj qij ´
for all u P Rk´1 .
q
n
i
j“1
i“1

(23)

Thus, for large n the density function of the posterior distribution is approximately given by
1
fU|Y n pu|y n q 9 expp´ hv puqq,
2

and hv puq is a quadratic function of u. Had u been taking values in the entire space Rk´1, we would
be able to conclude that the posterior distribution of U given Y n is approximately Gaussian. Supposing
that this is the case, define the matrix
L
¯T ´
¯
ÿ
n´
pqi,1 ´ qik q, . . . , pqik´1 ´ qik q
pqi,1 ´ qik q, . . . , pqi,k´1 ´ qik q ,
Φ “ Φpn, Qq :“
q
i“1 i
and the vector w P Rk´1

L
L
L
´ÿ
ÿ
pqi,1 ´ qik qvi ÿ pqi,2 ´ qik qvi
pqik´1 ´ qik qvi ¯T
w “ wpv, Qq :“
.
,
,...,
qi
qi
qi
i“1
i“1
i“1

Then the covariance and the vector of means of this Gaussian distribution are given by Φ´1 and Φ´1 w.
Note that Φ is independent of the value of Y n . At the same time, since w depends on the value of v,
and v is a function of y n , the mean vector Φ´1 w does vary with the realization of Y n .
2) Large deviations: The above argument does not directly apply because u is limited to the ellipsoid
B1 . In order to claim that the posterior distribution can be indeed approximated as Gaussian, we need to
show that the entire mass is concentrated in B1 , i.e., that under the Gaussian distribution N pΦ´1 w, Φ´1 q
the probability P pU R B1 q « 0.
2
To build intuition, let us consider the one-dimensional case. Let hpxq “ px´µq
be the (absolute value
2
2σ
of the) exponent of the Gaussian pdf. By the Chernoff bound, for X „ N pµ, σ 2 q we have
P p|X ´ µ| ě tq ď 2 expp´

t2
q.
2σ 2

(24)

This bound immediately implies that for any x̃ P R
a
a
P p hpXq ´ hpx̃q ě tq ď 2 expp´t2 q.

The situation is similar in the multi-dimensional case. Indeed, one can show that for U „ N pΦ´1 w, Φ´1 q
we have the following inequality: for any ũ P Rk´1 and any α ą 0
a
a
P p hv pUq ´ hv pũq ą nα q ď expp´nα q

for a large enough n. Now our task is to show that for almost all y n P Yn , we can find a ũ “ ũpy n q
such that
a
a
B1c Ď tu P Rk´1 : hv puq ´ hv pũq ą nα u
(25)
for some α ą 0, or more precisely, that (25) holds for all y n in a subset E2 Ď Yn such that P pY n P
E2 q « 1.

11

Toward that end, we define another ellipsoid
´ 1
3{δ0 ¯
´
(26)
n5{13 n6{13
(see (18)), where δ0 is a constant which will be specified later. Observe that the ratio between the radii
of B2 and B1 approaches 1 when n is large. Thus, P pu P B2 q « P pu P B1 q, and since P pu P B1 q “ 1,
we have P pu P B2 q « 1. Conditional on the event U “ ũ P B2 , we have1
B2 “ B

E

L
k
L
´ÿ
´
¯
n´ ÿ
Vi ¯2 ¯ 1 ÿ 1
ũj qij ´
“
Var ti pY n q “ Op1q,
q
n
n i“1 qi
i“1 i j“1

so for large n
g
fL
k
fÿ n ´ ÿ
Vi pY n q ¯2
e
ũj qij ´
ă n1{26
q
n
i
i“1
j“1

with large probability. We can phrase this as follows: conditional on U P B2 , for almost all y n P Yn we
can find ũ “ ũpy n q P B2 such that
g
fL ´ k
fÿ n ÿ
vi py n q ¯2
e
ũj qij ´
ă n1{26 .
q
n
i“1 i j“1

Since P pU P B2 q « 1, this is the same as saying that for almost all y n P Yn , we can find ũ “ ũpy n q P B2
such that
g
fL
k
a
fÿ n ´ ÿ
vi py n q ¯2
e
ũj qij ´
ă n1{26 .
(27)
hv pũq “
q
n
i
j“1
i“1
By the triangle inequality, for any ũ P B2 and any u P B1c , we have
g
f k
fÿ
e pu ´ ũ q2 ą 3{δ0 .
i
i
n6{13
i“1

Our next goal is to use this inequality to bound below the quantity
us introduce the quantity

(28)

` řL

1 řk
i“1 qi p j“1 puj

k
L
¯2 ¯1{2
´ÿ
1´ÿ
u
q
δ “ δpQq :“
min
j
ij
ř
uPRk´1 : ki“1 u2i “1 i“1 qi j“1

2
´ ũj qqij

˘1{2

. Let

(29)

Intuitively, δ measures how well Q can distinguish between different u’s. Our argument proceeds differently depending on whether δ ě δ0 or not.
If δ is small, then there is a pair u and u1 that are well-separated from each other by the ℓ2 distance,
but the posterior probabilities of u and u1 given y n are close to each other. Thus, the case δ ă δ0 for
a sufficiently small constant δ0 can be handled by a straightforward application of the Le Cam method,
and the main obstacle is represented by the opposite case.
1

Recall the convention that uk “ ´

řk´1
i“1

ui and ũk “ ´

řk´1
i“1

ũi .

12

For δ ě δ0 , according to (28) and (29), for any ũ P B2 and any u P B1c ,
g
g
fL
fL ´ k
k
¯
¯2
ÿ
ÿ
fÿ 1 ´ ÿ
f
2
n
1{2 e
e
ũj qij ´ uj qij “ n
pũj ´ uj qqij
q
q
i“1 i j“1
i“1 i j“1
g
f k
fÿ
1{2 e
pui ´ ũi q2
ěn δ

(30)

i“1

3{δ0
n6{13
1{26
“ 3n
.

ě n1{2 δ0

Combining (27) and (30) and using the triangle inequality, we conclude that for almost all y n P Yn and
any u P B1c
g
fL
k
a
fÿ n ´ ÿ
vi py n q ¯2
hv puq “ e
uj qij ´
ě 2n1{26 .
(31)
q
n
i
i“1
j“1

Now combining (31) with (27), we deduce that for almost all y n P Yn , we can find a ũ “ ũpy n q such
that
a
a
B1c Ď tu P Rk´1 : hv puq ´ hv pũq ą n1{26 u.
Once the details are filled in, this will establish (25), and thus we will be able to conclude that for almost
all y n P Yn , the posterior distribution of U given Y n “ y n is very close to N pΦ´1 w, Φ´1 q.
It is a standard fact that underřℓ22 loss, the optimal Bayes estimator for u is EpU|Y n q. Therefore, the
optimal Bayes estimation loss is ki“1 EpUi ´ EpUi |Y n qq2 , and this is equal to the sum of the variances of
the posterior distributions ofřUi given Y n . We just showed that the posterior distribution is very close to
N pΦ´1 w, Φ´1 q. Therefore, ki“1 EpUi ´ EpUi |Y n qq2 can be approximated as trpΦ´1 q ` 1T Φ´1 1, where
1 is the column vector of k ´ 1 ones. More precisely, we can show that
ˇ `
˘ˇ
ℓ22
pQq ě trpΦ´1 q ` 1T Φ´1 1 ´ ˇO n´14{13 ˇ.
rk,n

Then we will prove that for all Q P Dǫ,E ,

trpΦ´1 q ` 1T Φ´1 1 ě

1
M pk, ǫq
n

ℓ2

2
pQk,ǫ,d˚ , p̂q “ n1 M pk, ǫq, this will prove Theorem III.1.
and since by (11), (12), rk,n

V. A SYMPTOTICALLY

TIGHT LOWER BOUND :

P ROOF

OF

T HEOREM III.1

In this section we develop the plan of attack outlined in Section IV. Since the proof is rather long, we
divide it into several steps, isolating each of them in its own subsection.
A. Output alphabet reduction
Here we fill in the details left out in Sec. IV-A. Given Q P Dǫ,E , assume without loss of generality
that the output alphabet is Y “ t1, 2, . . . , L1 u for some integer L1 . Define an equivalence relation “”” on
Y as follows: for i1 , i2 P t1, 2, . . . , L1 u, we say that i1 ” i2 if
řk

Qpi1 |jq

j 1 “1 Qpi1

|j 1 q

“ řk

Qpi2 |jq

j 1 “1 Qpi2 |j

1q

for all j P rks.

(32)

In other words, we say that i1 ” i2 if the vectors pQpi1 |1q, Qpi1 |2q, . . . , Qpi1 |kqq and pQpi2 |1q, Qpi2 |2q,
. . . , Qpi2 |kqq are proportional to each other. It is easy to verify that ” is indeed an equivalence relation

13

L
and therefore it induces a partition of Y into L disjoint equivalence classes tAi uL
i“1 , so Y “ Yi“1 Ai . By
definition of Dǫ,E , for any i P Y, the vector pQpi|1q, Qpi|2q, . . . , Qpi|kqq is proportional to one of the
vectors in t1, eǫ uk , which implies that L ď 2k .
Next we will show that for the purposes of this proof, the original output alphabet Y can be replaced
with the alphabet tA1 , . . . , AL u with only minor notational changes. We briefly discuss them below, with
the overall goal of writing out the pdf fU |Y n as in (21)-(22).
For i P t1, 2, . . . , L1 u and y n P Yn , let t1i py n q be the number of times that symbol i appears in y n , and
let
k
1 ÿ
qi1 “
Qpi|jq.
(33)
k j“1

For i P t1, 2, . . . , Lu and j P t1, 2, . . . , ku, define
ÿ
t1a py n q,
ti py n q “
aPAi

qij “ QpAi |jq “

By definition of the equivalence relation (32), we have

qi “
ÿ

aPAi

ÿ

qa1 ,

aPAi

Qpa|jq.

Qpa|jq
qij
“
for all a P Ai and j P rks.
1
qa
qi

(34)

(35)

For i P t1, 2, . . . , L1 u and y n P Yn , let

v1 py n q “ pv11 py n q, v21 py n q, . . . , vL1 1 py n qq “ pt11 py n q ´ nq11 , t12 py n q ´ nq21 , . . . , t1L1 py n q ´ nqL1 1 q.
řL1 1 n
ř L1
ř 1 1 n
n
n
1
Since L
i“1 vi py q “ 0 for every y P Y . We also define the
i“1 nqi “ n, we have
i“1 ti py q “
random vector
V 1 “ pV11 , V21 , . . . , VL1 1 q :“ pt11 pY n q ´ nq11 , t12 pY n q ´ nq21 , . . . , t1L1 pY n q ´ nqL1 1 q.

For i P rLs and y n P Yn , let

vpy n q “ pv1 py n q, v2 py n q, . . . , vL py n qq “ pt1 py n q ´ nq1, t2 py n q ´ nq2, . . . , tL py n q ´ nqL q.
ř
n
n
n
Similarly, L
i“1 vi py q “ 0 for every y P Y . Moreover, by definition,
ÿ
va1 py n q for all y n P Yn .
vi py n q “

(36)

aPAi

We also define the random vector

V “ pV1 , V2 , . . . , VL q “ pt1 pY n q ´ nq1 , t2 pY n q ´ nq2 , . . . , tL pY n q ´ nqL q.

For the simplicity of notation, from now on we will write v1 py n q and vpy n q as v1 and v, respectively.
Similarly, we abbreviate vi1 py n q and vi py n q as vi1 and vi , respectively. In Proposition V.1 below, we will
show that in order to prove the lower bound in Theorem III.1, we only need the quantities qi , vi , qij , i P
rLs, j P rks. Therefore abusing notation, we will write Y as tA1 , . . . , AL u and remove L1 and all the
quantities associated with it from consideration in most parts of this proof.
Next let us switch our attention to the pdf fU |Y n . Given p “ pp1 , . . . , pk q P ∆k , we define a pk ´
1q-dimensional vector u “ pu1 , u2 , . . . , uk´1 q “ pp1 ´ 1{k, p2 ´ 1{k,ř
. . . , pk´1 ´ 1{kq and let U “
k´1
ui . As a result, estimating
pU1 , . . . , Uk´1 q be the corresponding random vector. Clearly, pk “ 1{k ´ i“1
řk´1
p is equivalent to estimating pu1 , u2 , . . . , uk´1 , ´ i“1 ui q, so from now on we will focus on estimating
řk´1
ui and define the corresponding random variable
the latter. Given u P Rk´1 , define uk puq “ ´ i“1
řk´1
Uk pUq “ ´ i“1 Ui . Below we write these quantities as uk and Uk respectively for simplicity of notation.

14

We only consider distributions of U supported on a small ellipsoid centered at p k1 , k1 , . . . , k1 q. We use
ℓ22
pQq. More specifically, we assume
Bayes estimation loss to bound below the minimax estimation loss rk,n
1
q.
that the random vector U is uniformly distributed over the ellipsoid B1 “ Bp n5{13
We have the following proposition.
Proposition V.1. Assume that U is distributed over the ellipsoid B1 and let fU,Y n be the density of the
joint distribution. For u P B1 we have fU,Y n pu, y n q “ Cv1 exppgpu, y n qq, where
gpu, y n q “

and Cv1 “

1
VolpB1 q

ś L1

nqa1 `va1

1
i“1 pqi q

L ´
ÿ

i“1

k
´
ÿ
uj qij ¯¯
pnqi ` vi q log 1 `
,
q
i
j“1

(37)

.

Proof. We can write the joint distribution density function of the random vectors U and Y n as follows:
# ś 1
ř
1
n
L
1
pqi1 ` kj“1 uj Qpi|jqqti py q if u P B1
n
i“1
C
0
fU,Y n pu, y q “
,
0
if u R B1
where C0 is the volume of B1 . For u P B1 , we have
1

1

k
L
L
ÿ
uj Qpi|jq ¯nqa1 `va1
1 ź 1 nqa1 `va1 ź ´
1`
pqi q
fU,Y n pu, y q “
C0 i“1
qi1
j“1
i“1
n

1

“ Cv1

k
!
´
ÿ
uj Qpi|jq ¯)
exp pnqa1 ` va1 q log 1 `
qi1
j“1
i“1

L
ź

“ C exp
v1

“ Cv1 exp
“ Cv1 exp
ś L1

nqa1 `va1

where Cv1 “ C10 i“1 pqi1 q
follows from (35) and (36).

L1 ´
´ÿ
i“1

pnqa1

L ÿ ´
´ÿ
i“1 aPAi

L ´
´ÿ
i“1

`

va1 q log

k
´
ÿ
uj Qpi|jq ¯¯¯
1`
qi1
j“1

k
´
ÿ
uj Qpa|jq ¯¯¯
pnqa1 ` va1 q log 1 `
qa1
j“1

k
´
ÿ
uj qij ¯¯¯
,
pnqi ` vi q log 1 `
qi
j“1

is a constant that depends on v1 but not on u, and the last equality

B. Approximating gpu, y n q

As already said, we will assume that the output alphabet of Q has the form tA1 , A2 , . . . , AL u and will
use the auxiliary quantities (the composition, etc.) associated with it according to their definitions in (34)
and (36). Let
k
L
L
k
´ÿ
ÿ
ÿ
uj qij
uj qij ¯2
1ÿ
vi
g2 pu, y n q :“
.
(38)
´
nqi
qi
2 i“1
qi
j“1
i“1
j“1

Further, let E1 Ď Yn be defined as follows:

L
)
!
ÿ
|vi | ă 2kn8{13 .
E1 “ y n :
i“1

15

We will show that when n is large, the difference between gpu, y n q and g2 pu, y n q is small for all u P B1
and y n P E1 .

Proposition V.2. Let gpu, y n q be as defined in (37). Then there is an integer N pk, ǫq such that for every
y n P E1 , u P B1 and n ą N pk, ǫq,
|gpu, y n q ´ g2 pu, y n q| ă

2k3
.
n2{13

(39)

Consequently, for all such y n , u and n,
4k3
exppg2 pu, y n qq.
n2{13
Proof. 1. We begin with approximating gpu, y n q as follows:
| exppgpu, y n qq ´ exppg2 pu, y n qq| ď

(40)

k
k
´ÿ
uj qij
1 ´ ÿ uj qij ¯2 ¯
.
pnqi ` vi q
g1 pu, y q “
´
qi
2 j“1 qi
i“1
j“1
L
ÿ

n

ř
1
for all j P t1, 2, . . . , ku (see (18)), and so | kj“1 uj qij | ă
For u P B1 , we have |uj | ă n5{13
Using this inequality together with the definition of qi (see Table I) we obtain
k
ˇÿ
uj qij ˇˇ
k
ˇ
ˇ
ˇ ă 5{13 ,
qi
n
j“1

1
n5{13

řk

j“1 qij .

i “ 1, 2, . . . , L.

(41)

Given k, ǫ, there is an integer N pk, ǫq such that for all n ą N pk, ǫq we can bound the difference of
gpu, y n q and g1 pu, y n q as follows: for all u P B1 and y n P Yn ,
|gpu, y n q ´ g1 pu, y n q| ď

k
L ´
k
k
ˇ
´
ÿ
ÿ
uj qij ¯ ´ ÿ uj qij
1 ´ ÿ uj qij ¯2 ¯ˇˇ¯
ˇ
pnqi ` vi qˇ log 1 `
´
´
ˇ
qi
qi
2 j“1 qi
j“1
i“1
j“1
k
ˇÿ
uj qij ˇˇ3
ˇ
pnqi ` vi qˇ
ˇ
qi
j“1
i“1

L
paq ÿ

ď

ă

k3

n15{13

L
ÿ

pnqi ` vi q “

i“1

k3
,
n2{13

(42)

where paq follows from Prop. A.1 (Appendix A).
2. Multiplying out in the definition of g1 pu, y n q, we can simplify this expression as follows:
g1 pu, y n q “ n
“

k
L ÿ
ÿ

i“1 j“1

L
ÿ

i“1

vi

uj qij `

L
ÿ

i“1

vi

k
k
k
L
L
´ÿ
ÿ
uj qij
uj qij ¯2 1 ÿ ´ ÿ uj qij ¯2
1ÿ
´
´
nqi
vi
qi
2 i“1
qi
2 i“1
qi
j“1
j“1
j“1

k
L
L
k
k
´ÿ
ÿ
uj qij
1ÿ
uj qij ¯2 1 ÿ ´ ÿ uj qij ¯2
´
,
´
nqi
vi
qi
2 i“1
qi
2 i“1
qi
j“1
j“1
j“1

ř
ř
where the second equality follows because L
qij “ 1 for all j “ 1, 2, . . . , k and kj“1 uj “ 0 (see
i“1
ř řk
(17)), and so L
i“1
j“1 uj qij “ 0.
We bound the difference of g1 pu, y n q and g2 pu, y n q as follows:
L
k
ˇÿ
´ÿ
ˇ
ˇ
k2
uj qij ¯2 ˇˇ
ˇg1 pu, y n q ´ g2 pu, y n qˇ “ 1 ˇˇ
vi
ˇ ă 10{13 }v}1 for all u P B1 ,
2 i“1
qi
2n
j“1

(43)

16

where the inequality follows from (41). As an immediate consequence, for every y n P E1 ,

3
ˇ
ˇ
ˇg1 pu, y n q ´ g2 pu, y n qˇ ď k for all u P B1 .
n2{13
n
Combined with (42), we deduce that for every y P E1 , u P B1
ˇ
ˇ
2k3
ˇ
ˇ
ˇgpu, y n q ´ g2 pu, y n qˇ ă 2{13 .
n
Therefore, for all y n P E1 , u P B1
!
´ 3 ¯
´ ´2k3 ¯)
ˇ
ˇ
ˇ exppgpu, y n qq ´ exppg2 pu, y n qqˇ ď exppg2 pu, y n qq max exp 2k
´
1,
1
´
exp
n2{13
n2{13
(44)
3
4k
n
ď 2{13 exppg2 pu, y qq,
n
where the last inequality holds for all n ě N pk, ǫq for a suitably chosen N pk, ǫq, and it follows from the
fact that |ex ´ 1| ď 2|x| for all x ď 1{2.

Next we show that P pY n P E1 q is close to 1 when n is large enough.

Proposition V.3. There is an integer N pk, ǫq such that for all n ą N pk, ǫq,
P pY n P E1 q ą 1 ´

1

n1{13

.

(45)

Proof. Given u P B1 , define the event
Eu “

L !
č

i“1

k
ˇ kn8{13 )
ˇ
ÿ
ˇ
ˇ
.
nuj qij ˇ ă
y n : ˇvi ´
2k
j“1

(Recall that v is a function of y n ). To prove the proposition, we first show that Eu Ď E1 for all u P B1 .
Then we show that P pY n P pEu qc |U “ uq is small for all u P B1 .
By the triangle inequality, we have
k
L ˇ
k
L ˇÿ
ˇ
ˇ ÿ
ÿ
ÿ
ˇ
ˇ
ˇ
ˇ
nuj qij ˇ.
nuj qij ˇ `
}v }1 ď
ˇvi ´
ˇ
i“1

i“1 j“1

Further,

k
L ÿ
k
L ÿ
k
L ˇÿ
ˇ ÿ
ÿ
ÿ
ˇ
ˇ
8{13
qij “ kn8{13 ,
n|u
|q
ď
n
ď
nu
q
ˇ
j ij
j ij ˇ
i“1 j“1

i“1 j“1

i“1 j“1

and trivially,

j“1

k
k
L ˇ
ˇ
ˇ
ˇ
ÿ
ÿ
ÿ
ˇ
ˇ
ˇ
ˇ
k
nuj qij ˇ.
nuj qij ˇ ď 2 max ˇvi ´
ˇvi ´

i“1

iPrLs

j“1

j“1

Combining these estimates, we obtain

k
ˇ
ˇ
ÿ
ˇ
ˇ
nuj qij ˇ for all u P B1 .
}v}1 ď kn8{13 ` 2k max ˇvi ´
1ďiďL

As a result, for all u P B1

j“1

Eu Ď E1 .

(46)

17

n
Note
řk that, conditional on U “ u, the random variable ti pY q has binomial distribution Bpn, qi `
j“1 uj qij q. Using Hoeffding’s inequality, for every u P B1 , i “ 1, . . . , L we have

k
k
ˇ
ˇ kn8{13 ˇ
¯ˇ
)
)
!ˇ t pY n q ´
!ˇ
ÿ
ÿ
k
ˇ
ˇ
ˇ
ˇ i
ˇ
ˇ
u
q
U
“
u
ě
´
q
`
U
“
u
“
P
P ˇVi ´
nuj qij ˇ ě
ˇ
ˇ
ˇ
ˇ
j ij
i
n
2k
2k n5{13
j“1
j“1
´ k2 n3{13 ¯
(47)
ď 2 exp ´ 2k´1 .
2
Combining (46) and (47), for every u P B1 we have

P pY n P pE1 qc |U “ uq ď P pY n P pEu qc |U “ uq
L
k
ˇ kn8{13 ˇ
!ˇ
)
ÿ
paq ÿ
ˇ
ˇ
ˇ
P ˇVi ´
nuj qij ˇ ě
ď
U
“
u
ˇ
2k
i“1
j“1
! k2 n3{13 )
ď 2L exp ´ 2k´1
2
! k2 n3{13 )
pbq
ď 2k`1 exp ´ 2k´1
2

where paq follows from the union bound and pbq follows from the fact that L ď 2k . Therefore,
! k2 n3{13 )
1
P pY n P E1 q ě 1 ´ 2k`1 exp ´ 2k´1 ą 1 ´ 1{13 ,
2
n
where the last inequality holds for all n ě N pk, ǫq for a suitably chosen N pk, ǫq.
C. Gaussian approximation to the posterior distribution
The expression (38) for the function g2 pu, y n q can also be written as
g2 pu, y n q “ ´

L
k
L
ÿ
vi ¯2 ÿ vi2
n ´ÿ
uj qij ´
`
.
2qi j“1
n
2nqi
i“1
i“1

Given v P RL , let us define a function hv : Rk´1 Ñ R and a constant Cv as
hv puq “

L
k
ÿ
n´ ÿ
vi ¯ 2
uj qij ´
for all u P Rk´1 ,
q
n
i
i“1
j“1

Cv “ exp

L
´ÿ
vi2 ¯
.
2nqi
i“1

(48)

(see (23); note that Cv does not depend on u). Using this notation, we have
L
ÿ
1
vi2
g2 pu, y n q “ ´ hv puq `
,
2
2nqi
i“1

(49)

exppg2 pu, y n qq “ Cv expp´hv puq{2q.

In order to estimate u from y n , we need to find the conditional distribution fU|Y n pu|y n q. As a first step,
we need to calculate
ż
ż
n
n
exppgpu, y n qqdu,
fU,Y n pu, y qdu “ Cv1
PY n py q “
Rk´1

B1

where Cv1 is defined in Prop. V.1; however this appears difficult (while it is possible to find the asymptotics
of this integral using, for instance, the multi-dimensional version of the Laplace method [18], controlling
the error terms presents a problem, so we proceed in an ad-hoc way). According to (40) and (45), when

18

n is sufficiently large, with large probability the ratio between exppg2 pu, y n qq and exppgpu, y n qq is very
close to 1. So we can use the following integral to approximate PY n py n q:
ż
ż
¯
´ 1
(50)
exppg2 pu, y n qqdu “ Cv1 Cv
Gpy n q “ Cv1
exp ´ hv puq du.
2
B1
B1

The integrand in (50) is proportional to the probability density function of some Gaussian distribution. We
will make use of this property to obtain an approximation to Gpy n q, which is in turn an approximation
of PY n py n q.
Define
L
k
´ÿ
¯2 ¯1{2
1´ÿ
δ “ δpQq “
min
u
q
(51)
j
ij
ř
uPRk´1 : ki“1 u2i “1 i“1 qi j“1
(repeated here from (29)). Note that we are minimizing a continuous function over a compact set, so the
minimum is attained. It is easy to verify that for all u P Rk´1
k
k
L
¯1{2
¯2 ¯1{2
´ÿ
´ÿ
1´ÿ
uj qij
.
ěδ
u2i
q
i“1
i“1 i j“1

(52)

Given k and ǫ, let define a constant
δ0 “ δ0 pk, ǫq :“

d

1
32M pk, ǫq

(53)

where M pk, ǫq is given by (13). The remainder of the proof of Theorem III.1 depends on whether δ ě δ0
or not. We divide the proof into these two cases because without this division, we can only prove a
weaker version of (19), where the constants Cpk, ǫq and N pk, ǫq are replaced with constants that depend
on Q.
D. Case 1: δ ě δ0

ℓ2

2
We use the Bayes estimation loss to bound below rk,n
pQq. It is well known that under ℓ22 loss, the
optimal Bayes estimator for ui is EpUi |Y n q. Therefore, the optimal Bayes estimation loss is

k
ÿ

i“1

EpUi ´ EpUi |Y n qq2 ,

(54)

and this is equal to the sum of the variances of the posterior distributions of Ui given Y n . The main idea
is to approximate the posterior distribution of U given Y n by ařmultivariate Gaussian distribution. More
T
specifically, we define a pk ´ 1q ˆ pk ´ 1q matrix Φpn, Qq :“ L
i“1 zi zi , where
c
n
zi “
pqi,1 ´ qi,k , qi,2 ´ qi,k , . . . , qi,k´1 ´ qi,k q.
(55)
qi
Equivalently, Φpn, Qq is defined by its associated quadratic form as follows:
uT Φpn, Qqu “

L
L
k
k´1
¯2 ÿ
¯2
ÿ
n´ ÿ
n´ ÿ
uj qij “
uj pqij ´ qik q for all u P Rk´1 .
q
q
i“1 i j“1
i“1 i j“1

(56)

Since δ ě δ0 ą 0, we have uT Φpn, Qqu ą 0 for all u ‰ 0, which shows that Φpn, Qq is positive definite.
For simplicity of notation, we write it as Φ, omitting the arguments. We will show that when n is large
enough, there is a set E2 Ď Yn with P pY n P E2 q close to 1, such that conditional
every y n P E1 X E2 ,
řon
k
´1
the covariance matrix of U is close to Φ . This will enable us to conclude that i“1 EpUi ´ EpUi |Y n qq2
can be approximated as trpΦ´1 q ` 1T Φ´1 1, where 1 is the all-ones column vector of length k ´ 1.

19

More precisely, our proof of Case 1 consists of two steps, summarized in the following proposition.
Proposition V.4. There are two positive constants C3 pk, ǫq, C4 pk, ǫq and an integer N pk, ǫq such that
when n ě N pk, ǫq, the following lower bound holds for all Q P Dǫ,E :
´
C3 pk, ǫq
C4 pk, ǫq ¯
ℓ22
ptrpΦ´1 q ` 1T Φ´1 1q ´ 14{13 .
(57)
pQq ě 1 ´
rk,n
1{13
n
n
Furthermore, for all Q P Dǫ,E and all positive integer n,
1
M pk, ǫq.
(58)
n
Once both (57) and (58) are established, this will complete the proof of Theorem III.1 for Case 1
because of (13), (14) and (19).
trpΦ´1 q ` 1T Φ´1 1 ě

1) Proof of (57): In order to prove inequality (57), we develop a refined version of the Local
Asymptotic Normality approach [16], [17]2 . Consider the ellipsoid (see (18))
´ 1
3{δ0 ¯
B2 “ B 5{13 ´ 6{13 ,
n
n
n
and define a subset E2 Ď Y as follows:
L
k
!
)
ÿ
n´ ÿ
vi ¯2
E2 “ y n : Dũ P B2 such that
ũj qij ´
ă n1{13 .
q
n
i“1 i j“1

Recall our convention that ũk “ ũk pũq “ ´
with PMFs.

řk´1
i“1

ũi , which stems from the fact that we are working

Proposition V.5. There is an integer N pk, ǫq such that for all n ą N pk, ǫq,
P pY n P E2 q ě 1 ´

2k`1 ` 3k{δ0
.
n1{13

(59)

The proof is given in Appendix B.
Our goal will be to show that for y n P E2 , the ratio between Gpy n q in (50) and
ż
´ 1
¯
n
Hpy q “ Cv1 Cv
exp ´ hv puq du
2
Rk´1

(60)

is very close to 1. Specifically, we have

Proposition V.6. There is an integer N pk, ǫq such that for all n ą N pk, ǫq and all y n P E2 ,
´
256 ¯
1 ´ 2{13 Hpy n q ď Gpy n q ď Hpy n q
(61)
n
The upper bound on Gpy n q in (61) is obvious. To prove the lower bound, we need several auxiliary
definitions and propositions.
Given α ą 0 and ũ P Rk´1 , define the set
a
a
Ev pũ, αq “ tu P Rk´1 : hv puq ´ hv pũq ą αu.
(62)

Proposition V.7. For every y n P E2 and α ě n´5{13 , there exists ũ P B2 such that the ellipsoid Bpαq
defined in (18) satisfies
pBpαqqc Ď Ev pũ, δ0 n1{2 pα ´ n´5{13 q ` n1{26 q.
(63)
2

A detailed discussion of the connection between our proof and LAN appears in Appendix J.

20

The proof is given in Appendix C.
Proposition V.8. Let Φ be an s ˆ s positive definite matrix, and let t be a column vector in Rs . Define
a quadratic function h : Rs Ñ R as follows:
hpuq “ pu ´ tqT Φpu ´ tq ` C,

(64)

where C ě 0 is a nonnegative constant. For a given ũ P Rs , define the set
a
a
Epũ, αq “ tu P Rs : hpuq ´ hpũq ą αu.
?
For all α ě s and all ũ P Rs the following inequality holds true:
ş
? 2
expp´ 12 hpuqqdu
Epũ,αq
´ pα´2 sq
ş
.
ď
e
expp´ 21 hpuqqdu
Rs

(65)

The proof is given in Appendix D.

Proof of Proposition V.6: Our plan is to use Prop. V.8 for the function hv defined in (48) in order to
estimate Gpy n q. First let us show that hv can be written as a quadratic form of the type (64). Define a
vector w P Rk´1 as follows:
L
´ÿ
¯T
pqim ´ qik qvi
w “ wpv, Qq “
, m “ 1, . . . , k ´ 1 .
(66)
qi
i“1

Then we have

k
L ÿ
k
L
L
¯2
ÿ
ÿ
ÿ
vi qij
vi2
n´ ÿ
uj qij ´ 2
uj `
hv puq “
q
qi
nqi
i“1 j“1
i“1
i“1 i j“1

“ uT Φu ´ 2
T

“ u Φu ´ 2

k ´ÿ
L
L
ÿ
ÿ
qij vi ¯
vi2
uj `
qi
nqi
j“1 i“1
i“1
L
k´1
ÿ ´ÿ
j“1

L

ÿ v2
pqij ´ qik qvi ¯
i
uj `
q
nq
i
i
i“1
i“1

“ uT Φu ´ wT u ´ uT w `

L
ÿ
vi2
nqi
i“1

“ pu ´ Φ´1 wqT Φpu ´ Φ´1 wq ´ wT Φ´1 w `

L
ÿ
vi2
,
nq
i
i“1

(67)

where the second equality follows from the definition of Φ in (56).
ř
vi2
Since hv puq ě 0 for all u P Rk´1 , the constant term C :“ ´wT Φ´1 w ` L
i“1 nqi is nonnegative. This
shows that hv satisfies the conditions in Prop. V.8.
To estimate Gpy n q we first note that, by Prop. V.7, for every y n P E2 , there exists ũ P B2 such that
pB1 qc Ď Ev pũ, n1{26 q. We then obtain
ż
´ 1
¯
exp ´ hv puq du
Gpy n q “ Cv1 Cv
2
B1
ż
´ 1
¯
¯ ¯
´ż
´ 1
exp ´ hv puq du
exp ´ hv puq du ´
ě Cv1 Cv
2
2
Ev pũ,n1{26 q
Rk´1
¯¯
´
´ 1`
?
˘2
ě Hpy n q 1 ´ exp ´ n1{26 ´ k ´ 1
2

21

´
256 ¯
ě Hpy n q 1 ´ 2{13 .
n
Here the next-to-last step follows from Prop. V.8, and the last inequality holds for all n ě N pk, ǫq as
long as we choose N pk, ǫq large enough. This proves the lower bound in (61).

We have shown that Gpy n q can be approximated by Hpy n q. Based on this, we can further show that
PY n py n q can be approximated by Hpy n q.

Lemma V.9. There is an integer N pk, ǫq such that for all n ą N pk, ǫq and all y n P E1 X E2 ,
ˇ
ˇ 4k3 ` 256
ˇ n n
n ˇ
P
py
q
´
Hpy
q
Hpy n q.
ˇ Y
ˇď
n2{13
Proof. For every y n P E1 we have
ż
ˇ
ˇ ż
ˇ
ˇ
exppg2 pu, y n qqduˇ
exppgpu, y n qqdu ´ Cv1
|PY n py n q ´ Gpy n q| “ ˇCv1
B1
ż B1
n
| exppgpu, y qq ´ exppg2 pu, y n qq|du
ď Cv 1
B1
ż
paq 4k 3
4k3
ď 2{13 Cv1
exppg2 pu, y n qqdu “ 2{13 Gpy n q
n
n
B1
3
4k
ď 2{13 Hpy n q,
n
where paq follows from (40). On account of (61), this concludes the proof.
Define
f1 pu, y n q “

Cv1 exppg2 pu, y n qq
.
Hpy n q

(68)

(69)

For every y n P E1 X E2 , we can approximate the conditional probability density function fU|Y n pu|Y n “
y n q as f1 pu, y n q. At the same time, we will also show that for a fixed y n , f1 pu, y n q is the probability
density function of a Gaussian random vector with mean vector Φ´1 w and covariance matrix Φ´1 .
The difference is bounded as follows: for all u P B1 ,
ˇ C 1 exppgpu, y n qq C 1 exppg pu, y n qq ˇ
ˇ v
ˇ
v
2
|fU|Y n pu|Y n “ y n q ´ f1 pu, y n q| “ ˇ
´
ˇ
PY n py n q
Hpy n q
´
¯
paq Cv1 exppg2 pu, y n qq
1 ` 4k3 {pn2{13 q
1 ´ 4k3 {pn2{13 q
max
ď
´
1,
1
´
Hpy n q
1 ´ p4k3 ` 256q{pn2{13 q
1 ` p4k3 ` 256q{pn2{13 q
pbq 16k 3 ` 512
f1 pu, y n q
ď
2{13
n
pcq C1 pk, ǫq
“
f1 pu, y n q,
(70)
n2{13
where paq follows from (40) and (68); pbq holds for all n ě N pk, ǫq as long as we take N pk, ǫq ą
p8k3 ` 512q13{2 ; in pcq we define C1 pk, ǫq :“ 16k3 ` 512. By definition,
¯
´
Cv1 Cv exp ´ 21 hv puq
´
¯
f1 pu, y n q “
ş
Cv1 Cv Rk´1 exp ´ 21 hv puq du
¯
´
1
´1
T
´1
exp ´ 2 pu ´ Φ wq Φpu ´ Φ wq
paq
´
¯
“ ş
1
´1 wqT Φpu ´ Φ´1 wqdu
exp
´
p
u
´
Φ
Rk´1
2

22

“a

a

|Φ|

p2πqk´1

´ 1
¯
exp ´ pu ´ Φ´1 wqT Φpu ´ Φ´1 wq ,
2

(71)

where paq follows from (67). Thus f1 indeed represents a Gaussian pdf.

Recall that our goal is to estimate the Bayes estimation loss (54). Proceeding in this direction, we
show next that for every y n P E1 X E2 , the ℓ1 distance between EpU|Y n “ y n q and Φ´1 w is very small.

Lemma V.10. There is an integer N pk, ǫq such that for all n ą N pk, ǫq and all y n P E1 X E2 ,
}EpU|Y n “ y n q ´ Φ´1 w}1 ď

where C2 pk, ǫq :“

32k 4 eǫ pk 3 `32q
δ02

`

?

C2 pk, ǫq
,
n7{13

k ´ 1.

Proof.
}EpU|Y n “ y n q ´ Φ´1 w}1
ż
›ż
›
n
n
ufU|Y n pu|Y “ y qdu ´
“›
“

ď
paq

ď

B1
k´1
ÿ ˇż

ˇ
ˇ

B1
i“1
ż
k´1
ÿˇ
i“1

ˇ
ˇ

B1

ui pfU|Y n pu|Y

16k3 ` 512
n2{13

16k3

1

Rk´1

ui fU|Y n pu|Y n “ y n qdu ´

` 512
n2{13

k´1
ÿż
i“1

B1

n

›
›
uf1 pu, y n qdu›

ż

Rk´1

ˇ
ˇ
ui f1 pu, y n qduˇ

ˇż
ˇ k´1
ˇ ÿˇ
“ y q ´ f1 pu, y qqduˇ `
ˇ
n

n

i“1

|ui |f1 pu, y n qdu `

ż

ż

k´1
ÿż
i“1

pB1

qc

pB1 qc

ˇ
ˇ
ui f1 pu, y n qduˇ

|ui |f1 pu, y n qdu

}u}1 f1 pu, y n qdu
}u}1 f1 pu, y n qdu `
c
pB1 q
c
ˆ
˙ ż
pbq 16k 3 ` 512 ?
2pk ´ 1q
´1
´1
ď
k ´ 1}Φ w}2 `
}u}1 f1 pu, y n qdu,
trpΦ q `
π
n2{13
pB1 qc

ď

Rk´1

(72)

where paq follows from (70); and pbq is justified in Appendix E.
Now let us write out w from its definition in (66):
}w}2 ď }w}1 “
ď keǫ

L
k´1
ÿ ˇÿ
j“1

L
k´1
ÿÿ

j“1 i“1

ˇ
ˇ

pqij ´ qik qvi ˇˇ
ˇ
qi
i“1

|vi |

ď 2k2 pk ´ 1qeǫ n8{13 for all y n P E1 ,

where the second line follows from the fact that the vector pqi,1 , qi,2 , . . . , qik q is proportional to one of
the vectors in t1, eǫ uk and the third one follows directly from the definition of E1 .
Next we claim that all the eigenvalues of Φ´1 are no greater than 1{pnδ02 q. Indeed, according to (52)
and (56), for all u P Rk´1
k
k
L
¯
¯2
´ÿ
ÿ
1´ÿ
2
2
ui ě nδ02 }u}22 .
uj qij ě nδ
u Φu “ n
q
i“1
i“1 i j“1
T

(73)

23

Using this, we have
2k3 eǫ
1
}w}2 ă 5{13 2 for all y n P E1 ,
2
nδ0
n
δ0
k
k´1
ă 10{13 4 ,
trpΦ´1 q ď
2
nδ0
n
δ0

}Φ´1 w}2 ď

where the last inequality holds for all n ě N pk, ǫq as long as we set N pk, ǫq to be large enough.
Combining the two inequalities above with (72), we deduce that for every y n P E1 X E2 ,
›
›
›
›
›EpU|Y n “ y n q ´ Φ´1 w›
1
ż
16k3 ` 512 2k4 eǫ
}u}1 f1 pu, y n qdu
`
ď
c
n2{13
n5{13 δ02
pB1 q
ż
32k4 eǫ pk3 ` 32q
“
}u}1 f1 pu, y n qdu
`
c
n7{13 δ02
pB1 q
ż
32k4 eǫ pk3 ` 32q ?
}u}2 f1 pu, y n qdu
` k´1
ď
n7{13 δ02
pB1 qc
ż
k
¯1{2
´ÿ
32k4 eǫ pk3 ` 32q ?
2
u
f1 pu, y n qdu
`
ď
k
´
1
i
n7{13 δ02
pB1 qc i“1
?
32k4 eǫ pk3 ` 32q
k´1
ă
(74)
` 7{13 ,
2
7{13
n
δ0
n
where the last inequality follows by the estimate (99) proved in Appendix F below. This completes the
proof of the lemma.
In the next step we bound the conditional expectation

řk

i“1 EpUi

´ EpUi |Y n qq2 when Y n P E1 X E2 .

Lemma V.11. There is an integer N pk, ǫq such that for all n ą N pk, ǫq and all y n P E1 X E2 ,
k
ÿ

´
¯ C pk, ǫq
C1 pk, ǫq ¯´
3
´1
T ´1
ErpUi ´ EpUi |Y n “ y n qq2 |Y n “ y n s ě 1 ´
trpΦ
q
`
1
Φ
1
´ 14{13 ,
2{13
n
n
i“1

where C3 pk, ǫq :“ 2pC2 pk, ǫqq2 ` 1.

(75)

Proof. As in Appendix F, given y n P Yn , define Ūpy n q “ pŪ1 py n q, . . . , Ūk´1 py n qq to be a pk ´ 1qdimensional Gaussian random vector with density function fŪpyn q p¨q “ f1 p¨, y n q, mean vector Φ´1 w and
covariance matrix Φ´1 . By Lemma V.10, for every y n P E1 X E2 we have
`
˘
C2 pk, ǫq
}EpU|Y n “ y n q ´ E Ūpy n q }1 “ }EpU |Y n “ y n q ´ Φ´1 w}1 ă
.
n7{13
řk´1
As usual, let Ūk py n q :“ ´ i“1
Ūi py n q. For every y n P E1 X E2 ,
k
ÿ

pEpUi |Y n “ y n q ´ EŪi py n qq2

i“1

“

k´1
ÿ
i“1

pEpUi |Y n “ y n q ´ EŪi py n qq2 `

ď 2}EpU|Y n “ y n q ´ EŪpy n q}21 ă

´ k´1
ÿ
i“1

EpUi |Y n “ y n q ´

pk, ǫqq2

2pC2
n14{13

k´1
ÿ
i“1

¯2
EŪi py n q

24

C3 pk, ǫq ´ 1
n14{13
(on the second line we use the definition of Ūk ). As a result, for every y n P E1 X E2 ,
“

k
ÿ

ErpUi ´ EpUi |Y n “ y n qq2 |Y n “ y n s

i“1

paq

“

ą
“

k
ÿ

i“1
k
ÿ

ErpUi ´ EpŪi py n qqq2 |Y n “ y n s ´

k
ÿ

i“1

ErrpUi ´ EpŪi py n qqsq2 |Y n “ y n s ´

i“1
k ż
ÿ

i“1 B1

pEpUi |Y n “ y n q ´ EpŪi py n qqq2

C3 pk, ǫq ´ 1
n14{13

pui ´ EpŪi py n qqq2 fU|Y n pu|Y n “ y n qdu ´

C3 pk, ǫq ´ 1
n14{13

k ż
´
C1 pk, ǫq ¯ ÿ
C3 pk, ǫq ´ 1
ě 1´
pui ´ EpŪi py n qqq2 f1 pu, y n qdu ´
n2{13
n14{13
i“1 B1
k ż
´
C1 pk, ǫq ¯ ÿ
C3 pk, ǫq ´ 1
ě 1´
pui ´ EpŪi py n qqq2 f1 pu, y n qdu ´
2{13
k´1
n
n14{13
i“1 R
k ż
ÿ
pui ´ EpŪi py n qqq2 f1 pu, y n qdu
´
pbq

c
i“1 pB1 q

k
´
C3 pk, ǫq ´ 1
C1 pk, ǫq ¯ ÿ
VarpŪi py n qq ´
“ 1´
2{13
n
n14{13
i“1
ż
k
ÿ
pui ´ EpŪi py n qqq2 f1 pu, y n qdu,
´

pcq

(76)

pB1 qc i“1

where paq follows by a straightforward rewriting; in pbq we use (70); pcq follows
fact that the
řk´1from the
n
n
n
n
probability density function of Ūpy q is f1 p¨, y q. Further, since Ūk py q “ ´ i“1 Ūi py q, we have
k
ÿ

i“1

VarpŪi py n qq “

k´1
ÿ
i“1

VarpŪi py n qq ` Var

“ trpΦ

´1

T

q`1 Φ

´1

1.

´ k´1
ÿ
i“1

¯
Ūi py n q

(77)

Finally, the integral in (76) is estimated in (104) in Appendix G. Using this estimate together with (77)
in (76), we arrive at the claimed inequality (75).
Now let us take the final step toward our goal of proving (57). Combining (75) with (45) and (59),
we bound below the optimal Bayes estimation loss as follows:
k
´
¯2
ÿ
E Ui ´ EpUi |Y n q

i“1

´´
C3 pk, ǫq ¯
C1 pk, ǫq ¯
´1
T ´1
ptrpΦ
q
`
1
Φ
1
q
´
ěP pY n P E1 X E2 q 1 ´
n2{13
n14{13
¯´´
¯
´
k`1
C1 pk, ǫq
C3 pk, ǫq ¯
1`2
` 3k{δ0
´1
T ´1
1
´
ptrpΦ
q
`
1
Φ
1
q
´
ě 1´
n1{13
n2{13
n14{13
´
¯
k`1
1`2
` 3k{δ0 C1 pk, ǫq
C3 pk, ǫq
ě 1´
´
ptrpΦ´1 q ` 1T Φ´1 1q ´ 14{13
1{13
2{13
n
n
n

25

´
C3 pk, ǫq
C4 pk, ǫq ¯
ptrpΦ´1 q ` 1T Φ´1 1q ´ 14{13 ,
ą 1´
n1{13
n
k`1
where in the last inequality we define C4 pk, ǫq :“ 1 ` 2
` 3k{δ0 ` C1 pk, ǫq. This establishes (57) and
completes the first step of the proof of Proposition V.4.

2) Proof of (58): We use the Cauchy-Schwarz inequality to bound trpΦ´1 q ` 1T Φ´1 1. The result is
given in the following proposition, which is proved in Appendix H.
Proposition V.12.
ř
´ řk´1 Φ
¯
ii
i‰j Φij ´1
i“1
trpΦ q ` 1 Φ 1 ě pk ´ 1q
.
(78)
´
k
kpk ´ 1q
Now let us further bound the term on right-hand side of (78). Recalling the definition of Φ in (55),
we write it out explicitly and perform a series of straightforward manipulations:
ř
řk´1
i‰j Φij
i“1 Φii
´
k
kpk ´ 1q
k´1
L
´ k´1
¯
¯¯
ÿ
ÿ´
ÿ
ÿ
1´
n
pqij ´ qik q2 ´
pk ´ 1q
pqij 1 ´ qik q pqij ´ qik q
“
kpk ´ 1q i“1 qi
j“1
j“1 1ďj 1 ďk´1,j 1 ‰j
´1

“
“
“

T

´1

k´1
L
´ k´1
¯
¯¯
ÿ ´ k´1
ÿ
ÿ
1´ ÿ
n
pqij ´ qik q2 ´
k
pqij 1 ´ qik q pqij ´ qik q
kpk ´ 1q i“1 qi j“1
j“1 j 1 “1
k´1
L
´ k´1
¯2 ¯
ÿ
ÿ
1´ ÿ
n
pqij ´ qik q2 ´
pqij ´ qik q
k
kpk ´ 1q i“1 qi j“1
j“1
k´1
k´1
L
ÿ
ÿ
1! ÿ 2
n
2
qij ` kpk ´ 1qqik
qij ´ 2kqik
k
kpk ´ 1q i“1 qi
j“1
j“1

´

´´ k´1
ÿ
j“1

qij

¯2

´ 2pk ´ 1qqik

k´1
ÿ
j“1

2
qij ` pk ´ 1q2 qik

¯)

k´1
k´1
´ k´1
ÿ ¯2 ¯
ÿ
n
1´ ÿ 2
2
“
qij
´
qij ` pk ´ 1qqik
qij ´ 2qik
k
kpk ´ 1q i“1 qi j“1
j“1
j“1
L
ÿ

k
k
L
ÿ
n
1 ´ ÿ 2 ´ ÿ ¯2 ¯
“
q ´
qij
k
kpk ´ 1q i“1 qi j“1 ij
j“1

“
ď

k ´
L
¯
´ ÿ
ÿ
qij ¯2
n
´ k2
qi k
kpk ´ 1q i“1
qi
j“1

L
ÿ
n
d˚ pk ´ d˚ q
k2 peǫ ´ 1q2 ˚ ǫ
qi
kpk ´ 1q
pd e ` k ´ d˚ q2 i“1

(79)

(80)

d˚ pk ´ d˚ q
n
kpeǫ ´ 1q2 ˚ ǫ
(81)
k´1
pd e ` k ´ d˚ q2
where (79) follows by definition of qi in Table I, and the inequality used to arrive at (80) is proved in
(114), Appendix I.
Substituting (81) into (78), we obtain inequality (58).
Now we are ready to prove (19) using (57) and (58). For this, we set
“

Cpk, ǫq :“ C4 pk, ǫqM pk, ǫq ` C3 pk, ǫq.

26

We obtain
ℓ2

2
pQq ě
rk,n

k
ÿ

EpUi ´ EpUi |Y n qq2 ě

i“1

Cpk, ǫq
1
M pk, ǫq ´ 14{13 .
n
n

This completes the proof of (19) for the case δ ě δ0 .
E. Case 2: δ ă δ0

This case is much easier to handle: We can rely on a straightforward application of Le Cam’s method
[15] (see also [19, Lemma 1]).
Our goal is again to prove (19). We use standard distance functions on distributions defined on finite
sets Y. The KL divergence between two such distributions m1 and m2 is defined as
ÿ
m1 pyq
Dkl pm1 }m2 q :“
m1 pyq log
.
m2 pyq
yPY
The total variation distance between m1 and m2 is defined as
}m1 ´ m2 }TV :“ max |m1 pAq ´ m2 pAq| “
AĎY

1ÿ
|m1 pyq ´ m2 pyq|.
2 yPY

(82)

According to (51), there is ũ P Rk´1 such that3
k
ÿ

i“1

ũ2i “ 1 and

With this ũ in mind, let

k
L
¯2 ¯1{2
´ÿ
1´ÿ
ũj qij
“ δ.
q
i“1 i j“1

(83)

?
p1 “ pU and p2 “ pU ` ũ{ nδ2

where as before, pU “ p1{k, 1{k, . . . , 1{kq denotes the uniform pmf.
Note that some of the coordinates of ũ can be negative, but we can ensure that p2 P ∆k for all
n ě N pk, ǫq as long as N pk, ǫq is sufficiently large. Consequently,
´
¯
1
ℓ22
pQq “ inf sup
rk,n
E ℓ22 pp̂pY n q, pq ě inf nE n ℓ22 pp̂pY n q, p1 q ` nE n ℓ22 pp̂pY n q, p2 q ,
Y „m2
2 p̂ Y „m1
p̂ pP∆k Y n „ppQqn
where m1 “ p1 Q and m2 “ p2 Q.
For a given estimator p̂ : Yn Ñ Rk , define the set

K1 :“ ty n P Yn : ℓ2 pp̂py n q, p1 q ě ℓ2 pp̂py n q, p2 qu
By the triangle inequality, we have
1
ℓ2 pp̂py n q, p1 q ě ℓ2 pp1 , p2 q “
2
1
ℓ2 pp̂py n q, p2 q ě ℓ2 pp1 , p2 q “
2

1
?
for all y n P K1 ,
2
2 nδ
1
?
for all y n P Kc1 .
2
2 nδ

Therefore, for any estimator p̂,
E ℓ22 pp̂pY n q, p1 q ` nE n ℓ22 pp̂pY n q, p2 q
Y „m 2
¯
1 ´ n n
n
n
c
m
pY
P
K
q
`
m
pY
P
K
q
ě
1
1
2
1
4nδ2

E :“

3

Y n „mn
1

we again use the convention that ũk “ ´

řk´1
i“1

ũi .

27

¯
1 ´
n
n
n
n
1
´
m
pY
P
K
q
`
m
pY
P
K
q
1
1
2
1
4nδ2
´
¯¯
´
1
n
n
n
n
m
pY
P
K
q
´
m
pY
P
K
q
1
´
sup
ě
2
1
4nδ2
KĎYn
¯
1 ´
n
n
“
,
1
´
}
m
´
m
}
TV
2
1
4nδ2
“

where the last step follows by definition (82). Using Pinsker’s inequality4 , we obtain
c
c
´
¯
¯
1
n
1 ´
1
n
n
Eě
1´
1´
Dkl pm2 }m1 q “
Dkl pm2 }m1 q .
4nδ2
2
4nδ2
2

Let us write out this expression explicitly, recalling the fact that the original output alphabet is Y “
t1, 2, . . . , L1 u and using in succession (33), (35), (34):
g
¯ +¸
´
f
řk
#
˜
1
f ÿ
k
L1 ´ ÿ
?ũj
´
¯¯
Q
pi|jq
`
fn
j“1
k
ũj
1
1
nδ2
Eě
Qpi|jq
`?
log
1´e
řk
2
1
2
4nδ
2 i“1
k
nδ
j“1 Qpi|jq k
j“1
g
˜
+¸
řk
f L1 #´
1`
k
¯
?ũj
fn ÿ
q
ÿ
Q
pi|jq
ũ
1
2
j“1
i
j
nδ
1´e
log
Qpi|jq ?
“
qi1 `
1
2
4nδ2
2 i“1
q
nδ
i
j“1
g
˜
+¸
f L1 # ´
k
k
¯
´
¯
ÿ
ÿ
fn ÿ
Q
pi|jq
ũ
ũ
1
Q
pi|jq
j
j
?
?
1´e
q1 1 `
“
log 1 `
1
1
2
4nδ2
2 i“1 i
q
q
nδ
nδ2
i
i
j“1
j“1
g
+¸
˜
f L #´
k
k
´
ÿ
ÿ
ÿ ¯´
fn ÿ
qij ũj ¯
qij ũj ¯
1
e
1
?
?
log 1 `
qa 1 `
1´
“
4nδ2
2 i“1
q
q
nδ2
nδ2
j“1 i
j“1 i
aPAi
g
+¸
˜
f L #´
k
k
¯
´
¯
ÿ
ÿ
fn ÿ
q
ũ
ũ
1
ij
j
? j
log 1 `
.
qij ?
qi `
1´e
“
2
4nδ2
2 i“1
q
nδ
nδ2
i
j“1
j“1
Bounding above the logarithm by logp1 ` 1q ď x, we further obtain
g
˜
+¸
f L #´
k
k
ÿ
fn ÿ
ũj ¯´ ÿ qij ũj ¯
1
e
?
Eě
qij ?
qi `
1´
4nδ2
2 i“1
q
nδ2
nδ2
j“1
j“1 i
g
˜
¸
f ´ L k
k
L
´ÿ
¯2 ¯
ÿ
fn ÿ ÿ
ũ
ũ
1
1
j
j
qij ?
qij ?
`
1´e
“
4nδ2
2 i“1 j“1
nδ2 i“1 qi j“1
nδ2
g
¸
˜
f
k
L
´ÿ
¯2
f 1 ÿ
1
1
qij ũj
1´e 2
“
4nδ2
2δ i“1 qi j“1
c ¯
1 ´
1
1
1
“
1´
ą
ą
2
2
4nδ
2
16nδ
16nδ02
2
“ M pk, ǫq
n
Cpk, ǫq
1
ě M pk, ǫq ´ 14{13 ,
n
n
4

Pinsker’s inequality asserts that }P1 ´ P2 }2TV ď 12 Dkl pP1 }P2 q for any two probability measures P1 , P2 .

(84)

(85)
(86)

28

ř řk
where (84) follows from (17), namely from the equality L
i“1
j“1 qij ũj “ 0; (85) follows from the
definition of ũ in (83); (86) follows from (53). (In the last step we make a somewhat arbitrary transition
to match the inequality (57) established for the case δ ě δ0 .)
This completes the proof of (19) for the case δ ă δ0 .

VI. O UTLOOK : O PEN

QUESTIONS

A. Uniqueness of the optimal privatization scheme
We believe that our privatization scheme Qk,ǫ,d˚ is essentially the unique optimal choice. More
precisely, recall that we reduced the output alphabet from the original set to the set of equivalence
classes; see Sec. V-A. We conjecture that, under the assumption that Q P Dǫ,E and after the alphabet
reduction, any scheme Q that is different from Qk,ǫ,d˚ , will entail a strictly larger estimation loss value.
In other words, for n large enough
ℓ2

ℓ2

2
2
pQk,ǫ,d˚ , p̂q,
pQq ě rk,n
rk,n

where p̂ is given in (8). Formally, we can phrase this conjecture as follows:
Conjecture 1. For Q P Dǫ,E ,

ℓ2

2
pQq “ M pk, ǫq
lim nrk,n

nÑ8

(87)

if and only if Q “ Qk,ǫ,d˚ (after accounting for the alphabet reduction).
Let us list some necessary conditions for this to hold.
piq From the proof in Section V we know that
ℓ2

2
pQq ě nptrpΦ´1 q ` 1T Φ´1 1q.
lim inf nrk,n

nÑ8

(88)

Therefore, a necessary condition for (87) to hold is
1
M pk, ǫq.
(89)
n
According to (80), (114), equality in (89) implies that any (asymptotically) optimal privatization scheme
satisfies the condition that each vector pQpi|jq, j “ 1, . . . , kq is proportional to one of the vectors in the
set tpv1 , v2 , . . . , vk q P t1, eǫ uk : v1 ` ¨ ¨ ¨ ` vk “ d˚ eǫ ` k ´ d˚ u, i.e., after normalizing, it contains exactly
d˚ entries of eǫ and k ´ d˚ entries 1.
trpΦ´1 q ` 1T Φ´1 1 “

piiq The converse part of Prop. H.1 (specifically, the claim in (109)) gives another set of necessary
conditions for (89) to hold.
piiiq Note that (88) is obtained by choosing p from a neighborhood of the uniform distribution pU . A
similar bound can be obtained by choosing p to be in the neighborhood of any point in the probability
simplex ∆k . Formally speaking, the observable random variables in our problem are Y n , and the unknown
parameters are pp1 , p2 , . . . , pk´1 q. Denoting by Ipp1 , p2 , . . . , pk´1 q the Fisher information matrix. As
shown in Appendix J,
Φpn, Qq “ Ip1{k, 1{k, . . . , 1{kq.

Similarly to (88), one can show that
ℓ2

2
pQq ě n trppIpp1 , p2 , . . . , pk´1 qq´1 ` 1T pIpp1 , p2 , . . . , pk´1 qq´1 1q
lim inf nrk,n

nÑ8

for all pp1 , p2 , . . . , pk´1 , 1 ´ p1 ´ ¨ ¨ ¨ ´ pk´1 q P ∆k . Therefore another set of necessary conditions for
(87) to hold is
1
trppIpp1 , p2 , . . . , pk´1 qq´1 q ` 1T pIpp1 , p2 , . . . , pk´1 qq´1 1 ď M pk, ǫq
n

29

for all pp1 , p2 , . . . , pk´1 , 1 ´ p1 ´ ¨ ¨ ¨ ´ pk´1q P ∆k .
We believe that the conditions listed above imply the uniqueness claim of the privatization mechanism
Qk,ǫ,d˚ .
We conclude by suggesting an even stronger conjecture which we also believe to be true.
Conjecture 2. For all Q with finite output alphabet,
ℓ2

2
pQq “ M pk, ǫq
lim nrk,n

nÑ8

if and only if Q “ Qk,ǫ,d˚ (after accounting for the alphabet reduction).
B. Asymptotically tight lower bound for the ℓ1 loss
Another open question is to find an asymptotically optimal privatization mechanism/estimation procedure for the ℓ1 loss. We similarly believe that our privatization scheme Qk,ǫ,d˚ and the empirical estimator
p̂ given by (8) are asymptotically optimal in this case as well. More precisely, in [13], we have shown
that
c d
´ 1 ¯
2
pdeǫ ` k ´ dq2
k
´
1
ℓ1
`o ? .
pQk,ǫ,d , p̂q “ ǫ
rk,n
e ´ 1 πn
dpk ´ dq
n
It is clear that

ℓ1
pQk,ǫ,d˚ , p̂q “
rk,n

min r ℓ1 pQk,ǫ,d , p̂q.
1ďdďk´1 k,n

Our conjecture is
lim

nÑ8

?

ℓ1
nrǫ,k,n

k´1
“ ǫ
e ´1

c d
2 pd˚ eǫ ` k ´ d˚ q2
.
π
d˚ pk ´ d˚ q

(90)

Within the frame of our approach, the obstacle in the way of
proving this conjecture can be described
ař
as follows. Given a positive definite matrix M , let SpM q :“
i Mii . Similarly to (88), one can show
that
? ℓ1
?
lim inf nrk,n
pQq ě npSpΦ´1 q ` p1T Φ´1 1q1{2 q.
nÑ8

To prove (90), we need a lower bound on the quantity SpΦ´1 q ` p1T Φ´1 1q1{2 , which is similar to (78).
So far we have not been able to find a useful bound of this kind.
ACKNOWLEDGEMENT

We are grateful to our colleague Itzhak Tamo for his help with the proof of Prop. H.1.

30

Appendices
A PPENDIX A
A

CALCULUS INEQUALITY

Proposition A.1. For all x ě ´ 32 , we have the following inequality:
ˇ
x2 ˇˇ ˇˇ ˇˇ
ˇ
ˇ logp1 ` xq ´ px ´ qˇ ď ˇx3 ˇ
2
Proof. Let
ˇ
x2
x2 ˇˇ ˇˇ ˇˇ
ˇ
h1 pxq “ logp1 ` xq ´ px ´ q, and h2 pxq “ ˇ logp1 ` xq ´ px ´ qˇ ´ ˇx3 ˇ.
2
2
Then
x2
h11 pxq “
ě 0 for all x ą ´1.
x`1
Since h1 p0q “ 0, we have h1 pxq ě 0 for all x ą 0, and h1 pxq ď 0 for all ´1 ă x ă 0. Consequently,
h2 pxq “ h1 pxq ´ x3 for x ą 0, and h2 pxq “ x3 ´ h1 pxq for ´ 1 ă x ă 0.

As a result,
h12 pxq “

x2
x2
2
´ 3x2 ă 0 for x ą 0, and h12 pxq “ 3x2 ´
ě 0 for ´ ď x ă 0.
x`1
x`1
3

Since h2 p0q “ 0, we conclude that h2 pxq ď 0 for all x ě ´ 23 .
P ROOF

A PPENDIX B
P ROPOSITION V.5

OF

We need the following simple proposition about the volume of ellipsoids.
Proposition B.1. Let Λ be an s ˆ s positive definite matrix. Let tu P Rs : uT Λu ď α21 u and tu P Rs :
uT Λu ď α22 u be two ellipsoids. Then the ratio of their volumes equals pα1 {α2 qs .

Proof. Consider the ellipsoid BΛ pαq :“ tu P Rs : uT Λu ď α2 u. Let λ1 , . . . , λs be the eigenvalues of Λ,
taken with multiplicities. Since Λ is positive definite, we can diagonalize it as Λ “ P T DP , where P is
an orthogonal matrix and D “ diagpλ1 , . . . , λs q. Then
ż
ż
π s{2
|αP T D ´1{2 |dv “ αs |D ´1{2 | s
du “
VolpBΛ pαqq “
Γp 2 ` 1q
vT vď1
uT Λuďα2
s
s{2
ź ´1{2
π
,
(91)
λ
“ αs s
Γp 2 ` 1q i“1 i

where the second equality follows by a change of variable v “ α1 D 1{2 P u, and the third one uses the
expression for the volume of the unit sphere in Rs . The proposition follows immediately from (91).

Now we are ready to prove Prop. V.5.
Proof of Prop. V.5. As mentioned
before, conditional on U “ u, the random variable ti pY n q has
řk
binomial distribution Bpn, qi ` j“1 uj qij q. With this in mind, using (17) several times, we have for all
u P B1 the following upper bound:
E

k
L
”ÿ
ı
Vi ¯2 ˇˇ
n´ ÿ
uj qij ´
ˇU “ u
q
n
i“1 i j“1

31

“E
“

k
L
¯¯2 ˇ
”ÿ
ı
ÿ
n ´ ti pY n q ´
ˇ
uj qij
U
“
u
´ qi `
ˇ
q
n
j“1
i“1 i

k
k
L
¯
¯´
ÿ
ÿ
ÿ
1´
uj qij
uj qij 1 ´ qi ´
qi `
q
j“1
j“1
i“1 i

L
k
k
k
L
ˇ´
¯
¯ ÿ
ÿ
ÿ
ÿ
1 ˇˇ ÿ
1 ´
ˇ
uj qij
uj qij `
uj qij ˇ 1 ´ qi ´
qi 1 ´ qi ´
ď
ˇ
q
q
i“1 i j“1
j“1
j“1
i“1 i

“L´1`

paq

k
L ˇÿ
k
¯
ÿ
ÿ
uj qij ˇˇ´
ˇ
uj qij
ˇ
ˇ 1 ´ qi ´
qi
i“1 j“1
j“1

ď L´1`

k

n5{13

´
“ pL ´ 1q 1 `

where paq follows from (41).
For all u P B2 , we have
P pY

n

k
L ´
¯
ÿ
ÿ
uj qij
1 ´ qi ´
j“1

i“1

k ¯

n5{13

ă 2L ď 2k`1 ,

(92)

L
k
ˇ
´ÿ
¯
n´ ÿ
Vi ¯2
ˇ
P E2 |U “ uq ě P
uj qij ´
ă n1{13 ˇU “ u
q
n
i“1 i j“1

“1´P

k
L
ˇ
¯
´ÿ
Vi ¯2
n´ ÿ
ˇ
uj qij ´
ě n1{13 ˇU “ u
q
n
i“1 i j“1

2k`1
,
(93)
n1{13
where the last step follows by the Markov inequality and (92). By our assumption, PU pB1 q “ 1, so from
(20),(26), and Prop. B.1 we obtain
3pk ´ 1q{δ0
3{δ0 ¯k´1
VolpB2 q ´
,
(94)
ě1´
“ 1 ´ 1{13
P pU P B2 q “
VolpB1 q
n
n1{13
ě1´

where the inequality follows from the fact that p1 ´ xqk ě 1 ´ kx for all 0 ď x ă 1. Therefore the
inequality holds for all n ě N pk, ǫq as long as we set N pk, ǫq ą p3{δ0 q13 . Now using (93) and (94) we
obtain
ż
ż
n
n
P pY n P E2 |U “ uqfU puqdu
P pY P E2 |U “ uqfU puqdu ě
P pY P E2 q “
B2
B1
ż
´
´
2k`1 ¯
2k`1 ¯
ě 1 ´ 1{13
fU puqdu “ 1 ´ 1{13 P pU P B2 q
n
n
B2
k`1
2
` 3k{δ0
ě1´
.
n1{13
This completes the proof of Prop. V.5.
P ROOF

A PPENDIX C
P ROPOSITION V.7

OF

For every y n P E2 , there exists ũ P B2 such that
k
L
´ÿ
a
vi ¯2 ¯1{2
n´ ÿ
ũj qij ´
ă n1{26 .
hv pũq “
q
n
i“1 i j“1

(95)

32

By definition of B2 , we have
k
´ÿ

pui ´ ũi q2

i“1

¯1{2

ě

By (52),

´ř

k
2
i“1 ũi

k
´ÿ

i“1

u2i

¯1{2

¯1{2

´

ă

1
n5{13

k
´ÿ

i“1

ũ2i

´

3{δ0
n6{13 .

¯1{2

According to triangle inequality,

ąα´

1
n5{13

`

3{δ0
for all u R Bpαq.
n6{13

k
k
L
¯1{2
¯2 ¯1{2
´ÿ
´ÿ
1
3
1´ÿ
puj ´ ũj qqij
pui ´ ũi q2
ą δ0 pα ´ 5{13 q ` 6{13 for all u R Bpαq.
ě δ0
q
n
n
i“1
i“1 i j“1

As a result,
L
k
´ÿ
¯2 ¯1{2
n´ ÿ
puj ´ ũj qqij
ą δ0 n1{2 pα ´ n´5{13 q ` 3n1{26 for all u R Bpαq.
q
i
i“1
j“1

Again by triangle inequality,
k
L
´ÿ
a
vi ¯2 ¯1{2
n´ ÿ
uj qij ´
hv puq “
q
n
i“1 i j“1

k
k
L
L
¯2 ¯1{2 ´ ÿ
´ÿ
vi ¯2 ¯1{2
n´ ÿ
n´ ÿ
puj ´ ũj qqij
ũj qij ´
´
ě
q
q
n
i“1 i j“1
i“1 i j“1

(96)

ąδ0 n1{2 pα ´ n´5{13 q ` 2n1{26 for all u R Bpαq.

Combining (95) and (96), we have
a
a
hv puq ´ hv pũq ą δ0 n1{2 pα ´ n´5{13 q ` n1{26 for all u R Bpαq.

Thus we conclude that for every y n P E2 , there exists ũ P B2 such that

pBpαqqc Ď Ev pũ, δ0 n1{2 pα ´ n´5{13 q ` n1{26 q.

This completes the proof of Prop. V.7.

P ROOF

A PPENDIX D
OF P ROPOSITION V.8

We will rely on a concentration result for random Gaussian vectors.
Proposition D.1. Let Z „ N p0, Is q be a standard Gaussian random vector. We have
?
?
pα´ sq2
for all α ě s.
P p}Z}2 ě αq ď e´ 2

(97)

This is a very special case of the following general concentration inequality due to Sudakov and
Tsirel’son [20] and Borell [21] (see also Pisier and Maurey [22, page 176]). Recall that a function
f : Rs Ñ R is called ρ-Lipschitz if
|f pzq ´ f pz1 q| ď ρ}z ´ z1 }2 for all z, z1 P Rs .

Theorem D.2 ([20], [21]). For a ρ-Lipschitz function f : Rs Ñ R and a standard Gaussian random
vector Z „ N p0, Is q, the random variable f pZq satisfies the following concentration inequality:
α2

P pf pZq ´ Ef pZq ě αq ď e´ 2ρ2 for all α ě 0.

(98)

33

Proof of Prop. D.1: Take f above to be f pzq “ }z}2 for all z P Rs , and note that it is 1-Lipschitz by
the triangle inequality, so (98) holds true. We have
P p}Z}2 ´ E}Z}2 ě αq ď e´

α2
2

for all α ě 0.

By Jensen’s inequality,

Therefore,

b
b
?
E}Z}2 “ E Z12 ` ¨ ¨ ¨ ` Zs2 ď EpZ12 ` ¨ ¨ ¨ ` Zs2 q “ s.
P p}Z}2 ´

?

s ě αq ď P p}Z}2 ´ E}Z}2 ě αq ď e´

Proof of Prop. V.8. Observe that
Define the following set:

a

hpũq ě
s

a

hptq “

?

α2
2

for all α ě 0.

C for all ũ P Rs , and so Epũ, αq Ď Ept, αq.

b

Epαq “ tu P R : pu ´ tqT Φpu ´ tq ą αu.
a
a
?
Since hpuq ď pu ´ tqT Φpu ´ tq ` C for all u P Rs , we have Ept, αq Ď Epαq. Let U „ N pt, Φ´1 q
be an s-dimensional Gaussian random vector with mean vector t and covariance matrix Φ´1 . Let Z “
Φ1{2 pU ´ tq. Then Z „ N p0, Is q. Indeed, the mean vector of Z is trivially zero, and the covariance matrix
is found as
EpZZT q “ EpΦ1{2 pU ´ tqpU ´ tqT Φ1{2 q “ Φ1{2 Φ´1Φ1{2 “ Is ,
?
respectively. We obtain, for all α ě s,
ş
ş
expp´ 12 pu ´ tqT Φpu ´ tqqdu
expp´ 21 hpuqqdu
Epũ,αq
Epũ,αq
ş
ş
“
expp´ 21 hpuqqdu
expp´ 21 pu ´ tqT Φpu ´ tqqdu
Rs
Rs
“ P pU P Epũ, αqq ď P pU P Epαqq
b
“ P p pU ´ tqT ΦpU ´ tq ą αq
a
“ P p ZT Z ą αq
ď e´

?
pα´ sq2
2

.

where the last step follows by (97).

P ROOF

A PPENDIX E
S TEP (b) IN E Q . (72)

OF

Let Λ be an s ˆ s positive definite matrix, and let t be a column vector in Rs . It is easily seen that
for a Gaussian random variable X „ N pµ, σ 2 q,
c
2σ 2
.
E|X| ď |µ| `
π
Therefore, we have
c s
c ´ s
¯1{2
?
2 ÿa
2s ÿ
VarpUi q
}U}1 ď }t}1 `
VarpUi q ď s}t}2 `
π i“1
π i“1
c
?
2s
“ s}t}2 `
trpΛq
π
which is what we used to obtain the last line in (72).

34

A PPENDIX F
P ROOF OF (74)
To prove the last estimate in (74), we will show that there exists an integer N pk, ǫq such that for every
n ě N pk, ǫq and every y n P E2 ,
ż
k
¯1{2
´ÿ
1
(99)
u2i
f1 pu, y n qdu ă 7{13 .
n
pB1 qc i“1
Given y n P Yn , define Ūpy n q “ pŪ1 py n q, . . . , Ūk´1 py n qq as a pk ´ 1q-dimensional Gaussian random
vector with density function fŪpyn q p¨q “ f1 p¨, y n q, mean vector Φ´1 w and covariance matrix Φ´1 . Note
Φ´1 w depends on y n . According to (48), (49), (60), and (69),
f1 pū, y n q “ ş

expp´ 21 hv pūqq
.
expp´ 12 hv puqqdu
Rk´1

?
With this, we can use the result of Prop. V.8, taking s “ k ´ 1. Namely, for all α ě k ´ 1, ũ P Rk´1 ,
inequality (65) gives the estimate
ż
´ 1
¯
?
`
˘
n
f1 pū, y n qdū ď exp ´ pα ´ k ´ 1q2 .
P Ūpy q P Ev pũ, αq “
2
Ev pũ,αq

For a given y n P E2 , take ũ whose existence is established in Prop. V.7. Using (63), we deduce that for
every y n P E2 and α ě n´5{13
¯2 )
! 1´
?
`
˘
.
(100)
δ0 n1{2 pα ´ n´5{13 q ` n1{26 ´ k ´ 1
P Ūpy n q P pBpαqqc ď exp ´
2
?
At this point we wish to ensure that n1{26 ´ k ´ 1 ą 0. Since n is taken to be sufficiently large, in
particular, n ě N pk, ǫq, at it suffices to ensure that N pk, ǫq ą k13 , which entails no loss of generality.
Define a random variable
´ k´1
ÿ
ÿ`
˘2 ¯1{2
˘
` k´1
n
n 2
Ūi py n q
.
Z̄py q “
Ūi py q `
i“1

i“1

Observe that

tŪpy n q P pBpαqqc u “ tZ̄py n q ě αu

and thus by (100), for every y n P E2 and α ě n´5{13 ,
¯2 )
´
¯
! 1´
?
.
P Z̄py n q ě α ď exp ´
δ0 n1{2 pα ´ n´5{13 q ` n1{26 ´ k ´ 1
2
Note that this implies that limz̄Ñ8 z̄P pZ̄py n q ě z̄q “ 0. Then we have, for every y n P E2 ,
ż
ż
k
´ k´1
´ k´1
¯1{2
´ÿ
ÿ
ÿ ¯2 ¯1{2
n
2
ū2i `
ūi
fŪpyn q pūqdū
f1 pu, y qdu “
ui
pB1 qc

ūPpB1 qc

i“1

“

ż

z̄ěn´5{13

i“1

z̄fZ̄pyn q pz̄qdz̄ “

ż

i“1

ż

z̄ěn´5{13

z̄dP pZ̄py n q ě z̄q
ż
ˇ8
´
ˇ
“ ´ z̄P pZ̄py n q ě z̄qˇ ´5{13 ´
“´

(101)

z̄dP pZ̄py n q ď z̄q

z̄ěn´5{13

n

“ n´5{13 P pZ̄py n q ě n´5{13 q `

z̄ěn´5{13

ż

P pZ̄py n q ě z̄qdz̄

z̄ěn´5{13

¯

P pZ̄py n q ě z̄qdz̄ ´ lim z̄P pZ̄py n q ě z̄q
z̄Ñ8

35

¯2 ¯
´ 1´
?
n1{26 ´ k ´ 1
ď n´5{13 exp ´
2
ż
¯2 ¯
´ 1´
?
1{2
´5{13
1{26
dz̄, (102)
exp ´
`
δ0 n pz̄ ´ n
q`n
´ k´1
2
z̄ěn´5{13

where in the last two steps we used (101).
To bound the second term on the last line of (102), we interpret it as? an integral of a (univariate)
Gaussian random variable Z with mean n´5{13 ´ δ0´1 n´6{13 ` δ0´1 n´1{2 k ´ 1 and variance δ0´2 n´1 .
Then
ż
¯2 ¯
´ 1´
?
1{2
´5{13
1{26
dz̄
δ0 n pz̄ ´ n
q`n
´ k´1
exp ´
2
z̄ěn´5{13
?
?
ż
´ δ2 n ´
?
`
˘¯2 ¯
δ0 n
2π
?
“ ?
dz
exp ´ 0 z ´ n´5{13 ´ δ0´1 n´6{13 ` δ0´1 n´1{2 k ´ 1
δ0 n zěn´5{13 2π
2
?
?
¯
?
2π
2π ´
´5{13
q “ ? P Z ´ EZ ě δ0´1 n´6{13 ´ δ0´1 n´1{2 k ´ 1
“ ? P pZ ě n
δ n
δ0 n
?0
´
2
?
˘2 ¯
2π
δ n`
ď ? exp ´ 0 δ0´1 n´6{13 ´ δ0´1 n´1{2 k ´ 1
δ0 n
2
?
´
?
˘2 ¯
1`
2π
“ ? exp ´ n1{26 ´ k ´ 1 ,
(103)
δ0 n
2
where the inequality follows from the Gaussian tail bound (a one-sided version of (24)). It remains to
use (103) in (102): We obtain that for every y n P E2 ,
? ¯
ż
k
´ 1`
¯1{2
´ÿ
´ 1
?
˘2 ¯
2π
1{26
n
2
?
`
exp
´
n
´
f1 pu, y qdu ď
ui
k
´
1
2
n5{13 δ0 n
pB1 qc i“1
1
ă 7{13 ,
n
where the last inequality holds for all n ě N pk, ǫq as long as N pk, ǫq is large enough.
A PPENDIX G
B OUNDING THE INTEGRAL
Let
I :“

IN

(76)

k ´
ÿ
`
˘¯2
ui ´ E Ūi py n q f1 pu, y n qdu

ż

pB1 qc i“1

Here we prove the following bound:
There exists an integer N pk, ǫq such that for every n ě N pk, ǫq and every y n P E2 ,
Iď

Using Ūk “ ´

1

n14{13

.

řk´1

Ūi , we have
ż
k´1
ÿ
pūi ´ EpŪi py n qqq2 f1 pū, y n qdū
I“
i“1

ūPpB1 qc i“1

`

ż

ūPpB1 qc

´ k´1
¯2
ÿ
n
pūi ´ EpŪi py qqq f1 pū, y n qdū
i“1

(104)

36

ř
řm 2
2
Since p m
i“1 xi q ď m i“1 xi , we obtain
ż
k´1
¯2
ÿ´
ūi ´ EpŪi py n qq f1 pū, y n qdū
Iďk
ūPpB1 qc i“1

Since EpŪpy n qq “ Φ´1 w, we can use inequality (73) which says that for every z P Rk´1 , zT Φz ě nδ02 }z}2 .
Taking z “ pū ´ Φ´1 wq we can continue as follows:
ż
pū ´ Φ´1 wqT pū ´ Φ´1 wqf1 pū, y n qdū
Iďk
c
ūPpB1 q
ż
k
ď 2
pū ´ Φ´1 wqT Φpū ´ Φ´1 wqf1 pū, y n qdū,
(105)
nδ0 ūPpB1 qc
To bound the integral in (105), for a given α ě 0, we define another set

Ev pαq “ tu P Rk´1 : pu ´ Φ´1 wqT Φpu ´ Φ´1 wq ą αu.

Now turning to the remark after (67), we note that hv pΦ´1 wq “ C ě 0. Thus for every ũ P Rk´1 we
obtain
pu ´ Φ´1 wqT Φpu ´ Φ´1 wq “ hv puq ´ hv pΦ´1 wq
a
`a
˘2
hv puq ´ hv pũq .
ě hv puq ´ hv pũq ě

As a result, for every ũ P Rk´1 ,

Ev pũ, αq Ď Ev pα2 q,

α ě 0.

According to Prop. V.7, for every y n P E2 , there exists ũ P B2 such that pB1 qc Ď Ev pũ, n1{26 q. Therefore
for all y n P E2 , pB1 qc Ď Ev pn1{13 q. Consequently, for every y n P E2 ,
ż
pū ´ Φ´1 wqT Φpū ´ Φ´1 wqf1 pū, y n qdū
c
pB1 q
ż
pū ´ Φ´1 wqT Φpū ´ Φ´1 wqf1 pū, y n qdū
ď
Ev pn1{13 q
d
ż
´ 1
¯
|Φ|
paq
´1
T
´1
´1
T
´1
exp ´ pū ´ Φ wq Φpū ´ Φ wq dū
pū ´ Φ wq Φpū ´ Φ wq
“
p2πqk´1
2
Ev pn1{13 q
ż
´
¯
1
1
pbq
zT z exp ´ zT z dz,
“ a
(106)
2
p2πqk´1 z: zT ząn1{13

where paq follows from (71); pbq follows from the change of variable z “ Φ1{2 pū ´ Φ´1 wq and the fact
that |Φ1{2 | “ |Φ|1{2 . Let Z „ N p0, Ik´1 q be a standard Gaussian random vector. We proceed similarly
to (102):
ż
´ 1 ¯
1
a
zT z exp ´ zT z dz
2
p2πqk´1 tz: zT ząn1{13 u
ż8
adP pZT Z ď aq
“
a“n1{13
ż8
ż8
ˇ8
¯
´
ˇ
T
T
P pZT Z ą aqda
adP pZ Z ą aq “ ´ aP pZ Z ą aqˇ 1{13 ´
“´
n
n1{13
n1{13
ż8
P pZT Z ą aqda ´ lim aP pZT Z ą aq
“ n1{13 P pZT Z ą n1{13 q `
aÑ8
1{13
n
´ 1
´ 1 ?
¯ ż8
¯
paq
?
?
ď n1{13 exp ´ pn1{26 ´ k ´ 1q2 `
exp ´ p a ´ k ´ 1q2 da
2
2
n1{13

37

´ a¯
¯ ż8
1 1{26 ?
2
exp ´
da
´ k ´ 1q `
ďn
exp ´ pn
2
8
n1{13
¯
´ n1{13 ¯
´ 1
?
,
(107)
“ n1{13 exp ´ pn1{26 ´ k ´ 1q2 ` 8 exp ´
2
8
where in paq we used Prop. D.1 and the fact that limaÑ8 aP pZT Z ą aq “ 0, and in pbq we take a
sufficiently large n, greater than a suitably chosen value N pk, ǫq.
Finally, using (106) and (107) in (105), we conclude that for every y n P E2 ,
´ n1{13 ¯
¯
´ 1
?
8k
k
I ď 12{13 2 exp ´ pn1{26 ´ k ´ 1q2 ` 2 exp ´
2
8
nδ0
n
δ0
1
ă 14{13 ,
n
and this implies (104) for all n ą N pk, ǫq as long as we take a sufficiently large N pk, ǫq.
pbq

´

1{13

P ROOF

A PPENDIX H
OF P ROPOSITION V.12

In this section we prove a somewhat stronger result which immediately implies Prop. V.12.
Proposition H.1. Let A “ paij q be a pk ´ 1q ˆ pk ´ 1q positive definite matrix and let B “ A´1 . Then
ř
¯
´ řk´1 a
i‰j aij
ii
i“1
ě k ´ 1.
(108)
´
ptrpBq ` 1T B 1q
k
kpk ´ 1q

The equality holds if and only if

aij “

#

2a
a

if i “ j
otherwise.

(109)

for some a ą 0.
Proof. Let λ1 , . . . , λk´1 be the eigenvalues of A and let v1 , v2 , . . . , vk´1 be the corresponding eigenvectors. Since A ą 0, the vectors v1 , . . . , vk´1 form an orthogonal basis for Rk´1 . Let us expand the
all-ones vector in Rk´1 in this basis:
k´1
ÿ
αi vi .
1“
i“1

It is clear that

k´1
ÿ
i“1

α2i “ k ´ 1

and the coefficients αi satisfy 0 ď α2i ď k ´ 1, i “ 1, . . . , k ´ 1. Furthermore, A “
řk´1 1
T
B “ i“1
λi vi vi . We obtain
k´1
k´1
ÿ α2
ÿ 1
T
i
`
trpBq ` 1 B 1 “
λ
λ
i“1 i
i“1 i

(110)
řk´1
i“1

λi vi viT and

and since

řk´1
i“1

k

aii

´

ř

i‰j

aij

kpk ´ 1q

“

k´1
¯
´ k´1
ÿ
ÿ
trpAq
1T A1
1
λi α2i ,
λi ´
k
´
“
k ´ 1 kpk ´ 1q
kpk ´ 1q
i“1
i“1

the left-hand side of (108) can be written as
k´1
¯
´ k´1
´ k´1
ÿ
ÿ 1 ` α2 ¯´ k´1
ÿ α2 ¯´ řk´1 λi řk´1 λi α2 ¯
ÿ 1
1
i
i“1
i
i
i“1
λi pk ´ α2i q
“
`
´
λ
λ
k´1
kpk ´ 1q
kpk ´ 1q i“1 λi
i“1
i“1 i
i“1 i

38

ě

¯2
´ k´1
ÿb
1
p1 ` α2i qpk ´ α2i q
kpk ´ 1q i“1

´ k´1
ÿ ? ¯2
1
ě
k “ k ´ 1,
kpk ´ 1q i“1

(111)
(112)

where (111) follows from the Cauchy-Schwarz inequality and (112) follows from the fact that p1`xqpk ´
xq ě k for all 0 ď x ď k ´ 1. This completes the proof of (108).
It is easy to verify that the equality in (108) holds if (109) holds. Let us prove the “only if” part. Note
2
that equality in (112) holds
? only if αi “ 0 or k ´ 1 for all i “ 1, 2, . . . , k ´ 1. By (110) this means
that one
? of the αi ’s is k ´ 1, and all the other αi ’s are 0. Without loss of generality, suppose that
α1 “ k ´ 1 and αi “ 0 for 2 ď i ď k ´ 1, and thus

Moreover, if (111) holds with equality, then

1
v1 “ ?
1.
k´1

(113)

λ2k´1 pk ´ α2k´1 q
λ21 pk ´ α21 q
λ22 pk ´ α22 q
“
“
¨
¨
¨
“
1 ` α21
1 ` α22
1 ` α2k´1

and thus
λ2 “ λ3 “ ¨ ¨ ¨ “ λk´1 “

Let J˜ be a pk ´ 1q ˆ pk ´ 1q matrix given by

»

λ1 —
—
J˜ “
—
k –

λ1
.
k

ﬁ
1 1 ... 1
1 1 ... 1 ﬃ
ﬃ
.. .. .. .. ﬃ
. . . . ﬂ
1 1 ... 1

By (113), the basis vectors vi , i “ 2, 3, . . . , k ´ 1 are orthogonal to 1. This implies that
˜ i “ λ1 vi ,
pA ´ Jqv
k

i “ 2, 3, . . . , k ´ 1.

˜ i “ λ1 vi for
˜ 1 “ pk´1qλ1 v1 . Therefore, pA ´ J˜qv1 “ λ1 v1 . As a result, pA ´ Jqv
On the other hand, Jv
k
k
k
λ
all i “ 1, 2, . . . , k ´ 1. Since v1 , . . . , vk´1 span Rk´1 , we deduce that A ´ J˜ “ k1 Ik´1 , where Ik´1 is
the identity matrix. This implies that
#
2 λ1 if i “ 1, 2, . . . , k ´ 1,
aij “ λ1k
otherwise.
k

Since λ1 ą 0, this concludes the proof.
A PPENDIX I
P ROOF OF (80)
Let d˚ be as defined in (11). To prove (80), we only need to prove the following inequality:
k ´
ÿ
qij ¯2

j“1

qi

´
ď k 1 ` peǫ ´ 1q2

d˚ pk ´ d˚ q ¯
, i “ 1, 2, . . . , L.
pd˚ eǫ ` k ´ d˚ q2

(114)

39

Proof. Since Q P Dǫ,E , by definition we have

qij
P t1, eǫ u
minj 1 Prks qij 1

for all i P rLs. Given i P rLs, define
di “ |tj :

qij

“ eǫ u|.

minj 1 Prks qij 1

Then
|tj : qij “ min qij 1 u| “ k ´ di .
j 1 Prks

Therefore,
k
ÿ
` qij ˘2

j“1

qi

“ di

`

˘2
`
˘2
keǫ
k
`
pk
´
d
q
i
di eǫ ` k ´ di
di eǫ ` k ´ di

di e2ǫ ` k ´ di
pdi eǫ ` k ´ di q2
pdi e2ǫ ` k ´ di qpdi ` k ´ di q
“k
pdi eǫ ` k ´ di q2
2
2ǫ
d e ` di pk ´ di qpe2ǫ ` 1q ` pk ´ di q2
“ k i 2 2ǫ
di e ` 2di pk ´ di qeǫ ` pk ´ di q2
¯
´
di pk ´ di qpeǫ ´ 1q2
“ k 1 ` 2 2ǫ
di e ` 2di pk ´ di qeǫ ` pk ´ di q2
´
´
di
k ´ di ¯´1 ¯
“ k 1 ` peǫ ´ 1q2 2eǫ `
e2ǫ `
k ´ di
di
´
˚
paq ´
k ´ d˚ ¯´1 ¯
d
2ǫ
ǫ
ǫ
2
e `
ď k 1 ` pe ´ 1q 2e `
k ´ d˚
d˚
´
¯
˚
˚
d pk ´ d q
“ k 1 ` peǫ ´ 1q2 ˚ ǫ
,
pd e ` k ´ d˚ q2
“ k2

where paq follows directly from the definition of d˚ in (11).

A PPENDIX J
L OCAL A SYMPTOTIC N ORMALITY AND F ISHER INFORMATION MATRIX
řk´1
Let p “ pp1 , p2 , . . . , pk´1 , 1 ´ i“1
pi q be a distribution (probability mass function) on X. Denote by
n
P py ; p1 , p2 , . . . , pk´1 q the probability mass function of a random vector Y n formed of i.i.d. samples
Y piq drawn according to the distribution pQ. Recall that in the beginning of Section V, we assumed that
the output alphabet of Q is Y “ t1, 2, . . . , L1 u, and we defined t1i py n q to be the number of times that
symbol i appears in y n . Therefore,
R ELATION

TO

1

n

log P py ; p1 , p2 , . . . , pk´1 q “
“

L1
ÿ

i“1

t1i py n q log qi1 `

L1
ÿ

i“1

L
ÿ

i“1

k´1
´
ÿ `
˘¯
pj Qpi|jq ´ Qpi|kq
t1i py n q log Qpi|kq `
j“1

t1i py n q log

“ log P py n ; 1{k, 1{k, . . . , 1{kq `

´ Qpi|kq
qi1

L ÿ
ÿ

i“1 aPAi

`

k´1
ÿ

pj

j“1

t1a py n q log

´ Qpi|jq
qi1

´

´ Qpa|kq
qa1

Qpi|kq ¯¯
qi1

`

k´1
ÿ
j“1

pj

´ Qpa|jq
qa1

´

Qpa|kq ¯¯
qa1

40

“ log P py n ; 1{k, 1{k, . . . , 1{kq `

L
ÿ

i“1

ti py n q log

´q

ik

qi

`

k´1
ÿ
j“1

pj

´q

ij

qi

´

qik ¯¯
,
qi

(115)

where the last equality follows from (34) and (35). Therefore, the function gpu, y n q defined in (37) can
be written as
P py n ; 1{k ` u1 , 1{k ` u2 , . . . , 1{k ` uk´1 q
.
(116)
gpu, y n q “ log
P py n ; 1{k, 1{k, . . . , 1{kq
In Section V, one of the main steps in the proof of (19) is to approximate gpu, y n q as g2 pu, y n q.
According to (38) and (56),
k
L
k
L
L
k
´ÿ
ÿ
ÿ
uj qij
uj qij ¯2 ÿ ÿ uj qij
1ÿ
1
vi
g2 pu, y n q “
vi
“
´
´ uT Φpn, Qqu.
nqi
q
2
q
q
2
i
i
i
j“1
i“1
j“1
i“1
i“1
j“1

The observable random variables in our problem are the coordinates of Y n , and the unknown parameters
are p1 , p2 , . . . , pk´1 . Denote by Ipp1 , p2 , . . . , pk´1 q the Fisher information matrix of p vs. Y n , where
ı
” B2
log P pY n ; p1 , p2 , . . . , pk´1 q
.
(117)
rIp1{k, 1{k, . . . , 1{kqsij “ ´E
Bpi Bpj
p1 “p2 “¨¨¨“pk´1 “1{k
We claim that
Φpn, Qq “ Ip1{k, 1{k, . . . , 1{kq.
Indeed, by (117) we have

rIp1{k,1{k, . . . , 1{kqsij
L
k´1
´q
” B2 ´ ÿ
ÿ ´ qmj
qmk ¯¯¯ı
mk
n
tm py q log
pj
`
´
“ ´E
Bpi Bpj m“1
qm
qm
qm
p1 “p2 “¨¨¨“pk´1 “1{k
j“1
“E
“n

L
” ÿ

m“1
L
ÿ

tm pY n q

pqmi ´ qmk qpqmj ´ qmk q ı
2
qm
p1 “p2 “¨¨¨“pk´1 “1{k

pqmi ´ qmk qpqmj ´ qmk q
,
qm
m“1

where the first step follows from (115). Comparing this with (55), we can easily see that Φpn, Qq “
Ip1{k, 1{k, . . . , 1{kq. Furthermore, it is also easy to check that
k
L
k´1
ˇ
¯
ÿ
ÿ
ÿ ´ B
uj qij
ˇ
vi
ui
.
“
log P py n ; p1 , p2 , . . . , pk´1 qˇ
qi
Bpi
p1 “p2 “¨¨¨“pk´1 “1{k
j“1
i“1
i“1

Therefore,

g2 pu, y n q “

k´1
ÿ
i“1

ui

ˇ
´ B
¯ 1
ˇ
´ uT Ip1{k, 1{k, . . . , 1{kqu.
log P py n ; p1 , p2 , . . . , pk´1 qˇ
Bpi
2
p1 “p2 “¨¨¨“pk´1 “1{k

Combining this with (116), we conclude that gpu, y n q « g2 pu, y n q for small u can be written as
P py n ; 1{k ` u1 , 1{k ` u2 , . . . , 1{k ` uk´1 q
log
P py n ; 1{k, 1{k, . . . , 1{kq
k´1
ˇ
¯ 1
ÿ ´ B
ˇ
ui
«
´ uT Ip1{k, 1{k, . . . , 1{kqu.
log P py n ; p1 , p2 , . . . , pk´1 qˇ
Bp
2
p1 “p2 “¨¨¨“pk´1 “1{k
i
i“1

This relation is a classic form of expressing Le Cam’s result on local asymptotic normality (see [16,
Chapter 2, Theorem 1.1]). As we already remarked in Sec. III, we could use this result to give a simpler
proof that a relation of the form (16) holds for an individual privatization scheme Q; however along this
route there seems to be no immediate way to establish the uniform bound (16).

41

R EFERENCES
[1] C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” in Theory of
Cryptography Conference. Springer, 2006, pp. 265–284.
[2] C. Dwork, “Differential privacy: A survey of results,” in International Conference on Theory and Applications of Models
of Computation. Springer, 2008, pp. 1–19.
[3] A. Ghosh, T. Roughgarden, and M. Sundararajan, “Universally utility-maximizing privacy mechanisms,” SIAM Journal on
Computing, vol. 41, no. 6, pp. 1673–1693, 2012.
[4] J. C. Duchi, M. I. Jordan, and M. J. Wainwright, “Local privacy and statistical minimax rates,” in 54th Annual IEEE
Symposium on the Foundations of Computer Science (FOCS), 2013, pp. 429–438.
[5] S. Kamath, A. Orlitsky, V. Pichapati, and A. T. Suresh, “On learning distributions from their samples,” Jounral of Machine
Learning Research: Workshop and Conference Proceedings, vol. 40, pp. 1–35, 2015.
[6] E. L. Lehmann and G. Casella, Theory of point estimation. Springer Science & Business Media, 2006.
[7] J. Duchi, M. J. Wainwright, and M. I. Jordan, “Local privacy and minimax bounds: Sharp rates for probability estimation,”
in Advances in Neural Information Processing Systems, 2013, pp. 1529–1537.
[8] Ú. Erlingsson, V. Pihur, and A. Korolova, “RAPPOR: Randomized aggregatable privacy-preserving ordinal response,”
in Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2014, pp.
1054–1067.
[9] S. L. Warner, “Randomized response: A survey technique for eliminating evasive answer bias,” Journal of the American
Statistical Association, vol. 60, no. 309, pp. 63–69, 1965.
[10] P. Kairouz, S. Oh, and P. Viswanath, “Extremal mechanisms for local differential privacy,” Jounral of Machine Learning
Research, vol. 17, pp. 1–51, 2016.
[11] P. Kairouz, K. Bonawitz, and D. Ramage, “Discrete distribution estimation under local privacy,” in Proc. 33rd Int. Conf.
Machine Learning, 2016, arXiv:1602.07387.
[12] S. Wang, L. Huang, P. Wang, Y. Nie, H. Xu, W. Yang, X. Li, and C. Qiao, “Mutual information optimally local private
discrete distribution estimation,” 2016, arXiv:1607.08025.
[13] M. Ye and A. Barg, “Optimal schemes for discrete distribution estimation under locally differential privacy,” 2017,
arXiv:1702.00610.
[14] J. C. Duchi, M. I. Jordan, and M. J. Wainwright, “Minimax optimal procedures for locally private estimation,” 2016,
arXiv:1604.02390.
[15] L. Le Cam, Asymptotic methods in statistical decision theory. Springer Science & Business Media, 2012.
[16] I. A. Ibragimov and R. Z. Has’minskii, “Statistical estimation,” 1981.
[17] J. Hájek, “Local asymptotic minimax and admissibility in estimation,” in Proceedings of the sixth Berkeley symposium on
mathematical statistics and probability, vol. 1, 1972, pp. 175–194.
[18] R. Wong, Asymptotic approximations of integrals. SIAM, 2001.
[19] B. Yu, “Assouad, Fano, and Le Cam,” in Festschrift for Lucien Le Cam. Springer, 1997, pp. 423–435.
[20] V. N. Sudakov and B. S. Tsirel’son, “Extremal properties of half-spaces for spherically invariant measures,” Journal of
Soviet Mathematics, vol. 9, no. 1, pp. 9–18, 1978, translated from Zap. Nauch. Sem., 41, 14-24, 1974.
[21] C. Borell, “The Brunn-Minkowski inequality in Gauss space,” Inventiones Mathematicae, vol. 30, no. 2, pp. 207–216,
1975.
[22] G. Pisier, “Probabilistic methods in the geometry of Banach spaces,” in Probability and analysis. Springer, 1986, pp.
167–241.

