Training Fully Connected Neural Networks is $\exists\mathbb{R}$-Complete

Summary

The paper investigates the algorithmic complexity of training fully connected ReLU neural networks. It is shown that perfectly fitting two-dimensional data by even a one-hidden layer network with two output neurons is $\exists\mathbb{R}$-complete, namely it is as hard as finding the roots of a multivariate polynomial with integer coefficients. The paper is well-composed and easy to read, and the findings are interesting even though they are somewhat limited as elaborated in the strengths/weaknesses sections. Overall, my opinion of this paper is positive and I believe it merits acceptance.

Strengths

- Very well-written and easy to follow. It is evident that the authors have put a lot of effort into composing this paper and thoroughly discussing its results, impact and drawbacks. - The results in this paper are interesting and may suggest that training neural networks is strictly harder (assuming a somewhat acceptable complexity theory hypothesis) than problem in NP. This indicates that certain practices make the worst-case complexity of real-world problems much harder, but the problems are nevertheless solved efficiently. As motivation for future work, it is interesting to study how changing these practices might affect the efficacy in which neural networks are being trained.

Weaknesses

- The paper studies the problem of perfectly fitting the data, while in practice we are interested in getting the training error to become sufficiently small. - The paper assumes that the learning problem requires classifying at least 13 classes that are two dimensional and are not linearly dependent. While I agree with the authors' claim that the gap between 3 and 13 classes seems immaterial, I still find the two-dimensional output requirement very limiting. This is due to the fact that we can always re-encode the target classes in a different manner which circumvents $\exists\mathbb{R}$-completeness. E.g., we can just encode the classes using the naturals $1,2,\ldots$. The authors point out that a common practice is to use $k$-dimensional standard unit vectors to encode $k$ different classes which may still imply $\exists\mathbb{R}$-completeness, but the study of this is left to future work. To summarize this weakness, the paper cannot currently rule out the possibility that common practices circumvent $\exists\mathbb{R}$-completeness entirely.

Questions

- Line 84: Why do you assume that $\gamma$ is rational and not real? - Line 109: The theorem statement says that the problem is hard "even" if certain conditions are met. I find this statement very confusing. It sounds like you can replace "There are exactly two" with "There are only two" to make it clearer. Similarly, I would change "The number of hidden neurons is a constant fraction of the number of data points." with "The number of hidden neurons is only a constant fraction of the number of data points.". Lastly, it seems like the last two items are a necessary condition rather than an "even" statement. Specifically, solving for $\gamma=0$ is at least as hard as approximating to some other $\gamma>0$, so it doesn't make sense to use state in line 109 that this holds "even if". Likewise, the assumption of using a ReLU activation is a necessary condition in the analysis from what I understand so this item also does not belong following an "even if" statement. Am I missing something? If so, please clarify the theorem statement. - Paragraph starting with line 226: It is mentioned that we can add inconsistent data points to modify the value of $\gamma$. Do you mean that this allows us to show a reduction from the $\gamma=0$ case to a general $\gamma>0$ case, and thus the two problems are equivalent? Please clarify.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

2 fair

Limitations

Yes

Summary

The paper proves ER-completeness of training (empirical risk minimization) a fully connected two-layer ReLU network with two inputs and two outputs. The result contributes to the understanding of theoretical complexity of neural network training at an important, fundamental level. The authors also did a good job explaining the intricacies of the achieved type of hardness result with respect to implications and applicability in the broader neural network training context. The true main, and (unavoidably) very technical part of the paper, i.e., the actual proofs, are delegated to a "supplementary material" document that is twice as long as the "main" paper. -- update: I have read and acknowledged all other reviews and the authors rebuttals, see discussion. --

Strengths

The result of this paper constitutes and important and fundamental contribution to the understanding of the complexity of training neural networks (to global optimality). Besides the main result itself, the paper's strength lie in its clarity of presentation and the discussion of context, limitations and implications.

Weaknesses

It appears to have become common practice to submit papers to NeurIPS (and ICML) whose actual, main content is put in a separate "Supplementary Material" document whose length far exceeds that of the supposed main paper. Unfortunately, this paper is no exception. I consider this a weakness because this format bears the danger of the formally most important parts of the work not being reviewed thoroughly due to the short review period and high review load of reviewers at these conferences. I cannot exclude myself from this -- I simply did not have the time to rigorously check all the details in the long supplementary document, and therefore cannot give a definitive answer regarding the proofs' correctness beyond "believing" everything appears to be in order. In this regard, I cannot help but wonder if a full journal paper would not be the better way to publish results that simply do not fit into the 9-page limit...

Questions

It seems that, while generally helpful, the proof outline in the "main" paper does not quite bring across why the reductions works. It is well-written and enables one to grasp the general concepts (gadgets etc) used for the reduction, but perhaps the authors could add some clarification with respect to the "crucial" step, i.e., why their encoding can be shown to answer the ETR instance if and only if the Train-F2NN problem can be fitted with 0 loss?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

4 excellent

Limitations

The authors adequately commented on applicability/meaning of their result and, thus, its inherent limitations.

Summary

This paper shows that training a neural network with two input neurons and two output neurons is ER complete where ER stands for the existential theory of the reals.

Strengths

A new idea (reduction) to prove hardness result. The paper is generally well written and provides a good cover of the (dense) related work.

Weaknesses

In the end, the results in the paper point more to the limitation of current computational hardness results than to the limitation of deep learning. The task of finding the exact minimizer and the inability to prove hardness results for the approximate case diminish the relevance of the results to modern ML. Personally, I'm not a fan of ER but I think the reductions could find uses elsewhere. The paper is somewhere between "accept" to "weak accept" and I'm willing to raise the score if the authors provide convincing responses. There are several issues with the writing such as: 1) Definition 2 is very cumbersome. Consider shortening it as it done in the Blum Rivest paper. 2) "However, when using gradient descent we usually do not get any guarantees on the quality of the obtained solutions or on the time it takes to compute them [30]". This is misleading as there are many (proven) results about GD finding the global minimum. [30] is one example one GD does not work well, but there are many other results for which it does work well such as "Globally optimal gradient descent for a convnet with gaussian inputs". 3) "Thus it would be very desirable to use other methods, like SAT- or mixed-integer programming solvers that are reliable and widely used in practice for many NP-complete problems." What does "reliably" mean here? I'm sure that there are bad examples for these heuristics just as there are for GD. 4) The elephant in the room which the authors largely ignore is the huge success of gradient-based optimization in training neural networks with tens of millions of neurons. 5) Definition 1 is strange. Consider using the standard matrix notation for neural networks. 6) There seems to be a redundancy between the average case analysis paragraph and the "Let us stress" paragraph. 7) I would put still more effort in explaining the ideas behind the main reduction and exemplifying it with a small example.

Questions

What happens to the hardness result if we only consider neural networks with limited precision? Say any weight or bias is represented by at most 10 bits?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

I think one of the biggest issues is not addressing the success of gradient-based optimization in the paper. The authors might want to talk more about improper learning which are typically used and make the learning task easier.

Summary

This paper strengthens a result by Abrahamsen, Kleist and Miltzow [Neurips 21] by showing that empirical minimization problem of two-layer neural network is \exist R-hard. They further show that arbitrary algebraic number is required as optimal weights even with rational data points. The example include a ReLU neural network with two inputs and two outputs.

Strengths

- The paper is well-written and the related works have been discussed in great details. - The reduction of training two-layer neural network to ETR-INV is novel. - The construction of inversion gadget in appendix B.3.4 is quite interesting to learn.

Weaknesses

- Definition 1 which defines neural networks from a directed acyclic graph seems to be redundant as the paper is devoted to analyze a two-layer fully connected neural networks, whose structure is much simpler. - The structure of the paper can be improved. The majority of the papers is to introduce definitions and discussing related works, while the main proof idea only starts at page 7. It would be better if the authors can elaborate on the proof idea. From my perspective, the main theoretical contribution in this paper is the reduction of training two-layer neural network to ETR-INV, while the details how they are achieved are largely left in the appendix.

Questions

See weakness.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

Yes.

Repsonse to authors

I keep my score and support acceptance. I encourage the authors to elaborate much more on the proof ideas.

Response to authors

Thanks for the response. I would like to keep the score.

Post-rebuttal response

Dear authors, Thank you very much for your detailed answer to each of my questions. I find your answers satisfying and wish you good luck in the future.