Sharpness, Stability, and Step-Size Scaling in Deep Polynomial Networks

Predicting the maximum stable learning rate of a neural network from its architecture alone has remained outside the reach of current theory, except for deep linear and shallow scalar models, where exact sharpness expressions are available. We close this gap for deep polynomial networks by proving the first computable, architecture-explicit lower bound on the largest Hessian eigenvalue at any interpolating minimum. The bound factorizes into three independently computable terms: a data-geometry factor, an architectural-capacity factor, and a label-energy factor. Combining our bound with the dynamical framework of Chemnitz and Engel [2025] and the stability conditions of Cohen et al. [2022], we derive critical step-size upper bounds for a range of optimizers from vanilla gradient descent to adaptive versions like Adam. The maximum stable learning rate for deep polynomial networks scales as $(\text{activation degree})^{(-2 \times \text{depth})}$, placing realistic polynomial network training in the Edge of Stability regime. Our derivation shows that this scaling is a Hessian-level consequence of the network's algebraic structure, not a property of any specific optimizer or dataset. With identity activation, our bound recovers the exact deep linear sharpness of Mulayoff and Michaeli [2020].