Path Regularization: A Convexity and Sparsity Inducing Regularization for Parallel ReLU Networks

Summary

The authors present a theoretical analysis of optimization for path-regularized parallel ReLU networks. They demonstrate how to represent this non-convex problem as a regularized convex problem. While convex problems in general admit polynomial time solutions, the size of this convex problem is exponential in the rank $r$ of the data matrix. However, its size is polynomial in the data dimension $d$ and number of examples $n$ if those are treated as being independent of the rank $r$. The authors then establish approximation guarantees when operating on a rank $r$ approximation of a (potentially) full rank data matrix. For matrices with quickly decaying singular values, this allows the convex problem to be effeciently solved at a decent accuracy. They then run experiments on a toy task and image classification datasets to demonstrate that their method can outperform gradient descent and other optimizers in both final performance and time.

Strengths

- Theoretical understanding of neural networks is an important and impactful topic. - Paper is well written and introduces novel analysis. - Emperical results support theory.

Weaknesses

- Although the authors claim that their solution is polynomial time in both data dimension $d$ and number of examples $n$, it is exponential in the rank $r$ of the data matrix. While they prove that using a low rank approxiation will approximate the optimal solution well if the low rank approximation is good, their approximation bound will be poor if the data matrix is inherently high dimensional. So their solution still has exponential complexity in the "implicit" dimensionality of the inputs. Typos: - line 166: I see $RR$ in one of the expressions. Should this be $\sqrt{m_1m_2}R$ instead?

Questions

- How does the algorithm scale to larger problem sizes?

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

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

3 good

Contribution

3 good

Limitations

Yes

Summary

This paper studies the problem of training parallel networks with three-layer subnetworks under path regularization. It is shown that the non-convex optimization problem of minimizing the regularized loss can be cast as a convex optimization problem, which can be solved efficiently.

Strengths

1. The study of parallel networks is interesting. 2. Finding efficient algorithms for training neural networks is important and the proposed solution seems novel and performs well.

Weaknesses

1. In all the experiments the networks have $m_2=1$? what happened if $m_2$ is large, does it affect the training time?

Questions

See "Weaknesses"

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

3 good

Presentation

3 good

Contribution

3 good

Limitations

See "Weaknesses"

Summary

The paper shows how parallel ReLU networks can be trained to approximate optimality in polynomial time by convex programming when employing a path-regularization (rather than weight decay or other regularization of the network weight parameters) and a low-rank approximation of the data matrix. Some numerical experiments demonstrate practical benefits of the approach. -- update: I have read and acknowledged all other reviews and the authors rebuttals, see discussion. --

Strengths

Positive and practical results on optimal training of neural networks are quite rare, so I see this work as an interesting contribution. The numerical experiments demonstrate that the proposed approach can work in practice as well (however, it should be mentioned in the main paper, not only as an aside in the supplementary document (Sect. A.1, ll. 491ff), that the image classification experiments did not use all hyperplane arrangements for the convex program, but only a small sampled subset, thus deviating from the theoretical model to achieve practical speed-up).

Weaknesses

I have read this paper (or a precursor preprint) a year or two ago, so the results aren't exactly new anymore, which may be a weakness. The techniques (to obtain a convex program solvable in poly-time) are very similar to earlier works on two-layer ReLU networks, which may make this work seem somewhat derivative; I don't think this is necessarily a weakness, but it may open a way to significantly shorten the very technical parts and referring to the earlier work (by Tolga&Pilanci) instead. In the (main) paper, Tables and Figures are not placed near where they are mentioned/discussed in the text body, which should be fixed as it breaks the flow or reading in a distracting way. Some statements are repetitive and should be consolidated accordingly (e.g., "Remark 1" essentially repeats what was mentioned at the end of the first paragraph of Sect. 2, and the sentence in lines 86-87 repeats Footnote 1). Throughout, there are various small typos and missing words (short ones like "of") Finally, 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 exceeds that of the supposed main paper. This paper is only a partial exception -- the main paper provides enough information and details to follow the ideas, but all (admittedly very technical) proofs can then be found in the very long Appendix (supplementary document) along with some further additional information. Thus, it may be considered a weakness of the paper to have such a long Appendix, because this format bears the danger of the formally most important parts of the work (proofs; algorithm details and specific setups) 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 well in order, especially since it is so reminiscent of the earlier work on two-layer ReLU networks, which I had read carefully at some point. 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

Is it correct that the entries in the last column of Table 2 are all identical? Also, in Remark 2, l. 166, is it meant to say "RR" in the nominator?

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

3 good

Contribution

3 good

Limitations

Limitations have been adequately addresses, as far as I can tell.

Summary

This study considers training the parallelized multi-layer neural networks with path-wise norm regularization. Through the duality argument, the authors reduce the regularized empirical minimization problem, which is highly non-convex, to the convex programming problem. They show that when the data matrix has a small rank, the solving time will only be polynomial time. In general, in cases where the data matrix does not shrinkage, an approximation method that also runs in polynomial time is proposed through the matrix approximation technique. Numerical experiments are conducted to show the effectiveness of the proposed regularization and the solving algorithm.

Strengths

- The theoretical results seem to be solid and clearly written. - The reduction of the neural network training problem beyond two-layer to the convex programming is a novel, and the proposed algorithm seems to work effectively in the experiment section.

Weaknesses

The exhibited results are interesting from the theoretical view, but I think there are restrictive from the practical view. - Whereas the reduction to the convex programming is interesting, the obtained time complexity $O(d^3m_1^3m_2^32^{3(m_1+1)m_2}n^{3(m_1+1)r})$ will be extremely large in the practical models even in it is polynomial. Indeed, the numerical experiment seems to end with narrow networks. - Apart from the above concern, although the approximate algorithm is provided, obtaining the low-rank approximation of the data matrix requires much time when using a large dataset (especially to which deep learning is applied).

Questions

- Do you consider that the time complexity obtained in Proposition 2 is just a theoretical one, and it will be faster in practice? - I have several concerns about the parameter dependence of the obtained time complexity in Proposition 2. First, does it not depend on the $K$, the number of parallelized networks? Second, the time complexity exhibited in Corollary 1 seems to be inconsistent with Proposition 2. When we apply Corollary 1 to the 3-layer networks, the term two will be powered by $3(m_1+m_2)$, but it becomes $3(m_1+1)m_2$ in Proposition 2. Which is correct?

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

3 good

Contribution

3 good

Limitations

N/A

Summary

This work studies the training of 3-layer parallel ReLU networks with path regularization. Specifically, the authors show that minimizing the non-convex learning objective with an \ell_2 pathwise weight decay is equivalent to a convex program that can be solved optimally in polynomial-time complexity (Proposition 1), except when the data matrix is full-rank. The authors also propose a more efficient polynomial-time algorithm (Theorem 2) for arbitrary data by using a local approximation of the data matrix on the training objective. The paper also provides numerous empirical results on toy and real data to support the theoretical results.

Strengths

+ This work provides a convex duality for parallel ReLU networks with path regularization. + An optimal, polynomial-time algorithm for arbitrary data, including full-rank data.

Weaknesses

- This work is basically an extension of techniques and results in [17] to a slightly different regularization, so there is a concern about novelty. - The performance of the proposed algorithm does not improve others on Fashion-MNIST, and why is the gain much higher in CIFAR-10, which is a more challenging dataset?

Questions

1. The authors claim that “we proved the polynomial-time trainability of deep ReLU networks without requiring any impractical assumptions unlike [17, 29].” Can the authors compare and contrast the assumptions made in this and those works? 2. How practical is the algorithm in Theorem 2? I can’t tell from Proposition 1 what closed-form mapping is and how one constructs optimal network weights from it. Can the authors clarify? 3. In Table 1, the bounds are exactly the same between this work and [29] for 2-layer networks. Why? 4. How does low-rank approximation error populate to the optimality?

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

3 good

Presentation

3 good

Contribution

2 fair

Limitations

Above.