On the optimization of discrepancy measures
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911095332012032 |
|---|---|
| author | Clément, François Kirk, Nathan Owen, Art B. Rusch, T. Konstantin |
| author_facet | Clément, François Kirk, Nathan Owen, Art B. Rusch, T. Konstantin |
| contents | 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_\infty$ star discrepancy is a poor criterion for this because it is computationally expensive and lacks differentiability. Its usual replacement, the $L_2$ star discrepancy, is smooth but exhibits other pathologies shown by J. Matoušek. In an attempt to address these problems, we introduce the \textit{average squared discrepancy} which averages over $2^d$ versions of the $L_2$ star discrepancy anchored in the different vertices of $[0,1]^d$. Not only can this criterion be computed in $O(dn^2)$ time, like the $L_2$ star discrepancy, but also we show that it is equivalent to a weighted symmetric $L_2$ 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 Matoušek. Furthermore, we present a comprehensive numerical study showing in particular that optimizing for the average squared discrepancy leads to strong performance for the $L_2$ star discrepancy, whereas the converse does not hold. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_04926 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the optimization of discrepancy measures Clément, François Kirk, Nathan Owen, Art B. Rusch, T. Konstantin Numerical Analysis Optimization and Control 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_\infty$ star discrepancy is a poor criterion for this because it is computationally expensive and lacks differentiability. Its usual replacement, the $L_2$ star discrepancy, is smooth but exhibits other pathologies shown by J. Matoušek. In an attempt to address these problems, we introduce the \textit{average squared discrepancy} which averages over $2^d$ versions of the $L_2$ star discrepancy anchored in the different vertices of $[0,1]^d$. Not only can this criterion be computed in $O(dn^2)$ time, like the $L_2$ star discrepancy, but also we show that it is equivalent to a weighted symmetric $L_2$ 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 Matoušek. Furthermore, we present a comprehensive numerical study showing in particular that optimizing for the average squared discrepancy leads to strong performance for the $L_2$ star discrepancy, whereas the converse does not hold. |
| title | On the optimization of discrepancy measures |
| topic | Numerical Analysis Optimization and Control |
| url | https://arxiv.org/abs/2508.04926 |