Passive-Aggressive Learning with a Free Intercept

Online linear classifiers such as the Perceptron and its "aggressive" descendants learn a separating line one example at a time. Aggressive algorithms update not only when they misclassify an example but also when they classify it correctly with too little confidence. Almost all of their theory assumes the separating hyperplane passes through the origin, a so-called homogeneous halfspace. Real data seldom cooperate. Practitioners recover an intercept with a trick: append a constant feature 1 to every input and let its weight act as the bias. That trick quietly penalizes the bias as if it were an ordinary weight. It also inflates the data radius and shrinks the effective margin. On biased data, an online learner that handles the intercept directly converges 2 to 10 times faster than one that uses the constant feature (Online Learning of Maximum p-Norm Margin Classifiers with Bias).

This note proposes a version of the passive-aggressive (PA) update that has an unpenalized intercept, tolerates label noise, uses constant memory, and needs no tuning of the bias. The PA update is the closed-form rule that moves the weights as little as possible while fixing the current example's margin. The idea fits in two sentences. First, the weight vector is updated by a PA step on the difference between the incoming example and a stored example of the opposite class. Second, the intercept is not learned by gradient steps at all: it is set at each round to the midpoint between robust running quantiles of the positive and negative classes' scores. The regime where this should matter most is the one existing tricks handle worst: lopsided data, where the minority class is small and the boundary sits far from both the origin and the data mean.

Core Claim

The obvious way to give PA a free intercept does not work, and seeing why fixes the design. PA chooses the new weights by solving $\min_w \tfrac12\|w-w_t\|^2$ subject to zero hinge loss on $(x_t,y_t)$, where $w_t$ is the current weight vector and $y_t\in\{\pm1\}$ the label. If an unpenalized bias $b$ is added to this problem, it becomes degenerate. Any violation can be fixed at zero cost by moving $b$ alone, so the weights never change and the learner just chases each example with its threshold. The constant-feature trick avoids this degeneracy only by penalizing the bias. With a constant feature of value $c$, the penalty is $(b-b_t)^2/c^2$, and the trick is then exactly a bias regularizer whose strength $1/c^2$ must be chosen.

The bound arithmetic makes the cost precise. Here $R$ is the data radius and $(u,b^\star)$ a separator with unit margin. A Perceptron-type bound of $(R^2+c^2)(\|u\|^2+b^{\star2}/c^2)$ is minimized at $c^2=R|b^\star|/\|u\|$, giving $(R\|u\|+|b^\star|)^2$. When the boundary crosses the data ($|b^\star|\le R\|u\|$), this is at most four times the bias-free bound $R^2\|u\|^2$. So a perfectly tuned constant loses at most a factor of four in the worst-case bound, which matches the "margin halving" reported by Ishibashi et al. A badly tuned constant can lose arbitrarily more. And the optimal $c$ depends on the unknown $b^\star$, which moves under drift.

Our claim is that the intercept should be treated as a statistic rather than a parameter. A max-margin hyperplane with bias is equivalent to a homogeneous max-margin hyperplane over pairwise differences $x^+-x^-$ (Online Learning of Maximum p-Norm Margin Classifiers with Bias). That equivalence lets the weight update ignore $b$ entirely. The bias can then be read off the score distributions. The resulting algorithm, which we call Anchored PA, should do three things. It should match the bias-free mistake bound $R^2\|u\|^2$ up to constants, independent of $c$. It should reach the convergence speed of the best oracle-tuned constant on stationary biased data. It should beat every fixed constant when the intercept drifts.

Research Program

The algorithm keeps a weight vector $w$, a small buffer of $k$ anchors per class, and two streaming quantile trackers. Each round it predicts $\mathrm{sign}(\langle w,x_t\rangle+b_t)$. On a margin violation it pairs $x_t$ with the opposite-class anchor whose score is closest to the boundary. It then applies a PA-I or PA-II step (the noise-tolerant PA variants with a cap $C$ on the step size, from Online Passive-Aggressive Algorithms) to the homogeneous constraint $\langle w, y_t(x_t-a)\rangle\ge 2$, where $a$ is the chosen anchor. The update is closed form:

$$w_{t+1}=w_t+\tau_t\,y_t(x_t-a),\qquad \tau_t=\min\Big\{C,\ \frac{\max\{0,\,2-\langle w_t,y_t(x_t-a)\rangle\}}{\|x_t-a\|^2}\Big\}.$$

The bias is then reset to $b_{t+1}=-\tfrac12(q^+_t+q^-_t)$. Here $q^+_t$ is a running low quantile of $\langle w_{t+1},x\rangle$ over positives and $q^-_t$ a running high quantile over negatives, both computed with the current $w$ applied to the anchor buffer plus a reservoir sample. Using quantiles rather than extremes is what gives soft-margin noise tolerance on the intercept side. The quantile level is set to a target noise level, and setting it to the extreme recovers the hard-margin midpoint.

This design addresses three limitations that Online Learning of Maximum p-Norm Margin Classifiers with Bias left open. PUMMA builds on the relaxation of The Relaxed Online Maximum Margin Algorithm. It is hard-margin only, it requires pairing stored positive and negative examples without a memory guarantee, and it is not a PA method. Our design also differs from Learning General Halfspaces with Adversarial Label Noise via Online Gradient Descent, which estimates the threshold once from the mean label under Gaussian inputs and then runs non-convex ramp-loss descent on $w$. Our estimate of $b$ is re-coupled to $w$ every round and assumes no input distribution. That makes it a convex, closed-form attempt at the joint online update those authors list as open. Because it is distribution-free, we do not inherit their guarantee and do not claim to.

The analysis has three parts. The first is a mistake bound for the realizable hard-margin case. We will show that the midpoint bias with $k\ge1$ anchors per class gives at most $O(R^2\|u\|^2)$ margin violations, by tracking $\langle w_t,u\rangle$ over difference vectors (radius $2R$, margin $2$). The second is a relative-loss bound for the PA-I and PA-II variants against the best biased comparator. It has an additive term for quantile-tracking error, which we expect to scale with the fraction of label noise. The third is a drift bound: if only $b^\star$ moves, by $\Delta$ per round, the number of extra mistakes should depend on how fast the quantiles update, not on $c$. The analogous quantity for the constant-feature trick grows like $\Delta c^2$ divided by the step size. We will also build a kernel version, where the anchors are already support vectors, so that the MNIST comparisons stay on the protocol of earlier papers.

Baselines

The naive reference point is the mistake-driven Perceptron with a constant feature of 1. On MNIST with a degree-4 polynomial kernel it is reported at 1.85% error after 4 epochs (The Relaxed Online Maximum Margin Algorithm) and 1.76% after 3 epochs (A New Approximate Maximal Margin Classification Algorithm). A second naive reference is batch soft-margin SVM with a true unpenalized bias, reported near 1.1% on MNIST (A New Approximate Maximal Margin Classification Algorithm). It serves as a ceiling on accuracy, not a competitor on cost.

The strongest existing online competitors are three methods. The first is PA-I/PA-II with a constant feature whose value $c$ is oracle-tuned on the test stream (Online Passive-Aggressive Algorithms). This is the honest version of the standard trick and the main threat. The second is voted ALMA$_2$, the best reported online number on MNIST at 1.35% after 3 epochs with $\alpha=0.8$ (A New Approximate Maximal Margin Classification Algorithm). The third is PUMMA, the only existing direct-bias margin method (Online Learning of Maximum p-Norm Margin Classifiers with Bias). No reported error number for PUMMA was found on Lacuna, only its "nearly twice as fast as ROMMA" convergence on Adult and its 2–10× speedup over ALMA on synthetic biased data. We will reimplement it.

Two further baselines round out the set. One is online hinge-loss gradient descent with a separate, unregularized step size for the bias. The other is running-mean centering followed by homogeneous PA.

For fairness, every method sees identical stream orders over 10 random permutations. Every method gets the same budget of 30 configurations over its own hyperparameters ($C$, $c$, $\alpha$, step sizes, quantile level), chosen on a held-out prefix. Separately, constant-feature PA also gets a fully oracle-tuned $c$ chosen on the test stream. Anchored PA is held to a stricter standard: it uses one fixed setting of $k$ and the quantile level across all datasets. Beating the field means two things. On stationary data, Anchored PA must match oracle-tuned constant-feature PA within run-to-run noise while beating held-out-tuned PA. On data with intercept drift or strong class imbalance, it must beat oracle-tuned PA at every fixed $c$.

Two ablations isolate the key ingredient. Anchored PA with the bias frozen at zero tests whether the difference-vector weight update alone matters. Constant-feature PA with the bias overwritten each round by our quantile midpoint tests whether the bias statistic alone matters.

Why not just…?

Why not just append a constant feature and tune its value? This is the real threat. On stationary data, the factor-of-four argument above says a well-tuned $c$ gives up only a bounded constant, and it may give up even less in practice. We do not argue around this. The oracle-$c$ sweep is in the baseline set, and if it matches Anchored PA on stationary benchmarks, we will report that. The case for our method then rests on the setting where no fixed $c$ works: intercept drift and heavy imbalance. There, the best $c$ moves with $b^\star$. That case is tested directly by the drift and minority-fraction experiments below.

Why not just subtract a running mean and stay homogeneous? Centering puts the origin at the data mean, which removes the bias only if the boundary passes near the mean. With a minority fraction $p\ll1$, the boundary sits in the tail, far from the mean. The minority-fraction sweep should show centering's advantage fading as $p$ shrinks. If it does not, centering is the simpler answer and we will say so.

Why not just run gradient descent with an unregularized, separately stepped bias? This avoids the degeneracy but brings back a step size for $b$ and loses the closed-form, scale-free PA step. Perceptron-type updates also adapt their thresholds slowly, which is exactly what aggressive updating was introduced to fix (Mistake-Driven Learning in Text Categorization). It is included as a baseline with the same tuning budget, so the comparison is empirical rather than asserted.

Why not just use PUMMA? PUMMA is hard-margin and has no noise-tolerant variant. Its convergence argument relies on pairing positive and negative examples, without a fixed-memory streaming design. The label-noise experiments measure the first gap directly, and the memory comparison at matched accuracy measures the second.

Proposed Experiments

The first experiment is a controlled synthetic study modeled on the artificial biased datasets of Ishibashi et al. Inputs are Gaussian, the true intercept $b^\star$ is swept from 0 to $2R\|u\|$, the minority fraction $p$ ranges from 0.5 down to 0.01, and adversarial label noise ranges from 0 to 10%. The noise levels follow the setting of Learning General Halfspaces with Adversarial Label Noise via Online Gradient Descent, which is also run as a baseline because it is designed for exactly this distribution. We measure cumulative mistakes and the number of updates needed to reach a positive margin, plotted against $b^\star$ and $p$, with the oracle-$c$ curve overlaid. The decisive prediction: the ratio of oracle-$c$ PA mistakes to Anchored PA mistakes should stay near 1 when $b^\star$ is small, rise toward the bound's factor as $b^\star$ grows, and rise further as $p$ shrinks.

The second experiment tests intercept drift. In the synthetic stream and in the Adult dataset (whose census income task has a strong class offset), we shift the intercept partway through the stream, either abruptly or as a slow ramp, while holding $w$ fixed. We count mistakes over the following window. Anchored PA should recover in a number of rounds set by the quantile window. Constant-feature PA, at every fixed $c$, should either recover slowly (large $c$) or start from a poor margin (small $c$).

The third experiment covers real benchmarks. These are Adult, a8a, and spambase. MNIST is run one-vs-all with a degree-4 polynomial kernel, so each task is naturally imbalanced at $p\approx0.1$ and directly comparable to the reported 1.35% (ALMA$_2$), 1.63% (aggressive ROMMA), and 1.76–1.85% (Perceptron) error rates. The million-instance malicious URL stream is the most imbalanced setting. Metrics are test error, F-measure on the minority class, and online mistakes per epoch. On URL we additionally run the label-querying variant of Lu et al.'s passive-aggressive active learner (Online Passive-Aggressive Active learning), with queries driven by $|\langle w,x\rangle+b|$. The bar is their reported cost-sensitive result: near full-supervision performance while querying 0.5% to 1% of labels.

This last test is exploratory. Active Learning of General Halfspaces: Label Queries vs Membership Queries shows that querying from a fixed pool of real examples cannot beat passive learning for biased halfspaces with small $p$. So any gain on URL must come from margin efficiency, not from beating that lower bound, and we will check whether label savings shrink as $p$ falls, as the bound predicts.

The study succeeds if three things hold together. Anchored PA must match oracle-tuned constant-feature PA on stationary benchmarks with no tuning of the bias. It must beat it clearly under drift and at small $p$. And both ablations must show that the quantile-midpoint bias is the ingredient doing the work.