Compute Better Spent: Replacing Dense Layers with Structured Matrices

• URL: http://arxiv.org/abs/2406.06248v1
• Date: Mon, 10 Jun 2024 13:25:43 GMT
• Title: Compute Better Spent: Replacing Dense Layers with Structured Matrices
• Authors: Shikai Qiu, Andres Potapczynski, Marc Finzi, Micah Goldblum, Andrew Gordon Wilson,
• Abstract summary: We identify more efficient alternatives to dense matrices, as exemplified by the success of convolutional networks in the image domain. We show that different structures often require drastically different initialization scales and learning rates, which are crucial to performance. We propose a novel matrix family containing Monarch matrices, the Block-Train, which we show performs better than dense for the same compute on multiple tasks.
• Score: 77.61728033234233
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Dense linear layers are the dominant computational bottleneck in foundation models. Identifying more efficient alternatives to dense matrices has enormous potential for building more compute-efficient models, as exemplified by the success of convolutional networks in the image domain. In this work, we systematically explore structured matrices as replacements for dense matrices. We show that different structures often require drastically different initialization scales and learning rates, which are crucial to performance, especially as models scale. Using insights from the Maximal Update Parameterization, we determine the optimal scaling for initialization and learning rates of these unconventional layers. Finally, we measure the scaling laws of different structures to compare how quickly their performance improves with compute. We propose a novel matrix family containing Monarch matrices, the Block Tensor-Train (BTT), which we show performs better than dense matrices for the same compute on multiple tasks. On CIFAR-10/100 with augmentation, BTT achieves exponentially lower training loss than dense when training MLPs and ViTs. BTT matches dense ViT-S/32 performance on ImageNet-1k with 3.8 times less compute and is more efficient than dense for training small GPT-2 language models.

Related papers

• BLAST: Block-Level Adaptive Structured Matrices for Efficient Deep Neural Network Inference [15.519068157865023]
  We introduce the Block-Level Adaptive STructured (BLAST) matrix to learn and leverage efficient structures prevalent in the weight matrices of linear layers within deep learning models. We demonstrate the efficiency of using the matrix for compressing both language and vision tasks.
  arXiv  Detail & Related papers  (2024-10-28T17:56:18Z)
• Searching for Efficient Linear Layers over a Continuous Space of Structured Matrices [88.33936714942996]
  We present a unifying framework that enables searching among all linear operators expressible via an Einstein summation. We show that differences in the compute-optimal scaling laws are mostly governed by a small number of variables. We find that Mixture-of-Experts (MoE) learns an MoE in every single linear layer of the model, including the projection in the attention blocks.
  arXiv  Detail & Related papers  (2024-10-03T00:44:50Z)
• Two Sparse Matrices are Better than One: Sparsifying Neural Networks with Double Sparse Factorization [0.0]
  We present Double Sparse Factorization (DSF), where we factorize each weight matrix into two sparse matrices. Our method achieves state-of-the-art results, enabling unprecedented sparsification of neural networks.
  arXiv  Detail & Related papers  (2024-09-27T15:48:39Z)
• Building on Efficient Foundations: Effectively Training LLMs with Structured Feedforward Layers [16.253898272659242]
  State-of-the-art results in large language models (LLMs) often rely on scale, which becomes computationally expensive. Our study focuses on transformer-based LLMs, specifically targeting the computationally intensive feedforward networks (FFNs) We show that wide and structured networks can utilize training FLOPs more efficiently, with fewer parameters and lower loss than dense models at their optimal trade-off.
  arXiv  Detail & Related papers  (2024-06-24T08:43:21Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks. The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions. We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
  arXiv  Detail & Related papers  (2023-09-30T15:57:14Z)
• Monarch: Expressive Structured Matrices for Efficient and Accurate Training [64.6871423399431]
  Large neural networks excel in many domains, but they are expensive to train and fine-tune. A popular approach to reduce their compute or memory requirements is to replace dense weight matrices with structured ones. We propose a class of matrices (Monarch) that is hardware-efficient.
  arXiv  Detail & Related papers  (2022-04-01T17:37:29Z)
• Effective Model Sparsification by Scheduled Grow-and-Prune Methods [73.03533268740605]
  We propose a novel scheduled grow-and-prune (GaP) methodology without pre-training the dense models. Experiments have shown that such models can match or beat the quality of highly optimized dense models at 80% sparsity on a variety of tasks.
  arXiv  Detail & Related papers  (2021-06-18T01:03:13Z)
• Structured Convolutions for Efficient Neural Network Design [65.36569572213027]
  We tackle model efficiency by exploiting redundancy in the textitimplicit structure of the building blocks of convolutional neural networks. We show how this decomposition can be applied to 2D and 3D kernels as well as the fully-connected layers.
  arXiv  Detail & Related papers  (2020-08-06T04:38:38Z)

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.