Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Authors in this work study the approximation of high-dimensional Lipschitz functions and characterize the size of the NN required for an arbitrarily good approximation. They are able to say if the data $x \in R^{D}$ is $\rho$-JL embedable in a low-dim manifold $R^d$, then there exists an apporpriate deep network (with say ReLU activation) that can approximate any $L/(1-\rho)$-Lipschitz function $g: [-M,M]^d \rightarrow \mathbb{R}^p$, then there exists a deep network with only a small constant increase in depth, and the size of the network that increases exponentially in $d$ instead of $D$ (the input dimension). They show this by an existence of a JL-embedding for general sets in $\mathbb{R}^D$, in terms of it's Gaussian width (or covering numbers). They use these results to obtain the required size of NN to get an $\varepsilon$-approximation of inverse maps that are Lipschitz continuous.

strength_and_weaknesses: Strengths:
Understanding training w.r.t the low-dimensional embeddings are important and this work has a good characterization of the size of the network required for Lipschitz continuous functions in high dimensions. 

Prior works such as (Chen et al. 2019) characterize the number of neurons that depend on the curvature of the low-dimensional manifold in question which can be difficult to estimate. This work sort of alleviates, with a less abstract notion, which are Gaussian widths of the set or the covering number, which seem to be more amenable to estimation from data.

The size of the network grows exponentially in $d$ rather than $D$, the input dimension and the results offer for tradeoffs in practice.

Weakness/Clarifications:
Are there any lower bounds known for the size of the networks? Could the authors comment on the tightness of the size of the networks.

It would have been great to see experiments on some high dimensional datasets as there are usually gaps in approximation characterizations and its training and generalization qualities. 

It would be nice to get some bounds on the samples required to for a reasonable approximation, when you estimate the GW or the covering number of the set. Or at least a some discussion pertaining to this.
clarity,_quality,_novelty_and_reproducibility: The paper is written clearly and well motivated and the techniques are novel. 

Minor comments:
The citation (Iwen et al. accepted (See Arxiv)) could be just changed to it's arxiv link.
Minor typo: Guassian->Gaussian in the last line of page 2.
summary_of_the_review: Overall it is an interesting work on the size of NNs required for approximation of Lipschitz continuous functions in high-dimensions by embedding them in a low-dimensional manifold with complexity parameters that are practical to estimate, as compared to prior work. It would have been great to see some experiments to see this in action.

UPDATE: After the response and the other reviews, it feels like many clarifications were not convincing and thus I decrease my score to 6.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors use the Johnson--Lindenstraus lemma to argue that a Lipschitz function over a suitable low-dimensional subset of a high-dimensional ambient space can be approximated by neural networks whose complexity mainly depends on the intrinsic dimensionality of the low-dimensional set, and only weakly on the ambient dimension. The authors extend the JL lemma to domains whose unit secant sets have controlled covering numbers or Gaussian width (effectively: low-dimensional domains). They give results for fully-connected and convolutional networks and apply them to two compressed-sensing-style problems.

strength_and_weaknesses: The theme of approximation rates that adapt to intrisic dimensionality is a familiar one in machine learning and signal processing. The current manuscript studies a natural construction where the data is first linearly projected into a low-dimensional Euclidean space. The injectivity and stability of this projection are guaranteed by the JL lemma and its extension to continuous sets provided in the manuscript.

In my opinion the main strength of the manuscript is that it focuses on a specific but still sufficiently general setting, and that it uses familiar tools to get a very explicit result that is natural and easy to understand. As far as I can tell, the mathematical arguments are sound, and the presentation is clear.

On the critical side, the novelty is in my opinion limited in view of existing work. The presented results seem to be a special case of 

``Universal Approximation Theorems for Differentiable Geometric Deep Learning'', JMLR, Anastasis Kratsios, Léonie Papon; 23(196):1−73, 2022.

To see this, set

- $I = 1$ 
- $X = \text{the subset S of}~\mathbb{R}^D$
- $Y = R^p$
- $\varphi(x) := (1/2M) * (Sx - (M,\ldots,M))$; i.e. the JL-embeding S->R^d and the rescaling of the cube [-M,M]^d to the unit cube [0,1]^d
	note that this map is injective and continuous (since it is bi-Lipschitz) whence it satisfies Assumption 7
- $\rho$ be the identity on R^p
- Take the exponential maps to be about the origin; i.e.
- Exp_{R^d,0}(u) = u +0 =u
- Exp_{R^p,0}(u) = u +0 =u

In fact, the above paper derives sharper approximation rates that are dimension-free when $f \circ \varphi^{-1}$ admits a Whitney-type extension of $\varphi(S)$ (Corollary 45). Related arguments are used Theorem 3.3 in ``Non-Euclidean Universal Approximation'' by Kratsios and Bilokopytov; in particular that should allow to substitute any universal regressor.


The present work is also closely related to

- Deep Fried Convnets: https://openaccess.thecvf.com/content_iccv_2015/papers/Yang_Deep_Fried_Convnets_ICCV_2015_paper.pdf
- NN approximation w/ random projections: https://core.ac.uk/download/pdf/153400703.pdf
- The classic work on nonlinear learning with local coordinate coding: https://papers.nips.cc/paper/2009/file/2afe4567e1bf64d32a5527244d104cea-Paper.pdf
- Direct inference on compressive measurements: https://ieeexplore.ieee.org/document/7532691
- Sketching and neural networks: https://arxiv.org/pdf/1604.05753.pdf

### A few additional remarks

- You mention that a mild drawback of the work of Chen et al. is that the bounds depend on manifold curvature which is unknown or hard to estimate. But in your JL-based results the covering number of the secant set will surely depend on similar parameters of the data domain. How would you reliably estimate covering numbers or Gaussian widths from data? 

- Your architecture first reduces dimension, a bit like an autoencoder, but standard architectures for inverse problems in imaging don't do that (one example is the U-Net). They first create many channels to expand dimensionality and then reduce it back to the image dimension. This demonstrably improves the expressivity. These architectures are very successful at addressing inverse problems, even at high resolutions. How does this fit your narrative? A related comment is that there are many situations where overparameterization is known to help (random kitchen sinks, most neural networks). In some cases we have theory. Again, it would be nice to hear how this combines with your narrative. Somehow I think that (admittedly vague) notions like inductive bias will deteriorate after compression.

- One thing that will certainly be problematic is that in many problems with convolutional structure a "good" architecture can opportunely leverage local information in the full-dimensional input (e.g., skip connections in the U-Net or the ResNet). A low-dimensional projection is likely to destroy this structure.

- I am slightly confused by the convolutional results (Theorem 3). Since there is no equivariance assumption on f, the output space of the network, R^p, should not be interpreted as an image? (assuming that we work with images). The result of Zhou, for example, seems to study a different model than the one used in inverse problems (where again in the case of images the channels and the output of a convolutional network like the U-net are image-like + equivariance plays an important role). Zhou as well as Oono & Suzuki seem to approximate a generic f \in C(Omega) and not leverage any image-related inductive bias of the domain or the range of f.

### Questions, suggestions, comments


- The covering numbers in Proposition 1 scale favorably when the set in question has some low dimensional structure (for example, it's an embedded manifold). It might be good to state this explicitly and write down some common scalings. Also, I assume there is a relation which such things as the box dimension and doubling constants.


- In compressive imaging the input to the reconstruction map is low dimensional to begin with and presumably cannot be compressed any further. Could you comment on the most natural classes of problems where your results apply?

- A philosophical comment: Your initial assumption is that the inverse operator is Lipschitz. I understand that you're looking at a problem which is already discretized, but many inverse operators in interesting inverse problems are not Lipschitz between function spaces on which they are usually defined. This is the case even for the Radon transform which smooths by half a derivative (in 2S) and thus has a Hölder inverse, though this can be "made Lipschitz" by changing norms. But in problems like electric impedance tomography, the inverse problem is only log stable for any reasonable norm (this is very bad). By the results of Bourgain and later others (e.g. Stefanov and Uhlman), once we go to finite dimension things do become Lipschitz but the Lipschitz constants will still reflect the fundamental instability of the continuous problem.


### A few misprints I caught


Introduction

- Nah et al. 2017 is a deblurring paper but it is cited in the context of low-does CT reconstruction; please double check all references

- Spurious ) after m < n in the second paragraph

- In paragraph 3, The inverse of the linear measurement map -> delete "inverse of the"

- Second sentence of paragraph 4: delete either alternatively or instead

Section 2: Related work

- The sentence starting with "Therefore, to study expressive power... " is broken 
- Last paragraph on p2: Guassian -> Gaussian


Section 3: Main results

- The sentence "Since our theory is to be applied..." is broken
- The title of 3.1 has two ands



clarity,_quality,_novelty_and_reproducibility: The paper is clearly written and easy to understand. (There are quite a few misprints and the prose could be streamlined, but that should be easy to fix.) As for originality, I have some doubts expressed in the previous box. The theme of rates that adapt to the intrinsic dimension of data is old and well-understood so I occasionally had the impression that the high-level idea is a bit oversold. My main objection is that I know of prior work that addresses the same problem and derives considerably more general results.
summary_of_the_review: This is a nice paper with a good, important idea, and a clear message. I think the presentation should include a careful comparison to earlier related results in the literature (some of which address the exact same problem and even make stronger statements). I very much appreciate the motivation via inverse problems but that also raises certain questions about inductive bias (arguably _the_ reason why the current architectures work so well across the board), and mangling this inductive bias by low-dimensional projections. But the bulk of the basis for my rating is the overlap of the result with the previous (more general) work of Kratsios and Papon, cited above. I think that the specific setting studied by the authors _is_ among the most interesting instances of this theory and warrants a specialized treatment, but I feel that this requires a substantial revision to properly reflect existing results.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this paper the authors answer why the size of a Lipschitz neural network in practice is much smaller than the theoretical bounds (which have an exponential in D dependence). The key idea that the authors provide is that number of parameters will vary exponential in the intrinsic dimension if there exists a matrix $A$ which projects a sample from higher dimension D to d, such that it also preserves the distance between the points. 

Therefore, if there exists a neural network with a given width, depth and parameters (epsilon-dependent) that can epsilon-approximate a Lipschitz d, then it can also approximate a function in D with only few extra parameters and layers.
strength_and_weaknesses: [Strengths]

The results provided in the paper are technically correct, and easy to follow and the proofs are well presented.

The authors also provide conditions under which it is reasonable for a JL to exist. 

The authors provide the estimates of size for solving some classical problems like sparse recovery and matrix completion. 

[Weakness]

The key contribution of the paper is dependent upon the existence of a JL-map $A$. However it is unclear if such a map can exist in natural domains for which neural networks are used. 

The proof techniques used to show epsilon-approximation in the intrinsic dimension, and the resulting size of the neural networks (in terms of depth, width and parameters) is very similar to previous works by Yarotsky (2018,2022) and indeed borrows a lot of details from the their proof. The key idea of the existence of a JL-Map $A$ does not seem like sufficiently novel.
clarity,_quality,_novelty_and_reproducibility: The paper is clear to follow, however seems to be lacking novelty in the key parts of the result.
summary_of_the_review: The techniques used to prove the main theorem seem to build heavily upon existing results, due to which I am currently leaning towards a weak-reject. I am open to having a discussion with the authors in this regard.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies how to approximate Lipschitz functions in high dimensions for signals with low-dimensional structures. By assuming the existence of a linear Johnson-Linderstrauss embedding on the signals, the appropriation bounds of Lipschitz functions based on neural networks are given. It allows for better explanation of the empirical success of deep learning models in inverse problems. 
strength_and_weaknesses: I think the main limitation of the theory is about that the model (y=F(x)) considered in this paper has no noise term, which is not very common in the literature of inverse problems. 
- If the results could be generalized to this case, the contribution would be stronger. It not, a discussion regarding this point is welcome in the conclusion.
- Do you have an estimation of the d in practice, so as to justify the theory is relevant to practice?
clarity,_quality,_novelty_and_reproducibility: The paper is well written and the results are well presented. 
summary_of_the_review: Revision: I tend to keep my score it is still not so clear how the results could be extended to noisy cases (without modifying Assumption 1). Also the application to inverse problems remain theoretical, therefore I think the impact of the paper is limited.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper shows representational bounds on expressing functions using a neural network, in the presence of "low dimensional" structure. Specifically, the assumption is the existence of a JL-like embedding: namely, a linear map to a lower-dimensional space, s.t. distances are approximately preserved, and the function in question is a composition with this linear map and a (Lipschitz) function. The reviewers thought that overall the paper is below the acceptance bar: from a purely technical point of view, the proof techniques are rather standard and expected; from a conceptual point of view, it's not clear what the paper teaches us about real trained neural networks (e.g. is it the case that such JL-like embeddings exist, and is this a significant causal factor in the design and success of neural architectures?) 
justification_for_why_not_higher_score: There was no substantive reason to accept the paper: the mathematical techniques on their own are fairly straightforward and standard; it was also unclear what conceptually the paper teaches us about architecture design or the success of neural networks.
Decision: Reject