Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the lower bound of the approximation error with respect to Lp norm. The approximation error means how well functions f can be approximated by functions g_w with parameters w. Besides the general case, the authors also provide results for some special cases where g_w is to a feed-forward neural network, f is Holder balls and monotonic functions. Matching upper bounds of the approximation error for those special cases are also provided to show that these bounds are relatively tight.
strengths_and_weaknesses: Strength (dominating): The result and contributions are clearly stated. Besides, this paper has good writing quality and most of the contents are easy to follow.

Weaknesses: Some details need more explanation. See my questions below.
questions: 1. In Section 4, the authors study the situation of monotonic functions. I wonder why monotonic functions are special/important in the sense of approximation performance.

2. It is not easy to see the effect of p in most of theorems and corollaries. Maybe the authors can provide some explanation on how different p affects the bound of the approximation error.

3. When considering the feed-forward neural network, the activation functions are limited to piecewise-polynomial ones (e.g., ReLU). Maybe the authors can discuss why piecewise-polynomial activation functions are essential for the current derivation, or, how other types of activation functions (e.g., sigmoid) make the estimation of approximation error difficult.
limitations: N/A
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper considers the problem of approximating functions in a family F by functions in another family G. More precisely, they consider the lower bound of the best approximation error $\sup_{f \in F}\inf_{g\in G} \Vert f - g\Vert_{L_p(X,\mu)}$ for real-valued functions, where $X$ is subset of $\mathbb{R}^n$ and $\mu$ is a probability measure on $X$.

The paper obtains a lower bound for bounded functions in terms of an inequality constraint which is expressed in terms of the packing number of $F$ and the fat-shattering dimension of $G$. The paper then uses this result to derive the lower bounds for the approximation of Hölder-continuous functions and multivariate monotonic functions by piecewise polynomial feedforward neural networks.

The main technical argument is heavily built upon a previous result by Mendelson. Still, it is nice work to employ it to solve the problem here, which was an open problem and believed to require new machinery other than the VC dimension theory, and proving a lower bound of the packing number of different families of functions is also nontrivial.

strengths_and_weaknesses: Strengths: Earlier results only concern the approximation in the L_infinity norm and the approximation in the L_p norm was an open problem, which was previously believed not within the reach of the VC dimension theory. This paper solves the open problem with VC dimension theory.

Weaknesses: The lower bound is still quite messy and it is not known how tight it is. The techniques of the core result was largely done in the previous works, but I don’t think this per se should be evaluated against the acceptance of the paper.

questions: I do not have any major questions. It would be good if the authors could give some comments on the tightness of their lower bounds.

The following are some minor points on writing:
- Line 25: “functions f in F can” -> “can functions f in F”
- Line 29: sup norm -> supremum norm (or just write L_infty norm if space is an issue). This has multiple occurrences throughout the paper.
- Line 29: the definition of sup norm is incorrect - it should be the essential supremum instead of supremum. The definition in Line 97 is correct though.
- Lines 49 and 53: how is the smoothness of a function defined? I don’t see this in the ‘Main definitions and notation’ section, either. Do you mean the Hölder exponent?
- Line 53: prove -> proves
- Line 61: add a comma before “where”
- Line 102: the usual notation of the packing number is like $M(F, \Vert \cdot \Vert, \epsilon)$, where the parameters are in a different order.
- Line 137 and footnote on the same page: inequation -> inequality; inequation is a word that is rarely used or used only when the direction of the inequality is unknown
- Line 158: above corollary -> corollary above
- Line 194: “$\leq \operatorname{fat}\_{\epsilon/32}(G)$” should be “$\leq \operatorname{fat}\_{\gamma}(G)$”
- Line 219: the measure lambda has been defined in Line 97, so the sentence can be omitted.
- Lines 679 and 680: “cancels” - I think the correct English word is “vanishes” if you mean the functions are zero outside the region

limitations: N.A.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper proves a new lower bound on the worst-case approximation error of functions in a set $F$ using functions in another set $G$. The bound is then instantiated in the specific case where $G$ is a piecewise-polynomial feedforward neural network. The approximation is considered in $L^p(\mu)$ norm for any $p \geq 1$.
strengths_and_weaknesses: The paper is original, clear, well written. Although I haven't checked all details, the authors appear to have done a good job at carrying out precise arguments.

The significance on this paper is however not clear. The results are very theoretical and there is no evidence that they would be relevant for any practical application.
questions: If possible, I would consider clarifying whether there would be any practical application of the lower bounds proved in the paper.

A small correction: in line 132, "finite" -> "compact" (or "finite-length", or something else)
limitations: I don't see any issues here.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper provides a general approximation lower bound result in the $L^p$ norm, and its applications to the neural-network setting. This result is built upon a probability result in [1], which relates the packing number in the $L^p$ norm of a function set $G$ and the fat-shattering dimension of $G$. Given this result, one can derive the approximation in the $L^p$ norm in a relatively straightforward way. Combining existing results on the pseudo-dimension of neural networks, the authors apply the result of $L^p$ norm approximation between two function classes to the neural-network setting. 

The authors further apply the neural-network approximation result to the Hölder-ball and monotonic-function settings, to demonstrate the similarity and difference of approximation in the sup norm and the $L^p$ norm.

[1]S. Mendelson. Rademacher averages and phase transitions in glivenko-cantelli classes. IEEE Transactions on Information Theory, 48, 2002.
strengths_and_weaknesses: Strengths:
1. Studying the approximation in the $L^p$ norm is a theoretically interesting problem in its own. Though the approximation result does not appear very surprising given the existing results provided by the authors, the approximation in the $L^p$ norm is a necessary complement to our current understanding of the approximation problem.
2. This paper is well-written. The results are technical, however, the authors have presented the paper in a quite accessible way.

Weaknesses:
Moving from sup norm to $L^p$ norm is an interesting mathematical and theoretical problem. However, it is not obvious how in practice these two norms can make a difference. 
questions: Could the authors explain what practical ramifications this new approximation in $L^p$ norm result can bring given the known sup norm approximation results?
limitations: No major concens. One notational suggestion: I believe that the constants $c_1$ in Equations (10) and (11) are different. You might consider changing $c_1$ in Equation (11) to $c_3$.
review_title: null

Meta-review: metareview: The paper provides novel lower bounds on function approximation, relating $L^p$ norm approximation error to combinatorial complexity measures of both the approximating and approximated functions classes. These bounds are instantiated for approximation via piecewise-polynomial neural networks. 

There is a consensus among the reviewers that the results of the paper are novel, solve an open problem, and follow from deep technical insights. Consequently, I concur with the majority of reviewers and recommend acceptance of the paper.
confidence: Certain
Decision: Accept