Transformers Provably Learn Sparse XOR with Polylogarithmic Parameters

Yaomengxi Han, Debarghya Ghoshdastidar

Learning sparse parity functions has become a theoretical testbed for studying feature learning in neural networks. However, existing analyses primarily focus on Feed-Forward Neura…