We would like to thank the reviewer for the feedback and comments. Please see our responses below for answers to provide additional points of clarification on the reviewer's open questions.

1. It is still a bit unclear to me how the training of the BM factorization for ReLU networks (19) is done in practice

(19) can be solved in practice using a variety of methods, the simplest of which is projected gradient descent. We now include a high-level description of the algorithm in Appendix A.1 to explain how this would be solved, along with the time complexity of the solution.

I would like to thank a lot the Authors for their efforts during the rebuttal: I have read the revision and the additional section regarding Projected Gradient Descent and its complexity, and this has answered my question. I have also read the other reviews and response. As a consequence, I have raised my confidence score.

We would like to thank the reviewer for the feedback and comments. We hope that you would consider increasing your score if your concerns are adequately addressed. Please see our responses below.

1. Showing that applying BM factorization to convex neural networks leads to more scalable implementations.

To help show more results on the fact that the BM factorization leads to more scalable implementations, we have added an additional section in Appendix A.1 which demonstrates the superior time complexity of the BM formulation compared to the original non-convex objective.

In addition, the reviewer has some questions around the need for layerwise training and how it relates to this paper. Below we can explain in more depth the rationale behind these experiments.

While training deep neural networks directly is possible using SGD heuristically applied to poorly understood non-convex objectives, we seek to find approaches that can optimize equivalent architectures to deep neural networks while having convex guarantees. While most of the theory around convex neural networks allows us to re-state two-layer neural networks as convex programs, we wish to extend the capabilities of this approach to deeper networks. Thus, layerwise learning is a natural solution -- each two-layer sub-component of a deeper neural network can be trained to global optimum using convex optimization. Layerwise learning has already shown great success in the non-convex training domain as shown in Belilovsky et al., 2019. However, naively using convex optimization to train layerwise networks does not scale computationally for the reasons discussed in Section 4.2.

Therefore, we show how the BM factorization applied to these convex networks (1) scales in a way that the original convex program doesn't, allowing us to train these architectures in a layerwise fashion in an approach that matches the performance of end-to-end trained deep neural networks; and (2) preserves convex guarantees around optimality and has an easily computable relative optimality gap bound. We hope this makes the motivations of the layerwise training experiments more clear to the reviewer.

2. What's the novelty of the paper at the technical level?

The primary technical novelty against other works such as Bach et al. (2008) and Haeffele et al. (2014) is in our characterization of stationary points. In Theorems 3.3 and 3.4, we characterize the relative optimality gap for stationary points of the BM factorization, which is not shown in any other work. Most other work around the BM factorization focus on local minima only. This is especially significant because for most NN objectives, there is no guarantee that BM will actually find local minima, as we discuss in Section 2.2. We note that there are other aspects to novelty in our work such as results in neural networks, though we believe the reviewer does not dispute this and is more curious about the technical innovations in how we study the BM factorization.

Thank you for the minor comments as well -- these have been revised in the updated version (see changes in the revised PDF in blue).

Dear Reviewer xgT4,

We believe that we have addressed your concerns in our responses. Since the deadline is approaching, we would like to hear your feedback so that we can respond to that before the discussion period ends. Please feel free to raise questions if you have other concerns.

Best regards,

Authors

We would like to thank the reviewer for the feedback and comments. We have added some recommended clarifications mentioned by the reviewer. Please see our responses below.

1. The discussion on how the proposed method is compared to [1] and [2] should be included at least theoretically, if not experimentally.

We thank the reviewer for notes on [1] and [2] -- these are interesting works that propose convex alternatives to neural networks. We should note that these are slightly different than the line of work we focus on in our paper, because they do not exactly match the objectives and architectures of typical non-convex neural networks, whereas in this paper we focus on exact convex formulations of an identical neural network objective (i.e. a solution to (3) maps one-to-one with a solution to (1)). We have included a brief mention of [1] and [2] in our related work section.

2. The authors could include a big O notation analysis on the computational cost to better illustrate exactly how much the BM factorization helps with scaling the method.

We have now included this big O notation analysis to illustrate the per-iteration complexity of solving the BM factorization compared to the original convex formulation in Appendix A.1.

Dear Reviewer 8nq3,

We believe that we have addressed your concerns in our responses. Since the deadline is approaching, we would like to hear your feedback so that we can respond to that before the discussion period ends. Please feel free to raise questions if you have other concerns. Thank you very much for your support, we really appreciate that!

Best regards,

Authors

We would like to thank the reviewer for the feedback and comments. We hope that you would consider increasing your score if your concerns are adequately addressed. At a high level, we have added some additional details to the paper in Appendix A.1 to demonstrate why the Burer-Monteiro factorization is more computationally efficient than solving the original convex neural network, as well as some experimental results in Appendix C.3 that also show this result. Please see our detailed responses below.

Responses to Weaknesses

1. Proposed BM formulation doesn't provide any advantages other than removing quasi-nuclear norm. It would be more efficient to solve the original convex problem.

We have provided additional explanations of the per-iteration complexity of the Burer-Monteiro factorization compared to the original convex problem.

While the Burer-Monteiro (BM) factorization adds additional variables (the original convex problem has $Pdc$ variables, while the BM factorized optimization problem has $Pm(d+c)$ variables), the per-iteration complexity is greatly reduced in the BM case. In the ReLU activation case, we can compare applying the Frank-Wolfe algorithm presented in (Sahiner et al., 2021b) to the convex problem (3) to projected gradient descent applied to (19).

In (Sahiner et al., 2021b) Appendix A.4.2, it is shown that a single Frank-Wolfe iterate on (3) is $\mathcal{O}(Pn^r)$, where $r := \mathrm{rank}(X)$. In contrast, a single iteration of projected gradient descent on (19) naively takes $\mathcal{O}(P(n^3 + n^2(d+c + dm) + dcm))$ time. It's clear that unless $m$ is chosen to be exponential in $n$ (which would never occur in practice), the per-iteration complexity of solving (3) is order of magnitude larger than that of (19) due to the exponential dependence on $r$. Therefore using the BM factorization greatly reduces the per-iteration complexity of solving the neural network optimization problem

We have added an additional section in the Appendix (Appendix A.1) to walk through the details of this result.

2. The proposed BM formulation for CNN is still not practical as the memory requirement is too high.

The proposed BM formulation for two-layer CNNs is practical -- this is why we use it in Section 4.2. The purpose of doing layerwise training is to expand these results to carry to deeper neural networks, rather than to overcome shortcomings of the computational complexity of the BM factorization for CNNs.

3. It does not reduce the time complexity and the memory requirement for solving the convex neural network training problem.

See above and Appendices A.1 and C.3 for an explanation of how we reduce the time complexity and memory requirements for solving the convex neural network problem.

4. Limited novelty

Aside from the BM factorization proposed in this work being the first time the BM factorization has been applied to neural network optimization, we present novel results in a few ways:

1. We derive a novel bound on the relative optimality of the stationary points of the BM factorization for neural networks. This is the first time stationary points of BM factorization have been showed in any work -- other works have solely focused on local minima, which are not guaranteed to be found with e.g. SGD.
2. Accordingly, we are the first to develop conditions to check if stationary points of BM factorizations have achieved their global optimum.
3. We also use this BM theory to uncover insights about novel neural network architectures, e.g. that linear self-attention networks with sufficiently many attention heads have no spurious local minima.

Dear Reviewer 4XdN,

We believe that we have addressed your concerns in our responses. Since the deadline is approaching, we would like to hear your feedback so that we can respond to that before the discussion period ends. Please feel free to raise questions if you have other concerns.

Best regards,

Authors

I want to thank the authors for providing the additional experimental results. My main concern is whether the time and memory complexity of the proposed BM formulation is practical, and I think the authors’ response and the additional experimental results have addressed my concerns. It is now clear that solving the proposed BM formulation with naive PGD has lower per-iteration cost than solving its convex formulation using Frank-Wolfe, however, the naive PGD might suffer from sublinear convergence. It would be interesting to see if it is possible to extend [1], which studies the preconditioned GD for unconstrained BM optimization problems, to derive the preconditioned PGD for solving the constrained BM optimization problems proposed in this paper (for example, equation 19 and 24).

I think with the additional results, the paper now has decent novelty as it is the first paper to propose the BM formulation for convex NN training that guarantees global optimality. Most importantly, the proposed BM formulation is indeed practical and does mitigate the scalability issue faced in convex NN training. I have adjusted my score.

[1] Gavin Zhang, Salar Fattahi, and Richard Y Zhang. Preconditioned gradient descent for overparameterized nonconvex burer-monteiro factorization with global optimality certification., JMLR 2023.

We would like to thank the reviewer for the feedback and comments. Please see our responses below for answers to provide additional points of clarification on the reviewer's open questions.

1. How feasible is it to generalize this framework to more than 1 hidden layer?

Unfortunately, there have not been many satisfactory convex formulations of deeper neural networks that are amenable to this kind of analysis. Hence our emphasis on layerwise training in Section 4.2.

2. Hard to keep track of all the norms at once.

We have updated our "notations" section in Section 2 to make these more clear.

3. Is there a feasible framework to analyze saddle points of the BM formulation and not just local minima?

Theorems 3.3 and 3.4 do exactly this -- they show results around the stationary points (which include saddle points) of the BM formulation, rather than just local minima which has been the focus of much of the existing BM literature.