cs.LGSep 14, 2026

Benign Loss Landscapes Can Coexist with Worst-Case Hardness

Authors: Zach Furman, Stephan Wäldchen, Yangda Bei, Liam Hodgkinson

Abstract

Deep neural networks are expressive enough to contain worst-case targets that can be evaluated in polynomial time but cannot be learned in polynomial time by gradient descent. For practical tasks they nonetheless learn well, raising the question of what non-generic structure of real-world targets enables this. Existing surrogate models cannot pose this question because they either lack hard-to-learn targets entirely (deep linear networks) or cannot evaluate such targets efficiently (kernel methods, infinite-width limits). We study tree tensor networks (TTNs), a model class that generalizes deep linear networks and Tucker decompositions. We show they embed arbitrary read-once Boolean formulas, and thus contain polynomial-size targets that cannot be learned by gradient descent in polynomial time under the same mechanism as neural networks. Despite this, we prove that their loss landscapes are conditionally benign for every realizable target: every local minimum that is minimum-norm is global. Thus, surprisingly, bad local minima are not what distinguishes between typical and worst-case problems in TTNs. Instead, learning difficulty in TTNs can arise from high-order degenerate saddle points, which we show are caused by rank-deficiency. This is explored through a case study of the parity function, illustrating the potential for TTNs to relate landscape geometry to computational hardness.

Explore similar work

CardsList
Jun 9, 2026cs.LG

Limitations of Learning Tanh Neural Networks with Finite Precision

We investigate limitations of learning tanh⁡\tanh neural networks from point evaluations under finite-precision computations and LpL^p accuracy guarantees, building on Berner, Grohs, and Voigtländer (2023). Our approach is based on a novel construction of sharply localized bump functions via iterated tanh⁡\tanh activations. Using this mechanism, we show that, in a finite-precision setting, no adaptive randomized algorithm based on mm samples can achieve a convergence rate higher than the Monte Carlo rate O(m−1/p)O(m^{-1/p}) in the LpL^p norm, unless the sampling budget grows exponentially with the size of the network parameters and architecture. The results reveal fundamental limitations imposed by finite precision on the learnability of classes containing localized bump functions, extending previous results for ReLU networks to the tanh⁡\tanh setting.
Philipp Grohs, Matěj Trödler
Neural NetworkFull-Precision PerformanceFinite Time Analysis
AskPDF
May 28, 2025cs.LG

Favorability of Loss Landscape with Weight Decay Requires Both Large Overparametrization and Initialization

The optimization of neural networks under weight decay remains poorly understood from a theoretical standpoint. While weight decay is standard practice in modern training procedures, most theoretical analyses focus on unregularized settings. In this work, we investigate the loss landscape of the ℓ2\ell_2-regularized training loss for two-layer ReLU networks. We show that the landscape becomes benign -- i.e., free of spurious local minima -- under large overparametrization, specifically when the network width mm satisfies m≳min⁡(nd,2n)m \gtrsim \min(n^d, 2^n), where nn is the number of data points and dd the input dimension. More precisely in this regime, almost all constant activation regions contain a global minimum and no spurious local minima. We further show that this level of overparametrization is not only sufficient but also necessary via the example of orthogonal data. Finally, we demonstrate that such loss landscape results primarily hold relevance in the large initialization regime. In contrast, for small initializations -- corresponding to the feature learning regime -- optimization can still converge to spurious local minima, despite the global benignity of the landscape.
Etienne Boursier, Matthew Bowditch, Matthias Englert +1
Loss LandscapeOver-Parameterized Neural NetworksRectified Linear Unit NetworksNeural Network OptimizationFlat Minima
AskPDF
Jul 7, 2026stat.ML

A Function-Space Dichotomy for Compositional Learning: Exponential Sub-Optimality of the Neural Tangent Kernel

A persistent empirical observation is that trained neural networks outperform their neural tangent kernel (NTK) limit on tasks with compositional structure, yet a quantitative account of when\textbf{when} and by how much\textbf{by how much} has been lacking. Working on the unit circle, we give such an account through a dichotomy between two complexity measures of the target: its Fourier complexity\textbf{Fourier complexity}, which controls NTK kernel regression, and its architectural complexity\textbf{architectural complexity}, which controls learning over depth-LL, width-ww ReLU networks with the variation norm of the weights bounded by RR. We first characterize the minimax rate of the architecture class CL,w,R\mathcal{C}_{L,w,R}, pinning it down up to a single factor of LL: between Ω(Lw2R2/n)Ω(Lw^2R^2/n) and O~(L2w2R2/n)\tilde{O}(L^2w^2R^2/n). We then show the NTK estimator sits exponentially\textbf{exponentially} above this floor whenever the two complexities decouple: for the depth-LL iterated sawtooth, NTK regression needs Ω(4L)Ω(4^L) samples while the minimax floor is polynomial in LL. Numerical experiments confirm the theoretical claims: on bandlimited smooth targets, the NTK is competitive or better, while on the hypercube sparse-parity model, a standard two-layer network beats the NTK by four to six orders of magnitude in test error. The gap is thus a function-space property, a mismatch between the kernel's smoothness bias and the target's compositional structure, rather than a generic kernel-versus-network phenomenon.
Arkaprabha Ganguli, Emil Constantinescu
Neural Tangent KernelRectified Linear Unit NetworksWeight-SpaceSmoothingOptimality
AskPDF