The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks

Recent advances in deep learning have demonstrated remarkable success in high-dimensional data tasks, yet the theoretical understanding of why neural networks generalize well remains incomplete. Early work like the Neural Tangent Kernel (NTK) framework (Jacot et al., 2018) showed that wide networks behave linearly during training, limiting their capacity to exploit complex structures. Meanwhile, mean-field theories (Chizat & Bach, 2020) began to describe non-linear dynamics but lacked precise structural conditions for function learnability. Sparse functions, which depend on few features, are known to be well approximated by neural networks (Bach, 2017), but the conditions under which SGD-trained networks can efficiently learn such functions in high dimensions are still unclear. This paper builds on these foundations, integrating Fourier analysis and PDE-based dynamics to identify structural properties—specifically MSP—that determine learnability.

Despite empirical success, deep neural networks' ability to learn structured functions like sparse or low-rank functions in high dimensions is not fully understood. Existing theories either focus on linear regimes, which fail to capture the non-linear benefits, or on worst-case bounds that are too loose. The core challenge is to identify precise, structural conditions of target functions that guarantee efficient learning with SGD, especially when the input space is exponentially large. Without such conditions, the sample complexity can grow exponentially, making practical learning infeasible. Bridging this gap requires analyzing the interplay between the function's Fourier structure and the training dynamics in a high-dimensional setting.

The paper's key innovations include: 1) defining the merged-staircase property (MSP) as a structural criterion based on the sequential growth of Fourier support sets; 2) establishing a dimension-free PDE model that approximates the training dynamics, independent of ambient dimension; 3) proving that MSP is necessary for functions to be strongly learnable with O(d) samples, and that generic MSP functions are almost surely learnable, thus nearly sufficient. This approach combines Fourier analysis, mean-field PDEs, and polynomial identity testing to rigorously connect the function's Fourier support structure with the dynamics of SGD, providing a new theoretical lens for deep learning analysis.

• �� Model the training dynamics of depth-2 neural networks using mean-field PDEs, capturing the evolution of weight distributions.
• �� Derive a dimension-free PDE approximation valid for functions with low-dimensional latent structure, simplifying high-dimensional analysis.
• �� Decompose target functions into Fourier-Walsh basis, analyze the support set growth, and define MSP as the sequential support set growth condition.
• �� Use polynomial identity testing to analyze whether the PDE dynamics can reach zero risk, linking this to the MSP condition.
• �� Prove that functions not satisfying MSP cannot be driven to zero risk by the dynamics, establishing the necessary condition.
• �� Show that generic MSP functions are almost surely learnable, completing the nearly sufficient characterization.

Synthetic experiments construct functions satisfying and violating MSP, then train depth-2 networks with SGD, measuring sample complexity and convergence. Different activation functions (ReLU, sigmoid) test the robustness of the theory. Comparisons with linear methods (kernel ridge regression, NTK) highlight the advantage of non-linearity for MSP functions. Varying the input dimension d and the support size P, experiments confirm the polynomial sample complexity for MSP functions and exponential for non-MSP. Additional ablation studies analyze the impact of regularization and initialization schemes, validating the theoretical predictions and demonstrating the practical relevance of the MSP criterion.

The study establishes MSP as a fundamental structural condition for efficient SGD learning of sparse functions. Functions satisfying MSP can be learned with O(d) samples, while non-MSP functions require exponentially more samples, confirming the theoretical advantage of non-linear training. The dimension-free PDE models accurately predict the training dynamics and convergence behavior. The results also show that linear methods like NTK cannot efficiently learn MSP functions, emphasizing the importance of non-linearity. These findings provide a rigorous foundation for understanding deep learning's success in structured high-dimensional problems.

Insights from this work can guide the design of neural architectures tailored to exploit low-dimensional structures in high-dimensional data, such as in genomics, signal processing, and feature selection. The MSP criterion offers a structural blueprint for developing algorithms that adaptively focus on relevant features, reducing sample complexity and improving generalization. Additionally, the theoretical framework can inform regularization strategies and initialization schemes to enhance training efficiency. Long-term, these principles could lead to automated methods for identifying and leveraging data structure in complex real-world datasets, advancing AI capabilities in scientific and industrial domains.

The analysis is limited to shallow (depth-2) networks; extending to deeper architectures involves additional complexities. The reliance on smooth activation functions and regularization parameters may restrict direct applicability to common non-smooth activations like ReLU. Experimental validation is primarily on synthetic functions, which may not fully capture real-world data complexity. The framework assumes idealized conditions, such as noiseless data and perfect optimization, which may differ from practical scenarios. Future work should address these limitations by analyzing deeper models, non-smooth activations, and noisy data environments.