Optimal Finite Interval Discrepancy via Binary Refinement

What the math gives to ML

The paper gives a sharp minimax law for progressively refining a conserved positive mass into binary pieces: no binary refinement schedule can keep the largest-to-smallest piece ratio below D_n = 2^{1-1/\lceil n/2\rceil} at every intermediate cardinality, and a lex-merge construction attains this bound. This transfers to progressive mixture-of-experts growth, hierarchical routers, and adaptive quantizers, where experts or bins are split while preserving their total routing probability or capacity. The useful asset is not merely balanced final weights, but an optimal guarantee on imbalance throughout the entire expansion trajectory. A practical adaptation is to split an expert's routing prior using a constrained search that keeps the current ratio close to the theorem's target, then initialize child router logits with matching probability offsets.