$$

For a moment, let’s forget that interference ever existed, and figure out how (and how fast) regularization will push towards sparsity in some encoding $W_i$. Since we’re only looking at feature benefit and regularization, the other encodings have no influence at all on what happens in $W_i$.

On each weight $W_{ik}$, we have

• feature benefit pushing up by $(1-{\Vert W_i\Vert }^2)W_{ik}$,
• regularization pushing down by $\lambda \mathrm{sign}(W_{ik})$.

Crucially, the upwards push is relative to $W_{ik}$, while the downwards push is absolute. This means that weights whose absolute value is above some threshold $\theta$ will increase, while those below the threshold will decrease, creating a “rich gets richer and poor gets poorer” dynamic that will push for sparsity. This threshold is

$$(1-{\Vert W_i\Vert }^2)W_{ik}=\lambda \mathrm{sign}(W_i)\iff |W_{ik}|=\frac{\lambda }{1-{\Vert W_i\Vert }^2}=:\theta .$$

And we have

$$\begin{array}{rl}\text{(1)}& \frac{\mathrm{d}|W_{ik}|}{\mathrm{d}t}& =\underset{\text{feature benefit}}{\underbrace{(1-{\Vert W_i\Vert }^2)|W_{ik}|}}-\underset{\text{regularization}}{\underbrace{\lambda \mathbb{1}[W_{ik}\ne 0]}}& =\{\begin{array}{ll}\underset{\text{constant in }k}{\underbrace{(1-{\Vert W_i\Vert }^2)}}\underset{\text{distance from threshold}}{\underbrace{(\left|W_{ik}\right|-\theta )}}& \text{if }{W}_{ik}\ne 0\\ 0& \text{otherwise.}\end{array}\end{array}$$

#figure

We call this expression the sparsity force. #to-write use that term in the rest of the write-up

#to-write already note informally that this stretches the values equally and therefore is affine (will maintain relative differences between nonzero values)?

Note that the threshold $\theta$ is not fixed: we will see that as $W_i$ gets sparser, ${\Vert W_i\Vert }^2$ gets closer to $1$, which increases the threshold and allows it to get rid of higher and higher entries, until only one is left. But how do we know what values $1-{\Vert W_i\Vert }^2$ will take over time?

A dynamic balance on ${\Vert W_i\Vert }^2$

As before, let’s consider the parallel push, which is the time derivative of ${\Vert W_i\Vert }^2$.

• Feature benefit pushes ${\Vert W_i\Vert }^2$ up with force $(1-{\Vert W_i\Vert }^2){\Vert W_i\Vert }^2$, which is $\mathrm{\Omega }(1)$ when $\mathrm{\Omega }(1)\le {\Vert W_i\Vert }^2\le 1-\mathrm{\Omega }(1)$.
• Reguralization pushes ${\Vert W_i\Vert }^2$ down by $\lambda {\Vert W_i\Vert }_1$, which is initially $\mathrm{\Theta }\left(\lambda \sqrt{m}\right)$, and can only get smaller as $W_i$ gets sparser while maintaining $\Vert W_i\Vert \le 1$.[^5]

Therefore, the push from regularization will always remain sub-constant, and in particular will never be able to push ${\Vert W_i\Vert }^2$ below $1/2$ (since that would require an $\mathrm{\Omega }(1)$ push down to counteract feature benefit when ${\Vert W_i\Vert }^2=1/2$). This means that in long-ish timescales, they will tend to be in balance (technically they could oscillate, but that seems unlikely so let’s assume they don’t): the upwards push on ${\Vert W_i\Vert }^2$ from feature benefit roughly matches the downwards push on ${\Vert W_i\Vert }^2$ from regularization.

#to-think Is this assumption of ${\Vert W_i\Vert }^2$ being static truly realistic? Need to check once I’ve found out what are the dynamics of ${\Vert W_i\Vert }_1$ assuming this. I think we’ll find that the derivative of ${\Vert W_i\Vert }_1$ will be proportional to $\lambda$ and thus the derivative of ${\Vert W_i\Vert }^2$ will be $\approx \lambda \frac{\mathrm{d}{\Vert W_i\Vert }_1}{\mathrm{d}t}$, which proportional to ${\lambda }^2$, so we can make it vanish by setting $\lambda$ arbitrarily low.

Balance happens when

$$(1-{\Vert W_i\Vert }^2){\Vert W_i\Vert }^2=\lambda {\Vert W_i\Vert }_1⟹1-{\Vert W_i\Vert }^2=\frac{\lambda {\Vert W_i\Vert }_1}{{\Vert W_i\Vert }^2}\approx \lambda {\Vert W_i\Vert }_1.$$

Let’s call this the balance condition. What’s great about it is that if we have a guess about what ${\Vert W_i\Vert }_1$ is at some point in time, it also tells us that what $1-{\Vert W_i\Vert }^2$ is, and therefore it tells us that the sparsity force will be

$$\begin{array}{rl}\frac{\mathrm{d}|W_{ik}|}{\mathrm{d}t}& \approx \{\begin{array}{ll}\lambda {\Vert W_i\Vert }_1\underset{\text{distance from threshold}}{\underbrace{(\left|W_{ik}\right|-\theta )}}& \text{if }{W}_{ik}\ne 0\\ 0& \text{otherwise.}\end{array}\end{array}$$

and the current threshold $\theta$ is

$$\theta =\frac{\lambda }{1-{\Vert W_i\Vert }^2}\approx \frac{\lambda }{\lambda {\Vert W_i\Vert }_1}=\frac{1}{{\Vert W_i\Vert }_1}.$$

How fast does it go?

See Feature benefit vs regularization through blowup for a more complicated and probably erroneous previous attempt.

Summing up equation (1) and letting $m^{\prime }:=\mathrm{\#}\left\{k\right|W_{ik}\ne 0\}$ be the number of nonzero weights in $W_i$, we have

$$\begin{array}{rl}-\frac{\mathrm{d}{\Vert W_i\Vert }_1}{\mathrm{d}t}& =\underset{\text{regularization}}{\underbrace{\lambda m^{\prime }}}-\underset{\text{feature benefit}}{\underbrace{(1-{\Vert W_i\Vert }^2){\Vert W_i\Vert }_1}}\\ \text{(by balance condition)}& & =\frac{\lambda }{{\Vert W_i\Vert }^2}(m^{\prime }{\Vert W_i\Vert }^2-{\Vert W_i\Vert }_1^2)& =\frac{\lambda (m^{\prime }{)}^2}{{\Vert W_i\Vert }^2}(\frac{{\Vert W_i\Vert }^2}{m^{\prime }}-{\left(\frac{{\Vert W_i\Vert }_1}{m^{\prime }}\right)}^2)\\ & =\frac{\lambda (m^{\prime }{)}^2}{{\Vert W_i\Vert }^2}\times \underset{\text{``sample variance over nonzero weights''}}{\underbrace{\frac{\sum _{k:W_{ik}\ne 0}{\left(\underset{\text{``deviation from mean''}}{\underbrace{|W_{ik}|-\frac{{\Vert W_i\Vert }_1}{m^{\prime }}}}\right)}^2}{m^{\prime }}}},\end{array}$$

where the last inequality is essentially the identity

$$\mathrm{E}\left[{\mathit{X}}^2\right]-\mathrm{E}[\mathit{X}{]}^2=\mathrm{Var}[\mathit{X}]$$

where the random variable $\mathit{X}$ is drawn by picking a $k$ at uniformly at random in $\left\{k\right|W_{ik}\ne 0\}$ and outputting $|W_{ik}|$.

If $\mathit{X}$’s relative variance is a constant (i.e. if $\mathit{X}$ is “well-rounded”), then

$$\begin{array}{rl}-\frac{\mathrm{d}{\Vert W_i\Vert }_1}{\mathrm{d}t}& =\frac{\lambda (m^{\prime }{)}^2}{{\Vert W_i\Vert }^2}\mathrm{Var}[\mathit{X}]\\ \text{(}\mathit{X}\text{ well-rounded)}& & =\frac{\lambda (m^{\prime }{)}^2}{{\Vert W_i\Vert }^2}\mathrm{\Theta }(\mathrm{E}[\mathit{X}{]}^2)& =\mathrm{\Theta }\left(\frac{\lambda }{{\Vert W_i\Vert }^2}{\Vert W_i\Vert }_1^2\right)\\ \text{(assuming }{\Vert W_i\Vert }^2=\mathrm{\Theta }(1)\text{)}& & =\mathrm{\Theta }\left(\lambda {\Vert W_i\Vert }_1^2\right),\end{array}$$

or if we define $w:=\frac{1}{{\Vert W_i\Vert }_1}$ (which is a proxy for the “typical nonzero weight”, and is $\approx \theta$ when ${\Vert W_i\Vert }^2\approx 1$), this becomes

$$\frac{\mathrm{d}w}{\mathrm{d}t}=\mathrm{\Theta }(\lambda ),$$

so $w(t)=w(0)+\mathrm{\Theta }(\lambda t)$ and

$${\Vert W_i(t)\Vert }_1=\frac{1}{\mathrm{\Theta }(w(0)+\lambda t)}=\frac{1}{\mathrm{\Theta }(\frac{1}{\sqrt{m}}+\lambda t)}$$

with high probability in $m$.

Will the relative variance be a constant?

Empirically, the relative variance is indeed a constant not too far from $1$ (see plot below). But why is that?

Suppose that currently $W_{i1}\ge W_{i2}\ge \cdots \ge W_{im}\ge 0$, and let’s look at the relative difference between the biggest weight $W_{i1}$ and some other weight $W_{ik}>0$, i.e.

$${\gamma }_k:=\frac{W_{i1}-W_{ik}}{W_{i1}}=1-\frac{W_{ik}}{W_{i1}}.$$

Using relative derivatives, we have

$$\frac{\mathrm{d}{\gamma }_k}{\mathrm{d}t}=-\frac{\mathrm{d}(W_{ik}/W_{i1})}{\mathrm{d}t}=-\frac{W_{ik}}{W_{i1}}(\frac{\mathrm{d}{W}_{ik}/\mathrm{d}t}{W_{ik}}-\frac{\mathrm{d}{W}_{i1}/\mathrm{d}t}{W_{i1}}).$$

Since feature benefit is a relative force, it contributes nothing to the difference of the relative derivatives of $W_{ik}$ and $W_{i1}$, so we just have the contribution from regularization

$$\begin{array}{rl}\frac{\mathrm{d}{\gamma }_k}{\mathrm{d}t}& =-\frac{W_{ik}}{W_{i1}}(\frac{-\lambda }{W_{ik}}-\frac{-\lambda }{W_{i1}})\\ & =\frac{\lambda W_{ik}}{W_{i1}}(\frac{1}{W_{ik}}-\frac{1}{W_{i1}})\\ & =\frac{\lambda }{W_{i1}}(1-\frac{W_{ik}}{W_{i1}})\\ & =\frac{\lambda }{W_{i1}}{\gamma }_k.\end{array}$$

Note that this differential equation doesn’t involve $W_{ik}$ at all! This means that there is a single function $\gamma (t)$ defined by

$$\{\begin{array}{rl}\gamma (0)& =1\\ \frac{\mathrm{d}\gamma }{\mathrm{d}t}(t)& =\frac{\lambda }{W_{i1}(t)}\gamma (t)\end{array}$$

such that for all $k$, as long as $W_{ik}(t)>0$,

$$1-\frac{W_{ik}(t)}{W_{i1}(t)}=\gamma (t)(1-\frac{W_{ik}(0)}{W_{i1}(0)})\Rightarrow W_{ik}(t)=\underset{\text{doesn't depend on }k}{\underbrace{W_{i1}(t)(1-\gamma (t))}}+\underset{\text{doesn't depend on }k}{\underbrace{\frac{\gamma (t)W_{i1}(t)}{W_{i1}(0)}}}{W}_{ik}(0).$$

In other words, the relative spacing of the nonzero weights never change: their change between times $0$ and $t$ is a single affine transformation.

Since the relative variance is scaling-invariant, we can think of this affine transformation as a simple translation. The value of the relative variance of the remaining nonzero weights $W_{i1}(t),\dots ,W_{i{m}^{\prime }}(t)$ at some point in time must be of the following form:

• take the initial values $W_{i1}(0),\dots ,W_{im}(0)$,
• translate them left by some amount which leaves $m^{\prime }$ weights positive,
• drop the values that have become $\le 0$,
• then compute the relative variance of what’s left.

In particular, the relative variance when $m^{\prime }$ weights are left must lie between the relative variance of

$$(W_{i1}(0)-W_{i(m^{\prime }+1)}(0),W_{i2}(0)-W_{i(m^{\prime }+1)}(0),\dots ,W_{i{m}^{\prime }}(0)-W_{i(m^{\prime }+1)}(0))$$

and the relative variance of

$$(W_{i1}(0)-W_{i{m}^{\prime }}(0),W_{i2}(0)-W_{i{m}^{\prime }}(0),\dots ,0)$$

(since these extremes have the same variance but the latter has a smaller mean).

These relative variances are functions of $m^{\prime }$ and the initial value of $W_i$ only, and (when $W_i$ is made of mean-$0$ normals) they will be $\mathrm{\Theta }(1)$ with high probability in $m^{\prime }$. The plot below shows these lower and upper values for $W_i(0)$ itself (in red) and for an idealized version of $W_i(0)$ that hits regular percentiles (in pink, dashed).

We can see that the orange curve does indeed lie within the red curves, and that the red and pink curves only start to diverge significantly at later time steps when $m^{\prime }$ is smaller.