Robust One-Bit Recovery via ReLU Generative Networks: Improved Statistical Rates and Global Landscape Analysis
We study the robust one-bit compressed sensing problem whose goal is to design an algorithm that faithfully recovers any sparse target vector θ0 ∈ R uniformly from m quantized noisy measurements. Under the assumption that the measurements are sub-Gaussian, to recover any k-sparse θ0 (k d) uniformly up to an error ε with high probability, the best known computationally tractable algorithm requires1 m ≥ Õ(k log d/ε). In this paper, we consider a new framework for the onebit sensing problem where the sparsity is implicitly enforced via mapping a low dimensional representation x0 through a known n-layer ReLU generative network G : R → R. Such a framework poses low-dimensional priors on θ0 without a known basis. We propose to recover the target G(x0) via an unconstrained empirical risk minimization (ERM) problem under a much weaker sub-exponential measurement assumption. For such a problem, we establish a joint statistical and computational analysis. In particular, we prove that the ERM estimator in this new framework achieves an improved statistical rate of m = Õ(kn log d/ ) recovering any G(x0) uniformly up to an error ε. Moreover, from the lens of computation, we prove that under proper conditions on the ReLU weights, our proposed empirical risk, despite non-convexity, has no stationary point outside of small neighborhoods around the true representation x0 and its negative multiple. Furthermore, we show that the global minimizer of the empirical risk stays within the neighborhood around x0 rather than its negative multiple. Our analysis sheds some light on the possibility of inverting a deep generative model under partial and quantized measurements, complementing the recent success of using deep generative models for inverse problems.