Stabilizing Linear Passive-Aggressive Online Learning with Weighted Reservoir Sampling
Authors: Skyler Wu
Fred Lu
Edward Raff
James Holt
Venue: NeurIPS 2024 poster (2024)
Keywords: online learning
passive aggressive
weighted reservoir sampling
stability
Primary area: online_learning
TL;DR: We combine weighted reservoir sampling with passive-aggressive online algorithms to dramatically mitigate test accuracy fluctuations.

Abstract: Online learning methods, like the seminal Passive-Aggressive (PA) classifier, are still highly effective for high-dimensional streaming data, out-of-core processing, and other throughput-sensitive applications. Many such algorithms rely on fast adaptation to individual errors as a key to their convergence. While such algorithms enjoy low theoretical regret, in real-world deployment they can be sensitive to individual outliers that cause the algorithm to over-correct. When such outliers occur at the end of the data stream, this can cause the final solution to have unexpectedly low accuracy. We design a weighted reservoir sampling (WRS) approach to obtain a stable ensemble model from the sequence of solutions without requiring additional passes over the data, hold-out sets, or a growing amount of memory. Our key insight is that good solutions tend to be error-free for more iterations than bad solutions, and thus, the number of passive rounds provides an estimate of a solution's relative quality. Our reservoir thus contains $K$ previous intermediate weight vectors with high survival times. We demonstrate our WRS approach on the Passive-Aggressive Classifier (PAC) and First-Order Sparse Online Learning (FSOL), where our method consistently and significantly outperforms the unmodified approach. We show that the risk of the ensemble classifier is bounded with respect to the regret of the underlying online learning method.

Stabilizing Linear Passive-Aggressive Online Learning with Weighted Reservoir Sampling
Skyler Wu Booz Allen Hamilton
Fred Lu Booz Allen Hamilton University of Maryland, Baltimore County lu ww.ffeddbahcoom
Harvard University
Stanford University com
Edward Raff
James Holt
Booz Allen Hamilton
Laboratory for Physical Sciences holt@lps. umd. edu
University Maryland, Baltimore County raff edward@bah. com com
Abstract
Online learning methods, like the seminal Pussive-Agreesive (PA) classifier, are still highly effective for high-dimensional streaming data, out-of-core processing, and other throughput-sensitive applications. Many such algorithms rely fast adaptation to individual emors as a key their convergence. While such algorithms enjoy low theoretical regret, in real-world deployment they can be sensitive individual outliers that cause the algorithm to over-correct. When such outliers occur at the end of the data stream, this can cause the final solution to have unexpectedly low accuracy. We design a weighted reservoir sampling (WRS) approach to obtain stable ensemble model from the sequence of solutions without requiring additional passes over the data, hold-out sets, or a growing amount memory. Our key insight is that good solutions tend to be error-free for more iterations than bad solutions, and thus, the number of passive rounds provides an estimate of solution's 's relative quality. Our reservoir thus contains K previous intermediate weight vectors with high survival times. We demonstrate our WRS approach on the Passive-Aggressing Classifier (PAC) and First-Order Sparse Online Learning (FSOL), where our method consistently and significantly outperforms the unmodified approach. We show that the risk of the ensemble classifier is bounded with respect to the regret of the underlying online learning method.
1 Introduction
Online learning algorithms are especially attractive when working with high-volume and high- dimensional streaming data, out-of-core processing, and other dtroughput-sensitive applications [I] For example, the seminal Vowpal Wabbit uses importance-weighted online learning algorithms 2 reach high quality solutions quickly, with optional second pass using LBFGGS refine the solution. The MOA library still uses the Pegasos algorithm as its linear classifier (3] Most relevantly, online learning algorithms are particularly appealing for binary classification tasks, such web spam classification [[] Such algorithms often enjoy fast theoretical convergence rates due to their fast adaptation to errors on individual data points, as opposed to batch or offline learning.
However, real-world deployment, online algorithms can be very sensitive to noisy observations in the data stream and over-correct, resulting in out-of-sample performance dropping precipi- tously between timesteps. Indeed, in many cases (see Figure I), an online learning algorithm might
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Avazu (App)
News20
1.0
0.9
0.8
PAC
0.7
0.6
PAC
0.6
PAC
0.5
Oracle PAC-WRS
Oracle
WRC-WRS
0.4
0.4
0.0
0.4
0.6
1.0
5000
10000
0.9
0.9
0.8
FSOL
0.7
0.7
FSOL
FSOL
Oracle
Oracle
0.5
F50L-WO
FSOL-WRS
0.0
0.2
0.4
0.6
0.8
1.0
0
5000 10000
Test accuracies (y-axis) over timestep (r-axis) for PAC-WRS and FSOL -WRS on Avazu (App) and News20. Light grey lines: test accuracies of the baseline methods - PAC or FSOL at each timestep. Solid black lines: test accuracies of the "oracle" models, computed as the cumulative maximum of the baselines. Solid blue lines: test accuracies of WRS-enhanced models. Note massive fluctuations of grey lines and stability of blue lines. All variants shown are using standard sampling weights for WRS, with sample-averaging
Figure 1:
achieve over 90% test accuracy after a given timestep, but then see its test accuracy drop by -30% after over-correcting on the next observation in the data stream. In many real-world settings. it may be infeasible computationally or memory-wist to maintain a hold-out evaluation set to select the solutions learned by our online algorithm. It may also be practically infeasible to train our classifier over multiple passes a given dataset or when online algorithms are used for "any-time" ready predictions.
In this paper, we introduce a weighted reservoir sampling (WRS) based approach that dramatically mitigates the aforementioned accuracy fluctuations. Our proposed method, WRS-Augmented Training (WAT), neither requires hold-out evaluation set nor additional passes over the training data. Most importantly, WAT can be used to stabilize any passive-aggressive online learning algorithm. We demonstrate the promise of our WAT method on the Passive Aggressive Classifier (PAC) 5 and First-Order Sparse Online Learning (FSOL) [ methods creating two new methods PAC-WRS and ESOL-WRS. Strikingly, across 16 benchmark datasets, WAT is able to mitigate test accuracy fluctuations in all 16 datasets on FSOL and 14 datasets PAC. To analyze the theoretical effectiveness of our method, we situate our approach in the online-to-batch conversion literature, enabling us to obtain generalization bounds on i.i.d. data streams.
2 Review of related work
Our work is motivated in part by a real-world need malware detection (6, in which large datasets make online methods particularly attractive 7 g, and a naturally noisy labeling process inhibits standard passive-aggressive methods 12 in Appendix
We show results for the EMBER malware benchmark
Online learning. In online learning for linear binary classification, one maintains a solution vector W, E R where D is the dimensionality of our data points (usually quite large), and represents the timestep. At each timestep f, we observe a single observation (æ,, 91) from high-throughput data stream, with feature vector 2; R and class label yı (+11-11) Given (æ,, yt), online learning algorithm will make a minor (potentially no effect) update to w, to output W before receiving the next (I1+1, 9t+1) 1) in the data stream. The classification rule using w, any test point x" is simply 8" = sign(w, x²). The goal is that as t + oo, the sequence of w, will enjoy

---

low cumulative loss. Towards this end, many online learning algorithms with various update rules have been proposed in the literature, including the AggressAeeees Classifier (PAC) [5], the Adaptive Regularization of Weight Vectors (AROW) methods [13 and the Adaptive Subgradient method (ADAGRAD) [4]. Some online learning algorithms have also been designed to specifically learn sparse solutions for we (proportion of zero entries), such as Truncated Gradient method [15], Stochastic MIrror Descent Algorithm made Sparse method (SMIDAS) [16], Regularized Dual Averaging (RDA) method 177, and First-Order and Second- ierorr Sparse Online Learning methods (FSOL and SSOL) M. In general, these sparsity-inducing methods are powered by some combination of solution truncation and LI norm minimization.
Passive-aggressive online learning. Within the family of online learning algorithms, passive- aggressive algorithm is one whose update rule makes no update to w, if (æt, Mr)) is classified correctly with sufficient margin. That is, we passively leave W++1 W,- If a margin error occurs, we aggressively update Wr+1 such that the error is fully correct (though a regularization penalty C will tamper the degree of aggressiveness). Usually, correct classification with sufficient margin defined using the hinge loss & - the algorithm remains passive at timestep t if & (Wai (æe, yr)) max (1 y, Zt. 0) O. Next, we introduce the two passive-aggressive algorithms that we will use to test our WRS- Augmented Training method.
ggresveeAgressvvee Classifier (PAC). Introduced by Crammer et al., PAC is actually a family of three algorithms: PA, PA-I, and PA-II [5] The hase PA algorithm update rule seeks to solve the following constrained optimization problem:
1 2 [|w w s.t. l(w; (æee Me)) 0.
Wx+1 arg min
WERD
Because of the hard constraint of forcing Wi+1 to satisfy E(w; (I),, = 0, the optimization is particularly vulnerable noisy data. As such, Crammer et al. introduce new constrained optimization function with a slackness hyperparameter Cerr to allow for some residual hinge loss and induce less aggressive, but presumably more stable updates:
Wx+1 = arg min-
2 fll - well - Cerre" s.t. E(W; (wr, Se and 2 0, WERD
where setting m = corresponds to PA-I and m 2 to PA-II. From initial testing, PA-I and PA-II performed very similarly, with a slight edge to PA-II. As such, for this paper, we will focus on PA-II, which performs the following closed-form update when in aggressive mode (5) Wr41
((w.( Yr For the remainder of this paper, "PAC" will refer to PA-II.
W. +
[< 2 Toaer
Orrtt Sparse Online Learning (FSOL). Introduced by Zhao et al. M. FSOL is passive- aggressive algorithm which attempts to find sparse solutions for We. Governed by a learning rate and sparsity parameter X. FSOL keeps track of two vectors O,, w. E RDD and performs the following update rules when in aggressive mode M:
0i+1= = 0 + my W141 sign(0:41) 11.411 -
where Ae ya and [w]+ takes the maximum of each element in v and 0. Zhao et al. note that the above update rules are identical to that of Xiao's RDA method with soft 1-norm regularization 17
Weighted Reservoir Sampling (WRS). Suppose we have collection of items V = (UI,..., J with corresponding nonnegative weights w WT. Our goal is to collect a size-K weighted random sample from V in one pass (imagine this process is indexed by time), where the population size T [V] is potentially unknown. Introduced by Efraimidis and Spirakis [4), weighted random sampling with a reservoir, which we shorten to weighted reservoir sampling (WRS), is an algorithm that allows us to collect such a size-K K weighted random sample under the aforementioned conditions. are making one pass through the items in V. at each timestep t, maintain and update a reservoir- - a temporary storage unit with a maximum capacity of K items, with each item in the reservoir potential candidate for our final size-K K sample. At time T, the K items that are currently in the reservoir will constitute our sample of K. We invite the interested reader to look at Algorithm A in [ for specific details.
Specifically,
Online-to-batch conversion. Online learning algorithms such as PAC generally do not impose any restrictions on the distribution of the training data sequence. Their regret bounds aim to control
3

---

the cumulative loss Mr of the algorithm over any sequence of data, compared with a minimal-loss fixed model w: regr Ei= (( - - (() = MM Ei= {(w;; 21). When using fixed model to classify unseen data, we need to impose an i.id. assumption on the data stream in order to measure the risk, or expected generalization error, of the model. Note that the distribution
DD itself is arbitrary and can still permit outliers or mixtures. Then the population risk is defined as Rp(w)= == [Ez=:(((w;;))) 2)].
To theoretically describe our algorithm, we leverage work on online-to-batch conversion, which takes an online algorithm with known regret bounds on an i.i.d. sequence of data and extracts a stable final model with low risk, For example, in the online perceptron algorithm, earlier work studied the pocker approach, which selects the longest-surviving model in the sequence as the final model [18 [9]. Other well-known approaches use the uniform average of the whole model sequence or the best-performing model over validation set (20].
As will be seen, our method generalizes these approaches to utilize multiple long-surving models as an ensemble model. Furthermore, we will introduce novel improvements, including a limited- size reservoir with probabilistic sampling. The risk bounds for our WAT model leverage improved techniques from [21 22 Our experimental results also demonstrate that our novel conversion technique outperforms prior baselines (see Appendix D)
3 Our method: WRS-Augmented Training (WAT)
In extreme. if a candidate solution w, from a passive-aggressive algorithm had perfect clas- sification with sufficient margin on any given data point, then the subsequent number of passive steps taken after time i (i.e., number of timesteps that our algorithm is in passive mode before going aggressive again) would be infinite. In the other extreme, if a candidate solution w. had extremely low performance, then our passive-aggressive algorithm is likely go aggressive very soon after time f, implying a very small subsequent number of passive steps after time t. In short, our key insight that high-performing solutions Wr tend to be error-free for more iterations than low-performing solutions. As such, the subsequent number of passive steps taken after the formation of w, provides an estimate of wy's 's relative quality (i.e., test accuracy).
However, we do not want to take the intermediate solution we that had the most passive updates as this, too, can be noise (and luck) sensitive. Idcally, we would like to sample from the merging distribution of w, as they occur, and take an average of those solutions to obtain a singular, highly robust, solution vector that performs well with little variance. But, we do not wish to store all w, due to intractability.
Putting these thoughts together, our WRg-Augeented Training (WAT) method functions follows. Given a base passive-aggressive algorithm (e.g.. PAC or FSOL), we will run said algorithm through our data stream {( (ee,,,))) 1=)) normal, but keep a size-K K reservoir of promising candidate solutions. The reservoir approach allows us to run through our data stream and collect a weighted random sample of candidate solutions of Ki weighted by their subsequent number of passive steps and without storing all intermediate solutions.
Naturally, this setup is suited for Efraimidis and Spirakis's WRS algorithm. Procedurally, every timestep that our algorithm goes aggressive, we obtain new active candidate solution. Right before we apply our aggressive mode update rule, we will add the outgoing candidate solution to our size- reservoir (and remove current resident of the reservoir, if necessary) following the steps of the WRS algorithm. At any timestep I, we can form an ensemble solution wwrs by taking an average of the candidate solutions currently in our reservoir. Hopefully, at any timestep I, WwRs will have more stable test performance than the current active candidate solution W..
3.1
WAT variants
We will experiment with a few additional variants of the WAT method. First, instead of weighting using the subsequent number of passive steps (which we denote as standard weights), what if we weight using the exponentiated subsequent number of passive steps (which we denote as exponential weights)? The idea with exponential weights is that it is closer in practice to deterministically picking the candidate solutions with the largest number of subsequent passive steps, while still maintaining some stochasticity - i.c., "greedier" policy. Second, when constructing ensemble solution
4

---

Algorithm WRS-Augmented Training (WAT)
Input: w initial solution vector, {(1,, y)) data stream, reservoir size, WS weighting scheme ("Standard" "Exponential"), AS averaging scheme ("Simple Average" or "Weighted Average"), ), VZ - voting- based zeroing (True or False), and other wwwe-meethhhseeeeee hyperpa- rameters H (e-g.. for PAC FSOL)
Output: WRS-stabilized solution vector WWRS-
1: function WAT(w, ((z,, We ))))?=
K, WS, AS, VZ, H)
2:
Initializing intermediate data structures
3:
- 0
Counter for subsequent passive steps of current solution candidate
4:
b Size-K reservoir for storing promising solutions, as array Size-K arrays for weights b, and auxiliary k, values for solutions in R # At each timestep, we observe (æe, yr)
R R-1
5:
b, 0.0
6:
7:
for
do
8:
if (w: Lt, B/)) > 0 then
If made error, in aggressive mode Terminate current solution, probabilistically add to reservoir using WRS
9:
10:
Draw u² ~ Onif(0, 1)
WS "Standard" then
12:
b- +
13:
else WS = "Exponential"" then
14:
b' + exp(s)
k + (u+)a++
> 6 10-8 prevent division by mi......... kiil: arg men! kij]
16:
R not full with solutions then
18:
R[1 + w, bli t b" klj] t k*
# Base method update rule
20:
w + w + g(.....
D p(...) specific to base algorithm (c.g.. PAC or FSOL)
b Reset number of subsequent passive steps > correctly-classffee still in passive mode D Increment number of subsequent passive steps
22:
else
23:
s+1
24:
Forming our PAC-WRS solution if AS = "Simple Average" then K
25:
26:
WWRS Σ Rij else if AS "Weighted Average" then
Simple average of solutions in reservoir
27:
WwRS f ビドー b(j)R[// b(jl)
Weighted avg. of solutions in reservoir
Voting Voting-based zeroing for extra sparsity if VZ is True then Zero out entries in Wwrs where the majority of solutions R[j] contain zeroes.
30:
32:
Return WwRs-
WwRs. should we take simple average of the residents in our reservoir or weighted average? Third, there are reasonable concerns that constructing Wwrs via averaging might negate the sparsity advantages of method like FSOL. due to different candidates in the reservoir containing Os in different entries. However, if the majority of candidate solutions in the reservoir contain Os at a given entry, what if we tried zeroing out said entry in WwRS, it is likely to be uninformative? We denote this add-on as voting-based zeroing.
We present the WAT method in full detail in Algorithm 1 To clarify, the elements in the data structures R, b, and (all of which are size-K arrays) are paired with each other, so that when we add/remove element in R, the corresponding elements in b and k are removed well. To be fully clear, R contains candidate solution vectors R[1].... R[K], with each R R[A] E R.D The vector contains scalar values b[l),... b[k], and likewise for the vector k.
3.2 Theoretical Analysis
One of the goals of our method to choose a set of effective models as the algorithm runs live, without the need for expensive evaluation a validation set. In this section we first provide validity
5

---

arguments for using observed survival as proxy to select high-accuracy models. These are finite- sample bounds based on reasoning about the reservoir R. Note that we are interested in studying generalization to unseen data, a complementary setting to prior work which shows convergence in terms of training set error for the perceptron model [19]. After establishing validity, we will turn to learning bounds for our ensemble model risk in the i.i.d. setting. Proofs are deferred to Appendix A
Validity analysis. We assume a given dataset 2f
)= is an i.i.d. sequence sampled from generating distribution D. We first suppose that (w; is the 0-1 loss, that is e(w; (x, y)) = ( of is misclassified by w. At any time t, we have an online model w., for which we define the survival time Sw, to be the number of subsequent correct classifications, stopping when we misclassifies sample. As W, does not change until error occurs, at any finite time only collect K updated models {w(1) 1== into R.
y). Then the risk (w( the probability that a random
Our first result bounds the difference in risk among two models in R: (1) the minimal-riss hypothesis W = arg min RD RD((()) which we do not know, and (2) the arg min Ww) which we observe. We also denote Sw and 8w, to be their respective survival times.
hypothesis w,
Theorem 1. Let w(").., ,...,
R be the updated outputs of an online PA algorithm on inputs Z ~ D. Also define Tm as the minimal achievable risk of any model, such that I'm S Ro(w)) almost surely. Then
w(h)
P(Rp(ws)) > Ro((w) + $ min
I'm
K e (rmmte) te)
2rm +E - T' (r + E)
This immediately leads to
I'm (K- -622-12100 (2(22mm)) Corollary 1. With prob. 1 - 6, RD (wp(w) S RD(W) + min 1- r.
851 -Fm)
While this bound explains the of top-1 survival in the worst case, we further justify the use of an ensemble (or reservoir) of top-surviving models. Specifically, given the use of top- B models, there is always certain probability that the top-(B 1) can lower the risk. Since B is base case, this implies that any value of B is worthy of consideration, until this probability decays to 0.
To simplify the notation, we sort the models in R by decreasing survival time s',...,,& & with R2. We also add an assumption that there is partition of R Rg UR such that R2 {w E R Tm S RD(w) I I'm + =) and Rs- = {w& E R: I'm + E < Rp (w) S rm + 32}, and that RR 2 B. That is, there is a set of good and bad models in terms of risk. In the Appendix we show that the assumption is readily satisfied.
corresponding re-indexed weights wi...., w/ and risks R2,
be the averaged risk of the top-B surviving models, and let Ro (W(B1)) be the averaged risk including the next highest survival model. Then RD(wB+1) S Rp (WB) with ((Ral)r
Theorem 2. Let
probability at least (( )r" (Tm + Rell
1/R.l-BBB (1 Tm - 3z)
Finally note that we can define an averaged model (weighted or unweighted) wB. For any convex 4x (w;:)) with risk Rt., such as the hinge loss, Jensen's 's inequality gives R.), (+1) S (D(WB+1)
Learning bounds. Now we turn to generalization bounds of our method, when run to a fixed stopping time T. We assume more generally that é(w; 2) convex, such as the hinge loss. Furthermore we suppose that the loss of any point in the training set is bounded by C. This is safe assumption for many passive-aggressive algorithms, where the input data is normalized and the update steps are not too large.
Theorem 3. Suppose É is convex and bounded from above by C. By time T, suppose the reservoir contains Ky models, with survival time of each at least 8T. Let Mars = Etm Tel(w,-1; 21) be the cumulative loss of the WAT reservoir sequence, with n. formally defined in the proof. Then w.p. 1 8,
log (T) Mors (KTST)²
7C log
T
Mørs KTST
8
RD ( wrrs <
KTST
The result shows that the risk of the ensemble model is stochastically bounded by the cumulative loss of the online procedure. By applying known regret bounds for the underlying online algorithms (c.g. PAC or FSOL), can further bound the risk in terms of the original learner, and subsequently

---

the optimal risk. In particular, we can "abstract out" the actual online learning method in the proof,
generic regret bound of form Mr T S Ei= ((: + r(T) for any w. Depending on the
algorithm often r (T) = O(VT) or even O(1).
With this in hand, we can show that the risk actually approaches the minimal risk. One additional assumption is required: / Ei= t= Te S + E, ((w,-1 =e) Mr (the WRS sequence has lower cumulative loss than the original learner). By definition, the reservoir contains the models which have longest survivals, and hence lowest regret density. So this statement is readily satisfied, as long as the distributions of non-zero losses are not different among the two sequences. In fact, under certain conditions, the incquality is likely strict which further improves the bound. Altogether we obtain:
Theorem 4. Given a PA algorithm, let Mr be its cumulative loss, and r(T) be the algorithm- sppciffcc excess regret. Then with probability - 8, the deviation in risk of our WRS model Wars from the optimal model w is bounded as
RD (Wos) S Rw(ww") T(T) +
2C log 2T
MT
7C log
2T
log f
CN
T
T TKTST
KTST
2T
Table I: Sizes, dimensions, and sparsities of all datasets used for numerical experiments.
Dataset
N
Nirain
Ncest
Sparsity
Avazu (App)
23
(via LIBSVM
1000000
14596137
10217295
4378842
0.999985
Avazu (Sile)
23
(via LIBSVM
1000000
25832830
18082981
7749849
0.999985
Cnico (Via LIBSVM
1000000
51882752
36317926
15564826
0.999961
Dexter 24
20000
600
420
180
0.995319
Dorothea 25
100000
1150
805
345
0.990909
KDD2010 (Algebra) 26 (via LIBSVM
20216830
8918054
6242637
2675417
0,999998
MNIST8 (4+9) 27/28 (via LIBSVM
784
1591785
1114249
477536
0,757170
News20 20 (via LIBSVM)
1355191
19954
13967
5987
0,999664
Newsgroups (Binary. CS) 30 skleamm
101631
18311
12817
5494
0,999049
PCMAC [32]
3289
1943
1360
583
0,985418
RCV1 3:3
(via LIBBVM
47236
697641
488348
209293
0,998451
Real-Sim (McCallum via LIBSVM
20958
72201
50540
21661
0,997549
SST-2 34
13757
67337
47135
20202
0,999421
URL 35
(via LIBSVM
3231961
2396130
1677291
718839
0.999964
W8A
36
(via LIBSVM
300
59245
41471
17774
0.957585
Webspam
37
(via LIBS VM
254
350000
244999
105001
0.664833
Numerical experiments
We combine WAT with base PAC and FSOL, forming two new methods PAC-WRS and FSOL-WRS"] We evaluate their performances across 16 binary classification datasets listed in Table [ Please see Appendix B for more dataset details. We are interested in three metrics: 1) Final test accuracy: proportion of test set data points clasecty by solution obtained after making one pass through the training data. 2) Final sparsity: proportion of zeroes in our classification solution obtained after making one pass through the training data. 3) Relative oracle performance (ROP): let pr, be the test accuracy of our base model (either PAC or FSOL) at time 1 and pt be the test accuracy of our model of interest (either base PAC, base FSOL, PAC-WRS. or FSOL-WRS)). Then, define Pr.oracle = max Pt, to be the cumulative maximum test accuracy of the base method at time t. In other words, Pt.ocacle represents the highest performance we could obtain if we had an oracle telling us which candidate solution vector we encountered was best. Then, define ROP = I minimal fluctuations, then ROP should be close O. or negative (i.e. achieving higher test accuracy than the oracle). In contrast, a large, positive ROP suggests fluctuations in test accuracy.
(Pr - p.). Intuitively, if a method has very stable test accuracy over time with
interested in the stability of WAT's test-set accuracy over the entirety of the training run, it is most illustrative to look at figures when possible. Representative figures will be shown in the
Because
Code available wtlhttp:://giiii http:p//.....tttoooocooceocceata Rewerroieeeeeer-eeeeeeee------ee -aaoiiir--amignggg- -eeee--uu-neeneeaanneeee

---

Avazu (App)
MNIST8 (4+9)
News20
0.075
0.02
0.10
0.050
0.01
0.025
0.00
Fift
0.05
0.000
-0.01
0.00
K=1
K=4
K-16
K-64
K=1
K=4
K-16
K-64
K=1
K=4
K-16
K-64
Sample Average
Weighted Average
PAC
Simple Average Vating.Based Zeraing
Weightedd Average Voding-Based Zercing
PAC (Mwam)
Figure 2: Relative oracle performances (y-axis) of base PAC and PAC-WRS using standard weights over reservoir sizes K (r-axis) on 3 representative datasets. Error bars represent the minimum and maximum values achieved across randomized trials. Blue: WRS- URS-augmented variants via simple average of reservoir members. Red: WRS-au URS-augmented variants via weighted average of reservoir members. Dotted lines: indicates voting-based zeroing was performed for additional sparsity, Lower values indicate more stable performance.
main paper, with all figures for all datasets in the appendix. When running any algorithm (PAC, FSOL, any dataset, we perform a random 70/30 train-test split. We begin by tuning the Cery. 7), and hyperparameters for base PAC and FSOL, with details located in Appendix B For PAC-WRS and FSOL-WRS, we use the hyperparameters for the corresponding base models, but try all possible WAT variants of weighting scheme (standard exponential), averaging scheme (simple vs. weighted), voting-based zeroing (True or False), and reservoir size K E {1,4, 4, 16, 64). We perform five trials for each PAC-WRS and FSOL-WRS variant with randomized shuffles of the training and test data, running through the training data only once for each trial. All candidate solutions are initialized as the vector. Please see more experimental details in Appendix B
MAC, or FSOL-WRO.
4.1 Stabilizing test performance
Figure I shows visually how PAC-WRS and FSOL-WRS are highly-effective stabilizing base PAC and FSOL's wildly-fluctualin test accuracy on Avazu (App) and News20. Corresponding figures for all 16 datasets and PAC-WRS/FSOL-WRS variants be found in Appendix G.2 From Figure 2 we see that PAC-WRS is highly-effective at reducing ROP compared to base PAC, and that the larger the reservoir size K, the more stable the resultant test accuracy for WwRs becomes. Furthermore, looking more carefully at MNIST8 (4+9), we observe that many PAC-WRS variants were able to achieve negative ROP values, suggesting that wwrs could achieve higher test accuracies than even the oracle. Corresponding figures for all 16 datasets can be found in Appendix G.T
observe that FSOL-WRS with standard weights and simple averaging success- fully stabilized test accuracy in all 16 tested datasets compared to base FSOL, as measured via ROP.
From Table
Table 2: Numbers of datasets out of 16 where each PAC-WRS or FSOL-WRS variant with K = 64 outperformed its corresponding base method (PAC or FSOL), as measured by ROP averaged across randomized trials.
PAC-WRS with exponential weights and simple averaging successfully stabilized test accuracy in 14 of tested datasets compared to base
Simple Average
Weighted Average
Standard
Exp.
Standard
Exponential
PAC. Following the best practices in [38 39).
PAC
13
14
13
11
FSOL
16
13
16
11
we perform Wilcoxon signed-rank tests for sta-
tistical significance on the differences in ROP between PAC/FSOL- -RRS versus base PAC and FSOL, taking into account performance on all 16 datasets. At a significance level of a = 0.05, we find that both PAC/FSOL-WRS achieve corresponding base models when equipped with standard weights (p < 0.0386 in each case, see Table 6 Appendix (F).
reductions in ROP compared to their
These results also suggest that standard weights are preferable to exponential weights. This makes sense because using exponential weights may be too "greedy," causing the algorithm to overly trust the number of passive steps as an indicator of test performance, polluting the reservoir with poor "lucky" candidate solutions, and refusing to remove them later.
8

---

Avazu (Site)
KDD2010 (Algebra)
SST-2
0.80
0.875
0.850
0.78
0.825
0.82
0.76
0.800
0.80
0.775
0.72
0.750
0.78
PSOL K=1
K=4
K-16
K-B4
ISOL
K=1
K-4
K-16 K-64
PSOL
K=1
K-4
K-10 K=64
Nimple Average
Wrighted Average
Oracie
15D1
Simplee Average Vating Based Zercing
Waighted Average Voling-Based Zeraing
Orwele (Mwan)
Final test accuracies (y-axis) of base FSOL and FSOL-WRS using standard weights over reservoir sizes K (z-axis) on 3 representative datasets. Error bars represent the minimum and maximum values achieved across 5 randomized trials. See Figure 2 for legend description.
Figure 3:
note on final test accuracy. From Figure we see that the final test accuracies achieved by FSOL-WRS are not only higher average than base FSOL,, but also have significantly lower variance. On these datasets, there no significant difference between FSOL-WRS variants with or without voting-based zeroing. As expected, final test accuracy seems be higher for larger values of reservoir size K. However, Wilcoxon signed-ran -rak tests to compare PAC-WRS and FSOL-WRS's improvements in final test accuracy over base PAC and FSOL indicate that FSOL-WRS with standard weights yields a statistically-signfffcai but PAC-WRS does discrepancy is that it is relatively unlikely for any given training data point to cause a massive drop in test accuracy, Furthermore, subsequent data points will usually help the base model self-correct (see Appendix G.2). Thus, this explains why the base method's i mean final test accuracy after particular fixed timestep (e.g., Numin) will not differ significantly from that of the WRS- ARR-aau method, especially not across only 5 trials.
improvement in final test accuracy compared to base FSOL, compared to base PAC (see Table in Appendix D. One hypothesis for this
Nonetheless, there enough data points in the training stream that these massive fluctuations in test accuracy could still happen thousands of times throughout the training process, corroborating what in Figure I If such drop in test accuracy model training is stopped, the consequences could be unacceptable. Furthermore, in continuously updated "any-time" environments, is hard to assess if one of these drops has occurred. As such, WAT is valuable as simple and effective way of preventing such fluctuations in test accuracy.
unlucky timestep when the
Avazu (Site)
KDD2010 (Algebra)
SST-2
0.9995
0.962
Hii
0.9990
0.6
0.9985
0.980
0.9980
0.979
0.9975
0.978
0.4
FSOL
K=1
K=44
K=16
K=64
FSOL
K=1
K=4
K=16
K=64
FSOL
K=1
Kmd
K=16
K=
Simple Average
Weighted Average
Simple Averoge Voting Based Zeroing
Weightted Average Vating Based Zeroing
Figure 4: Final sparsities (y-axis) of base FSOL and FSOL-WRS using standard weights over reservoir sizes K (æ-axis) on representative datasets. Error bars represent the minimum and maximum values achieved across 5 randomized trials. See Figure legend description.
Table Numbers of datasets out of 16 where each top-64 PAC or FSOL variant outper- formed its corresponding base method (PAC FSOL), as measured by relative oracle per- formance averaged across 5 trials.
Preservation of sparsity. Finally, we aim to re- tain the favorable weight sparsity from FSOL. From Figure 4 we observe that even with reservoir size K 64, the final sparsities achieved by FSOL-WRS are quite similar to that of base FSOL. Furthermore, we observe that with voting-based zeroing, FSOL- WRS often achieves even higher sparsity than the base model. Please see Appendix G.I for additional
Simple Average
Weighted Average
PAC FSOL
10
12
15
15

---

errorbar-type plots and Appendix G.2 for sparsity over timestep. One explanation for why even FSOL-WRS variants without voting-based zeroing can achieve similar sparsity base FSOL that the final reservoir will likely contain candidate solutions from significantly earlier timesteps, when weights were sparser due to fewer aggressive updates. Thus, WAT can maintain sparsity despite the use of weight averaging.
4.2 Ablations and extensions
Top-K ablation. A natural question that one might ask is ii--s--isi --stead of probabilistically sampling candidate solutions, what if we deterministically picked the top- candidate solutions with the largest subsequent numbers of passive steps and took their simple and/or weighted average? Setting K 64. we see from Table 3 that the best top-64 PAC/FSOL variants are not as effective as stabilizing test accuracy as the best PAC/FSOL-WRS variants, as shown Table [ and measured via ROP. Furthermore, Wilcoxon signed-rank test p-values from Table also suggest that this top-64 ablation cannot produce as statistically -iggiiiialysinniicaaan increases in test accuracy stability compared WAT, as measured via ROP. Like WAT, top- K is also ineffective at producing staisticalll-signifieee increases final test accuracy on PAC. On FSOL, top- K can produce statistically significant increases in final test accuracy, but these p-values are over order of magnitude larger than FSOL-WRS's (see Table in Appendix F.. As such, WAT still the best for stabilizing test accuracy.
also
Table 4: Wilcoxon signed-rank test p-values testing whether differences in relative oracle per- formance and final test accuracy between top-64 PAC/FSOL variants and base PAC/FSOL are statistically significant.
Relative Oracle Performance
Final Test Accuracy
Simple Average
Weighted Average
Simple Average Weighted Average
PAC
0.162
0.0298
0.214
0.255
FSOL
0.00270
0,00270
0,0130
0.0130
Additional ablations and comparisons. For the interested reader, in Appendix we include empirical performance comparisons of WRS-Augmented Training against two traditional ensembling mechanisms: moving average (e-g.. averaging the most-recently-obbeeeee K 64 weight vectors at each timestep) and exponential average (e.g.. forming an ensemble vector w, = 7, + (1 - at each timestep). where w, is the base algorithm's is candidate solution at timestep In short, especially in more real-world, large-scale settings where evaluation and checking are prohibitively expensive, WRS-Augmented Training is the fastest, most accurate, and most reliable method compared to all the aforementioned baselines.
Modifying WAT for non-passive aggressive methods. While the main theoretical and empirical results in this paper were primarily oriented towards aggresv-ageressive base models, in Appendix E. we include empirical simulations of applying a modified form of WRg-Angeented Training on top of three non nonn-pasive-aggressiv online learning methods: Stochastic Gradient Descent with Momentum 44). ADAGRAD [14,, and Truncated Gradient Descent [15]. general, our modified WRS- Training effectively mitigates test accuracy when it exists, and does minimal harm when it does not.
Conclusion, limitations, and future work
In this paper, we introduced WRS-Augmented Training (WAT), procedure that can be used to stabilize any passive-aggressive online learning algorithm, neither requiring a hold-out evaluation set nor additional passes over the training data. We applied WAT to base PAC and FSOL, demonstrating across 16 datasets that WAT is highly effective at mitigating the massive fluctuations in test accuracy between timesteps that affect many online learning algorithms. WAT runs at minimal cost, with only a fixed K multiple on memory for multiple weight vectors to be saved.
One limitation of this work is that WAT implicitly assumes that the training and test data come from fixed distributions that do not change over time. However, some data distributions will evolve over time. As such, candidate solution that entered the reservoir early on due to having a large number of subsequent passive steps might not actually retain its performance as the data distribution evolves over time. While they may eventually be replaced, non-lID adaptions may be useful in the future.
10

---

References
[1] Peilin Zhao, Dayong Wang, Pengcheng Wu, and Steven CH Hoi. A Unified Framework for Sparse Online Learning. ACM Transactions on Knowledge Discovery from Data (TKDD), 14(5):1-20, 2020.
[2] Nikos Karampatziakis and John Langford. Online Importance Weight Aware Updates, 2011. 1.
[3] Albert Bifet, Geoff Holmes, Bernhard Pfahringer, Philipp Kranen, Hardy Kremer, Timm Jansen, and Thomas Seidl. Moa: Massive online analysis, a framework for stream classification and clustering. In Proceedings of the first workshop applications of pattern analysis, pages 44-50. PMLR, 2010.
[4] Pavlos S Efraimidis and Paul G Spirakis. Weighted Random Sampling with Reservoir. Information Processing Letters, 9765):181-185, 2006.
[5] Koby Crammer, Ofer Dekel, Joseph Keshet, Shai Shalev-Shwaid and Yoram Singer. Online Passive- Dassive-Aggressive. Algorithms. Journal of Machine Learning Research, 7(19):551-585, 2006.
[6] Edward Raff, Bobby Filar, and James Holt. Getting Passive Aggressive About False Positives: Patching Deployed Malware Detectors. In 2020 International Conference on Data Mining Workshops (ICDMW), pages 506-515. IEEE, nov 2020.
[7] H. S. Anderson and P. Roth. EMBER: An Open Dataset for Training Static PE Malware Machine Learning Models. ArXiv e-prints, April 2018.
[8] Richard Harang and Ethan M. Rudd. Sorel-20m: A large scale benchmark dataset for malicious pe detection. Proceedings of the Conference on Applied Machine Learning for Information Security, 2021.
[9] Robert J Joyce, Edward Raff, Charles Nicholas, and James Holt. MalDICT: Benchmark Datasets on Malware Behaviors, Platforms, Exploitation, and Packers. Proceedings of the Conference Applied Machine Learning in Information Security, 2023.
[10] Robert J Joyce, Edward Raff, and Charles Nicholas. A Framework for Cluster and Classifier Evaluation in the Absence of Reference Labels. In Proceedings of the 14th ACM Workshop on Artificial Intelligence and Security (AlSec '21). Association for Computing Machinery, 2021.
[11] Robert Joyce, Edward Raff, and Charles Nicholas. Rank-1 I Similarity Matrix Decomposition For Modeling Changes in Antivirus Consensus Through Time. In Proceedings of the Conference on Applied Machine Learning for Information Security, 2021.
[12] Robert Joyce, Tirth Patel, Charles Nicholas, and Edward Raff. AVScan2Vec: Feature Learning on Antivirus Scan Data for Production-Scaal Malware Corpora. In Proceedings of the 16th ACM Workshop on Artificial Intelligence and Security, AlSec '23, page 185-196, New York, NY, USA, 2023, Association for Computing Machinery.
[13] Koby Crammer, Alex Kulesza, and Mark Dredze. Adaptive Regularization of Weight Vectors. Machine learning. 91:155-187. 2013.
[14] John Duchi, Elad Hazan, and Yoram Singer. Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. Journal of Machine Learning Research, 12(7), 2011.
[15] John Langford, Lihong Li, and Tong Zhang. Sparse Online Learning via Truncated Gradient. Journal of Machine Learning Research, 10(3), 2009.
[16] Shai Shalev- Shwattt- and Ambuj Tewari. Stochastic Methods for L1 Regularized Loss Mini- mization. In Proceedings of the 26th Annual International Conference on Machine Learning. pages 929-936, 2009.
[17) Lin Xiao. Dual Averaging Method for Regularized Stochastic Learning and Online Optimization. Advances in Neural Information Processing Systems, 22, 2009.
11

---

[18] Yoav Freund and Robert E Schapire. Large Margin Classification Using the Perceptron Algo- rithm. In Proceedings of the eleventh annual conference on Computational learning theory, pages 209-217, 1998.
[19] Marco Muselli. On convergence properties of pocket algorithm. IEEE Transactions on Neural Networks, 8(3):623 629, 1997.
[20] Nicolo Cesa-Bianchi, Alex Conconi. and Claudio Gentile. On the Generalization Ability of On-line Learning Algorithms. IEEE Transactions on Information Theory, 50(9):2050-2577, 2004.
[21] Nicolo Cesa-Bianchi and Claudio Gentile. Improved Risk Tail Bounds for On-line Algorithms. IEFE Transactions on Information Theory, 54(1):386-39) 2008.
[22] Ofer Dekel. From Online to Batch Learning with Cutoff-Averagig. Advances in Neural Information Processing Systems, 21, 2008
[23] Steve Wang and Will Cukierski.
Click-Through Rate Prediction.
Kaggle.
2014.
[24] Isabelle Guyon, Steve Gunn, Asa Ben-Hur, and Gideon Dror. Dexter. UCI Machine Learning Repository, 2008 DOI: https://bo..rr/11.2444////
[25] Isabelle Guyon, Steve Gunn, Asa Ben-Hur, and Gideon Dror. Dorothea. UCI Machine
Learning Repository, 2008 DOI:
[26] Stamper, A. Niculeseu-Mizil. S. Ritter, G.J. Gordon, and K.R. Koedinger. Algebra I 2008- 2009. Challenge Data Set from KDD Cup 2010 Educational Data Mining Challenge. Find it at http://pslcdattshhop..
2010.
[27] Jingwei Liang and Clarice Poon. Screening for Sparse Online Learning. arXiv preprint arXiv:2101.06982, 2021.
[28] Gaëlle Loosli, Stéphane Canu, and Léon Bottou. Training Invariant Support Vector Machines using Selective Sampling. In Léon Bottou, Olivier Chapelle, Dennis DeCoste, and Jason Weston, editors, Large Scale Kernel Machines, pages 301-320. MIT Press, Cambridge, MA., 2007.
[29] S Sathiya Keerthi, Dennis DeCoste, and Thorsten Joachims. Modified Finite Newton Method for Fast Solution of Large Scale Linear SVMs. Journal of Machine Learning Research, 6(3), 2005.
[30] Ken Lang. Newsweeder: Learning to Filter NetNews. In Proceedings of the Twelfth Interna- tional Conference on Machine Learning, pages 331-339, 1995.
[31] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-leamn Machine Learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
[32] Jundong Li, Kewei Cheng, Suhang Wang, Fred Morstatter, Robert Trevino, Jiliang Tang, and Huan Liu. Feature Selection: A Data Perspective. ACM Computing Surveys 54, 2018.
[33] David D Lewis, Yiming Yang, Tony Russell-Ross and Fan Li. Revl: A New Benchmark Collection for Text Categorization Research. Journal of machine learning research, 5(Apr):361- 397, 2004.
[34] Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Ng. and Christopher Potts. Recursive Deep Models for Semantic Compositionality over Sentiment Treebank. Proceedings of the 2013 Conference on Empirical Methods Natural Language Processing, pages 1631-1642, 2013.
[35] Justin Ma, Lawrence K Saul, Stefan Savage, and Geoffrey M Voelker. Identifying Suspicious urls: An Application of Large-Scale Online Learning. In Proceedings of the 26th Annual International Conference Machine Learning, pages 681 6-88888, 2009.
12

---

[36] John C Platt. Fast Training of Support Vector Machines Using Sequential Minimal Optimization. 1998.
[37] Steve Webb, James Caverlee, and Calton Pu. Introducing the Webb Spam Corpus: Using Email Spam to Identify Web Spam Automatically. In CEAS, 2006.
[38] Alessio Benavoli, Giorgio Corani, and Francesca Mangili. Should We Really Use Post-Hoc Tests Based on Mean-Ranks? Journal of Machine Learning Research, 17(5):1-10, 2016.
[39] Janez. Demšar. Statistical Comparisons of Classifiers over Multiple Data Sets. Journal of Machine Learning Research, 7(1):1-30, 2006.
[40] Πya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. In International conference on machine learning. pages 1149-1147. PMLR, 2013.
[41] David Freedman. tail probabilities for martingales. the Annals of Probability, pages 100-118, 1975.
13

---

A Proofs
A.1 Validity analysis
Proof of Theorem The main statement involves two independent bounds. See the proofs for Theorem and Theorem
Theorem 5. Let w(!),
w()) R be the updated outputs of online PA algorithm inputs of D. Define W. and w as previously. Also define I' as the minimal achievable risk of any model,
such that rm I RD(WW (W) almost surely.
Then
((R (D( +E) K
T'
2rm + E Tim (Tm + E)
Proof. First note that while (D(w) is constant value for any fixed w, RD(ws)) and RD(w) random variables induced by the distribution of Zf The sequence of observed samples affects both the algorithm's output w well the subsequent survival of
Next, we define the event interest A (w.)) > RD(w) + =}. For given realization of 2f
let the set RS {w E R. (D(w) Rp (w) + tE). Then
A S Ew E R (sw 2 sw) n (Ro(w)> > Ro(w) + +E)
(w Rg Sw 2 sw]
We aim to split this into separate events and apply union bound, but the contents and size of R depend on 2
Therefore we enumerate the models within each R. in the order they are received: {we up w (K) enabling the index refer to the corresponding model w!") in any realization of 2
Then we can split the event that hypothesis in the reservoir has longer survival into the union of events on each ordered hypothesis.
We have
A (5w E RR 8w 2 8
c Uis sw)
Applying the union bound, Lemma] I and then Lemma 2
P(A) < P(s 2 sw)
Σ (9 w P(s 2 sw !! w)
Σ E B P(S(w!") 2 ((W)/w! w)
Ro(w)
E B (D(ww (8)) + RD (w) (p(w!") ( (
I'm
< K
2r (m +
To further clarify, the probabilities computed depends on the realization of Z Lemma Jemma[allowe allows us to reason about the dependent model instances independent geometric variables, but need to extract into instance-independent state. Thus we need to condition on the weight values, and then bound the probability uniformly across the expectation, using the premise that the weight risks are e-distant.
the probability space of Z D, and w
L
14

---

Theorem 6. (Alternativ bound) Let the same conditions hold as in Theorem 5
Then
P(Rp(wa) > RD(w) + + S mm
Proof. As before, let (Ro((w)) > Rp(w) + + Then
A (Ro(w.) Ro(w)] [ {w, + w
(w, w
(&w 2 Sw, Vw E R]
The event {w, = w) implies w had or was tied for the highest survival, and we make the simplification that ties resolved in favor of w. Then
P(A) - P(sw 2 max Sw,, Vw E R)
P(sw Sw, Vw R)
Σ RD(w)(1- RD( II (1 (1-(1- (1-(1-Ro(w)) RD(w
Ro(w))) k- ( RD(w)- - =)*
S 11 (1 RD(w))
where in the third step, we apply Lemma 3 In the last step, we use the premise to suppose that there is least one hypothesis which is e-worse than w.
Considering the first-term only,
P(A) 1 1- RD((R))WW))))) ( (RD(w)) + +
1 - Ro(w) (RD(W)) +
exp ( (t) (Ro(()) +))
s exp ( x (rm +))
Remark. Note that this gives the worst-case bound presuming no knowledge over the distribution of risks among the K hypotheses. such scenario, the worst case is that all hypotheses achieve RD(W) except for one which is RD(w) + This is unrealistically adversarial, but the bound can easily be tightened by adding assumptions that the risks RD (D((()) are well-behaved and applying those in the last step.
Lemma 1. Let RD(w) be the misclassification risk. Suppose an online learner outputs hypothesis We at time after observing samples Z Let st be the subsequent survival time of w,, conditional on the observed sequence Zí. Also ((w) be the survival of w, over the distribution of sample sequences from DD Then S S(wi) has Geometric distribution with parameter R(w:). In addition 8, S(w).
Proof. For the first statement, observe that when sampling independently from D,
R(we) = Ep[1 [1|[[]]] ( * y)] = P(r.)))D(W((21) + y)
Since each i.i.d. sample has probability R(w;) to be misclassified, the number of trials until the first misclassificatton a Geometric distribution with parameter R(w,).
For the second, we need to consider a sequence of correct/incorreet classifications by w, as Bernoulli process of r.v. W. with parameter R(we), with stopping time 7 indicated by the first misclassification. 7 is random variable and see that S, L. Similarly 5(w,) can be defined on another Bernoulli process starting from From the memoryless property, these have the same distribution.
15

---

Lemma 2. Given random variables X and Y which are independent Geometric with parameters and q respectively (e.g. PMF of X P(X k) (1 (1-p)- -pp p. then
q
P(X 2 Y) + q - pd
and
P(X> Y)
14
p 9 Pq
Proof. For the first statement,
2 P(X Σ
P(Y ynx 29)
y=1
20
P(X 2 y/Y P) = v)
P(X 2 u) =
P(X = PV = v)
p) p.
p. (1 - 9)"-1a
PM
0-1
(1 - p)=
(1 p) 1-1
pq Σ (1 0-11
p
1 (1 p1 9)
q
p+ q - Pq
For the second, note that
P(X+Y)=11 P(Y X) =
p
p + q pq
-- pq
p + q pq
Lemma 3. Let Yı,..., Y, be independent Geometric random variables with respective parameters n q. Let X Geom(p) be independent. Then
20
P(X 2 max Y.) =
Σx(1 Pp11-pp
4z)²
16

---

Proof.
P(X 2 max Vi)
Σ
P(X
max Y; S <x)
a=1
P(X = x) P(max V, xx)
==1
Σ
P(X x) II sx)
a=1
by independence. Substitute the PMF and CMFs of the geometric distribution to finish.
Proof of Theorem
Proof. Note that
B+1 Σ
B Σ
=
R
1 B
R3
B +1 j=1
j=1
B+1 Σ R3
B Σ
(B+
m3}
j=1
/=1
1
R'8+1
Σ
R3
B
We now consider a subset this event. We will compute the probability that Ri,..., R'B E Rs and that R'841 E Ry. By definition, this latter event falls into A.
For this to occur, note from Lemma that each survival drawn from a Geometric distribution. We want the chance that the B largest survivals are from set Rs and then the next largest is from R.g. For additional simplicity, we further minimize the probability of this event by assigning all entries in Rg risk I'm and all entries in Rs risk Fm + 3z.
Conditioning on s'B+1 x, all entries from Rg are below x except for one, which equal to There are [Ryl ways to pick this largest one.
Then |R| B of the models in R2 are also below x, and B are above r. There are choose such B.
(Rl) ways to
Finally this probability is summed over all values of This is
Rob
R (1 (1 rm) (1 -mm -mm=--mm
(1 I' 3e) (1-mm Pm 333 Bz -3
B
As before, to get simpler expression, we just consider x. = yielding
P(A) 2 [Ryl [Ro] 2 (rm + +35) 1Rol-B BB rm - -32)
We also discuss the additional assumption of this Theorem to show that it is readily satisfied.
Assumption. There is partition of R Ry U Rs such that Rg (w E R Fm Ro(w) < Tm =} and R, = {w E R Tm + E < Rp(ww I Tm + 3E}, and that R2 2 B. That is, there is a set of good and bad models in terms of risk.
any small number that satisfies partition within the reservoir separating "good" from "bad" models e.g. (max4 R' Tmm/ works. For demonstration, suppose the
can set 6 >
17

---

underlying risks of the models in the reservoir range from 0.1 to 0.3, with 0.1 being the best risk Tm- Then 0.05. 2 then contains the models with risks in [0.1, 0.15] and R, contains those with risks in (0.15, 0.3]. The only time this isn't satisfied for any 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.
A.2 Learning bounds
Our bound follows from the following lemma from This itself is based on martingale inequalities from [1 and developments in (21).
Lemma 4 (Dekel). Let Li...., LT be sequence of real-valued random variables and let Zi...., Zr be sequence of random variables such that Lt = [8] Le (L Z.,.... Ze). Also assume
that L, E |0, for all Define Ue - Zz11), and let L, = Ei=1 Li. Then for any T 2 4 and 8 (0,1),
P V E (1... T}, Σu.> En / 20 (T) 7C log (1)
7
<8
From this obtain learning bound. The proof follows analogously the in modifications to handle our specific algorithm.
22 with
Proof of Theorem 3
Proof. In our method we have a reservoir R. containing K models w with associated weights bw. We focus the case where the weight is equal the passive steps survived by the model. To simplify this proof we consider a slightly modified algorithm, where all models with survival exceeding a threshold included in the reservoir.
0, if s(w,) <
if s(w,) = otherwise
We rewrite the weighted average of the reservoir models as a function of the entire training sequence of length T by defining Ny to be w, is in R and otherwise. Furthermore on the first instance that w, joins R, the n, instead set to This makes the weighting deterministic with respect the information at time t 1, at the cost of the reservoir size not being explicitly defined. While this is analogous to top-k averaging scheme, the full WRS scheme will follow from the same reasoning, with a more complicated definition of mi- This because all decision- makinn is performed using information that has already been
Then we write Wwrs Eis Te Et TeW,, and our goal is to control Rp (Wwrs). Furthermore,
define the cumulative loss as Mwrs IT Te((We-1, 2x). (We note that this term is little different from the observed cumulative WRS loss because of the requirement of reweighting on the s-th survival.)
In the lemma, let L, m,(((w-111)) 2)) and let U, E[Te((we11 =))==(-J]. Noting that L, is deterministic when conditioning on 2f. the assumptions are met. Then with probability we
have IT Us < Ly + / 2C2 (7)
7C (
Now U== - B[B(((((-1.2)))) = Σm Ti RPR((w where the first equality uses the fact that πy, determined by the filtration F and the second similarly uses the conditioning information to fix W and the i.i.d. assumption over 2.
Finally, we have Rp (o(Wwss) Jensen's inequality.
RD (
Ei mew)) S Ei, Dt ne RD(;)) from
18

---

Dividing the previous statement by Ei= we put the pieces together to conclude
Mars Ee TE
2C log
( E TT)2
M
7C log
Rip (eo(Wur Wure)
I
Σe
Finally, note that E, is the total time steps involved with the reservoir weights, which is at least Kr&t with Kr weights and 8T the minimal survival time of the reservoir. Substituting completes the proof.
Proof of Theorem
Proof. Combining the penultimate form of Theorem deduction that M Mwrs/ E. Te I Mr/TT we have
(with E, Th instead of KTST) and the
Mr T
2C log
1 Mr
7C
(w wrs)
+
E nxx
Σ,
Next, we turn our attention to the generic base-model online regret bound. From this we get
Mr /T S 1 Σ, [(w"[ 21) rTT)/T.
We need bound the cumulative loss of w", that is $ E, (aww[((w])) 22), in terms of the risk: RD(w" (w"). Using an application of Hoeffding bound, we get
log 1
l(w 2)) S RD(w") + +C1
T
27
which holds with probability 1 5.
Combining the undesired tail events under the union bound, we get
r(T) T
2C
4 Mr
7C 4
log
RD( (wrs)) S Rp(w")) +
Σ + C
T
T
21'
with probability 1 - 25. As before, substitute in KTST for Ee We complete.
Remark. The use of the online regret bound also indicates that the base models are improving over time. This means that their risks are decreasing, and hence the observed survival times are increasing. Thus even in the errrr term without T in the denominator, sT is increasing function of so we expect the error terms to decay T.
19

---

B Additional details on methods and experimental setups
B.1
Datasets
Of the 16 datasets used in our study (see Table 14 are directly from existing repositories and/or literature, while 2 of them Newsgroups (Binary, CS) and SST-2 were modified from pre-existing assets. First, Newsgroups (binary, CS) was formed by taking the original multi-class Newsgroups dataset hosted in [31 and combining the labels "Computers" and "Science" as a +11 class, and all other labels as the -1 class. Second, SST-2 is sentiment classification dataset originally containing text excerpts that we transformed into a linear classification dataset by using the CountVectorizer from 31
B.2 Base PAC and FSOL hyperparameter tuning
We start our set of experiments by tuning the Cerr hyperparameter for base PAC, testing values in 102, 10". For base FSOL, following Zhao et al.'s approach, we test values 102, 10 For each dataset, we perform
the set 10 10-3, 10-2
in 2- 2-2 ..... 2 2 and values in 0, 10-3 3 10 five rums of our base PAC and FSOL variants with randomized shuffles of the training and test data, running through the training data only once for each run. For each dataset, we pick the Cerrs 17, and À values corresponding to the base PAC and FSOL variants, within the top 2.5% in terms of final test aceuracy, that had the highest ROP, with all metrics averaged across the five runs. This experimental choice was made to strike a balance between simulating difficult and risky conditions as possible and still choosing useful base model variants.
B.3 Metries logging
Given that some of our datasets contain up to 36 million training points, it would be computationally and storage-wise unfeasible to record metrics each timestep. As such, for each dataset, we record metrics at R 200 evenly-spaced timesteps (exact number depends on divisibility and integer division of Nurain by 200) throughout the training stream, addition to the initial and final timesteps. As such ROP was also approximated by proxying oracle accuracy by taking the cumulative maximum base model test accuracy across timesteps where metrics were recorded. As shown in the over-time figures in Appendix G.2] such reduced resolution still tells us very clear picture, while cutting down computation and storage requirements by many orders of magnitude.
B.4 Compute requirements and code availability
All experiments were run on Linux computing cluster with 32 nodes, each with 40 Intel Xeon E5-2650 CPU cores and a total of 500 GB of RAM per node, managed using SLURM. Nonetheless, no experiments require multiprocessing or multiple cores. Depending on dataset size, some trials could take less than a minute to run, while the largest datasets would take couple hours max. However, larger datasets like Criteo will require 32 GB of RAM to load the dataset into memory.
Our source code for reproducing all experiments SerghheddRReeevvir--SSee Sampling-Augmentt Training/tree/main All experiments were run on CPU.
be found
20

---

C Applications to Malware Classification
Given that the original motivation for this work was real-world need in malware detection, present empirical results of PAC, PAC-WRS, FSOL, and FSOL-WRS on the EMBER malware classification dataset 77. The EMBER dataset is comprised of features extracted from 1.1M benign and malicious Windows portable executable files and thus can be considered very close to real-world test case our WRS-Augmented Training method on real-world deployment setting.
In Figure we observe that both base PAC and FSOL experience significant and frequent test accuracy dlucuuttios throughout the training process. However, both PAC-WRS and FSOL-WRS very successfully mitigate these test accuracy fluctuations and even outperform the oracle model, all without the use of a separate validation
PAC + PAC-WRS
FSOL + FSOL-WRS
Test Accuracy
0.95
0.95
0.90
0.85
PAC
0.85
FSOL
RAC-WRS
Oracie
Oracle
0.80
0.80
0
100000
200000 Timestep
300000
400000
100000
200000
300000
400000
Timestep
Figure 5: Test accuracies (y-axis) over timestep (æ-axis) for PAC/FSOL and PAC/FSOL-WRS on EMBER benchmark dataset for malware classification.
Indeed, WRS-Augmented Training is promising tool towards stabilizing test accuracy performance real-world deployment settings like malware detection.
21

---

D Comparisons to other ensembling and averaging schemes
One natural question a reader may ask is: how does WRS-Augmented Training compare traditional weight-averaging schemes such as moving average (e.g., averaging the K 64 weight vectors at each timestep) or exponential average (e.g.. forming an ensemble vector W, yw, + (1 - at each timestep), where w, is the base algorithm's 's candidate solution at timestep L.
From Figures 6 and 7 we observe that the exponential average scheme is consistently ineffective mitigating the test accuracy instabilities of the base models PAC and FSOL. The stability of the exponential average scheme is usually not much better than that of the base model, which makes sense because it still puts the majority of the weighting on the most recent candidate solution. From these figures, we also observe that the K = 64 moving average also has very mixed effectiveness. Overall, we see that Augmengdetted Training more preferable to the
64 moving average. This makes sense because with WRS- WRS-Augmented Training, we are much more selective about the quality of the candidate solutions that we retain in our reservoir, compared to moving average, which necessarily by definition must include poor-performing solutions as they appear.
Third, from Table method can be significantly computationally slower per iteration than WRS-Augmented Training. For example, with PAC as the base model. the moving average method was, on average, 6.579x slower per iteration than WRS-Augmented Training on KDD2010 (Algebra) and 10.050x slower per iteration than Aug-Augeented Training on URL. Similar trends hold when using FSOL as the base algorithm. These results make sense because with WRS- Augmented Training, we do not always add candidate solutions to our reservoir for averaging, while with the moving average method, we must always add new candidate solutions into our set. These insertion and deletion costs will accrue over time. On smaller datasets, the moving average is faster or slower depending on the dataset, but runtime is dominated by 10 and all methods finish within minutes. However, in more real-world, large-scale settings where evaluation and checking are prohibitively expensive, WRS- -uggenteeeteed Training is the fastest, most accurate, and most reliable method compared to all the baselines.
that for datasets with dimension D 100K, the moving average
22

---

Avazu
Criteo
0.24
0.87
0.80
0.00
0.70
0.7
0.78
0.76
0.6
0.8
1.00
1.0
400
107
KOD2010 (Algebra)
MNISTB
News20
0.32
1.0
0.950
0.95
0.9
0.90
0.90
0.400
0.00
0.7
0.30
0.850
0.80
0.75
0.0
5000
10000
Newsgroups (Binary, CS)
Real-Sim
1.0
0.81
0.6
0.85
SST-2
URL
WBA
Welspam
0.95
0.00
0.7
0.95
0.95
0.90
WilS-ugmmented Training
Moving Aug.
PAC
WRS-Augmented Training (For Emphasic)
Expo. Aug.
Figure 6: Test accuracies (y-axis) over timestep (r-axis) for WRS-Augmented Training (K 64), moving average (most recent K 64) and exponential average (7 = 0.9), using PAC as the base.
23

---

(Site)
0.9
3.84
0.9
3.80
0.8
0.78
0.78
0.76
0.8
0.8
0.75
300
400
167
107
(Algebra)
News20
0.95
0.95
0.85
0.50
0.8
0.80
0.85
0.75
0.80
1.00
0.0
5000
10000
166
166
Newsgroups (Binary. CS)
Real-Sim
0.9
0.90
1.00
1.0
0.95
0.90
0.8
0.70
0.85
SST-2
URL
W8A
Welspam
3.0
0.95
0.8
0.955
0.9
0.90
0.8
0.500
0.925
0.900
WRS W/RS-Augman megnleeed Treining
Moving Avg. Expo. Avg.
FSOL
WRS-Aug WRnttugmented mented Training (For Emphasis)
Figure 7: Test accuracies (y-axis) over timestep (r-axis) for WRS-Augmented Training (K = 64), moving average (most recent K 64) and exponential average (7 = 0.9), using FSOL as the base.
Table 5: Compute times per iteration (in seconds) moving average and exponential average relative to WRS -ug-aneeented training, with PAC (left) and FSOL (right) as base models. For example, on URL with PAC, moving average was, on average, 10.050x slower per iteration than WRS- URS-auggented training. Results were averaged over randomly-seeded trials.
PAC
FSOL
Dataset
Moving Avg.
Expo. Avg.
Moving Avg.
Expo. Avg.
Webspam
254
0.953
0.717
0.738
0.613
WSA
300
0.420
0.353
0.368
0.336
MNIST8 (4+9)
784
1.125
0.885
0,968
0.887
PCMAC
3289
0.483
0.312
0.377
0.235
SST-2
13757
0,903
0.431
0.748
0.411
Dexter
20000
0.577
0.143
0.285
0.066
Real-Sim
20958
0.949
0.624
0.707
0.564
RCV1
47236
1.825
0.892
1.366
1.011
Dorothea
100000
1.194
0.190000
0.580
0.254
Newsgroups (Binary, CS)
101631
3.587
1.042
1.376
0.543
Avazu (App)
1000000
8.357
2.507
8.078
2.544
Avazu (Site)
1000000
18.704
3.207
11.612
3,683
Criteo
1000000
13.108
2.876
7,009
2.381
News20
1355191
4.288
1.356
3.376
1.153
URL
3231961
10.050
3.945
9.124
4,058
KDD2010 (Algebra)
20216830
6.579
2.402
6.778
2.301

---

E Modified WRS-Augmented Training on non-passive aggressive online learning methods
In this section, we explore applying a modified form of WRS- ARRS-Augettedd Training (WAT) on top of three non-pasiive-aggrestie
online learning methods: Stochastic Gradient Descent with Momentum 40). ADAGRAD [14), and Truncated Gradient Descent [15. all using default hyperparameters. We emphasize that these three methods not passive-aggressive they always update their weight vectors at each time step, even if the data point was correctly classified. As such, the original WAT is directly applicable.
However, we can modify WAT as follows. First, we define a pseudo-passive step as one where the current solution candidate made no classification error (i.e., time step when the current solution candidate does make an error, we will sample the last weight vector before mistake was made into reservoir with probability proportional to the number of useudo-passive steps, hefore resetting our counter. The rest of WAT operates as normal under this pseudo-passive step weighting.
concept of margin). Second, at
we observe that all three non-passe massive-aggressin online algorithms, in particular Stochastic Gradient Descent with Momentum (SGD+M) and Truncated Gradient Descent (TGD), are susceptible to experiencing concerning fluctuations test accuracy. Consistently, across algorithms, we observe that when such fluctuations are present, modified WAT effectively mitigates such fluctuations very well. On the other hand, when there little fluctuation the base model (e.g.. ADAGRAD), applying modified WAT will do little to no harm. We emphasize that WAT was not designed for non-pas gassive-aggressae algorithms,, but is still demonstrably useful and adaptable to a wider class of base models, which constitute fruitful future work.
From Figures X
Avazu (App)
Avazu (Site)
Criteo
Dexter
0.88
0.0
0.80
0.0
0.84
0.70
0.02
0.65
0.7
0.0
0.2
0.4
0.6
0.8
1.0
0.3
0.5
3.0
3.5
100
200
300
400
Dorothea
KDD2010 (Algebra)
MNISTB (4+9)
News20
0.95
0.95
0.90
0.85
0.90
0.85
0.80
0.85
0.75
200
400
630
800
0.75
0.50
0:25
0.50
0.75
1.00
0.0
5000
10000
Newsgroops (Binary, CS)
PCMAC
Real-Sim
0.97
0.8
0.96
0.05
0.7
0.8
2500 5000 7500 1000012500
0.6
750
1000
1250
0.93
10000000000000000000000
1000020000 30000 40000
Webspam
0.94
0.7
0.85
0.97
0.92
0.6
30000
0.90
0.5
0.90
30000
20000
0.80
345
WRS.Augmented Training
WRS-Augmented Training (For Emphasis)
MomeMuuuu
Figure 8: Test accuracies (y-axis) over timestep (æ-axis) for modified WRS- Auggeeeeented Training (K 64) Stochastic Gradient Descent with Momentum.
25

---

(Apo)
Avazu
0.812
0.27
0.78
0.85
0.76
0.80
0.880
0.75
0.75
0.00
1.00
200
000
107
307
307
KDD2010 (Algebra)
(4+9)
0.88
0.545
0.57
0.85
0.00
0.75
0.85
0.930
0.0
5000
365
Newisgroups (Rinary, CS)
Real-Sim
0.5
0.97
0.5
0.95
0.90
0.6
0.93
0.85
20000
SST-2
URL
WBA
Webspam
0.985
0.96
0.900
0.7
0.975
0.050
0.96
0.970
0.500
WRS-Augmented Training
WRS-Augmented Training (For Emphasis)
AdaGrad
Figure 9: Test accuracies (y-axis) over timestep (z-axis) for modified WRS-Augmented Training
(K 64) on ADAGRAD.
26

---

(App)
(Site)
Dexter
0.770
0.87
0.78
0.0
0.760
0.85
0.750
0.6
1:00
400
101
(Algebra)
(4+9)
0.86
0.8
0.9
0.8
0.6
0.80
0.6
1.00
0.6
5000
10000
146
146
Newsgroups (Rinary. CS)
Real-Sim
0.0
0.90
0.7
0.88
0.86
0.80
0.8
SST-2
URL
W8A
Websgemn
0.9
0.65
0.8
0.97
0.7
0.60
0.96
0.95
WAS-Augmented Training
WRS-Augmented Training (For Emphasis)
Truncated Gradient Descent (TGD)
Figure 10: Test accuracies (y-axis) over timestep (æ-axis) for modified WRS-Augmented Training (K 64) on Truncated Gradient Descent.
27

---

Tables of p-values for Wilcoxon Signed-Rank Tests
Below, we provide full tables p-values computed using Wilcoxon Signed-Rank Tests towards prob- ing the statistical significance of the differences in ROP and final test accuracy between PAC/FSOL- WRS and their base model counterparts.
Table Wilcoxon signed-rank test p-values testing whether differences relative oracle perfor- mance between K 64 PAC/FSOL-WRS variants and base PAC/FSOL methods are statistically
significant.
Simple Average
Weighted Average
Standard
Exponential
Standard
Exponential
PAC
0.0150 0.000437
0.0199
0.0386 0.000437
0.325
FSOL
0.0879
0.0787
Table 7: Wilcoxon signed-rank test p-values testing whether differences in final test accuracy between K PAC/FSOL-WRS variants and base PAC/ESOL. methods are statistically significant.
Simple Average
Weighted Average
Standard
Exponential
Standard
Exponential
PAC
0.408
0.196
0.501
0.856
FSOL
0,00836
0.313
0.00836
0.679
28

---

G Additional results figures for PAC-WRS and FSOL-WRS
G.1 Uncertainty-quantfffe aggregate metrics across runs
Below, provide figures with error bars (minimum and maximum across 5 trials) showing the relative oracle performances (ROP), final test accuracies, and final sparsities of PAC-WRS and FSOL-WRS alongside the base PAC and FSOL models, across all 16 datasets. The main takeaways are that a) PAC-WRS and FSOL-WRS overall incur substantially-lower ROP than their corresponding base models; b) PAC-WRS and FSOL-WRS overall achieve comparable, if not improved. final test accuracy compared to their corresponding base models, consistently with lower variance, too; c) the final sparsities of PAC-WRS and FSOL-WRS are overall comparable, if not higher than those of their corresponding base models.
G.1.1
FSOL and FSOL-WRS
Avazu (App)
Avazu (Site)
Criteo
Dexter
0.20
0.15
0.094
0.006
0.20
0.10
0.004
0.002
0.002
0.001
0.000
0.05
0.000
-0.002
0.00
K-1
K-4 K-16 K-64
K-1
<-4
K-16 K-64
K-1
K-4
K-16 K-64
K-1
K-4
K-16 K-64
Dorothes
KDD2010 (Algebra)
MNIST8 (4+9)
News20
0.06
0.4
0.04
0.02
0.00
0.00
-0.02
0.0
K-11
K=4
K-16 K-64
K=1
K-4
K-15
K-64
K-1
K=4
K-16 K-64
K=1
K-4
K-16 K-64
Newsgroups (Binary, CS)
PCMAC
RCV1
Real-Sin
0.20
0.15
0.08
0.15
0.02
0.06
0.04
0.01
0.05
0.05
0.02
0.00
0.00
0.00
K=1
K=4
K=16
K=11
K=4
K=64
K=1
K=4
K=16 K=64
K-1
K=4
K=16
SST-2
URL
WBA
Webspam
0.08
0.325
0.06
0.100
0.04
0.075
0.02
0.00
0.025
0.02
-0.02
0.00
0.00
K-15
K-64
Kw64
K-16
Simple Average
Weighted Average
PSDL
Simple Average Voting-Based Zeroing
Weighted Average VVoting-Basee Boding-Based Zeroing
(Kean)
Relative oracle performances (y-axis) of base FSOL and FSOL- WRS using standard weights over reservoir sizes K (æ-axis) on all datasets. Error bars represent the minimum and maximum values achieved across 5 randomized trials. Blue: WRS-augmented variants via simple average of reservoir members. Red: WRS- WRS-augmented variants via weighted average of reservoir members. Dotted lines: indicates voting-based zeroing was performed for additional sparsity. Lower values indicate more stable performance.
Figure 11:
29

---

(Site)
0.88
0.795
0.9
0.86
0.790
0.785
0.0
0.780
0.775
150L
Kmdd K==16 Kobbd
1SOL
C:4 K=16 Kmb4
150L
K=16
150L
K:10 Kobc
Dorothea
KDD2010 (Algebra)
MNISTB (4+9)
News20
0.94
0.9
0.04
0.850
0.0
0.92
0.800
0.90
0.775
0.6
0.90
FSOL K+1
K-d
K-16 K-64
FSOL K-1
5-4
K-16 K-64
FSOX.
K-1
K-4
K-16 K-61
FSCL K-1 K-4 K-16 K-64
Newsgroups (Binary. CS)
PCMAC
RCV1
Real-Sim
0.85
0.97
0.96
0.80
0.85
0.75
0.90
0.70
0.80
0.95
0.65
0.94
FSOL
K+1
K-d
K-16 K-64
FSOL K=1
C-4
K-16 K-64
FSOL
K-]
Ke4
K-16 K=64
FSOL K=1 K-4 K- K-Gc
SST-2
URL
W8A
Webspam
0.9725
0.84
0.9
0.82
0.00
0.80
0.3730
0.7
0.9706
FSOL
K=1
K:44
K=16
K::64
FSOL K=1 C:4
K=16 K=:44
FSDL. K-1 K:4
K: K=04
PSOL K=1 K:4 K0 K:
Simple Average Simple Average Vasing
Winghted Average
Dracke
PSOL
Wir Wirghted Average Voting-tiesed zercing
Gracle (Mean)
Final test accuracies (y-axis) of base FSOL and FSOL-WRS using standard weights reservoir sizes (z-axis) on all datasets. Error bars represent the minimum and maximum values achieved across 5 randomized trials. Blue: WRS-augmented variants via simple average of reservoir members. Red: WRS-augmented variants via weighted average of reservoir members. Dotted lines: indicates voting-based zeroing was performed for additional sparsity.
Figure 12:
30

---

Avazu (Site)
Criteo
Dexter
0.50
0.45
0.92
0.40
0,979
0.90
0.978
K-15 K-64
FSOL
K-4
K-26 K-54
FSOL
K-1
K-4
K-16 K-64
FS0L
K-1
C-4 K-16 K-64
Dorothea
KDD2010 (Nlgebra)
MNISTa (4+9)
News20
0.9995
0.90
0.985
0.900
0.99995
0.9990
0.85
0.975
0.9965
0.970
0.9900
0.0975
0.960
FSDL K-1
K-4
K-16
K-66
FSOL
K-1
K-4
K-16 K-54
FSCL K-1 Kmd K-16 K-64
FSOL K-1 K-4 K-16 K-64
Newsgroups (Binary,
Real-Sim
0.75
0.40
0.35
0.7
0.35
0.25
0.20
0.35
0.35
0.4
FSOL
K+1
K-4
K=10 K-6G4
FSOL
K=1
K-d
K-26 K-54
FSOL
Kw]
Kud
K=16 K-64
FSOL
K-1
K-4 K=16 K=64
URL
Webspam
0.5
1.04
0.85
1.00
0.5%
8.0
0.56
1SDL
K=1
K:44
K:110
K=:64
FSOL
K=11
K-4
K:20
K:04
FSOL
K=1
Knd
K=10 K:04
PSOL
K=1
Ko4 K::16
K=64
Simple Average
Weighted Average
FSOL
Simple Average Variing
Wes Weighted Average Vating-Sased Zeroing
Figure 13: Final sparsities (y-axis) of base FSOL and FSOL-WRS using standard weights reservoir sizes (z-axis) on all datasets. Error bars represent the minimum and maximum values achieved across 5 randomized trials. Blue: WRS-augmented variants via simple average of reservoir members. Red: WRS-augmented variants via weighted average of reservoir members. Dotted lines: indicates voting-based zeroing was performed for additional sparsity.
31

---

(Site)
Criteo
0.10
0.005
0.06
0.084
0.014
0.012
0.122
0.06
0.010
0.075
0.04
0.002
0.008
0.050
0.02
0.001
0.006
0.00
K-1
K-1
K-16 K-61
K-1
K-1
K-16
K-61
K-1
K-4
K-16
K-64
K-1
K-4
K-16 K-64
Dorothca
KDD2010 (Algebra)
MNIST8 (4+9)
News20
0.04
0.4
0.15
0.06
0.10
0.04
0.7
0.02
0.00
K-1
K-4
K-26
K-64
K-1
K-4
K-15 K-64
K-1
K-4
K-15 K-64
K-1
K-4
K-16
K-64
Newsgroups (Binary.
PCMAC
RCV1
Real Sim
0.08
0.04
0.06
0.04
0.04
0.02
0.02
0.01
0.00
0.00
K=-1
K=44
K=16
K=:64
K=1
K=44
K=16 K=664
K=
K:44
K=16 K=64
K-1
K-4
K=16
K=64
SST-2
URL
WBA
Webspam
0.04
0.075
0.08
0.03
0.050
0.06
0.025
0.04
0.000
0.02
-0.025
0.00
Km1
Kmd
K=16
Kw64
K-1
Kmd
K-16
K-64
K=1
K-4
K-15
K=54
K=1
K-4
K-16
K=54
Simple Average
Weighted Average
Simple Average Voting-Based Zeroing
Weighted Average 4 Voting-Based Zeroing
FSOL (Mean)
Relative oracle performances (y-axis) of base FSOL and FSOL-WRS using exponential weights over reservoir sizes K (æ-axis) on all datasets. Error bars represent the minimum and maximum values achieved across 5 randomized trials. Blue: WRS-augmented variants via simple average of reservoir members. Red: WRS- URS-auummented variants via weighted average reservoir members. Dotted lines: indicates voting-based zeroing performed for additional sparsity. Lower values indicate more stable performance.
Figure 14:
32

---

(App)
Criteo
0.790
0.87
0.86
0,790
0.85
0.778
150L
K=:1 K:64
K=d C-10 Kmbb
1S0L
K=1
K-4
K=15 C:54
150L K= Kmbc
Dorothea
KDD2010 (Algebra)
MNIST8 (4+9)
News20
0.96
0.94
0.85
0.92
0.80
0.90
0.90
0.75
0.88
0.83
0.80
0.70
PSOL K-1 K-4 K-16 K-64
FSOL K-1 K-4 <-16 K-b4
FSOL K-1
K-4
K-15 6-61
FSOL K-1 K-4 K-16 K-66
Newsgroups [Binary, CS)
PCMAC
RCV1
Real-Sim Sim
0.90
0.850
0.825
0.85
0.800
0.90
0.82
0.88
FSOL
K=1
K-4
K-15 K-64
FSOL
K+1
Ked
C-16 K-64
FSCL K=1
K-4 K-16 C-54
FSOL
K=1 K-4 K- KwGc
SST-2
URL
WBA
Webspam
0.85
0.975
0,9725
0.92
0.50
0.80
0.92%
1901
0.86
0.900
0,9710
0.75
0.04
0.9705
FSOL K=11
K:4
K=15 K:64
150L
K=1 Kid
C:16
K:54
FSOL K=11 K-4 K=10
K=04
FSOL
K=1 K:4
K0 K:
Simple Average Simple Average Vating
Winghted Average
Dracke
PSOL
Wiighted Average Voting-tiasee Hleeed zercing
Gracle (Mean)
Final test accuracies (y-axis) of base FSOL and FSOL-WRS using exponential weights over reservoir sizes (æ-axis) on all datasets. Error bars represent the minimum and maximum values achieved across randomized trials. Blue: WRS-augmented variants via simple average of reservoir members. Red: WRS-augmented variants via weighted average of reservoir members. Dotted lines: indicates voting-based zeroing performed for additional sparsity.
Figure 15:
33

---

Avazu (Site)
Critea
Dexter
10
0.94
0,985
0.900
0.1
0.80
C-4 K-15 K-64
K-4 K-26 K-04
FSCL
K-1 K-4
K-16 K--64
FSOL
K-1 C-4
K-16 K-64
Dorothea
KDD2010 (Nlgebra)
MNIST8 (4+9)
News20
1,0000
0.99
0.99995
0.95
0.9995
0.98
0.97
0.85
0.90
FSOL
K-1
K-4
K-16
K-64
FSOL
K-1 K-4 K-16 K-54
FSCL
K-1 Kmd K-16 K-64
FSOL K-1 K-4 K-16 K-64
Newsgroups (Binary,
Real-Sim
0.75
0.4
0.0
0.70
0.6
0.5
11
0.05
0.4
0.80
0.2
0.0
0.3
0.35
FSOL
K-
K-4
K-10 K-66
FSOL
K=1
K-d
K-16 K-54
FSCL
Kw]
Kud
K=16 K-64
FSOL
K-1
K-4 K=16 K-64
URL
1c-3 5:300002
Webspam
0.05
1.04
0.95
0.90
0.55
1.00
9.0
0.80
0.45
FSOL
K=1
K:4
K=10
K=64
FSOL
K=1
K-4
K:26
K:04
FSOL K=1
Knd K=10 K:04
PSOL
K=1
K:4 K=16 K:64
Simple Average
Weighted Average
FSOL
Simple Average Variing
Weighted Average Vating-Sased Zeroing
Figure 16: Final sparsities (y-axis) of base FSOL and FSOL-WRS using exponential weights reservoir sizes (z-axis) on all datasets. Error bars represent the minimum and maximum values achieved across 5 randomized trials. Blue: WRS-augmented variants via simple average of reservoir members. Red: WRS-augmented variants via weighted average of reservoir members. Dotted lines: indicates voting-based zeroing was performed for additional sparsity.
34

---

G.1.2 PAC and PAC-WRS
Ávazu (App)
Avazu (Site)
Criteo
Dexter
0.0020
0.004
0.0015
0.15
0.003
0.04
0.0010
0.02
0.002
0.0005
0.05
0.00
K-1
K-4
K-16 K-64
K-1
K-4
K-16
K-64
K-1
K-4
K-16 K-64
K-1
K-4
K-16 K-64
Dorothea
KDD2010 (Algebra)
MNISTB (4+9)
News20
0.125
0.02
0.125
0.100
0.075
0.075
0.050
0.025
0.00
+128
0.00
0.025
-0.01
2225
0.000
K-1
K-4
K-
K-64
K=1
K-4
K-16
K-64
K=1
K-4
K-16 K=64
K-1
K=4
K=16
K=
Newsgroups (Binary, C5)
PCMAC
RCV1
Real-Sim
0.150
0.10
0.125
0.00
0.010
0.100
0.100
0.075
0.005
0.075
0.050
0.000
0.025
0.025
0.02
-0.005
1311
0.000
K=1
K=4
K=11
K=4
K=16 K=64
K=11
K=4
K=16 K=64
K-1
K=4
K=16
SST-2
URL
WSA
Webspam
0.075
0.006
0.0100
0.0075
0.050
0.004
0.02
0.025
0.000
12
0.002
0.0000
-0.025
0.000
K+1
K-16 Kw64
Simple Average
Weighted Average
PAC
Simpla Average Voting-Based Zeroing
Weigited Average
Votting Based Zeroing
PAC (Mean)
Relative oracle performances (y-axis) of base PAC and PAC-WRS using standard weights over reservoir sizes K (æ-axis) on all datasets. Error bars represent the minimum and maximum values achieved across 5 randomized trials. Blue: WRS-augmented variants via simple average of reservoir members. Red: WRS-augmentee variants via weighted average of reservoir members. Dotted lines: indicates boing-bbsed zeroing was performed for additional sparsity. Lower values indicate more stable performance.
Figure 17:
35

---

(App)
(Site)
0.58
0.000
0.795
0.96
0.86
0.807
0.94
0.84
0.92
0.806
0.90
0.82
0.805
0.788
K-11
C:44
C:100 Kmb44
K=10 K::44
K= Knmb
80C
K=1
Knd
K-10 Kob4
Dorothea
KDD2010 (Algebra)
MNISTB (4+9)
News20
0.94
0.88
HH
HiH
0.950
0.93
0.900
0.92
0.92
0.91
0.850
0.91
0.85
PAC
K-1
<-4
6-16 K-64
K-1 K-6
K-16 K-64
PAC K-1
K-4
K-16 K-64
IBC
K-1
Kmd
K-16 K-64
Newsgroups (Binary, CS)
PCMAC
RCV1
Real-Sim
0.975
0.85
0.05
0,950
9.80
0.50
0.75
0,900
PAC
K=-1
6-4
C-16 K-64
PAC
K=]
Kmd
K=16 K-54
PAC
K+1
C-4
K-16 Kw64
9AC
K=1
Ked
K-16 K-54
SST-2
URL
WBA
Webspam
0.86
0.985
HH
1111 XXE
0.84
0.900
0.97
0.91
0.82
0.96
0.50
0.80
0.95
PAC
K=11
C-4
C-
K=
RAC
K=]
K:4
K:10
K=04
PAC
K-1
K:4
K:166
K=64
86C
K=11
K: K:044
Simple Avarage
Weighted Average
Ctacil
PAC
Simple Average Viting-tassed Zerning
Weighted Average VVoling Weting-lssed
Cracie (Mean)
Final test accuracies (y-axis) of base PAC and PAC-WRS using standard weights reservoir sizes (z-axis) on all datasets. Error bars represent the minimum and maximum values achieved across 5 randomized trials. Blue: WRS-augmented variants via simple average of reservoir members. Red: WRS-augmented variants via weighted average of reservoir members. Dotted lines: indicates voting-based zeroing was performed for additional sparsity.
Figure 18:
36

---

Criteo
0.964
0.984
0.675
0.342
0.050
0.982
0,980
0.025
0.901
0.976
0.338
K=1
K=:16
K-:4
RMC
K=1bb
K:04
Kc:4
K::66 Kibbd
RMC
K=1
K=10
Kob4
Dorothea
KDD2010 (Algebra)
MNIST8 (4++9)
News20
0.35
0.8
0.050
0.70
0.
0.7
0.65
0.25
0.045
0.60
0.040
0.5
0.50
PNC
K-1
K-4
K-16
K-64
PAC
K+1
K-4
K-16
K-64
K-1
K-4
K-16 K-64
R9C
K-1
K-4
K-16 K-64
Newsgroups (Binary, CS)
PCMAC
RCV1
Real-Sim
0.30
0.25
0.6
0.32
0.29
0.30
0.15
0.15
0.10
0.10
0.05
P6C
K=1
K=4
K-16 K-64
PAC
K+1
K-4
K=16 K+64
9AC
K+1
K-4
K-16 K-64
B6C
K-1
K-4
K-16
K-54
SST-2
URL
W8A
Webspam
0.20
0.52
0.94
0.18
0.16
0.92
0.002
0.50
.00.
0.14
0.001
0.49
0.12
0.40
PAC
K=:1
Ko4
K=10
K:04
RAC
K=1
K:44
K=16
K:04
PAC
K=1
K=44
K=
K=64
R6C
K=1
K-4
K-10
K:54
Avarage
Weighted Average
FAC
Simple Average Vattin-tSssed Leroing
Weighoed Average Viringelssed Zeroing
Final sparsities (y-axis) of base PAC and PAC-WRS using standard weights reservoir sizes (z-axis) on all datasets. Error bars represent the minimum and maximum values achieved across 5 randomized trials. Blue: WRS-augmented variants via simple average of reservoir members. Red: WRS-augmented variants via weighted average of reservoir members. Dotted lines: indicates voting-based zeroing was performed for additional sparsity.
Figure 19:
37

---

(App)
(Site)
0.08
0.10
0.06
0.08
0.002
0.04
0.06
0.02
0.001
1217
0.000
K-1
K-1
K-16 K-64
K-1
<-4
K-16 K-64
K-1
K-4
K-16 K-64
K-1
K-4
K-16 K-61
Dorothea
KDD2010 (Algebra)
MNISTB (4+9)
News20
0.025
0.020
0.0050
0.04
0.08
0.0025
0.06
0.02
0.010
-0.0025
0.005
-0.0050
0.00
0.02
12
12
0.00
K-1
K-4
K-16
K-64
K=1
K-4
K-16 K-64
K--1
K-44
K-16
K-64
K=1
K-d
K-16
K=G4
Newsgroups (Binary, CS)
PCMAC
RCV1
Real Sim
0.020
0.03
0.06
0.015
0.02
0.06
0.010
0.04
0.04
0.005
1
0.01
0.02
0.000
11
K=11
K=4
K=16 K=64
K=11
K
K-16 K-64
K=11
K=44
K=16
K=
K=1
K-4
1=
K=64
SST-2
URL
W8A
Webspam
0.08
0.06
0.020
0.015
0.020
0.04
0.015
0.015
0.02
0.010
0.90
0.010
0.005
0.005
0.000
K-1
Km4
K-16
K-64
K-1
K=4
K-16
K-64
K-1
Km4
K-16
K-64
K=1
K=d
K-16
Kw54
Simple Average
Weighted Average
Simple Average Voting-Based Zeroing
Weighted Average Voting-Based Zeroing
PAC (Meen)
Relative oracle performances (y-axis) of base PAC and PAC-WRS using exponential weights over reservoir sizes K (z-axis) on all datasets. Error bars represent the minimum and maximum values achieved across 5 randomized trials. Blue: WRS-augmented variants via simple average of reservoir members. Red: WRS- URS-auummeted variants via weighted average reservoir members. Dotted lines: indicates voting-basee based zeroing performed for additional sparsity. Lower values indicate more stable performance.
Figure 20:
38

---

(App)
Criteo
0.000
0.7950
0.90
0.807
0.86
0.7925
0.94
0.1900
0.84
0.7875
0.90
0.7850
0.82
0.005
RMC
K=:1d Km64
Kidd C-10 K-bb
RBC
K=11
K-44
K=15 C:54
PMC
K: Kobc
Dorothea
KDD2010 (Algebra)
MNIST8 (4+9)
News20
0.96
0.94
0.95
0.93
0.875
0.93
0.94
0.92
0.91
0.91
0.92
0.90
0.065
0.89
INC K-1 K-4 K-15 K-64
IMC
K-1
K-4
C-16 K-b4
PSC
K-1
K-4
K-15 6-64
PNC
K-1
K-4
K-16 K-64
Newsgroups (Binary, CS)
PCMAC
RCV1
Real-Sim
0.97
0.85
0.90
0.96
0.875
0.80
0.850
0.92
0.95
0.75
0.825
0.90
0.94
0.000
RAC
K=1
K-4
K-15 K-64
BAC
K-+1
C-16 K-64
FAC
K=1
K-4
K=16 C-54
RAC
K=1
K-4 K-16 K-G4
SST-2
URL
WBA
Webspam
0.925
0.985
0.98
0.980
0.915
0.97
0.970
0.905
0.905
0.750
0.060
0.95
0.000
RAC
K:11
K:44
K=16
K=64
PAC
K=1
Kid
C:16
K:64
RAC
K=-1
K:4
K=16
C:04
RAC K=1 Ki4
K= K:
Simple Avarage
Weighted Average
Ctocil
FAC
Simple Average Viting-tissed Zerning
Weighted Average Votling Blaeed
Cracie (Mean)
Final test accuracies (y-axis) of base PAC and PAC-WRS using exponential weights reservoir sizes (z-axis) on all datasets. Error bars represent the minimum and maximum values achieved across 5 randomized trials. Blue: WRS-augmented variants via simple average of reservoir members. Red: WRS-augmented variants via weighted average of reservoir members. Dotted lines: indicates voting-based zeroing was performed for additional sparsity.
Figure 21:
39

---

(App)
Criteo
0.075
0.995
111!
0.990
0.342
0.338
0.9750
K:4
K-16 Km66
K=:1 Km-M4
RMC
K=11
Kidd
K::66
Ko64
K=4 K-16 Kobc
Dorothea
KDD2010 (Algebra)
MNIST8 (4+9)
News20
0.40
0.150
0.575
0.125
0.30
0.7
0.100
0.550
0.25
0.6
0.20
0.5
0.475
PMC
K-1
K-4
K-16
K-64
PAC
K-1
K-4
K-16 K-54
PMC
K-1
K-4
K-16 K-64
K-1
K-4
K-16 K-64
Newsgroups (Binary, CS)
PCMAC
RCV1
Real-Sim
0.6
0.25
0.150
0.6
0.5
0.125
0.20
0.4
0.100
0.10
PAC
K=1
K-4
K=16 Kw64
RAC
K=1
K-4
K=16 K-64
R6C
K+1
Ked
K-16 K-64
RAC
K=1
K-4
K-16 K-G4
SST-2
URL
W8A
Webspam
1.000
0.8
0.57
0.975
0.6
0.4
0.50
4400 4049
0.925
0.49
0.15
0.900
0.40
RAC
K=1
Km44
K=10
K:-64
RAC
K=1 K04
K=16
K:04
RAC
K=1
K:d
K=
K=64
RAC
K=1
Knd
K=16 K:64
Sirple Avarage
Weighted Average
DAC
Simple Average vantingtSased Leroing
Weighoed Average Viringelased Zeroing
Figure 22: Final sparsities (y-axis) of base PAC and PAC-WRS using exponential weights reservoir sizes (z-axis) on all datasets. Error bars represent the minimum and maximum values achieved across 5 randomized trials. Blue: WRS-augmented variants via simple average of reservoir members. Red: WRS-augmented variants via weighted average of reservoir members. Dotted lines: indicates voting-based zeroing was performed for additional sparsity.
40

---

G.2 Test accuracies and sparsities over time
Below, we provide figures showing test accuracies and sparsities over time on individual runs of PAC-WRS and FSOL-WRS, compared against their base model counterparts, all 16 datasets. The main takeaways are that a) test accuracies over time on PAC-WRS and FSOL-WRS are overall much stabler, if not also higher, than their base model counterparts (and much closer to that of the oracle); b) applying WAT to PAC and FSOL does not significantly impact sparsity - in some cases, especially with voting- based zeroing, sparsity actually increases compared the base model!
G.2.1
FSOL and FSOL-WRS
Avazu (App)
Avazu (Site)
Criteo
Dexter
0.50
0.55
117
0.50
0.5
0.75
0.70
0.65
0.70
0.65
0.65
0.7
0.00
0.60
Darothea
KDD2010 (Alqebra)
MNISTS (4+9)
News20
0.00
0.05
2.-
0.00
0.75
2.8
0.7
0.70
57-
0.7
0.6
0.8
148
Newsgroups (Binary. CS)
POMAC
RCV1
Real-Sim
0.50
0.90
1.0
0.55
0.87
0.5
0.50
0.80
0.75
0.75
0.70
0.70
0.65
0.02
0.00
0.6
0.6
0.6
SST-2
URL
W8A
Websgam
0.55
0.9
0.2
2.5
0.11
0.70
0.50
0.6
240000
160
(Simple Averagel
(Weignted Average)
PSOL-WRS (Simple Average Vatingg Uased Zeroing)
FSOL WIRS (Weighted Average + Voting Based Zeraing)
Oracie
Test accuracies (g-axis) K 64 using standard weighting on all 16 tested datasets. Light grey lines: test accuracies of the FSOL baseline methods each timestep. Solid black lines: test accuracies of the "oracle" models, computed as the cumulative maximum of the FSOL baselines. Blue: corresponds to FSOL-WRS variants ensembled via simple averaging. Red: corresponds to FSOL-WRS variants ensembled via weighted averaging. Dotted lines: indicate whether voting-based zeroing was applied for additional sparsity.
Figure 23:
timestep (r-axis) for FSOL-WRS with reservoir size
41

---

Avazu
318.592
(Site)
Criteo
10
1,000
1.0
1.00
1995
0.0
1.000
0.985
0.54
0.500
0.4
Dorothea
KDD2010 (Algebral
MINISBB (4+99)
News20
0.59
0.9900
0.50
-0.0000
0.0003
0.50
-0.00003
000000
-0/00012
0.5973
0.75
0.56
166
Newsgroups (Binary, CS)
PCMAC
RCV1
Real.Sim
1.0
1.0
1.0
1.0
0.5
0.0
0.8
0.7
0.6
0.5
0.4
0.2
044
4000
1000
12200
400
002
1200
150025
3:0000
450000
0
15200
30020
40000
URL
16-5+% 509e-1
WBA
0.5
0,500
0.50
0.690
0.05
5.0
0.80
140
FSOL-WRS
(Simple Average)
FSOL-WRS (Weighted Average)
FS0L
PSOL-WRS (Simple Average voting-Based Zeroing)
#SOL-WRS (weighted Average voting-Based Zeroing)
Oracte
Figure 24: Sparsity (y-axis) over timestep (æ-axis) for FSOL-WRS with reservoir size K 64 using standard weighting on all 16 tested datasets. Light grey lines: sparsities of the FSOL baseline methods at each timestep. Blue: corresponds to FSOL-WER variants ensembled via simple averaging. Red: corresponds to FSOL-WRS variants ensembled via weighted averaging. Dotted lines: indicate whether voting-bac based zeroing was applied for additional sparsity.
42

---

(App)
Avazu (Site)
Crite
Dexter
0.50
0.50
0.50
0.0
0.70
0.10
0.03
25
Dorothea
KDD2010 (Algebro)
MNIST8 (4+99)
News20
MW
0.00
0.5
0.75
3.8
0.0
0.7
0.70
07-
0.7
0.65
0.60
500
402000
Newsgroups (Binary. CS)
POMAC
RCV1
Real-Sim
0.50
0.40
1.0
0.65
0.83
0.5
0.:00
0.00
0.75
0.75
3.8
0.70
0.70
0.50
0.62
0.50
0.62
150003
SST-2
URL
W8A
Webspam
0.50
0.5
2.9
0.65
0.50
FSOL-WRS
(Simple Averagel
FSOL-WRS (Weignted Average)
PSOL
PSOL-WRS (Simple Average Vating-Sased Zeroing)
FSOL-WIS (Weignted Average Voting-Based Zeroing)
Oracte
Test accuracies (g-axis) over timestep (æ-axis) for FSOL-WRS with reservoir size K = 64 using exponential weighting on all 16 tested datasets. Light grey lines: test accuracies of the FSOL baseline methods each timestep. Solid black lines: test accuracies of the "oracle" models. computed as the cumulative maximum of the FSOL baselines. Blue: corresponds to FSOL-WRS variants ensembled via simple averaging. Red: corresponds to FSOL-WRS variants ensembled via weighted averaging. Dotted lines: indicate whether voting- based zeroing was applied for additional sparsity.
Figure 25:
43

---

Juazu (App)
319.999
(Site)
Crileo
Dexttr
10
1,000
1.0
1.00
0.005
0.90
0.200
0.005
0.000
0.52
100
Dorothes
KDD2010 (Algebra)
MNIST8
News20
0:93
0.99
-0.0000
299325
0.90
-0.00003
99900
0.85
0.50
-0/00022
0000010
299375
0.80
0.96
1nd
Newsgroups (Binary, CS)
PCMAC
RCV1
Real-Sim
1.0
1.0
1.0
1.0
0.8
0.7
0.2
4000
3020
12000
402
$20
1203
130000
320000
420005
23002
30020
45020
URL
5ST-2
1e-51h 3400
WBA
Watspam
0.55
3.5
0.003
0.90
0.000
0.05
0.13
FSOL-WRS (Simple Average)
FSOL-WRS (Weighted Average)
F50L
PSOL-WRS (Simple Average voting-Based Zeroing)
FSOL-WHS (Weighted Average voting-Based Zeroing)
Oracle
Figure 26: Sparsity (y-axis) over timestep (æ-axis) for FSOL-WRS with reservoir size K 64 using exponential weighting on all 16 tested datasets. Light grey lines: sparsities of the FSOL baseline methods each timestep. Blue: corresponds averaging. Red: corresponds to FSOL-WRR WRS variants ensembled via weighted averaging. Dotted lines: indicate whether voting-based zeroing was applied for additional sparsity.
3SOL-WRS variants ensembled via simple
44

---

G.2.2 PAC and PAC-WRS
Avazu (App)
Avazu (Site)
Criteo
Dexter
0.50
0.55
0.0
0.50
0.75
0.70
0.8
0.70
0.05
0.65
9.55
0.00
0.60
0.00
Dorothea
KDD2010 (Alqsbra)
MNISTS (4+
News20
0.80
0.87
0.80
0.75
0.7
0.70
0.6
0.
082
14b
Newsgroups (Binary. CS)
POMAC
RCV1
Real-Sim
0.50
1.0
0.5
0.70
0.55
0.00
0.6
0.6
5ST-2
URL
W8A
Websgam
0.50
1.0
1.0
0.55
0.9
0.50
0.5
2.0
0.50
15003
0.6
240000
160
RAC-WRS (Simple Averagel
PAC-WRS (Weighted Average)
PAC-WRS (Simple Average Vattigg Ulseed Zeroing)
PAC-WRS (Weighted Average + Voting Based Zeroing)
Oracle
Test accuracies (y-axis) over timestep (æ-axis) for PAC-WRS with reservoir size K 64 using standard weighting on all 16 tested datasets. Light grey lines: test accuracies of the PAC baseline methods at each timestep. Solid black lines: test accuracies of the "oracle" models, computed as the cumulative maximum of the PAC baselines. Blue: corresponds to PAC-WRS variants ensembled via simple averaging. Red: corresponds PAC-WRS variants ensembled via weighted averaging. Dotted lines: indicate whether voting- zeroing was applied for additional sparsity.
Figure 27:
45

---

Avazu
Avazu (5ite)
Criteo
Dexter
0.20
01355
0.3
0.590
0.8
0.305
0.310
0.500
1.0
Dorothea
<DD2010 (Algeora)
MNISTB (4+9)
News20
0.8
0.5
0.9
0.5
0.3
2.5
0.5
0.7
000000
4000
Newsgroups (Binary, CS)
PCMAC
RCV1
Roal-Sim
0.2
0.5
0.5
0.0
0.4
0.4
S5T-2
URL
WBA
Webspam
3.0
3.50
0.5
0.94
0.4
0.7
0.52
0.40
PNC-WRS (Simple Average)
PAC-WRS (Weighted Average)
PAC
PAC-WRS (Simple Average voting-Based Zeroing)
PAC-WIS (Weighted Average Voting-Besee Zeroing)
Orecle
Figure 28: Sparsity (y-axis) over timestep (æ-axis) for PAC-WRS with reservoir size K 64 using standard weighting on all 16 tested datasets. Light grey lines: sparsities of the PAC baseline methods each timestep. Blue: corresponds to PAC-W WRS variants ensembled via simple averaging. Red: corresponds to PAC-WRS variants ensembled via weighted averaging. Dotted lines: indicate whether voting-based zeroing was applied for additional sparsity.
46

---

(App)
AvazJ (Site)
Crite
Dexter
0.00
0.55
0.5
0.50
0.75
0.70
0.0
0.10
0.63
25
Dorothea
KDD2010 (Algebro)
MNIST8 (4+9)
News20
0.90
0.85
0.00
0.75
0.7
0.70
0.61
0.60
500
Newsgroups (Binary. CS)
POMAC
RCV1
Real-Sim
0.2
0.5
2.8
0.10
0.89
0.50
150003
SST-2
URL
WBA
Webspam
0.50
1.0
1.0
0.55
0.5
0.5-
0.29
0.50
PNC-WRS (Simple Averagel
PAC-WRS (Weighted Average)
PNC Oracle
PAC-WRS (Simple Average Voting-Sased Zeroing)
PAC-WRS (Weighted Average -Wting-Based Zeroing)
Test accuracies (y-axis) over timestep (æ-axis) for PAC-WRS with reservoir size 64 using exponential weighting on all 16 tested datasets. Light grey lines: test accuracies of the PAC baseline methods at each timestep. Solid black lines: test accuracies of the "oracle" models, computed as the cumulative maximum of the PAC baselines. Blue: corresponds to PAC-WPR CRR variants ensembled via simple averaging. Red: corresponds to PAC-WRS variants ensembled via weighted averaging. Dotted lines: indicate whether voting- based zeroing was applied for additional sparsity.
Figure 29;
47

---

Avazu
Avazu
Criteo
Dexter
0.20
01355
0.3
0.590
0.8
0.305
0.310
0.590
1.0
Dorothea
<DD2010 (Algeora)
MNISTB (4+9)
News20
0.8
0.5
0.9
0.5
0.3
2.5
0.5
0.7
000000
4000
Newssroups (Binary, CS)
PCMAC
RCV1
Roal-Sim
0.8
0.5
0.0
0.4
0.4
S5T-2
URL
WBA
Webspam
3.0
1.50
0.5
0.94
0.4
0.7
0.52
0.40
PNC-WRS (Simple Averagel
PAC-WRS (Weighted Average)
PAC
PAC-WRS (Simple Average voting-Based Zeroing)
PAC-WIR (Weighted Average Voting-Besed Zeroing)
Orecle
Figure 30: Sparsity (y-axis) over timestep (æ-axis) for PAC-WRS with reservoir size K 64 using exponential weighting on all 16 tested datasets. Light grey lines: sparsities of the PAC baseline methods at each timestep. Blue: corresponds to PAC- WRS variants ensembled via simple averaging. Red: corresponds to MRR variants ensembled via weighted averaging. Dotted lines: indicate whether aating-based zeroing was applied for additional sparsity.
48

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Please see our Abstract and Introduction.
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 or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long 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: Please see Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are 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 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.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to 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 address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't 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 complete (and correct) proof?
Answer: [Yes]
49

---

Justification:
Please see Section 3.2 and Appendix
A
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 referenced in 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 to provide short proof sketch 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 affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Please Section and Appendix B
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or 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 is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS 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) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either 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 to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers 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?
50

---

Answer: [Yes]
Justification: Please see our GitHub at htwp://hwww...uuuuuooouuunnnnn.a
Sww.roo--SSamppinnuuuggneeee Taaemeenntt-Taniingrrremmmii with detailed README.cm md file.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurlPS code and data submission guidelines (https www.:Suwwisssispoooooooooooooooi
/nipss.cc/pulli//uuui
for more details.
The authors should provide instructions on 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 is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Please see Algorithm 1 Section 4 and Appendix B as well as GitHuu at hntps://github.comm
http://eeeeeoooonnnn///e/eeeeeee Augmented-Tieee Trainingttre/main
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 a 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, supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Please see error bars and significance tests in Section and Appendix G.I
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror 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.)
51

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 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 error rates).
If error bars are reported in tables or 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 to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Please see Appendix B
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
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 into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with NeurlPS Code of Ethics http:////...a....c////////////ta
Answer: [Yes]
Justification: We have carefully read the NeurIPS Code of Ethics and have made sure that our research conforms to it.
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 circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there special consid- eration due to laws or regulations in 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: This paper introduces a foundational research method that does not have any direct paths negative societal impacts, aside from the general interactions of machine learning with society.
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 no societal impact why the paper does not address societal impact.
52

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment 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 to 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 to 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 negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
This paper does not involve any data or models that have high risk for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-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
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We enumerate and cite all datasets in Table Aside from our own preprocessed versions of Newsgroups (Binary, CS) and SST-2, the 14 other datasets are all publicly available.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the 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.
53

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/dataseta
datasets.papersstt
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 has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [Yes]
Justification:
Please see the README. md file in our accompanying GitHub htt.rrgiieeeeeeeeeerrrraanaannnn
Training/tree/min
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/mooell as part 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 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 details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing or work with human subjects was performed for this paper.
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 of Ethics, workers involved in data collection, curation, or 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 to 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 have any study participants and/or crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
54

---

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 we 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 as the institution conducting the review.
55


Reviews:
[{"review_id": "bRtiIkpGJL", "reviewer": "Reviewer_m761", "summary": "The paper seeks to address the issue of instability in passive-aggressive (PA) online learning algorithms, which are highly sensitive to individual data points, particularly outliers. These instabilities can lead to significant fluctuations in the model's accuracy, especially when an outlier is encountered late in the data stream. To mitigate this, the authors propose a novel approach called Weighted Reservoir Sampling (WRS), which augments the standard PA learning process by maintaining a reservoir of high-quality weight vectors that are less prone to overfitting due to outliers. This method is tested on two PA algorithms—Passive-Aggressive Classifier (PAC) and First-Order Sparse Online Learning (FSOL)—across several datasets, showing that WRS significantly stabilizes accuracy without the need for additional data passes or hold-out sets.", "questions": "Maintaining a reservoir of high-quality weight vectors adds computational overhead, particularly in terms of memory usage and processing time. While the paper claims this overhead is minimal, I would like to see if there are more detailed analysis or comparisons with baseline methods in terms of computational efficiency.", "limitations": "na", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality:\nThe introduction of Weighted Reservoir Sampling (WRS) as a method to stabilize PA algorithms is a novel contribution. The idea of leveraging the number of passive updates as a proxy for the quality of solutions is innovative, especially in the context of online learning.\n\nQuality:\nThe paper is methodologically rigorous, providing a thorough theoretical analysis to support the proposed WRS method. The empirical validation across multiple datasets strengthens the claim that WRS enhances the stability of PA learning algorithms.\n\nClarity:\nThe paper is well-written and clearly explains the problem, the proposed solution, and the results. The step-by-step presentation of the WRS method, along with detailed explanations of the experiments, makes the paper accessible to readers familiar with online learning.\nThe authors also use lots of wrap tables, making best use of the space. \n\nSignificance:\nThe significance of the work lies in its potential to improve the robustness of PA algorithms in real-world applications, where data streams often contain noisy or outlier data points. This method could be particularly valuable in fields like online advertising, real-time recommendation systems, and other high-dimensional streaming data applications.", "weaknesses": "Limited Applicability:\nWhile the WRS method is shown to work well with PAC and FSOL, its applicability to other online learning algorithms, especially those that are not passive-aggressive, is not explored. This limits the generality of the method.\n\nAssumption on Data Distribution:\nThe method assumes that the data distribution remains relatively stable over time. However, in real-world scenarios where data distributions might shift (concept drift), the effectiveness of WRS may diminish. This limitation is acknowledged but not deeply explored in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mcIoieu5Vv", "reviewer": "Reviewer_v2Wj", "summary": "The paper proposes a new algorithm for a binary online learning problem where the streaming data consists of i.i.d. samples. The authors propose a variant of the seminal algorithm of Passive-Aggressive classifier. The PAC algorithm only updates its current model when a missclassification occurs. The main idea of the paper is to augment this algorithm with a weighted reservoir sampling of previous models,  where the weight of each model is proportional to how much the model “lived” before an update occurs. At each time step $t$, the weighted ensemble solution from the reservoir is used for prediction. \n\nThe paper presents theoretical results for the risk of their algorithm, and conduct experiments to show the superiority of the methods compared against 2 online algorithm baselines.", "questions": "See above.", "limitations": "The paper discusses limitations in the conclusion.", "rating": 3, "confidence": 4, "soundness": 1, "presentation": 2, "contribution": 2, "strengths": "The idea of using reservoir sampling for a online algorithm is novel, and I have not seen it before. \n\nThe experimental section seems throughout, and a lot of datasets are used for the comparison with the baselines.", "weaknesses": "I believe that the theory is the weaker part of this paper. Also, the comparison with the previous baselines is not very well motivated.\n\nI am confused by the theoretical setting of this work. In online learning, it is often assumed that the data is generated by an adversary and it does not come from the same distribution. For example, the analysis of [1,5] (baselines used and described by this work) never uses this assumption, and they upper bound measures of error related to regret (also this inconsistency is in line 3-4 of abstract). In this context, there is no distribution, so the sentence at line 64 is false “The goal is that as t goes to infinity, w_t will generalize well to out-of-sample examples” (there is no distribution to generalize w.r.t., and the examples are not samples from a distribution).  I think this is the case for the analysis of the online algorithms described in Lines 65-74 other than [1,5] (I did not check)\n\nTo this end, the PAC (and FSOL) algorithm is trying to solve a different problem. The intuition that a solution is more promising if it is correct for a longer period of time only applies if the data is i.i.d., which is a different problem from the one of the paper introducing PAC. The same concern applies to the experimental section, where due to the random split (and thus shuffling) of the data, it can be considered as i.i.d., which is a different setting than the online learning setting.\n\nThe theoretical results (Thm 1 and Thm 2) are very hard to interpret, and it is unclear whether they provide any meaningful contribution. \n\nIf the data is i.i.d., a desirable property is that the gap between R_D(w_T) and R_D(w^*) goes to zero as T goes to infinity, where $w_T$ is the model of the algorithm at time $T$ (i.e., once I observe a large amount of data, my error converge to the error of $w*$), most likely with rate 1/sqrt(T). Alternatively, if I do not assume that the data is i.i.d. and I focus on a online setting, I would like to see an upper bound to the regret of order O(sqrt(T)). [This could possibly also imply the former with an online to batch conversion].\n\nAdditionally, both Thm 1 and Thm 2 are very hard to read. The definition of $r_m$ is unclear (isn’t the minimum risk achievable by any model w always less than R_{D}(w^*)?).  What is $r_m^{K}$ and $r_m^{K+1}?$.\n\nTheorem 2 depends on assumptions on the models stored by the algorithm that are unclear whether they are ever satisfied. Theorem 2 has dependencies on those assumptions that make it unclear whether the result is ever meaningful (e.g., is the probability of Thm2 ever $\\geq 1/2$)? Also, what is $\\epsilon$ in Thm 2 and lines 185-189 ( is it arbitrarily chosen?).\n\nI found lines 168 confusing. It seems that R(h) is defined but never used in the main paper, only R_{D}(w). Also it is unclear to me on what loss is used, since l(w,z) is previously defined as the hinge loss, but l(h,z) is the 0-1 loss (81).\n\nSuggestions: I would formally define concepts outside of related work (e.g, sparsity in line 73-74).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Also, the comparison with the previous baselines is not very well motivated. \n\nThe 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.\n\n> I believe that the theory is the weaker part of this paper.\n\nWe 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.\n\nWe 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. \n\nWe 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.\n\nWe 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. \nFirst, 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$.\n\n(1) risk($w\\_{wrs}$) <= WAvg(risk($w\\_t$)) (Jensen's inequality)\n\n(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\n\n(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)$.\n\n(4) regret($w^*$) $\\leq$ risk($w^*$) + error3 w.h.p. (Hoeffding bound). The error3 term is the $C \\sqrt{ \\log(2/\\delta) / (2T)}$ term\n \nCombining the steps and using union bound gives our result.\n\nSpecific theory qs:\n\nDefinition 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.\n\nThm 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.\n\nOur 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. \n\n$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$. \n\n[1] Cesa-Bianchi N, Conconi A, Gentile C. \"On the generalization ability of on-line learning algorithms.\" (2004).\n\n[2] Cesa-Bianchi N, Claudio G. \"Improved risk tail bounds for on-line algorithms.\" (2008).\n\n[3] Dekel O. \"From online to batch learning with cutoff-averaging.\" (2008).\n\n> Suggestions: I would formally define concepts outside of related work (e.g, sparsity in line 73-74).\n\nWe 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.\"", "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": "FWy4tnCRlL", "reviewer": "Reviewer_We6T", "summary": "This paper resolves the outlier sensitivity problem in online learning. The proposed approach (WAT) can stabilize passive-aggressive online learning algorithms and does not introduce common overheads like hold-out evaluation sets or additional passes.", "questions": "1. Can the authors provide more detailed explanations on how intermediate weight vectors are selected and maintained in the reservoir, and discuss the impact of different reservoir sizes on the algorithm's performance?\n\n2. I think more compared baselines are needed, such as ADAGRAD or Truncated Gradient.", "limitations": "This paper comprehensively discusses its limitations regarding the requirements for base and the assumptions on data distributions.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. The proposed WAT shows a significant reduction in test accuracy fluctuations.\n\n2. WAT maintains, and in some cases, enhances the sparsity of solutions in FSOL, which is crucial for high-dimensional data.\n\n3. The implementation of WAT does not require additional passes over the training data or hold-out evaluation sets.", "weaknesses": "1. While FSOL-WRS shows statistically significant improvements in final test accuracy, PAC-WRS does not consistently show the same level of improvement.\n\n2. Although minimal, there is still an additional memory and computational overhead associated with managing the reservoir of candidate solutions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> While FSOL-WRS shows statistically significant improvements in final test accuracy, PAC-WRS does not consistently show the same level of improvement.\n\n\nThis 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. \n\n\nWe 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).\n\nOn 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:\n\n| Dataset                 |   PAC-WRS |       PAC |   FSOL-WRS |      FSOL |\n|:------------------------|----------:|----------:|-----------:|----------:|\n| Avazu (App)             | -7.3e-05  | -0.595765 |  -5.3e-05  | -0.576633 |\n| Avazu (Site)            | -4.6e-05  | -0.012645 |  -5.2e-05  | -0.127786 |\n| Criteo                  | -0.000139 | -0.007106 |  -0.000356 | -0.088427 |\n| Dexter                  | -0.005556 | -0.057778 |  -0.011111 | -0.193333 |\n| Dorothea                | -0.001739 | -0.005797 |  -0.003478 | -0.868986 |\n| KDD2010 (Algebra)       | -1.1e-05  | -0.02043  |  -8.6e-05  | -0.108299 |\n| MNIST8 (4+9)            | -0.000174 | -0.150834 |  -0.000457 | -0.171815 |\n| News20                  | -0.00137  | -0.335327 |  -0.002572 | -0.337632 |\n| Newsgroups (Binary, CS) | -0.002111 | -0.159265 |  -0.002912 | -0.27692  |\n| PCMAC                   | -0.00446  | -0.064151 |  -0.004803 | -0.185592 |\n| RCV1                    | -0.000152 | -0.160971 |  -0.000159 | -0.097962 |\n| Real-Sim                | -0.00048  | -0.173778 |  -0.000554 | -0.133466 |\n| SST-2                   | -0.000832 | -0.120622 |  -0.000881 | -0.061439 |\n| URL                     | -6.2e-05  | -0.071025 |  -0.00034  | -0.122971 |\n| W8A                     | -0.000371 | -0.090931 |   0        | -0.777236 |\n| Webspam                 | -0.000491 | -0.112117 |  -0.00075  | -0.273266 |\n\nThe 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. \n\n> Can the authors provide more detailed explanations on how intermediate weight vectors are selected and maintained in the reservoir?\n\nSee additional comment due to space limitation. \n\n> Although minimal, there is still an additional memory and computational overhead associated with managing the reservoir of candidate solutions.\n\nYes, 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.*\n\n> [Can the authors] discuss the impact of different reservoir sizes on the algorithm's performance?\n\nOn 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.\n\n\n> I think more compared baselines are needed, such as ADAGRAD or Truncated Gradient.\n\nThank 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.", "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": "sB2yO3PU2m", "reviewer": "Reviewer_eWmu", "summary": "Passive-aggressive algorithm is a seminal method in online learning. However, it may be unstable when outliers arise. This paper uses weighted reservoir sampling to stabilize the linear passive-aggressive online learning. The key idea is that the subsequent number of passive steps can reflect the generalization error. Then the weighted reservoir sampling is used to sample the models with low generalization error. The final model is the ensemble of the sampled models.", "questions": "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.", "limitations": "None", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is clear and easy to follow. The proposed method makes a good use of the characteristic of the passive-aggressive algorithm. The experiments show the superiority of the proposed method.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">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.\n\nOur 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.\n\nPlease also see the response to reviewer v2Wj and the one-page PDF; we have added a new theory that strengthens the manuscript.\n\n> 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.\n\nThank 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.", "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": "0Y08Yt6Rj6", "reviewer": "Reviewer_NvJo", "summary": "The authors are interested in sequential learning algorithms, within an IID data setup. That is, the ultimate objective is expected loss for a single algorithm output, not the regret incurred by a sequence of candidates. More specifically, they are interested in linear binary classification, and their overarching goal is to design an algorithm which is less sensitive to idiosynchratic data points, especially those near the end of the learning process.\n\nBroadly speaking, their proposal is a procedure to construct a weighted sum of \"good candidates\" for the final algorithm output, ideally being far less sensitive to outliers that can take traditional online learning algorithms astray. Their procedure \"wraps\" around a base update (here, PAC or FSOL), and selects candidates for inclusion in a \"reservoir\" in a stochastic fashion, and the core mechanism underlying their weighting is to use the number of \"passive steps\" as an indicator of quality. Passive steps are those steps, given a certain candidate, where the 0-1 loss is zero (i.e., correct classification) and no updates are made.\n\nThe underlying idea itself is heuristic, but the authors provide theoretical analysis in the form of risk bounds for candidates selected based on the number of cumulative passive steps. Essentially, when the minimum achievable risk is small, the passive step-based choice is not likely to be much worse than the best choice among the stocked candidates. They also conduct a series of empirical tests, which suggest that their proposed approach can be applied in a straightforward way to achieve better accuracy and stability when compared with the base procedure their algorithm wraps around, on a variety of datasets.", "questions": "I do not have any critical questions for the authors. For the most part, I get their idea and I understand the investigation that they have carried out. Below is a handful of small points I tripped up on while reading the paper.\n\n- Abstract, *\"Our reservoir thus contains $K$ previous intermediate...\"*: here $K$ really has no meaning at all. Why not just say \"a subset of previous intermediate weight vectors...\" or something?\n\n- First sentence of 2.1: If my reading is correct, the first time \"linear binary classification\" is mentioned is here at the start of 2.1. I think most readers, having read up to this point (including the abstract!), will be shocked that the scenario considered by the authors is so narrow. This should be established earlier, and more clearly.\n\n- The symbol $T$ is used for iteration numbers as well as for transposing the weight vector in the main equation presented in 2.1 (for $\\\\hat{y}^{\\\\ast}$); this should be avoided if possible.\n\n- Reading through 2.3, I found the WRS exposition to be quite mysterious. What in particular about the problem being studied here makes WRS a natural fit? What parts of Algorithm 1 use the original WRS as-is, and which parts are original? It's not clear to me.\n\n- 3.2, *\"A given online learning algorithm outputs model $\\\\mathbf{w}\\_{t}$ after seeing $z\\_{t}$, with loss $\\\\ell(\\\\mathbf{w}\\_{t},z\\_{t})$\"*: I found this sentence clunky. Shouldn't the *output* be $\\\\mathbf{w}\\_{t+1}$, considering we have seen the data and loss for step $t$ already?\n\n- 3.2, third paragraph: thus far the \"model\" has been characterized by $\\\\mathbf{w}_{t}$ or simply $\\\\mathbf{w}$, but suddenly here $h$ appears. Plus, the $x$ here (not bold) is inconsistent with previous data notation.\n\n- 3.2, fourth paragraph: how are the *\"updated models\"* $\\\\mathbf{w}^{(j)}$ defined? What is $\\\\mathcal{J}$? This is all totally unclear.\n\n- Algorithm 1, line 15: this critical definition of $k^{\\\\ast}$ includes $w\\_{t}$, an undefined quantity. The only place I can find it is earlier in 2.3, regarding \"weights\" used in WRS. Are these supposed to be pre-fixed?\n\n- Algorithm 1, line 16: here $T$ is used as a \"threshold\" of sorts, but notation clashes with $T$ used for the number of iteration in the for-loop.\n\n- Algorithm 1, line 19: to update \"accordingly\" means what? Are the elements supposed to be paired up with elements of $\\\\mathcal{R}$, so that when an element is removed from $\\\\mathcal{R}$, the corresponding elements in $\\\\mathbfit{b}$ and $\\\\mathbfit{k}$ are removed as well? This is unclear. I can infer it from line 29 with some confidence, but readers shouldn't have to infer such things.\n\n- Algorithm 1, lines 27 and 29: the use of $\\\\mathbf{w}\\_{r}$ is bad notation; withing Algorithm 1, $\\\\mathcal{R}$ is said to be a set of promising solutions, but here it magically transforms into a set of the *indices* of promising solutions. This is even more problematic because $\\\\mathbf{w}$ with no index subscript is all we have within Algorithm 1, so $\\\\mathbf{w}\\_{r}$ is effectively undefined in this context. Note it also completely clashes with $\\\\mathbf{w}\\_{r} \\\\in \\\\mathcal{R}$ used in line 32.\n\n- Algorithm 1: when WS is \"Standard\", then $b^{\\\\ast}$ is updated, but under AS as \"Simple Average,\" $b^{\\\\ast}$ plays no subsequent role; is this correct? If so, considering the fact that \"Simple Average\" performs very similarly to \"Weighted Average,\" one wonders if the passive-step count based approach is actually meaningful at all. Note also that the critical $k^{\\\\ast}$ check in Algorithm 1 is unclear due to the undefined $w\\_{t}$.", "limitations": "Limitations have been discussed.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The authors present a procedure which is intuitive, can be given some theoretical grounding, and appears to work well in practice. The paper is well-structured, and the writing (aside from some technical points to be mentioned later) is very clear. While the basic idea of taking a weighted sum of good candidates to \"smooth out\" the performance of sequential learning algorithms is a well-studied tactic, the authors consider a rather unique approach applying weighted reservoir sampling to passive-aggressive base algorithms.", "weaknesses": "While I highlighted writing clarity as one of the paper's strengths, I found the methodology presented here rather difficult to understand. The WRS approach is positioned as a central part of the authors' strategy, but what part of Algorithm 1 is specific to WRS? If we remove the uniformly sampled random variable and just determine inclusion in the $K$-sized set of candidates by the number of passive steps, would things really change all that much for the worse?\n\nIn 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.\n\nFinally, 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](https://arxiv.org/abs/1903.00974), and so forth).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> 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.\n\nThank 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:\n\n- Abstract: We will replace K with \"a subset of intermediate weight vectors\" as recommended.\n- We will update the last sentence of our abstract to \"We demonstrate our WRS approach for binary linear classification with the Passive-Aggressive...\" \n- We will use the correct symbol '\\top' for transpose.\n- 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.\n- Agreed, we will fix to $\\boldsymbol{w}_{t+1}$\n- Thank you for catching our oversight, we will change $h$ to $\\boldsymbol{w}$ and bold x\n- $\\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}$\".\n- Algo 1, line 15: Thank you for catching our typo. The correct symbol should be $b^*$, rather than $w_t$.\n- Algo 1, line 16: We agree that using $T$ creates notational clash. We will instead use $\\tau$ for threshold.\n- 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. \n- 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]$.\n\n> Algorithm 1: when WS is \"Standard\", then $b^\\*$ is updated, but under AS as \"Simple Average,\" plays no subsequent role; is this correct?\n\nYes, 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.\n\n> 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).\n\nWe 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.", "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:
For all reviewers, insufficient time exists for us to run all datasets under all settings. In our responses below, we have results for 14 out of 16 datasets (for $K=64$). The largest two (Criteo and Avazu (Site)) could not be completed in the allotted time. KDD2010 is further a partial result, as not all jobs have finished all of the KDD2010 set. Because we are studying an online algorithm, we can share the partial-epoch results as they exist today. Camera-ready will have no issues getting all experiments done on time.  The general trends are very clear from these 14 datasets, though, with WRS's advantage increasing as datasets tend to get larger.

## Additional Base Models: Stochastic Gradient Descent with Momentum (SGD+M), Truncated Gradient Descent (TGD), and AdaGrad.

We thank Reviewers We6T and eWmu for encouraging us to explore additional baseline methods' test accuracy performances over time, and their particular suggestions of Stochastic Gradient Descent with Momentum (SGD+M), Truncated Gradient Descent (TGD), and AdaGrad. 

In general, these three additional base algorithms are **still susceptible to experiencing concerning fluctuations in test accuracy.** For example, in Figure 2 of our 1-page rebuttal PDF, we see that on MNIST8 (4+9), SGD+M and TGD both experience significant fluctuations in test accuracy over time. On this particular dataset, AdaGrad did not experience significant fluctuations.

Note that these 3 new baselines are not Passive-Aggressive algorithms (they always update the weight vector), and so WAT is performing well despite being pushed beyond its designed purpose.  To test these 3 baselines, we defined a pseudo-passive step as one that makes no classification error, and took the last weight vector before a mistake was made. The rest of WAT operated as normal under this pseudo-passive step weighting. 

**Critically, we find that for all three of SGD+M, TGD, and AdaGrad, our modified WAT effectively mitigates test accuracy instability when it exists, and does no harm when it does not.** For example, referencing Figure 2 in our 1-page rebuttal PDF, modified WAT significantly improves test accuracy stability on SGD+M and TGD, even achieving performance higher than that of the corresponding oracles. On AdaGrad, where the test accuracy was already rather stable, adding modified WAT still yields a slight increase in stability. As such, our WAT method is still useful and adaptable to a wider class of base models, which can constitute fruitful future work.

This will be added to the manuscript, which shows that WAT has more general utility in stabilizing online algorithms even if they are not PA.

## Additional Wrappers

We thank Reviewers We6T and NvJo for encouraging us to think more about the computational overhead of our WRS-augmented training (WAT) method, and to compare our WAT wrapper against alternative averaging strategies. Below, we compare WAT against averaging the $K$ most recent candidates (which we denote as *moving average*) and downweighting over time (which we denote as *exponential average*). Specifically, for both WAT and moving average, we use $K=64$. For exponential average, at timestep $t$, we recursively form our ensemble vector $\bar{\mathbf{w}}\_t = \gamma \mathbf{w}\_t + (1-\gamma)\bar{\mathbf{w}}\_{t-1}$ (using $\gamma = 0.9$), where $\mathbf{w}\_t$ is the base algorithm's candidate solution at timestep $t$. This recursive update rule indeed exponentially downweights the contribution of previous candidate solutions $\mathbf{w}\_t$.

Overall, we first find that the exponential average scheme is consistently ineffective at mitigating the test accuracy instability of the base models PAC and FSOL. The stability of the exponential average scheme is usually not much better than that of the base model, which makes sense because it still puts the majority of the weighting on the most recent candidate solution. We invite the reviewer to observe the results of exponential average on Avazu (App), KDD2010 (Algebra), RCV1, and MNIST8 (4+9) in Figure 1 of our 1-page rebuttal PDF, drawing the reviewer's attention to the massive oscillations of the red lines.

Second, we find that the $K=64$ moving average also has very mixed effectiveness. On some datasets, like RCV1 and MNIST8 (4+9) in the aforementioned Figure 1 (indicated by the blue lines), it performs only slightly worse than WAT. However, on other datasets like Avazu (App) and KDD2010 (Algebra), it performs significantly worse compared to WAT in terms of stabilizing test accuracy. This makes sense because, with WAT, we are much more selective about the quality of the candidate solutions that we retain in our reservoir, compared to moving average, which necessarily must include poor-performing solutions as they appear.

Third, from Table 1 in our 1-page rebuttal PDF, we find that for datasets with dimension $D > 100K$, **the moving average method can be significantly computationally slower per iteration than WAT.** For example, with PAC as base model, the moving average method is, on average, $10 \times$ slower per iteration than WAT on URL, and $8.357\times$ slower per iteration than WAT on Avazu (App). Similar trends hold when using FSOL as base. This makes sense because with WAT, we do not always add candidate solutions to our reservoir/set for averaging, while with the moving average method, we must always add new candidate solutions into our set. These insertion and deletion costs will accrue over time. On smaller datasets the moving average is faster or slower depending on dataset, but runtime is dominated by IO and all methods finish within minutes. This shows that in more real-world, large-scale settings where evaluation and checking are expensive, WAT is the fastest, most accurate, and most reliable method compared to all baselines.

Meta-review: After reviewing the submission, reviewer comments, robust author rebuttal, and further discussion with reviewers, I recommend accepting this paper (poster).  The author rebuttal goes a long way towards addressing the majority of reviewer criticisms, including expanding the use of WRS to additional base online learning algorithms and additional baseline stabilizing approaches (moving/exponential averaging), both of which further strengthen the message of the paper and I would expect to see in the final version of the paper.  Finally, the other main criticism I think arises from the fact that this work studies online learning in the iid setting, which I agree is an important setting worth studying. But this should be clarified and discussed early on in the work to correctly set expectations.
Decision: Accept (poster)