Computability of Classification and Deep Learning: From Theoretical Limits to Practical Feasibility through Quantization
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916353749811200 |
|---|---|
| author | Boche, Holger Fojtik, Vit Fono, Adalbert Kutyniok, Gitta |
| author_facet | Boche, Holger Fojtik, Vit Fono, Adalbert Kutyniok, Gitta |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_06212 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Computability of Classification and Deep Learning: From Theoretical Limits to Practical Feasibility through Quantization Boche, Holger Fojtik, Vit Fono, Adalbert Kutyniok, Gitta Machine Learning Computational Complexity 68T07, 68T05, 03D80, 65D15 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. |
| title | Computability of Classification and Deep Learning: From Theoretical Limits to Practical Feasibility through Quantization |
| topic | Machine Learning Computational Complexity 68T07, 68T05, 03D80, 65D15 |
| url | https://arxiv.org/abs/2408.06212 |