{"id":"f95efe95-3bc7-4d2a-ab74-7493c06f5989","arxiv_id":"2412.19677","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"For deep ReLU networks with random Gaussian weights, the paper gives upper bounds on the layer expansion needed for injectivity and finds the expansion need saturates by four layers.","lead":"This paper derives statistical upper bounds on how many output neurons each layer of a deep ReLU network needs so that different inputs produce different outputs. It reports that after four layers, extra layers need almost no additional expansion, a pattern previously seen mainly in experiments.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 1 is the load-bearing step and its proof breaks: the support-size inequality |S0| <= min(|S1|,|S2|) in eq. (15) is false for generic A(2), so the rank bound (16) and all Table 1 upper bounds are unproven.","rationale":"The reader rejected the paper because the central equivalence between injectivity and the extended l0 spherical perceptron feasibility problem is not rigorously established, pointing to the rank bound and support-size inequality in Section 3. My stress-test agrees and sharpens the critique: eq. (15) is not merely unproven but false for generic A(2), as a simple support-counting example shows. This is the most load-bearing concern because every numerical capacity upper bound in Table 1, and the claimed expansion saturation effect, is derived through Lemma 1 and the subsequent RDT analysis; if the equivalence step is unsound, the numbers have no rigorous basis. I also note the weak-injectivity case has a separate dimensional difficulty: the proof uses |S0| >= 2n, while the weak sparsity condition only gives |S0| >= n. The paper itself acknowledges the results are strict upper bounds, but that acknowledgment does not repair the missing argument. The proposed concrete test directly checks whether the rank bound and cardinality inequality hold in a small random instance, which would settle whether the proof as written can support the central claim.","tokens_in":29490,"tokens_out":18148,"duration_ms":492054,"concrete_test":"Run a finite-dimensional numerical rank check of the matrix M in eq. (14). Take n=10, m1=67, m2=83 (so alpha1=6.7, alpha2=8.3), draw iid Gaussian A(1), A(2), and pick two random inputs xbar and x whose first-layer ReLU supports S1,S2 overlap in all but one coordinate. Let S0 be the positive coordinates of A(2)max(A(1)xbar,0); this typically has |S0| >= 2n. Compute rank(M). If rank(M) < 2n in any instance, eq. (16) is false and Lemma 1's proof cannot establish injectivity. Also directly tabulate (|S0|, min(|S1|,|S2|)) to verify that eq. (15) fails for generic draws.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central reduction is Lemma 1: 2-layer injectivity is claimed to follow from infeasibility of the sparse-output feasibility problem (11). The proof in Section 3, eqs. (12)-(16), asserts that for two colliding inputs the supports satisfy 2n <= |S0| <= min(|S1|,|S2|) (eq. (15)). The upper bound is not a consequence of the non-degenerative assumption. Since S0 is an index set of the second layer and S1,S2 index the first layer, ReLU can create more nonzero output coordinates than its input has. For example, with n=1, m1=2, A(1)=[1;-1]^T and x=1, the first-layer support is S1={1}; for iid Gaussian A(2) with m2=20, t=A(2)max(A(1)x,0)=A(2)_{:,1}, so |S0| is about m2/2 = 10 > |S1|=1. Thus eq. (15) is plainly false in generic settings. Consequently the claimed rank lower bound (16) does not follow: even when |S0| >= 2n, the two n-column blocks of the matrix in (14) can be linearly dependent when S1 and S2 overlap, and no genericity argument is given that forces the concatenated columns to have full rank 2n. Moreover, for the weak injectivity case actually used in Table 1, infeasibility of (11) with finj=f(w) only guarantees |S0| >= n, so the asserted rank >= 2n is dimensionally impossible. Since (16) is the only step excluding a nonzero collision vector in (14), the capacity values 8.267, 9.49, and 10.124 in Table 1 are not established by the presented argument. The later Gordon-theorem step cannot repair this gap because it assumes the injectivity-to-feasibility equivalence of Lemma 1.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies injectivity of deep ReLU networks in the proportional high-dimensional regime and claims an equivalence between l-layer ReLU injectivity and l-extended ℓ0 spherical perceptron feasibility (Eq. (9)). Building on this equivalence, the author develops a random-duality-theory (RDT) framework and reports weak injectivity capacity upper bounds in Table 1: 6.7004, 8.267, 9.49, and 10.124 for 1, 2, 3, and 4 layers, respectively, with per-layer expansions decreasing to about 1.07 by the fourth layer. The paper also introduces a partially lifted RDT variant and reports lowered 2-layer bounds in Tables 8 and 9.","tokens_in":29893,"tokens_out":5058,"duration_ms":45465,"significance":"If the central equivalence and the subsequent random-duality steps were rigorous, the quantitative capacity bounds and the observed expansion-saturation effect would constitute a substantial advance over trivial depth-multiplicative bounds such as 6.7^l. The paper is explicit about the numerical values of all RDT parameters and honestly distinguishes upper bounds from exact capacities; the lifted RDT computation is a useful methodological contribution. However, the load-bearing Lemma 1 is not proven, and the numerical tables inherit this gap. The significance of the work is therefore strictly conditional on repairing the proof of the injectivity-to-feasibility equivalence.","major_comments":[{"comment":"The support-size inequality |S0| ≤ min(|S1|,|S2|) in Eq. (15) is false in general. S0 indexes nonzero coordinates of the second-layer output, while S1 and S2 index nonzero coordinates of the first-layer output; ReLU can create more nonzero output coordinates than its input has. For example, with n=1, m1=2, A(1)=[1; -1] and x=1, one has S1={1}, but for a generic iid Gaussian A(2) with m2=20, |S0| is approximately 10, far exceeding |S1|=1. Thus Eq. (15) does not follow from the non-degenerative assumption, and the subsequent rank lower bound in Eq. (16) is not established.","section":"Section 3, Eq. (15)"},{"comment":"Even when |S0| ≥ 2n, the rank bound in Eq. (16) is not justified. The matrix in Eq. (14) contains the blocks A(2)_{S0,So} A(1)_{So,:} and -A(2)_{S0,So} A(1)_{So,:}, which are negatives of each other when S1 and S2 overlap, and no genericity argument is supplied to show that the full 2n-column concatenation has rank 2n. Since the existence of a nonzero collision vector [xbar; x] in Eq. (14) is excluded only by this rank bound, the claimed implication from infeasibility of (11) to injectivity is not proven.","section":"Section 3, Eqs. (14)–(16)"},{"comment":"For the weak injectivity case actually used in Table 1, infeasibility of (11) with finj=f(w) only guarantees |S0| ≥ n, not |S0| ≥ 2n. The rank bound in Eq. (16) requires the factor 2n, so the proof cannot establish weak injectivity from the stated feasibility problem. The capacity values 8.267, 9.49, and 10.124 in Tables 1, 2, 4, and 6 are therefore unsupported by the argument as written.","section":"Section 3, weak injectivity definition after Eq. (17)"},{"comment":"The proof of Theorem 1 is only a one-line reference to a two-fold application of Gordon's probabilistic comparison theorem. The functional in Eq. (21) contains max(z,0) inside the term y(2)^T A(2) max(z,0), so the Gaussian process is not linear in the optimization variable z; moreover z is coupled to A(1) through the constraint A(1)x=z. The proof does not verify that the comparison theorem applies to the resulting constrained, nonconvex min-max problem, nor does it identify the required Lipschitz or index-set conditions. The implication (φ0>0) ⇒ typical injectivity is therefore not established by the cited theorem.","section":"Section 3, Theorem 1 and Eq. (27)"},{"comment":"The deep capacity computation takes α1 = 6.7004 as an input, which the author's own reference [82] provides as an RDT-based upper bound (or a statistical-physics prediction). If α1 is not the exact minimally admissible value, then the recursively defined minimally admissible sequence in Eq. (8) is not being used; using a larger-than-minimal first-layer expansion can only make the second-layer injectivity easier, so the resulting values in Table 1 cannot be claimed as upper bounds for the minimally admissible sequence. The paper should state explicitly that the reported numbers are conditional on the exactness of the single-layer value α1=6.7004.","section":"Section 2.2 and Table 1; Eq. (8)"}],"minor_comments":[{"comment":"The notation frp(A1:2) in Eq. (55) should be frp(A1:3) to match the three-layer setup.","section":"Section 4.1, Lemma 2 and Eq. (55)"},{"comment":"In the proof of Theorem 2, the term described as corresponding to A(3) repeats the A(2) expression with max(z,0); it should involve max(t,0) and the appropriate h(3), g(3) variables.","section":"Section 4.1, proof of Theorem 2"},{"comment":"The chain in Eq. (22) equates injectivity with P(F is feasible) → 1; for injectivity one expects infeasibility of the collision problem. The displayed equality appears to have the feasibility direction reversed and should be corrected.","section":"Section 3, Eq. (22)"},{"comment":"There are numerous typographical errors, including 'evem', 'od', 'Lipshitzian', 'extened', 'forth' for fourth, and the comma-decimal confusion '3, 68' in Table 6. A careful proofreading pass is needed.","section":"Throughout"},{"comment":"The norm notation in the constraint on y(2) is typeset as '|y(2)‖_2 = 1/√n', with a stray pipe; this should be ‖y(2)‖_2 = 1/√n.","section":"Section 3, Eqs. (21) and (26)"}],"recommendation":"reject","confidential_remarks":"The manuscript's central claim rests on Lemma 1, whose proof contains a false support-cardinality inequality and a rank argument that is not valid for overlapping supports. The Gordon-theorem step is also invoked without verifying its hypotheses. These are load-bearing gaps that cannot be fixed by local rewording; the numerical results in Tables 1–9 would need to be recomputed under a corrected equivalence. I also note the heavy reliance on the author's own prior RDT papers, which makes independent verification harder; a revised submission should either supply a complete proof of the equivalence for a well-defined notion of injectivity or substantially narrow the claims to conditional bounds."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is about upper-bounding the injectivity capacity of deep ReLU networks using random duality theory. The genuinely new parts are the recursive extension of the single-layer ℓ0 spherical perceptron equivalence to l layers, and the numerical values that show a saturation effect: the per-layer expansion drops to about 1.07 by depth 4. That is an appealing observation and matches the empirical folklore from deep compressed sensing. The paper also gives concrete RDT parameters and is upfront that the results are upper bounds, not exact capacities.\n\nThe problem is the central reduction. Lemma 1 asserts that injectivity is equivalent to infeasibility of the feasibility problem (11), and the proof relies on the support-size inequality 2n ≤ |S0| ≤ min(|S1|,|S2|) in (15). That inequality is false. S0 is the support of the final ReLU output; for a dense Gaussian A(2), the output has about m2/2 nonzeros, which can be much larger than the first-layer support. Concretely, with n=1, m1=2, A(1)=[1;-1]^T and x=1, S1={1}, but a generic 20×2 A(2) gives |S0|≈10 > |S1|. So the cardinality bound used to justify the rank lower bound does not hold. Even if |S0|≥2n for strong injectivity, that doesn't force the support nesting, and the matrix in (14) may be rank deficient when S1 and S2 overlap; no genericity argument is given for that. For the weak injectivity case actually used in Table 1, infeasibility only gives |S0|≥n, making the claimed rank≥2n dimensionally impossible. The later Gordon-theorem step can't repair this because it assumes the equivalence of Lemma 1.\n\nThere is also a secondary issue: the deep computations take α1=6.7004 from the author's own [82] as input, so the upper-bound status is conditional on that single-layer value being exact. That is a smaller concern, but worth noting.\n\nNet: the framework is interesting and the saturation effect is intriguing, but the load-bearing proof is wrong. The paper needs a complete proof of Lemma 1 (or a different reduction) before the numerical results can be taken seriously. I'd send it to a referee only to document the gap; I would not accept it in current form.","headline":"The recursive RDT program and saturation numbers are interesting, but Lemma 1's proof breaks on a false support-size inequality, so the central equivalence and all Table 1 bounds are unproven.","tokens_in":30461,"tokens_out":4419,"would_cite":false,"duration_ms":39414,"reading_group":"no","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","60B20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Deep ReLU networks become injective once total width reaches about 10 times the input, and depth beyond four layers adds almost nothing.","keywords":["deep ReLU networks","injectivity capacity","ℓ0 spherical perceptron","random duality theory","expansion saturation","Gaussian random matrices","weak and strong injectivity","compressed sensing"],"falsifier":"Simulate a two-layer Gaussian ReLU network near the claimed threshold, for example with $\\alpha_1=6.7004$ and $\\alpha_2=8.0$, and check whether two distinct finite-dimensional inputs produce the same output with non-negligible probability; finding such collisions would falsify the claimed equivalence. A more direct check is to compute the rank of the matrix in equation (14) for overlapping support sets with $|S_0|=2n$: a positive-probability configuration with rank below $2n$ would break the proof's key step.","tokens_in":29205,"feed_emoji":"🧠","tokens_out":10211,"duration_ms":84883,"temperature":0.7,"pith_summary":"The paper asks how many outputs a deep ReLU network needs relative to its inputs before the map is one-to-one, so that every realizable output is produced by exactly one input. It claims that the answer for an $l$-layer network is the capacity of an $l$-extended $\\ell_0$ spherical perceptron, a random feasibility problem with sparse ReLU-type constraints. Using random duality theory, it derives upper bounds on this injectivity capacity for Gaussian weights: a one-layer network needs about 6.70 outputs per input, a two-layer network 8.27, a three-layer network 9.49, and a four-layer network 10.12. The added expansion per layer thus falls from 1.23 to 1.07, a rapid saturation effect that matches what practitioners see in deep compressed sensing. Because strong random duality is not established, the paper carefully presents these as upper bounds rather than exact capacities.","feed_headline":"10x width suffices to make 4-layer ReLU nets injective","feed_subtitle":"Per-layer expansion drops from 6.7 to about 1.07, matching what deep compressed sensing sees in practice.","key_machinery":"The load-bearing object is the random-dual function $\\varphi_0$ (and its lifted counterpart $\\bar{\\varphi}_0$), a scalar quantity built from independent Gaussian vectors that lower-bounds the minimax objective of the feasibility problem. Its sign decides the issue: positivity of $\\varphi_0$ means the sparse-output feasibility problem is infeasible, which in turn means the ReLU network is typically injective. The machinery around it consists of a Gaussian comparison theorem that replaces the random matrices $A^{(i)}$ by Gaussian vectors, a Lagrangian reformulation of the sparse cardinality constraint, and the square-root trick that turns the resulting quadratic terms into one-dimensional Gaussian integrals. The optimized scalar integrals $f_{q,1}$ and $f_{q,2}$ are what the numerical tables actually evaluate to locate the zero of $\\varphi_0$.","core_discovery":"The paper's central claim is that injectivity of an $l$-layer ReLU network is equivalent to infeasibility of an $l$-extended $\\ell_0$ spherical perceptron. For two layers, the feasibility problem asks for a unit-norm $x$ satisfying $A^{(1)}x=z$, $A^{(2)}\\max(z,0)=t$, and $\\|\\max(t,0)\\|_0<2n$ (or $