REVIEW 4 major objections 5 minor 38 references
A principled approach for generating adversarial images under non-smooth dissimilarity metrics
T0 review · 4 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read 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.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (4)
- [Section 4, Table 1] 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.
- [Table 1 and footnote 1] 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 2.2 and Section 3] 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 4, Table 1] 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.
minor comments (5)
- [Algorithm 1] 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.
- [Equation (4) and Algorithm 1] 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.
- [Theorem 1 statement] There is a typographical error in part (a), '{Φ(xk}k≥0', which should read '{Φ(xk)}k≥0'.
- [Section 4, Table 2] 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 4, Implementation details] 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.
Circularity Check
No significant circularity: ProxLogBarrier is an empirical extension of prior work with independent baselines, and no claimed result reduces by construction to a fitted input.
full rationale
The paper's derivation chain is self-contained in the sense relevant to circularity. The method minimizes (7), m(u;x) + lambda*phi(F(u)), via the standard proximal gradient iteration (4), with proximal operators for l1, l2, linf, l0, and TV taken from textbook sources (Beck; Barbero and Sra; Duchi et al.). Theorem 1 is quoted from Beck's monograph and is an external, parameter-free convergence result; the fact that the authors' non-convex l0 prox lies outside its assumptions is a correctness concern, not a circular one. The LogBarrier attack [15] is cited as the starting point ('Our approach adopts the relaxation structure of the recently proposed LogBarrier attack [15]'), and LogBarrier is also an independent baseline in Tables 2 and 3; this self-citation is not load-bearing because the proximal-gradient extension and the empirical comparisons stand on their own. The central l0 claims are validated exclusively against independent FoolBox baselines (SparseFool, JSMA, Pointwise) on external datasets and models. No fitted parameter is renamed as a prediction: the median distances are measured attack outputs, not reconstructions of fitted values. The ImageNet l0 results being produced with an l1 prox ('the proximal operator for the l0 norm is far too strict. We decided to use the l1 norm to induce sparseness') and the internally inconsistent SparseFool CIFAR10 entry are reproducibility and overclaiming issues, but they are not instances of a derivation reducing to its own inputs by definition. Consequently, no circular step can be exhibited under the required standard, and the honest finding is no significant circularity.
Assumptions & free parameters
free parameters (5)
- λ0 =
0.1
- β =
0.75
- h =
0.1
- μ =
1 (0.5 for ImageNet ℓ1, 3 for ImageNet ℓ∞, 5 for TV)
- K / Kinner =
900/30 (2500 for ImageNet ℓ∞, 200/20 for TV)
assumptions (4)
- standard math Proximal gradient convergence theorem (Theorem 1) from Beck's book applies to the iterates of Algorithm 1.
- domain assumption The decision boundary F(u) = max_{i≠y} Z_i(u) - Z_y(u) is smooth enough for the log-barrier gradient to be well-defined and informative.
- domain assumption Each dissimilarity metric has a closed-form proximal operator.
- domain assumption The log-barrier relaxation in Eq (7) is a faithful surrogate for the misclassification constraint in Eq (5).
Cite this review
Pith. "Pith review of A principled approach for generating adversarial images under non-smooth dissimilarity metrics." pith.science (2026). https://pith.science/paper/XQCUDNXY
@misc{pith2026190801667,
author = {Pith},
title = {Pith review of: A principled approach for generating adversarial images under non-smooth dissimilarity metrics},
year = {2026},
howpublished = {\url{https://pith.science/paper/XQCUDNXY}},
note = {Machine review of arXiv:1908.01667}
}
abstract
Deep neural networks perform well on real world data but are prone to adversarial perturbations: small changes in the input easily lead to misclassification. In this work, we propose an attack methodology not only for cases where the perturbations are measured by $\ell_p$ norms, but in fact any adversarial dissimilarity metric with a closed proximal form. This includes, but is not limited to, $\ell_1, \ell_2$, and $\ell_\infty$ perturbations; the $\ell_0$ counting "norm" (i.e. true sparseness); and the total variation seminorm, which is a (non-$\ell_p$) convolutional dissimilarity measuring local pixel changes. Our approach is a natural extension of a recent adversarial attack method, and eliminates the differentiability requirement of the metric. We demonstrate our algorithm, ProxLogBarrier, on the MNIST, CIFAR10, and ImageNet-1k datasets. We consider undefended and defended models, and show that our algorithm easily transfers to various datasets. We observe that ProxLogBarrier outperforms a host of modern adversarial attacks specialized for the $\ell_0$ case. Moreover, by altering images in the total variation seminorm, we shed light on a new class of perturbations that exploit neighboring pixel information.
Reference graph
Works this paper leans on
-
[1]
Rima Alaifari, Giovanni S. Alberti, and Tandri Gauksson . Adef: an iterative algorithm to construct adversarial deformations. CoRR, abs/1804.07729, 2018
arXiv 2018
-
[2]
Anish Athalye, Nicholas Carlini, and David A. Wagner. Ob fuscated gradients give a false sense of security: Cir- cumventing defenses to adversarial examples. In Proceedings of the 35th International Conference on Machin e Learning, ICML 2018, Stockholmsm¨ assan, Stockholm, Sweden, July 10-15, 2018 , pages 274–283, 2018. THE PROXLOGBARRIER ADVERSARIAL A TT...
work page 2018
-
[3]
Proxquant: Quant ized neural networks via proximal operators
Y u Bai, Y u-Xiang Wang, and Edo Liberty. Proxquant: Quant ized neural networks via proximal operators. CoRR, abs/1810.00861, 2018
arXiv 2018
-
[4]
Fast newton-type methods for total variation regularization
´Alvaro Barbero and Suvrit Sra. Fast newton-type methods for total variation regularization. In Lise Getoor and Tobias Scheffer, editors, ICML, pages 313–320. Omnipress, 2011
work page 2011
-
[5]
Modular proximal optimiz ation for multidimensional total-variation regularizati on
Alvaro Barbero and Suvrit Sra. Modular proximal optimiz ation for multidimensional total-variation regularizati on. Journal of Machine Learning Research, 19(56):1–82, 2018
work page 2018
-
[6]
First-order methods in optimization
Amir Beck. First-order methods in optimization. 2017
work page 2017
-
[7]
Dec ision-based adversarial attacks: Reliable attacks agains t black-box machine learning models
Wieland Brendel, Jonas Rauber, and Matthias Bethge. Dec ision-based adversarial attacks: Reliable attacks agains t black-box machine learning models. arXiv preprint arXiv:1712.04248, 2017
arXiv 2017
-
[8]
Nicholas Carlini and David A. Wagner. Towards evaluatin g the robustness of neural networks. CoRR, abs/1608.04644, 2016
arXiv 2016
Show all 38 references
-
[9]
Jianbo Chen and Michael I. Jordan. Boundary attack++: Qu ery-efficient decision-based adversarial attack. CoRR, abs/1904.02144, 2019
1904 arXiv
-
[10]
Analysis of dawnbench, a time-to-accuracy machine learning performance benchmark
Cody Coleman, Daniel Kang, Deepak Narayanan, Luigi Nar di, Tian Zhao, Jian Zhang, Peter Bailis, Kunle Olukotun, Christopher R´ e, and Matei Zaharia. Analysis of dawnbench, a time-to-accuracy machine learning performance benchmark. CoRR, abs/1806.01427, 2018
2018 arXiv
-
[11]
Imagenet: A large-scale hierarchical image database
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, an d Fei-Fei Li. Imagenet: A large-scale hierarchical image database. In 2009 IEEE Computer Society Conference on Computer Vision an d Pattern Recognition (CVPR 2009), 20-25 June 2009, Miami, Florida, USA , pages 248–255, ...
2009
-
[12]
Efficient projections onto the l1-ball for learning in high dimensions
John Duchi, Shai Shalev-Shwartz, Y oram Singer, and Tus har Chandra. Efficient projections onto the l1-ball for learning in high dimensions. In Proceedings of the 25th International Conference on Machin e Learning, ICML ’08, pages 272–279, New Y ork, NY , USA, 2008. ACM
2008
-
[13]
Robust physical-world attacks on deep learning models
Kevin Eykholt, Ivan Evtimov, Earlence Fernandes, Bo Li , Amir Rahmati, Chaowei Xiao, Atul Prakash, Tadayoshi Kohno, and Dawn Song. Robust physical-world attacks on deep learning models. arXiv preprint arXiv:1707.08945, 2017
2017 arXiv
-
[14]
Scaleable input gradie nt regularization for adversarial robustness
Chris Finlay and Adam M Oberman. Scaleable input gradie nt regularization for adversarial robustness. arXiv preprint arXiv:1905.11468, 2019
1905 arXiv
-
[15]
Ob erman
Chris Finlay, Aram-Alexandre Pooladian, and Adam M. Ob erman. The logbarrier adversarial attack: making effec- tive use of decision boundary information. IEEE International Conference on Computer Vision (ICCV) , 2019
2019
-
[16]
Explaining and harnessing adversarial examples
Ian J Goodfellow, Jonathon Shlens, and Christian Szege dy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572, 2014
2014 arXiv
-
[17]
I dentity mappings in deep residual networks
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. I dentity mappings in deep residual networks. In Bastian Leibe, Jiri Matas, Nicu Sebe, and Max Welling, editors, Computer Vision – ECCV 2016 , pages 630–645, Cham,
2016
-
[18]
Learning multiple layers of features from tiny images
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images . 2009
2009
-
[19]
Goodfellow, and Samy Bengio
Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio. Adv ersarial examples in the physical world. CoRR, abs/1607.02533, 2016
2016 arXiv
-
[20]
Object recognition with gradient-based learning
Yann LeCun, Patrick Haffner, L´ eon Bottou, and Y oshua Bengio. Object recognition with gradient-based learning. In Shape, Contour and Grouping in Computer Vision , page 319, 1999
1999
-
[21]
Towards deep learning models resistant to adversarial attacks
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt , Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.06083, 2017
2017 arXiv
-
[22]
Learning proximal operators: Using denois- ing networks for regularizing inverse imaging problems
Tim Meinhardt, Michael M¨ oller, Caner Hazirbas, and Daniel Cremers. Learning proximal operators: Using denois- ing networks for regularizing inverse imaging problems. CoRR, abs/1704.03488, 2017
2017 arXiv
-
[23]
Sparsefool: a few pixels make a big difference
Apostolos Modas, Seyed-Mohsen Moosavi-Dezfooli, and Pascal Frossard. Sparsefool: a few pixels make a big difference. CoRR, abs/1811.02248, 2018
2018 arXiv
-
[24]
Deepfool: a simple and accurate method to fool deep neural networks
Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, and Pascal Frossard. Deepfool: a simple and accurate method to fool deep neural networks. CoRR, abs/1511.04599, 2015
2015 arXiv
-
[25]
Numerical optimization
Jorge Nocedal and Stephen Wright. Numerical optimization. Springer Science & Business Media, 2006
2006
-
[26]
McDaniel, Somesh Jha, Mat t Fredrikson, Z
Nicolas Papernot, Patrick D. McDaniel, Somesh Jha, Mat t Fredrikson, Z. Berkay Celik, and Ananthram Swami. The limitations of deep learning in adversarial settings. CoRR, abs/1511.07528, 2015
2015 arXiv
-
[27]
Catalyst for gradient - based nonconvex optimization
Courtney Paquette, Hongzhou Lin, Dmitriy Drusvyatski y, Julien Mairal, and Zaid Harchaoui. Catalyst for gradient - based nonconvex optimization. In Amos Storkey and Fernando Perez-Cruz, editors, Proceedings of the Twenty-First International Conference on Artificial Intelligence...
2018
-
[28]
Fo olbox v0.8.0: A python toolbox to benchmark the robust- ness of machine learning models
Jonas Rauber, Wieland Brendel, and Matthias Bethge. Fo olbox v0.8.0: A python toolbox to benchmark the robust- ness of machine learning models. CoRR, abs/1707.04131, 2017
2017 arXiv
-
[29]
V ariational analysis, volume 317
R Tyrrell Rockafellar and Roger J-B Wets. V ariational analysis, volume 317. Springer Science & Business Media, 2009
2009
-
[30]
Nonline ar total variation based noise removal algorithms
Leonid I Rudin, Stanley Osher, and Emad Fatemi. Nonline ar total variation based noise removal algorithms. Physica D: nonlinear phenomena, 60(1-4):259–268, 1992
1992
-
[31]
Robust perception through analysis by synthe- sis
Lukas Schott, Jonas Rauber, Wieland Brendel, and Matth ias Bethge. Robust perception through analysis by synthe- sis. CoRR, abs/1805.09190, 2018
2018 arXiv
-
[32]
One pixel attack for fooling deep neural networks
Jiawei Su, Danilo V asconcellos V argas, and Kouichi Sak urai. One pixel attack for fooling deep neural networks. CoRR, abs/:1710.08864, 2017
2017 arXiv
-
[33]
Goodfellow, and Rob Fergus
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In 2nd International Conference on Learning Representations , ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conferenc...
2014
-
[34]
Robustness may be at odds with accuracy
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be at odds with accuracy. arXiv preprint arXiv:1805.12152, 2018
2018 arXiv
-
[35]
Spatially transformed adversarial examples
Chaowei Xiao, Jun-Yan Zhu, Bo Li, Warren He, Mingyan Liu , and Dawn Song. Spatially transformed adversarial examples. CoRR, abs/1801.02612, 2018
2018 arXiv
-
[36]
Girshick, Piotr Doll´ ar, Zhuowen T u, and Kaiming He
Saining Xie, Ross B. Girshick, Piotr Doll´ ar, Zhuowen T u, and Kaiming He. Aggregated residual transformations for deep neural networks. CoRR, abs/1611.05431, 2016. THE PROXLOGBARRIER ADVERSARIAL A TTACK 13
2016 arXiv
-
[37]
Ad mm attack: An enhanced adversarial attack for deep neural networks with undetectable distortions
Pu Zhao, Kaidi Xu, Sijia Liu, Yanzhi Wang, and Xue Lin. Ad mm attack: An enhanced adversarial attack for deep neural networks with undetectable distortions. In Proceedings of the 24th Asia and South Pacific Design Automat ion Conference, ASPDAC ’19, pages 499–505, New Y ork, NY...
2019
-
[2016]
Springer International Publishing
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.