High-Dimensional Asymptotics

Follow this topic Ask about this topic

Latest papers

19 papers5 papers in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

Oct 15, 2026

Hard Way, The Only Way: Provable Merits of Training on Hardest Examples

Despite a surge of empirical interest in the ``unreasonable effectiveness'' of drastic data pruning for AI systems, a unified theoretical understanding of this phenomenon remains elusive. In this work, we provide a precise high-dimensional theory of learning under data pruning via weighted empirical risk minimization (ERM). As in previous work, we analyze a setting where pruning is performed along a one-dimensional subspace of the input space. Our analysis precisely characterizes the limiting test error curves in the regime where the input dimension N and sample size P tend to infinity with a fixed ratio N/P. The resulting theory recovers several recent results in the literature as special cases and provides a general lens to evaluate how pruning strategies interact with the loss function and label noise. Crucially, we characterize the optimal pruning strategy in the high-sample regime where P greatly exceeds N. We demonstrate that strategic pruning can accelerate the decay of classification test error from the classical sqrt(N/P) rate, typical of vanilla ERM with loss functions without exponential tail (e.g., quadratic loss), to the much faster Bayes-optimal scaling of order N/P. In this setup, we prove that, surprisingly, this optimal performance is achieved by a drastic pruning strategy: discarding almost all training data except for a small proportion, consisting strictly of the 2N hardest training examples.

Elvis Dohmatob

Concordia University · Mila – Quebec AI Institute · FAIR – Meta

High-Dimensional Asymptotics Dataset Pruning Statistical Learning Theory Empirical Risk Minimization Hard Negative Mining

Oct 6, 2026

High-Dimensional Statistical Inference for Sparse Support Vector Machines

Using a replica-symmetric high-dimensional characterization, we develop an inferential framework for sparse support vector machines when the sample size and number of features grow proportionally. The main challenge is the nonsmooth hinge loss, which prevents direct application of debiasing arguments developed for smooth classification losses. We overcome this difficulty by representing the

L_1

-penalized support vector machine (SVM) as a linear program and identifying the hinge-loss subgradient through its dual variables. This yields a computationally accessible debiased estimator whose coordinates are asymptotically Gaussian under the proportional asymptotic regime. The resulting distributional characterization provides confidence intervals and hypothesis tests for individual features and enables false-discovery-rate-controlled variable selection. Extensive simulations examine calibration, power, and variable-selection performance under a range of covariance structures, including strongly correlated designs. An analysis of high-dimensional breast cancer gene-expression data illustrates how the proposed inference can distinguish statistically significant features from variables selected by the original sparse SVM.

Peng Zeng, Hanwen Huang

Department of Mathematics and Statistics Auburn University, Auburn, AL 36849 · Department of Biostatistics, Data Science and Epidemiology Medical College of Georgia, Augusta University, Augusta, GA, 30912

Support Vector Machines Feature Selection High-Dimensional Asymptotics

Oct 6, 2026

Asymptotic Analysis of Empirical Risk Minimization on Entry-wise i.i.d. Heavy-Tailed Data

Many real-world datasets exhibit unusually large values far more frequently than predicted by Gaussian models. Heavy-tailed distributions capture this behavior, yet evaluating learning performance under them remains challenging because rare, large feature entries retain non-vanishing effects even in high dimensions. Even in the canonical setting of empirical risk minimization for linear regression with entry-wise i.i.d. symmetric

α

-stable data, a precise asymptotic characterization of prediction has been lacking. In this work, we introduce a functional order parameter that describes the random effective problem associated with each coefficient. Using the replica method, we fully characterize the generalization error in the proportional high-dimensional limit where the sample size and feature dimension diverge at a fixed ratio. Additionally, this analysis establishes a heavy-tail universality law, scaling laws relating typical errors to prediction reliability, and the Bayes-optimal prediction error. In addition to characterizing the effects of extreme entries on the learning process, our method applies broadly to other systems with persistent local heterogeneity.

Kaito Takanami, Takashi Takahashi, Yoshiyuki Kabashima

Graduate School of Science, The University of Tokyo · Institute for Physics of Intelligence, The University of Tokyo · Trans-Scale Quantum Science Institute, The University of Tokyo

Statistical Physics of Learning High-Dimensional Asymptotics Linear Regression Heavy-Tailed Distributions Empirical Risk Minimization

Oct 1, 2026

High-Dimensional Asymptotics and Dataset Selection for Private Transfer Learning

To commit to buying external data or participate in collaborative learning, one must decide whether the additional data will improve prediction enough to justify the cost. This comes with several challenges: (i) the decision often relies only on aggregated statistics available publicly, rather than individual-level data; (ii) covariate and model shifts can induce negative transfer, so the additional data deteriorates rather than improves performance; (iii) if the data is sensitive, its privatization requires the injection of noise, which can also offset the benefit of a larger sample size. In this paper, we model the problem of dataset selection through high-dimensional regression with multiple heterogeneous sources and a weighted ridge estimator. Our approach uses only summary statistics and it gives privacy guarantees either on labels only or jointly on features and labels, in terms of

ρ

-zero-concentrated differential privacy. The main technical contribution is a deterministic equivalent of the test error, which captures the interactions between sample size, covariance structure, model shift, regularization and privacy noise. Our theory allows to optimize hyperparameters (weights and ridge regularizers) and, more broadly, to decide when private external datasets are useful without accessing the data itself but only relying on population-level quantities. This provides a theoretically tractable foundation for private transfer learning, which we support via experiments on both synthetic and real-world datasets.

Filip Kovačević, Edwige Cyffers, Stefano Sarao Mannelli +1

Institute of Science and Technology Austria. · CNRS Dauphine PSL. · Computer Science and Engineering Department, Chalmers University of Technology and University of Gothenburg. +1

High-Dimensional Asymptotics Transfer Learning

Sep 30, 2026

Asymptotic Properties of Support Vector Machines in High-Dimension, Low-Sample-Size Settings under a Spiked Model

In this paper, we consider asymptotic properties of the support vector machine (SVM) in high-dimension, low-sample-size (HDLSS) settings under a spiked model. The existing theory of the SVM in the HDLSS context relies on the geometric representation of HDLSS data, which requires that the eigenvalues of the covariance matrices are not dominant. We first show that the geometric representation does not hold under the spiked model. We show that the Gram matrix of HDLSS data converges in distribution to a random matrix, namely, the HDLSS data converge to a random configuration in a finite-dimensional space whose dimension is given by the number of the spikes. We show that the misclassification rates of the SVM do not tend to zero, that is, the SVM does not hold the consistency property. We also show that the bias-corrected SVM (BC-SVM) does not give preferable performance in this setting because the bias term itself should be modified. In order to overcome such difficulties, we propose a spike-corrected SVM (SC-SVM). We show that the SC-SVM holds the consistency property when the sample size goes to infinity, and that the growth of the sample size is essential in the sense that any projection-based procedure fails when the sample size is fixed. Finally, we check the performance of the classifiers by numerical simulations.

Yugo Nakayama

Independent researcher

Support Vector Machines Classification Statistical Learning Theory Data-Efficient Learning High-Dimensional Asymptotics

Aug 28, 2026

Learning between the peaks: sharp asymptotics for kernel ridge regression under power-law anisotropy

We study kernel ridge regression under anisotropic Gaussian data, where the input covariance decays as a power law with exponent

α\geq 0

for polynomial inner-product kernels. We derive asymptotically sharp expressions for the kernel spectrum and the generalization error in the polynomial high-dimensional regime

n=Θ(d^κ)

, revealing how anisotropy reshapes the learning curves. For weak anisotropy (

0<α<1

), the problem remains effectively high-dimensional and retains some features of the isotropic case, while departing from it in others: the variance still peaks at integer sample complexities

κ\in\mathbb{N}

, but these peaks are progressively damped as

α

grows; meanwhile, for targets strongly aligned with the data's principal directions, the bias drops at fractional sample complexities, decoupling the bias transitions from the interpolation peaks. For strong anisotropy (

α> 1

), the effective dimension of the problem is constant, and the variance stops depending on sample size altogether, plateauing under ridgeless interpolation or vanishing at an explicit rate under fixed ridge penalty. The bias undergoes a sharp transition governed by the target's decay rate: below a threshold, learning is abrupt rather than gradual; above it, the bias decays as a power law that recovers the classical source and capacity rates. We finally specialize these results to single-index targets, showing how the alignment of the index with the data's principal directions determines the effect of anisotropy on learning. Together, our results clarify how the input geometry shapes the kernel features and fundamentally impacts its generalization properties.

Lorenzo Rizzi, Arie Wortsman Zurich, Bruno Loureiro

Departement d’Informatique, École Normale Supérieure, PSL & CNRS · Dipartimento di Fisica e Astronomia, Università degli Studi di Padova · Scuola Galileiana di Studi Superiori, Università degli Studi di Padova

Kernel Ridge Regression Kernel Methods Statistical Learning Theory High-Dimensional Asymptotics

Jul 10, 2026

Influence Diagnostics in High-dimensional M-estimation: Precise Asymptotics

The impact of a given training point on a statistical model is classically measured through its leave-one-out influence, which quantifies the effect of its removal from the training set on the model accuracy. While the statistics of leave-one-out influences are well understood in the low-dimensional, large sample limit

n\to \infty, d=O(1)

, they become more intricate in high dimensions, as the influence of a given sample develops non-trivial dependencies on all other training samples. For convex M-estimation under Gaussian design, in the high-dimensional limit

n\asymp d

, we show that the distribution of the influences across the training set converges to a limiting measure which we sharply characterize. Building on these results, we provide evidence that influential samples tend to lie close to the decision boundary, thereby making contact with a standard data selection heuristic in active learning.

Hugo Cui

Université Paris-Saclay, CNRS, Laboratoire de mathématiques d’Orsay, 91405, Orsay, France

Influence Functions Training Data Attribution High-Dimensional Asymptotics

Jun 30, 2026

Homogenization of $\ell_2$ -Adversarial Training in High-Dimensions: Exact Dynamics under Stochastic Gradient Descent

We develop a framework for analyzing the learning dynamics of

\ell_2

-adversarial training of single-index models on Gaussian mixtures in the high-dimensional limit under streaming stochastic gradient descent (SGD). We derive deterministic equivalents for a broad class of statistics of the SGD iterates, including the adversarial risk and distance to adversarial optimality, in terms of the solution to a system of ODEs. We use them to study two idealized learning rate schedules: the Polyak stepsize and exact line search. In the case of

\ell_2

-adversarial least squares with a single class, we show that, unlike noiseless standard least squares, no constant learning rate guarantees monotone descent of SGD towards a minimizer of the adversarial risk. We identify anisotropic covariance and a mismatch in ridge parameters as the main sources of suboptimality of exact line search relative to the Polyak stepsize. We also introduce a stochastic differential equation (SDE), called adversarial homogenized SGD, that captures the evolution of statistics of the iterates of SGD. For

\ell_2

-adversarial least squares, using this SDE, we show the evolution of the risk is equivalent, up to dimension-free constants, to that of SGD on standard least squares with an adaptive learning rate and adaptive

\ell_2

-regularization. When the dynamics converge, the limiting adversarial risk and SGD iterate are determined by a fixed-point equation, with the limiting iterate being equivalent to the solution of a ridge regression problem whose regularization parameter is the limiting effective regularization of SGD.

Fabrizzio Sabelli

Université de Montréal

Adversarial Training High-Dimensional Asymptotics Adversarial Robustness Gradient Descent Dynamics Stochastic Gradient Descent

Jun 25, 2026

Effective Covariance Dynamics in Solvable High-Dimensional GANs

We study a solvable high-dimensional model of generative adversarial network (GAN) training in which a linear generator learns a low-dimensional subspace from data with structured latent covariance. Prior solvable GAN analyses assume unconditional signals with diagonal latent covariance; we extend the multi-feature discriminator setting to class-dependent, correlated, and non-zero-mean latent structure. For the quadratic energy discriminator, all such heterogeneity enters the dynamics through a probability-weighted effective second moment. We prove that the stochastic microscopic training process converges, in the high-dimensional limit, to deterministic ordinary differential equations governed by this effective covariance. In the matched-covariance specialization, the stability analysis yields a mode-wise solvable interval determined by the learning rates and noise level: learning begins when the leading effective eigenvalue crosses the lower threshold, while full recovery requires all relevant effective modes to remain within the interval. This reveals a signal-boosting mechanism: low-rank correlations can lift weak directions above the learnability threshold, whereas overly strong correlations destabilize recovery. Numerical simulations validate the ODE, phase boundary, and boosting mechanism. Experiments on MNIST, FashionMNIST, and CIFAR-10 further show that informed generator covariance improves alignment with the data-driven reference subspace.

Andrew Bond, Zafer Doğan

MLIP Group, KUIS AI Center, Koç University, İstanbul, Turkey. · Dept. of EE Engineering, Koç University, İstanbul, Turkey.

High-Dimensional Asymptotics Neural Network Training Dynamics Generative Adversarial Networks

May 27, 2026

Dynamics of Stochastic Momentum with Sparse Updates in High Dimensions

Existing theory of momentum assumes that gradients arrive at every parameter at a roughly constant rate, an assumption violated in practice by heavy-tailed data distributions and modern architectures. We theoretically analyze the dynamics of two tractable models of momentum under sparse updates: a least squares model with sparse inputs and a logistic regression model with a rare class. Both admit exact closed-form second-moment dynamics whose high-dimensional limits we characterize across three scaling exponents for sparsity, batch size, and momentum decay. The phase structure on both problems is governed by the ratio of two intrinsic timescales: a momentum retention timescale (how many active updates the buffer survives) and a learning timescale (how many active updates it takes to reduce the squared error). When learning is much slower than retention, the limit matches SGD; when learning is faster, the system is unstable; where the timescales coincide, we recover classical heavy-ball dynamics. The oscillatory dynamics occur at different momentum values for different token sparsity, creating a spectral conflict for global momentum across token frequencies.

Katie Everett, Elliot Paquette

Google DeepMind & MIT · McGill University & Mila

High-Dimensional Asymptotics Momentum Methods Gradient Descent Dynamics Stochastic Gradient Descent

May 16, 2026

High-dimensional Limit of SGD for Diagonal Linear Networks

Understanding the behavior of stochastic gradient methods is a central problem in modern machine learning. Recent work has highlighted diagonal linear networks as a simplified yet expressive setting for analyzing the optimization and generalization properties of neural models. In this work, we show that in the high-dimensional regime, stochastic gradient descent on diagonal linear networks is well-approximated by continuous dynamics governed by a stochastic differential equation (SDE), which explicitly decouples the drift from the gradient noise. We further derive a deterministic partial differential equation whose solution propagates the relevant state of the iterates and characterizes the time evolution of a broad class of observable statistics, including the risk, curvature, and other metrics for optimality. Finally, we show that, under a suitable parametrization, the stochastic dynamics are globally well posed and converge exponentially fast to zero risk with high probability, yielding a fully explicit non-asymptotic description of their long-time behavior. Numerical simulations corroborate our theoretical findings.

Begoña García Malaxechebarría, Courtney Paquette, Maryam Fazel +1

University of Washington · McGill University · Google DeepMind +2

Stochastic Optimization Convergence Neural Network Training Dynamics Stochastic Gradient Descent High-Dimensional Asymptotics

May 14, 2026

Large Dimensional Kernel Ridge Regression: Extending to Product Kernels

Recent studies have reported

\textit{saturation effects}

and

\textit{multiple descent behavior}

in large dimensional kernel ridge regression (KRR). However, these findings are predominantly derived under restrictive settings, such as inner product kernels on sphere or strong eigenfunction assumptions like hypercontractivity. Whether such behaviors hold for other kernels remains an open question. In this paper, we establish a broad, new family of large dimensional kernels and derive the corresponding convergence rates of the generalization error. As a result, we recover key phenomena previously associated with inner product kernels on sphere, including:

i)

the

\textit{minimax optimality}

when the source condition

s\le 1

;

ii)

the

\textit{saturation effect}

when

s>1

;

iii)

a

\textit{periodic plateau phenomenon}

in the convergence rate and a

\textit {multiple-descent behavior}

with respect to the sample size

n

.

Yang Zhou, Yicheng Li, Yuqian Cheng +1

Department of Statistics and Data Science Tsinghua University Beijing, 100084, China · Department of Mathematical Science Tsinghua University Beijing, 100084, China

Generalization Bounds Kernel Ridge Regression Kernel Regression Double Descent Kernel Methods Ridge Regression+1

May 11, 2026

Characterizing the Generalization Error of Random Feature Regression with Arbitrary Data-Augmentation

This paper aims at analyzing the regularization effect that data augmentation induces on supervised regression methods in the proportional regime, where the number of covariates grows proportionally to the number of samples. We provide a tight characterization of the test error, measured in mean squared error, in terms only of the population quantities of the true data, as well as first and second order statistics of the augmentation scheme. Our results are valid under misspecified feature maps, and for any network architecture where only the last readout layer is trained, and the rest of the network is either frozen or randomly initialized. We specify our results in the case of Gaussian data, and show that our asymptotic characterization is tight in this setting.

Lucas Morisset, Alain Durmus, Adrien Hardy

Qube Research & Technologies · École Polytechnique

Neural Network Generalization High-Dimensional Asymptotics Data Augmentation Random Feature Methods Statistical Learning Theory

Apr 3, 2026

Characterization of Gaussian Universality Breakdown in High-Dimensional Empirical Risk Minimization

We study high-dimensional convex empirical risk minimization (ERM) under general non-Gaussian data designs. By heuristically extending the Convex Gaussian Min-Max Theorem (CGMT) to non-Gaussian settings, we derive an asymptotic min-max characterization of key statistics, enabling approximation of the mean

μ_{\hatθ}

and covariance

C_{\hatθ}

of the ERM estimator

\hatθ

. Specifically, under a concentration assumption on the data matrix and standard regularity conditions on the loss and regularizer, we show that for a test covariate

x

independent of the training data, the projection

\hatθ^\top x

approximately follows the convolution of the generally non-Gaussian distribution of

μ_{\hatθ}^\top x

with an independent centered Gaussian variable of variance

\mathrm{tr}(C_{\hatθ} \mathbb{E}[xx^\top])

. This result clarifies the scope and limits of Gaussian universality for ERMs. Numerical simulations across diverse losses and models are provided to validate our theoretical predictions and qualitative insights.

Chiheb Yaakoubi, Cosme Louart, Malik Tiomoko +1

School of Data Science, The Chinese University of Hong Kong, Shenzhen, China · Huawei Noah’s Ark Lab, Huawei Technologies, Paris, France · School of Electronic Information and Communications, Huazhong University of Science & Technology, China

Empirical Risk Minimization High-Dimensional Asymptotics

Mar 19, 2026

Precise Performance of Linear Denoisers in the Proportional Regime

In the present paper we study the performance of linear denoisers for noisy data of the form

\mathbf{x} + \mathbf{z}

, where

\mathbf{x} \in \mathbb{R}^d

is the desired data with zero mean and unknown covariance

\mathbfΣ

, and

\mathbf{z} \sim \mathcal{N}(0, \mathbfΣ_{\mathbf{z}})

is additive noise. Since the covariance

\mathbfΣ

is not known, the standard Wiener filter cannot be employed for denoising. Instead we assume we are given samples

\mathbf{x}_1,\dots,\mathbf{x}_n \in \mathbb{R}^d

from the true distribution. A standard approach would then be to estimate

\mathbfΣ

from the samples and use it to construct an

empirical" Wiener filter. However, in this paper, motivated by the denoising step in diffusion models, we take a different approach whereby we train a linear denoiser $\mathbf{W}$ from the data itself. In particular, we synthetically construct noisy samples $\hat{\mathbf{x}}_i$ of the data by injecting the samples with Gaussian noise with covariance $\mathbfΣ_1 \neq \mathbfΣ_{\mathbf{z}}$ and find the best $\mathbf{W}$ that approximates $\mathbf{W}\hat{\mathbf{x}}_i \approx \mathbf{x}_i$ in a least-squares sense. In the proportional regime $\frac{n}{d} \rightarrow κ> 1$ we use the {\it Convex Gaussian Min-Max Theorem (CGMT)} to analytically find the closed form expression for the generalization error of the denoiser obtained from this process. Using this expression one can optimize over $\mathbfΣ_1$ to find the best possible denoiser. Our numerical simulations show that our denoiser outperforms the

empirical" Wiener filter in many scenarios and approaches the optimal Wiener filter as

κ\rightarrow\infty

.

Reza Ghane, Danil Akhtiamov, Babak Hassibi

California Institute of Technology, Pasadena, CA, 91125

High-Dimensional Asymptotics

Feb 19, 2026

Topological Exploration of High-Dimensional Empirical Risk Landscapes: general approach, and applications to phase retrieval

We consider the landscape of empirical risk minimization for high-dimensional Gaussian single-index models (generalized linear models). The objective is to recover an unknown signal

\boldsymbolθ^\star \in \mathbb{R}^d

(where

d \gg 1

) from a loss function

\hat{R}(\boldsymbolθ)

that depends on pairs of labels

(\mathbf{x}_i \cdot \boldsymbolθ, \mathbf{x}_i \cdot \boldsymbolθ^\star)_{i=1}^n

, with

\mathbf{x}_i \sim \mathcal{N}(0, I_d)

, in the proportional asymptotic regime

n \asymp d

. Using the Kac-Rice formula, we analyze different complexities of the landscape -- defined as the expected number of critical points -- corresponding to various types of critical points, including local minima. We first show that some variational formulas previously established in the literature for these complexities can be drastically simplified, reducing to explicit variational problems over a finite number of scalar parameters that we can efficiently solve numerically. Our framework also provides detailed predictions for properties of the critical points, including the spectral properties of the Hessian and the joint distribution of labels. We apply our analysis to the real phase retrieval problem for which we derive complete topological phase diagrams of the loss landscape, characterizing notably BBP-type transitions where the Hessian at local minima (as predicted by the Kac-Rice formula) becomes unstable in the direction of the signal. We test the predictive power of our analysis to characterize gradient flow dynamics, finding excellent agreement with finite-size simulations of local optimization algorithms, and capturing fine-grained details such as the empirical distribution of labels. Overall, our results open new avenues for the asymptotic study of loss landscapes and topological trivialization phenomena in high-dimensional statistical models.

Antoine Maillard, Tony Bonnaire, Giulio Biroli

INRIA Paris & DI ENS, PSL University, Paris, France. · Université Paris-Saclay, CNRS, Institut d’Astrophysique Spatiale, 91405 Orsay, France · Laboratoire de Physique de l’École normale supérieure, ENS, Université PSL, CNRS, Sorbonne Université, Université Paris Cité, F-75005 Paris, France

Loss Landscape Loss Landscape Geometry Empirical Risk Minimization High-Dimensional Asymptotics

Oct 15, 2025

Exact Dynamics of Multi-class Stochastic Gradient Descent

We develop a framework for analyzing the learning dynamics of high-dimensional problems trained using one-pass stochastic gradient descent (SGD) with data from multiple anisotropic classes. Our main theorem provides exact expressions for quantities of interest, including the risk and the overlap with the true signal, in terms of a deterministic system of ODEs, valid in the high-dimensional limit. The theorem holds for a broad class of optimization problems and extends to settings where the number of classes grows with dimension. To illustrate its utility, we investigate in detail the effect of the data's anisotropic structure on the problems of binary logistic regression and least-squares (LS) loss. We study the LS in a linear multiclass setup and derive a learning-rate threshold that depends on the average eigenvalue of the covariance matrices. In the binary logistic regression, we study three cases: isotropic covariances, data covariance matrices with a large fraction of zero eigenvalues (denoted as the zero-one model), and covariance matrices with power-law spectra. We show that a structural phase transition occurs. In particular, for the zero-one model and the power-law model with sufficiently large power, SGD aligns more closely with values of the class mean that are projected onto the ``clean directions'' (i.e., directions of smaller variance). This is supported by analytical studies and numerical simulations, which show the exact asymptotic behavior of the loss in the high-dimensional limit. The effects of data anisotropy that we demonstrate are likely to hold beyond these examples and illustrate one application of the broader theorem that we prove.

Elizabeth Collins-Woodfin, Inbar Seroussi

Logistic Regression High-Dimensional Asymptotics Gradient Descent Dynamics Stochastic Gradient Descent

Jun 16, 2025

Random Matrix Theory for Deep Learning: Beyond Eigenvalues of Linear Models

Modern Machine Learning (ML) and Deep Neural Networks (DNNs) often operate on high-dimensional data and rely on overparameterized models, where classical low-dimensional intuitions break down. In particular, the proportional regime where the data dimension, sample size, and number of model parameters are all large and comparable, gives rise to novel and sometimes counterintuitive behaviors. This paper extends traditional Random Matrix Theory (RMT) beyond eigenvalue-based analysis of linear models to address the challenges posed by nonlinear ML models such as DNNs in this regime. We introduce the concept of High-dimensional Equivalent, which unifies and generalizes both Deterministic Equivalent and Linear Equivalent, to systematically address three technical challenges: high dimensionality, nonlinearity, and the need to analyze generic eigenspectral functionals. Leveraging this framework, we provide precise characterizations of the training and generalization performance of linear models, nonlinear shallow networks, and deep networks. Our results capture rich phenomena, including scaling laws, double descent, and nonlinear learning dynamics, offering a unified perspective on the theoretical understanding of deep learning in high dimensions.

Zhenyu Liao, Michael W. Mahoney

School of Electronic Information and Communications, Huazhong University of Science and Technology, Wuhan, China · ICSI, LBNL, and Department of Statistics, University of California, Berkeley, USA

Random Matrix Theory Neural Network Generalization Neural Network Training Dynamics Neural Scaling Laws High-Dimensional Asymptotics

Feb 17, 2022

Universality of empirical risk minimization

We study a general class of optimization problems with decision variable

\boldsymbolΘ \in \mathbb{R}^{p \times k}

and cost function which is the sum of

n

terms, each dependent on

\boldsymbolΘ

through the

k

-dimensional projection

\boldsymbolΘ^\top \boldsymbol{x}_i

, where

\boldsymbol{x}_i

,

i \leq n

are i.i.d. random vectors. This setting is general enough to include examples of current interest in statistical physics, high-dimensional statistics, and statistical learning theory. We consider the proportional asymptotics

n, p \to \infty

, with

n/p = Θ(1)

, and prove that, whenever there exists a minimizer satisfying a suitable generalization of a "delocalization" condition, the minimum value is universal. Namely, (for subgaussian

\boldsymbol{x}_i

) it depends on the distribution of

\boldsymbol{x}_i

only through its asymptotic mean and covariance. This delocalization condition is essentially necessary. Earlier universality results for such problems were limited to strongly convex loss functions. We derive applications of our theory to statistical learning and prove general universality results both for train and (under additional conditions) test error. In particular, we establish universality for vectors

\boldsymbol{x}_i

generated by random 1-layer neural networks (random features models) and first-order Taylor approximations of 2-layer networks (neural tangent models). Finally, we establish that the delocalization property holds for a class of statistical learning problems under a condition that is easy to verify.

Andrea Montanari, Basil Saeed

Department of Statistics and Department of Mathematics, Stanford University · Department of Electrical Engineering, Stanford University

Statistical Learning Theory Empirical Risk Minimization High-Dimensional Asymptotics