{"id":"776beb6d-60f2-49ee-8122-203ca14dd5b8","arxiv_id":"1908.10744","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":4,"one_line_summary":"Generative-model compressed sensing requires at least Ω(k log L) measurements for L-Lipschitz models and Ω(kd log w / log n) for ReLU networks, matching prior upper bounds up to small gaps.","lead":"This paper proves information-theoretic lower bounds for compressed sensing with generative models, showing that the measurement counts previously known to be sufficient are also necessary in the worst case. It constructs specific generative models, including ReLU networks, that make the lower bounds tight.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 7's amplitude ξ is off by a factor √k0: substituting m* into Lemma 2 gives ξ=Θ(√(α/(k k0))), not Θ(√(α/k)); with the stated ξ the Fano argument is vacuous for large k0.","rationale":"Theorems 3 and 4 appear sound: the Lipschitz constant calculation in Lemma 1, the reduction through Lemma 2, and the extension to spherical domains are consistent, and the stated L-threshold assumption is a genuine but disclosed condition. The upper-bound comparisons in Corollaries 1 and 2 are also reasonable. The problem is isolated to Theorem 7, which is central to the paper's ReLU claims. Its proof invokes Lemma 2 with group count K=kk0 but then states ξ = Θ(√(α/k)); a direct substitution of the chosen m* into Lemma 2 gives ξ² = Θ(α/(k k0)). With the larger stated ξ, the Fano mutual-information-to-log-volume ratio scales with k0, so the proof's lower bound becomes vacuous in the large-k0 regime that the theorem is designed to capture. This is not merely a cosmetic typo: the lower bound m = Ω(kk0 log(n/(kk0))) depends on the hard-signal amplitude being at the noise level, Θ(√(α/(k k0))). If corrected, the theorem and its consequences likely survive, and the paper's main scaling conclusions would be unchanged. For that reason a reject is not warranted, but the theorem statement and proof need a clear correction before the ReLU lower bound can be accepted as stated. I therefore recommend CONDITIONAL rather than UNCHANGED.","tokens_in":19337,"tokens_out":31490,"duration_ms":345105,"concrete_test":"Perform the substitution in the proof of Theorem 7 with K=kk0: plug σ²=α/m and ||A||²_F=C_A n into Lemma 2's formula ξ² = nσ² log(n/K)/(4||A||²_F), then set m=m* = floor(K log(n/K)/(64C1C_A)). If the resulting ξ² is Θ(α/(k k0)) rather than Θ(α/k), the theorem statement is algebraically inconsistent. Then check whether the recursive construction of Section IV-B can realize signals of magnitude ξ' = Θ(√(α/(k k0))) with all kk0 blocks nonzero; if no such z exists, the hard subset used for the Fano argument is not contained in Range(G), so Theorem 7 as stated is unproved.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The most load-bearing issue is in the proof of Theorem 7, the ReLU-network lower bound. Lemma 2, applied with K=kk0 groups and ||A||²_F=C_A n, requires the hard-signal amplitude to satisfy ξ² = nσ² log(n/K)/(4||A||²_F) = α log(n/K)/(4C_A m). In the proof, m* is the largest integer below K log(n/K)/(64C1C_A). Substituting m* gives ξ² ≈ 16C1α/K = Θ(α/(k k0)), not Θ(α/k). The theorem instead states ξ = √(C2 α/k), which is larger by a factor √k0 and is not Θ(1) in k0. With the stated ξ, the mutual information bound used in Lemma 2, I(V;y) ≤ ξ²/(2σ²)·(K/n)||A||²_F, grows like C2 C_A m k0/2; at m ≈ m* the Fano ratio I/((K/3) log(n/K)) scales as Θ(k0), so the lower bound in (32)–(35) is vacuous for large k0. Thus the proof as written does not establish the theorem's first claim for its stated parameter ξ. Either ξ should be Θ(√(α/(k k0))) and the theorem statement corrected, or the proof must exhibit a subset of Range(G) at the smaller amplitude; the recursive pulse construction of Section IV-B does not obviously provide such a subset, since the pulses have fixed amplitude ξ on their defining intervals.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper establishes algorithm-independent lower bounds on the number of measurements for compressive sensing with generative models. It constructs an explicit L-Lipschitz generative model whose range contains k-group-sparse signals, and combines this with a minimax lower bound for group-sparse recovery (Lemma 2) to show that, in a no-representation-error, no-optimization-error Gaussian-noise setting, any estimator with expected squared error O(alpha) needs m = Omega(k log L) measurements for both rectangular and spherical input domains (Theorems 3 and 4). These match the upper bounds of Bora et al. up to constants. For ReLU-network generative models, the paper constructs a more complex (k k0)-group-sparse signal generator and claims lower bounds that depend on depth and width (Theorem 7), showing the O(kd log w) upper bound is optimal or near-optimal in various regimes. The proofs are based on Fano-type inequalities; the main auxiliary result, Lemma 2, is proved in Appendix B, with a self-contained derivation of the mutual information bound and the covariance of the group-sparse prior.","tokens_in":19762,"tokens_out":16136,"duration_ms":149574,"significance":"If correct, the paper fills an important gap in the theory of compressive sensing with deep generative priors by showing that the sample-complexity scaling laws of Bora et al. cannot be improved without further assumptions. The Lipschitz lower bound construction is explicit, elementary, and directly matches the covering-number-based upper bound. The group-sparse minimax bound in Lemma 2 is carefully proved in an appendix, and the reciprocity between the constructed generative model and the group-sparse hard instance is transparent. These contributions are likely to become a standard reference for lower bounds in this area.","major_comments":[{"comment":"In the proof of Theorem 7, Lemma 2 is applied with K = k k0 groups, sigma^2 = alpha/m, and ||A||_F^2 = C_A n. Lemma 2 requires the hard-signal amplitude to satisfy xi^2 = n sigma^2 log(n/K)/(4||A||_F^2) = alpha log(n/K)/(4 C_A m). With m = m* chosen as the largest integer below K log(n/K)/(64 C1 C_A), this yields xi^2 = Theta(alpha/(k k0)), not Theta(alpha/k). The theorem instead states xi = sqrt(C2 alpha/k), which is a factor sqrt(k0) larger. For the stated xi, the mutual information bound I(V;y) <= xi^2/(2 sigma^2) * (K/n)||A||_F^2 becomes Theta(k0) times the term (K/3) log(n/K) in the denominator of the Fano lower bound in (32)-(35), so the bound is vacuous for large k0. Thus the proof as written does not establish the first claim of Theorem 7 for its stated parameter xi. The theorem should either be corrected to xi = Theta(sqrt(alpha/(k k0))) with a suitable constant, or the proof must exhibit a hard subset of Range(G) at the smaller amplitude; the recursive pulse construction of Section IV-B does not obviously provide such a subset, since the pulses are defined with fixed amplitude xi on their respective intervals. This is a load-bearing gap in the main ReLU lower bound.","section":"Section IV-B (Theorem 7) and Appendix B (Lemma 2)"}],"minor_comments":[{"comment":"In the abstract, the phrase 'ReLU networks with high depth and/or high depth' should be 'with high depth and/or high width'; this appears to be a typographical error.","section":"Abstract"},{"comment":"After setting C' = 1/sqrt(128 C1), the text says (21) reduces to m >= 1/(128 C' C_A) k log(n/k); substituting C' gives 1/(128 C1 C_A) k log(n/k), so the printed denominator appears to have a typographical error, replacing C1 with C'.","section":"Proof of Theorem 3"},{"comment":"The statement 'depth O(log n/(kr))' is ambiguous; it should read O(log(n/(kr))) to clearly indicate the logarithm of the ratio.","section":"Theorem 6"},{"comment":"The claim that the width is a constant multiple of the number of outputs, w = O(n), would benefit from a brief justification that each of the n parallel outputs can be realized with O(1) width and the specified depth using the sawtooth construction.","section":"Proof of Theorem 7, part (b)"}],"recommendation":"major_revision","confidential_remarks":"The error in the amplitude parameter in Theorem 7 is clear and load-bearing, but it appears local and fixable by restating xi as Theta(sqrt(alpha/(k k0))). Once corrected, the main ReLU lower bound should go through, and the rest of the paper is well supported. I would also ask the authors to fix the typo in the C' substitution in the proof of Theorem 3. The contribution is significant and worth pursuing through a revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know. First, the paper gives the first algorithm-independent lower bounds for compressive sensing with generative models, and the Lipschitz part is solid: the group-sparse hard-instance construction is elegant and the minimax argument checks out. Second, the ReLU-network result in Theorem 7 has a real bug in the proof as written. The stated amplitude ξ = Θ(√(α/k)) is too large by a factor √k0. Substituting the chosen m* into Lemma 2 (with K = kk0) yields ξ = Θ(√(α/(k k0))), not Θ(√(α/k)). With the larger ξ, the Fano ratio I/((K/3) log(n/K)) scales like Θ(k0) at m ≈ m*, so the lower bound becomes vacuous for large k0. This isn't a cosmetic typo: the proof explicitly claims the substitution gives the stated behavior. The fix is local — set ξ = Θ(√(α/(k k0))) and the Fano argument goes through unchanged, giving the same Ω(k k0 log(n/(k k0))) lower bound. The pulse construction still works at that smaller amplitude. So the theorem's conclusion likely stands, but a referee needs to require the correction.\n\nWhat the paper does well: the construction of an L-Lipschitz generative model that encodes group sparsity, the exact Lipschitz calculation, and the careful reduction to known minimax bounds are all clean. The spherical-domain extension via the largest inscribed ∞-ball is crude but works, and they explain why. They also acknowledge the concurrent work by Kamath et al., and they are upfront about the log n gap in the ReLU lower bound.\n\nSoft spots in proportion: the scope is the narrowly specialized setting of Corollaries 1-2 (no representation error, exact optimization, Gaussian noise), and the Lipschitz results need L above a small threshold; the paper states both clearly. The self-cited mutual-information bound in Appendix B is standard. These are minor.\n\nWho it's for: anyone building on Bora et al. or working on minimax sample complexity for structured priors. It deserves a serious referee. My recommendation: send to peer review; accept after the Theorem 7 amplitude correction. The bug is load-bearing for that proof as written, but it is clearly fixable and the main contribution is sound.","headline":"Solid first lower bounds for generative-model CS, but Theorem 7's proof has a real amplitude error that needs fixing.","tokens_in":20239,"tokens_out":5506,"would_cite":true,"duration_ms":52240,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A12","62C20","68T07"],"pacs":[],"model":"deepseek-v4-flash","headline":"For compressive sensing with Lipschitz generative models, $m = \\Omega(k \\log L)$ measurements are information-theoretically unavoidable.","keywords":["compressive sensing","generative models","information-theoretic lower bounds","sample complexity","group sparsity","minimax risk","ReLU networks","Lipschitz continuity"],"falsifier":"Instantiate the paper's double-triangular generative model with the prescribed parameters and compute the minimax risk over its range for a number of measurements $m$ below the claimed bound; if any estimator achieves average squared error $O(\\alpha)$ on that constructed group-sparse signal set, then Lemma 2 would be false and the lower bound would collapse.","tokens_in":19172,"feed_emoji":"📉","tokens_out":8400,"duration_ms":74793,"temperature":0.7,"pith_summary":"This paper asks how many noisy linear measurements are truly needed to recover a signal known to lie near the range of a generative model. The authors prove algorithm-independent lower bounds: no estimator, however computationally powerful, can achieve squared error of order $\\alpha$ unless the number of measurements is $\\Omega\\big(k \\log \\frac{L r}{\\sqrt{\\alpha}}\\big)$ for spherical input domains, and $\\Omega\\big(k \\log \\frac{L r \\sqrt{k}}{\\sqrt{\\alpha}}\\big)$ for rectangular domains, where $k$ is the latent dimension and $L$ is the Lipschitz constant. For generative models implemented by ReLU networks with depth $d$ and width $w$, the necessary measurement count is $\\Omega\\big(k d \\frac{\\log w}{\\log n}\\big)$ in general, and $\\Omega(k d \\log w)$ in some regimes. These bounds match, up to constants or logarithmic factors, the previously known upper bounds from [14], so the existing scaling laws cannot be improved without additional assumptions. The proof works by constructing a simple Lipschitz or ReLU generative model that can generate group-sparse signals, then invoking minimax lower bounds for group-sparse recovery.","feed_headline":"No algorithm beats k log L measurements for generative-model sensing","feed_subtitle":"Lower bounds show these generative-model sensing laws are optimal or near-optimal.","key_machinery":"The load-bearing object is a specially designed generative model that reduces the general problem to group-sparse recovery. For the Lipschitz case, the model divides the output into $k$ blocks and maps each scalar input $z_i$ through a double-triangular waveform into one block, so that exactly one entry per block is nonzero; its Lipschitz constant is $L = \\frac{2 n x_{\\max}}{k r}$. The argument then applies a minimax lower bound for estimating $k$-group-sparse signals from Gaussian measurements, obtained via a distance-based Fano inequality. The proof chooses the amplitude $x_{\\max}$ and the output dimension $n$ so that the hard signal set fits inside the model range while the Lipschitz constraint is respected, forcing $m = \\Omega\\big(k \\log \\frac{n}{k}\\big)$, which translates into the stated $k \\log L$ bound. For ReLU networks, the same group-sparse signals are generated using recursive sawtooth and trapezoidal constructions, and standard ReLU implementation results control the width and depth, producing the stated depth/width dependence.","core_discovery":"The central discovery is that the sample-complexity scaling established in [14] for compressive sensing with generative models is not an artifact of any particular algorithm: it is an information-theoretic requirement. For bounded $L$-Lipschitz generative models with $k$-dimensional inputs, the paper constructs a generative model whose range consists of $k$-group-sparse signals, built from blockwise double-triangular scalar mappings. A minimax lower bound for group-sparse recovery then implies that any algorithm achieving average squared error $O(\\alpha)$ in the idealized no-representation-error, no-optimization-error, i.i.d. Gaussian-noise setting needs $m = \\Omega\\big(k \\log \\frac{L r \\sqrt{k}}{\\sqrt{\\alpha}}\\big)$ measurements for rectangular domains and $m = \\Omega\\big(k \\log \\frac{L r}{\\sqrt{\\alpha}}\\big)$ for spherical domains. For ReLU networks, a recursive construction generates $(k k_0)$-group-sparse signals and yields a necessary measurement count of $\\Omega\\big(k k_0 \\log \\frac{n}{k k_0}\\big)$, which specialises to $\\Omega\\big(k d \\frac{\\log w}{\\log n}\\big)$ in general and $\\Omega(k d \\log w)$ in some regimes, matching the $O(k d \\log w)$ upper bound up to a log factor or exactly. The lower bounds hold for every fixed measurement matrix with normalized Frobenius norm, so the bottleneck is intrinsic to the model class itself.","pith_inferences":["I read this result as a warning that worst-case Lipschitz generative priors have fundamentally limited sample efficiency; the empirical gains seen with generative priors may therefore rely on real signal distributions being far better than the worst case.","A natural testable extension would be to check whether natural image priors avoid the adversarial geometry of the constructed group-sparse model by attempting recovery with fewer than $k \\log L$ measurements on realistic datasets.","The paper leaves open whether the extra $\\log n$ factor in the general ReLU lower bound can be removed by sharper constructions; closing that gap would settle the exact constant-order sample complexity for deep generative models.","The same group-sparse reduction technique could plausibly be applied to other generative-model inverse problems, such as phase retrieval or non-Gaussian measurement models, to see whether the same scaling laws survive."],"forward_implications":["The known upper bounds for Lipschitz generative models are tight up to constants in the idealized setting, so any further reduction in measurements must come from extra assumptions beyond Lipschitzness and bounded inputs.","For ReLU-network generative models, the $O(k d \\log w)$ upper bound is optimal or near-optimal; in particular, the depth-2 high-width construction gives a regime with matching scaling up to mild logarithmic terms.","The lower bounds hold for any algorithm and any fixed measurement matrix with normalized Frobenius norm, meaning the sample-complexity bottleneck is a property of the model class, not of specific recovery procedures.","Because the proof uses a hard prior distribution over signals, the same lower bound applies even to average-case recovery guarantees over that prior, strengthening the impossibility result.","If one wants fewer measurements, one must impose structure beyond the Lipschitz or ReLU architectural assumptions, such as distributional or weight-based assumptions, since the model classes considered here alone do not lower the information-theoretic cost."],"supporting_citations":[{"why":"Supplies the upper bounds and problem setup whose optimality is established, including the $O(k \\log L)$ and $O(k d \\log w)$ measurement guarantees.","marker":"[14]"},{"why":"Provides the sparse-recovery minimax technique that is adapted here to prove the group-sparse lower bound of Lemma 2.","marker":"[11]"},{"why":"Supplies the distance-based Fano inequality used as the general-purpose minimax lower bound in Lemma 4.","marker":"[24]"},{"why":"Gives the Gaussian-noise mutual information bound used to control $I(V; y)$ in the proof of Lemma 2.","marker":"[34]"},{"why":"Establishes that piecewise-linear functions can be implemented by a depth-2 ReLU network, used in the width-based part of Theorem 7.","marker":"[30]"},{"why":"Shows the sawtooth function can be implemented with bounded width and logarithmic depth, used to generate pulses for the ReLU construction.","marker":"[31]"},{"why":"Provides depth-width tradeoffs for ReLU networks, supporting the combined depth/width case in Theorem 7(c).","marker":"[32]"},{"why":"Concurrent work that independently proves a closely related Lipschitz lower bound; the paper contrasts the noise and representation-error settings.","marker":"[23]"}],"fun_headline_variants":["Lower bounds prove generative sensing needs Ω(k log L) measurements","Generative sensing: lower bounds match known upper bounds","No algorithm can improve on k log L for generative-model sensing","Information-theoretic limits: generative sensing needs Ω(k log L)","Minimax lower bounds show generative sensing laws are tight"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The lower bounds hold only in the idealized setting where the signal lies exactly in the model range, optimization error is zero, and the noise is i.i.d. Gaussian, and the Lipschitz results additionally require the Lipschitz constant $L$ to be above a stated threshold relative to $\\alpha$, $k$, and $r$; below that threshold the problem can become trivial and the bounds do not apply.","fun_headline_variants_meta":{"raw":{"variants":["Lower bounds prove generative sensing needs Ω(k log L) measurements","Generative sensing: lower bounds match known upper bounds","No algorithm can improve on k log L for generative-model sensing","Information-theoretic limits: generative sensing needs Ω(k log L)","Minimax lower bounds show generative sensing laws are tight"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000904,"raw_usage":{"total_tokens":3982,"prompt_tokens":1128,"completion_tokens":2854,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":744,"completion_tokens_details":{"reasoning_tokens":2771}},"tokens_in":744,"tokens_out":2854,"duration_ms":19639,"temperature":1.0,"reasoning_tokens":2771,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:37:43.879911+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Instantiate the paper's double-triangular generative model with the prescribed parameters and compute the minimax risk over its range for a number of measurements $m$ below the claimed bound; if any estimator achieves average squared error $O(\\alpha)$ on that constructed group-sparse signal set, then Lemma 2 would be false and the lower bound would collapse.","supporting_citations":[{"cited_title":"Compressed sensing using generative models,","cited_arxiv_id":null,"evidence_quote":"Supplies the upper bounds and problem setup whose optimality is established, including the $O(k \\log L)$ and $O(k d \\log w)$ measurement guarantees."},{"cited_title":"How well can we estimate a sparse vector?","cited_arxiv_id":null,"evidence_quote":"Provides the sparse-recovery minimax technique that is adapted here to prove the group-sparse lower bound of Lemma 2."},{"cited_title":"Understanding deep neural networks with rectified linear units,","cited_arxiv_id":null,"evidence_quote":"Establishes that piecewise-linear functions can be implemented by a depth-2 ReLU network, used in the width-based part of Theorem 7."},{"cited_title":"Benefits of depth in neural networks,","cited_arxiv_id":null,"evidence_quote":"Provides depth-width tradeoffs for ReLU networks, supporting the combined depth/width case in Theorem 7(c)."},{"cited_title":"Lower Bounds for Compressed Sensing with Generative Models","cited_arxiv_id":"1912.02938","evidence_quote":"Concurrent work that independently proves a closely related Lipschitz lower bound; the paper contrasts the noise and representation-error settings."}],"review_version":1}