Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies adaptivity of deep neural network models to anisotropic smoothness properties of target functions. Namely, when the target function belongs to an anisotropic Besov space (i.e. it has different levels of smoothness in different input directions), certain classes of deep networks may provide a rate that only depends on the average smoothness (i.e. the harmonic mean of certain smoothness parameters in each direction), instead of the worst-case smoothness. This is also studied for target functions that consist of compositions of such anisotropic Besov functions and compositions with an affine function. The authors also provide minimax lower bounds showing that linear estimators (such as kernel methods) may not adapt to such structures, and may provide exponentially worse sample complexity for some specific models.
main_review: The paper studies adaptivity properties of deep networks, a topic which has recently gained a lot of attention, as it can yield an understanding of what kind of functions deep learning can learn efficiently, and more efficiently than other standard procedures such as kernels. It provides a comprehensive study of adaptivity of neural networks to anisotropic smoothness, which is a useful prior, and has not been previously studied in this context. In this sense, I find the paper significant and novel. It is also very well written. I thus recommend acceptance.

A few minor comments:
* the authors briefly mention a motivation for anisotropic smoothness in the context of invariances on image problems. This seems quite interesting but the current explanation is very brief - I encourage the authors to expand further on this, and perhaps on other motivating examples.
* why is tilde{beta} in (1) defined like this instead of just as the harmonic mean? I find that this makes the rates with +1 instead of +d a bit puzzling to parse, and would find it more natural to just have the harmonic mean, so that you immediately recognize the usual rate when all the betas are equal (but I leave this choice to the authors).
* some typos: L199: d beta -> beta / d? L301: why the red text?


-------- update after rebuttal -------

Thank you for the response. I think these additional comments on motivating examples would be useful in the paper, so please do include them in the final version.
limitations_and_societal_impact: yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper provides a constructive approximation results of deep neural networks for approximating functions in anisotropic Besov spaces. The approximation result is further used to show the statistical convergence of using neural networks in a nonparametric regression problem. The highlights of the work fall in the circumvent of the curse of data dimensionality, when the anisotropic Besov space is not homogeneous in every canonical direction.

Some recent works study the adaptivity of neural networks to the intrinsic structures in data (Nakada & Imaizumi, 2020; Schmidt-Hieber, 2019; Chen et al., 2019), which can partially explain the practical success of neural networks in high-dimensional data applications. This work takes a different perspective: rather than considering the low-dimensional structures in the data manifold, the authors focus on "low-dimensional" structures in the function space. Intuitively, the "low-dimensional" structures in the function space refers to functions having very mild fluctuations in certain directions. This is a relatively less explored direction, yet of importance.

The paper is well organized and relatively easy to follow.
main_review: I am tending positive on the paper. There are a few questions.

1) Is it true that the composition of two anisotropic Besov functions is still an anisotropic Besov function? If so, I don't see the merit of considering two models of the true functions in Section 2.2, as deep composition can also be viewed as a special case of affine composition model, and vice versa.

2) Per definition of $\tilde{\beta}$ in Equation (1), when $\beta_j$ is approximately equal, there is still the curse of data dimensionality. However, when only a small fraction of $\beta_j$'s are small (severe fluctuation of the target function in these directions), the result is free of the curse. In such a case, is it possible that the target function may be approximated first by a function only supported on those significant coordinates, and then approximate the function on those significant coordinates? It seems that this argument translates finally to some low-dimensional structures in data. Can the authors kindly comment on this?

3) A practical motivation of studying anisotropic Besov spaces seems missing.
limitations_and_societal_impact: The authors briefly discussed the limitations in Section 7. No direct negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors investigate the approximation and estimation error of deep neural networks on anisotropic Besov spaces. It has been shown that Holder and Sobolev function spaces are plagued by an unavoidable curse of dimensionality, and a line of research has focused on showing how deep neural network can adaptively beat this curse on restricted classes of functions, such as compositorial functions or functions that depend on a low dimension subspace. This work focuses on Besov spaces, but with anisotropic smoothness requirements (which do not require for the data to lie exactly on a low dimensional subspace) and consider deep composition model similarly to Schmidt-Hieber (2018), but with functions in the anisotropic Besov spaces (they don’t need to be low-dimensional). They show that the rate of approximation/estimation depends on the harmonic mean of the directional smoothness parameters, instead of the worst case. In particular, this harmonic mean is independent of the dimension if the function is non smooth in only a few directions. Their results require bounds on the width, depth, sparsity, and infinity norm of the weights. They further show that the estimation error rates are minmax optimal. Finally they consider linear estimators and show a lower bound on their minimax rate, that is larger than the minimax rate of neural networks, which illustrates the poor adaptivity of linear estimators to the intrinsic dimensionality of the data.
main_review: This paper present new strong results which combines expressivity and generalization bounds on deep neural networks. The adaptivity to the average smoothness instead of the worst case smoothness is particularly interesting. For these reasons, I recommend the paper to be accepted. 

It would be great to comment more on the dependency of the different quantities on $n,d$ and other parameters. The current theorems are difficult to parse. For example, $N$ is proportional to the number of non zero parameters? For $\tilde{\beta}$ to not be of order $1/d$, $m$ needs to scale with $d$, is $L_1(d)$ linear in $d$ then? I think adding a few remarks would go a long way in improving the readability of these results.

While I think this represents an interesting theoretical work for the approximation/function space estimation community, I wonder how much this approach can help understand practical success of deep learning (in particular, I disagree with the last sentence of the conclusion ``''these analyses strongly support the practical success of deep learning from a theoretical perspective’’). In particular, numerous work have demonstrated that one cannot disentangle computational and statistical aspects in deep learning. Furthermore, the theorems have a sparsity requirement, which is usually not the case for practically trained neural networks. 

Typos: reference to Theorem 6 in Theorem 2? Reference to equation 8 bottom of page 6?


-------- update after rebuttal -------

Thank you to the authors for the response. I am satisfied with the paper and the updates mentioned by the authors. I keep the same rating.
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: This is a theory paper that analyzes deep neural networks through the lens of anisotropic Besov space. The paper provides a comprehensive study of adaptivity of neural networks to anisotropic (=direction-dependent) smoothness. The paper is clearly written and the authors have carefully positioned their work relative to prior works.
Decision: Accept (Spotlight)