Proposed change to Theorem 3.1, changed highlighted in bold.

Assume that $\rho^* > 1$, the loss function is the squared hinge loss function, and the sampling probability function $\pi$ is such that for all $u \leq 1$, $\pi(u) \leq \beta/2$ and

$\pi(u) \geq \pi^*(\ell(u)) := \frac{\beta}{2}\left(1-\frac{1}{1+\mu\sqrt{\ell(u)}}\right)$

for some constants $0 < \beta \leq 2$ and $\mu \geq \sqrt{2}/(\rho^*-1)$. Then, for any initial value $\theta_1$ such that $||\theta_1-\theta^*||\leq S$ and $\\{\theta_t\\}_{t>1}$ according to algorithm (1) with $\gamma = 1/R^2$,

$\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] \leq \frac{R^2 S^2}{\beta}\frac{1}{n},$

where $(x,y)$ is an independent sample of a labeled data point from $\mathcal{D}$.

Moreover, if the sampling is according to $\pi^*$, then the expected number of sampled points satisfies:

$\mathbb{E}\left[\sum\_{t=1}^n \pi^*(\ell(y\_t x\_t^\top \theta\_t))\right] \leq \min\\{\{\frac{1}{2}R S \mu\sqrt{\beta} \sqrt{n},\frac{1}{2}\beta n\}\\}.$

We propose to clarify this as follows in the introduction, where the added text is highlighted in bold:

There is a large body of work on 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 et al. [2021], 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 a sampling of points and an adaptive step size update that conform to the stochastic Polyak's step size in expectation. This is unlike to the adaptive step size SGD algorithm by Loizou et al [2021] which does not use sampling.

We thank the reviewer for a well-rounded summary of our results and for recognizing their potential interest to a NeurIPS-like community.

Weaknesses

The 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.

The 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. The 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.

As 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.

Question 1

The 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.

Questions 2 & 6

These are just typos -- we'll fix them.

Question 3

In 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".

Further details: in Theorem 3.1, we have $\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].$

Since 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 \begin{eqnarray*} \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]\ &=& \frac{1}{n}\sum_{t=1}^n \mathbb{E}\left[\ell(y x^\top \theta_t)\right]\ &=& \mathbb{E}\left[\frac{1}{n}\sum_{t=1}^n \ell(y x^\top \theta_t)\right]\ &\geq & \mathbb{E}\left[\ell\left(yx^\top \frac{1}{n}\sum_{t=1}^n \theta_t\right)\right]\ &=& \mathbb{E}\left[\ell(yx^\top \bar{\theta}_n)\right] \end{eqnarray*} where the last inequality follows from Jensen's inequality, as $\ell$ is assumed to be a convex function.

Question 4

In 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.

Question 5

The 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.

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.

Question 1

In 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.

Revision of Section 2: (added text in bold)

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$,

$\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)

where $\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$.

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).

For the choice of the stochastic step size, we consider two cases: (a) Constant-Weight Sampling: a Bernoulli sampling with a constant step size, and (b) Adaptive-Weight Sampling: a sampling that achieves stochastic Polyak's step size in expectation.

For 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)$. For 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$.

Question 2

With 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.

We first discuss convergence rate bounds. For the linearly separable binary classification case, in our paper, we provide conditions under which loss-based sampling policies achieve a convergence rate of $O(1/n)$ for the squared hinge loss function, the same as the perceptron algorithm (Theorem 3.1, and see also Theorems A.5 and A.6 in the appendix). It is well known that standard projected SGD algorithm with a constant step size guarantees a convergence rate of $O(1/\sqrt{n})$ for smooth convex loss functions. This convergence rate can be improved to $O(1/n)$ by using stochastic Polyak's step size, as shown by Loizou et al. [2021]. Our Theorem 3.3 shows that a convergence rate of $O(\Pi^{-1}(1/\sqrt{n}))$ can be achieved by a constant-weight, loss-based sampling with the sampling probability function $\pi$, where $\Pi$ is the primitive function of $\pi$. Our adaptive-weight sampling algorithm guarantees the same convergence rate as the algorithm that samples every point using projected SGD with stochastic Polyak's step size (Loizou et al. [2021]) under conditions given in Theorem 3.6. For our adaptive-weight sampling algorithm, with a constant sampling probability $\pi(x,y,\theta) = p$ for all $x,y,\theta$, the convergence rate bound in Theorem 3.6 holds provided that $p$ satisfies the condition in Equation (6).

We next discuss sampling complexity bounds, i.e., the bounds on the expected number of sampled points by an algorithm. The sampling complexity of an algorithm that samples each point is clearly $n$, where $n$ is the number of SGD updates. This stands in contrast to the sampling complexity of $O(\sqrt{n})$, which is shown to hold for active learning algorithms using certain loss-based policies (Theorem 3.1 and Lemma 3.5). We next consider the case of "uniform sampling," where each data point is sampled with a fixed probability $p$. In this case, the expected number of sampled points is $pn$.

For the linearly separable binary classification case, with uniform sampling with probability $p=\beta/2$, the convergence rate bound in Theorem 3.1 holds and the sampling complexity is $O(\beta n)$. This stands in contrast to the sampling complexity of $O(\sqrt{\beta n})$ under loss-based sampling according to $\pi^*$ defined in Theorem 3.1.

For the general classification setting, we provide the following discussion. For the projected SGD with uniform sampling, we can derive convergence rate bounds by using known results for projected SGD with a constant step size. Consider the projected SGD as in Equation (1) of our paper, with stochastic step size $z_t$ equal to the product of a fixed step size $\gamma > 0$ and $\zeta_t$, where $\zeta_t$ is a sequence of independent Bernoulli random variables with mean $p$. Then, we may regard this as an SGD algorithm with a constant step size $\gamma p$ and the stochastic gradient vector $g_t = (z_t/p) \nabla_\theta \ell(x_t,y_t,\theta_t)$. This stochastic gradient vector is clearly an unbiased estimator of $\nabla\_\theta \ell(x_t,y_t,\theta_t)$ and we have $\mathbb{E}[||g_t - \nabla\_\theta \ell(x\_t,y\_t,\theta\_t))||\_2^2\mid x\_t, y\_t, \theta\_t] = (1/p-1)||\nabla\_\theta \ell(x\_t,y\_t,\theta\_t)||^2$. Thus, we have $\mathbb{E}[||g\_t - \nabla\_\theta \ell(x\_t,y\_t,\theta\_t))||\_2^2\mid x\_t,y\_t,\theta\_t]\leq (1/p-1)\sigma^2$, for $\sigma$ such that $||\nabla \ell(x,y,\theta)||\_2^2\leq \sigma^2$, for every $x,y,\theta$. For smooth and convex loss functions, by a well-known convergence result for projected SGD with a constant step size (covered by Theorem 6.3 in Bubeck [2015]), it can be readily shown that for the step size set to $p/(L+(\sigma/S)\sqrt{1/p-1}\sqrt{n/2})$, the following convergence rate bound holds:

where $L$ and $S$ are defined in our paper. Hence, we have the sampling complexity $O(pn)$ and the convergence rate bound $O(1/\sqrt{pn})$. From Theorem 3.3 in our paper, we have the convergence rate bound $O(\Pi^{-1}(\sqrt{2}S\sigma_\pi/\sqrt{n}))$, and with additional assumption that $\pi$ is concave, the sampling complexity $O(\pi(\Pi^{-1}(\sqrt{2}S\sigma_\pi/\sqrt{n}))n)$. For the uniform sampling case, we have $\pi(x) = p$ and $\Pi^{-1}(x) = x/p$. Further noting that $\sigma_\pi \leq \sqrt{p}\sigma$, we have the convergence rate bound of $O(1/\sqrt{np})$ and the sampling complexity of $O(pn)$ holds, both conforming to what we derived above.

In our experimental results (see revised Figure 1 in the attached PDF), we demonstrate that faster convergence can be achieved using loss-based sampling compared to uniform sampling for comparable sampling complexity.

We thank the reviewer for providing insightful and useful comments.

Weakness 1

We 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.

Weakness 2 / Question 1

For 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.

Question 2

For 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.

Question 3

We 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.

From 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.

We thank the reviewer for their additional comments, interesting questions for discussion, and useful references. We are glad that the additional experimental results we provided have adequately addressed the concern raised by the reviewer.

We further elaborate on each weakness & question separately in the comments below.

We thank the reviewer for bringing the work by Kolossov, Montanari, and Tandon (2024) to our attention. We will add a discussion of this work in the related work section. Additionally, we will compare the sampling functions studied therein with those considered in our work. The examples of loss-based sampling functions we present are motivated by practical applications, such as the use of absolute error loss in certain industrial contexts.

We will include additional discussion on the case where the exact loss function is unknown. This scenario is addressed in our experimental results, where we used a Random Forest estimator. We believe that the concrete choice for Random Forest isn't of particular importance to our results: the important finding is that there exists regression models that lead to numerical results that show good conformance to those obtained using the exact loss values. Such results could also have been obtained with other alternative choices of the loss estimator (as we show through new experiments that we outline below), and this choice of loss estimator is not of material importance.

It is important to note that proposing a specific loss estimator is beyond the scope of our work. We will provide further discussion on the loss estimator we employed and other estimators we tested.

Additional experiments with neural network based loss estimator

Concretely, we have ran additional experiments with a neural network based loss estimator, and like with the RF loss estimator, have obtained numerical results that conform closely to the results that we obtained using the exact loss values.

Per the NeurIPS 2024 FAQ for authors, we're told not to send links in any part of the response, and unfortunately we do not have the ability to edit the official rebuttal anymore, only post comments, so we can't upload a PDF with the figure with the new results. However, we have sent a message to the AC with an anonymized link to the figure with results with the neural network based loss estimator.