Blessing of Dimensionality for Approximating Sobolev Classes on Manifolds

We thank the reviewer for the kind review. Please find point-by-point responses to the concerns and comments below.

It's not clear to me how applicable these results are in practice. Even when data satisfies the manifold assumption, the intrinsic dimension d may be quite large. It is not clear how large the authors think d is in practice, and how large a d would make these results applicable vs vacuous. For MNIST, for example, it's often given that d is between 7 and 14, depending on the digit. One can assume d is much larger for more challenging problems, maybe 20-40? In this case, the error bound $1/n^{1/d}$ is vacuous, unless the number of data points n is astronomically large (e.g., if d=20 we need $10^{20}$ data points!).

This work is intended as an extension of classical theory into the manifold hypothesis setting. Existing approximation results are equally vacuous for standard imaging examples, and moreover, estimates of intrinsic dimension vary wildly between methods. However, from the independence of ambient dimension, practical guidance could include minimizing the intrinsic dimensionality by reducing the number of uninformative variates. Our results quantitatively show that such variates increase the pseudodimension required to uniformly approximate the Sobolev ball with an exponential factor.

We would like to clarify that in Theorem 3.1, $n$ refers to the pseudo-dimension with which we are allowed to approximate the Sobolev class. As a concrete example, pseudodimension of ReLU neural networks scales as $\Omega(W \log W)$, where $W$ is the number of parameters, see for example Theorem 3 in [Bartlett2019]. The dependence on data points comes afterwards, using e.g. Proposition 2.3, albeit giving a sample complexity that is linear in the allowed pseudodimension. Towards the gap between the theoretical dataset requirements and practical machine learning, this could be because the Sobolev class is still a very descriptive class of functions. Rates for more structured classes of functions could be cause for future work.

I don't understand why the main result, Theorem 3.1, is measuring nonlinear n-width between the Sobolev space $W^{1,p}$ and the Lebesgue space $L^q$. It's really unclear to me why this implies anything about the difficulty in approximating Sobolev space functions. I'd like to see this clarified.

The main result concerns the approximation of the unit Sobolev ball using function classes of finite pseudo-dimension, where the approximation distance is measured in terms of maximum $L^q$ distance. Since the unit Sobolev ball has infinite pseudo-dimension, approximation with finite complexity classes is necessary for computation. We provide a lower bound for how much complexity is required to ($L^q$-uniformly) approximate functions in the unit Sobolev ball, which can be informally translated as how complicated the Sobolev ball is.

References

[Bartlett2019] Bartlett, P. L., Harvey, N., Liaw, C., & Mehrabian, A. (2019). Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 20(63), 1-17.

We thank the reviewer for the kind review. Please find point-by-point responses to the reviewer's concerns.

The result is not too surprising on the 1,p-Sobolev class, and considering that higher Sobolev space can even be an RKHS [1], one would expect major improvement on the rate. Also using volume comparison to control the packing number is rather standard, and one might further ask if the same technique is applicable to metric measure spaces or RCD spaces, though I understand this technicality may not be particularly befitting of this venue.

Indeed, we recover rates as given by Euclidean intuition. We note that since we derive rates in negatively curved space, the rates are slightly worse than Euclidean. Conversely, in positively curved space, one may be able to derive better constants using more precise bounds when using Bishop--Gromov. Asymptotically however, one should expect the same rates as the Euclidean case, as the neighborhoods given by packings informally become flat.

Faster rates require higher regularity of $W^{k,p}$, which change the lower bound from $n^{-1/D}$ to $n^{-k/D}$ in the Euclidean case. We note that construction of functions with appropriately bounded higher derivatives is more difficult than the Euclidean case due to the presence of curvature, and the authors are not aware of a result similar to [Azagra2007]. While the authors believe this is possible, this could introduce additional superexponential dependence on $d$, and require a uniform bound on the Riemann curvature tensor instead of only the Ricci curvature.

We speculate from a brief look at [Sturm2006] that the result may still hold in RCD spaces given appropriate analogs of Bishop--Gromov, as well as a uniform control on the measure of small balls (Prop. 3.3). However, the authors are not familiar with this line of work.

Typos: Definition 2.7 is defining packing number not covering number, and also metric entropy is not commonly defined this way. This version of metric entropy is exactly the same as packing number, hence (7) is not needed. (The key proposition C.1 is correct.) $\mathcal{C}Pf_a$ out side the balls on line 375 is not necessarily 0.

Changed the incorrect naming from covering number to packing number (Def. 2.7). We believe there are separate communities that define metric entropy differently (namely log of the covering number). We have replaced "metric entropy" with "$\epsilon$-metric entropy" in Definition 2.7 and Lemma C.2, as there does not seem to be an alternative name for the cardinality of the largest $\epsilon$-separated subset.

By definition in Equation (29), $\mathcal{C}$ clamps any function to 0 outside the balls $B_r(p_i)$.

References

[Sturm2006] Sturm, Karl-Theodor. ``A curvature-dimension condition for metric measure spaces." Comptes Rendus Mathematique 342.3 (2006): 197-200.

[Azagra2007] Daniel Azagra, Juan Ferrera, Fernando Lopez-Mesas, and Yenny Rangel. Smooth approximation of Lipschitz functions on Riemannian manifolds. Journal of Mathematical Analysis and Applications, 326(2):1370–1378, 2007.

We thank the reviewer for the detailed review. The authors would be happy to add additional background into the appendix if the reviewer believes that it would aid the readability of the paper. The typos have been fixed in the revised paper. Please additionally find below point-by-point responses to the reviewer's concerns.

Not only is the result of Theorem 1 independent of ambient dimension $D$, the ambient dimension does not appear anywhere in the estimates. This is somewhat odd because the abstract mentions the manifold hypothesis which concerns both $D$ and $d$. In some similar approximation bounds, there is typically some dependence on $D$. The authors should address this.

Existing approximation results typically consider explicit constructions to construct upper bounds on the statistical complexity. Such constructions generally come in terms of neural networks, in which the dependence on the ambient dimension comes naturally as a function of the output dimension. In this work, we consider instead an abstract manifold without any extrinsic structure as given by (isometric) embeddings into $\mathbb{R}^d$. As such, there is no dependence on the ambient dimension $D$ in our results.

In a similar vein, the authors do not present a connection between the sample complexity mentioned in Proposition 2.3 and the main Theorem 1, as far as I can see. The assumed connection is that, due to this property of classes with finite pseudo-dimension $\mathcal{H}_n$, the Sobolev class can also be estimated with the sample complexity given in (2), once the approximating class $\mathcal{H}_n$ is determined, it can be estimated with this sample complexity. This connection should be made somewhere.

Indeed, our result provides a worst-case lower bound on the approximation error, assuming that the true solution lies in an area that is not well approximated by $\mathcal{H}_n$. There is a tradeoff between the approximation between the risk minimizers in the Sobolev ball and in $\mathcal{H}_n$, as well as the generalization error incurred within $\mathcal{H}_n$, with the former decreasing and latter increasing as the allowed pseudo-dimension $n$ increases. Our result then characterizes the first tradeoff, while the second is given by classical generalization bounds/statistical complexity results. We add a short section to discuss this, left to the appendix due to space limitations in the main text.

The main structure of the proof is almost identical to (Maiorov and Ratsaby, 1999), except the construction of the $L^1$-separated set of functions, due to the domain being a manifold. There are a few questions about the extended lower bound, which I ask below in the "questions" section.

We address the reviewer's questions below. We note that in addition to the generalization from the unit hypercube $[0,1]^D$ to a general (compact separable Riemannian) manifold without boundary, our result also gives the exact dimension dependence by giving explicit constants, further extending (Maiorov and Ratsaby, 1999).

The Theorem 1 lower bound (12) has a dependence on $p$, unlike in the Euclidean case (Maiorov and Ratsaby, 1999). Is there a plausible reason for this, i.e. is $p$ there for an inherent reason?

The dependence arises from the fact that the volume of a manifold is not identically 1, as the Euclidean case considers only the unit hypercube $[0,1]^d$. The dependence on $p$ comes from an application of H"older's inequality to bound the constructions in their respective spaces, and are always attached to a $\mathrm{vol}(M)$.

Why is Theorem 1 restricted to the case $K<0$? What is different about the positive curvature case?

The estimate will be tighter in the positive curvature case, as volume estimates will be tighter. We present the result for the case where $K<0$ since this is more general. The proof can be easily modified for $K>0$ by changing Equation (40) to the corresponding form for elliptic space, namely replacing $\sinh(\sqrt{|K|t})$ with $\sin(\sqrt{Kt})$ (for $\rho < \pi \sqrt{|K|}$) to derive the same result, but with a different requirement for $r$ in Equation (51).

line 535: it is mentioned that the cutoff functions with bounds on higher derivatives is difficult to construct, but I am having trouble seeing why this should be so. Can the authors explain further?

While intuitively simple in the Euclidean case, going further than one derivative introduces Riemann curvature terms that must be individually controlled (corresponding to curvature when computing cross derivatives), such as in Equation (8). The authors are unaware of similar constructions in the literature that explicitly uniformly control the higher-order covariant derivatives. While a uniform bound on the Riemann curvature tensor $g^{ij}$ would allow for this, we consider only bounded Ricci curvature as it is more standard in the literature.