Super-fast rates of convergence for Neural Networks Classifiers under the Hard Margin Condition

2025/05/13 by Tepakbong, Nathanael, Zhou, Ding-Xuan, Zhou, Xiang
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.2505.08262

Abstract

We study the classical binary classification problem for hypothesis spaces of Deep Neural Networks (DNNs) with ReLU activation under Tsybakov's low-noise condition with exponent q>0, and its limit-case q→∞ which we refer to as the "hard-margin condition". We show that DNNs which minimize the empirical risk with square loss surrogate and ℓ_p penalty can achieve finite-sample excess risk bounds of order O(n^-α) for arbitrarily large α>0 under the hard-margin condition, provided that the regression function η is sufficiently smooth. The proof relies on a novel decomposition of the excess risk which might be of independent interest.

Citations

• Don't Fear Peculiar Activation Functions: EUAF and Beyond
• KAN: Kolmogorov-Arnold Networks
• On Excess Risk Convergence Rates of Neural Network Classifiers
• Classification with Deep Neural Networks and Logistic Loss
• Improved Bounds on Neural Complexity for Representing Piecewise Linear Functions
• Convergence Rates of Training Deep Neural Networks via Alternating Minimization Methods
• Optimal Convergence Rates of Deep Neural Networks in a Classification Setting
• Minimax Optimal Deep Neural Network Classifiers Under Smooth Decision Boundary
• Multiclass learning with margin: exponential rates with no bias-variance trade-off
• Optimal learning of high-dimensional classification problems using deep neural networks
• Understanding Square Loss in Training Overparametrized Neural Network Classifiers
• Convergence rates of deep ReLU networks for multiclass classification
• Fast Convergence on Perfect Classification for Functional Data
• Deep Equals Shallow for ReLU Networks in Kernel Regimes
• Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regime
• Evaluation of Neural Architectures Trained with Square Loss vs Cross-Entropy in Classification Tasks
• Deep Network Approximation for Smooth Functions
• Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks
• Approximation in L^p(μ) with deep ReLU neural networks
• Fast convergence rates of deep neural networks for classification
• Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Universality of Deep Convolutional Neural Networks
• Universality of deep convolutional neural networks
• Lipschitz regularity of deep neural networks: analysis and efficient estimation
• The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks
• Learning Sparse Neural Networks through L₀ Regularization
• Bounding and Counting Linear Regions of Deep Neural Networks
• Optimal approximation of piecewise smooth functions using deep ReLU\n neural networks
• Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks
• Error bounds for approximations with deep ReLU networks
• Distilling the Knowledge in a Neural Network
• On the Number of Linear Regions of Deep Neural Networks
• ImageNet classification with deep convolutional neural networks
• Enhancing Sparsity by Reweighted L1 Minimization
• Learning Theory Estimates via Integral Operators and Their Approximations
• Clarke subgradients of stratifiable functions
• Fast learning rates for plug-in classifiers under the margin condition

Related

• Optimal Convergence Rates of Deep Neural Network Classifiers
• Optimal Convergence Rates of Deep Neural Networks in a Classification Setting
• On Excess Risk Convergence Rates of Neural Network Classifiers
• Minimax Optimal Deep Neural Network Classifiers Under Smooth Decision Boundary
• Sharper Guarantees for Learning Neural Network Classifiers with Gradient Methods