Support Triangle Machine
summary
Presents a constructive algorithm that lifts single-neuron convex approximations into multi-neuron ones by iteratively decomposing each output coordinate into linear pieces, applying a geometric triangle lifting operation, and conjoining results to produce a multi-neuron approximation. Formalizes the problem as Convex Approximation Lifting and gives a correctness proof. Evaluated on sigmoid and tanh with box and polyhedron single-neuron domains; shows higher precision than Cartesian-product bounds, comparable precision to convex-hull methods but with better runtime, using a largest-area triangle heuristic.
AI-written summary · about
chapters (10)
- 0:00Support Triangle Machine intro
- 1:07Formal verification of neural nets
- 4:19Goals and prior work
- 5:01Problem formulation
- 7:33Observations enabling technique
- 9:03Support triangle properties
- 11:55Overall algorithm of Support Triangle Machine
- 13:01Evaluation methodology
- 15:34Contributions and future work
- 16:17Q&A
related talks
14mStatic analysis of ReLU neural networks with tropical polyhedra
23mPRIMA: General and Precise Neural Network Certification via Scalable Convex Hull
14mConvex Hull Approximation for Activation Functions
30mBoosting Multi-Neuron Convex Relaxation for Neural Network Verification
18mReLU Hull Approximation
52mFrom the Ball-proximal (Broximal) Point Method to Efficient Training of LLM
11mGeometric Methods for Machine Learning and Optimization
01h 51mUnderstanding Neural Networks (Somewhat)