A note on $L^2 \leftrightarrow L^1$ duality in shallow homogeneous nets

A new technical note explains that in a shallow homogeneous neural net, minimizing the L2 norm of the parameters is equivalent to minimizing the L1 norm of a measure over unit-norm neurons, a duality the author says is directly relevant to sparse autoencoders (SAEs) and their tendency toward sparsity. The note derives the equivalence by reparameterizing a general matrix factorization F = AB^T, showing that at optimum the row norms of A and B are equal and that the inner optimization reduces to a sum of nonnegative scale variables s_i over rank-one unit-norm matrices.

If you’ve been around the deep learning theory block long enough to get to know the locals, you’ve probably heard something like this at some point: In a shallow homogeneous neural net, minimizing the $L^2$-norm of the parameters is equivalent to minimizing the $L^1$-norm of a measure over unit-norm neurons. This makes a link between “aggregate $L^2$ land” and “sparse $L^1$ land.” It’s also directly relevant to SAEs, which are pretty much shallow homogeneous nets, and it’s the first place you should start when trying to understand why they tend towards sparsity. As far as I know, incredibly, this project has not yet been done. @The entire field of mechinterp. …anyways, Dhruva brought this up recently and asked me to write something explaining the idea. I’ve explained this a few times to different people, but I don’t actually know a good beginner ref for it, so I said yes. To get the idea, let’s start with a general matrix factorization problem. Let $\mathbf{A} \in \mathbb{R}^{m \times h}$ and $\mathbf{B} \in \mathbb{R}^{n \times h}$ be the two factors of a matrix $\mathbf{F} = \mathbf{AB}^\top$.<sup 1 fn:1 </sup Suppose we want to minimize some loss $\mathcal{L} \mathbf{F} $, which might for example be the distance between $\mathbf{F}$ and some target matrix. Let’s also toss in an $L^2$ parameter norm penalty with coefficient $\lambda$. We’ve got the following optimization problem on our hands: Note that I should really be saying $\operatorname{argmin}$ instead of $\min$ here, since we’re interested in the values of $\mathbf{A}, \mathbf{B}$ more than the value of the objective. As is common, we’ll just abuse notation a bit and leave it as understood that, when we describe an optimization process, we’re interested in both minimum and minimizer. Let’s let $\mathcal{F}$ be the set of realizable values for $\mathbf{F}$ under this parameterization. That is, it’s the set of all $\mathbf{F} \in \mathbb{R}^{m \times n}$ such that $\text{rank} \mathbf{F} \le h$. We can rewrite our optimization problem in the following “inner-outer” form: $$ \underbrace{ \min {\mathbf{F} \in \mathcal{F}} \mathcal{L} \mathbf{F} } {\text{outer opt. over }\mathbf{F}} \quad + \quad \frac{\lambda}{2} \cdot \underbrace{ \min {\mathbf{A},\mathbf{B}} \left \| \mathbf{A} \| \text{F}^2 + \|\mathbf{B}\| \text{F}^2 \right \ \ \text{s.t.} \ \ \mathbf{A} \mathbf{B}^\top = \mathbf{F}. } {\text{inner opt. over }\mathbf{A},\mathbf{B}\text{ given }\mathbf{F}} $$ The outer objective is not exactly minimized, since $\mathbf{F}$ appears in the inner term, too. However, the inner objective is always minimized — whatever $\mathbf{F}$ ends up being, we’re sure as heck gonna realize it the most efficient way possible, because why wouldn’t we? It’s free points. Anyways, the story at hand is about this inner loop and some easy ways we can win free points. First, let’s write out $$ \mathbf{F} = \sum {i=1}^h \mathbf{a} i \mathbf{b} i^\top, $$ where $\mathbf{a} i, \mathbf{b} i$ are the $i$-th rows of $\mathbf{A}, \mathbf{B}$. First key observation: if $|\mathbf{a} i| \neq |\mathbf{b} i |$, then we can get free points by rescaling like $$ \mathbf{a} i \rightarrow \mathbf{a} i \ \cdot \ \sqrt{\frac{\| \mathbf{b} i \|}{\| \mathbf{a} i \|}}, \qquad \mathbf{b} i \rightarrow \mathbf{b} i \ \cdot \ \sqrt{\frac{\| \mathbf{a} i \|}{\| \mathbf{b} i \|}}. $$ We can thus be assured that, at optimum, $|\mathbf{a} i| =|\mathbf{b} i |$. Let’s reparameterize to separate the norm and unit-vector degrees of freedom: $$ s i := \| \mathbf{a} i \|^2, \quad \hat{\mathbf{a}} i = \text{unit} \mathbf{a} i , \quad \hat{\mathbf{b}} i = \text{unit} \mathbf{b} i . $$ Let’s also let $\hat{\mathbf{M}} i := \hat{\mathbf{a}} i \hat{\mathbf{b}} i^\top$ be the rank-one, unit-norm matrix built from $\hat{\mathbf{a}} i, \hat{\mathbf{b}} i$. We can now rewrite the inner-loop optimization: $$ \min { s i, \hat{\mathbf{M}} i {i=1}^h} \sum {i=1}^h s i \quad \text{s.t.} \quad s i \ge 0 \ \ \text{and} \ \ \mathbf{F} = \sum {i=1}^h s i \hat{\mathbf{M}} i. $$ Note that now nothing is squared in the optimization objective. Things are starting to look $L^1$. Actually, we can relax the problem to allow $s i <0$ and get this equivalent problem: That’s explicitly an $L^1$ objective on the weights $s i$. To summarize the point here: penalizing the $L^2$-norm of two factors was equivalent to penalizing the $L^1$ norm of their product. For good measure ha , we can move to measure-theoretic language by taking $h \rightarrow \infty$. I’m not going to attempt to be rigorous here; I just want to point out that the inner optimization takes on the continuum formulation $$ \min {\mu} \int \mathcal{M} |d \mu| \qquad \text{s.t.} \qquad \int \mathcal{M} \hat{\mathbf{M}} \ d \mu = \mathbf{F}, $$ where $\mathcal{M}$ is the set of rank-one unit-norm matrices, and $\mu$ is a measure over that set that need be neither nonnegative nor integrate to one . At finite $h$, this formulation is still valid, but $\mu$ is just constrained to be a sum of at most $h$ atoms. Before moving on: the point is the form of the inner-loop optimization, not the solution, since after all we’re now going to go on to ReLU nets, for which there won’t be a closed-form solution. But since it exists, and curious minds might inquire, I’ll note that in this mfac case the solution to the inner loop is to have $\mu$ be a sum of $\text{rank} \mathbf{F} $ atoms, one for each SVD term of $\mathbf{F}$. Let’s set up a problem involving ReLU nets now. Again let $\mathbf{A} \in \mathbb{R}^{m \times h}$ and $\mathbf{B} \in \mathbb{R}^{n \times h}$, and let $$ {f} { \mathbf{A},\mathbf{B} }: \mathbf{x} \mapsto \mathbf{B} \ \text{ReLU} \mathbf{A^\top x} $$ be the vector-valued function at hand. Our optimization problem now takes the form $$ \min {\mathbf{A},\mathbf{B}} \left \mathcal{L} f { \mathbf{A},\mathbf{B} } + \frac{\lambda}{2} \left \| \mathbf{A} \| \text{F}^2 + \|\mathbf{B}\| \text{F}^2 \right \right . $$ This again admits the inner-outer form $$ \underbrace{ \min {f \in \mathcal{F}} \mathcal{L} f } {\text{outer opt. over }f} \quad + \quad \frac{\lambda}{2} \cdot \underbrace{ \min {\mathbf{A},\mathbf{B}} \left \| \mathbf{A} \| \text{F}^2 + \|\mathbf{B}\| \text{F}^2 \right \ \ \text{s.t.} \ \ f { \mathbf{A},\mathbf{B} } = f } {\text{inner opt. over }\mathbf{A},\mathbf{B}\text{ given }f} $$ for suitable $\mathcal{F}$. We have neuronwise rescaling symmetry between weight matrix rows $ \mathbf{a} i, \mathbf{b} i $, and we can invoke the same tricks as before. We just need some language to describe single-neuron functions, which are the generalization of rank-one matrices. Let $\hat{g} {\hat{\mathbf{a}}, \hat{\mathbf{b}}} : \mathbf{x} \mapsto \hat{\mathbf{b}} \ \text{ReLU} \hat{\mathbf{a}}^\top \mathbf{x} $ be a single-neuron function with unit vector inputs and outputs, and let $$ \mathcal{G} = \left\{\hat{g} { \hat{\mathbf{a}},\hat{\mathbf{b}} } \ \ \ \forall \ \ \ \hat{\mathbf{a}} \in \mathbb{S}^m, \hat{\mathbf{b}} \in \mathbb{S}^n \right\}. $$ The inner loop of the optimization takes the form $$ \min {\mu} \int \mathcal{G} |d \mu| \qquad \text{s.t.} \qquad \int \mathcal{G} \hat{g} \ d \mu = f, $$ where $\mu$ is a neither nonnegative nor normalized measure over $\mathcal{G}$. This is the “ta-dah” moment: we’ve transformed a problem with no $L^1$ in it at all into one with an explicit $L^1$ norm objective. If you doubt that the final here should really be thought of as $L^1$, then you could instead fix $\mu {\text{unif}}$ to be the uniform measure over $\mathcal{G}$ and instead optimize over a “weight function” $w$ like $$ \min {w} \int \mathcal{G} |w| \cdot d \mu \text{unif} \qquad \text{s.t.} \qquad \int \mathcal{G} \hat{g} \cdot w \cdot d \mu \text{unif} = f. $$ My various abuses of notation are catching up to me, though, so I’ll stop here. Thanks to Arthur Jacot for teaching me this back in the day. If the derivation below loses you, I suggest you work it through in a scalar case with $m = n = h = 1$. ↩ fnref:1