acceptodds
Under review as a conference paper at ICLR 2027

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

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 approximation error under the uniform distribution over the hypercube.

Primary area:
learning theory
Keywords:
depth separation, hierarchical learning, staircase function

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_5JSHOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies real-valued targets under the uniform distribution on the Boolean hypercube. For sufficiently large input dimension, it proves that constant-depth, polynomial-width networks under explicit analytic-activation and norm bounds cannot approximate deep quadratic targets. A logarithmic-depth learner can learn these targets by constructing Fourier features through layerwise coordinate descent, thresholding, and feature selection. Appendix D compiles the learned representation into a smooth network; the norm bound depends on fan-out in general and is constant for the deep-quadratic subclass used in the separation. Experiments test related hierarchical behavior in ReLU networks trained with Adam.

Critical strengths
  1. Lemma 2.2 addresses a substantive obstacle in extending polynomial approximation through several layers: the approximating polynomials can grow outside their approximation intervals. Appendix B partitions by the first failing layer and chooses the intervals backward to control that contribution. This supplies an approximation obstruction for the stated shallow class, rather than an optimization failure observed for one algorithm.
  2. The efficient-learning and approximation results meet on the same deep-quadratic targets. Theorem 3.1 handles finite-sample feature selection and duplicates; Fact 4.2 gives polynomially bounded target parameters. Appendix D then compiles the learned representation into a smooth network, with fan-out at most five and constant spectral norms for this subclass. This is the main reason I support acceptance: the result goes beyond an expressive-depth separation.
Critical weaknesses
  1. The lower bound is restrictive. Assumption 2.1 requires analytic continuation to a fixed strip and constrains the weight-norm and activation-regularity constants to satisfy CW,Cϕ≤dc0C_W,C_\phi\leq d^{c_0}, where c0<2−2L−7Lc_0<\frac{2^{-2L-7}}{L}. It excludes ReLU and does not cover arbitrary polynomially bounded weights. These explicit assumptions substantially narrow the scope of the separation.
  2. The learner uses an explicit degree-DD monomial expansion, fresh samples at each layer, hard thresholding, and weight-dependent feature selection. Compiling its output into a smooth network does not establish learnability by ordinary end-to-end training. The authors explicitly leave that extension to future work. The algorithmic guarantee therefore concerns this structured learner; the ReLU/Adam experiment remains illustrative.
Questions for authors
  1. Lemma C.5 gives a gap around the truncation threshold. What numerical precision, including label accuracy, is sufficient to preserve feature selection and the Appendix D compilation? This would clarify the computational guarantee under finite-precision arithmetic.
  2. Could you collect the total sample and arithmetic-operation bounds for the deep-quadratic specialization of Theorem 3.1 and Appendix D, using Fact 4.2, including the dependence on error and failure probability? This would make the computational cost of the separation easier to assess.
1 comment

Thank you for your careful reading and for asking us to make the precision requirements and computational costs of the learning procedure more explicit.

Truncation threshold and numerical precision.

Our algorithm is fairly robust to small errors. For the truncation threshold, any value below 2−D−1κ2^{-D-1} \kappa will work: The population true signal has strength at least 2−Dκ2^{-D} \kappa and the irrelevant features have population signal strength 00. Hence, it suffices to choose any reasonable value between (0,2−Dκ)(0, 2^{-D} \kappa), and then adjust the sample size and learning rate to ensure the empirical signals do not cross the threshold. In particular, we do not need to know the precise value of κ\kappa. Any reasonable lower bound suffices, as long as we choose the sample size according to this lower bound. This also covers independent mean-zero label noises, because in expectation, they contribute zero to the signal.

Similarly, for this feature selection step, we only need the numerical precision to be good enough that the empirical signals won't cross the threshold. For this purpose, inverse polynomial precision generally suffices. Moreover, this step still works even when the coefficients of learned features are inaccurate. The same is also true for deterministic label bias. For the function fitting/coefficient learning step that happens in the last layer, we generally need precision to be O(ϵ∗/m)O( \epsilon_* / \sqrt{m} ), so that it's possible to fit the target function to ϵ∗\epsilon_* accuracy.

The compilation step can also tolerate finite precision. During compilation, all coefficients are pulled out and merged into the last layer. Before the last layer, the intended inputs of the cosines are at their extrema (kπk \pi with k=Zk=\mathbb{Z}). Therefore, in each layer, small error in the input only incurs a second-order error in the output.

Sample and runtime complexity.

We have refined the sample/runtime complexity analysis in our upper bound and revised the submission. With this refined analysis, the total number of samples required by our depth-separation theorem is O~(d3+d/ϵ2)\tilde{O}( d^3 + d / \epsilon^2 ). The total number of coordinate descent steps is O~(d4)\tilde{O}(d^4). As discussed after Theorem 3.1, normalizing the intermediate representations can further improve the above bounds to O~(d2+d/ϵ2)\tilde{O}( d^2 + d / \epsilon^2 ) and O~(d2)\tilde{O}(d^2), respectively. The dependence on the failure probability is logarithmic and is included in O~\tilde{O}.

Since our algorithm uses layerwise training, computing one empirical gradient is relatively cheap as we can cache the results of earlier layers and focus solely on the last active layer. The overall runtime is therefore O(LM(N+T))=O~(d5+d3/ϵ2)O( L M (N + T) ) = \tilde{O}( d^5 + d^3/\epsilon^2 ) without normalization and O~(d4+d3/ϵ2)\tilde{O}(d^4 + d^3/\epsilon^2) with normalization. Compilation requires no additional samples and O~(d2)\tilde{O}(d^2) operations, which can be absorbed into the above bounds.

Lower bound conditions.

We have posted a global comment providing further justification for the lower bound conditions. It also discusses how to improve the exponent c0c_0 and remove the analyticity requirement through a direct influence-based argument.

Specialized algorithm.

We agree that it would be better to have end-to-end training guarantee for a more standard architecture. Unfortunately, this seems to be beyond the tools we have for networks with more than two layers. We view our learning result as a first step toward this goal.

Reviewer_emFUOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper shows an algorithmic separation between constant-depth and logarithmic-depth networks under the uniform distribution on the Boolean hypercube. Constant-depth networks with sufficiently regular activations and controlled spectral norms must incur constant L2L^2 error on deep quadratic functions. This lower bound is established via a polynomial approximation lemma. For the upper bound, a learner network trained by layerwise one-pass coordinate descent learns hierarchical staircase functions under the stated parameter conditions by adaptively composing Fourier features. For deep quadratic functions, the trained learner network can be compiled into a neural network matching the architecture of the lower bound. Finally, empirical evaluations using ReLU networks trained via Adam provide additional qualitative evidence.

Critical strengths

1. The polynomial approximation lemma may have independent interest.

I found the treatment of approximation error interesting. The argument controls both error propagation across layers and the contribution from inputs outside the approximation intervals, where a direct global argument runs into difficulties. The resulting lower bound rules out any learning algorithm whose output is a constant-depth network satisfying the assumptions, even with polynomial width.

2. The learning guarantee is combined with a lower bound for the same target class.

The learner discovers Fourier features from samples without knowing their supports in advance. The finite-sample analysis shows that layerwise one-pass coordinate descent can implement feature selection and deduplication, including when supports overlap. This extends the earlier hierarchical construction. For deep quadratic functions, compilation connects the trained learner to the feedforward architecture used in the lower bound.

Critical weaknesses

The connection to the empirical advantage of deep networks needs stronger justification.

My main concern is what this separation tells us about the empirical advantage emphasized in the introduction. The learning guarantee here uses a specific degree-DD polynomial feature mapping and a particular layerwise training procedure. Each layer has a scalar readout trained against the final labels, and its weights are then frozen. The staircase condition also requires the higher-order intermediate features used in the recursive construction to appear in the target’s Fourier spectrum. These choices yield an interesting mathematical result, but I am still unsure why this target class and training procedure provide an informative model of the empirical setting motivating the paper. Compilation establishes the architectural connection needed for the separation; it does not establish a learning guarantee for training directly in the compiled network’s parameters. The ReLU/Adam experiments provide qualitative evidence, but the architecture and training procedure differ from those analyzed theoretically.

Questions for authors

1. Connection to the motivation. What aspects of the empirical advantage of deep networks are hierarchical staircase functions and layerwise one-pass coordinate descent intended to capture? In particular, how should we interpret the role of the explicit degree-(D) feature map and the use of final labels to train each intermediate readout?

2. Informal statements and definitions. Please make the assumptions and approximation accuracy in Theorem 1.1 and Lemma 1.1 more explicit. I found it difficult to connect these informal statements to the conditions and bounds given later. Introducing the basic Fourier notation before Definition 1.2, rather than in Section 1.3, would also help.

3. Parameter dependencies and resource bounds. Could the authors state which parameters the hidden constants depend on and collect the model size, sample complexity, and running time for deep quadratic functions in one place? Please clarify the dependencies hidden in the asymptotic notation and distinguish the depths and widths of the learner and compiled networks, including the dimension of the polynomial feature map.

4.AI use statement. I was unsure how to interpret the distinction between “providing critical ingredients for proving mathematical claims” and “assisting in the writing of proofs,” and between “proposing or refining hypotheses” and “formulating mathematical claims.” Could the authors give a concrete example illustrating these distinctions?

3 comments

Thank you for the detailed feedback, particularly the question on the connection between our theoretical setting and the empirical motivation. We discuss the connection and answer the other questions below, and will incorporate these clarifications into the revision.

Connection to the motivation.

Using the label to train the intermediate readouts is motivated by the direct information paths provided by residual links. When the weights of later layers are still small, the identity part of residual links allows the label signal to reach early layers without going through the untrained later layers. Our layerwise training procedure can be viewed as an idealization of this mechanism.

The explicit polynomial feature map is primarily a technical choice. It separates feature construction from feature selection, and allows us to focus on the latter. In a more standard architecture, these two would happen simultaneously. Note that since DD is constant, the polynomial features are relatively simple functions and can be approximated by a standard fully connected layer. It is therefore plausible that more standard networks can also implement a similar mechanism. Our experiments also provide qualitative support for this possibility. Unfortunately, we were unable to prove a training guarantee for those more standard architectures.

That being said, we wish to point out most optimization results in deep learning theory still concern networks with only two layers. We believe that an optimization guarantee beyond constant layers is valuable, even when it requires a somewhat specialized training procedure.

Finally, the hierarchical staircase functions are intended to capture the idea that a deeper network first learn easier features and then compose them to obtain more complicated ones. In our setting, the complexity is modelled using degree. Note that in general, high-degree functions are not efficiently learnable, and compositional structure does not imply hierarchical learnability (think of kk-parity with 1≪k≪d1 \ll k \ll d). The hierarchical staircase condition provides a reasonably generic mechanism that allows efficient hierarchical learning.

Informal statements and definitions.

Thank you for the suggestions! We'll add more clarification in the revision.

Roughly speaking, Theorem 1.1 says that (1) for a constant-depth network, if the activations are sufficiently regular (like tanh), and the spectral norm of FC layer weights is bounded by dc0d^{c_0} with c0≤1/(8(L+1)32L)c_0 \le 1/(8(L+1)^3 2^L), then it cannot approximate any deep quadratic function to L2L^2-error below 1/41/4, but (2) we can efficiently train a log-depth network to learn this function class to arbitrary inverse polynomial accuracy.

Lemma 1.1 considers the same setting as in the lower bound part of Theorem 1.1 (with dc0d^{c_0} replaced by a generic CWC_W). It says that a constant-depth network satisfying those condition can be approximated by a polynomial of degree at most (CWlog⁡d)O(1)(C_W\log d)^{O(1)}. When CW=dc0C_W = d^{c_0} for some sufficiently small constant c0>0c_0 > 0, this effective degree is at most d1/2d^{1/2}. Consequently, such networks cannot capture the high-degree part of the target function.

Parameter dependencies and resource bounds.

We give the resource bounds for the deep quadratic specialization below. The asymptotic notation hides only universal constants, and we explicitly track dependence on input dimension dd, target accuracy ϵ\epsilon, and failure probability δ\delta. Note that target function's depth, local degree, width, and strength are log⁡2d+1\log_2 d + 1, 22, d−1d - 1, and 2/(dlog⁡2d)\sqrt{2 / (d \log_2 d)}, respectively. The local degree is a universal constant, and all other parameters can be described using dd.

Also, we have refined the sample/runtime complexity analysis in the revision. The following sample/runtime complexity bounds correspond the refined analysis.

  • Learner network size (pre-compilation): Depth = log⁡2d+1\log_2 d + 1, intermediate input/output dim = O(d)O(d), intermediate feature dimension = O(d2)O(d^2).
  • Learner network size (post-compilation): Depth = log⁡2d+3\log_2 d + 3, intermediate input/output/feature dim = O(d)O(d).
  • Total sample complexity: O(d3log⁡5(d/δ)+dlog⁡2(d/δ)/ϵ2)O( d^3 \log^5(d/\delta) + d \log^2(d/\delta) / \epsilon^2 )
  • Total number of coordinate descent steps: O(d4log⁡4(d/ϵ))O(d^4 \log^4(d/\epsilon)).

As discussed after Theorem 3.1, normalizing the intermediate representations can further improve the above bounds to O(d2log⁡2(d/δ)+dlog⁡2(d/δ)/ϵ2)O( d^2 \log^2(d/\delta) + d \log^2(d/\delta) / \epsilon^2 ) and O(d2log⁡d)O(d^2 \log d), respectively. Since our algorithm uses layerwise training, computing one empirical gradient is relatively cheap as we can cache the results of earlier layers and focus solely on the last active layer. The overall runtime is O(LM(N+T))=O~(d5+d3/ϵ2)O( L M (N + T) ) = \tilde{O}( d^5 + d^3/\epsilon^2 ), where O~\tilde{O} additionally hides polylogarithmic factors.

Clarification on the AI use statement.

We used the categories from the ICLR template (which we now realize is unnecessary). We agree that the distinctions need clarification. In our scenario, the basic criterion is whether the underlying mechanism comes from human.

For example, initially we tried to directly use Boolean Fourier analysis to prove the lower bound (similar to existing works in this area), but it didn't work. We then noticed that the end result of the Boolean Fourier analysis approach is effectively a polynomial approximation result, and a more direct approach to prove something like this is layerwise polynomial approximation. Since we don't have explicit characterization for the distribution of intermediate representations, this suggests using uniform polynomial approximation (instead of the usual Hermite polynomials-based approximation). Then, we asked LLM to find the relevant uniform polynomial approximation techniques, which we knew should exist somewhere in the literature, and LLM identified the theorem we need and its reference (Trefethen, 2019). This is an example of "providing critical ingredients for proving mathematical claims" in our definition. By saying "AI tools are not used in assisting in the writing of proofs," we mean that we wrote/structured the final proofs ourselves and no LLM was used at this stage.

The distinction between "proposing or refining hypotheses" and "formulating mathematical claims" lies in whether there's a condition in the first place. We found that when the problem is not already fully specified, LLM tends to give some "shortcut" solutions, that is, assuming strong conditions and proving something uninformative, and/or assuming extremely weak conditions and constructing a "counterexample." Hence, we did not use LLM to formulate mathematical claims, i.e., to decide the setting, which includes most of the lower bound conditions, the target function we use for separation, and the mechanism to exploit. Once we figured out the right setting and had a working argument, we used LLM to relax the conditions and refine the hypotheses.

Thank you for the detailed clarifications. They help clarify the intended scope of the results and the rationale for the modeling choices. I continue to recognize the theoretical value of the polynomial approximation result and the algorithmic separation.

I understand that the specialized feature map and layerwise training procedure are deliberate modeling choices. However, their limited connection to standard neural network training remains a concern in my assessment of the contribution’s significance. I therefore maintain my score of 2.

Reviewer_QSPYOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The objective of the paper is to explain one advantage of the depth of neural networks by combining two results : a learning guarantee for a deep network and an approximation impossibility for a class of shallow networks. The authors have developed a theoretical framework that explores functions whose features can be constructed incrementally by combining a limited number of features. The findings demonstrate that a specialized algorithm, training the network layer by layer, can efficiently learn this particular class.

For a subclass of function, they also prove that networks of constant depth and polynomial width, which satisfied some constraints on activations and weights norms, keep a constant approximation error. Then, the learned deep network can be transformed into a fully connected network that satisfies the norm conditions and regularity.

Critical strengths

1. The paper combine a learning guarantee with an approximation bound.

The negative part of the analysis shows that a particular optimizer fail. It also rules out a good approximation by any network belonging to the shallow class under consideration. The positive part provides an algorithm that learns targets from examples. This combination gives us a clear understanding of the depth advantage under study.

2. The construction correctly links to the architectures used in the two results

Learning first relies on a specialized architecture. The authors then show how to transform the learned model into a fully connected network with admissible activations and controlled norms. This step is important to ensure that the separation does not rely simply on different capabilities assigned to the two architectures. the analysis also takes into account of superposed features and duplicated representations.

Critical weaknesses

The scope of the result remains specialized

The lower bound depends on strong constraints on weight norms and regularity conditions that specifically exclude ReLu. These constraints are essential when larger norms are allowed. The targets have a shallow representation with cosine activations.

The learning method uses a layerwise procedure with explicit product construction and feature selection. The transformation of the network after training does not guarantee that standard training would directly yield this network.

These limits are stated explicitly and do not constitute an error. However they limit the conclusions that can be drawn about standard networks and training methods. The Relu/Adam experiments provide a complementary illustration, without removing these theoretical restrictions.

Questions for authors
  1. Could you explain more directly the essential role of constraints on norms in interpreting separation ? A brief discussion of the shallow representation possible when these constraints are relaxed would help clarify what depth brings to the table in the context of the study.

  2. For figure 1, could you specify the exact numbers of trainable parameters for each depth ? The width suggest a comparable budget but the other trainable matrices must also be taken into account. This clarification would help interpret the experimental comparison.

2 comments

Thank you for the feedback and for suggesting that we should clarify the role of the norm constraints and the parameter counts in our experiments.

Norm constraint.

We have posted a global comment providing further justification for the lower bound conditions and explaining how some of them can be relaxed.

Some restriction on norm is necessary: with poly(d)\mathrm{poly}(d) spectral norm budget, effectively any Fourier-sparse Boolean function can be represented using a two-layer network. This includes kk-parities with 1≪k≪d1 \ll k \ll d, which are not efficiently learnable using certain gradient-based methods and statistical queries.

Thus, relaxing the norm condition can lead to shallow representations whose existence alone says little about whether training can find them. Our lower bound conditions are designed to partially capture the properties a well-trained network desire and/or potentially have. This condition also reflects the usual belief that deep networks can work because they can compose simple functions to represent the more complicated target.

Number of trainable parameters in each model.

The numbers of trainable parameters in each model (from depth 2 to depth 8) are 3.4e6, 3.9e6, 4.0e6, and 4.0e6, respectively. The discrepancy comes from the fact that the width mm is chosen so that 2Lm22 L m^2 is roughly constant across models. The exact number of trainable parameters is the dm+(L−1)m2+Lm+Lm2=(2L−1)m2+(d+L)mdm + (L-1)m^2 + Lm + Lm^2 = (2L - 1)m^2 + (d + L)m, where the terms count the first-layer weights, later-layers weights, biases, and projection matrices weights, respectively. The RHS is only approximately 2Lm22 L m^2, instead of exactly. That being said, having 5∼20%5 \sim 20\% more/fewer trainable parameters probably won't change the qualitative behavior reported in Figure 1. We will clarify this in the revision.

Thank you for the rebuttal. The clarifications on the norm constraint and on the parameter counts answer my questions, and I appreciate the improved sample and runtime bounds and the relaxed assumptions on the lower bound. A few limitations remain, which the authors already acknowledge. Overall, the rebuttal does not change my assessment, and I keep my score of 3 (weak acceptance).

Reviewer_ZPDYOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies depth separation between constant-depth and logarithmic-depth neural networks with respect to the ability to learn certain functions. The authors show that networks of constant depth LL, polynomial width, sufficently regular activations, and spectral norms bounded by dc0d^{c_0}, where c0<2−2L−7/Lc_0<2^{-2L-7}/L, can be approximated by low-degree polynomials. Consequently, these networks cannot approximate certain functions containing high-degree monomials with collectively non-negligible coefficients.

On the other hand, the authors consider a generalization of staircase functions (which they call hierarchical staircase functions), in which higher-degree monomials can be constructed recursively from lower-degree ones. They propose a layerwise coordinate-descent algorithm that learns these functions, layer by layer, in polynomial time. Combining both results, they establish a separation for this particular family of hierarchical staircase functions that can be learned with depth O(log⁡d)O(\log d) and represented by networks of width O(d)O(d) and spectral norms bounded by a constant smaller than 55.

Critical strengths

Establishing separation between deep and shallow networks with respect to the ability of learning a class of functions is an interesting research question and relevant to understanding the role of depth in neural networks. Moreover, the polynomial approximation of shallow networks is an interesting result on its own.

Critical weaknesses

My main concern is about the significance of the depth separation. The lower bound requires extremely restrictive spectral-norm assumptions. While this implies an asymptotic (in the input dimension) separation under a common constant spectral-norm bound on the individual layers, the dimension required to obtain this from the stated bounds is very large. I am also not convinced that bounding the spectral norms of individual layers provides the most meaningful comparison, since the product of these norms can grow with depth but is constant for constant depth networks. Hence, it is not clear to me how much the result tells us about the advantages of depth. In particular, I wonder whether the separation really reflects the ability of deep networks to construct higher-order interactions (as claimed in the conclusion), or rather the limited expressivity of shallow networks under such strong norm restrictions.

The learning algorithm seems specifically designed for hierarchical staircase functions, and it is not clear what is gained by formulating it as neural-network training rather than simply constructing the network from the relevant polynomial features.

Questions for authors
  • How essential are the spectral-norm assumptions? Do the authors expect this to be a limitation of the proof techniques and that a similar separation under substantially weaker restrictions should hold or does this separation rely on the small norms?

  • Could a similar separation hold under bounds on the product of layerwise spectral norms or on the overall Lipschitz constant?

  • Is the proposed algorithm intended to reflect gradient based neural-network optimization, or simply to establish polynomial-time learnability? Could one also just "extract" the polynomial features and construct the network from the function?

2 comments

Thank you for your thoughtful questions about the norm assumptions and the alternative depth separation formulation. We'd like to address the concerns as follows.

On spectral norm condition.

Regarding the possibility of weaker conditions, we can improve the exponent to Θ(1/L2)\Theta(1/L^2) by exploiting the fact that the input distribution is Unif({±1}d)\mathrm{Unif}(\{\pm 1\}^d) and directly applying the influence estimates in Appendix B.1 (cf. Appendix B.4 of the revision). This also allows us to drop the analyticity requirement. The polynomial approximation approach remains useful because it is much more flexible with respect to the input distribution.

We have posted a global comment that includes further discussion on this improved dependence on LL, the necessity of norm restrictions, and the motivation for those conditions.

Separation under global budget vs layer budget.

We agree that depth separation under fixed global spectral norm/Lipschitzness budget is another plausible formulation. Our argument does not apply to this setting.

However, note that a global spectral norm budget can potentially give each layer of a shallow model too much approximation power. As discussed in the global comment, having Ω(k)\Omega(\sqrt{k}) spectral norm budget already allows a single neuron to represent kk-parity, despite that it cannot be efficiently learned with certain gradient-based methods or statistical queries when 1≪k≪d1 \ll k \ll d.

While our formulation fixes only per-layer budget and allows growing global budget, we believe it captures an important heuristic in deep learning: deep networks work because they can compose simple functions to represent a complicated target.

In our setting, "simple" is modeled by mild layer spectral norm and regular activations. Our depth separation shows that there exists genuinely complicated functions that require composition of super-constant simple functions (lower bound), yet can still be efficiently learned by a deep network without access to the ground-truth intermediate representations (upper bound). The second part matters as decomposability doesn't imply hierarchical learnability in general (even kk-parity can be decomposed into O(1)O(1)-parities). Our hierarchical staircase function class provides a concrete generic mechanism through which a deep network can learn and compose intermediate features from standard input-output pairs.

On the training algorithm.

One can indeed learn this function class by directly extracting the Fourier features. The purpose of our neural network-based algorithm is to show that we do not have to use a sophisticated algorithm to achieve poly-time learnability, and that algorithm is designed to mimic more standard gradient-based network training.

More specifically, the layerwise training procedure can be viewed as an idealization of the direct information path provided by residual links, which allow the final label signal to reach early layers without going through the untrained layers.

The use of coordinate descent and a diagonal parameterization is primarily technical. Ideally, we would use a standard FC layer and gradient descent, and show that different neurons automatically learn different features. However, we couldn't rule out the possibility of neurons learning mixtures of features in this setting.

Our training algorithm is indeed somewhat specialized, as are most optimization results beyond two-layer models. We view the identification of this setting and the analysis of this coordinate descent algorithm as a first step toward guarantees for more standard training methods.

Thank you for your response. I appreciate the improved bounds and recognize the theoretical value of combining efficient learning with an approximation lower bound for the same class of target functions.

However, the learning guarantee concerns a specialized hierarchical learner whose output can be compiled into either a deep network with small layer norms or a shallow network with larger norms. Thus, the separation is specifically tied to maintaining small per-layer norms, rather than directly comparing the training of the two architectures. The interpretation in terms of composing simple functions clarifies the motivation, but I remain unconvinced about how informative this constraint is for understanding the advantages of depth in learning functions.

I therefore keep my score of 2.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Improved bounds and further justification for the lower bound conditions

We thank all reviewers for their careful reading and helpful feedback. In this comment, we summarize the improvements to our sample and runtime complexity bounds, and address questions about the lower-bound assumptions that arose in several reviews.

Improved runtime and sample bounds

We have updated the manuscript to include improved sample and runtime complexity bounds. These improvements follow from a refined concentration analysis in Appendix C (the revised Lemmas C.3 and C.5). For deep quadratic functions, the improved bounds are O~(d3+d/ϵ2)\tilde{O}( d^3 + d / \epsilon^2 ) samples and O~(d4)\tilde{O}(d^4) coordinate descent steps.

We have also slightly improved the exponent in Assumption 2.1 by refining the tail bounds in Appendix B.1. We discuss a further relaxation below.

Relaxed conditions via a direct influence argument

By directly applying the refined influence estimates in Appendix B.1 and further exploiting the fact that the input distribution is Unif(±1d)\mathrm{Unif}(\\{\pm 1\\}^d), we can improve the exponent c0c_0 in CW,Cϕ≤dc0C_W, C_\phi \le d^{c_0} to 1/(4L(L+3))1/(4L(L+3)), and remove analytic activation condition (cf. Assumption B.11). We have updated Appendix B.1 and added Appendix B.4 to cover this approach.

The above approach, however, relies on the input distribution being Unif(±1d)\mathrm{Unif}(\\{\pm 1\\}^d). In contrast, our general polynomial approximation argument is much more flexible on the input distribution, regarding which it essentially relies only on concentration of intermediate representations (cf. Eq. (11)). In particular, this directly covers the Gaussian inputs case, where concentration follows immediately from Gaussian concentration of Lipschitz functions. Extensions to other distributions may also be possible under suitable assumptions.

Necessity of norm restrictions

Note that if we allow general poly(d)\mathrm{poly}(d) spectral norm, then any polynomially Fourier-sparse function can be efficiently represented by a two-layer network using the cosine neurons in Lemma D.3. For example, a spectral norm budget of O(k)O(\sqrt{k}) suffices to represent a kk-parity using a single neuron. However, when 1≪k≪d1 \ll k \ll d, learning an unknown kk-parity is known to be hard for statistical query algorithms and certain gradient-based algorithms. Some restriction on norm growth is therefore necessary for approximation-based lower bounds.

Motivation of our lower bound conditions

One way to go beyond unrestricted approximation results is to consider constraints that a well-trained model may satisfy, or that are at least desirable during training.

Our spectral norm condition is one such example. Even an O(1)O(1) spectral norm allows nonlinear feature learning and storage of Ω(d)\Omega(d) orthogonal features. Also, a large spectral norm permits substantial amplification in some intermediate input direction (modulo the pedagogical scenario where the large singular-direction is almost orthogonal to all intermediate inputs), which is in general an undesirable behavior. The widespread use of weight decay also reflects practical interest in controlling weight magnitudes.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.