Exploring The Loss Landscape Of Regularized Neural Networks Via Convex Duality

Thank you for your helpful comments on the paper. We have addressed them as the following:

1. Clarifications: Unclear sentences, math error (triangular inequality reversed), some undefined variables (e.g. P), results referring to the appendix, missing reference

Please see the general response. Some fixes that were made were:

1. Clearer statement on $\mathcal{P}^{\ast}_{\nu^{\ast}}$ and the intuition of optimal polytope
2. More accessible statement of main results
3. Bottom of Figure 2 explained
4. Clarification of the three interpolation problems solved (Section 3.3)

We have fixed the math error and added notations to the main paper, defining all undefined variables there. Also, we tried to move most results from the appendix (as much as the page limit allows). At last, thank you for pointing out an important reference that was missing. We added the reference in the related works section.

The authors have addressed every concern raised in my review, therefore I suggest this paper to be accepted at ICLR25.

4. What happens if $m < m^{\ast}$? What is the scale of $m^{\ast}$?

When $m < m^{\ast}$, we cannot apply the methods discussed in the paper directly because there is no convex reformulation. We "could" start with a cardinality-constrained optimization problem,

but the critical issue is that the above problem is not convex, so it is not clear yet how to deal the case $m < m^{\ast}$.

Precisely speaking, the scale of $m^{\ast}$ does not depend on $n, d$, but depend on the geometry of the dataset $(X, y)$. Specifically, consider $\mathcal{Q}_X = \{ReLU(Xu) \ | \ \lVert u \rVert_2 \leq 1\}$. Suppose we are solving the min-norm interpolation problem. Scale $y$ so that $ty \in \mathrm{Conv}(\mathcal{Q}_X \cup -\mathcal{Q}_X)$. The minimal number of points that are needed to express $ty$ as a sum of vectors from $\mathcal{Q}_X \cup -\mathcal{Q}_X$ becomes $m^{\ast}$. Hence, even for large $n, d$, depending on the dataset $m^{\ast}$ could be very small. It is an interesting open problem how $m^{\ast}$ would behave for random $(X, y)$, but unfortunately, I am unsure how things look like currently.

5. Can we still apply this technique for $\epsilon$ perturbations? One thing we could do is using a convex set $(u_i, v_i)_{i=1}^{P}$ where $L(\sum_i D_iX(u_i - v_i), y) + \beta \sum_i \lVert u_i \rVert_2 + \lVert v_i \rVert_2 \leq p^{\ast} + \epsilon$ where $p^{\ast}$ denotes the optimal value of the convex program. Here we will not have the optimal polytope characterization, so the connectivity behavior could differ and we may have that the set becomes connected even for lesser $m$. We think understanding how the connectivity behavior of the set changes as $\epsilon$ changes and understanding the (possible) phase transitional behavior is a very interesting direction of study, and also fits well with the initial description of mode connectivity.

6. Clarifications: $\mathcal{S}i$, optimal model fit, reversed triangular inequality, $\mathcal{P}^{\ast}_{\nu^{\ast}}$, the statement of Proposition 1, Dimensions in equation (7)

We no longer have complicated statements in the main paper. The optimal model fit and its uniqueness is stated before it is used. We fixed the triangular inequality and added more explanations for unclear statements, and specified the dimensions in equation (7). Please refer to the general response.

References [1] Hanin, Boris. "Ridgeless Interpolation with Shallow ReLU Networks in $1 D$ is Nearest Neighbor Curvature Extrapolation and Provably Generalizes on Lipschitz Functions." arXiv preprint arXiv:2109.12960 (2021).

[2] Boursier, Etienne, and Nicolas Flammarion. "Penalising the biases in norm regularisation enforces sparsity." Advances in Neural Information Processing Systems 36 (2023): 57795-57824.

[3] Joshi, Nirmit, Gal Vardi, and Nathan Srebro. "Noisy interpolation learning with shallow univariate relu networks." arXiv preprint arXiv:2307.15396 (2023).

[4] Ergen, Tolga, and Mert Pilanci. "Convex geometry of two-layer relu networks: Implicit autoencoding and interpretable models." International Conference on Artificial Intelligence and Statistics. PMLR, 2020.

[5] Ongie, Greg, et al. "A function space view of bounded norm infinite width relu nets: The multivariate case." arXiv preprint arXiv:1910.01635 (2019).

[6] Savarese, Pedro, et al. "How do infinite width bounded norm networks look in function space?." Conference on Learning Theory. PMLR, 2019.

[7] Parhi, Rahul, and Robert D. Nowak. "Banach space representer theorems for neural networks and ridge splines." Journal of Machine Learning Research 22.43 (2021): 1-40.

[8] Ergen, Tolga, and Mert Pilanci. "The Convex Landscape of Neural Networks: Characterizing Global Optima and Stationary Points via Lasso Models." arXiv preprint arXiv:2312.12657 (2023).

[9] Bartan, Burak, and Mert Pilanci. "Neural spectrahedra and semidefinite lifts: Global convex optimization of polynomial activation neural networks in fully polynomial-time." arXiv preprint arXiv:2101.02429 (2021).

[10] Ergen, Tolga, et al. "Globally optimal training of neural networks with threshold activation functions." arXiv preprint arXiv:2303.03382 (2023).

[11] Ergen, Tolga, and Mert Pilanci. "Path regularization: A convexity and sparsity inducing regularization for parallel relu networks." Advances in Neural Information Processing Systems 36 (2024).

[12] Garipov, Timur, et al. "Loss surfaces, mode connectivity, and fast ensembling of dnns." Advances in neural information processing systems 31 (2018).

Thank you for your helpful comments on the paper. We have addressed them as the following:

1. Significance of the result in 3.3

There are two consequences in the result of Theorem 3.3, both are of theoretical interest. The consequences are:

1. We show that free skip connections may affect the qualitative behavior of the optimal solutions(e.g. uniqueness and sparsity)
2. The nonunique min-norm interpolators imply that we have multiple interpolators with the same norm but with different generalization performances, and their behavior may diverge significantly outside the training set.

The first consequence is that in the literature, free skip connections have been imposed in the problem for a clearer derivation of optimal solutions ([1], [2], [3]). It has been believed in [2], [3] that not having free skip connections does not affect the optimal solution that much in practice. For example, in pg 2 of [3], it is stated that

"This skip connection avoids some complications and allows better characterizing ˆfS but does not meaningfully change the behavior [3]".

Our example shows that this statement is false, and not having free skip connections can make the problem have multiple min-norm interpolators and make the solution not sparse (i.e. the optimal interpolator may not be the sparsest). Thus, free skip connection may change the qualitative behavior of the solution (uniqueness & sparsity).

Another significance is that these different minimum-norm interpolators, though having the same norm, have different generalization performances (because they behave differently outside the training set). Generalization bounds are generally associated with parameter norms, but here we see that interpolators with the same norm have are drastically different: as $x \rightarrow \infty$, the two function differences diverge, and have population loss (which is a qualitative difference).

Moreover, the example demonstrates how convex duality can construct structured counterexamples motivated from the hidden convex geometry. The intuition for such construction is making the set $\mathcal{Q}_{X} = \{ReLU(Xu)\ | \ \Vert u \rVert_2 \leq 1\}$ meet with its supporting hyperplane with $n+1$ points.

At last, we would like to emphasize that while the setting $d = 1$ could seem restrictive, understanding minimum-norm interpolators is an important problem that has been extensively discussed [1]~[7]. We believe it is an interesting problem whether we can construct counterexamples where the minimum-norm solutions differ the most, but we would like to leave it for future work.

2. Significance of the result in Theorem 4 The significance of Theorem 4 is not within the proof strategy, but the fact that we can describe a certain subset of the optimal set of a deep neural network in a precise manner. It is challenging to describe the optimal set of deep networks, because of its nonconvexity without a good theoretical structure to work with. Nevertheless, due to page limitations, we moved the Theorem to the appendix and mention such characterization is possible in the main paper.

3. Universality of the techniques For the possible extensions to different activation functions, please see the general response.

Also, we have extensions of the result to parellel three-layer neural networks (Theorem 3 of the main paper). Also, there are discussions of convex reformulations of parallel neural networks of depth L [11], and we believe that at least some of the results (e.g. the polytope characterization) could be extended to these settings.

Overall, it is not true that these results could be extended to networks with arbitrary activation and architecture, but are not limited to only two-layer ReLU neural networks.

I would like to thank the authors for addressing my questions and concerns in detail, I believe now I understand the contributions of the papers better after reading the authors' response. I also checked the revised version of the paper, and it is much more readable comparing to the original version.

Overall, I believe this paper has solid theoretical contributions on understanding the loss landscape of certain neural networks with L2-regularization, and would like to suggest a clear acceptance of this paper to ICLR2025.

Finally, I have one last question: I think I'm able to understand the technical results in this paper, and it is based on a line of works [1-3] that studies the convex formulation of neural networks as mentioned in related works part. To be honest, I'm not familiar with the technical results this line of work, so I can not accurately tell how "novel" the technical parts is. Thus, could the authors elaborate a bit more on the connections and differences between this paper and the line of works[1-3] (or maybe other works follows this line)?

[1] Pilanci, Mert, and Tolga Ergen. "Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks." [2] Ergen, Tolga, and Mert Pilanci. "The Convex Landscape of Neural Networks: Characterizing Global Optima and Stationary Points via Lasso Models." [3] Mishkin, Aaron, and Mert Pilanci. "Optimal sets and solution paths of ReLU networks."

Thank you and best regards, Reviewer eG7f

Thank you for your helpful comments on the paper. We have addressed them as the following:

1. Different activation functions

For the possible extensions to different activation functions, please see the general response.

Though this is the case, this paper only discusses neural networks with ReLU activation - we now explicitly state that our scope is networks with ReLU activation in the Introduction and problem settings.

2. Presentation of Section 2 Thank you for pointing out the insufficient explanation on convex reformulations in Section 2. In the revised manuscript we added more explanation to Section 2. Specifically, we

1. clearly defined what $D_i, X, y$ and the shape of each matrix is in the problem setting and notations
2. We specifically stated that when $m \geq m^{\ast}$ for some critical threshold $m^{\ast} \leq n$, we have a convex reformulation.
3. We gave an exact notion what "equivalent convex problem" means, and gave how the two solutions are related.
4. We specifically stated that when $m \geq m^{\ast}$, strong duality holds and the dual problem also has the same optimal value as the primal problem.

3. Clarifications: Red points in Figure 1, the lower half of Figure 2

First, the red points in Figure 1 are actual optimal points in parameter space. Note that all permutations of each red point will be optimal: you could understand Figure 1 as all those permutations each plotted as red points, and as permutations are finite, we have finite number of red points.

We clarified the lower half of Figure 2 in the revised manuscript.

Thank you for your helpful comments on the paper. We have addressed them as the following:

1. Accessible explanations of theoretical results

We agree that the paper would benefit from more intuition and have uploaded a major revision improving the presentation. Please see the general reponse.

2. Empirical validation of theoretical results with real-world datasets

Unfortunately, it is extremely hard to verify our findings with real-world datasets and large models. There are two reasons:

1. Computing the critical widths $m^{\ast}$, $M^{\ast}$ is challenging. Though we present how we can compute the critical widths in practice (see Remark D.1. or answer 4 of the rebuttal), the algorithm is exponential in the number of data (the complexity is actually $O((n/d)^{dn})$, though we have an algorithm to upper bound $m^{\ast}$ by first computing a solution to the convex training problem and pruning the solution(as introduced in [6]). A naive bound is $m^{\ast} \leq n$). As finding $m^{\ast}$ is equivalent to finding sparsest points within a convex set, we believe that the problem could be NP-hard (e.g. [1] shows that finding a sparsest point in an ellipsoid is NP-Hard), and there might not be any efficient (or practical) algorithm to find these widths.

2. Obtaining the optimal solution set is challenging for real-world dataset and large models. This is because even for two-layer networks, training neural networks to global optimality can be NP-Hard in certain scenarios ([2], [3]). Even in cases where we can train networks to global optimality, e.g. when the network is sufficiently wide enough so that it does not have spurious local minima, we could use the convex reformulations to obtain the solution set, but one problem is that the number of variables(which is in scale $O((n/d)^d)$) for the problem will be too large and finding the exact optimal solution set is impractical.

Nevertheless, we think that this weakness demonstrates the theoretical strength of our results, as our results show how theoretical analysis can lead to scientific statements concerning neural network training where empirical experiments could never grasp (due to computational complexity).

3. Notations to the main paper

We summarized and moved the notation part to the main paper in the revised manuscript. Please refer to the general response.

4. A way to compute or estimate the critical widths $m^{\ast}$, $M^{\ast}$

There exists an algorithm to exactly compute the critical widths $m^{\ast}, M^{\ast}$. The algorithm is discussed in Remark D.1, and we have added that there exists an algorithm that can compute $m^{\ast}$ and one can refer to the appendix in the main paper.

5. How "the descent path to arbitrary global minimum" can motivate practical algorithms

The construction of a path that connects global minima can motivate new algorithms that search the optimal solution space. More specifically, the "meta-algorithm" that was used to prove that $\mathcal{P}^{*}(n+1)$ is connected could be directly used to construct a path between two points with low training loss.

Also, we have a practical implication of the Theorem, which says that the loss landscape is benign and even though the landscape is nonconvex, naive methods may find good parameters well.

6. Clarifications: $\mathrm{Diag}(1(Xh \geq 0))$, $\mathcal{P}^{\ast}_{\nu^{\ast}}$, Figure 2 bottom, the three interpolation problems

We clarified these in the revised manuscript. Specifically, $\mathrm{Diag}(1(Xh \geq 0))$ is defined in the notations, sentences explaining $\mathcal{P}^{\ast}_{\nu^{\ast}}$ and the three interpolation problems were rewritten, and the bottom of Figure 2 is explained with labels.

References [1] Natarajan, Balas Kausik. "Sparse approximate solutions to linear systems." SIAM journal on computing 24.2 (1995): 227-234.

[2] Boob, Digvijay, Santanu S. Dey, and Guanghui Lan. "Complexity of training ReLU neural network." Discrete Optimization 44 (2022): 100620.

[3] Froese, Vincent, and Christoph Hertrich. "Training neural networks is np-hard in fixed dimension." Advances in Neural Information Processing Systems 36 (2024).

[4] Cover, Thomas M. "Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition." IEEE transactions on electronic computers 3 (1965): 326-334.

[5] Haeffele, Benjamin D., and René Vidal. "Global optimality in tensor factorization, deep learning, and beyond." arXiv preprint arXiv:1506.07540 (2015).

[6] Mishkin, Aaron, and Mert Pilanci. "Optimal sets and solution paths of ReLU networks." International Conference on Machine Learning. PMLR, 2023.

We are very glad to see that the reviewer appreciated our work!

1. A deeper discussion on the topological implications of the results

The main topological implication of our theorem is that as the width increases, the topology of the solution set is complicated at first, but becomes simpler later on.

An important implication of our theorems is that all sublevel sets are connected when the width is sufficiently large ($n+1$) Hence, our result on connectivity is a non-asymptotic improvement of [2], enabling us to discuss the topology of sublevel sets not only in the case $m \rightarrow \infty$.

Another interesting direction to study the topology of the optimal set of neural networks is discussing its homology (i.e. we want to find out if the optimal set looks like a simple sphere, or something like a torus with a hole, etc.). We believe that our framework could be used to cound the number of holes that an optimal set of a neural network has, once we understand the homology of the cadinality-constrained set $\mathcal{P}^{*}(m)$ in the paper. We believe such characterization could make our understanding of neural network loss landscapes more complete, by excluding certain shapes as impossible or finding out that the "bottom of the loss landscape" looks like a certain shape.

[1] Haeffele, Benjamin D., and René Vidal. "Global optimality in tensor factorization, deep learning, and beyond." arXiv preprint arXiv:1506.07540 (2015).

[2] Freeman, C. Daniel, and Joan Bruna. "Topology and geometry of half-rectified network optimization." arXiv preprint arXiv:1611.01540 (2016).