Algorithmic Separation between Constant-Depth and Logarithmic-Depth Neural Networks

• URL: http://arxiv.org/abs/2607.25200v1
• Date: Tue, 28 Jul 2026 02:13:30 GMT
• Title: Algorithmic Separation between Constant-Depth and Logarithmic-Depth Neural Networks
• Abstract summary: We prove the first algorithmic separation between constant-depth and logarithmic-depth networks.<n>Specifically, we identify a class of Boolean functions with hierarchically structured spectra that logarithmic-depth networks can learn efficiently.
• Score: 64.7580803923092
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Despite the empirical advantages of deep networks over shallow ones, theoretical depth separations largely concern approximation power, while algorithmic results are mostly limited to comparisons between two- and three-layer networks. In this work, we prove the first algorithmic separation between constant-depth and logarithmic-depth networks. Specifically, we identify a class of Boolean functions with hierarchically structured Fourier spectra that logarithmic-depth networks can learn efficiently using layerwise coordinate descent by reconstructing the spectra hierarchically and adaptively. We also exhibit a subclass for which every constant-depth, polynomial-width network with sufficiently regular activations and controlled spectral norms must incur constant $L^2$ approximation error under the uniform distribution over the hypercube.

Related papers

• Approximate Contraction of Arbitrary Tensor Networks with a Flexible and Efficient Density Matrix Algorithm [8.329034093208826]
  We introduce a method to efficiently approximate tensor network contractions using low-rank approximations.<n>The proposed algorithm has the flexibility to incorporate a large portion of the environment when performing low-rank approximations.
  arXiv  Detail & Related papers  (2024-06-14T07:13:52Z)
• Provable Guarantees for Nonlinear Feature Learning in Three-Layer Neural Networks [44.31729147722701]
  We show that three-layer neural networks have provably richer feature learning capabilities than two-layer networks.<n>This work makes progress towards understanding the provable benefit of three-layer neural networks over two-layer networks in the feature learning regime.
  arXiv  Detail & Related papers  (2023-05-11T17:19:30Z)
• Depth Separation with Multilayer Mean-Field Networks [14.01059700772468]
  We show that arXiv:1904.06984 constructed a function that is easy to approximate using a 3-layer network but not approximable by any 2-layer network. Our result relies on a new way of extending the mean-field limit to multilayer networks.
  arXiv  Detail & Related papers  (2023-04-03T15:18:16Z)
• Block belief propagation algorithm for two-dimensional tensor networks [0.0]
  We propose a block belief propagation algorithm for contracting two-dimensional tensor networks and approximating the ground state of $2D$ systems. As applications, we use our algorithm to study the $2D$ Heisenberg and transverse Ising models, and show that the accuracy of the method is on par with state-of-the-art results.
  arXiv  Detail & Related papers  (2023-01-14T07:37:08Z)
• The Sample Complexity of One-Hidden-Layer Neural Networks [57.6421258363243]
  We study a class of scalar-valued one-hidden-layer networks, and inputs bounded in Euclidean norm. We prove that controlling the spectral norm of the hidden layer weight matrix is insufficient to get uniform convergence guarantees. We analyze two important settings where a mere spectral norm control turns out to be sufficient.
  arXiv  Detail & Related papers  (2022-02-13T07:12:02Z)
• Unified Field Theory for Deep and Recurrent Neural Networks [56.735884560668985]
  We present a unified and systematic derivation of the mean-field theory for both recurrent and deep networks. We find that convergence towards the mean-field theory is typically slower for recurrent networks than for deep networks. Our method exposes that Gaussian processes are but the lowest order of a systematic expansion in $1/n$.
  arXiv  Detail & Related papers  (2021-12-10T15:06:11Z)
• Optimization-Based Separations for Neural Networks [57.875347246373956]
  We show that gradient descent can efficiently learn ball indicator functions using a depth 2 neural network with two layers of sigmoidal activations. This is the first optimization-based separation result where the approximation benefits of the stronger architecture provably manifest in practice.
  arXiv  Detail & Related papers  (2021-12-04T18:07:47Z)
• A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks [56.084798078072396]
  We take a step towards closing the gap between theory and practice by significantly improving the known theoretical bounds on both the network width and the convergence time. We show that convergence to a global minimum is guaranteed for networks with quadratic widths in the sample size and linear in their depth at a time logarithmic in both. Our analysis and convergence bounds are derived via the construction of a surrogate network with fixed activation patterns that can be transformed at any time to an equivalent ReLU network of a reasonable size.
  arXiv  Detail & Related papers  (2021-01-12T00:40:45Z)
• Learning Deep ReLU Networks Is Fixed-Parameter Tractable [21.625005195943707]
  We consider the problem of learning an unknown ReLU network with respect to Gaussian inputs. We give an algorithm whose running time is a fixed weights in the ambient dimension. Our bounds depend on the number of hidden units, depth, spectral norm of the spectral norm, and Lipschitz constant.
  arXiv  Detail & Related papers  (2020-09-28T17:58:43Z)
• Dual-constrained Deep Semi-Supervised Coupled Factorization Network with Enriched Prior [80.5637175255349]
  We propose a new enriched prior based Dual-constrained Deep Semi-Supervised Coupled Factorization Network, called DS2CF-Net. To ex-tract hidden deep features, DS2CF-Net is modeled as a deep-structure and geometrical structure-constrained neural network. Our network can obtain state-of-the-art performance for representation learning and clustering.
  arXiv  Detail & Related papers  (2020-09-08T13:10:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.