CS Paper Radar

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

Kaito Takanami, Takashi Takahashi, Yoshiyuki Kabashima

cs.LG cond-mat.dis-nnmath.STstat.ML ·submitted 2026-10-06 02:27 UTC · v1

Abstract

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.

Closest papers

Nearest neighbours by meaning across the whole index.

On the Optimality of Random Features under General Conditions: Misspecified Cases and Robust Learning

cs.LG stat.ML ·2026-10-13 ·Caixing Wang
similarity 0.61
Abstract · 61 pages, 10 figures, 2 tables

Random features provide a standard approach to scaling kernel methods to large datasets by approximating the kernel with a finite-dimensional feature map. Existing works of random feature methods primarily focus on well-specified models and light-tailed noise conditions, leaving a gap in understanding their performance under more general conditions, such as misspecified models and heavy-tailed noise. In this paper, we provide a comprehensive and improved analysis of kernel ridge regression with random features (KRR-RF) under general conditions. In the light-tailed noise setting, we improve upon the worst-case uniform bounds of the feature map used in the previous works and lead to the minimax optimal learning rates with $2r+γ>α_0$, where $(r,γ,α_0)$ denote the regularity of the target function, the effective dimension of the kernel, and the embedding index of the RKHS, respectively. In the heavy-tailed noise setting, we leverage a recently developed Hilbert-valued Fuk-Nagaev inequality and extend the same optimal results under finite weak moment conditions. The additional cost to achieve robustness is a mildly stronger explicit sample-size requirement than in the light-tailed case. For both settings, our results recover the conditions random features budgets (up to log factors) required in the previous works. In the most benign case when $α_0=γ$, KRR-RF are minimax optimal for all $r \in (0,1]$. To the best of our knowledge, this is the first work to establish optimal learning rates for KRR-RF under weak moment conditions in the misspecified setting. Numerical experiments and a real data analysis validate the derived learning rates and demonstrate their practical relevance in the presence of mis-specification and heavy-tailed noise.

0.24

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

cs.LG ·2026-10-15 ·Elvis Dohmatob
theory similarity 0.61
Abstract

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.

0.28

Can Domain Generalization be Guaranteed in Small-Sample Learning?

cs.LG ·2026-09-30 ·Hong Zheng
similarity 0.60
Abstract

The small-sample learning problem remains a fundamental challenge in machine learning because limited training data lead to unstable model estimation and generalization. Structural Risk Minimization (SRM) has long been regarded as a principled solution under the classical i.i.d. assumption. However, domain generalization (DG) violates this assumption, leaving the theoretical role of SRM in DG largely unexplored. To bridge this gap, we establish the first theoretical guarantees for SRM in DG under mild assumptions. Specifically, based on the concept of stability, we derive learning consistency and generalization error bounds and prove that these bounds become tight when the hypotheses satisfy the stability condition. Building upon this, under a specific hypothesis space assumption, we establish stability, learning, and generalization bounds for SRM. We further discuss the applicability of these bounds to deep learning. This work establishes theoretical foundations for SRM under distribution shifts and sheds light on the design of robust DG algorithms in small-sample scenarios.

0.20

Tail-Weight Control and Localized Generalization in Nearly Low-Rank Adversarial Classification

cs.LG cs.AI ·2026-09-20 ·Kunyu Wang, Dehan Wang, Wenjun Chen
theory similarity 0.59
Abstract · 11 pages

Empirical ramp fitting can assign weight to pure-noise features even when the population optimum ignores them. We quantify this gap for norm-constrained adversarial classification with Gaussian signal and noise. The variance cost relative to normalized signed mean separates into two factors: selecting observations inside the active margin window and the curvature induced by the norm constraint. Changing the tail variance leaves the activewindow probability unchanged but changes the second factor. With positive attack budget and a signal-only predictor of risk below one half, we prove a uniform quadratic tail-deletion bound, including at zero tail variance. Sufficiently accurate approximate global empirical minimizers admit exact fixeddimensional asymptotic covariances in the low-risk regime with isotropic principal covariance. For positive tail variance at most principal variance, the product exceeds one; an additional moment condition transfers it to expected excess ramp and robust classification risks. A wide window analysis characterizes when this ordering reverses. Controlled experiments test the decomposition, and a separate contamination study examines its scope outside the Gaussian training model.

0.23

CVaR anchor regression protects against rare shifts

cs.LG stat.ME ·2026-09-22 ·Malte Londschien
theory similarity 0.59
Abstract

We study prediction in new environments when the training data contains rare, large distribution shifts. Anchor regression penalizes the average of the squared mean residual across environments. It protects against shifts in an ellipsoid determined by the second moment of the training shifts. Covering rare shifts may therefore require a large penalty $γ\gg 1$, expanding the ellipsoid in every direction and reducing accuracy on common environments. We propose CVaR anchor regression, which replaces the average of the squared mean residuals with a tail average. We prove an exact worst-case risk guarantee under a linear structural model that allows for heteroscedastic noise. CVaR anchor regression protects against shifts in a union of ellipsoids determined by second moments of the shifts in the worst $α$-fraction of environments. For $α$ small enough, this is the scaled convex hull of the training shifts and their negatives. It therefore covers all training shifts when $γ\geq 1$. Unlike CVaR or GroupDRO applied directly to prediction risks, CVaR anchor regression does not give environments more weight solely because their noise levels are high. Examples show how the method can improve protection against rare shifts while retaining accuracy on common environments. We illustrate the method on the New York City taxi dataset.

0.25

Exact Global Minimax Risk near Nonidentification

cs.LG stat.MLmath.ST ·2026-10-23 ·Kaiyue Yang, Yunan Wu
similarity 0.58
Abstract

We study squared-error estimation when a nuisance parameter is unidentified on a submodel but affects a target that vanishes there. For models with higher-order profile expansions, we give sufficient conditions under which the largest critical-path minimax risk is the exact asymptotic minimax risk over the full parameter space. An efficient observable feature, negligible calibration error and stable recovery yield one estimator attaining the leading constant uniformly, with the profile coordinates unknown. The estimator uses calibration estimates, a local feature mean and an empirical recovery feature. The constant is expressed through a bounded-normal decision problem. We verify the conditions in two models. In centered Gaussian logistic errors-in-variables regression with one surrogate and two unknown variances, we determine the fifth-order global coefficient risk and its exact constant. A sparse extension separates variance-decomposition uncertainty from direction estimation and specifies when the scalar constant is preserved. In a degree-balanced replicated-network model, we determine the sixth-order global edge-contrast risk when block proportions are unknown. Triangles identify a parameter combination; a bowtie supplies the additional information needed for the contrast.

0.29

Feature Normalization under Finite Training Budgets

cs.LG stat.MLmath.OC ·2026-10-12 ·Johan Larsson
similarity 0.58
Abstract · 45 pages

Standardizing a rare feature can help stochastic gradient descent learn its effect within a finite budget, but it also changes the noise cost of learning. We characterize the lowest rare-subgroup risks attainable by standardized and unscaled training when each chooses a nonnegative constant learning rate and a deterministic stopping time under the same observation cap. For two independent binary features, we derive both optimized risks as prevalence vanishes while the expected number of rare observations remains finite. Uniform control over rates and stopping times reduces each limiting oracle to a scalar minimization. With positive noise, the preferred scaling changes exactly once as we move signal to the rare feature while the limiting risk at initialization stays fixed and positive. The formulas also explain how noise and budget affect the comparison. Separate finite-prevalence bounds favor standardization on a rare-dominant signal family and unscaled training on a common-dominant family. The results concern final iterates with population preprocessing and fresh observations. Exact-moment searches assess the approximation at finite prevalence. In a controlled study, both orderings persist under observation reuse, estimated preprocessing, and intercept fitting when tuning choices are fixed before evaluation. Selecting a predictor after observing training can reverse an ordering, even when selection uses exact population risk.

0.34

The Optimal Sample Complexity of Pointwise Replicable Agnostic Learning

cs.LG ·2026-10-18 ·Guangjian Zhang
theory similarity 0.58
Abstract · 92 pages

Pointwise replicability asks that two independently trained predictors, using the same random seed, agree at each fixed query with high probability. We determine its optimal agnostic sample complexity on finite and countable domains. For every nonempty binary class of finite VC dimension $d\ge1$, the required number of independent examples is $Θ\!\left(\frac{d}{ρ^2α^2}+\frac{\log(1/β)}{α^2}\right)$, uniformly over independent accuracy, failure, and disagreement parameters $α,β,ρ\in(0,1/10)$. The learner returns one binary function, may be improper, and uses unrestricted shared randomness. Its sample budget is fixed before observing data, and the replicability guarantee includes queries of zero marginal mass. The main construction combines an ensemble of empirical-risk minimizers with a smooth, signal-dependent risk decomposition. A single shared phase selects the final binary predictor. Record times certify its weak-signal risk, while a uniform bound protects the strong-signal risk at that same selected time. A phase-comparison theorem controls the actual shared-seed execution under simultaneous changes in the marginals and risk coefficients. A rare repair step then makes the confidence cost additive. Together with matching lower bounds, this removes the remaining logarithmic overhead and parameter restrictions in the general countable-domain sample-complexity problem. This extended version also retains the earlier explicit constructions and their proofs, including proper learning for VC-one classes, the full finite-atom class, a faster realizable bound, and counterexamples that separate restrictions of particular algorithms from restrictions of the learning problem.

0.30