mlsanityData to 14 Oct 2026

Local Convergence of Approximate Newton Method for Two Layer Nonlinear Regression

arXiv 2311.15390 ↗First posted 26 Nov 2023cs.LGcited by 9

Not on the map. Why?

Abstract (arXiv)

There have been significant advancements made by large language models (LLMs) in various aspects of our daily lives. LLMs serve as a transformative force in natural language processing, finding applications in text generation, translation, sentiment analysis, and question-answering. The accomplishments of LLMs have led to a substantial increase in research efforts in this domain. One specific two-layer regression problem has been well-studied in prior works, where the first layer is activated by a ReLU unit, and the second layer is activated by a softmax unit. While previous works provide a solid analysis of building a two-layer regression, there is still a gap in the analysis of constructing regression problems with more than two layers. In this paper, we take a crucial step toward addressing this problem: we provide an analysis of a two-layer regression problem. In contrast to previous works, our first layer is activated by a softmax unit. This sets the stage for future analyses of creating more activation functions based on the softmax function. Rearranging the softmax function leads to significantly different analyses. Our main results involve analyzing the convergence properties of an approximate Newton method used to minimize the regularized training loss. We prove that the loss function for the Hessian matrix is positive definite and Lipschitz continuous under certain assumptions. This enables us to establish local convergence guarantees for the proposed training algorithm. Specifically, with an appropriate initialization and after O(log(1/ε)) iterations, our algorithm can find an ε-approximate minimizer of the training loss with high probability. Each iteration requires approximately O(nnz(C) + dω) time, where d is the model size, C is the input matrix, and ω < 2.374 is the matrix multiplication exponent.

Key facts. Cited by 9 papers in the map (data through 14 Oct 2026). Builds on 43 of its 75 references that are in the map. First posted on arXiv 26 Nov 2023.

Builds on

43 of 75 references.

References · 43

  1. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  2. 2023GPT-4 Technical Reportcited by 18,396
  3. 2014Very Deep Convolutional Networks for Large-Scale Image Recognitioncited by 15,364
  4. 2017Graph Attention Networkscited by 8,923
  5. 2022PaLM: Scaling Language Modeling with Pathwayscited by 5,326
  6. 2014Neural Machine Translation by Jointly Learning to Align and Translatecited by 4,548
  7. 2022OPT: Open Pre-trained Transformer Language Modelscited by 3,512
  8. 2020Reformer: The Efficient Transformercited by 1,668
  9. 2015Effective Approaches to Attention-based Neural Machine Translationcited by 1,026
  10. 2022What Can Transformers Learn In-Context? A Case Study of Simple Function Classescited by 715
  11. 2022What learning algorithm is in-context learning? Investigations with linear modelscited by 684
  12. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
31 more
  1. 2023Fine-Tuning Language Models with Just Forward Passescited by 345
  2. 2023Trained Transformers Learn Linear Models In-Contextcited by 337
  3. 2023Large Language Models Are Latent Variable Models: Explaining and Finding Good Demonstrations for In-Context Learningcited by 149
  4. 2023Representational Strengths and Limitations of Transformerscited by 133
  5. 2019Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networkscited by 121
  6. 2023A Theory for Emergence of Complex Skills in Language Modelscited by 113
  7. 2023Task-Specific Skill Localization in Fine-tuned Language Modelscited by 105
  8. 2023Fast Attention Requires Bounded Entriescited by 102
  9. 2023How Do Transformers Learn Topic Structure: Towards a Mechanistic Understandingcited by 86
  10. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  11. 2020Training (Overparametrized) Neural Networks in Near-Linear Timecited by 58
  12. 2023KDEformer: Accelerating Transformers via Kernel Density Estimationcited by 58
  13. 2023Attention Scheme Inspired Softmax Regressioncited by 49
  14. 2023Do Transformers Parse while Predicting the Masked Word?cited by 48
  15. 2023An Over-parameterized Exponential Regressioncited by 45
  16. 2019Gram-Gauss-Newton Method: Learning Overparameterized Neural Networks for Regression Problemscited by 40
  17. 2021Approximating How Single Head Attention Learnscited by 38
  18. 2023Algorithm and Hardness for Dynamic Attention Maintenance in Large Language Modelscited by 37
  19. 2023Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimensioncited by 37
  20. 2020Over-parameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionalitycited by 36
  21. 2023In-Context Learning for Attention Scheme: from Single Softmax Regression to Multiple Softmax Regression via a Tensor Trickcited by 32
  22. 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
  23. 2022Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessingcited by 29
  24. 2022Faster Algorithm for Structured John Ellipsoid Computationcited by 28
  25. 2023GradientCoin: A Peer-to-Peer Decentralized Large Language Modelscited by 23
  26. 2022Discrepancy Minimization in Input-Sparsity Timecited by 22
  27. 2023Solving Attention Kernel Regression Problem via Pre-conditionercited by 20
  28. 2023Beyond Classical Attention: Quantum Attention for Scalable Computationcited by 18
  29. 2023Trainable Transformer in Transformercited by 17
  30. 2023Convergence of Two-Layer Regression with Nonlinear Unitscited by 6
  31. 2023LEAN: Light and Efficient Audio Classification Networkcited by 3

Built on by

Cited by year

Citing papers per year: 2024: 5; 2025: 4.

9 papers.

  1. 2024LazyDiT: Lazy Learning for the Acceleration of Diffusion Transformerscited by 37
  2. 2024Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformerscited by 32
  3. 2024The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexitycited by 21
  4. 2025Breaking the Frozen Subspace: Importance Sampling for Low-Rank Optimization in LLM Pretrainingcited by 7
  5. 2024How to Inverting the Leverage Score Distribution?cited by 5
  6. 2025Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approachescited by 4
  7. 2024Inverting the Leverage Score Gradient: An Efficient Approximate Newton Methodcited by 3
  8. 2025CoVE: Compressed Vocabulary Expansion Makes Better LLM-based Recommender Systemscited by 3
  9. 2025Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decodingcited by 2