Convergence of Adam in Deep ReLU Networks via Directional Complexity and Kakeya Bounds

2025/05/21 by Sridhar, Anupama, Johansen, Alexander
Computer Science · #FOS: Computer and information sciences #Face and Expression Recognition #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Neural Networks and Applications #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2505.15013

openalex publication_date 2025/05/21 · openalex created_date 2025/10/19 · openalex updated_date 2026/07/28

Abstract

First-order adaptive optimization methods like Adam are the default choices for training modern deep neural networks. Despite their empirical success, the theoretical understanding of these methods in non-smooth settings, particularly in Deep ReLU networks, remains limited. ReLU activations create exponentially many region boundaries where standard smoothness assumptions break down. \textbfWe derive the first \(O (√d_eff/n)\) generalization bound for Adam in Deep ReLU networks and the first global-optimal convergence for Adam in the non smooth, non convex relu landscape without a global PL or convexity assumption. Our analysis is based on stratified Morse theory and novel results in Kakeya sets. We develop a multi-layer refinement framework that progressively tightens bounds on region crossings. We prove that the number of region crossings collapses from exponential to near-linear in the effective dimension. Using a Kakeya based method, we give a tighter generalization bound than PAC-Bayes approaches and showcase convergence using a mild uniform low barrier assumption.

Citations

• Connecting Independently Trained Modes via Layer-Wise Connectivity
• Spectral Dimension Flow, Localized Non-Orientable Horizon Defects, and Emergent Time in Black Holes: A Geometry-Driven Effective Framework
• Heavy-Tailed Class Imbalance and Why Adam Outperforms Gradient Descent on Language Models
• On Convergence of Adam for Stochastic Optimization under Relaxed Assumptions
• Convergence of Adam Under Relaxed Assumptions
• Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identification
• Coherent Gradients: An Approach to Understanding Generalization in\n Gradient Descent-based Optimization
• Uniform convergence may be unable to explain generalization in deep learning
• Complexity of Linear Regions in Deep Networks
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Gradient Descent Happens in a Tiny Subspace
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Measuring the Intrinsic Dimension of Objective Landscapes
• On the importance of single directions for generalization
• On the Convergence of Adam and Beyond
• Large Batch Training of Convolutional Networks
• Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition
• On the Expressive Power of Deep Neural Networks
• Train faster, generalize better: Stability of stochastic gradient descent
• On the Number of Linear Regions of Deep Neural Networks
• A Stochastic Approximation Method

Related

• On the Proof of Global Convergence of Gradient Descent for Deep ReLU\n Networks with Linear Widths
• Non-convergence to global minimizers in data driven supervised deep learning: Adam and stochastic gradient descent optimization provably fail to converge to global minimizers in the training of deep neural networks with ReLU activation
• A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks
• Optimization and Generalization of Gradient Descent for Shallow ReLU Networks with Minimal Width
• Optimal Rates for Generalization of Gradient Descent for Deep ReLU Classification