Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
45,915 characters · 13 sections · 33 citation commands
Non-Stochastic CDF Estimation Using Threshold Queries
\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 greenwald2001space,karnin2016optimal,manku1998approximate,munro1980selection, with applications to databases greenwald2001space, network health monitoring cormode2004holistic, and wireless sensor networks 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.}
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.}
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.
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, 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, 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 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.
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 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 isotonic. Perhaps surprisingly, 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 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 benor. In the same model of stochastic noise, 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. 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. 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. han and 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. acharya-information-constraints significantly generalized 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, acharya-information-constraints were able to recover the bounds presented by barnes. A similar setting where $n$ nodes can observe $m$ samples and communicate information using $l$ bits was presented and analyzed in 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 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.
We start by describing the CDF estimation problem as defined by 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:
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:
\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 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.
The 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 (ref)} 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 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 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 (ref), 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 (ref), we show the existence of a deterministic algorithm with query budget $O(1/\varepsilon)$, accuracy $\varepsilon$, and finite sample complexity. Then, in (ref), 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 (ref), 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 (ref), we prove a lower bound on TQM that matches our upper bound up to a constant factor and in (ref), we consider some generalizations and future work.
Blackwell approachability 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,
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 (ref) 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.
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
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:
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)$?
In this section, we transform the proof of approachability ((ref)) 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 (ref) as in the proof of approachability.
\begin{algorithm2e}[H] \caption{Multiplicative weights algorithm for $k$-TQM} 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)}$\; } } Output: $G_T[i] = \frac1{2T} \sum_{t=1}^T (\ell_t(i) + u_t(i) )$ for all $i \in [n]$. \end{algorithm2e}
In (ref), 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 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 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) 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] \caption{Randomized MW algorithm using importance weighting} 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)}$\; } } 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$?}
The proof of the theorem is presented in (ref).
In this section we sketch a proof that the sample complexity of (ref) is information-theoretically optimal, up to a constant factor. The full proof appears in (ref).
When $n \le \frac{1}{\varepsilon}$ this is Theorem 6 of 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.
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).$ (ref) 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.
\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 (ref).
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, 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 (ref), 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.}