Automatic Statistical Test for Rationally Expressible Algorithms by Selective Inference, with Applications to Feature Selection

• URL: http://arxiv.org/abs/2608.04667v1
• Date: Wed, 05 Aug 2026 10:25:56 GMT
• Title: Automatic Statistical Test for Rationally Expressible Algorithms by Selective Inference, with Applications to Feature Selection
• Abstract summary: Selective inference (SI) provides statistically valid $p$-values for hypotheses selected by applying an algorithm to the data.<n>We propose AutoSI, a framework that removes the barrier to exact SI for a narrow class.<n>We prove that the $p$-values computed by AutoSI are exactly valid in finite samples.
• Score: 9.892633657809785
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Selective inference (SI) provides statistically valid $p$-values for hypotheses selected by applying an algorithm to the data, correcting for the bias that arises when the same data are used both to select and to test a hypothesis. Developing an SI procedure for a new algorithm, however, has required an expert to derive, and then implement, the selection event, i.e., the conditions under which the hypothesis is selected. Repeating this specialized effort for every new algorithm is why exact SI has so far been available for only a narrow class. We propose AutoSI, a framework that removes this barrier in two ways. First, AutoSI constructs the selection event automatically from the algorithm's individual operations, so the user only writes the algorithm as ordinary NumPy-like code and derives nothing by hand. Second, AutoSI broadens the class of selection events SI can handle: existing exact methods are limited to selection events characterized by linear or quadratic inequalities in the data, whereas AutoSI covers any algorithm expressible through rational functions of the data (ratios of polynomials). We prove that the $p$-values computed by AutoSI are exactly valid in finite samples. We demonstrate AutoSI on three feature-selection methods, each written in a few dozen lines of code. One of these methods, the lasso with its tuning parameter selected by cross-validated $R^2$, cannot be handled within existing exact SI frameworks and is made possible by AutoSI. Experiments on synthetic and real datasets show that the resulting $p$-values control the type I error rate (i.e., the false positive rate) at the nominal level while retaining high power.

Related papers

• One Knob to Rule Them All: A Unified Optimal Transport View of Cold-Start Active Learning [19.504724272527515]
  Cold-Start Active Learning (CSAL) aims to select a valuable subset from an unlabeled pool without prior knowledge or human assistance.<n>We argue that the real challenge is not to design yet another selection, but to make CSAL adapt automatically to the data and task at hand.<n>We present a novel Sinkhorn-based CSAL algorithm, termed $$-Adaptive Selection ($$-AS)
  arXiv  Detail & Related papers  (2026-08-04T07:21:39Z)
• Automatic Demonstration Selection for LLM-based Tabular Data Classification [0.0]
  We present an algorithm to automatically select a reasonable number of required demonstrations.<n>Our method distinguishes itself by integrating the user's selected prompt template and the specific Large Language Model (LLM)<n>We then construct a similarity graph and analyze the eigenvalues of its Laplacian to derive the minimum number of demonstrations capable of representing the data.
  arXiv  Detail & Related papers  (2025-06-25T13:57:54Z)
• 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)
• Bisimulation Learning [55.859538562698496]
  We compute finite bisimulations of state transition systems with large, possibly infinite state space. Our technique yields faster verification results than alternative state-of-the-art tools in practice.
  arXiv  Detail & Related papers  (2024-05-24T17:11:27Z)
• Surrogate-based Autotuning for Randomized Sketching Algorithms in Regression Problems [34.59249597626943]
  We show how a surrogate-based autotuning approach can be used to address fundamental problems of parameter selection in RandNLA algorithms.<n>Our results show that our surrogate-based autotuning approach can achieve near-optimal performance with much less tuning cost than a random search.
  arXiv  Detail & Related papers  (2023-08-30T02:50:54Z)
• Towards Automated Imbalanced Learning with Deep Hierarchical Reinforcement Learning [57.163525407022966]
  Imbalanced learning is a fundamental challenge in data mining, where there is a disproportionate ratio of training samples in each class. Over-sampling is an effective technique to tackle imbalanced learning through generating synthetic samples for the minority class. We propose AutoSMOTE, an automated over-sampling algorithm that can jointly optimize different levels of decisions.
  arXiv  Detail & Related papers  (2022-08-26T04:28:01Z)
• Contextual Active Model Selection [10.925932167673764]
  We present an approach to actively select pre-trained models while minimizing labeling costs.<n>The objective is to adaptively select the best model to make a prediction while limiting label requests.<n>We propose CAMS, a contextual active model selection algorithm that relies on two novel components.
  arXiv  Detail & Related papers  (2022-07-13T08:22:22Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  In online algorithm selection (OAS), instances of an algorithmic problem class are presented to an agent one after another, and the agent has to quickly select a presumably best algorithm from a fixed set of candidate algorithms. For decision problems such as satisfiability (SAT), quality typically refers to the algorithm's runtime. In this work, we revisit multi-armed bandit algorithms for OAS and discuss their capability of dealing with the problem. We adapt them towards runtime-oriented losses, allowing for partially censored data while keeping a space- and time-complexity independent of the time horizon.
  arXiv  Detail & Related papers  (2021-09-13T18:10:52Z)
• An Extensive Experimental Evaluation of Automated Machine Learning Methods for Recommending Classification Algorithms (Extended Version) [4.400989370979334]
  Three of these methods are based on Evolutionary Algorithms (EAs), and the other is Auto-WEKA, a well-known AutoML method. We performed controlled experiments where these four AutoML methods were given the same runtime limit for different values of this limit. In general, the difference in predictive accuracy of the three best AutoML methods was not statistically significant.
  arXiv  Detail & Related papers  (2020-09-16T02:36:43Z)
• Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis [75.64261155172856]
  survival analysis (SA) naturally supports censored data and offers appropriate ways to use such data for learning distributional models of algorithm runtime. We leverage such models as a basis of a sophisticated decision-theoretic approach to algorithm selection, which we dub Run2Survive. In an extensive experimental study with the standard benchmark ASlib, our approach is shown to be highly competitive and in many cases even superior to state-of-the-art AS approaches.
  arXiv  Detail & Related papers  (2020-07-06T15:20:17Z)
• Parametric Programming Approach for More Powerful and General Lasso Selective Inference [25.02674598600182]
  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.
  arXiv  Detail & Related papers  (2020-04-21T04:46:29Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  We consider the problem of ranking $N$ objects starting from a set of noisy pairwise comparisons provided by a crowd of equal workers. We propose a class of non-adaptive ranking algorithms that rely on a least-squares intrinsic optimization criterion for the estimation of qualities.
  arXiv  Detail & Related papers  (2020-02-26T16:19:09Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  We propose the setting of extreme algorithm selection (XAS) where we consider fixed sets of thousands of candidate algorithms. We assess the applicability of state-of-the-art AS techniques to the XAS setting and propose approaches leveraging a dyadic feature representation.
  arXiv  Detail & Related papers  (2020-01-29T09:40:58Z)

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.