Second-Order Complexity Theory for Neural Networks

Machine learning relies on gradient-based training procedures whose empirical efficiency is usually analyzed through finite-dimensional arithmetic counts rather than formal complexity over continuous real-valued data. This paper studies neural-network training primitives as represented-real operators in the second-order complexity framework of Kawamura and Cook. Here, second-order polynomial time means computing a real-valued operator to accuracy $2^{-n}$ in time polynomial in the requested precision, architecture size, primitive evaluation costs, and supplied analytic certificates. We prove that dense backpropagation, convolutional backpropagation, soft attention, fixed finite SGD/Adam-style updates, and related smooth local primitives are second-order polynomial-time computable over the relevant represented real spaces. More precisely, dense one-sample backpropagation has tight arithmetic complexity $\Theta (s)$ for $s$ weights and polynomial bit complexity; convolutional backpropagation is polynomial in the number of active convolution incidences; dense soft-attention backpropagation has arithmetic cost $\Theta (\ell d^2+{\ell }^{2}d)$; and fixed finite smooth optimizer updates remain second-order polynomial-time computable under explicit smoothness and lower-bound certificates. Higher complexity enters through three distinct mechanisms: discontinuous selection, global optimization, and continuous-time flow solving. Hard routing, top-$k$ sparsification, argmax decisions, ReLU kink conventions, exact line search, and idealized gradient flow therefore change the second-order complexity status of the training operator. Overall, this work provides a rigorous mathematical language for precision, conditioning, and certificate dependence, which are often implicit in floating-point analyses, thus enabling a unifying complexity account for dense networks, CNNs, attention, Transformers, and standard optimizers.