Research map / Learning theory and algorithms / Combinatorial and search optimization
Scaling the Convex Barrier with Sparse Dual Algorithms
Alessandro De Palma, Harkirat Singh Behl, Rudy Bunel, Philip H.S. Torr, M. Pawan Kumar
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Active Set (600 iterations, initialized from 500 Big-M iterations) instead of Gurobi cut | Active Set bounding · CIFAR-10 incomplete verification (SGD-trained network) | bound tightness and runtime: 600 iterations; around 1/20th of the time | Improved |
| run Active Set for a larger budget (1050 or 1650 iterations) | Active Set bounding · CIFAR-10 incomplete verification (SGD-trained network) | bound tightness vs Gurobi cut: 1050 iterations; 1650 iterations | Improved |
| use the Big-M dual solver instead of BDD+ at equal runtime | dual solver for the Planet relaxation · CIFAR-10 incomplete verification (SGD-trained network) | gap to Gurobi Planet bound | Improved |
| add the tighter relaxation via a few (80) Active Set iterations instead of Big-M, same time | Big-M initial dual · CIFAR-10 incomplete verification (SGD-trained network) | improvement over Planet bounds: 80 iterations | Improved |
| use Saddle Point for few (80) iterations instead of Big-M | Big-M initial dual · CIFAR-10 incomplete verification (SGD-trained network) | improvement over Planet bounds: 80 iterations | No clear effect |
| initialize Saddle Point with Active Set iterations (AS-SP) rather than Big-M | Saddle Point · CIFAR-10 incomplete verification (SGD-trained network) | average bound tightness at equal time | Improved |
| use Saddle Point instead of Active Set when run for longer on a 2x7000 fully connected network | Active Set (limited to 1 cut per neuron by memory) · CIFAR-10 incomplete verification (fully connected, width 7000, 500 images) | bound tightness vs Gurobi cut: Active Set limited to a single constraint per neuron | Improved |
| running Active Set with only a single cut per neuron (memory-limited) (ablation) | Active Set · CIFAR-10 incomplete verification (fully connected, width 7000, 500 images) | bound tightness vs Gurobi cut | Hurt |
| run solvers on CPU instead of GPU | Active Set and Saddle Point · CIFAR-10 incomplete verification (SGD-trained network) | speed-accuracy trade-off vs Gurobi cut | Mixed |
Closest papers by meaning
- Scaling the Convex Barrier with Active Sets (ICLR 2021 · similarity 0.98)
- The Convex Relaxation Barrier, Revisited: Tightened Single-Neuron Relaxations for Neural Network Verification (NeurIPS 2020 · similarity 0.92)
- SDP-CROWN: Efficient Bound Propagation for Neural Network Verification with Tightness of Semidefinite Programming (ICML 2025 · similarity 0.90)
- Clip-and-Verify: Linear Constraint-Driven Domain Clipping for Accelerating Neural Network Verification (NeurIPS 2025 · similarity 0.88)
- Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time (ICML 2024 · similarity 0.87)
- Random Sparse Lifts: Construction, Analysis and Convergence of finite sparse networks (ICLR 2024 · 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.
