On the Convergence of Loss and Uncertainty-based Active Learning Algorithms
Authors: Daniel Haimovich
Dima Karamshuk
Fridolin Linder
Niek Tax
Milan Vojnovic
Venue: NeurIPS 2024 poster (2024)
Keywords: active learning
uncertainty sampling
loss-based sampling
Primary area: active_learning
TL;DR: We consider the convergence rates of loss and uncertainty-based active learning algorithms under various assumptions

Abstract: We investigate the convergence rates and data sample sizes required for training a machine learning model using a stochastic gradient descent (SGD) algorithm, where data points are sampled based on either their loss value or uncertainty value. These training methods are particularly relevant for active learning and data subset selection problems. For SGD with a constant step size update, we present convergence results for linear classifiers and linearly separable datasets using squared hinge loss and similar training loss functions. Additionally, we extend our analysis to more general classifiers and datasets, considering a wide range of loss-based sampling strategies and smooth convex training loss functions. We propose a novel algorithm called Adaptive-Weight Sampling (AWS) that utilizes SGD with an adaptive step size that achieves stochastic Polyak's step size in expectation. We establish convergence rate results for AWS for smooth convex training loss functions. Our numerical experiments demonstrate the efficiency of AWS on various datasets by using either exact or estimated loss values.

On the Convergence of Loss and Uncertainty-based Active Learning Algorithms
Daniel Haimovich Meta, Central Applied Science Canielha@meta.co
Dima Karamshuk Meta, Central Applied Science
karamshuk@meta.co
Fridolin Linder
Niek Tax
Meta, Central Applied Science fli Flinder@meta.co com
Meta, Central Applied Science niekSmeta. com
Milan Vojnović London School of Economics m. jo ac uk
Abstract
We investigate the convergence rates and data sample sizes required for training a machine learning model using a stochastic gradient descent (SGD) algorithm, where data points are sampled based on either their loss value uncertainty value. These training methods are particularly relevant for active learning and data subset selection problems. For SGD with a constant step size update, we present convergence results for linear classifiers and linearly separable datasets using squared hinge loss and similar training loss functions. Additionally, we extend our analysis to more general classifiers and datasets, considering wide range of We propose novel algorithm called Adaptive- Weight Sampling (AWS) that utilizes SGD with an adaptive step size that achieves stochastic Polyak's ' step size expectation. We establish convergence rate results for AWS for smooth convex training loss functions. Our numerical experiments demonstrate the efficiency AWS on various datasets by using either exact estimated loss values.
sampling strategies and smooth convex training loss functions.
Introduction
In practice, when training machine learning models for prediction tasks (classification or regression), one often has access to an abundance of unlabeled data, while obtaining the corresponding labels may entail high costs. This may especially be the case in fields like computer vision, natural language processing, and speech recognition. Active learning algorithms are designed to efficiently learn prediction model by employing a label acquisition, with the goal of minimizing the number of labels used train an accurate prediction model.
Various label acquisition strategies have been proposed, each aiming to select informative points for the underlying model training task; including query-by-committe [Seung et al., 1992 expected
model change [Settles et al. 2007], expected error reduction (Roy and McCallum 2001]. expected
variance reduction (Wang et 2016), and mutual information maximization Kirsch al. 2019
Kirsch and Gal 2022
common label acquisition strategy involves estimating uncertainty, which can be viewed as self-disagreement about predictions made by a given model. Algorithms using an uncertainty
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

acquisition strategy are referred to as uncertainty-basee active learning algorithms. Different variants of uncertainty strategies include margin of confidence. least confidence, and entropy-based sampling
[guuen et al. [022]] Recently, a loss-based active learning approach gained attention in research Yoo
and Kweon [209]] Lahlou et al. [202]] Nguyen et al. [2021] [uo et al. [202T] and is now applied at scale in industry, such as for training integrity violation classifiers at Meta. This method involves
selecting points for which there is a disagreement between the predicted label and the true label, as measured by loss function. Since the true loss of data point is unknown prior to the acquisition of the label, in practice, it is estimated using supervised learning. Loss-based sampling aligns with the spirit of the perceptron algorithm [Rosenblatt 1958], which updates the model only for falsely-classiff points.
Convergence guarantees for some incertainty-basee active learning algorithms have recently been established, such as for margin of confidence sampling [Raj and Bach] [022]. By contrast, there are only limited results on the convergence properties of loss-based active learning algorithms, as these only recently been started to be studied, e.g., Liu and Li [2023].
The primary focus of this paper is to establish convergence guarantees for stochastic gradient descent (SGD) algorithms where points are sampled based on their loss. Our work provides new results on conditions that ensure certain convergence rates and bounds on the expected sample size, accommodating various data sampling strategies. Our theoretical results are under assumption that the active learner has access to an oracle that provides unbiased estimate of the conditional expected loss for a point, given the feature vector of the point and the current prediction model. In practice, the loss cannot be evaluated at acquisition time since labels are yet unknown. Instead, a separate prediction model is used for loss estimation. In our experiments, we assess the impact of the bias and noise in such a loss estimator. Our convergence rate analysis accommodates also uncertainty-based data selection, for which we provide new results.
Uncertainty and loss-based acquisition strategies are also of interest for the data subset selection problem, often referred to as core-set selection or data pruning. This problem involves finding a small subset of training data such that the predictive performance of a classifier trained on it is close to that of classifier trained on the full training data. Recent studies have explored this problem in the context of training neural networks, as seen in works like Toneva et al.] [2019]. Coleman et al. (2020). + Paul et al. 2021 Sorscher et al. 2022). Mindermann et al. 2022]. such scenarios, the oracle can evaluate an underlying loss function exactly, avoiding the need for using a loss estimator.
There is large body of work convergence of SGD algorithms, e.g. see Bubeck] (2015) and Nesterov [2018). These results are established for SGD algorithms under either constant, diminishing or adaptive step sizes. Recently, Loizou al. [202T), studied SGD with the stochastic Polyak's step size, depending on the ratio of the loss and the squared gradient of the loss of a point. Our work
proposes an adaptive-window sampling algorithm and provides its convergence analysis, with the algorithm defined as SGD with sampling of points and an adaptive step size update that conform to the stochastic Polyak's 's step size expectation. This is unlike to the adaptive step size SGD algorithm by Loizou et al. [0211 which does not use sampling.
1.1 Summary of our Contributions
Our contributions can be summarizes as given in the following points:
For SGD with constant step size, we present conditions under which a non-asymptotic convergence rate of order (1//n) holds, where n represents the number of iterations of the algorithm, i.e., the number of unlabeled points presented to the algorithm. These conditions enable us to establish convergence rate results for loss-based sampling in the case of linear classifiers and lincarly separable datasets, with the loss function taking various forms such as the squared hinge loss function, generalized hinge loss function, or satisfying other specified conditions. Our results provide bounds for both expected loss and the number of sampled points, encompassing different loss-based strategies. These results are established by using a convergence rate lemma that may be of independent interest.
For SGD with a constant step size, we provide new convergence rate results for more general classi- fiers and datasets, with sampling of points according to an increasing function π of the conditional expected loss of point. In this case, we present conditions for smooth convex training loss functions under which a non-asymptotic convergence rate of order (1/T-))//n) holds, where IT is the primitive function of क. These results are established by leveraging the fact that the algorithm behaves

---

akin to SGD algorithm with an underlying objective function, as referred to as an equivalent loss in Liu and Li 2023]. J. allowing us to apply known convergence rate results for SGD algorithms.
We propose Adaptive- Weight Sampling (AWS), a novel learning algorithm that combines a sampling- based acquisition strategy with adaptive step-size SGD update, achieving the stochastic Polyak's step size update in expectation, which can be used with any differentiable loss function. We establish a condition under which a non-asymprotic convergence rate of order ((1/n) holds for AWS with smooth convex loss functions. We present uncertainty and loss-based strategies that satisfy this condition for binary classification, as well as an uncertainty strategy for multi-class classification.
We present numerical results that demonstrate the efficiency of AWS on various datasets.
1.2
Related Work
The early proposal of the query-by-committe (QBC) algorithm by [Seung et al. 1992 demonstrated
the benefits of active learning, an analysis of which was conducted under the selective sampling model by |Freund et al. [1997] and Gilll-bacchracl et al. [2005]. Dasgupta et al. [2099] showed that
the performance of QBC can be efficiently achieved by a modified perceptron algorithm with adaptive
filtering. The efficient and label-optimal learning of halfispaces was studied by Yan and Zhang [2017)
and, subsequently, by [hhen (202T]. Online active learning algorithms, studied under the name of
selective sampling, include works by Bianchi et al. 2006 2009 Dekel et al.) 2012 Orabona and Cesa-Bianchi] 2011 Cavallanti et al. 2011 Agarwall 2013]. For a survey, refer to Settles 2012]
Uncertainty sampling has been utilized for classification tasks since as early as
[ewis and Gale
1994], and subsequently in many other works, such as [Schohn and Cohn 2000 Zhu et al. 2010
Yang et al. 2015 Yang and Loog 2016 Lughofer and Pratamal [2088]. Mussmann and Liang [0188] demonstrated that threshold basse uncertainty sampling on a convex loss can be interpreted as performing a pre-conditioned stochastic gradient step on the population zero-one loss. However, none of these works have provided theoretical convergence guarantees.
The convergence of margin of confidence sampling was recently studied by Raj and Bach 20022) who demonstrated linear convergence for linear classifiers and linearly separable datasets, specifically for the hinge loss function, for a family of selection probability functions and an algorithm that performs SGD update with respect to the squared hinge loss function. However, our results for linear classifiers and linearly separable datasets differ, our focus lies on loss-based sampling strategies and providing bounds on the convergence rate of loss function and the expected number of sampled points. These results are established using a convergence rate lemma, which may be of independent interest. is noteworthy that the convergence rate for uncertainty-bast bbssed sampling, as in Theorem 3.1 of Raj and Bach 2022) can be derived by checking the conditions of the convergence rate lemma.
loss-based active learning algorithm was proposed by Yoo and Kweon (011)) comprising a loss prediction module and a target prediction model. The algorithm uses the loss prediction module to compute a loss estimate and prioritizes sampling points with a high estimated loss under the current prediction model. Lahlou et al. [2022] generalize this idea within a framework for uncertainty prediction. However, neither Yoo and Kweon 2019] nor Lahlou et al. [022] provided theoretical guarantees for convergence rates. Recent analysis of convergence for loss and uncertainty based
active learning strategies has been presented by [Lu and Li [023]. Specifically. they introduced the concept of an equivalent loss, demonstrating that a gradient descent algorithm employing point sampling can be viewed as a SGD algorithm optimizing an equivalent loss function. While they focused on specific cases like sampling proportional to conditional expected loss, our results allow for sampling based on any continuous increasing function of expected conditional loss, and provide explicit convergence rate bounds in terms of the underlying sampling probability function.
In addition, Loizou al. 2021 introduced a SGD algorithm featuring an adaptive stochastic Polyak's step size, which has theoretical convergence guarantees under various assumptions. This algorithm showcased robust performance in comparison to state-of- of-the--rt optimization methods, especially when training over ver-parametrized models. Our work proposes a novel sampling method that employs stochastic Polyak's ' step size in expectation, offering a convergence rate guarantee for smooth convex loss functions, contingent on condition related to the sampling probability function. Notably, we demonstrate the fulfilment of this condition for logistic regression and binary cross-entropy loss functions, encompassing both loss-based strategy involving proportional sampling to absolute error
3

---

loss and an uncertainty sampling strategy. Furthermore, we extend this condition to hold for an uncertainty sampling strategy designed for multi-class classification.
2 Problem Statement
We consider the setting of streaming algorithms where a machine learning model parameter 0, updated sequentially, upon encountering each data point, with (21,81),, ...; (Xin Vn) E X' x y denoting the sequence of data points with the corresponding labels, assumed to be independent and identically distributed with distribution D. Specifically, we consider the class of projected SGD algorithms defined as: given an initial value 01 E 9,
Bz+1= = Pe. (0, - 2₁ Vel(ar, ye, 0,)), for t 2
where É X x y x + R is training loss function, 24 is stochastic step size with mean ((2,,, yt, 0₂) for some function Ç X' y x θ + R., O, O and Pe, is the projection function. i... (e.(u) which requires no projection. For binary classification tasks, we assume y [-1,1]. For every t 0, we define 0. = (1/1) Ei_ 0,.
arg min.ge. ||u - u/|. Unless specified otherwise, we consider the case On = O,
By defining the distribution of the stochastic step size in Equation (I) appropriately, we can accommodate different active learning and data subset selection algorithms. In the context of active learning algorithms, at each step f, the algorithm observes the value of H, and decides whether or not to observe the value of the label yt- The value of 2, determine whether or not we observe the label yt- Deciding not to observe the value of the label y/ implies the step size of value zero (not updating the machine learning model).
For the choice of the stochastic step size, we consider two cases: (a) Constant-Weigee Sampling: a Bernoulli sampling with constant step size, and (b) Selaptive-Weight Sampling: a sampling that achieves stochastic Polyak's step size in expectation. For case (a), 21 is the product of a constant step size y and a Bernoulli random variable with mean π ( yt. 0z). For case (b), <(x, y. 0) is the "stochastic" Polyak's 's step size, and & is equal to Ç(I2, St. 0 Ut. 0²) with probability (Z ye, 0.) and equal otherwise. Note that using the notation x (I. y, 0) allows for the case when the sampling probability does not depend on the value of the label y.
For loss-based sampling, т is an increasing function of some loss function 6", which does not necessarily correspond to the training loss function f. Specifically, for binary classifier with p(x, y, 8) denoting the expected prediction label, sampling proportional
the absolute error loss is defined as (e() = wt" where (3r,, y. 0) = ly p(x, y, 0)l and w E (0, 1/2). For an uncertainty-bused sampling, æ is function of some quantity reflecting the uncertainty of the prediction model.
Our focus is on finding convergence conditions for algorithm ( and convergence rates under these conditions, as well as bounds the expected number of points sampled by the algorithm.
Additional Assumptions and Notation For binary classification, we say that data is separable if, for every point (z, v) E X' x V, either y = 1 with probability 1 or y = -1 with probability 1. The data is linearly separable if there exists 0 E θ such that y = sgn(x (*) for every x E X.. Linearly separable data has a p" -arrin if |x: lr 2 p" for every x E X, for some 0" e.
Some of our results are for linear classifiers, where the predicted label of point x is function of x 0. For example, a model with predicted label sgn 0) is a linear classifier. For logistic regression, the predicted label is with probability ax 8) and -1 otherwise, where is the logistic function defined as (z) = 11 )) For binary classification, we model the prediction probability of the positive label as (x 0), where o R. + j0, 1] is an increasing function, and o--u) + (u)) = for all u E R. The absolute error loss takes value 1 - o (x 6) if y = 1 or value (a 0) if y = 11, which corresponds to 1 - (yx T 0). The binary cross-entropy loss for a point (a, v) under model parameter 0 can be written as f(z, y, 0) = log(o 0)). Hence, absolute error loss-based sampling corresponds to the sampling probability function x 1 - c
For any given (x. E X x V, the loss function E(x, y, 0) is considered smooth on O' C C if it has a Lipschitz continuous gradient on O', i.e., there exists Ia., such that //V y, 01) 0211 for all 0,, 0z E O'. For any distribution over X x y, smooth. -mmoohhh
Vol(a, 02)1l < 10 ((an))y y, 0)] is ((as)~~ w [Z.
4

---

3 Convergence Rate Guarantees
In this section, we present conditions on the stochastic step size of algorithm (T) under which we can bound the total expected loss and the expected number of samples. For the Constant- Weight Sampling, we provide conditions that allow to derive bounds for linear classifiers and linearly separable datasets and more general cases. For Adaptive-WW Adaptive-Weight Sampling, we offer a condition that allows us to establish convergence bounds for both loss and incertainty-based sampling.
3.1
Constant- Weigtt Sampling
Linear Classifiers and Linearly Separable Datasets We focus on binary classification and briefly discuss extension multi-class classification. We consider the linear classifier with the predicted label sgn(æ: 0). With a slight abuse of notation, let f(z, y, 0) = {(u) and ( y, 0) = ग (w) where
u yr We assume that the domain X' bounded, i.e., there exists such that || < R for all
X. ||0 0* || S S for some S 2 O, and that the data is -maginn linearly separable.
We present convergence rate results for the training loss function corresponding to the squared hinge loss function, i.e. f(u) (1/2) max u, 0}². Our additional results also cover other cases, including class of smooth convex loss functions and a generalized smooth hinge loss function, which are presented in the Appendix.
Assume that p² 1, the loss function is the squared hinge loss function, and the sampling probability function n is such that for all u S 1, TTu)= S B/2 and
Theorem 3.1.
= B
T(u) 2 x (e(u))
+ P.y iuu)
for some constants 0 < 3 S 2 and μ 2 v2/(p" 110: - 0-11 S and {0r)es1 according to algorithm
Then. for any initial value 0 such that
with 7 R.
52
E [c(yx T 0n)]
SE
Σ
Elyrn) 0.) To.)
<
3
where (I. v) is an independent sample of labeled data point from D.
Moreover, if the sampling is according to x²,, then the expected number of sampled points satisfies
< min ( RRSH/BVn, - 3n 3n..
x x'(([xz]TT)) (00)
E
Condition (2) requires that the sampling probability function π is lower bounded by an increasing, concave function л² of the loss value. This fact, along with the expected loss bound, implies the asserted bound for the expected number of samples. The expected number of samples is ((vn) concerning the number of iterations and is ((1((p" 1)) concerning the margin p² 1.
Theorem 3.T and our other results for linear classifiers and linearly separable datasets, are established using convergence rate lemma, which is presented in Appendix A.2 along with its proof. This lemma generalizes the conditions used to establish the convergence rate for an uncertainty-baser sampling algorithm by Raj and Bach 2022). with the sampling probability function π Tu)) 1/(1 + j./z)), for some constant y >> O. It can be readily shown that Theorem 3. 1 in Raj and Bach 2022 follows from convergence rate lemma with the training loss function corresponding to the squared hinge loss function and the evaluation loss function (used for convergence rate guarantee) corresponding to the hinge loss function. Further details the convergence rate lemma discussed in Appendix 1.2. 1..2.
The convergence rate conditions for multi-class classification with the set of classes y are the same as for binary classification, with u(r, y, 0) := 0,, <>X/))>>( x. Oy., except for an additional factor of 2 in one of the conditions (see Lemma 10 in the Appendix). Hence, all the observations remain valid for the multi-class classification case.
5

---

Table 1: Examples of sampling probability functions.
(a)
I1(r))
11 (a)
1 1-c --"
x +
R2 < 22x for small x
min 1]
20
S11
//x
S 1/2
22
221
2 +
2 1/2
min((x/b)), 1 0,6
tu
a x 2 a
6140 (1 + a)
1+a
x 14a
x I 14a
14a
a
x
ite
Z
log(L + pa)
(2/11)) for small r
14pe
I+AVE
V
u²
2
log(1 + pVT)
= ((3/2)/1)))))) for small x
More General Classifiers and Datasets We consider algorithm ( where 2, is product of fixed step size 7 and Bernoulli random variable &e with mean <(,, y, 0). Let gr V Vol((,,, yt. 0z), which is random vector because G is a random variable and (Ir, y/) is a sampled point. Following Liu and Li [002)] we note that the algorithm (T) is SGD algorithm with respect objective function E with gradient
V Voē(0) = Bar y, 0) Vel(,, y. 0)]
where the expectation is with respect to r and y. This observation allows us to derive convergence rate results by deploying convergence rate results that are known to hold for SGD under various assumptions function e, variance of stochastic gradient vector and step size. A function e satisfying condition (3) is referred to as an equivalent loss in Liu and Li [2033]
Assume that the sampling probability is an increasing function of the conditional expected loss ((z 0) = [, y, 0) z/. With a slight abuse of notation, we denote this probability as ((((z, 0)) where π I [0, 1] is an increasing and continuous function. Let Il be the primitive of n, i.e.
II' = x. We then have
{()) ([ 0))]
If E(x, y, 0) is a convex function, for every (xr, v) E X' x V, then i a convex function.
This framework for establishing convergence rates allows to accommodate different sampling strategies and loss functions. The next lemma allows us to derive convergence rate results for expected loss with respect loss function l by applying convergence rate results for expected loss with respect to loss function É (which, recall, is the equivalent loss function).
Lemma 3.2. Assume that for algorithm with loss-based sampling according to n, for some functions f1,..., Im have
122
E
((0.)
< inf (0)
Σ f(n).
(5)
71
Then, it holds:
E
E(O.)
inf (((T))(((()))))) + Σ I ((((n))
We apply Lemma 3.2 to obtain the following result.
Theorem 3.3. Assume that E is convex function, i is L-smooth, Og is convex set, S supaee, ||0 - 11. and E[T(((x, 0))l[ y. 0.0) || s oz. Then, for algorithm with 7 1/(L + (o/R) n/2).
V2So Vn
LS2
B(e(ūm)) <
(().)
< inf ( + -1
+ I
8
Note that the bound on the expected loss in Theorem 3.3 depends on through I--1 and o² Specifically, we have a bound depending on क only through II-1 by upper bounding o² with supace, Elll Vol(,, v. [].

---

For convergence rates for large values of the number of iterations n. the bound in Theorem 3.2 crucially depends on how II (z) behaves for small values of r. In Table we show II and II for several examples of sampling probability function æ. For all examples in the table, (x) is sub-linear in x for small x. For instance, for absolute error loss sampling under binary cross-entropy loss function, x (2)
e e=. II (x) is approximately /2r for small z. For this case, we have
the following corollary.
Corollary 3.4. Under assumptions of Theorem 3.3 sampling probability π(²) = 1 - e e and 16
n 2 max {(5) 2So
2 2,
LS3) it holds x: 9
E( S E
E(O.)
S inf in (((0)) + 2 22/4///0,, n
1
+ 2VLS 1
/n
vn
By using a bound on the expected total loss, we can bound the expected total number of sampled points under certain conditions as follows.
Lemma 3.5. The following bounds hold:
1. Assume that is a concave function,, then E. EE π (f(1ss 0,)) S Ei ((0e)) n.
2. Assume that a K-Lipschitz or that for some K > 0, (() S min for all 2 then E |E>=1 x (L(2,, 0()) & min [KE] |Ei=1 {(0,) n).
We remark that a concave function for all examples in Table | without any additional conditions, except for (f)) min [ (e/b)², 1} which is concave under assumption 0 < a S 1. We remark also that for every example in Table I except the last one, (f) S min{Ke, 1} for some > 0. Hence, for all examples in Table D we have bound for the expected number of sampled points provided we have a bound for the expected loss.
3.2 Adaptive- Weight Sampling
In this section propose the Adaptive-Weile Sampling (AWS) algorithm that combines Bernoulli sampling and an adaptive SGD update, and provide a convergence rate guarantee. The algorithm is defined by (1) with the stochastic step size 2, being binary random variable that takes value Tt := C(x,, Yt. 0,)/ (x+, St. 0z) with probability (I2, Yr. 0z) and takes value 0 otherwise, where π some sampling probability function. Here, ((x, y, 0) the expected SGD (1) step size, defined as
C(x, 0) = B min
(1t, y, 0)
whenever |/oe((, y, 0)1l > 0 and [(x, y, 0) = otherwise, for constants 3, > 0, where
Vol(Lz 0)1
(1a y. 0) 8 y, 0) infor E(x,, y, 0')
The expected step size [(z, y, 0) corresponds to the stochastic Polyak's step size used by gradient descent algorithm proposed by [Loizou et al., 2021], which is accommodated as a special case when (अx, y, 0) 1 for all v, y, O. AWS introduces sampling component and re-weighting of the update to ensure that the step size remains according to the stochastic Polyak's 's step size in expectation. For many loss functions, info {(,, y, 0) 0, for every 2., y. In these cases, v0x,,, y. 0) |[Vol(z, y, /)]l2//(x. y. 0). For instance, for binary cross-entre cross-yntropy loss function, infg l(x, y. 0) = inf (- (a (yx ('))) = 0, for all x, y.
We next show a convergence rate guarantee for AWS.
Theorem 3.6. Assume that E a convex, L-smooth function, there exists A such that (xf(x, y. 0* 01 Elinfo ((., y, 0)] I A*, and the sampling probability function is such that, for some constant c. E (0, 1), for all v. y, such that ([V y, 8)11 > O.
7. ( y. 0) 2 2(1 c) min (or y, 13.
(6)
7

---

Then, we have
1
n (f(xee yt, 0c) E( yes 07))
pB ch
_
E
110
0- 0'112 n
n
2CR
where 6 = 3 min (1/L), p} and o7 is a minimizer of (1 yr, 8y) over 0'
1 The bound on the expected average loss in Theorem 3.6 boils down to A* /c (L)() 01 - by taking p = 1/(2)). Notably, under the condition on the sampling probability in Theorem 3.6 the convergence rate is of order O(1/n). A similar bound is known to hold for SGD with adaptive stochastic Polyak step size for the finite-sum problem, as seen in Theorem 3,4 of Loizou et al. [2021]
A difference is that Theorem 3.6 allows for sampling of the points.
Loss and seccertaintybaseee Sampling for Linear Binary Classifiers We consider linear binary classifiers, focusing particularly on logistic regression and the binary cross-entropy training loss function. The following corollaries of Theorem hold for sampling proportional to absolute error loss and uncertainty-basee based sampling probability function, respectively.
Corollary 3.7. For sampling proportional to absolute error loss, π Tu)) = w(1 ou)), with 3/(4(1 L) S w S and p = 1/(LL), the bound on the expected loss in Theorem 3.6 holds.
Corollary 3.8. For the uncertainty-bused sampling according
B
1
r(u)= = 2(1 c)
min pR² H(a) + aa]lu
where a E 10,1/2 and H(a) log(1/a) + (1 - a) log(1/(1 a))), the bound the expected
loss in Theorem 3.6 holds.
Other Cases For a constant sampling probability function with value of at least x<(2(1 - c)), condition (6) holds when x < c). When (Ix, y, 0) = ((z, y, 0)", where r) >> 0 and p3 E (0, 1.
condition o holds under 3 < 2(1 c)(1(22))) as shown in Appendix AA.4, Condition 6
also holds for an uncertainty-based sampling in multi-class classification, as shown in Appendix A.
Numerical Results
In this section evaluate AWS algorithm, defined in Section 3.2 In particular, we focus instance of AWS with stochastic Polyak's s expected step size for logistic regression and the loss-based sampling proportional absolute error loss, which refer to -eepttive-Weighh Sampling Polyak Absloss (AWS-PA). By, Corollary 3.7 AWS-PA converges according to Theorem 3.6 Here we demonstrate convergence real-world datasets and compare with other algorithms.
The implementation of AWS-PA -PA algorithm along with all the other code run the experimental setup that is described in this section is available at hittps://wwt gi thtt........ wttp///acebooooeeeeerr...oo SdaptivveWeighttSmmplll
We use modified version of the mushroom binary classification dataset [Chang and Lin 2011
that was used Loizou et al. (20TT) for evaluation of their algorithm. This modification uses RBF kernel features, resulting in a linearly separable dataset for a linear classifier like logistic regression. Furthermore, we include five datasets that we selected at random from the real-world datasets that were used in Yang and Loog [2018). benchmark study of active learning for logistic regression:
MNIST ys 5 LeCun et al. 1998), parkinsons Little et al. [200]]. splice Noordewier et al. [1990], tictactoe Aha [1991]. and credit Quinlan 1987]. While these datasets are not necessarily lincarly separable, Yang and Loog 2018 has shown that logistic regression achieves a good quality-of-fi
In our evaluation, we deliberately confine the training to single epoch. Throughout this epoch, we sequentially process each data instance, compute the loss for each individual instance, and subsequently update the model's weights. This approach, known as progressive validation [Blum) jet al. 1999], enables us to monitor the evolution of the average loss. The constraint to a single epoch ensures that we calculate losses only for instances that haven't 't influenced model weights. For each sampling scheme, we conduct a
sweep to minimize the average progressive loss and apply a procedure to ensure that all algorithms sample comparable numbers of instances.
8

---

0.6
cro lave
a8pioss
evergee
polysk plslooss
polyak random
palyai_absless
polyak random
0.5
1000
2000
3000
4000
5000
60/00
2000
4000
6000
8000
10000
Steration
iteration
(a) Mushrooms dataset
(b) MNIST binary classification of 3s vs 58
0,700
avorgee loxe
0.7-
random
0.575
10.6
polyak, aboloss payaaka
0.625
0.4
potyok 3b:1005
0.500
polyakt randor
40
300
200
400
600
8000
1000
Ror Reration
ileraiin
(c) Parkinsons dataset
(d) Splice datasct
orai-unbbpy loss
0.75
random
absloss
crose-e Desein Ivee
random
a
polyat_absils
average
0.70
polysk_randon
polyaki
0.5
0.4
Neration
(c) Tictactoe dataset
(f) Credit dataset
Figure 1: Convergence in terms of average cross-entropy progressive loss of random sampling, loss- based sampling based the absolute error loss, and our proposed algorithm (loss-based sampling with stochastic Polyak's 's step size). Our proposed algorithm outperforms the baselines in most cases.
In Appendix B.I
include further details this procedure, the hyper- paree--arreeter tuning, and other aspects of the experimental setup.
Figure T demonstrates that AWS-PA leads to faster convergence than the traditional loss-based sampling with a constant step size (akin to Yoo and Kweon [2019]). It also shows that the traditional loss-based sampling approach converges more rapidly than random sampling datasets. These results are obtained under hyper-parameter tuning such that different algorithms have comparable data sampling rates. We provide additional experimental results that demonstrate the efficiency of AWS-PA in Appendix B.2
five of the six
In active learning applications, the true loss of a point cannot be computed before the corresponding label is obtained. Hence, in practice we not know the true loss at the moment of making sampling decision. Therefore, we assess the effect of using a loss estimator, instead of using the true loss values. We use a Random Forest regressor to estimate absolute error loss based on the same set of features the target model and the target's model prediction as an extra feature. We retrain this estimator on every sampling step using the labeled points observed so far.
Figure 2 demonstrates that AWS-PA with the estimated absolute error losses performs similarly on all datasets to AWS-PA with the true absolute error losses. Moreover, for majority of the datasets, the two variants of AWS-PA achieve similar data sampling rates; this is shown Appendix B.3 along with further discussion.
Conclusion
We have provided convergence rate guarantees for loss and uncertainty-basee active learning algo- rithms under various assumptions. Furthermore, we introduced the novel Adaptive- Weight Sampling (AWS) algorithm that combines sampling with an adaptive size, conforming to stochastic Polyak's step size expectation, and demonstrated its convergence rate guarantee, contingent on a condition related to the sampling probability function.

---

pelyak abddss
everage cres--entii loss
palyet absiisssssssss..s estimetoo
love
potyak ccooscttotossccmmmao
1.00
0.25
1000
2000
3000
4000
5000
60/00
6000
10000
Eleration
ieeratiin
(a) Mushrooms dataset
(b) MNIST binary classification of 3s vs 58
0.68
average
0.66
0.5
0.64
0.62
200
400
800
1000
1200
Parkinsons dataset
(d) Splice dataset
0.72
1084
0.70
0.8
average
0.66
0.6
cross
0.64
100
200
300
400
500
600
700
100
200
300
400
500
Reration
iteration
(e) Tictactoe dataset
(l) Credit dataset
Figure 2: Active learning sampling based on an estimator of the absolute error loss performs on par with the sampling based on the ground truth value of absolute error loss.
For future research, it would be interesting to establish tight convergence rates for the training loss function and the sampling cost, especially comparing policies using sampling with a constant probability with those using adaptive boss-based sampling probabilities. would be interesting to explore adaptive-weizg paper. Additionally, exploring a theoretical study on the impact of bias and noise in the loss estimator, used for evaluating the sampling probability function, the convergence properties of algorithms could open up a valuable avenue for investigation.
sampling algorithms with adaptive sizes different than those studied in this
10

---

References
Alekh Agarwal. Selective sampling algorithms for cost-sensitive multiclass prediction. In Sanjoy Dasgupta and David McAllester, editors, Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 1220-1228, Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR.
David Aha.
Tic-Tac- Toe Endgame.
UCI Machine Learning Repository, 1991. DOI:
James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for hyper-parameice optimization. Advances in Neural Information Prucessing Systems, 24, 2011.
James Bergstra, Daniel Yamins, and David Cox. Making science of model search: Hyperparameter optimization in hundreds of dimensions for vision architectures. In Proceedings of the 30th International Conference Machine Learning, pages 115-123. PMLR, 2013.
Avrim Blum, Adam Kalai, and John Langford. Beating the hold-out: Bounds for k-fold and progressive cross-validation. In Proceedings of the Twelfth Annual Conference on Compulational Learning Theory (COLT), pages 203-208, 1999.
Sébastien Bubeck. Convex optimization: Algorithms and complexity. Found. Trends Mach. Learn., (3-4):231-357, nov 2015.
Giovanni Cavallanti, Nicolò Cesa-Bianchi, and Claudio Gentile. Learning noisy linear classifiers via adaptive and selective sampling. Machine Learning, 83(1):71-102, 2011.
Nicoló Resa-Bianchh, Claudio Gentile, and Luca Zaniboni. Worst-case analysis of selective sampling for linear classification. Journal of Machine Learning Research, 1(44):1205-1230, 2006.
Nicolò Sesa-Bianchi, Claudio Gentile, and Francesco Orabona. Robust bounds for classification via selective sampling. In Proceedings of the 26th Annual International Conference Machine Learning, ICML '09, page 121-128, New York, NY, USA, 2009. Association for Computing Machinery.
Chih-Chung Chang and Chih-Jen Lin. Libsvm: a library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 223 2011.
Cody Coleman, Christopher Yeh, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailis, Percy Liang, Jure Leskovec, and Matei Zaharia. Selection via proxy: Efficient data selection for deep learning. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
Koby Crammer and Yoram Singer. On the algorithmic implementation of multiclass kernel-based vector machines. Mach. Leurn. Res., 2:265-292, mar 2002. ISSN 1532-4435.
Sanjoy Dasgupta, Adam Tauman Kalai, and Claire Monteleoni. Analysis of perceptron-based active learning. Journal of Machine Learning Research, 10(11):281-22) 2009.
Ofer Dekel, Claudio Gentile, and Karthik Sridharan. Selective sampling and active learning from single and multiple teachers. J. Mach. Learn. Res., 13(1):2655-2677, sep 2012. ISSN 1532-4435.
Yoav Freund, H. Sebastian Seung, Eli Shamir, and Naftali Tishby. Selective sampling using the query by committee algorithm. Machine Learning, 133-1113 1997.
Ran bachraba Amir Navot, and Naftali Tishby. Query by committee made real. Y. Weiss, B. Schölkopf. and J. Platt, editors, Advances in Neural Information Processing Systems, volume 18. MIT Press, 2005.
Andreas Kirsch and Yarin Gal. Unifying approaches in active learning and active sampling via fisher information and cntommtiion-thorcee quanties. Transactions on Machine Learning Research, 2022.

---

Andreas Kirsch, Joost van Amersfoort, and Yarin Gal. Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Salem Lahlou, Moksh Jain, Hadi Nekoei, Victor Butoi, Paul Bertin, Jarrid Rector-Brooks, Maksym Korablyov, and Yoshua Bengio. Deup: Direct epistemic uncertainty prediction. Transactions on Machine Learning Research, 2022.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-23 -2224, 1998.
David D. Lewis and William A. Gale. A sequential algorithm for training text classifiers. In Bruce W. Croft and C. van Rijsbergen, editors, SIGIR '94, pages 3-12, London, I 1994. Springer London.
Max Little, Patrick Mesharry, Stephen Roberts, Declan Costello, and Irene Moroz. Exploiting nonlinear recurrence and fractal scaling properties for voice disorder detection. Nature Precedings, pages 1-1, 2007.
Shang Liu and Xiaocheng Li. Understanding uncertainty sampling, 2023. URL https://arxiv axg/abs/2800 0
Nicolas Loizou, Sharan Vaswani, Issam Hadj Laradji, and Simon Lacoste-Julien. Stochastic Polyak step-size for SGD: An adaptive learning rate for fast convergence. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 1306-1314, PMLR, 13-15 Apr 2021.
Edwin Lughofer and Mahardhika Pratama. Online active learning in data stream regression using uncertainty sampling based on evolving generalized fuzzy models. IEEE Transactions on Fuzzy Systems, 2621)666922222220 209, 2018.
Jian Luo, Jianzong Wang, Ning Cheng, and Jing Xiao. Loss prediction: End-to-end active learning approach for speech recognition. In 2021 International Joint Conference on Neural Networks (LJCNN), pages 1-7. IEEE, 2021.
Sören Mindermann, Jan M Braumer, Muhammed T Razzak, Mrinank Sharma, Andreas Kirsch, Winnie Xu, Benedikt Höltgen, Aidan N Gomez, Adrien Morisot, Sebastian Farquhar, et al. Prioritized training on points that are learnable, worth learning, and not yet learnt. International Conference Machine Learning, pages 1 15630-15649. PMLR, 2022.
Stephen Mussmann and Percy S Liang. Uncertainty sampling is preconditioned stochastic gradient descent on zero-one loss. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
Yuri Nesterov. Lectures Convex Optimization. Springer, 2018.
Minh-Tien Nguyen, Guido Zuccon, Gianluca Demartini, et al. Loss-based active learning for named entity recognition. In 2021 International Joint Conference on Neural Networks (IJCNN,, pages
1-8. IEEE, 2021.
Vu-Linh Nguyen, Mohammad Hossein Shaker, and Eyke Hüllermeier. How to measure uncertainty in uncertainty sampling for active learning. Machine Learning, 111(1):89-122, 2022.
Michiel Noordewier, Geoffrey Towell, and Jude Shavlik. Training Enowledge-based neural networks to recognize genes in dna sequences. Advances in neural information processing systems, 3, 1990.
Francesco Orabona and Nicolò Cesa-Bianchi. Better algorithms for selective sampling. In Pro- ceedings of the 28th International Conference on International Conference on Machine Learning, ICML' 11, page 433-440, Madison, WI, USA, 2011. Omnipress. ISBN 978 15530066195
12

---

Mansheej Paul, Surya Ganguli, and Gintare Karolina Dziugaite. Deep learning on data diet: Finding important examples early in training. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 20596-20607.
Curran Associates, Inc., 2021.
J. Ross Quinlan. Simplifying decision trees. International journal of man-machine studies, 27(3): 221 221-234, 1987.
Anant Raj and Francis Bach. Convergence of uncertainty sampling for active learning. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Pro- ceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 18310-18331. PMLR, 17-23 Jul 2022.
Jason Rennie. Smooth hinge classification, 2005. URL http://quone http:////ooeecoo/./a// wason/wwitte smoothHinge. pdf
Jason Rennie and Nathan Srebro. Loss functions for preference levels: Regression with discrete ordered labels. Proceedings of the IJCAI Multidisciplinary Workshop on Advances Preference Handling, 01 2005.
Rosenblatt. he perceptron: a probabilistic model for information storage and organization in the brain. Psychological review, (566):3864408 1958.
Nicholas Roy and Andrew McCallum. Toward optimal active learning through sampling estimation of error reduction. In Proceedings of the Eighteenth International Conference on Machine Learning. page 441 448, San Francisco, CA, USA, 2001. Morgan Kaufmann Publishers Inc.
Greg Schohn and David Cohn. Less is more: Active learning with support vector machines. In Proceedings of the Seventeenth International Conference on Machine Learning, ICML '00, page 839 846, San Francisco, CA, USA, 2000. Morgan Kaufmann Publishers Inc.
Burr Settles. Active learning: Synthesis lectures on artificial intelligence and machine learning. Springer Cham, 2012.
Burr Settles, Mark Craven, and Soumya Ray. Multiple-instanee active learning- In J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2007.
H. S. Seung, M. Opper, and H. Sompolinsky. Query by committee. COLT '92, page 287-294, New York, NY, USA, 1992. Association for Computing Machinery. ISBN 089791497X.
Jie Shen. On the power of localized perceptron for label-optimal learning of halfspaces with adversarial noise. In Marina Meila and Tong Zhang, editors, Proceedings the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 9503-9514, 18-24 Jul 2021.
Ben Sorscher, Robert Geirhos, Shashank Shekhar, Surya Ganguli, and Ari Morcos. Beyond neural scaling laws: beating power law scaling via data pruning. Advances in Neural Information Processing Systems, 35: 15:19533-19536 2022.
Mariya Toneva, Alessandro Sordoni, Remi Tachet des Combes, Adam Trischler, Yoshua Bengio, and Geoffrey J. Gordon. An empirical study of example forgetting during deep neural network learning. 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
Ran Wang, Chi-Yin Chow, and Sam Kwong. Ambiguity-based multiclass active learning. IEEE Transactions Fuzzy Systems, 24(1):242-248, 2016.
Songbai Yan and Chicheng Zhang. Revisiting perceptron: Efficient and label-optimal learning of halfspaces. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
13

---

Y. Yang and M. Loog. Active learning using uncertainty information. In Proceedings of the International Conference on Pattern Recoginition (ICPR), page 1646-2651, 2016.
Yazhou Yang and Marco Loog. benchmark and comparison of active learning for logistic regression. Puttern Recognition, 83:401-415, 2018.
Yi Yang. Zhigang Ma, Feiping Nie, Xiaojun Chang, and Alexander G. Hauptmann. Multi-class active learning by uncertainty sampling with diversity maximization. International Journal of Computer Vision, 113(2):113 127, 2015.
Donggeun Yoo and In So Kweon. Learning loss for active learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
Jingbo Zhu, Huizhen Wang. Benjamin K. Tsou, and Matthew Ma. Active learning with sampling by uncertainty and density for data annotations. IEEE Transactions on Audio, Speech, and Language Processing, 1866):1323-1331 2010.
14

---

A Appendix: Proofs, Discussion, and Additional Results
A.1 Limitations Discussion
It remains an open problem to investigate the tightness of convergence rate bounds for constant-weight sampling under the assumptions outlined in Theorem 3.3
The convergence rate results presented in Theorems 3.3 and 3.6 pertain to smooth convex training loss functions. Future research may explore weaker assumptions regarding the training loss function.
Regarding loss-based sampling strategies, our theoretical analysis assumes an unbiased and noiseless loss estimator. Extending this to account for estimation bias and noise would be a valuable avenue for further investigation.
Our numerical results demonstrate the effectiveness of our proposed algorithm and the robustness of our theoretical findings to loss estimation bias and noise across different datasets, utilizing the logistic regression model binary classifier. Future work could explore the application of other classification models, such as multi-layer neural networks.
A.2
Set of Convergence Rate Conditions
We present and prove two convergence rate lemmas for algorithm ① the first providing sufficient conditions for certain convergence rate and the second restricted to linear classifiers and linearly separable datasets.
The first lemma relies on the following condition involving the loss function used by algorithm and the loss function é used for evaluating the performance of the algorithm.
Assumption A.1. There exist constants a,, B 0 such that for all (I,9) X x y and 0 O.
л(x, y. 0) V Vol(x, y. 0)12 < al(x, v.
and
x (I. (0 0*) z 3f(2,
(8)
Lemma A.2. Under Assumption A.1 for any On and (0r)e>1 according to algorithm 7 B/a,
with
Σ E(re vr, 0.)
1 01 a
E
32
Moreover. for every (x, X x V, E(x, y. O is convex function in 6, then have
ElL(K, y, 0w)l s 110 - 0-113 a 1
32
where 0n = (1/n)E==1 Or.
Proof.
For any 0r E θ and t 2 1, we have
||0+1 1 ||0 1²1 - 22, Vol(x,, ye, T,) 0*) 21 Vol(ze, Vı, 0.11
Taking expectation in both sides of the equation, conditional on at, 3 and Gr, we have
B[]10++1 1- 2it Me, 0.]
100 0- 2,, 0.) V ye, 0,) (0. 0²) + ye. Vol vr 0.)1|
Under Assumption A.1
we have
0.+1 0-112 Øe. Me. 0c] S 110 8-112 2y Ve, 0₂) 72 Pal(xe Hc, v1, 01)
Hence, it holds
(2, 2a))E(((( Uo, 0,)
Ell 0-113) B1110 12)
15

---

Summing over t, we have
(2 - -2
Ell(xr. ye, 00] - ||0 1-112.
By taking = 3/a, we have
B((( Mr, 0c) s 110 - 0-11 32
The second statement of the lemma follows from the last above inequality and Jensen's inequality. D
For the case of linear classifiers and linearly separable datasets, it can be readily checked that Lemma [.2 implies the following lemma.
Lemma A.3. Assume that there exist constants az, 3 > such that for all u RR
(u)) s al(u)
(9)
and
T(u) (())(- u) 2 Bê(u).
(10)
Then, for any 02 such that 1|0 0- S and {0e hes1 according to algorithm 7 with 7 8/a.
Σ Eyy 0e)
S S2 $2
Moreover, if is convex convex function, then E [lyx ((y)
8n)
S 522a/$32 where On = (1/n) Ei=1 O,
A.2.1 Discussion
We discuss some implications of conditions (9) and 10 Some of this discussion will help us identify the types of loss functions to which the conditions cannot be applied.
First, we note that É(u) > 0 implies π (u) > 0. Hence, equivalently, rru) implies ē(u) = 0.
Second, note that under conditions ( and I0 is necessary that for all R, either
3R max 0) or (u)) 0. - f'(u)= I
Hence, whenever ē(u) > (and thus Tuu) > 0). then -f((u) S DR max(p" - u, 0}. The latter condition means that (1) = O whenever u 2 p" and otherwise the derivative of l at is bounded such that f' (u) 2 (a/(RR))) p-oo,p").
u). In other words, function must not decrease too fast on
Third, assume é and i are such that E(u) = 0 and É(u) = 0 for all u 2 1 and E(u) > 0 for all < 1.
Then, for every u < 1
J. (-(()))do S
BK J. (0- - u)de
a
which by integrating is equivalent to
f(u) 3R
(0- 1) - u) n)²)
This shows that must be upper bounded by a linear combination hinge and squared hinge loss function.
Forth, assume that is decreasing in u. then for every fixed uo IR,
ē(uu N a
(-((())) for every $ Ug.
16

---

If é = L, then
E(u)= 1
(V(uo)
2R r(u)) (wo -
1
-w) for all ugg
Fifth, and last, assume that is even function and that there exists >> 0 and uo p² such that E(u) 2 for every u I uo. Then,
1
(u)) Ω
eu/2
which limits the rate which ru) allowed decrease with u/. To see, this, from conditions (9) and (00. for every u S p=,
E(u) S 82 (p))pp" - u)²
Hence, (u) 2 (c3/ - -)) for every u S uo. The lower bound is tight in case when / is squared hinge loss function and f(m) = c for every no < 1. In this case, from conditions and (10p, for every u S uo.
1
cB (1 u)(p u) (T(u)=
R² (1 u)²
which implies ruu) = O
A.3 Proof of Theorem
We show that conditions of the theorem imply conditions ( and 10 to hold, for E L, which in turn imply conditions and ( and hence we can apply the convergence result of Lemma A.3
We first consider condition For squared hinge loss function é and f, clearly condition holds for every u 2 as in this case both side of the inequality are equal to zero. For every u <
{(u) (u)
2
Since by assumption TTu)= S 3/2 for all condition a/B 2 R2 implies condition 7
We next consider condition (8) Again, clearly, condition holds for every 2 as in this case both sides of the inequality are equal to zero. For u S 1, we can write (8) as follows
{(u)
8 u 2 u
Tuu)= 2 8 (- u)
8
2
1+ (1/(0' - 1))(( u)
8
2
1+ -()
This condition is implied by πu))= 2 x² (e(u)) where
" (e)
1
1 + vVE
with a 2 (2/(p-11 1).
The result of the theorem follows from Lemma for all u <
A.3 with a/3 RR and x()) 2 (E(())
For the expected number of samples we proceed as follows. First by concavity and monotonicity of function म and the expected loss bound, we have
Σ (x Me, V., 0.) n n ~- -110 -110--0111R8 11
n (f(xre, yr, 0.))
5 E
n.
Bn
17

---

Then, combined with the fact π TT( I Bu V for all 2 0, it follows
1100 -0 MVB
I
(llas, 0i))
2 Vn.
Since (v) 8/2 for all v, it obviously holds E EE>> क (f(1s, Be, 0,)) < (8/2)n, which com- pletes the proof of the theorem.
A.4 Linear Classifiers: Zero-one Loss and Absolute Error Loss-based Sampling
Here consider training loss functions satisfying: Assumption A.4. Function È is continuously differentiable on (-20, 0J, convex, and (0) - -1 and - (u) 2 for some constants C1 C2 > O.
We consider sampling proportional to either zero-one loss or absolute error loss. The zero-one loss defined as (u) == 1 [m50} (uzegu(== T0)- The absolute error loss is defined as fabs (u) := 2 (1 (u<0} + 1 (m=0)) = ly sgn(æ 0)]- Sampling proportional to zero-one loss is defined as T (u)) = who (u) for some constant w E (0, 1], while sampling proportional to absolute error loss is defined as т (u) wlabs(u) (u) for some constant w E (0, 1/2].
Theorem A.5. Assume that the loss function & satisfies Assumption 4.4 and p² > 0. Then, under sampling proportional to zero-one loss, for any initial value 0₂ such that 08 A* || S S and {0:]t2 }t>1
according to algorithm ( with y = c1p" ((2
En T 0.))
S²
E
Σ
(11)
G2w p²2
Furthermore, under sampling proportional to absolute error loss and q 201p" /(2R) the bound (TT) holds but with an additional factor 2f
Proof is provided in Appendix A.4.1
The bound in (11) well-known bound the number of mistakes made by the perceptron algorithm, of the order O(1/p²)). It can be readily observed that under sampling proportional to zero-one loss, the expected number of sampled points is bounded by (22/c1)² R /p²² which also holds for sampling proportional to absolute error loss but with an additional factor of 4.
A.4.1 Proof of Theorem A.5
We first consider the when sampling is proportional zero-one loss. We show that conditions of the theorem imply conditions (9) and (10) to hold, for / = ln and whor, which in turn imply conditions 7 and ( and hence we can apply the convergence result of Lemma A.3
Conditions and 10 are equivalent to:
we (l) < a, for every u I 0
and
w(- w(-E(u))(p - u) 2 3 for every S 0.
Since a convex function (2) is decreasing in u and (-I'(u))(p- - u) is decreasing in u. Therefore, conditions equivalent to
w lim (-E <a
and
w(-( ス 3.
These conditions hold true by taking wc Rd and A woip"
We next consider the case when sampling is proportional to absolute error loss. We show that conditions of the theorem imply conditions 9 and 10) to hold, for ? = far and क wlatss which in turn imply conditions and and hence we can apply the convergence result of Lemma A.3
18

---

Conditions 9 and 1T0
correspond to
2w( (u(-=(u))) & a for every u < 0 and w( w(- a
and
20 2w - u) 2 3 for every < 0 and w (0)) 2 B.
Again, since (=)) is decreasing in u and (-f(u))(pp - u) decreasing in u, it follows that the conditions equivalent to
2wl lim (-f( a 4--00
and
w( (-)( 2 3.
Hence, conditions 9 and (10) hold by taking a 2we It2 and B welp".
A.5 Linear Classifiers: Generalized Smooth Hinge Loss Function
Here we consider the training loss function corresponding to the generalized smooth hinge loss function [Rennie 2005], defined for as follows:
a+1 u
if 1 0
((u) =
1 +
if 4 otherwise.
(12)
This is continuously differentiable function that converges the value of the hinge loss function, max (1 u. 0), as a goes to infinity. The family of loss functions parameterized by a accommodates the smooth hinge loss function with
introduced by Rennie and Srebro 2005
Theorem A.6. Assume that p² 1, the loss function is the generulized smooth hinge loss function, and the sampling probability is according to the function nt, which, for 3 E (0, 1] and E (1, p"), is defined as
3
if 1u.0
x (u)
3
10 u 1
P-
ifu 2.
Then, for any initial value 0, such that |10, 80 S S and (0r hest according algorithm 7 with 1/(ca. where ca.p = a/(a(p 1) + 1), we have
R² S2
[lye [mm] s E
Σ ( 0²) I Cu.p
B
Furthermore, the same bound holds for every v such that ग T'()) S T()) S for all R, with
Ca.p 2o.
Proof provided in Appendix A.5.I
Note that x² is increasing in and is upper-bounded by x x" (u) 3(1 -(1-w) 8(1-w)(pp 1), which may be regarded as the limit for the hinge loss function. See Figure for an illustration.
We remark that the expected loss bound in Theorem A.6 is the same as for the squared hinge loss function Theorem 3.1 except for an additional factor Ca,p = a/(a(p 1) + 1). This factor is increasing in a but always lies in the interval [1/p, ( 1)], where the boundary values are achieved for I and + oc, respectively.
Theorem A.7. Assuming p¹ 1, the loss function is the generalized smooth hinge loss, and the sampling probability function πt" satisfies the assumptions in Theorem A.6 with n > ((a
1)/a)Ca,p R2 5²2 (3, the expected number of sampled points is bounded
/BCappR RS Vn, (p-
R222
E
Σ
(wer, 0.))
max
p
where K. is some positive constant.
19

---

0.8
0.4
1=1
0.2
Finge
0.0
-1.9
-0.5
0.5
3.0
Figure Sampling probability function for the family of generalized smooth hinge loss functions.
Proof provided in Appendix A.5.2
For any fixed number of iterations n satisfying the condition of the theorem, the expected number of sampled points is bounded by constant for sufficiently large value of parameter The bound in Theorem A.7 depends on how the loss function {(u) varies with u. When a is large, {(u) is approximately hinge loss).
(hinge loss), otherwise, it is approximately 5(1 - u)² for 0 S (squared
A.5.1 Proof of Theorem A.6
Assume that π² is such that for given p E (1. Then, x² satisfies equation (10) for all E. Note that
u) = BE(u) for all R.
B
a
if
t(u)
p-u u
x (u) B (- - u)
3
u (1 w)
_t p-u
if S S
a+1
if 1.
By condition
we must have
(u) < a
p
BR
Note that
if <
(())
(1 - u²)
if S u S
otherwise.
Hence, for every S 0, it must hold
1
<
0
3R2
which is equivalent to a/B < nP/ For every 0 S u S must hold
fa(u) 1- a
< BR
p - u
Thus, it must hold a/3 2 Ca. R² where Co.p = sup 1] fa)..
Function fa has boundary values f0) = 1/p and (1) = 0. Furthermore, note
(2( + (a - 1)u pau"-1
(p u)²
Note fa( = 1/p² and [1( = -pp - 1)a < Let u. such that (u.) 0. which holds if. and only if, ga (u.) (a 1)u," pau, a-1
0.
20

---

Note that
sup fa(u) fo (u.) au uE(0.1]
Ca.p
For = 1, fi is decreasing on [0, hence C1,p - f( = 1/p. For a 2, u, is a solution of
quadratic equation, and can be readily shown that c,,p 2p(1 vp2 1). For every 2 have Ca.p Σ a/(1 + a(p - 1)). This obviously holds with equality for a = 1, hence it suffices to show that the inequality holds for
Consider the case a > 1. Note that go (u.) = 0 is equivalent to
au
(13)
P
Combined with the fact ux [0, 1]. it immediately follows
a
au S
a - 1)
Note that u. goes to as goes to infinity. This can be shown by contradiction follows, Assume that there exists constant c E [0, 1) and (n such that u. I c for all a 2 ag- Then, from 13). ac > 1/p" The left-hand side in the last inequality goes to
Furthermore, note that limg-+xo Ca.p = 11/pp111111 1). To see this, consider 13)
goes to infinity while the right-hand side is constant greater
than zero, which yields a contradiction. From (13 follows that au a-1 goes to 1 1/(p - 1) as a goes infinity.
We prove the second statement the theorem as follows. It suffices to show that condition holds true condition (10) clearly holds for every such that (u) 2 n² (u) for every u E R. For condition (9) to hold, is sufficient that
{(u)
3R for all u S
f(u) = (u)) a
Note that
if 0
f(u) = a+1
(a+1)uta
if 5
a+I
w1-w-y
Function f decreasing function. This is obviously for 0. For 0 S show this as follows. Note that
2an (2a- 1) + 1)u + 2n (a +
f'(2)
(a 1)(1 wa)3
Hence, ('(x) S is equivalent to
2au*~1 2a + a) S (a + 1)(1 (2a - 1)n²).
In the last inequality, the left-hand side is increasing in and the right-hand side decreasing in Hence the inequality holds for every u E [0, 1] is equivalent to the inequality holding for 1. For 1, the inequality holds with equality.
Note that
0
1(1)
(a+ 1)u - (a 1)
0
-2(1 40 "ayaa u=1
c+1
(a 1)a
1 (a 1)a
a 2 2(1 - ua )a(a - 1) 11=1
+ 1 2a²
2a
It follows that inf,si f(u) f(L) 2u < a/(3R²), hence is suffices that a/B 2 R² /2/())).
21

---

A.5.2 Proof of Theorem A.7
Lemma A.8. For every a 2 1,
x x'()) S n (1) = =B - for every u S 1.
u
Proof. For u S 1, (u)
u). so obviously, =") - 3 u)/(p - u). For 0 S < 1, we show that next that a(1 - u1 =²) u S a - u). which implies that ("(u)= S (a/(a + 1)) - up) - u). To show the asserted inequality, by straightforward calculus it can be shown that the inequality is equivalent to (1 - (1 -=))= -))²- 2 1 - (1 a)(1 u) which clearly holds true.
1)
Lemma A.9. For every e E (1,6/5), for every S u S 1, if (a + 1)(1 - w) 2 c, then
E(u)= 2
1
1
1
(1 - u)
c
and, otherwise,
E(u)= 2 1
1 c
2 (1 u)²
a
3
c/2
Proof. We first show the first inequality. For 1, it clearly holds E(u) u, and
u 1
1
a+1 1-10
at1
(a + 1)(1 u) thus, for every c > 1, l(u)= (1 1/c)(1 u) whenever (a + 1)(1 u) 2 c. For S 1, holds ((u) 1 u - (1/(a (1) - ,( ) hence it clearly holds E(u) S 1 u.
Next, note
f(u) = 1 1 1-
21 1 (a+ u)
(a + 1)(1 - u)
Hence, again, for every e > 1, (()) 2 (1 - 110)(1 u) whenever (a + 1)(1 - u) 2
We next show the second inequality. For 0 < < 1, note that ('()) -(1 10---1 u²), (u) au=
and (u) = a(a- - 1)ua-² In particular, (1(1) = 0, (1) = a and (1) = a(a - 1). By limited Taylor development, for some un E [u, 1].
a(a - 1) ug 21 n))
((u) (1 u)²
6
From this, it immediately follows that {(u)= S (1 u)? for every u S 1. For the case a 2 2, we have
1 (a 1)(1- 11)
((u) 2 2 (1 u)² 1
Hence, for every c 2 0, E(u) 2 (1 - =1) - c/3) whenever (a + 1)(1 - u) c. For 1 sasa 2, we have
((u) 2 (1 - u)²
(a
1)(1 u)
2 2
a (1 - w)²
1 (a- 1) u)
2
3 22
3
u
Under (a + 1)(1 - u) < c, with 0 < c < 2, we have
(a 1)(1
a+I
Hence, it follows
((u) 2 0 (1 - u) (1 (1
c
2
31 -
22

---

Next, note that for every 2, y. 8
B
T'x 0) - n "yx (yzT)) 0) 8r p--1 (1- yz 0)
(1 L "((x,, y. 0)))
0
where {-1 is the inverse function of ((u) for < 1 and (0) 0.
Hence, we have
1))
(yra 0z)
1 - f-1
E (x yt, 0a)
B
100 1- R2
1 6-
ca.p
where the first inequality is by concavity of the function 1- - l- (() and the second inequality is by A..
To apply Lemma A.9
we need that
110
0-
e-1
Ca.p
B
which is equivalent to
101 - 8" 1|
= a < {(0)
Ca.p
3
a+ 1
i.e.
110 0²
a
n
Ca.p
a
By Lemma A.9 we can distinguish two cases when
E-
Co.p
|10:
1
2 c
B
n
a a
or, otherwise, where e is arbitrary constant in (1,6/5). In the first case,
|10
R²2
1
|00
1² 1
1- e-1-1 Ca.p
$
Ci
8
n
n
where = 1/(1-111 1/c) while in the second case
||0] 8" 12
2
|00
8+ 2 R
1 r-1
Ca.p
02
Co.p
3
n
where 02 = =1/(1 (1/3)e/11 e/2).
follows that for some constant K. > 0,
V /Bc..p 110 001|R D /
E
Σ n (Mo 01)
< kmma
Ca.p
110
0-112
(p 1)
A.6 Multi-class Classification for Linearly Separable Data
We consider multi-class classification with & 2 classes. Let y (l,...,k)
k} denote the set of
classes. For every y V, let By Rd and let 0 (0 ........T. ,TTT Radd be the parameter. For given and predicted class an element of arg max 0y.
The linear separability condition is defined follows: there exists 0* Rdd such that for some p" > 1, for every x E X' and y E V,
x y
max
x 0. pp"
y/ (e)
23

---

Let
u(a, 0) x xTo
0gy.
V'E
We consider margin loss functions which are according to decreasing function of u(æ, 0), i.c. ((,, 0) {u((2, y. 0)) and f(z, 0) = É(u(x, 0)). For example, this accomodates hinge loss function for multi-class classification [Cammme and Singer (002).
Lemma A.10. Conditions in Assumption hold provided that for every x, y and 0,
cal(u(x, v.8)
and
(( u(z, y. 0)) 2 3e(u(z, 0)).
Proof. For E X and y V, let Φ(x,)) = (61 "...))..,, v) TT where (,(x, = if i = and dz(x, u) is the d-dimensional null-vector, otherwise. Note that
u(x, y. 0) H (To(z,)) 1 0)
E W'E (a.00)
o oT((z.²))
(14)
where
(z,,0,00) = arg
max 0y y V'EY" (x.v.0)
Note that
[Voe(2, (u(( y, y. 0)) Volee,
From 14
Vou(z, y, 0) ((x,1) [y*(,,,, (x,.))
Σ (x,
It can be readily shown that
[[ v, 0)12 (1+ (xr y, 0/ ||-|| S 211==113
Hence, we have
Vol(z, y, 0)1 < 2( E'
(15)
Next, note that Vol(I,
0) 0), = =)
T Vol(z,y. - 8r) = (-1((u(xx y, 0)) Vou(z, 0) (0" 0).
and
V () Tg = =xTor 0 max TT B 2 p¹:
v'Ei(())
follows
Vol(x, y, 0, (0 (0-))------0000000000))))1))-( 2
(u(x, y. 0)) u(x, y, 0))
(16)
Using 15) and (6). for conditions 7 and 8 to hold, it suffices that
πΦx y, 0) ()- (u(x, (u( < ae(u(x,
and
(x, y, (-E (u(2, 0)) u(x, y. 0)) > (i(u(x v,
Note that these conditions are equivalent to those for the binary case and (T)) except for an additional factor 2 in the first of the last above inequalities.
D

---

LS 1 A.7 Proof of Lemma 3.2
Function II a convex function because, by assumption, i an increasing function. By and Jensen's 's inequality, we have
1
E
{(Ot)
E
[((((,,,
72
n
fare, 0e) )
IT
E
(x yos 0t))
IE
71
X2
)
IT
TF
<(Ot))
Therefore, we have
# )
1 Σ 20.0))
(()))
<II-1
E
m
n
Combined with condition
S
we have
n
inf ((0) + m
E
e(O.)
$ IT-1
fi(n)
71
inf -I
Σ II (fi(n))
where the last inequality holds because 11 is a concave function, and hence, it is subadditive function.
A.8 Proof of Theorem
Under assumptions of the theorem, by Theorem 6.3 Bubeck 2015
n
inf E(0) v25o, 1
E
((Om))
E
E(O.)
Vn
n
n
Combining with Lemma
3.2 we obtain the assertion of the theorem.
A.9
Proof of Corollary 3.4
Lemma A.11. For Il(x) -- 1
II (v) < 2 E (0, (3/4)3).
Proof. We consider
II(x) x (1 7).
By limited Taylor development,
1
1- <
1
x
2
Hence,
1 I1(x)
1
2 7
x²
3d
25

---

Note that (x)) 2 cx2 for some constant c >> 0 provided that
1
1 3
5 r
1
cr²
2
which is equivalent to S 3(1 - 2c). Hence, for any fixed E [0, 1/2), we have
IT 2 cx², for every [0,3(1 2c)]-
Now, condition 33(1-22 2c) implied by vIl(z//c & 3(1- 2e). i.c. I1(x)= s 19(1-2c)= Hence,
I (v) v -uv for y [0,9c(1 2c)
In particular, by taking = 1/4, we have
II (v) s for for y E (3/4)
We have the bound in Theorem
3.3 Under V250 VT (3/4)², we have
11-1
V250
1
S 20/11 V SS
vn
Vn
Under LS²/n S (3/4)?, we have
rT-1
< 2V 2VTSS
vn.
This completes the proof of the corollary.
A.10 Proof of Theorem 3.6
To simplify notation, we write (0) = E(x,, ye, 0) 7x,,, Vc. 01) and ne = π (xt; Ve. 0z).
Since is L-smooth function, have f(x, y, f) infø- l(x, y, 8*) 2
0)12
Hence, for any x. y, such that //V y. 0)] > 0, we have
((x, y. 0) - ming f(x, y, 0')
2 2L
(17)
| v. 0)12
Combined with the definition of ( and the fact (( Vt. 0₂) = Te we have
K = 3 min 22 S TT whenever
Vol(r,y, 0.
(18)
From the definition of ( and the fact ((Fe, Vc. 02) = YoTe, we have Te S p3.
(19)
Next, note
Bi|10++1 - 11 2t, Ve, 0.]
|00 1- - 2E 2, Iez Dt. 0e) (o)) ((): (0,-0")
+ B[2 Ft. Ve,
= 110: 1-1 2 T (Ot) (0. 8r) + 16 T
[[V)((00))11
< 110, - 1- - 2 (E. - ((0))) + 7/ (,(0.) - (.(0,) (Ec(0t) - -e((0))
(0,)11 = 100 - 1- - 7ITE 2 22 Y1 (.(0,) - (,7)
(Ee(0)) - (((1)) + 2 - (,,))
< |00 1- (cx(er(0.) - (.(())) + 2p 2p0((e(0") (,(O)))
26

---

where the first inequality is by convexity of f, the second inequality is by condition 6 and
18 and
Hence, we have
11 0-11 S B1100 0-11²- - 2cx (B(,)())) - ex(o:)] + 2no (o)))
By summing over t from 1 to n, we have
(l((0.) - (((07)) (c(())))((00)))
p
Σ (l((0)) (((03)) +
- 110 0-11
1
E2
OK
n
2Ck
n
p
1
1
(B(e(x, y, 0*) - Elinf (1x, v. 0)1)
+
110
1-1
CR
2Ck
n
A.11 Proofs of Corollaries 3.7 and 3.8
For linear classifiers,
V Vol(z, y, 0)11 h(y T>|=a111
f(x, v.
where (u(1) ((()) which plays pivotal role in condition (6)
For the condition ( to hold it suffices that
B
(a, y. 0) Z 2(1 c) min (pRthyyx 0), 1}.
Note that under assumption that E(u) is an smoohh function in u, E(yx T ()) is an L'||=||-- function in 0. Taking p 1/(2I) with T, = L' R2 we have pff = 1/(2/').
For the binary cross-entropy loss function, we have h(u) o' ( (ooooooo)())) cally, for the logistic regression case
Specifi-
h(u)= (I + e² log( 1 e
(20)
which is increasing in for < 0 and is decreasing in otherwise. Note that h(u) (1 (=t())2//E(0) /E(uu)
A.11.1 Proof of Corollary 3.7
We first note the following lemma, whose proof is provided in Appendix A.12 Lemma A.12. Function h, defined in (20). satisfies
h((u) S
= 1 - (u) all E IR
(21)
1 1 eu
Furthermore h(u) ( for large u.
See See Figure left, for a graphical illustration.
By Lemma A. 12 condition (6) in Theorem 3.6 satisfied with = 1/(2L), by sampling proportional to absolute error loss nT" (u) w(1 o (u) with 3/(4(1 c)) w
A.11.2 Proof of Corollary 3.8
We have the following lemma, whose proof is provided in A.13
Lemma A.13. Function h, defined in 20 satisfies, for every fixed a E 10,)/2).
h(u)= < H(a) + (1 a)lu for all IR
(22)
where (aa) = a (og(1/)) + (1 a) log(1/(1 a)). Furthermore, h(()) 1//ul as u tends to -oo.
See See Figure right, for graphical illustration.
By Lemma A.13 it follows that condition O6) in Theorem 3.6 is satisfied by uncertainty sampling according to
B min RR
1
(u) 2(1 -
((a) + (1 a)|u
27

---

181 eell
bound. 12
bound. 1/
08-
0.4
05
Figure 4: Upper bounds for function h defined in (20): (left) bound of Lemma A.12 (right) bounds of Lemma A.13
A.12 Proof of Lemma A.12
We need to prove that for every R,
(1 + ee) + e
=)= ") 1 1+ c²
By dividing both sides in the last inequality with (1 e1)² and the fact 1/(1+)")= = 1-1/(1+6
we note that the last above inequality is equivalent
log(1 1 + +e= 1 1
By straightforward calculus, this be rewritten as
log 1 (1-(1-1++)) 1+e- S- (- T
1
1
This clearly holds true because 1/(1+ + -) E (0, 1) and log(1 - 2) S -z for every = E (0, 1).
It remains only to show that lim h(w)/((u///La/e((// - (lo)) = 1. This is clearly true as
h(u)
o-)(u)
(1 + e" log((1 +
which goes to as u goes to infinity.
A.13 Proof of Lemma A.13
We first consider the case S Fix arbitrary e S 0. Since log(1 + e²) is convex function is lower bounded by the tangent passing through U, i.e.
log(1 + + e) log(1 e ")
T ev v).
Now, let a be such that 1- a = 1/(1 +1 e²). Since v S 0, we have E (0, 1/2]. It follows that for any fixed a E (0, 1/2].
log(1 + c ") 2 (()) (1 a)u.
Using this along with the obvious fact (1 + eu²2 2 have that for every < 0,
h(u) < log I + =
H(a) (1 a)
We next consider the case u 2 0. It suffices to show that for every 2 0, h(u) < fi(-u) and hence the upper bound established for the previous case applies. The condition h(u)) - h(-u) equivalent to
(1 + e log(1 +e-u- I (1+e- +ea)
28

---

By straightforward calculus, this is equivalent to
f(u) = (1 log + - u 20. 0.
This holds because function (i) f is increasing on [0. uo] and decreasing on [uo, 20). for some 2 0. (ii) f(0) and (iii) aim [()) O. Properties (ii) and (iii) are easy to check. We only show that property (i) holds true. By straightforward calculus,
('()) 2*
e 22 (2 + e²) -
It suffices to show that there is unique u' E R such that f'(u") = O. For any such u² it must hold 2 log(( e")) e Let e". Then, 2 log(1 + v) which is equivalent
1+0=
Both sides of the last equation are increasing in v, and the left-hand side is larger than the right-hand side for e. 1. Since the right-hand side is larger than the left-hand side for any large enough it follows that there is a unique point u at which the sides of the equation are equal. This shows that there is unique u* 2 0 such that ('(x") O.
remains show that lim h(w))( (1)//1///l) = 1, i.e.
lim EIt (1 + e0) + t =1
which clearly holds true as both 1/(1+ + e² and u/ log(1 + t go to 1 as u goes to -o0.
A.14 Convergence Conditions for (œx y, 0) = C(x, y, 0)"
suffices to show that under given conditions, the sampling probability function satisfies condition c Using the definition of the sampling probability function, condition (6) can be written as follows
Exx, 0) info f(x, y. 0')
Vol(r, y, 0)
min 3. [(z, 0) inf E(z, y 0)
(23)
Vol(z, y, 0)1
2(1
In the inequality (23) by 17 the left-hand side is least (1/(2L))* and clearly the right-hand side
at most //-1 ( c)). Hence, it follows that it suffices that
1
"
1
2
3
2L
2(1
c)
A.15 Uncertainty-base based Sampling for Multi-class Classification
We consider multi-class classification according to prediction function
0g
p x, Eyeye o
for y )
Assume that é is the cross-entropy function. Let
u(x, v) loog
Σ WEV
It can be shown that
Vol(z,,.0)11 < || (/(((,, y, 0)) Exx, y, 0)
where function is defined in 20 Hence, condition of Theorem 3,6 holds under
π (u) 2 2(1 - c) min (2pR2 h(u),, 1}.
29

---

For given and 2, let (I)..... (a) be an ordering of 01..... Sampling according function n² of the gap x (a) x Q
0g such that x 00) 2 ... x (z)
B
min (2pRth* 2(1 -
where
h' (g) (a) (1 -1- 0) max [g log(k 1),03
satisfies condition of Theorem 3.6
We next provide proofs for assertions made above. The loss function is assumed to be the cross- entropy loss function, i.e.
e
By
A(x, v1 -log
Everyetoo
Note that we can write
(x,v.0) -- (((1,)) (o(o..)] (T log
edloaat To
We consider
Vol(z, y. 0)1
{1., y. 0)
which is plays key role in the condition of Theorem 3.6 holds
Vol(z,8,0) = 6(2,8) v) Everrius el(eD') T0 v')
Even(o e
and
(x)((())) c0(2,)) ( )
(d(
[[Vo(E,,) 0)12
||0|2
Σ
Exerron ep(O,))T ||x:
(1-0-()))0)) Σ (c=eless)))
||x/|/2
V'E
From the last equation, it follows
||:|| (1 -1e -((()x)))) S VlV 0)12 s2|0|1 (1 (1=e-()))0)) 2
Note that 0) = log(1 + e =u(2,)00)) where
-1 )
u(x, ((z, = -log
Σ
(E)
It follows
Vol(z, y, 0)12
hh( 0))
s v. 0))
((I, v,
where h is function defined in 20 The following equation holds
u(x, y, 0) = 0_
max
x To log
e-mmax TT 8--xxT ov)
=E)
30

---

Note that
rr 1rT0 0g
max x² 2T log
Σ
( x =0 000000 -x- 000) 0,y)
=Ey((y}
('E
To (1) - TTTo 0
-log(k 1).
Combining with Lemma A.13 for every a E (0, 1/2),
1
h(u(z, 5 H(a) + a)
S hh'
(()) ((1)) x (())))
where
if y - log(k: g > log(k: 1).
(g(g)) ((a)
((a) (1-a) (ogk))))-((
B Appendix: Additional Material for Numerical Experiments
B.1 Further Details on Experimental Setup
Hyperparameter Tuning We used the Tree-structured Parzen Estimator (TPE) [Bergstra et al. 2011] algorithm in the hyperopt package [Bergstra et al. 2013) to tune the relevant hyperparameters for each method and minimize the average progressive cross entropy loss. For Polyak absloss and Polyak exponent we set the search space of 1) to [0.01, 1] and the search space of p [0, 1]. Note that the values of and influence the rate of sampling.
In line with the typical goal of active learning, aim to learn efficiently and minimize loss under some desired rate of sampling. Therefore, for every configuration of 17 and p we use binary search to find the value of |3 that achieves some target empirical sampling rate.
Observe that we would not control for B, then our hyperparameter tuning setup would simply find values of ? and p that lead to very high sampling rates, which is not in line with the goal of active learning. In the hyperparameter tuning we set the target empirical sampling rate to 50%.
Compute Resources All experiments were performed on single machine with 72 CPU cores and 228 GB RAM. It took around 2,000 seconds to complete training for AWS-PA with an absloss estimator on Mushrooms dataset, our slowest experiment. The training runs for other datasets and algorithms were considerably faster.
B.2 Further Details on Numerical Experiments with Different Algorithms
In Section 4
presented numerical results for comparing AWS-PA with other algorithms. These results are shown Figure Below are some additional details for these experiments.
Tuning Sampling Rate Figure I we compare Polyak absolute loss sampling to absolute loss sampling and random sampling. In this setting we have no control over the sampling rate of absolute loss sampling. Hence, we first run absolute loss sampling 14.9%. We then again use binary search to find the value of 3 to match this sampling rate with Polyak absolute loss sampling. Again, this setup conservative with respect to gains of Polyak absolute loss sampling as y and were optimized for sampling rate of 50%.
find an empirical sampling rate of
Sampling Efficiency of AWS-PA In Figure we had demonstrated on various datasets that AWS- based sampling Yoo and Kweon [2019).
PA leads faster convergence than the traditional 5 presents results as a function of the number of sampled instances, i.c., the number of labeled instances that were selected for training (i.e., cost). This contrasts Figure which showed on
X-axis the total number of iterations. The results confirm that sampling with AWS-PA PA not only leads to faster convergence than traditional loss-based sampling when expressed in terms of number of iterations, but also when expressed in the number of sampled instances.
31

---

8.6
palysk abslloss
0.
6.1
Figure Average cross entropy loss as a function of labeling cost for different sampling methods.
abstoss
abstoes polyake
0.6-
0.6
0.5
eranaeee tast
0.4
0.4
0.2
1000
2300
3050
4000
5000
6000
1000
2000
3000
4000
5000
6000
Reration
Rerstion
Figure 6: Average cross entropy loss on a hold-out testing set for different sampling methods.
AWS-PA Results on Holdout Test Set The results in Figure were obtained using progressive validation Blum et al. [999] procedure where the average loss is measured during an online learning procedure where for each instance the loss is calculated prior the weight update. Figures 6 and show that our finding that AWS-PA PA leads to faster convergence than traditional loss-based sampling and than random sampling also holds true separate hold out test set.
B.3 Further Details on the Robustness of AWS-PA Loss Estimation
presented numerical results for comparison of the training loss achieved by AWS-PA PA algorithm using the ground truth absolute error loss and estimated absolute error loss. These results shown in Figure 2] Here, provide more details for the underlying setup of experiments, and the number of sampled points.
In Section 4
Details on the Absloss Estimator For the experiments Figure 2 we use a separate Random Forest (RF) regressor which estimates absolute error loss based the same set of features as the target model with an addition of the target's model prediction as an extra feature. The estimator is retrained every sampling step using the labeled points observed far. We used the scikit-learn implementation of the RF regressor and manually tuned two hyperparameters for different datasets: (a) number of tree estimators (b) number of "warm-up" steps during which sample content with a constant probability until we collect enough samples to train an RF estimator. We parallelized training of the RF estimator across all available CPU cores and used default values for all other hyperparameters.
The statistics of the absloss as well as the parameters of the RF estimators for different datasets summarized Table 2 From the table, we note that the mean ground truth values of the absloss
1.0-
1.5
0.9
0.8
0.6-
absloss randov
0.8
abdess
0.5
0.5
polakk aboloss
400
600
Rbce
1000
1000
2000
3000
4000
5000
6000
iorration
Iteratoo
Figure 7: Test accuracy for different sampling methods.
32

---

Table Hyperparameters the absloss estimator and the comparison of the mean of ground truth and the mean of estimated absolute loss values.
Dataset
Number of trees
Warm-up steps
Mean absloss
Mean estimated absloss
Mushrooms
25
0.100
0.104
MNIST 3s 5s
25
50
0.089
0.087
Parkinsons
100
0,448
0,443
Splice
100
25
0.163
0.160
Tictactoe
100
0.435
0.416
Credit
100
50
0.277
0.294
poyskcabiloss
sampted labels
samoled labelt
8.00
poysk__tdlers_esimmaaa
600
8:00
400
400
polysk_absing sbsllss
200
Salyak/absllss_etteeeee estimatto
3000
Beration
(a) Mushrooms datasct
(b) MNIST binary classification of 3s 5s
Sampled lanels
polyak, absloss
pollyakt aboloss estimator
200
polyakk
pelynk_ahriioe
40
150
complce
100
50
01
40
80
100
120
144
200
400
600
800
1000
1200
Iteatioo
Itcration
(c) Parkinsons dataset
(d) Splice dataset
300
polyak,
200
polyak, absless
Simpled laves
polyak, absicoss estimator
simpledd labes
polyak, absloss estimator
200-
150-
200-
100
0-
100
200
3.00
400
500
600
700
100
200
300
400
500
iteration
Iteaaton
(c) Tictactoe datasct
(f) Credit dataset
Figure 8: Sampling efficiency for sampling based the ground truth of absolute loss v.s. estimated absolute loss.
largely in line with the mean estimated absloss. This suggests that possible to train absloss estimator with low bias or is even unbiased.
Sampling efficiency of the absloss estimator In Figure we compare the cost of sampling based on the ground truth absolute loss versus sampling based on the estimated absloss. We note that in out datasets,
sampling cost closely matches that of sampling based on ground truth absloss. However, in one of the cases (Splice) the sampling cost is lower and in one of the cases (Credit) it is higher than the baseline.
Alternative absloss estimators In Figure 2 we shared results of AWS-PA using a Random Forest regressor to estimate the absolute loss. Figure@sshwss shows the results the credit dataset of an otherwise identical experimental setup where we have replaced the Random Forest regressor absloss estimator with MLP neural network.
33

---

polyak absioss
polyak_absloss
cross-entin entreeytrpyyyyy lass
polyak Balyykkabslosss..__ma absloss__stttee eetiimaorr
0.7
average
0.6
0.5
100
200
400
500
iteration
Figure 9: Credit dataset with an MLP neural network loss estimator.
average cross-entropy loss
sampling probability: 0.010
sampling probability: 0.100
0.50
0.25
0.25
polyak_powar function
0.00
2000
4000
6000
2000
4000
6000
iteration
iteration
Figure 10: Average cross-entropy progressive loss of Polyak's step size compared SGD with constant step size, for 1 and 10% sampling from the mushrooms data.
B.4 Additional experiments
Experiments with different sampling rates Loizou et al. [202]] demonstrated that stochastic gradient descent with a step size corresponding their stochastic Polyak's step size converges faster than gradient descent. Figure [ejuurtO@lllusrattt that these findings extend to scenarios where selectively sample from the dataset rather than training on the full dataset, and the step size is according to stochastic Polyak's step size only in expectation.
To perform these experiments, similarly to the procedure deseribed in Appendix B.I we used binary search to find the value of 3 that correspondingly achieves the two target values I % and 10% with Polyak power function, while using the values of 1) and p that were optimised for a sampling rate of 50%. Therefore, our findings of the gains achieved for selective sampling according to stochastic Polyak's step size are likely conservative since 7 and p were not optimised for specifically these sampling rates.
Experiments with synthetic absloss estimator We simulate noisy estimator the absolute error loss AWS-PA We model an unbiased noisy estimator labe of the absolute error loss Lake E [0, 1] as random variable following the beta distribution, denoted as late Beta(a, 9),, where a and B are parameters set to ensure E [[aaba] = Labs- The variance of the noise can be controlled by the tuning parameter a, given by
Labs (1 Labs)
varléabs]
a + labe
Figure II shows that the convergence results are robust against estimation noise of the absolute error loss for wide range of values for a 2 1.
34

---

0.7
average cross entropy loss
polyak_absloss absloss
0.6
polyak absloss high noise
polyak_absloss absioss_ med noise
0.5
polyak_absloss, absloss__oow low_ onise
0.4
0.2
0.1
1000
2000
3000 4000 5000 6000 of iterations
Figure 11: Robustness of the proposed sampling approach with adaptive Polyak's step size for different variance var var[fatel = L labs)/(o /( + labs) noise levels of absolute error loss estimator: (low) a = 100, (medium) a 2.5, and (high) a = 1.
NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In the abstract and introduction, we summarize the problem settings that we consider and our results in these settings.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: the limitations section (Section A.1 we indicate several avenues for future
work that could be pursued to extend our work.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
35

---

The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't It acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We present basic assumptions and definitions in Section We list all the assumptions in the statements of the theorems. Complete proof's of our theoretical results are provided in Appendix
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: In Section provide the information for reproducing numerical results, along with more details provided Appendix
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility also be provided via detailed
36

---

instructions for how to replicate the results, access to a hosted model (e.g., g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome deseribe the particular way they provide for reproducibility. the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The datasets that we use are available in public domain and we have provided references for these datasets. We have provided detailed information about algorithms and experimental setups, which should be sufficient for reproducing our experiments. The code itself is publicly available at http:////ihhbbb.cccfffaaebreeree
ShaptiviieeiggttSmmp....g
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
jublic/guidess (tool///guidee//deeettuisssssss sisionyylccy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
7 7/nips. cc/ httcc/ubllccgguuueeeee wwwpc//ggieseseeee http:///ooooSSSisiiooieeeeem
stiobbmiissioooooooc.. for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question:
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
37

---

We have explained how the data is fed to the SGD algorithms that we consider, along with the sampling component and setting of the step size, hyperparameter tuning and other relevant details.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: Our experimental results show the training loss versus the number of iterations for single epoch. This is a standard way for comparing convergence rates of different algorithms. Consistency of our results is demonstrated through validation by using different training datasets.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2- 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have provided details on the compute resources we had used for running our experiments in Appendix B.I
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
38

---

The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpp/////eerpppp.c///up////////
Question:
Answer: [Yes]
Justification:
We have reviewed the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Given that this study primarily focuses on theoretical analysis, we do not foresee any negative social consequences.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymeet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML..
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
39

---

Released models that have high risk for misuse or dual-use use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We have cited references for the datasets that used well as for any other assets we used.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version asset used and, possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the pataasess.paperswtt paperswi thcode. cow/coo////ooooo /atasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
40

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
41


Reviews:
[{"review_id": "z4oT7V8YJg", "reviewer": "Reviewer_ie4P", "summary": "This submission studies the convergence guarantees of and bounds on the expected number of samples used when using loss based active learning. They additionally propose a new sampling scheme that combines loss based sampling and a Polyak step size and provide convergence guarantees. Their analysis covers multiple models and loss functions. They proposed methods further evaluated with numerical experiments on multiple datasets.", "questions": "To address the listed lack of clarity, is the above understanding correct?  \n\nAside from the lack of clarity mentioned above, the primary question from an optimization perspective is the choice of the Polyak step size. Given there are many choices for “adaptive” step size methods, it would be interesting to know the motivation behind this choice, and if other methods were considered.", "limitations": "The authors have addressed some limitations in their work and potential future directions.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The problem addressed is interesting and has not been addressed in the literature. In order for loss  based sampling strategies to be effectively deployed in the wild this sort of analysis is necessary. The algorithmic contributions are also of interest, and borrow a well known approach to setting step sizes (Polyak step sizes) from the optimization community to define their Adaptive-Weight Sampling scheme. This combination is a novel idea and a starting point to explore other methods of setting step sizes in this active learning context.", "weaknesses": "While  the technical contributions of this paper are interesting, the primary weakness is the communication of results. This reviewer has an optimization background rather than an active learning one, but even accounting for this the organization and exposition of results was challenging follow. For example, rather than defining algorithms in a LaTeX algorithm block as is standard in literature, authors simply  refer to modifying the (projected) SGD update. While the general idea of active learning is simple, it is also unclear which variant of active learning the authors are studying. Based on the step size being defined as a Bernoulli variable and the experiments conducting one pass over the dataset, it appears that the authors are studying a “streaming” approach to active learning, where the decision to evaluate the label or not is made upon encountering each datapoint. It appears that the selection operation is to ignore when the Bernoulli sample is zero and evaluate the loss otherwise. This is not made clear in the writing, and an optimization audience may be confused as to why some steps will have step size zero. This understanding could be incorrect, which is likely due to the lack of clarity and motivation of the definitions and algorithms. The authors are encouraged to be more explicit about what problem they are trying to solve, and what the exact definitions of their algorithm is.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for appreciating the importance of our work in ensuring the effective deployment of loss-based sampling strategies in practice, and suggesting where we can improve the presentation quality.\n\n# Question 1\nIn response to the first question raised by the reviewer: the reviewer's understanding of our problem formulation and algorithm definition is correct. We study convergence rates in the streaming computation setting, where the decision to evaluate the label or not is made upon encountering each data point. This is the same setting as in the convergence analysis of uncertainty-based sampling policies by Raj and Bach [2022]. Our algorithm is defined as the projected SGD in Equation (1) with a stochastic step size ($z_t$ in iteration $t$). Different active learning algorithms are accommodated by appropriately defining the distribution of the stochastic step size $z_t$, allowing for loss- and uncertainty-based sampling. Specifically, we consider constant-weight and adaptive-weight sampling policies, which are explained in Section 2, with further details provided in Section 3 for each algorithm studied. The decision not to evaluate the label of the data point in iteration $t$ implies a stochastic step size of zero ($z_t = 0$). We appreciate the reviewer's comment that a reader with an optimization background may get confused because our setup is similar to but different from the standard projected SGD. The meaning of the stochastic step size in the active learning setting is also different from what is typical in optimization. In our revision, we will add text to emphasize that we study convergence in the streaming computation setting and provide additional explanations for our definitions and algorithms. Specifically, we will make the following modifications in the problem statement section.\n\n### Revision of Section 2: (added text in bold)\n\n__Consider the setting of streaming algorithms where a machine learning model parameter $\\theta_t$ is updated sequentially, upon encountering each data point, with  $(x_1,y_1),\\ldots, (x_n,y_n) \\in \\mathcal{X}\\times \\mathcal{Y}$ denoting the sequence of data points with the corresponding labels, assumed to be independent and identically distributed with distribution $\\mathcal{D}$. Specifically, we consider the class of projected SGD algorithms defined as: given an initial value $\\theta_1\\in \\Theta$,__\n\n\n\n$\\theta\\_{t+1} = \\mathcal{P}\\_{\\Theta\\_0}\\left (\\theta\\_t - z\\_t \\nabla\\_\\theta \\ell(x\\_t, y\\_t, \\theta\\_t)\\right), \\hbox{for}\\hspace{0.1cm}  t \\geq 1$  (Equation 1)\n\nwhere $\\ell:\\mathcal{X}\\times \\mathcal{Y}\\times \\Theta\\rightarrow \\mathbb{R}$ is a training loss function, $z_t$ is a stochastic step size with mean $\\zeta(x_t, y_t, \\theta_t)$ for some function $\\zeta: \\mathcal{X} \\times \\mathcal{Y} \\times \\Theta \\mapsto \\mathbb{R}\\_+$, $\\Theta\\_0 \\subseteq \\Theta$, and $\\mathcal{P}\\_{\\Theta_0}$ is the projection function, i.e., $\\mathcal{P}\\_{\\Theta_0}(u) = \\arg\\min\\_{v \\in \\Theta_0} ||u - v||$. Unless specified otherwise, we consider the case $\\Theta\\_0 = \\Theta$, which requires no projection. For binary classification tasks, we assume $\\mathcal{Y} = \\{-1,1\\}$. For every $t>0$, we define $\\bar{\\theta}\\_t = (1/t)\\sum\\_{s=1}^t \\theta\\_s$.\n\n__By defining the distribution of the stochastic step  size $z_t$ in Equation 1 appropriately, we can accommodate different active learning and data subset selection algorithms. In the context of active learning algorithms, at each step $t$, the algorithm observes the value of $x_t$ and decides whether or not to observe the value of the label $y_t$ which affects the value of $z_t$. Deciding not to observe the value of the label $y_t$ implies the step size $z_t$ of value zero (not updating the machine learning model).__\n\nFor the choice of the stochastic step size, we consider two cases: (a) \\emph{Constant-Weight Sampling}: a Bernoulli sampling with a constant step size, and (b) \\emph{Adaptive-Weight Sampling}: a sampling that achieves stochastic Polyak's step size in expectation. \n\nFor case (a), $z\\_t$ is the product of a constant step size $\\gamma$ and a Bernoulli random variable with mean $\\pi(x\\_t, y\\_t, \\theta\\_t)$. \nFor case (b), $\\zeta(x, y, \\theta)$ is the \"stochastic\" Polyak's step size, and $z\\_t$ is equal to $\\zeta(x\\_t, y\\_t, \\theta\\_t) / \\pi(x\\_t, y\\_t, \\theta\\_t)$ with probability $\\pi(x\\_t, y\\_t, \\theta\\_t)$ and is equal to $0$ otherwise. Note that using the notation $\\pi(x,y,\\theta)$ allows for the case when the sampling probability does not depend on the value of the label $y$.\n\n# Question 2\nWith regard to the question on the motivation for studying the adaptive step size according to stochastic Polyak's step size, our primary motivation is its fast convergence rate, as shown by Loizou et al. [2021], both theoretically and experimentally. Specifically, it achieves a convergence rate of $O(1/n)$ in a smooth convex optimization setting, which is an improvement compared to a projected SGD with a constant step size, which achieves a convergence rate of $O(1/\\sqrt{n})$. The experimental results in Loizou et al. [2021] demonstrate cases where the adaptive step size according to stochastic Polyak's step size outperforms several benchmarks used for comparison, including the popular Adam optimizer. Our work shows that the aforementioned theoretical convergence rate guarantee of projected SGD with adaptive step size according to stochastic Polyak's step size can be achieved in a data sampling or active learning setting, as shown in Theorem 3.6. Loizou et al. [2021] did not study this setting. As for considering other adaptive step sizes, future work may study their convergence properties when used in conjunction with sampling, as in our adaptive-weight sampling algorithm. We will add a note to propose this as an interesting direction for future research in the conclusion section.", "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": "", "extra_scores": {}}, {"review_id": "oLMoUjU6Kj", "reviewer": "Reviewer_UMCS", "summary": "The paper considers the active learning algorithms based on uncertainty and loss functions. The learner queries the label of an unlabeled sample with probability proportional to (some function of) the uncertainty/loss and updates the parameter according to some step size scheme. The authors generalize previous results under the strictly separable binary classification setting and general classification setting with convex loss and smooth equivalent loss. The authors later propose a Polyak-type step size scheme called Adaptive-Weight Sampling and prove its convergence. Numerical experiments verify the efficiency of AWS under both oracle and estimation of loss functions.", "questions": "1. I wonder if it is possible to relax the requirement of knowing the exact loss functions before querying the label of the sample point.\n2. What's the comparison between the theoretical sample complexity of active learning (uncertainty/loss-based sampling) and that of passive learning (uniform sampling) in the considered problem setting?\n3. The authors conduct experiments on \"uniform sampling\" + \"constant step size\", \"loss-based sampling\" + \"constant step size\", and \"loss-based sampling\" + \"Polyak step size\" to verify the effectiveness of the approach of loss-based sampling. For completeness, it is necessary to present the performance of using \"uniform sampling\" + \"Polyak step size\" in the numerical experiments.\n(raised my rating from 5 to 6 after the rebuttal)", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The analysis is solid;\n2. The presentation is clear;\n3. The Adaptive-Weight Sampling (AWS) algorithm provides a novel perspective for active learning literature.", "weaknesses": "1. The generalization of previous results seems not to be very essential;\n2. The assumption of access to the exact loss function before querying seems too strong for theoretical analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing insightful and useful comments.\n\n# Weakness 1\nWe would like to clarify the reviewer's comment that we generalize previous results under the strictly separable binary classification setting and the general classification setting with convex loss and smooth equivalent loss. For the linearly separable binary classification setting, we provide new results on the convergence rates for loss-based sampling strategies. Previous work focused on margin of confidence uncertainty-based sampling (Raj and Bach [2022]) which is different. Our results on the convergence rates of constant-weight sampling for \"general classification with convex loss\" and \"smooth equivalent loss\" generalize the work by Liu and Li [2023]. Importantly, our convergence rate bounds allow for different sampling probability functions, going beyond specific sampling probability functions such as sampling proportional to a loss value.\n\n# Weakness 2 / Question 1\nFor the theoretical convergence rate analysis, it may be possible to relax the requirement of knowing the exact loss function value before querying the label of the sample point. This would involve accounting for the estimation noise of the loss value in the convergence rate analysis. This is an interesting avenue for future research, as indicated in the conclusion section. Note that in our experiments Figure 2, we evaluated algorithms that sample points using a loss value estimator, thus alleviating the need to know the exact loss value before querying the label of the sample point.\n\n# Question 2\nFor the question on the comparison of sampling complexities of active learning algorithms and those using uniform sampling of data points, we regard this as an interesting question for theoretical study. Such a study should consider both convergence rate and sampling complexity of algorithms. Please __see the comment below__ for a detailed discussion for the class of projected SGD algorithms using a loss-based sampling. \n\n# Question 3\nWe thank the reviewer for this suggestion. We conducted additional experiments to include the case of \"uniform sampling\" with \"Polyak step size.\" We will include this case in Figure 1 of our revised paper. The new experimental results are provided in the attached PDF file.\n\nFrom the results, we observe that applying stochastic Polyak's step size with uniform random sampling leads to faster convergence compared to uniform sampling with regular SGD updates. Moreover, sampling according to absolute error loss with stochastic Polyak's step size substantially improves upon uniform sampling with stochastic Polyak's step size.", "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": "", "extra_scores": {}}, {"review_id": "qu1umG925s", "reviewer": "Reviewer_7aAT", "summary": "This is a technical paper, whose subject of interest is the convergence of stochastic gradient-based learning algorithms which include a stochastic step size mechanism, whose value is allowed to be influenced by losses or other \"uncertainty\" related quantities that are computed at training time.\n\nTheir main theoretical results can be roughly broken into two categories based on the assumptions placed on the step-size mechanism. The first category is where the step size is a re-scaled Bernoulli random variable, taking values in $\\\\{0, \\\\gamma\\\\}$ in their notation, with $\\\\gamma$ fixed throughout but the probability of a non-zero step size (i.e., $z\\_{t} = \\\\gamma$) can change depending on the data/parameter at each step in the training routine. They start with an argument centered around a monotonic loss function and linear binary classifiers, but also consider an \"equivalent loss\" type of strategy (like in Liu an Li '23), again where a convenient monotonicity assumption (here on $\\\\pi$) preserves convexity and aids in analysis. Their main bounds are in-expectation upper bounds on the loss incurred by the average of iterates generated using this Bernoulli step size.\n\nThe second category is similar, but allows the actual step size to be impacted by loss/gradient values in an \"adaptive\" way, while retaining a certain probability of step size 0. This combination of Bernoulli step sizes with an adaptive step size is what they call \"Adaptive-Weight Sampling (AWS)\", and they provide conditions to obtain upper bounds on the (empirical) objective function of interest (i.e., the average loss). \n\nTheir theoretical results are complemented by empirical analysis, in which they compare uniform random sampling (of points for SGD), \"traditional\" loss-based sampling, and their AWS approach (their Fig 1). This setup assumes loss access, i.e., this is not active learning. On the other hand, for active learning scenarios, a loss estimator needs to be plugged in; they consider the impact of the quality of such an estimator in their second batch of tests (their Fig 2).", "questions": "Here are some points that caught my eye while reading the paper. Some are obvious typos, others are poor technical exposition.\n\n- What is the difference with Loizou et al. (2021)? In line 64, the authors say their work is different *\"as we consider convergence of SGD under sampling of points.\"* How is this different? It is unclear.\n\n- Line 140: typo of $\\\\mathcal{Y} = \\\\{-,1,1\\\\}$, should be $\\\\mathcal{Y} = \\\\{-1,1\\\\}$.\n\n- In the key bound of Theorem 3.1 (for example), what is expectation being taken with respect to? On the left-most side of the main inequality, $x$ and $y$ appear. One step to the right, and only $x\\_{t}$ and $y\\_{t}$ appear. Since there is no generalization analysis, I assumed expectation was with respect to $(x\\_{1},y\\_{1}),\\\\ldots,(x\\_{n},y\\_{n})$ and the randomness in the stochastic algorithm. Is this correct, or are $x$ and $y$ supposed to indicate test data?\n\n- I found the statement on page 5 that *\"algorithm (1) is an SGD algorithm with respect to an objective function $\\\\tilde{\\\\ell}$ with gradient...\"* a bit troubling. Given a random sample of $(x,y)$, indeed $\\\\pi(x,y,\\\\theta)\\\\nabla\\_{\\\\theta}\\\\ell(x,y,\\\\theta)$ is an unbiased estimator of $\\\\nabla\\_{\\\\theta}\\\\tilde{\\ell}(\\\\theta)$ as defined in (3), but in the case of constant-weight sampling, $z\\_{t}$ is *not* equal to $\\\\pi(x\\_{t},y\\_{t},\\\\theta\\_{t})$, but rather $\\mathbb{E}[z\\_{t}] = \\\\gamma\\\\pi(x\\_{t},y\\_{t},\\\\theta\\_{t})$, correct? Perhaps the authors are just glossing over the $\\\\gamma$, but I think if the authors want to say that $\\mathbb{E}[z\\_{t}\\\\nabla\\_{\\\\theta}\\ell(x\\_{t},y\\_{t},\\\\theta\\_{t})]$ equals the right-hand side of (3), it should be done a bit more precisely.\n\n- What is the main difference between the second half of section 3.1 and the work of Liu and Li (2023)? Are they considering the same problem and just looking at one special case of $\\\\Pi$ and $\\\\pi$? Is the problem setting different? This is all unclear to me.\n\n- Lemma 3.2: font for expectation is different from the other results ($\\\\mathbf{E}$ versus $\\\\mathbb{E}$).\n\nOverall, there is a decent effort here, but I think the paper still needs a fair bit of polish.", "limitations": "Not applicable.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "Overall, the paper is quite well-written and has a natural logical structure which is easy to follow. The authors have obtained a flexible set of conditions for evaluating SGD procedures with a stochastic loss-dependent step size mechanism, which appear to build quite directly upon the existing literature, which they are good about citing (e.g., Raj and Bach '22, Liu and Li '23).\n\nThe paper is a mixture of different efforts, some new convergence theory, a new proposed algorithm (AWS), plus formal/empirical analysis of this algorithm, and I think there is potential for this work to have an audience at a conference like NeurIPS.", "weaknesses": "I am not familiar with the related technical literature, so I will not comment on the novelty or theoretical prowess required to obtain the results here.\n\nI would personally highlight two main points I feel need improvement. The first point is that the narrative of this paper feels really bloated. To the best of my reading, all the talk of \"active learning\" in the title and throughout the paper is totally irrelevant to the entire paper, save for the last paragraph of section 4 plus Figure 2. Yes, there are obvious links between the procedure of interest here and active learning settings, but the core problem setting stands on its own just fine. There is no reason to structure the paper around active learning, it just makes things confusing and downplays the substantive results. I feel like I can say the exact same thing about \"uncertainty-based\" methods. The only uncertainty-related formulation I can find is Corollary 3.8. Having this is great, but why put uncertainty-based and loss-based methods on the same footing when writing the paper?\n\nThe second point is related to technical exposition. For the most part the work seems to be well done, but for a first-time reader, certain parts feel rushed and sloppy. I'll make a list of points I tripped up on in the following section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for a well-rounded summary of our results and for recognizing their potential interest to a NeurIPS-like community.\n\n# Weaknesses\nThe review focuses on some presentation issues. First, it argues that focusing the paper's exposition around active learning may be confusing and downplays our substantive results (on sampling-based learning). Additionally, it notes that it is unclear why we cover both loss-based and uncertainty-based methods, with the latter discussed only in some parts of the paper. Second, the reviewer noted some technical notation points that require clarification.\n\nThe class of algorithms we study (projected SGD with stochastic step size), defined in Section 2, accommodates active learning and data subset selection algorithms by appropriate definition of the stochastic step size.\nThe framework of projected SGD with stochastic step size can accommodate different data sampling strategies, including those depending on loss and uncertainty criteria. Our theoretical results in Section 3 apply to active learning learning algorithms under assumption that the algorithm decides whether or not to query the label of a data point based on knowing the exact loss value. Our experimental results evaluate active learning algorithms that decide whether or not to query the label of a data point based on estimated loss value, which showed good conformance to algorithms using exact loss values. Our theoretical results in Section 3 apply to data selection algorithms which can observe the value of the label of each data point, and use this to compute the exact loss value. In our revision of Section 2, we will clarify the connection between active learning algorithms and the projected SGD with stochastic step size--see the concrete revisions we plan to make in Section 2 in our response to reviewer Reviewer ie4P.\n\nAs for why covering both loss-based and uncertainty-based methods in our paper, we note that our theoretical framework and results allow us to derive convergence rate bounds for both these methods. Uncertainty-based methods are discussed at several points in our paper and the associated appendix. Following Theorem 3.1 we comment that the proof technique allows to establish the convergence rate for margin uncertainty-based method considered in Raj and Bach [2022]. In Corollary 3.8, we identify an uncertainty-based sampling probability for which the convergence rate bound in Theorem 3.6 holds. Furthermore, in Appendix A.15, we show how this can be extended to a multi-class classification setting. \n\n# Question 1\nThe difference is that, unlike Loizou et al [2021], we use *sampling* of points. In contrast, the algorithm by Loizou et al [2021] conducts SGD update with adaptive step size for every input point. Note that this difference is also precisely what makes our work focused on active learning, which focuses on efficient selection/sampling of points. __The comment titled \"Proposed clarification for question 1\"__ contains the proposed textual clarification for the introduction section. The changes to the problem statement that we propose in response to reviewer ie4P further clarify this.\n\n# Questions 2 & 6\nThese are just typos -- we'll fix them.\n\n# Question 3\nIn our paper, we consider the streaming computation setting where $(x_1,y_1), \\ldots, (x_n,y_n)$ is a sequence of independent and identically distributed labeled data points with distribution $\\mathcal{D}$. We will clarify this in the problem statement section (see the revised text in a response to Reviewer ie4P). In Theorem 3.1, $(x,y)$ is an independent sample of a labeled data point from $\\mathcal{D}$. Will clarify this by revising the statement of the theorem as __shown in comment titled \"Proposed clarification for Question 3\"__.\n\nFurther details: in Theorem 3.1, we have\n$\\mathbb{E}\\left[\\ell(yx^\\top \\bar{\\theta}\\_n)\\right] \\leq \\mathbb{E}\\left[\\frac{1}{n}\\sum\\_{t=1}^n \\ell(y\\_t x\\_t^\\top \\theta\\_t)\\right].$\n\nSince we consider a streaming algorithm and $(x_1,y_1), \\ldots, (x_n, y_n)$ is a sequence of independent labeled data points, for every $t\\in \\{1,\\ldots, n\\}$, $(x_t,y_t)$ and $\\theta_t$ are independent random variables as $\\theta_t$ depends only on $(x_1,y_1),\\ldots, (x_{t-1},y_{t-1})$. Hence, it follows that\n\\begin{eqnarray*}\n\\mathbb{E}\\left[\\frac{1}{n}\\sum_{t=1}^n \\ell(y_t x_t^\\top \\theta_t)\\right] &=& \\frac{1}{n}\\sum_{t=1}^n\\mathbb{E}\\left[\\ell(y_t x_t^\\top \\theta_t)\\right]\\\\\n&=& \\frac{1}{n}\\sum_{t=1}^n \\mathbb{E}\\left[\\ell(y x^\\top \\theta_t)\\right]\\\\\n&=& \\mathbb{E}\\left[\\frac{1}{n}\\sum_{t=1}^n \\ell(y x^\\top \\theta_t)\\right]\\\\\n&\\geq & \\mathbb{E}\\left[\\ell\\left(yx^\\top \\frac{1}{n}\\sum_{t=1}^n \\theta_t\\right)\\right]\\\\\n&=& \\mathbb{E}\\left[\\ell(yx^\\top \\bar{\\theta}_n)\\right]\n\\end{eqnarray*}\nwhere the last inequality follows from Jensen's inequality, as $\\ell$ is assumed to be a convex function. \n\n\n# Question 4\nIn the context of Equation (3), as noted in the text, $z_t$ is defined by $z_t = \\gamma \\zeta_t$, where $\\zeta_t$ is a Bernoulli random variable with mean $\\pi(x_t,y_t,\\theta_t)$. This is defined in the text.\n\n# Question 5\nThe problem setting is the same. The main difference is that we consider sampling according to a sampling probability function $\\pi$, while Liu and Li (2023) considered only some special cases of $\\pi$ such as sampling proportional to conditional loss value. We discussed this in the related work Section 1.2.", "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": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their insightful comments. We appreciate the positive feedback recognizing the problem we study as interesting, novel, and important, as well as the positive assessment of our results, which include both theoretical and experimental analyses. We also value the technical questions and suggestions for improving the clarity of our presentation.

Our study is motivated by the increasing interest in using active learning algorithms to effectively train machine learning models, focusing on the convergence rate of the training loss function and data labeling cost, as well as scalable training of machine learning algorithms by using a subset of training data points. We focus on data selection methods based on data point loss values (loss-based methods)
as those have recently gained attention both in theory (we list several references in the paper) and practice (it is deployed in various industry applications),
while their performance guarantees are not well understood. Our theoretical framework and results also cover more common uncertainty-based methods, where data points are selected based on a notion of prediction uncertainty.

The reviewers expressed different opinions regarding the presentation quality of our paper, with one reviewer finding it clear and others suggesting areas for improvement.
We appreciate the reviewer's feedback and acknowledge that our initial submission lacked clarity, in particular in explaining that we consider a class of streaming algorithms, focusing on projected SGD algorithms with stochastic step size, and how the concept of the stochastic step size relates to active learning and data subset selection problems. A crucial point to understanding this connection is that a zero step size can be seen as not selecting a point for labeling, and hence, the connection to loss-based active learning arises from stochastic step sizes that are specific to each point and depend on its estimated loss. In our review responses, we proposed concrete revisions to clarify these points.

Our theoretical results on convergence rates and sampling complexity of loss-based methods apply to active learning under the assumption that the algorithm has access to the exact loss value of each data point, which is used to decide whether to query the value of a data point's label. In practice, a loss-based active learning algorithm uses a noisy estimate of loss values, which is considered in our experimental results, showing good conformance with our theoretical results. We regard our theoretical results as an important step towards understanding loss-based active learning algorithms. In the context of the data subset selection problem, the algorithm can observe the label of each training data point, and thus exact loss values of data points are available to the algorithm.

A reviewer noted that we missed providing experimental results for one combination of sampling and adaptive step size, namely, uniform sampling with stochastic Polyak's step size. In response, we conducted additional experiments and included the results in our responses (see link to PDF below).

Meta-review: All the reviewers viewed the paper favourably, and it is a creative perspective so I think it would be welcome at the conference.
Decision: Accept (poster)