Discrepancy-balanced minibatch selection

Integrate this at the dataloader or minibatch-construction stage, before the forward pass used for the parameter update. At every training step, draw an IID candidate pool C of size M=kb, with k in {2,4,8}. Obtain a detached feature vector phi(x_i) for every candidate: initially use the penultimate-layer activation from the previous step, a fixed random projection of the input, or a small EMA encoder. Compute the pool mean mu_C=M^{-1} sum_{i in C} phi(x_i). Select exactly b examples minimizing D(B)=||b^{-1} sum_{i in B} phi(x_i)-mu_C||^2. Use greedy forward selection: initialize B as empty, repeatedly add the candidate giving the smallest updated discrepancy, and optionally perform 1-for-1 swaps for 2 to 5 local-search passes. The quadratic kernel form can accelerate scoring with precomputed K_ij=phi_i^T phi_j; for large p, normalize or project features to 32 to 128 dimensions. To reduce selection bias, randomly choose among the best r candidates at each greedy step, and compare against uniform selection from the same candidate pool. Pseudocode: C=sample(M); Phi=detach(encoder(C)); mu=mean(Phi); B=[]; for t in 1..b: j=argmin_j norm((sum(Phi[B])+Phi[j])/b-mu)^2; B.append(j); B=local_swaps(B); loss=mean(loss_fn(model(x[B]),y[B])); update(model,loss). The paper supplies the discrepancy and variance identity; the feature map, pool size, and greedy approximation are empirical choices. First test on CIFAR-10 with a small ResNet-18 and batch size 128, using candidate pools of 256 and 512, then on a small language model with next-token batches grouped by sequence. Measure gradient cosine similarity to a large reference batch, gradient variance across repeated batches, training loss at equal examples and equal wall-clock time, and final validation accuracy. Success means lower gradient variance and faster loss descent without worse validation performance; reject the method if candidate-scoring overhead exceeds the saved optimization steps or if feature balancing creates measurable selection bias.