Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors theoretically analyzed the dual of minimum norm optimization of over-parameterized deep neural networks. Specifically, they focused on deep neural networks with linear and ReLU activation functions, as well as parallel architectures where the output of each branch is a scalar. First, the authors considered the linear NNs and showed that the duality gap of general deep NN is non-zero, but for parallel NN with enough number of parallel branches, that would be zero. Next, they considered neural networks with ReLU activation functions and derived the duality gap for standard 3 layers neural networks. However, for an arbitrary deep parallel NN with ReLU activation, the duality gap would be zero if the L-th power of Frobenius norms of the weights is used as the regularizer.
main_review: The paper tackles an interesting and I believe important problem in NN optimization. Although the results are limited to minimum norm training of over-parametrized NN, the theoretical analysis may be useful in future development and analysis of deep NN optimizations. The paper has some shortcomings and some parts of the analysis were not clear, such as

1. As a theoretical paper, I expected to see more precise statements. For example, the paper claims that the duality gap is zero for parallel NN, but it seems that this is true only for NNs with enough number of parallel branches. 
2. Do the authors define parallel NNs such that the output of each branch is a scalar?
3. Some equations and derivations are not clear or obvious, e.g., proof of proposition 4, why equation (64) is equivalent to (16)? Why the power $L$ is dropped? Is deriving equation (22) similar to the ones in the references ? In the proof of proposition 6, it is not clear how the power $L$ (in equation (28), $\\|W_L\\|^L$) is dropped and the optimizaiton become over $\ell_2$ norm of the rows of $W_L$.
4. In the paragraph after equation (5), the authors claim that "The rescaling does not change the solution to (4).". Although by appropriate scaling $W_1$ and $W_2$ can still satisfy the constraint, but as the value of the objective function changes, the statement seems  inaccurate. Can the authors explain?
5. In section 4.1, Theorem 3, the authors assumed that data is rank 1. Does it simply imply that data samples are simply given by a scaling of a base vector, i.e., $x_i = s_i a$, for scalar $s_i$?
6. Theorem 5, is there any constraint on the number of branches or $m$?  
  
There are some minor typos in the equations, such as
- Section 2, first equation, $A_l=\Phi(W_lA_{l-1})$ should be $A_l=\Phi(A_{l-1}W_l)$. Similarly, for the second set of equations in that section.
- Is summation in equation (7) over $\\|W_i\\|^2$ rather than fixed $\\|W_L\\|$?
- First sentence section 4.2, "there is no duality gap for arbitrary deep ReLU networks", seems "parallel with large enough number of branches" should be added to make the statement accurate.

summary_of_the_review: The ideas and analysis of the paper to find the duality gap in training deep neural networks and when it achieves zero (at least for over-parametrized deep NNs) can be useful in understanding the optimization and training deep NNs and their properties. The paper adds non-trivial and solid results to the previous works in this domain, esp. works by Ergen and Pilanci. However, the writing and presentation of the paper falls short from the expectations.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The topic of this paper is the duality theorem for deep neural networks with linear and ReLU activation functions. In particular, this study shows that the strong duality (i.e., zero duality gap) does not hold for the standard deep models but it holds for parallel deep neural networks which are ensembles of networks with an appropriate regularization. These results are certainly useful because it enables global optimization of parallel deep models via the convex dual programs. 
main_review: [Contributions]

The analysis of the loss landscape of deep neural networks is an important topic to understand the global convergence property of optimization. Recently, the dual formulation of two-layer neural networks has been studied and the strong duality has been shown by the series of [Ergen and Pilanci] works and [Zhang et al. (2019)]. A natural question is to extend these results to deep models and this study answer the question. In particular, the strong duality theorem for the parallel deep ReLU model is quite interesting.


[Weaknesses]

I basically like the theoretical results in this paper, but I think the quality should be much improved and the paper is not ready for publication because of typos, ambiguity, and the lack of proof.  For the detail see below.

- I could not find the proof of the first part of Proposition 4 and 6. These are important statements that make the equivalence between (16) and (17), (28) and (29).
- Notations (Subsection 1.2): The notation $W_l \in \mathbb{R}^{m_1\times m_2}$ is somewhat confusing because $W_l$ represents the parameter of $l$-th layer in the main text.
- Eq. (1): $W_2$ → $w_2$. Moreover, there are many similar typos with the wrong uppercase and lowercase letters in the paper.
- Section2:
    - The formulation of standard networks: $W_l A_{l-1}$ → $A_{l-1}W_l$.
    - Inconsistent conditions: $m_l \geq \max\\{d,K\\}$, ($l \in [L-1]$), and $m_{L-1}=1$.
    - Lack of specification for the type of $A_{L-1}$ and $W_L$.
- Eq. (7): $\|W_L\|_F^2$ → $ \|  W_i \|_F^2$ ?
- Eq. (9): Notation $\forall$ is in the wong place ($\forall \| W_i \|_F$ → $\forall i \in [L-2]$).


[Additional references]

It is interesting that bi-dual problems become learning problems of mean field neural networks with TV-norm regularization and additional constraints (e.g., (41), (79), (97)). Hence, I think the strong duality theorem for parallel models is a reasonable consequence because parallel models are essentially neural networks in the (finite-width) mean field regime. There are many studies on the mean field regime. For instance, 

- A. Nitanda and T. Suzuki. Stochastic particle gradient descent for infinite ensembles. arXiv, 2017.
- S. Mei, A. Montanari, and P. M. Nguyen. A mean field view of the landscape of two-layer neural networks. PNAS, 2018.
- L. Chizat and F. Bach. On the global convergence of gradient descent for over-parameterized
models using optimal transport. NeurIPS, 2018.
- S. Mei, T. Misiakiewicz, and A. Montanari. Mean-field theory of two-layers neural networks:
dimension-free bounds and kernel limit. COLT, 2019.
- G. M. Rotskoff, S. Jelassi,  J. Bruna, and E. Vanden-Eijnden. Global convergence of neuron
birth-death dynamics. ICML, 2019.
- J. Sirignano and K. Spiliopoulos. Mean field analysis of neural networks: A central limit theorem. Stochastic Processes and their Applications, 2020.
- S. Akiyama and T. Suzuki. On learnability via gradient method for two-layer relu neural networks in teacher-student setting. ICML, 2021.
- L. Chizat. Sparse optimization on measures with over-parameterized gradient descent. Mathematical Programming, 2021.
- A. Nitanda, D. Wu, and T. Suzuki. Particle dual averaging: Optimization of mean field neural
networks with global convergence rate analysis. NeurIPS, 2021.
summary_of_the_review: The statements of main theorems are interesting and important, but the quality of the paper should be much improved. See the main review for detail.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, the author studies the duality gap in the neural network training problem. They show that in general (deep linear networks and three-layer ReLU networks), the duality gap is not zero. However, when restricting the parallel architecture, the authors show that the duality gap is indeed zero. 
main_review: Strength:
1. Analyzing the duality gap in neural network is an important research question both theoretically and empirically. 
2. The paper is well written and very good to follow.
3. Showing the duality gap is non-zero for three-layer ReLU networks is important. 

Weakness:
1. The author proves that the duality gap is zero when the neural network has parallel architecture, but I find there are little discussion behind this setting, i.e. why the parallel architecture can help closing the duality gap?
2. Is the parallel architecture setting practical? Has it been used empirically?
3. There is no numerically experiments supporting the theoretical result. 
4. In general, even when the duality gap is zero and we can solve the dual problem, how can we recover the primal solution? 
summary_of_the_review: I found the manuscript to be clearly written and technically sound. Although it has some weakness points, I think it still worth a publication.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: Using duality theory, this paper studies the duality gap between prime and dual optimization problems for deep linear (or relu) networks that have sequential or parallel structure. The major claim is that, assuming the networks is sufficiently over-parameterized, linear networks of depths at least 3 have nonzero duality gap, while strong duality holds for deep parallel networks. Similar conclusions are given for relu networks.
main_review: Strengths.

    1. The claims are very interesting.
    2. The message delivered in the introduction is clear.

Weakness.

    1. The mathematical presentation is confusing and full of typos. For example:
           1.1. In (1) its W_2, not w_2, this happens many times. 
           1.2. In the first formula of section 2, A_{\ell-1} is left-multiplied by W_l. It should be right-multiplied. This happens many times.           
           1.3. In the definition of parallel networks, its A_{0,j}, not A_{0}^{j}.
           1.4. Problem (7) has a typo.

    2. There seems to be very few technical novelty. Most of the paper is about the standard step of calculating the dual problem, the rescaling technique is also quite standard and well-known (e.g., in SVM), and was used in (Ergen & Pilanci, 2020b) for neural networks. Please clarify any technical novelty compared to prior works.

    3. There are no experiments that validate the theorems, while the claimed theorems lead to at least the following suspection. Specifically, the main result, Theorem 1, has two closed-form expressions for optimal values of P_{lin}(t) and D_{lin}(t) respectively, and in its proof (page 16) the authors claim that D_{lin}(t) is "strictly" smaller than P_{lin}(t). However, the two terms are obviously equal if X^{dagger}Y has its all singular values equal to 1. This means something wrong in the proof or in the statement of Theorem 1.

    4. Please provide some discussion on m^* of Proposition 1. It seems important to bound it.

    5. Assume Proposition 2 is correct. Further assume that we have ample and general enough data samples (so that X is a tall matrix of full rank). Then I could conclude that the optimal value of (7) is directly given by the optimal value of Proposition 2 where W is replaced by X^dagger Y. As a result, much of the development of the paper becomes pointless as the optimal value of (7), and thus an optimal solution, is already known. In this situation, why do we care about whether the duality gap is zero or not?

Questions: Please shed some light on proof techniques for deep linear networks and deep parallel networks as they are tightly related. My feeling is that the results for deep parallel networks are natural consequences of those for deep linear networks. Is that correct?

summary_of_the_review: The above concerns on mathematical clarity, technical novelty, technical correctness, and practical vadility lead me to form the opnion of reject. However, I am not an expert in this field of "theory of training neural networks", so I am looking forward to rebuttals from the authors, as well as comments from other reviewers and the area chair.
review_title: null

Meta-review: This is an interesting paper which further extends the duality theory of deep networks.  Unfortunately, reviewers had many concerns about, presentation, technical details, and missing prior work.  I will add that a large volume of relevant implicit bias work (e.g., in the setting of deep linear networks, mirroring Proposition 2) is completely uncited (e.g., works by Arora et al., Soudry et al., Ji et al.), despite being earlier than many of the works which are currently cited.  As such, I urge the authors to continue in their valuable line of work, taking into consideration all of these points and also the reviewer comments.

Separately, I note that there is a violation of the blind policy in the current revision: grant information was included.  The PC decide this was a minor violation and should not affect the review process, however their decision could have easily been otherwise.  I urge the authors to be exceptionally careful with such issues in the future.
Decision: Reject