Exploring The Loss Landscape Of Regularized Neural Networks Via Convex Duality
Authors: Sungyoon Kim
Aaron Mishkin
Mert Pilanci
Venue: ICLR 2025 Oral (2025)
Keywords: Convex duality
Machine Learning Theory
Loss Landscape
Optimal Sets
Primary area: learning theory
TL;DR: We investigate the loss landscape and topology of the optimal set of neural networks using convex duality.

Abstract: We discuss several aspects of the loss landscape of regularized neural networks: the structure of stationary points, connectivity of optimal solutions, path with non-increasing loss to arbitrary global optimum, and the nonuniqueness of optimal solutions, by casting the problem into an equivalent convex problem and considering its dual. Starting from two-layer neural networks with scalar output, we first characterize the solution set of the convex problem using its dual and further characterize all stationary points. With the characterization, we show that the topology of the global optima goes through a phase transition as the width of the network changes, and construct counterexamples where the problem may have a continuum of optimal solutions. Finally, we show that the solution set characterization and connectivity results can be extended to different architectures, including two layer vector-valued neural networks and parallel three-layer neural networks.

Published as a conference paper at ICLR 2025
EXPLORING THE LOSS LANDSCAPE OF REGULARIZED NEURAL NETWORKS VIA CONVEX DUALITY
Sungyoon Kim', Aaron Mishkin", Mert Pilanci*
Department of Electrical Engineering. Stanford University Department of Computer Science, Stanford University sykim7776st edu, amishkin@cs stanford. pilanci woancceettafford.ccm edu
ABSTRACT
We discuss several aspects of the loss landscape regularized neural networks: the structure of stationary points, connectivity of optimal solutions, path with non- increasing loss to arbitrary global optimum, and the nonuniqueness of optimal solutions, by casting the problem into equivalent convex problem and consid- ering its dual. Starting from two-layer neural networks with scalar output, we first characterize the solution set of the convex problem using its dual and further char- acterize all stationary points. With the characterization, we show that the topology of the global optima goes through a phase transition the width of the network changes, and construct examples where the problem may have a continuum optimal solutions. Finally, show that the solution set characterization and con- nectivity results can be extended to different architectures, including two-layer vector-valued neural networks and parallel three-layer neural networks.
INTRODUCTION
Despite the nonconvex nature of neural networks, training them with local gradient methods finds nearly optimal parameters. Understanding the properties of the loss landscape theoretically impor- tant, as it enables to depict the learning dynamics of neural networks. For instance, many existing works prove that the loss landscape "benign" some sense i.e. they don't 't have spurious local minima, bad valleys, or decreasing path to infinity Kawaguchi] (2016), Venturi et al. (2019), Hacffele & Vidal (2017), Sun et al. (2020). Wang et al. (2021b). Liang et al. (2022). Such characterization enlightens intuition why these networks trained well.
As part of understanding the loss landscape, understanding the structure global optimum has gained much interest. An example is mode connectivity Garipov et al. (2018), where simple curve connects two global optima in the set of optimal parameters. Another example is analyzing the permutation symmetry that global optimum has Simsek et al. (2021). Mathematically understand- ing the global optimum is important as it sheds light on the structure of the loss landscape. They can also motivate practical algorithms that search over neural networks with the same optimal cost Ainsworth et al. (2022), Mishkin & Pilanci (023). having practical motivations to study.
We shape the loss landscape of regularized neural networks with ReLU activation, mainly analyzing mathematical properties of the global optimum, by considering its convex counterpart and leveraging the dual problem. Our work inspired by the work of Mishkin & Pilanci (2023), where they characterize the optimal set and stationary points of two-layer neural network with weight decay using the convex counterpart. They also introduce several important concepts such as the polytope characterization of the optimal solution set, minimal solutions, pruning solution, and the optimal model fit. Expanding the idea of Mishkin & Pilanci (2023), we show a clear connection between the polytope characterization and the dual optimum. We further derive novel characters of the optimal set of neural networks, the loss landscape, and generalize the result to different architectures.
Finally, it is worth pointing out that regularization plays central role in modern machine learning, including the training of large language models Andriushchenko et al. (2023). Therefore, including regularization better reflects the training procedure in practice.

---

Published as a conference paper at ICLR 2025
m 171 +
M
+1
771
M
min(m* + M +1)
m: number of neurons
A schematic that illustrates the staircase of connectivity. This conceptual figure de- scribes the topological change in solution sets the number of neurons changes in high-level manner. Connected components that are not singletons are shown as blue sets, whereas singletons depicted as red dots. When m mm" there are only finitely many red dots. When m m² + 1, there exists a connected component that is not a singleton, i.e. blue set. When m M there exists connected component which is singleton, i.c. red dot. When m 2 M 1, there is no red dot. At last, when m 2 min(m" + M + 1}. there is single blue set.
Figure 1:
More importantly, adding regularization can change the qualitative behavior of the loss landscape and the global optimum Wang al. (2021b): for example, there always exist infinitely many op- timal solutions for the unregularized problem with ReLU activation due to positive homogeneity. However, regularizing the parameter weights breaks this tie and we may not have infinitely many optimal solutions. It is also possible to design the regularization for the loss landscape to satisfy certain properties such as no spurious local minima Liang et al. (2022), Ge et al. (2017) or unique global optimum Mishkin & Pilanci (2023), [Boursier & Flammarion (2023). Understanding the loss landscape regularized neural networks is not only a more realistic setup but can also give novel theoretical properties that the unregularized problem does not have.
The specific findings we have for regularized neural networks are:
The optimal polytope: We revisit the fact that the regularized neural network's convex reformu- lation has a polytope as an optimal set Mishkin & Pilanci (2023). We give a connection between the dual optimum and the polytope.
The staircase of connectivity: For two-layer neural networks with scalar output, we give critical widths and phase transitional behavior of the optimal set the width of the network changes. See Figure [ for an abstract depiction of this phenomenon.
Nonunique minimum-norm interpolators: We examine the problem in Boursier & Flammarion 2023) and show that free skip connections (i.e., an unregularized linear neuron), bias in the training problem, and unidimensional data are all necessary to guarantee the uniqueness of the minimum-
norm interpolator. We construct explicit examples where the solution is not unique in each case, in- spired by the dual problem. In contrast the previous perspectives Boursier Flammarion (2023). Joshi et al. (2023), our results imply that free skip connections may change the qualitative behavior of optimal solutions. Moreover, uniqueness does not hold dimensions greater than one.
We extend our results by providing general description of solution sets of the cone-constrained group LASSO. The extensions include the existence of fixed first-layer weight directions for parallel deep neural networks, and connectivity of optimal sets for vector-valued neural networks with regularization.
Generalizations:
The paper is organized as follows: after discussing related work (Section 1.1 and notations (Sec- tion 1.2), we discuss the convex reformulation neural networks as preliminary in Section 2 Then we discuss the case of two-layer neural networks with scalar output in Section 3, starting from the optimal polytope characterization (Section B.I), the staircase of connectivity (Section 3.2). and construction of non-unique minimum-norm interpolators (Section The possible generalizations are introduced in Section 4 Finally, we conclude the paper in Section Detailed explanations of the experiments and proofs are deferred to the appendix.
2

---

Published as a conference paper at ICLR 2025
1.1 RELATED WORK
Convex Reformulations of Neural Networks Starting from Pilanci & Ergen (202).. series of works have concentrated in reformulating neural network optimization problem to an equivalent convex problem and training neural networks to global optimality. It has been shown that many different existing neural network architectures with weight decay have such convex formulations, including vector-valued neural networks Sahhnne et al.] (2020), CNNs |Ergen & Pilanci (2020), and parallel three-layer networks Ergen & Pilanci] (2021). Furthermore, properties of the original non- convex problem such as the characterization of all Clarke stationary points Wang et al. (2021b), and the polyhedral characterization of optimal set Mishkin & Pilanci (2023) have also been discussed.
Connectivity of optimal sets of neural networks Mode connectivity is an empirical phenomenon where the optimal parameters of neural networks are connected by simple curves of almost similar training/test accuracy Garipoy et al. (2018). An intriguing phenomenon itself, it has given rise to theoretical analysis of the connectivity of optimal solutions: to name few. |Kuditipudi et al. (2019) introduces the concept of dropout stability to explain such phenomena, Zhao et al. (2023) uses group theory to understand the connected components of deep linear neural networks, and Akhtiamov & Thomson (2023) introduces theory from differential topology to understand mode connectivity. Per- mutation symmetry the parameter space also plays an important role in understanding connectiv- ity. Simsek et al. (202T) shows that assuming a unique global minimizer modulo permutations of certain size, increasing the size of each layer by one connects all global optima. Unfortunately. their assumption does not hold in our case (Appendix G A similar characterization is also done in Brea (et al. (2019), where saddle points with permutation symmetry are connected. [Sharma et al. (2024) further discusses different notions of linear connectivity modulo permutations. A different line of work concentrates on the connection between overparametrization and connectivity of solutions: the main insight here is that when the model is as large as the number of data, the solution set becomes connected Nguyen (202T), Nguyen et al. (202I). Nguyen (2019). Cooper (202T) has a similar con- nection for overparametrized networks, where they characterize the dimension of the manifold of the optimal parameter space.
Phase transitional behavior of the loss landscape Here introduce existing work in the literature that gives a characterization saying "adding one more neuron can change the qualitative behavior of the loss landscape", hence having the notion of critical model sizes. We reiterate Nguyen| (2021) and Simsek et al. (202T), where adding one neuron changes the connectivity behavior of the optimal set. Liang et al. 2018) adds an exponential neuron, which is a specifically designed neuron, along with a specific regularization to eliminate all spurious local minimum. Venturi et al. (2019) has the idea of defining upper/ / lower intrinsic dimensions of the training problem in the unregularized case, and shows that the quantity is related to whether the training problem has no spurious valleys. [i] cet al. (2022) discusses a critical width m where m 2 m=, all suboptimal basins are eliminated for certain activation functions. They also discuss how m is related with the number of data.
Loss landscapes and optimal sets of regularized networks Freeman & Bruna (016) discusses the loss landscape of the population loss along with a certain regularization, and proves the asymptotic connectivity of all sublevel sets as m increases. [Betti et al. (2022) also introduces an asymptotic landscape result for regularized networks. (Heffflle & Vidal (2017) deduces the loss landscape of parallel neural networks with the lens of convex equivalent problem, and shows that when the width m is larger than a certain threshold, there are no spurious local minima. Kunin et al. (2019) analyzes regularized linear autoencoders and points out the discrete structure of critical points under some symmetries. [Bccarell et al. (2024) bounds the Betti number of the sublevel set of the loss landscape for Pfaffian activations, discussing topological complexity of sublevel sets for both the unregularized and the regularized case. On the empirical side, Yang et al.] (202T) considers certain metries to consider the mode connectivity and sharpness of the landscape of regularized neural networks, and indeed show that larger models tend to have more connected solutions. A few work design specific regularization to make the loss landscape benign, removing spurious local minima and decreasing paths to infinity Ge et al. (2017), Liang et al. (2022).
Properties of unidimensional minimum-nore -orm interpolators Training minimum-norm interpola- tors for unidimensional data can lead to sparse interpolators Parhi & Nowak (2023). When we do not penalize the bias. Savarese al. (2019) has an exact characterization of the interpolation problem in function space, and Hanin (2021) completely characterizes the set of optimal interpolators. From the construction of optimal interpolators, it is natural that there exist problems with continuum of
3

---

Published as a conference paper at ICLR 2025
infinitely many optimal interpolators. A recent work by Nakhleh al. (2024) extends this setup to vector-valued networks and shows almost-sure uniqueness of a minimum norm interpolator. On the other hand, Boursier & Flammarion (2023) recently showed that when penalize the bias with free skip connections, we have a unique optimal interpolator. Furthermore, under certain assumptions on the training data, the optimal interpolator is the sparsest. Empirically, it has been believed that having a free skip connection does not affect the behavior of the solution Boursier & Flammarion (2023 Joshi et al. (2023).
1.2
PROBLEM SETTING AND NOTATIONS
We are interested in training neural network with regularization and ReLU activation, namely the optimization problem
min [(fo(X).v) + (R(()).
(1)
ØERP
Here, X Raxd is the data matrix, y RR" is the label vector, 0 RP the concatenation of all parameters of the neural network, fo the parametrization, 3 > 0 strength of the regularization, L R _ + E the convex loss function, and R: R2 18 the regularization.
We have two different objects of interest in the notion of optimal sets: the optimal solution set in parameter space and the set of optimal functions
O :- arg min ((fo(X), v) + (R(()) CRP F = (6
deRr
where F the set of functions f Rd + R. The notion of optimal functions will mostly be where we discuss minimum-norm interpolators. Note that O* regards parameters with permutation symmetry as different parameters.
discussed in Section 3.3
Next, we clarify the notion of connectivity in this paper. We say two points x. y E S is connected in 5 for two points I, E S, there exists a continuous function
[0.1] - S that satisfies [(0) x, f(1) y. We say S is connected if for any two points x, E S, x and y are connected in S. Also, an isolated point x in S means a point that has no continuous path from x to S - {x}.
At last, clarify the notations. the notation L(condition (AA) is defined for a scalar, vector, ma- trix that notes if the entrywise condition is met, the value is I, and else O. Note [m]] = 21, ... m)
ll as the l2 norm, ||-||r the Frobenious norm, (-)+ as the ReLU function, and diag the diagonal matrix given a vector. By a hyperplane arrangement, we mean a diagonal matrix diag(1(Xh 2 0)) for vector h E Rdd When we write D; for i [P], we mean all possible hyperplane arrangements generated from the data matrix X E B hence P means the number of all possible arrangement patterns. We also use the notation K. {u (2D; - I)Xu 0} for E [P] unless specified differ- ently (in vector-valued networks we will). By a + b, we mean the concatenation of two vectors(or matrices) a and b: if E E and b e E", a matrices, the notation A, means the i-th row of A, A.; means the i-th column of A, and for vector v, U.A denotes the k--th entry of v. We note the matrix inner product (A, B)M M = tr(A" B).
Rm-", (a:) denotes 0n + ag @ ..... ap. For
CONVEX REFORMULATIONS
Our main proof strategy will be introducing equivalent convex reformulation of the training prob- lem first introduced in Pilanci & Ergen (2020). In this section, we demonstrate the concept by giving an example for two-layer scalar output networks with weight decay.
Consider the optimization problem in equation 3
8 m
p"
min {wy Ory 1am1
L
Σ (Xw,)+aj
M (1w5 +
(3)
2
The variables wy E R2,ay E R for j E [m]. When the width m of problem in equation satisfies
m 2 m² for critical threshold m² < have an equivalent convex problem given cone- constrained group LASSO,
P D2X - vz).y -(x +
P
Prvx 1=
min 1P K.M.K
Σ i=1
Σ (1/uslla + l12)12).
(4)
4

---

Published as a conference paper at ICLR 2025
The intuition of convexification is constraining each variable at certain convex so that the model looks linear in that region, and applying an appropriate scaling to deal with regularization.
As equivalent convex problem, the optimal values p and Pevx equal. Morcover, from solution (u,, um) of equation sstissfynng m = =E= ((u; o 0) + [(u; # 0), we can recover the solution of equation with m neurons by a solution mapping (w;, 05) = (u// V1lu212.. (
for i E [a]. (Wi+a 0i+aa) (v:/v 11
[|0a]12) for i E [m al. without loss of generality (m - a].
assuming u, A for E [a] and vi + 0 for
The problem in equation has convex dual given as
max d' [uT(Xu)+ SP, VIuu
(v),
(5)
where I.¹ is the convex conjugate of T((,.) y) and y denotes the dual variable. Note that strong duality holds and p" = Poyx d' satisfied when m 2 m Furthermore, we will see that the dual
optimum v" determines the optimal set of both the convex problem in equation El and the original problem in equation 3
TWO-LAYER SCALAR OUTPUT NEURAL NETWORKS
3.1 THE OPTIMAL POLYTOPE
We first describe the optimal set of the problem in equation 4 where L is strictly convex. Note that the polytope characterization was first done in Mishkin & Pilanci (2023). Here, we emphasize the role of dual optimum in choosing the unique directions. To illustrate the solution set of equation 4 we introduce the notion of an optimal model fit and further characterize it as a singleton.
Proposition 1. Mishkin & Pilanci (2023) Let the optimal solution set of equation as O If the loss function L is strictly convex, the optimal model fit is unique, i.e. the set of optimal model fit
C, - Σ (u of (u), (
e0r = {x²} for some y" R
The solution set of equation is given as Theorem] I For a formal statement see Theorem
Theorem 1. (The Optimal Polytope, informal) Suppose is a strictly convex loss function. The di- rections of optimal parameters of the problem in equation f noted as u,, 02 are uniquely determined from the dual optimum v". Moreover, the solution set of equation 4 jis the polytope.
- (een, lc, 20 E
P. Σ
P =
DiXu, - D;X = 1² RdP
(6)
for the unique optimal model fit y defined in Proposition 7
Note that p is invariant under different choices of v², because they all correspond to the solution
set of equation 4 Hence, we use D for simplicity. For a geometric intuition of v²", see Appendix G
Theorem implies that equation 4 has a unique direction for each u, Us where i E [P]. which is determined by solving the dual problem. The intuition for this fact is quite clear: when we assume there exist two different solutions (u,, vi) and (u(, 2/) where u; and u/ are not colinear for
some i E [P]. ((u: + 22) (v; + v()/2), has a strictly smaller objective because L is strictly convex and ||a||2 + ||b||2 ||a + bil2 with equality only when and b are colinear. However, Theorem D implies further, that for any conic combination of such vectors D; ú, and DD ū; that sum up to y" becomes an optimal solution of equation 4
Another implication of Theorem is that for all stationary points of equation 3 there exists a finite of possible first-layer weight directions. For a formal statement see Corollary C.I
Corollary 1. Denote the set of Clarke stationary points of equation 3 Jas Oc. The set of directions of the stationary point U { (w////wlle (w, an) E θc, wi + 0 is finite, and is determined by the dual optimum of subsampled convex problems.
5

---

Published as a conference paper at ICLR 2025
The result follows from using the fact proven in Ergen & Pilanci (202)) where all stationary points of equation 3 are characterized by the global minimizer of the subsampled convex program that has the same structure with equation 4 The implication shows that not only the global minimum but the stationary points of equation also have a structure that is related to the convex problem.
3.2 THE STAIRCASE OF CONNECTIVITY
One significance of this characterization is that when m m", can relate the optimal solution set of the nonconvex problem in equation 3 with the subsets of equation 6 with certain cardinality constraints. Specifically, the eardinality-constraie {{{
set
P P" (m(m) == (u,, D (u,, 1i) E P Σ
I(u, + 0) + 1(0, + 0) S m )
C R2dP
(7)
will determine the solution set of equation 3 namely O (mm),, when m 2 m We write O" (m) to emphasize the dependency of m, since we illustrate a ppase-transiiionn behavior as m changes. For a formal definition of @* (m) see Appendix D The cardinality constraint is the main reason behind the staircase of connectivity: if m were to be unbounded, the optimal set would be a single con- nected polytope. However, as m becomes smaller, certain regions in the polytope are not reachable, possibly becoming disconnected.
Our proof strategy is first observing phase transitional behaviors in the cardinality-constrained set P' (m)) and linking the connectivity behavior of (m) and O* (m) with appropriate solution map- pings (Definition D.7] Definition D. Aside from the proof of Theorem the machinery develop can potentially be applicd to extend other topological properties of P (m(m) to (m)).
Theorem 2 states the staircase of connectivity informally. For formal statement and precise definition of critical widths see Theorem D.2 Note that we get rid of the trivial case where P =
(0 } by assuming (w;, ) + 0) O* (m) exists for some m (Proposition D.I.
Theorem 2. (The staircase of connectivity, informal) Denote the optimal solution set of equation 3 in
parameter space as O" (m) C (d4+1)m Suppose L is strictly convex loss function and there exists (w;, ) * (0,0) 0) E (m) for some m. We have critical widths m M that determine the phase transitional behavior of the solution set. Specifically, as m changes, we have that when
(i) m m", O' ('m)) is finite set. Hence, all solutions are disconnected to each other.
(ii) m 2 m. + 1, there exists A + A' E 6* (m) and path in O (m) connecting them.
(ii)) M (7m) is not a connected set. Moreover, there exists an isolated point in O (m)).
(iv) m > M 1, permutations of the solution are connected with no isolated points in (*)).
(v) m > min(m² + -MM + 1}, the set O* (m) is connected.
Figure I demonstrates Theorem 2 at a conceptual level. When m = m., the solution set has discrete structure. One way to see the fact is that when of the polytope P hence they have a discrete and isolated structure. When m 2 m= + 1, we have a trivial "splitting" operation that connects which leads to the existence of a "blue set"(a connected component with infinitely many solutions) in Figure D When m = M the solution having linearly independent first-layer weights with maximum cardinality corresponds to the isolated point in θ* (MM).. When m 2 M + 1, on the other hand, any solution connected with permutations of the same solution. The proof follows from first creating zero slot in the first layer weights and using the zero slot to permute. The idea of the proof identical to that of Simsek al. (202T), though the details differ. At last, when m Z min + M n+ 1}. the whole set is connected: m + M is obtained from first transforming the solution to have linearly independent flyst weights and interpolating the solution with minimum cardinality. n-1 follows from the fact that P' (n++1) 1) is connected, which needs a more sophisticated argument. For details see the proof in Appendix D Note that there exists algorithms that can exactly
m". the solutions vertices
solutions with m² nonzero first-layer weights,
compute these critical widths Remark D.I
From Haeffele Vidal (2017), we know that when m 2 n + 1 we have that all local minima are global (Theorem 2, Haeffele & Vidal (2017)) and moreover we have path with non-increasing

---

Published as a conference paper at ICLR 2025
m m 171 171
Figure 2: Staircase of connectivity for a toy example. The figures above the horizontal line show the toy problem's loss landscape as the width changes. The red star denotes single optimal solution while the blue line denotes a continuum of optimal solutions. The figures be- low the horizontal line show the corresponding optimal functions. The red/blue functions corre- spond to the functions parametrized by the red/blue sets in the loss landscape. Note that when 3 = min(m* +M, n + 1}, there exists continuous deformation from one solution to other.
(v) and objective to a global optimum starting from any point Vidal et al. (2022). With Theorem 2 (v) this fact, we can construct path with non-increasing objective from any point to any global minimum. The path is clear: starting from any point, use the path in Vidal et al. (022). to move to any global minimum.
Then use theorem2-vv
Corollary 2. Consider the problem in equation 3 with m 2 + 1. For any parameter 0 (wi,, O4)) ) there is a continuous path from any global minimizer 0" with nonincreasing loss.
Moreover, Corollary 2 iimpies the connectivity of all sublevel sets when m 2 + 1. This extends the result of Nguyen (2019) to regularized networks. For a more formal statement see Corollary D.2 D.22
Corollary 3. (Informal) Consider the problem in equation 3 with m 2 + 1. All sublevel sets of the loss function connected.
Example demonstrates Theorem 2 for toy optimization problem, which is solving regularized regression problem with two data points.
Example 1. (Demonstrating the staircase of connectivity for a toy example) Consider the dataset
{( 1 ((-33, 1), (v3,1) 1)} and the regularized regression problem with bias
Σ (a.x, + b:) - Vi
of +b))
min Pm
((0,00;.0))
2 5=1
2
In Figure 2 we plot the loss landscape and the corresponding optimal functions when B 0.1 for m 1,2.3.
The upper half of Figure 2 illustrates how the loss landscape looks near the global minima, and visualizes the optimal solution set for m = 2.3. The lower hulf of Figure shows the optimal learned function for m = 1, 3. The black dots are the datapoints, the red dots correspond to the optimal model fit y², and the red/blue functions correspond to the functions parametrized by the red/blue sets in the loss landscape, respectively.
When 2, two different functions are shown. This is because the connected component with infinitely many solutions emerges from the split of a single neuron corresponding to the same optimal function in F². When = 3. we have sequence of functions that continuously deform from to another with the same cost. For details on the solution set of the training problem, parameterization of optimal functions, and how the loss landscape is visualized, Appendix
7

---

Published as a conference paper at ICLR 2025
3.3 NON-UNIQUE OPTIMAL INTERPOLATORS
In this section, we will see how the dual problem can be used to construct specific problem instances that have non-unique interpolators. There are three different setups of interest. First, the minimum- norm interpolation problem with free skip connection and regularized bias (where we denote as SB (Skip connection; Bias)) refers to the problem in equation namely
Σ Elaa: l2 + +b 0f, subject to Xao + bo + Σ EXa +x1)+611)+0 - (8)
Inin
The parameters satisfy a, E Rd and b,, 02 E R for i E [m] U (0), and E IR" is vector of ones. The term "free skip connection" arises, as we have skip connection, i.c. the linear neuron do. that is not regularized. Next, we discuss the minimum-norm interpolation problem without free skip connections and regularized bias (NSB: No-Skip; Bias), which is the training problem in equation S with an additional constraint do bo 0. At last study the minimum norm interpolation problem with free skip connections but without bias (SNB: Skip; No-Bias), which is the problem in equation & with b; = 0 for all E [m] {0). Also, note that the width m is also optimized.
In Boursier & Flammarion (2023). it was proven that for unidimensional data, i.e. when d = 1, the of all optimal functions F of equation 8 is a singleton. When d >> it is not the case. This fact implies that to extend Boursier & Flammarion (0233 to higher dimensions, we may need additional structures besides free skip connections.
Proposition 2. When X E TR=x2, y E R,, we have a dataset (X. y) that has non-unique minimum- norm interpolator both for the SB and SNB problem in equation X
When we have no free skip connections, i.e. the case of NSB, for d we have class of data that has infinitely many optimal interpolators. The construction follows from making the dual problem ma j²" (Xu)+I have linearly dependent solutions by forcing n + optimal solutions. For a rigorous construction of (X, 1). see Proposition E.4
Proposition 3. (A class of training problems with infinitely many optimal interpolators, informal) Consider the NSB problem equation 8 with d For all n Z 2, we can construct infinitely many different datasets (X, y) having infmitely many minimum-nore interpolators.
In the following example, we give geometric description of finding the dataset (X,y) and the continuum of optimal interpolators for π n= =5 5.
Example 2. (Example of class of non-unique optimal interpolators) Consider the figure in Fig- ure 3a Following the arrow, we can find sns Sn-1,-- -1 defined in Proposition [.4] and can find
that each s, has norm 1, 8n = [0, 1]T and Un ////,,1//TT For the example in Figure 3a the data and y can be chosen
5t
7 tan
9x
11x IT.
x taan 3 tan
24 tan
24 tan
24 y ~ 194, 29, 24, 20, 20
24
3h show the continuum of optimal interpolators. We can that there are infinitely many interpolators with the same cost. A magnification of the range x E [-8, 0] is given to emphasize that the interpolators are indeed different. We can also see from Figure 3c that gradient descent learns the continuum of optimal interpolators. Here we set m = 10. For details on the formula of optimal interpolators, see Appendix
Figure
(a) The planar geometry
(b) Zooming in x [-8,0] (c) Trained interpolators
Figure 3: A demonstration of non-unique interpolators for 5. Figure 3al shows the geometric construction behind finding e s proposed in Proposition Figure Bhshows the continuum of optimal interpolators, and Figure 3c shows the learned interpolators trained by gradient descent.
8

---

Published as a conference paper at ICLR 2025
Proposition 3 demonstrates that understanding the optimal solution set with dual optimum enables us to enforce non non-uniqueness to the solution set. Moreover, these examples are not constructed case- by-case, but from geometric structure that is motivated by the object Qx {(Xu)+ + || S 1),
the convex set Conv(@x U - -x), and its supporting hyperplane.
Experimentally, the existence of free skip connections does not seem important in the behavior of the solution [Bursier Flammarion (2023). Joshi et al.] (2023). However, note that when there skip connection, there exists training problems where the minimum-norm interpolator has infinitely many solutions. Furthermore the interpolators in Example [T and Example 2 may have n breakpoints even with Assumption 1 in Boursier & Flammarion (2023) which can never be the sparsest interpolator. Hence, at least theoretically. free skip connection plays sigmificant role in guaranteeing the uniqueness and sparsity of the interpolator, along with penalizing the bias. Note that these different interpolators may have drastically different behavior for points not in the training set. For example, as x +o0, the difference between any two different interpolators diverge.
4 GENERALIZATIONS
In this section, we will extend our results from Section B to more general training setup. We use the fact that for networks of sufficiently large width, training neural network can be cast as a cone- constrained group LASSO problem Mishkin & Pilanci (2023). Analogous to Theorem |
we first
derive the optimal set of a general cone-constrained group LASSO in equation 9
P
Q Σ
P
min R.C.EYEEEEDD
L
A,0;
B, v) + B Σ (.,).).
(9)
Here, A,, B, E Raadd 01, E IRd RR. E R", Ci, Dr are cones, cones, R2 is the regularization (which a subspace V, C IRd and satisfy V: n nc, * 0), B > is the regularization strength, and L : R2 x _R" + R is convex but not necessarily strictly convex loss function. The assumption that R. is norm natural because it will help the training problem find a simpler solution. Equation (9) enables the analysis of many different training setups, including two- layer networks with free skip connections, interpolation, vector-valued outputs, and parallel deep networks of depth 3, extending the results in Section
we assume to be a norm defined
4.1 DESCRIPTION OF THE MINIMUM-NORM SOLUTION SET
The idea to derive the optimal set of equation 9 is essentially the same as deriving the optimal set of equation we consider the dual problem and use strong duality obtain the wanted result. The exact description of the optimal set is given
P Pron = ((s)
Bis: C, 0, O, (Bf'², O, Σ G,O, BBss
si) "''",,))
0, D.
(10)
First, Cy is the set of optimal model fits which was defined Proposition We have that 0, is contained in certain set, which is an analogy of the optimal polytope in the direction of each variable is fixed. Theorem is a special case where the of optimal directions is a singleton. Finally, we have constraint given to variables without regularization, which is also derived from the dual formulation. For detailed derivation see Theorem F1
Given the expression in equation 10 we can extend our results in Theorem Tnn Theorem Saaerrem@@drreee directly to the interpolation problem (Proposition F.I Proposition F.2). That is because for the interpolation problem, C, is a singleton and the set θ is also a singleton. We can also find the optimal set characterization the interpolation problem with free skip connections (Proposition the dual variable has satisfy (XT=" v², s) 0 for all s E Rd meaning XT 0 is given as an additional constraint for the dual problem. The additional constraint is the main reason why we have qualitatively different behavior in uniqueness when we have free skip connections.
Here,

---

Published as a conference paper at ICLR 2025
4.2 VECTOR-VALUED VALUED NETWORKS
Now we turn to two-layer neural networks with vector-valued outputs, namely the problem 13 + +
min (10 1m
(Xma)+ - YI
(11)
where w; E [dxx Si Rexx and E R The vector-valued problem is known to have a convex reformulation Sahiner et al. (2020), which is given
min V. 2
D r + 3 Σ V Vilk,,
x=1
The norm ||V|,,,. defined as |Vilk,, = min 8.1. V E (MC,, for KG conv (ug 1(2D; X) 2 0, |lug" I|. I 1}. and V; span (ug² (2D; (2D; T)xu 2 0,g E R*).
The problem falls in our category of equation and we can describe the optimal set of the problem completely. With appropriate solution maps, we can describe the optimal set of the nonconvex vector-valued problem in equation [1 (Proposition F.5 and the same idea can be applied to describe a subset of the optimal solution set for deep networks (Theorem F.2 A direct implication extends the loss landscape result in Corollary 2 to vector-valuct networks.
Corollary 4. Consider the problem in equation
7 with 2 ne 1. For any == (wi, 2:) )=
(d++o)m there exists a continuous path from 0 to any global optimum 6* with nonincreasing loss.
4.3 PARALLEL DEEP NEURAL NETWORKS
Finally, we extend the characterization to deeper networks. Convex reformulations of parallel three- layer neural networks have been discussed Ergen Pilanci (202T) Wang al. (2021a). The specific training problem we are interested in is
min m.( (M.WW.,.2.... Ots y
Σ W
I + ||22211 |
Σ ((WWi)) 42) y- (12)
The size of each weights are Wi; E Rddmm, w2: E IRm and oi E R. The dual problem of the con- vex reformulation can be understood as optimizing a linear function with cone and norm constraints, and we have analogous results of the optimal polytope. Specifically, columns first-layer weights as a set of finite vectors (Theorem 3). The result suggests that our re- sults are fairly generic, and could be generalized other deep parallel architecture with appropriate parametrization. For detailed proof see Appendix(F [F]
have the direction of the
Then, there are only finitely many possible values of the direction of the columns of W Moreover, the directions are determined by solving the dual problem maxijW, $111/ 1a 1V²)* ((XW1)+ when y + O.
Theorem 3. Consider the training problem in equation 12
5 CONCLUSION
In this paper, we present an in-depth exploration of the loss landscape and the solution set of reg- ularized neural networks. We start with two-layer scalar neural network the simplest case and demonstrate the properties of the set, including the existence of optimal directions, phase transition in connectivity, and non-uniqueness of minimum-norm interpolators. Then, we give a more general description on the optimal set of cone-constrained group LASSO and extend the previous results to a more general setup.
Our paper may be extended in multiple ways. One interesting problem that is left is. what is the right architecture to ensure the uniqueness of the minimum-norm interpolator for high dimensions, as free skip connection itself does not help. Another interesting problem is showing 'almost sure uniqueness' of problem equation up to permutations: intuitively, from the examples we show, it can be speculated that the solution of the dual problem max (Xu)++ subject to ||w]| < 1 is unlikely to have "too many" optimal solutions. Hence is likely that the dataset that makes the minimum-non norm interpolator non-unique is very small. We conjecture that the set will have measure in ? and leave it for future work. At last, extending the optimal polytope/connectivtty results to tree neural networks Zeger al. (2024) with arbitrary depth could be meaningful contribution.
10

---

Published as a conference paper at ICLR 2025
REPRODUCIBILITY STATEMENT
The only randomness that occurs from our experiments are Figure 5a Figure
5b
Figure 6a and
Figure 6bb where different initialization may lead different learned interpolators. We set random seeds properly to make all results reproducible. We used a laptop to do the experiments, and provided the code to generate the figures. Code available at wwwp://tw..o.oollaaaaaaalaoooosa convex-duue -anvx--duaity
ACKNOWLEDGEMENTS
This work was supported in part by the National Science Foundation (NSF) under CAREER award CCF-2236829, in part by the U.S. Army Research Office Early Career Award W911NF-21-1-0242, and in part by the Office of Naval Research under Grant N00014-24-1-2144.
REFERENCES
Samuel K Ainsworth, Jonathan Hayase, and Siddhartha Srinivasa. Git re-basin: Merging models modulo permutation symmetries. arXiv preprint urXiv:2209.04833 2022.
Danil Akhtiamov and Matt Thomson. Connectedness of loss landscapes via the lens of morse theory. NeurIPS Workshop on Symmetry and Geometry in Neural Representations, pp. 171- 181. PMLR, 2023.
Maksym Andriushchenko, Francesco D' Angelo, Aditya Varre, and Nicolas Flammarion. Why do we need weight decay in modern deep learning? arXiv preprint arXiv:2310004415, 2023.
Alberto Bietti, Joan Bruna, Clayton Sanford, and Min Jae Song. Learning single-index models with shallow neural networks. Advances in Neural Information Processing Systems, 35:9768-9783, 2022.
Etienne Boursier and Nicolas Flammarion. Penalising the biases norm regularisation enforces sparsity. Advances in Neural Information Processing Systems, 36:57795-57824, 2023.
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Johanni Brea, Berfin Simsek, Bernd Illing, and Wulfram Gerstner. Weight-space symmetry in deep networks gives rise permutation saddles, connected by equal-loss valleys across the loss land- scape. arXiv preprint prXiv:1907.02911 2019.
Maria Sofia Bucarelli, Giuseppe Alessio D' D'Inerno, Monica Bianchini, Franco Scarselli, and Fab- rizio Silvestri. A topological description of loss surfaces based on betti numbers. Neural Net- works, pp. 106465, 2024.
Yaim Cooper. Global minima of overparameteriize neural networks. SIAM Journal Mathematics of Data Science, 3(2):676-61,, 2021.
Thomas M Cover. Geometrical and statistical properties of systems of linear inequalities with ap- plications in pattern recognition. IEEE transactions on electronic computers, (3):326-334, 1965.
Tolga Ergen and Mert Pilanci. Training convolutional relu neural networks in polynomial time: Exact convex optimization formulations. arXiv preprint arXiv:2006.14799 2020.
Tolga Ergen and Mert Pilanci. Global optimality beyond two layers: Training deep relu networks via convex programs. In International Conference Machine Learming, pp. 2993-3003, PMLR, 2021.
Tolga Ergen and Mert Pilanci. The convex landscape of neural networks: Characterizing global optima and stationary points via lasso models. arXiv preprint arXiv:2312. 12657, 2023.
Daniel Freeman and Joan Bruna. Topology and geometry of half-rectified network optimization. arXiv preprint orxiv:161 101540, 2016.
11

---

Published as a conference paper at ICLR 2025
Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry P Vetrov, and Andrew G Wilson. Loss surfaces, mode connectivity, and fast ensembling of dnns. Advances in neural information pro- cessing systems, 31, 2018.
Rong Ge, Jason Lee, and Tengyu Ma. Learning mee-hidden-lan layer neural networks with landscape design. arXiv preprint 1rXiv:171..00555 2017.
Philipp Grohs and Gitta Kutyniok. Mathematical aspects of deep learning. Cambridge University Press, 2022.
Benjamin D Haeffele and René Vidal. Global optimality in neural network training. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 7331-7339, 2017.
Boris Hanin. Ridgeless interpolation with shallow relu networks in 1d is nearest neighbor curvature extrapolation and provably generalizes on lipschitz functions. arXiv preprint (xXiv:2109112660 2021.
Nirmit Joshi, Gal Vardi, and Nathan Srebro. Noisy interpolation learning with shallow univariate relu networks. arXiv preprint arXiv:2307.1539. 2023.
Kenji Kawaguchi. Deep learning without poor local minima. Advances neural information pro- cessing systems, 29, 2016.
Rohith Kuditipudi, Xiang Wang. Holden Lee, Yi Zhang, Zhiyuan Li, Wei Hu, Rong Ge, and Sanjeev Arora. Explaining landscape connectivity of low-cost solutions for multilayer nets. Advances in neural information processing systems, 32, 2019.
Daniel Kunin, Jonathan Bloom, Aleksandrina Goeva, and Cotton Seed. Loss landscapes of regu- larized linear autoencoders. In International conference machine learning, pp. 2560-3569, PMLR, 2019.
Dawei Li, Tian Ding, and Ruoyu Sun. On the benefit of width for neural networks: Disappearance of basins. SIAM Journal on Optimization, 32(3):1725 1758, 2022.
Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss land- scape of neural nets. Advances in neural information processing systems, 31, 2018.
Shiyu Liang, Ruoyu Sun, Jason D Lee, and Rayadurgam Srikant. Adding one neuron can eliminate all bad local minima. Advances in Neural Information Processing Systems, 31, 2018.
Shiyu Liang, Ruoyu Sun, and R Srikant. Revisiting landscape analysis in deep neural networks: Eliminating decreasing paths to infinity. SIAM Journal on Optimization, 32(4):2777-2877, 2022.
Aaron Mishkin and Mert Pilanci. Optimal sets and solution paths of relu networks. In International Conference on Machine Learning, pp. 24888-24924, PMLR, 2023.
Julia Nakhleh, Joseph Shenouda, and Robert D Nowak. The effects of multi-task learning on relu neural network functions. arXiv preprint arXiv:2410.21696, 2024.
Quynh Nguyen. On connected sublevel sets in deep learning. In International conference ma- chine learning, pp. 4790-4799. PMLR, 2019.
Quynh Nguyen. A note connectivity of sublevel sets in deep learning. 1eXiv:2001.08566. 2021.
arXiv preprint
Quynh N Nguyen, Pierre Bréchet, and Marco Mondelli. When are solutions connected in deep networks? Advances in Neural Information Processing Systems, 34:20956-20969, 2021.
Rahul Parhi and Robert D Nowak. Deep learning meets sparse regularization: A signal processing perspective. IEEE Signal Processing Magazine, 40(6):63-74, 2023.
Mert Pilanci and Tolga Ergen. Neural networks convex regularizers: Exact polynomial-time vex optimization formulations for two-layer networks. In International Conference on Machine Learming, pp. 7695-7705. PMLR, 2020.
12

---

Published as a conference paper at ICLR 2025
Arda Sahiner, Tolga Ergen, John Pauly, and Mert Pilanci. Vector-output relu neural network prob- lems are copositive programs: Convex analysis two layer networks and polynomial-timg algo- rithms. arXiv preprint arXiv:2012.13329, 2020.
Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look in function space? In Conference on Learning Theory, pp. 2667-2690. PMLR, 2019.
Ekansh Sharma, Devin Kwok, Tom Denton, Daniel Roy, David Rolnick, and Gintare Karolina Dziugaite. Simultaneous linear connectivity of neural networks modulo permutation. arXiv preprint arXiv:2404. N404:24404.06498, 2024.
Berfin Simsek, François Ged, Arthur Jacot, Francesco Spadaro, Clément Hongler, Wulfram Gerst- ner, and Johanni Brea. Geometry of the loss landscape in overparameterized neural networks: Symmetries and invariances. In International Conference on Machine Learning, pp. 9722-9732. PMLR, 2021.
Ruoyu Sun, Dawei Li, Shiyu Liang, Tian Ding, and Rayadurgam Srikant. The global landscape of neural networks: An overview. IEEE Signal Processing Magazine, 37(5):95 -00 2020.
Luca Venturi, Afonso S Bandeira, and Joan Bruna. Spurious valleys in one-hidden-layer neural network optimization landscapes. Journal of Machine Learning Research, 20(133))1-344 2019.
René Vidal, Zhihui Zhu, and Benjamin D Haeffele. Optimization landscape of neural networks.
Mathematical Aspects of Deep Learning, pp. 200, 2022.
Yifei Wang, Tolga Ergen, and Mert Pilanci. Parallel deep neural networks have zero duality gap. arXiv preprint arXiv:21 10.06482, 202
Yifei Wang, Jonathan Lacotte, and Mert Pilanci. The hidden convex optimization landscape of reg- ularized two-layer relu networks: an exact characterization optimal solutions. In International Conference Learning Representations, 2021b.
Yaoqing Yang, Liam Hodgkinson, Ryan Theisen, Joe Zou, Joseph E Gonzalez, Kannan Ramchan- dran, and Michael W Mahoney. Taxonomizing local versus global structure in neural network loss landscapes. Advances in Neural Information Processing Systems, 34:18722-18733, 2021.
Emi Zeger, Yifei Wang, Aaron Mishkin, Tolga Ergen, Emmanuel Candès, and Mert Pilanci. A library of mirrors: Deep neural nets in low dimensions are convex lasso models with reflection features. arXiv preprint arXiv:2403.0104 2024.
Bo Zhao, Nima Dehmamy, Robin Walters, and Rose Yu. Understanding mode connectivity via parameter space symmetry. In UniReps: the First Workshop Unifying Representations in Neural Models, 2023.
13

---

Published as a conference paper at ICLR 2025
APPENDIX
A DETAILS ON THE TOY EXAMPLE IN FIGURE 2
In this section, we give details of the toy example in Figure Specifically, illustrate how the loss landscape is plotted, how the set of optimal solutions is derived, and present the models that are found by gradient descent.
One important remark is that "the figure does not directly imply the staircase of connectivity" the fact that two optimal solutions are disconnected in the visualization does not mean disconnect- edness in the optimal solution, and vice versa. The figures are for the illustration of the phenomenon, not the proof.
The optimization problem that we consider is
2
1
8
min bb.
Σ (a,r, + b.)+0: yj
0 af + b2),
2
,=1
where (1),, ((-v3, 1), (v3,1)) and B = 0.1. When we write X = -3 1
E
/3, 1
R=x2 [1. and the first layer weights as U E R 2 second layer weights v IR the
optimization problem can also be written as
B (1111 + 1101)))
min UERaXm .E
- (IUU)) y112 +
2
Let the objective be L(U,v). Note that even when 1, there are three parameters, it is impossible to plot the loss landscape in three-dimensional plot. What we do is plot certain section of the loss landscape, as done et al. (2018), to demonstrate our result.
When m = 1, where VI- 0.53, we plot
F(t, s) = L( 1 [rl),
(rl)
for []. 0,
x
is the only optimum.
When m = 2, where r = -1- 0.5/3, we define
Up 0
V3r/(2v2)
-V3r/(2V2) r/(2/2)
0
U1
U2
r/(2/2)
r
T\/22
%
0
01 =
1/v2
0/2 =
r
Then, we plot
F(t, s) = ((cos(t)Us + 2s(U1 - Uo) + sin(t)U,, cos(f)uo + 2s(u1 - vo) + sin(t)u2).
for (t, s) E [-0.255, 0.6] 1-0.5, 0.3). The optimal solutions here are (t, (0, 0.5) and the line $ = 0. 0.
When m = 3, where
v1 0.58, we define
0..0.0 r,0,0
0
(3r/(2V2)
-V3r/(2V2)
0,
Un =
U
UU2
0
(2V22)
T/(222)
0,r,0
r
0
00
0
r/V2
02
0
r/v2
Then, we plot
F(I, [[cos(() (0n (s)))) sin(s) +sn((())sn()))))))
14

---

Published as a conference paper at ICLR 2025
for (t. [-0.5, x 1-0.5, 1]. The optimal solutions are 0, 2 0 and 0, 2 0.
The contour plot of the loss landscape can be found Figure It clearly shows that the connectivity behavior of the optimal solution changes.
3798
2011
3220
6731
3300
E37
-2.0 -039
0.5
-22
(a)
(b)
2
(c) 3
Figure 4: A contour plot of the loss landscape The three figures show the contour plot the loss landscape shown in Figure We can the staircase of connectivity more clearly.
Figure 5 gives what the gradient descent actually learns for the problem. We can see that gradient descent finds multiple optimal solutions, which verifies our claim that we have continuum of optimal solutions. We present the case both when m 3 and m 5. When m is increased, the model gets less stuck local minima.
10
10
08
0.8
06
0.
(a)
(h) m
Figure 5: Learned functions found by gradient descent The two figures show what functions gradient descent learns for the toy problem Example|] []] For both cases in m 3, 5, either gradient descent gets stuck at a local minimum or finds one of the optimal networks in the continuum of optimal solutions.
At last, show that all optimal functions can be written as
f(x) = Vnl(
3xt
r
Vistt
+ + Vall 33kt
x +
Vnt
)+ + x(( 21)
(V<(1 - 21) -21)
2
2
2
2
where x = 1 3/2 and L E [0, 1/2]. For of = 11/2, 1/2], we know that max//wllas 1i2 (X""(XXu (Xu)+1=
Let's say the optimal model fit
(Xu))+a.
i=1
Then,
(v,8") < Σ (x
W;
I|||u
11z ladl
S 2 1=1
Σ
uu 12 + larl)
1=1
15

---

Published as a conference paper at ICLR 2025
This means the objective has lower bound 2 y112 + 3 y²) and minimum of the lower bound is attained when y" objective is B /82 /4, and when 21 [0, / 10-1/2"" 01 /I 3/2 we have solution with cost B B² /4 hence y" is indeed optimal. v² y y", and use Theorem to find the complete solution set.
3/2. 8/2)T Substitute to that the lower bound of the
16

---

Published as a conference paper at ICLR 2025
B DETAILS ON THE TOY EXAMPLE IN FIGURE
The construction of x follows from Proposition 3 For the particular example we distribute the angles identically, hence we obtain the form in Example 2
The six optimal directions
v3/2 1/2
2222
1/2 [3/2
V6 v2/4 LV v2/4
0
v3/2 1/2
[v222]
Let's note these optimal directions U1 U2, -. Ug- We construct y
20((( + (Xūa)+ + (Xū;)+), which is numerically very similar to [94, 29, 24, 20, 20). Note that the class of optimal interpolators
f(x) (20 7.076t) ) ([2r, 1] #1)+
1] u2)+ (20 13. 13.1623f)((z; 1] ūz) + (13.1590)(zz; 1] u+)+ + (20 (.0811) 1] iss++ + (((x, 1] ū6) +
where E [0, 1.5194) which all have the same optimal cost 60.
Similar to the experiment in Appendix we give an example of the learned functions by gradient descent Figure 6 We set 3 0.1 and solve the regularized problem. Here we find multiple functions optimal: and the important remark is that not all (as some do stuck at local minima), but there exists different interpolators with the same cost.
160
280
120
120
300
60
80-
20-
-0 -6
(a) T7
(b) m 10
Figure 6: Learned interpolators found by gradient descent The two figures show what functions gradient descent learns for the toy problem in Example We set = 0.1 to approximately solve the minimum-norm interpolation problem. For both cases m and m = 10, either gradient descent gets stuck at local minimum or finds one of the optimal networks in the continuum of optimal solutions.
17

---

Published as a conference paper at ICLR 2025
C PROOFS IN SECTION 3.1
In this section, we briefly discuss how Theorem i derived and the intuition behind it. Consider the problem introduced in equation 4 and write its optimal solution set Ø To discuss the solution set, we first define the set of optimal model fits, which was first introduced in Mishkin & Pilanci (2023).
Definition C.1. Mishkin Pilanci 2023) The set of optimal model fits Cyy is defined as
Cg =
Σ D.X (ut - of) (M), 12 V2 E 6*).
When L is strictly convex, which is the case for 22 regression for instance, Cy becomes a singleton Mishkin & Pilanci (2023).
Proposition C.I. (Proposition 7 of the paper) Mishkin & Pilanci (2023) If the loss function L is strictly convex, the optimal model fit is unique, i.e. for the set of optimal model fit
C== DuX of) (1, o0 E
Cy 3v') } for some y² IR
Proof. Assume y1, 1/2 E Cy and yn # y2. Let Σe D,X(u; 12) = y and Σ D; (2X(u--04) =
metel ) Oang. The objective value of y2 for (us, ui) (14, df E Or. Think of (uctol aay is
2
11 + 1/2 L(
Mi u/
ll2 + 11 + 1/ 112
v)
2
which is strictly smaller than
1 2 ((11.v) +
Σ
uoll2 [/lll2 + I v) + 8
E1u4
Σ 1ulll + |14/ll2
The strict inequality follows from the fact that L is strictly convex. Contradiction follows, as we have found parameter that has smaller objective value than the optimal cost.
It is not necessary to characterize Cy singleton to derive the solution set itself (see Section 4.1 However, for the notion the optimal polytope and its application to the staircase of connectivity, we will need that C, is a singleton.
Before proving the optimal polytope characterization, we show that the ū, & introduced Theo- rem can be uniquely determined by solving the given optimization problem.
Proposition C.2. Consider the optimization problem
min v" D;Xu, min - D,Xu,
wES.
wES,
where Fn is an arbitary vector and KG {u ||ull2 S 1}. If the optimal objective is nonzero, there exists unique minimizer.
Proof. The problem equivalent to
min (w") ( u, WES;
which is a linear program on a convex set. We write w = =X" for convenience. Let's say the optimal objective p" and we have two minimizers u², uz. The first thing notice is that |ui 1. The reason is that when ||u || < 1, we can scale it to decrease the objective. Similarly, [uāllp 1. As they are two different minimizers, we know that
(w=)Tui un = (w=)TTss = p- (w*) u + u
2
and ||uj + uGll2 < because ut # us. Scale (uf + w2)/2 to obtain contradiction that of is the minimizer.
18

---

Published as a conference paper at ICLR 2025
Theorem C.1. (Theorem of the paper) Suppose L is strictly convex loss function. The directions of optimal parameters of the problem in equation noted as ū, Uú are uniquely determined from the dual problem.
ū arg min v²² D:Xu if min "' D2Xu -3, 0 otherwise, WES,
NES,
arg min -v" D2X if min WES.
-v" 7 D,XU 3, 0 otherwise.
vES,
where v is any dual optimum that satisfies
v = arg max - (v) subject to |V" D,Xul & Bluull2 Vu E K,, [P].
Here, D&s are all possible arrangements diag(1(Xh 0)) [P], fu |uu|2 1}. Moreover, the solution set of equation 4 is given as polytope,
Pú = -ca,,
P Σ
20 Vie [PE
D,Xūc - D,XU,d = 8² C CRUUP
1=1
(13)
where y is the unique optimal fit satisfying C. = }
Proof. Let's note O* as the solution set of equation 4 Also, fix v" to be any dual optimum. The directions ū. o are uniquely determined from Proposition C.2 Define P to be the set defined in equation 13 note the dependence of P has with y² (though we will see that for any choice of v*, P θ and the choice of v* does not matter).
We first show that O* Pi.. Take point (u,, o O We first know that E (iX(uÇ of) y" from Proposition satisfies
What we would like to do is showing the existence of c,, d2 that
20 u = C,ua, d; 2 0, of deus,
where ū; 82 are
ū. arg min V DiXu u if min wES;
V TT D;Xu -3, O otherwise, wES:
0/ arg min eES,
7 D2X if
min vES,
-3, 0 otherwise. - D,Xo -3,
Consider the Lagrangian
C((u;; 2,20 L(z, v) vF + > (B1lu + + + Σ - D;Xu),
where ui Us E KG. We that
min max C(u,, 11 ( max M
min EKK,, C(uu, v)) 2,v).
V
because is the dual variable that is only related to linear constraints. We can prove the fact rigor- ously by following the reasoning in Boyd & Vandenberghe (2004). We prove the fact for complete- ness.
First, we define the set
A= = ((w D.X(M= v.),8) uz, v K., T(w, v) Σ uu la ||1:||2 S $(),
where AC Rd x R. A is a convex set. Now, denote the optimal value of problem in equation 4 as p". When we define
B = (00 < p'},
is clear that A n B = By the separating hyperplane theorem, there exists (i, (2) E R x R which is nonzero, such that
(z,1) A A pul 2 pp"
19

---

Published as a conference paper at ICLR 2025
and also know 2 0: else t so and contradiction follows. If i > 0 we have [((ue, 2/ (u:, (=) we have that (z) DuX(u: u;)) 2 O, which is simply impossible. Hence,
2 p", and strong duality follows. If J = O, we conclude that for all
J > and strong duality holds.
Moreover, the dual problem
max min C((us, ti)=1, (Mat))
writes
maximize ('(r) subject to B1|u112 2 1 DiXu] Vu E K, [P].
The reason is the following: suppose for some v/ E RR, there exists u/ that satisfies uf E K. and n Dx + Bl]u[l12 < As we can scale t + oo for tu to see that for that v'. (u C((u,, us) 2,))=,,,1/)) = -cc Hence, this v/ cannot be the dual optimum. This means we only need to see the y that satisfies D,Xu + uillel2 22 2 0 for all E K,, E [P]. Similarly, we only need to see v that satisfies -μ² D,Xu + Bluull 2 0 for all 1C, E [P]. Hence, vz
the maximizer of
max min (2,,8) - vT= subject to Bl|ul12 2 | DxXul Vu E E.KK, [P],
and the rest follows.
As strong duality holds, for any primal optimum ((u), v - y the function [( 1i) v.)") attains minimum at ((u) uf (1=.1")) Boyd & Vandenberghe (2004). Note that x" is always y² due to Proposition and replaced by it.
Now,
L((u;, us) 0)) = -(z,,))) - -T= 2 ( + D,Xu,) + Σ (31lusl D,Xu,
D - D.Xoss)
each un becomes the minimizer of B||u||2 + v D2Xu subject to u E KG and each of becomes the minimizer of B1]u[l2- - D,Xu subject to u E K., Recall that v² is a vector that satisfies @||uull 2 Du Vu E K,, E [P], and when u = 0, both B1|u||2+ D'Xu Xu and B1|u[|2--" D u has function value 0. This implies that the minimum of both B||u||2++u* T D; X and 31|u|12 foul22=>** n* D, Xu.
subject to K., is for all E (P). As ((u7, uz ".."" minimizes C((u; 0z) vi) 1: 2,K²),
B| 1l2 + n² D2X = 0, BlluB112 " D2X 0.
We will find q; 2 0, and finding d, will be identical. Let's divide into cases.
When of let G; to find o; that satisfies o crül.
ii) When of + 0, notice that
min v² T weS,
and the optimum is attained ut 4 l2.- To see this, recall that (v*) Bllu|12 0 and (u+)²) DzX D:Xu//luu //lllulla 2 -3 for all nonzero E Kc, which implies that minwes, (u+) D.Xu -- 33. Furthermore, by Proposition C.2 there exists a unique minimizer of the problem minues, (v*) (D")T,XXu and ut/ /| 12 ū. Hence choosing c, = |u, 11 gives & 2 0 that satisfics u. = C Ut. Hence, we have found c 2 0, d, 2 0 that satisfies ut = c, of = d,0 and Pt.
Ee,,,X, (u - of)) =E= (c d, = y², meaning (ug,
Now, we show that P C O". Take an element (caūe, d. E P It is clear that -3. Similarly, if in # 0, we know that ( D,XY, = -3. Also, if ū;, 02 * 0. || = 1, 16,,122 = 1, see the proof of Proposition C.2 why this holds. Now, let's calculate the objective of (c,ū, d. We know
Cæū; E C., dæū E D. If ū. # 0, we know that (v*) (
E. D2X d,o,) y², hence the objective becomes
I(y", + B
Σ G 500
Σ di,
20

---

Published as a conference paper at ICLR 2025
using | 1, 1//1//12 1. Now, as Ei=1 D,X(c,ū d,ē,) yy, multiplying (N*)² on both sides gives Ea. #0 Gi + Ee,fo dj = (V', .3 Hence, the calculated objective becomes
L(v',y) ,v) (v", "">
hence for all points in Pv., the objective becomes constant. We already know that O S P.P... This means all points in Pe- have the same optimal objective value, and P S Or. This finishes the proof.
Corollary C.1. (Corollary of the paper) Consider the optimization problem in equation 3 the sel of Clarke stationary points of equation 3 as Oc. The
Denote
(104, oz) E Co w/ + }].
f=1
is finite, and each direction is determined by the dual optimum of the subsampled convex program.
Proof. From Ergen & Pilanci (003)), we know that all Clarke stationary points of equation have
corresponding subsampled convex problem. More specifically, for any (W,, 0ts ass) Occ we have a convex program with subsampled arrangement patterns D1, D2,... Dm E (D:)
m
m
min M..VER
T.
(>>
D,X(M, v)), 3
Σ
Musl12 + l|0zll2)
and solution mapping
(wi, a.) = (u// V | 2. (12l22))
if u, + 0, 2s +
if
Hence, the set of first-layer directions of Clarke stationary points is contained the set of optimal directions the subsampled convex program. As there are only finitely many subsampled convex programs, and each convex program has a unique set of fixed optimal directions, we know that the
U
W Twyl12
(w,, (w,,, o.) Oc, wy + +0}.
j=1
finite set. Furthermore, applying Theorem to the subsampled convex program leads to the wanted result.
21

---

Published as a conference paper at ICLR 2025
D PROOFS IN SECTION 3.2
In this section we prove Theorem using the cardinalitycconstranned optimal polytope (*(m) defined in equation 7 One thing to have in mind is that are not trying prove that P (m) and O" (m), the optimal set of the original problem in equation 3 with width m, are homeomorphic. Rather, we will argue that certain mappings enable us link the connectivity behavior between P" (m)) and (m) to arrive at Theorem 2
We first start by defining some relevant concepts. As starting point, we define the cardinality of solution.
Definition D.1. The cardinality of solution (u,, 1.) E P is defined as
card((u,, 2i) = Σ 1(4 + 0) + 1(0 0).
We introduce the cardinality- constrained optimal polytope again. Definition D.2. The cardinality constrained optimal polytope P (m) is defined the set
Da (m) { (us, f (u,, ve) E " c o)) S m] C R2d
(14)
One remark is that the largest possible cardinality of pa may be huge: in worst case, it could be that the largest cardinality is in scale of P, which is the number of all possible arrangement patterns. In general, the number of arrangement patterns are O(n)), hence ('mm) consists of a very small portion of P*
The next concept we introduce is the notion of irreducible solutions. This set can be understood as a set of minimal networks discussed in Mishkin & Pilanci (003), and used define the critical widths of the staircase.
Definition D.3. The irreducible solution set is defined as the set Pi (ws, ui) (ui, E (D:XuiJu (D;X vx linearly independent
(15)
One intuition of the irreducible solution set is that the set of "smallest solutions Mishkin & Pilanci (2023)": if the set (D,u,,) Nu. U (D, ) Joy4o is linearly dependent we can find a strictly smaller conic combination using the vectors from {D,Xu; ) U (; Jv The set Pi collection of solutions obtained from repeating this "pruning step" step that finds smaller solutions using linear dependence. A more rigorous definition of pruning is the following. Note that the existence of m with nonzero solution in O* (m) implies P # 0, which is equivalent to having a nonzero element in p We assume the nontrivial case where pa has a nonzero element from now on.
can be understood
Proposition D.1. The following three statements equivalent:
i) There exists that satisfies (w,, a;) #0 (m)) ii There exists (wa, u:) * 0 E P tii) Pi.. # 1
Proof. i) + ii): First assume m > 2P. Consider ((w,,, a4) a=) ui) where & is de- fined in Definition D.8 We know that (u,, vs){ is not solution of zeros, as it were the case, mm (Xw;) = O and (0. would have strictly smaller objective, contradicting (we, ats) m (m)). Now when we write the optimal value of the nonconvex objective Equa- tion (3) with pi,. and the optimal value of the convex objective in Equation 4 with p' P < p².
Also, when we write L as the convex objective, we know that L((u, v) Pm 2 p Hence we have found a nonzero (u,, 1)) that has objective value p², which means there a point in p which is nonzero.
Now let m < 2P. Assume P = {0, )) We know that pz S P and p = 11lv hence 1llvl < pt. On the other hand, the value $ f1ly [ is achievable by setting (0, 0)m which means Pm p². With the same logic, (((w, a; )/ is not a solution of zeros and its objective value
22

---

Published as a conference paper at ICLR 2025
is same Pm which is leading to contradiction that P {(0,0) since (u4, 2t) is nonzero and in P
ii) = iii): We use the pruning step in Definition to find element in Pirr Note that the prun- ing step does not end with 0, as (u, ui)= is not zero and the pruning step should not decrease the objective.
iii) = ii): As P.., 0. there is nonzero solution existence of nonzero solution pp".
Pier- As Pirr P", we know the ii) i): Set = 2P and consider ((u,, 2))) where v is defined in Definition D.7
Definition D.4. Mishkin Pilanci 2023)) Pruning a solution (ua vi) P means repeating: 1. Finding nontrivial linear combination
Σ 3F
C.D,Mu; +
Σ d,D,X =
and without loss of generality assume d1 > 0.
Constructing a solution with strictly less cardinality (ul, w)) = ((1 + eıl)us; (1- v where min (mine, - mind;>0 म, and ct di are defined be the coefficients defined in when U, 14 + 0 and 0 otherwise.
6z
#0 until the set (DXuu) u, U (D,Xe,)u, is linearly independent.
The notion of minimality gives a discrete structure in Pirrs hence the phase transitional behavior follows. The two critical widths of interest are the minimum / maximum cardinality of Pirr We denote
m²
min card((u,, ve) M (M. EP:
(ard u))( (u,,,.__,ER
max
Remark D.1. These widths can be found computationally by the following scheme: for t to n, choosel vectors from the (D,X (x.Xue)e (
where ūe 0; are optimal directions defined in Theorem 7 Check if they are linearly independent and can express y² as the conic combination of the vectors. The first value of that meets both criteria becomes m², and M will be updated each time meets both criteria until t becomes
The two specific discontinuity results we can achieve are the following: Proposition D.2. P* (mm") is finite set.
Proof. Consider two points (ui, Ub) R (u/, 2) P=(m).. same support, i.e. ui * + u/ # 0 and vs * 0 + of # for i E [P]. We know that as P' (mmmm) C Pt.
Suppose the two points have the
Σ D2X (1: 1=== = Σ D,X =().
Now, let's write the indices {ilu, # 0} {aj a2. at
fily # 0} = (b1, ...b..b.b............ ba). We have
that & + 8 S m² as (u;, v)){ Pm(m").. From Theorem for E and db,. d' 2 for E [s) that satisfies
we know the existence of ca,, ca.
ua. Ca, Ua,, V'a = c'. Ta,
Vi E [t].
ub. do, Tby V/. d' Ub.
Vi [s].
This means that
Ca. Da. Tua
Σ dr, Do, X
Σ Das Xun:
Σ dr Xub, = = 2m
and as Ca., do, not all the same, we have that the set
{ [Da, Xum, Him U (Do. (D., Xo,
linearly dependent. Now we apply pruning defined in Definition find an irreducible solution with cardinality strictly less than L + m=. which is contradiction the minimality of m This
23

---

Published as a conference paper at ICLR 2025
implies that two different points in (*m")) cannot have identical support, and the number of points in the set is upper bounded with the number of possible support, which is finite. More specifically,
m
2P j
[P'
Proposition D.3. PM (M)) has an isolated point, i.e. it has a point & P (M*) that has no path in P (M') from p to a different point pl.
Proof. Take the maximal-cardinality solution from (ut, of E Pirr. namely the solution
(4, E P", , (u U o
Je linearly independent,
and card((u), ( = A1 Assume the existence of a continuous function f ; [0, 1] - (M)) satisfying
f(0) = (u., of) S(1) (14, E S()) + 1(1).
Now, write f(t) = (u.(t), and define
(1) So if ū. =0 (I)u(())l2 otherwise,
(t) = S0 if T =0
(1)(2) otherwise,
For definition of ū. 0, see Theorem Some things to notice are:
i) The functions (t), (() [0, R are continuous.
ii) f(t)= = (c, (t), This holds because if ū. # 0, | = 1, and same for E,
iii) E (c,(()) 0) ((d,(t) + 0) S M and Ee (()(0) # 0) + 1(d,(0) * 0) M The
former holds because is path in P (M*), and the latter holds because (u., ef) has cardinality M
(c:(0), d(0)) Is Based on the observations, let's prove that if there exists such f. the set (D,Xuf)upst (D:Xoī Jugyo is linearly dependent. Thus we will arrive at a contradiction and will be able to show that there is no such f. and (uf, of) is isolated.
iv) We know that there exists 1' [0, 1] that satisfies (c(("), because f(0) # f(1).
Let's define f as
P Σ (3))) ((10))))))(()))4()))))) >
f inf 120
t
In other words, & is the instant where f(0) # f(t). From observation iv), we know that 1 E [0. 1]. Another fact that we can deduce is that
Σ (c(0))c((ti)) + (d.(0) d,(ti))² 0.
(16)
The reason is because if ( - c,(tt)) ( > 0, we can find some é that will make (c ct(t e))² (d) - d:(t1 e))² > 0 because of continuity, which contradiction that t is the infremum (because we have found a smaller that makes DP (c:(0) - (1)) + (d,(0) - (1)) > 0). Hence, for / E [0, 4].
(2)
-(a(0)-a(()) + (d(()) - d(t))²
At last, we know that for any > 0, there exists to E (t1, t + E) that satisfies
p
(a(0)) - c(t))) (d((0) - dttt))) > O.
(17)
24

---

Published as a conference paper at ICLR 2025
If there is no (t1,t) t1 c) that satisfies P
d,())) > 0 for some - -,))) (4(()) - dt))))² = 0: hence, the infremum should be strictly larger than L1, which is a contradiction.
e > O, it means that for all E [0, + e2], -=((((()-c(0)) c.)))
Now let's prove the claim that if there exists such f. the set {D;Xu, U of is linearly dependent. From equation 16] we know that
(0)) c4(4), d((0) = d(44) E
Take co > sufficiently small so that for all i E [P] that satisfies (() > 0, c;(1)
> for all t [t 11--0 Eo, t teg. and for all i E [P] that satisfies (0) > 0, di(t) > 0 for all t E [t -00 t t
Such Eo exists due to the continuity of e,, d,. Due to the definition, we know that
P M Σ (cc(00) 0) (0) # 0)
Σ
((a((t) + 0) + ((d((t) # M",
==1
(see observation iii) if any confusion exists), for all E [t1 - c + col. and
Σ (a(()) +0) (().(1) - V [4 - -0, col.
This means that for all / E [41 co: l + to), we know that (0) > 0 <> (()) > and d,(0) > 0 <> (t) > O. For that Eo, we can find top that was defined in equation 17 As too satisfies
P ((a(0)-aak)) + (d(() - de(ten 0, 1=1
((()), # di(tta) Also, (0) > 0 + ca(ten) > 0 and d()) > O & dittr)) > O. Now we have found two different solutions (c((0) 0. (0)o:) (c.(ta,) di (te,) Do) E PMMM), which means that
P E0(0)D, d((0), = y² Σ 1D,0, de(te -
(18)
As (c. (0) + (c: d. di(teo)) and (0) > + (tt,))) > 0, 0,d,(0) > + di(ter) >
0, we can see that equation 18 is two different linear combinations of the set (D,Xuf Fug U {D. lof hence the set (D.Xu h Fu U (D, bop is linearly dependent.
As we claimed, we have arrived at a contradiction assuming a continuous path from (1.: ) Hence the point is isolated.
Next, we pay attention to the connectivity results of (mm).. Our starting point will be noticing that for any (u,,)) P E P which is not in p the pruning mechanism defined in Definition D.4 gives a continuous path into Piry. This means that if we can connect two points in P 0 P* (m) with a continuous path in PD P*(m), the set Pa (m) is connected.
Proposition D.4. Consider (uz, P P*- p'-Pa Pipp Let card((u;, u.), Then, there exists continuous path in PM (m) that starts with (ui, oi) and ends with different point (ul, of) P* (m) n Pirr-
For each iteration of the pruning step, the starting solution and the ending solution is connected by a continuous path. As we iterate, we concatenate each continuous path, hence the resulting path should be continuous. The next thing we have to check is that the path is contained in P* (*()). We can see this due to the fact that in each pruning iteration, the cardinality of the solution does not increase, and the initial cardinality of the solution is m. At last, when pruning ends we arrive at irreducible solution, meaning the final solution we get from pruning is in P* (m) n Pirr
Proof. We will find such path by pruning the solution as in Definition D.4
We have two different strategies to prove the connectedness of P* (m)) One is directly interpolating the two solutions in Pt,,. and increasing m to guarantee the validity of such interpolation. From this, we obtain one critical width m. * + M
25

---

Published as a conference paper at ICLR 2025
Proposition D.5. The set (*mm" + M*) is connected.
Proof. We first prove that two points A, B E P (mm + + are connected with a continuous path in P (mmm + MM).
n Pir n One observation that we make is that A has a continuous path in Pa (m² + A to certain solution Am E Pirr that satisfies card (Am) = m² The construction of such a path is simple: interpolate A and Ams L.. f(t) (1 t) + tAm As we know
Take two points A + B pm +
card((1 - 1) + 1Am) S (Ard(4) + card(Am) & M + +mm,
the path has cardinality I m M The last inequality follows from the fact that A E P and card(A) I M Due to the polytope characterization, P is convex, and the path is in Pt. Combining these two, know the existence of path from A to Am in P (m" + MM).
Similarly, we know the existence of a path from B to Bm in p"(m + M*). At last, we know the existence of path from A. Bm again by interpolating these two. Concluding, for any two A, B E Pd (m= + M*) n P free there exists a continuous path in P* (m" + M
Now, take any two points A' E P (mm M From Proposition D.4 there exists continuous path in P* (m*++M² )M) that starts from A' to a certain Aarr E P +M +M'"~~M""'PPP irr and similarly there exists a path from 3' to Birr. At last, there is continuous path from Airr to Bay in P (m* + +*).
Connect all paths to find continuous path from A' to B' in P (m" + M*).
Another strategy is more involved, which is not directly interpolating two solutions A, B in P but repeatedly interpolating A with parts of B until the two are connected with path. We start with a particular lemma.
Lemma D.1. Suppose we have two linearly independent sets A (bj, b2. b&] R. and a given subset I {ai, Oiz: ... 0. C A. Also,
{ai, 02 ... .m..mm B
Xaa
pubs.
for some X E I. that satisfies Σ₁=1 Xi O, and B* that satisfies μ > 0. Then, there exists
vector μ¹ E R² that satisfies the following three properties:
1) || lo < ni + 1.
2) 4 O.
3) Σx 1= bi E span(fai, a2, ... am) and when we express
m
1
8,01
1=1
04
> 0.
j=1
Proof. k S Snm++1 there is nothing to prove. Assume is > m of a vector jı that satisfies llĀloo < [|a|lo. ā 2 and
Showing the existence
m
jubs E span((a1, a2 ... am H),
Σ jub
Σ 8:a;
and Σ 5 > O, j=1
is enough to prove proposed claim. That is because if the existence of such j is proved, we can apply the existence result again to A = {ai 02, am and B {bylö [k], u. * 0} with the same I. The premises are all satisfied: from the definition of jú we know that
Σ p
jub =
Σ 8rai, Σ i=1
5i, 0.
1=1
26

---

Published as a conference paper at ICLR 2025
[B]. This means if prove the existence of such ji and iteratively apply the existence result as stated above, we will arrive at a set 8 C that satisfies
and 14 if pu # O. Moreover, [B]
m
[B -
E 6
pib,
O
O.
a > 0 if E B", 0 otherwise.
is that if [Ba] > m 1, we can find subset of B with strictly less cardinality with the same property, hence it is not the terminal set. For that set, choosing 4 gives the wanted vector.
The reason why |BO| S n
Now we show the existence of such á when n - m + 1. We first extend {ai, 02 ... am to basis of R", and note it as {a1, -.. an). Express each b; as
b, = Σ Yyja..
==1
where i E [k]. Now, write Baxk as Ti = Yyt-
What we know is the relation
A
0 0n-m
which is simply the coordinate representation of D 1.bb Now know the set
{u E & 1 i2, ... dlp = 0, + 11" 0, -'m] ==
has dimension least
m 1, each linear constraint decreases the dimension at most 1. Here [[P1.P2 P2, . pr] E R.** denotes the concatenation of r rows of r, P(p to P(p.]- As
k n 0, there exists a nonzero p' that satisfies
Tp'
X O mm
Σ
M1 =
For that μ². consider + ep' and either increase or decrease until the cardinality of μ decreases. As J 0, always find such that satisfies [|æ+ ep'llo < ||д[[o- As stop when the cardinality changes, + ep' 2 should also hold. At last, we know that
[x+eX] 0n-m
T( + ex²)
and 0. +x,,)) 0. As the values of Pp directly correspond to the coordinate representation of {a1, 02, Jn we know that f + epi' is the jú that looking for. This finishes the proof.
The necessary width in this case is n + 1, and we obtain the following result.
Theorem D.1. The set P* + 1) connected.
Proof. Similar the proof of Proposition D.5 we show that for any two A, B E (*(++1)))))))) np: they are connected with continuous path in p (n + 1). The rest will directly follow. First, let's write A (u, v. e (u/, o Also, let's write
A = (D, X v. +0 U D.
B = (D U(-
and note them as A {41, 02, am C R B = (b,, b2 ..bb RR. At last d1, ... Ams μ1, 42, Pk are unique nonnegative numbers that satisfy
Σ Aja Σ H.bs = y¹
The uniqueness follows from the fact that A, E Pn + 1) n Pirr and the nonnegativeness follows from the optimal polytope characterization in Theorem Furthermore, note that Ap > 0 for
27

---

Published as a conference paper at ICLR 2025
all p E [m], My 0 for all q [k]. For example, if ap D,X for some u, + 0, Ap = 1|ubl12 0.
The rest is similar.
Our main proof strategy will be finding + m continuous functions ... G1, G2,
Gk : [0, 1] + R that satisfies:
Property 1) (0) X (1(1) (t( 2 0
Wi [m].t & [0.1]. Vj E k|, E [0.1].
Property 2) (0 = 0, My. 2
Property 3)
Σ B())a; Σ
G2(1ibb = .n' we [01]
==1
Property 4)
m
((F(t) 0) (G,((>2) Vt [0, Σ
j=1
First, let's see that if we find such continuous functions that satisfy Property 1) to Property 4), we can construct a path from B in P* + 1). The specific path we construct is: (u, 0s (1)) given
(F(()) + G2(t)) if ap = by = DiXu; P2(1) is ap ūu, Ag E [k] such that by = D;Xus Golt)ū; if by D,Xū, Dp E [m] such that Op D;Xū; 0 otherwise.
(t(t)=
(E,(1) + Go(())o; if ap = by -D.xE F7(1)0z is Op =-;Xu Ag E [k] such that by = - D;X Ga(t)T: if by - D;Xū, Dq E [m]such that Op D;Xū; otherwise.
(t)
Let's check that (t,(t,, (t)) is path from to B P* (n As F. 0 for all E [m], (0) 0 for all j E [k), we can see that (0,( (0)) A, (m,(1), (1)) B. Also, we can see that it is curve in pt: all (t),,, (1( are nonnegative multiples of üg Ty. and we know that
P Σ D.X(u.(1 - v;(()) Σ B(IJJ; +CG000 y."
k G2(0b, J=1
Moreover, the cardinality of (u.(1), vn (1)) bounded with
m
u,)(( & Σ ((F(()) > 0) + Σ
hence the proposed path becomes continuous path in P* 1). Now, we describe how we find such m + k continuous functions. We do:
Step 0) Initialize C A. fO) gi.g.(0) 0.
Step 1) While T = 0, 1, ... repeat:
If C C B, break.
(Facts that hold from the previous iteration) Let's write = {as, Cig. a.,. U
{b, b...................... We inductively have:
1) C is a linearly independent set.
2) [T) 20 Vi [m], 9j (T) > 0 VjE E [k]
3) (T) > DiiE (i,, 12
4, 9,
(T) > 0 + j E (i15f2, ... j.l.
4)
Σ Jin (T) + Σ
gi (T)bs- = -
1=
10
28

---

Published as a conference paper at ICLR 2025
(Applying Lemma D.1 We also know that Σ -- Ma bw y and pr 0 Ve [k]. Now we check the conditions to apply Lemma D. with := C, B == B, given subset {ai, Oizi' , air _ A. Then we know that C, B are linearly independent,
Σ few (T) E Diu (T)
Σ bub y²"
and Em=1 (T) O, Mw > 0 for all w [k]. Thus all conditions for Lemma D.1
are
met, and we can find di for w E [r], Py.. for w E [8], μ² that satisfies
|| llo sn+1-r- 1 2 0,
Σ
de Di
Ni
Djw
E m=
M
Σ um
Xi >
0.
10
(Update 1) Now we update the values of fú, 9j as the following:
A((1) = [(((T) = 0 if i f2..d i,
LE TT + 1/2,,
(1(T) - ali(1- -T) is iE (ú,, :.)
(x(t) (T) + auf (t -T) - aa
if if :. Ja}
tE [T,T+//22.
(T) + a1 - -aja(((( -T) is iE "ii.,,.....
Here, a = 2 min ( >0 (i,(()) (T)//i,, m,,,,inn,,,, >13, 91. (T) (M) (g,))) >0.
Update C so that S+(T + 1/2) > + E CC +122 > 0 + b, EC
(Update 2: Pruning) After this, we initialize r 0, (0) S(T 1/2), E [m], 2, (T + 1/2),j E [k] and repeat:
(Check) If C is linearly independent, break (Update) Say C {ar1, dr2, .. arz) U (lai, ba, ... bay) Find a nontrivial linear combi- nation
Σ Nywbsw 0,
Trw +
wiml
and without loss of generality suppose Σ Thu 2 0. If D1 The 0, choose ni find at least one Tha > 0 for w E [w]. Then, write
S + t) = Syw (r) ampt
2ow (r t) = (r)
an'aat
for & E [0, 1]. Here min muinkming..ss min. 8rw (r)/nw, miny,, 30 (rw(r)/ (r)) ///// At last, update so that (r(r + 1) > + a, E C, 2x(r + 1) > 0 + b; C. Increase by 1.
(Construct fi, Dj for E E 1/2,7'+1 1]) Concatente fa and 8;, Bj and zj for all E [m]. e [k].
Step 2) Let the termination time be T To obtain Pi, Gj [0, 1] - RR, simply write Fi(() =
M(TTTT)) G2(()= 9, (T/T").
Let's first verify that the facts that hold from the previous iteration. First, C is linearly independent set at the start of each iterate because of step (Update 2: Pruning), and the first fact holds. Also, fú, Je are updated only in steps (Updatel) and (Update 2: Pruning), and we can see that for all / E [0, T" the function values are nonnegative. In update we chose a sufficiently small and p² 2 update 2, we also chose sufficiently small. Hence, the second fact holds. At every update, we also update C, and the third fact holds. At last, we add a nontrivial linear combination of .UB that sums up to 0 at each update, so the sum
In
Σ fi()aa + Σ (1)b
j=1
is preserved to be v", which means that the last fact follows.
29

---

Published as a conference paper at ICLR 2025
One important argument make is that the algorithm actually terminates, i.c. T co. The iteration the second update terminates eventually, because at each iteration the cardinality of decreases by 1. To see the larger loop terminating, observe that
f((t)
a strictly decreasing function for / E N. This is because in (Update 1), as Ew= di. > 0, the sum
decreases, and (Update 2), the sum does not increase because we suppose 2w=1 Th 2 0. This means that at each starting step of the algorithm, identical C' cannot appear twice: as C is linearly independent there exists a unique expression that gives
Σ fi. aT)
Σ Iyn (T) = =y"
and identical C appeared twice we will have the same value of Ei= (T. = Em fi(t), which is contradicting the fact that Et fi(1) strictly decreases.
Finally, let's check that have found the right Fú, Gys. As the algorithm terminated, C S B, and we know that (1) = 0 for all E [m]. Also, as
G,(b,, ='',,,;";
and the set B is linearly independent, we know that G1(1) = H4 for all j E [k]. As previously are adding nontrivial linear combination that sums
mentioned, Property 3) is guaranteed up to 0 at each update. To see that Property 4) is true, we see the value of Σ ((P(()) > 0) + Ej (t) 0) for each update. In (Update 1), as ||~*|| S + does not exceed n + 1. In (Update 2), the cardinality always decreases. Hence, Σ 1(F,(1) > 0) Σラ (() > 0) S
8, the total cardinality
for all E [0, 1]. and we know that we have actually found the wanted functions. This finishes the proof.
n
Recall that in Nguyen (202)) it is proved that the solution set is connected for m + 1 in the unregularized case. The proof strategy of Nguyen (202T) is first creating a zero entry in the second layer and changing the corresponding first layer weight arbitrarily. If the network is unregularized this is possible because the change in the corresponding first layer weight where the second layer weight is 0 will not change the model fit, hence the optimality. However, when we have regulariza- tion, such transformation is not possible as the first and second layer weights are tied together. This why we need use the characterization in Theorem [ and Lemma D.I to prove Theorem D.I Overall, our result is nontrivial extension of Nguyen (22T to regularized networks.
At last, from Proposition Proposition D.6. Suppose P (mm') is connected and m' 2 M*. Then P* is connected for all m 2 m'.
D.6 we know that P (m) is connected when 2 min(n+ +1,m M*).
Proof. Take two points A, B from (m)) We know that there exists a path from A to Airra B to Byr that satisfies A Byr E P* (m)) Pi Notice that Agr. Birr E Pirp. there cardinality is at most M Hence they are elements of (mmm'), which finishes the proof as PO* (mm) ) is connected.
Now we connect the connectivity results of P* (m) to that of (m), the solution set of the original problem in equation] 3
The object O* (m) we care about is precisely
8
+* (m)
(w.. )
min (xm
L
Σ (XW:)
+
(1
[a.13) C R (d+1)m
We first define essential sets and mappings do this.
30

---

Published as a conference paper at ICLR 2025
Definition D.5. (Minimal Optimal Neural Networks) We say a parameter (w,, az) is minimal optimal if (w,,0z)5 p 2 E [m]. We denote the set of minimal optimal neural networks mminn()) (m).
O* (m) and ag0y 0 implies 1(Xw, 2 0) * 1(X 2 0) for all
Adapting the proof from Wang et al. (2021b), we can show that for any point E @* (m). there is continuous path from A to a point in 6iin (m). The path is essentially merging the neurons with same arrangement patterns and second layer sign.
Proposition D.7. Take any point A (mm).. We have continuous path from A to some point Amin E O (m) in (m)).
Proof. Write = (w), وz)ر Assume we have (w1, 01) and (w2, 02) that satisfies 0102 > 0 and 1(Xw1 2 0) 1(X 2 0). Let's write sign(a1) sign(az) = Define the curve
w1a1 + tw2a2
C(I) V Vwian + 1w202
[elan + tw202|122)
W202
V(L - (1-1)) 1122020222222 @ (wi, (ر)r
where f E [0, 1]. The intuition of this curve is merging two pair (w1, 01) and (w2, a2))
Let's check some basic facts to see that this curve indeed merges the two pairs and is O (m).
i) C(t) is well-defined. First, we know ||0202222 2 * O, because a2 * O. Also, say 1jai + (1 t)wya2 = for some t E [0. 1]. Then we have DXw1a1 wi 2 0)). As DXw, and DXwa is consisted of nonnegative entries and 0109 > 0, DXw a1 0 must hold. This means W/ a1 contradiction because 0n * 0. The well-definedness of C(t) implies that it is continuous, because is a composition of continuous functions.
-(1 DXgagg where D
because e (*(m) which is again
ii) C(O)- A, C(I) = -
VIleraa #2az2l2" VI Viwwar + w20r2l22)) @ (0, 0) @ (Wz, ay)}ss from
alt 4aaiaa
direct substitution. Note that the value Ee 1(a; F 0) decreased by 1.
úi) C(t) is curve in (mm).. This is because the sum E (X (ww;) a is preserved through the curve, and the regularization loss is less than that of A due to triangular inequality. In other words, the loss [(C(t)) I L(C(()) for all t E [0, 1]. and L(C())) is optimal, C(t) is curve in O (m)).
We repeat the merging process until there is no such pair. This process should terminate because each merging decreases E 1(a, # 0) by 1. After we don't 't have such pair, concatenate all the curves that we have to find a curve in O" (m)) At the end of the path, we don't 't have two (we, 0:), (my, 02) that satisfy 0,0; > 0 and (Xxs; 2 0) 1(Xwy 2 0), hence it is in (iii(())
Also, we define the notion of a canonical polytope. A canonical polytope is defined to break ties that occur because two cones K,; and K2 may have nonempty intersections. For instance, say D = D2Xu1 and U2 change the solution's 's optimality. As we will see later on, we will want to erase such ambiguity, hence we consider a canonical polytope.
for some (u, vi) P Then, swapping (u1, v1) and (u2, U2) will not
Definition D.6. (Canonical Polytope) The canonical polytope is defined as
Pian
(u, (w4, PE) PD, (diag(1(X 2 0)) =D; is un + 0,
diag (1(X; 2 0))= v. + #0)
Remark D.2. diagg((Xx 2 0)) = Dj implies (2D; - T)Xu 2 0, but not the opposite. The ambiguity happens because Ty : might be 0 for some rows.
Given the notion of the minimal optimal neural network and the canonical polytope, we define two natural mappings V : P ('(m) - (m) and & ("(m) + P*(m). These mappings have been discussed multiple times in the literature Pilanci & Ergen (2000), Wang et al. (2021b), and we
introduce it again with slight variations for our needs.
Definition D.7. Suppose m 2 m². We define v PP*(m) + (m) as
V ((u,, ((4,,,)) f)) = (- Vilusl22 Vllull2)
V;
(lullla) @ (0.00m-card(wu.))).
31

---

Published as a conference paper at ICLR 2025
Definition D.8. Suppose m m². We define D; (m))) P (m)
((ww;, on) = (ui, vi) = uup = DiEr aa where I= {il 04 > 0, D = diag (1 (Xw; 2 0))
(0 UUg = Eiez wilai where I = =ii a; < 0, D₂ =diag (Xx;; 2 0))}
The mappings indeed well-defined Proposition D.8 Proposition D.8. Suppose 2 m V P" (m) - (m)) and t (m(m) + (m(m) are well defined.
Proof. By well-defined, we want to see that for all A E (mmm), (AA) E (*(m) and has a unique value, and similarly for & too.
From Definition D.7 and Definition D.8 it is not hard to see that the function value is uniquely determined for each input. Also, from direct calculation, we can see that
(1w5)12 + +a])= = ( P Dix(u, - -.). +B (1l + [|05)12),
B Σ 2 ==1
(xws)++as.
for both A (u,, = and (A) = (wz, 2n)j0= and when A az)j and ((A) (u,, v²) The former case is rather clear. To see the latter case, first observe that when we apply the merging operation in Proposition D.7 the loss will strictly decrease if for two Wi, Wy with same arrangement pattern weren't 't parallel. So they are actually parallel, and for all I such that
Dp = diag( [(X 2 0)).
|1up122
Σ 8E7
Iuoillalasl Σ (11 az), iz
because all wy are parallel for E I. the optimization problems in equation 3 and equation 4 have same optimal values, which means Vr (AA E O* (m) and (AA) E (mm).
The last equality follows from E (m)).. As m 2 m²
Moreover, can that the two mappings similar to inverses of each other.
Proposition D.9. Take any A E P n (m()). Then, ((V(A)) A. Also, take any B (w,, a,){ E O (0mma(nn (m). Then, (B)( (Wals): o a permutation of B.
Proof. We know
L ((4,, 1n) =
Viluil1" ( Viluslla) #
Us
U;
Viuill2) @ (0. (or
V
Write (VV(U, ux) ()) = (u,, e Let see that u² = u, for all i E [P]. The case of will
follow similarly.
The first case is when u; 0. Say there exists Uj * 0 and diag(1(Xu, 2 0) D: As (u:, ui) E P con. diag(1(Xu;; 2 0)) = Dj D;, meaning i j. This is contradiction because u, = O. This means there is no u, * O that is 1(Xu, 2 0) = D,, and there is no uy * that is diag(1(Xx,
Tuyll 2 2 0)) D;. meaning u/ = 0.
The next case is when u, A 0. For u, *f 0 such that diag(I(Xu; uj 2 0)) D., the only possible j i. For that j. we know that (iag(1(Xuu, mua/vIlus //lulll2 2 0)) = D,. and ut = /t//Vlulle x Vluull2=
uy This means ui = u, for all i E [P]. same for e, meaning & v ((u;, v)) = (u, vi)e
Let's see Ve &b We know
Up wilai if > 0 and D, = diag(1(Xur) ((Xw; ; 2 0)), 0 otherwise (1g walasl if a; < 0 and D, diag( (Xw, 0)), 0 otherwise,
T ((w,, a.) = (u4, w0) =
because (wi, az) is minimal. Let's say E l(a; > 0) = mp Σm 1(a; 0) ma. Σm 1(a; < 0) = m.. In {u), U2, (p). there will be m, nonzero vectors. Index them as May Magz" Hamp"" For tay we find ja [m] that satisfies ua; wj, 02,1- Furthermore,
32

---

Published as a conference paper at ICLR 2025
Jis # Jig if i1 # i2 because jn Ji2 means Dai,
Dei and dss
aizz 81 -2. Similarly, define
Ub Ub21" Vbmn and Ub, wk, loc.l Then,
V ((((WW; az) ( wej, musilassl laysl
mi
Mn
Wk; wkkl
(viss logi Wo lagel
+
/ Wk, (akk
① (0, 0) m
Wk: aaks
i=1
i=1
First, we know that ||0z lay1 for all j E [mm] This leads to V ( )))) )) (wy, |ay 1 @ (wk,, lax @ (0,0)"*
As Ji * Jig if (1 # i2, the result is permutation of (w;, 0;) 0;)
At last, for these mappings be meaningful, we would want them to be continuous. Luckily, 4 is continuous Proposition D.10 Proposition D.10. The map & (*m)) P (m) is continuous.
Proof. We consider the sequence (wf.. az j=1 in e (m) that converges to (wf² ,03 >= (*()). Let's write
((ww), ( = (u uf D ((1n)) oj )-اا) (u, )
We will show that / + u. The rest will follow.
As a starting point, we deñne some necessary constants. We define Mj for E [m] that satisfy ugo * as the following: if k 2 Mj. I(Xuf 2 0) = 1(X 2 0) and afa50 > 0. Such Mj exists due to the following reasoning: we know that for any solution A (*(m,, there exists finite set of possible directions for wj, which are the directions of ū, 0 in P As wz # 0 and
w/ + wof. for sufficiently large k so that | is sufficiently small, wo has be a positive
scaling of wy. Also w # implies as * 0, meaning for sufficiently large k, a²,3 > 0 holds.
For j E [m] that has w = 0, define Nş(c) to be the number that satisfies & 2 Ne(c) implies [[ufa <.
Now prove that for sufficiently large kt ||u, -f < for all E [P]. For certain E [P], suppose there exists (f,,2, .. je} C [m]] that satisfies D. = diag ( [X u 2 0)) = diag(1(Xw;
2 0)) and o , Jg > O (hence " """",, we. # 0). It is clear that ui
ma M, we know that 1( 2 Ei= wf. az. When & max(maxwge00 Nyle/m))mmxxpp440
0) (X 2 0) and of > 0 for i E [1]. Also, for some j E [m]] which is not in f2, .e and D; (idgggl(Xeeiiiiaa (Xw, uf 2 0)), wje Hence,
u Σ w a +
Σ -,
wzat.
D, D,= wi 20))a500
u/ + u as w + j0 converging to + oc.
at
- aj for E [t] and the rest sum becomes smaller than c, hence
w > 0)) and a3 > 0. Here, u = O. Now take ho 2 max maxxmmen mma Nz(e/m), max 4o M3}. One thing to notice is for this k. if D, = diag(1(XW, 2 0)) and at > 0 for some j E [m]. w 0. Suppose w/S # 0. As 2 Mj. we know that D; diag( ((X 2 0)) and aze O. which contradicts the assumption that there is no such j. Hence, when we write
Finally, let's see the case where there is no j E [m]] that satisfies D; =
uf
Σ
a
- D. (XX 20))
as k: 2 Ny(e/m), || ll2 S c. As u00 O, we have that uy + ugo This finishes the proof.
L
However, v may not be continuous. The intuition is that the solutions in the image of V have zeros at the end, whereas the limit of & ((u,, 2)) as u, + 0 may have zeros at the middle. Thus we have slightly weaker notion of continuity for v Proposition D.I1
33

---

Published as a conference paper at ICLR 2025
Proposition D.11. Consider continuous path (u,(t), (,(t)) in P' P*(m). where uz(t), vy(t) [0. - Rd is either a zero map map can only have zero when & = 1. Consider the path ( (x()))=))) in (m)). Then, ((t) is continuous [0, 1), and li x(t)
s(t) = ((u,(t), permutation of 61).
Proof. Let's write what ((t) looks like. Write 11 < i2 < .....y ip the indices where u; (0) * 0, and < ig the indices where (())) + O. Denote the indices I, J. For t. [0, 1), ((1)
write ji < j2 < ....
is
(1) ( Vilu((t)l22
(t(t) Vilus(t)]2
(t(
Vllu((t)l2
(ilu,(t)22
IEI
iEJ
As I.J is fixed for t E [0, and (t(t) * uf (0) + O. (0.1). When L = lime-11 o(() may have zeros in the middle, whereas (11 has at the end, and the rest is the same. Hence, lime-11 ((t) is permutation of 6(1).
+ O, ø is continuous for
Given the machinery, we are ready to elaborate the results. We start with proving that if m is sufficiently large, all permutations of point A O (m) connected. The proof strategy is analogous to the proof in Simsek et al. (201)). where we create an empty slot to permute the weights.
Proposition D.12. Suppose m 2 M + 1. Take any (wj, a3)) E (m). There exists a continu- ous path from (wy, (1)]==1111 to an arbitrary permutation (Wals) ao(5))
Proof. Our proof will start from showing that for any A = (wj, وز)ر E (m)),, we can find continuous path A' = (w/,, af)" E ("mm) that satisfies دド= 10a]_aaa + 0) < First, use Proposition D.7 to find continuous path from A to some Amin (wf, 03) E (minmm) If E 1(a} # 0) < m, we have found such path.
If not, let's show that ((Xw3)+ ) is linearly dependent. As all as + 0, all ug + 0. Now think of ((Amin) = (u,, 0/ )= We can easily see that
(Xx =
As the latter set has m > M elements, should be linearly dependent. If not, it is a contradiction to the fact that the maximal cardinality of the element in Pir is M Hence, the set ((Xw))+a))) is linearly dependent, and as all as is nonzero, the set {(X w3)) } is linearly dependent. Now consider a nontrivial linear combination,
Σ cx(xx = 0.
Without loss of generality say afc < O. Define
fm = min
afe.00
and for è E [0, tm] define
|a + teg ||uf|l
(i((1) wi V
āz(()= / lufflala + teal sign(a?).
From the definition of tm. sign(a; + +tc.) = sign(a;) for [0, Also.
Σ (xx = Σ (Xwx)+ + tc:) = > (Xw,)) aj
=
and
Σ [ (+))( 11)(0) Σ To (t)ll(2))))( = Σ
I ll a + || (i)
2 1=1l
34

---

Published as a conference paper at ICLR 2025
At last, know that for the dual optimum v/ defined in Theorem 11
- - =
for all j E [m]. This is obtained by using the fact that (Amin) E P Hence, if Ei=1 ((xwg)++ 0, multiplying (u*)² on both sides leads
m
Σ
w (2tcssign(()) = O,
and
1 m
(112 (0)
> 1 |12la
2 2
|a.1?
Hence the objective is preserved throughout the curve. meaning the curve is in (m))). The cardi- nality decreased by at least 1 the end due the definition of tm- Now that we can find a continuous path from A to A' (w'). 0/)ح= E (m) where Σド= 1(a) * > 0) < m, we will find path from A' to any permutation of A', namely (wo Yon)) for some permutation a [m] + [m]. A simple path construction is as follows: we know that least one of = 0. Let that i = m without loss of generality. Starting from in = 1, we do the following: if u/ w ((io)) we do nothing. w/, * w ((a))* we first write
w/y (1) = v v1-1, (1) = di / t, w (1) = w',, ol = o4 VI,
for t E [0, 1], which intuitively 'moves' w/, to the empty space win and making w/ = O. Next we move w' (Ht) to wn with
why (t) w' (10)) Vt, (t) (t)=aaa = d'((o)) Vt,tt,, (t) = (((())) -I- (oo))) = d'o(to) vI -I-t.
for E [0, 1]. which intuitively 'moves' w'((ho) to the empty space W/o and making Wa(to) = At last, we make wm empty by using
w'(too (t) = wi,, Vt, (o())) (t) = o% Vt, w'm = w/, t = a' VI-t.
To wrap up. we may swap the element in (w;, as)) and (w)( ao(s) by first moving w; Wms then moving wo (i) to wi. and last moving wm to (()))-
Until here connected A = (wj, 0²)"== with A', and then A' with permutation of A'. To connect
A with (Wa(s), an())), simply run the path A + A' backwards to obtain (W (m)
Proposition D.12 enables us to connect two different permutations. Even though v is not essentially continuous, the fact that two permutations are connected will allow us construct paths in +* (m) from paths in PP* (m))
Proposition D.13. Suppose m 2 MM + If any two points A, B e (*(m) are connected with path with finite cardinality changes, θ* (m)) is connected.
Proof. Take two points A, B E (7)).. First use Proposition D.7 to find path from to Amin E O (m) and B to Buin E O0 (m.) Our main goal will be connecting Amin and Bmin by using the path from ((Amin) to (BBmin)
Consider the continuous path from ((Amin) to ((Bmin), namely f [0, 1] P*(m) satisfying f(0) = ((Amin), f(1) = (.Bin)) Write f(t) (t,( (,()) Divide [0 to times (to = 0, 0, (2, (fx-1:42 =1), where in each time interval either each u, 22 either always zero or always nonzero. We have finitely many such & because we assume that the cardinality change is finite. From Proposition D.I1 can see that the path v f(t) continuous at each interval. However, as we saw in Proposition D.II V f(4), lim, V o f((), lim V o f(() are all permutations of each other.
We construct a path from Vo f(0) to V o f(1) as following: First, for each p = 0, 1, .. k -1,
construct path from lim lim V o f(t) to lim lim, Vo f(t by defining
lim f() if t=tp tp
g(t)= = V f(t) if tE (tpi tp+1)
lim lim V o s(1) is L lp+1
35

---

(tp) Published as a conference paper at ICLR 2025
for t [b. tp]]- It is clear that 9 is continuous. Moreover, we can connect each V with lim, -11 V/ ft) and lim,,,, V/ o f(t). because from Proposition D.12 we know that when m 2 M + 1, two permutations are connected in e (m), and from Proposition D.11 from this construction, a one-sided limit is a permutation of the image. Hence, a connection from v/ o f(0) to V f(1) is possible, by connecting permutations at boundaries of each interval tu. t.... tk. and moving with V o inside the intervals.
connected. From Proposition D.9 know that v (AAin) is a permutation of Amin, and as m 2 M + 1 we know that they are connected. Same holds for V/ & (Bmmi)). This means that we have found a continuous path from Amin to Buin- At the beginning we connected A with Amin, B with Buin. which finishes the proof.
Hence, V o ((Amin) and Vp Φ (Bmin)
For discontinuity, we use the property of isolated points A E P n (P*(m)) with cardinality m. Proposition D.14, Suppose m 2 m'. If A E (m) n can is an isolated point in P (m) and has cArd(A) = m, V (A) an isolated point in O- (m).
Proof. Assume the existence of a continuous function f :000 - (*) that satisfies (T) = f(0), T f(1) * A. Consider the path & o f(t) in (m)). As A E (*(m) Pean $ (A())) A + &o o f(1), which is a contradiction that A is an isolated point in (*(m). Hence, ((A) does not have a path into O* (m) - & -AA
To finish the proof, we show that <- ((A) is finite. If a ((4) is finite, we will not be able to move from (A) to a point in & ((4) (A)) only using points in $ -- ((A) (A)). meaning we do not have a path from (A4 to (m))) (m)))(((A))) (V)))), proving our claim.
Suppose ((w,, a; 1 = A. If diag(( 2 0)) = (iaag((XM)) 2 0)) D2 for some 0;0; >
O. the two indices i and will either correspond to the same " lpp. and card $ ((ur,, az) 1)
m, which is a contradiction. Hence, (w,, ag )=.: E Pini((m) From Proposition D.9. we know that
v ( (w;, )=){ )) (AA) is permutation of (w; a.)) This means & ( is contained in set of permutation of V (A), which is finite.
Proposition D.13 and Proposition D.14 enables us to discuss connectivity of (*)) with the con-
nectivity P (m))). With the results that we obtained for P'(m), more specifically Proposi-
tion D.2 Proposition D.3 Proposition[D.5] Theorem D.I and applying Proposition D.13 and Propo-
sition D. appropriately, we arrive at the staircase of connectivity defined in Theorem 2
Theorem D.2. (Theorem the paper) (The stairease of connectivity) Denote the optimal solution set of equation 3 in parameter space as O* (m) C Rid-1)m Suppose L is strictly convex loss function and there exists (w,, 0 # (0, (), E O² (m) some m. Let m², M be two critical values defined in Theorem 2
As m changes, we have that when
(i) m m², e (m) is finite set. Hence, for any two optimal points A + A' E (m),, there is no from A to A' inside (m)).
(ii) m 2 m + 1, there exists optimal points A' (m)) and path in O* connecting them.
(iii) m = M ('m)) is not connected set. Moreover, there exists A E O (m) which is an isolated point, i.e. there is no path in (m) that connects A with A' + A E O* (m).
(iv) m 2 M + 1, permutations of the solution are connected. Hence, for all E O (m)) there exists A' * A in O³ (m) and a path in O* (m) that connects A and A'.
(v) m > min(m* + MM,, ,n + 1}, the set O* (m) is connected, i.e. for any two optimal points A A' E (m)) there exists a continuous path from A to A'.
Proof. Proof of starts by observing that A E O (m*) if A E O (m") If not, we can find
solution A' E Oinn (m- - 1) using Proposition D.7 and its image ((A') E (m" -1) 1). At last, ((A') is connected with point in pm(m"
1) p using Proposition D.4 which contradicts the minimality of m Now. for any E O* (AA B E P* (m") satisfies that V (BB is permutation of A. Hence, O"mm)) is contained in the set of permutations of (P (P**(m")) (m²)), and as
36

---

Published as a conference paper at ICLR 2025
PP' (m*) is finite from Proposition D.2
know that (*(m") is also finite.
Proof of ii) is rather simple: we know that the solution è* (m" will have a zero slot in (m=* +1),
and by using the moving operation in the proof of Proposition D. 12]
show that move
a neuron to the zero slot.
Proof of iii) follows from Proposition D.3 and Proposition D.14 We find an isolated point with cardinality .M" and is in Pir Say the isolated point is (u, v.) If diaa(1(Xu; 2 0)) diag(I(Xu; Z 0)) D, for some i + j and # 0, Uj # O. DpXu; u; and Dp.u; uj are colinear, which leads to a contradiction. Hence all patterns are different for u, v, and by appropriate rearrangement, we can find canonical solution with cardinality M Say that solution is Pean Now we apply Proposition D.14 to see that (Pean)) isolated O* (M*).
cardinality M and is also canonical: the isolated point in Proposition c
Proof of iv) almost directly follows from Proposition D.12 Note that when wt1 W12 Wm we
can prune the solution to connect it with a different solution, hence there is no isolated point. Proof of v) directly follows from Proposition D.5. Theorem D.Iand Proposition D.13 Note that the paths constructed in Proposition D.3 and Theorem D.I has only finitely many cardinality changes, hence
apply Proposition D.13 The solution set not singleton because 2 m + 0
Corollary D.1. (Corollary of the paper) Consider the optimization problem in equation Sup- pose m n + and denote the optimal set of equation 3 as O" (m). For any 0 (w, 0g ) (R(41)mm there exists a continuous path from 0 to any point 0 E 2 (m) with nonincreasing loss.
Proof. The proof almost directly follows from Haeffele & Vidal (0117) and Theorem D.1 First, we know the existence of a continuous path with nonincreasing loss from any point to any local minimum. We know that the local minimum actually global from Haeffele Vidal (2017). Now, we know that the set O" (m) is connected: hence, we can construct a continuous path from that global minimum to any global minimum we want. Note that we can apply the result of Haeffele and Vidal
Grohs & Kutyniok (2022), chapter4) because Φ(X, w, a) = (Xw)+ and ((w ||l are nondegenerate pairs.
Corollary D.2. (Corollary of the paper) Consider the optimization problem in equation Sup- pose 2 n+11 and denote the objective in equation 3 as L((), where 0 == (wy, 0z y2 E 11++1 Let the optimal value of equation Bas p². For any X greater than or equal to p", we have that the sublevel set {0 (()) S }} is connected.
Proof. Take two points 0,, O2 that satisfies L(0,), S A. Fix an arbitrary 0r from the optimal
θ* From Corollary [ we know the existence path with nonincreasing loss from 01 l", and 0g to 6* Hence we found path inside the sublevel set {Ø C(0) s }} that connects 0₃ and 0g. This means that the sublevel set connected.
37

---

Published as a conference paper at ICLR 2025
E PROOFS IN SECTION 3.3
In this section, we give the examples constructed Section 3.3 and their rigorous proof.
The specific examples present the following: Proposition E.1. Suppose n = 3, input data is given as
{ 22, v:) [110000100,-1122,333222331
X = [21 R3x2 Then, the minimization problem in equation with free skip connections and without bias, namely the SNB problem, has at least two different solutions in F
Proof. Let's consider the set Qx = ((Xu)+++ ||ul|2 S 1}. The six possible hyperplane arrangement patterns 1(Nu 2 0) are (001), (010), (100), (011), (101), (110), and when we draw the set Qx we get the following shape Figure
(b) The set Conv(2x U -x)). is denoted with the black point.
(a) Six linear regions of (Xu)+-
Figure 7: The shape Qx for a certain 2d data. The input space is split into six regions, and each region becomes either ld or a 2d object in a 3-dimensional space. Observe that Qx meets with x - y + = with six points.
With some scaling trick, we can see that the problem is further equivalent to m
m
minimize,,, (10, 2
Σ Jash subject to Xwo+ Σ (Xw;)+as = y. ||willl S
Vi E [m].
Now, choose 1,, For any optimal wo, 11 W2 0gg a1 we know that
vt Xwo
T (Xwxx)+ Σ of (XW:)) (v.
and
(v,y) < Jot (Xwi)+ 5
1=1
which means that the objective value is lower bounded by (V, 3) = 1. At last, we have two different models that have different breaklines and have objective value The two models
[
1
1/2
Wo 3
w1
/2
0
W2
22
V3/2
.1
'2"
02
02
22"
and
1 1
1 1/2
1
1/2
1
1
Wo
3
w1
1-
w2
V2
3
.1
V2"
02
V2
With direct substitution, that both have objective value of 1. At last, the breaklines differ, as the breaklines directly correspond the weight vectors Wi, W2: this means that the two optimal functions different.
that they both valid interpolators. A direct calculation shows
38

---

Published as a conference paper at ICLR 2025
Proposition E.2. Suppose 4, input data is given
{1 F21. = (-10,,))
x= [x1 E R Then, the minimization problem in equation g least two different solutions in F
namely the SB problem, has at
Proof. We give a similar proof strategy as that in Proposition bounding ju" (Xu)+I for [1, 11,11.1-111 and | < Note that X
E.1 writing X [X E R and
not easy to visualize the shape of ((Xu)+ 1|lll2 S as in Figure 7 but we can solve the optimization problem by splitting the input domain into 14 regions where the lunction (Xu)+ linear. There are 14 such regions due to the classical result of of(Cr (965). A simple convex optimization for these 14 liner regions yields that
Ix"( 5 V/[ul|2
Another way to this is writing [a, b,c and n² (Xu)+
(1a + cl -
- bb
and with the constraint a² + b² + c² < 1, we have that the above formula is bounded between -1 and Using the same scaling trick, we see that the lower bound of the objective (M, y) as in Proposition E.1 which is 4. At last, choose models as
T 0
0
100
W1
22
U22
=
-
2
01 = - -V2,
0
and
0
V2
/2
V2, = V2.
100
W1
12 =
Both solutions have 4 and interpolates the data. With some simplification, can see that the first solution gives f(x, y) 1 - whereas the second solution gives f(r,)) -1+ 2(x)+ 2(-2)+ Apparently we have two different minimum-ne norm interpolators. A visualization (and the symmetry behind it) can be found in Figure g
2
0
-2
0
1
-1
1
-1
(a) Interpolator f(x, 3) 2(y)+ 2(-
(b) Interpolator f(x, = -1 2(x) 2(-2)+
Figure 8: Two different minimum -ormm interpolators. We can see that the V shape is the minimum- norm interpolator, and the rotation of the other.
The propositions Proposition E. and Proposition
E.2 gives Proposition
39

---

Published as a conference paper at ICLR 2025
Proposition E.3. (Proposition) 2 of the paper) Consider the minimum--nrrm interpolation problem
E xm1
(Iw, +a;), subject to Xu + > (Xw;)+
min (Rl mm
where for input Xin. X = Xin in the unbiased case and X [Xin [1] in the biased case. Note that is also an optimization variable that is not fixed. When the input is 2-dimensional, we have non-unique minimum-noow -nrm interpolator regardless of bias.
Proof. This a direct consequence Proposition E. and Proposition
Proposition E.4. (Proposition 3 of the paper) Consider the minimum-nore interpolation problem without free skip connections and regularized bias, namely the NSB problem. Take vectors RR2 that satisfy
v3 1 IT.
[0, 12 > 0 vi E [n]. ||5x|12 1, > 0 vk In 1}, 8n, =0,==0,,==
Un
2 2
where write E Un-it1 Sk.- Now, choose I, 0 and choose y any conic combi- nation of n vectors
(81,1 + 81,1)) [n). ((8,-1n)) vn)1 + (sn Un)21)+
with positive weights. Then, there exist infinitely many minimum-norm interpolators.
Proof. Let's choose proposed in Proposition 3 Also, let's choose X [x|]]] E Rax2 Then the NSB problem is written as
R as 822 Write
min m. mm T
Σ
Elsll + lasl? subject to
(xwx)+a
We first show that
max
1 (Xu)+1=1 11
(19)
10l|251
and the solutions are 81, .2, Sn; 8n Un-
The first thing to observe is that 0ı < 12 < ... < In. To prove this, let's see that for = n
8n 8n-1 < Zj.
T:-1 <
8n-it1,1
The reason is the following: for .. 1, know ||s + 11-1/12 1, and as
|8n-1+1| 12 = we know 8n-it1 24-1 = -1/2 || 12 0. Hence, 9n-1+1,1%-11, +
8n Sn-i+ 1,-++1,00;112
0, have 2n-i41.2/8m-it 11-1,1 /1111/111111 11- = -I; -F-1- Similarly, || 0:ll2 = 1, and as 8n-it1 1/4 > 0, we have
0, and 8n-it1,1, 8n 1-2
8n 9n- 8n 14111 > -U,,1/
-T This means for
2,3, 2.3,...n
xi-1 < Tj. and
21 < 42 < ... < In-1- At last, we have in-1 Un < 0 because ||o,]12 = llan + Un l|2 1.
meaning 1n- < 0, whereas v, = v3 > 0, meaning 21 < x2 < < En.
0)). We can see that the possible patterns are diag( 00 0, ... .)). diag((0, 0, ... 0, 1)). diag( 0, -.. 1, 1)), diag((0, 1.... 1]). diag([1, 1... 1, 1]), ... diag([1, 0.... 0, 0)) In other words, starting from the n-th entry, 0 turns to in reverse order, then we have all ones, then Is become Os at starting from the nith entry. Let's denote the diagonal matrices D,, D2.... D2n.
Now we consider the possible arrangement patterns diag (1XXu
Solving equation 19 is equivalent to solving
DD.Xuu.
(2D; - ()-)))a200 |1
The absolute value function is erased
0.
For D,, the objective is 0. For D2 to D,+2. we first know that D,
/ = 1. To see this, observe
that - D2 X la || [n. 1]]l2 |/ |
1, - D3 D2X112 = || [xnyy 1] + un- [ 1]]l2
40

---

Published as a conference paper at ICLR 2025
Un Un-1112 1, ..... -||>" Dn+1X | 01l12 1, 11 D Dn+2X112 |Ei= dell2 v3
2 2 2l112 = 1. For Dn+3 3 to D2n. we can also see that || D,Xll1 < 1. That is because
T Dn D = Sn - sk-1 for k 2 2. ||sn Sk-1 12 = 2 28, Sk-1, and as we know 1/2 =
8n 81 < An 82 < 8...8 8n 8n-1 (which the sum of 21 and as 442 > we have the property),
|88- - s2-1 < for k = -,,,,.... n.
We can then see that (2D, 11)0000 I| v DD I ma || D2 1. The last thing to check is that $1, $2 Snz 8n that
On are actual solutions. For = 2.3, .... n2 1, we know
8n 8n,1+1,2
1 32 < -
34 <. Fit11 < ... Ina
8n-i41,1
and when we write k; = T 11² we have that kn Sn-i+1 > 0, .....e ki 8n i+1 > 0, ki 8q <
0,..- K ... Sn-i+1 As 8; = D for these s;s, 1 (Xs,)= =
for all 2, 3.......
Hence, for $2 83, Sn- (2D X) 8, 2 0.
The three cases we have to check are when i = n. and Sy Un When n, Sn, = |0, 1)T and as all k,s have positive values, Sn k; > 0 for all E [n] and indeed, Sn becomes solution. Also, we know that ||sı + +-2n1ll 1/22-21 = 1, meaning #1 < 22 < ... < Fn-1
-81,2/81,1 /1.1. Hence,
1n-1- $1 < 0, ....... k1
< 0. As 81 and kn are parallel, we know ln > 0. Same with other
cases, as ||s| 12 = 1, 81 is solution. At last, let's check that (2Dn+2 - 1)X(s,, - up) 2 0. As
On = 1/2/2 Sn Un = 1-/3/2.1/2/ Up (sp, - Un) < 0 and kn (sn - vn) < 0. For i E [n 1]. we know x; < O. Hence, -v /33,, + > O. This means (2Dn+2 X) - -v,)
and as | vnll2 1, we have S,, U, as solution too.
Now that we have found n + 1 different solutions to problem in equation 19 let's note them W1, W2 Wnt1- y is chosen any conic combination
n+1
Co X wi)++
(20)
where > O. We know that the interpolation problem is equivalent to
min t subject to y E +Conv (2x U U-2x),
where 2x {(x)++ ||ul|2 s 1} Pilanci & Ergen (022)). In other words, the minimum-norm
interpolation problem without free skip connections and regularized bias is equivalent to
min m.
dil
y
Σ
dx(xz))+
for some || < 1, [m]) For any diy 2, that satisfies || 12:112~ 5 1 and
Σ
d (X 2x+)+++
=
1=1
we have that
n+1
(v,8) = Σ c
Σ
(X2)) S
>
(x2)) S |d
i=1
1=1
meaning (v, is the optimal value, and any conic combination of {(X 1 yields solution.
Let's write wn [a., b. The optimal interpolator then becomes
n+1
f(X) = Σ a (a,x + bb)++
The last thing to check is that there are infinitely many such interpola- tors. This slightly different from y having infinitely many different conic combination expressions of ((Xw) wx)+ 1 because different e, may correspond to the same function.
for o; satisfying equation 20
41

---

Published as a conference paper at ICLR 2025
As final step, show that indeed have infinitely many different interpolators. Recall that {81, $2, ... S2, Sn -n Without loss of generality let 8; w, for [n]] and s,, Un 1 As
= {Wi, W2 ... Wn+1]. }. Note that $1.1; 82,1, ... 8n.1 2 and Sn,1 - < 0.
-oo, the slope will be 1n+1@++1- Showing the different conic representations of have different Ca+1 values is enough. The interesting observation is that the vectors ((Xw:)+ >>=1 is actually linearly indepen- dent, because each vector has D2, D3. ... Dn+1 as arrangement patterns and for each $1, $2, Sn, strict inequality holds. Hence, for each different conic combination of y. Ca+1 should be differ- ent. This means the slope at - -oo is different, and we indeed have infinitely many optimal interpolators.
42

---

Published as a conference paper at ICLR 2025
F PROOFS IN SECTION 4
In this section, we prove how our results can be generalized to different architectures and setups. We begin by describing general solution set.
Theorem F.1. Consider the cone-constrained group LASSO with regularization Ri,
P
min DE
L
A.O:
Σ i=1
B,s., v) B Σ R.(..).
(21)
==1
i=1
Assume 0,, RRd, A,, B3 E Raxd
R2 V; R are norms, C, Dy Ed are proper cones for
i E [PLj E [Q], C. V + for [P] and B > 0. The optimal set P gen is given as
Q
Pi = (c.0)) @ (s:) a 2 0. Σ
G,O,;
Σ
Bis E Cyy
i=1
-=1
E
8.) 0, E (22)
where v" is any vector that minimizes (*() subject the constraint
min (A} v, u) (R) = 0, min MEC,NV
(BJ D, s) O,
sED,
for all i [P]. E QQ. F(S, v, -0,(,),,, = {u E S, (u, u) -)
3), S; = C. | Ri(w) S 1} and Zer(S) = (0) if = S otherwise. Here, f(-) = 1(-,v) and f denotes the Fenchel
conjugate of f.
Proof. Suppose the optimal set of the problem in equation
21 is θ We show that Q S P gen
gen
and vice versa. Suppose (0" s0)) = (0 e (s
E
We know that Σ A +
gen
_i Bis E Cy. hence it satisfies the second condition for consider the convex optimization problem
A
B Also,
P
Q Σ
L(w v) + 3 Σ R(0,) subject to u.0, w.D.
min
Σ
A,O, +
B,s,
t=1
1=1
i=1
and its Lagrangian
P
(w,,,ss = L(w,y) - v-w +
(R.(0.) + Σ (B v,))
(23)
The strong duality argument is essentially the same as that with the proof in Theorem Moreover, for the dual problem
max
min w. w.D.eC,"V
C(w, 0, s,v),
min (4Tv, v. u) + (u) < O. we can scale u infinitely large to attain the minimum -o0. Same holds when minnep; (BF v, u) O. Hence, these cases cannot maximize the dual objective, and the dual problem can be written
minued, nv, (A) p.u)+ (R) min L(w, v) '"
max
minnec, (A, +3) (²), min.er, (B² v,a)=D
minuep, (B, =,
meaning 2²* is the dual optimal point. When strong duality holds, for any primal optimal point (w" 0" S*) and the dual optimal point v². the Lagrangian L(w, s,v) v*) attains minimum
(w- s*). Substitute 1² in equation 23 to see that each 6* is a minimizer the problem
min (A v." 2) + RR(u) subject to u E C, n.,
One thing to notice is that the value (AT 87) + (R, 0. because if it is strictly smaller than O can strictly decrease the objective (4 0² u) + (R) with 20"
43

---

Published as a conference paper at ICLR 2025
If 8: = O, can choose G; = 0 to find C₁2, 0g Zer(F(S,, -3)). of # 0, we know that (.)) o O. and the vector 0/ (0;)) satisfies 0J (0?) S; and (Aīv", 0 (0))) = =
Choose C2 (,)) 0, = 0 ((;) to find c, 0, E Zer(F(S,, V-, -8)).
For of s, we know that each of are the minimizer of the problem
mini!? v2,",,,, u) subject to u E Dj.
hence it should be in D, and the value (B.' 12, s = 0.
Concluding, for any (6", s"), clearly Σ A,0; Ei=1 Bys} E C. and E Dr, (B, v.' {) = 0, choose 4 = 0 when 0 = O, C = R(0;), 0, = /R((0) otherwise to see that (0", s*) E P gea and
θ gon S Pggn.
Now, let's take an element (0, 8) E P gen We know that 0 E C, nV; and & E D; 0f + 0, we know that (v" A.O.) - as 0, E F(S:, A3 v², -9). Moreover, 0; is the solution to
min a (.( (A7 (VV",,)) u),
because for all u E S. (ATV", , u) 2 (u) 2 -8 holds. This means (8,) = 1 for all 02 + 0, as the minimum will be attained at nonzero point, hence the boundary where Rr(w) = 1. Using (v*, A.O.) = -3 and (B v², 8i) 0. we get
W','' = (v', Σ G,A, +
Bisi) = -3 Σ Ci
i=1
0:70
for some w' E Cyy On the other hand, from (0,) for all E [P]. we know that
Ri(c()) = =Eo, cz.
0:40
This leads the fact that for s0,
P
L Σ A,0, + Σ B,s. + Σ R,( = L(w' + Σ c- L(w, v)) - (V" ww"
0.40
At last, show that for all w' E Cy.
P I. i=1
Mw .)) (v", w/) 8, M.
min
A,0;
+
BBsi. + 3 F=1 (0:).).
1=1
The fact follows when we use the fact that for (8',s) Ogen that satisfies w' EE A,8, + Ed Bis,, the point (w', 0',''')) becomes a minimizer of L(w, v²), Hence, each minimizer 0ç a minimizer of the problem
min(A, "0, u) + BR,(u) subject to E E n., which means that (R, = -(v", ",',,,'' for all i E [P], as v² satisfies
min (AT u) + (u) 0. aec.nv
Also, (0,,,ss = 0 as sy minimizes
(B. s) subject to E Dj, and we see that
8 (()) - -1V", w'),
and
min e.E
L
A,O, +
Σ
B y) +B R(00) =I( Σ A,0 +
Bish, v) + 3 > R((0)
1=1
i=1
T.(w', v) (v" _w"),
44

---

Published as a conference paper at ICLR 2025
meaning (f, O gen because
A, +
B v) 3 Σ R(O.) = L(w' .v) (0"" w²).
This means
P gon C 0
gens
and finishes the proof.
One application of the theorem is characterizing the optimal set of the interpolation problem. This leads to the staircase of connectivity for interpolation problems.
Proposition F.1. The solution set of the optimization problem
P
min EK
Jusll + ||ull22
subject to
Σ 11
D.X(u: (mx - -v:)= =
given
P D. 1/ R2aP.
p (1i a, 20 Vie
where ūs ūn are fixed directions found by solving the optimization problem
T. arg min T7 DiXu if min WES.
T D,Xu 11, 0 otherwise,
ueS,
0. arg min - T D.Xu if min HES,
- x D.XU = 1, 0 otherwise.
vES,
and D² any dual optimum that satisfies
1" arg min(u,y) subject ju" S ||ull2 Vu tee e
Here, S; = KC n {u ||u||2 1}.
Proof. Let's apply Theorem F.I to the problem. Note that we can set B = 1. In fact, B can be arbitrary, and scaling v² to make will lead to the same result.
When we apply Theorem
F. we have that
Pom = { (Gu,d
c. c. 0.
Σ D,NUG - D,Xū,d, =y.
ú E (F X" Dav", -1)), i3 E
where D² is the dual optimum that minimizes L (- subject to the constraint
min (X" D.V, u) + ||u||2 0, min (-x D u) + |ul| 0,
(24)
WEk.
WE
for all i E [P). We know that [v*(v) (v, v). and equation 24 can be rewritten to T D.Xul ||u]|2-
s
Also, D,", {0} if there is such that n T D,Xu -1, and is exactly that -1) vector exists. Note that as min,ex, (X") D,v, u) + ||ul[22 = 0, we have unique minimum for the optimal direction Proposition C.2 Same holds for ūz.
45

---

subject to Published as a conference paper at ICLR 2025
Proposition F.2. (The stairease connectivity for minimum-norm interpolation problem) Write the solution set of the optimization problem
min 0uy
12 la4|
1=1
subject to
Σ (Xw:)
as O" (m). Suppose y + O. As m changes, we have that
(i) m m @* is finite set. Hence, any two optimal points A + A' E (m)), there is no path from A to A' inside (* (m).
(ii) m 2 m + 1, there exists optimal points A, A' (*)) and a path in O (m) connecting them.
(iii m = M (m()) is not connected set. Moreover, there exists A E O (m) which is an isolated point, iee. there is no path (m)) that connects A with A' + A 0* (m).
(iv) m M + 1, permutations of the solution are connected. Hence, for all E (*)), there exists A' + A in (m) and a path in Oe (m) that connects A and A'.
(v) 2 min(m* + MM, 1}, the set @ (m) is connected, i.e. for any two optimal points + A' E ( (m), there exists a continuous path from A'.
Proof. The proof follows from observing that Proposition D.2 Proposition
D.3 Proposition D.4
Proposition D.5 Theorem D.I. Proposition D.7 Proposition D.12 Proposition D.13 Proposi-
tion D.14 holds for interpolation problems too. We can apply the same proof strategy for Proposi- tion D.2 Proposition D.3 Proposition D.4] Proposition D.S) Theorem D.I] because the description of the optimal polytope identical except for which directions the solutions are fixed at. The same solution map can be applied because it preserves both the fit and the regularization. The continuity preserved, and have Proposition D.12] Proposition D.13 Proposition D.14 The mapping in can also be applied here.
Proposition can
Another implication of the theorem is that free skip connections, the dual variable has to satisfy X 0. The existence of free skip connections constrain freedom v, which brings qualitative difference to the uniqueness of the solution set.
Proposition F.3. The solution set of the optimization problem
P
min M..0
Uulll + ||ul12
1=1
Xuo + Σ DiX(u, - v.) = y.
is given as
F. { up 2 (c,ū;, c, d 2 OViE [P]. Xug +
- y ) C RRuP,
p' =
i=1
where ūg is are fixed directions found by solving the optimization problem
U, = arg min "T D.Xu if min aeS,
"T D.Xu = -1, 0 otherwise,
wES.
U: arg min - vES,
- TT D if min wES
- DiXu = 11, 0 otherwise.
where v" is the dual optimum that satisfies
V² = arg min(v, y) subject to T D. S [|ll12 Vu V (,, xTv=0.
Here, S, KG, n {u ||u||2 < 1).
46

---

Published as a conference paper at ICLR 2025
Proof. Note that if apply Theorem F.1 to the given problem, have almost identical char- acterization from Proposition F.I except for the free skip connection. For the skip connection Up E R. we know that oR (X"" This means XTv- ====0. O.
(X" 1/" un) 0 for all up IR because up is unconstrained.
Next we give applications of Theorem F.1 to different architectures. We start by characterizing the optimal set of vector-valued neural network with weight decay.
Proposition F.4. The solution set of the convex reformulation of the vector-valued problem given as
P
min V.
DAXV, +
+
V K,,.
(25)
where the norm [VVl,,, is defined as
mint t 2 such that V E &tKi
for Kr; conv Now(uug {ug" (2D;- X) 2 O, ||ug2111 }} defined in V: = spanfug" (2D; I)Xu
0, 9 E R. The optimal solution set of e'quatiin 25 is given as
P
E. EGD.NV = Y", (e Ze D.N" -.NN p Vec (cv 1 20, (c
1=1
where N* = Y is the dual optimum that minimizes ||N IIp subject
(N, D,XA) 3l 20 AA V. iE [P].
Proof.
Let's define A, as
D,X
A =
D&X
which is a block matrix in A; E Ruexde, Also, define the flattening operation Flae pdxe + Rde and Flne: Raxe Rac For optimization variables 0 Rdd we have the equivalent problem
P
P
min 0.
Σ
A.O, ( +
Here, we are merely flattening each to make it into a vector-inpu optimization problem. When we apply Theorem F.l to the flattened problem, we have the optimal set
((a0) 2 0. Σ C,A, (Y Zer Ae.
Phat
where
S ful |llll 1 = Flac((ss),
v² being the minimizer of (v) where f Lp( F,Flee()) subject to (ATv*, s) + Bless] 2 O. We know that v² = Flno(Y*) FY) for the optimal model fit Y*.
Write N* = =F (v²).
Now we use Fl-11 Fl-1 to go back to the original solution space and recover Pr. First, we know that A.O, Flne (D; F1 (0.)). Hence, the constraint Σ c,A,O, Fl"o(Y*) is equivalent to
P
Σ
q &DDXFI-
de (0) Y
(26)
Also, consider the
F(F)ae(K,,), A Fla, (u (AF V. ,u) -3)-
47

---

Published as a conference paper at ICLR 2025
When we use block notation (V*)² [(x1), (18)², ... (..-((1))), x² = (uz)² (uc)"
for E R" u E Rdo, we can see that
(u') Duy) =
using notations for matrix inner product. Hence, we can see that
Flao (F(F AFv", -B,())m) = Ku
D,XU) = -33 = XE(K,,,-DD,. -B, G)M),
and for (0.) Pha Fl (0.) satisfies equation 26 and we also have the fact that FI (0.) EF(K,, X"D,"" ())))). Hence we arrive at the desired result.
Proposition F.S. Assume m 2 m so that the nonconvex problem in equation and its convex reformulation in equation 25 are equivalent. The solution set of the vector-valued problem
min 7 Th
(xw;)+2] -11
We wel1 1 + 12
where wi E [dx1 2 Rex1 is given
s= { (w;, 21) ((ww; =))= Pvece R( [ 2)
||wb||2 12ll2 vi Vi e
where
0 if # s.t. Dp diag(1((w) 2 0))
((10,,2)) (V))-1 = =V==
Σ Waz Pa; is Dr = diag(1 ( (X 2 0)) for Up].
0 is wi s.l. Dp = diag(1(X 2 0))
R((,, 2:) = (Ri) = Rp =
Σ/ May Iallza, llz if Dp diag ((Xwa; way 2 0)) for j E [tpl.
and Pioc is defined in Proposition F.4
Proof. Let's note the solution set of equation
11
as O We will prove that O- S. First, find (V;)) we know that
point (w), )m in O*. When o((w), 2, 3m
m
Σ (xw))+(3)
Σ DXXV;
hence the le error is the same for both parameters. Also, we have that El 1V/ S Em [ ||a||2;; ll 1 Em ll 11 + || 112. Thus, when we note Lnouevx as the loss function
2
of equation 11 and note Levx as the loss function of equation 25 we have that
Inonevx { 2 Teeee (
=
(27)
holds general. As the minimal value Lnonevx and Levx is the same, we have that @((wf )m P Also, the inequality in equation 27 is actually an equality, and have RR,,, 2: m = (IIVil,;,>)
Now we take a point (wi, 2:) in S. We know that Levx(( (p((w; 2)) the optimal value. Also, we know that Lnonevx( (ww, 2)m² = Lovx(o((w;, x)m²)) because R(w,, x))²)) = ([lo((we, 3 )P and ||wl||2 = |æal|ыVi E [m]. At last, the fact that as m 2 m and the two optimal values are the same implies that (w,, 2:) Or.
Theorem E.2. Consider layer neural network
sx(X) ((((XW)), ....I-)WWWW
48

---

Published as a conference paper at ICLR 2025
where W E Rdd-ixdd do d and 0 (W.) Consider the training problem
3
min L(fo(X),
and denote its optimal set as O¹. We can characterize subset of 0"", namely the set
1, W W 2 W ' ..), = = (W @ (W--1, W&) @ (W)) 10 W6
Here, X ([((XW1)+
2)++
The expression of 0 1 (Y', Wi, W3 W k-2 W k+1," (W) is given as
{0 (WW))) + (Wi-1, W&) @ (W)) 0 E 0¹, Qd. (Wk-1. Wh) Pree,intp
Rdd (W Ws) 16 (W Wo)lkk., (( (I( Wi [de)].
where on (A, (( (.. Rm tion F.5 and P vec,intp is defined as
() RA, R((A,, B(.) for defined in Proposi-
P Peeciintp
(eVV) a 20, Σ aD,XV;=
x D"NN", -.,
for the dual optimum N E Raxe that minimizes (N, Y)u subject to
(N, D,X A) + Alllk,. 2 AA Raxe E
Here K. convfug (2D; I)Xu 2 0, 1l S 1}. where D; denotes all possible arrange-
ments diag(1(Xh 0)).
Proof. The result is an application of Theorem H.1 to the vector-valued interpolation problem
u4 + ||::
subject
de
(Xui) = =Y',
where in E R1 Us E RRde x1 and then applying Proposition F.5
The characterization enables to extend the comnectivity result to valued networks.
Theorem F.3. Consider the optimization problem
m I
m
min {
(Xw:) -Y112 +
Σ
we 2 + 1
(28)
where Wi E IRd, 2; E R for i E [mr), and Y E Ruxe 1fm 2 nc + 1, the solution set in parameter
space O" C Rm((+c is connected.
Proof. Let's take two solutions (w,, 24) (w 2/) O², We write as the direction of w, i.c. w/|lw[[2 for w + O.
The first claim we prove is that for given {(Xwa, sT conic combination that satisfies
mm and {(X b. 7 7 mm
consider the
Σ (
+
T +
Σ
i=1
49

---

Published as a conference paper at ICLR 2025
for the optimal model fit Y Then ( (,WWay v /c20a +( VV, b, yd,2', by m (0, is an optimal solution of equation 28 when m2 + m2 I m, given that Wa 2/ + 0.
To see this, we first see that for the dual variable N (N", (X w:)+ - for all wi + 0. Sup-
pose D2 diag( (1 wa, 2 0)) for E [tp]. the same notation as the statement of Proposition F.5 and without loss of generality assume a1 = i. As (w,, 2, 2:) E S, we know R((w;, )m
(I Hence, when we write V = cy for some Vp E F(Kp, D N* - B, () M)
first know that V Σن=لl Ilall ,a z We can find such Vp because if Vp 0, could set all Wa, = =0 and it will strictly decrease the objective. Note that || = 1, yielding Cp |Vl E Wa, lla lza, ll,, and Vg is convex combination of Way za Now, let
=T
4p
V
X Way =f Paz²
jml
where by sum up to 1. We know that (N", Dp XV, - and N satisfy
min (N", D,XA) 2 3. AEK,
Hence, for all Cay zT, we have that
(N", Dp XWaa Fay) = -3,
for j [pp]. This implies for all E [m]. we have that when w, o O,
(N", (X -
and same for w/ # O. Now we are ready to prove the claim. We first know that the regression error is the same, we have the same model fit Y*. The regularization error is given as
m1
m22
C
d3
(N",Y").
Hence, the cost of the problem the same for any choice of the conic combination, and (VehWag (aaa,) yi + (Vdww', b. od is optimal when my + m2 S m.
At last, suppose 2 Tie + 1. Note that the vectors {( ) and {(ww))+2f T y are matrices in ne - dimensional subspace. As any conic combination that sums up to Y makes a solution, can first prune both solutions to make them linearly independent, and then connect the two using the same idea introduced in Theorem D.I
Corollary F.1. (Corollary of the paper) Consider the optimization problem in equation 77 Sup-
pose 2 nc + and denote the optimal set of equation 77 as O* (m). For any 0 = (wi, >=1 (=1 R(d+omm there exists continuous path from 0 to any point 0* E (mm)) with nonincreasing loss.
Proof. The proof is identical to that of Corollary 2. From Haeffele & Vidal (017)). we know that when nc + 1, the vector-valued training problem in equation I1 has no strict local minimum, iee all local minima are global. Now from any 0, move to a local minimum using a path with nonincreasing loss, then the local minimum is global. As θ* (m)) is connected, know that can arrive at any global minimum using a path with nonincreasing loss.
Finally, we extend our theory to parallel neural networks with depth 3. We have an optimal polytope characterization that states the first-layer weights have finite set of fixed possible directions. Theorem F.4. (Theorem) 3 of the paper) Consider the training problem
min m.(W (Wi.. (s m
Wi P + |1 11 + las;
)m
subject
((XW))
50

---

Published as a conference paper at ICLR 2025
Here, Wi: Raxms, W22 R and as R for [m]] Then, there only finitely many possible values of the direction of the columns of Wi. Moreover, when y # O, the directions are determined by solving the dual problem
(( ((XW(()))
max W1 IIs wallasi
Proof. We can see the problem is equivalent to
min m. m..[[Walllss.])l was aa M am
subject to
(2) y.
from Wang et al. (2021a). Furthermore, when we write
2x = w2) Wi e gdxmi u2 E ER", |Wille & 1, 1///22122 - 1
the problem is equivalent to
min 120 0 subject to WEt Conv U -x).
Now we find a cone-constrained linear expression of (XXW))+wp) Let's denote D { as the set of all possible arrangement patterns diag(1 (Xh 2 0)) and D(m1) denote all possi- ble (())) size tuples of elements in D. Let's note (:(m)) (Di1, Dia.... Dimi)) where
Da, Di2: ... Dim E D. i runs from to (PP)). Also, let's fix E -1m
Given D,(m1), 8, we define the set D' = {D))
Ps(i) as the set of all possible arrangements of diag(1(Xh 2 0)), where X :22X ... Dim, X] Raxmid
When (s(m)); 8, D2 are fixed, and (Wi)., (which denote the column Wi), w2 are fixed in sets:
(2Dik IIX O, S2 2 0 4k E [m1].
n DaX(W)) 2 20,
k=1
the ReLU expression becomes
mi
(XX1)) > D X
other words, when we denote K(DD(m2),,s, D') as
K(D;(m1),, s, D2) { w2) (2D I)X (WG) 20, O, SEWZK 2
Wk: E [m1]:
(2D' n mi
Dax(WW), 2 20.
R
mi
Qx
U
DjDaa X(W)).
IW1, ( D'),
[-1,1) m1 j=1
|iile < 1, 112 $ 11
51

---

Published as a conference paper at ICLR 2025
Now consider the change of variables, where write (Wi)-, constraint becomes Ex=1 Uis l|2 S 1. To show this, we show that
Uk E Rd.
The norm
1921
{((W1), w26 ma
[Will s 1, 1122212 s = (())
lolll2 $1}.
First, for ||W,
I| S 1, [2 l2 I 1, assume the column weights are 01 02 am.. Then we
have of + mm S 1, w + 2 +... + w2ms
and use Cauchy-Schwartz see that I 1. To prove the latter, choose W1 = [01/ / - Vllu 112,, 12),02 u2 = Pmy 12]
E ak W2kk
Iv Te 12,
With change of variables, the cones are written as
K. (D, 8, DJ) (w m (2D I)s 2 0, Vk [m1],
(2D) - 1 Σ
D Dxx Up 2 20
which is a fixed cone Rd. Hence, Qx can be rewritten as
Qx U
U
mi UUUD
U
Pa(s)
U
DiDaXo (ww)k= (Di(m)))) Dÿ): Σ on l| S $1}.
m2
(E(-1,1)m
k=1
As a result, we have found piecewise linear expression of Qx. When = O, we know that the optimal weights are all zeros. not, we know that the problem
minimize t 2 O subject to E
has dual variable n" that satisfies: y - Xca)) for some c E C, all c; are minimizers of (u*)²e (e subject to C. To see this fact, consider the supporting hyperplane on We can find vector that satisfies (v" y) S (v",t"a for all e E C and (v" (v",u)/t"
C. Write y to (" -i >;c:) and apply inner product with n² to see the wanted result. More specifically, we have that \;("", y) < (p( t²c,) for all i E [m]] and add them to see that the inequalities are actually an equality, and (v", 2) (v" ,t) for all i [m]]
(v", c) for all
Hence, noting as Conv(Q (Qx U - Qx). there exists a dual variable 1/ where the optimal (W1, W2) must lie in the set arg max ll $1 |a (V~) ((XW((()))))))))) For each constraint set
mi
(w)) E (D, Dz).
Σ
Jullla S 1,
we are optimizing linear function over this set (as the ReLU expression linear function of (ux) ). If there exists two different maximizers of the problem (uk) m the average of the two will still be in the cone and satisfy the norm constraint strictly. Say (1))== the average of the two solutions the cost function (which is either (N*)T Σn D'Da, Xv, or its negation)
value will be the same, but Em < 1. Multiplying 1/ mi 1 leads to a contradiction fixed. As the direction of the columns of W, are fixed to finite set of values.
in the optimality. Hence, for fixed cone (D, Dÿ), the optimal (vx (vx)
en
52

---

Published as a conference paper at ICLR 2025
G ADDITIONAL DISCUSSIONS
In this section, we discuss the geometrical intuition of the dual optimum, non-unique solutions, and also explain why the assumption in Simsek et al. (2021) might not hold in
The specific problem of interest is interpolating the dataset {(-v3, 1), (v3, 1)} with two-layer neural network with bias. We want to find a minimum norm interpolator, where the cost function also includes regularizing the bias. We can write the problem
m
min m.(ar Ore aum
wwill + las1?)
subject
m
Σ (Xwx)444 = y,
-v 1 v3 1
Here, X =
and [1, The last column of X denotes the bias term.
The problem is equivalent to
min m.
aad
2=1
subject to
Σ
(Xm))+a = V. ||w/|12 1 1.
See Pilanci & Ergen (2200) for a similar "scaling trick".
In other words, when denote 2x ((Xu)+ |||u|| s 1}. the problem becomes Pilanci & Ergen 2020
mint 0 subject y E tConv( (2x -22x.
Figure shows the shape of Qx and its convex hull.
(a) (Xul ||w||2 $ 1}
(b) ((Xu)+1 [|ul|a s 1}
(c) Conv(Qx Qx)
Figure 9: The shape of Conv( Qx U Qx).). We can that the line + 2 is tangent to the set (Xu) | ||u]|2 < 1}, and meets with two points (2, 0), (0, 2) on the set Qx Hence, Conv Conv(QxU UQxU-QQ @x) exactly the diamond [x| + |vl 2.
One thing to notice that Figure 9b the line x + y = 2 meets with Qx with three points, and the convex hull Conv(Qx J @ is diamond. The intuition of the dual variable is that it is the normal vector of a face where the optimal . 2. Hence the dual optimum is //* [1, 1]" We can also construct different minimum-nome interpolators by linear combinations of the three green points in Figure 99b) we can express y by only using the middle point (1, 1) here, the interpolator becomes y 1. We
exists. In our case, = [1, 1 lies on the exact line
two points (2, 0)
53

---

Published as a conference paper at ICLR 2025
and (0,2) to express (1, here, we have another interpolator that has two breakpoints. We can three points where there will be infinitely many ways to express (1, 1), that leads to a continuum of interpolators.
The assumption in Simsek al. (202T) that there cxists unique model with zero loss and minimal width does not work here. We adapt it to the regularized case, and assume that there exists unique interpolator with minimal width and a solution to
min (
wwil2 + |aul?
subject
m Σ (Xwi)) = y,-
Here, X =
[x
E R Now choose = 1- before, but choose y 3/22.
Then, there exist two ways to express as a conic combination of (2, 0), (1, 1), and (0. 2) with two points. As y is not parallel to [2, 0), [1, 1), [0, 2].
that m is minimal. Hence don't
have uniqueness of the smallest model in this case, and the results in Simsek et al. (2021) will not apply general.
54


Reviews:
[{"review_id": "PrQin5TgUr", "reviewer": "Reviewer_UbdA", "summary": "The authors present a deep and novel analysis of the loss landscape and a solution in the context of regularized neural networks. They also show that the topology of the global optima undergoes a phase transition as the width of the network changes.", "questions": "No questions.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well-written, easy to follow, and its results are clear and novel. The theoretical results stand out for their depth and clarity, as do the empirical results. The support of images is quite helpful when reading through some mathematical arguments or proofs of theoretical results.", "weaknesses": "Perhaps a deeper discussion on the topological implications of their results would be beneficial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3yB5yBUuw8", "reviewer": "Reviewer_Rcks", "summary": "In this work the authors analyze multiple aspects of the loss landscape of regularized two-layer neural networks with scalar output, including the structure of stationary points, the connectivity of optimal solutions and the non uniqueness of optimal solutions. The main proof strategy is to translate the problem into an equivalent convex problem and characterize its solution set through its dual form. \nThe authors show that the topology of the global optima goes through a phase transition as a function of the hidden layer width, which they term the staircase of connectivity. \nThis result is extended later to networks with vector-valued outputs, and parallel deep networks of depth 3.", "questions": "1. Is there a way to bound or estimate the critical widths $m^*$ and $M^*$ in practice, for instance on real datasets? \n2. In line 186: What does $h$ refer to in $\\text{diag}[1 (Xh \\geq 0)]$ ?\n3. It is not very clear to me what lines 225-226 mean. Could you perhaps rephrase it? (That $\\mathcal{P}^*_{\\nu^*}$ does depend on $\\nu^*$, but that the specific choice of it does not matter.)\n4. Figure 2 bottom: The axis labels are missing and it is not very clear to me what the red and blue lines are supposed to represent.\n5. In line 351 the author mention three interpolation problems of interest, but only discuss one problem on the minimum-norm interpolation problem. What are the other two interpolation problems and can you also extend your results to these problems?\n6. The paper describes a path of nonincreasing loss that connects local to global minima. Could this insight be incorporated into practical training algorithms, such as initializing weights or guiding optimizers in large-scale training?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- I found the \"staircase of connectivity\" very insightful, particularly how the connectivity properties of the optimal solutions are connected to critical widths $m^*$ and $M^*$. This finding explains how increasing the number of neurons affects the connectedness of optimal sets, and makes the observation of mode connectivity [Garipov et al. 2018] more precise. \n- The paper generalizes its findings also to vector-valued networks and deep networks with skip connection, which provides a broader framework that can be applied across different architectures.", "weaknesses": "- I found the theoretical results, for instance on the staircase of connectivity, hard to interpret in practice and would benefit from more accessible explanations. While the toy example in Example 1 illustrates the concept, the absence of labels in Figure 2, as well as the notation-heavy formulation makes it difficult for readers to grasp the results intuitively. \n- Although the toy examples are helpful, the paper lacks actual empirical validation of the theoretic results. I think it would add credibility to this work, if the staircase of connectivity concept would also be tested on actual neural network architectures trained on real data. It would be interesting to see how these results scale with different data distributions and larger models. \n- Overall I found the work quite difficult to read due to the dense mathematical formalism. I also feel like the section on notations should not be in the appendix, but should - at least in a shortened version - be included in the main paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HQoVKFvKsC", "reviewer": "Reviewer_iEp8", "summary": "In this paper, the authors apply convex duality for two-layer ReLU networks to study mode connectivity and unique minimal-norm interpolator problems, while also working to generalize this framework. Specifically, the authors have:\n\n* identified the staircase of connectivity that describes how connectivity evolves with width;\n* constructed none-unique minimal-norm interpolator by breaking the uniqueness conditions;\n* generalized the optimal polytope to the general cone-constrained group LASSO problem and applied it to more complicated architectures.", "questions": "I wonder if the authors have any comment regarding the weaknesses.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors apply the new technique of convex duality to problems of connectivity and minimal-norm interpolation, which have been studied previously using other methods. This approach yields both generalizations of existing results and new insights into these problems. Overall, I believe this paper is a strong demonstration of how convex duality can be leveraged in the theoretical study of machine learning. The abstract concepts are clarified through figures and examples.", "weaknesses": "I have some concerns with the presentation of this work. Specifically:\n\n* If I understand correctly, the convex duality only applies to ReLU networks. This is not emphasized.\n* I found Section 2 difficult to follow without prior knowledge of Pilanci & Ergen (2020). The relations between (1), (2), and (3) are mentioned but not explained (When do they have the same loss value? How do the solutions relate to each other?) Dimensions of $X$ and $y$ are not mentioned. $D_i$ is not explained.\n* In Figure 1, is each red point truly a unique solution, or does it represent solutions equivalent under permutation (p-unique)? If they are p-unique solutions, readers may get the wrong impression. \n* The lower half of Figure 2 is not explained.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HhvVGoYFPR", "reviewer": "Reviewer_eG7f", "summary": "This paper studies the loss landscape of ReLU networks with $L_2$-regularization. The authors first study the canonical case of a two-layer  network with scalar output, and characterize the connectivity of the solution for different number of neurons. Then, the authors extend the results to a more general class of problems, including: minimal norm interpolation, vector-valued ReLU network, and parallel deep neural network.", "questions": "1.  A general question is about the scope of the techniques in this paper. It seems that the techniques only apply to  two-layer ReLU networks, since the problem can be equivalently written as a convex problem with regularization. It is not applicable to other activation functions and seems hard to generalize to multi-layer cases. Thus, could you elaborate more on the universality of the techniques?\n\n2. The results in this paper require the number of neurons $m \\geq m_*$. As far as  I understand, $m_*$ is the minimal number of neurons needed to achieve the optimal model. I'm wondering what would happen if $m<m_*$? Also, in general, what is the scaling of $m_*$ depending on $n,d$? \n\n3. The results in Theorem 2 consider the connectivity of the optimal solution set, which is equivalent to the connectivity of a path with $0$ perturbation. What about the case that allow $\\epsilon$-pertubation along the path? Is the techniques still applicable?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This paper develops a general framework to characterize the global optimum of the regularized ReLU network via convex duality. From my understanding, the key contribution of this convex duality framework in Theorem 1 is that it allows one to characterize the \"direction\" of the weights separately in the regularized case, which is then useful for characterizing the global optimum. I believe this contribution is novel and solid. \n\n2. I think the framework of characterizing the global optimal is quite general even though it is restricted to ReLU network. In particular, it do not require large over-parameterization, special scaling, or special data distributions. Thus, I believe the results can be applied to other more specific settings and is potentially useful for characterizing other properties besides the connectivity of the solutions.", "weaknesses": "1.Although I believe this paper has a solid contribution, I found there's a few part I don't understand the significance:    \n- I think I understand the contributions in section 3.1 and 3.2, however, I'm not sure about  In section 3.3, the authors showed that for a class of data set with dimension $=1$ that satisfies certain conditions, if the network do not have skip connection, then there are infinitely many minimal norm interpolators (which is a connected set ). I'm not sure the significance of these results, since (1) it is for a special construction of dataset. (2) it might be that those infinitely many minimal norm interpolators behave qualitatively almost the same, for example, the radius of the solution set is small. Could you discuss more on the significance of the results?\n\n- In section 4, I understand the contribution of generalizing it to a vector-valued function. However, I'm not sure the significance of the results in Theorem 4. Since anyway you fixed all the other layers but only keep two consecutive layers, and technically I didn't see any difference from a two-layer network.  Could you discuss more on the significance of the results?\n\n2. One main issue of the paper is the writing, especially the main part of the paper. I check the appendices, and it is much more readable. So I suggest the authors consider rearranging the content. To name a few issues\\typos that confuse me when reading the main part: \n\n    - Line 215: and 216, what is the definition of $\\mathcal{S}_i$?\n    - Line 223: what the definition of \"optimal model fit\", what is $u_i^*, v_i^*$, and why it is unique?\n    - Line 232: the triangle inequality is reversed. Also could you be more specific about the discussion between Liine 229-232?\n    - The statement of Proposition 1:  First, you use $v_{i,1}$ to denote the first entry of a vector, could you specify this?  Also, you define $s_k = \\sum_{i=1}^k v_{n-i+1},$ but also require $||s_k|| =1, s_n = [0,1]^\\top$, could you discuss the existence of such construction? \n    - In equation (7), could you specify the dimension of the variables?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FZyygWqDvC", "reviewer": "Reviewer_ki4t", "summary": "This manuscript proposes a characterization of the topology of the global optima in the loss landscape, focusing on regularized two-layers neural networks with free skip-connections with a partial extension to deep neural networks. The authors provide a characterization of the optimal set in terms of the width of the hidden layer, which determines a so-called \"staircase of connectivity\" when such a width occurs in critical values and phase transitions. The authors study the uniqueness of the minimum-norm interpolator, highlighting necessary guarantees (such as the free ski connections, bias in the training problem and unidmiensional data). An experimental study integrates the theoretical findings.", "questions": "Can the authors proofread again the manuscript to eliminate typos, unclear sentences and missing notation?\nCan they make the presentation of the result more readable, including relevant results from the Appendix?\nCan they integrate the relevant existing literature in the Related Work section?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper has original content, and bridges together several concepts proposed in the literature on the topic. The method of analysis is rigorous and it gives a solid contribution to the field.", "weaknesses": "The manuscript presents some unclear sentences (e.g. line 198-199). There is a clear math error at line 232 (the triangle inequality holds with the reverse inequality; to be candid, I am quite sure it is a typo) and some symbols are not defined at all, not even in the Appendix (e.g. the symbol P, that occurs very often through the entire manuscript). \nThere are many references to results listed in the Appendix; if relevant, I think it might be better to put them in the main manuscript.\nAn important reference to the characterization of loss landscapes over neural networks with regularization terms and/or skip connections is missing, also because it gives a theoretical hint on the low importance of skip connections [1].\n\n[1] Bucarelli, M. S., D’Inverno, G. A., Bianchini, M., Scarselli, F., & Silvestri, F. (2024). A topological description of loss surfaces based on Betti Numbers. Neural Networks, 106465.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)