# Double Bubble, Toil and Trouble: Enhancing Certified Robustness through Transitivity

arXiv: https://arxiv.org/abs/2210.06077 · HTML: https://mlsanity.com/paper/2210.06077/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 50 references that are in the map.
- First posted on arXiv 12 Oct 2022.

## Builds on (most cited first, 27 of 27)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Practical Black-Box Attacks against Machine Learning](https://mlsanity.com/paper/1602.02697/) (2016)
- [Evasion Attacks against Machine Learning at Test Time](https://mlsanity.com/paper/1708.06131/) (2017)
- [Certified Robustness to Adversarial Examples with Differential Privacy](https://mlsanity.com/paper/1802.03471/) (2018)
- [Efficient Neural Network Robustness Certification with General Activation Functions](https://mlsanity.com/paper/1811.00866/) (2018)
- [Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers](https://mlsanity.com/paper/1906.04584/) (2019)
- [Towards Fast Computation of Certified Robustness for ReLU Networks](https://mlsanity.com/paper/1804.09699/) (2018)
- [Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Complete and Incomplete Neural Network Robustness Verification](https://mlsanity.com/paper/2103.06624/) (2021)
- [Certified Adversarial Robustness with Additive Noise](https://mlsanity.com/paper/1809.03113/) (2018)
- [A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networks](https://mlsanity.com/paper/1902.08722/) (2019)
- [MACER: Attack-free and Scalable Robust Training via Maximizing Certified Radius](https://mlsanity.com/paper/2001.02378/) (2020)
- [Certified Defenses for Adversarial Patches](https://mlsanity.com/paper/2003.06693/) (2020)
- [(De)Randomized Smoothing for Certifiable Defense against Patch Attacks](https://mlsanity.com/paper/2002.10733/) (2020)
- [A Study of Face Obfuscation in ImageNet](https://mlsanity.com/paper/2103.06191/) (2021)
- [Motivating the Rules of the Game for Adversarial Example Research](https://mlsanity.com/paper/1807.06732/) (2018)
- [TSS: Transformation-Specific Smoothing for Robustness Certification](https://mlsanity.com/paper/2002.12398/) (2020)
- [Fast Certified Robust Training with Short Warmup](https://mlsanity.com/paper/2103.17268/) (2021)
- [Higher-Order Certification for Randomized Smoothing](https://mlsanity.com/paper/2010.06651/) (2020)
- [Double Sampling Randomized Smoothing](https://mlsanity.com/paper/2206.07912/) (2022)
- [Towards Evaluating and Training Verifiably Robust Neural Networks](https://mlsanity.com/paper/2104.00447/) (2021)
- [TPC: Transformation-Specific Smoothing for Point Cloud Models](https://mlsanity.com/paper/2201.12733/) (2022)
- [Improving the semidefinite programming bound for the kissing number by exploiting polynomial symmetry](https://mlsanity.com/paper/1609.05167/) (2016)

## Built on by (most cited first, 15 of 15)

- [Provably Unlearnable Data Examples](https://mlsanity.com/paper/2405.03316/) (2024)
- [Fox in the Henhouse: Supply-Chain Backdoor Attacks Against Reinforcement Learning](https://mlsanity.com/paper/2505.19532/) (2025)
- [Et Tu Certifications: Robustness Certificates Yield Better Adversarial Examples](https://mlsanity.com/paper/2302.04379/) (2023)
- [It's Simplex! Disaggregating Measures to Improve Certified Robustness](https://mlsanity.com/paper/2309.11005/) (2023)
- [Position: Certified Robustness Does Not (Yet) Imply Model Security](https://mlsanity.com/paper/2506.13024/) (2025)
- [Rethinking Randomized Smoothing from the Perspective of Scalability](https://mlsanity.com/paper/2312.12608/) (2023)
- [Multi-level Certified Defense Against Poisoning Attacks in Offline Reinforcement Learning](https://mlsanity.com/paper/2505.20621/) (2025)
- [Spatial-Frequency Discriminability for Revealing Adversarial Perturbations](https://mlsanity.com/paper/2305.10856/) (2023)
- [Effects of Exponential Gaussian Distribution on (Double Sampling) Randomized Smoothing](https://mlsanity.com/paper/2406.02309/) (2024)
- [Average Certified Radius is a Poor Metric for Randomized Smoothing](https://mlsanity.com/paper/2410.06895/) (2024)
- [CAMP in the Odyssey: Provably Robust Reinforcement Learning with Certified Radius Maximization](https://mlsanity.com/paper/2501.17667/) (2025)
- [Dual Randomized Smoothing: Beyond Global Noise Variance](https://mlsanity.com/paper/2512.01782/) (2025)
- [On the Extreme Variance of Certified Local Robustness Across Model Seeds](https://mlsanity.com/paper/2601.13303/) (2026)
- [Halt Fast! Early Stopping for Certified Robustness](https://mlsanity.com/paper/2606.27694/) (2026)
- [What Was That Again? Certified Robustness for Automatic Speech Recognition](https://mlsanity.com/paper/2606.27698/) (2026)

## Abstract (arXiv)

In response to subtle adversarial examples flipping classifications of neural network models, recent research has promoted certified robustness as a solution. There, invariance of predictions to all norm-bounded attacks is achieved through randomised smoothing of network inputs. Today's state-of-the-art certifications make optimal use of the class output scores at the input instance under test: no better radius of certification (under the L2 norm) is possible given only these score. However, it is an open question as to whether such lower bounds can be improved using local information around the instance under test. In this work, we demonstrate how today's "optimal" certificates can be improved by exploiting both the transitivity of certifications, and the geometry of the input space, giving rise to what we term Geometrically-Informed Certified Robustness. By considering the smallest distance to points on the boundary of a set of certifications this approach improves certifications for more than 80% of Tiny-Imagenet instances, yielding an on average 5 % increase in the associated certification. When incorporating training time processes that enhance the certified radius, our technique shows even more promising results, with a uniform 4 percentage point increase in the achieved certified radius.