2306/2306.00119.md

Title: Optimal Sets and Solution Paths of ReLU Networks

URL Source: https://arxiv.org/html/2306.00119

Markdown Content: Back to arXiv

This is experimental HTML to improve accessibility. We invite you to report rendering errors. Use Alt+Y to toggle on accessible reporting links and Alt+Shift+Y to toggle off. Learn more about this project and help improve conversions.

Why HTML? Report Issue Back to Abstract Download PDF 1Introduction 2Convex Reformulations 3The Constrained Group Lasso 4Specialization to Neural Networks 5Experiments 6Conclusion

HTML conversions sometimes display errors due to content that did not convert correctly from the source. This paper uses the following packages that are not yet supported by the HTML conversion tool. Feedback on these issues are not necessary; they are known and are being worked on.

failed: silence failed: centernot

Authors: achieve the best HTML results from your LaTeX submissions by following these best practices.

License: arXiv.org perpetual non-exclusive license arXiv:2306.00119v2 [cs.LG] 19 Jan 2024 Optimal Sets and Solution Paths of ReLU Networks Aaron Mishkin Mert Pilanci Abstract

We develop an analytical framework to characterize the set of optimal ReLU neural networks by reformulating the non-convex training problem as a convex program. We show that the global optima of the convex parameterization are given by a polyhedral set and then extend this characterization to the optimal set of the non-convex training objective. Since all stationary points of the ReLU training problem can be represented as optima of sub-sampled convex programs, our work provides a general expression for all critical points of the non-convex objective. We then leverage our results to provide an optimal pruning algorithm for computing minimal networks, establish conditions for the regularization path of ReLU networks to be continuous, and develop sensitivity results for minimal ReLU networks.

Machine Learning, ICML \WarningFilter

remresetThe remreset package

1Introduction

Neural networks have transformed machine learning. Despite their success, little is known about the global optima for typical non-convex training problems, the solution path of regularized networks, or how to prune networks without degrading the model fit. This is in stark contrast to generalized linear models with ℓ 2 or ℓ 1 penalties; for example, it is well-known that the lasso (Tibshirani, 1996) has a piece-wise linear path (Osborne et al., 2000; Efron et al., 2004), a polyhedral solution set (Tibshirani, 2013), and admits efficient algorithms for computing minimal solutions (Tibshirani, 2013). In this paper, we close the gap by studying neural networks through the lens of convex reformulations.

Figure 1:Convex vs non-convex solution spaces for two-layer ReLU networks. We plot the first feature of three different neurons; the non-convex parameterization maps the compact polytope of solutions for the convex parameterization into a curved manifold.

One of the main challenges of neural networks is non-convexity. For non-convex problems, stationarity of the training objective does not imply optimality of the network weights and so, to the best of our knowledge, no work has been able to derive an analytical expression for the optimal set. Convex reformulations provide a solution by rewriting the non-convex optimization problem as a convex program in a lifted parameter space (Pilanci & Ergen, 2020). We focus on the convex reformulation for two-layer networks with ReLU activation functions and weight decay regularization. The resulting problem is related to the group lasso (Yuan & Lin, 2006) and induces neuron sparsity in the network.

Let 𝑍 ∈ ℝ 𝑛 × 𝑑 be a data matrix and 𝑦 ∈ ℝ 𝑛 associated targets. The prediction function for two-layer ReLU networks is

𝑓 𝑊 1 , 𝑤 2 ⁢ ( 𝑍 )

∑ 𝑖

1 𝑚 ( 𝑍 ⁢ 𝑊 1 ⁢ 𝑖 ) + ⁢ 𝑤 2 ⁢ 𝑖 ,

where 𝑊 1 ∈ ℝ 𝑚 × 𝑑 , 𝑤 2 ∈ ℝ 𝑚 are the weights of the first and second layers, 𝑚 is the number of hidden units, and ( ⋅ ) +

max ⁡ { ⋅ , 0 } is the ReLU activation. Fitting 𝑓 𝑊 1 , 𝑤 2 with convex loss 𝐿 and weight decay ( ℓ 2 ) regularization leads to the standard non-convex optimization problem:

min 𝑊 1 , 𝑤 2 ⁡ 𝐿 ⁢ ( 𝑓 𝑊 1 , 𝑤 2 ⁢ ( 𝑍 ) , 𝑦 ) + 𝜆 2 ⁢ ( ‖ 𝑊 1 ‖ 𝐹 2 + ‖ 𝑤 2 ‖ 2 2 ) ⏟ 𝑅 ⁢ ( 𝑊 1 , 𝑤 2 ) .

(1)

The regularization path or solution function of this training problem is the mapping between the regularization parameter 𝜆 and the set of optimal model weights,

𝒪 * ⁢ ( 𝜆 )

arg ⁢ min 𝑊 1 , 𝑤 2 𝐿 ⁢ ( 𝑓 𝑊 1 , 𝑤 2 ⁢ ( 𝑍 ) , 𝑦 ) + 𝜆 2 ⁢ 𝑅 ⁢ ( 𝑊 1 , 𝑤 2 ) .

(2)

In general, the optimal neural network is not unique and 𝒪 * ⁢ ( 𝜆 ) will be set valued. Indeed, there are always at least 𝑚 ! solutions since any permutation of the hidden units yields an identical model. We call the solution to a ReLU training p-unique when it is unique up to splits and permutations.

We study 𝒪 * by re-writing Equation 1 as an instance of the constrained group lasso (CGL). We make the following contributions by analyzing CGL:

•

We derive an analytical expression for the solution set of two-layer ReLU networks and criteria for solutions to be p-unique (unique up to permutations/splits).

•

We extend this characterization to show that the set of stationary points of a two-layer ReLU model is exactly

𝒞 𝜆

{ ( 𝑊 1 , 𝑤 2 ) : 𝒟 ~ ⊆ 𝒟 𝑍 , 𝑓 𝑊 1 , 𝑤 2 ( 𝑍 )

𝑦 ^ 𝒟 ~ ,

(3)

𝑊 1 ⁢ 𝑖

( 𝛼 𝑖 / 𝜆 ) 1 / 2 ⁢ 𝑣 𝑖 ⁢ ( 𝒟 ~ ) , 𝑤 2 ⁢ 𝑖

𝜉 𝑖 ⁢ ( 𝛼 𝑖 ⁢ 𝜆 ) 1 / 2 ,

𝛼 𝑖 ≥ 0 , 𝑖 ∈ [ 𝑚 ] ∖ 𝒮 𝜆 ⟹ 𝛼 𝑖

0 } ,

where 𝒟 ~ is a set of sub-sampled activation patterns, 𝑦 ^ 𝒟 ~ is the unique optimal model fit using those patterns, and 𝑣 𝑖 ⁢ ( 𝒟 ~ ) are uniquely given by optimal parameters for the dual of the convex reformulation. See Figure 1.

•

We provide an optimal pruning algorithm that can be used to compute minimal models — the smallest-width neural networks which are optimal for a given dataset and regularization parameter — and an intuitive extension for pruning beyond minimal models.

•

We prove that the regularization path of ReLU networks is discontinuous in general and establish sufficient conditions for path to be closed/continuous.

•

We give a simple algorithm for computing the unique ReLU network corresponding to the min-norm model in the convex lifting and, under additional constraint qualifications, develop differential sensitivity results for minimal ReLU networks.

In many cases, we obtain strictly stronger results for gated ReLU networks (Fiat et al., 2019), which correspond directly to an unconstrained group lasso problem (Mishkin et al., 2022). In particular, we give new sufficient conditions for (i) the group lasso to be unique, (ii) global continuity of the group lasso model fit, and (iii) weak differentiability of the solution function for gated ReLU networks.

The paper is structured as follows: we cover related work in Section 1.1 and introduce notation in Section 1.2. Then we provide details for convex reformulations of neural network in Section 2. Section 3 analyzes CGL and Section 4 interprets these results in the specific context of two-layer ReLU networks. Section 5 concludes with experiments.

1.1Related Work

The Lasso and Group Lasso: Our work is most similar to Hastie et al. (2007), who consider homotopy methods, and Tibshirani (2013), who characterize the lasso solution set. Limited results exist beyond the lasso. Tibshirani & Taylor (2011) analyze the generalized lasso, while Yuan & Lin (2006) show the group lasso is piece-wise linear when 𝑋 is orthogonal. Roth & Fischer (2008) partially characterize the group lasso solution set, while Vaiter et al. (2012) derive stability results and the degrees-of-freedom.

Convex Reformulations: Convex reformulations for neural networks have rapidly advanced since Pilanci & Ergen (2020); convolutions (Ergen & Pilanci, 2021b; Gupta et al., 2021), vector-outputs (Sahiner et al., 2021), batch-norm (Ergen et al., 2021), and deeper networks (Ergen & Pilanci, 2021a) have all been explored.

Neural Network Solution Sets: Characterizations of solution sets are largely empirical. Mode connectivity has been studied extensively, Garipov et al. (2018); Draxler et al. (2018). Nguyen (2019); Kuditipudi et al. (2019) attempt to theoretically explain mode connectivity. Sensitivity is connected to differentiable optimization layers (Agrawal et al., 2019) and hypergradient descent (Baydin et al., 2017). We refer to Blalock et al. (2020) for an overview on pruning.

1.2Notation

We use lower-case 𝑎 to denote vectors and upper-case 𝐴 for matrices. For 𝑑 ∈ ℕ , [ 𝑑 ]

{ 1 , … , 𝑑 } . Calligraphic letters 𝒞 denote sets. For a block of indices 𝑏 𝑖 ⊆ [ 𝑑 ] , we write 𝐴 𝑏 𝑖 for the sub-matrix of columns indexed by 𝑏 𝑖 . Similarly, 𝑎 𝑏 𝑖 is the sub-vector indexed by 𝑏 𝑖 . If ℳ is a collection of blocks, then 𝐴 ℳ is the submatrix and 𝑎 ℳ the sub-vector with columns/elements indexed by blocks in the collection. Finally, | ℳ | is cardinality of the union of blocks in ℳ .

2Convex Reformulations

Now we introduce background on convex reformulations. Convex reformulations re-write Equation 1 as a convex program by enumerating the activations a single neuron in the hidden layer can take on for fixed 𝑍 as follows:

𝒟 𝑍

{ 𝐷

diag ⁢ ( 𝟙 ⁢ ( 𝑍 ⁢ 𝑢 ≥ 0 ) ) : 𝑢 ∈ ℝ 𝑑 } .

This set grows as | 𝒟 𝑍 | ≤ 𝑂 ⁢ ( 𝑟 ⁢ ( 𝑛 / 𝑟 ) 𝑟 ) , where 𝑟 := rank ⁢ ( 𝑍 ) (Pilanci & Ergen, 2020). Each “activation pattern” 𝐷 𝑖 ∈ 𝒟 𝑍 is associated with a convex cone,

𝒦 𝑖

{ 𝑢 ∈ ℝ 𝑑 : ( 2 ⁢ 𝐷 𝑖 − 𝐼 ) ⁢ 𝑍 ⁢ 𝑢 ⪰ 0 } .

If 𝑢 ∈ 𝒦 𝑖 , then 𝑢 matches 𝐷 𝑖 , meaning 𝐷 𝑖 ⁢ 𝑍 ⁢ 𝑢

( 𝑍 ⁢ 𝑢 ) + . For any subset 𝒟 ~ ⊆ 𝒟 𝑍 , the convex reformulation is,

min 𝑣 , 𝑤

𝐿 ⁢ ( ∑ 𝐷 𝑖 ∈ 𝒟 ~ 𝐷 𝑖 ⁢ 𝑍 ⁢ ( 𝑣 𝑖 − 𝑢 𝑖 ) , 𝑦 ) + 𝜆 ⁢ ∑ 𝐷 𝑖 ∈ 𝒟 ~ ‖ 𝑣 𝑖 ‖ 2 + ‖ 𝑢 𝑖 ‖ 2

(4)

s.t. 𝑣 𝑖 , 𝑢 𝑖 ∈ 𝒦 𝑖 .

Pilanci & Ergen (2020) prove that this program and Equation 1 are equivalent in the following sense: if 𝒟 ~

𝒟 𝑍 and 𝑚 ≥ 𝑚 * for some 𝑚 * ≤ 𝑛 + 1 , then the two programs have the same optimal value and every solution to the convex program can be mapped to a solution of the non-convex training problem and vice-versa. Given a solution ( 𝑣 * , 𝑢 * ) , optimal weights for the ReLU problem are given by

𝑊 1 ⁢ 𝑖

𝑣 𝑖 * / ‖ 𝑣 𝑖 * ‖ , 𝑤 2 ⁢ 𝑖

‖ 𝑣 𝑖 * ‖

(5)

𝑊 1 ⁢ 𝑗

𝑢 𝑖 * / ‖ 𝑢 𝑖 * ‖ , 𝑤 2 ⁢ 𝑗

− ‖ 𝑢 𝑖 * ‖ ,

where we use the convention that 0 / 0

0 .

In practice, learning with 𝒟 𝑍 is intractable except when the data are low rank. Mishkin et al. (2022) provide refined conditions on 𝒟 ~ which are sufficient for Equation 4 to be equivalent to the non-convex problem, while Wang et al. (2021) show that the minimum of every sub-sampled convex program is a stationary point of the ReLU training problem.

2.1Gated ReLU Networks

An alternative is the gated ReLU activation function,

𝜙 𝑔 ⁢ ( 𝑍 , 𝑢 )

diag ⁢ ( 𝟙 ⁢ ( 𝑍 ⁢ 𝑔 ≥ 0 ) ) ⁢ 𝑍 ⁢ 𝑢 ,

where 𝑔 ∈ ℝ 𝑑 is a “gate” vector, which is also optimized. The gated ReLU activation modifies the ReLU activation to decouple the thresholding operator from the neuron weights. Two-layer gated ReLU networks predict as follows:

ℎ 𝑊 1 , 𝑤 2 ⁢ ( 𝑍 )

∑ 𝑖

1 𝑚 𝜙 𝑔 𝑖 ⁢ ( 𝑍 , 𝑊 1 ⁢ 𝑖 ) ⁢ 𝑤 2 ⁢ 𝑖 .

(6)

Mishkin et al. (2022) show that this gated ReLU neural network has the convex reformulation,

min 𝑢 ⁡ 𝐿 ⁢ ( ∑ 𝐷 𝑖 ∈ 𝒟 ~ 𝐷 𝑖 ⁢ 𝑍 ⁢ 𝑤 𝑖 , 𝑦 ) + 𝜆 ⁢ ∑ 𝐷 𝑖 ∈ 𝒟 ~ ‖ 𝑤 𝑖 ‖ 2 ,

(7)

where decoupling the activations from the neuron weights allows 𝑢 𝑖 , 𝑣 𝑖 ∈ 𝒦 𝑖 to be merged. The solution mapping for 𝑤 * and conditions for for the convex program to be equivalent to Equation 6 are similar to the ReLU case.

3The Constrained Group Lasso

In this section, we develop properties of CGL, a generalized linear model which captures both the convex ReLU and convex gated ReLU programs. Let ℬ

{ 𝑏 1 , … , 𝑏 𝑚 } be a disjoint partition of the feature indices [ 𝑑 ] . Given regularization parameter 𝜆 ≥ 0 , CGL solves the program:

𝑝 * ⁢ ( 𝜆 )

min 𝑤

𝐹 𝜆 ⁢ ( 𝑤 ) := 1 2 ⁢ ‖ 𝑋 ⁢ 𝑤 − 𝑦 ‖ 2 2 + 𝜆 ⁢ ∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 𝑏 𝑖 ‖ 2

(8)

s.t. 𝐾 𝑏 𝑖 ⊤ ⁢ 𝑤 𝑏 𝑖 ≤ 0 ⁢  for all  ⁢ 𝑏 𝑖 ∈ ℬ ,

where 𝐾 𝑏 𝑖 ∈ ℝ | 𝑏 𝑖 | × 𝑎 𝑏 𝑖 . Solutions to Equation 8 are block sparse when 𝜆 is sufficiently large, meaning 𝑤 𝑏 𝑖

0 for a subset of blocks. This is similar to the feature sparsity given by the lasso, to which CGL naturally reduces when 𝑏 𝑖

{ 𝑖 } and 𝐾 𝑏 𝑖

0 for each 𝑏 𝑖 ∈ ℬ . Although we consider squared-error, our results generalize to strictly convex losses — see Appendix C for comments.

The convex reformulations introduced in the previous section are instances of CGL using the basis function 𝑋

[ 𝐷 1 ⁢ 𝑍 ⁢ … ⁢ 𝐷 𝑝 ⁢ 𝑍 ] , where 𝑝

| 𝒟 ~ 𝑍 | . For gated ReLU models, 𝐾 𝑏 𝑖

0 while ReLU models set 𝐾 𝑏 𝑖

− 𝑍 ⊤ ⁢ ( 2 ⁢ 𝐷 𝑖 − 𝐼 ) . For both problems, block sparsity from the group ℓ 1 penalty induces neuron sparsity in the final solution.

Our goal is to characterize the solution function of CGL,

𝒲 * ⁢ ( 𝜆 ) := arg ⁢ min 𝑤 : 𝐾 𝑏 𝑖 ⊤ ⁢ 𝑤 𝑏 𝑖 ≤ 0 𝐹 𝜆 ⁢ ( 𝑤 )

For a general data matrix, 𝐹 𝜆 is not strictly convex and CGL may admit multiple solutions — these correspond to networks which are not related by permutation. As such, 𝒲 * is a point-to-set map and we must use a criterion to define a function; for instance, the min-norm solution mapping

𝑤 * ( 𝜆 )

arg ⁢ min { ∥ 𝑤 ∥ 2 : 𝑤 ∈ 𝒲 * ( 𝜆 ) } ,

defines a function for all 𝜆 ≥ 0 .

Now we introduce notation that will be used throughout this section. Let 𝑦 ^ ⁢ ( 𝜆 )

𝑋 ⁢ 𝑤 for 𝑤 ∈ 𝒲 * ⁢ ( 𝜆 ) denote the optimal model fit, which is the same for any choice of optimal 𝑤 (Lemma A.1). Similarly, define the optimal residual 𝑟 ⁢ ( 𝜆 ) := 𝑦 − 𝑦 ^ ⁢ ( 𝜆 ) and 𝑐 𝑏 𝑖 ⁢ ( 𝜆 ) := 𝑋 𝑏 𝑖 ⊤ ⁢ 𝑟 ⁢ ( 𝜆 ) as the correlation vector for block 𝑏 𝑖 . We write 𝑐 ∈ ℝ 𝑑 for the concatenation of these block-vectors. Finally, let 𝜌 𝑏 𝑖 be the dual parameters for the constraint 𝐾 𝑏 𝑖 ⊤ ⁢ 𝑤 𝑏 𝑖 ≤ 0 , 𝜌 their concatenation, and 𝐾 the block-diagonal matrix with blocks given by 𝐾 𝑏 𝑖 .

The Lagrangian associated with Equation 8 is

ℒ ⁢ ( 𝑤 , 𝜌 )

1 2 ⁢ ‖ 𝑋 ⁢ 𝑤 − 𝑦 ‖ 2 2 + 𝜆 ⁢ ∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 𝑏 𝑖 ‖ 2 + ⟨ 𝐾 ⁢ 𝜌 , 𝑤 ⟩ .

(9)

The constraints are linear, strong duality attains if feasibility holds, and the necessary and sufficient conditions for primal-dual pair ( 𝑤 , 𝜌 ) to be optimal are the KKT conditions:

𝑋 𝑏 𝑖 ⊤ ⁢ ( 𝑋 ⁢ 𝑤 − 𝑦 ) + 𝐾 𝑏 𝑖 ⁢ 𝜌 𝑏 𝑖 + 𝑠 𝑏 𝑖

0

(10)

𝐾 𝑏 𝑖 ⊤ ⁢ 𝑤 𝑏 𝑖
≤ 0

[ 𝜌 𝑏 𝑖 ] 𝑗 ⋅ [ 𝐾 𝑏 𝑖 ] 𝑗 ⊤ ⁢ 𝑤 𝑏 𝑖

0 ∀ 𝑗 ∈ [ 𝑎 𝑏 𝑖 ]

𝜌 𝑏 𝑖

≥ 0 ,

where 𝑠 𝑏 𝑖 ∈ ∂ 𝜆 ⁢ ‖ 𝑤 𝑏 𝑖 ‖ 2 . Since the KKT conditions hold for every combination of optimal primal-dual pair (Boyd & Vandenberghe, 2014), we always use the min-norm dual optimal parameter 𝜌 * with no loss of generality. To simplify our notations, we define 𝑣 𝑏 𝑖 := 𝑐 𝑏 𝑖 − 𝐾 𝑏 𝑖 ⁢ 𝜌 𝑏 𝑖 * . In what follows, all proofs are deferred to Appendix A.

3.1Describing the Optimal Set

Stationary of the Lagrangian implies the equicorrelation set

ℰ 𝜆

{ 𝑏 𝑖 ∈ ℬ : ‖ 𝑣 𝑏 𝑖 ‖ 2

𝜆 } .

contains all blocks which may be active for fixed 𝜆 . That is, the active set 𝒜 𝜆 ⁢ ( 𝑤 )

{ 𝑏 𝑖 : 𝑤 𝑏 𝑖 ≠ 0 } satisfies 𝒜 𝜆 ⁢ ( 𝑤 ) ⊆ ℰ 𝜆 for every 𝑤 ∈ 𝒲 * ⁢ ( 𝜆 ) . However, not all blocks in ℰ 𝜆 may be non-zero for some solution. Thus, we define

𝒮 𝜆

{ 𝑏 𝑖 ∈ ℬ : ∃ 𝑤 ∈ 𝒲 * ⁢ ( 𝜆 ) , 𝑤 𝑏 𝑖 ≠ 0 } ,

which is the set of blocks supported by some solution.

Our first result combines KKT conditions with uniqueness of 𝑦 ^ ⁢ ( 𝜆 ) to characterize the solution set for fixed 𝜆

0 . {restatable}propositionsolFnCGL Fix 𝜆

0 . The optimal set for the CGL problem is given by

𝒲 * ( 𝜆 )

{
𝑤 ∈ ℝ 𝑑 : ∀ 𝑏 𝑖 ∈ 𝒮 𝜆 , 𝑤 𝑏 𝑖

𝛼 𝑏 𝑖 ⁢ 𝑣 𝑏 𝑖 , 𝛼 𝑏 𝑖 ≥ 0 ,

(11)

∀ 𝑏 𝑗 ∈ ℬ ∖ 𝒮 𝜆 , 𝑤 𝑏 𝑗

0 , 𝑋 𝑤

𝑦 ^ }

Since this characterization is implicit due to the dependence on 𝒮 𝜆 , we also give an alternative and explicit construction in Proposition A.2, which shows that when 𝐾

0 we may replace 𝒮 𝜆 with ℰ 𝜆 ; We prefer Section 3.1 to Proposition A.2 since it better mirrors this simpler setting. However, Proposition A.2 can be substituted wherever desired.

Now that we know “shape” of the solution set, it is possible to obtain simple conditions for existence of a unique solution. As an immediate consequence of Section 3.1, the solution map is a subset of directions in Null ⁢ ( 𝑋 ℰ 𝜆 ) .

Corollary 3.1.

If 𝑤 , 𝑤 ′ ∈ 𝒲 * ⁢ ( 𝜆 ) and 𝑧 ′

𝑤 − 𝑤 ′ , then

𝑧 ℰ 𝜆 ′ ∈ 𝒩 𝜆 := 𝑁𝑢𝑙𝑙 ⁢ ( 𝑋 ℰ 𝜆 ) ∩ { 𝑧 ℰ 𝜆 : ∀ 𝑏 𝑖 ∈ ℰ 𝜆 , 𝑧 𝑏 𝑖

𝛼 𝑏 𝑖 ⁢ 𝑣 𝑏 𝑖 } .

As a result, the group lasso solution is unique if 𝒩 𝜆

{ 0 } .

Corollary 3.1 extends a similar result for the lasso to CGL (Tibshirani, 2013, Eq. 9) and implies the solution is unique for all 𝜆 ≥ 0 if the columns of 𝑋 are linearly independent. The corollary also provides a simple check for primal uniqueness given a primal-dual solution pair.

{restatable}

lemmauniqueCGL Fix 𝜆

0 . The solution to CGL problem is unique if and only if { 𝑋 𝑏 𝑖 ⁢ 𝑣 𝑏 𝑖 } 𝒮 𝜆 are linearly independent.

Note that a dual solution 𝜌 is necessary to compute 𝑣 in general; By uniformizing over 𝑣 𝑏 𝑖 , we obtain a stronger condition that can be checked whenever ℰ 𝜆 is known, yet is still weaker than linear independence of the columns of 𝑋 .

Corollary 3.2.

If the columns of 𝑋 ℰ 𝜆 are linearly independent, then the CGL problem has a unique solution.

Finally, we consider the special case when there are no constraints and 𝐾

0 . In this setting, 𝑣 𝑏 𝑖

𝑐 𝑏 𝑖 — the dual parameters are trivially zero — and we can provide a global condition which is much stronger than linear independence.

{restatable}

propositionGGP[Group General Position] Suppose for every ℰ ⊆ ℬ , | ℰ | ≤ 𝑛 + 1 , there do not exist unit vectors 𝑧 𝑏 𝑖 ∈ ℝ | 𝑏 𝑖 | such that for any 𝑗 ∈ ℰ ,

𝑋 𝑏 𝑗 ⁢ 𝑧 𝑏 𝑗 ∈ affine ⁢ ( { 𝑋 𝑏 𝑖 ⁢ 𝑧 𝑏 𝑖 : 𝑏 𝑖 ∈ ℰ ∖ 𝑏 𝑗 } ) .

Then the group lasso solution is unique for all 𝜆

0 . We call this uniqueness condition group general position (GGP) because it naturally extends general position to groups of vectors. General position is itself an extension of affine independence and is sufficient for the lasso solution to be unique (Tibshirani, 2013). GGP is strictly weaker than linear independence of the columns of 𝑋 , but neither implies nor is implied by general position (Proposition A.3).

3.2Computing Dual Optimal Parameters

The main difficulty of Corollary 3.1 is that knowledge of a dual optimal parameter is required to check if a unique solution exists. A dual optimal parameter is also required to fully leverage our characterization of the optimal set. As such, now we turn to computing optimal dual parameters.

We give one Lagrange dual problem for CGL in Lemma A.4. A nice feature of this dual problem is 𝑣 𝑏 𝑖 attains an alternative interpretation as dual variable. However, evaluating the dual requires computing ( 𝑋 ⊤ ⁢ 𝑋 ) + , which may be difficult even if 𝑋 is structured, as in the convex ReLU program. Instead, we focus on computing 𝜌 given a primal solution.

Let 𝑤 ∈ 𝒲 * ⁢ ( 𝜆 ) . If 𝑤 𝑏 𝑖 ≠ 0 , then KKT conditions imply

𝐾 𝑏 𝑖 ⁢ 𝜌 𝑏 𝑖

𝑐 𝑏 𝑖 − 𝜆 ⁢ 𝑤 𝑏 𝑖 ‖ 𝑤 𝑏 𝑖 ‖ 2 ,

(12)

so that the “dual fit” 𝑑 ^ 𝑏 𝑖

𝐾 𝑏 𝑖 ⁢ 𝜌 𝑏 𝑖 is easily computed. Recovering the dual parameter is a linear feasibility problem:

𝜌 𝑏 𝑖 ∈ { 𝜌 𝑏 𝑖 ≥ 0 : 𝐾 𝑏 𝑖 ⁢ 𝜌 𝑏 𝑖

𝑑 ^ 𝑏 𝑖 } .

(13)

If 𝑤 𝑏 𝑖

0 , then complementary slackness is trivially satisfied and we compute the min-norm dual parameter by solving the following program:

min ⁡ { ‖ 𝜌 𝑏 𝑖 ‖ 2 : ‖ 𝑐 𝑏 𝑖 − 𝐾 𝑏 𝑖 ⁢ 𝜌 𝑏 𝑖 ‖ 2 ≤ 𝜆 , 𝜌 𝑏 𝑖 ≥ 0 } .

(14)

In general, however, we only need some dual optimal parameter for our results to hold; thus, is is typically easier to find 𝜌 by solving the following non-negative regression:

𝜌 𝑏 𝑖

arg ⁢ min { ∥ 𝐾 𝑏 𝑖 𝜌 𝑏 𝑖 − 𝑐 𝑏 𝑖 ∥ 2 2 : 𝜌 𝑏 𝑖 ≥ 0 } .

(15)

See Proposition A.5 for details.

3.3Minimal Solutions and Optimal Pruning

Often we want the most parsimonious solution, i.e. the one using the fewest feature groups. We say a primal solution 𝑤 is minimal if there does not exist 𝑤 ′ ∈ 𝒲 * ⁢ ( 𝜆 ) such that 𝒜 𝜆 ⁢ ( 𝑤 ′ ) ⊊ 𝒜 𝜆 ⁢ ( 𝑤 ) . Building on the previous section, we start with a sufficient condition for 𝑤 to be minimal. {restatable}propositionminimalSols For 𝜆

0 , 𝑤 ∈ 𝒲 * ⁢ ( 𝜆 ) is minimal if and only if the vectors { 𝑋 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 } 𝒜 ⁢ ( 𝑤 ) are linearly independent.

Linear independence of { 𝑋 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 } 𝒜 ⁢ ( 𝑤 ) also identifies 𝑤 as a vertex of 𝒲 * ⁢ ( 𝜆 ) (Bertsekas, 2009), meaning minimal models are exactly the extreme points of the optimal set. Combining this characterization with our condition for uniqueness of a solution (Corollary 3.1) shows that minimal solutions are the only solution on their support.

Corollary 3.3.

Suppose 𝑤 is a minimal solution. Then 𝑤 is the unique solution with support 𝒜 𝜆 ⁢ ( 𝑤 ) .

If 𝑋 satisfies group dependence (Definition A.7), then all minimal solutions have the same number of active blocks.

{restatable}

propositionminimalSolCharacterization Let 𝒱

Span ⁢ ( { 𝑋 𝑏 𝑖 ⁢ 𝑤 ¯ 𝑏 𝑖 } ) for 𝑤 ¯ ∈ 𝒲 * ⁢ ( 𝜆 ) . If 𝑋 satisfies group dependence, then every minimal solution has 𝑐

dim ⁢ ( 𝒱 ) active blocks.

Algorithm 1 Optimal Solution Pruning   Input: data matrix 𝑋 , solution 𝑤 .    𝑘 ← 0 .    𝑤 𝑘 ← 𝑤 .   while  ∃ 𝛽 ≠ 0 s.t. ∑ 𝑏 𝑖 ∈ 𝒜 𝜆 ⁢ ( 𝑤 𝑘 ) 𝛽 𝑏 𝑖 ⁢ 𝑋 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 𝑘

0  do       𝑏 𝑖 𝑘 ← arg ⁢ max 𝑏 𝑖 { | 𝛽 𝑏 𝑖 | : 𝑏 𝑖 ∈ 𝒜 𝜆 ( 𝑤 𝑘 ) }       𝑡 𝑘 ← 1 / | 𝛽 𝑏 𝑖 𝑘 |       𝑤 𝑘 + 1 ← 𝑤 𝑘 ⁢ ( 1 − 𝑡 𝑘 ⁢ 𝛽 𝑏 𝑖 )       𝑘 ← 𝑘 + 1   end while   Output: final weights 𝑤 𝑘

Algorithm 1 gives a procedure which, starting from any optimal solution 𝑤 , computes a optimal model with minimal support in 𝑂 ( ( 𝑛 3 𝑙 + 𝑛 𝑑 ) time, where 𝑙 is the number active blocks in 𝑤 (see Proposition A.6). Moreover, if the blocks of 𝑋 satisfy a regularity condition, then starting model has no affect on the cardinality of the minimal solution found. Our algorithm can also be used to verify a minimal solution, since if 𝑤 minimal then it is unique on its support and Algorithm 1 must return 𝑤 immediately. This procedure also implies the existence of at least one minimal solution.

Corollary 3.4.

There exists 𝑤 ∈ 𝒲 * ⁢ ( 𝜆 ) for which the vectors { 𝑋 𝑏 𝑖 ⁢ 𝑤 ⁢ ( 𝜆 ) : 𝑏 𝑖 ∈ 𝒜 ⁢ ( 𝑤 ) } are linearly independent.

Corollary 3.4 will be useful tool later when we study sensitivity of the model fit to perturbations in 𝑦 and 𝜆 .

A disadvantage of Algorithm 1 is that it cannot continue beyond a minimal solution. However, minimal models may still be quite large. We can perform approximate pruning in such cases using the least squares fit to approximate 𝛽 ,

𝛽 ~

arg ⁢ min ‖ 𝐴 ⁢ 𝛽 − 𝑋 𝑏 𝑗 ⁢ 𝑤 𝑏 𝑗 ‖ 2 2 ,

where 𝐴

[ 𝑋 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 ] 𝒜 𝜆 ∖ 𝑏 𝑗 and 𝑏 𝑗 ∈ 𝒜 𝜆 is chosen randomly. Using 𝛽 ~ in Algorithm 1 is optimal when { 𝑋 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 } 𝒜 𝜆 are dependent and chooses the update parameters to minimize degradation of the model fit otherwise.

3.4Continuity of the Solution Path

A major concern when learning with regularizers is how to tune the parameter 𝜆 . Typical strategies like grid-search on the (cross) validation loss are effective only if the solution function satisfies basic continuity properties. For example, if 𝒲 * is single-valued but discontinuous in 𝜆 , then the sample complexity of grid-search can be made arbitrarily poor by “hiding” the optimal 𝜆 in a discontinuity (Nesterov et al., 2018, Sec. 1.1). In this section, we justify grid-search for CGL by proving several continuity properties of the solution function, particularly when the solution is unique. We start with basic definitions of continuity for point-to-set maps.

Definition 3.5 (Closed).

𝑇 : 𝒳 → 2 𝒵 is closed if { 𝑥 𝑘 } ⊂ 𝒳 , 𝑥 𝑘 → 𝑥 ¯ and 𝑧 𝑘 ∈ 𝑇 ⁢ ( 𝑥 𝑘 ) , 𝑧 𝑘 → 𝑧 ¯ implies 𝑧 ¯ ∈ 𝑇 ⁢ ( 𝑥 ¯ ) .

Definition 3.6 (Open).

𝑇 : 𝒳 → 2 𝒵 is open if { 𝑥 𝑘 } ⊂ 𝒳 , 𝑥 𝑘 → 𝑥 ¯ and 𝑧 ¯ ∈ 𝑇 ⁢ ( 𝑥 ¯ ) , implies there exists 𝑘 ′ ∈ ℕ , 𝑧 𝑘 ∈ 𝑇 ⁢ ( 𝑥 𝑘 ) for 𝑘 ≥ 𝑘 ′ , such that 𝑧 𝑘 → 𝑧 ¯ .

We say that 𝑇 is continuous if it is both closed and open. If 𝑇 ⁢ ( 𝑥 ) is a singleton for all 𝑥 ∈ 𝒳 , then openness/closedness are equivalent and imply continuity. We start with (functional) continuity of the optimal objective.

{restatable}

propositionvalueContinuityCGL 𝜆 ↦ 𝑝 * ⁢ ( 𝜆 ) is continuous for all 𝜆 ≥ 0 .

While standard sensitivity results imply that 𝒲 * is closed, unfortunately openness is not possible in the general setting.

{restatable}

propositionmapContinuityCGL While 𝒲 * is closed on ℝ + , it is open if only if 𝑋 is full column rank. However, if the solution is unique on Λ ⊂ ℝ + , then 𝒲 * is open at every 𝜆 ∈ Λ .

As a corollary of Definition 3.6, 𝒲 * is open on ℝ + if and only if 𝑋 is full column rank. Continuity of 𝒲 * is impossible in general because, as Hogan (1973) shows, openness is a local stability property; since 𝒲 * ⁢ ( 0 ) is unbounded, many “unstable” solutions exist at 𝜆

0 which are not limit points of other solutions. Continuity of the unique solution path is an immediate corollary of Definition 3.6.

Corollary 3.7.

If the CGL solution is unique on an interval Λ ⊂ ℝ + , then it is also continuous on Λ .

In particular, if 𝐾

0 and GGP holds, then the group lasso solution is continuous for all 𝜆 > 0 . We can strengthen our continuity results when 𝐾 𝑏 𝑖

0 in another way: by analyzing the dual of the group lasso problem, we extend continuity from 𝑝 * to the optimal model fit.

{restatable}

propositionmodelFitContinuity If 𝐾

0 , then 𝑦 ^ ⁢ ( 𝜆 ) is continuous on ℝ + and the penalty ∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 𝑏 𝑖 ⁢ ( 𝜆 ) ‖ 2 is continuous for 𝜆

0 .

3.5The Min-Norm Path

Now we turn our attention to the min-norm solution path. Min-norm solutions are typically used in under-determined problems since the norm of the solution is connected to generalization (Neyshabur et al., 2015; Gunasekar et al., 2017). Furthermore, the min-norm solution is a function of 𝜆 , unlike 𝒲 * . Throughout this section, 𝒜 𝜆 *

𝒜 𝜆 ⁢ ( 𝑤 * ) denotes the active set of the min-norm solution.

Unfortunately, studying the min-norm path immediately encounters a surprising difficulty: as opposed to least-squares problems or the lasso (see Tibshirani (2013)), the min-norm solution may not lie in the row space of the active set.

{restatable}

propositionrowCE Suppose 𝐾 𝑏 𝑖

0 . There exists ( 𝑋 , 𝑦 ) and 𝜆

0 such that 𝑤 𝒜 𝜆 * * ⁢ ( 𝜆 ) ∉ Row ⁢ ( 𝑋 𝒜 𝜆 * ) .

Since the min-norm solution is not given by projecting onto Row ⁢ ( 𝑋 𝒜 𝜆 * ) , how can we compute and study it? Again, our characterization for the solution set provides a way forward.

{restatable}

propositionminNormProgram Let 𝜆

0 and consider the program:

𝛼 *

arg ⁢ min 𝛼 ≥ 0 ‖ 𝛼 ‖ 2 2 ⁢  s.t. ⁢ ∑ 𝑏 𝑖 ∈ 𝒮 𝜆 𝛼 𝑏 𝑖 ⁢ 𝑋 𝑏 𝑖 ⁢ 𝑣 𝑏 𝑖

𝑦 ^ .

(16)

Then the min-norm solution is given by 𝑤 𝑏 𝑖 *

𝛼 𝑏 𝑖 * ⁢ 𝑣 𝑏 𝑖 .

Equation 16 is a quadratic program (QP) that can be solved with off-the-shelf software like cvxpy (Diamond & Boyd, 2016). If | ℬ | and 𝑑 are large, this QP may be too expensive to handle directly. In such situations, we propose to the solve the following elastic-net-type problem

min 𝑤

1 2 ⁢ ‖ 𝑋 ⁢ 𝑤 − 𝑦 ‖ 2 2 + 𝜆 ⁢ ∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 𝑏 𝑖 ‖ 2 + 𝛿 2 ⁢ ‖ 𝑤 ‖ 2 2

(17)

s.t. 𝐾 𝑏 𝑖 ⊤ ⁢ 𝑤 𝑏 𝑖 ≤ 0 ⁢  for all  ⁢ 𝑏 𝑖 ∈ ℬ .

This ℓ 2 -penalized CGL problem is equivalent to CGL with modified dataset ( 𝑋 ~ , 𝑦 ~ ) (Lemma A.13). Since the optimization problem is strongly convex ( 𝑋 ~ is full column rank), invoking Definition 3.6 implies the solution 𝑤 𝛿 ⁢ ( 𝜆 ) is continuous for all 𝜆 ≥ 0 . Moreover, as 𝛿 → 0 , the penalized solution converges to the min-norm solution to CGL. {restatable}propositionpenConvergence The solution to the ℓ 2 -penalized problem converges to the min-norm solution as 𝛿 → 0 . That is,

lim 𝛿 → 0 𝑤 𝛿 ⁢ ( 𝜆 )

𝑤 * ⁢ ( 𝜆 ) .

Uniqueness and continuity of the solution path for the penalized CGL problem mean we may prefer to solve Problem (17) with small 𝛿 > 0 when tuning 𝜆 . Section 3.5 guarantees that the bias induced by 𝛿 will be small and a polishing step with 𝛿

0 can always be used. Finally, non-zero 𝛿 ensures the objective is strongly convex, meaning we can use linearly convergent methods to solve the problem.

3.6Sensitivity

Now we move onto the problem of sensitivity of a solution 𝑤 ∈ 𝒲 * ⁢ ( 𝜆 , 𝑦 ) to perturbations, either in 𝜆 or the targets 𝑦 . The main tool for measuring such perturbations are the gradients, for example ∇ 𝜆 𝑤 ⁢ ( 𝜆 , 𝑦 ) . However, since the solution path of the group lasso is non-smooth, we must cope with the fact that gradients are not available everywhere.

We show that the gradients of minimal solutions exist almost everywhere under additional constraint qualifications (CQs). We do so by considering a reduced problem and showing that the solution to this reduced problem is exactly 𝑤 𝒜 𝜆 . Define the reduced problem as follows:

min 𝑤 𝒜 𝜆

1 2 ⁢ ‖ 𝑋 𝒜 𝜆 ⁢ 𝑤 𝒜 𝜆 − 𝑦 ‖ 2 2 + 𝜆 ⁢ ∑ 𝑏 𝑖 ∈ 𝒜 𝜆 ‖ 𝑤 𝑏 𝑖 ‖ 2

(18)

s.t. 𝐾 𝒜 𝜆 ⊤ ⁢ 𝑤 𝒜 𝜆 ≤ 0

If 𝒜 𝜆 ⁢ ( 𝑤 ) is the support of a minimal solution, then 𝑤 is the only solution with support 𝒜 𝜆 and Equation 18 can be used to compute the unique active weights. {restatable}propositionconstraintReduced Let 𝑤 ∈ 𝒲 * ⁢ ( 𝜆 , 𝑦 ) be minimal. The active blocks 𝑤 𝒜 𝜆 are the unique solution to Problem (18). We use this fact to obtain a local solution function for CGL using the implicit function theorem. Given a solution 𝑤 , let

ℬ ⁢ ( 𝑤 )

⋃ 𝑏 𝑖 ∈ 𝒜 𝜆 { 𝑗 ∈ [ 𝑎 𝑏 𝑖 ] : [ 𝐾 𝑏 𝑖 ] 𝑗 ⊤ ⁢ 𝑤 𝑏 𝑖

0 } ,

be the active constraints. We now need two classical CQs.

Definition 3.8 (LICQ).

𝑤 ∈ 𝒲 * ⁢ ( 𝜆 , 𝑦 ) satisfies linear independence CQ if { [ 𝐾 ] 𝑗 : 𝑗 ∈ ℬ ⁢ ( 𝑤 ) } are linearly independent.

Definition 3.9 (SCS).

Primal solution 𝑤 ∈ 𝒲 * ⁢ ( 𝜆 ) satisfies strict complementary slackness if there exists a dual optimal parameter 𝜌 such that [ 𝜌 ] 𝑗

0 for every 𝑗 ∈ ℬ .

Now we can state our main differential sensitivity result.

{restatable}

propositionlocalSolFn Let 𝑤 ∈ 𝒲 * ⁢ ( 𝜆 ¯ , 𝑦 ¯ ) be minimal and suppose 𝑤 satisfies LICQ on the active set 𝒜 𝜆 and SCS on the equicorrelation set ℰ 𝜆 . Then 𝑤 has a locally continuous solution function ( 𝜆 , 𝑦 ) ↦ 𝑤 ⁢ ( 𝜆 , 𝑦 ) . Moreover, if

𝐷

[ 𝑋 𝒜 𝜆 ⊤ ⁢ 𝑋 𝒜 𝜆 + 𝑀 ⁢ ( 𝑤 ¯ )

𝐾 𝒜 𝜆

𝜌 ¯ 𝒜 𝜆 ⊙ 𝐾 𝒜 𝜆

diag ⁢ ( 𝐾 𝒜 𝜆 ⊤ ⁢ 𝑤 ¯ 𝒜 𝜆 ) ] ,

where ⊙ is the element-wise product, 𝑢 𝑏 𝑖

𝑤 𝑏 𝑖 ‖ 𝑤 𝑏 𝑖 ‖ 2 , 𝑢 is the concatenation of these vectors, and 𝑀 is block-diagonal projection matrix in Equation 26, then the Jacobians of 𝑤 ⁢ ( 𝜆 ¯ , 𝑦 ¯ ) with respect to 𝜆 and 𝑦 are given as follows:

∇ 𝜆 𝑤 ⁢ ( 𝜆 ¯ , 𝑦 ¯ )

− [ 𝐷 − 1 ] 𝒜 𝜆 ⁢ 𝑢 𝒜 𝜆 ⁢ ∇ 𝑦 𝑤 ⁢ ( 𝜆 ¯ , 𝑦 ¯ )

[ 𝐷 − 1 ] 𝒜 𝜆 ⁢ 𝑋 𝒜 𝜆 ⊤ ,

where [ 𝐷 𝒜 𝜆 − 1 ] 𝒜 𝜆 is the | 𝒜 𝜆 | × | 𝒜 𝜆 | dimensional leading principle submatrix of 𝐷 .

4Specialization to Neural Networks Algorithm 2 Approximate ReLU Pruning   Input: data matrix 𝑍 , weights 𝑊 1 , 𝑤 2 , score function 𝑠 .    𝑚 ← | 𝒜 𝜆 ⁢ ( 𝑊 1 ) |    ( 𝑊 1 0 , 𝑤 2 0 ) ← ( 𝑊 1 , 𝑤 2 ) .    𝑞 𝑖 0 ← ( 𝑋 ⁢ 𝑊 1 ⁢ 𝑖 0 ) + ⁢ 𝑤 2 0   for  𝑘

0 ⁢  to  ⁢ 𝑚 − 1  do       𝑗 𝑘

arg ⁢ min 𝑖 ∈ 𝒜 𝜆 ⁢ ( 𝑊 1 ⁢ 𝑖 𝑘 ) 𝑠 ⁢ ( 𝑊 1 ⁢ 𝑖 𝑘 )       𝛽 𝑘

arg ⁢ min 𝛽 ‖ ∑ 𝑖 ≠ 𝑗 𝑘 𝛽 𝑖 ⁢ 𝑞 𝑖 𝑘 − 𝑞 𝑗 𝑘 𝑘 ‖ 2 2       𝑖 𝑘 ← arg ⁢ max 𝑖 { | 𝛽 𝑖 | : 𝑖 ∈ 𝒜 𝜆 ( 𝑊 1 ⁢ 𝑖 𝑘 ) }       𝑡 𝑘 ← 1 / | 𝛽 𝑖 𝑘 |       ( 𝑊 1 ⁢ 𝑖 𝑘 + 1 , 𝑤 2 ⁢ 𝑖 𝑘 + 1 ) ← ( 𝑊 1 ⁢ 𝑖 𝑘 , 𝑤 2 ⁢ 𝑖 𝑘 ) ⋅ ( 1 − 𝑡 𝑘 ⁢ 𝛽 𝑖 ) 1 / 2       𝑞 𝑖 𝑘 + 1 ← 𝑞 𝑖 𝑘 ⋅ ( 1 − 𝑡 𝑘 ⁢ 𝛽 𝑖 )   end for   Output: final weights 𝑊 1 𝑘 , 𝑤 2 𝑘

Now we specialize our results for CGL to two-layer neural networks with ReLU or gated ReLU activations. We state and prove our results for ReLU networks, but they are easily adapted to gated ReLUs. We start by interpreting conditions for uniqueness in the context of non-convex ReLU models and then move on to discussing optimal pruning for ReLU networks and continuity properties of the solution function. Proofs are deferred to Appendix B.

Optimal Sets and Uniqueness: Combining the mapping between solutions for the convex reformulation and the original non-convex training problem (Equation 5) and Section 3.1 immediately allows us to characterize the solution set for the full ReLU problem: {restatable}theoremreluSolFn Suppose 𝑚 ≥ 𝑚 * and 𝐷 ~

𝒟 𝑍 (no sub-sampling), with 𝑝

| 𝒟 ~ 𝑍 | . Then the optimal set for the ReLU problem up to permutation/splitting symmetries is

𝒪 𝜆

{ ( 𝑊 1 , 𝑤 2 ) : 𝑓 𝑊 1 , 𝑤 2 ( 𝑍 )

𝑦 ^ , 𝑊 1 ⁢ 𝑖

( 𝛼 𝑖 / 𝜆 ) 1 / 2 𝑣 𝑖 ,

(19)

𝑤 2 ⁢ 𝑖

𝜉 𝑖 ( 𝛼 𝑖 𝜆 ) 1 / 2 , 𝛼 𝑖 ≥ 0 , 𝑖 ∈ [ 2 𝑝 ] ∖ 𝒮 𝜆 ⇒ 𝛼 𝑖

0 } .

Eq. (19) abuses notation by using 𝒮 𝜆 as a subset of the neuron indices { 1 , … ⁢ 2 ⁢ 𝑝 } , where { 1 , … ⁢ 𝑝 } index positive neurons for which 𝜉 𝑖

• 1 (corresponding to blocks 𝐷 𝑖 ⁢ 𝑍 ) and { 𝑝

• 1 , … , 2 ⁢ 𝑝 } index the negative neurons (corresponding to − 𝐷 𝑖 ⁢ 𝑍 ), for which 𝜉 𝑖

  − 1 . Figure 1 plots the first feature of three neurons as they vary over this solution set. The mapping from convex to non-convex parameterization transforms the polytope of solutions into a curved manifold.

Choosing a sub-sampled set of patterns 𝒟 ~ ⊂ 𝒟 𝑍 corresponds to finding a stationary point of the non-convex training problem (Wang et al., 2021). Using this fact with Algorithm 2 finally justifies description of all stationary points of the ReLU problem given in the introduction. {restatable}propositionstationaryPoints The set of stationary points of two-layer ReLU networks up to permutation/splitting symmetries is

𝒞 𝜆

{
( 𝑊 1 , 𝑤 2 ) : 𝒟 ~ ⊆ 𝒟 𝑍 , 𝑓 𝑊 1 , 𝑤 2 ⁢ ( 𝑍 )

𝑦 ^ 𝒟 ~ ,

𝑊 1 ⁢ 𝑖

( 𝛼 𝑖 / 𝜆 ) 1 / 2 ⁢ 𝑣 𝑖 ⁢ ( 𝒟 ~ ) , 𝑤 2 ⁢ 𝑖

𝜉 𝑖 ⁢ ( 𝛼 𝑖 ⁢ 𝜆 ) 1 / 2 ,

𝛼 𝑖 ≥ 0 , 𝑖 ∈ [ 2 | 𝒟 ~ | ] ∖ 𝒮 𝜆 ⟹ 𝛼 𝑖

0 } ,

where 𝒟 ~ are sub-sampled activation patterns, 𝑦 ^ 𝒟 ~ is the optimal model fit using those patterns, and 𝑣 𝑖 ⁢ ( 𝒟 ~ )

𝑐 𝑏 𝑖 ⁢ ( 𝒟 ~ ) − 𝐾 𝑏 𝑖 ⁢ 𝜌 𝑏 𝑖 ⁢ ( 𝒟 ~ ) is determined by the fit and the dual parameters.

We note that since deeper networks are also related to CGL through convex reformulations (Ergen & Pilanci, 2021a), Algorithm 2 may also be applied beyond two layers.

Recall that the solution set for a two-layer ReLU network is typically not unique due to model symmetries. However, if the convex solution is unique, then the non-convex ReLU training problem is p-unique. Combining this with our results for CGL gives the following sufficient conditions.

{restatable}

propositionpUnique Let 𝜆

0 and suppose that the convex ReLU problem has a unique solution. Then the ReLU model solution is p-unique. In particular, if { 𝐷 𝑖 ⁢ 𝑍 ⁢ 𝑣 𝑏 𝑖 } ℰ 𝜆 are linearly independent, then the non-convex solution is p-unique.

For gated ReLU networks, it is also sufficient to check the blocks [ 𝐷 𝑖 ⁢ 𝑍 ] 𝐷 𝑖 ∈ 𝒟 ~ to see if they satisfy GGP. By looking at the structure of 𝐷 𝑖 ⁢ 𝑋 , we give simple sufficient conditions for sub-sampled convex ReLU programs to be p-unique.

{restatable}

propositionreluUnique Let 𝜆 > 0 and 𝑝

| 𝒟 ~ | . Suppose 𝑍 follows a continuous probability distribution and nnz ⁢ ( 𝐷 𝑖 ) ≥ 𝑝 ⋅ 𝑑 for every 𝐷 𝑖 ∈ 𝒟 ~ . If ℰ 𝜆 does not contain two blocks with the same activation pattern, then the sub-sampled convex ReLU program has a p-unique solution almost surely.

Algorithm 2 requires 𝑛 to be much greater than 𝑑 to be useful due to the trivial bound nnz ⁢ ( 𝐷 𝑖 ) ≤ 𝑛 . In practice, the condition on activation patterns can be enforced by constraining 𝑣 𝑖

0 or 𝑤 𝑖

0 for each activation pattern before solving the convex reformulation.

Table 1:Tuning neural networks by searching over the optimal set. We fit two-layer ReLU networks on the training set and compute the minimum ℓ 2 norm solution (Min L 2 ). Then we tune by finding an extreme point approximating the maximum ℓ 2 -norm solution (EP), minimizing validation MSE over the optimal set (V-MSE), and minimizing test MSE over the optimal set (T-MSE). Results show median test accuracy; Max Diff. reports the difference between the best and worse models found. Exploring the optimal set reveals a huge disparity in the performance of optimal networks, with the generalization gap exceeding 20 points on four datasets. Dataset Min L 2 EP V-MSE T-MSE Max Diff. fertility 0.66 0.69 0.65 0.64 0.05 heart-hung. 0.75 0.75 0.71 0.85 0.14 mammogr. 0.77 0.77 0.57 0.78 0.21 monks-1 0.67 0.66 0.49 0.57 0.17 planning 0.53 0.52 0.53 0.7 0.17 spectf 0.64 0.64 0.56 0.58 0.08 horse-colic 0.75 0.59 0.74 0.85 0.26 ilpd-indian 0.59 0.59 0.53 0.72 0.19 parkinsons 0.74 0.74 0.65 0.88 0.23 pima 0.68 0.68 0.68 0.87 0.2 Figure 2:Pruning neurons from two-layer ReLU networks on binary classification tasks from the UCI repository. We compare our theory-inspired approach (Optimal/LS), against removing the neuron with smallest ℓ 2 norm (Neuron Magnitude), removing the neuron with the smallest weighted gradient norm (Gradient Magnitude), and random pruning (Random). For Optimal/LS, we use Algorithm 2, which begins with optimal pruning and then switches to a least-squares heuristic. We plot test accuracy against number of active neurons. Optimal/LS dominates the baseline methods on every dataset and even improves test accuracy on breast-cancer and fertility.

Pruning: If ( 𝑣 , 𝑢 ) is a minimal solution to the convex reformulation, then the corresponding ReLU network is the p-unique model using only those activation patterns (Propositions 3.3 and 2). Thus, Algorithm 1 can be used to prune any solution to obtain a neuron-sparse neural network achieving the optimal training objective. Algorithm 2 specializes our pruning algorithm to the ReLU problem and extends it to support approximate pruning. Note the resulting procedure is completely independent of the convex reformulation. The complexity of this method is as follows.

{restatable}

propositionminimalComplexity Suppose 𝑟

rank ⁢ ( 𝑋 ) . Then an optimal and minimal ReLU network with at most 𝑚 * ≤ 𝑛 non-zero neurons can be computed in 𝑂 ⁢ ( 𝑑 3 ⁢ 𝑟 3 ⁢ ( 𝑛 / 𝑟 ) 3 ⁢ 𝑟 ) time.

As a consequence, the complexity of computing an optimal and minimal ReLU network is fully polynomial when 𝑟 is bounded. We also have a more sensitive statement for the minimal width: if ( 𝑊 1 * , 𝑤 2 * ) are optimal weights for the ReLU model, then 𝑚 * is at most the dimension of Span ⁢ { ( 𝑋 ⁢ 𝑊 1 ⁢ 𝑖 * ) + } 𝑖 and exactly this dimension under group dependence (Corollary 3.3). We experiment with pruning ReLU networks using this approach in Section 5 and that show it is more effective than naive pruning strategies.

Continuity: First we give a negative result for singular networks, that is, models where 𝑚 < 𝑚 * and no convex reformulation exists. In this setting, the solution map can be made to behave arbitrarily poorly. {restatable}propositiononeNeuron There exists ( 𝑍 , 𝑦 ) for which 𝒪 * is not open nor is the model fit 𝑓 𝑊 1 , 𝑤 2 ⁢ ( 𝑍 ) continuous in 𝜆 . Combined with the next result, Figure 2 indicates that the threshold 𝑚 * may be crucial for continuity to extend to the non-convex parameterization.

Corollary 4.1.

Suppose 𝑚 ≥ 𝑚 * . Then the optimal model fit for two-layer gated ReLU networks is continuous at all 𝜆

0 . Similarly, if the (gated) ReLU solution is p-unique on an open interval Λ , then the regularization path is also continuous on Λ up to permutations of the weights.

Together, Corollary 4.1 and Algorithm 2 are concrete conditions for the model fit and regularization path of a sub-sampled problem to be continuous.

Min-Norm Solutions: In Section 3.5, we examined minimum ℓ 2 -norm solutions to CGL. However, all optimal ReLU models have the same ℓ 2 -norm when 𝜆

0 . Minimizing the Euclidean norm of solutions to the convex reformulation instead minimizes the sum of norms to the fourth power. {restatable}lemmaminNormNN The minimum ℓ 2 -norm solution to the convex reformulation of a (gated) ReLU model corresponds to the optimal neural network which minimizes,

𝑟 ⁢ ( 𝑊 1 , 𝑤 2 )

∑ 𝑖

1 𝑚 ‖ 𝑊 1 ⁢ 𝑖 ‖ 2 4 + ‖ 𝑤 2 ⁢ 𝑖 ‖ 2 4 ,

and admits no neuron-merge symmetries.

As a result, we can compute the 𝑟 -minimal optimal ReLU network by solving Problem (16). If 𝒮 𝜆 is unknown, then using 𝒜 𝜆 ⁢ ( 𝑤 ) for some solution 𝑤 as an approximation gives the 𝑟 -minimal network using a subset of those activations.

Sensitivity: Definition 3.9 extends similar results for the group lasso by Vaiter et al. (2012) to CGL using standard CQs. Since 𝐾 is block-diagonal, LICQ will be satisfied whenever the rows of 𝑍 are linearly independent. SCS is more challenging; while the classical theorem of Goldman & Tucker (2016) establishes that SCS is satisfied for linear programs, it is known that SCS can fail for general cone programs (Tunçel & Wolkowicz, 2012). As such, SCS must be checked on a per-problem basis in general.

In the context of gated ReLU problems, 𝐾

0 and there is no requirement for CSC/LICQ. Minimal models 𝑤 ⁢ ( 𝜆 , 𝑦 ) are weakly differentiable, which Vaiter et al. (2012) uses to compute the degrees of freedom of 𝑤 via Stein’s Lemma (Stein, 1981). It is straightforward to extend this calculation to the gated ReLU weights using the chain rule, which can then be used to calculate Stein’s unbiased risk estimator.

5Experiments

Through convex reformulations, we have characterized the optimal sets of ReLU networks, computed minimal networks, and provided sensitivity results. Our goal in this section is to illustrate the power of our framework for analyzing ReLU networks and developing new algorithms.

Tuning: We first consider a tuning task on 10 binary classification datasets from the UCI repository (Dua & Graff, 2017). For each dataset, we do a train/validation/test split, fit a two-layer ReLU model on the training set, and then compute the minimum ℓ 2 -norm model. We use this to explore the optimal set in three ways: (i) we compute an extreme point that (approximately) maximizes the model’s ℓ 2 -norm; (ii) we minimize the validation MSE over 𝒲 * ⁢ ( 𝜆 ) ; (iii) we minimize test MSE over 𝒲 * ⁢ ( 𝜆 ) . These procedures select for different optimal models, have no effect on the training objective, and are only possible because we know 𝒲 * .

The results are summarized in Table 1. We see that optimal models can perform very differently at test time despite having exactly the same training error and model norm. Indeed, 9/10 datasets show at least a 10 percent gap between the best and worst models and 4/10 have a gap exceeding 20 percent accuracy. We conclude that the training objective is badly under-determined even for shallow neural networks, implying that implicit regularization is critical in practice. See Appendix D for results on additional datasets.

Figure 3:Pruning neurons from two-layer ReLU networks on two binary classification tasks drawn from the CIFAR-10 dataset. We compare our method (Optimal/LS) against baselines; see Figure 2 for details. Our approach, which makes use of a weight correction after pruning, outperforms every baseline.

Pruning: We also consider several neuron pruning tasks. We use two-layer ReLU networks and start pruning from the model given by optimizing the convex reformulation. We compare four strategies: (i) pruning neurons optimally using Algorithm 2 until { ( 𝑋 ⁢ 𝑊 1 ⁢ 𝑖 ) + } 𝒜 𝜆 are linearly independent and then approximately using least-squares fits; and (ii) by removing the neuron with the smallest magnitude, ‖ 𝑊 1 ⁢ 𝑖 ⋅ 𝑤 2 ⁢ 𝑖 ‖ ; (iii) by removing the neuron with the smallest weighted gradient; and (iv) by random pruning.

Figure 2 shows test performance of the these methods for five UCI datasets. Our theory-based pruning method has better test performance than the baselines on every dataset considered; on hill-valley, the gap between our approach and magnitude-based pruning is approximately 40 % . Figure 3 presents similar results for two binary tasks taken from the CIFAR-10 dataset (Krizhevsky et al., 2009). We provide experiments on additional datasets, including MNIST (LeCun et al., 1998), and experimental details in Appendix D.

6Conclusion

We study the structure and properties of solution sets for shallow neural networks with (gated) ReLU activations. Unlike previous work, we avoid non-convexity of neural networks by studying the constrained group lasso, a generalized linear model which unifies the convex reformulations of both ReLU and gated ReLU networks. We derive analytical expressions for the optima and all stationary points of the training objective for two-layer ReLU networks. Building on this characterization, we develop conditions for the optimal neural network to be p-unique, an algorithm for optimal pruning of neural networks, and sensitivity results. We demonstrate the utility of our framework in experiments on MNIST, CIFAR-10, and the UCI datasets.

There is still much work to do in this area. For example, we conjecture that the min-norm CGL solution, which corresponds to the network minimizing a fourth-power penalty, always has a continuous regularization path. More generally, it remains to extend our characterization of the solution set to deeper networks and vector-output models.

Acknowledgements

This work was supported by the National Science Foundation (NSF), Grants ECCS-2037304, DMS-2134248; by the NSF CAREER Award, Grant CCF-2236829; by the U.S. Army Research Office Early Career Award, Grant W911NF-21-1-0242; by the Stanford Precourt Institute; by the Stanford Research Computing Center; and by the ACCESS—AI Chip Center for Emerging Smart Systems through InnoHK, Hong Kong, SAR. Aaron Mishkin was supported by NSF Grant DGE-1656518 and by NSERC Grant PGSD3-547242-2020. We thank Frederik Kunstner and Victor Sanches Portella for many insightful discussions.

References Agrawal et al. (2019) ↑ Agrawal, A., Amos, B., Barratt, S., Boyd, S., Diamond, S., and Kolter, J. Z.Differentiable convex optimization layers.Advances in neural information processing systems, 32, 2019. ApS (2022) ↑ ApS, M.Mosek optimizer API for python.Version, 9(17):6–4, 2022. Baydin et al. (2017) ↑ Baydin, A. G., Cornish, R., Rubio, D. M., Schmidt, M., and Wood, F.Online learning rate adaptation with hypergradient descent.arXiv preprint arXiv:1703.04782, 2017. Berge (1997) ↑ Berge, C.Topological Spaces: including a treatment of multi-valued functions, vector spaces, and convexity.Courier Corporation, 1997. Bertsekas (2009) ↑ Bertsekas, D.Convex optimization theory, volume 1.Athena Scientific, 2009. Blalock et al. (2020) ↑ Blalock, D. W., Ortiz, J. J. G., Frankle, J., and Guttag, J. V.What is the state of neural network pruning?In Dhillon, I. S., Papailiopoulos, D. S., and Sze, V. (eds.), Proceedings of Machine Learning and Systems 2020, MLSys 2020, Austin, TX, USA, March 2-4, 2020. mlsys.org, 2020. Boyd & Vandenberghe (2014) ↑ Boyd, S. P. and Vandenberghe, L.Convex Optimization.Cambridge University Press, 2014. Clarke (1990) ↑ Clarke, F. H.Optimization and nonsmooth analysis.SIAM, 1990. Delgado et al. (2014) ↑ Delgado, M. F., Cernadas, E., Barro, S., and Amorim, D. G.Do we need hundreds of classifiers to solve real world classification problems?J. Mach. Learn. Res., 15(1):3133–3181, 2014. Diamond & Boyd (2016) ↑ Diamond, S. and Boyd, S.CVXPY: A Python-embedded modeling language for convex optimization.Journal of Machine Learning Research, 17(83):1–5, 2016. Draxler et al. (2018) ↑ Draxler, F., Veschgini, K., Salmhofer, M., and Hamprecht, F. A.Essentially no barriers in neural network energy landscape.In Dy, J. G. and Krause, A. (eds.), Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp.  1308–1317. PMLR, 2018. Dua & Graff (2017) ↑ Dua, D. and Graff, C.UCI machine learning repository, 2017.URL http://archive.ics.uci.edu/ml. Efron et al. (2004) ↑ Efron, B., Hastie, T., Johnstone, I., and Tibshirani, R.Least angle regression.The Annals of statistics, 32(2):407–499, 2004. Ergen & Pilanci (2021a) ↑ Ergen, T. and Pilanci, M.Global optimality beyond two layers: Training deep ReLU networks via convex programs.In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp.  2993–3003. PMLR, 2021a. Ergen & Pilanci (2021b) ↑ Ergen, T. and Pilanci, M.Implicit convex regularizers of CNN architectures: Convex optimization of two- and three-layer networks in polynomial time.In International Conference on Learning Representations: ICLR 2021, 2021b. Ergen et al. (2021) ↑ Ergen, T., Sahiner, A., Ozturkler, B., Pauly, J. M., Mardani, M., and Pilanci, M.Demystifying batch normalization in ReLU networks: Equivalent convex optimization models and implicit regularization.In International Conference on Learning Representations, 2021. Fiacco & Ishizuka (1990) ↑ Fiacco, A. V. and Ishizuka, Y.Sensitivity and stability analysis for nonlinear programming.Annals of Operations Research, 27(1):215–235, 1990. Fiat et al. (2019) ↑ Fiat, J., Malach, E., and Shalev-Shwartz, S.Decoupling gating from linearity.arXiv preprint arXiv:1906.05032, 2019. Garipov et al. (2018) ↑ Garipov, T., Izmailov, P., Podoprikhin, D., Vetrov, D. P., and Wilson, A. G.Loss surfaces, mode connectivity, and fast ensembling of DNNs.In Bengio, S., Wallach, H. M., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pp.  8803–8812, 2018. Goldman & Tucker (2016) ↑ Goldman, A. J. and Tucker, A. W.4. theory of linear programming.In Linear Inequalities and Related Systems.(AM-38), Volume 38, pp.  53–98. Princeton University Press, 2016. Gunasekar et al. (2017) ↑ Gunasekar, S., Woodworth, B. E., Bhojanapalli, S., Neyshabur, B., and Srebro, N.Implicit regularization in matrix factorization.In Guyon, I., von Luxburg, U., Bengio, S., Wallach, H. M., Fergus, R., Vishwanathan, S. V. N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp.  6151–6159, 2017. Gupta et al. (2021) ↑ Gupta, V., Bartan, B., Ergen, T., and Pilanci, M.Exact and relaxed convex formulations for shallow neural autoregressive models.In International Conference on Acoustics, Speech, and Signal Processing, 2021. Hastie et al. (2007) ↑ Hastie, T., Taylor, J., Tibshirani, R., and Walther, G.Forward stagewise regression and the monotone lasso.Electronic Journal of Statistics, 1:1–29, 2007. Hogan (1973) ↑ Hogan, W. W.Point-to-set maps in mathematical programming.SIAM review, 15(3):591–603, 1973. Krizhevsky et al. (2009) ↑ Krizhevsky, A., Hinton, G., et al.Learning multiple layers of features from tiny images.2009. Kuditipudi et al. (2019) ↑ Kuditipudi, R., Wang, X., Lee, H., Zhang, Y., Li, Z., Hu, W., Ge, R., and Arora, S.Explaining landscape connectivity of low-cost solutions for multilayer nets.In Wallach, H. M., Larochelle, H., Beygelzimer, A., d’Alché-Buc, F., Fox, E. B., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp.  14574–14583, 2019. LeCun et al. (1998) ↑ LeCun, Y., Bottou, L., Bengio, Y., and Haffner, P.Gradient-based learning applied to document recognition.Proceedings of the IEEE, 86(11):2278–2324, 1998. Mishkin et al. (2022) ↑ Mishkin, A., Sahiner, A., and Pilanci, M.Fast convex optimization for two-layer ReLU networks: Equivalent model classes and cone decompositions.In Chaudhuri, K., Jegelka, S., Song, L., Szepesvári, C., Niu, G., and Sabato, S. (eds.), International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp.  15770–15816. PMLR, 2022. Nesterov et al. (2018) ↑ Nesterov, Y. et al.Lectures on convex optimization, volume 137.Springer, 2018. Neyshabur et al. (2015) ↑ Neyshabur, B., Tomioka, R., and Srebro, N.In search of the real inductive bias: On the role of implicit regularization in deep learning.In Bengio, Y. and LeCun, Y. (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Workshop Track Proceedings, 2015. Nguyen (2019) ↑ Nguyen, Q.On connected sublevel sets in deep learning.In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp.  4790–4799. PMLR, 2019. Osborne et al. (2000) ↑ Osborne, M. R., Presnell, B., and Turlach, B. A.A new approach to variable selection in least squares problems.IMA journal of numerical analysis, 20(3):389–403, 2000. Pilanci & Ergen (2020) ↑ Pilanci, M. and Ergen, T.Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks.In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, volume 119 of Proceedings of Machine Learning Research, pp.  7695–7705. PMLR, 2020. Robinson & Day (1974) ↑ Robinson, S. M. and Day, R. H.A sufficient condition for continuity of optimal sets in mathematical programming.Journal of Mathematical Analysis and Applications, 45(2):506–511, 1974. Roth & Fischer (2008) ↑ Roth, V. and Fischer, B.The group-lasso for generalized linear models: uniqueness of solutions and efficient algorithms.In Cohen, W. W., McCallum, A., and Roweis, S. T. (eds.), Machine Learning, Proceedings of the Twenty-Fifth International Conference (ICML 2008), Helsinki, Finland, June 5-9, 2008, volume 307 of ACM International Conference Proceeding Series, pp.  848–855. ACM, 2008. Sahiner et al. (2021) ↑ Sahiner, A., Ergen, T., Pauly, J. M., and Pilanci, M.Vector-output ReLU neural network problems are copositive programs: Convex analysis of two layer networks and polynomial-time algorithms.In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. Stein (1981) ↑ Stein, C. M.Estimation of the mean of a multivariate normal distribution.The annals of Statistics, pp.  1135–1151, 1981. Tibshirani (1996) ↑ Tibshirani, R.Regression shrinkage and selection via the lasso.Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267–288, 1996. Tibshirani (2013) ↑ Tibshirani, R. J.The lasso problem and uniqueness.Electronic Journal of statistics, 7:1456–1490, 2013. Tibshirani & Taylor (2011) ↑ Tibshirani, R. J. and Taylor, J.The solution path of the generalized lasso.The annals of statistics, 39(3):1335–1371, 2011. Tunçel & Wolkowicz (2012) ↑ Tunçel, L. and Wolkowicz, H.Strong duality and minimal representations for cone optimization.Computational optimization and applications, 53(2):619–648, 2012. Vaiter et al. (2012) ↑ Vaiter, S., Deledalle, C., Peyré, G., Fadili, J., and Dossal, C.The degrees of freedom of the group lasso for a general design.CoRR, abs/1212.6478, 2012. Wang et al. (2021) ↑ Wang, Y., Lacotte, J., and Pilanci, M.The hidden convex optimization landscape of regularized two-layer ReLU networks: an exact characterization of optimal solutions.In International Conference on Learning Representations, 2021. Yuan & Lin (2006) ↑ Yuan, M. and Lin, Y.Model selection and estimation in regression with grouped variables.Journal of the Royal Statistical Society: Series B (Statistical Methodology), 68(1):49–67, 2006. Appendix AConstrained Group Lasso: Proofs A.1Describing the Optimal Set Lemma A.1.

The model fit is the same for all optimal solutions to the CGL problem. That is,

𝑋 ⁢ 𝑤

𝑋 ⁢ 𝑤 ′  for all  ⁢ 𝑤 , 𝑤 ′ ∈ 𝒲 * ⁢ ( 𝜆 ) .

As a consequence, the sum of group norms is also constant when 𝜆

0 .

Proof.

This follows in a similar fashion to the classic result for the group lasso. Let 𝑤 , 𝑤 ′ ∈ 𝒲 * ⁢ ( 𝜆 ) , 𝑤 ¯

1 2 ⁢ 𝑤 + 1 2 ⁢ 𝑤 ′ , and suppose 𝑝 * is the optimal value of the constrained program. By convexity, we have

1 2 ⁢ ‖ 𝑋 ⁢ 𝑤 ¯ − 𝑦 ‖ 2 2 + 𝜆 ⁢ ∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 ¯ 𝑏 𝑖 ‖ 2
≤ 1 2 ⁢ 𝑝 * + 1 2 ⁢ 𝑝 *

𝑝 * ,

where the inequality is strict if 𝑋 ⁢ 𝑤 ≠ 𝑋 ⁢ 𝑤 ′ by strong convexity of 𝑓 ⁢ ( 𝑢 )

‖ 𝑢 − 𝑦 ‖ 2 2 . Since 𝑤 , 𝑤 ′ are both feasible, 𝑤 ¯ is also feasible and clearly 𝑤 ¯ cannot obtain an objective value less than 𝑝 * . Thus, 𝑋 ⁢ 𝑤

𝑋 ⁢ 𝑤 ′ must hold.

To see the second part of the result, observe that

𝜆 ⁢ ∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 ¯ 𝑏 𝑖 ‖ 2

𝑝 * − 1 2 ⁢ ‖ 𝑦 ^ ⁢ ( 𝜆 ) − 𝑦 ‖ 2 2 ,

is also constant over 𝒲 * ⁢ ( 𝜆 ) . ∎

\solFnCGL

Proof.

Fix 𝜆

0 and let 𝑤 ∈ 𝒲 * ⁢ ( 𝜆 ) . If 𝑤 𝑏 𝑖 ≠ 0 , then the KKT conditions require

𝜆 ⁢ 𝑤 𝑏 𝑖 ‖ 𝑤 𝑏 𝑖 ‖ 2

𝑣 𝑏 𝑖 ⟹ 𝑤 𝑏 𝑖

𝛼 𝑏 𝑖 ⁢ 𝑣 𝑏 𝑖 ,

for 𝛼 > 0 . If 𝑤 𝑏 𝑖

0 , then 𝑤 𝑏 𝑖

𝛼 𝑏 𝑖 ⁢ 𝑣 𝑏 𝑖 holds trivially for 𝛼 𝑏 𝑖

0 . Since 𝑤 is optimal, it must satisfy

𝑋 ⁢ 𝑤

𝑦 ^ ,

by Lemma A.1. Finally, 𝒜 𝜆 ⁢ ( 𝑤 ) ⊆ 𝒮 𝜆 so that 𝑤 satisfies the characterization.

For the reverse direction, we start by defining

𝒳

{ 𝑤 ∈ ℝ 𝑑 :
∀ 𝑏 𝑖 ∈ 𝒮 𝜆 , 𝑤 𝑏 𝑖

𝛼 𝑏 𝑖 ⁢ 𝑣 𝑏 𝑖 , 𝛼 𝑏 𝑖 ≥ 0 ,

∀ 𝑏 𝑗 ∈ ℬ ∖ 𝒮 𝜆 , 𝑤 𝑏 𝑗

0 , 𝑋 𝑤

𝑦 ^ }

Take any 𝑤 ′ ∈ 𝒳 . If 𝑤 𝑏 𝑖 ′ ≠ 0 , then 𝑏 𝑖 ∈ ℰ 𝜆 and ‖ 𝑣 𝑏 𝑖 ‖ 2

𝜆 so that we may write

𝑤 𝑏 𝑖 ′

𝛼 𝑏 𝑖 ⁢ 𝑣 𝑏 𝑖
⟹ 𝑤 𝑏 𝑖 ′ ‖ 𝑤 𝑏 𝑖 ′ ‖ 2

𝛼 𝑏 𝑖 ⁢ 𝑣 𝑏 𝑖 ‖ 𝛼 𝑏 𝑖 ⁢ 𝑣 𝑏 𝑖 ‖ 2

⟹ 𝑤 𝑏 𝑖 ′ ‖ 𝑤 𝑏 𝑖 ′ ‖ 2

𝑣 𝑏 𝑖 𝜆

⟹ 𝜆 ⁢ 𝑤 𝑏 𝑖 ′ ‖ 𝑤 𝑏 𝑖 ′ ‖ 2

𝑣 𝑏 𝑖 .

That is,

𝑋 𝑏 𝑖 ⊤ ⁢ ( 𝑋 ⁢ 𝑤 − 𝑦 ) + 𝜆 ⁢ 𝑤 𝑏 𝑖 ′ ‖ 𝑤 𝑏 𝑖 ′ ‖ 2 + 𝐾 𝑏 𝑖 ⁢ 𝜌 𝑏 𝑖 *

0 ,

which is exactly stationarity of the Lagrangian.

If 𝑤 𝑏 𝑖 ′

0 , then 𝑋 ⁢ 𝑤 ′

𝑦 ^ implies

‖ 𝑋 𝑏 𝑖 ⊤ ⁢ ( 𝑦 − 𝑋 ⁢ 𝑤 ′ ) + 𝐾 ⁢ 𝜌 𝑏 𝑖 * ‖ 2

‖ 𝑋 𝑏 𝑖 ⊤ ⁢ ( 𝑦 − 𝑋 ⁢ 𝑤 ) + 𝐾 ⁢ 𝜌 𝑏 𝑖 * ‖ 2 ≤ 𝜆 ,

for some 𝑤 ∈ 𝒲 * ⁢ ( 𝜆 ) , which also implies the Lagrangian is stationary.

Now we show optimality of 𝑤 ′ by checking feasibility and complementary slackness. If 𝑤 𝑏 𝑖 ′ ≠ 0 then 𝑤 𝑏 𝑖 ′

𝛼 𝑏 𝑖 ′ 𝛼 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 for some optimal solution 𝑤 with 𝛼 𝑏 𝑖

0 . This follows since 𝑤 𝑏 𝑖 ′ ≠ 0 implies 𝑏 𝑖 ∈ 𝒮 𝜆 . Thus,

𝐾 𝑏 𝑖 ⊤ ⁢ 𝑤 𝑏 𝑖 ′

𝛼 𝑏 𝑖 ′ 𝛼 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 ≤ 0 ,

by feasibility of 𝑤 𝑏 𝑖 . Similarly, we find that complementary slackness is satisfied as follows:

[ 𝜌 𝑏 𝑖 ] 𝑗 ⋅ [ 𝐾 𝑏 𝑖 ] 𝑗 ⊤ ⁢ 𝑤 𝑏 𝑖 ′

𝛼 𝑏 𝑖 ′ 𝛼 𝑏 𝑖 ⁢ [ 𝜌 𝑏 𝑖 ] 𝑗 ⋅ [ 𝐾 𝑏 𝑖 ] 𝑗 ⊤ ⁢ 𝑤 𝑏 𝑖

0 .

If 𝑤 𝑏 𝑖

0 , then both feasibility and complementary slackness are trivial. Since ( 𝑤 ′ , 𝜌 * ) are feasible and 𝜌 * is dual optimal, we conclude the KKT conditions are satisfied and thus 𝑤 ′ ∈ 𝒲 * ⁢ ( 𝜆 ) . This completes the proof. ∎

Proposition A.2.

Fix 𝜆

0 . The optimal set for CGL problem is also given by

𝒲 * ( 𝜆 )

{ 𝑤 ∈ ℝ 𝑑 :
∀ 𝑏 𝑖 ∈ ℰ 𝜆 , 𝑤 𝑏 𝑖

𝛼 𝑏 𝑖 ⁢ 𝑣 𝑏 𝑖 , 𝛼 𝑏 𝑖 ≥ 0 ,

(20)

∀ 𝑏 𝑗 ∈ ℬ ∖ ℰ 𝜆 , 𝑤 𝑏 𝑗

0 , 𝑋 ⁢ 𝑤

𝑦 ^ ,

𝐾 ⊤ 𝑤 ≤ 0 , ⟨ 𝜌 * , 𝐾 ⊤ 𝑤 ⟩

0 }

Proof.

Fix 𝜆

0 and let 𝑤 ∈ 𝒲 * ⁢ ( 𝜆 ) . If 𝑤 𝑏 𝑖 ≠ 0 , then the KKT conditions require

𝜆 ⁢ 𝑤 𝑏 𝑖 ‖ 𝑤 𝑏 𝑖 ‖ 2

𝑣 𝑏 𝑖 ⟹ 𝑤 𝑏 𝑖

𝛼 𝑏 𝑖 ⁢ 𝑣 𝑏 𝑖 ,

for 𝛼 > 0 . If 𝑤 𝑏 𝑖

0 , then 𝑤 𝑏 𝑖

𝛼 𝑏 𝑖 ⁢ 𝑣 𝑏 𝑖 holds trivially for 𝛼 𝑏 𝑖

0 . Since 𝑤 is optimal, it must satisfy

𝑋 ⁢ 𝑤

𝑦 ^ ,

by Lemma A.1. Finally, ⟨ 𝜌 * , 𝐾 ⁢ 𝑤 ⟩

0 and is feasible by KKT conditions so that 𝑤 satisfies the characterization.

For the reverse direction, we start by defining

𝒳

{ 𝑤 ∈ ℝ 𝑑 :
∀ 𝑏 𝑖 ∈ ℰ 𝜆 , 𝑤 𝑏 𝑖

𝛼 𝑏 𝑖 ⁢ 𝑣 𝑏 𝑖 , 𝛼 𝑏 𝑖 ≥ 0 ,

∀ 𝑏 𝑗 ∈ ℬ ∖ ℰ 𝜆 , 𝑤 𝑏 𝑗

0 , 𝑋 ⁢ 𝑤

𝑦 ^ ,

𝐾 ⊤ 𝑤 ≤ 0 , ⟨ 𝜌 * , 𝐾 ⊤ 𝑤 ⟩

0 }

Take any 𝑤 ′ ∈ 𝒳 . If 𝑤 𝑏 𝑖 ′ ≠ 0 , then 𝑏 𝑖 ∈ ℰ 𝜆 and ‖ 𝑣 𝑏 𝑖 ‖ 2

𝜆 so that we may write

𝑤 𝑏 𝑖 ′

𝛼 𝑏 𝑖 ⁢ 𝑣 𝑏 𝑖
⟹ 𝑤 𝑏 𝑖 ′ ‖ 𝑤 𝑏 𝑖 ′ ‖ 2

𝛼 𝑏 𝑖 ⁢ 𝑣 𝑏 𝑖 ‖ 𝛼 𝑏 𝑖 ⁢ 𝑣 𝑏 𝑖 ‖ 2

⟹ 𝑤 𝑏 𝑖 ′ ‖ 𝑤 𝑏 𝑖 ′ ‖ 2

𝑣 𝑏 𝑖 𝜆

⟹ 𝜆 ⁢ 𝑤 𝑏 𝑖 ′ ‖ 𝑤 𝑏 𝑖 ′ ‖ 2

𝑣 𝑏 𝑖 .

That is,

𝑋 𝑏 𝑖 ⊤ ⁢ ( 𝑋 ⁢ 𝑤 − 𝑦 ) + 𝜆 ⁢ 𝑤 𝑏 𝑖 ′ ‖ 𝑤 𝑏 𝑖 ′ ‖ 2 + 𝐾 𝑏 𝑖 ⁢ 𝜌 𝑏 𝑖 *

0 ,

which is exactly stationarity of the Lagrangian.

If 𝑤 𝑏 𝑖 ′

0 , then

𝑋 ⁢ 𝑤 ′

𝑦 ^ ⟹ ‖ 𝑋 𝑏 𝑖 ⊤ ⁢ ( 𝑦 − 𝑋 ⁢ 𝑤 ′ ) + 𝐾 ⁢ 𝜌 𝑏 𝑖 * ‖ 2 ≤ 𝜆 ,

which also implies the Lagrangian is stationary.

Since ⟨ 𝜌 * , 𝐾 ⊤ ⁢ 𝑤 ′ ⟩

0 and 𝐾 ⊤ ⁢ 𝑤 ′ ≤ 0 , i.e. 𝑤 ′ is feasible, it is clear that complementary slackness must also hold. We conclude that ( 𝑤 ′ , 𝜌 * ) are primal-dual optimal by the KKT conditions and the proof is complete. ∎

\uniqueCGL

Proof.

Suppose by way of contradiction that 𝑤 , 𝑤 ′ ∈ 𝒲 * ⁢ ( 𝜆 ) such that 𝑤 ≠ 𝑤 ′ . By Section 3.1, we have

0

𝑋 ⁢ ( 𝑤 − 𝑤 ′ )

∑ 𝑏 𝑖 ∈ 𝒮 𝜆 𝑋 𝑏 𝑖 ⁢ ( 𝑤 𝑏 𝑖 − 𝑤 𝑏 𝑖 ′ )

∑ 𝑏 𝑖 ∈ 𝒮 𝜆 ( 𝛼 𝑏 𝑖 − 𝛼 𝑏 𝑖 ′ ) ⁢ 𝑋 𝑏 𝑖 ⁢ 𝑣 𝑏 𝑖 ,

which implies that the vectors { 𝑋 𝑏 𝑖 ⁢ 𝑣 𝑏 𝑖 } 𝒮 𝜆 are linearly dependent.

Necessity follows from Algorithm 1, which shows that, given a solution 𝑤 ∈ 𝒲 * ⁢ ( 𝜆 ) , linear dependence of { 𝑋 𝑏 𝑖 ⁢ 𝑤 ⁢ ( 𝜆 ) : 𝑏 𝑖 ∈ 𝒜 ⁢ ( 𝑤 ⁢ ( 𝜆 ) ) } implies the exist of at least one additional solution. ∎

\GGP

Proof.

Suppose the group Lasso solution is not unique. Then, Corollary 3.1 implies

𝒩 𝜆

Null ⁢ ( 𝑋 ℰ 𝜆 ) ⁢ ⋂ { 𝑧 : 𝑧 𝑏 𝑖

𝛼 𝑏 𝑖 ⁢ 𝑐 𝑏 𝑖 , 𝑏 𝑖 ∈ ℰ 𝜆 } ,

is non-empty. That is, there exist 𝛼 𝑏 𝑖 ≥ 0 such that

𝑋 𝑏 𝑗 ⁢ 𝑐 𝑏 𝑗

∑ 𝑏 𝑖 ∈ ℰ 𝜆 ∖ 𝑗 𝛼 𝑏 𝑖 ⁢ 𝑋 𝑏 𝑖 ⁢ 𝑐 𝑏 𝑖 .
Taking inner-products on both sides with the residual 𝑟 ,
𝑟 ⊤ ⁢ 𝑋 𝑏 𝑗 ⁢ 𝑐 𝑏 𝑗

∑ 𝑏 𝑖 ∈ ℰ 𝜆 ∖ 𝑗 𝛼 𝑏 𝑖 ⁢ 𝑟 ⊤ ⁢ 𝑋 𝑏 𝑖 ⁢ 𝑐 𝑏 𝑖

⟹ 𝑐 𝑏 𝑗 ⊤ ⁢ 𝑐 𝑏 𝑗

∑ 𝑏 𝑖 ∈ ℰ 𝜆 ∖ 𝑗 𝛼 𝑏 𝑖 ⁢ 𝑐 𝑏 𝑖 ⊤ ⁢ 𝑐 𝑏 𝑖

⟹ 𝜆 2

∑ 𝑏 𝑖 ∈ ℰ 𝜆 ∖ 𝑗 𝛼 𝑏 𝑖 ⁢ 𝜆 2

⟹ 1

∑ 𝑏 𝑖 ∈ ℰ 𝜆 ∖ 𝑗 𝛼 𝑏 𝑖 .

Thus, we deduce that

𝑋 𝑏 𝑗 ⁢ 𝑐 𝑏 𝑗

∑ 𝑏 𝑖 ∈ ℰ 𝜆 ∖ 𝑗 𝛽 𝑏 𝑖 ⁢ 𝑋 𝑏 𝑖 ⁢ 𝑐 𝑏 𝑖 ,

(21)

where ∑ 𝑏 𝑖 ∈ ℰ 𝜆 ∖ 𝑗 𝛽 𝑏 𝑖

1 , meaning 𝑋 𝑏 𝑗 𝑐 𝑏 𝑗 ∈ affine ( 𝑋 𝑏 𝑖 𝑧 𝑏 𝑖 : 𝑏 𝑖 ∈ ℰ 𝜆 ∖ 𝑏 𝑗 ) Now, suppose that | ℰ 𝜆 | > 𝑛 + 1 . Then, { 𝑋 𝑏 𝑖 ⁢ 𝑐 𝑏 𝑖 : 𝑏 𝑖 ∈ ℰ 𝜆 ∖ 𝑗 } are linearly dependent and, by eliminating dependent vectors 𝑋 𝑏 𝑖 ⁢ 𝑐 𝑏 𝑖 , we can repeat the above proof with a subset ℰ ′ of at most 𝑛 + 1 blocks. Noting ‖ 𝑐 𝑏 𝑖 ‖ 2

𝜆 for each 𝑏 𝑖 ∈ ℰ 𝜆 and rescaling both sides of Equation 21 by 𝜆 implies the existence of unit vectors 𝑧 𝑏 𝑖 which contradict GGP. This completes the proof. ∎

Proposition A.3.

Group general position does not imply the columns of 𝑋 are in general position. Similarly, general position of the columns of 𝑋 does not imply group general position.

Proof.

Let 𝑥 1 , … , 𝑥 𝑑 ∈ ℝ 𝑑 − 1 . Consider the simple case where we have two groups: 𝑏 1

{ 1 } and 𝑏 2

{ 2 , … , 𝑑 } . Group general position is violated if there exists a unit vector 𝑧 𝑏 2 such that

𝑥 1

𝑋 𝑏 2 ⁢ 𝑧 𝑏 2 .

⇔ 𝑥 1

∈ 𝑋 𝑏 2 ⁢ 𝐵 𝑑 − 1 ,

where 𝐵 𝑑 − 1

{ 𝑧 ∈ ℝ 𝑑 − 1 : ‖ 𝑧 ‖ 2 ≤ 1 } . In contrast, general position is violated if

𝑥 1
∈ affine ⁢ ( 𝑥 2 , … , 𝑥 𝑑 )

⇔ 𝑥 1
∈ 𝑋 𝑏 2 ⁢ { 𝑧 : ⟨ 𝑧 , 1 ⟩

1 } .

Taking 𝑋 𝑏 2

𝐼 , it is trivial to see that group general position can hold when general position is violated and vice-versa. ∎

A.2Computing Dual Optimal Parameters Lemma A.4.

One Lagrange dual of CGL is the following:

max 𝜂 , 𝜌

− 1 2 ⁢ ( 𝜂 + 𝐾 ⁢ 𝜌 − 𝑋 ⊤ ⁢ 𝑦 ) ⁢ ( 𝑋 ⊤ ⁢ 𝑋 ) + ⁢ ( 𝜂 + 𝐾 ⁢ 𝜌 − 𝑋 ⊤ ⁢ 𝑦 ) + 1 2 ⁢ ‖ 𝑦 ‖ 2 2

(22)

s.t. 𝜂 + 𝐾 ⁢ 𝜌 ∈ 𝑅𝑜𝑤 ⁢ ( 𝑋 ) , ‖ 𝜂 𝑏 𝑖 ‖ 2 ≤ 𝜆 ⁢ ∀ 𝑏 𝑖 ∈ ℬ ,

where 𝜂 𝑏 𝑖

𝑐 𝑏 𝑖 − 𝐾 𝑏 𝑖 ⁢ 𝜌 𝑏 𝑖 shows that the vectors 𝑣 𝑏 𝑖 are, in fact, dual variables. Moreover, if 𝐾

0 , then 𝜌 *

0 and 𝜂 has the unique solution 𝜂 𝑏 𝑖

𝑋 𝑏 𝑖 ⊤ ⁢ ( 𝑦 − 𝑋 ⁢ 𝑤 )

𝑐 𝑏 𝑖 . That is, the dual parameters are the (unique) block correlation vectors.

Proof.

We re-write the group Lasso problem as follows:

min 𝑤 ⁡ 1 2 ⁢ ‖ 𝑋 ⁢ 𝑧 − 𝑦 ‖ 2 2 + 𝜆 ⁢ ∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 𝑏 𝑖 ‖ 2 s.t. ⁢ 𝑧

𝑤 , 𝐾 𝑏 𝑖 ⊤ ⁢ 𝑧 𝑏 𝑖 ≤ 0 .

The Lagrangian for this problem is

ℒ ⁢ ( 𝑤 , 𝑧 , 𝜂 , 𝜌 )

1 2 ⁢ ‖ 𝑋 ⁢ 𝑧 − 𝑦 ‖ 2 2 + ⟨ 𝜂 , 𝑧 − 𝑤 ⟩ + ⟨ 𝜌 , 𝐾 ⊤ ⁢ 𝑧 ⟩ + 𝜆 ⁢ ∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 𝑏 𝑖 ‖ 2

1 2 ⁢ ‖ 𝑋 ⁢ 𝑧 − 𝑦 ‖ 2 2 + ⟨ 𝜂 + 𝐾 ⁢ 𝜌 , 𝑧 ⟩ − ⟨ 𝜂 , 𝑤 ⟩ + 𝜆 ⁢ ∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 𝑏 𝑖 ‖ 2 .

Minimizing over 𝑧 , we find that stationarity implies

𝑋 ⊤ ⁢ ( 𝑦 − 𝑋 ⁢ 𝑧 )

𝜂 + 𝐾 ⁢ 𝜌 ,

so that 𝜂 + 𝐾 ⁢ 𝜌 ∈ Row ⁢ ( 𝑋 ) . Solving this system, we find

𝑋 ⊤ ⁢ 𝑋 ⁢ 𝑧

𝑋 ⊤ ⁢ 𝑦 − 𝜂 − 𝐾 ⁢ 𝜌 ⟹ 𝑧

( 𝑋 ⊤ ⁢ 𝑋 ) + ⁢ [ 𝑋 ⊤ ⁢ 𝑦 − 𝜂 − 𝐾 ⁢ 𝜌 ] + 𝑐 ,

where 𝑐 ∈ Null ⁢ ( 𝑋 ) . Let us minimize over 𝑤 similarly. The Lagrangian decouples block-wise in 𝑤 , so that we must solve

min 𝑤 𝑏 𝑖 ⁡ 𝜆 ⁢ ‖ 𝑤 𝑏 𝑖 ‖ 2 − ⟨ 𝜂 𝑏 𝑖 , 𝑤 𝑏 𝑖 ⟩ ,

for each 𝑏 𝑖 ∈ ℬ . The minimum value is achieved by the (negative) Fenchel conjugate of 𝜆 ⁢ ‖ 𝑤 𝑏 𝑖 ‖ 2 evaluated at 𝜂 𝑏 𝑖 ; that is,

min 𝑤 𝑏 𝑖 ⁡ 𝜆 ⁢ ‖ 𝑤 𝑏 𝑖 ‖ 2 − ⟨ 𝜂 𝑏 𝑖 , 𝑤 𝑏 𝑖 ⟩

− 𝟙 ⁢ ( ‖ 𝜂 𝑏 𝑖 ‖ 2 ≤ 𝜆 ) .

Combining this with the expression for 𝑧 , we obtain

ℒ ⁢ ( 𝑐 , 𝜂 , 𝜌 )

− 1 2 ⁢ ( 𝜂 + 𝐾 ⁢ 𝜌 − 𝑋 ⊤ ⁢ 𝑦 ) ⁢ ( 𝑋 ⊤ ⁢ 𝑋 ) + ⁢ ( 𝜂 + 𝐾 ⁢ 𝜌 − 𝑋 ⊤ ⁢ 𝑦 ) + ⟨ 𝜂 + 𝐾 ⁢ 𝜌 , 𝑐 ⟩ − ∑ 𝑏 𝑖 ∈ ℬ 𝟙 ⁢ ( ‖ 𝜂 𝑏 𝑖 ‖ 2 ≤ 𝜆 )

− 1 2 ⁢ ( 𝜂 + 𝐾 ⁢ 𝜌 − 𝑋 ⊤ ⁢ 𝑦 ) ⁢ ( 𝑋 ⊤ ⁢ 𝑋 ) + ⁢ ( 𝜂 + 𝐾 ⁢ 𝜌 − 𝑋 ⊤ ⁢ 𝑦 ) − ∑ 𝑏 𝑖 ∈ ℬ 𝟙 ⁢ ( ‖ 𝜂 𝑏 𝑖 ‖ 2 ≤ 𝜆 ) ,

where the second equality follows since 𝜂 + 𝐾 ⁢ 𝜌 ∈ Row ⁢ ( 𝑋 ) and 𝑐 ∈ Null ⁢ ( 𝑋 ) are orthogonal. (Alternatively, one can observe that the dual problem is unbounded below whenever ⟨ 𝑐 , 𝜂 + 𝐾 ⁢ 𝜌 ⟩ ≠ 0 .) Thus, the dual problem is equal to

max 𝜂 , 𝜌 − 1 2 ⁢ ( 𝜂 + 𝐾 ⁢ 𝜌 − 𝑋 ⊤ ⁢ 𝑦 ) ⁢ ( 𝑋 ⊤ ⁢ 𝑋 ) + ⁢ ( 𝜂 𝐾 ⁢ 𝜌 − 𝑋 ⊤ ⁢ 𝑦 ) − ∑ 𝑏 𝑖 ∈ ℬ 𝟙 ⁢ ( ‖ 𝜂 𝑏 𝑖 ‖ 2 ≤ 𝜆 ) − 𝟙 ⁢ ( 𝜂 + 𝐾 ⁢ 𝜌 ∈ Row ⁢ ( 𝑋 ) ) ,

which completes the derivation.

Recalling 𝑧

𝑤 for any primal-dual optimal pair and

𝑋 ⊤ ⁢ ( 𝑦 − 𝑋 ⁢ 𝑧 )

𝜂 + 𝐾 ⁢ 𝜌 ,

shows that 𝜂 𝑏 𝑖

𝑐 𝑏 𝑖 − 𝐾 ⁢ 𝜌 as claimed. Moreover, if 𝐾

0 , then we may assume without loss of generality that he corresponding dual vectors 𝜌 𝑏 𝑖 are zero. In this case, 𝜂 𝑏 𝑖

𝑐 𝑏 𝑖 and, since 𝑐 𝑏 𝑖 is unique, the dual solution must also be unique. ∎

Proposition A.5.

Let 𝜆 > 0 and 𝑤 ∈ 𝒲 * ⁢ ( 𝜆 ) . If 𝑤 𝑏 𝑖

0 , then any solution to Equation 15 is dual optimal for block 𝑏 𝑖 .

Proof.

Let 𝜌 𝑏 𝑖 be a solution to Equation 15. Since 𝑤 is optimal and strong duality holds, there exists some min-norm dual optimal vector 𝜌 * . Moreover 𝜌 * satisfies 𝜌 𝑏 𝑖 * ≥ 0 and

‖ 𝐾 𝑏 𝑖 ⁢ 𝜌 𝑏 𝑖 − 𝑐 𝑏 𝑖 ‖ 2 2 ≤ ‖ 𝐾 𝑏 𝑖 ⁢ 𝜌 𝑏 𝑖 * − 𝑐 𝑏 𝑖 ‖ 2 2 ≤ 𝜆 2 ,

so 𝑤 is both feasible satisfies stationarity of the Lagrangian, Finally, because 𝑤 𝑏 𝑖

0 , complementary slackness,

[ 𝜌 𝑏 𝑖 ] 𝑗 ⋅ [ 𝐾 𝑏 𝑖 ] 𝑗 ⊤ ⁢ 𝑤 𝑏 𝑖

0 ,

is verified for every 𝑗 ∈ [ 𝑎 𝑏 𝑖 ] . Since the KKT conditions are sufficient for primal-dual optimality, we conclude that 𝜌 𝑏 𝑖 is dual optimal. This completes the proof. ∎

A.3Minimal Solutions and Optimal Pruning \minimalSols

Proof.

Let 𝑤 ∈ 𝒲 * ⁢ ( 𝜆 ) and assume that the vectors { 𝑋 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 } 𝒜 ⁢ ( 𝑤 ) are linearly independent. By way of contradiction, assume there exists 𝑤 ′ ∈ 𝒲 * ⁢ ( 𝜆 ) with strictly smaller support. By Section 3.1, we have

𝑤 𝑏 𝑖 ′

𝛽 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 ,

for some 𝛽 𝑏 𝑖 ≥ 0 . This holds for each 𝑏 𝑖 ∈ 𝒜 𝜆 ⁢ ( 𝑤 ) (with 𝛽 𝑏 𝑖

0 when 𝑏 𝑖 ∈ 𝒜 𝜆 ⁢ ( 𝑤 ) ∖ 𝒜 𝜆 ⁢ ( 𝑤 ′ ) ) so that

𝑋 ⁢ 𝑤

𝑋 ⁢ 𝑤 ′ ⟹ ∑ 𝑏 𝑖 ∈ 𝒜 𝜆 ⁢ ( 𝑤 ) ( 1 − 𝛽 𝑏 𝑖 ) ⁢ 𝑋 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖

0 ,

which is a contradiction.

For the reverse direction, assume that 𝑤 is minimal, but that { 𝑋 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 } 𝒜 ⁢ ( 𝑤 ) are not linearly independent. Then the correctness of Algorithm 1 (see Proposition A.6) implies 𝑤 is not minimal. ∎

Proposition A.6.

Algorithm 1 returns a minimal solution to the constrained group lasso problem in at most 𝑂 ⁢ ( 𝑛 3 ⁢ 𝑙 + 𝑛 ⁢ 𝑑 ) time, where 𝑙 is the number of non-zero groups in the initial solution.

Proof.

Correctness: Let 𝑤 ∈ 𝒲 * ⁢ ( 𝜆 ) and 𝒜 be the associated active set. If 𝑤 0

𝑤 is minimal, then Section 3.3 implies { 𝑋 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 } 𝒜 are linearly independent the algorithm returns a minimal solution.

Let 𝑘 ≥ 0 and suppose 𝑤 𝑘 is not minimal. Then there exist weights 𝛽 𝑏 𝑖 such that

∑ 𝑏 𝑖 ∈ 𝒜 𝛽 𝑏 𝑖 ⁢ 𝑋 𝑏 𝑖 ⁢ 𝑤 𝑘

0 .

Let 𝑤 𝑏 𝑖 𝑡

( 1 − 𝑡 ⁢ 𝛽 𝑏 𝑖 ) ⁢ 𝑤 𝑏 𝑖 and let 𝑡 𝑘 be as defined in the algorithm. By construction, 𝑡 𝑘 is the smallest magnitude 𝑡 such that ( 1 − 𝑡 ⁢ 𝛽 𝑏 𝑖 )

0 for some 𝑏 𝑖 ∈ 𝒜 . We assume without loss of generality that 𝑡 𝑘

0 .

Fix 0 < 𝑡 < 𝑡 𝑘 . Let’s show that 𝑤 𝑡 is a solution to the constrained problem. Firstly, we have

𝑋 ⁢ 𝑤 𝑡

𝑋 ⁢ 𝑤 𝑘 − 𝑡 ⁢ ∑ 𝑏 𝑖 ∈ 𝒜 𝛽 𝑏 𝑖 ⁢ 𝑋 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 𝑘

𝑋 ⁢ 𝑤 𝑘 ,

showing that the model fit preserved. Moreover,

𝑤 𝑏 𝑖 𝑡

( 1 − 𝑡 ⁢ 𝛽 𝑏 𝑖 ) ⁢ 𝑤 𝑏 𝑖 𝑘

( 1 − 𝑡 ⁢ 𝛽 𝑏 𝑖 ) ⁢ 𝛼 𝑏 𝑖 ⁢ 𝑣 𝑏 𝑖 ,

where ( 1 − 𝑡 ⁢ 𝛽 𝑏 𝑖 ) ⁢ 𝛼 𝑏 𝑖

0 by the choice of 𝑡 . We conclude that 𝑤 𝑡 is optimal by Section 3.1.

By construction,

lim 𝑡 ↑ 𝑡 𝑘 𝑤 𝑡

𝑤 𝑘 + 1 .

Since 𝑤 𝑡 is an optimal solution, it has the (unique) optimal squared error and sum of group norms. Taking limits as 𝑡 ↑ 𝑡 𝑘 , we see that

𝑋 ⁢ 𝑤 𝑘 + 1

𝑋 ⁢ 𝑤 𝑘 , ∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 𝑏 𝑖 𝑘 + 1 ‖ 2

∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 𝑏 𝑖 ‖ 2 , 𝐾 ⊤ ⁢ 𝑤 𝑘 + 1 ≤ 0 ,

which implies that 𝑤 𝑘 + 1 obtains the optimal objective value and is feasible. Thus 𝑤 𝑘 + 1 is also a solution. Finally, 𝒜 ⁢ ( 𝑤 𝑘 + 1 ) is strictly smaller than 𝒜 ⁢ ( 𝑤 𝑘 ) , as required.

Arguing by induction now implies that Algorithm 1 returns an minimal solution in a finite number of steps.

Complexity: First, observe that we can pre-compute the block-wise model fits 𝑞 𝑏 𝑖

𝑋 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 before running the algorithm. The complexity is at most 𝑂 ⁢ ( 𝑛 ⁢ 𝑑 ) . At each iteration of the algorithm, we must do two things: (i) compute a non-trivial solution to a homogeneous equation and (ii) update the weights of the model fits. For (i), it is clear that any set of 𝑛 + 1 of the 𝑞 𝑏 𝑖 vectors will be linearly dependent, so that we compute a non-trivial solution to the homogeneous equation using the SVD in an at most 𝑂 ⁢ ( 𝑛 3 ) operations. For (ii), updating at most 𝑛 of the 𝛽 𝑏 𝑖 ’s requires 𝑂 ⁢ ( 𝑛 ) time. Since the algorithm runs at most 𝑙 iterations, we obtain a final complexity of 𝑂 ⁢ ( 𝑛 3 ⁢ 𝑙 + 𝑛 ⁢ 𝑑 ) , as claimed. ∎

Definition A.7.

We say that 𝑋 satisfies group dependence if for every choice of vectors 𝑧 𝑏 𝑖 ∈ ℝ | 𝑏 𝑖 | and partition 𝒟 ∪ ℐ

ℬ , 𝒟 ∩ ℐ

∅ such that

𝑔 𝒟 := ∑ 𝑏 𝑗 ∈ 𝒟 𝑋 𝑏 𝑗 ⁢ 𝑧 𝑏 𝑗 ∈ Span ⁢ ( { 𝑋 𝑏 𝑖 ⁢ 𝑧 𝑏 𝑖 : 𝑏 𝑖 ∈ ℐ } ) ,

it holds that

Span ⁢ ( { 𝑋 𝑏 𝑗 ⁢ 𝑧 𝑏 𝑗 : 𝑏 𝑗 ∈ 𝒟 } ) ⊆ Span ⁢ ( { 𝑋 𝑏 𝑖 ⁢ 𝑧 𝑏 𝑖 : 𝑏 𝑖 ∈ ℐ } ) .

In other words, linear dependence of 𝑔 𝒟 and { 𝑋 𝑏 𝑖 ⁢ 𝑧 𝑏 𝑖 : 𝑏 𝑖 ∈ ℐ } implies linear dependence of 𝑋 𝑏 𝑗 ⁢ 𝑧 𝑏 𝑗 and { 𝑋 𝑏 𝑖 ⁢ 𝑧 𝑏 𝑖 : 𝑏 𝑖 ∈ ℐ } for every 𝑏 𝑗 ∈ 𝒟 .

Lemma A.8.

If 𝑋 satisfies group dependence, then each step of the Algorithm 1 preserves the span of { 𝑋 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 𝑘 } . That is, only linearly dependent vectors are removed.

Proof.

Let 𝒱

Span ⁢ { 𝑋 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 } be the span of the initial solution. Since 𝑤 0

𝑤 by definition, the base case holds trivially.

Now, suppose Span ⁢ ( 𝑋 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 𝑘 )

𝒱 and let 𝒟 𝑘

𝒜 𝜆 ⁢ ( 𝑤 𝑘 ) ∖ 𝒜 𝜆 ⁢ ( 𝑤 𝑘 + 1 ) . For every 𝑏 𝑗 ∈ 𝒟 𝑘 , it holds that 𝛽 𝑏 𝑗

𝛽 𝑏 𝑖 𝑘 , meaning

∑ 𝑗 ∈ 𝒟 𝑘 𝑋 𝑏 𝑗 ⁢ 𝑤 𝑏 𝑗 𝑘 ∈ Span ⁢ ( { 𝑋 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 𝑘 : 𝑏 𝑖 ∈ 𝒜 𝜆 ⁢ ( 𝑤 𝑘 + 1 ) } ) .

Group dependence now implies for every 𝑏 𝑗 ∈ 𝒟 𝑘 there exists 𝜁 𝑗 such that

𝑋 𝑏 𝑗 ⁢ 𝑤 𝑏 𝑗 𝑘

∑ 𝑏 𝑖 ∈ 𝒜 𝜆 ⁢ ( 𝑤 𝑘 ) 𝜁 𝑏 𝑖 𝑗 ⁢ 𝑋 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 𝑘 .

Let 𝑣 ∈ 𝒱 and observe that

𝑣

∑ 𝑏 𝑖 ∈ 𝒜 𝜆 ⁢ ( 𝑤 𝑘 ) 𝛼 𝑏 𝑖 ⁢ 𝑋 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 𝑘

∑ 𝑏 𝑖 ∈ 𝒜 𝜆 ⁢ ( 𝑤 𝑘 + 1 ) 𝛼 𝑏 𝑖 ⁢ 𝑋 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 𝑘 + ∑ 𝑏 𝑗 ∈ 𝒟 𝑘 𝛼 𝑏 𝑗 ⁢ 𝑋 𝑏 𝑗 ⁢ 𝑤 𝑏 𝑗 𝑘

∑ 𝑏 𝑖 ∈ 𝒜 𝜆 ⁢ ( 𝑤 𝑘 + 1 ) 𝛼 𝑏 𝑖 ⁢ 𝑋 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 𝑘 + ∑ 𝑏 𝑗 ∈ 𝒟 𝑘 ∑ 𝑏 𝑖 ∈ 𝒜 𝜆 ⁢ ( 𝑤 𝑘 + 1 ) 𝛼 𝑏 𝑗 ⁢ 𝜁 𝑏 𝑖 𝑗 ⁢ 𝑋 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 𝑘

∑ 𝑏 𝑖 ∈ 𝒜 𝜆 ⁢ ( 𝑤 𝑘 + 1 ) ( 𝛼 𝑏 𝑖 + [ ∑ 𝑏 𝑗 ∈ 𝒟 𝑘 𝛼 𝑏 𝑗 ⁢ 𝜁 𝑏 𝑖 𝑗 ] ) ⁢ 𝑋 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 𝑘

∑ 𝑏 𝑖 ∈ 𝒜 𝜆 ⁢ ( 𝑤 𝑘 + 1 ) ( 𝛼 𝑏 𝑖 + [ ∑ 𝑏 𝑗 ∈ 𝒟 𝑘 𝛼 𝑏 𝑗 ⁢ 𝜁 𝑏 𝑖 𝑗 ] 1 − 𝑡 𝑘 ⁢ 𝛽 𝑏 𝑖 ) ⁢ 𝑋 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 𝑘 + 1 ,

Thus, Span ⁢ ( 𝑋 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 𝑘 + 1 )

𝒱 . Arguing by induction completes the proof. ∎

Lemma A.9.

Let 𝒳

{ 𝑥 1 , … , 𝑥 𝑘 } be a set of linearly dependent vectors. Every linearly independent subset of 𝒳 obtained by iteratively removing linearly dependent vectors has the same cardinality.

Proof.

Let 𝒴 , 𝒴 ′ ⊂ 𝒳 be linearly independent subsets obtained by pruning linearly dependent vectors from 𝒳 and assume | 𝒴 ′ | < | 𝒴 | . Since 𝒴 and 𝒴 ′ are obtained by pruning only linearly dependent vectors, it must be that

Span ⁢ ( 𝒴 ′ )

Span ⁢ ( 𝒴 )

Span ⁢ ( 𝒳 ) .

Let 𝑐

dim ⁢ ( Span ⁢ ( 𝒳 ) ) . Only a set of 𝑐 linearly independent vectors can span Span ⁢ ( 𝒳 ) ; thus, | 𝒴 |

𝑐 must hold and 𝒴 ′ cannot span Span ⁢ ( 𝒳 ) . This is a contradiction. We conclude | 𝒴 ′ |

| 𝒴 | as claimed. ∎

Lemma A.10.

There exists a solution to CGL with support exactly 𝒮 𝜆 .

Proof.

By definition, there exists 𝑤 ∈ 𝒲 * ⁢ ( 𝜆 ) such that 𝑤 𝑏 𝑖 ≠ 0 for every 𝑏 𝑖 ∈ 𝒮 𝜆 . Taking convex combination of these solutions yields 𝑤 ′ with support exactly 𝒮 𝜆 . Since 𝒲 * ⁢ ( 𝜆 ) is convex, 𝑤 ′ is also a solution. This completes the proof. ∎

Lemma A.11.

Let 𝑤 be a minimal solution and 𝑤 ¯ be a solution with support 𝒮 𝜆 , which exists by Lemma A.10. Then, 𝑤 ¯ can be pruned in one step to obtain 𝑤 .

Proof.

Suppose 𝑤 ¯ is minimal. Then { 𝑋 𝑏 𝑖 ⁢ 𝑤 ¯ 𝑏 𝑖 } 𝒮 𝜆 are linearly independent, which implies { 𝑋 𝑏 𝑖 ⁢ 𝑣 𝑏 𝑖 } 𝒮 𝜆 are also linearly independent. We conclude 𝑤 ¯ is the unique solution to CGL by Corollary 3.1 and the claim holds trivially.

Suppose 𝑤 ¯ is not minimal. Since 𝒜 𝜆 ⁢ ( 𝑤 ) ⊂ 𝒮 𝜆 , Span ⁢ { 𝑋 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 } ⊂ Span ⁢ { 𝑋 𝑏 𝑖 ⁢ 𝑤 ¯ 𝑏 𝑖 } so that every vector 𝑋 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 can be written as a linear combination of vectors in { 𝑋 𝑏 𝑖 ⁢ 𝑤 ¯ 𝑏 𝑖 } . Thus, we find that

∑ 𝑏 𝑖 ∈ 𝒜 𝜆 ⁢ ( 𝑤 ¯ ) 𝑋 𝑏 𝑖 ⁢ 𝑤 ¯ 𝑏 𝑖

𝑦 ^

∑ 𝑏 𝑖 ∈ 𝒜 𝜆 ⁢ ( 𝑤 ) 𝑋 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖

⟹ ∑ 𝑏 𝑖 ∈ 𝒮 𝜆 ∖ 𝒜 𝜆 ⁢ ( 𝑤 ) 𝑋 𝑏 𝑖 ⁢ 𝑤 ¯ 𝑏 𝑖 + ∑ 𝑏 𝑖 ∈ 𝒜 𝜆 ⁢ ( 𝑤 ) 𝛽 𝑏 𝑖 ⁢ 𝑋 𝑏 𝑖 ⁢ 𝑤 ¯ 𝑏 𝑖

0 ,

where 𝛽 𝑏 𝑖

1 − 𝛼 𝑏 𝑖 𝛼 ¯ 𝑏 𝑖 for 𝑤 𝑏 𝑖

𝛼 𝑏 𝑖 ⁢ 𝑣 𝑏 𝑖 , 𝑤 ¯ 𝑏 𝑖

𝛼 ¯ 𝑏 𝑖 ⁢ 𝑣 𝑏 𝑖 . Thus, { 𝑋 𝑏 𝑖 ⁢ 𝑤 ¯ 𝑏 𝑖 } are linearly dependent and it is possible to prune the solution.

Now we show that we can, in fact, prune all vectors in 𝒮 𝜆 ∖ 𝒜 𝜆 ⁢ ( 𝑤 ) in one pruning step. First, observe that 𝛼 𝑏 𝑖 𝛼 ¯ 𝑏 𝑖

0 so that 𝛽 𝑏 𝑖 < 1 for every 𝑏 𝑖 ∈ 𝒜 𝜆 ⁢ ( 𝑤 ) . Following the proof of Proposition A.6, define

𝑤 𝑏 𝑖 𝑡

( 1 − 𝑡 ⁢ 𝛽 𝑏 𝑖 ) ⁢ 𝑤 ¯ 𝑏 𝑖

( 1 − 𝑡 ⁢ 𝛽 𝑏 𝑖 ) ⁢ 𝛼 ¯ 𝑏 𝑖 ⁢ 𝑣 𝑏 𝑖 ,

for 0 < 𝑡 < 1 . Since 𝛽 𝑏 𝑖 < 1 for every 𝑏 𝑖 ∈ 𝒮 𝜆 , it is straightforward to deduce that 𝑤 𝑏 𝑖 𝑡 is optimal by Section 3.1. Arguing as in Proposition A.6, we can show 𝑤 1 is also optimal. It remains only to notice that 𝑤 𝑏 𝑖 1

0 for 𝑏 𝑖 ∈ 𝒮 𝜆 ∖ 𝒜 𝜆 ⁢ ( 𝑤 ) and 𝑤 𝑏 𝑖 1

𝑤 𝑏 𝑖 for 𝑏 𝑖 ∈ 𝒜 𝜆 ⁢ ( 𝑤 ) . Thus, the pruning algorithm can move from 𝑤 ¯ to 𝑤 in one step. ∎

\minimalSolCharacterization

Proof.

Suppose 𝑤 and 𝑤 ′ are two minimal solutions. Both can be obtained by pruning the maximal solution with support 𝒮 𝜆 (Lemma A.11). Thus, 𝑤 and 𝑤 ′ both span Span ⁢ ( { 𝑋 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 } ) by Lemma A.8. Lemma A.9 now implies 𝑤 and 𝑤 ′ have the same number of active blocks. This number must be 𝑐 , otherwise there would be a linearly dependent vector in { 𝑋 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 } 𝒜 𝜆 ⁢ ( 𝑤 ) and 𝑤 would not be minimal. This completes the proof. ∎

A.4Continuity of the Solution Path {restatable}

lemmaboundedSolutionsCGL Every solution to the constrained group lasso problem is bounded by an absolute constant independent of 𝜆 . Specifically, every 𝑤 ∈ 𝒲 * ⁢ ( 𝜆 ) satisfies

∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 𝑏 𝑖 ‖ 2 ≤ ∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 ¯ 𝑏 𝑖 ‖ 2 .

where 𝑤 ¯ ∈ 𝒲 * ⁢ ( 0 ) is the least-squares solution with minimum ℓ 2 -norm.

Proof.

Let ℎ ⁢ ( 𝑤 )

∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 𝑏 𝑖 ‖ 2 , and define 𝑊 𝑔 to be the set of least squares solutions with minimum group norm,

𝑊 𝑔

arg ⁢ min { ℎ ⁢ ( 𝑤 ) : 𝑤 ∈ 𝒲 * ⁢ ( 0 ) } .

Let 𝑤 𝑔 ∈ 𝑊 𝑔 , and suppose that ℎ ⁢ ( 𝑤 𝑔 ) < ℎ ⁢ ( 𝑤 ⁢ ( 𝜆 ) ) for some 𝜆

0 , 𝑤 ∈ 𝒲 * ⁢ ( 𝜆 ) . Since

1 2 ⁢ ‖ 𝑋 ⁢ 𝑤 𝑔 − 𝑦 ‖ 2 2 ≤ 1 2 ⁢ ‖ 𝑋 ⁢ 𝑤 ⁢ ( 𝜆 ) − 𝑦 ‖ 2 2

we deduce

1 2 ⁢ ‖ 𝑋 ⁢ 𝑤 𝑔 − 𝑦 ‖ 2 2 + 𝜆 ⁢ ℎ ⁢ ( 𝑤 𝑔 ) ⁢ < 1 2 ∥ ⁢ 𝑋 ⁢ 𝑤 ⁢ ( 𝜆 ) − 𝑦 ∥ 2 2 + 𝜆 ⁢ ℎ ⁢ ( 𝑤 ⁢ ( 𝜆 ) ) ,

which is a contradiction. So ℎ ⁢ ( 𝑤 ⁢ ( 𝜆 ) ) ≤ ℎ ⁢ ( 𝑤 𝑔 ) for all 𝜆

0 . Observing ℎ ⁢ ( 𝑤 𝑔 ) ≤ ℎ ⁢ ( 𝑤 ¯ ) since 𝑤 ¯ may not be in 𝑊 𝑔 gives the result. Since ℎ ⁢ ( 𝑤 ¯ ) is independent of 𝜆 , we conclude that 𝒲 * ⁢ ( 𝜆 ) is bounded independent of 𝜆 . ∎

\valueContinuityCGL

Proof.

Define the joint objective function

𝑓 ⁢ ( 𝑤 , 𝜆 )

1 2 ⁢ ‖ 𝑋 ⁢ 𝑤 − 𝑦 ‖ 2 2 + 𝜆 ⁢ ∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 𝑏 𝑖 ‖ 2 .

Clearly 𝑓 ⁢ ( 𝑤 , 𝜆 ) is jointly continuous in 𝑤 and 𝜆 . By Section A.4, minimization of 𝑓 ⁢ ( 𝑤 , 𝜆 ) subject to 𝐾 𝑏 𝑖 ⊤ ⁢ 𝑤 𝑏 𝑖 ≤ 0 is equivalent to the constrained minimization problem,

𝑝 * ⁢ ( 𝜆 )

min 𝑤 ⁡ 𝑓 ⁢ ( 𝑤 , 𝜆 ) s.t. ⁢ ∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 𝑏 𝑖 ‖ 2 ≤ 𝐶 , 𝐾 𝑏 𝑖 ⊤ ⁢ 𝑤 𝑏 𝑖 ≤ 0 ,

where 𝐶 is a finite absolute constant. Note that this expression is also valid when 𝜆

0 as the min-norm solution to the unregularized least squares problem obeys the constraint.

Thus, 𝒲 * is a continuous optimization problem over a continuous (constant in this case) compact constraint set and the classical result of Berge (1997) (see also Hogan (1973)[Theorem 7]) implies 𝑝 * is continuous. ∎

\mapContinuityCGL

Proof.

Joint continuity of the objective

𝑓 ⁢ ( 𝑤 , 𝜆 )

1 2 ⁢ ‖ 𝑋 ⁢ 𝑤 − 𝑦 ‖ 2 2 + 𝜆 ⁢ ∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 𝑏 𝑖 ‖ 2 ,

combined with continuity of the (constant) constraint allows us to use Robinson & Day (1974, Theorem 1) to obtain that that 𝒲 * is upper semi-continuous. Since 𝒲 * is convex and bounded, it is compact. It is thus also uniformly compact and upper semi-continuity is equivalent to closedness (Hogan, 1973)[Theorem 3]. We conclude that 𝒲 * is closed as claimed.

If 𝑋 is full column rank, then the constrained group lasso solution is unique for all 𝜆 ≥ 0 . The solution map is a singleton on ℝ + , and closedness and openness are equivalent properties for singleton maps. Since we have already shown it is closed, the solution map must also be open. An identical argument shows that the solution map is open at on any interval over which the solution is unique.

Now we show the reverse implication by proving the contrapositive. Assume 𝑋 is not full column-rank and suppose 𝐾 𝑏 𝑖

0 for each 𝑏 𝑖 ∈ ℬ . The solution map at 𝜆

0 is the solution set to the least squares problem,

min 𝑤 ⁡ 1 2 ⁢ ‖ 𝑋 ⁢ 𝑤 − 𝑦 ‖ 2 2 ,

which is known to be 𝒲 * ⁢ ( 0 )

{ 𝑤 * ⁢ ( 0 ) + 𝑧 : 𝑧 ∈ Null ⁢ ( 𝑋 ) } . While 𝒲 * ⁢ ( 0 ) is unbounded, it holds that 𝒲 * ⁢ ( 𝜆 ) ⊂ 𝐶 for some bounded 𝐶 for every 𝜆

0 (Section A.4). As a result, there exist uncountably many solutions in 𝒲 * ⁢ ( 0 ) which are not limit points of solutions in 𝒲 * ⁢ ( 𝜆 𝑘 ) as 𝜆 𝑘 → 0 . In other words, 𝒲 * ⁢ ( 0 ) is not open at 0 . ∎

\modelFitContinuity

Proof.

Consider the dual problem from Lemma A.4,

max 𝜂

− 1 2 ⁢ ( 𝜂 − 𝑋 ⊤ ⁢ 𝑦 ) ⁢ ( 𝑋 ⊤ ⁢ 𝑋 ) + ⁢ ( 𝜂 − 𝑋 ⊤ ⁢ 𝑦 ) + 1 2 ⁢ ‖ 𝑦 ‖ 2 2

s.t. 𝜂 ∈ Row ⁢ ( 𝑋 ) , ‖ 𝜂 𝑏 𝑖 ‖ 2 ≤ 𝜆 ⁢ ∀ 𝑏 𝑖 ∈ ℬ .

The objective function is a convex quadratic and continuous in 𝜂 . The constraint set is

𝒞 ⁢ ( 𝜆 )

{ 𝜂 : 𝜂 ∈ Row ( 𝑋 ) , : ∥ 𝜂 𝑏 𝑖 ∥ 2 ≤ 𝜆 ∀ 𝑏 𝑖 ∈ ℬ } .

Let’s show that 𝒞 is continuous.

Let 𝜆 𝑘 ≥ 0 , 𝜆 𝑘 → 𝜆 ¯ and 𝜂 𝑘 ∈ 𝒞 ⁢ ( 𝜆 𝑘 ) such that 𝜂 𝑘 → 𝜂 ¯ . Since 𝜂 𝑘 ∈ Row ⁢ ( 𝑋 ) , 𝜂 ¯ ∈ Row ⁢ ( 𝑋 ) . Moreover,

‖ [ 𝜂 𝑘 ] 𝑏 𝑖 ‖ 2 ≤ 𝜆 𝑘 ,

so that taking limits on both sides implies ‖ 𝜂 ¯ 𝑘 ‖ 2 ≤ 𝜆 ¯ . Thus, 𝜂 ¯ ∈ 𝒞 ⁢ ( 𝜆 ¯ ) , showing that 𝒞 is closed.

Hogan (1973, Theorem 12) states that 𝒞 ⁢ ( 𝜆 ) is open at 𝜆 ¯ if for each 𝑏 𝑖 ∈ ℬ , 𝑔 𝑏 𝑖 ⁢ ( 𝜆 , 𝜂 )

‖ 𝜂 𝑏 𝑖 ‖ 2 − 𝜆 is continuous on 𝜆 ¯ × 𝒞 ⁢ ( 𝜆 ) , convex in 𝜂 , and for fixed 𝜆 , and there exists 𝜂 ¯ such that such that 𝑔 ⁢ ( 𝜆 , 𝜂 ¯ ) < 0 .

Let us check these conditions. First, observe that 𝑔 𝑏 𝑖 is continuous and convex in 𝜂 for any choice of 𝜆 . Taking 𝜂 ¯

0 , we find

𝑔 𝑏 𝑖 ⁢ ( 𝜆 , 0 )

− 𝜆 < 0 ,

as long as 𝜆

0 . Thus, 𝒞 ⁢ ( 𝜆 ) is open at each 𝜆

0 .

At 𝜆

0 , 𝒞 ⁢ ( 𝜆 )

{ 0 } . Since 𝒞 is closed everywhere, we conclude it is open at 𝜆

0 . Putting these results together proves that 𝒞 is continuous.

Recall that the dual solution satisfies 𝜂 𝑏 𝑖 *

𝑐 𝑏 𝑖 , so that it is always unique. Combining this fact with Robinson & Day (1974, Theorem 1) implies that 𝜆 ↦ 𝜂 * ⁢ ( 𝜆 ) is a continuous function. Since we have

𝜂 * ⁢ ( 𝜆 )

𝑐 ⁢ ( 𝜆 )

𝑋 ⊤ ⁢ ( 𝑦 − 𝑋 ⁢ 𝑤 * ⁢ ( 𝜆 ) ) ,

it must be that the model fit 𝑦 ^ ⁢ ( 𝜆 )

𝑋 ⁢ 𝑤 * ⁢ ( 𝜆 ) is continuous as well (any discontinuities must be in Null ⁢ ( 𝑋 ) , but 𝑦 ^ is orthogonal to Null ⁢ ( 𝑋 ) ).

Finally, using Definition 3.6, we have

𝑝 * ⁢ ( 𝜆 ) − 1 2 ⁢ ‖ 𝑦 ^ ⁢ ( 𝜆 ) − 𝑦 ‖ 2 2

𝜆 ⁢ ∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 𝑏 𝑖 ‖ 2 ,

is a sum of continuous functions and thus continuous. Writing

𝑔 ⁢ ( 𝜆 )

∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 𝑏 𝑖 ‖ 2

[ 𝜆 ⁢ ∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 𝑏 𝑖 ‖ 2 ] ⁢ [ 1 𝜆 ] ,

as the product of continuous functions shows 𝑔 ⁢ ( 𝜆 ) is continuous at every 𝜆

0 . ∎

A.5The Min-Norm Path Proposition A.12.

Consider the min group-norm interpolation problem,

min 𝑤 ⁢ ∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 𝑏 𝑖 ‖ 2 s.t. ⁢ 𝑋 ⁢ 𝑤

𝑦 .

There exist 𝑋 , 𝑦 such that the minimum-group-norm solution to this problem is unique and not in 𝑅𝑜𝑤 ⁢ ( 𝑋 𝒜 𝜆 * ) .

Proof.

We provide a counter-example where the solution is not the row space of the active set. Choose

𝑋

[ 1

2

0

1
0
2 ] , 𝑦

[ 1

1 ] ,

where the vertical line indicates the block structure, i.e., 𝑏 1

{ 1 , 2 } and 𝑏 2

{ 3 } .

Clearly a solution using only 𝑏 2 cannot interpolate the data, so the active set must be { 𝑏 1 , 𝑏 2 } or { 𝑏 1 } . If the active set is 𝑏 1 , then the minimum norm interpolating solution can only be 𝑤

[ 1 0 0 ] ⊤ , which has group norm 1 .

Now, consider when the active set is { 𝑏 1 , 𝑏 2 } . The interpolating solution in Row ⁢ ( 𝑋 ) satisfies the following system

[ 1

2

0

1

0

2 ] ⁢ ( 𝛼 ⁢ [ 1

2

0 ] + 𝛽 ⁢ [ 1

0

2 ] )

[ 1

1 ]

⟹ [ 5 ⁢ 𝛼 + 𝛽

𝛼 + 5 ⁢ 𝛽 ]

[ 1

1 ] .

Solving for 𝛼 and 𝛽 yields 𝛼

1 − 5 ⁢ 𝛽 and 24 ⁢ 𝛽

4 , which implies 𝛽

1 / 6 and 𝛼

1 / 6 . The optimal 𝑤 * is thus

𝑤 *

[ 1 / 3

1 / 3

1 / 3 ] ,

and the group norm of 𝑤 * is

∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 𝑏 𝑖 * ‖ 2

2 / 9 + 1 / 3

( 1 + 2 ) / 3 < 1 .

Thus, we can discount the interpolating solution using only 𝑏 1 .

Now let’s see if we can reduce the norm by including directions in Null ⁢ ( 𝑋 ) . The Null space is orthogonal to both rows of 𝑋 , from which we conclude

Null ⁢ ( 𝑋 )

{ 𝛾 ⁢ 𝑧 : 𝑧

[ − 2 / 3

1 / 3

1 / 3 ] , 𝛾 ∈ ℝ } .

Any vector 𝑤 ′

𝑤 * + 𝛾 ⁢ 𝑧 is an interpolating solution, so it only remains to check if there is a choice of 𝛾 that decreases the group norm. Assuming 𝛾

− 1 ,

∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 𝑏 𝑖 * ‖ 2
≤ ∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 𝑏 𝑖 ′ ‖ 2

⇔ 1 + 2 3

( 1 3 − 2 ⁢ 𝛾 3 ) 2 + ( 1 3 + 𝛾 3 ) 2 + | 1 + 𝛾 3 |

⇔ 1 + 2 3 − 1 + 𝛾 3

≤ ( 1 3 − 2 ⁢ 𝛾 3 ) 2 + ( 1 3 + 𝛾 3 ) 2

(since 𝛾

− 1 )

⇔ ( 1 + 2 3 − 1 + 𝛾 3 ) 2

≤ ( 1 3 − 2 ⁢ 𝛾 3 ) 2 + ( 1 3 + 𝛾 3 ) 2

⇔ ( 2 − 𝛾 ) 2

≤ ( 1 − 2 ⁢ 𝛾 ) 2 + ( 1 + 𝛾 ) 2

The left-hand side satisfies

( 2 − 𝛾 ) 2

2 − 2 ⁢ 2 ⁢ 𝛾 + 𝛾 2 ,

while the right-hand side is

( 1 − 2 ⁢ 𝛾 ) 2 + ( 1 + 𝛾 ) 2

1 − 4 ⁢ 𝛾 + 4 ⁢ 𝛾 2 + 1 + 2 ⁢ 𝛾 + 𝛾 2

2 − 2 ⁢ 𝛾 + 5 ⁢ 𝛾 2 .

As a result,

∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 𝑏 𝑖 * ‖ 2

≤ ∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 𝑏 𝑖 ′ ‖ 2

⇔ 2 − 2 ⁢ 𝛾 + 5 ⁢ 𝛾 2 − 2 − 𝛾 2 + 2 ⁢ 2 ⁢ 𝛾

≥ 0

⇔ 2 ⁢ ( 2 − 1 ) ⁢ 𝛾 + 4 ⁢ 𝛾 2

≥ 0 .

However, it is easy to check that this fails for 𝛾 ∈ ( ( 1 − 2 ) / 2 , 0 ) . So the minimum-group-norm interpolating solution is not in Row ⁢ ( 𝑋 𝒜 𝜆 * ) .

Now let’s show that the minimum-group-norm solution is unique. This holds if the group norm as a function of 𝛾 ,

𝑔 ⁢ ( 𝛾 )

( 1 3 − 2 ⁢ 𝛾 3 ) 2 + ( 1 3 + 𝛾 3 ) 2 + | 1 + 𝛾 3 | ,

is strictly convex. The function ℎ 2 ⁢ ( 𝛾 )

| 1 + 𝛾 3 | is convex, so we need only show that

ℎ 1 ⁢ ( 𝛾 )

( 1 3 − 2 ⁢ 𝛾 3 ) 2 + ( 1 3 + 𝛾 3 ) 2

1 3 ⁢ 2 − 2 ⁢ 𝛾 + 5 ⁢ 𝛾 2 ,

is strictly convex. Taking the second derivative, we find

ℎ 1 ′′ ⁢ ( 𝛾 )

3 ( 2 − 2 ⁢ 𝛾 + 5 ⁢ 𝛾 2 ) 3 / 2

0

for all 𝛾 . This completes the proof. ∎

Lemma A.13.

Let 𝑊 𝑔 be the set of least squares solutions with minimum group norm. That is,

𝑊 𝑔

arg ⁢ min 𝑤 { ∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 𝑏 𝑖 ∥ 2 : 𝑋 ⊤ ⁢ 𝑋 ⁢ 𝑤

𝑋 ⊤ ⁢ 𝑦 } .

Then every limit point of the min-norm group lasso solution as 𝜆 → 0 lies in 𝑊 𝑔 .

Proof.

Let 𝜆 𝑘 → 0 and observe that 𝑤 * ⁢ ( 𝜆 𝑘 ) has at least one limit point since it is bounded (Section A.4). Since ‖ 𝑐 𝑏 𝑖 ⁢ ( 𝜆 𝑘 ) ‖ 2 ≤ 𝜆 𝑘 , we see that lim 𝑘 ‖ 𝑐 𝑏 𝑖 ⁢ ( 𝜆 𝑘 ) ‖ 2

0 and thus lim 𝑘 𝑐 𝑏 𝑖 ⁢ ( 𝜆 𝑘 )

0 .

FO optimality conditions imply

( 𝑋 ⊤ ⁢ 𝑋 ) ⁢ 𝑤 * ⁢ ( 𝜆 )

𝑋 ⊤ ⁢ 𝑦 − 𝑐 ⁢ ( 𝜆 ) ,

(23)

which, taking limits on both sides, gives

lim 𝑘 ( 𝑋 ⊤ ⁢ 𝑋 ) ⁢ 𝑤 * ⁢ ( 𝜆 𝑘 )

𝑋 ⊤ ⁢ 𝑦 .

(24)

That is, every limit point 𝑤 ¯ of 𝑤 * ⁢ ( 𝜆 𝑘 ) is a least squares solution satisfying ℎ ⁢ ( 𝑤 ¯ ) ≤ ℎ ⁢ ( 𝑤 𝑔 ) . We conclude that 𝑤 ¯ ∈ 𝑊 𝑔 . ∎

\rowCE

Proof.

Consider the setting of Proposition A.12, with

𝑋

[ 1

2

0

1
0
2 ] , 𝑦

[ 1

1 ] ,

where the vertical line indicates the block structure, i.e., 𝑏 1

{ 1 , 2 } and 𝑏 2

{ 3 } . We have shown that the min group norm interpolant is unique, is supported on 𝑏 1 and 𝑏 2 , and does not lie in 𝑅 ⁢ 𝑜 ⁢ 𝑤 ⁢ ( 𝑋 ) . Let 𝑤 𝑔 be this solution.

Let 𝜆 𝑘 ↓ 0 . By Lemma A.13, every limit point of 𝑤 * ⁢ ( 𝜆 𝑘 )

𝑤 𝑔 . Thus, lim 𝑘 𝑤 * ⁢ ( 𝜆 𝑘 ) exists and is exactly 𝑤 𝑔 . Moreover, 𝑤 * ⁢ ( 𝜆 𝑘 ) must be supported on 𝑏 1 and 𝑏 2 for all 𝑘 sufficiently large.

Decomposing 𝑤 𝑔

𝑎 + 𝑏 and 𝑤 * ⁢ ( 𝜆 𝑘 )

𝑟 𝑘 + 𝑛 𝑘 where 𝑎 , 𝑟 𝑘 ∈ Row ⁢ ( 𝑋 ) and 𝑏 , 𝑛 𝑘 ∈ Null ⁢ ( 𝑋 ) , we see that

‖ 𝑤 𝑔 − 𝑤 * ⁢ ( 𝜆 𝑘 ) ‖ 2 2

‖ 𝑎 − 𝑟 𝑘 ‖ 2 2 + ‖ 𝑏 − 𝑛 𝑘 ‖ 2 2 → 0 ,

implying that 𝑛 𝑘 ≠ 0 for sufficiently large 𝑘 . In other words, the min-norm solution to the group lasso problem fails to fall in Row ⁢ ( 𝑋 ) for some 𝜆

0 . ∎

\minNormProgram

Proof.

Let 𝑤 ∈ 𝒲 * ⁢ ( 𝜆 ) . By Section 3.1, 𝑤 𝑏 𝑖

𝛼 𝑏 𝑖 ⁢ 𝑣 𝑏 𝑖 where 𝛼 𝑏 𝑖 ≥ 0 . Moreover, 𝛼 𝑏 𝑖

0 for every 𝑏 𝑖 ∈ ℬ ∖ 𝒮 𝜆 . As a result,

‖ 𝑤 ‖ 2 2

‖ 𝑤 ℰ 𝜆 ‖ 2 2

∑ 𝑏 𝑖 ∈ 𝒮 𝜆 ‖ 𝛼 𝑏 𝑖 ⁢ 𝑣 𝑏 𝑖 ‖ 2 2

𝜆 ⁢ ‖ 𝛼 ‖ 2 2 ,

where the last equality follows from 𝑏 𝑖 ∈ 𝒮 𝜆 ⟹ 𝑏 𝑖 ∈ ℰ 𝜆 , which enforces ‖ 𝑣 𝑏 𝑖 ‖ 2

𝜆 .

Now suppose 𝛼 * is optimal for the cone program and let 𝑤 ∈ ℝ 𝑑 such that 𝑤 𝑏 𝑖

𝛼 𝑏 𝑖 * ⁢ 𝑣 𝑏 𝑖 . By construction, 𝛼 𝑏 𝑖 *

0 for all 𝑏 𝑖 ∈ ℬ ∖ 𝒮 𝜆 (or it could not be optimal) so that 𝑤 𝑏 𝑖

0 for all 𝑏 𝑖 ∈ ℬ ∖ 𝒮 𝜆 . Moreover,

𝑋 ⁢ 𝑤

∑ 𝑏 𝑖 ∈ 𝒮 𝜆 𝛼 𝑏 𝑖 * ⁢ 𝑋 𝑏 𝑖 ⁢ 𝑣 𝑏 𝑖

𝑦 ^ ,

Thus, 𝑤 solves

arg ⁢ min 𝑤 ‖ 𝑤 ‖ 2 2 ⁢  s.t.
∀ 𝑏 𝑖 ∈ 𝒮 𝜆 , 𝑤 𝑏 𝑖

𝛼 𝑏 𝑖 ⁢ 𝑣 𝑏 𝑖 , 𝛼 𝑏 𝑖 ≥ 0 ,

∀ 𝑏 𝑗 ∈ ℬ ∖ 𝒮 𝜆 , 𝑤 𝑏 𝑗

0 , 𝑋 ⁢ 𝑤

𝑦 ^ .

Invoking Section 3.1 now proves that 𝑤 is the min-norm solution. ∎

{restatable}

lemmal2Reformulation The ℓ 2 -penalized group lasso problem in Equation 17 is equivalent to the following CGL problem:

min 𝑤

1 2 ⁢ ‖ 𝑋 ~ ⁢ 𝑤 − 𝑦 ~ ‖ 2 2 + 𝜆 ⁢ ∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 𝑏 𝑖 ‖ 2

(25)

s.t. 𝐾 𝑏 𝑖 ⊤ ⁢ 𝑤 𝑏 𝑖 ≤ 0 ⁢  for all  ⁢ 𝑏 𝑖 ∈ ℬ .

where we have defined the extended data matrix and targets

𝑋 ~

[ 𝑋

𝛿 ⁢ 𝐼 ] 𝑦 ~

[ 𝑦

0 ] .

Moreover, 𝑋 ~ is full column-rank and thus the CGL solution is unique.

Proof.

It is straightforward to show the equivalence by direct calculation. For any 𝑤 ∈ ℝ 𝑑 ,

1 2 ⁢ ‖ 𝑋 ~ ⁢ 𝑤 − 𝑦 ~ ‖ 2 2

1 2 ⁢ ‖ 𝑋 ⁢ 𝑤 − 𝑦 ‖ 2 2 + 1 2 ⁢ ‖ 𝛿 ⁢ 𝐼 ⁢ 𝑤 − 0 ‖ 2 2

1 2 ⁢ ‖ 𝑋 ⁢ 𝑤 − 𝑦 ‖ 2 2 + 𝛿 2 ⁢ ‖ 𝑤 ‖ 2 2 ,

Substituting this identity into Equation 25 establishes the equivalence.

It is clear by inspection that 𝑋 ~ is full column rank. Then Null ⁢ ( 𝑋 𝒞 )

∅ for all 𝒞 ⊂ ℬ and the solution is unique by Section 3.1. ∎

\penConvergence

Proof.

First we show that ‖ 𝑤 𝛿 ⁢ ( 𝜆 ) ‖ 2 ≤ ‖ 𝑤 * ⁢ ( 𝜆 ) ‖ 2 . Suppose by way of contradiction that ‖ 𝑤 𝛿 ⁢ ( 𝜆 ) ‖ 2

‖ 𝑤 * ⁢ ( 𝜆 ) ‖ 2 for some 𝛿

0 . Since

1 2 ⁢ ‖ 𝑋 ⁢ 𝑤 * ⁢ ( 𝜆 ) − 𝑦 ‖ 2 2 + 𝜆 ⁢ ∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 𝑏 𝑖 * ⁢ ( 𝜆 ) ‖ 2

min 𝑤 : 𝐾 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 ≤ 0 ⁡ 1 2 ⁢ ‖ 𝑋 ⁢ 𝑤 − 𝑦 ‖ 2 2 + 𝜆 ⁢ ∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 𝑏 𝑖 ‖ 2

≤ 1 2 ⁢ ‖ 𝑋 ⁢ 𝑤 𝛿 ⁢ ( 𝜆 ) − 𝑦 ‖ 2 2 + 𝜆 ⁢ ∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 𝑏 𝑖 𝛿 ⁢ ( 𝜆 ) ‖ 2 ,

we deduce

1 2 ⁢ ‖ 𝑋 ⁢ 𝑤 * ⁢ ( 𝜆 ) − 𝑦 ‖ 2 2 + 𝜆 ⁢ ∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 𝑏 𝑖 * ⁢ ( 𝜆 ) ‖ 2 + 𝛿 2 ⁢ ‖ 𝑤 * ⁢ ( 𝜆 ) ‖ 2 2 ⁢ < 1 2 ∥ ⁢ 𝑋 ⁢ 𝑤 𝛿 ⁢ ( 𝜆 ) − 𝑦 ∥ 2 2 + 𝜆 ⁢ ∑ 𝑏 𝑖 ∈ ℬ ‖ [ 𝑤 𝛿 ⁢ ( 𝜆 ) ] 𝑏 𝑖 ‖ 2 + 𝛿 2 ⁢ ‖ 𝑤 𝛿 ⁢ ( 𝜆 ) ‖ 2 2 ,

which contradicts optimality of 𝑤 𝛿 ⁢ ( 𝜆 ) . So ‖ 𝑤 𝛿 ⁢ ( 𝜆 ) ‖ 2 ≤ ‖ 𝑤 * ⁢ ( 𝜆 ) ‖ 2 for all 𝛿

0 . As a result, the sequence { 𝑤 𝛿 𝑘 ⁢ ( 𝜆 ) } 𝛿 𝑘 , where 𝛿 𝑘 ↓ 0 , is bounded and admits at least one convergent subsequence. Let 𝑤 ¯ ⁢ ( 𝜆 ) be the limit point associated with one such subsequence; clearly ‖ 𝑤 ¯ ⁢ ( 𝜆 ) ‖ 2 ≤ ‖ 𝑤 ⁢ ( 𝜆 ) * ‖ 2 .

Let’s show that 𝑤 ¯ ⁢ ( 𝜆 ) is a solution to the group lasso problem by checking the KKT conditions. Suppose 𝜆

0 . Stationarity of the Lagrangian is

𝑋 ⊤ ⁢ ( 𝑋 ⁢ 𝑤 𝛿 𝑘 ⁢ ( 𝜆 ) − 𝑦 ) + 𝐾 ⁢ 𝜌 𝛿 𝑘 ⁢ ( 𝜆 ) + 𝑠 𝛿 𝑘 ⁢ ( 𝜆 ) + 𝛿 𝑘 ⁢ 𝑤 𝛿 𝑘 ⁢ ( 𝜆 )

0 ,

where 𝑠 𝑏 𝑖 𝛿 𝑘 ⁢ ( 𝜆 ) ∈ ∂ 𝜆 ⁢ ‖ 𝑤 𝑏 𝑖 𝛿 𝑘 ‖ 2 . Since ‖ 𝑠 𝑏 𝑖 𝛿 𝑘 ⁢ ( 𝜆 ) ‖ 2 ≤ 𝜆 and 𝑤 𝛿 𝑘 ⁢ ( 𝜆 ) is bounded, clearly 𝐾 ⁢ 𝜌 𝛿 𝑘 ⁢ ( 𝜆 ) is also bounded.

Dropping to a subsequence if necessary, let lim 𝑘 𝑤 𝛿 𝑘 ⁢ ( 𝜆 )

𝑤 ¯ and lim 𝑘 𝐾 𝑏 𝑖 ⁢ 𝜌 𝑏 𝑖 𝛿 𝑘

𝑧 ¯ 𝑏 𝑖 . Define

𝑅 1 / 𝑛

{ 𝜌 𝑏 𝑖 : ‖ 𝐾 𝑏 𝑖 ⁢ 𝜌 𝑏 𝑖 − 𝑧 ¯ 𝑏 𝑖 ‖ ∞ ≤ 1 𝑛 , 𝜌 𝑏 𝑖 ≥ 0 } .

The sequence of sets 𝑅 1 / 𝑛 is polyhedral and thus retractive. Moreover, for each 𝑛 ∈ ℕ , there exists 𝑘 such that

‖ 𝐾 𝑏 𝑖 ⁢ 𝜌 𝑏 𝑖 𝛿 𝑘 − 𝑧 ¯ 𝑏 𝑖 ‖ ∞ ≤ 1 / 𝑛 ,

since 𝐾 𝑏 𝑖 ⁢ 𝜌 𝑏 𝑖 𝛿 𝑘 → 𝑧 ¯ 𝑏 𝑖 . Recalling 𝜌 𝑏 𝑖 𝛿 𝑘 ≥ 0 shows that ℝ 1 / 𝑛 is non-empty. The limit of a sequence of nested, non-empty, retractive sets is also non-empty (Bertsekas, 2009, Proposition 1.4.10). Moreover, since the limit is exactly

𝑅 ¯

{ 𝜌 𝑏 𝑖 : 𝐾 𝑏 𝑖 ⁢ 𝜌 𝑏 𝑖

𝑧 ¯ 𝑏 𝑖 , 𝜌 𝑏 𝑖 ≥ 0 } ,

we deduce that there exists 𝜌 ¯ ≥ 0 such that 𝐾 𝑏 𝑖 ⁢ 𝜌 ¯ 𝑏 𝑖

𝑧 ¯ 𝑏 𝑖 .

Taking limits on either side of the stationarity condition, we find

𝑋 𝑏 𝑖 ⊤ ⁢ ( 𝑦 − 𝑋 ⁢ 𝑤 ¯ ⁢ ( 𝜆 ) ) − 𝐾 𝑏 𝑖 ⁢ 𝜌 ¯ ⁢ ( 𝜆 )

𝑠 ¯ 𝑏 𝑖 ,

where the limit point 𝑠 ¯ 𝑏 𝑖 satisfies ‖ 𝑠 ¯ 𝑏 𝑖 ‖ ≤ 𝜆 . If 𝑏 𝑖 ∈ ℬ ∖ 𝒜 𝜆 ⁢ ( 𝑤 ¯ ⁢ ( 𝜆 ) ) , then 𝑤 ¯ 𝑏 𝑖 satisfies stationarity.

Let 𝑏 𝑖 ∈ 𝒜 𝜆 ⁢ ( 𝑤 ¯ ⁢ ( 𝜆 ) ) . Since 𝑤 𝛿 𝑘 ⁢ ( 𝜆 ) → 𝑤 ¯ ⁢ ( 𝜆 ) , ‖ 𝑤 𝑏 𝑖 𝛿 𝑘 − 𝑤 ¯ 𝑏 𝑖 ‖ 2 → 0 and it must happen that 𝑤 𝑏 𝑖 𝛿 𝑘

0 for all 𝑘 sufficiently large. That is, 𝒜 ⁢ ( 𝑤 𝛿 𝑘 ⁢ ( 𝜆 ) ) ⊇ 𝒜 ⁢ ( 𝑤 ¯ ) for all 𝑘 ≥ 𝑘 ′ . Using 𝑏 𝑖 ∈ 𝒜 ⁢ ( 𝑤 𝛿 𝑘 ⁢ ( 𝜆 ) ) provides a closed-form expression for 𝑠 𝑏 𝑖 𝛿 𝑘 :

lim 𝑘 𝑠 𝛿 𝑘 ⁢ ( 𝜆 )

𝜆 ⁢ lim 𝑘 𝑤 𝑏 𝑖 𝛿 𝑘 ⁢ ( 𝜆 ) ‖ 𝑤 𝑏 𝑖 𝛿 𝑘 ⁢ ( 𝜆 ) ‖ 2

𝜆 ⁢ 𝑤 ¯ 𝑏 𝑖 ⁢ ( 𝜆 ) ‖ 𝑤 ¯ 𝑏 𝑖 ⁢ ( 𝜆 ) ‖ 2 ,

which shows that 𝑠 ¯ 𝑏 𝑖 is a subgradient of 𝜆 ⁢ ‖ 𝑤 𝑏 𝑖 ‖ 2 . We conclude that the Lagrangian is stationary in 𝑤 ¯ 𝑏 𝑖 as well.

Let us check the remainder of the KKT conditions. For feasibility, it is straightforward to observe that

𝐾 𝑏 𝑖 ⊤ ⁢ 𝑤 𝑏 𝑖 𝛿 𝑘 ⁢ ( 𝜆 ) ≤ 0 ∀ 𝑘 ⟹ 𝐾 𝑏 𝑖 ⊤ ⁢ 𝑤 ¯ 𝑏 𝑖 ⁢ ( 𝜆 ) ≤ 0 .

Similarly,

⟨ 𝜌 𝑏 𝑖 𝛿 𝑘 , 𝐾 𝑏 𝑖 ⊤ ⁢ 𝑤 𝑏 𝑖 𝛿 𝑘 ⟩

0 ∀ 𝑘 ⟹ ⟨ 𝜌 ¯ 𝑏 𝑖 , 𝐾 𝑏 𝑖 ⊤ ⁢ 𝑤 ¯ 𝑏 𝑖 ⟩

0 ,

which, combined with 𝜌 ¯ ≥ 0 , is sufficient to establish complementary slackness. We have shown the subsequential limits ( 𝑤 ¯ , 𝜌 ¯ ) satisfies the KKT conditions and thus 𝑤 ¯ is a solution to the constrained group lasso problem.

Since the min-norm solution is unique and ‖ 𝑤 ¯ ⁢ ( 𝜆 ) ‖ 2 ≤ ‖ 𝑤 * ⁢ ( 𝜆 ) ‖ 2 , it must be that 𝑤 ¯ ⁢ ( 𝜆 )

𝑤 * ⁢ ( 𝜆 ) . Noting that this holds for every limit point implies lim 𝛿 ↓ 0 𝑤 𝛿 ⁢ ( 𝜆 ) exists and is 𝑤 * ⁢ ( 𝜆 ) . This completes the proof for 𝜆

0 .

If 𝜆

0 , then the proposition follows similarly with the additional observation that 𝑠 𝛿 𝑘 ⁢ ( 0 )

0 for all 𝑘 . ∎

A.6Sensitivity \constraintReduced

Proof.

Let 𝑤 be as in the theorem statement. We starting by showing that 𝑤 obtains the optimal objective value for the reduced problem:

1 2 ⁢ ‖ 𝑋 𝒜 𝜆 ⁢ 𝑤 𝒜 𝜆 − 𝑦 ‖ 2 2 + 𝜆 ⁢ ∑ 𝑏 𝑖 ∈ 𝒜 𝜆 ‖ 𝑤 𝑏 𝑖 ‖ 2

min 𝑤 : 𝐾 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 ≤ 0 ⁡ 1 2 ⁢ ‖ 𝑋 ⁢ 𝑤 − 𝑦 ‖ 2 2 + 𝜆 ⁢ ∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 𝑏 𝑖 ‖ 2

≤ min 𝑤 𝒜 𝜆 : 𝐾 𝒜 𝜆 ⁢ 𝑤 𝒜 𝜆 ≤ 0 ⁡ 1 2 ⁢ ‖ 𝑋 𝒜 𝜆 ⁢ 𝑤 𝒜 𝜆 − 𝑦 ‖ 2 2 + 𝜆 ⁢ ∑ 𝑏 𝑖 ∈ 𝒜 𝜆 ‖ 𝑤 𝑏 𝑖 ‖ 2

≤ 1 2 ⁢ ‖ 𝑋 𝒜 𝜆 ⁢ 𝑤 𝒜 𝜆 − 𝑦 ‖ 2 2 + 𝜆 ⁢ ∑ 𝑏 𝑖 ∈ 𝒜 𝜆 ‖ 𝑤 𝑏 𝑖 ‖ 2 ,

where the last inequality makes explicit use of feasibility of 𝑤 𝒜 𝜆 . Since 𝑤 𝒜 𝜆 is feasible for the reduced problem and attains the minimum objective value, it must be optimal. Note that it is straightforward to check that the active blocks of the min-norm dual parameter 𝜌 𝒜 𝜆 * are dual optimal for the reduced problem.

Now, let 𝑤 𝒜 𝜆 ′ be an optimal solution to the reduced problem. Since 𝜌 𝒜 𝜆 * is dual optimal for the reduced problem, Section 3.1 implies

𝑤 𝑏 𝑖 ′

𝛼 𝑏 𝑖 ′ ⁢ 𝑣 𝑏 𝑖 ,

for every 𝑏 𝑖 ∈ 𝒜 𝜆 , with 𝛼 𝑏 𝑖 ′ ≥ 0 . Since 𝑋 𝒜 𝜆 ⁢ 𝑤 𝒜 𝜆 ′

𝑋 𝒜 𝜆 ⁢ 𝑤 𝒜 𝜆 , we deduce

∑ 𝑏 𝑖 ∈ 𝒜 𝜆 ( 𝛼 𝑏 𝑖 − 𝛼 𝑏 𝑖 ′ ) ⁢ 𝑋 𝑏 𝑖 ⁢ 𝑏 𝑖

0 ,

which contradicts minimality of 𝑤 unless 𝛼 𝑏 𝑖

𝛼 𝑏 𝑖 ′ . That is, 𝑤 𝒜 𝜆 ′

𝑤 𝒜 𝜆 . We conclude that the reduced problem provides the unique minimal solution with support 𝒜 𝜆 . ∎

Lemma A.14.

Let 𝑤 ∈ 𝒲 * ⁢ ( 𝜆 ) be minimal. Then 𝑤 is a second-order stationary point of the reduced problem (Equation 18).

Proof.

Define 𝑀 ⁢ ( 𝑤 ) to be the block-diagonal projection matrix given by

𝑀 ⁢ ( 𝑤 ) 𝑏 𝑖

1 ‖ 𝑤 𝑏 𝑖 ‖ 2 ⁢ ( 𝐼 − 𝑤 𝑏 𝑖 ‖ 𝑤 𝑏 𝑖 ‖ 2 ⁢ 𝑤 𝑏 𝑖 ⊤ ‖ 𝑤 𝑏 𝑖 ‖ 2 ) .

(26)

The Hessian of the Lagrangian of the reduced problem with respect to 𝑤 is exactly

∇ 𝑤 2 ℒ ⁢ ( 𝑤 𝒜 𝜆 , 𝜌 𝒜 𝜆 )

𝑋 𝒜 𝜆 ⊤ ⁢ 𝑋 𝒜 𝜆 + 𝜆 ⁢ 𝑀 𝒜 𝜆 ⁢ ( 𝑤 ) .

A sufficient condition for 𝑤 to be second-order stationary is that this Hessian is positive-definite. We now shows this fact holds.

Clearly ∇ 𝑤 2 ℒ ⁢ ( 𝑤 𝒜 𝜆 , 𝜌 𝒜 𝜆 ) is positive semi-definite as it is the sum of a PSD projection matrix and a Gram matrix, which is always PSD. Let 𝑤 ¯ ∈ ℝ | 𝒜 𝜆 | such that 𝑤 ¯ ≠ 0 . Suppose that

0

𝑤 ¯ ⊤ ⁢ ∇ 𝑤 2 ℒ ⁢ ( 𝑤 𝒜 𝜆 , 𝜌 𝒜 𝜆 ) ⁢ 𝑤 ¯

𝑤 ¯ ⊤ ⁢ 𝑋 𝒜 𝜆 ⊤ ⁢ 𝑋 𝒜 𝜆 ⁢ 𝑤 ¯ + 𝑤 ¯ ⊤ ⁢ 𝜆 ⁢ 𝑀 ⁢ ( 𝑤 ) ⁢ 𝑤 ¯

‖ 𝑋 𝒜 𝜆 ⁢ 𝑤 ‖ 2 2 + 𝜆 ⁢ 𝑤 ⊤ ⁢ 𝑀 ⁢ ( 𝑤 ) ⁢ 𝑤 .

Since 𝑀 ⁢ ( 𝑤 ¯ ) is PSD, it must hold that

𝑤 ¯ ⊤ ⁢ 𝑀 ⁢ ( 𝑤 ) ⁢ 𝑤 ¯

0 ,

which is true if and only if 𝑤 ¯ 𝑏 𝑖

𝛽 𝑏 𝑖 ⁢ 𝑤 𝑏 𝑖 , 𝛽 𝑏 𝑖 ∈ ℝ , for each 𝑏 𝑖 ∈ 𝒜 𝜆 . As a result, we find that

𝑋 𝒜 𝜆 ⁢ 𝑤 − 𝑋 𝒜 𝜆 ⁢ 𝑤 ¯

∑ 𝑏 𝑖 ∈ 𝒜 𝜆 ( 1 − 𝛽 𝑏 𝑖 ) ⁢ 𝛼 𝑏 𝑖 ⁢ 𝑋 𝑏 𝑖 ⁢ 𝑣 𝑏 𝑖

0 ,

which contradicts minimality of 𝑤 ¯ unless 𝛽 𝑏 𝑖

1 for each 𝑏 𝑖 ∈ 𝒜 𝜆 . But then ‖ 𝑋 𝒜 𝜆 ⁢ 𝑤 ‖ 2 2

0 and we conclude that the Hessian is positive-definite as desired. ∎

\localSolFn

Proof.

Recall from Equation 18 that 𝑤 𝒜 𝜆 is the unique solution to the reduced group lasso problem. In fact, as we show in Lemma A.14, 𝑤 𝒜 𝜆 is a second order stationary point for the reduced problem. Now, combining this fact with LICQ and SCS and using standard results on differential sensitivity from optimization theory (see, e.g. Fiacco & Ishizuka (1990, Theorem 5.1) and the references therein) we obtain the following:

For ( 𝜆 , 𝑦 ) in a neighborhood of 𝜆 ¯ , 𝑦 ¯ , there exists a unique once continuously differentiable function

𝑙 ~ ⁢ ( 𝜆 , 𝑦 )

[ ℎ ~ ⁢ ( 𝜆 , 𝑦 )

𝑔 ~ ⁢ ( 𝜆 , 𝑦 ) , ]

such that ℎ ~ ⁢ ( 𝜆 ¯ , 𝑦 ¯ )

𝑤 𝒜 𝜆 , 𝑔 ~ ⁢ ( 𝜆 ¯ , 𝑦 ¯ )

𝜌 𝒜 𝜆 * , and 𝑙 ~ ⁢ ( 𝜆 , 𝑦 ) is a primal-dual solution to the reduced problem.

Now we show that 𝑙 ~ can be extended from the reduced problem to obtain a local solution function for the constrained group lasso. Define ℎ ⁢ ( 𝜆 , 𝑦 ) such that ℎ 𝒜 𝜆 ⁢ ( 𝜆 , 𝑦 )

ℎ ~ ⁢ ( 𝜆 , 𝑦 ) and ℎ ℬ ∖ 𝒜 𝜆 ⁢ ( 𝜆 , 𝑦 )

0 . We shall show how to extend 𝑔 shortly. For 𝑏 𝑖 ∈ 𝒜 𝜆 , the pair ℎ 𝑏 𝑖 ⁢ ( 𝜆 , 𝑦 ) , 𝑔 𝑏 𝑖 ⁢ ( 𝜆 , 𝑦 ) verifies the KKT conditions (which are separable over block) since it verifies them for the reduced problem. So, we need only consider 𝑏 𝑖 ∈ ℬ ∖ 𝒜 𝜆 .

First, consider 𝑏 𝑖 ∈ ℬ ∖ ℰ 𝜆 . In this case, we have

‖ 𝑋 𝑏 𝑖 ⊤ ⁢ ( 𝑦 ¯ − 𝑋 ⁢ ℎ ⁢ ( 𝜆 ¯ , 𝑦 ¯ ) ) + 𝐾 𝑏 𝑖 ⁢ 𝜌 𝑏 𝑖 ⁢ ( 𝜆 ¯ , 𝑦 ¯ ) ‖ 2 < 𝜆 ¯ ,

Since this inequality is strict and

𝑧 ⁢ ( 𝜆 ¯ , 𝑦 ¯ )

𝑋 𝑏 𝑖 ⊤ ⁢ ( 𝑦 ¯ − 𝑋 ⁢ ℎ ⁢ ( 𝜆 ¯ , 𝑦 ¯ ) ) ,

is continuous in 𝜆 ¯ , 𝑦 ¯ , there exists a neighborhood of 𝜆 ¯ , 𝑦 ¯ on which

‖ 𝑧 ⁢ ( 𝜆 , 𝑦 ) + 𝐾 𝑏 𝑖 ⁢ 𝜌 𝑏 𝑖 ⁢ ( 𝜆 ¯ , 𝑦 ¯ ) ‖ 2 ≤ 𝜆 .

Since 𝜌 𝑏 𝑖 ⁢ ( 𝜆 ¯ , 𝑦 ¯ ) ≥ 0 and 𝑤 𝑏 𝑖

0 , dual feasibility and complementary slackness hold. We conclude that the extension 𝑔 𝑏 𝑖 ⁢ ( 𝜆 , 𝑦 )

𝜌 𝑏 𝑖 ⁢ ( 𝜆 ¯ , 𝑦 ¯ ) satisfies KKT conditions on this neighbourhood.

Now suppose 𝑏 𝑖 ∈ ℰ 𝜆 ⁢ ( 𝜆 ¯ , 𝑦 ¯ ) ∖ 𝒜 𝜆 . If

‖ 𝑋 𝑏 𝑖 ⊤ ⁢ ( 𝑦 − 𝑋 ⁢ ℎ ⁢ ( 𝜆 , 𝑦 ) ) ‖ 2

𝜆 ,

then taking 𝑔 𝑏 𝑖 ⁢ ( 𝑦 , 𝜆 )

0 satisfies KKT conditions. Otherwise, observe that

‖ 𝑋 𝑏 𝑖 ⊤ ⁢ ( 𝑦 ¯ − 𝑋 ⁢ ℎ ⁢ ( 𝜆 ¯ , 𝑦 ¯ ) ) + 𝐾 𝑏 𝑖 ⁢ 𝜌 𝑏 𝑖 ⁢ ( 𝜆 ¯ , 𝑦 ¯ ) ‖ 2

𝜆 ¯ ,

must hold for some dual parameter 𝜌 𝑏 𝑖 ⁢ ( 𝜆 ¯ , 𝑦 ¯ ) by KKT conditions. Moreover, SCS implies that we can choose the dual parameter to satisfy,

𝜌 𝑏 𝑖 ⁢ ( 𝜆 ¯ , 𝑦 ¯ )

0 ,

since 𝐾 𝑏 𝑖 ⊤ ⁢ 𝑤 𝑏 𝑖 ⁢ ( 𝜆 ¯ , 𝑦 ¯ )

0 . Finally, because

𝑋 𝑏 𝑖 ⊤ ⁢ ( 𝑦 − 𝑋 ⁢ ℎ ⁢ ( 𝜆 , 𝑦 ) )

is a continuous function of ( 𝑦 , 𝜆 ) , taking 𝜆 , 𝑦 sufficiently close to 𝜆 ¯ , 𝑦 ¯ implies there exists 𝜌 𝑏 𝑖 ⁢ ( 𝜆 , 𝑦 ) ≥ 0 such that

‖ 𝑋 𝑏 𝑖 ⊤ ⁢ ( 𝑦 − 𝑋 ⁢ ℎ ⁢ ( 𝜆 , 𝑦 ) ) + 𝐾 𝑏 𝑖 ⁢ 𝜌 𝑏 𝑖 ⁢ ( 𝜆 , 𝑦 ) ‖ 2 ≤ 𝜆 .

Now we choose our extension to be 𝑔 𝑏 𝑖 ⁢ ( 𝜆 , 𝑦 )

𝜌 𝑏 𝑖 ⁢ ( 𝜆 , 𝑦 ) so that ( ℎ 𝑏 𝑖 , 𝑔 𝑏 𝑖 ) satisfies stationarity of the Lagrangian as well. Since 𝑔 𝑏 𝑖 is feasible and ℎ 𝑏 𝑖 is the zero function, primal feasibility, dual feasibility, and complementary slackness also hold.

Since 𝑙

( 𝑔 , ℎ ) satisfies the KKT conditions in a local neighborhood of 𝜆 ¯ , 𝑦 ¯ , it is exactly a local solution function. Moreover, since 𝑔 ℬ ∖ 𝒜 ⁢ ( 𝜆 , 𝑦 )

0 over this neighborhood, it is easy to see that the gradient for parameter blocks in ℬ ∖ 𝒜 is 0 . For 𝑔 𝒜 𝜆 , Fiacco & Ishizuka (1990, Theorem 5.1) implies that the gradients are given as follows:

Recall from Lemma A.14, that 𝑀 𝒜 𝜆 is a block-diagonal projection matrix with blocks given by

𝑀 ⁢ ( 𝑤 ¯ ) 𝑏 𝑖

1 ‖ 𝑤 ¯ 𝑏 𝑖 ‖ 2 ⁢ ( 𝐼 − 𝑤 ¯ 𝑏 𝑖 ‖ 𝑤 ¯ 𝑏 𝑖 ‖ 2 ⁢ 𝑤 ¯ 𝑏 𝑖 ⊤ ‖ 𝑤 ¯ 𝑏 𝑖 ‖ 2 ) .

Then, the Jacobian of ∇ 𝑤 ℒ ⁢ ( 𝑤 ¯ 𝒜 𝜆 , 𝜌 ¯ 𝒜 𝜆 ) for the reduced problem with respect to the primal-dual parameters is given by

𝐷

[ 𝑋 𝒜 𝜆 ⊤ ⁢ 𝑋 𝒜 𝜆 + 𝑀 ⁢ ( 𝑤 ¯ )

𝐾 𝒜 𝜆

𝜌 ¯ 𝒜 𝜆 ⊙ 𝐾 𝒜 𝜆

diag ⁢ ( 𝐾 𝒜 𝜆 ⊤ ⁢ 𝑤 ¯ 𝒜 𝜆 ) ] .

It also holds that 𝐷 is invertible. Finally, let 𝑢 𝑖

𝑤 𝑖 ‖ 𝑤 𝑏 𝑖 ‖ 2 and 𝑢 the concatenation of these vectors. We are now able to write the Jacobians of 𝑤 ⁢ ( 𝑦 , 𝜆 ) with respect to 𝑦 and 𝜆 as follows:

∇ 𝜆 𝑤 ⁢ ( 𝜆 ¯ , 𝑦 ¯ )

− [ 𝐷 − 1 ] 𝒜 𝜆 ⁢ 𝑢 𝒜 𝜆 ∇ 𝑦 𝑤 ⁢ ( 𝜆 ¯ , 𝑦 ¯ )

[ 𝐷 − 1 ] 𝒜 𝜆 ⁢ 𝑋 𝒜 𝜆 ⊤ ,

where [ 𝐷 𝒜 𝜆 − 1 ] 𝒜 𝜆 is the | 𝒜 𝜆 | × | 𝒜 𝜆 | dimensional leading principle submatrix of 𝐷 . ∎

Appendix BSpecialization: Proofs Lemma B.1.

Let ( 𝑊 1 , 𝑤 2 ) and ( 𝑊 1 ′ , 𝑤 2 ′ ) be two solutions to the non-convex ReLU training problem. If for every 𝑖 ∈ [ 𝑚 ] , it holds that

𝑊 1 ⁢ 𝑖 ⁢ 𝑤 2 ⁢ 𝑖

𝑊 1 ⁢ 𝑖 ′ ⁢ 𝑤 2 ⁢ 𝑖 ′ ,

and 𝑠𝑖𝑔𝑛 ⁢ ( 𝑤 2 ⁢ 𝑖 )

𝑠𝑖𝑔𝑛 ⁢ ( 𝑤 2 ⁢ 𝑖 ′ ) , then 𝑊 1

𝑊 1 ′ and 𝑤 2

𝑤 2 ′ . That is, the solutions are the same.

Proof.

The ReLU prediction function 𝑓 𝑊 1 , 𝑤 2 is invariant to scalings of the form

𝑊 ¯ 1 ⁢ 𝑖

𝛼 ⁢ 𝑊 1 ⁢ 𝑖 𝑤 ¯ 2 ⁢ 𝑖

𝑤 2 ⁢ 𝑖 / 𝛼 ,

where 𝛼

0 . Using this, we deduce that both solutions must satisfy the following equations:

1

arg ⁢ min 𝛼 𝛼 2 ⁢ ‖ 𝑊 1 ⁢ 𝑖 ‖ 2 2 + ‖ 𝑤 2 ⁢ 𝑖 ‖ 2 2 / 𝛼 2

1

arg ⁢ min 𝛼 𝛼 2 ⁢ ‖ 𝑊 1 ⁢ 𝑖 ′ ‖ 2 2 + ‖ 𝑤 2 ⁢ 𝑖 ′ ‖ 2 2 / 𝛼 2 ,

which in turn implies that

‖ 𝑊 1 ⁢ 𝑖 ‖ 2

‖ 𝑤 2 ⁢ 𝑖 ‖ 2 , ‖ 𝑊 1 ⁢ 𝑖 ′ ‖ 2

‖ 𝑤 2 ⁢ 𝑖 ′ ‖ 2

We deduce

‖ 𝑊 1 ⁢ 𝑖 ‖ 2 2

‖ 𝑊 1 ⁢ 𝑖 ‖ 2 ⁢ ‖ 𝑤 2 ⁢ 𝑖 ‖ 2

‖ 𝑊 1 ⁢ 𝑖 ⁢ 𝑤 2 ⁢ 𝑖 ‖ 2

‖ 𝑊 1 ⁢ 𝑖 ′ ⁢ 𝑤 2 ⁢ 𝑖 ′ ‖ 2

‖ 𝑊 1 ⁢ 𝑖 ′ ‖ 2 ⁢ ‖ 𝑤 2 ⁢ 𝑖 ′ ‖ 2

‖ 𝑊 1 ⁢ 𝑖 ′ ‖ 2 2 ,

where we have used the fact that ‖ 𝑤 2 ⁢ 𝑖 ‖ 2

| 𝑤 2 ⁢ 𝑖 | . This implies 𝑊 1 ⁢ 𝑖

𝑊 1 ⁢ 𝑖 ′ since 𝑊 1 ⁢ 𝑖 and 𝑊 1 ⁢ 𝑖 ′ are collinear, meaning 𝑤 2 ⁢ 𝑖

𝑤 2 ⁢ 𝑖 ′ must also hold. ∎

Lemma B.2.

Let ( 𝑊 1 , 𝑤 2 ) and ( 𝑊 ~ 1 , 𝑤 ~ 2 ) be two solutions to the non-convex ReLU training problem. If ( 𝑊 1 , 𝑤 2 ) and ( 𝑊 ~ 1 , 𝑤 ~ 2 ′ ) map to the same solution in the convex reformulation, then they are equal up to permutations or splits/merges of of neurons with collinear weights.

Proof.

Let ( 𝑊 1 , 𝑤 2 ) be a solution to the non-convex ReLU training problem. For each neuron, associate 𝑊 1 ⁢ 𝑖 with the sparsest activation pattern 𝐷 𝑖 to which 𝑊 1 ⁢ 𝑖 conforms. That is, given 𝑊 1 ⁢ 𝑖 , we associate it with the following pattern:

𝐷 𝑖

arg ⁢ min { nnz ⁢ ( 𝐷 𝑗 ) : 𝐷 𝑗 ∈ 𝒟 𝑍 , 2 ⁢ ( 𝐷 𝑗 − 𝐼 ) ⁢ 𝑍 ⁢ 𝑊 1 ⁢ 𝑖 ≥ 0 } .

If 𝑊 1 ⁢ 𝑖 and 𝑊 1 ⁢ 𝑗 are associated with the same pattern 𝐷 𝑖 and sign ⁢ ( 𝑤 2 ⁢ 𝑖 )

sign ⁢ ( 𝑤 2 ⁢ 𝑗 ) , then Mishkin et al. (2022) prove 𝑊 1 ⁢ 𝑖 and 𝑊 1 ⁢ 𝑗 are collinear, i.e. 𝑊 1 ⁢ 𝑖

𝛼 ⁢ 𝑊 1 ⁢ 𝑗 for some 𝛼

0 . They also prove that the model obtained by merging these collinear neurons as

𝑊 1 ⁢ 𝑖 ′

𝑊 1 ⁢ 𝑖 ⁢ | 𝑤 2 ⁢ 𝑖 | + 𝑊 1 ⁢ 𝑗 ⁢ | 𝑤 2 ⁢ 𝑗 | ‖ 𝑊 1 ⁢ 𝑖 ⁢ | 𝑤 2 ⁢ 𝑖 | + 𝑊 1 ⁢ 𝑗 ⁢ | 𝑤 2 ⁢ 𝑗 | ‖ 2 1 / 2 , 𝑤 2 ⁢ 𝑖 ′

sign ⁢ ( 𝑤 2 ⁢ 𝑖 ) ⁢ ‖ 𝑊 1 ⁢ 𝑖 ⁢ | 𝑤 2 ⁢ 𝑖 | + 𝑊 1 ⁢ 𝑗 ⁢ | 𝑤 2 ⁢ 𝑗 | ‖ 2 1 / 2 ,

where 𝑊 1 ⁢ 𝑗 ′

0 , and 𝑤 2 ⁢ 𝑗 ′

0 , is also an optimal solution to the non-convex ReLU problem. We term this the merge/split symmetry.

By recursively merging all collinear neurons assigned to the same activation pattern for which sign ⁢ ( 𝑤 2 ⁢ 𝑖 )

sign ⁢ ( 𝑤 2 ⁢ 𝑗 ) holds, we eventually obtain an optimal reduced model ( 𝑊 1 ′ , 𝑤 2 ′ ) such that no two non-zero neurons share an activation pattern 𝐷 𝑖 and have second-layer weights with the same sign. We may then place an ordering on the neurons by ordering the 𝐷 𝑖 matrices from 1 to 𝑝 . This removes all permutation symmetries.

Since every signed neuron in the non-convex model now corresponds to a unique pattern 𝐷 𝑖 , the mapping to the convex program is given by

𝑣 𝑖

{ 𝑊 1 ⁢ 𝑖 ′ ⁢ 𝑤 2 ⁢ 𝑖 ′

if  𝑤 2 ⁢ 𝑖 ′ ≥ 0

0
otherwise

𝑢 𝑖

{ − 𝑊 1 ⁢ 𝑖 ′ ⁢ 𝑤 2 ⁢ 𝑖 ′

if  𝑤 2 ⁢ 𝑖 ′ < 0

0

otherwise ,

Applying this procedure to ( 𝑊 1 , 𝑤 2 ) and ( 𝑊 ~ 1 , 𝑤 ~ 2 ) and recalling that they map to the same solution implies

𝑊 1 ⁢ 𝑖 ′ ⁢ 𝑤 2 ⁢ 𝑖 ′

𝑊 ~ 1 ⁢ 𝑖 ′ ⁢ 𝑤 ~ 2 ⁢ 𝑖 ′ ,

and sign ⁢ ( 𝑤 2 ⁢ 𝑖 ′ )

sign ⁢ ( 𝑤 ~ 2 ⁢ 𝑖 ′ ) for every 𝑖 . Invoking Lemma B.1 is sufficient to prove ( 𝑊 1 ′ , 𝑤 2 ′ ) and ( 𝑊 ~ 1 ′ , 𝑤 ~ 2 ′ ) are identical.

To obtain this result, we (i) merged all collinear neurons with the same sign in the second layer and then (ii) sorted the neurons according to their activation patterns. Thus, it must be that ( 𝑊 1 , 𝑤 2 ) and ( 𝑊 ~ 1 , 𝑤 ~ 2 ) differ only by (i) splitting of neurons into collinear neurons and (ii) the ordering (i.e. permutation) of the neurons. This completes the proof. ∎

\reluSolFn

Proof.

Let the proposed optimal set be the completion of

𝒰 𝜆

{ ( 𝑊 1 , 𝑤 2 ) : 𝑓 𝑊 1 , 𝑤 2 ( 𝑍 )

𝑦 ^ , 𝑊 1 ⁢ 𝑖

( 𝛼 𝑖 / 𝜆 ) 1 / 2 𝑣 𝑖 ,

𝑤 2 ⁢ 𝑖

𝜉 𝑖 ( 𝛼 𝑖 𝜆 ) 1 / 2 , 𝛼 𝑖 ≥ 0 , 𝑖 ∈ [ 2 𝑝 ] ∖ 𝒮 𝜆 ⇒ 𝛼 𝑖

0 } ,

over all permutations of the neurons and splits/merges of collinear neurons. Let ( 𝑊 1 , 𝑤 2 ) ∈ 𝒰 𝜆 . Inverting Equation 5, we compute a candidate solution 𝑢 to the convex reformulation as

𝑢 𝑖

𝑊 1 ⁢ 𝑖 ⁢ 𝑤 2 ⁢ 𝑖

𝛼 𝑖 ⁢ 𝑣 𝑖 ,

for some 𝛼 𝑖 ≥ 0 , where we assumed without loss of generality that 𝑤 2 ⁢ 𝑖 ≥ 0 (if 𝜉 𝑖

− 1 , then we simply map to a “negative” neuron in the convex reformulation). Moreover, 𝛼 𝑖

0 if 𝑖 ∈ [ 2 ⁢ 𝑝 ] ∖ 𝒮 𝜆 . Since the solution mapping preserves the prediction of the neural network, we also have 𝑋 ⁢ 𝑢

𝑦 ^ , which is enough to guarantee 𝑢 is a solution to the convex reformulation using Section 3.1. Since 𝑢 is a solution, we conclude that ( 𝑊 1 , 𝑤 2 ) must be optimal for the non-convex ReLU problem.

For the reverse inclusion, let ( 𝑊 1 , 𝑤 2 ) ∈ 𝒪 𝜆 and suppose no permutation or merge/split symmetry of ( 𝑊 1 , 𝑤 2 ) is in 𝒰 𝜆 . While ( 𝑊 1 , 𝑤 2 ) ∉ 𝒰 𝜆 , it still maps to some solution to the convex reformulation, call it 𝑢 . As 𝒰 𝜆 is obtained by mapping every solution to the convex reformulation (i.e. every 𝑢 ∈ 𝒲 𝜆 * ) to the non-convex parameterization, it must be that 𝑢 also maps to some ( 𝑊 ~ 1 , 𝑤 ~ 2 ) in 𝒰 𝜆 . Lemma B.2 now shows that ( 𝑊 1 , 𝑤 2 ) and ( 𝑊 ~ 1 , 𝑤 ~ 2 ) are identical up to permutations and splits/merges of collinear neurons But, this implies ( 𝑊 1 , 𝑤 2 ) ∈ 𝒰 𝜆 up to permutation and merge/split symmetries, which is a contradiction. We conclude that the optimal set is the completion of 𝒰 𝜆 as claimed. ∎

\stationaryPoints

Proof.

The proof is almost immediate.

Given any sub-sampled set of activation patterns 𝒟 ~ ⊂ 𝒟 𝑍 , Wang et al. (2021, Theorem 3) prove that the solutions to the sub-sampled convex program are Clarke stationary points (Clarke, 1990) of the non-convex ReLU optimization problem in Equation 1, and vice-versa. Using the expression for the CGL solution set in Section 3.1, which applies to sub-sampled convex reformulations as well as the full program, we obtain a version of Algorithm 2 for stationary points. That is, every model ( 𝑊 1 , 𝑤 2 ) in

𝒞 𝜆 ( 𝒟 ~ )

{
( 𝑊 1 , 𝑤 2 ) : 𝑓 𝑊 1 , 𝑤 2 ⁢ ( 𝑍 )

𝑦 ^ 𝒟 ~ , 𝑊 1 ⁢ 𝑖

( 𝛼 𝑖 / 𝜆 ) 1 / 2 ⁢ 𝑣 𝑖 ⁢ ( 𝒟 ~ ) , 𝑤 2 ⁢ 𝑖

𝜉 𝑖 ⁢ ( 𝛼 𝑖 ⁢ 𝜆 ) 1 / 2 ,

𝛼 𝑖 ≥ 0 , 𝑖 ∈ [ 𝑚 ] ∖ 𝒮 𝜆 ⟹ 𝛼 𝑖

0 } ,

is a stationary point of the non-convex ReLU program. Taking the union over all sub-sampled sets of activation patterns gives 𝒞 𝜆 , which is guaranteed to contain every stationary point of the non-convex objective. This completes the proof. ∎

\pUnique

Proof.

Since there is only one solution to the convex reformulation, all solutions to the non-convex training problem must map to that solution. Lemma B.2 now implies that the solution map for the non-convex problem is p-unique, i.e. unique up to permutations and splits/merges of collinear neurons. ∎

\reluUnique

Proof.

We assume without loss of generality that only indices from 1 to 𝑝 are in ℰ 𝜆 . By Corollary 3.1, the constrained group lasso admits a unique solution if and only if

⋃ 𝑖 ∈ ℰ 𝜆 { 𝐷 𝑖 ⁢ 𝑍 ⁢ 𝑣 𝑏 𝑖 } ,

are linearly independent. We now show that this fact holds under the proposed sufficient condition by proving the stronger fact that ⋃ 𝑖 ∈ ℰ 𝜆 { [ 𝐷 𝑖 ⁢ 𝑍 ] 𝑗 : 𝑗 ∈ [ 𝑑 ] } are linearly independent with probability one, where [ 𝐷 𝑖 ⁢ 𝑍 ] 𝑗 is the 𝑗 th column of 𝐷 𝑖 ⁢ 𝑍 . Since nnz ⁢ ( 𝐷 𝑖 ) ≥ 𝑑 * 𝑝 and 𝑍 has a continuous probability distribution, it holds that [ 𝐷 𝑖 ⁢ 𝑍 ] 𝑗 has at least 𝑑 * 𝑝 non-zero entries with probability 1. Let

𝒮 𝑖 ⁢ 𝑗

Span ⁢ ( ⋃ 𝑖 ∈ ℰ 𝜆 { [ 𝐷 𝑖 ⁢ 𝑍 ] 𝑗 : 𝑗 ∈ [ 𝑑 ] } ∖ [ 𝐷 𝑖 ⁢ 𝑍 ] 𝑗 ) ,

and observe that dim ⁢ ( 𝒮 𝑖 ⁢ 𝑗 ) ≤ 𝑑 * 𝑝 − 1 . As a result, the conditional probability [ 𝐷 𝑖 ⁢ 𝑍 ] 𝑗 falls in this subspace satisfies

Pr ⁡ ( [ 𝐷 𝑖 ⁢ 𝑍 ] 𝑗 ∈ 𝒮 𝑖 ⁢ 𝑗 | ⋃ 𝑖 ∈ ℰ 𝜆 { [ 𝐷 𝑖 ⁢ 𝑍 ] 𝑗 : 𝑗 ∈ [ 𝑑 ] } ∖ [ 𝐷 𝑖 ⁢ 𝑍 ] 𝑗 )

0 .

Taking expectations over the remaining vectors in 𝑍 implies

Pr ⁡ ( [ 𝐷 𝑖 ⁢ 𝑍 ] 𝑗 ∈ 𝒮 𝑖 ⁢ 𝑗 )

0 .

Finally, using a union bound over 𝑖 , 𝑗 implies that ⋃ 𝑖 ∈ ℰ 𝜆 { [ 𝐷 𝑖 ⁢ 𝑍 ] 𝑗 : 𝑗 ∈ [ 𝑑 ] } are linearly independent almost surely. ∎

\minimalComplexity

Proof.

The proof follows directly from existing results.

Recall from Pilanci & Ergen (2020) that there are at most

𝑝 ∈ 𝑂 ⁢ ( 𝑟 ⁢ 𝑛 𝑟 3 ⁢ 𝑟 ) ,

activation patterns in the convex reformulation and that the complexity of computing an optimal ReLU model using a standard interior-point solver is 𝑂 ⁢ ( 𝑑 3 ⁢ 𝑟 3 ⁢ ( 𝑛 / 𝑟 ) 3 ⁢ 𝑟 ) .

We know from Proposition A.6 that the complexity of pruning an optimal neural network with at most 2 ⁢ 𝑝 neuron is 𝑂 ⁢ ( 𝑛 3 ⁢ 𝑝 + 𝑛 ⁢ 𝑑 ) . Combining these complexities, we find that the cost of optimization dominates and overall complexity of computing an optimal and minimal neural network grows as 𝑂 ⁢ ( 𝑑 3 ⁢ 𝑟 3 ⁢ ( 𝑛 / 𝑟 ) 3 ⁢ 𝑟 ) .

Finally, the bound on the number of active neurons follows from the fact that dim Span ⁢ ( { ( 𝑋 ⁢ 𝑊 1 ⁢ 𝑖 * ) + } 𝑖 ) ≤ 𝑛 . This completes the proof. ∎

\minNormNN

Proof.

Let ( 𝑢 , 𝑣 ) be an optimal solution to the convex reformulation. Pilanci & Ergen (2020) show that an optimal solution to the original two-layer ReLU optimization problem is given by setting

𝑊 1 ⁢ 𝑖

𝑢 𝑖 ‖ 𝑢 𝑖 ‖ 2 , 𝑤 2 ⁢ 𝑖

‖ 𝑢 𝑖 ‖ 2 ,

and

𝑊 1 ⁢ 𝑗

𝑣 𝑖 ‖ 𝑣 𝑖 ‖ 2 , 𝑤 2 ⁢ 𝑗

− ‖ 𝑣 𝑖 ‖ 2 ,

where we define 0 0

0 . Then, the 𝑟 -value of any such solution can be calculated as

𝑟 ⁢ ( 𝑊 1 , 𝑤 2 )

∑ 𝑖

1 𝑚 ‖ 𝑊 1 ⁢ 𝑖 ‖ 2 4 + ‖ 𝑤 2 ⁢ 𝑖 ‖ 2 4

∑ 𝑢 𝑖 ≠ 0 ‖ 𝑢 𝑖 ‖ 𝑢 𝑖 ‖ 2 ‖ 2 4 + ‖ ‖ 𝑢 𝑖 ‖ 2 ‖ 2 4 + ∑ 𝑣 𝑖 ≠ 0 ‖ 𝑣 𝑖 ‖ 𝑣 𝑖 ‖ 2 ‖ 2 4 + ‖ ‖ 𝑣 𝑖 ‖ 2 ‖ 2 4

∑ 𝑢 𝑖 ≠ 0 ‖ 𝑢 𝑖 ‖ 2 2 + ‖ 𝑢 𝑖 ‖ 2 2 + ∑ 𝑣 𝑖 ≠ 0 ‖ 𝑣 𝑖 ‖ 2 2 + ‖ 𝑣 𝑖 ‖ 2 2

2 ⁢ ‖ 𝑢 ‖ 2 2 + 2 ⁢ ‖ 𝑣 ‖ 2 2 .

That is, 𝑟 ⁢ ( 𝑊 1 , 𝑤 2 ) is a monotone transformation of the Euclidean norm of ( 𝑢 , 𝑣 ) . Moreover, all optimal ReLU networks up to permutation and neuron-split symmetries can be obtained by applying this mapping to the solution to a convex reformulation. We conclude that the minimum 𝑟 -valued optimal ReLU network before any such symmetries are applied is given by the minimum ℓ 2 -norm solution to the convex reformulation.

Now, clearly permutation symmetries have no affect on the 𝑟 value. However, splitting neurons into multiple collinear neurons can, in fact, reduce 𝑟 . For example, consider splitting a neuron ( 𝑊 1 ⁢ 𝑖 , 𝑤 2 ⁢ 𝑖 ) into ( 𝑊 1 ⁢ 𝑖 ′ , 𝑤 2 ⁢ 𝑖 ′ ) and ( 𝑊 1 ⁢ 𝑗 ′ , 𝑤 2 ⁢ 𝑗 ′ ) such that 𝑊 1 ⁢ 𝑖 ′ and 𝑊 1 ⁢ 𝑗 ′ are collinear, sign ⁢ ( 𝑤 2 ⁢ 𝑖 ′ )

sign ⁢ ( 𝑤 2 ⁢ 𝑗 ′ ) , and

𝑊 1 ⁢ 𝑖

𝑊 1 ⁢ 𝑖 ′ ⁢ 𝑤 2 ⁢ 𝑖 ′ + 𝑊 1 ⁢ 𝑗 ′ ⁢ 𝑤 2 ⁢ 𝑗 ′ ‖ 𝑊 1 ⁢ 𝑖 ′ ⁢ 𝑤 2 ⁢ 𝑖 ′ + 𝑊 1 ⁢ 𝑗 ′ ⁢ 𝑤 2 ⁢ 𝑗 ′ ‖ 2 1 / 2 , 𝑤 2 ⁢ 𝑖

sign ⁢ ( 𝑤 2 ⁢ 𝑖 ) ⁢ ‖ 𝑊 1 ⁢ 𝑖 ′ ⁢ 𝑤 2 ⁢ 𝑖 ′ + 𝑊 1 ⁢ 𝑗 ′ ⁢ 𝑤 2 ⁢ 𝑗 ′ ‖ 2 1 / 2 ,

and ‖ 𝑊 1 ⁢ 𝑖 ′ ‖ 2

‖ 𝑤 2 ⁢ 𝑖 ′ ‖ 2 , ‖ 𝑊 1 ⁢ 𝑗 ′ ‖ 2

‖ 𝑤 2 ⁢ 𝑗 ′ ‖ 2 . This operation is known to preserve optimality (Mishkin et al., 2022). However, the conditions on the split neurons also imply

‖ 𝑊 1 ⁢ 𝑖 ‖ 2 4 + ‖ 𝑤 2 ⁢ 𝑖 ‖ 2 4

2 ⁢ ‖ 𝑊 1 ⁢ 𝑖 ′ ⁢ 𝑤 2 ⁢ 𝑖 ′ + 𝑊 1 ⁢ 𝑗 ′ ⁢ 𝑤 2 ⁢ 𝑗 ′ ‖ 2 2

2 ⁢ ‖ 𝑊 1 ⁢ 𝑖 ′ ⁢ 𝑤 2 ⁢ 𝑖 ′ ‖ 2 2 + 2 ⁢ ‖ 𝑊 1 ⁢ 𝑗 ′ ⁢ 𝑤 2 ⁢ 𝑗 ′ ‖ 2 2 + 4 ⁢ ⟨ 𝑊 1 ⁢ 𝑖 ′ ⁢ 𝑤 2 ⁢ 𝑖 ′ , 𝑊 1 ⁢ 𝑗 ′ ⁢ 𝑤 2 ⁢ 𝑗 ′ ⟩

> 2 ⁢ ‖ 𝑊 1 ⁢ 𝑖 ′ ⁢ 𝑤 2 ⁢ 𝑖 ′ ‖ 2 2 + 2 ⁢ ‖ 𝑊 1 ⁢ 𝑗 ′ ⁢ 𝑤 2 ⁢ 𝑗 ′ ‖ 2 2

‖ 𝑊 1 ⁢ 𝑖 ′ ‖ 2 4 + ‖ 𝑤 2 ⁢ 𝑖 ′ ‖ 2 4 + ‖ 𝑊 1 ⁢ 𝑗 ′ ‖ 2 4 + ‖ 𝑤 2 ⁢ 𝑗 ′ ‖ 2 4 ,

where have used positive collinearity of 𝑊 1 ⁢ 𝑖 ′ and 𝑊 2 ⁢ 𝑖 ′ . As a result, the 𝑟 -value of a solution can be decreased by splitting neurons. Thus, the minimum-norm solution to the convex reformulation is only the minimum 𝑟 -value optimal ReLU network out of all networks which admit no neuron-merge symmetries. ∎

\oneNeuron

Proof.

Mishkin et al. (2022) show that Equation 1 has the same global optimal values as

min 𝑣 , 𝛾 ∈ { − 1 , 1 } ⁡ 1 2 ⁢ ‖ ∑ 𝑖

1 𝑝 ( 𝑋 ⁢ 𝑣 𝑖 ) + ⁢ 𝛾 − 𝑦 ‖ + 𝜆 ⁢ ∑ 𝑖

1 𝑝 ‖ 𝑤 𝑖 ‖ 2 .

(27)

Moreover, the objective-preserving mapping 𝑊 1 ⁢ 𝑖

𝑣 𝑖 / ‖ 𝑣 𝑖 ‖ 2 , 𝑤 2 ⁢ 𝑖

𝛾 𝑖 ⁢ ‖ 𝑣 𝑖 ‖ 2 can be used to obtain an optimal ReLU network from a solution to Equation 27. We proceed by analyzing this equivalent problem and then use the mapping to return to the original non-convex formulation.

Consider the case 𝑝

1 . Let 𝑋 , 𝑦 consist of two training points, ( 𝑥 1 , 𝑦 1 )

( − 100 , 1 ) and ( 𝑥 2 , 𝑦 2 )

( 1 , 10 ) . In what follows, we drop the subscript for 𝑣 and 𝛾 since 𝑝

1 and we consider a one-dimensional. The optimization problem of interest is

min 𝑣 , 𝛾 ⁡ 1 2 ⁢ ( ( 𝑥 1 ⁢ 𝑣 ) + ⁢ 𝛾 − 𝑦 1 ) 2 + ( ( 𝑥 2 ⁢ 𝑣 ) + ⁢ 𝛾 − 𝑦 2 ) 2 + 𝜆 ⁢ | 𝑣 | .

Since 𝑥 1 < 0 and 𝑥 2

0 , we can re-write this optimization problem as

min 𝑣 , 𝛾 ⁡ 1 2 ⁢ 𝟙 𝑣 ≤ 0 ⁢ ( ( 𝑥 1 ⁢ 𝑣 ⁢ 𝛾 − 𝑦 1 ) 2 + 𝑦 2 2 ) + 𝟙 𝑣

0 ⁢ ( ( 𝑥 2 ⁢ 𝑣 ⁢ 𝛾 − 𝑦 2 ) 2 + 𝑦 1 2 ) + 𝜆 ⁢ | 𝑣 | .

By inspection, we see that 𝛾

• 1 is optimal in both cases, leading to the following simplified expression:

min 𝑣 ⁡ 1 2 ⁢ 𝟙 𝑣 ≤ 0 ⁢ ( ( 𝑥 1 ⁢ 𝑣 − 𝑦 1 ) 2 + 𝑦 2 2 ) + 𝟙 𝑣

0 ⁢ ( ( 𝑥 2 ⁢ 𝑣 − 𝑦 2 ) 2 + 𝑦 1 2 ) + 𝜆 ⁢ | 𝑣 | .

This is a piece-wise continuous (but non-smooth) quadratic with a breakpoint at 𝑣 *

0 . We determine the solution to this minimization problem via a case analysis.

Case 1: 𝑣 *

0 . Then, the optimal objective is trivially 𝑓 ⁢ ( 𝑣 * )

𝑦 1 2 + 𝑦 2 2

101 .

Case 2: 𝑣 * < 0 . First order optimality conditions are

𝑥 1 ⁢ ( 𝑥 1 ⁢ 𝑣 − * − 𝑦 1 ) − 𝜆

0 ⟹ 𝑣 − *

𝑦 1 ⋅ 𝑥 1 + 𝜆 𝑥 1 2 ,

which is valid only if 𝜆 < | 𝑦 1 ⋅ 𝑥 1 |

100 . The minimum objective value is then

1 2 ⁢ ( ( 𝑥 1 ⁢ 𝑣 − * − 𝑦 1 ) 2 + 𝑦 2 2 ) − 𝜆 ⁢ 𝑣 − *

( ( 𝑥 1 ⁢ 𝑦 1 ⋅ 𝑥 1 + 𝜆 𝑥 1 2 − 𝑦 1 ) 2 + 𝑦 2 2 ) − 𝜆 ⁢ ( 𝑦 1 ⋅ 𝑥 1 + 𝜆 𝑥 1 2 )

𝜆 2 𝑥 1 2 + 𝑦 2 2 − 𝜆 ⁢ ( 𝑦 1 ⋅ 𝑥 1 + 𝜆 𝑥 1 2 )

− 𝜆 ⁢ 𝑦 1 𝑥 1 + 𝑦 2 2

𝜆 100 + 100 .

Case 3: 𝑣 + *

0 . Similarly to the previous case, we obtain

𝑥 2 ⁢ ( 𝑥 2 ⁢ 𝑣 + * − 𝑦 2 ) + 𝜆

0 ⟹ 𝑣 + *

𝑦 2 ⋅ 𝑥 2 − 𝜆 𝑥 2 2 ,

which is valid only if 𝜆 < | 𝑦 2 ⋅ 𝑥 2 |

10 . In this case, the minimum objective is

1 2 ⁢ ( ( 𝑥 2 ⁢ 𝑣 + * − 𝑦 2 ) 2 + 𝑦 1 2 ) + 𝜆 ⁢ 𝑣 + *

( ( 𝑥 2 ⁢ 𝑦 2 ⋅ 𝑥 2 + 𝜆 𝑥 2 2 − 𝑦 2 ) 2 + 𝑦 1 2 ) − 𝜆 ⁢ ( 𝑦 2 ⋅ 𝑥 2 + 𝜆 𝑥 2 2 )

𝜆 2 𝑥 2 2 + 𝑦 2 2 + 𝜆 ⁢ ( 𝑦 2 ⋅ 𝑥 2 − 𝜆 𝑥 2 2 )

𝜆 ⁢ 𝑦 2 𝑥 2 + 𝑦 1 2

10 ⁢ 𝜆 + 1 .

To combine the cases, observe that

𝑓 ⁢ ( 𝑣 + * ) − 𝑓 ⁢ ( 𝑣 − * )

𝜆 ⁢ 𝑦 2 𝑥 2 + 𝑦 1 2 − [ − 𝜆 ⁢ 𝑦 1 𝑥 1 + 𝑦 2 2 ]

𝜆 ⁢ ( 𝑥 1 ⁢ 𝑦 2 + 𝑥 2 ⁢ 𝑦 1 𝑥 1 ⁢ 𝑥 2 ) + 𝑦 1 2 − 𝑦 2 2

𝜆 ⁢ ( − 100 ⁢ ( 10 ) + 1 ⁢ ( 1 ) − 100 ⁢ ( 1 ) ) + 1 − 100

9.99 ⁢ 𝜆 − 99 .

We deduce that 𝑓 ⁢ ( 𝑣 + * ) − 𝑓 ⁢ ( 𝑣 − * )

0 (and thus 𝑣 * ≤ 0 ) whenever 𝜆

99 9.99 ≈ 10 and 𝑓 ⁢ ( 𝑣 + * ) − 𝑓 ⁢ ( 𝑣 − * )

0 < 0 otherwise. In this latter case, 𝑣 * ≥ 0 .

Taking 𝜆

10 , we find

𝑓 ⁢ ( 𝑣 − * )

100 − 0.1

99.99 < 101

𝑦 1 2 + 𝑦 2 2

𝑓 ⁢ ( 0 ) ,

so that 𝑣 − * is optimal and 𝑣 − * < 0 . Moreover, 𝑣 − * is strictly increasing as a function of 𝜆 , for all 𝜆

99 9.99 so that 𝑣 − * is optimal and strictly negative on the interval [ 99 9.99 , 10 ] .

Now, consider 𝜆

99 9.99 − 𝜖 to see that

𝑓 ⁢ ( 𝑣 + * )

990 9.99 + 1 − 10 ⁢ 𝜖 < 101

𝑦 1 2 + 𝑦 2 2

𝑓 ⁢ ( 0 ) ,

for all 𝜖

0 . We deduce that 𝑣 + * is optimal for all 𝜖

0 and thus 𝑣 + * is optimal and strictly positive on the interval [ 0 , 99 9.99 ] .

To summarize, the solution function for this problem is as follows:

𝒲 * ⁢ ( 𝜆 )

{ 𝜆 100 2 − 0.01

if  𝜆

99 9.99

{ 𝜆 100 2 − 0.01 , 0.1 − 𝜆 100 }
if  𝜆

99 9.99

0.1 − 𝜆 100

if  𝜆 < 99 9.99 .

This point-to-set map is clearly not open: for every sequence 𝜆 𝑘 ↑ 99 9.99 , 𝑣 𝑘 ∈ 𝒲 * ⁢ ( 𝜆 𝑘 ) implies lim 𝑘 𝑣 𝑘 ≠ 𝜆 100 2 − 0.01 . Moreover, a similar result holds for limits from above. Finally, it is clear by inspection that the optimal model fit is not unique at 𝜆

99 9.99 , cannot be continuous in the functional sense, and, since it is not open, also fails to be continuous in the sense of point-to-set maps. ∎

Appendix CExtension to General Losses

In this section, we briefly discuss how to extend our results to general loss functions. Although we use the least-squares error throughout our derivations, this can be generalized to a smooth and strictly convex loss function 𝐿 : ℝ 𝑛 × ℝ 𝑛 → ℝ without difficulty. To do so, consider the more general problem,

𝑝 * ⁢ ( 𝜆 )

min 𝑤

𝐹 𝜆 ⁢ ( 𝑤 ) := 1 2 ⁢ 𝐿 ⁢ ( 𝑋 ⁢ 𝑤 , 𝑦 ) + 𝜆 ⁢ ∑ 𝑏 𝑖 ∈ ℬ ‖ 𝑤 𝑏 𝑖 ‖ 2

(28)

s.t. 𝐾 𝑏 𝑖 ⊤ ⁢ 𝑤 𝑏 𝑖 ≤ 0 ⁢  for all  ⁢ 𝑏 𝑖 ∈ ℬ .

If 𝐿 is strictly convex, then uniqueness of the optimal model fit 𝑦 ^ ⁢ ( 𝜆 )

𝑋 ⁢ 𝑤 follows from straightforward adaption of Lemma A.1. Indeed, the only property of the squared-error used in this lemma is strict convexity.

Since the model fit is constant in 𝒲 * and 𝐿 is both smooth and strictly convex, the gradient ∇ 𝑤 𝐿 ⁢ ( 𝑋 ⁢ 𝑤 , 𝑦 ) , which is given by

𝑋 ⊤ ⁢ ∇ 𝑦 ^ 𝐿 ⁢ ( 𝑦 ^ , 𝑦 ) ,

must also be constant over 𝒲 * . Thus, it is straightforward to replace the correlation vector 𝑐 𝑏 𝑖

𝑋 𝑏 𝑖 ⊤ ⁢ ( 𝑦 − 𝑋 ⁢ 𝑤 ) with 𝑋 𝑏 𝑖 ⊤ ⁢ ∇ 𝑦 ^ 𝐿 ⁢ ( 𝑦 ^ , 𝑦 ) throughout our derivations.

We form a Lagrange dual problem for CGL for one continuity-type result. Corollary 3.7 uses the Lagrange dual to show that the correlation vector 𝑐 𝑏 𝑖 is the unique solution to a convex optimization program and applies standard sensitivity results to obtain continuity of 𝑦 ^ . In this same fashion, 𝑋 𝑏 𝑖 ⊤ ⁢ ∇ 𝑦 ^ 𝐿 ⁢ ( 𝑦 ^ , 𝑦 ) is the unique solution to a Lagrange dual problem where the dual objective uses the convex conjugate 𝐿 * , rather than the dual of the quadratic penalty. If ∇ 𝑦 ^ 𝐿 ⁢ ( 𝑦 ^ , 𝑦 ) is continuous in 𝑦 ^ , then this is sufficient to deduce continuity of the model fit using the same argument.

Appendix DAdditional Experiments Figure 4:Pruning neurons on five datasets from the UCI repository. This figure extends Figure 2 with training accuracy in addition to the test accuracies shown in the main paper. Figure 5:Pruning neurons on five additional datasets from the UCI repository. See Figure 2 for details. Our method (Optimal/LS) preservers test accuracy for longer than the baseline methods, leading to compact models with better generalization.

In this section we provide additional experimental results as well as the necessary details to replicate our pruning experiments. Code to replicate all of our experiments is provided at https://github.com/pilancilab/relu_optimal_sets.

D.1Additional Results Figure 6:Pruning experiments on binary classification tasks from the CIFAR-10 dataset. This figure reproduces results from Figure 3 with training accuracies added and also includes results for an additional task, cats vs dogs, not presented in the main paper. Figure 7:Pruning experiments on three binary classification tasks taken from MNIST. Table 2:Tuning neural networks by searching over the optimal set. We fit two-layer ReLU networks on the training set and compute the minimum ℓ 2 norm solution (Min L 2 ). Then we tune by finding an extreme point approximating the maximum ℓ 2 -norm solution (EP), minimizing validation MSE over the optimal set (V-MSE), and minimizing test MSE over the optimal set (T-MSE). Max Diff. reports the difference between the best and worse models found. For each method we give the median and interquartile range as median (lower/upper). Dataset Min L 2 EP V-MSE T-MSE Max Diff. blood 0.72 (0.72/0.74) 0.72 (0.72/0.74) 0.62 (0.61/0.62) 0.7 (0.68/0.71) 0.1 (0.11/0.12) breast-cancer 0.64 (0.61/0.65) 0.64 (0.61/0.65) 0.61 (0.6/0.64) 0.71 (0.66/0.71) 0.1 (0.06/0.08) fertility 0.66 (0.62/0.7) 0.69 (0.62/0.69) 0.65 (0.64/0.7) 0.64 (0.57/0.64) 0.05 (0.06/0.06) heart-hungarian 0.75 (0.7/0.77) 0.75 (0.7/0.77) 0.71 (0.56/0.72) 0.85 (0.82/0.86) 0.14 (0.26/0.14) hepatitis 0.75 (0.74/0.78) 0.75 (0.74/0.78) 0.73 (0.69/0.75) 0.77 (0.77/0.9) 0.05 (0.08/0.15) hill-valley 0.64 (0.64/0.65) 0.65 (0.64/0.65) 0.64 (0.64/0.67) 0.64 (0.64/0.65) 0.0 (0.0/0.01) mammographic 0.77 (0.77/0.77) 0.77 (0.77/0.77) 0.57 (0.56/0.62) 0.78 (0.78/0.8) 0.21 (0.22/0.18) monks-1 0.67 (0.64/0.71) 0.66 (0.64/0.71) 0.49 (0.48/0.51) 0.57 (0.51/0.61) 0.17 (0.15/0.2) planning 0.53 (0.51/0.61) 0.52 (0.51/0.61) 0.53 (0.52/0.53) 0.7 (0.68/0.74) 0.17 (0.17/0.21) spectf 0.64 (0.62/0.7) 0.64 (0.62/0.7) 0.56 (0.53/0.56) 0.58 (0.56/0.66) 0.08 (0.09/0.14) horse-colic 0.75 (0.75/0.76) 0.59 (0.57/0.61) 0.74 (0.73/0.75) 0.85 (0.85/0.85) 0.26 (0.27/0.24) ilpd-indian-liver 0.59 (0.57/0.6) 0.59 (0.57/0.6) 0.53 (0.53/0.57) 0.72 (0.7/0.73) 0.19 (0.17/0.17) parkinsons 0.74 (0.72/0.74) 0.74 (0.72/0.74) 0.65 (0.65/0.74) 0.88 (0.86/0.9) 0.23 (0.21/0.16) pima 0.68 (0.66/0.68) 0.68 (0.66/0.68) 0.68 (0.64/0.7) 0.87 (0.86/0.88) 0.2 (0.22/0.19) tic-tac-toe 0.98 (0.98/0.98) 0.76 (0.69/0.8) 0.98 (0.98/0.99) 1.0 (1.0/1.0) 0.24 (0.31/0.2) statlog-heart 0.71 (0.7/0.73) 0.71 (0.7/0.73) 0.7 (0.67/0.73) 0.84 (0.83/0.86) 0.14 (0.17/0.13) ionosphere 0.85 (0.83/0.86) 0.76 (0.73/0.76) 0.84 (0.84/0.84) 0.88 (0.88/0.89) 0.12 (0.15/0.12)

Tuning Table 2 shows results for our tuning task on an additional 7 datasets, as well as the 10 given in Table 1. We report the interquartile range as well as median test accuracies for each method. We observe similar results as presented in the main text. Only one dataset (tic-tac-toe) shows no variation in test accuracy as we explore the optimal set.

Pruning: Figure 4 shows train and test accuracy for our optimal/least-squares pruning method as well as magnitude/gradient-based pruning and random pruning on the same five datasets from the UCI repository as presented in Figure 2. Our approach shows significantly less decay in train accuracy as neurons are pruned; this matches the intuition of the least-squares heuristic for pruning, which selects the coefficients 𝛽 to best preserve the model fit.

We observe that both our pruning method and pruning by neuron/gradient norm show very similar training accuracy until most of the neurons have been pruned. While this behavior is expected from our theory-based approach, it is somewhat surprising that pruning by neuron/gradient-norm also maintains train accuracy nearly as well. This behavior suggests that there are many neurons with very small norm which can be eliminated without significantly affecting the model prediction.

Figure 5 presents results for neuron pruning on five additional datasets from the UCI repository, while Figure 7 shows results for three binary classification tasks taken from the MNIST dataset. The trends are generally the same as in Figure 4, with our approach (Theory/LS) outperforming the baselines. Finally Figure 6 extends the results on CIFAR-10 given in Figure 3 with one additional task and with training accuracies.

D.2Experimental Details

Now we give the details necessary to reproduce our experiments. Our experiments use the pre-processed versions of UCI datasets provided by Delgado et al. (2014), but do we do not use their evaluation procedure as it is known to have data leakage.

D.2.1Tuning

We select 17 binary classification datasets from the UCI repository. For each dataset we use a random 60/20/20 split of the data into train, validation, and test sets. We use the commercial interior point method MOSEK (ApS, 2022) through the interface provided by CVXPY (Diamond & Boyd, 2016) to compute the initial model which is then tuned. We modify the tolerances of this method to use 𝜏

10 − 8 for measuring both primal convergence and violation of the constraints. For each dataset, we use fixed 𝜆

0.001 and a maximum of 1000 neurons. To compute the min ℓ 2 -norm optimal model, we use the MOSEK and the optimization problem given in Section 3.5.

To approximate the maximum ℓ 2 -norm model, we solve the following program:

𝛼 *

arg ⁢ max 𝛼 ≥ 0 ∑ 𝑏 𝑖 ∈ 𝒮 𝜆 𝛼 𝑏 𝑖 ⁢  s.t. ⁢ ∑ 𝑏 𝑖 ∈ 𝒮 𝜆 𝛼 𝑏 𝑖 ⁢ 𝑋 𝑏 𝑖 ⁢ 𝑣 𝑏 𝑖

𝑦 ^ .

This is a linear program which is straightforward to solve using interior point methods. Moreover, we have

‖ 𝑤 * ‖ 2 2

𝜆 2 ⁢ ∑ 𝑏 𝑖 ( 𝛼 𝑏 𝑖 * ) 2 ,

so that ∑ 𝑏 𝑖 𝛼 𝑏 𝑖 acts as an approximation, where we recall 𝛼 𝑏 𝑖 ≥ 0 necessarily.

To tune each model with respect to the validation/test MSE, we solve the following optimization problem:

min 𝑤 ⁡ { 1 2 ⁢ ‖ 𝑋 ~ ⁢ 𝑤 − 𝑦 ~ ‖ 2 2 : 𝑤 ∈ 𝒲 * ⁢ ( 𝜆 ) } ,

with respect to the parameters of the convex formulation. Here, ( 𝑋 ~ , 𝑦 ~ ) is either the validation or test set. We repeat each experiment five times with different random splits of the data and random resamplings of 500 activation patterns 𝐷 𝑖 . This guarantees that each non-convex network has at most 1000 neurons after optimization, although it may have less due to the sparsity inducing penalty.

D.2.2Pruning

Methods: We use the augmented Lagrangian method of Mishkin et al. (2022) to compute the starting model which is then pruned. We modify the tolerances of this method to use 𝜏

10 − 8 for measuring both primal convergence and violation of the constraints.

Pruning by neuron magnitude is straightforward: we sort the neurons by ‖ 𝑊 1 ⁢ 𝑖 ⁢ 𝑤 2 ⁢ 𝑖 ‖ 2 , which measures the total magnitude of the neuron, and then drop the smallest one. For pruning by gradient norm, we compute 𝐺 1 ⁢ 𝑖

∇ 𝑊 1 ⁢ 𝑖 𝐿 ⁢ ( 𝑓 𝑊 1 , 𝑤 2 ⁢ ( 𝑍 ) , 𝑦 ) , 𝑔 2 ⁢ 𝑖

∇ 𝑊 2 ⁢ 𝑖 𝐿 ⁢ ( 𝑓 𝑊 1 , 𝑤 2 ⁢ ( 𝑍 ) , 𝑦 ) and then score each neuron as

𝑠 𝑖

‖ 𝑊 1 ⁢ 𝑖 ⋅ 𝐺 1 ⁢ 𝑖 ⁢ 𝑤 2 ⁢ 𝑖 ⁢ 𝑔 2 ⁢ 𝑖 ‖ 2 ,

where ⋅ indicates the element-wise product. The neuron with smallest score is zeroed. This is consistent the existing implementations of pruning by gradient norm (Blalock et al., 2020) and attempts to measure the variation of a linearization of the loss in neuron 𝑖 . For Random, we simply select a neuron from a uniform random distribution.

For Optimal/LS, we start by using Algorithm 1 to prune until no linear dependence exists amongst the neuron fits 𝐷 𝑖 ⁢ 𝑍 ⁢ 𝑊 1 ⁢ 𝑖 . At this point, we choose 𝛽 to minimize the squared-error in the training fit. We choose the neuron to prune by selecting the index that minimizing the residual in the least-squares fit,

𝑖 𝑘

arg ⁢ min 𝑗 min 𝛽 ⁡ 1 2 ⁢ ‖ ∑ 𝑖 ≠ 𝑗 𝛽 𝑖 ⁢ 𝐷 𝑖 ⁢ 𝑍 ⁢ 𝑤 𝑖 − 𝐷 𝑗 ⁢ 𝑍 ⁢ 𝑤 𝑗 ‖ .

This produced the best result in all of our experiments, although you can also select 𝑖 𝑘 using neuron magnitude or any other rule in the literature on structured pruning.

UCI Datasets: We select 10 moderately-sized binary classification datasets from the UCI repository. For each dataset we use a random 50/50 split of the data into train and test sets, fixed 𝜆

0.01 , and sample 25 activation patterns 𝐷 𝑖 . This results in a maximum of 50 neurons in each final model; since the datasets are low dimensional, randomly sampling activation patterns typically results in fewer than 50 neurons. All results are repeated for five different random splits and we plot the median and interquartile ranges of the results.

MNIST and CIFAR-10: We select three binary classification tasks from each dataset such that no task shares a target with another task. For each dataset we use a random 50/50 split of the data into train and test sets. For MNIST, we use 𝜆 − 0.01 , while we used 𝜆

0.05 for CIFAR-10. We sample 50 activation patterns 𝐷 𝑖 for each tasking, which produces a maximum of 100 neurons in each final model. All results are repeated for five different random splits and we plot the median and interquartile ranges of the results.

Generated by L A T E xml Instructions for reporting errors

We are continuing to improve HTML versions of papers, and your feedback helps enhance accessibility and mobile support. To report errors in the HTML that will help us improve conversion and rendering, choose any of the methods listed below:

Click the "Report Issue" button. Open a report feedback form via keyboard, use "Ctrl + ?". Make a text selection and click the "Report Issue for Selection" button near your cursor. You can use Alt+Y to toggle on and Alt+Shift+Y to toggle off accessible reporting links at each section.

Our team has already identified the following issues. We appreciate your time reviewing and reporting rendering errors we may not have found yet. Your efforts will help us improve the HTML versions for all readers, because disability should not be a barrier to accessing research. Thank you for your continued support in championing open access for all.

Have a free development cycle? Help support accessibility at arXiv! Our collaborators at LaTeXML maintain a list of packages that need conversion, and welcome developer contributions.

Report Issue Report Issue for Selection