Learning Curves and Benign Overfitting of Spectral Algorithms in Large Dimensions

• URL: http://arxiv.org/abs/2604.23212v1
• Date: Sat, 25 Apr 2026 08:38:07 GMT
• Title: Learning Curves and Benign Overfitting of Spectral Algorithms in Large Dimensions
• Abstract summary: We study the learning curve and benign overfitting of spectral algorithms in a large-dimensional setting.<n>Our results reveal that the learning curve is not simply U-shaped but instead consists of three distinct regimes.
• Score: 7.479111923791646
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Existing large-dimensional theory for spectral algorithms resolves either the optimally tuned point or the interpolation limit, but leaves the under-regularized regime unexplored. We study the learning curve and benign overfitting of spectral algorithms in the large-dimensional setting where the sample size and dimension are of comparable order, i.e., $n \asymp d^γ$ for some $γ>0$. We first consider inner-product kernels on the sphere $\mathbb{S}^{d-1}$ and establish a sharp asymptotic characterization of the excess risk across the full regularization path under various source conditions $s \geq 0$, where $s$ measures the relative smoothness of the regression function. Our results reveal that the learning curve is not simply U-shaped but instead consists of three distinct regimes: over-regularized, under-regularized, and interpolation regimes. This characterization allows us to fully capture the benign overfitting phenomenon, demonstrating that benign overfitting arises consistently across both the under-regularized and interpolation regimes whenever $s$ is positive but no larger than a critical threshold. We further show that, in the sufficiently regularized regime, the kernel learning curve is recovered by an associated sequence model. Finally, we extend the learning-curve analysis to large-dimensional KRR for a class of kernels on general domains in $\mathbb{R}^d$ whose low-degree eigenspaces satisfy spectral-scaling and hyper-contractivity conditions.

Related papers

• Multi-kernel spectral clustering: Entrywise eigenvector perturbation bounds and exact recovery [5.506184984859199]
  Kernel spectral clustering with a single bandwidth can be inadequate for data exhibiting multiple characteristic pairwise-distance scales.<n>We address this issue through a multi- kernel formulation that aggregates kernels with different bandwidths.<n>We develop a rigorous theoretical analysis of the resulting method under a general high-dimensional, multi-scale mixture model.
  arXiv  Detail & Related papers  (2026-08-09T13:34:27Z)
• Stochastic global optimization of continuous functions via random walks on Grassmannians [19.659410865201384]
  We introduce a global optimization method based on random walks on Grassmannian manifold.<n>The method repeatedly samples random $k$-dimensional linear subspaces.<n>We identify a gap parameter that controls the rate at which the iterates approach the global minimum value.
  arXiv  Detail & Related papers  (2026-05-13T22:06:50Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• Low-degree Lower bounds for clustering in moderate dimension [53.03724383992195]
  We study the fundamental problem of clustering $n$ points into $K$ groups drawn from a mixture of isotropic Gaussians in $mathbbRd$.<n>We show that while the difficulty of clustering for $n leq dK$ is driven by dimension reduction and spectral methods, the moderate-dimensional regime involves more delicate phenomena leading to a "non-optimal rate"<n>We provide a novel non-spectral algorithm matching this rate, shedding new light on the computational limits of the clustering problem in moderate dimension.
  arXiv  Detail & Related papers  (2026-02-26T14:03:55Z)
• Inexact subgradient methods for semialgebraic functions [18.293072574300798]
  Motivated by the extensive application of approximate gradients in machine learning, we investigate subexact additive methods subject to persistent errors.<n>Our analysis addresses both vanishing and constant step-size regimes.
  arXiv  Detail & Related papers  (2024-04-30T12:47:42Z)
• Generalization error of spectral algorithms [17.93452027304691]
  We consider the training of kernels with a family of $textitspectral algorithms$ specified by profile $h(lambda)$. We derive the generalization error as a functional of learning profile $h(lambda)$ for two data models.
  arXiv  Detail & Related papers  (2024-03-18T11:52:33Z)
• Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation [52.73824786627612]
  This paper establishes new convergence results for textitgeodesic strongly monotone games.<n>Our key result shows that RGD attains last-iterate linear convergence in a textitgeometry-agnostic fashion.<n>Overall, this paper presents the first geometry-agnostic last-iterate convergence analysis for games beyond the Euclidean settings.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• Generalization in Supervised Learning Through Riemannian Contraction [4.3604518673788135]
  In a supervised learning setting, we show that if an metric 0 is contracting in someian rate $lambda, it is uniformly uniformly rate with $math. The results hold for gradient and deterministic loss surfaces, in both continuous and stable $-time. They can be shown to be optimal in certain linear settings, such as over Descent$ convex or strongly convex loss surfaces.
  arXiv  Detail & Related papers  (2022-01-17T23:08:47Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  inductive biases are central in preventing overfitting empirically. This work considers this issue in arguably the most basic setting: constant-stepsize SGD for linear regression. We reflect on a number of notable differences between the algorithmic regularization afforded by (unregularized) SGD in comparison to ordinary least squares.
  arXiv  Detail & Related papers  (2021-03-23T17:15:53Z)
• The Heavy-Tail Phenomenon in SGD [7.366405857677226]
  We show that depending on the structure of the Hessian of the loss at the minimum, the SGD iterates will converge to a emphheavy-tailed stationary distribution. We translate our results into insights about the behavior of SGD in deep learning.
  arXiv  Detail & Related papers  (2020-06-08T16:43:56Z)
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
  We study the inequality and non-asymptotic properties of approximation procedures with Polyak-Ruppert averaging. We prove a central limit theorem (CLT) for the averaged iterates with fixed step size and number of iterations going to infinity.
  arXiv  Detail & Related papers  (2020-04-09T17:54:18Z)
• Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
  We develop a convex analytic approach to analyze finite width two-layer ReLU networks. We show that an optimal solution to the regularized training problem can be characterized as extreme points of a convex set. In higher dimensions, we show that the training problem can be cast as a finite dimensional convex problem with infinitely many constraints.
  arXiv  Detail & Related papers  (2020-02-25T23:05:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.