The Strong Lottery Ticket Hypothesis for Multi-Head Attention Mechanisms
The strong lottery ticket hypothesis (SLTH) conjectures that high-performing
subnetworks, called strong lottery tickets (SLTs), are hidden in randomly
initialized neural networks. Although recent theoretical studies have
established the SLTH across various neural architectures, the SLTH for
transformer architectures still lacks theoretical understanding. In particular,
the current theory of the SLTH does not yet account for the multi-head
attention (MHA) mechanism, a core component of transformers. To address this
gap, we introduce a theoretical analysis of the existence of SLTs within MHAs.
We prove that, if a randomly initialized MHA of H heads and input dimension
d has the hidden dimension O(dlog(Hd^{3/2})) for the key and value, it
contains an SLT that approximates an arbitrary MHA with the same input
dimension with high probability. Furthermore, by leveraging this theory for
MHAs, we extend the SLTH to transformers without normalization layers. We
empirically validate our theoretical findings, demonstrating that the
approximation error between the SLT within a source model (MHA and transformer)
and an approximate target counterpart decreases exponentially by increasing the
hidden dimension of the source model.
690d5a51ad2597bf6c464c92
Hikari Otsuka
claimed_verified
2025-11-07T10:28:50.332Z
676a62adaeb3bcd701e23c1b
https://cdn-avatars.huggingface.co/v1/production/uploads/676a62adaeb3bcd701e23c1b/Ktei5ou531-00r51q0bdO.png
Hikari Otsuka
h-otsuka
user
h-otsuka
690d5a51ad2597bf6c464c93
Daiki Chijiwa
690d5a51ad2597bf6c464c94
Yasuyuki Okoshi
690d5a51ad2597bf6c464c95
Daichi Fujiki
690d5a51ad2597bf6c464c96
Susumu Takeuchi
690d5a51ad2597bf6c464c97
Masato Motomura
The Strong Lottery Ticket Hypothesis for Multi-Head Attention Mechanisms
The strong lottery ticket hypothesis (SLTH) conjectures that high-performing
subnetworks, called strong lottery tickets (SLTs), are hidden in randomly
initialized neural networks. Although recent theoretical studies have
established the SLTH across various neural architectures, the SLTH for
transformer architectures still lacks theoretical understanding. In particular,
the current theory of the SLTH does not yet account for the multi-head
attention (MHA) mechanism, a core component of transformers. To address this
gap, we introduce a theoretical analysis of the existence of SLTs within MHAs.
We prove that, if a randomly initialized MHA of H heads and input dimension
d has the hidden dimension O(dlog(Hd^{3/2})) for the key and value, it
contains an SLT that approximates an arbitrary MHA with the same input
dimension with high probability. Furthermore, by leveraging this theory for
MHAs, we extend the SLTH to transformers without normalization layers. We
empirically validate our theoretical findings, demonstrating that the
approximation error between the SLT within a source model (MHA and transformer)
and an approximate target counterpart decreases exponentially by increasing the
hidden dimension of the source model.
Theoretical analysis proves the existence of strong lottery tickets within multi-head attention mechanisms and extends the strong lottery ticket hypothesis to transformers without normalization layers.
strong lottery ticket hypothesis strong lottery tickets multi-head attention transformers normalization layers