# Mode Estimation with Partial Feedback

Charles Arnal* Vivien Cabannes* Vianney Perchet  Datashape, Inria, Saclay,
France  Fundamental Artificial Intelligence Research (FAIR), Meta AI, New
York, USA  Center for Research in Economics and Statistics (CREST), ENSAE,
Palaiseau, France

###### Abstract

The combination of lightly supervised pre-training and online fine-tuning has
played a key role in recent AI developments. These new learning pipelines call
for new theoretical frameworks. In this paper, we formalize core aspects of
weakly supervised and active learning with a simple problem: the estimation of
the mode of a distribution using partial feedback. We show how entropy coding
allows for optimal information acquisition from partial feedback, develop
coarse sufficient statistics for mode identification, and adapt bandit
algorithms to our new setting. Finally, we combine those contributions into a
statistically and computationally efficient solution to our problem.

62L05,

62B86,

62D10,

62B10,

Active Learning,

Partial Feedback,

Entropy Coding,

Coarse Search,

Best Arm Identification,

###### keywords:

[class=MSC]

###### keywords:

**footnotetext: These authors contributed equally to this work.

, and

###### Contents

  1. 1 Introduction
    1. 1.1 The Mode Estimation with Partial Feedback Problem
    2. 1.2 Related Work
    3. 1.3 Performance Metrics
    4. 1.4 Summary of Contributions
  2. 2 The Empirical Mode Estimator
    1. 2.1 Proof of Theorem 1
    2. 2.2 Minimax Optimality
  3. 3 Exhaustive Dichotomic Search Procedures
    1. 3.1 Entropy Coding
    2. 3.2 Exhaustive Search with Fixed Coding
    3. 3.3 Exhaustive Search with Adaptive Coding
    4. 3.4 Proofs
  4. 4 Truncated Search
    1. 4.1 Coarse Sufficient Statistics
    2. 4.2 Adaptive Truncated Search
    3. 4.3 Proofs
  5. 5 Bandit-Inspired Elimination
    1. 5.1 Design of the elimination schedule
    2. 5.2 Proofs
  6. 6 Set Elimination
    1. 6.1 Proofs
  7. .2 Information Projection Computation
  8. .3 Additional Proofs for Section 3
  9. .4 Additional Proofs for Section 4
  10. .5 Additional Proofs for Section 5
  11. .6 Additional Proofs for Section 6

##  1 Introduction

The mode of a distribution is a fundamental concept in statistics, serving as
a key identifier for the most likely event to occur. For instance, identifying
modes of conditional distributions is the main task of classification
algorithms –classification consists in learning the mapping
$f^{*}(x)=\operatorname*{arg\,max}_{y}p(y\,|\,x)$ for a joint distribution $p$
over inputs $x$ and classes $y$. Traditionally, datasets were small enough to
fully annotate samples before learning the modes of the underlying
distributions. However, with the increasing scale of machine learning
problems, data collection has become a significant part of machine learning
pipelines. This is illustrated by the substantial efforts dedicated to data
preprocessing to train foundational AI models (see, e.g., OpenAI, 2023;
Touvron et al., 2023). Moreover, it is foreseeable that future models will
incorporate annotation feedback loops. Indeed, fine-tuning foundational models
already relies on various active learning strategies, such as reinforcement
learning with human feedback (Ziegler et al., 2020) and partial annotations
(Zhu, Jordan and Jiao, 2023). This makes theories of weakly-supervised, and
active learning highly relevant to the machine learning community. This paper
introduces one of the simplest setups to combine active and weakly-supervised
learning. It focuses on partial annotations, and searches for the best
algorithms to identify the mode of a distribution given a budget of
annotations.

###  1.1 The Mode Estimation with Partial Feedback Problem

The task at hand is the identification of the mode of a distribution $p\in
P({\mathcal{Y}})$, where ${\mathcal{Y}}$ is a set of $m$ elements or classes,
through partial feedback. Let us denote as
${\mathcal{Y}}=\left\\{y_{1},\ldots,y_{m}\right\\}$ this set of classes, and
assume that the $m$ elements $y_{1},\ldots,y_{m}$ are indexed by decreasing
probability, i.e. $p(y_{i})\geq p(y_{i+1})$ for any $i<m$. The goal is to find
the most probable value $y_{1}$ of ${\mathcal{Y}}$, which we assume to be
unique for simplicity, i.e.

$y_{1}=\operatorname*{arg\,max}_{y\in{\mathcal{Y}}}{\mathbb{P}}_{Y\sim
p}(Y=y).$ (1)

To estimate the mode, we assume the existence of independent samples $(Y_{j})$
distributed according to $p$. However, the practitioner does not directly
observe the samples; instead, they can sequentially acquire weak information
on them. Formally, at each time $t\in{\mathbb{N}}$, the practitioner selects
an index $j_{t}\in{\mathbb{N}}$ and a set of potential labels
$S_{t}\subset{\mathcal{Y}}$, and ask whether the sample $Y_{j_{t}}$ belongs to
$S_{t}$ or not, leading to the observation of the binary variable

$\mathbf{1}_{Y_{j_{t}}\in S_{t}}.$ (2)

We call the process of checking whether $Y_{j_{t}}\in S_{t}$ a query, leading
to the following problem description:

######  Problem 1.

Design a sequence of queries $(\mathbf{1}_{Y_{j_{t}}\in S_{t}})$ to
efficiently estimate the mode of $p$, where each query
$\mathbf{1}_{Y_{j_{t}}\in S_{t}}$ can depend on the previous observations of
$(\mathbf{1}_{Y_{j_{s}}\in S_{s}})_{s<t}$.

The overarching objective is to design and analyze efficient algorithms that
output a good estimate of the mode using a minimal number of queries. Although
real-world applications often come with peculiarities, Problem 1 is generic
enough that its resolution should shed light on a large variety of online
learning tasks with partial feedback.

Among possible variants of Problem 1, one could forbid the experimenter from
asking more than one query per sample, i.e. forcing $j_{t}=t$, add a
contextual variable $X\in{\mathcal{X}}$ that conditions the distribution of
$\mathbf{1}_{Y\in S}$, assume that some queries are cheaper to make than
others, or consider cases where random noise affects the observations
$\mathbf{1}_{Y\in S}$. Rather than the mode $y_{1}$ of the distribution $p$,
we may want to identify instead one or all the classes $y$ such that $p(y)\geq
p(y_{1})-\epsilon$ for some $\epsilon>0$. Finally, more structure could be
added to the set ${\mathcal{Y}}$, rather than let it be a collection of
unrelated classes without any meaningful interactions. In particular, the
queried sets $S$ could be restricted to belong to some predefined collection
of sets ${\mathcal{S}}$ –e.g., each class in ${\mathcal{Y}}$ represents an
animal species, and you can ask whether the animal $Y$ is a feline, but not
whether it belongs to $\\{$cat, wolf, common snapping turtle$\\}$. More
generally, the observation of $\mathbf{1}_{Y\in S}$ could be replaced by a
random variable $F(Y,S)$ for some function $F$, so that $F(Y,S)$ need not be
discrete or equal to $\sum_{y\in S}F(Y,S)$.

Problem 1 and its variations appear in many contexts. A natural illustration
would be a content-providing service, such as a social network app with a
scrolling-centric interface, that tries to identify which type of content the
user is most likely to like from a collection ${\mathcal{Y}}$ of possible
topics. The app shows a batch of posts or videos to the user (which
corresponds to the choice of a set $S$), and receives some measure of user
satisfaction in return (such as their scrolling time); from this information,
the app must design future batches of content and find the user’s favourite
topics. Another natural example comes from advertising: a hotel can compose
online ads using various combinations of pictures from a set ${\mathcal{Y}}$
of photos of a given room. Each combination corresponds to a set $S$, and the
variable $\mathbf{1}_{Y\in S}$ is equal to $1$ when online visitor $Y$ clicks
on the ad. The hotel tries to identify which pictures maximize the chances of
the ad being clicked. Similar situations can also arise in experimental
sciences: a biologist tries to understand which genes $y$ in a collection
${\mathcal{Y}}$ of genes considered have the strongest effect on a certain
property. To that end, they can test whether activating a set $S$ of genes
results in the expression of the property.

###  1.2 Related Work

In terms of related problems, Problem 1 bears resemblances to the active
labeling framework introduced by Cabannes et al. (2022). This framework was
motivated by dynamic pricing (Cesa-Bianchi, Cesari and Perchet, 2019), active
ranking (Jamieson and Nowak, 2011; Braverman, Mao and Peres, 2019), and
hierarchical classification (Cesa-Bianchi, Gentile and Zaniboni, 2006;
Gangaputra and Geman, 2006). Additionally, a clear connection can be drawn
with the well-studied task of best-arm identification in multi-armed bandit
settings (Bubeck, Munos and Stoltz, 2010),111The connection is apparent if we
force $i_{t}=t$ and $S_{t}$ to be a singleton for every $t\in{\mathbb{N}}$.
particularly in the context of combinatorial bandits (Chen et al., 2016) and
even more precisely of transductive linear bandits (Fiez et al., 2019).

In terms of techniques, our algorithms draw their inspirations from the
entropic coding schemes of Huffman (1952) and Vitter (1987), the elimination
algorithm of Even-Dar, Mannor and Mansour (2006), together with the doubling
trick of Auer et al. (1995). Finally, we notice that the expectation-maximum
(EM) algorithm of Dempster, Laird and Rubin (1977) was notably motivated by
the estimation of probability from partial observations, although we did not
pursue their approximate Bayesian approach.

Philosophically, our approach was motivated by the fact that Kolmogorov
capacity, hence entropy coding, lies at the heart of statistical learning
theory (see, e.g., Cucker and Smale (2002), as well as Grünwald (2007)),
suggesting that a contextual version of our setup might provide insightful
perspectives on active learning.

###  1.3 Performance Metrics

Various performance metrics can be applied to algorithms that output a guess
$\hat{y}$ of the mode of $p$ after a certain number of queries. We will focus
on the probability of error, i.e., on the minimal $\delta$ such that

${\mathbb{E}}[\mathbf{1}_{\hat{y}\neq y_{1}}]={\mathbb{P}}(\hat{y}\neq
y_{1})\leq\delta,$ (3)

as a function of the number of queries $T$. Here, the randomness is inherited
from that of the samples $(Y_{j})$ and of the algorithm. Equation (3) can be
seen as the “risk” associated with the “zero-one loss”, which is used in
classification problems. Other reasonable metrics include the expected
difference ${\mathbb{E}}[p(y_{1})-p(\hat{y})]$, or the probability of
$\epsilon$-approximate success ${\mathbb{P}}(p(\hat{y})\geq
p(y_{1})-\epsilon)$. Despite those variations, the principles behind our
algorithms can be readily adapted to different metrics.

Among additional nuances, in some contexts, a user might fix in advance a
“confidence” level $\delta$, and be interested in algorithms that minimize the
(expected) number of queries $T$ to achieve it. Reciprocally, one might fix a
“budget” of queries $T$, and design algorithms that minimize the probability
$\delta$ of false prediction using those queries. These settings typically
lead to equations of the shape

${\mathbb{E}}[T]\leq\ln(C_{1}/\delta)\alpha_{1},\qquad\text{or
respectively}\qquad\delta\leq C_{2}\exp(-T/\alpha_{2}),$ (4)

where the constants $\alpha_{i}$ and $C_{i}$ depend on the unknown
distribution $p$. Once again, algorithm design principles are often agnostic
to the settings differentiation, usually allowing the conversion of one type
of bound into the other. To offer quantitative comparisons, we focus on the
joint asymptotic behavior with respect to $\delta$ and $T$, which is
determined by the constants $\alpha$, removing $C$ from the picture. This
provides a simple metric: the smaller $\alpha$, the better the algorithm.

Note that our proofs also yield guarantees on the sample complexity of our
algorithms; however, the expected number of queries required is a more
relevant quantity, as it captures both the sample efficiency of an algorithm
and the efficiency with which it extracts the necessary information from each
sample, which is a key aspect of our setting.

###  1.4 Summary of Contributions

| Exhaustive Search Algorithm 3
---
$\Delta_{2}^{-2}+\Delta_{2}^{-2}\log_{2}(m)$
|
$\downarrow$ |  |
| Adaptive Search Algorithm 4
---
$\Delta_{2}^{-2}+\Delta_{2}^{-2}\left(\sum_{i\geq
1}p(y_{i})\left|\log_{2}p(y_{i})\right|\right)$
$\longrightarrow$ |  | Elimination Algorithm 8
---
$\Delta_{2}^{-2}+\sum_{i\geq
1}p(y_{i})\Delta_{i}^{-2}\left|\log_{2}p(y_{i})\right|$
$\downarrow$ |  | $\downarrow$
| Truncated Search Algorithm 7
---
$\Delta_{2}^{-2}+\Delta_{2}^{-2}\left|\log_{2}p(y_{1})\right|$
$\longrightarrow$ |  | Set Elimination Algorithm 9
---
$\Delta_{2}^{-2}+\left(\sum_{i\geq
1}p(y_{i})\Delta_{i}^{-2}\right)\left|\log_{2}p(y_{1})\right|$
Table 1:  Summary of the coefficient $\alpha$ as per (4) found for different
methods, up to universal constants when $p(y_{1})$ is bounded away from $1$,
and with $\Delta_{1}=\Delta_{2}$. The arrows indicate improvements.

Our first contribution is to introduce a new problem, Problem 1, which
captures key aspects of most online learning tasks with partial feedback. It
is simple enough to allow for rigorous theory to be developed, yet naturally
generalizes to match practical scenarios from the real world. We introduce
several important ideas to efficiently solve Problem 1, which lead to
increasingly refined algorithms, whose performances can be compared in terms
of the coefficient $\alpha$ introduced in (4). An outline is provided in Table
1, up to universal multiplicative constants. Though each algorithm is
discussed in detail later in the article, let us introduce them here.

The most naive one, the Exhaustive Search Algorithm 3, consists in fully
identifying each sample $Y_{j}$ through binary search. At any time $t$, it
outputs the most frequent class among the identified samples as an estimation
of the true mode. For a tolerated probability of error $\delta\in(0,1]$ and a
class $y_{i}\in{\mathcal{Y}}$, a number of samples proportional to
$\Delta_{i}^{-2}\ln(1/\delta)$ is needed to correctly identify $y_{1}$ as the
mode among $\\{y_{1},y_{i}\\}$, where

$\Delta_{i}^{2}:=-\ln\Big{(}1-(\sqrt{p(y_{1})}-\sqrt{p(y_{i})})^{2}\Big{)}.$
(5)

Unsurprisingly, $\Delta_{i}^{-2}$ is increasing with $p(y_{i})\in[0,p(y_{1}))$
and grows infinitely large when $p(y_{i})$ get closer to $p(y_{1})$. The
probability of error of Algorithm 3 is dominated by the probability of
mistakenly picking the second most likely candidate $y_{2}$ as the mode,
leading to the asymptotic performance
$\alpha=\Delta_{2}^{-2}\left\lceil\log_{2}(m)\right\rceil$, as detailed in
Section 3. It can be improved by identifying new samples with an entropy-based
dichotomic search that uses a learned empirical distribution $\hat{p}$ on
${\mathcal{Y}}$, which yields Algorithm 5. Asymptotically, it replaces the
$\log_{2}(m)$ queries per sample of Algorithm 3 by an expected number of
queries equal to the entropy $H(p):=\sum_{i\geq
1}p(y_{i})\left|\log_{2}(p(y_{i}))\right|\leq\log_{2}(m)$ of $p$, plus one
query per sample due to some boundary effects, as reflected in Table 1 and as
explained in Subsection 3.3. Showing how online learning with partial feedback
benefits from entropy coding is our second contribution.

There are two disjoint ways to further improve Algorithm 5. The first one
exploits the main characteristic of our problem: the possibility of asking for
partial information on samples at a lower cost than for complete
identification. In particular, when searching for the mode by identifying
samples with entropy-based techniques using Huffman trees, one can stop the
identification procedure at roughly the depth of the mode in the tree, as
classes that are deeper in the tree are unlikely candidates. This idea leads
to the design of the Truncated Search Algorithm 7, detailed in Section 4. It
reduces the asymptotic number of queries per sample from a constant plus the
average depth of leaves in a Huffman tree $H(p)$ to a constant plus the
minimal depth $\left|\log_{2}(p(y_{1}))\right|$, as seen in Table 1. The
second amelioration comes from the adaptation of bandit algorithms to our
setting. We develop in Section 5 the Elimination Algorithm 8, that discards
mode candidates as soon as they seem unlikely to be the true mode. The class
$y_{i}\in{\mathcal{Y}}$ can be eliminated after roughly
$\Delta_{i}^{-2}\ln(1/\delta)$ samples, leading to an asymptotic performance
$\alpha\simeq\Delta_{2}^{-2}+\sum_{i\geq
1}\Delta_{i}^{-2}\,p(y_{i})\left|\log_{2}(p(y_{i}))\right|$, with the abuse of
notation $\Delta_{1}^{-2}:=\Delta_{2}^{-2}$.

While Algorithms 7 and 8 are both improvements over the Adaptive Exhaustive
Search Algorithm 5, neither is strictly better than the other. When
$p(y_{1})-p(y_{2})$ is very small compared to the other gaps
$p(y_{1})-p(y_{i})$, the advantage goes to the Elimination
Algorithm,222Consider the distribution $p(y_{1})=2/m$, $p(y_{2})=2/m-1/m^{2}$
and $p(y)=(1-p(y_{1})-p(y_{2}))/(m-2)$ for all other
$y\in{\mathcal{Y}}=\\{y_{1},\ldots,y_{m}\\}$. Then $\alpha_{E}=\sum_{i\geq
1}\Delta_{i,*}^{-2}\,p(y_{i})\left|\log_{2}(p(y_{i}))\right|=O(\alpha_{TS}/m)$
as $m\rightarrow\infty$.  while it goes to the Truncated Search Algorithm when
there are many $y\in{\mathcal{Y}}$ with small mass $p(y)\ll p(y_{1})$ and
$p(y_{1})-p(y_{2})$ is not too small.333Consider the distribution
$p(y_{1})=1/2$ and $p(y)=1/(2(m-1))$ for all other
$y\in{\mathcal{Y}}=\\{y_{1},\ldots,y_{m}\\}$. Then
$\alpha_{E}\rightarrow\infty$ while $\alpha_{TS}=\sum_{i\geq
1}\Delta_{2}^{-2}\,p(y_{i})\left|\log_{2}(p(y_{1}))\right|=O(1)$ as
$m\rightarrow\infty$.  We combine the ideas of each algorithm and get the best
of both worlds with the Set Elimination Algorithm 9, presented in Section 6,
which can be understood either as grouping together low mass classes before
applying an elimination procedure to the resulting partitions, or as refining
the truncated search procedure by taking into account confidence intervals.
This is reflected in the corresponding coefficient
$\alpha=\Delta_{2}^{-2}+\sum_{i\geq
1}\Delta_{i}^{-2}\,p(y_{i})\left|\log_{2}(p(y_{1}))\right|$, where the number
of samples $\Delta_{i}^{-2}$ is as for the Elimination Algorithm, while the
expected number of queries needed for each sample
$1+\left|\log_{2}(p(y_{1}))\right|$ comes from the Truncated Search Algorithm,
resulting in the best asymptotic performance among the proposed algorithms.
_This sophisticated solution to Problem 1, together with its implementation
available online, is our final contribution_.

In conclusion, our main contributions are summarized as follows.

  1. 1.

Introducing the problem of mode estimation with partial feedback, Problem 1.

  2. 2.

Unveiling links between adaptive entropy coding and active learning.

  3. 3.

Combining adaptive entropy coding, coarse search procedures and bandits-
inspired principles into Algorithm 9, an intuitive yet efficient solution to
Problem 1.

Last but not least, we provide a code base to help researchers advance our
knowledge of weakly supervised online learning, available at
www.github.com/VivienCabannes/mepf.

##  2 The Empirical Mode Estimator

In the first part of this article, we will design mode estimation algorithms
that fully identify each sample $Y_{j}$ one after the other. Given the
identification of $n$ samples, those algorithms estimate the mode of $p$ as
the empirical mode among the $n$ samples,

$\hat{y}_{n}:=\operatorname*{arg\,max}_{y\in{\mathcal{Y}}}\sum_{j\in[n]}\mathbf{1}_{Y_{j}=y},$
(6)

with ties broken arbitrarily. A tight characterization of the performance of
the estimator (6) is offered by the following theorem.

######  Theorem 1 (Empirical mode performance).

Let $(Y_{j})_{j\in[n]}$ be $n$ independent variables sampled according to
$p\in P({\mathcal{Y}})$. Then the probability of error of (6) satisfies

$\exp\left(-n\Delta_{2}^{2}-m\ln(n+1)-c_{p}\right)\leq{\mathbb{P}}(\hat{y}_{n}\neq
y_{1})\leq\exp\left(-n\Delta_{2}^{2}\right).$ (7)

where $\Delta_{2}$ is defined in Eq. (5), and $c_{p}$ is some constant that
depends on $p$.

When accessing $n$ samples, the performance of empirical mode $\hat{y}_{n}$
cannot be bested without additional information on $p$, which leads to the
following corollary.

######  Corollary 2 (Minimax lower bound).

For any distribution $p_{0}\in P({\mathcal{Y}})$, and any algorithm
${\mathcal{A}}$ that predicts $\hat{y}:={\mathcal{A}}((Y_{j})_{j\in[n]})$
based on $n$ observations $(Y_{j})$, there exists a permutation
$\sigma\in\mathfrak{S}_{m}$ such that, when the data are generated according
to $p\in P({\mathcal{Y}})$ defined through the formula
$p(y)=p_{0}(\sigma(y))$, the lower bound (7) holds for this algorithm.

As one needs at least a single query per sample to gain any meaningful
information, Corollary 2 states that the number of queries $T$ need to be
greater than $\Delta_{2}^{-2}\ln(1/\delta)$, up to higher order terms, to
reach precision $\delta$ as defined by Equation (3). The main challenge is
thus to get as close to this lax lower bound as possible.

###  2.1 Proof of Theorem 1

In this subsection, we prove Theorem 1. We follow a proof of Sanov’s theorem
due to Csiszár and Körner (2011), together with an explicit computation of an
information projection. Let us partition all possible sequences of
observations $(Y_{j})_{j\in[n]}$ according to their empirical distribution
defined as

$\hat{p}_{(Y_{j})}(y):=n^{-1}\sum_{j\in[n]}\mathbf{1}_{Y_{j}=y}.$

To do so, we define for any such empirical distribution $q\in
P({\mathcal{Y}})\cap n^{-1}\cdot{\mathbb{N}}^{\mathcal{Y}}$ the type class

${\mathcal{T}}(q)=\left\\{(y_{t})\in{\mathcal{Y}}^{n}\,\middle|\,\mathopen{}\forall\,y\in{\mathcal{Y}};\quad\hat{p}_{(y_{t})}(y)=q(y)\right\\}.$

The event $\\{\hat{y}_{n}\neq y_{1}\\}$ is the union over all the values that
$\hat{p}$ can take of the events “$\hat{p}$ does not have the right mode”,
which we can write as a union of disjoint events according to the type of
$(Y_{j})$, which leads to the bound

$\sum_{q\in{\mathcal{Q}}_{n,-}}{\mathbb{P}}_{(Y_{j})\sim
p}\big{(}(Y_{j})\in{\mathcal{T}}(q)\big{)}\leq{\mathbb{P}}_{(Y_{j})_{j\in[n]}}(\hat{y}\neq
y_{1})\leq\sum_{q\in{\mathcal{Q}}_{n,+}}{\mathbb{P}}_{(Y_{j})\sim
p}\big{(}(Y_{j})\in{\mathcal{T}}(q)\big{)},$

where we account for the cases where $\hat{p}$ has several modes by
differentiating

${\mathcal{Q}}_{n,-}=\left\\{q\in P({\mathcal{Y}})\cap
n^{-1}\cdot{\mathbb{N}}^{\mathcal{Y}}\,\middle|\,\mathopen{}y_{1}\notin\operatorname*{arg\,max}q(y)\right\\},$
(8)

and

${\mathcal{Q}}_{n,+}=\left\\{q\in P({\mathcal{Y}})\cap
n^{-1}\cdot{\mathbb{N}}^{\mathcal{Y}}\,\middle|\,\mathopen{}\operatorname*{arg\,max}q(y)\neq\operatorname*{arg\,max}p(y)\right\\}.$
(9)

We would like to enumerate the different classes in the previous sums, as well
as their probability. A few lines of derivations lead to the equality,

${\mathbb{P}}((Y_{j})=(z_{j}))=2^{-n(H(\hat{p}_{(z_{j})})+D(\hat{p}_{(z_{j})}\|p))}.$

Here, $D$ is the Kullback-Leibler divergence, and $H$ the entropy

$D(q\|p)={\mathbb{E}}_{Y\sim q}[\log_{2}(\frac{q(Y)}{p(Y)})],\qquad
H(q)={\mathbb{E}}_{Y\sim q}[-\log_{2}(q(Y))].$

As a consequence, using the exchangeability of the $(Y_{j})$,

${\mathbb{P}}((Y_{j})\in{\mathcal{T}}(q))={\mathbb{P}}(\hat{p}_{(Y_{j})}=q)=\left|{\mathcal{T}}(q)\right|2^{-n(H(q)+D(q\|p))}.$

We are left with the computation of the cardinality of each
${\mathcal{T}}(q)$. This is nothing but

$\left|{\mathcal{T}}(q)\right|=\binom{n}{(nq(y))_{y\in{\mathcal{Y}}}}=\frac{n!}{\prod_{y\in{\mathcal{Y}}}(nq(y))!}.$

This cardinality can be bounded with probabilistic arguments, as shown in
Theorem 11.1.3 (which is 12.1.3 in the 2nd edition) of Cover and Thomas
(1991),444Slightly tighter bounds can be derived from the fact that, as proven
by Robbins (1955),  $k!=\sqrt{2\pi}k^{k+1/2}e^{-k+r_{k}},\quad\text{with}\quad
0\leq\frac{1}{12k+1}\leq r_{k}\leq\frac{1}{12k}\leq 1.$

$(n+1)^{-m}2^{nH(q)}\leq\left|{\mathcal{T}}(q)\right|\leq 2^{nH(q)}.$

Collecting the different pieces so far, we reach the conclusion,

$(n+1)^{-m}\sum_{q\in{\mathcal{Q}}_{n,-}}2^{-nD(q\|p)}\leq{\mathbb{P}}(\hat{y}\neq
y_{1})\leq\sum_{q\in{\mathcal{Q}}_{n,+}}2^{-nD(q\|p)}.$

From there, using the fact that the cardinality of ${\mathcal{Q}}_{n,+}$ is at
most $(n+1)^{m}$, we get the rough bound

$(n+1)^{-m}\max_{q\in{\mathcal{Q}}_{n,-}}2^{-nD(q\|p)}\leq{\mathbb{P}}(\hat{y}\neq
y_{1})\leq(n+1)^{m}\max_{q\in{\mathcal{Q}}_{n,+}}2^{-nD(q\|p)}.$ (10)

It is useful to define the “limit” ${\mathcal{Q}}=\left\\{q\in
P({\mathcal{Y}})\,\middle|\,\mathopen{}\operatorname*{arg\,max}q(y)\neq\operatorname*{arg\,max}p(y)\right\\}$
of the sets ${\mathcal{Q}}_{n,-}$ and ${\mathcal{Q}}_{n,+}$. We are left with
the computation of the so-called “information projections”
$\min_{q\in{\mathcal{Q}}_{n,-}}D(q\|p)$ and
$\min_{q\in{\mathcal{Q}}_{n,+}}D(q\|p)$.

######  Lemma 1.

For any distribution $p\in P({\mathcal{Y}})$, there exists a constant $c_{p}$
such that for any $n\in{\mathbb{N}}$ with ${\mathcal{Q}}_{n,-}$ and
${\mathcal{Q}}_{n,+}$ defined by Equations (8) and (9),

$\frac{\Delta_{2}^{2}}{\ln(2)}+\frac{c_{p}}{n\ln(2)}\geq\min_{q\in{\mathcal{Q}}_{n,-}}D(q\|p)\geq\min_{q\in{\mathcal{Q}}_{n,+}}D(q\|p)\geq\min_{q\in{\mathcal{Q}}}D(q\|p)=\frac{\Delta_{2}^{2}}{\ln(2)}.$

This lemma is proved in Appendix .2. Combining it with Equation (10), we find
that

$\exp\left(-n\Delta_{2}^{2}-c_{p}-m\ln(n+1)\right)\leq{\mathbb{P}}(\hat{y}\neq
y_{1})\leq\exp\left(-n\Delta_{2}^{2}+m\ln(n+1)\right).$

Finally, we note that an argument of Dinwoodie (1992) shows that
$\ln({\mathbb{P}}(\hat{y}_{n}\neq y))/n$ is always below its limit proved by
Sanov (1957), which yields the stronger bound

${\mathbb{P}}(\hat{y}\neq y_{1})\leq\exp(-n\Delta_{2}^{2})$

which we reported in Theorem 1.

###  2.2 Minimax Optimality

This subsection proves Corollary 2. To turn Theorem 1 into the minimax
Corollary 2, we can use a prior on $p$ such that the optimal Bayesian
algorithm is the mode estimation algorithm. To do so, let us endow the simplex
$P({\mathcal{Y}})$ with a distribution $D$ and try to minimize

${\mathcal{E}}({\mathcal{A}})={\mathbb{E}}_{p\sim
D}\left[{\mathbb{E}}_{(Y_{j})}\left[\mathbf{1}_{{\mathcal{A}}((Y_{j}))\neq
y^{*}_{p}}\,\middle|\,\mathopen{}p\right]\right],$

where ${\mathcal{A}}((Y_{j}))$ is the mode predicted by an algorithm
${\mathcal{A}}$ upon observing the independent samples $(Y_{j})$ generated
according to $p\in P({\mathcal{Y}})$, and $y^{*}_{p}$ is the mode of $p$. To
find the optimal algorithm ${\mathcal{A}}^{*}$, we can invert the expectation
as

${\mathcal{E}}({\mathcal{A}})={\mathbb{E}}_{(Y_{j})}\left[{\mathbb{E}}_{p\sim
D}\left[\mathbf{1}_{{\mathcal{A}}((Y_{j}))\neq
y^{*}_{p}}\,\middle|\,\mathopen{}(Y_{j})\right]\right].$

This leads to the optimal algorithm

${\mathcal{A}}^{*}((Y_{j}))=\operatorname*{arg\,min}_{y\in{\mathcal{Y}}}{\mathbb{E}}_{p}\left[\mathbf{1}_{y\neq
y^{*}_{p}}\,\middle|\,\mathopen{}(Y_{j})\right]=\operatorname*{arg\,max}_{y\in{\mathcal{Y}}}{\mathbb{P}}_{p\sim
D}\left(y^{*}_{p}=y\,\middle|\,\mathopen{}(Y_{j})\right).$

It follows from
${\mathcal{E}}({\mathcal{A}})\geq{\mathcal{E}}({\mathcal{A}}^{*})$ that there
exists at least one distribution $p$ in the support of $D$ such that the error
made by any algorithm ${\mathcal{A}}$ on this distribution cannot be better
that the one made for ${\mathcal{A}}^{*}$, i.e.,

${\mathbb{E}}_{(Y_{j})}\left[\mathbf{1}_{{\mathcal{A}}((Y_{j}))\neq
y^{*}_{p}}\,\middle|\,\mathopen{}p\right]\geq{\mathbb{E}}_{(Y_{j})}\left[\mathbf{1}_{{\mathcal{A}}^{*}((Y_{j}))\neq
y^{*}_{p}}\,\middle|\,\mathopen{}p\right].$

One can define a prior such that ${\mathcal{A}}^{*}$ corresponds to the
empirical mode, i.e., ${\mathcal{A}}^{*}((Y_{j}))=\hat{y}_{n}$. In particular,
Corollary 2 follows from taking $D$ as the uniform distribution over the set
of permutations of the given distribution $p_{0}$, i.e.,
$\mathfrak{S}_{m}\cdot
p_{0}=\left\\{p\,\middle|\,\mathopen{}\exists\,\sigma\in\mathfrak{S}_{m},p=\sigma_{\\#}p_{0}\right\\}$.
Since any algorithm has to have its expected performance over the distribution
$p$ bounded by the one of ${\mathcal{A}}^{*}$, for any algorithm, there exists
at least one distribution $p\in\mathfrak{S}_{m}\cdot p_{0}$ such that its
performance is no better than the one of ${\mathcal{A}}^{*}$.

### Aside on User-Knowable Bounds

For a user that does not know $\Delta_{y}$, the bound of Theorem 1 is not
practically helpful, and the practitioner might be interested in stronger
formal guarantees. In particular, Valiant (1984) introduced the notion of
$(1-\delta)$-probably $\epsilon$-approximately correct estimator, for some
$\epsilon,\delta>0$, which reads
${\mathbb{P}}(p(\hat{y})<p(y_{1})-\epsilon)\leq\delta$. Proofs based on
concentration inequalities can usually be reworked to derive such
$(\epsilon,\delta)$-PAC bounds by replacing some quantity $\Delta$, related to
differences $p(y)-p(y_{1})$, by $\epsilon$ in the bound on the error $\delta$.
This is notably the case for Theorem 1. One can also estimate
$\hat{\Delta}_{y}$ and use plug-in techniques. The second half of this paper
will provide algorithms, namely the Elimination and Set Elimination
Algorithms, such that the user knows, and furthermore can choose, the
probability $\delta$ with which the algorithm will fail to output the true
mode –in the bandit literature, such algorithms are called $(0,\delta)$-PAC.

##  3 Exhaustive Dichotomic Search Procedures

This section introduces baseline algorithms based on exhaustive search
procedures. To leverage the empirical mode estimator, a naive baseline
consists in fully identifying each sample $Y_{j}$ one after the other. Using a
binary search, this can be done with $\left\lceil\log_{2}(m)\right\rceil$
queries (2) per sample. We can thus fully identify $n$ samples with
$T=n\left\lceil\log_{2}(m)\right\rceil$ queries. Together with Theorem 1, we
deduce that this naive baseline gets to precision $\delta$ as defined by
Equation (3) with a number of queries bounded by
$T=\Delta_{2}^{-2}\left\lceil\log_{2}(m)\right\rceil\ln(1/\delta)$. Our first
proposed improvement over this baseline is to refine binary searches through
entropy codes in order to minimize the average number of binary questions
asked to fully identify each sample $Y_{j}$, reducing the number of queries
per sample from $\left\lceil\log_{2}(m)\right\rceil$ to a quantity close to
the entropy $H(p)$ of $p$ (Shannon, 1948).

###  3.1 Entropy Coding

In order to identify each sample $Y_{j}$ with the least amount of queries, we
will use binary search algorithms stemming from coding theory. This section
fixes terminology and adds self-contained details on the matter.

######  Definition 1 (Binary Tree etc.).

For a set of elements ${\mathcal{Y}}$, we define leaves as abstract objects
$V_{y}$ for all $y\in{\mathcal{Y}}$. From leaves, we define nodes $V$ as
abstract objects associated with a right child $V_{1}=r(V)$ and a left child
$V_{2}=l(V)$ which are either nodes or leaves. A vertex is an abstract object
$V$ which is either a node or a leaf. A vertex $V_{1}$ is a descendant of
$V_{2}$, denoted by $V_{1}\lhd V_{2}$, if it can be built from the composition
$V_{1}=s_{1}\circ s_{2}\circ s_{3}\circ\cdots\circ s_{d}(V_{2})$ for
$d\in{\mathbb{N}}$ and $s_{i}\in\left\\{r,l\right\\}$ The descendants of a
node $V$ are all the vertices that can be built from the composition
$V^{\prime}\lhd V$. A binary tree ${\mathcal{T}}={\mathcal{T}}(R)$ is defined
from a root node $R$ with a finite number of descendants forming a collection
of vertices, such that each $V$ in this collection of vertices is defined by a
unique path $V=s_{1}\circ s_{2}\circ s_{3}\circ\cdots\circ s_{d}(R)$, with
$d=D_{\mathcal{T}}(V)\in{\mathbb{N}}$ being known as the depth of $V$ in
${\mathcal{T}}$.

A binary tree is associated with a prefix code.

######  Definition 2 (Vertex code).

The code $c_{\mathcal{T}}(V)\in\left\\{0,1\right\\}^{D_{\mathcal{T}}(V)}$ of
vertex $V$ in ${\mathcal{T}}$ is defined as the unique path to go from the
root node of ${\mathcal{T}}$ to $V$ by reading $c_{\mathcal{T}}(V)$ and
recursively advancing to the right child if reading a $1$ and to the left
child if reading a $0$.

The concept of binary tree is graphically intuitive. Let us provide an example
of a tree, and annotate each node in the tree with its code as per Definition
2. In the following illustration, each left (resp. right) child of a node are
represented below the node on the left (resp. on the right). We emphasize the
separation between right and left with a vertical bar. For example, if
$V=r\circ l\circ l\circ r(R)$, then $c_{\mathcal{T}}(V)=1001$.

        Root Node
    Leaf: 0 |                                  Node: 1
            |                     Node: 10        | Leaf: 11
            |       Node: 100         | Leaf: 101 |
            | Leaf: 1000 | Leaf: 1001 |           |

Prefix codes have been heavily studied in information theory, where the goal
is to transform a set ${\mathcal{Y}}$ in order to describe its elements $y$
with a sequence of bits $c(y)$. In particular, the minimal number of bits
transmitted when encoding sequences of tokens $(Y_{j})\in{\mathcal{Y}}^{n}$
into the concatenation of the codes $(c(Y_{j}))_{j\in[n]}$ is linked with the
entropy of the empirical distribution of the $y\in{\mathcal{Y}}$ in $(Y_{j})$.
There is a well known fundamental limit, for any $p\in{\mathcal{Y}}$,

$\min_{{\mathcal{T}}}{\mathbb{E}}_{Y\sim p}[D_{\mathcal{T}}(Y)]\geq
H(p):={\mathbb{E}}_{Y\sim p}[-\log_{2}p(Y)],$

where $D_{\mathcal{T}}(y)$ is seen as the length of the code $c(y)$, the
expectation is seen as the average code length, and the minimization as the
search for the best coding algorithm to minimize message length.

A simple algorithm to obtain optimal codes was found by Huffman (1952) –we
reproduce it in Algorithm 1. It takes as input a set of elements
${\mathcal{Y}}$ such that some positive value $v(y)$ is associated to each
$y\in{\mathcal{Y}}$. It outputs a tree whose leaves are the elements of
${\mathcal{Y}}$ and whose vertices also come associated to values, and which
satisfies certain conditions with respect to those values. When the value
$v(y)$ of element $y\in{\mathcal{Y}}$ is equal to $p(y)$ for some distribution
$p\in{\mathbb{P}}({\mathcal{Y}})$, which is assumed in Algorithm 1, then the
prefix code of the resulting tree on the elements of ${\mathcal{Y}}$ is
optimal with respect to the distribution $p$, i.e. it minimizes
$\min_{{\mathcal{T}}}{\mathbb{E}}_{Y\sim p}[D_{\mathcal{T}}(Y)]$ (see Huffman,
1952).

To describe Algorithm 1 succinctly, we introduce two notions of vertex
orderings. The first comes from the value $v(y)$ associated by hypothesis to
each $y\in{\mathcal{Y}}$, which would typically be $p(y)$, $N(y)$ or $N(y)/n$,
respectively the probability of $y$ for some distribution $p$, the empirical
occurrence counts of $y$ for some set of samples, or its empirical
probability. Given a tree whose leaves $V_{y}$ are in bijection with the
elements of ${\mathcal{Y}}$, let us associate to $V_{y}$ the value of the
corresponding $y\in{\mathcal{Y}}$, i.e. $v(V_{y})=v(y)$. The value of a node
is then defined recursively as the sum of its children value
$v(V)=v(r(V))+v(l(V))$. This leads to the following notion of ordering.

######  Definition 3 (Node ordering).

Two vertices $V_{1}$ and $V_{2}$ satisfy the partial ordering $V_{1}\vdash
V_{2}$ if $v(V_{1})<v(V_{2})$ or if $v(V_{1})=v(V_{2})$ and $V_{2}$ is a node
while $V_{1}$ is a leaf. The two vertices are equivalent, which we write
$V_{1}\sim_{\vdash}V_{2}$, if $V_{1}\not\vdash V_{2}$ and $V_{2}\not\vdash
V_{1}$.

The second ordering orders the nodes from bottom to top, and left to right.

######  Definition 4 (Code ordering).

Two vertices $V_{1}$ and $V_{2}$ in a tree ${\mathcal{T}}$ satisfy the total
ordering $V_{1}<_{\mathcal{T}}V_{2}$ if
$D_{\mathcal{T}}(V_{1})>D_{\mathcal{T}}(V_{2})$ or if
$D_{\mathcal{T}}(V_{1})=D_{\mathcal{T}}(V_{2})$ and
$c_{\mathcal{T}}(V_{1})<c_{\mathcal{T}}(V_{2})$ with respect to the
lexicographical order.

Once again, this is a highly visual concept. Let us number the vertices of the
previous tree according to the total ordering from Definition 4.

        Root Node: 9
    Leaf: 7 |                           Node: 8
            |                Node: 5      | Leaf: 6
            |       Node: 3     | Leaf: 4 |
            | Leaf: 1 | Leaf: 2 |         |

Data: Set of elements ${\mathcal{Y}}$ endowed with a probability distribution
$p\in P({\mathcal{Y}})$.

Create vertices $V_{y}$ for each $y\in{\mathcal{Y}}$ with value
$v(V_{y})=p(y)$;

Sort all the node into a heap ${\mathcal{S}}$ according to the comparison
$\vdash$ (Definition 3);

while  _${\mathcal{S}}$ has more than one element_ do

Pop $V_{1}$, $V_{2}$ the respective smallest elements in ${\mathcal{S}}$;

Merge them into a parent node $V$ with $V_{1}$ as the left child and $V_{2}$
the right one;

Insert $V$ into the heap ${\mathcal{S}}$ with its value
$v(V)=v(V_{1})+v(V_{2})$;

end while

Set the remaining node $V$ in the heap ${\mathcal{S}}$ as the root node of
${\mathcal{T}}={\mathcal{T}}(V)$;

Result: Huffman tree ${\mathcal{T}}$

Algorithm 1 Huffman Scheme

Let us illustrate Algorithm 1 with the count vector $N=(69,14,8,6,3)$. At the
first iteration, we set all nodes in a heap. Let us represent this heap as a
sorted list with comma-separated elements.

    Leaf 3; Leaf 6; Leaf 8; Leaf 14; Leaf 69;

Then we merge the two smallest ones and add the result in the heap. Let us
picture descendants below the nodes.

    Leaf 8; Node 9; Leaf 14; Leaf 69;
       Leaf 3 | Leaf 6

We iterate the process.

    Leaf 14; Node 17; Leaf 69
        Leaf 8 | Node 9
            Leaf 3 | Leaf 6

Now the heap is only made of a node with value $31$ and a leaf with value
$69$.

        Node 31; Leaf 69;
    Leaf 14 | Node 17
         Leaf 8 | Node 9
             Leaf 3 | Leaf 6

We end up with a binary tree.

                                         Node: 100
           Node: 31                        | Leaf: 69
    Leaf: 14 |       Node: 17              |
             | Leaf: 8 |       Node: 9     |
             |         | Leaf: 3 | Leaf: 6 |

In this paper, we introduce algorithms that build and adapt Huffman trees with
respect to a distribution $p$ that is simultaneously being learnt online. This
requires updating the trees on the fly. We can do so with the rebalancing
algorithm of Vitter (1987), which we present in Algorithm 2. This algorithm
uses integer values (which corresponds to empirical counts), and updates the
tree in reaction to an increase in value of $+1$ for a single leaf. Of course,
it can be repeatedly applied to account for greater changes.

Data: A Huffman tree ${\mathcal{T}}$ with counts $v(V)\in{\mathbb{N}}$. A node
$V$.

Swap $V$ with the biggest $V_{1}$ in the sense of $<_{\mathcal{T}}$ such that
$V\sim_{\vdash}V_{1}$;

Update $v(V):=v(V)+1$;

Swap $V$ with the smallest $V_{2}$ in the sense of $<_{\mathcal{T}}$ such that
$V\vdash V_{2}$;

if  _$v(V)=v(V_{2})$_ then

Update the new parent of $V_{2}$ by calling this algorithm on
$({\mathcal{T}},V_{2})$;

else

Update the new parent of $V$ by calling this algorithm on $({\mathcal{T}},V)$;

end if

Result: Updated Huffman tree ${\mathcal{T}}$.

Algorithm 2 Vitter Rebalancing

One can prove the following properties of the Huffman tree construction and
rebalancing.

######  Proposition 2 (Vitter (1987)).

When ${\mathcal{T}}$ is built with Algorithm 1 with some initial value
$v(V_{y})=\sum_{j\in[t_{0}]}\mathbf{1}_{Y_{j}=y}>0$ (for some set of samples
$(Y_{j})_{j}\subset{\mathcal{Y}}$) and is updated incrementally at each
timestep $t\in{\mathbb{N}}$ with respect to Algorithm 2 and the observation of
new samples $Y_{t}\in{\mathcal{Y}}$, the total ordering $<_{\mathcal{T}}$
(Definition 4) is always compatible with the partial ordering $\vdash$
(Definition 3).

Note that some subtleties are to be taken into account at initialization to
deal with leaves that have not yet been observed. In coherence with the
construction of Vitter (1987), we consider a special “not yet observed” node
which defines a balanced subtree containing all the unobserved leaves as its
descendants. When observing a new element $y$, we remove it from this subtree,
re-balance the subtree, and create a new node whose left child is the “not yet
observed” node and whose right one is the leaf corresponding to this $y$. This
new node is set at the former place of the “not yet observed” node.

Finally, the following code property will be useful to derive statistical
guarantees for our algorithms.

######  Definition 5.

A coding scheme ${\mathcal{A}}$ that associates a binary tree
${\mathcal{T}}_{\mathcal{A}}(p)$ to a probability vector $p\in
P({\mathcal{Y}})$ is said to be $C$-balanced if
$|c_{{\mathcal{T}}_{\mathcal{A}}(p)}(y)|\leq
C\left\lceil\log_{2}(p(y))\right\rceil$ for all $y\in{\mathcal{Y}}$.

Shannon codes are built explicitly to be $1$-balanced (Shannon, 1948).
However, in contrast with Huffman coding, Shannon coding does not provide the
lowest expected. Huffman codes are not always $1$-balanced, but the following
lemma, which we prove in Appendix .3, states that they are at least
$2$-balanced –in fact, one can prove a slightly better constant than 2.

######  Lemma 3.

Let ${\mathcal{T}}$ be a Huffman tree with respect to a value function $v$ on
its vertices such that $v(R)=1$, where $R$ is the root of ${\mathcal{T}}$.
Then for any vertex $V$ of ${\mathcal{T}}$, we have

$D_{\mathcal{T}}(V)\leq 2\left\lceil\log_{2}(1/v(V))\right\rceil.$

In other words, Huffman codes are $2$-balanced.

###  3.2 Exhaustive Search with Fixed Coding

As mentioned at the start of the section, our first, and rather naive,
proposed method of solving Problem 1 is to fully identify each sample $Y_{i}$
using a fixed search procedure, i.e., a set of $q$ predefined questions
$(\mathbf{1}_{y\in S_{i}})_{i\in[q]}$ such that any element
$y\in{\mathcal{Y}}$ is fully identified by the values of the functions
$\mathbf{1}_{y\in S_{i}}$. Such a search procedure an be mapped to a prefix
code $c:{\mathcal{Y}}\to\left\\{0,1\right\\}^{q}$ that associates any $y$ to
the binary code $c(y)=(\mathbf{1}_{y\in S_{i}})_{i\in[q]}$. It can also be
mapped to a binary tree, the code describing branching properties to reach the
leaf $y$ from the root node. Each question can be seen as eliciting one bit in
the code of $Y_{j}$, or equivalently going down one node in the corresponding
tree. Reciprocally, a code $(c(y)_{j})_{j\in[q]}$ is associated with the
search procedure considering
$S_{j}=\left\\{y\in{\mathcal{Y}}\,\middle|\,\mathopen{}c(y)_{j}=1\right\\}$.
In simple terms, $S_{j}$ enumerates all elements whose code $c$ contains a $1$
in the $j$-th position. This strategy for solving Problem 1 is formalized in
Algorithm 3. The average number of questions asked by such a search procedure
reads $\sum_{y\in{\mathcal{Y}}}p(y)|c(y)|$ where $|c(y)|$ is the length of the
code of $y$, or equivalently the depth of $y$ in the associated binary tree.
Consequently, if the predefined search procedure is a simple binary search,
the length of the code of any element is at most
$\left\lceil\log_{2}(m)\right\rceil$, and Theorem 1 guarantees that we need at
most $T=\ln(1/\delta)\alpha$ queries with
$\alpha=\Delta_{2}^{-2}\left\lceil\log_{2}(m)\right\rceil$ to bound the
probability of error by $\delta$.

Data: Set of classes ${\mathcal{Y}}=\left\\{y_{1},\ldots,y_{m}\right\\}$
endowed with $p\in P({\mathcal{Y}})$. A code
$c:{\mathcal{Y}}\to\left\\{0,1\right\\}^{d}$ (by default, we let
$d=\left\lceil\log_{2}(m)\right\rceil$ and $c(y_{i})$ be the binary
representation of the number $i$ with zeros in front)

for  _$j\in[n]$_ do

Get new sample $Y_{j}\sim p$ and query $c_{k}(Y_{j})$ for
$k\in\\{1,\ldots,\textrm{length}(c(Y_{j}))\\}$ until $Y_{j}$ is identified;

end for

Set $\hat{y}=\operatorname*{arg\,max}_{y\in{\mathcal{Y}}}N(y)$, where
$N(y)=\sum_{j\in[n]}\mathbf{1}_{Y_{j}=y}$;

Result: Estimated mode
$\hat{y}=\operatorname*{arg\,max}\sum_{j\in[n]}\mathbf{1}_{Y_{j}=y}$ of $p$.

Algorithm 3 Fixed Coding Exhaustive Search

###  3.3 Exhaustive Search with Adaptive Coding

Ideally, we would like to apply Algorithm 3 with a code $c$ that is optimal
with respect to the distribution $p$. As $p$ is not known a priori, we need to
learn the code on the fly. This leads to Algorithm 4, where a code is adapted
iteratively to best reflect the current estimate $\hat{p}$ of $p$ based on
past observations. As shown by the following theorem, the need to learn a code
online does not impact too much the complexity of Algorithm 5 in comparison to
that of Algorithm 3 with an optimal code.

Data: Set of classes ${\mathcal{Y}}=\left\\{y_{1},\ldots,y_{m}\right\\}$
endowed with $p\in P({\mathcal{Y}})$.

Initialize $N(y)=0$ for all $y\in{\mathcal{Y}}$; A coding scheme
${\mathcal{A}}$, an initial tree ${\mathcal{T}}$;

for  _$j\in[n]$_ do

Get new sample $Y_{j}\sim p$ and identify it by querying the entries of
$c_{\mathcal{T}}$;

Update $N(Y_{j})=N(Y_{j})+1$, and
${\mathcal{T}}={\mathcal{T}}_{\mathcal{A}}(\hat{p})$ where
$\hat{p}(y)=N(y)/j$;

end for

Set $\hat{y}=\operatorname*{arg\,max}_{y\in{\mathcal{Y}}}N(y)$;

Result: Estimated mode
$\hat{y}=\operatorname*{arg\,max}\sum_{j\in[n]}\mathbf{1}_{Y_{j}=y}$ of $p$.

Algorithm 4 Adaptive Coding Exhaustive Search

Data: Set of classes ${\mathcal{Y}}=\left\\{y_{1},\ldots,y_{m}\right\\}$
endowed with $p\in P({\mathcal{Y}})$.

Initialize $N(y)=0$ for all $y\in{\mathcal{Y}}$; Set ${\mathcal{T}}$ a Huffman
tree with $V_{y}=N(y)$;

for  _$j\in[n]$_ do

Get new sample $Y_{j}\sim p$ and identify it by querying the entries of
$c_{\mathcal{T}}(Y_{j})$;

Update $N(Y_{j})=N(Y_{j})+1$, and the Huffman tree ${\mathcal{T}}$ with
Algorithm 2;

end for

Set $\hat{y}=\operatorname*{arg\,max}_{y\in{\mathcal{Y}}}N(y)$;

Result: Estimated mode
$\hat{y}=\operatorname*{arg\,max}\sum_{j\in[n]}\mathbf{1}_{Y_{j}=y}$ of $p$.

Algorithm 5 Adaptive Coding Exhaustive Search with Huffman Coding

######  Theorem 3 (Adaptive entropic search performance).

Given a $C$-balanced coding scheme (Definition 5), in order to fully identify
$n$ samples $(Y_{j})$ following the adaptive coding strategy of Algorithm 4,
one needs on average ${\mathbb{E}}[T]$ queries, where

$nH(p)\leq{\mathbb{E}}[T]\leq Cn(H(p)+1)+28Cm\log_{2}(n)+6Cm+m^{2},$ (11)

and $H(p):=-\sum_{y\in{\mathcal{Y}}}p(y)\log_{2}(p(y))$ is the entropy of the
distribution $p\in P({\mathcal{Y}})$. In particular, in the case of Huffman
coding, Algorithm 5 yields

$nH(p)\leq{\mathbb{E}}[T]\leq 2n(H(p)+1)+o(n).$

As shown by Theorem 3, to reach a probability of error smaller than $\delta$,
Algorithm 4 needs $T=\ln(1/\delta)\alpha$ queries with
$\alpha=C\Delta_{2}^{-2}(H(p)+1)$ up to higher-order terms, with $C=1$ for
Shannon coding and $C=2$ for Huffman coding. This is an improvement in most
cases over the coefficient
$\alpha=\Delta_{2}^{-2}\left\lceil\log_{2}(m)\right\rceil$ of Algorithm 3.
Nonetheless, both Algorithms 3 and 4 precisely estimate $p(y)$ for each class
$y$, which is more information than needed if one only wants the mode of $p$,
leaving room for improvements.

###  3.4 Proofs

This subsection is devoted to the proof of Theorem 3. It is well known from
information theory that one has to ask at least $H(p)$ questions on average to
be able to identify $Y\sim p$ (Shannon, 1948), which explains the lower bound.
We need to prove the upper bound.

Recall that Algorithm 4 identifies each $Y_{i}$ by following a $C$-balanced
tree with respect to the empirical distribution $\hat{p}_{i}$ of the
previously observed samples $(Y_{j})_{j\leq i}\subset{\mathcal{Y}}$ as values.
Let us denote by $T_{n}$ the number of queries made to identify all the
$(Y_{i})$ for $i\leq n$. At round $i$, our search procedure associated with
the probability distribution $\hat{p}_{i}$ identifies each element $y$ in
${\mathcal{Y}}$ such that $\hat{p}_{i}(y)\neq 0$ with at most
$C\left\lceil-\log_{2}(\hat{p}_{i}(y))\right\rceil$ queries as per Definition
5. When $y$ is such that $\hat{p}_{i}(y)=0$, we identify it with at most $m$
queries. Hence, at round $i+1\in[n]$, $Y_{i+1}\sim p$ is identified with at
most the following number of questions on average

$C+{\mathbb{E}}_{y\sim p}\left[-\mathbf{1}_{\hat{p}_{i}(y)\neq 0}\cdot
C\log_{2}(\hat{p}_{i}(y))+\mathbf{1}_{\hat{p}_{i}(y)=0}\cdot m\right],$

where $\hat{p}_{i}$ is our estimate of $p$ after the complete identification
of $Y_{i}$, hence the one used for the queries on $Y_{i+1}$. Note that in this
setting, for each $y\in{\mathcal{Y}}$, there is at most a single round where
we need to identify $Y_{i}=y$ while $\hat{p}_{i-1}(y)=0$. Recursively, this
leads to

${\mathbb{E}}_{(Y_{i})_{i\leq n}}\left[T_{n}\right]\leq
Cn-C\sum_{i=1}^{n-1}{\mathbb{E}}_{(Y_{j})}\left[\sum_{y\in{\mathcal{Y}}}p(y)\mathbf{1}_{\hat{p}_{i}(y)\neq
0}\cdot\log_{2}(\hat{p}_{i}(y))\right]+m^{2}.$

Let us assume without loss of generality that $p(y)$ is never $0$, as the
terms for which $p(y)=0$ do not contribute to the sum. Now we split this
equation into two parts: a first part where one does not have a tight control
of the empirical distribution, but that is really unlikely and will not
contribute much to the full picture; and a part where the empirical
distribution concentrates towards its real mean,

$\displaystyle-\sum_{i=1}^{n-1}{\mathbb{E}}_{(Y_{j})}\left[\sum_{y\in{\mathcal{Y}}}p(y)\mathbf{1}_{\hat{p}_{i}(y)\neq
0}\log_{2}(\hat{p}_{i}(y))\right]=-\sum_{i=1}^{n-1}\sum_{y\in{\mathcal{Y}}}p(y){\mathbb{E}}_{(Y_{j})}\left[\mathbf{1}_{N_{y,i}\neq
0}\log_{2}\left(\frac{N_{y,i}}{i}\right)\right]$
$\displaystyle=\sum_{i,y}p(y){\mathbb{E}}_{(Y_{j})}\left[1_{\\{|\frac{N_{y,i}-ip(y)}{ip(y)}|\geq\frac{1}{2}\\}}\mathbf{1}_{N_{y,i}\neq
0}\log_{2}\left(\frac{i}{N_{y,i}}\right)+1_{\\{|\frac{N_{y,i}-ip(y)}{ip(y)}|<\frac{1}{2}\\}}\log_{2}\left(\frac{i}{N_{y,i}}\right)\right],$

where $N_{y,i}=\sum_{j\leq i}\mathbf{1}_{Yj=y}$ is the number of times we have
seen $y$ in the first $i$ samples. The first term corresponds to a highly
unlikely event, which we prove in Appendix .3.

######  Lemma 4.

With $N_{i,y}$ denoting the empirical count
$\sum_{j\in[i]}\mathbf{1}_{Y_{j}=y}$,

$-\sum_{i=1}^{n-1}\sum_{y\in{\mathcal{Y}}}p(y){\mathbb{E}}_{(Y_{j})}\left[1_{\\{|\frac{N_{y,i}-ip(y)}{ip(y)}|\geq\frac{1}{2}\\}}\mathbf{1}_{N_{y,i}\geq
1}\log_{2}\left(\frac{N_{y,i}}{i}\right)\right]\leq 22m\log_{2}(n),$

We now consider the second term. Let us extract the scaling in $H(p)$ inherent
to entropy coding. To that end, we rewrite it as

$-\sum_{i=1}^{n-1}\sum_{y\in{\mathcal{Y}}}p(y){\mathbb{E}}_{(Y_{j})}\bigg{[}1_{\\{|\frac{N_{y,i}-ip(y)}{ip(y)}|<\frac{1}{2}\\}}\bigg{(}\log_{2}\left(p(y)\right)+\log_{2}\left(\frac{N_{y,i}}{ip(y)}\right)\bigg{)}\bigg{]}.$

The first term presents the desired scaling

$-\sum_{i=1}^{n-1}\sum_{y\in{\mathcal{Y}}}p(y){\mathbb{E}}_{(Y_{j})}\left[1_{\\{|\frac{N_{y,i}-ip(y)}{ip(y)}|<\frac{1}{2}\\}}\log_{2}\left(p(y)\right)\right]\leq-\sum_{i=1}^{n-1}\sum_{y\in{\mathcal{Y}}}p(y)\log_{2}\left(p(y)\right)\leq
nH(p).$

Finally, we deal with the rightmost logarithm, using the Taylor series of the
logarithm to show concentration for the empirical mean of the logarithm. The
details are provided in Appendix .3.

######  Lemma 5.

With $N_{i,y}$ denoting the empirical count
$\sum_{j\in[i]}\mathbf{1}_{Y_{j}=y}$,

$-\ln(2){\mathbb{E}}_{(Y_{j})}\left[1_{\\{|\frac{N_{y,i}-ip(y)}{ip(y)}|<\frac{1}{2}\\}}\log_{2}\left(\frac{N_{y,i}}{ip(y)}\right)\right]\leq
4m(\ln(n)+1).$

Collecting the different pieces together, we find the upper bound,

$\displaystyle{\mathbb{E}}_{(Y_{i})_{i\leq n}}\left[T_{n}\right]\leq
Cn-C\sum_{i=1}^{n-1}{\mathbb{E}}_{(Y_{j})}\left[\sum_{y\in{\mathcal{Y}}}p(y)\mathbf{1}_{\hat{p}_{i}(y)\neq
0}\cdot\log_{2}(\hat{p}_{i}(y))\right]+m^{2}$ $\displaystyle\leq
Cn(1+H(p))+m^{2}+22Cm\log_{2}(n)+\frac{4Cm}{\ln(2)}(\ln(n)+1)+m^{2}$
$\displaystyle\leq Cn(1+H(p))+28Cm\log_{2}(n)+6Cm+m^{2}.$

##  4 Truncated Search

In this section, we improve upon the previous search procedures using the
following key observation. When estimating the empirical mode of a batch by
identifying samples following a Huffman tree, one can stop the search
procedure roughly when reaching the depth $D=\left|\log_{2}(p(y_{1}))\right|$
of the mode, resulting in about $\left|\log_{2}p(y_{1})\right|$ queries per
sample on average, rather than $H(p)$ queries when trying to fully identify
each sample.

###  4.1 Coarse Sufficient Statistics

We introduce the concept of admissible partitions, which provide sufficient
statistics for mode estimation that are weaker than the full empirical
distribution $\hat{p}$, as well as the concept of $\eta$-admissible partition,
which will be useful to build statistically and computationally efficient
algorithms. Recall that a partition ${\mathcal{P}}$ of ${\mathcal{Y}}$ is a
subset of $2^{\mathcal{Y}}$, such that for any
$\left\\{S_{1},S_{2}\right\\}\subset{\mathcal{P}}$, $S_{1}\cap
S_{2}=\emptyset$, and $\cup_{S\in{\mathcal{P}}}S={\mathcal{Y}}$. Here and
throughout the text, for $p\in P({\mathcal{Y}})$ and $S\subset{\mathcal{Y}}$,
we define $p(S):=\sum_{y\in S}p(y)$.

######  Definition 6 (Admissible partitions).

An admissible partition of ${\mathcal{Y}}$ with respect to $p\in
P({\mathcal{Y}})$ refers to a partition ${\mathcal{P}}\subset 2^{\mathcal{Y}}$
such that

$\operatorname*{arg\,max}_{S\in{\mathcal{P}}}p(S)=\left\\{y^{*}\right\\},\qquad\text{where}\qquad
y^{*}=\operatorname*{arg\,max}_{y\in{\mathcal{Y}}}p(y).$ (12)

For $\eta>0$, an $\eta$-admissible partition of ${\mathcal{Y}}$ with respect
to $p$ is similarly defined as an admissible partition ${\mathcal{P}}\subset
2^{\mathcal{Y}}$ for which all sets $S\in{\mathcal{P}}$ such that
$p(S)\geq\eta$ are singletons, and at most a single set $S$ verifies
$p(S)<\eta/2$. Formally,

$\left|\left\\{S\in{\mathcal{P}}\,\middle|\,\mathopen{}p(S)<\eta/2\right\\}\right|\leq
1\qquad\text{and}\qquad\forall\,S\in{\mathcal{P}},\quad{p(S)\geq\eta\quad\Rightarrow\quad|S|=1}.$
(13)

The interest of admissible partitions comes from the fact that if
${\mathcal{P}}$ is an admissible partition with respect to both $p$ and
$p^{\prime}\in P({\mathcal{Y}})$, then $p$ and $p^{\prime}$ have the same
modes. In particular, if ${\mathcal{P}}$ is an admissible partition for the
empirical distribution $\hat{p}$ of some batch of samples, the set
$S\in{\mathcal{P}}$ with the largest mass $\hat{p}(S)$ is a singleton
containing the empirical mode of the batch. On the computational side, when
$p$ is known, $\eta$-admissible partitions are easy to build, which contrasts
with the NP-hardness of finding an admissible partition of minimal
cardinality, or of finding a set $S$ that maximizes $p(S)$ under the
constraint $p(S)\leq p(y^{*})$.555 The latter is equivalent to the knapsack
problem (Mathews, 1896), while the partition problem (Korf, 1998) can be
reduced to the former with the following construction. Consider a list $p_{0}$
of positive integers and include an element $p_{*}$ equal to half the sum of
$p_{0}$ plus an infinitesimal quantity. Next, normalize all elements to
transform the new list into a probability vector $p$ whose elements add up to
one. Checking if $p_{0}$ can be partitioned into two lists $S_{1}$ and $S_{2}$
that sum to the same value is equivalent to determining whether there exists
an admissible partition of $p$ of cardinality three.

###  4.2 Adaptive Truncated Search

Building upon Definition 6, Algorithm 6 efficiently constructs an
$\eta$-admissible partition ${\mathcal{P}}$ of ${\mathcal{Y}}$ with respect to
the empirical frequencies $\hat{p}$ of a batch of samples $(Y_{j})_{j\in[n]}$.
It uses a predefined binary tree ${\mathcal{T}}$, and takes two parameters
$\gamma,\epsilon\in[0,1]$ that define $\eta=\gamma\hat{p}(\hat{y})-\epsilon$,
where $\hat{y}$ is the mode of $\hat{p}$. The algorithm starts with the
trivial partition ${\mathcal{P}}=\left\\{{\mathcal{Y}}\right\\}$, and
recursively refines it by splitting the set $S_{*}$ with the greatest
empirical mass until $S_{*}$ is a singleton, which must then be equal to
$\\{\hat{y}\\}$. It then keeps splitting non-singleton sets of mass strictly
greater than $\gamma\hat{p}(\hat{y})-\epsilon$ until there are no such sets
left. The splitting is done using the tree ${\mathcal{T}}$ as follows: we
identify each node $V$ in the tree with the set of all the elements that map
to its descendent leaves
$S(V)=\left\\{y\in{\mathcal{Y}}\,\middle|\,\mathopen{}V_{y}\lhd V\right\\}$.
At each time step, the sets $S$ of the current partition correspond to nodes
$(V_{S})$ of ${\mathcal{T}}$, and the set $S_{*}=S(V_{*})$ that has to be
split is replaced in the partition by its two children
$S(l(V_{*})),S(r(V_{2}))$ in ${\mathcal{T}}$. This consumes
$N(S_{*})=\sum_{j\in[n]}\mathbf{1}_{Y_{j}\in S_{*}}$ queries to identify which
sample belongs to $S_{1}$ and which to $S_{2}$. At the end, a Huffman scheme
is applied to merge sets into an $\eta$-admissible partition, and re-balance
the tree ${\mathcal{T}}$ so that all sets in the partition are at a similar
depth, roughly equal to $\log_{2}(2/\eta)$, in the new tree. This re-balancing
keeps the structure of the “sub-trees” below the nodes corresponding to the
sets of the partition intact. In addition, the algorithm identifies which
sample belongs to which set of ${\mathcal{P}}$, as well as the empirical mode
$\hat{y}$.

Data: Set ${\mathcal{Y}}=\left\\{y_{1},\ldots,y_{m}\right\\}$, binary tree
${\mathcal{T}}$, $n$ samples $(Y_{j})$, parameters
$\gamma,\epsilon\in{\mathbb{R}}$.

Set $V_{*}$ the root of the tree ${\mathcal{T}}$, $S_{*}={\mathcal{Y}}$,
$N(S_{*})=n$;

Set ${\mathcal{S}}=\left\\{(V_{*}:n)\right\\}$ built as a heap,
${\mathcal{L}}=\\{\\}$ an empty list, and $C=-\infty$;

For all $S$ and $V$, we denote $N(S)=\sum_{j\in[n]}\mathbf{1}_{Y_{j}\in
S}\in{\mathbb{N}}$ and
$S(V)=\left\\{y\in{\mathcal{Y}}\,\middle|\,\mathopen{}V_{y}\lhd
V\right\\}\subset{\mathcal{Y}}$.

while  _the heap ${\mathcal{S}}$ is non-empty and $N(S_{*})\geq C$_ do

Set $V_{*}=\operatorname*{arg\,max}_{V\in{\mathcal{S}}}N(S(V))$ by popping it
out of the heap ${\mathcal{S}}$; set $S_{*}=S(V_{*})$;

if  _$V_{*}$ is a leaf_ then

If it was the first encountered leaf, set $\\{\hat{y}\\}:=S_{*}$, and refine
$C:=\gamma N(\\{\hat{y}\\})-\epsilon n$;

Add $V_{*}$ to the list ${\mathcal{L}}$;

else

Make $N(S_{*})$ queries to get all the information on $(\mathbf{1}_{Y_{j}\in
S(V)})_{j\in[n]}$ for $V\in\left\\{l(V_{*}),r(V_{*})\right\\}$;

Insert each child $V\in\left\\{l(V_{*}),r(V_{*})\right\\}$ into the heap
${\mathcal{S}}$ with value $N(S(V))$;

end if

end while

Add all the remaining elements of the heap to the list ${\mathcal{L}}$;

Apply Huffman’s scheme, Algorithm 1, to the list ${\mathcal{L}}$ to rebalance
the top of the tree ${\mathcal{T}}$;

Result: A tree ${\mathcal{T}}$ containing an
$(\gamma\hat{p}(\hat{y})-\epsilon)$-admissible partition for $\hat{p}$, and
the empirical mode $\hat{y}$.

Algorithm 6 Batch Tree Rebalancing

This suggests a new way to tackle Problem 1: given a batch of samples,
Algorithm 6 yields an admissible partition with respect to the empirical
distribution $\hat{p}$, and in particular identifies its empirical mode
$\hat{y}$, which is the best possible mode estimate. It does not need to fully
identify each sample to do so, unlike Algorithms 3 and 5. The number of
queries consumed by Algorithm 6 depends on the tree ${\mathcal{T}}$ that it
takes as input: upon reaching the final partition ${\mathcal{P}}$, the
algorithm will have required $D$ queries for each sample belonging to a given
set $S\in{\mathcal{P}}$, where $D$ is the depth of the node associated with
$S$ in the tree ${\mathcal{T}}$. To minimize the expected number of queries
needed, ${\mathcal{T}}$ should be a partial Huffman tree with respect to the
distribution $p$; this would result in $D\leq
C\left\lceil-\log_{2}(2/p(y_{1}))\right\rceil$ for each $S\in{\mathcal{P}}$,
with $C=2$ as per Lemma 3. We do not have a priori access to the distribution
$p$, but we can learn the structure of such a tree over several rounds, with a
slack parameter $\epsilon_{r}$ to account for the gradually increasing
precision of our estimates. This is Algorithm 7, whose guarantees are provided
by Theorem 4.

Data: Set ${\mathcal{Y}}=\left\\{y_{1},\ldots,y_{m}\right\\}$, samples
$(Y_{s})$, scheduling $(n_{r})\in{\mathbb{N}}^{\mathbb{N}}$ and
$(\epsilon_{r})\in{\mathbb{R}}^{\mathbb{N}}$.

Set ${\mathcal{T}}$ a binary search tree;

for  _$r\in{\mathbb{N}}$_ do

Get $n_{r}$ fresh samples $(Y_{j,r})_{j\in[n_{r}]}$ defining an empirical
probability $\hat{p}_{r}$;

Run Algorithm 6 with tree ${\mathcal{T}}$, $\gamma=1$ and
$\epsilon=\epsilon_{r}$ to obtain the empirical mode $\hat{y}_{r}$ and update
${\mathcal{T}}$;

end for

Result: Return the last $\hat{y}_{r}$ as the estimated mode.

Algorithm 7 Truncated Search

######  Theorem 4 (Truncated search performance).

For any $\delta>0$, the number of queries $T$ needed by Algorithm 7 run with
the schedulings $n_{r}:=2^{r}$ and
$\epsilon_{r}:=\frac{1}{4m}\left(\frac{2}{3}\right)^{\frac{r}{2}}$ to
correctly identify the mode with probability at least $1-\delta$ satisfies

${\mathbb{E}}[T]\leq
8\ln(1/\delta)\Delta_{2}^{-2}\left\lceil\log_{2}\left(\frac{4}{p(y_{1})}\right)\right\rceil+o(\ln(1/\delta)).$
(14)

Algorithm 7 is a clear amelioration over the previous search algorithms: the
probability of error remains the same as a function of the number of samples,
while reducing the average number of queries per sample from $H(p)$ to roughly
$\left|\log_{2}p(y_{1})\right|$, going from average code length to minimal
code length. Nonetheless, there is still room for improvement. Algorithm 7
identifies the empirical mode of the entire batch with absolute certitude.
This contrasts with the main takeaway from the bandit literature: one should
leverage confidence intervals to build statistically efficient algorithms so
as to avoid spending queries solely to rule out highly unlikely events. We
explore this intuition in the next section. Note that replacing the Huffman
code from Algorithm 6 by any $C$-balanced code would result in a modified
bound

${\mathbb{E}}[T]\leq
4C\ln(1/\delta)\Delta_{2}^{-2}\left\lceil\log_{2}\left(\frac{4}{p(y_{1})}\right)\right\rceil+o(\ln(1/\delta)).$

in Theorem 4 (in particular, using a Shannon code would yield $C=1$).

###  4.3 Proofs

This subsection provides the key elements for the proof of Theorem 4. Our
strategy is the following.

  * •

Find a likely event ${\mathcal{A}}$ where the algorithm behaves as desired.

  * •

Show that its complement ${}^{c}{\mathcal{A}}$ is unlikely enough that the
additional queries it elicits are asymptotically negligible.

Let $r\geq 2$. We let ${\mathcal{T}}_{r}$ be the updated tree at the end of
round $r$, and ${\mathcal{P}}_{r}$ be the corresponding $\eta_{r}$-admissible
partition where $\eta_{r}=\hat{p}_{r}(\hat{y}_{r})-\epsilon_{r}$. Here
$\hat{p}_{r}$ is the empirical distribution of the samples at round $r$, and
$\hat{y}_{r}$ is the corresponding empirical mode. Let us define the event

${\cal
A}=\left\\{\forall\,S\subset{\mathcal{Y}},\quad\max\left\\{|\hat{p}_{r-1}(S)-p(S)|,|\hat{p}_{r}(S)-p(S)|\right\\}\leq\frac{\epsilon_{r-1}-\epsilon_{r}}{4}\right\\}.$
(15)

A union bound, detailed in Appendix .4, shows that ${\cal A}$ is likely to
happen as the number of rounds increases, as stated in the following lemma.

######  Lemma 6.

The event ${\mathcal{A}}$ defined by (15) satisfies

${\mathbb{P}}\left({}^{c}{\mathcal{A}}\right)\leq
2^{m+1}\exp\left(-\frac{n_{r-1}}{2}\left(\frac{\epsilon_{r-1}-\epsilon_{r}}{4}\right)^{2}\right).$
(16)

We claim that under the event ${\mathcal{A}}$, the $\eta_{r-1}$-admissible
partition obtained at the end of round $r-1$ stays admissible at round $r$,
namely, we have the implication

${\mathcal{A}}\quad\subset\quad\left\\{\text{All sets
}S\in{\mathcal{P}}_{r-1}\text{ such that
}\hat{p}_{r}(S)>\hat{p}_{r}(\hat{y}_{r})-\epsilon_{r}\text{ are
singletons}\right\\}.$ (17)

###### Proof of Equation (17).

Indeed, ${\mathcal{A}}$ implies that
$|\hat{p}_{r-1}(S)-\hat{p}_{r}(S)|\leq(\epsilon_{r-1}-\epsilon_{r})/2$ and as
a consequence, for any set $S\in{\mathcal{P}}_{r-1}$ of cardinality at least
$2$, the fact that ${\mathcal{P}}_{r-1}$ is
$(\hat{p}_{r-1}(\hat{y}_{r})-\epsilon_{r-1})$-admissible with respect to
$\hat{p}_{r-1}$ leads to

$\displaystyle\hat{p}_{r}(S)$
$\displaystyle\leq\hat{p}_{r-1}(S)+\frac{\epsilon_{r-1}-\epsilon_{r}}{2}<\hat{p}_{r-1}(\hat{y}_{r-1})-\epsilon_{r-1}+\frac{\epsilon_{r-1}-\epsilon_{r}}{2}$
$\displaystyle\leq\hat{p}_{r}(\hat{y}_{r-1})-\epsilon_{r}\leq\hat{p}_{r}(\hat{y}_{r})-\epsilon_{r},$

Hence, under ${\mathcal{A}}$, all sets $S\in{\mathcal{P}}_{r-1}$ such that
$\hat{p}_{r}(S)>\hat{p}_{r}(\hat{S}_{r})-\epsilon_{r}$ are singletons. ∎

Let us assume that ${\mathcal{A}}$ is realized –then all sets
$S\in{\mathcal{P}}_{r-1}$ are either singletons or such that
$\hat{p}_{r}(S)\leq\hat{p}_{r}(\hat{y}_{r})-\epsilon_{r}$. Hence, when
Algorithm 6 is applied to the $n_{r}$ samples of round $r$, a sample $Y_{i,r}$
belonging to some set $S\in{\mathcal{P}}_{r-1}$ only consumes a number of
queries smaller666The number of queries needed can be strictly smaller than
the depth of $S$ if some parent set $S^{\prime}$ of $S$ is such that
$\hat{p}_{r-1}(S^{\prime})>\hat{p}_{r-1}(\hat{y}_{r-1})-\epsilon_{r-1}$ but
$\hat{p}_{r}(S^{\prime})\leq\hat{p}_{r}(\hat{y}_{r})-\epsilon_{r}$. or equal
to the depth $D(S)$ of $S$ in the tree ${\mathcal{T}}_{r-1}$. Since
${\mathcal{T}}_{r-1}$ was obtained by applying Huffman’s scheme to the sets of
${\mathcal{P}}_{r-1}$ at the end of Algorithm 6 to re-balance the tree
${\mathcal{T}}_{r-2}$, we can leverage Lemma 3 to bound the depth $D(S)$.
Since $\left\\{y_{1}\right\\}\subset{\mathcal{Y}}$, when ${\mathcal{A}}$ is
realized

$p(y_{1})-\hat{p}_{r-1}(\hat{y}_{r-1})\leq
p(y_{1})-\hat{p}_{r-1}(y_{1})<\frac{\epsilon_{r-1}-\epsilon_{r}}{4}<\epsilon_{r}.$

As ${\mathcal{P}}_{r-1}$ is
$(\hat{p}_{r-1}(\hat{y}_{r-1})-\epsilon_{r-1})$-admissible, necessarily each
$S\in{\mathcal{P}}_{r-1}$ (except at most one) is such that

$\hat{p}_{r-1}(S)\geq\frac{\hat{p}_{r-1}(\hat{y}_{r-1})-\epsilon_{r-1}}{2}>\frac{p(y_{1})-\epsilon_{r}-\epsilon_{r-1}}{2}\geq\frac{p(y_{1})-2\epsilon_{r-1}}{2}\geq\frac{p(y_{1})}{4},$

where we use the fact that $\epsilon_{r-1}<1/4m\leq p(y_{1})/4$. Applying
Lemma 3, we deduce that

$D(S)\leq 2\left\lceil\log_{2}(4/p(y_{1}))\right\rceil.$ (18)

If $S$ is such that
$\hat{p}_{r-1}(S)<\frac{\hat{p}_{r-1}(\hat{y}_{r-1})-\epsilon_{r-1}}{2}$ (and
there can be only one such set), then it must share a parent in
${\mathcal{T}}_{r-1}$ with some other set $S^{\prime}$, from which we deduce
that its depth follows the same bound. Hence the total number of queries
consumed at round $r$, assuming that ${\mathcal{A}}$ is realized, is at most
$n_{r}2\left\lceil\log_{2}(4/p(y_{1}))\right\rceil$. If the event
${\mathcal{A}}$ is not realized, we can roughly upper bound the number of
queries spent per sample by $m$, hence we can upper bound the total number of
queries by $n_{r}m$. In the special case $r=1$, we similarly need at most
$n_{r}m$ queries. A few lines of derivations provided in Appendix .4 lead to
the following lemma.

######  Lemma 7.

When running Algorithm 7 with the schedule of Theorem 4, the expected number
of queries needed for round $r$ satisfies

${\mathbb{E}}\left[T_{r}\right]\leq
2^{r}\left(\left\lceil\log_{2}\left(\frac{4}{p(y_{1})}\right)\right\rceil+m2^{m+1}\exp\left(-\left(\frac{4}{3}\right)^{r}\frac{C}{m^{2}}\right)\right)$

for some constant $C>0$.

At the end of round $r$, the algorithm outputs the empirical mode
$\hat{y}_{r}$ of the $n_{r}$ samples $(Y_{i,r})_{i\in[n_{r}]}$ defining the
empirical probability $\hat{p}_{r}$. We know from Theorem 1 that its
probability of error $\delta_{r}$ is bounded by

$\delta_{r}\leq\exp\left(-n_{r}\Delta_{2}^{2}\right)=\exp\left(-2^{r}\Delta_{2}^{2}\right).$

Now let $\delta>0$, and define the round

$r_{\delta}=\min\left\\{r\,\middle|\,\mathopen{}\exp(-n_{r}\Delta_{2}^{2})\leq\delta\right\\}=\min\left\\{r\,\middle|\,\mathopen{}n_{r}\geq\Delta_{2}^{-2}\ln(1/\delta)\right\\}$

By construction, $n_{r_{\delta}}=2n_{r_{\delta}-1}\leq
2\ln(1/\delta)\Delta_{2}^{-2}$. At the end of round $r_{\delta}$, the
probability of outputting the correct class is at least $1-\delta$, and the
total number of expected queries used so far by Algorithm 7 is at most

$\displaystyle\sum_{r=1}^{r_{\delta}}{\mathbb{E}}[T_{r}]$
$\displaystyle\leq\sum_{r=1}^{r_{\delta}}n_{r}\left(2\left\lceil\log_{2}\left(\frac{4}{p(y_{1})}\right)\right\rceil+m2^{m+1}\exp\left(-\left(\frac{4}{3}\right)^{r}\frac{C}{m^{2}}\right)\right)$
$\displaystyle\leq
2\left\lceil\log_{2}\left(\frac{4}{p(y_{1})}\right)\right\rceil\sum_{r=1}^{r_{\delta}}n_{r}+\sum_{r\geq
1}2^{r}m2^{m+1}\exp\left(-\left(\frac{4}{3}\right)^{r}\frac{C}{m^{2}}\right)$
$\displaystyle\leq
4n_{r_{\delta}}\left\lceil\log_{2}\left(\frac{4}{p(y_{1})}\right)\right\rceil+\tilde{C}\leq
8\ln(1/\delta)\Delta_{2}^{-2}\left\lceil\log_{2}\left(\frac{4}{p(y_{1})}\right)\right\rceil+o(\ln(1/\delta)).$

This completes the proof.

##  5 Bandit-Inspired Elimination

The core idea of this section is to successively eliminate candidate classes
$y\in{\mathcal{Y}}$ in order to lower the required number of queries compared
to the Exhaustive Search Algorithm from Section 3, which can be done by
adapting and improving the seminal Successive Elimination Algorithm from Even-
Dar, Mannor and Mansour (2006), resulting in Algorithm 8.

Data: Set ${\mathcal{Y}}$, probability $p\in P({\mathcal{Y}})$, samples
$\\{Y_{r}\\}_{r\in{\mathbb{N}}}$, schedule
$\sigma:{\mathbb{N}}\times{\mathbb{R}}^{\mathcal{Y}}\to{\mathbb{R}}^{\mathcal{Y}}$.

Set $S_{e}=\emptyset$ the set of eliminated guesses, $r=0$,
$N(y)=0\in{\mathbb{R}}^{m}$;

while  _${\mathcal{Y}}\backslash S_{e}$ is not a singleton_ do

Set $r\leftarrow r+1$ and query $\mathbf{1}_{Y_{r}\in S_{e}}$;

if  _$Y_{r}\notin S_{e}$_ then

Identify $Y_{r}$ with a Huffman tree adapted to empirical counts $N(y)$ on
${\mathcal{Y}}\setminus S_{e}$;

Update $N(Y_{r})=N(Y_{r})+1$, and set the empirical distribution
$\hat{p}_{r}(y)\propto N(y)$ accordingly;

Set $S_{e}=S_{e}\cup\\{y\in{\mathcal{Y}}\setminus
S_{e}|\hat{p}_{r}(y)+\sigma_{y}(r,\hat{p}_{r})<\max_{z\in{\mathcal{Y}}\setminus
S_{e}}\hat{p}_{r}(z)\\}$;

end while

Result: Estimate mode $\hat{y}$ as the only element of
${\mathcal{Y}}\backslash S_{e}$.

Algorithm 8 Elimination

Algorithm 8 takes as input a generic parameter function $\sigma$ and works as
follows: at any time, it maintains a set of eliminated classes
$S_{e}\subset{\mathcal{Y}}$ that are deemed unlikely to be the mode. At the
start of round $r$, the algorithm tests whether the new sample $Y_{r}$ belongs
to $S_{e}$; if not, it is identified with a Huffman tree adapted to the
empirical distribution $\hat{p}_{r}$ on ${\mathcal{Y}}\backslash S_{e}$, which
is then updated.777There is a minor abuse of notations in the description of
Algorithm 8: in the expression “$\sigma_{y}(r,\hat{p}_{r})$”, the distribution
$\hat{p}_{r}$ on ${\mathcal{Y}}\backslash S_{e}$ is implicitly seen as a
distribution on ${\mathcal{Y}}$ by setting $\hat{p}_{r}(y)=0$ if $y\in S_{e}$
so that it is a valid argument for $\sigma$.  Any class $y$ such that its
empirical mass $\hat{p}_{r}(y)$ satisfies
$p_{r}(y)+\sigma_{y}(r,\hat{p}_{r})<\max_{z\in{\mathcal{Y}}\setminus
S_{e}}\hat{p}_{r}(z)$ is finally added to the set of eliminated classes
$S_{e}$. For a well-chosen parameter function $\sigma$, Algorithm 8 has a high
probability of identifying the true mode, as stated in Theorem 5.

######  Theorem 5.

Let $\delta>0$, and define the elimination scheduling
$\sigma:{\mathbb{N}}\times{\mathbb{R}}^{\mathcal{Y}}\to{\mathbb{R}}^{\mathcal{Y}}$
as

$\sigma_{y}(r,\hat{p})=\sqrt{\frac{c\max_{z}\hat{p}_{r}(z)\ln(\pi^{2}mr^{2}/\delta)}{r}},\qquad\text{with}\qquad
c=24.$ (19)

With probability $1-\delta$, Algorithm 8 terminates, identifies the right mode
and has consumed less than $T$ queries, where, conditionally to this
successful event,

$\frac{{\mathbb{E}}[T]}{\ln(1/\delta)}\leq
C_{1}\frac{p(y_{1})}{\nabla_{2}^{2}}+C_{2}\sum_{i\in[m]}p(y_{i})\frac{p(y_{1})}{\nabla_{i}^{2}}\left\lceil\log_{2}\left(\frac{1}{p(y_{i})}\right)\right\rceil+o(1),$

for two universal constants $C_{1},C_{2}$, $\nabla_{i}:=p(y_{1})-p(y_{1})$ if
$i\neq 1$ and $\nabla_{1}=\nabla_{2}$.

As shown in Proposition 8 below, whose proof can be found in Appendix .5,
$\nabla_{i}^{-2}p(y_{1})$ is equal to $\Delta_{i}^{-2}$ up to a multiplicative
factor as long as $p(y_{1})$ is bounded away from $1$ –this is no constraint
in most interesting use cases, as Problem 1 gets easier the closer $p(y_{1})$
gets to $1$. Hence we see that Theorem 5 is a clear improvement upon the
Exhaustive Search Algorithms 3 and 5. In essence, one requires roughly
$\Delta_{i}^{-2}\log(1/\delta)$ samples to know with certainty $1-\delta$ that
class $y_{i}$ is not the mode. As the Exhaustive Search Algorithm from Section
3 never eliminates any class, the number of samples it requires to reach
accuracy $1-\delta$ is conditioned by the second most likely class $y_{2}$,
the one that is hardest to correctly dismiss. Conversely, Algorithm 8
eliminates with high probability the class $y_{i}$ after having seen about
$\log(1/\delta)\Delta_{i}^{-2}$ samples, which translates to an improved
asymptotic expected number of required queries as a function of $\delta$.
However, Algorithm 8 does not leverage the coarse statistics and search
truncation mechanism presented in Section 4, leaving room for further
improvement. We combine the elimination mechanism of Algorithm 8 and the
search truncation technique of Algorithm 7 in Section 6, after the remainder
of this section which is dedicated to the discussion of Algorithm 8 and the
proof of Theorem 5.

######  Proposition 8.

Let $p\in P({\mathcal{Y}})$ with $p(y_{1})>p(y_{i})$ for all $i\in[m]$. We
have the following inequality, with $\nabla_{i}:=p(y_{1})-p(y_{i})$ and
$\Delta_{i}^{2}=-\ln(1-(\sqrt{p(y_{1})}-\sqrt{p(y_{i})})^{2})$,

$\frac{p(y_{1})}{-\ln(1-p(y_{1}))}p(y_{1})\nabla_{i}^{-2}\leq\Delta_{i}^{-2}\leq
4p(y_{1})\nabla_{i}^{-2}.$

In particular, if $p(y_{1})$ is bounded away from $1$, then
$-p(y_{1})/\ln(1-p(y_{1})$ is bounded away from $0$ and $\Delta_{i}^{-2}\simeq
p(y_{1})\nabla_{i}^{-2}$ up to a multiplicative constants.

###  5.1 Design of the elimination schedule

Algorithm 8 was inspired by the seminal algorithm of Even-Dar, Mannor and
Mansour (2006). Their Successive Elimination Algorithm uses Hoeffding’s
inequality to define $\sigma_{y}(r,p)=\sigma_{r}$ where
$\sigma_{r}^{2}\simeq\ln(1/\delta)/r$. It is known that Hoeffding’s inequality
can be refined for sub-gamma variables with Bernstein’s inequalities, which
was the main motivation behind the UCB-V algorithm of Audibert, Munos and
Szepesvári (2009). Bernstein’s inequality can be seen as a convenient weak
formulation of Chernoff’s bounds, which in the case of Bernoulli variables are
expressed in terms of KL-divergences, and have motivated the KL-UCB algorithm
of Cappé et al. (2013). KL-based confidence intervals are defined as

$\sigma_{y}(r,p)=\inf\left\\{q\in[0,1]\,\middle|\,\mathopen{}\exp(-rD(p(y)\|p(y)\pm
q))\leq\delta\right\\}.$

While they arguably provide the best asymptotic results, they introduce
computational overhead that we were keen to avoid in our algorithms.

Rather than trying to find the tightest confidence intervals, our definition
of $\sigma_{y}(r,p)$ in Theorem 5 comes from a different perspective: the
optimization of elimination times. We know from Lemma 24, a variant of Theorem
1 provided in Appendix .2 based on a method of Cramér (1938), that we can not
safely eliminate $y_{i}$ as a mode candidate before having made
$r_{i}\simeq\Delta_{i}^{-2}\ln(1/\delta)$ observations of both
$\mathbf{1}_{Y_{j}=y_{i}}$ and $\mathbf{1}_{Y_{i}=y_{1}}$. The Proposition 8
below states that this is roughly the same as asking for

$r_{i}\simeq
p(y_{1})\nabla_{i}^{-2}\ln(1/\delta)=p(y_{1})(p(y_{1})-p(y_{i}))^{-2}\ln(1/\delta).$

Plugging this in the elimination criterion of Algorithm 8, we would like to
define $\sigma$ so as to ensure that with high probability,

$\hat{p}_{r}(y_{1})-\hat{p}_{r}(y_{i})-\sigma_{y_{i}}(r,\hat{p})\geq 0$

for any $r\leq r_{i}$. Assuming that the empirical probability $\hat{p}_{r}$
converges fast enough to $p$, a confidence parameter $\sigma$ defined as

$\sigma_{y_{i}}(r,p)\simeq(p(y_{1})-p(y_{i}))\sqrt{\frac{r_{i}}{r}}\simeq\sqrt{\frac{p(y_{1})\ln(1/\delta)}{r}}$

satisfies this constraint. Of course, we do not have a priori access to
$p(y_{1})$. Instead, we estimate it at round $r$ with
$\max_{y\in{\mathcal{Y}}}\hat{p}_{r}(y)$. Up to a few constants needed to
account for union bounds, this leads to $\sigma$ as defined in Theorem 5. In
comparison to the results of Even-Dar, Mannor and Mansour (2006), whose
algorithm requires $O(\sum_{i}\nabla_{i}^{-2}\log(1/\delta))$ samples, we gain
a factor $p(y_{1})<1$, thanks to which we reach the ideal scaling in
$\Delta_{i}^{-2}$ as long as $p(y_{1})$ is bounded away from $1$.

###  5.2 Proofs

In this section, we prove Theorem 5. Let $\hat{p}_{r}$ denotes the empirical
probability of the first $r$ samples $(Y_{i})_{i\leq r}$, and $S_{r}$ be the
set $S_{e}$ of rejected classes, updated at each iteration $r$ by Algorithm 8.
We define $\hat{y}_{r}=\operatorname*{arg\,max}_{y\in{\mathcal{Y}}\backslash
S_{r}}\hat{p}_{r}(y)$, and $\delta_{r}=\delta/\pi^{2}mr^{2}$, and we consider
the elimination criterion

$\hat{p}_{r}(y)+\sigma_{r}<\hat{p}_{r}(\hat{y}_{r}),\qquad\sigma_{r}=\sqrt{\frac{24\hat{p}_{r}(\hat{y}_{r})\ln(1/\delta_{r})}{r}}$

from Algorithm 8 with the schedule from Theorem 5.

We have seen in the discussion of the previous subsection that the estimation
of the unknown quantity $p(y_{1})$ by $\hat{p}_{r}(\hat{y}_{r})$ is a key
component of the definition of $\sigma_{r}$. In fact, it turns out that
estimating $p(y_{1})$ is much easier than finding the mode $y_{1}$, yet can
help us with that second, harder task. The next two lemmas deal with this
subproblem, and are crucial to our proof of Theorem 5. Chernoff’s bound for
Bernoulli variables states that one needs roughly $\ln(1/\delta)/p(y)$ samples
to get a good estimate of $p(y)$ up to multiplicative constants. It leads to
the following lemma, proved in Appendix .5.

######  Lemma 9.

For any $c>1$, let $\hat{p}_{r}$ be the empirical probability associated with
$r$ random samples $(Y_{i})_{i\leq r}$ independently distributed according to
$p\sim P({\mathcal{Y}})$. It holds that

$\forall\,r\geq\frac{c+1}{(c-1)^{2}}\frac{1}{p(y)}\ln(1/\delta),\qquad{\mathbb{P}}(\hat{p}_{r}(y)>cp(y))\leq\delta$

and

$\forall\,r\geq\frac{c^{2}}{(c-1)^{2}}\frac{1}{p(y)}\ln(1/\delta),\qquad{\mathbb{P}}(\hat{p}_{r}(y)<c^{-1}p(y))\leq\delta.$

While Lemma 9 shows that one needs about $r\simeq\ln(1/\delta)/p(y_{1})$
samples in order to get a good estimate of $p(y_{1})$, it is not of much use
by itself: as $p(y_{1})$ is a priori unknown, we cannot compute this required
number of samples. We could naively estimate it as the first round $r$ such
that $r\max_{y\in{\mathcal{Y}}}\hat{p}_{r}(y)\geq\ln(1/\delta)$. The next
lemma shows that this strategy actually works well.

######  Lemma 10.

For any $r\in{\mathbb{N}}_{\geq 1}$, $\delta>0$ and $c>1$, let
$\hat{y}_{r}=\operatorname*{arg\,max}_{y\in{\mathcal{Y}}}\hat{p}_{r}(y)$ and
consider the event

${\mathcal{A}}_{r}=\left\\{r\hat{p}_{r}(\hat{y}_{r})\leq
c\ln(1/\delta)\right\\}.$

Then

$\forall\,r\leq\frac{2c^{2}-c}{2c+1+\sqrt{1+8c}}\frac{1}{p(y_{1})}\ln(1/\delta),\qquad{\mathbb{P}}({}^{c}{\mathcal{A}}_{r})\leq
m\delta,$

and

$\forall\,r\geq\frac{c^{2}}{c+1-\sqrt{1+2c}}\frac{1}{p(y_{1})}\ln(1/\delta),\qquad{\mathbb{P}}({\mathcal{A}}_{r})\leq\delta.$

Note that by combining Lemmas 9 and 10, one can derive an efficient
$(0,\delta)$-PAC algorithm to get a good estimate of $p(y_{1})$ up to user-
defined multiplicative constants: first, use Lemma 9 and the aforementioned
constants to express the number $r_{0}$ of samples needed as a function of
$p(y_{1})$ and $\delta$. This number cannot be explicitly computed by the
user, as they do not have access to $p(y_{1})$; however, one can use Lemma 10
to define some event ${\mathcal{A}}$ associated to some constant $c$ such that
once ${\mathcal{A}}$ does not hold any more, $r$ is bigger than $r_{0}$ will
high probability. For any such $r$, $\hat{p}_{r}(\hat{y}_{r})$ will be a good
estimate of $p(y_{1})$. Though we do not explicitly use such an algorithm, it
is implicitly at the core of Theorem 4, as will become apparent in what
follows.

As for the proof of Theorem 4, we define likely events that ease the analysis.
Their definitions, and lower bounds on their probabilities, are provided by
the following lemma, proven in Appendix .5.

######  Lemma 11.

Let us write $\tilde{\sigma}_{r}=\sqrt{3p(y_{1})\ln(1/\delta_{r})/r}$, and
define the events

  * •

$A_{1}=\\{\hat{p}_{r}(y_{1})\geq p(y_{1})/2$ for all $r\geq
4\ln(1/\delta_{r})/p(y_{1})\\}$,

  * •

$A_{2}=\\{\hat{p}_{r}(\hat{y}_{r})\leq 2p(y_{1})$ for all $r\geq
4\ln(1/\delta_{r})/p(y_{1})\\}$,

  * •

$A_{3}=\\{|\hat{p}_{r}(y_{i})-p(y_{i})|\leq\tilde{\sigma}_{r}\\}$ for all
$r\geq 4\ln(1/\delta_{r})/p(y_{1})$ and $i\in[m]$,

  * •

$A_{4}=\\{\sigma_{r}\geq\hat{p}_{r}(\hat{y}_{r})$ for all $r\leq
4\ln(1/\delta_{r})/p(y_{1})\\}$.

Then ${\mathbb{P}}(A_{i})\geq 1-\delta/6$ for $i\in\\{1,2,4\\}$ and
${\mathbb{P}}(A_{3})\geq 1-\delta/3$.

Those events will allow us to guarantee the validity of Algorithm 8 with high
probability. Note that, due to a coincidence in our choice of constants, the
event $A_{2}$ is in fact implied by $A_{3}$. We nonetheless keep $A_{2}$ as a
separate event for increased readability. Intuitively, these events should be
interpreted as follows: $A_{1}$ and $A_{2}$ ensure that $\hat{p}_{r}(\hat{y})$
is roughly equal to $p(y_{1})$ once the threshold
$r=\frac{4}{p(y_{1})}\ln(1/\delta_{r})$, which is given by Lemmas 9 and 10, is
reached. Past this threshold, the quantity
$\tilde{\sigma}_{r}=\sqrt{\frac{3p(y_{1})\ln(1/\delta_{r})}{r}}$ acts as a
good deterministic proxy for
$\sigma_{r}/2=\sqrt{\frac{6\hat{p}_{r}(\hat{y})\ln(1/\delta_{r})}{r}}$, and
$A_{3}$ ensures that the empirical probability mass $\hat{p}_{r}(y_{i})$ of
each class $y_{i}$ is within an interval of width $\tilde{\sigma}_{r}$
centered around the true mass $p(y_{i})$. Before this threshold, $A_{4}$
ensures that $\sigma_{r}$ is too large for the elimination criterion to be
satisfied, hence that no classes are eliminated before
$r\leq\frac{4}{p(y_{1})}\ln(1/\delta_{r})$. All of this combined keeps $y_{1}$
from being wrongly eliminated, and yields upper bounds on the elimination
times of the classes $y_{i}$ with $i>1$. The next paragraphs will formalize
these claims. We start by showing that the mode is never wrongfully
eliminated.

######  Lemma 12.

When the events $(A_{i})_{i\in[4]}$ hold, the mode $y_{1}$ is never
eliminated.

###### Proof.

If $A_{4}$ holds, then for any $r\leq 4\ln(1/\delta_{r})/p(y_{1})$ we have
$\hat{p}_{r}(y)+\sigma_{r}\geq\hat{p}_{r}(\hat{y}_{r})$, hence, by definition
of the elimination criterion, no classes can be eliminated at round $r$.

Let us now consider any round $r\geq 4\ln(1/\delta_{r})/p(y_{1})$. Assume that
$y_{1}$ has not yet been eliminated at the start of round $r$. The event
$A_{3}$ implies

$\hat{p}_{r}(y_{1})\geq p(y_{1})-\tilde{\sigma}_{r}\geq
p(y_{i})-\tilde{\sigma}_{r}\geq\hat{p}_{r}(y_{i})-2\tilde{\sigma}_{r},$

while the event $A_{1}$ leads to
$\hat{p}_{r}(\hat{y}_{r})\geq\hat{p}_{r}(y_{1})\geq p(y_{1})/2$, hence

$\sigma_{r}=\sqrt{24\hat{p}_{r}(\hat{y}_{r})\ln(1/\delta_{r})/r}\geq\sqrt{12p(y_{1})\ln(1/\delta_{r})/r}=2\tilde{\sigma}_{r}.$

This means that the criterion
$\hat{p}_{r}(y_{1})+\sigma_{r}<\hat{p}_{r}(\hat{y}_{r})$ cannot be satisfied,
and thus $y_{1}$ cannot be eliminated at round $r$ if it was not at round
$r-1$. Recursively, we deduce that $y_{1}$ is never eliminated. ∎

Let us now focus on the elimination of the other classes $y\neq y_{1}$.

######  Lemma 13.

When the event $(A_{j})_{j\in[4]}$ hold, the class
$y_{i}\in{\mathcal{Y}}\backslash\\{y_{1}\\}$ is eliminated no later than when

$r>108\frac{p(y_{1})}{\nabla_{i}^{2}}\ln(1/\delta_{r}).$

Since $\ln(\delta_{r})=\ln(1/\delta)+2\ln(r)+c$, this defines an elimination
time

$r(y_{i})=108\frac{p(y_{1})}{\nabla_{i}^{2}}\ln(1/\delta)+o(\ln(1/\delta)).$
(20)

###### Proof.

Let $i>1$, and assume that the events $(A_{j})_{j\in[4]}$ hold. We know from
Lemma 12 that our hypothesis implies that $y_{1}$ is never eliminated, hence
that $\hat{p}_{r}(\hat{y}_{r})\geq\hat{p}_{r}(y_{1})$. Due to $A_{2}$, it also
implies that

$\tilde{\sigma}_{r}=\sqrt{\frac{3p(y_{1})\ln(1/\delta_{r})}{r}}\geq\sqrt{\frac{3\hat{p}_{r}(\hat{y}_{r})\ln(1/\delta_{r})}{2r}}=\frac{\sigma_{r}}{4}.$

Furthermore, $A_{3}$ implies that

$\hat{p}_{r}(\hat{y}_{r})-\hat{p}_{r}(y_{i})\geq
p(y_{1})-p(y_{i})-2\tilde{\sigma}_{r}.$

If the following inequality holds

$p(y_{1})-p(y_{i})>6\tilde{\sigma}_{r}.$

then

$\hat{p}_{r}(\hat{y}_{r})-\hat{p}_{r}(y_{i})\geq
p(y_{1})-p(y_{i})-2\tilde{\sigma}_{r}>4\tilde{\sigma}_{r}\ \geq\sigma_{r}.$

The lemma reduces to the characterization of $r$ such that
$p(y_{1})-p(y_{i})>6\tilde{\sigma}_{r}$. ∎

The two previous lemmas have shown that when $(A_{i})_{i\in[4]}$ hold, $y_{1}$
is never eliminated and $y_{i}$ is eliminated at the latest when
$r=108(p(y_{1})-p(y_{i}))^{-2}p(y_{1})\ln(1/\delta)+o(\ln(1/\delta))$. In
particular, the algorithm ends and outputs the correct mode before $r_{2}$.
Using Lemma 11, this happens with probability at least

${\mathbb{P}}(\cap_{i\in[4]}{\mathcal{A}}_{i})\geq
1-{\mathbb{P}}({}^{c}A_{1}\cup{}^{c}A_{2}\cup{}^{c}A_{3}\cup{}^{c}A_{4})\geq
1-\sum_{i=1}^{4}{\mathbb{P}}({}^{c}A_{i})\geq 1-\delta,$ (21)

Regarding the number of expected queries, we use one query for each sample to
check if it belongs to the eliminated set. If it is not, i.e. $Y_{i}\notin
S_{r}$, we expect, based on Theorem 3, to have to ask about
$|\log_{2}(\tilde{p}(y))|$ $\leq\left|\log_{2}(p(y))\right|$ queries to
identify $Y_{i}=y$, where $\tilde{p}$ is the restriction of $p$ to the set
${\mathcal{Y}}\setminus S_{r}$.

This explains the number of queries in Theorem 5,

$\displaystyle{\mathbb{E}}\left[T\,\middle|\,\mathopen{}(A_{j})_{j\in[4]}\right]$
$\displaystyle\lesssim\sum_{r\leq
r(y_{2})}\sum_{i\in[m]}p(y_{i})(1+\mathbf{1}_{y_{i}\notin
S_{r}}|\log_{2}(p(y_{i}))|)$ $\displaystyle\lesssim
r(y_{2})+\sum_{i\in[m]}r(y_{i})p(y_{i})|\log_{2}(p(y_{i}))|$
$\displaystyle\simeq\Big{(}\frac{p(y_{1})}{\nabla_{2}^{2}}+\sum_{i\leq
m}p(y_{i})\frac{p(y_{1})}{\nabla_{i}^{2}}|\log_{2}(p(y_{i}))|\Big{)}\ln(1/\delta).$

The proof technicalities are provided in Appendix .5, yielding the following
lemma.

######  Lemma 14.

In the setting of Theorem 5, with the event $(A_{i})_{i\in[n]}$ defined in
Lemma 11,

$\frac{{\mathbb{E}}\left[T|(A_{j})_{j\in[4]}\right]}{\ln(1/\delta}\leq
324\frac{p(y_{1})}{\nabla_{2}^{2}}+216\sum_{i=1}^{m}p(y_{i})\left|\log_{2}(p(y_{i}))\right|\frac{p(y_{1})}{\nabla_{i}^{2}}+o(1)$

Lemma 14 ends the proof of Theorem 5 and explicits the constants $C_{1}$ and
$C_{2}$.

##  6 Set Elimination

The intuition behind Algorithm 7 is that given a Huffman tree with respect to
$p$, one does not need to go far below the depth $-\log_{2}p(y_{1})+1$ when
searching for the mode (or equivalently, that classes with low probability can
be grouped into sets of classes with probability roughly equal to
$p(y_{1})/2$). Meanwhile, the intuition behind Algorithm 8 is that one can
quickly eliminate low-probability classes to focus on likely candidates. The
combination of these ideas yields Algorithm 9, which outperforms both. Classes
are partitioned into sets of mass roughly equal to $p(y_{1})/2$, which are
eliminated as soon as they appear unlikely to be the mode. Those partitions
must sometimes be redefined (as the sets might be of greater mass than
initially estimated), but these reorderings are rare and do not impact
asymptotic performance. Hence, under the light of Proposition 8, Algorithm 9
requires roughly $\Delta_{i}^{-2}\log(1/\delta)$ samples to discard class
$y_{i}$ as a mode candidate with confidence level $1-\delta$, and a sample
consumes roughly $\left|\log_{2}p(y_{1})\right|$ queries. This explains
Theorem 6.

Data: ${\mathcal{Y}}$, $(Y_{s})\sim p$, scheduling
$(n_{r})\in{\mathbb{N}}^{\mathbb{N}}$ and
$(\epsilon_{r})\in{\mathbb{R}}^{\mathbb{N}}$, confidence interval parameter
$\sigma$.

Set the eliminated set $S_{e}=\emptyset$, $r=0$, and ${\mathcal{T}}$ a binary
search tree;

while  _${\mathcal{Y}}\backslash S_{e}$ is not a singleton_ do

Set $r\leftarrow r+1$;

Get $n_{r}$ fresh samples $(Y_{j,r})_{j\in[n_{r}]}$;

Ask $(\mathbf{1}_{(Y_{j,r})\in S_{e}})_{j\in[n_{r}]}$ to remove samples that
belong to the eliminated set $S_{e}$;

We call $\hat{p}_{r}$ the empirical distribution on $(Y_{j,r})_{j\in[n_{r}]}$
and $\hat{y}_{r}$ the mode of its restriction to ${\mathcal{Y}}\backslash
S_{e}$;

Run Algorithm 6 with tree ${\mathcal{T}}$ and parameters
$\gamma=1/2,\epsilon=\epsilon_{r}/\hat{p}_{r}({\mathcal{Y}}\backslash S_{e})$
on the samples $Y_{j,r}\not\in S_{e}$;

This updates ${\mathcal{T}}$ and yields a
$\hat{p}_{r}(\hat{y}_{r})/2-\epsilon_{r}$-admissible partition
${\mathcal{P}}_{r}$ of ${\mathcal{Y}}\backslash S_{e}$ with respect to
$\hat{p}_{r}$;

Set $\hat{p}_{+}(S)=\hat{p}_{r}(S)+\sigma(n_{r},\hat{p}_{r})$ for
$S\in{\mathcal{P}}_{r}$;

Set $S_{e}=S_{e}\cup\\{y\in
S\>|\>S\in{\mathcal{P}},\hat{p}_{+}(S)<\hat{p}_{r}(\hat{y}_{r})\\}$ to
eliminate unlikely mode candidates;

end while

Result: Return the mode estimate $\hat{y}_{r}$ of the last round $r$ as the
estimated mode.

Algorithm 9 Set Elimination

######  Theorem 6.

If Algorithm 9 is run with schedule $n_{r}:=2^{r}$ and
$\epsilon_{r}:=\frac{1}{4m}\left(\frac{2}{3}\right)^{\frac{r}{2}}$ and
confidence interval parameter $\sigma$ defined from a confidence level
parameter $\delta>0$ as888 Note that although we do not have access to all the
$\\{\hat{p}_{r}(z)\\}_{z\in{\mathcal{Y}}\backslash S_{e}}$ when running
Algorithm 9, we have access to their maximizer (as an output of Algorithm 6),
which ensures that $\sigma(n_{r},\hat{p}_{r})$ is computable by the user.

$\sigma(n,\hat{p})=\sqrt{\frac{c\max_{z\in{\mathcal{Y}}\setminus
S_{e}}\hat{p}(z)\ln(\pi^{2}mn^{2}/\delta)}{n}},\qquad\text{with}\qquad c=24,$
(22)

then with probability $1-\delta$ Algorithm 9 terminates, identifies the right
mode and consumes less than $T$ queries, where, conditionally to this
successful event,

$\displaystyle\frac{{\mathbb{E}}\left[T\right]}{\log(1/\delta)}$
$\displaystyle\leq C_{1}\frac{p(y_{1})}{\nabla_{2}^{2}}+C_{2}\sum_{i\leq
m}p(y_{i})\frac{p(y_{1})}{\nabla_{i}^{2}}\left\lceil\log_{2}\left(\frac{10}{p(y_{1})}\right)\right\rceil+o(1),$

for two universal constants $C_{1},C_{2}$, $\nabla_{i}:=p(y_{1})-p(y_{1})$ if
$i\neq 1$ and $\nabla_{1}=\nabla_{2}$.

Note that the asymptotic expected number of queries required only depends on
the classes $y$ that are close in probability mass to $y_{1}$, as the
contribution to the sum of all the classes $y$ that are such that $p(y)\leq
p(y_{1})/2$ is smaller than
$4C_{2}\left\lceil\log_{2}(10/p(y_{1}))\right\rceil\log(1/\delta)/p(y_{1})$.
In particular, we have freed ourselves from any direct dependence in the
number $m$ of classes. On the other hand, we expect to have to precisely
estimate the probability mass $p(y_{i})$ of the classes for which $p(y_{i})$
is close to $p(y_{1})$. In line with this intuition, the dependence in those
classes of the expected number of queries is roughly
$C_{2}\Delta_{i}^{-2}\left\lceil\log_{2}(10/p(y_{1}))\right\rceil\log(1/\delta)$,
which corresponds, up to a multiplicative factor, to the number of samples
needed to disqualify $y_{i}$ as a mode candidate multiplied by the rough
number of queries needed to precisely identify $y_{i}$ using a Huffman tree
adapted to $p$. These semi-heuristic arguments suggest that there should be no
easy way to improve upon Algorithm 9, besides tightening the various constants
in Theorem 6 through more careful computations.

###  6.1 Proofs

This section provides the proof for Theorem 6, which is a combination of sorts
of the proofs of Theorems 4 and 5. Let $r\geq 2$, $n_{r}=2^{r}$, and
$\hat{p}_{r}$ be the empirical probability distribution associated to the
samples $(Y_{i,r})_{i\in[n_{r}]}$ used in the $r$-th round in Algorithm 9. We
denote by $S_{r}$ the random set of all classes that have been eliminated in
the previous rounds, and by $\hat{y}_{r}$ the mode of $\hat{p}_{r}$ restricted
to ${\mathcal{Y}}\backslash S_{r}$, i.e.
$\hat{y}_{r}=\operatorname*{arg\,max}_{y\not\in S_{r}}\hat{p}_{r}(y)$. To
simplify notation, we write $\sigma_{r}$ for $\sigma_{y}(n_{r},\hat{p}_{r})$,
and set $\delta_{r}=\delta/\pi^{2}mn_{r}^{2}$.

We start by introducing the same events as in the proof of Theorem 5, with the
small nuance that the distributions $\hat{p}_{r}$ for $r\in{\mathbb{N}}$ are
independent from each other, and that we only consider the subset of indices
$\\{n_{r}\\}_{r}\subset{\mathbb{N}}$. The proof of the associated lemma is the
same as that of Lemma 11.

######  Lemma 15.

Let us write $\tilde{\sigma}_{r}=\sqrt{3p(y_{1})\ln(1/\delta_{r})/n_{r}}$, and
define the events

  * •

$A_{1}=\\{\hat{p}_{r}(y_{1})\geq p(y_{1})/2$ for all $r$ such that $n_{r}\geq
4\ln(1/\delta_{r}/p(y_{1})\\}$,

  * •

$A_{2}=\\{\hat{p}_{r}(\hat{y}_{r})\leq 2p(y_{1})$ for all $r$ such that
$n_{r}\geq 4\ln(1/\delta_{r})/p(y_{1})\\}$,

  * •

$A_{3}=\\{|\hat{p}_{r}(y_{i})-p(y_{i})|\leq\tilde{\sigma}_{r}$ for all $r$
such that $n_{r}\geq 4\ln(1/\delta_{r})/p(y_{1})$ and $i\in[m]\\}$,

  * •

$A_{4}=\\{\sigma_{r}\geq\hat{p}_{r}(\hat{y}_{r})$ for all $r$ such that
$n_{r}\leq 4\ln(1/\delta_{r})/p(y_{1})\\}$.

Then ${\mathbb{P}}(\cap_{i\in[4]}{\mathcal{A}}_{i})\geq 1-\delta$.

Once again $y_{1}$ cannot be eliminated when the events $(A_{i})_{i\in[4]}$
hold.

######  Lemma 16.

When the events $(A_{i})_{i\in[4]}$ defined in Lemma 15 holds, Algorithm 9
does not eliminate the mode.

###### Proof.

Assume that $y_{1}$ was not eliminated at the start of round $r$. The round
iteration defines a $(\hat{p}_{r}(\hat{y}_{r})/2-\epsilon_{r})$-admissible
partition ${\mathcal{P}}_{r}$ on ${\mathcal{Y}}\backslash S_{r}$ with respect
to $\hat{p}_{r}$, and all samples $Y_{i,r}$ are identified along
${\mathcal{P}}_{r}\cup\\{S_{r}\\}$. Necessarily
$\\{\hat{y}_{r}\\}\in{\mathcal{P}}_{r}$. At the end of this round, a class
$y\in{\mathcal{Y}}\setminus S_{r}$ can only be added to the set $S_{r}$ of
eliminated classes if it belongs to some set $S\subset{\mathcal{Y}}\backslash
S_{r}$ such that $\hat{p}_{r}(S)+\sigma_{r}<\hat{p}_{r}(\hat{y}_{r})$. In
particular, this implies that $\hat{p}_{r}(y)+\sigma_{r}<p_{r}(\hat{y}_{r})$,
which is the criterion that was applied in the Elimination Algorithm 8 from
Section 5. As in the proof of Theorem 5, the events $(A_{i})_{i\in[4]}$ ensure
that $\hat{p}_{r}(y_{1})+\sigma_{r}<p_{r}(\hat{y}_{r})$ is never true, which
means that $y_{1}$ cannot be eliminated. ∎

Let us now estimate the expected number of queries required for round $r$,
still assuming that events $(A_{i})_{i\in[4]}$ are realized. We introduce the
same event as in the proof of Theorem 4.

${\mathcal{B}}_{r}=\left\\{\forall\,S\subset{\mathcal{Y}},\quad\max\left\\{|\hat{p}_{r-1}(S)-p(S)|,|\hat{p}_{r}(S)-p(S)|\right\\}\leq\frac{\epsilon_{r-1}-\epsilon_{r}}{4}\right\\}.$
(23)

We have already shown that

${\mathbb{P}}({}^{c}{\mathcal{B}}_{r})\leq
2^{m+1}\exp\Big{(}-\frac{n_{r-1}}{2}\Big{(}\frac{\epsilon_{r-1}-\epsilon_{r}}{4}\Big{)}^{2}\Big{)}\leq
2^{m+1}\exp\Big{(}-\Big{(}\frac{4}{3}\Big{)}^{r}\frac{C}{m^{2}}\Big{)},$ (24)

for some constant $C>0$. When ${\mathcal{B}}_{r}$ holds, we can bound the
number of queries similarly to what we have done for Theorem 4.

######  Lemma 17.

Let ${\mathcal{T}}_{r-1}$ be the tree as updated by Algorithm 6 at the end of
round $r-1$ of Algorithm 9. A sample $Y_{i,r}\not\in S_{r}$ belonging to some
set $S\in{\mathcal{P}}_{r-1}$ only consumes at round $r$ a number of queries
smaller than or equal to the depth $D(S)$ of $S$ in the tree
${\mathcal{T}}_{r-1}$. When ${\mathcal{B}}_{r}$ (23) holds,

$D(S)\leq 2\left\lceil\log_{2}\Big{(}\frac{10}{p(y_{1})}\Big{)}\right\rceil.$

###### Proof.

For $r\geq 1$, ${\mathcal{T}}_{r}$ is built as a Huffman tree on the nodes
corresponding to the sets of ${\mathcal{P}}_{r}$ with respect to
$\hat{p}_{r}$. Similarly to the case of the Truncated Search Algorithm 7 and
the proof of the associated Theorem 4, when $B_{r}$ is realized, all sets
$S\in{\mathcal{P}}_{r-1}$ are either singletons or such that
$\hat{p}_{r}(S)\leq\hat{p}_{r}(\hat{y}_{r})/2-\epsilon_{r}$. Hence, when
Algorithm 6 is applied to the $n_{r}$ samples of round $r$, a sample
$Y_{i,r}\not\in S_{r}$ belonging to some set $S\in{\mathcal{P}}_{r-1}$ only
consumes a number of queries smaller than or equal to the depth $D(S)$ of $S$
in the tree ${\mathcal{T}}_{r-1}$. Using as in the proof of Theorem 4 the
facts that $\epsilon_{r-1}<p(y_{1})/4$ and that all $S\in{\mathcal{P}}_{r-1}$
(except at most one) satisfy

$\displaystyle\hat{p}_{r-1}(S)$
$\displaystyle\geq\frac{\hat{p}_{r-1}(\hat{y}_{r-1})/2-\epsilon_{r-1}}{2}>\frac{p(y_{1})-\frac{\epsilon_{r-1}-\epsilon_{r}}{4}-2\epsilon_{r-1}}{4}>\frac{p(y_{1})-\frac{9\epsilon_{r-1}}{4}}{4}>\frac{7p(y_{1})}{64}.$

We conclude that $D(S)\leq 2\left\lceil\log_{2}(64/7p(y_{1}))\right\rceil$
thanks to Lemma 3. ∎

If the event ${\mathcal{B}}_{r}$ is not realized, we can roughly upper bound
the number of queries spent per sample by $m$, hence we can upper bound the
total number of queries by $n_{r}m$. In the special case $r=1$, we similarly
need at most $n_{r}m$ queries.

Let $T_{r}$ be the total number of queries needed for round $r$ (it is a
random variable). We spend $n_{r}$ queries at the start of the round to check
whether $Y_{i,r}\in S_{r}$ for each sample $Y_{i,r}$, $i\in[n_{r}]$. We have
shown that if $r\geq 2$, then

$T_{r}\leq\sum_{i=1}^{n_{r}}1+1_{\\{Y_{i,r}\not\in
S_{r}\\}}\left(2\left\lceil\log_{2}\left(\frac{10}{p(y_{1})}\right)\right\rceil+1_{{}^{c}B_{r}}m\right),$
(25)

while if $r=1$, $T_{r}\leq n_{1}m$.

As previously, we will bound (the expectation of) $1_{\\{Y_{i,r}\not\in
S_{r}\\}}$ by a deterministic quantity under the events $(A_{j})_{j\in[4]}$.

######  Lemma 18.

When the events $(A_{j})_{j\in[4]}$ holds, then $y_{i}\neq y_{1}$ is added to
$S_{r}$ no later than when $r=r(y)$, where the elimination time $r(y)$ is
defined as

$r(y)=\min\left\\{r\,\middle|\,\mathopen{}n_{r}>108\max\left((p(y_{1})-p(y))^{-2},(p(y_{1})/2)^{-2}\right)p(y_{1})\ln(1/\delta_{r})\right\\}$

In particular

$n_{r(y)}\leq
216\max\left((p(y_{1})-p(y))^{-2},(p(y_{1})/2)^{-2}\right)p(y_{1})\ln(1/\delta_{r}).$

###### Proof.

We write $\tilde{\sigma}_{r}=\sqrt{3p(y_{1})\ln(1/\delta_{r})/n_{r}}$; we have
seen in the proof of Theorem 5 that $A_{2}$ implies
$4\tilde{\sigma}_{r}\geq\sigma_{r}$. Let us now consider $y\in{\mathcal{Y}}$,
and let $S_{r}(y)$ be the set of the partition ${\mathcal{P}}_{r}$ to which
$y$ belongs, assuming that it has not yet been eliminated at the start of
round $r$. Note that by definition of ${\mathcal{P}}_{r}$, either
$\hat{p}_{r}(S_{r}(y))\leq\hat{p}_{r}(\hat{y}_{r})/2$ or $S_{r}(y)=\\{y\\}$.

We first examine the case $p(y)\leq p(y_{1})/2$. The event $A_{3}$ implies
that $\hat{p}_{r}(y)\leq p(y_{1})/2+\tilde{\sigma}_{r}$ and that
$\hat{p}_{r}(\hat{y}_{r})/2\leq p(\hat{y}_{r})/2+\tilde{\sigma}_{r}/2\leq
p(y_{1})/2+\tilde{\sigma}_{r}/2$. Thus $\hat{p}_{r}(S_{r}(y))\leq
p(y_{1})/2+\tilde{\sigma}_{r}$. Thanks to $A_{3}$ again, we know that
$\hat{p}_{r}(\hat{y}_{r})\geq p(y_{1})-\tilde{\sigma}_{r}$. Hence

$\hat{p}_{r}(\hat{y}_{r})-\hat{p}_{r}(S_{r}(y))\geq
p(y_{1})/2-2\tilde{\sigma}_{r}.$

If $p(y_{1})/2\geq 6\tilde{\sigma}_{r}$, then

$\hat{p}_{r}(\hat{y}_{r})-\hat{p}_{r}(S_{r}(y))\geq
4\tilde{\sigma}_{r}\geq\sigma_{r}$

and $S_{r}(y)$ gets eliminated at the end of round $r$.

Now let us consider the case $p(y)\geq p(y_{1})/2$. Similarly, the event
$A_{3}$ ensures that $\hat{p}_{r}(y)\leq p(y)+\tilde{\sigma}_{r}$ and that

$\hat{p}_{r}(S_{r}(y))\leq\hat{p}_{r}(\hat{y}_{r})/2\leq
p(y_{1})/2+\tilde{\sigma}_{r}/2\leq p(y)+\tilde{\sigma}_{r}/2$

in the case where $|S_{r}(y)|\geq 2$, hence that

$\hat{p}_{r}(S_{r}(y))\leq p(y)+\tilde{\sigma}_{r}.$

As above, $\hat{p}_{r}(\hat{y}_{r})\geq p(y_{1})-\tilde{\sigma}_{r}$, hence

$\hat{p}_{r}(\hat{y}_{r})-\hat{p}_{r}(S_{r}(y))\geq
p(y_{1})-p(y)-2\tilde{\sigma}_{r}.$

If $p(y_{1})-p(y)\geq 6\tilde{\sigma}_{r}$, then

$\hat{p}_{r}(\hat{y}_{r})-\hat{p}_{r}(S_{r}(y))\geq
4\tilde{\sigma}_{r}\geq\sigma_{r},$

and $S_{r}(y)$ must be eliminated at the end of round $r$.

We have shown that if $p(y)\leq p(y_{1})/2$, $y$ is eliminated at the latest
at the end of the first round $r$ for which $p(y_{1})/2\geq
6\tilde{\sigma}_{r}$, and if $p(y)\geq p(y_{1})/2$, it is eliminated at the
latest at the end of the first round for which $p(y_{1})-p(y)\geq
6\tilde{\sigma}_{r}$. Note that as in the proof of Theorem 5, the condition
$\rho>6\tilde{\sigma}_{r}$ (for $\rho\in\\{p(y_{1})-p(y),p(y_{1})/2\\}$) is
equivalent to

$n_{r}>108\rho^{-2}p(y_{1})\ln(1/\delta_{r}),$

which defines the elimination time $r(y)$. ∎

The previous lemma allows us to bound $\mathbf{1}_{Y_{i,r}\notin S_{r}}$ by
$\mathbf{1}_{r\leq r(y)}$. We are now left with the computation of the upper
bound in Equation (25). We provide the derivations in Appendix .6, which yield
the following lemma.

######  Lemma 19.

With the events $(A_{i})_{i\in[4]}$ as defined in Lemma 15,

$\displaystyle\frac{{\mathbb{E}}\left[T\,\middle|\,\mathopen{}(A_{i})_{i\in[4]}\right]}{\ln(1/\delta)}\leq
432\frac{p(y_{1})}{(p(y_{1})-p(y_{2}))^{2}}p(y_{1})$
$\displaystyle+864\sum_{y\in{\mathcal{Y}}\text{ s.t.
}p(y)<p(y_{1})/2}p(y)\frac{4}{p(y_{1})^{2}}p(y_{1})\left\lceil\log_{2}\left(\frac{10}{p(y_{1})}\right)\right\rceil$
$\displaystyle+864\sum_{y\in{\mathcal{Y}}\text{ s.t. }p(y)\geq
p(y_{1})/2}p(y)\frac{1}{(p(y_{1})-p(y))^{2}}p(y_{1})\left\lceil\log_{2}\left(\frac{10}{p(y_{1})}\right)\right\rceil+o(1).$

Note that since

$\max\left((p(y_{1})-p(y))^{-2},(p(y_{1})/2)^{-2}\right)\leq
4(p(y_{1})-p(y))^{-2}$

for any $y\in{\mathcal{Y}}$, we can weaken and simplify this upper bound as

$\frac{{\mathbb{E}}\left[T\,\middle|\,\mathopen{}(A_{i})_{i\in[4]}\right]}{\ln(1/\delta)}\leq
432\frac{p(y_{1})^{2}}{(p(y_{1})-p(y_{2}))^{2}}+3456\sum_{y\in{\mathcal{Y}}}\frac{p(y_{i})p(y_{1})}{\nabla_{i}^{2}}\left\lceil\log_{2}\left(\frac{10}{p(y_{1})}\right)\right\rceil+o(1)).$

This completes the proof.

### Aside on “Forever Running” Algorithms

It is easy to reuse parts of the proofs of Theorems 5 and 6 to turn algorithms
that output the empirical mode, namely the Exhaustive, Adaptive and Truncated
Search Algorithms, into $(\epsilon,\delta)$-PAC algorithms for $\epsilon\geq
0$ and $\delta>0$. On can also modify the Elimination and Set Elimination
Algorithms to turn them into algorithms that run forever for ever increasing
accuracy by adapting the doubling trick credited to Auer et al. (1995) to our
partial feedback setting. The asymptotic expected number of queries as a
function of the probability of error $\delta$ would scale in the same way as
for the initial algorithms, though with worse constants.

## Conclusion

This article introduces Problem 1, a new framework in which to formalize the
problem of active learning with weak supervision. It presents three important
ideas on how to solve it, namely the use of adaptive entropy coding, coarse
sufficient statistics and confidence intervals, and illustrates these ideas
through increasingly complex algorithms. Finally, it combines those ideas into
Algorithm 9, which provably only needs an expected number

$\displaystyle{\mathbb{E}}\left[T\right]$
$\displaystyle\leq\Bigg{(}C_{1}\Delta_{2}^{-2}+C_{2}\sum_{i\leq
m}\Delta_{i}^{-2}\left\lceil\log_{2}\Big{(}\frac{10}{p(y_{1})}\Big{)}\right\rceil+o(1)\Bigg{)}\log(1/\delta),$

of queries to identify the mode with probability at least $1-\delta$ (assuming
that $p(y_{1})$ is bounded away from $1$).

##

###  .2 Information Projection Computation

Recall the definitions of the set

${\mathcal{Q}}=\left\\{q\in
P({\mathcal{Y}})\,\middle|\,\mathopen{}\operatorname*{arg\,max}q(y)\neq\operatorname*{arg\,max}p(y)\right\\},$
${\mathcal{Q}}_{n,-}=\left\\{q\in P({\mathcal{Y}})\cap
n^{-1}\cdot{\mathbb{N}}^{\mathcal{Y}}\,\middle|\,\mathopen{}y_{1}\notin\operatorname*{arg\,max}q(y)\right\\},$
(8)

and

${\mathcal{Q}}_{n,+}=\left\\{q\in P({\mathcal{Y}})\cap
n^{-1}\cdot{\mathbb{N}}^{\mathcal{Y}}\,\middle|\,\mathopen{}\operatorname*{arg\,max}q(y)\neq\operatorname*{arg\,max}p(y)\right\\}.$
(9)

In this section, we prove Lemma 1 from Section 2, which we restate here for
the reader’s convenience, as well as some related results.

See 1

Lemma 1 is a substatement of Lemmas 21 and 23 below. We first prove the
following intermediate result.

######  Lemma 20.

Let ${\mathcal{Y}}=\\{y_{1},\ldots,y_{m}\\}$. Let
$q,p\in{\mathbb{P}}({\mathcal{Y}})$ and
$y^{\prime},y^{\prime\prime}\in{\mathcal{Y}}$ be such that

$\frac{q(y^{\prime})}{p(y^{\prime})}>\frac{q(y^{\prime\prime})}{p(y^{\prime\prime})}.$

Let us define for
$\epsilon\in(0,\min\\{q(y^{\prime}),1-q(y^{\prime\prime})\\}]$, the
distribution $q_{\epsilon}\in P({\mathcal{Y}})$

$q_{\epsilon}(y)=\left\\{\begin{array}[]{ll}q(y)-\epsilon&\text{if
}y=y^{\prime}\\\ q(y)+\epsilon&\text{if }y=y^{\prime\prime}\\\
q(y)&\text{otherwise,}\end{array}\right.$

then

$\epsilon\in\left(0,\frac{q(y^{\prime})p(y^{\prime\prime})-q(y^{\prime\prime})p(y^{\prime})}{p(y^{\prime})+q(y^{\prime})}\right]\qquad\Rightarrow\qquad
D(q_{\epsilon}\|p)<D(q\|p).$

###### Proof.

Indeed,

$D(q_{\epsilon}\|p)=(q(y^{\prime})-\epsilon)\log\left(\frac{q(y^{\prime})-\epsilon}{p(y^{\prime})}\right)+(q(y^{\prime\prime})+\epsilon)\log\left(\frac{q(y^{\prime\prime})+\epsilon}{p(y^{\prime\prime})}\right)+C(q,p),$

where $C(q,p)$ are some terms that do not depend on $\epsilon$, and

$\frac{\mathop{}\\!\mathrm{d}}{\mathop{}\\!\mathrm{d}\epsilon}D(q_{\epsilon}\|p)=\log\left(\frac{p(y^{\prime})(q(y^{\prime\prime})+\epsilon)}{(q(y^{\prime})-\epsilon)p(y^{\prime\prime})}\right)$

is strictly negative for $\epsilon>0$ such that
$\frac{p(y^{\prime})(q(y^{\prime\prime})+\epsilon)}{(q(y^{\prime})-\epsilon)p(y^{\prime\prime})}<1$,
which leads to the condition on $\epsilon$. ∎

We can now characterize the information projection $\min_{q\in Q}D(q\|p)$.

######  Lemma 21.

Let ${\mathcal{Y}}=\\{y_{1},\ldots,y_{m}\\}$ and
$p\in{\mathbb{P}}({\mathcal{Y}})$ be such that $p(y_{1})>p(y_{2})>0$ and
$p(y_{i-1})\geq p(y_{i})$ for all $i=2,\ldots,m$. Define

${\mathcal{Q}}:=\left\\{q\in
P({\mathcal{Y}})\,\middle|\,\mathopen{}\exists\,y\in{\mathcal{Y}}\setminus\\{y_{1}\\}\text{
s.t. }q(y)\geq q(y_{1})\right\\}.$

There exists $q^{*}\in{\mathcal{Q}}$ such that $D(q^{*}\|p)=\min_{q\in
Q}D(q\|p)$, and999This characterization of $q^{*}$ is exact up to some
renaming of classes $y$ with equal probability masses.

$q^{*}(y_{1})=q^{*}(y_{2})=\frac{1-\lambda(1-p(y_{1})-p(y_{2}))}{2}$

and

$q^{*}(y_{i})=\lambda p(y_{i})\quad\forall i\in\\{3,\ldots,m\\}$

for

$\lambda=\frac{1}{1-(\sqrt{p(y_{1})}-\sqrt{p(y_{2})})^{2}}.$

It satisfies

$D(q^{*}\|p)=-\log(1-(\sqrt{p(y_{1})}-\sqrt{p(y_{2})})^{2}).$

###### Proof.

The statement is trivial when $m=2$ or $\sum_{i=3}^{m}p(y_{i})=0$ (with
$\lambda=1$), which we assume henceforth not to be the case.

Observe first that if $y\in{\mathcal{Y}}$ is such that $p(y)=0$, then
necessarily $q^{*}(y)=0$. Indeed, if $p(y)=0$ and $q^{*}(y)>0$, then
$D(q^{*}\|p)=\infty$, while $\min_{q\in Q}D(q\|p)<0$ (consider for example
$q\in{\mathbb{P}}({\mathcal{Y}})$ defined as
$q(y_{1})=q(y_{2})=(p(y_{1})+p(y_{2}))/2$ and $q(y)=p(y)$ for all
$y\in{\mathcal{Y}}\backslash\\{y_{1},y_{*}\\}$).

Let $y_{*}\in{\mathcal{Y}}\setminus\left\\{y_{1}\right\\}$ be a mode of
$q^{*}$, which exists by hypothesis. We must have

$\forall\,y^{\prime},y^{\prime\prime}\in{\mathcal{Y}}\setminus\\{y_{*},y_{1}\\}\quad\text{s.t.
}p(y^{\prime})\neq 0,p(y^{\prime\prime})\neq
0,\qquad\frac{q(y^{\prime})}{p(y^{\prime})}\leq\frac{q(y^{\prime\prime})}{p(y^{\prime\prime})},$

as otherwise one could apply Lemma 20 to $y^{\prime}$ and $y^{\prime\prime}$
to find $q_{\epsilon}\in{\mathcal{Q}}$ such that
$q_{\epsilon}(y_{1})=q(y_{1})\leq q(y_{*})=q_{\epsilon}$, hence
$q_{\epsilon}\in{\mathcal{Q}}$, and $D(q_{\epsilon}\|p)<D(q\|p)$, which would
contradict the definition of $q^{*}$.

In particular, this implies by symmetry that

$\exists\,\lambda\geq
0\quad\text{s.t.}\quad\forall\,y\in{\mathcal{Y}}\setminus\left\\{y_{1},y_{*}\right\\}\quad
q(y)=\lambda p(y).$

We observe that

$q^{*}(y_{1})=q^{*}(y_{*}).$

Indeed, we always have $q^{*}(y_{*})/p(y_{*})>q^{*}(y_{1})/p(y_{1})$, since
$q^{*}(y_{*})\geq q^{*}(y_{1})$ and $p(y_{1})>p(y_{*})$. If
$q^{*}(y_{1})<q^{*}(y_{*})$, we could apply Lemma 20 to $y_{1},y_{*}$ with a
small enough $\epsilon$ to find $q_{\epsilon}\in Q$ with
$D(q_{\epsilon}\|p)<D(q\|p)$.

Now let us show that

$\exists\,y\in\\{y\in{\mathcal{Y}}\setminus\\{y_{1}\\}|q^{*}(y)=q^{*}(y_{*})\\}\quad\text{
s.t.}\quad p(y)=p(y_{2}).$

Indeed, assume that it is not the case: then $y_{*}$ does not satisfy those
conditions, hence it must be such that $p(y_{*})<p(y_{2})$, and $y_{2}$ does
not satisfy those conditions, hence it must be such that
$q^{*}(y_{*})>q^{*}(y_{2})$. Consider the distribution $q$ defined as
$q(y_{2})=q^{*}(y_{*})$, $q(y_{*})=q^{*}(y_{2})$ and $q(y)=q^{*}(y)$ for all
$y\in{\mathcal{Y}}\setminus\\{y_{2},y_{*}\\}$. Then $q\in Q$, and

$\displaystyle D(q^{*}\|p)-D(q\|p)$
$\displaystyle=q^{*}(y_{*})\log(q^{*}(y_{*})/p(y_{*}))+q^{*}(y_{2})\log(q^{*}(y_{2})/p(y_{2}))$
$\displaystyle\qquad-q^{*}(y_{2})\log(q^{*}(y_{2})/p(y_{*}))-q^{*}(y_{*})\log(q^{*}(y_{*})/p(y_{2}))$
$\displaystyle=q^{*}(y_{*})\log(p(y_{2})/p(y_{*}))+q^{*}(y_{2})\log(p(y_{*})/p(y_{2}))$
$\displaystyle=(q^{*}(y_{*})-q^{*}(y_{2}))\log(p(y_{2})/p(y_{*}))>0,$

leading to a contradiction. Hence there exists
$\tilde{y}\in\\{y\in{\mathcal{Y}}\setminus\\{y_{1}\\}|q^{*}(y)=q^{*}(y_{*})\\}$
such that $p(\tilde{y})=p(y_{2})$. Consider now the distribution $q$ defined
as $q(\tilde{y})=q^{*}(y_{2})$, $q(y_{2})=q^{*}(\tilde{y})$ and
$q(y)=q^{*}(y)$ for all $y\in{\mathcal{Y}}\backslash\\{y^{*},\tilde{y}\\}$;
then $q\in{\mathcal{Q}}$ and $D(q\|p)=D(q^{*}\|p)$, and without loss of
generality we can rename $q$ into $q^{*}$ for the remainder of the proof.

Let us write $x=q^{*}(y_{1})=q^{*}(y_{2})$. As

$1=\sum_{i=1}^{m}q^{*}(y_{i})=2x+\sum_{i=3}^{m}\lambda
p(y_{i})=2x+\lambda(1-p(y_{1})-p(y_{2})),$

we find that $x=(1-\lambda(1-p(y_{1})-p(y_{2})))/2$.

We should have

$\frac{q^{*}(y_{1})}{p(y_{1})}\leq\lambda=\frac{q^{*}(y)}{p(y)}\leq\frac{q^{*}(y_{2})}{p(y_{2})}$

for $y\in{\mathcal{Y}}\setminus\\{y_{1},y_{2}\\}$, as we could otherwise apply
Lemma 20 to reach a contradiction with the definition of $q^{*}$. This leads
to the constraint

$\frac{x}{p(y_{1})}=\frac{1-\lambda(1-p(y_{1})-p(y_{2}))}{2p(y_{1})}\leq\lambda,\text{
i.e. }\lambda\geq\frac{1}{(1+p(y_{1})-p(y_{2}))},$

as well as

$\lambda\leq\frac{x}{p(y_{2})}=\frac{1-\lambda(1-p(y_{1})-p(y_{2}))}{2p(y_{2})},\text{
i.e. }\lambda\leq\frac{1}{(1-p(y_{1})+p(y_{2}))}.$

Hence we have shown that $q^{*}$ must be some distribution $q_{\lambda}$
defined as $q_{\lambda}(y_{i})=\lambda p(y_{i})$ for all $i\geq 3$ and

$q_{\lambda}(y_{1})=q_{\lambda}(y_{2})=\frac{1-\lambda(1-p(y_{1})-p(y_{2}))}{2}.$

for some

$\lambda\in\left[\frac{1}{1+p(y_{1})-p(y_{2})},\frac{1}{1-p(y_{1})+p(y_{2})}\right].$

If we show that $D(q_{\lambda}\|p)$ is minimized for
$\lambda=\frac{1}{1-(\sqrt{p(y_{1})}-\sqrt{p(y_{2})})^{2}}$ and that
$D(q^{*}\|p)=-\log(1-(\sqrt{p(y_{1})}-\sqrt{p(y_{2})})^{2})$, the proof is
complete; this is the statement of Lemma 22 below. ∎

######  Lemma 22.

Consider the family of distributions $q_{\lambda}$ defined for
$\lambda\in[0,(1-p(y_{1})-p(y_{2}))^{-1}]$ as $q_{\lambda}(y_{i})=\lambda
p(y_{i})$ for all $i\geq 3$ and

$q_{\lambda}(y_{1})=q_{\lambda}(y_{2})=\frac{1-\lambda(1-p(y_{1})-p(y_{2}))}{2}.$

Then

$\operatorname*{arg\,min}_{\lambda}D(q_{\lambda}\|p)=\frac{1}{1-(\sqrt{p(y_{1})}-\sqrt{p(y_{2})})^{2}}$

and

$\min_{\lambda}D(q_{\lambda}\|p)=\\-\log(1-(\sqrt{p(y_{1})}-\sqrt{p(y_{2})})^{2}).$

###### Proof.

We compute

$\displaystyle D(q_{\lambda}\|p)$
$\displaystyle=\frac{1-\lambda(1-p(y_{1})-p(y_{2}))}{2}\log\left(\frac{(1-\lambda(1-p(y_{1})-p(y_{2})))^{2}}{4p(y_{1})p(y_{2})}\right)$
$\displaystyle\qquad\qquad+\sum_{i=3}^{m}\lambda p(y_{i})\log(\lambda)$
$\displaystyle=\frac{1-a\lambda}{2}\log\left(\frac{(1-a\lambda)^{2}}{b}\right)+a\lambda\log(\lambda),$

where $a=1-p(y_{1})-p(y_{2})$ and $b=4p(y_{1})p(y_{2})$, which implies that
the derivative reads

$\displaystyle\frac{\mathop{}\\!\mathrm{d}}{\mathop{}\\!\mathrm{d}\lambda}D(q_{\lambda}\|p)$
$\displaystyle=-\frac{a}{2}\log\left(\frac{(1-a\lambda)^{2}}{b}\right)+(1-a\lambda)\cdot\frac{-a}{1-a\lambda}+a\log(\lambda)+a$
$\displaystyle=\frac{a}{2}\log\left(\frac{b\lambda^{2}}{(1-a\lambda)^{2}}\right)$
$\displaystyle=\frac{1-p(y_{1})-p(y_{2})}{2}\log\left(\frac{4p(y_{1})p(y_{2})\lambda^{2}}{(1-\lambda(1-p(y_{1})-p(y_{2})))^{2}}\right).$

We can study the sign of this derivative,

$\displaystyle\operatorname{sign}\left(\frac{\mathop{}\\!\mathrm{d}}{\mathop{}\\!\mathrm{d}\lambda}D(q_{\lambda}\|p)\right)$
$\displaystyle=\operatorname{sign}\left(\frac{b\lambda^{2}}{(1-a\lambda)^{2}}-1\right)=\operatorname{sign}\left(b\lambda^{2}-(1-a\lambda)^{2}\right)$
$\displaystyle=\operatorname{sign}\left((b-a^{2})\lambda^{2}+2a\lambda-1\right).$

The roots of this polynomial are

$\displaystyle\lambda_{\pm}$
$\displaystyle=\frac{-a\pm\sqrt{a^{2}+b-a^{2}}}{b-a^{2}}=\frac{-a\pm\sqrt{b}}{b-a^{2}}=\frac{1}{a\pm\sqrt{b}}$
$\displaystyle=\frac{1}{1-p(y_{1})-p(y_{2})\pm
2\sqrt{p(y_{1})p(y_{2})}}=\frac{1}{1-(\sqrt{p(y_{1})}\mp\sqrt{p(y_{2})})^{2}}.$

The sign of the leading coefficient of the polynomial is

$\displaystyle\operatorname{sign}(b-a^{2})$
$\displaystyle=\operatorname{sign}(\sqrt{b}-a)=\operatorname{sign}(2\sqrt{p(y_{1})p(y_{2})}+p(y_{1})+p(y_{2})-1)$
$\displaystyle=\operatorname{sign}((\sqrt{p(y_{1})}+\sqrt{p(y_{2})})^{2}-1)=\operatorname{sign}(\sqrt{p(y_{1})}+\sqrt{p(y_{2})}-1).$

As a consequence, there are two possibilities.

If $\sqrt{p(y_{1})}+\sqrt{p(y_{2})}\geq 1$, then $b-a^{2}$, as well as
$\sqrt{b}-a$, is positive, and
$\mathop{}\\!\mathrm{d}D/\mathop{}\\!\mathrm{d}\lambda$ is negative from
$\lambda_{-}=(a-\sqrt{b})^{-1}\leq 0$ to $\lambda_{+}=(a+\sqrt{b})^{-1}$ and
positive afterwards, in which case $\lambda_{+}$ is the minimizer of
$D(q_{\lambda}\|p)$.

If $\sqrt{p(y_{1})}+\sqrt{p(y_{2})}\leq 1$, then $b-a^{2}$, as well as
$\sqrt{b}-a$ is negative, and
$\mathop{}\\!\mathrm{d}D/\mathop{}\\!\mathrm{d}\lambda$ is negative from
$\lambda=0$ to $\lambda_{+}=(a+\sqrt{b})^{-1}$, then positive until
$\lambda_{-}=(a-\sqrt{b})^{-1}$ and negative afterwards, in which case either
$\lambda_{+}$ or the right extremity of the domain of $\lambda$ is the
minimizer of $D(q_{\lambda}\|p)$ on the domain of $\lambda$. Yet this right
extremity is $(1-p(y_{1})-p(y_{2}))^{-1}$ is smaller than $\lambda_{-}$, since

$p(y_{1})+p(y_{2})\leq
p(y_{1})+2\sqrt{p(y_{1})p(y_{2})}+p(y_{2})=(\sqrt{p(y_{1})}+\sqrt{p(y_{2})})^{2},$

implies

$(1-p(y_{1})-p(y_{2}))^{-1}\leq(1-(\sqrt{p(y_{1})}+\sqrt{p(y_{2})})^{2})^{-1}=\lambda_{-},$

hence the minimizer has to be $\lambda_{+}$.

We conclude that $\lambda_{+}$ is always the minimizer of
$D(q_{\lambda_{+}}\|p)$. Hence, using that $\lambda_{+}$ solves
$b\lambda^{2}=(1-a\lambda)^{2}$,

$\displaystyle D(q_{\lambda_{+}}\|p)$
$\displaystyle=\frac{1-a\lambda_{+}}{2}\log\left(\frac{(1-a\lambda_{+})^{2}}{b}\right)+a\lambda_{+}\log(\lambda_{+})$
$\displaystyle=\frac{1-a\lambda_{+}}{2}\log\left(\lambda_{+}^{2}\right)+a\lambda_{+}\log(\lambda_{+})=\log(\lambda_{+}).$

This ends the computation of the information projection. ∎

To close this subsection, let us finally prove the upper bound on
$\min_{q\in{\mathcal{Q}}_{n,-}}D(q\|p)$ from Lemma 1 (in fact, we prove a
little more).

######  Lemma 23.

Let ${\mathcal{Y}}=\\{y_{1},\ldots,y_{m}\\}$, $n\geq 1$,

${\mathcal{Q}}_{n,-}=\left\\{q\in P({\mathcal{Y}})\cap
n^{-1}\cdot{\mathbb{N}}^{\mathcal{Y}}\,\middle|\,\mathopen{}y_{1}\notin\operatorname*{arg\,max}q(y)\right\\}$

and

${\mathcal{Q}}=\left\\{q\in
P({\mathcal{Y}})\,\middle|\,\mathopen{}\operatorname*{arg\,max}q(y)\neq\operatorname*{arg\,max}p(y)\right\\}.$

Then

$\displaystyle\min_{q\in{\mathcal{Q}}_{n,-}}D(q\|p)\leq\min_{q\in{\mathcal{Q}}}D(q\|p)$
$\displaystyle\quad+\frac{m}{n}\Biggl{(}\max\left\\{-\log(\lambda),\log\left(\frac{1-\lambda(1-p(y_{1})-p(y_{2}))}{2p(y_{2})}\right)\right\\}+1\Biggl{)}$
$\displaystyle\quad+\frac{1}{n}\sum_{y\in{\mathcal{Y}}_{>0}}\log\left(1+\frac{1}{nq^{*}(y)}\right)$

where $\lambda=(1-(\sqrt{p(y_{1})}-\sqrt{p(y_{2})})^{2})^{-1}$ and
${\mathcal{Y}}_{>0}=\\{y\in{\mathcal{Y}}\;|p(y)\neq 0\\}$.

###### Proof.

Let $q^{*}\in\operatorname*{arg\,min}_{q\in{\mathcal{Q}}}D(q\|p)$ be such that
$q^{*}(y_{1})=q^{*}(y_{2})=\frac{1-\lambda(1-p(y_{1})-p(y_{2}))}{2}$ and
$q^{*}(y)=p(y)$ for $\lambda=(1-(\sqrt{p(y_{1})}-\sqrt{p(y_{2})})^{2})^{-1}$
(as in Lemma 21). Then for $n>m$, one can construct
$q_{n}\in{\mathcal{Q}}_{n,+}$ such that $q_{n}(y)\leq q^{*}(y)+1/n$ for all
$y\in{\mathcal{Y}}$ and such that $q_{n}(y)=0$ if
$y\not\in{\mathcal{Y}}_{>0}$. The general idea is as follows: let $q_{n}(y)=0$
for all $y\not\in{\mathcal{Y}}_{>0}$. Then let $q_{n}(y_{1})=\left\lfloor
q^{*}(y_{1})n\right\rfloor/n$ and $q_{n}(y_{2})=\left(\left\lfloor
q^{*}(y_{1})n\right\rfloor+1\right)/n$, and $q_{n}(y)=\left(\left\lfloor
q^{*}(y)n\right\rfloor+\epsilon_{y,n}\right)/n$ for
$y\in{\mathcal{Y}}\backslash\\{y_{1},y_{2}\\}$ such that $q^{*}(y)\neq 0$,
with $\epsilon_{y,n}\in\\{0,1\\}$ chosen so that
$\sum_{y\in{\mathcal{Y}}}q_{n}(y)=1$ (small adjustments can be necessary
depending on whether $q^{*}(y_{1})n\in{\mathbb{N}}$ etc.).

Then

$D(q_{n}\|p)=\sum_{y\in{\mathcal{Y}}}q_{n}(y)\log\left(\frac{q_{n}(y)}{p(y)}\right)=\sum_{y\in{\mathcal{Y}}}q_{n}(y)\log\left(\frac{q^{*}(y)}{p(y)}\right)+\sum_{y\in{\mathcal{Y}}}q_{n}(y)\log\left(\frac{q_{n}(y)}{q^{*}(y)}\right).$

The first sum can be bounded as

$\displaystyle\sum_{y\in{\mathcal{Y}}}q_{n}(y)\log\left(\frac{q^{*}(y)}{p(y)}\right)$
$\displaystyle=\sum_{y\in{\mathcal{Y}}}q^{*}(y)\log\left(\frac{q^{*}(y)}{p(y)}\right)+\sum_{y\in{\mathcal{Y}}}(q_{n}(y)-q^{*}(y))\log\left(\frac{q^{*}(y)}{p(y)}\right)$
$\displaystyle\leq
D(q^{*}\|p)+\frac{m}{n}\max\left\\{\log(\lambda),\log\left(\frac{q^{*}(y_{2})}{p(y_{2})}\right)\right\\},$

and the second sum can be bounded as follows

$\displaystyle\sum_{y\in{\mathcal{Y}}}q_{n}(y)\log\left(\frac{q_{n}(y)}{q^{*}(y)}\right)$
$\displaystyle\leq\sum_{y\in{\mathcal{Y}}_{>0}}(q^{*}(y)+1/n)\log\left(1+\frac{1}{nq^{*}(y)}\right)$
$\displaystyle\leq\sum_{y\in{\mathcal{Y}}_{>0}}q^{*}(y)\log\left(1+\frac{1}{nq^{*}(y)}\right)+\sum_{y\in{\mathcal{Y}}_{>0}}\frac{1}{n}\log\left(1+\frac{1}{nq^{*}(y)}\right)$
$\displaystyle\leq\sum_{y\in{\mathcal{Y}}_{>0}}q^{*}(y)\frac{1}{nq^{*}(y)}+\sum_{y\in{\mathcal{Y}}_{>0}}\frac{1}{n}\log\left(1+\frac{1}{nq^{*}(y)}\right)$
$\displaystyle\leq\frac{m}{n}+\frac{1}{n}\sum_{y\in{\mathcal{Y}}_{>0}}\log\left(1+\frac{1}{nq^{*}(y)}\right).$

Thus

$\displaystyle\min_{q\in{\mathcal{Q}}_{n,-}}D(q\|p)\leq D(q_{n}\|p)$
$\displaystyle\leq$ $\displaystyle
D(q^{*}\|p)+\frac{m}{n}\left(\max\left\\{\log(\lambda),\log\left(\frac{q^{*}(y_{2})}{p(y_{2})}\right)\right\\}+1\right)+\frac{1}{n}\sum_{y\in{\mathcal{Y}}_{>0}}\log\left(1+\frac{1}{nq^{*}(y)}\right).$

This concludes the proof of the Lemma. ∎

An alternative construction yields

$\min_{q\in{\mathcal{Q}}_{n,-}}D(q\|p)\leq
D(q^{*}\|p)+C(m,p(y_{1}),p(y_{2}))/\sqrt{n}$

for some constant $C(m,p(y_{1}),p(y_{2}))$ that only depends on
$m,p(y_{1}),p(y_{2})$ (rather than on all $p(y)$), though at the cost of a
less favorable asymptotic behaviour in $n$.

#### Sanity Check with Cramér-Chernoff method

We remark that the upper bound of Theorem 1 can be proved more directly.
Consider first the simple union bound

$\displaystyle{\mathbb{P}}(\hat{y}_{n}\neq y_{1})$
$\displaystyle={\mathbb{P}}\big{(}\min_{i\neq
1}\sum_{j\in[n]}\mathbf{1}_{Y_{j}=y_{1}}-\mathbf{1}_{Y_{j}=y_{i}}\leq
0\big{)}={\mathbb{P}}\big{(}\cup_{i\neq
1}\big{\\{}\sum_{j\in[n]}\mathbf{1}_{Y_{j}=y_{1}}-\mathbf{1}_{Y_{j}=y_{i}}\leq
0\big{\\}}\big{)}$ $\displaystyle\leq\sum_{i\neq
1}{\mathbb{P}}\big{(}\sum_{j\in[n]}\mathbf{1}_{Y_{j}=y_{1}}-\mathbf{1}_{Y_{j}=y_{i}}\leq
0\big{)}\leq(m-1){\mathbb{P}}\big{(}\sum_{j\in[n]}\mathbf{1}_{Y_{j}=y_{1}}-\mathbf{1}_{Y_{j}=y_{2}}\leq
0\big{)}.$

The term
${\mathbb{P}}\big{(}\sum_{j\in[n]}\mathbf{1}_{Y_{j}=y_{1}}-\mathbf{1}_{Y_{j}=y_{2}}\leq
0\big{)}$ can be bounded with Chernoff’s method:

######  Lemma 24 (Chernoff’s bound).

Let $p\in P({\mathcal{Y}})$ be a distribution over ${\mathcal{Y}}$, and
$(Y_{j})$ be $n$ independent samples distributed according to $p$ with
$p(y_{1})>p(y_{i})$. Then

${\mathbb{P}}(\sum_{j\in[n]}\mathbf{1}_{Y_{j}=y_{1}}-\mathbf{1}_{Y_{j}=y_{i}}\leq
0)\leq\exp\left(-n\Delta_{i}^{2}\right),$

where $\Delta_{i}$ is defined in Equation (5).

###### Proof.

This can be proven using the fact that, for a random variable $X$,

${\mathbb{P}}(X\geq 0)=\inf_{t>0}{\mathbb{P}}(\exp(tX)\geq
1)\leq\inf_{t>0}{\mathbb{E}}[e^{tX}].$

As a consequence, with $X=\sum X_{j}$ and
$X_{j}=\mathbf{1}_{Y_{j}=y_{i}}-\mathbf{1}_{Y_{j}=y_{1}}$,

${\mathbb{P}}(X\geq
0)\leq\inf_{t>0}{\mathbb{E}}[e^{tX}]=\inf_{t>0}{\mathbb{E}}[e^{tX_{1}}]^{n}=\inf_{t>0}\exp(n\ln({\mathbb{E}}[e^{tX_{1}}])).$

We are left with a simple computation,

$\displaystyle\inf_{t>0}{\mathbb{E}}[e^{tX_{1}}]$
$\displaystyle=\inf_{t>0}\left(e^{t}p(y_{i})+(1-p(y_{i})-p(y_{1}))+e^{-t}p(y_{1})\right)$
$\displaystyle=\left(2\sqrt{p(y_{1})p(y_{i})}+(1-p(y_{1})-p(y_{i}))\right)=\left(1-(\sqrt{p(y_{1})}-\sqrt{p(y_{i})})^{2}\right)$

where we used that the infimum is found for
$e^{t}=\sqrt{p(y_{1})/p(y_{i})}>1$. ∎

In fact, we know from Cramér (1938) that Chernoff’s bound is asymptotically
exponentially tight. As we also have

$\displaystyle{\mathbb{P}}(\hat{y}_{n}\neq
y_{1})\geq{\mathbb{P}}\big{(}\sum_{j\in[n]}\mathbf{1}_{Y_{j}=y_{1}}-\mathbf{1}_{Y_{j}=y_{2}}\leq
0\big{)},$

we get that

$\lim\frac{\ln({\mathbb{P}}(\hat{y}_{n}\neq
y_{1}))}{n}=\lim\frac{\ln({\mathbb{P}}\big{(}\sum_{j\in[n]}\mathbf{1}_{Y_{j}=y_{1}}-\mathbf{1}_{Y_{j}=y_{2}}\leq
0)\big{)}}{n}=\Delta_{2}^{2}.$

As mentioned in Section 2, Dinwoodie (1992) states that
$\ln({\mathbb{P}}(\hat{y}_{n}\neq y_{1}))/n$ is always below
$-\min_{q\in{\mathcal{Q}}}D(q\|p)$, while Sanov (1957) states that
$\ln({\mathbb{P}}(\hat{y}_{n}\neq y_{1}))/n$ converges to
$-\min_{q\in{\mathcal{Q}}}D(q\|p)$ as $n$ grows large when ${\mathcal{Y}}$ is
discrete. This shows without any further computations that
$\min_{q\in{\mathcal{Q}}}D(q\|p)=\Delta_{2}^{2}$, and implies the upper bound
of Theorem 1.

###  .3 Additional Proofs for Section 3

See 3

###### Proof.

Let us proceed by induction on $\operatorname{depth}_{\mathcal{T}}(V)$. If
$\operatorname{depth}_{\mathcal{T}}(V)=0$, i.e. $V=R$, or if
$\operatorname{depth}_{\mathcal{T}}(V)=1$, the statement is trivial. Let us
assume that $\operatorname{depth}_{\mathcal{T}}(V)\geq 2$. At some point
during the construction of ${\mathcal{T}}$, the element $V$ was merged with
another element $V^{\prime}$ to create a new parent node $P$. At that point,
$V$ and $V^{\prime}$ were the two elements with smallest value $v$ in the heap
${\mathcal{S}}$. If $v(V^{\prime})\geq v(V)$, then $v(P)\geq 2v(V)$. By
induction,

$\displaystyle\operatorname{depth}_{\mathcal{T}}(V)$
$\displaystyle=\operatorname{depth}_{\mathcal{T}}(P)+1\leq
2\left\lceil\log_{2}(1/v(P))\right\rceil+1\leq
2\left\lceil\log_{2}(1/2v(V))\right\rceil+1$ $\displaystyle\leq
2\left\lceil\log_{2}(1/v(V))-1\right\rceil+1\leq
2\left\lceil\log_{2}(1/v(V))\right\rceil.$

If $v(V^{\prime})\leq v(V)$, then any $v(P)\geq v(V)$, and as any other
element $V^{\prime\prime}$ must be such that $v(V^{\prime\prime})\geq v(V)$,
the parent $\tilde{P}$ (which results from the merging of $P$ and some
$V^{\prime\prime})$ of $P$ satisfies $v(\tilde{P})\geq 2v(V)$. By induction,

$\displaystyle\operatorname{depth}_{\mathcal{T}}(V)$
$\displaystyle=\operatorname{depth}_{\mathcal{T}}(\tilde{P})+2\leq
2\left\lceil\log_{2}(1/v(\tilde{P}))\right\rceil+2\leq
2\left\lceil\log_{2}(1/2v(V))\right\rceil+2$ $\displaystyle\leq
2\left\lceil\log_{2}(1/v(V))-1\right\rceil+2\leq
2\left\lceil\log_{2}(1/v(V))\right\rceil.$

This concludes the proof. ∎

See 4

###### Proof.

Looking at it, we see that

$\displaystyle-\sum_{i=1}^{n-1}\sum_{y\in{\mathcal{Y}}}p(y){\mathbb{E}}_{(Y_{j})}\left[1_{\\{|\frac{N_{y,i}-ip(y)}{ip(y)}|\geq\frac{1}{2}\\}}\mathbf{1}_{N_{y,i}\geq
1}\log_{2}\left(\frac{N_{y,i}}{i}\right)\right]$
$\displaystyle\leq\sum_{i=1}^{n-1}\sum_{y\in{\mathcal{Y}}}p(y){\mathbb{P}}\left(\left|\frac{N_{y,i}-ip(y)}{ip(y)}\right|\geq\frac{1}{2}\right)\log_{2}\left(i\right)$

Using a simplification of Chernoff’s bound for Bernoulli variables (Hoeffding,
1963), we get the following bound

${\mathbb{P}}\left(\left|\frac{N_{y,i}-ip(y)}{ip(y)}\right|\geq\frac{1}{2}\right)\leq
2\exp(-\frac{ip(y)}{10}).$

Hence

$\displaystyle\sum_{i=1}^{n-1}\sum_{y\in{\mathcal{Y}}}p(y){\mathbb{P}}\left(\left|\frac{N_{y,i}-ip(y)}{ip(y)}\right|\geq\frac{1}{2}\right)\log_{2}\left(i\right)$
$\displaystyle\leq\sum_{y\in{\mathcal{Y}}}p(y)\log_{2}(n)\sum_{i=1}^{n-1}2\sqrt{2}\exp(-\frac{ip(y)}{10})$
$\displaystyle\leq
2\log_{2}(n)\sum_{y\in{\mathcal{Y}}}\frac{p(y)}{1-e^{-\frac{p(y)}{10}}}\leq
22m\log_{2}(n),$

where the last inequality comes from the fact that $p\mapsto
p/(1-e^{-\frac{p}{10}})$ is upper bounded by $1$ for $p\in[0,1]$. Note that
the constant could be improved, but not dramatically. ∎

See 5

###### Proof.

We will develop the logarithm up to the second order –higher orders do not
easily yield better bounds.

$\displaystyle-\ln(2){\mathbb{E}}_{(Y_{j})}\left[1_{\\{|\frac{N_{y,i}-ip(y)}{ip(y)}|<\frac{1}{2}\\}}\log_{2}\left(\frac{N_{y,i}}{ip(y)}\right)\right]$
$\displaystyle=-\ln(2){\mathbb{E}}_{(Y_{j})}\left[1_{\\{|\frac{N_{y,i}-ip(y)}{ip(y)}|<\frac{1}{2}\\}}\log_{2}\left(1+\frac{N_{y,i}-ip(y)}{ip(y)}\right)\right]$
$\displaystyle=-{\mathbb{E}}_{(Y_{j})}\left[1_{\\{|\frac{N_{y,i}-ip(y)}{ip(y)}|<\frac{1}{2}\\}}\left(\frac{N_{y,i}-ip(y)}{ip(y)}-\frac{1}{2(1+\xi)^{2}}\left(\frac{N_{y,i}-ip(y)}{ip(y)}\right)^{2}\right)\right]$

where $\xi$ is a random variable (inheriting its randomness from the
$(Y_{j})$) that belongs to the interval
$\left[0,\frac{N_{y,i}-ip(y)}{ip(y)}\right]$ if
$\frac{N_{y,i}-ip(y)}{ip(y)}\geq 0$ (respectively
$\left[\frac{N_{y,i}-ip(y)}{ip(y)},0\right]$ if
$\frac{N_{y,i}-ip(y)}{ip(y)}\leq 0$) and depends on the value of $N_{y,i}$.
Note that the Taylor expansion of $x\mapsto\ln(1+x)$ is valid because
$\left|\frac{N_{y,i}-ip(y)}{ip(y)}\right|<\frac{1}{2}$. Now

$\displaystyle
1_{\\{|\frac{N_{y,i}-ip(y)}{ip(y)}|<\frac{1}{2}\\}}\left(-\frac{N_{y,i}-ip(y)}{ip(y)}+\frac{1}{2(1+\xi)^{2}}\left(\frac{N_{y,i}-ip(y)}{ip(y)}\right)^{2}\right)$
$\displaystyle<1_{\\{|\frac{N_{y,i}-ip(y)}{ip(y)}|<\frac{1}{2}\\}}\left(-\frac{N_{y,i}-ip(y)}{ip(y)}+2\left(\frac{N_{y,i}-ip(y)}{ip(y)}\right)^{2}\right)$
$\displaystyle\leq