The exact contents of citations.db main_text.text for this paper — one flattened LaTeX string, title through conclusion, appendix excluded, unmodified except for removing email addresses. This is what our citation measures are computed over.
45,915 characters
Non-Stochastic CDF Estimation Using Threshold Queries
\begin{titlepage}
\maketitle
\begin{abstract}
\rdkedit{Estimating the empirical distribution of a scalar-valued
data set is a basic and fundamental task. In this
paper, we tackle the problem of estimating an empirical
distribution} in a setting with two challenging features.
First, the algorithm does not
directly observe the data; instead, it only asks
a limited number of threshold queries about each sample.
Second, the data are not assumed to be independent
and identically distributed;
instead, we allow for an arbitrary process generating
the samples, including an adaptive adversary. These
considerations are relevant, for example, when modeling a
seller experimenting with posted prices to estimate the
distribution of consumers' willingness to pay for a product:
offering a price and observing a consumer's purchase decision
is equivalent to asking a single threshold query about their value,
and the distribution of consumers' values may be non-stationary
over time, as early adopters may differ markedly from late adopters.
Our main result quantifies, to within a constant factor, the
sample complexity of estimating the empirical CDF of a sequence
of elements of $[n]$, up to $\varepsilon$ additive error,
using one threshold query per sample. The complexity depends only
logarithmically on $n$, and our result can be interpreted
as extending the existing logarithmic-complexity results for
noisy binary search to the more challenging setting where
noise is non-stochastic. Along the way to designing our
algorithm, we consider a more general model in which the
algorithm is allowed to make a limited number of
simultaneous threshold queries on each sample. We
solve this problem using Blackwell's Approachability Theorem
and the exponential weights method.
As a side result of independent interest, we
characterize the minimum number of simultaneous
threshold queries required by deterministic
CDF estimation algorithms.
\end{abstract}
\end{titlepage}
\section{Introduction}
\label{sec:intro}
\rdkedit{
Estimating the empirical distribution of a scalar-valued
data set is a basic and fundamental task. For example,
estimating quantiles of a data stream is one of the
oldest and most well-studied problems in streaming algorithms
\citep{greenwald2001space,karnin2016optimal,manku1998approximate,munro1980selection}, with applications to databases~\citep{greenwald2001space}, network health monitoring~\citep{cormode2004holistic},
and wireless sensor networks \citep{shrivastava2004medians},
among others. Ideally, a data analyst would like to be able
to assume that the data values
are independent and identically distributed,
and that they are directly observable.
However, these assumptions might
be violated in applications of interest.}
\begin{enumerate}
\item In many settings, samples can only be evaluated indirectly
by comparing them to specified thresholds and
learning whether or not each sample is less
than or equal to its corresponding threshold.
This is the case, for instance, when a seller
experiments with varying posted prices in order to estimate
the distribution of consumers' willingness to pay for a
product or service. Other examples arise when
eliciting information about the distribution of
individuals' abilities using pass-fail tests
with a variable level of difficulty (e.g.~swimming tests)
or when evaluating the quality of a new product by asking
consumers to compare it against products of known quality.
(There is ample evidence in the behavioral sciences that
human subjects' quality judgments can be elicited more
reliably with ordinal comparisons than with subjective
numerical ratings
\citep{ali2012,chapelle,larichev,moshkovich}.)
\item The assumption that samples are
independent and identically distributed may also be violated. Returning to the posted-pricing
application, early adopters of a product might differ
markedly from late adopters in their willingness to pay
for the product, and the late adopters' willingness
to pay may even depend on the rate of adoption by earlier
consumers, which in turn depends on the posted prices
they were offered. \vgedit{A similar application arises in an auction setting with repeated bidding - an internet advertiser estimates the distribution of winning bids by varying their own bid. To account for complex influences on the behavior of other bidders, assuming a worst-case input sequence rather than i.i.d. is very useful \citep{weed16-auctions}.}
\end{enumerate}
In this work we tackle the problem of estimating
the empirical distribution of a sequence of numbers
using threshold queries, in a non-stochastic setting
that makes no assumptions about the process by which
the sequence is generated. Our model even allows the
sequence to be constructed by an adaptive adversary.
We assume the algorithm asks one threshold
query about each element of the sequence,
and the query and its answer are revealed
to both parties before the next element
of the sequence is generated by the adversary.
The key question we aim to resolve is: {\em what is the
sample complexity of estimating the empirical CDF of a
distribution on $[n] = \{1,2,\ldots,n\}$ to within $\varepsilon$?}
In more detail, what is the smallest $T$ such that
there exists a randomized algorithm that succeeds,
with probability at least $3/4$, in learning an
estimate of the empirical CDF of
an arbitrary sequence $x_1,\ldots,x_T$
that differs from the true empirical CDF
(in $L_\infty$ norm) by at most $\varepsilon$?
In this paper, we resolve the question to within
a constant factor, by proving asymptotically matching
upper and lower bounds. In fact,
our lower bound is valid even in a stochastic setting
where the elements $x_1,\ldots,x_T$ are i.i.d.~samples
from a distribution on $[n]$. Hence our results reveal,
perhaps surprisingly, that {\em up to a constant factor,
there is no difference in the sample complexity of
CDF estimation in the stochastic and non-stochastic
settings.}
\subsection{Relation to noisy binary search and median estimation}
\label{sec:noisy-binary}
Let us say that $m \in [n]$ is an {\em $\varepsilon$-approximate
median} of the sequence $x_1,x_2,\ldots,x_T$ if at least
$(\frac12 - \varepsilon) T$ elements of the sequence are
less than or equal to $m$ and at least $(\frac12 - \varepsilon) T$
of them are greater than or equal to $m$.
Approximate median estimation reduces to
approximate CDF estimation: if $\hat{F}$ is an
$\varepsilon$-accurate estimate of the empirical CDF of
$x_1,\ldots,x_T$ then an index $m$ that satisfies
$\hat{F}(m-1) < \frac12 \le \hat{F}(m)$
is an approximate median.
In the special case when $x_1,x_2,\ldots,x_T$
is restricted to be a constant sequence,
CDF estimation
and median estimation both become equivalent to binary
search: the empirical CDF is a $\{0,1\}$-valued step
function with a step at some $x \in [n]$ and $x$ is
the unique approximate median, so both tasks become
equivalent to identifying the value of $x$ using queries
of the form $x \stackrel{?}{\le} q_t$. The problem
our work addresses can
thus be interpreted as a generalization of binary search
in which the answers to comparison queries are perturbed
by non-stochastic noise.
One easy consequence of this connection to binary search
is a lower bound of $\lfloor \log_2(n) \rfloor$
on the sample complexity of approximate CDF estimation and
approximate median estimation.
In the important special
case when $\varepsilon$ is a small constant (e.g., $\varepsilon = 0.01$),
the algorithms we present in this paper match this trivial
lower bound to within a constant factor, exponentially
improving the best previously known bounds for CDF estimation
and median estimation in the non-stochastic setting.
\subsection{Techniques}
Given that CDF estimation generalizes binary search and
that the sample complexity bound we are aiming for ---
$O(\log n)$ in the case of constant $\varepsilon$ --- matches
the query complexity of binary search, a natural
idea is to try designing CDF estimation algorithms
with a recursive structure resembling that of binary
search. Indeed, in the stochastic setting,
\citet{karp} presented a median estimation algorithm,
based on binary search with backtracking, whose sample
complexity is $O(\log n)$ when $\varepsilon$ is constant.
Using this algorithm as a subroutine,
\citet{meister} showed how to solve CDF estimation
in the stochastic setting at the cost of an additional
$1/\varepsilon$ factor in sample complexity.
In the non-stochastic setting, one can similarly attempt
to base CDF estimation or median estimation on divide-and-conquer
strategies that zero in on intervals where the
density of samples is high.
However, there is an obvious difficulty:
the past samples need not have any relation to
those in the present and future.
Thus, focusing on intervals that contained many
past samples could draw the algorithm's attention
away from the intervals containing most of the
present samples, making it impossible
to maintain an accurate CDF estimate.
We are not aware of any way to overcome
this difficulty and base a non-stochastic
CDF estimation algorithm on the principle
of divide-and-conquer with backtracking.
Instead, to design our algorithm we take a
detour through a more general model in which
the CDF estimation algorithm is allowed to
make $k$ simultaneous threshold queries for
each sample. When $k=1$ this matches our
original model, but when $k$ exceeds
$\frac{1}{\varepsilon}$ the problem undergoes
an interesting qualitative change: it
becomes solvable by deterministic
algorithms. To solve it, we show that
the problem of using threshold queries
to compute a CDF estimate that is
accurate with probability 1 is equivalent
to a question about the approachability
of a convex set in a two-player game
with vector payoffs. Blackwell's
Approachability Theorem gives us a
criterion for determining the number
of simultaneous queries necessary to
solve CDF estimation using a Las Vegas
randomized algorithm that almost surely
terminates and outputs an $\varepsilon$-accurate
answer. Using the exponential weight
approachability algorithm of
\citet{perchet}, we show that this
objective can in fact be achieved by
a deterministic algorithm in only
$O(\log(n)/\varepsilon)$ rounds, with
$O(1/\varepsilon)$ simultaneous queries
per round. We believe the design and analysis
of this deterministic, simultaneous-query
algorithm for CDF estimation may be
of independent interest. It is also a
vital step in designing a randomized
algorithm that solves CDF estimation in
the original non-stochastic setting with
only one threshold query per sample.
Our algorithm for that problem can be
interpreted as a randomized simulation
of the deterministic simultaneous-query
algorithm: it randomly samples one of the
$O(1/\varepsilon)$ simultaneous queries recommended
by the deterministic algorithm, then uses
importance weighting to produce an unbiased
estimate of the payoff vector that would
have resulted from making all of the recommended
queries simultaneously.
\subsection{Related work}
\label{sec:relwork}
As noted earlier, our problem generalizes noisy
binary search to a setting with non-stochastic noise.
The first paper to study this generalization
is by \citet{meister}, who proved a sample
complexity upper bound $O(n \log(n) / \varepsilon^2)$
using a na\"{i}ve algorithm that queries a
uniformly random threshold $q_t \in [n]$ at each time
$t \in [T]$ and estimates $\hat{F}(i)$ by simply
averaging the values observed in the time steps
$t$ when $q_t = i$. In other words, the na\"{i}ve
algorithm breaks down the problem of estimating a
CDF over $[n]$ into $n$ independent point-estimation
problems, one for each $i \in [n]$, which are each
solved by directly querying $F(i)$ often enough
that the average of the sampled queries approximates
the population average. This ignores the fact that
the empirical CDF must be a monotone function, and
that shape constraints such as monotonicity typically
improve the sample complexity of estimation \citep{isotonic}.
Perhaps surprisingly, \citeauthor{meister}
showed that when $\varepsilon = O(1/n)$, there is a
lower bound for $\varepsilon$-accurate CDF estimation
that matches the na\"{i}ve algorithm's sample
complexity up to a constant factor. This still
left an exponential gap between the upper and lower
bounds for the case of general $\varepsilon > 0$.
Our work closes this gap, proving a tight bound
(up to constant factors) for all $n$ and $\varepsilon > 0$
which exponentially improves
the Meister-Nietert upper bound in the case
$\varepsilon = \Omega(1)$. Prior to our work, it was not known whether CDF estimation
algorithms could obtain any asymptotic improvement
at all over the na\"{i}ve algorithm.
The earliest works on noisy binary search
assumed a stochastic noise model that correctly
answers each comparison query with probability
$\frac12 + \varepsilon$ and otherwise flips the answer.
In this model, an algorithm with sample complexity
$O(\log(n) / \varepsilon^2)$ was presented and analyzed
by \citet{burnashev}, who actually
showed that their algorithm's complexity
is optimal up to a $1 + o(1)$ factor.
An even more precise sample complexity
bound for the same algorithm was later provided
by \citet{benor}. In the same model of stochastic noise,
\citet{feige} provided a different noisy binary
search algorithm with $O(\log(n)/\varepsilon^2)$
complexity; they also supplied algorithms for
a number of other
fundamental problems such as sorting in the same
noisy comparison model. \citet{karp} generalized
the stochastic noisy comparison model to a setting
in which the probability of a correct answer to a
query depends on the identities of the elements
being compared, but is always greater than $\frac12$,
and they showed that the $O(\log(n)/\varepsilon^2)$ sample
complexity bound for noisy binary search continues
to hold in this setting. \citet{meister} showed
how to use the Karp-Kleinberg noisy binary search
algorithm as a subroutine in a CDF estimation
algorithm that achieves sample complexity
$O(\log(n)/\varepsilon^3)$ when the adversary is
stochastic. (In the notation introduced earlier,
this means the sequence $x_1,x_2,\ldots,x_T$ is
created by drawing i.i.d.~samples from a fixed
but unknown distribution.)
\egedit{Many works in the literature have studied distribution learning under specific constraints. \cite{han} and \cite{barnes} proved various minimax lower bounds for the problem of learning structured distributions in distributed networks. In their setting, every node in the network observes one independent sample drawn from the underlying distribution, and there is a central processor to which every node in the network communicates $k$ bits. \cite{acharya-information-constraints} significantly generalized \citeauthor{barnes}'s result, presenting unified lower bounds for distributed parametric estimation under a wide variety of local information constraints including communication, privacy, and data access constraints. They modeled their setting by considering a set of channels through which samples are passed to obtain observations. Using this general model, \citeauthor{acharya-information-constraints} were able to recover the bounds presented by \citeauthor{barnes}. A similar setting where $n$ nodes can observe $m$ samples and communicate information using $l$ bits was presented and analyzed in \cite{acharya-multiple-samples}. Like previous works, we model our problem as distribution learning under a set of constraints. Rather than focusing on communication channels in distributed models, our constraints are defined on the sequence of threshold queries the algorithm can make.}
The distribution estimation problem is also studied within the context of online dynamic pricing and auctions. A seller repeatedly interacts with a buyer by setting prices for an item and observing whether the buyer purchases or not. An auctioneer learns a winning distribution by adaptively choosing reserve prices. Although both of these settings are limited to binary feedback: observing whether the item is bought, the literature \citep{kleinberg, leme, blum, reviewer1request} in these contexts assume the distribution is fixed or slowly-changing and often while trying to minimize a notion of regret with respect to the best fixed price in hindsight. We don't make any assumptions about the distribution.
\section{Threshold Query Model}
We start by describing the CDF estimation problem as defined by \citet{meister}. At each time step $t$, the adversary produces a sample $x_t \in [n+1]$, and the algorithm $\mathcal{A}$ generates a query $q_t \in [n]$, each ignorant of the other's choice. Then, the algorithm receives feedback ${\textbf 1}(x_t \leq q_t)$ and produces a CDF estimate $\hat{F}_t$ of $x_1, \ldots, x_t$ while $q_t$ is revealed to the adversary. The adversary is allowed to be adaptive, i.e may select $x_t$ based on the history of the prior $t-1$ time steps. Let $F_t$, defined by $F_t (i) = \frac{1}{t} \sum_{\tau = 1}^t {\textbf 1}(x_\tau \leq i)$ be the empirical CDF of the sequence $x_1, \ldots, x_t$, where $F_t(0) = 0$. They define the estimation error of the algorithm at time $t$ as the Kolmogorov-Smirnov distance between the empirical CDF, $F_t$, and the algorithm's estimate $\hat{F}_t : [n] \rightarrow [0,1]$. In other words, the estimation error is $|| \hat{F}_t - F_t ||_\infty := \sup_{i \in [n]} | \hat{F}_t (i) - F_t (i)|$.
\vgmargincomment{i added a newline here}
We generalize this formulation in two ways. First, we allow the adversary to pick any monotone function \pcoedit{$v_t : [n] \rightarrow [0,1]$ at each time step instead of a sample $x_t \in [n]$. This generalizes the original setting since $v_t (i) = {\textbf 1}(x_t \leq i)$ is a monotone step function. Thus, picking $x_t \in [n]$ is equivalent to choosing a monotone step function.}
\vgedit{Then, $F_t$ can easily be redefined to be the empirical average of the monotone functions instead, i.e. $F_t(i) = \frac1t \sum_{\tau = 1}^t v_\tau(i)$.}
Second, rather than insisting that the algorithm must make only one query per sample, we \pcodelete{generalize the model to give} \pcoedit{allow} the algorithm a specified number of queries per sample, where this query budget could be anywhere between 1 and $n$.
We now proceed to formalize this Threshold Query Model (TQM). Consider an online estimation environment defined by parameters $n, k$, where the timing of each round $t$ is as follows:
\begin{enumerate}
\item Adversary chooses a monotone function \vgedit{$v_t : [n] \rightarrow [0,1]$.}
\item Algorithm chooses a set of (up to) $k$ query points: $q_{1,t} \leq \ldots \leq q_{k,t} \in [n]$; adversary observes these query points.
\item Algorithm receives feedback: $y_{1,t} \leq \ldots \leq y_{k,t} \in [0,1]$, where $y_{i,t} = \vgedit{v}_t(q_{i,t}).$
\end{enumerate}
We will refer to an environment with this interaction structure as the $k$-TQM,
and we will refer to the parameter $k$ as the {\em query budget}. Since much of our focus is on the case when the query budget equals 1, we will refer to the 1-TQM simply as the TQM.
At the end of the $T$ rounds, the algorithm returns a function $G_T: [n] \rightarrow [0,1]$. We say this algorithm
has {\em accuracy $\varepsilon$} and {\em sample complexity $T$} if it satisfies
the guarantee that for all $\tau \ge T$, the probability that
$\|G_{\tau} - F_{\tau}\| \le \varepsilon$ is at least $\frac34$, against any (potentially adaptive) adversary. For brevity, we will sometimes refer to an algorithm with accuracy $\varepsilon$ and sample complexity $T$ as an $(\varepsilon,T)$-algorithm.
We are interested in the following questions:
\begin{enumerate}
\item For a fixed accuracy $\varepsilon$ and query budget $k$, what is the minimum sample complexity?
In other words, what is the smallest $T$ for which there exists an $(\varepsilon, T)$-algorithm for the $k$-TQM?
\item For a fixed accuracy $\varepsilon$ and sample complexity $T$,
how large must the query budget be?
In other words, what is the smallest $k$ for which there exists a
$(\varepsilon,T)$-algorithm for the $k$-TQM?
\end{enumerate}
\rdkedit{For $k=1$, our work shows that the answer to the first question is $O \left( \frac{\log n}{\varepsilon^3} \right)$, which is tight up to a constant factor.
We also resolve the second question precisely when $T$ is sufficiently large as a function of $n$ and $\varepsilon$, showing that query budget $k = \frac{1}{2 \varepsilon} - 1$ is necessary and sufficient for deterministic algorithms and that query budget $k=1$ is necessary and sufficient for randomized algorithms.}
For simplicity, we shall say a pair $(k, T)$ is \textbf{achievable} if there is an $(\varepsilon,T)$-algorithm for the $k$-TQM.
Algorithms for the $k$-TQM may be deterministic or randomized.
Observe that an $\varepsilon$-accurate deterministic algorithm for the $k$-TQM
must achieve the guarantee that $\|G_{\tau} - F_{\tau}\|_{\infty} \le \varepsilon$
{\em with probability 1} for all $\tau \ge T$ and all adversaries.
\subsection{Deterministic Algorithms for the Threshold Query Model}
The \cite{meister} result can be interpreted as an $\left(\varepsilon, O \left( \frac{n \log n}{\varepsilon^2} \right) \right)$-algorithm for the TQM. In contrast, there does not exist a deterministic algorithm for the TQM. In fact, by using a pigeonhole argument\footnote{The argument is presented in \Cref{pf:deterministic}}
one can show that deterministic algorithms with accuracy $\varepsilon$ and finite sample complexity must have query budget $k \ge \pcoedit{\frac{1}{2\varepsilon}} - 1$.
This shows a qualitative distinction between
deterministic and randomized algorithms for the $k$-TQM, when $k$ is small.
Perhaps the most important reason we study
deterministic algorithms with query
budget $k>1$ is that it informs our design of a randomized algorithm with query budget 1.
In fact, our algorithms for the TQM (i.e., with query budget 1) work by simulating a deterministic algorithm with a larger query budget.
The algorithm in \cite{meister} can be thought of as simulating a deterministic algorithm with query budget $n$ that simply queries every point at each timestep. This observation suggests a strategy for improving the sample complexity of the algorithm of \citet{meister} by first designing more query-efficient deterministic $k$-TQM algorithms and then simulating them using randomized algorithms.
Our goal is two-fold: making the query budget and sample complexity
simultaneously as small as possible. Naturally, the sample complexity of any simulation algorithm for TQM would depend on these two parameters. However, the smaller the query budget, the greater the sample complexity required for $\varepsilon$-accurate CDF estimation. The trivial deterministic $n$-TQM algorithm guarantees an $\varepsilon$-accurate CDF estimate for every $T \ge 1$, i.e,
its sample complexity is $1$.
In \Cref{sec:elementary}, we show elementary deterministic algorithms,
one with query budget $O(\sqrt{n}/ \varepsilon)$ and sample complexity
$O(1/\varepsilon)$, the other with query budget $O \left( \frac{\log n}{\varepsilon} \right)$
and sample complexity $O \left( \frac{\log n}{\varepsilon} \right).$
However, neither of these elementary algorithms
attains the lowest possible query budget for deterministic
algorithms. Using the Blackwell's Approachability Theorem, in
\Cref{sec:approach}, we show the existence of a deterministic algorithm with query budget $O(1/\varepsilon)$, accuracy $\varepsilon$, and finite sample complexity. Then, in \Cref{sec:mult-wt}, we show using the multiplicative weights method that this algorithm can be designed to have sample complexity $O \left( \frac{\log n}{\varepsilon} \right)$.
In \Cref{sec:import-wt}, we adapt this algorithm for the TQM using importance weighting and show that its sample complexity is bounded by
$O \left( \frac{\log n}{\varepsilon^3} \right)$.
In \Cref{sec:low-bd-sketch}, we prove a lower bound on TQM that matches our upper bound up to a constant factor and in \Cref{sec:conclusion}, we consider some generalizations and future work.
\section{Using Approachability to solve TQM}\label{sec:approach}
\subsection{Review of Blackwell Approachability}
Blackwell approachability \citep{blackwell} generalizes the problem of playing a repeated two-player zero-sum game to games whose payoffs are vectors instead of scalars. In a Blackwell approachability game, at all times $t$, two players interact in this order: first, Player 1 selects an action $\vgedit{a}_t \in \vgedit{A}$; then, Player 2 selects an action $\vgedit{b}_t \in \vgedit{B}$; finally, Player 1 incurs the vector-valued payoff $\vgedit{h(a_t,b_t)} \in \mathbb{R}^d$. The sets \vgedit{$A , B$} of player actions are assumed to be compact convex subsets of finite-dimensional vector spaces, and $\vgedit{h}$ is assumed to be a biaffine function on \vgedit{$A \times B$}. Player 1's objective is to guarantee that the average payoff converges to some desired closed convex target set $S \subseteq \mathbb{R}^d$. Formally, given target set $S \subseteq \mathbb{R}^d$, Player 1's goal is to pick actions \vgedit{$a_1, a_2, \ldots \in A$} such that no matter the actions \vgedit{$b_1, b_2, \ldots \in B$} played by Player 2,
\begin{equation} \label{eq:approach}
\textnormal{\texttt{dist}} \left(\frac{1}{T} \sum_{t=1}^T \pcoedit{h}(x_t, y_t), S \right) \rightarrow 0 \quad \text{as} \quad T \rightarrow \infty
\end{equation}
The action $\vgedit{a}_t$ is allowed to depend on the realized payoff
vectors $\vgedit{h_s(a_s,b_s)}$ for $s=1,2,\ldots,t-1$.
We say the set $S$ is approachable if Player~1
has a strategy that attains the goal~\eqref{eq:approach}
no matter how Player 2 plays. Blackwell's Approachability
Theorem asserts that a convex set $S \subset {\mathbb{R}}^d$
is approachable if and only if every closed halfspace
containing $S$ is approachable. This is a
convenient criterion for approachability, because one
can test whether a halfspace is approachable by
computing the value of an associated zero-sum game,
or equivalently by solving a linear program.
\subsection{Approachability Reduction}
A deterministic algorithm for the $k$-TQM
chooses queries $q_{1,t} \le q_{2,t} \le \cdots \le q_{k,t}$ at time $t$, and receives feedback $y_{1,t} \le y_{2,t} \le \cdots \le y_{k,t}$,
where $y_{i,t} = \vgedit{v}_t(q_{i,t})$. For notational convenience, we will interpret $q_{0,t}=0, q_{k+1,t}=n+1, y_{0,t}=0, y_{k+1,t}=1.$
\vgmargincomment{i just added a newline here}
For index $i \in [n]$,
define $\ell_t(i)$ and $u_t(i)$ by
\begin{equation*}
\ell_t(i) =
\max \{ y_{j,t} \mid 0 \le j \le k+1, \, q_{j,t} \le i \}, \qquad
u_t(i) =
\min \{ y_{j,t} \mid 0 \le j \le k+1, \, q_{j,t} \ge i \}
.
\end{equation*}
These are the tightest lower and upper bounds on $F_t(i)$
that can be deduced from the values the algorithm queried.
Let $d_t(i) = u_t(i) - \ell_t(i)$.
At time $T$, the best lower and upper bounds on
$\frac1T \sum_{t=1}^T \vgedit{v}_t(i)$ that can be deduced
from the values queried are
$\frac1T \sum_{t=1}^T \ell_t(i)$ and
$\frac1T \sum_{t=1}^T u_t(i)$. Hence,
we know that $\frac1T \sum_{t=1}^T \vgedit{v}_t(i)$
belongs to an interval of width $\frac1T \sum_{t=1}^T d_t(i)$.
When this interval width is less than
or equal to $2 \varepsilon$ for every $i \in [n]$,
it is safe to stop and output an estimate
$G_T : [n] \to [0,1]$ defined by setting $G_T(i)$ to be the
midpoint of the interval
$\left[ \frac1T \sum_{t=1}^T \ell_t(i),
\frac1T \sum_{t=1}^T u_t(i) \right]$.
This suggests the following formulation of the deterministic
query model as a game with vector payoff. In each round:
\begin{enumerate}
\item Adversary chooses monotone non-decreasing
$\vgedit{v}_t : [n] \to [0,1]$.
\item Algorithm simultaneously chooses $q_{1,t} \le \cdots \le q_{k,t}$. \vgedit{This corresponds to Player 1's action.}
\item Feedback $y_{i,t} = \vgedit{v}_t(q_{i,t})$ is revealed for $i=1,2,\ldots,k$. \vgedit{This corresponds to Player 2's action.}
\item The $n$-dimensional loss vector is $\mathbf{d}_t =
(d_t(1), \, d_t(2), \, \cdots , \, d_t(n)).$ \vgedit{In our reduction, this corresponds to the vector-valued payoff at time $t$.}
\vgmargincomment{I can also give the blackwell approachability correspondences in this list}
\end{enumerate}
The questions we seek to understand
are: for which values of $k$ is there an algorithm
that guarantees to approach the set $(-\infty,2 \varepsilon]^n$?
If the set is approachable, how large must $T$ be to ensure that
the algorithm's $L_{\infty}$ distance from that set is
$O(\varepsilon)$?
\begin{proposition} \label{prop:approachable}
In the vector payoff game corresponding to query budget $k$, the set $(-\infty,2 \varepsilon]^n$ is approachable whenever $k + 1 \ge \frac{1}{2 \varepsilon}$.
\end{proposition}
\begin{proof}
To show that $S = (-\infty,2 \varepsilon]^n$ is an
approachable set, we need to show that every halfspace
containing $S$ is approachable. A halfspace containing
$S$ is a set $H$ of the form
\[
H = \left\{ \mathbf{x} \left| \sum_{i=1}^n a_i x_i \le b
\right. \right\}
\]
where $a_1, a_2, \ldots, a_n$ are non-negative, at least
one of them is strictly positive, and $b \ge
\sum_{i=1}^n a_i (2 \varepsilon).$ Without loss of generality\footnote{
Otherwise, $H$ is a proper superset of another halfspace
$H'$ that also contains $S$, and to show $H$ is approachable
it suffices to show $H'$ is approachable.},
$b$ is equal to $2 \varepsilon \sum_{i=1}^n a_i$.
Also, without changing the halfspace $H$, we can normalize
$a_1,\ldots,a_n, b$ so that
$\sum_{i=1}^n a_i = 1$ and $b = 2 \varepsilon$.
Assume henceforth that we have adopted such a normalization.
For $j=1,\ldots,k$ let
\begin{equation} \label{eq:qj}
q_j = \min \left\{ q \, \left| \,
\sum_{i=1}^q a_i \ge \frac{j}{k+1}
\right. \right\} .
\end{equation}
We aim to show that for any choice of $\vgedit{v}_t$ by
the adversary, the loss vector $\mathbf{d}_t$ belongs to
$H$ when the algorithm chooses $q_1,\ldots,q_k$ as defined
in Equation~\eqref{eq:qj}.\footnote{
\vgedit{For brevity, we are using the notation $q_j$ while referring to the query $q_{j, t}$}} For notational convenience,
let $q_0 = 0, \, q_{k+1} = n+1$ and
let $\vgedit{v}_t(0) = 0, \, \vgedit{v}_t(n+1) = 1$. Observe, by the
definition of $q_j$, that
\begin{equation} \label{eq:qj-sum}
\sum_{i=q_{j}+1}^{q_{j+1}-1} a_i =
\sum_{i=1}^{q_{j+1}-1} a_i \; - \;
\sum_{i=1}^{q_{j}} a_i <
\frac{j+1}{k+1} - \frac{j}{k+1} = \frac{1}{k+1} .
\end{equation}
Also observe that for $i = q_j$
we have $u_t(i) = \ell_t(i) = \vgedit{v}_t(q_j),
\, d_t(i)=0$, while for
$q_j < i < q_{j+1}$ we have
\rdkedit{$u_t(i) = \vgedit{v}_t(q_{j+1})$,
$\ell_t(i) = \vgedit{v}_t(q_j)$,
$d_t(i) = \vgedit{v}_t(q_{j+1}) - \vgedit{v}_t(q_j)$.
Hence,
\begin{align*}
\sum_{i=1}^n a_i d_t(i)
& =
\sum_{j=0}^k \sum_{i=q_j+1}^{q_{j+1}-1} a_i (\vgedit{v}_t(q_{j+1}) - \vgedit{v}_t(q_j)) \\
& \le
\sum_{j=0}^k \frac{\vgedit{v}_t(q_{j+1}) - \vgedit{v}_t(q_j)}{k+1}
= \frac{\vgedit{v}_t(q_{k+1}) - \vgedit{v}_t(q_0)}{k+1}
= \frac{1}{k+1} .
\end{align*}
}
The right side is less than or equal to $b = 2 \varepsilon$
whenever \rdkedit{$k+1 \ge \frac{1}{2 \varepsilon}.$}
\rdkedit{This confirms that every halfspace containing
$S$ is approachable, hence $S$ is approachable.}
\end{proof}
\section{Multiplicative Weights Algorithm for CDF estimation with parallel queries}\label{sec:mult-wt}
In this section, we transform the proof of approachability
(\Cref{prop:approachable}) into
a deterministic algorithm with query budget $k = \lfloor 1/\varepsilon \rfloor$, accuracy $\varepsilon$,
and sample complexity $\frac{9 \ln n}{\varepsilon}$.
The key to designing the
algorithm will be to select coefficients
$a_{i,t}$ in each round $t$ using the
multiplicative weights algorithm, and
then respond to these coefficients by
choosing query points $q_{1,t},\ldots,q_{k,t}$
using Equation~\eqref{eq:qj}
as in the proof of approachability.
\begin{algorithm2e}[H]\label{algo:mult-wt}
\caption{Multiplicative weights algorithm for $k$-TQM}
\textbf{Initialize}: \
\rdkedit{$\eta = 1/3$}\;
$w_{i,0} = \frac1n$ for $i \in [n]$\;
\For{$t=1,2,\ldots,T$}{
$W = \sum_{i=1}^n w_{i,t-1}$\;
For $i \in [n]$ let $a_{i,t} = w_{i,t-1}/W$\;
For $j \in [k]$ let
$ q_{j,t} = \min \left\{ q \, \left| \,
\sum_{i=1}^q a_{i,t} \ge \frac{j}{k+1}
\right. \right\} $\;
Query points $q_{1,t}, \ldots, q_{k,t}$ and receive
answers $y_{1,t}, \ldots, y_{k,t}$\;
Let $q_{0,t} = 0$ and $q_{k+1,t} = n$\;
\For{$i \in [n]$}{
\rdkedit{$\ell_t(i) = \max \{ y_{j,t} \mid 0 \le j \le k+1, \, q_{j,t} \le i \}$}\;
\rdkedit{$u_t(i) = \min \{ y_{j,t} \mid 0 \le j \le k+1, \, q_{j,t} \ge i \} $}\;
$d_t(i) = u_t(i) - \ell_t(i)$\;
$w_{i,t} = w_{i,t-1} \cdot (1+\eta)^{d_t(i)}$\;
}
}
\textbf{Output}: $G_T[i] = \frac1{2T} \sum_{t=1}^T (\ell_t(i) + u_t(i) )$ for
all $i \in [n]$.
\end{algorithm2e}
\begin{theorem} \label{thm:mult-wts}
When $k +1 \ge \frac{1}{\varepsilon}$,
\rdkedit{Algorithm~\ref{algo:mult-wt} solves the
$k$-TQM with accuracy $\varepsilon$ and sample
complexity $\frac{9 \ln n}{\varepsilon}$.}
\end{theorem}
\begin{proof}
The weights $w_{i,t}$ and coefficients $a_{i,t}$
in Algorithm~\ref{algo:mult-wt} evolve according to the
update equations of the standard Hedge algorithm
with parameter $\eta = 1/3$, and
according to the analysis of that algorithm in \cite{hedge}
\rdkmargincomment{Citation needed!},
we have the inequality
\begin{equation} \label{eq:hedge}
\sum_{t=1}^T \sum_{i=1}^n a_i d_t(i) \ge
(1 - \eta) \max_{i \in [n]} \{ \sum_{t=1}^T d_t(i) \}
- \frac{\ln n}{\eta} .
\end{equation}
From the proof of \Cref{prop:approachable} we know that
for all $t$, \rdkedit{$\sum_{i=1}^n a_i d_t(i) \le \frac{1}{k+1}$.}
Substituting this bound into Inequality~\eqref{eq:hedge}
we obtain
\rdkedit{
\begin{equation} \label{eq:mw1}
\frac{T}{k+1} \ge
(1 - \eta) \max_{i \in [n]} \left\{ \sum_{t=1}^T d_t(i) \right\}
- \frac{\ln n}{\eta} =
\frac23 \max_{i \in [n]} \left\{ \sum_{t=1}^T d_t(i) \right\}
- 3 \ln n \ge
\frac23 \max_{i \in [n]} \left\{ \sum_{t=1}^T d_t(i) \right\}
- \frac{\varepsilon}{3} T,
\end{equation}
}
where the second inequality follows from the fact
that \rdkedit{$T \ge \frac{9 \ln n}{\varepsilon}$}.
Recalling that \rdkedit{$\eta = \frac13,
k+1 \ge \frac{1}{\varepsilon},$} we find that
\rdkedit{
\begin{align*}
\varepsilon T & \ge
\frac23 \max_{i \in [n]} \left\{ \sum_{t=1}^T d_t(i) \right\}
- \frac{\varepsilon}{3} T \\
\frac43 \varepsilon T & \ge
\frac23 \max_{i \in [n]} \left\{ \sum_{t=1}^T d_t(i) \right\} \\
2 \varepsilon & \ge
\max_{i \in [n]} \left\{ \tfrac 1T \sum_{t=1}^T d_t(i) \right\} .
\end{align*}
}
The right side of the last inequality is equal to the
width of the interval
$\left[ \frac1T \sum_{t=1}^T \ell_t(i), \;
\frac1T \sum_{t=1}^T u_t(i) \right]$.
That interval is guaranteed to contain
$\frac1T \sum_{t=1}^T \vgedit{v}_t(i)$, and its
midpoint is $G_T(i)$, so we are assured
that
\rdkedit{$|G_T(i) - \frac1T \sum_{t=1}^T
\vgedit{v}_t(i)|
\le \frac12 \left( 2 \varepsilon \right) = \varepsilon$,}
as desired.
\end{proof}
\section{Randomized algorithm using importance weighting}\label{sec:import-wt}
In \Cref{sec:mult-wt}, we presented a deterministic algorithm
with accuracy $\varepsilon$, query budget $\lfloor \frac{1}{\varepsilon} \rfloor$,
and sample complexity $\frac{9 \ln n}{\varepsilon}$.
Earlier we noted that no deterministic algorithm can obtain
accuracy $\varepsilon$ with a query budget less than $\frac{1}{2 \varepsilon} - 1$.
\rdkmargincomment{Off by a factor of 2?}
In this section, we turn our attention to \textit{randomized} algorithms
with query budget 1.
One natural approach would be to simulate the deterministic algorithm from the previous section; that is, run one step of Algorithm $\ref{algo:mult-wt}$ to obtain a set of $k$ query points, and over the course of the next
$O\left(\frac{k \log n}{\varepsilon^2} \right)$
time-steps, randomly sample one of the $k$ points to query to get an $\varepsilon$-accurate estimate of the CDF at each of the $k$ query points.
This approach can be carried out successfully, although we omit the
details from this paper. However, the resulting sample complexity bound
exceeds the optimal bound by a factor of $\Omega \left(
\frac{\ln \ln n}{\varepsilon} \right).$
One of the main reasons for this is that the algorithm commits to sampling from a \textit{fixed} set of $k$ points for $O\left(\frac{k \log n}{\varepsilon^2} \right)$ time steps even though the algorithm's CDF estimate is changing and Algorithm~\ref{algo:mult-wt} might suggest a different set of $k$ query points.
To circumvent this issue of committing to a fixed set of query points, we use an approach from the bandit literature known as importance weighting.
We can't query all the points $q_{1,t}, \ldots, q_{k,t}$ to receive feedback $y_{1,t}, \ldots, y_{k,t}$, so we instead choose one point uniformly at random $q_{m,t}$, to receive feedback $y_{m,t}$. We set the values $\hat{y}_{j,t}$ to $k \cdot y_{m,t}$ if $j = m$ and $0$ otherwise. Then we proceed with the rest of the algorithm with values $\hat{y}_{1,t}, \ldots, \hat{y}_{k,t}$ instead of $y_{1,t}, \ldots, y_{k,t}$.
\begin{algorithm2e}[H]\label{algo:import-wt}
\caption{Randomized MW algorithm using importance weighting}
\textbf{Initialize}: \
$k = \frac{2}{\varepsilon}, \eta = \varepsilon^2 /16 $\;
$w_{i,0} = \frac1n$ for $i \in [n]$\;
\For{$t=1,2,\ldots,T$}{
$W = \sum_{i=1}^n w_{i,t-1}$\;
For $i \in [n]$ let $a_{i,t} = w_{i,t-1}/W$\;
For $j \in [k]$ let
$ q_{j,t} = \min \left\{ q \, \left| \,
\sum_{i=1}^q a_{i,t} \ge \frac{j}{k+1}
\right. \right\} $\;
Let $q_{0,t} = 0$ and $q_{k+1,t} = n$\;
For $j \in [k]$ let $\hat{y}_{j,t} = 0$\;
Sample $m$ uniformly from $[k]$\;
Query $q_{m,t}$ and receive $y_{m,t}$\;
Set $\hat{y}_{m,t} = k \cdot y_{m,t}$\;
\For{$i \in [n]$}{
$\hat{\ell}_t(i) = \hat{y}_{r,t} \ \text{where} \ r = \max \{ j \mid 0 \le j \le k+1, \, q_{j,t} \le i \} $\;
$\hat{u}_t(i) = \hat{y}_{r,t} \ \text{where} \ r = \min \{ j \mid 0 \le j \le k+1, \, q_{j,t} \ge i \} $\;
$\hat{d}_t(i) = \hat{u}_t(i) - \hat{\ell}_t(i)$\;
$w_{i,t} = w_{i,t-1} \cdot (1+\eta)^{\hat{d}_t(i)}$\;
}
}
\textbf{Output}: $\hat{G}_T[i] = \frac1{2T} \sum_{t=1}^T (\hat{\ell}_t(i) + \hat{u}_t(i) )$ for all $i \in [n]$.
\end{algorithm2e}
\rdkcomment{Should the output be denoted by $G_T$ rather
than $\hat{G}_T$?}
\begin{theorem}\label{thm:import-wts}
Algorithm~\ref{algo:import-wt}
solves the TQM with accuracy $\varepsilon$ and
sample complexity $\frac{64 \log n}{\varepsilon^3}$.
\end{theorem}
The proof of the theorem is presented in
\Cref{sec:import-wts-proof}.
\section{Lower Bound}
\label{sec:low-bd-sketch}
In this section we sketch a proof that the sample
complexity of \Cref{algo:import-wt} is
information-theoretically optimal, up to
a constant factor. The full proof appears
in \Cref{sec:low-bd-proof}.
\begin{theorem} \label{thm:low-bd}
For any $n > 1, \varepsilon > 0$, every algorithm that solves
the CDF estimation problem with accuracy $\varepsilon$, using
one threshold query per sample, requires at least
$T_0 = \Omega(\min\{n,\frac{1}{\varepsilon} \cdot \log(n) / \varepsilon^2)$
samples.
\end{theorem}
When $n \le \frac{1}{\varepsilon}$ this is Theorem 6
of \citet{meister}, so for the remainder of this
section we discuss the proof when $n > \frac{1}{\varepsilon}.$
Assume for convenience\footnote{These
assumptions are without loss of generality.
First increase $\varepsilon$ by a factor of at most 6,
to ensure that $\frac{1}{6\varepsilon}$ is an integer less than or
equal to $n$, then decrease $n$ by a factor of
at most 2 to ensure that $n$ is divisible by $\frac{1}{6 \varepsilon}$.
These changes to $\varepsilon$ and $n$ only affect the implicit constant
in the big-$\Omega$ expression for the lower bound.}
that the numbers
$k = \frac{1}{6 \varepsilon}$ and $m = n/k = 6 \varepsilon n$
are positive integers. We will then define a
family of probability distributions parameterized
by $\theta \in [m]^k$. Their cumulative distribution
functions, $\{ F_{\theta} \mid \theta \in [m]^k\}$,
are designed to have three properties.
\begin{enumerate}
\item For any function $\hat{F}$ there is at most
one $\theta \in [m]^k$ such that
$\| \hat{F} - F_{\theta} \|_{\infty} < \frac{3 \varepsilon}{2}.$
Hence, given a $\frac{3 \varepsilon}{2}$-accurate estimate of $F_{\theta}$
we can deduce the value of $\theta$.
(\Cref{lem:ftheta-decode})
\item Informally, any sequence of $1/\varepsilon^{2}$
threshold queries reveals at most $O(1)$ bits
of information about $\theta$. In the proof,
this statement is formalized information-theoretically
in terms of the expected KL-divergence between the
learner's prior and posterior distributions over
$\theta$.
(\Cref{lem:klbayes-ub})
\item Starting from a uniform prior over
$\theta \in [m]^k$, the posterior distribution
after any sequence of threshold queries is a
product distribution. In other words, writing
$\theta$ as a $k$-tuple $(\theta_1,\ldots,\theta_k),$
the $k$ coordinates of the tuple are mutually
independent under the posterior distribution.
(\Cref{lem:posterior-is-product})
\end{enumerate}
Now suppose the adversary generates a sequence
$x_1,\ldots,x_T$ by sampling $\theta \in [m]^k$
uniformly at random and then drawing $T$
independent samples from the distribution
with CDF $F_{\theta}.$
Using the Dvoretzky-Kiefer-Wolfowitz Inequality,
we will argue that with probability at least $\frac{7}{8}$,
the empirical CDF of the samples differs from
$F_{\theta}$ by less than $\frac{\varepsilon}{2}$ in
$L_{\infty}$ norm. Hence, an $\varepsilon$-accurate
estimate of the empirical distribution is a
$\frac{3 \varepsilon}{2}$-accurate estimate of $F_{\theta}$,
and consequently it uniquely determines the value
of $\theta$. This implies that an algorithm which
succeeds, with probability at least $\frac34$,
in outputting an $\varepsilon$-accurate estimate of
the empirical distribution of the samples,
must also succeed with probability at least
$\frac58$ in learning the exact value of
$\theta$, a random variable of entropy
$k \log(m)$. Since it takes $\Omega(1/\varepsilon^{2})$
queries to learn a single bit of information
about $\theta$, it takes $\Omega(k \log(m) / \varepsilon^2)$
queries to learn the exact value of $\theta$ with
constant probability. Recalling the definitions
of $k$ and $m$, we see that this bound is
$\Omega(\log(\varepsilon n) / \varepsilon^3).$ \Cref{thm:low-bd}
asserts the stronger lower bound $\Omega(\log(n) / \varepsilon^3)$,
which is asymptotically greater when $1/\varepsilon = n^{1-o(1)}.$
To strengthen the lower bound in this case, we use the third
property of the construction --- that the posterior
distribution over $\theta$ is a product distribution ---
to prove a stronger lower bound on the expected KL divergence
between the prior and posterior distributions at the time
when the algorithm outputs its estimate.
\section{Discussion and Open Problems}\label{sec:conclusion}
\pcoedit{
In addressing the online CDF estimation problem, we took a detour to a more general setting - the Threshold Query Model. Although we completely characterize the sample complexity of online CDF estimation using threshold queries, this only resolves the sample complexity question for the $k$-TQM for $k = 1$. One direction for future work is to characterize the optimal sample complexity for every value of the query budget $k$. Another direction is to extend the Threshold Query Model to other distance metrics besides the Kolmogorov-Smirov distance. It is important to note that the presented algorithms are fully adaptive. In some practical settings, however, there might issues of latency and delays. This raises a question of whether the query budget and sample complexity is higher for non-adaptive algorithms, and if so, by how much? Some special cases of this are addressed in \Cref{sec:elementary}.
A natural extension to consider is the continuous-support setting, where the queries and samples can be any real value in the interval $[0,1]$. Without any additional assumptions, CDF estimation in this setting becomes intractable. This is because there are infinitely many values and the algorithm cannot cover all of them with a finite number of queries. However, \cite{meister} point out that if we specify some resolution $r$ of interest, then by setting $n = O(1/r)$, this reduces to the discrete-support case. We wonder what assumptions on the adversary's probability density function would make the CDF estimation problem tractible and if our techniques would be applicable.
\vgedit{Another direction of interest is to consider higher-dimensional generalizations that estimate multivariate distributions - the samples are now vector-valued, and the algorithm queries the data using linear threshold functions (i.e., halfspaces).}
In \Cref{sec:intro}, we pointed out some related works in \vgedit{relevant application areas like} online dynamic pricing and auctions. We wonder if our techniques can be extended to these settings as well.}
\bibliographystyle{apalike}
\bibliography{bibliography}