Stabilizing Linear Passive-Aggressive Online Learning with Weighted Reservoir Sampling

Online learning algorithms are especially attractive when working with high-volume and high-dimensional streaming data, out-of-core processing, and other throughput-sensitive applications [1]. For example, the seminal Vowpal Wabbit uses importance-weighted online learning algorithms [2] to reach high quality solutions quickly, with an optional second pass using LBFGS to 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 as web spam classification [1]. 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, in 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 precipitously between timesteps. Indeed, in many cases (see Figure 1), an online learning algorithm might achieve over $90\%$ test accuracy after a given timestep, but then see its test accuracy drop by $20-30\%$ after over-correcting on the next observation in the data stream. In many real-world settings, it may be infeasible computationally or memory-wise to maintain a hold-out evaluation set to select the highest-performance solutions learned by our online algorithm. It may also be practically infeasible to train our classifier over multiple passes of a given dataset or when online algorithms are used for “any-time” ready predictions.

In this paper, we introduce a weighted reservoir sampling (WRS) [4] based approach that dramatically mitigates the aforementioned accuracy fluctuations. Our proposed method, WRS-Augmented Training (WAT), neither requires a 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) [1] methods — creating two new methods PAC-WRS and FSOL-WRS. Strikingly, across 16 benchmark datasets, WAT is able to mitigate test accuracy fluctuations in all 16 datasets on FSOL and 14 datasets on 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.

Our work is motivated in part by a real-world need in malware detection [6], in which large datasets make online methods particularly attractive [7, 8], and a naturally noisy labeling process inhibits standard passive-aggressive methods [9, 10, 11, 12]. We show results for the EMBER malware benchmark in Appendix C.

Online learning. In online learning for linear binary classification, one maintains a solution vector $\mathbf{w}_{t}\in\mathbb{R}^{D}$, where $D$ is the dimensionality of our data points (usually quite large), and $t$ represents the timestep. At each timestep $t$, we observe a single observation $(\mbox{\boldmath$x$}_{t},y_{t})$ from a high-throughput data stream, with feature vector $\mbox{\boldmath$x$}_{t}\in\mathbb{R}^{D}$ and class label $y_{t}\in\{+1,-1\}$. Given $(\mbox{\boldmath$x$}_{t},y_{t})$, an online learning algorithm will make a minor (potentially no effect) update to $\mathbf{w}_{t}$ to output $\mathbf{w}_{t+1}$, before receiving the next $(\mbox{\boldmath$x$}_{t+1},y_{t+1})$ in the data stream. The classification rule using $\mathbf{w}_{t}$ on any test point $\mbox{\boldmath$x$}^{*}$ is simply $\hat{y}^{*}=\mbox{sign}(\mathbf{w}_{t}^{\top}\mbox{\boldmath$x$}^{*})$. The goal is that as $t\to\infty$, the sequence of $\mathbf{w}_{t}$ will enjoy low cumulative loss. Towards this end, many online learning algorithms with various update rules have been proposed in the literature, including the Passive-Aggressive Classifier (PAC) [5], the Adaptive Regularization of Weight Vectors (AROW) methods [13] and the Adaptive Subgradient method (ADAGRAD) [14]. Some online learning algorithms have also been designed to specifically learn sparse solutions for $\mathbf{w}_{t}$ (proportion of zero entries), such as Truncated Gradient method [15], Stochastic MIrror Descent Algorithm made Sparse method (SMIDAS) [16], Regularized Dual Averaging (RDA) method [17], and First-Order and Second-Order Sparse Online Learning methods (FSOL and SSOL) [1]. In general, these sparsity-inducing methods are powered by some combination of solution truncation and L1 norm minimization.

Passive-aggressive online learning. Within the family of online learning algorithms, a passive-aggressive algorithm is one whose update rule makes no update to $\mathbf{w}_{t}$ if $(\mbox{\boldmath$x$}_{t},y_{t})$ is classified correctly with sufficient margin. That is, we passively leave $\mathbf{w}_{t+1}=\mathbf{w}_{t}$. If a margin error occurs, we aggressively update $\mathbf{w}_{t+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 is defined using the hinge loss $\ell$ — the algorithm remains passive at timestep $t$ if $\ell\left(\mathbf{w}_{t};\left(\mbox{\boldmath$x$}_{t},y_{t}\right)\right)=\max\left(1-y_{t}\mathbf{w}_{t}^{\top}\mbox{\boldmath$x$}_{t},0\right)=0.$ Next, we introduce the two passive-aggressive algorithms that we will use to test our WRS-Augmented Training method.

Passive-Aggressive Classifier (PAC). Introduced by Crammer et al., PAC is actually a family of three algorithms: PA, PA-I, and PA-II [5]. The base PA algorithm update rule seeks to solve the following constrained optimization problem:

Because of the hard constraint of forcing $\mathbf{w}_{t+1}$ to satisfy $\ell(\mathbf{w};(\mbox{\boldmath$x$}_{t},y_{t}))=0$, the optimization is particularly vulnerable to noisy data. As such, Crammer et al. introduce a new constrained optimization function with a slackness hyperparameter $C_{err}$ to allow for some residual hinge loss and induce less aggressive, but presumably more stable updates:

where setting $m=1$ 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]: $\mathbf{w}_{t+1}=\mathbf{w}_{t}+\frac{\ell(\mathbf{w}_{t};(\mbox{\boldmath$x$}_{t},y_{t}))}{\|\mbox{\boldmath$x$}_{t}\|^{2}+\frac{1}{2C_{err}}}y_{t}\mbox{\boldmath$x$}_{t}.$ For the remainder of this paper, “PAC" will refer to PA-II.

First-Order Sparse Online Learning (FSOL). Introduced by Zhao et al. [1], FSOL is a passive-aggressive algorithm which attempts to find sparse solutions for $\mathbf{w}_{t}$. Governed by a learning rate $\eta$ and a sparsity parameter $\lambda$, FSOL keeps track of two vectors $\mbox{\boldmath$\theta$}_{t},\mathbf{w}_{t}\in\mathbb{R}^{D}$ and performs the following update rules when in aggressive mode [1]:

where $\lambda_{t}=\eta\lambda$ and $[\mbox{\boldmath$v$}]_{+}$ 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, 1].

Weighted Reservoir Sampling (WRS). Suppose we have a collection of items $V=\{\mbox{\boldmath$v$}_{1},\dots,\mbox{\boldmath$v$}_{T}\}$, with corresponding nonnegative weights $w_{1},\dots,w_{T}$. 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$ weighted random sample under the aforementioned conditions. Specifically, as we are making our one pass through the items in $V$, at each timestep $t$, we maintain and update a reservoir — a temporary storage unit with a maximum capacity of $K$ items, with each item in the reservoir a potential candidate for our final size-$K$ sample. At time $T$, the $K$ items that are currently in the reservoir will constitute our sample of size-$K$. We invite the interested reader to look at Algorithm A in [4] for specific details.

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 the cumulative loss $M_{T}$ of the algorithm over any sequence of data, compared with a minimal-loss fixed model $\hat{\mathbf{w}}$: $\mathrm{reg}_{T}\coloneqq\sum_{t=1}^{T}\ell(\mathbf{w}_{t};z_{t})-\sum_{t=1}^{T}\ell(\hat{\mathbf{w}};z_{t})=M_{T}-\sum_{t=1}^{T}\ell(\hat{\mathbf{w}};z_{t})$. When using a fixed model to classify unseen data, we need to impose an i.i.d. assumption on the data stream in order to measure the risk, or expected generalization error, of the model. Note that the distribution $\mathcal{D}$ itself is arbitrary and can still permit outliers or mixtures. Then the population risk is defined as $R_{\mathcal{D}}(\mathbf{w})\coloneqq\mathbb{E}_{z\sim\mathcal{D}}[\ell(\mathbf{w};z)]$.

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 pocket approach, which selects the longest-surviving model in the sequence as the final model [18, 19]. Other well-known approaches use the uniform average of the whole model sequence or the best-performing model over a validation set [20].

As will be seen, our method generalizes these approaches to utilize multiple long-survival 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).

In one extreme, if a candidate solution $\mathbf{w}_{t}$ from a passive-aggressive algorithm had perfect classification with sufficient margin on any given data point, then the subsequent number of passive steps taken after time $t$ (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 $\mathbf{w}_{t}$ had extremely low performance, then our passive-aggressive algorithm is likely to go aggressive very soon after time $t$, implying a very small subsequent number of passive steps after time $t$. In short, our key insight is that high-performing solutions $\mathbf{w}_{t}$ 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 $\mathbf{w}_{t}$ provides an estimate of $\mathbf{w}_{t}$’s relative quality (i.e., test accuracy).

However, we do not want to take the intermediate solution $\mathbf{w}_{t}$ that had the most passive updates as this, too, can be noise (and luck) sensitive. Ideally, we would like to sample from the merging distribution of $\mathbf{w}_{t}$ 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 $\mathbf{w}_{t}$ due to intractability.

Putting these thoughts together, our WRS-Augmented Training (WAT) method functions as follows. Given a base passive-aggressive algorithm (e.g., PAC or FSOL), we will run said algorithm through our data stream $\{(\mbox{\boldmath$x$}_{t},y_{t})\}_{t=1}^{\top}$, as normal, but keep a size-$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 size-$K$, 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 a new active candidate solution. Right before we apply our aggressive mode update rule, we will add the outgoing candidate solution to our size-$K$ reservoir (and remove a current resident of the reservoir, if necessary) following the steps of the WRS algorithm. At any timestep $t$, we can form an ensemble solution $\mathbf{w}_{\textnormal{WRS}}$ by taking an average of the candidate solutions currently in our reservoir. Hopefully, at any timestep $t$, $\mathbf{w}_{\textnormal{WRS}}$ will have more stable test performance than the current active candidate solution $\mathbf{w}_{t}$.

We combine WAT with base PAC and FSOL, forming two new methods PAC-WRS and FSOL-WRS¹¹1Code available at https://github.com/FutureComputing4AI/Weighted-Reservoir-Sampling-Augmented-Training. We evaluate their performances across 16 binary classification datasets listed in Table 1. Please see Appendix B for more dataset details. We are interested in three metrics: 1) Final test accuracy: proportion of test set data points correctly-classified 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 $p_{t,\text{base}}$ be the test accuracy of our base model (either PAC or FSOL) at time $t$ and $p_{t}$ be the test accuracy of our model of interest (either base PAC, base FSOL, PAC-WRS, or FSOL-WRS). Then, define $p_{t,\text{oracle}}=\max_{\text{base}}p_{t,\text{base}}$ to be the cumulative maximum test accuracy of the base method at time $t$. In other words, $p_{t,\text{oracle}}$ represents the highest performance we could obtain if we had an oracle telling us which candidate solution vector we encountered was best. Then, define $\text{ROP}=\frac{1}{T}\sum_{t=1}^{\top}(p_{t,\text{oracle}}-p_{t})$. Intuitively, if a method has very stable test accuracy over time with minimal fluctuations, then ROP should be close to $0$, or negative (i.e. achieving a higher test accuracy than the oracle). In contrast, a large, positive ROP suggests fluctuations in test accuracy.

Because we are 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 main paper, with all figures for all datasets in the appendix. When running any algorithm (PAC, FSOL, PAC-WRS, or FSOL-WRS) on any dataset, we perform a random 70/30 train-test split. We begin by tuning the $C_{err}$, $\eta$, and $\lambda$ 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 or exponential), averaging scheme (simple vs. weighted), voting-based zeroing (True or False), and reservoir size $K\in\{1,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 $\mathrm{𝟎}$ vector. Please see more experimental details in Appendix B.

In this paper, we introduced WRS-Augmented Training (WAT), a 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, a 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-IID adaptions may be useful in the future.