Exploring The Loss Landscape Of Regularized Neural Networks Via Convex Duality

## Abstract

Abstract We discuss several aspects of the loss landscape of regularized neural networks: the structure of stationary points, connectivity of optimal solutions, path with nonincreasing 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.

## 1 Introduction

Despite the nonconvex nature of neural networks, training these networks with local gradient methods finds nearly optimal parameters. Understanding the properties of the loss landscape is theoretically important, as it enables us to depict the learning dynamics of neural networks. For instance, many existing works prove that the loss landscape is “benign” in some sense - i.e. they don’t have spurious local minima, bad valleys, or decreasing path to infinity [], [], [], [], [], []. Such characterization enlightens our intuition on why these networks are trained so well.

As part of understanding the loss landscape, understanding the structure of global optimum has gained much interest. An example is mode connectivity [], where a simple curve connects two global optima in the set of optimal parameters. A different example is analyzing the permutation symmetry that a global optimum has []. Mathematically understanding the global optimum is theoretically important, as it sheds light on the structure of the loss landscape. In addition, these characterizations can motivate practical algorithms that search over neural networks with the same optimal cost [], [], having practical motivations for study.

We shape the loss landscape of regularized neural networks, mainly describing mathematical properties of the global optimum, by considering its convex counterpart and leveraging the dual problem. Our work is inspired by the work by [], where they characterize the optimal set and stationary points of a 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 a solution, and the optimal model fit. Expanding the idea of [], we show a clear connection between the polytope characterization and the dual optimum. With the characterization, 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 a central role in modern machine learning, including the training of large language models []. Therefore, including regularization better reflects the training procedure in practice. More importantly, adding regularization can change the qualitative behavior of the loss landscape and the global optimum: for example, there always exist infinitely many optimal solutions for the unregularized problem with ReLU activation due to positive homogeneity. However, regularizing the parameter weights breaks this tie and we may not (and we will see that it is indeed the case) have infinitely many solutions. It is also possible to design the regularization for the loss landscape to satisfy certain properties such as no spurious local minima [], [] or unique global optimum [], []. Understanding the loss landscape of regularized neural networks is not only a more realistic setup but can also give novel theoretical properties that the unregularized problem does not have.

Figure: Figure 1: A schematic that illustrates the staircase of connectivity. This conceptual figure describes the topological change in solution sets as the number of neurons $m$ changes in a high-level manner. Connected components that are not singletons are depicted as the blue sets, whereas singletons are depicted as red dots. When $m=m^{*}$, there are only finitely many red dots. When $m\geq m^{*}+1$, there exists a connected component which is not a singleton, i.e. a blue set. When $m=M^{*}$, there exists a connected component which is a singleton, i.e. a red dot. When $m\geq M^{*}+1$, there is no red dot. At last, when $m\geq\min\{m^{*}+M^{*},n+1\}$, there is a single blue set. For details of the description of critical widths $m^{*},M^{*}$, see [3.2](#S3.SS2)

The specific findings we have for regularized neural networks are:

$\bullet$ The optimal polytope: We revisit the fact that the regularized neural network’s convex reformulation has a polytope as an optimal set []. We give a connection between the dual optimum and the polytope.

$\bullet$ The staircase of connectivity: For two-layer neural networks with scalar output, we give critical widths and phase transitional behavior of the optimal set as the width of the network $m$ changes. See [Figure 1](#S1.F1) for an abstract depiction of this phenomenon.

$\bullet$ Nonunique minimum-norm interpolators: We examine the problem in [] 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 counterexamples to uniqueness in each case, inspired by the dual problem. In contrast to the previous perspectives [], [], our results imply that free skip connections may change the qualitative behavior of optimal solutions. Moreover, uniqueness does not hold in dimensions greater than one.

$\bullet$ Generalizations: We extend our results by providing a 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.

The paper is organized as the following: after discussing related work ([Section 1.1](#S1.SS1)), we discuss the convex reformulation of neural networks as a preliminary in [Section 2](#S2). Then we discuss the case of two-layer neural networks with scalar output in [Section 3](#S3), starting from the optimal polytope characterization ([Section 3.1](#S3.SS1)), the staircase of connectivity ([Section 3.2](#S3.SS2)), and construction of non-unique minimum-norm interpolators ([Section 3.3](#S3.SS3)). The possible generalizations are introduced in [Section 4](#S4). Finally, we conclude the paper in [Section 5](#S5). For details on the notations, experiments, and the proofs, see the appendix.

### 1.1 Related Work

Convex Reformulations of Neural Networks Starting from [], a series of works have concentrated in reformulating a 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 [], CNNs [], and parallel three-layer networks []. Furthermore, properties of the original nonconvex problem such as the characterization of all Clarke stationary points [], and the polyhedral characterization of optimal set [] 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 []. An intriguing phenomenon itself, it has given rise to theoretical analysis of the connectivity of optimal solutions: to name a few, [] introduces the concept of dropout stability to explain such phenomena, [] uses group theory to understand the connected components of deep linear neural networks, and [] introduces theory from differential topology to understand mode connectivity. Permutation symmetry in the parameter space also plays an important role in understanding connectivity. [] shows that assuming a unique global minimizer modulo permutations of a certain size, increasing the size of each layer by one connects all global optima. Unfortunately, their assumption does not hold in our case [Appendix H](#A8). A similar characterization is also done in [], where saddle points with permutation symmetry are connected. [] 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 [], [], []. [] has a similar connection for overparametrized networks, where they characterize the dimension of the manifold of the optimal parameter space.

Phase transitional behavior of the loss landscape Here we 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 [] and [], where adding one neuron changes the connectivity behavior of the optimal set. [] adds an exponential neuron, which is a specifically designed neuron, along with a specific regularization to eliminate all spurious local minimum. [] had the idea of defining upper / lower intrinsic dimensions of the training problem in the unregularized case, and showed that the quantity is related to whether the training problem has no spurious valleys. [] discusses a critical width $m^{*}$ where $m\geq m^{*}$, all suboptimal basins are eliminated for certain activation functions. They also discuss how $m^{*}$ is related with $n$, the number of data.

Loss landscapes and optimal sets of regularized networks [] discusses the loss landscape of the population loss along with a certain regularization, and proves the asymptotic connectivity of all sublevel sets as the width $m\rightarrow\infty$. [] also introduces an asymptotic landscape result for regularized networks. [] 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 is no spurious local minima. [] analyzes regularized linear autoencoders and points out the discrete structure of critical points under some symmetries. On the empirical side, [] considers certain metrics 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. Certain work designs specific regularization to make the loss landscape benign, removing spurious local minima and decreasing paths to infinity [], [].

Properties of unidimensional minimum-norm interpolators Training minimum-norm interpolators for unidimensional data can lead to sparse interpolators []. When we do not penalize the bias, [] has an exact characterization of the interpolation problem in function space, and [] completely characterizes the set of optimal interpolators. From the construction of optimal interpolators, it is natural that there exist problems with a continuum of infinitely many optimal interpolators. On the other hand, [] recently showed that when we 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 free skip connection does not affect the behavior of the solution [], [].

## 2 Convex Reformulations

Our main proof strategy will be first solving the equivalent convex reformulation of the original problem, obtaining the solution set of the convex reformulation, and mapping it back to the solution set of the original problem. Here we demonstrate the equivalent problems for training a two-layer neural network with weight decay, following [].

Consider the optimization problem in ([1](#S2.E1)),

$$ $\min_{\{w_{j},\alpha_{j}\}_{j=1}^{m}}L\left(\sum_{j=1}^{m}(Xw_{j})_{+}\alpha_{j},y\right)+\frac{\beta}{2}\sum_{j=1}^{m}\left(\lVert w_{j}\rVert_{2}^{2}+\alpha_{j}^{2}\right).$ (1) $$

The variables $w_{j}\in\mathbb{R}^{d},\alpha_{j}\in\mathbb{R}$ for $j\in[m]$. When the width $m$ of problem in ([1](#S2.E1)) is larger than a critical threshold $m^{*}$, we have an equivalent convex problem, i.e. all solutions of the nonconvex problem can be deduced from the convex counterpart. An equivalent problem is given as a cone-constrained group LASSO,

$$ $\min_{\{u_{i},v_{i}\}_{i=1}^{P},\ u_{i},v_{i}\in\mathcal{K}_{i}}L\left(\sum_{i=1}^{P}D_{i}X(u_{i}-v_{i}),y\right)+\beta\sum_{i=1}^{P}\left(\lVert u_{i}\rVert_{2}+\lVert v_{i}\rVert_{2}\right).$ (2) $$

Here, $D_{i}$ in $i\in[P]$ denotes all possible arrangement patterns $\mathrm{diag}[1(Xh\geq 0)]$ of the dataset $X$, and $\mathcal{K}_{i}=\{u\ |\ (2D_{i}-I)Xu\geq 0\}$ denotes the cones that each variable lies at. The intuition of convexification is constraining each variable at a certain convex cone so that the model looks linear in that region, and apply appropriate scaling to deal with regularization. The problem in ([1](#S2.E1)) has a convex dual, given as

$$ $\max_{|\nu^{T}(Xu)_{+}|\leq\beta,\ \forall\lVert u\rVert_{2}\leq 1}-L^{*}(\nu),$ (3) $$

where $L^{*}$ is the convex conjugate of $L(\cdot,y)$ and $\nu$ denotes the dual variable. Note that strong duality holds when $m\geq m^{*}$. Furthermore, we will see that the dual optimum $\nu^{*}$ determines the optimal set of both the convex problem in ([2](#S2.E2)) and the original problem in ([1](#S2.E1)).

## 3 Two-layer scalar output neural networks

In this section, we discuss the properties the optimal set and the stationary points of the optimization problem in ([1](#S2.E1)). We begin by describing the optimal set of the convex problem in ([2](#S2.E2)), which is a polytope that depends only on the data. From the characterization, we study how the topology of the optimal set changes as the width $m$ evolves. We define critical widths based on the convex program in ([2](#S2.E2)), and describe how phase transition occurs between the critical widths. Finally, we analyze the uniqueness of the minimum-norm interpolation problem introduced in []. We emphasize the importance of free skip connections for uniqueness and sparsity, and further provide counterexamples in higher dimensions.

### 3.1 The optimal polytope

We first describe the optimal set of the problem in ([2](#S2.E2)). Note that the polytope characterization was first done in []. Here, we emphasize the role of dual optimum in choosing the unique directions.

###### Theorem 1 .

(The Optimal Polytope, informal) Suppose $L$ is a strictly convex loss function. The directions of optimal parameters of the problem in ([2](#S2.E2)), noted as $\bar{u}_{i},\bar{v}_{i}$, are uniquely determined from the dual problem

$$ $\bar{u}_{i}=\operatorname*{arg\,min}_{u\in\mathcal{S}_{i}}{\nu^{*}}^{T}D_{i}Xu\ \ \mathrm{if}\ \ \min_{u\in\mathcal{S}_{i}}{\nu^{*}}^{T}D_{i}Xu=-\beta,\ \ 0\ \ otherwise,$ $$

$$ $\bar{v}_{i}=\operatorname*{arg\,min}_{v\in\mathcal{S}_{i}}-{\nu^{*}}^{T}D_{i}Xv\ \ \mathrm{if}\ \ \min_{v\in\mathcal{S}_{i}}-{\nu^{*}}^{T}D_{i}Xv=-\beta,\ \ 0\ \ otherwise.$ $$

Here $\nu^{*}$ is any dual optimum of ([3](#S2.E3)). Moreover, the solution set of ([2](#S2.E2)) is the polytope,

$$ $\mathcal{P}^{*}_{\nu^{*}}:=\left\{(c_{i}\bar{u}_{i},d_{i}\bar{v}_{i})_{i=1}^{P}\ |\ c_{i},d_{i}\geq 0\quad\forall i\in[P],\quad\sum_{i=1}^{P}D_{i}X\bar{u}_{i}c_{i}-D_{i}X\bar{v}_{i}d_{i}=y^{*}\right\}\subseteq\mathbb{R}^{2dP},$ (4) $$

for the unique optimal model fit $y^{*}=\sum_{i=1}^{P}D_{i}X(u_{i}^{*}-v_{i}^{*})$.

Note that the choice of dual variables do not change $\mathcal{P}^{*}_{\nu^{*}}$. The definition itself does depend on $\nu^{*}$, but for any choice of $\nu^{*}$ we know that $\mathcal{P}^{*}_{\nu^{*}}$ is the optimal set of ([2](#S2.E2)), meaning the choice of $\nu^{*}$ does not matter. As $\mathcal{P}^{*}_{\nu^{*}}$ does not depend on $\nu^{*}$, we will use $\mathcal{P}^{*}$ instead for simplicity. For a geometric intuition of $\nu^{*}$, refer to [Appendix H](#A8).

[Theorem 1](#Thmtheorem1) implies that ([2](#S2.E2)) have a unique direction for each $u_{i},v_{i}$ where $i\in[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_{i},v_{i})_{i=1}^{P}$ and $(u_{i}^{\prime},v_{i}^{\prime})_{i=1}^{P}$ where $u_{i}$ and $u_{i}^{\prime}$ are not colinear, taking the average of the two decreases the objective because $\lVert a\rVert_{2}+\lVert b\rVert_{2}\leq\lVert a+b\rVert_{2}$ with equality when $a$ and $b$ are colinear. However, [Theorem 1](#Thmtheorem1) implies further, that for any conic combination of such vectors $D_{i}X\bar{u}_{i}$ and $-D_{i}X\bar{v}_{i}$ that sum up to $y^{*}$, it becomes an optimal solution of ([2](#S2.E2)).

Another implication of [Theorem 1](#Thmtheorem1) is that for all stationary points of ([1](#S2.E1)), there exists a finite set of possible first-layer weights ([D.1](#A4.Thmappxcorollary1)). The result follows from using the fact proven in [], where all stationary points of ([1](#S2.E1)) are characterized by the global minimizer of the subsampled convex program that has the same structure with ([2](#S2.E2)). The implication shows that not only the global minimum but the stationary points of ([1](#S2.E1)) also have a structure that is related to the convex problem.

###### Theorem 1 .

### 3.2 The staircase of connectivity

One significance of this characterization is that when $m\geq m^{*}$, we can relate the optimal solution set of the nonconvex problem in ([1](#S2.E1)) with the subsets of ([4](#S3.E4)) with certain cardinality constraints. Specifically, the cardinality-constrained set

$$ $\mathcal{P}^{*}(m):=\left\{(u_{i},v_{i})_{i=1}^{P}\ |\ (u_{i},v_{i})_{i=1}^{P}\in\mathcal{P}^{*},\sum_{i=1}^{P}1(u_{i}\neq 0)+1(v_{i}\neq 0)\leq m\right\}\subseteq\mathbb{R}^{2dP},$ (5) $$

will determine the solution set of ([1](#S2.E1)) when $m\geq m^{*}$. 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 connected 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 $\mathcal{P}^{*}(m)$, and linking the connectivity behavior of $\mathcal{P}^{*}(m)$ and $\Theta^{*}(m)$ with appropriate solution mappings ([E.7](#A5.Thmappxdefinition7), [E.8](#A5.Thmappxdefinition8)). Aside from the proof of [Theorem 2](#Thmtheorem2), the machinery we develop can potentially be applied to extend other topological properties of $\mathcal{P}^{*}(m)$ to $\Theta^{*}(m)$.

The next result formalizes the staircase of connectivity:

###### Theorem 2 .

(The staircase of connectivity) Denote the optimal solution set of ([1](#S2.E1)) in parameter space as $\Theta^{*}(m)\subseteq\mathbb{R}^{(d+1)m}$. Suppose $L$ is a strictly convex loss function. Let

$$ $\mathcal{P}^{*}_{\mathrm{irr}}=\left\{(u_{i},v_{i})_{i=1}^{P}\ |\ (u_{i},v_{i})_{i=1}^{P}\in\mathcal{P}^{*},\ \{D_{i}Xu_{i}\}_{u_{i}\neq 0}\cup\{D_{i}Xv_{i}\}_{v_{i}\neq 0}\ \mathrm{linearly\leavevmode\nobreak\ independent}\right\},$ $$

and define two critical values

$$ $m^{*}:=\min_{\{u_{i},v_{i}\}_{i=1}^{P}\in\mathcal{P}^{*}_{\mathrm{irr}}}\sum_{i=1}^{P}1(u_{i}\neq 0)+1(v_{i}\neq 0),\ \ M^{*}:=\max_{\{u_{i},v_{i}\}_{i=1}^{P}\in\mathcal{P}^{*}_{\mathrm{irr}}}\sum_{i=1}^{P}1(u_{i}\neq 0)+1(v_{i}\neq 0).$ $$

As $m$ changes, we have that when

- (i)
$m=m^{*}$, $\Theta^{*}(m)$ is a finite set. Hence, for any two optimal points $A\neq A^{\prime}\in\Theta^{*}(m)$, there is no path from $A$ to $A^{\prime}$ inside $\Theta^{*}(m)$.
- (ii)
$m\geq m^{*}+1$, there exists optimal points $A,A^{\prime}\in\Theta^{*}(m)$ and a path in $\Theta^{*}(m)$ connecting them.
- (iii)
$m=M^{*}$, $\Theta^{*}(m)$ is not a connected set. Moreover, there exists $A\in\Theta^{*}(m)$ which is an isolated point, i.e. there is no path in $\Theta^{*}(m)$ that connects $A$ with $A^{\prime}\neq A\in\Theta^{*}(m)$.
- (iv)
$m\geq M^{*}+1$, permutations of the solution are connected. Hence, for all $A\in\Theta^{*}(m)$, there exists $A^{\prime}\neq A$ in $\Theta^{*}(m)$ and a path in $\Theta^{*}(m)$ that connects $A$ and $A^{\prime}$.
- (v)
$m\geq\min\{m^{*}+M^{*},n+1\}$, the set $\Theta^{*}(m)$ is connected, i.e. for any two optimal points $A\neq A^{\prime}\in\Theta^{*}(m)$, there exists a continuous path from $A$ to $A^{\prime}$.

[Figure 1](#S1.F1) demonstrates [Theorem 2](#Thmtheorem2) at a conceptual level. When $m=m^{*}$, the solution set has a discrete structure. One way to see it is that when $m=m^{*}$, the solutions are vertices of the polytope $\mathcal{P}^{*}$, hence they have a discrete and isolated structure. When $m\geq m^{*}+1$, we have a trivial “splitting” operation that connects two solutions with $m^{*}$ nonzero first-layer weights, which leads to the existence of a “blue set”(a connected component with infinitely many solutions) in [Figure 1](#S1.F1). When $m=M^{*}$, the solution in $\mathcal{P}^{*}_{\mathrm{irr}}$ with maximum cardinality corresponds to the isolated point in $\Theta^{*}(M^{*})$. When $m\geq M^{*}+1$, on the other hand, any solution is connected with permutations of the same solution. The proof follows from first moving to a point in $\mathcal{P}^{*}_{\mathrm{irr}}$, creating a zero slot, and using the zero slot to permute. The idea of the proof is identical to that of [], though the details differ. At last, when $m\geq\min\{m^{*}+M^{*},n+1\}$, the whole set is connected: $m^{*}+M^{*}$ is obtained from first moving to a point in $\mathcal{P}^{*}_{\mathrm{irr}}$ and interpolating the solution with the solution with minimum cardinality. $n+1$ follows from a more sophisticated argument ([E.1](#A5.Thmappxtheorem1)).

Recall that in [], it is proved that the solution set is connected for $m=n+1$ in the unregularized case. The proof strategy of [] 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 regularization, such transformation is not possible as the first and second layer weights are tied together. This is why we need to use the characterization in [Theorem 1](#Thmtheorem1) and [E.1](#A5.Thmappxlemma1) to prove [E.1](#A5.Thmappxtheorem1). Overall, our result is a nontrivial extension of [] to regularized networks.

From [], we know that when $m\geq n+1$ we have that all local minima are global (Theorem 2). With [E.1](#A5.Thmappxtheorem1), we have a characterization of the loss landscape for regularized neural networks when $m\geq n+1$. The path is clear: starting from any point, gradient flow brings the point to a local minimum. From [] the local minimum is global. Then use [E.1](#A5.Thmappxtheorem1) to move to any global minimum.

###### Corollary 1 .

Consider the training problem in [Equation 1](#S2.E1) with $m\geq n+1$. For any parameter $\theta:=(w_{i},\alpha_{i})_{i=1}^{m}$, there exists a continuous path from $\theta$ to any global minimizer $\theta^{*}\in\Theta^{*}(m)$ with nonincreasing loss.

[Example 1](#Thmexample1) demonstrates [Theorem 2](#Thmtheorem2) for a toy optimization problem, which is solving a regularized regression problem with two data points.

###### Example 1 .

Figure: 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 $m$ changes, and the figures below the horizontal line show the learned function. The red star denotes a single optimal solution while the blue line denotes a continuum of optimal solutions. The connectivity of the solution set matches well with what [Theorem 2](#Thmtheorem2) predicts. Note that when $m=3=\min\{m^{*}+M^{*},n+1\}$, there exists a continuous deformation from one solution to another.
Refer to caption: /html/2411.07729/assets/ICLR_2025_Template/figures/m_=_1_landscape_noaxis.png

(Demonstrating the staircase of connectivity for a toy example) Consider the dataset $\{(x_{i},y_{i})\}_{i=1}^{2}=\{(-\sqrt{3},1),(\sqrt{3},1)\}$ and the regularized regression problem with bias

$$ $\min_{\{(\theta_{i},a_{i},b_{i})\}_{i=1}^{m}}\frac{1}{2}\sum_{j=1}^{2}\left(\sum_{i=1}^{m}(a_{i}x_{j}+b_{i})_{+}\theta_{i}-y_{j}\right)^{2}+\frac{\beta}{2}\sum_{i=1}^{m}(\theta_{i}^{2}+a_{i}^{2}+b_{i}^{2}).$ $$

In [Figure 2](#S3.F2), we plot the loss landscape and the corresponding optimal functions when $\beta=0.1$ for $m=1,2,3$. For details on the solution set of the training problem, parameterization of optimal functions, and how the loss landscape is visualized, see [Appendix B](#A2).

The plot of functions when $m=2$ shows two different functions. This is because the connected component with infinitely many solutions emerges from the split of a single neuron, which corresponds to the same optimal function in $\mathcal{F}^{*}$. When $m=3$, we have a sequence of functions that continuously deform from one to another with the same cost.

###### Theorem 2 .

###### Corollary 1 .

###### Example 1 .

### 3.3 Non-unique optimal interpolators

In this section, we will see how the dual problem can be used to construct specific problems that have non-unique interpolators. There are three interpolation problems of interest. First, the minimum-norm interpolation problem with free skip connection and regularized bias refers to the problem in ([6](#S3.E6)), namely

$$ $\min_{m,a_{0},\{a_{i},b_{i}\theta_{i}\}_{i=1}^{m}}\sum_{i=1}^{m}\lVert a_{i}\rVert_{2}^{2}+b_{i}^{2}+\theta_{i}^{2},\quad\mathrm{subject}\ \ \mathrm{to}\quad Xa_{0}+\sum_{i=1}^{m}(Xa_{i}+b_{i}1)_{+}\theta_{i}=y.$ (6) $$

Terminology: The term “free skip connection” arises, as we have a skip connection, i.e., the linear neuron $a_{0}$, that is not regularized. We refer to the architecture in ([6](#S3.E6)) as SB (Skip connection; Bias). When we say the minimum-norm interpolation problem without free skip connections and regularized bias (NSB: No-Skip; Bias), we mean the training problem in ([6](#S3.E6)) with an additional constraint $a_{0}=0$. When we say the minimum-norm interpolation problem with free skip connections but without bias (SNB: Skip; No-Bias), we mean the training problem in ([6](#S3.E6)) with $b_{i}=0$ for all $i\in[m]$. Also, note that the width $m$ is not fixed: it is also optimized.

In [], it was proven that for unidimensional data, i.e. when $d=1$, ([6](#S3.E6)) has a unique minimizer in function space. In other words, the set of all optimal functions $\mathcal{F}^{*}$ is a singleton. We first show that when the input is not unidimensional, we have non-unique optimal interpolators both for SB and SNB setting ([F.3](#A6.Thmappxproposition3)).

The result implies two facts: first, unidimensional data with bias can be understood as 2-dimensional data that is distributed on the upper half-plane and trained without bias. Hence, the result shows that a restriction in the distribution of data can change the qualitative behavior of $\mathcal{F}^{*}$. Another fact is that even with free skip connections, we will not have unique minimum-norm interpolators for 2-dimensional input. To extend [] to higher dimensions, we may need additional structures besides free skip connections.

When we have no free skip connections, i.e. the case of NSB, we have a class of data that has infinitely many optimal interpolators. The construction follows from making the dual problem $\max_{\lVert u\rVert\leq 1}|\nu^{T}(Xu)_{+}|$ to have $n+1$ different optimal solutions.

###### Proposition 1 .

(A class of training problems with infinitely many optimal interpolators) Consider the minimum-norm interpolation problem without free skip connections and regularized bias.
Take $n$ vectors in $\mathbb{R}^{2}$ that satisfy

$$ $v_{n}=[\frac{\sqrt{3}}{2},\frac{1}{2}]^{T},\ \lVert s_{k}\rVert_{2}=1,s_{k}>0\ \ \forall k\in[n-1],\ s_{n}=[0,1]^{T},\ v_{i,2}>0\ \ \forall i\in[n].$ $$

where we write $\sum_{i=1}^{k}v_{n-i+1}=s_{k}$. Now, choose $x_{i}=v_{i,1}/v_{i,2}$ and choose $y$ as any conic combination of $n+1$ vectors

$$ $(s_{i,1}x+s_{i,2}1)_{+}\quad\forall i\in[n],\quad((s_{n}-v_{n})_{1}x+(s_{n}-v_{n})_{2}1)_{+},$ $$

with positive weights. Then, there exist infinitely many minimum-norm interpolators.

In the following example, we give a geometric description of finding the vectors $v_{i}$ for $i\in[n]$ and the continuum of optimal interpolators for $n=5$.

###### Example 2 .

(Example of a class of non-unique optimal interpolators)
Consider the figure in [Figure 3(a)](#S3.F3.sf1). Following the arrow, we can find $s_{n},s_{n-1},\cdots s_{1}$, and can find that each $s_{i}$ has norm 1, $s_{n}=[0,1]^{T}$ and $v_{n}=[\sqrt{3}/2,1/2]^{T}$. For the example in [Figure 3(a)](#S3.F3.sf1), the data $x$ and $y$ can be chosen as

$$ $x=[\tan\frac{\pi}{3},-\tan\frac{5\pi}{24},-\tan\frac{7\pi}{24},-\tan\frac{9\pi}{24},-\tan\frac{11\pi}{24}]^{T},\quad y\simeq[94,29,24,20,20]^{T}.$ $$

[Figure 3(b)](#S3.F3.sf2) show the continuum of optimal interpolators. We can see that there are infinitely many interpolators with the same cost. A magnification of the range $x\in[-8,0]$ is given to emphasize that the interpolators are indeed different. We can also see from [Figure 3(c)](#S3.F3.sf3) that gradient descent learns the continuum of optimal interpolators. Here we set $m=10$. For details on the formula of optimal interpolators, see [Appendix C](#A3).

Figure: (a) The planar geometry
Refer to caption: /html/2411.07729/assets/ICLR_2025_Template/figures/Geometry_2d_geogebra.png

Experimentally, the existence of free skip connections does not seem important in the behavior of the solution [], []. However, note that when there is no skip connection, there exists training problems where the minimum-norm interpolator has infinitely many solutions, and having $n$ breakpoints - which can never be a sparsest interpolator. Hence, at least theoretically, free skip connection plays a significant role in guaranteeing uniqueness and sparsity of the interpolator, along with penalizing the bias.

###### Proposition 1 .

###### Example 2 .

## 4 Generalizations

In this section, we will extend our results from [Section 3](#S3) to a more general training setup. We use the fact that for networks of sufficiently large width, training a neural network can be cast as a cone-constrained group LASSO problem []. Analogous to [Theorem 1](#Thmtheorem1), we first derive the optimal set of a general cone-constrained group LASSO, which is the problem in ([7](#S4.E7)):

$$ $\min_{\theta_{i}\in\mathcal{C}_{i},s_{i}\in\mathcal{D}_{i}}L(\sum_{i=1}^{P}A_{i}\theta_{i}+\sum_{i=1}^{Q}B_{i}s_{i},y)+\beta\sum_{i=1}^{P}\mathcal{R}_{i}(\theta_{i}),$ (7) $$

where $\mathcal{C}_{i},\mathcal{D}_{i}$ are proper cones, $\mathcal{R}_{i}$ is the regularization (which we assume to be a norm), and $L$ is a convex but not necessarily strictly convex loss function. The assumption that $\mathcal{R}_{i}$ is a norm is natural, because it will help the training problem find a simpler solution. Note that this setup enables to analyze many different training setups, including two-layer networks with free skip connections, interpolation problem, vector-valued outputs, and parallel deep networks of depth 3, and generalize the results in [Section 3](#S3).

### 4.1 Description of the minimum-norm solution set

The idea to derive the optimal set of ([7](#S4.E7)) is essentially the same as deriving the optimal set of ([2](#S2.E2)): we consider the dual problem and use strong duality to obtain the wanted result. The exact description of the optimal set is given as

$$ $\mathcal{P}^{*}_{\mathrm{gen}}=\Big{\{}(c_{i}\bar{\theta}_{i})_{i=1}^{P}\oplus(s_{i})_{i=1}^{Q}|\ c_{i}\geq 0,\sum_{i=1}^{P}c_{i}A_{i}\bar{\theta}_{i}+\sum_{i=1}^{Q}B_{i}s_{i}\in\mathcal{C}_{y},\bar{\theta}_{i}\in\bar{\Theta}_{i},\langle B_{i}^{T}\nu^{*},s_{i}\rangle=0,s_{i}\in\mathcal{D}_{i}\Big{\}}.$ (8) $$

First, $\mathcal{C}_{y}$ is the set of optimal model fits, which was defined at [D.1](#A4.Thmappxdefinition1). We have that $\bar{\theta}_{i}$ is contained in a certain set, which is an analogy of the optimal polytope that the direction of each variable is fixed. [Theorem 1](#Thmtheorem1) is a special case where the set of optimal directions is a singleton. Finally, we have a constraint given to variables without regularization, which is also derived from the dual formulation.

Given the expression in ([8](#S4.E8)), we can extend our results in [Theorem 1](#Thmtheorem1) and [Theorem 2](#Thmtheorem2) directly to the interpolation problem ([G.1](#A7.Thmappxproposition1), [G.2](#A7.Thmappxproposition2)) . That is because for the interpolation problem, $\mathcal{C}_{y}$ is a singleton and the set $\bar{\Theta}_{i}$ is also a singleton. We can also find the optimal set characterization of the interpolation problem with free skip connections ([G.3](#A7.Thmappxproposition3)). Here, the dual variable has to satisfy $\langle X^{T}\nu^{*},s\rangle=0$ for all $s\in\mathbb{R}^{d}$, meaning $X^{T}\nu^{*}=0$ is given as an additional constraint for the dual problem. The additional constraint is the main reason why we have qualitatively different behavior when we have free skip connections.

### 4.2 Vector-valued networks

Now we turn to two-layer neural networks with vector-valued outputs, namely the problem

$$ $\min_{(w_{i},z_{i})_{i=1}^{m}}\frac{1}{2}\lVert\sum_{i=1}^{m}(Xw_{i})_{+}z_{i}^{T}-Y\rVert_{F}^{2}+\frac{\beta}{2}\Big{(}\sum_{i=1}^{m}\lVert w_{i}\rVert_{2}^{2}+\lVert z_{i}\rVert_{2}^{2}\Big{)},$ (9) $$

where $w_{i}\in\mathbb{R}^{d\times 1},z_{i}\in\mathbb{R}^{c\times 1}$ and $Y\in\mathbb{R}^{n\times c}$.
The vector-valued problem is known to have a convex reformulation [], which is given as

$$ $\min_{V_{i}}\frac{1}{2}\lVert\sum_{i=1}^{P}D_{i}XV_{i}-Y\rVert_{2}^{2}+\beta\sum_{i=1}^{P}\lVert V_{i}\rVert_{\mathcal{K}_{i},*}.$ $$

The norm $\lVert V\rVert_{\mathcal{K}_{i},*}$ is defined as
$\lVert V\rVert_{\mathcal{K}_{i},*}:=\min t\geq 0\ \ \mathrm{s.t.}\ \ V\in t\mathcal{K}_{i},$
for $\mathcal{K}_{i}=\mathrm{conv}\{ug^{T}\ |(2D_{i}-I)Xu\geq 0,\lVert ug^{T}\rVert_{*}\leq 1\}$.

It is clear that the problem falls in our category of ([7](#S4.E7)), 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 ([9](#S4.E9)) ([G.5](#A7.Thmappxproposition5)). A direct implication extends the connectivity result to vector-valued networks ([Theorem 3](#Thmtheorem3)), and the loss landscape result of [Corollary 1](#Thmcorollary1) ([G.1](#A7.Thmappxcorollary1)).

###### Theorem 3 .

Consider the optimization problem in ([9](#S4.E9)). If $m\geq nc+1$, the solution set in parameter space $\Theta^{*}\subseteq\mathbb{R}^{m(d+c)}$ is connected.

Moreover, the characterization of the solution set of ([9](#S4.E9)) enables us to find a certain subset of the solution set of regularized $L$ - layer training problem. Consider a deep neural network

$$ $f_{\theta}(X)=((((XW_{1})_{+}W_{2})_{+}\cdots)_{+}W_{L-1})_{+}W_{L},$ $$

where $W_{i}\in\mathbb{R}^{d_{i-1}\times d_{i}}$, $d_{0}=d$ and $\theta=(W_{i})_{i=1}^{L}$, and the training problem with $l_{2}$ regularization,

$$ $\min_{\theta}L(f_{\theta}(X),y)+\frac{\beta}{2}\sum_{i=1}^{L}\lVert W_{i}\rVert_{F}^{2}.$ (10) $$

Let the optimal set of ([10](#S4.E10)) be $\Theta^{*}$. Choose two consecutive weights $W_{k-1},W_{k}$, fix the other weights to $W_{i}^{\prime}$, and see the optimal set satisfying $(((XW_{1}^{\prime})_{+}W_{2}^{\prime})_{+}\cdots)_{+}W_{k-1})_{+}W_{k}=Y^{\prime}$ for some given $Y^{\prime}\in\mathbb{R}^{n\times d_{k}}$. When we write $((XW_{1}^{\prime})_{+}W_{2}^{\prime})_{+}\cdots W_{k-2})_{+}=\tilde{X}$, we can see that this subset is the optimal set of the vector-valued interpolation problem in ([9](#S4.E9)). Hence we arrive at the following characterization. For an exact expression of the subset, see [G.2](#A7.Thmappxtheorem2).

###### Theorem 4 .

(Informal) Let the optimal set of ([10](#S4.E10)) as $\Theta^{*}$. We have an exact characterization of a subset of $\Theta^{*},$ namely the set

$$ $\displaystyle\Theta_{k-1,k}^{*}(Y^{\prime},$ $\displaystyle W_{1}^{\prime},W_{2}^{\prime},\cdots,W_{k-2}^{\prime},W_{k+1}^{\prime},\cdots W_{L}^{\prime})$ $\displaystyle:=\Big{\{}\theta=(W_{i}^{\prime})_{i=1}^{k-2}\oplus(W_{k-1},W_{k})\oplus(W_{i}^{\prime})_{i=k+1}^{L}\ |\ \theta\in\Theta^{*},\ (\tilde{X}W_{k-1})_{+}W_{k}=Y^{\prime}\Big{\}}.$ $$

[Theorem 4](#Thmtheorem4) provides an analytic method to construct a family of deep networks that achieve identical training costs and regularization.

###### Theorem 3 .

###### Theorem 4 .

### 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 [], []. The specific training problem we are interested in is

$$ $\min_{m,\{W_{1i},w_{2i},\alpha_{i}\}_{i=1}^{m}}\frac{1}{3}\left(\sum_{i=1}^{m}\lVert W_{1i}\rVert_{F}^{3}+\lVert w_{2i}\rVert_{2}^{3}+|\alpha_{i}|^{3}\right)\ \ \mathrm{s.t.}\ \sum_{i=1}^{m}((XW_{1i})_{+}w_{2i})_{+}\alpha_{i}=y.$ (11) $$

The size of each weights are $W_{1i}\in\mathbb{R}^{d\times m_{1}},w_{2i}\in\mathbb{R}^{m_{1}}$, and $\alpha_{i}\in\mathbb{R}$. The dual problem of the convex reformulation can indeed be understood as optimizing a linear function with cone and norm constraints in this case too, hence we have analogous results of the optimal polytope. Here we have the direction of the columns of first-layer weights as a set of finite vectors. For detailed proof see [Appendix G](#A7).

###### Theorem 5 .

Consider the training problem in ([11](#S4.E11)). Then, there are only finitely many possible values of the direction of the columns of $W_{1i}^{*}$. Moreover, the directions are determined by solving the dual problem $\max_{\lVert W_{1}\rVert_{F}\leq 1,\lVert w_{2}\rVert_{2}\leq 1}|(\nu^{*})^{T}((XW_{1})_{+}w_{2})_{+}|.$

[Theorem 5](#Thmtheorem5) suggests that our results are fairly generic, and could be generalized to other deep parallel architecture with appropriate parametrization.

###### Theorem 5 .

## 5 Conclusion

In this paper, we present an in-depth exploration of the loss landscape and the solution set of regularized neural networks. We start with a two-layer scalar neural network as the simplest case, and demonstrate properties of the set, including 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 into 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 ([1](#S2.E1)), up to permutations: intuitively, from the counterexamples we show, it can be speculated that the solution of the dual problem $\max|\nu^{T}(Xu)_{+}|$ subject to $\lVert u\rVert\leq 1$ is unlikely to have “too many” optimal solutions. Hence it is likely that the dataset that makes the minimum-norm interpolator non-unique is very small. We conjecture that the set will have measure 0 in $\mathbb{R}^{2n}$, and leave it for future work. At last, extending the optimal polytope/connectivity results to tree neural networks [] with arbitrary depth could be a meaningful contribution.

## Reproducibility Statement

The only randomness that occurs from our experiments are [Figure 5(a)](#A2.F5.sf1), [Figure 5(b)](#A2.F5.sf2), [Figure 6(a)](#A3.F6.sf1), and [Figure 6(b)](#A3.F6.sf2), where different initialization may lead to 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.

## Appendix

## Appendix A Notations

In this section, we will introduce the training problem that we deal with throughout the paper, the objects of interest, and the notations.

We are interested in training a neural network with regularization, namely the optimization problem

$$ $\min_{\theta\in\mathbb{R}^{p}}L(f_{\theta}(X),y)+\beta\mathcal{R}(\theta).$ (12) $$

Here, $X\in\mathbb{R}^{n\times d}$ is the data matrix, $y\in\mathbb{R}^{n}$ is the label vector, $\theta\in\mathbb{R}^{p}$ the concatenation of all parameters of the neural network, $f_{\theta}$ the parametrization, $\beta>0$ the regularization, $L:\mathbb{R}^{n}\times\mathbb{R}^{n}\rightarrow\mathbb{R}$ the loss function, and $\mathcal{R}:\mathbb{R}^{p}\rightarrow\mathbb{R}$ the regularization. We assume that $L$ is a convex function, where many problems of interest (e.g. squared, $l_{1}$, cross-entropy loss) satisfy. Note that the above setting includes the minimum-norm interpolation problem when we let $L$ as the indicator function of $D=\{(x,x)|\ x\in\mathbb{R}^{n}\}$. Though the setup is general, we will have specific neural network architectures of interest for each section, and the problem of interest will be described.

Now we turn to the notion of the “optimal set” that we are interested in. We have two different objects of interest: the optimal solution set in parameter space

$$ $\Theta^{*}:=\operatorname*{arg\,min}_{\theta\in\mathbb{R}^{p}}L(f_{\theta}(X),y)+\beta\mathcal{R}(\theta)\subseteq\mathbb{R}^{p},$ (13) $$

and the set of optimal functions in function space

$$ $\mathcal{F}^{*}:=\{f_{\theta}\ |\ \theta\in\Theta^{*}\}\subseteq\mathcal{F},$ (14) $$

where $\mathcal{F}$ is the set of functions $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$. The notion of optimal functions will mostly be discussed in [Section 3.3](#S3.SS3), where we discuss minimum-norm interpolators. Note that $\Theta^{*}$ regards parameters with permutation symmetry as different parameters.

At last, we would briefly mention the notion of connectivity in this paper. We say two points $x,y\in S$ is connected in $S$ if for two points $x,y\in S$, there exists a continuous function $f:[0,1]\rightarrow S$ that satisfies $f(0)=x,f(1)=y$. We say $S$ is connected if for any two points $x,y\in S$, $x$ and $y$ are connected in $S$. The definition implies that $S$ is path connected in general topology, and as $S$ is a subset of $\mathbb{R}^{p}$, path connectedness and connectedness are equivalent.

Some notations to clarify: the notation $1(\mathrm{condition}(A))$ is defined for a scalar, vector, or a matrix that notes if the entrywise condition is met, the value is 1, and else 0. Hence, $1(\mathrm{condition}(A))$ has the same shape with $A$. Note $[m]=\{1,2,\cdots,m\}$, $\lVert\cdot\rVert_{2}$ as the $l_{2}$ norm, and $\lVert\cdot\rVert_{F}$ as the Frobenious norm, $(\cdot)_{+}$ as the ReLU function. When we write $D_{i}$ for $i\in[P]$, we mean all possible arrangements generated from the data matrix $X\in\mathbb{R}^{n\times d},$ see [Section 2](#S2) for definition. We also use the notation $\mathcal{K}_{i}$ for $i\in[P]$ unless specified differently (in vector-valued networks we will). By $a\oplus b$, we mean the concatenation of two vectors(or matrices) $a$ and $b$: if $a\in\mathbb{R}^{m}$ and $b\in\mathbb{R}^{n}$, $a\oplus b\in\mathbb{R}^{m+n}$, $(a_{i})_{i=1}^{p}$ denotes $a_{1}\oplus a_{2}\oplus\cdots a_{p}$. For matrices, the notation $A_{i\cdot}$ means the $i$-th row of $A$, $A_{\cdot i}$ means the $i$-th column of $A$, and for vector $v$, $v_{,k}$ denotes the $k$-th entry of $v$. At last, we note the matrix inner product $\langle A,B\rangle_{M}=tr(A^{T}B)$.

## Appendix B Details on the toy example in Figure 2

In this section, we give details of the toy example in [Figure 2](#S3.F2). Specifically, we 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 disconnectedness 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

$$ $\min_{\{(\theta_{i},a_{i},b_{i})\}_{i=1}^{m}}\frac{1}{2}\sum_{j=1}^{2}\left(\sum_{i=1}^{m}(a_{i}x_{j}+b_{i})_{+}\theta_{i}-y_{j}\right)^{2}+\frac{\beta}{2}\sum_{i=1}^{m}(\theta_{i}^{2}+a_{i}^{2}+b_{i}^{2}),$ $$

where $\{(x_{i},y_{i})\}_{i=1}^{2}=\{(-\sqrt{3},1),(\sqrt{3},1)\}$ and $\beta=0.1$. When we write $X=\begin{bmatrix}-\sqrt{3},1\\
\sqrt{3},1\end{bmatrix}\in\mathbb{R}^{2\times 2}$, $y=[1,1]^{T}$, and the first layer weights as $U\in\mathbb{R}^{2\times m}$, second layer weights $v=\mathbb{R}^{m}$, the optimization problem can also be written as

$$ $\min_{U\in\mathbb{R}^{2\times m},v\in\mathbb{R}^{m}}\frac{1}{2}\lVert(XU)_{+}v-y\rVert_{2}^{2}+\frac{\beta}{2}(\lVert U\rVert_{F}^{2}+\lVert v\rVert_{2}^{2}).$ $$

Let the objective be $L(U,v)$. Note that even when $m=1$, there are three parameters, so it is impossible to plot the loss landscape in a three-dimensional plot. What we do is plot a certain section of the loss landscape, as done in [], to demonstrate our result.

When $m=1$, where $r=\sqrt{1-0.5\beta}$, we plot

$$ $F(t,s)=L(\begin{bmatrix}t\\ s\end{bmatrix},[r]),$ $$

for $(t,s)\in[-1,1]\times[-0.5,2]$. $t=0,s=r$ is the only optimum.

When $m=2$, where $r=\sqrt{1-0.5\beta}$, we define

$$ $U_{0}=\begin{bmatrix}0&0\\ r&0\end{bmatrix},\quad U_{1}=\begin{bmatrix}\sqrt{3}r/(2\sqrt{2})&-\sqrt{3}r/(2\sqrt{2})\\ r/(2\sqrt{2})&r/(2\sqrt{2})\end{bmatrix},\quad U_{2}=\begin{bmatrix}0&0\\ 0&r\end{bmatrix},$ $$

$$ $v_{0}=\begin{bmatrix}r\\ 0\end{bmatrix},\quad v_{1}=\begin{bmatrix}r/\sqrt{2}\\ r/\sqrt{2}\end{bmatrix},\quad v_{2}=\begin{bmatrix}0\\ r\end{bmatrix}.$ $$

Then, we plot

$$ $F(t,s)=L(\cos(t)U_{0}+2s(U_{1}-U_{0})+\sin(t)U_{2},\cos(t)v_{0}+2s(v_{1}-v_{0})+\sin(t)v_{2}).$ $$

for $(t,s)\in[-0.25,0.6]\times[-0.5,0.3]$. The optimal solutions here are $(t,s)=(0,0.5)$ and the line $s=0,t\geq 0$.

When $m=3$, where $r=\sqrt{1-0.5\beta}$, we define

$$ $U_{0}=\begin{bmatrix}0,0,0\\ r,0,0\end{bmatrix},U_{1}=\begin{bmatrix}0&\sqrt{3}r/(2\sqrt{2})&-\sqrt{3}r/(2\sqrt{2})\\ 0&r/(2\sqrt{2})&r/(2\sqrt{2})\end{bmatrix},U_{2}=\begin{bmatrix}0,0,0\\ 0,r,0\end{bmatrix},$ $$

$$ $v_{0}=\begin{bmatrix}r\\ 0\\ 0\end{bmatrix},\quad v_{1}=\begin{bmatrix}0\\ r/\sqrt{2}\\ r/\sqrt{2}\end{bmatrix},\quad v_{2}=\begin{bmatrix}0\\ r\\ 0\end{bmatrix}.$ $$

Then, we plot

$$ $F(t,s)=L(\cos(t)\cos(s)U_{0}+\cos(t)\sin(s)U_{1}+\sin(t)U_{2},\cos(t)\cos(s)v_{0}+\cos(t)\sin(s)v_{1}+\sin(t)v_{2}).$ $$

for $(t,s)\in[-0.5,1]\times[-0.5,1]$. The optimal solutions are $s=0,t\geq 0$ and $t=0,s\geq 0$.

The contour plot of the loss landscape can be found in [Figure 4](#A2.F4). It clearly shows that the connectivity behavior of the optimal solution changes.

Figure: (a) $m=1$
Refer to caption: /html/2411.07729/assets/ICLR_2025_Template/figures/m_=_1_contour.png

[Figure 5](#A2.F5) 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 a continuum of optimal solutions. We present the case both when $m=3$ and $m=5$. When $m$ is increased, the model gets less stuck at local minima.

Figure: (a) $m=3$
Refer to caption: /html/2411.07729/assets/ICLR_2025_Template/figures/GD_n=2_m=3.png

At last, we show that all optimal interpolators can be written as

$$ $f(x)=\sqrt{\kappa t}(\frac{\sqrt{3\kappa t}}{2}x+\frac{\sqrt{\kappa t}}{2})_{+}+\sqrt{\kappa t}(-\frac{\sqrt{3\kappa t}}{2}x+\frac{\sqrt{\kappa t}}{2})_{+}+\sqrt{\kappa(1-2t)}\left(\sqrt{\kappa(1-2t)}\right)_{+},$ $$

where $\kappa=1-\beta/2$ and $t\in[0,1/2]$. For $\nu^{T}=[1/2,1/2]$, we know that $\max_{\lVert u\rVert_{2}\leq 1}|\nu^{T}(Xu)_{+}|=1$. Let’s say the optimal model fit

$$ $y^{*}=\sum_{i=1}^{m}(Xu_{i})_{+}\alpha_{i}.$ $$

Then,

$$ $\langle\nu,y^{*}\rangle\leq\sum_{i=1}^{m}|\nu^{T}(X\frac{u_{i}}{\lVert u_{i}\rVert_{2}})|\lVert u_{i}\rVert_{2}|\alpha_{i}|\leq\frac{1}{2}\Big{(}\sum_{i=1}^{m}\lVert u_{i}\rVert_{2}^{2}+|\alpha_{i}|^{2}\Big{)}.$ $$

This means the objective has a lower bound $\frac{1}{2}\lVert y^{*}-y\rVert_{2}^{2}+\beta\langle\nu,y^{*}\rangle$, and minimum of the lower bound is attained when $y^{*}=[1-\beta/2,1-\beta/2]^{T}$. Substitute to see that the lower bound of the objective is $\beta-\beta^{2}/4$, and when $u_{1}=[0,\sqrt{1-\beta/2}]^{T}$, $\alpha_{1}=\sqrt{1-\beta/2}$ we have a solution with cost $\beta-\beta^{2}/4$ hence $y^{*}$ is indeed optimal. $\nu^{*}=y-y^{*}$, and use [Theorem 1](#Thmtheorem1) to find the complete solution set.

## Appendix C Details on the toy example in Figure 3

The construction of $x$ follows from [Proposition 1](#Thmproposition1). For the particular example we distribute the angles identically, hence we obtain the form in [Example 2](#Thmexample2). The six optimal directions are

$$ $\begin{bmatrix}\sqrt{3}/2\\ 1/2\end{bmatrix},\begin{bmatrix}\sqrt{2}/2\\ \sqrt{2}/2\end{bmatrix},\begin{bmatrix}1/2\\ \sqrt{3}/2\end{bmatrix},\begin{bmatrix}\sqrt{6}-\sqrt{2}/4\\ \sqrt{6}+\sqrt{2}/4\end{bmatrix},\begin{bmatrix}0\\ 1\end{bmatrix},\begin{bmatrix}-\sqrt{3}/2\\ 1/2\end{bmatrix}.$ $$

Let’s note these optimal directions as $\bar{u}_{1},\bar{u}_{2},\cdots\bar{u}_{6}$. We construct $y$ as

$$ $y=20((X\bar{u}_{1})_{+}+(X\bar{u}_{3})_{+}+(X\bar{u}_{5})_{+}),$ $$

which is numerically very similar to $[94,29,24,20,20]$. Note that the class of optimal interpolators are

$$ $\displaystyle f(x)=(20-7.076t)($ $\displaystyle[x,1]\cdot\bar{u}_{1})_{+}+(13.1592t)([x,1]\cdot\bar{u}_{2})_{+}+(20-13.1623t)([x,1]\cdot\bar{u}_{3})_{+}$ $\displaystyle+(13.159t)([x,1]\cdot\bar{u}_{4})_{+}+(20-7.081t)([x,1]\cdot\bar{u}_{5})_{+}+t([x,1]\cdot\bar{u}_{6})_{+},$ $$

where $t\in[0,1.5194]$ which all have the same optimal cost 60.

Similar to the experiment in [Appendix B](#A2), we give an example of the learned functions by gradient descent in [Figure 6](#A3.F6). We set $\beta=0.1$ and solve the regularized problem. Here we find multiple functions as 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.

Figure: (a) $m=6$
Refer to caption: /html/2411.07729/assets/ICLR_2025_Template/figures/GD_n=5_m=6.png

## Appendix D Proofs in Section 3.1

In this section, we briefly discuss how [Theorem 1](#Thmtheorem1) is derived and the intuition behind it. Consider the problem introduced in ([2](#S2.E2)), and write its optimal solution set as $\Theta^{*}$. To discuss the solution set, we first define the set of optimal model fits, which was first introduced in [].

###### Definition D.1 .

[] The set of optimal model fits $\mathcal{C}_{y}$ is defined as

$$ $\mathcal{C}_{y}=\Big{\{}\sum_{i=1}^{P}D_{i}X(u_{i}^{*}-v_{i}^{*})\ |\ (u_{i}^{*},v_{i}^{*})_{i=1}^{P}\in\Theta^{*}\Big{\}}.$ $$

When $L$ is strictly convex, which is the case for $l_{2}$ regression for instance, $\mathcal{C}_{y}$ becomes a singleton [].

###### Proposition D.1 .

If the loss function $L$ is strictly convex, the optimal model fit is unique, i.e. for the set of optimal model fit

$$ $\mathcal{C}_{y}=\Big{\{}\sum_{i=1}^{P}D_{i}X(u_{i}^{*}-v_{i}^{*})\ |\ (u_{i}^{*},v_{i}^{*})_{i=1}^{P}\in\Theta^{*}\Big{\}},$ $$

$\mathcal{C}_{y}=\{y^{*}\}$ for some $y^{*}\in\mathbb{R}^{n}$.

###### Proof.

Assume $y_{1},y_{2}\in\mathcal{C}_{y}$ and $y_{1}\neq y_{2}$. Let $\sum_{i=1}^{P}D_{i}X(u_{i}-v_{i})=y_{1}$ and $\sum_{i=1}^{P}D_{i}X(u^{\prime}_{i}-v^{\prime}_{i})=y_{2}$ for $(u_{i},v_{i})_{i=1}^{P},(u_{i}^{\prime},v_{i}^{\prime})_{i=1}^{P}\in\Theta^{*}$. Think of $(\frac{u_{i}+u_{i}^{\prime}}{2},\frac{v_{i}+v_{i}^{\prime}}{2})_{i=1}^{P}=\theta_{avg}$. The objective value of $\theta_{avg}$ is

$$ $L(\frac{y_{1}+y_{2}}{2},y)+\beta\sum_{i=1}^{P}\left(\lVert\frac{u_{i}+u_{i}^{\prime}}{2}\rVert_{2}+\lVert\frac{v_{i}+v_{i}^{\prime}}{2}\rVert_{2}\right)$ $$

which is strictly smaller than

$$ $\frac{1}{2}\left(L(y_{1},y)+\beta\left(\sum_{i=1}^{P}\lVert u_{i}\rVert_{2}+\lVert v_{i}\rVert_{2}\right)+L(y_{2},y)+\beta\left(\sum_{i=1}^{P}\lVert u^{\prime}_{i}\rVert_{2}+\lVert v^{\prime}_{i}\rVert_{2}\right)\right).$ $$

The strict inequality follows from the fact that $L$ is strictly convex. Contradiction follows, as we have found a parameter that has smaller objective value than the optimal cost.
∎

It is not necessary to characterize $\mathcal{C}_{y}$ as a singleton to derive the solution set itself (see [Section 4.1](#S4.SS1)). However, for the notion of the optimal polytope and its application to the staircase of connectivity, we will need that $\mathcal{C}_{y}$ is a singleton.

Before proving the optimal polytope characterization, we show that the $\bar{u}_{i}$, $\bar{v}_{i}$ introduced in [Theorem 1](#Thmtheorem1) can be uniquely determined by solving the given optimization problem.

###### Proposition D.2 .

Consider the optimization problem

$$ $\min_{u\in\mathcal{S}_{i}}\nu^{T}D_{i}Xu,\quad\min_{u\in\mathcal{S}_{i}}-\nu^{T}D_{i}Xu,$ $$

where $\nu\in\mathbb{R}^{n}$ is an arbitary vector and $\mathcal{S}_{i}=\mathcal{K}_{i}\cap\{u\ |\ \lVert u\rVert_{2}\leq 1\}$. If the optimal objective is nonzero, there exists a unique minimizer.

###### Proof.

The problem is equivalent to

$$ $\min_{u\in\mathcal{S}_{i}}(w^{*})^{T}u,$ $$

which is a linear program on a convex set. We write $w^{*}=\pm X^{T}D_{i}\nu^{*}$ for convenience. Let’s say the optimal objective $p^{*}<0$ and we have two minimizers $u_{1}^{*}$, $u_{2}^{*}$. The first thing to notice is that $\lVert u_{1}^{*}\rVert_{2}=1$. The reason is that when $\lVert u_{1}^{*}\rVert_{2}<1$, we can scale it to decrease the objective. Similarly, $\lVert u_{2}^{*}\rVert_{2}=1$. As they are two different minimizers, we know that

$$ $(w^{*})^{T}u_{1}^{*}=(w^{*})^{T}u_{2}^{*}=p^{*}=(w^{*})^{T}(\frac{u_{1}^{*}+u_{2}^{*}}{2}),$ $$

and $\lVert u_{1}^{*}+u_{2}^{*}\rVert_{2}<2$ because $u_{1}^{*}\neq u_{2}^{*}$. Scale $(u_{1}^{*}+u_{2}^{*})/2$ to obtain contradiction that $u_{1}^{*}$ is the minimizer.
∎

###### Theorem D.1 .

([Theorem 1](#Thmtheorem1) of the paper) Suppose $L$ is a strictly convex loss function. The directions of optimal parameters of the problem in ([2](#S2.E2)), noted as $\bar{u}_{i},\bar{v}_{i}$, are uniquely determined from the dual problem,

$$ $\bar{u}_{i}=\operatorname*{arg\,min}_{u\in\mathcal{S}_{i}}{\nu^{*}}^{T}D_{i}Xu\ \ \mathrm{if}\ \ \min_{u\in\mathcal{S}_{i}}{\nu^{*}}^{T}D_{i}Xu=-\beta,\ \ 0\ \ otherwise,$ $$

$$ $\bar{v}_{i}=\operatorname*{arg\,min}_{v\in\mathcal{S}_{i}}-{\nu^{*}}^{T}D_{i}Xv\ \ \mathrm{if}\ \ \min_{v\in\mathcal{S}_{i}}-{\nu^{*}}^{T}D_{i}Xv=-\beta,\ \ 0\ \ otherwise.$ $$

where $\nu^{*}$ is any dual optimum that satisfies

$$ $\nu^{*}=\operatorname*{arg\,max}-L^{*}(\nu)\ \ \mathrm{subject}\ \ \mathrm{to}\ \ |\nu^{T}D_{i}Xu|\leq\beta\lVert u\rVert_{2}\ \ \forall u\in\mathcal{K}_{i},i\in[P].$ $$

Here, $D_{i}$s are all possible arrangements $diag(1(Xh\geq 0))$ for $i\in[P]$, $\mathcal{S}_{i}=\mathcal{K}_{i}\cap\{u\ |\ \lVert u\rVert_{2}\leq 1\}$. Moreover, the solution set of ([2](#S2.E2)) is given as a polytope,

$$ $\mathcal{P}^{*}_{\nu^{*}}:=\left\{(c_{i}\bar{u}_{i},d_{i}\bar{v}_{i})_{i=1}^{P}\ |\ c_{i},d_{i}\geq 0\quad\forall i\in[P],\quad\sum_{i=1}^{P}D_{i}X\bar{u}_{i}c_{i}-D_{i}X\bar{v}_{i}d_{i}=y^{*}\right\}\subseteq\mathbb{R}^{2dP},$ (15) $$

where $y^{*}$ is the unique optimal fit satisfying $\mathcal{C}_{y}=\{y^{*}\}$.

###### Proof.

Let’s note $\Theta^{*}$ as the solution set of ([2](#S2.E2)). Also, fix $\nu^{*}$ to be any dual optimum. The directions $\bar{u}_{i},\bar{v}_{i}$ are uniquely determined from [D.2](#A4.Thmappxproposition2). Define $\mathcal{P}^{*}$ to be the set defined in ([15](#A4.E15)): note the dependence of $\mathcal{P}^{*}$ has with $\nu^{*}$ (though we will see that for any choice of $\nu^{*}$, $\mathcal{P}^{*}_{\nu^{*}}=\Theta^{*}$ and the choice of $\nu^{*}$ does not matter).

We first show that $\Theta^{*}\subseteq\mathcal{P}^{*}_{\nu^{*}}$. Take a point $(u_{i}^{*},v_{i}^{*})_{i=1}^{P}\in\Theta^{*}$. We first know that $\sum_{i=1}^{P}D_{i}X(u_{i}^{*}-v_{i}^{*})=y^{*}$ from [D.1](#A4.Thmappxproposition1). What we would like to do is showing the existence of $c_{i},d_{i}$ that satisfies

$$ $c_{i}\geq 0,\ \ u_{i}^{*}=c_{i}\bar{u}_{i},\ \ d_{i}\geq 0,\ \ v_{i}^{*}=d_{i}\bar{v}_{i},$ $$

where $\bar{u}_{i},\bar{v}_{i}$ are

$$ $\bar{u}_{i}=\operatorname*{arg\,min}_{u\in\mathcal{S}_{i}}{\nu^{*}}^{T}D_{i}Xu\ \ \mathrm{if}\ \ \min_{u\in\mathcal{S}_{i}}{\nu^{*}}^{T}D_{i}Xu=-\beta,\ \ 0\ \ otherwise,$ $$

$$ $\bar{v}_{i}=\operatorname*{arg\,min}_{v\in\mathcal{S}_{i}}-{\nu^{*}}^{T}D_{i}Xv\ \ \mathrm{if}\ \ \min_{v\in\mathcal{S}_{i}}-{\nu^{*}}^{T}D_{i}Xv=-\beta,\ \ 0\ \ otherwise.$ $$

Consider the Lagrangian

$$ $\mathcal{L}((u_{i},v_{i})_{i=1}^{P},z,\nu)=L(z,y)-\nu^{T}z+\sum_{i=1}^{P}(\beta\lVert u_{i}\rVert_{2}+\nu^{T}D_{i}Xu_{i})+\sum_{i=1}^{P}(\beta\lVert v_{i}\rVert_{2}-\nu^{T}D_{i}Xv_{i}),$ $$

where $u_{i},v_{i}\in\mathcal{K}_{i}$. We can see that

$$ $\min_{u_{i},v_{i}\in\mathcal{K}_{i},z}\max_{\nu}\mathcal{L}((u_{i},v_{i})_{i=1}^{P},z,\nu)=\max_{\nu}\min_{u_{i},v_{i}\in\mathcal{K}_{i},z}\mathcal{L}((u_{i},v_{i})_{i=1}^{P},z,\nu),$ $$

because $\nu$ is the dual variable that is only related to linear constraints. We can prove the fact rigorously by following the reasoning in []. We prove the fact for completeness.

First, we define the set

$$ $\mathcal{A}=\{(w-\sum_{i=1}^{P}D_{i}X(u_{i}-v_{i}),t)\ |\ u_{i},v_{i}\in\mathcal{K}_{i},L(w,y)+\beta\sum_{i=1}^{P}\lVert u_{i}\rVert_{2}+\lVert v_{i}\rVert_{2}\leq t\},$ $$

where $\mathcal{A}\subseteq\mathbb{R}^{n}\times\mathbb{R}$. It is clear that $\mathcal{A}$ is a convex set. Now, denote the optimal value of problem in ([2](#S2.E2)) as $p^{*}$. When we define

$$ $\mathcal{B}=\{(0,s)\ |\ s<p^{*}\},$ $$

it is clear that $\mathcal{A}\cap\mathcal{B}=\emptyset$.
By the separating hyperplane theorem, there exists $(\tilde{\nu},\tilde{\mu})\in\mathbb{R}^{n}\times\mathbb{R}$ which is nonzero, $\alpha$ such that

$$ $(z,t)\in\mathcal{A}\Rightarrow\tilde{\nu}^{T}z+\tilde{\mu}t\geq\alpha\leq\tilde{\mu}p^{*},$ $$

and we also know $\tilde{\mu}\geq 0$: else $t\rightarrow\infty$ and contradiction follows. If $\tilde{\mu}>0$ we have $\mathcal{L}((u_{i},v_{i})_{i=1}^{P},z,\tilde{\nu}/\tilde{\mu})\geq p^{*}$, and strong duality follows. If $\tilde{\mu}=0$, we conclude that for all $(u_{i},v_{i})_{i=1}^{P},z$ we have that $(\tilde{\nu})^{T}(z-\sum_{i=1}^{P}D_{i}X(u_{i}-v_{i}))\geq 0$, which is simply impossible. Hence, $\tilde{\mu}>0$ and strong duality holds.

Moreover, the dual problem

$$ $\max_{\nu}\min_{(u_{i},v_{i})_{i=1}^{P},z}\mathcal{L}((u_{i},v_{i})_{i=1}^{P},z,\nu)$ $$

writes

$$ $\mathrm{maximize}-L^{*}(\nu)\ \ \mathrm{subject}\ \ \mathrm{to}\ \ \beta\lVert u\rVert_{2}\geq|\nu^{T}D_{i}Xu|\ \ \forall u\in\mathcal{K}_{i},i\in[P].$ $$

The reason is the following: suppose for some $\nu^{\prime}\in\mathbb{R}^{n}$, there exists $u_{i}^{\prime}$ that satisfies $u_{i}^{\prime}\in\mathcal{K}_{i}$ and $\nu^{\prime T}D_{i}Xu_{i}^{\prime}+\beta\lVert u_{i}^{\prime}\rVert_{2}<0$. As we can scale $t\rightarrow\infty$ for $tu_{i}^{\prime}$ to see that for that $\nu^{\prime}$, $\min_{(u_{i},v_{i})_{i=1}^{P},z}\mathcal{L}((u_{i},v_{i})_{i=1}^{P},z,\nu^{\prime})=-\infty$. Hence, this $\nu^{\prime}$ cannot be the dual optimum. This means we only need to see the $\nu$ that satisfies $\nu^{T}D_{i}Xu+\beta\lVert u\rVert_{2}\geq 0$ for all $u\in\mathcal{K}_{i},i\in[P]$. Similarly, we only need to see $\nu$ that satisfies $-\nu^{T}D_{i}Xu+\beta\lVert u\rVert_{2}\geq 0$ for all $u\in\mathcal{K}_{i},i\in[P]$. Hence, $\nu^{*}$ is the maximizer of

$$ $\max_{\nu}\min_{z}L(z,y)-\nu^{T}z\ \ \ \ \mathrm{subject}\ \ \mathrm{to}\ \ \beta\lVert u\rVert_{2}\geq|\nu^{T}D_{i}Xu|\ \ \forall u\in\mathcal{K}_{i},i\in[P],$ $$

and the rest follows.

As strong duality holds, for any primal optimum $((u_{i}^{*},v_{i}^{*})_{i=1}^{P},y^{*})$, the function $\mathcal{L}((u_{i},v_{i})_{i=1}^{P},z,\nu^{*})$ attains minimum at $((u_{i}^{*},v_{i}^{*})_{i=1}^{P},y^{*})$ []. Note that $z^{*}$ is always $y^{*}$ due to [D.1](#A4.Thmappxproposition1), and replaced by it.

Now, as

$$ $\mathcal{L}((u_{i},v_{i})_{i=1}^{P},z,\nu^{*})=L(z,y)-{\nu^{*}}^{T}z+\sum_{i=1}^{P}(\beta\lVert u_{i}\rVert_{2}+{\nu^{*}}^{T}D_{i}Xu_{i})+\sum_{i=1}^{P}(\beta\lVert v_{i}\rVert_{2}-{\nu^{*}}^{T}D_{i}Xv_{i}),$ $$

each $u_{i}^{*}$ becomes the minimizer of $\beta\lVert u\rVert_{2}+{\nu^{*}}^{T}D_{i}Xu$ subject to $u\in\mathcal{K}_{i}$ and each $v_{i}^{*}$ becomes the minimizer of $\beta\lVert u\rVert_{2}-{\nu^{*}}^{T}D_{i}Xu$ subject to $u\in\mathcal{K}_{i}$. Recall that $\nu^{*}$ is a vector that satisfies $\beta\lVert u\rVert_{2}\geq|\nu^{T}D_{i}Xu|\ \ \forall u\in\mathcal{K}_{i},i\in[P]$, and when $u=0$, both $\beta\lVert u\rVert_{2}+{\nu^{*}}^{T}D_{i}Xu$ and $\beta\lVert u\rVert_{2}-{\nu^{*}}^{T}D_{i}Xu$ has function value 0. This implies that the minimum of both $\beta\lVert u\rVert_{2}+{\nu^{*}}^{T}D_{i}Xu$ and $\beta\lVert u\rVert_{2}-{\nu^{*}}^{T}D_{i}Xu$ subject to $u\in\mathcal{K}_{i}$ is 0 for all $i\in[P]$. As $((u_{i}^{*},v_{i}^{*})_{i=1}^{P},y^{*})$ minimizes $\mathcal{L}((u_{i},v_{i})_{i=1}^{P},z,\nu^{*})$,

$$ $\beta\lVert u_{i}^{*}\rVert_{2}+{\nu^{*}}^{T}D_{i}Xu_{i}^{*}=0,\quad\beta\lVert v_{i}^{*}\rVert_{2}-{\nu^{*}}^{T}D_{i}Xv_{i}^{*}=0.$ $$

We will find $c_{i}\geq 0$, and finding $d_{i}$ will be identical. Let’s divide into cases.
i) When $u_{i}^{*}=0$, let $c_{i}=0$ to find $c_{i}\geq 0$ that satisfies $u_{i}^{*}=c_{i}\bar{u}_{i}$.
ii) When $u_{i}^{*}\neq 0$, notice that

$$ $\min_{u\in\mathcal{S}_{i}}{\nu^{*}}^{T}D_{i}Xu=-\beta\neq 0,$ $$

and the optimum is attained at $u_{i}^{*}/\lVert u_{i}^{*}\rVert_{2}$. To see this, recall that $(\nu^{*})^{T}D_{i}Xu+\beta\lVert u\rVert_{2}\geq 0$ and $(\nu^{*})^{T}D_{i}Xu/\lVert u\rVert_{2}\geq-\beta$ for all nonzero $u\in\mathcal{K}_{i}$, which implies that $\min_{u\in\mathcal{S}_{i}}(\nu^{*})^{T}D_{i}Xu=-\beta$. Furthermore, by [D.2](#A4.Thmappxproposition2), there exists a unique minimizer of the problem $\min_{u\in\mathcal{S}_{i}}(\nu^{*})^{T}D_{i}Xu$, and $u_{i}^{*}/\lVert u_{i}^{*}\rVert_{2}=\bar{u}_{i}$. Hence choosing $c_{i}=\lVert u_{i}^{*}\rVert_{2}$ gives $c_{i}\geq 0$ that satisfies $u_{i}^{*}=c_{i}\bar{u}_{i}$. Hence, we have found $c_{i}\geq 0$, $d_{i}\geq 0$ that satisfies $u_{i}^{*}=c_{i}\bar{u}_{i},v_{i}^{*}=d_{i}\bar{v}_{i}$ and $\sum_{i=1}^{P}D_{i}X(u_{i}^{*}-v_{i}^{*})=$$\sum_{i=1}^{P}D_{i}X(c_{i}\bar{u}_{i}-d_{i}\bar{v}_{i})=y^{*}$, meaning $(u_{i}^{*},v_{i}^{*})_{i=1}^{P}\in\mathcal{P}^{*}$.
Now, we show that $\mathcal{P}^{*}_{\nu^{*}}\subseteq\Theta^{*}$. Take an element $(c_{i}\bar{u}_{i},d_{i}\bar{v}_{i})_{i=1}^{P}\in\mathcal{P}^{*}_{\nu^{*}}$. If $\bar{u}_{i}\neq 0$, we know that $(\nu^{*})^{T}D_{i}X\bar{u}_{i}=-\beta$. Similarly, if $\bar{v}_{i}\neq 0$, we know that $-(\nu^{*})^{T}D_{i}X\bar{v}_{i}=-\beta$. Also, if $\bar{u}_{i},\bar{v}_{i}\neq 0$, $\lVert\bar{u}_{i}\rVert_{2}=1,\lVert\bar{v}_{i}\rVert_{2}=1$, see the proof of [D.2](#A4.Thmappxproposition2) why this holds. Now, let’s calculate the objective of $(c_{i}\bar{u}_{i},d_{i}\bar{v}_{i})_{i=1}^{P}$. We know $\sum_{i=1}^{P}D_{i}X(c_{i}\bar{u}_{i}-d_{i}\bar{v}_{i})=y^{*}$, hence the objective becomes

$$ $L(y^{*},y)+\beta\sum_{\bar{u}_{i}\neq 0}c_{i}+\beta\sum_{\bar{v}_{i}\neq 0}d_{i},$ $$

using $\lVert\bar{u}_{i}\rVert_{2}=1,\lVert\bar{v}_{i}\rVert_{2}=1$. Now, as $\sum_{i=1}^{P}D_{i}X(c_{i}\bar{u}_{i}-d_{i}\bar{v}_{i})=y^{*}$, multiplying $(\nu^{*})^{T}$ on both sides gives $\sum_{\bar{u}_{i}\neq 0}c_{i}+\sum_{\bar{v}_{i}\neq 0}d_{i}=-\langle\nu^{*},y^{*}\rangle/\beta$. Hence, the calculated objective becomes

$$ $L(y^{*},y)-\langle\nu^{*},y^{*}\rangle,$ $$

hence for all points in $\mathcal{P}^{*}_{\nu^{*}}$, the objective becomes constant. We already know that $\Theta^{*}\subseteq\mathcal{P}^{*}_{\nu^{*}}$. This means all points in $\mathcal{P}^{*}_{\nu^{*}}$ have the same optimal objective value, and $\mathcal{P}^{*}_{\nu^{*}}\subseteq\Theta^{*}$. This finishes the proof.
∎

###### Corollary D.1 .

Consider the optimization problem in ([1](#S2.E1)). Denote the set of Clarke stationary points of ([1](#S2.E1)) as $\Theta_{C}$. The set

$$ $\bigcup_{j=1}^{m}\Big{\{}\frac{w_{j}}{\lVert w_{j}\rVert_{2}}\ |\ (w_{i},\alpha_{i})_{i=1}^{m}\in\Theta_{C},\ w_{j}\neq 0\Big{\}},$ $$

is finite, and each direction is determined by the dual optimum of the subsampled convex program.

###### Proof.

From [], we know that all Clarke stationary points of ([1](#S2.E1)) have a corresponding subsampled convex problem. More specifically, for any $(w_{i},\alpha_{i})_{i=1}^{m}\in\Theta_{C}$, we have a convex program with subsampled arrangement patterns $\tilde{D}_{1},\tilde{D}_{2},\cdots\tilde{D}_{m}\in\{D_{i}\}_{i=1}^{P}$,

$$ $\min_{u_{i},v_{i}\in\tilde{\mathcal{K}}_{i}}L\Big{(}\sum_{i=1}^{m}\tilde{D}_{i}X(u_{i}-v_{i}),y\Big{)}+\beta\Big{(}\sum_{i=1}^{m}\lVert u_{i}\rVert_{2}+\lVert v_{i}\rVert_{2}\Big{)},$ $$

and a solution mapping

$$ $(w_{i},\alpha_{i})=\begin{cases}(u_{i}/\sqrt{\lVert u_{i}\rVert_{2}},\ \sqrt{\lVert u_{i}\rVert_{2}})\quad if\quad u_{i}\neq 0,\\ (v_{i}/\sqrt{\lVert v_{i}\rVert_{2}},\ -\sqrt{\lVert v_{i}\rVert_{2}})\quad if\quad v_{i}\neq 0.\end{cases}$ $$

Hence, the set of first-layer directions of Clarke stationary points is contained in the set of optimal directions of 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 set

$$ $\bigcup_{j=1}^{m}\Big{\{}\frac{w_{j}}{\lVert w_{j}\rVert_{2}}\ |\ (w_{i},\alpha_{i})_{i=1}^{m}\in\Theta_{C},\ w_{j}\neq 0\Big{\}},$ $$

is a finite set. Furthermore, applying [Theorem 1](#Thmtheorem1) to the subsampled convex program leads to the wanted result.
∎

###### Definition D.1 .

###### Proposition D.1 .

###### Proof.

###### Proposition D.2 .

###### Proof.

###### Theorem D.1 .

###### Proof.

###### Corollary D.1 .

###### Proof.

## Appendix E Proofs in Section 3.2

In this section we prove [Theorem 2](#Thmtheorem2), using the cardinality-constrained optimal polytope $\mathcal{P}^{*}(m)$ defined in ([5](#S3.E5)). One thing to have in mind is that we are not trying to prove that $\mathcal{P}^{*}(m)$ and $\Theta^{*}(m)$, the optimal set of the original problem in ([1](#S2.E1)) with width $m$, are homeomorphic. Rather, we will argue that certain mappings enable us to link the connectivity behavior between $\mathcal{P}^{*}(m)$ and $\Theta^{*}(m)$ to arrive at [Theorem 2](#Thmtheorem2).

We first start by defining some relevant concepts. As a starting point, we define the cardinality of a solution.

###### Definition E.1 .

The cardinality of a solution $(u_{i},v_{i})_{i=1}^{P}\in\mathcal{P}^{*}$ is defined as

$$ $\mathrm{card}((u_{i},v_{i})_{i=1}^{P})=\sum_{i=1}^{P}1(u_{i}\neq 0)+1(v_{i}\neq 0).$ $$

We introduce the cardinality-constrained optimal polytope again.

###### Definition E.2 .

The cardinality constrained optimal polytope $\mathcal{P}^{*}(m)$ is defined as the set

$$ $\mathcal{P}^{*}(m):=\left\{(u_{i},v_{i})_{i=1}^{P}\ |\ (u_{i},v_{i})_{i=1}^{P}\in\mathcal{P}^{*},\mathrm{card}((u_{i},v_{i})_{i=1}^{P})\leq m\right\}\subseteq\mathbb{R}^{2dP}.$ (16) $$

One remark is that the largest possible cardinality of $\mathcal{P}^{*}$ may be huge: in worst case, it could be that the largest cardinality is in a scale of $P$, which is the number of all possible arrangement patterns. In general, the number of arrangement patterns are $O(n^{d})$, hence $\mathcal{P}^{*}(m)$ consists of a very small portion of $\mathcal{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 [], and is used to define the critical widths of the staircase.

###### Definition E.3 .

The irreducible solution set is defined as the set

$$ $\mathcal{P}^{*}_{irr}=\left\{(u_{i},v_{i})_{i=1}^{P}\ |\ (u_{i},v_{i})_{i=1}^{P}\in\mathcal{P}^{*},\ \{D_{i}Xu_{i}\}_{u_{i}\neq 0}\cup\{D_{i}Xv_{i}\}_{v_{i}\neq 0}\ \mathrm{linearly\leavevmode\nobreak\ independent}\right\}.$ (17) $$

One intuition of the irreducible solution set is that it is the set of “smallest solutions []”: if the set $\{D_{i}Xu_{i}\}_{u_{i}\neq 0}\cup\{D_{i}Xv_{i}\}_{v_{i}\neq 0}$ is linearly dependent we can find a strictly smaller conic combination using the vectors from $\{D_{i}Xu_{i}\}_{u_{i}\neq 0}\cup\{-D_{i}Xv_{i}\}_{v_{i}\neq 0}$. The set $\mathcal{P}^{*}_{irr}$ can be understood as a collection of solutions obtained from repeating this “pruning step” - a step that finds smaller solutions using linear dependence. A more rigorous definition of pruning is the following.

###### Definition E.4 .

([]) Pruning a solution $(u_{i},v_{i})_{i=1}^{P}\in\mathcal{P}^{*}$ means repeating:
1. Finding a nontrivial linear combination

$$ $\sum_{u_{i}\neq 0}c_{i}D_{i}Xu_{i}+\sum_{v_{i}\neq 0}d_{i}D_{i}Xv_{i}=0,$ $$

and without loss of generality assume $d_{1}>0$.
2. Constructing a solution with strictly less cardinality $(u^{\prime}_{i},v^{\prime}_{i})_{i=1}^{P}=((1+c_{i}t)u_{i},(1-d_{i}t)v_{i})_{i=1}^{P}$, where $t=\min\{\min_{c_{i}<0}-\frac{1}{c_{i}},\min_{d_{i}>0}\frac{1}{d_{i}}\}$,
until the set $\{D_{i}Xu_{i}\}_{u_{i}\neq 0}\cup\{D_{i}Xv_{i}\}_{v_{i}\neq 0}$ is linearly independent.

The notion of minimality gives a discrete structure in $\mathcal{P}^{*}_{irr}$, hence the phase transitional behavior follows. The two critical widths of interest are the minimum / maximum cardinality of $\mathcal{P}^{*}_{irr}$. We denote

$$ $m^{*}:=\min_{(u_{i},v_{i})_{i=1}^{P}\in\mathcal{P}^{*}_{\mathrm{irr}}}\mathrm{card}((u_{i},v_{i})_{i=1}^{P}),\ \ M^{*}:=\max_{(u_{i},v_{i})_{i=1}^{P}\in\mathcal{P}^{*}_{\mathrm{irr}}}\mathrm{card}((u_{i},v_{i})_{i=1}^{P}).$ $$

###### Remark E.1 .

These widths can be found computationally by the following scheme: for $t=1$ to $n$, choose $t$ vectors from the set $\{D_{i}X\bar{u}_{i}\}_{i=1}^{P}\cup\{D_{i}X\bar{v}_{i}\}_{i=1}^{P}$, where $\bar{u}_{i},\bar{v}_{i}$ are optimal directions defined in [Theorem 1](#Thmtheorem1). Check if they are linearly independent and can express $y^{*}$ as the conic combination of the $t$ vectors. The first value of $t$ that meets both criteria becomes $m^{*}$, and $M^{*}$ will be updated each time $t$ meets both criteria until $t$ becomes $n$.

The two specific discontinuity results we can achieve are the following:

###### Proposition E.1 .

$\mathcal{P}^{*}(m^{*})$ is a finite set.

###### Proof.

Consider two points $(u_{i},v_{i})_{i=1}^{P},(u_{i}^{\prime},v_{i}^{\prime})_{i=1}^{P}\in\mathcal{P}^{*}(m^{*})$. Suppose the two points have the same support, i.e. $u_{i}\neq 0\Leftrightarrow u_{i}^{\prime}\neq 0$ and $v_{i}\neq 0\Leftrightarrow v_{i}^{\prime}\neq 0$ for $i\in[P]$. We know that as $\mathcal{P}^{*}(m^{*})\subseteq\mathcal{P}^{*}$,

$$ $\sum_{i=1}^{P}D_{i}X(u_{i}-v_{i})=y^{*}=\sum_{i=1}^{P}D_{i}X(u_{i}^{\prime}-v_{i}^{\prime}).$ $$

Now, let’s write the indices $\{i|u_{i}\neq 0\}=\{a_{1},a_{2},\cdots a_{t}\}$, $\{i|v_{i}\neq 0\}=\{b_{1},b_{2},\cdots b_{s}\}$. We have that $t+s\leq m^{*}$ as $(u_{i},v_{i})_{i=1}^{P}\in\mathcal{P}^{*}(m^{*})$. From [Theorem 1](#Thmtheorem1), we know the existence of $c_{a_{i}},c^{\prime}_{a_{i}}\geq 0$ for $i\in[t]$ and $d_{b_{i}},d^{\prime}_{b_{i}}\geq 0$ for $i\in[s]$ that satisfies

$$ $u_{a_{i}}=c_{a_{i}}\bar{u}_{a_{i}},u^{\prime}_{a_{i}}=c^{\prime}_{a_{i}}\bar{u}_{a_{i}},\quad\forall i\in[t],$ $$

$$ $v_{b_{i}}=d_{b_{i}}\bar{v}_{b_{i}},v^{\prime}_{b_{i}}=d^{\prime}_{a_{i}}\bar{v}_{b_{i}},\quad\forall i\in[s].$ $$

This means that

$$ $\sum_{i=1}^{t}c_{a_{i}}D_{a_{i}}X\bar{u}_{a_{i}}-\sum_{i=1}^{s}d_{b_{i}}D_{b_{i}}X\bar{v}_{b_{i}}=\sum_{i=1}^{t}c^{\prime}_{a_{i}}D_{a_{i}}X\bar{u}_{a_{i}}-\sum_{i=1}^{s}d^{\prime}_{b_{i}}D_{b_{i}}X\bar{v}_{b_{i}}=y^{*},$ $$

and as $c_{a_{i}},d_{b_{i}}$ s are not all the same, we have that the set

$$ $\{D_{a_{i}}X\bar{u}_{a_{i}}\}_{i=1}^{t}\cup\{D_{b_{i}}X\bar{v}_{b_{i}}\}_{i=1}^{s}$ $$

is linearly dependent. Now we apply pruning defined in [E.4](#A5.Thmappxdefinition4) to find an irreducible solution with cardinality strictly less than $t+s=m^{*}$, which is a contradiction to the minimality of $m^{*}$. This implies that two different points in $\mathcal{P}^{*}(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,

$$ $|\mathcal{P}^{*}(m^{*})|\leq\sum_{j=1}^{m^{*}}{2P\choose j}.$ $$

∎

###### Proposition E.2 .

$\mathcal{P}^{*}(M^{*})$ has an isolated point, i.e. it has a point $p\in\mathcal{P}^{*}(M^{*})$ that has no path in $\mathcal{P}^{*}(M^{*})$ from $p$ to a different point $p^{\prime}$.

###### Proof.

Take the maximal-cardinality solution from $(u^{\circ}_{i},v^{\circ}_{i})_{i=1}^{P}\in\mathcal{P}^{*}_{irr}$, namely the solution

$$ $(u^{\circ}_{i},v^{\circ}_{i})_{i=1}^{P}\in\mathcal{P}^{*},\{D_{i}Xu^{\circ}_{i}\}_{u^{\circ}_{i}\neq 0}\cup\{D_{i}Xv^{\circ}_{i}\}_{v^{\circ}_{i}\neq 0}\ linearly\ independent,$ $$

and $\mathrm{card}((u^{\circ}_{i},v^{\circ}_{i})_{i=1}^{P})=M^{*}$. Assume the existence of a continuous function $f:[0,1]\rightarrow\mathcal{P}^{*}(M^{*})$ satisfying

$$ $f(0)=(u^{\circ}_{i},v^{\circ}_{i})_{i=1}^{P},\ f(1)=(u^{\prime}_{i},v^{\prime}_{i})_{i=1}^{P},\ f(0)\neq f(1).$ $$

Now, write $f(t)=(u_{i}(t),v_{i}(t))_{i=1}^{P}$ and define

$$ $c_{i}(t)=\begin{cases}0\quad if\quad\bar{u}_{i}=0\\ \lVert u_{i}(t)\rVert_{2}\quad otherwise,\end{cases}$ $$

$$ $d_{i}(t)=\begin{cases}0\quad if\quad\bar{v}_{i}=0\\ \lVert v_{i}(t)\rVert_{2}\quad otherwise,\end{cases}$ $$

For definition of $\bar{u}_{i},\bar{v}_{i}$, see [Theorem 1](#Thmtheorem1). Some things to notice are:
i) The functions $c_{i}(t),d_{i}(t):[0,1]\rightarrow\mathbb{R}$ are continuous.
ii) $f(t)=(c_{i}(t)\bar{u}_{i},d_{i}(t)\bar{v}_{i})_{i=1}^{P}$. This holds because if $\bar{u}_{i}\neq 0$, $\lVert\bar{u}_{i}\rVert_{2}=1$, and same for $\bar{v}_{i}$.
iii) $\sum_{i=1}^{P}1(c_{i}(t)\neq 0)+1(d_{i}(t)\neq 0)\leq M^{*}$, and $\sum_{i=1}^{P}1(c_{i}(0)\neq 0)+1(d_{i}(0)\neq 0)=M^{*}$. The former holds because $f$ is a path in $\mathcal{P}^{*}(M^{*})$, and the latter holds because $(u^{\circ}_{i},v^{\circ}_{i})_{i=1}^{P}$ has cardinality $M^{*}$.
iv) We know that there exists $t^{\prime}\in[0,1]$ that satisfies $(c_{i}(t^{\prime}),d_{i}(t^{\prime}))_{i=1}^{P}\neq(c_{i}(0),d_{i}(0))_{i=1}^{P}$. It is because $f(0)\neq f(1)$.
Based on the observations, let’s prove that if there exists such $f$, the set $\{D_{i}Xu^{\circ}_{i}\}_{u^{\circ}_{i}\neq 0}\cup\{D_{i}Xv^{\circ}_{i}\}_{v^{\circ}_{i}\neq 0}$ is linearly dependent. Thus we will arrive at a contradiction and will be able to show that there is no such $f$, and $(u^{\circ}_{i},v^{\circ}_{i})_{i=1}^{P}$ is isolated.
Let’s define $t_{1}$ as

$$ $t_{1}=\inf_{t\geq 0}\left\{t\ |\ \sum_{i=1}^{P}(c_{i}(0)-c_{i}(t))^{2}+(d_{i}(0)-d_{i}(t))^{2}>0\right\}.$ $$

In other words, $t_{1}$ is the instant where $f(0)\neq f(t)$. From observation iv), we know that $t_{1}\in[0,1]$.
Another fact that we can make is that

$$ $\sum_{i=1}^{P}(c_{i}(0)-c_{i}(t_{1}))^{2}+(d_{i}(0)-d_{i}(t_{1}))^{2}=0.$ (18) $$

The reason is because if $\sum_{i=1}^{P}(c_{i}(0)-c_{i}(t_{1}))^{2}+(d_{i}(0)-d_{i}(t_{1}))^{2}>0$, we can find some $\epsilon$ that will make $\sum_{i=1}^{P}(c_{i}(0)-c_{i}(t_{1}-\epsilon))^{2}+(d_{i}(0)-d_{i}(t_{1}-\epsilon))^{2}>0$ because of continuity, which is a contradiction that $t_{1}$ is the infremum (because we have found a smaller $t$ that makes $\sum_{i=1}^{P}(c_{i}(0)-c_{i}(t))^{2}+(d_{i}(0)-d_{i}(t))^{2}>0$).
At last, we know that for any $\epsilon>0$, there exists $t_{\epsilon}\in(t_{1},t_{1}+\epsilon)$ that satisfies

$$ $\sum_{i=1}^{P}(c_{i}(0)-c_{i}(t_{\epsilon}))^{2}+(d_{i}(0)-d_{i}(t_{\epsilon}))^{2}>0.$ (19) $$

If there is no $t\in(t_{1},t_{1}+\epsilon)$ that satisfies $\sum_{i=1}^{P}(c_{i}(0)-c_{i}(t))^{2}+(d_{i}(0)-d_{i}(t))^{2}>0$ for some $\epsilon>0$, it means that for all $t\in[0,t_{1}+\epsilon_{2}]$, $\sum_{i=1}^{P}(c_{i}(0)-c_{i}(t))^{2}+(d_{i}(0)-d_{i}(t))^{2}=0$: hence, the infremum should be strictly larger than $t_{1}$, which is a contradiction.

Now let’s prove the claim that if there exists such $f$, the set $\{D_{i}Xu^{\circ}_{i}\}_{u^{\circ}_{i}\neq 0}\cup\{D_{i}Xv^{\circ}_{i}\}_{v^{\circ}_{i}\neq 0}$ is linearly dependent. From ([18](#A5.E18)), we know that

$$ $c_{i}(0)=c_{i}(t_{1}),\quad d_{i}(0)=d_{i}(t_{1})\quad\forall i\in[P].$ $$

Take $\epsilon_{0}>0$ sufficiently small so that for all $i\in[P]$ that satisfies $c_{i}(0)>0$, $c_{i}(t)>0$ for all $t\in[t_{1}-\epsilon_{0},t_{1}+\epsilon_{0}]$, and for all $i\in[P]$ that satisfies $d_{i}(0)>0$, $d_{i}(t)>0$ for all $t\in[t_{1}-\epsilon_{0},t_{1}+\epsilon_{0}]$. Such $\epsilon_{0}$ exists due to the continuity of $c_{i},d_{i}$. Due to the definition, we know that

$$ $M^{*}=\sum_{i=1}^{P}1(c_{i}(0)\neq 0)+1(d_{i}(0)\neq 0)\leq\sum_{i=1}^{P}1(c_{i}(t)\neq 0)+1(d_{i}(t)\neq 0)\leq M^{*},$ $$

(see observation iii) if any confusion exists), for all $t\in[t_{1}-\epsilon_{0},t_{1}+\epsilon_{0}]$, and

$$ $\sum_{i=1}^{P}1(c_{i}(t)\neq 0)+1(d_{i}(t)\neq 0)=M^{*},\quad\forall t\in[t_{1}-\epsilon_{0},t_{1}+\epsilon_{0}].$ $$

This means that for all $t\in[t_{1}-\epsilon_{0},t_{1}+\epsilon_{0}],$ we know that $c_{i}(0)>0\Leftrightarrow c_{i}(t)>0$ and $d_{i}(0)>0\Leftrightarrow d_{i}(t)>0$.
For that $\epsilon_{0}$, we can find $t_{\epsilon_{0}}$ that was defined in ([19](#A5.E19)). As $t_{\epsilon_{0}}$ satisfies

$$ $\sum_{i=1}^{P}(c_{i}(0)-c_{i}(t_{\epsilon_{0}}))^{2}+(d_{i}(0)-d_{i}(t_{\epsilon_{0}}))^{2}>0,$ $$

$(c_{i}(0),d_{i}(0))_{i=1}^{P}\neq(c_{i}(t_{\epsilon_{0}}),d_{i}(t_{\epsilon_{0}}))_{i=1}^{P}$. Also, $c_{i}(0)>0\Leftrightarrow c_{i}(t_{\epsilon_{0}})>0$ and $d_{i}(0)>0\Leftrightarrow d_{i}(t_{\epsilon_{0}})>0$. Now we have found two different solutions $(c_{i}(0)\bar{u}_{i},d_{i}(0)\bar{v}_{i})_{i=1}^{P}$, $(c_{i}(t_{\epsilon_{0}})\bar{u}_{i},d_{i}(t_{\epsilon_{0}})\bar{v}_{i})_{i=1}^{P}\in\mathcal{P}^{*}(M^{*})$, which means that

$$ $\sum_{i=1}^{P}c_{i}(0)D_{i}X\bar{u}_{i}-d_{i}(0)D_{i}X\bar{v}_{i}=y^{*}=\sum_{i=1}^{P}c_{i}(t_{\epsilon_{0}})D_{i}X\bar{u}_{i}-d_{i}(t_{\epsilon_{0}})D_{i}X\bar{v}_{i}.$ (20) $$

As $(c_{i}(0),d_{i}(0))_{i=1}^{P}\neq(c_{i}(t_{\epsilon_{0}}),d_{i}(t_{\epsilon_{0}}))_{i=1}^{P}$ and $c_{i}(0)>0\Leftrightarrow c_{i}(t_{\epsilon_{0}})>0,d_{i}(0)>0\Leftrightarrow d_{i}(t_{\epsilon_{0}})>0$, we can see that ([20](#A5.E20)) is two different linear combinations of the set $\{D_{i}Xu^{\circ}_{i}\}_{u^{\circ}_{i}\neq 0}\cup\{D_{i}Xv^{\circ}_{i}\}_{v^{\circ}_{i}\neq 0}$ - hence the set $\{D_{i}Xu^{\circ}_{i}\}_{u^{\circ}_{i}\neq 0}\cup\{D_{i}Xv^{\circ}_{i}\}_{v^{\circ}_{i}\neq 0}$ is linearly dependent.

As we claimed, we have arrived at a contradiction assuming a continuous path from $(u_{i}^{\circ},v_{i}^{\circ})_{i=1}^{P}$. Hence the point is isolated.
∎

Next, we pay attention to the connectivity results of $\mathcal{P}^{*}(m)$. Our starting point will be noticing that for any $(u_{i},v_{i})_{i=1}^{P}\in\mathcal{P}^{*}$ which is not in $\mathcal{P}^{*}_{irr}$, the pruning mechanism defined in [E.4](#A5.Thmappxdefinition4) gives a continuous path into $\mathcal{P}^{*}_{irr}$. This means that if we can connect two points in $\mathcal{P}^{*}_{irr}\cap\mathcal{P}^{*}(m)$ with a continuous path in $\mathcal{P}^{*}(m)$, the set $\mathcal{P}^{*}(m)$ is connected.

###### Proposition E.3 .

Consider $(u_{i},v_{i})_{i=1}^{P}\in\mathcal{P}^{*}-\mathcal{P}^{*}_{irr}$. Let $m=\mathrm{card}((u_{i},v_{i})_{i=1}^{P})$. Then, there exists a continuous path in $\mathcal{P}^{*}(m)$ that starts with $(u_{i},v_{i})_{i=1}^{P}$ and ends with a different point $(u_{i}^{\prime},v_{i}^{\prime})_{i=1}^{P}\in\mathcal{P}^{*}(m)\cap\mathcal{P}^{*}_{irr}$.

###### Proof.

We will find such path by pruning the solution as in [E.4](#A5.Thmappxdefinition4). 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 $\mathcal{P}^{*}(m)$. 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 a irreducible solution, meaning the final solution we get from pruning is in $\mathcal{P}^{*}(m)\cap\mathcal{P}^{*}_{irr}$.
∎

We have two different strategies to prove the connectedness of $\mathcal{P}^{*}(m)$. One is directly interpolating the two solutions in $\mathcal{P}^{*}_{irr}$, and increasing $m$ to guarantee the validity of such interpolation. From this, we obtain one critical width $m^{*}+M^{*}$.

###### Proposition E.4 .

The set $\mathcal{P}^{*}(m^{*}+M^{*})$ is connected.

###### Proof.

We first prove that two points $A,B\in\mathcal{P}^{*}(m^{*}+M^{*})\cap\mathcal{P}^{*}_{irr}$ are connected with a continuous path in $\mathcal{P}^{*}(m^{*}+M^{*})$.
Take two points $A\neq B\in\mathcal{P}^{*}(m^{*}+M^{*})\cap\mathcal{P}^{*}_{irr}$. One observation that we can make is that $A$ has a continuous path in $\mathcal{P}^{*}(m^{*}+M^{*})$ to a certain solution $A_{m}\in\mathcal{P}^{*}_{irr}$ that satisfies $\mathrm{card}(A_{m})=m^{*}$. The construction of such a path is simple: interpolate $A$ and $A_{m}$, i.e. $f(t)=(1-t)A+tA_{m}$. As we know

$$ $\mathrm{card}((1-t)A+tA_{m})\leq\mathrm{card}(A)+\mathrm{card}(A_{m})\leq M^{*}+m^{*},$ $$

the path has cardinality $\leq m^{*}+M^{*}$. The last inequality follows from the fact that $A\in\mathcal{P}^{*}_{irr}$ and $\mathrm{card}(A)\leq M^{*}$. Due to the polytope characterization, $\mathcal{P}^{*}$ is convex, and the path is in $\mathcal{P}^{*}$. Combining these two, we know the existence of a path from $A$ to $A_{m}$ in $\mathcal{P}^{*}(m^{*}+M^{*})$.
Similarly, we know the existence of a path from $B$ to $B_{m}$ in $\mathcal{P}^{*}(m^{*}+M^{*})$. At last, we know the existence of a path from $A_{m}$ to $B_{m}$, again by interpolating these two. Concluding, for any two $A,B\in\mathcal{P}^{*}(m^{*}+M^{*})\cap\mathcal{P}^{*}_{irr}$, there exists a continuous path in $\mathcal{P}^{*}(m^{*}+M^{*})$.
Now, take any two points $A^{\prime},B^{\prime}\in\mathcal{P}^{*}(m^{*}+M^{*})$. From [E.3](#A5.Thmappxproposition3), there exists a continuous path in $\mathcal{P}^{*}(m^{*}+M^{*})$ that starts from $A^{\prime}$ to a certain $A_{irr}\in\mathcal{P}^{*}(m^{*}+M^{*})\cap\mathcal{P}^{*}_{irr}$, and similarly there exists a path from $B^{\prime}$ to $B_{irr}$. At last, there is a continuous path from $A_{irr}$ to $B_{irr}$ in $\mathcal{P}^{*}(m^{*}+M^{*})$. Connect all paths to find a continuous path from $A^{\prime}$ to $B^{\prime}$ in $\mathcal{P}^{*}(m^{*}+M^{*})$.
∎

Another strategy is more involved, which is not directly interpolating two solutions $A,B$ in $\mathcal{P}^{*}_{irr}$, but repeatedly interpolating $A$ with parts of $B$ until the two are connected with a path. We start with a particular lemma.

###### Lemma E.1 .

Suppose we have two linearly independent sets $A=\{a_{1},a_{2},\cdots a_{m}\}$, $B=\{b_{1},b_{2},\cdots b_{k}\}\subseteq\mathbb{R}^{n}$ and a given subset $\mathcal{I}=\{a_{i_{1}},a_{i_{2}},\cdots a_{i_{t}}\}\subset A$. Also,

$$ $\sum_{i=1}^{m}\lambda_{i}a_{i}=\sum_{i=1}^{k}\mu_{i}b_{i},$ $$

for some $\lambda\in\mathbb{R}^{m}$ that satisfies $\sum_{j=1}^{t}\lambda_{i_{j}}>0$, and $\mu\in\mathbb{R}^{k}$ that satisfies
$\mu>0$. Then, there exists a vector $\mu^{*}\in\mathbb{R}^{k}$ that satisfies the following three properties:
1) $\lVert\mu^{*}\rVert_{0}\leq n-m+1$.
2) $\mu^{*}\geq 0$.
3) $\sum_{i=1}^{k}\mu^{*}_{i}b_{i}\in span(\{a_{1},a_{2},\cdots a_{m}\})$ and when we express

$$ $\sum_{i=1}^{k}\mu^{*}_{i}b_{i}=\sum_{i=1}^{m}\delta_{i}a_{i},$ $$

$$ $\sum_{j=1}^{t}\delta_{i_{j}}>0.$ $$

###### Proof.

If $k\leq n-m+1$ there is nothing to prove. Assume $k>n-m+1$. Showing the existence of a vector $\tilde{\mu}$ that satisfies $\lVert\tilde{\mu}\rVert_{0}<\lVert\mu\rVert_{0}$, $\tilde{\mu}\geq 0$ and

$$ $\sum_{i=1}^{k}\tilde{\mu}_{i}b_{i}\in span(\{a_{1},a_{2},\cdots a_{m}\}),\quad\sum_{i=1}^{k}\tilde{\mu}_{i}b_{i}=\sum_{i=1}^{m}\delta_{i}a_{i}\quad and\quad\sum_{j=1}^{t}\delta_{i_{j}}>0,$ $$

is enough to prove our proposed claim. That is because if the existence of such $\tilde{\mu}$ is proved, we can apply the existence result again to $A=\{a_{1},a_{2},\cdots,a_{m}\}$ and $\tilde{B}=\{b_{i}|i\in[k],\tilde{\mu}_{i}\neq 0\}$ with the same $\mathcal{I}$. The premises are all satisfied: from the definition of $\tilde{\mu}$ we know that

$$ $\sum_{i\in[k],\tilde{\mu}_{i}\neq 0}\tilde{\mu}_{i}b_{i}=\sum_{i=1}^{m}\delta_{i}a_{i},\ \ \sum_{j=1}^{t}\delta_{i_{j}}>0,$ $$

and $\tilde{\mu}_{i}>0$ if $\tilde{\mu}_{i}\neq 0$. Moreover, $|\tilde{B}|<|B|$. This means if we prove the existence of such $\tilde{\mu}$ and iteratively apply the existence result as stated above, we will arrive at a set $B^{\circ}\subseteq B$ that satisfies

$$ $|B^{\circ}|\leq n-m+1,\quad\sum_{b_{i}\in B^{\circ}}\mu^{\circ}_{i}b_{i}=\sum_{i=1}^{m}\delta_{i}^{\circ}a_{i},\quad\sum_{j=1}^{t}\delta_{i_{j}}^{\circ}>0,\quad\mu^{\circ}_{i}>0\ \ if\ \ b_{i}\in B^{\circ},\ \ 0\ \ otherwise.$ $$

The reason why $|B^{\circ}|\leq n-m+1$ is that if $|B^{\circ}|>n-m+1$, we can find a subset of $B^{\circ}$ with strictly less cardinality with the same property, hence it is not the terminal set. For that set, choosing $\mu^{\circ}=\mu^{*}$ gives the wanted vector.

Now we show the existence of such $\tilde{\mu}$ when $k>n-m+1$. We first extend $\{a_{1},a_{2},\cdots a_{m}\}$ to a basis of $\mathbb{R}^{n}$, and note it as $\{a_{1},a_{2},\cdots a_{n}\}$. Express each $b_{i}$ s as

$$ $b_{i}=\sum_{j=1}^{n}\gamma_{ij}a_{j}.$ $$

where $i\in[k]$. Now, write $\Gamma\in\mathbb{R}^{n\times k}$ as $\Gamma_{ij}=\gamma_{ji}$. What we know is the relation

$$ $\Gamma\mu=\begin{bmatrix}\lambda\\ 0_{n-m}\end{bmatrix},$ $$

which is simply the coordinate representation of $\sum_{i=1}^{k}\mu_{i}b_{i}.$ Now we know the set

$$ $\{\mu\in\mathbb{R}^{k}\ |\ 1^{T}\Gamma[i_{1},i_{2},\cdots i_{t}]\mu=0,\Gamma[m+1]^{T}\mu=0,\cdots\Gamma[n]^{T}\mu=0\}$ $$

has dimension at least $k-n+m-1$, as each linear constraint decreases the dimension at most 1. Here $\Gamma[p_{1},p_{2},\cdots p_{r}]\in\mathbb{R}^{r\times k}$ denotes the concatenation of $r$ rows of $\Gamma$, $\Gamma[p_{1}]$ to $\Gamma[p_{r}]$. As $k-n+m-1>0$, there exists a nonzero $\mu^{\prime}$ that satisfies

$$ $\Gamma\mu^{\prime}=\begin{bmatrix}\lambda^{\prime}\\ 0_{n-m}\end{bmatrix},\quad\sum_{j=1}^{t}\lambda^{\prime}_{i_{j}}=0.$ $$

For that $\mu^{\prime}$, consider $\mu+\epsilon\mu^{\prime}$ and either increase or decrease $\epsilon$ until the cardinality of $\mu$ decreases. As $\mu>0$, we can always find such $\epsilon$ that satisfies $\lVert\mu+\epsilon\mu^{\prime}\rVert_{0}<\lVert\mu\rVert_{0}$. As we stop when the cardinality changes, $\mu+\epsilon\mu^{\prime}\geq 0$ should also hold. At last, we know that

$$ $\Gamma(\mu+\epsilon\mu^{\prime})=\begin{bmatrix}\lambda+\epsilon\lambda^{\prime}\\ 0_{n-m}\end{bmatrix},$ $$

and as $\sum_{j=1}^{t}\lambda^{\prime}_{i_{j}}=0$, $\sum_{j=1}^{t}(\lambda_{i_{J}}+\epsilon\lambda^{\prime}_{i_{j}})>0$. As the values of $\Gamma\mu$ directly correspond to the coordinate representation of $\{a_{1},a_{2},\cdots a_{n}\}$, we know that $\mu+\epsilon\mu^{\prime}$ is the $\tilde{\mu}$ that we were looking for. This finishes the proof.
∎

The necessary width in this case is $n+1$, and we obtain the following result.

###### Theorem E.1 .

The set $\mathcal{P}^{*}(n+1)$ is connected.

###### Proof.

Similar to the proof of [E.4](#A5.Thmappxproposition4), we show that for any two $A,B\in\mathcal{P}^{*}(n+1)\cap\mathcal{P}^{*}_{irr}$, they are connected with a continuous path in $\mathcal{P}^{*}(n+1)$. The rest will directly follow.
First, let’s write $A=(u_{i},v_{i})_{i=1}^{P},B=(u_{i}^{\prime},v_{i}^{\prime})_{i=1}^{P}$. Also, let’s write

$$ $\mathcal{A}=\{D_{i}X\bar{u}_{i}\}_{u_{i}\neq 0}\cup\{-D_{i}X\bar{v}_{i}\}_{v_{i}\neq 0},\quad\mathcal{B}=\{D_{i}X\bar{u}_{i}\}_{u^{\prime}_{i}\neq 0}\cup\{-D_{i}X\bar{v}_{i}\}_{v^{\prime}_{i}\neq 0},$ $$

and note them as $\mathcal{A}=\{a_{1},a_{2},\cdots a_{m}\}\subseteq\mathbb{R}^{n}$, $\mathcal{B}=\{b_{1},b_{2},\cdots b_{k}\}\subseteq\mathbb{R}^{n}$. At last, $\lambda_{1},\lambda_{2},\cdots\lambda_{m}$, $\mu_{1},\mu_{2},\cdots\mu_{k}$ are unique nonnegative numbers that satisfy

$$ $\sum_{i=1}^{m}\lambda_{i}a_{i}=\sum_{i=1}^{k}\mu_{i}b_{i}=y^{*}.$ $$

The uniqueness follows from the fact that $A,B\in\mathcal{P}^{*}(n+1)\cap\mathcal{P}^{*}_{irr}$, and the nonnegativeness follows from the optimal polytope characterization in [Theorem 1](#Thmtheorem1). Furthermore, note that $\lambda_{p}>0$ for all $p\in[m]$, $\mu_{q}>0$ for all $q\in[k]$. For example, if $a_{p}=D_{i}X\bar{u}_{i}$ for some $u_{i}\neq 0$, $\lambda_{p}=\lVert u_{i}\rVert_{2}>0$. The rest is similar.
Our main proof strategy will be finding $k+m$ continuous functions $F_{1},F_{2},\cdots F_{m},G_{1},G_{2},\cdots,$ $G_{k}:[0,1]\rightarrow\mathbb{R}$ that satisfies:
Property 1) $F_{i}(0)=\lambda_{i},F_{i}(1)=0,F_{i}(t)\geq 0\quad\forall i\in[m],t\in[0.1]$.
Property 2) $G_{j}(0)=0,G_{j}(1)=\mu_{j},G_{j}(t)\geq 0\quad\forall j\in[k],t\in[0.1]$.
Property 3)

$$ $\sum_{i=1}^{m}F_{i}(t)a_{i}+\sum_{j=1}^{k}G_{j}(t)b_{j}=y^{*}\quad\forall t\in[0,1].$ $$

Property 4)

$$ $\sum_{i=1}^{m}1(F_{i}(t)>0)+\sum_{j=1}^{k}1(G_{j}(t)>0)\leq n+1\quad\forall t\in[0,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 $A$ to $B$ in $\mathcal{P}^{*}(n+1)$. The specific path we construct is: $(u_{i}(t),v_{i}(t))_{i=1}^{P}$ given as

$$ $u_{i}(t)=\begin{cases}(F_{p}(t)+G_{q}(t))\bar{u}_{i}\quad if\quad a_{p}=b_{q}=D_{i}X\bar{u}_{i}\\ F_{p}(t)\bar{u}_{i}\quad if\quad a_{p}=D_{i}X\bar{u}_{i},\ \nexists\ q\in[k]\ \ such\ that\ b_{q}=D_{i}X\bar{u}_{i}.\\ G_{q}(t)\bar{u}_{i}\quad if\quad b_{q}=D_{i}X\bar{u}_{i},\ \nexists\ p\in[m]\ such\ that\ a_{p}=D_{i}X\bar{u}_{i}\\ 0\quad otherwise.\end{cases}$ $$

$$ $v_{i}(t)=\begin{cases}(F_{p}(t)+G_{q}(t))\bar{v}_{i}\quad if\quad a_{p}=b_{q}=-D_{i}X\bar{v}_{i}\\ F_{p}(t)\bar{v}_{i}\quad if\quad a_{p}=-D_{i}X\bar{v}_{i},\ \nexists\ q\in[k]\ such\ that\ b_{q}=-D_{i}X\bar{v}_{i}.\\ G_{q}(t)\bar{v}_{i}\quad if\quad b_{q}=-D_{i}X\bar{v}_{i},\ \nexists\ q\in[m]such\ that\ a_{p}=-D_{i}X\bar{v}_{i}\\ 0\quad otherwise.\end{cases}$ $$

Let’s check that $(u_{i}(t),v_{i}(t))_{i=1}^{P}$ is a path from $A$ to $B$ in $\mathcal{P}^{*}(n+1)$. As $F_{i}(1)=0$ for all $i\in[m]$, $G_{j}(0)=0$ for all $j\in[k]$, we can see that $(u_{i}(0),v_{i}(0))_{i=1}^{P}=A$, $(u_{i}(1),v_{i}(1))_{i=1}^{P}=B$. Also, we can see that it is a curve in $\mathcal{P}^{*}$: all $u_{i}(t)$, $v_{i}(t)$ are nonnegative multiples of $\bar{u}_{i},\bar{v}_{i}$, and we know that

$$ $\sum_{i=1}^{P}D_{i}X(u_{i}(t)-v_{i}(t))=\sum_{i=1}^{m}F_{i}(t)a_{i}+\sum_{j=1}^{k}G_{j}(t)b_{j}=y^{*}.$ $$

Moreover, the cardinality of $(u_{i}(t),v_{i}(t))_{i=1}^{P}$ bounded with

$$ $\mathrm{card}((u_{i}(t),v_{i}(t))_{i=1}^{P})\leq\sum_{i=1}^{m}1(F_{i}(t)>0)+\sum_{j=1}^{k}1(G_{j}(t)>0)\leq n+1$ $$

hence the proposed path becomes a continuous path in $\mathcal{P}^{*}(n+1)$.
Now, we describe how we find such $m+k$ continuous functions. We do:
Step 0) Initialize $\mathcal{C}=A$, $f_{i}(0)=\lambda_{i},g_{i}(0)=0$.
Step 1) While $T=0,1,\cdots,$ repeat:

- •
If $\mathcal{C}\subseteq\mathcal{B}$, break.
- •
(Facts that hold from the previous iteration) Let’s write $\mathcal{C}=\{a_{i_{1}},a_{i_{2}},\cdots a_{i_{r}}\}\cup\{b_{j_{1}},b_{j_{2}},\cdots b_{j_{s}}\}$. We inductively have:
1) $\mathcal{C}$ is a linearly independent set.
2) $f_{i}(T)\geq 0\quad\forall i\in[m],g_{j}(T)\geq 0\quad\forall j\in[k]$.
3) $f_{i}(T)>0\Leftrightarrow i\in\{i_{1},i_{2},\cdots i_{r}\}$, $g_{j}(T)>0\Leftrightarrow j\in\{j_{1},j_{2},\cdots j_{s}\}$.
4)
$\sum_{w=1}^{r}f_{i_{w}}(T)a_{i_{w}}+\sum_{w=1}^{s}g_{j_{w}}(T)b_{j_{w}}=y^{*}.$
- •
(Applying [E.1](#A5.Thmappxlemma1)) We also know that $\sum_{w=1}^{k}\mu_{w}b_{w}=y^{*}$ and $\mu_{w}>0$ $\forall w\in[k]$. Now we check the conditions to apply [E.1](#A5.Thmappxlemma1) with $A:=\mathcal{C}$, $B:=\mathcal{B}$, given subset $\{a_{i_{1}},a_{i_{2}},\cdots,a_{i_{r}}\}\subseteq A$. Then we know that $\mathcal{C},B$ are linearly independent,
$\sum_{w=1}^{r}f_{i_{w}}(T)a_{i_{w}}+\sum_{w=1}^{s}g_{j_{w}}(T)b_{j_{w}}=\sum_{w=1}^{k}\mu_{w}b_{w}=y^{*},$
and $\sum_{w=1}^{r}f_{i_{w}}(T)>0$, $\mu_{w}>0$ for all $w\in[k]$. Thus all conditions for [E.1](#A5.Thmappxlemma1) are met, and we can find $\tilde{\lambda}_{i_{w}}$ for $w\in[r]$, $\tilde{\mu}_{j_{w}}$ for $w\in[s]$, $\mu^{*}$ that satisfies
$\lVert\mu^{*}\rVert_{0}\leq n+1-r-s,\ \ \mu^{*}\geq 0,\ \ \sum_{w=1}^{r}\tilde{\lambda}_{i_{w}}a_{i_{w}}+\sum_{w=1}^{s}\tilde{\mu}_{j_{w}}b_{j_{w}}=\sum_{w=1}^{k}\mu_{w}^{*}b_{w},\ \ \sum_{w=1}^{r}\tilde{\lambda}_{i_{w}}>0.$
- •
(Update 1) Now we update the values of $f_{i},g_{j}$ as the following:
$f_{i}(t)=\begin{cases}f_{i}(T)=0\quad if\quad i\notin\{i_{1},i_{2},\cdots i_{r}\}\\
f_{i}(T)-\alpha\tilde{\lambda}_{i}(t-T)\quad if\quad i\in\{i_{1},i_{2},\cdots i_{r}\},\end{cases}t\in[T,T+1/2],$
$g_{i}(t)=\begin{cases}g_{i}(T)+\alpha\mu^{*}_{i}(t-T)=\alpha\mu^{*}_{i}(t-T)\quad if\quad i\notin\{j_{1},j_{2},\cdots j_{s}\}\\
g_{i}(T)+\alpha\mu^{*}_{i}(t-T)-\alpha\tilde{\mu}_{i}(t-T)\quad if\quad i\notin\{j_{1},j_{2},\cdots j_{s}\},\end{cases}t\in[T,T+1/2].$
Here, $\alpha=2\min\{\min_{\tilde{\lambda}_{i_{w}}>0}f_{i_{w}}(T)/\tilde{\lambda}_{i_{w}},\min_{\tilde{\mu}_{j_{w}}>\mu^{*}_{j_{w}}}g_{j_{w}}(T)/(\tilde{\mu}_{j_{w}}-\mu^{*}_{j_{w}})\}>0$.
Update $\mathcal{C}$ so that $f_{i}(T+1/2)>0\Leftrightarrow a_{i}\in\mathcal{C}$, $g_{i}(T+1/2)>0\Leftrightarrow b_{i}\in\mathcal{C}$.
- •
(Update 2: Pruning) After this, we initialize $r=0$, $s_{i}(0)=f_{i}(T+1/2),i\in[m],z_{j}(0)=g_{j}(T+1/2),j\in[k]$ and repeat:
(Check) If $\mathcal{C}$ is linearly independent, break
(Update) Say $\mathcal{C}=\{a_{r1},a_{r2},\cdots a_{rx}\}\cup\{b_{s1},b_{s2},\cdots b_{sy}\}$. Find a nontrivial linear combination
$\sum_{w=1}^{x}\eta_{w}a_{rw}+\sum_{w=1}^{y}\eta^{\prime}_{w}b_{sw}=0,$
and without loss of generality suppose $\sum_{w=1}^{x}\eta_{w}\geq 0$. If $\sum_{w=1}^{x}\eta_{w}=0$, choose $\eta^{\prime}_{w}$ to find at least one $\eta^{\prime}_{w}>0$ for $w\in[y]$. Then, write
$s_{rw}(r+t)=s_{rw}(r)-\alpha\eta_{w}t,\quad z_{sw}(r+t)=z_{sw}(r)-\alpha\eta^{\prime}_{w}t$
for $t\in[0,1]$. Here $\alpha=\min\{\min_{\eta_{w}>0}s_{rw}(r)/\eta_{w},\min_{\eta^{\prime}_{w}>0}z_{rw}(r)/\eta^{\prime}_{w}\}$.
At last, update $\mathcal{C}$ so that $s_{i}(r+1)>0\Leftrightarrow a_{i}\in\mathcal{C}$, $z_{i}(r+1)>0\Leftrightarrow b_{i}\in\mathcal{C}$. Increase $r$ by 1.
- •
(Construct $f_{i},g_{j}$ for $t\in[T+1/2,T+1]$) Concatente $f_{i}$ and $s_{i}$, $g_{j}$ and $z_{j}$ for all $i\in[m]$, $j\in[k]$.

Step 2) Let the termination time be $T^{*}$. To obtain $F_{i},G_{j}:[0,1]\rightarrow\mathbb{R}$, simply write $F_{i}(t)=f_{i}(T/T^{*}),G_{j}(t)=g_{j}(T/T^{*})$.

Let’s first verify that the facts that hold from the previous iteration. First, $\mathcal{C}$ is a linearly independent set at the start of each iterate because of step (Update 2: Pruning), and the first fact holds. Also, $f_{i},g_{j}$ are updated only in steps (Update1) and (Update 2: Pruning), and we can see that for all $t\in[0,T^{*}]$ the function values are nonnegative. In update 1, we chose $\alpha$ sufficiently small and $\mu^{*}\geq 0$. In update 2, we also chose $\alpha$ sufficiently small. Hence, the second fact holds. At every update, we also update $\mathcal{C}$, and the third fact holds. At last, we add a nontrivial linear combination of $\mathcal{A}\cup\mathcal{B}$ that sums up to 0 at each update, so the sum

$$ $\sum_{i=1}^{m}f_{i}(t)a_{i}+\sum_{j=1}^{k}g_{j}(t)b_{j},$ $$

is preserved to be $y^{*}$, which means that the last fact follows.

One important argument to make is that the algorithm actually terminates, i.e. $T^{*}<\infty$. The iteration in the second update terminates eventually, because at each iteration the cardinality of $\mathcal{C}$ decreases by 1. To see the larger loop terminating, observe that

$$ $\sum_{i=1}^{m}f_{i}(t)$ $$

is a strictly decreasing function for $t\in\mathbb{N}$. This is because in (Update 1), as $\sum_{w=1}^{r}\tilde{\lambda}_{i_{w}}>0$, the sum decreases, and in (Update 2), the sum does not increase because we suppose $\sum_{w=1}^{x}\eta_{w}\geq 0$. This means that at each starting step of the algorithm, identical $\mathcal{C}$ cannot appear twice: as $\mathcal{C}$ is linearly independent there exists a unique expression that gives

$$ $\sum_{w=1}^{r}f_{i_{w}}(T)a_{i_{w}}+\sum_{w=1}^{s}g_{j_{w}}(T)b_{j_{w}}=y^{*},$ $$

and if identical $\mathcal{C}$ appeared twice we will have the same value of $\sum_{w=1}^{r}f_{i_{w}}(T)=\sum_{i=1}^{m}f_{i}(t)$, which is contradicting the fact that $\sum_{i=1}^{m}f_{i}(t)$ strictly decreases.

Finally, let’s check that we have found the right $F_{i},G_{j}$s. As the algorithm terminated, $\mathcal{C}\subseteq\mathcal{B}$, and we know that $F_{i}(1)=0$ for all $i\in[m]$. Also, as

$$ $\sum_{j=1}^{k}G_{j}(1)b_{j}=y^{*},$ $$

and the set $\mathcal{B}$ is linearly independent, we know that $G_{j}(1)=\mu_{j}$ for all $j\in[k]$. As previously mentioned, Property 3) is guaranteed as we are adding a nontrivial linear combination that sums up to 0 at each update. To see that Property 4) is true, we see the value of $\sum_{i=1}^{m}1(F_{i}(t)>0)+\sum_{j=1}^{k}1(G_{j}(t)>0)$ for each update. In (Update 1), as $\lVert\mu^{*}\rVert\leq n+1-t-s$, the total cardinality does not exceed $n+1$. In (Update 2), the cardinality always decreases. Hence, $\sum_{i=1}^{m}1(F_{i}(t)>0)+\sum_{j=1}^{k}1(G_{j}(t)>0)\leq n+1$ for all $t\in[0,1]$, and we know that we have actually found the wanted functions. This finishes the proof.
∎

At last, from [E.5](#A5.Thmappxproposition5), we know that $\mathcal{P}^{*}(m)$ is connected when $m\geq\min\{n+1,m^{*}+M^{*}\}$.

###### Proposition E.5 .

Suppose $\mathcal{P}^{*}(m^{\prime})$ is connected and $m^{\prime}\geq M^{*}$. Then $\mathcal{P}^{*}(m)$ is connected for all $m\geq m^{\prime}$.

###### Proof.

Take two points $A,B$ from $\mathcal{P}^{*}(m)$. We know that there exists a path from $A$ to $A_{irr}$, $B$ to $B_{irr}$ that satisfies $A_{irr},B_{irr}\in\mathcal{P}^{*}(m)\cap\mathcal{P}^{*}_{irr}$. Notice that as $A_{irr},B_{irr}\in\mathcal{P}^{*}_{irr}$, there cardinality is at most $M^{*}$. Hence they are elements of $\mathcal{P}^{*}(m^{\prime})$, which finishes the proof as $\mathcal{P}^{*}(m^{\prime})$ is connected.
∎

Now we connect the connectivity results of $\mathcal{P}^{*}(m)$ to that of $\Theta^{*}(m)$, the solution set of the original problem in ([1](#S2.E1)). We first define essential sets and mappings to do this.

###### Definition E.5 .

(Minimal Optimal Neural Networks) We say a parameter $(w_{j},\alpha_{j})_{j=1}^{m}$ is minimal optimal if $(w_{j},\alpha_{j})_{j=1}^{m}\in\Theta^{*}(m)$ and $\alpha_{p}\alpha_{q}>0$ implies $1(Xw_{p}\geq 0)\neq 1(Xw_{q}\geq 0)$ for all $p\neq q\in[m]$. We denote the set of minimal optimal neural networks as $\Theta^{*}_{\mathrm{min}}(m)$.

Adapting the proof from [], we can show that for any point $A\in\Theta^{*}(m)$, there is a continuous path from $A$ to a point in $\Theta^{*}_{\mathrm{min}}(m)$. The path is essentially merging the neurons with same arrangement patterns and second layer sign.

###### Proposition E.6 .

Take any point $A\in\Theta^{*}(m)$. We have a continuous path from $A$ to some point $A_{\mathrm{min}}\in\Theta^{*}_{\mathrm{min}}(m)$ in $\Theta^{*}(m)$.

###### Proof.

Write $A=(w_{j},\alpha_{j})_{j=1}^{m}$. Assume we have $(w_{1},\alpha_{1})$ and $(w_{2},\alpha_{2})$ that satisfies $\alpha_{1}\alpha_{2}>0$ and $1(Xw_{1}\geq 0)=1(Xw_{2}\geq 0)$. Let’s write $\mathrm{sign}(\alpha_{1})=\mathrm{sign}(\alpha_{2})=s$. Define the curve

$$ $\displaystyle C(t)=(\frac{w_{1}\alpha_{1}+tw_{2}\alpha_{2}}{\sqrt{\lVert w_{1}\alpha_{1}+tw_{2}\alpha_{2}\rVert_{2}}},$ $\displaystyle\sqrt{\lVert w_{1}\alpha_{1}+tw_{2}\alpha_{2}\rVert_{2}}s)$ $\displaystyle\oplus\ (\sqrt{1-t}\frac{w_{2}\alpha_{2}}{\sqrt{\lVert w_{2}\alpha_{2}\rVert_{2}}},\sqrt{(1-t)\lVert w_{2}\alpha_{2}\rVert_{2}}s)\ \oplus\ (w_{j},\alpha_{j})_{j=3}^{m},$ $$

where $t\in[0,1]$. The intuition of this curve is merging two pair $(w_{1},\alpha_{1})$ and $(w_{2},\alpha_{2})$.
Let’s check some basic facts to see that this curve indeed merges the two pairs and is in $\Theta^{*}(m)$.
i) $C(t)$ is well-defined. First, we know $\lVert w_{2}\alpha_{2}\rVert_{2}\neq 0$, because $\alpha_{2}\neq 0$. Also, say $w_{1}\alpha_{1}+(1-t)w_{2}\alpha_{2}=0$ for some $t\in[0,1]$. Then we have $DXw_{1}\alpha_{1}=-(1-t)DXw_{2}\alpha_{2}$, where $D=\mathrm{diag}(1(Xw_{1}\geq 0))$. As $DXw_{1}$ and $DXw_{2}$ is consisted of nonnegative entries and $\alpha_{1}\alpha_{2}>0$, $DXw_{1}\alpha_{1}=0$ must hold. This means $w_{1}=\alpha_{1}=0$ because $A\in\Theta^{*}(m)$ - which is again contradiction because $\alpha_{1}\neq 0$. The well-definedness of $C(t)$ implies that it is continuous, because it is a composition of continuous functions.
ii) $C(0)=A$, $C(1)=(\frac{w_{1}\alpha_{1}+w_{2}\alpha_{2}}{\sqrt{\lVert w_{1}\alpha_{1}+w_{2}\alpha_{2}\rVert_{2}}},\sqrt{\lVert w_{1}\alpha_{1}+w_{2}\alpha_{2}\rVert_{2}}s)\ \oplus\ (0,0)\ \oplus\ (w_{j},\alpha_{j})_{j=3}^{m}$ from direct substitution. Note that the value $\sum_{i=1}^{m}1(\alpha_{i}\neq 0)$ decreased by 1.
iii) $C(t)$ is a curve in $\Theta^{*}(m)$. This is because the sum $\sum_{i=1}^{m}(Xw_{i})_{+}\alpha_{i}$ is preserved through the curve, and the regularization loss is less than that of $A$ due to triangular inequality. In other words, the loss $L(C(t))\leq L(C(0))$ for all $t\in[0,1]$, and as $L(C(0))$ is optimal, $C(t)$ is a curve in $\Theta^{*}(m)$.

We repeat the merging process until there is no such pair. This process should terminate because each merging decreases $\sum_{i=1}^{m}1(\alpha_{i}\neq 0)$ by 1. After we don’t have such pair, concatenate all the curves that we have to find a curve in $\Theta^{*}(m)$. At the end of the path, we don’t have two $(w_{i},\alpha_{i})$, $(w_{j},\alpha_{j})$ that satisfy $\alpha_{i}\alpha_{j}>0$ and $1(Xw_{i}\geq 0)=1(Xw_{j}\geq 0)$, hence it is in $\Theta^{*}_{\mathrm{min}}(m)$.
∎

Also, we define the notion of a canonical polytope. A canonical polytope is defined to break ties that occur because two cones $\mathcal{K}_{i}$ and $\mathcal{K}_{j}$ may have nonempty intersections. For instance, say $D_{1}Xu_{1}=D_{2}Xu_{1}$ and $u_{2}=0$ for some $(u_{i},v_{i})_{i=1}^{P}\in\mathcal{P}^{*}$. Then, swapping $(u_{1},v_{1})$ and $(u_{2},v_{2})$ will not change the solution’s optimality. As we will see later on, we will want to erase such ambiguity, hence we consider a canonical polytope.

###### Definition E.6 .

(Canonical Polytope) The canonical polytope is defined as

$$ $\displaystyle\mathcal{P}^{*}_{\mathrm{can}}=\Big{\{}(u_{i},v_{i})_{i=1}^{P}\ |\ (u_{i},v_{i})_{i=1}^{P}\in\mathcal{P}^{*},diag(1(Xu_{i}\geq 0))=$ $\displaystyle D_{i}\ if\ u_{i}\neq 0,$ $\displaystyle diag(1(Xv_{i}\geq 0))=D_{i}\ if\ v_{i}\neq 0\Big{\}}.$ $$

###### Remark E.2 .

$\mathrm{diag}(1(Xu\geq 0))=D_{i}$ implies $(2D_{i}-I)Xu\geq 0$, but not the opposite. The ambiguity happens because $x_{j}\cdot u$ might be 0 for some rows.

Given the notion of the minimal optimal neural network and the canonical polytope, we define two natural mappings $\Psi:\mathcal{P}^{*}(m)\rightarrow\Theta^{*}(m)$ and $\Phi:\Theta^{*}(m)\rightarrow\mathcal{P}^{*}(m)$. These mappings have been discussed multiple times in the literature [], [], and we introduce it again with slight variations for our needs.

###### Definition E.7 .

Suppose $m\geq m^{*}$. We define $\Psi:\mathcal{P}^{*}(m)\rightarrow\Theta^{*}(m)$ as

$$ $\Psi((u_{i},v_{i})_{i=1}^{P}):=(\frac{u_{i}}{\sqrt{\lVert u_{i}\rVert_{2}}},\sqrt{\lVert u_{i}\rVert_{2}})_{u_{i}\neq 0}\oplus(\frac{v_{i}}{\sqrt{\lVert v_{i}\rVert_{2}}},-\sqrt{\lVert v_{i}\rVert_{2}})_{v_{i}\neq 0}\oplus(0,0)^{m-\mathrm{card}((u_{i},v_{i})_{i=1}^{P})},$ $$

###### Definition E.8 .

Suppose $m\geq m^{*}$. We define $\Phi:\Theta^{*}(m)\rightarrow\mathcal{P}^{*}(m)$ as

$$ $\Phi((w_{i},\alpha_{i})_{i=1}^{m})=(u_{i},v_{i})_{i=1}^{P}:=\begin{cases}u_{p}=\sum_{i\in\mathcal{I}}w_{i}|\alpha_{i}|\ where\ \mathcal{I}=\{i\ |\ \alpha_{i}>0,D_{p}=1(Xw_{i}\geq 0)\}\\ v_{q}=\sum_{i\in\mathcal{I}}w_{i}|\alpha_{i}|\ where\ \mathcal{I}=\{i\ |\ \alpha_{i}<0,D_{q}=1(Xw_{i}\geq 0)\}.\end{cases}$ $$

The mappings are indeed well-defined [E.7](#A5.Thmappxproposition7).

###### Proposition E.7 .

Suppose $m\geq m^{*}$. $\Psi:\mathcal{P}^{*}(m)\rightarrow\Theta^{*}(m)$ and $\Phi:\Theta^{*}(m)\rightarrow\mathcal{P}^{*}(m)$ are well defined.

###### Proof.

By well-defined, we want to see that for all $A\in\mathcal{P}^{*}(m)$, $\Psi(A)\in\Theta^{*}(m)$ and has a unique value, and similarly for $\Phi$ too.
From [E.7](#A5.Thmappxdefinition7) and [E.8](#A5.Thmappxdefinition8), it is not hard to see that the function value is uniquely determined for each input. Also, from direct calculation, we can see that

$$ $L\left(\sum_{j=1}^{m}(Xw_{j})_{+}\alpha_{j},y\right)+\frac{\beta}{2}\sum_{j=1}^{m}\left(\lVert w_{j}\rVert_{2}^{2}+\alpha_{j}^{2}\right)=L\left(\sum_{i=1}^{P}D_{i}X(u_{i}-v_{i}),y\right)+\beta\sum_{i=1}^{P}\left(\lVert u_{i}\rVert_{2}+\lVert v_{i}\rVert_{2}\right),$ $$

for both $A=(u_{i},v_{i})_{i=1}^{P}$ and $\Psi(A)=(w_{j},\alpha_{j})_{j=1}^{m}$ and when $A=(w_{j},\alpha_{j})_{j=1}^{m}$ and $\Phi(A)=(u_{i},v_{i})_{i=1}^{P}$. As $m\geq m^{*}$ the optimization problems in ([1](#S2.E1)) and ([2](#S2.E2)) have same optimal values, which means $\Psi(A)\in\Theta^{*}(m)$ and $\Phi(A)\in\mathcal{P}^{*}(m)$.
∎

Moreover, we can see that the two mappings are similar to inverses of each other.

###### Proposition E.8 .

Take any $A\in\mathcal{P}^{*}_{\mathrm{can}}\cap\mathcal{P}^{*}(m)$. Then, $\Phi(\Psi(A))=A$. Also, take any $B=(w_{j},\alpha_{j})_{j=1}^{m}\in\Theta^{*}_{\mathrm{min}}(m)$. Then, $\Psi(\Phi(B))=(w_{\sigma(j)},\alpha_{\sigma(j)})_{j=1}^{m}$ a permutation of $B$.

###### Proof.

We know

$$ $\Psi((u_{i},v_{i})_{i=1}^{P}):=(\frac{u_{i}}{\sqrt{\lVert u_{i}\rVert_{2}}},\sqrt{\lVert u_{i}\rVert_{2}})_{u_{i}\neq 0}\oplus(\frac{v_{i}}{\sqrt{\lVert v_{i}\rVert_{2}}},-\sqrt{\lVert v_{i}\rVert_{2}})_{v_{i}\neq 0}\oplus(0,0)^{m-\mathrm{card}((u_{i},v_{i})_{i=1}^{P})}.$ $$

Write $\Phi(\Psi((u_{i},v_{i})_{i=1}^{P}))=(u_{i}^{\prime},v_{i}^{\prime})_{i=1}^{P}$. Let
s see that $u_{i}^{\prime}=u_{i}$ for all $i\in[P]$. The case of $v$ will follow similarly.
The first case is when $u_{i}=0$. Say there exists $u_{j}\neq 0$ and $1(Xu_{j}\geq 0)=D_{i}$. As $(u_{i},v_{i})_{i=1}^{P}\in\mathcal{P}^{*}_{can}$, $1(Xu_{j}\geq 0)=D_{j}=D_{i}$, meaning $i=j$. This is a contradiction because $u_{i}=0$. This means there is no $u_{j}\neq 0$ that is $1(Xu_{j}\geq 0)=D_{i}$, and there is no $u_{j}\neq 0$ that is $1(Xu_{j}/\sqrt{\lVert u_{j}\rVert_{2}}\geq 0)=D_{i}$, meaning $u_{i}^{\prime}=0$.
The next case is when $u_{i}\neq 0$. For $u_{j}\neq 0$ such that $1(Xu_{j}\geq 0)=D_{i}$, the only possible $j=i$. For that $j$, we know that $1(Xu_{i}/\sqrt{\lVert u_{i}\rVert_{2}}\geq 0)=D_{i}$, and $u_{i}^{\prime}=u_{i}/\sqrt{\lVert u_{i}\rVert_{2}}\times\sqrt{\lVert u_{i}\rVert_{2}}=u_{i}$. This means $u_{i}^{\prime}=u_{i}$ for all $i\in[P]$, same for $v$, meaning $\Phi(\Psi((u_{i},v_{i})_{i=1}^{P}))=(u_{i},v_{i})_{i=1}^{P}$.
Let’s see $\Psi\circ\Phi$. We know

$$ $\Phi((w_{i},\alpha_{i})_{i=1}^{m})=(u_{i},v_{i})_{i=1}^{P}:=\begin{cases}u_{p}=w_{i}|\alpha_{i}|\ \ if\ \alpha_{i}>0\ and\ D_{p}=1(Xw_{i}\geq 0),\ \ 0\ \ otherwise\\ v_{q}=w_{i}|\alpha_{i}|\ \ if\ \alpha_{i}<0\ and\ D_{q}=1(Xw_{i}\geq 0),\ \ 0\ \ otherwise,\end{cases}$ $$

because $(w_{i},\alpha_{i})_{i=1}^{m}$ is minimal. Let’s say $\sum_{i=1}^{m}1(\alpha_{i}>0)=m_{p}$, $\sum_{i=1}^{m}1(\alpha_{i}=0)=m_{z}$, $\sum_{i=1}^{m}1(\alpha_{i}<0)=m_{n}$. In $\{u_{1},u_{2},\cdots u_{P}\}$, there will be $m_{p}$ nonzero vectors. Index them as $u_{a_{1}},u_{a_{2}},\cdots u_{a_{m_{p}}}$. For $u_{a_{i}},$ we can find $j_{i}\in[m]$ that satisfies $u_{a_{i}}=w_{j_{i}}|\alpha_{j_{i}}|$. Furthermore, $j_{i_{1}}\neq j_{i_{2}}$ if $i_{1}\neq i_{2}$ because $j_{i_{1}}=j_{i_{2}}$ means $D_{a_{i_{1}}}=D_{a_{i_{2}}}$ and $a_{i_{1}}=a_{i_{2}}$, $i_{1}=i_{2}$. Similarly, define $v_{b_{1}},v_{b_{2}},\cdots v_{b_{m_{n}}}$ and $v_{b_{i}}=w_{k_{i}}|\alpha_{k_{i}}|$. Then,

$$ $\Psi(\Phi((w_{i},\alpha_{i})_{i=1}^{m}))=\left(\frac{w_{j_{i}}|\alpha_{j_{i}}|}{\sqrt{w_{j_{i}}|\alpha_{j_{i}}|}},\sqrt{w_{j_{i}}|\alpha_{j_{i}}|}\right)_{i=1}^{m_{p}}\oplus\ \left(\frac{w_{k_{i}}|\alpha_{k_{i}}|}{\sqrt{w_{k_{i}}|\alpha_{k_{i}}|}},-\sqrt{w_{k_{i}}|\alpha_{k_{i}}|}\right)_{i=1}^{m_{n}}\oplus\ (0,0)^{m_{z}}.$ $$

First, we know that $\lVert w_{j}\rVert_{2}=|\alpha_{j}|$ for all $j\in[m]$. This leads to

$$ $\Psi(\Phi((w_{i},\alpha_{i})_{i=1}^{m}))=\left(w_{j_{i}},|\alpha_{j_{i}}|\right)_{i=1}^{m_{p}}\oplus\ \left(w_{k_{i}},-|\alpha_{k_{i}}|\right)_{i=1}^{m_{n}}\oplus\ (0,0)^{m_{z}}.$ $$

As $j_{i_{1}}\neq j_{i_{2}}$ if $i_{1}\neq i_{2}$, the result is a permutation of $(w_{i},\alpha_{i})_{i=1}^{m}$.
∎

At last, for these mappings to be meaningful, we would want them to be continuous. Luckily, $\Phi$ is continuous [E.9](#A5.Thmappxproposition9).

###### Proposition E.9 .

The map $\Phi:\Theta^{*}(m)\rightarrow\mathcal{P}^{*}(m)$ is continuous.

###### Proof.

We consider the sequence $(w^{k}_{j},\alpha^{k}_{j})_{j=1}^{m}$ in $\Theta^{*}(m)$ that converges to $(w^{\infty}_{j},\alpha^{\infty}_{j})_{j=1}^{m}\in\Theta^{*}(m)$. Let’s write

$$ $\Phi((w^{k}_{j},\alpha^{k}_{j})_{j=1}^{m})=(u^{k}_{i},v^{k}_{i})_{i=1}^{P},\quad\Phi((w^{\infty}_{j},\alpha^{\infty}_{j})_{j=1}^{m})=(u^{\infty}_{i},v^{\infty}_{i})_{i=1}^{P}.$ $$

We will show that $u_{i}^{k}\rightarrow u_{i}^{\infty}$. The rest will follow.
As a starting point, we define some necessary constants. We define $M_{j}$ for $j\in[m]$ that satisfy $w_{j}^{\infty}\neq 0$ as the following:
if $k\geq M_{j}$, $1(Xw_{j}^{\infty}\geq 0)=1(Xw_{j}^{k}\geq 0)$ and $\alpha_{j}^{k}\alpha_{j}^{\infty}>0$. Such $M_{j}$ exists due to the following reasoning: we know that for any solution $A\in\Theta^{*}(m)$, there exists a finite set of possible directions for $w_{j}$, which are the directions of $\bar{u}_{i},\bar{v}_{i}$ in $\mathcal{P}^{*}$. As $w_{j}^{\infty}\neq 0$ and $w_{j}^{k}\rightarrow w_{j}^{\infty}$, for sufficiently large $k$ so that $\lVert w_{j}^{k}-w_{j}^{\infty}\rVert_{2}$ is sufficiently small, $w_{j}^{\infty}$ has to be a positive scaling of $w_{j}^{k}$. Also $w_{j}^{\infty}\neq 0$ implies $\alpha_{j}^{\infty}\neq 0$, meaning for sufficiently large $k$, $\alpha_{j}^{k}\alpha_{j}^{\infty}>0$ holds. For $j\in[m]$ that has $w_{j}^{\infty}=0$, define $N_{j}(\epsilon)$ to be the number that satisfies $k\geq N_{j}(\epsilon)$ implies $\lVert w_{j}^{k}\alpha_{j}^{k}\rVert_{2}\leq\epsilon$.

Now we prove that for sufficiently large $k$, $\lVert u_{i}^{k}-u_{i}^{\infty}\rVert_{2}\leq\epsilon$ for all $i\in[P]$. For a certain $i\in[P]$, suppose there exists $\{j_{1},j_{2},\cdots j_{t}\}\subseteq[m]$ that satisfies $D_{i}=1(Xw_{j_{1}}^{\infty}\geq 0)=\cdots=1(Xw_{j_{t}}^{\infty}\geq 0)$ and $\alpha_{j_{1}}^{\infty},\cdots,\alpha_{j_{t}}^{\infty}>0$ (hence $w_{j_{1}}^{\infty},\cdots,w_{j_{t}}^{\infty}\neq 0$). It is clear that $u_{i}^{\infty}=\sum_{i=1}^{t}w_{j_{i}}^{\infty}\alpha_{j_{i}}^{\infty}$. When $k\geq\max\{\max_{w_{j}^{\infty}=0}N_{j}(\epsilon/m),\max_{w_{j}^{\infty}\neq 0}M_{j}\}$, we know that $1(Xw_{j_{i}}^{k}\geq 0)=1(Xw_{j_{i}}^{\infty}\geq 0)$ and $\alpha_{j_{i}}^{k}>0$ for $i\in[t]$. Also, for some $j\in[m]$ which is not in $\{j_{1},j_{2},\cdots,j_{t}\}$, $w_{j}^{\infty}=0$. Hence,

$$ $u_{i}^{k}=\sum_{i=1}^{t}w_{j_{i}}^{k}\alpha_{j_{i}}^{k}+\sum_{w_{j}^{\infty}=0,D_{i}=1(Xw_{j}^{k}\geq 0),\alpha_{j}^{k}>0}w_{j}^{k}\alpha_{j}^{k}.$ $$

$u_{i}^{k}\rightarrow u_{i}^{\infty}$, as $w_{j_{i}}^{k}\rightarrow w_{j_{i}}^{\infty},\alpha_{j_{i}}^{k}\rightarrow\alpha_{j_{i}}^{\infty}$ for $i\in[t]$ and the rest sum becomes smaller than $\epsilon$, hence converging to 0 as $k\rightarrow\infty$.

Finally, let’s see the case where there is no $j\in[m]$ that satisfies $D_{i}=1(Xw_{j}^{\infty}\geq 0)$ and $\alpha_{j}^{\infty}>0$. Here, $u_{i}^{\infty}=0$. Now take $k\geq\max\{\max_{w_{j}^{\infty}=0}N_{j}(\epsilon/m),\max_{w_{j}^{\infty}\neq 0}M_{j}\}$. One thing to notice is for this $k$, if $D_{i}=1(Xw_{j}^{k}\geq 0)$ and $\alpha_{j}^{k}>0$ for some $j\in[m]$, $w_{j}^{\infty}=0$. Suppose $w_{j}^{\infty}\neq 0$. As $k\geq M_{j}$, we know that $D_{i}=1(Xw_{j}^{\infty}\geq 0)$ and $\alpha_{j}^{\infty}>0$, which contradicts the assumption that there is no such $j$. Hence, when we write

$$ $u_{i}^{k}=\sum_{w_{j}^{\infty}=0,D_{i}=1(Xw_{j}^{k}\geq 0),\alpha_{j}^{k}>0}w_{j}^{k}\alpha_{j}^{k},$ $$

as $k\geq N_{j}(\epsilon/m)$, $\lVert u_{i}^{k}\rVert_{2}\leq\epsilon$. As $u_{i}^{\infty}=0$, we have that $u_{i}^{k}\rightarrow u_{i}^{\infty}$. This finishes the proof.
∎

However, $\Psi$ may not be continuous. The intuition is that the solutions in the image of $\Psi$ have zeros at the end, whereas the limit of $\Psi((u_{i},v_{i})_{i=1}^{P})$ as $u_{i}\rightarrow 0$ may have zeros at the middle. Thus we have a slightly weaker notion of continuity for $\Psi$ [E.10](#A5.Thmappxproposition10).

###### Proposition E.10 .

Consider a continuous path $(u_{i}(t),v_{i}(t))_{i=1}^{P}$ in $\mathcal{P}^{*}(m)$, where $u_{i}(t),v_{i}(t):[0,1]\rightarrow\mathbb{R}^{d}$ is either a zero map or a map can only have zero when $t=1$. Consider the path $\phi(t)=\Psi((u_{i}(t),v_{i}(t))_{i=1}^{P})$ in $\Theta^{*}(m)$. Then, $\phi(t)$ is continuous in $[0,1)$, and $\lim_{t\rightarrow 1}\phi(t)$ is a permutation of $\phi(1)$.

###### Proof.

Let’s write what $\phi(t)$ looks like. Write $i_{1}<i_{2}<\cdots i_{p}$ the indices where $u_{i}(0)\neq 0$, and write $j_{1}<j_{2}<\cdots<j_{q}$ the indices where $v_{i}(0)\neq 0$. Denote the indices $\mathcal{I},\mathcal{J}$. For $t\in[0,1)$, $\phi(t)$ is

$$ $\phi(t)=\left(\frac{u_{i}(t)}{\sqrt{\lVert u_{i}(t)\rVert_{2}}},\sqrt{\lVert u_{i}(t)\rVert_{2}}\right)_{i\in\mathcal{I}}\oplus\left(\frac{v_{i}(t)}{\sqrt{\lVert v_{i}(t)\rVert_{2}}},-\sqrt{\lVert v_{i}(t)\rVert_{2}}\right)_{i\in\mathcal{J}}\oplus(0,0)^{m-p-q}.$ $$

As $\mathcal{I},\mathcal{J}$ is fixed for $t\in[0,1)$ and $u_{i}(t)\neq 0$ if $u_{i}(0)\neq 0$, $v_{i}(t)\neq 0$ if $v_{i}(0)\neq 0$, $\phi$ is continuous for [0,1). When $t=1$, $\lim_{t\rightarrow 1}\phi(t)$ may have zeros in the middle, whereas $\phi(1)$ has zeros at the end, and the rest is the same. Hence, $\lim_{t\rightarrow 1}\phi(t)$ is a permutation of $\phi(1)$.
∎

Given the machinery, we are ready to elaborate the results. We start with proving that if $m$ is sufficiently large, all permutations of a point $A\in\Theta^{*}(m)$ are connected. The proof strategy is analogous to the proof in [], where we create an empty slot to permute the weights.

###### Proposition E.11 .

Suppose $m\geq M^{*}+1$. Take any $(w_{j},\alpha_{j})_{j=1}^{m}\in\Theta^{*}(m)$. There exists a continuous path from $(w_{j},\alpha_{j})_{j=1}^{m}$ to an arbitrary permutation $(w_{\sigma(j)},\alpha_{\sigma(j)})_{j=1}^{m}$.

###### Proof.

Our proof will start from showing that for any $A=(w_{j},\alpha_{j})_{j=1}^{m}\in\Theta^{*}(m)$, we can find a continuous path $A^{\prime}=(w_{j}^{\prime},\alpha_{j}^{\prime})_{j=1}^{m}\in\Theta^{*}(m)$ that satisfies $\sum_{j=1}^{m}1(\alpha_{j}^{\prime}\neq 0)<m$. First, use [E.6](#A5.Thmappxproposition6) to find a continuous path from $A$ to some $A_{\mathrm{min}}=(w_{j}^{\circ},\alpha_{j}^{\circ})\in\Theta^{*}_{\mathrm{min}}(m)$. If $\sum_{j=1}^{m}1(\alpha_{j}^{\circ}\neq 0)<m$, we have found such path.
If not, let’s show that $\{(Xw_{j}^{\circ})_{+}\}_{j=1}^{m}$ is linearly dependent. As all $\alpha_{j}^{\circ}\neq 0$, all $w_{j}^{\circ}\neq 0$. Now think of $\Phi(A_{\mathrm{min}})=(u_{i},v_{i})_{i=1}^{P}$. We can easily see that

$$ $\{(Xw_{j}^{\circ})_{+}\alpha_{j}^{\circ}\}_{j=1}^{m}=\{D_{i}Xu_{i}\}_{u_{i}\neq 0}\cup\{-D_{i}Xv_{i}\}_{v_{i}\neq 0}.$ $$

As the latter set has $m>M^{*}$ elements, it should be linearly dependent. If not, it is a contradiction to the fact that the maximal cardinality of the element in $\mathcal{P}^{*}_{\mathrm{irr}}$ is $M^{*}$. Hence, the set $\{(Xw_{j}^{\circ})_{+}\alpha_{j}^{\circ}\}_{j=1}^{m}$ is linearly dependent, and as all $\alpha_{j}^{\circ}$ is nonzero, the set $\{(Xw_{j}^{\circ})_{+}\}_{j=1}^{m}$ is linearly dependent.
Now consider a nontrivial linear combination,

$$ $\sum_{i=1}^{m}c_{i}(Xw_{i}^{\circ})_{+}=0.$ $$

Without loss of generality say $\alpha_{1}^{\circ}c_{1}<0$. Define

$$ $t_{m}=\min_{\alpha_{i}^{\circ}c_{i}<0}-\frac{\alpha_{i}^{\circ}}{c_{i}},$ $$

and for $t\in[0,t_{m}]$ define

$$ $\tilde{w}_{i}(t)=w_{i}^{\circ}\sqrt{\frac{|\alpha_{i}^{\circ}+tc_{i}|}{\lVert w_{i}^{\circ}\rVert_{2}}},\quad\tilde{\alpha}_{i}(t)=\sqrt{\lVert w_{i}^{\circ}\rVert_{2}|\alpha_{i}^{\circ}+tc_{i}|}\ sign(\alpha_{i}^{\circ}).$ $$

From the definition of $t_{m}$, $sign(\alpha_{i}^{\circ}+tc_{i})=sign(\alpha_{i}^{\circ})$ for $t\in[0,t_{m}]$. Also,

$$ $\sum_{i=1}^{m}(X\tilde{w}_{i}(t))_{+}\tilde{\alpha}_{i}(t)=\sum_{i=1}^{m}(Xw_{i}^{\circ})_{+}(\alpha_{i}^{\circ}+tc_{i})=\sum_{i=1}^{m}(Xw_{i}^{\circ})_{+}\alpha_{i}^{\circ},$ $$

and

$$ $\frac{1}{2}\sum_{i=1}^{m}\lVert\tilde{w}_{i}(t)\rVert_{2}^{2}+|\tilde{\alpha}_{i}(t)|^{2}=\sum_{i=1}^{m}\lVert\tilde{w}_{i}(t)\rVert_{2}|\tilde{\alpha}_{i}(t)|=\sum_{i=1}^{m}\lVert w_{i}^{\circ}\rVert_{2}|\alpha_{i}^{\circ}|+\lVert w_{i}^{\circ}\rVert_{2}tc_{i}sign(\alpha_{i}^{\circ}).$ $$

At last, we know that for the dual optimum $\nu^{*}$ defined in [Theorem 1](#Thmtheorem1),

$$ $(\nu^{*})^{T}(Xw_{j}^{\circ})_{+}=-\beta\lVert w_{j}^{\circ}\rVert_{2}sign(\alpha_{j}^{\circ}),$ $$

for all $j\in[m]$. This is obtained by using the fact that $\Phi(A_{\mathrm{min}})\in\mathcal{P}^{*}$. Hence, if $\sum_{i=1}^{m}c_{i}(Xw_{i}^{\circ})_{+}=0$, multiplying $(\nu^{*})^{T}$ on both sides leads

$$ $\sum_{i=1}^{m}\lVert w_{i}^{\circ}\rVert_{2}tc_{i}sign(\alpha_{i}^{\circ})=0,$ $$

and

$$ $\frac{1}{2}\sum_{i=1}^{m}\lVert\tilde{w}_{i}(t)\rVert_{2}^{2}+|\tilde{\alpha}_{i}(t)|^{2}=\sum_{i=1}^{m}\lVert w_{i}^{\circ}\rVert_{2}|\alpha_{i}^{\circ}|=\frac{1}{2}\sum_{i=1}^{m}\lVert w_{i}^{\circ}\rVert_{2}^{2}+|\alpha_{i}^{\circ}|^{2}.$ $$

Hence the objective is preserved throughout the curve, meaning the curve is in $\Theta^{*}(m)$. The cardinality decreased by at least 1 at the end due to the definition of $t_{m}$.
Now that we can find a continuous path from $A$ to $A^{\prime}=(w_{j}^{\prime},\alpha_{j}^{\prime})_{j=1}^{m}\in\Theta^{*}(m)$ where $\sum_{j=1}^{m}1(\alpha_{j}^{\prime}\neq 0)<m$, we will find a path from $A^{\prime}$ to any permutation of $A^{\prime}$, namely $(w_{\sigma(j)}^{\prime},\alpha_{\sigma(j)}^{\prime})_{j=1}^{m}$ for some permutation $\sigma:[m]\rightarrow[m]$. A simple path construction is as follows: we know that at least one $\alpha_{i}^{\prime}=0$. Let that $i=m$ without loss of generality. Starting from $i_{0}=1$, we do the following: if $w_{i_{0}}^{\prime}=w_{\sigma(i_{0})}^{\prime}$, we do nothing. If $w_{i_{0}}^{\prime}\neq w_{\sigma(i_{0})}^{\prime}$, we first write

$$ $w_{i_{0}}^{\prime}(t)=w_{i_{0}}^{\prime}\sqrt{1-t},\alpha_{i_{0}}(t)=\alpha_{i_{0}}^{\prime}\sqrt{1-t},w_{m}^{\prime}(t)=w_{i_{0}}^{\prime}\sqrt{t},\alpha_{m}^{\prime}(t)=\alpha_{i_{0}}^{\prime}\sqrt{t},$ $$

for $t\in[0,1]$, which intuitively ’moves’ $w_{i_{0}}^{\prime}$ to the empty space $w_{m}$ and making $w_{i_{0}}^{\prime}=0$. Next we move $w_{\sigma(i_{0})}^{\prime}$ to $w_{i}^{\prime}$ with

$$ $w_{i_{0}}^{\prime}(t)=w_{\sigma(i_{0})}^{\prime}\sqrt{t},\alpha_{i_{0}}(t)=\alpha_{\sigma(i_{0})}^{\prime}\sqrt{t},w_{\sigma(i_{0})}^{\prime}(t)=w_{\sigma(i_{0})}^{\prime}\sqrt{1-t},\alpha_{\sigma(i_{0})}^{\prime}(t)=\alpha_{\sigma(i_{0})}^{\prime}\sqrt{1-t},$ $$

for $t\in[0,1]$, which intuitively ’moves’ $w_{\sigma(i_{0})}^{\prime}$ to the empty space $w_{i_{0}}$ and making $w_{\sigma(i_{0})}=0$. At last, we make $w_{m}$ empty by using

$$ $w_{\sigma(i_{0})}^{\prime}(t)=w_{i_{0}}^{\prime}\sqrt{t},\alpha_{\sigma(i_{0})}(t)=\alpha_{i_{0}}^{\prime}\sqrt{t},w_{m}^{\prime}(t)=w_{i_{0}}^{\prime}\sqrt{1-t},\alpha_{m}^{\prime}(t)=\alpha_{i_{0}}^{\prime}\sqrt{1-t}.$ $$

To wrap up, we may swap the element in $(w_{i},\alpha_{i})$ and $(w_{\sigma(i)},\alpha_{\sigma(i)})$ by first moving $w_{i}$ to $w_{m}$, then moving $w_{\sigma}(i)$ to $w_{i}$, and at last moving $w_{m}$ to $w_{\sigma(i)}$.
Until here we connected $A=(w_{j},\alpha_{j})_{j=1}^{m}$ with $A^{\prime}$, and then $A^{\prime}$ with a permutation of $A^{\prime}$. To connect $A$ with $(w_{\sigma(j)},\alpha_{\sigma(j)})$, simply run the path $A\rightarrow A^{\prime}$ backwards to obtain $(w_{\sigma(j)},\alpha_{\sigma(j)})_{j=1}^{m}$.
∎

[E.11](#A5.Thmappxproposition11) enables us to connect two different permutations. Even though $\Psi$ is not essentially continuous, the fact that two permutations are connected will allow us to construct paths in $\Theta^{*}(m)$ from paths in $\mathcal{P}^{*}(m)$.

###### Proposition E.12 .

Suppose $m\geq M^{*}+1$. If any two points $A,B\in\mathcal{P}^{*}(m)$ are connected with a path with finite cardinality changes, $\Theta^{*}(m)$ is connected.

###### Proof.

Take two points $A,B\in\Theta^{*}(m)$. First use [E.6](#A5.Thmappxproposition6) to find path from $A$ to $A_{\mathrm{min}}\in\Theta^{*}_{\mathrm{min}}(m)$ and $B$ to $B_{\mathrm{min}}\in\Theta^{*}_{\mathrm{min}}(m)$. Our main goal will be connecting $A_{\mathrm{min}}$ and $B_{\mathrm{min}}$ by using the path from $\Phi(A_{\mathrm{min}})$ to $\Phi(B_{\mathrm{min}})$.
Consider the continuous path from $\Phi(A_{\mathrm{min}})$ to $\Phi(B_{\mathrm{min}})$, namely $f:[0,1]\rightarrow\mathcal{P}^{*}(m)$ satisfying $f(0)=\Phi(A_{\mathrm{min}})$, $f(1)=\Phi(B_{\mathrm{min}})$. Write $f(t)=(u_{i}(t),v_{i}(t))_{i=1}^{P}$. Divide $[0,1]$ to times $(t_{0}=0,t_{1})$, $(t_{1},t_{2})\cdots(t_{k-1},t_{k}=1)$, where in each time interval either each $u_{i},v_{i}$ are either always zero or always nonzero. We have finitely many such $t_{i}$ s because we assume that the cardinality change is finite. From [E.10](#A5.Thmappxproposition10), we can see that the path $\Psi\circ f(t)$ is continuous at each interval. However, as we saw in [E.10](#A5.Thmappxproposition10), $\Psi\circ f(t_{i})$, $\lim_{t\rightarrow t_{i}^{-}}\Psi\circ f(t)$, $\lim_{t\rightarrow t_{i}^{+}}\Psi\circ f(t)$ are all permutations of each other.
We construct a path from $\Psi\circ f(0)$ to $\Psi\circ f(1)$ as following: First, for each $p=0,1,\cdots,k-1$, construct a path from $\lim_{t\rightarrow t_{p}^{+}}\Psi\circ f(t)$ to $\lim_{t\rightarrow t_{p+1}^{-}}\Psi\circ f(t)$ by defining

$$ $g(t)=\begin{cases}\lim_{t\rightarrow t_{p}^{+}}\Psi\circ f(t)\quad if\quad t=t_{p}\\ \Psi\circ f(t)\quad if\quad t\in(t_{p},t_{p+1})\\ \lim_{t\rightarrow t_{p+1}^{-}}\Psi\circ f(t)\quad if\quad t=t_{p+1},\end{cases}$ $$

for $t\in[t_{p},t_{p+1}]$. It is clear that $g$ is continuous. Moreover, we can connect each $\Psi\circ f(t_{p})$ with $\lim_{t\rightarrow t_{p}^{+}}\Psi\circ f(t)$ and $\lim_{t\rightarrow t_{p}^{-}}\Psi\circ f(t)$, because from [E.11](#A5.Thmappxproposition11), we know that when $m\geq M^{*}+1$, two permutations are connected in $\Theta^{*}(m)$, and from [E.10](#A5.Thmappxproposition10), from this construction, a one-sided limit is a permutation of the image. Hence, a connection from $\Psi\circ f(0)$ to $\Psi\circ f(1)$ is possible, by connecting permutations at boundaries of each interval $t_{0},t_{1},\cdots,t_{k}$, and moving with $\Psi\circ f$ inside the intervals.
Hence, $\Psi\circ\Phi(A_{\mathrm{min}})$ and $\Psi\circ\Phi(B_{\mathrm{min}})$ are connected. From [E.8](#A5.Thmappxproposition8), we know that $\Psi\circ\Phi(A_{\mathrm{min}})$ is a permutation of $A_{\mathrm{min}}$, and as $m\geq M^{*}+1$ we know that they are connected. Same holds for $\Psi\circ\Phi(B_{\mathrm{min}})$. This means that we have found a continuous path from $A_{\mathrm{min}}$ to $B_{\mathrm{min}}$. At the beginning we connected $A$ with $A_{\mathrm{min}}$, $B$ with $B_{\mathrm{min}}$, which finishes the proof.
∎

For discontinuity, we use the property of isolated points $A\in\mathcal{P}^{*}_{\mathrm{can}}\cap\mathcal{P}^{*}(m)$ with cardinality $m$.

###### Proposition E.13 .

Suppose $m\geq m^{*}$. If $A\in\mathcal{P}^{*}(m)\cap\mathcal{P}^{*}_{\mathrm{can}}$ is an isolated point in $\mathcal{P}^{*}(m)$ and has $\mathrm{card}(A)=m$, $\Psi(A)$ is an isolated point in $\Theta^{*}(m)$.

###### Proof.

Assume the existence of a continuous function $f:[0,1]\rightarrow\Theta^{*}(m)$ that satisfies $\Psi(A)=f(0)$, $\Phi\circ f(1)\neq A$. Consider the path $\Phi\circ f(t)$ in $\mathcal{P}^{*}(m)$. As $A\in\mathcal{P}^{*}(m)\cap\mathcal{P}^{*}_{\mathrm{can}}$, $\Phi(\Psi(A))=A\neq\Phi\circ f(1)$, which is a contradiction that $A$ is an isolated point in $\mathcal{P}^{*}(m)$. Hence, $\Psi(A)$ does not have a path into $\Theta^{*}(m)-\Phi^{-1}(A)$.
To finish the proof, we show that $\Phi^{-1}(A)$ is finite. If $\Phi^{-1}(A)$ is finite, we will not be able to move from $\Psi(A)$ to a point in $\Phi^{-1}(A)-\{\Psi(A)\}$ only using points in $\Phi^{-1}(A)-\{\Psi(A)\}$, meaning we do not have a path from $\Psi(A)$ to $\Theta^{*}(m)-\{\Psi(A)\}$, proving our claim.
Suppose $\Phi((w_{i},\alpha_{i})_{i=1}^{m})=A$. If $1(Xw_{i}\geq 0)=1(Xw_{j}\geq 0)=D_{p}$ for some $\alpha_{i}\alpha_{j}>0$, the two indices $i$ and $j$ will either correspond to the same $u_{p}$ or $v_{p}$, and $\mathrm{card}(\Phi((w_{i},\alpha_{i})_{i=1}^{m}))<m$, which is a contradiction. Hence, $(w_{i},\alpha_{i})_{i=1}^{m}\in\Theta^{*}_{\mathrm{min}}(m)$. From [E.8](#A5.Thmappxproposition8), we know that $\Psi(\Phi((w_{i},\alpha_{i})_{i=1}^{m}))=\Psi(A)$ is a permutation of $(w_{i},\alpha_{i})_{i=1}^{m}$. This means $\Phi^{-1}(A)$ is contained in a set of permutation of $\Psi(A)$, which is finite.
∎

[E.12](#A5.Thmappxproposition12) and [E.13](#A5.Thmappxproposition13) enables us to discuss connectivity of $\Theta^{*}(m)$ with the connectivity of $\mathcal{P}^{*}(m)$. With the results that we obtained for $\mathcal{P}^{*}(m)$, more specifically [E.1](#A5.Thmappxproposition1), [E.2](#A5.Thmappxproposition2), [E.4](#A5.Thmappxproposition4), [E.1](#A5.Thmappxtheorem1), and applying [E.12](#A5.Thmappxproposition12) and [E.13](#A5.Thmappxproposition13) appropriately, we arrive at the staircase of connectivity defined in [Theorem 2](#Thmtheorem2).

###### Theorem E.2 .

([Theorem 2](#Thmtheorem2) of the paper) (The staircase of connectivity) Denote the optimal solution set of ([1](#S2.E1)) in parameter space as $\Theta^{*}(m)\subseteq\mathbb{R}^{(d+1)m}$. Suppose $L$ is a strictly convex loss function. Let $m^{*},M^{*}$ be two critical values defined in [Theorem 2](#Thmtheorem2).
As $m$ changes, we have that when

- (i)
$m=m^{*}$, $\Theta^{*}(m)$ is a finite set. Hence, for any two optimal points $A\neq A^{\prime}\in\Theta^{*}(m)$, there is no path from $A$ to $A^{\prime}$ inside $\Theta^{*}(m)$.
- (ii)
$m\geq m^{*}+1$, there exists optimal points $A,A^{\prime}\in\Theta^{*}(m)$ and a path in $\Theta^{*}(m)$ connecting them.
- (iii)
$m=M^{*}$, $\Theta^{*}(m)$ is not a connected set. Moreover, there exists $A\in\Theta^{*}(m)$ which is an isolated point, i.e. there is no path in $\Theta^{*}(m)$ that connects $A$ with $A^{\prime}\neq A\in\Theta^{*}(m)$.
- (iv)
$m\geq M^{*}+1$, permutations of the solution are connected. Hence, for all $A\in\Theta^{*}(m)$, there exists $A^{\prime}\neq A$ in $\Theta^{*}(m)$ and a path in $\Theta^{*}(m)$ that connects $A$ and $A^{\prime}$.
- (v)
$m\geq\min\{m^{*}+M^{*},n+1\}$, the set $\Theta^{*}(m)$ is connected, i.e. for any two optimal points $A\neq A^{\prime}\in\Theta^{*}(m)$, there exists a continuous path from $A$ to $A^{\prime}$.

###### Proof.

Proof of i) starts by observing that $A\in\Theta^{*}_{\mathrm{min}}(m^{*})$ if $A\in\Theta^{*}(m^{*})$. If not, we can find a solution $A^{\prime}\in\Theta^{*}_{\mathrm{min}}(m^{*}-1)$ using [E.6](#A5.Thmappxproposition6), and its image $\Phi(A^{\prime})\in\mathcal{P}^{*}(m^{*}-1)$. At last, $\Phi(A^{\prime})$ is connected with a point in $\mathcal{P}^{*}(m^{*}-1)\cap\mathcal{P}^{*}_{\mathrm{irr}}$ using [E.3](#A5.Thmappxproposition3), which contradicts the minimality of $m^{*}$. Now, for any $A\in\Theta^{*}(m^{*})$, $\Phi(A)=B\in\mathcal{P}^{*}(m^{*})$ satisfies that $\Psi(B)$ is a permutation of $A$. Hence, $\Theta^{*}(m^{*})$ is contained in the set of permutations of $\Psi(\mathcal{P}^{*}(m^{*}))$, and as $\mathcal{P}^{*}(m^{*})$ is finite from [E.1](#A5.Thmappxproposition1), we know that $\Theta^{*}(m^{*})$ is also finite.
Proof of ii) is rather simple: we know that the solution in $\Theta^{*}(m^{*})$ will have a zero slot in $\Theta^{*}(m^{*}+1)$, and by using the moving operation in the proof of [E.11](#A5.Thmappxproposition11), we can show that we can move a neuron to the zero slot.
Proof of iii) follows from [E.2](#A5.Thmappxproposition2) and [E.13](#A5.Thmappxproposition13). We can find an isolated point with cardinality $M^{*}$ and is also canonical: the isolated point in [E.2](#A5.Thmappxproposition2) has cardinality $M^{*}$ and is in $\mathcal{P}^{*}_{\mathrm{irr}}$. Say the isolated point is $(u_{i},v_{i})_{i=1}^{P}$. If $1(Xu_{i}\geq 0)=1(Xu_{j}\geq 0)=D_{p}$ for some $i\neq j$ and $u_{i}\neq 0,u_{j}\neq 0$, $D_{p}Xu_{i}$ and $D_{p}Xu_{j}$ are colinear, which leads to a contradiction. Hence all patterns are different for $u,v$, and by appropriate rearrangement, we can find a canonical solution with cardinality $M^{*}$. Say that solution is $P_{\mathrm{can}}$ Now we apply [E.13](#A5.Thmappxproposition13) to see that $\Psi(P_{\mathrm{can}})$ is isolated in $\Theta^{*}(M^{*})$.
Proof of iv) directly follows from [E.11](#A5.Thmappxproposition11).
Proof of v) directly follows from [E.4](#A5.Thmappxproposition4), [E.1](#A5.Thmappxtheorem1) and [E.12](#A5.Thmappxproposition12). Note that the paths constructed in [E.4](#A5.Thmappxproposition4) and [E.1](#A5.Thmappxtheorem1) has only finitely many cardinality changes, hence we can apply [E.12](#A5.Thmappxproposition12).
∎

###### Corollary E.1 .

([Corollary 1](#Thmcorollary1) of the paper) Consider the optimization problem in ([1](#S2.E1)). Suppose $m\geq n+1$ and denote the optimal set of ([1](#S2.E1)) as $\Theta^{*}(m)$. For any $\theta:=(w_{i},\alpha_{i})_{i=1}^{m}\in\mathbb{R}^{(d+1)m}$, there exists a continuous path from $\theta$ to any point $\theta^{*}\in\Theta^{*}(m)$ with nonincreasing loss.

###### Proof.

The proof almost directly follows from [] and [E.1](#A5.Thmappxtheorem1). 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 is actually global from []. Now, we know that the set $\Theta^{*}(m)$ is connected: hence, we can construct a continuous path from that global minimum to any global minimum we want.
∎

###### Definition E.1 .

###### Definition E.2 .

###### Definition E.3 .

###### Definition E.4 .

###### Remark E.1 .

###### Proposition E.1 .

###### Proof.

###### Proposition E.2 .

###### Proof.

###### Proposition E.3 .

###### Proof.

###### Proposition E.4 .

###### Proof.

###### Lemma E.1 .

###### Proof.

###### Theorem E.1 .

###### Proof.

###### Proposition E.5 .

###### Proof.

###### Definition E.5 .

###### Proposition E.6 .

###### Proof.

###### Definition E.6 .

###### Remark E.2 .

###### Definition E.7 .

###### Definition E.8 .

###### Proposition E.7 .

###### Proof.

###### Proposition E.8 .

###### Proof.

###### Proposition E.9 .

###### Proof.

###### Proposition E.10 .

###### Proof.

###### Proposition E.11 .

###### Proof.

###### Proposition E.12 .

###### Proof.

###### Proposition E.13 .

###### Proof.

###### Theorem E.2 .

###### Proof.

###### Corollary E.1 .

###### Proof.

## Appendix F Proofs in Section 3.3

In this section, we give the counterexamples constructed in [Section 3.3](#S3.SS3) and their rigorous proof.

The specific counterexamples we present are the following:

###### Proposition F.1 .

Suppose $n=3$, input data is given as

$$ $\{(x_{1i},x_{2i},y_{i})\}_{i=1}^{3}=\{(1,0,1/6),(-1/2,\sqrt{3}/2,2/3),(-1/2,-\sqrt{3}/2,1/6)\},$ $$

$X=\begin{bmatrix}x_{1}x_{2}\end{bmatrix}\in\mathbb{R}^{3\times 2}$. Then, the minimization problem in ([6](#S3.E6)) without bias has at least two different solutions in $\mathcal{F}^{*}$.

###### Proof.

Let’s consider the set $\mathcal{Q}_{X}=\{(Xu)_{+}\ |\ \lVert u\rVert_{2}\leq 1\}$. The six possible hyperplane arrangement patterns $1(Xu\geq 0)$ are $(001),(010),(100),(011),(101),(110),$ and when we draw the set $\mathcal{Q}_{X}$ we get the following shape in [Figure 7](#A6.F7).

Figure: (a) Six linear regions of $(Xu)_{+}$.

With some scaling trick, we can see that the problem is further equivalent to

$$ $\mathrm{minimize}_{m,w_{0},\{w_{i},\alpha_{i}\}_{i=1}^{m}}\quad\sum_{i=1}^{m}|\alpha_{i}|,\quad\mathrm{subject}\ \mathrm{to}\quad Xw_{0}+\sum_{i=1}^{m}(Xw_{i})_{+}\alpha_{i}=y,\ \lVert w_{i}\rVert_{2}\leq 1\quad\forall i\in[m].$ $$

Now, choose $\nu=[1,1,1]^{T}$. For any optimal $w_{0},w_{1},w_{2},\alpha_{0},\alpha_{1}$, we know that

$$ $\nu^{T}Xw_{0}+\sum_{i=1}^{m}\nu^{T}(Xw_{i})_{+}\alpha_{i}=\sum_{i=1}^{m}\nu^{T}(Xw_{i})_{+}\alpha_{i}=\langle\nu,y\rangle,$ $$

and

$$ $\langle\nu,y\rangle\leq\sum_{i=1}^{m}|\nu^{T}(Xw_{i})_{+}||\alpha_{i}|\leq\sum_{i=1}^{m}|\alpha_{i}|,$ $$

which means that the objective value is lower bounded by $\langle\nu,y\rangle$ = 1. At last, we have two different models that have different breaklines and have objective value 1. The two models are:

$$ $w_{0}=-\frac{1}{3}\begin{bmatrix}1\\ 0\end{bmatrix},w_{1}=\frac{1}{\sqrt{2}}\begin{bmatrix}1\\ 0\end{bmatrix},w_{2}=\frac{1}{\sqrt{2}}\begin{bmatrix}-1/2\\ \sqrt{3}/2\end{bmatrix},\alpha_{1}=\frac{1}{\sqrt{2}},\alpha_{2}=\frac{1}{\sqrt{2}},$ $$

and

$$ $w_{0}=-\frac{1}{3}\begin{bmatrix}-1/2\\ -\sqrt{3}/2\end{bmatrix},w_{1}=\frac{1}{\sqrt{2}}\begin{bmatrix}-1/2\\ -\sqrt{3}/2\end{bmatrix},w_{2}=\frac{1}{\sqrt{2}}\begin{bmatrix}-1/2\\ \sqrt{3}/2\end{bmatrix},\alpha_{1}=\frac{1}{\sqrt{2}},\alpha_{2}=\frac{1}{\sqrt{2}}.$ $$

With direct substitution, we can see that they are both valid interpolators. A direct calculation shows that both have objective value of 1. At last, the breaklines differ, as the breaklines directly correspond to the weight vectors $w_{1},w_{2}$: this means that the two optimal functions are different.
∎

###### Proposition F.2 .

Suppose $n=4$, input data is given as

$$ $\{(x_{1i},x_{2i},y_{i})\}_{i=1}^{4}=\{(1,0,1),(0,1,-1),(-1,0,1),(0,-1,-1)\},$ $$

$X=[x_{1}x_{2}]\in\mathbb{R}^{n\times 2}$. Then, the minimization problem in ([6](#S3.E6)) has at least two different solutions in $\mathcal{F}^{*}$.

###### Proof.

We give a similar proof strategy as that in [F.1](#A6.Thmappxproposition1), writing $\bar{X}=[X\ |\ 1]\in\mathbb{R}^{n\times 3}$ and bounding $|\nu^{T}(\bar{X}u)_{+}|$ for $\nu=[1,-1,1,-1]^{T}$ and $\lVert u\rVert\leq 1$. Note that $\bar{X}^{T}\nu=0$. It is not easy to visualize the shape of $\{(\bar{X}u)_{+}|\lVert u\rVert_{2}\leq 1\}$ as in [Figure 7](#A6.F7), but we can solve the optimization problem by splitting the input domain into 14 regions where the function $(\bar{X}u)_{+}$ is linear. There are 14 such regions due to the classical result of []. A simple convex optimization for these 14 liner regions yields that

$$ $|\nu^{T}(\bar{X}u)_{+}|\leq 1\quad\forall\lVert u\rVert_{2}\leq 1.$ $$

Another way to see this is writing $u=[a,b,c]$ and $\nu^{T}(\bar{X}u)_{+}$ as

$$ $\frac{1}{2}(|a+c|+|a-c|-|b+c|-|b-c|),$ $$

and with the constraint $a^{2}+b^{2}+c^{2}\leq 1$, we have that the above formula is bounded between $-1$ and 1.
Using the same scaling trick, we see that the lower bound of the objective is $\langle\nu,y\rangle$ as in [F.1](#A6.Thmappxproposition1), which is 4. At last, choose two models as

$$ $w_{0}=\begin{bmatrix}0\\ 0\\ 1\end{bmatrix},w_{1}=\begin{bmatrix}0\\ \sqrt{2}\\ 0\end{bmatrix},w_{2}=\begin{bmatrix}0\\ -\sqrt{2}\\ 0\end{bmatrix},\alpha_{1}=-\sqrt{2},\alpha_{2}=-\sqrt{2},$ $$

and

$$ $w_{0}=\begin{bmatrix}0\\ 0\\ -1\end{bmatrix},w_{1}=\begin{bmatrix}\sqrt{2}\\ 0\\ 0\end{bmatrix},w_{2}=\begin{bmatrix}-\sqrt{2}\\ 0\\ 0\end{bmatrix},\alpha_{1}=\sqrt{2},\alpha_{2}=\sqrt{2}.$ $$

Both solutions have cost 4 and interpolates the data. With some simplification, we can see that the first solution gives $f(x,y)=1-2(y)_{+}-2(-y)_{+}$, whereas the second solution gives $f(x,y)=-1+2(x)_{+}+2(-x)_{+}$. Apparently we have two different minimum-norm interpolators. A visualization (and the symmetry behind it) can be found in [Figure 8](#A6.F8).

Figure: (a) Interpolator $f(x,y)=1-2(y)_{+}-2(-y)_{+}$

∎

The two propositions [F.1](#A6.Thmappxproposition1) and [F.2](#A6.Thmappxproposition2) gives [F.3](#A6.Thmappxproposition3).

###### Proposition F.3 .

Consider the minimum-norm interpolation problem

$$ $\min_{m,u,\{w_{i},\alpha_{i}\}_{i=1}^{m}}\frac{1}{2}\sum_{i=1}^{m}\left(\lVert w_{i}\rVert_{2}^{2}+\alpha_{i}^{2}\right),\quad\mathrm{subject}\ \mathrm{to}\quad Xu+\sum_{i=1}^{m}(Xw_{i})_{+}\alpha_{i}=y,$ $$

where for input $X_{in}$, $X=X_{in}$ in the unbiased case and $X=[X_{in}|1]$ in the biased case. Note that $m$ is also an optimization variable that is not fixed. When the input is 2-dimensional, we have a non-unique minimum-norm interpolator regardless of bias.

###### Proof.

This is a direct consequence of [F.1](#A6.Thmappxproposition1) and [F.2](#A6.Thmappxproposition2).
∎

###### Proposition F.4 .

([Proposition 1](#Thmproposition1) of the paper)
Consider the minimum-norm interpolation problem without free skip connections and regularized bias.
Take $n$ vectors in $\mathbb{R}^{2}$ that satisfy

$$ $v_{n}=[\frac{\sqrt{3}}{2},\frac{1}{2}]^{T},\ \lVert s_{k}\rVert_{2}=1,s_{k}>0\ \ \forall k\in[n-1],\ s_{n}=[0,1]^{T},\ v_{i,2}>0\ \ \forall i\in[n].$ $$

where we write $\sum_{i=1}^{k}v_{n-i+1}=s_{k}$. Now, choose $x_{i}=v_{i,1}/v_{i,2}$ and choose $y$ as any conic combination of $n+1$ vectors

$$ $(s_{i,1}x+s_{i,2}1)_{+}\quad\forall i\in[n],\quad((s_{n}-v_{n})_{1}x+(s_{n}-v_{n})_{2}1)_{+},$ $$

with positive weights. Then, there exist infinitely many minimum-norm interpolators.

###### Proof.

Let’s choose $x$ as proposed in [Proposition 1](#Thmproposition1). Also, let’s choose $\nu\in\mathbb{R}^{n}$ as $\nu_{i}=v_{i,2}$. Write $\bar{X}=[x|1]\in\mathbb{R}^{n\times 2}$. Then the problem without free skip connection and with regularized bias becomes

$$ $\min_{m,w_{0},\{w_{i},\alpha_{i}\}_{i=1}^{m}}\sum_{i=1}^{m}\lVert w_{i}\rVert_{2}^{2}+|\alpha_{i}|^{2}\quad\mathrm{subject}\ \ \mathrm{to}\quad\bar{X}w_{0}+\sum_{i=1}^{m}(\bar{X}w_{i})_{+}\alpha_{i}=y.$ $$

We first show that

$$ $\max_{\lVert u\rVert_{2}\leq 1}|\nu^{T}(\bar{X}u)_{+}|=1,$ (21) $$

and the solutions are $s_{1},s_{2},\cdots s_{n},s_{n}-v_{n}$.
The first thing to observe is that $x_{1}<x_{2}<\cdots<x_{n}$. To prove this, let’s see that for $i=2,3,\cdots n-1$,

$$ $x_{i-1}<-\frac{s_{n-i+1,2}}{s_{n-i+1,1}}<x_{i}.$ $$

The reason is the following: for $i=2,3,\cdots n-1$, we know $\lVert s_{n-i+1}+v_{i-1}\rVert_{2}=1$, and as $\lVert s_{n-i+1}\rVert_{2}=1$ we know $s_{n-i+1}\cdot v_{i-1}=-1/2\cdot\lVert v_{i-1}\rVert_{2}^{2}<0$. Hence, $s_{n-i+1,1}v_{i-1,1}+s_{n-i+1,2}v_{i-1,2}<0$, and as $s_{n-i+1,1},s_{n-i+1,2},v_{i-1,2}>0$, we have $s_{n-i+1,2}/s_{n-i+1,1}<-v_{i-1,1}/v_{i-1,2}=-x_{i-1}$. Similarly, $\lVert s_{n-i+1}-v_{i}\rVert_{2}=1$, and as $s_{n-i+1}\cdot v_{i}>0$, we have $s_{n-i+1,2}/s_{n-i+1,1}>-v_{i,1}/v_{i,2}=-x_{i}$. This means for $i=2,3,\cdots n-1$, $x_{i-1}<x_{i}$, and $x_{1}<x_{2}<\cdots<x_{n-1}$. At last, we have $v_{n-1}\cdot v_{n}<0$ because $\lVert v_{n}\rVert_{2}=\lVert v_{n}+v_{n-1}\rVert_{2}=1$, meaning $x_{n-1}<0$, whereas $x_{n}=\sqrt{3}>0$, meaning $x_{1}<x_{2}<\cdots<x_{n}$.

Now we consider the possible arrangement patterns $\mathrm{diag}(1(\bar{X}u\geq 0))$. We can see that the possible patterns are $\mathrm{diag}([0,0,\cdots,0])$, $\mathrm{diag}([0,0,\cdots,0,1])$, $\mathrm{diag}([0,0,\cdots,1,1])$, $\cdots\mathrm{diag}([0,1,\cdots,1,1])$, $\mathrm{diag}([1,1,\cdots,1,1])$, $\cdots\mathrm{diag}([1,0,\cdots,0,0])$. In other words, starting from the $n$-th entry, 0 turns to 1 in reverse order, then we have all ones, then 1s become 0s at starting from the $n$-th entry. Let’s denote the diagonal matrices $D_{1},D_{2},\cdots D_{2n}$.

Solving ([21](#A6.E21)) is equivalent to solving

$$ $\max_{(2D_{i}-I)\bar{X}u\geq 0,\ \lVert u\rVert_{2}\leq 1}\nu^{T}D_{i}\bar{X}u.$ $$

The absolute value function is erased as $\nu>0$.

For $D_{1}$, the objective is 0.
For $D_{2}$ to $D_{n+2}$, we first know that $\lVert\nu^{T}D_{i}\bar{X}\rVert_{2}=1$. To see this, observe that $\lVert\nu^{T}D_{2}\bar{X}\rVert_{2}=\lVert\nu_{n}[x_{n},1]\rVert_{2}=\lVert v_{n}\rVert_{2}=1$, $\lVert\nu^{T}D_{3}\bar{X}\rVert_{2}=\lVert\nu_{n}[x_{n},1]+\nu_{n-1}[x_{n-1},1]\rVert_{2}=\lVert v_{n}+v_{n-1}\rVert_{2}=1$, $\cdots,\lVert\nu^{T}D_{n+1}\bar{X}\rVert_{2}=\lVert\sum_{i=1}^{n}v_{i}\rVert_{2}=1,\lVert\nu^{T}D_{n+2}\bar{X}\rVert_{2}=\lVert\sum_{i=1}^{n-1}v_{i}\rVert_{2}=\lVert[-\frac{\sqrt{3}}{2},\frac{1}{2}]\rVert_{2}=1$. For $D_{n+3}$ to $D_{2n}$, we can also see that $\lVert\nu^{T}D_{i}\bar{X}\rVert_{2}<1$. That is because $\nu^{T}D_{n+k}\bar{X}=s_{n}-s_{k-1}$ for $k\geq 2$. $\lVert s_{n}-s_{k-1}\rVert_{2}=2-2s_{n}\cdot s_{k-1}$, and as we know $1/2=s_{n}\cdot s_{1}<s_{n}\cdot s_{2}<\cdots s_{n}\cdot s_{n-1}$ (which is the sum of $v_{i,2}$, and as $v_{i,2}>0$ we have the property), $\lVert s_{n}-s_{k-1}\rVert_{2}<1$ for $k=3,4,\cdots n$.

We can then see that $\max_{(2D_{i}-I)\bar{X}u\geq 0,\ \lVert u\rVert_{2}\leq 1}\nu^{T}D_{i}\bar{X}u\leq\max_{i\in[2n]}\lVert\nu^{T}D_{i}\bar{X}\rVert_{2}=1$. The last thing to check is that $s_{1},s_{2},\cdots s_{n},s_{n}-v_{n}$ are actual solutions. For $i=2,3,\cdots n-1$, we know that

$$ $x_{1}<x_{2}<\cdots<x_{i-1}<-\frac{s_{n-i+1,2}}{s_{n-i+1,1}}<x_{i}<x_{i+1}<\cdots<x_{n},$ $$

and when we write $k_{i}=[x_{i},1]^{T}$, we have that $k_{n}\cdot s_{n-i+1}>0,\cdots k_{i}\cdot s_{n-i+1}>0$, $k_{i-1}\cdot s_{n-i+1}<0,\cdots k_{1}\cdots s_{n-i+1}<0$ for all $i=2,3,\cdots n-1$. Hence, for $s_{2},s_{3},\cdots s_{n-1}$, $(2D_{i+1}-I)\bar{X}s_{i}\geq 0$. As $s_{i}=\bar{X}^{T}D_{i+1}\nu$, for these $s_{i}$s, $\nu^{T}(\bar{X}s_{i})_{+}=1$.

The three cases we have to check are when $i=1,n$, and $s_{n}-v_{n}$. When $i=n$, $s_{n}=[0,1]^{T}$ and as all $k_{i}$s have positive y values, $s_{n}\cdot k_{i}>0$ for all $i\in[n]$ and indeed, $s_{n}$ becomes a solution. Also, we know that $\lVert s_{1}+v_{n-1}\rVert_{2}=1$, meaning $x_{1}<x_{2}<\cdots<x_{n-1}<-s_{1,2}/s_{1,1}$. Hence, $k_{n-1}\cdot s_{1}<0,\cdots k_{1}\cdot s_{1}<0$. As $s_{1}$ and $k_{n}$ are parallel, we know $k_{n}\cdot s_{1}>0$. Same with other cases, as $\lVert s_{1}\rVert_{2}=1$, $s_{1}$ is a solution. At last, let’s check that $(2D_{n+2}-I)\bar{X}(s_{n}-v_{n})\geq 0$. As $v_{n}=[\sqrt{3}/2,1/2]^{T}$, $s_{n}-v_{n}=[-\sqrt{3}/2,1/2]^{T}$, $v_{n}\cdot(s_{n}-v_{n})<0$ and $k_{n}\cdot(s_{n}-v_{n})<0$. For $i\in[n-1]$, we know $x_{i}<0$. Hence, $-\sqrt{3}x_{i}+1>0$. This means $(2D_{n+2}-I)\bar{X}(s_{n}-v_{n})>0$ and as $\lVert s_{n}-v_{n}\rVert_{2}=1$, we have $s_{n}-v_{n}$ as a solution too.

Now that we have found $n+1$ different solutions to problem in ([21](#A6.E21)), let’s note them $w_{1},w_{2},\cdots w_{n+1}$. $y$ is chosen as any conic combination

$$ $y=\sum_{i=1}^{n+1}c_{i}(\bar{X}w_{i})_{+},$ (22) $$

where $c_{i}>0$. We know that the interpolation problem is equivalent to

$$ $\min\ t\quad\mathrm{subject}\ \ \mathrm{to}\quad y\in t\mathrm{Conv}(\mathcal{Q}_{\bar{X}}\cup-\mathcal{Q}_{\bar{X}}),$ $$

where $\mathcal{Q}_{\bar{X}}=\{(\bar{X}u)_{+}\ |\ \lVert u\rVert_{2}\leq 1\}$ []. In other words, the minimum-norm interpolation problem without free skip connections and regularized bias is equivalent to

$$ $\min_{m,(z_{i},d_{i})_{i=1}^{m}}\sum_{i=1}^{m}|d_{i}|,\quad y=\sum_{i=1}^{m}d_{i}(\bar{X}z_{i})_{+},$ $$

for some $\lVert z_{i}\rVert_{2}\leq 1$, $i\in[m]$. For any $d_{i},z_{i}$ that satisfies $\lVert z_{i}\rVert_{2}\leq 1$ and

$$ $y=\sum_{i=1}^{m}d_{i}(\bar{X}z_{i})_{+},$ $$

we have that

$$ $\langle\nu,y\rangle=\sum_{i=1}^{n+1}c_{i}=\sum_{i=1}^{m}d_{i}\nu^{T}(\bar{X}z_{i})_{+}\leq\sum_{i=1}^{m}|d_{i}\nu^{T}(\bar{X}z_{i})_{+}|\leq\sum_{i=1}^{m}|d_{i}|,$ $$

meaning $\langle\nu,y\rangle$ is the optimal value, and any conic combination of $\{(\bar{X}w_{i})_{+}\}_{i=1}^{n+1}$ yields a solution.

Let’s write $w_{i}=[a_{i},b_{i}]^{T}$. The optimal interpolator then becomes

$$ $f(\bar{X})=\sum_{i=1}^{n+1}c_{i}(a_{i}x+b_{i})_{+},$ $$

for $c_{i}$ s satisfying ([22](#A6.E22)). The last thing to check is that there are infinitely many such interpolators. This is slightly different from $y$ having infinitely many different conic combination expressions of $\{(\bar{X}w_{i})_{+}\}_{i=1}^{n+1}$, because different $c_{i}$ may correspond to the same function.

As a final step, we show that we indeed have infinitely many different interpolators. Recall that $\{s_{1},s_{2},\cdots s_{n},s_{n}-v_{n}\}=\{w_{1},w_{2},\cdots w_{n+1}\}$. Note that $s_{1,1},s_{2,1},\cdots s_{n,1}\geq 0$ and $s_{n,1}-v_{n,1}<0$. Without loss of generality let $s_{i}=w_{i}$ for $i\in[n]$ and $s_{n}-v_{n}=w_{n+1}$. As $x\rightarrow-\infty$, the slope will be $c_{n+1}a_{n+1}$. Showing the different conic representations of $y$ have different $c_{n+1}$ values is enough. The interesting observation is that the vectors $\{(\bar{X}w_{i})_{+}\}_{i=1}^{n}$ is actually linearly independent, because each vector has $D_{2},D_{3},\cdots D_{n+1}$ as arrangement patterns and for each $s_{1},s_{2},\cdots s_{n}$, strict inequality holds. Hence, for each different conic combination of $y$, $c_{n+1}$ should be different. This means the slope at $x\rightarrow-\infty$ is different, and we indeed have infinitely many optimal interpolators.
∎

###### Proposition F.1 .

###### Proof.

###### Proposition F.2 .

###### Proof.

###### Proposition F.3 .

###### Proof.

###### Proposition F.4 .

###### Proof.

## Appendix G Proofs in Section 4

In this section, we prove how our results can be generalized to different architectures and setups. We begin by describing a general solution set.

###### Theorem G.1 .

Consider the cone-constrained group LASSO with regularization $\mathcal{R}_{i}$,

$$ $\min_{\theta_{i}\in\mathcal{C}_{i},s_{i}\in\mathcal{D}_{i}}L(\sum_{i=1}^{P}A_{i}\theta_{i}+\sum_{i=1}^{Q}B_{i}s_{i},y)+\beta\sum_{i=1}^{P}\mathcal{R}_{i}(\theta_{i}).$ (23) $$

Assume $\theta_{i},s_{j}\in\mathbb{R}^{d}$, $A_{i},B_{j}\in\mathbb{R}^{n\times d}$, $\mathcal{R}_{i}:\mathbb{R}^{d}\rightarrow\mathbb{R}$ are norms, $\mathcal{C}_{i},\mathcal{D}_{j}\subseteq\mathbb{R}^{d}$ are proper cones for $i\in[P],j\in[Q]$, and $\beta>0$. The optimal set $\mathcal{P}^{*}_{\mathrm{gen}}$ is given as

$$ $\begin{split}\mathcal{P}^{*}_{\mathrm{gen}}=\Big{\{}(c_{i}\bar{\theta}_{i})_{i=1}^{P}\oplus(s_{i})_{i=1}^{Q}|\ c_{i}\geq 0,&\sum_{i=1}^{P}c_{i}A_{i}\bar{\theta}_{i}+\sum_{i=1}^{Q}B_{i}s_{i}\in\mathcal{C}_{y},\\ &\bar{\theta}_{i}\in Zer(F(\mathcal{S}_{i},A_{i}^{T}\nu^{*},-\beta,\langle,\rangle)),\langle B_{i}^{T}\nu^{*},s_{i}\rangle=0,s_{i}\in\mathcal{D}_{i}\Big{\}},\end{split}$ (24) $$

where $\nu^{*}$ is any vector that minimizes $f^{*}(\nu)$
subject to the constraint

$$ $\min_{u\in\mathcal{C}_{i}}\langle A_{i}^{T}\nu,u\rangle+\beta\mathcal{R}_{i}(u)=0,\quad\min_{s\in\mathcal{D}_{j}}\langle B_{j}^{T}\nu,s\rangle=0,$ $$

for all $i\in[P]$, $j\in[Q]$, $F(\mathcal{S},v,-\beta,\langle,\rangle)=\{u\ |\ u\in\mathcal{S},\langle v,u\rangle=-\beta\},$ $\mathcal{S}_{i}=\mathcal{C}_{i}\cup\{u\ |\ \mathcal{R}_{i}(u)=1\}$ and $Zer(S)=\{0\}$ if $S=\emptyset$, $S$ otherwise. Here, $f(\cdot)=L(\cdot,y)$ and $f^{*}$ denotes the Fenchel conjugate of $f$.

###### Proof.

Suppose the optimal set of the problem in ([23](#A7.E23)) is $\Theta^{*}_{\mathrm{gen}}$. We show that $\Theta^{*}_{\mathrm{gen}}\subseteq\mathcal{P}^{*}_{\mathrm{gen}}$ and vice versa. Suppose $(\theta^{*},s^{*})=(\theta^{*}_{i})_{i=1}^{P}\oplus(s^{*}_{i})_{i=1}^{Q}\in\Theta^{*}_{\mathrm{gen}}$. We know that $\sum_{i=1}^{P}A_{i}\theta^{*}_{i}+\sum_{i=1}^{Q}B_{i}s_{i}^{*}\in\mathcal{C}_{y}$, hence it satisfies the second condition for $w^{*}=\sum_{i=1}^{P}A_{i}\theta^{*}_{i}+\sum_{i=1}^{Q}B_{i}s_{i}^{*}$. Also, consider the convex optimization problem

$$ $\min_{w,\theta_{i}\in\mathcal{C}_{i},s_{i}\in\mathcal{D}_{i}}L(w,y)+\beta\sum_{i=1}^{P}\mathcal{R}(\theta_{i})\ \ \mathrm{subject}\ \mathrm{to}\ \sum_{i=1}^{P}A_{i}\theta_{i}+\sum_{i=1}^{Q}B_{i}s_{i}=w,$ $$

and its Lagrangian

$$ $\mathcal{L}(w,\theta,s,\nu)=L(w,y)-\nu^{T}w+\sum_{i=1}^{P}(\langle A_{i}^{T}\nu,\theta_{i}\rangle+\beta\mathcal{R}_{i}(\theta_{i}))+\sum_{i=1}^{Q}\langle B_{i}^{T}\nu,s_{i}\rangle.$ (25) $$

The strong duality argument is essentially the same as that with the proof in [Theorem 1](#Thmtheorem1). Moreover, for the dual problem

$$ $\max_{\nu}\min_{w,\theta_{i}\in\mathcal{C}_{i},s_{i}\in\mathcal{D}_{i}}\mathcal{L}(w,\theta,s,\nu),$ $$

if $\min_{u\in\mathcal{C}_{i}}\langle A_{i}^{T}\nu,u\rangle+\beta\mathcal{R}_{i}(u)<0$, we can scale $u$ infinitely large to attain the minimum $-\infty$. Same holds when $\min_{u\in\mathcal{D}_{i}}\langle B_{i}^{T}\nu,u\rangle<0$. Hence, these cases cannot maximize the dual objective, and the dual problem can be written as

$$ $\max_{\begin{subarray}{c}\min_{u\in\mathcal{C}_{i}}\langle A_{i}^{T}\nu,u\rangle+\beta\mathcal{R}_{i}(u)=0\\ \min_{u\in\mathcal{D}_{i}}\langle B_{i}^{T}\nu,u\rangle=0\end{subarray}}\min_{w}L(w,y)-\nu^{T}w=\max_{\begin{subarray}{c}\min_{u\in\mathcal{C}_{i}}\langle A_{i}^{T}\nu,u\rangle+\beta\mathcal{R}_{i}(u)=0\\ \min_{u\in\mathcal{D}_{i}}\langle B_{i}^{T}\nu,u\rangle=0\end{subarray}}-f^{*}(\nu),$ $$

meaning $\nu^{*}$ is the dual optimal point. When strong duality holds, for any primal optimal point $(w^{*},\theta^{*},s^{*})$ and the dual optimal point $\nu^{*}$, the Lagrangian $\mathcal{L}(w,\theta,s,\nu^{*})$ attains minimum at $(w^{*},\theta^{*},s^{*})$. Substitute $\nu^{*}$ in ([25](#A7.E25)) to see that each $\theta_{i}^{*}$ is a minimizer of the problem

$$ $\min\ \langle A_{i}^{T}\nu^{*},u\rangle+\beta\mathcal{R}(u)\ \ \mathrm{subject}\ \mathrm{to}\ u\in\mathcal{C}_{i}.$ $$

One thing to notice is that the value $\langle A_{i}^{T}\nu^{*},\theta_{i}^{*}\rangle+\beta\mathcal{R}(\theta_{i}^{*})=0$, because if it is strictly smaller than 0 we can strictly decrease the objective $\langle A_{i}^{T}\nu^{*},u\rangle+\beta\mathcal{R}(u)$ with $u=2\theta_{i}^{*}$.

If $\theta_{i}^{*}=0$, we can choose $c_{i}=0$ to find $c_{i},\bar{\theta}_{i}\in Zer(F(\mathcal{S}_{i},A_{i}^{T}\nu^{*},-\beta))$. If $\theta_{i}^{*}\neq 0$, we know that $\mathcal{R}(\theta_{i}^{*})\neq 0$, and the vector $\theta_{i}^{*}/\mathcal{R}(\theta_{i}^{*})$ satisfies $\theta_{i}^{*}/\mathcal{R}(\theta_{i}^{*})\in\mathcal{S}_{i}$ and $\langle A_{i}^{T}\nu^{*},\theta_{i}^{*}/\mathcal{R}(\theta_{i}^{*})\rangle=-\beta$. Choose $c_{i}=\mathcal{R}(\theta_{i}^{*})$, $\bar{\theta}_{i}=\theta_{i}^{*}/\mathcal{R}(\theta_{i}^{*})$ to find $c_{i},\bar{\theta}_{i}\in Zer(F(\mathcal{S}_{i},A_{i}^{T}\nu^{*},-\beta))$.

For $s_{i}^{*}$ s, we know that each $s_{i}^{*}$ s are the minimizer of the problem

$$ $\min\langle B_{i}^{T}\nu^{*},u\rangle\ \ \mathrm{subject}\ \mathrm{to}\ \ u\in\mathcal{D}_{i},$ $$

hence it should be in $\mathcal{D}_{i}$ and the value $\langle B_{i}^{T}\nu^{*},s_{i}^{*}\rangle=0$.

Concluding, for any $(\theta^{*},s^{*})$, clearly $\sum_{i=1}^{P}A_{i}\theta_{i}^{*}+\sum_{j=1}^{Q}B_{j}s_{j}^{*}\in\mathcal{C}_{y}$ and $s_{i}^{*}\in\mathcal{D}_{i},\langle B_{i}^{T}\nu^{*},s_{i}^{*}\rangle=0$, choose $c_{i}=0$ when $\theta_{i}^{*}=0$, $c_{i}=\mathcal{R}(\theta_{i}^{*})$, $\bar{\theta}_{i}=\theta_{i}^{*}/\mathcal{R}(\theta_{i}^{*})$ otherwise to see that $(\theta^{*},s^{*})\in\mathcal{P}_{\mathrm{gen}}^{*}$, and

$$ $\Theta^{*}_{\mathrm{gen}}\subseteq\mathcal{P}_{\mathrm{gen}}^{*}.$ $$

Now, let’s take an element $(\theta,s)\in\mathcal{P}_{\mathrm{gen}}^{*}$.
If $\bar{\theta}_{i}\neq 0$, we know that $\langle\nu^{*},A_{i}\bar{\theta}_{i}\rangle=-\beta$ as $\bar{\theta}_{i}\in F(\mathcal{S}_{i},A_{i}^{T}\nu^{*},-\beta)$. Moreover, $\bar{\theta}_{i}$ is the solution to

$$ $\min_{u\in\mathcal{C}_{i},\mathcal{R}_{i}(u)\leq 1}\langle A_{i}^{T}\nu^{*},u\rangle,$ $$

because for all $u\in\mathcal{S}_{i}$, $\langle A_{i}^{T}\nu^{*},u\rangle\geq-\beta\mathcal{R}_{i}(u)\geq-\beta$ holds. This means $\mathcal{R}_{i}(\bar{\theta}_{i})=1$ for all $\bar{\theta}_{i}\neq 0$, as the minimum will be attained at a nonzero point, hence the boundary where $\mathcal{R}_{i}(u)=1$. Using $\langle\nu^{*},A_{i}\bar{\theta}_{i}\rangle=-\beta$ and $\langle B_{i}^{T}\nu^{*},s_{i}\rangle=0$, we get

$$ $\langle\nu^{*},w^{\prime}\rangle=\langle\nu^{*},\sum_{i=1}^{P}c_{i}A_{i}\bar{\theta}_{i}+\sum_{i=1}^{Q}B_{i}s_{i}\rangle=-\beta\sum_{\bar{\theta}_{i}\neq 0}c_{i},$ $$

for some $w^{\prime}\in\mathcal{C}_{y}$. On the other hand, from $\mathcal{R}_{i}(\bar{\theta}_{i})=1$ for all $i\in[P]$, we know that

$$ $\sum_{i=1}^{P}\mathcal{R}_{i}(c_{i}\bar{\theta}_{i})=\sum_{\bar{\theta}_{i}\neq 0}c_{i}.$ $$

This leads to the fact that for $(\theta,s)$,

$$ $L(\sum_{i=1}^{P}A_{i}\theta_{i}+\sum_{i=1}^{Q}B_{i}s_{i},y)+\beta\sum_{i=1}^{P}\mathcal{R}_{i}(\theta_{i})=L(w^{\prime},y)+\beta\sum_{\bar{\theta}_{i}\neq 0}c_{i}=L(w^{\prime},y)-\langle\nu^{*},w^{\prime}\rangle.$ $$

At last, we show that for all $w^{\prime}\in\mathcal{C}_{y}$,

$$ $L(w^{\prime},y)-\langle\nu^{*},w^{\prime}\rangle=\min_{\theta_{i}\in\mathcal{C}_{i},s_{i}\in\mathcal{D}_{i}}L(\sum_{i=1}^{P}A_{i}\theta_{i}+\sum_{i=1}^{Q}B_{i}s_{i},y)+\beta\sum_{i=1}^{P}\mathcal{R}_{i}(\theta_{i}).$ $$

The fact follows when we use the fact that for $(\theta^{\prime},s^{\prime})\in\Theta^{*}_{\mathrm{gen}}$ that satisfies $w^{\prime}=\sum_{i=1}^{P}A_{i}\theta_{i}^{\prime}+\sum_{i=1}^{Q}B_{i}s_{i}^{\prime}$, the point $(w^{\prime},\theta^{\prime},s^{\prime})$ becomes a minimizer of $\mathcal{L}(w,\theta,s,\nu^{*})$.
Hence, each minimizer $\theta_{i}^{\prime}$ is a minimizer of the problem

$$ $\min\langle A_{i}^{T}\nu^{*},u\rangle+\beta\mathcal{R}_{i}(u)\ \ \mathrm{subject}\ \mathrm{to}\ u\in\mathcal{C}_{i},$ $$

which means that $\beta\mathcal{R}_{i}(\theta^{\prime}_{i})=-\langle\nu^{*},A_{i}\theta^{\prime}_{i}\rangle$ for all $i\in[P]$, as $\nu^{*}$ satisfies

$$ $\min_{u\in\mathcal{C}_{i}}\langle A_{i}^{T}\nu^{*},u\rangle+\beta\mathcal{R}_{i}(u)=0.$ $$

Also, $\langle\nu^{*},B_{i}s_{i}^{\prime}\rangle=0$ as $s_{i}^{\prime}$ minimizes $\langle B_{i}^{T}\nu^{*},s\rangle\ \ \mathrm{subject}\ \mathrm{to}\ s\in\mathcal{D}_{i}$, and we see that

$$ $\beta\sum_{i=1}^{P}\mathcal{R}_{i}(\theta^{\prime}_{i})=-\langle\nu^{*},w^{\prime}\rangle,$ $$

and

$$ $\displaystyle\min_{\theta_{i}\in\mathcal{C}_{i},s_{i}\in\mathcal{D}_{i}}L(\sum_{i=1}^{P}A_{i}\theta_{i}+\sum_{i=1}^{Q}B_{i}s_{i},y)+\beta\sum_{i=1}^{P}\mathcal{R}(\theta_{i})$ $\displaystyle=L(\sum_{i=1}^{P}A_{i}\theta_{i}^{\prime}+\sum_{i=1}^{Q}B_{i}s_{i}^{\prime},y)+\beta\sum_{i=1}^{P}\mathcal{R}(\theta_{i}^{\prime})$ $\displaystyle=L(w^{\prime},y)-\langle\nu^{*},w^{\prime}\rangle,$ $$

meaning $(\theta,s)\in\Theta^{*}_{\mathrm{gen}}$ because

$$ $L(\sum_{i=1}^{P}A_{i}\theta_{i}+\sum_{i=1}^{Q}B_{i}s_{i},y)+\beta\sum_{i=1}^{P}\mathcal{R}(\theta_{i})=L(w^{\prime},y)-\langle\nu^{*},w^{\prime}\rangle.$ $$

This means

$$ $\mathcal{P}_{\mathrm{gen}}^{*}\subseteq\Theta^{*}_{\mathrm{gen}},$ $$

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 G.1 .

The solution set of the optimization problem

$$ $\min_{u_{i},v_{i}\in\mathcal{K}_{i}}\quad\sum_{i=1}^{P}\lVert u_{i}\rVert_{2}+\lVert v_{i}\rVert_{2}$ $$

subject to

$$ $\sum_{i=1}^{P}D_{i}X(u_{i}-v_{i})=y,$ $$

is given as

$$ $\mathcal{P}^{*}:=\left\{(c_{i}\bar{u}_{i},d_{i}\bar{v}_{i})_{i=1}^{P}\ |\ c_{i},d_{i}\geq 0\quad\forall i\in[P],\quad\sum_{i=1}^{P}D_{i}X\bar{u}_{i}c_{i}-D_{i}X\bar{v}_{i}d_{i}=y\right\}\subseteq\mathbb{R}^{2dP},$ $$

where $\bar{u}_{i},\bar{v}_{i}$ are fixed directions found by solving the optimization problem

$$ $\bar{u}_{i}=\operatorname*{arg\,min}_{u\in\mathcal{S}_{i}}{\nu^{*}}^{T}D_{i}Xu\ \ \mathrm{if}\ \ \min_{u\in\mathcal{S}_{i}}{\nu^{*}}^{T}D_{i}Xu=-1,\ \ 0\ \ otherwise,$ $$

$$ $\bar{v}_{i}=\operatorname*{arg\,min}_{v\in\mathcal{S}_{i}}-{\nu^{*}}^{T}D_{i}Xv\ \ \mathrm{if}\ \ \min_{v\in\mathcal{S}_{i}}-{\nu^{*}}^{T}D_{i}Xv=-1,\ \ 0\ \ otherwise.$ $$

and $\nu^{*}$ is any dual optimum that satisfies

$$ $\nu^{*}=\operatorname*{arg\,min}\langle\nu,y\rangle\ \ \mathrm{subject}\ \ \mathrm{to}\ \ |\nu^{T}D_{i}Xu|\leq\lVert u\rVert_{2}\ \ \forall u\in\mathcal{K}_{i},i\in[P].$ $$

Here, $\mathcal{S}_{i}=\mathcal{K}_{i}\cap\{u\ |\ \lVert u\rVert_{2}\leq 1\}$.

###### Proof.

Let’s apply [G.1](#A7.Thmappxtheorem1) to the problem. Note that we can set $\beta=1$. In fact, $\beta$ can be arbitrary, and scaling $\nu^{*}$ to make $\beta=1$ will lead to the same result.

When we apply [G.1](#A7.Thmappxtheorem1), we have that

$$ $\displaystyle\mathcal{P}^{*}_{\mathrm{gen}}=\Big{\{}\ (c_{i}\bar{u}_{i},d_{i}\bar{v}_{i})_{i=1}^{m}\ |\$ $\displaystyle c_{i},d_{i}\geq 0,\sum_{i=1}^{P}D_{i}X\bar{u}_{i}c_{i}-D_{i}X\bar{v}_{i}d_{i}=y,$ $\displaystyle\bar{u}_{i}\in Zer(F(\mathcal{S}_{i},X^{T}D_{i}\nu^{*},-1)),\bar{v}_{i}\in Zer(F(\mathcal{S}_{i},-X^{T}D_{i}\nu^{*},-1))\Big{\}},$ $$

where $\nu^{*}$ is the dual optimum that minimizes $L^{*}(\cdot,y)$ subject to the constraint

$$ $\min_{u\in\mathcal{K}_{i}}\langle X^{T}D_{i}\nu,u\rangle+\lVert u\rVert_{2}=0,\quad\min_{u\in\mathcal{K}_{i}}\langle-X^{T}D_{i}\nu,u\rangle+\lVert u\rVert_{2}=0,$ (26) $$

for all $i\in[P]$. We know that $L^{*}(\nu)=\langle\nu,y\rangle$, and ([26](#A7.E26)) can be rewritten to $|\nu^{T}D_{i}Xu|\leq\lVert u\rVert_{2}$.
Also, $F(\mathcal{S}_{i},X^{T}D_{i}\nu^{*},-1)=\{0\}$ if there is no $u$ such that ${\nu^{*}}^{T}D_{i}Xu=-1$, and is exactly that vector if exists. Note that as $\min_{u\in\mathcal{K}_{i}}\langle X^{T}D_{i}\nu,u\rangle+\lVert u\rVert_{2}=0$, we have a unique minimum for the optimal direction [D.2](#A4.Thmappxproposition2). Same holds for $\bar{v}_{i}$.
∎

###### Proposition G.2 .

(The staircase of connectivity for minimum-norm interpolation problem) Write the solution set of the optimization problem

$$ $\min_{(w_{j},\alpha_{j})_{j=1}^{m}}\quad\frac{1}{2}\sum_{i=1}^{m}\lVert w_{i}\rVert_{2}^{2}+|\alpha_{i}|^{2},$ $$

subject to

$$ $\sum_{i=1}^{m}(Xw_{i})_{+}\alpha_{i}=y,$ $$

as $\Theta^{*}(m)$. As $m$ changes, we have that

- (i)
$m=m^{*}$, $\Theta^{*}(m)$ is a finite set. Hence, for any two optimal points $A\neq A^{\prime}\in\Theta^{*}(m)$, there is no path from $A$ to $A^{\prime}$ inside $\Theta^{*}(m)$.
- (ii)
$m\geq m^{*}+1$, there exists optimal points $A,A^{\prime}\in\Theta^{*}(m)$ and a path in $\Theta^{*}(m)$ connecting them.
- (iii)
$m=M^{*}$, $\Theta^{*}(m)$ is not a connected set. Moreover, there exists $A\in\Theta^{*}(m)$ which is an isolated point, i.e. there is no path in $\Theta^{*}(m)$ that connects $A$ with $A^{\prime}\neq A\in\Theta^{*}(m)$.
- (iv)
$m\geq M^{*}+1$, permutations of the solution are connected. Hence, for all $A\in\Theta^{*}(m)$, there exists $A^{\prime}\neq A$ in $\Theta^{*}(m)$ and a path in $\Theta^{*}(m)$ that connects $A$ and $A^{\prime}$.
- (v)
$m\geq\min\{m^{*}+M^{*},n+1\}$, the set $\Theta^{*}(m)$ is connected, i.e. for any two optimal points $A\neq A^{\prime}\in\Theta^{*}(m)$, there exists a continuous path from $A$ to $A^{\prime}$.

###### Proof.

The proof follows from observing that [E.1](#A5.Thmappxproposition1), [E.2](#A5.Thmappxproposition2), [E.3](#A5.Thmappxproposition3), [E.4](#A5.Thmappxproposition4), [E.1](#A5.Thmappxtheorem1), [E.6](#A5.Thmappxproposition6), [E.11](#A5.Thmappxproposition11), [E.12](#A5.Thmappxproposition12), [E.13](#A5.Thmappxproposition13) holds for interpolation problems too. We can apply the same proof strategy for [E.1](#A5.Thmappxproposition1), [E.2](#A5.Thmappxproposition2), [E.3](#A5.Thmappxproposition3), [E.4](#A5.Thmappxproposition4), [E.1](#A5.Thmappxtheorem1), because the description of the optimal polytope is 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 is preserved, and we have [E.11](#A5.Thmappxproposition11), [E.12](#A5.Thmappxproposition12), [E.13](#A5.Thmappxproposition13). The mapping in [E.6](#A5.Thmappxproposition6) can also be applied here.
∎

Another implication of the theorem is that for free skip connections, the dual variable has to satisfy $X^{T}\nu=0$. The existence of free skip connections constrain freedom on $\nu$, which brings qualitative difference to the uniqueness of the solution set.

###### Proposition G.3 .

The solution set of the optimization problem

$$ $\min_{u_{i},v_{i}\in\mathcal{K}_{i}}\quad\sum_{i=1}^{P}\lVert u_{i}\rVert_{2}+\lVert v_{i}\rVert_{2}$ $$

subject to

$$ $Xu_{0}+\sum_{i=1}^{P}D_{i}X(u_{i}-v_{i})=y,$ $$

is given as

$$ $\mathcal{P}^{*}:=\left\{u_{0}\oplus(c_{i}\bar{u}_{i},d_{i}\bar{v}_{i})_{i=1}^{P}\ |\ c_{i},d_{i}\geq 0\ \forall i\in[P],\ Xu_{0}+\sum_{i=1}^{P}D_{i}X\bar{u}_{i}c_{i}-D_{i}X\bar{v}_{i}d_{i}=y\right\}\subseteq\mathbb{R}^{2dP},$ $$

where $\bar{u}_{i},\bar{v}_{i}$ are fixed directions found by solving the optimization problem

$$ $\bar{u}_{i}=\operatorname*{arg\,min}_{u\in\mathcal{S}_{i}}{\nu^{*}}^{T}D_{i}Xu\ \ \mathrm{if}\ \ \min_{u\in\mathcal{S}_{i}}{\nu^{*}}^{T}D_{i}Xu=-1,\ \ 0\ \ otherwise,$ $$

$$ $\bar{v}_{i}=\operatorname*{arg\,min}_{v\in\mathcal{S}_{i}}-{\nu^{*}}^{T}D_{i}Xv\ \ \mathrm{if}\ \ \min_{v\in\mathcal{S}_{i}}-{\nu^{*}}^{T}D_{i}Xv=-1,\ \ 0\ \ otherwise.$ $$

where $\nu^{*}$ is the dual optimum that satisfies

$$ $\nu^{*}=\operatorname*{arg\,min}\langle\nu,y\rangle\ \ \mathrm{subject}\ \ \mathrm{to}\ \ |\nu^{T}D_{i}Xu|\leq\lVert u\rVert_{2}\ \ \forall u\in\mathcal{K}_{i},i\in[P],\quad X^{T}\nu^{*}=0.$ $$

Here, $\mathcal{S}_{i}=\mathcal{K}_{i}\cap\{u\ |\ \lVert u\rVert_{2}\leq 1\}$.

###### Proof.

Note that if we apply [G.1](#A7.Thmappxtheorem1) to the given problem, we have almost an identical characterization from [G.1](#A7.Thmappxproposition1), except for the free skip connection. For the skip connection $u_{0}\in\mathbb{R}^{d}$, we know that $\min_{u_{0}\in\mathbb{R}^{d}}\langle X^{T}\nu^{*},u_{0}\rangle=0$ for all $u_{0}\in\mathbb{R}^{d}$ because $u_{0}$ is unconstrained. This means $X^{T}\nu^{*}=0$.
∎

Next we give applications of [G.1](#A7.Thmappxtheorem1) to different architectures. We start by characterizing the optimal set of a vector-valued neural network with weight decay.

###### Proposition G.4 .

The solution set of the convex reformulation of the vector-valued problem given as

$$ $\min_{V_{i}}\frac{1}{2}\lVert\sum_{i=1}^{P}D_{i}XV_{i}-Y\rVert_{2}^{2}+\beta\sum_{i=1}^{P}\lVert V_{i}\rVert_{\mathcal{K}_{i},*},$ (27) $$

where the norm $\lVert V\rVert_{\mathcal{K}_{i},*}$ is defined as

$$ $\min t\geq 0\ \ such\ that\ \ V\in t\mathcal{K}_{i},$ $$

for $\mathcal{K}_{i}=\mathrm{conv}\{ug^{T}\ |(2D_{i}-I)Xu\geq 0,\lVert ug^{T}\rVert_{*}\leq 1\}$. The optimal solution set of ([27](#A7.E27)) is given as

$$ $\mathcal{P}^{*}_{\mathrm{vec}}=\Big{\{}(c_{i}\bar{V}_{i})_{i=1}^{P}|\ c_{i}\geq 0,\sum_{i=1}^{P}c_{i}D_{i}X\bar{V}_{i}=Y^{*},\bar{V}_{i}\in Zer(\mathrm{F}(\mathcal{K}_{i},X^{T}D_{i}N^{*},-\beta,\langle,\rangle_{M}))\Big{\}},$ $$

where $N^{*}=Y^{*}-Y$ is the dual optimum that minimizes $\lVert N+Y\rVert_{F}^{2}$ subject to

$$ $\langle N,D_{i}XA\rangle+\beta\lVert A\rVert_{\mathcal{K}_{i},*}\geq 0\quad\forall A\in\mathbb{R}^{d\times c},\quad i\in[P].$ $$

###### Proof.

Let’s define $A_{i}$ as

$$ $A_{i}=\begin{bmatrix}D_{i}X&&\\ &\ddots&\\ &&D_{i}X\end{bmatrix},$ $$

which is a block matrix in $A_{i}\in\mathbb{R}^{nc\times dc}$. Also, define the flattening operation $Fl_{dc}:\mathbb{R}^{d\times c}\rightarrow\mathbb{R}^{dc}$ and $Fl_{nc}:\mathbb{R}^{n\times c}\rightarrow\mathbb{R}^{nc}$. For optimization variables $\theta_{i}\in\mathbb{R}^{dc}$, we have the equivalent problem

$$ $\min_{\theta_{i}}\frac{1}{2}\lVert\sum_{i=1}^{P}A_{i}\theta_{i}-Fl_{nc}(Y)\rVert_{2}^{2}+\beta\sum_{i=1}^{P}\lVert\theta_{i}\rVert_{Fl_{dc}(\mathcal{K}_{i}),*}.$ $$

Here, we are merely flattening each $V_{i}$ s to make it into a vector-input optimization problem. When we apply [G.1](#A7.Thmappxtheorem1) to the flattened problem, we have the optimal set

$$ $\mathcal{P}^{*}_{\mathrm{flat}}=\Big{\{}(c_{i}\bar{\theta}_{i})_{i=1}^{P}|\ c_{i}\geq 0,\sum_{i=1}^{P}c_{i}A_{i}\bar{\theta}_{i}=Fl_{nc}(Y^{*}),\bar{\theta}_{i}\in Zer(\mathrm{F}(S_{i},A_{i}^{T}\nu^{*},-\beta,\langle,\rangle))\Big{\}},$ $$

where

$$ $S_{i}=\{u|\ \lVert u\rVert_{Fl_{dc}(\mathcal{K}_{i}),*}\leq 1\}=Fl_{dc}(\mathcal{K}_{i}),$ $$

$\nu^{*}$ being the minimizer of $f^{*}(\nu)$ where $f=L_{F}(\ \cdot\ ,Fl_{nc}(Y))$, subject to
$\langle A_{i}^{T}\nu^{*},s\rangle+\beta\lVert s\rVert_{Fl_{dc}(\mathcal{K}_{i}),*}\geq 0$.
We know that $\nu^{*}=Fl_{nc}(Y^{*})-Fl_{nc}(Y)$ for the optimal model fit $Y^{*}$. Write $N^{*}=Fl^{-1}_{nc}(\nu^{*})$.

Now we use $Fl_{dc}^{-1},Fl_{nc}^{-1}$ to go back to the original solution space and recover $\mathcal{P}_{\mathrm{vec}}^{*}$. First, we know that $A_{i}\bar{\theta}_{i}=Fl_{dc}(D_{i}XFl_{nc}^{-1}(\bar{\theta}_{i}))$. Hence, the constraint $\sum_{i=1}^{P}c_{i}A_{i}\bar{\theta}_{i}=Fl_{nc}(Y^{*})$ is equivalent to

$$ $\sum_{i=1}^{P}c_{i}D_{i}XFl_{dc}^{-1}(\bar{\theta}_{i})=Y^{*}.$ (28) $$

Also, consider the set

$$ $\mathrm{F}(Fl_{dc}(\mathcal{K}_{i}),A_{i}^{T}\nu^{*},-\beta,\langle,\rangle)=Fl_{dc}(\mathcal{K}_{i})\cap\{u\ |\ \langle A_{i}^{T}\nu^{*},u\rangle=-\beta\}.$ $$

When we use block notation $(\nu^{*})^{T}=[(\nu_{1}^{*})^{T},(\nu_{2}^{*})^{T},\cdots(\nu_{c}^{*})^{T}]$, $u^{T}=[(u_{1})^{T},(u_{2})^{T},\cdots,(u_{c})^{T}]$ for $\nu^{*}\in\mathbb{R}^{nc}$, $u\in\mathbb{R}^{dc}$, we can see that

$$ $(\nu^{*})^{T}A_{i}u=\sum_{i=1}^{c}(\nu_{i}^{*})^{T}D_{i}Xu_{i}=\langle Fl_{nc}^{-1}(\nu^{*}),D_{i}XFl_{dc}^{-1}(u)\rangle_{M},$ $$

using notations for matrix inner product. Hence, we can see that

$$ $\displaystyle Fl_{dc}^{-1}(\mathrm{F}(Fl_{dc}(\mathcal{K}_{i}),A_{i}^{T}\nu^{*},-\beta,\langle,\rangle_{M}))$ $\displaystyle=\mathcal{K}_{i}\cap\{U\ |\ \langle Fl_{nc}^{-1}(\nu^{*}),D_{i}XU\rangle=-\beta\}$ $\displaystyle=\mathrm{F}(\mathcal{K}_{i},X^{T}D_{i}N^{*},-\beta,\langle,\rangle_{M}),$ $$

and for $(\theta_{i})_{i=1}^{P}\in\mathcal{P}^{*}_{\mathrm{flat}}$, $Fl_{dc}^{-1}(\theta_{i})$ satisfies ([28](#A7.E28)) and we also have the fact that $Fl_{dc}^{-1}(\bar{\theta}_{i})\in$$\mathrm{F}(\mathcal{K}_{i},X^{T}D_{i}N^{*},-\beta,\langle,\rangle_{M})$. Hence we arrive at the desired result.
∎

###### Proposition G.5 .

Assume $m\geq m^{*}$ so that the nonconvex problem in ([9](#S4.E9)) and its convex reformulation in ([27](#A7.E27)) are equivalent. The solution set of the vector-valued problem

$$ $\min_{\{w_{i},z_{i}\}_{i=1}^{m}}\frac{1}{2}\lVert\sum_{i=1}^{m}(Xw_{i})_{+}z_{i}^{T}-Y\rVert_{2}^{2}+\frac{\beta}{2}\sum_{i=1}^{m}\lVert w_{i}\rVert_{2}^{2}+\lVert z_{i}\rVert_{2}^{2},$ $$

where $w_{i}\in\mathbb{R}^{d\times 1},z_{i}\in\mathbb{R}^{c\times 1}$ is given as

$$ $\displaystyle\mathcal{S}=\Big{\{}(w_{i},z_{i})_{i=1}^{m}\ |\ \phi((w_{i},z_{i})_{i=1}^{m})\in\mathcal{P}^{*}_{\mathrm{vec}},\mathcal{R}((w_{i},z_{i})_{i=1}^{m})=\lVert$ $\displaystyle\phi((w_{i},z_{i})_{i=1}^{m})\rVert_{\mathcal{K}_{i},*},$ $\displaystyle\lVert w_{i}\rVert_{2}=\lVert z_{i}\rVert_{2},\ \ \forall i\in[m]\Big{\}},$ $$

where

$$ $\phi((w_{i},z_{i})_{i=1}^{m})=(V_{i})_{i=1}^{P}:=V_{p}=\begin{cases}0\ \ if\ \ \nexists\ \ w_{i}\ \ s.t.\ \ D_{p}=1(Xw_{i}\geq 0)\\ \sum_{j=1}^{t_{p}}w_{a_{j}}z_{a_{j}}^{T}\ \ if\ \ D_{p}=1(Xw_{a_{j}}\geq 0)\ \ for\ \ j\in[t_{p}],\end{cases}$ $$

$$ $\mathcal{R}((w_{i},z_{i})_{i=1}^{m})=(R_{i})_{i=1}^{P}:=R_{p}=\begin{cases}0\ \ if\ \ \nexists\ \ w_{i}\ \ s.t.\ \ D_{p}=1(Xw_{i}\geq 0)\\ \sum_{j=1}^{t_{p}}\lVert w_{a_{j}}\rVert_{2}\lVert z_{a_{j}}\rVert_{2}\ \ if\ \ D_{p}=1(Xw_{a_{j}}\geq 0)\ \ for\ \ j\in[t_{p}],\end{cases}$ $$

and $\mathcal{P}^{*}_{\mathrm{vec}}$ is defined in [G.4](#A7.Thmappxproposition4).

###### Proof.

Let’s note the solution set of ([9](#S4.E9)) as $\Theta^{*}$. We will prove that $\Theta^{*}=\mathcal{S}$. First, find a point $(w_{i}^{*},z_{i}^{*})_{i=1}^{m}$ in $\Theta^{*}$. When $\phi((w_{i}^{*},z_{i}^{*})_{i=1}^{m})=(V_{i}^{*})_{i=1}^{P}$, we know that

$$ $\sum_{i=1}^{m}(Xw_{i}^{*})_{+}(z_{i}^{*})^{T}=\sum_{i=1}^{P}D_{i}XV_{i}^{*},$ $$

hence the $l_{2}$ error is the same for both parameters. Also, we have that $\sum_{i=1}^{P}\lVert V_{i}^{*}\rVert_{\mathcal{K}_{i},*}\leq\sum_{i=1}^{m}\lVert w_{i}^{*}\rVert_{2}\lVert z_{i}^{*}\rVert_{2}=\frac{1}{2}\sum_{i=1}^{m}\lVert w_{i}^{*}\rVert_{2}^{2}+\lVert z_{i}^{*}\rVert_{2}^{2}$, Thus, when we note $L_{\mathrm{noncvx}}$ as the loss function of ([9](#S4.E9)) and note $L_{\mathrm{cvx}}$ as the loss function of ([27](#A7.E27)), we have that

$$ $L_{\mathrm{noncvx}}((w_{i}^{*},z_{i}^{*})_{i=1}^{m})\geq L_{\mathrm{cvx}}(\phi((w_{i}^{*},z_{i}^{*})_{i=1}^{m})),$ (29) $$

holds in general. As the minimal value of $L_{\mathrm{noncvx}}$ and $L_{\mathrm{cvx}}$ is the same, we have that $\phi((w_{i}^{*},z_{i}^{*})_{i=1}^{m})\in\mathcal{P}^{*}_{\mathrm{vec}}$. Also, the inequality in ([29](#A7.E29)) is actually an equality, and we have $\mathcal{R}((w_{i},z_{i})_{i=1}^{m})=(\lVert V_{i}\rVert_{\mathcal{K}_{i},*})_{i=1}^{P}$.

Now we take a point $(w_{i},z_{i})_{i=1}^{m}$ in $\mathcal{S}$. We know that $L_{\mathrm{cvx}}(\phi((w_{i},z_{i})_{i=1}^{m}))$ is the optimal value. Also, we know that $L_{\mathrm{noncvx}}((w_{i},z_{i})_{i=1}^{m})=L_{\mathrm{cvx}}(\phi((w_{i},z_{i})_{i=1}^{m}))$ because $\mathcal{R}((w_{i},z_{i})_{i=1}^{m})=(\lVert\phi((w_{i},z_{i})_{i=1}^{m})\rVert_{\mathcal{K}_{i},*})_{i=1}^{P}$ and $\lVert w_{i}\rVert_{2}=\lVert z_{i}\rVert_{2}\forall i\in[m]$. At last, the fact that as $m\geq m^{*}$ and the two optimal values are the same implies that $(w_{i},z_{i})_{i=1}^{m}\in\Theta^{*}$.
∎

###### Theorem G.2 .

([Theorem 4](#Thmtheorem4) of the paper)
Consider a $L$ - layer neural network

$$ $f_{\theta}(X)=((((XW_{1})_{+}W_{2})_{+}\cdots)W_{L-1})_{+}W_{L}$ $$

where $W_{i}\in\mathbb{R}^{d_{i-1}\times d_{i}}$, $d_{0}=d$ and $\theta=(W_{i})_{i=1}^{L}$. Consider the training problem

$$ $\min_{\theta}L(f_{\theta}(X),y)+\frac{\beta}{2}\sum_{i=1}^{L}\lVert W_{i}\rVert_{F}^{2},$ $$

and denote its optimal set as $\Theta^{*}$. We can characterize a subset of $\Theta^{*},$ namely the set

$$ $\displaystyle\Theta_{k-1,k}^{*}(Y^{\prime},$ $\displaystyle W_{1}^{\prime},W_{2}^{\prime},\cdots,W_{k-2}^{\prime},W_{k+1}^{\prime},\cdots W_{L}^{\prime})$ $\displaystyle:=\Big{\{}\theta=(W_{i}^{\prime})_{i=1}^{k-2}\oplus(W_{k-1},W_{k})\oplus(W_{i}^{\prime})_{i=k+1}^{L}\ |\ \theta\in\Theta^{*},\ (\tilde{X}W_{k-1})_{+}W_{k}=Y^{\prime}\Big{\}}.$ $$

Here, $\tilde{X}=((((XW_{1}^{\prime})_{+}W_{2}^{\prime})_{+})\cdots W_{k-2}^{\prime})_{+}$.

The expression of $\Theta_{k-1,k}^{*}(Y^{\prime},W_{1}^{\prime},W_{2}^{\prime},\cdots,W_{k-2}^{\prime},W_{k+1}^{\prime},\cdots W_{L}^{\prime})$ is given as

$$ $\displaystyle\Big{\{}\theta=$ $\displaystyle(W_{i}^{\prime})_{i=1}^{k-2}\oplus(W_{k-1},W_{k})\oplus(W_{i}^{\prime})_{i=k+1}^{L}\ |\ \theta\in\Theta^{*},\ \phi_{d_{k}}(W_{k-1},W_{k})\in\mathcal{P}^{*}_{\mathrm{vec,intp}},$ $\displaystyle\mathcal{R}_{d_{k}}(W_{k-1},W_{k})=\lVert\phi_{d_{k}}(W_{k-1},W_{k})\rVert_{\mathcal{K}_{i},*},\lVert(W_{k-1})_{\cdot,i}\rVert_{2}=\lVert(W_{k})_{i,\cdot}\rVert_{2}\ \forall i\in[d_{k}]\Big{\}},$ $$

where $\phi_{m}(A,B)=\phi((A_{\cdot,i},B_{i,\cdot})_{i=1}^{m}),\mathcal{R}_{m}(A,B)=\mathcal{R}((A_{\cdot,i},B_{i,\cdot})_{i=1}^{m})$ for $\phi$ defined in [G.5](#A7.Thmappxproposition5), and $\mathcal{P}^{*}_{\mathrm{vec,intp}}$ is defined as

$$ $\mathcal{P}^{*}_{\mathrm{vec,intp}}=\Big{\{}(c_{i}\bar{V}_{i})_{i=1}^{P}|\ c_{i}\geq 0,\sum_{i=1}^{P}c_{i}D_{i}X\bar{V}_{i}=Y^{\prime},\bar{V}_{i}\in Zer(\mathrm{F}(\mathcal{K}_{i},X^{T}D_{i}N^{*},-1,\langle,\rangle_{M}))\Big{\}},$ $$

for the dual optimum $N^{*}\in\mathbb{R}^{n\times c}$ that minimizes $\langle N,Y\rangle_{M}$ subject to

$$ $\langle N,D_{i}XA\rangle+\beta\lVert A\rVert_{\mathcal{K}_{i},*}\geq 0\quad\forall A\in\mathbb{R}^{d\times c},\quad i\in[P].$ $$

Here $\mathcal{K}_{i}=\mathrm{conv}\{ug^{T}\ |\ (2D_{i}-I)Xu\geq 0,\lVert ug^{T}\rVert_{*}\leq 1\}$, where $D_{i}$ denotes all possible arrangements $1(Xh\geq 0)$.

###### Proof.

The result is an application of [G.1](#A7.Thmappxtheorem1) to the vector-valued interpolation problem

$$ $\sum_{i=1}^{d_{k}}\lVert u_{i}\rVert_{2}^{2}+\lVert v_{i}\rVert_{2}^{2},$ $$

subject to

$$ $\sum_{i=1}^{d_{k}}(Xu_{i})_{+}v_{i}^{T}=Y^{\prime},$ $$

where $u_{i}\in\mathbb{R}^{d_{k-1}\times 1},v_{i}\in\mathbb{R}^{d_{k+1}\times 1}$, and then applying [G.5](#A7.Thmappxproposition5).
∎

The characterization enables us to extend the connectivity result to vector-valued networks.

###### Theorem G.3 .

([Theorem 3](#Thmtheorem3) of the paper) Consider the optimization problem

$$ $\min_{\{w_{i},z_{i}\}_{i=1}^{m}}\frac{1}{2}\lVert\sum_{i=1}^{m}(Xw_{i})_{+}z_{i}^{T}-Y\rVert_{2}^{2}+\frac{\beta}{2}\sum_{i=1}^{m}\lVert w_{i}\rVert_{2}^{2}+\lVert z_{i}\rVert_{2}^{2},$ (30) $$

where $w_{i}\in\mathbb{R}^{d},z_{i}\in\mathbb{R}^{c}$ for $i\in[m]$, and $Y\in\mathbb{R}^{n\times c}$. If $m\geq nc+1$, the solution set in parameter space $\Theta^{*}\subseteq\mathbb{R}^{m(d+c)}$ is connected.

###### Proof.

Let’s take two solutions $(w_{i},z_{i})_{i=1}^{m},(w_{i}^{\prime},z_{i}^{\prime})_{i=1}^{m}\in\Theta^{*}$. We write $\bar{w}$ as the direction of $w$, i.e. $w/\lVert w\rVert_{2}$.
The first claim we prove is that for given $\{(X\bar{w}_{a_{i}})_{+}\bar{z}_{a_{i}}^{T}\}_{i=1}^{m_{1}}$ and $\{(X\bar{w^{\prime}}_{b_{i}})_{+}\bar{z^{\prime}}_{b_{i}}^{T}\}_{i=1}^{m_{2}}$, consider the conic combination that satisfies

$$ $\sum_{i=1}^{m_{1}}c_{i}(X\bar{w}_{a_{i}})_{+}\bar{z}_{a_{i}}^{T}+\sum_{i=1}^{m_{2}}d_{i}(X\bar{w^{\prime}}_{b_{i}})_{+}\bar{z^{\prime}}_{b_{i}}^{T}=Y^{*},$ $$

for the optimal model fit $Y^{*}$. Then $(\sqrt{c_{i}}\bar{w}_{a_{i}},\sqrt{c_{i}}\bar{z}_{a_{i}})_{i=1}^{m_{1}}\oplus(\sqrt{d_{i}}\bar{w^{\prime}}_{b_{i}},\sqrt{d_{i}}\bar{z^{\prime}}_{b_{i}})_{i=1}^{m_{2}}$ is an optimal solution of ([30](#A7.E30)) when $m_{1}+m_{2}\leq m$.

To see this, we first see that for the dual variable $N^{*}$, $\langle N^{*},(X\bar{w}_{i})_{+}\bar{z}_{i}^{T}\rangle=-\beta$. Suppose $D_{p}=1(Xw_{a_{i}}\geq 0)$ for $i\in[t_{p}]$, the same notation as in the statement of [G.5](#A7.Thmappxproposition5). As $(w_{i},z_{i})_{i=1}^{m}\in\mathcal{S}$, we know $\mathcal{R}((w_{i},z_{i})_{i=1}^{m})=(\lVert V_{i}\rVert_{\mathcal{K}_{i},*})_{i=1}^{P}$. Hence, when we write $V_{p}=c_{p}\bar{V}_{p}$ for some $\bar{V}_{p}\in F(\mathcal{K]_{p},X^{T}D_{p}N^{*},-\beta,\langle,\rangle_{M}})$, we first know that $V_{p}=\sum_{j=1}^{t_{p}}\lVert w_{a_{j}}\rVert_{2}\lVert z_{a_{j}}\rVert_{2}\bar{w}_{a_{j}}\bar{z}_{a_{j}}^{T}$. Also, as $c_{p}=\lVert V_{p}\rVert_{\mathcal{K}_{p},*}=\sum_{j=1}^{t_{p}}\lVert w_{a_{j}}\rVert_{2}\lVert z_{a_{j}}\rVert_{2}$, $\bar{V}_{p}$ is a convex combination of $\bar{w}_{a_{j}}\bar{z}_{a_{j}}^{T}$. Now, let

$$ $\bar{V}_{p}=\sum_{j=1}^{t_{p}}\lambda_{j}\bar{w}_{a_{j}}\bar{z}_{a_{j}}^{T},$ $$

where $\lambda_{j}$ s sum up to 1. We know that $\langle N^{*},D_{p}X\bar{V}_{p}\rangle=-\beta$ and $N^{*}$ satisfy

$$ $\min_{A\in\mathcal{K}_{i}}\langle N^{*},D_{p}XA\rangle\geq-\beta.$ $$

Hence, for all $\bar{w}_{a_{j}}\bar{z}_{a_{j}}^{T}$, we have that

$$ $\langle N^{*},D_{p}X\bar{w}_{a_{j}}\bar{z}_{a_{j}}^{T}\rangle=-\beta,$ $$

for $j\in[t_{p}]$. This implies for all $i\in[m]$, we have that

$$ $\langle N^{*},(X\bar{w}_{i})_{+}\bar{z}_{i}^{T}\rangle=\langle N^{*},(X\bar{w}_{i}^{\prime})_{+}\bar{z}_{i}^{\prime T}\rangle=-\beta.$ $$

Now we are ready to prove the claim. We first know that the regression error is the same, as we have the same model fit $Y^{*}$. The regularization error is given as

$$ $\beta\Big{(}\sum_{i=1}^{m_{1}}c_{i}+\sum_{i=1}^{m_{2}}d_{i}\Big{)}=-\langle N^{*},Y^{*}\rangle.$ $$

Hence, the cost of the problem is the same for any choice of the conic combination, and $(\sqrt{c_{i}}\bar{w}_{a_{i}},\sqrt{c_{i}}\bar{z}_{a_{i}})_{i=1}^{m_{1}}\oplus(\sqrt{d_{i}}\bar{w^{\prime}}_{b_{i}},\sqrt{d_{i}}\bar{z^{\prime}}_{b_{i}})_{i=1}^{m_{2}}$ is optimal when $m_{1}+m_{2}\leq m$.

At last, suppose $m\geq nc+1$. Note that the vectors $\{(Xw_{i})_{+}z_{i}^{T}\}_{i=1}^{m}$ and $\{(Xw_{i}^{\prime})_{+}z_{i}^{\prime T}\}_{i=1}^{m}$are matrices in $nc$ - dimensional subspace. As any conic combination that sums up to $Y^{*}$ makes a solution, we can first prune both solutions to make them linearly independent, and then connect the two using the same idea introduced in [E.1](#A5.Thmappxtheorem1).
∎

###### Corollary G.1 .

Consider the optimization problem in ([9](#S4.E9)). Suppose $m\geq nc+1$ and denote the optimal set of ([9](#S4.E9)) as $\Theta^{*}(m)$. For any $\theta:=(w_{i},z_{i})_{i=1}^{m}\in\mathbb{R}^{(d+c)m}$, there exists a continuous path from $\theta$ to any point $\theta^{*}\in\Theta^{*}(m)$ with nonincreasing loss.

###### Proof.

The proof is identical to that of [Corollary 1](#Thmcorollary1). From [], we know that when $m\geq nc+1$, the vector-valued training problem in ([9](#S4.E9)) has no strict local minimum, i.e. all local minima are global. Now from any $\theta$, move to a local minimum using a path with nonincreasing loss, then the local minimum is global. As $\Theta^{*}(m)$ is connected, we know that we 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 a finite set of fixed possible directions.

###### Theorem G.4 .

([Theorem 5](#Thmtheorem5) of the paper) Consider the training problem

$$ $\min_{m,\{W_{1i},w_{2i},\alpha_{i}\}_{i=1}^{m}}\frac{1}{3}\left(\sum_{i=1}^{m}\lVert W_{1i}\rVert_{F}^{3}+\lVert w_{2i}\rVert_{2}^{3}+|\alpha_{i}|^{3}\right)$ $$

subject to

$$ $\sum_{i=1}^{m}((XW_{1i})_{+}w_{2i})_{+}\alpha_{i}=y.$ $$

Here, $W_{1i}\in\mathbb{R}^{d\times m_{1}},w_{2i}\in\mathbb{R}^{m_{1}}$ and $\alpha_{i}\in\mathbb{R}$ for $i\in[m]$. Then, there are only finitely many possible values of the direction of the columns of $W_{1i}^{*}$. Moreover, the directions are determined by solving the dual problem

$$ $\max_{\lVert W_{1}\rVert_{F}\leq 1,\lVert w_{2}\rVert_{2}\leq 1}|(\nu^{*})^{T}((XW_{1})_{+}w_{2})_{+}|$ $$

###### Proof.

We can see the problem is equivalent to

$$ $\min_{m,\{\|W_{1i}\rVert_{2}\leq 1,\lVert w_{2i}\rVert_{2}\leq 1,\alpha_{i}\}_{i=1}^{m}}\ \sum_{i=1}^{m}|\alpha_{i}|,$ $$

subject to

$$ $\sum_{i=1}^{m}((XW_{1i})_{+}w_{2i})_{+}\alpha_{i}=y,$ $$

from [].
Furthermore, when we write

$$ $\mathcal{Q}_{X}=\Big{\{}((XW_{1})_{+}w_{2})_{+}\ |\ W_{1}\in\mathbb{R}^{d\times m_{1}},w_{2}\in\mathbb{R}^{m_{1}},\lVert W_{1}\rVert_{F}\leq 1,\lVert w_{2}\rVert_{2}\leq 1\Big{\}},$ $$

the problem is equivalent to

$$ $\min\ \ t\geq 0\quad\mathrm{subject}\ \ \mathrm{to}\quad y\in t\ \mathrm{Conv}(\mathcal{Q}_{X}\cup-\mathcal{Q}_{X}).$ $$

Now we find a cone-constrained linear expression of $((XW_{1})_{+}w_{2})_{+}$. Let’s denote $\mathcal{D}=\{D_{i}\}_{i=1}^{P_{1}}$ as the set of all possible arrangement patterns $\mathrm{diag}(1(Xh\geq 0))$ and $\mathcal{D}(m_{1})$ denote all possible $P_{1}\choose m_{1}$ size $m_{1}$ tuples of elements in $\mathcal{D}$. Let’s note $D_{i}(m_{1})=(D_{i1},D_{i2},\cdots D_{im_{1}})$, where $D_{i1},D_{i2},\cdots D_{im_{1}}\in\mathcal{D}$. $i$ runs from 1 to $P_{1}\choose m_{1}$. Also, let’s fix $s\in\{1,-1\}^{m_{1}}$.

Given $D_{i}(m_{1}),s$, we define the set $\mathcal{D^{\prime}}=\{D_{j}^{\prime}\}_{j=1}^{P_{2}(i)}$ as the set of all possible arrangements of $\mathrm{diag}(1(\tilde{X}h\geq 0))$, where $\tilde{X}=[D_{i1}X|D_{i2}X|\cdots|D_{im_{1}}X]\in\mathbb{R}^{n\times m_{1}d}$.

When $D_{i}(m_{1}),s,D_{j}^{\prime}$ are fixed, and $(W_{1})_{\cdot,i}$ (which denote the $i$ - th column of $W_{1}$), $w_{2i}$ are fixed in sets:

$$ $(2D_{ik}-I)X(W_{1})_{\cdot,k}\geq 0,\quad s_{k}w_{2k}\geq 0\quad\forall k\in[m_{1}],$ $$

$$ $(2D_{j}^{\prime}-I)(\sum_{k=1}^{m_{1}}D_{ik}X(W_{1})_{\cdot,k}w_{2k})\geq 0,$ $$

the ReLU expression becomes

$$ $((XW_{1})_{+}W_{2})_{+}=\sum_{k=1}^{m_{1}}D_{j}^{\prime}D_{ik}X(W_{1})_{\cdot,k}w_{2k}.$ $$

In other words, when we denote $\mathcal{K}(D_{i}(m_{1}),s,D_{j}^{\prime})$ as

$$ $\displaystyle\mathcal{K}(D_{i}(m_{1}),s,D_{j}^{\prime})=\Big{\{}(W_{1},w_{2})\ |\ (2D_{ik}-I)X(W_{1})_{\cdot,k}$ $\displaystyle\geq 0,\ \ s_{k}w_{2k}\geq 0\quad\forall k\in[m_{1}],$ $\displaystyle(2D_{j}^{\prime}-I)(\sum_{k=1}^{m_{1}}D_{ik}X(W_{1})_{\cdot,k}w_{2k})\geq 0\Big{\}},$ $$

$$ $\displaystyle\mathcal{Q}_{X}=\bigcup_{i=1}^{P_{1}\choose m_{1}}\bigcup_{s\in\{-1,1\}^{m_{1}}}\bigcup_{j=1}^{P_{2}(i)}\Big{\{}\sum_{k=1}^{m_{1}}D_{j}^{\prime}D_{ik}X(W_{1})_{\cdot,k}w_{2k}\ |\ (W_{1},w_{2})\in$ $\displaystyle\mathcal{K}(D_{i}(m_{1}),s,D_{j}^{\prime}),$ $\displaystyle\lVert W_{1}\rVert_{F}\leq 1,\lVert w_{2}\rVert\leq 1\Big{\}}.$ $$

Now we consider the change of variables, where we write $(W_{1})_{\cdot,k}w_{2k}=v_{k}\in\mathbb{R}^{d}$. The norm constraint becomes $\sum_{k=1}^{m_{1}}\lVert v_{k}\rVert_{2}\leq 1$. To show this, we show that

$$ $\{((W_{1})_{\cdot,k}w_{2k})_{k=1}^{m_{1}}\ |\ \lVert W_{1}\rVert_{F}\leq 1,\lVert w_{2}\rVert_{2}\leq 1\}=\{(v_{k})_{k=1}^{m_{1}}\ |\ \sum_{k=1}^{m_{1}}\lVert v_{k}\rVert_{2}\leq 1\}.$ $$

First, for $\lVert W_{1}\rVert_{F}\leq 1,\lVert w_{2}\rVert_{2}\leq 1$, assume the column weights are $a_{1},a_{2},\cdots a_{m_{1}}$. Then we have $a_{1}^{2}+\cdots a_{m_{1}}^{2}\leq 1$, $w_{21}^{2}+w_{22}^{2}+\cdots+w_{2m_{1}}^{2}\leq 1$, and use Cauchy-Schwartz to see that $\sum_{k=1}^{m_{1}}a_{k}|w_{2k}|\leq 1$. To prove the latter, choose $W_{1}=[v_{1}/\sqrt{\lVert v_{1}\rVert_{2}}|\cdots|v_{m_{1}}/\sqrt{\lVert v_{m_{1}}\rVert_{2}}],w_{2}=[\sqrt{\lVert v_{1}\rVert_{2}},\cdots,\sqrt{\lVert v_{m_{1}}\rVert_{2}}]^{T}$.

With change of variables, the cones are written as

$$ $\displaystyle\mathcal{K}_{v}(D_{i}(m_{1}),s,D_{j}^{\prime})=\Big{\{}(v_{k})_{k=1}^{m_{1}}\ |\ (2D_{ik}-I)s_{k}Xv_{k}$ $\displaystyle\geq 0,\ \ \forall k\in[m_{1}],$ $\displaystyle(2D_{j}^{\prime}-I)\sum_{k=1}^{m_{1}}D_{ik}Xv_{k}\geq 0\Big{\}},$ $$

which is a fixed cone in $\mathbb{R}^{d}$. Hence, $\mathcal{Q}_{X}$ can be rewritten as

$$ $\displaystyle\mathcal{Q}_{X}=\bigcup_{i=1}^{P_{1}\choose m_{1}}\bigcup_{s\in\{-1,1\}^{m_{1}}}\bigcup_{j=1}^{P_{2}(i)}\Big{\{}\sum_{k=1}^{m_{1}}D_{j}^{\prime}D_{ik}Xv_{k}\ |\ (v_{k})_{k=1}^{m_{1}}\in$ $\displaystyle\mathcal{K}_{v}(D_{i}(m_{1}),s,D_{j}^{\prime}),\sum_{k=1}^{m_{1}}\lVert v_{k}\rVert_{2}\leq 1\Big{\}}.$ $$

As a result, we have found a piecewise linear expression of $\mathcal{Q}_{X}$. We know that the problem

$$ $\mathrm{minimize}\ t\quad\mathrm{subject}\ \ \mathrm{to}\quad y\in tC$ $$

has a dual variable $\nu^{*}$ that satisfies: if $y=t^{*}(\sum_{i=1}^{m}\lambda_{i}c_{i})$ for some $c_{i}\in C$, all $c_{i}$ s are minimizers of $(\nu^{*})^{T}c$ subject to $c\in C$. To see this fact, consider the supporting hyperplane on $y$. We can find a vector that satisfies $\langle\nu^{*},y\rangle\leq\langle\nu^{*},t^{*}c\rangle$ for all $c\in C$. Write $y=t^{*}(\sum_{i=1}^{m}\lambda_{i}c_{i})$ and apply inner product with $\nu^{*}$ to see the wanted result. More specifically, we have that $\lambda_{i}\langle\nu^{*},y\rangle\leq\lambda_{i}\langle\nu^{*},t^{*}c_{i}\rangle$ for all $i\in[m]$, and add them to see that the inequalities are actually an equality, and $\langle\nu^{*},y\rangle=\langle\nu^{*},t^{*}c_{i}\rangle$ for all $i\in[m]$.

Hence, noting $C$ as $\mathrm{Conv}(Q_{X}\cup-Q_{X})$, there exists a dual variable $\nu^{*}$ where the optimal $(W_{1},w_{2})$ must lie in the set $\operatorname*{arg\,max}_{\lVert W_{1}\rVert_{F}\leq 1,\lVert w_{2}\rVert_{2}\leq 1}|(\nu^{*})^{T}((XW_{1})_{+}w_{2})_{+}|$. For each constraint set

$$ $(v_{k})_{k=1}^{m_{1}}\in\mathcal{K}_{v}(D_{i}(m_{1}),s,D_{j}^{\prime}),\quad\sum_{k=1}^{m_{1}}\lVert v_{k}\rVert_{2}\leq 1,$ $$

we are optimizing a linear function over this set (as the ReLU expression is a linear function of $(v_{k})_{k=1}^{m_{1}}$). If there exists two different maximizers of the problem $(v_{k})_{k=1}^{m_{1}}$, $(v_{k}^{\prime})_{k=1}^{m_{1}}$, the average of the two will still be in the cone and satisfy the norm constraint strictly. Say $(v_{k}^{\prime\prime})_{k=1}^{m_{1}}$ is the average of the two solutions - the cost function (which is either $(\nu^{*})^{T}\sum_{k=1}^{m_{1}}D_{j}^{\prime}D_{i1}Xv_{k}$ or its negation) value will be the same, but $\sum_{k=1}^{m_{1}}\lVert v_{k}^{\prime\prime}\rVert_{2}<1$. Multiplying $1/\sum_{k=1}^{m_{1}}\lVert v_{k}^{\prime\prime}\rVert_{2}$ leads to a contradiction in the optimality. Hence, for fixed cone $\mathcal{K}_{v}(D_{i}(m_{1}),s,D_{j}^{\prime})$, the optimal $(v_{k})_{k=1}^{m_{1}}$ are fixed. As $v_{k}=(W_{1})_{\cdot,k}w_{2k}$, the direction of the columns of $W_{1}$ are fixed to a finite set of values.
∎

###### Theorem G.1 .

###### Proof.

###### Proposition G.1 .

###### Proof.

###### Proposition G.2 .

###### Proof.

###### Proposition G.3 .

###### Proof.

###### Proposition G.4 .

###### Proof.

###### Proposition G.5 .

###### Proof.

###### Theorem G.2 .

###### Proof.

###### Theorem G.3 .

###### Proof.

###### Corollary G.1 .

###### Proof.

###### Theorem G.4 .

###### Proof.

## Appendix H Additional Discussions

In this section, we discuss the geometrical intuition of the dual optimum, non-unique solutions, and also explain why the assumption in [] might not hold in our case.

The specific problem of interest is interpolating the dataset $\{(-\sqrt{3},1),(\sqrt{3},1)\}$ with a 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 as

$$ $\min_{m,\{w_{i},\alpha_{i}\}_{i=1}^{m}}\frac{1}{2}\Big{(}\sum_{i=1}^{m}\lVert w_{i}\rVert_{2}^{2}+|\alpha_{i}|^{2}\Big{)}$ $$

subject to

$$ $\sum_{i=1}^{m}(\bar{X}w_{i})_{+}\alpha_{i}=y.$ $$

Here, $\bar{X}=\begin{bmatrix}-\sqrt{3}&1\\
\sqrt{3}&1\end{bmatrix}$ and $y=[1,1]^{T}$. The last column of $\bar{X}$ denotes the bias term.

The problem is equivalent to

$$ $\min_{m,\{w_{i},\alpha_{i}\}_{i=1}^{m}}\sum_{i=1}^{m}|\alpha_{i}|,$ $$

subject to

$$ $\sum_{i=1}^{m}(\bar{X}w_{i})_{+}\alpha_{i}=y,\quad\lVert w_{i}\rVert_{2}\leq 1.$ $$

See [] for a similar “scaling trick”.

In other words, when we denote $\mathcal{Q}_{\bar{X}}=\{(\bar{X}u)_{+}\ |\ \lVert u\rVert_{2}\leq 1\}$, the problem becomes []

$$ $\min t\geq 0\quad\mathrm{subject}\ \mathrm{to}\quad y\in t\mathrm{Conv}(\mathcal{Q}_{\bar{X}}\cup-\mathcal{Q}_{\bar{X}}).$ $$

[Figure 9](#A8.F9) shows the shape of $\mathcal{Q}_{\bar{X}}$ and its convex hull.

Figure: (a) $\{Xu\ |\ \lVert u\rVert_{2}\leq 1\}$

One thing to notice is that in [Figure 9(b)](#A8.F9.sf2), the line $x+y=2$ meets with $\mathcal{Q}_{\bar{X}}$ with three points, and the convex hull $\mathrm{Conv}(\mathcal{Q}_{\bar{X}}\cup-\mathcal{Q}_{\bar{X}})$ is a diamond. The intuition of the dual variable is that it is the normal vector of a face where the optimal fit exists. In our case, $y=[1,1]^{T}$ lies on the exact line $x+y=2$. Hence the dual optimum is $\nu^{*}=[1,1]^{T}$. We can also construct different minimum-norm interpolators by linear combinations of the three green points in [Figure 9(b)](#A8.F9.sf2): we can express $y$ by only using the middle point $(1,1)$ - here, the interpolator becomes $y=1$. We can use two points $(2,0)$ and $(0,2)$ to express $(1,1)$ - here, we have another interpolator that has two breakpoints. We can use three points - where there will be infinitely many ways to express $(1,1)$, that leads to a continuum of interpolators.

The assumption in [] that there exists a unique model with zero loss and minimal width does not work here. We can adapt it to the regularized case, and assume that there exists a unique interpolator with minimal width and a solution to

$$ $\min_{m,\{w_{i},\alpha_{i}\}_{i=1}^{m}}\frac{1}{2}\Big{(}\sum_{i=1}^{m}\lVert w_{i}\rVert_{2}^{2}+|\alpha_{i}|^{2}\Big{)}$ $$

subject to

$$ $\sum_{i=1}^{m}(\bar{X}w_{i})_{+}\alpha_{i}=y.$ $$

Here, $\bar{X}=[x\ |\ 1]\in\mathbb{R}^{n\times 2}$. Now choose $x=[-\sqrt{3},\sqrt{3}]$ as before, but choose $y=[1/2,3/2]$. Then, there exist two ways to express $y$ 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]$, we can see that $m^{*}=2$ is minimal. Hence we don’t have uniqueness of the smallest model in this case, and the results in [] will not apply in general.

## Peer Reviews

confidence: 5
contribution: 3
initial_rating: 8
presentation: 4
questions: No questions.
soundness: 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.
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.
weaknesses: Perhaps a deeper discussion on the topological implications of their results would be beneficial.

---

confidence: 2
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. Is there a way to bound or estimate the critical widths $m^*$ and $M^*$ in practice, for instance on real datasets? 
2. In line 186: What does $h$ refer to in $\text{diag}[1 (Xh \geq 0)]$ ?
3. 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.)
4. 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.
5. 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?
6. 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?
soundness: 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. 
- 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.
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. 
The 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. 
This result is extended later to networks with vector-valued outputs, and parallel deep networks of depth 3.
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. 
- 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. 
- 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.

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 3
questions: I wonder if the authors have any comment regarding the weaknesses.
soundness: 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.
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:

* identified the staircase of connectivity that describes how connectivity evolves with width;
* constructed none-unique minimal-norm interpolator by breaking the uniqueness conditions;
* generalized the optimal polytope to the general cone-constrained group LASSO problem and applied it to more complicated architectures.
weaknesses: I have some concerns with the presentation of this work. Specifically:

* If I understand correctly, the convex duality only applies to ReLU networks. This is not emphasized.
* 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.
* 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. 
* The lower half of Figure 2 is not explained.

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 2
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?

2. 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$? 

3. 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?
soundness: 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. 

2. 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.
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.
weaknesses: 1.Although I believe this paper has a solid contribution, I found there's a few part I don't understand the significance:    
- 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?

- 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?

2. 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: 

    - Line 215: and 216, what is the definition of $\mathcal{S}_i$?
    - Line 223: what the definition of "optimal model fit", what is $u_i^*, v_i^*$, and why it is unique?
    - Line 232: the triangle inequality is reversed. Also could you be more specific about the discussion between Liine 229-232?
    - 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? 
    - In equation (7), could you specify the dimension of the variables?

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: Can the authors proofread again the manuscript to eliminate typos, unclear sentences and missing notation?
Can they make the presentation of the result more readable, including relevant results from the Appendix?
Can they integrate the relevant existing literature in the Related Work section?
soundness: 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.
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.
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). 
There are many references to results listed in the Appendix; if relevant, I think it might be better to put them in the main manuscript.
An 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].

[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.

Meta-review: This paper studies the loss landscape of regularized ReLU networks, focusing on the structure of stationary points, the connectivity of optimal solutions and the non uniqueness of optimal solutions. The authors start by considering a two-layer network with scalar output, and characterize the connectivity of the solution for different sizes of the network. Then, they consider extensions to minimal norm interpolation, vector-valued networks, and deep neural networks.

The reviewers found the results insightful (especially the 'staircase of connectivity' phenomenon) and well-integrated in the related literature. The proposed framework based on convex duality is rather general: it does not require large over-parameterization or specific scalings, which is a strong point. At the technical level, the origin of this framework is to be found in earlier work by Pilanci et al., which limits a bit the technical novelty. However, significant effort is required to tackle the settings considered here. All reviewers are positive about the paper, and so am I. Thus, I recommend it to be accepted.

Decision: Accept (Oral)