Chromatic Collision-Free Pairwise Batches

1. Integration point: modify pair construction and minibatch scheduling for a pairwise objective such as metric learning, Siamese training, pairwise ranking, or graph edge prediction. Build a graph whose vertices are examples in the current data pool and whose directed edges are positive or negative pairs contributing to the loss. Ignore direction during coloring because the matching condition concerns shared endpoints. Compute a greedy edge coloring by processing edges in descending endpoint-degree order and assigning each edge the smallest color unused at either endpoint. 2. Pseudocode: edges = build_pairs(pool); colors = greedy_edge_color(edges); grad_est = 0; for t in 1..r: c = sample_categorical(q); Ec = edges[colors == c]; loss_c = sum(loss(model(x_i), model(x_j)) for (i,j) in Ec); grad_c = backward(loss_c); grad_est += grad_c/(r*q[c]); optimizer.step(grad_est). For exact accumulation, process every color and sum all color gradients. 3. Compute from the paper's mathematics the matching partition, chromatic count $\chi$, and inverse-probability correction. Estimate color sampling probabilities using an exponential moving average of color-gradient norms or squared norms, for example $q_c\propto\sqrt{\widehat{\operatorname{Var}}(g_c)}$, while enforcing $q_c\ge q_{\min}$ to retain coverage. Log $\chi$, color-class sizes, gradient variance, and endpoint collision rates. 4. First cheap experiment: train a small Siamese or supervised metric-learning network on CIFAR-10 using a fixed number of pairwise loss evaluations. Compare ordinary random pair minibatches, one-color matching minibatches, and two-color minibatches under identical optimizer and FLOP budgets. Measure gradient variance across repeated batches, loss smoothness, wall-clock throughput, and validation accuracy. The method succeeds if matching batches reduce gradient variance or improve accuracy per pair evaluation; it fails if greedy coloring overhead dominates or if collision removal provides no benefit after equalizing compute.