Irrespective of training, the solution given in the post should theoretically work for fairly general as well, correct?
Suppose , with inputs , , and . [If can modify so that it is in an arbitrarily small region around the origin, while staying in required form]
Divide the network width into blocks of size .
Have the th feature write to a subset of blocks (With corresponding to the binary codewords in the post). [i.e: Write to the blocks so that if there are no collisions between active codewords, will be the contents of the block.]
Now apply the remainder of (apart from ) block-wise. And then read off as usual, while applying .
The blocks in without collisions will have computed exactly. And then we just need errors to not blow up on collided blocks. If we are told that the final hidden layer of is bounded on the typical input distribution then can append a truncation layer to bound how disruptive collided blocks can be.
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.
Interesting result.
Irrespective of training, the solution given in the post should theoretically work for fairly general
Suppose
Divide the network width into
Have the
Now apply the remainder of
The blocks in
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.