When dealing with high-dimensional data, our statistical intuition often betrays us. In the classical "large $d$, small $n$" paradigm—where the number of features ($d$) matches or exceeds the number of samples ($n$)—standard statistical estimators begin to break down. As noted by Bharath K. Sriperumbudur et al., the conventional empirical average exhibits severe limitations in these settings because the variance of the estimator scales with the dimensionality, quickly drowning out the true underlying signal.
To combat this, a powerful and recurring strategy across machine learning is subspace compression. Whether through random projections, low-rank approximations, or shrinkage techniques, reducing the effective dimensionality of a problem introduces a controlled amount of approximation bias but yields a massive reduction in estimation variance.
Understanding why this trade-off works requires looking at how compression acts as a regularizer across regression, representation learning, and kernel methods.
The Geometry of the Trade-off
Why does throwing away information by compressing a feature space actually improve performance? We can decompose the total expected error of an estimator into two competing components:
$$\text{Total Error} = \text{Approximation Bias}^2 + \text{Estimation Variance}$$
- Approximation Bias: By forcing our model to operate in a lower-dimensional subspace, we lose granular details. The compressed space can no longer perfectly represent the true target function or distribution.
- Estimation Variance: In a high-dimensional space, an estimator has too many degrees of freedom and overfits to the random noise inherent in a finite sample. Compressing the space restricts these degrees of freedom, stabilizing the estimator.
As Odalric Maillard et al. demonstrate in the context of Compressed Least-Squares Regression (CLSR), this trade-off is highly effective when the target function can be represented by a small norm in the original high-dimensional space. By controlling the size of the projected space, the total risk can be minimized.
Total Error
^
| \ / Full Dimension Error
| \ /
| \ Optimal /
| \ Dimension /
| \ | /
| \_____v_________/ <- U-Shaped Risk Curve
| \ /
| Bias^2 \ / Variance
| (Decreasing) \ / (Increasing)
+--------------------------------------------> Dimensionality
The challenge lies in finding the "sweet spot" where the reduction in variance outweighs the introduced bias. Mahdi Milani Fard et al. proved that the optimal projection dimension scales with the square root of the product of data sparsity and the number of training samples. Too much compression discards vital features (high bias), while too little compression leaves the model vulnerable to redundant or noisy dimensions (high variance).
Random Projections and Embeddings
One of the most computationally efficient ways to achieve this compression is through random projection. Instead of computing expensive data-dependent transformations like PCA, we can project high-dimensional features into a lower-dimensional subspace using a random matrix.
In reinforcement learning, this mechanism prevents overfitting in value function estimation. Mohammad Ghavamzadeh et al. introduced LSTD-RP, a variant of Least-Squares Temporal Difference learning that uses random projections. They showed that a slight increase in approximation error from the projection is heavily offset by the reduction in estimation variance when features exceed samples. Similarly, Mahdi Milani Fard et al. applied random projections to feature generation, demonstrating that error contraction can be achieved in a compressed space that scales only logarithmically with the original dimension.
This exact same U-shaped error curve governs representation learning:
- Word Embeddings: Zi Yin et al. used matrix perturbation theory to explain why choosing word embedding dimensionality is a bias-variance trade-off. Increasing dimensionality captures finer semantic signals (lowering bias) but incorporates more finite-sample noise into the representation (increasing variance).
- Off-Policy Evaluation: When evaluating AI policies over massive action spaces, Yuta Saito et al. showed that standard inverse propensity scoring collapses due to extreme variance. Their Marginalized Inverse Propensity Scoring (MIPS) estimator uses low-dimensional action embeddings to aggregate data across similar actions, trading granular action details for stable evaluation.
- Bilinear Pooling: In fine-grained visual recognition, second-order features suffer from high estimation variance. Tan Yu et al. note that while reducing memory via smaller projections typically degrades feature accuracy, structured random projections can optimize this trade-off.
Kernel Mean Shrinkage and Stein's Phenomenon
The compression-induced trade-off is not limited to explicit dimensionality reduction; it also manifests as shrinkage toward a subspace or reference point. This is beautifully illustrated in kernel methods, where data is mapped into an infinite-dimensional Reproducing Kernel Hilbert Space (RKHS).
To represent a probability distribution in an RKHS, we typically compute the empirical kernel mean—the simple average of the kernel evaluations over our samples. However, Krikamol Muandet et al. demonstrated that the standard empirical average is actually inadmissible in high-dimensional feature spaces.
This sub-optimality stems from Stein's Phenomenon: in higher dimensions, the variance of the empirical mean dominates the total estimation error. By applying a shrinkage factor that pulls the empirical estimate toward a fixed reference point (such as the origin), we introduce a small, controlled amount of bias but achieve a massive reduction in variance.
Unstable Empirical Mean (High Variance)
o .
*
\ | /
Fixed Reference Point -------->X<-------- True Kernel Mean
/ | \
* . o
Shrunk Estimator (Low Variance, Small Bias)
Krikamol Muandet et al. extended this concept to spectral filtering, proving that the performance advantages of shrinkage-based estimators become increasingly pronounced as the dimensionality of the dataset grows.
When infinite-dimensional feature spaces must be approximated by finite proxies—such as in online learning with kernel losses—Niladri S. Chatterji et al. showed that the proxy dimension acts as the primary dial for this trade-off. A lower-dimensional proxy reduces the variance of loss estimates during bandit feedback but increases the error in representing the true loss function.
Alternative Paradigms of Subspace Selection
Depending on the structure of the problem, the compression mechanism can take several other forms:
- Feature Aggregation: Instead of random projection, we can merge highly correlated features by averaging them. Alberto Maria Metelli et al. derived a mathematical threshold for feature aggregation, proving that when sample sizes are limited, the variance reduction from averaging correlated features consistently outweighs the bias introduced by blending them.
- Covariate Shift Correction: In high-dimensional density ratio estimation, importance weights become highly unstable. Mingming Gong et al. showed that finding a low-dimensional projection that preserves only target-relevant information yields far more stable and accurate importance weights than estimating ratios in the original space.
- Likelihood-Informed Subspaces: For non-linear inverse problems, Tiangang Cui et al. speed up MCMC sampling by identifying a low-dimensional subspace constrained by the data, treating the remaining unconstrained directions analytically to reduce sampling variance.
- Low-Rank Hashing: For large-scale image retrieval, Ke Jiang et al. showed that reducing the projection rank below the full sample size filters out estimation noise in the principal components, maximizing retrieval accuracy.
- Spectral Q-Learning: In mobile health applications with small patient cohorts, Yuhe Gao et al. integrated PCA with deep Q-learning, demonstrating that aggressive dimensionality reduction prevents the model from overfitting to high-frequency sensor noise.
Conclusion
Subspace compression works because high-dimensional noise is isotropic, while meaningful signals are typically concentrated in low-dimensional manifolds or possess small norms. By compressing the space, we block out the multi-directional noise that plagues high-dimensional estimators. The fundamental lesson across these diverse fields is identical: accepting a bounded amount of structural bias is often the only way to escape catastrophic variance.
Key Foundational Work
Compressed Least-Squares Regression (2009) — contributed 3 concept elements to this direction.
LSTD with Random Projections (2010) — contributed 2 concept elements to this direction.