On the Convergence of Loss and Uncertainty-based Active Learning Algorithms

Proposed clarification for question 1

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

Proposed clarification for Question 3

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

Detailed response to question 2

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: $$ S\sigma \sqrt{\frac{2(1-p)}{pn}} + \frac{L S^2}{n} $$ 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.

General response to UMCS's comment

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.

Response to Reviewer UMCS's comment on Weakness 2 and Question 1

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](https://neurips.cc/Conferences/2024/PaperInformation/NeurIPS-FAQ#:~:text=the%20author%20rebuttal%3F-,No.,all%20linked%20files%20are%20anonymized), 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.

Response to Reviewer UMCS's comment on Weakness 1

Regarding Weakness 1, in our response, we aimed to emphasize that we provide new results identifying conditions and characterizing the convergence rate and sampling complexity for the linearly separable case. This includes Theorem 3.1 for the squared hinge loss function, as well as several results presented in the appendix, such as Theorem A.5 for sampling proportional to zero-one loss or absolute error loss, and Theorems A.6 and A.7 for a generalized smooth hinge loss function. To the best of our knowledge, these results are novel and provide insights into the performance of loss-based sampling policies. As noted by the reviewer, a key technical aspect in the proofs is the convergence rate Lemmas A.2 and A.3, which generalize Lemma 1 in Raj and Bach's work, which is restricted to specific choices of loss functions and uncertainty-based sampling. This generalization was instrumental in establishing our results and may prove useful in future work. We have discussed how our generalization relates to Lemma 1 by Raj and Bach, as seen in lines 196-203. Additionally, note that the proofs of Theorems 3.1, A.5, A.6, and A.7 also require additional technical steps.

Response to reviewer UMCS's "One more question for your response to my Question 2"

Regarding the question of whether loss-based sampling theoretically has a better sampling complexity or convergence rate than uniform sampling in the general classification setting, this is an interesting question that warrants further study. Our experimental results demonstrate instances where sampling based on absolute error loss shows better sampling complexity and convergence rate than uniform sampling. The convergence rate result in Theorem 3.3 provides an upper bound on the expected cumulative training loss for loss-based sampling according to a sampling function $\pi$. This bound accommodates uniform sampling as a special case, and in that case, it conforms to the bound that can be obtained through the convergence analysis of projected SGD, as outlined in our response. One may compare the convergence rate and sampling complexity bounds for sampling according to a sampling function $\pi$ and uniform sampling, as discussed below. From Theorem 3.3, we have: $$ \mathbb{E}\left[\frac{1}{n}\sum_{t=1}^n \ell(\theta_t)\right] \leq \bar{\ell} $$ where: $$ \bar{\ell}: = \ell^*_\pi + \Pi^{-1}\left(\frac{\sqrt{2}S\sigma_{\pi}}{\sqrt{n}}\right) + \Pi^{-1}\left(\frac{LS^2}{n}\right) $$ and $$ \ell^*_\pi := \inf_{\theta\in \Theta}\Pi^{-1}(\mathbb{E}_x[\Pi(\mathbb{E}_y[\ell(x,y,\theta)\mid x])]). $$ For uniform sampling with probability $p\in (0,1]$, we have $\pi(x) = p$, $\Pi(x) = px$ and $\Pi^{-1}(x) = x/p$. Let $\ell^*:=\inf_{\theta \in \Theta} \ell(\theta)$. By the convexity of $\Pi$ (as $\pi$ is an increasing function), note that $\ell^*_\pi\geq \ell^*$ for every $\pi$. From Theorem 3.3, for uniform sampling with probability $p \in (0,1]$, it holds that: $$ \mathbb{E}\left[\frac{1}{n}\sum_{t=1}^n \ell(\theta_t)\right] \leq \ell^* + \frac{\sqrt{2}S\sigma}{\sqrt{pn}} + \frac{LS^2}{pn} $$ where $\sigma$ is such that $$ \mathbb{E}\_{x,y}[||\nabla\_\theta \ell(x,y,\theta)||^2] - p ||\mathbb{E}\_{x,y}[\nabla_\theta \ell(x,y,\theta)]||^2\leq \sigma^2 \hbox{ for every } \theta \in \Theta. $$ For the discussion of sampling complexity, consider the case where $\pi$ is a concave function. By Lemma 3.5, by sampling according to $\pi$, the expected number of samples is upper bounded by $\pi(\bar{\ell})n$. Obviously, for uniform sampling with probability $p$, the expected number of samples is $pn$. Therefore, the sampling complexity for sampling according to the sampling function $\pi$ is lower or equal to that for uniform sampling with probability $p$ if the following condition holds: $$ p \geq \pi(\bar{\ell}). $$ The convergence rate upper bound under sampling according to $\pi$ is smaller than or equal than that under uniform sampling if the following condition holds: $$ \bar{\ell}\leq \ell^* + \frac{\sqrt{2}S\sigma}{\sqrt{pn}} + \frac{LS^2}{pn}. $$ By a straightforward calculus, it can be shown that this condition is equivalent to $$ \sqrt{pn}\leq S\frac{\sigma + \sqrt{\sigma^2 + 2L(\bar{\ell}-\ell^*)}}{\sqrt{2}(\bar{\ell}-\ell^*)}. $$ Combining with $p \geq \pi(\bar{\ell})$, it is necessary that $$ \sqrt{\pi(\bar{\ell})n}\leq S\frac{\sigma + \sqrt{\sigma^2 + 2L(\bar{\ell}-\ell^*)}}{\sqrt{2}(\bar{\ell}-\ell^*)} $$ which is also sufficient when $p = \pi(\bar{\ell})$. The condition can be further analyzed for different cases including $\ell_\pi^* > \ell^*$ and $\ell_\pi^* = 0$ (and hence $\ell^*=0$). In our revision, we will include further discussion on the dependence of the convergence rate and sampling complexity on the sampling function $\pi$. Additionally, we will highlight as an open research problem the need to study the tightness and comparison of convergence rates and sampling complexities for the general classification setting in the conclusion section.