Neural Network Approximation of Lipschitz Functions in High Dimensions with Applications to Inverse Problems
Authors: Santhosh Karnik
Rongrong Wang
Mark Iwen
Venue: Submitted to ICLR 2023 (2023)
Keywords: approximation theory
neural networks
deep learning
Johnson-Lindenstrauss embedding
inverse problems

Abstract: The remarkable successes of neural networks in a huge variety of inverse problems have fueled their adoption in disciplines ranging from medical imaging to seismic analysis over the past decade.  However, the high dimensionality of such inverse problems has simultaneously left current theory, which predicts that networks should scale exponentially in the dimension of the problem, unable to explain why the seemingly small networks used in these settings work as well as they do in practice. To reduce this gap between theory and practice, a general method for bounding the complexity required for a neural network to approximate a Lipschitz function on a high-dimensional set with a low-complexity structure is provided herein. The approach is based on the observation that the existence of a linear Johnson-Lindenstrauss embedding $\mathbf{A} \in \mathbb{R}^{d \times D}$ of a given high-dimensional set $\mathcal{S} \subset \mathbb{R}^D$ into a low dimensional cube $[-M,M]^d$ implies that for any Lipschitz function $f : \mathcal{S} \to \mathbb{R}^p$, there exists a Lipschitz function $g : [-M,M]^d \to \mathbb{R}^p$ such that $g(\mathbf{A}\mathbf{x}) = f(\mathbf{x})$ for all $\mathbf{x} \in \mathcal{S}$. Hence, if one has a neural network which approximates $g : [-M,M]^d \to \mathbb{R}^p$, then a layer can be added which implements the JL embedding $\mathbf{A}$ to obtain a neural network which approximates $f : \mathcal{S} \to \mathbb{R}^p$. By pairing JL embedding results along with results on approximation of Lipschitz functions by neural networks, one then obtains results which bound the complexity required for a neural network to approximate Lipschitz functions on high dimensional sets. The end result is a general theoretical framework which can then be used to better explain the observed empirical successes of smaller networks in a wider variety of inverse problems than current theory allows.

NEURAL NETWORK APPROXIMATION OF LIPSCHITZ FUNCTIONS IN HIGH DIMENSIONS WITH APPLICA- TIONS TO INVERSE PROBLEMS
Anonymous authors Paper under double-bling brind review
ABSTRACT
The remarkable successes of neural networks in huge variety of inverse prob- lems have fueled their adoption in disciplines ranging from medical imaging to seismic analysis over the past decade. However, the high dimensionality of such inverse problems has simultaneously left current theory, which predicts that net- works should scale exponentially in the dimension of the problem, unable plain why the seemingly small networks used in these settings work as well as they do in practice. To reduce this gap between theory and practice, general method for bounding the complexity required for a neural network to approximate Lipschitz function on high-dimennional set with a low-complexity structure is provided herein. The approach is based on the observation that the existence of a linear
embedding A E Rdx of a given high- nigh-dimensional set S C IR into low dimensional cube [-M, M1 implies that for any Lipschitz function f S - IR,, there exists a Lipschitz function
M,, .M IRP such that 9 (Ax)) = f(x) for all x E S. Hence, if one has neural network which approximates g [-M, MM + R", then layer can be added which implements R".
the JL embedding A obtain neural network which approximates By pairing JL. embedding results along with results on approximation of Lipschitz functions by neural networks, one then obtains results which bound the complexity required for a neural network to approximate Lipschitz functions on high dimen- sional sets. The end result general theoretical framework which can then be used to better explain the observed empirical successes of smaller networks in a wider variety of inverse problems than current theory allows.
INTRODUCTION
At present various network architectures (NN, CNN, ResNet) achieve state-of-the-art performance in broad range of inverse problems, including matrix completion (Zheng al., 2016; Monti al., 2017: Dziugaite& & Roy, 2015; He et al., 2017) image-deconvolution (Xu et al., 2014; Kupyn et al., 2018), low-dose CT-reconstiiutiion (Nah ef al., 2017), electric and magnetic inverse Problems (Coc- corese et al., 1994) (seismic analysis, electromagnetic scattering). However, since these problems are very high dimensional, classical universal approximation theory for such networks provides very pessimistic estimates of the network sizes required to learn such inverse maps (i.e., as being much larger than what standard computers can store, much less train). As result, gap still exists be- tween the widely observed successes of networks in practice and the network size bounds provided by current theory in many inverse problem applications. The purpose of this paper to provide refined bound on the size of networks in wide range of such applications and to show that the net- work size is indeed affordable in many inverse problem settings. In particular, the bound developed herein depends the model complexity of the domain of the forward map instead of the domain's 's extrinsic input dimension, and therefore is much smaller in a wide variety model settings.
To be more specific, recall in most inverse problems one aims recover some signal x from its measurement y = F(x). Here y and r could both be high dimensional vectors, or even matrices and tensors, and F, which is called the forward map/operator, could either be linear nonlinear with various regularity conditions depending on the application. In all cases, however, recovering x from y amounts to inverting F. In other words, aims want to find the operator F-1, that sends every

---

measurement y back to the original signal z. Depending on the specific application of interest, there are various commonly considered forms of the forward map F. For example, F could be a linear map from high to low dimensions as in compressive sensing applications; F could be convolution operator that computes the shifted local blurring of an image as in the image deblurring setting; F could be mask that filters out the unobserved entries of the data in the matrix completion application: or F' could also be the source-to-solution map of a differential equation as in ODE/PDE based inverse problems.
In most of these applications, the inverse operator F-1 does not possess a closed-form expression. As a result, order to approximate the inverse one commonly uses analytical approaches that in- volve solving, c.g., an optimization problem. Take the sparse recovery as an example. With the prior knowledge that the true signal x E RR is sparse, one can recover it from the under-determined measurements Rm e y Ar with < n.) by solving the optimization problem
④ = arg min ||=||u>
===y
The inverse of the linear measurement map F(x) =y= Ar when restricted to the low-complexity domain of sparse vectors has an inverse, F-1 (v), that is then the minimizer E above.
Note that traditional optimization-basse approaches could be extremely slow for large-scale prob- lems (e.g., for n large above). Alternatively, we can approximate the inverse operator by a neural network instead. Amortizing the initial cost of an expensive training stage, the network can later achieve unprecedented speed over time at the test stage leading to better total efficiency over its life- time. To realize this goal, however, we need to first find neural network architecture Se. and train it to approximate F-), so that the approximation error max, llfe(v) - F (y)ll = l[fe(y) x is small. The purpose of this paper to provide unified way to give meaningful estimation of the size of the network that one can use to set up the network in situations where the domain of F is low-complexity as is the case in, e.g., compressive sensing, low-rank matrix completion, deblurring with low-dimensional signal assumptions, etc..
2 RELATED WORK
The expressive power of neural networks is important in applications as means of both guiding network architecture design choices, as well as for providing confidence that good network solu- tions exist in general situations. As result, numerous results about the approximation power has been established in recent years (Zhou, 2020; Petersen & Voigtlaender, 2020; Yarotsky, 2022; 2018; Lin & Jegelka, 2018). Most results concern the approximation of functions on RRP. however, and yield network sizes that increase exponentially with the input dimension D. As a result, the high dimensionality of many inverse problems leads to bounds from most of the existing literature which are too large to explain the observed empirical success of neural approaches in such applications.
similar gigh-dimensional scaling issue arises in many image classification tasks as well. Motivated by this setting (Chen et al., 2019) refined previous approximation results for ReLU networks, and showed that input data that close to a low-dimensional manifold leads to network sizes that only grow exponentially with respect to the intrinsic dimension of the manifold. However, this improved bound relies on the data fitting manifold assumption which quite strong in the inverse problems setting. For example, even the "simple" sparse recovery problem does not have domain/range that forms a manifold (note that the intersections of s-dimensional subspaces prevent from it being a manifold). Therefore, to study expressive power of networks on inverse problems needs to remove such strict manifold assumptions. Another mild issue with such manifolds results is that the number of neurons also depends on the curvature of the manifold in question which be difficult to estimate. Furthermore, such curvature dependence is unavoidable for manifold results and needs to be incorporated into any valid bounds.!
In this paper, we provide another way to estimate the size of the network, by directly using the Guassian width of the data as a measure of its inherent complexity. Our result can therefore be
'To see why, e.g., curvature dependence is unavoidable, consider any discrete training dataset in a compact ball. There always exists I-dimensional manifold, namely curve, that goes through all the data points. Thus, the mere existence of the 1-dimensional manifold does not mean the data complexity is low. Curvature information and other manifold properties matter well!
2

---

considered generalization of the manifold result discussed above in two ways. First, it applies to more arbitrary data sets with low complexities. And, it also applies to other types of networks besides just feedforward ReLu networks. Both types of generalization are then shown to be useful and applicable to various inverse problems.
MAIN RESULTS
We begin by stating few definitions. We say that neural network e-approximates function if the function implemented by the neural network satisfies [ffx)) f(z)ll>> S for all æ in the domain of f. We say that neural network architecture c-approximates any function in a function class FF if for any function implemented by the neural network with that choice of edge weights satisfies [If(()) - f()))l S for all æ in the domain of f.
F, there exists choice of edge weights such that the function f
Also, for any positive integers matrix A E RdxD is a p-JL (Johnson- -ohnsonn-Linde Lindenstrauss) embedding of S if
D, any set S R., and any constant p (0. 1), we say that
p)| z'1l2 S || Ax Ax' 1|2 S (1 p)] æ'112 for all x, x If we furthermore have A(S) := {Ax : S) C T, we say that A is p-JL embedding of S into T. Intuitively, p-JL embedding S into IR transforms S from a high-dimensional space to low-dimensional space without significantly distorting distances between points.
Existing universal approximation theorems for various types of neural networks are mainly stated for functions defined on an d-dimensional cube. Our main contribution is to generalize these results to functions defined on arbitrary JL-embedable sets, which possibly reside in very high dimensions. We then demonstrate how our result can be applied inverse problems to obtain reasonable estimate of the network size.
Contributions:
Since our theory is to be applied to general inverse problems, for which we cannot assume anything more than Lipschitz continuous. Hence in this paper, we focus on the class of Lipschitz functions.
More explicitly, show that if there exists p-JL embedding of high-dimensional set S R into a low-dimensional cube [-M, M]], then we can use any neural network architecture which can e-approximate - -Liischit functions on [-M, Mjd to construct a neural network architecture which can e-approximate L-Lipschitz functions on S. To establish this, we show that if there exists p-JI. embedding A R of S C DRD into d-dimensions, then for any T--Lipschitz function f: + R", there exists a L Lipschitz function [-M, M) + R (where M supres ||Ax] (lx)) such that g (Ax) = [(x ) for all æ E S. Hence, if we have neural network which can approximate g : [-M, Mjd + TR, then we can compose with a neural network which implements the JI. embedding A to obtain neural network which approximates f S + R.. By pairing JL embedding existence results along with results on approximation of Lipschitz functions by neural networks, we obtain results which bound the complexity required for neural network to approximate Lipschitz functions on high dimensional sets.
1-p
We now state main theorem.
Theorem Let d D be positive integers, and let L, M > and E (0,1) be constants. Let S C DD be bounded subset for which there exists p-JL embedding A E gdxD of S into M,d.
a) Suppose that any + Lipschitz function g M|M, E. can be e-approximated by feedforward neural network with most N nodes, edges, and layers. Then, any L-Lipschitz function f S + R2 can be e-approximated by feedforward neural network with at most N D nodes, Dd edges, and
layers.
b) Furthermore, if there exists single feedforward neural network architecture with at most N nodes, edges, and layers that can e-approximate any - - function g [-M, M] + RP, then there also exists another feedforward neural network architecture with at most N + f S RR.
nodes, E+ Dd edges, and C+ layers that can c-approximate any L-Lipschirt,function
c) Suppose that the p-JL embedding is of the form A = MD, where M is a partial circulant matrix, and D is a diagonal matrix with +1 its diagonal. Also, suppose that any - ipsschit
3

---

f
small as possible while still ensuring that RD 3 S
R P
JL
g
[-M, M
Figure I: there exists a p-JL embedding of S C RD into -.MM then we can write the target function f S I2 f= go JL where g |-M, MI + RR. So, then construct neural network approximation of f by using a neural network approximation of and adding a layer to implement the JL embedding.
function g [-M, + IP can be e-approximated by a convolutional neural network with at most N nodes, ' parameters, and L layers. Then, any L-Lipschitz function f S - R can be c- approximated by feedforward neural network with at most N +3D nodes, P parameters, and C + 4 layers.
d) Furthermore, if there exists a single convolational neural network architecture with at most N nodes, ' parameters, and L luyers that can e-approximate any T-p -ipscchhtttzzz function [- M + RP, then there also exists another convolutional neural network architecture with most N 2D nodes, p + 2Dd parameters, and L 3 layers that e-approximate any L- foaschitz,uunctinn S RR.
Remark The theorem ensures that the network size for approximating grows exponentially with the compressed dimension dl instead of growing exponentially with the input dimension D. The task now reduces making the compressed dimension p-JL embedding of S into M-M, Mfd exists.
Remark 2. The theorem is quite general as parts and b are not restricted to any particular type of network or activation function. In Section 3.3, we provide two corollaries of Theorem that establish the expressive power of the feedforward and convolutional neural networks.
Remark 3. If an inverse operator is I. Lipschitz continuous and there exists a p-JI. embedding of the set of possible observations into d dimensions, then the theorem gives us bound on the complexity of neural network architecture required to approximate the inverse operator.
3.1 JL EMBEDDINGS, AND COVERING NUMBERS AND GAUSSTAN WIDTH
As the existence of the JL map is a critical assumption our theorem, in this section, we discuss the sufficient conditions for this assumption hold. In addition, also about the structures of the JL maps, as they will end up being the first layer of the final neural network. For example, the neural network of convolution type, we need make sure that a cireulant JL matrix exists.
Existence of p-JL maps: It is well-known that for finite sets S, the existence of a p-JL embedding be guaranteed by the Jchnson-Lindenstrenn Johnson-Lindenstrane lemma cannot be directly used. In the following proposition, we extend the Soanson-Lindenstrauss lemma from a finite set of points general set S.
Lemma. For sets with infinite cardinally, the
Proposition 1. Let p E (0, 1). For S C RD, define
2 x
Us =
x, x E s.t. x + x'
x x'122
be the closure of the set of unit secants of S, and (Us || 11, 5) to be the covering number of Us with 5-balls. Then, there exists a set S with S = 2N || |||1|,, 8) points such that if matrix A RdxDD is p-Jl. embedding of St, then A is also (o A| em.eeddinn S.

---

The proposition guarantees that whenever have JL- for finite sets, map for infinite sets with similar level of complexity measured in terms of the covering numbers. There are many known JL-maps for finite sets that we extend from, including sub-Gaussian matrix (Matoušek, 2008), Gaussian circulant matrices with random sign flip (Cheng & 7hangg 2014), etc. We present some of the related results here.
extend to
Proposition 2 (Matousek, 2008)). Let 2i....,2,, En R. Let p E (0. and 3 (0, Let A E RdxD be random matrix whose entries are ii..d. from subgaussian distribution with mean O and variance 1. Then, there exists a constant C > depending only on the subgaussian "log n. distribution such that if d 2 Cp-2 3 then Va A will be a p-JL embedding of (21...., .n. with probability at least - B.
Proposition 3 (Corollary 1.3 (Cheng Zhang, 2014)). Let 11,..... In RRD. Let p E (0. 1)) and let d = O(p log 1+a n.) for some a > O. Let A = MD where M E RdxD is random Gaussian circulant matrix and D E DD is a random Rademacher diagonal matrix. Then, with probability at least (1 (D + d)e log" "), A is p-JL embedding of "......;,p??
Note that the in the proposition can be set to be any positive number making the probability of failure less than 1.
Combining the results of Propositions 2 and 3 with Proposition 1, we have the following existence result for the JL map of an arbitrary set S,
Proposition Let p (0,1) be a constant. For S C RD, let N(Us, 1122,6) to be the covering number with 5-balls of the unit secant Us of S defined in Proposition 1. Then
). then there exists a matrix A R which is a p-JL a) If 2 d Z p Nog. ll2. AYDD). embedding S.
TV33 then there exists matrix A E RdxD in the form of MD and of size D that works as p-JL map for S, where M is partial circulant matrix and D is a diagonal matrix with +1 on its diagonal.
Df d Z p- log((D + 4d) log log.N 11
The above proposition characterizes the compressibility of a set S by a JL-mapping terms of the covering number. Alternatively, one can also characterize it using the Gaussian width. For example, in (Iwen et al., accepted. (See Arxiv 21 21.004193) it is shown using methods from (Vershynin, 2018) that if the set of unit secants of S has low Gaussian width, then with high probability subgaussian random matrix with provide a low- oow-distrtiio linear embedding, and the dimension d required scales quadratically with the Gaussian width of the set of unit secants S.
Proposition 5 (Corollary 2.1 in (lwen al., accepted. (See Arxiv 2110.04193)). Let p, (0, be constants. Let A E RdxD be matrix whose rows a.....,, at are independent, isotropic (Bla,a = I), and subgaussian random vectors. Let S C TRD,, and Let
(Uss) E
E sup (u, 2). ~ Normal(O.1) ueUs
to be the Gaussian width Us. Then, there exists constant C > 0 depending only on the distri- bution of the rows of A such that if
C (w(US) /log 3)) P
d
then t is p-JL embedding of S with probability least B.
In practice, one can use either the Gaussian width (Proposition 5) or the covering number (Proposi- tion to compute the lower bound of d. whichever more convenient for a specific application.
3.2 UNIVERSAL APPROXIMATOR NEURAL NETWORKS FOR LIPSCHITZ FUNCTIONS ON d-DIMENSIONAL. CUBES
In Theorem 1, we showed that with the help of JL, approximation rate of neural networks for functions defined arbitrary set S can be derived from their approximation rates for functions
5

---

defined the cube 1-M, M/4. In this section, review known results for the later, that they can be used in combination Theorem to provide useful approximation results for network appli- cations to various inverse problems. Specifically, for functions defined on the cube [-M, M] One is the Feedforward ReI.U network and the other is the Resnet type convolution neural network.
review two types of universal approximators
Feedforward ReLU network: The fully connected feedforward neural network with ReLU acti- vation is known to be a universal approximator of any Lipschitz function on the box [-M, Mj Moreover, for such networks, the -on-ssympootic approximation error has also been established, allowing us to get estimate of the network size. The proposition below is a variant of Proposition in (Yarotsky, 2018), and the proof uses an approximating function that uses the same ideas as in (Yarotsky, 2018).
Proposition 6. Given constants L, L,Me and positive integers and p. there exists a ReLU NN architecture with most
(p+C1) (2 LMvd + +1) edges, C2 (2 LMVd + +1) +p nodes, and [log2 + 1)]+2 layers
that can e-approximate any L-Lipschitz functtion g [-M, + R.. Here, C1, C2 > 0 are uni- versal constants. Also for each edge of the ReLU NN, the corresponding weight is either independent of g. or is of the form (x) for some fixed [-M, M) and coordinate i = 1,....P
Convolutional Neural Network: As many successful network applications on inverse problems results from the use of filters in the CNN architectures (Jin et al., 2017), we are particularly inter- ested in the expressive power of CNN in approximating the Lipschitz functions. Currently known non-asymptotic results for CNN includes (Zhou, 2020; Petersen & Voigtlaender, 2020; Yarotsky, 2022), but they are established under stricter assumptions than merely Lipschitz continuous. On the other hand, the ResNet-based CNN with the following architecture has been shown possess good convergence rate.
CNN = FCw,, (Conv war bM +id)
(Conv + P
where a the activation function, each Conv an convolution layer with Lm filters tii stored in wM and I. bias by....., ..., Jyhe stored bm- The addition by the identity map, Conv wx bbs + id, makes it a residual block. FCW.B represents a fully connected layer appended to the final layer of the network. We see that the ResNet-based CNN is essentially a normal CNN with skip connections.
w im
The following asymptotic result is proved in (Oono & Suzuki, 2019). We note that the authors of (Oono & Suzuki, 2019) proved more general result for 3-Hölder functions, but state it for Lipsehitz functions, i.e., 8 1.
Proposition 7 (Corollary 4 from (Oono & Suzuki, 2019)). Let Let [-1, R be a Lipschitz function. Then, for any K E {2.....), d), there exists a CNN f(CNN) with O(N) residual blocks, each of which has depth Olog N) and O(1) channels, and whose filter size is most K. such that Ilf - -IccN < ((N-//))
3.3
MAIN RESULTS
We can now combine Propositions 4 5, and with our Theorem obtain theorems bounding the required complexity of a seeed-forward/cooolluiioo neural network that can e-approximate any L-Lipschitz function on arbitrary sets S c R for which p-JL embedding into [-M, Mj exists.
Theorem 2. Let d < D be positive integers, and let L 0 and p E (0, 1) be constants. Let S R be a bounded set and Us be its set of unit secants. Suppose that
d z min {o log Nog.Nss.U Il. l12. ~/D), p p (w(Us)))
where NUUs; |l 11,, ( is the covering number and w(ss) is the Gaussian width Us. Then, there exists ReLU neural network architecture with at most
(p (p+C)) (i+
LMVA (1-p)= + +1) + Dd edges,

---

C2 (2
LMVa PT-pje
+1] +p+ D nodes,
and [ogg (d + 1)] 3 layers
that can e-approximate any L- Liiipchitttfuunttin S - IR,, where M = suPres ||
Our Theorem is a variant on our Theorem 2, but for convolutional neural networks.
Theorem 3. Let d < D be positive integers, and let L > 0 and E (0, 1) be constants. Let S C RD be a bounded set and Us be its set of unit secants. Suppose that
dZ log(4D + 4d) log ll2, av3D).
Then, for any L-Lipschitr, function f + RR, there exists a ResNet type CNN fICNM) in the form of (1) with (NN) residual blocks, each of which has depth Ollog N) and ((1) channels, and whose filter size is at most such that [|f -(CNN)) S O(N-1//).
4 APPLICATIONS TO INVERSE PROBLEMS
Now focus inverse problems and demonstrate how the main theorems can be used provide a reasonable estimate of the size of the neural networks needed to solve some classical inverse prob- lems signal processing. The problems we consider here are sparse recovery, blind deconvolution, and matrix completion.
In all the inverse problems, we want to recover some signal x S from its forward measurement F(r), where the forward map F is assumed to be known. The minimal assumption we have to impose on F is the invertibility.
Assumption (invertibility of the forward map): Let S be the domain of the forward map F, and F(S) be the range. Assume that the inverse operator F-1 : S exists and is Lipschitz continuous with constant L,
|| (v:) FF Dlly1
vell. for all V1, U2 E.
For any inverse problems satisfying Assumption 1, Theorem 1, and 3 provide ways to estimate the size of the universal approximator networks for the inverse map. When applying the theorems to each problem, need estimate the covering number of Uy first.
Depending on the problem, one may estimate the covering number either numerically or theoreti- cally. the domain y of the inverse map irregular and discrete, then may be casier to compute the covering number numerically. If the domain has a nice mathematical structure, then we may be able to estimate theoretically. Below are three examples of the theoretical estimation. From them, we see that it is quite common for inverse problems to have small intrinsic complexity, with which Theorems and 3 can significantly reduce the required size of the network from the previously known results.
We emphasize that the covering number that the theorems use the one of the unit secant of ) which can be much larger than the covering number of y itself.
Sparse recovery: Sparsity is now one of the most commonly used priors in inverse problems as signals in many real applications possess certain level sparsity in some appropriate domain. For simplicity, consider the strictly sparse signals. Let ΣN be the set of s-sparse vectors of length N. Assume a sparse vector is measured linearly y = Ar = F(x), the inverse problem amounts to recovering from y. Now that want to AΣ = y E + & E E.N. and estimate the size of the network through the theorems, we need to estimate the covering number of the unit secant U UAx.-
network to approximate the inverse map F-1
Proposition 8. Let UAzy denote the set of unit secants of AΣ Then, we have
N
log (U Any, 11 () S s log 8

---

Proof. By definition, the unit secant of ) = AA is defined as
Uy
11 1/2
M1 E A
|M 3/2
which contains all unit vectors that are linear combinations of 2s columns of A. Let with [T] 2s be a fixed support set, the covering number of span(Ar) n mmm1 is (g)²s, so the covering number of Uy is at most (g)²)
If the inverse of F exists, such in the case when A is Restricted-ssoment -eat--ss-mmmtmtoooeeeeee matrix, then by Theorem 2 and 3, there exist neural networks of fully connected type or of CNN type with O(c-+log number of weights, that can do the sparse recovery up to error of
Blind deconvolution: Blind deconvolution concerns the recovery of a signal x from its blurry mea- surements
A: @ x
(2)
when the kernel & is also unknown. Here & denotes the convolution operation.
Blindddeconvolution is an ill-posed problem due the existence of scaling ambiguity between a and k. namely, if (k, æ) is solution, then (ak: =) with a j 0 is also a solution. To resolve this issue, we focus on recovering the outer product zk", where I and k here are both columns vectors. The recovery of the outer product x from the convolution y in various settings (Lee et al., 2015; Ahmed et al., 2013). For example, (Ahmed et al., 2013) showed that if we assume x = 4u and & Vr, where & RN..(n < N) is i.i.d Gaussian matrix and V E (m. < N) is matrix of small coherence, then for large enough N, the outer-product rk can be stably recovered from y in the following sense. For any two signal-kernel pairs (x. k), (ž, Ie) and their corresponding convolutions y. D. we have
@ x can be well well-posed
(3) with some L. When using neural network to approximate the inverse map by F-1, y - zk need to estimate the covering number of the unit secant cone of y = {y = x & k. x E DΣN k E span }. which is done in the following proposition.
||ck" - .k < T - ūl
Proposition Suppose the inverse map F-1, y + xk is Lipschitz continuous with Lipschitz 2 k, E span()), k E spant)), the logarithm of the covering
constant L, then for y = {y number of the set of unit secants of y bounded by
3L
log lo || 1122, S max n log 5
Combining this proposition with Theorem 2 and 3, we obtain that there exist neural networks of full connected type of CNN type having about O max(mm log(4(n+m)) number of weights, that can solve the blinddeeconvolution problem up to an error of c.
Matrix completion: Matrix Completion is central task in machine learning where want to cover a matrix from its partially observed entries. It arises from a number of applications including image super resolution (Shi el al., 2013; Cao et al., 2014), image/video denoising (Ji et al., 2010), recommender systems (Zheng el al., 2016; Monti et al., 2017), and gene-expression prediction (Ka- pur et al., 2016), etc.. Recently neural network models have achieved state-of-the-art performance (Zheng et al., 2016; Monti et al., 2017; Dziugaite & Roy, 2015; He et al., 2017). but a general existence result in the non oonaypyptotiic regime is still missing.
In this setting, the measurements Y P consists of set of observed entries of the unknown low-rank matrix X, where 92 the index set of the observed entries and Pn is the mask that sets all but entries in Ω to O. Assuming M is the set of n X m matrices with rank at most r and X Mr. m, If the mask is random, and the left and right eigenvectors U, V of X are incoherent, in the sense that
|UTer S
NOT V n
JIV exll S V
Por m
max S
max ISism
((UVT) Daall S
P1T nvn
max 1sign.1si$m
8

---

then it is known (e.g. (Candes & Plan, 2010)) that provided that the number of observations
[ 2 por max(m, n log" max n).,
then with overwhelming probability, the inverse map F-1; : - exists and is Lipschitz continu- ous. Let us denote the set of low-rank matrices satisfying (4) be C. To estimate the complexity of the inverse map, we compute the covering number of Uy for ) = {Y PaX X E M.T." nc}. Proposition 10. Suppose the mask is chosen so that the inverse map F-1 Y PaX - X is Lipschitz continuous with Lipschitz constant L,, then for y [PaX X E MM nC), the logarithm of the covering number of the set of unit secants of y is bounded by
L ④
log log,N(U>, 11 11,, S r(m + log
Combining this proposition with Theorem 2 and 3, we obtain that there exist neural networks of full connected type or of CNN type having about O(c-r(m+m) log(Lam)) number of weights, that can solve the blind-deconvoluttinn problem up an error of
CONCLUSION AND DISCUSSION
The main message of this paper is that when neural networks are used to approximate Lipschitz continuous functions, the size of the network only needs to grow exponentially with respect to the intrinsic complexity of the input set measured using either the Gaussian width or the covering numbers. Therefore, it is more optimistic than the previous estimate that requires the size of the network to grow exponentially with respect to the input dimension.
Similar results were derived previously in (Chen et al., 2019) in a more restrictive setting, namely, the input set is assumed to be close to smooth manifold with small curvature, and the network type is restricted to the feedforward ReLU networks. In this paper, by utilizing the JL map, we able to state the result in very general setting, that does not pose any structural requirement on the inputs set other than that they have a small complexity. In addition, our result holds for many different types of networks although we only stated it for feedfoward neural networks and the ResNet type of convolutional neural networks, the same idea naturally applies to other types of networks as long as an associated JI.-map exists.
The estimate we provided for the network size ultimately depends on the complexity of the input set, measured by either the covering number or the Gaussian width of its set of unit secants. The computation of these quantities varies case by case, and in some cases might be rather difficult. This a possible limitation the proposed method. Because if the estimation of the input complexity is not tight enough, we may again get pessimistic bound. Having said that, for most of the classical inverse problems, the covering number and the Gaussian width are not too difficult to calculate. As demonstrated in Section 4, there are many known properties of them that one can use to facilitate the calculation. And when a training dataset given, one can even compute the covering number numerically with off-the-shelf algorithms.
Finally, although the applications of neural networks to inverse problems are seeing its success. There are much more failed attempts with unclear reasons. One common explanation is that the size of the network in use is not large enough for the targeted applications. Since inverse problems models usually have much higher intrinsic dimensionality than say image classification models, the required network sizes might also be much larger. The classical universal approximation theorems only guarantees small errors when the network size approaches infinity, therefore is not very helpful in the non-asymptotic regime where we have to choose the network size, which is now known to be critical to good performances. We hope the presented result can give more insight on this matter.
REFERENCES
Ahmed, Ali, Recht, Benjamin, & Romberg, Justin. 2013. Blind deconvolution using convex pro- gramming. IEEE Transactions on Information Theory, 60(3), 1-11-.
Arora, Raman, Basu, Amitabh, Mianjy, Poorya, & Mukherjee, Anirbit. 2016. Understanding deep neural networks with rectified linear units. arXiv preprint arXiv: 1.01411.

---

Azagra, Daniel, Le Gruyer, Erwan, & Mudarra, Carlos. 2021. Kirszbraun's theorem via explicit formula. Canadian Mathematical Bulletin, 64(1), 142-153.
Candes, Emmanuel J, & Plan, Yaniv. 2010. Matrix completion with noise. Proceedings of the IEEE, 98(6), 925-936.
Candes, Emmanuel J, & Plan, Yaniv. 2011. Tight oracle inequalities for low-rank matrix recov- ery from minimal number of noisy random measurements. IEEE Transactions on Information Theory, (7) 2342-2359.
Cao, Feilong, Cai, Miaomiao, & Tan, Yuanpeng. 2014. Image interpolation via low-rank matrix completion and recovery. IEEE Transactions on Circuits and Systems for Video Technology, 25(8), 1261-1270.
Chen, Minshuo, Jiang, Haoming, Liao, Wenjing, & Zhao, Tuo. 2019. Efficient approximation of deep relu networks for functions on low dimensional manifolds. Advances in neural information processing systems, 32.
Cheng, Lizhi, & Zhang, Hui. 2014. New bounds for circulant Johnson-LLnndessrruus embeddings. Communications Mathematical Sciences, 12(4), 695-705.
Coccorese, Enzo, Martone, Raffaele, & Morabito, F Carlo. 1994. A neural network approach for the solution of electric and magnetic inverse problems. IEEE transactions on magnetics, 30(5), 2829-2839.
Dziugaite, Gintare Karolina, & Roy, Daniel M. 2015, Neural network matrix factorization. arXiv preprint arXiv:1511.0644)
He, Xiangnan, Liao, Lizi, Zhang, Hanwang, Nie, Liqiang, Hu, Xia, & Chua, Tat-Seng. 2017. Neural collaborative filtering. Pages 173-182 of: Proceedings of the 26th international conference on world wide web.
Iwen, M.A., Schmidt, Benjamin, Tavakoli, Arman, accepted. (See Arxiv 2110.04193). On Fast Lindesn-Lindesssrauss Embeddings of Compact Submanifolds of IR with Boundary. Discrete & Computational Geometry.
Ji, Hui, Liu, Chaoqiang, Shen, Zuowei, & Xu, Yuhong. 2010. Robust video denoising using low rank matrix completion. Pages 1791-1798 of: 2010 IEEE Computer Society Conference Computer Vision and Pattern Recognition. IEEE.
Jin, Kyong Hwan, McCann, Michael T, Froustey, Emmanuel, & Unser, Michael. 2017. Deep convo- lutional neural network for inverse problems in imaging. IEEE Transactions on Image Processing, 26(9), 4522.
Kapur, Arnav, Marwah, Kshitij, & Alterovitz, Gil. 2016. Gene expression prediction using low-rank matrix completion. BMC bioinformatics, 17(1), 1-13.
Kupyn, Orest, Budzan, Volodymyr, Mykhailych, Mykola, Mishkin, Dmytro, & Matas, Jiff. 2018. Deblurgan: Blind motion deblurring using conditional adversarial networks. Pages 8183-8192 of: Proceedings of the IEEE conference on computer vision and pattern recognition.
Lee, Kiryung, Li, Yanjun, Junge, Marius, & Bresler, Yoram. 2015. Stability in blind deconvolu- tion of sparse signals and reconstruction by alternating minimization. Pages 158-162 of: 2015 International Conference on Sampling Theory and Applications (SampTAA). IEEE.
Lin, Hongzhou, & Jegelka, Stefanie. 2018. Resnet with one-neuron hidden layers is universal approximator. Advances in neural information processing systems, 31.
Matoušek, Jih 2008. On variants of the Johnson-Lindennstaaue lemma. Random Structures & Algorithms, 33(2), 142-156.
Monti, Federico, Bronstein, Michael, & Bresson, Xavier. 2017. Geometric matrix completion with recurrent multi-graph neural networks. Advances in neural information processing systems, 30.
10

---

Nah, Seungjun, Hyun Kim, Tae, & Mu Lee, Kyoung, 2017. Deep multi-scale convolutional neural network for dynamic scene deblurring. Pages 3883-3891 of: Proceedings of the IEEE conference computer vision and pattern recognition.
Oono, Kenta, Suzuki, Taiji. 2019. Approximation and non-parametric estimation of ResNet- type convolutional neural networks. Pages 4922-4931 of: International Conference on Machine Learning. PMLR.
Petersen, Philipp. & Voigtlaender, Felix. 2020. Equivalence of approximation by convolutional neu- ral networks and fully-connected networks. Proceedings of the American Mathemalical Society, 148(4), 1567-1581
Schwartz, Jacob T. 1969. Nonlinear functional analysis. Vol. 4. CRC Press.
Shi, Feng, Cheng. Jian, Wang. Li, Yap. New-Thian & Shen, Dinggang. 2013. Low-rank total
variation for image super-resolution. Pages 155-162 of: International Conference on Medical Image Computing and Computer-Assiste Intervention. Springer.
Vershynin, Roman. 2018. High-dimensional probability: An introduction with applications in data science. Vol. 47. Cambridge university press.
Wedin, Per-Ake. 1972. Perturbation bounds connection with singular value decomposition. BIT Numerical Mathematics, 12(1), 991111.
Xu, Li, Ren, Jimmy S, Liu, Ce, & Jia, Jiaya. 2014. Deep convolutional neural network for image deconvolution. Advances in neural information processing systems, 27.
Yarotsky, Dmitry. 2018. Optimal approximation of continuous functions by very deep ReLU net- works. Pages 639-649 of: Conference on learning theory. PMLR.
Yarotsky, Dmitry. 2022. Universal approximations invariant maps by neural networks. Construc- five Approximation, 55(1), 407-474.
Zheng, Yin, Tang, Bangsheng, Ding, Wenkui, & Zhou, Hanning. 2016. neural autoregressive approach to collaborative filtering. Pages 764-773 of: International Conference on Machine Learning. PMLR.
Zhou, Ding-Xuan. 2020. Universality of deep convolutional neural networks. Applied and compu- lational harmonic analysis, 48(2), 787-794.


Reviews:
[{"review_id": "z7o4fwOWesZ", "reviewer": "Reviewer_RMbx", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. ", "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. ", "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. \n- 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.\n- Do you have an estimation of the d in practice, so as to justify the theory is relevant to practice?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ZfpBiq2flO", "reviewer": "Reviewer_ZXNm", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. \n\nTherefore, 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.", "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.", "strength_and_weaknesses": "[Strengths]\n\nThe results provided in the paper are technically correct, and easy to follow and the proofs are well presented.\n\nThe authors also provide conditions under which it is reasonable for a JL to exist. \n\nThe authors provide the estimates of size for solving some classical problems like sparse recovery and matrix completion. \n\n[Weakness]\n\nThe 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. \n\nThe 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.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "W0bi9tly_B6", "reviewer": "Reviewer_Q6xo", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.\n", "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.\n", "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.\n\nIn 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.\n\nOn 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 \n\n``Universal Approximation Theorems for Differentiable Geometric Deep Learning'', JMLR, Anastasis Kratsios, Léonie Papon; 23(196):1−73, 2022.\n\nTo see this, set\n\n- $I = 1$ \n- $X = \\text{the subset S of}~\\mathbb{R}^D$\n- $Y = R^p$\n- $\\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\n\tnote that this map is injective and continuous (since it is bi-Lipschitz) whence it satisfies Assumption 7\n- $\\rho$ be the identity on R^p\n- Take the exponential maps to be about the origin; i.e.\n- Exp_{R^d,0}(u) = u +0 =u\n- Exp_{R^p,0}(u) = u +0 =u\n\nIn 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.\n\n\nThe present work is also closely related to\n\n- Deep Fried Convnets: https://openaccess.thecvf.com/content_iccv_2015/papers/Yang_Deep_Fried_Convnets_ICCV_2015_paper.pdf\n- NN approximation w/ random projections: https://core.ac.uk/download/pdf/153400703.pdf\n- The classic work on nonlinear learning with local coordinate coding: https://papers.nips.cc/paper/2009/file/2afe4567e1bf64d32a5527244d104cea-Paper.pdf\n- Direct inference on compressive measurements: https://ieeexplore.ieee.org/document/7532691\n- Sketching and neural networks: https://arxiv.org/pdf/1604.05753.pdf\n\n### A few additional remarks\n\n- 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? \n\n- 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.\n\n- 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.\n\n- 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.\n\n### Questions, suggestions, comments\n\n\n- 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.\n\n\n- 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?\n\n- 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.\n\n\n### A few misprints I caught\n\n\nIntroduction\n\n- 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\n\n- Spurious ) after m < n in the second paragraph\n\n- In paragraph 3, The inverse of the linear measurement map -> delete \"inverse of the\"\n\n- Second sentence of paragraph 4: delete either alternatively or instead\n\nSection 2: Related work\n\n- The sentence starting with \"Therefore, to study expressive power... \" is broken \n- Last paragraph on p2: Guassian -> Gaussian\n\n\nSection 3: Main results\n\n- The sentence \"Since our theory is to be applied...\" is broken\n- The title of 3.1 has two ands\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "3Qbc_FKNp3", "reviewer": "Reviewer_MC9E", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.\n", "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.\n\nUPDATE: After the response and the other reviews, it feels like many clarifications were not convincing and thus I decrease my score to 6.", "strength_and_weaknesses": "Strengths:\nUnderstanding 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. \n\nPrior 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.\n\nThe size of the network grows exponentially in $d$ rather than $D$, the input dimension and the results offer for tradeoffs in practice.\n\nWeakness/Clarifications:\nAre there any lower bounds known for the size of the networks? Could the authors comment on the tightness of the size of the networks.\n\nIt 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. \n\nIt 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.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject