I suspect the trade-off for a shallow network is an exponential explosion in weights and computation.

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.

I haven't read the paper, but most of the time, in order to achieve matching outputs with less layers, you will need exponentially more neurons per layer.

If you have infinite parallelism I believe the shallow network would be faster, but deep networks will use less total operations and will be faster in practice.

There may be some utility to optimizing a given neural network to exploit the features of a given computational architecture. The point would be to expand the width of each layer to hit the limits of your hardware's parallelism. I.e., partition the network into n parts and shallow-ize each one to produce a new neural network with n layers, each of which being roughly as wide as your p parallel computational channels.

+1

This is how it is for logic design using gates, and I believe that's not a coincidence.

Finding the right optimum between parallel and deep for logic design is computationally intensive itself, hence it often comes down to experiencial learning. The latter implies potential use of machine learning for that optimization. And it contunues ... lived happily thereafter. :-)

If you can go back and forth between representations with better than quadratic scaling, it would mean RNNs with infinite context lengths and no vanishing gradient. You wouldn't need transformers.