When training a machine learning model, regularization is the primary tool used to prevent overfitting. By penalizing model complexity—whether through Tikhonov penalties ($L_2$), Lasso penalties ($L_1$), or structural constraints—we force the model to ignore random fluctuations in finite training data.
However, a fundamental tension arises as the volume of available data grows. If the regularization penalty remains fixed while the sample size $n$ approaches infinity, the model remains permanently constrained by its initial bias. It will fail to exploit the richer information provided by the larger dataset, resulting in underfitting. Conversely, if the regularization penalty is removed entirely or reduced too quickly, the model will overfit the remaining noise in the finite sample.
To achieve statistical consistency—where the learned model converges to the true underlying distribution or the optimal Bayes risk—the regularization parameter $\lambda$ cannot be a static constant. Instead, it must be treated as a dynamic function of the sample size, $\lambda(n)$, designed to vanish at a mathematically precise rate.
The Classical Scaling Benchmarks
The optimal rate at which regularization should decay depends heavily on the geometry of the loss function and the structure of the hypothesis space. In classical parametric and linear settings, two primary scaling laws emerge: $1/n$ and $1/\sqrt{n}$.
In random-design linear regression, Petri Koistinen demonstrated in Asymptotic Theory for Regularization: One-Dimensional Linear Case that the optimal regularization parameter for ridge regression scales as $1/n$. When a model is misspecified, maintaining this strict $1/n$ inverse scaling is critical; failing to reduce the penalty at this rate actively degrades generalization performance as more data becomes available.
For problems focused on sparse recovery or low-rank matrix estimation, the critical threshold shifts to the inverse square root of the sample size ($n^{-1/2}$). In Bolasso: model consistent Lasso estimation through the bootstrap, Bach et al. showed that adjusting the Lasso penalty to decay at a rate proportional to $n^{-1/2}$ ensures model consistency. This specific rate ensures that true features are selected with high probability across bootstrap samples, while the selection of noise variables remains unstable and can be filtered out.
A similar boundary appears in matrix factorization. Bach et al. proved in Consistency of trace norm minimization that an $n^{-1/2}$ scaling factor provides the exact threshold required to achieve parametric convergence and guarantee correct rank recovery rather than overfitting the noise.
Infinite-Dimensional Spaces and Kernel Machines
When moving from linear models to non-parametric kernel methods, the hypothesis space becomes infinite-dimensional. This drastically increases the risk of overfitting, requiring careful coordination between the sample size and the regularization strength.
Rosasco et al. provided the foundational mathematical bridge for this regime in Learning, Regularization and Ill-Posed Inverse Problems. By framing supervised learning as a discretized operator equation, the authors proved that the consistency of kernel learning algorithms can be derived using classical Tikhonov regularization tools, provided the regularization parameter is scaled as a specific power of the sample size.
To determine how fast these methods converge, Steinwart et al. established tight learning rates in Fast Rates to Bayes for Kernel Machines. They showed that by precisely scheduling the decay of the regularization parameter relative to the underlying geometric noise conditions of the dataset, Support Vector Machines (SVMs) with Gaussian kernels can achieve nearly linear convergence rates ($n^{-1+\epsilon}$). Furthermore, Steinwart et al. demonstrated in Sparsity of SVMs that use the epsilon-insensitive loss that scaling the parameter inversely with the sample size ensures universal consistency while simultaneously maintaining stable sparsity, preventing the number of support vectors from growing uncontrollably.
For multivariate correlation methods, the scaling laws must be adjusted to preserve numerical stability. Fukumizu et al. proved in Statistical Convergence of Kernel CCA that to guarantee convergence to the population solution, the regularization coefficient must decay at a rate where the product of the cube root of the sample size and the coefficient approaches infinity ($n^{1/3}\lambda_n \to \infty$).
This need for controlled decay is also vital for hypothesis testing. Harchaoui et al. demonstrated in Testing for Homogeneity with Kernel Fisher Discriminant Analysis that establishing a specific vanishing rate for the regularization parameter is what stabilizes the limiting distribution of the test statistic, allowing the homogeneity test to remain consistent across complex data types. The persistent challenge of identifying these exact decay boundaries across diverse multi-class settings was further highlighted by Tobias Glasmachers in Universal Consistency of Multi-Class Support Vector Classification.
Resolving Paradoxes in Bayesian and Agnostic Learning
The necessity of sample-dependent scaling extends beyond frequentist optimization into Bayesian inference and information-theoretic learning rules.
In Bayesian model selection, employing a fixed regularization parameter in a prior can lead to Bartlett’s paradox, a phenomenon where the marginal likelihood becomes pathologically biased toward the simplest possible null model, completely ignoring the empirical evidence as the dataset grows. Jordan et al. resolved this boundary condition in Posterior Consistency of the Silverman g-prior in Bayesian Model Choice. The authors proved that by dynamically scaling the regularization parameter in kernel-based priors inversely with the sample size, the prior's influence diminishes at the correct rate, avoiding the paradox and ensuring posterior consistency.
Fixed Prior Penalty (λ = constant) ──> Retains bias, causes Bartlett's Paradox
Sample-Scaled Penalty (λ ∝ 1/n) ──> Diminishes prior bias, ensures Posterior Consistency
Similarly, when learning the structure of graphical models, Eggeling et al. showed in On Structure Priors for Learning Bayesian Networks that sample-size dependent prior scaling is essential. It exerts a powerful regularizing force when data is scarce to prevent overfitting to spurious correlations, yet gracefully allows the data likelihood to dominate the posterior as the sample size expands.
From an information-theoretic perspective, Srebro et al. provided an exact characterization of this tension within the Minimum Description Length (MDL) framework in Quantifying Overfitting along the Regularization Path for Two-Part-Code MDL in Supervised Classification. They proved that for agnostic learning to remain strongly consistent, the complexity penalty must grow relative to the sample size within a highly specific range. If the parameter grows too slowly, the model under-regularizes and overfits the noise; if it grows too quickly, it over-regularizes and ignores the data entirely.
Modern Frontiers: Optimal Transport and Implicit Scaling
The principles of sample-dependent parameter scaling continue to guide modern non-parametric problems, such as optimal transport (OT) map estimation and graph-based semi-supervised learning.
When estimating discontinuous transport maps from continuous to discrete distributions, Pooladian et al. demonstrated in Minimax estimation of discontinuous optimal transport maps: The semi-discrete case that scaling the entropic regularization parameter inversely with the square root of the sample size ($n^{-1/2}$) balances approximation bias and estimation variance. This specific scaling achieves a minimax optimal convergence rate that remains entirely independent of the input dimensionality. For conditional simulation tasks, Baptista et al. showed in Conditional simulation via entropic optimal transport: Toward non-parametric estimation of conditional Brenier maps that linking the cost function's scaling parameters to a negative power of the sample size (such as $n^{-1/5}$) serves as a robust rule of thumb for maintaining statistical accuracy.
In graph-based settings, the scaling relationship often involves geometric connectivity alongside explicit penalties. Slepcev et al. analyzed this in Analysis of p-Laplacian Regularization in Semisupervised Learning, demonstrating how the connectivity radius $\varepsilon$ of a random graph must scale relative to the number of points $n$ to ensure the well-posedness and stability of the learned functions as the graph converges to a continuous domain.
Implicit Regularization via Early Stopping
Regularization does not always have to be explicitly programmed as a penalty term in a loss function. One of the most profound insights in modern learning theory is that optimization algorithms can introduce implicit regularization.
Rosasco et al. formalized this concept in Learning with Incremental Iterative Regularization by analyzing incremental gradient methods like Stochastic Gradient Descent (SGD). They proved that the number of training passes (epochs) acts directly as an implicit regularization parameter.
To maintain statistical consistency as the dataset grows, the optimal number of training passes must scale as a specific power of the total sample size. Stopping too early acts like an overly aggressive Tikhonov penalty, while optimization for too long mirrors under-regularization. Calibrating the number of iterations to the sample size ensures the model's algorithmic complexity matches the available information volume.
Data-Driven Parameter Selection
While asymptotic scaling laws provide theoretical targets (e.g., $\lambda \propto n^{-1}$), practitioners cannot easily compute the exact optimal coefficient for a finite dataset because the underlying noise level and true function smoothness are unknown.
To bridge theory and practice, Rodriguez et al. studied data-driven parameter selection in On Learning the Optimal Regularization Parameter in Inverse Problems. By applying Empirical Risk Minimization (ERM) to a training set of known solutions, the authors proved that a data-driven approach can learn the optimal regularization parameter without prior knowledge of the problem's smoothness.
Crucially, the performance gap between these learned parameters and the ideal theoretical optimum decreases at a rate proportional to the inverse or square root of the number of training samples. This confirms that we can learn how to scale regularization parameters directly from data, matching the performance of optimal a priori theoretical rules.
Key Foundational Work
Asymptotic Theory for Regularization: One-Dimensional Linear Case (1997) — contributed 3 concept elements to this direction.
Learning, Regularization and Ill-Posed Inverse Problems (2004) — contributed 2 concept elements to this direction.
Fast Rates to Bayes for Kernel Machines (2004) — contributed 1 concept elements to this direction.