Pith. sign in

REVIEW 2 major objections 4 minor 22 references

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

T0 review · 2 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read AutoSI automatically constructs the selection event of any rationally expressible algorithm written in ordinary array code and returns exactly valid selective p-values, extending exact post-selection inference to polynomial selection…

desk verdict A genuinely useful automation of selective inference, but the sweep-completeness claim is false as stated under Condition 1; fixable with a more careful condition. read the letter →

arxiv 2608.04667 v1 pith:UJQMMCUP submitted 2026-08-05 stat.ML cs.LG

Teruyuki Katsuoka , Tomohiro Shiraishi , Shuichi Nishino , Ichiro Takeuchi This is my paper · ORCID
classification stat.MLcs.LG MSC 62F0362J0762J05
keywords selectiveinferencepost-selectionrationallyexpressiblealgorithmpolynomialselectioneventfeaturetruncatednormalcross-validatedlassoparametricprogramming
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

AutoSI is a framework that automatically constructs the selection event of any algorithm the user writes in ordinary NumPy-like array code, provided the algorithm is deterministic, terminating, and computes only with rational functions of the data (Condition 1). The paper claims that for such algorithms AutoSI recovers the truncation region $Z$ exactly and returns the selective p-value $p_{\mathrm{selective}} = P_{H_0}(|z| \ge |z_{\mathrm{obs}}| \mid z \in Z)$, which satisfies $P_{H_0}(p_{\mathrm{selective}} \le \alpha) = \alpha$ for every $\alpha$, exactly, in finite samples (Theorem 1). This would matter because exact selective inference has so far required an expert to hand-derive each algorithm's selection event and has been limited to linear or quadratic inequalities; AutoSI removes that manual step and extends exactness to polynomial selection events of arbitrary degree, such as a lasso whose regularization strength is chosen by $K$-fold cross-validated $R^2$ (degree $4K$). The paper demonstrates the framework on marginal screening, the lasso, and the cross-validated lasso, showing type I error control and power on synthetic and real data.

What carries the argument

The load-bearing object is the truncation region $Z = \{z : A(a+bz) = A(y)\}$ on the line $Y(z) = a + bz$ through the observed response, where $a = Q(y)$ fixes the sufficient statistic of the nuisance parameter and $b = \Sigma\eta/(\eta^\top\Sigma\eta)$ carries the test statistic $z = \eta^\top Y$. AutoSI builds $Z$ by carrying every intermediate quantity as a rational function of $z$ — stored as numerator and denominator coefficient vectors — so each data-dependent operation (comparison, absolute value, max, argmax, sort) becomes a sign condition $\mathrm{num}(z)/\mathrm{den}(z) > 0$ on a polynomial, and each run of the algorithm certifies the interval between the nearest real roots of the recorded numerator and denominator polynomials. Real roots are computed numerically as real eigenvalues of companion matrices, which works at any polynomial degree. Algorithm 1 then sweeps the line from a sufficiently small starting $z$, stepping past each certified interval's right endpoint by a small $\gamma$, and unions the intervals whose output matches the observed one; this is the parametric-programming step that assembles the full $Z$. Lemma 1 and Theorem 1 reduce the selective test to this truncation by conditioning on the sufficient statistic, so that the unconditional type I error rate is exactly $\alpha$.

What would settle it

Run AutoSI's sweep on a rationally expressible algorithm whose true truncation region $Z$ can be enumerated exactly (e.g., the fixed-$\lambda$ lasso on a small design, where $Z$ can be computed by exhaustive evaluation of the algorithm over a dense grid of $z$), and compare the AutoSI output with the exact $Z$ for successively smaller step sizes $\gamma$; if for any positive $\gamma$ the symmetric difference is nonempty, or if on 10,000 null datasets the empirical distribution of $p_{\mathrm{selective}}$ deviates from uniform beyond Monte Carlo error at $\alpha = 0.05$, then the asserted exactness of Eq. (9) and Theorem 1 fails for that setting.

Watch

Extended reading notes

Core claim

The central claim, stated on the paper's own terms, is that any algorithm satisfying Condition 1 — deterministic, terminating, using only rational arithmetic plus comparisons and selections — has a selection event that AutoSI can compute automatically. Running the algorithm along the one-dimensional line $Y(z) = a + bz$ and representing every intermediate array as a rational function of $z$, AutoSI records the sign condition $\mathrm{num}(z)/\mathrm{den}(z) > 0$ for every data-dependent decision, obtains the roots of these polynomials by companion-matrix eigenvalue computation, and sweeps the line to assemble the truncation region $Z = \{z : A(a+bz) = A(y)\}$ as a union of intervals (Eqs. 8–9). With $Z$ in hand the selective p-value of Eq. (5) follows from the truncated normal distribution and satisfies the exact uniformity property of Theorem 1. In particular, the framework handles selection events described by polynomial inequalities of degree higher than two, including the degree-12 system for a 3-fold cross-validated $R^2$ lasso, which no existing exact method can handle.

Load-bearing premise

The claim that AutoSI recovers the whole truncation region exactly rests on the unproved assertion that sweeping the line with a 'sufficiently small' step $\gamma$ misses no intervals (Eq. 9); there is no rule for choosing $\gamma$ and no analysis of numerical error from the companion-matrix root-finding, so if the sweep merges or skips intervals the computed p-value conditions on the wrong set and Theorem 1's exact guarantee no longer applies.

Editorial extensions

If this is right

  • Exact selective inference becomes available for any user-written rationally expressible algorithm, with no expert derivation of the selection event.
  • Selection events of polynomial degree higher than two — such as a $K$-fold cross-validated $R^2$ lasso (degree $4K$) — become exactly testable, a class previously beyond every exact method.
  • Because AutoSI conditions on the output alone (the union of intervals) rather than the full computation path, its p-values are as powerful as the selection event allows; the w/o-pp ablation shows the power cost of over-conditioning.
  • Users can test the algorithm they actually run, not a simplified surrogate, so findings from data-driven pipelines carry correct false-positive guarantees.
  • The same framework transfers to any rationally expressible algorithm beyond feature selection, at a computational cost that grows with the degree of the selection event.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the sweep step $\gamma$ were given a provable bound or replaced by exact interval arithmetic, AutoSI would amount to a compiler that turns any rationally expressible pipeline into a valid test, making selective inference a routine service rather than a per-algorithm research task.
  • The framework's cost is tied to polynomial degree growth: algorithms with deeply nested loops and many comparisons (e.g., iterative fits with many branch points) could produce very high-degree polynomials whose companion-matrix eigenvalues become numerically fragile; the paper does not quantify this degradation, which is a testable scaling property.
  • The exactness guarantee presumes a known covariance $\Sigma$; on real data the authors plug in an estimated variance, so practical p-values are exact only up to that estimation, a gap the paper acknowledges but does not close.
  • Because equality tests ($==$, $!=$) are deliberately untracked at measure-zero points, an algorithm whose selection depends on exact ties would have its $Z$ correct only up to a null set; whether this affects any practical algorithm is not examined.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper proposes AutoSI, a framework that automatically constructs the selection event of a user-written algorithm by tracking each primitive comparison and selection as sign conditions on rational functions of a one-dimensional line parameter z. For any algorithm satisfying Condition 1 (deterministic, terminating, rationally expressible), the paper claims that a fixed-step sweep (Algorithm 1, Eq. (9)) recovers the entire truncation region Z = {z : A(a+bz)=A(y)}, so that the selective p-value p_selective = P_{H0}(|z|>=|z_obs| | z in Z) is exactly valid in finite samples (Theorem 1). The framework is demonstrated on marginal screening, the lasso, and a lasso tuned by cross-validated R^2, the last of which has a degree-twelve selection event beyond the reach of existing exact SI methods. Experiments on synthetic and real data report type I error control and high power.

Significance. If the central claim held, AutoSI would be a substantial advance: it would remove the per-algorithm manual derivation that has limited exact SI to linear or quadratic selection events, and it would make exact selective inference available for arbitrary rationally expressible algorithms. The paper is commendable for shipping an open-source implementation, for using reproducible explicit seeds in the experiments, and for demonstrating that the framework works end-to-end on three feature-selection methods, including one whose selection event is far outside the previous exact-SI toolbox. The classical line-reduction argument (Lemma 1, Theorem 1) is standard and correctly applied. However, the universal claim over all of Condition 1 is not supported: the sweep in Eq. (9) can miss infinitely many selection intervals for a terminating rationally expressible algorithm, so the exact-validity guarantee does not hold for the stated class. This is a load-bearing gap, though it appears fixable by restricting the class or by replacing the fixed-step sweep with an adaptive procedure with a correctness proof.

major comments (2)
  1. [3.4, Eq. (9), Algorithm 1] The completeness assertion in Eq. (9) is false for the class defined by Condition 1, and no fixed step gamma can make it true. Condition 1 allows data-dependent while-loops whose iteration count is unbounded along the line, so Z can be an infinite union of intervals accumulating at a point. For example, with a=0 and b=e1, define A(y) as follows: if y0<=0 return 0; set t=1/y0 and k=0; while t>1 do t=t/2 and k=k+1; then return the parity of k (computed by repeated subtraction, using only rational arithmetic and comparisons). This terminates for every input and satisfies Condition 1. The set Z for output 1 is an infinite disjoint union of half-open intervals accumulating at z=0. Algorithm 1 advances by z <- I_+(z)+gamma, so once the current z is below gamma, the next jump overshoots infinitely many of these intervals; the computed union is a strict subset of Z for every gamma>0. The selective p-value is then computed under the wrong truncation region, and Theorem 1's exact validity guarantee does not apply. The phrase 'provided that the sweep uses a sufficiently small step gamma' cannot be turned into a procedure because the required gamma depends on the unknown Z. I recommend restricting Condition 1 (e.g., to algorithms whose selection region on any line is a finite union of intervals) and proving completeness under that restriction, or replacing the fixed-step sweep by an adaptive subdivision procedure with a correctness proof.
  2. [3.3, Eq. (8)] The paper claims exact validity but the implementation locates interval endpoints as real eigenvalues of companion matrices, and no error analysis is given for how numerical errors propagate into Z. For the p-value in Eq. (5) to be an exact selective p-value, Z must be the exact truncation region; approximate roots can shift endpoints, merge adjacent intervals, or, in the counterexample above, skip narrow intervals altogether. Finite-sample exactness therefore requires either a proof that the numerical errors provably do not change Z (e.g., via certified root isolation and separation bounds) or an explicit statement of the precision assumptions under which the computed p-value is exact.
minor comments (4)
  1. [Abstract and Appendix D] The abstract states that the p-values are 'exactly valid in finite samples,' but Theorem 1 assumes a known covariance Sigma, whereas the real-data experiments use a plug-in estimate of the noise variance; Appendix D itself says 'the inference is then exact up to this plug-in estimate.' This limitation should be acknowledged in the main text or abstract.
  2. [Algorithm 1] Lines 2-3 of Algorithm 1 specify 'initialize z to a sufficiently small value' and 'while z is not large enough,' but no concrete criterion is given for either. Even under a finite-union restriction, the sweep needs a termination condition that detects infinite intervals or a prescribed bound with a validity argument.
  3. [2.2, Eq. (5)] The symbol z is used both for the line parameter in Eq. (4) and for the random variable eta^T Y in Eq. (5). Distinguishing these, for example by writing the random variable as Z and the observed value as z_obs, would make the conditioning expression less ambiguous.
  4. [Figure 1] In panel (c), the intervals are labeled with different selected sets M={3}, M={5}, M={4}; since the truncation region Z is the union of intervals whose output matches the observed one, shading only the matching set in the final panel would help the reader connect the figure to Eq. (6).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the selective p-value is constructed from the algorithm's actual output via the standard line-reduction, with no fitted quantity renamed as a prediction.

full rationale

The paper's derivation chain is self-contained in the sense relevant to circularity. The truncation region Z is defined in Eq. (6) as the set of z with A(a+bz)=A(y), and Algorithm 1 constructs it by running the user's algorithm at sweep points and recording intervals in which the output is provably unchanged. The collected union in Eq. (9) is by construction the set of z whose output matches the observed one, assuming the sweep is fine enough; no parameter is fitted to the data and then reused as a prediction. The selective p-value in Eq. (5) is the standard truncated-normal probability from Lee et al. and Fithian et al., and Theorem 1 is a direct application of that classical result rather than a claim derived from AutoSI's own output. Self-citations (Le Duy and Takeuchi 2021, 2022) are used only to name the parametric-programming technique; the validity proof in Appendix A does not rely on those papers. The 'sufficiently small step gamma' assertion is an unproved completeness condition and a potential correctness risk for algorithms with accumulating intervals, but that is not circularity: the sweep is not defined in terms of the p-value or the fitted data. The experimental type I error checks are confirmatory, not inputs to the construction. Therefore the paper does not exhibit self-definitional, fitted-input, or self-citation-load-bearing circularity.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

The central validity theorem rests on standard SI theory (known Sigma, reduction to a line) plus three AutoSI-specific assumptions: rational expressibility of the algorithm, null-set ties, and exact recovery of the truncation region by the sweep. The only hand-chosen control parameter is the sweep step gamma, whose appropriate value is not specified.

free parameters (1)
  • sweep step gamma
    Algorithm 1 advances z by I+(z)+gamma and initializes z to a 'sufficiently small' value; no rule is given for choosing gamma, and Eq. (9) requires gamma to be sufficiently small to recover Z exactly.
assumptions (5)
  • domain assumption The response Y follows N(mu, Sigma) with known Sigma (Section 2.1).
    The entire selective inference framework, including the truncated normal p-value, assumes a known covariance; the real-data experiments only approximate this by plugging in an estimated variance.
  • standard math Conditioning on Q(Y)=(I_n-b eta^T)Y reduces the problem to a one-dimensional line Y(z)=a+bz (Lemma 1).
    This is the classical SI reduction; it requires eta^T b=1 and independence of Q(Y) and eta^T Y, which hold under the Gaussian model.
  • domain assumption The algorithm is deterministic, terminates, and makes all decisions by comparing rational functions of the data (Condition 1).
    This delimits the class of algorithms AutoSI can handle; algorithms with random components, non-rational functions, or equality-based infinite loops are outside the stated scope.
  • domain assumption Ties in comparisons occur only at roots of the recorded polynomials, a null set, and can be ignored (Section 3.2, Appendix B).
    The proof and the sweep rely on ignoring tie points; if ties had positive measure, the selection event could be mischaracterized.
  • domain assumption Real roots of the recorded polynomials are computed exactly or to sufficient accuracy by companion-matrix eigenvalues (Section 3.3).
    The algorithm's implementation uses numerical root-finding; the paper provides no error analysis connecting approximation error in the roots to error in the reported p-value.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Automatic Statistical Test for Rationally Expressible Algorithms by Selective Inference, with Applications to Feature Selection." pith.science (2026). https://pith.science/paper/UJQMMCUP

@misc{pith2026260804667,
  author       = {Pith},
  title        = {Pith review of: Automatic Statistical Test for Rationally Expressible Algorithms by Selective Inference, with Applications to Feature Selection},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UJQMMCUP}},
  note         = {Machine review of arXiv:2608.04667}
}
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.

Figures

Figures reproduced from arXiv: 2608.04667 by the authors.

Figure 1
Figure 1. Our framework, AutoSI, automatically derives the selection event [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Type I error rates on synthetic data as the sample size [PITH_FULL_IMAGE:figures/full_fig_p017_2.png] view at source ↗
Figure 3
Figure 3. Power on synthetic data as the signal strength ∆ grows; [PITH_FULL_IMAGE:figures/full_fig_p018_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 7 canonical work pages

  1. [1]

    Selective Inference : The Silent Killer of Replicability

    Yoav Benjamini. Selective Inference : The Silent Killer of Replicability . Harvard Data Science Review, 2 0 (4), dec 16 2020. https://hdsr.mitpress.mit.edu/pub/l39rpgyc

    work page 2020

  2. [2]

    Chen and Daniela M

    Yiqun T. Chen and Daniela M. Witten. Selective inference for k-means clustering. Journal of Machine Learning Research, 24 0 (152): 0 1--41, 2023. URL http://jmlr.org/papers/v24/22-0371.html

    work page 2023

  3. [3]

    More powerful conditional selective inference for generalized lasso by parametric programming

    Vo Nguyen Le Duy and Ichiro Takeuchi. More powerful conditional selective inference for generalized lasso by parametric programming. The Journal of Machine Learning Research, 23 0 (1): 0 13544--13580, 2022

    2022

  4. [4]

    Quantifying statistical significance of neural network-based image segmentation by selective inference

    Vo Nguyen Le Duy, Shogo Iwazaki, and Ichiro Takeuchi. Quantifying statistical significance of neural network-based image segmentation by selective inference. Advances in Neural Information Processing Systems, 35: 0 31627--31639, 2022

    2022

  5. [5]

    Optimal inference after model selection

    William Fithian, Dennis Sun, and Jonathan Taylor. Optimal inference after model selection. arXiv preprint arXiv:1410.2597, 2014

    arXiv 2014

  6. [6]

    Selective inference for hierarchical clustering

    Lucy L Gao, Jacob Bien, and Daniela Witten. Selective inference for hierarchical clustering. Journal of the American Statistical Association, pages 1--11, 2022

    2022

  7. [7]

    Exact post-selection inference for the generalized lasso path

    Sangwon Hyun, Max G’sell, and Ryan J Tibshirani. Exact post-selection inference for the generalized lasso path. Electronic Journal of Statistics, 12 0 (1): 0 1053--1097, 2018

    2018

  8. [8]

    Testing for a change in mean after changepoint detection

    Sean Jewell, Paul Fearnhead, and Daniela Witten. Testing for a change in mean after changepoint detection. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84 0 (4): 0 1082--1104, 2022

    2022

Show all 22 references
  1. [9]

    The UCI machine learning repository

    Markelle Kelly, Rachel Longjohn, and Kolby Nottingham. The UCI machine learning repository. https://archive.ics.uci.edu, 2023

    2023

  2. [10]

    Parametric programming approach for more powerful and general lasso selective inference

    Vo Nguyen Le Duy and Ichiro Takeuchi. Parametric programming approach for more powerful and general lasso selective inference. In International conference on artificial intelligence and statistics, pages 901--909. PMLR, 2021

    2021

  3. [11]

    Exact post model selection inference for marginal screening

    Jason D Lee and Jonathan E Taylor. Exact post model selection inference for marginal screening. Advances in neural information processing systems, 27, 2014

    2014

  4. [12]

    Exact post-selection inference, with application to the lasso

    Jason D Lee, Dennis L Sun, Yuekai Sun, and Jonathan E Taylor. Exact post-selection inference, with application to the lasso. The Annals of Statistics, 44 0 (3): 0 907--927, 2016

    2016

  5. [13]

    Joshua R. Loftus. Selective inference after cross-validation, 2015. URL https://arxiv.org/abs/1511.08866

    2015 arXiv

  6. [14]

    Unifying approach to selective inference with applications to cross-validation, 2018

    Jelena Markovic, Lucy Xia, and Jonathan Taylor. Unifying approach to selective inference with applications to cross-validation, 2018. URL https://arxiv.org/abs/1703.06559

    2018 arXiv

  7. [15]

    Statistical test for auto feature engineering by selective inference

    Tatsuya Matsukawa, Tomohiro Shiraishi, Shuichi Nishino, Teruyuki Katsuoka, and Ichiro Takeuchi. Statistical test for auto feature engineering by selective inference. In Yingzhen Li, Stephan Mandt, Shipra Agrawal, and Emtiyaz Khan, editors, Proceedings of The 28th International...

    2025

  8. [16]

    Valid p-value for deep learning-driven salient region

    Daiki Miwa, Duy Vo Nguyen Le, and Ichiro Takeuchi. Valid p-value for deep learning-driven salient region. In Proceedings of the 11th International Conference on Learning Representation, 2023

    2023

  9. [17]

    Statistical test for anomaly detections by variational auto-encoders

    Daiki Miwa, Tomohiro Shiraishi, Vo Nguyen Le Duy, Teruyuki Katsuoka, and Ichiro Takeuchi. Statistical test for anomaly detections by variational auto-encoders. arXiv preprint arXiv:2402.03724, 2024

    2024 arXiv

  10. [18]

    Statistical test for attention map in vision transformers

    Tomohiro Shiraishi, Daiki Miwa, Teruyuki Katsuoka, Vo Nguyen Le Duy, Koichi Taji, and Ichiro Takeuchi. Statistical test for attention map in vision transformers. International Conference on Machine Learning, 2024

    2024

  11. [19]

    Statistical test for feature selection pipelines by selective inference

    Tomohiro Shiraishi, Tatsuya Matsukawa, Shuichi Nishino, and Ichiro Takeuchi. Statistical test for feature selection pipelines by selective inference. In Aarti Singh, Maryam Fazel, Daniel Hsu, Simon Lacoste-Julien, Felix Berkenkamp, Tegan Maharaj, Kiri Wagstaff, and Jerry Zhu, ...

    2025

  12. [20]

    Statistical learning and selective inference

    Jonathan Taylor and Robert J Tibshirani. Statistical learning and selective inference. Proceedings of the National Academy of Sciences, 112 0 (25): 0 7629--7634, 2015

    2015

  13. [21]

    Exact post-selection inference for sequential regression procedures

    Ryan J Tibshirani, Jonathan Taylor, Richard Lockhart, and Robert Tibshirani. Exact post-selection inference for sequential regression procedures. Journal of the American Statistical Association, 111 0 (514): 0 600--620, 2016

    2016

  14. [22]

    Conditional selective inference for robust regression and outlier detection using piecewise-linear homotopy continuation

    Toshiaki Tsukurimichi, Yu Inatsu, Vo Nguyen Le Duy, and Ichiro Takeuchi. Conditional selective inference for robust regression and outlier detection using piecewise-linear homotopy continuation. arXiv preprint arXiv:2104.10840, 2021

    2021 arXiv

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.