Convex Formulations for Training Two-Layer ReLU Neural Networks

We thank the reviewer for their detailed feedback and for finding our paper to be novel and insightful. We acknowledge that the reviewer is right in many of their observations. We appreciate the reviewer’s grasp of our work.

Practical contribution. Our paper provides a simple yet novel formulation that offers a new perspective on this problem. Unlike existing approaches such as NTK/NNGP or the method proposed by Sahiner et al. (2021), our approach is built on fundamentally different techniques, providing unique insights. Specifically, compared to Sahiner et al., our formulation is more compact and eliminates the need to enumerate sign patterns. We will include [1] in the discussion of related works in the revised paper. For further discussion on the practical aspects of our method, we kindly refer the reviewer to the "General Remarks" section, above.

Experimental evaluation. We refer the reader to the “General Remarks” for a discussion on our experimental evaluation, which mainly targets validating our theoretical contributions rather than arguing for a practical training scheme. Note that, despite its limitations, our experimental settings still involve problems that cannot be solved by the prior works such as Sahiner et al. 2021.

Furthermore, we agree that it would be interesting to test the width required in rounding to evaluate the observations made in [2] within our setting. We will leave a thorough investigation of this to a future study.

Quadratic vs. cubic scaling. This is correct—while the formulation scales with $n^2$ (since the rank is absorbed), storing the factors requires $n^3$ storage. We now clarify this in the paper.

Computational complexity. Solving CP-NN or the associated rounding problems is NP-hard. The complexity of solving an SDP depends on the specific algorithm used. A typical interior point method for solving an SDP problem with an $n \times n$ matrix variable and $m$ constraints requires approximately $\mathcal{O}(n^3 + m^2 n^2 + m^3)$ arithmetic operations per iteration and about $\mathcal{O}(\log(1/\epsilon))$ iterations to achieve an $\epsilon$-accurate solution. We now include a discussion about the computational aspects and report the runtime (see “General Remarks”) in the main paper.

Small issues. We fixed all of the small issues and thank the reviewer for bringing these up. In the light of these, we further polished some parts of our paper.

Questions

Q1. Theorem 1 is applicable for any convex loss function $\ell: \mathbb{R}^d \times \mathbb{R}^c \to \mathbb{R}$ (with the corresponding change in the objective function), since our analysis focuses on the feasible sets and is largely independent of the loss function.

Q2. This corresponds to the complexity of the rounding problem, which is a specific instance of nonnegative matrix factorization, a problem that is generally NP-hard, similar to solving the CP-NN.

Q3. There can be solutions to NN-integral-train that are not discrete. However, for any such solution, there always exists another solution (that achieves the same objective value) with discrete measure supported on $R$ elements, where $R$ is the critical width. In Lemma 4 (which is used in Theorem 2), we observe that $\Lambda$ can be decomposed using a continuous probability measure, as a continuous probability distribution can always be constructed to match the first and second moments of a discrete distribution. Here, $\mathbb{E}[\lambda\lambda^\top]$ represents the second moment matrix of the random variable $\lambda$.

Q4. We thank the reviewer for this insightful question. The rounding process effectively captures the main alignments, resulting in strong training and test accuracies, as noted in the paper. However, upon further investigation based on the reviewer’s suggestion, we noticed that it introduces a scaling issue, which negatively affects the loss values and renders them suboptimal. We will further explore the rounding procedure to address this issue and develop more robust solutions. We thank the reviewer for this suggestion which also poses a promising future direction.

Q5. This is likely attributable to the problem size. We used the SCS solver in CVXPY for larger datasets. While this first-order algorithm is more scalable, it yields solutions with limited accuracy compared to interior-point methods. We believe that solving the problem with higher accuracy could resolve the discrepancy. However, we cannot currently rule out the possibility that the relaxation gap depends on the problem size, as we lack sufficient data to refute this hypothesis.

We appreciate that the reviewer finds our proposed method interesting and clearly presented. Below, we address all the weaknesses pointed out and kindly ask the reviewer to reconsider their rating.

On practicality and empirical evaluations. We notice that the reviewer appears to have overlooked the insights convex formulations can offer. We contribute to a deeper understanding of neural networks. We believe this to be a valuable goal, even if it does not immediately translate to a novel intervention to better train neural networks bringing performance advantages. For overall concerns regarding empirical evaluations and the practical value of our contributions, we refer the reviewer to our “General Remarks”, where we have thoroughly discussed these aspects.

NTK, NNGP and SGD. We would like to clarify a few potential misunderstandings here. Firstly, our aim is not to propose CP-NN or SDP-NN as replacements for actual neural network training, nor to position them as direct competitors to NNGP or NTK. Instead, the primary objective of this work is to introduce a novel perspective by framing neural network training within a convex optimization framework, which is grounded in fundamentally different principles compared to kernel-based methods. Consequently, whether or not the method goes beyond the NTK regime is outside the scope here.

Second, we agree with the reviewer that NTK/NNGP cannot fully explain the success of deep learning due to their inherent limitations. Yet, unlike the reviewer suggested, our formulation differs significantly and does not share the same constraints. Unlike NTK and NNGP, our convex formulation is exact and applies to both finite and infinite-width regimes as long as the critical-width threshold is satisfied. Additionally, our method is not dependent on initialization. Any empirical inexactness arises solely from the relaxation and rounding processes, which do not undermine the theoretical validity of our contributions, even if the computation is NP-hard. As such, drawing theoretical conclusions solely based on empirical performance would overlook the broader implications and insights brought by our work.

Third, we would like to clarify the distinctions between NNGP, NTK, and SGD. NNGP models the prior predictive distribution of an untrained neural network in the infinite-width limit, while NTK captures the training dynamics of gradient descent under similar assumptions. Neither of these frameworks is equivalent to SGD. While NTK can approximate SGD dynamics under specific overparameterized conditions (as noted in the references provided by the reviewer), this correspondence is not universal and relies on several assumptions. Importantly, as stated in the paper, we use SGD with a hidden layer of 300 neurons in our experiments. Under these conditions, we do not expect SGD to align with NTK.

We now include this discussion into our paper. We hope these clarifications address the reviewer’s concerns and highlight our distinct contributions.

Fang et al. 2022. Thank you for bringing this reference [5] to our attention; we have included it in the related works section. However, the techniques employed in that work and ours are entirely different. While they focus on deep network models, they particularly assume activation functions with continuously differentiable gradients, which makes their approach not applicable to ReLU neural networks. Moreover, their convex representation for infinite width neural network training is infinite-dimensional, with a discrete model obtained through a sampling approach that guarantees equivalence only in the limit as the number of neurons approaches infinity. In contrast, our work focuses on two-layer ReLU neural networks, characterizes a finite critical width, and introduces a finite-dimensional convex optimization formulation for (in)finite width neural network training.

We thank the reviewer for expressing further concerns. We must admit that we suspect the reviewer might be overlooking the main point in our paper in favor of prioritizing performance or comparing to NTK. This is further evident from the reviewer's repeated emphasis on MNIST/CIFAR benchmarks, which are themselves considered to be toy in the regime of modern machine learning.

Please note that the inability to handle the large problem sizes, as in MNIST/CIFAR, is not a unique limitation of our method but common to all similar works within the prominent convex-formulations literature, to which our paper contributes. We would like to reiterate that while our method scales to larger problem sizes compared to prior work, such as Sahiner et al. 2021, improving training performance is not the primary objective of our research. Therefore, it would be inappropriate to assess our work solely on this criterion. Instead, our experiments are a testament to the theoretical correctness of our approach, and they should not be interpreted as an attempt to provide new training algorithms. Our contribution lies in offering a novel perspective and advancing the theoretical understanding of neural networks through convex formulations.

We also wish to stress that our theory is fundamentally distinct than NTK (as we explained) and we do not see the need to contrast them. Nevertheless, our contributions are advantageous over NTK due to:

(i) Finite networks. Thanks to the critical width, we can theoretically work with finite neural networks without resorting to approximations or truncation. This is a significant step beyond the limitations of NTK/NNGP.

(ii) Initialization-independence. Our convex formulation does not assume a particular initialization and provides an exact closed form. NTK/NNGP are strongly tied to the initialization.

While not positioning ourselves as direct competitors to NTK/NNGP, we believe that these are clear theoretical advantages, that are important on several fronts we summarize below:

Advantages of our convex formulations. Convex formulations of neural networks offer significant benefits in advancing our understanding of deep networks. In addition to our last comment to Reviewer 9js6, we now provide an expanded discussion and perspective on this:

(i) Convex formulations are essential in converting pesky non-convex landscapes into interpretable ones. By doing so, they provide a clearer view of the solution space, revealing its geometric structure, and help identify properties of optimal solutions without getting trapped in suboptimal configurations.

(ii) They pave the way for a rigorous theoretical analysis, including guarantees of convergence, uniqueness, and stability of solutions. This is in contrast to traditional training where guarantees are often limited or conditional on specific initialization schemes or overparameterization. We leave such analysis for a future work.

(iii) Thanks to our exact co-positive formulation, studying how high-dimensional lifting of data affects separability and decision boundaries can offer insights into how neural networks learn representations and resolve ambiguities in the data.

(iv) Bridging the gaps between optimization, geometry, and learning theory is fundamental to develop a modern theory for deep networks. This is what we precisely contribute towards.

In the light of these, one particularly compelling avenue for future work involves leveraging our convex formulation to study generalization as pointed out by the Reviewer 9js6. Let us paraphrase our latest response below. Generalizing solutions are known to reside in the "wide minima" of the loss landscape. This gives a relationship between the generalization error and the location of critical points. For our lifted convex formulations, the critical points are readily identifiable and can be mapped back to the non-convex landscape of the original problem through smooth parameterizations, as demonstrated by Levin et al. [*]. By characterizing the local convexity of these points, we can potentially determine which solutions generalize better. While we have not yet investigated this, we plan to make such connections clearer in the future.

MNIST/CIFAR evaluations. We have nonetheless initiated experiments on a subsampled version of MNIST, following a similar approach to Sahiner et al. (2021), who additionally applied data whitening to make their computations feasible. Notably, unlike Sahiner et al., we do not require data whitening to ensure computationally tractable sign patterns. The results of these experiments will be included in a further revision.

We will include all these discussions into our paper and hope that this expanded exposition provides clarity strengthening the reviewer’s grasp of our contributions.

[*] Levin, E., Kileel, J., and Boumal, N. The effect of smooth parametrizations on nonconvex optimization landscapes. Mathematical Programming. 2024.

We appreciate the reviewer’s thoughtful summary of our work and their positive feedback, reflecting a clear grasp of our contributions. Below, we address the concerns raised:

Numerical comparison to prior work. We agree with the reviewer that numerical comparisons to prior work are relevant. Yet, the goal of our experiments is to validate our SDP relaxation and not to outperform existing benchmarks. It is because our formulations as well as the related works, are intended primarily for theoretical understanding rather than practical application. In this context, different formulations should not be viewed as rivals, as they can provide different insights, as the reviewer recognized. For more details, we refer the reviewer to the general response regarding runtimes.

Runtime. We refer the reviewer to the general response regarding runtimes.

On the insights. Exploring the geometry of the solution space in the convex landscape and its mapping to the original nonconvex template could yield valuable insights into how neural networks resolve data. We refer the reviewer to our general response for more details.

Beyond our exposition in the general remarks (see above), the exact CP-NN formulation, combined with an analog of the results by Waldspurger and Waters on the tightness of the Pataki-Barvinok (PB) bound for factorization rank in CP-NN formulations, could provide insights into the minimal width required for ReLU neural networks to succeed. Specifically, Waldspurger and Waters studied the MaxCut SDP and its factorized (non-convex) formulation. It is well-established that the factorized problem does not exhibit spurious local minima when the factorization rank exceeds the PB bound, which scales as $O(\sqrt{n})$, where $n$ is the number of vertices (number of constraints, for a more general SDP template). Recently, Waldspurger and Waters demonstrated that the PB bound is tight, meaning that even if the original SDP problem has a unique rank-1 solution, the factorized (non-convex) problem can fail unless the factorization rank is greater than the PB bound. This result provides critical guidance for selecting the rank in matrix factorization problems.

We have already touched upon these research directions in the conclusion of our main paper and we will make these connections, which motivate immediate attention to studying CP-NN formulations and their corresponding factorized (non-convex) representations, clearer.

We thank the reviewer for highlighting the clarity and reproducibility of our paper as well as the informativeness of the background we provide. In what follows, we address their concerns. In the light of these, we kindly ask the reviewer to reconsider their judgement.

Evaluation using training loss. We thank the reviewer for bringing this to discussion. Our empirical studies evaluate both generalization performance (e.g., in Table 3 using real datasets) and optimization performance (e.g., in Table 2 using random and spiral datasets). We would like to emphasize that comparing methods based solely on training loss poses challenges, especially for real-world data, where the true global minimum of the training objective is generally unknown. While the SDP relaxation provides a lower bound on the objective and SGD finds an upper bound (converging to a local solution). This fundamental difference makes direct comparisons between their results difficult. We also refer the reviewer to “General Remarks” for a broader discussion on our empirical studies.

Choice of the loss function. It is noteworthy that our analysis is independent of the loss. Hence, we can get the same guarantees for any convex loss function as long as we use the corresponding loss function in CP-NN as well. In the revised version, we will clarify this and will incorporate regression tasks to better align with the MSE loss.

Bias term. The reviewer is correct that the addition of a bias term can significantly improve performance, particularly for 2-layer ReLU networks. Theoretically, the inclusion of a bias term does not alter the underlying framework, as it can be incorporated by augmenting the input data with a column of ones. While our formulation does allow for a bias term, we inadvertently omitted it in our experiments. Importantly, both the SDP relaxation and SGD baselines were evaluated on the same model—without bias terms—ensuring consistency in the comparisons. Nevertheless, we recognize that incorporating a bias term would yield more meaningful empirical results. As the reviewer suggested, we will update the text to explicitly note this limitation and its implications. Additionally, we will conduct further experiments incorporating bias terms for both methods to evaluate their impact on performance. While it is computationally demanding to rerun the experiments once again with a bias term, we will certainly include those in the revision.

On the losses in Table 2. It is important to note that SDP-NN is a relaxation of the original problem, meaning it provides a lower bound on the objective. Therefore, its loss value is not directly comparable to SGD, which provides an upper bound by finding a feasible (but possibly suboptimal) solution. The lower loss for SDP-NN does not mean it "performs better" in the traditional sense, but rather indicates the quality of the relaxation. To evaluate the relationship between the two, we compute the approximation ratio, which quantifies how close the solution obtained by SGD is to the lower bound provided by SDP-NN. We like to point out that this is not a limitation of our method but stems from the nature of the problem – the global solution of the training being unavailable.

Let us elaborate on that a little. Specifically, the exact approximation ratio is defined as:

where $F\_{\mathrm{relaxed}}^*$ denotes the relaxed solution. However, since we do not know the true global minimum $F^*$, we instead compute the empirical approximation ratio (AR), which provides only a lower bound on how well the SDP-NN relaxation captures the training problem:

Here, $F\_{\mathrm{SGD}}^*$ corresponds to the local minimum found by SGD, and because $F\_{\mathrm{SGD}}^* \geq F^*$, we ensure that:

This guarantees that the reported AR provides a lower bound on the actual approximation ratio.

TOS rounding step. Although the rounding step lacks convergence guarantees, as noted in Remark 3, it serves as a valuable tool for validating our SDP-NN relaxation. Despite the heuristic nature of rounding, the ability to extract the trained weights of a successful neural network demonstrates that the SDP-NN solution contains the necessary information. It is important to emphasize that the rounding step is not integral to the theoretical contributions of the proposed framework and is used solely for empirical evaluations.

Equation labelling. We thank the reviewer for highlighting this point. We have now ensured that only the equations are explicitly referenced, while the associated concepts are clearly and explicitly addressed in the text.

Runtime. We refer the reviewer to the general response regarding runtimes.

Please check if the authors' response addresses your concerns.

As per reviewer suggestions we have incorporated bias into our formulation and conducted additional evaluations with and without the bias terms. This led to a considerable improvement in accuracy and F1 scores on the Pima Indians and Bank Notes datasets, as reported in the table below.

It is worth noting that for NTK/NNGP, bias was already included (to their advantage) in the main paper. We will update the main paper to include these new results, along with results from the remaining datasets. We hope that the reviewer considers these additional results in their final evaluation.

We would like to let all reviewers know that we have updated our manuscript with the additional discussions, evaluations and changes.