4 ms·

> Based on this proof, we provide an algorithm that, given a deep ReLU network, finds the explicit weights of the corresponding shallow network. I’m out of dat

> Based on this proof, we provide an algorithm that, given a deep ReLU network, finds the explicit weights of the corresponding shallow network. I’m out of date on the research, but I suspect the real value here is the algorithm. Sounds like some version of this could eventually help reduce inference time

WithinReason 3y ago
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.
idontpost 3y ago
[dead]
tripplyons 3y ago
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.
- uoaei 3y ago
  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.
- alok-g 3y ago
  +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. :-)
coderenegade 3y ago
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.

WithinReason 3y ago

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.

idontpost 3y ago

[dead]

tripplyons 3y ago

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.

uoaei 3y ago
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.
alok-g 3y ago
+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. :-)

coderenegade 3y ago

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.