Training Fully Connected Neural Networks is $\exists\mathbb{R}$-Complete
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909145389596672 |
|---|---|
| author | Bertschinger, Daniel Hertrich, Christoph Jungeblut, Paul Miltzow, Tillmann Weber, Simon |
| author_facet | Bertschinger, Daniel Hertrich, Christoph Jungeblut, Paul Miltzow, Tillmann Weber, Simon |
| contents | We consider the problem of finding weights and biases for a two-layer fully connected neural network to fit a given set of data points as well as possible, also known as EmpiricalRiskMinimization. Our main result is that the associated decision problem is $\exists\mathbb{R}$-complete, that is, polynomial-time equivalent to determining whether a multivariate polynomial with integer coefficients has any real roots. Furthermore, we prove that algebraic numbers of arbitrarily large degree are required as weights to be able to train some instances to optimality, even if all data points are rational. Our result already applies to fully connected instances with two inputs, two outputs, and one hidden layer of ReLU neurons. Thereby, we strengthen a result by Abrahamsen, Kleist and Miltzow [NeurIPS 2021]. A consequence of this is that a combinatorial search algorithm like the one by Arora, Basu, Mianjy and Mukherjee [ICLR 2018] is impossible for networks with more than one output dimension, unless $\mathsf{NP}=\exists\mathbb{R}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2204_01368 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Training Fully Connected Neural Networks is $\exists\mathbb{R}$-Complete Bertschinger, Daniel Hertrich, Christoph Jungeblut, Paul Miltzow, Tillmann Weber, Simon Computational Complexity Machine Learning Neural and Evolutionary Computing We consider the problem of finding weights and biases for a two-layer fully connected neural network to fit a given set of data points as well as possible, also known as EmpiricalRiskMinimization. Our main result is that the associated decision problem is $\exists\mathbb{R}$-complete, that is, polynomial-time equivalent to determining whether a multivariate polynomial with integer coefficients has any real roots. Furthermore, we prove that algebraic numbers of arbitrarily large degree are required as weights to be able to train some instances to optimality, even if all data points are rational. Our result already applies to fully connected instances with two inputs, two outputs, and one hidden layer of ReLU neurons. Thereby, we strengthen a result by Abrahamsen, Kleist and Miltzow [NeurIPS 2021]. A consequence of this is that a combinatorial search algorithm like the one by Arora, Basu, Mianjy and Mukherjee [ICLR 2018] is impossible for networks with more than one output dimension, unless $\mathsf{NP}=\exists\mathbb{R}$. |
| title | Training Fully Connected Neural Networks is $\exists\mathbb{R}$-Complete |
| topic | Computational Complexity Machine Learning Neural and Evolutionary Computing |
| url | https://arxiv.org/abs/2204.01368 |