High-Dimensional Learning in Finance††thanks: Replication code is available from the author.
Link to Most Recent Version)
Abstract
Recent advances in machine learning have shown promising results for financial prediction using large, over-parameterized models. This paper provides theoretical foundations and empirical validation for understanding when and how these methods achieve predictive success. I examine three key aspects of high-dimensional learning in finance. First, I prove that within-sample standardization in Random Fourier Features implementations fundamentally alters the underlying Gaussian kernel approximation, replacing shift-invariant kernels with training-set dependent alternatives. Second, I derive sample complexity bounds showing when reliable learning becomes information-theoretically impossible under weak signal-to-noise ratios typical in finance. Third, VC-dimension analysis reveals that ridgeless regression’s effective complexity is bounded by sample size rather than nominal feature dimension. Comprehensive numerical validation confirms these theoretical predictions, revealing systematic breakdown of claimed theoretical properties across realistic parameter ranges. These results show that when sample size is small and features are high-dimensional, observed predictive success is necessarily driven by low-complexity artifacts, not genuine high-dimensional learning.
Key words: Portfolio choice, machine learning, random matrix theory, PAC-learning
JEL classification: C3, C58, C61, G11, G12, G14
1 Introduction
The integration of machine learning methods into financial prediction has emerged as one of the most active areas of research in empirical asset pricing (Kelly et al. 2024, Gu et al. 2020, Bianchi et al. 2021, Chen et al. 2024, Feng et al. 2020). The appeal is clear: while financial markets generate increasingly high-dimensional data, traditional econometric methods remain constrained by limited sample sizes and the curse of dimensionality. Machine learning promises to uncover predictive relationships that elude traditional linear models by leveraging nonlinear approximations and high-dimensional overparameterized representations, thereby expanding the frontier of return predictability and portfolio construction.
Yet despite rapid adoption and impressive empirical successes, our theoretical understanding of when and why machine learning methods succeed in financial applications remains incomplete. This gap is particularly pronounced for high-dimensional methods applied to the notoriously challenging problem of return prediction, where signals are weak, data are limited, and spurious relationships abound. A fundamental question emerges: under what conditions can sophisticated machine learning methods genuinely extract predictive information from financial data, and when might apparent success arise from simpler mechanisms?
The pioneering work of Kelly et al. (2024) has significantly advanced our theoretical understanding by establishing rigorous conditions under which complex machine learning models can outperform traditional approaches in financial prediction. Their theoretical framework, grounded in random matrix theory, demonstrates that the conventional wisdom about overfitting may not apply in high-dimensional settings, revealing a genuine ’virtue of complexity’ under appropriate conditions. This breakthrough provides crucial theoretical foundations for understanding when and why sophisticated methods succeed in finance.
Building on these theoretical advances, this paper examines how practical implementation details interact with established mechanisms. This becomes important as recent empirical analysis Nagel (2025) suggests that high-dimensional methods may achieve success through multiple pathways that differ from theoretical predictions. Several questions emerge: What are the information-theoretic requirements for learning with weak signals? How do implementation choices affect underlying mathematical properties? When do complexity benefits reflect different learning mechanisms? Understanding these interactions helps characterize the complete landscape of learning pathways in high-dimensional finance applications.
This paper provides theoretical foundations for answering these questions through three main contributions that help characterize the different mechanisms through which high-dimensional methods achieve predictive success in financial prediction.
First, I extend the theoretical analysis to practical implementations, showing how the standardization procedures commonly used for numerical stability modify the kernel approximation properties that underlie existing theory. While Random Fourier Features (RFF) theory rigorously proves convergence to shift-invariant Gaussian kernels under idealized conditions (Rahimi & Recht 2007, Sutherland & Schneider 2015), I prove that the within-sample standardization employed in every practical implementation modifies these theoretical properties. The standardized features converge instead to training-set dependent kernels that violate the mathematical foundations required for kernel methods. This breakdown explains why methods cannot achieve the kernel learning properties established by existing theory and must rely on fundamentally different mechanisms.
Rahimi & Recht (2007) prove that for features with and , the empirical kernel converges in probability to the Gaussian kernel as . This convergence requires that features maintain their original distributional properties and scaling. However, I prove that the within-sample standardization employed in every practical implementation—where —fundamentally alters the convergence properties. The standardized features converge instead to training-set dependent kernels that violate the shift-invariance and stationarity properties required for kernel methods. A detailed analysis of how standardization breaks the specific theoretical conditions appears in Section 3, following the formal proof of this breakdown.
Second, I derive sharp sample complexity bounds that characterize the information-theoretic limits of high-dimensional learning in financial settings. Using PAC-learning theory,111In PAC-learning (Valiant 1984), a predictor is “probably approximately correct” if, with samples, its risk is within of optimal with probability ; I apply these bounds (see Kearns & Vazirani 1994) to gauge when weak return signals are learnable. I establish both exponential and polynomial lower bounds showing when reliable extraction of weak predictive signals becomes impossible regardless of the sophistication of the employed method. These bounds reveal that learning over function spaces with thousands of parameters suggests that reliable learning may require stronger conditions than typically available in typical financial applications. For example, methods claiming to harness 12,000 parameters with 12 monthly observations require signal-to-noise ratios exceeding realistic bounds by orders of magnitude, suggesting that predictive success may arise through mechanisms that differ from the theoretical framework.
Third, I characterize the effective complexity of high-dimensional methods through VC dimension analysis and sharp learning thresholds.222Effective complexity—often called the effective degrees of freedom—is the trace of the “hat” matrix, where . For minimum-norm (ridgeless) regression is an idempotent projector of rank , so irrespective of the nominal dimension ; see Hastie et al. (2009, Chapter 7), Bartlett et al. (2020), and Hastie et al. (2022). I prove that ridgeless regression operates over function spaces with complexity bounded by sample size rather than parameter count, regardless of nominal dimensionality. Combined with precise learning thresholds that depend on signal strength, feature dimension, and sample size, these results provide practitioners with concrete tools for evaluating when available data suffices for reliable prediction versus when apparent performance must arise through alternative mechanisms.
While these theoretical results provide clear mathematical boundaries on learning feasibility, their practical relevance depends on how they manifest across the parameter ranges typically employed in financial applications. The gap between asymptotic theory and finite-sample reality can be substantial, particularly when dealing with the moderate dimensions and sample sizes common in empirical asset pricing. Moreover, the breakdown of kernel approximation under standardization represents a fundamental departure from assumed theoretical properties that requires empirical quantification to assess its practical severity.
To bridge this theory-practice gap, I conduct comprehensive numerical validation of the kernel approximation breakdown across realistic parameter spaces that span the configurations used in recent high-dimensional financial prediction studies (Kelly et al. 2024, Nagel 2025). The numerical analysis examines how within-sample standardization destroys the theoretical Gaussian kernel convergence that underlies existing RFF frameworks, quantifying the magnitude of approximation errors under practical implementation choices. These experiments reveal that standardization-induced kernel deviations reach mean absolute errors exceeding 40% relative to the theoretical Gaussian kernel in typical configurations (, ), with maximum deviations approaching 80% in high-volatility training windows. The kernel approximation failure manifests consistently across different feature dimensions and sample sizes, with relative errors scaling approximately as in line with theoretical predictions. The numerical validation thus provides concrete evidence that practical implementation details create substantial violations of the theoretical assumptions underlying high-dimensional RFF approaches, with error magnitudes sufficient to fundamentally alter method behavior.
Together, these results explain why methods may achieve predictive success through multiple pathways, including both sophisticated learning and simpler pattern-matching mechanisms. These findings provide practitioners with frameworks for understanding and evaluating different sources of predictive performance in high-dimensional models. for understanding when such methods can genuinely contribute to predictive performance versus when they exploit statistical artifacts.
1.1 Literature Review
This paper builds on three distinct but interconnected theoretical traditions to provide foundations for understanding high-dimensional learning in financial prediction.
The Probably Approximately Correct (PAC) framework (Valiant 1984, Kearns & Vazirani 1994) provides fundamental tools for characterizing when reliable learning is information-theoretically feasible. Classical results establish that achieving generalization error with confidence requires sample sizes scaling with the complexity of the function class, typically (Shalev-Shwartz & Ben-David 2014). Recent advances in high-dimensional learning theory (Belkin et al. 2019, Bartlett et al. 2020, Hastie et al. 2022) have refined these bounds for overparameterized models, showing that the effective rather than nominal complexity determines learning difficulty. However, these results have not been systematically applied to the specific challenges of financial prediction, where weak signals and limited sample sizes create particularly demanding learning environments.
The RFF methodology (Rahimi & Recht 2007) provides computationally efficient approximation of kernel methods through random trigonometric features, with theoretical guarantees assuming convergence to shift-invariant kernels under appropriate conditions (Rudi & Rosasco 2017). Subsequent work has characterized the approximation quality and convergence rates for various kernel classes (Mei & Montanari 2022), establishing RFF as a foundation for scalable kernel learning. However, existing theory assumes idealized implementations that may not reflect practical usage. In particular, no prior work has analyzed how the standardization procedures commonly employed to improve numerical stability affect the fundamental convergence properties that justify the theoretical framework.
The phenomenon of ”benign overfitting” in overparameterized models has generated substantial theoretical interest (Belkin et al. 2019, Bartlett et al. 2020), with particular focus on understanding when adding parameters can improve rather than harm generalization performance. The VC dimension provides a classical measure of model complexity that connects directly to generalization bounds (Vapnik 1998), while recent work on effective degrees of freedom (Hastie et al. 2022) shows how structural constraints can limit the true complexity of nominally high-dimensional methods. These insights have been applied to understanding ridge regression in high-dimensional settings, but the connections to kernel methods and the specific constraints imposed by ridgeless regression in financial applications remain underexplored.
The application of machine learning to financial prediction has generated extensive empirical literature (Gu et al. 2020, Kelly et al. 2024, Chen et al. 2024), with particular attention to high-dimensional methods that can potentially harness large numbers of predictors (Feng et al. 2020, Bianchi et al. 2021). The theoretical framework of Kelly et al. (2024) provides crucial insights into when high-dimensional methods can succeed, particularly their demonstration that ridgeless regression can achieve positive performance despite seemingly problematic complexity ratios. This paper extends their analysis by examining how practical implementation considerations interact with these theoretical mechanisms.
This paper contributes to each of these literatures by providing the first unified theoretical analysis that connects sample complexity limitations, kernel approximation breakdown, and effective complexity bounds to explain the behavior of high-dimensional methods in financial prediction.
The remainder of the paper proceeds as follows. Section 2 establishes the theoretical framework and formalizes the theory-practice disconnect in RFF implementations. Section 3 proves that within-sample standardization fundamentally breaks kernel approximation, explaining why claimed theoretical properties cannot hold in practice. Section 4 establishes information-theoretic barriers to high-dimensional learning, showing that genuine complexity benefits are impossible under realistic financial conditions. Section 6 concludes. All technical details are relegated to a supplementary document containing Appendices A and B, which are available upon request from the author.
2 Background and Framework
This section establishes the theoretical framework for analyzing high-dimensional prediction methods in finance. I first formalize the return prediction problem, then examine the critical disconnect between RFF theory and practical implementation that underlies my main results.
2.1 The Financial Prediction Problem
Consider the fundamental challenge of predicting asset returns using high-dimensional predictor information. I observe predictor vectors and subsequent returns for , with the goal of learning a predictor that minimizes expected squared loss .
The challenge lies in the fundamental characteristics of financial prediction: signals are weak relative to noise, predictors exhibit complex persistence patterns, and available sample sizes are limited by the nonstationarity of financial markets. These features create a particularly demanding environment for high-dimensional learning methods.
I formalize this environment through three core assumptions that capture the essential features while maintaining sufficient generality for my theoretical analysis.
Assumption 1 (Financial Prediction Environment).
The return generating process is where:
-
(a)
is the true regression function with
-
(b)
is noise with and
-
(c)
The signal-to-noise ratio for some
-
(d)
Predictors follow with and eigenvalues of in
This assumption captures the essential features of financial prediction that distinguish it from typical machine learning applications. The bounded signal condition and weak SNR scaling reflect the empirical reality that financial predictors typically explain only 1-5% of return variation (Welch & Goyal 2008). The persistence in predictors (eigenvalues of in ) captures the well-documented dynamics of financial variables like dividend yields and interest rate spreads, which proves crucial for understanding why short training windows lead to mechanical pattern matching rather than genuine learning.
Assumption 2 (Random Fourier Features Construction).
High-dimensional predictive features are constructed as where and for . In practical implementations, these features are standardized within each training sample: where .
This assumption formalizes the RFF methodology as actually implemented in practice, including the crucial standardization step that has not been analyzed in existing theoretical frameworks. The standardization appears in every practical implementation to improve numerical stability, yet as I prove, it fundamentally alters the mathematical properties of the method.
Assumption 3 (Regularity Conditions).
The input distribution has bounded support and finite moments, ensuring well-defined feature covariance satisfying for constants . Training samples satisfy standard non-degeneracy conditions.333Specifically, the matrix has full column rank , ensuring the geometric properties needed for my convergence analysis. See Appendix B for technical details.
These technical conditions ensure that concentration inequalities apply and that my convergence results hold with high probability. The conditions are mild and satisfied in typical financial applications.444For example, for the KMZ setup with predictors and training windows, these conditions hold almost surely since continuous economic variables generically satisfy the required independence properties.
Assumption 4 (Affine Independence of the Sample).
Let with . The matrix has full column rank (equivalently, the augmented vectors are affinely independent).
This assumption enters my analysis through the small-ball probability estimates needed to establish convergence of standardized kernels. The full-rank requirement ensures that the linear change of variables is bi-Lipschitz on bounded sets, enabling geometric control that yields exponential small-ball bounds and finiteness of key expectations. In Kelly et al.’s empirical design with predictors and months, the matrix is , and since elements are continuous macroeconomic variables, affine dependence has Lebesgue measure zero, making this assumption mild.
Assumption 5 (Sub-Gaussian RFFs).
For every unit vector , the scalar is -sub-Gaussian under : for all .
Assumption 5 requires that linear combinations of the random Fourier features are sub-Gaussian with parameter , ensuring for all unit vectors and scalars . This concentration condition is essential for applying uniform convergence results and obtaining non-asymptotic bounds on the empirical feature covariance matrix that appear in our sample complexity analysis. The assumption is standard in high-dimensional learning theory and is automatically satisfied for RFF with bounded support: since , each feature is bounded, and linear combinations of bounded random variables are sub-Gaussian with parameter . This ensures that concentration inequalities apply to the feature covariance estimation, enabling our PAC-learning bounds while remaining satisfied in all practical RFF implementations.
2.2 The Theory-Practice Disconnect in Random Fourier Features
The foundation of high-dimensional prediction methods in finance rests on RFF theory, yet a fundamental disconnect exists between theoretical guarantees and practical implementation. Understanding this disconnect is crucial for interpreting what these methods actually accomplish.
2.2.1 Theoretical Guarantees Under Idealized Conditions
The RFF methodology (Rahimi & Recht 2007) provides rigorous theoretical foundations for kernel approximation. For target shift-invariant kernels , the theory establishes that:
(2.1) |
in probability, under the condition that features maintain their original distributional properties. This convergence enables kernel methods to be approximated through linear regression in the RFF space, with all the theoretical guarantees that kernel learning provides.
2.2.2 What Actually Happens in Practice
Every practical RFF implementation deviates from the theoretical setup in a seemingly minor but mathematically crucial way. To improve numerical stability and ensure comparable scales across features, practitioners standardize features using training sample statistics:
(2.2) |
This standardization fundamentally alters the mathematical properties of the method. The standardized empirical kernel becomes:
(2.3) |
This standardized kernel no longer converges to the Gaussian kernel. Instead, as I prove in Theorem 1, it converges to a training-set dependent limit that violates the shift-invariance and stationarity properties required for kernel methods.
3 How Standardization Modifies Kernel Approximation
Having established the theory-practice disconnect in Section 2, I now prove rigorously that standardization fundamentally alters the kernel approximation properties that justify RFF methods. This breakdown explains why high-dimensional methods cannot achieve their claimed theoretical properties and must rely on simpler mechanisms.
3.1 Main Result
Theorem 1 (Modified Convergence of Gaussian-RFF Approximation under Standardization).
Then:
-
(a)
For every fixed , the standardized kernel estimator converges almost surely:
-
(b)
The limit kernel depends on the particular training set , whereas the Gaussian kernel is training-set independent. Consequently, in general.
The proof proceeds in two steps. First, I establish that the standardized kernel function has finite expectation despite the random denominator, enabling application of the strong law of large numbers for part (a). This requires controlling the probability that the empirical variance becomes arbitrarily small, which I achieve through geometric analysis exploiting the full-rank condition. Second, I prove training-set dependence by explicit construction: scaling any training point with yields different limiting kernels, establishing that . The complete technical proof appears in Appendix A.
3.2 Analysis of the Breakdown
To understand the implications of Theorem 1, I examine precisely how standardization violates the conditions under which RFF theory operates. Rahimi & Recht (2007) prove convergence to the Gaussian kernel under two essential conditions: distributional alignment of frequencies and phases with the target kernel’s Fourier transform, and preservation of the prescribed scaling .
Standardization systematically violates both conditions. The original features have theoretical properties derived from specified distributions of and , but the standardization factor varies with the training set, altering the effective distribution in a data-dependent manner. The expectation now depends on , disrupting the direct mapping to . Additionally, the fixed scaling that ensures correct kernel approximation is replaced by a random, sample-dependent factor, breaking the fundamental relationship between feature products and kernel values.
These modifications have important mathematical implications. The standardized features yield an empirical kernel that converges to , which is training-set dependent rather than depending only on like the Gaussian kernel. The resulting kernel is not shift-invariant since reflects absolute positions of training points, and shifting the data changes . This creates temporal non-stationarity as kernel properties change when training windows roll forward.
3.3 Implications for Financial Applications
Theorem 1 resolves the fundamental puzzles in high-dimensional financial prediction by revealing that claimed theoretical properties simply do not hold in practice. KMZ develop their theoretical analysis assuming RFF converge to Gaussian kernels. Their random matrix theory characterization, effective complexity bounds, and optimal shrinkage formula all depend critically on this convergence. However, their empirical implementation employs standardization, which fundamentally alters the convergence properties, creating a notable difference between theory and practice.
With modified kernel structure, methods may perform learning that differs from the theoretical framework, potentially involving pattern-matching mechanisms based on training-sample dependent similarity measures. The standardized kernel creates similarity measures based on training-sample dependent weights rather than genuine predictor relationships. This explains Nagel (2025) empirical finding that high-complexity methods produce volatility-timed momentum strategies regardless of underlying data properties. The broken kernel structure makes the theoretically predicted learning more challenging, leading methods to weight returns based on alternative similarity measures within the training window.
The apparent virtue of complexity may arise through different mechanisms than originally theorized. Their method cannot achieve its theoretical properties due to standardization, so any success must arise through alternative mechanisms. This resolves the central puzzle of how methods claiming to harness thousands of parameters succeed with tiny training samples: they may operate through mechanisms that differ from the high-dimensional framework, potentially involving simpler pattern-matching approaches that happen to work in specific market conditions.
4 Fundamental Barriers to High-Dimensional Learning
The kernel approximation breakdown in Section 3 reveals that methods cannot achieve their claimed theoretical properties. This section establishes that even if this breakdown were corrected, fundamental information-theoretic barriers would still prevent genuine high-dimensional learning in financial applications. These results explain why methods must rely on the mechanical pattern matching that emerges from broken kernel structures.
4.1 Sample Complexity Lower Bounds
I establish fundamental limits on learning over the high-dimensional function spaces that methods claim to harness, requiring an additional regularity condition for my convergence analysis.
Theorem 2 (Exponential lower bound, random design).
Assume the data–generation scheme of Assumptions 1, 2, and 3, and suppose additionally that the RFF are -sub-Gaussian: for every unit , (Assumption 5).
Let and denote by the noise variance. Then, for every ,
(4.1) |
for a universal constant .
Moreover, there is a constant such that whenever ,
(4.2) |
with .
The proof uses a minimax argument with Fano’s inequality. I construct a -packing with well-separated parameters. The Kullback-Leibler (KL) divergence between corresponding data distributions satisfies . Fano’s inequality then implies any decoder has error probability . Since low estimation risk would enable perfect identification (contradicting Fano), I obtain . Optimizing yields the exponential bound. The high-probability version conditions on well-conditioned designs using matrix concentration.
Theorems 2 applies directly to machine learning methods employing RFF as actually implemented in practice. The theoretical framework covers the complete practical pipeline where random feature weights are drawn from specified distributions, standardization procedures are applied for numerical stability, and learning proceeds over the resulting linear-in-features function class using any estimation method including OLS, ridge regression, LASSO, or ridgeless regression.
The bounds establish information-theoretic impossibility in two complementary forms: the expectation bound averaged over all possible feature realizations, and the high-probability bound showing that the same limitations hold for most individual feature draws. KMZ follows precisely this framework with features and training observations, making both versions directly applicable to their empirical analysis. The universal constant depends on the feature covariance bounds from the regularity conditions and the sub-Gaussian parameter controlling concentration properties, but remains bounded away from zero under standard assumptions for financial applications.
Theorem 3 (Polynomial minimax lower bound – high probability).
-
(a)
In-expectation bound. For every
-
(b)
High-probability bound. There exists a constant such that whenever ,
(4.3)
Thus the same lower bound holds for each realised design matrix with probability at least .
The proof uses a standard basis packing with refined concentration analysis. I construct functions using the canonical basis: and for , where . The population covariance ensures separation . For the KL bound, , enabling Fano’s inequality with error probability . The risk-identification argument yields , giving the polynomial bound. For part (b), I condition on the ”good design” event with probability when , then apply the same argument with adjusted constants.
The universal constants in my polynomial lower bounds have transparent structure that illuminates the fundamental barriers to high-dimensional learning in finance. The expectation bound employs , which depends on the feature covariance bounds and measures the quality of the feature construction. For RFF with the standard construction where , the theoretical expectation suggests under ideal conditions, yielding in the best case. Even when the conditioning number increases to moderate values around 10, I obtain , representing manageable degradation in the constant.
The high-probability bound introduces additional dependence on the sub-Gaussian parameter through both the concentration quality and the threshold requirement for the probabilistic guarantee to hold. Throughout my analysis, I employ the conservative choice , deliberately favoring the possibility of learning by using constants that are optimistic relative to typical financial applications. This conservative approach strengthens my impossibility conclusions: even when I bias the analysis toward finding that learning should be possible, the fundamental barriers persist. The comparable magnitude of constants between fixed and random feature settings confirms that these information-theoretic limitations are robust to implementation details and reflect inherent properties of high-dimensional learning with limited financial data.
4.2 Effective Complexity: The VC Dimension Reality
The Vapnik-Chervonenkis (VC) dimension provides a fundamental measure of model complexity that directly connects to generalization performance and sample complexity requirements (Vapnik & Chervonenkis 1971, Vapnik 1998). For a hypothesis class , the VC dimension is the largest number of points that can be shattered (i.e., correctly classified under all possible binary labelings) by functions in . This combinatorial measure captures the essential complexity of a learning problem: classes with higher VC dimension require more samples to achieve reliable generalization.
The connection between VC dimension and sample complexity is formalized through uniform convergence bounds. Classical results show that for a hypothesis class with VC dimension , achieving generalization error with confidence requires sample size (Blumer et al. 1989, Shalev-Shwartz & Ben-David 2014). This relationship reveals why effective model complexity, rather than nominal parameter count, determines learning difficulty.
In the context of high-dimensional financial prediction, VC dimension analysis becomes crucial for understanding what machine learning methods actually accomplish. While methods may claim to leverage thousands of parameters, their effective complexity—as measured by VC dimension—may be much lower due to structural constraints imposed by the optimization procedure. Ridgeless regression in the overparameterized regime () provides a particularly important case study, as the interpolation constraint fundamentally limits the achievable function class regardless of the ambient parameter dimension.
Theorem 4 (Effective VC Dimension of Ridgeless RFF Regression).
Let be a fixed feature map (e.g. standardized RFF) and define the linear function class
Fix a training sample with and denote . Write and . The corresponding ridgeless (minimum-norm) regression functions are
Let . Then
-
(a)
.
-
(b)
. In particular, if is invertible (full row rank), the VC dimension equals .
KMZ correctly note that, after minimum–norm fitting, the effective degrees of freedom of their RFF model equal the sample size (), not the nominal dimension (): “the effective number of parameters in the construction of the predicted return is only …”. Theorem 4 rigorously justifies this statement by showing that the VC dimension of ridgeless RFF regression is bounded above by .
This observation, however, leaves open the central question that KMZ label the “virtue of complexity”: does the enormous RFF dictionary contribute predictive information beyond what a -dimensional linear model could extract? In kernel learning the tension is familiar: one combines an extremely rich representation (in principle, infinite–dimensional) with an estimator whose statistical capacity is implicitly capped at . Overfitting risk is therefore limited, but any real performance gain must come from the non-linear basis supplied by the features rather than from high effective complexity per se.
4.3 Sharp Learning Thresholds
The previous bounds establish that learning is difficult, but do not precisely characterize the boundary between feasible and infeasible regimes. I derive sharp thresholds that separate learnable from unlearnable scenarios.
Understanding such thresholds is crucial for financial applications where practitioners must decide whether available data is sufficient for reliable prediction. While my previous bounds show that learning is difficult, they do not precisely characterize the boundary between feasible and infeasible learning regimes. The following analysis addresses this gap by establishing sharp learning thresholds that depend on the signal-to-noise ratio, feature dimension, and sample size.
Definition 1 (Learning Threshold).
For target prediction error , define the learning threshold as:
where is the signal-to-noise ratio and is the universal constant from Theorem 3.
The polynomial learning threshold reveals why my characterization provides actionable guidance where cruder exponential bounds would not. Unlike exponential characterizations that scale catastrophically with feature dimension , my threshold scales as —a fundamental difference that enables meaningful evaluation with realistic parameters.
This distinction proves crucial for understanding high-dimensional financial prediction. The threshold exhibits intuitive monotonicity properties: easier targets (larger ) require weaker signals, while higher complexity relative to sample size (larger ) demands stronger signals. More importantly, the explicit dependence on sample size shows precisely how additional observations reduce required signal strength, revealing that sample complexity alone does not determine learning difficulty.
The practical significance becomes clear when evaluating typical financial applications. For the parameters employed by KMZ— features, observations, targeting accuracy—my threshold requires signal-to-noise ratios exceeding , compared to observed financial signal strengths of –. This gap of nearly two orders of magnitude places such applications decisively outside the learnable regime, providing theoretical validation that apparent success must arise through mechanisms other than genuine high-dimensional learning.
The sharp nature of this transition explains why high-dimensional methods may appear to succeed or fail unpredictably: small changes in problem parameters can move applications across the fundamental boundary between learnable and unlearnable regimes.
Theorem 5 (Sharp Learning Threshold for RFF-based Predictors).
Consider the RFF prediction problem under Assumptions 1–3, with target prediction error and universal constant from Theorem 3. Then there exists a sharp phase transition characterized by the complexity-to-sample ratio :
-
(a)
Phase I (Impossible Learning): If
then learning with error is impossible.
-
(b)
Phase II (Possible Learning): If
then learning with error becomes information-theoretically feasible with sufficiently sophisticated estimators.
-
(c)
Trivial Regime: If , then the function class is too simple relative to the target accuracy, and standard parametric rates apply.
Corollary 1 (Weak Signal Learning Impossibility).
Under the weak signal assumption with , there exists a critical sample size threshold such that learning is impossible when .
Applying these thresholds to Kelly et al.’s reported performance reveals the impossibility of their claimed mechanism. Their high-complexity model achieves (corresponding to ) with parameters , .
The complexity-to-sample ratio appears manageable, but the signal strength requirement demands that predictive signals explain at least 9,940
This analysis confirms that their empirical success cannot arise from genuine learning over the claimed high-dimensional function space, providing theoretical validation for the mechanical pattern matching explanation.
These results resolve the central puzzle by showing that apparent ’virtue of complexity’ may reflect mechanisms that differ from both the predicted high-dimensional learning (information-theoretically impossible) and the theoretical properties (which are modified by standardization). Instead, methods achieve success through mechanical pattern matching that emerges when kernel approximation fails.
The standardization procedure ensures methods accidentally implement volatility-timed momentum strategies operating in low-dimensional spaces bounded by sample size. This transforms evaluation from ”how can complex methods work with limited data?” to ”how can we distinguish mechanical artifacts from genuine learning?”
The following section provides empirical validation of these theoretical predictions, demonstrating the kernel breakdown and learning impossibility in practice.
5 Empirical Validation of Kernel Approximation Breakdown
This section provides comprehensive empirical validation of Theorem 1 through systematic parameter exploration across the entire space of practical RFF implementations. My experimental design spans realistic financial prediction scenarios, testing whether standardization preserves the Gaussian kernel approximation properties that underlie existing theoretical frameworks. The results provide definitive evidence that standardization fundamentally breaks RFF convergence properties, confirming that methods cannot achieve their claimed theoretical guarantees in practice.
5.1 Data Generation and Model Parameters
I generate realistic financial predictor data following the autoregressive structure typical of macroeconomic variables used in return prediction. For each parameter combination , I construct predictor matrices where:
(5.1) |
The persistence parameters are drawn from the range to match the high persistence of dividend yields, interest rates, and other financial predictors (Welch & Goyal 2008). The correlation structure with captures modest cross-correlation among predictors.
Random Fourier Features are constructed as where and . Standardization is applied as where following universal practice in RFF implementations.
My parameter exploration covers the comprehensive space:
-
•
Number of features:
-
•
Training window: months
-
•
Kernel bandwidth:
-
•
Input dimension: .
5.2 Experimental Goal
The primary objective is to test whether standardization preserves the convergence established in Rahimi & Recht (2007). Under the null hypothesis that standardization has no effect, both standard and standardized RFF should exhibit identical convergence properties and error distributions. Theorem 1 predicts systematic breakdown with training-set dependent limits .
I conduct 1,000 independent trials per parameter combination, generating fresh training data, RFF weights, and query points for each trial. This provides robust statistical power to detect systematic effects across the parameter space while controlling for random variations in specific realizations.
5.3 Comparison Metrics
My empirical analysis employs four complementary approaches to characterize the extent and nature of kernel approximation breakdown. I begin by examining convergence properties through mean absolute error between empirical and true Gaussian kernels, tracking how approximation quality evolves as . This directly tests whether standardized features preserve the fundamental convergence properties established in Rahimi & Recht (2007).
To quantify the systematic nature of performance deterioration, I construct degradation factors as the ratio across matched parameter combinations. Values exceeding unity indicate that standardization worsens kernel approximation, while larger ratios represent more severe breakdown. This metric provides a scale-invariant measure of standardization effects that facilitates comparison across different parameter regimes.
Statistical significance is assessed through Kolmogorov-Smirnov two-sample tests comparing error distributions between standard and standardized RFF implementations. Under the null hypothesis that standardization preserves distributional properties, these tests should yield non-significant results. Systematic rejection of this null across parameter combinations provides evidence that standardization fundamentally alters the mathematical behavior of RFF methods beyond what could arise from random variation.
Finally, I conduct comprehensive parameter sensitivity analysis to identify the conditions under which breakdown effects are most pronounced. Heatmap visualizations reveal how degradation severity depends on combinations, enabling us to characterize the parameter regimes where theoretical guarantees are most severely compromised. This analysis is particularly relevant for understanding the implications for existing empirical studies that employ specific parameter configurations.
5.4 Results and Validation of Theorem 1
5.4.1 Universal Convergence Failure
Figure 1 provides decisive evidence of convergence breakdown. Standard RFF (blue circles) exhibit the theoretically predicted convergence rate, with mean absolute error declining from at to at . This confirms that unstandardized features preserve Gaussian kernel approximation properties.
In stark contrast, standardized RFF (red squares) completely fail to converge, plateauing around - mean error regardless of . For large , standardized features are worse than standard RFF, demonstrating that additional features provide no approximation benefit when standardization is applied. This plateau behavior directly validates Theorem LABEL:thm:standardization_breakdown’s prediction that standardized features converge to training-set dependent limits rather than the target Gaussian kernel.
5.4.2 Systematic Degradation Across Parameter Space
Figure 2 reveals that breakdown occurs universally across all parameter combinations, with no regime where standardization preserves kernel properties. The degradation patterns exhibit clear economic intuition and align closely with the theoretical mechanisms underlying Theorem 1.
The most pronounced effects emerge along the feature dimension, where degradation increases dramatically with , ranging from 1.2 times at to 6.0 times at . This escalating pattern reflects the cumulative nature of standardization artifacts: as more features undergo within-sample standardization, the collective distortion of kernel approximation properties intensifies. Each additional standardized feature contributes random scaling factors that compound to produce increasingly severe departures from the target Gaussian kernel.
Sample size effects provide particularly compelling evidence for the breakdown mechanism. Smaller training windows exhibit severe degradation, reaching 41.6 times deterioration for months. This extreme sensitivity to sample size occurs because standardization relies on empirical variance estimates that become increasingly unreliable with limited data. When training windows shrink to the 6-12 month range typical in financial applications, these variance estimates introduce substantial noise that fundamentally alters the scaling relationships required for kernel convergence. The magnitude of this effect—exceeding 40 times degradation in realistic scenarios—demonstrates that standardization can completely overwhelm any approximation benefits from additional features.
Kernel bandwidth parameters reveal additional structure in the breakdown pattern. Low bandwidth values () produce 12.8 times degradation, while higher bandwidths stabilize around 3.1 times deterioration. This occurs because tighter kernels, which decay more rapidly with distance, are inherently more sensitive to the scaling perturbations introduced by standardization. Small changes in feature magnitudes translate into disproportionately large changes in kernel values when the bandwidth is narrow, amplifying the distortions created by training-set dependent scaling factors.
In contrast, input dimension effects remain remarkably stable, with degradation ranging only between 3.1 and 4.6 times across . This stability confirms that breakdown stems primarily from the standardization procedure itself rather than the complexity of the underlying input space. Whether using 5 or 30 predictor variables, the fundamental mathematical properties of standardized RFF remain equally compromised, suggesting that the kernel approximation failure is intrinsic to the standardization mechanism rather than an artifact of high-dimensional inputs.
5.4.3 Parameter Sensitivity Analysis
Figure 3 provides detailed parameter sensitivity analysis through degradation factor heatmaps. The interaction reveals that combinations typical in financial applications—such as features with months—produce degradation factors exceeding . This directly impacts methods like Kelly et al. (2024) using and .
The interaction shows that standardization effects compound: high complexity () combined with tight kernels () yields degradation exceeding . These parameter ranges are commonly employed in high-dimensional return prediction, suggesting widespread applicability of my breakdown results.
5.4.4 Statistical Significance
The error distributions between standard and standardized RFF are fundamentally different across the entire parameter space, providing strong statistical evidence against the null hypothesis that standardization preserves kernel approximation properties. Figure 4 presents Kolmogorov-Smirnov test statistics that consistently exceed 0.5 across most parameter combinations, with many approaching the theoretical maximum of 1.0. Such large test statistics indicate that the cumulative distribution functions of standard and standardized RFF errors diverge substantially, ruling out the possibility that observed differences arise from sampling variation.
The statistical evidence is most compelling in parameter regimes commonly employed in financial applications. For high feature counts (), KS statistics approach 0.9, while short training windows () yield statistics near 1.0. These values correspond to p-values that are effectively zero, providing overwhelming evidence to reject the null hypothesis of distributional equivalence. The magnitude of these test statistics exceeds typical significance thresholds by orders of magnitude, establishing statistical significance that is both robust and economically meaningful.
The systematic pattern of large KS statistics across parameter combinations demonstrates that the breakdown identified in Theorem 1 is not confined to specific implementation choices or edge cases. Instead, the distributional differences persist universally across realistic parameter ranges, indicating that standardization fundamentally alters the stochastic properties of RFF approximation errors. This statistical evidence complements the degradation factor analysis by confirming that the observed differences represent genuine distributional shifts rather than changes in central tendency alone.
These results establish that standardization creates systematic, statistically significant alterations to RFF behavior that cannot be attributed to random variation, specific parameter selections, or implementation artifacts. The universality and magnitude of the statistical evidence provide definitive support for the conclusion that practical RFF implementations cannot achieve the theoretical kernel approximation properties that justify their use in high-dimensional prediction problems.
5.4.5 Alternative Kernel Convergence
Figure 5 provides empirical validation of Theorem 1’s central prediction that within-sample standardization fundamentally alters Random Fourier Features convergence properties. The analysis compares three distinct convergence behaviors across varying feature dimensions :
The blue line demonstrates that standard (non-standardized) RFF achieve the theoretical convergence rate to the Gaussian kernel , validating the foundational result of Rahimi & Recht (2007). The convergence follows the expected Monte Carlo rate, with mean absolute error decreasing from approximately at to at .
The red line reveals the fundamental breakdown predicted by Theorem 1: standardized RFF fail to converge to the Gaussian kernel, instead exhibiting slower convergence with substantially higher errors. At , the error remains above —four times larger than the standard case—demonstrating that standardization prevents achievement of the theoretical guarantees.
Most importantly, the green line confirms Theorem 1’s constructive prediction by showing that standardized RFF do converge to the modified limit . This convergence exhibits the canonical rate, reaching error levels below at , thereby validating my theoretical characterization of the standardized limit.
My empirical validation employs the sample standard deviation standardization actually used in practice:
(5.2) | ||||
(5.3) |
rather than the simpler RMS normalization that might be assumed theoretically. This distinction strengthens rather than weakens my validation for two crucial reasons.
First, Theorem 1’s fundamental insight—that any reasonable standardization procedure breaks Gaussian kernel convergence and creates training-set dependence—remains intact regardless of the specific standardization formula. The theorem establishes that standardized features converge to some training-set dependent limit , with the exact form depending on implementation details.
Second, testing against the actual standardization procedure used in practical implementation ensures that my theoretical predictions match real-world behavior. The fact that standardized RFF converge to the correctly computed rather than to provides the strongest possible validation: my theory successfully predicts the behavior of methods as actually implemented, not merely as idealized.
The convergence patterns thus confirm all key predictions of Theorem 1: standardization breaks the foundational convergence guarantee of RFF theory, creates training-set dependent kernels that violate shift-invariance, and produces systematic errors that persist even with large feature counts. These findings validate my theoretical framework while highlighting the critical importance of analyzing methods as actually implemented rather than as theoretically idealized.
5.4.6 Implications for Existing Theory
My results provide definitive empirical validation of Theorem 1 across the entire parameter space relevant for financial applications. The universal nature of degradation—ranging from modest effects to extreme breakdown—demonstrates that standardization fundamentally alters RFF convergence properties regardless of implementation details.
Notably, parameter combinations employed by leading studies exhibit substantial degradation: Kelly et al. (2024)’s configuration (, , ) falls in the - degradation range, while more extreme combinations approach or higher degradation. This suggests that empirical successes documented in the literature cannot arise from the theoretical kernel learning mechanisms that justify these methods.
The systematic nature of these effects, combined with their large magnitudes, supports the conclusion that alternative explanations—such as the mechanical pattern matching identified by Nagel (2025)—are required to understand why high-dimensional RFF methods achieve predictive success despite fundamental theoretical breakdown.
6 Conclusion
This paper resolves fundamental puzzles in high-dimensional financial prediction by providing rigorous theoretical foundations that explain when and why complex machine learning methods succeed or fail. My analysis contributes three key results that together clarify the apparent contradictions between theoretical claims and empirical mechanisms in recent literature.
First, I prove that within-sample standardization—employed in every practical Random Fourier Features implementation—fundamentally breaks the kernel approximation that underlies existing theoretical frameworks. This breakdown explains why methods operate under different conditions than theoretical assumptions and must rely on simpler mechanisms than advertised.
Second, I establish sharp sample complexity bounds showing that reliable extraction of weak financial signals requires sample sizes and signal strengths far exceeding those available in typical applications. These information-theoretic limits demonstrate that apparent high-dimensional learning often reflects mechanical pattern matching rather than genuine complexity benefits.
Third, I derive precise learning thresholds that characterize the boundary between learnable and unlearnable regimes, providing practitioners with concrete tools for evaluating when available data suffices for reliable prediction versus when apparent success arises through statistical artifacts.
These results explain why methods claiming sophisticated high-dimensional learning often succeed through simple volatility-timed momentum strategies operating in low-dimensional spaces bounded by sample size. Rather than discouraging complex methods, my findings provide a framework for distinguishing genuine learning from mechanical artifacts and understanding what such methods actually accomplish.
The theoretical insights extend beyond the specific methods analyzed, offering guidance for evaluating any high-dimensional approach in challenging prediction environments. As machine learning continues to transform finance, rigorous theoretical understanding remains essential for distinguishing genuine advances from statistical mirages and enabling more effective application of these powerful but often misunderstood techniques.
References
- (1)
- Bartlett et al. (2020) Bartlett, P. L., Long, P. M., Lugosi, G. & Tsigler, A. (2020), ‘Benign overfitting in linear regression’, Proceedings of the National Academy of Sciences 117(48), 30063–30070.
- Belkin et al. (2019) Belkin, M., Hsu, D., Ma, S. & Mandal, S. (2019), ‘Reconciling modern machine‐learning practice and the bias–variance trade‐off’, Proceedings of the National Academy of Sciences 116(32), 15849–15854.
- Bianchi et al. (2021) Bianchi, D., Büchner, M. & Tamoni, A. (2021), ‘Bond risk premiums with machine learning’, Review of Financial Studies 34(2), 1046–1089.
- Blumer et al. (1989) Blumer, A., Ehrenfeucht, A., Haussler, D. & Warmuth, M. K. (1989), ‘Learnability and the vapnik-chervonenkis dimension’, Journal of the ACM 36(4), 929–965. Key paper connecting VC dimension to PAC learnability.
- Chen et al. (2024) Chen, L., Pelger, M. & Zhu, J. (2024), ‘Deep learning in asset pricing’, Management Science 70(2), 714–750.
- Feng et al. (2020) Feng, G., Giglio, S. & Xiu, D. (2020), ‘Taming the factor zoo: A test of new factors’, Journal of Finance 75(3), 1327–1370.
- Gu et al. (2020) Gu, S., Kelly, B. & Xiu, D. (2020), ‘Empirical asset pricing via machine learning’, Review of Financial Studies 33(5), 2223–2273.
- Hastie et al. (2022) Hastie, T., Montanari, A., Rosset, S. & Tibshirani, R. J. (2022), ‘Surprises in high-dimensional ridgeless least squares interpolation’, Annals of Statistics 50(2), 949–986.
- Hastie et al. (2009) Hastie, T., Tibshirani, R. & Friedman, J. (2009), The Elements of Statistical Learning: Data Mining, Inference, and Prediction, 2 edn, Springer, New York.
- Kearns & Vazirani (1994) Kearns, M. J. & Vazirani, U. V. (1994), An Introduction to Computational Learning Theory, MIT Press.
- Kelly et al. (2024) Kelly, B., Malamud, S. & Zhou, K. (2024), ‘The virtue of complexity in return prediction’, Journal of Finance 79(1), 459–503.
- Mei & Montanari (2022) Mei, S. & Montanari, A. (2022), ‘The generalization error of random features regression: Precise asymptotics and the double descent curve’, Communications on Pure and Applied Mathematics 75(4), 667–766.
- Nagel (2025) Nagel, S. (2025), ‘Seemingly virtuous complexity in return prediction’, Working paper .
- Rahimi & Recht (2007) Rahimi, A. & Recht, B. (2007), Random features for large-scale kernel machines, in ‘Advances in Neural Information Processing Systems’, Vol. 20, pp. 1177–1184.
- Rudi & Rosasco (2017) Rudi, A. & Rosasco, L. (2017), Generalization properties of learning with random features, in ‘Advances in Neural Information Processing Systems’, Vol. 30, pp. 3215–3225.
- Shalev-Shwartz & Ben-David (2014) Shalev-Shwartz, S. & Ben-David, S. (2014), Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, Cambridge, UK. Modern textbook with clear exposition of VC theory and PAC learning.
- Sutherland & Schneider (2015) Sutherland, D. J. & Schneider, J. (2015), On the error of random fourier features, in ‘Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence’, pp. 862–871.
-
Tropp (2012)
Tropp, J. A. (2012), ‘User-friendly tail bounds for sums of random matrices’, Foundations of Computational Mathematics 12(4), 389–434.
See especially Theorem 6.2 for the matrix Bernstein inequality used in the proof.
https://doi.org/10.1007/s10208-011-9099-z - Tropp (2015) Tropp, J. A. (2015), An Introduction to Matrix Concentration Inequalities, Vol. 8 of Foundations and Trends in Machine Learning, Now Publishers, Boston.
- Valiant (1984) Valiant, L. G. (1984), ‘A theory of the learnable’, Communications of the ACM 27(11), 1134–1142.
- Vapnik (1998) Vapnik, V. N. (1998), Statistical Learning Theory, Wiley, New York. Comprehensive treatment of VC theory and statistical learning.
- Vapnik & Chervonenkis (1971) Vapnik, V. N. & Chervonenkis, A. Y. (1971), ‘On the uniform convergence of relative frequencies of events to their probabilities’, Theory of Probability & Its Applications 16(2), 264–280. Foundational paper introducing VC dimension.
- Welch & Goyal (2008) Welch, I. & Goyal, A. (2008), ‘A comprehensive look at the empirical performance of equity premium prediction’, Review of Financial Studies 21(4), 1455–1508.






Appendix A Technical Proofs for Kernel Approximation Breakdown
This appendix provides complete mathematical proofs for the results in Section 3. We establish that within-sample standardization of Random Fourier Features fundamentally breaks the Gaussian kernel approximation that underlies the theoretical framework of high-dimensional prediction methods.
A.1 Model Setup and Notation
We analyze the standardized Random Fourier Features used in practical implementations. Draw , independently of the training set . For query points , define the standardized kernel function:
Given i.i.d. copies , we write .
A.2 Proof of Theorem 1
The proof proceeds in two steps: establishing almost-sure convergence in part (a) and demonstrating training-set dependence in part (b).
A.2.1 Step 1: Integrability and Almost-Sure Convergence
We first establish that has finite expectation, enabling application of the strong law of large numbers.
Write
Since , integrability of follows once we show . Lemma 1 proves this claim.
Using , we obtain:
for every . Hence .
Since the variables are i.i.d. with finite mean, Kolmogorov’s strong law yields:
This establishes part (i) of Theorem 1.
A.2.2 Step 2: Training-Set Dependence
We now prove that the limiting kernel depends on the training set, unlike the Gaussian kernel.
Define the radial function:
Now fix and compare two training sets:
Write and . Conditioning on :
Because is Gaussian with variance , scaling strictly enlarges . By Lemma 2, this implies on a set of of positive measure. Since on that set, the two integrals—and therefore the two kernels—differ:
The Gaussian kernel depends only on and is training-set independent. Hence , which proves part (b) of Theorem 1.
A.3 Supporting Lemmas
Lemma 1 (Small–ball estimate).
Let satisfy the affine–independence assumption
(A) |
Draw and independently and set
Then there exists a constant (depending on ) such that for every ,
Proof of Lemma 1.
We convert the small–ball event into a geometric one. Using the inequality , where is the distance of to the points where , the condition forces the vector to lie inside an -dimensional Euclidean ball of radius , whose volume scales like . Because the affine map has full rank, the Gaussian density of its image is uniformly bounded, so the probability of the event is at most a constant times this volume, yielding the bound .
Put and write . Then
For every with we have
(A.1) |
(Use for and set .)
Because and ,
Hence the event implies
The Lebesgue volume of is with the unit-ball volume in .
Write By linearity, with Assumption (A) implies is non–singular, so possesses a density satisfying
For every fixed we have so
Finally,
where . ∎
Lemma 2 (Strict Radial Monotonicity).
The derivative satisfies for every .
Proof of Lemma 2.
Using the identity and the isotropy of , . Each is positive and increasing on , and the series converges absolutely on compacts, so term-wise differentiation gives . ∎
A.4 Connection to Existing Literature
Our analysis uses only the first four moments of the draw for , which aligns with the finite-moment conditions imposed in Kelly et al. (2024). Specifically, their Condition 0 requires , which our standard Gaussian assumption satisfies. No additional distributional assumptions beyond those already present in the KMZ framework are required for our impossibility results.
The breakdown we establish is therefore endemic to the standardized RFF approach as implemented, rather than an artifact of stronger technical conditions. This reinforces the fundamental nature of the theory-practice disconnect we identify.
Appendix B Technical Proofs for Section 4
Proof of Theorem 2.
The strategy is the classical minimax/Fano route: (i) build a large packing of well-separated parameters, (ii) show that their induced data distributions are statistically indistinguishable, (iii) invoke Fano’s inequality to bound any decoder’s error, and (iv) convert decoder error into a lower bound on prediction risk.
Packing construction. Fix a radius . Because the Euclidean ball in has volume growth proportional to , it contains a -packing of size ; hence . Define . For each index let denote the joint distribution of the training sample generated according to with independent Gaussian noise .
Average KL divergence. Let be the random design matrix whose -th row is . Conditioned on the log-likelihood ratio between and is Gaussian, and one checks
Taking expectation over and using gives
(The inequality uses and .)
Fano’s inequality. Draw an index uniformly from and let be any measurable decoder based on the sample . Fano’s max–KL form (e.g. CoverThomas2006, Eq. 16.32) yields
Choosing the packing radius such that the right-hand side equals (so that any decoder errs at least half the time) gives
(B.1) |
Link between prediction risk and decoder error. Let be an arbitrary estimator and put . Because the nearest-neighbour decoder chooses , the triangle inequality gives
Meanwhile each pair in the packing satisfies ; since , . Consequently, if the decoder must succeed (), contradicting . Hence
(B.2) |
Expectation lower bound. Substituting (B.1) into (B.2) and absorbing the harmless factor into a constant yields
which is the desired in-expectation bound.
High-probability refinement over the design. Finally, define the “well-conditioned design” event
For sub-Gaussian rows, the matrix Bernstein inequality (Tropp 2012, Theorem 6.2) guarantees provided . On the empirical Gram matrix satisfies , so the previous KL-and-distance calculations hold with constants . Repeating the Fano–risk argument under therefore gives
for every fixed . Taking outer expectation over the design and using produces the advertised high-probability bound. ∎
Proof of Theorem 3.
Part (a) Let be the standard basis of . Define
All lie in the ball , and .
For let be the distributions of the samples when the true parameter is or . Conditioned on the design matrix , both are Gaussians with means and covariance . Taking expectation over ,
With equiprobable hypotheses, Fano gives
Because ,
If attains mean-squared error , then on the event the triangle inequality forces , contradicting the separation just shown. Therefore
Substituting the definition of yields
Setting completes the proof.
Part (b)
1. Packing of the coefficient ball.
Let be the canonical basis in and set
All lie in the Euclidean ball and satisfy
2. A “good-design” event.
Define
By the sub-Gaussian matrix Bernstein inequality (e.g., Tropp (2015)) there is a constant such that
(B.3) |
3. KL bound conditional on .
For the conditional Kullback–Leibler divergence equals
On we have , so
4. Fano’s inequality conditional on .
With the hypotheses equiprobable, Fano (max-KL form) gives, conditional on ,
5. Relating risk to identification (conditional).
Since the population covariance satisfies , for any
Argument identical to Theorem 3 shows that for every estimator and every
(B.3) |
6. Remove the conditioning.
(a) Linear class .
Because for every , the norm bound does not remove any labelings that an unconstrained homogeneous hyperplane in could realise. Hence the set has the same VC dimension as all homogeneous linear separators in , namely .
(b) Ridgeless class .
For any training targets the ridgeless solution is , where † denotes the Moore–Penrose pseudoinverse. Consequently every predictor can be written as
Define the data–dependent feature map
Its image lies in the -dimensional subspace , so after an appropriate linear change of basis. Thus the hypothesis class
is (up to an invertible linear map) exactly the class of homogeneous linear separators in . By the cited VC fact, . Because , we obtain the claimed bound. If is invertible, then , giving equality. ∎
Proof of Theorem 5.
The proof follows from the polynomial lower bound in Theorem 3:
For learning to be impossible with error , we need:
Phase I (Impossible Learning): Suppose and .
Since both arguments of the minimum satisfy the bound , we have:
Therefore:
establishing that learning with error is information-theoretically impossible.
Phase II (Possible Learning): Suppose and .
Since , we have:
The lower bound becomes:
Since the information-theoretic lower bound is , learning with error is not ruled out by fundamental limitations.
Trivial Regime: If , then regardless of the value of :
Hence:
The function class is too simple relative to target accuracy , and standard parametric rates apply. ∎
Proof of Corollary 1.
We analyze when the conditions of Theorem 5 are satisfied.
For impossibility, we need . Since , we have , so:
We also need . Under Assumption LABEL:ass:weak_signal, , so:
Learning is impossible when both conditions hold simultaneously:
(B.4) | ||||
(B.5) |
For fixed , the complexity condition gives:
Learning is impossible when .
This interval is non-empty when is sufficiently small, specifically when:
∎