AI Paper Atlas

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

JMLR 2024 · Learning theory and algorithms › Combinatorial and search optimization · approach: Semidefinite relaxations for verification

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 changedWhereMeasuredEffect
use Active Set (600 iterations, initialized from 500 Big-M iterations) instead of Gurobi cutActive Set bounding · CIFAR-10 incomplete verification (SGD-trained network)bound tightness and runtime: 600 iterations; around 1/20th of the timeImproved
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 iterationsImproved
use the Big-M dual solver instead of BDD+ at equal runtimedual solver for the Planet relaxation · CIFAR-10 incomplete verification (SGD-trained network)gap to Gurobi Planet boundImproved
add the tighter relaxation via a few (80) Active Set iterations instead of Big-M, same timeBig-M initial dual · CIFAR-10 incomplete verification (SGD-trained network)improvement over Planet bounds: 80 iterationsImproved
use Saddle Point for few (80) iterations instead of Big-MBig-M initial dual · CIFAR-10 incomplete verification (SGD-trained network)improvement over Planet bounds: 80 iterationsNo clear effect
initialize Saddle Point with Active Set iterations (AS-SP) rather than Big-MSaddle Point · CIFAR-10 incomplete verification (SGD-trained network)average bound tightness at equal timeImproved
use Saddle Point instead of Active Set when run for longer on a 2x7000 fully connected networkActive 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 neuronImproved
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 cutHurt
run solvers on CPU instead of GPUActive Set and Saddle Point · CIFAR-10 incomplete verification (SGD-trained network)speed-accuracy trade-off vs Gurobi cutMixed

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy