Empirical Risk Minimization

Also known as ERM

Ask about this topic

Overview

Empirical risk minimization chooses a model or decision rule to minimize average loss on a training sample, providing a foundation for regression, classification, and many neural-network objectives. Statistical analyses use localized Rademacher complexity, concentration and small-ball methods, and high-dimensional tools such as Gaussian comparison and approximate message passing to bound test error and study when structure, weighting, or constraints help. Optimization work examines gradient methods, regularization, distributed primal-dual algorithms, and privacy-preserving variants, while extensions address biased or dependent data, distribution shift, heavy tails, and selective labels. A central tension is that low empirical risk or faster fitting need not ensure reliable test performance: guarantees depend on model complexity and data conditions, while computational, privacy, and robustness constraints introduce further tradeoffs.

Latest papers

CardsList

45 papers5 papers in the last four weeks, down 29% on the four weeks before. 0.0% of all new papers.

Nov 1, 2026

Benign population landscapes do not transfer to empirical risk minimization in nonsmooth optimization

Benign landscapes provide a geometric explanation for the success of iterative methods on nonconvex problems arising in data science. The landscape is benign if every local minimizer is global and every other critical point is a strict saddle. For methods that avoid strict saddles, convergence to a critical point therefore implies convergence to a global minimizer. For smooth stochastic optimization, a common strategy for establishing such landscapes proceeds in two steps: (i)(i) establish benign geometry for the population objective---which is often easier to analyze---and (ii)(ii) transfer this geometry to the empirical objective using concentration of gradients and Hessians. Recent work has extended saddle-point avoidance guarantees to weakly convex nonsmooth optimization through the notion of active strict saddles. We show, however, that benign population geometry need not transfer to empirical objectives in this setting. Specifically, for robust phase retrieval with Gaussian measurements---a well-studied and highly structured problem---the population objective is benign. Nevertheless, the empirical objective has sharp spurious local minima with probability bounded away from zero as the sample size tends to infinity. This asymptotic probability lower bound is independent of the dimension.

Penghao Wang, Mateo Díaz, Liwei Jiang

Edwardson School of Industrial Engineering, Purdue University. · Department of Statistics & Data Science Institute, University of Chicago.

Nonconvex OptimizationEmpirical Risk Minimization
AskPDF
Oct 15, 2026

Two Sample Sizes in Test-Time LLM Ensembling: Buffered ERM and Minimax Theory

Test-time scaling can improve the performance of large language models by generating multiple answers to a question and aggregating them. Weighted ensembles extend this idea by drawing answers from several models, with the weights determining how often each model is used. Learning these weights from a training dataset involves two sample sizes: QQ labeled questions and NN generations per model and question. We study their interplay through the clean risk, the population error of the ensemble's infinite-generation voting rule. Under a margin condition with exponent ββ, we show that empirical risk minimization (ERM) with a calibrated margin buffer achieves excess risk of order Q−1/2+N−β/2Q^{-1/2}+N^{-β/2}, up to logarithmic factors, for fixed numbers of models and candidate answers. To investigate the optimality of this dependence on QQ and NN, we analyze a simplified submodel with two models and two possible answers per question. We characterize its minimax excess risk up to constants by a Hellinger modulus for a binomial-mixture experiment. Polynomial approximation and spectral analysis reveal three regimes. When questions are relatively scarce, the Q−1/2Q^{-1/2} term governs learning and the general buffered ERM is optimal. In an intermediate regime, pooling generation counts across questions improves upon estimating each answer distribution separately, with only logarithmic gains from additional questions. With sufficiently many questions, the minimax excess risk reaches an N−βN^{-β} identification floor that persists even with infinitely many questions. The submodel's lower bounds also apply to general ensembles, matching the buffered-ERM upper bound up to logarithmic factors when questions are scarce and in parts of the intermediate regime. Questions remain about the transitions between regimes and the construction of matching pooled estimators for general ensembles.

Zhi Zhang, Arash A. Amini

Department of Statistics and Data Science, UCLA

Language Model EnsemblesTest-Time ScalingStatistical Learning TheoryEmpirical Risk Minimization
AskPDF
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 AsymptoticsDataset PruningStatistical Learning TheoryEmpirical Risk MinimizationHard Negative Mining
AskPDF
Oct 13, 2026

Learning a Group Element from Its Action: Galois Correspondences, Optimal ERM, and an Abel-Ruffini Threshold for the Natarajan Dimension

We study learning an unknown element gg of a group acting with finite orbits on a countable set, from examples (x,gx)(x,gx). After a sample on AA, the consistent hypotheses are the restrictions of a coset of the pointwise stabilizer of AA, and the sample forces exactly the labels of points this stabilizer fixes; for a Galois group, they form the field generated by the data. Through this correspondence, multiclass dimensions become group invariants: the DS and graph dimensions equal the height, the Littlestone dimension the longest irredundant sequence length, and the teaching dimension the minimal base size. Among deterministic learners, symmetry makes empirical risk minimization optimal: on nondegenerate classes every consistent learner, whatever its tie-breaking, attains the optimal realizable sample complexity up to constant factors, and every consistent online learner the optimal mistake bound. Agnostically, every ERM's sample complexity exceeds the known lower bound by at most the DS-to-Natarajan ratio, up to constants. For finite Galois extensions of countable fields, the Natarajan dimension equals a group invariant, the coset-cube number, which is at least the number of complemented factors of any chief series of any subgroup. Hence the dimensions coincide for every solvable Galois group, while for the groups A5A_5 and S5S_5 of the quintic they are 2<32<3 and 3<43<4, and A5A_5 is the smallest group with a gap. For the Galois group SnS_n of the general equation of degree nn, they coincide exactly when n≤4n\le 4, i.e., in characteristic zero, exactly when the equation is solvable by radicals; the implication is one-way, as the simple group PSL(2,8)\mathrm{PSL}(2,8) has no gap. For linear, orthogonal and unitary maps of Rd\mathbb R^d or Cd\mathbb C^d both dimensions equal dd, and a two-fibered pseudo-cube is a disjoint union of Natarajan cubes exactly when its monodromy group is abelian.

Xiaoyu Li

University of New South Wales

Sample ComplexityMulticlass ClassificationEmpirical Risk Minimization
AskPDF
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 LearningHigh-Dimensional AsymptoticsLinear RegressionHeavy-Tailed DistributionsEmpirical Risk Minimization
AskPDF
Sep 24, 2026

Entropy Regularization: A Free Correction to Cross-Entropy for Verified Demonstrations

Large language models are often post-trained on expert demonstrations using cross-entropy (CE), even when the downstream objective is not to imitate the demonstrated solution but to produce any output accepted by a verifier. This mismatch is seen in verifiable domains with multiple correct solutions, such as mathematical reasoning and code generation, where training data may contain only one expert solution per problem. We show that minimizing cross-entropy can be misaligned with minimizing verifier risk; two policies can assign identical likelihood to the observed demonstrations while placing different probability mass on incorrect outputs. This is formalized through a learning-theoretic counterexample in which CE minimization selects a suboptimal policy. We identify that controlling the support of the learned policy can solve this problem by preventing probability mass from spreading to unsupported outputs. Since support size is non-differentiable and computationally intractable, we propose entropy-regularized cross-entropy (ER-CE), using token-level Shannon entropy as a tractable proxy. Finally, across mathematical reasoning and code-generation benchmarks, we find that entropy-regularized training consistently improves verifier accuracy over standard cross-entropy. Our results identify a simple failure mode of imitation-based post-training in verifiable tasks and provide a practical objective that is better aligned with producing correct outputs.

Mihir Dhanakshirur, Adam Ousherovitch, Ambuj Tewari

Department of Statistics, University of Michigan

Entropy RegularizationLLM ReasoningEmpirical Risk Minimization
AskPDF
Sep 20, 2026

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

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.

Kunyu Wang, Dehan Wang, Wenjun Chen

The Chinese University of Hong Kong · Columbia University

Adversarial RobustnessRobust Loss FunctionsEmpirical Risk Minimization
AskPDF
Sep 9, 2026

Weighted Empirical Risk Minimization for Machine Learning under Long-Range Dependence: Exact Pathwise Rates and Learning-Error Geometry

We develop an exact almost-sure learning theory for smooth parametric models trained by regularly weighted empirical risk minimization on long-range dependent data. The training observations are generated from a fixed finite window of a stationary Gaussian sequence, and the sample weights are regularly varying. If the loss gradient at the population minimizer has Wiener-chaos rank mm and a nonzero low-frequency coefficient, then, in the long-memory interior regime, the finite-lag score reduces on the iterated-logarithm scale to a single weighted Hermite chaos. This yields an almost-sure Bahadur representation, an exact limsup law for the learned parameter, and, for m≥2m\ge2, the functional cluster set of the complete learning trajectory. The polynomial learning exponent is determined by the memory parameter and the chaos rank and is invariant under the admissible power weighting, whereas the sharp pathwise constant and cluster geometry depend on the weights. In the rank-one case, global optimization over the admissible power exponents shows that every optimizer is positive. Time-series prediction and classification examples illustrate the results.

Elina Moldavskaya

Technion–Israel Institute of Technology, Israel

Statistical Learning TheoryEmpirical Risk Minimization
AskPDF
Sep 9, 2026

An Exponential Deterministic--Randomized Gap in ERM-Oracle Complexity for Thresholds on an Unknown Order

Attias, Hanneke and Ramaswami (NeurIPS 2025) asked whether randomization provably reduces the oracle calls needed for online learning when the class is accessible only through an oracle. We study the instance they singled out: transductive online learning of thresholds on an unknown total order of T instances, with a consistency-type ERM oracle that returns a full concept consistent with a queried labeled set (or reports non-realizability). Our main result is a separation for a fixed natural oracle. When the oracle is the minimal-prefix rule (or the maximal-prefix rule), every deterministic learner makes M mistakes and Q calls with M+Q≥T−εM+Q\ge T-\varepsilon on some instance (ε∈{0,1}\varepsilon\in\{0,1\}, according to whether the empty prefix is a concept), and the constant is exact; hence O(log⁡T)O(\log T) mistakes cost T−ε−O(log⁡T)T-\varepsilon-O(\log T) calls, whereas that paper's randomized learner achieves O(log⁡T)O(\log T) expected calls and mistakes under the same rule. The randomized order is optimal: on an explicit hard distribution under the minimal-prefix rule, every learner has expected mistakes at least ((T+1−ε) 128−E[Q]−1)/2((T+1-\varepsilon)\,128^{-\mathbb{E}[Q]}-1)/2, so Ω(log⁡T)Ω(\log T) expected calls are necessary for polylogarithmic mistakes. The separation is governed by the oracle's selection rule, not by the class alone: for a legal feasible-median ERM rule a deterministic learner achieves O(log⁡T)O(\log T) calls and mistakes, while a global-median rule again forces linear total cost. The same linear bound holds when the oracle's answers are chosen adversarially and then frozen into a memoryless oracle. We add partial tradeoff results for fixed query budgets (the middle regime is open) and an interface contrast: with only a weak consistency oracle, returning a realizability bit, both deterministic and randomized learners need Θ(T)Θ(T) calls.

Xuan Li

University of New South Wales, Sydney, Australia

Query ComplexityOracle ComplexityOnline LearningEmpirical Risk Minimization
AskPDF
Sep 8, 2026

Weighted Data Selection: Sharp Upper-Half and Five-Dimensional Laws

How much risk does a small reweighted training support retain? For finite weighted least squares with the minimum-norm learner, we prove the exact law Γd(n)=3−n/dΓ_d(n)=3-n/d throughout ⌈3d/2⌉≤n≤2d−1\lceil3d/2\rceil\leq n\leq2d-1. The guarantee covers every observed feature rank and uses selections that preserve the full feature span. Balanced simplex anchors reduce dimension; positive-weight lifting and independent-line compression close the risk bound. Shifted coordinate pairs attain the matching lower bound. The complete dataset-level upper bound and sharpness construction are verified in Lean 4. At the smaller budget (d,n)=(5,6)(d,n)=(5,6), we also prove Γ5(6)=11/5Γ_5(6)=11/5, matching the simplex-block prediction from 5=3+25=3+2 over arbitrary interacting configurations. Circuit covers, comparison second moments, and circuit-plane probabilities give the sharp excess 6/56/5, while polar-face geometry resolves shared rank-three circuits. The general simplex-block frontier connects these laws within the intermediate-budget selection problem.

Zhongxuan Liu, Hongzhi Wang

Faculty of Computing, Harbin Institute of Technology

Data SelectionTraining Data SelectionLinear RegressionEmpirical Risk Minimization
AskPDF
Sep 8, 2026

Fitting and Learning Basis-Restricted Propositional Formulas

For a finite set OO of Boolean functions, we consider the class of propositional formulas built using the functions in OO as connectives. We determine, for each possible choice of OO, the complexity of various fitting and learning problems. These include: finding a formula that fits a given labeled sample, finding a small one (an Occam algorithm), minimizing the number of misclassified examples when the sample is not realizable (empirical risk minimization), and several forms of PAC learning. Our results apply both to formulas (represented as trees) and to circuits. We also briefly discuss the status of the same questions for other kinds of propositional fragments.

Balder ten Cate

Boolean Function LearningEmpirical Risk Minimization
AskPDF
Sep 8, 2026

GPU-Enabled Large-Scale Optimization Using Randomized Linear Algebra

This paper introduces rlaopt, a PyTorch-based package for large-scale optimization and scientific computing using randomized numerical linear algebra (RandNLA). Despite substantial progress in RandNLA-based algorithms, few implementations combine GPU acceleration with a simple interface for specifying optimization problems. rlaopt addresses this gap by providing GPU-enabled solvers for positive-definite linear systems and convex empirical risk minimization with constraints and regularizers. These solvers use RandNLA to accelerate conjugate gradient (NystromPCG), operator splitting (NysADMM), and stochastic gradient methods (SAPPHIRE). Moreover, rlaopt includes a modeling language that lets users specify problems using natural mathematical syntax. rlaopt automatically checks compatibility with the selected solver and performs the required problem decomposition. The solvers also support differentiation through their iterations, enabling applications such as hyperparameter tuning. Experiments on ridge regression, bounded multinomial logistic regression, and bounded elastic net identify when randomized preconditioning improves performance and demonstrate substantial speedups from GPU execution. The package is open-source under an Apache license, with source code at https://github.com/udellgroup/rlaopt and version 0.1.0 available on PyPI.

Pratik Rathore, Zachary Frangella, Parth Nobel +2

Stanford University

Empirical Risk Minimization
AskPDF
Aug 31, 2026

An Agnostic Sample Compression Scheme for Squared Loss of Near-Linear Size in the Fat-Shattering Dimension

We study the squared-loss sample compression question posed by Attias, Hanneke, Kontorovich, and Sadigurschi in their ICML 2024 paper. For every nonempty class F⊆[0,1]X\mathcal{F}\subseteq[0,1]^{\mathcal{X}} and accuracy 0<α≤10<α\le1 with d=fat⁡(F,c′α)<∞d=\operatorname{fat}(\mathcal{F},c'α)<\infty, where c′>0c'>0 is universal, we prove the existence of a deterministic agnostic scheme of total size O(dlog⁡3(2/α))O(d\log^3(2/α)). Its code contains original labeled observations and auxiliary bits, and its reconstruction has empirical loss at most αα above the infimum over F\mathcal{F} on every finite sample. This establishes the polylogarithmic formulation in Section 5 of arXiv:1810.01864v2. The construction approximates a near-optimal internal target by a fixed-step boosting ensemble and takes its equal-weight median. Average loss permits an accuracy-dependent number of rounds, so the entire ensemble can be retained without dual-dimension sparsification. Quantized target constraints and round-membership bits determine the reconstructed function exactly. We also prove that, when retained observations must come from the sample, a fixed class of fat-shattering dimension one requires total size Ω(log⁡(1/α))Ω(\log(1/α)). With observations and auxiliary bits charged together, this rules out the proceedings version's log-free formulation under its original-example restriction. The framework extends to average power loss at scale α/pα/p.

Guangjian Zhang, Zhengyi Yang, Xiaoyang Wang

Agnostic LearningSample CompressionEmpirical Risk Minimization
AskPDF
Aug 28, 2026

Exact Risk Ratios for Weighted Data Selection in Linear Regression

How much data must a fixed learner retain? Hanneke, Moran, Shlimovich and Yehudayoff (COLT 2025) posed this question for linear regression with the minimum-norm empirical risk minimizer. A selector sees a finite dataset D⊆Rd×RD\subseteq R^d\times R, keeps at most nn examples with nonnegative weights, and Fw(d,n)F_w(d,n) is the worst-case ratio between the full-data loss of the trained predictor and the optimal loss. The value is ∞\infty for n<dn<d, d+1d+1 at n=dn=d and 11 for n≥2dn\ge2d, and the regime d<n<2dd<n<2d was left open. We settle several cases. For every dd we prove Fw(d,2d−1)=1+1/dF_w(d,2d-1)=1+1/d, which confirms a claim stated without proof in the original note. We also prove Fw(3,4)=5/3F_w(3,4)=5/3, Fw(4,5)=2F_w(4,5)=2 and Fw(4,6)=3/2F_w(4,6)=3/2, the three smallest cells not covered by that formula. For every intermediate budget n=d+kn=d+k we prove the lower bound Fw(d,d+k)≥1+Γd,kF_w(d,d+k)\ge1+Γ_{d,k}, where Γd,kΓ_{d,k} is an explicit harmonic quantity over balanced partitions of dd. This bound is the exact minimax value on the class of datasets whose whitened systems split into orthogonal circuit blocks. All proved values equal 1+Γd,k1+Γ_{d,k}, and we conjecture that this holds throughout the open regime. Our upper bounds combine a rigidity theorem for positive spanning configurations of loss gradients with normal forms of the small positive bases in R3R^3 and R4R^4. These forms are special cases of the classification of Cornaz, Kerleau and Royer; we also control all gradients outside the basis. A dimension-free extremal-basis argument converts sign-cone geometry into selections of d+1d+1 points. Explicit counterexamples rule out several shorter routes. Every upper bound is constructive, with selection procedures polynomial in the number of points for fixed dimension. Every numerical claim about a specific instance is an exact rational or algebraic identity, recomputed in exact arithmetic in the supplementary material.

Guangjian Zhang

University of New South Wales

Training Data SelectionLinear RegressionEmpirical Risk MinimizationCoreset SelectionMinimax Estimation
AskPDF
Aug 10, 2026

ReliableNet: A Chance-Constrained Approach to Trustworthy Classification in Deep Learning

A prediction that is both confident and wrong is a critical reliability failure because it can bypass abstention and human review precisely when the model is mistaken. Empirical risk minimization (ERM) controls average loss but not this failure directly, while calibration, uncertainty estimation, conformal risk control, and selective prediction methods target related reliability properties rather than bounding the joint failure event during training. We propose ReliableNet, which constrains the Joint Confident-Wrong (JCW) probability, the probability that a prediction is simultaneously confident and incorrect, below a user-specified risk budget α∈(0,1)α\in(0,1). We formulate this as a chance-constrained ERM problem, use a conservative smooth inner approximation whose population feasibility implies the original JCW constraint. Across four tabular and two image datasets, ReliableNet is the only method certified within the JCW budget for every dataset and seed in distribution, when compared against baselines spanning ERM, post-hoc calibration, conformal risk control, and selective prediction. Under demographic, ambiguity, spurious-correlation, novel-class, and covariate shifts, it achieves the lowest empirical JCW among the compared methods while remaining very competitive in accuracy, coverage, calibration, and selective prediction. Risk-coverage results further indicate that ReliableNet achieves better selective ranking than the benchmark methods on most datasets. Overall, ReliableNet provides a principled approach to trustworthy classification.

Ange-Clément Akazan, Ineza Remy Mugenga, Abebe Geletu +2

School of Agriculture and Science, University of KwaZulu-Natal, Pietermaritzburg, KwaZulu-Natal, South Africa · 2AIMS Research and Innovation Centre, African Institute for Mathematical Sciences, Kigali, Rwanda · 3African Institute for Mathematical Sciences, Kigali, Rwanda

Chance-Constrained OptimizationClassificationEmpirical Risk Minimization
AskPDF
Jul 30, 2026

Tight Sample Complexity for Low-Rank Adaptation: Matching Bounds and Rank Selection

Low-Rank Adaptation (LoRA) has become the standard mechanism for fine-tuning large pretrained models, yet its statistical properties remain only partially understood. Existing generalization results provide upper bounds of the form O~(sqrt(rd/n)) or O~(rd/n), but a matching lower bound is missing, and the question of how to choose the LoRA rank r has no formal answer. Both gaps are closed here. A local Rademacher argument establishes an upper bound of O~(rd/n) on the excess risk of the empirical risk minimizer over rank-r LoRA, whenever the target adaptation has rank at most r. A matching minimax lower bound of Omega(rd/n) is then proved via a Fano-type packing of the rank-r subspace of R^{d x d}; the bound applies to any estimator whose output lies in the rank-r LoRA class. Combining the two yields a rank-selection dichotomy. For the constrained empirical risk minimizer, the optimal rank equals the intrinsic rank r*, and over-ranking strictly hurts. For adaptive estimators of the nuclear-norm-then-truncate type, over-ranking is harmless and the rate saturates at Theta~(r* d / n) regardless of r. Taken together, the three results characterize the statistical complexity of LoRA fine-tuning within the well-specified locally quadratic regime, and identify the empirically observed over-parameterization penalty as a property of unregularized empirical risk minimization rather than of the LoRA class itself. Predictions of the theory are verified on a synthetic trace-regression benchmark and on real LoRA fine-tuning across three (model, task) configurations covering DistilBERT and RoBERTa on SST-2 and MRPC. All configurations exhibit the predicted U-shape in validation loss, with two showing statistically significant loss inflation at large ranks (paired permutation p = 0.016).

Arunan J

Independent Researcher, Chennai, India.

Sample ComplexityLow-Rank AdaptationMinimax EstimationStatistical Learning TheoryEmpirical Risk Minimization
AskPDF
Jul 26, 2026

Learning switched non-linear dynamical systems from a single trajectory

We study empirical risk minimization for learning non-linear dynamical systems whose transition dynamics may switch over time. Under stability assumptions, and i.i.d switching over a set of KK modes, we derive non-asymptotic bounds on the prediction risk expressed in terms of the metric entropy of the underlying function class. We instantiate our general result for Hölder and linear function classes, obtaining explicit convergence rates that depend on the effective sample size TpiTp_i, where TT is the trajectory length and pip_i is the probability of observing mode ii. Numerical simulations support our theoretical findings. To the best of our knowledge, these results are the first non-asymptotic guarantees for learning switched nonlinear dynamical systems from a single trajectory.

Sunny G. W. Wang, Hemant Tyagi

Division of Mathematical Sciences, SPMS, NTU Singapore 637371

Regime-Switching Dynamical SystemsNonlinear System IdentificationSystem IdentificationStatistical Learning TheoryEmpirical Risk Minimization
AskPDF
Jul 19, 2026

Team DACTYL at PAN 2026: Bayesian Data Mixing and Empirical X-risk Minimization for AI-text Detection

Existing research shows that AI-generated text detection classifiers achieve strong in-distribution (ID) performance but do not maintain the same performance on out-of-distribution (OOD) texts, suggesting overfitting to dataset-specific features. However, combining different training datasets doesn't always improve performance and, in some cases, can even encourage shortcut learning. To address this issue, we fine-tune BERT-tiny models with Bayesian classification heads to select texts across three different datasets to use as a consolidated training set. We trained three different classifiers: fine-tuned DeBERTa-V3-large and ModernBERT-large classifiers via empirical X-risk minimization, and an MCGrad model that calibrates the predictions from the ModernBERT-large classifier. The DeBERTa-V3-large-large classifier achieves a mean score of 0.882 on the PAN 2026 test set across five metrics: AUROC, F1F_1, C@1, Brier score, and F0.5uF_{0.5u}. ModernBERT-large achieves a score of 0.96 while MCGrad achieves the best score of the three with a mean score of 0.974, ranking second on the leaderboard. Our results highlight that careful dataset curation can lead to strong OOD performance. We release our ModernBERT-large and DeBERTa-V3-large models at https://huggingface.co/collections/ShantanuT01/panclef-2026 .

Shantanu Thorat

College Station, Texas, US

AI-Generated Text DetectionData SelectionOOD DetectionRobustness of Machine-Generated Text DetectionEmpirical Risk Minimization
AskPDF
Jun 26, 2026

Replica Symmetry Breaking and Algorithmic Thresholds in Empirical Risk Minimization under Multi-Index Model

Modern machine learning models are trained by optimizing high-dimensional non-convex empirical risk functions. Such cost functions can have a multitude of local optima and yet, gradient-based optimization appears to converge to near-global optima. Within a simple supervised learning setting, we develop a precise picture of which parts of the empirical risk landscape are accessible by polynomial-time algorithms. We are given i.i.d. pairs {(xi,yi):  1≤i≤n}\{(\boldsymbol{x}_i,y_i):\; 1 \le i\le n\} with xi∈Rd\boldsymbol{x}_i\in \mathbb{R}^d standard Gaussian feature vectors, and yi∈Ry_i\in\mathbb{R} response variables that depend on xi\boldsymbol{x}_i through their projections on an unknown kk-dimensional subspace. We use empirical risk minimization to learn a model that depends on an mm-dimensional projection of the data (e.g., an mm-neurons neural network). We propose an incremental approximate message passing (IAMP) algorithm and precisely characterize the training error it achieves, as well as the relation between test and training error, in the high dimensional asymptotics n,d→∞n,d\to\infty, with n/d→α∈(0,+∞)n/d\toα\in (0, +\infty). Based on earlier work in related models, we expect that the performance achieved by our algorithm is optimal among polynomial-time algorithms.

Andrea Montanari, Kangjie Zhou

Department of Mathematics and Department of Statistics, Stanford University · Department of Statistics, Columbia University

Approximate Message PassingStatistical Learning TheoryMulti-Index ModelsEmpirical Risk Minimization
AskPDF
Jun 22, 2026

Non-asymptotic estimates of the minimal risk in statistical learning

In this paper we prove some concentration inequalities for two types of error probabilities in the Empirical Risk Principle (ERP) in statistical learning, which provide a lower bound and an upper bound for the minimal risk (in terms of the minimal empirical risk) with non-asymptotic high confidence. The usual boundedness condition of the empirical risk function is relaxed to the Gaussian or exponential integrability condition. The confidence of the lower bound of the minimal risk is shown to be independent of the number of training parameters and the dimension of the input vectors, allowing one to detect the deficiency of a learning machine efficiently; and the confidence of the upper bound of the minimal risk is proved to be high provided that the sample size nn is much greater than the box dimension of the parameter set ΘΘ in the Orlicz metric dψ1d_{ψ_1} associated with the risk functions. Our work is based on Talagrand's concentration inequalities (the sharp versions by Bousquet and Klein-Rio), transport-entropy inequalities and the recent progress in the theory of empirical processes and statistical learning.

Liming Wu, Sen Yang

Laboratoire de Mathématiques Blaise Pascal, CNRS-UMR 6620, Université Clermont Auvergne · IASM, Harbin Institute of Technology

Statistical Learning TheoryEmpirical Risk MinimizationGeneralization Bounds
AskPDF
Jun 18, 2026

On the Oracle Complexity of Interpolation-Based Gradient Descent

Recent work on first-order optimizers for empirical risk minimization (ERM) has suggested that smoothness of ERM loss functions in the training data, rather than in the optimization parameters, can be leveraged to improve the oracle complexity of gradient descent (GD) methods. In this paper, we propose an inexact gradient method, piecewise polynomial interpolation-based gradient descent (PPI-GD), which approximates the full gradient in each iteration by querying the first-order oracle at equidistant points in the data domain to construct polynomial interpolants of the resulting gradient samples over appropriately sized patches of the data domain. We analyze the oracle complexity of PPI-GD for strongly convex and non-convex loss functions when the data space dimension is bounded by a polylogarithmic function of the number of training samples, and find it to outperform several GD variants in key regimes when the loss function is sufficiently smooth. Furthermore, our analysis extends several techniques from the error analysis of bicubic spline interpolants to the setting of dd-variate tensor product polynomial interpolants which may be of independent interest in interpolation analysis.

Dongmin Lee, William Lu, Anuran Makur

Department of Computer Science, Purdue University, West Lafayette, IN 47907, USA · Department of Computer Science and the Elmore Family School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN 47907, USA

Oracle ComplexityGradient DescentNonconvex OptimizationStatistical Learning TheoryEmpirical Risk Minimization
AskPDF
May 14, 2026

Focused PU learning from imbalanced data

We propose a new method of learning from positive and unlabeled (PU) examples in highly imbalanced datasets. Many real-world problems, such as disease gene identification, targeted marketing, fraud detection, and recommender systems, are hard to address with machine learning methods, due to limited labeled data. Often, training data comprises positive and unlabeled instances, the latter typically being dominated by negative, but including also several positive instances. While PU learning is well-studied, few methods address imbalanced settings or hard-to-detect positive examples that resemble negative ones. Our approach uses a focused empirical risk estimator, incorporating both positive and unlabeled examples to train binary classifiers. Empirical evaluations demonstrate state-of-the-art performance on imbalanced datasets under two labeling mechanisms - selecting positives completely at random (SCAR) and selecting at random (SAR). Beyond these controlled experiments, we demonstrate the value of the proposed method in the real-world application of financial misstatement detection.

Elias Zavitsanos, Georgios Paliouras

Institute of Informatics and Telecommunications, NCSR “Demokritos”, Patriarhou Gregoriou E and 27 Neapoleos St., Agia Paraskevi, 15310, Attica, Greece.

Class-Imbalanced LearningBinary ClassificationWeakly Supervised LearningClassificationPositive-Unlabeled LearningEmpirical Risk Minimization
AskPDF
May 12, 2026

Learning U-Statistics with Active Inference

UU-statistics play a central role in statistical inference. In many modern applications, however, acquiring the labels required for UU-statistics is costly. Motivated by recent advances in active inference, we develop an active inference framework for UU-statistics that selectively queries informative labels to improve estimation efficiency under a fixed labeling budget, while preserving valid statistical inference. Our approach is built on the augmented inverse probability weighting UU-statistic, which is designed to incorporate the sampling rule and machine learning predictions. We characterize the optimal sampling rule that minimizes its variance and design practical sampling strategies. We further extend the framework to UU-statistic-based empirical risk minimization. Experiments on real datasets demonstrate substantial gains in estimation efficiency over baseline methods, while maintaining target coverage.

Xiaoning Wang, Yuyang Huo, Liuhua Peng +1

School of Statistics and Data Sciences, LPMC, KLM-DASR and LEBPS, Nankai University, Tianjin, China · School of Mathematics and Statistics, The University of Melbourne, Melbourne, Australia

Active InferenceU-StatisticsActive LearningAdaptive SamplingStatistical Learning TheoryEmpirical Risk Minimization
AskPDF
May 8, 2026

Risk-Consistent Multiclass Learning from Random Label-Subset Membership Queries

Obtaining accurate class labels is often costly or unreliable, and may also be limited by privacy or other practical conditions. Compared with asking an annotator to provide the exact class, it is often easier to ask whether the true label belongs to a certain label subset. This query-response form defines a distinct weak-supervision mechanism: weak supervision information is generated through feedback on a label subset. Although weakly supervised learning has studied many learning frameworks, most existing work starts from established weak label objects. A systematic characterization is still lacking for weakly supervised learning generated directly by such query response observations. This paper proposes a multiclass learn ing framework under random label-subset queries. We model the data-generating distribution of query-response observations and derive an unbiased estimator of the target risk under the empirical risk minimization (ERM) framework. To address negative empirical risk and the associated overfitting problem, we introduce corrected risk estimators based on non-negative and absolute-value corrections. Theoretical analysis establishes a conditional generalization and excess-risk bound for the unbiased estimator, and a bias-and-consistency result for the corrected risk estimator. Experiments under the matched random-query mechanism demonstrate the feasibility of direct query-response learning and the stabilization effect of risk correction.

Jiaxu Su, Junpeng Li, Changchun Hua +1

Engineering Research Center of the Ministry of Education for Intelligent Control System and Intelligent Equipment, Yanshan University, Qinhuangdao, China

Multiclass ClassificationWeakly Supervised LearningClassificationStatistical Learning TheoryEmpirical Risk Minimization
AskPDF
Apr 28, 2026

Elite-Driven Support Vector Machines for Classification

Support vector machines (SVMs) are a standard tool for binary classification, but their classical formulations are purely data-driven and offer no direct way to encode trusted benchmark models or structured preferences on selected subsets of the data. We propose Elite-Driven Support Vector Machines (EDSVM), a general framework that augments regularized empirical risk minimization by guiding the slack variables for a curated set of elite observations (typically the union of support vectors from one or more reference SVMs). EDSVM combines the usual slack loss with a deviation penalty that shrinks new slacks toward benchmark slack values, defining a localized, margin-aligned notion of proximity to reference models, unlike global function penalties in knowledge distillation or teacher-student methods, and without requiring privileged features as in SVM+/LUPI. Within this framework we develop two concrete models, C-EDSVM and LS-EDSVM, based respectively on hinge-type and squared-slack losses. For both variants we derive dual quadratic programs that can be implemented with modest modifications of standard SVM solvers, and we give simple sufficient conditions under which the induced margin losses are classification calibrated. Simulation studies and experiments on several UCI benchmarks show that EDSVMs closely track the behaviour induced by reference SVMs while achieving predictive performance that is competitive with, and sometimes better than, C-SVM, LINEX-SVM, and LS-SVM.

Mohammad Jafari Jozani, Bahram Moeinianfar

Department of Statistics, University of Manitoba, Winnipeg, Manitoba, CANADA, R3T2N2

Binary ClassificationSupport Vector MachinesClassificationStatistical Learning TheoryEmpirical Risk Minimization
AskPDF
Apr 22, 2026

Decentralized Machine Learning with Centralized Performance Guarantees via Gibbs Algorithms

In this paper, it is shown, for the first time, that centralized performance is achievable in decentralized learning without sharing the local datasets. Specifically, when clients adopt an empirical risk minimization with relative-entropy regularization (ERM-RER) learning framework and a forward-backward communication between clients is established, it suffices to share the locally obtained Gibbs measures to achieve the same performance as that of a centralized ERM-RER with access to all the datasets. The core idea is that the Gibbs measure produced by client~kk is used, as reference measure, by client~k+1k+1. This effectively establishes a principled way to encode prior information through a reference measure. In particular, achieving centralized performance in the decentralized setting requires a specific scaling of the regularization factors with the local sample sizes. Overall, this result opens the door to novel decentralized learning paradigms that shift the collaboration strategy from sharing data to sharing the local inductive bias via the reference measures over the set of models.

Yaiza Bermudez, Samir M. Perlaza, Iñaki Esnaola

Centre Inria d'Université Côte d'Azur, INRIA, Sophia Antipolis, France. · Laboratoire GAATI, Université de la Polynésie française, Fa'a'ā, French Polynesia. · ECE Dept. Princeton University, Princeton, 08544 NJ, USA. +1

Decentralized LearningStatistical Learning TheoryEmpirical Risk Minimization
AskPDF
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θ^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 xx independent of the training data, the projection θ^⊤x\hatθ^\top x approximately follows the convolution of the generally non-Gaussian distribution of μθ^⊤xμ_{\hatθ}^\top x with an independent centered Gaussian variable of variance tr(Cθ^E[xx⊤])\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 MinimizationHigh-Dimensional Asymptotics
AskPDF
Mar 20, 2026

From Cross-Validation to SURE: Asymptotic Risk of Tuned Regularized Estimators

We derive the asymptotic risk function of regularized empirical risk minimization (ERM) estimators tuned by nn-fold cross-validation (CV). The out-of-sample prediction loss of such estimators converges in distribution to the squared-error loss (risk function) of shrinkage estimators in the normal means model, tuned by Stein's unbiased risk estimate (SURE). This risk function provides a more fine-grained picture of predictive performance than uniform bounds on worst-case regret, which are common in learning theory: it quantifies how risk varies with the true parameter. As key intermediate steps, we show that (i) nn-fold CV converges uniformly to SURE, and (ii) while SURE typically has multiple local minima, its global minimum is generically well separated. Well-separation ensures that uniform convergence of CV to SURE translates into convergence of the tuning parameter chosen by CV to that chosen by SURE.

Karun Adusumilli, Maximilian Kasy, Ashia Wilson

Department of Economics, University of Pennsylvania. · Department of Economics, University of Oxford. · Department of Electrical Engineering and Computer Science, MIT.

Cross-ValidationShrinkage EstimationEmpirical Risk Minimization
AskPDF
Mar 17, 2026

Self-Regularized Learning Methods

We introduce a general framework for analyzing learning algorithms based on the notion of self-regularization, which captures implicit complexity control without requiring explicit regularization. This is motivated by previous observations that many algorithms, such as gradient-descent based learning, exhibit implicit regularization. In a nutshell, for a self-regularized algorithm the complexity of the predictor is inherently controlled by that of the simplest comparator achieving the same empirical risk. This framework is sufficiently rich to cover both classical regularized empirical risk minimization and gradient descent. Building on self-regularization, we provide a thorough statistical analysis of such algorithms including minmax-optimal rates, where it suffices to show that the algorithm is self-regularized -- all further requirements stem from the learning problem itself. Finally, we discuss the problem of data-dependent hyperparameter selection, providing a general result which yields minmax-optimal rates up to a double logarithmic factor and covers data-driven early stopping for RKHS-based gradient descent.

Max Schölpple, Liu Fanghui, Ingo Steinwart

Institute for Stochastics and Applications, University of Stuttgart · School of Mathematical Sciences, Institute of Natural Sciences and MOE-LSC, Shanghai Jiao Tong University

Statistical Learning TheoryImplicit RegularizationEmpirical Risk Minimization
AskPDF
Mar 16, 2026

Muon Converges under Heavy-Tailed Noise: Nonconvex Hölder-Smooth Empirical Risk Minimization

Muon is a recently proposed optimizer that enforces orthogonality in parameter updates by projecting gradients onto the Stiefel manifold, leading to stable and efficient training in large-scale deep neural networks. Meanwhile, the previously reported results indicated that stochastic noise in practical machine learning may exhibit heavy-tailed behavior, violating the bounded-variance assumption. In this paper, we consider the problem of minimizing a nonconvex Hölder-smooth empirical risk that works well with the heavy-tailed stochastic noise. We then show that Muon converges to a stationary point of the empirical risk under the boundedness condition accounting for heavy-tailed stochastic noise. In addition, we show that Muon converges faster than mini-batch SGD.

Hideaki Iiduka

Department of Computer Science Meiji University 1-1-1 Higashimita, Tama-ku, Kawasaki-shi, Kanagawa 214-8571 Japan

Nonconvex Stochastic OptimizationMuon OptimizerNonconvex OptimizationEmpirical Risk MinimizationHeavy-Tailed Stochastic Optimization
AskPDF