Research map / Learning theory and algorithms / Prediction and decision losses
Expressivity of ReLU-Networks under Convex Relaxations
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Theoretical study of which CPWL function classes ReLU networks can precisely express under IBP, DeepPoly, triangle (Δ) and multi-neuron convex relaxations, showing gains for univariate functions but impossibility of single-neuron relaxations for multivariate convex monotone CPWL functions.
Problem
Whether the expressivity of ReLU networks under convex relaxations used in certification is fundamentally limited, given the known IBP limitation for convex univariate CPWL functions.
Approach
Systematically characterizes which CPWL function classes (monotone, convex, monotone-convex, general) can be encoded by ReLU networks whose analysis under each convex relaxation (IBP, DeepPoly-0/1, triangle, multi-neuron) is precise, proving univariate results and a multivariate impossibility for the max function under the triangle relaxation.
Key results
- Δ and DeepPoly can precisely express univariate convex CPWL functions, which IBP cannot.
- Δ permits exponentially larger solution spaces than DeepPoly for convex CPWL functions.
- No finite ReLU network can Δ-express the max function precisely, so single-neuron relaxations cannot express multivariate convex monotone CPWL functions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DeepPoly-0, DeepPoly-1, or Δ instead of IBP for univariate convex CPWL functions | ReLU networks analyzed with convex relaxations · Univariate convex CPWL functions | precise expressivity | Helped |
| Use any considered relaxation, including IBP, for univariate monotone CPWL functions | ReLU networks · Univariate monotone CPWL functions | precise expressivity | Helped |
| Use Δ instead of DeepPoly-0 or DeepPoly-1 | ReLU networks encoding univariate convex CPWL functions · Univariate convex CPWL functions | network solution space | Helped |
| Use a multi-neuron relaxation that analyzes all ReLUs jointly | Single-layer ReLU networks · Univariate CPWL functions | precise expressivity | Helped |
| Use any single-neuron convex relaxation, including the most precise Δ relaxation, for multivariate convex monotone CPWL functions | Finite ReLU networks · Multivariate convex monotone CPWL functions | precise expressivity | Hurt |
Surprising findings
- Even the simple function max(x,y) = y + relu(x-y) cannot be precisely analyzed by the triangle relaxation for any finite ReLU network, despite the exact analysis on boxes being trivial.
Limitations
- Results are theoretical and only cover the considered relaxations (IBP, DeepPoly, Δ, multi-neuron).
- Multivariate impossibility is shown only for single-neuron relaxations; multi-neuron and non-convex relaxations remain open.
- No empirical training experiments validate that more precise relaxations improve accuracy.
Experimental setup
Baselines: IBP DeepPoly-0 DeepPoly-1 Triangle relaxation Multi-Neuron relaxation
Builds on: interval bound propagation DeepPoly CROWN triangle relaxation (Δ)
Closest papers by meaning
- Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time (ICML 2024 · similarity 0.90)
- Convex Formulations for Training Two-Layer ReLU Neural Networks (ICLR 2025 · similarity 0.90)
- Compelling ReLU Networks to Exhibit Exponentially Many Linear Regions at Initialization and During Training (ICML 2025 · similarity 0.88)
- Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizes (NeurIPS 2024 · similarity 0.87)
- Stable Minima of ReLU Neural Networks Suffer from the Curse of Dimensionality: The Neural Shattering Phenomenon (NeurIPS 2025 · similarity 0.87)
- Loss Landscape of Shallow ReLU-like Neural Networks: Stationary Points, Saddle Escape, and Network Embedding (ICLR 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.