Let me restate your proposed setting first to make sure I follow.
We want to compute , i.e., a scalar function that naively requires n layers of width d each to compute exactly.
The network we are now interested in is one of width and depth -- so it can in principle trivially compute instances of in parallel.
We are interested in a regime where we compute more than such instances, so we assume we compute (sparse) features simultaneously.
Your proposal is then to divide the network into blocks of width , and assign a subset to feature $i$. These blocks correspond to the binary codewords in the post.
I definitely agree that this works exactly if there are no collisions. This sounded too-good-to-be-true to me at first, but then I realized that’s because that’ll lead to quite a bit of leakage to inactive features—the construction in the post is also in principle capable of exactly computing an active feature in the collision-less case, but it turns out to be more favorable loss-wise to undershoot active features to reduce leakage to inactive features. I suspect this would also be the case if we managed to elicit a construction like this through training.
Hmm I was viewing the undershooting of the ReLU as being a minor correction. After all it’s not like the expected value is taken to , it’s just weakly interpolated there. In either case we can always modify to undershoot or whatever is required by the design.
Yeah leakage to inactive features is always the concern. MSE is pretty lenient about this—some when considering the scenario use to punish outliers. Like MSE doesn’t care very much if a few inactive features falsely activate with high magnitude as long as it’s only with probability. I guess helps here but would need to do the calculations properly.
But yeah given linear bottleneck width in and random codes (unsure about designed ones) there’s an exponentially small w.r.t chance that a given codeword of length will have no collisions. So the construction is very unlikely to be exactly computing.
All you gain is that the network can be layers long and you can solve the compressed computation setup for it, and the only thing that matters for MSE is the bounds on the final output. So you can imagine having a massive classifier network for instance which just outputs or at the end. And knowing this you truncate all the blocks to output values between and , to bound the error.
By the way, have you tried higher values of , i.e: ? Do you end up with the same results? It would be kinda cool if you got a range of families of constructions for different values of .
I have run it for higher values, yes. gives a very similar solution to . I just tried it for and it also appears to give something similar but with wider spread in codeword size. However, this appears to just be an optimization failure: the -trained network loses to the -trained network on the objective. I suppose the shape of the gradient for very high is just not great: it becomes dominated by the most extreme outliers giving the optimizer too noisy a signal. I haven’t thought about this too much, though.
Thank you!
Let me restate your proposed setting first to make sure I follow.
We want to compute
The network we are now interested in is one of width
We are interested in a regime where we compute more than
Your proposal is then to divide the network into
I definitely agree that this works exactly if there are no collisions. This sounded too-good-to-be-true to me at first, but then I realized that’s because that’ll lead to quite a bit of leakage to inactive features—the construction in the post is also in principle capable of exactly computing an active feature in the collision-less case, but it turns out to be more favorable loss-wise to undershoot active features to reduce leakage to inactive features. I suspect this would also be the case if we managed to elicit a construction like this through training.
This was a long-winded way of saying: I agree.
Yes, that’s the scenario I was intending.
Hmm I was viewing the undershooting of the ReLU as being a minor correction. After all it’s not like the expected value is taken to
Yeah leakage to inactive features is always the concern. MSE is pretty lenient about this—some when considering the scenario use
But yeah given linear bottleneck width in
All you gain is that the network can be
By the way, have you tried higher values of
I have run it for higher values, yes.