Feature Gradients: Scalable Feature Selection via Discrete Relaxation

Nicolo Fusi; Rishit Sheth

REVIEW 4 major objections 5 minor 1 cited by

Feature Gradients: Scalable Feature Selection via Discrete Relaxation

T0 review · 4 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read Feature Gradients makes feature selection a continuous optimization problem, scaling to millions of features while capturing higher-order feature-target interactions.

desk verdict A genuinely useful, efficient feature-selection method built on a sound linear-time trick, with honest caveats; a few experimental reporting issues to fix. read the letter →

arxiv 1908.10382 v1 pith:7DE4Y3KG submitted 2019-08-27 stat.ML cs.LG

Rishit Sheth , Nicolo Fusi This is my paper · ORCID

classification stat.MLcs.LG

keywords featureselectiongradient-basedsearchdiscreterelaxationlearnabilityestimationhigher-orderinteractionssublineardataregimescalablefiltersmini-batchoptimization

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

Feature Gradients is a proposal for turning feature subset selection into a differentiable optimization problem. The paper's central claim is that a recent estimator of how well a feature subset predicts a target, which previously could only be evaluated on a fixed subset, can be computed in mini-batches with cost linear in the number of samples and features, and can then be minimized over a relaxed continuous variable whose entries are squashed to 0/1. Because the estimator's order controls how many features interact at once, the search can discover higher-order correlations, not just per-feature scores. On classification datasets, the paper reports that this method outperforms ANOVA and mutual-information filters on small data and the MISSION streaming filter at scale, in both the more-samples-than-features and more-features-than-samples regimes. The payoff, if these results hold up, is a filter method that is statistically efficient in N

What carries the argument

The load-bearing object is the estimator f(s) from Kong and Valiant, Eq. (1): f(s) = yᵀy/N − Σ_{i=0}^{k−1} aᵢ (N choose i+2) yᵀ triud(X diag(s) Xᵀ)^{i+1} y. The triud operator zeros out the lower triangle and diagonal, and Proposition 2.1 shows triud(zzᵀ)y is computable by one reverse cumulative sum; expanding X diag(s)Xᵀ as Σ_d s_d G_d allows repeated application in O(ND). The paper then relaxes s ∈ {0,1}^D to s = σ(v) ∈ [0,1]^D and runs Adam on f(σ(v)) plus an L1 penalty. The estimator order k is the dial controlling how many feature interactions enter the objective.

What would settle it

Construct a synthetic N<D classification dataset in which the label is determined by a known three-way interaction among three specific features and all other features are pure noise. Run Feature Gradients at order 3; if the three interaction features are not among the selected features, or if order 3 fails to beat order 1 on held-out AUC, the central claim that the method discovers higher-order correlations is contradicted.

Watch

Extended reading notes

Core claim

The paper's discovery is that subset quality, as measured by the Kong-Valiant residual-variance estimator f(s), has a gradient that can be followed. Writing s = σ(v) turns the NP-hard binary selection into unconstrained minimization of f(σ(v)) + (λ/D)‖σ(v)‖₁; Lemma 2.1 shows each step costs O(ND) time and O(N) space. Higher estimator order k incorporates kth-order feature interactions with a constant per-order increase, so the search can move beyond pairwise or main-effect filters. The experimental section reports that FG order 6 significantly beats single-feature filters on mnist35 and gisette, and FG order 4 beats MISSION on rcv1, webspam, and criteo, including maintaining 0.92 test AUC with 22 selected features out of 16.6 million. This is the paper's evidence for the combination of scalability and higher-order interaction detection.

Load-bearing premise

The load-bearing premise is that the Kong-Valiant estimator f(s), after centering and scaling, faithfully measures which feature subsets will help a downstream classifier; if the estimator's assumptions (i.i.d. data, bounded moments, and Gaussianity for classification) are violated too severely, the gradient signal will not point toward useful features.

Editorial extensions

If this is right

Feature selection becomes feasible on datasets with tens of millions of samples and millions of features, as demonstrated on webspam and criteo.
Increasing the estimator order lets users trade computational cost against the depth of feature interactions being searched, at constant complexity per order.
Feature Gradients can act as a drop-in filter ahead of any downstream model, since it evaluates subset quality rather than training a predictor.
The mini-batch formulation makes the method online-capable, so feature subsets can be updated as new data arrive.
In N<<D regimes, selection is guided by sublinear learnability estimates rather than by training a model, reducing overfitting risk.

Reading between the lines

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

The same differentiable-relaxation template could be applied to other subset-quality estimators, not just the Kong-Valiant criterion, yielding a family of differentiable filters.
Because the objective is non-convex and initialization-dependent, annealing the squashing temperature or running multiple restarts would likely improve selection stability; the paper does not investigate this.
The online extension mentioned in the discussion could be developed into a streaming monitor that tracks which feature subsets matter as a distribution drifts over time.
On datasets where FG order 1 and order 6 agree closely, higher-order feature interactions are probably not needed, giving practitioners a cheap diagnostic.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Colleague,

The short version: this paper earns its place. The core algorithmic contribution is real — they show the Kong–Valiant residual variance estimator can be computed in O(ND) time and O(N) space via a simple reverse-cumulative-sum trick, then run mini-batch gradient descent on a continuous relaxation of the discrete feature-selection problem. The proof of Lemma 2.1 is clean and correct. That combination is new relative to the cited literature, and it is a practical answer to a real need: scalable feature selection that captures higher-order interactions in N > D and N < D regimes.

What the paper does well: the experiments are honestly designed. They select features with FG, then fit a fresh logistic regression on the selected features and evaluate test AUC, which is exactly the right way to test a filter. On mnist35, gisette, rcv1, webspam, and criteo, FG beats the relevant baselines (ANOVA, mutual information, MISSION) at most subset sizes. The visualization of selected MNIST pixels clustering at the upper loop is a nice sanity check. The authors also state the key limitations in Section 2: the classification bound assumes Gaussianity and the objective is non-convex. No hiding.

Soft spots, in proportion. First, the webspam claim: they report a p-value of 0.0201 and call it significant at level 0.01. That is simply inconsistent, and a referee should ask for the corrected p-value or a corrected significance level. Second, there are no error bars anywhere; for the small datasets a paired t-test is reported, but the large-dataset comparisons show only point AUCs at each subset size. Third, the mini-batch gradient estimator is used without any analysis — no bias or variance bound, no convergence guarantee. That is not fatal for an empirical paper, but it is a real gap. Fourth, the proxy-fidelity worry is legitimate in theory: the Kong–Valiant estimator's guarantees assume i.i.d. bounded moments and Gaussianity for classification, and the paper applies it to binary labels and arbitrary features. But note the experiments directly measure the downstream AUC, so on these datasets the proxy empirically tracks the target. The theoretical gap remains, but it is a scope-of-analysis issue, not a demonstrated failure.

Missing code is also a reproducibility problem; the MISSION code was modified and mentioned, but FG itself is not released. For a method paper, that matters.

Who this is for: anyone working on feature selection for high-dimensional, large-N problems, especially in genomics or text. A serious referee should engage with it; the p-value error and missing code need fixing, but the core idea and demonstrations hold up. I would accept it for review.

Referee Report

4 major / 5 minor

Summary. The paper proposes Feature Gradients (FG), a filter-style feature selection algorithm that uses the Kong–Valiant learnability estimator as an objective, relaxes the discrete feature subset indicator to a sigmoidal continuous variable, and optimizes the relaxed objective with Adam over mini-batches. The authors prove that the estimator can be evaluated in O(ND) time and O(N) space, and they argue that increasing the estimator order accounts for higher-order feature interactions. The method is evaluated on small datasets (mnist35, gisette) against ANOVA and mutual-information filters, and on larger datasets (rcv1, webspam, criteo) against MISSION, with logistic-regression AUC as the performance metric. The central claims are scalability to large N and D, applicability in both N > D and N < D regimes, and the ability to exploit higher-order correlations.

Significance. If the claims hold, FG would be a practically valuable filter: it is the first method to combine the sublinear-dimension statistical guarantees of the Kong–Valiant estimator with a gradient-based subset search that can capture feature interactions. The paper has concrete strengths: Lemma 2.1 gives an explicit and checkable linear-time, linear-space computation; the small-data experiments show large and mostly statistically significant AUC improvements over standard filters; and the use of held-out logistic-regression AUC is a reasonable evaluation protocol. The computational complexity result is the kind of verifiable contribution that is useful beyond the specific application. However, the supporting analysis is incomplete in several load-bearing places, and one reported significance claim is internally inconsistent, so the current version needs substantial revision.

major comments (4)

[Section 4, webspam results] The text states that FG 'is able to locate feature subsets resulting in test set performance significantly better than MISSION (significance level 0.01, with p-values of 0.0064 and 0.0201 for rcv1 and webspam, respectively).' Since 0.0201 > 0.01, the webspam comparison is not significant at the stated level, so the claim as written is contradicted by the reported p-value. Please either correct the significance statement or use a level of 0.05 for that comparison.
[Section 2 and Section 4] The optimization objective f(s) is the Kong–Valiant residual-variance estimator, whose classification bound assumes Gaussian examples, yet the experiments apply the method to binary labels and non-Gaussian features and evaluate with logistic-regression AUC. The manuscript acknowledges this limitation in Section 2 but offers no diagnostic of proxy fidelity, such as the correlation between f(s) and held-out AUC over a range of subsets. Without such a diagnostic, the reported gains could be dataset-specific, and the abstract's claim that the algorithm is 'capable of finding higher-order correlations' is broader than what is demonstrated.
[Section 2, mini-batch optimization] The paper claims that the calculation can be performed iteratively in mini-batches, but it gives no analysis of the mini-batch gradient estimates (bias, variance, consistency) and no convergence analysis for the non-convex relaxed objective. The authors themselves note that 'the objective (plus penalty) is non-convex and likely has many local optima,' yet the sensitivity of the results to initialization, learning rate, and mini-batch size is not reported. This is load-bearing because the entire method rests on the ability of Adam to reliably optimize the relaxed objective.
[Section 4, higher-order interaction evidence] The evidence for higher-order interaction detection consists of paired comparisons of FG order 6 versus order 1 on two small datasets. There is no synthetic experiment with known ground-truth interaction structure, so the observed improvements could come from better polynomial approximation of a linear or low-order signal rather than from genuine recovery of higher-order correlations. A controlled experiment with known pairwise or higher-order terms would substantially strengthen the central claim.

minor comments (5)

[Section 2, Proposition 2.1] The description of the vector (sum_{i=2}^N u_i, ..., u_N, 0) as a reverse cumulative sum is slightly imprecise; it is a shifted reverse prefix sum of u. Clarifying the indexing would make the O(N) claim easier to verify.
[Section 1] There is a typo: 'constant increase in time and space complexity with with each additional order' contains a duplicated 'with'.
[Section 4] The order parameter k is used in the definition of the estimator, but the experiments do not specify exactly how 'FG order 4' and 'FG order 6' correspond to the coefficients {a_i} and the summation limit in Eq. (1). Please state this explicitly.
[Section 4, figures] In Figures 2 and 5 the point colors encode feature subset size, but the color scale is not shown in the reproduced figures; adding a colorbar or equivalent legend would improve interpretability.
[General] No statement of code or data availability is included; since the algorithm is presented as a practical scalable method, a reproducibility statement would be helpful.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Feature Gradients uses an external learnability estimator and is validated against external benchmarks.

full rationale

The paper's optimization objective, Eq. (1), is taken directly from Kong and Valiant [2018] and is not fitted to the evaluation metric; the residual-variance estimator is an external, stated input rather than a derived prediction of the paper. The algorithmic contributions, including the discrete-to-continuous relaxation s = sigma(v), mini-batching, and the linear-time/space lemmas, are self-contained extensions with proofs that do not assume the experimental conclusions. The regularization parameter lambda is selected via validation-set grid search, which is standard model selection and not a fitted input renamed as a prediction. The paper contains no self-citations, so no load-bearing argument reduces to a self-citation chain. The main caveat, acknowledged in Section 2, is that the Kong-Valiant classification bound assumes Gaussianity and that the objective is non-convex; this is an applicability limitation, not a circular step. The empirical claims are supported by measured AUC comparisons against external baselines such as ANOVA filters, mutual-information filters, and MISSION, so the reported gains are not forced by construction.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

The paper introduces no new theoretical entities. It leans on the Kong-Valiant estimator as an external construction and on manually chosen hyperparameters.

free parameters (4)

regularization strength lambda = grid-searched on validation sets
Controls the number of selected features; chosen per dataset via validation performance (Section 2, experiments).
estimator order k = 6 for small datasets, 4 for large datasets
Higher orders capture more feature interactions; chosen manually, experiments show order 6 improves over order 1.
mini-batch size = 1000 (rcv1), 8 (webspam), 100 (criteo)
Selected as largest fitting in GPU memory; affects stochastic gradient estimates.
Adam learning rate = 0.1
Fixed across all experiments, not tuned.

assumptions (4)

domain assumption The Kong-Valiant estimator requires i.i.d. examples/labels and bounded 2nd/4th order moments and bounded noise variance.
Stated in Section 2 footnote 1; the algorithm inherits these requirements.
domain assumption The classification bound of Kong and Valiant assumes Gaussianity of the examples.
Acknowledged in Section 2; the paper applies the method to classification anyway, relying on empirical robustness.
ad hoc to paper The relaxed non-convex objective can be optimized effectively by Adam gradient descent.
No convergence or local-optima analysis is given; the paper appeals to experimental success (Section 2 and 4).
domain assumption A single set of degree-k polynomial coefficients is valid for all input data matrices after scaling by the square root of the largest singular value.
Assumed in Section 4 FG implementation to reuse KV coefficients.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Feature Gradients: Scalable Feature Selection via Discrete Relaxation." pith.science (2026). https://pith.science/paper/7DE4Y3KG

@misc{pith2026190810382,
  author       = {Pith},
  title        = {Pith review of: Feature Gradients: Scalable Feature Selection via Discrete Relaxation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7DE4Y3KG}},
  note         = {Machine review of arXiv:1908.10382}
}

read the original abstract

In this paper we introduce Feature Gradients, a gradient-based search algorithm for feature selection. Our approach extends a recent result on the estimation of learnability in the sublinear data regime by showing that the calculation can be performed iteratively (i.e., in mini-batches) and in linear time and space with respect to both the number of features D and the sample size N . This, along with a discrete-to-continuous relaxation of the search domain, allows for an efficient, gradient-based search algorithm among feature subsets for very large datasets. Crucially, our algorithm is capable of finding higher-order correlations between features and targets for both the N > D and N < D regimes, as opposed to approaches that do not consider such interactions and/or only consider one regime. We provide experimental demonstration of the algorithm in small and large sample-and feature-size settings.

Figures

Figures reproduced from arXiv: 1908.10382 by the authors.

**Figure 1.** mnist35 input examples. in the relevant sections. The squashing function was σ(2x) where σ(·) is the sigmoid function (this choice of squashing function is equivalent to 1 2 (tanh(x) + 1)). Small datasets. The smaller dimensional datasets are: • mnist35. Classification of 3s vs. 5s in the MNIST dataset with random noise added to produce a more challenging scenario. Samples are shown in [PITH_FULL_IMAGE:figures/full… view at source ↗

**Figure 2.** FG order 6 performance vs. standard filter methods SKF (left) and SKMI (right) on [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

**Figure 3.** Feature selection on mnist35. The different columns represent different feature subset sizes (denoted below the bottom row). The features selected by the filter method utilizing the one-way ANOVA criterion (top) and by FG order 6 (bottom) are colored according to their (normalized) scores. 6 [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: Scores (y-axis) as a function of FG order (x-axis) on [PITH_FULL_IMAGE:figures/full_fig_p007_4.png]

**Figure 5.** Figure 5: FG order 4 performance vs. MISSION on rcv1 (top left), webspam (top right), and criteo (bottom). References A. Abid, M. F. Balin, and J. Zou. Concrete autoencoders for differentiable feature selection and reconstruction. arXiv preprint arXiv:1901.09346, 2019. A. Aghaza…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Make Both Ends Meet: A Synergistic Optimization Infrared Small Target Detection with Streamlined Computational Overhead
eess.IV 2025-04 conditional novelty 4.0 of 10

LE-IRSTD, a YOLOv8-n variant using MBConv, partial convolution, variable-kernel convolution, and GSConv, reports a 2.6M-parameter model with mAP 95.4 on IRSTD-1K, outperforming listed SOTA methods.

Reference graph

Works this paper leans on

17 extracted references · 12 canonical work pages · cited by 1 Pith paper

[1]

A. Abid, M. F. Balin, and J. Zou. Concrete autoencoders for differentiable feature selection and reconstruction. arXiv preprint arXiv:1901.09346, 2019

work page Pith review arXiv 1901
[2]

MISSION: Ultra Large-Scale Feature Selection using Count-Sketches

A. Aghazadeh, R. Spring, D. LeJeune, G. Dasarathy, A. Shrivastava, and R. G. Baraniuk. MISSION : Ultra large-scale feature selection using count-sketches. arXiv preprint arXiv:1806.04310, 2018

work page Pith review arXiv 2018
[3]

G. Forman. An extensive empirical study of feature selection metrics for text classification. JMLR , pages 1289--1305, 2003

work page 2003
[4]

Guyon and A

I. Guyon and A. Elisseeff. An introduction to variable and feature selection. JMLR , pages 1157--1182, 2003

work page 2003
[5]

E. Jang, S. Gu, and B. Poole. Categorical reparameterization with G umbel-softmax. arXiv preprint arXiv:1611.01144, 2016

arXiv 2016
[6]

D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014

arXiv 2014
[7]

Kohavi and G

R. Kohavi and G. H. John. Wrappers for feature subset selection. Artificial intelligence, pages 273--324, 1997

work page 1997
[8]

Kong and G

W. Kong and G. Valiant. Estimating learnability in the sublinear data regime. CoRR, abs/1805.01626, 2018. URL http://arxiv.org/abs/1805.01626

arXiv 2018

Show all 17 references

[9]

H. Liu, K. Simonyan, and Y. Yang. DARTS: D ifferentiable architecture search. CoRR, abs/1806.09055, 2018. URL http://arxiv.org/abs/1806.09055

2018 arXiv
[10]

C. J. Maddison, A. Mnih, and Y. W. Teh. The C oncrete distribution: A continuous relaxation of discrete random variables. arXiv preprint arXiv:1611.00712, 2016

2016 arXiv
[11]

B. K. Natarajan. Sparse approximate solutions to linear systems. SIAM journal on computing , pages 227--234, 1995

1995
[12]

Saeys, I

Y. Saeys, I. Inza, and P. Larra \ n aga. A review of feature selection techniques in bioinformatics. Bioinformatics, pages 2507--2517, 2007

2007
[13]

Y. Sun, S. Todorovic, and S. Goodison. Local-learning-based feature selection for high-dimensional data analysis. IEEE transactions on pattern analysis and machine intelligence , pages 1610--1626, 2009

2009
[14]

Tibshirani

R. Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), pages 267--288, 1996

1996
[15]

K. Yu, X. Wu, W. Ding, and J. Pei. Towards scalable and accurate online feature selection for big data. In ICDM , pages 660--669, 2014

2014
[16]

Yu and H

L. Yu and H. Liu. Feature selection for high-dimensional data: A fast correlation-based filter solution. In ICML , pages 856--863, 2003

2003
[17]

Yu and H

L. Yu and H. Liu. Efficient feature selection via analysis of relevance and redundancy. JMLR , pages 1205--1224, 2004

2004

Pith tools

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

[1] [1]

A. Abid, M. F. Balin, and J. Zou. Concrete autoencoders for differentiable feature selection and reconstruction. arXiv preprint arXiv:1901.09346, 2019

work page Pith review arXiv 1901

[2] [2]

MISSION: Ultra Large-Scale Feature Selection using Count-Sketches

A. Aghazadeh, R. Spring, D. LeJeune, G. Dasarathy, A. Shrivastava, and R. G. Baraniuk. MISSION : Ultra large-scale feature selection using count-sketches. arXiv preprint arXiv:1806.04310, 2018

work page Pith review arXiv 2018

[3] [3]

G. Forman. An extensive empirical study of feature selection metrics for text classification. JMLR , pages 1289--1305, 2003

work page 2003

[4] [4]

Guyon and A

I. Guyon and A. Elisseeff. An introduction to variable and feature selection. JMLR , pages 1157--1182, 2003

work page 2003

[5] [5]

E. Jang, S. Gu, and B. Poole. Categorical reparameterization with G umbel-softmax. arXiv preprint arXiv:1611.01144, 2016

arXiv 2016

[6] [6]

D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014

arXiv 2014

[7] [7]

Kohavi and G

R. Kohavi and G. H. John. Wrappers for feature subset selection. Artificial intelligence, pages 273--324, 1997

work page 1997

[8] [8]

Kong and G

W. Kong and G. Valiant. Estimating learnability in the sublinear data regime. CoRR, abs/1805.01626, 2018. URL http://arxiv.org/abs/1805.01626

arXiv 2018