Random features approximate a kernel by mapping each document through many random cosine waves, written $\cos(\omega^\top x + b)$, and then fitting a linear model on top. A kernel here means a similarity function between inputs, and these maps make kernel methods cheap on large corpora. The usual recipe draws the wave directions $\omega$ from an isotropic Gaussian, which treats every direction in input space alike. Theory says this is costly in high dimensions. When the dimension grows with the sample size, any kernel that is symmetric under rotations behaves no better than a low-degree polynomial, and a perfect approximation of such a kernel only reproduces that weak estimator faithfully. Text classification with heavily skewed labels is the hardest version of this setting. The input is a bag of words with tens of thousands of dimensions, and the class that matters, such as condescending paragraphs or a rare news topic, may have a few dozen training examples. Directions estimated from the data are dominated by the majority class.
We propose to break this symmetry using the labels, and to do it in a way that resists imbalance. We draw the random wave directions from an anisotropic Gaussian whose covariance is the class-balanced average of the gradient outer products of a current predictor. Each class contributes equally to the covariance, whatever its size. This concentrates frequencies along the directions in which the predictor's output changes within each class, minority included, and spends little budget on the remaining noise directions. The approach is cheap and closed-form. Its key ingredient can be tested by a single switch: replacing the class-balanced average with the ordinary per-sample average.
Core Claim
How rotational invariance of common kernels prevents generalization in high dimensions proves that kernel ridge regression with any rotationally invariant kernel has bias at least as large as the error of the best low-degree polynomial fit when $d/n^\beta \to c$. That paper motivates our work. It identifies symmetry breaking as necessary, but it only points to architectural priors or manual feature selection. Optimal Rates for Random Fourier Features shows random features converge to the target kernel at rate $O(m^{-1/2})$, where $m$ is the number of features. Taken together, the two papers imply that the lever is which kernel is approximated, not how accurately.
Our claim is twofold. First, on high-dimensional imbalanced text, isotropic random-feature classifiers are close to linear in practice, so they add almost nothing over a linear model. Second, an anisotropic spectrum built from class-balanced gradient statistics recovers a real nonlinear component that helps minority-class F1. The same spectrum built from unbalanced statistics loses most of that gain. We state both halves as falsifiable predictions, not results.
Concretely, let $f$ be the current random-feature predictor and $g_i = \nabla_x f(x_i)$ its input gradient at training document $i$. Let $\mathcal{C}$ be the set of classes and $n_c$ the number of training documents in class $c$. The class-balanced gradient covariance is
$$M_{\text{bal}} = \frac{1}{|\mathcal{C}|}\sum_{c \in \mathcal{C}} \frac{1}{n_c}\sum_{i:\,y_i=c} g_i g_i^\top ,$$
and new frequencies are drawn as $\omega \sim \mathcal{N}(0, \sigma^{-2}(M_{\text{bal}}/\mathrm{tr}M_{\text{bal}} + \epsilon I))$. Here $\sigma$ is a bandwidth and $\epsilon$ keeps a small isotropic floor. The ablation replaces $M_{\text{bal}}$ with $M_{\text{unw}} = \frac{1}{n}\sum_i g_i g_i^\top$, which under 70:1 imbalance is essentially the majority class's gradient geometry.
Research Program
The algorithm alternates two steps, two or three times. In the first step it fits a class-weighted ridge or logistic model on the current $m$ random features. In the second it computes $M_{\text{bal}}$ and redraws all $m$ frequencies from the anisotropic Gaussian.
This is affordable for sparse inputs with $d > 10{,}000$. For a random-feature predictor, $g_i = -\sqrt{2/m}\sum_j a_j \sin(\omega_j^\top x_i + b_j)\,\omega_j$, where $a_j$ are the fitted output weights and $b_j$ the random phases. Every gradient therefore lies in the span of the current frequency matrix $\Omega \in \mathbb{R}^{m\times d}$. This gives $M_{\text{bal}} = \Omega^\top G\, \Omega$ with $G$ an $m \times m$ matrix. Sampling from $\mathcal{N}(0, M_{\text{bal}})$ only needs a factor of $G$ and one multiplication by $\Omega$. The cost is $O(nm^2 + m^2 d)$ per round, and no $d \times d$ matrix is ever formed. To keep the first round from being purely random, we seed it with an isotropic spectrum restricted to a vocabulary chosen by tf-IG. That vocabulary selection is described in A Novel Term Selection Approach in sLDA for Imbalanced Text Categorization, which uses information gain in place of inverse document frequency so that minority-specific words survive filtering. We use it as a supplied tool.
The two closest methods learn frequencies differently. Data Dependent Kernel Approximation using Pseudo Random Fourier Features learns frequencies by stochastic gradient descent to reconstruct an unsupervised isotropic kernel, so it inherits the symmetry we want to break and ignores labels. Not-So-Random Features is the nearest prior work. It is supervised: a min-max game in which support vector dual weights pick hard points and Langevin dynamics searches for frequencies, one feature at a time. It reports about 85% on CIFAR-10 auto-vs-truck with 100 features, against 70–73% for isotropic random features. It was tested only on balanced, low- to moderate-dimensional inputs. Its sample weighting comes from margins, not class membership, and it adds features greedily in a $d$-dimensional search. Our method differs in two ways. It reshapes the whole spectral distribution at once through a closed-form low-rank covariance, and it builds equal class mass directly into the statistic that defines the spectrum.
Alongside the method we build a diagnostic for whether a kernel classifier is doing anything nonlinear. For each trained model, we regress its test-set scores onto the best linear function and onto the best sparse quadratic function of the input. For quadratic terms we use the oblivious degree-2 tree sketch of Oblivious Sketching of High-Degree Polynomial Kernels, which embeds degree-$p$ polynomial kernels with target size polynomial rather than exponential in $p$. We report the fraction of variance left over, separately on minority and majority test documents. The polynomial-barrier theory predicts that the isotropic model's leftover is near zero. Our method should be worth pursuing only if its leftover is clearly positive on minority documents and that leftover carries predictive signal.
Baselines
The naive reference point is the do-nothing model: a class-weighted linear SVM on TF-IDF features. We also report the isotropic Gaussian random-feature model with class-weighted logistic regression at the same $m$, the same input features, and the same bandwidth search. This second model is the method the theory says should collapse to roughly linear behaviour. Matching or failing to exceed it would end the proposal.
The strongest cheap competitor is a linear SVM on tf-IG features, as in Liu et al.. On their 70:1 Reuters R8 subset (Earn / Trade / Grains), a tf-IG pipeline reaches macro-F1 of 92.75%, up from 84.45% with tf-idf. Their final classifier is a linear SVM on supervised topic features, not raw tf-IG vectors. We will rerun both their topic pipeline, where reproducible, and the simpler raw tf-IG linear SVM on the identical split. Beating it means higher macro-F1 and Grains F1 averaged over resampled training subsets. Because the Grains class has only 10 test documents, we report bootstrap intervals, and "beating" requires the interval of the difference to exclude zero.
The strongest kernel competitor is Not-So-Random Features. We run it both as published and with class-weighted SVM duals, at matched final feature counts and matched wall-clock budget. No result on text or under imbalance is reported on Lacuna for this method. PRFF is run at the same feature budgets; no reported downstream number for it was found on Lacuna. Another baseline is an axis-aligned variant that learns only a diagonal per-word scaling from the diagonal of $M_{\text{bal}}$. It tests whether rotations beyond word selection matter at all.
The strongest system overall is fine-tuned RoBERTa. Don't Patronize Me! reports binary F1 of 70.63% for RoBERTa on its own data split. SemEval-2022 Task 4 reports top systems in the mid-60s on the official test set. For crisis tweets, SRL4NLP reports macro-F1 of 54.19 (French, KOZLOWSKImerge) and 74.97 (English, HUMAIDmerge) using retrieval augmentation and focal loss. We do not expect a kernel on bag-of-words to beat these numbers. The fair comparison is our method applied to frozen, mean-pooled RoBERTa embeddings, set against a class-weighted linear probe of those same embeddings and against full fine-tuning with focal loss. We report F1 together with training compute.
The decisive ablation is the balanced versus unweighted gradient covariance, with everything else held fixed.
Why not just…?
Why not just fine-tune RoBERTa with focal or class-weighted loss? On accuracy this probably wins on DPM. The note says so plainly: the 70.63% and mid-60s figures above are targets we do not claim to reach from bag-of-words. The proposal's value lies elsewhere, in two places. One is the scientific question of whether symmetry breaking guided by labels revives nonlinear kernels under imbalance. The other is the frozen-embedding regime, where a balanced spectrum on top of a fixed encoder may close part of the gap between a linear probe and fine-tuning at a small fraction of the cost. Pérez-Almendros et al. also note that BERT-large overfit their small dataset and that SVMs matched transformers on some subcategories. So per-category results are where any advantage would show.
Why not just use tf-IG and a linear SVM? This is the most serious threat on Reuters-style topic tasks, where keywords decide the label. If our nonlinearity diagnostic shows near-zero leftover variance on R8 even for the balanced spectrum, we will report that the minority boundary there is effectively linear and that kernels are unnecessary. We expect any gain to appear on DPM, where condescension depends on combinations of words rather than single keywords. That is a prediction, not established evidence.
Why not just reweight the dual variables in Not-So-Random Features by class? That is the obvious combination of existing pieces, and we run it as a baseline. Our reason to expect a difference is mechanical. Its sequential Langevin search places one frequency at a time in a space with more than 10,000 dimensions, while our update reshapes all frequencies at once from a closed-form covariance. If the class-weighted version matches ours at equal wall-clock time, the contribution shrinks to the diagnostic, and we will say so.
Why not just select features and then use an isotropic kernel, which breaks symmetry by coordinate selection? Donhauser et al. themselves name feature selection as one escape from the barrier. The diagonal-scaling and tf-IG-seeded isotropic baselines test exactly this. If they match the full low-rank spectrum, the honest conclusion is that per-word relevance is enough for text. In that case the method simplifies to a balanced per-word relevance estimate.
Proposed Experiments
The experiments run on four benchmarks: the Reuters R8 three-class subset, DPM / SemEval-2022 Task 4 Subtask 1 (about 9.5% positive), HUMAIDmerge and KOZLOWSKImerge, and OffensEval 2020 Subtask A across five languages. On each we use TF-IDF inputs and frozen-embedding inputs. Feature budgets are $m \in \{100, 500, 2000, 10000\}$, with five seeds and a matched tuning budget for every method. Metrics are minority-class F1, macro-F1, and minority precision-recall area, plus the nonlinearity leftover for each model.
The first decisive check is whether isotropic random features fall within noise of the linear SVM and show near-zero leftover. That would confirm the barrier is operating on text. The second check is whether the balanced spectrum beats both the isotropic model and the tf-IG linear SVM on minority F1, with positive leftover concentrated on minority documents. The third check is whether the unweighted-covariance ablation loses most of that gain.
To control imbalance directly, we subsample the minority class of DPM to positive rates of 9.5%, 5%, 2% and 1%. If balancing is the active ingredient, the gap between the balanced and unweighted spectra should widen as the minority shrinks. If the gap stays flat or vanishes, the imbalance story is wrong and only the symmetry-breaking story survives.
References
- How rotational invariance of common kernels prevents generalization in high dimensions
- Optimal Rates for Random Fourier Features
- A Novel Term Selection Approach in sLDA for Imbalanced Text Categorization
- Data Dependent Kernel Approximation using Pseudo Random Fourier Features
- Not-So-Random Features
- Oblivious Sketching of High-Degree Polynomial Kernels
- Don't Patronize Me! An Annotated Dataset with Patronizing and Condescending Language towards Vulnerable Communities
- SemEval-2022 Task 4: Patronizing and Condescending Language Detection
- Image and Text: Fighting the same Battle? Super Resolution Learning for Imbalanced Text Classification