{"id":"9842f044-b802-4b2c-86e4-d248f1fb4965","arxiv_id":"1908.10382","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Feature Gradients computes a learnability-based score for feature subsets in linear time and uses gradient descent on a continuous relaxation to select features, outperforming filter baselines and MISSION on several datasets.","lead":"This paper introduces Feature Gradients, a feature selection method that uses gradient descent on a smoothed version of a learnability estimator to pick useful columns from very large datasets. It aims to scale to millions of samples and features while capturing combinations of columns that predict the target together.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Central claim leans on Kong–Valiant objective being a faithful proxy for downstream classification, a condition the paper concedes in Section 2 is not guaranteed outside Gaussian settings.","rationale":"The algorithm itself is sound: Lemma 2.1's O(ND) evaluation is correct, the triud recurrence is a valid linear-time primitive, and the discrete-to-continuous relaxation with sigma is a reasonable heuristic. The experiments show consistent AUC gains on four datasets, and increasing the estimator order from 1 to 6 improves results, which is suggestive that higher-order terms carry signal. The main soft spot remains the gap between the theoretical conditions under which the Kong–Valiant estimator is justified and the way FG is deployed. This is not a fatal flaw: the Section 2 caveat is explicit and the empirical results are the actual evidence. But the paper does not quantify how much of the observed gain comes from a better approximation of the linear explained variance rather than from genuinely novel higher-order feature interactions. In addition, the reported webspam p-value (0.0201) is larger than the claimed 0.01 significance level, so the large-N-less-than-D comparison is not significant as stated; this should be corrected or reanalyzed. These issues do not overturn the central algorithmic claim, but they do support the existing CONDITIONAL verdict rather than an unconditional accept.","tokens_in":7201,"tokens_out":9580,"duration_ms":106771,"concrete_test":"On synthetic data with a known linear-plus-interaction target, generate both Gaussian features and heavy-tailed or binary features. For many random subsets of each size d, compute the FG objective f(s) from Eq. (1) and the held-out AUC of the same logistic-regression evaluation used in Section 4, then compute the Spearman rank correlation between the two. If that correlation collapses in the non-Gaussian condition relative to the Gaussian condition, the proxy assumption underlying the central claim fails and the claimed generality should be scaled back.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The method's usefulness hinges on Eq. (1), the Kong–Valiant residual-variance estimator, whose ranking of feature subsets is the signal that gradient descent follows. The theoretical support for that estimator assumes i.i.d. examples and bounded 2nd and 4th moments for regression, and Gaussian examples for the classification bound; the experimental protocol, however, applies FG to binary labels and non-Gaussian features, then evaluates with logistic-regression AUC. Section 2 explicitly flags this: 'the classification bound ... assumes Gaussianity of the examples' and 'the objective (plus penalty) is non-convex and likely has many local optima.' If f(s) does not track the AUC of the downstream classifier across subsets, the selected features are not guaranteed to be useful, and the demonstrated gains could be dataset-specific. The paper offers no diagnostic of proxy fidelity, such as the correlation between f(s) and held-out AUC, and no synthetic control separating interaction detection from better polynomial approximation of a linear signal, so the abstract's 'capable of finding higher-order correlations' is broader than what is shown.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":7407,"tokens_out":4727,"duration_ms":49504,"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":[{"comment":"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":"Section 4, webspam results"},{"comment":"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":"Section 2 and Section 4"},{"comment":"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":"Section 2, mini-batch optimization"},{"comment":"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.","section":"Section 4, higher-order interaction evidence"}],"minor_comments":[{"comment":"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":"Section 2, Proposition 2.1"},{"comment":"There is a typo: 'constant increase in time and space complexity with with each additional order' contains a duplicated 'with'.","section":"Section 1"},{"comment":"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":"Section 4"},{"comment":"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.","section":"Section 4, figures"},{"comment":"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.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"The paper has a concrete, checkable computational contribution in Lemma 2.1 and promising small-data evidence, so I would not reject it. The main issues are fixable in principle: correct the webspam significance claim, add proxy-fidelity diagnostics and synthetic interaction experiments, and discuss the stochastic/non-convex optimization gap. The refereeing process should require these additions before publication in a serious journal."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe 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.\n\nWhat 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.\n\nSoft 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.\n\nMissing 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.\n\nWho 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.","headline":"A genuinely useful, efficient feature-selection method built on a sound linear-time trick, with honest caveats; a few experimental reporting issues to fix.","tokens_in":7907,"tokens_out":1623,"would_cite":true,"duration_ms":16458,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Feature Gradients makes feature selection a continuous optimization problem, scaling to millions of features while capturing higher-order feature-target interactions.","keywords":["feature selection","gradient-based search","discrete relaxation","learnability estimation","higher-order feature interactions","sublinear data regime","scalable filters","mini-batch optimization"],"falsifier":"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.","tokens_in":6990,"feed_emoji":"🎯","tokens_out":7688,"duration_ms":66669,"temperature":0.7,"pith_summary":"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<D settings and computationally cheap enough for datasets with millions of features.","feed_headline":"Gradient search finds feature interactions standard filters miss","feed_subtitle":"A differentiable relaxation of subset search scales to millions of dimensions and beats per-feature filters and MISSION.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the learnability estimator f(s) and the sublinear bounds that Feature Gradients differentiates.","marker":"Kong and Valiant [2018]"},{"why":"The MISSION streaming feature selector that serves as the large-scale baseline and comparison point.","marker":"[Aghazadeh et al., 2018]"},{"why":"The correlation-based filter methods that represent the greedy baseline on small datasets.","marker":"Yu and Liu [2003, 2004]"},{"why":"Establishes NP-hardness of subset selection, motivating the discrete-to-continuous relaxation.","marker":"[Natarajan, 1995]"},{"why":"Provides the Adam optimizer used for the relaxed gradient search.","marker":"[Kingma and Ba, 2014]"},{"why":"The differentiable-architecture-search relaxation that this paper's relaxation is aligned with.","marker":"Liu et al. [2018]"}],"fun_headline_variants":["Gradient feature selection scales to millions of dimensions","Feature selection via gradients finds higher-order interactions","Gradient-based subset search beats per-feature filters","Iterative gradient search for feature selection in linear time","Differentiable relaxation unlocks large-scale feature interaction search"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Gradient feature selection scales to millions of dimensions","Feature selection via gradients finds higher-order interactions","Gradient-based subset search beats per-feature filters","Iterative gradient search for feature selection in linear time","Differentiable relaxation unlocks large-scale feature interaction search"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000208,"raw_usage":{"total_tokens":1368,"prompt_tokens":874,"completion_tokens":494,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":490,"completion_tokens_details":{"reasoning_tokens":422}},"tokens_in":490,"tokens_out":494,"duration_ms":5123,"temperature":1.0,"reasoning_tokens":422,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:44:31.095591+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}