Chen, Liu and Wang

Actively Learning for Contextual Search

Active Learning for Contextual Search with Binary Feedbacks

Xi Chen ††thanks: Author names listed in alphabetical order. Stern School of
Business, New York University, NY 10011, USA Quanquan Liu Department of Food
and Resource Economics, University of Florida, Gainesville, FL 32611, USA
Yining Wang Warrington College of Business, University of Florida,
Gainesville, FL 32611, USA

In this paper, we study the learning problem in contextual search, which is
motivated by applications such as first-price auction, personalized medicine
experiments, and feature-based pricing experiments. In particular, for a
sequence of arriving context vectors, with each context associated with an
underlying value, the decision-maker either makes a query at a certain point
or skips the context. The decision-maker will only observe the binary feedback
on the relationship between the query point and the value associated with the
context. We study a PAC learning setting, where the goal is to learn the
underlying mean value function in context with a minimum number of queries. To
address this challenge, we propose a tri-section search approach combined with
a margin-based active learning method. We show that the algorithm only needs
to make $O(1/\varepsilon^{2})$ queries to achieve an $\epsilon$-estimation
accuracy. This sample complexity significantly reduces the required sample
complexity in the passive setting, at least $\Omega(1/\varepsilon^{4})$.

Active learning, binary feedback, contextual search, first-price auction

##  1 Introduction

Contextual search, which extends the classical binary search problem to high
dimensions, finds a wide range of applications, such as auctions, dynamic
pricing, and personalized medicine. In the contextual search problem, for each
round $i=1,2,3$, an item (e.g., a customer or a patient) arrives sequentially,
each with a contextual vector $x_{i}\in\mathbb{R}^{d}$ accessible to the
decision-maker. We assume that the context $x_{i}$ incurs an unknown
stochastic _value_ $u_{i}=v(x_{i})+\xi_{i}$, where $v(x_{i})$ is the mean
value function of $x_{i}$ and $\xi_{i}$ is the stochastic noise. The decision-
maker selects a query $b_{i}\in\mathbb{R}$ and then observes the _binary
feedback_ , i.e., whether $u_{i}\geq b_{i}$ or vice versa. The true value
$u_{i}$ will never be revealed. To better fit our motivating applications that
illustrated below, the decision-maker is allowed to skip making a query to
save her budget. Our goal is to learn the mean value function $v(x_{i})$ with
a minimum number of queries. We now explain three motivating applications:

First-price Auction: In the Ads industry, many well-known Ad exchange
platforms have recently shifted from the second-price auction to the first-
price auction, such as ApNexus, Index Exchange, OpenX, and Google Ad Manager
(Sluis 2017, Davies 2019). Compared to the second-price auction, the first-
price auction has the advantages of enhanced transparency for bidders and
potentially increased revenue for the seller. The first-price auction becomes
increasingly popular in real-time bidding, which runs online auctions over a
large number of demand side platforms.

For an agent to design her bidding strategy, it is critically important to
learn the _market price_ given a context of an ad, i.e., the highest bid from
her competitors. This problem can be naturally cast as a contextual search
problem. Each $x_{i}$ corresponds to a coming bid request111Each bid request
usually contains the auction information, including user information (e.g.,
location, browser label), publisher information (e.g., web URL and ad slot
size), and the ad content., and $u_{i}=v(x_{i})+\xi_{i}$ corresponds to the
unknown market price for this auction. The agent first decides whether she
wants to participate in the auction and then posts her bid $b_{i}$ if she
joins the auction. In many first-price auction settings in real-time bidding,
the agent would only observe the _binary feedback_ on whether she wins the
auction but not the market price $u_{i}$. This problem is referred to as the
_landscape forecasting problem_ in the literature (Zhang et al. 2014).
Existing research mainly focuses on landscape forecasting under the second-
price auction (Wang et al. 2016, Ren et al. 2019). However, the feedback
structure of the first-price auction is fundamentally different from that of
the second-price auction. In the second price auction, when $b_{i}>u_{i}$, the
winning agent will be able to observe the market price $u_{i}$ as $u_{i}$ is
exactly the cost that she needs to pay. In contrast, the winning agent only
receives the binary feedback in a standard first-price auction. Moreover,
since an agent has the right to avoid making a bid, our contextual search
problem setting allows _the choice of not making a query_ to accommodate our
motivating application.

Personalized Medicine Experiment: In personalized medicine, a common practice
is to leverage a clinical trial experiment to determine the appropriate dosage
of a drug for an individual. Bastani and Bayati (2020) adopted a linear bandit
model (i.e., the linear form of $v(x)$) to investigate the relationship
between the optimal dosage and the patients’ profile. We consider a clinical
trial experiment for an expensive drug. The profile of each coming potential
experimental unit is characterized by $x_{i}$ (e.g., her demographics,
diagnosis, medications, and genetics). The algorithm will first decide whether
the experimental unit will be given the drug, and if so, recommends a dosage
$b_{i}$. The appropriate level of the dosage is modeled by
$u_{i}=v(x_{i})+\xi_{i}$. The algorithm receives binary feedback on whether
the recommended dosage is above or below the appropriate level. Moreover, we
assume that each clinical trial is costly. Thus, the goal is to use the
minimum number of trials to learn the ideal personalized dosage level for the
drug (i.e., the $v$ function).

Feature-based Pricing Experiment: For an online shopping platform that sells a
large number of different products, it is important to understand customers’
valuation for each product. Feature-based pricing models the valuation as a
linear function in the product’s feature vector (Qiang and Bayati 2016,
Javanmard and Nazerzadeh 2019, Cohen et al. 2020). It would be very costly to
conduct price experiments for all products. Thus, based on the feature vector
for each product $i$, the algorithm first decides whether the price experiment
should be conducted for this product. If so, a price $b_{i}$ is suggested, and
binary purchase decision will be observed subsequently.

Motivated by these applications, the goal of this paper is to propose an
efficient algorithm to learn $v(x)$. Following the existing literature on
contextual search and feature-based pricing, we also adopt linear model of the
mean valuation function, i.e., $v(x)=\langle x,w^{*}\rangle-\mu^{*}$ for some
unknown coefficient vector $w^{*}\in\mathbb{R}^{d}$ and the intercept
$\mu^{*}\in\mathbb{R}$. As compared to the existing literature, our contextual
search problem has the following unique features, which calls for new
algorithmic development:

  1. 1.

First, the existing contextual search setup aims to minimize either the
absolute loss $|b_{i}-v(x_{i})|$ or the $\epsilon$-ball loss
$\mathbb{I}(|b_{i}-v(x_{i})|>\epsilon)$ for some pre-determined $\epsilon$
over time. Here $\mathbb{I}(\cdot)$ denotes the indicator function. In
contrast, we consider a learning problem, where the goal is to learn $v(x)$ as
accurately as possible. Therefore, we adopt a probably approximately correct
(PAC) setting (see (2) in Sec. 2) instead of regret minimization setting in
existing literature (Lobel et al. 2017, Leme and Schneider 2018, Krishnamurthy
et al. 2021). To facilitate the analysis of this learning problem, we assume
the stochasticity of the contextual information $x_{i}$.

  2. 2.

Second, as we are motivated by _experimental_ applications, the decision-maker
should judge the benefit of a context $x_{i}$ to the learning problem.
Therefore, compared to the existing contextual search, our problem has another
layer of decision, i.e., whether to conduct a query or not, beyond the
decision of the query point itself.

To address this problem, we adopt the active learning framework from machine
learning (Settles 2012). In particular, we adopt the margin-based active
learning approach (Balcan et al. 2007). At a high level, let
$\widehat{v}(\cdot)$ be the current estimate of the underlying $v(\cdot)$
function and $\widehat{b}$ be the query point. For an arriving context $x$,
the margin-based active learning will make a query if
$|\widehat{v}(x)-\widehat{b}|$ is sufficiently small, which indicates that it
is difficult to determine the relationship between $\widehat{b}$ and
$\widehat{v}(x)$. Although it is an intuitive approach, existing margin-based
active learning approach cannot be applied to address our problem due to the
existence of the intercept $\mu^{*}$. In fact, there is a famous negative
result, which shows that active learning cannot significantly improve sample
complexity over _passive learning_ for linear binary classification models
_with intercepts_ (Dasgupta 2005b). Please refer to Figure 1 in Sec. 1.1 for
details.

To address this challenge, we propose an active learning procedure consisting
of three major stages:

  1. 1.

The first stage of the algorithm is to use trisection search to locate two
queries $\widehat{b}_{1}$ and $\widehat{b}_{2}$ that are close to the
underlying intercept term $\mu^{*}$, without consuming too many labeled
(queried) samples. In this first stage sample selection (i.e., determining
whether a sample is to be labeled/queried or not) is _not_ carried out, but
the algorithm will actively explore different actions in order to obtain
$\widehat{b}_{1},\widehat{b}_{2}$ that are close to $\mu^{*}$;

  2. 2.

The second stage of the algorithm is to apply margin based active learning to
learn the linear model $w^{*}$ and an intercept term depending on both
$\mu^{*}$ and $\widehat{b}_{1},\widehat{b}_{2}$. In this second stage sample
selection will be carried out, as only those users with contextual vectors
$x_{t}$ close to classification hyperplanes will be queried/labeled (see
Algorithm 3 later for details). The actions taken in this stage (on selected
samples) will be fixed to either $\widehat{b}_{1}$ or $\widehat{b}_{2}$
obtained in the first stage.

Note that, although this classification model still has non-zero intercept
terms, the closeness of $\widehat{b}_{1},\widehat{b}_{2}$ to $\mu^{*}$ would
imply that the obtained labels under actions $\widehat{b}_{1}$ or
$\widehat{b}_{2}$ are _balanced_ , circumventing the negative results in the
work of Dasgupta (2005b) which specifically constructed counter-examples with
unbalanced labels. In Figure 1 and the following related work section we give
a detailed account of this negative example and how it presents challenges to
active learning. Indeed, our theoretical analysis extends the arguments in
Balcan et al. (2007) to this more general setting of linear classification
_with intercepts_ and balanced labels, with similar convergence rates derived.

  3. 3.

The final stage of the algorithm is to reconstruct the mean utility model
$\widehat{v}(\cdot)$ from the estimated linear model and intercepts. Because
margin-based active learning can only estimate a linear model up to scales, we
need model estimates at two different actions
$\widehat{b}_{1},\widehat{b}_{2}$ (corresponding to two different effective
intercepts) in order to reconstruct $w^{*}$ and $\mu^{*}$ in $v(\cdot)$.
Details of how this reconstruction is carried out are given in the last two
lines of Algorithm 1.

We establish the sample complexity bound for the proposed margin-based active
learning with a tri-section search scheme. We assume that with
$\widetilde{O}(1/\varepsilon^{3})$ total number of incoming contexts, the
decision-maker only needs to make $\widetilde{O}(1/\varepsilon^{2})$ queries
to estimate the mean value function $v(x)$ within $\varepsilon$-precision
(with high probability). Here $\widetilde{O}$ here hides the dependence on $d$
and other logarithmic factors. We also show that in the passive setting, where
the decision-maker is required to conduct queries for all arriving contexts as
in the standard contextual search, the sample complexity would be at least
$\Omega(1/\varepsilon^{4})$ (see Remark 3.5).

###  1.1 Related work

Our problem setting can be viewed as a variant of the contextual search
problem, which is an extension of the classical binary search. In binary
search, the decision-maker tries to guess a fixed constant $\mu^{*}$ (i.e.,
the value $u_{i}\equiv\mu^{*}$ for all $i$ in our problem) by iteratively
making queries $b_{i}$. In the PAC learning setting, the binary search
algorithm only needs $O(\log(1/\varepsilon))$ queries to estimate $\mu^{*}$
within $\varepsilon$-precision. Due to the importance of applications such as
personalized medicine and feature-based pricing, contextual search has
received a lot of attention in recent years. The existing literature mainly
adopts the linear model for the mean value function. For $\varepsilon$-ball
loss $\sum_{i}\mathbb{I}(|b_{i}-v(x_{i})|>\varepsilon)$, Lobel et al. (2017)
established the $\Omega(d\log(1/\varepsilon\sqrt{d}))$ regret lower bound and
proposed the project volume algorithm that achieves a near-optimal regret of
$O(d\log(d/\varepsilon))$. For absolute loss $\sum_{i}|b_{i}-v(x_{i})|$, Leme
and Schneider (2018) established the regret bound of $O(\text{poly}(d))$. As
we explained in the introduction, to fit the applications considered in our
paper (e.g., landscape forecasting in the first-price auction), we adopt a PAC
learning setting and equip the decision-maker with the ability to pass an
incoming context (e.g., skipping an auction). While most contextual search
settings in the literature consider adversarial contextual information, we
assume the stochasticity of the contextual information as we study a learning
problem.

In one of our motivating examples for the first-price auction, there are
several recent research works devoted to optimizing the bidding strategy in
repeated auctions (Balseiro et al. 2019, Han et al. 2020a, b). These works
formulate the problem into contextual bandits with certain monotone
structures. In particular, Balseiro et al. (2019) proposed a cross-learning
contextual bandits formulation, where at each round, the decision-maker learns
rewards associated with all possible contextual information after making a
decision. In the context of the first-price auction, Balseiro et al. (2019)
modeled the bidder’s own valuation as the context and thus, the bidder would
know reward associated with other possible valuation after making the bid. In
our setting, the contextual information is the bid request’s profile (e.g.,
the information of user, publisher, and ad content). Furthermore, the
formulation and results of (Balseiro et al. 2019) allow for only a finite
number of possible bids, following classical literature on contextual bandits.
In contrast, our modeling and algorithm allow the placed bids to vary
continuously on the real line to allow for more flexible bidding strategies.
Han et al. (2020a, b) formulated the bidding problem into a contextual bandit
framework with either the censored feedback structure (i.e., the bidder only
knows the winner’s bid) or the full-information feedback structure (i.e., the
bidder knows the highest competing bid). Our paper mainly focuses on the
landscaping forecasting problem, which facilitates the design of the bidding
strategy by providing an accurate estimation of the highest competing bid.
Moreover, we consider a more limited (and thus challenging) feedback structure
with only binary feedback.

Figure 1: Illustration of negative examples of problem instances constructed
in (Dasgupta 2005b).

Note: the left panel shows examples of non-homogeneous linear classifiers with
_unbalanced_ labels, for which Dasgupta (2005b) shows that active learning
(i.e., sample selection for labeling purposes) cannot lead to significantly
improved sample complexity. The right panel shows non-homogenous linear
classifiers with _balanced_ labels, for which improvements of sample
complexity can be made via sample selection (active learning).

Active learning is an important research area in machine learning, originating
from the seminal work of Cohn et al. (1994) dating back to the 1990s. The main
idea behind active learning is to equip the learning algorithm with the
ability to _select_ samples or data points to be labeled, improving its sample
complexity in applications where labels are expensive to obtain but unlabeled
data are abundant. There have been many successful algorithms developed for
active learning, such as bisection search for one-dimensional noiseless
problems (Dasgupta 2005b), greedy method (Dasgupta 2005a), disagreement-based
active learning (Hanneke 2007, Balcan et al. 2009, Zhang and Chaudhuri 2014),
margin based active learning (Balcan et al. 2007, Balcan and Long 2013, Wang
and Singh 2016) and active learning based on surrogate loss functions (Awasthi
et al. 2017, Balcan and Zhang 2017). Due to the vast literature on active
learning we cannot cite all related works here, and would like to refer
interested readers to the excellent review of Hanneke et al. (2014) for an
overview of this area.

Our approach in this paper resembles the margin-based active learning method
(Balcan et al. 2007, Balcan and Long 2013, Wang and Singh 2016) which is
developed for linear classifiers and have been popular in the active learning
literature due to its intuitive nature, tight sample complexity, and relative
ease of implementation. However, while linear classifiers seem simple, non-
homogeneous linear classifiers (i.e., linear classifiers with _an intercept
term_) present notorious challenges to active learning algorithms. More
specifically, the work of Dasgupta (2005a) shows that when $d\geq 2$ and non-
homogeneous linear classifiers produce unbalanced samples, such as the example
shown on the left panel of Figure 1. In this illustrative example, potential
linear classifiers are within $O(\varepsilon)$ distance to the domain
boundary, and thus, active learning _cannot_ asymptotically improve sample
complexity over passive learning as it takes $O(1/\varepsilon)$ samples to hit
the boundaries. Note that, it is easy to verify that, if a non-homogenous
linear classifier is within $\epsilon$ distance to the boundary and the
underlying distribution of unlabeled samples is relatively uniform, the
probability of seeing a positive sample (as indicated in the region colored by
blue in Figure 1) is also on the order of $O(\epsilon)$. To overcome this
counter-example, in this paper we exploit the special structure in the
contextual search problem to “balance” the labels, as shown on the right panel
of Figure 1. While the balanced model still possesses a non-zero intercept
term, the classifier will be generally $\Omega(1)$ away from the boundary,
which our theoretical analysis shows is sufficient of obtaining desired sample
complexity results for active learning.

Active learning has been an important area in machine learning. However, it
has not received a lot of attention in operations management. This paper takes
a preliminary step on exploring the applications of active learning, and
hopefully, it will inspire more research on active learning to address
challenges arising from operations management.

###  1.2 Paper organization

The rest of the paper is organized as follows. Sec. 2 describes the problem
formulation and necessary assumptions. Sec. 3 develops our margin-based active
learning algorithm with the tri-section search and establishes the sample
complexity bound. The technical proofs are provided in Sec. 4. We provide the
numerical simulation studies in Sec. 5, followed by the conclusion in Sec. 6.
Proofs of some technical lemmas are relegated to the appendix.

##  2 Problem Formulation and Assumptions

In our modeling, assuming the items (e.g., ads or experimental units)
$i=1,2,3,\cdots$ arrive sequentially, each with a contextual or feature vector
$x_{i}\in\mathbb{R}^{d}$ accessible to the decision-maker. We assume that the
contextual vectors $\\{x_{i}\\}_{i\geq 1}$ are independently and identically
distributed with respect to an unknown underlying distribution $P_{X}$. We
also assume that $\|x_{i}\|_{2}\leq 1$ for the ease of illustration. Given the
contextual vector $x_{i}\in\mathbb{R}^{d}$, the “valuation” of the item (e.g.,
the highest competing bid in a first-price auction or appropriate dosage in
personlized medical treatment) follows a linear model:

$u_{i}=v(x_{i})+\xi_{i}=\langle x_{i},w^{*}\rangle-\mu^{*}+\xi_{i},$ (1)

where $v(\cdot)=\langle\cdot,w^{*}\rangle-\mu^{*}$ is an underlying linear
model with a fixed but unknown coefficient vector $w^{*}\in\mathbb{R}^{d}$,
the intercept $\mu^{*}\in\mathbb{R}$, and the noise $\\{\xi_{i}\\}_{i\geq 1}$,
which are independently and identically distributed stochastic variations with
respect to an unknown distribution $P_{\xi}$.

After observing the contextual vector $x_{i}\in\mathbb{R}^{d}$, the decision-
maker will make :

  1. 1.

Let the item pass without taking any actions, and thereby without obtaining
any feedback/information;

  2. 2.

Make a query at $b_{i}\in\mathbb{R}$, and observe the binary feedback
$y_{i}=1$ if $u_{i}\geq b_{i}$ or $y_{i}=-1$ if $u_{i}<b_{i}$.

Since making a query (e.g., posting a bid to participate in an auction or
admitting an experimental unit into a clinical trail program) incurs much
higher implicit cost as compared to passing (i.e., taking no action), the main
goal of the decision-maker is to use as fewer number of queries as possible to
estimate the mean valuation function $v(\cdot)$ to a certain precision. More
specifically, let $\varepsilon,\delta\in(0,1)$ be target accuracy and
probability parameters. We use $n(\varepsilon,\delta)$ to denote the number of
queries an learning algorithm takes in order to produce an estimate
$\widehat{v}(\cdot)$ that satisfies

$\sup_{\|x\|_{2}\leq
1}\big{|}\widehat{v}(x)-v(x)\big{|}\leq\varepsilon,\;\;\;\;\;\;\text{with
probability $\geq 1-\delta$}.$ (2)

Clearly, the smaller $n(\varepsilon,\delta)$ is the more efficient the
designed learning algorithm is. The main objective of this paper is to design
an active learning algorithm that minimizes $n(\varepsilon,\delta)$.
Additionally, we use $m(\varepsilon,\delta)$ to denote the number of _total_
samples (i.e., the number of total incoming contexts) an algorithm requires to
obtain an estimate $\widehat{v}$ satisfying Eq. (2). While those incoming
contexts skipped by our algorithm usually do not incur extra cost, it is
desirable that $m(\varepsilon,\delta)$ is reasonable because the supply of
experimental units might still be limited. In active learning literature, an
$m(\varepsilon,\delta)$ is _reasonable_ if it is a polynomial function in
terms of $1/\varepsilon,\log(1/\delta)$ and $d$ (Cohn 1996, Cohn et al. 1994,
Balcan et al. 2007).

Throughout this paper we impose the following assumptions.

  1. (A1)

There exists a constant $B<\infty$ such that $\|w^{*}\|_{2}\leq B$ and
$|\mu^{*}|\leq B$;

  2. (A2)

The distribution $P_{X}$ satisfies the following condition: it is supported on
the unit $\ell_{2}$ ball
$\mathbb{B}_{2}(d)=\\{x\in\mathbb{R}^{d}:\|x\|_{2}\leq 1\\}$; it admits a
probability density function $f_{x}(\cdot)$; there exist constants
$0<c_{x}\leq C_{x}<\infty$ such that $c_{x}f_{u}(x)\leq f_{x}(x)\leq
C_{x}f_{u}(x)$ for all $x\in\mathbb{B}_{2}(d)$, where $f_{u}$ is the
probability density function (PDF) of the uniform distribution on
$\mathbb{B}_{2}(d)$;

  3. (A3)

The distribution $P_{\xi}$ satisfies the following condition: $\Pr[\xi\leq
0]=\Pr[\xi\geq 0]=1/2$; it admits a probability density function
$f_{\xi}(\cdot)$; there exist constants $0<c_{\xi}\leq C_{\xi}<\infty$ such
that $\sup_{\xi\in\mathbb{R}}f_{\xi}(\xi)\leq C_{\xi}$ and $\inf_{|\xi|\leq
2}f_{\xi}(\xi)\geq c_{\xi}$.

Assumption (A1) is a standard bounded assumption imposed on model parameters.
Assumption (A2) assumes that the contextual vectors are independently and
identically distributed, with respect to a bounded and non-degenerate
distribution $P_{X}$ that is unknown. Similar “non-degenerate” or “covariate
diversity” assumptions were also adopted in the contextual learning literature
(Bastani and Bayati 2020, Bastani et al. 2021), and the assumption is actually
weaker than some of the existing works on active learning (Balcan et al. 2007,
Wang and Singh 2016), which requires $P_{X}$ to be the exact uniform
distribution over $\mathbb{B}_{2}(d)$.

Assumption (A3) is a general condition imposed on the distribution $P_{\xi}$
of the noise variables. Essentially, it assumes that zero is the median of the
noise distribution $P_{\xi}$, which ensures that the linear classifier is the
optimal Bayes classifier. The same assumption is common in the active learning
literature (Balcan et al. 2007, Wang and Singh 2016). Note that we do not
assume the noise distribution $P_{\xi}$ has any specific parametric forms
(e.g., Logistic or Probit noises), making it generally applicable to a broad
range of problems.

##  3 Margin-based Active Learning with Tri-section Search

Algorithm 1 A meta-algorithm for actively learning contextual functions.

1:Input: dimension $d$, accuracy parameters $\varepsilon,\delta$, algorithm
parameters $\kappa_{m},\kappa_{n},\kappa_{\varepsilon},\beta_{0}$.

2:$\widehat{b}_{1},\widehat{b}_{2}\leftarrow\textsc{TrisectionSearch}(\varepsilon_{s},\delta_{s})$
with $\varepsilon_{s}=0.1/\sqrt{d-1}$, $\delta_{s}=\delta/3$;

3:Let
$\varepsilon_{a}=\kappa_{\varepsilon}{\varepsilon^{2}}/\ln^{2}(1/\varepsilon)$,
$\delta_{a}=\delta/3$;

4:$(\widehat{w}_{1},\widehat{\beta}_{1})\leftarrow\textsc{MarginBasedActiveLearning}(\widehat{b}_{1},\varepsilon_{a},\delta_{a},\kappa_{m},\kappa_{n},\sqrt{\varepsilon_{a}},\beta_{0})$;

5:$(\widehat{w}_{2},\widehat{\beta}_{2})\leftarrow\textsc{MarginBasedActiveLearning}(\widehat{b}_{2},\varepsilon_{a},\delta_{a},\kappa_{m},\kappa_{n},\sqrt{\varepsilon_{a}},\beta_{0})$;

6:Let
$\widehat{\alpha}=(\widehat{b}_{2}-\widehat{b}_{1})/(\widehat{\beta}_{2}-\widehat{\beta}_{1})$;

7:Output: utility function estimate
$\widehat{v}(\cdot)=\langle\cdot,\widehat{w}\rangle-\widehat{\mu}$, where
$\widehat{w}=\widehat{\alpha}\widehat{w}_{1}$ and
$\widehat{\mu}=\widehat{\alpha}\widehat{\beta}_{1}-\widehat{b}_{1}$.

The main algorithm we proposed for actively learning contextual functions is
given in Algorithm 1. The main idea of the proposed algorithm can be
summarized as follows.

The first step is to find two actions or bidding prices
$\widehat{b}_{1},\widehat{b}_{2}$ that are reasonably close to the mean
utility $\mu^{*}$. This is to ensure that when the actions are fixed at
$\widehat{b}_{1}$ or $\widehat{b}_{2}$, the labels received from user streams
are relatively balanced, thereby circumventing the negative results in the
work of Dasgupta (2005b). In Sec. 3.1 we show how
$\widehat{b}_{1},\widehat{b}_{2}$ can be found without using too much labeled
samples, by using a trisection search idea.

After we obtained candidate bidding prices $\widehat{b}_{1}$ and
$\widehat{b}_{2}$, we use a margin-based active learning algorithm to estimate
the linear model $w^{*}$ and mean utility $\mu^{*}$. The margin-based active
learning algorithm is similar to the work of Balcan et al. (2007), with the
difference being that in our setting the active learning algorithm needs to
incorporate a (relatively small) intercept term, which complicates its design
and analysis.

Finally, we use the estimates $(\widehat{w}_{1},\widehat{\beta}_{1})$ and
$(\widehat{w}_{2},\widehat{\beta}_{2})$ obtained from the above-mentioned
active learning procedure _under two different fixed actions
$\widehat{b}_{1},\widehat{b}_{2}$_ to reconstruct the linear utility
parameters $w^{*}$ and $\mu^{*}$. The reason we need two fixed actions
$\widehat{b}_{1},\widehat{b}_{2}$ is because the active learning procedure
solves a classification problem, for which we can only estimate the linear
model and its intercept _up to scalings_ because if one multiply both the
linear model and its intercept by a constant the resulting classification
problem is the same. Hence, we need two fixed actions
$\widehat{b}_{1},\widehat{b}_{2}$ to construct an approximate linear system of
equations, the solution of which would give as consistent estimates of $w^{*}$
and $\mu^{*}$.

Below we briefly explain our intuition behind the construction of the utility
function estimate $\widehat{v}(\cdot)$ in Algorithm 1. For simplicity we will
omit the learning errors occurred in the two MarginBasedActiveLearing
invocations. Because the margin based active learning algorithm learns linear
classifiers up to normalization (see Algorithm 3), we have the following
equivalence:

$\displaystyle\langle\widehat{w}_{1},x\rangle-\widehat{\beta}_{1}>0$
$\displaystyle\Longleftrightarrow$ $\displaystyle\langle
w^{*},x\rangle-\mu^{*}>\widehat{b}_{1};$
$\displaystyle\langle\widehat{w}_{2},x\rangle-\widehat{\beta}_{2}>0$
$\displaystyle\Longleftrightarrow$ $\displaystyle\langle
w^{*},x\rangle-\mu^{*}>\widehat{b}_{2},$

where $\|\widehat{w}_{1}\|_{2}=\|\widehat{w}_{2}\|_{2}=1$ due to the
construction of Algorithm 3. Again, we emphasize that the above equivalence
only holds approximately due to learning errors of
$\widehat{w}_{1},\widehat{\beta}_{1},\widehat{w}_{2},\widehat{\beta}_{2}$, but
we will omit these learning errors for the ease of explanation. Let
$\alpha=\|w^{*}\|_{2}$. We have
$\widehat{\beta}_{1}=(\mu^{*}+\widehat{b}_{1})/\alpha$ and
$\widehat{\beta}_{2}=(\mu^{*}+\widehat{b}_{2})/\alpha$. Therefore, we set
$\widehat{\alpha}=(\widehat{b}_{2}-\widehat{b}_{1})/(\widehat{\mu}_{2}-\widehat{\mu}_{1})$
as the estimate of $\alpha$, and
$\widehat{\mu}=\widehat{\alpha}\widehat{\beta}_{1}-\widehat{b}_{1}$ as the
estimate of $\widehat{\mu}$. Thus, we obtain the utility function estimate
$\widehat{v}(\cdot)$ in Algorithm 1.

###  3.1 Tri-section search for accurate mean utility

Algorithm 2 A tri-section search algorithm to roughly estimate the mean
utility parameter $\mu^{*}$

1:function TrisectionSearch($\varepsilon_{s},\delta_{s}$)

2: Initialize: sample counter $n=0$, lower and upper bounds
$\widehat{b}_{1}=-B$, $\widehat{b}_{2}=B$;

3: while $\widehat{b}_{2}-\widehat{b}_{1}>\varepsilon_{s}$ do

4:
$\widehat{b}_{3}\leftarrow\widehat{b}_{1}+(\widehat{b}_{2}-\widehat{b}_{1})/3$,
$\widehat{b}_{4}\leftarrow\widehat{b}_{2}-(\widehat{b}_{2}-\widehat{b}_{1})/3$,
$\widehat{n}=\widehat{r}_{3}=\widehat{r}_{4}=0$,
$\underline{p}_{3}=\underline{p}_{4}=0$,
$\overline{p}_{3}=\overline{p}_{4}=1$;

5: while $\underline{p}_{3}\leq 0.5\leq\overline{p}_{3}$ and
$\underline{p}_{4}\leq 0.5\leq\overline{p}_{4}$ do

6: For an incoming user $x$, take action $\widehat{b}_{3}$ and observe result
$y\in\\{0,1\\}$;

7: For another incoming user $x^{\prime}$, take action $\widehat{b}_{4}$ and
observe result $y^{\prime}\in\\{0,1\\}$;

8: $n\leftarrow n+1$, $\widehat{n}\leftarrow\widehat{n}+1$,
$\widehat{r}_{3}=\widehat{r}_{3}+\boldsymbol{1}\\{y_{3}=1\\}$,
$\widehat{r}_{4}=\widehat{r}_{4}+\boldsymbol{1}\\{y_{4}=1\\}$;

9: Update:
$[\underline{p}_{3},\overline{p}_{3}]\leftarrow\frac{\widehat{r}_{3}}{\widehat{n}}\pm\sqrt{\frac{\ln(8n^{2}/\delta_{s})}{2\widehat{n}}}]$
and
$[\underline{p}_{4},\overline{p}_{4}]\leftarrow\frac{\widehat{r}_{4}}{\widehat{n}}\pm\sqrt{\frac{\ln(8n^{2}/\delta_{s})}{2\widehat{n}}}]$;

10: end while

11: Set $\widehat{b}_{1}\leftarrow\widehat{b}_{3}$ if $\underline{p}_{3}>0.5$
or $\underline{p}_{4}>0.5$ and $\widehat{b}_{2}\leftarrow\widehat{b}_{4}$
otherwise;

12: end while

13: return $(\widehat{b}_{1},\widehat{b}_{2})$.

14:end function

Let $b^{*}\in\mathbb{R}$ be the unique value such that $\Pr_{x\sim
P_{X}}[v(x)\geq b^{*}]=1/2$. Because $P_{X}$ and $P_{\xi}$ have PDFs, such a
value of $b^{*}$ exists and is unique. Intuitively, if one commits to the
fixed action $b^{*}$ then the labels received by the algorithm should be
balanced. Algorithm 2 shows how to find actions
$\widehat{b}_{1},\widehat{b}_{2}$ that are reasonably close to $b^{*}$,
without consuming too many labeled samples.

Figure 2: Graphical illustration of the main idea behind Algorithm 2.

Note: the left panel shows the first case of the trisection search, in which
$\wp(b_{3})=\mathbb{E}_{x\sim P_{X}}[y|x,w^{*},\mu^{*},b_{3}]>1/2$. Once
$\underline{p}_{3}$ exceeds $1/2$, the algorithm will move $b_{1}$ to $b_{3}$.
The right panel shows the second case of the trisection search, in which
$\wp(b_{4})=\mathbb{E}_{x\sim P_{X}}[y|x,w^{*},\mu^{*},b_{4}]<1/2$. As both
$\overline{p}_{3},\overline{p}_{4}$ are below 1/2, the algorithm will move
$b_{2}$ to $b_{4}$. The strict monotonicity of $\wp(\cdot)$ as a function of
$b$ ensures that the trisection search will never exclude $b^{*}$ from
$[b_{1},b_{4}]$, and that the search will terminate in $O(d\log(d/\delta))$
iterations (see Lemma 3.2).

The main idea behind Algorithm 2 is a trisection search approach, motivated by
the fact that the probability $\Pr_{x\sim P_{X}}[v(x)\geq b]$ is a
monotonically decreasing function of $b$, and furthermore as $|b-b^{*}|$
increases the gap between $\Pr_{x\sim P_{X}}[v(x)\geq b]$ and $\Pr_{x\sim
P_{X}}[v(x)\geq b^{*}]=1/2$ will also increase (see, e.g., Lemma 4.1 in the
proof). This allows us to use a trisection search procedure to localize the
value of $b^{*}$, by simply comparing an empirical estimate of $\Pr_{x\in
P_{X}}[v(x)\geq b]$ at the current value of $b$. More specifically, at an
iteration $\widehat{b}_{3},\widehat{b}_{4}$ are the two midpoints and
$[\underline{p}_{3},\overline{p}_{3}]$ are lower and upper estimates of
$\Pr_{x\sim P_{X}}[v(x)\geq\widehat{b}_{3}]$ and similarly
$[\underline{p}_{4},\overline{p}_{4}]$ are lower and upper estimates for
$\Pr_{x\sim P_{X}}[v(x)\geq\widehat{b}_{4}]$. With either probabilities being
separated from $1/2$, the algorithm could move $\widehat{b}_{1}$ or
$\widehat{b}_{2}$ to $\widehat{b}_{3}$ or $\widehat{b}_{4}$. The algorithm is
guaranteed to maintain that $b^{*}\in[\widehat{p}_{1},\widehat{p}_{2}]$,
thanks to the monotonicity of $\Pr_{x\sim P_{X}}[v(x)\geq b]$ with respect to
$b$.

The following technical lemmas are the main results explaining the objective
and guarantee of Algorithm 2, which are proved in Sec. 4.1.

###### Lemma 3.1

Suppose $d\geq 2$ and let $\beta^{*}=b^{*}+\mu^{*}$. Then
$\frac{|\beta^{*}|}{\|w^{*}\|_{2}}\leq\sqrt{\frac{2\ln(100C_{x}C_{\xi}/c_{x}c_{\xi})}{d-1}}=O(1/\sqrt{d})$.

###### Lemma 3.2

Suppose $d\geq 2$ and let $(\widehat{b}_{1},\widehat{b}_{2})$ be the values
returned by $\textsc{BisectionSearch}(\varepsilon_{s},\delta_{s})$. With
probability $1-\delta_{s}$ the following hold: $\widehat{b}_{1}\leq
b^{*}\leq\widehat{b}_{2}$, and at most
$O(\varepsilon_{s}^{-2}\log(1/\delta_{s}\varepsilon_{s}))=O(d\log(d/\delta))$
queried samples are consumed.

Intuitively, Lemma 3.1 establishes that the “balancing” intercept $b^{*}$ is
$O(1/\sqrt{d})$ close to the intercept $\mu^{*}$ in the utility model, which
is helpful for our later analysis. Lemma 3.2 further establishes that the
returned two actions $\widehat{b}_{1},\widehat{b}_{2}$ sandwich the “label-
balancing” action $b^{*}$, and also upper bound the total number of labeled
(queried) samples consumed in the algorithmic procedure.

###  3.2 Margin-based Active Learning

In Algorithm 3 we provide the pseudocode description of the margin based
active learning algorithm we use in this problem to actively learn a linear
model with intercepts.

Algorithm 3 Margin-based Active Learning Non-homogeneous Linear Classifiers

1:function
MarginBasedActiveLearning($b,\varepsilon_{a},\delta_{a},\kappa_{m},\kappa_{n},\epsilon_{0},\beta_{0}$)

2: Collect $n_{0}=\lceil\kappa_{n}/\epsilon_{0}^{2}\rceil$ samples with action
$b$ and let $\mathcal{D}_{0}=\\{(x,y)\\}\subseteq\mathbb{B}_{d}(2)\times\\{\pm
1\\}$, $|\mathcal{D}_{0}|=n_{0}$ be the queried samples;

3: Let
$\widehat{w}_{0},\widehat{\beta}_{0}\leftarrow\arg\min_{\|w\|_{2}=1,|\beta|\leq\beta_{0}}\sum_{(x,y)\in\mathcal{D}_{0}}\boldsymbol{1}\\{y\neq\mathrm{sgn}(\langle
x,w\rangle-\beta)\\}$;

4: Let $k_{0}=\min\\{k\in\mathbb{N}:2^{-k}\epsilon_{0}\leq\varepsilon_{a}\\}$;

5: for $k=1,2,\cdots,k_{0}$ do

6: $\epsilon_{k}\leftarrow 2^{-k}\epsilon_{0}$,
$m_{k}\leftarrow\kappa_{m}\sqrt{\epsilon_{k}}$,
$n_{k}\leftarrow\lceil\kappa_{n}d/\epsilon_{k}\rceil$,
$\mathcal{D}_{k}=\emptyset$;

7: while $|\mathcal{D}_{k}|<n_{k}$ do

8: Observe context vector $x\in\mathbb{R}^{d}$ for the next object;

9: if $|\langle x,\widehat{w}_{k-1}\rangle-\widehat{\beta}_{k-1}|\leq m_{k}$
then

10: Invoke action $b$ and let $y\in\\{\pm 1\\}$ be the collected binary
feedback;

11: Update $\mathcal{D}_{k}\leftarrow\mathcal{D}_{k}\cup\\{x,y\\}$;

12: end if

13: end while

14:
$\widehat{w}_{k},\widehat{\beta}_{k}\leftarrow\arg\min_{\|w\|_{2}=1,|\beta|\leq\beta_{0}}\sum_{(x,y)\in\mathcal{D}_{k}}\boldsymbol{1}\\{y\neq\mathrm{sgn}(\langle
x,w\rangle-\beta)\\}$;

15: end for

16: return $\widehat{w}_{k_{0}},\widehat{\beta}_{k_{0}}$.

17:end function

Note that in Algorithm 3 the query point $b$ is fixed, with the algorithm only
able to select which sample/contextual vector to act upon. Since the query
point $b$ is fixed, we can consider linear models with intercepts as
$\widehat{v}(\cdot)=\langle\cdot,\widehat{w}\rangle-\widehat{\beta}$. For such
a model, we define the _error_ of $\widehat{v}$ under the query point $b$ as

$\mathrm{err}_{b}(\widehat{v}):=\Pr_{x\sim P_{X},\xi\sim
P_{\xi}}\big{[}\mathrm{sgn}(\underbrace{v(x)+\xi}_{u(x)}-b)\neq\mathrm{sgn}(\widehat{v}(x))\big{]},$
(3)

where $v(x)=\langle x,w^{*}\rangle-\mu^{*}$. Note that for any
$b\in\mathbb{R}$, the model
$v_{b}^{*}(\cdot):=\langle\cdot,w^{*}\rangle-\mu^{*}-b$ has the smallest error
defined in Eq. (3), This is because $v_{b}^{*}(\cdot)$ is the Bayes
classifier; that is, $v_{b}^{*}(x)\geq 0$ if and only if $\Pr[v(x)+\xi\geq
b|x]\geq 1/2$. Hence, we can also define the _excess error_ of a model
$\widehat{v}(\cdot)$ as

$\Delta\mathrm{err}_{b}(\widehat{v}):=\mathrm{err}_{b}(\widehat{v})-\mathrm{err}_{b}(v_{b}^{*}).$
(4)

Figure 3: Graphical illustration of the main idea of Algorithm 3.

Note: the left panel shows the initialization step (Lines 2 and 4) of
Algorithm 3. In the initialization step, sample selection is not carried out
and the obtained model estimates $\widehat{w}_{0},\widehat{\beta}_{0}$ have
error upper bounded by $\varepsilon_{0}$. The right panel shows the first
iteration of Algorithm 3. As shown in the figure, only those samples that are
within an $m_{1}$ margin around $\widehat{w}_{0},\widehat{\beta}_{0}$ (those
within the blue dashed lines) are labeled/queried. After the first iteration,
a more refined estimate $\widehat{w}_{1},\widehat{\beta}_{1}$ is obtained and
a shrunk margin $m_{2}$ is imposed (marked with maroon) for the next
iteration.

Figure 3 illustrates the principles of Algorithm 3. The main idea of Algorithm
3 is simple: the algorithm first uses a “warm-up” epoch consisting of $n_{0}$
queried samples to construct a preliminary model estimate $\widehat{w}_{0}$
and $\widehat{\beta}_{0}$. There is no sample selection or active learning in
this warm-up procedure, and the analysis of excess errors of
$\widehat{w}_{0},\widehat{\beta}_{0}$ follow standard VC theory analyzing
empirical risk minimizers of binary classifiers (see e.g. Lemma A.5 in the
proof and also Balcan et al. (2007), Vapnik and Chervonenkis (2015), Vapnik
(2013)). Next, in each epoch the algorithm only take action $b$ for those
users with contextual vectors that are _close_ to the current classification
hyperplane (i.e., those users with small “margin” $|\langle
x,\widehat{w}_{k-1}\rangle-\widehat{\beta}_{k-1}|$). This concentrates our
labeled/queried samples to the region that are close to the classification
hyperplane, which helps reduce the number of queried samples as the queried
samples are collected on regions that are the most uncertain from a binary
classification perspective.

The following lemma is the main result of this section, which is proved in
Sec. 4.2.

###### Lemma 3.3

Let $(\widehat{w},\widehat{\beta})$ be returned by Algorithm 3 with parameters
satisfying $|\mu^{*}-b|/\|w^{*}\|_{2}\leq\beta_{0}=O(1/\sqrt{d})$,
$\kappa_{m}=\Omega(1)$,
$\kappa_{n}=\Omega(d+\log\log(1/\varepsilon_{a})+\log(1/\delta_{a}))$ and
$\epsilon_{0}=\sqrt{\varepsilon_{a}}$. Let
$\widehat{v}(\cdot)=\langle\cdot,\widehat{w}\rangle-\widehat{\beta}$. Then for
sufficiently large $d$ and sufficiently small $\varepsilon_{a}$, with
probability $1-\delta_{a}$ the following hold:

  1. 1.

$\Delta\mathrm{err}(\widehat{v})\leq\varepsilon_{a}$;

  2. 2.

Algorithm 3 consumes $O(\kappa_{n}d/\varepsilon_{a})$ queried samples and
$O(\kappa_{n}\sqrt{d}e^{d\varepsilon_{a}}/\varepsilon_{a}^{3/2})$ total
samples.

Essentially, Lemma 3.3 shows that the estimated linear model
$\widehat{v}(\cdot)$ produced by Algorithm 3 has the target excess risk
$\varepsilon_{a}$ with high probability. The lemma also upper bounds the
number of queried and total samples consumed in the estimation procedure. As
we can see, the number of labeled samples required is on the order of
$O(1/\varepsilon_{a})$, which is an order of magnitude fewer than the total
number of samples consumed (on the order of $O(1/\varepsilon^{3/2})$). This
shows that the active learning procedure is capable of drastically reducing
the number of queried samples required to attain an accurate model estimate
$\widehat{v}$, by being selective in the user context vectors.

###  3.3 Sample complexity analysis of Algorithm 1

In this section we establish the following theorem, which analyzes the sample
complexity (both samples that are queried on and samples that are passed) of
Algorithm 1, and provides guidance on the selection of the algorithm input
parameters.

###### Theorem 3.4

Suppose Algorithm 1 is executed with $\kappa_{m}\asymp 1$, $\kappa_{n}\asymp
d+\log\log(1/\varepsilon)+\log(1/\delta)$, $\kappa_{\varepsilon}\asymp 1/d$
and $\beta_{0}\asymp 1/\sqrt{d}$. Then for sufficiently small $\varepsilon>0$
and sufficiently large $d$, with probability $1-\delta$ it holds that
$|\widehat{v}(x)-v(x)|\leq\varepsilon$ for all $x\in\mathbb{B}_{2}(d)$.
Furthermore, the algorithm makes $n(\delta,\varepsilon)$ queries among
$m(\delta,\varepsilon)$ total samples/contexts, with

$\displaystyle n(\delta,\varepsilon)$ $\displaystyle=$ $\displaystyle
O\left(\frac{d^{3}\log(d\log(d\varepsilon^{-1})/\delta)\log^{2}(1/\varepsilon)}{\varepsilon^{2}}\right),$
$\displaystyle m(\delta,\varepsilon)$ $\displaystyle=$ $\displaystyle
O\left(\frac{d^{3}\log(d\log(d\varepsilon^{-1})/\delta)\log^{3}(1/\varepsilon)}{\varepsilon^{3}}\right).$

###### Remark 3.5

If the decision-maker needs to make queries to all incoming contexts/samples
(i.e., skipping uninformative samples is not allowed), then at least
$\Omega(d/\varepsilon^{4})$ samples are required. To see this, note that the
standard classification theory establishes that $\Omega(d/\varepsilon^{2})$
samples are needed to obtain a linear classifier $\widehat{w}$ such that
$\Pr[\mathrm{sgn}(\widehat{w}^{\top}x)\neq\mathrm{sgn}((w^{*})^{\top}x)]\leq\varepsilon$
(see, e.g., Mammen and Tsybakov (1999), Ben-David and Urner (2014)). On the
other hand, it can be shown via an integration argument as follows. Let
$\angle(\widehat{w},w^{*})$ denote the angle between $\widehat{w}$ and
$w^{*}$. If both $\widehat{w},w^{*}$ are normalized (i.e.,
$\|\widehat{w}\|_{2}=\|w^{*}\|_{2}=1$) and
$\|\widehat{w}-w^{*}\|_{2}\approx\angle(\widehat{w},w^{*})\approx\varepsilon$
then
$\Pr_{x}[\mathrm{sgn}(\widehat{w}^{\top}x)\neq\mathrm{sgn}((w^{*})^{\top}x)]\approx\varepsilon^{2}$.
This shows that in order to achieve
$|\widehat{v}(\cdot)-v(\cdot)|\leq\varepsilon$ we must have
$\Pr_{x}[\mathrm{sgn}(\widehat{w}^{\top}x)\neq\mathrm{sgn}((w^{*})^{\top}x)]\lesssim{\varepsilon}^{2}$,
indicating a sample complexity lower bound of
$\Omega(d/(\varepsilon^{2})^{2})=\Omega(d/\varepsilon^{4})$.

Theorem 3.4 shows that, by using more unlabeled/unqueried samples than those
that are labeled (more specifically, $1/\varepsilon^{3}$ total samples and
$1/\varepsilon^{2}$ labeled ones), the utility function estimate
$\widehat{v}(\cdot)$ produced by our active learning algorithm is within
$\varepsilon$ estimation error with high probability. In Sec. 5 of numerical
studies, we will see that the availability of unlabeled samples will greatly
improve the estimation accuracy of an active learning algorithm, compared to a
passive learning baseline which cannot skip or select samples to query.

##  4 Technical Proofs

In this section we state the proofs of the main results in this paper. There
are also some technical lemmas that either easy to prove, or cited/rephrased
from existing works, which will be presented in the appendix. For simplicity,
let $P_{U}$ be the uniform distribution on
$\mathbb{B}_{2}(d)=\\{x\in\mathbb{R}^{d}:\|x\|_{2}\leq 1\\}$ for all proofs in
this section.

###  4.1 Proof of results in Sec. 3.1

####  4.1.1 Proof of Lemma 3.1.

First note that $\langle w^{*},x\rangle-\mu^{*}\geq b^{*}$ is equivalent to
$\langle w^{*},x\rangle-\beta^{*}\geq 0$, with $\beta^{*}=\mu^{*}+b^{*}$. Note
also that we may assume $\|w^{*}\|_{2}=1$ because $|\beta^{*}|/\|w^{*}\|_{2}$
is invariant to $\|w^{*}\|_{2}$. In this proof we shall use the lower and
upper bounds of $f_{x}$ by connecting it with the uniform distribution on
$\mathbb{B}_{2}(d)$, $P_{U}$. Because $P_{U}$ is isotropic, we may assume
without loss of generality that $w^{*}=(1,0,\cdots,0)$ and $\beta^{*}\geq 0$.
We will also abbreviate $\eta=\eta_{b^{*}}$ and $\Delta=\Delta_{b^{*}}$ since
all margins in this proof are with respect to $b^{*}$. Then for all
$x\in\mathbb{B}_{2}(d)$ with $x_{1}\geq\beta^{*}$, $\eta(x)\geq 1/2$ and
further more

$\eta(x)-\frac{1}{2}=\phi(x_{1}-\beta^{*})=\int_{0}^{x_{1}-\beta^{*}}\phi^{\prime}(u)\mathrm{d}u\leq
C_{\xi}(x_{1}-\beta^{*}).$

Subsequently, by Assumption (A2) and Lemma A.1, it holds that

$\displaystyle\int_{x_{1}\geq\beta^{*}}$
$\displaystyle\left(\eta(x)-\frac{1}{2}\right)\mathrm{d}P_{x}(x)\leq
C_{x}\int_{x_{1}\geq\beta^{*}}\left(\eta(x)-\frac{1}{2}\right)\mathrm{d}P_{U}(x)\leq
C_{x}C_{\xi}\int_{x_{1}\geq\beta^{*}}(x_{1}-\beta^{*})\mathrm{d}P_{U}(x)$
$\displaystyle\leq
C_{x}C_{\xi}\int_{0}^{1}\sqrt{\frac{d+1}{2\pi}}e^{-(d-1)(\beta^{*}+\gamma)^{2}/2}\gamma\mathrm{d}\gamma\leq
C_{x}C_{\xi}\sqrt{d}e^{-(d-1)(\beta^{*})^{2}/2}\int_{0}^{1}\gamma
e^{-(d-1)\gamma^{2}/2}\mathrm{d}\gamma.$ (5)

With $\gamma\mapsto\gamma/\sqrt{d-1}$, we have $\int_{0}^{1}\gamma
e^{-(d-1)\gamma^{2}/2}\mathrm{d}\gamma\leq\sqrt{\frac{2\pi}{d-1}}\mathbb{E}_{z\sim\mathcal{N}(0,1/(d-1))}[|z|]/2\leq
1/(d-1)$. Noting that $\sqrt{d}\leq\sqrt{2(d-1)}$ for $d\geq 2$, Eq. (5) can
then be simplified to

$\int_{x_{1}\geq\beta^{*}}\left(\eta(x)-\frac{1}{2}\right)\mathrm{d}P_{x}(x)\leq\frac{\sqrt{2}C_{x}C_{\xi}}{\sqrt{d-1}}e^{-(d-1)(\beta^{*})^{2}/2}.$
(6)

On the other hand, for all $x\in\mathbb{B}_{2}(d)$ with $x_{1}\leq\beta^{*}$,
$\eta(x)\leq 1/2$ and furthermore

$\frac{1}{2}-\eta(x)=-\phi(x_{1}-\beta^{*})=\int_{0}^{\beta^{*}-x_{1}}\phi^{\prime}(u)\mathrm{d}u\geq
c_{\xi}(\beta^{*}-x_{1}).$

Subsequently, by Assumption (A2) and Lemma A.1, it holds that

$\displaystyle\int_{x_{1}\leq\beta^{*}}$
$\displaystyle\left(\frac{1}{2}-\eta(x)\right)\mathrm{d}P_{x}(x)\geq
c_{x}\int_{x_{1}\leq 0}\left(\frac{1}{2}-\eta(x)\right)\mathrm{d}P_{U}(x)\geq
c_{x}c_{\xi}\int_{x_{1}\leq 0}(\beta^{*}-x_{1})\mathrm{d}P_{U}(x)$
$\displaystyle\geq c_{x}c_{\xi}\int_{x_{1}\leq 0}-x_{1}\mathrm{d}P_{U}(x)\geq
c_{x}c_{\xi}\int_{0}^{1}\sqrt{\frac{d+1}{16\pi}}e^{-(d-1)\gamma^{2}/2}\gamma\mathrm{d}\gamma\geq\frac{c_{x}c_{\xi}\sqrt{d}}{4\sqrt{\pi}}\int_{1/\sqrt{d-1}}^{\sqrt{2}/\sqrt{d-1}}e^{-(d-1)\gamma^{2}/2}\gamma\mathrm{d}\gamma$
$\displaystyle\geq\frac{c_{x}c_{\xi}\sqrt{d}}{4\sqrt{\pi}}\times\frac{1}{e\sqrt{d-1}}\times\frac{\sqrt{2}-1}{\sqrt{d-1}}\geq\frac{(\sqrt{2}-1)c_{x}c_{\xi}}{4e\sqrt{\pi(d-1)}}.$
(7)

Combining Eqs. (5,7) we obtain

$\frac{1}{2}=\Pr_{x\sim
P_{x}}[y=1|b^{*}]\leq\frac{1}{2}+\frac{\sqrt{2}C_{x}C_{\xi}}{\sqrt{d-1}}e^{-(d-1)(\beta^{*})^{2}/2}-\frac{(\sqrt{2}-1)c_{x}c_{\xi}}{4e\sqrt{\pi(d-1)}}.$

To satisfy the above inequality, $\beta^{*}\geq 0$ must satisfy

$\beta^{*}\leq\sqrt{\frac{2\ln(100C_{x}C_{\xi}/c_{x}c_{\xi})}{d-1}}=O(1/\sqrt{d}),$

which proves Lemma 3.1.

####  4.1.2 Proof of Lemma 3.2.

For notational simplicity define $\wp(\widehat{b}):=\Pr_{x\sim
P_{x}}[v(x)\geq\widehat{b}]$. Clearly, $\wp(b^{*})=1/2$ and $\wp(\cdot)$ is a
monotonically decreasing function. By Hölder inequality, at sample $n$ we have
$\Pr[\wp(\widehat{b}_{3})\in[\underline{p}_{3},\overline{p}_{3}]]\geq
1-2e^{-2\widehat{n}\times\ln(8n^{2}/\delta_{s})/(2\widehat{n})}\geq
1-\frac{\delta_{s}}{4n^{2}}$. The same inequality holds for
$\Pr[\wp(\widehat{b}_{4})\in[\underline{p}_{4},\overline{p}_{4}]]$ as well. By
the union bound, the probability that
$\wp(\widehat{b}_{3})\in[\underline{p}_{3},\overline{p}_{3}]$ and
$\wp(\widehat{b}_{4})\in[\underline{p}_{4},\overline{p}_{4}]$ throughout the
entire Algorithm 2 is lower bounded by

$1-\sum_{n\geq
1}2\times\frac{\delta_{s}}{4n^{2}}=1-\frac{\delta_{s}}{2}\sum_{n\geq
1}\frac{1}{n^{2}}\geq 1-\frac{\delta_{s}}{2}\frac{\pi^{2}}{6}\geq
1-\delta_{s}.$

This shows that with probability $1-\delta_{s}$ the
$(\widehat{b}_{1},\widehat{b}_{2})$ pair returned by Algorithm 2 satisfies
$\widehat{b}_{1}\leq b^{*}\leq\widehat{b}_{2}$ due to the monotonicity of the
$\wp(\widehat{b})$ function.

To analyze the number of queried samples/objects by Algorithm 2, we require
some additional technical results. The following lemma connects the deviation
$|\wp(\widehat{b})-1/2|$ with $|\widehat{b}-b^{*}|$.

###### Lemma 4.1

Recall the definition that $\wp(\widehat{b})=\Pr_{x\sim
P_{x}}[w(x)\geq\widehat{b}]$ and $b^{*}$ such that $\wp(b^{*})=1/2$. Then
$0.07c_{x}c_{\xi}|\widehat{b}-b^{*}|\leq|\wp(\widehat{b})-1/2|\leq
C_{\xi}|\widehat{b}-b^{*}|$.

###### Proof 4.2

Proof of Lemma 4.1. Define $\beta^{*}=b^{*}+\mu^{*}$ and
$\widehat{\beta}=\widehat{b}+\mu^{*}$. Define also
$s:=\widehat{\beta}-\beta^{*}$, so that $\widehat{\beta}=\beta^{*}+s$. Recall
the definition of margin that $\Delta_{b^{*}}(x)=v(x)-\beta^{*}$, and
$\Pr[y=1|x,b^{*}]=\phi(\Delta_{b^{*}}(x))$. Under $\widehat{b}$, we have
$\Delta_{\widehat{b}}(x)=v(x)-\widehat{\beta}=\Delta_{b^{*}}(x)-s$ and
$\Pr[y=1|x,\widehat{b}]=\phi(\Delta_{b^{*}}(x)-s)$. Subsequently,

$\displaystyle\big{|}\wp(\widehat{b})-\wp(b^{*})\big{|}$
$\displaystyle\leq\mathbb{E}_{x\sim
P_{x}}\left[\big{|}\phi(\Delta_{b^{*}}(x)-s)-\phi(\Delta_{b^{*}}(x))\big{|}\right]\leq\sup_{|\gamma|\leq
1}\big{|}\phi(\gamma-s)-\phi(\gamma)\big{|}\leq C_{\xi}|s|.$

This proves the upper bound on $|\wp(\widehat{b})-1/2|$.

We next consider the lower bound of $|\wp(\widehat{b})-1/2|$. Without loss of
generality assume $\beta^{*}\geq 0$, $w^{*}=(1,0,\cdots,0)$ and $s\geq 0$. We
will lower bound $|\wp(\widehat{b})-1/2|$ by study the decrease of
$\Pr[y=1|x]$ on the ball segment
$\mathbb{B}_{2}(d)\cap\\{x\in\mathbb{R}^{d}:-r\leq x_{1}\leq 0\\}$ with
$r=1/\sqrt{2(d-1)}\leq 1/\sqrt{2}$ for $d\geq 2$. More specifically,

$\displaystyle\big{|}\wp(\widehat{b})$
$\displaystyle-1/2\big{|}\geq\int_{r\leq x_{1}\leq
0}\big{[}\phi(\beta^{*}-x_{1})-\phi(\beta^{*}-x_{1}-s)\big{]}\mathrm{d}P_{X}(x)$
$\displaystyle\geq c_{x}\int_{r\leq x_{1}\leq
0}\big{[}\phi(\beta^{*}-x_{1})-\phi(\beta^{*}-x_{1}-s)\big{]}\mathrm{d}P_{U}(x)$
(8) $\displaystyle\geq
c_{x}\int_{0}^{r}\sqrt{\frac{d+1}{16\pi}}e^{-(d-1)\gamma^{2}/2}\big{[}\phi(\beta^{*}+\gamma)-\phi(\beta^{*}+\gamma-s)\big{]}\mathrm{d}\gamma$
(9) $\displaystyle\geq
c_{x}\int_{0}^{r}\sqrt{\frac{d+1}{16\pi}}e^{-(d-1)\gamma^{2}/2}c_{\xi}s\mathrm{d}\gamma$
(10) $\displaystyle\geq c_{x}r\times\sqrt{\frac{d+1}{16\pi}}\times
e^{-(d-1)r^{2}/2}\times
c_{\xi}s=\frac{c_{x}c_{\xi}s}{4\sqrt{2\pi\sqrt{e}}}\geq 0.07c_{x}c_{\xi}s.$
(11)

Here Eq. (8) is due to Assumption (A2), Eq. (9) is due to Lemma A.1, and Eq.
(10) is due to Assumption (A3). $\square$

We are now ready to analyze the number of queried samples in Algorithm 2. Fix
an arbitrary pair of $(\widehat{b}_{1},\widehat{b}_{2})$ at outer iteration
$\tau$ such that
$\widehat{b}_{2}-\widehat{b}_{1}=\varepsilon_{\tau}=2(2/3)^{\tau}B\geq\varepsilon_{a}$.
Then either $|\widehat{b}_{3}-b^{*}|\geq\varepsilon_{\tau}/6$ or
$|\widehat{b}_{4}-b^{*}|\geq\varepsilon_{\tau}/6$. Let $\widehat{n}_{\tau}$ be
the final count of $\widehat{n}_{\tau}$ when outer iteration $\tau$ ends. The
condition $0.5\in[\underline{p}_{3},\overline{p}_{3}]\wedge
0.5\in[\underline{p}_{4},\overline{p}_{4}]$ in the inside while loop will be
violated if
$\sqrt{\ln(8n_{\tau}^{2}/\delta_{s})/2\widehat{n}_{\tau}}<0.07c_{x}c_{\xi}\varepsilon_{\tau}/6$,
which translates to

$\widehat{n}_{\tau}\leq
1+\frac{7500\ln(8n_{\tau}/\delta_{s})}{c_{x}^{2}c_{\xi}^{2}\varepsilon_{\tau}^{2}},$

where $n_{\tau}=\sum_{\tau^{\prime}\leq\tau}\widehat{n}_{\tau^{\prime}}$. Let
$\tau_{0}$ be the largest integer such that
$\varepsilon_{\tau_{0}}\geq\varepsilon_{a}$. Then the total number of queried
samples is upper bounded by

$2\sum_{\tau\leq\tau_{0}}\widehat{n}_{\tau}=O\left(\sum_{\tau\leq\tau_{0}}\frac{1}{\varepsilon_{\tau}^{2}}\log\left(\frac{1}{\delta_{s}\varepsilon_{\tau}}\right)\right)=O(\varepsilon_{\tau_{0}}^{-2}\log(1/\delta_{s}\varepsilon_{\tau_{0}}))=O(\varepsilon_{a}^{-2}\log(1/\delta_{s}\varepsilon_{a})).$

###  4.2 Proof of results in Sec. 3.2

The objective of this section is to prove the key Lemma 3.3. Throughout this
proof we assume that $d$ is sufficiently large and $\varepsilon_{a}>0$ is
sufficiently small. We also define $\theta(w,w^{\prime})$ as the smallest
angle between $w,w^{\prime}\in\mathbb{R}^{d}$.

Recall the definition that $v^{*}_{b}(\cdot)=\langle\cdot,w^{*}\rangle-\beta$
with $\beta=b+\mu^{*}$ is the non-homogeneous linear classifier with the
smallest classification error. For presentation simplicity, we shall normalize
$v^{*}_{b}(\cdot)$ (since only the _signs_ of $v^{*}_{b}(\cdot)$ matter in a
binary classification problem) as
$v^{*}_{b}(\cdot)=\langle\cdot,\widetilde{w}^{*}\rangle-\widetilde{\beta}$
where $\widetilde{w}^{*}=w^{*}/\|w^{*}\|_{2}$ and
$\widetilde{\beta}=\beta/\|w^{*}\|_{2}$. Our first technical lemma shows that
if another classifier
$\widehat{v}(\cdot)=\langle\cdot,\widehat{w}\rangle-\widehat{\beta}$ has small
excess error, then the angle between $\widehat{w}$ and $\widetilde{w}^{*}$
must be small.

###### Lemma 4.3

Let $\widehat{v}(\cdot)=\langle\cdot,\widehat{w}\rangle-\widehat{\beta}$,
$\|\widehat{w}\|_{2}=1$ be a learnt classifier such that
$\Delta\mathrm{err}(\widehat{v})=\mathrm{err}(\widehat{v})-\mathrm{err}(v^{*}_{b})\leq\epsilon$.
Then for sufficiently small $\epsilon$, it holds that
$\tan\theta(\widehat{w},\widetilde{w}^{*})\leq
23e^{(d-2)\beta_{0}^{2}/2}\sqrt{\epsilon}=O(\sqrt{\epsilon})$.

###### Proof 4.4

Proof of Lemma 4.3. Abbreviate $\theta=\theta(\widehat{w},\widetilde{w}^{*})$.
Without loss of generality, assume $w^{*}=(1,0,\cdots,0)$,
$\widehat{w}=(1-\cos\theta,\sin\theta,0,\cdots,0)$ and $\widetilde{\beta}\geq
0$. For sufficiently small $\epsilon$, we have $\tan\theta\leq 1$, and the
disagreement region between $\widehat{v}$ and $v_{b}^{*}$ is depicted in blue
in the left panel of Figure 4. Note also that, as one adjusts the intercept
$\widehat{\beta}$ in $\widehat{v}$, one disagreement region will enlarge and
the other one will shrink. As a result, the minimal disagreement region is
depicted in yellow in the middle panel of Figure 4, with the radius $\rho$ to
be at least $1/2$ for sufficiently large $d$ since
$|\beta|\leq\beta_{0}=O(1/\sqrt{d})$. To further simplify, we take only the
upper triangle of the disagreement region with $r=1/2\sqrt{d}\leq\rho$ and
study the rectangular region designated as $\Omega$ in the right panel of
Figure 4, whose size is $\frac{r}{2}\times h$ where $h=\frac{r}{2}\tan\theta$.

Figure 4: Graphical illustration of the proof of Lemma 4.3.

The excess error of $\widehat{v}$ can be lower bounded by the deviation of
$\eta(x)=\Pr[y=1|x,b]$ from $1/2$ on $\Omega$. More specifically,

$\displaystyle\Delta\mathrm{err}(\widehat{v})$
$\displaystyle\geq\int_{\Omega}\left(\eta(x)-\frac{1}{2}\right)\mathrm{d}P_{X}(x)\geq
c_{x}\int_{\Omega}\left(\eta(x)-\frac{1}{2}\right)\mathrm{d}P_{U}(x)=c_{x}\int_{\Omega}\phi(x_{1}-\beta)\mathrm{d}P_{U}(x)$
(12) $\displaystyle\geq
c_{x}c_{\xi}\int_{\Omega}(x_{1}-\beta)\mathrm{d}P_{U}(x)\geq
c_{x}c_{\xi}\int_{\Omega}\frac{d}{4\pi}e^{-(d-2)(x_{1}^{2}+x_{2}^{2})/2}(x_{1}-\beta)\mathrm{d}x_{1}\mathrm{d}x_{2}$
(13) $\displaystyle\geq\frac{c_{x}c_{\xi}d}{4\pi}\int_{0}^{h}\gamma
e^{-(d-2)((\beta+h)^{2}+r^{2})/2}\mathrm{d}\gamma\geq\frac{c_{x}c_{\xi}d}{4\pi}e^{-(d-2)(\beta^{2}+r^{2})}\frac{1}{2}h^{2}\geq\frac{e^{-(d-2)\beta^{2}}}{128\pi\sqrt[4]{e}}\tan^{2}\theta.$
(14)

Here, Eq. (12) is due to Assumption (A2) and the definition of $\phi$; Eq.
(13) is due to Assumption (A3) and Lemma A.3. Taking the square root on both
sides of Eq. (14) and noting that $\Delta\mathrm{err}(\widehat{v})=\epsilon$,
we complete the proof of Lemma 4.3. $\square$

The next lemma shows that if $\Delta\mathrm{err}(\widehat{v})$ is small, then
the intercept $\widehat{\beta}$ cannot be too far away from $\beta$ either.

###### Lemma 4.5

Let $\widehat{v}(\cdot)=\langle\cdot,\widehat{w}\rangle-\widehat{\beta}$,
$\|\widehat{w}\|_{2}=1$, $|\widehat{\beta}|\leq\beta_{0}$ be a learnt
classifier such that
$\Delta\mathrm{err}(\widehat{v})=\mathrm{err}(\widehat{v})-\mathrm{err}(v_{b}^{*})=\epsilon$.
Then for sufficiently small $\epsilon$,
$|\widehat{\beta}-\widetilde{\beta}|\leq
3601\sqrt{\pi}C_{x}C_{\xi}c_{x}^{-1}c_{\xi}^{-1}\max\\{e^{(d-1)\beta_{0}^{2}},1\\}\sqrt{\epsilon}$
$=O(\sqrt{\epsilon})$.

###### Proof 4.6

Proof of Lemma 4.5. Let $\theta=\theta(\widehat{w},\widetilde{w}^{*})$, and
assume without loss of generality that $\widetilde{w}^{*}=(1,0,\cdots,0)$ and
$\widetilde{\beta}\geq 0$. Let also
$\Delta_{\beta}=\widehat{\beta}-\widetilde{\beta}$.

Figure 5: Graphical illustration of proof of Lemma 4.5.

First we compare the two models of
$\widehat{v}(\cdot)=\langle\cdot,\widehat{w}\rangle-\widehat{\beta}$ and
$\widehat{v}^{*}(\cdot)=\langle\cdot,\widetilde{w}^{*}\rangle-\widehat{\beta}$.
When $d$ is sufficiently large and $\epsilon$ is sufficiently small, the
disagreement region between $\widehat{v}$ and $\widehat{v}^{*}$ is depicted in
the left panel of Figure 5. Since the two line segments intersect when
$|\widehat{\beta}|\leq\beta_{0}\to 0$ as $d\to\infty$ and
$\theta(\widehat{w},\widetilde{w}^{*})\to 0$ as $\epsilon\to 0$, the maximal
disagreement region between $\widehat{v}$ and $\widehat{v}^{*}$ is reached by
the two green dashed lines in the left panel of Figure 5, an upper bound of
which is depicted in the middle panel of Figure 5 by projecting onto the
1-dimensional space along the direction of $\widetilde{w}^{*}$. Subsequently,
the disagreement between $\widehat{v}$ and $\widehat{v}^{*}$ can be upper
bounded as

$\displaystyle\int_{\mathrm{sgn}(\widehat{v}(x))\neq\mathrm{sgn}(\widehat{v}^{*}(x))}\left|\eta(x)-\frac{1}{2}\right|\mathrm{d}P_{X}(x)\leq\int_{x_{1}\in[\widehat{\beta}\pm\tan\theta]}\left|\eta(x)-\frac{1}{2}\right|\mathrm{d}P_{X}(x)\leq
C_{x}C_{\xi}\int_{x_{1}\in[\widehat{\beta}\pm\tan\theta]}\big{|}x_{1}-\widetilde{\beta}\big{|}\mathrm{d}P_{U}(x)$
$\displaystyle\leq
C_{x}C_{\xi}\int_{-\tan\theta}^{\tan\theta}\sqrt{\frac{d+1}{4\pi}}e^{-(d-1)(\widehat{\beta}+\gamma)^{2}/2}|\gamma-\Delta_{\beta}|\mathrm{d}\gamma$
(15) $\displaystyle\leq
C_{x}C_{\xi}\sqrt{\frac{d+1}{4\pi}}\int_{-\tan\theta}^{\tan\theta}|\gamma-\Delta_{\beta}|\mathrm{d}\gamma=C_{x}C_{\xi}\sqrt{\frac{d+1}{4\pi}}\left(\tan^{2}\theta+2\Delta_{\beta}\tan\theta\right)$
$\displaystyle\leq
150C_{x}C_{\xi}\sqrt{d+1}\left(e^{(d-2)\beta_{0}^{2}}\epsilon+2e^{(d-2)\beta_{0}^{2}/2}\sqrt{\epsilon}\Delta_{\beta}\right)$
(16) $\displaystyle=O(\sqrt{d}\epsilon+\sqrt{d\epsilon}\Delta_{\beta}).$

Here, Eq. (15) is due to Lemma A.1, and the last inequality of Eq. (17) holds
by Lemma 4.3.

Next, consider the disagreement between the two models of
$\widehat{v}^{*}(\cdot)=\langle\cdot,\widetilde{w}^{*}\rangle-\widehat{\beta}$
and $v^{*}(\cdot)=\langle\cdot,\widetilde{w}^{*}\rangle-\widetilde{\beta}$.
First consider the case of $\widehat{\beta}\geq\widetilde{\beta}$, and let
$\Delta_{\beta}=\widehat{\beta}-\widetilde{\beta}$. The disagreement region
between $\widehat{v}^{*}$ and $v^{*}$ in this case is depicted in the right
panel of Figure 5. The disagreement between $\widehat{v}^{*}$ and $v^{*}$ can
then be lower bounded by

$\displaystyle\int_{\mathrm{sgn}(\widehat{v}^{*}(x))\neq\mathrm{sgn}(v^{*}(x))}\left(\eta(x)-\frac{1}{2}\right)\mathrm{d}P_{X}(x)\geq\int_{x_{1}\in[\widetilde{\beta},\widehat{\beta}]}\left(\eta(x)-\frac{1}{2}\right)\mathrm{d}P_{X}(x)\geq
c_{x}c_{\xi}\int_{x_{1}\in[\widetilde{\beta},\widehat{\beta}]}(x_{1}-\widetilde{\beta})\mathrm{d}P_{U}(x)$
$\displaystyle\geq
c_{x}c_{\xi}\int_{0}^{\Delta_{\beta}}\sqrt{\frac{d+1}{16\pi}}e^{-(d-1)(\widetilde{\beta}+\gamma)^{2}/2}\gamma\mathrm{d}\gamma\geq
c_{x}c_{\xi}\sqrt{\frac{d+1}{16\pi}}e^{-(d-1)\beta_{0}^{2}/2}\int_{0}^{\Delta_{\beta}}\gamma\mathrm{d}\gamma$
(17)
$\displaystyle\geq\frac{c_{x}c_{\xi}\sqrt{d+1}}{8\sqrt{\pi}}e^{-(d-1)\beta_{0}^{2}/2}\Delta_{\beta}^{2}.$
(18)

Here the second inequality in Eq. (17) holds because
$\widehat{\beta}=\beta+\Delta_{\beta}\leq\beta_{0}$ by optimization
constraint. If $\widehat{\beta}<\widetilde{\beta}$, the disagreement region
has more density because the region (the $[\widehat{\beta},\widetilde{\beta}]$
strip) is closer to the origin than the perimeter of the $\mathbb{B}_{2}(d)$
ball.

Combining Eqs. (17,18) and noting that $v^{*}$ is the Bayes classifier (i.e.,
the classifier that minimizes classification error), we have that

$\displaystyle\Delta\mathrm{err}(\widehat{v})$
$\displaystyle\geq\frac{c_{x}c_{\xi}\sqrt{d+1}}{8\sqrt{\pi}}e^{-(d-1)\beta_{0}^{2}/2}\Delta_{\beta}^{2}-150C_{x}C_{\xi}\sqrt{d+1}\left(e^{(d-2)\beta_{0}^{2}}\epsilon+2e^{(d-2)\beta_{0}^{2}/2}\sqrt{\epsilon}\Delta_{\beta}\right).$
(19)

Since $\Delta\mathrm{err}(\widehat{v})=\epsilon$ and $|\Delta_{\beta}|\leq
2\beta_{0}=O(1/\sqrt{d})$, for sufficiently large $d$ the above inequality
solves to

$|\Delta_{\beta}|\leq
3601\sqrt{\pi}\frac{C_{x}C_{\xi}}{c_{x}c_{\xi}}\max\big{\\{}e^{(d-1)\beta_{0}^{2}},1\big{\\}}\times\sqrt{\epsilon}=O(\sqrt{\epsilon}),$

which is to be proved. $\square$

We are now ready to prove the key Lemma 3.3 in Sec. 3.2.

###### Proof 4.7

Proof of Lemma 3.3. Recall the definition that
$\epsilon_{k}=2^{-k}\epsilon_{0}$. We use mathematical induction to prove
that, at the end of each outer iteration $k\in\\{0,1,2,\cdots,k_{0}\\}$, with
probability $1-\delta_{a}/(k_{0}+1)$ it holds that
$\Delta\mathrm{err}(\widehat{w}_{k},\widehat{\beta}_{k})\leq\epsilon_{k}$.

##### Base of induction.

For $k=0$, invoke Lemma A.5 with $n=n_{0}$ and $\delta=\delta_{a}/(k_{0}+1)$,
we have with probability $1-\delta$ that
$\Delta\mathrm{err}(\widehat{w}_{0},\widehat{\mu}_{0})\leq
O(\sqrt{\frac{d+\ln(k_{0}/\delta_{a})}{n_{0}}})$. Note also that
$k_{0}\asymp\log(1/\varepsilon_{a})$. Hence, with
$n_{0}=\Omega(\varepsilon_{a}^{-1}(d+\log\log(1/\varepsilon_{a})+\log(1/\delta_{a}))$,
we have with probability $1-\delta_{a}/(k_{0}+1)$ that
$\Delta\mathrm{err}(\widehat{w}_{0},\widehat{\mu}_{0})\leq\epsilon_{0}$.

##### Inductive steps.

We assume the inductive hypothesis is true for $k-1$, i.e.,
$\Delta\mathrm{err}(\widehat{w}_{k-1},\widehat{\mu}_{k-1})\leq\epsilon_{k-1}=2^{-(k-1)}\epsilon_{0}$.
We will prove in this step that
$\Delta\mathrm{err}(\widehat{w}_{k},\widehat{\mu}_{k})\leq\epsilon_{k}=2^{-k}\epsilon_{0}$
with probability $1-\delta_{a}/(k_{0}+1)$.

Denote $S_{1}=\\{x\in\mathbb{B}_{2}(d):|\langle
x,\widehat{w}_{k-1}\rangle-\widehat{\beta}_{k-1}|\leq m_{k}\\}$ and
$S_{2}=\mathbb{B}_{2}(d)\backslash S_{1}$. Because
$\Delta\mathrm{err}(\widehat{w}_{k-1},\widehat{\beta}_{k-1})\leq\epsilon_{k-1}$,
by Lemmas 4.3 and 4.5 we have that $\tan\theta(\widehat{w}_{k-1},w^{*})\leq
C\sqrt{\varepsilon_{k-1}}$ and $|\widehat{\beta}_{k-1}-\beta|\leq
C\sqrt{\varepsilon_{k-1}}$ for some constant $C$ depending only on
$C_{x},c_{x},C_{\xi},c_{\xi}$. Hence, with $m_{k}$ selected as
$m_{k}=\Omega(\sqrt{\epsilon_{k-1}})$, we have that
$\mathrm{sgn}(x^{\top}\widehat{w}_{k-1}-\widehat{\beta}_{k-1})=\mathrm{sgn}(x^{\top}w^{*}-\beta)$
for all $x\in S_{2}$. Subsequently,

$\Delta\mathrm{err}(\widehat{w}_{k},\widehat{\beta}_{k})=[\mathrm{err}(\widehat{w}_{k},\widehat{\beta}_{k}|S_{1})-\mathrm{err}(w^{*},\beta|S_{1})]\Pr[x\in
S_{1}]=:\Delta\mathrm{err}(\widehat{w}_{k},\widehat{\beta}_{k}|S_{1})\Pr[x\in
S_{1}],$ (20)

where
$\mathrm{err}(w,\beta|S_{1})=\Pr_{(x,y)}[y\neq\mathrm{sgn}(w^{\top}x-\beta)|x\in
S_{1}]$.

Invoking Lemma A.5, if
$n_{k}\geq\Omega(C_{x}^{2}m_{k}^{2}d^{2}\epsilon_{k}^{-2}\ln(k_{0}/\delta_{a}))=\Omega(d^{2}\epsilon_{k}^{-1}\ln(k_{0}/\delta_{a}))$
then it holds with probability $1-\delta_{a}/(k_{0}+1)$ that

$\Delta\mathrm{err}(\widehat{w}_{k},\widehat{\beta}_{k}|S_{1})\leq\frac{\epsilon_{k}}{1.3C_{x}m_{k}\sqrt{d}}.$
(21)

On the other hand, we have that

$\displaystyle\Pr_{x\sim P_{X}}[x\in S_{1}]$ $\displaystyle\leq
C_{x}\Pr_{x\sim P_{U}}[x\in S_{1}]\leq C_{x}\Pr_{x\sim P_{U}}[|x_{1}|\leq
m_{k}]\leq
C_{x}\sqrt{\frac{2(d+1)}{\pi}}\int_{0}^{m_{k}}e^{-(d-1)u^{2}/2}\mathrm{d}u$
(22) $\displaystyle\leq 1.3C_{x}m_{k}\sqrt{d}.$ (23)

Here, the last inequality in Eq. (22) holds by invoking Lemma A.1. Plug Eqs.
(21,23) into Eq. (20). We proved that
$\Delta\mathrm{err}(\widehat{w}_{k},\widehat{\beta}_{k})\leq\epsilon_{k}$,
which completes the induction step.

In the final part of the proof we upper bound the total number of labeled
(queried) and unlabeled samples used in Algorithm 3. The number of labeled
samples is simply $n_{0}+\sum_{k=1}^{k_{0}}n_{k}$. It can be upper bounded by

$\displaystyle n_{0}+\sum_{k=1}^{k_{0}}n_{k}$ $\displaystyle\leq
O(\kappa_{n}\epsilon_{0}^{-2})+\sum_{k=1}^{k_{0}}O(\kappa_{n}d\epsilon_{k}^{-1})\leq
O(\kappa_{n})\times\left(\frac{1}{\varepsilon_{a}}+\sum_{k=1}^{k_{0}}\frac{2^{k}d}{\sqrt{\varepsilon_{a}}}\right)\leq
O\left(\frac{\kappa_{n}d}{\varepsilon_{a}}\right),$

where the last inequality holds because
$k_{0}=\min\\{k\in\mathbb{M}:2^{-k}\epsilon_{0}\leq\varepsilon_{a}\\}$ and
$\epsilon_{0}=\sqrt{\varepsilon_{a}}$. This shows that the total number of
labeled samples consumed is on the order of $O(\kappa_{n}d/\varepsilon_{a})$.

To upper bound the total number of samples (labeled/queried or unlabeled/not
queried), note that at epoch $k$ the number of total samples is upper bounded
by $n_{k}/\Pr[x\in S_{1}(k)]$, where
$S_{1}(k)=\\{x\in\mathbb{B}_{2}(d):|x^{\top}\widehat{w}_{k-1}-\widehat{\beta}_{k-1}|\leq
m_{k}\\}$. Because $|\widehat{\beta}_{k-1}|\leq\beta_{0}$, we can lower bound
$\Pr[x\in S_{1}(k)]$ as

$\displaystyle\Pr_{x\sim P_{X}}[x\in S_{1}(k)]$ $\displaystyle\geq
c_{x}\Pr_{x\sim P_{U}}[x\in S_{1}(k)]\geq c_{x}\Pr_{x\sim
P_{U}}[|x-\widehat{\beta}_{k-1}|\leq m_{k}]$ $\displaystyle\geq
c_{x}\sqrt{\frac{d+1}{16\pi}}\int_{0}^{m_{k}}e^{-(d-1)(|\widehat{\beta}_{k-1}|+u)^{2}/2}\mathrm{d}u$
$\displaystyle\geq c_{x}\sqrt{\frac{d+1}{16\pi}}e^{-(d-1)\beta_{0}^{2}}\times
m_{k}e^{-(d-1)m_{k}^{2}}$ $\displaystyle\geq\Omega(\sqrt{d})\times
m_{k}e^{-(d-1)m_{k}^{2}}.$

Hence, the total number of samples consumed can be upper bounded by

$\displaystyle n_{0}+\sum_{k=1}^{k_{0}}\frac{n_{k}}{\Pr[x\in S_{1}(k)]}$
$\displaystyle\leq
O(\kappa_{n}\epsilon_{0}^{-2})+\sum_{k=1}^{k_{0}}O\left(\frac{\kappa_{n}\sqrt{d}e^{(d-1)m_{k}^{2}}}{m_{k}\epsilon_{k}}\right)$
$\displaystyle\leq
O(\kappa_{n}\epsilon_{0}^{-2})+\sum_{k=1}^{k_{0}}O\left(\frac{\kappa_{n}\sqrt{d}e^{(d-1)\times
O(\epsilon_{k})}}{\epsilon_{k}^{3/2}}\right)$ $\displaystyle\leq
O\left(\frac{\kappa_{n}\sqrt{d}e^{d\varepsilon_{a}}}{\varepsilon_{a}^{3/2}}\right).$

This completes the proof of Lemma 3.3. $\square$

###  4.3 Proof of Theorem 3.4

Recall the definition that $v(\cdot)=\langle\cdot,w^{*}\rangle-\mu^{*}$.
Define $\alpha:=\|w^{*}\|_{2}\leq B$, $\widetilde{w}^{*}=w^{*}/\alpha$, and
for $j\in\\{1,2\\}$ define
$\widetilde{\beta}_{j}=(\mu^{*}+\widehat{b}_{j})/\alpha$. By Lemma 3.3, we
have
$\Delta\mathrm{err}(\widehat{w}_{j},\widehat{\beta}_{j})\leq\varepsilon_{a}$,
which by Lemmas 4.3 and 4.5 implies
$\tan\theta(\widehat{w}_{j},\widetilde{w}^{*})=O(\sqrt{\varepsilon_{a}})$ and
$|\widehat{\beta}_{j}-\widetilde{\beta}_{j}|=O(\sqrt{\varepsilon_{a}})$. This
implies that
$|\alpha\widehat{\beta}_{j}-\mu^{*}-\widehat{b}_{j}|\leq\alpha\times
O(\sqrt{\varepsilon_{a}})=O(B\sqrt{\varepsilon_{a}})$. On the other hand, the
stopping condition in Algorithm 3 implies
$|\widehat{b}_{2}-\widehat{b}_{1}|=\Omega(\varepsilon_{s})=\Omega(1/\sqrt{d})$,
which yields
$|\widehat{\beta}_{2}-\widehat{\beta}_{1}|=\Omega(1/(\alpha\sqrt{d}))$ for
sufficiently small $\varepsilon$ because
$\widehat{\beta}_{1}\to(\mu^{*}+\widehat{b}_{1})/\alpha$ and
$\widehat{\beta}_{2}\to(\mu^{*}+\widehat{b}_{2})/\alpha$ as $\varepsilon\to
0$. Subsequently,

$\displaystyle\big{|}\widehat{\alpha}-\alpha\big{|}$
$\displaystyle=\left|\alpha-\frac{\alpha\widehat{\beta}_{2}-\mu^{*}\pm
O(B\sqrt{\varepsilon_{a}})-\alpha\widehat{\beta}_{1}+\mu^{*}\pm
O(B\sqrt{\varepsilon_{a}})}{\widehat{\beta}_{2}-\widehat{\beta}_{1}}\right|$
$\displaystyle=\frac{O(B\sqrt{\varepsilon_{a}})}{|\widehat{\beta}_{2}-\widehat{\beta}_{1}|}=O(B^{2}\sqrt{d\varepsilon_{a}}).$
(24)

We now upper bound $|\widehat{\mu}-\mu^{*}|$ and $\|\widehat{w}-w^{*}\|_{2}$.
By definition,
$\widehat{\mu}=\widehat{\alpha}\widehat{\beta}_{1}-\widehat{b}_{1}$ and
$\mu^{*}=\alpha\widetilde{\beta}_{1}-\widehat{b}_{1}$. Subsequently,

$\displaystyle\big{|}\widehat{\mu}-\mu^{*}\big{|}$
$\displaystyle\leq\big{|}\widehat{\alpha}-\alpha\big{|}\cdot|\widehat{\beta}_{1}|+\alpha\big{|}\widehat{\beta}_{1}-\widetilde{\beta}_{1}\big{|}\leq
O(B^{2}\sqrt{d\varepsilon_{a}}\beta_{0})+O(B\sqrt{\varepsilon_{a}})\leq
O(B^{2}\sqrt{d\varepsilon_{a}}).$ (25)

Similarly, $\widehat{w}=\widehat{\alpha}\widehat{w}_{1}$ and
$w^{*}=\alpha\widetilde{w}^{*}$. Therefore,

$\displaystyle\|\widehat{w}-w^{*}\|$
$\displaystyle\leq|\widehat{\alpha}-\alpha|\cdot\|\widehat{w}\|_{2}+\alpha\|\widehat{w}_{1}-\widetilde{w}^{*}\|_{2}\leq
O(B^{2}\sqrt{d\varepsilon_{a}})+O(B\sqrt{\varepsilon_{a}})=O(B^{2}\sqrt{d\varepsilon_{a}}).$
(26)

With the choice of
$\varepsilon_{a}=\kappa_{\varepsilon}\varepsilon^{2}/\ln^{2}(1/\varepsilon)$
and $\kappa_{\varepsilon}\asymp 1/d$, and with $\varepsilon\to 0$ being
sufficiently small, Eqs. (25,26) yield that
$\sup_{x\in\mathbb{B}_{2}(d)}|\widehat{v}(x)-v^{*}(x)|\leq\varepsilon$.
Finally, plugging in the expression of
$\varepsilon_{a}=\kappa_{\varepsilon}\varepsilon^{2}/\ln^{2}(1/\varepsilon)$
and invoking Lemmas 3.2, 3.3 we obtain the upper bounds on
$n(\varepsilon,\delta)$ and $m(\varepsilon,\delta)$.

##  5 Numerical results

We use synthetic data to study the numerical performance of our proposed
active learning methods and compare it with baseline methods. The main
baseline method we are comparing against is a passive learning method:

  * •

The baseline method will first invoke the TrisectionSearch routine in
Algorithm 2 to obtain actions $\widehat{b}_{1},\widehat{b}_{2}$. The method
then divides the remaining number of samples into two halves and use Logistic
regression to form two model estimates $\widehat{w}_{1},\widehat{\beta}_{1}$
and $\widehat{w}_{2},\widehat{\beta}_{2}$ under actions $\widehat{b}_{1}$ and
$\widehat{b}_{2}$ respectively, _without_ sample selection. The method finally
uses Lines 6 and 7 of Algorithm 2 to produce an estimate $\widehat{v}(\cdot)$
of the utility function $v(\cdot)$.

We also mention details of the implementation of our proposed active learning
algorithm. The implementation slightly deviates from the descriptions of the
algorithms and the selection of parameter values in the theoretical results,
due to computational efficiency issues and other factors we observe could
impact the algorithm’s numerical performances. In Line 14 the 0/1-error
empirical risk minimization step is replaced with Logistic regression as the
former formulation is computationally expensive. We also remove the
$\|w\|_{2}=1,|\beta|\leq\beta_{0}$ constraints in the optimization but
normalize the estimator after optimization. The parameters of Algorithm 2 are
set as $\varepsilon_{s}=0.5$ and $\delta_{s}=0.1$. The parameters of Algorithm
3 are set as $\varepsilon_{0}=0.2$, $\kappa_{m}=1.0$ and
$\kappa_{n}=d+\ln(n)$. Note that we no longer need the $\beta_{0}$ parameter
with the Logistic regression formulation.

For the problem settings, we adopt $P_{X}=P_{U}$ being the uniform
distribution on the $d$-dimensional $\ell_{2}$ ball $\mathbb{B}_{2}(d)$. We
set the mean utility model $v(\cdot)$ as
$v(\cdot)=\langle\cdot,\theta^{*}\rangle-\mu^{*}$ with
$\theta^{*}=(2/\sqrt{d},\cdots,2/\sqrt{d})$, and $\mu^{*}=-2.5$. The noise
distribution $P_{\xi}$ is set as the uniform distribution on interval
$[-1,1]$.

###  5.1 Convergence of utility estimates

In the first set of reports we report how fast the utility estimates
$\widehat{v}(\cdot)$ of our proposed algorithm (and the passive learning
baseline) converge to the ground truth $v(\cdot)$ as the number of labeled
(queried) samples $n$ increases. The estimation errors between
$\widehat{v}(\cdot)=\langle\cdot,\widehat{w}\rangle-\widehat{\mu}$ and
$v(\cdot)=\langle\cdot,w^{*}\rangle-\mu^{*}$ are reported as
$\|\widehat{w}-w^{*}\|_{2}+|\widehat{\mu}-\mu^{*}|$.

Figure 6: Log-log plot of the estimation errors of $v(\cdot)$ as a function of
the number of labeled (queried) samples $n$, for $d\in\\{2,3,5\\}$. The dotted
lines are fitted linear regression of the log-log plots.

Figure 6 reports the estimation errors of the active learning algorithm and
the passive learning baseline for dimension settings of $d\in\\{2,5,10\\}$.
Each reported error statistic is averaged over 200 independent trials, since
both the labels and algorithm decisions contain randomness. As we can see, our
proposed active learning algorithm (the blue curves) outperforms significantly
the estimates of the baseline passive learning algorithm (the red curves),
demonstrating the sample efficiency of active learning.

We further fit linear regression models on the log-log plots for both
algorithms. For the active learning algorithm, the slopes of the fitted linear
models are very close to $-0.5$, suggesting an asymptotic convergence rate of
$n(\varepsilon,\delta)\asymp 1/\varepsilon^{2}$. This matches our theoretical
results established in Theorem 3.4. On the other hand, the slopes of fitted
models for the passive learning baseline range from $-0.17$ to $-0.31$, which
are orders of magnitudes slower convergence rates compared to the
$1/\varepsilon^{2}$ rates for active learning methods.

###  5.2 Sensitivity of model dimensions

We use numerical results to evaluate the sensitivity of estimation errors with
respect to the dimensions of the underlying linear model $d$. In Figure 7, we
report the estimation errors of the active learning algorithm and the passive
learning baseline for dimensions $d$ ranging from 3 to 30.

Figure 7: Plot of the estimation errors of $v(\cdot)$ for different labeled
(queried) samples $n$ and $d\in[3,30]$ settings. Here $m$ in the legend stands
for million (e.g., $n=2m$ means the sample size is 2 million).

As we can see in Figure 7, the estimation errors of our proposed active
learning approach scale near linearly with the dimension $d$ of the underlying
linear model. The active learning algorithm also consistently outperforms the
passive learning baseline, especially in large $n$ or $d$ settings.

###  5.3 Sensitivity of unlabeled samples

Figure 8: Plots of estimation errors of $v(\cdot)$ by the active learning
algorithm with different budgets of unlabeled samples (i.e., the number of
labeled samples $n(\varepsilon,\delta)$ varies from 0.5 million, 1 million, to
2 million). The $x$-axis is the $\log$ of the ratio between the number of
unlabeled samples and the number of labeled samples. The $y$-axis is the
estimation error. Dotted lines are errors of the passive learning algorithm.

In this section we report numerical results showing how the estimation errors
of the proposed active learning algorithm decrease as the algorithm has access
to more unlabeled samples. For this purpose, we define the _ratio_ between
unlabeled and labeled samples as

$\rho:=\frac{m(\varepsilon,\delta)-n(\varepsilon,\delta)}{n(\varepsilon,\delta)},$

where $m(\varepsilon,\delta)$ is the total number of samples consumed and
$n(\varepsilon,\delta)$ is the number of samples that are labeled/queried.
Thus, the numerator $m(\varepsilon,\delta)-n(\varepsilon,\delta)$ is the
number of skipped samples. While our theoretical results in Theorem 3.4
indicate that $\rho$ has to scale as large as $O(1/\varepsilon)$ for the
margin-based active learning algorithm. In practice, however, it is possible
to achieve significant estimation accuracy improvements with smaller values of
$\rho$: when the unlabeled sample budget is completely consumed, the margin-
based active learning algorithm will revert back to passive learning without
any additional sample selection being carried out.

In Figure 8 we plot the estimation errors of the utility $v(\cdot)$ as a
function of $\log_{2}(\rho)$, with larger values of $\log_{2}(\rho)$
indicating more unlabeled samples involved. We also report the estimation
errors of the passive learning algorithm as a benchmark, which can be regarded
as an instance of $\rho=0$ (i.e., all the samples are labeled). As we can see,
the estimation errors of our proposed active learning algorithm decrease
rapidly with increasing $\rho$, and the performance increase is significant
when $\rho$ is as small as 0.5 or 1.0. This shows that even with a modest
amount of unlabeled samples, the active learning procedure can already
significantly increase the accuracy of the estimated utility function
$\widehat{v}(\cdot)$.

##  6 Conclusions

In this paper, we study a learning problem in contextual search, where the
goal is to use as fewer queries as possible to accurately estimate the mean
value function. To this end, we propose a margin-based active learning
algorithm with tri-section search scheme and establish the corresponding PAC
learning sample complexity bound. Our bound shows a significant improvement
over the passive setting.

There are several interesting future directions. First, we assume a linear
model in this paper. It would be interesting to extend the linear model to
more general parametric and non-parametric models. Second, in general,
establishing lower bound result in active learning for binary feedback is very
challenging. Despite that, it is worth to explore the optimality of our
algorithm. Third, we hope the proposed active learning algorithm would inspire
more research on adaption of active learning to solve important operations
problems.

## Acknowledgment

The authors would like to thank Zhengyuan Zhou for brainstorming the problem.

##  Appendix A Some technical lemmas

###### Lemma A.1

Suppose $x\sim P_{U}$. Then for any measurable set $A\subseteq[-1,1]$, it
holds that $\Pr[x_{1}\in A]\leq\sqrt{\frac{d+1}{2\pi}}\int_{u\in
A}e^{-(d-1)u^{2}/2}\mathrm{d}u$. If $A\subseteq[-1/\sqrt{2},1/\sqrt{2}]$ then
$\Pr[x_{1}\in A]\geq\sqrt{\frac{d+1}{16\pi}}\int_{u\in
A}e^{-(d-1)u^{2}/2}\mathrm{d}u$.

###### Proof A.2

Proof of Lemma A.1. Let $V_{d}=\pi^{d/2}/\Gamma(1+d/2)$ be the volume of
$\mathbb{B}_{2}(d)$, where
$\Gamma(z)=\int_{0}^{\infty}x^{z-1}e^{-x}\mathrm{d}x$ is the Gamma function.
Using change-of-variable in multivariate integration, it is easy to verify
that $\Pr[x_{1}\in A]=\frac{V_{d-1}}{V_{d}}\int_{u\in
A}(1-u^{2})^{(d-1)/2}\mathrm{d}u=\frac{1}{\sqrt{\pi}}\frac{\Gamma(d/2+1)}{\Gamma(d/2+1/2)}\int_{u\in
A}(1-u^{2})^{(d-1)/2}\mathrm{d}u$. By Kershaw’s inequality (Kershaw 1983), for
any $m>0$ it holds that
$\frac{m}{\sqrt{m+1}}<\frac{\Gamma(m+1/2)}{\Gamma(m)}<\sqrt{m}$. Subsequently,

$\Pr[x_{1}\in A]\leq\frac{\sqrt{d/2+1/2}}{\sqrt{\pi}}\int_{u\in
A}(1-u^{2})^{(d-1)/2}\mathrm{d}u\leq\sqrt{\frac{d+1}{2\pi}}\int_{u\in
A}e^{-(d-1)u^{2}/2}\mathrm{d}u,$

where the last inequality holds because $1-z\leq e^{-z}$ for all $u\geq 0$.
For the other direction, note that $m/\sqrt{m+1}\geq 1/\sqrt{2}$ for $m\geq 1$
and $1-z\geq 0.5e^{-z}$ for all $0\leq z\leq 1/2$. We have

$\Pr[x_{1}\in A]\geq\frac{\sqrt{d/2+1/2}}{\sqrt{2\pi}}\int_{u\in
A}(1-u^{2})^{(d-1)/2}\mathrm{d}u\geq\sqrt{\frac{d+1}{16\pi}}\int_{u\in
A}e^{-(d-1)u^{2}}\mathrm{d}u,$

where the last inequality holds because $u^{2}\leq 1/2$ for all $u\in A$ as
assumed. $\square$

###### Lemma A.3

Suppose $d\geq 2$ and $x\sim P_{U}$. Then for any measurable set
$A\subseteq[-1,1]^{2}\cap\mathbb{B}_{2}(d)$, it holds that
$\Pr[(x_{1},x_{2})\in A]\leq\frac{d}{2\pi}\int_{(u_{1},u_{2})\in
A}e^{-(d-2)(u_{1}^{2}+u_{2}^{2})/2}\mathrm{d}u_{1}\mathrm{d}u_{2}$. If
$x_{1}^{2}+x_{2}^{2}\leq 1/2$ for all $(x_{1},x_{2})\in A$, then
$\Pr[(x_{1},x_{2})\in A]\geq\frac{d}{4\pi}\int_{(u_{1},u_{2})\in
A}e^{-(d-2)(u_{1}^{2}+u_{2}^{2})/2}\mathrm{d}u_{1}\mathrm{d}u_{2}$.

###### Proof A.4

Proof of Lemma A.3 By the change-of-variable formula, $\Pr[(x_{1},x_{2})\in
A]=\frac{V_{d-2}}{V_{d}}\int_{(u_{1},u_{2})\in
A}(1-u_{1}^{2}-u_{2}^{2})^{(d-2)/2}\mathrm{d}u_{1}\mathrm{d}u_{2}=\frac{d}{2\pi}\int_{(u_{1},u_{2})\in
A}(1-u_{1}^{2}-u_{2}^{2})^{(d-2)/2}\mathrm{d}u_{1}\mathrm{d}u_{2}$. The rest
of the proof is identical to the proof of Lemma A.1. $\square$

We next define some useful notations that will make our proof similar. For any
$x\in\mathbb{B}_{2}(d)$ and $b\in\mathbb{R}$, define

$\eta_{b}(x):=\Pr[y=1|x,b],\;\;\;\;\;\;\Delta_{b}(x):=v(x)-b=\langle
x,w^{*}\rangle+\mu^{*}-b.$ (27)

Because $y=1$ if and only if $v(x)+\xi\geq b$ and $\xi\sim P_{\xi}$ with
$\int_{-\infty}^{0}f_{\xi}(u)\mathrm{d}u=\int_{0}^{\infty}f_{\xi}(u)\mathrm{d}u=1/2$
(see Assumption (A3)), we have that
$\eta_{b}(x)-\frac{1}{2}=\int_{-\Delta_{b}(x)}^{0}f_{\xi}(u)\mathrm{d}u=F_{\xi}(0)-F_{\xi}(-\Delta_{b}(x))$
if $\Delta_{b}(x)\geq 0$, and
$\eta_{b}(x)-\frac{1}{2}=-\int_{0}^{-\Delta_{b}(x)}f_{\xi}(u)\mathrm{d}u=F_{\xi}(0)-F_{\xi}(-\Delta_{b}(x))$
if $\Delta_{b}(x)<0$, where $F_{\xi}(\cdot)$ is the CDF of $P_{\xi}$. Since
$\eta_{b}(x)$ only depends on $\Delta_{b}(x)$, we can define

$\phi(\Delta):=F_{\xi}(0)-F_{\xi}(-\Delta).$ (28)

It then holds that $\eta_{b}(x)-\frac{1}{2}=\phi(\Delta_{b}(x))$. Furthermore,
by definition we have that $\phi(\Delta)\leq 0$ for all $\Delta\leq 0$,
$\phi(\Delta)\geq 0$ for all $\Delta\geq 0$, $\phi(0)=0$ and
$\phi^{\prime}(\Delta)=f_{\xi}(-\Delta)\in[c_{\xi},C_{\xi}]$ for all
$|\Delta|\leq 2$, thanks to Assumption (A3).

Now let
$\mathcal{V}=\\{v(\cdot):v(\cdot)=\langle\cdot,w\rangle-\beta,w\in\mathbb{R}^{d},\beta\in\mathbb{R}\\}$
be a hypothesis class of non-homogeneous $d$-dimensional linear classifiers.
The following lemma is a consequence of the classical VC theory of
classification (see, e.g., (Balcan et al. 2007, Theorem 8)).

###### Lemma A.5

Fix a distribution $P$ supported on $\mathbb{B}_{2}(d)$ and a joint
distribution $Q$ supported on $\mathbb{B}_{2}(d)\times\\{0,1\\}$, such that
the marginal of $Q$ on $\mathbb{B}_{2}(d)$ is $P$. Let
$v^{*}=\arg\min_{v\in\mathcal{V}}\mathrm{err}(v|Q)$, where
$\mathrm{err}(v|Q)=\Pr_{(x,y)\sim Q}[y\neq\mathrm{sgn}(v(x))]$. Let
$\\{(x_{i},y_{i})\\}_{i=1}^{n}\overset{i.i.d.}{\sim}Q$ be $n$ i.i.d. samples,
and
$\widehat{v}=\arg\min_{v\in\mathcal{V}}\sum_{i=1}^{n}\boldsymbol{1}\\{y_{i}\neq
v(x_{i})\\}$ be the empirical risk minimizer. Then there exists a universal
constant $C>0$ such that for any $\epsilon,\delta\in(0,1)$, if $n\geq
C\epsilon^{-2}(d+1+\ln(1/\delta))$ then it holds with probability $1-\delta$
that $\mathrm{err}(\widehat{v}|Q)-\mathrm{err}(v^{*}|Q)\leq 2\epsilon$.

###### Proof A.6

Proof of Lemma A.5. Note that the VC dimension of $\mathcal{V}$ is $d+1$. By
(Balcan et al. 2007, Theorem 8), it holds with probability $1-\delta$ that

$\Pr\left[\forall
v\in\mathcal{V},\left|\frac{1}{n}\sum_{i=1}^{n}\boldsymbol{1}\\{y_{i}\neq\mathrm{sgn}(v(x_{i}))\\}-\mathrm{err}(v|Q)\right|\leq\epsilon\right]\geq
1-\delta.$

The lemma is proved by using triangle inequality. $\square$

## References

  * Awasthi et al. (2017) Awasthi, Pranjal, Maria Florina Balcan, Philip M Long. 2017.  The power of localization for efficiently learning linear separators with noise.  Journal of the ACM 63(6) 1–27.
  * Balcan et al. (2009) Balcan, Maria-Florina, Alina Beygelzimer, John Langford. 2009.  Agnostic active learning.  Journal of Computer and System Sciences 75(1) 78–89.
  * Balcan et al. (2007) Balcan, Maria-Florina, Andrei Broder, Tong Zhang. 2007.  Margin based active learning.  International Conference on Computational Learning Theory (COLT).
  * Balcan and Long (2013) Balcan, Maria-Florina, Phil Long. 2013.  Active and passive learning of linear separators under log-concave distributions.  Conference on Learning Theory. PMLR, 288–316.
  * Balcan and Zhang (2017) Balcan, Maria-Florina, Hongyang Zhang. 2017.  Sample and computationally efficient learning algorithms under s-concave distributions.  Advances in Neural Information Processing Systems.
  * Balseiro et al. (2019) Balseiro, Santiago, Negin Golrezaei, Mohammad Mahdian, Vahab Mirrokni, JonSchneider. 2019.  Contextual bandits with cross-learning.  Advances in Neural Information Processing Systems.
  * Bastani and Bayati (2020) Bastani, Hamsa, Mohsen Bayati. 2020.  Online decision making with high-dimensional covariates.  Operations Research 68(1) 276–294.
  * Bastani et al. (2021) Bastani, Hamsa, Mohsen Bayati, Khashayar Khosravi. 2021.  Mostly exploration-free algorithms for contextual bandits.  Management Science 67(3) 1329–1349.
  * Ben-David and Urner (2014) Ben-David, Shai, Ruth Urner. 2014.  The sample complexity of agnostic learning under deterministic labels.  Conference on Learning Theory. PMLR, 527–542.
  * Cohen et al. (2020) Cohen, Maxime C., Ilan Lobel, Renato Paes Leme. 2020.  Feature-based dynamic pricing.  Management Science 66(11) 4921–4943.
  * Cohn et al. (1994) Cohn, David, Les Atlas, Richard Ladner. 1994.  Improving generalization with active learning.  Machine Learning 15(2) 201–221.
  * Cohn (1996) Cohn, David A. 1996.  Neural network exploration using optimal experiment design.  Neural Networks 9(6) 1071–1083.
  * Dasgupta (2005a) Dasgupta, Sanjoy. 2005a.  Analysis of a greedy active learning strategy.  Advances in Neural Information Processing Systems.
  * Dasgupta (2005b) Dasgupta, Sanjoy. 2005b.  Coarse sample complexity bounds for active learning.  Advances in Neural Information Processing Systems.
  * Davies (2019) Davies, Jessica. 2019.  What to know about google’s implementation of first-price ad auctions.  https://digiday.com/media/buyers-welcome-auction-standardization-as-google-finally-goes-all-in-on-first-price/.
  * Han et al. (2020a) Han, Yanjun, Zhengyuan Zhou, Aaron Flores, Erik Ordentlich, Tsachy Weissman. 2020a.  Learning to bid optimally and efficiently in adversarial first-price auctions.  arXiv preprint arXiv:2007.04568 .
  * Han et al. (2020b) Han, Yanjun, Zhengyuan Zhou, Tsachy Weissman. 2020b.  Optimal no-regret learning in repeated first-price auctions.  arXiv preprint arXiv:2003.09795 .
  * Hanneke (2007) Hanneke, Steve. 2007.  A bound on the label complexity of agnostic active learning.  Proceedings of the 24th International Conference on Machine Learning. 353–360.
  * Hanneke et al. (2014) Hanneke, Steve, et al. 2014.  Theory of disagreement-based active learning.  Foundations and Trends® in Machine Learning 7(2-3) 131–309.
  * Javanmard and Nazerzadeh (2019) Javanmard, Adel, Hamid Nazerzadeh. 2019.  Dynamic pricing in high-dimensions.  Journal of Machine Learning Research 20(9) 1–49.
  * Kershaw (1983) Kershaw, D. 1983.  Some extensions of w. gautschi’s inequalities for the gamma function.  Mathematics of Computation 41(164) 607–611.
  * Krishnamurthy et al. (2021) Krishnamurthy, Akshay, Thodoris Lykouris, Chara Podimata, Robert E. Schapire. 2021\.  Contextual search in the presence of irrational agents.  Proceedings of the Symposium on Theory of Computing (STOC).
  * Leme and Schneider (2018) Leme, R. Paes, J. Schneider. 2018.  Contextual search via intrinsic volumes.  Proceedings of the IEEE Symposium on Foundations of Computer Science.
  * Lobel et al. (2017) Lobel, Ilan, Renato Paes Leme, Adrian Vladu. 2017.  Multidimensional binary search for contextual decision-making.  arXiv preprint arXiv:1611.00829 .
  * Mammen and Tsybakov (1999) Mammen, Enno, Alexandre B Tsybakov. 1999.  Smooth discrimination analysis.  The Annals of Statistics 27(6) 1808–1829.
  * Qiang and Bayati (2016) Qiang, Sheng, Mohsen Bayati. 2016.  Dynamic pricing with demand covariates.  Available at SSRN 2765257 .
  * Ren et al. (2019) Ren, Kan, Jiarui Qin, Lei Zheng, Weinan Zhang, Yong Yu. 2019.  Deep landscape forecasting for real-time bidding advertising.  ACM SIGKDD Conference on Knowledge Discovery and Data Mining.
  * Settles (2012) Settles, B. 2012.  Active Learning.  Morgan & Claypool.
  * Sluis (2017) Sluis, Sarah. 2017.  Everything you need to know about bid shading.  https://www.adexchanger.com/online-advertising/everything-you-need-to-know-about-bid-shading/.
  * Vapnik (2013) Vapnik, Vladimir. 2013.  The nature of statistical learning theory.  Springer science & business media.
  * Vapnik and Chervonenkis (2015) Vapnik, Vladimir N, A Ya Chervonenkis. 2015.  On the uniform convergence of relative frequencies of events to their probabilities.  Measures of complexity. Springer, 11–30.
  * Wang and Singh (2016) Wang, Yining, Aarti Singh. 2016.  Noise-adaptive margin-based active learning and lower bounds under tsybakov noise condition.  Thirtieth AAAI Conference on Artificial Intelligence.
  * Wang et al. (2016) Wang, Yuchen, Kan Ren, Weinan Zhang, Jun Wang, Yong Yu. 2016.  Functional bid landscape forecasting for display advertising.  Proceedings of European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases.
  * Zhang and Chaudhuri (2014) Zhang, Chicheng, Kamalika Chaudhuri. 2014.  Beyond disagreement-based agnostic active learning.  Advances in Neural Information Processing Systems, vol. 27. 442–450.
  * Zhang et al. (2014) Zhang, Weinan, Shuai Yuan, Jun Wang. 2014.  Optimal real-time bidding for display advertising.  ACM SIGKDD Conference on Knowledge Discovery and Data Mining.