Covering-Based Interaction Regularization

Integrate this at the loss level around a feature trunk g and prediction head f. Use k=2 or k=3 and generate perturbations u_i in input space; for images, use independent small Gaussian, color, or spatial perturbations, and for token models use continuous embedding perturbations before the embedding projection. For every minibatch element, evaluate g(x+sum_{i in S}u_i) for all S⊆[k], cache the results, and compute each inner difference by the inclusion-exclusion formula above. Enumerate families H of nonempty subsets whose union is [k]; for k=2 or 3 this is cheap by brute force. For each chosen H, form the list of inner differences Δg(x;u_T), feed these directions to f at base point g(x), and compute the outer finite difference. A practical penalty set is all H containing a block with |T|≥2, or all H with overlapping subsets; set w_H=1/|H| and normalize each term by the product of perturbation norms. Add the penalty to cross-entropy or MSE with λ swept over {1e-4,1e-3,1e-2}. The direct mixed difference and covering sum should agree numerically; log R_check as an implementation invariant. The mathematics determines the inclusion-exclusion and covering enumeration exactly; perturbation scales, penalty weights, and which H are penalized are empirical choices. First test on CIFAR-10 with a small ResNet-18, comparing ordinary weight decay, a standard Jacobian finite-difference penalty, and this covering penalty. Measure clean accuracy, accuracy under composed perturbations, calibration, and training stability across perturbation scales. Success is lower error under two simultaneous perturbations and smoother loss trajectories at equal clean accuracy, without more than roughly 2x training FLOPs for k=2.