Robust One-Bit Recovery via ReLU Generative Networks

Jul 12, 2020



We study the robust one-bit compressed sensing problem whose goal is to design an algorithm that faithfully recovers any sparse target vector θ_0∈ℝ^d uniformly via m quantized noisy measurements. Specifically, we consider a new framework for this problem where the sparsity is implicitly enforced via mapping a low dimensional representation x_0 ∈^k through a known n-layer ReLU generative network G:ℝ^k→ℝ^d such that θ_0 = G(x_0). Such a framework poses low-dimensional priors on θ_0 without a known sparsity basis. We propose to recover the target G(x_0) solving an unconstrained empirical risk minimization (ERM). Under a weak sub-exponential measurement assumption, we establish a joint statistical and computational analysis. In particular, we prove that the ERM estimator in this new framework achieves a statistical rate of m=𝒪̃(kn log d /ε^2) recovering any G(x_0) uniformly up to an error ε. When the network is shallow (i.e., n is small), we show this rate matches the information-theoretic lower bound up to logarithm factors on ε^-1. 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 x_0 and its negative multiple. Furthermore, we show that the global minimizer of the empirical risk stays within the neighborhood around x_0 rather than its negative multiple under further assumptions on ReLU weights.



About ICML 2020

The International Conference on Machine Learning (ICML) is the premier gathering of professionals dedicated to the advancement of the branch of artificial intelligence known as machine learning. ICML is globally renowned for presenting and publishing cutting-edge research on all aspects of machine learning used in closely related areas like artificial intelligence, statistics and data science, as well as important application areas such as machine vision, computational biology, speech recognition, and robotics. ICML is one of the fastest growing artificial intelligence conferences in the world. Participants at ICML span a wide range of backgrounds, from academic and industrial researchers, to entrepreneurs and engineers, to graduate students and postdocs.

Store presentation

Should this presentation be stored for 1000 years?

How do we store presentations

Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%


Recommended Videos

Presentations on similar topic, category or speaker