Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper provides a theoretical study on the difficulty of learning an unknown ReLU network with a fixed number of layers by another ReLU network with the same number of layers. While previous attempts usually look at NP-hardness of the optimization process of this task, even allowing for known data distribution, the paper tackles the problem from a learnability/information theoretic point of view and studies bounds on sample complexity that any learning algorithm can achieve. The end result is a separation between L-infinity learnability and Lp learnability when p is finite. In particular, when requiring that the learned network is close in L-infinity norm, the sample complexity scales at least exponentially in depth and input dimension, even if one allows for arbitrary runtime in the learning algorithm.







strength_and_weaknesses: Strengths

1. The results are quantitative where both the upper and lower bound are non-asymptotic. The proof is clean and constructive. 
The paper is very clearly written. Special care was given to compare to existing work and to discuss specific results in order to avoid over-claiming.
2. Assumptions made are natural and rather weak. The learning problem is also natural and relevant (teacher-student learning).
Relevant empirical study to substantiate theoretical claims.

Weaknesses

1. The results are not very surprising as learning in L-infinity is known to be hard. 
2. Some discussions can be useful regarding the upper bound result (of Theorem 2.4). 
3. The results are only truly novel in the L-infinity setting, which is a restrictive setting (mainly for security, safety-critical applications), as learning is known to be tractable in L-p where p is finite. (This is acknowledged by the authors.) 
4. The constructed hard function for the lower bound proof makes use of sharp bumpy hat functions, which is not natural in real-world settings.
5. I would really appreciate a more in depth comparison to SQ learnability literature since they share the common setting of studying sample complexity (as opposed to runtime complexity under fixed sample size). The authors, however, did a good job comparing their results in the PAC learnability setting.
clarity,_quality,_novelty_and_reproducibility: 1. Clarity:
The paper is written very clearly and is a treat to read. The authors went to great lengths to avoid misrepresentation of their results and perform comprehensive comparison with existing literature. 
2. Quality:
I did not go through the proof in the appendix line-by-line due to lack of time but on quick inspection, and on studying the proof sketch provided in the main text, I believe the proof is correct and has high quality. The proof idea is also clear and organized. 
3. Novelty:
In the L-infinity setting, the paper claims to be the first to show quantitative lower-bound for learnability. 
4. Reproducibility:
Experiments in the papers are described in detail with hyperparameters listed comprehensively in the appendix. I have not run the code myself due to lack of time but I believe that the results are reproducible, or otherwise can be quickly shown to be wrong. 
summary_of_the_review: Despite the limited setting under which the main results are proven (learning under L-infinity) and slightly unrealistic counterexample for the lower bound (which is rather common in the literature, in fact), the paper is very clearly written (even in the proof), gives concrete, quantitative, and comprehensive results under mild assumptions and is, in general, an interesting and well-conceived theoretical paper. Therefore, I recommend acceptance.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper presents a fundamental impossibility result associated with the neural network function class. It is proven that given a specific network architecture (e.g., depth and width) with ReLU activation function and norm-bounded parameters, there exists a neural network function u such that u cannot be determined *efficiently* from (possibly adaptive) input-output sample pairs, where the needed sample size to determine u can be lower bounded by a term that scales exponential in the input dimension d. This result is equivalent to the following one: given a specific network architecture with ReLU activation function and norm-bounded parameters, to learn a target function uniformly well with error $\epsilon$ (where the error is measured to be the $L^\infty$ distance between the learned function and the target), the sample complexity must scale like $\Omega(\epsilon^{-d})$.

The paper discussed a quite general setting with the error defined to be $L^p$ distance for any $p\in [1,\infty]$. The above exponential bound happens exactly when $p=\infty$, which contrasts the common squared-error setting $p=2$, for which sample-efficient learning is possible.

Moreover, the dependency of several problem-dependent parameters is made explicit in the bound, such as the network layer $L$, the hidden dimension $B$, and the scale of the parameters $c$ under $\ell_q$-norm. The authors gave a fruitful discussion of their results and also presented an upper bound. They finally conducted experiments to verify the theoretical results.
strength_and_weaknesses: **Strength**:

I feel the presented theoretical result is interesting. The result gives us a better understanding of the complicated nature of the neural network function class which is fundamentally different from classic function classes, such as linear models or polynomials. It shows that the representation of a neural network cannot be inferred from a tractable number of input-output samples even if the number of network parameters is small. I partially agree with the authors that the result may be useful for future works in understanding several important topics, e.g., why modern neural networks are vulnerable to adversarial examples. I also agree that learning functions to minimize the uniform error $L^\infty$ instead of $L^2$ is *necessary* for some applications such as solving partial differential equations. So in this respect, I think the present theoretical result is significant.

This paper is well-written and clear. Although the theoretical bound involves many problem-dependent parameters in a complicated manner, it is well-explained using carefully presented remarks. Moreover, the simplified version (Theorem 1.1) gives readers an overall picture of the more advanced result, while being easy to understand. The authors also present a proof sketch that is helpful in gaining insights into why the result holds. The discussions in this paper are particularly comprehensive.

**Weaknesses**:
1. I think there is a mismatch between the setting in this paper and the commonly used settings in learning real-world function classes. In practice, it is unlikely that the target function is represented by a neural network similar to the counterexample in this paper. If I understand correctly, the reason why the sample complexity must scale like $\Omega(\epsilon^{-d})$ is that neural networks can represent ''bump functions'' which are highly local. Therefore, if there are no samples in the ``bump'' area, the target function clearly cannot be learned. However, such non-smoothness may hardly appear in practice. Therefore, the current theory may not shed light on practical settings. I think it is an important and natural assumption that the target function to be learned is ''smooth'' (rather than all functions that can be represented by neural networks).\
 Although the authors said that ''this is satisfied in several applications of interest, e.g., model extraction attacks (Tramèr et al., 2016; He et al., 2022) and teacher-student settings (Mirzadeh et al., 2020; Xie et al., 2020)'', the target functions there are *well-trained* neural networks rather than any possible one in the neural network function class. Therefore, these cases may not be the same as the one studied in this paper.

2. The authors also said that the result is related to the adversarial vulnerability of neural networks. While I partially agree with the potential implications of the result in this paper, I think the current setting is still quite different from the setting of adversarial examples. In particular, Theorem 1.1 may only show that neural networks can represent highly non-smooth functions with many spikes, for which adversarial examples exist. However, given finite samples, why are neural networks prone to learn bump/spike functions rather than smooth functions? It is because of the inductive bias or training algorithms? I think currently it is still not clear how the result in this paper relates to the adversarial vulnerability of neural networks.

3. While I am generally satisfied with the case when $q=\infty$ (i.e., the setting of bounded weight coefficients), I think the current bound for $q<2$ may be vacuous and unreasonable. In particular, in this case $\Omega$ scales like $d^{-d}$, which means that when fixing $\epsilon$, the bound $\left(\frac {\Omega}{64d\epsilon}\right)^d$ vanishes as $d\to \infty$. Namely, the lower bound becomes trivial when $d$ is large. This is clearly impossible since the problem becomes harder when $d$ is larger. Therefore, the bound for the case of $q<2$ is very loose and may not really make sense. Note that there is a large gap between the lower bound and the upper bound for $q\le 2$ (Theorem 2.4, which does not vanish when $d$ is large). In another way, the main theorem only applies when $\epsilon=o(1/d)$. For the high dimensional setting which usually occurs in practice, the bound becomes vacuous.
clarity,_quality,_novelty_and_reproducibility: See the above section.

Besides, I also have a series of questions:

1. In Theorem 1.1, it is written ``$L$ layers with width up to $3d$''. Is the statement wrong (maybe the correct statement would be $L$ layers with width at least $3d$)? I think increasing the width should only make the network function more complicated.
2. In the main theorem, when $q=2$, it seems that $\Omega$ will have different values under the two different calculations in equation (3). Are the constants $\frac 1 {4\times 3^{2/q}}$ and $\frac 1 {24}$ correct? What is the reason for this inconsistency?
3. Theorem 2.2 requires the assumption that $L\ge 3$. I wonder why it cannot be applied for two-layer networks. Are two-layer networks fundamentally different from networks with $L\ge 3$ layers in proving this theorem? 
4. The authors said that Theorem 2.2 only applies for ReLU neural networks. I am quite interested in the assumption and would like to know more about it: what are the difficulties in generalizing the result to other activation functions? Do you think/conjecture that Theorem 2.2 can still apply in general settings?
5. Regarding Figure 3: it is said that this paper focuses on ReLU networks. However, the blue curve in Figure 3 is smooth, which is strange to me. Can the authors provide an explanation?
6. The authors use simple vector $\ell_q$ norm to constrain the model's parameters. While it is certainly fine (not a weakness), I may wonder if it is possible to use bounded matrix norm per layer to constrain the model's parameters since it is finer than the coarse vector norm and takes into consideration the layered network structure.

Miscellaneous minor issues:
The first line in page 8: what is equation (2.1) linked to?
summary_of_the_review: Overall, I think this paper is interesting. The result is well-presented, and the writing is clear. Nevertheless, there are several weaknesses raised above. I hope the authors can clarify them and I will reevaluate this paper based on authors' response.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper provides sample complexity upper bound and lower bound for learning high uniform accuracy ReLU networks. It shows that any learning algorithm recovers neural networks to achieve high uniform accuracy needs intractably many samples (exponentially depending on the input dimension, network width and network depth).

strength_and_weaknesses: Strength:  This paper study the sample complexity of learning high uniform accuracy neural networks. Uniform accuracy is not a common criterion that people analyze in statistical learning theory, but it can help to understand the stability of the network, which I believe is an important contribution to the deep learning community.


Weakness:  While I’m not familiar with uniform accuracy-related work, I feel some of the important lines of literature are missing. For example, I’m wondering whether the author can first provide some detailed literature results regarding the difference between sample complexity of average accuracy vs uniform accuracy on simpler hypothesis classes, such as linear classifier, polynomial classifier, etc? Moreover, I believe how neural network approximate function is another line of related work related to this paper, which should be discussed and compared with the results.

clarity,_quality,_novelty_and_reproducibility: 1. I suggest formally giving the definition of uniform accuracy instead of burying it in the text. 
2. A detailed comparison between the sample complexity of NN under uniform accuracy and under normal average accuracy proposed in the literature, is necessary.
3. The proof sketch in the main paper can be clearer, i.e. first give the definition of bump functions. Some of the math notation in the proof sketch is not introduced.
4. What are the x-axis and y-axis of figure 3, also the discussion is not very clear to me.
5. Though the theorem suggests sample complexity exponentially depends on the dimension, I'm wondering whether the experiments can be more flexible. Only consider dimension=1 and 3 looks too simple and hardly gives any insight for real-world application.
6. I'm not following the motivation that connects uniform accuracy with adversarial robustness, in the sense that this paper considers a teacher-student setting, so all the samples are guaranteed to generate from the same neural network, whereas for adversarial robustness, even considering the standard Lp perturbation attack, there's no guarantee that the adversarial examples and the clean samples all come from the same network.
summary_of_the_review: Overall, I believe this is an interesting paper with good contribution that considers the sample complexity of neural networks for uniform accuracy.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: Motivated by robustness of trained models, the paper studies the statistical complexity of learning the class of ReLU networks up to $\ell_\infty$-error (uniform error). In particular, they show that the sample complexity required for learning ReLU neural networks with $L $ layers each with width at most $3d$ (where $d$ is the input dimension) and bounded norm coefficients requires exponential in $d$ and $L $ samples. In contrast, learning to $\ell_2$-error requires polynomially on $d$. They also give (almost) matching upper bounds. The results in the paper allow for the underlying algorithm to be adaptive in the selection of the data points, that is, it can query the points necessary to give the required guarantee. The key idea is to use the flatness of ReLU to show that the NN class contains functions of the following form: for any $y\in \mathbb{R}^d$ the function is non-zero only for a small ball around point $y$ in the space. Therefore, to learn the function from samples to $\ell_\infty$ accuracy, one needs to sample a point in every small ball, that is, cover the entire space which requires exponential in $d $ samples. The norm bounds on the weights governs the radius of these balls and the base of the exponent.
strength_and_weaknesses: Strengths: 
- The paper makes progress towards understanding the information theoretic limits of robust learning, which is an important problem in the light of adversarial vulnerabilities in current ML models. The lower bounds hold for all algorithms and not restricted to some computational models.
- The paper is well-written and easy to follow. The authors do a good job of thoroughly discussing the theorem statements and their implications.

Weaknesses:
- I am not convinced by the technical depth of the main result and more generally the setting. It is worst-case in nature and for a very general class. This makes the lower bound weaker, since getting $\ell_\infty$ bounded error in such a setting seems naturally hard. The examples in Remark 1.3 where such a goal is tractable are restricted to polynomials/linear functions which have special structure in terms of interpolation.
- Experiments are in very low dimensions. Trends for different errors also seem similar. Hence, it is unclear what the reader should take away from the experiments.
clarity,_quality,_novelty_and_reproducibility: I have some questions that are not clear from the paper:
- Why does the width need a dependence on $d$? What is the actual dependence on the width independent of $d$?
- The construction of these bump functions uses only 2-layers to actually construct the “hat” function and then the rest of the layers are pass through layers that affect only the scaling of the function (hence the Lipschitz constant). Similarly, the width shows up in its interplay with the norm constraint affecting the scaling. Assuming that the $\ell_1$-norm of the weights is bounded by 1 at each layer would remove this blow-up. Is there any use of depth outside of this?
- What are the differences with the constructions in Telgarsky 2015? I understand that the work deals with purely approximation and not sample complexity, but they do bound the total error in the interval.
summary_of_the_review: Overall, in my opinion, the worst-case nature of the result makes it not very interesting. The requirement of $\ell_\infty$-bounded error becomes extremely strong, and not very insightful for realistic models. As the authors point out in the limitations, studying this in a more reasonable sub-class of neural networks or understanding uniform error restricted to some manifold or under some perturbation model would be more useful and interesting.

Post rebuttal: Increased the score from 3-> 5.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors study the problem of learning classes of deep, feedfoward neural
networks with ReLU activations through with guarantees in terms of $L^\infty$
accuracy, through the angle of sample complexity requirements. More precisely,
they consider a rather general model where a learner can adaptively query
points of the solid cube $[0, 1]^d$ for evaluations of an unknown deep ReLU
network $f$, and provide lower bounds on the number of queries necessary for
any (possibly randomized) such algorithm to output an $\varepsilon$
approximation to $f$, for all possible choices of the network $f$ in a
restricted class (bounded number of neurons, bounded depth, and norm-bounded
weights). The obtained lower bound grows exponentially in the dimension $d$ and
the network depth, demonstrating a strong barrier to learning in this setting.
Upper bounds are derived in the same algorithmic setting (as before,
computational complexity is not considered)


strength_and_weaknesses: ## Strengths

- The lower bound holds very generally and without conditions associated with
  other SQ-type lower bounds that apply to more natural algorithms like GD/SGD.
- The focus on $L^\infty$ estimation has possible connections to
  security-critical settings where one is interested in the ability to recover
  the parameters of a neural network model.
- The paper is very clearly written and well-referenced. It is possible to
  understand the paper's main results at a technical level without having to
  reference notation/etc. in the appendices because background information is
  explained completely.

## Weaknesses

Although I have not checked the proofs, the authors' results seem reasonable to
me. Therefore most of my comments here will not be weaknesses with the
(well-written) paper per se, but rather questions about the motivation and
implications for practice of the theory.

- The requirement $B \leq 3d$ in Theorem 2.2 seems unnatural -- can this be
  improved? Is there a "functional" description (e.g. from the proof) of what
  this constraint implies?
- The exponential dependence on dimension may be seen as not too
  surprising: one needs a number of points exponential in dimension just to
  cover the input space, and the class seems complex enough that it is really
  necessary to have such a dense covering. What seems more interesting is
  that it is also necessary to sample exponential in depth. However, one is
  naturally curious about the extent to which this is simply because the
  learning problem is extremely hard -- arbitrary depth-L networks can
  parameterize very complex functions, with many linear regions (e.g.
  following Montúfar's work) -- and whether the same exponential dependencies
  would appear for learning e.g. a Sobolev or a Besov class. Another angle
  on this question would be to consider how the bound would look for learning a
  "smoothed" class of ReLU networks, e.g. those with a bounded number of
  linear regions, or the like. The behavior that may be most interesting as a
  theory for the practical successes of deep learning would be one that
  captures the ability of deeper networks to *adaptively* represent complex
  functions, when it is necessary, given sufficient samples -- and it seems
  this kind of explanation is out of reach of the present theory, given that
  the class being learned contains extremely complex functions implemented by
  general depth-$L$ networks. (The authors mention this as a direction for
  future work in the conclusion; it would be nice to hear some thoughts in this
  context in the response.)
- Similarly to the previous point, I am not completely convinced about the
  connection the authors make between their result and adversarial robustness
  -- although indeed in the setting of adversarial robustness one is interested
  in $L^\infty$ stability guarantees, these are generally not in the
  teacher-student setting where the training labels are generated by some deep
  neural network, but rather by some dataset with certain structures
  (statistical, geometric, etc.). In this latter setting, the requirements to
  be robust to worst-case corruptions may be quite different from the setting
  that is considered here. I think this is especially pertinent with regards to
  the $\exp(L)$ dependence in the authors' lower bound -- how would the
  corresponding lower bound look in the setting of a structured, labelled
  dataset?


## Minor / Questions / Comments
- Is there a version of Theorem 1.1 that applies to networks of arbitrary
  intermediate widths (like Theorem 1.4)?
- In Theorem 1.1, when $q \leq 2$ the result seems to be vacuous in high
  dimensions unless $\varepsilon$ goes to zero; on the other hand, it seems
  that working through the corresponding bound in Theorem 2.2 implies a
  nonvacuous result in high dimensions (it seems the dependence on width $B$
  has been worst-cased to a dimension dependence in Theorem 1.1). Would it
  make sense to state the result differently? Reading Theorem 1.1, I have the
  sense that the bound is very loose with respect to Theorem 1.4 for "mild
  regularization" (whereas with the actual dependence, the gap between the
  bounds becomes much clearer).
- Some comments on *what the class of functions implemented by the
  architectures considered is* would be helpful here in assessing the degree
  of difficulty of the learning problem, relative to some of the other
  classes mentioned in Remark 1.3 -- e.g. in the proof idea section describing
  the bump function, can we also know Sobolev estimates for these functions (to
  better understand what the class being embedded is, effectively)? 
  - The proof sketch of the lower bound reminds of some of the description of
  Bubeck and Sellke's work on robustness is there any connection here?
  (Keywords like Baum's construction of memorizing networks and its
  generalization by Bubeck et al., etc...)
- Could the authors provide a proof sketch for the upper bound in Theorem 2.4?
  Given that this upper bound applies to an adaptive, potentially randomized
  algorithm, is it safe to assume that this upper bound applies to an algorithm
  that is "stronger" than e.g. empirical risk minimization under a
  distributional assumption, which as the authors mention in related work has
  been considered in works with a similar flavor? I am just interested in how
  to compare this upper bound to results I have seen in related work on $L^p$
  $p \ll +\infty$ learning of ReLUs with certain algorithms.
- It might be more correct to say that the "minimal error over neural network
  target functions" is estimated/approximated, rather than "computed", on page 8.

clarity,_quality,_novelty_and_reproducibility: The paper builds off various works on expressivity and learning of deep
feedfoward neural networks to establish a new result, with a motivation that
seems to also be new. The work is clearly written and well-referenced.
Mathematical claims are very clearly written, without ambiguous notation.


summary_of_the_review: 
The paper presents a solid contribution to the understanding of teacher-student
learning of neural networks to a high degree of uniform accuracy. I am unsure
of the general implications of the theory given the student-teacher setting,
but I think the work may lead to many interesting follow-up investigations, as
the authors mention in the conclusion.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper aims to show that for any learning problem formulated over target classes containing ReLU neural networks of a prescribed architecture, the number of training samples needed for an adaptive randomized algorithm to guarantee a given uniform accuracy scales exponentially both in the depth and the input dimension of the network architecture.
strength_and_weaknesses: ### Strengths

- The paper considers an unorthodox (but important and impactful) statistical learning problem: sample complexity for uniform accuracy (instead of expected accuracy). The motivation and impact of such an analysis are discussed carefully throughout the manuscript. The main ideas and techniques of the work were developed based on well-founded rationales and in general, the paper is well-written with a sufficient literature review.
- One of the important (and maybe novel) insights of the work about neural networks in this learning setting is that while there exist functions that can be exactly represented by small neural networks, these representations cannot be inferred from samples because of the network’s expressiveness.
- The mathematical analyses of the work are rigorous, intuitive, and seem correct.
- One main technical contribution of the work is to explicitly show that neural network models contain a large class of “bump functions” with estimable L^p norms and disjoint supports. Thus, with a “small” number of observations, no algorithm would be able to distinguish those functions from the zero function, or one another. The sample complexity depends on p, and when p=\infty (uniform accuracy), the dependency is exponential.
- Beyond this direct application of the analysis, several components of its explicit computations would be of great interest to a broader audience. For example, the bump functions, which have support in B(y, 1/M) and are greater than 1/2 in B(y, 1/(2Ms)), are very similar in spirit to the concept of mollifiers and approximation of the Delta Dirac function. The fact that they can be represented by a standard feed-forward ReLU network could be a useful tool in other contexts.

### Weaknesses

- None noted.

### Additional comments

- As stated in the comments, I think the explicitness of Lemmas A.1 and A.2 are technically interesting, and some detailed descriptions of the insights of those constructions would be appreciated. For example, the steps (and the constructions of the layers) in the proof of Lemma A.2 have their own meaning (representing the hat functions, representing the bump functions, controlling the norms), and some verbal descriptions of what they do would make the parts more accessible. (I want to note that it’s just an optional comment and will not affect my review decision.)
clarity,_quality,_novelty_and_reproducibility: (see Strengths and Weaknesses)
summary_of_the_review: The paper rigorously addresses a meaningful question in applied machine learning. The work provides novel insights into the learning problem, and its technical contributions might be of broad interest.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Summary
---
This paper studies the difficulty of learning an unknown ReLU neural network with a fixed number of layers by another ReLU neural network with the same number of layers. The authors take a learnability/information theoretic approach and derive bounds on the sample complexity that any learning algorithm must achieve. They show that when the learned network is required to be close in $L^\infty$ norm, the sample complexity scales at least exponentially in the depth and input dimension, even if the learning algorithm is allowed to have arbitrary runtime. In contrast, sample-efficient learning is possible when the error is measured using the $L^2$ distance. The authors also provide upper bounds on the sample complexity and conduct experiments to verify their theoretical results.

Strength
---
- The paper is well-written. The results are non-asymptotic with a clean and constructive proof and are significant for understanding the complicated nature of the neural network function class.
- One of the important insights of the work is that while there exist functions that can be exactly represented by small neural networks, these representations cannot be inferred from samples because of the network's expressiveness. The paper explicitly shows that neural network models with bounded norm coefficients contain a large class of “bump functions” with estimable $L^p$ norms and disjoint supports. 

Weaknesses
---
- The constructed hard function for the lower bound proof makes use of sharp bumpy hat functions, which are not natural in real-world settings
- The bound for the case of $q<2$ may be vacuous and unreasonable. There is a large gap between the lower bound and the upper bound for $q\le 2$, and the main theorem only applies when $\epsilon=o(1/d)$ , making it vacuous in the high dimensional setting. The authors mostly agreed with this point in their response.
- It may not be very suprising that learning in $L^\infty$ norm is harder than learning in $L^2$ norm.


justification_for_why_not_higher_score: - It may not be very surprising that learning in $L^\infty$ norm is harder than learning in $L^2$ norm.
- Since this paper is mostly a hardness result (lower bound result) and seems too theoretical to the broader audience of ICLR, I didn't recommend oral/spotlight presentation for this paper.
justification_for_why_not_lower_score: - The results are important. This paper shows a separation between $L^\infty$ learnability and $L^p$ learnability when $p$ is finite. 
- The paper and the proofs are well presented.
Decision: Accept: poster