# Improved Algorithms for Agnostic Pool-based Active Classification

Julian Katz-Samuels  Jifan Zhang  Lalit Jain  Kevin Jamieson

###### Abstract

We consider active learning for binary classification in the agnostic pool-
based setting. The vast majority of works in active learning in the agnostic
setting are inspired by the CAL algorithm where each query is uniformly
sampled from the disagreement region of the current version space. The sample
complexity of such algorithms is described by a quantity known as the
disagreement coefficient which captures both the geometry of the hypothesis
space as well as the underlying probability space. To date, the disagreement
coefficient has been justified by minimax lower bounds only, leaving the door
open for superior instance dependent sample complexities. In this work we
propose an algorithm that, in contrast to uniform sampling over the
disagreement region, solves an experimental design problem to determine a
distribution over examples from which to request labels. We show that the new
approach achieves sample complexity bounds that are never worse than the best
disagreement coefficient-based bounds, but in specific cases can be
dramatically smaller. From a practical perspective, the proposed algorithm
requires no hyperparameters to tune (e.g., to control the aggressiveness of
sampling), and is computationally efficient by means of assuming access to an
empirical risk minimization oracle (without any constraints). Empirically, we
demonstrate that our algorithm is superior to state of the art agnostic active
learning algorithms on image classification datasets.

##  1 Introduction

Most applications of machine learning have an enormous amount of unlabeled
data. Yet, many powerful machine learning methods require that this data be
labeled and reliable labels are costly since they require human intervention.
The cost of providing labels has become one of the main bottlenecks in
applications of machine learning, generating much interest in the problem of
_active classification_ where the learner is given an unlabeled pool of
examples and her goal is to identify an accurate hypothesis using the minimum
number of labels possible (Settles, 2011).

One of the most popular algorithmic paradigms is disagreement-based active
classification (Hanneke et al., 2014). Under this approach, after observing
$k$ labels a version space $\mathcal{V}_{k}$ of the most promising classifiers
is maintained, and the learner queries an example $x$ if there are two
hypotheses $h_{1}$ and $h_{2}$ belonging to $\mathcal{V}_{k}$ that disagree on
the label of $x$. This approach has received much attention because it applies
to generic hypothesis classes, it can be made robust to label noise, and it
can be efficient by using a constrained cost-sensitive classification oracle,
a problem for which there are many reasonable heuristics (Agarwal et al.,
2018; Beygelzimer et al., 2010).

However, disagreement-based active classification suffers from two significant
shortcomings. First, it queries uniformly any example on which there is
disagreement even though intuitively some of these examples may be much more
informative than others. Second, disagreement-based active classification
algorithms tend to take a naive union bound over all hypotheses, which ignores
many of the dependencies among the hypotheses. Indeed, recent work in pure
exploration combinatorial and linear bandits has shown that such naive union
bounds can be highly suboptimal and have a significant impact on empirical
performance (Cao & Krishnamurthy, 2019; Jain & Jamieson, 2019; Katz-Samuels et
al., 2020). Given that these naive union bounds are very loose and appear in
the confidence bounds used by the algorithms, in practice, many works instead
replace these union bounds with a constant that can be tuned to control the
aggressiveness of the algorithm (Beygelzimer et al., 2010; Huang et al.,
2015). Unfortunately, this constant introduces a hyperparameter to the active
learning algorithm that is difficult to set before seeing lots of data.

We design a new algorithm for pool-based active classification that addresses
these shortcomings. It optimizes a novel experimental design objective that
finds the best subset of examples in the disagreement region to query in order
to identify the best classifier. It avoids wasteful union bounds by adapting
to the geometry of the hypothesis space and thus avoiding the need to choose
hyperparameters. We introduce a new notion of sample complexity inspired by
experimental design that improves on disagreement-based active classification
by a factor up to $\sqrt{n}$ where $n$ is the size of the pool while being
only a logarithmic factor worse than disagreement-based learning in the worst
case.

###  1.1 Preliminaries

Let $\mathcal{X}$ denote the input space, and let
$\\{x_{1},\ldots,x_{n}\\}\subset\mathcal{X}$ denote a pool of examples. Let
$\mathcal{H}$ denote a class of hypotheses where each
$h:\mathcal{X}\mapsto\\{0,1\\}$ assigns a label to each example in the pool.
Let
$\operatorname*{\mathcal{H}_{x}}:=\\{(h(x_{i}))_{i\in[n]}:h\in\mathcal{H}\\}$
denote the set of labelings over the pool induced by the hypothesis class
$\mathcal{H}$. Let $d$ denote the VC dimension of $\mathcal{H}$. When example
$i\in[n]$ is queried, the agent receives label
$Y_{i}\sim\text{Bern}({\operatorname*{\eta}}_{i})$ where
$\eta=(\eta_{i})_{i=1}^{n}\in[0,1]^{n}$. We define the error of a hypothesis
$h\in\mathcal{H}$ on the pool of examples as given by

$\displaystyle\operatorname*{\text{err}}(h)$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\mathbb{P}(Y_{i}\neq h(x_{i}))$ (1)
$\displaystyle=\frac{1}{n}\sum_{i\in[n]}{\operatorname*{\eta}}_{i}(1-h(x_{i}))+(1-{\operatorname*{\eta}}_{i})h(x_{i}).$

Let
$h^{*}:=\operatorname*{arg\,min}_{h\in\mathcal{H}}\operatorname*{\text{err}}(h)$
be the hypothesis of minimum error, and let
$\nu=\operatorname*{\text{err}}(h^{*})$. The goal in active classification is
to find an $h\in\mathcal{H}$ with error close to that of $h^{*}$ using as few
label queries as possible. In this paper, we quantify performance as follows:

Problem. Agnostic Pool Based PAC Active Classification: Given
$\epsilon>0,\delta\in(0,1)$, identify an $\epsilon$-good classifier, that is,
an $h\in\mathcal{H}$ such that
$\operatorname*{\text{err}}(h)-\operatorname*{\text{err}}(h^{*})\leq\epsilon$
with probability at least $1-\delta$ using as few labels as possible.

######  Remark 1.

The goal of finding an $\epsilon$-good classifier over a pool of examples is
closely related to the goal of using an active classification algorithm to
find a classifier with good generalization. Suppose $VCdim(\mathcal{H})=d$ and
let $\mathcal{D}$ be a distribution over $\mathcal{X}\times\\{0,1\\}$. For
$i=1,\dots,n$ let $(x_{i},y_{i})\sim\mathcal{D}$. If $\widehat{h}$ satisfies
$\operatorname*{\text{err}}(\widehat{h})\leq\min_{h\in\mathcal{H}}\operatorname*{\text{err}}(h)+\epsilon$,
then with probability at least $1-\delta$

$\displaystyle\mathbb{P}_{(x,y)\sim\mathcal{D}}(\widehat{h}(x)\neq y)\leq$
$\displaystyle\quad\min_{h\in\mathcal{H}}\mathbb{P}_{(x,y)\sim\mathcal{D}}(h(x)\neq
y)+\epsilon+O\Big{(}\sqrt{\frac{d\ln(1/\delta)}{n}}\Big{)}.$

by standard passive generalization bounds (Boucheron et al., 2005).

###  1.2 Main contributions

We briefly summarize our contributions:

  * •

We cast pool-based active binary classification as an _adaptive experimental
design problem_ that computes an optimal sampling distribution over the pool
of unlabelled examples. We demonstrate that an $\epsilon$-good classifier can
be obtained with probability at least $1-\delta$ by requesting just
$\gamma^{*}(\epsilon)+\rho^{*}(\epsilon)\log(1/\delta)$ labels if examples to
label are drawn from the optimal design, where $\gamma^{*}(\epsilon)$ and
$\rho^{*}(\epsilon)$ are problem-dependent quantities defined in the next
section.

  * •

Since this optimal design uses problem dependent information like $\eta$, it
is not a constructive strategy or algorithm for a learner. Treating the sample
complexity achieved by this optimal design as a target, we design an algorithm
that performs sequential stages of experimental design to match the sample
complexity of the optimal design,
$\gamma^{*}(\epsilon)+\rho^{*}(\epsilon)\log(1/\delta)$ up to a
$\log(1/\epsilon)$ factor. The algorithm employs the use of a novel estimator
that appeals to a chaining argument. Unfortunately, the method is not
computationally efficient.

  * •

We propose a second algorithm that is computationally efficient given access
to an empirical risk minimization oracle. The price for computational
tractability is a slightly worse sample complexity. Besides being
computationally efficient, our approach avoids the need to tune
hyperparameters and the use of a _constrained_ empirical risk minimization
oracle which are required by other active learning algorithms (Beygelzimer et
al., 2010; Huang et al., 2015).

  * •

We compare our sample complexity results to those of state-of-the-art
disagreement-based learning algorithms that are given in terms of the so-
called disagreement coefficient. We demonstrate that our results, up to log
factors, are never worse than previous results, but can be substantially
better in certain cases.

  * •

Empirically, we compare our procedure to state-of-the-art algorithms for the
agnostic setting including variants of the importance weighted active learning
algorithm (IWAL) (Beygelzimer et al., 2010) and active cover (Huang et al.,
2015). We demonstrate that our method is superior across four image
classification tasks.

##  2 Experimental Design for Active Classification

We seek to identify an $\epsilon$-good classifier by seeing as few labels as
possible. To this end, we can take motivation from _experimental design_ to
consider the _optimal_ sampling distribution over our pool of unlabeled
examples $[n]$. For an arbitrary distribution
$\lambda\in\triangle_{n}:=\\{p\in\mathbb{R}^{n}:p_{i}\geq 0,\forall
i\in[n];\sum_{i=1}^{n}p_{i}=1\\}$ suppose we sampled
$I_{1},\cdots,I_{t}\sim\lambda$ and then observed $y_{s}$ for each $s\in[t]$.
Then an unbiased natural estimator for the error of a classifier
$h\in\mathcal{H}$ defined by (1) is given by

$\displaystyle\widetilde{\operatorname*{\text{err}}}(h)=\frac{1}{t}\sum_{s=1}^{t}\frac{1/n}{\lambda_{I_{s}}}\mathbbm{1}\\{h(x_{I_{s}})\neq
y_{s}\\}.$

Indeed, by i.i.d. sampling from $\lambda$, we have for any $s\in[t]$

$\displaystyle\mathbb{E}[\widetilde{\operatorname*{\text{err}}}(h))]$
$\displaystyle=\mathbb{E}\Big{[}\frac{1/n}{\lambda_{I_{s}}}\mathbbm{1}\\{h(x_{I_{s}})\neq
y_{s}\\}\Big{]}$
$\displaystyle=\sum_{i=1}^{n}\mathbb{P}(I_{s}=i)\frac{1/n}{\lambda_{i}}\mathbb{E}[\mathbbm{1}\\{h(x_{i})\neq
y_{s}\\}|I_{s}=i]$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\mathbb{P}(Y_{i}\neq
h(x_{i}))=\operatorname*{\text{err}}(h)$

since by definition, $\mathbb{P}(I_{s}=i)=\lambda_{i}$. Likewise, an estimator
for the excess risk is given by

$\displaystyle\widetilde{\operatorname*{\text{err}}}(h)$
$\displaystyle-\widetilde{\operatorname*{\text{err}}}(h^{*})=$ (2)
$\displaystyle\frac{1}{t}\sum_{s=1}^{t}\frac{1/n}{\lambda_{i}}(\mathbbm{1}\\{h(x_{I_{s}})\neq
y_{s}\\}-\mathbbm{1}\\{h^{*}(x_{I_{s}})\neq y_{s}\\}).$

It is straightforward to show that the variance of
$\widetilde{\operatorname*{\text{err}}}(h)-\widetilde{\operatorname*{\text{err}}}(h^{*})$
is upper bounded by
$\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\lambda_{i}n^{2}}\mathbbm{1}\\{h^{*}(x_{i})\neq
h(x_{i})\\}$, using the upper bound $\mathbbm{1}\\{h(x_{I})\neq
y_{s}\\}-\mathbbm{1}\\{h^{*}(x_{I})\neq
y_{s}\\})\leq\mathbbm{1}\\{h^{*}(x_{I})\neq h(x_{I})\\}$. Applying Bernstein’s
inequality (and ignoring the $1/t$ term) with probability at least $1-\delta$

$\displaystyle|\widetilde{\operatorname*{\text{err}}}(h)-\widetilde{\operatorname*{\text{err}}}(h^{*})-(\operatorname*{\text{err}}(h)-\operatorname*{\text{err}}(h^{*}))|\lessapprox$
$\displaystyle\quad\sqrt{\frac{\sum_{i=1}^{n}\frac{1}{\lambda_{i}n^{2}}\mathbbm{1}\\{h^{*}(x_{i})\neq
h(x_{i})\\}\log(|\mathcal{H}_{x}|/\delta)}{t}}.$ (3)

This then suggests that to estimate the excess error of this particular $h$
with probability at least $1-\delta$, it suffices to take $t$ large enough to
make the RHS of (3) less than $\epsilon$. To upper bound the excess risk of
every $h\in\mathcal{H}$ simultaneously, it suffices to take
$t\geq\sup_{h\in\mathcal{H}}\frac{\sum_{i=1}^{n}\frac{1}{\lambda_{i}n^{2}}\mathbbm{1}\\{h^{*}(x_{i})\neq
h(x_{i})\\}}{\max\\{\epsilon^{2},(\operatorname*{\text{err}}(h)-\operatorname*{\text{err}}(h^{*}))^{2}\\}}\log(|\mathcal{H}|/\delta)$.
If we seek to _minimize_ the total number of observations, we simply minimize
over all $\lambda\in\triangle_{n}$, motivating the complexity measure:

$\displaystyle\rho^{*}(\epsilon)$
$\displaystyle:=\inf_{\lambda\in\operatorname*{\mathbf{\triangle}}_{n}}\sup_{h\in\mathcal{H}\setminus\\{h^{*}\\}}\frac{\sum_{i=1}^{n}\frac{1}{\lambda_{i}n^{2}}\mathbbm{1}\\{h^{*}(x_{i})\neq
h(x_{i})\\}}{\max(\operatorname*{\text{err}}(h)-\operatorname*{\text{err}}(h^{*}),\epsilon)^{2}}.$

Thus, we’d expect that if $t\geq\rho^{*}(\epsilon)\log(|\mathcal{H}|/\delta)$
samples are drawn from the $\lambda$ that minimizes $\rho^{*}(\epsilon)$, then
$\widehat{h}=\arg\min_{h\in\mathcal{H}}\widetilde{\operatorname*{\text{err}}}(h)$
will be $\epsilon$-good.

###  2.1 Sidestepping the Naive Union Bound

A significant shortcoming of the standard approach of applying Bernstein’s
inequality with a naive union bound is that the the naive union bound incurs
an additional factor of $\log(|\operatorname*{\mathcal{H}_{x}}|)$ in the
sample complexity. For infinite classes,
$\log(|\operatorname*{\mathcal{H}_{x}}|)$ can be replaced by the VC-dimension
of $\operatorname*{\mathcal{H}_{x}}$, however this can still be very loose. In
practice, active learning algorithms replace
$\log(|\operatorname*{\mathcal{H}_{x}}|)$ by a tunable parameter $C_{0}$
(Beygelzimer et al., 2010; Huang et al., 2015). Ideally $C_{0}$ would be
chosen via cross-validation but since our data is being chosen adaptively,
under an active algorithm that depends on $C_{0}$, it is unclear how to make
the choice a priori.

To improve upon the naive union-bound we appeal to results from empirical
process theory. Appealing to the Talagrand/Bousquet inequality (Boucheron et
al., 2005), for all $h\in\mathcal{H}$, especially the empirical risk minimizer
$\widehat{h}=\operatorname*{arg\,min}_{h\in\mathcal{H}}\widetilde{\operatorname*{\text{err}}}(h)$,
we have

$\displaystyle\widetilde{\operatorname*{\text{err}}}(h)-\widetilde{\operatorname*{\text{err}}}(h^{\ast})-(\operatorname*{\text{err}}(h)-\operatorname*{\text{err}}{h^{\ast}})$
$\displaystyle\leq$ $\displaystyle
2\mathbb{E}[\sup_{h\in\mathcal{H}}|\widetilde{\operatorname*{\text{err}}}(h)-\widetilde{\operatorname*{\text{err}}}(h^{\ast})-(\operatorname*{\text{err}}(h)-\operatorname*{\text{err}}{h^{\ast}})|]$
$\displaystyle+\sqrt{\frac{\sup_{h\in\mathcal{H}}\sum_{i=1}^{n}\frac{1}{\lambda_{i}n^{2}}\mathbbm{1}\\{h^{*}(x_{i})\neq
h(x_{i})\\}\log(1/\delta)}{t}}$
$\displaystyle+\frac{4\sup_{i\in[n]}1/\lambda_{i}\log(1/\delta)}{3t}.$

Traditionally, we compute the expectation of the suprema using symmeterization
to obtain the Rademacher complexity of $\mathcal{H}\backslash\\{h^{*}\\}$. In
general, the Rademacher complexity is within a $\log(n)$ factor of the
Gaussian Width (Bartlett & Mendelson, 2002). In particular,

$\displaystyle\mathbb{E}[$
$\displaystyle\sup_{h\in\mathcal{H}}|\widetilde{\operatorname*{\text{err}}}(h)-\widetilde{\operatorname*{\text{err}}}(h^{\ast})-(\operatorname*{\text{err}}(h)-\operatorname*{\text{err}}{h^{\ast}})|]$
$\displaystyle\leq\frac{1}{\sqrt{t}}\mathbb{E}_{{\zeta}\sim
N(0,I)}\Big{[}\sup_{h\in\mathcal{H}}\sum_{i\in[n]}\frac{{\zeta}_{i}}{n\lambda^{1/2}}(h^{*}(x_{i})-h(x_{i}))\Big{]}.$

Using the same argument that motivated $\rho^{*}(\epsilon)$ but applying
Bousquet’s inequality instead of Bernstein’s inequality, we introduce the
following new complexity measure for active classification:

$\displaystyle\gamma^{*}(\epsilon)$
$\displaystyle:=\inf_{\lambda\in\operatorname*{\mathbf{\triangle}}_{n}}\mathbb{E}_{{\zeta}}\Big{[}\sup_{h\in\mathcal{H}}\frac{\sum_{i\in[n]}\frac{{\zeta}_{i}(h^{*}(x_{i})-h(x_{i}))}{n\lambda_{i}^{1/2}}}{\max(\operatorname*{\text{err}}(h)-\operatorname*{\text{err}}(h^{*}),\epsilon)}\Big{]}^{2}.$

Analogous to above, if we ignore the $1/t$ term, we’d expect that if
$t\geq\gamma^{*}(\epsilon)+\rho^{*}(\epsilon)\log(1/\delta)$ samples are drawn
from the $\lambda$ that minimizes the maximum of $\gamma^{*}(\epsilon)$ and
$\rho^{*}(\epsilon)$, then
$\widehat{h}=\arg\min_{h\in\mathcal{H}}\widetilde{\operatorname*{\text{err}}}(h)$
will be $\epsilon$-good.

We can relate $\gamma^{*}(\epsilon)$ to $\rho^{*}(\epsilon)$ in the following
way.

######  Proposition 1 (Katz-Samuels et al. (2020)).

$\gamma^{*}(\epsilon)\leq
c\log(|\operatorname*{\mathcal{H}_{x}}|)\rho^{*}(\epsilon)\leq
cd\log(\frac{n}{d})\rho^{*}(\epsilon)$.

The first inequality parallels the application of Massart’s finite class lemma
to bound the Rademacher complexity in statistical learning theory and the
second inequality follows from the Sauer-Shelah Lemma. Katz-Samuels et al.
(2020) also demonstrates a lower bound on $\gamma^{*}(\epsilon)$ that is
dominated by $\rho^{*}(\epsilon)$. In the appendix, we show that
$\gamma^{*}(\epsilon)$ matches the minimax rates for classification given for
the hypothesis class of thresholds in (Castro & Nowak, 2008).

Main Takeaway: In Section 3 we will establish an algorithm that achieves a
sample complexity of
$(\gamma^{\ast}(\epsilon)+\rho^{\ast}(\epsilon)\log(1/\delta))\log(1/\epsilon)$
to obtain an $\epsilon$-good classifier with probability greater than
$1-\delta$. In the next section we compare this result to disagreement based
methods. Note that we will write $\rho^{*}:=\rho^{*}(0)$ and
$\gamma^{*}:=\gamma^{*}(0)$.

###  2.2 Comparison with the Disagreement Coefficient

To date, theoretically grounded active learning algorithms in the agnostic
setting are disagreement region sampling methods. At the beginning of each
round $t$ these algorithms construct a version space
$\mathcal{V}\subset\mathcal{H}$ which is defined to be the set of classifiers
that have yet to be ruled out by the algorithm using the observed labels up to
round $t-1$. These algorithms then choose $x_{I_{t}}$ to be uniformly sampled
from $\operatorname*{\text{DIS}}(\mathcal{V})$, the disagreement region, which
is the set of points on which any two hypotheses in $\mathcal{V}$ disagree:

$\displaystyle\operatorname*{\text{DIS}}(\mathcal{V})$
$\displaystyle=\\{i:\exists h,h^{\prime}\in\mathcal{V}\text{ s.t.
}h(x_{i})\neq h^{\prime}(x_{i})\\}.$

In the notation of the previous section, these algorithms are sampling from
$\lambda_{t}$ where $\lambda_{t}$ is the uniform distribution supported on
$\operatorname*{\text{DIS}}(\mathcal{V})$ (Hanneke et al., 2014).

The main complexity measure considered for disagreement based algorithms is
the disagreement coefficient defined as

$\displaystyle\operatorname*{\theta}(\xi)$
$\displaystyle=\sup_{r\geq\xi}\frac{|\operatorname*{\text{DIS}}(B(h_{*},r))|/n}{r}$

where $B(h_{*},r)$ is the ball of radius $r$ centered at $h^{*}$:

$\displaystyle B(h_{*},r)$
$\displaystyle=\\{h\in\mathcal{H}:\frac{\sum_{i\in[n]}\mathbbm{1}\\{h^{*}(x_{i})\neq
h(x_{i})\\}}{n}\leq r\\}.$

We consider sample complexity results for finding an $h$ with
$\operatorname*{\text{err}}(h)\leq\nu+\epsilon$, where
$\nu=\operatorname*{\text{err}}(h^{\ast})$ under two common settings.

  1. 1.

The Agnostic Setting: we make no assumptions on $\eta\in[0,1]^{n}$. In this
case the best known sample complexities scale like

$\displaystyle\operatorname*{\theta}(\epsilon)(\frac{\nu^{2}}{\epsilon^{2}}+\log(1/\epsilon))d$

where $d$ is the VC dimension of $\mathcal{H}$ (Hanneke et al., 2014). Note
that the noiseless setting of $\eta\in\\{0,1\\}^{n}$ is a special case.

  2. 2.

The Tsybakov noise condition: for some $a\in[1,\infty)$ and $\alpha\in(0,1]$
every $h\in\mathcal{H}\setminus\\{h^{*}\\}$ satisfies

$\displaystyle\frac{\sum_{i\in[n]}\mathbbm{1}\\{h^{*}(x_{i})\neq
h(x_{i})\\}}{n}$ $\displaystyle\leq
a(\operatorname*{\text{err}}(h)-\operatorname*{\text{err}}(h^{*}))^{\alpha}.$

In this case the best known sample complexities scale like:

$\displaystyle
a^{2}\frac{1}{\epsilon^{2-2\alpha}}\operatorname*{\theta}(a\epsilon^{\alpha})d\log(1/\epsilon).$

We now compare our claimed sample complexity of
$\gamma^{\ast}(\epsilon)+\rho^{\ast}(\epsilon)\log(1/\delta)$ to these known
sample complexity results. Define
$\Delta_{min}:=\min_{h\in\mathcal{H}\setminus\\{h_{*}\\}}\operatorname*{\text{err}}(h)-\operatorname*{\text{err}}(h^{*})$.

######  Proposition 2.

  * •

Suppose that $\operatorname*{\eta}\in\\{0,1\\}^{n}$.

$\displaystyle\rho^{*}(\epsilon)\leq
c\log(n\Delta_{min}^{-1}\vee\epsilon^{-1})\operatorname*{\theta}(\epsilon)[1+\frac{\nu^{2}}{\epsilon^{2}}].$

  * •

Suppose that the Tsabokov noise condition holds for some $a\in[1,\infty)$ and
$\alpha\in(0,1]$. Then,

$\displaystyle\rho^{*}(\epsilon)\leq
ca^{2}\frac{1}{\epsilon^{2-2\alpha}}\operatorname*{\theta}(a\epsilon^{\alpha})\log(n\Delta_{min}^{-1}\vee\epsilon^{-1}).$

Recall that Propositions 1 shows $\gamma^{\ast}(\epsilon)\leq
cd\rho^{\ast}(\epsilon)\log(n/d)$. Hence from Proposition 2, we see that our
sample complexity, $\gamma^{*}+\rho^{*}\log(1/\delta)$ is always as good as
the state-of-the-art sample complexities of disagreement-based learning up to
logarithmic factors in $n$ and $\epsilon^{-1}$ in both settings.

However, the converse is not true. In general the disagreement based active
classification sample complexities can be substantially larger than $\rho^{*}$
and $\gamma^{*}$.

######  Proposition 3.

There exists an instance where for sufficiently small $\xi$,
$\operatorname*{\theta}(\xi)\geq\Omega(n^{1/2})$ while $\rho^{*}=O(1)$ and
$\gamma^{*}=\log(n)$.

We emphasize that this is not just a feature of the analysis; any algorithm
that selects queries uniformly at random in the region of disagreement will
perform poorly on the instance in the proposition. This gap demonstrates a
provable improvement over prior art.

##  3 Fixed Confidence Algorithm

Input: Confidence level $\delta\in(0,1)$.

$\mathcal{H}_{1}\longleftarrow\mathcal{H}$, $k\longleftarrow 1$,
$\delta_{k}\longleftarrow\delta/2k^{2}$.

while $|\mathcal{H}_{k}|>1$ do

Let $\lambda_{k}$ and $\tau_{k}$ be the solution and value of the following
optimization problem
$\displaystyle\inf_{\lambda\in\operatorname*{\mathbf{\triangle}}_{n}}$
$\displaystyle\mathbb{E}_{{\zeta}\sim
N(0,I)}\Big{[}\max_{h\in\mathcal{H}_{k}}\sum_{i\in[n]}h(x_{i})\frac{{\zeta}_{i}}{n\lambda_{i}^{1/2}}\Big{]}^{2}$
(4) $\displaystyle+$ $\displaystyle
2\log(\frac{1}{\delta_{k}})\max_{h,h^{\prime}\in\mathcal{H}_{k}}\max_{h,h^{\prime}\in\mathcal{G}}\sum_{i=1}^{n}\frac{1}{\lambda_{i}n^{2}}\mathbbm{1}\\{h(x_{i})\neq
h^{\prime}(x_{i})\\}$

Set $N_{k}\longleftarrow c\tau_{k}2^{2(k+1)}$ where $c$ is a universal
constant.

Query $I_{1},\ldots,I_{N_{k}}\sim\lambda_{k}$ and receive rewards
$y_{1},\ldots,y_{N_{k}}$.

Let $\hat{\eta}_{k}:=\hat{\eta}(\mathcal{H}_{k},\delta_{k})$ be the estimator
defined in Theorem 1 for $\mathcal{H}_{k}$ with failure probability
$\delta_{k}$ using the samples $\\{(x_{I_{s}},y_{s})\\}_{s=1}^{N_{k}}$

$\mathcal{H}_{k+1}\longleftarrow\mathcal{H}_{k}\setminus\\{h\in\mathcal{H}_{k}:\exists
h^{\prime}\text{ such that
}\widetilde{\operatorname*{\text{err}}}(h^{\prime},\hat{\eta}_{k})-\widetilde{\operatorname*{\text{err}}}(h,\hat{\eta}_{k})+\frac{1}{2^{k+1}}\leq
0\\}$.

$k\longleftarrow k+1$

end while

Return: $\mathcal{H}_{k}=\\{\widehat{h}\\}$.

Algorithm 1 ACED (Active Classification using Experimental Design).

Algorithm 1 is an elimination-style algorithm, in the style of $A^{2}$ (Balcan
et al., 2009; Dasgupta et al., 2007; Huang et al., 2015; Jain & Jamieson,
2019), but optimizes the querying distribution similarly to algorithms from
the pure exploration linear bandits literature (Fiez et al., 2019; Katz-
Samuels et al., 2020). It chooses a distribution $\lambda_{k}$ over the
examples in (4) that minimizes the confidence bounds from Theorem 1 and
queries enough random examples from $\lambda_{k}$ to ensure that the estimates
of the difference in error rates,
$\operatorname*{\text{err}}(h)-\operatorname*{\text{err}}(h^{*})$, improve at
least by a factor of $2$ for all remaining hypotheses $h\in\mathcal{H}_{k}$.
Using these improved estimates of the gaps, it then eliminates all hypotheses
that can be shown to be suboptimal using the confidence bound in Theorem 1.

Given an estimator $\hat{\eta}$ for $\eta$, denote the induced estimate for
the error as

$\displaystyle\widetilde{\operatorname*{\text{err}}}(h,\hat{\eta})$
$\displaystyle=\frac{1}{n}\sum_{i\in[n]}{\hat{\operatorname*{\eta}}}_{i}(1-h(x_{i}))+(1-{\hat{\operatorname*{\eta}}}_{i})h(x_{i}).$

######  Theorem 1.

Let $\mathcal{G}\subset\mathcal{H}$. There exists an estimator
$\hat{\eta}(\mathcal{G},\delta)$ for $\eta$ constructed from $t$ samples drawn
i.i.d. from $\lambda$ such that with probability at least $1-\delta$,

$\displaystyle\sup_{h,h^{\prime}\in\mathcal{G}}|[\widetilde{\operatorname*{\text{err}}}(h,\hat{\eta})-\widetilde{\operatorname*{\text{err}}}(h^{\prime},\hat{\eta})]-[\operatorname*{\text{err}}(h)-\operatorname*{\text{err}}(h^{\prime})]|$
$\displaystyle\lesssim$
$\displaystyle\sqrt{\frac{\log(2/\delta)\max_{h,h^{\prime}\in\mathcal{G}}\sum_{i=1}^{n}\frac{1}{\lambda_{i}n^{2}}\mathbbm{1}\\{h(x_{i})\neq
h^{\prime}(x_{i})\\}}{t}}$
$\displaystyle+\sqrt{\frac{\mathbb{E}[\sup_{h\in\mathcal{G}}\sum_{i\in[n]}h(x_{i})\frac{{\zeta}_{i}}{n\lambda_{i}^{1/2}}]^{2}}{t}}.$

For now, we treat the estimator in Theorem 1 as a black-box and defer its
discussion until Section 4.1. Note that unlike the Talagrand/Bousquet
inequality presented before (3), _this confidence interval does not have a
term depending on the inverse of the worst case importance weight_.

Algorithm 1 attains the following sample complexity.

######  Theorem 2.

Let $\delta\in(0,1)$ and $\epsilon>0$. With probability at least $1-\delta$
Algorithm 1 returns $\widehat{h}\in\mathcal{H}$ after $\tau$ samples where
$\operatorname*{\text{err}}(\widehat{h})\leq\operatorname*{\text{err}}(h^{*})+\epsilon$
and

$\displaystyle\tau\lesssim\log(1/\epsilon)[\log(1/\delta)\rho^{*}(\epsilon)+\gamma^{*}(\epsilon)].$

##  4 Fixed Budget Algorithm

Input: Budget $T$, tolerance $\epsilon>0$

$N\longleftarrow\Big{\lfloor}T/\log_{2}(\epsilon^{-1})\Big{\rfloor}$, and
$\hat{\eta}_{0}=0$

for $k=1,2,\ldots,\Big{\lfloor}\log_{2}(\epsilon^{-1})\Big{\rfloor}$ do

$\tilde{h}_{k}\longleftarrow\operatorname*{arg\,min}_{h\in\mathcal{H}}\widetilde{\operatorname*{\text{err}}}(h,\hat{\eta}_{k-1})$.

Let $\lambda_{k}$ be the solution of the following optimization problem
$\displaystyle\inf_{\lambda\in\operatorname*{\mathbf{\triangle}}_{n}}\\!\mathbb{E}_{{\zeta}\sim
N(0,I)}\Big{[}\max_{h\in\mathcal{H}}\frac{\sum_{i\in[n]}(\tilde{h}_{k}(x_{i})-h(x_{i}))\frac{{\zeta}_{i}}{n\lambda_{i}^{1/2}}}{2^{-k+1}+\widetilde{\operatorname*{\text{err}}}(h,\hat{\eta}_{k-1})-\widetilde{\operatorname*{\text{err}}}(\tilde{h}_{k},\hat{\eta}_{k-1})}\Big{]}$
(5)

Sample $\\{x_{I_{1}},\ldots,x_{I_{N}}\\}\sim\lambda_{k}$.

Query $x_{I_{1}},\ldots,x_{I_{N}}$ and observe $y_{1},\ldots,y_{N}$.

Compute an estimate $\hat{\eta}_{k}$.

end for

Return:
$\operatorname*{arg\,min}_{h\in\mathcal{H}}\widetilde{\operatorname*{\text{err}}}(h,\hat{\eta}_{k})$

Algorithm 2 Fixed Budget ACED.

In many applications, the agent is given a budget of $T$ queries and a
performance target $\epsilon>0$, and the goal is to maximize the probability
of outputing a classifier $\widehat{h}\in\mathcal{H}$ such that
$\operatorname*{\text{err}}(\widehat{h})\leq\operatorname*{\text{err}}(h^{*})+\epsilon$.
We design a new algorithm for this setting that can be made computationally
efficient given access to a weighted classification oracle (defined shortly).

Algorithm 2 splits the budget into
$\Big{\lfloor}\log(\epsilon^{-1})\Big{\rfloor}$ phases. In each phase, the
algorithm computes the design that optimizes (5), the objective of which
approximates
$\mathbb{E}\Big{[}\max_{h\in\mathcal{H}\setminus\\{h^{*}\\}}\frac{\sum_{i\in[n]}\frac{{\zeta}_{i}}{n\lambda^{1/2}}(h^{*}(x_{i})-h(x_{i}))}{\max(\operatorname*{\text{err}}(h)-\operatorname*{\text{err}}(h^{*}),2^{-k+1})}\Big{]}^{2}$.
The algorithm can use any estimator $\hat{\eta}_{k}$ at each round $k$. The
next theorem uses the estimator of Theorem 1.

######  Theorem 3.

Let $T\in\mathbb{N}$ and $\epsilon>0$. Let $\widehat{h}$ denote the
$h\in\mathcal{H}$ returned by Algorithm 2. There exists an estimator
$\hat{\eta}_{k}$ using the samples $\\{(x_{I_{s}},y_{s})\\}_{s=1}^{N}$ in
round $k$ of Algorithm 2 such that for an absolute constant $c>0$

$\displaystyle\mathbb{P}(\operatorname*{\text{err}}(\widehat{h})$
$\displaystyle\geq\operatorname*{\text{err}}(h^{*})+\epsilon)$
$\displaystyle\leq\log(n\epsilon^{-1})\exp\Big{(}-\frac{cT}{\log(\epsilon^{-1})[\gamma^{*}(\epsilon)+\rho^{*}(\epsilon)]}\Big{)}.$

If $T\geq
c\log(\log(\epsilon^{-1}))\log(1/\delta)\log(\epsilon^{-1})[\gamma^{*}(\epsilon)+\rho^{*}(\epsilon)]$,
then with probability at least $1-\delta$, Algorithm 2 outputs
$\widehat{h}\in\mathcal{H}$ such that
$\operatorname*{\text{err}}(\widehat{h})\leq\operatorname*{\text{err}}(h^{*})+\epsilon$.
The proof of Theorem 3 leverages the estimator defined in Theorem 1 for
$\mathcal{H}$ and failure probability $\delta_{k}=\exp(-\Theta(N/\gamma_{k}))$
with $\gamma_{k}$ equal to the value of (5).

######  Remark 2.

Given $\\{(I_{t},y_{t})\\}_{t=1}^{T}$ where $I_{t}\sim\lambda$ define

$\displaystyle\hat{\eta}_{\gamma}^{(\text{Importance})}=\frac{1}{T}\sum_{t=1}^{T}\frac{y_{t}}{\lambda_{I_{t}}+\gamma}\mathbf{e}_{I_{t}}.$
(6)

If importance-weighted estimator $\hat{\eta}_{\gamma}^{(\text{Importance})}$
with $\gamma=0$ is used in Algorithm 2 (with a slightly modified objective
function in (5), see the Supplementary Material), one can obtain a
computationally efficient algorithm whose probability of error scales as

$\displaystyle\mathbb{P}(\operatorname*{\text{err}}(\widehat{h})\geq\operatorname*{\text{err}}(h^{*})+\epsilon)\leq$
$\displaystyle\quad\log(n\epsilon^{-1})\exp(-\frac{T-\log(|\operatorname*{\mathcal{H}_{x}}|)\psi^{*}(\epsilon)}{\log(\epsilon^{-1})[\gamma^{*}(\epsilon)+\rho^{*}(\epsilon)+\psi^{*}(\epsilon)]})$

where
$\displaystyle\psi^{*}(\epsilon)\\!:=\\!\min_{\lambda\in\operatorname*{\mathbf{\triangle}}_{n}}\max_{\begin{subarray}{c}i\in[n]:\exists
h\in\mathcal{H}\\\ h^{*}(x_{i})\neq
h(x_{i})\end{subarray}}\frac{1/n\lambda_{i}}{\max(\epsilon,\operatorname*{\text{err}}(h)-\operatorname*{\text{err}}(h^{*}))}.$

There are instances where $\psi^{*}(\epsilon)\gg\gamma^{*}(\epsilon)$ and
therefore the cost of computational efficiency is a worse sample complexity.
See the appendix for more details.

###  4.1 Discussion of Theorem 1

Theorem 1 above demonstrates the existence of an estimator that avoids any
dependence on $\log(|\operatorname*{\mathcal{H}_{x}}|)$. The construction of
the estimator in Theorem 1 uses generic chaining, a technique that builds a
highly optimized union bound to avoid extraneous logarithmic factors
(Talagrand, 2014). Generic chaining is most easily applied when a given
estimator $\hat{\eta}$ satisfies the property that
$\widetilde{\operatorname*{\text{err}}}(h,\hat{\eta})-\widetilde{\operatorname*{\text{err}}}(h^{\prime},\hat{\eta})$
is sub-Gaussian for every “direction” $h-h^{\prime}$ of interest (e.g., see
(Katz-Samuels et al., 2020)). Though the
$\hat{\eta}_{\gamma}^{(\text{Importance})}$ estimator has sub-Gamma tails in
general, ruling out its use, the following result shows that for
$h-h^{\prime}$ in a ball under a certain norm, we can construct an estimator
for
$\widetilde{\operatorname*{\text{err}}}(h,\hat{\eta})-\widetilde{\operatorname*{\text{err}}}(h^{\prime},\hat{\eta})$
with a sub-Gaussian-like tail.

######  Proposition 4.

Fix $\lambda\in\triangle_{n}$, $\delta\in(0,1)$, and
$h,h^{\prime}\in\mathcal{H}$. If $T$ samples are taken from $\lambda$ and
$\hat{\eta}:=\hat{\eta}^{(\text{Importance})}_{\gamma}$ is computed with
$\gamma=\sqrt{\frac{\log(2/\delta)}{3\sum_{i=1}^{n}\frac{1}{\lambda_{i}n^{2}}\mathbbm{1}\\{h(x_{i})\neq
h^{\prime}(x_{i})\\}}}$ then with probability at least $1-\delta$

$\displaystyle|[\widetilde{\operatorname*{\text{err}}}$
$\displaystyle(h,\hat{\eta})-\widetilde{\operatorname*{\text{err}}}(h^{\prime},\hat{\eta})]-[\operatorname*{\text{err}}(h)-\operatorname*{\text{err}}(h^{\prime})]|$
$\displaystyle\left(\sqrt{\tfrac{2}{3}}+1\right)\sqrt{\frac{2\sum_{i=1}^{n}\frac{1}{\lambda_{i}n^{2}}\mathbbm{1}\\{h(x_{i})\neq
h^{\prime}(x_{i})\\}\log(\tfrac{2}{\delta})}{t}}.$

The idea behind Theorem 1 is to apply generic chaining to all $h-h^{\prime}$,
but to use a different $\hat{\eta}$ (specifically, a different $\gamma$) based
on the size of $h-h^{\prime}$ prescribed by Proposition 4. Details of the
technique can be found in the supplementary materials.

###  4.2 Computationally Efficient Experimental Design

In this section, we discuss how to solve (5) efficiently given access to a
weighted empirical risk minimization oracle, which we will introduce shortly.
First, note that minimizing (5) is equivalent to minimizing
$\mathbb{E}_{{\zeta}\sim N(0,I)}[\max_{h\in\mathcal{H}}f(\lambda;h;{\zeta})]$
with respect to $\lambda$ where

$\displaystyle f(\lambda;h;{\zeta})$
$\displaystyle:=\tfrac{\sum_{i\in[n]}(\tilde{h}_{k}(x_{i})-h(x_{i}))\frac{{\zeta}_{i}}{n\lambda_{i}^{1/2}}}{2^{-k+1}+\widetilde{\operatorname*{\text{err}}}(h,\hat{\eta}_{k-1})-\widetilde{\operatorname*{\text{err}}}(\tilde{h}_{k},\hat{\eta}_{k-1})}$
$\displaystyle:=\tfrac{\sum_{i\in[n]}(\tilde{h}_{k}(x_{i})-h(x_{i}))\frac{{\zeta}_{i}}{n\lambda_{i}^{1/2}}}{2^{-k+1}+\sum_{i\in[n]}(1-2\hat{\eta}_{k-1,i})(\tilde{h}_{k}(x_{i})-h(x_{i}))}.$

It is known that $\mathbb{E}_{{\zeta}\sim
N(0,I)}[\max_{h\in\mathcal{H}}f(\lambda;h;{\zeta})]$ is convex in $\lambda$
(Katz-Samuels et al., 2020), hence we perform the minimization over $\lambda$
via stochastic mirror descent with stochastic gradient
$g(\lambda,{\zeta})=\nabla f(\lambda,\widetilde{h};{\zeta})$ where
${\zeta}\sim\mathcal{N}(0,I)$ and
$\widetilde{h}\in\arg\max_{h\in\mathcal{H}}f(\lambda,h;{\zeta})$. To obtain
$\widetilde{h}$ for a fixed $\lambda$ and ${\zeta}$, first note that the value
$\max_{h\in\mathcal{H}}f(\lambda;h;{\zeta})$ is equal to

$\displaystyle\min_{r\in\mathbb{R}^{+}}r\,\text{subject to}\enspace
ar+b+\max_{h\in\mathcal{H}}\,\sum_{i\in[n]}(c_{i}r+d_{i})h(x_{i})\leq 0$

where $a=-2^{-k+1}-\sum_{i\in[n]}(1-2\hat{\eta}_{k,i})\tilde{h}_{k}(x_{i})$,
$b=\sum_{i\in[n]}\frac{{\zeta}}{n\lambda_{i}^{1/2}}\tilde{h}_{k}(x_{i})$,
$c_{i}=1-2\hat{\eta}_{k-1,i}$ and $d_{i}=-\frac{{\zeta}}{n\lambda_{i}^{1/2}}$.

For any fixed positive value of $r$ it suffices to check the constraint. We
can then use a line search procedure to find the minimizing value of $r$
(details in Appendix K).

Thus we have reduced to checking the constraint for a fixed
$r\in\mathbb{R}^{+}$. Specifically, the difficulty is to solve for
$\max_{h\in\mathcal{H}}\sum_{i\in[n]}w_{i}\cdot h(x_{i})$ where $w_{i}$ are
arbitrary weights. This can be reduced to weighted $0/1$-loss minimization
problem that is solvable by a weighted classification oracle:

$\displaystyle\text{oracle}(\\{\tilde{w}_{i},\tilde{x}_{i},\tilde{y}_{i}\\}_{i=1}^{n})\\!:=\\!\operatorname*{arg\,min}_{h\in\mathcal{H}}\\!\sum_{i\in[n]}\tilde{w}_{i}\\!\cdot\\!\mathbf{1}\\{h(\tilde{x}_{i})\neq\tilde{y}_{i}\\}$

for inputs $\\{\tilde{w}_{i},\tilde{x}_{i},\tilde{y}_{i}\\}_{i=1}^{n}$. Then,

$\displaystyle\max_{h\in\mathcal{H}}\sum_{i\in[n]}w_{i}\cdot
h(x_{i})=\text{oracle}(\\{|w_{i}|,x_{i},\mathbf{1}\\{w_{i}\geq
0\\}\\}_{i=1}^{n}).$

##  5 Implementation and Experiments

In the previous section we reduced the experimental design objective of (5) to
a weighted 0/1 loss classification problem using weights that are functions of
the estimated vector $\widehat{\eta}$. In practice we replace this 0/1 loss
with a surrogate convex loss, namely the logistic loss. However, to implement
Algorithm 2 we still have to specify the choice of estimator $\hat{\eta}$.
Though the estimator specified in Theorem 1 is theoretically grounded, it is
difficult to implement in practice since it involves a costly constrained
linear optimization problem over the set of hypothesis in $\mathcal{H}_{k}$.
As described in Remark 2, it is still possible to have a theoretical guarantee
for other estimators such as the IPS estimator. As described precisely in
Appendix K, in our implementation we take the estimate for $\hat{\eta}_{k}$ to
be

$\displaystyle\big{[}\hat{\eta}_{k}^{(\text{Naive})}\big{]}_{i}=\text{average}(\\{y_{s}^{(j)}:I_{s}^{(j)}=i,s\in[N_{j}],j\in[k]\\}),$

i.e. a simple average of the labels we see. Here $I_{s}^{(j)}$ indexes the
$s$-th query we made in round $j$. In our experiments we only considered the
persistent noise setting (i.e., querying the same image more than once would
always return the same label as before, or formally, $\eta_{i}\in\\{0,1\\}$).
Thus, if we sample a point $x_{I_{s}}^{(j)}$ (i.e., $I_{s}^{(j)}$) more than
once, we set $y_{s}^{(j)}$ to be the previously observed label and we did not
count this observation in our count of total labels taken. To take advantage
of all of the labels observed so far, we also employ a water-filling technique
for sampling in practice (details in Appendix K).

Baselines. To validate Algorithm 2 we conducted a set of experiments against
the following baselines that are considered to be state-of-the-art
theoretically-justified methods in disagreement based active learning. Our set
of methods are chosen based on the ones considered in (Huang et al., 2015),
the most recent work of relevance. Details on the precise implementations of
these methods are available in the supplementary materials in Appendix K.

  * •

Passive: We considered a passive baseline where we uniformly at random choose
samples from our pool, retrain our model on our current samples and report the
accuracy.

  * •

Importance Weighted Active Learning (IWAL) : IWAL was originally introduced in
Beygelzimer et al. (2009) and is an active learning algorithm in the streaming
setting. Our implementation is based on the algorithm presented in Beygelzimer
et al. (2010) which we refer to as IWAL0. We also consider variants, IWAL1,
and oracular versions ORA-IWAL0, ORA-IWAL1 detailed in Huang et al. (2015).

  * •

Online Active Cover (OAC): OAC is described in Huang et al. (2015). We used
the implementation of OAC that is available in Vowpal Wabbit (Agarwal et al.,
2014).

Datasets. We evaluate on the following four real datasets.

  * •

MNIST 0-4 vs 5-9 (LeCun et al., 1998). We considered the standard MNIST
dataset but in a binary setting where digits 0-4 are labelled as 0, and 5-9
are labelled as 1. Our pool has 50000 images in total, and we classified based
on the flattened images (784 dimensions).

  * •

SVHN 2 vs 7 (Netzer et al., 2011). We considered the binary classification
problem of determining whether a digit was a 2 or a 7 (ignoring all other
images). To prevent the logistic classifier from overfitting to arbitrary
labels and to restrict the hypothesis class $\mathcal{H}$, we downsample the
images to 512 dimensional feature vectors through PCA. There are 16180 images
in total.

  * •

CIFAR Bird vs Plane (Netzer et al., 2011). We considered the binary
classification problem of determining whether a digit was a bird or a plane
(ignoring all other images). To prevent the logistic classifier from
overfitting to arbitrary labels and to restrict the hypothesis class
$\mathcal{H}$, we downsample the images to 576 dimensional feature vectors
through PCA. There are 10000 images in total.

  * •

FashionMNIST T-shirt vs Pants (Xiao et al., 2017). We considered the binary
classification problem of T-shirt vs Pants. Our pool has 12000 images in
total, and we classified based on the flattened images (784 dimensions).

Implementations. We use two implementations to measure the performances of the
algorithms.

  * •

Implementation from Vowpal Wabbit (Agarwal et al., 2014) that is used by Huang
et al. (2015). The implementation employs an online learner that only updates
based on the latest queried label, therefore has time complexity that scales
linearly in the number of images $n$.

  * •

For our implementation in a batched setting, we retrain the entire classifier
to convergence every time new labels become available. We find that the online
learner of above can perform significantly better than our batched learner
during the first few batches of training. However, our implementation has more
stable accuracies during the course of training and performs slightly superior
($<1\%$) in final accuracy. This comes at a cost of an $O(n^{2})$ time
complexity, which is too expensive in some of the settings.

In particular, we only use the Vowpal Wabbit implementation for the OAC
experiments and the oracular variants of IWAL algorithms for our MNIST
experiement, due to the high computation cost for running these algorithms
with exhaustive hyperparameter search. However, we think this is still a fair
comparison when evaluating some baselines using the the two implementations
since it is the best one can achieve for those baselines within a computation
budget (single machine with state-of-art commercialized CPU that runs for a
month).

Hypothesis Class. In our implementation, we took the hypothesis space to be
the set of linear separators in the underlying feature space. We used the
logistic regression implementation in Scikit-learn (Pedregosa et al., 2011)
for our underlying classification oracle.

Figure 1: MNIST Performance

Figure 2: SVHN Performance

Figure 3: CIFAR Performance

Figure 4: FashionMNIST

Discussion. For each of the binary classification datasets, we plot the
running maximum accuracy on the unlabelled pool against the number of queries
taken as in Figure 1,2,4,3 (full scale images included in Appendix L). The
passive curves are evaluated based on the averages of $10$ runs. In the CIFAR
experiment, ACED is an average over $5$ runs. We find the curve in this
setting to be very consistent, and that the standard deviations are minimal
for visualization. All of the other curves are evaluated based on a single
run. For baselines algorithms proposed in the streaming setting (variants of
IWAL and OAC), in each round we uniformly sample an example from the pool, and
feed a fixed number of passes. We select the best $C_{0}$ based on which
hyperparameter setting takes the least amount of queries to reach the same
level of accuracy. Detailed hyperparameters considered for the baselines are
included in Appendix M. Furthermore, to demonstrate active gains in
generalization, we include plots on holdout test sets in Appendix N.

On all four datasets, our algorithm outperforms other baselines by taking much
fewer queries to reach the passive accuracy on the entire dataset. Sometimes
the active learning algorithms even beat the passive accuracy on the whole
dataset, which is a known phenomenon of active learning studied by Mussmann &
Liang (2018). For the MNIST dataset, we do not include performance curves for
the oracular variants of IWAL, since the Vowpal Wabbit implementation turns
out to be performing at random chance. We also notice that OAC stops taking
queries very early on (no longer making queries when given more passes over
the pool). However, when increasing $C_{0}$, the aggressiveness to make a
query, OAC starts performing worst than passive pretty easily. We include
Figure 9 in the appendix to demonstrate how sensitive the OAC curves are to
the hyperparameter $C_{0}$, which one cannot tune in real applications.

As a special case, on the FashionMNIST dataset, our binary classification task
is linearly separable and the baseline methods fail miserably. For all of the
IWAL algorithms on this dataset, we searched in an extended range of
hyperparameters than the ones used in the other three tasks. When fixing the
random order of the stream, however, all of the baselines become equivalent,
and perform almost identical to passive. Since in practice, only one set of
hyperparameters can be deployed, this again demonstrates the shortcoming of
these baseline algorithms, whereas our method does not rely on any
aggressiveness hyperparameter.

##  6 Related Work and Discussion

Active Classification: Active classification has received much attention with
a large number of theoretical and empirical works (see (Hanneke et al., 2014)
and (Settles, 2011) for excellent surveys). Cohn et al. (1994) initiated
research into the study of disagreement based active classification
algorithms, proposing CAL for the realizable setting. Balcan et al. (2009)
extended disagreement-based active classification to the agnostic case,
introducing the method, $A^{2}$. Hanneke (2007) provided a general analysis of
$A^{2}$ in terms of the disagreement coefficient, with follow-up works
improving on the sample complexity of this approach (Dasgupta et al., 2007;
Hanneke, 2009; Hanneke et al., 2011; Koltchinskii, 2010; Hanneke et al.,
2014). The results in Section 2.2 show that our sample complexities are never
worse than the ones obtained by this line of work.

An extension of this line of work has aimed to attain similar sample
complexities, while leveraging an empirical risk minimization oracle to design
more practical algorithms (Dasgupta et al., 2007; Hsu, 2010; Beygelzimer et
al., 2010; Huang et al., 2015). With the exception of Huang et al. (2015),
these methods tend to have a conservative query policy that samples uniformly
in the disagreement region, leading to an onerous label requirement. While
Huang et al. (2015) has a more aggressive query policy that does not sample
uniformly in the disagreement region, their sample complexity result could
also be obtained by sampling uniformly in the disagreement region and,
therefore, their theoretical result does not reflect gains from a careful
selection of points in the disagreement region. In particular, the dominant
term is still the disagreement coefficient and, hence, it can be much worse
than our sample complexity on instances such as the one in Proposition 3.

Recently, Jain & Jamieson (2019) showed that active classification in the
pool-based setting is an instance of combinatorial bandits, an observation
that is central to our analysis. They provided the first analysis that shows
the contribution of each example to the sample complexity providing a more
fine-grained result than the disagreement coefficient. We improve on this work
by optimizing the sampling distribution in the region of disagreement and
using improved estimators such as the one in Theorem 1. Proposition 4 of Katz-
Samuels et al. (2020) implies that our sample complexity is always better than
the sample complexity in Jain & Jamieson (2019).

Linear and Combinatorial Bandits. $\rho^{*}$ has been shown to be the dominant
term in a lower bound for pure exploration linear bandits and combinatorial
bandits (Soare et al., 2014; Chen et al., 2017; Fiez et al., 2019). Recently
Katz-Samuels et al. (2020) introduced the notion of $\gamma^{*}$ for linear
and combinatorial bandits, showing that it is a lower bound for any non-
interactive oracle MLE algorithm. One of our contributions is making the
connection between the active classification and linear/combinatorial bandit
literature, and showing that we can leverage the results from this work to
obtain improved sample complexities for agnostic active classification.

## References

  * Agarwal et al. (2014) Agarwal, A., Chapelle, O., Dudík, M., and Langford, J.  A reliable effective terascale linear learning system.  _The Journal of Machine Learning Research_ , 15(1):1111–1133, 2014.
  * Agarwal et al. (2018) Agarwal, A., Beygelzimer, A., Dudík, M., Langford, J., and Wallach, H.  A reductions approach to fair classification.  In _International Conference on Machine Learning_ , pp. 60–69. PMLR, 2018.
  * Balcan et al. (2009) Balcan, M.-F., Beygelzimer, A., and Langford, J.  Agnostic active learning.  _Journal of Computer and System Sciences_ , 75(1):78–89, 2009.
  * Bartlett & Mendelson (2002) Bartlett, P. L. and Mendelson, S.  Rademacher and gaussian complexities: Risk bounds and structural results.  _Journal of Machine Learning Research_ , 3(Nov):463–482, 2002.
  * Beygelzimer et al. (2009) Beygelzimer, A., Dasgupta, S., and Langford, J.  Importance weighted active learning.  In _Proceedings of the 26th annual international conference on machine learning_ , pp. 49–56, 2009.
  * Beygelzimer et al. (2010) Beygelzimer, A., Hsu, D. J., Langford, J., and Zhang, T.  Agnostic active learning without constraints.  In _Advances in neural information processing systems_ , pp. 199–207, 2010.
  * Boucheron et al. (2005) Boucheron, S., Bousquet, O., and Lugosi, G.  Theory of classification: A survey of some recent advances.  _ESAIM: probability and statistics_ , 9:323–375, 2005.
  * Cao & Krishnamurthy (2019) Cao, T. and Krishnamurthy, A.  Disagreement-based combinatorial pure exploration: Sample complexity bounds and an efficient algorithm.  In _Conference on Learning Theory_ , pp. 558–588, 2019.
  * Castro & Nowak (2008) Castro, R. M. and Nowak, R. D.  Minimax bounds for active learning.  _IEEE Transactions on Information Theory_ , 54(5):2339–2353, 2008.
  * Chen et al. (2017) Chen, L., Gupta, A., Li, J., Qiao, M., and Wang, R.  Nearly optimal sampling algorithms for combinatorial pure exploration.  In _Conference on Learning Theory_ , pp. 482–534, 2017.
  * Cohn et al. (1994) Cohn, D., Atlas, L., and Ladner, R.  Improving generalization with active learning.  _Machine learning_ , 15(2):201–221, 1994.
  * Dasgupta et al. (2007) Dasgupta, S., Hsu, D. J., and Monteleoni, C.  A general agnostic active learning algorithm.  _Advances in neural information processing systems_ , 20:353–360, 2007.
  * Fiez et al. (2019) Fiez, T., Jain, L., Jamieson, K. G., and Ratliff, L.  Sequential experimental design for transductive linear bandits.  In _Advances in Neural Information Processing Systems_ , pp. 10666–10676, 2019.
  * Hanneke (2007) Hanneke, S.  A bound on the label complexity of agnostic active learning.  In _Proceedings of the 24th international conference on Machine learning_ , pp. 353–360, 2007.
  * Hanneke (2009) Hanneke, S.  Adaptive rates of convergence in active learning.  In _COLT_. Citeseer, 2009.
  * Hanneke et al. (2011) Hanneke, S. et al.  Rates of convergence in active learning.  _The Annals of Statistics_ , 39(1):333–361, 2011\.
  * Hanneke et al. (2014) Hanneke, S. et al.  Theory of disagreement-based active learning.  _Foundations and Trends® in Machine Learning_ , 7(2-3):131–309, 2014.
  * Hsu (2010) Hsu, D. J.  _Algorithms for active learning_.  PhD thesis, UC San Diego, 2010.
  * Huang et al. (2015) Huang, T.-K., Agarwal, A., Hsu, D. J., Langford, J., and Schapire, R. E.  Efficient and parsimonious agnostic active learning.  In _Advances in Neural Information Processing Systems_ , pp. 2755–2763, 2015.
  * Jain & Jamieson (2019) Jain, L. and Jamieson, K. G.  A new perspective on pool-based active classification and false-discovery control.  In _Advances in Neural Information Processing Systems_ , pp. 13992–14003, 2019.
  * Karampatziakis & Langford (2010) Karampatziakis, N. and Langford, J.  Online importance weight aware updates.  _arXiv preprint arXiv:1011.1576_ , 2010.
  * Katz-Samuels et al. (2020) Katz-Samuels, J., Jain, L., Karnin, Z., and Jamieson, K.  An empirical process approach to the union bound: Practical algorithms for combinatorial and linear bandits.  _arXiv preprint arXiv:2006.11685_ , 2020.
  * Koltchinskii (2010) Koltchinskii, V.  Rademacher complexities and bounding the excess risk in active learning.  _The Journal of Machine Learning Research_ , 11:2457–2485, 2010.
  * LeCun et al. (1998) LeCun, Y., Bottou, L., Bengio, Y., and Haffner, P.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278–2324, 1998.
  * Ledoux (2001) Ledoux, M.  _The Concentration of Measure Phenomenon_.  Mathematical surveys and monographs. American Mathematical Society, 2001\.  ISBN 9780821837924.  URL https://books.google.com/books?id=mCX_cWL6rqwC.
  * Mussmann & Liang (2018) Mussmann, S. and Liang, P.  Uncertainty sampling is preconditioned stochastic gradient descent on zero-one loss.  _arXiv preprint arXiv:1812.01815_ , 2018.
  * Netzer et al. (2011) Netzer, Y., Wang, T., Coates, A., Bissacco, A., Wu, B., and Ng, A. Y.  Reading digits in natural images with unsupervised feature learning.  2011\.
  * Pedregosa et al. (2011) Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., and Duchesnay, E.  Scikit-learn: Machine learning in Python.  _Journal of Machine Learning Research_ , 12:2825–2830, 2011\.
  * Settles (2011) Settles, B.  From theories to queries: Active learning in practice.  In _Active Learning and Experimental Design workshop In conjunction with AISTATS 2010_ , pp. 1–18, 2011.
  * Soare et al. (2014) Soare, M., Lazaric, A., and Munos, R.  Best-arm identification in linear bandits.  In _Advances in Neural Information Processing Systems_ , pp. 828–836, 2014.
  * Talagrand (2014) Talagrand, M.  _Upper and lower bounds for stochastic processes: modern methods and classical problems_ , volume 60.  Springer Science & Business Media, 2014.
  * Vershynin (2019) Vershynin, R.  _High-Dimensional Probability_.  2019\.
  * Xiao et al. (2017) Xiao, H., Rasul, K., and Vollgraf, R.  Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms.  _arXiv preprint arXiv:1708.07747_ , 2017.

###### Contents

  1. 1 Introduction
    1. 1.1 Preliminaries
    2. 1.2 Main contributions
  2. 2 Experimental Design for Active Classification
    1. 2.1 Sidestepping the Naive Union Bound
    2. 2.2 Comparison with the Disagreement Coefficient
  3. 3 Fixed Confidence Algorithm
  4. 4 Fixed Budget Algorithm
    1. 4.1 Discussion of Theorem 1
    2. 4.2 Computationally Efficient Experimental Design
  5. 5 Implementation and Experiments
  6. 6 Related Work and Discussion
  7. A Generalization
  8. B Reduction to Combinatorial Bandits
  9. C Disagreement Coefficient
  10. D Ridge IPS Estimator Tail Bound
  11. E Looseness of Bernstein’s Bound for Importance Sampling Estimator
  12. F Proof of Theorem 1
  13. G Fixed Confidence Algorithms
  14. H Fixed Budget Proof
    1. H.1 Technical Lemmas
  15. I Efficient Fixed Budget Algorithm
    1. I.1 Lemmas
  16. J Thresholds
  17. K Implementation Details
    1. K.1 Optimization
      1. K.1.1 Mirror Descent
      2. K.1.2 Line Search
    2. K.2 Sampling
    3. K.3 Batched IWAL
  18. L Full Scale Plots for Performances on the Pool
  19. M Hyperparameters for Baselines
  20. N Generalization Performance on Holdout Set

##  Appendix A Generalization

###### Proof of Remark 1.

Define the event

$\displaystyle\mathcal{E}:=\\{\forall
h\in\mathcal{H}:|\operatorname*{\text{err}}(h)-\mathbb{P}(h(x)\neq f(x))|\leq
c[\sqrt{\frac{\ln(1/\delta)}{n}}+\sqrt{\frac{d}{n}}]\\}.$

where the randomness is over the draw of the pool
$\\{x_{1},\ldots,x_{n}\\}\sim\mathcal{D}_{\mathcal{X}}$. Using the bounded
differences inequality and 3.4 in (Boucheron et al., 2005), we have by a
standard argument that $\mathbb{P}(\mathcal{E})\geq 1-\delta$. Suppose
$\mathcal{E}$ holds for the remainder of the proof. Let
$\bar{h}=\operatorname*{arg\,min}_{h\in\mathcal{H}}\mathbb{P}_{(x,y)\sim\mathcal{D}}(h(x)\neq
f(x))$. Then,

$\displaystyle\mathbb{P}(\widehat{h}(x)\neq f(x))$
$\displaystyle\leq\operatorname*{\text{err}}(\widehat{h})+c[\sqrt{\frac{\ln(1/\delta)}{n}}+\sqrt{\frac{d}{n}}]$
$\displaystyle\leq\min_{h\in\mathcal{H}}\operatorname*{\text{err}}(h)+\epsilon+c[\sqrt{\frac{\ln(1/\delta)}{n}}+\sqrt{\frac{d}{n}}]$
$\displaystyle\leq\operatorname*{\text{err}}(\bar{h})+\epsilon+c[\sqrt{\frac{\ln(1/\delta)}{n}}+\sqrt{\frac{d}{n}}]$
$\displaystyle\leq\mathbb{P}(\bar{h}(x)\neq
f(x))+\epsilon+2c[\sqrt{\frac{\ln(1/\delta)}{n}}+\sqrt{\frac{d}{n}}].$

∎

##  Appendix B Reduction to Combinatorial Bandits

We state and prove our results for active classification in the language of
combinatorial bandits, a strictly more general problem, which we now
introduce.

Combinatorial Bandits: There are $n$ distributions $\nu_{1},\ldots,\nu_{n}$
supported on $[-1,1]$ with mean
$\mu_{i}=\mathbb{E}_{{\zeta}\sim\nu_{i}}{\zeta}$. $\mathcal{H}$ is a
collection of subsets of $[n]$. At each round $t$, the agent queries a
distribution $I_{t}$ and observes $y_{t}\sim\nu_{I_{t}}$. Given
$\epsilon>0,\delta\in(0,1)$, the goal is to identify $h\in\mathcal{H}$ that
satisfies

$\displaystyle\sum_{i\in h}\mu_{i}\geq\sum_{i\in h^{*}}\mu_{i}-\epsilon$

with probability at least $1-\delta$ using as few samples as possible.

We also write $\mu:=(\mu_{1},\ldots,\mu_{n})^{\top}$. We interchangely treat
each $h\in\mathcal{H}$ as a set in $[n]$ or as a vector in $\\{0,1\\}^{n}$
with $h_{i}=1$ if $i\in h$ and $h_{i}=0$ otherwise. Using this vector
notation, we often write $h^{\top}\mu=\sum_{i\in h}\mu_{i}$.

Reduction to combinatorial bandits: We use the reduction of active
classification to combinatorial bandits from (Jain & Jamieson, 2019). Note
that

$\displaystyle\operatorname*{\text{err}}(h)$
$\displaystyle=\frac{1}{n}[\sum_{i\in[n]:h(x_{i})=0}{\operatorname*{\eta}}_{i}+\sum_{i\in[n]:h(x_{i})=1}(1-{\operatorname*{\eta}}_{i})]=\frac{1}{n}[\sum_{i\in[n]}{\operatorname*{\eta}}_{i}-\sum_{i\in[n]:h(x_{i})=1}\mu_{i}]$

where $\mu_{i}:=2{\operatorname*{\eta}}_{i}-1$. Thus, treating each
$h\in\mathcal{H}$ as a set where $i\in h$ iff $h(x_{i})=1$, we observe
$\operatorname*{arg\,min}_{h\in\mathcal{H}}\operatorname*{\text{err}}(h)=\operatorname*{arg\,max}_{h\in\mathcal{H}}\sum_{i\in
h}\mu_{i}$ and that finding a hypothesis $h$ such that

$\displaystyle\operatorname*{\text{err}}(h)-\min_{h^{\prime}\in\mathcal{H}}\operatorname*{\text{err}}(h^{\prime})\leq\epsilon$

is equivalent to finding $h$ such that $\sum_{i\in
h}\mu_{i}\geq\max_{h^{\prime}\in\mathcal{H}}\sum_{i\in
h^{\prime}}\mu_{i}-n\epsilon$. Thus, active classification can be viewed as an
instance of combinatorial bandits where each $\nu_{i}$ is a random variable
supported on $\\{-1,1\\}$ with mean $\mu_{i}=2{\operatorname*{\eta}}_{i}-1$.
Therefore, _any algorithm for $\epsilon$-good arm identification for
combinatorial bandits yields an algorithm for active binary classification in
the pool-based setting_.

##  Appendix C Disagreement Coefficient

We now introduce equivalent definitions of
$\rho^{*}(\epsilon),\gamma^{*}(\epsilon)$ and the disagreement coefficient in
the combinatorial bandit setting.

$\displaystyle\rho^{*}(\epsilon)$
$\displaystyle:=\inf_{\lambda\in\operatorname*{\mathbf{\triangle}}_{n}}\sup_{h\in\mathcal{H}\setminus\\{h^{*}\\}}\frac{\Big{\lVert}h^{*}-h\Big{\rVert}^{2}_{A(\lambda)^{-1}}}{\max(\mu^{\top}(h^{*}-h),\epsilon)^{2}}$
$\displaystyle\gamma^{*}(\epsilon)$
$\displaystyle:=\inf_{\lambda\in\operatorname*{\mathbf{\triangle}}_{n}}\mathbb{E}_{{\zeta}\sim
N(0,I)}[\sup_{h\in\mathcal{H}\setminus\\{h^{*}\\}}\frac{(h^{*}-h)^{\top}A(\lambda)^{-1/2}{\zeta}}{\max(\mu^{\top}(h^{*}-h),\epsilon)}]^{2}.$

Define the ball of radius $r$ centered at $h^{*}$

$\displaystyle B(h_{*},r)$ $\displaystyle=\\{h\in\mathcal{H}:\frac{|h\Delta
h_{*}|}{n}\leq r\\}$

and

$\displaystyle\operatorname*{\text{DIS}}(B(h_{*},r))$
$\displaystyle=\\{i:\exists h,h^{\prime}\in B(h_{*},r)\text{ s.t. }i\in
h\Delta h^{\prime}\\}.$

The disagreement coefficient is defined as

$\displaystyle\operatorname*{\theta}(\epsilon)$
$\displaystyle=\sup_{r\geq\epsilon}\frac{|\operatorname*{\text{DIS}}(B(h_{*},r))|/n}{r}$
$\displaystyle=\sup_{r\geq\epsilon}\frac{|\\{i:i\in h\Delta h^{\prime}\text{
for some }h,h^{\prime}\in\mathcal{H}\text{ s.t. }\max(|h_{*}\Delta
h|,|h_{*}\Delta h^{\prime}|)\leq nr\\}|}{nr}.$

The proof of Proposition 2 follows by a peeling argument and the application
of the following lemma.

######  Lemma 1.

Let $\epsilon\in[\frac{\Delta_{min}}{n},1]$.

  * •

Suppose the noiseless case holds, i.e.,
$\operatorname*{\eta}\in\\{0,1\\}^{n}$. If
$\epsilon\in[\frac{\Delta_{min}}{n},\nu)$, then

$\displaystyle\sup_{\xi\geq\epsilon}\min_{\lambda}\max_{h:\Delta_{h}\leq
n\xi}\frac{\Big{\lVert}h_{*}-h\Big{\rVert}_{A(\lambda)^{-1}}^{2}}{(n\xi)^{2}}\leq
9\operatorname*{\theta}(\epsilon)\frac{\nu^{2}}{\epsilon^{2}}$

and if $\epsilon\in[\nu,1]$, then

$\displaystyle\sup_{\xi\geq\epsilon}\min_{\lambda}\max_{h:\Delta_{h}\leq
n\xi}\frac{\Big{\lVert}h_{*}-h\Big{\rVert}_{A(\lambda)^{-1}}^{2}}{(n\xi)^{2}}\leq
9\operatorname*{\theta}(\epsilon).$

  * •

Suppose that the Tsabokov noise condition holds for some $a\in[1,\infty)$ and
$\alpha\in(0,1]$. Then,

$\displaystyle\min_{\lambda}\max_{h:\Delta_{h}\leq
n\epsilon}\frac{\Big{\lVert}h_{*}-h\Big{\rVert}_{A(\lambda)^{-1}}^{2}}{(n\epsilon)^{2}}\leq
ca^{2}\frac{1}{\epsilon^{2-2\alpha}}\operatorname*{\theta}(a\epsilon^{\alpha})\log(n\Delta_{min}^{-1}\vee\epsilon^{-1})$

###### Proof.

Noiseless Case: $\operatorname*{\eta}\in\\{0,1\\}^{n}$: Under the noiseless
assumption, we have that

$\displaystyle\operatorname*{\text{err}}(h)=\frac{1}{n}|\operatorname*{\eta}\Delta
h|=\frac{1}{n}[\sum_{i\in\operatorname*{\eta}\setminus h}1+\sum_{i\in
h\setminus\operatorname*{\eta}}1=\frac{1}{n}[\sum_{i\in\operatorname*{\eta}}1+\sum_{i\in
h\setminus\operatorname*{\eta}}1-\frac{1}{n}\sum_{i\in\operatorname*{\eta}\setminus
h}1]=\frac{1}{n}|\operatorname*{\eta}|-\frac{1}{n}\sum_{i\in h}\mu_{i}.$ (7)

Recall $\nu=\operatorname*{\text{err}}(h^{*})$.

Fix $\xi\geq\epsilon$. Suppose $\Delta_{h}\leq n\xi$. We have by (7)
$\frac{1}{n}\sum_{i\in
h}\mu_{i}=\frac{1}{n}|\operatorname*{\eta}|-\frac{1}{n}|\operatorname*{\eta}\Delta
h|$ and thus

$\displaystyle n\xi\geq\Delta_{h}=|\operatorname*{\eta}\Delta
h|-|\operatorname*{\eta}\Delta h_{*}|=|\operatorname*{\eta}\Delta h|-n\nu$

and thus $|\operatorname*{\eta}\Delta h|\leq n(\xi+\nu)$. Thus, if
$\Delta_{h}\leq n\xi$, we have that

$\displaystyle|h_{*}\Delta
h|\leq|h_{*}\Delta\operatorname*{\eta}|+|h\Delta\operatorname*{\eta}|\leq
n(2\nu+\xi)$ (8)

Furthermore, by (8)

$\displaystyle\min_{\lambda}\max_{h:\Delta_{h}\leq
n\xi}\frac{\Big{\lVert}h_{*}-h\Big{\rVert}_{A(\lambda)^{-1}}^{2}}{(n\xi)^{2}}$
$\displaystyle=\min_{\lambda}\max_{h:\Delta_{h}\leq n\xi}\frac{\sum_{i\in
h_{*}\Delta h}\frac{1}{\lambda_{i}}}{(n\xi)^{2}}$
$\displaystyle\leq\frac{|\\{i:i\in h_{*}\Delta h\text{ for some
}h\in\mathcal{H}\text{ s.t. }\Delta_{h}\leq
n\xi\\}|\cdot\max_{h:\Delta_{h}\leq n\xi}|h_{*}\Delta h|}{(n\xi)^{2}}$
$\displaystyle\leq\frac{|\\{i:i\in h_{*}\Delta h\text{ for some
}h\in\mathcal{H}\text{ s.t. }|h_{*}\Delta h|\leq n(2\nu+\xi)\\}|\cdot
n(2\nu+\xi)}{(n\xi)^{2}}.$ (9)

where the first inequality takes $\lambda$ to be the uniform distribution over
$|\\{i:i\in h_{*}\Delta h\text{ for some }h\in\mathcal{H}\text{ s.t.
}\Delta_{h}\leq n\xi\\}|$.

Suppose $\epsilon\geq\nu$. Then, $\xi\geq\epsilon\geq\nu$, and we have

$\displaystyle\frac{|\\{i:i\in h_{*}\Delta h\text{ for some
}h\in\mathcal{H}\text{ s.t. }|h_{*}\Delta h|\leq
n(2\nu+\xi)\\}|n(2\nu+\xi)}{(n\xi)^{2}}$ $\displaystyle\leq 3\frac{|\\{i:i\in
h_{*}\Delta h\text{ for some }h\in\mathcal{H}\text{ s.t. }|h_{*}\Delta h|\leq
3n\xi)\\}|}{n\xi}$ $\displaystyle=9\frac{|\\{i:i\in h_{*}\Delta h\text{ for
some }h\in\mathcal{H}\text{ s.t. }|h_{*}\Delta h|\leq 3n\xi)\\}|}{3n\xi}$

and, using (9) in addition,

$\displaystyle\sup_{\xi\geq\epsilon}\min_{\lambda}\max_{h:\Delta_{h}\leq
n\xi}\frac{\Big{\lVert}h_{*}-h\Big{\rVert}_{A(\lambda)^{-1}}^{2}}{(n\xi)^{2}}$
$\displaystyle\leq\sup_{\xi\geq\epsilon}9\frac{|\\{i:i\in h_{*}\Delta h\text{
for some }h\in\mathcal{H}\text{ s.t. }|h_{*}\Delta h|\leq 3n\xi)\\}|}{3n\xi}$
$\displaystyle\leq 9\operatorname*{\theta}(3\epsilon)$ $\displaystyle\leq
9\operatorname*{\theta}(\epsilon).$

Now, suppose $\epsilon\in[\frac{\Delta_{min}}{n},\nu]$. Suppose
$\xi\geq\epsilon$ satisfies $\xi\in[\frac{\Delta_{min}}{n},\nu]$. Then,

$\displaystyle\frac{|\\{i:i\in h_{*}\Delta h\text{ for some
}h\in\mathcal{H}\text{ s.t. }|h_{*}\Delta h|\leq
n(2\nu+\xi)\\}|n(2\nu+\xi)}{(n\xi)^{2}}$ $\displaystyle=\frac{|\\{i:i\in
h_{*}\Delta h\text{ for some }h\in\mathcal{H}\text{ s.t. }|h_{*}\Delta h|\leq
n(2\nu+\xi)\\}|n(2\nu+\xi)}{(n\nu)^{2}}\frac{\nu^{2}}{\xi^{2}}$
$\displaystyle\leq 3\frac{|\\{i:i\in h_{*}\Delta h\text{ for some
}h\in\mathcal{H}\text{ s.t. }|h_{*}\Delta h|\leq
3n\nu)\\}|}{n\nu}\frac{\nu^{2}}{\xi^{2}}$ $\displaystyle\leq 9\frac{|\\{i:i\in
h_{*}\Delta h\text{ for some }h\in\mathcal{H}\text{ s.t. }|h_{*}\Delta h|\leq
3n\nu)\\}|}{3n\nu}\frac{\nu^{2}}{\xi^{2}}$ $\displaystyle\leq
9\operatorname*{\theta}(3\nu)\frac{\nu^{2}}{\xi^{2}}$ $\displaystyle\leq
9\operatorname*{\theta}(\xi)\frac{\nu^{2}}{\xi^{2}}.$

Combining this with (9), this implies that

$\displaystyle\sup_{\xi\geq\epsilon}\min_{\lambda}\max_{h:\Delta_{h}\leq
n\xi}\frac{\Big{\lVert}h_{*}-h\Big{\rVert}_{A(\lambda)^{-1}}^{2}}{(n\xi)^{2}}$
$\displaystyle\leq\sup_{\xi\geq\epsilon}\min_{\lambda}\max_{h:\Delta_{h}\leq
n\xi}\frac{\Big{\lVert}h_{*}-h\Big{\rVert}_{A(\lambda)^{-1}}^{2}}{(n\xi)^{2}}$
$\displaystyle\leq
9\operatorname*{\theta}(\epsilon)\frac{\nu^{2}}{\epsilon^{2}}.$

Case 2: Tsabakov Noise: Suppose Tsabokov’s noise condition is satisfied with
$a\in[1,\infty)$ and $\alpha\in(0,1]$. Fix $\xi\geq\epsilon$. If
$\Delta_{h}\leq n\xi$, then Tsabokov’s noise condition implies that

$\displaystyle\frac{|h^{*}\Delta h|}{n}\leq
a(\frac{\Delta_{h}}{n})^{\alpha}\leq a\xi^{\alpha}$

Then,

$\displaystyle\min_{\lambda}\max_{h:\Delta_{h}\leq
n\xi}\frac{\Big{\lVert}h^{*}-h\Big{\rVert}_{A(\lambda)^{-1}}^{2}}{(n\xi)^{2}}$
$\displaystyle=\min_{\lambda}\max_{h:\Delta_{h}\leq n\xi}\frac{\sum_{i\in
h^{*}\Delta h}\frac{1}{\lambda_{i}}}{(n\xi)^{2}}$
$\displaystyle\leq\frac{|\\{i:i\in h^{*}\Delta h\text{ for some
}h\in\mathcal{H}\text{ s.t. }\Delta_{h}\leq
n\xi\\}|\cdot\max_{h:\Delta_{h}\leq n\xi}|h^{*}\Delta h|}{(n\xi)^{2}}$
$\displaystyle\leq\frac{|\\{i:i\in h^{*}\Delta h\text{ for some
}h\in\mathcal{H}\text{ s.t. }\frac{|h_{*}\Delta h|}{n}\leq
a\xi^{\alpha}\\}|\cdot\max_{h:\Delta_{h}\leq n\xi}|h^{*}\Delta
h|}{(n\xi)^{2}}$ $\displaystyle\leq\frac{|\\{i:i\in h^{*}\Delta h\text{ for
some }h\in\mathcal{H}\text{ s.t. }\frac{|h_{*}\Delta h|}{n}\leq
a\xi^{\alpha}\\}|an\xi^{\alpha}}{(n\xi)^{2}}$
$\displaystyle=a^{2}\frac{|\\{i:i\in h^{*}\Delta h\text{ for some
}h\in\mathcal{H}\text{ s.t. }\frac{|h_{*}\Delta h|}{n}\leq
a\xi^{\alpha}\\}|}{a\xi^{\alpha}n}\frac{1}{\xi^{2-2\alpha}}$
$\displaystyle\leq
a^{2}\frac{1}{\xi^{2-2\alpha}}\operatorname*{\theta}(a\xi^{\alpha})$

Taking the sup over $\xi\geq\epsilon$ of both sides implies the result.

∎

###### Proof of Proposition 2.

The argument follows by a peeling argument. Define

$\displaystyle\lambda^{(k)}:=\min_{\lambda}\max_{h:\Delta_{h}\in(n2^{-k-1},n2^{-k}]}\frac{\Big{\lVert}h^{*}-h\Big{\rVert}_{A(\lambda)^{-1}}^{2}}{\Delta_{h}^{2}}$
$\displaystyle\bar{\lambda}:=\frac{1}{\lceil\log_{2}(n\Delta_{\min}^{-1}\vee\epsilon^{-1})\rceil}\sum_{k=0}^{\lceil\log_{2}(n\Delta_{\min}^{-1}\vee\epsilon^{-1})\rceil}\lambda^{(k)}.$

Notice that
$\frac{1}{\lceil\log_{2}(n\Delta_{\min}^{-1}\vee\epsilon^{-1})\rceil}A(\lambda^{(k)})\preceq
A(\bar{\lambda})$, which implies that

$\displaystyle
A(\bar{\lambda})^{-1}\preceq\lceil\log_{2}(n\Delta_{\min}^{-1}\vee\epsilon^{-1})\rceil
A(\lambda^{(k)})^{-1}.$ (10)

Thus,

$\displaystyle\rho^{*}(n\epsilon)$
$\displaystyle=\min_{\lambda}\max_{h\in\mathcal{H}\setminus\\{h^{*}\\}}\frac{\Big{\lVert}h^{*}-h\Big{\rVert}_{A(\lambda)^{-1}}^{2}}{\max(n\epsilon,\Delta_{h})^{2}}$
$\displaystyle\leq\max_{h\in\mathcal{H}\setminus\\{h^{*}\\}}\frac{\Big{\lVert}h^{*}-h\Big{\rVert}_{A(\bar{\lambda})^{-1}}^{2}}{\max(n\epsilon,\Delta_{h})^{2}}$
$\displaystyle=\max_{k=0,1,\dots,\lceil\log_{2}(n\Delta_{min}^{-1}\vee\epsilon^{-1})\rceil}\max_{h:\Delta_{h}\in(n2^{-k-1},n2^{-k}]}\frac{\Big{\lVert}h^{*}-h\Big{\rVert}_{A(\bar{\lambda})^{-1}}^{2}}{\max(n\epsilon,\Delta_{h})^{2}}$
$\displaystyle\leq\lceil\log_{2}(n\Delta_{\min}^{-1}\vee\epsilon^{-1})\rceil\max_{k=0,1,\dots,\lceil\log_{2}(n\Delta_{min}^{-1}\vee\epsilon^{-1})\rceil}\max_{h:\Delta_{h}\in(n2^{-k-1},n2^{-k}]}\frac{\Big{\lVert}h^{*}-h\Big{\rVert}_{A(\lambda^{(k)})^{-1}}^{2}}{\max(n\epsilon,\Delta_{h})^{2}}$
(11)
$\displaystyle=\lceil\log_{2}(n\Delta_{\min}^{-1}\vee\epsilon^{-1})\rceil\max_{k=0,1,\dots,\lceil\log_{2}(n\Delta_{min}^{-1}\vee\epsilon^{-1})\rceil}\min_{\lambda}\max_{h:\Delta_{h}\in(n2^{-k-1},n2^{-k}]}\frac{\Big{\lVert}h^{*}-h\Big{\rVert}_{A(\lambda^{(k)})^{-1}}^{2}}{\max(n\epsilon,\Delta_{h})^{2}}$
(12) $\displaystyle\leq
2\lceil\log_{2}(n\Delta_{\min}^{-1}\vee\epsilon^{-1})\rceil\sup_{\xi\geq\epsilon\vee\frac{\Delta_{min}}{n}}\min_{\lambda}\max_{h:\Delta_{h}\leq
n\xi}\frac{\Big{\lVert}h^{*}-h\Big{\rVert}_{A(\lambda)^{-1}}^{2}}{(n\xi)^{2}}$

where inequality (11) follows by (10) and (12) follows by the definition of
$\bar{\lambda}^{(k)}$.

The result now follows by applying Lemma 1 in each case (noiseless
$\operatorname*{\eta}\in\\{0,1\\}$ with $\epsilon>\nu$ and $\epsilon<\nu$, and
Tsabokov noise condition). ∎

###### Proof of Proposition 3.

Step 1: Define the instance. Let $m\in\mathbb{N}$. Define
$h_{i}=[m]\cup\\{m+i\\}$ for $i=1,\ldots,m^{2}$ and let $n=m+m^{2}$. Define
$h_{0}=\emptyset$. Let $\mu_{i}=-1$ for all $i\in[n]$. Note that $h_{0}$ is
the best set and that $\mu^{\top}(h_{0}-h_{i})=m+1$ for all $i\neq 0$.

Step 2: Compute problem-dependent quantities. We have that

$\displaystyle\rho^{*}=\inf_{\lambda}\max_{i=1,\ldots,m^{2}}\frac{\sum_{j\in[m]\cup\\{m+i\\}\frac{1}{\lambda_{j}}}}{(m+1)^{2}}\leq\frac{2m^{2}+2m^{2}}{(m+1)^{2}}\leq
O(1)$

where we used

$\displaystyle\lambda_{i}$ $\displaystyle=\begin{cases}\frac{1}{2m}&i\in[m]\\\
\frac{1}{2m^{2}}&i\in\\{m+1,\ldots,m+m^{2}\\}\end{cases}.$

Let $\xi$ such that $n\xi\leq m+1$. Letting $r=m+1$, we have that

$\displaystyle\operatorname*{\theta}(\xi)$ $\displaystyle\geq\frac{|\\{i:i\in
h_{*}\Delta h\text{ for some }h\in\mathcal{H}\text{ s.t. }|h_{*}\Delta h|\leq
r\\}|}{r}$ $\displaystyle=\frac{m+m^{2}}{m+1}$ $\displaystyle\geq\frac{1}{2}m$
$\displaystyle\geq\frac{1}{2\sqrt{2}}\sqrt{n}.$

∎

##  Appendix D Ridge IPS Estimator Tail Bound

Now, we introduce the ridge IPS estimator, which we leverage in constructing
our generic chaining estimator.

######  Proposition 5.

Fix $\mathcal{X}=\\{\mathbf{e}_{i}:i\in[n]\\}$ and
$\mathcal{H}\subset\\{0,1\\}^{n}$ as well as some $\mu\in[-1,1]^{n}$. Let
$v\in\mathbb{R}^{n}$. Fix some $\lambda\in\triangle_{n}$ and draw
$\\{x_{s}\\}_{i=1}^{t}\sim\lambda$ and then observe $y_{s}$ with mean
$x_{s}^{\top}\mu$ and $|y_{i}|\leq 1$ with probability $1$ for $s=1,\ldots,t$.

For any $\alpha\in\mathbb{R}_{+}^{n}$ define

$\displaystyle
A(\alpha):=\sum_{i=1}^{n}\alpha_{i}\mathbf{e}_{i}\mathbf{e}_{i}^{\top}$

For some $s>0$ define

$\displaystyle\widehat{\mu}$ $\displaystyle=(A(t\lambda)+sI)^{-1}X^{\top}y.$

and for any $s>0$ let $A(\alpha+s):=A(\alpha)+sI_{n}$. For some $s>0$ define

$\displaystyle\widehat{\mu}$ $\displaystyle=(A(t\lambda)+sI)^{-1}X^{\top}y$

where $X$, $y$, $\epsilon$ are the $\\{(x_{i},y_{i},\epsilon_{i})\\}_{i}$
stacked. If we take
$s=\sqrt{\frac{\log(2/\delta)}{3\|v\|_{(nA(\lambda))^{-1}}^{2}}}$ then

$\displaystyle|\langle v,\widehat{\mu}-\mu\rangle|$
$\displaystyle\leq(\sqrt{2/3}+1)\sqrt{\frac{2\|v\|_{A(\lambda)^{-1}}^{2}\log(2/\delta)}{t}}$

###### Proof of Proposition 5.

Fix $\mathcal{X}=\\{\mathbf{e}_{i}:i\in[n]\\}$ and
$\mathcal{H}\subset\\{0,1\\}^{n}$ as well as some $\mu\in[-1,1]^{n}$. Note
that for any $v\in\\{-1,0,1\\}^{n}$ we have

$\displaystyle\left|\mathbb{E}[\langle v,\widehat{\mu}-\mu\rangle]\right|$
$\displaystyle=\left|\langle
v,(A(t\lambda)+sI)^{-1}A(t\lambda)\mu-\mu\rangle\right|$
$\displaystyle=\left|\langle v,(A(t\lambda)+sI)^{-1}(A(t\lambda)+sI-
sI)\mu-\mu\rangle\right|$ $\displaystyle=\left|s\langle
v,(A(t\lambda)+sI)^{-1}\mu\rangle\right|$ $\displaystyle\leq
s\|v\|_{(tA(\lambda)+sI)^{-1}}^{2}$

using the fact that $\mu\in[-1,1]^{n}$. Define

$\displaystyle S$ $\displaystyle=\langle v,\widehat{\mu}\rangle$
$\displaystyle=\sum_{i=1}^{n}v^{\top}(A(t\lambda)+sI)^{-1}x_{i}y_{i}$
$\displaystyle=:\sum_{i=1}^{n}X_{i}$

Note that

$\displaystyle\sum_{i=1}^{n}\mathbb{E}[X_{i}^{2}]$
$\displaystyle=\sum_{i=1}^{n}\mathbb{E}[\langle
v,(A(t\lambda)+sI)^{-1}x_{i}y_{i}\rangle^{2}]$ $\displaystyle\leq
v^{\top}(A(t\lambda)+sI)^{-1}A(t\lambda)(A(t\lambda)+sI)^{-1}v$
$\displaystyle\leq\|v\|_{(nA(\lambda)+sI)^{-1}}^{2}$

and

$\displaystyle|X_{i}|\leq|\langle
v,(A(t\lambda)+sI)^{-1}x_{i}y_{i}\rangle|\leq 1/s$

for all $i$, we have by Bernstein’s inequality that

$\displaystyle\sum_{i=1}^{n}X_{i}-\mathbb{E}[X_{i}]\leq\sqrt{2\|v\|_{(nA(\lambda)+sI)^{-1}}^{2}\log(1/\delta)}+\frac{\log(1/\delta)}{3s}.$

Thus,

$\displaystyle\langle v,\widehat{\mu}\rangle$
$\displaystyle\leq\mathbb{E}[\langle
v,\widehat{\mu}\rangle]+\sqrt{2\|v\|_{(nA(\lambda)+sI)^{-1}}^{2}\log(1/\delta)}+\frac{\log(1/\delta)}{3s}$
$\displaystyle=\langle v,\mu\rangle+\mathbb{E}[\langle
v,\widehat{\mu}-\mu\rangle]+\sqrt{2\|v\|_{(nA(\lambda)+sI)^{-1}}^{2}\log(1/\delta)}+\frac{\log(1/\delta)}{3s}$
$\displaystyle\leq\langle
v,\mu\rangle+s\|v\|_{(nA(\lambda)+sI)^{-1}}^{2}+\sqrt{2\|v\|_{(nA(\lambda)+sI)^{-1}}^{2}\log(1/\delta)}+\frac{\log(1/\delta)}{3s}$

from which we conclude, that

$\displaystyle|\langle v,\widehat{\mu}-\mu\rangle|$ $\displaystyle\leq
s\|v\|_{(nA(\lambda)+sI)^{-1}}^{2}+\frac{\log(2/\delta)}{3s}+\sqrt{2\|v\|_{(nA(\lambda)+sI)^{-1}}^{2}\log(2/\delta)}$
$\displaystyle\leq
s\|v\|_{(nA(\lambda))^{-1}}^{2}+\frac{\log(2/\delta)}{3s}+\sqrt{2\|v\|_{(nA(\lambda))^{-1}}^{2}\log(2/\delta)}$

If we take $s=\sqrt{\frac{\log(2/\delta)}{3\|v\|_{(nA(\lambda))^{-1}}^{2}}}$
then

$\displaystyle|\langle v,\widehat{\mu}-\mu\rangle|$
$\displaystyle\leq(\sqrt{2/3}+1)\sqrt{\frac{2\|v\|_{A(\lambda)^{-1}}^{2}\log(2/\delta)}{n}}$

∎

##  Appendix E Looseness of Bernstein’s Bound for Importance Sampling
Estimator

A natural approach to combinatorial bandits is to use the importance sampling
estimator and apply Bernstein’s bound in an algorithm like RAGE from (Fiez et
al., 2019). Applying the standard analysis would yield a term in the sample
complexity that scales as:

$\displaystyle\inf_{\lambda}\max_{h\neq h^{*}}\max_{j\in h_{*}\Delta
h}\frac{\frac{1}{\lambda_{j}}}{\sum_{k\in h_{*}}\mu_{k}-\sum_{k\in
h}\mu_{k}}.$

The following proposition shows that there exists instances where such a
sample complexity is suboptimal by a polynomial factor in the dimension.

######  Proposition 6.

There exists a combinatorial bandit problem where $\rho^{*}=O(1)$ and

$\displaystyle\inf_{\lambda}\max_{h\neq h^{*}}\max_{j\in h^{*}\Delta
h}\frac{\frac{1}{\lambda_{j}}}{\sum_{k\in h_{*}}\mu_{k}-\sum_{k\in
h}\mu_{k}}\geq\Omega(\sqrt{n})$

###### Proof.

Step 1: Define the instance. Let $m\in\mathbb{N}$. Define
$h_{i}=[m]\cup\\{m+i\\}$ for $i=1,\ldots,m^{2}$ and let $n=m+m^{2}$. Define
$h_{0}=\emptyset$. Let $\mu_{i}=-1$ for all $i\in[n]$. Note that
$\mu^{\top}(h_{0}-h_{i})=m+1$ for all $i\neq 0$.

Step 2: Compute problem-dependent quantities. Then,

$\displaystyle\rho^{*}=\inf_{\lambda}\max_{i=1,\ldots,m^{2}}\frac{\sum_{j\in[m]\cup\\{m+i\\}\frac{1}{\lambda_{j}}}}{(m+1)^{2}}\leq\frac{2m^{2}+2m^{2}}{(m+1)^{2}}\leq
O(1)$

where we used

$\displaystyle\lambda_{i}$ $\displaystyle=\begin{cases}\frac{1}{2m}&i\in[m]\\\
\frac{1}{2m^{2}}&i\in\\{m+1,\ldots,m+m^{2}\\}\end{cases}.$

On the other hand,

$\displaystyle\inf_{\lambda}\max_{i=1,\ldots,m^{2}}\max_{j\in[m]\cup\\{m+i\\}}\frac{\frac{1}{\lambda_{j}}}{m+1}$
$\displaystyle\geq\inf_{\lambda}\max_{i=1,\ldots,m^{2}}\max_{j=m+i}\frac{\frac{1}{\lambda_{j}}}{m+1}$
$\displaystyle=\frac{m^{2}}{m+1}$ $\displaystyle\geq\frac{1}{2}m$
$\displaystyle\geq\frac{1}{2\sqrt{2}}\sqrt{n}$

∎

##  Appendix F Proof of Theorem 1

Before proving Theorem 1, we introduce some machinery from the theory of
generic chaining (see e.g. (Vershynin, 2019) for more details). Fix a set
$T\subset\mathbb{R}^{n}$. Consider a sequence of subset
$(T_{k})_{k=0}^{\infty}$ such that $T_{k}\subset T$

$\displaystyle|T_{0}|=1,\quad\quad|T_{k}|\leq 2^{2^{k}}.$

A sequence $(T_{k})_{k=0}^{\infty}$ satisfying the above properties is called
_admissible_.

######  Definition 1.

Let $d$ be a metric on $\mathbb{R}^{n}$. The $\gamma_{2}$-functional of $T$ is
defined as

$\displaystyle\gamma_{2}(T,d)$ $\displaystyle=\inf_{(T_{k})}\sup_{t\in
T}\sum_{k=0}^{\infty}2^{k/2}d(t,T_{k})$

where the infimum is taken over all admissible sequences.

Here, we state and prove Theorem 4, the combinatorial bandit counterpart of
Theorem 1. The proof uses the technique of generic chaining to avoid a naive
union bound, which would introduce a dependence on $\log(|\mathcal{G}|)$.
Unfortunately, the IPS estimator has an excessively large sub-Gaussian norm,
and the concentration inequality for ridge IPS estimator from Proposition 5
decays at a suitably fast sub-Gaussian rate for only a subset of pairs
$h,h^{\prime}\in\mathcal{G}$–not all pairs–implying that neither of these
estimators can be used directly. To sidestep this issue, we apply the
estimator from Proposition 5 to all pairs of $h,h^{\prime}\in\mathcal{G}$ to
construct a feasibility program that yields the estimator in Theorem 4.

######  Theorem 4.

Let $\mathcal{G}\subset\mathcal{H}$. Fix some $\lambda\in\triangle_{n}$ and
draw $\\{x_{s}\\}_{i=1}^{t}\sim\lambda$ and then observe $y_{s}$ with mean
$x_{s}^{\top}\mu$ and $|y_{s}|\leq 1$ with probability $1$ for $s=1,\ldots,t$.
There exists an estimator $\widehat{\mu}\in[-1,1]^{n}$ such that we have that
with probability at least $1-\delta$,

$\displaystyle\sup_{h,h^{\prime}\in\mathcal{G}}|(h-h^{\prime})^{\top}(\widehat{\mu}-\mu)|\leq
c[\log(1/\delta)\max_{h,h^{\prime}\in\mathcal{G}}\Big{\lVert}h-h^{\prime}\Big{\rVert}_{A(t\lambda)^{-1}}+\mathbb{E}_{{\zeta}\sim
N(0,I)}[\sup_{h\in\mathcal{G}}h^{\top}A(t\lambda)^{-1/2}{\zeta}]]$

###### Proof of Theorem 4.

Step 1: Pick the admissible sequence. Fix $h_{0}\in\mathcal{G}$. Note that for
any $\tilde{\mu}\in\mathbb{R}^{n}$

$\displaystyle\sup_{h,h^{\prime}\in\mathcal{G}}|(h-h^{\prime})^{\top}(\tilde{\mu}-\mu)|\leq
2\sup_{h\in\mathcal{G}}|(h-h_{0})^{\top}(\tilde{\mu}-\mu)|$ (13)

and thus we focus on upper bounding the RHS.

Let $(\mathcal{R}_{k})_{k=0}^{K}$ be an admissible sequence of $\mathcal{G}$
wrt the metric $d(x,y):=\Big{\lVert}x-y\Big{\rVert}_{A(t\lambda)^{-1}}$ where
$\mathcal{R}_{0}=\\{h_{0}\\}$ and $\mathcal{R}_{K}=\mathcal{G}$ and
$\mathcal{R}_{k}\subset\mathcal{G}$ such that

$\displaystyle\sup_{h\in\mathcal{G}}\sum_{k=1}^{K}2^{k/2}\inf_{h^{\prime}\in{\mathcal{R}}_{k}}\Big{\lVert}h-h^{\prime}\Big{\rVert}_{A(t\lambda)^{-1}}$
$\displaystyle\leq
2\gamma(\mathcal{G},\Big{\lVert}\cdot\Big{\rVert}_{A(t\lambda)^{-1}})$

Let $\mathcal{T}_{k}=\cup_{l=1}^{k}\mathcal{R}_{l}$. Note that
$\mathcal{T}_{1}\subset\mathcal{T}_{2}\subset\ldots\subset\mathcal{T}_{K}$ and
$K=\log(\log(|\mathcal{G}|))\leq\log(n)$.

Step 2: Constructing the estimator. Let $X$, and $y$ be the
$\\{(x_{s},y_{s})\\}_{s=1}^{t}$ stacked, respectively. For each
$h,h^{\prime}\in\mathcal{G}$ and $k\in[K]$ such that
$h,h^{\prime}\in\mathcal{T}_{k}$, define the estimator

$\displaystyle\widehat{\mu}_{h,h^{\prime},k}=(A(t\lambda)+s_{h,h^{\prime},k}I)^{-1}X^{\top}y$

where
$s_{h,h^{\prime},k}=\sqrt{1/3}\frac{u+2^{k/2}}{\Big{\lVert}h-h^{\prime}\Big{\rVert}_{A(t\lambda)^{-1}}}$.
Define the events

$\displaystyle\mathcal{E}_{h,h^{\prime},k}$
$\displaystyle=\\{|(h-h^{\prime})^{\top}(\widehat{\mu}_{h,h^{\prime},k}-\mu)|\leq(\sqrt{2/3}+1)\sqrt{4}(u+2^{k/2})\Big{\lVert}h-h^{\prime}\Big{\rVert}_{A(t\lambda)^{-1}}\\}$
(14) $\displaystyle\mathcal{E}$
$\displaystyle=\cap_{k=1}^{K}\cap_{h,h^{\prime}\in\mathcal{T}_{k}}\mathcal{E}_{h,h^{\prime},k}$
(15)

Applying the bound for the Ridge IPS from Proposition 5 and rearranging, for
every $k\in[K]$ and $h,h^{\prime}\mathcal{T}_{k}$,

$\displaystyle\Pr(|(h-h^{\prime})^{\top}(\widehat{\mu}_{h,h^{\prime},k}-\mu)|>(\sqrt{2/3}+1)\sqrt{4}(u+2^{k/2})\Big{\lVert}h-h^{\prime}\Big{\rVert}_{A(t\lambda)^{-1}})$
$\displaystyle\leq 2\exp(-2(u+2^{k/2})^{2}).$ (16)

Then, by the union bound, we have that

$\displaystyle\Pr(\mathcal{E}^{c})$ $\displaystyle\leq\sum_{k\geq
1}|\mathcal{T}_{k}|^{2}\Pr(\mathcal{E}_{h,h^{\prime},k}^{c})$
$\displaystyle\leq c\sum_{k\geq 1}|\mathcal{T}_{k}|^{2}\exp(-2(2^{k}+u^{2}))$
(17) $\displaystyle\leq c\sum_{k\geq 1}2^{2^{k}+1}\exp(-2(2^{k}+u^{2}))$ (18)
$\displaystyle\leq c^{\prime}\exp(-2u^{2}).$

where (17) follows by (16) and where line (18) follows since by construction

$\displaystyle|\mathcal{T}_{k}|\leq\sum_{l=1}^{k}|\mathcal{R}_{k}|\leq\sum_{l=1}^{k}2^{2^{l}}\leq
2^{2^{k}+1}.$

Suppose $\mathcal{E}$ holds for the remainder of the proof with $u$ taking the
value of $\bar{u}=\sqrt{\tfrac{\log(c^{\prime}/\delta)}{2}}$.

Define the polyhedron

$\displaystyle\widehat{\mu}\in P=\\{z\in[-1,1]^{n}:\forall k\in[K],\forall
h,h^{\prime}\in\mathcal{T}_{k}:\,\,|(h-h^{\prime})^{\top}\widehat{\mu}_{h,h^{\prime},k}-z)|\leq
c[\bar{u}+2^{k/2}]\Big{\lVert}h-h^{\prime}\Big{\rVert}_{A(t\lambda)^{-1}}\\}.$

We define the estimator $\widehat{\mu}$ to be any point in $P$ if it is
nonempty and, otherwise we let $\widehat{\mu}$ be any point in
$\mathbb{R}^{n}$.

Note that on the event $\mathcal{E}$, $\mu\in P$ and hence $P$ is nonempty.
Furthermore, by the triangle inequality, $\forall k\in[K],\forall
h,h^{\prime}\in\mathcal{T}_{k}$

$\displaystyle|(h-h^{\prime})^{\top}(\widehat{\mu}-\mu)|$
$\displaystyle\leq|(h-h^{\prime})^{\top}(\widehat{\mu}-\widehat{\mu}_{h,h^{\prime},k})|+|(h-h^{\prime})^{\top}(\widehat{\mu}_{h,h^{\prime},k}-\mu)|$
$\displaystyle\leq
2c(\bar{u}+2^{k/2})\Big{\lVert}h-h^{\prime}\Big{\rVert}_{A(t\lambda)^{-1}}.$

Step 3: Proving the inequality. Fix $\bar{h}\in\mathcal{G}$. Let
$k(\bar{h},l)$ be the smallest integer such that

$\displaystyle
d(\bar{h},\mathcal{T}_{k(\bar{h},l)})\leq\frac{d(\bar{h},\mathcal{T}_{k(\bar{h},l-1)})}{2}.$

Note that

$\displaystyle d(\bar{h},\mathcal{T}_{k(\bar{h},l)})\leq
2^{-l}\max_{h,h^{\prime}\in\mathcal{G}}\Big{\lVert}h-h^{\prime}\Big{\rVert}_{A(t\lambda)^{-1}}.$

Let $\pi_{l}(\bar{h})\in\mathcal{T}_{k(\bar{h},l)}$ such that

$\displaystyle\Big{\lVert}\bar{h}-\pi_{l}(\bar{h})\Big{\rVert}_{A(t\lambda)^{-1}}=\min_{h\in\mathcal{T}_{k(\bar{h},l)}}\Big{\lVert}\bar{h}-h\Big{\rVert}_{A(t\lambda)^{-1}}.$

By the triangle inequality

$\displaystyle|(\bar{h}-h_{0})^{\top}(\widehat{\mu}-\mu)|\leq\sum_{l\geq
1}|(\pi_{l}(\bar{h})-\pi_{l-1}(\bar{h}))^{\top}(\widehat{\mu}-\mu)|$
$\displaystyle\leq 2c\sum_{l\geq
1}(\bar{u}+2^{k/2})\Big{\lVert}\pi_{l}(\bar{h})-\pi_{l-1}(\bar{h})\Big{\rVert}_{A(t\lambda)^{-1}}$
$\displaystyle\leq c^{\prime}\sum_{l\geq
1}(\bar{u}+2^{k/2})\Big{\lVert}\pi_{l}(\bar{h})-\bar{h}\Big{\rVert}_{A(t\lambda)^{-1}}$
(19)

where we use event $\mathcal{E}$ and the triangle inequality. We have by
construction that

$\displaystyle\sum_{l\geq
1}\bar{u}\Big{\lVert}\pi_{l}(\bar{h})-\bar{h}\Big{\rVert}_{A(t\lambda)^{-1}}$
$\displaystyle\leq\sum_{l\geq
1}2^{-l}\max_{h,h^{\prime}\in\mathcal{G}}\Big{\lVert}h-h^{\prime}\Big{\rVert}_{A(t\lambda)^{-1}}$
$\displaystyle\leq
c^{\prime}\bar{u}\max_{h,h^{\prime}\in\mathcal{G}}\Big{\lVert}h-h^{\prime}\Big{\rVert}_{A(t\lambda)^{-1}}.$
(20)

Furthermore,

$\displaystyle\sum_{l\geq
1}2^{k/2}\Big{\lVert}\pi_{l}(\bar{h})-\bar{h}\Big{\rVert}_{A(t\lambda)^{-1}}$
$\displaystyle\leq
c^{\prime}\gamma(\mathcal{G},\Big{\lVert}\cdot\Big{\rVert}_{A(t\lambda)^{-1}})$
(21) $\displaystyle\leq c^{\prime\prime}\mathbb{E}_{{\zeta}\sim
N(0,I)}[\sup_{h\in\mathcal{G}}h^{\top}A(t\lambda)^{-1/2}{\zeta}]$ (22)

where (21) follows by the definition of $\mathcal{T}_{k}$ and (22) follows by
Talagrand’s majorizing measure theorem (Theorem 8.6.1 in (Vershynin, 2019)).
Putting together (13), (19), (20), and (22), and noting that $\bar{h}$ is
arbitrary, the result follows.

∎

######  Remark 3.

We emphasize that the construction of this estimator does not use any
knowledge of $\mu$. The admissible sequence
$(\mathcal{R}_{k})_{k\in\mathbb{N}}$ does not require knowledge of $\mu$ to be
chosen and the polyhedron $P$ can be defined without knowledge of $\mu$.

##  Appendix G Fixed Confidence Algorithms

We restate Algorithm 1 in the language of combinatorial bandits.

Input:  Confidence level $\delta\in(0,1)$.

$\mathcal{H}_{1}\longleftarrow\mathcal{H}$, $k\longleftarrow 1$,
$\delta_{k}\longleftarrow\delta/2k^{2}$.

while $|\mathcal{H}_{k}|>1$ do

Let $\lambda_{k}$ and $\tau_{k}$ be the solution and value of the following
optimization problem
$\displaystyle\inf_{\lambda\in\operatorname*{\mathbf{\triangle}}_{n}}\mathbb{E}_{{\zeta}\sim
N(0,I)}[\max_{h,h^{\prime}\in\mathcal{H}_{k}}(h-h^{\prime})^{\top}A(\lambda)^{-1/2}{\zeta}]^{2}+2\log(\frac{1}{\delta_{k}})\max_{h,h^{\prime}\in\mathcal{H}_{k}}\Big{\lVert}h-h^{\prime}\Big{\rVert}^{2}_{A(\lambda)^{-1}}$

Set $N_{k}\longleftarrow c\tau_{k}(\frac{2^{k+1}}{n})^{2}$ where $c$ is a
universal constant.

Query $I_{1},\ldots,I_{N_{k}}\sim\lambda_{k}$ and receive rewards
$y_{1},\ldots,y_{N_{k}}$.

Let $\widehat{\mu}_{k}$ be the estimator defined in Theorem 4.

$\mathcal{H}_{k+1}\longleftarrow\mathcal{H}_{k}\setminus\\{h\in\mathcal{H}_{k}:\exists
h^{\prime}\text{ such that
}(h^{\prime}-h)^{\top}\widehat{\mu}_{k}-\frac{n}{2^{k+1}}\geq 0\\}$.

$k\longleftarrow k+1$

end while

Return:  $\mathcal{H}_{k}=\\{\widehat{h}\\}$.

Algorithm 3 ACED for Combinatorial Bandits.

We now restate Theorem 2 as Theorem 5 in the combinatorial bandits setting.

######  Theorem 5.

Let $\delta\in(0,1)$ and $\epsilon>0$. With probability at least $1-\delta$
Algorithm 1 returns $h\in\mathcal{H}$ such that
$\mu^{\top}\widehat{h}+\epsilon<\mu^{\top}h^{*}$ and uses at most

$\displaystyle\log(1/\epsilon)[\log(1/\delta)\rho^{*}(\epsilon)+\gamma^{*}(\epsilon)]$

The proof of Theorem 5 is essentially identical to the proof of Theorem 4 in
(Katz-Samuels et al., 2020), and we therefore omit it. The key technical
technical hurdle in obtaining Theorem 5 is the estimator given in Theorem 4.

##  Appendix H Fixed Budget Proof

We restate the fixed budget algorithm, Algorithm 2, and the Theorem 3in the
language of combinatorial bandits as Algorithm 4 and Theorem 6, respectively.

Input: Budget $T$, tolerance $\epsilon>0$.

$\widehat{\mu}_{1}=\bm{0}\in\mathbb{R}^{n}$,
$N\longleftarrow\Big{\lfloor}T/\log_{2}(n\epsilon^{-1})\Big{\rfloor}$.

for $k=1,2,\ldots,\Big{\lfloor}\log_{2}(n\epsilon^{-1})\Big{\rfloor}$ do

$\tilde{h}_{k}\longleftarrow\operatorname*{arg\,max}_{h\in\mathcal{H}}\widehat{\mu}_{k}^{\top}h$

Let $\lambda_{k}$ be the solution of the following optimization problem
$\displaystyle\inf_{\lambda\in\operatorname*{\mathbf{\triangle}}}\mathbb{E}_{{\zeta}\sim
N(0,I)}[\max_{h\in\mathcal{H}}\frac{(\tilde{h}_{k}-h)^{\top}A(\lambda)^{-1/2}{\zeta}}{2^{-k+1}n+\widehat{\mu}^{\top}_{k}(\tilde{h}_{k}-h)}]^{2}$
(23)

Sample $\\{x_{1},\ldots,x_{N}\\}\sim\lambda_{k}$.

Query $x_{1},\ldots,x_{N}$ and receive rewards $y_{1},\ldots,y_{N}$.

Let $\widehat{\mu}_{k+1}$ be the estimator defined in the proof of Theorem 6.

end for

Return:
$\operatorname*{arg\,max}_{h\in\mathcal{H}}\widehat{\mu}_{k+1}^{\top}h$.

Algorithm 4 Fixed Budget ACED for Combinatorial Bandits.

######  Theorem 6.

Let $T\in\mathbb{N}$ and $\epsilon>0$. Let $\widehat{h}$ denote the
$h\in\mathcal{H}$ returned by Algorithm 2. If
$T\geq\log(n\epsilon^{-1})[\gamma^{*}(\epsilon)+\rho^{*}(\epsilon)]$, then

$\displaystyle\mathbb{P}(\mu^{\top}\widehat{h}+\epsilon<\mu^{\top}h^{*})\leq\log(n\epsilon^{-1})\exp(-\frac{T}{\log(n\epsilon^{-1})[\gamma^{*}(\epsilon)+\rho^{*}(\epsilon)]})$

The key technical challenge in the proof (see Step 1) is constructing an
estimator that concentrates rapidly enough. To this end, we leverage the
estimator in Theorem 4, applying it to various subsets of $\mathcal{H}$ based
on their estimated gaps and combine them into a single estimator by defining
it to belong to a polyhedron (denoted $P$ in step 1.2.2) characterizing
estimators with the suitable concentration properties. We argue that on a good
event, the true mean $\mu$ belongs to $P$, making it feasible and thus
obtaining our estimator. The next challenge is bounding the probability of
error of our algorithm. The estimator constructed at round $k+1$ is chosen to
have failure probability

$\displaystyle\delta_{k+1}=\exp(-c\frac{N}{\mathbb{E}[\sup_{h\in\mathcal{H}}\frac{(\widetilde{h}_{k}-h)^{\top}A(\lambda)^{-1/2}{\zeta}}{(\widetilde{h}_{k}-h)^{\top}\widehat{\mu}_{k}+2^{-k+1}n}]^{2}}),$

for a suitably large universal constant $c>0$, which we note is a function of
(23). Thus, this step of the proof (step 3) shows that
$\delta_{k+1}\leq\exp(-\frac{T}{\log(n\epsilon^{-1})[\gamma^{*}(\epsilon)+\rho^{*}(\epsilon)]})$.
We note that while this step of the proof and algorithm style are novel to our
knowledge, the mechanics of bounding the various quantities appearing in this
step are quite similar to arguments in (Katz-Samuels et al., 2020).

###### Proof of Theorem 6.

Step 1: Construction of the Estimator. Define the sets

$\displaystyle S_{k}=\\{h\in\mathcal{H}:\Delta_{h}\leq n2^{-k+1}\\}.$

Let $\widehat{\mu}_{k}$ be some estimator formed from data collected in $k$th
round. Define the event

$\displaystyle\mathcal{E}_{k}(\widehat{\mu}_{k})$ $\displaystyle=\\{\forall
h\in
S_{k}^{c},\,\,|(h_{*}-h)^{\top}(\widehat{\mu}_{k}-\mu)|\leq\frac{\Delta_{h}}{8}\\}$
$\displaystyle\cap\\{\forall h\in
S_{k},\,\,|(h_{*}-h)^{\top}(\widehat{\mu}_{k}-\mu)|\leq\frac{2^{-k+1}n}{8}\\}$

We show that at every round $k$, we can construct an estimator
$\widehat{\mu}_{k}\in[-1,1]^{n}$ such that
$\Pr(\mathcal{E}_{k}^{c}(\widehat{\mu}_{k})|\mathcal{E}_{k-1}(\widehat{\mu}_{k-1}),\ldots,\mathcal{E}_{1}(\widehat{\mu}_{1}))\leq\delta_{k}\log(n\epsilon^{-1})$
where $\delta_{k}>0$ will be chosen at the $k$th round.

Step 1.1: Base Case

Let $\widehat{\mu}_{1}$ be the estimator from Theorem 1 applied with
$\delta_{1}$ to $\mathcal{H}$ (to be chosen later). Then, we have that

$\displaystyle\sup_{h,h^{\prime}\in\mathcal{H}}|(h-h^{\prime})^{\top}(\widehat{\mu}_{1}-\mu)|$
$\displaystyle\leq
c[\log(2/\delta_{1})\max_{h,h^{\prime}\in\mathcal{H}}\Big{\lVert}h-h^{\prime}\Big{\rVert}_{A(N\lambda)^{-1}}+\mathbb{E}_{{\zeta}\sim
N(0,I)}[\sup_{h\in\mathcal{H}}h^{\top}A(N\lambda)^{-1/2}{\zeta}]]$
$\displaystyle\leq
c[\frac{\pi}{2}\log(2/\delta_{1})\mathbb{E}[\sup_{h\in\mathcal{H}}(h-h^{\prime})^{\top}A(N\lambda)^{-1/2}{\zeta}]+\mathbb{E}_{{\zeta}\sim
N(0,I)}[\sup_{h\in\mathcal{H}}h^{\top}A(N\lambda)^{-1/2}{\zeta}]]$ (24)
$\displaystyle\leq c^{\prime}\sqrt{\log(2/\delta_{1})}\mathbb{E}_{{\zeta}\sim
N(0,I)}[\sup_{h\in\mathcal{H}}h^{\top}A(N\lambda)^{-1/2}{\zeta}].$

where in line (24) we used Lemma 2. Now, we have that

$\displaystyle\frac{\sup_{h,h^{\prime}\in\mathcal{H}}|(h-h^{\prime})^{\top}(\widehat{\mu}-\mu)|}{n}$
$\displaystyle\leq
c\sqrt{\log(2/\delta_{1})}\mathbb{E}[\frac{\sup_{h\in\mathcal{H}}h^{\top}A(N\lambda)^{-1/2}{\zeta}]}{n}]$
$\displaystyle\leq\frac{1}{8}$

where we chose

$\displaystyle\delta_{1}=2\exp(-c^{\prime\prime}\frac{N}{\mathbb{E}[\frac{\sup_{h\in\mathcal{H}}h^{\top}A(\lambda)^{-1/2}{\zeta}]}{n}]^{2}})$

for a universal constant $c^{\prime\prime}>0$ large enough. This proves the
base case for both $h\in S_{1}^{c}$ and $h\in S_{1}$.

Step 1.2: Inductive Step. Next, we show the inductive step. Suppose that at
round $k$, the hypothesis is satisfied, i.e., the algorithm has constructed
estimators $\widehat{\mu}_{1},\ldots,\widehat{\mu}_{k}$ such that
$\mathcal{E}_{k}(\widehat{\mu}_{k})\cap\ldots\cap\mathcal{E}_{1}(\widehat{\mu}_{1})$
holds. Now, we construct an estimator $\widehat{\mu}_{k+1}$ for round $k+1$.
Define for every $l\in[k]\cup\\{0\\}$, the set

$\displaystyle\widehat{S}_{l}=\\{h:(\widetilde{h}_{k}-h)^{\top}\widehat{\mu}_{k}\leq
2^{-l+1}n\\}.$

We will construct an estimator each subset $\widehat{S}_{l}$ and then combine
these into a single estimator. $\widehat{S}_{l}$ can be thought of as an
estimate for $S_{l}$ as suggested by the following claim.

######  Claim 1.

$S_{l+1}\subset\widehat{S}_{l}\subset S_{l-1}$ for all $l\in[k]$.

###### Proof of Claim 1.

Since $\mathcal{E}_{k}$ holds, by Lemma 3, we have that

  1. 1.

for all $h\in S_{k}^{c}$,

$\displaystyle|(\tilde{h}_{k}-h)^{\top}\widehat{\mu}_{k}-(h_{*}-h)^{\top}\mu|$
$\displaystyle\leq\frac{1}{2}\Delta_{h}.$ (25)

  2. 2.

for all $h\in S_{k}$,

$\displaystyle|(\tilde{h}_{k}-h)^{\top}\widehat{\mu}_{k}-(h_{*}-h)^{\top}\mu|$
$\displaystyle\leq\frac{1}{2}2^{-k+1}n.$ (26)

Suppose $h\in\widehat{S}_{l}$, that is,
$(\tilde{h}_{k}-h)^{\top}\widehat{\mu}_{k}\leq 2^{-l+1}n$. We show that $h\in
S_{l-1}$. If $h\in S_{k}$, then we automatically have that $h\in S_{l-1}$
since $l\in[k]$ and $S_{k}\subset S_{l-1}$. Thus, suppose $h\in S_{k}^{c}$.
Then, (25) implies that
$\Delta_{h}\leq(\tilde{h}_{k}-h)^{\top}\widehat{\mu}_{k}+\tfrac{\Delta_{h}}{2}\leq
2^{-l+1}n+\tfrac{\Delta_{h}}{2}$. Rearranging, we have that $\Delta_{h}\leq
2^{-l+2}n$, implying that $h\in S_{l-1}$. We conclude that
$\widehat{S}_{l}\subset S_{l-1}$.

Now, suppose that $h\in S_{l+1}$. If $h\in S_{k}^{c}$, then we have that
$(\tilde{h}_{k}-h)^{\top}\widehat{\mu}_{k}\leq 3/2\Delta_{h}\leq 2^{-l+1}n$
and hence $h\in\widehat{S}_{l}$. Suppose $h\in S_{k}$. (26) implies that

$\displaystyle(\tilde{h}_{k}-h)^{\top}\widehat{\mu}_{k}\leq\Delta_{h}+2^{-k}n\leq
2^{-k+1}n+2^{-k}n\leq 2^{-k+2}n$

where the second inequality follows since $h\in S_{k}$. Thus,
$h\in\widehat{S}_{k-1}$. Showing that $S_{k+1}\subset\widehat{S}_{k}$ follows
by a similar argument and we conclude that $S_{l+1}\subset\widehat{S}_{l}$.
This shows the claim.

∎

Step 1.2.1: Constructing the estimator for $\widehat{S}_{l}$. Let
$l\in[k]\cup\\{0\\}$. We use Theorem 1 to construct an estimator
$\widehat{\mu}_{k+1,l}(\delta_{k+1})$ for each $\widehat{S}_{l}$ such that for
all $l\in[k]\cup\\{0\\}$, the event

$\displaystyle\mathcal{E}_{k+1,l}=\\{\sup_{h,h^{\prime}\in\widehat{S}_{l}}|(h-h^{\prime})^{\top}(\widehat{\mu}_{k+1,l}(\delta_{k+1})-\mu)|$
$\displaystyle\leq
c[\log(2/\delta_{k+1})\max_{h,h^{\prime}\in\widehat{S}_{l}}\Big{\lVert}h-h^{\prime}\Big{\rVert}_{A(N\lambda)^{-1}}$
$\displaystyle+\mathbb{E}_{{\zeta}\sim
N(0,I)}[\sup_{h\in\widehat{S}_{l}}h^{\top}A(N\lambda)^{-1/2}{\zeta}]]\\}$

holds with probability at least $1-\delta_{k+1}$ (that will be chosen later).
We assume that $\cap_{l\in[k]\cup\\{0\\}}\mathcal{E}_{k+1,l}$ holds for the
remainder of the proof, which by the union bound holds with probability at
least $1-\delta\log(n\epsilon^{-1})$.

Fix $l\in[k]$. We have that

$\displaystyle\sup_{h,h^{\prime}\in
S_{l+1}}|(h-h^{\prime})^{\top}(\widehat{\mu}_{k+1,l}(\delta_{k+1})-\mu)|$
$\displaystyle\leq\sup_{h,h^{\prime}\in\widehat{S}_{l}}|(h-h^{\prime})^{\top}(\widehat{\mu}_{k+1,l}(\delta_{k+1})-\mu)|$
(27) $\displaystyle\leq
c[\log(2/\delta_{k+1})\max_{h,h^{\prime}\in\widehat{S}_{l}}\Big{\lVert}h-h^{\prime}\Big{\rVert}_{A(N\lambda)^{-1}}+\mathbb{E}_{{\zeta}\sim
N(0,I)}[\sup_{h\in\widehat{S}_{l}}h^{\top}A(N\lambda)^{-1/2}{\zeta}]$
$\displaystyle\leq
c\sqrt{\log(1/\delta_{k+1})\mathbb{E}[\sup_{h\in\widehat{S}_{l}}h^{\top}A(N\lambda)^{-1/2}{\zeta}]^{2}}$
(28) $\displaystyle\leq c\sqrt{\log(1/\delta_{k+1})\mathbb{E}[\sup_{h\in
S_{l-1}}h^{\top}A(N\lambda)^{-1/2}{\zeta}]^{2}}$ (29)

where inequality (27) follows by $S_{l+1}\subset\widehat{S}_{l}$ from Claim 1,
inequality (28) follows by Lemma 2, and the inequality (29) follows from
$\widehat{S}_{l}\subset S_{l-1}$ from Claim 1.

Now, we have that

$\displaystyle\frac{\sup_{h,h^{\prime}\in
S_{l+1}}|(h-h^{\prime})^{\top}(\widehat{\mu}_{k+1,l}(\delta_{k+1})-\mu)|}{2^{-l}n}$
$\displaystyle\leq c\sqrt{\log(1/\delta_{k+1})\mathbb{E}[\sup_{h\in
S_{l-1}}\frac{h^{\top}A(N\lambda)^{-1/2}{\zeta}}{2^{-l}n}]^{2}}$
$\displaystyle\leq
c^{\prime}\sqrt{\log(1/\delta_{k+1})\frac{\mathbb{E}[\sup_{h\in
S_{l-1}}\frac{(\tilde{h}_{k}-h)^{\top}A(\lambda)^{-1/2}{\zeta}}{2^{-l+2}n}]^{2}}{N}}$
$\displaystyle\leq c^{\prime\prime}\sqrt{\
\log(1/\delta_{k+1})\frac{\mathbb{E}[\sup_{h\in
S_{l-1}}\frac{(\tilde{h}_{k}-h)^{\top}A(\lambda)^{-1/2}{\zeta}}{\Delta_{h}+2^{-k+1}n}]^{2}}{N}}$
(30) $\displaystyle\leq
c^{\prime\prime}\sqrt{\log(1/\delta_{k+1})\frac{\mathbb{E}[\sup_{h\in\mathcal{H}}\frac{(\tilde{h}_{k}-h)^{\top}A(\lambda)^{-1/2}{\zeta}}{\Delta_{h}+2^{-k+1}n}]^{2}}{N}}$
(31) $\displaystyle\leq
c^{\prime\prime\prime}\sqrt{\log(1/\delta_{k+1})\frac{\mathbb{E}[\sup_{h\in\mathcal{H}}\frac{(\tilde{h}_{k}-h)^{\top}A(\lambda)^{-1/2}{\zeta}}{(\tilde{h}_{k}-h)^{\top}\widehat{\mu}_{k}+2^{-k+1}n}]^{2}}{N}}$
(32)

Since $\tilde{h}_{k}\in S_{l-1}$ by Lemma 3 and for all $h\in S_{l-1}$,
$2^{-l+2}n\geq\Delta_{h}+2^{-k+1}n$,, we may apply Lemma 4 to obtain line
(30). (32) follows since we assumed $\mathcal{E}_{k}$ holds and Lemma 3.

Now, we choose

$\displaystyle\delta_{k+1}=\exp(-c^{\prime}\frac{N}{\mathbb{E}[\sup_{h\in\mathcal{H}}\frac{(\widetilde{h}_{k}-h)^{\top}A(\lambda)^{-1/2}{\zeta}}{(\widetilde{h}_{k}-h)^{\top}\widehat{\mu}_{k}+2^{-k+1}n}]^{2}})$

for a universal constant $c^{\prime}>0$ large enough to guarantee that with
probability at least $1-\delta_{k+1}$,

$\displaystyle\frac{\sup_{h,h^{\prime}\in
S_{l+1}}|(h-h^{\prime})^{\top}(\widehat{\mu}_{k+1,l}(\delta_{k+1})-\mu)|}{2^{-l}n}\leq\frac{1}{32}.$

Step 1.2.2: Combining the estimators into a single estimator
$\widehat{\mu}_{k+1}$. Now, define the polyhedron based on the estimators
$\widehat{\mu}_{k+1,l}(\delta_{k+1})$ for $l=0,1,\ldots,k$:

$\displaystyle P$ $\displaystyle=\\{y\in[-1,1]^{n}:\forall
l\in[k]\cup\\{0\\},\forall
h,h^{\prime}\in\widehat{S}_{l}:\frac{|(h-h^{\prime})^{\top}(\widehat{\mu}_{k+1,l}(\delta_{k+1})-y)|}{2^{-l}n}\leq\frac{1}{32}\\}.$

We define the estimator $\widehat{\mu}_{k+1}$ as follows: if $P$ is nonempty,
then let $\widehat{\mu}_{k+1}$ be any point in $P$; otherwise, let
$\widehat{\mu}_{k+1}$ be any point in $\mathbb{R}^{n}$.

On the event $\cap_{l\in[k]\cup\\{0\\}}\mathcal{E}_{k+1,l}$ , $P$ is nonempty
since $\mu\in P$ and, thus, $\widehat{\mu}_{k+1}\in P$.

Let $l\in[k]\cup\\{0\\}$ and $h,h^{\prime}\in\widehat{S}_{l}$. By the triangle
inequality the event $\cap_{l\in[k]\cup\\{0\\}}\mathcal{E}_{k+1,l}$, and
$\widehat{\mu}_{k+1}\in P$, we have that

$\displaystyle\frac{|(h-h^{\prime})^{\top}(\widehat{\mu}_{k+1}-\mu)|}{2^{-l}n}$
$\displaystyle\leq\frac{|(h-h^{\prime})^{\top}(\widehat{\mu}_{k+1}-\widehat{\mu}_{k+1,l})|}{2^{-l}n}+\frac{|(h-h^{\prime})^{\top}(\mu-\widehat{\mu}_{k+1,l})|}{2^{-l}n}\leq\frac{1}{16}.$

By the union bound, with probability at least
$1-\delta_{k+1}\log(n\epsilon^{-1})$, for every $l\in[k]\cup\\{0\\}$,

$\displaystyle\sup_{h,h^{\prime}\in
S_{l+1}}\frac{|(h-h^{\prime})^{\top}(\widehat{\mu}_{k+1}-\mu)|}{2^{-l}n}\leq\sup_{h,h^{\prime}\in\widehat{S}_{l}}\frac{|(h-h^{\prime})^{\top}(\widehat{\mu}_{k+1}-\mu)|}{2^{-l}n}\leq\frac{1}{16}.$

where we used $S_{l+1}\subset\widehat{S}_{l}$ from Claim 1. Furthermore, since
$\widehat{\mu}_{k}\in[-1,1]^{n}$ note that $\widehat{S}_{0}=\mathcal{H}$ and
so we also have that

$\displaystyle\sup_{h,h^{\prime}\in\mathcal{H}}\frac{|(h-h^{\prime})^{\top}(\widehat{\mu}_{k+1}-\mu)|}{n}\leq\frac{1}{16}.$

Thus, we have shown that for all $l\in[k]\cup\\{0\\}$,

$\displaystyle\sup_{h,h^{\prime}\in
S_{l}}\frac{|(h-h^{\prime})^{\top}(\widehat{\mu}_{k+1}-\mu)|}{2^{-l}n}\leq\frac{1}{16}.$
(33)

Now, we are ready to finish the inductive step. Let $h\in S_{k+1}^{c}$. Let
$j$ be the largest integer such that $h\in S_{j}$. Then,
$2^{-j}n\leq\Delta_{h}\leq 2^{-j+1}n$. Then, the inequality (33) implies that

$\displaystyle\frac{|(h^{*}-h)^{\top}(\widehat{\mu}_{k+1}-\mu)|}{\Delta_{h}}$
$\displaystyle\leq\frac{|(h^{*}-h)^{\top}(\widehat{\mu}_{k+1}-\mu)|}{2^{-j}n}$
(34) $\displaystyle\leq\sup_{h,h^{\prime}\in
S_{j}}\frac{|(h^{\prime}-h)^{\top}(\widehat{\mu}_{k+1}-\mu)|}{2^{-j+1}n}$ (35)
$\displaystyle\leq\frac{1}{16}.$ (36)

A similar argument shows that if $h\in S_{k+1}$,

$\displaystyle|(h^{*}-h)^{\top}(\widehat{\mu}_{k+1}-\mu)|\leq\frac{2^{-k}n}{16}.$
(37)

Step 2: Correctness Consider the final round $\bar{k}=\log(n\epsilon^{-1})$
and let $h$ such that $\Delta_{h}\geq\epsilon$. Then, by the previous step, we
have that

$\displaystyle|(h_{*}-h)^{\top}(\widehat{\mu}_{k}-\mu)|\leq\frac{\Delta_{h}}{8}.$

Therefore,
$(h^{*}-h)^{\top}\widehat{\mu}_{\bar{k}}\geq\frac{7}{8}\Delta_{h}>0$. Thus,
$h$ cannot be the empirical maximizer in the final round and the algorithm
outputs $\bar{h}\in\mathcal{H}$ such that
$\mu^{\top}\bar{h}\geq\mu^{\top}h^{*}-\epsilon$.

Step 3: Bounding the probability of error Now, we need to bound the
probability of error. We bound $\delta_{k}$ for all $k$. This argument is
quite similar to the one given in (Katz-Samuels et al., 2020). Fix a round
$k$. Lemma 3 yields

$\displaystyle\mathbb{E}_{{\zeta}\sim
N(0,I)}[\max_{h\in\mathcal{H}}\frac{(\tilde{h}_{k}-h)^{\top}A(\lambda)^{-1/2}{\zeta}}{2^{-k+1}n+\widehat{\mu}^{\top}_{k+1}(\tilde{h}_{k}-h)}]^{2}$
$\displaystyle\leq c\mathbb{E}_{{\zeta}\sim
N(0,I)}[\max_{h\in\mathcal{H}}\frac{(\tilde{h}_{k}-h)^{\top}A(\lambda)^{-1/2}{\zeta}}{2^{-k+1}n+\Delta_{h}}]^{2}$
(38) $\displaystyle\leq c^{\prime}[\mathbb{E}_{{\zeta}\sim
N(0,I)}[\max_{h\in\mathcal{H}}\frac{(h_{*}-h)^{\top}A(\lambda)^{-1/2}{\zeta}}{2^{-k+1}n+\Delta_{h}}]^{2}$
(39) $\displaystyle+\mathbb{E}_{{\zeta}\sim
N(0,I)}[\max_{h\in\mathcal{H}}\frac{(h_{*}-\tilde{h}_{k})^{\top}A(\lambda)^{-1/2}{\zeta}}{2^{-k+1}n+\Delta_{h}}]^{2}]$
(40)

We start by bounding the first term. Fix
$h_{0}\in\mathcal{H}\setminus\\{h_{*}\\}$.

$\displaystyle\mathbb{E}_{{\zeta}\sim N(0,I)}[$
$\displaystyle\max_{h\in\mathcal{H}}\frac{(h_{*}-h)^{\top}A(\lambda)^{-1/2}{\zeta}}{2^{-k+1}n+\Delta_{h}}]^{2}$
$\displaystyle\leq\mathbb{E}_{{\zeta}\sim
N(0,I)}[\max_{h\in\mathcal{H}\setminus\\{h_{*}\\}}|\frac{(h_{*}-h)^{\top}A(\lambda)^{-1/2}{\zeta}}{2^{-k+1}n+\Delta_{h}}|]^{2}$
$\displaystyle\leq 8\mathbb{E}_{{\zeta}\sim
N(0,I)}[\max_{h\in\mathcal{H}\setminus\\{h_{*}\\}}\frac{(h_{*}-h)^{\top}A(\lambda)^{-1/2}{\zeta}}{2^{-k+1}n+\Delta_{h}}]^{2}+8\frac{\Big{\lVert}h_{*}-h_{0}\Big{\rVert}_{A(\lambda)^{-1}}^{2}}{(2^{-k+1}n+\Delta_{h_{0}})^{2}}$
(41) $\displaystyle\leq 8[\mathbb{E}_{{\zeta}\sim
N(0,I)}[\max_{h\in\mathcal{H}\setminus\\{h_{*}\\}}\frac{(h_{*}-h)^{\top}A(\lambda)^{-1/2}{\zeta}}{\max(\epsilon,\Delta_{h})}]^{2}$
$\displaystyle+\max_{h\neq
h_{*}}\frac{\Big{\lVert}h_{*}-h\Big{\rVert}_{A(\lambda)^{-1}}^{2}}{\max(\epsilon,\Delta_{h})^{2}}]$
(42)

where line (41) is the consequence of exercise 7.6.9 in (Vershynin, 2019).

Now, we turn to the second term. We have that

$\displaystyle\mathbb{E}_{{\zeta}\sim
N(0,I)}[\max_{h\in\mathcal{H}}\frac{(h_{*}-\tilde{h}_{k})^{\top}A(\lambda)^{-1/2}{\zeta}}{2^{-k+1}n+\Delta_{h}}]^{2}$
$\displaystyle\leq\mathbb{E}_{{\zeta}\sim
N(0,I)}[\max(\frac{(h_{*}-\tilde{h}_{k})^{\top}A(\lambda)^{-1/2}{\zeta}}{2^{-k+1}n},0)]^{2}$
$\displaystyle\leq
c\frac{\Big{\lVert}h_{*}-\tilde{h}_{k}\Big{\rVert}_{A(\lambda)^{-1}}^{2}}{(2^{-k+1}n)^{2}}$
$\displaystyle\leq
c^{\prime}\frac{\Big{\lVert}h_{*}-\tilde{h}_{k}\Big{\rVert}_{A(\lambda)^{-1}}^{2}}{\max(\epsilon,\Delta_{\tilde{h}_{k}})^{2}}$
(43) $\displaystyle\leq
c^{\prime}\max_{h\in\mathcal{H}\setminus\\{h_{*}\\}}\frac{\Big{\lVert}h_{*}-h\Big{\rVert}_{A(\lambda)^{-1}}^{2}}{\max(\epsilon,\Delta_{h})^{2}}$
(44)

where we obtain line (43) since $\tilde{h}_{k}\in S_{k+2}$ by Lemma 3.

Plugging in the design used at round $k$, $\lambda_{k}$, we have that

$\displaystyle\mathbb{E}_{{\zeta}\sim
N(0,I)}[\max_{h\in\mathcal{H}}\frac{(\tilde{h}_{k}-h)^{\top}A(\lambda_{k})^{-1/2}{\zeta}}{2^{-k+1}n+\widehat{\mu}^{\top}_{k+1}(\tilde{h}_{k}-h)}]^{2}$
$\displaystyle=\min_{\lambda}\mathbb{E}_{{\zeta}\sim
N(0,I)}[\max_{h\in\mathcal{H}}\frac{(\tilde{h}_{k}-h)^{\top}A(\lambda)^{-1/2}{\zeta}}{2^{-k+1}n+\widehat{\mu}^{\top}_{k+1}(\tilde{h}_{k}-h)}]^{2}$
(45) $\displaystyle\leq
c\min_{\lambda}[\rho^{*}(\epsilon;\lambda)+\gamma^{*}(\epsilon;\lambda)]$ (46)
$\displaystyle\leq c^{\prime}[\rho^{*}(\epsilon)+\gamma^{*}(\epsilon)]$ (47)

where

$\displaystyle\rho^{*}(\epsilon;\lambda)$
$\displaystyle:=\sup_{h\in\mathcal{H}\setminus\\{h^{*}\\}}\frac{\Big{\lVert}h^{*}-h\Big{\rVert}^{2}_{A(\lambda)^{-1}}}{\max(\mu^{\top}(h^{*}-h),\epsilon)^{2}}$
$\displaystyle\gamma^{*}(\epsilon;\lambda)$
$\displaystyle:=\mathbb{E}_{{\zeta}\sim
N(0,I)}[\sup_{h\in\mathcal{H}\setminus\\{h^{*}\\}}\frac{(h^{*}-h)^{\top}A(\lambda)^{-1/2}{\zeta}}{\max(\mu^{\top}(h^{*}-h),\epsilon)}]^{2}.$

and (45) follows by definition of $\lambda_{k}$, (46) follows by (40), (42),
and (44), and (47) follows by Lemma 13 of (Katz-Samuels et al., 2020).

Putting it together, for all $k$

$\displaystyle\delta_{k+1}$
$\displaystyle=\exp(-c^{\prime}\frac{N}{\mathbb{E}[\sup_{h\in\mathcal{H}}\frac{(\widetilde{h}_{k}-h)^{\top}A(\lambda)^{-1/2}{\zeta}}{(\widetilde{h}_{k}-h)^{\top}\widehat{\mu}_{k}+2^{-k+1}n}]^{2}})$
$\displaystyle\leq\exp(-c^{\prime\prime}\frac{N}{[\gamma^{*}(\epsilon)+\rho^{*}(\epsilon)]})$
$\displaystyle\leq\exp(-c^{\prime\prime\prime}\frac{T}{\log(n\epsilon^{-1})[\gamma^{*}(\epsilon)+\rho^{*}(\epsilon)]})$

This completes the proof.

∎

######  Remark 4.

We stress that the construction of the estimators in the proof of Theorem 6 is
based solely on data observed by the algorithm and $\mathcal{H}$ and at no
point is knowledge of $\mu$ used.

###  H.1 Technical Lemmas

The proof of Theorem 6 uses the following Lemmas, which appeared originally as
Lemma 11, Lemma 1, and Lemma 13 in (Katz-Samuels et al., 2020).

######  Lemma 2.

Let $\mathcal{G}\subset\mathcal{H}$. Then,

$\displaystyle\mathbb{E}_{{\zeta}\sim
N(0,I)}[\max_{h,h^{\prime}\in\mathcal{H}}[A(\lambda)^{-1/2}(h-h^{\prime})]^{\top}{\zeta}]^{2}\geq\frac{2}{\pi}\max_{h,h^{\prime}\in\mathcal{H}}\Big{\lVert}h-h^{\prime}\Big{\rVert}_{A(\lambda)^{-1}}^{2}.$

######  Lemma 3.

Let $k\geq 1$. Consider the $k$th round of Algorithm 4. Suppose that

  * •

if $h\in S_{k}^{c}$,

$\displaystyle|(h_{*}-h)^{\top}(\widehat{\mu}_{k}-\mu)|\leq\frac{\Delta_{h}}{8}$
(48)

  * •

if $h\in S_{k}$,

$\displaystyle|(h_{*}-h)^{\top}(\widehat{\mu}_{k}-\mu)|\leq\frac{2^{-k+1}n}{8}.$
(49)

Then, the following hold:

  1. 1.

$\displaystyle\tilde{h}_{k}\in S_{k+2},$ (50)

  2. 2.

if $h\in S_{k}^{c}$

$\displaystyle|(\tilde{h}_{k}-h)^{\top}\widehat{\mu}_{k}-(h_{*}-h)^{\top}\mu|$
$\displaystyle\leq\frac{1}{2}\Delta_{h}.$ (51)

  3. 3.

if $h\in S_{k}$,

$\displaystyle|(\tilde{h}_{k}-h)^{\top}\widehat{\mu}_{k}-(h_{*}-h)^{\top}\mu|$
$\displaystyle\leq\frac{1}{2}2^{-k+1}n.$ (52)

  4. 4.

There exist universal constants $c,c^{\prime}>0$ such that

$\displaystyle
c\mathbb{E}[\sup_{h\in\mathcal{H}}\frac{(\tilde{h}_{k}-h)^{\top}A(\lambda)^{-1/2}{\zeta}}{\Delta_{h}+2^{-k+1}n}]^{2}$
$\displaystyle\leq\mathbb{E}[\sup_{h\in\mathcal{H}}\frac{(\tilde{h}_{k}-h)^{\top}A(\lambda)^{-1/2}{\zeta}}{(\tilde{h}_{k}-h)^{\top}\widehat{\mu}_{k}+2^{-k+1}n}]^{2}$
$\displaystyle\leq
c^{\prime}\mathbb{E}[\sup_{h\in\mathcal{H}}\frac{(\tilde{h}_{k}-h)^{\top}A(\lambda)^{-1/2}{\zeta}}{\Delta_{h}+2^{-k+1}n}]^{2}$

######  Lemma 4.

Let $V=\\{v_{1},\ldots,v_{l}\\}\subset\mathbb{R}^{d}$ with $0\in V$. Suppose
$a_{i}\geq 1$ for all $i\in[l]$. Then,

$\displaystyle\mathbb{E}_{{\zeta}\sim N(0,I)}[\sup_{v_{i}\in
V}v_{i}^{\top}{\zeta}]\leq\mathbb{E}_{{\zeta}\sim N(0,I)}[\sup_{v_{i}\in
V}a_{i}v_{i}^{\top}{\zeta}]$

##  Appendix I Efficient Fixed Budget Algorithm

Input: Budget $T$, tolerance $\epsilon>0$.

$\widehat{\mu}_{1}=\bm{0}\in\mathbb{R}^{d}$,
$N\longleftarrow\Big{\lfloor}T/\log_{2}(n\epsilon^{-1})\Big{\rfloor}$.

for $k=1,2,\ldots,\Big{\lfloor}\log_{2}(d\epsilon^{-1})\Big{\rfloor}$ do

$\tilde{h}_{k}\longleftarrow\operatorname*{arg\,max}_{h\in\mathcal{H}}\widehat{\mu}_{k}^{\top}h$

Let $\lambda_{k}^{(1)}$ be the solution of the following optimization problem
$\displaystyle\inf_{\lambda\in\operatorname*{\mathbf{\triangle}}}\mathbb{E}_{{\zeta}\sim
N(0,I)}[\max_{h\in\mathcal{H}}\frac{(\tilde{h}_{k}-h)^{\top}A(\lambda)^{-1/2}{\zeta}}{2^{-k+1}n+\widehat{\mu}^{\top}_{k}(\tilde{h}_{k}-h)}]^{2}$
(53)

Let $\lambda_{k}^{(2)}$ be the solution to
$\displaystyle\inf_{\lambda\in\operatorname*{\mathbf{\triangle}}}\max_{h\in\mathcal{H}}\max_{i\in\tilde{h}_{k}\Delta
h}\frac{\frac{1}{\lambda_{i}}}{2^{-k+1}n+\widehat{\mu}_{k}^{\top}(\tilde{h}_{k}-h)}$
(54)

$\lambda_{k}\longleftarrow\frac{1}{2}(\lambda_{k}^{(1)}+\lambda_{k}^{(2)})$

Sample $\\{x_{1},\ldots,x_{N}\\}\sim\lambda_{k}$.

Query $x_{1},\ldots,x_{N}$ and receive rewards $y_{1},\ldots,y_{N}$.

Let $\widehat{\mu}_{k+1}=\frac{1}{N}\sum_{s=1}^{N}A(\lambda)^{-1}x_{s}y_{s}$.

end for

Return $\operatorname*{arg\,max}_{h\in\mathcal{H}}\widehat{\mu}_{k+1}^{\top}h$

Algorithm 5 Fixed Budget ACED for Combinatorial Bandits (Computationally
Efficient).

In this section, we present Algorithm 5, which can be implemented in practice.
Algorithm 5 resembles Algorithm 4 with two differences. First, it uses the IPS
estimator instead of the theoretical estimator derived in the proof of Theorem
6. Second, it mixes the design (given in used in (23)) with the design defined
in (54) in order to control the worst-case deviations of the IPS estimator.

Now, we briefly discuss why Algorithm 5 can be efficiently implemented. As is
standard in combinatorial bandits, we assume access to a linear maximization
oracle: for any $v\in\mathbb{R}^{d}$, we can compute

$\displaystyle\text{Oracle}(v)=\operatorname*{arg\,max}_{z\in\mathcal{Z}}v^{\top}z$

efficiently.111In the setting of active classification, this is equivalent to
assuming a weighted $0/1$ loss minimization oracle. (Katz-Samuels et al.,
2020) gave a procedure for efficiently solving (53) up to a constant factor
assuming a linear maximization oracle, and so we focus on (54). Define the
function $g(\lambda)=\max_{i\in\tilde{h}_{k}\Delta
h}\frac{\frac{1}{\lambda_{i}}}{2^{-k+1}n+\widehat{\mu}_{k}^{\top}(\tilde{h}_{k}-h)}$.
$g$ is convex since it is the maximum of a collection of convex functions. One
can compute the subgradient of $g$ using the linear maximization oracle. For
each $i\in\tilde{h}_{k}$, one can compute

$\displaystyle\max_{h:i\not\in h}\widehat{\mu}^{\top}_{k}h$

by defining

$\displaystyle\tilde{\mu}_{j}^{(i)}=\begin{cases}\tilde{\mu}_{j}&j\neq i\\\
-\infty&j=i\end{cases}$

and use the linear maximization oracle to compute
$\max_{h}h^{\top}\tilde{\mu}^{(i)}$. Using a similar technique, for each
$i\not\in\tilde{h}_{k}$, one can compute

$\displaystyle\max_{h:i\in h}\widehat{\mu}^{\top}_{k}h.$

Then, using a standard result about subgradients, we have that $\partial
g(\lambda)$ consists of
$\frac{\partial}{\partial\lambda}\frac{\frac{1}{\lambda_{\tilde{i}}}}{\widehat{\mu}_{k}^{\top}(\tilde{h}_{k}-h)}$
where $\tilde{i}$ and $h$ attain the maximum in

$\displaystyle\max_{h\in\mathcal{H}}\max_{i\in\tilde{h}_{k}\Delta
h}\frac{\frac{1}{\lambda_{i}}}{2^{-k+1}n+\widehat{\mu}_{k}^{\top}(\tilde{h}_{k}-h)}.$

Thus, using this trick for computing the subgradient and any optimization
procedure for nonsmooth convex optimization, we can optimize (54). In Theorem
7, for the sake of simplicity and focusing on the key ideas, we suppose that
(53) and (54) are solved exactly, but using the optimization ideas laid out
here would only affect the sample complexity up to constant factors.

The following complexity parameter is a key term in Theorem 7:

$\displaystyle\psi^{*}(\epsilon):=\min_{\lambda\in\operatorname*{\mathbf{\triangle}}}\max_{h\in\mathcal{H}\setminus\\{h^{*}\\}}\max_{i\in
h^{*}\Delta
h}\frac{\frac{1}{\lambda_{i}}}{\max(\epsilon,\mu^{\top}(h^{*}-h))}.$

######  Theorem 7.

Let $T\in\mathbb{N}$ and $\epsilon>0$. If $T\geq
c_{1}\log(n\epsilon^{-1})[\gamma^{*}(\epsilon)+\rho^{*}(\epsilon)+\psi^{*}(\epsilon)\log(|\mathcal{H}|)\log(\log(|\mathcal{H}|))]$
, then Algorithm 5 satisfies

$\displaystyle\mathbb{P}(\mu^{\top}\widehat{h}+\epsilon<\mu^{\top}h^{*})\leq
c_{2}\log(n\epsilon^{-1})\exp(-\frac{T-\log(|\mathcal{H}|)\log(\log(|\mathcal{H}|))\psi^{*}(\epsilon)}{\log(n\epsilon^{-1})[\gamma^{*}(\epsilon)+\rho^{*}(\epsilon)+\psi^{*}(\epsilon)]})$

where $c_{1},c_{2}>0$ are universal constants.

###### Proof of Theorem 7.

Let $\alpha>0$ be a universal constant that will be specified later. Let
$\delta>0$ such that

$\displaystyle
T=\alpha\log(n\epsilon^{-1})[\log(1/\delta)(\gamma^{*}(\epsilon)+\rho^{*}(\epsilon)+\psi^{*}(\epsilon))+\psi^{*}(\epsilon)\log(|\mathcal{H}|)\log(\log(|\mathcal{H}|))],$

which exists since by assumption $T\geq
c\log(n\epsilon^{-1})[\gamma^{*}(\epsilon)+\rho^{*}(\epsilon)+\psi^{*}(\epsilon)\log(|\mathcal{H}|)\log(\log(|\mathcal{H}|))]$.
Note that

$\displaystyle
N=\log(1/\delta)\alpha(\gamma^{*}(\epsilon)+\rho^{*}(\epsilon)+\psi^{*}(\epsilon))+\psi^{*}(\epsilon)\log(|\mathcal{H}|)\log(\log(|\mathcal{H}|)).$
(55)

Recall
$\widehat{\mu}_{k}=\frac{1}{N}A(\lambda)^{-1}\sum_{s=1}^{N}x_{I_{s}}y_{s}$.
Recall

$\displaystyle S_{k}=\\{h\in\mathcal{H}:\Delta_{h}\leq n2^{-k+1}\\}.$

Note that $S_{0}=\mathcal{H}$ since $\mu\in[-1,1]$ by assumption. Define the
event at round $k$ for $l\in[k]\cup\\{0\\}$,

$\displaystyle\mathcal{E}_{k,l}=$ $\displaystyle\\{\sup_{h,h^{\prime}\in
S_{l}}|(h-h^{\prime})^{\top}(\widehat{\mu}_{k}-\mu)|)\leq$ $\displaystyle
c[\mathbb{E}[\sup_{h\in
S_{l}}h^{\top}A(N\lambda)^{-1/2}{\zeta}]+(\log(\log(|S_{l}|))\log(|S_{l}|)+\log(1/\delta))\frac{\max_{h,h^{\prime}\in
S_{l}}\max_{i\in h\Delta h^{\prime}}\frac{1}{\lambda_{i}}}{N}$
$\displaystyle+\Big{\lVert}h-h^{\prime}\Big{\rVert}_{A(N\lambda)^{-1}}\sqrt{\log(1/\delta)})\\}$

Define $\mathcal{E}_{k}=\cap_{l=0}^{k}\mathcal{E}_{k,l}$ and
$\mathcal{E}=\cap_{k=1}^{\log_{2}(n\epsilon^{-1})}\mathcal{E}_{k}$. Now, using
the law of total probability, the independence of samples between rounds, and
Lemma 5

$\displaystyle\mathbb{P}(\mathcal{E}^{c})$ $\displaystyle\leq\sum_{k\geq
1}\sum_{l=0}^{k}\mathbb{P}(\mathcal{E}_{k,l}^{c}|\cap_{j=1}^{k-1}\mathcal{E}_{j})\leq\log(n\epsilon^{-1})^{2}\delta.$

Suppose that $\mathcal{E}$ occurs for the remainder of the proof. Note that
using the same series of inequalities as in (27)-(29), we have that

$\displaystyle\sup_{h,h^{\prime}\in
S_{l}}|(h-h^{\prime})^{\top}(\widehat{\mu}_{k}-\mu)|)\leq$ $\displaystyle
c^{\prime}[\sqrt{\log(1/\delta)})\mathbb{E}[\sup_{h\in
S_{l}}h^{\top}A(N\lambda)^{-1/2}{\zeta}]+(\log(\log(|S_{l}|))\log(|S_{l}|)+\log(1/\delta))\frac{\max_{h,h^{\prime}\in
S_{l}}\max_{i\in h\Delta h^{\prime}}\frac{1}{\lambda_{i}}}{N}]$

We argue inductively that at every round $k\geq 2$

  1. 1.

for all $h\in S_{k}^{c}$,

$\displaystyle|(h_{*}-h)^{\top}(\widehat{\mu}_{k}-\mu)|\leq\frac{\Delta_{h}}{8}$

  2. 2.

for all $h\in S_{k}$,

$\displaystyle|(h_{*}-h)^{\top}(\widehat{\mu}_{k}-\mu)|\leq\frac{2^{-k+1}n}{8}.$

Step 1: Base Case. Let $k=2$. Then, the event $\mathcal{E}_{2,0}$ implies that

$\displaystyle\sup_{h\in\mathcal{H}}\frac{|(h^{*}-h)^{\top}(\widehat{\mu}_{k}-\mu)|)}{2^{-1}n}$
$\displaystyle\leq\sup_{h,h^{\prime}\in\mathcal{H}}\frac{|(h-h^{\prime})^{\top}(\widehat{\mu}_{k}-\mu)|)}{2^{-1}n}$
$\displaystyle\leq$
$\displaystyle\frac{1}{2^{-1}n}c^{\prime}[\sqrt{\log(1/\delta)})\mathbb{E}[\sup_{h\in\mathcal{H}}h^{\top}A(N\lambda)^{-1/2}{\zeta}]+(\log(|\mathcal{H}|)+\log(1/\delta))\frac{\max_{h,h^{\prime}\in\mathcal{H}}\max_{i\in
h\Delta h^{\prime}}\frac{1}{\lambda_{i}}}{N}]$
$\displaystyle=\frac{1}{2^{-1}n}c^{\prime}[\sqrt{\frac{\log(1/\delta)\mathbb{E}[\sup_{h\in\mathcal{H}}h^{\top}A(\lambda)^{-1/2}{\zeta}]^{2}}{\log(1/\delta)\alpha[\gamma^{*}(\epsilon)+\rho^{*}(\epsilon)]}}+(\log(|\mathcal{H}|)+\log(1/\delta))\frac{\max_{h,h^{\prime}\in\mathcal{H}}\max_{i\in
h\Delta
h^{\prime}}\frac{1}{\lambda_{i}}}{\alpha\psi^{*}(\epsilon)(\log(\log(\mathcal{H}))\log(\mathcal{H})+\log(1/\delta))}].$
(56)

where the last line follows by (55). Recall that
$\lambda_{1}=\frac{1}{2}(\lambda^{(1)}_{1}+\lambda_{2}^{(1)})$ where
$\lambda^{(1)}_{1}$ is the minimizer of (53) and $\lambda^{(1)}_{1}$ is the
minimizer of (54). We have that

$\displaystyle\mathbb{E}[\sup_{h\in\mathcal{H}}\frac{h^{\top}A(\lambda_{1})^{-1/2}{\zeta}}{2^{-1}n}]^{2}$
$\displaystyle\leq
4\mathbb{E}[\sup_{h\in\mathcal{H}}\frac{h^{\top}A(\lambda_{1}^{(1)})^{-1/2}{\zeta}}{2^{-1}n}]^{2}$
(57)
$\displaystyle=4\min_{\lambda}\mathbb{E}[\sup_{h\in\mathcal{H}}\frac{h^{\top}A(\lambda)^{-1/2}{\zeta}}{2^{-1}n}]^{2}$
(58) $\displaystyle\leq c[\gamma^{*}(\epsilon)+\rho^{*}(\epsilon)]$ (59)

(57) follows by sudakov-fernique inequality since
$A(\lambda_{1})\succeq\frac{1}{2}A(\lambda_{1}^{(1)})$ implies that
$\sqrt{2}A(\lambda_{1}^{(1)})^{-1/2}\succeq A(\lambda_{1})^{-1/2}$. Line (58)
follows by definition of $\lambda_{1}^{(1)}$. Finally, (59) follows by the
same series of inequalities that established (47).

Fix $h,h^{\prime}\in\mathcal{H}$. Then, if $i\in h\Delta h^{\prime}$, then
either $i\in h\Delta h^{*}$ or $i\in h^{\prime}\Delta h^{*}$. Thus,

$\displaystyle\max_{h,h^{\prime}\in\mathcal{H}}\max_{i\in h\Delta
h^{\prime}}\frac{\frac{1}{\lambda_{1,i}}}{2^{-1}n}$ $\displaystyle\leq
2\max_{h\in\mathcal{H}\setminus\\{h^{*}\\}}\max_{i\in h\Delta
h^{*}}\frac{\frac{1}{\lambda_{1,i}}}{2^{-1}n}$ $\displaystyle\leq
4\max_{h\in\mathcal{H}\setminus\\{h^{*}\\}}\max_{i\in h\Delta
h^{*}}\frac{\frac{1}{\lambda^{(2)}_{1,i}}}{2^{-1}n}$ (60)
$\displaystyle=8\min_{\lambda}\max_{h\in\mathcal{H}\setminus\\{h^{*}\\}}\max_{i\in
h\Delta h^{*}}\frac{\frac{1}{\lambda_{i}}}{2n}$ (61) $\displaystyle\leq
c\psi^{*}(\epsilon)$ (62)

where (60) follows by definition of $\lambda_{1}$, (61) follows by definition
of $\lambda_{1}^{(2)}$, and (62) follows by definition of $\psi^{*}(\epsilon)$
and since for all $h\in\mathcal{H}\setminus\\{h^{*}\\}$, $\Delta_{h}\leq 2n$.

Then, putting together (56), (59), and (62), we have that if the universal
constant $\alpha$ is large enough, then

$\displaystyle\sup_{h,h^{\prime}\in\mathcal{H}}\frac{|(h-h^{\prime})^{\top}(\widehat{\mu}_{k}-\mu)|)}{2^{-1}n}$
$\displaystyle\leq\frac{1}{8}$

this proves the base case.

Step 2: Inductive Step. Suppose that at round $k\geq 2$

  1. 1.

for all $h\in S_{k}^{c}$,

$\displaystyle|(h_{*}-h)^{\top}(\widehat{\mu}_{k}-\mu)|\leq\frac{\Delta_{h}}{8}$

  2. 2.

for all $h\in S_{k}$,

$\displaystyle|(h_{*}-h)^{\top}(\widehat{\mu}_{k}-\mu)|\leq\frac{2^{-k+1}n}{8}.$

Now, we prove the statement for round $k+1$. Let $l\in[k+1]$. Using
$\mathcal{E}_{k+1,l}$, we have that

$\displaystyle\frac{\sup_{h,h^{\prime}\in
S_{l}}|(h-h^{\prime})^{\top}(\widehat{\mu}_{k+1}-\mu)|}{2^{-l}n}\leq
c\sqrt{\log(1/\delta)\mathbb{E}[\sup_{h\in
S_{l}}\frac{h^{\top}A(N\lambda_{k})^{-1/2}{\zeta}}{2^{-l}n}]^{2}}$ (63)
$\displaystyle+(\log(\log(|S_{l}|))\log(|S_{l}|)+\log(1/\delta))\frac{\max_{h,h^{\prime}\in
S_{l}}\max_{i\in h\Delta h^{\prime}}\frac{1/\lambda_{k,i}}{2^{-l}n}}{N}$ (64)

Bounding the first term, we have that

$\displaystyle\sqrt{\log(1/\delta)\mathbb{E}[\sup_{h\in
S_{l}}\frac{h^{\top}A(N\lambda_{k})^{-1/2}{\zeta}}{2^{-l}n}]^{2}}$
$\displaystyle\leq c^{\prime}\sqrt{\log(1/\delta)\frac{\mathbb{E}[\sup_{h\in
S_{l}}\frac{(\tilde{h}_{k}-h)^{\top}A(\lambda_{k})^{-1/2}{\zeta}}{2^{-l+2}n}]^{2}}{N}}$
$\displaystyle\leq
c^{\prime\prime}\sqrt{\log(1/\delta)\frac{\mathbb{E}[\sup_{h\in
S_{l}}\frac{(\tilde{h}_{k}-h)^{\top}A(\lambda_{k})^{-1/2}{\zeta}}{\Delta_{h}+2^{-k+1}n}]^{2}}{N}}$
(65) $\displaystyle\leq
c^{\prime\prime}\sqrt{\log(1/\delta)\frac{\mathbb{E}[\sup_{h\in\mathcal{H}}\frac{(\tilde{h}_{k}-h)^{\top}A(\lambda_{k})^{-1/2}{\zeta}}{\Delta_{h}+2^{-k+1}n}]^{2}}{N}}$
(66) $\displaystyle\leq
c^{\prime\prime\prime}\sqrt{\log(1/\delta)\frac{\mathbb{E}[\sup_{h\in\mathcal{H}}\frac{(\tilde{h}_{k}-h)^{\top}A(\lambda_{k})^{-1/2}{\zeta}}{(\tilde{h}_{k}-h)^{\top}\widehat{\mu}_{k}+2^{-k+1}n}]^{2}}{N}}$
(67)

Since $\tilde{h}_{k}\in S_{l}$ by Lemma 3 and for all $h\in S_{l-1}$,
$2^{-l+2}n\geq\Delta_{h}+2^{-k+1}n$,, we may apply Lemma 4 to obtain line
(65). (67) follows since we assumed $\mathcal{E}_{k}$ holds and Lemma 3. Using
a similar series of inequalities to Step 3 in the proof of Theorem 3, we have
that

$\displaystyle\sqrt{\log(1/\delta)\mathbb{E}[\sup_{h\in
S_{l}}\frac{h^{\top}A(N\lambda_{k})^{-1/2}{\zeta}}{2^{-l}n}]^{2}}$
$\displaystyle\leq
c^{\prime\prime\prime}\sqrt{\log(1/\delta)\frac{\mathbb{E}[\sup_{h\in\mathcal{H}}\frac{(\tilde{h}_{k}-h)^{\top}A(\lambda_{k})^{-1/2}{\zeta}}{(\tilde{h}_{k}-h)^{\top}\widehat{\mu}_{k}+2^{-k+1}n}]^{2}}{N}}$
$\displaystyle\leq
c^{\prime\prime\prime\prime}\sqrt{\log(1/\delta)\frac{\mathbb{E}[\sup_{h\in\mathcal{H}}\frac{(\tilde{h}_{k}-h)^{\top}A(\lambda_{k}^{(1)})^{-1/2}{\zeta}}{(\tilde{h}_{k}-h)^{\top}\widehat{\mu}_{k}+2^{-k+1}n}]^{2}}{N}}$
(68)
$\displaystyle=c^{\prime\prime\prime\prime}\min_{\lambda}\sqrt{\log(1/\delta)\frac{\mathbb{E}[\sup_{h\in\mathcal{H}}\frac{(\tilde{h}_{k}-h)^{\top}A(\lambda)^{-1/2}{\zeta}}{(\tilde{h}_{k}-h)^{\top}\widehat{\mu}_{k}+2^{-k+1}n}]^{2}}{N}}$
(69) $\displaystyle\leq
c^{\prime\prime\prime\prime\prime}\sqrt{\log(1/\delta)\frac{\rho^{*}(\epsilon)+\gamma^{*}(\epsilon)}{N}}$
(70) $\displaystyle\leq\frac{1}{32}$ (71)

where (68) follows by Sudakov-Fernique inequality and the definition of
$\lambda_{k}$, (69) follows by the definition of $\lambda_{k}^{(1)}$, (70)
follows by the same series of inequalities used to establish (47), and the
last line follows by plugging in (55) and letting $\alpha$ be a large enough
universal constant.

Now, we bound the second term. We have that

$\displaystyle\max_{h,h^{\prime}\in S_{l}}\max_{i\in h\Delta
h^{\prime}}\frac{1/\lambda_{k,i}}{2^{-l}n}$ $\displaystyle\leq 2\max_{h\in
S_{l}}\max_{i\in\widetilde{h}_{k}\Delta h}\frac{1/\lambda_{k,i}}{2^{-l}n}$
$\displaystyle\leq 4\max_{h\in S_{l}}\max_{i\in\widetilde{h}_{k}\Delta
h}\frac{1/\lambda_{k,i}}{2^{-k+1}n+\Delta_{h}}$ (72) $\displaystyle\leq
c\max_{h\in S_{l}}\max_{i\in\tilde{h}_{k}\Delta
h}\frac{1/\lambda_{k,i}}{2^{-k+1}n+\widehat{\mu}_{k}^{\top}(\tilde{h}_{k}-h)}$
(73) $\displaystyle\leq c^{\prime}\max_{h\in
S_{l}}\max_{i\in\widetilde{h}_{k}\Delta
h}\frac{1/\lambda_{k,i}}{2^{-k+1}n+\Delta_{h}}$ (74) $\displaystyle\leq
c^{\prime\prime}\max_{h\in S_{l}}\max_{i\in\widetilde{h}_{k}\Delta
h}\frac{1/\lambda_{k,i}^{(2)}}{2^{-k+1}n+\Delta_{h}}$ (75)
$\displaystyle=c^{\prime\prime}\min_{\lambda}\max_{h\in
S_{l}}\max_{i\in\widetilde{h}_{k}\Delta
h}\frac{1/\lambda_{i}}{2^{-k+1}n+\Delta_{h}}$ (76) $\displaystyle\leq
c^{\prime\prime\prime}\psi(\epsilon)$ (77)

where in (72) we used that since for all $h\in S_{l}$,
$2^{-l}n\geq\frac{2^{-k+1}n+\Delta_{h}}{2}$ and and in (73) we used the
inductive hypothesis and Lemma 3 and in (74), we used the inductive hypothesis
and Lemma 3 again, (75) follows by the definition of $\lambda_{k}$, (76)
follows by the definition of $\lambda_{k}^{(2)}$, and (77) follows by the
definition of $\psi(\epsilon)$. Thus,

$\displaystyle(\log(\log(|S_{l}|))\log(|S_{l}|)+\log(1/\delta))\frac{\max_{h,h^{\prime}\in
S_{l}}\max_{i\in h\Delta h^{\prime}}\frac{1/\lambda_{k,i}}{2^{-l}n}}{N}$
$\displaystyle\leq
c^{\prime\prime\prime}(\log(\log(|S_{l}|))\log(|S_{l}|)+\log(1/\delta))\frac{\psi(\epsilon)}{N}$
(78) $\displaystyle\leq\frac{1}{32}$ (79)

where the last line follows by plugging in (55) and letting $\alpha$ be a
large enough universal constant. Then, putting together (64), (71), and (79)
yields for every $l\in[k+1]\cup\\{0\\}$

$\displaystyle\frac{\sup_{h,h^{\prime}\in
S_{l}}|(h-h^{\prime})^{\top}(\widehat{\mu}_{k+1}-\mu)|}{2^{-l}n}\leq\frac{1}{16}$

Using the same series of inequalities used to establish (36) and (37)
completes the inductive step.

Step: Correctness. This argument is the same as in the correctness step in the
proof of Theorem 6 ∎

###  I.1 Lemmas

In this Section, we prove the main concentration inequality, Lemma 5, that is
used in the proof of Theorem 7. We need the following definition for the proof
of Lemma 5.

######  Definition 2.

Fix a set $T\subset\mathbb{R}^{n}$. Let $d$ be a metric on $\mathbb{R}^{n}$.
The $\gamma_{1}$-functional of $T$ is defined as

$\displaystyle\gamma_{1}(T,d)$ $\displaystyle=\inf_{(T_{k})}\sup_{t\in
T}\sum_{k=0}^{\infty}2^{k}d(t,T_{k})$

where the infimum is taken over all admissible sequences of $T$.

######  Lemma 5.

Let $\mathcal{G}\subset\mathcal{H}$. Fix some $\lambda\in\triangle_{n}$ and
draw $\\{x_{s}\\}_{i=1}^{t}\sim\lambda$ and then observe $y_{s}$ with mean
$x_{s}^{\top}\mu$ and $|y_{i}|\leq 1$ with probability $1$ for $s=1,\ldots,t$.
Then, there exists a universal constant $c>0$ such that for any $u>0$ with
probability at most $\exp(-u)$

$\displaystyle\sup_{h,h^{\prime}\in\mathcal{G}}|(h-h^{\prime})^{\top}$
$\displaystyle(\frac{1}{t}A(\lambda)^{-1}\sum_{s=1}^{t}x_{I_{s}}y_{s}-\mu)|\leq$
$\displaystyle
c[\mathbb{E}[\sup_{h\in\mathcal{G}}h^{\top}A(t\lambda)^{-1/2}{\zeta}]+(\log(\log(|\mathcal{G}|))\log(|\mathcal{G}|)+u)\frac{\max_{h,h^{\prime}\in\mathcal{G}}\max_{i\in
h\Delta h^{\prime}}\frac{1}{\lambda_{i}}}{t}$
$\displaystyle+\Big{\lVert}h-h^{\prime}\Big{\rVert}_{A(t\lambda)^{-1}}\sqrt{u}]$

###### Proof.

Using Corollary 7.9 of (Ledoux, 2001), we have that with probability at least
$1-\exp(-u)$,

$\displaystyle\sup_{h,h^{\prime}\in\mathcal{G}}|(h-h^{\prime})^{\top}(\frac{1}{t}A(\lambda)^{-1}$
$\displaystyle\sum_{s=1}^{t}x_{I_{s}}y_{s}-\mu)|\leq$ $\displaystyle
c[\mathbb{E}[\sup_{h,h^{\prime}\in\mathcal{G}}|(h-h^{\prime})^{\top}(\frac{1}{t}A(\lambda)^{-1}\sum_{s=1}^{t}x_{I_{s}}y_{s}-\mu)|]+u\frac{\max_{h,h^{\prime}\in\mathcal{G}}\max_{i\in
h\Delta h^{\prime}}\frac{1}{\lambda_{i}}}{t}$
$\displaystyle+\Big{\lVert}h-h^{\prime}\Big{\rVert}_{A(t\lambda)^{-1}}\sqrt{u}).$
(80)

Using the standard technique of symmetrization, we have that

$\displaystyle\mathbb{E}[\sup_{h,h^{\prime}\in\mathcal{G}}|(h-h^{\prime})^{\top}(\frac{1}{t}A(\lambda)^{-1}\sum_{s=1}^{t}x_{I_{s}}y_{s}-\mu)|]\leq
2\mathbb{E}_{\epsilon_{1},\ldots,\epsilon_{t}}[\sup_{h,h^{\prime}\in\mathcal{G}}|(h-h^{\prime})^{\top}(\frac{1}{t}A(\lambda)^{-1}\sum_{s=1}^{t}x_{I_{s}}\epsilon_{s}|]$
(81)

where $\epsilon_{1},\ldots,\epsilon_{t}$ are Rademacher random variables. By
Bernstein’s inequality, we have that

$\displaystyle\mathbb{P}(|(h-h^{\prime})^{\top}(\frac{1}{t}A(\lambda)^{-1}\sum_{s=1}^{t}x_{I_{s}}\epsilon_{s}|\geq
u)\leq
2\exp(-c\frac{u^{2}}{\Big{\lVert}h-h^{\prime}\Big{\rVert}^{2}_{A(t\lambda)^{-1}}},\frac{u}{\max_{i\in
h\Delta h^{\prime}}\frac{1}{t\lambda_{i}}}).$ (82)

Define the set
$\widetilde{\mathcal{G}}=\\{A(\lambda)^{-1}h:h\in\mathcal{G}\\}$. Then, using
(82) and applying Theorem 2.2.23 of (Talagrand, 2014), we have that

$\displaystyle\mathbb{E}[\sup_{h,h^{\prime}\in\mathcal{G}}|(h-h^{\prime})^{\top}(\frac{1}{t}A(\lambda)^{-1}\sum_{s=1}^{t}x_{I_{s}}\epsilon_{s}|]$
$\displaystyle\leq
c[\gamma_{2}(\widetilde{\mathcal{G}},d_{2})+\gamma_{1}(\widetilde{\mathcal{G}},d_{1})]$
(83)

where $d_{2}$ is the metric induced by $\Big{\lVert}\cdot\Big{\rVert}_{2}$ and
$d_{1}$ is the metric induced $\Big{\lVert}\cdot\Big{\rVert}_{\infty}$. Using
Talagrand’s majorizing measure theorem (Theorem 8.6.1 in (Vershynin, 2019)),
we have that

$\displaystyle\gamma_{2}(\widetilde{\mathcal{G}},d_{2})\leq
c\mathbb{E}_{{\zeta}\sim
N(0,I)}[\sup_{h\in\mathcal{H}}h^{\top}A(\lambda)^{-1}{\zeta}].$ (84)

From the definition of $\gamma_{1}$, it follows trivially that

$\displaystyle\gamma_{1}(\widetilde{\mathcal{G}},d_{1})$
$\displaystyle\leq\log(\log(|\mathcal{G}|))\log(|\mathcal{G}|)\frac{\max_{h,h^{\prime}\in\mathcal{G}}\max_{i\in
h\Delta h^{\prime}}\frac{1}{\lambda_{i}}}{t}.$ (85)

Finally, putting together (80), (81), (83), (84), and (85), we obtain the
result.

∎

##  Appendix J Thresholds

Let $n$ be a power of $2$. Let $\mathcal{H}=\\{\mathbf{e}_{[k]}:k\in[n]\\}$
where $[\mathbf{e}_{A}]_{i}=\mathbf{1}\\{i\in A\\}$. Assume that
$\mu_{*}\in\epsilon(2\mathbf{e}_{[k_{\star}]}-1)$ for some $k_{\star}\in[n]$.