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

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. $\mathbf{\text{We}}\mathbf{\text{derive}}\mathbf{\text{the}}\mathbf{\text{first}}\tilde{O}\text{\hspace{0.17em}⁣}\left(\sqrt{d_{\mathrm{e}\mathrm{f}\mathrm{f}}\mathrm{/}n}\right)\mathbf{\text{generalization}}\mathbf{\text{bound}}\mathbf{\text{for}}\mathbf{\text{Adam}}\mathbf{\text{in}}\mathbf{\text{Deep}}\mathbf{\text{ReLU}}\mathbf{\text{networks}}\mathbf{\text{and}}\mathbf{\text{the}}\mathbf{\text{first}}\mathbf{\text{global-optimal}}\mathbf{\text{convergence}}\mathbf{\text{for}}\mathbf{\text{Adam}}\mathbf{\text{in}}\mathbf{\text{the}}\mathbf{\text{non}}\mathbf{\text{smooth,}}\mathbf{\text{non}}\mathbf{\text{convex}}\mathbf{\text{relu}}\mathbf{\text{landscape}}\mathbf{\text{without}}\mathbf{\text{a}}\mathbf{\text{global}}\mathbf{\text{PL}}\mathbf{\text{or}}\mathbf{\text{convexity}}\mathbf{\text{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.