Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Any Deep ReLU Network Is Shallow

arxiv.org

Post reply on HN
Print view View original

51–60 of 62 posts

Re: Any Deep ReLU Network Is Shallow

#51

Post by radarsat1 »

anonymoushn wrote: post #43
cellis wrote: post #42

Earlier quoted context omitted.

Could you point to an inductive proof of this?

I don't think you need induction, you can just use the fact that the input is a fixed size and the output is a fixed size. The "constructive" proof is, feed in all possible inputs, record the outputs in a lookup table.

Which obviously only works for the training data. It's a good example to remond that the whole point is to predict unseen input output pairs (generalization) so what is important is not so much the ability to fit a function, but to interpolate and extrapolate that function. And different bases and different fitting algorithms will have different behaviour in that respect.

Re: Any Deep ReLU Network Is Shallow

#52

Post by alok-g »

tripplyons wrote: post #20
curiousllama wrote: post #6

Earlier quoted context omitted.

> 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

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.

+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. :-)

Re: Any Deep ReLU Network Is Shallow

#53

Post by alok-g »

foota wrote: post #39

Another maybe silly thought, but if any relu network could be written in three layers, does this allow for a hyper efficient ReLu only hardware for ml where the pipeline is fixed?

See these comments on the same post if not already.

https://news.ycombinator.com/item?id=36453136

Short answer to your question: Not true in general.

Re: Any Deep ReLU Network Is Shallow

#55

Post by [deleted] »

radarsat1 wrote: post #51
anonymoushn wrote: post #43

Earlier quoted context omitted.

I don't think you need induction, you can just use the fact that the input is a fixed size and the output is a fixed size. The "constructive" proof is, feed in all possible inputs, record the outputs in a lookup table.

Which obviously only works for the training data. It's a good example to remond that the whole point is to predict unseen input output pairs (generalization) so what is important is not so much the ability to fit a function, but to interpolate and extrapolate that function. And different bases and different fitting algorithms will have different behaviour in that respect.

[deleted]

Re: Any Deep ReLU Network Is Shallow

#56

Post by anonymoushn »

radarsat1 wrote: post #51
anonymoushn wrote: post #43

Earlier quoted context omitted.

I don't think you need induction, you can just use the fact that the input is a fixed size and the output is a fixed size. The "constructive" proof is, feed in all possible inputs, record the outputs in a lookup table.

Which obviously only works for the training data. It's a good example to remond that the whole point is to predict unseen input output pairs (generalization) so what is important is not so much the ability to fit a function, but to interpolate and extrapolate that function. And different bases and different fitting algorithms will have different behaviour in that respect.

What do you mean? It works for all possible inputs.

Re: Any Deep ReLU Network Is Shallow

#57

Post by ndriscoll »

godelski wrote: post #44
WithinReason wrote: post #3

I thought it was known for a long time that any function can be represented with a neural network with a single layer. It's an almost trivial finding if you think about it: imagine you have a steep step function that looks something like this: __/^^ with the non-zero derivative in a small range, e.g. 0.000-0.001 (or ϵ if you like). Let's call this f. You can piece together any function from these tiny pieces as ∑ᵢ cᵢ…

I think you're being a little too quick to jump to the answer. There are plenty of functions where this isn't true. Two easy examples are jump discontinuities (one that looks like this ____----- but more wiggly) (known as piecewise continuous) and functions with hole. These cannot be approximated to arbitrary accuracy, even with an infinite number of them. You need to pay close attention to the wording in the approxi…

> Borel means that it includes all finite open intervals in the real numbers. So (0,1) but not [0,1].

The Borel algebra is generated by open sets, but it includes complements (and therefore closed sets) as well. In fact it's also generated by closed sets. The Borel algebra of R also contains sets like the rationals and the irrationals. The types of sets that aren't included in the Borel algebra (but are in the Lebesgue) are nasty things like (some) subsets of the cantor set.

Re: Any Deep ReLU Network Is Shallow

#58

Post by p1esk »

radarsat1 wrote: post #51
anonymoushn wrote: post #43

Earlier quoted context omitted.

I don't think you need induction, you can just use the fact that the input is a fixed size and the output is a fixed size. The "constructive" proof is, feed in all possible inputs, record the outputs in a lookup table.

Which obviously only works for the training data. It's a good example to remond that the whole point is to predict unseen input output pairs (generalization) so what is important is not so much the ability to fit a function, but to interpolate and extrapolate that function. And different bases and different fitting algorithms will have different behaviour in that respect.

We are talking about converting a trained neural network into a lookup table.

Re: Any Deep ReLU Network Is Shallow

#59

Post by radarsat1 »

p1esk wrote: post #58
radarsat1 wrote: post #51

Earlier quoted context omitted.

Which obviously only works for the training data. It's a good example to remond that the whole point is to predict unseen input output pairs (generalization) so what is important is not so much the ability to fit a function, but to interpolate and extrapolate that function. And different bases and different fitting algorithms will have different behaviour in that respect.

We are talking about converting a trained neural network into a lookup table.

Ah, get your point and misunderstood. I thought you were talking about comparing the neural network to a lookup table, not modeling the network itself. In that case the proof is only true if you consider the digital implementation of the neural network. Since it's a continuous function this proof would be impossible mathematically, as the domain is not enumerable. But if you consider only every possible float32 for example, then it works.

In any case it's kind of a useless statement that way as it says nothing about neural networks. You can replace "neural network" with "function" and it still works.

Re: Any Deep ReLU Network Is Shallow

#60

Post by p1esk »

radarsat1 wrote: post #59
p1esk wrote: post #58

Earlier quoted context omitted.

We are talking about converting a trained neural network into a lookup table.

Ah, get your point and misunderstood. I thought you were talking about comparing the neural network to a lookup table, not modeling the network itself. In that case the proof is only true if you consider the digital implementation of the neural network. Since it's a continuous function this proof would be impossible mathematically, as the domain is not enumerable. But if you consider only every possible float32 for e…

You're right, but the idea of looking things up instead of computing them can be useful when we are constrained by the available compute power. I'm not talking about simple lookup tables, of course, but if you look at recent trends in large foundational models, there's a lot of interest in efficient access to external information, or ways to pay attention to the inputs selectively, rather than in all-to-all fashion (e.g. landmark attention tokens).
Post reply on HN