ReLU Hull Approximation
summary
Proposes WraLU, a fast algorithm that builds a convex polytope wrapping the ReLU hull by reusing the two linear pieces as lower faces and constructs upper faces from edges and vertices (one hyperplane per (n−1)d hyperplane plus a point). Implements WraLU in PRIMA, compares to exact MILP and approximations (SBM+PDDM, triangle relaxation), and reports tighter approximations with fewer constraints and reduces LP constraints by up to half; exact in low-dimensional cases, heuristic but scalable to higher dimensions.
AI-written summary · about
chapters (12)
- 0:00ReLU Hull Approximation intro
- 0:23Neural network verification importance
- 1:05Neural network verification
- 2:07Exact vs approximate verification
- 2:53Linear constraints for ReLU
- 3:37ReLU Hull in 3D
- 5:53High-dimensional ReLU Hull
- 7:22Efficiency and precision optimizations
- 8:28Verification methods evaluation
- 9:32SODA framework integration
- 10:17Future work and generalization
- 11:07Q&A
related talks
14mConvex Hull Approximation for Activation Functions
01h 03mUnderstanding ReLU Networks Through Graph Problems and Polyhedra
14mStatic analysis of ReLU neural networks with tropical polyhedra
28mStatic analysis of ReLU neural networks with tropical polyhedra
23mPRIMA: General and Precise Neural Network Certification via Scalable Convex Hull
54mPrimal-Dual Algorithms for Hyperbolic Programming Problems
20mSupport Triangle Machine
01h 14mApproximation Power