{"id":"08dc4cb2-7d69-4322-8cba-0ace1d92b752","arxiv_id":"2506.12613","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Using isoperimetric inequalities on SO(d), this paper proves that random convolutional networks with odd activations or ReLU have sign-flipping adversarial examples at distance O(||x0||/sqrt(d)).","lead":"Random convolutional networks, including ReLU networks of any constant depth, provably have adversarial examples: for any fixed input, a tiny perturbation flips the network's output sign with high probability. The proof uses measure concentration on the rotation group SO(d), extending and simplifying earlier results for fully connected networks.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.2 rests on an unproved extension of the kernel approximation Lemma 6.6 from fully connected networks to convolutional ones; Theorem 3.1 itself is not affected.","rationale":"The reader's weakest-assumption analysis identifies precisely the same load-bearing concern: Lemma 6.6 is cited from [8] and its extension to convolutional patch-averaged kernels is not demonstrated. My reading of the manuscript confirms that Lemma 6.4, the only source of the separation constant β feeding the Sudakov argument in Lemma 6.5, relies entirely on that kernel approximation. Theorem 3.1, by contrast, is self-contained: it uses odd activations, the SO(d)-invariance of regular convolutional first layers, and the isoperimetric inequality on SO(d), none of which require Lemma 6.6. Thus the central isoperimetric insight is sound, and the first main theorem appears correct. The conditional verdict is therefore appropriate: the paper should not be rejected, but Theorem 3.2 should not be accepted as fully proved until the convolutional kernel approximation is supplied. Since the reader already gave a conditional verdict, my stress-test does not change the verdict.","tokens_in":10988,"tokens_out":10214,"duration_ms":122929,"concrete_test":"Independently re-derive Lemma 6.6 in the simplest nontrivial convolutional case: l=2, one Xavier convolutional ReLU layer followed by a linear readout, with width w, stride s, and d input dimension. For a fixed input pair, compute Cov(ReLU(Wu), ReLU(Wv)) under Xavier W and check whether it equals d₂ · σ̂( (1/w) Σ_r ⟨x_r, y_r⟩/d ) plus o(1) uniformly over overlapping patches. If the derivation requires w=n (fully connected) or fails to handle weight sharing, then Lemma 6.4 is unsupported. Confirm with a numerical check at d=10^3, w=5, n=10, d₂=10^3: if ⟨Ψ(x), Ψ(y)⟩ − k(x,y) is not o(1), Theorem 3.2 is not established.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step in Theorem 3.2 is Lemma 6.4, which guarantees that the m rotated inputs are separated in the penultimate feature space by a constant β. Lemma 6.4 is derived entirely from Lemma 6.6, which is stated as a citation to [8] and asserts that for random convolutional ReLU networks, ⟨Ψ(x), Ψ(y)⟩ ≈ k(x,y) for the patch-averaged recursive kernel defined in §6.1.1. The cited source [8] proves a kernel approximation for fully connected networks; the text gives no proof that the result extends to convolutional layers with shared weights, overlapping patches, and stride. This is not a cosmetic gap: a convolutional layer applies the same random matrix to many overlapping patches, creating cross-position dependencies that are absent in the fully connected case, and the recursive kernel k_{v,t} averages over w_v adjacent entries. The proof of Lemma 6.4 also needs a uniform statement over all m² pairs, with the required width scaling and o_d(1) failure probability, but Lemma 6.6 as stated is pointwise and the union bound is not supplied. Additionally, the definition of k_{l,1} for the final linear layer is ambiguous: it is unclear whether the final layer has width n_{l-1}, whether the σ̂ nonlinearity is applied at v=l, and how the summation over spatial positions enters the kernel. Since Lemma 6.5's Sudakov argument needs a positive separation β, failure of the convolutional kernel approximation would collapse the balance lemma and with it Theorem 3.2. Theorem 3.1 uses only odd activations and the isoperimetric SO(d) framework, so it stands independently of this gap.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proves two existence results for adversarial perturbations of random convolutional networks. Theorem 3.1 covers networks whose first layer is a regular random convolutional layer and all activations are odd; it shows that for even d, with probability at least 1 - 2e^{-τ^2/32}, either f(x0) = 0 or a sign-flipping perturbation exists of radius (τ/√(d-2))·(||x0||_sp/||x0||)·||x0||. Theorem 3.2 extends this to constant-depth convolutional Xavier ReLU networks under width and channel counts that are ω(log(nd)). The method reduces the problem to concentration of measure: SO(d)-invariant and balanced random functions on an SO(d)-metric space necessarily have adversarial examples, by an isoperimetric inequality. The odd-activation case follows from the balance of odd functions and the metric-space isoperimetric theorem. The ReLU case requires a separate balance lemma, proved by taking m ≈ √log d random rotations, showing the final layer separates them via Sudakov's inequality, and using a kernel approximation result to control the penultimate feature inner products.","tokens_in":11318,"tokens_out":5053,"duration_ms":61269,"significance":"The isoperimetric reduction is conceptually appealing, and Theorem 3.1 is essentially self-contained: its proof uses only the SO(d)-concentration inequality, the Lipschitz bound of Lemma 4.3, and the elementary balance of odd activations. The perturbation radius matches known fully connected results and the argument contains no fitted parameters, which is a genuine strength. However, Theorem 3.2 is not established in the submitted form: the key kernel approximation, Lemma 6.6, is cited from prior work on fully connected networks, and the extension to convolutional patch-averaging is neither proved nor exactly referenced. Additionally, the paper does not supply the uniform and quantitative versions of that approximation needed for the balance argument. The central idea is promising and deserves publication after this gap is addressed.","major_comments":[{"comment":"Lemma 6.6 is load-bearing for Theorem 3.2, but it is stated only as a citation to [8]. The cited paper proves kernel approximation for fully connected networks; the submitted text gives no proof that the result extends to convolutional layers with shared weights, overlapping patches, and stride, nor to the recursively defined patch-averaged kernel k_{v,t}. This is not a cosmetic issue: Lemma 6.4 derives the required β-separation of the m rotated inputs entirely from Lemma 6.6, and Lemma 6.5 needs that separation for the Sudakov argument. The author should either provide a proof of the convolutional kernel approximation in this paper or give an exact reference that states the convolutional version with the same recursion.","section":"§6.1.1, Lemma 6.6"},{"comment":"Even if the convolutional version of Lemma 6.6 is accepted, the quoted statement is pointwise: it bounds |k(x,y) - ⟨Ψ(x),Ψ(y)⟩| for fixed x,y with failure probability δ. Lemma 6.4 needs a simultaneous statement over all m^2 pairs with failure probability o_d(1), under the width assumption d_i = ω(log(nd)) from Theorem 3.2. The text does not provide a union bound or a uniform version, and the scaling is not reconciled: Lemma 6.6 requires d_i ≳ l^2 log(ln/δ)/ε^2, which with ε = o_d(1) can be much larger than ω(log(nd)). The author should state the exact width requirement needed for Lemma 6.4 and prove or reference the corresponding uniform statement.","section":"§6.1, Lemma 6.6 and Lemma 6.4, quantitative uniformity"},{"comment":"The definition of the final kernel k(⃗x,⃗y) = k_{l,1}(⃗x,⃗y) is ambiguous. The final layer is linear, yet the recursive definition applies the nonlinearity σ̂ at every level, including v = l; it is also unclear whether n_l = d_l = 1 in the kernel recursion and how the summation over spatial positions is represented. This ambiguity matters in Lemma 6.4, where the values k_{v,t}(x_i,x_j) for i ≠ j and k_{v,t}(x_i,x_i) = 1 are used to lower-bound ∥Ψ(x_i) - Ψ(x_j)∥. The author should define the recursion precisely for the final linear layer and state explicitly which normalization makes k(x,x) = 1.","section":"§6.1.1, definition of k_{l,1}"}],"minor_comments":[{"comment":"The text writes “isoperimetric inequalities on so(d)”; the group being used is SO(d), the special orthogonal group, and the notation should be consistent throughout.","section":"Abstract and Section 1"},{"comment":"The sentence “Since U^{-1}x0 ∈ A^-_ϵ there is y ∈ A^- such that d(y, U^{-1}x0)” is incomplete; it should state d(y, U^{-1}x0) ≤ ϵ, which is the property used in the subsequent chain of inequalities.","section":"§5, proof of Lemma 5.3"},{"comment":"The displayed probability bound has an unclear constant: the event is over all pairs 1 ≤ i < j ≤ m and all positions 1 ≤ t ≤ n, so the union bound should give O(m^2 n e^{-d/8}); the factor “2” in the displayed expression appears unnecessary and should be checked.","section":"§6.1, Lemma 6.3"},{"comment":"The phrase “w.p. 1 - o_d(1)” is used several times without specifying the underlying probability space; the randomness is over the network weights, while the conditioning on the event over the points x_i should be stated explicitly.","section":"§6.1.1, proof of Lemma 6.4"},{"comment":"The notation x0 ∈ (R · S^{d-1})^n and the later replacement R = √d should be clarified: define R as the radius of the sphere and state that homogeneity of ReLU is used to reduce to R = √d before the proof of Lemma 6.1.","section":"Theorem 3.2 and §6.1"}],"recommendation":"major_revision","confidential_remarks":"The main theorem for odd activations is clean and self-contained, and the SO(d)-isoperimetric framing is a genuine contribution. The ReLU theorem, however, is not yet supported because the convolutional kernel approximation is cited rather than proved or precisely located in the literature. This is a fixable gap, but it is load-bearing; a major revision with a full treatment of Lemma 6.6 is appropriate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper extends the recent line on adversarial examples in random networks to convolutional architectures, and it does so with a substantially cleaner proof technique. The central idea—using isoperimetric concentration on SO(d) to show that any SO(d)-invariant, balanced random function has a nearby sign flip—is simple and genuinely useful. Theorem 3.1 (odd activations, first convolutional layer) is essentially self-contained, and I believe it.\n\nThe ReLU result (Theorem 3.2) is the weak half. The balance argument reduces to three lemmas, and Lemma 6.4 rests on Lemma 6.6, a kernel approximation statement cited from Daniely et al. [8]. That citation is not enough here. [8] proves kernel approximation for fully connected networks; this paper needs the same result for a recursive patch-averaging kernel on convolutional layers with shared weights and overlapping patches. The text provides no proof that the [8] argument extends to that setting, and the stress-test note is right that the cross-position dependencies are exactly what's missing. The paper also needs a uniform version of Lemma 6.6 (over all m² pairs) but states it pointwise; the union bound is not supplied. The definition of k_{l,1} for the final linear layer is also left a bit vague. These are fixable, but they are not cosmetic—Lemma 6.4's positive separation is the input to the Sudakov step, so without a proper kernel approximation the balance lemma and Theorem 3.2 collapse.\n\nWhat the paper does well: it's clearly written, the SO(d)-isoperimetric framework is a real simplification, and the odd-activation theorem is new and correct. It also honestly notes that it does not give an algorithm for finding the perturbation, a step backward from prior work but acceptable for an existence result.\n\nI agree with the reader's conditional verdict. The paper deserves peer review and should be engageable, but a referee should demand a full proof of the convolutional kernel approximation or a citation that explicitly covers it. If that gap is patched, this is a nice contribution to the theory literature.","headline":"A clean, genuinely new proof that random convolutional networks have adversarial examples; the ReLU half rests on an unproved kernel-approximation extension, so treat Theorem 3.2 as conditional and Theorem 3.1 as solid.","tokens_in":11824,"tokens_out":2772,"would_cite":true,"duration_ms":31395,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","60E15","52A40","60B20"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that before any training, a random convolutional network has, with high probability, a nearby input that flips the output's sign, and shows this follows directly from isoperimetric concentration on the rotation group…","keywords":["adversarial examples","random neural networks","convolutional networks","isoperimetric inequality","special orthogonal group","concentration of measure","ReLU networks","kernel approximation"],"falsifier":"Run a finite-width convolutional ReLU network with Xavier initialization, fix an input $\\vec{x}_0$ with $\\|\\vec{x}_0\\|\\approx\\sqrt d$, sample $m=\\lfloor\\sqrt{\\log d}\\rfloor$ points from its $SO(d)$-orbit, and measure the penultimate feature distances $\\|\\Psi(\\vec{x}_i)-\\Psi(\\vec{x}_j)\\|$; if for large $d$ and widths $\\omega(\\log nd)$ the minimal distance does not stay above a positive constant $\\beta$, or if the feature inner products deviate from the kernel $k(\\vec{x}_i,\\vec{x}_j)$ by a constant, then Lemma 6.4 fails and the ReLU guarantee of Theorem 3.2 does not follow.","tokens_in":10798,"feed_emoji":"🎲","tokens_out":11142,"duration_ms":124947,"temperature":0.7,"pith_summary":"The paper establishes that adversarial examples are unavoidable in a broad class of random convolutional networks, before any training. If the first layer is a regular random convolutional layer, all activations are odd, and the input dimension $d$ is even, then for any fixed input $\\vec{x}_0$, with probability at least $1-2e^{-\\tau^2/32}$ over the random weights, either the output is zero or a perturbation of size roughly $\\|\\vec{x}_0\\|/\\sqrt{d}$ changes its sign, regardless of the width or depth of the remaining layers. For constant-depth convolutional ReLU networks with Xavier initialization, a similar guarantee holds when widths and the input dimension grow faster than $\\log(nd)$. The mechanism is geometric: the random function is invariant under rotations of the input, and the uniform measure on the special orthogonal group $SO(d)$ concentrates so strongly that every balanced sign pattern has a sign change very close to every point. This gives a short proof that extends earlier results for fully connected random networks.","feed_headline":"Rotation symmetry alone forces adversarial examples in random conv nets","feed_subtitle":"A tiny perturbation changes the network's output sign with high probability, before any training.","key_machinery":"The load-bearing object is the pair consisting of the special orthogonal group $SO(d)$ with its Haar measure, extended to the orbit $C(\\vec{x}_0)$ of the fixed input under the rotation action. This orbit is a transitive $SO(d)$-metric space whose action is $L$-Lipschitz with $L=\\|\\vec{x}_0\\|_{\\mathrm{sp}}$. Theorem 4.4 transfers measure concentration from $SO(d)$ to the orbit, giving the neighborhood bound used in Lemma 5.3. The proof then needs just two facts about the network: $SO(d)$-invariance of the random function (Lemma 5.1), supplied by a regular random convolutional first layer; and balance, meaning the sets where the output is positive and negative each have measure at least $p$ on the orbit. Odd activations give $p=1/2$ immediately; for ReLU networks the paper proves $p\\approx 1/\\log d$ through an auxiliary chain in which a quoted kernel-approximation result identifies the penultimate feature map's inner products with a recursively defined patch-average kernel $k$, forcing constant separation of random orbit points, and Sudakov's inequality then guarantees the final linear layer takes both signs.","core_discovery":"The central claim, stated on the paper's own terms, is that the existence of adversarial examples in random convolutional networks is a rotation-symmetry phenomenon. Because the first layer's weight matrix is regular, meaning its distribution is unchanged by right multiplication with any orthogonal matrix, the whole random network is $SO(d)$-invariant: rotating the input is statistically equivalent to re-randomizing that layer. Fix an input $\\vec{x}_0$ and look at its orbit $C(\\vec{x}_0)=\\{U\\vec{x}_0:U\\in SO(d)\\}$, equipped with the pushforward of Haar measure. The isoperimetric inequality for $SO(d)$-metric spaces (Theorem 4.4) says that any subset of the orbit of measure at least $p$ has an $\\epsilon$-neighborhood of measure at least $1-\\exp(-(d-2)\\epsilon^2 p^2/(8L^2))$, where $L=\\|\\vec{x}_0\\|_{\\mathrm{sp}}$ is the spectral norm of the input matrix. Applying this to the positive and negative regions of the network's output on the orbit shows that a random rotation puts $\\vec{x}_0$ within distance $\\epsilon$ of both regions. The only network property left to prove is balance: odd activations give exact balance with $p=1/2$, and for ReLU networks approximate balance follows from a kernel-approximation lemma plus a Sudakov lower bound on the last layer.","pith_inferences":["The geometric core of Theorem 5.2 applies to any $SO(d)$-invariant random function that is balanced, so other architectures whose initialization is rotation-invariant should inherit the same adversarial-example guarantee without further changes.","Because the proof is non-constructive, the paper leaves open whether a simple algorithm such as gradient descent finds the guaranteed perturbation in convolutional networks; the fully connected case has such algorithms, so testing a single gradient step on random convolutional nets is a natural next experiment.","The bound's dependence on the spectral-norm ratio suggests the hardest inputs are highly anisotropic ones, where $\\|\\vec{x}_0\\|_{\\mathrm{sp}}/\\|\\vec{x}_0\\|$ is close to 1, giving a quantitative prediction about which inputs are least robust.","The parity condition for odd activations enters only because $-I$ must lie in $SO(d)$; the same concentration argument should work on the full orthogonal group $O(d)$, which would remove the even-dimension restriction."],"forward_implications":["For odd-activation networks whose first layer is a regular random convolutional layer, every fixed input has a sign-flipping perturbation of radius at most $(\\tau/\\sqrt{d-2})(\\|\\vec{x}_0\\|_{\\mathrm{sp}}/\\|\\vec{x}_0\\|)\\|\\vec{x}_0\\|$ with probability at least $1-2e^{-\\tau^2/32}$; for any input this is $O(\\|\\vec{x}_0\\|/\\sqrt{d})$.","For typical random inputs the spectral-norm ratio is about $1/\\sqrt{\\min(d,n)}$, improving the radius to $O(\\|\\vec{x}_0\\|/\\sqrt{\\min(d^2,dn)})$.","Constant-depth convolutional ReLU networks with Xavier initialization have adversarial examples with probability $1-o_d(1)$ as soon as the number of channels and the input dimension are $\\omega(\\log(nd))$.","The conclusions hold for random, untrained networks, so the phenomenon is tied to the architecture's initialization and its rotation invariance, not to a particular training procedure.","The probability bound degrades gracefully with the parameter $\\tau$, so one can trade confidence against perturbation size."],"supporting_citations":[{"why":"Supplies the measure concentration bound for $SO(d)$ (Theorem 4.1) that drives the isoperimetric inequality.","marker":"[16]"},{"why":"Quoted as Lemma 6.6: proves the kernel approximation for random ReLU feature maps that the balance argument for convolutional ReLU networks depends on.","marker":"[8]"},{"why":"Supplies Sudakov's lower bound used in Lemma 6.5 to show the last linear layer takes both signs.","marker":"[25]"},{"why":"Earlier result proving adversarial examples in random fully connected ReLU networks; the convolutional results extend this line of work.","marker":"[7]"},{"why":"Previous fully connected multi-layer random ReLU result that weakened width assumptions; context for Theorem 3.2.","marker":"[2]"},{"why":"Earlier two-layer random network result showing a single gradient step finds adversarial examples; comparison for the non-constructive convolutional statement.","marker":"[4]"},{"why":"Most recent fully connected random network result dropping width restrictions; the paper extends it to convolutional architectures.","marker":"[18]"},{"why":"Defines Xavier initialization, the weight distribution assumed in Theorem 3.2.","marker":"[11]"},{"why":"Supplies the high-dimensional tail and Gaussian concentration estimates used in Lemmas 6.3 and 6.5.","marker":"[27]"}],"fun_headline_variants":["Rotation symmetry is enough to guarantee adversarial examples in random conv nets","Adversarial examples are inevitable in random conv nets due to rotation symmetry","Random conv nets have adversarial examples because of rotation symmetry","Rotation symmetry alone makes adversarial examples unavoidable in random conv nets"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is Lemma 6.6, quoted from a previous paper on fully connected networks, which says the feature map of a random convolutional ReLU network approximates a patch-average kernel; the proof of the ReLU balance argument would collapse if that approximation fails, and the text does not show how the fully connected proof extends to convolutional layers.","fun_headline_variants_meta":{"raw":{"variants":["Rotation symmetry is enough to guarantee adversarial examples in random conv nets","Adversarial examples are inevitable in random conv nets due to rotation symmetry","Random conv nets have adversarial examples because of rotation symmetry","Rotation symmetry alone makes adversarial examples unavoidable in random conv nets"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000795,"raw_usage":{"total_tokens":3468,"prompt_tokens":880,"completion_tokens":2588,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":496,"completion_tokens_details":{"reasoning_tokens":2518}},"tokens_in":496,"tokens_out":2588,"duration_ms":21872,"temperature":1.0,"reasoning_tokens":2518,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T00:46:29.208252+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run a finite-width convolutional ReLU network with Xavier initialization, fix an input $\\vec{x}_0$ with $\\|\\vec{x}_0\\|\\approx\\sqrt d$, sample $m=\\lfloor\\sqrt{\\log d}\\rfloor$ points from its $SO(d)$-orbit, and measure the penultimate feature distances $\\|\\Psi(\\vec{x}_i)-\\Psi(\\vec{x}_j)\\|$; if for large $d$ and widths $\\omega(\\log nd)$ the minimal distance does not stay above a positive constant $\\beta$, or if the feature inner products deviate from the kernel $k(\\vec{x}_i,\\vec{x}_j)$ by a constant, then Lemma 6.4 fails and the ReLU guarantee of Theorem 3.2 does not follow.","supporting_citations":[{"cited_title":"The random matrix theory of the classical compact groups , volume 218","cited_arxiv_id":null,"evidence_quote":"Supplies the measure concentration bound for $SO(d)$ (Theorem 4.1) that drives the isoperimetric inequality."},{"cited_title":"Toward deeper understanding of neural networks: The power of initialization and a dual view on expressivity","cited_arxiv_id":null,"evidence_quote":"Quoted as Lemma 6.6: proves the kernel approximation for random ReLU feature maps that the balance argument for convolutional ReLU networks depends on."},{"cited_title":"Probability in high dimension","cited_arxiv_id":null,"evidence_quote":"Supplies Sudakov's lower bound used in Lemma 6.5 to show the last linear layer takes both signs."},{"cited_title":"Most relu networks suffer from ℓ2 adversarial perturbations","cited_arxiv_id":null,"evidence_quote":"Earlier result proving adversarial examples in random fully connected ReLU networks; the convolutional results extend this line of work."},{"cited_title":"Adversarial examples in multi-layer random relu networks","cited_arxiv_id":null,"evidence_quote":"Previous fully connected multi-layer random ReLU result that weakened width assumptions; context for Theorem 3.2."},{"cited_title":"A single gradient step finds adversarial examples on random two-layers neural networks","cited_arxiv_id":null,"evidence_quote":"Earlier two-layer random network result showing a single gradient step finds adversarial examples; comparison for the non-constructive convolutional statement."},{"cited_title":"Adversarial examples in random neural networks with general activations","cited_arxiv_id":null,"evidence_quote":"Most recent fully connected random network result dropping width restrictions; the paper extends it to convolutional architectures."},{"cited_title":"Understanding the difficulty of training deep feedforward neural networks","cited_arxiv_id":null,"evidence_quote":"Defines Xavier initialization, the weight distribution assumed in Theorem 3.2."},{"cited_title":"High-dimensional probability: An introduction with applications in data science , volume 47","cited_arxiv_id":null,"evidence_quote":"Supplies the high-dimensional tail and Gaussian concentration estimates used in Lemmas 6.3 and 6.5."}],"review_version":1}