MetaLA: Unified Optimal Linear Approximation to Softmax Attention Map

• URL: http://arxiv.org/abs/2411.10741v1
• Date: Sat, 16 Nov 2024 08:47:32 GMT
• Title: MetaLA: Unified Optimal Linear Approximation to Softmax Attention Map
• Abstract summary: Linear Transformer (LinFormer), State Space Model (SSM), and Linear RNN (LinRNN) have been proposed to replace the conventional softmax attention in Transformer structures. We find that none of the current linear models meet all three conditions, resulting in suboptimal performance. Our experiments on Multi-Query Associative Recall (MQAR) task, language modeling, image classification, and Long-Range Arena benchmark demonstrate that MetaLA is more effective than the existing linear models.
• Score: 42.396856648479314
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Various linear complexity models, such as Linear Transformer (LinFormer), State Space Model (SSM), and Linear RNN (LinRNN), have been proposed to replace the conventional softmax attention in Transformer structures. However, the optimal design of these linear models is still an open question. In this work, we attempt to answer this question by finding the best linear approximation to softmax attention from a theoretical perspective. We start by unifying existing linear complexity models as the linear attention form and then identify three conditions for the optimal linear attention design: 1) Dynamic memory ability; 2) Static approximation ability; 3) Least parameter approximation. We find that none of the current linear models meet all three conditions, resulting in suboptimal performance. Instead, we propose Meta Linear Attention (MetaLA) as a solution that satisfies these conditions. Our experiments on Multi-Query Associative Recall (MQAR) task, language modeling, image classification, and Long-Range Arena (LRA) benchmark demonstrate that MetaLA is more effective than the existing linear models.

Related papers

• Pareto-Optimal Offline Reinforcement Learning via Smooth Tchebysheff Scalarization [2.5513673603819886]
  Large language models can be aligned with human preferences through offline reinforcement learning (RL) on small labeled datasets.<n>We use this to derive Smooth Tchebysheff of Multi-Objective Preferences (STOMP), a novel formulation that extends direct optimization to the multiobjective.<n>STOMP achieves the highest hyper-objectives in eight of nine settings according to both off-policy and generative evaluations.
  arXiv  Detail & Related papers  (2026-04-14T18:00:39Z)
• $γ$-weakly $θ$-up-concavity: Linearizable Non-Convex Optimization with Applications to DR-Submodular and OSS Functions [52.031993908548294]
  We introduce and $$-weakly $$-up-concavity, a novel first-orderizing condition that characterizes a broad approximation of such functions.<n>Our framework recovers the optimal coefficient for DR-submodular class and significantly improves existing approximation coefficients.
  arXiv  Detail & Related papers  (2026-02-13T22:34:44Z)
• LinearizeLLM: An Agent-Based Framework for LLM-Driven Exact Linear Reformulation of Nonlinear Optimization Problems [1.3854111346209868]
  Reformulating nonlinear optimization problems is largely manual and expertise-intensive.<n>We introduce textitLinearizeLLM, an agent-based framework that solves this task by leveraging Large Language Models (LLMs)<n>The framework assigns each nonlinear pattern to a textitreformulation agent that is explicitly instructed to derive an exact linear reformulation for its nonlinearity pattern.<n>Agents then coordinate to assemble a solver-ready linear model equivalent to the original problem.
  arXiv  Detail & Related papers  (2025-10-12T16:43:21Z)
• Adaptive Cubic Regularized Second-Order Latent Factor Analysis Model [14.755426957558868]
  High-dimensional and incompleteHDI datasets have become ubiquitous across various real-world applications.<n>We propose a two-fold approach to mitigate information instabilities.<n>The ACRS HDI demonstrate that the ALF represents higher representation than the faster advancing (SACR) models.
  arXiv  Detail & Related papers  (2025-07-03T03:15:54Z)
• Random Matrix Theory for Deep Learning: Beyond Eigenvalues of Linear Models [51.85815025140659]
  Modern Machine Learning (ML) and Deep Neural Networks (DNNs) often operate on high-dimensional data.<n>In particular, the proportional regime where the data dimension, sample size, and number of model parameters are all large gives rise to novel and sometimes counterintuitive behaviors.<n>This paper extends traditional Random Matrix Theory (RMT) beyond eigenvalue-based analysis of linear models to address the challenges posed by nonlinear ML models.
  arXiv  Detail & Related papers  (2025-06-16T06:54:08Z)
• Sequential-Parallel Duality in Prefix Scannable Models [68.39855814099997]
  Recent developments have given rise to various models, such as Gated Linear Attention (GLA) and Mamba.<n>This raises a natural question: can we characterize the full class of neural sequence models that support near-constant-time parallel evaluation and linear-time, constant-space sequential inference?
  arXiv  Detail & Related papers  (2025-06-12T17:32:02Z)
• Comba: Improving Bilinear RNNs with Closed-loop Control [57.800320390698516]
  We introduce the concept of Bilinear RNNs with a comprehensive analysis on the advantages and limitations of these models.<n>We propose a novel Bilinear RNN variant named Comba, which adopts a scalar-plus-low-rank state transition, with both state feedback and output feedback corrections.<n>We also implement a hardware-efficient chunk-wise parallel kernel in Triton and train models with 340M/1.3B parameters on large-scale corpus.
  arXiv  Detail & Related papers  (2025-06-03T05:44:50Z)
• An Iterative Bayesian Approach for System Identification based on Linear Gaussian Models [86.05414211113627]
  We tackle the problem of system identification, where we select inputs, observe the corresponding outputs from the true system, and optimize the parameters of our model to best fit the data. We propose a flexible and computationally tractable methodology that is compatible with any system and parametric family of models.
  arXiv  Detail & Related papers  (2025-01-28T01:57:51Z)
• Weight-based Decomposition: A Case for Bilinear MLPs [0.0]
  Gated Linear Units (GLUs) have become a common building block in modern foundation models. Bilinear layers drop the non-linearity in the "gate" but still have comparable performance to other GLUs. We develop a method to decompose the bilinear tensor into a set of interacting eigenvectors.
  arXiv  Detail & Related papers  (2024-06-06T10:46:51Z)
• Value-Biased Maximum Likelihood Estimation for Model-based Reinforcement Learning in Discounted Linear MDPs [16.006893624836554]
  We propose to solve linear MDPs through the lens of Value-Biased Maximum Likelihood Estimation (VBMLE) VBMLE is computationally more efficient as it only requires solving one optimization problem in each time step. In our regret analysis, we offer a generic convergence result of MLE in linear MDPs through a novel supermartingale construct.
  arXiv  Detail & Related papers  (2023-10-17T18:27:27Z)
• Matrix Completion via Non-Convex Relaxation and Adaptive Correlation Learning [90.8576971748142]
  We develop a novel surrogate that can be optimized by closed-form solutions. We exploit upperwise correlation for completion, and thus an adaptive correlation learning model.
  arXiv  Detail & Related papers  (2022-03-04T08:50:50Z)
• Bilinear Classes: A Structural Framework for Provable Generalization in RL [119.42509700822484]
  Bilinear Classes is a new structural framework which permits generalization in reinforcement learning. The framework incorporates nearly all existing models in which a sample complexity is achievable. Our main result provides an RL algorithm which has sample complexity for Bilinear Classes.
  arXiv  Detail & Related papers  (2021-03-19T16:34:20Z)
• LQF: Linear Quadratic Fine-Tuning [114.3840147070712]
  We present the first method for linearizing a pre-trained model that achieves comparable performance to non-linear fine-tuning. LQF consists of simple modifications to the architecture, loss function and optimization typically used for classification.
  arXiv  Detail & Related papers  (2020-12-21T06:40:20Z)
• To Each Optimizer a Norm, To Each Norm its Generalization [31.682969645989512]
  We study the implicit regularization of optimization methods for linear models interpolating the training data in the under-parametrized and over-parametrized regimes. We argue that analyzing convergence to the standard maximum l2-margin is arbitrary and show that minimizing the norm induced by the data results in better generalizations.
  arXiv  Detail & Related papers  (2020-06-11T21:07:38Z)
• Variational Inference and Learning of Piecewise-linear Dynamical Systems [33.23231229260119]
  We propose a variational approximation of piecewise linear dynamical systems. We show that the model parameters can be split into two sets, static and dynamic parameters, and that the former parameters can be estimated off-line together with the number of linear modes, or the number of states of the switching variable.
  arXiv  Detail & Related papers  (2020-06-02T14:40:35Z)
• Multi-Objective Matrix Normalization for Fine-grained Visual Recognition [153.49014114484424]
  Bilinear pooling achieves great success in fine-grained visual recognition (FGVC) Recent methods have shown that the matrix power normalization can stabilize the second-order information in bilinear features. We propose an efficient Multi-Objective Matrix Normalization (MOMN) method that can simultaneously normalize a bilinear representation.
  arXiv  Detail & Related papers  (2020-03-30T08:40:35Z)
• Learning Bijective Feature Maps for Linear ICA [73.85904548374575]
  We show that existing probabilistic deep generative models (DGMs) which are tailor-made for image data, underperform on non-linear ICA tasks. To address this, we propose a DGM which combines bijective feature maps with a linear ICA model to learn interpretable latent structures for high-dimensional data. We create models that converge quickly, are easy to train, and achieve better unsupervised latent factor discovery than flow-based models, linear ICA, and Variational Autoencoders on images.
  arXiv  Detail & Related papers  (2020-02-18T17:58:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.