Empirical Risk Minimization

Also known as ERM

Follow this topic Ask about this topic

Latest papers 42

3 papers in the last four weeks, down 57% on the four weeks before. 0.0% of all new papers.

All topics

Learning a Group Element from Its Action: Galois Correspondences, Optimal ERM, and an Abel-Ruffini Threshold for the Natarajan Dimension
Oct 13, 2026Xiaoyu LiSample Complexity Multiclass Classification
University of New South Wales
Asymptotic Analysis of Empirical Risk Minimization on Entry-wise i.i.d. Heavy-Tailed Data
Oct 6, 2026Kaito Takanami, Takashi Takahashi, Yoshiyuki KabashimaStatistical Physics of Learning Linear Regression
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
Entropy Regularization: A Free Correction to Cross-Entropy for Verified Demonstrations
Sep 24, 2026Mihir Dhanakshirur, Adam Ousherovitch, Ambuj TewariEntropy Regularization LLM Reasoning
Department of Statistics, University of Michigan
Tail-Weight Control and Localized Generalization in Nearly Low-Rank Adversarial Classification
Sep 20, 2026Kunyu Wang, Dehan Wang, Wenjun ChenAdversarial Robustness Robust Loss Functions
The Chinese University of Hong Kong · Columbia University
Weighted Empirical Risk Minimization for Machine Learning under Long-Range Dependence: Exact Pathwise Rates and Learning-Error Geometry
Sep 9, 2026Elina MoldavskayaStatistical Learning Theory Empirical Risk Minimization
Technion–Israel Institute of Technology, Israel
An Exponential Deterministic--Randomized Gap in ERM-Oracle Complexity for Thresholds on an Unknown Order
Sep 9, 2026Xuan LiQuery Complexity Oracle Complexity
University of New South Wales, Sydney, Australia
Weighted Data Selection: Sharp Upper-Half and Five-Dimensional Laws
Sep 8, 2026Zhongxuan Liu, Hongzhi WangData Selection Training Data Selection
Faculty of Computing, Harbin Institute of Technology
Fitting and Learning Basis-Restricted Propositional Formulas
Sep 8, 2026Balder ten CateBoolean Function Learning Empirical Risk Minimization
GPU-Enabled Large-Scale Optimization Using Randomized Linear Algebra
Sep 8, 2026Pratik Rathore, Zachary Frangella, Parth Nobel +2Empirical Risk Minimization
Stanford University
An Agnostic Sample Compression Scheme for Squared Loss of Near-Linear Size in the Fat-Shattering Dimension
Aug 31, 2026Guangjian ZhangEmpirical Risk Minimization
Exact Risk Ratios for Weighted Data Selection in Linear Regression
Aug 28, 2026Guangjian ZhangTraining Data Selection Linear Regression
University of New South Wales
ReliableNet: A Chance-Constrained Approach to Trustworthy Classification in Deep Learning
Aug 10, 2026Ange-Clément Akazan, Ineza Remy Mugenga, Abebe Geletu +2Chance-Constrained Optimization Classification
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
Tight Sample Complexity for Low-Rank Adaptation: Matching Bounds and Rank Selection
Jul 30, 2026Arunan JSample Complexity Low-Rank Adaptation
Independent Researcher, Chennai, India.
Learning switched non-linear dynamical systems from a single trajectory
Jul 26, 2026Sunny G. W. Wang, Hemant TyagiRegime-Switching Dynamical Systems Nonlinear System Identification
Division of Mathematical Sciences, SPMS, NTU Singapore 637371
Team DACTYL at PAN 2026: Bayesian Data Mixing and Empirical X-risk Minimization for AI-text Detection
Jul 19, 2026Shantanu ThoratAI-Generated Text Detection Data Selection
College Station, Texas, US
Replica Symmetry Breaking and Algorithmic Thresholds in Empirical Risk Minimization under Multi-Index Model
Jun 26, 2026Andrea Montanari, Kangjie ZhouStatistical Learning Theory Multi-Index Models
Department of Mathematics and Department of Statistics, Stanford University · Department of Statistics, Columbia University
Non-asymptotic estimates of the minimal risk in statistical learning
Jun 22, 2026Liming Wu, Sen YangStatistical Learning Theory Empirical Risk Minimization
Laboratoire de Mathématiques Blaise Pascal, CNRS-UMR 6620, Université Clermont Auvergne · IASM, Harbin Institute of Technology
On the Oracle Complexity of Interpolation-Based Gradient Descent
Jun 18, 2026Dongmin Lee, William Lu, Anuran MakurOracle Complexity Gradient Descent
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
Focused PU learning from imbalanced data
May 14, 2026Elias Zavitsanos, Georgios PaliourasClass-Imbalanced Learning Binary Classification
Institute of Informatics and Telecommunications, NCSR “Demokritos”, Patriarhou Gregoriou E and 27 Neapoleos St., Agia Paraskevi, 15310, Attica, Greece.
Learning U-Statistics with Active Inference
May 12, 2026Xiaoning Wang, Yuyang Huo, Liuhua Peng +1Active Inference Active Learning
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
Risk-Consistent Multiclass Learning from Random Label-Subset Membership Queries
May 8, 2026Jiaxu Su, Junpeng Li, Changchun Hua +1Multiclass Classification Weakly Supervised Learning
Engineering Research Center of the Ministry of Education for Intelligent Control System and Intelligent Equipment, Yanshan University, Qinhuangdao, China
Elite-Driven Support Vector Machines for Classification
Apr 28, 2026Mohammad Jafari Jozani, Bahram MoeinianfarBinary Classification Support Vector Machines
Department of Statistics, University of Manitoba, Winnipeg, Manitoba, CANADA, R3T2N2
Decentralized Machine Learning with Centralized Performance Guarantees via Gibbs Algorithms
Apr 22, 2026Yaiza Bermudez, Samir M. Perlaza, Iñaki EsnaolaDecentralized Learning Statistical Learning Theory
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
Characterization of Gaussian Universality Breakdown in High-Dimensional Empirical Risk Minimization
Apr 3, 2026Chiheb Yaakoubi, Cosme Louart, Malik Tiomoko +1Empirical Risk Minimization
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
From Cross-Validation to SURE: Asymptotic Risk of Tuned Regularized Estimators
Mar 20, 2026Karun Adusumilli, Maximilian Kasy, Ashia WilsonEmpirical Risk Minimization
Department of Economics, University of Pennsylvania. · Department of Economics, University of Oxford. · Department of Electrical Engineering and Computer Science, MIT.
Self-Regularized Learning Methods
Mar 17, 2026Max Schölpple, Liu Fanghui, Ingo SteinwartStatistical Learning Theory Implicit Regularization
Institute for Stochastics and Applications, University of Stuttgart · School of Mathematical Sciences, Institute of Natural Sciences and MOE-LSC, Shanghai Jiao Tong University
Muon Converges under Heavy-Tailed Noise: Nonconvex Hölder-Smooth Empirical Risk Minimization
Mar 16, 2026Hideaki IidukaNonconvex Stochastic Optimization Muon Optimizer
Department of Computer Science Meiji University 1-1-1 Higashimita, Tama-ku, Kawasaki-shi, Kanagawa 214-8571 Japan
Interleaved Resampling and Refitting: Data and Compute-Efficient Evaluation of Black-Box Predictors
Mar 15, 2026Haichen Hu, David Simchi-LeviEmpirical Risk Minimization
Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA 02139, USA
On the Statistical Optimality of Optimal Decision Trees
Mar 5, 2026Zineng Xu, Subhro Ghosh, Yan Shuo TanDecision Tree Learning Statistical Learning Theory
Department of Statistics and Data Science, National University of Singapore · Department of Mathematics, National University of Singapore
A Researcher's Guide to Empirical Risk Minimization
Feb 25, 2026Lars van der LaanEmpirical Risk Minimization Statistical Learning Theory
Department of Statistics, University of Washington

Oct 13, 2026J/K move · Enter open · S save

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

Xiaoyu Li

University of New South Wales

Sample Complexity Multiclass Classification Empirical Risk Minimization

Open paper AskPDF arXiv

We study learning an unknown element

g

of a group acting with finite orbits on a countable set, from examples

(x,gx)

. After a sample on

A

, the consistent hypotheses are the restrictions of a coset of the pointwise stabilizer of

A

, 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

A_5

and

S_5

of the quintic they are

2<3

and

3<4

, and

A_5

is the smallest group with a gap. For the Galois group

S_n

of the general equation of degree

n

, they coincide exactly when

n\le 4

, i.e., in characteristic zero, exactly when the equation is solvable by radicals; the implication is one-way, as the simple group

\mathrm{PSL}(2,8)

has no gap. For linear, orthogonal and unitary maps of

\mathbb R^d

\mathbb C^d

both dimensions equal

d

, and a two-fibered pseudo-cube is a disjoint union of Natarajan cubes exactly when its monodromy group is abelian.