Understanding ReLU Networks Through Graph Problems and Polyhedra
summary
Shows exact representability results: continuous piecewise‑linear functions equal maxima of affine pieces via Wang and Sun, so ReLU nets need only log2 depth for integer weights but one hidden layer cannot do max of three. New construction compresses depth—max of five in two hidden layers and a general log3 upper bound using Newton polytopes, Minkowski sums and polyhedral decompositions. Also builds polynomial‑size ReLU networks for minimum spanning tree and max‑flow; monotone/input‑convex nets face exponential size lower bounds via (virtual) extension complexity for matching and TSP.
AI-written summary · about
chapters (11)
- 0:00ReLU networks and polyhedra
- 3:21Expressivity of ReLU networks
- 8:20Piecewise linear ReLU functions
- 12:58Depth complexity of ReLU
- 17:44Lower bounds on ReLU depth
- 22:20Polyhedral geometry for ReLU
- 36:41ReLU networks for graph problems
- 43:51Lower bounds via extension complexity
- 53:10Virtual extension complexity
- 56:03Summary of ReLU networks
- 1:02:59Q&A on ReLU
related talks
14mStatic analysis of ReLU neural networks with tropical polyhedra
28mStatic analysis of ReLU neural networks with tropical polyhedra
32mTight Hardness Results for Training Depth-2 ReLU Networks
30mComputational Barriers For Learning Some Generalized Linear Models
18mReLU Hull Approximation
01h 04mNeural Networks meet Nonparametric Regression: Generalization by Weight Decay and Large...
01h 14mApproximation Power
01h 04mRandomized Embeddings and Neural Networks