Approximation Power
summary
Shows that continuous univariate functions are representable as integrals of step/ReLU atoms by sampling the derivative or second derivative, and that infinite‑width sampling yields constructive approximations with log(1/ε) depth constructions for squaring/multiplication. Proves indicator on a box needs extra layer unless one uses exponentially many hyperplanes (≈2^d), gives an explicit Sobolev/Taylor local‑polynomial construction with depth log(1/ε) and width scaling polynomially in 1/ε, and provides L1 lower bound separations between shallow and deeper ReLU networks.
AI-written summary · about
chapters (9)
- 0:00Workshop introduction
- 1:26Defining approximation power
- 6:12Elementary universal approximation
- 12:30Univariate function approach
- 24:18Classical approximation theorems
- 34:41Multiplication and complexity
- 43:07Depth and network efficiency
- 50:25Bumpy functions and depth
- 1:02:00Taylor expansions and conclusion
related talks
01h 03mUnderstanding ReLU Networks Through Graph Problems and Polyhedra
32mTight Hardness Results for Training Depth-2 ReLU Networks
56mThe mathematics of machine learning
59mTutorial: Statistical Learning Theory and Neural Networks I
45mIs Deeper Better Only When Shallow Is Good?
19mInterval Universal Approximation for Neural Networks
30mComputational Barriers For Learning Some Generalized Linear Models
01h 04mRandomized Embeddings and Neural Networks