WraLU: Fast and Precise ReLU Hull Approximation

Overview

WraLU is a fast and precise approach to over-approximating the convex hull of the ReLU function (referred to as the ReLU hull), one of the most used activation functions. POPL’24 (the 51st ACM SIGPLAN Symposium on Principles of Programming Languages).

Key Idea

Our key insight is to formulate a convex polytope that “wraps” the ReLU hull, by reusing the linear pieces of the ReLU function as the lower faces and constructing upper faces that are adjacent to the lower faces. The upper faces can be efficiently constructed based on the edges and vertices of the lower faces, given that an n-dimensional hyperplane can be determined by an (n−1)-dimensional hyperplane and a point outside of it.

Performance Highlights

• Up to 50% fewer constraints, reaching comparable or better precision in less time — the figure the paper’s abstract reports
• Construction is bookkeeping over the ReLU’s own edges and vertices, so cost grows with the polytope’s combinatorics rather than with a geometry search
• Handles arbitrary input polytopes and higher-dimensional cases
• Used in verification experiments on CNNs and ResNet-style models with tens of thousands of neurons
• Designed for LP-based neural network verification pipelines that benefit from tighter ReLU relaxations

How It Works

1. Lower Faces: Reuse the linear pieces of the ReLU function directly
2. Upper Face Construction: Build upper faces adjacent to lower faces using edge and vertex information
3. Wrapping Polytope: The resulting convex polytope tightly wraps the ReLU hull
4. Integration: Feed the constraints to LP solvers for neural network verification

Related Tools

• WraAct: Extension to general activation functions (Sigmoid, Tanh, MaxPool)
• wraact (library): Unified Python library for hull approximation

@article{ma2024relu,
  author = {Ma, Zhongkui and Li, Jiaying and Bai, Guangdong},
  title = {ReLU Hull Approximation},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {8},
  number = {POPL},
  pages = {2260--2287},
  year = {2024},
  publisher = {ACM New York, NY, USA}
}