mlsanityData to 14 Oct 2026

Efficient SGD Neural Network Training via Sublinear Activated Neuron Identification

arXiv 2307.06565 ↗First posted 13 Jul 2023cs.LGcited by 11

Not on the map. Why?

Abstract (arXiv)

Deep learning has been widely used in many fields, but the model training process usually consumes massive computational resources and time. Therefore, designing an efficient neural network training method with a provable convergence guarantee is a fundamental and important research question. In this paper, we present a static half-space report data structure that consists of a fully connected two-layer neural network for shifted ReLU activation to enable activated neuron identification in sublinear time via geometric search. We also prove that our algorithm can converge in O(M2/ε2) time with network size quadratic in the coefficient norm upper bound M and error term ε.

Key facts. Cited by 11 papers in the map (data through 14 Oct 2026). Builds on 64 of its 94 references that are in the map. First posted on arXiv 13 Jul 2023.

Builds on

64 of 94 references.

References · 64

  1. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  3. 2014Going Deeper with Convolutionscited by 4,241
  4. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  5. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
  6. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
  7. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 574
  8. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 566
  9. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 261
  10. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 222
  11. 2016Modular Multitask Reinforcement Learning with Policy Sketchescited by 203
  12. 2020FetchSGD: Communication-Efficient Federated Learning with Sketchingcited by 179
38 more
  1. 2019Towards moderate overparameterization: global convergence guarantees for training shallow neural networkscited by 176
  2. 2016Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivitycited by 138
  3. 2019An Improved Analysis of Training Over-parameterized Deep Neural Networkscited by 121
  4. 2023Fast Attention Requires Bounded Entriescited by 102
  5. 2018On the Convergence Rate of Training Recurrent Neural Networkscited by 82
  6. 2019Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networkscited by 76
  7. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  8. 2019Quadratic Suffices for Over-parametrization via Matrix Chernoff Boundcited by 59
  9. 2020Training (Overparametrized) Neural Networks in Near-Linear Timecited by 58
  10. 2020An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applicationscited by 57
  11. 2019Solving Empirical Risk Minimization in the Current Matrix Multiplication Timecited by 53
  12. 2023Attention Scheme Inspired Softmax Regressioncited by 49
  13. 2017Relative Error Tensor Low Rank Approximationcited by 45
  14. 2023An Over-parameterized Exponential Regressioncited by 45
  15. 2016Faster Kernel Ridge Regression Using Sketching and Preconditioningcited by 44
  16. 2020Faster Dynamic Matrix Inverse for Faster LPscited by 44
  17. 2023Solving Regularized Exp, Cosh and Sinh Regression Problemscited by 44
  18. 2023The Closeness of In-Context Learning and Weight Shifting for Softmax Regressioncited by 41
  19. 2023Algorithm and Hardness for Dynamic Attention Maintenance in Large Language Modelscited by 37
  20. 2023Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimensioncited by 37
  21. 2020Over-parameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionalitycited by 36
  22. 2022A Faster Small Treewidth SDP Solvercited by 36
  23. 2023An Iterative Algorithm for Rescaled Hyperbolic Functions Regressioncited by 35
  24. 2021Fast Sketching of Polynomial Kernels of Polynomial Degreecited by 33
  25. 2021Scaling Neural Tangent Kernels via Sketching and Random Featurescited by 32
  26. 2021Does Preprocessing Help Training Over-parameterized Neural Networks?cited by 32
  27. 2023In-Context Learning for Attention Scheme: from Single Softmax Regression to Multiple Softmax Regression via a Tensor Trickcited by 32
  28. 2023InfoPrompt: Information-Theoretic Soft Prompt Tuning for Natural Language Understandingcited by 30
  29. 2018SEGA: Variance Reduction via Gradient Sketchingcited by 29
  30. 2019Optimal Sketching for Kronecker Product Regression and Low Rank Approximationcited by 29
  31. 2022Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessingcited by 29
  32. 2023A Mathematical Abstraction for Balancing the Trade-off Between Creativity and Reality in Large Language Modelscited by 29
  33. 2022Faster Algorithm for Structured John Ellipsoid Computationcited by 28
  34. 2020Generalized Leverage Score Sampling for Neural Networkscited by 26
  35. 2015Optimal Principal Component Analysis in Distributed and Streaming Modelscited by 24
  36. 2019A near-optimal algorithm for approximating the John Ellipsoidcited by 23
  37. 2019Neural Networks Learning and Memorization with (almost) no Over-Parameterizationcited by 23
  38. 2018BourGAN: Generative Networks with Metric Embeddingscited by 22

50 most cited of 64 All 64 (JSON)

Built on by

Cited by year

Citing papers per year: 2023: 8; 2024: 3.

11 papers.

  1. 2023How to Protect Copyright Data in Optimization of Large Language Models?cited by 26
  2. 2023Solving Attention Kernel Regression Problem via Pre-conditionercited by 20
  3. 2024HSR-Enhanced Sparse Attention Accelerationcited by 19
  4. 2024Exploring the Frontiers of Softmax: Provable Optimization, Applications in Diffusion Model, and Beyondcited by 15
  5. 2023A Unified Scheme of ResNet and Softmaxcited by 12
  6. 2023Unmasking Transformers: A Theoretical Approach to Data Recovery via Attention Weightscited by 12
  7. 2023An Automatic Learning Rate Schedule Algorithm for Achieving Faster Convergence and Steeper Descentcited by 9
  8. 2023The Expressibility of Polynomial based Attention Schemecited by 7
  9. 2023Convergence of Two-Layer Regression with Nonlinear Unitscited by 6
  10. 2023A Theoretical Insight into Attack and Defense of Gradient Leakage in Transformercited by 6
  11. 2024Advancing the Understanding of Fixed Point Iterations in Deep Neural Networks: A Detailed Analytical Studycited by 4