Parametric Programming Approach for More Powerful and General Lasso Selective Inference

• URL: http://arxiv.org/abs/2004.09749v3
• Date: Mon, 22 Feb 2021 13:18:36 GMT
• Title: Parametric Programming Approach for More Powerful and General Lasso Selective Inference
• Authors: Vo Nguyen Le Duy, Ichiro Takeuchi
• Abstract summary: Selective Inference (SI) has been actively studied in the past few years for conducting inference on the features of linear models. The main limitation of the original SI approach for Lasso is that the inference is conducted not only conditional on the selected features but also on their signs. We propose a parametric programming-based method that can conduct SI without conditioning on signs even when we have thousands of active features.
• Score: 25.02674598600182
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Selective Inference (SI) has been actively studied in the past few years for conducting inference on the features of linear models that are adaptively selected by feature selection methods such as Lasso. The basic idea of SI is to make inference conditional on the selection event. Unfortunately, the main limitation of the original SI approach for Lasso is that the inference is conducted not only conditional on the selected features but also on their signs -- this leads to loss of power because of over-conditioning. Although this limitation can be circumvented by considering the union of such selection events for all possible combinations of signs, this is only feasible when the number of selected features is sufficiently small. To address this computational bottleneck, we propose a parametric programming-based method that can conduct SI without conditioning on signs even when we have thousands of active features. The main idea is to compute the continuum path of Lasso solutions in the direction of a test statistic, and identify the subset of the data space corresponding to the feature selection event by following the solution path. The proposed parametric programming-based method not only avoids the aforementioned computational bottleneck but also improves the performance and practicality of SI for Lasso in various respects. We conduct several experiments to demonstrate the effectiveness and efficiency of our proposed method.

Related papers

• Prompt Optimization with EASE? Efficient Ordering-aware Automated Selection of Exemplars [66.823588073584]
  Large language models (LLMs) have shown impressive capabilities in real-world applications. The quality of these exemplars in the prompt greatly impacts performance. Existing methods fail to adequately account for the impact of exemplar ordering on the performance.
  arXiv  Detail & Related papers  (2024-05-25T08:23:05Z)
• Efficient Weighting Schemes for Auditing Instant-Runoff Voting Elections [57.67176250198289]
  AWAIRE involves adaptively weighted averages of test statistics, essentially "learning" an effective set of hypotheses to test. We explore schemes and settings more extensively, to identify and recommend efficient choices for practice. A limitation of the current AWAIRE implementation is its restriction to a small number of candidates.
  arXiv  Detail & Related papers  (2024-02-18T10:13:01Z)
• Causal Feature Selection via Transfer Entropy [59.999594949050596]
  Causal discovery aims to identify causal relationships between features with observational data. We introduce a new causal feature selection approach that relies on the forward and backward feature selection procedures. We provide theoretical guarantees on the regression and classification errors for both the exact and the finite-sample cases.
  arXiv  Detail & Related papers  (2023-10-17T08:04:45Z)
• Bounded P-values in Parametric Programming-based Selective Inference [23.35466397627952]
  We introduce a procedure to reduce the computational cost while guaranteeing the desired precision, by proposing a method to compute the lower and upper bounds of p-values. We demonstrate the effectiveness of the proposed method in hypothesis testing problems for feature selection in linear models and attention region identification in deep neural networks.
  arXiv  Detail & Related papers  (2023-07-21T04:55:03Z)
• Generalizing Bayesian Optimization with Decision-theoretic Entropies [102.82152945324381]
  We consider a generalization of Shannon entropy from work in statistical decision theory. We first show that special cases of this entropy lead to popular acquisition functions used in BO procedures. We then show how alternative choices for the loss yield a flexible family of acquisition functions.
  arXiv  Detail & Related papers  (2022-10-04T04:43:58Z)
• Black-box Selective Inference via Bootstrapping [5.960626580825523]
  Conditional selective inference requires an exact characterization of the selection event, which is often unavailable except for a few examples like the lasso. This work addresses this challenge by introducing a generic approach to estimate the selection event, facilitating feasible inference conditioned on the selection event.
  arXiv  Detail & Related papers  (2022-03-28T05:18:21Z)
• Fast Feature Selection with Fairness Constraints [49.142308856826396]
  We study the fundamental problem of selecting optimal features for model construction. This problem is computationally challenging on large datasets, even with the use of greedy algorithm variants. We extend the adaptive query model, recently proposed for the greedy forward selection for submodular functions, to the faster paradigm of Orthogonal Matching Pursuit for non-submodular functions. The proposed algorithm achieves exponentially fast parallel run time in the adaptive query model, scaling much better than prior work.
  arXiv  Detail & Related papers  (2022-02-28T12:26:47Z)
• More Powerful Conditional Selective Inference for Generalized Lasso by Parametric Programming [20.309302270008146]
  Conditional selective inference (SI) has been studied intensively as a new statistical inference framework for data-driven hypotheses. We propose a more powerful and general conditional SI method for a class of problems that can be converted into quadratic parametric programming.
  arXiv  Detail & Related papers  (2021-05-11T10:12:00Z)
• More Powerful and General Selective Inference for Stepwise Feature Selection using the Homotopy Continuation Approach [17.191349670354228]
  Conditional selective inference (SI) has been actively studied as a new statistical inference framework for data-driven hypotheses. The main limitation of the existing conditional SI methods is the loss of power due to over-conditioning. We develop a more powerful and general conditional SI method for SFS using the homotopy method which enables us to overcome this limitation.
  arXiv  Detail & Related papers  (2020-12-25T09:01:45Z)
• Post-selection inference with HSIC-Lasso [19.928884107444908]
  We propose a selective inference procedure using the framework of truncated Gaussians combined with the polyhedral lemma. We then develop an algorithm, which allows for low computational costs and provides a selection of the regularisation parameter. The performance of our method is illustrated by both artificial and real-world data based experiments, which emphasise a tight control of the type-I error, even for small sample sizes.
  arXiv  Detail & Related papers  (2020-10-29T15:10:21Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)

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.