Fast exact conformalization of the Lasso using piecewise linear homotopy

DOI10.1093/BIOMET/ASZ046MaRDI QIDQ5212903zbMATH OpenOpenAlexWikidataFDO

Authors Jing Lei

Publication date 30 January 2020

Published in Biometrika (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.00427

zbMATH Keywords

conformal predictionelastic netLassomodel-free inferenceonline algorithm

Mathematics Subject Classification ID

Ridge regression; shrinkage estimators (Lasso) (62J07) Statistics on metric spaces (62R20)

Abstract: Conformal prediction is a general method that converts almost any point predictor to a prediction set. The resulting set keeps good statistical properties of the original estimator under standard assumptions, and guarantees valid average coverage even when the model is misspecified. A main challenge in applying conformal prediction in modern applications is efficient computation, as it generally requires an exhaustive search over the entire output space. In this paper we develop an exact and computationally efficient conformalization of the Lasso and elastic net. The method makes use of a novel piecewise linear homotopy of the Lasso solution under perturbation of a single input sample point. As a by-product, we provide a simpler and better justified online Lasso algorithm, which may be of independent interest. Our derivation also reveals an interesting accuracy-stability trade-off in conformal inference, which is analogous to the bias-variance trade-off in traditional parameter estimation. The practical performance of the new algorithm is demonstrated using both synthetic and real data examples.

Recommendations

• A tutorial on conformal prediction
• Nonparametric predictive distributions based on conformal prediction
• Cross-conformal predictors
• Distribution-free predictive inference for regression
• Regression conformal prediction with random forests

Cited in

(18)

• Predictive inference with the jackknife+
• Comparing six shrinkage estimators with large sample theory and asymptotically optimal prediction intervals
• Methods to compute prediction intervals: a review and new results
• Conformal prediction: a unified review of theory and new challenges
• Local Linear Convergence of ISTA and FISTA on the LASSO Problem
• A fast conformal classifier based on multi-output extreme learning machine
• An homotopy method for l _p regression provably beyond self-concordance and in input-sparsity time
• Conformal Prediction: A Gentle Introduction
• Conditional predictive inference for stable algorithms
• Root-finding approaches for computing conformal prediction set
• Accelerate the warm-up stage in the Lasso computation via a homotopic approach
• Conformal prediction beyond exchangeability
• Training-conditional coverage for distribution-free predictive inference
• Discretized conformal prediction for efficient distribution-free inference
• A confidence machine for sparse high-order interaction model
• Conditionality principle under unconstrained randomness
• Conformal prediction for multivariate responses with Euclidean likelihood
• Estimating the false discovery rate of variable selection

This page was built for publication: Fast exact conformalization of the Lasso using piecewise linear homotopy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212903)