Universal Approximation with Certified Networks

2019/09/30 by Maximilian Baader, Baader, Maximilian, Matthew Mirman +3
Computer Science · Mathematics · #Adversarial Robustness in Machine Learning #Domain Adaptation and Few-Shot Learning #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.1909.13846

ICLR 2020

openalex publication_date 2019/09/30 · arxiv created 2020/01/14 · arxiv updated 2020/01/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Training neural networks to be certifiably robust is critical to ensure their safety against adversarial attacks. However, it is currently very difficult to train a neural network that is both accurate and certifiably robust. In this work we take a step towards addressing this challenge. We prove that for every continuous function f, there exists a network n such that: (i) n approximates f arbitrarily close, and (ii) simple interval bound propagation of a region B through n yields a result that is arbitrarily close to the optimal output of f on B. Our result can be seen as a Universal Approximation Theorem for interval-certified ReLU networks. To the best of our knowledge, this is the first work to prove the existence of accurate, interval-certified networks.

Citations

• Gradient-based learning applied to document recognition
• Efficient Formal Safety Analysis of Neural Networks
• Semidefinite relaxations for certifying robustness to adversarial examples
• On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models
• Certified Adversarial Robustness via Randomized Smoothing
• A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networks
• Universal Lipschitz Approximation in Bounded Depth Neural Networks
• Provable defenses against adversarial examples via the convex outer adversarial polytope
• Learning Multiple Layers of Features from Tiny Images

Related

• Make Interval Bound Propagation great again
• On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models
• Understanding Certified Training with Interval Bound Propagation
• Expected Tight Bounds for Robust Training
• Fast and Stable Interval Bounds Propagation for Training Verifiably Robust Models