AI RESEARCH
Transformers Provably Learn Sparse XOR with Polylogarithmic Parameters
arXiv CS.LG
•
ArXi:2502.07553v2 Announce Type: replace Learning sparse parity functions has become a theoretical testbed for studying feature learning in neural networks. However, existing analyses primarily focus on Feed-Forward Neural Networks (FFNNs). Meanwhile, theoretical understanding of Transformers in this setting remains limited, despite their empirical success and structural suitability for discovering sparse over long sequences. To address this gap, we analyze how a single-layer, two-head Transformer learns the sparse XOR problem.