Generalisation error in learning with random features and the hidden manifold model

Federica Gerace; Bruno Loureiro; Florent Krzakala; Marc Mézard; Lenka Zdeborová

Source-linked AI summary

Generalisation error in learning with random features and the hidden manifold model

Federica Gerace, Bruno Loureiro, Florent Krzakala, Marc Mézard, Lenka Zdeborová

arXiv:2002.09339v2Feb 21, 2020math.STcs.LGmath.PRstat.ML

TL;DR

The paper asks how regression and classification generalise on high-dimensional synthetic data spanning hidden manifolds, random features, and lazy-training-related models. It uses the replica method to derive a closed-form asymptotic generalisation error across parametrisation regimes and broad losses, finding analytic double descent for logistic regression and better performance from orthogonal projections. The results also characterise hidden-manifold phase behaviour and motivate extensions to more complex tasks.

Problem
Existing generalisation analyses are limited by worst-case bounds, i.i.d. inputs, or networks with few hidden units, motivating broader high-dimensional learning curves for structured data.
Method
The paper applies the replica method to derive a closed-form high-dimensional generalisation error for synthetic models with generic feature matrices and broad loss functions.
Results
Orthogonal random-feature embeddings outperform Gaussian random projections, while logistic regression shows double descent with its peak at the linear-separability threshold.
Takeaways & Limitations
The formalism provides a unified analytical treatment of hidden-manifold, random-feature, and lazy-training-related settings and a basis for extensions to more complex tasks.
Takeaways & Limitations
The replica-based results lack a rigorous proof for the present model, and the hidden-manifold task retains an asymptotic generalisation error of 0.0325 as α → ∞.

Abstract

from arXiv · show

We study generalised linear regression and classification for a synthetically generated dataset encompassing different problems of interest, such as learning with random features, neural networks in the lazy training regime, and the hidden manifold model. We consider the high-dimensional regime and using the replica method from statistical physics, we provide a closed-form expression for the asymptotic generalisation performance in these problems, valid in both the under- and over-parametrised regimes and for a broad choice of generalised linear model loss functions. In particular, we show how to obtain analytically the so-called double descent behaviour for logistic regression with a peak at the interpolation threshold, we illustrate the superiority of orthogonal against random Gaussian projections in learning with random features, and discuss the role played by correlations in the data generated by the hidden manifold model. Beyond the interest in these particular problems, the theoretical formalism introduced in this manuscript provides a path to further extensions to more complex tasks.

1 Introduction

The paper develops a high-dimensional theory of generalisation for synthetic data models covering hidden manifolds, random features, and lazy-training connections. Using the replica method, it derives a generic closed-form error formula and applies it to double descent, projection design, and hidden-manifold phase behaviour.

Motivation: Existing statistical-physics analyses largely assume i.i.d. inputs or networks with few hidden units, limiting relevance to manifold-structured data and wider networks.
Model scope: The framework studies supervised regression and classification on synthetic high-dimensional data generated through latent variables, nonlinear feature maps, and generalized linear rules.
Method: The replica method yields a closed-form generalisation error in the high-dimensional limit for broad loss functions and generic feature matrices, including deterministic features.The formula applies when sample and ambient or latent dimensions grow with ratios of order one.
Method: The analysis extends Gaussian-covariate equivalence to the considered data model, while numerical comparisons support its accuracy despite the absence of a rigorous proof.
Applications: Nonregularized logistic regression exhibits double descent, with its worst-generalisation peak at the linear-separability threshold rather than necessarily at p = n.
Applications: Orthogonal feature embeddings outperform Gaussian random projections and reach the kernel limit with fewer projections.
Applications: The framework computes the hidden-manifold generalisation phase diagram and examines dependence on parameters including the ambient-to-latent dimension ratio.

2 Main analytical results

The paper derives a scalar optimisation and closed-form generalisation-error formula through the replica method, with a Gaussian-equivalence interpretation and numerical validation. The result applies in the high-dimensional limit to generic feature matrices satisfying balance and reproduces a known rigorous special case.

Analytical formula: In the limit p, d, n →∞ with α = n/p and γ = d/p fixed, the generalisation error is given by an integral evaluated at saddle-point solutions.The formulation assumes a feature matrix with well-behaved spectral density and a nonlinearity whose centered-Gaussian integral is zero.
Replica method: The replica computation reduces the high-dimensional optimisation to a simpler scalar optimisation for directly computing generalisation error.The asymptotic error depends on the learned weights through scalar parameters, whose fixed-point or saddle-point equations determine the result.
Analytical formula: The closed-form expression is valid for generic feature-matrix sequences satisfying balance conditions in the high-dimensional regime.The balance condition is also assumed to hold with probability one under the replicated Gibbs measure used in the derivation.
Gaussian equivalence: The Gaussian equivalence theorem maps the asymptotic generalisation error to that of a linear model, extending beyond the generalised linear task studied here.For square loss with Gaussian random matrices, this mapping coincides with a result proved using random matrix theory.
Validation and scope: The formula agrees with simulations and reproduces rigorous results for Gaussian projection matrices with ridge regression, but broader rigorous proof remains open.The reported agreement remains accurate even for relatively small system sizes.

3 Applications of the generalisation formula

The applications demonstrate double descent in logistic regression, advantages of orthogonal random features, and strong over-parameterised generalisation when data lie on a low-dimensional hidden manifold.

3.1 Double descent for classification with logistic loss: Double descent in logistic regression peaks when the data become linearly separable, rather than at p = n as in square-loss regression.The separability threshold depends on n/d and shifts as data correlations change.
3.1 Double descent for classification with logistic loss: At optimal regularisation in the kernel limit, generalisation error approaches 0.17 for square loss and 0.16 for logistic loss.Logistic loss also achieves better error than square loss for most finite projection ratios, except near its interpolation peak.
3.2 Random features: Gaussian versus orthogonal: Orthogonal random projections outperform Gaussian projections and reach the kernel limit with fewer projections.The asymptotic prediction is shared by properly normalised orthogonal and deterministic Fourier or Hadamard matrices with the same spectral density.
3.2 Random features: Gaussian versus orthogonal: Orthogonal features require fewer projections for linear separability, shifting the logistic phase-transition curve left relative to Gaussian features.Their overall behaviour remains qualitatively similar to that of random i.i.d. projections.
3.2 Random features: Gaussian versus orthogonal: Figure 5 compares generalisation error versus p/n for ridge regression and logistic classification using Gaussian and orthogonal projection matrices.The experiments include fixed and optimal regularisation, with theory compared against gradient-descent simulations.
3.3 The hidden manifold model phase diagram: Figure 6 varies α = n/p at fixed d/p = 0.1 for square-loss classification, showing how regularisation changes the interpolation peak.At very small regularisation, the peak occurs at α = 1, with the over-parametrised regime on the left.
3.3 The hidden manifold model phase diagram: Figure 7 maps square-loss classification error over n/p and d/p, finding low error even when p > n if the latent dimension is sufficiently small.The paper states that good generalisation is achieved in the over-parametrised regime when roughly d ≲ n.
3.3 The hidden manifold model phase diagram: In the hidden-manifold setting, increasing d/p worsens error, while the asymptotic error approaches 0.0325 in the reported limit.The paper identifies adding hidden variables to the neural network as a future direction for improving performance.

A.1 The dataset

The dataset unifies hidden-manifold and random-features perspectives through latent Gaussian inputs, a generic feature matrix, nonlinear observations, and generalised-linear labels.

A.1 The dataset: The dataset consists of n examples with p-dimensional observations and real-valued labels sampled from a generalised linear model.The output channel is defined through a generalised linear rule with noise and data-dependent responses.
A.1 The dataset: The regression and classification examples use noisy linear and deterministic sign output channels, respectively.For regression, ξµ ∼ N(0, 1) and Δ > 0.
A.1 The dataset: Under the hidden-manifold view, p-dimensional observations are generated from a latent d < p subspace hidden by a component-wise scalar nonlinearity.The labels depend on the manifold coordinates.
A.1 The dataset: Under the random-features view, d-dimensional data are projected into a higher-dimensional space, transformed nonlinearly, and related to kernel ridge regression.With infinitely many features at fixed d/p, ridge regression becomes equivalent to kernel ridge regression with a limiting kernel determined by F and σ.

A.2 The task

The task learns a generalised-linear predictor with ridge regularisation and evaluates its expected error on an independent sample in a high-dimensional limit.

A.2 The task: The paper learns the latent-data rule using a generalised linear model with weights w ∈ R^p.The weights minimise a loss function augmented by a ridge regularisation term with λ > 0.
A.2 The task: The framework allows general loss, prediction, and target functions, including non-convex losses.Applications focus on identity mappings for regression and sign mappings for classification, using square and logistic losses.
A.2 The task: For the strictly convex losses considered, ridge-regularised optimisation has a unique solution.This applies to the square and logistic loss settings used in the applications.
A.2 The task: Generalisation error is evaluated on an independently drawn test pair using the model prediction ˆf(xnew · ˆw).For classification, the chosen error counts misclassification and equals one minus classification accuracy.
A.2 The task: The analysis takes p, d, and n to infinity while keeping α = n/p and γ = d/p fixed.This is the high-dimensional, or thermodynamic, limit used throughout the manuscript.

B Gaussian equivalence theorem

The replicated Gaussian equivalence (rGE) is introduced as the central result used in the replica calculation of generalisation error.

The rGE strengthens the Gaussian equivalence theorem for application within the replica calculation.It is required because the calculation averages over multiple samples, or replicas, from a Gibbs distribution.

B.1 Gaussian equivalence theorem

The Gaussian equivalence theorem characterises the joint statistics of transformed projections and latent Gaussian variables in a high-dimensional limit under balance conditions.

The theorem applies as d,p →∞ with fixed p/d and fixed r, assuming σ is odd and specified balance conditions hold.These asymptotic and balance assumptions define the regime in which the equivalence is asserted.
The result concerns any distinct coordinate indices and arbitrary choices of the replica indices a_1,…,a_k within the stated ranges.The theorem is formulated for finite collections of variables indexed by distinct coordinates and replica labels.
Under these conditions, {λ_a, ν} become jointly normal with zero mean and specified covariances.The covariance structure is the theorem’s central conclusion for the projected variables.
The replicated version requires the balance condition to hold for every sample drawn from the Gibbs distribution μ_β.This extends the fixed-family theorem to the replica setting used in the calculation.

C Replica analysis

The replica analysis reformulates the optimisation problem through a Gibbs measure and derives the asymptotic generalisation error by evaluating its free energy in the high-dimensional limit.

The derivation starts from a Gibbs formulation of the optimisation problem and applies replica analysis from statistical physics.The Gibbs measure concentrates on the optimisation solution as β →∞.
In the limit n,p,d →∞ with fixed d/p and n/p, the free energy density is computed using the replica method.Its β →∞ limit yields optimal overlaps that characterise the generalisation error.
A large-deviation assumption and self-averageness permit concentration of the free energy around a typical thermodynamic value.The free-energy distribution is assumed to satisfy a large deviation principle with maximum at f_β.
The calculation uses replicated Gaussian equivalence to replace the relevant variables with asymptotically Gaussian ones and reduce dependence to overlap parameters.After averaging over inputs, the replicated partition-function integrals couple only through these overlaps.
The analysis imposes a replica-symmetric Ansatz, justified for convex losses with λ > 0 but not guaranteed for non-convex losses.Non-convex losses may admit replica-symmetry-breaking solutions requiring further analysis of the free-energy landscape.
The resulting free energy depends on the projection matrix through spectral properties, including its limiting spectral measure and Stieltjes transform.The derivation then specialises the framework to Gaussian projections and their Marchenko–Pastur law.

C.4 Gaussian equivalent model

After applying Gaussian equivalence, the replicated partition function matches that of a dual dataset with Gaussian covariates and the same labels.

Averaging the original dataset after Gaussian equivalence produces the replicated partition function of an equivalent Gaussian-covariate dataset.The labels remain distributed according to the same Py distribution.
Matching the parameters κ0 and κ1 makes the transformed variables jointly Gaussian with the same correlation matrix Σ.This establishes the equivalence between the two replicated formulations.
The two models therefore have equivalent asymptotic generalisation and test errors.The equivalence transfers the asymptotic error analysis from the hidden data model to the Gaussian model.

D Saddle-point equations and the generalisation error

The replica analysis reduces the original p-dimensional optimisation to a one-dimensional problem over overlap parameters, which determine both generalisation error and training loss.

The p-dimensional minimisation is replaced by a one-dimensional minimisation over overlap parameters and their conjugates.
At β →∞, the replica solution corresponds to the original optimisation solution.
Both generalisation error and training loss can be expressed entirely through the optimal overlap parameters.

D.1 Generalisation error as a function of the overlaps

The section derives generalisation error for an independently drawn sample and expresses it through the optimal overlap parameters, with classification depending on the angle between the learned feature representation and the teacher.

Generalisation error is defined on a new sample independently drawn from the same data distribution.
The replica formalism rewrites the generalisation error in terms of the optimal overlap parameters.
For linear regression labels, the section gives a specialised expression for the generalisation error.
For the corresponding classification task, generalisation depends only on the angle between F ˆ w and θ0.

D.2 Training loss

The appendix connects training-loss asymptotics to the replica free energy, derives iteratively solvable saddle-point equations, and describes analytical examples and numerical validation for the generated-data model.

D.2 Training loss: Training loss is related to the free energy density and can be written solely in terms of overlap parameters.The derivation uses derivatives of the free energy with respect to β and separates regulariser and loss contributions.
D.2 Training loss: For strictly convex losses, the β →∞ extremisation problem has a unique solution characterised by self-consistent saddle-point equations.
D.2 Training loss: The saddle-point equations can be iterated using auxiliary functions determined by the spectral density, label rule, and loss function.For convex losses at β →∞, the converged fixed point gives the overlaps of the estimator solving the original optimisation problem.
D.2 Training loss: The β →∞ analysis uses an ansatz for overlap-parameter scaling, motivated by estimator variance vanishing as a power law and Gibbs-measure concentration.
Examples: The appendix treats ridge regression with linear labels and classification with square loss and ridge regularisation as analytically tractable examples.The ridge-regression example corresponds to the setting studied in [32].
Numerical procedure: Numerical simulations generate data from the specified random-feature model, fit square- or logistic-loss estimators, and evaluate generalisation on independent samples.The procedure averages results over independent draws; most main-text examples used nseeds = 30.
Numerical procedure: The data-generation pipeline draws F and θ0, constructs X and y, computes the estimator, generates new data, and averages the resulting generalisation error across seeds.The examples use Gaussian teacher vectors, linear regression labels, sign classification labels, and either Gaussian or random orthogonal projections.