Active Learning with Neural Networks: Insights from Nonparametric Statistics
Authors: Yinglun Zhu
Robert D Nowak
Venue: NeurIPS 2022 Accept (2022)

Abstract: Deep neural networks have great representation power, but typically require large numbers of training examples. This motivates deep active learning methods that can significantly reduce the amount of labeled training data. Empirical successes of deep active learning have been recently reported in the literature, however, rigorous label complexity guarantees of deep active learning have remained elusive. This constitutes a significant gap between theory and practice. This paper tackles this gap by providing the first near-optimal label complexity guarantees for deep active learning. The key insight is to study deep active learning from the nonparametric classification perspective. Under standard low noise conditions, we show that active learning with neural networks can provably achieve the minimax label complexity, up to disagreement coefficient and other logarithmic terms. When equipped with an abstention option, we further develop an efficient deep active learning algorithm that achieves $\mathsf{polylog}(\frac{1}{\varepsilon})$ label complexity, without any low noise assumptions.  We also provide extensions of our results beyond the commonly studied Sobolev/H\"older spaces and develop label complexity guarantees for learning in Radon $\mathsf{BV}^2$ spaces, which have recently been proposed as natural function spaces associated with neural networks.

Active Learning with Neural Networks: Insights from Nonparametric Statistics
Yinglun Zhu Department of Computer Sciences University of Wisconsin-Madie Madiiso Madison, WI 53706 yinglunecs. wisc. edu
Robert Nowak
Department of Electrical and Computer Engineering
University of Wisconsin Wisconsin-Madison
Madison, WI 53706
rdnowak@wi sc. edu
Abstract
Deep neural networks have great representation power, but typically require large numbers of training examples. This motivates deep active learning methods that can significantly reduce the amount of labeled training data. Empirical successes deep active learning have been recently reported in the literature, however, rigorous label complexity guarantees of deep active learning have remained elusive. This constitutes significant gap between theory and practice. This paper tackles this gap by providing the first near-optimal label complexity guarantees for deep active learning. The key insight is study deep active learning from the nonparametric classification perspective. Under standard low noise conditions, we show that active learning with neural networks can provably achieve the minimax label complexity, to disagreement coefficient and other logarithmic terms. When equipped with an abstention option, we further develop efficient deep active learning algorithm that achieves polylog( {t) label complexity, without any low noise assumptions. We also provide extensions of our results beyond the commonly studied Sobolev/Hölder spaces and develop label complexity guarantees for learning Radon BV² spaces, which have recently been proposed as natural function spaces associated with neural networks.
Introduction
We study active learning with neural network hypothesis classes, sometimes known deep active learning. Active learning agent proceeds by selecting the most informative data points to label: The goal of active learning is to achieve the same accuracy achievable by passive learning, but with much fewer label queries (Settles, 2009; Hanneke, 2014). When the hypothesis class is a set of neural networks, the learner further benefits from the representation power of deep neural networks, which has driven the successes of passive learning in the past decade (Krizhevsky et al., 2012; LeCun al., 2015). With these added benefits, deep active learning has become popular research area, with empirical successes observed in many recent papers (Sener and Savarese, 201 8; Ash et al., 2019; Citovsky et al., 2021; Ash et al., 2021; Kothawade al., 2021; Emam et al., 2021; Ren et al., 2021). However, due to the difficulty of analyzing a set of neural networks, rigorous label complexity guarantees for deep active learning have remained largely elusive.
To the best of our knowledge, there are only two papers (Karzand and Nowak, 2020; Wang et al., 2021) that have made the attempts at theoretically quantifying active learning gains with neural networks. While insightful views are provided, these two works have their own limitations. The guarantees provided in Karzand and Nowak (2020) only work in the 1d case where data points uniformly sampled from [o, 1] and labeled by well-seperated piece-wise constant function in a noise-free way (i.e., without any labeling noise). Wang al. (2021) study deep active learning by
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

linearizing the neural network at its random initialization and then analyzing it as a linear function; moreover, as the authors agree, their error bounds and label complexity guarantees can in fact be vacuous in certain cases. Thus, it's fair to say that up to now researchers have not identified cases where deep active learning are provably near minimax optimal (or even with provably non-vacuous guarantees), which constitutes a significant gap between theory and practice.
In this paper, we bridge this gap by providing the first near-optimal label complexity guarantees for deep active learning. We obtain insights from the nonparametric setting where the conditional probability (of taking a positive label) is assumed to be smooth function (Tsybakov, 2004; Audibert and Tsybakov, 2007). Previous nonparametric active learning algorithms proceed by partitioning the action space into exponentially many sub-regions (e.g., partitioning the unit cube [0, 1] into E sub-cubes each with volume e and then conducting local mean (or some higher-order statisties) estimation within each sub-region (Castro and Nowak, 2008; Minsker, 2012; Locatelli et al., 2017, 2018; Shekhar et al., 2021; Kpotufe al., 2021). We show that, with an appropriately chosen set of neural networks that globally approximates the smooth regression function, one can in fact recover the minimax label complexity for active learning, up to disagreement coefficient (Hanneke, 2007, 2014) and other logarithmic factors. Our results are established by (i) identifying the "right tools" to study neural networks (ranging from approximation results (Yarotsky, 2017, 2018) complexity measure of neural networks (Bartlett et al., 2019)), and (ii) developing novel extensions of agnostic active learning algorithms (Balcan al., 2006; Hanneke, 2007, 2014) 4) to work with a set of neural networks.
While matching the minimax label complexity in nonparametric active learning is existing, such minimax results scale as (poly( (Castro and Nowak, 2008; Locatelli et al., 2017) and do not resemble what is practically observed in deep active learning: A fairly accurate neural network classifier can be obtained by training with only a few labeled data points. Inspired by recent results in parametric active learning with abstention (Puchkin and Zhivotovskiy, 2021; Zhu and Nowak, 2022), we develop an oracle-efficient algorithm showing that deep active learning provably achieves ( 5 ! label complexity when equipped with an abstention option (Chow, 1970). Our algorithm not only achieves an exponential saving in label complexity (without any low noise assumptions), but also highly practical: In real-world scenarios such as medical imaging, it makes more sense for the classifier to abstain from making prediction on hard examples (e.g., those that are close to the boundary), and ask medical experts to make the judgments.
1.1 Problem setting
Let X' denote the instance space and y denote the label space. We focus on the binary classification problem where y == (+1,-1), The joint distribution over X' x y is denoted as Dxy- We use Dx to denote the marginal distribution over the instance space X, and use Dyl= to denote the conditional distribution of ) with respect to any X. We consider the standard active learning setup where x ~ Dx but its label y ~ Dylz is only observed after issuing a label query. We define n(x)) == Py (y +1) as the conditional probability of taking a positive label. The Bayes optimal classifier h+* can thus be expressed as h=(x)= == (inn(22(zz) - 1). For any classifier h: X + V, its (standard) error is calculated as err(h) := IP (xyy (h(x)) + w): and its (standard)
excess error is defined as excess(h) == err(h) eir(h") Our goal is to learn an accurate classifier with small number of label querying.
The nonparametric setting. We consider the nonparametric setting where the conditional prob- ability is characterized by a smooth function. Fix any a E N4. the Sobolev norm of a function f: X IR is defined as |]. /l.....>
max ess supzex D fx)), where a = (a1,.... aa). Jal = > Oi; and D denotes the standard a-th weak derivative of f. The unit ball in the Sobolev space defined as W (x)) == { l| S 1}. Following the convention of nonparametric active learning (Castro and Nowak, 2008; Minsker, 2012; Locatelli et al., 2017, 2018: Shekhar et al., 2021; Kpotufe et al., 2021), we assume X' = (0, 1jd and 17 E W (X') (except in Scction 4).
Neural Networks. We consider feedforward neural networks with Rectified Linear Unit (ReLU) activation function, which is defined as (z)U(z) == max (x. 0}. Each neural network sann : XX' + R consists of several input units (which corresponds to the covariates of x E 2)), one output unit (which corresponds to the prediction in R), and multiple hidden computational units. Each hidden
2

---

computational unit takes inputs { ) (which are outputs from previous layers) and perform the computation ReLU<E;= W b) with adjustable parameters (us);=1 and b; the output unit performs the same operation, but without the ReLU nonlinearity. We use W to denote the total number of parameters of a neural network, and L to denote the depth of the neural network.
1.2 Contributions and paper organization
Neural networks are known to be universal approximators (Cybenko, 1989; Hornik, 1991). In this paper, we argue that, both passive and active regimes, the universal approximatability makes neural networks "universal classifiers" for classification problems: With an appropriately chosen set of neural networks, one can recover known minimax rates (up to disagreement coefficients in the active setting) in the rich nonparametric regimes.' We provide informal statements of our main results in the sequel, with detailed statements and associated definitions/algoriine
deferred to later sections.
In Section 2, we analyze the label complexity of deep active learning under the standard Tsybakov noise condition with smoothness parameter chosen set of neural network classifiers and denote 0xam (E) as the disagreement coefficient (Hanneke, 2007, 2014) level e. We develop the following label complexity guarantees for deep active learning.
(Tsybakov, 2004). Let Hann be an appropriately
Theorem 1 (Informal). There exists algorithm that returns neural network classifier h E Hann with excess error (E)) after querying (9 (e (eT4#).
d-2n
llabll..
The label complexity presented in Theorem matches the active learning lower bound 12(E" (Locatelli et al., 2017) up to the dependence on the disagreement coefficient (and other logarithmic factors). Since Oza.. (5) S E -1 by definition, the label complexity presented in Theorem is never #+2etod
a-to d+22
a+a3 ) (Audibert and Tsybakov, 2007). We also discover worse than the passive learning rates Ō(E- conditions under which the disagreement coefficient with respect to a set of neural network classifiers can be properly bounded, i.e., OHa.. (s) o(s-1) (implying strict improvement over passive learning)
and mm (E) = o(1) (implying matching active learning lower bound).
In Section 3, we develop label complexity guarantees for deep active learning when an additional abstention option is allowed (Chow, 1970; Puchkin and Zhivotovskiy. 2021; Zhu and Nowak, 2022). Suppose cost (e-g. 0.49) that is marginally smaller than random guessing (which has expected cost 0.5) is incurred whenever the classifier abstains from making a predication, we develop the following label complexity guarantees for deep active learning.
Theorem (Informal). There exists an efficient algorithm that constructs neural network classifier Tidmn with Chow's 'ss excess error (e) after querying polylog(2) labels.
The above polylog( { label complexity bound is achieved without any low noise assumptions. Such exponential label savings theoretically justify the great empirical performances of deep active learning observed in practice (e.g.. in Sener and Savarese (2018) 8)): It suffices to label a few data points achieve high accuracy level. Moreover, apart from initialization step, our algorithm (Algorithm 4) developed for Theorem 2 can be efficiently implemented in Ö(E-") time, given a convex loss regression oracle over an appropriately chosen set of neural networks; in practice, the regression oracle can be approximated by running stochastic gradient descent.
Technical contributions. Besides identifying the "right tools" (ranging from approximation results (Yarotsky, 2017, 2018) to complexity analyses (Bartlett et al., 2019)) to analyze deep active learning, theoretical guarantees are empowered by novel extensions of active learning algorithms under neural network approximations. In particular, we deal with approximation error in active learning under Tsybakov noise, and identify conditions that greatly relax the approximation requirement in the learning with abstention setup; we also analyze the disagreement coefficient, both classifier-basce and value function-based, with set of neural networks. These analyses together lead our main results for deep active learning (e.g., Theorem I and Theorem 2). More generally, we establish a
"A a byproduct, our results also provide a new perspective on nonparametric active learning through the lens of neural network approximations. Nonparametric active learning was previously tackled through space partitioning and local estimations over exponentially many sub-regions (Castro and Nowak, 2008; Minsker, 2012; Locatelli et al., 2017, 2018; Shekhar et al., 2021: Kpotufe al., 2021).
3

---

bridge between approximation theory and active learning: we provide these general guarantees in Appendix B (under Tsybakov noise) and Appendix D (with the abstention option), which can be of independent interests. Benefited from these generic algorithms and guarantees, in Section 4, we extend our results into learning smooth functions in the Radon BV² space (Ongie et al., 2020; Parhi and Nowak, 2021, 2022a,b; Unser, 2022), which recently proposed as a natural space analyze neural networks.
1.3 Related work
Active learning concerns about learning accurate classifiers without extensive human labeling. One of the earliest work of active learning dates back to the CAL algorithm proposed by Cohn al. (1994), which set the cornerstone for dixagreement-buce -based active learning. Since then, a long line of work have been developed, either directly working with a set classifier (Balcan al., 2006; Hanneke, 2007; Huang et al., 2015; Cortes et al.. 2019) or work with set of regression functions (Krishnamurthy al., 2017. 2019). These work mainly focus on the parametric regime (e.g., learning with set of linear classifiers), and their label complexities rely on the boundedness of the so-called disagreement coefficient (Hanneke, 2007, 2014; Friedman, 2009). Active learning in the nonparametric regime has been analyzed in Castro and Nowak (2008); Minsker (2012); Locatelli et al. (2017, 2018); Kpotufe et al. (2021). These algorithms rely on partitioning of the input space X' C [0. 1 into exponentially (in dimension) many small cubes, and then conduct local mean (or some higher-order statistics) estimation within each small cube.
Dasgupta et al., 2007; Beygelzimer et al., 2009, 2010:
It is well known that, in the worst case, active learning exhibits no label complexity gains over the passive counterpart (Kääriäinen, 2006). To bypass these worst-case scenarios, active learning has been popularly amalyzed under the so-called Tsybakov low noise conditions (Tsybakov, 2004). Under Tsy- bakov noise conditions, active learning has been shown to be strictly superior than passive learning in terms of label complexity (Castro and Nowak, 2008; Locatelli et al., 2017). Besides analyzing active learning under favorable low noise assumptions, more recently, researchers consider active learning with an abstention option and analyze its label complexity under Chow's 's error (Chow, 1970). In par- ticular, Puchkin and Zhivotovskiy (2021); ; Zhu and Nowak (2022) develop active learning algorithms with polylog( !) label complexity when analyzed under Chow's excess error. Shekhar et al. (2021) study nonparametric active learning under a different notion of the Chow's 's excess error, and propose al- gorithms with poly(? ( label complexity; their algorithms follow similar procedures of those partition- based nonparametric active learning algorithms (e.g., Minsker (2012); Locatelli et al. (2017)).
Inspired by the success of deep learning in the passive regime, active learning with neural networks has been extensively explored in recent years (Sener and Savarese, 2018; Ash et al., 2019; Citovsky et al., 2021; Ash et al., 2021; Kothawade et al., 2021; Emam et al., 2021; Ren et al., 2021). Great empirical performances are observed these papers, however, rigorous label complexity guarantees have largely remains elusive (except in Karzand and Nowak (2020); Wang et al. (2021), with limitations discussed before). We bridge the gap between practice and theory by providing the first near-optimal label complexity guarantees for deep active learning. Our results are built upon approximation results deep neural networks (Yarotsky, 2017, 2018; Parhi and Nowak, 2022b) and VC/pseudo dimension analyses of neural networks with given structures (Bartlett et al., 2019).
2 Label complexity of deep active learning
We analyze the label complexity of deep active learning in this section. We first introduce the Tsybakov noise condition in Section 2. and then identify the "right tools" to analyze classification problems with neural network classifiers in Section 2.2 (where we also provide passive learning guarantees). We establish our main active learning guarantees in Section 2.3.
2.1 Tsybakov noise condition
It is well known that active learning exhibits no label complexity gains over the passive counterpart without additional low noise assumptions (Kääriäinen, 2006). We next introduce the Tsybokov low noise condition (Tsybakov, 2004), which has been extensively analyzed in active learning literature.

---

Definition 1 (Tsybakov noise). A distribution Xxy satisfies the Tsybakov noise condition with parameter 2 and a universal constant 2 1 VT > 0,
PA-Dx (17(2) 1/21 ST)
The case with 3 = O corresponds to the general case without any low noise conditions, where no active learning algorithm can outperform the passive counterpart (Audibert and Tsybakov, 2007; Locatelli et al., 2017). We use P(a, 3) to denote the set of distributions satisfying: (i) the smoothness conditions introduced in Section 1.1 with parameter > 0; and (ii) the Tsybakov low noise condition (i.e., Definition 1) with parameter 3 2 O. We assume Dxy P(a, (3) in the rest of Section 2. As in Castro and Nowak (2008); Hanneke (2014), we assume the knowledge of noise/smoothness parameters.
2.2 Approximation and expressiveness of neural networks
Neural networks known to be universal approximators (Cybenko, 1989; Hornik, 1991): For any continuous function X - IR and any error tolerance x > 0, there exists a large enough neural network fdnn such that [l - g g|loc
supzex [ann (z)) 9(x) K. Recently, non-asympototic approximation rates by ReLUU neural networks have been developed for smooth functions in the Sobolev space, which we restate in the following."
Theorem (Yarotsky (2017)). Fix any k. > 0. For any = E WT ([0,1]%) there exists a neural network Sdnn with W = 0(x & log )) total number of parameters arranged in L Olog ) layers such that [[ 1l S K.
=
The architecture of the neural network fann appearing in the above theorem only depends on the smooth function space W ((0, 1] but otherwise is independent of the regression function f*; also see Yarotsky (2017) for details. Let Fann denote the set of neural network regression functions with the same architecture. We construct set of neural network classifiers by thresholding the regression function at 3. i.e., Hann == {hg == (2g -1): f Jdnn The next result concerns about the expressiveness of the neural network classifiers, in terms of well-known complexity measure: the VC dimension (Vapnik and Chervonenkis, 1971).
Theorem 4 (Bartlett et al. (2019)). Let Hann be a set of neural network classifiers of the same architecture and with W parameters arranged in L layers. We then have
S2(WL L log(W/L)) L)) S VCdim((Hann) S O(W log(W)).
With these tools, we can construct a set of neural network classifiers Hdnn such that (i) the best in-class classifier h E Hann has small excess error, and (ii) Hann has well-controlled VC dimension that is proportional to smooth/noise parameters. More specifically, we have the following proposition.
Proposition 1. Suppose Dxy E P(a, 3). One can construct a set of neural network classifier Hánn such that the following two properties hold simultaneously:
inf err(h) err(h*) 0(e) and VCdim Ö(s (ai))))
heHam
With the approximation results obtained above, to learn a classifier with O excess error, one only needs to focus on a set of neural networks Hann with well-controlled VC dimension. As warm-up, we first analyze the label complexity of such procedure the passive regime (with fast rates).
Theorem 5. Suppose Dxy E P(a, 3). Fix any E, > 0. Let Hdan be the set of neural network 1-2uin0
classifiers constructed in Proposition 1. With = Ō(s
i.i.d. sampled points, with a(1+3;
probability least - 8, the empirical risk minimizer h Hann achieves excess error O(E).
The label complexity results obtained in Theorem 5 matches, up to logarithmic factors, the passive d:
learning lower bound Q( our proposed learning procedure with a set of neural networks is near minimax optimal."
+(1+7)
established in Audibert and Tsybakov (2007), indicating that
"As in Yarotsky (2017), we hide constants that are potentially a-dependent and d-dependent into the Big-Oh notation.
"Smilar passive learning guarantees have been developed with different tools and analyses, e.g., see results in Kim et al. (2021).
5

---

2.3 Deep active learning and guarantees
The passive learning procedure presented in the previous section treats every data point equally, i.e., requests the label of every data point. Active learning reduces the label complexity by only querying labels of data points that are "more important". We present deep active learning results in this section. Our algorithm (Algorithm 1) is inspired by RobustCAL (Balcan et al., 2006; Hanneke, 2007, 2014) and the seminal CAL algorithm (Cohn al., 1994); we call our algorithm NeuraiCAL to emphasize that it works with set of neural networks.
For any accuracy level 0, NeuraICAL first initialize set of neural network classifiers Hg Hdnn such that (i) the best in-class classifier h := arg min err(h) has excess error at most O and (ii) the VC dimension of Hann is upper bounded by Ö( wct) (see Section 2.2 for more details). NeuralCAL then rums in epochs of geometrically increasing lengths. At the beginning of epoch m, based on previously labeled data points, NeuralCAL updates set of active classifier H.m. such that, with high probability, the best classifier h remains uneliminated. Within each epoch m, NeuralCAL only queries the label y of a data point æ if it lies in the region of disagreement with respect to the current active set of classifier Hm, i.e., DIS(Hm) == {a E X' Eh1, h2 Hm s.t. hı (x) & hz(z)). NeuraICAL returns any classifier 7 E Hm that remains uneliminated after M epoch.
Algorithm 1 NeuraICAL
Input: Accuracy level e E (0, 1), confidence level E (0,
1: Let Hdnn be a set of neural networks classifiers constructed in Proposition 1.
2: Define T == 148 VCdim Hddm)) M == [log2 T1 Tm == 2" for m 2 and TO == 0.
3: Define Pm = :00 (((
110 248
VCdim Ham) Mogm) 7m llog (M/6)
for m 2 2 and := 1.
4: Define Rh) = Er (:1(h(x)) + we) with the convention that Σe Et=1 O.
5: Initialize Ho == Hdnn-
6: for epoch m L.2...., do
7: Update active set 7m := {h Hm-1 (h) I infaEH... Rm + Tm-1 Pml
8: if epoch m = M then
9:
Return any classifier E HM. for time f = Tm-1 + 1...., . Tm do
10:
11:
Observe 24 ~ Dx. Set Q+ = 1 (xt E DIS(Hm)).
if Q, = then Query the label of xe.
13:
Since NeuralCAL only queries labels of data points lying in the region of disagreement, its label complexity should intuitively be related how fast the region of disagreement shrinks. More formally, the rate of collapse of the (probability measure of) region of disagreement is captured by the (classifier-basee) disagreement coefficient (Hanneke, 2007, 2014), which we introduce next. Definition 2 (Classifier-baset disagreement coefficient). For any sn and classifier E H. the classifier-bused disagreement coefficient of h is defined as
02, == =sup PANDY (DI5(Bx(h,e)) V1,
8 where (x) == to E H P(x E X g(x) + Mx))) S e}. We also define 0x(so) == suPacи (so)
=350
The guarantees of NeuralCAL follows from a more general analysis of RobustCAL under approxi- mation. In particular, to achieve fast rates (under Tsybakov noise), previous analysis of RobustCAL requires that the Bayes classifier is in the class (or a Bernstein condition for every h E H) (Hanneke, 2014). These requirements are stronger compared to what we have in the case with neural network approximations. Our analysis extends the understanding of RobustCAL under approximation. We defer such general analysis to Appendix B, and present the following guarantees.
Theorem 6. Suppose Dxy P(a, B). Fix any e, O. With probability least 1 8, Algorithm I 8 2420
returns a classifier h Honn with excess error ((s) after querying Ö(0 (e 1te) ) ato? ) labels.

---

We next discuss in detail the label complexity of deep active learning proved in Theorem 6.
Ignoring the dependence on disagreement coefficient, the label complexity appearing in Theorem matches, up to logarithmic factors, the lower bound [2(E
d+2o
ats2) ) for active learning (Locatelli
et al., 2017). At the same time, the label complexity appearing in Theorem 6 is never worse than d420408
the passive counterpart (i.e., O a(1+8)
since H (e 1+3 E
We also identify cases when Hemm (ETÉB) o(E 1+7) ), indicating strict improvement over passive learning (e.g., when Dx is supported on countably many data points), and when He.. (e - (11), indicating matching the minimax active lower bound (e.g., when Dxy satisfies conditions such as decomposibility defined in Definition 4. See Appendix C.2 for detailed discussion).
Our algorithm and theorems lead to the following results, which could benefit both deep active learning and nonparametric learning communities.
Near minimax optimal label complexity for deep active learning. While empirical successes of deep active learning have been observed, rigorous label complexity analysis remains elusive except for two attempts made in Karzand and Nowak (2020); Wang et al. (2021). The guarantees provided in Karzand and Nowak (2020) only work in very special cases (i.c., data uniformly sampled from [0, 1] and labeled by well-separated piece-constant functions in noise-free way). Wang et al. (2021) study deep active learning in the NTK regime by linearizing the neural network at its random initialization and analyzing it as a linear function; moreover, as the authors agree, their error bounds and label complexity guarantees are vacuous in certain cases. On the other hand, our guarantees are minimax optimal, up to disagreement coefficient and other logarithmic factors, which bridge the gap between theory and practice in deep active learning.
New perspective on nonparametrie learning. Nonparametric learning of smooth functions have been mainly approached by partitioning- methods (Tsybakov, 2004; Audibert and Tsybakov, 2007; Castro and Nowak, 2008; Minsker, 2012: Locatelli et al., 2017, 2018; Kpotufe et al., 2021): Partition the unit cube [0, 1jd into exponentially (in dimension) many sub-cubes and conduct local mean estimation within each sub-cube (which additionally requires a strictly stronger membership querying oracle). Our results show that, in both passive and active settings, one can learn globally with a set of neural networks and achieve near minimax optimal label complexities.
3 Deep active learning with abstention: Exponential speedups
While the theoretical guarantees provided in Section are near minimax optimal, the label complexity scales as poly(?), which doesn't 't match the great empirical performance observed in deep active learn- ing. In this section, we fill in this gap by leveraging the idea of abstention and provide deep active learning algorithm that achieves exponential label savings. We introduce the concepts of abstention and Chow's 's excess error in Section 3.1, and provide our label complexity guarantees in Section 3.2.
3.1 Active learning without low noise conditions
The previous section analyzes active learning under Tsybakov noise, which has been extensively studied in the literature since Castro and Nowak (2008). More recently, promising results are observed in active learning under Chow's 's excess error, but otherwise without any low noise assumption (Puchkin and Zhivotovskiy, 2021; Zhu and Nowak, 2022). We introduce this setting in the following.
Abstention and Chow's error (Chow, 1970). We consider classifier of the form h X DU(L} where I denotes the action of abstention. For any fixed < 7 < 2.2 the Chow's 's error is defined as
err, (h) = P(a.))-Dxy (h(x) + y, (x)))) + 1) (1/2 7) 7) (x.,))Dxy (h(x) = L).
"We remark that disagreement coefficient is usually bounded/analyzed under additional assumptions on Dxy. even for simple cases with set of linear classifiers (Friedman, 2009; Hanneke, 2014). The label complexity guarantees of partition-based nonparametric active algorithms (e.g.. Castro and Nowak (2008)) do not depend on the disagreement coefficient, but they are analyzed under stronger assumptions, e.g., they require the strictly stronger membership querying oracle. See Wang (2011) 1) for discussion. We left comprehensive analysis of the disagreement coefficient with set of neural network classifiers for future work.
7

---

The parameter 7 can be chosen as small constant, e.g., = 0.01, to avoid excessive abstention: The price of abstention only marginally smaller than random guess (which incurs cost 0.5). The Chow's excess error is then defined as excess, (ft == err, (h) err(h*) (Puchkin and Zhivotovskiy, 2021).
At a high level, analyzing with Chow's excess error allows slackness in predications of hard examples (e.g., data points whose 77()) is close 2) by leveraging the power of abstention. Puchkin and Zhivotovskiy (2021); Zhu and Nowak (2022) show that polylog( ( is always achievable in the parametric settings. We generalize their results to the nonparametric setting and analyze active learning with a set of neural networks.
3.2 Exponential speedups with abstention
In this section, we work with a set of neural network regression functions Fann : X approximates 1)) and then construct classifiers h X' y {1} with additional abstention action. To work with a set of regression functions Fann. we analyze its "complexity" from the lenses of pseudo dimension Pdim (Pollard, 1984; Haussler, 1989, 1995) and value function disagreement coefficient 8 (4) (for some 0) (Foster et al., 2020). We defer detailed definitions of these complexity measures to Appendix D.1.
- [0. 1] (that
Algorithm 2 NeuralCAL++
Input: Accuracy level E (0, 1), confidence level E (0, 1), abstention parameter E 1/,).2).
I: Let Fann be a set of neural network regression functions obtained by (i) applying Theorem with an appropriate approximation level и (which satisfies 1 = poly polylog( and (ii) applying a preprocessing step on the set of neural networks obtained from step (i). See Appendix E for details.
2: Define T == F (d/4)-Pdim((am)
M := [loge T7. and Cs == O(Pdim(Fam) 3: Define Tm = 2 for m 2 1. == O, and 8. := 3(M m + 1)C3.
54
4: Define (fm -
(z(((z)) y.)² with the convention that Σe .......
1=1
5: for epoch m = 1, 2,.,.... M do
6: Get fm == arg min Emr Qe(f(x)) n1)
7: (Implicitely) Construct active set Fm { Fann Rm) (mm(F + Bm
8: Construct classifier Tim :X' + -1, as
[Icb(x;;m)) ucb((;;;Fm) + 31 Y, +7]]
Am (z) = (igu(2fmm(3)) 1), o.w.
and query function if epoch m MM then
= (1= E ((cb(r;Fm) 3. ucubb(;;F Fm) +)) 1 (()m(()) # L).
9:
10:
Return classifier Teas-
11:
for time / = Tm-1 + 1,..., do Observe 3, Dxx Set Q == Im (12).
13:
if Q2 = 1 then Query the label ye of Ft.
We now present NeuralCAL++ (Algorithm 2), deep active learning algorithm that leverages the power of abstention. NeuralCAL++ first initialize a set of set neural network regression functions Fann by applying preprocessing step on top of the set of regression functions obtained from Theorem with a carefully chosen approximation level k. The preprocessing step mainly contains two actions: (1) clipping fann X R into fam X -> [o, 1] (since we obviously have n7(x) [0, 1)): and (2) filtering out fann E Fann that are clearly not good approximation of After initialization, NeuralCAL++ runs in epochs of geometrically increasing lengths. At the beginning of epoch m [M]. NeuralCAL++ (implicitly) constructs active set of regression functions F... that are "close" to the true conditional probability 17. For any x ~ Dx. NeuralCALt+ constructs a lower bound lcb(æ: Fm) = /EF f(x and an upper bound ucb(æ: Fm)) supye f(x) as confidence range of nT(x) (based on Fm). An empirical classifier with an abstention option
8

---

and query function Im X' - {0,1} } are then constructed based on the confidence range (and the abstention parameter y). For any time step within epoch m. NeuralCAL++ queries the label of the observed data point I; if and only if Q: == 9m (2,) = 1. NeuralCAL++ returns hM as the learned classifier.
hm : ++1,
NeuralCAL++ adapted from the algorithm developed Zhu and Nowak (2022), but with novel extensions. In particular, the algorithm presented in Zhu and Nowak (2022) requires the existence of a f F such that || y/1 S (to achieve Chow's excess emror), Such an approximation requirement directly leads to poly(2) label complexity the nonparametric setting, which is unacceptable. The initialization step of NeuraiCAL++ (line 1) is carefully chosen to ensure that Pdlmm(Fnn)) 0y (?) = p pooyyog( { together with a sharper analysis of concentration results, these conditions help us derive the following deep active learning guarantees (also see Appendix D for more general guarantee).
Theorem 7. Fix any e, 6,6,7 > 0. With probability at least 1 - 6, Algorithm 2 (with an appropriate initialization at line 1) returns classifier h with Chow's excess error (E) after querying poly())- polylog( 2 labels.
We discuss two important aspects of Algorithm 2/Theorem 7 in the following, i.c., exponential savings and computational efficiency. We defer more detailed discussions to Appendix F.I.
Theorem 7 shows that, equipped with an abstention option, deep active learning enjoys polylog(?) label complexity. This provides theoretical justifications for great empirical results of deep active learning observed in practice. Moreover, Algorithm 2 outputs a classifier that abstains properly, i.e., it abstains only if abstention is the optimal choice; such a property further implies polylog(?) label complexity under standard excess error and Massart noise (Massart and Nédélec, 2006).
Exponential speedups.
Computational efficiency. Suppose one can efficiently implement a (weighted) square loss regression oracle over the initialized set of neural networks Fann: Given any set S of weighted examples ()) E R4 x X' x y as input, the regression oracle outputs fann := arg FeFo Emw,r.ies w(f(x) y)² 5 Algorithm 2 can then be efficiently implemented with (2) . oracle calls.
While the label complexity obtained in Theorem has desired dependence on polylog( { its dependence on y can be of order y - poly(d), Our next result shows that, however, such dependence is unavoidable even in the case of learning single ReLU function.
Theorem 8. Fix any 7 E (0, 1/8). For any accuracy level e sufficiently small, there exists problem instance such that (1) E W1 (X) and is of the form 7f(x) == ReLU((W, + a) + b; and (2) for any active learning algorithm, it takes at least -S(d) labels identify an e-optimal classifier, for either standard excess error or Chow's 's excess error (with parameter 7).
Extensions
Previous results are developed in the commonly studied Sobolev/Hölder spaces. Our techniques, however, are generic and can be adapted to other function spaces, given neural network approximation results. In this section, we provide extensions of our results to the Radon BV" space, which was recently proposed the natural function space associated with ReLU neural networks (Ongie et al., 2020; Parhi and Nowak, 2021, b022a,b; Unser, 2022).
The Radon 2 space. The Radon 2V² unit ball over domain X' is defined as A (V) { [I/ = I 1}. where |I (x) denotes the Radon BV² norm of over domain X.7 Following Parhi and Nowak (2022b), we assume X' = {a E Rd ||~|| s 1} and v E A (2).
'In practice, one can approximate this oracle by running stochastic gradient descent. 'Other extensions are also possible given neural network approximation results, e.g., recent results established in Lu et al. (2021).
We provide more mathematical backgrounds and associated definitions in Appendix G.

---

The Radon BV² space naturally contains neural networks of the form [dn) = k= U/- ReLU(w, x + b;). On the contrary, such fan doesn't tt lie in any Sobolev space of order 2 2 (since sann doesn't have second order weak derivative). Thus, if v takes the form the afore- mentioned neural network (e.g.. ?) = fdnn). approximating 1 up to x from Sobolev perspective requires O(x**) total parameters, which suffers from the curse of dimensionality. On the other side, however, such bad dependence dimensionality goes away when approximating from a Radon BV² perspective, as shown in the following theorem.
Theorem (Parhi and Nowak (2022b)). Fix any K. > O. For any f E A (2), there exists one-hidden layer neural network fann of width O( d4s) such that I| fannlloo S
24
Equipped with this approximation result, we provide the active learning guarantees for learning a smooth function within the Radon BV unit ball as follows.
Theorem 10. Suppose E (X) and the Tsybakov noise condition is satisfied with parameter
B O. Fix any e, > O. There exists algorithm such that, with probability at least 1- 6, it learns
a classifier h E Hann with excess error Oee) after querying O10 (ET
4d46 (++3)243)) ) labels.
Compared the label complexity obtained in Theorem 6, the label complexity obtained in the above theorem doesn't t suffer from the curse of dimensionality: For d large enough, the above label complexity scales as E (0(( yet label complexity in Theorem 6 scales as E e(0() Active learning guarantees under Chow's 's excess error in the Radon BV space are similar to results presented in Theorem 7, and are thus deferred to Appendix G.
5 Discussion
We provide the first near-optimal deep active learning guarantees, under both standard excess error and Chow's excess error. Our results powered by generic algorithms and analyses developed for active learning that bridge approximation guarantees into label complexity guarantees. We outline some natural directions for future research below.
Disagreement coelficients for neural networks. While we have provided some results regarding the disagreement coefficients for neural networks, we believe a comprehensive investigation on this topic is needed. For instance, can we discover more general settings where the classifier-based disagreement coefficient can be upper bounded by (1)) It is also interesting explore sharper analyses on the value function disagreement coefficient.
Adaptivity in deep active learning. Our current results are established with the knowledge of some problem-dependent parameters, e.g., the smoothness parameters regarding the function spaces and the noise levels. It will be interesting to see if one can develop algorithms that can automatically adapt to unknown parameters, e.g., by leveraging techniques developed in Locatelli et al. (2017, 2018).
Acknowledgments and Disclosure of Funding
The authors would like to thank Rahul Parhi for many helpful discussions regarding his papers. We also would like to thank anonymous reviewers for their constructive comments. This work is partially supported by NSF grant 1934612 and AFOSR grant FA9550-18-110166.
References
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference on Machine Learning, pages 1638-1646. PMLR, 2014.
Martin Anthony. Uniform glivenko-cantelli theorems and concentration of measure in the mathemati- cal modelling of learning. Research Report 1SE-CDAM-2002-007 2002.
Jordan Ash, Surbhi Goel, Akshay Krishnamurthy, and Sham Kakade. Gone fishing: Neural active learning with fisher embeddings. Advances in Neural Information Processing Systems, 34, 1021.
10

---

Jordan T Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. arXiv preprint arXiv:1906.036777 2019.
Yves Audibert and Alexandre B Tsybakov. Fast learning rates for plug-in classifiers. The Annals of statistics, 35(2):608-60 633, 2007.
Maria-Florins Balcan, Alina Beygelzimer, and John Langford. Agnostic active learning. In Proceed- ings of the 23rd international conference on Machine learning. pages 65-72, 2006.
Peter L Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve-dimension and pscudodimension bounds for piecewise linear neural networks. The Journal of Machine Learning Research, 20(1 (0(1):228) ):2285-2301, 2019.
Alina Beygelzimer, Sanjoy Dasgupta, and John Langford. Importance weighted active learning. In Proceedings of the 26th annual international conference on muchine learning, pages 49-56, 2009,
Alina Beygelzimer, Daniel J Hsu, John Langford, and Tong Zhang. Agnostic active learning without constraints. Advances in neural information processing systems, 23, 2010.
Stéphane Boucheron, Olivier Bousquet, and Gábor Lugosi. Theory of classification: A survey of some recent advances. ESAIM: probability and statistics, 9:323-375, 2005.
Rui M Castro and Robert D Nowak. Minimax bounds for active learning. IEEE Transactions on Information Theory, 54(5):2339-22 2353, 2008.
CK Chow. On optimum recognition enror and reject tradeoff. IEEE Transactions on information theory, 16(1): (11))):1444 14,44,6,1111 1970.
Gui Citovsky, Giulia DeSalvo, Claudio Gentile, Lazaros Karydas, Anand Rajagopalan, Afshin Rostamizadeh, and Sanjiv Kumar. Batch active learning at scale. Advances in Neural Information Processing Systems, 34, 2021.
David Cohn, Les Atlas, and Richard Ladner. Improving generalization with active learning. Machine learning, 15(2):001-221 1994.
Corinna Cortes, Giulia DeSalvo, Mehryar Mohri, Ningshan Zhang, and Claudio Gentile. Active learning with disagreement graphs. In International Conference on Machine Learning, pages 1379-1387. PMLR, 2019.
George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989.
Sanjoy Dasgupta, Daniel Hsu, and Claire Monteleoni. A general agnostic active learning algorithm. Advances in neural information processing systems, 20, 2007.
Zeyad Ali Sami Emam, Hong-Min Chu, Ping-Yeh Chiang, Wojeiech Czaja, Richard Leapman, Micah Goldblum, and Tom Goldstein. Active learning the imagenet scale. arXiv preprint
arXiv:2111.12880 2021.
Dylan Foster, Alekh Agarwal, Miroslav Dudík, Haipeng Luo, and Robert Schapire. Practical contextual bandits with regression oracles. In International Conference on Machine Learning, pages 1539-1548. PMLR, 2018.
Dylan J Foster, Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu. Instance-dependent complexity of contextual bandits and reinforcement learning: A disagreement- based perspective. arXiv preprint arXiv:2010.03104 2020.
David A Freedman. On tail probabilities for martingales. the Annals of Probability, pages 180-118, 1975.
Eric Friedman. Active learning for smooth problems. In COLT. Citeseer, 2009.
Steve Hanneke. A bound on the label complexity of agnostic active learning. In Proceedings of the 24th international conference on Machine learning, pages 353-360, 2007.
Steve Hanneke. Theory of active learning. Foundations and Trends in Machine Learning, 7(2-3), 2014.
David Haussler. Decision theoretic generalizations of the pac model for neural net and other learning applications. 1989.
David Haussler. Sphere packing numbers for subsets of the boolean n-cube with bounded vapnik- chervonenkis dimension. Journal of Combinatorial Theory, Series A. 69(2)2117-33,, 1995.

---

Juha Heinonen. Lectures on Lipschitz analysis. Number 100. University of Jyväskylä, 2005.
Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural networks, 4(2): 251-257, 1991.
Tzu-Kuo Huang, Alekh Agarwal, Daniel Hsu, John Langford, and Robert Schapire, Efficient and parsimonious agnostic active learning. Advances in Neural Information Processing Systems, 28, 2015.
Matti Kääriäinen. Active learning the non-realizable case. In International Conference on Algorithmic Learning Theory, pages 63-77. Springer, 2006.
Mina Karzand and Robert D Nowak. Maximin active learning in overparameterized model classes. IEEE Journal on Selected Areas in Information Theory, 1 111):677-177, 2020.
Yongdai Kim, Ilsang Ohn, and Dongha Kim. Fast convergence rates of deep neural networks for classification. Neural Networks, 138:179-197, 2021.
Suraj Kothawade, Nathan Beck, Krishnateja Killamsetty, and Rishabh Iyer. Similar: Submodular information measures based active learning in realistic scenarios. Advances in Neural Information Processing Systems, 34, 2021.
Samory Kpotufe, Gan Yuan, and Yunfan Zhao. Nuances in margin conditions determine gains in active learning. arXiv preprint 1rXiv:2110.08444 2021.
Akshay Krishnamurthy, Alekh Agarwal, Tzu-Kuo Huang, Hal Daumé III, and John Langford. Active learning for cost-sensitive classification. In International Conference on Machine Learning, pages 1915-1924. PMLR. 2017.
Akshay Krishnamurthy, Alekh Agarwal, Tzu-Kuo Huang, Hal Daumé III, and John Langford. Active learning for cost-sensitive classification. Journal of Machine Learning Research, 20:1-50, 2019.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convolu- tional neural networks. Advances in neural information processing systems, 25, 2012.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553):4364444 2015.
Gene Li, Pritish Kamath, Dylan J Foster, and Nathan Srebro. Eluder dimension and generalized rank. arXiv preprint 10Xiv:2104.06970, 2021.
Andrea Locatelli, Alexandra Carpentier, and Samory Kpotufe. Adaptivity noise parameters in nonparametric active learning. In Proceedings of the 2017 Conference on Learning Theory, PMLR, 2017.
Andrea Locatelli, Alexandra Carpentier, and Samory Kpotufe. An adaptive strategy for active learning with smooth decision boundary. In Algorithmic Learning Theory, pages 547-571. PMLR, 2018.
Jianfeng Lu, Zuowei Shen, Haizhao Yang, and Shijun Zhang. Deep network approximation for smooth functions. SIAM Journal on Mathematical Analysis, 5365):5465-5506, 2021.
Pascal Massart and Élodie Nédélec. Risk bounds for statistical learning. The Annals of Statistics, 34 (5):2326-2366 2006.
Stanislav Minsker. Plug-in approach to active learning. Journal of Machine Learning Research, 13 (1), 2012.
Greg Ongie, Rebecca Willett, Daniel Soudry, and Nathan Srebro. A function space view of bounded norm infinite width relu nets: The multivariate case. In International Conference on Learning Representations, 2020.
Rahul Parhi and Robert D Nowak. Banach space representer theorems for neural networks and ridge splines. Mach. Learn. Res., 22(43):1-40, 2021.
Rahul Parhi and Robert Nowak. What kinds of functions do deep neural networks learn? insights from variational spline theory. SIAM Journal on Mathematics of Duta Science, 4(2):464 489, 2022a.
Rahul Parhi and Robert Nowak. Near-minimax optimal estimation with shallow relu neural networks. IEEE Transactions on Information Theory, 2022b.
D Pollard. Convergence of Stochastic Processes. David Pollard, 1984.
12

---

Nikita Puchkin and Nikita Zhivotovskiy. Exponential savings in agnostic active learning through abstention. arXiv preprint arXiv:2102.0045,, 2021.
Pengzhen Ren, Yun Xiao, Xiaojun Chang, Po- Yao Huang. Zhihui Li, Brij B Gupta, Xiaojiang Chen, and Xin Wang. A survey of deep active learning. ACM Computing Surveys (CSUR), 54(9):1-40, 2021.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. NIPS, pages 2256-2264. Citeseer, 2013.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. In International Conference on Learning Representations, 2018.
Burr Settles, Active learning literature survey. 2009.
Shubhanshu Shekhar, Mohammad Ghavamzadeh, and Tara Javidi. Active learning for classification with abstention. IEEE Journal Selected Areas in Information Theory, 2(2):705-7199 2021.
Alexander B Tsybakov. Optimal aggregation of classifiers in statistical learning. The Annals of Staristics, 32(1):135-166, 2004.
Michael Unser. Ridges, neural networks, and the radon transform. arXiv preprini arXiv:2203.02543 2022.
VN Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2):264, 1971.
Martin J Wainwright. High-dimensions statistics: A non-asymptotic viewpoint, volume 48, Cam- bridge University Press, 2019.
Liwei Wang. Smoothness, disagreement coefficient, and the label complexity of agnostic active learning. Journal of Machine Learning Research, 12(7), 2011.
Zhilei Wang, Pranjal Awasthi, Christoph Dann, Ayush Sekhari, and Claudio Gentile. Neural active learning with performance guarantees. Advances in Neural Information Processing Systems, 34, 2021.
Andrew Chi-Chin Yao. Probabilistic computations: Toward unified measure of complexity. In 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), pages 222-227. IEEE Computer Society, 1977.
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94: 103-114, 2017.
Dmitry Yarotsky. Optimal approximation of continuous functions by very deep relu networks. In Conference learning theory, pages 639-649. PMLR, 2018
Yinglun Zhu and Robert Nowak. Efficient active learning with abstention. arXiv preprint arXiv:2204.0000 00043, 2022.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 5 for discussions on limitations and directions for future work.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our paper is theoretical in nature, and there is no negative societal impact of our work in the foresecable future.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Assumptions are clearly stated in the statement of each theorem.
(b) Did you include complete proofs of theoretical results? [Yes] Complete proofs are provided in the Appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [N/A]
Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you 're
using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable?
[N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(C) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "yHFzgqr23jN", "reviewer": "Reviewer_qadK", "summary": "This paper shows that active learning with neural networks can provably achieve the minimax label complexity, up to disagreement coefficient, and other logarithmic terms under the assumption that the neural network is obtained from $\\alpha$-Sobolev space. Then the authors try to generalize the idea up to the Radon $BV^2$ space.\n\nAs claimed by the authors, the main contributions of the paper are **1)** to extend the understanding of how approximation affects active learning to achieve fast rates (e.g., under Tsybakov noise in Theorem 1) which corresponds to Theorem 6, and **2)** to identify conditions that greatly relax the (previous) approximation requirement in the learning with abstention setup (to develop Theorem 2) which corresponds to Theorem 7.\n\nI think the key component of the paper is building a bridge by extending the active learning analysis in the parametric setting to the non-parametric DNN setting leveraging the universal approximation property of the ReLU activated neural networks.", "questions": "This paper contains a lot of materials from existing literature, so contains a long proof to digest. I still have some questions to clarify. Once questions are clarified, I would rather consider updating my rating. Thank you.\n\n1. In algorithm 2, why $\\beta_m$ is chosen to be adaptively decreasing? This implies that the abstention region seems to be adaptively changing(decreasing) as the epoch $m$ increases. How is this decreasing $\\beta_m$ facilitating the exponential gain toward the label complexity in Algorithm 2? I was not able to grasp the full intuition.\n2. How is the geometrically increasing query length contributing to the exponential gain of the label complexity? In other words, what's the motivation of the geometrically increasing query length? And how is it related to the decreasing $\\beta_m$? I understand it is necessary for analysis, but the cost of the geometrically increasing query seems to be expensive (at least for making a decision if it is under abstention or not) unless it produces an exponentially small size of the non-abstention selection for a real label query. I see some relation at Lemma 10, but the decreasing abstention region (as described in Question 1 above) seems to be conflicting with the geometrically increasing number of points in the abstention region because of the geometrically increasing query length.\n3. At L955 of Appendix D5, the condition described in the equation $(19)$ seems to be important as it is also used in the proof of Theorem 7. But I am not able to find where the condition $(19)$ has been established in the proof of Theorem 15. Can you elaborate on where the equation $(19)$ has been established/or used in the proof? (I suspect L965, but it's not sufficient.)\n4. In practice, the diversification of point selection is essential to improve active learning performance.  As far as I see, the Tsybakov noise condition controls the number of ambiguous (and redundant) points in the input domain. For exponential speed up, in Theorem 7, the parameter $\\beta$ does not appear anymore. It might be embedded somewhere in the proof, but I was not able to find it. Can you explain the relationship between the Tsybakov noise parameter $\\beta$ and the number of queries in Theorem 7? Intuitively, if the redundant points are concentrated around **the outside of the abstention region** but still inside the query range, algorithm 2 might be failed. I was wondering where to avoid such a case.\n5. At L858, I was wondering if $M_t(f)$ is still a martingale with abstention option. In other words, I want to understand the relationship between the martingale condition and the exponential gain of the label complexity. If it is a martingale, the active learning process is a fair game in some sense. How is it possible to achieve the exponential speed-up under this martingale regime?\n\n---------------------------------------------------------------------------------------------------------------------------------------------------\nAfter rebuttal, the authors clarified all my questions properly.\n\nBecause of the limited review process time, I cannot assure to confirm the whole correctness of the paper by myself.\nHowever, as a collective effort to confirm the result, I do not see any serious issues or problems in this paper.\nAccordingly, I updated my rating given that\n- the closely related work [1] needs to be confirmed officially because I see lots of overlapped material with the paper [1] as cited by the authors,\n- the authors revise the paper properly.\n\nThank you.\n\n[1] Zhu, Yinglun, and Robert Nowak. \"Efficient Active Learning with Abstention.\" arXiv preprint arXiv:2204.00043 (2022).", "limitations": "1. In practice, geometrically increasing query length might be unrealistic (with/without abstention). Practical active learning typically assumes a constant size (or budget-constrained size) of the query for each epoch. I was wondering if there is a way to improve both the algorithm and the analysis with a constant query size.\n2. As mentioned, it is not straightforward how to generalize the idea to the multi-class classification problem.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "** Strength\n1. This paper provides an extensive theoretical insight into how deep active learning could be successful in the binary classification problem.\n2. This paper proves the exponential gain of the label complexity in deep active learning with the abstention option.\n\n** Weakness\n1. The paper focuses on the binary classification problem, which is the fundamental case to build necessary theoretical tools. Still, it doesn't seem to be straightforward how to generalize the insight to the multi-class classification problems when we apply the proposed algorithm in practice.\n2. The presentation could be improved. The non-parametric setting mainly focuses on the $\\alpha$-Sobolev space (weakly differentiable space up to $\\alpha$-th order) in the main article. But after reading the whole paper including the supplementary material, Radon $BV^2$ space is a better function space to consider. Because the contents of the main article are heavily relying on the supplementary material, it might be better to re-organize the paper by focusing on the Radon $BV^2$ space instead of the $\\alpha$-Sobolev space. Then all relevant results from $\\alpha$-Sobolev can be moved to the supplementary material. \n\n** Minor points\n1. At the footprint on page 3, \"exponentially my sub-regions\" should be \"exponentially many sub-regions\".\n2. At Algorithm 2, $Pdim(\\cdot)$ doesn't seem to be defined in the main article. I was able to locate it at L749 of Definition 6 in the supplementary material.\n3. At L785, I cannot find the definition of $\\mathcal{N}(\\frac{\\kappa'}{8L};\\mathcal{X},\\|\\cdot\\|_2)$. I understand it is the covering (or sphere-packing) number, but the definition seems to be missing.\n4. At L793, balls of the radius $\\frac{\\kappa}{8L}$ should be $\\frac{\\bar{\\kappa}}{8L}$.\n5. At L807, Proposition 8 of Appendix D.1.3, the second condition should be $0$ if $f(x)\\leq 0$ instead of $-1$ if $f(x)\\geq 1$.\n6. At L835 of Appendix D.2, $B_{1}^{d}$ should be $B_{r}^{d}$.\n7. At L914 of Appendix D.4.2, $(a+b)^2\\leq a^2+b^2$ should be $(a+b)^2 \\leq 2(a^2+b^2)$.\n8. At L1046 of Appendix E.2.2., the notation $\\alpha$ is conflicting with the notion $\\alpha$-Sobolev space. As far as I understand, this $\\alpha$ in L1046 has nothing to do with $\\alpha$-th order weak differentiability. Please reconsider using another letter in either case.\n9. At L1057, $\\bar{a}:=\\frac{\\gamma}{8M}$ should be $\\bar{\\alpha}:=\\frac{\\gamma}{8M}$.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ZO7KNop89eH", "reviewer": "Reviewer_ynw4", "summary": "\nThe authors investigate the label complexity guarantees for deep active learning from the nonparametric classification perspective. They first look into the RobustCAL algorithm which only queries data points lying in the region of disagreement and provides the near minimax optimal label complexity, bringing closer the gap between theory and practice of deep active learning. Next they replace the low noise condition with abstention and Chow’s excess error, which enables exponential speedups and leads to sharper concentration results. Last, they conclude with extensions from Sobolev/H\\\"{o}lder space to Radon BV^2 space.", "questions": "I am not entirely familiar with the field, but I enjoy reading the paper. I wonder how the theorem can be carried over to implementation like how to decide whether to implement abstention, and like how to verify the conditions/assumptions of the theorems.", "limitations": "The current work mainly focuses on classification with binary labels. And the main theorems have dependence on the disagreement coefficient or Chow’s errors (the authors identify as well).", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The authors provide a detailed overview of related literature in the field. The presentation of the paper is clear and easy to follow. The contributions are theoretical. Theorem 6 provides near optimal label complexity up to disagreement coefficients and logarithmic factors. Theorem 7 provides good theoretical intuition for why abstention is efficient in practice.  ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5s4sstr1oT4", "reviewer": "Reviewer_TeP9", "summary": "This paper studies the deep active learning problem and focuses on the rigorous label complexity guarantees. Deep active learning has received practical success, however, there lack of rigorous theoretical guarantees of deep active learning. In this paper, they consider a nonparametric setting. They show the relationship between approximation and active learning. They also give an analysis of the disagreement coefficient. ", "questions": " - Their paper has a lot of results. Which one is the most significant result?", "limitations": " - their result relies on the disagreement coefficient, which does not have explicit expression.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n - Their result is easy to extend and can be applied to a large class of smooth functions that have recently been proposed. Their result can be applied to ReLU neural networks.\n - In both passive and active settings, they can learn by the neural network to achieve near minimax optimal label complexities, which gives a new perspective on nonparametric learning\n\nCons:\n - Their result is meaningful when the disagreement coefficient is well-bounded. However, they left the analysis of the disagreement coefficient for future work. The disagreement coefficient does not have an explicit expression, which makes it hard to judge how important their results are. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4sckcuNYBpC", "reviewer": "Reviewer_MozJ", "summary": "This paper provides the first near minimax optimal label complexity guarantees for deep active learning.\nSection 2 analyzes the label complexity of deep active learning under Tsybakov noise. Section 3 analyzes it under another setting with an abstention option and without any low noise assumption. Section 4 extends the results to Radon BV2 space.", "questions": "1. In line 202 under Theorem 3, the paper says \"The architecture of the neural network $f_{dnn}$ appearing in the above theorem is independent of $f^*$\". Could the authors elaborate more on this conclusion? Intuitively, given a function $f^*$, why is the architecture of the neural network that can best approximate $f^*$ within a small error **independent** of $f^*$?\n2. Following the above question, since both $H_{dnn}$ and $F_{dnn}$ are specific sets of neural networks defined based on the architecture of $f_{dnn}$, the problem setting becomes very limited if $f_{dnn}$ is chosen based on the true function $f^*$.\n3. How important is the smooth assumption on $\\eta$? Section 4 demonstrates how the results can be extended to Radon BV2 space. Can we assume that the results can be extended to any space as long as the approximation power of the neural networks can be proved?\n4. Section 3 states that the results are generalized from that of Zhivotovskiy (2021); Zhu and Nowak (2022). Line 316-323 presents how this paper is new compared to Zhu and Nowak (2022). How about the work of Zhivotovskiy (2021)? How is section 3 technically novel compared to Zhivotovskiy (2021)?\n5. Any numerical simulations?\n6. There are many grammar errors:\n- line 181: exhibit -> exhibits\n- line 212: has well-controlled -> has a well-controlled\n- line 287: analyze -> analyzes\n- line 323: function -> functions\n- ...", "limitations": " ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. This paper contributes new theoretical results to the area of deep active learning.\n2. The proof techniques could be potentially useful for the theoretical study in this area. I like how the results do not require the Bayes classifier to be in the hypothesis class. Instead, it only requires a good approximation to be in the hypothesis class.\n3. A new algorithm with theoretical support has been proposed.\n\nWeakness:\n1. The paper does not have a conclusion section.\n2. No experiment is provided to support the claims. Especially, a new algorithm (Algorithm 2) is proposed, but no numerical simulation is demonstrated.\n3. The limitation of the chosen set of neural networks $H_{dnn}$ and $F_{dnn}$ has not been discussed.\n4. Results in Section 2 and Section 3 appear to be a bit disconnected.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept