mlsanityData to 7 Oct 2026

A Derandomization Framework for Structure Discovery: Applications in Neural Networks and Beyond

arXiv 2510.19382 ↗First posted 22 Oct 2025stat.ML cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Understanding the dynamics of feature learning in neural networks (NNs) remains a significant challenge. The work of (Mousavi-Hosseini et al., 2023) analyzes a multiple index teacher-student setting and shows that a two-layer student attains a low-rank structure in its first-layer weights when trained with stochastic gradient descent (SGD) and a strong regularizer. This structural property is known to reduce sample complexity of generalization. Indeed, in a second step, the same authors establish algorithm-specific learning guarantees under additional assumptions. In this paper, we focus exclusively on the structure discovery aspect and study it under weaker assumptions, more specifically: we allow (a) NNs of arbitrary size and depth, (b) with all parameters trainable, (c) under any smooth loss function, (d) tiny regularization, and (e) trained by any method that attains a second-order stationary point (SOSP), e.g. perturbed gradient descent (PGD). At the core of our approach is a key textitderandomization lemma, which states that optimizing the function mathbbEx left[gθ(Wx + b)right] converges to a point where W = 0, under mild conditions. The fundamental nature of this lemma directly explains structure discovery and has immediate applications in other domains including an end-to-end approximation for MAXCUT, and computing Johnson-Lindenstrauss embeddings.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 64 of its 89 references that are in the map. First posted on arXiv 22 Oct 2025.

Builds on

64 of 89 references.

References · 64

  1. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  2. 2016Gaussian Error Linear Units (GELUs)cited by 3,431
  3. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  4. 2017Visualizing the Loss Landscape of Neural Netscited by 1,126
  5. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  6. 2017Spectrally-normalized margin bounds for neural networkscited by 681
  7. 2018On Lazy Training in Differentiable Programmingcited by 671
  8. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  9. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 649
  10. 2018A Mean Field View of the Landscape of Two-Layers Neural Networkscited by 463
  11. 2018On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transportcited by 422
  12. 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 410
38 more
  1. 2017Methods for Interpreting and Understanding Deep Neural Networkscited by 342
  2. 2014In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learningcited by 339
  3. 2018Stronger generalization bounds for deep nets via a compression approachcited by 306
  4. 2015Norm-Based Capacity Control in Neural Networkscited by 299
  5. 2017How to Escape Saddle Points Efficientlycited by 284
  6. 2020Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Losscited by 267
  7. 2018Implicit Bias of Gradient Descent on Linear Convolutional Networkscited by 251
  8. 2022Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limitcited by 184
  9. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
  10. 2022High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representationcited by 146
  11. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 142
  12. 2022The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networkscited by 141
  13. 2018Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networkscited by 140
  14. 2020Towards Theoretically Understanding Why SGD Generalizes Better Than ADAM in Deep Learningcited by 125
  15. 2019Implicit Regularization of Discrete Gradient Dynamics in Linear Neural Networkscited by 122
  16. 2020Online stochastic gradient descent on non-convex losses from high-dimensional inferencecited by 119
  17. 2019Dynamics of stochastic gradient descent for two-layer neural networks in the teacher-student setupcited by 112
  18. 2021Implicit Bias of SGD for Diagonal Linear Networks: a Provable Benefit of Stochasticitycited by 107
  19. 2017Recovery Guarantees for One-hidden-layer Neural Networkscited by 94
  20. 2022Learning Single-Index Models with Shallow Neural Networkscited by 92
  21. 2017A Random Matrix Approach to Neural Networkscited by 80
  22. 2020Learning Parities with Neural Networkscited by 77
  23. 2021The staircase property: How hierarchical structure can guide deep learningcited by 62
  24. 2022Neural Networks Efficiently Learn Low-Dimensional Representations with SGDcited by 61
  25. 2023Learning time-scales in two-layers neural networkscited by 57
  26. 2017Learning ReLUs via Gradient Descentcited by 54
  27. 2023On Learning Gaussian Multi-index Models with Gradient Flowcited by 53
  28. 2020Learning a Single Neuron with Gradient Methodscited by 50
  29. 2020Optimization and Generalization of Shallow Neural Networks with Quadratic Activation Functionscited by 50
  30. 2022Phase diagram of Stochastic Gradient Descent in high-dimensional two-layer neural networkscited by 50
  31. 2021A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Networkcited by 47
  32. 2020Agnostic Learning of a Single Neuron with Gradient Descentcited by 46
  33. 2024Neural network learns low-dimensional polynomials with SGD near the information-theoretic limitcited by 45
  34. 2019Compression based bound for non-compressed network: unified generalization error analysis of large compressible deep neural networkcited by 39
  35. 2024Computational-Statistical Gaps in Gaussian Single-Index Modelscited by 39
  36. 2023SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problemcited by 36
  37. 2019First-order methods almost always avoid saddle points: the case of vanishing step-sizescited by 35
  38. 2020Learning Polynomials of Few Relevant Dimensionscited by 34

50 most cited of 64 All 64 (JSON)

Built on by

Not cited yet.