Estimation Contracts for Outlier-Robust Geometric Perception

• URL: http://arxiv.org/abs/2208.10521v1
• Date: Mon, 22 Aug 2022 18:01:49 GMT
• Title: Estimation Contracts for Outlier-Robust Geometric Perception
• Authors: Luca Carlone
• Abstract summary: Outlier-robust estimation is a fundamental problem and has been extensively investigated by statisticians practitioners. We provide conditions on the input under which modern estimation algorithms are guaranteed to recover an estimate close to the ground in the presence of outliers.
• Score: 25.105820975269506
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Outlier-robust estimation is a fundamental problem and has been extensively investigated by statisticians and practitioners. The last few years have seen a convergence across research fields towards "algorithmic robust statistics", which focuses on developing tractable outlier-robust techniques for high-dimensional estimation problems. Despite this convergence, research efforts across fields have been mostly disconnected from one another. This paper bridges recent work on certifiable outlier-robust estimation for geometric perception in robotics and computer vision with parallel work in robust statistics. In particular, we adapt and extend recent results on robust linear regressions (applicable to the low-outlier case with << 50% outliers) and list-decodable regression (applicable to the high-outlier case with >> 50% outliers) to the setup commonly found in robotics and vision, where (i) variables (e.g., rotations, poses) belong to a non-convex domain, (ii) measurements are vector-valued, and (iii) the number of outliers is not known a priori. The emphasis here is on performance guarantees: rather than proposing new algorithms, we provide conditions on the input measurements under which modern estimation algorithms are guaranteed to recover an estimate close to the ground truth in the presence of outliers. These conditions are what we call an "estimation contract". Besides the proposed extensions of existing results, we believe the main contributions of this paper are (i) to unify parallel research lines by pointing out commonalities and differences, (ii) to introduce advanced material (e.g., sum-of-squares proofs) in an accessible and self-contained presentation for the practitioner, and (iii) to point out a few immediate opportunities and open questions in outlier-robust geometric perception.

Related papers

• Risk and cross validation in ridge regression with correlated samples [72.59731158970894]
  We provide training examples for the in- and out-of-sample risks of ridge regression when the data points have arbitrary correlations. We further extend our analysis to the case where the test point has non-trivial correlations with the training set, setting often encountered in time series forecasting. We validate our theory across a variety of high dimensional data.
  arXiv  Detail & Related papers  (2024-08-08T17:27:29Z)
• Deep Learning-Based Object Pose Estimation: A Comprehensive Survey [73.74933379151419]
  We discuss the recent advances in deep learning-based object pose estimation. Our survey also covers multiple input data modalities, degrees-of-freedom of output poses, object properties, and downstream tasks.
  arXiv  Detail & Related papers  (2024-05-13T14:44:22Z)
• Differentially Private Linear Regression with Linked Data [3.9325957466009203]
  Differential privacy, a mathematical notion from computer science, is a rising tool offering robust privacy guarantees. Recent work focuses on developing differentially private versions of individual statistical and machine learning tasks. We present two differentially private algorithms for linear regression with linked data.
  arXiv  Detail & Related papers  (2023-08-01T21:00:19Z)
• Fine-grained analysis of non-parametric estimation for pairwise learning [9.676007573960383]
  We are concerned with the generalization performance of non-parametric estimation for pairwise learning. Our results can be used to handle a wide range of pairwise learning problems including ranking, AUC, pairwise regression and metric and similarity learning.
  arXiv  Detail & Related papers  (2023-05-31T08:13:14Z)
• Uncertainty-Aware Instance Reweighting for Off-Policy Learning [63.31923483172859]
  We propose a Uncertainty-aware Inverse Propensity Score estimator (UIPS) for improved off-policy learning. Experiment results on synthetic and three real-world recommendation datasets demonstrate the advantageous sample efficiency of the proposed UIPS estimator.
  arXiv  Detail & Related papers  (2023-03-11T11:42:26Z)
• Assaying Out-Of-Distribution Generalization in Transfer Learning [103.57862972967273]
  We take a unified view of previous work, highlighting message discrepancies that we address empirically. We fine-tune over 31k networks, from nine different architectures in the many- and few-shot setting.
  arXiv  Detail & Related papers  (2022-07-19T12:52:33Z)
• Outlier-Robust Geometric Perception: A Novel Thresholding-Based Estimator with Intra-Class Variance Maximization [4.3487328134753795]
  We present a novel general-purpose robust estimator TIVM (Thresholding with Intra-class Variance Maximization) It can collaborate with standard non-minimal solvers to efficiently reject outliers for geometric perception problems. Our estimator can retain approximately the same level of robustness even when the inlier-noise statistics of the problem are fully unknown.
  arXiv  Detail & Related papers  (2022-04-04T08:57:34Z)
• ROBIN: a Graph-Theoretic Approach to Reject Outliers in Robust Estimation using Invariants [30.19476775410544]
  Outliers are typically the result of incorrect data association or feature matching. Current approaches for robust estimation fail to produce accurate estimates in the presence of many outliers. This paper develops an approach to prune outliers.
  arXiv  Detail & Related papers  (2020-11-07T02:09:33Z)
• $\gamma$-ABC: Outlier-Robust Approximate Bayesian Computation Based on a Robust Divergence Estimator [95.71091446753414]
  We propose to use a nearest-neighbor-based $gamma$-divergence estimator as a data discrepancy measure. Our method achieves significantly higher robustness than existing discrepancy measures.
  arXiv  Detail & Related papers  (2020-06-13T06:09:27Z)
• Generating Artificial Outliers in the Absence of Genuine Ones -- a Survey [0.0]
  The literature features different approaches to generate artificial outliers. We start by clarifying the terminology in the field, which varies from publication to publication. We group the approaches by their general concepts and how they make use of genuine instances.
  arXiv  Detail & Related papers  (2020-06-05T19:33:10Z)
• High-Dimensional Robust Mean Estimation via Gradient Descent [73.61354272612752]
  We show that the problem of robust mean estimation in the presence of a constant adversarial fraction can be solved by gradient descent. Our work establishes an intriguing connection between the near non-lemma estimation and robust statistics.
  arXiv  Detail & Related papers  (2020-05-04T10:48:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.