The Quadratic Bottleneck of High Dimensional Feature Scaling

119 concepts114 papers2 proposals

In machine learning, we often celebrate the "big data" era as a challenge of volume—processing millions of samples. However, a more insidious scaling problem exists not in the number of samples, but in the number of features. When a model attempts to account for the relationships between features, it often falls into a quadratic trap: the computational and memory requirements grow with the square of the feature dimension ($O(d^2)$).

The Interaction Explosion

The most common source of quadratic scaling is the desire to model how features interact. In a simple linear model, each feature is treated as an independent signal. But real-world data is rarely independent. In natural language, words depend on other words; in genomics, genes interact in complex networks.

To capture these dependencies, many models explicitly calculate pairwise relationships. David I. Inouye et al. demonstrate this in topic modeling, where modeling word dependencies results in a parameter space that grows quadratically with the vocabulary size (Admixture of Poisson MRFs: A Topic Model with Word Dependencies). Similarly, Jun Xiao et al. show that Factorization Machines, which are designed to learn feature interactions, face a performance bottleneck because they must process every possible pair of non-zero features (Attentional Factorization Machines: Learning the Weight of Feature Interactions via Attention Networks).

This "interaction explosion" means that doubling your feature count doesn't just double your work—it quadruples it.

The Memory Wall

Even if we have the processing power to handle $O(d^2)$ operations, we often run out of memory first. Many algorithms require storing a full matrix of these relationships, such as a correlation matrix or a similarity graph.

Mehrdad Rostami et al. highlight this in the context of feature selection for genomics, where constructing a complete correlation graph for tens of thousands of variables becomes physically impossible on standard hardware (A Novel Community Detection Based Genetic Algorithm for Feature Selection). The authors of Towards Utilitarian Online Learning - A Review of Online Algorithms in Open Feature Space note that this memory bottleneck is particularly severe in streaming data, where the feature space expands dynamically, making it prohibitively expensive to track every new feature-to-feature correlation.

Scaling Deep Representations

Modern deep learning is not immune to this bottleneck. While we often focus on the spatial complexity of Transformers (which is quadratic relative to sequence length), there is a parallel bottleneck in the feature dimension.

Xiang Zhang et al. observe that while linear complexity can be achieved for spatial windows, the computational overhead still scales quadratically with the number of feature channels, limiting how "wide" a model can become (HiT-SR: Hierarchical Transformer for Efficient Image Super-Resolution). In self-supervised learning, Yutaro Shigeto et al. point out that popular loss functions like Barlow Twins hit a "computational wall" because they rely on feature decorrelation, which requires computing a $d \times d$ covariance matrix (Learning Decorrelated Representations Efficiently Using Fast Fourier Transform).

Breaking the Bottleneck

To scale beyond a few thousand features, researchers must find ways to approximate these $O(d^2)$ interactions. Several strategies have emerged:

  1. Spectral Approximations: Yutaro Shigeto et al. use the Fast Fourier Transform (FFT) to reduce decorrelation complexity from $O(d^2)$ to $O(d \log d)$.
  2. Structural Assumptions: Akash Kumar argues that the quadratic barrier of feature recovery can be bypassed if the underlying features possess a low-rank structure (The Complexity of Learning Sparse Superposed Features with Feedback).
  3. Randomized Projections: Michael W. Mahoney et al. utilize sketching and random projections to approximate matrix coherence and leverage scores, avoiding the $O(nd^2)$ cost of computing an orthogonal basis (Fast approximation of matrix coherence and statistical leverage).
  4. Sparsity Constraints: Deguang Kong introduces the exclusive group LASSO to eliminate redundancy, effectively reducing the number of active features the model must consider (Uncorrelated Group LASSO).

By moving away from exhaustive pairwise modeling, these methods allow machine learning to step out of the quadratic shadow and into truly high-dimensional spaces.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_quadratic_feature_scaling_44c03d48,
  title = {quadratic feature scaling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/quadratic-feature-scaling/rdr_44c03d4820d940c78b65fe0417b1f3e4},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_quadratic_feature_scaling_44c03d48_v1,
  title = {quadratic feature scaling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/quadratic-feature-scaling/rdr_44c03d4820d940c78b65fe0417b1f3e4/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake