The Generalized Lasso with Nonlinear Observations and Generative Priors

In this paper, we study the problem of signal estimation from noisy non-linear measurements when the unknown n-dimensional signal is in the range of an L-Lipschitz continuous generative model with bounded k-dimensional inputs. We make the assumption of sub-Gaussian measurements, which is satisfied by a wide range of measurement models, such as linear, logistic, 1-bit, and other quantized models. In addition, we consider the impact of adversarial corruptions on these measurements. Our analysis is based on a generalized Lasso approach (Plan and Vershynin, 2016). We first provide a non-uniform recovery guarantee, which states that under i.i.d. Gaussian measurements, roughly O k ǫ 2 log L samples suffice for recovery with an ℓ 2 -error of ǫ, and that this scheme is robust to adversarial noise. Then, we apply this result to neural network generative models, and discuss various extensions to other models and non-i.i.d. measurements. Moreover, we show that our result can be extended to the uniform recovery guarantee under the assumption of a so-called local embedding property, which is satisfied by the 1-bit and censored Tobit models. Despite the far-reaching utility of standard CS, in many real-world applications the assumption of a linear model is too restrictive. To address this problem, the semi-parametric single index model (SIM) is considered in various papers [10, 25, 26] : where f : R → R is an unknown (possibly random) function that is independent of a i . In general, f plays the role of a nonlinearity, and we aim to estimate the signal x * despite this unknown nonlinearity. Note that the norm of x * is sacrificed in SIM, since it may be absorbed into the unknown function f . Hence, for simplicity of presentation, we assume that x * is a unit vector in R n . In this 34th Conference on Neural Information Processing Systems (NeurIPS 2020), Vancouver, Canada. paper, similar to that in [26], we make the assumption that the random variables y i are sub-Gaussian; see Section 2.2 for several examples. In addition, to further strengthen the robustness guarantees, we also allow for adversarial noise. That is, we consider the case of corrupted observations ỹ that can be produced from y in an arbitrary manner (possibly depending on A) subject to an ℓ 2 -norm constraint. Motivated by the tremendous success of deep generative models in abundance of real applications [8] , a new perspective of CS has recently emerged, in which the assumption that the underlying signal can be well-modeled by a (deep) generative model replaces the common sparsity assumption [2] . In addition to the theoretical developments, existing works have presented impressive numerical results for CS with generative models, with large reductions (e.g., a factor of 5 to 10) in the required number of measurements compared to sparsity-based methods [2] . Related Work In this subsection, we provide a summary of some relevant existing works. These works can roughly be divided into (i) CS with generative models, and (ii) SIM without generative models. CS with generative models: Bora et al. [2] show that for an L-Lipschitz continuous generative model with bounded k-dimensional inputs, roughly O(k log L) random Gaussian linear measurements suffice for an accurate recovery. The analysis in [2] is based on the K-Lasso (2), as well as showing that a natural counterpart to the Restricted Eigenvalue Condition (REC), termed the Set-REC (S-REC), is satisfied by Gaussian measurement matrices. Extensive experimental results for the K-Lasso have been presented in [2] in the case of linear measurements. Follow-up works of [2] provide certain additional algorithmic guarantees [5, 13, 23, 28] , as well as information-theoretic lower bounds [15, 18] . 1-bit CS with generative models has been studied in various recent works [17, 27] . In [27] , the authors study robust 1-bit recovery for d-layer, w-width ReLU neural network generative models, and the dithering technique [6, 14, 16, 40] is used to enable the estimation of the norm. It is shown that roughly O kd ǫ 2 log w sub-exponential measurements guarantee the uniform recovery 1 of any signal in the range of the generative model up to an ℓ 2 -error of ǫ. These results do not apply to general nonlinear measurement models, and the authors only consider ReLU neural networks with no offsets, rather than general deep generative models. In addition, the algorithm analyzed is different to the K-Lasso.