mlsanityData to 14 Oct 2026

Solving Regularized Exp, Cosh and Sinh Regression Problems

arXiv 2303.15725 ↗First posted 28 Mar 2023cs.LGcited by 44

Not on the map. Why?

Abstract (arXiv)

In modern machine learning, attention computation is a fundamental task for training large language models such as Transformer, GPT-4 and ChatGPT. In this work, we study exponential regression problem which is inspired by the softmax/exp unit in the attention mechanism in large language models. The standard exponential regression is non-convex. We study the regularization version of exponential regression problem which is a convex problem. We use approximate newton method to solve in input sparsity time. Formally, in this problem, one is given matrix A ∈ ℝn × d, b ∈ ℝn, w ∈ ℝn and any of functions exp, cosh and sinh denoted as f. The goal is to find the optimal x that minimize 0.5 | f(Ax) - b |22 + 0.5 | diag(w) A x |22. The straightforward method is to use the naive Newton's method. Let nnz(A) denote the number of non-zeros entries in matrix A. Let ω denote the exponent of matrix multiplication. Currently, ω ≈ 2.373. Let ε denote the accuracy error. In this paper, we make use of the input sparsity and purpose an algorithm that use log ( |x0 - x^*|2 / ε) iterations and widetildeO(nnz(A) + dω ) per iteration time to solve the problem.

Key facts. Cited by 44 papers in the map (data through 14 Oct 2026). Builds on 68 of its 95 references that are in the map. First posted on arXiv 28 Mar 2023.

Builds on

68 of 95 references.

References · 68

  1. 2017Attention Is All You Needcited by 60,361
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  3. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  4. 2020Language Models are Few-Shot Learnerscited by 32,419
  5. 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 7,005
  6. 2022PaLM: Scaling Language Modeling with Pathwayscited by 5,326
  7. 2022OPT: Open Pre-trained Transformer Language Modelscited by 3,512
  8. 2020Transformers are RNNs: Fast Autoregressive Transformers with Linear Attentioncited by 2,022
  9. 2020Reformer: The Efficient Transformercited by 1,668
  10. 2020Rethinking Attention with Performerscited by 1,601
  11. 2019Generating Long Sequences with Sparse Transformerscited by 1,546
  12. 2017Accurate, Large Minibatch SGD: Training ImageNet in 1 Hourcited by 1,492
38 more
  1. 2020Linformer: Self-Attention with Linear Complexitycited by 1,474
  2. 2016On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minimacited by 1,352
  3. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 655
  4. 2018Universal Transformerscited by 647
  5. 2019Implicit Regularization in Deep Matrix Factorizationcited by 405
  6. 2017Don't Decay the Learning Rate, Increase the Batch Sizecited by 320
  7. 2019Gradient Descent Maximizes the Margin of Homogeneous Neural Networkscited by 320
  8. 2017Train longer, generalize better: closing the generalization gap in large batch training of neural networkscited by 279
  9. 2020Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Losscited by 268
  10. 2018Implicit Bias of Gradient Descent on Linear Convolutional Networkscited by 251
  11. 2017The Marginal Value of Adaptive Gradient Methods in Machine Learningcited by 250
  12. 2019Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networkscited by 162
  13. 2021Inductive Biases and Variable Creation in Self-Attention Mechanismscited by 144
  14. 2021Scatterbrain: Unifying Sparse and Low-rank Attention Approximationcited by 130
  15. 2015Path-SGD: Path-Normalized Optimization in Deep Neural Networkscited by 120
  16. 2021Toward Understanding the Feature Learning Process of Self-supervised Contrastive Learningcited by 119
  17. 2021Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformerscited by 102
  18. 2023Fast Attention Requires Bounded Entriescited by 102
  19. 2018Solving Linear Programs in the Current Matrix Multiplication Timecited by 100
  20. 2019Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networkscited by 76
  21. 2021Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Modelscited by 76
  22. 2020The Implicit and Explicit Regularization Effects of Dropoutcited by 71
  23. 2018Theoretical Analysis of Auto Rate-Tuning by Batch Normalizationcited by 65
  24. 2018Norm matters: efficient and accurate normalization schemes in deep networkscited by 62
  25. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  26. 2020Training (Overparametrized) Neural Networks in Near-Linear Timecited by 58
  27. 2023KDEformer: Accelerating Transformers via Kernel Density Estimationcited by 58
  28. 2020An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applicationscited by 57
  29. 2017SGD Learns the Conjugate Kernel Class of the Networkcited by 54
  30. 2019Solving Empirical Risk Minimization in the Current Matrix Multiplication Timecited by 53
  31. 2020A Faster Interior Point Method for Semidefinite Programmingcited by 53
  32. 2022Towards Understanding Mixture of Experts in Deep Learningcited by 52
  33. 2021Understanding the Generalization of Adam in Learning Neural Networks with Proper Regularizationcited by 49
  34. 2020A Mathematical Theory of Attentioncited by 46
  35. 2017Relative Error Tensor Low Rank Approximationcited by 45
  36. 2020Faster Dynamic Matrix Inverse for Faster LPscited by 44
  37. 2020SMYRF: Efficient Attention using Asymmetric Clusteringcited by 43
  38. 2019A Deterministic Linear Program Solver in Current Matrix Multiplication Timecited by 42

50 most cited of 68 All 68 (JSON)

Built on by

Cited by year

Citing papers per year: 2023: 34; 2024: 6; 2025: 4.

44 papers.

Sort:

By area:

  1. 2023H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Modelscited by 832
  2. 2023Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Timecited by 252
  3. 2023Attention Scheme Inspired Softmax Regressioncited by 49
  4. 2023An Over-parameterized Exponential Regressioncited by 45
  5. 2023The Closeness of In-Context Learning and Weight Shifting for Softmax Regressioncited by 41
  6. 2023Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimensioncited by 37
  7. 2024LazyDiT: Lazy Learning for the Acceleration of Diffusion Transformerscited by 37
  8. 2023An Iterative Algorithm for Rescaled Hyperbolic Functions Regressioncited by 35
  9. 2023In-Context Learning for Attention Scheme: from Single Softmax Regression to Multiple Softmax Regression via a Tensor Trickcited by 32
  10. 2024Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformerscited by 32
  11. 2023InfoPrompt: Information-Theoretic Soft Prompt Tuning for Natural Language Understandingcited by 30
  12. 2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Timecited by 30
32 more
  1. 2023A Mathematical Abstraction for Balancing the Trade-off Between Creativity and Reality in Large Language Modelscited by 29
  2. 2023How to Protect Copyright Data in Optimization of Large Language Models?cited by 26
  3. 2023Differentially Private Attention Computationcited by 25
  4. 2023GradientCoin: A Peer-to-Peer Decentralized Large Language Modelscited by 23
  5. 2024Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Timecited by 22
  6. 2024The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexitycited by 21
  7. 2023Solving Attention Kernel Regression Problem via Pre-conditionercited by 20
  8. 2023Zero-th Order Algorithm for Softmax Attention Optimizationcited by 16
  9. 2023Why Softmax Attention Outperforms Linear Attentioncited by 15
  10. 2023A Unified Scheme of ResNet and Softmaxcited by 12
  11. 2023Unmasking Transformers: A Theoretical Approach to Data Recovery via Attention Weightscited by 12
  12. 2023Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Accelerationcited by 11
  13. 2023Efficient SGD Neural Network Training via Sublinear Activated Neuron Identificationcited by 11
  14. 2023Federated Empirical Risk Minimization via Second-Order Methodcited by 9
  15. 2023Efficient Alternating Minimization with Applications to Weighted Low Rank Approximationcited by 9
  16. 2023An Automatic Learning Rate Schedule Algorithm for Achieving Faster Convergence and Steeper Descentcited by 9
  17. 2023Solving Tensor Low Cycle Rank Approximationcited by 8
  18. 2023Faster Robust Tensor Power Method for Arbitrary Ordercited by 8
  19. 2023Fast and Efficient Matching Algorithm with Deadline Instancescited by 7
  20. 2023The Expressibility of Polynomial based Attention Schemecited by 7
  21. 2023A Theoretical Insight into Attack and Defense of Gradient Leakage in Transformercited by 6
  22. 2023One Pass Streaming Algorithm for Super Long Token Attention Approximation in Sublinear Spacecited by 6
  23. 2023Structured and Fast Optimization: The Kronecker SGD Algorithmcited by 5
  24. 2024How to Inverting the Leverage Score Distribution?cited by 5
  25. 2023Query Complexity of Active Learning for Function Family With Nearly Orthogonal Basiscited by 4
  26. 2025Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approachescited by 4
  27. 2024Inverting the Leverage Score Gradient: An Efficient Approximate Newton Methodcited by 3
  28. 2025When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?cited by 3
  29. 2025Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decodingcited by 2
  30. 2025Towards Sampling Data Structures for Tensor Products in Turnstile Streamscited by 1
  31. 2023Online Adaptive Mahalanobis Distance Estimationcited by 0
  32. 2023Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Trainingcited by 0