A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing
Authors: Junren Chen
Jonathan Scarlett
Michael Ng
Zhaoqiang Liu
Venue: NeurIPS 2023 poster (2023)
Keywords: Compressed sensing
generative models
nonlinearity
uniform recovery

Abstract: In generative compressed sensing (GCS), we want to recover a signal $\mathbf{x^*}\in\mathbb{R}^n$ from $m$ measurements ($m\ll n$) using a generative prior $\mathbf{x^*}\in G(\mathbb{B}_2^k(r))$, where $G$ is typically an $L$-Lipschitz continuous generative model and $\mathbb{B}_2^k(r)$ represents the radius-$r$ $\ell_2$-ball in $\mathbb{R}^k$. Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $\mathbf{x^*}$ rather than for all $\mathbf{x^*}$ simultaneously. In this paper, we build a unified framework to derive uniform recovery guarantees for nonlinear GCS where the observation model is nonlinear and possibly discontinuous or unknown. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index model as canonical examples. Specifically, using a single   realization of the sensing ensemble and generalized Lasso,   all $\mathbf{x^*}\in G(\mathbb{B}_2^k(r))$ can be recovered up to an $\ell_2$-error at most $\epsilon$ using roughly $\tilde{O}({k}/{\epsilon^2})$ samples, with omitted logarithmic factors typically being dominated by $\log L$.  Notably, this almost coincides with existing non-uniform guarantees up to logarithmic factors, hence the uniformity costs very little.    As part of our technical contributions, we introduce Lipschitz approximation to handle discontinuous observation models.    We also develop a concentration inequality  that produces tighter bound for product process whose index sets have low metric entropy.  Experimental results are presented to corroborate our theory.

A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing
Junren Chen"
Jonathan Scarlett National University of Singapore scarlett@comp. nus. edu. sg
University of Hong Kong chenjr588conmect. hku .kk
Michael K. Ng
Zhaoqiang Liu" UESTC zqliu128gmail.com com
Hong Kong Baptist University mi michael -ngghku. edu. .k
Abstract
In generative compressed sensing (GCS), we want to recover signal xx R from measurements (m < n) using generative prior x= E G where G is typically an L-Lipschitz continuous generative model and B (r) represents the radius-r f2-ball in R* Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for fixed x=* rather than for all x" simultancously. In this paper, we build a unified framework to derive uniform recovery guarantees for nonlinear GCS where the observation model is nonlinear and possibly discontinuous or unknown. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models canonical examples. Specifically, using a single realization of the sensing ensemble and generalized Lasso, all x= e G(B) (r)) can be recovered up to fg-error most using roughly (kk/<2) samples, with omitted logarithmic factors typically being dominated by log L. Notably, this almost coincides with existing non-uniform guarantees up to logarithmic factors, hence the uniformity costs very little, As part of our technical contributions, we introduce the Lipschitz approximation to handle discontinuous observation models. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy. Experimental results are presented to corroborate our theory.
Introduction
In compressed sensing (CS) that concerns the reconstruction of low-complexity signals (typically sparse signals) [5 6 it is standard to employ random measurement ensemble, i.c., random sensing matrix and other randomness that produces the observations. Thus, recovery guarantee involving a single draw of the measurement ensemble could be non-uniform or uniform the non- uniform one ensures the accurate recovery of any fixed signal with high probability, while the uniform one states that one realization of the measurements works simultaneously for all structured signals of interest. Uniformity is highly desired property in CS, since in applications the measurement ensemble is typically fixed and should work for signals (17]. Besides, the derivation of uniform guarantee is often significantly harder than a non-uniform one, making uniformity an interesting theoretical problem its own right.
"Corresponding authors.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Inspired by the tremendous success of deep generative models in different applications, it was recently proposed to use a generative prior to replace the commonly used sparse prior CS (2). which led to numerical success such significant reduction of the measurement number. This new perspective for CS, which we call generative compressed sensing (GCS), has attracted a large volume of research interest, e.g., nonlinear GCS (29 33 45), MRI applications 46), and information- -hhoorttticcccc bounds (27,34), among others. This paper focuses on the uniform recovery problem for nonlinear GCS, which is formally stated below. Our main goal is to build a unified framework that can produce uniform recovery guarantees for various nonlinear measurement models.
Problem: Let (r) be the fz-ball with radius in R Suppose that G (r) + R" is an L-Lipschitz continuous generative model, a1,..., am E R" are the sensing vectors, x E K := (r) is the underlying signal, and we have the observations = fi(a, x²), i == L..... m, where fi())...,,
are possibly unknown possibly random non-linearities. Given a single realization of {a,, fi under what conditions we can uniformly recover all xx E KC from the corresponding {a; Vi Ji up to an fz-norm error of E??
1.1
Related Work
We divide the related works into nonlinear CS (based on traditional structures like sparsity) and nonlinear GCS,
Nonlinear CS: Beyond the standard linear CS model where one observes yi a, x", recent years have witnessed rapidly increasing literature on nonlinear CS. An important nonlinear CS model is 1-bit CS that only retains the sign y = sign(a xx) 22 41 42 Subsequent works also considered 1-bit CS with dithering y; = sign(a; x= + T;) achieve norm reconstruction under sub-Gaussian sensing vectors 1
48). Besides, the benefit of using dithering was found in uniformly quantized
CS with observation V/
8(1i + 2) is the uniform quantizer with Moreover, the authors of [16 43 44 studied the more general single index
Qs x=* + Tz), where (.(-)
8
resolution 6
8
48 52
model (SIM) where the observation y = fa x=) involves (possibly) unknown nonlinearity fi-
While the restricted isometry property (RIP) of the sensing matrix A = [a1,... am] ]m leads to uniform recovery in linear CS
[4]15] 49]. this is not true in nonlinear CS. In fact, many existing results are non-
uniform [9 16 41 44 48), and some uniform guarantees can be found in 7 8
Most of these uniform guarantees suffer from a slower error rate.
The most relevant work to this paper is the recent work [17] that described a unified approach to uniform signal recovery for nonlinear CS. The authors of [17] showed that in the aforementioned models with k-sparse x= uniform f2-norm recovery error of could be achieved via generalized Lasso using roughly k/e" measurements [17 Section 4]. In this work, we build unified framework for uniform signal recovery in nonlinear GCS. To achieve a uniform f--norm error of in the above models with the generative prior xx E G(B (r)). our framework only requires a number of samples proportional to k/e². Unlike (17) that used the technical results (36) to bound the product process, we develop a concentration inequality that produces a tighter bound in the setting of generative prior, thus allowing us derive sharper uniform eтror rate.
Nonlinear GCS: Building on the seminal work by Bora et al. (2). numerous works have investigated
linear or nonlinear GCS [1 19 20 23 25 30 39 41]5 with a recent survey (47) providing
a comprehensive overview. Particularly for nonlinear GCS, 1-bit CS with generative models has
been studied in (1 and generative priors have been used for SIM in 29 32 33 In addition, score-based generative models have been applied to nonlinear CS in [0
The majority of research for nonlinear GCS focuses on non-uniform recovery, with only a few exceptions [33
[33145] 45 Specifically, under a generative prior, (33] Section 5] presented uniform recovery
sign(x). Their proof technique is based on the local embedding property developed in [31 which is a geometric property that is often
guarantees for SIM where ys = [a x=)) with deterministic Lipschitz fa or f((x)
and currently only known for 1-bit measurements
and deterministic Lipschitz link functions. In contrast, our proof technique does not rely on such
In order to establish a unified framework, our recovery method 2.1 involves a parameter '' that should be chosen according to ft. For the specific single index model with possibly unknown fr. we can follow prior works 33 43 to assume that T'=" E K, and recover xx without using T'. See Remark for more details.

---

geometric properties and yields a unified framework with more generality. Furthermore, 33 did not consider dithering, which limits their ability to estimate the norm of the signal.
The authors of [45) derived a uniform guarantee from dithered 1-bit measurements under bias-free ReLU neural network generative models, while we obtain uniform guarantee with the comparable rate for more general Lipschitz generative models, Additionally, their recovery program differs from the generalized Lasso approach (cf. Section 2.1) used in our work. Specifically, they minimize an &g loss with ||> [2 as the quadratic term, while generalized Lasso uses || A ll that depends on the sensing vector. As result, our approach can be readily generalized to sensing vectors with an unknown covariance matrix (33] Section 4.2], unlike [45 that is restricted to isotropic sensing vectors. Under random dithering, while (45) only considered 1-bit measurements, we also present new results for uniformly quantized measurements (also referred to as multi-bir bit quantizer in some
works 13
1.2 Contributions
In this paper, we build a unified framework for uniform signal recovery in nonlinear GCS. We summarize the paper structure and our main contributions as follows:
We present Theorem D as our main result in Section 2 Under rather general observation models that can be discontinuous or unknown, Theorem] 1 states that the uniform recovery of all
x:* ( (r)) up to an f2-norm error of can be achieved using roughly O klogL) samples. Specifically, we obtain uniform recovery guarantees for 1-bit GCS, 1-bit GCS with dithering, Lipschite-contimuous SIM, and uniformly quantized GCS with dithering.
We provide proof sketch in Section 3 Without using the embedding property as in (33] we handle the discontinuous observation model by constructing a Lipschitz approximation. Compared to [1]]. we develop new concentration inequality (Theorem (2 to derive tighter
bounds for the product processes arising in the proof.
We also perform proof-of-concept experiments on the MNIST (28 and CelebA (35 datasets for various nonlinear models to demonstrate that by using a single realization of fe we can obtain reasonably accurate reconstruction for multiple signals. Due to the page limit, the experimental
results and detailed proofs are provided in the supplementary material.
1.3 Notation
We use boldface letters to denote vectors and matrices, while regular letters are used for scalars. For
a vector æ, we let || (1 S q S oc) denote its norm. We use B (r) := {2 R || S r} to denote the l, ball in I"," and (B (r))) represents its complement. The unit Euclidean sphere is denoted by Sn-1 ;= {x E I"" ||0||| = 1}. We use C, C2 C, to denote absolute constants whose values may differ from line to line. We write A O(B) or A S B (resp. A = B)B or A Z B) if A S CB for some C (resp. A 2 cB for some c). We write A x B if = O(B) and A = (2BB) simultaneously hold. We sometimes use Ô(-) to further hide logarithmic factors, where the hidden factors typically dominated by log L. in GCS, or log n in CS. We let ((,,, E) be the Gaussian distribution with mean and covariance matrix E. Given K1, C R", " a E R" and some a E I,, we define K2 + K2² == {01 22 I1 K1, 22 E K2). + K1 = {a} + K1, and aK1 = {ax: : E K. We also adopt the conventions of aAb = min(a, b). and avb = max(a, 6}.
2 Main Results
We first give some preliminaries.
Definition 1. For random variable X, we define the sub-Gaussian norm || 11, := inf > 0 E exp(X' /t?) < 2} and the sub-exponential norm [| 1l := inf > 0 E exp((xX/t) S 2). X
sub- Gaussian (resp. sub-exponential) if || < co (resp. [ s < co). For a random vector
R.,, we let || == sup ||0" T fl
Definition 2. Let be a subset of We say that subset So C S is an r--net of S if every point in S is at most 1) distance away from some point in So, i.e. S C So + BB(r) Given radius
3

---

define the covering number (SS,)) 1)) as the minimal cardinality of an n-net of S. The metric entropy of S with respect to radius 17 is defined as (H.)) log 1og.N(S,,)
2.1 Problem Setup
We make the following assumptions on the observation model.
Assumption 1. Let a ~ NO, In) and let be a possibly unknown, possibly random non-linearity that is independent of a. Let (a+ fs) be i.i.d. copies of (a, With single draw of (a,; Si) for x= E = G (r)). where G BB) - R= is an L-Lipschitz generative model, we observe {us = x1)] i=1 We can express the model more compactly as y f(Ax"), where A = [a,,... am] E Rmxn f fm).") and y (y/,,.., Vm.)
IR
In this work, we consider the generalized Lasso as the recovery method 16 43 to ignore the non-linearity and minimize the regular &g loss. In addition, we need to specify a constraint that reflects the cww-ooplexityy nature of x*, and specifically, dependent scaling factor T R and use the constraint "x TK"". Note that this is necessary even if the problem is linear, for example, with observations y 2Ax** one needs to minimize the lz loss over "x E 2K" Also, when the generative prior is given by Tx E K = (rB) we should simply use "x: K." constraint; this is technically equivalent the treatment adopted in 33 (see more discussions Remark beloww. Taken collectively. we consider
whose core idea
introduce problem-
a = arg min 11y
-Ax 12-
(2.1)
#ETK:
Importantly, we want to achieve uniform recovery of all x" E K. with single realization of (A,
2.2 Assumptions
Let f be the function that characterizes our nonlinear measurements. We introduce several assump- tions on here, and then verify them for specific models in Section 2.3 We define the set of discontinuities as
9 (a E : is discontinuous at a}.
We define the notion of jump discontinuity as follows.
Definition (Jump discontinuity). A function f R + RR has a jump discontinuity at xo if both L- = lim y 2-26 ((x) and L+ := lim Zin ((x exist but L + Lt. We simply call the oscillation at Tp. Le., [L L- the jump.
Roughly put, our framework applies to piece-wis Lipschitz continuous fi with (at most) countably infinite jump discontinuities, which have bounded jumps and are well separated. The precise statement given below.
Assumption 2. For some (Bo, Lo, 30), the following statement unconditionaaly holds true for any realization of J (specifically, SI,..., I'm in our observations):
2 is one of the following: Ø, a finite set, or a countably infinite set;
All discontinuities of J (if any) are jump discontinuttees with the jump bounded by Bo:
Lipiischhitz on any interval (a, b) satisfying (a, b) 9 2.
la - bl 2 So holds for any a, b E 2y, + b (we set Bo = 20 1
For simplicity, we assume f(x)) = lim (xx for Jn E 2
We note that Assumption is satisfied by T.-Lipschitz f with (Ba, Lo- 30) = (0, I, 20), bit quantized observation ) sign(- + 7) (T is the potential dither, similarly below) with
(By Lu. 30) = (2, 0, oo), and uniformly quantized observation f(-) 8(1 (1 + 2) with (Bo. Ln, 3o) = (Ó, 0, 8).
'This is very mild because the observations are fa(a? x), while P(a" x E 2,,) = 0 (as B,, is at most countably infinite and (0, In)).

---

An) Under Asssumption 2 for any 5 E [0, 2 we construct fi.9 as the Lipschitz approximation of fi deal with the potential discontinuity of (i.e., 9, * Ø). Specifically, fú,s modifies f. in f + 1-2 B 91 to be piece-wise linear and Lipschitz continuous; see its precise definition (3.4).
2
We develop Theorem to bound certain product processes appearing in the analysis, which produces bounds tighter than (36] when the index sets have low metric entropy. To make Theorem Maamaaapppiii applicable, we further make the following Assumption 3 which can be checked case-by-case by estimating the
sub-Gaussian norm and probability tail. Also, U and U2 can even be a bit crude because the measurement number in Theorem ( depends on them in a logarithmic manner.
Assumption 3. Let a ~ (O, In), under Assumptions fig in 3.4 We let
2 we define the Lipschitz approximation
(a) fú,((a) Ta, EI, f(.((a) f((a).
(2.2)
For all 3 E (0, do we assume the following holds with some parameters (A U/ p( and (A U )((2))
suPzek I m)ll< A PP (supaex KE Ta x)) S U 2 1 p(u)
supzek || 1) < A P (Suupeek (a (TTx) x) S U 2 - p(2)
To build a more complete theory we further introduce two useful quantities. For some x KC we define the target mismatch p(x:) as in 17 Definition 1]:
p x
[[ x)a. - Txxl2
(2.3)
It is easy to see that F. [ a)) minimizes the expected &g loss [ Ax:12] thus one can roughly understand EE [i x)a, as the expectation of & Since Txe is the desired ground truth, small p(z) is intuitively an important ingredient for generalized Lasso to succeed. Fortunately, in many models, p(x) with a suitably chosen T will vanish (e-g.. linear model (2), single index model 33 1-bit model (31) or at least be sufficiently small (e.g., 1-bit model with dithering (45)
As mentioned before, our method deal with discontinuity ft is introduce its approximation Si,s, which differs from Js only in Ø/ 1- G. This will produce some bias because the actual observation fa x²) rather than fa xx)). 1. Hence, for some x E we define the following quantity to measure the bias induced by ft.g:
[ 2.222
3 2. ~ N(O,
(a)))) = P a x 24
(2.4)
The following assumption can often be satisfied by choosing suitable 7 and sufficiently small $1-
Assumption Suppose Assumptions ! hold true with parameters Bu, La, Bo, A AA For the T used in (2.1) 1 p(æ) defined in (2.3) salisfies
sup p(x) S v Øek
(2.5)
m
Moreover, there exists some
B1
<
3a
such that 2
k
(LoB1 + Bo) sup aek
US, (x) ( V (2) >
(2.6)
In the proof, the estimation error || - Tx is contributed by a concentration term of scaling Ō((A))) v A(²)) /K/m) and some bias terms. The main aim of Assumption 4 is to pull down the bias terms so that the concentration term dominant.
2.3 Main Theorem and its Implications
We now present our general theorem and apply it to some specific models.
5

---

Theorem 1. Under Assumptions 7 given any recovery accuracy E (0.1), if it holds that m Z (A
22 (1) V Ag 2 then with probability at least m(Po + + m cxp(-9(nn) C' C'exp(-(((k)) on single realization of (A. := (a;; fi) we have the uniform signal recovery guarantee - Tx I for all x² E K. where & is the solution to (2.1) with y = f(A²)) and and other parameters that
L = log P is a logarithmic factor with P being polynomial in (I, n) (I,n) rypically scale as O + n). See (C.17) for the precise expression of L.
To illustrate the power of Theorem] 1 we specialize it to several models to obtain concrete uniform signal recovery results. Starting with Theorem T the remaining work is select parameters that justify Assumptions 2 We summarize the strategy as follows: (i) Determine the parameters in Assumption 2 by the measurement model; (ii) Set T that verifies (2.5) (see Lemmas
| for the following models); (iii) Set the parameters in Assumption 3 for which bounding the norm of Gaussian vector is useful; (iv) Set 31 to guarantee (2.6) based on some standard probability argument. We only provide suitable parameters for the following concrete models due to space limit, while leaving more details to Appendix E
(A) 1-bit GCS. Assume that we have the 1-bit observations = sign(a, x then fi(') = f()-
sign(.) satisfies Assumption 2 with (Bo, La, Bo) (2, 0, 20). In this model, it is hopeless to recover the norm of ||==||2; as done in previous work, we assume x E K C S (31 Remark
1]. We set 7 12/m and take the parameters in Assumption as Ag 1, Ug Vn, pO" x
exp(-s(nn)) Ag x 1, (2) x 1, P(2) = O. We take 5 = 31 x le U
to guarantee 2.6 With these
choices, Theorem | speciallizes the following:
Corollary 1. Consider Assumption 7 with f((-) sign(.) and K. c S let c (0.1) be any given recovery accuracy. If m Z 2/2 log
then with probability at least 1 - 2m exp(-cn)
(n(k/mm))
mexp(- on a single draw of (a.) we have the uniform signal recovery guarantee a
V lla S 6 for all x=* E K. where the solution to 2.19 with y = sign( (An) and =
Remark 1. A uniform recovery guarantee for generalized Lasso in 1-bit GCS was obtained in 133
Section 5]. Their proof relies on the local embedding property in (37j. Note that such geometric property is often
dependent and highly nontrivial. By contrast, our argument is free of geometric properties of this kind.
Remark 2. For traditional 1-bit CS. 11 Corollary 2] requires m 2 =Okefet) to achieve uniform
l2-accuracy of 6. for all k-sparse signals, which is inferior to our (kk/2). This is true for all remaining examples. To obtain such sharper rate, the key technique is to use our Theorem 2 (rather
than (36)) to obtain tighter bound for the product processes, will be discussed in Remark 8
rid (B) 1-bit GCS with dithering. Assume that the a, xx is quantized to 1-bit with dither &|->, A\) for some À to be chosen, i.e., we observe y = sign(a, xx + T.). Following [45] we assume IC C BB( (R) for some R > 0. Here, using dithering allows the recovery of signal norm 122 so we do not need to assume K. C g--1 as in Corollary| [ We set x = CRR/log m with
T
sufficiently large C. and T = A-1 In Assumption 3 we take Ag" (1) 1, U x /n, pf()) x
exp( (m)). Af² () x 1, 22 x 1, and p!2) = O. Moreover, we take B = B1 = Ak to guarantee
(.6 Now we can invoke Theorem to to get the following.
Corollary 2. Consider Assumption I with f((-) = sign(- + Ti), ~ 1- A1 and K. c IB (R), and \ = CRRlog m with sufficiently large C. Let e E (0, be any given recovery accuracy. If Lr/mi
m 2 2/ log ((EA(k/m)) ). then with probability at least 1 2m exp(-en) m mmxp(--((k)) on
single draw of (ai, Ti) Ti) we have the uniform signal recovery guarantee || - || S é ffor
all x== K, where & is the solution to 2.1 with y sign( Ax" + +T) (here, T [TI, [T,,... .... Tm] ) and T --11
Remark 3. To our knowledge, the only related prior result is in [45 Theorem 3.2). However, their result is restricted to ReLU networks. By contrast, we deal with the more general Lipschitz generative models; by specializing our result to the ReLU network that is typically (n ((d)) >-Lischittz (2) (d
4 'Here and in other similar statements, we implicitly assume a large enough implicd constant. Throughout this work, the random dither independent of the {a.

---

the number of layers), our enorr rate coincides with theirs up to logaritumic factor. Additionally, as already mentioned in the Introduction Section, our result can be generalized a sensing vector with an unknown covariance matrix, unlike theirs which is restricted to isotropic sensing vectors. The advantage of their result is in allowing sub-exponential sensing vectors.
(C) Lipschitz-continuuus SIM with generative prior. Assume that any realization of f is uncon- ditionally I-LLipschitz, which implies Assumption 2 with (Bo, Io, = (0, oo). We further assume (ff((0) < B) 2 1 - Py for some (B, P)). Because the norm of x is absorbed into the unknown f()). we assume K C Sa-1 We set 3 == so that fi. = ft. We introduce the quantities where 9 ~ (O, 1). We choose T = and set parameters in Assumption 3 as Ag x v + p, Uf x + +L++)) + B, p(l) x P/ + exp(-2(n)), Ag x
= [g + llf(g)
* p4, Ug 0, p(²2) O. Now we are ready to apply Theorem t this model. We obtain:
Corollary 3. Consider Assumption with L-Lipschitz f, suppose that ((f(0) B) 1 Po and define the parameters = Ef ggg... 1 = llf with g ~ N( 1). Let c E (0, be any given recovery accuracy. If m 2
(++ log (omymbbaattt(((t)+//// 2²
then with probability at least 1 2mm2mmmm exp(-cn) - mí c1 exp( (k()) on a single draw of (a,, fa) we have the uniform signal recovery guarantee || μax |l2 S for all x² E E,K, where a is the solution to 2.7 with y = [(Ax)) and T μ..
(utv)r
Remark 4. While the main result of (33) is non-uniform, it was noted in 133 Section 5] that similar uniform ervor rate can be established for any deterministic 1-Lipschitz J. Our result here is
more general that the L-Lipschitz J is possibly random. Note that randomness on f is significant because it provides much more flexibility (e.g,, additive random noise).
Remark 5. For SIM with unknown fo it may seem impractical to use (2.7) as it requires p = (g) where g ~ (0, 1). However, by assuming pac K G(BB)r) as in (33), which is natural for sufficiently expressive G(.), we can simply use x: E K. as constraint in 2. Our Corollary 3 remains valid in this case under some inessential changes of log μ factors in the sample complexity:
(D) Uniformly quantized GCS with dithering. The uniform quantizer with resolution 8 > is defined (s(a) ( }) for RR. Using dithering Tę ~ V/ [- 8 -.. suppose that the 2
observations are ys = (a x= + T:). This satisfies Assumption 2 with (Bu, Lo, So) = (5, 0, 8). We set T = 1 and take parameters for Assumption 3 as follows: A.") .. A! UU! x 5, and
pb") = 2 O. We take 3 = 31 x to confirm (.6 With these parameters, we obtain the following from Theorem 0
T T), resolution 8 > O. Let > 0 be any given recovery accuracy. If m 2 8% log (m then with probability at least 1 - 2m exp(-cn) - c1 exk(-S(kk) on a single draw of (a,, T.) we have the uniform recovery guarantee | x=" ||2 S for all x² K., where å is the solution 2.. with y = 2A(Ax + T) and T 1 (here,
Corollary 4. Consider Assumption
1 with s() = 2x( + T),
11 1. 41 for some quantization /rymmn
[TI.....
_mm]T), :mm]'....m]]
Remark 6. While this dithered uniform quantized model has been widely studied in traditional CS (e.g., non-uniform recovery {8 48), uniform recovery 117 (2)), it has not been investigated in GCS
even for non-unjje uni-unfform recovery. Thus, this is new to the best of our knowledge.
A simple extension to the noisy model y = fAxx) + n where 17 E Rm has i.i.d lub-Gaussian entries can be obtained by fairly straightforward extension of our analysis; see Appendix F
3 Proof Sketch
To provide sketch of our proof, begin with the optimality condition |/g (Tx**) We expand the square and plug in y = f(Ax*) to obtain
A < lly
A
2
2 (f(Ax)) TAx" A(# Tx²)).
(
Tx*)
<
(3.1)
vm
2
m
For the final goal || - Tox 1l2
S 6, up to rescaling, it is enough to prove || Ta S 3e. | Tx > 2e, without loss of generality. Combined with
We assume for convenience that
7

---

ē. Tx" E TK, we know ã - -Tx" E K, where K; = (TK ) (B)(2))) K- = -K-Ko K. We further define
(3.2)
where the normalized error lives, i.e. lower bound (resp., upper bound) for the left-hand side (resp., the right-hand side) of (3. We
8-TF" 1 E (K.)). Our strategy is to establish a uniform
emphasize that these bounds must hold uniformly for all x" E K.
It is relatively easy to use set-restricted eigenvalue condition (S-REC) (2) to establish a uniform lower bound for the left-hand side of (3.1), see Appendix B. for more details. It is significantly more challenging to derive an upper bound for the right-hand side of (3.1). As the upper bound must hold
uniformly for all x², we first take the supremum over x and & and consider bounding the following:
L
(f(Ax*) TAx A( Tx*))
m
(Jila) x²) -Ta, x²)) (a, [ -Tx*')
(3.3)
< _ Tx
sup sup
(fi(a, 2) Ta: x)) (a. v) = 1 Tx"" i=1
1|2 L...
#E (E(K))
where (K=)** is defined in (32)). Clearly, R. is the supremum of a product process, whose factors are indexed by x E K and )". It is, general, challenging to control a product process. and existing results often require both factors to satisfy certain "sub-Gaussian increments" condition (e.g.. [36 37). However, the first factor of R, (i.e., fi xx) Ta, x²) does not admit such a condition when fi is not continuous (e.g., the 1-bit model f; = sign(-)) (-). We will construct the Lipschitz approximation of fs to overcome this difficulty shortly Section 3.1
Remark 7. We note that these challenges stem from our pursuit of uniform recovery. In fact, a non-uniform guarantee for SIM was presented in [33 Theorem 1]. In its proof. the key ingredient is 33 Lemma 3) that bounds Bn without the supremam on x. This can be done as long as fc(a, x*) -aussiann, while the potential discontimuity of is totally unproblematic.
3.1 Lipschitz Approximation
For any E Dy. we define the one-sided limits as f (xo) = lim fi(x) and (+o) lim,-xnj --20 f((x), and write their average as (mo) = [ (ro) + (zo)). Given any approximation
accuracy B E (0, Bo we construct the Lipschitz continuous function ʃí,3 as:
f((x)
i & 9,, + + 0 if amo 2t, s.t. [mo 2 xol
ft,s(z) (xo) (m)) fi(m0 ())(000)))
(3.4)
B
(#0) + 2Ifi(zo+ 4) (zo))(=-
if Emp E 2/, s.t. x E [20, xo + +
B
We have defined the approximation error (. fi, - f(() in Assumption 3 An important observation is that both fú, and |Es,e] are Lipschitz continuous (see Lemma below). Here, is crucial to consider |s,,al rather than 6x,s the latter is not continuous; see Figure for an intuitive graphical illustration and more explanations in Appendix [B.2
Lemma 1. With Bo, Lo, Po given in Assumption 2 for any B E (0, (g), fa, is (Lo ) Lipschitt
over R, and | is (2Lo + Be) Lipsschitz over R.
3.2 Bounding the product process
We now present our technique to bound P,. Recall that (a)((a) and ei,)(a) were defined in 2.2 By Lemma &i,9 is (Lo + T + Be) -Lipschhit Now we use f((a) Ta = (a,) Ei, to decompose Rn (in the following, we sometimes shorten "SuPœEK sup SUP " as "sup "):
Ru < sup 2.v m
1 Σ ( x) (a, v) + sup
Σ (a x:) eal Tl. v|.
2.v m
(3.5)
8

---

Jos
2
Figure 1: (Left): fi and its approximation fioss: (Right): approximation error 51,05; [c...s)-
It remains to control Bai and Luz. By the Lipschitz continuity of É,s and |ei,e], the factors of R.,. l and Ru2 admit sub-Gaussian increments, so it is natural to first center them and then invoke the concentration inequality for product process due to Mendelson [36] Theorem 1.13), which we restate in Lemma 3 (Appendix A.. However, this does not produce a tight bound and would eventually to achieve a uniform 22-error of e, as is the case in 17 Section 4].
require Ō (k/E*) e*)
In fact, Lemma is based on Gaussian width and hence blind to the fact that K, (KC))* here have low metric entropy (Lemma 6). By characterizing the low intrinsic dimension of index sets via metric entropy, we develop the following concentration inequality that can produce tighter bound for Rus and Lu2. This also allows us to derive uniform error rates sharper than those in [7 Section 4].
Theorem 2. Let 9n: 9m (a) and h h (a) be stochastic processes indexed by E X C R V c RR?,, both defined with respect to a common random variable a. Assume that:
(AI.) (a), hw(a) are sub- Gaussian for some (Ag, An) and admit sub- nab-Gaussian increments regarding & distance for some (Mg. Mn):
11 - 9x (a) 11 S M2 1| - x' 22112, [1gn(a)llvs S Ag, Vx E ex; (a) hor (a) I MAlle 02112, [ih((a)llss S An, Va, ev..
(3.6)
(A2.) On a single draw of a. for some (Leg Ug. Liz Un) the following events simultaneously hold with probability at least Po:
(a) Sw (a)l < Lg [1|1 x' 2'12,, 19x( (a) I Ug. Va, Ex; (h)(a) har S L - e'112, (a)) S Un, Vu, U' E.
(3.7)
Let a1s..., am be i.i.d. copies of a, and introduce the shorthand Syn LgUh + MggA and
Tan Un + Mn If m H (X, An H (V,
(mTTahh where ((,,) is the
AgAn
/mS.u))
metric entropy defined in Definition 2 then with probability at least mPo exp
AgAn ) + HVV, AgAn VTTT where 1 = sup ueV Em (a,(ha)),,aa)) - Blga ( aa, (h,))/((a)))) is the supremum of product process.
})] we have I I Ag
v HX AgAn ) + HV, fmT
AgAn
/mSgg.
vm
Remark 8. We use L.,t as an example to illustrate the advantage of Theorem 2 over Lemma 5 The key step is on bounding the centered process
R.2. == sup sup {1s,,(a,) [T),((a vi - -El x)lla, o1]}. &Ek vE(K))
Va, then one can use Theorem 2 or Lemma to bound A L22.0 Note that vlls, = -11 justifies the choice Ar, = O(1), and both H (K..) and H (KK,) nn)) depend linearly on & but only logarithmically on r (Lemma 6). so Theorem 2 could bound Ruz.c by Ö(Ag / kk/) that depends on Mg in a logarithmic manner. However, the bound produced by Lemma 5 depends linearly on Mg: see term Anw)((K) in A..I). From 3.6). Mg should
Let gn (a:) l x²) and h,(a.)
vm
be proportional to the Lipsehitz constant of (E,,g), which scales as 1 (Lemma) 7y. The issue is that B many cases we need to take extremely small 3 to guarantee that (2.6) holds true (e.g., we take 3 x k/m in 1-bit GCS). Thus, Lemma 5 produces worse bound compared to our Theorem 2

---

4 Conclusion
In this work, we built a unified framework for uniform signal recovery in nonlinear generative compressed sensing. We showed that using generalized Lasso, sample size of (kk/+²) suffices to uniformly recover all æ E G(B (r)) up to an f2-error of e. We specialized our main theorem to 1-bit GCS with/without dithering, single index model, and uniformly quantized GCS, deriving uniform guarantees that are new or exhibit some advantages over existing ones. Unlike [33], our proof is free of any non- non-trivial embedding property. As part of our technical contributions, we constructed the Lipschitz approximation to handle potential discontinuity in the observation model, and also developed a concentration inequality to derive tighter bound for the product processes arising in the proof, allowing to obtain a uniform error rate faster than [77.. Possible future directions include extending our framework to handle the adversarial noise and representation error.
Acknowledgment. J. Chen was supported by Hong Kong PhD Fellowship from the Hong Kong Research Grants Council (RGC). Scarlett was supported by the Singapore National Research Foundation (NRF) under grant A-0008064-00-00 M. K. Ng was partially supported by the HKRGC GRF 17201020, 17300021, CRF C7004-21GF and Joint NSFC-RGC N-HKU76921.
References
[1] M. Asim, M. Daniels, O. Leong, A. Ahmed, and P. Hand, "Invertible generative models for inverse problems: Mitigating representation error and dataset bias," International Conference on Machine Learning. PMLR, 2020, pp. 399-409,
[2] A. Bora, Jalal, E. Price, and A. G. Dimakis, "Compressed sensing using generative models," in International Conference on Machine Learning. PMLR, 2017, pp. 537-546.
[3] P. T. Boufounos and R. G. Baraniuk, "1-bit compressive sensing," in Annual Conference Information Sciences and Systems. IEEE, 2008, pp. 16-21.
[4] T. T. Cai and A. Zhang, "Sparse representation of a polytope and recovery of sparse signals and low-rank matrices," IEEE Transactions on Information Theory, vol. 60, no. 1, pp. 122-132, 2013.
[5] E. J. Candes and T. Tao, "Decoding by linear programming." IEEE Transactions on Information Theory, vol. 51, no. 12, pp. 4203-4215, 2005.
[6] E. J. Candes and Tao, "Near-optimal signal recovery from random projections: Universal encoding strategies?" IEEE Transactions Information Theory, vol. 52, no. 12, pp. 5406-5425, 2006.
[7] J. Chen and M. K. Ng. "Uniform exact reconstruction of sparse signals and low-rank matrices from phase-only measurements," IEEE Transactions on Information Theory, vol. 69, no. 10, pp. 6739 6764, 2023.
[8] J. Chen, M. K. Ng, and D. Wang, "Quantizing heavy-tailed data in statistical estimation: (Near) Minimax rates, covariate quantization, and uniform recovery," arXiv preprint arXiv:2212.1456.. 2022.
[9] Chen, C.-L. Wang, M. Ng. and D. Wang. "High dimensional statistical estimation under uniformly dithered one-bit quantization," IEEE Transactions on Information Theory, vol. 69, no. pp. 5151-5187, 2023.
[10] H. Chung. J. Kim, M. T. Mccann, M. L. Klasky, and J. C. Ye, "Diffusion posterior sampling for general noisy inverse problems," in International Conference Learning Representations, 2022.
[11] G. Daras, J. Dean, A. Jalal, and A. Dimakis, "Intermediate layer optimization for inverse problems using deep generative models," in International Conference on Machine Learning. PMLR, 2021, pp. 2421-2432.
[12] M. Dhar, A. Grover, and S. Ermon, "Modeling sparse deviations for compressed sensing using generative models," in International Conference on Machine Learning. PMLR, 2018, pp- 1214-1223.
10

---

[13] S. Dirksen, "Quantized compressed sensing: survey," in Compressed Sensing and Its Applica- tions: Third International MATHEON Conference 2017. Springer. 2019, pp. 67-95.
[14] S. Dirksen and S. Mendelson, "Non-Gaussian hyperplane tessellations and robust one-bit compressed sensing," Journal of the European Mathematicul Society, vol. 23, no. 9, pp. 2913- 2947, 2021.
Jourrnl
[15] S. Foucart and H. Rauhut, A Mathematical Introduction to Compressive Sensing. Springer, 2013.
[16] M. Genzel, "High-dimensee estimation of structured signals from non non-linear observations with general convex loss functions," IEEE Transactions on Information Theory, vol. 63, no. 3, pp. 1601-1619, 2016.
[17] M. Genzel and A. Stollenwerk, "A unified approach to uniform signal recovery from nonlinear observations," Foundations of Computational Mathematics, pp. 1-74, 2022.
[18] R. M. Gray and
Stockham, "Dithered quantizers," IEEE Transactions on Information Theory, vol. 39, no. 3, pp. 805-812, 1993.
[19] P. Hand, O. Leong, and V. Voroninski, "Phase retrieval under a generative prior," Advances in Neural Information Processing Systems, vol. 31, 2018.
[20] P. Hand and V. Voroninski, "Global guarantees for enforcing deep generative priors by empirical risk," in Conference On Learning Theory. PMLR, 2018, pp. 970-978.
[21] L. Jacques and Feuillen, "The importance of phase in complex compressive sensing," IEEE Transactions on Information Theory, vol. 67, no. 6, pp. 4150-4161, 2021.
[22] L. Jacques, J. N. Laska, P. T. Boufounos, and R. G. Baraniuk, "Robust 1-bit compressive sensing via binary stable embeddings of sparse vectors," IEEE Transactions on Information Theory, vol. 59, no. 4, pp. 2082-2102 2013.
[23] A. Jalal, Karmalkar, A. Dimakis, and E. Price, "Instance-optimal compressed sensing via posterior sampling." in International Conference Machine Learning (ICML), 2021.
[24] A. Jalal, M. Arvinte, G. Daras, E. Price, A. G. Dimakis, and J. Tamir, "Robust compressed sensing MRI with deep generative priors," " Advances in Neural Information Processing Systems, vol. 34, pp. 14 938- 14 954, 2021.
[25] A. Jalal, L. Liu, A. G. Dimakis, and C. Caramanis, "Robust compressed sensing using generative models," " Advances in Neural Information Processing Systems, vol. 33, pp. 713-727, 2020.
[26] Y. Jiao, D. Li, M. Liu, X. Lu, and Y. Yang. "Just least squares: Binary compressive sampling with low generative intrinsic dimension," " Journal of Scientific Computing, vol. 95, no. 1, p. 28, 2023.
[27] A. Kamath, E. Price, and S. Karmalkar, "On the power of compressed sensing with generative models," in International Conference on Machine Learning. PMLR, 2020, pp. 5101-5109.
[28] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, "Gradient-basee learning applied to document recognition," " Proceedings of the IEEE, vol. 86, no. 11, pp. 2078-2222221 2324, 1998.
[29] Liu and Z. Liu, "Non-iterative recovery from nonlinear observations using generative models." in IEFF/CVF Conference Computer Vision and Pattern Recognition, 2022, pp. 233-243.
[30] Z. Liu, S. Ghosh, and Scarlett, "Towards sample-optimal compressive phase retrieval with sparse and generative priors," Advances in Neural Information Processing Systems, vol. 34, pp. 17 656-17 668, 2021.
[31] Z. Liu, S. Gomes, A. Tiwari, and J. Scarlett, "Sample complexity bounds for 1-bit compressive sensing and binary stable embeddings with generative priors," in International Conference Machine Learning. PMLR, 2020, pp. 6216-6225.
[32] Z. Liu and J. Han, "Projected gradient descent algorithms for solving nonlinear inverse problems with generative priors," arXiv preprint 2209 10093, 2022.
[33] Z. Liu and J. Scarlett, "The generalized Lasso with nonlinear observations and generative priors."
Advances in Neural Information Processing Systems, vol. 33, pp. 19 125-19 136, 2020.
[34] Z. Liu and J. Scarlett, generative models," IEEE Journal on Selected Areas Information Theory, vol. 1, no. 1, pp. 292-303, 2020.
cngemmttion-thereetee lower bounds for compressive sensing with
11

---

[35] Z. Liu, P. Luo, X. Wang. and X. Tang. "Deep learning face attributes in the wild," in Proceedings of the IEEE International Conference on Computer Vision, 2015, pp. 3730-3738.
[36] S. Mendelson, "Upper bounds on product and multiplier empirical processes," Stochastic Processes and their Applications, vol. 126, no. 12, pp. 3652-3680, 2016.
[37] S. Mendelson, "On multiplier processes under weak moment assumptions." in Geometric Aspects of Functional Analysis: Israel Seminar (GAFA) 2014-2016. Springer, 2017, pp. 301-318.
[38] X. Meng and Y. Kabashima, "Quantized compressed sensing with score-based generative models," in International Conference on Learning Representations, 2023.
[39] A. Naderi and Y. Plan, "Sparsity-fuee compressed sensing with applications to generative priors," IEEE Journal Selected Areas in Information Theory, 2022.
[40] G. Ongie, A. Jalal, C. A. Metzler, R. G. Baraniuk, A. G. Dimakis, and R. Willett, "Deep learning techniques for inverse problems in imaging," " IEEE Journal on Selected Areas in Information Theory, vol. 1, no. I, pp. 39-56, 2020.
[41] Y. Plan and R. Vershynin, "Robust 1-bit compressed sensing and sparse logistic regression: A convex programming approach," IEEE Transactions on Information Theory, vol. 59, no. 1, pp. 482-494, 2012.
[42] Y. Plan and R. Vershynin, "One-bit compressed sensing by linear programming." Communica- tions on Pure and Applied Mathematics, vol. 66, no. pp. 1275-1297, 2013.
[43] Y. Plan and R. Vershynin, "The generalized lasso with non-linear observations," IEEE Transac- tions on information theory, vol. 62, no. 3, pp. 1528-1537, 2016.
[44] Y. Plan, R. Vershynin, and E. Yudovina, "Hiigh-dimensional estimation with geometric con- straints," Information and Inference: A Journal of the IMA, vol. 6, no. 1, pp. 1 1-40, 2017.
[45] S. Qiu, X. Wei, and Z. Yang. "Robust one-bit recovery via ReLU generative networks: Near- optimal statistical rate and global landscape analysis," in International Conference on Machine Learning. PMLR, 2020, pp. 7857-7866.
[46] T. M. Quan, T. Nguyen-Duc, and W.-K. Jeong, "Compressed sensing MRI reconstruction using generative adversarial network with cyclie loss," IEEE Transactions on Medical Imaging, vol. 37, no. 6, pp. 1488-1497, 2018.
[47] Scarlett, R. Heckel, M. R. Rodrigues, P. Hand, and Y. C. Eldar, "Theoretical perspectives on deep learning methods in inverse problems," IEEE Journal on Selected Areas in Information Theory, 2022.
[48] C. Thrampoulidis and S. Rawat, "The generalized lasso for sub- uub-gaussian measurements with dithered quantization," IEEE Transactions on Information Theory, vol. 66, no. 4, pp. 2487-2500, 2020.
[49] Y. Traonmilin and R. Gribonval, "Stable recovery of low-dimensional cones in Hilbert spaces: One RIP to rule them all," Applied and Computational Harmonic Analysis, vol. 45, no. 1, pp. 170-205, 2018.
[50] R. Vershynin, High- digheddimesiooal probability: An introduction with applications in data science. Cambridge University Press, 2018, vol. 47.
[51] Whang, Lindgren, and A. Dimakis, "Composing normalizing flows for inverse problems," in International Conference Machine Learning, 2021, pp. 11 158-11 169.
[52] C. Xu and L. Jacques, "Quantized compressive sensing with RIP matrices: The benefit of dithering," " Information and Inference: A Journal of the IMA, vol. no. pp. 543-586, 2020.
12

---

Supplementary Material
A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing (NeurIPS 2023)
A Technical Lemmas
Lemma (Lemma 2.7.7, (50). Let X, be sub-Gaussian, then XY sub-exponential with
|XY||, $ || ||
Lemma (Centering. 50 Exercise 2.7.10]). For some absolute constant C, || -XX-EXlee
EXX] S
C plp--
Lemma 4. (Bernstein's 's inequality, 50 Theorem 2.8.1J. Let XI,.., Xx be independent, zero-mean, sub-exponential random variables. Then for every 2 0, for some absolute constant we have
N Σ x 2t
-emin
12
|X "maxisisN" ||Xiller (|xalbe))
P
S 2 exp
N
Ei=1
Lemma 5. ((3),, statement adapted from 16. Theorem 8)). Let Iu (a) and he he (a) be C R both defined some common random variable a. Assume that (Al.) in Theorem holds, and let a..... be i..dd copies of a. Then for any u 2 1, with probability at least 2 eexp(-cul we have the bound
stochastic processes indexed by x E X' C R
sup =
(a(()))a((a))) - -EE (lgn(a)))l
wEV V
c (M, (2)) + Ag) (Ma w(V) + tu An)
(A.1)
Ag Mn w(V) + An Mg w(X) + u AgAn
vm
where w(-) is the Gaussian width defined as w(X) = E sup g x where g ~ (N,
The proofs of the remaining lemmas will be provided in Appendix D (Some simple facts such as Lemma g were already used in prior works; while we provide the proofs for completeness.)
Lemma 6. (Metric entropy of some constraint sets). Assume K. = (rB) for some L-Lipshhitz
generative model G. Let K- = K. for some T > 0, E (0, 1) let K,_ = (TK-) n (B3 (2e))
and further define (K7)* = { : KT Then for any E (0, Lr), we have
3Lr
6Lr
HFC, < k klog
HK ,1) S 2h log
11
12T H ((K.)",,) < 2h 2k
12
H (K=, .4) < 2 log
en
where (..)) is the metric entropy defined in Definition 2
Lemma 7. (Bound the form of Gaussian vector). If a (00 I.), then P([|a|||2
vnl 2
2 Dexp(-CI") In particular, setting x /n yields P([|a||2 2 /n) 2 2exp(-((m))
In the following, Lemmas 8 indicate suitable choices of T' in the concrete models we consider. These choices make p(x)
2.3 sufficiently small or even zero.
Lemma 8. (Choice of T' in I-bit GCS), If ~ N((0, In), then for any x E Sn-1 it holds that Elsign(a TTaaTT)))ee a)aaa
2 c.
Lemma 9. (Choice of in 1-bit GCS with dithering). Ifa ~ N(. I.) and ~ W|-x, A) are independent, and X CR with sufficiently large C, then for any By(R) it holds that | (sign(a (a x + r) x 09.
13

---

Lemma 10. (Choice of of in SIM). (0, I,), for some function f and any a E g"-1 it holds pæz for μ. = [F] with ~ (0,1), 1).
that ( x)aa
Lemma 11. (Choice of T uniformly quantized GCS with dithering). Given any 6
let
21 ] and (-(-) = ((Lž] + 2) Then, for any a E R, it holds that 1|Qs(a ( + -)]
In particular, let a E In be a random vector satisfying E(aaT) = In and T ~ W | 6 be independent of a, then we have Ii[Os(a') T)aa= x.
2 2
Lemma 12 facilitates our analysis of the uniform quantizer.
Lemma 12. Ler f((-) = 55 2) for T; V 3: 21 and fi,g(-) be defined 63.4 for some 0 < 3 < 5
1g 2. Moreover, let (i,s(a) = [i
s,, = fa - Jz(a), then for any E IR,
[a)) 26, (E,,(aa) holds deterministically.
More generally, the approximation error (s),((a) can always be bounded as follows.
Lemma 13. Suppose that ft satisfies Assumption
2 and for any B E [0, Puj we construct fú.p in 3Toff
3.4 Then, for any a E R, we have ((. <
22 + Bτ) 1 E 2 2.2.50 1).
B More Details of the Proof Sketch
B.1 Set-Restricted Eigenvalue Condition
Definition 4. Let S C R". For parameters 7,8 > 0, a matrix A E p2xx is said to satisfy
S-REC(S, (, 8)
the following holds:
A((x)
x22)l2 2 1 222112 8, V V0i,v2 E S.
was proved in 2 that standard Gaussian.
A satisfies the S-REC with high probability the entries of A are i.i.d.
Vm
Lemma 14. (Lemma 4.1 in (2.. Let G (r(r) be L-Lipschitz for some r, > 0, and define
K. (r)) For any a E (0, 1). if Rmxx has i.i.d. N 1) entries, and 22 d== log 4x)
then 1 satisfies S-RECIKC1 - a,,) with probability at least 1 exp( exp(=S((a²m)).
Vm
B.2 Lipschitz Approximation
The approximation error (-) can be expanded as:
i $ 9₁, +[- 21
2:
(x,)(x) = ft' (20) - f((x) 20 (x00) fi(zo- (2000))))) (x0) - fz())) + 2[fi(oot 8) 12 (=0))(==))))
if E (my - 8 vol. (Ery E 9₁)
3
if [No, To 211 (E.r 9₁,)
9
Although |x,,a| is Lipschitz continuous, EG, is not. In particular, given zy E 9, we note that
(x0) lim (v,((2) = (x0) fi (20) - (5, (zo) f (2o)), 1
z-120
(To)
lim (x,((x) (2ro - 1 (1r) = (5 (2o) - (2n)).
Thus, it is crucial to include the absolute value for rendering the continuity.
C Proofs of Main Results
C.1 Proof of Theorem
1
Proof. Up to rescaling, we only need to prove that || Tx 2/2 S
holds uniformly for a* E K.
We can assume | Tw 1|2 2 > 2e; otherwise, the desired bound is immediate.
14

---

(1) Lower bounding the left-hand side of (3.1)
We use S-REC to find lower bound for
A (Ø- Tx
)1 Specifically, we invoke Lemma 14
mm
with = 2 and = 27. which gives that under = 22k " with probability at least 1 - exp(-cm), the following holds:
A
( 222)
Σ 01
x2ll2
V V0i 22 E K. 2T
(C.1)
Vm
2
Recall that we assume (C.I
| Tx
2
2e, T K. and xx E so we set #1
3. 22 x in
to obtain
A vm
④
1
x²))
||
Tx T==122-
2T
47
Thus, the left-hand side of 3.1) can be lower bounded by 0(1 Tx Tx()))) 112)
(2) Upper bounding the right-hand side of 3.1
As analysed (3.3 and (3.5). the right-hand side 3.1 is bounded by 2|| - -x="122
2 112 (Bu1 - Ru2).
so all that remains to bound Li Ru2. In the rest of the proof, simply write supm,
sUPPEx,.E(Kx5) y- and recall the shorthand (,,((a) fa,s(a) Ta. Thus, the first factor of An, is given by (a, æ). By centering, we have
Ru1 S sup 2
(a a))(a v) - E a (a, a){(a] w)]}
[)]{{])))) + sup E a))(aT
2,8
Lul.c
Rut.
(C.2)
and
Ruo < sup (a
x){{a vl B [[] x)|aaa [[]sia(a)=>\la
wl]
sup
IE [| x)) ||, v
0,
Ru2.c
36 u2c
(C.3)
We will invoke Theorem multiple times to derive the required bounds. (2.1) Bounding the centered product process Bul.c-
We let gæ (a;) (a. æ)) and hy = a; v. and write
m
Bilc = sup a,
(g - (lgg(a))hooa)))}
We verify conditions in Theorem 2 follows:
For any x. x' E K. because Ei,9 is (Lo + Ba + T) Lipschitz continuous (Lemma we have
Bo )laaT x ---aa -a7 a'lles
(l,)(a;) Sw (ai)llus S (Lo + T
3
Bo
= OLo + + || x'112-
Since a; (N. by Lemma with probability 1 - 2 eex((-A(n)) we have ||a:||2 O(yn). On this event, we have
Bo 3
(a.) - gx (a:) S (Lo +
)a x - a. x'1
By
< (Lo + +
|aaillal x'112
3
= =0 Lo + T
Bo
) - x'112.
B
15

---

Recall (K in 3.2). Since (k C sa-1, for any v, E (x,)', we have || v
a, o' vll = ( v v' 22. and when ||a:|| = nl)n) we have la a v'l - a 22 0
o' 12 = Ovvol 22 Moreover, because ) c E. for any v (Ke we have
||, 01lo2 0(1,, a el ||a:122 = O(vn).
Combined with Assumption and its parameters (Ag) U p) and (Ag (2) ,U? P)))) Bul.c satisfies the conditions of Theorem
[ with the following parameters
Bo
Mg x Lo T
Ag = A0) Mr A =1
Bo ) U, = U Ln = vn, Un = vn.
L x (i Lo + +
and Po = P! + 2 eexp( (f(())) Now suppose that we have
m Hf K, Vmn Lo +T B
A
+ H
(KET..
(C.44)
/mlvr (TT g + Ab
and note that by using Lemma 6
(C.4)
can be guaranteed by
I(VnUg) + +455) )
Lr Lr
Bu B
2 k log
puLLo +T
(C.5)
Ag
Then Theorem Ceex((-((k))
yields that the following bound holds with probability at least - mp!")
m exp(=S(()):
A
A Vml ( + A!
Bultel x
9 Vm
H K,
+ H (KE))
Vmnl To + T+ + 3
(C.6)
n(Lo + +T+ Bo + T(VTU,) + 1)
k
Lr A (1)
$
A
log
m
(2.2) Bounding the centered product process L
We let 9m (a;) (a, æ)) and hy (a.) la, v/. and write
22,. sup a
(g (a,)h,,a)) - (lo.(a,),,
We verify the conditions in Theorem as follows:
For any x, xx' E KC, because |ea,e| is (2L. + Be -Lipschiizz continuous (Lemma) 1. we have
Bu )aay x - a,'xx' a'll
(a:)(a;) - 9x (ai)l S (2Lo +
B
Bo
Bu
=
|| x' 1122
By Lemma 7 with probability at least 1 - 2 -eepp ((p(-)((n)) we have ||as|12 = O(vr). On this event, we have
Bo
(a,) Dx (a.)) S (2Lo +
)aa T x
a, x'1
B
By
(2Lo- +
|||, 2'112
3
Bo
= 0(v Lo +
|| 1/2
B
16

---

For any v, E )* we have |||a vl ul la v 11 I
|a (v - -')ll - 0(1) 0'
Similarly as before, we assume |a, = ((vn), which gives |a v a. 00 - |
1212 = O(vn)ll - 2' Moreover, (K c B3 implies |||a, ~ = ((1) and a w -
||0/||||l||| Olv holds for all E (K
Combined with Assumption 3 Luz, satisties the conditions of Theorem 2 with
Bo
Mg x Lo +
Ag = - Mr x 1, A₁ x O11)
3
Lg vn + ) Ug U La vn, Un vn
Bu
and Po = p(2) P( + eexp( -I())) Suppose we have
(2)
A vm(AAz + vnuuf2))
m R H K, "//mml
+ H (Ko)),
Lo
which can be guaranteed (from Lemma 6 by
Lrvm
Bo n(Lo Boy
T(A (2) + vnnug2n)
2 k loo
(C.7)
A
Then, we can invoke Theorem mp(?) 2m (xn)
2 to obtain that the following bound holds with probability at least
1
A
A!
Bu2,e1
2
H K,
+ + (KT)r, /m((A9 ( + v
vm
Vmnll Lo +
Bu
B
(C.8)
k
Lrvm m A
Bo)+
3 + T(A + vTuug ))
( 9
log
n(Lo +
m
(2.3) Bounding the expectation terms Rul.es Ru2,e-
Recall that (a) = (a) -Ta and i (a) fa, fi(a), and so (a) er.a(a)
Ta. Hence, by using al ] I, and ||0|| 1, we have
Rul.e S sup IE[ (f x) -Ta, TaT=)) (a. w)] sup E [ev (a æ))aa v]
< sup øEX
[a x)aa - TTxll2 + sup 2.v
I. [le (a x)) x)|l wl
(C.9)
< sup p(x) + L22,.
#ex
where p(x) is the model mismatch defined in 2.3 and Paz. is defined in (C.3 It remains to bound R2 e. for which we first apply Cauchy-Schwand (with ||0||2 I 1) and then use Lemma 13 obtain
Buz,c = =suple | (a, x)) x)|aaT [J]
z_v
< sup 8,v
F Fllee, (a x: 11] Ella. rl
E (E,,(a aT E 2n. + [-
3
2' 21)]
sup #Ek
V
(C.10)
3LoB
+ BB)
sup V ( PaaTT aaaa 2, + [ #Ek
2' -
2
3
+ Bo)
sup aek
(2)(x))
2
17

---

where we use Lemmal 13 in the third and fourth line, and (1) is defined in (..4.
(3) Combining everything to conclude the proof.
Recall that in Assumption we assume that
sup ( V A
=EX
and we take sufficiently small 81 such that
(Lo.1 + Bo) sup V Ma, (x) S (A V 1 mE
then by setting 3 31. the derived bound w1. + uuzc (see (C. and (C.8) dominates that of
Lute + uue (see (C.9) and (C.10)) and so L11 + Lu 2 d
uul.c Ba2e
Recall that (C.6) and C.8) guaranteed by the sample size of (C.5 and
C.7 while C.5 and
CC.7 hold as long as
Lr L
n(Lo + T Ba T(vT(U)) v v + (A. V {
B
2 k log
Ag (1)
A!
kg
(here we use L to abbreviate the log factors)
(C.11)
with probability at least - m(p(") + pp??) m exx((-S((mm)) C exp((S((k)) we have
K m Therefore, the right-hand side of (3.1 can be uniformly bounded by
Rule + B S (4 A!
o | Tx
112 (4 V (
k
(C.12)
m
Combining with the uniform lower bound for the left-hand side of 3.1 i.e 2(1 12) we obtain the following bound uniformly for all x=:
ki
|| Tx S (A V A )
m
Hence, long
m z (4 V A (21) 2 Kg
2
we again obtain ||0 - Tw* S 3e, which completes the proof.
C.2 Proof of Theorem
Proof. Step 1. Control the process over finite nets.
Recall that X' and V the index of and stated in Theorem the desired concentration for fixed pair (ær, v) E X' x V. By Lemma l|g (lo)) [/ (a.) An, Furthermore, centering (Lemma gives
We first establish Ia (a. (a:) S
2
9 ha,) (a).(a))) = O(ggAn)
Thus, for fixed (x, v) E X V we define
I I
m Σ Im
E[gg (a.)h
Then, we can invoke Bernstein's 's inequality (Lemma
to obtain for any 2 0 that
P( 2 2) 2exp
(cmmmin min
t An }).
(C.13)
A,
18

---

We construct 91 as an -net of X, and G2 as an net of V, with both nets being minimal in that log |91| HH (X' 77 ) log [92] = (V, 12).. and where 7), T2 are be chosen later. Then, we take
a union bound of (C.13 over (æ., v) E 91 x 92 to obtain
(( HVV. cmmmin (AgAn) AAmi))
I
sup
a, 21 s 2exp
=ECi DE92
(C.14)
Now set x An 26 2 for sufficiently large hidden constant. Then, if m 2 (X - H (V, 72)) for large enough C so that AnAn S (we assume this now and will confirm it in C.21 after specifying 7/1 12). C.14) gives
T2
(V. (V.ne) # (X' m) + H
P
sup æEEi
Lw, AgAn
S 2exp (- + (V(.)))))
m
WEG2
Hence, from now on we proceed with the proof on the event
H HX m) + H (2,
sup
Lm AgAn
(C.15)
E
m
2E92
which holds within the promised probability.
Step 2. Control the approximation error of the nets.
We have derived bound for suP=eS, |m while we want to control sup=ex,vev |l, so we further investigate how close these two quantities are. We define the event as
81 = the events in 3.7 hold for all a,, i E [m]],
then by assumption (A2.) in the theorem statement, a union bound gives P( > 1 - mPo. In the following, we proceed with the analysis of the event &1. Combining with (C.15) we now bound vl for any given E X, v E V. Specifically, we pick x' E G1, E 92 such that
I|e' 2||2 S mh I1o' u112 1/2, and thus we have
Ta, S | I S0 50
AgAnn
H HX + H (V,12)
- (C.16)
m
Moreover, we have
1
(alaa))oo(a.) (a (a,))) m E (l - Iw (a: (h (a:)
i=1
Gne (e(aa))o(a))
Iw (ai)h (a) g (a, hh (a;))
171
erra
(C.17)
We bound erT; using the event & as follows:
1
err <
(a, Gw (a;)) 1he (hv (h,(a,) -ar(
m
4. || x'112 1/2 Un + Ln -11 1-100- v'l12 Ug
(C.18)
L,Unn + LnU,m1 = LnUnI + LnU,
m
19

---

On the other hand, we bound erTy using assumption (A1.)in the theorem statement. Noting that
E| = O 1l [50] Proposition 2.7.1(b)), and further applying Lemma 2
we obtain
err2 S (a:)(a))))(a 9w (a. (a.)ll
11 (a;) I (x: (a,)lle + 11 (ar))(a ho (o.)(a
(C.19)
< 11 - Sw (a:) vl (a:))l + 1 (02))ll2l//00 - ho (a:)llvs
- M, || - x' 1|2 An + Ag. MA || v'1l2 S Mg MG + Ma12.
Note that the bounds (C.18) and 19.99 hold uniformly for all (xr E X V, and hence, we can substitute them into (C.16 and C.
to obtain
( AgAn/
H (X, 7h) + H (V,n))
sup mm 50 meX
+ (LgUh +Lggn++MgAN Mg + (LaUg Mr. Mr
m
VEV
(C.20)
Recall that we use the shorthand Sg, =- LgUn + MgAn and Tg LuU, + Mr We set AgAn.
AgAn. 71 x vmS,aa 122 x V so that the right-hand side of C.20) is dominated by the first term. Overall, with sample size satisfying
m Ω
H
H(x;
AgAn VmSg.n
+ H (v,
AgAn VmT g.h.
(C.21)
can bound I supwEx suPEEy Le,vl (defined in the theorem statement)
H AgAm An1mm-1//5 + a.h
HV Ag -1/21 g.h
1/2T
IS IS AgAn
(C.22)
m
with probability at least
-St (H((x
AgAn /mSggn )
H (v, AgAn
VmT.gN )
m. 2 exp
This completes the proof.
D Other Omitted Proofs
D.1 Proof of Lemma (Lipschitz continuity of fú, and Es,o).
Proof. is straightforward check that fi, and | are piece-wise continuous functions; hence, it suffices to prove that they are Lipschitz with the claimed Lipschitz constant over each piece. In any interval contained in the part of x 2, + 21 fi, fi and |ct,al O trivially satisfy the claim. any interval contained in [ro _. xo] for some To 9 fe, is linear with
slope (J) - fi - )), combined with the bound (f0) fi - ) < (fo) -
(x()) + 15; (2o) - fr 9)1 S f (fo)) LoB < (Bn + To, we know that fi, is (Lo + Bo Lippshhitz Further, lex,a| = |fi, - St), and / is Lo-Lipschitz over this interval, so Jes is (2Lo + Ba Lipischit continuous. A similar argument applies to an interval contained in [No, Fu + 2
2
D.2 Proof of Lemma (Metric entropy of constraint sets).
Proof. Bounding H (K.,))
By 50
Corollary 4.2.13], there exists an ( 71 -net In of B/ such that
2Lr
3Lr "
log | < le log
+ 1) < k log
17
where we use S Lr. Note that r is an (4) -net of (r),), and because G is L-Lipschitz, G(rGi) is an 77-net of K, thus yielding H < l log 3Dr
20

---

Bounding X .n) and (K, .7).
We construct 92 as an (3) -ntt net of satisfying log [92] S k: klog 6Lr G2 G2 is nenett of K. K - K. showing that
Then, easy to see that
6Lr
HKK S log 992 26 log
For given T > 0, this directly implies H (TK. .1) S 2k 6T Moreover, because K. C
TK by 50 Exercise 4.2.10] (which states that H (K),)) S H (K2, {) holds for any 0 if 11 22) we obtain
HK H (TK:: !
12
s 2h: log
"
Bounding H ((K2)"
We construct G3 as an (eπ) net of K satisfying log Gal S 2k log 12TLr then we consider (Ga)* == [ G3). We aim prove that (9a)* is 7-net of (K,, )" Note that any æ (X_ can z for some E K and recall that || || 2 2e. Moreover, by construction, there
en
be written as | exists some 22 93 such that ||| 22 l|2 S en. Note that =2 2
E (9a)", and moreover have
22
=2
2
2 1|
|||
1
|
|2 1
2|
22 l12
|2 1|2
|| 112
|| l2
||21||2 1|
21
x21la
2ET
|| 112
2E
17.
Hence, we obtain
12T
H (KK,), m) < log [9s) < log 19al S 2k log
which completes the proof.
D.3
Proof of Lemma 8 (Choice of T in 1-bit GCS).
Proof.
Since x Sn-1 for some orthogonal matrix P we have Px ee (the first column of I,).
Since = Pa [ā,] has the same distribution as a, we have
Bssign(a" x)a) BBlsign(a" e e1)P a P M[sign(ā
2
= PT -
D.4
Proof of Lemma
CCoice of T in 1-bit GCS with dithering).
Proof.
We first note that
E B[sign(a" Ta x +Taa]
sup wE
[ sign(a T x + +)7aaTo) - -x- zT)).
(D.1)
1
We first fix and expect over T 2 -- A) to obtain
Er, [Asigu(a" x TTaa v]
[((aa xl \) sa Φ) [(aaTz) 5 (A+a" ( x a TTa
=(>a Tv) v)
21
21
=(a" x)(aa v)l((a x A) + (da T v) sign(a x)1((a T æ| > A).
21

---

We plug this into D.1 and note that x' x'v- Ea(a" x)( (a(aaa)(a" v)1, which gives
Elsign(a" a + +T)aa= A
a
E ([(Aa () sign(a
- (a <) (eaaaTT]s v)) [o) 20 > 21)
sup
(D.2)
vES
$
sup
([)aa' v la >=laaaaaa e > A))
vEga-1
For any B2( (R) and v E s"-1, we have
||a a1o>> = O(R) and l|a volss = O(1) Applying
the Cauchy-Schward inequality, we obtain
E ([Ala v la a " A))
X) sv 2/2(22 Dallaa/l333 E x v)) V 2exp(-c)2/1)
Sv El(A|aTu ol + I=T [aTaaTl)))) P(a
A
Exexp
-R m
Note that in the third line, use the probability tail bound of the sub- Gaussaan |a æc and in the last line, we use = CRylog m with some sufficiently large C. The proof completed by substituting this into D.2.
D.5 Proof of Lemma 10 CCoice of T in SIM).
Proof. This lemma slightly generalizes that of Lemma We again choose an orthogonal matrix P such that Pæ = e1, where e₁ represents the first column of I, Since a and Pa have the same distribution, we have
Els(a x)a P - PTE[[((Pa)Te) Pe)
(TE PT (T(e))) par.
D.6 Proof of Lemma 11 (Choice of T in uniformly quantized GCS with dithering).
Proof. In the theorem, the statement before "In particular" can found 18 on this, we have [[{s(a") x + +)aa = IE, [Qs x r)aa (aa x) æ.
Theorem 1]. Based
D.7 Proof of Lemma 12 (Bounds on ISs,al and |er,9 for the uniform quantizer).
Proof. By the definition of fi, in 3.4 we have [c), (a), fı(a)] 8. It follows that
fi(-) 2s(-+77 with (a 0( + )). and [Q((a -a s holds for any a E E. Hence,
$ To complete have (a) aa| (a +T| S - f((a) (a(() I 8 26.
the proof, the inequalities (,)(a) - (f,
D.8 Proof of Lemma 13 (Bound on the approximation error (
Proof. For any $ 9,, + 1. L. by the definition in 3.4) we have (1,)(a) = 0. Ifa E [ro _
for some Zo E Dj. then we have
|Ev,((a)) (a) f((a))
fi, (No) + (ft,a(20) - fi (xo)) (xo) - fa(a)
Bp
2Lo +
zol aal+1o 11 fr (2o) Lo al
B
Bp
8 + 1,, (x0) - J; (2o)) -
3T.
3L +
2 + Bo,
B
2
2
where we use Lemma and Assumption 2 in the third line, and use |a zol < and (a
(fr (æo) + ft (2o) in the fourth line.
22

---

E Parameter Selection for Specific Models
F.1 1-bit GCS
To specialize Theorem to this model, we select the parameters as follows:
Assumption
2 Under the 1-bit observation model y; sign(a, x*), the function fi(-)
f(-) = sign(-) satisfies Assumption 2 with (Bo, Lo, Bo) = (2, 0, oo).
2.5 in Assumption
Recall that K. C g Under the assumption || 2 1, we set
T= = 2/ so that p(z) = 0 holds for all x E X' (Lemma 8), which provides 2.5
Assumption 3. By Lemma 7 we have P(]|a||2 = Olvn) > 1 - 2 expl - ((n)), and we
suppose that this high-probability event holds. Also note that [|i S 1. Hence, we have
IIS,s(a T 1)) S Il
x)]l + |Ta =1ly, = 0(1),
sup (a x) aeK
S Ifi, x)) + Ta x 1 1+1+T|aalz = O(Vn).
Because 6i,8
JL, Si have l|er, (a a:) >> 0(1), and l Tx)] < 2 holds
deterministically. Hence, regarding the parameters in Assumption 3 we can take
1 11,0 vn, P exp(- A 11U0, 1.P() 0.
2.6 in Assumption It remains to pick 31 that satisfies 2.6 Note that Ry = {0]. and for
any x E KC a x (0, 1), so we have
(=(x)) P PaaT
3 1 0(3).
x
2'
Thus, we take 81 x to guarantee (.6).
E.2
1-bit GCS with dithering
To specialize Theorem to this model, we select the parameters as follows:
Assumption
The observation function can be written as f(-) sign(- 7) with W [-X, Xl, which satisfies Assumption 2 with (Bu, Lo. Bu) (2, 0, oo).
2.5) in Assumption We set À = CRvlogg m with C' Carge enough, so that Lemma justifies 2.5).
Assumption By Lemma we have P([aa|| O(vn)) 111--am 2exp(=S((n).. Assume this event holds, and note that Jú, is still bounded by 1, we have
[ (aTTll < [[i,s(a =>) + -11A''''
a. xe æ
0()
sup (a, (Taaa]=)]]]))) m)) S 1 sup mek
1 x
<
sup X |2 =Ek
Moreover, because Ei, = Si,8 fú, the following hold deterministically: ||er,p m lle ((1), suPaek 16t (a a:) = 0(1). Thus, regarding the parameters in Assumption we can take
A 1, (11) Vn, pd x exp( ((n)), AT x 1, U(2) x p( 0.
(2.6) in Assumption #
remains to confirm (2.6) for suitable 3r. For any 8, note that 2.7 T + 8), and hence for any x E K. C By (R) we have
2r.
+
= ir
2'2
[----- 5 2. - - -
(1) Pa
8
8 8
(z(x)) = P a T x e
2' 2'2 2 X
which can be seen by conditioning Hence, take 3 = B1
Ak to guarantee 2.6
23

---

E.3 Lipschitz-continoous SIM with generative prior
To specialize Theorem I to this model, we select the parameters as follows:
Assumption 2 Since f is L-Lipschitz by assumption, it satisfies Assumption 2 with
BB. Lo. 3b) = (0, oo).
E[ vb [llg)) where 9 No, 1). Then, we choose T = μ so that p(x) = 0 holds for any æ
(2.5) in Assumption 4 Recall that we have defined the quantities
(Lemmaa 10p, thus justifying (2.5)
Assumption 3 Because fe is L-Lipschitz and does contain any discontinuity, there is no need to construct the Lipschitz approximation fi, for some 3 > 0, while we simply use 3 = 0, which implies fi = Si and ,i = 0. Note that (a,)(a) fi(a) pa, and so have
llf((a T x)) pa æ1l02 < I[fi(a T <)ll> + I| T x allv2 O + u).
We suppose ||a||2 O(vn), which holds with probability at least Lexp(-S((m)) (Lemma
7 we also suppose fi) S B, which holds with probability at least 1 Pd by assumption.
On these two events, we have
[fe(a T xt) pa T x: V [i T x) [:(0)] + (A((0) + /=|aa|2 |=|1|
s i|aal|2 + B p||a||2 x (1 / B.
Combined with 6i, O, we can set the parameters in Assumption 3 as follows:
A x e + n, U x +) B, p()) x Pd exp(-S(nn))
A 2 + μ, U3²0) = p(2) =.
2.6 in Assumption 4 Because 3 0 and 9 =8, (26) is trivially satisfied.
E.4 Uniformly quantized GCS with dithering
To specialize Theorem I to this model, we select the parameters as follows:
Assumption The uniform quantizer with resolution å > 0 is defined as Qs(a) = 6(1
for E R. We consider this quantizer with dithering Ti 4/ --6 3. f] Specifically, we observe
y: = 2s(a, x* + T:), so the observation function f(-) 2s + 7) with T ~ -1 5/4 1
Hence, Assumption 2 is satisfied with (Bu, Lo, (u) (6, 0, 6).
2.5) in Assumption The benefit of dithering is to whiten the quantization noise. With T = 1,
for any E K. Lemma I1 implies p(x) |E (a x + T,)aa] x 1|2 = 0, thus justifying
(.5).
Assumption Note that for any (0, 3) by Lemma 12 we can take the parameters for Assumption as follows:
1 (1)
9 ((2) U 8, p(") po2) 0.
All that remains is to pick 3 = B1 that satisfies 2.6 0/ T; + 82, hence for any K. we have
(2.6) in Assumption
Because
(x) P Pa - + 5z
B 2 () =P(a (a + oz
3 & 2 2. -- -0 (
2'
which can be seen by using the randomness of ~ 21-2 2
conditionally on æ. Hence, we
kō take 3 = 31 m which provides (.6).
F Handling Sub-Gaussian Additive Noise
In this appendix, we describe how our results can be extended to the noisy model f(Ax*) + n. where v Inm is the noise vector that is independent of (A, f) and has i.i.d. sub-Gaussian entries V/s satisfying | 0(1). Along similar lines as in 3.1 3.1
3.3), we find that gives
rise to an additional term (n. A(a Tx")) to the right-hand side of 3.1 3. which is bounded by
24

---

2||a Tx= sup (E 1 (n. Av), with the constraint set (K,)) defined in (.2). Thus, in (33 in addition to Bu.. in the noisy setting need to bound the additional term
1|2
1 (n, An) (C(KT)) m
1 Σ naa v.
R₂y
sup
sup "E(()T
m
This can be done by the following lemma, which indicates that the sharp (uniform) rate in Theorem | can be retained in the presence of noise 17.
Lemma 15. (Bounding the additional term R2,), In the noisy setting described above, with probability
log T(a)) C2 exp(-I((m)) we have R2 2 klog TLe
least C
m
Proof. Conditioning on 17, the randomness of a, gives Ei= naa; NoO, In
m² In). and so II E. n.a.) TT m Σn= ()aa)) "elles Callnila u2 holds for any 01 22 E R. Let w(-) be the Gaussian width as defined in Lemma 5 Then, using the randomness of a, ss Talagrand's
comparison inequality [50] Exercise 8.6.5] yields that for any 2 0, we have
PP R - Cillm/1a (M(((,))*) +1)
exp(-t²)
(F.1)
m
Next, we bound the Gaussian width )*) Recall that )" is defined in (3.2. and Lemma bounds its metric entropy .H ((C,), )", S 2k log 12TLe, Thus, can invoke Dudley's integral en
inequality (50) Theorem 8.1.3] to obtain
Lr en
TLr klog
w((K))) S C2
2k log
dn S
Now, further let / / A:log Thr in (F.1) to obtain that R2 x
Ilnllay The m
holds with
remains deal with the randomness of v and bound [mll.. Because has ii.d. entries with || 1l = (1), by (50. Theorem 3.1.1] we can obtain that || S Cavmm with probability at least expp( c3m). Substituting this bound into R2 S [Iullay/k log Poe the result follows.
probability least 1 - 2 exp(-eppep -k log TLr).
To close this appendix, briefly state how to adapt the proof of Theorem I to explicitly include the additive noise 77. Specifically, the left-hand side of (3.1 and its uniform lower bound [2 --xx"""
remain unchanged, while the right-hand side of (3.1 now bounded by 2 T'x 1|2 2- (R.1
Ass + R(,) (with 2 2 - Tx" "< 11,R being the additional term); thus, combining the bound (C.12) on 2 Tx" 1|2
m1 + Fuz) and Lemma we establish a uniform upper bound
o ||0 |8-TTx Tw 122 [(A)] V A(D))
k. +
k log The
for the right-hand side of (3.). Therefore, to ensure uniform recovery up to the f--norm accuracy of e under the sub-Gan Gaussian noise it suffices to have a sample complexity
log
T'r
2 (A
(F.2
22
Since the logarithmic factors L in C.11 dominates log TLr F.2 indeed coincides with the sample complexity m 2 (A v A
K. e
in Theorem under the mild condition of A!") A! 2(1).
G Experimental Results for the MNIST dataset
G.1 Details of the Settings
In this section, we conduct experiments on the MNIST dataset 28 to support our theoretical framework. We use various nonlinear measurement models, including 1-bit, dithered 1-bit, RcLU,
25

---

2
6
6
2
3
2
3
4
9
6
7
O
2
4
S
6
7
6
7
O
J
2
3
Figure 2: Reconstructed images of the MNIST dataset for the noiseless 1-bit measurements with m 150.
and uniformly quantized CS with dithering (UQD). We select 30 images from the MNIST testing set, ensuring that there are three images from each of the 10 classes for maximum variability. single measurement matrix A is generated and used for all 30 test images. All the experiments are repeated for 10 random trials. All the experiments are run using Python 3.10.6 and PyTorch 2.0.0, with an NVIDIA RTX 3060 Laptop 6GB GPU.
We train variational autoencoder (VAE) on the training of the MNIST dataset, which has 60,000 images, each of size 784. The decoder of the VAE is fully connected neural network with ReLU activations, with input dimension k 20 and output dimension 784, and two hidden layers with 500 neurons each. We train the VAE using the Adam optimizer with mini-batch size of 100 and learning rate of 0.001.
Since our contributions are primarily theoretical, we only provide simple proof-of-concept exper- imental results. In particular, since (2.1) is intractable solve exactly, estimate the underlying signal, we choose to use the algorithm proposed in [2] (referred to as CSGM) to approximate it. CSGM performs gradient descent algorithm in the latent space in R&& with random restarts. In addition, compare with the Lasso program that is solved by the iterative shrinkage thresholding algorithm.
For CSGK, we follow the setting in 2 and perform 10 random restarts with 1000 gradient descent steps per restart and pick the reconstruction with the best measurement error.
G.2 Experimental Results for Noiseless 1-bit Measurements and Uniformly Quantized Measurements with Dithering
In this subsection, we present the numerical results for 1-bit measurements and uniformly quantized measurements with dithering, while the results for dithered 1-bit measurements and the Lipschitz SIM where the nonlinear link function is ReLU are similarly provided Appendix G.3 For 1-bit measurements, since the underlying signal is assumed be unit vector and aim recover the direction of the signal, we use cosine similarity that calculated as â x=" /(I|z]|2 ||æ ||2) with & being the estimated vector to measure the reconstruction performance. For uniformly quantized measurements with dithering, we use the relative f2-norm distance between the underlying signal and the estimated vector, i.e., | x= [||| 1|2. to measure the reconstruction performance.
Since this paper is concerned with uniform recovery performance, in each trial, we record the worst- case reconstruction performance (i.e., the smallest cosine similarity the largest relative error) over the 30 test images, and the worst-case cosine similarity or relative error is averaged over 10 trials.
Figures and show that for noiseless 1-bit measurements and uniformly quantized measurements with dithering with the test images when the number of measurements m is as small as 150 and 100 respectively.
the CSGM approach can produce reasonably accurate reconstruction for all
G.3 Experimental Results for ReLU and Dithered 1-bit Measurements
We present the experimental results for the ReLU link function and dithered 1-bit measurements in Figures 6 and 7 For dithered 1-bit measurements, we set X = R m with R > 0 being a tuning parameter. For the case of using the ReLU link function, similarly noiseless 1-bit measurements, we calculate the cosine similarity to measure the reconstruction performance. For dithered 1-bit measurements, similarly to uniformly quantized measurements with dithering, we calculate the relative f--nom distance. We observe that for these two nonlinear measurement models
26

---

6
6
2
3
4
S
6
O
7
6
6
7
O
2
3
6
Figure 3: Reconstructed images of the MNIST dataset for UQD with 100 and à = 3.
1.0
CSOM
Cosine Similertt
0.7
Relalive Ertor
Relative Errer
0.6
0.3
0.4
0.7
0.7
0.3
0.5
0.5
50
75
100
125
150
175 200
225
250
50
75
100
125
150
175 200
225
250
0.0
2.5
5.0
10.0 12.5
15. 17.5 20.0
(a) 1-bit with varying m
(b) UQD fixed å
(c) UQD with fixed m
Figure 4: Quantitative results of the performance of CSGM for 1-bit and UQD mcasurements on the
MNIST dataset.
with a single realization of the random measurement ensemble, CSGM can also lead to reasonably good reconstruction for all the test images when the number of measurements is small compared to the ambient dimension.
H Experimental Results for the CelebA dataset
which contains more than 200,000 face images for celebrities with an ambient dimension n 12288. We train deep convolutional generative adversarial network (DCGAN) following the settings in hhtps //pytorch.
In this section, present numerical results for the CelebA dataset 35
Baclcgganaaa___________e faces ttteeuuutrrlllla html The latent dimension of the generator is k 100 and the number of epochs for training is 20. Since the experiments for CelebA are more time-consuming than those of MNIST, we select 20 images from the test set of CelebA and perform random trials. Other settings are the same as those for the MNIST dataset.
Since we have observed from the numerical results for MNIST that the experiments for the ReLU link function and dithered 1-bit measurements similar, only present the results for noiseless 1-bit measurements and uniformly quantized observations with dithering.
From Figures and 10
observe that for noiseless 1-bit measurements with 1500 samples, single measurement matrix A can lead to reasonably accurate reconstruction for the test images. In addition, from Figures] and 10 we observe that for uniformly quantized measurements with
Origina
2
O
3
6
8
9
O
2
3
2
O
4
6
8
O
2
3
8
Figure Reconstructed images of the MNIST dataset for the ReLUU link function with
150 and
0.2.
27

---

O
2
7
6
6
0
2
3
4
6
7
O
4
5
6
6
7
O
2
3
5
350 400 450 500 550 Figure 6: Examples of reconstructed images of the MNIST dataset for dithered 1-bit measurements
with m 250 and 5.
1.0
0.7
CSGM
CSCM
Cosine Similant
Cosire Simillaiity
Relative Error
0.6
63
0.5
0.7
8 93
0.6
Lasso
50
75
100
125
150
275
200
225
250
0.25 0.50 0.75
1.00 1.25 150 1.75 2.00
150
200
250
300
m
(a) ReL.U with fixed 0.1
(b) ReLU with fixed 150
(c) Dithered 1-bit with fixed R
Figure 7: Quantitative results of the performance of CSCM for the ReLU link function and dithered 1-bit measurements on the MNIST dataset.
dithering, a single realization of the measurement matrix and random dither is sufficient for the reasonably accurate recovery of the 20 test images when m 1000 and
20.
CSOM Original
Figure Reconstructed images of the CelebA dataset for the noiseless 1-bit measurements with 1500.
28

---

Original
jide
Figure Reconstructed images of the CelebA dataset for UQD with 1000 and 6 20.
CSGM
1.2
C3GM
1.0
Coslie Similartt
Reletive Error
0.0
Relative Error
3.1
0.6
0.9
0.5
0.8
0.7
0.4
0.6
0.3
CSGM
0.5
200
800
2000
600
1000
(a) 1-bit with varying m
(b) UQD with fixed 20
(c) UQD with fixed m 500
Figure 10: Quantitative results of the performance of CSGM for 1-bit and UQD measurements on the CelebA dataset.
29


Reviews:
[{"review_id": "NKihbfPoPy", "reviewer": "Reviewer_K1vm", "summary": "The paper discusses a unified framework for uniform signal recovery in nonlinear generative compressed sensing. The authors utilized the use of generalized Lasso and Lipschitz approximation to allow for a lower sample size of measurements.", "questions": "1) Please expand on the transitions between equations.\n2) How did you ensure that the assumptions that were presented in the paper hold in your experiments?", "limitations": "The limitations are adequately addressed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "In what follows the strengths of the paper are given:\n\n1) The paper presents a framework for deriving uniform recovery guarantees for nonlinear generative compressed sensing where the observation model is nonlinear and possibly discontinuous or unknown.\n2) Utilizing the generalized Lasso and Lipschitz approximation allowed for a lower sample size of $\\tilde{O} \\left( \\frac{k}{\\varepsilon^2} \\right)$, which is smaller than the previously best bound of $\\tilde{O}\\left( \\frac{k}{\\varepsilon^4}\\right)$.\n3) The idea of drawing back from using a concentration inequality (Lemma 5) in the appendix and instead leveraging the use of metric entropy to derive a tighter upper bound on $\\mathcal{R}_u$ is quite interesting.\n4) Finally, the paper is mainly theoretical and the experimentation done in the supplementary is to show confirm the findings of the paper, which are extensively shown.", "weaknesses": "The paper is somewhat hard to follow:\n1) Some notations are used before they are defined.\n2) Some explanations around the mathematical parts are not properly stated, e.g., transitions.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your recognition of this paper and the helpful comments. Regarding readability, please see the general response above.  \n\n(**How did you ensure that the assumptions that were presented in the paper hold in your experiments?**)\n\nWe would like to highlight that this work is primarily theoretical, and the experiments are basic proof-of-concept and not a main contribution. Assumptions 2-4 are assumed solely for the theory, and we have verified in Corollaries 1-4 (with the details being provided in Appendix E) that these assumptions are reasonable and are satisfied by various nonlinear models. As for Assumption 1, in particular for the assumption of no representation error (i.e., the target signal is contained in the range of the generative model) and its practical effect, please refer to our general responses to all reviewers. \n"}, {"review_id": "nvfSkMUtIF", "reviewer": "Reviewer_85GG", "summary": "This paper introduced a unified framework for uniform signal recovery in nonlinear generative compressed sensing, in particular, 1-bit generative compressed sensing (GCS) and single-index models (SIM).   The authors obtain  uniform recovery guarantees for 1-bit  GCS, 1-bit GCS with dithering, Lipschitz-continuous SIM, and uniformly quantized GCS with dithering.  Experimental results are presented to corroborate the theoretical results. ", "questions": "See above", "limitations": "Unreasonable assumptions and lack of discussions of some latest works. ", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1.  A unified framework for uniform signal recovery in nonlinear generative compressed sensing is proposed. \n2.  Uniform recovery guarantees are obtained for 1-bit  GCS, 1-bit GCS with dithering, Lipschitz-continuous SIM, and uniformly quantized GCS with dithering. \n\n", "weaknesses": "1. Both main statements and corresponding proofs build on the strong assumption that the target signal exactly belongs to the domain of generative models. Apparently, this is not the case for real-life compressed sensing, both theoretically and empirically. The key idea of generative compressed sensing is to recover an unknown target signal by leveraging the generative prior to capture its intrinsic structure. Nevertheless,  it does not assume that the target signal is exactly generated by the assumed generative models. However, the goal of this paper is to prove the uniform recovery of a signal that is exactly generated by a known generative model, which is apparently not the case of real compressed sensing, or is a different problem.  What if the target signal is not generated by the assumed generative model? \n\n\n2. Given that this paper assumes that the target signal is exactly generated by a known generative model, how can the results be applied to practical generative models. For example, given two algorithms, one using a VAE prior, the other using a GAN prior, how to compare the corresponding reconstruction results? \n\n\n3. Are the main results applicable to diffusion models? This paper assumes an L-Lipschitz continuous generative model and a radius r Ball in R^k. Recently, there are several recent studies on diffusion models for generalized linear inverse problems including 1-bit compressed sensing, for example:\n\n[R1] Meng, Xiangming, and Yoshiyuki Kabashima. \"Quantized Compressed Sensing with Score-Based Generative Models.\" ICLR2023\n[R2] Chung, Hyungjin, Jeongsol Kim, Michael T. Mccann, Marc L. Klasky, and Jong Chul Ye. \"Diffusion posterior sampling for general noisy inverse problems.\" ICLR2023.\n\n[R1] discussed quantized compressed sensing with score-based generative models and [R2] introduces a unified diffusion posterior sampling method for general noisy linear and nonlinear problems. Can the main statements in this paper apply to the above latest studies with diffusion models? Please illustrate the main differences and explain why. \n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your useful comments and questions. Regarding the signal lying exactly in Range(G) and applying to practical generative models, please see the general response above.\n\n(**Are the main results applicable to diffusion models?**)\n\nIn this paper, our focus is on generative models with a low-dimensional latent structure of size $k \\ll n$, which captures many important generative models of interest.   However, diffusion models are very different in that they map $\\mathbb{R}^n \\to \\mathbb{R}^n$ and create significant mathematical complications, e.g., Range(G) may be prohibitively large unless we only consider a small subset (e.g., one with high probability) of the latent space.  Being unable to handle such models when studying the sample complexity of high-dimensional inverse problems is not specifically a limitation of our work, but rather a **substantial open problem that is yet to be tackled by anyone** (to our knowledge).  Accordingly, we strongly believe that addressing this open problem should not be expected in a work of our nature.  To back up our claims, we note that even papers specifically about provable recovery with diffusion models do not give sample complexity guarantees (e.g., see https://arxiv.org/abs/2307.00619 and https://arxiv.org/abs/2302.01217).\n\nNevertheless, we thank the reviewer for pointing out these two interesting papers on diffusion models. We will cite these papers in a revised Conclusion and Future Work Section and mention that providing similar uniform sample complexity guarantees for diffusion models is an interesting future direction. \n\n"}, {"review_id": "qCP7b05Sga", "reviewer": "Reviewer_6eZp", "summary": "In non-linear compressed sensing, one would like to recover x from a\nseries of observations y_i = f_i(a_ix); and in generative compressed\nsensing, x is drawn from a generative model.  The contribution of this\npaper is a framework for uniform recovery with general nonlinear\nmeasurements and Lipschitz generative models; in particular, this\nframework includes Lipschitz generative models and dithered 1-bit\nmeasurements, which were not previously known to give uniform\nrecovery.\n", "questions": "* Can you give a corollary for handling Gaussian noise?\n\n* What would you do for nonlinear sensing that's more nonlinear than discretization, e.g., sinusoidal or quadratic observations?", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The result is fairly general, handling dithered 1-bit or otherwise\ndiscretized measurements, as well as noise in the measurements.  The\nbound is pretty good, basically ideal except possibly for some terms\ninside the log factor.\n", "weaknesses": "The first specific application the authors present for this framework\nis:\n\n (1) uniform recovery of (2) Lipschitz generative models from (3)\n dithered 1-bit measurements\n\nThis is pretty specific, and if any one of the terms is relaxed\n(nonuniform, a ReLU generator, or non-dithered) then prior work covers\nit.  That is to say: the result is nice and general, but prior work\nhas pretty well covered the most interesting cases covered by this\nresult.\n\nThe writeup could be improved, repeatedly defining things in terms of\nterms that are defined pages later.  For example, the main theorem\n(Theorem 1) relies on script(L), which isn't defined until the\nsupplemental material; Assumption 3 uses section 3;\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your positive assessment of this paper and the useful comments and suggestions.  We respond regarding the writing quality in the general response to all reviews, and respond to the other points as follows.\n\n(**If any one of the terms is relaxed (nonuniform, a ReLU generator, or non-dithered) then prior work covers it**) \n\nThanks for the comment. We agree that some prior results have been established if any one of the three terms is changed, but we also note that any of the three terms is non-trivial rather than a straightforward extension:\n\n- As explained in the paper, it is often significantly more challenging to establish uniform guarantees compared to non-uniform ones.\n- Compared to ReLU networks studied in Qiu et al. (2020), our Lipschitz generative model is more general and requires different proof techniques.\n- Dithered 1-bit measurements and non-dithered 1-bit measurements are of very different characteristics, e.g., the former allows for norm recovery while the latter cannot; this can be seen by comparing our Corollaries 1 and 2.\n- Besides the 1-bit cases, we also mention that our Corollary 4, regarding dithered uniformly quantized measurements, is of practical interest and novel. Specifically, in the literature, there is no prior (uniform/non-uniform) guarantee for GCS under such a quantizer. Also, in a situation where we are allowed to sample several bits from each measurement, the uniform quantizer could retain more information and hence may be preferable. \n- We highlight the significance of a unified framework, which allows us to clearly see the ingredients (i.e., our Assumptions 2-4) that lead to sharp uniform recovery guarantees. We believe that this is also positioned as an important contribution. \n\nS. Qiu et al. \"Robust one-bit recovery via ReLU generative networks: Near-optimal statistical rate and global landscape analysis.\" In ICML, 2020.\n\n(**Can you give a corollary for handling Gaussian noise?**)\n\nSince the non-linearities can be possibly random, Gaussian noise can be encompassed in our results for single index models (see Corollary 3). For the remaining quantization models, we may consider the case of adding Gaussian noise explicitly with the measurement model $\\mathbf{y}=f(\\mathbf{A}\\mathbf{x}^*)+\\mathbf{e}$ where $\\mathbf{e}$ follows the $m$-dimensional standard Gaussian distribution. For this case, we will need to bound an additional term $\\sup_{\\mathbf{v}} \\sum_{i=1}^m e_i \\mathbf{a}_i^\\top \\mathbf{v}$, which is not a product process and is easy to handle compared to the current $\\mathscr{R}_u$ (defined in the equation before Line 301). We will add a corollary for handling Gaussian noise in the revised version.\n\n\n(**What would you do for nonlinear sensing that's more nonlinear than discretization, e.g., sinusoidal or quadratic observations?**)\n\nSince the $\\sin(\\cdot)$ function is 1-Lipschitz continuous, the sinusoidal model where $f_i(x) = \\sin(x)$ is encompassed by our single index model result (Corollary 3) where we can achieve accurate recovery without knowing $f_i$. For the quadratic model where $f_i(x)=x^2$ (which corresponds to the phase retrieval problem), we note that the important parameter $T$  (see Line 138) is zero, which means our results are not applicable to this model. However, we note that it is a common issue that classical single index models do not encompass the quadratic model, and phase retrieval models are typically studied separately from our sort of models. See, e.g., Page 5 and the Conclusion Section of Yang et al. (2017). We thank the reviewer for this interesting question and we leave the uniform recovery guarantees for generative model based phase retrieval for future study. \n\nZ. Yang et al. \"High-dimensional non-Gaussian single index models via thresholded score function estimation.\" In ICML, 2017. \n"}]

Author rebuttal:
**General responses to the three anonymous reviewers**

We are very grateful to the reviewers for their helpful feedback and suggestions. Our responses to the main concerns shared by multiple reviewers are given as follows. Other responses are given to each reviewer separately. 

(**The assumption that the target signal exactly belongs to the range of generative models**) 

We agree that relaxing the assumption of no representation error (i.e., the target signal lies exactly in the range of the generative model) is of significant interest. However, for high-dimensional single index models (SIMs) with the generalized Lasso method, it may be infeasible to obtain comparable theoretical guarantees upon doing so. To the best of our knowledge, all prior works in this line (high-dimensional SIMs with generalized Lasso type approaches) assume no representation error, even under simpler classical priors where the target signal is assumed to be exactly contained in a low-complexity structured set or for weaker non-uniform recovery guarantees. A partial reference list is provided below. 

In particular, appropriately handling the representation error for SIMs (with the generalized Lasso approach) has been mentioned as an open problem in the Discussion Section of the seminal work by Plan & Vershynin (2016).  We also highlight the recent work of Genzel & Stollenwerk (2023), which is the most relevant work to ours and also considers a setting where the signal lies *exactly* in a known structured set.  

As is evident from the fact that these recent papers have been published in the topmost venues in machine learning, and/or as evidenced by the substantial citation counts of these works (also shown on the list), we believe that the assumption of no representation error has been widely accepted in the active research area of high-dimensional SIMs.  We sincerely hope that the final score/decision for our submission will be based on the main goal and contributions of this particular paper, rather than on the general limitations in a broad and popular line of works. 

References:

Y. Plan &  R. Vershynin. "The generalized lasso with non-linear observations." IEEE Trans. Inf. Theory, 2016. [198 citations]

M. Genzel. "High-dimensional estimation of structured signals from non-linear observations with general convex loss functions." IEEE Trans. Inf. Theory, 2016. [47 citations]

Z. Yang et al. "High-dimensional non-Gaussian single index models via thresholded score function estimation." In ICML, 2017. [47 citations]

X. Wei et al. "On the statistical rate of nonlinear recovery in generative models with heavy-tailed data." In ICML, 2019. [22 citations]

C. Thrampoulidis & A.S. Rawat. "The generalized lasso for sub-gaussian measurements with dithered quantization." IEEE Trans. Inf. Theory, 2020. [24 citations]

Z. Liu &  J. Scarlett. "The generalized lasso with nonlinear observations and generative priors." In NeurIPS, 2020. [12 citations]

M. Genzel &  A. Stollenwerk. "A unified approach to uniform signal recovery from nonlinear observations." Foundations of Computational Mathematics, 2023. [New paper]

(**Given the assumption that the target signal is exactly generated by a known generative model, how can the results be applied to practical generative models?**)

We would like to highlight that this work is primarily theoretical, and the experiments are basic proof-of-concept and not a main contribution. We observe from the experimental results presented in the supplementary material that we can obtain accurate reconstruction for MNIST and CelebA images using a relatively small number of samples. This indicates that the generalized Lasso approach itself is still effective with representation error, although the theory is an interesting open problem. 

(**The paper is somewhat hard to follow or the writeup could be improved**) 

In the revised paper, we will ensure that all the notations are defined before they are used and add more explanations between equations to make the paper easier to follow. This will include the specific suggestions by Reviewer 6eZp, and those we find from our own careful proofreading. We also welcome any further specific pointers from all three reviewers. While we will strive to be meticulous with these edits, we are confident that they will still amount to relatively minor changes.

Meta-review: The paper studies non-linear compressed sensing, where one tries to recover a signal from non-linear measurements. This paper proposes a unified framework when the generative model is Lipschitz, which is a natural assumption. There are cases where previous results were not covering, e.g. Lipschitz generators and dithered 1-bit measurements, a very challenging case. Overall the paper is technically very strong and makes progress in the theory of compressed sensing with generative priors with complicated measurement models.  

The authors did a very good job in extensively answering questions of the reviewers, including providing corollaries that were not clearly stated in the paper. 

One reviewer raised several concerns about the limitation of the assumption that the signals indeed come from the generative model, but this is a standard assumption when developing theory in this space. Realizability is sensible to study if nothing has been known before for this type of measurement. Further the experimental evaluation is very limited in this paper as pointed out by reviewers. I still recommend that this paper is accepted since it makes serious project on a challenging and general inverse problem and the theoretical contributions are solid.
Decision: Accept (poster)