Variance Reduction via Orthogonal Random Features

122 concepts52 papers1 proposal

To scale kernel methods to massive datasets, researchers often rely on Random Fourier Features (RFF). The core idea is to approximate a complex kernel function by projecting data onto a set of random vectors. Traditionally, these vectors are sampled independently from a Gaussian distribution. However, independent sampling is surprisingly inefficient: random vectors tend to "clump" together, leaving large gaps in the feature space and resulting in high approximation variance.

A growing body of research suggests a simple but powerful fix: instead of sampling vectors independently, we should force them to be orthogonal. By ensuring that random features are mutually perpendicular, we can achieve significantly lower variance, better spectral approximation, and higher sample efficiency.

The Problem of Redundancy in Independent Sampling

When we sample projection vectors independently, we are essentially throwing darts at a high-dimensional hypersphere. Because the samples are independent, there is a non-trivial probability that several vectors will point in nearly the same direction. In the context of kernel approximation, this redundancy is wasted computation; these "clumped" features provide overlapping information about the data's geometry while leaving other directions entirely unobserved.

Yu et al. demonstrated that this independent sampling leads to high estimator variance, which degrades the stability of the approximation. To address this, the authors proposed Orthogonal Random Features (ORF). By replacing independent Gaussian projections with an orthogonal basis, they introduced negative correlations between the sampled features. This negative correlation is the "secret sauce" of variance reduction: when one feature overestimates the kernel value, another is likely to underestimate it, causing the errors to cancel out.

Why Orthogonality Works: Coverage and Correlation

The intuition behind ORF is geometric. Imagine trying to estimate the volume of a shape by taking random slices. If your slices are all parallel, you learn very little about the shape's depth. If you force the slices to be orthogonal, you are guaranteed to capture different dimensions of the object.

This geometric intuition is backed by rigorous theory. Choromanski et al. introduced a property called the "charm" of a kernel. They proved that for kernels derived from completely monotone functions—which include the widely used Gaussian and Matérn families—orthogonal sampling is mathematically guaranteed to outperform independent sampling. The authors showed that the "charm" links the analytical derivatives of the kernel directly to the variance reduction achieved through structured projections.

Furthermore, Choromanski et al. showed that orthogonal matrices provide a superior spectral approximation of the true kernel matrix. This ensures a more efficient coverage of the feature space, which in turn leads to tighter upper bounds on predictive error in tasks like Kernel Ridge Regression.

Structured Orthogonality for Speed

While Gram-Schmidt orthogonalization can be computationally expensive, researchers have developed "structured" versions that provide the benefits of orthogonality with much lower overhead.

  1. Hadamard Transforms: Dobriban and Liu analyzed the Subsampled Randomized Hadamard Transform (SRHT), showing that these structured orthogonal projections preserve data geometry more effectively than Gaussian matrices. In the large-data limit, non-orthogonal projections introduce a variance penalty that SRHT avoids.
  2. Circulant Matrices: Feng et al. utilized Signed Circulant Random Features (SCRF). By using cyclic shifts and random signs, they achieved loglinear computation time while matching the statistical stability of dense Gaussian projections.
  3. Super-Bit LSH: In the domain of similarity search, Li et al. showed that orthogonalizing random projection vectors in batches (Super-Bit LSH) significantly reduces the variance of angular similarity estimates compared to standard sign-random-projections.

Expanding the Reach of Orthogonal Features

The benefits of orthogonal features extend far beyond simple Gaussian kernels:

  • Optimal Transport: In Sliced Wasserstein distances, Sisouk et al. found that sampling entire orthonormal bases for projection directions ensures a more even distribution across the hypersphere, providing more accurate distance estimations than uniform sampling. Similarly, Kim applied orthogonal Monte Carlo sampling to visual tracking, reducing redundancy in 1D slices of high-dimensional distributions.
  • Linearized Transformers: To stabilize "linear" attention mechanisms (like the Performer), Likhosherstov et al. combined orthogonal projections with positive, bounded random features. This combination prevents the numerical instabilities and training explosions often seen in standard RFF-based attention.
  • Indefinite Kernels: Even for non-positive definite kernels, Fang et al. demonstrated that enforcing orthogonality across random vectors reduces approximation error by 10-20% compared to independent sampling.
  • Gradient Estimation: For backpropagation-free training, Wang and Markou showed that orthogonalizing the matrices used to guess gradient directions reduces both bias and noise, allowing these methods to scale to larger neural networks.

Conclusion

The transition from independent to orthogonal random features represents a shift from "blind" sampling to "structured" coverage. By enforcing geometric constraints on the projection space, researchers across various subfields have found a consistent way to reduce variance and improve sample efficiency. Whether through the Subsampled Randomized Hadamard Transform or the "charming" properties of radial basis functions, orthogonality ensures that every random feature contributes unique, non-redundant information to the model.

Key Foundational Work

Super-Bit Locality-Sensitive Hashing (2012) — contributed 2 concept elements to this direction.
Training Logistic Regression and SVM on 200GB Data Using b-Bit Minwise Hashing and Comparisons with Vowpal Wabbit (VW) (2011) — contributed 2 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 57 papers
  2. Version 1 · 2026-10-04 · 59 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_orthogonal_random_features_cd02c016,
  title = {orthogonal random features},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/orthogonal-random-features/rdr_cd02c016c547491d9c6eb235348c576e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 2, frozen text):

@misc{lacuna_orthogonal_random_features_cd02c016_v2,
  title = {orthogonal random features},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/orthogonal-random-features/rdr_cd02c016c547491d9c6eb235348c576e/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake