Stabilizing Linear Passive-Aggressive Online Learning with Weighted Reservoir Sampling

We thank the reviewer for encouraging us to elaborate more on the differences between WRS-Augmented Training (WAT) vs. simply taking the candidate solutions with $K$ largest numbers of passive steps (denoted as ``top-$K$"). The primary operational difference between WAT and top-$K$ lies in the probabilistic sampling steps in Lines 10-15 of Algorithm 1. We hypothesize that WAT's probabilistic approach imbues an element of exploration that may yield dividends in some cases where the number of passive steps might not be a perfect indicator of performance, compared to deterministic top-$K$.

Emphasizing our discussion in Section 4.4 and Tables 2-4, holding reservoir/set size at $K=64$, we find that PAC-WRS (simple average + standard weights) successfully stabilized test accuracy performance on 13 out of 16 datasets compared to PAC + top-$K$'s (simple average) 10 out of 16 datasets, as measured via Relative Oracle Performance and averaged across 5 trials. We focus on simple averaging of reservoir solutions and standard weights (i.e., number of passive steps as opposed to the exponentiated number of passive steps) because, overall, these settings appear to be the most optimal and robust. We also found that FSOL-WRS successfully stabilized test accuracy performance on all 16 of 16 datasets, compared to 15 datasets for FSOL + top-$K$.

Figure 3 in our 1-page rebuttal PDF shows the test accuracy curves over time for WAT and top-$K$ (both with $K=64$) on three datasets --- Avazu (App), Avazu (Site), and Criteo, with PAC as a base model. The shaded regions represent the minimum and maximum test accuracy values at each timestep, taken over each algorithm's 5x trials. The thin lines inside the shaded regions represent the 5x individual trials of each algorithm. The solid lines represent the means taken across the 5x trials. From this Figure 3, we see that the performances of WAT and top-$K$ are not only statistically different, but also oftentimes do not even overlap across the extremes of multiple trials, with WAT being higher performing

Furthermore, synthesizing Table 4 in Section 4.4 and Tables 5-6 in Appendix C, using Wilcoxon Signed-Rank Tests on ROP measured with respect to base PAC/FSOL, we find that top-$K$ cannot yield nearly as statistically-significant increases in test accuracy stability as WAT, for both PAC and FSOL. At significance level $\alpha = 0.05$, while both WAT and top-$K$ can produce statistically-significant increases in final test accuracy compared to base FSOL, top-$K$'s $p$-values are more than an order of magnitude larger than their WAT counterparts. Finally, both WAT and top-$K$ cannot produce statistically-significant increases in final test accuracy on PAC.

To further probe the differences between WAT and top-$K$, for this rebuttal, we also computed Wilcoxon Signed-Rank Tests on ROP, treating top-$K$ as the control method and viewing WRS as a probabilistic treatment/modification of the deterministic top-$K$ control method (using $K=64$). Under this framework, we found that PAC-WRS outperformed PAC + top-$K$ on 12 out of 16 datasets, averaged across 5x trials, with a statistically-significant $p=0.0213$ at significance level $\alpha = 0.05$. In other words, using PAC as base model, injecting this probabilistic treatment to form WAT was statistically-significant at improving test accuracy stability, compared to deterministic top-$K$. On FSOL, under this second hypothesis testing framework, FSOL-WRS and FSOL + top-$K$ achieved a statistical tie ($p=0.10$). Note (per one-page PDF), WAT always improved stability where other methods did not.

Nonetheless, aggregating all of the aforementioned results and analyses, it is clear that the probabilistic WRS-augmented training method is superior to the deterministic top-$K$ method, with minimal additional computational cost compared to the naive base algorithm.

In addition, the use of formal notation in the paper is in my opinion quite sloppy in parts. The technical material feels rushed, and makes it difficult for readers/reviewers to effectively parse the procedure being proposed. I will provide some concrete examples in the next field.

Thank you for taking your time to provide us with so many helpful revisions. We will address each of these one-by-one below with proposed line edits:

• Abstract: We will replace K with "a subset of intermediate weight vectors" as recommended.
• We will update the last sentence of our abstract to "We demonstrate our WRS approach for binary linear classification with the Passive-Aggressive..."
• We will use the correct symbol '\top' for transpose.
• We will motivate better that we aim to take an ensemble of online models into a single final model and explain how sampling from models with high survival times is a good proxy metric for this. We will then discuss that WRS is a linear-time, low-memory method to efficiently accomplish this.
• Agreed, we will fix to $\boldsymbol{w}_{t+1}$
• Thank you for catching our oversight, we will change $h$ to $\boldsymbol{w}$ and bold x
• $\mathcal{J}$ was the reservoir in the theory, but to be consistent with our Algo block, we will change it and clarify that $\mathcal{R}$ is the reservoir, and we will "collect a model $\boldsymbol{w}^{(j)}$ only when it is first updated, into $\mathcal{R}$".
• Algo 1, line 15: Thank you for catching our typo. The correct symbol should be $b^*$, rather than $w_t$.
• Algo 1, line 16: We agree that using $T$ creates notational clash. We will instead use $\tau$ for threshold.
• Algorithm 1, line 19: Thank you for this catch. We will clarify when initializing our data structures $\mathcal{R}, \mathbf{b}, \mathbf{k}$ (all of which are size-$K$ arrays) that the elements in $\mathcal{R}, \mathbf{b},$ and $\mathbf{k}$ are paired with each other, so that when we remove an element in $\mathcal{R}$, the corresponding elements in $\mathbf{b}$ and $\mathbf{k}$ are removed as well.
• Algorithm 1, lines 27 and 29: Agreed, we will fix the notational overloading by clarifying that $\mathcal{R}$ contains candidate solution vectors $\mathcal{R}[1], \mathcal{R}[2], \dots \mathcal{R}[K]$, with each $\mathcal{R}[i] \in \mathbb{R}^D$. Similarly, $\mathbf{b}$ contains scalar values $b[1], \dots, b[K]$, and $\mathbf{k}$ contains scalar values $k[1], \dots, k[K]$. Then, we would revise Lines 16-19 of Algorithm 1 to say that $\tau = \min\_{j \in \{ 1, \dots, K\}} b[j]$, with corresponding index $i = \text{arg}\min\_{j \in \{ 1, \dots, K\}} b[j]$. Then if $k^\* > \tau$ (assuming the reservoir is full), we replace $\mathcal{R}[i]$ with our current candidate solution $\mathbf{w}$, replace $b[i]$ with $b^\*$, and replace $k[i]$ with $k^\*$. Line 29 now becomes $\mathbf{w}\_{\text{WRS}} \leftarrow \sum_{j=1}^K b[j] \mathcal{R}[j]$.

Algorithm 1: when WS is "Standard", then $b^\*$ is updated, but under AS as "Simple Average," plays no subsequent role; is this correct?

Yes, this is correct because we are just taking a simple average of the candidate solutions in the reservoir (i.e., equal weightings of $\frac{1}{K}$ on each member of the reservoir). However, we clarify that entry into the reservoir, for both AS as "Simple Average" or "Weighted Average," is still based on the candidate solutions' (potentially exponentiated) passive steps. The difference between "Simple Average" and "Weighted Average" is how we form our ensemble solution $\mathbf{w}\_{\text{WRS}}$ from the $K$ vectors in our reservoir --- membership into the reservoir is still based on the (potentially exponentiated) number of passive steps. For discussion on the meaningfulness of using this passive-step count based approach vs. simply taking the most recent $K$ vectors, for example, please see the "Additional Wrappers" discussion in the Author Rebuttal. Nonetheless, with the notational correction on Line 15, the critical $k^\*$ check should now be fully-defined.

Finally, considering the fact that there is a massive literature on taking averages of candidates from iterative learning procedures, I think many readers will find it troubling that the empirical investigations are completely inward-facing, i.e., they simply evaluate the base algorithms and the proposed wrapper under different settings, and do not treat other alternative averaging strategies which are far more generally applicable (e.g., averaging $K$ most recent candidates, downweighting over time, using so-called "anytime" sub-routines, and so forth).

We agree that this is a very important point. We will also cite prior work on online-to-batch averaging (references in response to v2Wj). Please see ``Additional Wrappers" in our Author Rebuttal for further additional base-methods and wrapper alternatives, showing our method works against a wider spectrum of alternatives.

The theoretical analysis assumes i.i.d. condition, which is not consistent with the motivation that individual outliers exist and do harm to PA classifier.

Our method falls in a category of techniques that convert algorithms to a low-risk model which generalizes well to unseen data. In order to bound the risk in such manner, there has to be an assumption on the distribution which is usually an arbitrary i.i.d. data distribution. We do wish to highlight though that even under the i.i.d. model, the base passive-aggressive algorithms are often unstable because their update steps can be too aggressive or change the angle of the separating hyperplane too much, so to speak. Also, because the distribution is arbitrary, it can be a mixture distribution with a fraction of "outlier" points, and our theory still holds. The reviewer does bring up an interesting point, which is investigating underlying data distributions which explicitly contain outliers -- to our knowledge this hasn't been studied in the context of online-to-batch conversion and would be interesting future work.

Please also see the response to reviewer v2Wj and the one-page PDF; we have added a new theory that strengthens the manuscript.

I wonder whether the online gradient descent with momentum can perform well, because it can also be seen as a special ensemble method. I suggest authors add this method for comparison.

Thank you for your suggestion. Please see our ``Additional Base Models" response in the Author Rebuttal, where we investigate Stochastic Gradient Descent with Momentum alongside two similar methods Truncated Gradient Descent and AdaGrad. We also investigate the effectiveness of adapting WRS-Augmented Training to these non-passive aggressive base methods.

We are very glad that we were able to address your questions and are grateful for the raised score and vote of confidence. Please let us know if any other questions or feedback arise. Thank you so much!

We appreciate the reviewer encouraging us to clarify the candidate solution selection procedure for our WRS-Augmented Training (WAT), revisiting our discussion in Section 3 and, in particular, Algorithm 1. The main idea is that WAT is a wrapper that builds around an existing passive-aggressive algorithm like PAC or FSOL.

Notationally, let $\mathbf{w}\_t$ be the intermediate candidate solution retained by the base model (e.g., PAC) at timestep $t$. Given PAC's passive-aggressive nature, PAC only updates the intermediate candidate solution at timestep $t$ if it makes a mistake (i.e., incurs nonzero hinge-loss) on the current observation $\mathbf{x}\_t$ in our data stream.

Suppose PAC's intermediate candidate solution made a mistake at time $t$. Then, imagine that the base PAC algorithm's intermediate candidate solution did not make any mistakes at timesteps $t+1, t+2, \dots, t+PS$, and only made its next mistake at time $t+PS+1$ (where $PS$ is short for passive steps). By definition of passive aggressive, we know that $\mathbf{w}\_{t+1} = \mathbf{w}\_{t+2} = \dots = \mathbf{w}\_{t+PS}$ (because no update was made). However, at time $t+PS+1$, the base PAC algorithm makes an update to its intermediate candidate solution using the PAC update rule: $\mathbf{w}\_{t+PS+1} \neq \mathbf{w}\_{t+PS}$. At this timestep $t+PS+1$, we say that our outgoing intermediate candidate solution $\mathbf{w}\_{t+PS}$ had survived $PS$ passive timesteps without making a mistake and requiring an aggressive update. Then, at timestep $t+PS+1$, we will insert $\mathbf{w}\_{t+PS}$ into our reservoir with a probability that is a function of $PS$ --- the larger $PS$ is, the more likely $\mathbf{w}\_{t+PS}$ is to enter our reservoir (see Lines 10-19 in Algorithm 1 for specific schemes). If $\mathbf{w}\_{t+PS}$ enters our reservoir, to maintain our reservoir of size $K$ (with $K$ predetermined), we will need to remove an older member of the reservoir (please see Lines 16-18 of Algorithm 1).

While FSOL-WRS shows statistically significant improvements in final test accuracy, PAC-WRS does not consistently show the same level of improvement.

This question has helped us realize we did not fully convey the utility of WRS. The manuscript demonstrates same-or-improved accuracy (ROP, introduced in Section 4) clearly but does not as well emphasize the stability of the test accuracy over time. Having equal accuracy and more stability would be an improvement, and we deliver equal or better accuracy (depending on base-method) plus stability.

We now also include a new metric, which we call Worst-Case Performance Difference (WPD). Intuitively, we would also like to know what is the worst possible decrease in test accuracy performance between consecutive observations. For example, a model that has a demonstrated risk of dropping 50% in test accuracy performance between consecutive online observations is not a safe model for deployment. We define WPD to be the minimum (i.e., most negative) percent change in test set accuracy between consecutive observations in the second half of the epoch (as early iterations have natural asperity, and 1/2 epoch is well into ``this should be usable now'' territory).

On WPD, we find that both PAC-WRS and FSOL-WRS uniformly outperform PAC and FSOL, respectively, on all 16 of 16 datasets, averaged across 5 trials, with statistically-significant $p$-values of $< 0.0005$. In particular, on Avazu (App), PAC-WRS achieves a worst-case performance decrease of only $0.0073$ percent, compared to base PAC seeing a worst-case performance decrease of $59.57$ percent. For another example, on News20, the WPD values for PAC-WRS and base PAC are $0.137$ percent and $33.53$ percent, respectively. Please find the WPD values for PAC/FSOL and PAC/FSOL-WRS in the table below:

The main takeaway with our WPD analyses is that PAC-WRS and FSOL-WRS are overwhelmingly and statistically-significantly effective at preventing worst-case decreases in test set accuracy compared to their base algorithms. Combine with already existing results that WAT has same-or-improved accuracy, WAT essentially comes with no cost beyond a minor amount of additional computation.

Can the authors provide more detailed explanations on how intermediate weight vectors are selected and maintained in the reservoir?

See additional comment due to space limitation.

Although minimal, there is still an additional memory and computational overhead associated with managing the reservoir of candidate solutions.

Yes, we agree that there is still a minimal cost towards managing the candidate solutions in the reservoir. However, we invite the reviewer to view our ``Additional Wrappers" response in the Author Rebuttal, where we show that compared to other averaging schemes like moving average and exponential average, our WRS-augmented training mechanism wins decisively on both efficacy and computational cost.

[Can the authors] discuss the impact of different reservoir sizes on the algorithm's performance?

On the role of reservoir size $K$, echoing our presentations and figures in Sections 4.1 - 4.3, in general, the bigger $K$ is the better in terms of performance. Larger values of $K$ (we tried $K=1, 4, 16, 64$) are associated with both higher mean final test accuracies and stronger mean Relative Oracle Performances, with better consistency across 5x trials. However, from Figure 3 in the main text and similar figures in Appendix D, we do see that there are diminishing returns to increasing $K$ past a certain point. Of course, there is also a slightly increased storage cost from needing to store more vectors in our reservoir, though this cost is not significant. In general, based on our results across the 16 datasets, we recommend $K=64$ as a starting point.

I think more compared baselines are needed, such as ADAGRAD or Truncated Gradient.

Thank you for your suggestion. Please see our ``Additional Base Models" response in the Author Rebuttal, where we investigate AdaGrad and Truncated Gradient Descent alongside Stochastic Gradient Descent with Momentum, as well. We also investigate the effectiveness of adapting WRS-Augmented Training to these non-passive aggressive base methods.

Also, the comparison with the previous baselines is not very well motivated.

The goal of our proposed method, WRS-Augmented Training (WAT), is to stabilize the test accuracy over time of a passive-aggressive base model, like PAC or FSOL, which originally can have massive fluctuations in test accuracy over time (see Figure 1 in the main text). Applying WAT to PAC and FSOL as a lightweight wrapper yields two new models PAC-WRS and FSOL-WRS. Our WAT is considered successful if the resultant PAC-WRS and FSOL-WRS output test accuracies over time that are much stabler than that of their base methods, PAC and FSOL, respectively. While the choices of test accuracy and (preservation of) sparsity are standard metrics in online binary classification, to directly quantify how much PAC/FSOL-WRS stabilize test accuracy relative to their base algorithms PAC/FSOL, we introduced a new metric, Relative Oracle Performance (ROP). Specifically, ROP measures the difference between the cumulative maximum test accuracy of the base method PAC/FSOL versus that of PAC/FSOL-WRS, averaged across timepoints $t$. The motivation with ROP is that if a method has very stable test accuracy over time (with minimal fluctuations), then its test accuracy curve should look very similar to its cumulative maximum test accuracy curve, implying an ROP very close to $0$, if not negative. It follows that we use PAC and FSOL as our main baselines, with the discussed metrics, for comparison in the main text. If accepted, we will add the above clarification to our camera-ready manuscript.

I believe that the theory is the weaker part of this paper.

We appreciate the reviewer pointing out the difference in our underlying setting compared to the PA model. Our method does fall in the category of online-to-batch conversion techniques like prior works [1-3]: We aim to take an online algorithm with known regret bounds on a fixed sequence of data and find a stable transformation of the model sequence to a low-risk final model in the iid setting. We believe this was not clearly conveyed and will more clearly differentiate our setting.

We also agree with the reviewer's request for bounds showing the gap between $R\_D(w\_T)$ and $R\_D(w*)$ goes to 0 as T -> infinity.

We have developed a new risk bound for our method, which is given in the PDF (Theorem 1). As can be inferred from the bound, the deviation in risk of our final model from the optimal risk shrinks over time with high probability. This is guaranteed to hold if the reservoir size $K_T$ grows at any rate over time. This is supported experimentally since large reservoir sizes (e.g. 64) are especially effective on our large datasets.

We sketch the proof steps and sequence of bounds/inequalities that give the new theorem below. A more detailed and well formatted (OpenReview doesn't support it) will be added to the camera-ready copy. First, using an indexing trick, we express the weighted reservoir model as a weighted average of the sequence of models, i.e. $w\_{wrs}$ = WAvg($w\_t$), which has cumulative loss $M\_t$.

(1) risk($w\_{wrs}$) <= WAvg(risk($w\_t$)) (Jensen's inequality)

(2) WAvg(risk($w\_t$)) $\leq M\_t$ + error1 w.h.p. (adapting a Bernstein's maximal inequality for martingales, e.g. [2], [3]). error1 here refers to the $\sqrt{2C\log(2T/\delta) M_T / (T K_T s)} + 7C \log(2T/\delta) / (K_T s)$ terms

(3) $M\_t \leq$ regret($w^*$) + error2 for any (optimal) $w^*$ (applying PA algo-specific regret rates). Here the error2 is $r(T)/T$, with many online algos achieving either $r(T) = O(\sqrt{T})$ or $O(1)$.

(4) regret($w^*$) $\leq$ risk($w^*$) + error3 w.h.p. (Hoeffding bound). The error3 term is the $C \sqrt{ \log(2/\delta) / (2T)}$ term

Combining the steps and using union bound gives our result.

Specific theory qs:

Definition of $r_m$: We will clarify our notation. Our $R_D(w^*)$ depends on the observed sequence, so it's a random variable, while $r_m$ is an instance-independent value, which we need for the bound to make sense. $r_m^K$ is $r_m$ raised to the power $K$. We will write $(r_m)^K$ instead to clarify that.

Thm 2 assumptions: It is true that strong assumptions were needed to make any reasonable bounds for a finite-size reservoir, because we are analyzing an inverse problem. To clarify, if we know the underlying risks of the sequence, we can compute exact probabilities on the survival distributions, but we can't reason backwards from observed survivals to risks without placing either (1) strong assumptions or (2) Bayesian priors on what the underlying risks are.

Our new theorem (see PDF) instead applies martingale concentration inequalities to perform the inverse inference in a large-sample setting, and thus we believe it is a stronger, more intuitive result which addresses the reviewer's concerns.

$R(h)$, loss used: Thank you for pointing that out, we will revise to use $R\_D$, which refers to risk under the 0-1 loss only. When the hinge loss is used (which was only mentioned after Thm 2), we will specifically use $R\_D^h$.

[1] Cesa-Bianchi N, Conconi A, Gentile C. "On the generalization ability of on-line learning algorithms." (2004).

[2] Cesa-Bianchi N, Claudio G. "Improved risk tail bounds for on-line algorithms." (2008).

[3] Dekel O. "From online to batch learning with cutoff-averaging." (2008).

Suggestions: I would formally define concepts outside of related work (e.g, sparsity in line 73-74).

We agree with the reviewer, and will move the formal definitions for sparsity and test accuracy into the second paragraph of the Introduction for our camera-ready manuscript. We propose the following insertion: ``In this paper, for full clarity, we define test accuracy as the proportion of points classified correctly (with no margin considerations involved) in a hold-out test set, operationally fixed to be $30$ percent of the relevant full dataset. We define sparsity as the proportion of entries in a vector that are zeroes."

Re: (2b).

We will clarify that the regret in our theorem is actually that of the underlying online algorithm (e.g. PAC/FSOL) used in our wrapper. In a similar manner to other online-to-batch ensembles, our method accepts an online algorithm as the base, with a known regret bound, and extracts an ensemble model with accompanying risk bound as a function of the original regret bound.

To make this more evident we can highlight an intermediate result first: $R_D(w_{wrs}) \leq M_T/T + \sqrt{2C\log(2T/\delta) M_T / (TK_T s)} + 7C\log(2T/\delta)/(K_T s)$ where $M_T$ is the actual regret bound of PA/FSOL/etc. (and give our original theorem after). This form is more aligned with prior works such as (Cesa-Bianchi et al. 2008), (Dekel 2009).

We will also provide the actual regret bounds for the underlying online algos (e.g. PA/FSOL/AdaGrad) papers for the reader as a table in our updated paper. For example, FSOL has $M_T = O(\sqrt{T})$ disregarding constants (Thm 2 of their paper).

*Re: log(T/delta)/(K_T s) term: * Here $s$ is the minimal survival time of the models within the reservoir. We clarify that $K_T$ increasing is a sufficient but not necessary condition for the error to shrink to 0. Another sufficient condition is $s$ growing larger over time, and this is likely because the online learning solutions naturally improve over time. We agree that ideally we would enjoy seeing a term of $T$ in the denominator, but note that since the other error terms have $O(1/\sqrt{T})$, a growth rate of product $K_T s \propto O(\sqrt{T})$ is sufficient to have a convergence rate not worse than the other terms.

We thank the reviewer for their detailed feedback on our presentation and theory. We reviewed our exposition and agree that we were imprecise in our writing in those areas. We have fixed the writing as follows:

Re: (1). We clarify that the underlying online algorithms bound regret rather than risk. Lines 4-5 (abstract) now say "While such algorithms enjoy low theoretical regret, in real-world deployment ... "

Section 2.1: "The goal is that as $t\to\infty$, $\boldsymbol{w}_t$ will enjoy low cumulative regret."

To resolve the disconnect, we now clarify that there are two categories of prior work: (i) online learning algorithms such as PAC/FSOL/AdaGrad which bound regret for any sequence of points, and (ii) online-to-batch conversion from a sequence of online solutions to a final model, with bounded risk of the final model under the i.i.d. assumption. We clarify that our work falls into the second category, as our method wraps any underlying online learning method from (i) to produce a stable ensemble. Like other works in (ii), our goal is to achieve a low-risk final model which generalizes to unseen examples.

We also point out that although the online learning methods in (i) give regret bounds, at least some of them do ultimately care about generalization. For example, the FSOL and AdaGrad papers evaluate the final model on a train-test split over real datasets. This indicates the generalization/iid use case is of interest as an end goal even in those original papers! In addition numerous applied works have directly used PA algorithms for out-of-sample prediction, e.g. [1], [2].

[1] Kiritchenko et al. NRC-Canada-2014: Detecting aspects and sentiment in customer reviews

[2] Petrovic et al. RT to Win! Predicting Message Propagation in Twitter

We have expanded the above discussion with more references into a new subsection in our Related Works.

Furthermore, in the abstract, we now say: "We design a weighted reservoir sampling (WRS) approach to obtain a stable ensemble model from the sequence of solutions without requiring additional [...]"

Re: (2.a). We will restructure our theory section and clarify that our original Thms 1/2 are finite-sample bounds to assess the validity of our approach, i.e. to demonstrate that the approach of using high survival as a proxy measure is reasonable, rather than to provide learning/generalization bounds. For the latter (i.i.d. setting) we will rely on and emphasize the new theorem in the PDF.

As in our previous response we do acknowledge that assumptions are needed in Thm 2 because it's an inverse problem with little "evidence". However these assumptions are actually readily satisfied, and making them clearer below further strengthens our work -- thank you.

$\varepsilon>0$ can be any small number that satisfies a partition within the reservoir separating "good" from "bad" models -- e.g. $\varepsilon = (\max_k R_k' - r_m) / 4$ works. For demonstration, suppose the underlying risks of the $K$ models in the reservoir range from 0.1 to 0.3, with 0.1 being the best risk $r_m$. Then $\varepsilon = 0.05$. $\mathcal{J}_g$ then contains the models with risks in $[0.1, 0.15]$ and $\mathcal{J}_b$ contains those with risks in $(0.15, 0.3]$. The only time this isn't satisfied for any $\varepsilon$ is if one of the partitions always ends up empty, which only happens if all the $K$ models have the same risk, a highly unlikely scenario where it is obvious that an ensemble isn't needed.

We have added the above explanation to the paragraph introducing Theorem 2.

Re: R_D(w^*). As suggested, we will change the notation to be consistent so that $w^*$ is always the optimal classifier w.r.t. distribution D. We will use $\tilde{w}$ instead for the lowest-risk model actually contained in the reservoir.

See next comment for reply to (2b).

Thank you for this additional review. We know it is a bit much to add your review and then see so much other content in reviews/rebuttals, but we are encouraged by the significant overlap in your review and the other positive reviews we have received.

Limited Applicability:

Other reviews have brought this concern up as well, and we have worked to remediate it. If you look at the all-author rebuttal (and our response to We6T and NvJo), we have added three additional base-algorithms to stabilize. These algorithms are not technically passive-aggressive either, showing our theory and method empirically generalizes and that non-PA algorithms can be adapted to use with WAT. Thus, our method is shown to stabilize the PA, FSOL, Truncated Gradient Descent, SGD + Momentum, and AdaGrad based learning methods.

I would like to see if there are more detailed analysis or comparisons with baseline methods in terms of computational efficiency.

In addition to the added baselines, we also added other alternative "wrapper" algorithms. This includes the simple moving average and the exponentially weighted average baselines (see "Additional Wrappers" in the Author Rebuttal) and the top-K ablation (see our rebuttal + comment to Reviewer NvJo). In summary, these other wrapper alternatives can help sometimes, but WAT always equals or outperforms them in test accuracy, whereas the others each have a few datasets on which they degrade. Moreover, compared to the well-established moving average and exponentially-weighted average methods, as the datasets get larger, WAT is the fastest to run by up to 10x as it does extra work on a less frequent (stochastic) basis, and that extra work is computationally very cheap. Again, see the all-author rebuttal for a table with the speedup factors.

WAT only performs additional work when an error is made. This additional work entails a) the computation of a $k^*$ key via sampling a single uniform random variable and 3 floating point operations (extremely cheap, line 15 of Algorithm 1) and b) finding the smallest value/corresponding index in a size-$K$ array (also very cheap, with $K=64$ being the upper limit in our testing). The weight vector+bias are only added to the reservoir (with another vector+bias pair being replaced) if the stochastic reservoir insertion check (also very cheap) is satisfied (lines 17-19 of Algorithm 1). To be precise, if the reservoir is updated, the size-$K$ arrays $\mathbf{b}$ and $\mathbf{k}$ also each get updated at one index (very cheap). That is all the extra work required during the training process. All operations are extremely cheap, and the more accurate an algorithm is, the cheaper it gets as the reservoir insertion check becomes less frequent.

Assumption on Data Distribution

We thank the reviewer for this interesting point and will add more discussion in the paper. The use of the IID assumption in our theoretical analysis is a requirement to discuss the risk/generalization error, and is aligned with prior work on converting online algorithms to ensemble models. See also the all-author rebuttal for a new theorem that provides a conversion from the original base-algorithm specific regret $r(T)$ into the risk bound for our WRS (proof sketch in reply to v2Wj due to character limits). While more empirical exploration of concept drift would be valuable, we believe it extends beyond the scope of the work and our time remaining in the rebuttal period.

We appreciate your review again, and we know there is a lot of other reviewer/rebuttal content to process at the last minute. We hope your positive review, which aligns well with our other positive and constructive reviews, is a good indication of the value of our work and that others will find interest/inspiration from our unique approach to a reservoir of weight vectors.