AI Paper Atlas

Research map / Learning theory and algorithms / Combinatorial and search optimization

PREMAP: A Unifying PREiMage APproximation Framework for Neural Networks

Xiyue Zhang, Benjie Wang, Marta Kwiatkowska, Huan Zhang

JMLR 2025 · Learning theory and algorithms › Combinatorial and search optimization · approach: Semidefinite relaxations for verification · 6 citations (OpenAlex)

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 PREMAP approximation instead of exact preimage computationpreimage generation · Vehicle Parking and VCAScomputation time: Exact 3174.709 s vs PREMAP 1.120 s (under-approx) on Vehicle; VCAS 6363.272 -> 10.775Improved
use PREMAP instead of exact preimage to describe the preimagepolytope count · Vehicle Parkingnumber of polytopes: average reduction of 69.2%Improved
use PREMAP under-approximation instead of exact preimagepolytope count · VCASnumber of polytopes: 131 -> 15 (88.5% reduction)Improved
use PREMAP over-approximation instead of exact preimagepolytope count · VCASnumber of polytopes: 131 -> 1 (99.2% reduction)Improved
use PREMAP instead of Invprop for under-approximationpreimage under-approximation · Vehicle Parkingcoverage ratio: 0.909 -> 0.945 (average Cov)Improved
use PREMAP instead of Invprop for under-approximation timepreimage under-approximation · Vehicle Parkingtime (s): 2.403 -> 1.120Improved
use Invprop instead of PREMAP for over-approximationpreimage over-approximation · Vehicle Parkingcoverage ratio and time: PREMAP 1.081 vs Invprop 1.059 coverage; time 1.148 vs 0.840Hurt
add new input-feature splitting heuristic over prior method (ablation)PREMAP refinement · preimage approximationcomputation time to same precision: 49.7% (avg.) computation time of the prior methodImproved
add Lagrangian relaxation for neuron splitting constraints (ablation)PREMAP · MNIST preimage approximationprecision: precision gains of up to 58.6% (avg.)Improved

Later papers that compared with this method

1 later accepted paper reports PREMAP as a baseline in their results tables; 1 of them report a better number on most of the results they share with it.

Matched by method name in results tables read by AI. Authors' own tables tend to favour the newer method, and a comparison can be missed when a method is renamed.

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