Research map / Learning theory and algorithms / Sample complexity

RANSAC Scoring Done Right

NeurIPS 2026 · Learning theory and algorithms › Sample complexity · approach: Optimal mean estimation and subsampling · 0 citations (OpenAlex)

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 a scale-free RANSAC scoring function that analytically marginalizes the inlier noise scale under an Inverse-Gamma prior for a fixed inlier partition, then optimizes over partitions via an O(N log N) sort-and-sweep.

Problem

RANSAC model scoring functions (inlier counting, MSAC, GaU, MAGSAC++) depend on a threshold tied to the inlier scale, which must be estimated from contaminated data or hand-tuned.

Approach

Reverse the elimination order: for a fixed inlier partition, marginalize sigma in closed form under a conjugate Inverse-Gamma prior (Jeffreys as limit), then maximize over partitions, yielding a closed-form score in which the inlier scale does not appear, computed by sort-and-sweep.

Key results

• On PhotoTourism the proposed IG variants reach within 0.006 degrees of their asymptote of 0.77 degrees already at 2 validation pairs, while MSAC, GaU, MAGSAC++ need about 1024 pairs.
• On HEB, IG-Robust achieves 7.65 degree asymptote vs 7.85 degrees for the best threshold-based baseline.
• Proposed methods' cross-trial std at 2 validation pairs is 0.002-0.019 degrees vs 0.05-0.35 for baselines (30-100x gap).

Surprising findings

• Oracle per-pair envelopes invert the ordering: the proposed methods have the highest per-pair-best error, because their hyperparameter mostly calibrates score values rather than model selection.
• Jeffreys (non-informative) prior is the worst of the three proposed variants on HEB at small validation sizes.

Limitations

• On HEB, low inlier cardinality (median ~10 per pair) and structured outliers make the uniform-outlier assumption violated and IG-MLE fragile.
• Informative-prior variants need ground-truth annotations on validation pairs.
• Hyperparameter a still required, though it is an outlier half-width rather than inlier scale.

Experimental setup

Datasets: PhotoTourism ETH3D Homography Estimation Benchmark (HEB)

Benchmarks: PhotoTourism ETH3D HEB

Metrics: median rotation error (SO(3) angular distance) std of expected test error across validation trials

Baselines: RANSAC MSAC GaU MAGSAC++

Builds on: MAGSAC++ MSAC MLESAC Shekhovtsov unified threshold framework LO-RANSAC

Closest papers by meaning

• Learning To Find Good Models in RANSAC (CVPR 2022 · similarity 0.88)
• MAGSAC: Marginalizing Sample Consensus (CVPR 2019 · similarity 0.87)
• LAION-C: An Out-of-Distribution Benchmark for Web-Scale Vision Models (ICML 2025 · similarity 0.83)
• PARSAC: Accelerating Robust Multi-Model Fitting with Parallel Sample Consensus (AAAI 2024 · similarity 0.82)
• Foundation Model-oriented Robustness: Robust Image Model Evaluation with Pretrained Models (ICLR 2024 · similarity 0.81)
• RODEO: Robust Outlier Detection via Exposing Adaptive Out-of-Distribution Samples (ICML 2024 · similarity 0.81)