Interval Universal Approximation for Neural Networks
summary
Proves an interval universal approximation theorem: for any continuous target and any practical squashable functions (monotone with one-sided limits) there exists a neural net whose interval abstract semantics approximate the set semantics arbitrarily closely. The constructive proof requires exponentially many neurons (exponential construction), and the related range-approximation (RA) decision is shown Σ2-intermediate and thus strictly harder than NP-complete under standard complexity assumptions. Consequence: certifiably robust networks always exist but cannot be built efficiently in general.
AI-written summary · about
chapters (8)
- 0:00Intro
- 0:16Adversarial Attack and Robustness
- 2:02Certified Robustness via Interval Abstract Interpretation
- 3:09Problem of Abstract Interpretation
- 5:17Interval Universal Approximation
- 6:46Limit of Interval Domain
- 11:00Formulation of RA
- 13:55Usages of Squashable Functions
related talks
31mAbstract Neural Networks
01h 51mUnderstanding Neural Networks (Somewhat)
19mAbstract Neural Networks
17mUniversality of Neural Networks
22mFormal Security Analysis of Neural Networks using Symbolic Intervals
01h 14mApproximation Power
56mThe mathematics of machine learning
59mTutorial: Statistical Learning Theory and Neural Networks I