Focused Width in Adversarial Fake Detection: A Separation

Gao Huang

Periodic test breaks focused-width conjecture by √log n

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · glm-5.2

2026-07-07 13:38 UTC pith:DLPGFSUY

load-bearing objection Clean counterexample disproving a stated conjecture. The periodic cosine test is the key new idea, and the proofs check out.

arxiv 2607.05379 v1 pith:DLPGFSUY submitted 2026-07-06 math.ST stat.TH

Focused Width in Adversarial Fake Detection: A Separation

Gao Huang This is my paper

classification math.ST stat.TH

keywords mathscrfakefocusedmodelradiuswidthdetectabilitysubset

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper disproves a conjecture that a geometric quantity called the focused width characterizes the detectability radius — the scale at which adversarial fakes become distinguishable from genuine data — up to universal constants for all origin-symmetric perturbation sets. For any origin-symmetric set T_n sandwiched between the discrete hypercube {-1,1}^n and the odd integer grid (2Z+1)^n, the author proves that the ratio of focused width to detectability radius is at least of order √(log n), showing the focused width can overestimate detectability by that factor. The mechanism is a periodic cosine test function F_r(x) = Σ cos(πx_j/r) that flips sign under every shift by an odd integer multiple of r, exploiting arithmetic structure invisible to the linear geometric lens of focused width. The paper further shows this separation is not an intrinsic limit: under product Laplace data, the gap widens to at least polynomial order n^{1/4}.

Core claim

A single periodic test function — the sum of coordinatewise cosines with period 2r — simultaneously detects every adversarial perturbation drawn from any subset of the odd integer grid at scales far below what the focused width predicts. This works because every odd-integer shift flips the sign of each cosine term, turning the detection problem into a concentration-of-measure question rather than a linear geometry question. The focused width, being a linear Gaussian-complexity quantity, cannot see this arithmetic periodicity, and the resulting gap grows with dimension.

What carries the argument

The periodic test function F_r(x) = Σ cos(πx_j / r), whose sign flips under any shift by an odd integer grid vector; Hoeffding's inequality applied to the bounded independent variables Z_j = cos(πX_j / r) to show F_r concentrates around its positive mean; and a matching upper and lower bound on the focused width via the set n^{-1}Q_n and Jensen's inequality with Rademacher decomposition of Gaussian vectors.

Load-bearing premise

The upper bound on detectability radius relies on Hoeffding's inequality applied to the variables cos(πX_j/r), which requires that the expectation of each cosine term is large enough relative to n to drive the tail probability below 0.1. If the concentration of these bounded variables were insufficient at the claimed scale, the detectability radius upper bound — and hence the separation result — would not hold.

What would settle it

Construct a perturbation set between the hypercube and the odd integer grid for which the periodic cosine test fails to achieve detection at scale O(1/√(log n)), or show that the focused width can be matched by a different test at the focused-width scale for all such sets, closing the gap.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

The focused width cannot serve as a universal proxy for detectability radius outside highly symmetric perturbation sets; practitioners using it as a benchmark for adversarial robustness may overestimate difficulty of detection by logarithmic or polynomial factors.
Periodic or arithmetic structure in perturbation sets can be exploited by tests that are invisible to linear geometric complexity measures, suggesting that detection thresholds depend on the algebraic structure of the adversary's allowed perturbations, not just their geometry.
The gap between geometric complexity and true detectability is distribution-dependent: heavier-tailed data (Laplace vs. Gaussian) widens the separation, indicating that the reliability of geometric benchmarks varies with the data model.
Designing adversarial perturbation sets that lack exploitable arithmetic structure could restore the predictive power of focused-width-type bounds, pointing toward a characterization of which structural features make geometric proxies tight.
The absence of a universal testing mechanism for general perturbation sets remains open: neither linear geometric methods nor periodic arithmetic tests alone may suffice for sets mixing geometric and arithmetic structure.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

Clean counterexample disproving a stated conjecture. The periodic cosine test is the key new idea, and the proofs check out.

read the letter

This note disproves the focused width conjecture of Mendelson–Paouris–Vershynin by exhibiting a broad class of discrete perturbation sets — anything between the hypercube {−1,1}^n and the odd integer grid (2Z+1)^n — for which the focused width overestimates the detectability radius by at least √(log n). The Laplace extension pushes the separation to n^{1/4}. The proofs are correct and self-contained, and the result is a genuine contribution to the subfield. The reader's assessment and the stress-test note both land. I checked the two pillars: Lemma 1 (focused width equals √(2/π)) and Lemma 2 (detectability radius ≲ 1/√(log n)). The lower bound in Lemma 1 uses Jensen on the support function conditioned on the Rademacher part, which is clean. The upper bound via U_0 = n^{-1}Q_n is tight. Lemma 2's Hoeffding application is standard: Z_j = cos(πX_j/r) are independent, bounded in [−1,1], with mean ν = exp(−π²/(2r²)) > 0, so the tail bound P(Σ(Z_j − ν) ≤ −nν) ≤ exp(−nν²/2) is exactly equation (18). The deterministic sign-flip (Fact 1) is also correct: shifting by an odd multiple of r flips each cosine. No gaps in the Gaussian argument. The Laplace extension (Section 3) follows the same structure with the Laplace characteristic function, and the n^{1/4} bound comes through. One minor observation: the separation depends entirely on the arithmetic structure of the odd integer grid. The periodic test exploits that all admissible shifts are odd integers, so the cosine flips sign. This is a legitimate and clever construction, but the counterexample class is quite specific. The paper is upfront about this — the summary notes that the relevant structure is arithmetic, not geometric. The broader claim that no single universal mechanism exists is reasonable but speculative; the paper proves one separation, not a taxonomy. This is a short, focused note that does exactly what it says. It belongs in a good probability or statistics journal. The audience is researchers in high-dimensional probability and adversarial detection. It deserves a serious referee who can verify the Hoeffding steps and the Jensen argument, which are the load-bearing pieces. I'd recommend sending it out for review.

Referee Report

0 major / 6 minor

Summary. This paper disproves a conjecture of Mendelson, Paouris, and Vershynin [12] that the focused width characterizes the detectability radius up to universal constants for all origin-symmetric perturbation sets. The author considers any origin-symmetric set T_n satisfying {-1,1}^n ⊂ T_n ⊂ (2Z+1)^n and proves that w̃(T_n)/r(T_n) ≳ √(log n), establishing a separation. The proof combines a dimension-free lower bound w̃(T_n) = √(2/π) (Lemma 1) with a periodic cosine-based detection test (Lemma 2) that achieves detectability at scale r ≲ 1/√(log n). A non-Gaussian extension to product Laplace data yields a polynomial separation of order n^{1/4}. The proofs are clean, self-contained, and parameter-free.

Significance. The paper resolves a natural and explicitly stated conjecture in the adversarial fake detection framework of [12]. The separation is conceptually clear: the focused width is a linear-geometric quantity, while the detectability radius permits arbitrary measurable tests, and the author identifies a concrete arithmetic mechanism (periodic sign-flipping on the odd integer grid) that exploits this gap. The extension to product Laplace data, showing that the logarithmic separation is not intrinsic, adds value. The construction is parameter-free, the constants emerge from Hoeffding's inequality and the Gaussian characteristic function, and the results are falsifiable. The paper should be of broad interest to the high-dimensional probability and mathematical statistics community.

minor comments (6)

The definition of the shifted set A - rT in equation (1) and the surrounding text uses the notation A - rT := {x - rt : x ∈ A, t ∈ T}. This is slightly nonstandard; a brief clarifying remark that this is the Minkowski-type difference relevant to the adversarial model would help readers unfamiliar with [12].
In Fact 2, the reference for Hoeffding's inequality is given as [14, Theorem 2.2.6], which points to Vershynin's textbook. This is acceptable, but the classical Hoeffding (1963) reference could also be cited for completeness. The same citation style is used in the proof of Theorem 2.
Theorem 1 states 'for all sufficiently large n' but does not specify a threshold. While this is standard for asymptotic results, indicating the rough threshold (e.g., n ≥ 100 or n ≥ 1000) would help the reader gauge when the bound becomes effective.
In Section 3, the definition of ρ_n in equation (23) involves an infimum over ρ > 0 satisfying a condition for every r ≥ ρ. It would improve clarity to briefly note that this infimum is well-defined (the set is nonempty for symmetric distributions with finite first moment and a continuous, positive characteristic function near the origin).
The paper does not discuss whether the √(log n) separation is tight for the Gaussian case. A brief remark on whether a matching lower bound r(T_n) ≳ 1/√(log n) is known or conjectured would contextualize the result.
In the proof of Corollary 1, equation (28) gives ρ_n = π/√2 · (n/(2 log 10) - 1)^{-1/2}. The transition from the definition (23) to this closed form could be spelled out in one additional line for the reader's convenience.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for a careful and generous report. The referee's recommendation is minor revision, and the report contains no major comments beyond the summary and significance assessment. We address the report below.

Circularity Check

0 steps flagged

No significant circularity identified; the derivation is self-contained with no fitted parameters and no self-citation chain.

full rationale

The paper's central result (Theorem 1) is built from two independent ingredients: (1) Lemma 1, which computes w̃(T_n) = √(2/π) via Jensen's inequality and an explicit hitting set U_0 = n⁻¹Q_n, and (2) Lemma 2, which bounds r(T_n) ≲ 1/√(log n) via a periodic cosine test and Hoeffding's inequality. Neither ingredient reduces to the other by construction. There are no fitted parameters: the constants emerge from E|N(0,1)| = √(2/π) and from the Gaussian characteristic function φ(π/r) = exp(−π²/(2r²)), both standard facts. The Hoeffding application (Fact 2) uses independent bounded variables Z_j = cos(πX_j/r) ∈ [−1,1] with mean ν = exp(−π²/(2r²)), yielding P(F_r ≤ 0) ≤ exp(−nν²/2), which is a standard concentration bound, not a tautology. The non-Gaussian extension (Section 3) follows the same structure with the Laplace characteristic function φ(u) = 1/(1+u²/2), again a standard computation. Citations to [12] (Mendelson, Paouris, Vershynin) define the problem setup and the conjecture being disproved; they are not used to justify the proof itself. Citation [13] (Smirnov) provides inspiration for the periodic test idea but the construction is carried out independently. Citation [14] (Vershynin's textbook) is a standard reference for Hoeffding's inequality. No self-citation chain exists: the author Gao Huang does not appear among the cited authors. The derivation chain is clean and self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

No free parameters are fitted or introduced. No axioms beyond standard mathematical results (Hoeffding, characteristic functions, Jensen) are used. No new entities (particles, forces, dimensions) are postulated. The paper is a pure derivation from established probability theory.

axioms (3)

standard math Standard Gaussian measure and concentration (Hoeffding's inequality for bounded random variables)
Used in Fact 2 to bound P(F_r(X) ≤ 0) via Hoeffding's inequality applied to Z_j = cos(πX_j/r) ∈ [-1,1].
standard math Characteristic function of standard Gaussian and Laplace distributions
Used to compute E[cos(πX/r)] = exp(-π²/(2r²)) for Gaussian and 1/(1+π²/(2r²)) for Laplace.
standard math Jensen's inequality for convex functions
Used in Lemma 1 to lower bound w(U) by conditioning on the Rademacher vector and applying Jensen to the support function h_U.

pith-pipeline@v1.1.0-glm · 12784 in / 1744 out tokens · 210807 ms · 2026-07-07T13:38:36.733883+00:00 · methodology

0 comments

read the original abstract

We study the adversarial fake detection model introduced by Mendelson, Paouris and Vershynin. In this model, a genuine sample is $\pmb{X}\sim N(0,\pmb{I}_n)$, while a fake sample is produced as $\pmb{X}+r\pmb{t}({\pmb{X}})$, where the adversary first observes $\pmb{X}$ and then chooses an admissible perturbation $\pmb{t}({\pmb{X}})$ from a prescribed set $\mathscr{T}\subset\mathbb{R}^n$. The central quantity is the detectability radius $r(\mathscr{T})$, which formalizes the transition scale at which fake samples become reliably distinguishable from genuine ones. Mendelson, Paouris and Vershynin introduced the focused width $\widetilde{w}(\mathscr{T})$ as a geometric parameter for this radius and conjectured that, for every origin-symmetric set $\mathscr{T}$, it characterizes $r(\mathscr{T})$ up to universal constants. In this note, we disprove this conjecture for a broad class of discrete sets. More precisely, we consider any origin-symmetric set $\mathscr{T}_n$ lying between the hypercube and the odd integer grid: \begin{equation*} \{-1,1\}^n\subset\mathscr{T}_n\subset ( 2\mathbb{Z}+1)^n. \end{equation*} For every such $\mathscr{T}_n$, we prove that $\frac{\widetilde{w}(\mathscr{T}_n)}{r(\mathscr{T}_n) }\gtrsim \sqrt{\log n}$. Thus, in the Gaussian model, the focused width can overestimate the detectability radius by a $\sqrt{\log n}$ factor and therefore does not characterize it in general. We further show that this logarithmic scale is not intrinsic: in the corresponding non-Gaussian model with product Laplace data, the focused width benchmark can even exceed the detectability radius by at least a polynomial factor of order $n^{1/4}$.

discussion (0)

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages · 2 internal anchors

[1]

On com- binatorial testing problems.The Annals of Statistics, 38(5):3063–3092, 2010

Louigi Addario-Berry, Nicolas Broutin, Luc Devroye, and G´ abor Lugosi. On com- binatorial testing problems.The Annals of Statistics, 38(5):3063–3092, 2010

work page 2010
[2]

Cand` es, and Arnaud Durand

Ery Arias-Castro, Emmanuel J. Cand` es, and Arnaud Durand. Detection of an anomalous cluster in a network.The Annals of Statistics, 39(1):278–304, 2011

work page 2011
[3]

Cand` es, and Yaniv Plan

Ery Arias-Castro, Emmanuel J. Cand` es, and Yaniv Plan. Global testing under sparse alternatives: ANOVA, multiple comparisons and the higher criticism.The Annals of Statistics, 39(5):2533–2556, 2011

work page 2011
[4]

Detection of sparse mixtures: Higher criticism and scan statistic.Electronic Journal of Statistics, 13(1):208–230, 2019

Ery Arias-Castro and Andrew Ying. Detection of sparse mixtures: Higher criticism and scan statistic.Electronic Journal of Statistics, 13(1):208–230, 2019

work page 2019
[5]

Non-asymptotic minimax rates of testing in signal detection

Yannick Baraud. Non-asymptotic minimax rates of testing in signal detection. Bernoulli, 8(5):577–606, 2002. 13

work page 2002
[6]

Tony Cai, Jiashun Jin, and Mark G

T. Tony Cai, Jiashun Jin, and Mark G. Low. Estimation and confidence sets for sparse normal mixtures.The Annals of Statistics, 35(6):2421–2449, 2007

work page 2007
[7]

Tsy- bakov, and Yuhao Wang

Alexandra Carpentier, Olivier Collier, La¨ etitia Comminges, Alexandre B. Tsy- bakov, and Yuhao Wang. Minimax rate of testing in sparse linear regression. Automation and Remote Control, 80(10):1817–1834, 2019

work page 2019
[8]

Sparse signal detection in heteroscedastic gaussian sequence models: Sharp minimax rates.Bernoulli, 30(3):2127–2153, 2024

Julien Chhor, Rajarshi Mukherjee, and Subhabrata Sen. Sparse signal detection in heteroscedastic gaussian sequence models: Sharp minimax rates.Bernoulli, 30(3):2127–2153, 2024

work page 2024
[9]

Donoho and Jiashun Jin

David L. Donoho and Jiashun Jin. Higher criticism for detecting sparse heteroge- neous mixtures.The Annals of Statistics, 32(3):962–994, 2004

work page 2004
[10]

Donoho and Alon Kipnis

David L. Donoho and Alon Kipnis. The impossibility region for detecting sparse mixtures using the higher criticism.The Annals of Applied Probability, 34(5):4921– 4939, 2024

work page 2024
[11]

Ingster, Alexandre B

Yuri I. Ingster, Alexandre B. Tsybakov, and Nicolas Verzelen. Detection boundary in sparse regression.Electronic Journal of Statistics, 4:1476–1526, 2010

work page 2010
[12]

Can we spot a fake?

Shahar Mendelson, Grigoris Paouris, and Roman Vershynin. Can we spot a fake? arXiv preprint arXiv:2410.18880, 2024

work page internal anchor Pith review Pith/arXiv arXiv 2024
[13]

Detecting adversarial attacks on random samples

Gleb Smirnov. Detecting adversarial attacks on random samples.arXiv preprint arXiv:2408.06166, 2024

work page internal anchor Pith review Pith/arXiv arXiv 2024
[14]

Cambridge University Press, 2018

Roman Vershynin.High-Dimensional Probability: An Introduction with Applica- tions in Data Science, volume 47 ofCambridge Series in Statistical and Proba- bilistic Mathematics. Cambridge University Press, 2018. 14

work page 2018

[1] [1]

On com- binatorial testing problems.The Annals of Statistics, 38(5):3063–3092, 2010

Louigi Addario-Berry, Nicolas Broutin, Luc Devroye, and G´ abor Lugosi. On com- binatorial testing problems.The Annals of Statistics, 38(5):3063–3092, 2010

work page 2010

[2] [2]

Cand` es, and Arnaud Durand

Ery Arias-Castro, Emmanuel J. Cand` es, and Arnaud Durand. Detection of an anomalous cluster in a network.The Annals of Statistics, 39(1):278–304, 2011

work page 2011

[3] [3]

Cand` es, and Yaniv Plan

Ery Arias-Castro, Emmanuel J. Cand` es, and Yaniv Plan. Global testing under sparse alternatives: ANOVA, multiple comparisons and the higher criticism.The Annals of Statistics, 39(5):2533–2556, 2011

work page 2011

[4] [4]

Detection of sparse mixtures: Higher criticism and scan statistic.Electronic Journal of Statistics, 13(1):208–230, 2019

Ery Arias-Castro and Andrew Ying. Detection of sparse mixtures: Higher criticism and scan statistic.Electronic Journal of Statistics, 13(1):208–230, 2019

work page 2019

[5] [5]

Non-asymptotic minimax rates of testing in signal detection

Yannick Baraud. Non-asymptotic minimax rates of testing in signal detection. Bernoulli, 8(5):577–606, 2002. 13

work page 2002

[6] [6]

Tony Cai, Jiashun Jin, and Mark G

T. Tony Cai, Jiashun Jin, and Mark G. Low. Estimation and confidence sets for sparse normal mixtures.The Annals of Statistics, 35(6):2421–2449, 2007

work page 2007

[7] [7]

Tsy- bakov, and Yuhao Wang

Alexandra Carpentier, Olivier Collier, La¨ etitia Comminges, Alexandre B. Tsy- bakov, and Yuhao Wang. Minimax rate of testing in sparse linear regression. Automation and Remote Control, 80(10):1817–1834, 2019

work page 2019

[8] [8]

Sparse signal detection in heteroscedastic gaussian sequence models: Sharp minimax rates.Bernoulli, 30(3):2127–2153, 2024

Julien Chhor, Rajarshi Mukherjee, and Subhabrata Sen. Sparse signal detection in heteroscedastic gaussian sequence models: Sharp minimax rates.Bernoulli, 30(3):2127–2153, 2024

work page 2024

[9] [9]

Donoho and Jiashun Jin

David L. Donoho and Jiashun Jin. Higher criticism for detecting sparse heteroge- neous mixtures.The Annals of Statistics, 32(3):962–994, 2004

work page 2004

[10] [10]

Donoho and Alon Kipnis

David L. Donoho and Alon Kipnis. The impossibility region for detecting sparse mixtures using the higher criticism.The Annals of Applied Probability, 34(5):4921– 4939, 2024

work page 2024

[11] [11]

Ingster, Alexandre B

Yuri I. Ingster, Alexandre B. Tsybakov, and Nicolas Verzelen. Detection boundary in sparse regression.Electronic Journal of Statistics, 4:1476–1526, 2010

work page 2010

[12] [12]

Can we spot a fake?

Shahar Mendelson, Grigoris Paouris, and Roman Vershynin. Can we spot a fake? arXiv preprint arXiv:2410.18880, 2024

work page internal anchor Pith review Pith/arXiv arXiv 2024

[13] [13]

Detecting adversarial attacks on random samples

Gleb Smirnov. Detecting adversarial attacks on random samples.arXiv preprint arXiv:2408.06166, 2024

work page internal anchor Pith review Pith/arXiv arXiv 2024

[14] [14]

Cambridge University Press, 2018

Roman Vershynin.High-Dimensional Probability: An Introduction with Applica- tions in Data Science, volume 47 ofCambridge Series in Statistical and Proba- bilistic Mathematics. Cambridge University Press, 2018. 14

work page 2018