On the optimization of discrepancy measures

Points in the unit cube with low discrepancy can be constructed using algebra or, more recently, by direct computational optimization of a criterion. The usual L_∞ star discrepancy is a poor criterion for this because it is computationally expensive and lacks differentiability. Its usual replacement, the L2 star discrepancy, is smooth but exhibits other pathologies shown by J. Matouvsek. In an attempt to address these problems, we introduce the textitaverage squared discrepancy which averages over 2d versions of the L2 star discrepancy anchored in the different vertices of [0,1]d. Not only can this criterion be computed in O(dn2) time, like the L2 star discrepancy, but also we show that it is equivalent to a weighted symmetric L2 criterion of Hickernell's by a constant factor. We compare this criterion with a wide range of traditional discrepancy measures, and show that only the average squared discrepancy avoids the problems raised by Matouvsek. Furthermore, we present a comprehensive numerical study showing in particular that optimizing for the average squared discrepancy leads to strong performance for the L2 star discrepancy, whereas the converse does not hold.