Department of Computer Science, Duke University, NC, USA
pankaj@cs.duke.edupankaj@cs.duke.eduhttps://orcid.org/0000-0002-9439-181X
Department of Computer Science, Duke University, NC, USA
rahul.raychaudhury<EMAIL_ADDRESS>Department of Computer
Science, University of Illinois at Chicago, IL, USA
stavros@uic.edustavros@uic.eduhttps://orcid.org/0000-0002-2114-8886 Department
of Computer Science, Duke University, NC, USA
junyang@cs.duke.edujunyang@cs.duke.eduhttps://orcid.org/0000-0003-0604-6790
Pankaj K. Agarwal, Rahul Raychaudhury, Stavros Sintos, and Jun Yang
[100]Theory of computation Computational Geometry

# Computing Data Distribution from Query Selectivities

Pankaj K. Agarwal  Rahul Raychaudhury  Stavros Sintos  Jun Yang

###### Abstract

We are given a set $\mathcal{Z}=\\{(R_{1},s_{1}),\ldots,(R_{n},s_{n})\\}$,
where each $R_{i}$ is a _range_ in $\mathbb{R}^{d}$, such as rectangle or
ball, and $s_{i}\in[0,1]$ denotes its _selectivity_. The goal is to compute a
small-size _discrete data distribution_
$\mathcal{D}=\\{(q_{1},w_{1}),\ldots,(q_{m},w_{m})\\}$, where
$q_{j}\in\mathbb{R}^{d}$ and $w_{j}\in[0,1]$ for each $1\leq j\leq m$, and
$\sum_{1\leq j\leq m}w_{j}=1$, such that $\mathcal{D}$ is the most
_consistent_ with $\mathcal{Z}$, i.e.,
$\mathrm{err}_{p}(\mathcal{D},\mathcal{Z})=\frac{1}{n}\sum_{i=1}^{n}\\!\lvert{s_{i}-\sum_{j=1}^{m}w_{j}\cdot\mathbbm{1}(q_{j}\in
R_{i})}\rvert^{p}$ is minimized. In a database setting, $\mathcal{Z}$
corresponds to a workload of range queries over some table, together with
their observed selectivities (i.e., fraction of tuples returned), and
$\mathcal{D}$ can be used as compact model for approximating the data
distribution within the table without accessing the underlying contents.

In this paper, we obtain both upper and lower bounds for this problem. In
particular, we show that the problem of finding the best data distribution
from selectivity queries is $\mathsf{NP}$-complete. On the positive side, we
describe a Monte Carlo algorithm that constructs, in time
$O((n+\delta^{-d})\delta^{-2}\mathop{\mathrm{polylog}}n)$, a discrete
distribution $\tilde{\mathcal{D}}$ of size $O(\delta^{-2})$, such that
$\mathrm{err}_{p}(\tilde{\mathcal{D}},\mathcal{Z})\leq\min_{\mathcal{D}}\mathrm{err}_{p}(\mathcal{D},\mathcal{Z})+\delta$
(for $p=1,2,\infty$) where the minimum is taken over all discrete
distributions.  We also establish conditional lower bounds, which strongly
indicate the infeasibility of relative approximations as well as removal of
the exponential dependency on the dimension for additive approximations. This
suggests that significant improvements to our algorithm are unlikely.

###### keywords:

selectivity queries, discrete distributions, Multiplicative Weights Update,
eps-approximation, learnable functions, depth problem, arrangement

###### category:

##  1 Introduction

The _selectivity_ of a selection query on a set of objects in a database is
the probability of a random object in the database satisfying the query
predicate. A key step in query optimization, selectivity estimation is used by
databases for estimating costs of alternative query processing plans and
picking the best one. Consequently, selectivity estimation has been studied
extensively in the last few decades [30, 35, 42, 43, 45].

Historically, selectivity estimation has been data-driven. These approaches
construct, or dynamically maintain, a small-size synopsis of the data
distribution using histograms or random samples that minimize estimation
error. While these methods work well in low dimensions, they suffer from the
curse of dimensionality. As a result, interest in learning-based methods for
selectivity estimation has been growing over the years [23, 31, 32, 33, 37,
39]. Many different methods have been proposed that work with the data
distribution, observed selectivities from query workloads, or a combination of
both.  At a high-level, many of these techniques build a model of the
underlying data distribution and use it to answer queries. While they work
very well in practice, often outperforming their traditional counterparts, a
theoretical understanding of this line of work is missing. This leads to the
natural question, whether selectivity can be learned efficiently from a small
sample of query selectivities alone, without access to the data distribution.
Hu et al. [26] formalize the learnability of the selectivity estimation
problem in this setting. They use the agnostic-learning framework [24], an
extension of the classical PAC learning framework for real-valued functions,
where one is given a set of sample queries from a fixed query distribution and
their respective selectivities (the _training set_), and the goal is to
efficiently construct a data distribution so that the selectivity of a new
query from the same query distribution can be answered with high accuracy.
They show that for a wide class of range queries, the selectivity query can be
learned within error $\varepsilon\in(0,1)$ with probability at least
$1-\delta$ using a training set of size $\varepsilon^{-O(1)}\log\delta^{-1}$,
where the exponent of $\varepsilon$ depends on the query type; see [26] for a
precise statement of their results.  Informally, learnability implies that
performance of a model on the training set generalizes to unseen queries from
the same distribution. This reduces the task of learning to finding a (model
of the) data distribution that best fits the training data i.e. _Empirical
Risk Minimization (ERM)_.  Although Hu et al. [26] prove a sharp bound on the
sample complexity, their algorithm for ERM takes prohibitively long and
produces a data distribution of large size. They also present fast heuristics
to construct small-size data distributions, but they do not provide any
guarantee on the performance with respect to the best data distribution
fitting the training set. This raises the question of how to develop a
provably efficient and effective algorithm for constructing the best data
distribution (in a given family) from a training set.

Note that the size of the distribution computed by [26], can further be
reduced to $O(\varepsilon^{-2})$ by choosing an $\varepsilon$-approximation,
with an increase of $\varepsilon$ in the error; see [22] and Section 3 below.
However, the paper aims at computing a small-size distribution  (whose
performance is comparable to the best data distribution) directly and
efficiently, without constructing a large-size distribution first. For this
problem, we obtain hardness results as well as efficient algorithms.

Problem Statement. A _range space_ $\Sigma=(\mathcal{X},{\mathcal{R}})$
comprises a set of _objects_ $\mathcal{X}$ and a collection of subsets
${\mathcal{R}}\subseteq 2^{\mathcal{X}}$ called _ranges_. In this paper,
$\mathcal{X}$ is a finite set of points, and each range $R\in{\mathcal{R}}$
corresponds to a query that returns the subset of objects that fall within a
simple geometric region such as a rectangle (corresponding to an orthogonal
range query), a ball (neighborhood range query), or a half-space (query with a
linear constraint). We will not distinguish between a region $R$ and
$R\cap\mathcal{X}$, so with a slight abuse of notation, we will use
${\mathcal{R}}$ to denote a set of geometric regions such as a set of
rectangles or balls.

A _discrete distribution_ $\mathcal{D}=\\{(p_{1},w_{1}),...,(p_{m},w_{m})\\}$
is defined by a finite set of points and their associated probabilities, where
each $p_{i}$ is a point in $\mathbb{R}^{d}$ for some constant $d\geq 1$, each
$w_{i}>0$, and $\sum_{i=1}^{m}w_{i}=1$. We refer to the point set
$\\{p_{1},...,p_{m}\\}$ as the _support_ of $\mathcal{D}$ and denote it by
$\mathrm{supp}(\mathcal{D})$. The _size_ of a discrete distribution
$\mathcal{D}$ is defined as the size of its support and is denoted as
$|\mathcal{D}|$. Let $\mathbb{D}$ denote the family of all discrete
distributions, and let $\mathbb{D}_{k}$ be the family of discrete
distributions of size at most $k$. Given a range $R\subseteq{\mathcal{R}}$,
let $s_{\mathcal{D}}(R)=\sum_{i=1}^{m}\mathbbm{1}(p_{i}\in R)w_{i}$ denote the
_selectivity_ of $R$ over $\mathcal{D}$, which is the probability for a random
point drawn from $\mathcal{D}$ to lie in $R$ (or the total measure of
$\mathcal{D}$ inside $R$).

In this paper, our goal is to learn a (discrete) distribution from the
selectivities of range queries. For ease of exposition, we will describe our
results for rectangles (orthogonal ranges), although our techniques extend to
other natural range spaces.

Let $\mathcal{Z}=\\{z_{1},...,z_{n}\\}$ be a set of _training samples_ , where
$z_{i}=(R_{i},s_{i})$, $R_{i}$ is an axis-aligned rectangle (orthogonal range)
in $\mathbb{R}^{d}$, and $s_{i}\in[0,1]$ is its observed selectivity.111Note
that we do not assume the training set $\mathcal{Z}$ to be consistent with any
distribution distribution in $\mathbb{D}$, or any distribution in general;
i.e., there might not exist any distribution $\mathcal{D}$ such that $s_{i}$
reflects the selectivity of $R_{i}$ for every $1\leq i\leq n$. This
flexibility allows us to model settings where the query workload was executed
on an evolving database instance, and the observed selectivities on different
concrete instances may not be consistent with each other.  Let
${\mathcal{R}}=\\{R_{1},...,R_{n}\\}$ denote the set of ranges in
$\mathcal{Z}$. For a discrete distribution $\mathcal{D}\in\mathbb{D}$ and for
$p\geq 1$ we define the ($\ell_{p}$) empirical error to be

$\mathrm{err}_{p}(\mathcal{D},\mathcal{Z})=\frac{1}{n}\sum_{i=1}^{n}\left|{s_{\mathcal{D}}(R_{i})-s_{i}}\right|^{p},\text{
and for }p=\infty,\mathrm{err}_{\infty}(\mathcal{D},\mathcal{Z})=\max_{1\leq
i\leq n}\left|{s_{\mathcal{D}}(R_{i})-s_{i}}\right|.$ (1)

We focus on $p=1,2$, and $\infty$.

Let
$\alpha^{*}_{p}(\mathcal{Z})=\min_{\mathcal{D}\in\mathbb{D}}\mathrm{err}_{p}(\mathcal{D},\mathcal{Z})$
denote the minimum error achievable for all distributions in the family. Given
$\mathcal{Z}$, our goal is to compute a discrete distribution
$\tilde{\mathcal{D}}_{p}$ with
$\mathrm{err}(\tilde{\mathcal{D}}_{p},\mathcal{Z})=\alpha^{*}_{p}$. As argued
in [26], such a discrete distribution of size $O(n^{d})$ can be computed in
$n^{O(d)}$ time. However, this distribution is too large even for moderate
values of $n$ and $d$, so we are interested in computing a smaller size
distribution at the cost of a slight increase in the empirical error. Hence,
our problem becomes the following: given $\mathcal{Z}$ and some
$\delta\in[0,1]$, compute a small-size distribution $\mathcal{D}$, ideally of
size that depends on $\delta$ and independent of $n$, such that
$\mathrm{err}_{p}(\mathcal{D},\mathcal{Z})\leq\alpha^{*}_{p}+\delta$.
Alternatively, given a size budget $k$, compute a distribution
$\hat{\mathcal{D}}\in\mathbb{D}_{k}$ such that
$\mathrm{err}_{p}(\hat{\mathcal{D}},\mathcal{Z})=\min_{\mathcal{D}\in\mathbb{D}_{k}}\mathrm{err}_{p}(\mathcal{D},\mathcal{Z})$.

Our results. We present both negative and positive results for the data-
distribution222In this paper we focus on discrete distributions. For
simplicity, sometimes we use the term data distribution instead of discrete
distribution. learning problem. On the negative side in Section 5, we prove
that the problem is $\mathsf{NP}$-complete even for rectangles in
$\mathbb{R}^{2}$. Namely, given $\mathcal{Z}$ where ${\mathcal{R}}$ is a set
of rectangles in $\mathbb{R}^{2}$, $p\in\\{1,2,\infty\\}$, and two parameters
$\delta\in[0,1]$ and $k\geq 1$, the problem of determining whether there is a
data distribution $\mathcal{D}$ of size $k$ such that
$\mathrm{err}_{p}(\mathcal{D},\mathcal{Z})\leq\delta$ is $\mathsf{NP}$-hard.

On the positive side, we focus on designing an efficient algorithm for
constructing a small-size distribution with additive-approximation error. We
present a Monte Carlo algorithm that computes, with high probability, a
discrete distribution $\tilde{\mathcal{D}}$ of size $O(\delta^{-2})$ with
$\mathrm{err}_{p}(\tilde{\mathcal{D}},\mathcal{Z})\leq\alpha^{*}_{p}+\delta$,
for $p\in\\{1,2,\infty\\}$, in $O(n\delta^{-2}\log n+\delta^{-d-2}\log^{3}n)$
time (exact time complexity is given in Lemma 3.117). Starting with $p=1$
($\ell_{1}$ empirical error), we first present in Section 2 a basic algorithm
that maps our problem to a linear program ($\mathsf{LP}$) with $O(n)$
constraints and $O(n^{d})$ variables. We show how the Multiplicative-Weight-
Update (MWU) method [4] can be used to solve this $\mathsf{LP}$. A naive
implementation of the MWU of this algorithm takes $\Omega(n^{d})$ time. Next,
in Section 3, we exploit underlying geometry in two ways to solve this
$\mathsf{LP}$ involving exponential number of variables efficiently, by
representing it implicitly. First, we give a geometric interpretation to the
main step of the MWU method: we map a maximization problem with $O(n^{d})$
variables to the problem of finding the weighted deepest point in an
arrangement of $n$ rectangles in $\mathbb{R}^{d}$. The best algorithm to solve
this geometric problem takes $O(n^{d/2})$ time [8], which would allow one to
improve the running time to $O(\delta^{-2}n^{d/2}\log n)$. But this is also
expensive. Second, we use the notion of $\varepsilon$-approximation to quickly
compute an approximately deepest point in a weighted set of rectangles
efficiently, in time $O(\delta^{-d}\log n)$.

In Section 4 we extend our algorithm to more general settings. We show that
our near-linear time algorithm works for the $\ell_{\infty}$ and the
$\ell_{2}$ empirical error. Furthermore, we show that our algorithm can be
extended to other ranges such as balls and halfspaces in $\mathbb{R}^{d}$.

In Section 5, we also give conditional lower bounds that indicate that
avoiding the exponential dependency on $d$ is not possible even for additive
approximations. This makes meaningful improvements to our algorithm unlikely.
We also give conditional lower bounds for a variant of our problem, allowing
an arbitrary relative approximation factor on the size of the distribution or
an arbitrary relative approximation factor on the error of the returned
distribution. Our conditional hardness results are based on the $FPT\neq W[1]$
conjecture; see [13] for the definition. Finally, we also show that when the
distribution size is fixed, any relative approximation is $\mathsf{NP}$-hard.

##  2 Basic Algorithm

In this section we present our basic algorithm for computing a small-size
discrete distribution that (approximately) minimizes the $\ell_{1}$ empirical
error. For simplicity, let $\mathrm{err}(\cdot,\cdot)$ and $\alpha^{*}$ denote
$\mathrm{err}_{1}(\cdot,\cdot)$ and $\alpha^{*}_{1}$, respectively. Given a
training set $\mathcal{Z}$ and a parameter $\delta\in(0,1)$, it computes a
discrete distribution $\mathcal{D}^{*}$ of size $O(\delta^{-2}\log n)$ such
that $\mathrm{err}(\mathcal{D}^{*},\mathcal{Z})=\alpha^{*}+\delta$. At the
heart, there is a decision procedure IsFeasible that, given $\mathcal{Z}$ and
parameters $\alpha,\delta\in(0,1)$, returns a distribution $\mathcal{D}^{*}$
with $\mathrm{err}(\mathcal{D}^{*},\mathcal{Z})\leq\alpha+\delta/2$ if
$\alpha\geq\alpha^{*}$ and returns No if $\alpha<\alpha^{*}$.

We do not know the value of $\alpha^{*}$, so we perform a binary search on the
value of $\alpha$. In particular, let
$E=\\{\frac{\delta}{2},(1+\frac{\delta}{2})\frac{\delta}{2},(1+\frac{\delta}{2})^{2}\frac{\delta}{2},\ldots,1\\}$
be a discretization of the range $[0,1]$, and let $\alpha_{j}$ be the $j$-th
value of $E$. Suppose the binary search currently guesses $\alpha_{i}$ to be
the current guess of $\alpha^{*}$. If
$\textsc{IsFeasible}(\mathcal{Z},\delta,\alpha_{i})$ returns a distribution
$\mathcal{D}$, we continue the binary search for values less than $\alpha_{i}$
in $E$. Otherwise, we continue the binary search for values greater than
$\alpha_{i}$ in $E$. At the end of the binary search, we return the last
distribution $\mathcal{D}^{*}$ that IsFeasible found. Assuming the correctness
of the decision procedure, the algorithm returns the desired distribution in
$\log\frac{1}{\delta}$ iterations. If $\alpha^{*}\leq\delta/2$, then
$\textsc{IsFeasible}(\mathcal{Z},\delta,\alpha_{1})$ returns a distribution
$\mathcal{D}^{*}$ such that
$\mathrm{err}(\mathcal{D}^{*},\mathcal{Z})\leq\alpha_{1}+\delta/2=\delta\leq\alpha^{*}+\delta$.
In any other case, without loss of generality assuming that
$\alpha_{i-1}<\alpha^{*}\leq\alpha_{i}$, we have
$\alpha_{i}\leq(1+\delta/2)\alpha^{*}$. By definition,
$\textsc{IsFeasible}(\mathcal{Z},\delta,\alpha_{i})$ returns a distribution
$\mathcal{D}_{i}$ such that
$\mathrm{err}(\mathcal{D}_{i},\mathcal{Z})\leq\alpha_{i}+\delta/2$. Hence,

$\mathrm{err}(\mathcal{D}^{*},\mathcal{Z})\leq\mathrm{err}(\mathcal{D}_{i},\mathcal{Z})\leq\alpha_{i}+\delta/2\leq(1+\delta/2)\alpha^{*}+\delta/2\leq\alpha^{*}+\delta.$

We now describe the decision procedure IsFeasible.

###  2.1 Decision procedure

Let $\mathcal{Z},\delta$, and $\alpha$ be as defined above. The decision
problem can be formulated as follows:

($\mathsf{FP}$1)

$\displaystyle\quad\quad\exists?\text{ }\mathcal{D}\in\mathbb{D}\text{ s.t.}$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}u_{i}$ $\displaystyle\leq\alpha$
$\displaystyle\left|{s_{\mathcal{D}}(R_{i})-s_{i}}\right|$ $\displaystyle\leq
u_{i}\quad\quad\text{ for }i=1\ldots n$ $\displaystyle u_{i}$
$\displaystyle\in[0,1]\quad\text{for }i=1\ldots n.$

Here $u_{i}$ models the error in the selectivity of $R_{i}$. A challenge in
solving the above decision problem is determining the candidate set of points
in $\mathrm{supp}(\mathcal{D})$. The problem as stated is infinite-
dimensional. Our next lemma suggests how to reduce it to a finite-dimensional
problem by constructing a finite set of candidate points for
$\mathrm{supp}(\mathcal{D})$.

The _arrangement_ of ${\mathcal{R}}$, denoted
$\mathop{\mathrm{\EuScript{A}}}({\mathcal{R}})$, is a partitioning of
$\mathbb{R}^{d}$ into contiguous regions called _cells_ such that for every
($d$-dimensional) cell $\mathsf{\tau}$ in the arrangement, $\mathsf{\tau}$
lies in the same subset of ${\mathcal{R}}$. For each $d$-dimensional cell
$\mathsf{\tau}\in\mathop{\mathrm{\EuScript{A}}}({\mathcal{R}})$, we choose an
arbitrary point $p_{\mathsf{\tau}}$ in the interior of $\mathsf{\tau}$. Let
$\mathcal{P}=\\{p_{\mathsf{\tau}}\mid\mathsf{\tau}\in\mathop{\mathrm{\EuScript{A}}}({\mathcal{R}})\\}$
be the set of candidate points. Note that
$\mathop{\mathrm{\EuScript{A}}}({\mathcal{R}})$ has $O(n^{d})$ cells, and it
can be computed in $O(n^{d}\log n)$ time [2]. Therefore,
$\left|{\mathcal{P}}\right|=O(n^{d})$ and $\mathcal{P}$ can be computed in
$O(n^{d}\log n)$ time.

Figure 1: The (black) points $q_{i}$ represent points from the underlying data
distribution $\mathcal{D}$ while (blue) points
$p_{\mathsf{\tau}}\in\mathcal{P}$. The (green) dashed segments show three
cells of the arrangement in rectangle $R$. The weights of points in
$\mathcal{P}$ are: $w(p_{1})=w_{1}+w_{3}$, $w(p_{2})=w_{2}$,
$w(p_{3})=w_{4}+w_{5}$, $w(p_{4})=w_{6}+w_{8}$, $w(p_{5})=w_{7}$.

######  Lemma 2.1.

For any discrete distribution $\mathcal{D}\in\mathbb{D}$, there is another
discrete distribution $\mathcal{D}^{\prime}$ such that
$\mathrm{supp}(\mathcal{D}^{\prime})\subseteq\mathcal{P}$ and
$\mathrm{err}(\mathcal{D},\mathcal{Z})=\mathrm{err}(\mathcal{D}^{\prime},\mathcal{Z})$.

######  Proof 2.2.

For each $d$-dimensional cell
$\mathsf{\tau}\in\mathop{\mathrm{\EuScript{A}}}({\mathcal{R}})$, let

$w_{\mathsf{\tau}}=\\!\\!\\!\\!\\!\sum_{p_{i}\in\mathrm{supp}(\mathcal{D})}\\!\\!\\!\\!\\!\\!\\!\mathbbm{1}(p_{i}\in\mathsf{\tau})w_{i}$

be the total weight of points of $\mathrm{supp}(\mathcal{D})$ that lie in
$\mathsf{\tau}$. We define

$\mathcal{D}^{\prime}=\\{(p_{\mathsf{\tau}},w_{\mathsf{\tau}})\mid\mathsf{\tau}\in\mathop{\mathrm{\EuScript{A}}}({\mathcal{R}}),w_{\mathsf{\tau}}>0\\}.$

See also Figure 1. By definition, for any rectangle $R\in{\mathcal{R}}$, the
cells of $\mathop{\mathrm{\EuScript{A}}}({\mathcal{R}})$ lying inside $R$
induce a partitioning of $R$. Let
$\mathop{\mathrm{\EuScript{A}}}({\mathcal{R}}\mid R)$ denote this partitioning
of $R$ into cells. Then

$\displaystyle s_{\mathcal{D}^{\prime}}(R)$
$\displaystyle=\\!\\!\\!\\!\sum_{p_{\mathsf{\tau}}\in\mathcal{P}}\\!\\!\\!\mathbbm{1}(p_{\mathsf{\tau}}\in
R)w_{\mathsf{\tau}}=\\!\\!\\!\\!\sum_{\mathsf{\tau}\in\mathop{\mathrm{\EuScript{A}}}({\mathcal{R}}\mid
R)}\\!\\!\\!\\!\\!\\!\\!w_{\mathsf{\tau}}=\\!\\!\\!\sum_{\mathsf{\tau}\in\mathop{\mathrm{\EuScript{A}}}({\mathcal{R}}\mid
R)}\sum_{p_{i}\in\mathsf{\tau}\cap\mathrm{supp}(\mathcal{D})}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!w_{i}$
$\displaystyle=\\!\\!\\!\\!\\!\\!\sum_{p_{i}\in\mathrm{supp}(\mathcal{D})}\\!\\!\\!\\!\\!\\!\\!\\!\mathbbm{1}(p_{i}\in
R)w_{i}=s_{\mathcal{D}}(R).$

Hence,
$\mathrm{err}(\mathcal{D},\mathcal{Z})=\mathrm{err}(\mathcal{D}^{\prime},\mathcal{Z})$.

Remark. We note that the choice of point $p_{\mathsf{\tau}}$ in each cell
$\mathsf{\tau}\in\mathop{\mathrm{\EuScript{A}}}({\mathcal{R}})$ is arbitrary;
one can use any point in $\mathsf{\tau}$ as its representative point.

In view of Lemma 2.1, it suffices to restrict $\mathrm{supp}(\mathcal{D})$ to
be a subset of $\mathcal{P}$. We order the cells of
$\mathop{\mathrm{\EuScript{A}}}({\mathcal{R}})$ arbitrarily and let $p_{j}$
denote the point chosen from the $j$-th cell, so
$\mathcal{P}=\\{p_{1},\ldots,p_{m}\\}$ where $m=|P|$. We introduce a real
variable $v_{j}\in[0,1]$ that models the weight of $p_{j}\in\mathcal{P}$. Then
($\mathsf{FP}$2.1) can be rewritten as

($\mathsf{FP}$2)

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}u_{i}$ $\displaystyle\leq\alpha$
$\displaystyle\left|\sum_{j:p_{j}\in R_{i}}v_{j}-s_{i}\right|$
$\displaystyle\leq u_{i}\quad\quad\text{for }i=1\ldots n$ (2)
$\displaystyle\sum_{j=1}^{m}v_{j}$ $\displaystyle\leq 1$ (3) $\displaystyle
u_{i},v_{j}$ $\displaystyle\in[0,1]\quad\text{ for }i=1\ldots n,\;j=1\ldots m$

We require that the sum of weights of the discrete distribution we compute is
at most $1$ because, for any distribution returned with $\sum_{j}^{m}v_{j}<1$,
we can add an arbitrary point that is not contained in any range with weight
$1-\sum_{j}^{m}v_{j}$.

The above decision problem can be written as a linear program by replacing (2)
with two linear inequalities.

($\mathsf{LP}$1)

$\displaystyle-\frac{1}{n}\sum_{i=1}^{n}u_{i}$ $\displaystyle\geq-\alpha$ (4)
$\displaystyle u_{i}-\sum_{j:p_{j}\in R_{i}}v_{j}$ $\displaystyle\geq-
s_{i}\quad\quad\text{for }1\leq i\leq n$ (5) $\displaystyle
u_{i}+\sum_{j:p_{j}\in R_{i}}v_{j}$ $\displaystyle\geq s_{i}\quad\quad\text{
for }1\leq i\leq n$ (6) $\displaystyle\sum_{j=1}^{m}v_{j}$ $\displaystyle\leq
1$ (7) $\displaystyle u_{i},v_{j}$ $\displaystyle\in[0,1]\quad\text{ for
}i=1\ldots n,\;j=1\ldots m$

It will be convenient to write the above $\mathsf{LP}$ in a compact form. Let
$\mathsf{u}=(u_{1},\ldots,u_{n})$, $\mathsf{v}=(v_{1},\ldots,v_{m})$, and
$\mathsf{x}=(\mathsf{u},\mathsf{v})$. Set

$\mathbb{X}=\\{\mathsf{x}=(\mathsf{u},\mathsf{v})\in[0,1]^{n+m}\mid\lVert{\mathsf{v}}\rVert_{1}\leq
1\\}.$

For $0\leq\kappa\leq 2n$, let
$\mathsf{A}_{\kappa}\mathsf{x}\geq\mathsf{b}_{\kappa}$ denote the $\kappa$-th
constraint of (4), (5), (6). Namely,
$\mathsf{A}_{0}\mathsf{x}\geq\mathsf{b}_{0}$ denotes (4), and for $1\leq i\leq
n$, $\mathsf{A}_{2i-1}\mathsf{x}\geq\mathsf{b}_{2i-1}$ and
$\mathsf{A}_{2i}\mathsf{x}\geq\mathsf{b}_{2i}$ denote the constraints (5) and
(6), respectively, for the rectangle $R_{i}$. Then ($\mathsf{LP}$2.1) asks
whether there exists an $\mathsf{x}\in\mathbb{X}$ such that
$\mathsf{A}\mathsf{x}\geq\mathsf{b}$.

We use a Multiplicative-Weight-Update (MWU) method to solve this linear
program, following the general approach described by Arora et al. [4], though
the exact implementation depends on the specific $\mathsf{LP}$; see also [41].
We describe how this approach is implemented in our setting. We will need this
algorithm for the faster implementation described in Section 3.

###  2.2 MWU algorithm

We describe an algorithm that either returns a
$\tilde{\mathsf{x}}\in\mathbb{X}$ such that
$\mathsf{A}\tilde{\mathsf{x}}\geq\mathsf{b}-\delta/4$ or returns that there is
no feasible solution for ($\mathsf{LP}$2.1). We set two parameters
$\eta=\frac{\delta}{c_{1}}$ and
$T=\left\lceil{c_{2}\delta^{-2}\ln(2n+1)}\right\rceil$, where $c_{1},c_{2}>0$
are sufficiently large constants to be chosen later. The algorithm works in
$T$ rounds. At the beginning of round $t$, it has a $(2n+1)$-dimensional
probability vector $\mathsf{w}=(w_{0},\ldots,w_{2n})$. Initially,
$\mathsf{w}=(\frac{1}{2n+1},\ldots,\frac{1}{2n+1})$. In the $t$-th round, the
algorithm solves the decision problem consisting of one constraint

${\mathsf{w}}^{\top}\mathsf{A}\mathsf{x}\geq{\mathsf{w}}^{\top}\mathsf{b},\quad\mathsf{x}\in\mathbb{X}$
(8)

which we refer to as the _expected constraint_. The algorithm computes, as
described below,
$\mathsf{x}=\operatorname*{arg\,max}_{x\in\mathbb{X}}{\mathsf{w}}^{\top}\mathsf{A}\mathsf{x}$.

If ${\mathsf{w}}^{\top}\mathsf{A}\mathsf{x}<{\mathsf{w}}^{\top}\mathsf{b}$, we
conclude that ($\mathsf{LP}$2.1) is infeasible because, by definition, any
feasible solution of ($\mathsf{LP}$2.1) satisfies (8), and we return No.
Otherwise, for $i=0\ldots 2n$, we set

$w_{i}=w_{i}\frac{1-\eta(\mathsf{A}_{i}\mathsf{x}-\mathsf{b}_{i})}{\mu}$ (9)

where $\mu$ is a normalization factor so that
$\lVert{\mathsf{w}}\rVert_{1}=1$.

If the algorithm does not return No within the first $T$ rounds, then after
completing $T$ rounds, it returns
$\tilde{\mathsf{x}}=\frac{1}{T}\sum_{i=1}^{T}\mathsf{x}$. Suppose
$\tilde{\mathsf{x}}=(\tilde{\mathsf{u}},\tilde{\mathsf{v}})$. We return the
distribution $\tilde{D}=\\{(p_{j},\tilde{v}_{j})\mid\tilde{v}_{j}>0\\}$.

Computing $\boldsymbol{\mathsf{x}}$. We now describe the computation of
$\mathsf{x}=(u_{1},\ldots,u_{n},v_{1},\ldots,v_{m})$ at each step. We can
express the LHS of the expected constraint (8) as

${\mathsf{w}}^{\top}\mathsf{A}\mathsf{x}=\sum_{i=1}^{n}\varphi_{i}u_{i}+\sum_{j=1}^{m}\psi_{j}v_{j}$
(10) $\displaystyle\text{where }\quad\varphi_{i}$
$\displaystyle=w_{2i}+w_{2i-1}-\frac{w_{0}}{n}\quad\text{for }1\leq i\leq n,$
(11) $\displaystyle\psi_{j}$ $\displaystyle=\sum_{i:p_{j}\in
R_{i}}w_{2i}-w_{2i-1}\quad\text{for }1\leq j\leq m.$ (12)

Note that the two terms in (10) do not share variables and (7) does not
involve $u_{i}$’s, so we can maximize each of them independently. Recall that
$u_{i}\in[0,1]$, so to maximize (10), we choose for $1\leq i\leq n$,

$u_{i}=\begin{cases}1&\text{if }\varphi_{i}>0,\\\
0&\text{otherwise.}\end{cases}$ (13)

Next, we choose $v_{j}$ as follows. Let $j=\operatorname*{arg\,max}_{1\leq
j\leq m}\psi_{j}$. Since $\mathsf{v}\in[0,1]^{m}$ and
$\lVert{\mathsf{v}}\rVert_{1}\leq 1$ for
$(\mathsf{u},\mathsf{v})\in\mathbb{X}$, we choose for $1\leq j\leq m$,

$v_{j}=\begin{cases}1&\text{if }j=j\text{ and }\psi_{j}>0,\\\
0&\text{otherwise.}\end{cases}$ (14)

Note that although many $u_{i}$’s could be set to $1$, at most one $v_{j}$ is
set to $1$. This property will be crucial for our faster implementation in the
next section. Since at most $T$ $v_{j}$’s are non-zero,
$|\tilde{\mathcal{D}}|\leq T=O(\delta^{-2}\log n)$.

This completes the description of our basic algorithm. We now analyze its
running time and correctness.

###  2.3 Analysis

######  Lemma 2.45.

Assume that the MWU algorithm returns a solution $\tilde{\mathsf{x}}$ after
$T$ rounds. Then
$\mathsf{A}_{i}\tilde{\mathsf{x}}\geq\mathsf{b}_{i}-\delta/4$, for every
$0\leq i\leq 2n$.

######  Proof 2.46.

It is straightforward to verify that for any round $1\leq t\leq T$,
$|\mathsf{A}_{i}\mathsf{x}-\mathsf{b}_{i}|\leq 2$. Let
$\mathcal{T}^{-}_{i}=\\{t\leq
T\mid\mathsf{A}_{i}\mathsf{x}-\mathsf{b}_{i}<0\\}$ be the subset of rounds
where $\mathsf{A}_{i}\mathsf{x}-\mathsf{b}_{i}<0$. Using the analysis in Arora
et al. [4] (see the proof of Theorem 3.3), for every $0\leq i\leq 2n$, we
obtain,

$\displaystyle 0$
$\displaystyle\leq\sum_{t=1}^{T}\frac{1}{2}(\mathsf{A}_{i}\mathsf{x}-\mathsf{b}_{i})+\eta\sum_{t=1}^{T}\frac{1}{2}|\mathsf{A}_{i}\mathsf{x}-\mathsf{b}_{i}|+\frac{\ln(2n+1)}{\eta}$
$\displaystyle=(1+\eta)\sum_{t=1}^{T}\frac{1}{2}(\mathsf{A}_{i}\mathsf{x}-\mathsf{b}_{i})+2\eta\sum_{t\in\mathcal{T}^{-}_{i}}\frac{1}{2}|\mathsf{A}_{i}\mathsf{x}-\mathsf{b}_{i}|+\frac{\ln(2n+1)}{\eta}$
$\displaystyle\leq(1+\eta)\sum_{t=1}^{T}\frac{1}{2}(\mathsf{A}_{i}\mathsf{x}-\mathsf{b}_{i})+2\eta
T+\frac{\ln(2n+1)}{\eta}.$

The last inequality follows because
$|\mathsf{A}_{i}\mathsf{x}-\mathsf{b}_{i}|\leq 2$. Noting that
$\tilde{\mathsf{x}}=\frac{1}{T}\sum_{i=1}^{T}\mathsf{x}$, we get
$0\leq(1+\eta)(\mathsf{A}_{i}\tilde{\mathsf{x}}-\mathsf{b}_{i})+4\eta+\frac{2\ln(2n+1)}{\eta
T}$. By choosing $c_{1}=32$ and $c_{2}=512$, we obtain
$\eta=\frac{\delta}{32}$ and
$T=\left\lceil{512\delta^{-2}\ln(2n+1)}\right\rceil$. Therefore

$(1+\eta)(\mathsf{A}_{i}\tilde{\mathsf{x}}-\mathsf{b}_{i})+\delta/4\geq
0\Leftrightarrow\mathsf{A}_{i}\tilde{\mathsf{x}}\geq\mathsf{b}_{i}-\delta/4.$

######  Lemma 2.57.

Given a training set $\mathcal{Z}$ and parameters $\alpha,\delta$, the
algorithm IsFeasible either returns a discrete distribution
$\tilde{\mathcal{D}}$ of size $O(\delta^{-2}\log n)$ such that
$\mathrm{err}(\tilde{\mathcal{D}},\mathcal{Z})\leq\alpha+\delta/2$, or returns
No for $\alpha<\alpha^{*}$.

######  Proof 2.58.

First, by definition, our algorithm always solves the expected constraint
optimally. Hence, if the algorithm stops in iteration $t\leq T$ (because we
cannot satisfy the expected constraint
${\mathsf{w}}^{\top}\mathsf{A}\mathsf{x}\geq{\mathsf{w}}^{\top}\mathsf{b}$ for
$\mathsf{x}\in\mathbb{X}$) then it is also true that there is no
$\mathsf{x}\in\mathbb{X}$ such that $\mathsf{A}\mathsf{x}\geq\mathsf{b}$. So
the algorithm correctly returns that the $\mathsf{LP}$ is infeasible and
$\alpha<\alpha^{*}$.

Next, assume that the algorithm returns $\tilde{\mathcal{D}}$. Recall that
$\tilde{\mathsf{x}}=(\tilde{\mathsf{u}},\tilde{\mathsf{v}})=(\tilde{u}_{1},\ldots,\tilde{u}_{n},\tilde{v}_{1},\ldots,\tilde{v}_{n})\in\mathbb{X}$.
Since $\mathbb{X}$ is convex and $\mathsf{x}\in\mathbb{X}$ for each $1\leq
t\leq T$, it also holds that $\tilde{\mathsf{x}}\in\mathbb{X}$ and
$\lVert{\tilde{\mathsf{v}}}\rVert_{1}\leq 1$. Hence, it follows that
$\tilde{\mathcal{D}}$ is indeed a distribution of size at most
$T=O(\delta^{-2}\log n)$. From Lemma 2.45 and the equivalence of
($\mathsf{FP}$2.1) and ($\mathsf{LP}$2.1), we get

$\frac{1}{n}\sum_{i=1}^{n}\tilde{u}_{i}\leq\alpha+\delta/4\quad\text{and}\quad\left|\sum_{j:p_{j}\in
R_{i}}\tilde{v}_{j}-s_{i}\right|\leq u_{i}+\delta/4$

for $i=1\ldots n$. Recall that
$s_{\tilde{\mathcal{D}}}(R_{i})=\sum_{j}\mathbbm{1}(p_{j}\in
R_{i})\tilde{v}_{j}$. Hence

$\displaystyle\mathrm{err}(\tilde{\mathcal{D}},\mathcal{Z})$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}|s_{\tilde{\mathcal{D}}}(R_{i})-s_{i}|\leq\frac{1}{n}\sum_{i=1}^{n}\tilde{u}_{i}+\delta/4\leq\alpha+\delta/4+\delta/4=\alpha+\delta/2.$

As for the running time, the binary search executes $O(\log\frac{1}{\delta})$
iterations, each of which runs the IsFeasible algorithm. We need $O(m\log
n)=O(n^{d}\log n)$ time to construct ($\mathsf{LP}$2.1). The IsFeasible
algorithm runs for $T=O(\delta^{-2}\log n)$ rounds. In each round $t$, we need
$O(n)$ time to compute the values of $\mathsf{u}$ by (11) and (13). We need
$O(m\log n)=O(n^{d}\log n)$ time to find all the values $\psi_{j}$ by (12).
Putting everything together, we have the following lemma.

######  Lemma 2.64.

The algorithm runs in $O(\delta^{-2}n^{d}\log^{2}n\log\delta^{-1})$ time.

##  3 The Improved Algorithm

We present an implementation of a small variant of the algorithm in the last
section that computes the desired distribution with high probability in
$n(\delta^{-1}\log n)^{O(1)}$ time (see Theorem 3.122 below for a more precise
characterization). There are two challenges in implementing the IsFeasible
procedure efficiently. First, ($\mathsf{LP}$2.1) has $O(n^{d})$
variables—although $\mathsf{u}$ has dimension $n$, $\mathsf{v}$ has dimension
$m=O(n^{d})$—so we cannot afford to represent ($\mathsf{LP}$2.1) explicitly.
Second, in each round $t$, computing $\mathsf{u}$ is easy, but computing
$\mathsf{v}$ quickly seems challenging even though only one of the values in
$\mathsf{v}$ is non-zero. We exploit underlying geometry to address both
challenges. We first describe how to implement IsFeasible without writing the
$\mathsf{LP}$ explicitly and then describe how to compute $\mathsf{x}$
quickly.

Implicit representation of $\boldsymbol{\mathsf{LP}}$. We maintain the
probability vector $\mathsf{w}$ as before. We also maintain a multi-set
$\mathcal{F}\subset\mathbb{R}^{d}$ of points. Initially,
$\mathcal{F}=\emptyset$. Each round adds one point to $\mathcal{F}$, so
$\left|{\mathcal{F}}\right|\leq T=O(\delta^{-2}\log n)$. Since we have
$\mathsf{w}$ at our disposal, we can compute $u_{i}$, for $1\leq i\leq n$,
using (11) and (13) as before. The main question is how to compute
$j=\operatorname*{arg\,max}_{1\leq j\leq m}\psi_{j}$ without maintaining all
the variables explicitly. For each rectangle $R_{i}\in{\mathcal{R}}$, let
$\omega(R_{i})=w_{2i}-w_{2i-1}$. For each point $x\in\mathbb{R}^{d}$, we
define its _depth_ with respect to $({\mathcal{R}},\omega)$, denoted by
$0pt(x)$, to be

$0pt(x)=\sum_{R\in{\mathcal{R}}}\mathbbm{1}(x\in R)\omega(R).$

It is easily checked that the depth of all points lying in the same cell of
$\mathop{\mathrm{\EuScript{A}}}({\mathcal{R}})$ is the same, and that many
cells may have the same depth. By the definition of the depth,
$\psi_{j}=0pt(p_{j})$. Thus the problem of computing $j$ is equivalent to
choosing a point $p$ in $\mathbb{R}^{d}$ of the maximum depth, i.e.,
$0pt(p)=\max_{p\in\mathbb{R}^{d}}0pt(p)$. Chan [8] has described an
$O(n^{d/2})$ time algorithm to compute a point of maximum depth in a set of
$n$ weighted rectangles in $\mathbb{R}^{d}$. We refer to this algorithm as
$\textsc{ DeepestPt}({\mathcal{R}},\mathsf{\omega})$, where ${\mathcal{R}}$ is
a set of $n$ rectangles in $\mathbb{R}^{d}$ and
$\mathsf{\omega}\in\mathbb{R}^{n}$ is the weight vector.

We thus proceed in the $t$-th round of IsFeasible as follows. First, compute
the vector $\mathsf{u}$ as before. Next, we compute the deepest point $p$ by
calling $\textsc{ DeepestPt}({\mathcal{R}},\mathsf{\omega})$. If $0pt(p)>0$,
then we add $p$ to the set $F$; otherwise we ignore it. Intuitively, this is
equivalent to setting $v_{j}=1$ if $\psi_{j}>0$ and $0$ otherwise. We do not
know how to compute $j$ efficiently and thus cannot compute which $v_{j}$
needs to be set to $1$. But what comes to our rescue is that we only need to
compute $w_{q}\mathsf{A}_{q}\mathsf{x}$, for all $0\leq q\leq 2n$, to check
whether the expected constraint holds and to update the weight factors.
Fortunately, we can accomplish this using only $\mathsf{u}$ and $p$, without
an explicit representation of $\mathsf{x}$, as follows. We set
$w_{2i-1}\mathsf{A}_{2i-1}\mathsf{x}=w_{2i-1}u_{i}$ and
$w_{2i}\mathsf{A}_{2i}\mathsf{x}=\mathsf{w}_{2i}u_{i}$ if $0pt(p)\leq 0$ or
$p\notin R_{i}$, and we set
$w_{2i-1}\mathsf{A}_{2i-1}\mathsf{x}=w_{2i-1}(u_{i}-1)$ and
$w_{2i}\mathsf{A}_{2i}\mathsf{x}=w_{2i}(u_{i}+1)$ if $0pt(p)>0$ and $p\in
R_{i}$. It can be checked that these values are the same as when we set
$v_{j}$ as above.

After having computed $w_{q}\mathsf{A}_{q}\mathsf{x}$ for all $0\leq q\leq
2n$, we check whether
${\mathsf{w}}^{\top}\mathsf{A}\mathsf{x}<{\mathsf{w}}^{\top}\mathsf{b}$. If
so, we stop and return No. Otherwise, we compute $\mathsf{w}$ using (9) as
before. If the algorithm is not aborted within the first $T$ rounds, we return
$\hat{\mathcal{D}}=\\{(p,\frac{1}{T})\mid p\in\mathcal{F}\\}$. Recall that
$\mathcal{F}$ is a multi-set. If there are $s$ copies of a point $p$, we keep
only one copy of $p$ and set its weight to $\frac{s}{T}$. The following lemma
establishes the correctness of the algorithm.

######  Lemma 3.49.

Given $\mathcal{Z}$ and $\delta\in[0,1]$,
$\mathrm{err}(\tilde{\mathcal{D}},\mathcal{Z})=\mathrm{err}(\hat{\mathcal{D}},\mathcal{Z})$.

######  Proof 3.50.

For simplicity, we assume that for any $\mathsf{\omega}$, $1\leq t\leq T$, the
maximum-depth cell in $\mathop{\mathrm{\EuScript{A}}}({\mathcal{R}})$ with
respect to $\mathsf{\omega}$ is unique and that $j$ are distinct for each
$t\leq T$. Then by the definition of depth, $p$ and $p_{j}$ lie in the same
cell of $\mathop{\mathrm{\EuScript{A}}}({\mathcal{R}})$, so the value of
${\mathsf{w}}^{\top}\mathsf{A}\mathsf{x}$ computed by the implicit algorithm
is the same as ${\mathsf{w}}^{\top}\mathsf{A}\mathsf{x}$ computed by the basic
algorithm. Hence, assuming $\mathsf{w}$ computed by the two algorithms is the
same, $\mathsf{w}$ computed by them is also the same. Recall that $v_{j}$ is
set to $1$ if and only if $\psi_{j}>0$, which is the same condition when $p$
is added to $\mathcal{F}$ by the implicit algorithm. $v_{j}=1$ if and only if
$p\in F$. Hence, $p_{j}\in\mathrm{supp}(\tilde{\mathcal{D}})$ if and only if
$p\in\mathrm{supp}(\hat{\mathcal{D}})$ and $p_{j}$ and $p$ lie in the same
cell of $\mathop{\mathrm{\EuScript{A}}}({\mathcal{R}})$. The same argument as
in Lemma 2.1 now implies that
$\mathrm{err}(\tilde{\mathcal{D}},\mathcal{Z})=\mathrm{err}(\hat{\mathcal{D}},\mathcal{Z})$.

Fast computation of $\boldsymbol{p}$. The main observation is that it is not
crucial to compute
$\mathsf{x}=\operatorname*{arg\,max}_{\mathsf{x}\in\mathbb{X}}{\mathsf{w}}^{\top}\mathsf{A}\mathsf{x}$
in the $t$-th round of the MWU algorithm. Instead, it suffices to compute
$\tilde{\mathsf{x}}$ such that
${\mathsf{w}}^{\top}\mathsf{A}\tilde{\mathsf{x}}\geq{\mathsf{w}}^{\top}\mathsf{A}\mathsf{x}-\delta/12$.
In the terminology of the implicit $\mathsf{LP}$ algorithm, this is equivalent
to saying that it suffices to compute a point $\tilde{p}$ with
$0pt(\tilde{p})\geq\max_{p\in\mathbb{R}^{d}}0pt(p)-\delta/12$. We use
$\varepsilon$-approximations and random sampling [22, 10] to compute
$\tilde{p}$ quickly. The notion of $\varepsilon$-approximation is defined for
general range spaces but we define $\varepsilon$-approximation in our setting.

Given a set ${\mathcal{R}}$ of rectangles and a weight function
$\omega:{\mathcal{R}}\rightarrow[0,1]$ a multi-subset
$\mathcal{N}\subset{\mathcal{R}}$ is called an _$\varepsilon$ -approximation_
of $({\mathcal{R}},\omega)$ if for any point $x\in\mathbb{R}^{d}$,

$\left|{\frac{0pt(x,{\mathcal{R}},\omega)}{\omega({\mathcal{R}})}-\frac{0pt(x,\mathcal{N})}{\left|{\mathcal{N}}\right|}}\right|\leq\varepsilon,$
(15)

where $\Delta(x,{\mathcal{R}},\omega)$ is the weighted depth of point $x$ in
the set of rectangles ${\mathcal{R}}$ with weights $\omega$, and
$\Delta(x,\mathcal{N})$ is the depth of point $x$ in the set of rectangles
$\mathcal{N}$ assuming that the weight of each rectangle in $\mathcal{N}$ is
$1$.

Let $A$ be a random (multi-)subset of ${\mathcal{R}}$ of size
$O(\varepsilon^{-2}\ln\phi^{-1})$ where at each step each rectangle of
${\mathcal{R}}$ is chosen with probability proportional to its weight (with
repetition). It is well known [22, 10] that $A$ is an
$\varepsilon$-approximation with probability at least $1-\phi$. With this
result at our disposal, we compute $\tilde{p}$, an approximately deepest point
with respect to $({\mathcal{R}},\mathsf{w})$, as follows. Let $\mathsf{w}$ be
as defined above. Let $\mathsf{w}^{+}=(w^{+}_{1},\ldots,w^{+}_{n})$ and
$\mathsf{w}^{-}=(w^{-}_{1},\ldots,w^{-}_{n})$ be two vectors such that
$w^{+}_{i}=w_{2i}$ and $w^{-}_{i}=w_{2i-1}$ for every $1\leq i\leq n$. We set
$r=c_{3}\delta^{-2}$, where $c_{3}>0$ is a sufficiently large constant. We
repeat the following for $\mu=O(\log n)$ times: For each $h\leq\mu$, we choose
a random sample $\mathcal{N}^{+}_{h}$ of $({\mathcal{R}},\mathsf{w}^{+})$ of
size $r$ and another random sample $\mathcal{N}^{-}_{h}$ of
$({\mathcal{R}},\mathsf{w}^{-})$ of size $r$. Let
$\mathcal{N}_{h}=\mathcal{N}^{+}_{h}\cup\mathcal{N}^{-}_{h}$. We define the
weight function $\bar{\omega}_{h}:\mathcal{N}_{h}\rightarrow\mathbb{R}$ as

$\bar{\omega}_{h}(R)=\begin{cases}\frac{\lVert{\mathsf{w}^{+}}\rVert_{1}}{r}&\text{if
}R\in\mathcal{N}^{+}_{h},\\\
-\frac{\lVert{\mathsf{w}^{-}}\rVert_{1}}{r}&\text{if
}R\in\mathcal{N}^{-}_{h}.\end{cases}$ (16)

We compute a deepest point $\tilde{p}_{h}$ with respect to
$(\mathcal{N}_{h},\bar{\omega}_{h})$ along with
$0pt(\tilde{p}_{h},\mathcal{N}_{h},\bar{\mathsf{\omega}}_{h})$ by calling
$\textsc{ DeepestPt}(\mathcal{N}_{h},\bar{\omega}_{h})$. After repeating $\mu$
times, we choose as $\tilde{p}$ the point $\tilde{p}_{\xi}$ with the median
$0pt(\tilde{p}_{\xi},\mathcal{N}_{\xi},\bar{\mathsf{\omega}}_{\xi})$ among
depths
$\\{0pt(\tilde{p}_{1},\mathcal{N}_{1},\bar{\mathsf{\omega}}_{1}),\ldots,0pt(\tilde{p}_{\mu},\mathcal{N}_{\mu},\bar{\mathsf{\omega}}_{\mu})\\}$,
where $\xi\in[1,\mu]$. Recall that $\mathsf{\omega}_{i}=w_{2i}-w_{2i-1}$.

######  Lemma 3.99.

$0pt(\tilde{p},{\mathcal{R}},\omega)\geq\max_{x\in\mathbb{R}^{d}}0pt(x,{\mathcal{R}},\omega)-\delta/12$
with probability at least $1-1/n^{O(1)}$.

######  Proof 3.103.

If we choose the constant $c_{3}$ sufficiently large, then both
$\mathcal{N}_{h}^{+}$ and $\mathcal{N}_{h}^{-}$ are
$\frac{\delta}{48}$-approximations with probability greater than $1/2$.
Therefore, for any point $x\in\mathbb{R}^{d}$,

$\left|{\frac{0pt(x,{\mathcal{R}},\mathsf{w}^{+})}{\lVert{\mathsf{w}^{+}}\rVert_{1}}-\frac{0pt(x,\mathcal{N}^{+}_{h})}{\left|{\mathcal{N}^{+}_{h}}\right|}}\right|,\left|{\frac{0pt(x,{\mathcal{R}},\mathsf{w}^{-})}{\lVert{\mathsf{w}^{-}}\rVert_{1}}-\frac{0pt(x,\mathcal{N}^{-}_{h})}{\left|{\mathcal{N}^{-}_{h}}\right|}}\right|\leq\frac{\delta}{48}.$
(17)

Using (17) and the fact that
$\lVert{\mathsf{w}^{+}}\rVert_{1},\lVert{\mathsf{w}^{-}}\rVert_{1}\leq 1$, we
obtain

$\displaystyle 0pt(x,{\mathcal{R}},\mathsf{\omega})$
$\displaystyle\\!=\\!0pt(x,{\mathcal{R}},\mathsf{w}^{+})\\!-\\!0pt(x,{\mathcal{R}},\mathsf{w}^{-})\leq\frac{\lVert{\mathsf{w}^{+}}\rVert_{1}}{r}0pt(x,\mathcal{N}_{h}^{+})\\!-\\!\frac{\lVert{\mathsf{w}^{-}}\rVert_{1}}{r}0pt(x,\mathcal{N}_{h}^{-})\\!+\\!2\frac{\delta}{48}$
$\displaystyle=0pt(x,\mathcal{N}_{h},\bar{\mathsf{\omega}}_{h})+\frac{\delta}{24}.$

Similarly, $0pt(x,{\mathcal{R}},\mathsf{\omega})\geq
0pt(x,\mathcal{N}_{h},\bar{\mathsf{\omega}}_{h})-\frac{\delta}{24}$. Next, we
define
$x^{*}=\operatorname*{arg\,max}_{x\in\mathbb{R}^{d}}0pt(x,{\mathcal{R}},\mathsf{\omega})$.
Hence, with probability greater than $1/2$,
$0pt(\tilde{p}_{h},{\mathcal{R}},\mathsf{\omega})\geq
0pt(x^{*},{\mathcal{R}},\mathsf{\omega})-\frac{\delta}{12}$.

Using the well known _median trick_ (an application of the median trick can be
found in [28]), we know that $\tilde{p}=\tilde{p}_{\xi}$ that has the median
depth satisfies $0pt(\tilde{p},{\mathcal{R}},\mathsf{\omega})\geq
0pt(x^{*},{\mathcal{R}},\mathsf{\omega})-\frac{\delta}{12}$, with probability
at least $1-1/n^{O(1)}$.

######  Lemma 3.115.

With probability at least $1-1/n^{O(1)}$, the IsFeasible decision procedure
either returns a discrete distribution $\tilde{\mathcal{D}}$ of size
$O(\delta^{-2}\log n)$ such that
$\mathrm{err}(\tilde{\mathcal{D}},\mathcal{Z})\leq\alpha+\delta/2$ or returns
No for $\alpha<\alpha^{*}$.

######  Proof 3.116.

Using the proofs of Lemma 2.45 and Lemma 2.57 (by slightly increasing the
constants $c_{1},c_{2}$) we get that with probability at least $1-1/n^{O(1)}$,
if the algorithm does not abort in the first $T$ iterations in the end it
finds $\tilde{\mathsf{x}}\in\mathbb{X}$ such that
$\mathsf{A}\tilde{\mathsf{x}}\geq\mathsf{b}-3\delta/12=\mathsf{b}-\delta/4$.
Using Lemma 3.49 and Lemma 2.57, we conclude the result.

######  Lemma 3.117.

The improved algorithm runs in time

$O((n+\delta^{-2}\log^{2}n+\delta^{-d}\log n)\delta^{-2}\log
n\log\delta^{-1}).$

######  Proof 3.118.

In each round, we spend $O(n)$ time to compute $\mathsf{u}$. For each $h$, we
construct two $\varepsilon$-approximations
$\mathcal{N}^{-}_{h},\mathcal{N}^{+}_{h}$ of size $O(\delta^{-2})$ by applying
weighted random sampling. Using a binary search tree constructed at the
beginning of each round of the MWU algorithm, we get each sample in $O(\log
n)$ time. Hence, we construct $\mathcal{N}_{h}$ in $O(\delta^{-2}\log n)$. We
spend $O((\delta^{-2})^{d/2})$ time to compute $\tilde{p}_{h}$ using [8].
Overall we spend $O((\delta^{-2}\log n+\delta^{-d})\log n)$ time to compute
the point $\tilde{p}$. Summing these bounds over all iterations of the binary
search and the MWU method, we have the desired bound.

The algorithm we proposed computes a discrete distribution
$\tilde{\mathcal{D}}$ of size $O(\delta^{-2}\log n)$. The size can be reduced
to $O(\delta^{-2})$ as follows. We first run the algorithm above with
$\delta\leftarrow\delta/2$. After obtaining $\tilde{\mathcal{D}}$, we repeat
the following procedure $O(\log n)$ times. In the $h$-th iteration, we get a
$\tilde{\mathcal{N}}_{h}$ of $O(\delta^{-2})$ weighted random samples from
$\tilde{\mathcal{D}}$. This is a $\delta/2$-approximation with probability at
least $1/2$. Let $\tilde{\mathcal{D}}_{h}$ be the distribution of size
$O(\delta^{-2})$ defined by $\tilde{\mathcal{N}}_{h}$. In the end, we return
the best $\delta/2$-distribution $\tilde{\mathcal{D}}_{h}$ with respect to
$\mathrm{err}(\tilde{\mathcal{D}}_{h},\mathcal{Z})$. With probability at least
$1-1/n^{O(1)}$, we find a distribution of size $O(\delta^{-2})$ and additive
error $\delta$. The running time of the additional steps is dominated by the
running time in Lemma 3.117.

######  Theorem 3.122.

Let $\mathcal{Z}=\\{z_{1},\ldots,z_{n}\\}$ be a set of training samples such
that $z_{i}=(R_{i},s_{i})$, where $R_{i}$ is an axis aligned rectangle in
$\mathbb{R}^{d}$ and $s_{i}\in[0,1]$ is its selectivity. Given a parameter
$\delta\in(0,1)$, a discrete distribution $\tilde{\mathcal{D}}$ of size
$O(\delta^{-2})$ can be computed in $O((n+\delta^{-2}\log^{2}n+\delta^{-d}\log
n)\delta^{-2}\log n\log\delta^{-1})$ time such that
$\mathrm{err}_{1}(\mathcal{Z},\tilde{\mathcal{D}})\leq\alpha^{*}_{1}(\mathcal{Z})+\delta$,
with probability at least $1-1/n^{O(1)}$.

Remark. As we will see in the next section, our main algorithm can be extended
to other settings. However, for axis-aligned rectangles, we can improve the
dependency on $d$ if we use a more sophisticated construction of
$\varepsilon$-approximations for rectangular ranges. In fact, using [40] to
construct the $\varepsilon$-approximation [10], we can get a distribution
$\tilde{D}$ with the same properties as in Theorem 3.122 in
$O((n+\delta^{-6}\log^{2}n+\delta^{-d/2})\delta^{-2}\log n\log\delta^{-1})$
time.

##  4 Extensions

###  4.1 Extending to other error functions

So far, we only focused on the $\ell_{1}$ empirical error. Our algorithm can
be extended to $\ell_{\infty}$ and $\ell_{2}$ empirical errors with the same
asymptotic complexity. In both cases, we run the same binary search as we had
for the $\ell_{1}$ error, and we call the
$\textsc{IsFeasible}(\mathcal{Z},\delta,\alpha)$.

$\boldsymbol{\ell_{\infty}}$ error. Following the same arguments as in Section
2.1, we can formulate the problem as a simpler $\mathsf{LP}$ than
($\mathsf{LP}$2.1). More specifically, by definition, we have to satisfy
$u_{i}\leq\alpha$ for $1\leq i\leq n$ instead of constraint (4). However, we
observe that the linear problem is then equivalent to ($\mathsf{LP}$2.1)
setting $u_{i}=\alpha$ for $1\leq i\leq n$. Without having a vector
$\mathsf{u}$, in each round $t$, the algorithm only computes the vector
$\mathsf{v}$ by computing $p$ as we had in Section 3. The result follows.

$\boldsymbol{\ell_{2}}$ error. The goal now is to find a distribution
$\mathcal{D}$ that minimizes $\mathrm{err}(\mathcal{D},\mathcal{Z})$. This is
equivalent to the feasibility problem ($\mathsf{LP}$2.1) replacing constraint
(4) with

$-\frac{1}{n}\sum_{i=1}^{n}u_{i}^{2}\geq-\alpha.$ (18)

Interestingly, the MWU method works even if the feasibility problem is on the
form $f(\mathsf{x})\geq 0$, where $f(\cdot)$ is concave. It is straightforward
to see that the new constraint (18) is concave. The rest of the constraints
remain the same as in ($\mathsf{LP}$2.1) so they are linear. Hence, we can use
the same technique to optimize the new feasibility problem. Still the goal is
to try and satisfy the expected constraint (8) by maximizing its LHS. In fact
the new LHS of (8) is

${\mathsf{w}}^{\top}\mathsf{A}\mathsf{x}=\sum_{i=1}^{n}-\frac{w_{0}}{n}u_{i}^{2}+(w_{2i}+w_{2i-1})u_{i}+\sum_{j=1}^{m}\psi_{j}v_{j}$
(19)

The variables $v_{i}$ are set by efficiently computing $p$ as shown in Section
3. So we only focus on setting the variables $u_{i}$. Recall that our goal is
to maximize the LHS in order to check if the expected constraint is satisfied.
By simple algebraic calculations it is straightforward to see that the
function $g(u_{i})=-\frac{w_{0}}{n}u_{i}^{2}+(w_{2i}+w_{2i-1})u_{i}$ under the
constraint $u_{i}\in[0,1]$ is maximized for

$u_{i}=\min\left\\{\frac{n(w_{2i}+w_{2i-1})}{2w_{0}},1\right\\}.$ (20)

After computing $\mathsf{w}$, we can find $\mathsf{u}$ in $O(n)$ time. Hence,
using (20) instead of (13) we can set $\mathsf{u}$ that maximizes the expected
constraint. All the other steps of the algorithm remain the same. Following
the improved algorithm along with the proofs of Lemmas 2.45, 2.57, if
$\alpha>\alpha^{*}_{2}(\mathcal{Z})$, with high probability, we get a
distribution $\tilde{\mathcal{D}}$ of size $O(\delta^{-2})$ in near linear
time such that
$\mathrm{err}_{2}(\tilde{\mathcal{D}},\mathcal{Z})\leq\alpha+\delta/2$.

######  Theorem 4.17.

Let $\mathcal{Z}=\\{z_{1},\ldots,z_{n}\\}$ be a set of training samples such
that $z_{i}=(R_{i},s_{i})$, where $R_{i}$ is an axis-aligned rectangle in
$\mathbb{R}^{d}$ and $s_{i}\in[0,1]$ is its selectivity. Given the parameters
$\delta\in(0,1)$ and $p\in\\{1,2,\infty\\}$, a discrete distribution
$\tilde{\mathcal{D}}$ of size $O(\delta^{-2})$ can be computed in
$O((n+\delta^{-2}\log^{2}n+\delta^{-d}\log n)\delta^{-2}\log
n\log\delta^{-1})$ time such that
$\mathrm{err}_{p}(\mathcal{Z},\tilde{\mathcal{D}})\leq\alpha^{*}_{p}(\mathcal{Z})+\delta$
with probability at least $1-1/n^{O(1)}$.

###  4.2 Extending to other types of ranges

Besides rectangles, our algorithm can be extended to more general ranges such
as balls and halfspaces in $\mathbb{R}^{d}$. A _semi-algebraic_ set in
$\mathbb{R}^{d}$ is a set defined by Boolean functions over polynomial
inequalities, such as a unit semi-disc $\\{(x^{2}+y^{2}\leq 1)\cap(x\geq
0)\\}$, or an annulus $\\{(x^{2}+y^{2}\leq 4)\cap(x^{2}+y^{2}\geq 1)\\}$. Most
familiar geometric shapes such as balls, halfspaces, simplices, ellipsoids,
are semi-algebraic sets. The _complexity_ of a semi-algebraic set is the sum
of the number of polynomial inequalities and their maximum degree. See [5] for
a discussion on semi-algebraic sets. Our results extend to semi-algebraic
ranges of constant complexity. Let
$\mathcal{Z}=\\{(\Gamma_{1},s_{1}),\ldots,(\Gamma_{n},s_{n})\\}$ be a training
set where each $\Gamma_{i}$ is a semi-algebraic set of constant complexity.
Let $\Gamma=\\{\Gamma_{1},\ldots,\Gamma_{n}\\}$. It is known that
$\mathop{\mathrm{\EuScript{A}}}(\Gamma)$ has $n^{O(d)}$ complexity, that for
any weight function $\omega\\!:\Gamma\rightarrow[0,1]$, the deepest point can
be computed in $O(n^{d})$ time, and that a random sample of size
$O(\delta^{-2}\log\phi^{-1})$ is a $\delta$-approximation with probability at
least $1-\phi$, [1, 2]. With these primitives at our disposal, the algorithm
in Section 3 can be extended to this setting. Omitting all the details we
obtain the following.

######  Theorem 4.18.

Let $\mathcal{Z}=\\{z_{1},\ldots,z_{n}\\}$ be a set of training samples such
that $z_{i}=(\Gamma_{i},s_{i})$, where $\Gamma_{i}$ is a semi-algebraic set of
constant complexity and $s_{i}\in[0,1]$ is its selectivity. Given the
parameters $\delta\in(0,1)$ and $p\in\\{1,2,\infty\\}$, a discrete
distribution $\tilde{\mathcal{D}}$ of size $O(\delta^{-2})$ can be computed in
$O((n+\delta^{-2}\log^{2}n+\delta^{-2d}\log n)\delta^{-2}\log
n\log\delta^{-1})$ time such that
$\mathrm{err}_{p}(\mathcal{Z},\tilde{\mathcal{D}})\leq\alpha^{*}_{p}(\mathcal{Z})+\delta$
with probability at least $1-1/n^{O(1)}$.

##  5 Hardness

The proofs in this section can be found in Appendix A.

###  5.1 NP-Completeness

Let Selectivity be the decision problem of constructing a distribution with
small size and minimum error. More specifically, let
$\mathcal{Z}=\\{(R_{1},s_{1}),...,(R_{n},s_{n})\\}$ be the input training set
consisting of $n$ rectangles in $\mathbb{R}^{d}$. Let $k$ be a positive
natural number and $\varepsilon\in[0,1]$ be an error parameter. The
Selectivity problem asks if there exists a distribution
$\mathcal{D}\in\mathbb{D}_{k}$ such that
$\mathrm{err}_{p}(\mathcal{D},\mathcal{Z})\leq\varepsilon$. We prove the
following theorem.

######  Theorem 5.1.

The Selectivity problem is $\mathsf{NP}$-Complete, even for $d=2$.

The $\mathsf{NP}$-hardness proof is based on a gadget used by [36] to prove
the NP-hardness of the _Square Cover_ problem: given a set $\mathcal{R}$ of
$n$ squares, and a parameter $k$, decides if there are $k$ points
$S\in\mathbb{R}^{2}$ such that $R\cap S\neq\emptyset$ for each
$R\in\mathcal{R}$. We prove Theorem 5.1 by reducing _3_ -SAT to the
Selectivity problem in $\mathbb{R}^{2}$. Let $(X,C)$ be the _3_ -SAT formula
consisting of variables $x_{1},...,x_{n}$ and clauses $C_{1},...,C_{m}$. We
construct a set of weighted axis-aligned rectangles $\mathcal{Z}$ and a number
$k$ such that $(X,C)$ is satisfiable if and only if there exists a discrete
distribution $\mathcal{D}$ of size $k$ such that
$\mathrm{err}_{p}(\mathcal{D},\mathcal{Z})=0$.

In the previous reduction, we created a training set $\mathcal{Z}$ such that
there exists a $\mathcal{D}\in\mathbb{D}_{k}$ with
$\mathrm{err}_{p}(\mathcal{D},\mathcal{Z})=0$ if and only if the formula is
satisfiable. This implies something stronger. Given $\mathcal{Z}$ and $k$, let
$\alpha^{*}_{p,k}=\min_{\mathcal{D}\in\mathbb{D}_{k}}\mathrm{err}_{p}({\mathcal{D},\mathcal{Z}})$.

######  Corollary 5.2.

Let $f:\mathbb{N}\xrightarrow{}\mathbb{N}$ be a function. Given a training set
$\mathcal{Z}$ and an input parameter $k\in\mathbb{N}$, no polynomial-time
algorithm can find $\mathcal{D}\in\mathbb{D}_{k}$ such that
$\mathrm{err}_{p}(\mathcal{D},\mathcal{Z})\leq
f(n)\alpha^{*}_{p,k}(\mathcal{Z})$, unless $P=NP$.

###  5.2 Conditional lower bounds

A natural question that arises now is, given $k$, whether we can find a
discrete distribution of size at most $g(n)k$ such that the error is at most
$f(n)\alpha^{*}_{p,k}$, where $f(n),g(n)$ are non-negative functions. As it
turns out, if we are interested in near-linear algorithms, then it is
unlikely.  The same technique shows that removing the exponential dependency
on $d$ from additive approximations is unlikely.

Formally, we define the Selectivity+ problem. We are given a training set
$\mathcal{Z}$ of $n$ rectangles in $\mathbb{R}^{d}$ along with their
associated selectivities and a parameter $k$. Selectivity+ asks to find
$\mathcal{D}\in\mathbb{D}$ such that $\left|{\mathcal{D}}\right|\leq{g(n)k}$
and $\mathrm{err}_{p}(\mathcal{D},\mathcal{Z})\leq f(n)\alpha^{*}_{p,k}$,
where $g:\mathbb{N}\xrightarrow{}\mathbb{N}$ and
$f(n):\mathbb{N}\xrightarrow{}\mathbb{N}$ are any functions that satisfy
$f(n)\geq 1$, $g(n)\geq 1$, and $g(n)\cdot k=O(n)$. We prove the following
theorem.

######  Theorem 5.3.

The Selectivity+ problem cannot be solved in $h(d)n^{O(1)}$ time, where $h$ is
any computable function $h:\mathbb{N}\rightarrow\mathbb{N}$, under the
$\mathsf{FPT}\neq W[1]$ conjecture.

Similarly to the Selectivity+ problem, we define the Approx-Selectivity
problem. Here, we are given a training set $\mathcal{Z}$ of $n$ rectangles in
$\mathbb{R}^{d}$ along with their associated selectivities. Let $\delta>0$ be
a parameter. Approx-Selectivity asks to find a $\mathcal{D}\in\mathbb{D}$ such
that $\left|{\mathcal{D}}\right|\leq\frac{1}{\delta^{3}}$ and
$\mathrm{err}_{p}(\mathcal{D},\mathcal{Z})\leq f(n)\alpha^{*}_{p,1}+\delta$,
where $f(n):\mathbb{N}\xrightarrow{}\mathbb{N}$ is any function that satisfies
$f(n)\geq 1$.

The requirements for Approx-Selectivity are considerably weak. First, we are
allowed to use more points than our algorithm i.e. $\frac{1}{\delta^{3}}$
points. Second, we only need to compete with a multiplicative factor of the
best solution using just one point i.e. $f(n)\alpha^{*}_{p,1}$. It turns out
that for small $\delta$, the conditions of the Approx-Selectivty become the
same as Selectivity+ and hence the proof technique for Theorem 5.3 also proves
the following:

######  Theorem 5.4.

The Approx-Selectivity problem cannot be solved in
$h(d)\big{(}n^{O(1)+\delta^{-O(1)}}+n^{O(1)}\delta^{-O(1)}\big{)}$ time, where
$h$ is any computable function $h:\mathbb{N}\rightarrow\mathbb{N}$, under the
$\mathsf{FPT}\neq W[1]$ conjecture.

Both theorems are based on the reductions from the _coverage problem_. For the
coverage problem, we are given a set ${\mathcal{R}}$ of $n-1$ rectangles in
$\mathbb{R}^{d}$ and a box $B$. The coverage problem asks if the union of
rectangles in ${\mathcal{R}}$ covers $B$ completely. In [7], they prove that
the coverage problem is $W[1]$-hard with respect to dimension $d$, showing
that the existence of a $d$-clique in a graph with $\sqrt{n}$ vertices can be
reduced to the coverage problem with $O(n)$ boxes in $\mathbb{R}^{d}$. Thus,
the time complexity of the $d$-clique problem is intimately related to our
problem. If fast matrix multiplication is allowed, the best known algorithm
for the $d$-clique problem requires $\omega(n^{d/3})$ time [38]. Due to
inefficiencies of fast matrix multiplication, there is a lot of interest in
solving the clique problem using combinatorial algorithms (i.e. without fast
matrix multiplication). However, the best current combinatorial algorithm for
the $d$-clique problem in general graphs requires
$\Omega(n^{d}/\mathop{\mathrm{polylog}}(n))$ running time. These facts lead us
to the following remark.

Remark. A $o(n^{d/2-\eta})$ time combinatorial algorithm for the Selectivity+
problem or a $o(n+\delta^{-d/2+\eta})$ time combinatorial algorithm for the
the Approx-Selectivity problem, for any $\eta>0$, is unlikely because such an
algorithm would lead to a $o(n^{d-\eta})$ combinatorial algorithm for
$d$-clique, solving a major open problem in graph theory.

##  6 Related Work

Selectivity Estimation. Selectivity estimation techniques can be broadly
classified into three regimes: query-driven, data-driven, and hybrid. Most
literature focuses on orthogonal range queries.

Query-driven methods: These methods derive selectivity estimates based on
previous queries and their results. They do not require access to the
underlying data distribution. Methods falling under this category include DQM
[23] and the query-driven histogram techniques such as STHoles [6], Isomer
[44], and QuickSel [39]. They construct models or histograms using results
from previous queries and apply these models to estimate selectivity for new
queries.

Data-driven methods: These methods, on the other hand, derive selectivity
estimates from the underlying data distribution. They sample data and build
statistical models that capture the data distribution, which are then used for
selectivity estimation. There is long history along this direction, but some
recent examples in this category include Naru [48], DQM-D [34], and
DeepDB[25].

Hybrid methods: These methods take into account both the query workload and
the underlying data distribution. They not only model the data distribution
but also incorporate query feedback to refine the model over time. Examples of
such methods include MSCN [27] and LW [14], which utilize both data and query
features in a regression-based framework for selectivity estimation. See [46]
for a detailed literature review.

Our method is query-driven, but is unique because none of query-driven and
data-driven models above offered theoretical guarantees on the learnability of
the functions or their learning procedures.

Multiplicative-Weights-Update (MWU) method. The MWU method has been
independently rediscovered multiple times and has found applications in
several areas including machine learning [16], game theory [17, 19], online
algorithms [15], computational geometry [11], etc. In the context of
optimization problems, there is a rich body of work on using MWU and related
techniques to efficiently solve special classes of LPs and SDPs [29, 41, 49,
3]. The technique we use in this paper is an adaption of the one used by [41]
to solve packing and covering LPs. See also [4] for a detailed overview. The
MWU method has also been used to implicitly solve linear programs. A classical
example is the multicommodity flow problem where the describing the LP
explicitly requires exponential number constraints [18]. Furthermore, there
has been a lot of work related to implicitly solving special classes of LPs in
computational geometry or combinatorial optimization using the MWU method [9,
11, 12], the primal dual method [47], or the ellipsoid method [21, 20].

Despite the geometric nature of our problem, to the best of our knowledge, all
previous (geometric) techniques that implicitly solve an $\mathsf{LP}$ do not
extend to our problem. In particular, in [11] the authors study various
geometric packing and covering problems, such as the weighted set cover of
points by disks, and the maximum weight independent set of disks, using the
MWU method. The main difference from our setting is that for all problems they
study, the matrix $\mathsf{A}$ and the vector $\mathsf{b}$ are non-negative.
One of the main challenges in our setting is that we have to deal with both
positive and negative values in $\mathsf{A}$ and $\mathsf{b}$. It is not clear
how their algorithms can be extended to our setting. For example, for the
maximum weight independent set problem, they also describe an efficient
algorithm to compute an approximately deepest point. However, their algorithm
works in $2$ dimensions while all ranges have positive weights. In our
setting, we have ranges in any constant dimension $d$ with both positive and
negative weights.

##  7 Conclusion and future work

In this work, we studied the problem of finding the data distribution to fit a
query training set consisting of axis-aligned rectangles (representing
orthogonal range selectivity queries) with the smallest error. While the
problem has been studied in the past, only an expensive $\Omega(n^{d})$
algorithm was known for constructing a distribution of size $O(n^{d})$. We
showed that the decision problem is $\mathsf{NP}$-complete even for $d=2$.
Based on a standard complexity conjecture, we also gave conditional lower
bounds showing that the exponential dependency on $d$ is inevitable for
additive or relative approximations.  On the positive side, for the $\ell_{1}$
empirical error, we gave a
$O((n+\delta^{-d})\delta^{-2}\mathop{\mathrm{polylog}}n)$ time algorithm that
returns a data distribution of size $O(\delta^{-2})$ with additive error
$\delta$. Furthermore, we showed that our algorithm for $\ell_{1}$ error can
be extended to $\ell_{2}$ and $\ell_{\infty}$, as well as any type of ranges
as long as they are algebraic sets of constant complexity.  In view of our
hardness results, significant improvements to our upper bounds are unlikely.

There are some interesting directions following from this work.  What
properties should the data and query distribution satisfy so that the running
time is polynomial in $d$ as well? In addition to selectivity queries, another
interesting line of work is to study the construction of distributions for
other types of database queries such as aggregation and joins.

## References

  * [1] P. K. Agarwal, B. Aronov, E. Ezra, and J. Zahl.  Efficient algorithm for generalized polynomial partitioning and its applications.  SIAM Journal on Computing, 50(2):760–787, 2021.
  * [2] P. K. Agarwal and M. Sharir.  Arrangements and their applications.  In Handbook of computational geometry, pages 49–119. Elsevier, 2000.
  * [3] S. Arora, E. Hazan, and S. Kale.  Fast algorithms for approximate semidefinite programming using the multiplicative weights update method.  In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05), pages 339–348. IEEE, 2005.
  * [4] S. Arora, E. Hazan, and S. Kale.  The multiplicative weights update method: a meta-algorithm and applications.  Theory of computing, 8(1):121–164, 2012.
  * [5] S. Basu, R. Pollack, and M. F. Roy.  Algorithms in real algebraic geometry.  2nd ed., Springer-Verlag, 2000.
  * [6] N. Bruno, S. Chaudhuri, and L. Gravano.  Stholes: A multidimensional workload-aware histogram.  In S. Mehrotra and T. K. Sellis, editors, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, Santa Barbara, CA, USA, May 21-24, 2001, pages 211–222. ACM, 2001.
  * [7] T. M. Chan.  A (slightly) faster algorithm for klee’s measure problem.  In Proceedings of the twenty-fourth annual symposium on Computational geometry, pages 94–100, 2008.
  * [8] T. M. Chan.  Klee’s measure problem made easy.  In 2013 IEEE 54th annual symposium on foundations of computer science, pages 410–419. IEEE, 2013.
  * [9] T. M. Chan and Q. He.  Faster approximation algorithms for geometric set cover.  In 36th International Symposium on Computational Geometry (SoCG 2020), 2020.
  * [10] B. Chazelle.  The discrepancy method: randomness and complexity.  Cambridge University Press, 2000.
  * [11] C. Chekuri, S. Har-Peled, and K. Quanrud.  Fast lp-based approximations for geometric packing and covering problems.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1019–1038. SIAM, 2020.
  * [12] K. L. Clarkson and K. Varadarajan.  Improved approximation algorithms for geometric set cover.  In Proceedings of the twenty-first annual symposium on Computational geometry, pages 135–141, 2005.
  * [13] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh.  Parameterized algorithms, volume 5.  Springer, 2015.
  * [14] A. Dutt, C. Wang, A. Nazi, S. Kandula, V. R. Narasayya, and S. Chaudhuri.  Selectivity estimation for range predicates using lightweight models.  Proc. VLDB Endow., 12(9):1044–1057, 2019.
  * [15] D. P. Foster and R. Vohra.  Regret in the on-line decision problem.  Games and Economic Behavior, 29(1-2):7–35, 1999.
  * [16] Y. Freund and R. E. Schapire.  A decision-theoretic generalization of on-line learning and an application to boosting.  Journal of computer and system sciences, 55(1):119–139, 1997.
  * [17] Y. Freund and R. E. Schapire.  Adaptive game playing using multiplicative weights.  Games and Economic Behavior, 29(1-2):79–103, 1999.
  * [18] N. Garg and J. Könemann.  Faster and simpler algorithms for multicommodity flow and other fractional packing problems.  SIAM Journal on Computing, 37(2):630–652, 2007.
  * [19] M. D. Grigoriadis and L. G. Khachiyan.  A sublinear-time randomized approximation algorithm for matrix games.  Operations Research Letters, 18(2):53–58, 1995.
  * [20] M. Grötschel, L. Lovász, and A. Schrijver.  The ellipsoid method and its consequences in combinatorial optimization.  Combinatorica, 1:169–197, 1981.
  * [21] M. Grötschel, L. Lovász, and A. Schrijver.  Geometric algorithms and combinatorial optimization, volume 2.  Springer Science & Business Media, 2012.
  * [22] S. Har-Peled.  Geometric approximation algorithms.  Number 173. American Mathematical Soc., 2011.
  * [23] S. Hasan, S. Thirumuruganathan, J. Augustine, N. Koudas, and G. Das.  Deep learning models for selectivity estimation of multi-attribute queries.  In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pages 1035–1050, 2020.
  * [24] D. Haussler.  Decision theoretic generalizations of the pac model for neural net and other learning applications.  Information and computation, 100(1):78–150, 1992.
  * [25] B. Hilprecht, A. Schmidt, M. Kulessa, A. Molina, K. Kersting, and C. Binnig.  Deepdb: learn from data, not from queries!  Proceedings of the VLDB Endowment, 13(7):992–1005, 2020.
  * [26] X. Hu, Y. Liu, H. Xiu, P. K. Agarwal, D. Panigrahi, S. Roy, and J. Yang.  Selectivity functions of range queries are learnable.  In SIGMOD ’22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022, pages 959–972. ACM, 2022.
  * [27] A. Kipf, T. Kipf, B. Radke, V. Leis, P. A. Boncz, and A. Kemper.  Learned cardinalities: Estimating correlated joins with deep learning.  In 9th Biennial Conference on Innovative Data Systems Research, CIDR 2019, Asilomar, CA, USA, January 13-16, 2019, Online Proceedings. www.cidrdb.org, 2019.
  * [28] A. Kogler and P. Traxler.  Parallel and robust empirical risk minimization via the median trick.  In Mathematical Aspects of Computer and Information Sciences: 7th International Conference, MACIS 2017, Vienna, Austria, November 15-17, 2017, Proceedings, pages 378–391. Springer, 2017.
  * [29] C. Koufogiannakis and N. E. Young.  Beating simplex for fractional packing and covering linear programs.  In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pages 494–504. IEEE Computer Society, 2007.
  * [30] R. J. Lipton, J. F. Naughton, and D. A. Schneider.  Practical selectivity estimation through adaptive sampling.  In Proceedings of the 1990 ACM SIGMOD international conference on Management of data, pages 1–11, 1990.
  * [31] R. Marcus, P. Negi, H. Mao, N. Tatbul, M. Alizadeh, and T. Kraska.  Bao: Making learned query optimization practical.  SIGMOD Rec., 51(1):6–13, 2022.
  * [32] R. Marcus, P. Negi, H. Mao, C. Zhang, M. Alizadeh, T. Kraska, O. Papaemmanouil, and N. Tatbul23.  Neo: A learned query optimizer.  Proceedings of the VLDB Endowment, 12(11).
  * [33] R. Marcus and O. Papaemmanouil.  Deep reinforcement learning for join order enumeration.  In Proceedings of the First International Workshop on Exploiting Artificial Intelligence Techniques for Data Management, pages 1–4, 2018.
  * [34] V. Markl, P. J. Haas, M. Kutsch, N. Megiddo, U. Srivastava, and T. M. Tran.  Consistent selectivity estimation via maximum entropy.  The VLDB journal, 16:55–76, 2007.
  * [35] Y. Matias, J. S. Vitter, and M. Wang.  Wavelet-based histograms for selectivity estimation.  In Proceedings of the 1998 ACM SIGMOD international conference on Management of data, pages 448–459, 1998.
  * [36] N. Megiddo and K. J. Supowit.  On the complexity of some common geometric location problems.  SIAM J. Comput., 13(1):182–196, 1984.
  * [37] P. Negi, R. Marcus, H. Mao, N. Tatbul, T. Kraska, and M. Alizadeh.  Cost-guided cardinality estimation: Focus where it matters.  In 2020 IEEE 36th International Conference on Data Engineering Workshops (ICDEW), pages 154–157. IEEE, 2020.
  * [38] J. Nešetřil and S. Poljak.  On the complexity of the subgraph problem.  Commentationes Mathematicae Universitatis Carolinae, 26(2):415–419, 1985.
  * [39] Y. Park, S. Zhong, and B. Mozafari.  Quicksel: Quick selectivity learning with mixture models.  In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pages 1017–1033, 2020.
  * [40] J. M. Phillips.  Algorithms for epsilon-approximations of terrains.  In Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games, volume 5125 of Lecture Notes in Computer Science, pages 447–458. Springer, 2008.
  * [41] S. A. Plotkin, D. B. Shmoys, and É. Tardos.  Fast approximation algorithms for fractional packing and covering problems.  Mathematics of Operations Research, 20(2):257–301, 1995.
  * [42] V. Poosala, P. J. Haas, Y. E. Ioannidis, and E. J. Shekita.  Improved histograms for selectivity estimation of range predicates.  ACM Sigmod Record, 25(2):294–305, 1996.
  * [43] V. Poosala and Y. E. Ioannidis.  Selectivity estimation without the attribute value independence assumption.  In VLDB, volume 97, pages 486–495, 1997.
  * [44] U. Srivastava, P. J. Haas, V. Markl, M. Kutsch, and T. M. Tran.  ISOMER: consistent histogram construction using query feedback.  In L. Liu, A. Reuter, K. Whang, and J. Zhang, editors, Proceedings of the 22nd International Conference on Data Engineering, ICDE 2006, 3-8 April 2006, Atlanta, GA, USA, page 39. IEEE Computer Society, 2006.
  * [45] M. Stocker, A. Seaborne, A. Bernstein, C. Kiefer, and D. Reynolds.  Sparql basic graph pattern optimization using selectivity estimation.  In Proceedings of the 17th international conference on World Wide Web, pages 595–604, 2008.
  * [46] X. Wang, C. Qu, W. Wu, J. Wang, and Q. Zhou.  Are we ready for learned cardinality estimation?  Proceedings of the VLDB Endowment, 14(9):1640–1654, 2021.
  * [47] D. P. Williamson.  The primal-dual method for approximation algorithms.  Mathematical Programming, 91:447–478, 2002.
  * [48] Z. Yang, E. Liang, A. Kamsetty, C. Wu, Y. Duan, X. Chen, P. Abbeel, J. M. Hellerstein, S. Krishnan, and I. Stoica.  Deep unsupervised cardinality estimation.  Proceedings of the VLDB Endowment, 13(3).
  * [49] N. E. Young.  Sequential and parallel algorithms for mixed packing and covering.  In Proceedings 42nd IEEE symposium on foundations of computer science, pages 538–546. IEEE, 2001.

##  Appendix A Missing proofs from Section 5

###  A.1 Proof of Theorem 5.1

It is straightforward to show that $\textsc{Selectivity}\in\mathsf{NP}$. Given
a distribution $\mathcal{D}$ (set of weighted points in $\mathbb{R}^{d}$) of
polynomial size in $n$ and the training set $\mathcal{Z}$ we evaluate (1) in
$O(n|\mathcal{D}|)$.

#### Placement of rectangles

Given an instance of the $3$-SAT problem we construct an instance of the
Selectivity problem. The placement of rectangles (which are squares in this
case) in $\mathcal{Z}$ is exactly the same as the placement of squares in
[36]. We show the high level of construction for completeness.

Each variable $x_{i}$ will be represented by a chain of squares
$\\{R_{1}^{i},...,R_{2K_{i}}^{i}\\}$, for polynomially bounded $K_{i}$, such
that two rectangles intersect if and only if they are adjacent. See Figure 3.
As we see later, sometimes, the intersection of two rectangles in a chain
includes more than an edge. The intuition for placing such squares is the
following. Let $I$ be a set of points of size $K_{i}$ that covers every
rectangle in the chain. Observe that by construction, either every point in
$I$ belongs to $R^{i}_{k}\cap R^{i}_{k+1}$ where $k=1,3,...,2K_{i}-1$ or all
points belong to $R^{i}_{k}\cap R^{i}_{k+1\,(mod\,2K_{i})}$ where
$k=2,4,..,2K_{i}$. We associate the former collection of sets with a true
assignment and call it an _odd-cover_ and the latter collection of sets with a
false assignment and call it an _even-cover_.

Each clause $C_{j}$ will be represented by a rectangle $S_{j}$ such that
chains corresponding to variables in that clause will intersect that
rectangle. If clause $C_{j}$ contains the variable $x_{i}$ without negation
then $S_{j}$ intersects a pair $R^{i}_{k},R^{i}_{k+1}$ where $k$ is odd. If it
contains the variable $x_{i}$ with negation then $S_{j}$ intersects a pair
$R^{i}_{k},R^{i}_{k+1}$ where $k$ is even. Please check Figure 5 for as an
example for the clause $C_{5}=(\neg x_{1}\lor x_{2}\lor\neg x_{3})$ (please
ignore the red points for now).

In the overall schematic, chains corresponding to different variables may
intersect. We call these regions junctions. At the junctions, the two chains
will share a rectangle in a way that will allow them to propagate their values
independently. The four corners of the common-rectangle represent the four
combination of values of the variables. See Figure 4.

The overall construction looks like Figure 2. We omit the details of the above
construction, see [36] for a thorough treatment. For us, it is sufficient that
the construction of the rectangles is done in polynomial time.

#### Assigning Selectivities

Let $N_{c}$ denote the number of junctions. We will set
$k=\sum_{i=1}^{n}K_{i}-N_{c}$ and assign each rectangle a weight of
$\frac{1}{k}$.

######  Lemma A.1.

If $(X,C)$ is satisfiable then there exists a $\mathcal{D}\in\mathbb{D}_{k}$
such that $\mathrm{err}_{p}(\mathcal{D},\mathcal{Z})=0$.

######  Proof A.2.

Suppose the formula is true and let $\phi$ be its assignment. For each
$x_{i}$, if it is assigned true (resp. false) pick $K_{i}$ points, one point
from each set in its odd-cover (resp. even-cover). At the junctions, place the
points appropriately so that they are consistent with both chains. For
example, consider the junction of two variables $x_{1},x_{2}$ in Figure 4. We
only place one point in the middle square. If both $x_{1},x_{2}$ are true then
we add point $a_{1}$ in $\mathcal{D}$. If $x_{1}$ is true and $x_{2}$ false we
add point $a_{3}$ in $\mathcal{D}$. If $x_{1}$ is false and $x_{2}$ true we
add point $a_{2}$ in $\mathcal{D}$. Otherwise, if both $x_{1},x_{2}$ are false
we add point $a_{4}$ in $\mathcal{D}$. The above steps uses all $k$ points and
places exactly one point in each chain-rectangle (including junctions). Set
the weight of each point to be $\frac{1}{k}$. Thus, the error generated by
each chain-rectangle or junction is $0$. Now we consider the clause
rectangles. Since the formula is satisfiable at least one variable in each
clause is set to true. Consider a clause $C_{j}$. Suppose variable $x_{i}$ is
a part of $C_{j}$ and without loss of generality, $x_{i}$ does not have
negation in $C_{i}$. Moreover, assume that $x_{i}$ is true in $\phi$. This
implies a point was picked from the odd-cover of $x_{i}$. We make sure that
this point also lies inside the rectangle corresponding to clause $C_{j}$. By
construction of the clause gadget this is always possible. We also make sure
that any other variable $x_{h}$ that also satisfies $C_{j}$ does not include
any points from its odd-cover touches $C_{i}$. Again by construction, this is
always possible. For example consider the clause $C_{5}=\neg x_{1}\lor
x_{2}\lor\neg x_{3}$ at Figure 5. Assume that $x_{1}$ is false, $x_{2}$ is
true, and $x_{3}$ is true in assignment $\phi$. Since variable $x_{1}$ is
false it contain a point in the intersection of $R_{16}^{1}\cap R_{16}^{1}$
(left gray area in Figure 5). Variable $x_{1}$ makes $C_{5}$ true so we place
point $a_{5}$ in $\mathcal{D}$ which is in the intersection of $R_{16}^{1}\cap
R_{16}^{1}\cap S_{5}$. $x_{2}$ is true so it should contain a point in the
intersection of $R_{21}^{2}\cap R_{22}^{2}$ (right gray area in Figure 5).
$x_{2}$ also makes $C_{5}$ true, however we have already placed a point in
$S_{5}$. Hence, we add point $a_{8}$ in $\mathcal{D}$, instead of the point
$a_{7}$. Finally, $x_{3}$ is true so it contains the points $a_{1},a_{2}$ in
$\mathcal{D}$ and they do not lie in $S_{5}$. If $x_{3}$ was false then we
would add point $a_{3}$ in $\mathcal{D}$ instead of point $a_{4}$ because
$S_{5}$ already contains a point (the point $a_{5}$ from variable $x_{1}$).
For any possible assignment, we can guarantee that if $C_{5}$ is true then
only one among points $a_{4},a_{5},a_{7}$ is added in $\mathcal{D}$, while if
$C_{5}$ is false then no points among $a_{4},a_{5},a_{7}$ is added in
$\mathcal{D}$. Hence, now each rectangle has exactly one point with weight
$\frac{1}{k}$. Therefore the error is $0$.

######  Lemma A.3.

If there exists a $\mathcal{D}\in\mathbb{D}_{k}$ such that
$\mathrm{err}_{p}(\mathcal{D},\mathcal{Z})=0$ then $(X,C)$ is satisfiable.

######  Proof A.4.

The distribution $\mathcal{D}$ has error $0$, so it must place at least one
point in every rectangle. Since it takes $k=\sum_{i=1}^{m}K_{i}-N_{c}$ just to
hit every rectangle in a variable-chain, $\mathcal{D}$ must place exactly one
point in each rectangle and assign it a weight of $\frac{1}{k}$. From the
analysis of [36], we know that such a placement of points must correspond to
an odd-cover or even-cover for every variable-chain. This defines an
assignment for every variable. Furthermore, since $\mathcal{D}$ places a point
in each clause, for every clause $C_{i}$ at least some variable in that clause
must be satisfied. Hence, $(X,C)$ is satisfiable.

Figure 2: Schematic with two clauses and four variables Figure 3: Variable
Chain Figure 4: Junction of variables $x_{1},x_{2}$. Figure 5: Clause
$C_{5}=(\neg x_{1}\lor x_{2}\lor\neg x_{3})$. The gray areas are the
intersections $R_{16}^{1}\cap R_{17}^{1}$, $R_{21}^{2}\cap R_{22}^{2}$.

###  A.2 Proof of Theorem 5.3

In the coverage problem, we are given a set ${\mathcal{R}}$ of $n-1$
rectangles in $\mathbb{R}^{d}$ and a box $B$. The coverage problem asks if the
union of rectangles in ${\mathcal{R}}$ covers $B$ completely. The coverage
problem is known to be $W[1]$-Hard. Under the $\mathsf{FPT}\neq W[1]$
conjecture, this implies that there cannot be an algorithm for coverage with
running time $h(d)n^{O(1)}$, where $h:\mathbb{N}\rightarrow\mathbb{N}$.

Let $\mathcal{A}$ be an algorithm for Selectivity+. We are going to prove by
contradiction that $\mathcal{A}$ cannot run in $h(d)n^{O(1)}$ time, under the
$\mathsf{FPT}\neq W[1]$ conjecture. Let assume that $\mathcal{A}$ runs in
$h(d)n^{O(1)}$ time.

For each rectangle $R_{i}\in{\mathcal{R}}$, we construct $z_{i}=(R_{i},0)$,
i.e., rectangle $R_{i}$ with selectivity $0$. Finally, we add $z_{n}=(B,1)$.
We set $k=1$. The running time to construct the instance of the Selectivity+
problem is $O(d\cdot n)$. We then run $\mathcal{A}$ on this instance.

We first consider the case when the input is a No instance of the coverage
problem. This implies that there exists a point $q\in\mathbb{R}^{d}$ such that
$q\cap B\neq\emptyset$ and
$q\bigcap(\bigcup_{R_{i}\in{\mathcal{R}}}R_{i})=\emptyset$. Consider the
distribution $\mathcal{D}=\\{(q,1)\\}$. Notice that
$\mathrm{err}_{p}(\mathcal{D},\mathcal{Z})=0=\alpha^{*}_{p,1}=\alpha^{*}_{p,k}=f(n)\alpha^{*}_{p,k}$
because $q$ lies only inside $B$, where $B$ has selectivity $1$ and all other
rectangles $R_{i}$ have selectivity $0$. By definition of Selectivity+,
$\mathcal{A}$ in this instance must return a distribution $\mathcal{D}$ such
that $\mathrm{err}_{p}(\mathcal{D},\mathcal{Z})=0$.

In the Yes instance of the coverage problem, if $q\in B$ then
$q\in\bigcup_{R_{i}\in{\mathcal{R}}}R_{i}$. Hence, if we add any point $q\in
B$ in distribution $\mathcal{D}$ with positive probability then
$\mathrm{err}_{p}(\mathcal{D},\mathcal{Z})>0$ because the selectivity of every
rectangle in ${\mathcal{R}}$ is $0$. On the other hand, the selectivity of $B$
is $1$ so if we do not add any point $q\in B$ in $\mathcal{D}$ with positive
probability then $\mathrm{err}_{p}(\mathcal{D},\mathcal{Z})>0$. In any case,
$f(n)\alpha^{*}_{p,k}\geq\mathrm{err}_{p}(\mathcal{D},\mathcal{Z})>0$.
Actually, it is easy to verify that for any $\mathcal{D}\in\mathbb{D}$,
$\mathrm{err}_{p}(\mathcal{D},\mathcal{Z})>\frac{1}{2n^{2}}$ for any
$p\in\\{1,2,\infty\\}$. Thus, $f(n)\alpha^{*}_{p,k}>\frac{1}{2n^{2}}>0$.

Overall, let $\mathcal{D}$ be the distribution returned by $\mathcal{A}$ in
$h(d)n^{O(1)}$ time. Given $\mathcal{D}$, we can find
$\mathrm{err}_{p}(\mathcal{D},\mathcal{Z})$ in $O(n^{2})$ time, because
$|\mathcal{D}|\leq g(n)k\leq n$. If
$\mathrm{err}_{p}(\mathcal{D},\mathcal{Z})=0$ then the solution to the
coverage problem in the original instance is No. Otherwise, if
$\mathrm{err}_{p}(\mathcal{D},\mathcal{Z})>0$, then the solution to the
coverage problem in the original instance is Yes. This implies a
$h(d)n^{O(1)}$ time algorithm for the coverage problem, which is a
contradiction, under the $\mathsf{FPT}\neq W[1]$ conjecture. Hence,
$\mathcal{A}$ cannot run in $h(d)n^{O(1)}$ time.

###  A.3 Proof of Theorem 5.4

Similar to the previous proof we map an instance of coverage to an instance of
Approx-Selectivity, picking $\varepsilon=\frac{1}{8n^{2}}$. Same argument
shows that in No instance we get a distribution with error at most
$\frac{1}{8n^{2}}$ while in the Yes instance, it returns a distribution with
error at least $\frac{1}{2n^{2}}$.