[posted this in parallel with Kaarel’s answer below] This is Bayesian learning, and here the answer is yes. Kaarel actually has a really cool construction of depth 2 that can do xor of 1000 bits.
Of course SGD can’t learn (a subset-level) xor by standard learning results. However there are no impossibility results on SGD-learning a version of xor “with advice”, where the target is a concatenation of all xors over a binary tree (so for 4 bits, this is the 3-dimensional output (xor(x1, x2), xor(x3, x4), xor(x1, x2, x3, x4)). Here lazy/ kernel methods still provably require exponential time or exponential sample complexity but empirical methods just work.
This is a regime where a dynamical version of our mean field results suggests that in infinite width mean field settings, things should stabilize in width if one chooses lr carefully (essentially in a Greg Yang sense). This does seem to happen, though the width stabilization is slow. In particular I am working with a collaborator/MARS mentee, Sergey, on trying to analyze the SGD/Adam results of various deep ladder xor networks (currently up through 16 bit parity) via mean field-esque methods. The weird result Sergey sees is that for 8-bit parity, there’s some learning of the corresponding feature already at the first layer whereas for 16-bit parity the model definitively first learns the 4- and 8-bit xors at early layers and then combines them into 16-bit xor
[posted this in parallel with Kaarel’s answer below] This is Bayesian learning, and here the answer is yes. Kaarel actually has a really cool construction of depth 2 that can do xor of 1000 bits.
Of course SGD can’t learn (a subset-level) xor by standard learning results. However there are no impossibility results on SGD-learning a version of xor “with advice”, where the target is a concatenation of all xors over a binary tree (so for 4 bits, this is the 3-dimensional output (xor(x1, x2), xor(x3, x4), xor(x1, x2, x3, x4)). Here lazy/ kernel methods still provably require exponential time or exponential sample complexity but empirical methods just work.
This is a regime where a dynamical version of our mean field results suggests that in infinite width mean field settings, things should stabilize in width if one chooses lr carefully (essentially in a Greg Yang sense). This does seem to happen, though the width stabilization is slow. In particular I am working with a collaborator/MARS mentee, Sergey, on trying to analyze the SGD/Adam results of various deep ladder xor networks (currently up through 16 bit parity) via mean field-esque methods. The weird result Sergey sees is that for 8-bit parity, there’s some learning of the corresponding feature already at the first layer whereas for 16-bit parity the model definitively first learns the 4- and 8-bit xors at early layers and then combines them into 16-bit xor