Research map / Learning theory and algorithms / Sample complexity
Universal Consistency of Wide and Deep ReLU Neural Networks and Minimax Optimal Convergence Rates for Kolmogorov-Donoho Optimal Function Classes
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves universal strong consistency of wide and deep ReLU network classifiers trained on logistic loss, and gives sufficient conditions (via Kolmogorov-Donoho optimal exponents) under which neural network classifiers attain minimax optimal excess-risk rates, with interpolating classifiers.
Problem
Whether finitely wide and deep neural network classifiers are universally consistent, and in which distributional regimes they achieve minimax optimal convergence rates for excess classification risk without explicit smoothness assumptions on the regression function.
Approach
Uses sieve-based empirical risk minimization over ReLU networks with growing architectures and a compactification argument (Wald's method) for universal consistency; for rates, controls estimation error via VC-dimension and approximation error via neural-network approximation of function classes with finite Kolmogorov-Donoho optimal exponent, avoiding calibration inequalities by constructing Hölde
Key results
- Proves that empirical risk minimizers of logistic loss over ReLU networks with width or depth growing (W(S_n)>=n or L(S_n)>=n) are universally strongly consistent.
- Gives sufficient conditions (e.g., 2(1+alpha)gamma*(1-m*) >= (2+alpha)m*) under which plug-in classifiers achieve minimax optimal rates up to polylog factors for function classes with finite Kolmogorov-Donoho optimal exponent.
- Shows interpolating logistic-loss minimizers achieve zero training classification error, with minimax optimal rates up to log factor under a slightly stronger condition.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use logistic-loss empirical risk minimization with wide or deep ReLU networks whose width or depth grows with sample size | ReLU neural network classifiers · Arbitrary probability distributions | classification risk consistency | Helped |
| Use classification-loss empirical risk minimization with networks that optimally represent the regression-function class | ReLU neural network classifiers · Distributions with regression functions in an optimally representable class | excess classification risk | Helped |
| Use logistic-loss empirical risk minimization with skip connections and the allowed activation functions | Feed-forward neural network classifiers · Distributions with regression functions in an optimally representable class | excess classification risk | Helped |
Surprising findings
- Minimax-optimal rates for classification can be achieved by ERM on the L2 approximation-theoretic side without calibration inequalities, which the authors argue can be suboptimal.
- Minimizing the L2 risk and minimax classification risk are not interchangeable: the uniform minimax rates can match but the plug-in of the L2 minimizer is not necessarily optimal.
Limitations
- Universal consistency relies on existence of architectures growing with n and is not computationally practical as an algorithm analysis; ERM over the compactified space is an abstract object.
- Minimax rates require the stronger condition for logistic-loss ERM and results hold only up to polylogarithmic factors.
- Assumes marginal density of X bounded w.r.t. Lebesgue measure on [0,1]^d and regression function in a compact class with finite optimal exponent.
Experimental setup
Metrics: excess classification risk consistency (almost sure) minimax convergence rate
Baselines: Kim et al. 2021 (Universal consistency of 1-hidden-layer sigmoidal networks) Hu et al. 2021 / Kim et al. (NTK-based consistency) Kohler and Langer (Hölder smooth deep networks)
Builds on: Tsybakov noise condition Kolmogorov-Donoho optimal exponent Wald's consistency method Devroye et al. universal consistency of neural network classifiers
Closest papers by meaning
- Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizes (NeurIPS 2024 · similarity 0.89)
- ReLU Network with Width $d+\mathcal{O}(1)$ Can Achieve Optimal Approximation Rate (ICML 2024 · similarity 0.88)
- Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time (ICML 2024 · similarity 0.88)
- Stable Minima of ReLU Neural Networks Suffer from the Curse of Dimensionality: The Neural Shattering Phenomenon (NeurIPS 2025 · similarity 0.87)
- A Universal Growth Rate for Learning with Smooth Surrogate Losses (NeurIPS 2024 · similarity 0.87)
- Global Minimizers of $\ell^p$-Regularized Objectives Yield the Sparsest ReLU Neural Networks (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.