{"id":"dc13623a-5313-4f8b-a3a7-0f5ffb3b4adf","arxiv_id":"1908.01667","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"ProxLogBarrier extends the LogBarrier adversarial attack to non-smooth metrics via proximal gradient, achieving state-of-the-art ℓ0 perturbation results.","lead":"This paper introduces ProxLogBarrier, an adversarial attack method for neural networks that works with non-smooth distance measures, including the ℓ0 pixel count and total variation. The method outperforms several existing attacks, especially for ℓ0 perturbations, and applies to any metric with a closed-form proximal operator.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"ImageNet ℓ0 SOTA numbers come from an ℓ1-prox variant, and Table 1 lacks code and error bars, so the all-datasets ℓ0 claim is not yet independently auditable.","rationale":"The reader's weakest assumption concerns the absence of a convergence guarantee for the non-convex ℓ0 prox. That is a real but secondary issue: the contribution is an algorithm plus an empirical SOTA claim, and empirical results can be valid even when the supporting theorem does not apply. The more load-bearing problem is that the exact empirical claim is not auditable: the ImageNet ℓ0 numbers use an ℓ1 proxy rather than the derived ℓ0 prox, and the paper provides no code or error bars, with at least one suspicious baseline value. None of this disproves the central claim; a reproducible run with the actual ℓ0 prox could confirm it. The verdict should remain CONDITIONAL, not stronger, until that run is provided.","tokens_in":11664,"tokens_out":10523,"duration_ms":110276,"concrete_test":"Obtain the exact code and configuration for Table 1 and rerun the ImageNet-1k ℓ0 benchmark (same 500 images and ResNet-50) with the actual ℓ0 hard-threshold proximal operator H_√(2μ) from Section 3 instead of the ℓ1 prox, keeping all other hyperparameters as in Section 4. If the ℓ0-prox run does not achieve a median ℓ0 distance near 268 and below SparseFool's 1175, the all-datasets ℓ0 SOTA claim rests on the ℓ1 relaxation rather than the proposed ℓ0 method. As a secondary check, recompute the CIFAR10 SparseFool median with the model described in the footnote to confirm whether 3071 is a typo and whether the corrected baseline still leaves PLB ahead.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is the empirical ℓ0 SOTA statement in Table 1. The evidence for it is weaker than the text suggests in two connected ways. First, the ImageNet-1k ℓ0 results are not produced by the ℓ0 proximal operator derived in Section 3: Section 4 states that 'the proximal operator for the ℓ0 norm is far too strict. We decided to use the ℓ1 norm to induce sparseness in our adversarial perturbation (changing both the prox parameter and the step size to 0.5).' Therefore the reported ImageNet median distance of 268 comes from an ℓ1-relaxed PLB variant, not from the ℓ0 algorithm whose proximal form is derived and advertised, so the sentence 'Across all datasets considered, ProxLogBarrier outperforms all other attack methods' overstates what was evaluated for the proposed ℓ0 method. Second, Table 1 is given without code, seeds, or repeated trials, and one baseline entry is internally inconsistent: SparseFool on CIFAR10 is listed with median 3071 pixels out of 3072, while the footnote describes a matched comparison in which about 1.4% of pixels, roughly 43, are perturbed. That discrepancy prevents an independent audit of the comparison. The non-convex ℓ0 prox also lies outside Theorem 1, but the decisive gap is empirical: the claim would stand if the table were reproducible, so the missing reproducibility and the ImageNet ℓ1/ℓ0 mismatch are the load-bearing points.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes ProxLogBarrier, an adversarial attack that applies proximal gradient descent to a log-barrier relaxation of the misclassification constraint, thereby accommodating dissimilarity metrics with closed-form proximal operators, including non-smooth and non-convex ones such as ℓ0 and the total variation seminorm. The authors derive proximal operators for ℓ1, ℓ2, ℓ∞, ℓ0, and TV, present Algorithm 1 with backtracking and best-iterate tracking, and report experiments on MNIST, CIFAR10, and ImageNet-1k for undefended and defended models. The main empirical claim is that ProxLogBarrier achieves state-of-the-art ℓ0 adversarial distances across all datasets, with additional results for ℓ2, ℓ∞, and TV perturbations.","tokens_in":11941,"tokens_out":3051,"duration_ms":32665,"significance":"If the empirical claims are reproducible, the paper provides a useful and simple framework that extends adversarial attacks beyond differentiable ℓp metrics, and the TV experiments open a relatively unexplored class of perturbations. The algorithm is clearly specified, the proximal operators are standard, and the comparison suite covers commonly used baselines. However, the central ℓ0 state-of-the-art claim rests on Table 1, which currently has unresolved internal inconsistencies and a mismatch between the ImageNet experiments and the ℓ0 algorithm derived in Section 3. The theoretical motivation via Theorem 1 also does not cover the non-convex ℓ0 proximal operator used in the headline experiments, so the contribution is primarily empirical. With code, seeds, repeated trials, and corrected reporting, the work would be a solid benchmark contribution; without these, the strength of the claims is not independently auditable.","major_comments":[{"comment":"The ImageNet-1k ℓ0 results are not produced by the ℓ0 proximal operator derived in Section 3. Section 4 states: 'the proximal operator for the ℓ0 norm is far too strict. We decided to use the ℓ1 norm to induce sparseness in our adversarial perturbation (changing both the prox parameter and the step size to 0.5).' Since the ImageNet median distances of 268 and 691 in Table 1 are the only ImageNet ℓ0 entries, the sentence 'Across all datasets considered, ProxLogBarrier outperforms all other attack methods' overstates what was evaluated for the proposed ℓ0 method. Please report the ℓ0-hard-thresholding results separately from the ℓ1-relaxed variant, or clearly label the ImageNet column as an ℓ1-relaxed approximation and qualify the all-datasets claim.","section":"Section 4, Table 1"},{"comment":"The CIFAR10 SparseFool row lists a median distance of 3071 pixels out of 3072, while footnote 1 describes a matched comparison in which about 1.4% of pixels, roughly 43 pixels, are perturbed. These two numbers cannot both describe the same attack and dataset, and the asterisk convention does not resolve the discrepancy. This internal inconsistency prevents an independent audit of the comparison baseline and must be corrected or explained before the table can support the state-of-the-art claim.","section":"Table 1 and footnote 1"},{"comment":"Theorem 1 is invoked as the main motivation, but its assumptions require g to be a non-degenerate closed convex function and dom(g) ⊆ int(dom(f)). The ℓ0 counting 'norm' is non-convex and non-degenerate only in a formal sense, so Theorem 1 does not apply to the proximal gradient iteration used for the headline ℓ0 experiments. The paper should explicitly state that the ℓ0 case is heuristic, supported only by backtracking and best-iterate tracking, and should not present Theorem 1 as a convergence guarantee for that regime.","section":"Section 2.2 and Section 3"},{"comment":"The empirical state-of-the-art claim is based on single-run median distances without reported seeds, confidence intervals, or code. Since the attack initialization and the stochastic elements of the baselines can materially affect median distances, the absence of repeated trials or a code release makes the all-datasets superiority claim difficult to verify. Please provide code or, at minimum, multiple runs with variance measures for Table 1.","section":"Section 4, Table 1"}],"minor_comments":[{"comment":"The line 'Every Kinner iterations: λ = λ0βk' is ambiguous because k is the global iteration index; it would be clearer to introduce a separate schedule counter.","section":"Algorithm 1"},{"comment":"The proximal gradient step (4) uses a step size τ, while Algorithm 1 uses step size h and proximal parameter μ; the relationship between these quantities should be stated explicitly.","section":"Equation (4) and Algorithm 1"},{"comment":"There is a typographical error in part (a), '{Φ(xk}k≥0', which should read '{Φ(xk)}k≥0'.","section":"Theorem 1 statement"},{"comment":"The notation for thresholds such as 'ε = 2/255' is used without a denominator convention; please define whether the pixel range is [0,1] or [0,255] consistently.","section":"Section 4, Table 2"},{"comment":"The description of the ImageNet-1k defended model cites 'scaleable input gradient regularization' but does not give the model accuracy or the defense hyperparameters; one sentence with these details would help reproducibility.","section":"Section 4, Implementation details"}],"recommendation":"major_revision","confidential_remarks":"The paper's central contribution is an empirical ℓ0 attack benchmark, and the main claims are plausible but currently not fully auditable. The ImageNet ℓ0/ℓ1 mismatch and the SparseFool entry inconsistency in Table 1 are load-bearing and should be resolved before acceptance. Releasing code and seeds would substantially de-risk the state-of-the-art claim."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe short version: this is a useful, clearly written extension of the LogBarrier attack to non-smooth metrics, and the ℓ0 results on MNIST and CIFAR10 look genuinely strong. But the headline ImageNet ℓ0 claim is weaker than it appears, because the authors say they switched to an ℓ1 prox there, and the main table has an internal inconsistency that needs an audit.\n\nWhat is new: instead of approximating the metric to keep it differentiable, the paper uses proximal gradient steps for any dissimilarity with a closed-form prox. That covers ℓ0 hard thresholding and total variation, which were outside the original LogBarrier. The TV experiments are new and give a concrete way to think about perturbations that exploit neighboring pixels. That part of the framework is a real contribution.\n\nThe soft spots are mainly in the empirics. Section 4 states that on ImageNet the ℓ0 prox was \"far too strict\" and that they used the ℓ1 norm to induce sparseness, changing both the prox parameter and the step size. So the 268 median distance in Table 1 is not produced by the ℓ0 algorithm derived in Section 3. The text then says ProxLogBarrier outperforms all other attacks across all datasets, which overstates what was evaluated for the ℓ0 method. Second, Table 1 has no error bars or repeated trials, and the SparseFool entry for CIFAR10 lists 3071 pixels out of 3072 while the footnote says roughly 1.4% of pixels (about 43) are perturbed. That mismatch makes the comparison un-auditable as reported. The theory gap is less serious: Theorem 1 assumes convex g, and ℓ0 is non-convex, so the cited convergence guarantee doesn't directly apply; the authors mostly rely on empirical behavior, which is fine as a heuristic if the experiments are reproducible.\n\nTo give credit where it is due: the margins over SparseFool, JSMA, and Pointwise on MNIST and CIFAR10 are large, the attack always finds an adversary on those datasets where SparseFool sometimes fails, and the authors openly acknowledge the poor ImageNet ℓ∞ performance. The writing is honest and the baseline selection is reasonable.\n\nThis paper is for people working on sparse adversarial perturbations or benchmarking robustness. It deserves a serious referee, but the revision should include code or seeds, a corrected Table 1, and an ImageNet ℓ0 result from the actual ℓ0 prox (or a clear relabeling of that column as an ℓ1 relaxation).\n\nBest.","headline":"Useful proximal-gradient extension of LogBarrier for ℓ0 and TV, but the ImageNet ℓ0 headline comes from an ℓ1 variant and Table 1 needs audit before the SOTA claim holds.","tokens_in":12460,"tokens_out":3284,"would_cite":false,"duration_ms":29878,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that one proximal-gradient attack, ProxLogBarrier, outperforms specialized sparse attacks on MNIST, CIFAR10, and ImageNet-1k and extends adversarial perturbation generation to total-variation metrics.","keywords":["adversarial examples","proximal gradient method","non-smooth optimization","ℓ0 sparsity","total variation","log-barrier attack","deep neural networks","adversarial robustness"],"falsifier":"On the same 1000 CIFAR10 test images and the same network used in the paper, run ProxLogBarrier and SparseFool with $\\ell_0$ perturbations and identical defenses; if SparseFool's median $\\ell_0$ distance is lower than ProxLogBarrier's, or if ProxLogBarrier fails to return any adversarial image for more than half the images while SparseFool succeeds, the paper's central $\\ell_0$ claim collapses.","tokens_in":11454,"feed_emoji":"🎯","tokens_out":11543,"duration_ms":99754,"temperature":0.7,"pith_summary":"This paper sets out to show that a single attack algorithm, ProxLogBarrier, can generate minimal adversarial perturbations for any dissimilarity metric with a closed-form proximal operator, removing the differentiability requirement of the earlier LogBarrier attack. The method starts from a deliberately misclassified image and moves it toward the original while a logarithmic barrier keeps it misclassified. The paper reports that for the sparse $\\ell_0$ metric this one approach beats the specialized attacks SparseFool, JSMA, and Pointwise on MNIST, CIFAR10, and ImageNet-1k, on both plain and adversarially defended networks. It also introduces perturbations measured by total variation, a non-$\\ell_p$ metric based on neighboring pixel differences.","feed_headline":"ProxLogBarrier beats sparse-attack baselines on three datasets","feed_subtitle":"A proximal gradient framework handles ℓ0, ℓ∞, and total variation, beating SparseFool and JSMA on defended and undefended models.","key_machinery":"The load-bearing object is the proximal operator of the chosen dissimilarity metric, used inside a proximal gradient update. For the $\\ell_0$ counting metric the prox is component-wise hard thresholding, $H_\\alpha(s) = s \\mathbf{1}_{\\{|s|>\\alpha\\}}$; for $\\ell_1$, soft thresholding; for $\\ell_\\infty$, projection onto the $\\ell_1$ ball via Moreau decomposition; and for total variation, the finite-difference TV prox. Because the prox is metric-specific but the update is not, ProxLogBarrier turns the attack problem into a generic composite minimization and removes the need for the metric to be differentiable. The differentiable part of the objective is the log barrier $\\phi(F(u))$ with $F(u)=\\max_{i\\ne y} Z(u)_i - Z(u)_y$, which keeps iterates on the misclassified side of the decision boundary.","core_discovery":"ProxLogBarrier solves a log-barrier relaxation of the minimal-perturbation problem, $\\min_u m(u;x) - \\lambda \\log(z_{\\max} - z_y)$, where $m$ is any adversarial dissimilarity metric with a closed proximal operator. The optimization is carried out by proximal gradient steps, $u^{k+1} = \\mathrm{Prox}_{\\mu m}(u^k - h\\lambda \\nabla \\phi(F(u^k)))$, followed by a backtracking line search that preserves misclassification and by best-iterate recording. The paper's central claim is that this framework eliminates the need for smooth approximations of the metric and outperforms all compared attacks for $\\ell_0$ perturbations on MNIST, CIFAR10, and ImageNet-1k for both undefended and defended models. For $\\ell_2$ the method is best on MNIST and ImageNet-1k and competitive on CIFAR10; for $\\ell_\\infty$ it is best on MNIST but struggles on ImageNet-1k. The total-variation experiments reveal a new class of adversarial images that change color smoothly or in localized regions rather than altering scattered individual pixels.","pith_inferences":["The same update could be applied to any structured sparsity or low-complexity metric with a known prox, such as wavelet sparsity or low-rank penalties, not only pixel-count and total variation; the paper does not test these.","Because the algorithm walks from a misclassified image back toward the original, the reported distances are upper bounds on the true minimal adversarial distance; a natural extension is a verification study that compares ProxLogBarrier's images against exact or certified minima on small patches.","Total-variation-minimal perturbations look like smooth tints, which suggests a perceptual-robustness test: ask humans to rate whether a TV-minimal adversary is less noticeable than an $\\ell_p$-minimal adversary at matched classifier fooling rates; this is not run in the paper.","The ImageNet-1k $\\ell_\\infty$ weakness suggests the log-barrier formulation depends on well-separated decision boundaries; replacing $\\phi$ with a different misclassification penalty that is less sensitive to boundary geometry could extend the method to those cases. This is an inference, not a paper claim."],"forward_implications":["Sparse attacks become practical and general: practitioners can use the same algorithm for $\\ell_0$ on MNIST, CIFAR10, and ImageNet-1k and obtain lower median pixel counts than SparseFool, JSMA, and Pointwise, including against adversarially trained models.","Any metric with a closed proximal form can be inserted unchanged, so total-variation perturbations become a standard attack option; the paper shows these appear as smooth tints or localized color shifts.","For $\\ell_2$ perturbations, ProxLogBarrier beats all compared attacks on MNIST and ImageNet-1k and matches or beats most baselines on CIFAR10, while for $\\ell_\\infty$ it dominates on MNIST but is not reliable on ImageNet-1k because decision boundaries behave poorly there.","Defenses aimed at $\\ell_\\infty$ do not stop $\\ell_0$ attacks: adversarial training on MNIST and CIFAR10 leaves ProxLogBarrier's $\\ell_0$ success rates at 79.8% and 74.9% at median distance."],"supporting_citations":[{"why":"introduces the LogBarrier attack that ProxLogBarrier extends by replacing gradient descent with proximal steps","marker":"[15]"},{"why":"supplies the proximal gradient method and the convergence theorem that motivates the algorithm","marker":"[6]"},{"why":"provides the SparseFool baseline, the main $\\ell_0$ attack it must outperform","marker":"[23]"},{"why":"provides the JSMA baseline for $\\ell_0$ perturbations","marker":"[26]"},{"why":"provides the Pointwise black-box baseline for $\\ell_0$ perturbations","marker":"[31]"},{"why":"supplies the efficient projection onto the $\\ell_1$ ball used in the $\\ell_\\infty$ proximal operator","marker":"[12]"},{"why":"supply the efficient total-variation proximal operator that makes TV-norm attacks possible","marker":"[4, 5]"},{"why":"describes the adversarial training used to build the defended MNIST and CIFAR10 models","marker":"[21]"}],"fun_headline_variants":["ProxLogBarrier attacks with any dissimilarity metric, not just ℓp","ProxLogBarrier: one attack for ℓ0, ℓ∞, and total variation","ProxLogBarrier: adversarial attacks beyond ℓp norms","ProxLogBarrier outperforms sparse attacks on three datasets","ProxLogBarrier: a unified attack for ℓ0, ℓ2, ℓ∞, and total variation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that proximal-gradient iterates on a non-convex, non-smooth objective will move from a misclassified image back toward the original; the paper's convergence guarantee requires smoothness and convexity, so this behavior is trusted to hold empirically.","fun_headline_variants_meta":{"raw":{"variants":["ProxLogBarrier attacks with any dissimilarity metric, not just ℓp","ProxLogBarrier: one attack for ℓ0, ℓ∞, and total variation","ProxLogBarrier: adversarial attacks beyond ℓp norms","ProxLogBarrier outperforms sparse attacks on three datasets","ProxLogBarrier: a unified attack for ℓ0, ℓ2, ℓ∞, and total variation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001155,"raw_usage":{"total_tokens":4832,"prompt_tokens":1035,"completion_tokens":3797,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":651,"completion_tokens_details":{"reasoning_tokens":3684}},"tokens_in":651,"tokens_out":3797,"duration_ms":26320,"temperature":1.0,"reasoning_tokens":3684,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:05:58.549983+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On the same 1000 CIFAR10 test images and the same network used in the paper, run ProxLogBarrier and SparseFool with $\\ell_0$ perturbations and identical defenses; if SparseFool's median $\\ell_0$ distance is lower than ProxLogBarrier's, or if ProxLogBarrier fails to return any adversarial image for more than half the images while SparseFool succeeds, the paper's central $\\ell_0$ claim collapses.","supporting_citations":[{"cited_title":"Ob erman","cited_arxiv_id":null,"evidence_quote":"introduces the LogBarrier attack that ProxLogBarrier extends by replacing gradient descent with proximal steps"},{"cited_title":"First-order methods in optimization","cited_arxiv_id":null,"evidence_quote":"supplies the proximal gradient method and the convergence theorem that motivates the algorithm"},{"cited_title":"Efficient projections onto the l1-ball for learning in high dimensions","cited_arxiv_id":null,"evidence_quote":"supplies the efficient projection onto the $\\ell_1$ ball used in the $\\ell_\\infty$ proximal operator"}],"review_version":1}