Building Conformal Prediction Intervals with Approximate Message Passing

• URL: http://arxiv.org/abs/2410.16493v1
• Date: Mon, 21 Oct 2024 20:34:33 GMT
• Title: Building Conformal Prediction Intervals with Approximate Message Passing
• Authors: Lucas Clarté, Lenka Zdeborová,
• Abstract summary: Conformal prediction is a powerful tool for building prediction intervals that are valid in a distribution-free way. We propose a novel algorithm based on Approximate Message Passing (AMP) to accelerate the computation of prediction intervals. We show that our method produces prediction intervals that are close to the baseline methods, while being orders of magnitude faster.
• Score: 14.951392270119461
• License:
• Abstract: Conformal prediction has emerged as a powerful tool for building prediction intervals that are valid in a distribution-free way. However, its evaluation may be computationally costly, especially in the high-dimensional setting where the dimensionality and sample sizes are both large and of comparable magnitudes. To address this challenge in the context of generalized linear regression, we propose a novel algorithm based on Approximate Message Passing (AMP) to accelerate the computation of prediction intervals using full conformal prediction, by approximating the computation of conformity scores. Our work bridges a gap between modern uncertainty quantification techniques and tools for high-dimensional problems involving the AMP algorithm. We evaluate our method on both synthetic and real data, and show that it produces prediction intervals that are close to the baseline methods, while being orders of magnitude faster. Additionally, in the high-dimensional limit and under assumptions on the data distribution, the conformity scores computed by AMP converge to the one computed exactly, which allows theoretical study and benchmarking of conformal methods in high dimensions.

Related papers

• On Statistical Rates and Provably Efficient Criteria of Latent Diffusion Transformers (DiTs) [12.810268045479992]
  We study the universal approximation and sample complexity of the DiTs score function. We show that latent DiTs have the potential to bypass the challenges associated with the high dimensionality of initial data.
  arXiv  Detail & Related papers  (2024-07-01T08:34:40Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  In this paper, we propose a distributed sampling scheme based on the alternating direction method of multipliers. We provide both theoretical guarantees of our algorithm's convergence and experimental evidence of its superiority to the state-of-the-art. In simulation, we deploy our algorithm on linear and logistic regression tasks and illustrate its fast convergence compared to existing gradient-based methods.
  arXiv  Detail & Related papers  (2024-01-29T02:08:40Z)
• Scalable computation of prediction intervals for neural networks via matrix sketching [79.44177623781043]
  Existing algorithms for uncertainty estimation require modifying the model architecture and training procedure. This work proposes a new algorithm that can be applied to a given trained neural network and produces approximate prediction intervals.
  arXiv  Detail & Related papers  (2022-05-06T13:18:31Z)
• Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
  We study algorithms for estimating the statistical leverage scores of rectangular dense or sparse matrices of arbitrary rank. Our approach is based on combining rank revealing methods with compositions of dense and sparse randomized dimensionality reduction transforms.
  arXiv  Detail & Related papers  (2021-05-23T19:21:55Z)
• An AI-Assisted Design Method for Topology Optimization Without Pre-Optimized Training Data [68.8204255655161]
  An AI-assisted design method based on topology optimization is presented, which is able to obtain optimized designs in a direct way. Designs are provided by an artificial neural network, the predictor, on the basis of boundary conditions and degree of filling as input data.
  arXiv  Detail & Related papers  (2020-12-11T14:33:27Z)
• Amortized Conditional Normalized Maximum Likelihood: Reliable Out of Distribution Uncertainty Estimation [99.92568326314667]
  We propose the amortized conditional normalized maximum likelihood (ACNML) method as a scalable general-purpose approach for uncertainty estimation. Our algorithm builds on the conditional normalized maximum likelihood (CNML) coding scheme, which has minimax optimal properties according to the minimum description length principle. We demonstrate that ACNML compares favorably to a number of prior techniques for uncertainty estimation in terms of calibration on out-of-distribution inputs.
  arXiv  Detail & Related papers  (2020-11-05T08:04:34Z)
• Conformal prediction for time series [16.38369532102931]
  textttEnbPI wraps around ensemble predictors, which is closely related to conformal prediction (CP) but does not require data exchangeability. We perform extensive simulation and real-data analyses to demonstrate its effectiveness compared with existing methods.
  arXiv  Detail & Related papers  (2020-10-18T21:05:32Z)
• Frequency Estimation in Data Streams: Learning the Optimal Hashing Scheme [3.7565501074323224]
  We present a novel approach for the problem of frequency estimation in data streams that is based on optimization and machine learning. The proposed approach exploits an observed stream prefix to near-optimally hash elements and compress the target frequency distribution. We show that the proposed approach outperforms existing approaches by one to two orders of magnitude in terms of its average (per element) estimation error and by 45-90% in terms of its expected magnitude of estimation error.
  arXiv  Detail & Related papers  (2020-07-17T22:15:22Z)
• Asymptotic Analysis of an Ensemble of Randomly Projected Linear Discriminants [94.46276668068327]
  In [1], an ensemble of randomly projected linear discriminants is used to classify datasets. We develop a consistent estimator of the misclassification probability as an alternative to the computationally-costly cross-validation estimator. We also demonstrate the use of our estimator for tuning the projection dimension on both real and synthetic data.
  arXiv  Detail & Related papers  (2020-04-17T12:47:04Z)
• Estimating Basis Functions in Massive Fields under the Spatial Mixed Effects Model [8.528384027684194]
  For massive datasets, fixed rank kriging using the Expectation-Maximization (EM) algorithm for estimation has been proposed as an alternative to the usual but computationally prohibitive kriging method. We develop an alternative method that utilizes the Spatial Mixed Effects (SME) model, but allows for additional flexibility by estimating the range of the spatial dependence between the observations and the knots via an Alternating Expectation Conditional Maximization (AECM) algorithm. Experiments show that our methodology improves estimation without sacrificing prediction accuracy while also minimizing the additional computational burden of extra parameter estimation.
  arXiv  Detail & Related papers  (2020-03-12T19:36:40Z)
• Scalable Distributed Approximation of Internal Measures for Clustering Evaluation [5.144809478361603]
  Internal measure for clustering evaluation is the silhouette coefficient, whose computation requires a quadratic number of distance calculations. We present the first scalable algorithm to compute such a rigorous approximation for the evaluation of clusterings based on any metric distances. We also prove that the algorithm can be adapted to obtain rigorous approximations of other internal measures of clustering quality, such as cohesion and separation.
  arXiv  Detail & Related papers  (2020-03-03T10:28:14Z)

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.