Pith. sign in

REVIEW 2 major objections 4 minor 35 references

This paper proves the first algorithmic separation between constant-depth and logarithmic-depth neural networks: a log-depth network can efficiently learn a class of Boolean functions that every smooth constant-depth network provably fails

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-01 03:06 UTC pith:NUEFTB6Z

load-bearing objection First constant-vs-log-depth algorithmic separation claim, but the lower bound's stated constants don't nail the low-degree approximation; the upper bound is solid. the 2 major comments →

arxiv 2607.25200 v1 pith:NUEFTB6Z submitted 2026-07-28 cs.LG stat.ML

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

Yunwei Ren , Zihao Wang , Jason D. Lee This is my paper
classification cs.LG stat.ML MSC 68Q3268T0741A10
keywords algorithmic depth separationhierarchical staircase functionsdeep quadratic functionsChebyshev polynomial approximationlayerwise coordinate descentBoolean Fourier analysisconstant-depth neural networkslearning theory
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Deep networks are often observed to outperform shallow ones, but existing theory mostly separates their approximation power, not their trainability. This paper proves the first algorithmic depth separation: it exhibits a natural class of Boolean functions—hierarchical staircase functions, including concrete 'deep quadratic' functions—that a logarithmic-depth network can provably learn efficiently, while every constant-depth network with smooth activations and bounded spectral norms incurs constant L2 error on the same functions. The lower bound works by showing any such constant-depth network is well approximated by a polynomial of polylogarithmic degree, whereas the target functions concentrate a constant fraction of Fourier mass on degrees at least √d. The upper bound is achieved by a layerwise one-pass coordinate-descent algorithm that reconstructs the target's Fourier spectrum hierarchically, composing previously learned low-degree features into new high-degree ones.

Core claim

The central claim is that adaptive hierarchical feature construction is a provable mechanism by which depth enables efficient learning. For d=2^{L*}, each deep quadratic function places at least one-third of its Fourier mass on degrees ≥√d. The paper proves that every constant-depth, polynomial-width network with activations analytic in a strip and spectral norms ≤d^{c0} (c0<2^{-2L-7/L}) has L2 error at least 1/4 on any such function, while a depth-(L*+1) network trained by layerwise one-pass coordinate descent learns every depth-L* hierarchical staircase function to arbitrary accuracy with polynomial samples and time. The lower bound rests on a polynomial approximation lemma: under those re

What carries the argument

The objects that carry the argument are hierarchical staircase functions and their subclass, deep quadratic functions. A Boolean function is a hierarchical staircase function of depth L and local degree D if its Fourier spectrum is contained in the sets K_l defined inductively: K_1 = {∅, singletons}, and K_{l+1} adds every spectrum set that is the symmetric difference of at most D sets already in K_l; the deep quadratic functions are the running example, built by pairing coordinates and multiplying paired features level by level. The lower-bound machinery is the Chebyshev polynomial approximation lemma: activations that are analytic in a strip and grow at most polynomially can be replaced, o

Load-bearing premise

The separation depends on the lower-bound assumption (Assumption 2.1) that all activations are analytic in a fixed strip with polynomial growth and that weight spectral norms are at most d^{c0} for a sufficiently small c0; if the activation is ReLU or the spectral norm bound is violated, the low-degree polynomial approximation of constant-depth networks may fail and the stated separation is not established.

What would settle it

Train a constant-depth fully connected network with tanh or sigmoid activations, weight spectral norms ≤ d^{c0} with c0 < 2^{-2L-7/L}, on the base deep quadratic function with d=2^{L*} (say L*=8, d=256) under the uniform distribution over {±1}^d, and measure L2 error: an error below 1/4 would contradict Theorem 4.1(a). Alternatively, showing that a ReLU network with bounded spectral norms learns the same function to error below 1/4 would demonstrate the separation does not extend to standard practical activations.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Any constant-depth, polynomial-width network with analytic strip activations and spectral-norm bounds has L2 error at least 1/4 on every deep quadratic function, regardless of the training algorithm.
  • A depth-(log₂d + 1) network trained by layerwise one-pass coordinate descent learns every depth-log₂d hierarchical staircase function to arbitrary accuracy with poly(d) samples and time.
  • The positive learnability result covers not just deep quadratics but also staircase functions, merged-staircase functions, read-once decision trees, and addressing functions.
  • The trained learner can be compiled into the same architectural format as the lower-bound network (with depth allowed to grow), so the separation is not an artifact of comparing mismatched network families.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the polynomial-approximation lemma suggests a broad hardness principle—any target concentrating Fourier mass at super-polylogarithmic degrees should be hard for constant-depth networks under the same smoothness assumptions, so the separation likely extends beyond deep quadratic functions.
  • Editorial inference: if the analyticity assumption could be relaxed to cover ReLU activations, the separation would transfer to the architectures used in practice; the paper does not claim this, and its lower-bound proof does not apply directly.
  • Editorial inference: the hierarchical staircase class suggests a testable criterion for learnability—targets whose Fourier features can be composed from a constant number of previously discovered features are efficiently learnable by this algorithm, whereas targets like random high-degree parities are not; synthetic experiments could probe this boundary.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper claims the first algorithmic separation between constant-depth and logarithmic-depth neural networks. It defines hierarchical staircase functions and proves that a depth-L network trained by layerwise one-pass coordinate descent can learn them efficiently (Theorem 3.1), including depth-L* deep quadratic functions when L*=log_2 d. On the lower-bound side, it proves that any constant-depth network satisfying Assumption 2.1—analytic activations with strip growth, spectral-norm bounds C_W,C_phi≤d^{c0}, and polynomial width—admits a low-degree polynomial approximation, yielding constant L2 error on deep quadratic functions. The separation is Theorem 4.1.

Significance. An algorithmic depth separation beyond two-versus-three layers is a significant potential contribution. The upper bound is nontrivial: the hierarchical staircase class is broader than previously studied staircase classes, and the proof handles adaptive feature discovery and deduplication. The lower bound technique—Chebyshev approximation of constant-depth networks with subgaussian intermediate representations—is also potentially of independent interest. The paper is careful about the architecture for the lower bound and provides substantial appendix proofs. However, the central lower-bound proof as stated contains a concrete numerical inconsistency between Assumption 2.1 and Lemma 2.2 that must be resolved.

major comments (2)
  1. [§2.1, Assumption 2.1(a) and Lemma 2.2] The stated constants do not imply the claimed low-degree approximation. Lemma 2.2 gives deg ≲ [(C_phi C_W^2)^{2L+3}(log d)^{2L+2}]^{L(2L+1)}. Assumption 2.1(a) permits C_phi=C_W=d^{c0} with c0<2^{-2L-7/L}. Substituting the maximal values gives deg ≲ d^{3 c0 (2L+3) L (2L+1)} up to log factors. For L=2 the assumption allows c0≈0.00552, and the exponent is ≈3·0.00552·7·2·5≈1.16, so the degree bound is d^{1.16}, not ≪d^{1/2}. The gap persists for L=3,4,5; only for larger L does the c0 bound become small enough. Thus Lemma 2.2, Theorem 2.1, and part (a) of Theorem 4.1 are not established for all networks covered by Assumption 2.1. The assumption should be strengthened, e.g. c0<1/(6(2L+3)L(2L+1)), or the degree bound sharpened.
  2. [§4, Theorem 4.1(a)] The separation theorem inherits the above issue. The lower bound is stated for every constant-depth network satisfying Assumption 2.1, and L is an arbitrary universal constant. Since depths 2 through 5 already defeat the asserted c0 condition, the central claim 'any constant-depth network' is too strong as written. This is not a minor technicality: the polynomial-approximation argument is the whole lower-bound mechanism. The fix may be local (change the c0 bound), but as it stands the theorem does not follow from the supplied proof.
minor comments (4)
  1. [§1.1, Theorem 1.1] The informal statement says c0 is 'sufficiently small' but the formal Assumption 2.1 chooses an explicit c0 threshold that is not sufficiently small for small constant depths. Please align the informal and formal statements after correcting the constant.
  2. [Assumption 3.1(a)] The plain-text rendering shows '𝑥(𝑙)𝑘 .0' where it should read '𝑥(𝑙)𝑘 ≠ 0'. Several other equations have OCR-style artifacts; the final typeset version should be checked carefully.
  3. [§3.2 and Appendix C] The proof that Sel never discards needed entries relies on the number of nonzero trained features being at most |S*|≤m. This is argued in Lemma C.6, but a short explicit statement in the main text would help readability.
  4. [§2.2] The proof sketch states that C_W and C_phi are universal constants 'for ease of presentation' and defers the general case to Appendix B. Since the formal Assumption 2.1 allows polynomial growth in d, this transition is precisely where the problematic c0 dependence enters; the final version should make the general-case constants fully explicit.

Circularity Check

0 steps flagged

No circular derivation; lower and upper bounds are self-contained, with only minor non-load-bearing self-citations to the authors' prior work (RDKL26).

full rationale

The derivation chain is not circular. The lower bound (Theorem 2.1) rests on Lemma 2.2, a Chebyshev polynomial approximation argument proved in Appendix B from Assumption 2.1 using standard external references (Rivlin, Trefethen, Boucheron-Lugosi-Massart, O'Donnell); its conclusion (degree << d^{1/2}) is derived, not assumed, and the target hardness (Fourier mass >= 1/3 at degree >= sqrt(d), Fact 4.2) is an independent property of deep quadratic functions. The upper bound (Theorem 3.1) is proved by a self-contained induction in Appendix C (Lemmas C.2-C.6): the loss decomposition, concentration bound, and one-pass coordinate-descent analysis are derived from scratch using only fresh input-output samples of f*, and the spectrum S* is not given to the algorithm, so 'learning' is not the answer being handed back. The hierarchical-staircase class is deliberately aligned with the algorithm's recurrence, but Theorem 4.1's separation also uses the independent Fourier-mass lower bound, and the deep-quadratic subclass is concrete (width d-1, signal sqrt(2/(L*d))), so the result has content beyond the definition. The only self-citations with author overlap are to RDKL26: the deep-quadratic example ('cf. Appendix C of [RDKL26]') and the 'shallow-to-deep chaining principle (cf. Informal Principle 2 of [RDKL26])'. These are motivational pointers; the formal proofs re-derive the needed statements, so the self-citation is not load-bearing. No parameters are fitted to data and no fitted quantity is renamed as a prediction. The skeptic's c0-threshold concern about Lemma 2.2 / Assumption 2.1(a) is a possible quantitative soundness gap (whether the stated constant 2^{-2L-7/L} implies the displayed << d^{1/2} bound for small L); it concerns the validity of an implication, not equivalence of output to input, so it is a correctness risk rather than a circularity and does not change the circularity score.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 0 invented entities

The paper introduces no new physical entities or fitted parameters. Its central assumptions are standard Fourier analysis plus explicit regularity and sample-oracle conditions. The free-parameter list is empty because all constants in the proofs are universal or directly specified in theorem statements.

axioms (5)
  • standard math Input distribution is uniform on {±1}^d and Boolean monomials form an orthonormal basis (Section 1.3).
    Used throughout for Fourier decompositions and L2 error calculations.
  • domain assumption Lower-bound networks satisfy Assumption 2.1: constant depth, polynomial width, spectral-norm bounded weights, analytic activations with strip-growth condition.
    This is the class of networks for which the Chebyshev polynomial approximation lemma is proven. Excludes ReLU and networks with large spectral norms.
  • domain assumption Upper-bound algorithm receives i.i.d. samples from the uniform distribution and knows parameters m, kappa, L, D of the target class (Theorem 3.1).
    The sample complexity and threshold choice depend on these parameters, so the learner must know them or have valid upper/lower bounds.
  • domain assumption The target functions have bounded L2 norm ||f*||_2 <= 1 and signal strength kappa > 0.
    Needed for the coordinate-descent convergence and truncation threshold in Lemma C.5.
  • domain assumption For deep quadratic functions, local degree D=2, width O(d), and signal strength sqrt(2/(L* d)) (Fact 4.2).
    Used to instantiate the upper bound and ensure polynomial sample complexity.

pith-pipeline@v1.3.0-alltime-deepseek · 41771 in / 10057 out tokens · 111734 ms · 2026-08-01T03:06:48.601290+00:00 · methodology

0 comments
read the original 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.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

35 extracted references · 2 canonical work pages · 1 internal anchor

  1. [1]

    and Bernstein, Jeremy , month = may, year =

    Yang, Greg and Simon, James B. and Bernstein, Jeremy , month = may, year =. A. doi:10.48550/arXiv.2310.17813 , abstract =

    Pith/arXiv arXiv doi:10.48550/arxiv.2310.17813

  2. [2]

    , month = jul, year =

    Yang, Greg and Hu, Edward J. , month = jul, year =. Tensor. Proceedings of the 38th

  3. [3]

    Proceedings of the IEEE International Conference on Computer Vision (ICCV) , month =

    He, Kaiming and Zhang, Xiangyu and Ren, Shaoqing and Sun, Jian , title =. Proceedings of the IEEE International Conference on Computer Vision (ICCV) , month =

  4. [4]

    2026 , eprint=

    Phase Transitions for Feature Learning in Neural Networks , author=. 2026 , eprint=

    2026

  5. [5]

    Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics , pages =

    Understanding the difficulty of training deep feedforward neural networks , author =. Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics , pages =. 2010 , editor =

    2010

  6. [6]

    Journal of the ACM (JACM) , author =

    Efficient noise-tolerant learning from statistical queries , volume =. Journal of the ACM (JACM) , author =. 1998 , keywords =. doi:10.1145/293347.293351 , abstract =

    arXiv 1998

  7. [7]

    Failures of

    Shalev-Shwartz, Shai and Shamir, Ohad and Shammah, Shaked , month = aug, year =. Failures of. Proceedings of the 34th

  8. [8]

    Bruna, Joan , month = jul, year =. The. doi:10.48550/arXiv.2607.03347 , abstract =

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2607.03347

  9. [9]

    Tabanelli, Hugo and Dandi, Yatin and Pesce, Luca and Krzakala, Florent , month = feb, year =. Deep. doi:10.48550/arXiv.2602.10867 , abstract =

    doi:10.48550/arxiv.2602.10867

  10. [10]

    Dandi, Yatin and Pesce, Luca and Zdeborová, Lenka and Krzakala, Florent , editor =. The. Advances in. 2025 , keywords =

    2025

  11. [11]

    and Favero, Alessandro and Wyart, Matthieu , month = jul, year =

    Cagnetta, Francesco and Petrini, Leonardo and Tomasini, Umberto M. and Favero, Alessandro and Wyart, Matthieu , month = jul, year =. How. Physical Review X , publisher =. doi:10.1103/PhysRevX.14.031001 , abstract =

    doi:10.1103/physrevx.14.031001

  12. [12]

    Daniely, Amit , month = jan, year =. Deep. doi:10.48550/arXiv.2601.00455 , abstract =

    work page doi:10.48550/arxiv.2601.00455

  13. [13]

    What can

    Allen-Zhu, Zeyuan and Li, Yuanzhi , month = dec, year =. What can. Proceedings of the 33rd

  14. [14]

    Backward

    Allen-Zhu, Zeyuan and Li, Yuanzhi , editor =. Backward. Proceedings of. 2023 , keywords =

    2023

  15. [15]

    , month = oct, year =

    Wang, Zihao and Nichani, Eshaan and Lee, Jason D. , month = oct, year =. Learning. The

  16. [16]

    International Conference on Representation Learning , author =

    Learning. International Conference on Representation Learning , author =. 2025 , keywords =

    2025

  17. [17]

    The merged-staircase property: a necessary and nearly sufficient condition for

    Abbe, Emmanuel and Adsera, Enric Boix and Misiakiewicz, Theodor , month = jun, year =. The merged-staircase property: a necessary and nearly sufficient condition for. Proceedings of

  18. [18]

    The staircase property:

    Abbe, Emmanuel and Boix-Adsera, Enric and Brennan, Matthew S and Bresler, Guy and Nagaraj, Dheeraj , editor =. The staircase property:. Advances in. 2021 , pages =

    2021

  19. [19]

    2024 , eprint=

    Theoretical Analysis of Inductive Biases in Deep Convolutional Networks , author=. 2024 , eprint=

    2024

  20. [20]

    Proceedings of

    Abbe, Emmanuel and Adserà, Enric Boix and Misiakiewicz, Theodor , month = jul, year =. Proceedings of

  21. [21]

    , editor =

    Ren, Yunwei and Dandi, Yatin and Krzakala, Florent and Lee, Jason D. , editor =. Provable. Proceedings of. 2026 , pages =

    2026

  22. [22]

    Ren, Yunwei and Zhou, Mo and Ge, Rong , month = feb, year =. Depth. The

  23. [23]

    Optimization-

    Safran, Itay and Lee, Jason , editor =. Optimization-. Proceedings of. 2022 , keywords =

    2022

  24. [24]

    Provable

    Nichani, Eshaan and Damian, Alex and Lee, Jason D , editor =. Provable. Advances in. 2023 , keywords =

    2023

  25. [25]

    Safran, Itay and Reichman, Daniel and Valiant, Paul , month = jul, year =. Depth. Proceedings of

  26. [26]

    Journal of Machine Learning Research , author =

    Depth separation beyond radial functions , volume =. Journal of Machine Learning Research , author =. 2022 , keywords =

    2022

  27. [27]

    Safran, Itay and Eldan, Ronen and Shamir, Ohad , editor =. Depth. Proceedings of the. 2019 , keywords =

    2019

  28. [28]

    Safran, Itay and Shamir, Ohad , editor =. Depth-. Proceedings of the 34th. 2017 , keywords =

    2017

  29. [29]

    Daniely, Amit , editor =. Depth. Proceedings of the 2017. 2017 , keywords =

    2017

  30. [30]

    Eldan, Ronen and Shamir, Ohad , editor =. The. 29th. 2016 , pages =

    2016

  31. [31]

    benefits of depth in neural networks , volume =

    Telgarsky, Matus , editor =. benefits of depth in neural networks , volume =. 29th. 2016 , pages =

    2016

  32. [32]

    , year =

    Rivlin, Theodore J. , year =. Chebyshev polynomials: from approximation theory to algebra and number theory , isbn =

  33. [33]

    , year =

    Trefethen, Lloyd N. , year =. Approximation theory and approximation practice , isbn =. doi:10.1137/1.9781611975949 , language =

    doi:10.1137/1.9781611975949

  34. [34]

    Concentration inequalities: a nonasymptotic theory of independence , isbn =

    Boucheron, Stéphane and Lugosi, Gábor and Massart, Pascal , year =. Concentration inequalities: a nonasymptotic theory of independence , isbn =

  35. [35]

    Analysis of

    O'Donnell, Ryan , month = jun, year =. Analysis of