The goal of standard compressive sensing is to estimate an unknown vector from linear measurements under the assumption of sparsity in some basis. Recently, it has been shown that significantly fewer measurements may be required if the sparsity assumption is replaced by the assumption that the unknown vector lies near the range of a suitably-chosen generative model.   In particular, in (Bora {\em et al.}, 2017) it was shown that roughly $O(k\log L)$ random Gaussian measurements suffice for accurate recovery when the $k$-input generative model is bounded and $L$-Lipschitz, and that $O(kd \log w)$ measurements suffice for $k$-input ReLU networks with depth $d$ and width $w$.  In this paper, we establish corresponding algorithm-independent lower bounds on the sample complexity using tools from minimax statistical analysis.   In accordance with the above upper bounds, our results are summarized as follows: (i) We construct an $L$-Lipschitz generative model capable of generating group-sparse signals, and show that the resulting necessary number of measurements is $\Omega(k \log L)$; (ii) Using similar ideas, we construct two-layer ReLU networks of high width requiring $\Omega(k \log w)$ measurements, as well as lower-width deep ReLU networks requiring $\Omega(k d)$ measurements.   As a result, we establish that the scaling laws derived in (Bora {\em et al.}, 2017) are optimal or near-optimal in the absence of further assumptions. The problem of sparse estimation via linear measurements (commonly referred to as compressive sensing) is well-understood, with theoretical developments including sharp performance bounds for both practical algorithms [1, 2, 3, 4] and (potentially intractable) information-theoretically optimal algorithms [5, 6, 7, 8] . Following the tremendous success of deep generative models in a variety of applications [9] , a new perspective on compressive sensing was recently introduced, in which the sparsity assumption is replaced by the assumption of the underlying signal being well-modeled by a generative model (typically corresponding to a deep neural network) [10] . This approach was seen to exhibit impressive performance in experiments, with reductions in the number of measurements by large factors such as 5 to 10 compared to sparsity-based methods. In addition, [10] provided theoretical guarantees on their proposed algorithm, essentially showing that an L-Lipschitz generative model with bounded k-dimensional inputs leads to reliable recovery with m = O(k log L) random Gaussian measurements (see Section 2 for a precise statement). Moreover, for a ReLU network generative model from R k to R n with width w and depth d, it suffices to have m = O(kd log w). A variety of follow-up works provided additional theoretical guarantees (e.g., for more specific optimization algorithms [11, 12] , more general models [13] , or under random neural network weights [14, 15] ) for compressive sensing with generative models, but the main results of [10] are by far the most relevant to ours. In this paper, we address a prominent gap in the existing literature by establishing algorithmindependent lower bounds on the number of measurements needed (e.g., this is explicitly posed as an open problem in [15] ). Using tools from minimax statistical analysis, we show that for generative models satisfying the assumptions of [10] , the above-mentioned dependencies m = O(k log L) and m = O(kd log w) cannot be improved (or in the latter case, cannot be improved by more than a log n factor) without further assumptions. Our argument is essentially based on a reduction to compressive sensing with a group sparsity model (e.g., see [16] ), i.e., forming a neural network that is capable of producing such signals. The proofs are presented in the full paper [17] . We have established, to our knowledge, the first lower bounds on the sample complexity for compressive sensing with generative models. To achieve these, we constructed generative models capable of producing group-sparse signals, and then applied a minimax lower bound for group-sparse recovery. For bounded Lipschitz-continuous generative models we matched the O(k log L) scaling law derived in [10] , and for ReLU-based generative models, we showed that the dependence of the O(kd log w) bound from [10] has an optimal or near-optimal dependence on both the width and depth. A possible direction for future research is to understand what additional assumptions could be placed on the generative model to further reduce the sample complexity.
We establish that the scaling laws derived in (Bora et al., 2017) are optimal or near-optimal in the absence of further assumptions.
{"src": "scitldr-AIC_train", "paper_id": "SJgYiQnq8H"}