mlsanityData to 7 Oct 2026

Convergence of Two-Layer Regression with Nonlinear Units

arXiv 2308.08358 ↗First posted 16 Aug 2023cs.LG stat.MLcited by 6

Not on the map. Why?

Abstract (arXiv)

Large language models (LLMs), such as ChatGPT and GPT4, have shown outstanding performance in many human life task. Attention computation plays an important role in training LLMs. Softmax unit and ReLU unit are the key structure in attention computation. Inspired by them, we put forward a softmax ReLU regression problem. Generally speaking, our goal is to find an optimal solution to the regression problem involving the ReLU unit. In this work, we calculate a close form representation for the Hessian of the loss function. Under certain assumptions, we prove the Lipschitz continuous and the PSDness of the Hessian. Then, we introduce an greedy algorithm based on approximate Newton method, which converges in the sense of the distance to optimal solution. Last, We relax the Lipschitz condition and prove the convergence in the sense of loss value.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 63 of its 91 references that are in the map. First posted on arXiv 16 Aug 2023.

Builds on

63 of 91 references.

References · 63

  1. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  2. 2023GPT-4 Technical Reportcited by 18,132
  3. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Modelcited by 7,916
  4. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  5. 2023Sparks of Artificial General Intelligence: Early experiments with GPT-4cited by 2,579
  6. 2020Reformer: The Efficient Transformercited by 1,658
  7. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  8. 2022What Can Transformers Learn In-Context? A Case Study of Simple Function Classescited by 700
  9. 2022What learning algorithm is in-context learning? Investigations with linear modelscited by 671
  10. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  11. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 572
  12. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
38 more
  1. 2023Fine-Tuning Language Models with Just Forward Passescited by 337
  2. 2023Trained Transformers Learn Linear Models In-Contextcited by 331
  3. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 260
  4. 2023Sophia: A Scalable Stochastic Second-order Optimizer for Language Model Pre-trainingcited by 260
  5. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 221
  6. 2019Towards moderate overparameterization: global convergence guarantees for training shallow neural networkscited by 176
  7. 2023Large Language Models Are Latent Variable Models: Explaining and Finding Good Demonstrations for In-Context Learningcited by 149
  8. 2023Representational Strengths and Limitations of Transformerscited by 132
  9. 2019An Improved Analysis of Training Over-parameterized Deep Neural Networkscited by 120
  10. 2019Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networkscited by 120
  11. 2023A Theory for Emergence of Complex Skills in Language Modelscited by 111
  12. 2023Task-Specific Skill Localization in Fine-tuned Language Modelscited by 104
  13. 2023Fast Attention Requires Bounded Entriescited by 102
  14. 2018Solving Linear Programs in the Current Matrix Multiplication Timecited by 100
  15. 2018On the Convergence Rate of Training Recurrent Neural Networkscited by 82
  16. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  17. 2019Quadratic Suffices for Over-parametrization via Matrix Chernoff Boundcited by 58
  18. 2020Training (Overparametrized) Neural Networks in Near-Linear Timecited by 58
  19. 2023KDEformer: Accelerating Transformers via Kernel Density Estimationcited by 58
  20. 2020A Refined Laser Method and Faster Matrix Multiplicationcited by 56
  21. 2019Solving Empirical Risk Minimization in the Current Matrix Multiplication Timecited by 53
  22. 2023Attention Scheme Inspired Softmax Regressioncited by 49
  23. 2021A Zeroth-Order Block Coordinate Descent Algorithm for Huge-Scale Black-Box Optimizationcited by 46
  24. 2020Faster Dynamic Matrix Inverse for Faster LPscited by 44
  25. 2019A Deterministic Linear Program Solver in Current Matrix Multiplication Timecited by 42
  26. 2019Gram-Gauss-Newton Method: Learning Overparameterized Neural Networks for Regression Problemscited by 40
  27. 2021Approximating How Single Head Attention Learnscited by 38
  28. 2023Algorithm and Hardness for Dynamic Attention Maintenance in Large Language Modelscited by 37
  29. 2020Over-parameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionalitycited by 36
  30. 2022A Faster Small Treewidth SDP Solvercited by 36
  31. 2023An Iterative Algorithm for Rescaled Hyperbolic Functions Regressioncited by 35
  32. 2021Solving SDP Faster: A Robust IPM Framework and Efficient Implementationcited by 33
  33. 2023In-Context Learning for Attention Scheme: from Single Softmax Regression to Multiple Softmax Regression via a Tensor Trickcited by 32
  34. 2022Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessingcited by 29
  35. 2022Faster Algorithm for Structured John Ellipsoid Computationcited by 28
  36. 2020Generalized Leverage Score Sampling for Neural Networkscited by 26
  37. 2019A near-optimal algorithm for approximating the John Ellipsoidcited by 23
  38. 2022A Sublinear Adversarial Training Algorithmcited by 22

50 most cited of 63 All 63 (JSON)

Built on by

Cited by year

Citing papers per year: 2023: 3; 2024: 2; 2025: 1.

6 papers.

  1. 2023Why Softmax Attention Outperforms Linear Attentioncited by 15
  2. 2023Unmasking Transformers: A Theoretical Approach to Data Recovery via Attention Weightscited by 11
  3. 2023Local Convergence of Approximate Newton Method for Two Layer Nonlinear Regressioncited by 9
  4. 2024Advancing the Understanding of Fixed Point Iterations in Deep Neural Networks: A Detailed Analytical Studycited by 4
  5. 2025Towards Sampling Data Structures for Tensor Products in Turnstile Streamscited by 1
  6. 2024Enhancing Stochastic Gradient Descent: A Unified Framework and Novel Acceleration Methods for Faster Convergencecited by 0