Linear Complexity Self-Attention With 3rd Order Polynomials.

Area of Science:

• Computer Vision
• Deep Learning
• Neural Networks

Background:

• Self-attention and non-local blocks excel at capturing long-range dependencies in neural networks.
• Their quadratic computational complexity limits practical application in real-world scenarios.

Purpose of the Study:

• To develop computationally efficient alternatives to existing self-attention and non-local blocks.
• To maintain or improve performance in computer vision tasks while reducing computational cost.

Main Methods:

• Analysis of self-attention and non-local blocks through a polynomial lens.
• Design of novel polynomial operators (Poly-NL and Poly-SA) with linear complexity.
• Integration of proposed modules as drop-in replacements in Convolutional Neural Networks (CNNs) and Vision Transformers (ViTs).

Main Results:

• Demonstrated that self-attention is a specific instance of a third-order polynomial.
• Developed polynomial operators that capture similar data patterns as non-local and self-attention but with linear complexity.
• Achieved comparable or superior performance on various computer vision tasks compared to existing methods.

Conclusions:

• The proposed polynomial modules (Poly-NL and Poly-SA) offer a computationally efficient solution for capturing long-range dependencies.
• These modules provide a practical and effective replacement for quadratic self-attention and non-local layers in deep learning architectures.
• Linear complexity enables wider adoption of powerful attention mechanisms in resource-constrained environments.