acceptodds
Under review as a conference paper at ICLR 2027

When Are Feature Crosses Discoverable?

Abstract

Why can explicit feature crosses help models that can already represent interactions? Expressive capacity does not ensure that finite data suffice to fit and certify a useful additive correction to a trained predictor. We formalize this gap as checkpoint-local discoverability, separating residual fitting from post-selection certification. A local risk expansion connects one-step utility to curvature-weighted residual prediction. In a fixed-design Gaussian model, we derive a sufficient exposure–cost frontier for linear smoothers that balances accessible signal, noise fitting, and search complexity. For nested Gaussian projection learners that fully expose the same signal, refinement strictly lowers the probability of positive gain by adding noise-only directions. We introduce CROSSAUDIT, a sample-split audit that selects the pre-validation update with the largest positive simultaneous lower confidence bound and otherwise returns a null update. For bounded logit updates under logistic loss, every positive certificate guarantees exact conditional population-risk improvement at the prescribed confidence level despite candidate selection. Controlled synthetic and semi-synthetic CTR experiments reproduce the refinement effect: atomic representations can lose utility while preserving the target function, whereas hierarchical sharing retains the coarse signal. Real-label audits further show that pair-indexed utility need not be interaction-only: main-effect repairs can be stronger, while the tested post-fit residualized pairs receive no positive certificates.

Primary area:
learning theory
Keywords:
Feature Crosses, Feature Interactions, Checkpoint-Local Discoverability, Tabular Learning, Post-Selection Risk Certification

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_X5ZTOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper investigates when adding a 'feature cross' can improve a trained model, even when the model can already represent crosses. To make this more concrete: suppose you want to predict whether or not someone will pay back their loan. It might be worth adding a feature that records the combination of (1) how long someone has had a bank account and (2) their profession. Now, if you have already added these two features separately, the model can already represent this interaction, but this does not imply that it will learn this interaction from a finite dataset. The paper studies whether an additive correction to a predictor can help.

It first develops a general analysis of when adding a correction zz helps an already trained model f(x)f(\boldsymbol{x}). It does so through a second-order taylor expansion around the already trained model f(x)f(\boldsymbol{x}), which is exact for squared loss. When we add zz to the predictions of f(x)f(\boldsymbol{x}) through an linear smoother, derives a condition for which this addition helps (under a fixed-design Gaussian model). It then focuses the analysis to feature crosses, showing that adding more combinations of features can hurt - when these combinations capture the same signal, adding more combinations increases the estimation noise.

The paper proposes a method called CROSSAUDIT, which fits corrections based on zz and adds an correction only when the lower confidence bound on improvement on the validation loss is positive. The experiments verify the theoretical claims in a synthetic settings, and a semi-synthetic setting using covariates from the Avazu and Criteo datasets. In these experiments, they investigate logistic regression, Multilayer perceptrons, and a model called FM (which I believe is a factorization machine).

Critical strengths
  • The research question is interesting: why can adding feature cross help when the model could learn these crosses? There is a trade-off here betwen (1) the capacity of the model to represent this feature cross, and (2) its ability to estimate the usefulness of this cross from data. By studying the residuals of a trained model, the authors provide a concrete way to address this question.

  • The analysis provides useful intuitions for when a cross can help. In particular, the trade-off between (1) adding more features and thus estimation noise (increasing variance) and (2) adding information that is useful for the predictions (decreasing bias). The comparison between atomic and hierarchical estimators illustrates that this depends on the training procedure and the representation.

Critical weaknesses
  • I found this paper extremely hard to read and understand. Below, I give several concrete examples to illustrate the broader presentation problem. My intention is to offer constructive feedback that I hope will help the authors make the paper accessible to readers interested in feature crosses.

    • The abstract introduces many technical terms, which are not necessarily obvious or expected to be known by interested readers. Examples include (but are not limited to) “post-selection certification,” “sufficient exposure–cost frontier,” and “nested Gaussian projection learners”. Instead, it would be good to use plain English and explain that the method fits candidate feature crosses and checks whether they improve validation loss.
    • In a similar vein, the terms “positive certificate,” “the refinement effect,” “atomic representations,” and “main-effect repairs” appear in the abstract. These terms become (more, although not completely) understandable later but they make the abstract difficult to follow.
    • In the introduction, it is not initially clear what is meant with “the update representation” and “a candidate repair to a particular predictor”. Similarly, it is not clear what is meant with “An atomic table assigns one coefficient to each joint state”.
    • As another example, “These oracle quantities remain graded under dependent covariates” (Section 3.2) - what is meant with graded? what dependent covariates? This list is by no means exhaustive but serves to illustrate a broader point.
  • The theoretical results need more intuition and explanation. Sections 2–3 study a correction to a trained model; their results are not specific to feature crosses. This is not generally clear, and I would encourage the authors to state the structure of their argument more explicitly. As another example, the transition from studying the expected risk to a fixed-Gaussian design is very abrupt - this design needs to be introduced in much more detail.

  • Some of the theoretical results do not need the current degree of emphasis. Lemma 2.1 is simply a Taylor expansion - which is fine to use, but does not need this much attention in the paper. I believe this does not aid with exposing the theory - I believe it would be better to have a more concise derivation and then instead spend much more words on explaining what these results mean. Similarly, Proposition 3.1 is a standard quadratic bias–variance calculation. This does not invalidate the analysis, but it distracts from the main theoretical contributions of the paper.

  • My primary concern for the CROSSAUDIT method is that it is not compared to simply (1) estimating the correction on training data and (2) selecting the correction based on its performance on a validation set (e.g. via cross-validation). I appreciate that the paper develops a guarantee that, under certain conditions, adding the correction reduces the expected loss. However, I believe a similar guarantee could be obtained by calculating (standard) confidence intervals for the validation loss. The paper does compare different confidence bounds in a synthetic experiment, but it is not clear what the practical advantage of CROSSAUDIT is over simpler procedures.

  • Relatedly, the five-way split used in CROSSAUDIT seems quite demanding for a method motivated by finite-data limitations (as then the model will not learn the feature cross). The reported CTR experiments use 200K rows, which seems to me like quite a lot. Experiments varying the sample size and allocation along the five splits would help establish when the procedure is useful.

  • The related-work part is way too short: I would encourage the authors to discuss more explicitly how their approach relates to fitting corrections to model residuals (e.g. gradient boosting), the bias–variance trade-off when adding features, and methods for selecting feature crosses.

Questions for authors

Why does the MLP benefit more from the corrections than the other models? Since it also has a higher loss before adding the corrections, could this be because it has not been trained sufficiently? It would be useful to see whether adding the corrections has a similar effect when we train the MLP for longer.

2 comments
AuthorsOpenReview ↗

Response to Reviewer X5ZT

Thank you for the detailed presentation and methodology suggestions.

Presentation. We rewrote the abstract and introduction around a device–country example: a model may represent this interaction but lack enough observations in individual cells to estimate a reliable correction in the revised paper. We define atomic tables, main-effect repairs, and positive certificates where first introduced. Sections 2–3 present the general analysis of corrections to a fitted predictor, while Section 4 specializes it to feature crosses. We shortened the Taylor and quadratic derivations, explain the fixed-design Gaussian model and dependent-covariate exposure, and expand the connections to boosting, bias–variance, interaction screening, hierarchical sharing, and held-out risk control.

1. Comparison with simpler validation procedures. CROSSAUDIT combines pre-validation fitting and bounds, simultaneous inference across candidates, and an explicit null decision. We compared it with validation-mean selection, split-validation (select-then-certify), and simultaneous Hoeffding bounds using the same fitted update family. Validation-mean selection chooses the highest D3 mean gain and selects a non-null update in every run. Split validation selects on the first 15K D3 observations and certifies the locked choice on the remaining 15K; it obtains 0/3 certificates on each dataset.

For the extended MLP, the full-30K-D3 comparison is shown below. Certificate-based methods use joint-eight correction; validation-mean selection is reported descriptively. Entries give certificate counts and mean null-inclusive D4 log-loss gains:

PolicyAvazuCriteo
Validation mean (descriptive D4 gain)0.0019320.000859
Empirical Bernstein (CROSSAUDIT)3/3; 0.0005601/3; 0.000082
Hoeffding, log(M/δ)0/3; 00/3; 0
Hoeffding, log(2M/δ)0/3; 00/3; 0

Validation-mean selection yields larger observed D4 gains, while empirical Bernstein supplies simultaneous positive-gain certificates for some selected updates; neither tested Hoeffding variant certifies an update in these runs. The EB/Hoeffding comparison reuses the same fitted updates, D2-derived bounds, and D3 gains. For gains in

−Bj,Bj-B_j,B_j

, the one-sided Hoeffding penalty is B_j√(2log(M/δ)/n), and EB uses L=log(2M/δ). Per-family, joint-two, and joint-eight use M=H, 2H, and 8H (four checkpoints × permissive/shuffled families), respectively, at δ=0.1 within each dataset–seed. Families select separately under each simultaneous penalty. Per-family EB certifies 3/3 Avazu and 2/3 Criteo runs, while both Hoeffding variants certify 0/3 in either dataset.

The independent search stress test (Figure 2/Table 5) provides complementary error-rate evidence: over 1,000 repetitions per setting with n=3,000 and δ=0.05, naive maximization has FWER 1.000, while both simultaneous methods have zero observed false certificates under the strict null (95% exact-binomial upper bound ≈0.0030). With one gain-0.02 candidate among H=1,000, EB detects it in 30.8% of repetitions versus 11.0% for Hoeffding. Together, the controlled and CTR comparisons show how simultaneous certification and variance-adaptive bounds affect the decision to deploy a correction.

2. Validation budget and split roles. Holding D0/D1/D2/D4 fixed, we evaluated prespecified 10K/20K/30K prefixes of D3. Under per-family correction, extended-MLP certificates are 0/3, 0/3, 3/3 on Avazu (null-inclusive gains 0, 0, 0.000828) and 0/3, 0/3, 2/3 on Criteo (gains 0, 0, 0.000235). The 30K endpoint uses per-family correction; the table above uses joint-eight. D0 trains the checkpoint, D1 forms candidates, D2 fits corrections, and D3 selects and certifies. D4 provides independent reporting and is not needed for CROSSAUDIT itself. The prefix experiment isolates how validation budget influences certification; optimizing the full allocation across splits is a separate design question.

3. MLP optimization sensitivity. We increased its maximum training budget from 30 to 100 epochs and early-stopping patience from 5 to 15, with D0-only learning-rate selection and scheduling. All six runs chose initial LR 0.0003; the selected extended refits used 13–14 epochs on Avazu and 9–10 on Criteo. Mean base log-loss improved 0.409673 → 0.408322 and 0.484401 → 0.479195, and AUC improved 0.738309 → 0.739421 and 0.760586 → 0.763125 (Avazu/Criteo). Remaining joint-eight null-inclusive pair gains decreased from 0.001052 → 0.000560 and 0.000523 → 0.000082, with 3/3 and 1/3 extended-model certificates. Appendix I gives the training schedules, validation comparisons, candidate manifests, selection locks, and D4 results.

I appreciate the effort of the authors. I will go over each original concern, and briefly discuss the extent to which it has been addressed.

In terms of presentation; while I appreciate the authors attempt to improve the presentation, I believe the paper remains hard to understand. While the device-country example helps, and the writing has improved, I still think many terms used are hard to understand. Not too continue nitpicking, but more to illustrate; let's just take line 40-41 from the manuscript:

We ask whether an additive update zz, estimated from a finite fitting sample, reduces risk and whether independent validation can support that claim

What is an additive update? what is a 'finite fitting sample'? what is 'independent validation'?

I believe the paper needs to adopt much more 'plain English' when describing these things. To illustrate; I believe line 40-41 basically describe; 'We ask whether adding a correction based on a feature cross (e.g. interactions of device type and country) can help with performance of the model, and whether we can estimate the usefulness of this correction can be established using a validation set'.

This example from line 40-41 is not the only one but I am using it to describe a broader problem I have with the paper.

In terms of the comparison to selection based on validation; I understand that what the authors are doing is more sophisticated than simply selecting based on some validation criterion. I have a couple of outstanding questions regarding the comparison;

  1. Presumably, you can use more samples when using plain selection based on the validation set (no five-fold split is needed, as for your procedure). Is this taken into account?
  2. 'Validation-mean selection yields larger observed D4 gains' does this mean it is better?

I appreciate the authors adding an experiment where they vary the validation split, but again have genuine trouble understanding what the result of this; in plain english, if you vary the size of the allocation across the the five splits, do the results still hold? when yes/no?

I also appreciate the authors redoing the MLP experiments but I do share the concern of other reviewers that it remains undertuned.

Overall, the main concern I have against acceptance of the paper still holds (clarity of writing), hence why I retain my score.

Reviewer_GsZKOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies when explicit feature crosses can improve an already trained model. It analyzes the trade-off between residual signal and estimation cost, and proposes CROSSAUDIT to certify improvements using independent validation. Experiments show that finer crosses can hurt performance, hierarchical sharing helps, and real-label improvements often come from lower-order effects.

Critical strengths
  1. The paper offers an interesting perspective by distinguishing representational capacity from the ability to learn useful corrections with finite data.

  2. The theoretical analysis explains why finer feature crosses can hurt performance, supported by controlled experiments.

  3. CROSSAUDIT provides statistical guarantees for selecting beneficial updates, and the experiments carefully examine whether pair-based improvements come from genuine interactions.

Critical weaknesses
  1. The refinement theorem relies on restrictive assumptions and does not directly cover the regularized logistic learners used in the experiments.

  2. The real-label experiments find no certified improvements from residualized pair updates, leaving the benefits of genuine interactions unclear.

  3. The MLP checkpoints perform worse than simpler logistic models, raising questions about whether the findings extend to stronger, better-trained models.

Questions for authors
  1. How are candidate feature pairs selected on D1? Would different selection methods affect the results?

  2. Could the lack of positive certificates for residualized pair updates in the real-label experiments because of the residualization method used?

  3. Would CROSSAUDIT still find useful updates with stronger or better-trained models?

2 comments
AuthorsOpenReview ↗

Response to Reviewer GsZK

Thank you for the helpful questions.

1. Refinement theory and its empirical counterpart. Theorem 4.2 isolates the effect of extra estimation directions under nested Gaussian projections that expose the same signal. The semi-synthetic CTR experiment tests this mechanism with real Avazu/Criteo covariates, planted logistic labels, regularized residual updates, exact log-loss gains, and independent D3 certification. At r=16, atomic versus hierarchical D4 gains are 0.00108 versus 0.00761 on Avazu and 0.00283 versus 0.01038 on Criteo (best non-null subfamily selections under the common 318-tuple penalty). Hierarchical updates obtain positive certificates in all 18 dataset–seed–pair settings, versus 16/18 for atomic updates; shuffled and support-matched wrong controls obtain none. The theorem remains a projection result; the logistic experiment is an empirical test of the same mechanism under regularization.

The exposure–cost frontier favors coarse or hierarchically shared representations when finer partitions mainly increase estimation dimension. When refinement exposes additional residual signal with adequate support, fine-grained updates can instead be beneficial. This gives a concrete representation choice tied to the available data.

2. What the residualized-pair control measures. For each fitted permissive pair, we subtract its D2 curvature-weighted projection onto the all-main-effect space. Across 18 checkpoint audits, residualized-pair families obtain no positive certificates. Matched comparisons (Table 14) show that residualization leaves only 0.8–15.8% of the permissive pair’s D4 gain in the four Avazu cases and negative D4 gains in the three Criteo cases. These results locate most of the certified permissive-pair utility in lower-order residual structure for the tested checkpoints.

The numerical projection is accurate: all runs meet the leakage tolerance, the maximum relative leakage is 2.93×10⁻⁸, and no LSQR run reaches its iteration limit. The conclusion is specific to this post-fit projection; a different reference space or pre-fit interaction-only basis could have different power. The planted-signal experiment independently shows that hierarchical updates can recover a specified pair signal.

3. Candidate generation and alternative choices. On D1, the generator ranks fields by residual-projection energy, takes the top 16, enumerates pairs, retains those with 20–12,000 observed joint cells, reranks feasible pairs by residual-projection energy, and keeps at most 40 pairs per checkpoint. The shared union contains at most 120 entries and preserves generator orientations. It is fixed before D2/D3, and both original and extended MLPs use the same union. A different generator changes the candidate family and may change discovery power; the simultaneous certificate applies to any family fixed before validation under the stated conditions. Appendix F.2 gives the implemented procedure.

4. Better-optimized checkpoints. We increased the MLP’s maximum training budget from 30 to 100 epochs and early-stopping patience from 5 to 15, selecting the initial learning rate on D0 alone (0.0003 in all six runs). Mean base log-loss improved from 0.409673 to 0.408322 on Avazu and from 0.484401 to 0.479195 on Criteo; AUC improved from 0.738309 to 0.739421 and from 0.760586 to 0.763125. Five of six seed-level loss comparisons and all six AUC comparisons improved. Under joint-eight correction, the extended MLP retains positive pair certificates in 3/3 Avazu and 1/3 Criteo runs, with null-inclusive D4 gains 0.000560 and 0.000082. Main logistic has lower base losses (0.405914/0.473533); FM provides a separate interaction-capable comparator. The reduction in remaining gain as the MLP improves supports the checkpoint-local view.

The main D3 audits use 30K observations, with per-family, joint-two, and joint-eight multiplicity scopes M=H, 2H, and 8H at δ=0.1. Each family selects a candidate or null under its stated penalty. Appendix I reports training schedules, actual H values, seed-level results, and run-level records.

I appreciate the authors for the additional discussions and results. They have addressed some of my concerns.

But I still have some concerns left. The real-label experiments still show no positive certificates for residualized pair updates. The additional MLP experiments are helpful, but the improved models still underperform simpler logistic models in terms of base log-loss.

I believe the paper has interesting contributions, but these concerns remain. So I will keep my original rating.

Reviewer_N12zOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper analyzes when an additive feature-cross repair can be fitted and certified on independent data. It combines a Gaussian exposure–noise analysis with simultaneous validation bounds, then studies refinement, parameter sharing, and lower-order repair controls.

Critical strengths

The refinement experiments hold the representable signal fixed while varying estimation cost. The lower-order controls are also informative: they test whether apparent pair-table gains actually require interactions. Reporting these negative results is useful.

Critical weaknesses
  1. The scope of the real-data findings remains unclear. The negative controls are informative. However, the MLP trails main-effect logistic regression in Table 10, while main-effect repair gives larger mean gains than pair repair on Criteo MLP in the separate Table 13 panel. It remains unclear whether these repair patterns persist on stronger, well-optimized expressive checkpoints.

  2. The theory offers limited guidance for discovery. The sufficient results use standard Gaussian projection and concentration arguments. The exposure frontier depends on an unknown signal, while CROSSAUDIT certifies an already fitted update. Their connection assumes sufficient population gain (Appendix B.6), leaving actionable candidate selection unresolved.

  3. Promised run records are absent. The archive supplies scripts and processed CSVs but lacks the locked manifests and seed-level logs described in Appendices C.6, G, and H. Candidate selection and certification counts cannot be cross-checked from those records.

Questions for authors
  1. Do the observed repair patterns persist on stronger, well-optimized expressive checkpoints?
  2. Which actionable conclusion about candidate selection follows from the exposure analysis beyond standard residual fitting and held-out selection?
  3. Can you provide the exact locked manifests and logs behind the reported tables?
2 comments
AuthorsOpenReview ↗

Response to Reviewer N12z

Thank you for the careful review.

1. Checkpoint quality and repair interpretation. We compared the original and extended MLPs on the same 200K-row Avazu/Criteo samples and splits (seeds 17/271/2027). The extended training increased the maximum budget from 30 to 100 epochs and patience from 5 to 15, with learning-rate selection on D0 alone, and all six runs selected 0.0003. The candidate union was generated by the original three checkpoints and locked before D2/D3, so both MLP variants audit identical candidates.

Under joint-eight correction, original → extended MLP yields:

  • Avazu: log-loss 0.409673 → 0.408322; AUC 0.738309 → 0.739421; certificates 3/3 → 3/3; null-inclusive D4 gain 0.001052 → 0.000560.
  • Criteo: log-loss 0.484401 → 0.479195; AUC 0.760586 → 0.763125; certificates 2/3 → 1/3; null-inclusive D4 gain 0.000523 → 0.000082.

Better optimization lowers the mean remaining repair gain while positive certificates persist in both datasets. Main logistic has lower base log-loss (0.405914/0.473533, Avazu/Criteo), and FM provides another interaction-capable checkpoint (0.40681/0.47517). The separate low-order audit (Table 13; seeds 101/503/4099) further characterizes the repair type: on Criteo MLP, mean null-inclusive D4 gain is (5.022 ± 2.562)×10⁻³ for main effects versus (0.894 ± 0.201)×10⁻³ for permissive pairs; post-fit residualized pairs receive no positive certificates. Thus, pair-indexed utility can include substantial lower-order residual structure.

2. What the theory tells us to select. Theorem 3.2 identifies three quantities governing discoverability: exposed residual signal, effective noise-fitting dimension, and candidate-search cost. Operationally, this favors well-supported coarse crosses when extra detail adds little residual signal, and hierarchical sharing when refinement mainly fragments support. On D1, we rank fields by residual-projection energy, retain the top 16, screen pairs for 20–12,000 observed joint cells, and keep up to 40 pairs per checkpoint. This provides a computable screening rule before fitting, while the exposure–cost index itself is an oracle diagnostic.

The controlled known-signal study supports the criterion: the exposure–cost score distinguishes positive from nonpositive D4 gains with AUC 0.940 ± 0.018, compared with 0.757 ± 0.043 for raw signal strength. At r=16, atomic/hierarchical D4 gains are 0.00108/0.00761 on Avazu and 0.00283/0.01038 on Criteo (common 318-tuple penalty; certification counts reported separately). These results favor sharing when refinement fragments support without adding signal.

3. Reproducibility and correction scope. The supplementary package provides detailed run-level records for the results reported in the revision, including D0 optimization trials, D1 rankings and support screens, candidate-source and locked-union manifests, D2 update bounds, per-tuple D3 statistics and selection locks, and D4 reports. Across the six dataset–seed runs, all 216 comparisons against the recorded reference metrics for the main-logistic, FM, and original-MLP checkpoints are within the stated tolerances. The per-seed records are in records/records_supplement/six_run_record/ in feature_cross.zip; Appendix G summarizes the configurations and record contents.

The primary checkpoint audit uses a separate per-family correction for permissive-pair and shuffled-control candidates: for H pair×regularization×step tuples, M=H and L=log(2M/δ), with δ=0.1. Additional joint-two and joint-eight comparisons use M=2H and 8H, respectively, with each family selecting its best positive LCB or null. The implemented H values are (840,1080,920) on Avazu and (960,840,840) on Criteo (seeds 17/271/2027). For extended-MLP permissive pairs, per-family/joint-two/joint-eight certification counts and gains are 3/3, 3/3, 3/3 and 0.000828, 0.000560, 0.000560 on Avazu; 2/3, 2/3, 1/3 and 0.000235, 0.000235, 0.000082 on Criteo. The protocols and results appear in Appendices F and I.

Thanks for the additional experiments and clarifications. The new results address some of my concerns, but it’s still unclear how well the findings carry over to stronger models or how much the analysis helps with choosing which feature crosses to try. I’ll keep my score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.