# Robust Implicit Regularization via Weight Normalization

Hung-Hsu Chou  Munich Center for Machine Learning, Technical University of
Munich, Germany  Holger Rauhut  Ludwig Maximilian University of Munich,
Germany  Rachel Ward  University of Texas at Austin, USA

###### Abstract

Overparameterized models may have many interpolating solutions; implicit
regularization refers to the hidden preference of a particular optimization
method towards a certain interpolating solution among the many. A by now
established line of work has shown that (stochastic) gradient descent tends to
have an implicit bias towards low rank and/or sparse solutions when used to
train deep linear networks, explaining to some extent why overparameterized
neural network models trained by gradient descent tend to have good
generalization performance in practice. However, existing theory for square-
loss objectives often requires very small initialization of the trainable
weights, which is at odds with the larger scale at which weights are
initialized in practice for faster convergence and better generalization
performance. In this paper, we aim to close this gap by incorporating and
analyzing gradient flow (continuous-time version of gradient descent) with
_weight normalization_ , where the weight vector is reparameterized in terms
of polar coordinates, and gradient flow is applied to the polar coordinates.
By analyzing key invariants of the gradient flow and using Lojasiewicz’s
Theorem, we show that weight normalization also has an implicit bias towards
sparse solutions in the diagonal linear model, but that in contrast to plain
gradient flow, weight normalization enables a robust bias that persists even
if the weights are initialized at practically large scale. Experiments suggest
that the gains in both convergence speed and robustness of the implicit bias
are improved dramatically by using weight normalization in overparameterized
diagonal linear network models.

Keywords —  implicit regularization, weight normalization, gradient descent,
overparameterization, linear neural network, vector factorization, L1
minimization, compressed sensing

###### Contents

  1. 1 Introduction
    1. 1.1 Our contribution and related work
    2. 1.2 Formulation
    3. 1.3 Notation and outline
  2. 2 Main Results
  3. 3 Proofs
    1. 3.1 Basic properties
    2. 3.2 Invariants of the flow
    3. 3.3 Convergence for L=1,2
    4. 3.4 An example of time-dependent learning rate
  4. 4 Experiments
    1. 4.1 Gaussian ground truth
    2. 4.2 Sparse ground truth
    3. 4.3 Sparse ground truth with positive and negative entries
  5. 5 Summary and Discussion

##  1 Introduction

Unlike many classical models such as linear regression or kernel methods,
recent machine learning breakthroughs are often based on overparameterized
models, e.g. neural networks, where the number of data is less than the number
of parameters. To develop theoretical understanding of modern machine
learning, many researchers focus on analyzing the simplified model, the linear
network [2, 9, 15, 19, 26, 27], where the activation function is the identity.
From those studies, a phenomenon known as implicit regularization gradually
emerges from the fog.

Implicit regularization refers to the hidden preference of the learning model,
in contrast to explicit regularization which is explicitly specified in the
training process. In particular, implicit regularization can be found in
vector [35], matrix [3, 7, 14, 20, 26, 27, 31, 36], and tensor [32, 33]
factorization. In these examples, we understand theoretically that gradient
descent (GD) applied to simple overparameterized models exhibits implicit
regularization for sparse/low-rank solutions, i.e. solutions of low
complexity. Therefore, in applications where low complexity is desirable, the
algorithm is guaranteed to perform well.

Yet, many of these theoretical guarantees only hold for GD with small [8, 36]
or infinitesimal [2, 3] initialization, which is not practical because small
initialization leads to slow convergence – in fact, as initialization
decreases, the time required to converge to a small neighborhood of zero
increases. In practice, GD is initialized very differently. For example, a
common setting for neural networks is the Xavier initialization [17], where
the initial weights are normalized independent Gaussian vectors. Such scaling
leads to not only empirical success but also is theoretically justified by the
neural tangent kernel [11, 23].

This gap between implicit bias theory (which requires small initialization)
and practice (where initialization is often not small but normalized)
indicates that the algorithm which has so far been the main focus of study for
implicit bias – (stochastic) gradient descent, or (S)GD – might be too
simplistic compared to the algorithms used in practice to train neural
networks. As the authors in [18, 35] point out, the theoretical limitation
might be due to the choice of loss function, for instance the commonly used
$\ell_{2}$ loss. It was shown that GD on loss functions with exponential
tails, such as exponential, logistic, and sigmoid losses, in general does not
require small initialization. However, the optimization procedure requires
certain notions of normalization, otherwise the iterates are likely to blow
up. Hence it is natural to consider combining normalization with $\ell_{2}$
loss to remove the constraints on initialization.

Indeed, _normalization_ of some form is an important modification to plain
(S)GD used in practice for accelerating convergence and generalization. Batch
normalization [22] and layer normalization [4] are among the most popular
choices, while weight normalization (WN) [34] was one of the earliest proposed
normalization algorithms and represents a simple model for batch
normalization.

In [39], GD with WN was shown to induce implicit bias towards the minimal
$\ell_{2}$-norm solution in a region of initialization in the setting of
overparameterized linear regression. The impact of WN on implicit bias in the
linear regression setting hints that WN might be a fundamental algorithmic
aspect of the implicit bias observed in practice.

Weight normalization re-parameterizes the weight vector in each layer in polar
coordinates,

$\displaystyle{\bf x}=\frac{r}{\|{\bf u}\|_{2}}{\bf u};$ (1)

(S)GD is then implemented separately with respect to the vector ${\bf u}$ and
magnitude scalar $r$. While overwhelming empirical evidence shows that weight
normalization induces faster convergence of (S)GD towards solutions with
better generalization performance, rigorous theoretical proofs of these
effects have remained challenging due to the nonlinearity introduced in (1).

It is then natural to study GD with WN, and in particular to hope that WN can
induce a more robust implicit bias towards low-complexity solutions. To be
concise, we will be analyzing gradient flow (GF), the continuous-time version
of gradient descent, in the following context. There are works establishing
connections between GD and GF, e.g. [7, 28], which show that for sufficiently
small step-size, GD and GF exhibit similar behaviours.

###  1.1 Our contribution and related work

In this paper, we show that GF with WN, when applied to the standard diagonal
linear model for vector/matrix factorization, achieves implicit
bias/regularization towards sparse solutions without small initialization. In
short, we show that

_Weight normalization provably induces a robust implicit bias/regularization._

The implicit bias/regularization is robust in the sense that it does not
depend on the initialization as much as many other works suggested [2, 3, 8,
36].

Previous papers have analyzed implicit bias induced by normalization. In the
context of classification using multilayer linear neural networks, [25] and
[30] analyzed gradient flow with WN. These papers do not study the
relationship between robustness of initialization and implicit bias because in
the context of classification, even plain GF without normalization exhibits an
implicit bias to max-margin (min $\ell_{2}$-norm) solutions independent of
initialization.

In [40] the authors established a connection between adaptive GF and WN and
provided robust convergence guarantees for weight-normalized GF. [22] extended
these convergence guarantees to batch normalization. The papers [12, 41]
provided linear convergence of normalized GF methods in the setting of
multilayer ReLU networks in the neural tangent kernel regime.

[39] showed that gradient flow with respect to WN induces robust implicit bias
towards the minimal $\ell_{2}$ norm solution, in the radius $r_{0}<r^{*}$
where $r^{*}$ is the magnitude of the minimal $\ell_{2}$ norm solution.

Our work extends the results from [39], proving that _WN induces robust
implicit bias in a family of overparameterized diagonal linear network models
of arbitrary depth_ , which includes overparameterized least squares as the
base model. The loss corresponding to such family takes the form

$\Big{\|}{\bf A}\big{(}{\bf x}^{(1)}\odot\cdots\odot{\bf x}^{(L)}\big{)}-{\bf
b}\Big{\|}_{2}^{2}$ (2)

where $\odot$ is the entry-wise product. It is shown in [8] that GF on (2)
under identical initialization is equivalent to GF on

$\Big{\|}{\bf A}{\bf x}^{\odot L}-{\bf b}\Big{\|}_{2}^{2}.$ (3)

On the other hand, [39] showed that applying WN (1) to overparameterized
linear regression induces implicit regularization towards minimal $\ell_{2}$
norm, that is, GF on the loss

$\displaystyle\Big{\|}{\bf A}\Big{(}\frac{r}{\|{\bf u}\|_{2}}{\bf
u}\Big{)}-{\bf b}\Big{\|}_{2}^{2}$ (4)

converges to the limit such that

$\lim_{t\to\infty}r(t){\bf u}(t)\approx\operatorname*{arg\,min}_{{\bf A}{\bf
z}={\bf b}}\|{\bf z}\|_{2}.$ (5)

In this paper we generalize the proof strategy in [39] to obtain a robust
$\ell_{1}$-minimization solver, precisely by showing that for $L\geq 2$, GF on
the loss function (where $\odot$ denotes the entry-wise product/power)

$\displaystyle\Big{\|}{\bf A}\Big{(}\frac{r}{\|{\bf u}\|_{2}}{\bf
u}\Big{)}^{\odot L}-{\bf b}\Big{\|}_{2}^{2}$ (6)

converges to the limit such that

$\lim_{t\to\infty}(r(t){\bf u}(t))^{\odot
L}\approx\operatorname*{arg\,min}_{{\bf A}{\bf z}={\bf b}}\|{\bf z}\|_{1}.$
(7)

Although the implicit bias towards minimal $\ell_{1}$-norm solution has been
studied in many works , e.g. [15, 29], _our method does not necessarily
require small initialization_ , which opens the possibility in understanding
networks trained with larger initialization.

(a) Weight normalization significantly decreases the error compared to
gradient descent, especially from larger-scale initialization of the weights.

(b) WN enables algorithms to have small error even without small
initialization.

Figure 1: WN converges to minimal $\ell_{1}$-norm solutions from a wider range
of initialization, and hence is more robust in the sense that it is not
sensitive to the choice of initialization. This suggests that GF with WN could
be used as an efficient alternative for $\ell_{1}$-minimization. Each data
point in Figure 1(a) is an average over ten random initializations at fixed
scale. In Figure 1(a), the plotted errors are after a fixed common number of
iterations of GF with and without WN, so larger error indicates a combination
of larger final error and slower convergence.

Our work also builds on a long line of work on the factorized linear
multilayer model [21, 24, 37, 38, 42, 43]. To precisely quantify the error
coming from the approximation “$\approx$” in (5), we seek inspiration from
[8], where the authors showed that for $L\geq 2$, GF on the loss (3) converges
to the limit whose $\ell_{1}$-norm is almost minimized in the following sense.
Let $\tilde{{\bf x}}={\bf x}^{\odot L}$. Then the limit $\tilde{{\bf
x}}_{\infty}:=\lim_{t\to\infty}\tilde{{\bf x}}(t)$ satisfies ${\bf
A}\tilde{{\bf x}}_{\infty}={\bf b}$ and

$\|\tilde{{\bf x}}_{\infty}\|_{1}-\min_{{\bf A}{\bf z}={\bf b}}\|{\bf
z}\|_{1}\leq\varepsilon(\|\tilde{{\bf x}}_{0}\|_{1})\cdot\min_{{\bf A}{\bf
z}={\bf b}}\|{\bf z}\|_{1}$ (8)

where $\tilde{{\bf x}}_{0}=\tilde{{\bf x}}(0)$ and
$\varepsilon:\mathbb{R}\to\mathbb{R}$ is an increasing function (which we will
later used and specified) with $\varepsilon(0)=0$. In general, we need
$\|\tilde{{\bf x}}_{0}\|_{1}\ll 1$ to have $\varepsilon(\|\tilde{{\bf
x}}_{0}\|_{1})\ll 1$. This often implies that if the initialization is on the
unit sphere, the error $\varepsilon$ is simply too large for (8) to be useful
at all.

Fortunately, this problem disappears when we incorporate normalization as in
(6). In Theorem 2.2, we show that the error bound can be improved to

$\|\tilde{{\bf x}}_{\infty}\|_{1}-\min_{{\bf A}{\bf z}={\bf b}}\|{\bf
z}\|_{1}\leq\varepsilon(\rho^{-L}\|\tilde{{\bf x}}_{0}\|_{1})\cdot\min_{{\bf
A}{\bf z}={\bf b}}\|{\bf z}\|_{1}$ (9)

for some $\rho\geq 1$ that increases as ${\bf x}_{0}$ decreases (the explicit
dependence will be later stated in (18)). As a consequence, the right hand
side remains small even for moderately small initialization such as the
normalized Gaussian vector, which often leads to smaller generalization error
[11, 23].

###  1.2 Formulation

We now introduce the two main models, gradient flow without normalization and
gradient flow with normalization, and a key parameter ${\tilde{\eta}}$, which
we call the learning rate ratio. They are defined as follows. Let ${\bf
A}\in\mathbb{R}^{M\times N}$ and ${\bf b}\in\mathbb{R}^{M}$ be given. Let
$L\in\mathbb{N}$ and consider the following loss function:

$\displaystyle\mathcal{L}({\bf x})$ $\displaystyle=\frac{1}{2L}\|{\bf A}{\bf
x}^{\odot L}-{\bf b}\|_{2}^{2}.$ (10)

We say that ${\bf x}(t)$ follows the gradient flow (without WN) if

$\displaystyle\partial_{t}{\bf x}$ $\displaystyle=-\nabla\mathcal{L}({\bf
x}),\quad{\bf x}(0)={\bf x}_{0}.$ (11)

This is the setting of many previous works on implicit bias in
overparameterized models. In this paper, we define the loss function with WN
as

$\displaystyle\widetilde{\mathcal{L}}(r,{\bf u})$
$\displaystyle=\mathcal{L}\left(\frac{r}{\|{\bf u}\|_{2}}{\bf u}\right)$ (12)

for $r\in\mathbb{R}$ and ${\bf u}\in\mathbb{R}^{N}$. We say that $(r(t),{\bf
u}(t))$ follows the gradient flow with WN if

$\displaystyle\partial_{t}r$
$\displaystyle=-\eta_{r}\nabla_{r}\widetilde{\mathcal{L}}(r,{\bf u}),\quad
r(0)=r_{0}$ (13) $\displaystyle\partial_{t}{\bf u}$ $\displaystyle=-\eta_{\bf
u}\nabla_{{\bf u}}\widetilde{\mathcal{L}}(r,{\bf u}),\quad{\bf u}(0)={\bf
u}_{0}$ (14)

where $\eta_{r},\eta_{\bf u}>0$ are the learning rates for the respective
parameters. We can always assume $\eta_{\bf u}=1$ without loss of generality
(by Lemma 3.1 below). Unless otherwise specified, the default setting in this
paper is that $\eta_{r}$ equals to some positive time-independent constant
${\tilde{\eta}}$. We call this constant the learning rate ratio. The choice of
${\tilde{\eta}}$ is important and will be discussed later on in the remarks
after Theorem 2.2 and Theorem 2.3. Roughly speaking, smaller ${\tilde{\eta}}$
allows us to take larger initialization, but we cannot take it arbitrarily
small because it will cause numerical instability.

###  1.3 Notation and outline

Boldface uppercase letters such as ${\bf A}$ are matrices with entries
$A_{mn}$, boldface lowercase letters such as ${\bf u}$ are vectors with
entries $u_{n}$, and non-boldface letters are scalars. The pseudo-inverse of
${\bf A}$ is denoted by ${\bf A}^{\dagger}$. The transpose of ${\bf A}$ and
${\bf u}$ are denoted by ${\bf A}^{\top}$ and ${\bf u}^{\top}$. Orthogonal
projection matrices are defined as $\mathcal{P}_{{\bf A}}:={\bf
A}^{\dagger}{\bf A}$ and $\mathcal{P}_{{\bf u}}:=\frac{{\bf u}{\bf
u}^{\top}}{\|{\bf u}\|_{2}^{2}}$. Entry-wise products/powers are denoted with
$\odot$, and inequalities between vectors and number are understood as entry-
wise inequality, e.g. ${\bf u}\geq 0$ means $u_{n}\geq 0$ for all $n$.
Similarly, $\log({\bf u})$ is a vector whose entries are $\log(u_{n})$, and
the vector $\mathbf{1}$ and $\mathbf{0}$ are vectors of ones and zeros,
respectively. We denote the set of non-negative real numbers as
$\mathbb{R}_{+}$, and similarly the non-negative solution space as
$S_{+}:=\\{{\bf z}\geq 0:{\bf A}{\bf z}={\bf b}\\}$. We also denote the
weighted $\ell_{1}$-norm of ${\bf z}$ with weight ${\bf w}$ by $\|{\bf
z}\|_{{\bf w},1}:=\|{\bf w}\odot{\bf z}\|_{1}$.

We state our main theorems in Section 2. The main proofs are given in Section
3. We demonstrate our numerical results in Section 4, and provide a summary
and discussion in Section 5.

##  2 Main Results

Our main contribution is summarized in Theorem 2.2. In general, the strength
of implicit regularization increases as the (magnitude of) initialization
decreases. Therefore many works focus on small [8, 36] or infinitesimal [2, 3]
initialization. However, small initialization causes not only numerical
instability, but also slow convergence rate. Hence, there is a strong
incentive to avoid small initialization.

The core idea is to magnify the implicit regularization via an appropriate
learning rate ratio to obtain small error without small initialization
$r_{0}$. For instance, we will see that in the setting of Theorem 2.2, the
error decreases exponentially with respect to initialization according to
(20), which can be compared to the setting of [8] where the error only
decreases polynomially according to (8).

######  Theorem 2.1 (Theorem 2.1 from [8]).

Let $L\geq 2$, ${\bf A}\in\mathbb{R}^{M\times N}$ and ${\bf
b}\in\mathbb{R}^{M}$ and assume that $S_{+}$ is non-empty. Suppose ${\bf x}$
follows the dynamics (11) with ${\bf x}_{0}>0$. Let $\tilde{{\bf x}}={\bf
x}^{\odot L}$.Then the limit $\tilde{{\bf
x}}_{\infty}:=\lim_{t\to\infty}\tilde{{\bf x}}(t)$ exists and $\tilde{{\bf
x}}_{\infty}\in S_{+}$. Moreover, consider $\gamma=1-\frac{2}{L}\in[0,1]$ and

$\displaystyle{\bf w}=\tilde{{\bf
x}}(0)^{\odot\frac{2}{L}-1},\quad{Q}:=\min_{{\bf z}\in S_{+}}\|{\bf z}\|_{{\bf
w},1},\quad\beta_{1}=\|\tilde{{\bf x}}(0)\|_{{\bf
w},1},\quad\beta_{\min}=\min_{n\in[N]}w_{n}\tilde{x}_{n}(0).$

Suppose ${Q}>c_{L}\beta_{1}^{\frac{2}{L}}$, then

$\|\tilde{{\bf x}}_{\infty}\|_{{\bf w},1}-{Q}\leq\varepsilon{Q},$ (15)

where the constant $c_{L}$ is given by

$c_{L}:=\begin{cases}1&\text{if }L=2,\\\
\left(\frac{L}{2}\right)^{\frac{L}{L-2}}&\text{if }L>2,\end{cases}$ (16)

and the error $\varepsilon$ is defined as

$\displaystyle\varepsilon(\beta_{1},\beta_{\min}):=\begin{cases}\frac{\log(\beta_{1}/\beta_{\min})}{\log({Q}/\beta_{1})}&\text{if
}L=2,\\\\[6.0pt]
\frac{L(\beta_{1}^{\gamma}-\beta_{\min}^{\gamma})}{2{Q}^{\gamma}-L\beta_{1}^{\gamma}}&\text{if
}L>2.\end{cases}$ (17)

We now state our main result.

######  Theorem 2.2 (Magnification of implicit regularization).

Let $L\in\mathbb{N}$, $L\geq 2$, ${\bf A}\in\mathbb{R}^{M\times N}$, ${\bf
b}\in\mathbb{R}^{M}$, $(\eta_{r},\eta_{\bf u})=({\tilde{\eta}},1)$ for some
constant ${\tilde{\eta}}>0$. Suppose $(r,{\bf u})$ follow the dynamics in (13)
and (14) with $r_{0},{\bf u}_{0}>0$ satisfying $\|{\bf u}_{0}\|_{2}=1$ and
$r_{0}\leq\min({\tilde{\eta}}^{1/2},\|{\bf A}^{\dagger}{\bf b}\|_{2}^{1/L})$.
Denote ${\bf x}=\frac{r}{\|{\bf u}\|_{2}}{\bf u}$. Suppose there exists ${\bf
v}>0$ such that ${\bf A}{\bf v}=0$, $S_{+}$ is non-empty, and the limit
$\tilde{{\bf x}}_{\infty}:=\lim_{t\to\infty}{\bf x}(t)^{\odot L}$ exists. Let

$\rho:=\frac{r_{0}}{\|{\bf A}^{\dagger}{\bf
b}\|_{2}^{1/L}}\exp\left(\frac{\|{\bf A}^{\dagger}{\bf
b}\|_{2}^{2/L}-r_{0}^{2}}{2{\tilde{\eta}}}\right),$ (18)

be the magnification factor. Then

  1. 1.

The loss defined in (10) decreases exponentially in time, i.e., for all $t\geq
0$

$\mathcal{L}({\bf x}(t))\leq\mathcal{L}({\bf x}_{0})e^{-ct}$ (19)

for some constant $c>0$. In addition, the limit $\tilde{{\bf x}}_{\infty}$
lies is $S_{+}$.

  2. 2.

It holds that $\rho\geq 1$, and the limit $\tilde{{\bf x}}_{\infty}$ satisfies
(15) with error

$\varepsilon(\rho^{-L}\beta_{1},\rho^{-L}\beta_{\min})$ (20)

as defined in (17).

###### Proof.

See Section 3.2. ∎

Our second main result is that for $L=2$ in particular, we can moreover prove
convergence (rather than assuming it).

######  Theorem 2.3 (Convergence).

In the setting of Theorem 2.2, the limit $\tilde{{\bf
x}}_{\infty}:=\lim_{t\to\infty}\tilde{{\bf x}}(t)$ always exists for $L=2$
(and there is no need to assume that it exists).

###### Proof.

See Section 3.3. ∎

Here are some remarks on the scaling and generalization of Theorem 2.2 and
Theorem 2.3.

  * •

Error reduction due to $\rho$.
Consider the case where $L=2$ and $r_{0}=1$. Let ${Q}=\min_{{\bf z}\in
S_{+}}\|{\bf z}\|_{1}$. If the initialization takes the form $\alpha{\bf 1}$,
then from Theorem 2.2 the error is given by

$\varepsilon(\rho^{-L}\beta_{1},\rho^{-L}\beta_{\min})=\frac{\log(\beta_{1}/\beta_{\min})}{\log(\rho^{L}{Q}/\beta_{1})}.$

Thus we can make the right hand side small by making $\rho$ sufficiently
large. Note that this is impossible without normalization.

  * •

How to choose ${\tilde{\eta}}$ and $r_{0}$.
Since the goal is to make $\rho$ large, we want to set ${\tilde{\eta}}$ small.
However, due to the constraint $r_{0}\leq{\tilde{\eta}}^{1/2}$, small
${\tilde{\eta}}$ will also restrict the range of $r_{0}$ we can choose. Hence
there is a trade-off. Fortunately, since ${\tilde{\eta}}$ contributes an
exponential factor, mildly small ${\tilde{\eta}}$ like $0.1$ is usually
sufficient.

  * •

Assumption on kernel of ${\bf A}$.
One of the assumptions is that the kernel of ${\bf A}\in\mathbb{R}^{M\times
N}$ has non-empty intersection with the positive quadrant. In general, the
number of orthants in $\mathbb{R}^{N}$ intersecting with a random subspace of
dimension $K\geq 1$ is $2\cdot\sum_{i=0}^{K-1}\binom{N-1}{i}$ [10]. In our
setting $K$ is the dimension of the kernel of ${\bf A}$, and it is lower
bounded by $N-M$. Suppose now that ${\bf A}$ is chosen at random such that the
kernel is a random subspace, whose distribution is invariant under rotation.
For instance, this is the case for Gaussian random matrices ${\bf A}$ as often
considered in compressive sensing. Then by symmetry, the probability that it
intersects the positive orthant is given by
$2\sum_{i=0}^{K-1}\binom{N-1}{i}/2^{N}$. Thus our assumption holds with
probability

$p=\frac{1}{2^{N-1}}\cdot\sum_{i=0}^{K-1}\binom{N-1}{i}=1-\frac{1}{2^{N-1}}\cdot\sum_{i=0}^{N-K-1}\binom{N-1}{i}.$

For instance, when $M=1$, $K=N-1$ and hence $p=1-(1/2)^{N-1}$. Furthermore,
when $\lambda:=\frac{N-K-1}{N-1}\leq\frac{1}{2}$ (small number of
measurements) we can lower bound this probability via ([13])

$\displaystyle p\geq 1-2^{-(N-1)(1+H(\lambda))},$

where $H(\lambda)=\lambda\log_{2}\lambda+(1-\lambda)\log_{2}(1-\lambda)$.

  * •

Extension beyond non-negative solutions
A common strategy to extend results from the positive solution set $S_{+}$ to
the full solution set $S:=\\{{\bf z}:{\bf A}{\bf z}={\bf b}\\}$ is to
introduce further parameters. For example, although gradient flow on the loss
function

$\mathcal{L}({\bf x})=\|{\bf A}{\bf x}^{\odot L}-{\bf b}\|_{2}^{2},\quad{\bf
x}_{0}>0$

can only lead to positive solutions, gradient flow on the modified loss
function

$\mathcal{L}_{\pm}({\bf u},{\bf v})=\|{\bf A}({\bf u}^{\odot L}-{\bf v}^{\odot
L})-{\bf b}\|_{2}^{2},\quad{\bf u}_{0},{\bf v}_{0}>0$ (21)

can lead to any solution [8, 16, 38], since ${\bf u}$ takes care of the
positive part and ${\bf v}$ takes care of the negative part. However, our key
lemma (Lemma 3.11), which depends on uniqueness, no longer holds in this
regime. The intuitive reason is that

${\bf u}^{\odot L}-{\bf v}^{\odot L}=({\bf u}^{\odot L}+\zeta)-({\bf v}^{\odot
L}+\zeta)$

for any $\zeta$. In particular, since we cannot assume ${\bf u}$ and ${\bf v}$
have disjoint supports, it is unlikely that we can uniquely define $({\bf
u},{\bf v})$ based on the invariants in Lemma 3.8. Therefore, our analysis
only focuses on the case of positive solution set in this paper. We
nevertheless include some simulation for gradient descent on the modified loss
function (21) in Section 4.3 along with some discussion.

Theorem 2.2 provides the optimal scaling when $\eta_{r}$ is a constant.
Interestingly, an alternative time-dependent step-size choice
$(\eta_{r},\eta_{\bf u})=(r^{2},1)$ provides a different dynamic which is
close to the gradient flow dynamics without weight normalization (11). In this
case, we can prove convergence to the stationary point instead of assuming it
for all $L\geq 2$. Below we state the results for this special case and
encourage readers to explore more possibilities.

######  Theorem 2.4 (A time-dependent learning rate).

Consider the same setting as in Theorem 2.2, except that the learning rates
are given by $(\eta_{r},\eta_{\bf u})=(r^{2},1)$ and here we do not assume the
existence of the limit. If ${\bf b}$ is not identically zero, then the
following holds.

  1. 1.

The limit $\tilde{{\bf x}}_{\infty}:=\lim_{t\to\infty}\tilde{{\bf x}}(t)$
exists and lies in $S_{+}$.

  2. 2.

The limit $\tilde{{\bf x}}_{\infty}$ satisfies (15) with error
$\varepsilon(\beta_{1},\beta_{\min})$ as defined in (17). In other words, it
satisfies the same error bound as in Theorem 2.2 with $\rho=1$ (no
magnification).

###### Proof.

See Section 3.4. ∎

##  3 Proofs

Here is the outline of the proofs. First we prove the basic properties of the
dynamics (13) and (14), including scaling (Lemma 3.1, constant norm (Lemma
3.2), constant sign (Lemma 3.3), and decreasing loss (Lemma 3.5).

We then prove Theorem 2.2 via the comparison (Lemma 3.9) between invariants
without weight normalization (Lemma 3.7) and invariants with weight
normalization (Lemma 3.8), together with the boundedness (Lemma 3.10) and the
uniqueness (Lemma 3.11) of the trajectories.

We further prove Theorem 2.3 based on the additional boundedness (Lemma 3.12)
for $L=1,2$. We prove Theorem 2.4 through a different approach than the
previous parts.

Finally, we analyze the trajectories through dynamic reduction (Lemma 3.14)
and the non-increasing Bregman divergence (Lemma 3.18), which is similar to
the proof in [8].

###  3.1 Basic properties

We first compute all the derivatives that will be used later on. By the chain
rule,

$\displaystyle\nabla\mathcal{L}({\bf x})$ $\displaystyle=[{\bf A}^{\top}({\bf
A}{\bf x}^{\odot L}-{\bf b})]\odot({\bf x}^{\odot L-1}),$ (22)
$\displaystyle\nabla_{r}\widetilde{\mathcal{L}}(r,{\bf u})$
$\displaystyle=\frac{{\bf u}^{\top}}{\|{\bf
u}\|_{2}}\nabla\mathcal{L}\left(\frac{r}{\|{\bf u}\|_{2}}{\bf u}\right),$ (23)
$\displaystyle\nabla_{{\bf u}}\widetilde{\mathcal{L}}(r,{\bf u})$
$\displaystyle=\frac{r}{\|{\bf u}\|_{2}}(I-\mathcal{P}_{{\bf
u}})\nabla\mathcal{L}\left(\frac{r}{\|{\bf u}\|_{2}}{\bf u}\right).$ (24)

We claimed in Section 1.2 that $\eta_{{\bf u}}=1$ can be fixed without loss of
generality. Lemma 3.1 provides the justification: scaling $\eta_{{\bf u}}$ is
equivalent to scaling the magnitude of the initialization ${\bf u}_{0}$, which
is independent of the initialization ${\bf x}_{0}=\frac{r}{\|{\bf
u}\|_{2}}{\bf u}$.

######  Lemma 3.1 (Re-scaled learning rate $\eta_{{\bf u}}$).

Suppose $(r,{\bf u})$ follows (13) and (14) with initialization $(r_{0},{\bf
u}_{0})$ and learning rate $(\eta_{r},\eta_{\bf u})$. Fix ${a}>0$. Suppose
$(r^{({a})},{\bf u}^{({a})})$ follows (13) and (14) with initialization
$(r_{0},{a}{\bf u}_{0})$ and learning rate $(\eta_{r},{a}^{2}\eta_{\bf u})$.
Then $r^{({a})}(t)=r(t)$ and ${\bf u}^{({a})}(t)={a}{\bf u}(t)$ for all $t\geq
0$. As a result,

$\displaystyle\frac{r}{\|{\bf u}\|_{2}}{\bf u}=\frac{r^{({a})}{\bf
u}^{({a})}}{\|{\bf u}^{({a})}\|_{2}}.$

###### Proof.

First note that for

$r^{({a})}=r\quad\text{and}\quad{\bf u}^{({a})}={a}{\bf u}$ (25)

we obtain

$\displaystyle\nabla_{r^{({a})}}\widetilde{\mathcal{L}}(r^{({a})},{\bf
u}^{({a})})$ $\displaystyle=\nabla_{r}\widetilde{\mathcal{L}}(r,{\bf u}),$
$\displaystyle\nabla_{{\bf u}^{({a})}}\widetilde{\mathcal{L}}(r^{({a})},{\bf
u}^{({a})})$ $\displaystyle={a}^{-1}\nabla_{{\bf
u}}\widetilde{\mathcal{L}}(r,{\bf u}).$

Consequentially,

$\displaystyle\partial_{t}r^{({a})}$
$\displaystyle=-\eta_{r}\nabla_{r^{({a})}}\widetilde{\mathcal{L}}(r^{({a})},{\bf
u}^{({a})})=\partial_{t}r,$ (26) $\displaystyle\partial_{t}{\bf u}^{({a})}$
$\displaystyle=-{a}^{2}\eta_{\bf u}\nabla_{{\bf
u}^{({a})}}\widetilde{\mathcal{L}}(r^{({a})},{\bf
u}^{({a})})={a}\partial_{t}{\bf u}.$ (27)

Since (25) holds for $t=0$ and is preserved due to (26) and (27), (25) holds
for all $t\geq 0$. ∎

To avoid division by zero, it is important to have some control over the norm
$\|{\bf u}\|_{2}$. According to the next lemma, $\|{\bf u}\|_{2}$ does not
change in time, and hence it stays positive if it starts positive.

######  Lemma 3.2 (Constant norm).

For all $t\geq 0$, $\|{\bf u}(t)\|_{2}=\|{\bf u}(0)\|_{2}$.

###### Proof.

A direct computation yields

$\displaystyle\partial_{t}\|{\bf u}\|_{2}^{2}$ $\displaystyle=2{\bf
u}^{\top}\partial_{t}{\bf u}=-2{\bf u}^{\top}\nabla_{{\bf
u}}\widetilde{\mathcal{L}}(r,{\bf u})$ $\displaystyle=-2\frac{r}{\|{\bf
u}\|_{2}}{\bf u}^{\top}(I-\mathcal{P}_{{\bf
u}})\nabla\mathcal{L}\left(\frac{r}{\|{\bf u}\|_{2}}{\bf u}\right)=0$

because ${\bf u}^{\top}(I-\mathcal{P}_{{\bf u}})=0$. This implies the claim. ∎

Based on Lemma 3.1 and Lemma 3.2, without loss of generality we set $\|{\bf
u}_{0}\|_{2}=1$ from now on so that $\|{\bf u}(t)\|_{2}=1$ for all $t\geq 0$.

Another important property is that ${\bf u}$ stays non-negative, as stated by
the next lemma. This implies the property that $\langle{\bf
u},\bm{1}\rangle=\|{\bf u}\|_{1}$, which will be useful in the proof of
Theorem 2.2 and Theorem 2.4.

######  Lemma 3.3 (Constant sign).

Let $L\in\mathbb{N}$ and $L\geq 2$. If $r(0)>0$ and ${\bf u}(0)>0$, then
$r(t)>0$ and ${\bf u}(t)>0$ for all $t\geq 0$.

###### Proof.

Note that $\nabla_{r}\widetilde{\mathcal{L}}(r,{\bf u})$ is local Lipschitz
continuous in $r$, and $\nabla_{{\bf u}}\widetilde{\mathcal{L}}(r,{\bf u})$ is
local Lipschitz continuous in ${\bf u}$. Hence by the Picard–Lindelöf theorem
the trajectory is unique. In particular, $\partial_{t}r$ and $u_{n}$ cannot
reach zero at finite time, since this would otherwise contradict to the
uniqueness of the trajectory (if we apply Picard–Lindelöf theorem backward in
time). We now show that $r=0$ implies that $\partial_{t}r=0$ and $u_{n}=0$
implies that $\partial_{t}u_{n}=0$. By (22), (23), and (24), we have

$\displaystyle\partial_{t}r$
$\displaystyle=-\eta_{r}\nabla_{r}\widetilde{\mathcal{L}}(r,{\bf
u})=-\frac{\eta_{r}}{\|{\bf u}\|_{2}}{\bf
u}^{\top}\nabla\mathcal{L}\left(\frac{r}{\|{\bf u}\|_{2}}{\bf u}\right)$ (28)
$\displaystyle\partial_{t}{\bf u}$ $\displaystyle=-\eta_{\bf u}\nabla_{{\bf
u}}\widetilde{\mathcal{L}}(r,{\bf u})=-\eta_{\bf u}\frac{r}{\|{\bf
u}\|_{2}}(I-\mathcal{P}_{{\bf u}})\nabla\mathcal{L}\left(\frac{r}{\|{\bf
u}\|_{2}}{\bf u}\right)$ $\displaystyle=-\eta_{\bf u}\frac{r}{\|{\bf
u}\|_{2}}\nabla\mathcal{L}\left(\frac{r}{\|{\bf u}\|_{2}}{\bf
u}\right)+\eta_{\bf u}\frac{r}{\|{\bf u}\|_{2}^{3}}{\bf u}{\bf
u}^{\top}\nabla\mathcal{L}\left(\frac{r}{\|{\bf u}\|_{2}}{\bf u}\right)$
$\displaystyle=-\eta_{\bf u}\frac{r}{\|{\bf
u}\|_{2}}\nabla\mathcal{L}\left(\frac{r}{\|{\bf u}\|_{2}}{\bf
u}\right)-\eta_{\bf u}\frac{r\partial_{t}r}{\eta_{r}\|{\bf u}\|_{2}^{2}}{\bf
u}.$ (29)

If $r=0$, then $\nabla\mathcal{L}=0$ and hence $\partial_{t}r=0$. If
$u_{n}=0$, then $[\nabla\mathcal{L}]_{n}=0$ and hence $\partial_{t}u_{n}=0$.
Since $\partial_{t}r$ and $u_{n}$ cannot reach zero at finite time, $r$ and
$u_{n}$ cannot reach zero either. By continuity, the signs of $r$ and $u_{n}$
will stay constant. ∎

######  Remark 3.4.

Note that although Lemma 3.3 shows that the ${\bf u}(t)>0$ for all $t\geq 0$,
it does not guarantee that its limit is strictly positive. Hence later on
while discussing the limit we will need some slightly stronger results (Lemma
3.10 and the Lemma 3.11).

We now examine the dynamics of the loss, which is non-increasing in time.

######  Lemma 3.5 (Non-increasing loss).

If $(r,{\bf u})$ follows (13) and (14), then the loss
$\widetilde{\mathcal{L}}(r,{\bf u})$ is non-increasing in time, i.e.
$\partial_{t}\widetilde{\mathcal{L}}(r,{\bf u})\leq 0$.

###### Proof.

By chain rule we have

$\displaystyle\partial_{t}\widetilde{\mathcal{L}}(r,{\bf u})$
$\displaystyle=\left\langle\nabla_{r}\widetilde{\mathcal{L}}(r,{\bf
u})\,,\,\partial_{t}r\right\rangle+\left\langle\nabla_{{\bf
u}}\widetilde{\mathcal{L}}(r,{\bf u})\,,\,\partial_{t}{\bf u}\right\rangle$
$\displaystyle=-\eta_{r}\|\nabla_{r}\widetilde{\mathcal{L}}(r,{\bf
u})\|_{2}^{2}-\eta_{\bf u}\|\nabla_{{\bf u}}\widetilde{\mathcal{L}}(r,{\bf
u})\|_{2}^{2}\leq 0.$

This completes the proof. ∎

We can even derive the convergence rate under the assumption that some entries
are uniformly lower bounded, which in fact holds if the trajectory is upper
bounded, as we will later on prove in Lemma 3.10 in Section 3.2.

######  Lemma 3.6 (Convergence rate).

Let ${\bf x}=\frac{r}{\|{\bf u}\|_{2}}{\bf u}$ and $(r,{\bf u})$ follows (13)
and (14) with $\|{\bf u}_{0}\|_{2}^{2}=1$. Let $t_{0}\geq 0$. Suppose there
exists constant $c_{r},c_{\bf u},c_{\bf x}>0$ such that $\eta_{r}\geq c_{r}$,
$\eta_{\bf u}\geq c_{\bf u}$, and $|{\bf x}_{I}|\geq c_{\bf x}$ for all
$t\in[t_{0},T]$, for some index set $I\subset[N]$. Denote ${\bf A}_{I}$ to be
the sub-matrix of ${\bf A}$ with columns indexed by $I$. If ${\bf A}_{I}$ has
full rank, then for all $t\geq t_{0}$,

$\mathcal{L}({\bf x}(t))\leq\mathcal{L}({\bf
x}(t_{0}))\exp\left(-\min\left(c_{r},c_{\bf u}c_{\bf x}^{2}|I|\right)2Lc_{\bf
x}^{2}\sigma_{\min}^{2}({\bf A}|_{I})(t-t_{0})\right)$ (30)

for all $t\in[0,T]$, where $\sigma_{\min}({\bf A}|_{I})$ is the smallest
singular value of ${\bf A}|_{I}$.

###### Proof.

By Lemma 3.2, $\|{\bf u}\|_{2}=\|{\bf u}_{0}\|_{2}=1$. By Lemma 3.5, we have

$\partial_{t}\widetilde{\mathcal{L}}(r,{\bf
u})=-\eta_{r}\|\nabla_{r}\widetilde{\mathcal{L}}(r,{\bf
u})\|_{2}^{2}-\eta_{\bf u}\|\nabla_{{\bf u}}\widetilde{\mathcal{L}}(r,{\bf
u})\|_{2}^{2}.$

Note that by (23) and (24),

$\displaystyle-\eta_{r}\|\nabla_{r}\widetilde{\mathcal{L}}(r,{\bf
u})\|_{2}^{2}-\eta_{\bf u}\|\nabla_{{\bf u}}\widetilde{\mathcal{L}}(r,{\bf
u})\|_{2}^{2}$ $\displaystyle=-\nabla\mathcal{L}({\bf
x})^{\top}\left(\eta_{r}\mathcal{P}_{{\bf u}}+\eta_{\bf
u}r^{2}(I-\mathcal{P}_{{\bf u}})\right)\nabla\mathcal{L}({\bf x})$
$\displaystyle\leq-\min\left(\eta_{r},\eta_{\bf
u}r^{2}\right)\|\nabla\mathcal{L}({\bf x})\|_{2}^{2}.$

Suppose that there exist constant $c_{r},c_{\bf u},c_{\bf x}>0$ such that
$\eta_{r}\geq c_{r}$, $\eta_{\bf u}\geq c_{\bf u}$, and $|{\bf x}|\geq c_{\bf
x}$ for all $t\in[t_{0},T]$, then $r^{2}=\|{\bf x}\|_{2}^{2}\geq|I|\cdot
c_{\bf x}^{2}$ and hence

$\displaystyle\min\left(\eta_{r},\eta_{\bf u}r^{2}\right)$
$\displaystyle\geq\min\left(c_{r},c_{\bf u}|I|\cdot c_{\bf x}^{2}\right).$

On the other hand,

$\displaystyle\left\|\nabla\mathcal{L}\left({\bf x}\right)\right\|_{2}^{2}$
$\displaystyle\geq c_{\bf x}^{2L-2}\|{\bf A}|_{I}^{\top}({\bf A}{\bf x}^{\odot
L}-{\bf b})\|_{2}^{2}$ $\displaystyle\geq c_{\bf
x}^{2L-2}\sigma_{\min}^{2}({\bf A}|_{I})\|{\bf A}{\bf x}^{\odot L}-{\bf
b}\|_{2}^{2}=2Lc_{\bf x}^{2L-2}\sigma_{\min}^{2}({\bf A}|_{I})\mathcal{L}({\bf
x}).$

Putting together the estimates, we obtain

$\displaystyle\partial_{t}\mathcal{L}({\bf x})\leq-\min\left(c_{r},|I|c_{\bf
u}c_{\bf x}^{2}\right)2Lc_{\bf x}^{2L-2}\sigma_{\min}^{2}({\bf
A}|_{I})\mathcal{L}({\bf x}).$

By Gronwall’s inequality we get the linear convergence rate

$\displaystyle\mathcal{L}({\bf x}(t))\leq\mathcal{L}({\bf
x}(t_{0}))\exp\left(-\min\left(c_{r},|I|c_{\bf u}c_{\bf x}^{2}\right)2Lc_{\bf
x}^{2L-2}\sigma_{\min}^{2}({\bf A}|_{I})(t-t_{0})\right).$

This completes the proof. ∎

###  3.2 Invariants of the flow

We first derive some statements regarding invariants and uniqueness, and then
present the proof of Theorem 2.2. The first step is to compare the invariants
for the cases with and without normalization. We will see that they take
similar form, but differ by an exponential factor.

######  Lemma 3.7 (Invariant, without normalization).

Let $L\in\mathbb{N}$. Suppose ${\bf x}$ follows the dynamics in (11). Then the
quantity

$h_{0}(t):=\left(I-{\bf A}^{\dagger}{\bf A}\right)\cdot\begin{cases}\log({\bf
x}(t))&\text{if }L=2\\\ {\bf x}(t)^{\odot 2-L}&\text{if }L\neq 2\end{cases}$
(31)

is the same for all $t\geq 0$, where ${\bf A}^{\dagger}$ is the pseudoinverse
of ${\bf A}$.

###### Proof.

Note that $(I-\mathcal{P}_{{\bf A}}){\bf A}^{\top}=0$. It suffices to show
that $\partial_{t}h_{0}=0$. By direct computation we have

$\displaystyle\partial_{t}h_{0}$ $\displaystyle=(I-\mathcal{P}_{{\bf
A}})\,c({\bf x}^{\odot 1-L}\odot\partial_{t}{\bf x})$
$\displaystyle=-c(I-\mathcal{P}_{{\bf A}})\,({\bf x}^{\odot 1-L}\odot[{\bf
A}^{\top}({\bf A}{\bf x}^{\odot L}-{\bf b})]\odot{\bf x}^{\odot L-1})$
$\displaystyle=-c(I-\mathcal{P}_{{\bf A}}){\bf A}^{\top}({\bf A}{\bf x}^{\odot
L}-{\bf b})=0$

where $c=1$ if $L=2$, and $c=2-L$ otherwise. Thus $h_{0}$ remains constant for
all $t\geq 0$. ∎

######  Lemma 3.8 (Invariant, with normalization).

Let $L\in\mathbb{N}$, ${\tilde{\eta}}>0$, and $(\eta_{r},\eta_{\bf
u})=({\tilde{\eta}},1)$. Suppose $r,{\bf u}$ follow the dynamics in (13) and
(14) with $\|{\bf u}_{0}\|_{2}=1$. Then the quantity

$h_{\tilde{\eta}}(t):=(I-{\bf A}^{\dagger}{\bf
A})\cdot\begin{cases}\log\left({\bf
u}(t)\exp\left(\frac{1}{2{\tilde{\eta}}}r(t)^{2}\right)\right)&\text{if
}L=2\\\ {\bf u}(t)^{\odot
2-L}\exp\left(\frac{2-L}{2{\tilde{\eta}}}r(t)^{2}\right)&\text{if }L\neq
2\end{cases}$ (32)

remains constant for all $t\geq 0$, where ${\bf A}^{\dagger}$ is the
pseudoinverse of ${\bf A}$.

###### Proof.

Since $\|{\bf u}_{0}\|_{2}=1$, by Lemma 3.2 $\|{\bf u}(t)\|_{2}=1$ for all
$t\geq 0$. By substituting $\eta_{r}={\tilde{\eta}}$, $\eta_{\bf u}=1$, and
$\|{\bf u}\|_{2}=1$ into the dynamics (29), we obtain

$\displaystyle\partial_{t}{\bf u}=-r\nabla\mathcal{L}\left(r{\bf
u}\right)-\frac{r}{{\tilde{\eta}}}{\bf
u}\partial_{t}r=-r\nabla\mathcal{L}\left(r{\bf
u}\right)-\frac{1}{2{\tilde{\eta}}}\partial_{t}(r^{2}){\bf u}.$ (33)

Since

$(I-\mathcal{P}_{{\bf A}})\left({\bf u}^{\odot
1-L}\odot\nabla\mathcal{L}\left(r{\bf u}\right)\right)=(I-\mathcal{P}_{{\bf
A}})\left({\bf A}^{\top}\left({\bf A}\left(r{\bf u}\right)^{\odot L}-{\bf
b}\right)r^{L-1}\right)=0,$ (34)

by applying the operation $(I-\mathcal{P}_{{\bf A}})[{\bf u}^{\odot
1-L}\odot\,\cdot\,]$ to (33) we have

$\displaystyle(I-\mathcal{P}_{{\bf A}})({\bf u}^{\odot
1-L}\odot\partial_{t}{\bf
u})=-\frac{1}{2{\tilde{\eta}}}\partial_{t}(r^{2})(I-\mathcal{P}_{{\bf A}}){\bf
u}^{\odot 2-L}.$ (35)

Let us now separate the case of $L=2$ from $L>2$.

For $L=2$, since ${\bf u}^{\odot-1}\odot\partial_{t}{\bf
u}=\partial_{t}\log({\bf u})$, (35) can be expressed as

$(I-\mathcal{P}_{{\bf A}})\partial_{t}\log({\bf
u})=-\frac{1}{2{\tilde{\eta}}}\partial_{t}(r^{2})(I-\mathcal{P}_{{\bf
A}})\bm{1},$

which is a separable differential equation whose solution (via integration
from $0$ to $t$) satisfies

$(I-\mathcal{P}_{{\bf A}})(\log({\bf u})-\log({\bf
u}_{0}))=-\frac{1}{2{\tilde{\eta}}}(r^{2}-r_{0}^{2})\cdot(I-\mathcal{P}_{{\bf
A}})\bm{1}.$

Rearranging terms we obtain

$(I-\mathcal{P}_{{\bf A}})\left(\log({\bf
u})+\frac{r^{2}}{2{\tilde{\eta}}}\bm{1}\right)=(I-\mathcal{P}_{{\bf
A}})\left(\log({\bf u}_{0})+\frac{r_{0}^{2}}{2{\tilde{\eta}}}\bm{1}\right).$
(36)

Note that we can combine terms by noting that

$\displaystyle\log({\bf u})+\frac{r^{2}}{2{\tilde{\eta}}}\bm{1}=\log({\bf
u})+\log\left(\exp\left(\frac{r^{2}}{2{\tilde{\eta}}}\bm{1}\right)\right)=\log\left({\bf
u}\cdot\exp\left(\frac{r^{2}}{2{\tilde{\eta}}}\right)\right)$

For $L\neq 2$ the left hand side of (35) can be written as
$\frac{1}{2-L}\partial_{t}(I-\mathcal{P}_{{\bf A}}){\bf u}^{\odot 2-L}$. Let
$\widetilde{{\bf u}}=(I-\mathcal{P}_{{\bf A}}){\bf u}^{\odot 2-L}$. Then we
have that

$\displaystyle\partial_{t}(\widetilde{{\bf
u}})=-\frac{2-L}{2{\tilde{\eta}}}\partial_{t}(r^{2})\cdot\widetilde{{\bf u}}.$

Multiplying both sides by $\odot\widetilde{{\bf u}}^{-1}$ and again using the
fact that $\widetilde{{\bf u}}^{\odot-1}\odot\partial_{t}\widetilde{{\bf
u}}=\partial_{t}\log(\widetilde{{\bf u}})$, we have

$\partial_{t}(\log(\widetilde{{\bf
u}}))=\frac{L-2}{2{\tilde{\eta}}}\partial_{t}(r^{2})\cdot\bm{1},$

which is a separable differential equation whose solution (via integration
from $0$ to $t$) satisfies

$\log(\widetilde{{\bf u}})-\log(\widetilde{{\bf
u}}_{0})=\frac{L-2}{2{\tilde{\eta}}}(r^{2}-r_{0}^{2})\cdot{\bf 1}.$

Since $\log(\widetilde{{\bf u}})-\log(\widetilde{{\bf
u}}_{0})=\log(\widetilde{{\bf u}}\odot\widetilde{{\bf u}}_{0}^{\odot-1})$, we
take the exponential on both sides to get

$\widetilde{{\bf u}}\odot\widetilde{{\bf
u}}_{0}^{\odot-1}=\exp\left(\frac{L-2}{2{\tilde{\eta}}}(r^{2}-r_{0}^{2})\right)\cdot{\bf
1},$

which is equivalent to

$\displaystyle\widetilde{{\bf
u}}\cdot\exp\left(\frac{2-L}{2{\tilde{\eta}}}r^{2}\right)=\widetilde{{\bf
u}}_{0}\cdot\exp\left(\frac{2-L}{2{\tilde{\eta}}}r_{0}^{2}\right)$ (37)

and hence the conclusion follows. ∎

Lemma 3.8 is a generalization of Lemma 2.5 in [39], which considered the case
$L=1$ corresponding to linear regression. When $L=1$, this means that the
component $\left(I-{\bf A}^{\dagger}{\bf A}\right){\bf u}$ vanishes as $r$
increases, so that $r_{\infty}{\bf u}_{\infty}\approx{\bf A}^{\dagger}{\bf
b}$. For $L\neq 1$, the geometric interpretation is less intuitive because we
only have the characterization of ${\bf u}^{\odot 2-L}$ instead of ${\bf u}$.

Fortunately, instead of directly analyzing the invariant $h_{\tilde{\eta}}$ in
Lemma 3.8, we can compare it with the invariants $h_{0}$ in Lemma 3.7 and make
an insightful connection, which will be stated in the next lemma.

######  Lemma 3.9 (Invariant comparison).

Let $L\in\mathbb{N}$ and ${\tilde{\eta}}>0$. Suppose ${\bf x}$ follows the
dynamics in (11), and $(r,{\bf u})$ follow the dynamics in (13) and (14) with
$(\eta_{r},\eta_{\bf u})=({\tilde{\eta}},1)$, $r_{0},{\bf u}_{0}>0$, and
$\|{\bf u}_{0}\|_{2}=1$. Denote ${\bf x}_{\text{wn}}=\frac{r}{\|{\bf
u}\|_{2}}{\bf u}$. Suppose $r_{\infty}=\lim_{t\to\infty}r(t)$ exists and not
equal to zero. Then for $L=2$,

$\displaystyle\lim_{t\to\infty}\left(I-\mathcal{P}_{{\bf A}}\right)\log({\bf
x}(t))$ $\displaystyle=\left(I-\mathcal{P}_{{\bf A}}\right)\log({\bf x}(0))$
(38) $\displaystyle\lim_{t\to\infty}\left(I-\mathcal{P}_{{\bf
A}}\right)\log({\bf x}_{\text{wn}}(t))$ $\displaystyle=(I-\mathcal{P}_{{\bf
A}})\log\left(\gamma(r_{0},r_{\infty})\cdot{\bf x}_{\text{wn}}(0)\right)$ (39)

and for $L\neq 2$,

$\displaystyle\lim_{t\to\infty}\left(I-\mathcal{P}_{{\bf A}}\right){\bf
x}^{\odot 2-L}(t)$ $\displaystyle=\left(I-\mathcal{P}_{{\bf A}}\right){\bf
x}^{\odot 2-L}(0)$ (40)
$\displaystyle\lim_{t\to\infty}\left(I-\mathcal{P}_{{\bf A}}\right){\bf
x}_{\text{wn}}^{\odot 2-L}(t)$ $\displaystyle=\left(I-\mathcal{P}_{{\bf
A}}\right)[\,\gamma(r_{0},r_{\infty})\cdot{\bf x}_{\text{wn}}^{\odot
L}(0)]^{\odot 2-L}$ (41)

where the re-scaling factor is given by

$\displaystyle\gamma(r_{0},r)$
$\displaystyle:=\frac{r}{r_{0}}\exp\left(\frac{r_{0}^{2}-r^{2}}{2{\tilde{\eta}}}\right).$
(42)

We only focus on $\lim_{t\to\infty}\left(I-\mathcal{P}_{{\bf
A}}\right)\log({\bf x}(t))$ and not $\left(I-\mathcal{P}_{{\bf
A}}\right)\log(\lim_{t\to\infty}\tilde{{\bf x}}(t))$, because the latter
quantity might not be well-defined if $\lim_{t\to\infty}\tilde{{\bf x}}(t)$
has zero entries.

###### Proof.

For ${\bf x}$, the result directly follows from Lemma 3.7. For ${\bf
x}_{\text{wn}}$, we need to do a bit more calculation. By Lemma 3.2, $\|{\bf
u}(t)\|_{2}=1$ for all $t\geq 0$. Thus ${\bf x}_{\text{wn}}=r{\bf u}$. By
assumption the limit $r_{\infty}$ exists and is strictly positive. By Lemma
3.8, for $L=2$,

$\displaystyle\left(I-\mathcal{P}_{{\bf A}}\right)\log({\bf x}_{\text{wn}})$
$\displaystyle=(I-\mathcal{P}_{{\bf A}})\log(r{\bf u})$
$\displaystyle=(I-\mathcal{P}_{{\bf A}})\log\left({\bf
u}\exp\left(\frac{r^{2}}{2{\tilde{\eta}}}\right)\exp\left(-\frac{r^{2}}{2{\tilde{\eta}}}\right)r\right)$
$\displaystyle=\underbrace{(I-\mathcal{P}_{{\bf A}})\log\left({\bf
u}\exp\left(\frac{r^{2}}{2{\tilde{\eta}}}\right)\right)}_{\text{invariant}}+(I-\mathcal{P}_{{\bf
A}})\bm{1}\log\left(\exp\left(-\frac{r^{2}}{2{\tilde{\eta}}}\right)r\right)$
$\displaystyle=(I-\mathcal{P}_{{\bf A}})\log\left({\bf
u}_{0}\exp\left(\frac{r_{0}^{2}}{2{\tilde{\eta}}}\right)\right)+(I-\mathcal{P}_{{\bf
A}})\bm{1}\log\left(\exp\left(-\frac{r^{2}}{2{\tilde{\eta}}}\right)r\right)$
$\displaystyle=(I-\mathcal{P}_{{\bf A}})\log\bigg{(}\underbrace{r_{0}{\bf
u}_{0}}_{{\bf
x}_{\text{wn}}(0)}\underbrace{\frac{r}{r_{0}}\exp\left(\frac{r_{0}^{2}-r^{2}}{2{\tilde{\eta}}}\right)}_{\gamma(r_{0},r)}\bigg{)}$
$\displaystyle=(I-\mathcal{P}_{{\bf A}})\log\left(\gamma(r_{0},r)\cdot{\bf
x}_{\text{wn}}(0)\right)$

and for $L\neq 2$ we obtain that

$\displaystyle\left(I-\mathcal{P}_{{\bf A}}\right){\bf x}_{\text{wn}}^{\odot
2-L}$ $\displaystyle=\left(I-\mathcal{P}_{{\bf A}}\right){\bf u}^{\odot
2-L}r^{2-L}$ $\displaystyle=\underbrace{\left(I-\mathcal{P}_{{\bf
A}}\right){\bf u}^{\odot
2-L}\exp\left(\frac{2-L}{2{\tilde{\eta}}}r^{2}\right)}_{\text{invariant}}\exp\left(-\frac{2-L}{2{\tilde{\eta}}}r^{2}\right)r^{2-L}$
$\displaystyle=\left(I-\mathcal{P}_{{\bf A}}\right){\bf u}_{0}^{\odot
2-L}\exp\left(\frac{2-L}{2{\tilde{\eta}}}r_{0}^{2}\right)\exp\left(-\frac{2-L}{2{\tilde{\eta}}}r^{2}\right)r^{2-L}$
$\displaystyle=\left(I-\mathcal{P}_{{\bf A}}\right)(\,\underbrace{{\bf
u}_{0}r_{0}}_{{\bf x}_{\text{wn}}(0)}\,)^{\odot
2-L}\underbrace{\left(\frac{r}{r_{0}}\right)^{2-L}\exp\left(\frac{(2-L)(r_{0}^{2}-r^{2})}{2{\tilde{\eta}}}\right)}_{\gamma(r_{0},r)^{2-L}}$
$\displaystyle=\left(I-\mathcal{P}_{{\bf A}}\right)[\,\gamma(r_{0},r)\cdot{\bf
x}_{\text{wn}}(0)]^{\odot 2-L}.$

By continuity $\gamma(r_{0},r)$ converges to $\gamma(r_{0},r_{\infty})$, which
is well-defined because $r_{0},r_{\infty}>0$. This completes the proof. ∎

To make the full use of Lemma 3.9, we need to ensure that the invariants and
the fact that they converge to zero loss uniquely characterize the relation
between ${\bf x}_{\text{wn}}$ and ${\bf x}$. Thus we will need the following
two lemmas. Note that for the first one, we need to assume that the rows of
${\bf A}$ sum to zero. We leave it to future investigations whether
boundedness from below of the entries of ${\bf x}_{\text{wn}}$ and ${\bf x}$
holds also in general, or under other conditions.

######  Lemma 3.10 (Bounded above implies bounded below).

Consider the same setting as in Lemma 3.9. Suppose that there exists ${\bf
v}>0$ such ${\bf A}{\bf v}=0$ and that ${\bf x}_{\text{wn}},{\bf x}$ are
bounded above. Then each entry of ${\bf x}_{\text{wn}}$ and ${\bf x}$ is also
bounded away from zero.

###### Proof.

Since $\gamma$ defined in (42) is both bounded above and below, it suffices to
prove the case for ${\bf x}$. We will prove the statement by contradiction.
Suppose $x_{j}$ is not bounded away from zero. Then, there exists a sequence
$\\{t_{k}\\}_{k\in\mathbb{N}}$ such that $\lim_{k\to\infty}x_{j}(t_{k})=0$. By
assumption there exists ${\bf v}>0$ such that ${\bf A}{\bf v}=0$. Then for any
${\bf z}$ such that $(I-\mathcal{P}_{{\bf A}}){\bf z}=0$, it holds

$\langle{\bf z},{\bf v}\rangle=\langle\mathcal{P}_{{\bf A}}{\bf z},{\bf
v}\rangle+\langle(I-\mathcal{P}_{{\bf A}}){\bf z},{\bf v}\rangle=\langle{\bf
z},\mathcal{P}_{{\bf A}}{\bf v}\rangle=0.$

Let us now consider the case where $L=2$. By the invariant defined in Lemma
3.7, for all $k\in\mathbb{N}$,

$(I-\mathcal{P}_{{\bf A}})\log({\bf x}(t_{\bf k}))=(I-\mathcal{P}_{{\bf
A}})\log({\bf x}_{0}).$

This implies that there exists a sequence $\\{{\bf z}_{k}\\}_{k\in\mathbb{N}}$
such that $(I-\mathcal{P}_{{\bf A}}){\bf z}_{k}=0$ and

$\log({\bf x}(t_{k}))=\log({\bf x}_{0})+{\bf z}_{k}.$

Taking the inner product with ${\bf v}$ on both sides and using the fact that
$\langle{\bf z}_{k},{\bf v}\rangle=0$, we obtain

$\langle\log({\bf x}(t_{k})),{\bf v}\rangle=\langle\log({\bf x}_{0}),{\bf
v}\rangle.$

In the limit as $k\to\infty$, the left hand side becomes $-\infty$ because
${\bf x}$ is upper bounded while $\log(x_{j})$ goes to $-\infty$. This is a
contradiction since the right hand side is just a constant. Therefore all
entries of ${\bf x}$ must be bounded away from zero.

The same proof strategy works for $L\neq 2$ as well, leading to

$\langle{\bf x}^{\odot\frac{2}{L}-1}(t_{k}),{\bf v}\rangle=\langle{\bf
x}_{0}^{\odot\frac{2}{L}-1},{\bf v}\rangle.$

The left hand side tends to infinity as $k\to\infty$ if
$\lim_{k\to\infty}x_{j}(t_{k})=0$. This completes the proof. ∎

######  Lemma 3.11 (Uniqueness).

Suppose $\tilde{{\bf x}}^{(1)},\tilde{{\bf x}}^{(2)}$ are strictly positive
and uniformly bounded above and away from zero. If

$\displaystyle\lim_{t\to\infty}{\bf A}[\tilde{{\bf x}}^{(1)}(t)-\tilde{{\bf
x}}^{(2)}(t)]=0$ (43)

and

$\displaystyle\begin{cases}\lim_{t\to\infty}\left(I-\mathcal{P}_{{\bf
A}}\right)[\log(\tilde{{\bf x}}^{(1)}(t))-\log(\tilde{{\bf
x}}^{(2)}(t))]=0&\text{if }L=2,\\\ \lim_{t\to\infty}\left(I-\mathcal{P}_{{\bf
A}}\right)[(\tilde{{\bf x}}^{(1)}(t))^{\odot\frac{2}{L}-1}-(\tilde{{\bf
x}}^{(2)}(t))^{\odot\frac{2}{L}-1}]=0&\text{if }L\neq 2,\end{cases}$ (44)

then $\lim_{t\to\infty}\tilde{{\bf x}}^{(1)}(t)-\tilde{{\bf x}}^{(2)}(t)=0$.

###### Proof.

Let us first discuss the case where $L=2$. Since $\mathcal{P}_{{\bf A}}$ is a
projection, by decomposing vectors into the form ${\bf x}=\mathcal{P}_{{\bf
A}}{\bf x}+(I-\mathcal{P}_{{\bf A}}){\bf x}$, we have

$\displaystyle\lim_{t\to\infty}\langle\tilde{{\bf x}}^{(1)}(t)-\tilde{{\bf
x}}^{(2)}(t),\log(\tilde{{\bf x}}^{(1)}(t))-\log(\tilde{{\bf
x}}^{(2)}(t))\rangle$
$\displaystyle\quad=\lim_{t\to\infty}\langle\underbrace{\mathcal{P}_{{\bf
A}}[\tilde{{\bf x}}^{(1)}(t)-\tilde{{\bf x}}^{(2)}(t)]}_{\text{converges to
}0}\,,\,\underbrace{\log(\tilde{{\bf x}}^{(1)}(t))-\log(\tilde{{\bf
x}}^{(2)}(t))}_{\text{bounded}}\rangle$
$\displaystyle\qquad+\langle\underbrace{\tilde{{\bf x}}^{(1)}(t)-\tilde{{\bf
x}}^{(2)}(t)}_{\text{bounded}}\,,\,\underbrace{(I-\mathcal{P}_{{\bf
A}})[\log(\tilde{{\bf x}}^{(1)}(t))-\log(\tilde{{\bf
x}}^{(2)}(t))]}_{\text{converges to }0}\rangle$ $\displaystyle\quad=0$

Note that due to the monotonicity of $\log$, we have
$(a-b)(\log(a)-\log(b))\geq 0$, and consequently

$\bm{\xi}(t):=[\tilde{{\bf x}}^{(1)}(t)-\tilde{{\bf
x}}^{(2)}(t)]\odot[\log(\tilde{{\bf x}}^{(1)}(t))-\log(\tilde{{\bf
x}}^{(2)}(t))]\geq 0.$

A more compact way to express $\bm{\xi}$ is via the difference

$\bm{\Delta}:=|\tilde{{\bf x}}^{(1)}-\tilde{{\bf x}}^{(2)}|$

and the expression

$\displaystyle\bm{\xi}$ $\displaystyle=\bm{\Delta}\odot\log({\bf
1}+\bm{\Delta}\odot\min(\tilde{{\bf x}}^{(1)},\tilde{{\bf
x}}^{(2)})^{\odot-1})$ $\displaystyle\geq\bm{\Delta}\odot\log({\bf
1}+\bm{\Delta}\odot(\tilde{{\bf x}}^{(1)})^{\odot-1}).$ (45)

Since $\bm{\xi}\geq 0$ and $\langle\bm{\xi}(t),{\bf 1}\rangle$ converges to
zero as $t\to\infty$, we can deduce that $\bm{\xi}$ converges to zero as
$t\to\infty$. Together with (45) and the assumption that $\tilde{{\bf
x}}^{(1)}$ is uniformly bounded above, we conclude that $\bm{\Delta}$ must
also converges to zero. Since $\bm{\Delta}$ converges to zero, our conclusion
follows.

For $L>2$ the analysis is similar. First use the assumption to deduce that

$\displaystyle 0=\lim_{t\to\infty}\langle\tilde{{\bf x}}^{(1)}(t)-\tilde{{\bf
x}}^{(2)}(t),(\tilde{{\bf x}}^{(2)}(t))^{\odot\frac{2}{L}-1}-(\tilde{{\bf
x}}^{(1)}(t))^{\odot\frac{2}{L}-1}\rangle.$

Since the vector

$\bm{\xi}(t):=[\tilde{{\bf x}}^{(1)}(t)-\tilde{{\bf
x}}^{(2)}(t)]\odot[(\tilde{{\bf
x}}^{(2)})^{\odot\frac{2}{L}-1}(t)-(\tilde{{\bf
x}}^{(1)})^{\odot\frac{2}{L}-1}(t)]$

is non-negative and $\langle\bm{\xi}(t),{\bf 1}\rangle$ converges to zero, we
can deduce that $\bm{\xi}$ converges to zero. We will use the following fact:
if $a=b+\delta$ with $a,b,\delta\geq 0$, then

$\displaystyle\frac{1}{b}-\frac{1}{a}\geq\begin{cases}\frac{1}{2b}&\text{if
}\delta\geq b\\\ \frac{\delta}{2b^{2}}&\text{if }\delta\leq b\end{cases}$

and consequently

$\frac{1}{b}-\frac{1}{a}\geq\frac{1}{2b^{2}}\cdot\min\left(b,\delta\right).$

By substituting ${\bf a}=\max(\tilde{{\bf x}}^{(1)},\tilde{{\bf
x}}^{(2)})^{\odot 1-\frac{2}{L}}$ and ${\bf b}=\min(\tilde{{\bf
x}}^{(1)},\tilde{{\bf x}}^{(2)})^{\odot 1-\frac{2}{L}}$ into $\bm{\xi}$, we
obtain that

$\displaystyle\bm{\xi}$ $\displaystyle=|\tilde{{\bf x}}^{(1)}-\tilde{{\bf
x}}^{(2)}|\odot[{\bf b}^{\odot-1}-{\bf a}^{\odot-1}]$
$\displaystyle\geq\frac{1}{2}|\tilde{{\bf x}}^{(1)}-\tilde{{\bf
x}}^{(2)}|\odot\min\left({\bf b}^{\odot-1},|(\tilde{{\bf x}}^{(1)})^{\odot
1-\frac{2}{L}}-(\tilde{{\bf x}}^{(2)})^{\odot 1-\frac{2}{L}}|\odot{\bf
b}^{\odot-2}\right)$ $\displaystyle\geq\frac{1}{2}|\tilde{{\bf
x}}^{(1)}-\tilde{{\bf x}}^{(2)}|\odot\min\left((\tilde{{\bf
x}}^{(1)})^{\odot\frac{2}{L}-1},|(\tilde{{\bf x}}^{(1)})^{\odot
1-\frac{2}{L}}-(\tilde{{\bf x}}^{(2)})^{\odot 1-\frac{2}{L}}|\odot(\tilde{{\bf
x}}^{(1)})^{\odot\frac{4}{L}-2}\right)$

We again see that the difference $|\tilde{{\bf x}}^{(1)}(t)-\tilde{{\bf
x}}^{(2)}(t)|$ converges to zero because $\bm{\xi}(t)$ converges to zero and
$\tilde{{\bf x}}^{(1)},\tilde{{\bf x}}^{(2)}$ are uniformly bounded above and
below. Hence the proof is complete. ∎

###### Proof of Theorem 2.2.

The convergence rate of loss directly follows from Lemma 3.6 and Lemma 3.10.
For notation simplicity, denote $\tilde{{\bf x}}={\bf x}^{L}$ and $\tilde{{\bf
x}}_{\text{wn}}=\left(r{\bf u}/\|{\bf u}\|_{2}\right)^{\odot L}$. Since we
assume that $\tilde{{\bf x}}_{\text{wn}}$ converges to a minimizer of the loss
function, we obtain

$0=\lim_{t\to\infty}\mathcal{P}_{{\bf A}}[\tilde{{\bf x}}(t)-\tilde{{\bf
x}}_{\text{wn}}(t)].$

By Lemma 3.9, we also have

$\displaystyle 0$ $\displaystyle=\lim_{t\to\infty}\left(I-\mathcal{P}_{{\bf
A}}\right)\begin{cases}[\log(\tilde{{\bf x}}(t))-\log(\tilde{{\bf
x}}_{\text{wn}}(t))]&\text{if }L=2,\\\ [\tilde{{\bf
x}}^{\odot\frac{2}{L}-1}(t)-\tilde{{\bf
x}}_{\text{wn}}^{\odot\frac{2}{L}-1}(t)]&\text{if }L\neq 2.\end{cases}$

Therefore we can show that $\lim_{t\to\infty}\tilde{{\bf
x}}_{\text{wn}}(t)=\lim_{t\to\infty}\tilde{{\bf x}}(t)$. We use Theorem 2.1
from [8], which characterize the limit of $\tilde{{\bf x}}$, to draw the
conclusion on $\tilde{{\bf x}}_{\text{wn}}$. Note that $\tilde{{\bf x}}$ is
uniformly bounded below according to Lemma 3.10.

Essentially, we effectively re-scale the initialization by
$\gamma(r_{0},r_{\infty})$. To obtain the rest of the theorem, we will analyze
the function $\gamma$. The goal is to minimize $\gamma(r_{0},r_{\infty})$ so
that the “effective” initialization is small, ideally much less than $1$, so
that we get a weaker bound than the one in Theorem 2.1 by a factor of
$\gamma(r_{0},r_{\infty})$. Since $r_{0}$ and $r_{\infty}$ are dependent but
we do not know the exact relation, we will use some properties of the $\gamma$
and $r_{\infty}$ to derive bound of the improved factor.

Since we can choose $r_{0}$ but not $r_{\infty}$, we will examine the effect
of $r_{\infty}$ while fixing $r_{0}$. For now, let us assume that
$r_{\infty}\gg r_{0}$. The partial derivative of $\gamma$ is given by

$\displaystyle\partial_{r}\gamma(r_{0},r)$
$\displaystyle=\frac{1}{r_{0}}\left(1-\frac{r^{2}}{{\tilde{\eta}}}\right)\cdot\exp\left(\frac{r_{0}^{2}-r^{2}}{2{\tilde{\eta}}}\right).$

This implies that as long as ${\tilde{\eta}}\leq r_{0}^{2}$, we have

$\gamma(r_{0},r_{\infty})=\gamma(r_{0},r_{0})+\int_{r_{0}}^{r_{\infty}}\partial_{r}\gamma(r_{0},r)dr\leq\gamma(r_{0},r_{0})=1.$

In fact, for any $r\in[r_{0},r_{\infty}]$,
$\gamma(r_{0},r_{\infty})\leq\gamma(r_{0},r)$. Hence to upper bound
$\gamma(r_{0},r_{\infty})$, it suffices to lower bound $r_{\infty}$. By
assumption ${\bf A}\tilde{{\bf x}}_{\infty}={\bf b}$ and hence $\|\tilde{{\bf
x}}_{\infty}\|_{2}\geq\|{\bf A}^{\dagger}{\bf b}\|_{2}$. Consequently

$\displaystyle r_{\infty}$ $\displaystyle=\|\tilde{{\bf x}}_{\infty}^{\odot
1/L}\|_{2}=\|\tilde{{\bf x}}_{\infty}\|_{2/L}^{1/L}$
$\displaystyle\geq\|\tilde{{\bf x}}_{\infty}\|_{2}^{1/L}\geq\|{\bf
A}^{\dagger}{\bf b}\|_{2}^{1/L}.$

This also proves that $r_{\infty}\geq r_{0}$ and the proof is complete. ∎

###  3.3 Convergence for L=1,2

In this section we will prove the boundedness for $L=1,2$ state Lojasiewicz’s
Theorem [1], and based on this we will prove the convergence result stated in
Theorem 2.3.

######  Lemma 3.12 (Boundedness).

Let $L=1,2$ and ${\tilde{\eta}}>0$. Suppose $(r,{\bf u})$ follow the dynamics
in (13) and (14) with $(\eta_{r},\eta_{\bf u})=({\tilde{\eta}},1)$,
$r_{0},{\bf u}_{0}>0$. If all entries of ${\bf u}$ are bounded away from zero,
then $r$ is uniformly upper bounded.

###### Proof.

Denote $\widetilde{r}=\exp(r^{2}/(2{\tilde{\eta}}))$. Without loss of
generality we may assume $\|{\bf u}_{0}\|_{2}=1$. By Lemma 3.2, $\|{\bf
u}(t)\|_{2}=1$ for all $t\geq 0$. According to Lemma 3.5, the loss is non-
increasing, and hence $\|{\bf A}(r{\bf u})^{\odot L}-{\bf b}\|_{\infty}$ is
upper bounded. Consequently,

$\|\mathcal{P}_{{\bf A}}(r{\bf u})^{\odot L}\|_{\infty}\leq B_{1}$ (46)

for some $B_{1}\geq 0$. On the other hand, by Lemma 3.8, the quantity

$(I-\mathcal{P}_{{\bf A}})\cdot\begin{cases}\log(\widetilde{r}{\bf
u})&\text{if }L=2\\\ (\widetilde{r}{\bf u})^{\odot 2-L}&\text{if }L\neq
2\end{cases}$ (47)

equals its value at initialization for all $t\geq 0$. Thus its
$\ell_{\infty}$-norm is upper bounded by some $B_{2}\geq 0$.

Let us first study the case where $L=1$ by examining the inner product
$\langle r{\bf u},\widetilde{r}{\bf u}\rangle$. By decomposing
$I=\mathcal{P}_{{\bf A}}+(I-\mathcal{P}_{{\bf A}})$, we obtain

$\displaystyle\left\langle r{\bf u},\widetilde{r}{\bf u}\right\rangle$
$\displaystyle=\left\langle r{\bf u},\mathcal{P}_{{\bf A}}\widetilde{r}{\bf
u}\right\rangle+\left\langle r{\bf u},(I-\mathcal{P}_{{\bf
A}})\widetilde{r}{\bf u}\right\rangle$
$\displaystyle=\left\langle\mathcal{P}_{{\bf A}}r{\bf u},\widetilde{r}{\bf
u}\right\rangle+\left\langle r{\bf u},(I-\mathcal{P}_{{\bf
A}})\widetilde{r}{\bf u}\right\rangle$ $\displaystyle\leq
B_{1}\left\|\widetilde{r}{\bf u}\right\|_{1}+B_{2}\|r{\bf u}\|_{1}$
$\displaystyle=\left(B_{1}\widetilde{r}+B_{2}r\right)\left\|{\bf
u}\right\|_{1}$
$\displaystyle\leq\left(B_{1}\widetilde{r}+B_{2}r\right)\sqrt{N},$

where the last inequality comes from the fact that $\|{\bf
u}\|_{1}\leq\sqrt{N}\|{\bf u}\|_{2}=\sqrt{N}$. Since the left hand side can be
explicitly expressed as

$\left\langle r{\bf u},\widetilde{r}{\bf u}\right\rangle=r\widetilde{r}\|{\bf
u}\|_{2}^{2}=r\widetilde{r},$

we have

$r\exp\left(\frac{r^{2}}{2{\tilde{\eta}}}\right)\leq\left(B_{1}\exp\left(\frac{r^{2}}{2{\tilde{\eta}}}\right)+B_{2}r\right)\sqrt{N}.$

This implies that $r$ is uniformly bounded, because otherwise the left hand
side will eventually exceed the right hand side.

For $L=2$ we use a similar strategy by examining the inner product
$\langle(r{\bf u})^{\odot 2},\log(\widetilde{r}{\bf u})\rangle$. We first
obtain a lower bound of the inner product,

$\displaystyle\langle(r{\bf u})^{\odot 2},\log(\widetilde{r}{\bf u})\rangle$
$\displaystyle=r^{2}(\log(\widetilde{r})\langle{\bf u}^{\odot 2},{\bf
1}\rangle+\langle{\bf u}^{\odot 2},\log({\bf u})\rangle)$
$\displaystyle=r^{2}\left(\log(\widetilde{r})\|{\bf u}\|_{2}^{2}+\langle{\bf
u}^{\odot 2},\log({\bf u})\rangle\right).$

Since $\xi^{2}\log(\xi)\geq-\frac{1}{2e}$ for all $\xi\geq 0$, we have

$\langle(r{\bf u})^{\odot 2},\log(\widetilde{r}{\bf u})\rangle\geq
r^{2}\left(\log(\widetilde{r})-\frac{N}{2e}\right).$ (48)

We now derive an upper bound. By decomposing $I=\mathcal{P}_{{\bf
A}}+(I-\mathcal{P}_{{\bf A}})$, we obtain

$\displaystyle\left\langle(r{\bf u})^{\odot 2},\log\left(\widetilde{r}{\bf
u}\right)\right\rangle$ $\displaystyle=\left\langle(r{\bf u})^{\odot
2},\mathcal{P}_{{\bf A}}\log\left(\widetilde{r}{\bf
u}\right)\right\rangle+\left\langle(r{\bf u})^{\odot 2},(I-\mathcal{P}_{{\bf
A}})\log\left(\widetilde{r}{\bf u}\right)\right\rangle$
$\displaystyle=\left\langle\mathcal{P}_{{\bf A}}(r{\bf u})^{\odot
2},\mathcal{P}_{{\bf A}}\log\left(\widetilde{r}{\bf
u}\right)\right\rangle+\left\langle(r{\bf u})^{\odot 2},(I-\mathcal{P}_{{\bf
A}})\log\left(\widetilde{r}{\bf u}\right)\right\rangle$ $\displaystyle\leq
B_{1}\left\|\mathcal{P}_{{\bf A}}\log\left(\widetilde{r}{\bf
u}\right)\right\|_{1}+B_{2}\|(r{\bf u})^{\odot 2}\|_{1}$
$\displaystyle=B_{1}\left\|\log(\widetilde{r})\cdot\mathcal{P}_{{\bf A}}{\bf
1}+\mathcal{P}_{{\bf A}}\log\left({\bf u}\right)\right\|_{1}+B_{2}r^{2}\|{\bf
u}\|_{2}^{2}$ $\displaystyle\leq B_{1}\log(\widetilde{r})\|\mathcal{P}_{{\bf
A}}{\bf 1}\|_{1}+B_{1}\left\|\mathcal{P}_{{\bf A}}\log\left({\bf
u}\right)\right\|_{1}+B_{2}r^{2}.$

Note that $B_{1}\left\|\mathcal{P}_{{\bf A}}\log\left({\bf
u}\right)\right\|_{1}$ is upper bounded by some constant $C$ because the
entries of ${\bf u}$ are bounded both above and below. Combining this with
(48), we have

$\frac{r^{4}}{2{\tilde{\eta}}}-\frac{eNr^{2}}{2}\leq\left(\frac{B_{1}}{2{\tilde{\eta}}}\|\mathcal{P}_{{\bf
A}}{\bf 1}\|_{1}+B_{2}\right)r^{2}+C,$

which implies that $r$ is upper bounded because the left hand side scales like
$r^{4}$ while the right hand side scales like $r^{2}$. ∎

######  Theorem 3.13 (Theorem 4 in [5]).

If $\mathcal{L}:\mathbb{R}^{N}\to\mathbb{R}$ is analytic and the curve
$t\mapsto{\bf x}(t)\in\mathbb{R}^{N}$, $t\in[0,\infty)$ is bounded and a
solution of the gradient flow equation $\partial_{t}{\bf
x}=\nabla\mathcal{L}({\bf x})$, then ${\bf x}$ converges to a critical point
of $\mathcal{L}$ as $t\to\infty$.

###### Proof of Theorem 2.3.

The assumptions of Theorem 3.13 are satisfied with loss function
$\widetilde{\mathcal{L}}$. By Lemma 3.12, $\|{\bf x}(t)\|$ is bounded, and
hence by Theorem 3.13 must converges to a critical point of
$\widetilde{\mathcal{L}}$. ∎

###  3.4 An example of time-dependent learning rate

In this section we study a particular example of time-dependent learning rate,
given by $(\eta_{r},\eta_{\bf u})=(r^{2},1)$. Note that instead of a constant
in time, $\eta_{r}=r^{2}(t)$ is a function depends on time. In this case the
dynamics is greatly simplified and is similar to gradient flow without
normalization (11). Such simplification allows us to analyze the dynamics
based on established methods, such as the argument with Bregman divergence in
[8], and completely bypass the need of invariants and uniqueness results
proved in Section 3.2.

However, gradient flow under this particular choice of learning rate
($(\eta_{r},\eta_{\bf u})=(r^{2},1)$) no longer exhibits the magnification
effect as in the constant rate case ($(\eta_{r},\eta_{\bf
u})=({\tilde{\eta}},1)$), and hence does not yield better bounds than the ones
in previous works (8). It is nevertheless remarkable that the dynamics with
certain choices of learning rate can be so different from the one with time-
independent learning rate.

We will first prove a general reduction in dynamics. In fact, from Lemma 3.14
we can see why $(\eta_{r},\eta_{\bf u})=(r^{2},1)$ is a natural choice of
time-dependent learning rate.

######  Lemma 3.14 (Dynamics reduction).

Suppose $r$ and ${\bf u}$ follow the gradient flow in (13) and (14) with
$\|{\bf u}(0)\|=1$. Let ${\bf x}:=\frac{r}{\|{\bf u}\|_{2}}{\bf u}$. Then

$\partial_{t}{\bf x}=-\left(\eta_{r}\frac{{\bf x}{\bf x}^{\top}}{\|{\bf
x}\|_{2}^{2}}+\eta_{\bf u}(\|{\bf x}\|_{2}^{2}I-{\bf x}{\bf
x}^{\top})\right)\nabla\mathcal{L}\left({\bf x}\right).$ (49)

###### Proof.

By (23) and (24),

$\displaystyle\partial_{t}\left(\frac{r}{\|{\bf u}\|_{2}}{\bf u}\right)$
$\displaystyle={\bf u}\frac{\partial_{t}r}{\|{\bf u}\|_{2}}+\frac{r}{\|{\bf
u}\|_{2}}(I-\mathcal{P}_{{\bf u}})\partial_{t}{\bf u}$
$\displaystyle=-\eta_{r}\mathcal{P}_{{\bf
u}}\nabla\mathcal{L}\left(\frac{r}{\|{\bf u}\|_{2}}{\bf u}\right)-\eta_{\bf
u}\frac{r^{2}}{\|{\bf u}\|_{2}^{2}}\left(I-\mathcal{P}_{{\bf
u}}\right)^{2}\nabla\mathcal{L}\left(\frac{r}{\|{\bf u}\|_{2}}{\bf u}\right)$
$\displaystyle=-\left(\eta_{r}\mathcal{P}_{{\bf u}}+\frac{\eta_{\bf
u}r^{2}}{\|{\bf u}\|_{2}^{2}}(I-\mathcal{P}_{{\bf
u}})\right)\nabla\mathcal{L}\left(\frac{r}{\|{\bf u}\|_{2}}{\bf u}\right).$

Since $\|{\bf u}\|_{2}=1$, by Lemma 3.2 and $r=\|{\bf x}\|_{2}$, we obtain

$\displaystyle\mathcal{P}_{{\bf u}}=\frac{{\bf u}{\bf u}^{\top}}{\|{\bf
u}\|_{2}^{2}}=\frac{r{\bf u}(r{\bf u})^{\top}}{r^{2}}=\frac{{\bf x}{\bf
x}^{\top}}{\|{\bf x}\|_{2}^{2}}=\mathcal{P}_{{\bf x}}$

and hence (49) holds. ∎

Observe that if $(\eta_{r},\eta_{\bf u})=(r^{2},1)$, then (49) is greatly
simplified as stated next.

######  Corollary 3.15 (Dynamic reduction, time-dependent learning rate).

Let $L\in\mathbb{N}$, $(\eta_{r},\eta_{\bf u})=(r^{2},1)$, and $\|{\bf
u}(0)\|=1$. Denote ${\bf x}:=\frac{r}{\|{\bf u}\|_{2}}{\bf u}$. Then

$\partial_{t}{\bf x}=-\|{\bf x}\|_{2}^{2}\cdot\nabla\mathcal{L}\left({\bf
x}\right).$ (50)

###### Proof.

The statement follows from Lemma 3.14 by substituting $(\eta_{r},\eta_{\bf
u})=(r^{2},1)$ into (49). ∎

Note that without the additional factor $\|{\bf x}\|_{2}^{2}$, we are back to
the setting that does not include weight normalization at all (3). Although
the extra factor changes in time, since it is only a scalar as opposed to a
vector or a matrix, it is possible to apply the same proof strategy as for
gradient flow without normalization as in [8].

Before diving into the proof we would like to outline the general concepts. We
consider the set of all non-negative solutions $S_{+}:=\\{{\bf z}\geq 0:{\bf
A}{\bf z}={\bf b}\\}$ and examine how $\tilde{{\bf x}}:={\bf x}^{\odot L}$
approaches this set. The key insight is to measure the distance with an
appropriate Bregman divergence, so that $\tilde{{\bf x}}$ approaches every
element in $S_{+}$ at the same rate. Hence, by proving that $\tilde{{\bf x}}$
eventually reaches $S_{+}$, we conclude that it must reach the element that is
closest to the initialization measured in Bregman divergence defined next.

######  Definition 3.16 (Bregman Divergence).

Let $F:\Omega\to\mathbb{R}$ be a continuously-differentiable, strictly convex
function defined on a closed convex set $\Omega$. The Bregman divergence
associated with $F$ for points $p,q\in\Omega$ is defined as

$D_{F}(p,q)=F(p)-F(q)-\langle\nabla F(q),p-q\rangle.$ (51)

######  Lemma 3.17 ([6]).

The Bregman divergence $D_{F}$ is non-negative and, for any $q\in\Omega$, the
function $p\mapsto D_{F}(p,q)$ is strictly convex.

######  Lemma 3.18 (Non-increasing Bregman Divergence).

Let $L\in\mathbb{N}$, $L\geq 2$, $(\eta_{r},\eta_{\bf u})=(r^{2},1)$, and
$\|{\bf u}(0)\|=1$. Denote ${\bf x}=\frac{r}{\|{\bf u}\|_{2}}{\bf u}$ and
$\tilde{{\bf x}}={\bf x}^{\odot L}$. Then for any ${\bf z}\geq 0$ such that
${\bf A}{\bf z}={\bf b}$,

$\partial_{t}D_{F}({\bf z},\tilde{{\bf x}}(t))=-2L\|{\bf
x}(t)\|_{2}^{2}\cdot\mathcal{L}({\bf x}(t))$ (52)

where $D_{F}$ is the Bregman divergence associated with the function
$F:\mathbb{R}_{+}^{N}\to\mathbb{R}$ given by

$F(\tilde{{\bf x}})=\begin{cases}\frac{1}{2}\langle\tilde{{\bf
x}}\odot\log(\tilde{{\bf x}})-\tilde{{\bf x}},\bm{1}\rangle&\text{if }L=2\\\
\frac{L}{2(2-L)}\langle\tilde{{\bf
x}}^{\odot\frac{2}{L}},\bm{1}\rangle&\text{if }L>2.\end{cases}$ (53)

######  Lemma 3.19 (Convergence, time-dependent learning rate).

Let $L\in\mathbb{N}$, $L\geq 2$, $(\eta_{r},\eta_{\bf u})=(r^{2},1)$, $\|{\bf
u}(0)\|=1$ and $r(0)>0$. Denote ${\bf x}=\frac{r}{\|{\bf u}\|_{2}}{\bf u}$.
Suppose that ${\bf b}$ is not identically zero and the solution set
$S_{+}=\\{{\bf z}\geq 0:{\bf A}{\bf z}={\bf b}\\}$ is non-empty. Then

$\lim_{t\to\infty}\mathcal{L}({\bf x}(t))=0.$

###### Proof.

Denote $\tilde{{\bf x}}={\bf x}^{\odot L}$ and ${\bf x}_{0}={\bf x}(0)$. We
prove the statement by contradiction. Suppose that $\mathcal{L}({\bf x}(t))$
does not converge to zero. Since $\mathcal{L}$ is non-increasing in $t$
according to Lemma 3.5, $\mathcal{L}$ is bounded away from zero. Therefore,
there exists $\varepsilon>0$ such that $\mathcal{L}({\bf
x}(t))\geq\varepsilon$ for all $t\geq 0$.

Let ${\bf z}\in S_{+}$. Since $r(0)>0$ and ${\bf u}(0)\geq 0$, we have ${\bf
x}\geq 0$ for all $t\geq 0$ by Lemma 3.3. Hence $D_{F}({\bf z},\tilde{{\bf
x}}(t))$ is well-defined. By Lemma 3.18, $D_{F}({\bf z},\tilde{{\bf x}}(t))$
is non-increasing in $t$ and hence bounded above by $D_{F}({\bf z},\tilde{{\bf
x}}_{0})$. By Lemma 3.17, $D_{F}$ is non-negative and hence bounded below.
Therefore by (52),

$\displaystyle D_{F}({\bf z},\tilde{{\bf
x}}_{0})\geq-\int_{0}^{\infty}\partial_{t}D_{F}({\bf z},\tilde{{\bf
x}}(t))dt=\int_{0}^{\infty}2L\|{\bf x}(t)\|_{2}^{2}\cdot\mathcal{L}({\bf
x}(t))dt\geq 2L\varepsilon\int_{0}^{\infty}\|{\bf x}(t)\|_{2}^{2}dt.$ (54)

Since $D_{F}({\bf z},\tilde{{\bf x}}_{0})<\infty$, by (54) $\|{\bf
x}(t)\|_{2}$ cannot be bounded away from zero. This implies that there exists
an increasing sequence $\\{t_{k}\\}_{k\in[\mathbb{N}]}$ such that
$\lim_{k\to\infty}\|{\bf x}(t_{k})\|_{2}=0$. Together with the fact that ${\bf
x}$ is non-negative, we get that for all $n\in[N]$,
$\lim_{k\to\infty}x_{n}(t_{k})=0$, and consequently
$\lim_{k\to\infty}\tilde{x}_{n}(t_{k})=0$.

We now prove that $D_{F}$ eventually exceeds its initial value, i.e. there
exists $T>0$ such that $D_{F}({\bf z},\tilde{{\bf x}}(T))>D_{F}({\bf
z},\tilde{{\bf x}}_{0})$, and hence the contradiction. Note that the Bregman
divergence in our case is given by

$D_{F}({\bf z},\tilde{{\bf x}})=\begin{cases}\frac{1}{2}\langle{\bf
z}\odot\log({\bf z})-{\bf z}+\tilde{{\bf
x}},\bm{1}\rangle-\frac{1}{2}\langle\log(\tilde{{\bf x}}),{\bf
z}\rangle&\text{if }L=2,\\\ \langle\frac{L}{2(2-L)}{\bf
z}^{\odot\frac{2}{L}}+\frac{1}{2}\tilde{{\bf
x}}^{\odot\frac{2}{L}},\bm{1}\rangle-\frac{1}{2-L}\langle\tilde{{\bf
x}}^{\odot\frac{2}{L}-1},{\bf z}\rangle&\text{if }L>2.\end{cases}$

As ${\bf x}$ converges to zero, all terms except the last one converge to
zero, while the last term blows up to infinity because ${\bf z}\geq 0$ and
${\bf z}$ is not identically zero (as a consequence of ${\bf b}$ being not
identically zero). Thus there exists $k\in\mathbb{N}$ such that $D_{F}({\bf
z},\tilde{{\bf x}}(t_{k}))>D_{F}({\bf z},\tilde{{\bf x}}_{0})$. This
contradicts Lemma 3.18. Therefore $\mathcal{L}({\bf x}(t))$ converges to zero.
∎

###### Proof of Theorem 2.4.

The convergence of the loss follows directly from Lemma 3.19. Then existence
of the limit and the optimality of the limit follows the same proof strategy
as in [8]. ∎

##  4 Experiments

We conduct experiments to evaluate our method in terms of accuracy,
convergence, and the effect of the key parameter: the learning rate ratio
${\tilde{\eta}}$ used in Theorem 2.2. We set the ambient dimension to be
$N=1000$ and $M=150$. The matrix ${\bf A}$ is generated as

${\bf A}=\frac{1}{\sqrt{M}}{\bf G},\quad{\bf b}={\bf A}{\bf x}^{*}$

where ${\bf x}^{*}$ is the ground truth and ${\bf G}\in\mathbb{R}^{M\times N}$
has independent and standard normal distributed entries. We will examine two
cases: either the ground truth vector ${\bf x}^{*}$ is generated as a Gaussian
vector (not sparse in general), or generated as a random sparse vector. The
first case is more generic, and we compare the difference (which should be
small according to Theorem 2.2)

$\varepsilon_{1}:=\|\tilde{{\bf x}}_{\infty}\|_{1}-\min_{{\bf z}\in
S_{+}}\|{\bf z}\|_{1}\;.$

On the other hand, in the second case for sufficiently sparse ${\bf x}^{*}$ we
can expect almost exact recovery of ${\bf x}^{*}$ due to the restricted
isometry property of ${\bf A}$. Hence we will compare the difference

$\varepsilon_{2}:=\|\tilde{{\bf x}}_{\infty}-{\bf x}^{*}\|_{1}\;.$

For both cases, we study the case $L=2$ for illustration. Similar improvements
are also observed in cases where $L>2$. All experiments are conducted with GD
with either constant small step size, or step size yields by the line search
method. Each data point is an average over ten random data (${\bf A}$ and
${\bf b}$) and random initialization ${\bf x}_{0}$. Number of iterations are
set to be $10^{6}$ or whenever the loss function falls below $10^{-12}$. We
will compare GD without normalization and GD with normalization.

To keep the presentation concise, we will not plot the results for weight
normalization with time-dependent learning rate specified in Section 3.4,
because in all our experiments they perfectly coincide with the results coming
from regular GD without weight normalization, which is consistent with Theorem
2.4.

###  4.1 Gaussian ground truth

(a) Normalization significantly reduces the error $\varepsilon_{1}$.

(b) Loss with normalization during training.

Figure 2: Here we fix ${\tilde{\eta}}=0.1$. GD with normalization yields
significantly much smaller error than GD without normalization. In all
experiments the loss converges to values close to zero, as shown in Figure
2(b). All results are average over $10$ trials. Note that although in Figure
2(a) the error with WN seems to decreases when initialization increases, it is
mostly due to the fact that small initialization causes slow convergence and
our algorithm for small initialization simply terminate due to run time before
it reaches its optimal accuracy.

Here we generate ${\bf x}^{*}$ as $|{\bf z}|$, where ${\bf z}$ is a standard
Gaussian vector in $\mathbb{R}^{n}$ with independent entries. In the first
experiment (Figure 2), we fix ${\tilde{\eta}}=0.1$ and vary the initialization
$r_{0}$. In Figure 2(a), we compare the error $\varepsilon_{1}$ produced by
the two algorithms. According to Theorem 2.2, the one with normalization
should yield smaller $\varepsilon_{1}$ for fixed initialization $r_{0}$, which
is consistent with our results. In fact the difference is quite significant.
For instance, when $r_{0}=1$ the error differs by a factor of $100$! In Figure
2(b) we observe that during training all loss decreases monotonically to
vicinity of zero. According to experiments, convergence usually holds as long
as the initialization $r_{0}$ is less than the limit $r_{\infty}$. Note that
in 4(b) we present cases where convergence does not hold.

(a) Smaller ${\tilde{\eta}}$ leaders to smaller error $\varepsilon_{1}$ (with
WN).

(b) Smaller ${\tilde{\eta}}$ requires more iterations (with WN).

Figure 3: Here we fix $r_{0}=1$. As the learning rate ratio ${\tilde{\eta}}$
decreases, the error decreases but requires more number of iterations. Thus
there is a trade-off between the accuracy and the convergence rate. All
results are average over $10$ trials.

In the second experiment (Figure 3), we fix $r_{0}=1$ (which corresponds to
initialization on the unit sphere) and vary the learning rate ratio
${\tilde{\eta}}$. In Figure 3(a) we again analyze the error $\varepsilon_{1}$
among different algorithms. We see that in general as ${\tilde{\eta}}$
decreases, the error $\varepsilon_{1}$ decreases. In particular, such error
goes is significantly smaller than the error of GD without normalization,
which is represented by the horizontal line. In Figure 3(b) we see that as
${\tilde{\eta}}$ decreases, GD with normalization converges slower. Therefore,
there is a trade-off between the accuracy and the convergence rate. Smaller
${\tilde{\eta}}$ induces smaller error, but requires more time.

###  4.2 Sparse ground truth

Here we first generate ${\bf z}$ as a standard Gaussian with independent
entries. We select a random support with size $s=10$ and let ${\bf z}^{*}$ be
a vector equal to ${\bf z}$ on such support and zero otherwise. We then set
${\bf x}^{*}$ to be $s\cdot\frac{|{\bf z}^{*}|}{\|{\bf z}^{*}\|_{1}}$.

(a) The improvement in reconstruction error $\varepsilon_{2}$ occurs when
$r_{0}\leq s=\sqrt{10}$.

(b) Loss with normalization also decreases monotonically.

Figure 4: Here we fix ${\tilde{\eta}}=0.1$ and analyze the reconstruction
error $\varepsilon_{2}$. Since the data is generated such that $s\leq
r_{\infty}$. When $r_{0}\leq s$ (and hence $r_{0}\leq r_{\infty}$), GD with
normalization yields smaller error than the ones without normalization. All
results are average over $10$ trials.

In the third experiment (Figure 4), we fix ${\tilde{\eta}}=0.1$ and vary
initialization $r_{0}$. Since the data is generated based on ${\bf b}={\bf
A}{\bf x}^{*}$ with $\|{\bf x}^{*}\|_{1}=s$, assuming that the loss converges
to zero, we know that $s\leq r_{\infty}$. In Figure 4(a) we compare the
reconstruction error $\varepsilon_{2}$ among different algorithms. Again we
see that the error for GD with normalization is smaller, but the difference is
only apparent for $r_{0}<r_{\infty}$. In Figure 4(b) we observe that, in
contrast to Figure 2(b), the loss does not necessarily converge to zero, for
instance when $r_{0}=100$.

###  4.3 Sparse ground truth with positive and negative entries

(a) WN leads to smaller reconstruction error $\varepsilon_{2}$.

(b) Similar to before, loss with normalization decreases monotonically.

Figure 5: The setting is the same as in Figure 4, except that in such setting
we can recover ground truth vectors that are not necessarily non-negative.

The setting of the forth experiment (Figure 5) is the same as the third
experiment, except that the ground truth is not constrained to have positive
entries, i.e. ${\bf x}^{*}$ equals to $s\cdot\frac{{\bf z}^{*}}{\|{\bf
z}^{*}\|_{1}}$, and the loss function we use here is the same as in (21)

$\mathcal{L}_{\pm}({\bf u},{\bf v})=\frac{1}{2L}\|{\bf A}({\bf u}^{\odot
L}-{\bf v}^{\odot L})-{\bf b}\|_{2}^{2},\quad{\bf u}_{0},{\bf v}_{0}>0$

motivated by [8, 16, 38]. We observe that the benefit of WN still exists, but
less strong as the one in the third experiment.

##  5 Summary and Discussion

In this paper we initiate a study of the implicit bias of gradient descent
with weight normalization beyond the linear regression setting. In the
overparameterized diagonal linear neural network model, we show that weight
normalization provably enables a robust implicit regularization towards sparse
solutions that holds beyond the regime of small initialization. We moreover
show a linear rate of convergence and an explicit dependence on the
initialization scale, indicating that smaller initialization corresponds to
slower convergence rate. Numerical experiments are consistent with our theory,
and the key quantities such as invariants and the proof strategies can
potentially be applied in more general settings.

There are still many remaining questions such as

  1. 1.

Do our results generalize to other settings which currently require small
initialization to prove an implicit bias?

  2. 2.

Can we use the proof strategy to study the effect of weight normalization on
neural networks with first-order homogeneous activation functions, such as
ReLU?

  3. 3.

Can we extend the results here from gradient flow to gradient descent?

  4. 4.

Is there a reasonable choice of time-dependent rate that might outperform
constant rate, or does the time-dependent rate necessarily lose the magnified
implicit bias as shown in Theorem 2.4?

## Acknowledgement

R. Ward is grateful for support from AFOSR MURI FA9550-19-1-0005, NSF DMS
1952735, NSF HDR 1934932, HDR TRIPODS Phase II grant 2217058, and NSF CCF
2019844. H.C. and H.R. acknowledge funding from the Deutsche
Forschungsgemeinschaft (DFG) through the Collaborative Research Center
Sparsity and Singular Structures (SFB 1481). H.C. acknowledge funding from
Munich Center for Machine Learning (MCML).

## References

  * [1] P. A. Absil, R. Mahony, and B. Andrews.  Convergence of the iterates of descent methods for analytic cost functions.  SIAM Journal on Optimization, 16(2):531–547, 2005.
  * [2] S. Arora, N. Cohen, and E. Hazan.  On the optimization of deep networks: Implicit acceleration by overparameterization.  In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, pages 244–253, 2018.
  * [3] S. Arora, N. Cohen, W. Hu, and Y. Luo.  Implicit regularization in deep matrix factorization.  In Advances in Neural Information Processing Systems, pages 7413–7424, 2019.
  * [4] J. L. Ba, J. R. Kiros, and G. E. Hinton.  Layer normalization.  arXiv preprint arXiv:1607.06450, 2016.
  * [5] B. Bah, H. Rauhut, U. Terstiege, and M. Westdickenberg.  Learning deep linear neural networks: Riemannian gradient flows and convergence to global minimizers.  Information and Inference: A Journal of the IMA, 11(1):307–353, 02 2021.
  * [6] L. Bregman.  The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming.  USSR Computational Mathematics and Mathematical Physics, 7(3):200–217, 1967.
  * [7] H. Chou, C. Gieshoff, J. Maly, and H. Rauhut.  Gradient descent for deep matrix factorization: Dynamics and implicit bias towards low rank.  arXiv preprint: 2011.13772, 2020.
  * [8] H.-H. Chou, J. Maly, and H. Rauhut.  More is less: inducing sparsity via overparameterization.  Information and Inference: A Journal of the IMA, 12(3), 04 2023\.  iaad012.
  * [9] N. Cohen, G. Menon, and Z. Veraszto.  Deep linear networks for matrix completion – an infinite depth limit.  arXiv preprint arXiv: 2210.12497, 2023.
  * [10] T. M. Cover.  Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition.  IEEE Trans. Electron. Comput., 14(3):326–334, 1965.
  * [11] S. Du, J. Lee, H. Li, L. Wang, and X. Zhai.  Gradient descent finds global minima of deep neural networks.  In International conference on machine learning, pages 1675–1685. PMLR, 2019.
  * [12] Y. Dukler, Q. Gu, and G. Montúfar.  Optimization theory for relu neural networks trained with normalization layers.  In International conference on machine learning, pages 2751–2760. PMLR, 2020.
  * [13] J. Flum and M. Grohe.  Parameterized Complexity Theory.  Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006\.
  * [14] K. Geyer, A. Kyrillidis, and A. Kalev.  Low-rank regularization and solution uniqueness in over-parameterized matrix sensing.  In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, pages 930–940, 2020.
  * [15] G. Gidel, F. Bach, and S. Lacoste-Julien.  Implicit regularization of discrete gradient dynamics in linear neural networks.  In Advances in Neural Information Processing Systems, pages 3202–3211, 2019.
  * [16] D. Gissin, S. Shalev-Shwartz, and A. Daniely.  The implicit bias of depth: How incremental learning drives generalization.  In International Conference on Learning Representations, 2020.
  * [17] X. Glorot and Y. Bengio.  Understanding the difficulty of training deep feedforward neural networks.  In Y. W. Teh and M. Titterington, editors, Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pages 249–256, Chia Laguna Resort, Sardinia, Italy, 13–15 May 2010. PMLR.
  * [18] S. Gunasekar, J. Lee, D. Soudry, and N. Srebro.  Characterizing implicit bias in terms of optimization geometry.  In J. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 1832–1841. PMLR, 10–15 Jul 2018.
  * [19] S. Gunasekar, J. D. Lee, D. Soudry, and N. Srebro.  Implicit bias of gradient descent on linear convolutional networks.  In Advances in Neural Information Processing Systems, pages 9461–9471, 2018.
  * [20] S. Gunasekar, B. E. Woodworth, S. Bhojanapalli, B. Neyshabur, and N. Srebro.  Implicit regularization in matrix factorization.  In Advances in Neural Information Processing Systems, pages 6151–6159, 2017.
  * [21] P. D. Hoff.  Lasso, fractional norm and structured sparse estimation using a Hadamard product parametrization.  Computational Statistics & Data Analysis, 115:186–198, 2017.
  * [22] S. Ioffe and C. Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  In International conference on machine learning, pages 448–456. PMLR, 2015.
  * [23] A. Jacot, C. Hongler, and F. Gabriel.  Neural tangent kernel: Convergence and generalization in neural networks.  In Advances in Neural Information Processing Systems, pages 8580–8589, 2018.
  * [24] J. Li, T. Nguyen, C. Hegde, and K. W. Wong.  Implicit sparse regularization: The impact of depth and early stopping.  In Advances in Neural Information Processing Systems, pages 28298–28309, 2021.
  * [25] D. Morwani and H. G. Ramaswamy.  Inductive bias of gradient descent for weight normalized smooth homogeneous neural nets.  In International Conference on Algorithmic Learning Theory, pages 827–880. PMLR, 2022.
  * [26] B. Neyshabur, R. Tomioka, R. Salakhutdinov, and N. Srebro.  Geometry of optimization and implicit regularization in deep learning.  arXiv preprint arXiv: 1705.03071, 2017.
  * [27] B. Neyshabur, R. Tomioka, and N. Srebro.  In search of the real inductive bias: On the role of implicit regularization in deep learning.  In International Conference on Learning Representations, 2015.
  * [28] G. M. Nguegnang, H. Rauhut, and U. Terstiege.  Convergence of gradient descent for learning linear neural networks.  arXiv preprint arXiv: 2108.02040, 2021.
  * [29] S. Pesme and N. Flammarion.  Saddle-to-saddle dynamics in diagonal linear networks.  arXiv preprint arXiv: 2304.00488, 2023.
  * [30] T. Poggio, Q. Liao, and A. Banburski.  Complexity control by gradient descent in deep networks.  Nature communications, 11(1):1–5, 2020.
  * [31] N. Razin and N. Cohen.  Implicit regularization in deep learning may not be explainable by norms.  In Advances in Neural Information Processing Systems, pages 21174–21187, 2020.
  * [32] N. Razin, A. Maman, and N. Cohen.  Implicit regularization in tensor factorization.  arXiv preprint: 2102.09972, 2021.
  * [33] N. Razin, A. Maman, and N. Cohen.  Implicit regularization in hierarchical tensor factorization and deep convolutional neural networks.  arXiv preprint arXiv: 2201.11729, 2022.
  * [34] T. Salimans and D. P. Kingma.  Weight normalization: A simple reparameterization to accelerate training of deep neural networks.  In Advances in Neural Information Processing Systems, volume 29, page 901. Curran Associates, Inc., 2016.
  * [35] D. Soudry, E. Hoffer, M. S. Nacson, S. Gunasekar, and N. Srebro.  The implicit bias of gradient descent on separable data.  The Journal of Machine Learning Research, 19(1):2822–2878, 2018\.
  * [36] D. Stöger and M. Soltanolkotabi.  Small random initialization is akin to spectral learning : Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction.  In Advances in Neural Information Processing Systems, pages 23831–23843, 2021.
  * [37] T. Vaskevicius, V. Kanade, and P. Rebeschini.  Implicit regularization for optimal sparse recovery.  In Advances in Neural Information Processing Systems, pages 2972–2983, 2019.
  * [38] B. Woodworth, S. Gunasekar, J. D. Lee, E. Moroshko, P. Savarese, I. Golan, D. Soudry, and N. Srebro.  Kernel and rich regimes in overparametrized models.  In Proceedings of Thirty Third Conference on Learning Theory, pages 3635–3673, 2020.
  * [39] X. Wu, E. Dobriban, T. Ren, S. Wu, Z. Li, S. Gunasekar, R. Ward, and Q. Liu.  Implicit regularization and convergence for weight normalization.  In Advances in Neural Information Processing Systems, volume 33, pages 2835–2847. Curran Associates, Inc., 2020.
  * [40] X. Wu, R. Ward, and L. Bottou.  Wngrad: Learn the learning rate in gradient descent.  arXiv preprint arXiv:1803.02865, 2018.
  * [41] X. Wu, Y. Xie, S. S. Du, and R. Ward.  Adaloss: A computationally-efficient and provably convergent adaptive gradient method.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36(8), pages 8691–8699, 2022.
  * [42] C. You, Z. Zhu, Q. Qu, and Y. Ma.  Robust recovery via implicit bias of discrepant learning rates for double over-parameterization.  In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 17733–17744. Curran Associates, Inc., 2020.
  * [43] P. Zhao, Y. Yang, and Q.-C. He.  Implicit regularization via hadamard product over-parametrization in high-dimensional linear regression.  arXiv preprint: 1903.09367, 2019.