On testing networks that compute ...
summary
Introduces a property-testing model for fully connected feedforward ReLU networks where distance means changing at most an epsilon-fraction of weights per layer to get a function that differs on at most delta fraction of inputs. Gives a tester that decides whether a network computes the zero function or is far using only poly(1/epsilon) queries (and polylog(1/delta)) independent of n,m — samples a small set of hidden nodes and inputs and rejects if a scaled sum is large. Extends to constant-depth and multiple outputs, proves the distribution-free setting needs much larger sample complexity, and shows one-sided testers can require Omega(m).
AI-written summary · about
chapters (10)
- 0:00Introduction
- 3:59Motivation for testing neural networks
- 8:06Model definition of layered networks
- 13:10Focus on one-hidden-layer networks
- 19:53Epsilon-delta distance in networks
- 27:03Query complexity and testability
- 29:13Testing zero and OR functions
- 33:58Extensions to multiple layers and outputs
- 34:44Distribution-free testing challenges
- 35:32Open problems and future directions
related talks
32mFinetuning Stable Diffusion with low-rank adaptation techniques
23mWorst-Case to Expander-Case Reductions
28mEpic Fail: Emulators can tolerate some edge faults for free
01h 31mCircuits of Bounded Depth
47mInvariance, Geometry and Deep Neural Networks
01h 01mExact Algorithms from FPT Algorithms
40mResilience of 3-Majority Dynamics to Non-Uniform Schedulers
01h 30mDeep Learning Techniques for Monocular Depth Estimation