Research map / Learning theory and algorithms / Prediction and decision losses
Tightening Robustness Verification of MaxPool-based Neural Networks via Minimizing the Over-Approximation Zone
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.
Proposes Ti-Lin, provably neuron-wise tightest linear bounds for MaxPool, integrated into CNN-Cert, DeepPoly, ERAN and α,β-CROWN to certify more robust MaxPool-based CNNs and PointNets.
Problem
Incomplete robustness verification of MaxPool-based neural networks is loose because existing linear relaxations of the multi-variate MaxPool function do not minimize the over-approximation zone.
Approach
Derives upper linear bound through the endpoints of the input region's space diagonal (f(a), f(b)) and a lower bound selecting the input with largest midpoint, proven to be neuron-wise tightest for MaxPool, computable in O(pool_size × log^3) time.
Key results
- Ti-Lin improves certified accuracy over α,β-CROWN by up to 78.6% on CIFAR CNN 6-layer model, and over MaxLin by 28.6% in the same setting.
- On DeepPoly backsubstitution, Ti-Lin achieves up to 5.3× speedup over 3DCertify with almost the same runtime as DeepPoly.
- Ti-Lin improves certified accuracy over DeepPoly by up to 39.4% on MNIST CNN 8-layer.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the baseline MaxPool bounds with Ti-Lin neuron-wise tightest linear bounds | DeepPoly on MNIST CNN, 8 layers · MNIST | certified accuracy: 38.4 -> 77.8 | Helped |
| Replace the baseline MaxPool bounds with Ti-Lin neuron-wise tightest linear bounds | 3DCertify on MNIST CNN, 8 layers · MNIST | certified accuracy: 70.7 -> 77.8 | Helped |
| Replace the baseline MaxPool bounds with Ti-Lin neuron-wise tightest linear bounds | α, β-CROWN on CIFAR-10 CNN, 6 layers · CIFAR-10 | certified accuracy: 7.1 -> 85.7 | Helped |
| Replace MaxLin block-wise bounds with Ti-Lin neuron-wise tightest bounds | α, β-CROWN on CIFAR-10 CNN, 6 layers · CIFAR-10 | certified accuracy: 57.1 -> 85.7 | Helped |
| Replace ERAN's MaxPool bounds with Ti-Lin bounds | ERAN on CIFAR-10 CNN, 8 layers · CIFAR-10 | certified accuracy: 50.0 -> 58.3 | Helped |
| Replace the baseline MaxPool bounds with Ti-Lin neuron-wise tightest linear bounds | DeepPoly on CIFAR-10 CNN, 7 layers · CIFAR-10 | certified accuracy: 13.8 -> 37.9 | Helped |
| Replace the baseline MaxPool bounds with Ti-Lin neuron-wise tightest linear bounds | Ti-Lin integrated into DeepPoly on ModelNet40 64p FGSM · ModelNet40 | certified accuracy: 12.1 -> 13.6 | Helped |
| Replace α, β-CROWN MaxPool bounds with Ti-Lin bounds | α, β-CROWN on MNIST CNN, 8 layers · MNIST | certified accuracy: 0.0 -> 3.0 | Helped |
Surprising findings
- Transforming MaxPool into ReLU and affine layers (OSIP) costs considerably more time and yields coarser results.
- MaxLin and Ti-Lin complement each other: neither dominates across settings, motivating the Hybrid-Lin variant in the appendix.
Limitations
- Benefits are measured on specific benchmarks; networks come from prior works (3DCertify, ERAN, VNN-COMP, CNN-Cert).
- Tightness is neuron-wise per MaxPool layer; ReLU+MaxPool block-wise tightness is not addressed by this method alone.
- Only the MaxPool layer is relaxed; hardware is a single 48-core CPU server with 125 GB RAM and no GPU mentioned.
Experimental setup
Datasets: MNIST CIFAR-10 Tiny ImageNet ModelNet40
Benchmarks: MNIST CIFAR-10 ModelNet40
Metrics: certified accuracy average runtime speedup upper bound via PGD
Baselines: CNN-Cert DeepPoly 3DCertify MN-BaB ERAN OSIP α,β-CROWN MaxLin
Builds on: DeepPoly CROWN MaxLin PRIMA α,β-CROWN
Closest papers by meaning
- Towards General Robustness Verification of MaxPool-based Convolutional Neural Networks via Tightening Linear Approximation (CVPR 2024 · similarity 0.96)
- Tightening Robustness Verification of Convolutional Neural Networks with Fine-Grained Linear Approximation (AAAI 2021 · similarity 0.90)
- VNN: Verification-Friendly Neural Networks with Hard Robustness Guarantees (ICML 2024 · similarity 0.88)
- Probably Approximately Global Robustness Certification (ICML 2025 · similarity 0.87)
- Interpreting Robustness Proofs of Deep Neural Networks (ICLR 2024 · similarity 0.87)
- Certified but Private: Scalable Zero-Knowledge Proofs for the Formal Verification of Neural Networks (NeurIPS 2026 · similarity 0.86)
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.