Lexicographic and Depth-Sensitive Margins in Homogeneous and Non-Homogeneous Deep Models

Introduction

Inductive bias introduced through the learning process plays a crucial role in training deep neural networks and in the generalization properties of the learned models (Neyshabur et al., 2015b, a; Zhang et al., 2017; Keskar et al., 2017; Neyshabur et al., 2017; Wilson et al., 2017; Hoffer et al., 2017). Deep neural networks used in practice are typically highly overparameterized, i.e., have far more trainable parameters than training examples. Thus, using these models, it is usually possible to fit the data perfectly and obtain zero training error (Zhang et al., 2017). However, simply minimizing the training loss does not guarantee good generalization to unseen data – many global minima of the training loss indeed have very high test error (Wu et al., 2017). The inductive bias introduced in our learning process affects which specific global minimizer is chosen as the predictor. Therefore, it is essential to understand the nature of this inductive bias to understand why overparameterized models, and particularly deep neural networks, exhibit good generalization abilities.

A common way to introduce an additional inductive bias in overparameterized models is via small amounts of regularization, or loose constraints . For example, Rosset et al. (2004b, a); Wei et al. (2018) show that, in overparameterized classification models, a vanishing amount of regularization, or a diverging norm constraint can lead to max-margin solutions, which in turn enjoy strong generalization guarantees.

In this work we similarly investigate the connection between margin maximization and the limits of

The “optimization path” of unconstrained, unregularized gradient descent.

The “constrained path”, where we optimize with a diverging (increasingly loose) constraint on the norm of the parameters.

The closely related “regularization path”, of solutions with decreasing penalties on the norm.

To better understand the questions we tackle in this paper, and our contribution toward understanding the inductive bias introduced in training, let us briefly survey prior work.

Rosset et al. (2004b, a); Wei et al. (2018) investigated the connection between the regularization and constrained paths and the max-margin solution. Rosset et al. (2004a, b) considered linear (hence homogeneous) models with monotone loss and explicit norm regularization or constraint, and proved convergence to the max-margin solution for certain loss functions (e.g., logistic loss) as the regularization vanishes or the norm constraint diverges. Wei et al. (2018) extended the regularization path result to non-linear but positive-homogeneous prediction functions,

e.g. as obtained by a ReLU network with uniform depth.

These results are thus limited to only positive homogeneous predictors, and do not include deep networks with bias parameters, ensemble models with different depths, ResNets, or other models with skip connections. Here, we extend this connection beyond positive homogeneous predictors.

Furthermore, even for homogeneous or linear predictors, there might be multiple margin maximizing solutions. For linear models, Rosset et al. (2004b) alluded to a refined set of maximum margin classifiers that in addition to maximizing the distance to the closest data point (max-margin), also maximize the distance to the second closest data point, and so on. We formulate such special maximum margin solutions as “lexicographic max-margin” classifiers which we introduce in Section 4.2. We show that for general continuous homogeneous models, the constrained path with diverging norm constraint converges to these more refined “lexicographic max-margin” classifiers.

Another line of works studied the connection between unconstrained, unregularized optimization with a specific algorithm (i.e., the limit of the “optimization path”), and the max-margin solution. For linear prediction with the logistic loss (or other exponential tail losses), we now know gradient descent (Soudry et al., 2018b; Ji & Telgarsky, 2018) as well as SGD (Nacson et al., 2019b) converges in direction to the max-margin solution, while steepest descent with respect to an arbitrary norm converges to the max-margin w.r.t. the corresponding norm (Gunasekar et al., 2018b). All the above results are for linear prediction. Gunasekar et al. (2018a); Nacson et al. (2019a); Ji & Telgarsky (2019) obtained results establishing convergence to margin maximizing solutions also for certain uniform-depth linear networks (including fully connected networks and convolutional networks), which still implement linear model. Separately, Xu et al. (2019) analyzed a single linear unit with ReLU activation—a limited non-linear but still positive homogeneous model. Lastly, Soudry et al. (2018a) analyzed a non-linear ReLU network where only a single weight layer is optimized.

Here, we extend this relationship to general, non-linear and positive homogeneous predictors for which the loss can be minimized only at infinity. We establish a connection between the limit of unregularized unconstrained optimization and the max-margin solution.

We note that the connection between regularization path and optimization path was previously considered in a different settings, where a finite (global) minimum exists. In such settings the questions asked are different than the ones we consider here, and are not about the limit of the paths. E.g., Ali et al. (2018) showed for gradient flow a multiplicative relation between the risk for the gradient flow optimization path and the ridge-regression regularization path. Also, Suggala et al. (2018) showed that for gradient flow and strongly convex and smooth loss function – gradient descent iterates on the unregularized loss function are pointwise close to solutions of a corresponding regularized problem.

Contributions

We examine overparameterized realizable problems (i.e., where it is possible to perfectly classify the training data), when training using monotone decreasing classification loss functions. For simplicity, we focus on the exponential loss. However, using similar techniques as in Soudry et al. (2018a) our results should extend to other exponential-tailed loss functions such as the logistic loss and its multi-class generalization. This is indeed the common setting for deep neural networks used in practice.

As long as the margin attainable by a (unregularized, unconstrained) model is unbounded, then the margin of the constrained path converges to the max-margin. See Corollary 1.

If additional conditions hold, the constrained path also converges to the “margin path” in parameter space (the path of minimal norm solutions attaining increasingly large margins). See section 3.1.

If the model is a sum of homogeneous functions of different orders (i.e., it is not homogeneous itself), then we can still characterize the asymptotic solution of both the constrained path and the margin path. See Theorem 3.2.

This solution implies that in an ensemble of homogeneous neural networks, the ensemble will aim to discard the most shallow network. This is in contrast to what we would expect from considerations of optimization difficulty (since deeper networks are typically harder to train (He et al., 2016)).

This also allows us to represent hard-margin SVM problems with unregularized bias using such models. This is in contrast to previous approaches which fail to do so, as pointed out recently (Nar et al., 2019).

We find general conditions under which the optimization path converges to stationary points of the margin path or the constrained path. See section 4.1.

We show that the constrained path converges to a specific type max-margin solution, which we term the “lexicographic max-margin”. The authors thank Rob Shapire for the suggestion of the nomenclature during initial discussions. See Theorem 4.

Preliminaries and Basic Results

In this paper, we will study the following exponential tailed loss function

We will use in our results the following basic lemma

exists and is strictly monotonically decreasing in $\rho$, $\forall\rho\geq\rho_{0}$, for some $\rho_{0}$. Then, $\forall\rho\geq\rho_{0}$, the optimization problem in eq. 2 has the same set of solutions $\left(\mathbf{w}\right)$ as

whose minimum is obtained at $g(\mathbf{w})=\rho$.

The optimization path in the Euclidean norm $\boldsymbol{\theta}\left(t\right)$, is given by the direction of iterates of gradient descent algorithm with initialization $\boldsymbol{\theta}\left(0\right)$ and learning rates $\left\{\eta_{t}\right\}_{t=1}^{\infty}$,

2 The Constrained Path

The constrained path for the loss in eq. 1 is given by minimizer of the loss at a given norm value $\rho>0$, i.e.,

The constrained path was previously considered for linear models (Rosset et al., 2004a). However, most previous works (e.g. Rosset et al. (2004b); Wei et al. (2018)) focused on the regularization path, which is the minimizer of the regularized loss. These two paths are closely linked, as we discuss in more detail in Appendix F.

Denote the constrained minimum of the loss as follows:

$\mathcal{L}^{*}\left(\rho\right)$ exists for any finite $\rho$ as the minimum of a continuous function on a compact set.

There exists $\rho_{0}$ such that $\mathcal{L}^{*}\left(\rho\right)$ is strictly monotonically decreasing to zero for any $\rho\geq\rho_{0}$.

enables an alternative form of the constrained path

Under assumption 1, for all $\rho>\rho_{0}$ and for all $\theta_{c}\in\Theta_{c}\left(\rho\right)$, we have $\left\|\boldsymbol{\theta}_{c}\right\|=1$.

Let $\rho>0$. We assume, in contradiction, that $\exists\theta_{c}\in\Theta_{c}\left(\rho\right)$ so that $\left\|\boldsymbol{\theta}_{c}\right\|=b<1$. This implies that $\mathcal{L}^{*}\left(\rho\right)=\mathcal{L}^{*}\left(\rho b\right)$ which contradicts our assumption that $\mathcal{L}^{*}\left(\rho\right)$ is strictly monotonically decreasing. ∎

3 The Margin Path

and the max-margin at scale of $\rho>0$ as

Note that for all $\rho$, this maximum exists as the maximum of a continuous function on a compact set.

There exist $\rho_{0}$ such that $\gamma^{*}\left(\rho\right)$ is strictly monotonically increasing to $\infty$ for any $\rho\geq\rho_{0}$.

Many common prediction functions satisfy this assumption, including the sum of positive-homogeneous prediction functions.

Using Lemma 1 with Assumption 2, we have:

Non-Homogeneous Models

For all $\rho$, the constrained path margin deviation from the max-margin is bounded, as we prove next.

For all $\rho$, and every $\boldsymbol{\theta}_{c}\left(\rho\right)$ in $\Theta_{c}\left(\rho\right)$

If $\lim_{\rho\rightarrow\infty}\gamma^{*}\left(\rho\right)=\infty$, then for all $\rho$, and every $\boldsymbol{\theta}_{c}\left(\rho\right)$ in $\Theta_{c}\left(\rho\right)$

The last corollary states that the margin of the constrained path converges to the maximum margin. However, this does not necessarily imply convergence in parameter space, i.e., this result does not guaranty that $\Theta_{c}\left(\rho\right)$ converges to $\Theta_{m}\left(\rho\right)$. We analyze some positive and negative examples to demonstrate this claim.

It is straightforward to see that, for $\alpha$-positive homogeneous prediction functions (Definition 1) the margin path $\Theta_{m}(\rho)$ in eq. 6 is the same set for any $\rho$, and is given by

Additionally, as we show next, for such models Lemma 3 implies convergence in parameter space, i.e., $\Theta_{c}\left(\rho\right)$ converges to $\Theta_{m}\left(\rho\right)$. To see this, notice that for $\alpha$-positive homogeneous functions $f_{n}$, $\forall\boldsymbol{\theta}_{c}\left(\rho\right)\in\Theta_{c}\left(\rho\right)$:

By continuity, the last equation implies that $\Theta_{c}\left(\rho\right)$ converges to $\Theta_{m}\left(\rho\right)$. For full details see Appendix D.1.

Connection to previous results: For linear models, Rosset et al. (2004a) connected the $L_{1}$ constrained path and maximum $L_{1}$ margin solution. In addition, for any norm, Rosset et al. (2004b) showed that the regularization path converges to the limit of the margin path. In a recent work, Wei et al. (2018) extended this result to homogeneous models with cross-entropy loss. Here, for homogeneous models and any norm, we show a connection between the constrained path and the margin path.

Extension: Later, in Theorem 4 we prove a more refined result: the constrained path converges to a specific subset of the margin path set (the lexicographic max-margin set).

In contrast, in general models, 8 does not necessarily imply convergence in the parameter space. We demonstrate this result in the next example.

Example 2: log predictor: We denote $\mathbf{z}_{n}=y_{n}\mathbf{x}_{n}$ for some dataset $\left\{\mathbf{x}_{n},y_{n}\right\}_{n=1}^{N}$, with features $\mathbf{x}_{n}$ and label $y_{n}$. We examine the prediction function $f_{n}\left(\rho,\boldsymbol{\theta}\right)=\log\left(\rho\boldsymbol{\theta}^{\top}\mathbf{z}_{n}\right)$ for $\boldsymbol{\theta}^{\top}\mathbf{z}_{n}>0$. We focus on the loss function tail behaviour and thus only care about the loss function behaviour in $\boldsymbol{\theta}^{\top}\mathbf{z}_{n}>0$ region. We assume that a separator which satisfy this constraint exists since we are focusing on realizable problems.

Since $\log(.)$ is strictly increasing and $\rho>0$, we have

but clearly, $\widetilde{\gamma}\left(\boldsymbol{\theta}_{c}\left(\rho\right)\right)\nrightarrow\widetilde{\gamma}^{*}$. Thus, Lemma 3 does not guarantee that $\widetilde{\gamma}\left(\boldsymbol{\theta}_{c}\left(\rho\right)\right)\to\widetilde{\gamma}^{*}$ as $\rho\to\infty$, or that $\Theta_{c}\left(\rho\right)$ converges to $\Theta_{m}\left(\rho\right)$.

Analogies with regularization and optimization paths: This example demonstrates that for the prediction function $\log(\rho\boldsymbol{\theta}^{\top}\mathbf{z})$ for $\boldsymbol{\theta}^{\top}\mathbf{z}>0$, the constrained path does not necessarily converge to the margin path. This is equivalent to setup A: linear prediction models with loss function $\exp\left(-\log\left(u\right)\right)$. Rosset et al. (2004b) and Nacson et al. (2019a) state related results for setup A. Both works derived conditions on the loss function that ensure convergence to the margin path from the regularization/ optimization path respectively. Rosset et al. (2004b) showed that in setup A the regularization path does not necessarily converge to the margin path. (Nacson et al., 2019a) showed a similar result for the optimization path, i.e., that in setup A the optimization path does not necessarily converge to the margin path. Both results align with our results for the constrained path.

In contrast, according to the conditions of Rosset et al. (2004b); Nacson et al. (2019a), we know that if the prediction function is $\log^{1+\epsilon}(\rho\boldsymbol{\theta}^{\top}\mathbf{z})$ for some $\epsilon>0$ and $\boldsymbol{\theta}^{\top}\mathbf{z}>0$, then the regularization path and optimization path do converge to the margin path. In the next example, we show that this is also true for the constrained path.

Example 3: $(1+\epsilon)$-log predictor: We examine the prediction function $f_{n}\left(\rho,\boldsymbol{\theta}\right)=\log^{1+\epsilon}\left(\rho\boldsymbol{\theta}^{\top}\mathbf{z}_{n}\right)$ for $\boldsymbol{\theta}^{\top}\mathbf{z}_{n}>0$ and some $\epsilon>0$. Since the log function is strictly increasing and $\epsilon,\rho>0$, we have

For all $\boldsymbol{\theta}_{c}\left(\rho\right)\in\Theta_{c}\left(\rho\right)$:

For $\rho\to\infty$ we must have $\left(\log\left(\widetilde{\gamma}^{*}\right)-\log\left(\widetilde{\gamma}\left(\boldsymbol{\theta}_{c}\left(\rho\right)\right)\right)\right)\to 0$, which implies, by continuity, that $\Theta_{c}\left(\rho\right)$ converges to $\Theta_{m}\left(\rho\right)$. For details, see Appendix D.2.

2 Sum of Positively Homogeneous Functions

Remark: The results in this subsection are specific for the Euclidean or $L_{2}$ norm.

Let $f_{n}\left({\rho}\boldsymbol{\theta}\right)$ be functions that are a finite sum of positively homogeneous functions, i.e., for some finite $K$:

where $\boldsymbol{\theta}=\left[\boldsymbol{\theta}_{1},\dots,\boldsymbol{\theta}_{K}\right]$ and $f_{n}^{\left(k\right)}\left(\boldsymbol{\theta}_{k}\right)$ are $\alpha_{k}$-positive homogeneous functions, where $0<\alpha_{1}<\alpha_{2}<\dots<\alpha_{K}$.

First, we characterize the asymptotic form of the margin path in this setting.

Let $f_{n}\left(\boldsymbol{\theta}\right)$ be a sum of positively homogeneous functions as in eq. 10. Then, the set of solutions of

where the $o\left(1\right)$ term is vanishing as $\gamma^{*}\left(\rho\right)\rightarrow\infty$, and

We write the original optimization problem

Dividing by $\gamma^{*}\left(\rho\right)$, using the $\alpha_{k}$ positive homogeneity of $f_{n}^{\left(k\right)}$, and changing the variables as $\boldsymbol{\theta}_{k}=\frac{1}{{\rho}}\boldsymbol{w}_{k}\left(\gamma^{*}\left(\rho\right)\right)^{\frac{1}{\alpha_{k}}}$, we obtain an equivalent optimization problem

We denote the set of solutions of eq. 14 as $\mathcal{W}\left(\gamma^{*}\left(\rho\right)\right)$. Taking the limit of $\gamma^{*}\left(\rho\right)\rightarrow\infty$ of this optimization problem we find that any solution $\boldsymbol{w}\in\mathcal{W}\left(\gamma^{*}\left(\rho\right)\right)$ must minimize the first term in the sum $\left\|\boldsymbol{w}_{1}\right\|^{2}$, and only then the other terms. Therefore the asymptotic solution is of the form of eqs. 12 and 13. We prove this reasoning formally in Appendix B, i.e., we show that

The solution of eq. 14 is the same solution described in Lemma 4, i.e., eqs. 12 and 13.

The following Lemma will be used to connect the constrained path to the characterization of the margin path.

Let $f_{n}\left({\rho}\boldsymbol{\theta}\right)$ be a sum of positively homogeneous functions as in eq. 10. Any path $\boldsymbol{\theta}\left(\rho\right)$ such that

is of the form described in eqs. 12 and 13.

Combining Lemma 3, 4 and Lemma 5 we obtain the following Theorem

where the $o\left(1\right)$ term is vanishing as $\gamma^{*}(\rho)\rightarrow\infty$, and

Theorem 1 implications: An important implication of Theorem 1 is that an ensemble on neural networks will aim to discard the shallowest network in the ensemble. Consider the following setting: for each $k\in\left\{1,\dots,K\right\}$, the function $\forall n:\,f_{n}^{\left(k\right)}\left({\rho}\boldsymbol{\theta}_{k}\right)$ represents a prediction function of some feedforward neural network with no bias, all with the same positive-homogeneous activation function $\sigma\left(\cdot\right)$ of some degree $\alpha$ (e.g., ReLU activation is positive-homogeneous of degree $1$). Note that in this setup, each of the $k$ prediction functions $f_{n}^{\left(k\right)}\left({\rho}\boldsymbol{\theta}_{k}\right)$ is also a positive-homogeneous function. In particular, network $k$ with depth $d_{k}$ is positive homogeneous with degree $\alpha_{k}=\alpha{d_{k}}$ where $\alpha$ is the activation function degree. Since all the networks have the same activation function, deeper networks will have larger degree. We assume WLOG that $d_{1}<d_{2}<\dots<d_{K}$. This implies that $\alpha_{1}<\alpha_{2}<\dots<\alpha_{K}$. In this setting, $\forall n:\,f_{n}\left({\rho}\boldsymbol{\theta}\right)=\sum_{k=1}^{K}f_{n}^{\left(k\right)}\left({\rho}\boldsymbol{\theta}_{k}\right)$ represents an ensemble of these networks. From Theorem 1, the solution of the constrained path will satisfy

where $\boldsymbol{w}^{*}\in\mathcal{W}$ and $\mathcal{W}$ is calculated using eq. 13. Examining equation 13, we observe that the network aims to minimize the $\boldsymbol{w}_{1}$ norm. In particular, if the network ensemble can satisfy the constraints $\forall n:f_{n}\left(\boldsymbol{w}\right)\geq 1$ with $\boldsymbol{w}_{1}=\mathbf{0}$, then the first equation obtained solutions will satisfy $\boldsymbol{w}_{1}=\mathbf{0}$. Thus the ensemble will discard the shallowest network if it is ”unnecessary” to satisfy the constraint.

Furthermore, from eq. 14 we conjecture that after discarding the shallowest “unnecessary” network, the ensemble will tend to minimize $\lVert\boldsymbol{w}_{2}\rVert$, i.e., to discard the second shallowest ”unnecessary” network. This will continue until there are no more ”unnecessary” shallow networks. In other words, we conjecture that the an ensemble of neural networks will aim to discard the shallowest “unnecessary” networks.

Additionally, using Theorem 1 we can now represent hard-margin SVM problems with unregularized bias. Previous results only focused on linear prediction functions without bias. Trying to extend these results to SVM with bias by extending all the input vectors $\mathbf{x}_{n}$ with an additional ${}^{\prime}1^{\prime}$ component would fail since the obtained solution in the original $\mathbf{x}$ space is the solution of

Homogeneous Models

In the previous section we connected the constrained path to the margin path. We would like to refine this characterization and also understand the connection to the optimization path. In this section we are able to do so for prediction functions $f_{n}\left(\boldsymbol{\theta}\right)$ which are $\alpha$-positive homogeneous functions (definition 1).

In the homogeneous case, eq. 7 is equivalent, $\forall\rho$, to

Remark: The results in this subsection are specific for the Euclidean or $L_{2}$ norm, as opposed to many of the results in this paper which are stated for any norm.

In this section, we link the optimization path to the margin path and the constrained path. These results require the following smoothness assumption:

We assume $f_{n}(\cdot)$ is a $\mathcal{C}^{2}$ function.

The limit of the margin path for homogeneous models is given by eq. 18. In this section we first relate the optimization path to this limit of margin path.

The first-order optimality conditions of 18 are:

$\forall n$, $f_{n}(\boldsymbol{\theta})\geq\gamma^{*}(1)$

We denote by $\Theta_{m}^{s}$ the set of first-order stationary points.

with $\lVert\textbf{a}\rVert_{1}=1$, $\lVert\bar{}\boldsymbol{w}{()}\rVert_{2}=1$, $\lim\limits_{t\to\infty}h(t)=0$, $\lim\limits_{t\to\infty}\epsilon_{n}(t)=0$, and $\lim\limits_{t\to\infty}\boldsymbol{\delta}(t)=0$.

Constraint qualifications allow the first-order optimality conditions of Definition 3 to be a necessary condition for optimality. Without constraint qualifications, the global optimum need not satisfy the optimality conditions.

LICQ is the simplest among many constraint qualification conditions identified in the optimization literature (Nocedal & Wright, 2006).

For example, in linear SVM, LICQ is ensured if the set of support vectors is linearly independent. Consider $f_{n}(\boldsymbol{\theta})=\mathbf{x}_{n}^{\top}\boldsymbol{\theta}$ and $\mathbf{x}_{n}$ be the support vectors. Then $\nabla f_{n}(\bar{}\boldsymbol{w}{()})=\mathbf{x}_{n}$ , and so linear independence of the support vectors implies LICQ. For data sampled from an absolutely continuous distribution, the SVM solution will always have linearly independent support vectors (Soudry et al., 2018b, Lemma 12), but LICQ may fail when the data is degenerate.

Define $\bar{}\boldsymbol{w}{()}=\lim\limits_{t\rightarrow\infty}\frac{\boldsymbol{\theta}(t)}{\lVert\boldsymbol{\theta}(t)\rVert_{2}}$. Under Assumptions 3, 4, and constraint qualification at $\bar{}\boldsymbol{w}{()}$ (Assumption 5), $\bar{}\boldsymbol{w}{()}$ is a first-order stationary point of 18.

The proof of Theorem 2 can be found in Appendix E.1.

Next, we study how the optimization path as $t\to\infty$ converges to stationary points of the constrained path with $\rho\to\infty$.

The first-order optimally conditions of the constrained path $\min_{\|\boldsymbol{\theta}\|\leq 1}\mathcal{L}(\rho\boldsymbol{\theta})$, require that the constraints hold, and the gradient of the Lagrangian of the constrained path

Under Assumption 1, $\boldsymbol{\theta}$ is first-order optimal for the problem $\min_{\|\boldsymbol{\theta}\|\leq 1}\mathcal{L}(\rho\boldsymbol{\theta})$ if it satisfies:

On many paths the gradient of the Lagrangian goes to zero as $\rho\rightarrow\infty$. However, we have a faster vanishing rate for the specific optimization paths that follow Definition 4 below. Therefore, these paths better approximate true stationary points:

A sequence $\widetilde{\boldsymbol{\theta}}(t)$ is first-order optimal for $\min_{\|\boldsymbol{\theta}\|\leq 1}\mathcal{L}(\rho\boldsymbol{\theta})$ with $\rho\to\infty$ if

To relate the limit points of gradient decent to the constrained path, we will focus on stationary points of the constrained path that minimize the loss.

Let $\bar{}\boldsymbol{w}{()}=\lim\limits_{t\to\infty}\frac{\boldsymbol{\theta}(t)}{\|\boldsymbol{\theta}(t)\|}$ be the limit direction of gradient descent. Under Assumptions 1, 3, 4, and constraint qualification at $\bar{}\boldsymbol{w}{()}$ (Assumption 5), the sequence $\boldsymbol{\theta}(t)/\lVert\boldsymbol{\theta}(t)\rVert$ is a first-order optimal point for $\rho\to\infty$ (Definition 4).

The proof of Theorem 3 can be found in Appendix E.2.

2 Lexicographic Max-Margin

Recall that for positive homogeneous prediction functions, the margin path $\Theta_{m}(\rho)$ in eq. 11 is the same set for any $\rho$ and is given by

For non-convex functions $f_{n}$ or non-Euclidean norms $\|.\|$, the above set need not be unique. In this case, we define the following refined set of maximum margin solution set

The lexicographic margin set denoted by $\Theta_{m,N}^{*}$ is given by the following iterative definition of $\Theta_{m,k}^{*}$ for $k=1,2,\ldots,N$:

In the above definition, $\Theta_{m,1}^{*}=\Theta_{m}^{*}$ denotes the set of maximum margin solutions, $\Theta_{m,1}^{*}$ denotes the subset of $\Theta_{m,1}^{*}$ with second smallest margin, and so on.

Using this notation, we can rewrite $\Theta_{m,k+1}^{*}$ as

We also define the limit set of constrained path as follows:

The limit set of constrained path is defined as follows:

For $\alpha$-positive homogeneous prediction functions the limit set of constrained path is contained in the lexicographic maximum margin set, i.e., $\Theta_{c}^{\infty}\subseteq\Theta_{m,N}^{*}$.

The proof of the above Theorem follows from adapting the arguments of (Rosset et al., 2004a) (Theorem $7$ in Appendix $B.2$) for general homogeneous models. We show the complete proof in Appendix E.3.

Summary

In this paper we characterized the connections between the constrained, margin and optimization paths. First, in Section 3, we examined general non-homogeneous models. We showed that the margin of the constrained path solution converges to the maximum margin. We further analyzed this result and demonstrated how it implies convergence in parameters, i.e., $\Theta_{c}\left(\rho\right)$ converges to $\Theta_{m}\left(\rho\right)$, for some models. Then, we examined functions that are a finite sum of positively homogeneous functions. These prediction function can represent an ensemble of neural networks with positive homogeneous activation functions. For this model, we characterized the asymptotic constrained path and margin path solution. This implies a surprising result: ensembles of neural networks will aim to discard the most shallow network. In the future work we aim to analyze sum of homogeneous functions with shared variables, such as ResNets.

Second, in Section 4 we focus on homogeneous models. For such models we link the optimization path to the margin and constrained paths. Particularly, we show that the optimization path converges to stationary points of the constrained path and margin path. In future work, we aim to extend this to non-homogeneous models. In addition, we give a more refined characterization of the constrained path limit. It will be interesting to find whether this characterization be further refined to answer whether the weighting of the data point can have any effect on the selection of the asymptotic solution — as (Byrd & Lipton, 2018) observed empirically that it did not.

Acknowledgements

The authors are grateful to C. Zeno, and N. Merlis for helpful comments on the manuscript. This research was supported by the Israel Science foundation (grant No. 31/1031), and by the Taub foundation. SG and NS were partially supported by NSF awards IIS-1302662 and IIS-1764032.

References

Appendix

Let $\mathbf{w}^{*}\left(\rho\right)$ be a solution of the optimization problem in eq. 2. Then, $g\left(\mathbf{w}^{*}\left(\rho\right)\right)=\rho$, since otherwise we could have decreased $\rho$ without changing $\mathbf{w}^{*}\left(\rho\right)$ or $\phi(\rho)$ — and this is impossible, since $\phi(\rho)$ is strictly monotonically decreasing. Therefore, we cannot decrease $g\left(\mathbf{w}\right)$ below $\rho$ without increasing $f(\mathbf{w})$ above $\phi(\rho)$. This implies that $\mathbf{w}^{*}\left(\rho\right)$ is a solution of the optimization problem in eq. 3 with $\phi\left(\rho\right)$. Next, all that is left to show that eq. 3 has no additional solutions. Suppose by contradiction there were such solutions $\mathbf{w}^{\prime}\left(\rho\right)$. Since they are also minimizers of eq. 3, like $\mathbf{w}^{*}\left(\rho\right)$, they have the same minimum value $g\left(\mathbf{w}^{\prime}\left(\rho\right)\right)=\rho$. Since they are not solutions of eq. 2, we have $f(\mathbf{w})>\phi(\rho)$. However, this means they are not feasible for eq. 3, and therefore cannot be solutions. ∎

Appendix B Proof of Claim 1

Recall we denoted the set of solutions of eq. 14 as $\mathcal{W}\left(\gamma^{*}\left(\rho\right)\right)$, and recall $\mathcal{W}$ from eq. 13. To simplify notations we omit the dependency on $\rho$ from the notation, i.e., we replace $\gamma^{*}\left(\rho\right)$ with $\gamma$. Suppose the claim was not correct. Then, there would have existed $\epsilon>0$ such that $\forall\gamma$, $\exists\gamma^{\prime}>\gamma$ such that $\exists\boldsymbol{w}^{*}\left(\gamma^{\prime}\right)\in\mathcal{W}\left(\gamma^{\prime}\right)\setminus\mathcal{B}_{\epsilon}\left(\mathcal{W}\right).$ Note that $\boldsymbol{w}^{*}\left(\gamma^{\prime}\right)\in\mathcal{W}\left(\gamma^{\prime}\right)$ is feasible in both optimization problems (eq. 13 and 14), since both problems have the same constraints. Moreover, since $\boldsymbol{w}^{*}\left(\gamma^{\prime}\right)\notin\mathcal{B}_{\epsilon}\left(\mathcal{W}\right)$ it must be sub-optimal in comparison to the solution of eq. 13. Therefore, $\exists\epsilon^{\prime}>0$ such that for any $\gamma^{\prime}$, $\left\|\boldsymbol{w}_{1}^{*}\left(\gamma^{\prime}\right)\right\|^{2}>\min_{\boldsymbol{w}\in\mathcal{W}}\left\|\boldsymbol{w}_{1}\right\|^{2}+\epsilon^{\prime}$. Then we can write (from eq. 14)

From Assumption 2 we know that $\exists c>0$ such that \text{\forall\gamma}>c a solution of the margin path exists. Therefore, $\forall\gamma\geq c$, eq. 11 is feasible. We assume, WLOG, that $c<\gamma^{\prime}$. This implies that there exist a feasible finite solution $\widetilde{\boldsymbol{w}}$ to eq. 24 which does not depend on $\gamma^{\prime}$. Therefore, $\forall\gamma^{\prime}$, $\forall\boldsymbol{w}\in\mathcal{W}\left(\gamma^{\prime}\right)$, and $\forall k\in\left[K\right]$ the values of $\left\|\boldsymbol{w}_{k}\right\|^{2}$ are respectively bounded below the values of $\left\|\widetilde{\boldsymbol{w}}_{k}\right\|^{2}$, which are independent of $\gamma^{\prime}$. This implies that if we select $\gamma^{\prime}$ large enough, we will have $\sum_{k=2}^{K}(\gamma^{\prime})^{\frac{2}{\alpha_{k}}-\frac{2}{\alpha_{1}}}\left\|\boldsymbol{w}_{k}\right\|^{2}<\epsilon^{\prime}$. This would contradict the assumption that $\boldsymbol{w}^{*}\left(\gamma^{\prime}\right)\in\mathcal{W}\left(\gamma^{\prime}\right)$ and therefore minimizes eq. 24. This implies that $\forall\epsilon$, $\exists\gamma_{0}$ such that $\forall\gamma>\gamma_{0}$, we have $\mathcal{W}\left(\gamma\right)\subset\mathcal{B}_{\epsilon}\left(\mathcal{W}\right)$, which entails the Theorem.

Appendix C Proof of Lemma 5

We assume by contradiction that yet $\boldsymbol{\theta}\left(\rho\right)$ does not have the form of eqs. 12 and 13. Without loss of generality we can write

If $\mathbf{v}_{k}\left(\rho^{\prime}\right)=\boldsymbol{w}_{k}^{*}+o\left(1\right)$, for some $\boldsymbol{w}^{*}=\left[\boldsymbol{w}_{1}^{*},\dots,\boldsymbol{w}_{K}^{*}\right]\in\mathcal{W}$. Then we could have written, from eqs. 25 and 15

which contradicts out assumption that $\rho\boldsymbol{\theta}\left(\rho\right)$ does not have the form of eq. 13 and 14.

Therefore $\exists\delta>0$, such that $\forall\rho$, $\exists\rho^{\prime}>\rho$: $\mathbf{v}\left(\rho^{\prime}\right)\notin\mathcal{B}_{\delta}\left(\mathcal{W}\right)$. The norm of the solution in eq. 25

is equal to the norm of the solution with margin $\gamma^{*}\left(\rho^{\prime}\right)$

and so, dividing by $\left[\gamma\left(\rho,\boldsymbol{\theta}\left(\rho\right)\right)\right]^{\frac{2}{\alpha_{k}}}$ we obtain

However, since $\mathbf{v}\left(\rho^{\prime}\right)\notin\mathcal{B}_{\delta}\left(\mathcal{W}\right)$, $\exists\epsilon^{\prime}>0$ such that for all $\rho^{\prime}$: $\left\|\mathbf{v}_{1}\left(\rho^{\prime}\right)\right\|^{2}>\left\|\boldsymbol{w}_{1}^{*}\right\|^{2}+\epsilon^{\prime}$ plugging this into eq. 26 we obtain

which is a contradiction. Therefore, $\mathbf{v}\left(\rho^{\prime}\right)$ converges into $\mathcal{W}$, and eq. 25 can be written in the form of eqs. 12 and 13. ∎

Appendix D Examples Section: Auxiliary Results

We denote $g\left(\boldsymbol{\theta}\right)=\min\limits_{n}f_{n}\left(\boldsymbol{\theta}\right).$ This is a continues function since $\forall n:$ $f_{n}$ is continues. In addition, we define for some $\rho_{0}>0$

where $\boldsymbol{\theta}_{m}\in\Theta_{m}$. Using this definition we also define $d\left(\boldsymbol{\theta}\right)$ as the Euclidean distance between $\boldsymbol{\theta}$ and any point in the set $\Theta_{m}$ and $d\left(r\right)$ as the maximal distance for $\boldsymbol{\theta}\in A_{r}$:

Note that the maximum in the last equation is obtained as the maximum of a continues function over a compact set. We want to show that $\Theta_{c}\left(\rho\right)$ converges to $\Theta_{m}$. From definition, this implies that $\forall\epsilon>0$ $\exists\rho_{0}$ such that $\forall\rho>\rho_{0}$ $\Theta_{c}\left(\rho\right)\subset\mathcal{B}_{\epsilon}\left(\Theta_{m}\right)$, i.e., $\forall\boldsymbol{\theta}_{c}(\rho)\in\Theta_{c}\left(\rho\right)$: $\exists\boldsymbol{\theta}^{\prime}\in\Theta_{m}:\left\|\boldsymbol{\theta}_{c}(\rho)-\boldsymbol{\theta}^{\prime}\right\|<\epsilon$. Assume in contradiction that this is not the case. This means that $\exists\epsilon>0$ such that $\forall\rho_{0}:\exists\rho>\rho_{0}$ and $\exists\boldsymbol{\theta}_{c}(\rho)\in\Theta_{c}\left(\rho\right)$ so that $\forall\boldsymbol{\theta}^{\prime}\in\Theta_{m}:\left\|\boldsymbol{\theta}_{c}(\rho)-\boldsymbol{\theta}^{\prime}\right\|>\epsilon$. This implies that $\lim_{r\to 0}d\left(r\right)\neq 0$ . Using the limit definition we get that $\exists\epsilon>0$ so that $\forall\delta>0,$ $\exists\left|r\right|<\delta$ and $d\left(r\right)>\epsilon$. Using our notations this implies that

Next, we build a subsequence $\left\{\boldsymbol{\theta}_{i}\right\}_{i=1}^{\infty}$ by taking a decreasing series of $\left\{\delta_{i}\right\}_{i=1}^{\infty}$ and their associated $\boldsymbol{\theta}^{\prime}$ from the last equation. Since $\boldsymbol{\theta}_{i}^{\prime}$ are bounded, there exist a convergent subsequence $\left\{\widetilde{\boldsymbol{\theta}}_{i}\right\}_{i=1}^{\infty}.$ For this subsequence, we obtain, using $g$ continuity

which implies that $\exists\boldsymbol{\theta}_{m}^{*}\in\Theta_{m}$ so that $\lim_{i\to\infty}\widetilde{\boldsymbol{\theta}}_{i}=\boldsymbol{\theta}_{m}^{*}$ which contradicts the fact that $d\left(\widetilde{\boldsymbol{\theta}}_{i}\right)>\epsilon>0$. ∎

Second, we need to show that $\left(\log\left(\widetilde{\gamma}^{*}\right)-\log\left(\widetilde{\gamma}\left(\boldsymbol{\theta}_{c}\left(\rho\right)\right)\right)\right)\to 0$ implies that $\Theta_{c}\left(\rho\right)$ converges to $\Theta_{m}\left(\rho\right)$.

We denote $g\left(\boldsymbol{\theta}\right)=\log\left(\min\limits_{n}\boldsymbol{\theta}^{\top}\mathbf{x}_{n}\right)$. The rest of the proof is identical to the proof for the homogeneous case in Appendix D.1.

Appendix E Proofs in Section 4

Define $S=\{n:f_{n}(\bar{}\boldsymbol{w}{()})=\gamma^{*}(1)\}$, where $\gamma^{*}(1)$ is the optimal margin attainable by a unit norm $\boldsymbol{\theta}$.

For $n\in S$ , the second term is asymptotically negligible as a function of $t$,

Let $\bar{}\boldsymbol{w}{()}_{s}(t):=g(t)\bar{}\boldsymbol{w}{()}+sg(t)\boldsymbol{\delta}(t)$. We bound the integrand in the second term.

where $B=\max_{\|\boldsymbol{\theta}\|\leq 1}\|\nabla^{2}f_{n}(\boldsymbol{\theta})\|<\infty$ since $\nabla^{2}f_{n}$ is a continuous function maximized over a compact set.

$\nabla f_{n}(g(t)\bar{}\boldsymbol{w}{()})=g(t)^{\alpha-1}\nabla f_{n}(\bar{}\boldsymbol{w}{()})$, and for $n\in S$, $\|\nabla f_{n}(\bar{}\boldsymbol{w}{()})\|>0$ via constraint qualification (Assumption 5). Thus for $n\in S$ and using $\|\boldsymbol{\delta}(t)\|=o(1)$,

Let $S=\{n:f_{n}(\bar{}\boldsymbol{w}{()})=\gamma^{*}(1)\}$. Under the conditions of Theorem 2, $a_{n}=0$ for $n\notin S$.

Consider $n\notin S$ so $f_{n}(\bar{}\boldsymbol{w}{()})=\gamma_{n}>\gamma^{*}(1)$.

$\bar{}\boldsymbol{w}{()}$ satifies the first-order optimality of margin problem.

where $\Delta_{n}(t)=\int_{s=0}^{s=1}\nabla^{2}f_{n}(g(t)\bar{}\boldsymbol{w}{()}+sg(t)\delta(t))g(t)\delta(t)ds$. By multiplying out and using $a_{n}=0$ for $n\notin S$ (Lemma 7),

Via constraint qualification (Assumption 5), $I=\Omega(g(t)^{\alpha-1}h(t))$ and the second part of Lemma 6, $II=o(I)$.

Since $\epsilon_{tn}=o(1)$, then $III=o(I)$. By the first part of Lemma 6, $IV=O(Bg(t)^{\alpha-1}\|\delta(t)\|)=o(I)$ since $\|\delta(t)\|\to 0$.

Since $I$ is the largest term then after normalization,

Since $\lim\limits_{t\to\infty}\frac{\boldsymbol{\theta}(t)}{\|\boldsymbol{\theta}(t)\|}=\lim\limits_{t\to\infty}\frac{\overset{\bullet}{\boldsymbol{\theta}}(t)}{\lVert\overset{\bullet}{\boldsymbol{\theta}}(t)\rVert}$ (Gunasekar et al., 2018b), then

Thus $\bar{}\boldsymbol{w}{()}$ satisfies the first-order optimality conditions of 18. ∎

E.2 Proof of Theorem 3

The proof is similar to the proof of Theorem 2. From Equations 29 and 28 in the proof of Theorem 2, we see that

E.3 Proof of Theorem 4

The proof is adapted from the ideas outlined in Theorem $7$ in (Rosset et al., 2004a).

For any $\boldsymbol{\theta}_{\infty}\in\Theta_{c}^{\infty}$, from definition, let $\{\rho_{i},\boldsymbol{\theta}_{\rho_{i}}\}_{i=1}^{\infty}$ denote a sequence such that $\rho_{i}\to\infty$, $\boldsymbol{\theta}_{\rho_{i}}\in\Theta_{c}(\rho_{i})$ and $\boldsymbol{\theta}_{\rho_{i}}\to\boldsymbol{\theta}_{\infty}$. Thus, for any $\epsilon>0$, $\exists i_{0}$ such that $\forall i>i_{0}$, $\lVert\boldsymbol{\theta}_{\infty}-\boldsymbol{\theta}_{\rho_{i}}\rVert\leq\epsilon$.

We need to show that $\boldsymbol{\theta}_{\infty}\in\Theta_{m,N}^{*}$. We will prove this theorem by induction, where we show that for all $k=0,1,2,\ldots,N$, $\boldsymbol{\theta}_{\infty}\in\Theta_{m,k}^{*}$.

Assume that for some $k$, $\boldsymbol{\theta}_{\infty}\in\Theta_{m,k}^{*}$. We need to show the inductive argument that $\boldsymbol{\theta}_{\infty}\in\Theta_{m,k+1}^{*}$.

where in the minimization on the right, ties are broken arbitrarily.

Using the above notation, $\Theta_{m,k+1}^{*}$ is given by

If possible, let $\boldsymbol{\theta}_{\infty}\notin\Theta_{m,k+1}^{*}$ and let $\boldsymbol{\theta}^{\prime}\in\Theta_{m,k+1}^{*}$. Using the inductive assumption and the definition of $\Theta_{m,k+1}^{*}$, we have we have $\boldsymbol{\theta}_{\infty},\boldsymbol{\theta}^{\prime}\in\Theta_{m,k}^{*}$. From the definition of $\Theta_{m,k+1}^{*}$, we can deduce the following,

Recall that $\mathcal{L}(\boldsymbol{\theta})=\sum_{n}\exp(-f_{n}(\boldsymbol{\theta}))$, where $f_{n}$ are $\alpha$-positive homogeneous

Upper bound on $\mathcal{L}(\rho\boldsymbol{\theta}^{\prime})$.

Lower bound on $\mathcal{L}(\rho\boldsymbol{\theta}_{\infty})$.

Lower bound on $\mathcal{L}(\rho_{i}\boldsymbol{\theta}_{\rho_{i}})$ for large enough $i$. Recall that the sequence of $\boldsymbol{\theta}_{\rho_{i}}\to\boldsymbol{\theta}_{\infty}$ satisfies $\boldsymbol{\theta}_{\rho_{i}}\in\Theta_{c}(\rho_{i})$. From the definition of constrained path, we have for all $i$, $\mathcal{L}(\rho_{i}\boldsymbol{\theta}_{\rho_{i}})\leq\mathcal{L}(\rho_{i}\boldsymbol{\theta}_{\infty})$.

Since $\boldsymbol{\theta}_{\rho_{i}}\to\boldsymbol{\theta}_{\infty}$, using continuity of min and max of finite number of continuous functions, we have

Now consider the two cases for $i\geq i_{0}(\epsilon)$:

where $(a)$ follows from using eq. 34 to get $f_{n_{k+1}^{*}(\boldsymbol{\theta}_{\rho_{i}})}(\boldsymbol{\theta}_{\rho_{i}})\leq f_{n_{k+1}^{*}(\boldsymbol{\theta}_{\infty})}(\boldsymbol{\theta}_{\infty})-\epsilon=\gamma-\epsilon$.

Since, $\rho_{i}\to\infty$ and $\epsilon_{i}>0$, for large enough $i$, we have $\exp(\rho_{i}^{\alpha}\epsilon_{i})-N>0$ Thus, for large enough $i$, from the above two equations, we will have $\mathcal{L}(\rho_{i}\boldsymbol{\theta}_{\rho_{i}})-\mathcal{L}(\rho_{i}\boldsymbol{\theta}_{\infty})>0$, which is a contradiction, since $\boldsymbol{\theta}_{\rho_{i}}\in\Theta_{c}(\rho_{i})$. Thus, this case cannot happen for large enough $i$

Remaining steps in the proof. For any $\epsilon>0$, from eqs. 32, 33, and Lemma 8 in Step $3$, we have the following for large enough $i$’s

where $(a)$ follows since $m_{2}<m_{1}$ and above equation holds for arbitrarily small $\epsilon$.

This completes the proof of the theorem. ∎

Appendix F The Regularization Path

The regularization path is given by the following set, $\forall c>0$:

$\forall c>0:\ \Theta_{r}\left(c\right)$ is not empty, i.e., $\forall c:\ \min_{\boldsymbol{\theta}}\;\mathcal{L}\left(\boldsymbol{\theta}\right)+\frac{1}{c}\left\|\boldsymbol{\theta}\right\|^{2}$ exists.

Note that $\forall c>0:\ \mathcal{L}\left(\boldsymbol{\theta}\right)+\frac{1}{c}\left\|\boldsymbol{\theta}\right\|^{2}$ is coercive since $\mathcal{L}\left(\boldsymbol{\theta}\right)$ is lower bounded. Thus, the minimum of $\mathcal{L}\left(\boldsymbol{\theta}\right)+\frac{1}{c}\left\|\boldsymbol{\theta}\right\|^{2}$ is attained as the minimum of a continuous coercive function over a nonempty closed set. ∎

If Assumption 1 is satisfied, then as $c\to\infty$ we have that $\lVert\boldsymbol{\theta}_{r}\left(c\right)\rVert\to\infty$ where $\boldsymbol{\theta}_{r}\left(c\right)\in\Theta_{r}\left(c\right)$. We state this result in the following lemma.

If $\exists\rho_{0}$ such that $\mathcal{L}^{*}\left(\rho\right)$ is strictly monotonically decreasing for any $\rho\geq\rho_{0}$, and $\boldsymbol{\theta}_{r}\left(c\right)\in\arg\min_{\boldsymbol{\theta}}\;\mathcal{L}\left(\boldsymbol{\theta}\right)+\frac{1}{c}\left\|\boldsymbol{\theta}\right\|^{2}$ then as $c\to\infty$, we have $\lVert\boldsymbol{\theta}_{r}\left(c\right)\rVert\to\infty$.

Note that $\mathcal{L}^{*}\left(M+\epsilon\right)-\mathcal{L}^{*}\left(M\right)<0$ since we assume that $\mathcal{L}^{*}\left(\rho\right)$ is strictly monotonically decreasing for any $\rho\geq\rho_{0}$. For sufficiently large $c$ we get that

which contradicts our assumption that $\boldsymbol{\theta}_{r}\left(c\right)$ is an optimal solution. ∎

F.2 Connections between regularization and constrained paths

For convex loss function, the regularization and constrained paths are known to be equivalent. For general loss function, we state the following basic result.

$\forall c>0,\,\forall\theta_{r}\in\Theta_{r}\left(c\right):\,\exists\rho$ so that $\theta_{r}\in\Theta_{c}(\rho)$, and, If $\exists\rho_{0}$ such that $\mathcal{L}^{*}\left(\rho\right)$ is strictly monotonically decreasing for any $\rho\geq\rho_{0}$ then $\forall\theta_{r}\in\Theta_{r}\left(c\right)$: $\Theta_{c}\left(\left\|\theta_{r}\right\|\right)\subset\Theta_{r}\left(c\right)$.

To prove Lemma 11 we combine the results from the following two lemmas. ∎

$\forall c>0,\,\forall\theta_{r}\in\Theta_{r}\left(c\right):\,\exists\rho$ so that $\theta_{r}\in\Theta_{c}(\rho)$.

For some $c>0$, let $\boldsymbol{\theta}_{r}^{*}\left(c\right)\in\Theta_{r}(c)$. From $\Theta_{r}(c)$ definition (eq. 36) $\left\|\boldsymbol{\theta}_{r}^{*}\left(c\right)\right\|=1$ and thus $\boldsymbol{\theta}_{r}^{*}\left(c\right)$ is a feasible solution of eq. 5. Additionally, $\exists\alpha>0$ so that $\forall\boldsymbol{\theta}^{(1)}$:

For $\rho=\alpha$ we have that $\boldsymbol{\theta}_{r}^{*}\left(c\right)\in\Theta_{c}(\rho)$ since $\forall\boldsymbol{\theta}^{(1)}$:

and particularly, $\forall\boldsymbol{\theta}^{(2)}$ such that $\left\|\boldsymbol{\theta}^{(2)}\right\|\leq 1$:

\forall c>0\text{,\,\forall\boldsymbol{\theta}_{r}\in\Theta_{r}\left(c\right)$:\,$\Theta_{c}\left(\left\|\boldsymbol{\theta}_{r}\right\|\right)\subset\Theta_{r}\left(c\right)}.

For some $c>0$, let $\boldsymbol{\theta}_{r}^{*}\left(c\right)\in\arg\min_{\boldsymbol{\theta}}\;\mathcal{L}\left(\boldsymbol{\theta}\right)+\frac{1}{c}\left\|\boldsymbol{\theta}\right\|^{2}$. For $\rho=\left\|\boldsymbol{\theta}_{r}^{*}\left(c\right)\right\|$ and $\boldsymbol{\theta}_{c}^{*}\in\arg\min_{\boldsymbol{\theta}}\mathcal{L}\left(\rho\frac{\boldsymbol{\theta}}{\left\|\boldsymbol{\theta}\right\|}\right)$ we have that $\forall\boldsymbol{\theta}$

Thus, $\forall\boldsymbol{\theta}^{(2)}$ so that $\left\|\boldsymbol{\theta}^{(2)}\right\|=\rho=\left\|\boldsymbol{\theta}_{r}^{*}\left(c\right)\right\|$ we have that