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

Lassoelastic netonline algorithmconformal predictionmodel-free inference

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

(15)

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

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)