Online kernel learners, such as the kernel Perceptron, predict with a weighted sum of similarities to stored past examples called support vectors. Every mistake adds another stored example, so memory and per-prediction cost grow without limit as the data stream continues. This is the "curse of kernelization." The standard fix caps the dictionary at $B$ vectors and, when the cap is hit, evicts or merges vectors. Every algorithm in this line, from The Forgetron to Ahpatron, counts memory in whole vectors stored at full floating-point precision. Real devices count memory in bytes. Mixed-precision deep learning has shown that stored intermediate tensors tolerate 2–4 bits when bits are assigned by sensitivity (ActNN, Value-aware Quantization). That suggests a different budget question: under a fixed number of bytes, should a learner keep a few exact vectors or many coarse ones? And which vectors deserve the bits?
The proposal is to demote rather than delete. When the byte budget fills, low-influence support vectors are re-quantized to fewer bits instead of being projected away. Bits per vector are set by a simple allocation rule derived from how much each vector's quantization error can move the prediction. The learner thereby chooses its own point on the count-versus-precision curve. We will test whether this beats the obvious alternative of uniformly quantizing everything and raising $B$ to fill the same bytes. We treat that outcome as genuinely uncertain.
Core Claim
For a kernel $k$ that changes smoothly with its inputs (for the Gaussian kernel, its Lipschitz constant $L$ scales with one over the bandwidth), replacing support vector $x_i$ by a quantized copy $\hat x_i$ perturbs the prediction $f(x)=\sum_i \alpha_i k(x_i,x)$ by at most $L\sum_i |\alpha_i|\,\|\hat x_i - x_i\|$, where $\alpha_i$ is the vector's coefficient. With $b_i$ bits per coordinate, the uniform-quantizer error on vector $i$ is roughly $\|\hat x_i - x_i\| \approx c_i\sqrt{d}\,2^{-b_i}$. Here $d$ is the input dimension and $c_i$ is the per-vector value range. Minimizing this bound subject to a byte budget $\mathcal{B}$ gives
$$\min_{\{b_i\},\,S}\ \sum_{i\in S} |\alpha_i|\, c_i\, 2^{-b_i}\quad \text{s.t.}\quad \sum_{i\in S}\big(d\, b_i + h\big) \le \mathcal{B},$$
where $S$ is the retained set and $h$ is the fixed per-vector overhead in bits (the coefficient plus a scale factor). The solution is water-filling: $b_i \approx \log_2(|\alpha_i| c_i) + \text{const}$, rounded to a few hardware-friendly tiers (FP32, INT8, INT4, INT2). A vector is dropped only when its optimal bit-width falls below the lowest tier.
The idea mirrors ActNN's variance-driven bit allocation and V-Quant's choice to keep a few high-magnitude values exact. The difference is the unit of allocation: whole dictionary entries, weighted by their dual coefficients, rather than activation tensors. Our claim is that at small byte budgets, such a dictionary reaches lower average mistake rate than full-precision Ahpatron and Forgetron. The claim is also that it matches or beats uniform quantization with an enlarged $B$.
Relation to Prior Work
Two papers already connect reduced precision with online kernel learning, and both stop short of this question. Mixed-Precision Kernel Recursive Least Squares keeps cancellation-prone operations in FP64 (prediction error and the novelty test that decides whether to add a vector) and moves the inverse-covariance update to FP32. It reports 24–25% memory savings and up to 1.32× speedup with no accuracy loss. It also shows that uniform FP32 produces NaNs. Its support vectors stay in FP64 and it never trades count against precision. We reuse its lesson as a design constraint: margins, coefficient updates and Ahpatron's projection solve run in FP32 or higher on dequantized vectors, and only storage is compressed. QC-ODKLA quantizes messages to 3 bits in a decentralized random-feature learner with no MSE loss. It never touches a support-vector dictionary, because it has none. Its result does motivate the random-feature-plus-quantization competitor below.
The budgeted methods supply the base algorithm and the targets. Ahpatron keeps the $B/2$ largest-coefficient vectors and projects the rest onto them, achieving the tightest stated mistake bound. In our variant, the projection step becomes a demotion step that keeps the smaller-coefficient vectors at fewer bits. The Forgetron and the random-discard budget Perceptron shrink coefficients and evict. Their shrinking actually helps our scheme: older, shrunk vectors naturally fall to low tiers. Budget passive-aggressive compensates the remaining weights after pruning, the same intent as projection. The deep-learning papers (ActNN, V-Quant, Backprop with Approximate Activations) supply the quantizers: per-vector scale, optional stochastic rounding, outlier preservation. Their evidence that stored tensors tolerate 2–4 bits motivates the work, but it does not transfer automatically. Their errors average out over a minibatch gradient, whereas ours enter every prediction directly through a nonlinear kernel. For that reason stochastic rounding does not make $k(\hat x_i,x)$ unbiased, and we treat it as an ablation, not an assumption.
Research Program
We will build three things.
The first is a tiered dictionary with per-vector scale and offset, packed storage per tier, and on-the-fly dequantization inside the kernel evaluation. The evaluation fuses unpacking with the distance computation so that the overhead ActNN and V-Quant warn about is measured, not hidden.
The second is the demotion rule plugged into Ahpatron's maintenance phase and into the Forgetron. Allocation is recomputed at each maintenance event and amortized over $B/2$ rounds, as Ahpatron amortizes its solve. A vector that is promoted cannot regain lost precision, so vectors only move down tiers.
The third is analysis. We will extend Ahpatron's mistake bound with an additive term proportional to $L\sum_i |\alpha_i| c_i\sqrt{d}\,2^{-b_i}$. We expect this extension to be loose, and we will check empirically whether the term predicts which budgets favor precision over count. We also expect a crossover: precision should matter more for narrow kernel bandwidths (large $L$) and high $d$. Count should matter more for broad kernels and non-stationary streams, where tracking needs many recent vectors.
Datasets are chosen with care, because several standard benchmarks have binary or categorical features (a9a, w8a, phishing). On those, storing FP64 is simply wasteful and lossless bit-packing wins trivially. The main evidence will therefore come from continuous-feature streams: SUSY, ijcnn1, cod-rna and Census-Income. Phishing and MNIST binary pairs (8-bit native pixels) serve as controls where the fair baseline stores data in its native format. A secondary track applies storage tiering to the KRLS dictionary on Mackey-Glass, Lorenz and the synthetic 3D regression, on top of the Mixed-Precision KRLS scheme.
Baselines
The naive reference is Ahpatron with full-precision vectors at the largest $B$ that fits the byte budget. We also run a variant that stores each vector in its lossless native format, which on phishing and MNIST is far smaller than FP64. The strongest published number in this setting is Ahpatron's average mistake rate of 7.27% on phishing at $B=400$ and 23.66% on SUSY (Ahpatron). The file does not give the SUSY budget, so we will rerun Ahpatron ourselves at matched bytes rather than compare to that figure directly. For a9a, w8a, ijcnn1 and cod-rna, the file has no reported Ahpatron number, so all comparisons there are reruns.
The decisive competitor is uniform-precision Ahpatron. It stores every vector in FP16, INT8 or INT4 with per-vector scale and sets $B$ as large as the same byte budget allows. It is the simplest way to exploit quantization, and if it matches our method, the allocation rule adds nothing.
Two ablations isolate the key ingredient. The first assigns tiers randomly with the same tier histogram as our method. The second assigns tiers by age instead of $|\alpha_i|$. Together they test whether coefficient-weighted allocation, rather than mere mixing of precisions, is what helps.
For the random-feature competitor we run NOGD-style random Fourier features (Large Scale Online Kernel Classification; RFF KLMS/KRLS). Its weight vector, and the dimension $D$, are sized to the same byte budget, and it is run in FP32 and with QC-ODKLA-style 3-bit weights. The Forgetron and random-discard Perceptron are also run at matched bytes. For regression, Mixed-Precision KRLS is the baseline, and its reported result is accuracy identical to FP64 with 1.32× speedup on the synthetic task.
Every method gets the same streams, the same five random orderings, a kernel bandwidth and regularization grid of equal size tuned on a held-out prefix, and byte budgets that include all overheads (coefficients, scales, packing). Beating Ahpatron requires a lower mean mistake rate across orderings at two or more of the four budgets we sweep, on at least three of the four continuous datasets. Beating uniform quantization requires a consistent gap beyond ordering variance, and we will report it either way.
Why not just…?
Why not just quantize everything uniformly and raise $B$? This is the real threat, and the proposal is built to settle it rather than assume it away. The bound above predicts that uniform allocation wastes bits on low-$|\alpha_i|$ vectors. Coefficients in budgeted Perceptrons are heavy-tailed, especially after Forgetron-style shrinking. The prediction fails if coefficients are close to uniform, or if mistake rate is limited by count rather than fidelity. The matched-byte uniform baseline and the random-tier ablation directly measure this. If uniform INT8 with a larger $B$ wins, the paper's contribution becomes the measured count-versus-precision curve and the recommendation that budgeted kernel learners should simply store INT8 vectors. That is still a useful, previously unmeasured result.
Why not just use random Fourier features, which have fixed memory? Random features remove dictionary management but need a large $D$ to approximate the kernel. The byte cost of $D$ FP32 weights competes directly with the dictionary's bytes. Ahpatron's reported gains over NOGD on SUSY (23.66% versus 25.49%) suggest dictionaries win at moderate budgets in full precision. Whether that still holds once both sides are quantized, as QC-ODKLA shows random-feature weights can be at 3 bits, is open. Our matched-byte comparison answers it, and we will report the budgets where random features win.
Why not just run the whole learner in FP32 or FP16? Mixed-Precision KRLS found that uniform FP32 KRLS diverges to NaNs because of cancellation in error and novelty computations. We therefore never lower arithmetic precision in those paths, only storage precision. A uniform-FP16-arithmetic run is included as a negative control to confirm the same failure mode in Ahpatron's projection solve.
Why not just compress the stored data losslessly? On binary and categorical datasets this is the right answer and dominates everything. That is exactly why those datasets serve only as controls and the main claims rest on continuous-feature streams, where lossless compression of floats saves little.
Decisive Checks
For each continuous dataset we will plot mistake rate against bytes for every method, at four budgets spanning roughly one-eighth to twice the FP64 footprint of $B=400$. The headline check is whether the tiered dictionary's curve lies below both full-precision Ahpatron and uniform-quantized Ahpatron. A second check is whether the bound's precision term, evaluated on the live dictionary, predicts the bandwidth at which the best uniform bit-width shifts from low to high. A third is wall-clock time per round with fused dequantization against FP32 Ahpatron, which must stay within the ~9% overhead V-Quant reports for its own setting for the method to be practical. A clear negative on the first check, with uniform INT8 matching the tiered scheme everywhere, will be reported as the main finding.
References
- The Forgetron: A Kernel-Based Perceptron on a Fixed Budget
- Ahpatron: A New Budgeted Online Kernel Learning Machine with Tighter Mistake Bound
- ActNN: Reducing Training Memory Footprint via 2-Bit Activation Compressed Training
- Value-Aware Quantization for Training and Inference of Neural Networks
- Mixed-Precision Kernel Recursive Least Squares
- QC-ODKLA: Quantized and Communication- Censored Online Decentralized Kernel Learning via Linearized ADMM
- Tracking the best hyperplane with a simple budget Perceptron
- Online Passive-Aggressive Algorithms on a Budget
- Backprop with Approximate Activations for Memory-efficient Network Training
- Large Scale Online Kernel Classification
- Efficient KLMS and KRLS algorithms: A random fourier feature perspective