4 ms·

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

by WithinReason 3y ago

tdullien 3y ago
Yep
throwawaymaths 3y ago
I'm not sure it's exponential, but it is dramatic.
joe_the_user 3y ago
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.
- a1369209993 3y ago
  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.
  - uoaei 3y ago
    I would assume the distinction between trained and untrained networks is a constant factor at best.
    - a1369209993 3y ago
      I meant 'trained' networks in contrast to totally-synthetic intentionally-pathological networks like my 2abs-1 example. (It could be that only pathological cases give bad results - similar to how (Hindley-Milner) type inference is EXPTIME-complete but works fine for ~all real world programs - but that seems unlikely.)
youssefabdelm 3y ago
I guess people could use it as a form of post-training "compression"
- coderenegade 3y ago
  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 suspect the trade-off for a shallow network is an exponential explosion in weights and computation.

tdullien 3y ago

Yep

throwawaymaths 3y ago

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

joe_the_user 3y ago

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.

a1369209993 3y ago
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.
- uoaei 3y ago
  I would assume the distinction between trained and untrained networks is a constant factor at best.
  - a1369209993 3y ago
    I meant 'trained' networks in contrast to totally-synthetic intentionally-pathological networks like my 2abs-1 example. (It could be that only pathological cases give bad results - similar to how (Hindley-Milner) type inference is EXPTIME-complete but works fine for ~all real world programs - but that seems unlikely.)

youssefabdelm 3y ago

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

coderenegade 3y ago
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.