Optimal learning of high-dimensional classification problems using deep neural networks

• URL: http://arxiv.org/abs/2112.12555v2
• Date: Fri, 24 Dec 2021 07:53:17 GMT
• Title: Optimal learning of high-dimensional classification problems using deep neural networks
• Authors: Philipp Petersen, Felix Voigtlaender
• Abstract summary: We study the problem of learning classification functions from noiseless training samples, under the assumption that the decision boundary is of a certain regularity. For the class of locally Barron-regular decision boundaries, we find that the optimal estimation rates are essentially independent of the underlying dimension.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of learning classification functions from noiseless training samples, under the assumption that the decision boundary is of a certain regularity. We establish universal lower bounds for this estimation problem, for general classes of continuous decision boundaries. For the class of locally Barron-regular decision boundaries, we find that the optimal estimation rates are essentially independent of the underlying dimension and can be realized by empirical risk minimization methods over a suitable class of deep neural networks. These results are based on novel estimates of the $L^1$ and $L^\infty$ entropies of the class of Barron-regular functions.

Related papers

• Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability [71.82666334363174]
  We develop a unified framework for lower bound methods in statistical estimation and interactive decision making. We introduce a novel measure, decision dimension, which facilitates the complexity of new lower bounds for interactive decision making.
  arXiv  Detail & Related papers  (2024-10-07T15:14:58Z)
• Dimension-independent learning rates for high-dimensional classification problems [53.622581586464634]
  We show that every $RBV2$ function can be approximated by a neural network with bounded weights. We then prove the existence of a neural network with bounded weights approximating a classification function.
  arXiv  Detail & Related papers  (2024-09-26T16:02:13Z)
• On Excess Risk Convergence Rates of Neural Network Classifiers [8.329456268842227]
  We study the performance of plug-in classifiers based on neural networks in a binary classification setting as measured by their excess risks. We analyze the estimation and approximation properties of neural networks to obtain a dimension-free, uniform rate of convergence.
  arXiv  Detail & Related papers  (2023-09-26T17:14:10Z)
• The Boundaries of Verifiable Accuracy, Robustness, and Generalisation in Deep Learning [73.5095051707364]
  We consider classical distribution-agnostic framework and algorithms minimising empirical risks. We show that there is a large family of tasks for which computing and verifying ideal stable and accurate neural networks is extremely challenging.
  arXiv  Detail & Related papers  (2023-09-13T16:33:27Z)
• The Cascaded Forward Algorithm for Neural Network Training [61.06444586991505]
  We propose a new learning framework for neural networks, namely Cascaded Forward (CaFo) algorithm, which does not rely on BP optimization as that in FF. Unlike FF, our framework directly outputs label distributions at each cascaded block, which does not require generation of additional negative samples. In our framework each block can be trained independently, so it can be easily deployed into parallel acceleration systems.
  arXiv  Detail & Related papers  (2023-03-17T02:01:11Z)
• Learning Lipschitz Functions by GD-trained Shallow Overparameterized ReLU Neural Networks [12.018422134251384]
  We show that neural networks trained to nearly zero training error are inconsistent in this class. We show that whenever some early stopping rule is guaranteed to give an optimal rate (of excess risk) on the Hilbert space of the kernel induced by the ReLU activation function, the same rule can be used to achieve minimax optimal rate.
  arXiv  Detail & Related papers  (2022-12-28T14:56:27Z)
• Sample Complexity of Nonparametric Off-Policy Evaluation on Low-Dimensional Manifolds using Deep Networks [71.95722100511627]
  We consider the off-policy evaluation problem of reinforcement learning using deep neural networks. We show that, by choosing network size appropriately, one can leverage the low-dimensional manifold structure in the Markov decision process.
  arXiv  Detail & Related papers  (2022-06-06T20:25:20Z)
• Benefit of deep learning with non-convex noisy gradient descent: Provable excess risk bound and superiority to kernel methods [41.60125423028092]
  We show that any linear estimator can be outperformed by deep learning in a sense of minimax optimal rate. The excess bounds are so-called fast learning rate which is faster than $O bounds.
  arXiv  Detail & Related papers  (2020-12-06T09:22:16Z)
• Attribute-Guided Adversarial Training for Robustness to Natural Perturbations [64.35805267250682]
  We propose an adversarial training approach which learns to generate new samples so as to maximize exposure of the classifier to the attributes-space. Our approach enables deep neural networks to be robust against a wide range of naturally occurring perturbations.
  arXiv  Detail & Related papers  (2020-12-03T10:17:30Z)
• Neural network approximation and estimation of classifiers with classification boundary in a Barron class [0.0]
  We prove bounds for the approximation and estimation of certain binary classification functions using ReLU neural networks. Our estimation bounds provide a priori performance guarantees for empirical risk using networks of a suitable size.
  arXiv  Detail & Related papers  (2020-11-18T16:00:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.