New Complexity-Theoretic Frontiers of Tractability for Neural Network Training

Summary

The paper studies the neural network training problem for ReLU and linear networks. They show new settings where the problem can be solved in polynomial time. They provide two main contributions: - For ReLU networks, they give a polynomial-time algorithm for training constant-size networks where the out-degree of all hidden neurons is $1$. This extends similar previous results for depth-$2$ networks. They observe that every constant-size network can be transformed into a network with the above structure. - For linear networks, they identify a condition, called untangling, that allows for efficient learning if the untangling is given. Finding an untangling is NP-hard in general, but if the network has a constant number of hidden neurons or a constant treewidth, then it can be found in linear time.

Strengths

The neural network training problem is a natural question that has been studied in several prior works. This paper makes a further step towards understanding when this problem can be solved efficiently, for both linear and ReLU networks. Also, the paper is well-written.

Weaknesses

My comments are regarding the result on ReLU networks: - The result requires out-degree of exactly $1$ for all hidden neurons. It is indeed more general than the results of Arora et al. 2018 and Boob et al. 2022, but the family of networks covered by the new result and not by the previous ones is somewhat restricted. The authors show that every constant-size network can be transformed into a network with the above structure, but it is not clear to me what the implications of the ability to solve the problem for the transformed network are. It would be helpful if the authors elaborated further on the motivation for this transformation. - I am trying to understand what are the main technical differences between the current result and Arora et al. 2018, and what are the main non-trivial steps. I would be happy if the authors elaborate more on this issue. Below I provide some comments in this respect: - Regarding Lemmas 1 and 2: The idea of “pushing the weights backward” in ReLU networks with out-degree $1$ of each neuron (i.e., making all weights in {-1,0,1} in all layers except for the first layer) is not new. It was done, e.g., in [1]. - Regarding Lemma 3: The authors compare it to Arora et al. in the Remark, and claim that both the bound on the number of partitions and the efficient enumeration method are essentially new. I actually believe that the $|D|^{O(n)}$ bound on the number of partitions follows immediately from the Sauer–Shelah lemma (do you agree?). I don’t know whether an efficient enumeration algorithm was previously known. Is it the main technical contribution in this result? - Regarding Lemma 4: I believe that the Sauer–Shelah lemma can give a tighter bound here (namely, $|D|^{O(n \cdot \text{poly}(x))}$). Again, I don’t know regarding efficient enumeration. - Given Lemmas 1-4, the proof of Theorem 5 becomes similar to the result from Arora et al., right? - The result in Section 5, namely, transforming networks to larger ones with out-degree $1$, is a trick that was also used in prior works. As far as I understand, this is exactly Remark 2.2. from [1]. - Typo in line 215: should be $a_{u,w}^*$. [1] Maass, Wolfgang. "Bounds for the computational power and learning complexity of analog neural nets." Proceedings of the twenty-fifth annual ACM symposium on Theory of computing. 1993.

Questions

See the “weaknesses” section.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, 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

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

The authors discussed the limitations.

Summary

This paper studies the computational complexity of empirical risk minimization (ERM) for neural networks, that is, given an architecture and training data points, find weights and biases of a global minimum of the training error. The problem is well-known to be NP-/ER-/W[1]-hard already in very easy special cases. This paper identifies a bunch of cases in which it can still be solved in polynomial time, namely in each of the following cases: - for ReLU networks with all hidden neurons having out-degree one, if the size of the NN is regarded as a fixed constant, - for an improper ReLU learning setting, leading essentially to the case of the first bullet point by blowing up the architecture, - for linearly activated NNs if they fulfill a certain structural property. Moreover, the authors analyze the computational complexity of determining whether a linearly activated NN satisfies the structural property mentioned in the third bullet point.

Strengths

- Given the significance and hardness of the problem, finding tractable special cases is a very important contribution to the theory of machine learning. This paper provides a decent starting point (building upon Arora et al. (2018)) and hopefully initiates further research towards this goal. - The paper is mathematically very well-written. It even cleans up with some vagueness in previous work (see Remark after Lem. 3). - The paper also is very precise in surveying the previous literature on computational complexity of ERM for NNs.

Weaknesses

- The obtained algorithms are only of theoretical interest because (i) the tractable special cases are rather unrealistic, (ii) the running times have still high dependencies on "fixed" constants, and (iii) this work focusses purely on minimizing the training error and neglects learning / generalization. So the paper should really be seen as fundamental theoretical research rather than pushing the frontiers of what we can do in practice. As such, I think it is of significant value. Apart from this, I have many minor comments as below. None of them is a reason to downvote for me, but I urge the authors to carefully work on them for the next version: - My impression is that the abstract is not very informative. Instead of spending too much effort on motivating the results there (see also my next comment), it would be better to be more precise of what this paper actually proves (why not simply state the main results?). - While I believe the paper makes important contributions (as outlined above), I am quite unhappy with the way the results are pitched, e.g. already in the abstract, and in lines 17-20, and other places where the authors claim that so little is known about the complexity of NN training. Yes, it is true that not many positive results have been achieved for pure empirical risk minimization, but this is for a good reason: the problem simply IS really hard in the worst-case, and this has been studied thoroughly. While I do agree that finding tractable special cases is an important research contribution, I believe that this will always only be possible for very special cases and therefore disagree with staging this as such a "huge" gap in the literature. - a recent preprint you might not be aware of is: Froese, Hertrich: "Training Neural Networks is NP-Hard in Fixed Dimension" (https://arxiv.org/abs/2303.17045). This includes a multitude of new stronger hardness results for both ReLU (and linear threshold) networks. I think you should cite this in line with other negative complexity results you already cite, like (Arora et al., 2018; Abrahamsen et al., 2021; Goel et al., 2021; Froese et al., 2022; Bertschinger et al., 2022). In particular in line 52, for the constant n case, the Bertschinger et al. (2022) result relies on multi-dimensional outputs. The new preprint suggested above shows that NP-hardness can already be achived with a single-dimensional output (and still only 2-dimensional input). - line 65: "it is not difficult to show that LIN-NNT is poly-time tractable for any network of bounded size": why is this the case? can you please elaborate? And does it depend on whether the NNs are fully-connected or not? - lines 68-69: are you referring to arbitrary n but constant w here? If so, please make the arbitrary dependence on n more explicit. - lines 90 and beyond: are you still talking about fixed size? - line 278: "save" -> "except"?? (or I completely misunderstand this sentence) - line 282: the ellipsoid method is NOT polynomial in the number of variables and constraints. In fact, its time complexity depends on the bit-length of the encoding of the input. It is what people call "weakly polynomial" and there is no strongly polynomial time algorithm known, even for the special case of linear programming. This also affects the running time of the overall algorithm. It should be something like $|D|^{\mathcal{O}(nw2^w)}\cdot\mathrm{poly}(L)$, where $L$ is the bit-length of the encoding of all data points. Please fix this everywhere in the paper where you state running times involving a quadratic program (for example, this also applies to Thm. 12). - line 297: in addition to the cited thesis, you should probably also cite the paper the thesis is based on (Hertrich, C., Basu, A., Di Summa, M., & Skutella, M. Towards lower bounds on the depth of ReLU neural networks. NeurIPS 2021.) and additionally the following paper making significant progress towards proving the conjecture: Haase, C. A., Hertrich, C., & Loho, G. Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes. ICLR 2023. - line 305: point (2): "polynomial-time training" is very misleading here, this is only true if the architecture size is regarded as a fixed constant! - general comment about Section 5: what you are doing here is known as improper learning in the learning theory community. You should probably mention the term and compare to the respective literature. In particular, while you prove that your blow-up procedure does not increase the training error, such a move might heavily increase the generalization error of empirical risk minimization in learning settings. You should mention this! - line 348: Are you a "such that" missing at the end of this line? - line 379: d3 -> d_3

Questions

No particular questions, but I invite the authors to reply to any of the comments I've made if they disagree.

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

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

All statements are mathematically rigorous and all assumptions properly stated. The authors should mention that the blow-up in Section 5 might heavily increase the generalization error in learning settings, see my respective comment above. The authors should point out more clearly that the purpose of the provided algorithms is purely theoretical, see my first point in "weaknesses".

Summary

The paper studies algorithms for exact minimization of quadratic loss over ReLU and linear neural networks when the total number of neurons is a fixed constant. The results can be divided into two parts: * A polynomial time algorithm for a fixed size ReLU/linear network, when it has the following structure: 1) One layer of neurons with arbitrary edges between inputs and those neurons. 2) A tree of neurons (i.e., every neuron has out-degree one) on top of that. More precisely, the algorithm runs in time $|D|^{O(nw 2^w)}$, where $|D|$ is size of the dataset, $n$ number of inputs, and $w$ total number of hidden and output neurons. * A polynomial time algorithm for a (possibly large) linear network whenever all hidden neurons can be collapsed (like in a graph minor) onto inputs and outputs such that the resulting bipartite graph is equal to the connectivity graph between inputs and outputs. So, it's some sort of condition that says that the graph has a "simple" connectivity structure. This pattern of connectivity needs to be known to the algorithm, the authors prove that it is in general NP-hard to find it. In both of these settings polynomial-time algorithms are already known for the most natural subcases (for example, one fully connected layer in the ReLU case).

Strengths

* The topic is interesting and relevant. As the authors point out, we know surprisingly little even about simple cases of this basic problem. * The paper is clearly written, including the context and exhaustive discussion of related work. It was a pleasure to read. * A lot of attention was paid to careful and correct explanations in the proofs.

Weaknesses

It is not clear how many interesting new cases these theorems cover. I did not feel the results and proofs were particularly surprising. For example, the ReLU proof quite heavily (but skillfully) relies on previously used enumeration of hyperplane partitions. And the tree structure in the ReLU theorem does not look very relevant to practical architectures.

Questions

Line numbers are for the extended version from the supplement. * I admit this is a matter of opinion, but the title seems a bit over the top. I would suggest to make it more informative. * remark after lemma 3, I think it is great that you worked out the details of this enumeration problem. But as a point of feedback, parts of this remark read to me as unnecessarily hostile. * line 372, typo "we the set" * Corollary 6, technically you never defined "MIXED-NNT". * proof of Theorem 12, you call inputs/outputs $x$ and $y$, but then you switch to $n$ and $o$. also in paragraph starting in line 547, I would double-check the transposition symbols. * proof of Theorem 13, I found it frustrating that $D_i$ and $D_j$ denote very different objects in this proof.

Rating

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

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

4 excellent

Presentation

4 excellent

Contribution

2 fair

Limitations

see above

Summary

This paper studies the computational complexity of training linear and ReLU neural networks. Under assumptions such as the squared loss and the out-degree of every hidden neuron being exactly one, the authors prove that there exists an algorithm such that the global optimal solution can be computed in polynomial time for the linear and ReLU networks when the input dimension and the number of hidden neurons are fixed. To better understand the tractability of training linear networks, the idea of untangling is proposed and used to develop the existence of a polynomial-time algorithm for training linear networks. Although deciding whether a given architecture has an untangling is NP-hard in general, the authors prove that the complexity of determining this property for linear networks is linear time. They also provide a complexity result for computing an untangling of an architecture of bounded treewidth.

Strengths

The novelty of this paper is clear. First, it ensures the existence of a training algorithm for linear and ReLU networks that achieves global optimal solutions in polynomial time under a different assumption compared to previous work. Second, the idea of untangling is proposed as a new assumption for studying these networks. These contributions could open up a new angle for studying the training complexity of ReLU and linear networks. The paper is well-written, and I enjoy reading the paper.

Weaknesses

In my view, the assumptions are the main weaknesses of this work. The out-degree being 1 and the untangling of architecture are unrealistic assumptions. Deep neural network models in practice do not satisfy these assumptions. Second, finding the global optimal solution seems to be unnecessary. Usually, we would avoid getting to the global optimal solution because of overfitting. Third, when a machine problem is given, we only have the dataset so the number of hidden neurons $w$ is unknown. Based on these reasons, it seems hard to apply the results in this paper to applications.

Questions

1. The squared loss is assumed in this work. Would it be possible to extend it to convex loss functions? 2. Usually, there are symmetries in the dataset. Would it be possible to leverage the symmetries or redundancies in the data and reduce the bounds? Would it be possible to apply that to drop some strong assumptions on the architecture and still maintain the polynomial complexity? 3. Do you need the number of bits of the input in the bounds? What computational models are you assuming?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, 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

4 excellent

Presentation

3 good

Contribution

2 fair

Limitations

The authors point out two questions at the end as possible future directions. However, due to the unrealistic assumptions mentioned above, there are strong limitations to applying the results to applications. Although this is a purely theoretical paper, I still think it would be a good idea to describe possible workarounds of the assumptions and how the current results could be impactful to machine learning problems.

Summary

This paper investigates the theoretical complexity of finding the global optimal solution of ReLU networks and linear networks. Specifically, it first considers a specially designed neural network, each hidden neuron of which has only one outgoing edge. By using the homogeneity of the ReLU function, it reparameterizes this network such that all the weights (except the first layer ones) are either -1 or +1 (i.e., moves the absolute values into the first layer weights). In this way, it shows that it is possible to find the global optimal by enumerating the partitions of the data space, with time complexity that is polynomial in the dataset size (but not polynomial in network size). It also shows that a normal fully-connected neural network can be “blown up” to one with the above special design (out-degree = 1 for each neuron), by replicating hidden neurons that have multiple out-going edges.

Strengths

The obtained time complexity of finding the global optimal is polynomial in the dataset size. This paper handles multi-layer ReLU/linear neural networks, while prior works only obtain similar results on one-hidden layer networks.

Weaknesses

The main trick of this paper is to consider those variables (e.g., network width, depth, input dimension etc) in which the time complexity is exponential or greater as constants, so that the time complexity can be *stated as* polynomial – in the remaining variable (i.e., dataset size). I don’t think this is a clever trick, as it does not solve the problem at all. Note that the complexity is far greater than polynomial (or even than exponential) in the other variables, for width $w$ it is $|D|^{w2^w}$, and for depth it is larger than $|D|^{2^{\lambda^l}}$. Given this large complexity in width and depth, the result of time complexity has little to no usefulness for practice. The paper only focuses on the time complexity, while ignoring the space complexity – memory costs. Note that the blowing up procedure requires much more space complexity, which is exponential in depth. Recall that a neural network without blowing-up only requires space which is linear in depth. This huge memory cost is a drawback of the analyzed training algorithm, and should be considered and analyzed.

Questions

No further questions

Rating

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

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

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

limitation is not discussed in the main text