Refit or Expand? Finite-Sample Certification of Interaction Surrogates under Compound Shifts

Assessing multistage inference under compound distribution shifts requires repeated evaluations across parameter settings because interacting parameters and noncommuting operators can produce non-additive performance changes. Interaction surrogates approximate these joint effects using low-order marginal moments. However, when surrogate error exceeds a tolerance, empirical point estimates cannot establish whether the discrepancy can be resolved by coefficient refitting or requires additional features. We introduce a finite-sample certification framework based on empirical Bernstein confidence intervals. We solve two linear programs: a robust refit program provides an upper bound on the error achievable in the surrogate class, while a dual program provides a lower bound for every class member through the design matrix’s left nullspace. These bounds can certify parameter misfit or feature inadequacy and identify minimal adequate subsets among candidate terms. For bilinear surrogates, the same guarantees hold uniformly over continuous product mixtures of evaluated marginals. Vision and language experiments show when interactions can be omitted, when refitting suffices, and when feature expansion is required. For ResNet-50 on ImageNetV2 under resampling/JPEG shifts, the one-term class has certified error at least 0.185 pp while a two-term surrogate has certified error at most 0.135 pp. For blur/JPEG, order reversal changes error by over 6 pp. The interaction surrogates correct all three order selection errors made by the additive approximation.