4 ms·
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 Theor
by 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 agoThey (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 agoI would assume the distinction between trained and untrained networks is a constant factor at best.
- a1369209993 3y agoI 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.)