Concentration Inequalities for Incomplete U-statistics over Arbitrary Sampling Graphs
arXiv:2607.17048
2026
Training
1 ideas extracted · analyzed Aug 30, 2026
What the math gives to ML
The paper turns dependence among pairwise kernel evaluations into a graph-structural quantity: edge coloring partitions sampled pairs into matchings, and terms within each matching depend on disjoint independent variables. This suggests a graph-aware minibatching method for pairwise neural objectives, where colors become collision-free microbatches and the chromatic index controls the number of dependent strata that must be combined. The most practical transfer is constructing training batches and confidence estimates from edge-color classes so that pairwise losses or gradients have predictable dependence and can be subsampled safely.
Ideas from this paper
Unverified
2026
Represent every pairwise training interaction as a directed edge and edge-color the interaction graph. Use one color class, or a small set of colors, as a microbatch: because a color class is a matching, no data example participates in two pairwise terms within that microbatch. This removes within-batch gradient collisions and provides a graph-dependent estimate of how many dependent strata are being combined.
Useful6/10
Difficulty5/10
Novelty7/10