<figure><img src="image_1.png" /></figure>

HAL
open science

# Diagonal Linear Networks and the Lasso Regularization Path

Raphaël Berthier

<figure><img src="image_2.png" /></figure>

To cite this version:

Raphaël Berthier. Diagonal Linear Networks and the Lasso Regularization Path. 2025. hal-05282524

HAL Id: hal-05282524

https://hal.science/hal-05282524v1

Preprint submitted on 25 Sep 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Diagonal Linear Networks and the Lasso Regularization Path

Raphaël Berthier*

September 22, 2025

## Abstract

Diagonal linear networks are neural networks with linear activation and diagonal weight matrices. Their theoretical interest is that their implicit regularization can be rigorously analyzed: from a small initialization, the training of diagonal linear networks converges to the linear predictor with minimal 1-norm among minimizers of the training loss. In this paper, we deepen this analysis showing that the full training trajectory of diagonal linear networks is closely related to the lasso regularization path. In this connection, the training time plays the role of an inverse regularization parameter. Both rigorous results and simulations are provided to illustrate this conclusion. Under a monotonicity assumption on the lasso regularization path, the connection is exact while in the general case, we show an approximate connection.

<footnote>* Sorbonne Université, Inria, Centre Inria de Sorbonne Université, Paris, France</footnote>
# Contents

<table><tr><td>1</td><td>Introduction</td><td>3</td></tr><tr><td>2</td><td>The u ◦ v case — statement of the results</td><td>5</td></tr><tr><td>2.1</td><td>Connection to the lasso under a monotonicity assumption</td><td>5</td></tr><tr><td>2.2</td><td>Simulations</td><td>6</td></tr><tr><td>2.3</td><td>Approximate connection to the lasso in the general case</td><td>6</td></tr><tr><td>2.4</td><td>Related work and final remarks</td><td>8</td></tr><tr><td>3</td><td>The u ◦ u case — statement of the results</td><td>9</td></tr><tr><td>3.1</td><td>Connection to the positive lasso under a monotonicity assumption</td><td>10</td></tr><tr><td>3.2</td><td>Approximate connection to the positive lasso in the general case</td><td>10</td></tr><tr><td>4</td><td>The u ◦ u case — proofs of the results</td><td>11</td></tr><tr><td>4.1</td><td>Mirror flow interpretation</td><td>11</td></tr><tr><td>4.2</td><td>Uniform bound on the trajectories</td><td>12</td></tr><tr><td>4.3</td><td>The positive lasso and linear complementarity problems</td><td>16</td></tr><tr><td>4.4</td><td>The positive lasso regularization path and parametric linear complementarity problems</td><td>17</td></tr><tr><td>4.5</td><td>Proof of Theorem 3.2.</td><td>19</td></tr><tr><td>4.6</td><td>Proof of Theorem 3.1.</td><td>22</td></tr><tr><td>5</td><td>The u ◦ v case — proof of the results</td><td>22</td></tr><tr><td>5.1</td><td>Reductions</td><td>23</td></tr><tr><td>5.1.1</td><td>Reduction of the lasso to the positive lasso</td><td>23</td></tr><tr><td>5.1.2</td><td>Reduction of dynamics in the u ◦ v case to the u ◦ u case.</td><td>24</td></tr><tr><td>5.2</td><td>Proofs</td><td>25</td></tr><tr><td>5.2.1</td><td>Proof of Theorem 2.1</td><td>25</td></tr><tr><td>5.2.2</td><td>Proof of Theorem 2.2</td><td>26</td></tr><tr><td></td><td>References</td><td>27</td></tr></table>
# 1 Introduction

**Context.** The composition of layers enables a neural network to learn a modular representation of the data. However, the reasons why learning the components of this representation is computationally amenable through gradient descent methods and why it leads to excellent generalization properties are still not fully understood [3].

In order to address this questions, machine learning theory has studied the gradient flow training of linear networks—where the activation is linear— and diagonal linear networks (DLNs)—where, in addition, weight matrices are diagonal. These studies have pointed out that a certain implicit regularization phenomenon appears when training neural networks: the gradient descent minimizes certain regularization penalties, although not explicitly present in the loss function [31]. This phenomenon has been shown to be beneficial for the generalization properties of the trained networks, and thus suggested to be a key ingredient in the success of neural networks. See, e.g., [16, 21, 9, 20] for contributions to the implicit regularization of neural networks and [32, 34, 33, 17, 20, 2, 27, 28, 25, 10, 4, 26] for more contributions specifically on DLNs.

We now briefly recall the form of this phenomenon in the case of DLNs. Consider the minimization of quadratic function:

$$ \ell(x) = \frac{1}{2} \langle x, Mx \rangle - \langle r, x \rangle, \quad x \in \mathbb{R}^d. $$

We assume that this function is convex, i.e. that $M$ is positive semidefinite, and that it is lower-bounded, i.e. that $r \in \text{Span } M$. The minimization of such functions arises, e.g., when solving linear least-squares problems.

A DLN (with two layers) consists in parametrizing $x = u \circ v$, where $\circ$ denotes the component-wise product of the two vectors $u, v \in \mathbb{R}^d$, and training the parameters $u$ and $v$ with the gradient flow on $\ell(x) = \ell(u \circ v)$. This induces a trajectory $u(t), v(t)$ as well as an effective linear parameter $x(t) = u(t) \circ v(t)$. When initialized from a suitable infinitesimal initialization $x(0)$, the training of DLNs is shown to converge to the minimizer of $\ell$ with minimal 1-norm [33]. As a consequence, the minimizer selected by the training of a DLN benefits from a sparsifying effect, which is beneficial for the generalization properties of the trained network.

**Contributions.** For a regularization parameter $\lambda \ge 0$, we define the lasso objective as

$$ \text{Lasso}(x, \lambda) = \ell(x) + \lambda \|x\|_1. $$

In other words, the result above states that DLNs converge to a minimum of the lasso objective with infinitesimal regularization parameter $\lambda = 0^+$.

In this work, we show that there is in fact a deeper connection between the training trajectory of DLNs and the lasso regularization path. The connection holds in the same infinitesimal initialization limit. When $x(0)$ is of magnitude
$\epsilon \ll 1$, the time $t$ is jointly rescaled as $t(s, \epsilon) = \frac{1}{2}(\log \frac{1}{\epsilon})s$. Consider the average of the trajectory of $x$:

$$ \bar{x}(t) = \frac{1}{t} \int_{0}^{t} x(u) du. $$

We then have the following informal result:

As $\epsilon \to 0$, in this joint regime, for all $s > 0$, $\bar{x}(t(s, \epsilon))$ (approximately) minimizes the lasso objective $\text{Lasso}(\cdot, \frac{1}{s})$.

In the informal result above, the parenthesized word “approximately” refers to a more technical discussion. Under a monotonicity assumption on the lasso regularization path, we show that $\text{Lasso}(\bar{x}(t(s, \epsilon)), \frac{1}{s})$ converges to the minimum of $\text{Lasso}(\cdot, \frac{1}{s})$ as $\epsilon \to 0$. However, when the lasso regularization path is not monotone, we only show that $\bar{x}(t(s, \epsilon))$ is an approximate minimizer of $\text{Lasso}(\cdot, \frac{1}{s})$, even in the limit $\epsilon \to 0$, where the suboptimality gap is controlled by the deviation from the monotonicity assumption. This distinction is also apparent in simulations.

This result shows that early stopping the training of DLNs can offer a tradeoff between sparsity and data fitting. An earlier stopping time leads to a sparser linear model. This deepens the connection between DLNs and sparse regression.

Our results also cover the case $x = u \circ u$, that is less motivated by the theoretical study of neural networks, but that is algebraically more elegant. As a consequence, we provide the proofs in the $u \circ u$ case first, and then deduce the proofs in the $u \circ v$ by a reduction to the $u \circ u$ case. This systematic reduction strategy might be of independent interest for the study of DLNs.

**Outline.** Sec. 2 is the one of interest for most readers. It contains the results in the case $x = u \circ v$ and their discussions. Sec. 2.1 provides the exact connection under the monotonicity assumption on the lasso regularization path, Sec. 2.2 presents simulations that illustrate the results, and Sec. 2.3 covers the general case, beyond the monotonicity assumption. Sec. 2.4 concludes this section by discussing in more detail the related work and a speculative conclusion for the theory of neural networks.

Sec. 3 contains the parallel results in the case $x = u \circ u$. Sec. 4 contains the proofs of the results in the $u \circ u$ case. This section contains the bulk of the technical effort of this paper, as the proofs in the $u \circ v$ case, provided in Sec. 5, are obtained by a systematic reduction to the $u \circ u$ case.

**Notations.** We denote $\langle \cdot, \cdot \rangle$ the canonical inner product on $\mathbb{R}^d$ and $\| \cdot \|$ the associated norm. We note $\| \cdot \|_1$ the 1-norm on vectors: $\|x\|_1 = \sum_{i=1}^d |x_i|$.

We use the notation $x \ge 0$ to denote that $x$ has all coordinates nonnegative.

If $x$ is a real number, we denote $x_+ = \max(x, 0)$ its positive part and $x_- = \max(-x, 0)$ its negative part.

When $\varphi$ is a univariate function and $x \in \mathbb{R}^d$, we denote $\varphi(x) = (\varphi(x_1), \dots, \varphi(x_d))$ the component-wise application of $\varphi$ to $x$. This notation is used, for instance,
for $\varphi = \log$, for $\varphi(x) = x^2$, for $\varphi(x) = x_+$ or for $\varphi(x) = x_-$. We thus denote $x^2 = x \circ x$.

We sometimes write explicitly the dependence of the constants on some parameters, for instance $C_i = C_i(M, r, \alpha)$. Without any index, the notation $C(\dots)$ indicates a constant that depends on the parameters between the parentheses. This constant can change from one occurrence to the next.

We denote $\mathbb{1} = (1, \dots, 1)$ the vector of ones, whose dimension is implicit from the context.

When $I$ is a subset of $\{1, \dots, d\}$, we denote $A_I$ the submatrix of $A$ where the columns whose index are in $I$ are selected, and $A_{I,I}$ the submatrix of $A$ where both the rows and the columns whose index are in $I$ are selected.

## 2 The $u \circ v$ case — statement of the results

**Setting.** Diagonal linear networks consist in parametrizing $x$ as a product of two vectors $x = u \circ v$. We study the training of such networks with the gradient flow, i.e.,

$$ \frac{du}{dt} = -\nabla_u (\ell(u \circ v)), \qquad \frac{dv}{dt} = -\nabla_v (\ell(u \circ v)). \qquad (2.1) $$

We study this flow in the limit of small initialization. More precisely, we denote $u^\epsilon(t)$ and $v^\epsilon(t)$ the solutions of Eqs. (2.1) with initial conditions $u^\epsilon(0) = \sqrt{\epsilon}\beta$ and $v^\epsilon(0) = \sqrt{\epsilon}\gamma$, where $\beta$ and $\gamma$ are fixed vectors in $\mathbb{R}^d$ and $\epsilon$ is a small parameter. We denote $x^\epsilon(t) = u^\epsilon(t) \circ v^\epsilon(t)$. The scalings in $\epsilon$ are chosen so that $x^\epsilon(0)$ is of order $\epsilon$. For non-degeneracy reasons, we assume that for all $i \in \{1, \dots, d\}$, $\beta_i \neq \pm \gamma_i$.

We also define $\bar{x}^\epsilon(t) = \frac{1}{t} \int_0^t x^\epsilon(u) du$ the average of the trajectory of $x^\epsilon$. The goal of our analyses is to connect the average of the trajectory to the lasso optimization problem

$$ \min_{z \in \mathbb{R}^d} \text{Lasso}(z, \lambda). \qquad (2.2) $$

We denote $\text{Lasso}_*(\lambda) = \min_{z \in \mathbb{R}^d} \text{Lasso}(z, \lambda)$ the minimum of this optimization problem.

Define a rescaled time

$$ s = \frac{2}{\log \frac{1}{\epsilon}} t. \qquad (2.3) $$

Below, we frequently abuse notations and use the same notation for rescaled versions of functions of time. For instance, $\bar{x}^\epsilon(s)$ denotes $\bar{x}^\epsilon(t)$ where $t = \frac{\log \frac{1}{\epsilon}}{2}s$.

### 2.1 Connection to the lasso under a monotonicity assumption

**Theorem 2.1.** For all $s > 0$, let $x(s)$ denote a minimizer of the lasso

$$ \min_{x \in \mathbb{R}^d} \text{Lasso} \left( x, \frac{1}{s} \right). $$
Assume that $s > 0 \mapsto sx(s)$ is coordinate-wise monotone. Then

$$ \text{Lasso} \left( \bar{x}^{\epsilon}(s), \frac{1}{s} \right) \xrightarrow{\epsilon \to 0} \text{Lasso}_{*} \left( \frac{1}{s} \right). $$

As $\lim_{s \to 0^+} x(s) = 0$, a sufficient condition that ensures $s \mapsto sx(s)$ to be monotone, is to have the lasso regularization path $s \mapsto x(s)$ itself monotone. Under the latter condition, the lasso regularization path has already been shown to be equivalent to computationally cheaper algorithms such as the least angle regression algorithm [15], incremental forward stagewise regression [18] or boosting [29]. Moreover, it is also argued that even when $s \mapsto x(s)$ is not monotone, the solutions of these different algorithms might not be very far, see for example Figure 1 in [15]. A sufficient condition for the lasso regularization path to be monotone, derived in the latter article, is to have $S(M_{II})^{-1}S\mathbf{1} \ge 0$ for all subsets $I \subset \{1, \dots, d\}$ and for all diagonal sign matrices $S \in \mathbb{R}^{I \times I}$ (see also [18, Sec. 6] for a succinct statement).

The monotonicity of $s \mapsto sx(s)$ specifically has been studied, to the best of our knowledge, only in the case of the positive lasso, which corresponds to the parametrization $x = u^2$, see Sec. 3.1.

## 2.2 Simulations

In order to illustrate the results of this paper and discuss the importance of the monotonicity assumption, we provide some simulations. The code is available on github [5].

We randomly generate problem instances in dimension $d = 4$ as follows. We consider the quadratic function $\ell(x) = \frac{1}{2}\|Xx - y\|^2$, where $n = 3$, $X \in \mathbb{R}^{n \times d}$ and $y \in \mathbb{R}^n$ are independent and have i.i.d. standard normal entries.

In this case, the lasso regularization path is almost surely unique [30]. We observe empirically that $s \mapsto sx(s)$ is monotone with probability 0.76, over 1000 random instances. Thus Theorem 2.1 applies in a majority of cases.

In all simulations, we take $\epsilon = 10^{-5}$, $\beta = 1$ and $\gamma = 0$.

Figure 1 compares the average trajectory $\bar{x}^{\epsilon}(s)$ of DLNs with the lasso regularization path $x(s)$ on problems generated randomly as above. We observe that the trajectory $\bar{x}^{\epsilon}(s)$ is qualitatively similar to $x(s)$ in all instances, and that the suboptimality gap $(\text{Lasso}(\bar{x}^{\epsilon}(s), \frac{1}{s}) - \text{Lasso}_{*}(\frac{1}{s})) / \text{Lasso}_{*}(\frac{1}{s})$ remains relatively small (below 0.04 on the provided instances). However, the comparison is much tighter in the monotone case than in the nonmonotone case; in particular, the suboptimality gap is an order of magnitude smaller for monotone instances.

## 2.3 Approximate connection to the lasso in the general case

We now provide an approximate optimality results in the nonmonotone case that comforts the simulations.
<figure><img src="image_4.png" /><figcaption>Figure 1: Comparison between the average trajectory $\bar{x}^\epsilon(s)$ of DLNs and the lasso regularization path $x(s)$. In the subfigure (a), problems instances are generated randomly conditionally on the monotonicity of $s \mapsto sx(s)$. Conversely, in the subfigure (b), problems instances are generated randomly conditionally on the non-monotonicity of $s \mapsto sx(s)$. We provide two instances of each case, one in each column. In each instance, we plot the coordinates $\bar{x}_i^\epsilon(s)$ along with $x_i(s)$, and the suboptimality gap $(\text{Lasso}(\bar{x}^\epsilon(s), \frac{1}{s}) - \text{Lasso}_*(1/s)) / \text{Lasso}_*(1/s)$. Simulation details are provided in Sec. 2.2.</figcaption></figure>
**Theorem 2.2.** For all $s > 0$, let $x(s)$ denote a minimizer of the lasso

$$ \min_{x \in \mathbb{R}^d} \text{Lasso} \left( x, \frac{1}{s} \right). $$

Assume that $s > 0 \mapsto x(s)$ is absolutely continuous on compact subsets of $(0, +\infty)$. Let

$$ z^{\downarrow}(s) = \sum_{i=1}^{d} \int_{0}^{s} \left[ \left( \frac{d}{du}(ux_{i}(u)_{+}) \right)_{-} + \left( \frac{d}{du}(ux_{i}(u)_{-}) \right)_{-} \right] du. \quad (2.4) $$

Heuristically, $z^{\downarrow}(s)$ quantifies the deviation from monotonicity of $z(s) = sx(s)$. Then, there exists a constant $C = C(d, M, r, \alpha) > 0$ such that

$$ \limsup_{\epsilon \to 0} \text{Lasso} \left( \bar{x}^{\epsilon}(s), \frac{1}{s} \right) \le \text{Lasso}_{*} \left( \frac{1}{s} \right) + C \left[ \frac{(1+s)^{1/2}}{s} z^{\downarrow}(s)^{1/2} + \frac{1+s}{s^2} z^{\downarrow}(s) \right]. $$

This theorem predicts that the suboptimality gap spikes when the lasso regularization path is not monotone (when $z^{\downarrow}(s)$ is large) and then decays afterwards (as $s$ increases). This is consistent with the observations in Figure 1.

## 2.4 Related work and final remarks

**Additional related work.** In contrast with many works on diagonal linear networks, this paper does not assume any statistical model for the data that generated the loss $\ell$, and focuses only on the optimization analysis. In particular, our results could cover noisy or noiseless data, and general design matrices. This is in contrast with many works that require a restricted isometry property, or a coherence assumption on the design matrix [32, 34, 20].

Under a statistical linear model with additive noise, early stopping is used in DLNs to achieve optimal rates [32, 34, 20]. Similarly, in the same setting, the regularization parameter of the lasso is usually chosen proportional to the magnitude of the additive noise [19, Chapter 11]. Our work sheds light on this correspondence: a non-zero regularization parameter corresponds to a finite stopping time.

More specifically, some earlier works have noted the similarity between the trajectory of DLNs and the lasso regularization path [32, 4, 26]. Vaskevicius et al. noted that $t/\log \frac{1}{\epsilon}$ plays the role of an inverse regularization parameter in their statistical guarantee [32] (see discussion below their Thm. 1). However, they note that “the gradient descent optimization path [of DLNs] [...] exhibits qualitative and quantitative differences from the lasso regularization path.” Our contribution argues that the qualitative differences are only due to the fact that the lasso regularization path corresponds to the *averaged* gradient descent optimization path, with mild differences discussed in this paper (see also Fig. 1). Finally, the author proved Thm. 3.1, the equivalent of Thm. 2.1 in the case $x = u \circ u$, but only when $M$ is a matrix with non-positive off-diagonal entries [4]. (In this case, the monotonicity assumption is guaranteed.)
**Final remarks.** This works strengthens our understanding of the implicit regularization of neural networks. Not only the asymptotic convergence point is implicitly regularized, but also the full trajectory of the neural network. The earlier the neural networks is stopped, the more regularized the solution is.

Our proof technique provides a way to analyze the implicit regularization in a dynamical way, that is, as time evolves. We hope that this new perspective will help to tackle a major difficulty of the implicit regularization line of research: we do not know how to describe the implicit regularization of more complex neural networks, beyond DLNs. For instance, the implicit regularization of matrix factorization problems can not be described by the nuclear norm, as one would expect from a natural generalization of the results on DLNs [1, 22]. We hope that this discrepancy can be understood through a dynamical study of the deviation between matrix factorization dynamics and nuclear norm minimizers.

## 3 The $u \circ u$ case — statement of the results

**Setting.** In this section, we state an alternative version of the results of this paper, in the case where the regressor $x$ is parametrized as $x = u^2 = u \circ u$ instead of $x = u \circ v$. This study is less directly related to simplified models of neural networks, and has the disadvantage of constraining the sign of $x$, but it enables an elegant theory. Moreover, as we discuss in Section 5, the case $x = u \circ v$ can be reduced to the case $x = u^2$, thus in fact the bulk of the theory is contained in this case, and the case $x = u \circ v$ follows as corollaries.

In the case $x = u^2$, the gradient flow dynamics

$$ \frac{du}{dt} = -\nabla_u (\ell(u^2)) \qquad (3.1) $$

can be written a closed-form differential equation in $x = u^2$:

$$ \frac{dx}{dt} = -4x \circ \nabla \ell(x). \qquad (3.2) $$

In this section, we denote $u^\epsilon(t)$ the solution of Eq. (3.1) with initial condition $u^\epsilon(0) = \sqrt{\epsilon}\alpha$ where $\alpha$ is a fixed vector in $\mathbb{R}^d$ and $\epsilon$ is a small parameter. We denote $x^\epsilon(t) = u^\epsilon(t)^2$. We assume that all coordinates $\alpha_i$ of $\alpha$ are nonzero: if $\alpha_i = 0$, by Eq. (3.2), the coordinate of $x_i^\epsilon(t)$ remains zero for all $t \ge 0$, thus this case is degenerate.

Again, we define $\bar{x}^\epsilon(t) = \frac{1}{t} \int_0^t x^\epsilon(u) du$ the average of the trajectory of $x$. The goal of our analyses is to connect the average of the trajectory to the positive lasso optimization problem

$$ \min_{x \ge 0} \mathrm{Lasso}(x, \lambda). \qquad (3.3) $$

We denote PosLasso$_*(\lambda) = \min_{x \ge 0} \mathrm{Lasso}(x, \lambda)$ the minimum of this optimization problem.
Define a rescaled time

$$s = \frac{4}{\log \frac{1}{\epsilon}} t. \qquad (3.4)$$

## 3.1 Connection to the positive lasso under a monotonicity assumption

**Theorem 3.1.** For all $s > 0$, let $x(s)$ denote a minimizer of the positive lasso

$$\min_{x \ge 0} \text{Lasso} \left( x, \frac{1}{s} \right).$$

Assume that $s > 0 \mapsto sx(s)$ is nondecreasing (coordinate-wise). Then

$$\text{Lasso} \left( \bar{x}^{\epsilon}(s), \frac{1}{s} \right) \xrightarrow{\epsilon \to 0} \text{PosLasso}_{*} \left( \frac{1}{s} \right).$$

The monotonicity of $s \mapsto sx(s)$ translates into the monotonicity of the solution of the parametric linear complementarity problem (4.11), introduced in Sec. 4.4. This monotonicity has first been studied in a different context, the analysis of elastoplastic structures [12]. Cottle proposes an algorithm to test whether the solution of a given problem is monotone, and derives necessary and sufficient conditions under which monotonicity holds for all possible values of $r$ [11]. See also [24] when $M$ is non-invertible. A sufficient condition for monotonicity is when $M$ is a positive definite matrix with non-positive off-diagonal entries. The author has proved Thm. 3.1 under this more restrictive assumption [4].

## 3.2 Approximate connection to the positive lasso in the general case

We now turn to the general case.

**Theorem 3.2.** For all $s > 0$, let $x(s)$ denote a minimizer of the positive lasso

$$\min_{x \ge 0} \text{Lasso} \left( x, \frac{1}{s} \right).$$

Assume that $s > 0 \mapsto x(s)$ is absolutely continuous on compact subsets of $(0, +\infty)$. Let

$$z^{\downarrow}(s) = \sum_{i=1}^{d} \int_{0}^{s} \left( \frac{d}{du}(ux_{i}(u)) \right)_{-} du. \qquad (3.5)$$

Heuristically, $z^{\downarrow}(s)$ quantifies the deviation from monotonicity of $z(s) = sx(s)$. Then, there exists a constant $C = C(d, M, r, \alpha) > 0$ such that

$$\limsup_{\epsilon \to 0} \text{Lasso} \left( \bar{x}^{\epsilon}(s), \frac{1}{s} \right) \le \text{PosLasso}_{*} \left( \frac{1}{s} \right) + C \left[ \frac{(1+s)^{1/2}}{s} z^{\downarrow}(s)^{1/2} + \frac{1+s}{s^2} z^{\downarrow}(s) \right].$$
# 4 The $u \circ u$ case — proofs of the results

This section is organized as follows.

The first four subsections gather some elements to prepare the proofs. In Sec. 4.1, we recall the mirror flow perspective on the DLN dynamics [23]. In Sec. 4.2, we prove a preliminary bound on the DLN dynamics, that is uniform in time $t$ and for $\epsilon$ small enough. Its proof is independent from the rest of the proofs, and can be skipped in a first reading. Sec. 4.3 introduces linear complementary problems, that provide a primal-dual perspective on the positive lasso. This primal-dual perspective is crucial to our proofs. Sec. 4.4 extends this introduction to parametric linear complementarity problems, where a parameter $s$ varies in the problem.

Finally, in Sec. 4.5, we prove Thm. 3.2 and in Sec. 4.6, we deduce the proof of Thm. 3.1.

**Additional notations for the proofs.** When applied to a $d \times d$ matrix, $\|\cdot\|$ denotes the operator norm associated to the norm $\|\cdot\|$ on $\mathbb{R}^d$. When $A$ is a positive semidefinite operator on a linear space $V$, we denote $\langle\cdot, \cdot\rangle_A = \langle\cdot, A\cdot\rangle$ the semidefinite inner product on $V$ associated to $A$ and $\|\cdot\|_A$ the associated seminorm.

When $A \in \mathbb{R}^{d \times k}$ is a matrix, we denote $A^\dagger \in \mathbb{R}^{k \times d}$ its Moore-Penrose pseudo-inverse.

If $f: \mathbb{R}^d \to \mathbb{R}$ is a function that has a unique minimizer on a set $C$, then we denote $\operatorname{argmin}_{x \in C} f(x)$ this unique minimizer.

## 4.1 Mirror flow interpretation

We recall the interpretation of the DLN dynamics as a mirror flow [23]. For a general introduction on mirror flows, we refer to [7, Chap. 4].

Eq. (3.2) can be interpreted as a mirror flow

$$ \frac{d\nabla h(x^{\varepsilon})}{dt} = -\nabla \ell(x^{\varepsilon}), \qquad (4.1) $$

where the mirror map

$$ h(x) = \frac{1}{4} \sum_{i=1}^{d} (x_i \log x_i - x_i) $$

is the entropy of the vector $x > 0$.

A central tool in analyzing mirror flows is the Bregman divergence associated to the mirror map $h$. For $x, y > 0$, it is defined as

$$ \begin{aligned} D(x, y) &= h(x) - h(y) - \langle \nabla h(y), x - y \rangle \\ &= \frac{1}{4} \sum_{i=1}^{d} \left( x_i \log \frac{x_i}{y_i} - x_i + y_i \right). \end{aligned} \qquad (4.2) $$
Note that, by convexity of the mirror map $h$, the Bregman divergence $D$ is always nonnegative. In our case, this Bregman divergence can be interpreted as a relative entropy.

The mirror variable $\nabla h(x^{\varepsilon})$ has an initialization $\nabla h(x^{\varepsilon}(0))$ that is diverging as $\varepsilon \to 0$:

$$ \nabla h(x^{\varepsilon}(0)) = \frac{1}{4} \log x^{\varepsilon}(0) = -\frac{1}{4} \left( \log \frac{1}{\varepsilon} \right) \mathbb{1} + O(1). $$

For this reason, we define a rescaled mirror variable

$$ w^{\varepsilon}(s) = -\frac{4}{\log \frac{1}{\varepsilon}} \nabla h(x^{\varepsilon}(s)) = -\frac{1}{\log \frac{1}{\varepsilon}} \log x^{\varepsilon}(s). $$

We have $w^{\varepsilon}(0) \xrightarrow{\varepsilon \to 0} \mathbb{1}$. This rescaled version particularly fits the analysis in the rescaled time $s$. For instance,

$$ \frac{dw^{\varepsilon}}{ds} = -\frac{4}{\log \frac{1}{\varepsilon}} \frac{dt}{ds} \frac{d\nabla h(x^{\varepsilon})}{dt} \Big|_{(\text{Eq. (4.1)})} = \nabla \ell(x^{\varepsilon}) = -r + Mx^{\varepsilon}. \quad (4.3) $$

## 4.2 Uniform bound on the trajectories

The goal of this section is to prove that the trajectories $x^{\varepsilon}(t)$ of the DLN dynamics are bounded uniformly in $t \ge 0$ and $\varepsilon > 0$ sufficiently small.

**Proposition 4.1.** There exists $C = C(d, M, r, \alpha) > 0$ and $\varepsilon_0 = \varepsilon_0(\alpha) > 0$ such that

$$ \forall \varepsilon \in (0, \varepsilon_0), \forall t \ge 0, \quad \|x^{\varepsilon}(t)\| \le C. $$

To prove this result, we first note that as the DLN dynamics are a gradient flow, the function values must be nonincreasing along trajectories.

**Lemma 4.2.** For all $\varepsilon > 0$, $t \mapsto \ell(x^{\varepsilon}(t))$ is nonincreasing.

As a consequence, there exists $C_1 = C_1(M, r, \alpha)$, $C_2 = C_2(M, r, \alpha) > 0$ such that for all $0 < \varepsilon \le 1$, for all $t \ge 0$, $\ell(x^{\varepsilon}(t)) \le C_1$ and $\|Mx^{\varepsilon}(t)\| \le C_2$.

*Proof.* Using Eq. (3.2),

$$ \frac{d}{dt} (\ell(x^{\varepsilon})) = \sum_{i=1}^{d} \partial_i \ell(x^{\varepsilon}) \frac{dx_i^{\varepsilon}}{dt} = -4 \sum_{i=1}^{d} x_i^{\varepsilon} (\partial_i \ell(x^{\varepsilon}))^2 \le 0. $$

This proves that $t \mapsto \ell(x^{\varepsilon}(t))$ is nonincreasing.

Moreover, the continuous function $\ell$ is bounded by a constant $C_1 = C_1(M, r, \alpha)$ on the compact interval $[0, \alpha^2] \subset \mathbb{R}^d$. As a consequence, for all $0 < \varepsilon \le 1$, for all $t \ge 0$,

$$ \ell(x^{\varepsilon}(t)) \le \ell(x^{\varepsilon}(0)) = \ell(\varepsilon\alpha^2) \le C_1. $$
Finally, let $x_* = x_*(r, M)$ be the minimum norm minimizer of $\ell$. Then for any $x \in \mathbb{R}^d$,

$$ \begin{aligned} \|Mx\|^2 &\le \|M\|\|M^{1/2}x\|^2 \le 2\|M\| (\|M^{1/2}x_*\|^2 + \|M^{1/2}(x-x_*)\|^2) \\ &= 2\|M\| (\|M^{1/2}x_*\|^2 + 2\ell(x) - 2\ell(x_*)). \end{aligned} $$

Thus the lemma holds with

$$ C_2(M, r, \alpha) = 2\|M\| (\|M^{1/2}x_*\|^2 + 2C_1(M, r, \alpha) - 2\ell(x_*)). $$

□

This result proves Prop. 4.1 when $M$ is positive definite. However, the proof in the positive semidefinite case requires more work. Our strategy consists in characterizing the flow $x^\epsilon(t)$ from its image $Mx^\epsilon(t)$, and, as a consequence, showing that $x^\epsilon(t)$ is bounded by a bound on its image $Mx^\epsilon(t)$. These arguments are the two lemmas below.

**Lemma 4.3.** For all $t \ge 0$,

$$ x^\epsilon(t) = \underset{x \ge 0, Mx=Mx^\epsilon(t)}{\operatorname{argmin}} D(x, x^\epsilon(0)), \quad (4.4) $$

where $D(x, y)$ is defined in Eq. (4.2). Note that we extend $D(x, y)$ to coordinates $x_i = 0$ by setting by continuity $0 \log 0 = 0$.

*Proof.* A point $x > 0$ is a minimizer of $\min_{x \ge 0, Mx=Mx^\epsilon(t)} D(x, x^\epsilon(0))$ if and only if $Mx = Mx^\epsilon(t)$ and $\nabla_x D(x, x^\epsilon(0)) \in \operatorname{Span} M$. For $x = x^\epsilon(t) > 0$, only the second condition needs to be checked. As $\nabla_x D(x, y) = \nabla h(x) - \nabla h(y)$ and by Eq. (4.1), we have

$$ \begin{aligned} \nabla_x D(x^\epsilon(t), x^\epsilon(0)) &= \nabla h(x^\epsilon(t)) - \nabla h(x^\epsilon(0)) \\ &= \int_0^t (r - Mx^\epsilon(t')) dt' \in \operatorname{Span} M. \end{aligned} $$

Moreover, $x^\epsilon(t)$ is the unique minimizer as $D(.,.)$ is marginally strictly convex in its first variable. This justifies using the notation $\operatorname{argmin}$. This concludes the proof. □

**Lemma 4.4.** There exists $\epsilon_0 = \epsilon_0(\alpha) > 0$ and $C = C(d, M) > 0$ such that for all $0 < \epsilon \le \epsilon_0$, for all $y = Mu$ for some $u \in \mathbb{R}^d$, $u \ge 0$, denoting

$$ x(y) = \underset{x \ge 0, Mx=y}{\operatorname{argmin}} D(x, x^\epsilon(0)), \quad (4.5) $$

we have

$$ \|x(y)\| \le C(1 + \|y\|^2). $$

Before we prove this last lemma, let us combine the above lemmas to prove Prop. 4.1.
Proof of Proposition 4.1. By Lemma 4.3,

$$x^{\epsilon}(t) = \underset{x>0, Mx=Mx^{\epsilon}(t)}{\operatorname{argmin}} D(x, x^{\epsilon}(0)). \quad (4.6)$$

Using Lemma 4.4 and then Lemma 4.2, there exists $\epsilon_0 = \epsilon_0(\alpha) > 0$ such that for all $0 < \epsilon < \epsilon_0$,

$$\|x^{\epsilon}(t)\| \le C(d, M)(1 + \|Mx^{\epsilon}(t)\|^2) \le C(d, M)(1 + C_2(M, r, \alpha)^2).$$

□

We are now only left with the proof of Lemma 4.4 to finish this section. This result requires a Caratheodory theorem on cones. Let $a_i$, $i \in I$, denote a finite family of vectors in $\mathbb{R}^d$. The cone generated by $(a_i)_{i \in I}$ is defined as

$$\mathrm{Cone}(a_i, i \in I) = \left\{ \sum_{i \in I} \lambda_i a_i \mid \lambda_i \ge 0, i \in I \right\}.$$

**Theorem 4.5 ([8]).** Let $a_1, \dots, a_k \in \mathbb{R}^d$ and $y \in \mathrm{Cone}(a_1, \dots, a_k)$.

There exists a linearly independent subfamily $a_i$, $i \in I$, $I \subset \{1, \dots, k\}$ such that $y \in \mathrm{Cone}(a_i, i \in I)$.

In particular, $y$ is in the cone generated by a subfamily of at most $d$ vectors.

To be precise, Carathéodory's theorem usually refers to the last statement. However, below, we are interested in the linear independence statement, which follows easily from the same proof.

*Proof.* As $y \in \mathrm{Cone}(a_1, \dots, a_k)$, $y$ can be decomposed as $y = \sum_{i \in I} \lambda_i a_i$ with $I \subset \{1, \dots, k\}$ and $\lambda_i \ge 0$, $i \in I$. Consider such a decomposition with $I$ of minimal cardinality. We will show that in this case, the $a_i$, $i \in I$ are linearly independent.

By contradiction, assume that there exists $\mu_i$, $i \in I$, not all equal to 0, such that $\sum_{i \in I} \mu_i a_i = 0$. Then for all $t$, we have that $y = \sum_{i \in I} (\lambda_i - t\mu_i)a_i$. We will use this degree of freedom in $t$ to remove an element from $I$, and thus contradict the minimality of $I$.

Without loss of generality, we can assume that there exists a positive $\mu_i$. (We can consider $-\mu$ instead of $\mu$.) Consider

$$\tau = \inf \{t \ge 0 \mid \lambda_i - t\mu_i = 0 \text{ for some } i \in I\}.$$

Note that $\tau < \infty$ as there exists $i \in I$ such that $\mu_i > 0$. Then for all $i \in I$, $\lambda_i - \tau\mu_i \ge 0$, with equality for at least one $i \in I$, that we denote $i_0$. Then $y = \sum_{i \in I \setminus \{i_0\}} (\lambda_i - \tau\mu_i)a_i$. Thus $I$ is not minimal, which gives a contradiction. □

We now use Carathodory's theorem to show a central lemma. Let us give first the motivation. Consider a feasible linear system $Ax = b$. The minimum norm solution $x = A^\dagger b$ is bounded in norm by $\|A^\dagger\|\|b\|$. We now consider the
same question for the system $Ax = b$ with the additional constraint $x \ge 0$ (assuming there exists at least one such solution). How can the minimum norm solution be bounded? Carathéodory's theorem enables to prove that, the non-negative minimum norm solution is, again, bounded by a constant proportional to the norm of $b$.

**Lemma 4.6.** Let $A \in \mathbb{R}^{d \times k}$. There exists $C = C(A) > 0$ such that for all $y = Au$ for some $u \in \mathbb{R}^k$, $u \ge 0$, denoting

$$x(y) = \underset{x \ge 0, Ax=y}{\operatorname{argmin}} \|x\|, \qquad (4.7)$$

we have

$$\|x(y)\| \le C\|y\|.$$

*Proof.* First, we note that $\|x\|$ diverges as $\|x\| \to \infty$, $x \ge 0$, $Ax = y$. As a consequence, the minimizer in Eq. (4.5) is well-defined as the unique minimizer of a strictly convex function on a compact set.

In this proof, we show that the lemma holds with $C := \max_{I \subset \{1, \dots, k\}} \|(A_I)^\dagger\|$. Denote $a_1, \dots, a_k$ the columns of $A$. Let $y = Au$ for some $u \ge 0$. Then $y \in \text{Cone}(a_1, \dots, a_k)$. By Carathéodory's theorem, there exists a linearly independent subfamily $a_i$, $i \in I$, such that $y \in \text{Cone}(a_i, i \in I)$, i.e., $y = A_I v$ for some $v \in \mathbb{R}^I$, $v \ge 0$. The matrix $A_I$ has full column rank, thus $v = (A_I)^\dagger y$. Consider $x \in \mathbb{R}^k$ such that $x_i = v_i$ if $i \in I$, and $x_i = 0$ otherwise. Then $Ax = y$ and $x \ge 0$. Thus

$$\|x(y)\| \le \|x\| = \|v\| = \|(A_I)^\dagger y\| \le \|(A_I)^\dagger\| \|y\| \le C\|y\|.$$

This completes the proof. $\square$

We are now ready to prove Lemma 4.4.

*Proof of Lemma 4.4.* First, we note that $D(x, x^\epsilon(0))$ diverges as $\|x\| \to \infty$, $x \ge 0$. As a consequence, the minimizer in Eq. (4.5) is well-defined as the unique minimizer of a strictly convex function on a compact set.

The only difference between Lemma 4.4 and Lemma 4.6 is that the former minimizes $D(x, x^\epsilon(0))$ while the latter minimizes $\|x\|$. However, the two quantities are comparable in the sense that there exists $\epsilon_0 = \epsilon_0(\alpha)$, $C_1 = C_1(d)$, $C_2 = C_2(d) > 0$ such that for all $0 < \epsilon \le \epsilon_0$, for all $x \ge 0$,

$$\frac{1}{8} \left( \log \frac{1}{\epsilon} \right) \|x\| - C_1 \le D(x, x^\epsilon(0)) \le C_3 \left( \log \frac{1}{\epsilon} \right) \|x\| + \frac{1}{4} \|x\|^2 + 1. \quad (4.8)$$

Indeed,

$$\begin{align*}
D(x, x^\epsilon(0)) &= \frac{1}{4} \sum_{i=1}^{d} \left( x_i \log \frac{x_i}{\epsilon \alpha_i^2} - x_i + \epsilon \alpha_i^2 \right) \\
&= \frac{1}{4} \sum_{i=1}^{d} x_i \log x_i + \frac{1}{4} \left( \log \frac{1}{\epsilon} - 1 \right) \|x\|_1 + \frac{1}{4} \sum_{i=1}^{d} x_i \log \frac{1}{\alpha_i^2} + \frac{\epsilon}{4} \sum_{i=1}^{d} \alpha_i^2.
\end{align*}$$
For the lower-bound, we use that $u \mapsto u \log u$ is bounded from below on $\mathbb{R}_{\ge 0}$.
Thus there exists $\varepsilon_1 = \varepsilon_1(\alpha)$ such that, for all $\varepsilon < \varepsilon_1$,

$$D(x, x^{\varepsilon}(0)) \geq -C_1(d) + \frac{1}{8} \left( \log \frac{1}{\varepsilon} \right) \|x\|.$$

For the upper-bound, we have

$$D(x, x^{\varepsilon}(0)) = \frac{1}{4} \sum_{i=1}^{d} \left( x_i \log \frac{x_i}{\varepsilon \alpha_i^2} - x_i + \varepsilon \alpha_i^2 \right) \\ \leq \frac{1}{4} \sum_{i=1}^{d} x_i \left( \log x_i + \log \frac{1}{\varepsilon} + \log \frac{1}{\alpha_i^2} \right) + \frac{\varepsilon}{4} \sum_{i=1}^{d} \alpha_i^2.$$

We use $\log y \le y$ for $y > 0$. Thus there exists $\varepsilon_2 = \varepsilon_2(\alpha)$, $C_2 = C_2(d)$ such that, for all $\varepsilon < \varepsilon_2$,

$$D(x, x^{\varepsilon}(0)) \leq \frac{1}{4} \|x\|^2 + \frac{1}{2} \left( \log \frac{1}{\varepsilon} \right) \sum_{i=1}^{d} x_i + 1 \leq \frac{1}{4} \|x\|^2 + C_2(d) \left( \log \frac{1}{\varepsilon} \right) \|x\| + 1.$$

Thus Eq. (4.8) holds for $\varepsilon \le \varepsilon_0(\alpha) := \min(\varepsilon_1(\alpha), \varepsilon_2(\alpha))$.

We now define $\beta(y) = \underset{\beta=0, M=\underline{y}}{\operatorname{argmin}} \|\beta\|$. By Lemma 4.6, $\|\beta(y)\| \le C_3(M)\|y\|$. Then we have,

$$\begin{align*}
\frac{1}{8} \left( \log \frac{1}{\varepsilon} \right) \|x(y)\| &\le C_1(d) + D(x(y), x^{\varepsilon}(0)) && \text{by Eq. (4.8)} \\
&\le C_1(d) + D(\beta(y), x^{\varepsilon}(0)) && \text{by the variational definition of } x(y) \\
&\le C_4(d) + C_2(d) \left( \log \frac{1}{\varepsilon} \right) \|\beta(y)\| + \frac{1}{4} \|\beta(y)\|^2 && \text{by Eq. (4.8)} \\
&\le C_4(d) + C_5(d, M) \left( \log \frac{1}{\varepsilon} \right) \|y\| + C_6(d, M) \|y\|^2.
\end{align*}$$

Assuming that $\varepsilon_0$ is small enough so that $\frac{1}{8} \log \frac{1}{\varepsilon_0} \ge 1$, we have

$$\|x(y)\| \le C_4(d) + 8C_5(d, M)\|y\| + C_6(d, M)\|y\|^2 \le C(d, M)(1 + \|y\|^2).$$

□

## 4.3 The positive lasso and linear complementarity problems

The positive lasso is in fact a constrained quadratic optimization problem: $\min_{x \ge 0} \frac{1}{2} \langle x, Mx \rangle - \langle r, x \rangle + \lambda \langle 1, x \rangle$. As a consequence, its primal dual formulation is a linear complementarity problem [13].
**Proposition 4.7.** Let $x \in \mathbb{R}^d$. The vector $x$ is a minimizer of the optimization problem (3.3) if and only if there exists $v \in \mathbb{R}^d$ such that $(v, x)$ is a solution of

$$ \begin{aligned} v &= -r + \lambda \mathbb{1} + Mx, \\ v &\ge 0, x \ge 0, \langle v, x \rangle = 0. \end{aligned} \quad (4.9) $$

The system above has the form of a linear complementarity problem (LCP) [13].

This result is classical and its proof follows from convex duality [6, Section 5]. We recall it for the sake of completeness.

*Proof.* For simplicity, we denote $q = -r + \lambda \mathbb{1}$. The Lagrangian associated to (3.3) is

$$ L(x, v) = \text{Lasso}(x, \lambda) - \langle v, x \rangle = \frac{1}{2} \langle x, Mx \rangle + \langle q, x \rangle - \langle v, x \rangle $$

where $v \in \mathbb{R}^d$ is the Lagrange multiplier associated to the constraint $x \ge 0$. As the optimization problem (3.3) is convex, the KKT conditions are necessary and sufficient for optimality. The stationarity condition is

$$ 0 = \nabla_x L(x, v) = q + Mx - v, $$

the feasibility conditions are $x \ge 0$ and $v \ge 0$, and the complementary slackness condition is $\langle v, x \rangle = 0$. This proves Prop. 4.7. □

We now study the existence and uniqueness of the solution of the LCP (4.9). Note that if $M$ is positive definite, there exists a unique solution $(v, x)$ [13, Thm. 3.1.6]. In the more general case where $M$ is positive semidefinite, existence still holds but uniqueness is more subtle. For instance, the positive lasso (3.3) might not have a unique minimizer, thus we might not have uniqueness of the solution in $x$. However, we have uniqueness in $v$.

**Proposition 4.8.** There exists a solution of the LCP (4.9). Moreover, the solution of the LCP is unique in $v$ in the sense that if $(v, x)$ and $(v', x')$ are two solutions of the LCP, then $v = v'$.

*Proof. Existence.* By [14], it suffices to show that $\text{Lasso}(x, \lambda) = \ell(x) + \lambda \langle \mathbb{1}, x \rangle$ is bounded from below on the set $\{x | x \ge 0\}$. The first term $\ell(x)$ is bounded from below on $\mathbb{R}^d$ (as $r \in \text{Span}(M)$), and the second term is nonnegative on $\{x | x \ge 0\}$.

*Uniqueness.* The result is provided in [13, Thm. 3.1.7(d)]. □

## 4.4 The positive lasso regularization path and parametric linear complementarity problems

In Sec. 3, we consider a solution $x(s)$ of the positive lasso with regularization parameter $\lambda = \frac{1}{s}$, $s > 0$. For varying $s$, we obtain a certain parametrization
of the regularization path of the positive lasso. In this section, we draw a connection with so-called parametric LCPs.

From Prop. 4.7, there exists $v(s)$ such that $(v(s), x(s))$ is a solution of the LCP

$$v(s) = -r + \frac{1}{s}1 + Mx(s), \qquad (4.10)$$
$$v(s) \ge 0, x(s) \ge 0, \langle v(s), x(s) \rangle = 0.$$

Denote $w(s) = sv(s)$ and $z(s) = sx(s)$. Then

$$w(s) = -sr + 1 + Mz(s), \qquad (4.11)$$
$$w(s) \ge 0, z(s) \ge 0, \langle w(s), z(s) \rangle = 0.$$

This is a parametric LCP, where the parameter is $s$ [13, Sec. 4.5].

Note that while the LCP (4.10) is defined only for $s > 0$, the LCP (4.11) is also defined for $s = 0$. This extension is rather trivial, the solution of both LCPs being simple for $s$ small enough, as shown in the following lemma.

**Lemma 4.9.** Assume $0 \le s < \frac{1}{\|r\|_{\infty}}$. Then the LCP (4.11) has a unique solution $(w(s), z(s)) = (1 - sr, 0)$. If further $s > 0$, this means that the LCP (4.10) has a unique solution $(v(s), x(s)) = (-r + \frac{1}{s}1, 0)$.

*Proof.* $(w(s), z(s)) = (1 - sr, 0)$ is a solution of (4.11). As the solution is unique in $w$, $1 - sr$ is the unique solution in $w$. But as $1 - sr > 0$, this imposes that $z(s) = 0$ is the unique solution in $z$ by complementarity. $\square$

We now prove a simple regularity result on solutions of parametric LCPs.

**Lemma 4.10.** Let $w(s)$ be the unique solution in $w$ of the parametric LCP (4.11). Then $s \ge 0 \mapsto w(s)$ is Lipschitz continuous and thus absolutely continuous, $\frac{dw}{ds} \in \text{Span } M$ and $\|\frac{dw}{ds}\|_{M^\dagger} \le \|r\|_{M^\dagger}$.

*Proof.* Let $s, s' \ge 0$ and $(w, z) = (w(s), z(s))$, $(w', z') = (w(s'), z(s'))$ denote solutions of the parametric LCP (4.11) for the respective values $s, s'$. Then, we have

$$w = -sr + 1 + Mz, \quad \text{and} \quad w' = -s'r + 1 + Mz'.$$

Hence, $w - w' = -(s - s')r + M(z - z') \in \text{Span } M$ and

$$\begin{aligned}
\|w - w'\|_{M^\dagger}^2 &= \langle w - w', -(s - s')r + M(z - z') \rangle_{M^\dagger} \\
&= -(s - s')\langle w - w', r \rangle_{M^\dagger} + \langle w - w', z - z' \rangle \\
&= -(s - s')\langle w - w', r \rangle_{M^\dagger} + \langle w, z \rangle - \langle w', z \rangle - \langle w, z' \rangle + \langle w', z' \rangle.
\end{aligned}$$

We can use Hölder's inequality to bound the first term. Furthermore, by complementarity slackness $\langle z, w \rangle = \langle z', w' \rangle = 0$. Finally, all vectors $w, w', z, z'$ are nonnegative, thus $\langle w', z \rangle, \langle w, z' \rangle \ge 0$. Thus, we have

$$\|w - w'\|_{M^\dagger}^2 \le |s - s'| \|w - w'\|_{M^\dagger} \|r\|_{M^\dagger},$$
i.e.,

$$ \|w - w'\|_{M^{\dagger}} \le |s - s'| \|r\|_{M^{\dagger}}. $$

This proves that the map $s \mapsto w(s)$ is Lipschitz continuous. As for all $s, s'$, $w(s) - w(s') \in \text{Span } M$, we have $\frac{dw}{ds} \in \text{Span } M$. The inequality above also shows that $\|\frac{dw}{ds}\|_{M^{\dagger}} \le \|r\|_{M^{\dagger}}$. $\square$

## 4.5 Proof of Theorem 3.2

For all $s > 0$, $x(s)$ is a minimizer of $\min_{x \ge 0} \text{Lasso}(x, \frac{1}{s})$. We use the notations of Sec. 4.4: by Prop. 4.7, there exists $v(s)$ such that $(v(s), x(s))$ is a solution of the LCP (4.10). For $s > 0$, denote $w(s) = sv(s)$ and $z(s) = sx(s)$. Then $(w(s), z(s))$ are solution of the parametric LCP (4.11). We extend this definition of $(w, z)$ with $(w(0), z(0)) = (1, 0)$, which a solution of the LCP (4.11) for $s = 0$.

In this proof, the solution $(w(s), z(s))$ of the parametric LCP will be compared to $(w^{\epsilon}(s), z^{\epsilon}(s))$ where $w^{\epsilon}(s)$ is defined in Sec. 4.1 and

$$ z^{\epsilon}(s) = s \bar{x}^{\epsilon}(s) = \int_{0}^{s} x^{\epsilon}(u) du. $$

Note that:

$$ \frac{dz^{\epsilon}}{ds} = x^{\epsilon}(s). \qquad (4.12) $$

Integrating Eq. (4.3), we obtain

$$ w^{\epsilon}(s) = w^{\epsilon}(0) - sr + Mz^{\epsilon}(s). \qquad (4.13) $$

This equation has a similarity with the first equation of the LCP (4.11). We now seek to bound

$$ \Delta^{\epsilon}(s) := \frac{1}{2} \|z^{\epsilon}(s) - z(s)\|_{M}^{2}. $$

At $s = 0$, we have by definition, $z^{\epsilon}(0) = 0$ and by Lemma 4.9, $z(0) = 0$. Thus $\Delta^{\epsilon}(s) = 0$.

We compute the derivative of $\Delta^{\epsilon}(s)$:

$$ \frac{d\Delta^{\epsilon}}{ds} = \left\langle \frac{dz^{\epsilon}(s)}{ds} - \frac{dz(s)}{ds}, M(z^{\epsilon}(s) - z(s)) \right\rangle $$

We use Eqs. (4.12), (4.13) and the first equation of (4.11):

$$ \begin{aligned} \frac{d\Delta^{\epsilon}}{ds} &= \left\langle x^{\epsilon}(s) - \frac{dz(s)}{ds}, w^{\epsilon}(s) - w(s) + 1 - w^{\epsilon}(0) \right\rangle \\ &= \langle x^{\epsilon}(s), w^{\epsilon}(s) \rangle - \langle x^{\epsilon}(s), w(s) \rangle - \left\langle \frac{dz(s)}{ds}, w^{\epsilon}(s) \right\rangle \qquad (4.14) \\ &\quad + \left\langle \frac{dz(s)}{ds}, w(s) \right\rangle + \langle x^{\epsilon}(s), 1 - w^{\epsilon}(0) \rangle - \left\langle \frac{dz(s)}{ds}, 1 - w^{\epsilon}(0) \right\rangle. \end{aligned} $$

We now upper-bound each term separately:
• The function $u > 0 \mapsto u \log u$ is uniformly lower bounded by a universal constant thus

$$ \langle x^{\epsilon}(s), w^{\epsilon}(s) \rangle = - \frac{1}{\log \frac{1}{\epsilon}} \sum_{i=1}^{d} x_{i}^{\epsilon}(s) \log x_{i}^{\epsilon}(s) \le \frac{C(d)}{\log \frac{1}{\epsilon}}. $$

• We have $x^{\epsilon}(s) \ge 0$ and $w(s) \ge 0$ thus $-\langle x^{\epsilon}(s), w(s) \rangle \le 0$.

• If $\frac{dz_i(s)}{ds} \ge 0$, we use that by Prop. 4.1,

$$ w_i^{\epsilon}(s) = - \frac{1}{\log \frac{1}{\epsilon}} \log x_i^{\epsilon}(s) \ge - \frac{C(d, M, r, \alpha)}{\log \frac{1}{\epsilon}}. $$

If $\frac{dz_i(s)}{ds} \le 0$, we use Eq. (4.3) and Prop. 4.1 to obtain

$$ w_i^{\epsilon}(s) \le C(d, M, r, \alpha)(1 + s). $$

Thus

$$ - \left\langle \frac{dz(s)}{ds}, w^{\epsilon}(s) \right\rangle \le C(d, M, r, \alpha) \sum_{i=1}^{d} \left[ \frac{1}{\log \frac{1}{\epsilon}} \left( \frac{dz_i(s)}{ds} \right)_+ + (1+s) \left( \frac{dz_i(s)}{ds} \right)_- \right]. $$

• Let $i \in \{1, \dots, d\}$. We show that $\frac{dz_i(s)}{ds}w_i(s) = 0$. From Eqs. (4.11), we have $w_i(s)z_i(s) = 0$. If $w_i(s) = 0$, then the conclusion is obvious. Otherwise $z_i(s) = 0$. Differentiating $w_i(s)z_i(s) = 0$, we obtain $\frac{dw_i(s)}{ds}z_i(s) + w_i(s)\frac{dz_i(s)}{ds} = 0$. As $z_i(s) = 0$, this gives the desired conclusion.

Thus, we have $\langle \frac{dz(s)}{ds}, w(s) \rangle = 0$.

• Note that $1 - w^{\epsilon}(0) = 1 + \frac{1}{\log \frac{1}{\epsilon}} \log x^{\epsilon}(0) = \frac{2}{\log \frac{1}{\epsilon}} \log \alpha$. This enables to bound the last two terms, using again Prop. 4.1.

Recall that $z^{\downarrow}(s) = \sum_{i=1}^{d} \int_{0}^{s} \left( \frac{dz_i(u)}{du} \right)_{-} du$. Denote also $z^{\uparrow}(s) = \sum_{i=1}^{d} \int_{0}^{s} \left( \frac{dz_i(u)}{du} \right)_{+} du$. Integrating the bounds obtained between 0 and $s$, we have

$$ \Delta^{\epsilon}(s) \le C(d, M, r, \alpha) \left[ \frac{1}{\log \frac{1}{\epsilon}} (s + z^{\uparrow}(s)) + (1+s)z^{\downarrow}(s) \right]. $$

At this point, we have bounded $\|z^{\epsilon}(s) - z(s)\|_{M}^{2}$, or, equivalently, $\|\bar{x}^{\epsilon}(s) - x(s)\|_{M}^{2}$, where $x(s)$ is a minimizer of the positive lasso with regularization $\lambda = \frac{1}{s}$. However, as $M$ might not be positive definite, we can not conclude directly.

The positive lasso objective function $\text{Lasso}(x, \frac{1}{s})$ is a quadratic function on the set of nonnegative vectors $x \ge 0$:

$$ \text{Lasso} \left( x, \frac{1}{s} \right) = g_s(x) := \frac{1}{2} \langle x, Mx \rangle - \langle r, x \rangle + \frac{1}{s} \langle \mathbb{1}, x \rangle. $$
As a consequence, we can compute Lasso($\bar{x}^{\epsilon}(s), 1/s$) = $g_s(\bar{x}^{\epsilon}(s))$ using the second-order approximation of $g_s$ at $x(s)$:

$$
\begin{align*}
\text{Lasso}\left(\bar{x}^{\epsilon}(s), \frac{1}{s}\right) - \text{PosLasso}_{*}\left(\frac{1}{s}\right) &= g_s(\bar{x}^{\epsilon}(s)) - g_s(x(s)) \\
&= \langle \nabla g_s(x(s)), \bar{x}^{\epsilon}(s) - x(s) \rangle + \frac{1}{2} \|\bar{x}^{\epsilon}(s) - x(s)\|_{M}^{2} \\
&= \left\langle Mx(s) - r + \frac{1}{s}1, \bar{x}^{\epsilon}(s) - x(s) \right\rangle + \frac{1}{2} \|\bar{x}^{\epsilon}(s) - x(s)\|_{M}^{2} \\
&= \langle v(s), \bar{x}^{\epsilon}(s) - x(s) \rangle + \frac{1}{2} \|\bar{x}^{\epsilon}(s) - x(s)\|_{M}^{2} \\
&= \frac{1}{s^2} E^{\epsilon}(s)
\end{align*}
$$

where $E^{\epsilon}(s) = \langle w(s), z^{\epsilon}(s) - z(s) \rangle + \Delta^{\epsilon}(s)$. We compute

$$
\frac{dE^{\epsilon}(s)}{ds} = \left\langle \frac{dw(s)}{ds}, z^{\epsilon}(s) - z(s) \right\rangle + \langle w(s), x^{\epsilon}(s) \rangle - \left\langle w(s), \frac{dz(s)}{ds} \right\rangle + \frac{d\Delta^{\epsilon}(s)}{ds}.
$$

For the first term, we use the Cauchy-Schwarz inequality and Lemma 4.10.
Moreover, several terms cancel out with the expression of the derivative of $\Delta^{\epsilon}(s)$
in Eq. (4.14). We obtain

$$
\frac{dE^{\epsilon}(s)}{ds} \le \|r\|_{M^{\dagger}} \|z^{\epsilon}(s) - z(s)\|_{M} + \langle x^{\epsilon}(s), w^{\epsilon}(s) \rangle - \left\langle \frac{dz(s)}{ds}, w^{\epsilon}(s) \right\rangle \\
+ \langle x^{\epsilon}(s), 1 - w^{\epsilon}(0) \rangle - \left\langle \frac{dz(s)}{ds}, 1 - w^{\epsilon}(0) \right\rangle.
$$

All of these terms have been bounded above. Integrating between 0 and s, we
obtain

$$
\begin{align*}
E^{\epsilon}(s) &\le C(d, M, r, \alpha) \left[ \int_0^s \Delta^{\epsilon}(u)^{1/2} du + \frac{1}{\log \frac{1}{\epsilon}} (s + z^{\uparrow}(s)) + (1+s)z^{\downarrow}(s) \right] \\
&\le C(d, M, r, \alpha) \left[ s \left( \frac{1}{\log \frac{1}{\epsilon}} (s + z^{\uparrow}(s)) + (1+s)z^{\downarrow}(s) \right)^{1/2} \right. \\
&\qquad \left. + \frac{1}{\log \frac{1}{\epsilon}} (s + z^{\uparrow}(s)) + (1+s)z^{\downarrow}(s) \right].
\end{align*}
$$

This allows use to conclude

$$
\begin{align*}
\limsup_{\epsilon \to 0} \text{Lasso}\left(\bar{x}^{\epsilon}(s), \frac{1}{s}\right) - \text{PosLasso}_{*}\left(\frac{1}{s}\right) \\
&= \limsup_{\epsilon \to 0} \frac{1}{s^2} E^{\epsilon}(s) \\
&\le C(d, M, r, \alpha) \left[ \frac{(1+s)^{1/2}}{s} z^{\uparrow}(s)^{1/2} + \frac{1+s}{s^2} z^{\downarrow}(s) \right].
\end{align*}
$$
## 4.6 Proof of Theorem 3.1

Thm. 3.1 is an application of Thm. 3.2. However, to apply Thm. 3.2, we need to prove that $s \mapsto x(s)$ is absolutely continuous. This is proven in the following lemma (in combination with Lemma 4.9).

**Lemma 4.11.** Under the assumptions of Thm. 3.1, the function $s \ge 0 \mapsto z(s)$ is absolutely continuous on compact subsets of $[0, +\infty)$.

*Proof.* From Lemma 4.10, we have that $s \ge 0 \mapsto w(s)$ is $C_1(M, r)$-Lipschitz continuous for some constant $C_1(M, r) > 0$. Using the linear relationship $w(s) = -sr + 1 + Mz(s)$, this implies that $z \ge 0 \mapsto P_{\text{Span } M} z(s)$ is $C_2(M, r)$-Lipschitz continuous for some constant $C_2(M, r) > 0$, where $P_{\text{Span } M}$ denotes the orthogonal projection onto $\text{Span } M$.

Denote also $P_{\text{ker } M}$ denotes the orthogonal projection onto $\text{ker } M$. We have the complementarity slackness $\langle w(s), z(s) \rangle = 0$. Recall that $w(s) \in 1 + \text{Span } M$. Thus we obtain

$$ 
\begin{aligned}
0 &= \langle w(s), z(s) \rangle = \langle w(s), P_{\text{Span } M} z(s) \rangle + \langle w(s), P_{\text{ker } M} z(s) \rangle \\
  &= \langle w(s), P_{\text{Span } M} z(s) \rangle + \langle 1, P_{\text{ker } M} z(s) \rangle.
\end{aligned} 
\quad (4.15) $$

Consider $s_1 \le s_2$. As $s \mapsto z(s)$ is monotone, we have

$$ 
\begin{aligned}
\|z(s_2) - z(s_1)\|_1 &= \langle 1, z(s_2) - z(s_1) \rangle \\
&= \langle 1, P_{\text{Span } M} z(s_2) - P_{\text{Span } M} z(s_1) \rangle \\
&\quad + \langle 1, P_{\text{ker } M} z(s_2) - P_{\text{ker } M} z(s_1) \rangle.
\end{aligned} 
$$

We use Hölder's inequality and Eq. (4.15):

$$ 
\begin{aligned}
\|z(s_2) - z(s_1)\|_1 &\le \sqrt{d} \| P_{\text{Span } M} z(s_2) - P_{\text{Span } M} z(s_1) \| \\
&\quad + \langle w(s_1), P_{\text{Span } M} z(s_1) \rangle - \langle w(s_2), P_{\text{Span } M} z(s_2) \rangle \\
&\le \sqrt{d} C_2(M, r) |s_2 - s_1| + \langle w(s_1) - w(s_2), P_{\text{Span } M} z(s_1) \rangle \\
&\quad + \langle w(s_2), P_{\text{Span } M} z(s_1) - P_{\text{Span } M} z(s_2) \rangle \\
&\le \sqrt{d} C_2(M, r) |s_2 - s_1| + C_1(M, r) |s_2 - s_1| C_2(M, r) s_2 \\
&\quad + (\sqrt{d} + C_1(M, r) s_1) C_2(M, r) |s_2 - s_1| \\
&\le C_3(d, M, r) (1 + s_1 + s_2) |s_2 - s_1|.
\end{aligned} 
$$

This proves that $z \ge 0 \mapsto z(s)$ is Lipchitz, and thus absolutely continuous, on compact subsets of $[0, +\infty)$. $\square$

# 5 The $u \circ v$ case — proof of the results

The strategy of this section is to reduce the $u \circ v$ case to the $u^2$ case. The reduction methods are detailed in Sec. 5.1. In Sec. 5.1.1, we reduce the lasso problem to a positive lasso problem. In Sec. 5.1.2, we reduce the DLN dynamics in the $u \circ v$ case to the dynamics in the $u^2$ case. Finally, in Sec. 5.2, we use these elements to deduce Thm. 2.1 from Thm. 3.1 and Thm. 2.2 from Thm. 3.2.
## 5.1 Reductions

### 5.1.1 Reduction of the lasso to the positive lasso

We study the minimization of the lasso objective:

$$ \min_{x \in \mathbb{R}^d} \{ \text{Lasso}(x, \lambda) = \ell(x) + \lambda \|x\|_1 \}, \quad \ell(x) = \frac{1}{2} \langle x, Mx \rangle - \langle r, x \rangle. $$

We want to connect the lasso minimization problem to a positive lasso minimization problem (3.3). This can be seen as a complexification of the lasso minimization problem, as constrained minimization problems are arguably more delicate to deal with than unconstrained ones. However, the lasso objective is quadratic on nonnegative vectors, while it is not on the full space $\mathbb{R}^d$ (when $\lambda > 0$). The constrained minimization of a quadratic has some advantages over the unconstrained minimization of a non-smooth function.

The strategy is to decompose $x$ as the difference $x = y^{\text{pos}} - y^{\text{neg}}$ of two nonnegative vectors $y^{\text{pos}}, y^{\text{neg}} \ge 0$. For instance, a canonical choice would be to take $y^{\text{pos}} = x_+$ and $y^{\text{neg}} = x_-$. Note that for such a decomposition,

$$ \ell(x) = \tilde{\ell}(y), \quad y = \begin{pmatrix} y^{\text{pos}} \\ y^{\text{neg}} \end{pmatrix}, $$

where $\tilde{\ell}$ is the quadratic function

$$ \tilde{\ell}(y) = \frac{1}{2} \langle y, \tilde{M}y \rangle - \langle \tilde{r}, y \rangle, \quad \tilde{M} = \begin{pmatrix} M & -M \\ -M & M \end{pmatrix}, \quad \tilde{r} = \begin{pmatrix} r \\ -r \end{pmatrix}. $$

We define the lasso objective associated to $\tilde{\ell}$:

$$ \widetilde{\text{Lasso}}(y, \lambda) = \tilde{\ell}(y) + \lambda \|y\|_1. $$

We denote $\widetilde{\text{PosLasso}}(\lambda) = \min_{y \ge 0} \widetilde{\text{Lasso}}(y, \lambda)$ the minimum of the positive lasso optimization problem associated to $\tilde{\ell}$.

**Lemma 5.1.** (1) For any $y = (y^{\text{pos}}, y^{\text{neg}}) \in \mathbb{R}^{2d}_{\ge 0}$,

$$ \text{Lasso}(y^{\text{pos}} - y^{\text{neg}}, \lambda) \le \widetilde{\text{Lasso}}(y, \lambda), $$

with equality if and only if $\lambda = 0$ or $\langle y^{\text{pos}}, y^{\text{neg}} \rangle = 0$.

(2) If $z$ minimizes Lasso$(\cdot, \lambda)$ over $\mathbb{R}^d$, then $y = (z_+, z_-) \in \mathbb{R}^{2d}_{\ge 0}$ minimizes $\widetilde{\text{Lasso}}(\cdot, \lambda)$ over $\mathbb{R}^{2d}_{\ge 0}$.

(3) $\widetilde{\text{PosLasso}}(\lambda) = \widetilde{\text{PosLasso}}_*(\lambda)$.
Proof. (1) Consider $y = (y^{\text{pos}}, y^{\text{neg}}) \in \mathbb{R}_{\ge 0}^{2d}$.

$$
\begin{align*}
\text{Lasso}(y^{\text{pos}} - y^{\text{neg}}, \lambda) &= \ell(y^{\text{pos}} - y^{\text{neg}}) + \lambda \|y^{\text{pos}} - y^{\text{neg}}\|_1 \\
&\le \ell(y^{\text{pos}} - y^{\text{neg}}) + \lambda (\|y^{\text{pos}}\|_1 + \|y^{\text{neg}}\|_1) \\
&= \tilde{\ell}(y) + \lambda \|y\|_1 \\
&= \widetilde{\text{Lasso}}(y, \lambda).
\end{align*}
$$

There is equality if and only if $\lambda = 0$ or there is equality in the triangle inequality, which happens if and only if $\langle y^{\text{pos}}, y^{\text{neg}} \rangle = 0$.

(2) Let $z$ be a minimizer of $\text{Lasso}(., \lambda)$ over $\mathbb{R}^d$. Consider $y = (y^{\text{pos}}, y^{\text{neg}}) \in \mathbb{R}_{\ge 0}^{2d}$. Then, from (1),

$$
\widetilde{\text{Lasso}}(y, \lambda) \ge \text{Lasso}(y^{\text{pos}} - y^{\text{neg}}, \lambda) \ge \text{Lasso}(z, \lambda) = \widetilde{\text{Lasso}}((z_+, z_-), \lambda),
$$

where the equality holds in the last step as $\langle z_+, z_- \rangle = 0$. As a consequence, $(z_+, z_-)$ minimizes $\widetilde{\text{Lasso}}(., \lambda)$ over $\mathbb{R}_{\ge 0}^{2d}$.

(3) From (1), we have $\text{Lasso}_*(\lambda) \le \widetilde{\text{PosLasso}}(\lambda)$. Further, if $z$ is a minimizer of $\text{Lasso}(., \lambda)$ over $\mathbb{R}^d$, then

$$
\text{Lasso}_*(\lambda) = \text{Lasso}(z, \lambda) = \widetilde{\text{Lasso}}((z_+, z_-), \lambda) \ge \widetilde{\text{PosLasso}}(\lambda).
$$

This proves the equality.

<figure><img src="image_5.png" /></figure>

5.1.2 Reduction of dynamics in the u ◦ v case to the u ◦ u case

Recall that the dynamics in the $u \circ v$ case are defined by

$$
\frac{du}{dt} = -\nabla_u (\ell(u \circ v)) = -v \circ \nabla \ell(u \circ v),
$$

$$
\frac{dv}{dt} = -\nabla_v (\ell(u \circ v)) = -u \circ \nabla \ell(u \circ v).
$$

Consider

$$
p^{\text{pos}} = \frac{1}{2}(u + v),
$$

$$
p^{\text{neg}} = \frac{1}{2}(u - v).
$$

Then

$$
u \circ v = (p^{\text{pos}})^2 - (p^{\text{neg}})^2.
$$

Define $\tilde{t} = \frac{t}{2}$. Then

$$
\begin{align*}
\frac{\mathrm{d}p^{\mathrm{pos}}}{\mathrm{d}\tilde{t}} &= \frac{\mathrm{d}t}{\mathrm{d}\tilde{t}} \frac{1}{2} \left( \frac{\mathrm{d}u}{\mathrm{d}t} + \frac{\mathrm{d}v}{\mathrm{d}t} \right) = \frac{\mathrm{d}u}{\mathrm{d}t} + \frac{\mathrm{d}v}{\mathrm{d}t} = -v \circ \nabla \ell(u \circ v) - u \circ \nabla \ell(u \circ v) \\
&= -2p^{\mathrm{pos}} \circ \nabla \ell((p^{\mathrm{pos}})^2 - (p^{\mathrm{neg}})^2) = -2p^{\mathrm{pos}} \circ \nabla_{y^{\mathrm{pos}}} \tilde{\ell}((p^{\mathrm{pos}})^2, (p^{\mathrm{neg}})^2) \\
&= -\nabla_{p^{\mathrm{pos}}} (\tilde{\ell}((p^{\mathrm{pos}})^2, (p^{\mathrm{neg}})^2)).
\end{align*}
$$
Similarly,

$$ \frac{dp^{\text{neg}}}{dt} = -\nabla_{p^{\text{neg}}} (\tilde{\ell}((p^{\text{pos}})^2, (p^{\text{neg}})^2)). $$

Thus we obtain

$$ \frac{d}{dt} \left( \begin{pmatrix} p^{\text{pos}} \\ p^{\text{neg}} \end{pmatrix} \right) = - \nabla_{(p^{\text{pos}}, p^{\text{neg}})} \left( \tilde{\ell} \left( \left( \begin{pmatrix} p^{\text{pos}} \\ p^{\text{neg}} \end{pmatrix} \right)^2 \right) \right). $$

This is an equation of the form (3.1) in the $u \circ u$ case. As a consequence, we have reduced a gradient flow on $\ell$ in the $u \circ v$ case to a gradient flow on $\tilde{\ell}$ in the $u \circ u$ case.

## 5.2 Proofs

The proofs of Thms. 2.1 and 2.2 are provided by reductions to Thms. 3.1 and 3.2 respectively.

In each theorem, we are provided a minimizer $x(s)$ of Lasso $(., \frac{1}{s})$ over $\mathbb{R}^d$. By Lemma 5.1(2), $(x_+(s), x_-(s))$ minimizes $\widetilde{\text{Lasso}}(., \frac{1}{s})$ over $\mathbb{R}^{2d}$. This minimizer of the positive lasso will be used in applying Thms 3.1 and 3.2.

Further, we use the reduction of Sec. 5.1.2 from the $u \circ v$ case to the $u^2$ case. We keep the same notations in this section, but now denote the dependence in $\varepsilon$ of the solutions. Thus, with $\tilde{t} = \frac{t}{2}$, we have

$$ \frac{d}{dt} \left( \begin{pmatrix} p^{\text{pos},\varepsilon} \\ p^{\text{neg},\varepsilon} \end{pmatrix} \right) = - \nabla_{(p^{\text{pos},\varepsilon}, p^{\text{neg},\varepsilon})} \left( \tilde{\ell} \left( \left( \begin{pmatrix} p^{\text{pos},\varepsilon} \\ p^{\text{neg},\varepsilon} \end{pmatrix} \right)^2 \right) \right). $$

Again, this is an equation of the form (3.1) in the $u^2$ case.

Denote $\begin{pmatrix} y^{\text{pos},\varepsilon} \\ y^{\text{neg},\varepsilon} \end{pmatrix} = \begin{pmatrix} p^{\text{pos},\varepsilon} \\ p^{\text{neg},\varepsilon} \end{pmatrix}^2$ and $\begin{pmatrix} \bar{y}^{\text{pos},\varepsilon} \\ \bar{y}^{\text{neg},\varepsilon} \end{pmatrix}$ its time-average. The application of Thms. 3.1 and 3.2 describe the performance of $\begin{pmatrix} \bar{y}^{\text{pos},\varepsilon} \\ \bar{y}^{\text{neg},\varepsilon} \end{pmatrix}$ in the minimization of the positive lasso objective $\widetilde{\text{Lasso}}(., \frac{1}{s})$, where $\tilde{s}$ is defined in coherence with Eq. (3.4):

$$ \tilde{s} = \frac{4}{\log \frac{1}{\varepsilon}} \tilde{t} = \frac{2}{\log \frac{1}{\varepsilon}} t \quad (\text{Eq. (2.3)}) \quad s. $$

### 5.2.1 Proof of Theorem 2.1

In Thm. 2.1, it is assumed that $s \mapsto sx(s)$ is coordinate-wise monotone. As a consequence, $s \mapsto s(x_+(s), x_-(s))$ is coordinate-wise non-decreasing. Thus we can apply Thm. 3.1. We obtain

$$ \widetilde{\text{Lasso}} \left( \begin{pmatrix} \bar{y}^{\text{pos},\varepsilon}(s) \\ \bar{y}^{\text{neg},\varepsilon}(s) \end{pmatrix}, \frac{1}{s} \right) \xrightarrow{\varepsilon \to 0} \widetilde{\text{PosLasso}}_* \left( \frac{1}{s} \right). $$
We recall from Sec. 5.1.2 that $x^\epsilon = u^\epsilon \circ v^\epsilon = (p^{\text{pos},\epsilon})^2 - (p^{\text{neg},\epsilon})^2 = y^{\text{pos},\epsilon} - y^{\text{neg},\epsilon}$.
Thus, using Lemma 5.1(1), (3), we obtain

$$
\begin{align*}
\text{Lasso} \left( \bar{x}^{\epsilon}(s), \frac{1}{s} \right) - \text{Lasso}_{*} \left( \frac{1}{s} \right) &= \text{Lasso} \left( \bar{y}^{\text{pos},\epsilon}(s) - \bar{y}^{\text{neg},\epsilon}(s), \frac{1}{s} \right) - \text{Lasso}_{*} \left( \frac{1}{s} \right) \\
&\le \widetilde{\text{Lasso}} \left( \left( \frac{\bar{y}^{\text{pos},\epsilon}(s)}{\bar{y}^{\text{neg},\epsilon}(s)}, \frac{1}{s} \right) - \widetilde{\text{PosLasso}}_{*} \left( \frac{1}{s} \right) \right) \\
&\xrightarrow{\epsilon \to 0} 0.
\end{align*}
$$

5.2.2 Proof of Theorem 2.2

In Thm. 2.2, it is assumed that $s \mapsto sx(s)$ is absolutely continuous. As a consequence, $s \mapsto s(x_+(s), x_-(s))$ is absolutely continuous. Thus we can apply Thm. 3.2.

Note that the quantity $z^\downarrow(s)$ defined in Eq. (3.5), when $x(s)$ is replaced by $(x_+(s), x_-(s))$, corresponds to the quantity $z^\downarrow(s)$ defined in Eq. (2.4). Thus, applying Thm. 3.2, we obtain

$$
\limsup_{\epsilon \to 0} \widetilde{\text{Lasso}} \left( \left( \frac{\bar{y}^{\text{pos},\epsilon}(s)}{\bar{y}^{\text{neg},\epsilon}(s)}, \frac{1}{s} \right) \right) \le \widetilde{\text{PosLasso}}_{*} \left( \frac{1}{s} \right) + C \left[ \frac{(1+s)^{1/2}}{s} z^{\downarrow}(s)^{1/2} + \frac{1+s}{s^2} z^{\downarrow}(s) \right].
$$

Thus, combining with Lemma 5.1(1), (3), we obtain

$$
\begin{align*}
\limsup_{\epsilon \to 0} \text{Lasso} \left( \bar{x}^{\epsilon}(s), \frac{1}{s} \right) &= \limsup_{\epsilon \to 0} \text{Lasso} \left( \bar{y}^{\text{pos},\epsilon}(s) - \bar{y}^{\text{neg},\epsilon}(s), \frac{1}{s} \right) \\
&\le \limsup_{\epsilon \to 0} \widetilde{\text{Lasso}} \left( \left( \frac{\bar{y}^{\text{pos},\epsilon}(s)}{\bar{y}^{\text{neg},\epsilon}(s)}, \frac{1}{s} \right) \right) \\
&\le \widetilde{\text{PosLasso}}_{*} \left( \frac{1}{s} \right) + C \left[ \frac{(1+s)^{1/2}}{s} z^{\downarrow}(s)^{1/2} + \frac{1+s}{s^2} z^{\downarrow}(s) \right] \\
&\le \text{Lasso}_{*} \left( \frac{1}{s} \right) + C \left[ \frac{(1+s)^{1/2}}{s} z^{\downarrow}(s)^{1/2} + \frac{1+s}{s^2} z^{\downarrow}(s) \right].
\end{align*}
$$

Acknowledgements

The author is grateful to Loucas Pillaud-Vivien for numerous stimulating discus-
sions and for providing valuable insights that have improved the development
of this work. The author also acknowledges support from the ANR and the
Ministère de l'Enseignement Supérieur et de la Recherche.
References

[1] Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. *Advances in Neural Information Processing Systems*, 2019.

[2] Shahar Azulay, Edward Moroshko, Mor Shpigel Nacson, Blake Woodworth, Nathan Srebro, Amir Globerson, and Daniel Soudry. On the implicit bias of initialization shape: Beyond infinitesimal mirror descent. In *International Conference on Machine Learning*, pages 468–477. PMLR, 2021.

[3] Peter Bartlett, Andrea Montanari, and Alexander Rakhlin. Deep learning: a statistical viewpoint. *Acta Numerica*, 30:87–201, 2021.

[4] Raphaël Berthier. Incremental learning in diagonal linear networks. *Journal of Machine Learning Research*, 24(171):1–26, 2023.

[5] Raphaël Berthier. Github repository. https://github.com/raphael-berthier/dln-lasso, 2025.

[6] Stephen Boyd and Lieven Vandenberghe. *Convex Optimization*. Cambridge University Press, 2004.

[7] Sébastien Bubeck. Convex optimization: Algorithms and complexity. *Foundations and Trends in Machine Learning*, 8(3-4):231–357, 2015.

[8] Constantin Carathéodory. Über den variabilitätsbereich der fourier'schen konstanten von positiven harmonischen funktionen. *Rendiconti Del Circolo Matematico di Palermo (1884-1940)*, 32(1):193–217, 1911.

[9] Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In *Conference on Learning Theory*, pages 1305–1338. PMLR, 2020.

[10] Hung-Hsu Chou, Johannes Maly, and Holger Rauhut. More is less: inducing sparsity via overparameterization. *Information and Inference: A Journal of the IMA*, 12(3), 2023.

[11] Richard Cottle. Monotone solutions of the parametric linear complementarity problem. *Mathematical Programming*, 3(1):210–224, 1972.

[12] Richard Cottle. A parametric linear complementarity problem (problem by G. Maier). *SIAM Review*, 15(2):381–384, 1973.

[13] Richard Cottle, Jong-Shi Pang, and Richard E Stone. *The linear complementarity problem*. SIAM, 2009.

[14] Curtis Eaves. The linear complementarity problem. *Management science*, 17(9):612–634, 1971.
[15] Bradley Efron, Trevor Hastie, Iain Johnstone, and Robert Tibshirani. Least angle regression. *The Annals of Statistics*, 32(3):407–499, 2004.

[16] Suriya Gunasekar, Blake Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. *Advances in Neural Information Processing Systems*, 2017.

[17] Jeff HaoChen, Colin Wei, Jason Lee, and Tengyu Ma. Shape matters: Understanding the implicit bias of the noise covariance. In *Conference on Learning Theory*, pages 2315–2357. PMLR, 2021.

[18] Trevor Hastie, Jonathan Taylor, Robert Tibshirani, and Guenther Walther. Forward stagewise regression and the monotone lasso. *Electronic Journal of Statistics*, 1:1–29, 2007.

[19] Trevor Hastie, Robert Tibshirani, and Martin Wainwright. Statistical learning with sparsity. *Monographs on statistics and applied probability*, 2015.

[20] Jiangyuan Li, Thanh Nguyen, Chinmay Hegde, and Ka Wai Wong. Implicit sparse regularization: The impact of depth and early stopping. *Advances in Neural Information Processing Systems*, 2021.

[21] Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in over-parameterized matrix sensing and neural networks with quadratic activations. In *Conference on Learning Theory*, pages 2–47. PMLR, 2018.

[22] Zhiyuan Li, Yuping Luo, and Kaifeng Lyu. Towards resolving the implicit bias of gradient descent for matrix factorization: Greedy low-rank learning. *International Conference on Learning Representations*, 2021.

[23] Zhiyuan Li, Tianhao Wang, Jason Lee, and Sanjeev Arora. Implicit bias of gradient descent on reparametrized models: On equivalence to mirror descent. *Advances in Neural Information Processing Systems*, 2022.

[24] Nimrod Megiddo. On monotonicity in parametric linear complementarity problems. *Mathematical Programming*, 12:60–66, 1977.

[25] Mor Shpigel Nacson, Kavya Ravichandran, Nathan Srebro, and Daniel Soudry. Implicit bias of the step size in linear diagonal neural networks. In *International Conference on Machine Learning*, pages 16270–16295. PMLR, 2022.

[26] Scott Pesme and Nicolas Flammarion. Saddle-to-saddle dynamics in diagonal linear networks. *Advances in Neural Information Processing Systems*, 2023.

[27] Scott Pesme, Loucas Pillaud-Vivien, and Nicolas Flammarion. Implicit bias of SGD for diagonal linear networks: a provable benefit of stochasticity. *Advances in Neural Information Processing Systems*, 2021.
[28] Loucas Pillaud-Vivien, Julien Reygner, and Nicolas Flammarion. Label noise (stochastic) gradient descent implicitly solves the Lasso for quadratic parametrisation. In *Conference on Learning Theory*, pages 2127–2159. PMLR, 2022.

[29] Saharon Rosset, Ji Zhu, and Trevor Hastie. Boosting as a regularized path to a maximum margin classifier. *Journal of Machine Learning Research*, 5(Aug):941–973, 2004.

[30] Ryan Tibshirani. The lasso problem and uniqueness. *Electronic Journal of Statistics*, 7:1456–1490, 2013.

[31] Gal Vardi. On the implicit bias in deep-learning algorithms. *Communications of the ACM*, 66(6):86–93, 2023.

[32] Tomas Vaskevicius, Varun Kanade, and Patrick Rebeschini. Implicit regularization for optimal sparse recovery. *Advances in Neural Information Processing Systems*, 2019.

[33] Blake Woodworth, Suriya Gunasekar, Jason Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrized models. In *Conference on Learning Theory*, pages 3635–3673. PMLR, 2020.

[34] Peng Zhao, Yun Yang, and Qiao-Chu He. High-dimensional linear regression via implicit regularization. *Biometrika*, 109(4):1033–1046, 2022.