Computability of Classification and Deep Learning: From Theoretical Limits to Practical Feasibility through Quantization

• URL: http://arxiv.org/abs/2408.06212v1
• Date: Mon, 12 Aug 2024 15:02:26 GMT
• Title: Computability of Classification and Deep Learning: From Theoretical Limits to Practical Feasibility through Quantization
• Authors: Holger Boche, Vit Fojtik, Adalbert Fono, Gitta Kutyniok,
• Abstract summary: We study computability in the deep learning framework from two perspectives. We show algorithmic limitations in training deep neural networks even in cases where the underlying problem is well-behaved. Finally, we show that in quantized versions of classification and deep network training, computability restrictions do not arise or can be overcome to a certain degree.
• Score: 53.15874572081944
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The unwavering success of deep learning in the past decade led to the increasing prevalence of deep learning methods in various application fields. However, the downsides of deep learning, most prominently its lack of trustworthiness, may not be compatible with safety-critical or high-responsibility applications requiring stricter performance guarantees. Recently, several instances of deep learning applications have been shown to be subject to theoretical limitations of computability, undermining the feasibility of performance guarantees when employed on real-world computers. We extend the findings by studying computability in the deep learning framework from two perspectives: From an application viewpoint in the context of classification problems and a general limitation viewpoint in the context of training neural networks. In particular, we show restrictions on the algorithmic solvability of classification problems that also render the algorithmic detection of failure in computations in a general setting infeasible. Subsequently, we prove algorithmic limitations in training deep neural networks even in cases where the underlying problem is well-behaved. Finally, we end with a positive observation, showing that in quantized versions of classification and deep network training, computability restrictions do not arise or can be overcome to a certain degree.

Related papers

• The Boundaries of Verifiable Accuracy, Robustness, and Generalisation in Deep Learning [71.14237199051276]
  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)
• Neural Fields with Hard Constraints of Arbitrary Differential Order [61.49418682745144]
  We develop a series of approaches for enforcing hard constraints on neural fields. The constraints can be specified as a linear operator applied to the neural field and its derivatives. Our approaches are demonstrated in a wide range of real-world applications.
  arXiv  Detail & Related papers  (2023-06-15T08:33:52Z)
• Generalized Uncertainty of Deep Neural Networks: Taxonomy and Applications [1.9671123873378717]
  We show that the uncertainty of deep neural networks is not only important in a sense of interpretability and transparency, but also crucial in further advancing their performance. We will generalize the definition of the uncertainty of deep neural networks to any number or vector that is associated with an input or an input-label pair, and catalog existing methods on mining'' such uncertainty from a deep model.
  arXiv  Detail & Related papers  (2023-02-02T22:02:33Z)
• Adversarial Robustness with Semi-Infinite Constrained Learning [177.42714838799924]
  Deep learning to inputs perturbations has raised serious questions about its use in safety-critical domains. We propose a hybrid Langevin Monte Carlo training approach to mitigate this issue. We show that our approach can mitigate the trade-off between state-of-the-art performance and robust robustness.
  arXiv  Detail & Related papers  (2021-10-29T13:30:42Z)
• Provable Regret Bounds for Deep Online Learning and Control [77.77295247296041]
  We show that any loss functions can be adapted to optimize the parameters of a neural network such that it competes with the best net in hindsight. As an application of these results in the online setting, we obtain provable bounds for online control controllers.
  arXiv  Detail & Related papers  (2021-10-15T02:13:48Z)
• Sparse Deep Learning: A New Framework Immune to Local Traps and Miscalibration [12.05471394131891]
  We provide a new framework for sparse deep learning, which has the above issues addressed in a coherent way. We lay down a theoretical foundation for sparse deep learning and propose prior annealing algorithms for learning sparse neural networks.
  arXiv  Detail & Related papers  (2021-10-01T21:16:34Z)
• Constrained Learning with Non-Convex Losses [119.8736858597118]
  Though learning has become a core technology of modern information processing, there is now ample evidence that it can lead to biased, unsafe, and prejudiced solutions.
  arXiv  Detail & Related papers  (2021-03-08T23:10:33Z)
• Learning for Integer-Constrained Optimization through Neural Networks with Limited Training [28.588195947764188]
  We introduce a symmetric and decomposed neural network structure, which is fully interpretable in terms of the functionality of its constituent components. By taking advantage of the underlying pattern of the integer constraint, the introduced neural network offers superior generalization performance with limited training. We show that the introduced decomposed approach can be further extended to semi-decomposed frameworks.
  arXiv  Detail & Related papers  (2020-11-10T21:17:07Z)
• Optimization and Generalization of Regularization-Based Continual Learning: a Loss Approximation Viewpoint [35.5156045701898]
  We provide a novel viewpoint of regularization-based continual learning by formulating it as a second-order Taylor approximation of the loss function of each task. Based on this viewpoint, we study the optimization aspects (i.e., convergence) as well as generalization properties (i.e., finite-sample guarantees) of regularization-based continual learning.
  arXiv  Detail & Related papers  (2020-06-19T06:08:40Z)

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.