The Lipschitz Constant of Self-Attention

By Hyunjik Kim, George Papamakarios, Andriy Mnih. 2020

231 citations recorded by the source corpus.

Lipschitz constants of neural networks have been explored in various contexts in deep learning, such as provable adversarial robustness, estimating Wasserstein distance, stabilising training of GANs, and formulating invertible neural networks. Such works have focused on bounding the Lipschitz constant of fully connected or convolutional networks, composed of linear maps and pointwise non-linearities. In this paper, we investigate the Lipschitz constant of self-attention, a non-linear neural network module widely used in sequence modelling. We prove that the standard dot-product self-attention is not Lipschitz, and propose an alternative L2 self-attention that is Lipschitz. We derive an upper bound on the Lipschitz constant of L2 self-attention and provide empirical evidence for its asymptotic tightness. To demonstrate the practical relevance of the theory, we formulate invertible self-attention and use it in a Transformer-based architecture for a character-level language modelling task.

Subfields: Cognitive Neuroscience, Experimental and Cognitive Psychology, Statistical and Nonlinear Physics, Model Architectures

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Cognitive Neuroscience

In Experimental and Cognitive Psychology

In Statistical and Nonlinear Physics

In Model Architectures

Citations in the corpus

Attention is Not All You Need: Pure Attention Loses Rank Doubly Exponentially with Depth (2021, methodology): “A linearized form of self-attention was also found to exhibit a depth phase transition [LWS + 20]; and the Lipschitz constant of self-attention was analyzed by [KPM20].”
On the Effectiveness of Lipschitz-Driven Rehearsal in Continual Learning (2022, neutral): “Moreover, our approximation cannot be applied to not-Lipschitz continuous layers ( e.g. , cross-attention) [41].”
Rethinking Space-Time Networks with Improved Memory Coverage for Efficient Video Object Segmentation (2021, methodology): “A simple decomposition greatly simplifies the implementation, as noted in [69]:”
Deep Generative Modelling: A Comparative Review of VAEs, GANs, Normalizing Flows, Energy-Based and Autoregressive Models (2021, methodology): “Enforcing Lipschitz constraints has been achieved with convolutional networks [59], [138], [156] as well as self-attention [119].”
One Fits All: Power General Time Series Analysis by Pretrained LM (2023, background): “The proof of essentially follows the analysis in Kim et al. (2021), and we include it in Appendix G for completeness.”
On The Computational Complexity of Self-Attention (2022, background): “Self-attention also exhibits undesirable Lipschitz continuity properties, but this can be ﬁxed by pursuing kernel-like alternatives [25].”
Scaling up GANs for Text-to-Image Synthesis (2023, unknown): “As the Lipschitz continuity of discriminators has played a critical role in stable training [2,18,43,44], we use the L2-distance instead of the dot product as the attention logits to promote Lipschitz continuity [35], similar to ViTGAN [38].”
Decoder-Only or Encoder-Decoder? Interpreting Language Model as a Regularized Encoder-Decoder (2023, background): “The detailed proof can be found in Kim et al. (2020).”