- 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
- 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.
- 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
- 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 , where . It excludes ReLU and does not cover arbitrary polynomially bounded weights. These explicit assumptions substantially narrow the scope of the separation.
- The learner uses an explicit degree- 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
- 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.
- 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.
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κ will work: The population true signal has strength at least 2−Dκ and the irrelevant features have population signal strength 0. Hence, it suffices to choose any reasonable value between (0,2−Dκ), 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 κ. 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), so that it's possible to fit the target function to ϵ∗ 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π with k=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). The total number of coordinate descent steps is O~(d4). As discussed after Theorem 3.1, normalizing the intermediate representations can further improve the above bounds to O~(d2+d/ϵ2) and O~(d2), respectively. The dependence on the failure probability is logarithmic and is included in 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) without normalization and O~(d4+d3/ϵ2) with normalization. Compilation requires no additional samples and O~(d2) 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 c0 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.