Yep

I'm not sure it's exponential, but it is dramatic.

From the paper:

    Corollary 1. Given a ReLU network N : Rn → Rm, the shallow 
    network S : Rn → Rm of depth L = 3, as specified in the proof 
    of Theorem 1, has width bounded by 
    max{2n + k, 2n + p, 2 · p · m}

I think p might be the number of layers but I'm not sure and I'm sure about k at all.

So it they might be claiming a pretty tight bound in on weights.

They (suspiciously but not necessarily intentionally) avoid calling attension to it but:

> Let ({fω}ω∈Ω,Ω) be the decomposition that corresponds to N. Label the parts 1,...,p.

p is the number of regions the deep network divides R^n into, and is in general exponential in the network depth. (Eg consider R^1 = [-1,+1], L[k](x) = 2*abs(x)-1 ∀k (where abs(x) = x - 2*ReLU(-x), IIRC), which divides R^1 into 2^D equal segments using only D individual ReLUs, assuming I wrote the formulas down correctly.)

So for a arbitrary deep network the shallow network size is definitely exponential in input depth, and while it's not clear whether that's true for typical 'trained' deep networks, I would be surprised if it wasn't.

I would assume the distinction between trained and untrained networks is a constant factor at best.

I meant 'trained' networks in contrast to totally-synthetic intentionally-pathlogical networks like my 2abs-1 example. It could be similar to how (Hindley-Milner) type inference is EXPTIME-complete but works fine for ~all real world programs; that just seems unlikely.

I guess people could use it as a form of post-training "compression"

The best use case would be if you can efficiently switch between representations. Shallow nets don't suffer from the vanishing gradient problem, so you could have very, very deep RNNs, convert to a shallow net for the gradient update, and then convert back to an RNN for the next rollout. Of course, most RNNs track an internal state, which isn't considered in the paper, but overcoming that limitation could make RNN training effective for long enough rollouts that transformers are no longer needed, especially given that RNNs scale better for long sequences than transformers do.