Research map / Learning theory and algorithms / Sample complexity
Towards General Robustness Verification of MaxPool-based Convolutional Neural Networks via Tightening Linear Approximation
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 MaxLin, a robustness verifier for MaxPool-based CNNs that tightens single-neuron linear relaxations of MaxPool to obtain larger certified lower bounds and faster verification.
Problem
Certifying robustness of MaxPool-based CNNs under l1, l2, and l∞ perturbations is hard because MaxPool is multivariate and nonlinear; existing verifiers either lose precision (loose single-neuron bounds) or are too slow (multi-neuron relaxations).
Approach
Selects the first and second maximum of upper bounds and the max lower bound of MaxPool inputs to construct tighter closed-form linear upper/lower bounds, claims block-wise tightness for ReLU+MaxPool, and plugs these into CNN-Cert and 3DCertify via binary search for the certified lower bound.
Key results
- MaxLin improves average certified lower bound over CNN-Cert by up to 110.60% and over Ti-Lin by up to 49.26% on CNNs (Table 1).
- Against 3DCertify, MaxLin achieves up to 5.13× speedup and up to 39.94% larger certified bounds; vs DeepPoly up to 62.17% improvement (Table 2).
- On the Activation+MaxPool block volume experiment, MaxLin has the smallest over-approximation volume for ReLU+MaxPool and Adaptive-ReLU+MaxPool among baselines.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MaxLin’s tightened linear approximation for MaxPool instead of CNN-Cert’s MaxPool bounds | CNNs and LeNet on MNIST, CIFAR-10, and Tiny ImageNet · CNN-Cert benchmarks | certified lower bound: up to 110.60% improvement | Helped |
| Use MaxLin’s tightened linear approximation for MaxPool instead of Ti-Lin’s bounds | CNNs and LeNet on MNIST, CIFAR-10, and Tiny ImageNet · CNN-Cert benchmarks | certified lower bound: up to 49.26% improvement | Helped |
| Use MaxLin’s MaxPool bounds instead of DeepPoly’s | CNNs and LeNet · MNIST and CIFAR-10 ERAN benchmarks | certified lower bound: up to 62.17% improvement | Helped |
| Use MaxLin’s MaxPool bounds instead of 3DCertify’s | CNNs and LeNet · MNIST and CIFAR-10 ERAN benchmarks | certified lower bound: up to 39.94% improvement; -1.43↓ | Mixed |
| Use MaxLin rather than 3DCertify’s Double Description MaxPool bounds | CNNs and LeNet · MNIST and CIFAR-10 ERAN benchmarks | runtime speedup: up to 5.13× speedup | Helped |
| Replace the verifier’s MaxPool linear bounds with MaxLin while keeping the CNN-Cert framework | MaxPool-based networks · CNN-Cert benchmarks | runtime | No clear effect |
Surprising findings
- MaxLin is slightly worse than 3DCertify on MNIST LeNet Sigmoid (-1.43%), which the authors attribute to network-dependent verifier behavior.
Limitations
- Incomplete verifier: certified lower bounds are sound but not tight relative to the true robustness bound.
- Performance varies across networks; MaxLin is not uniformly best (e.g., LeNet Sigmoid vs 3DCertify).
Experimental setup
Datasets: MNIST CIFAR-10 Tiny ImageNet ModelNet40
Benchmarks: MNIST CIFAR-10 Tiny ImageNet ModelNet40 ERAN benchmarks
Metrics: certified lower bound bound improvement (%) average runtime speedup certified accuracy volume of over-approximation zone
Baselines: CNN-Cert DeepPoly 3DCertify Ti-Lin α,β-CROWN ERAN MN-BaB
Builds on: CNN-Cert DeepPoly 3DCertify Ti-Lin VeriNet
Closest papers by meaning
- Tightening Robustness Verification of MaxPool-based Neural Networks via Minimizing the Over-Approximation Zone (CVPR 2025 · similarity 0.96)
- Tightening Robustness Verification of Convolutional Neural Networks with Fine-Grained Linear Approximation (AAAI 2021 · similarity 0.91)
- VNN: Verification-Friendly Neural Networks with Hard Robustness Guarantees (ICML 2024 · similarity 0.88)
- Verification of Neural Networks Against Convolutional Perturbations via Parameterised Kernels (AAAI 2025 · similarity 0.87)
- Learning Better Certified Models from Empirically-Robust Teachers (NeurIPS 2026 · similarity 0.87)
- Probably Approximately Global Robustness Certification (ICML 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.