AI & ML
Optimal Polynomial Tractability Exponents for the Inverse Star Discrepancy
arXiv cs.NA0 views
arXiv:2607.23571v3 Announce Type: replace Abstract: The inverse of the star discrepancy $n^\ast(d, \varepsilon)$ satisfies \[ d \varepsilon^{-1} \lesssim n^{\ast}(d,\varepsilon)\lesssim d\varepsilon^{-2} \] for all $d \in \mathbb{N}$ and $0 < \varepsilon < \varepsilon_0$. The upper bound was established by Heinrich, Novak, Wasilkowski and Wo\'{z}niakowski (2001), while the lower bound is due to Hinrichs (2004). Steinerberger (2023) subsequently gave an elementary proof of the latter result. These bounds imply that the inverse of the star discrepancy depends linearly on the dimension, but the exact exponent of $\varepsilon^{-1}$ had remained open. In this paper we prove a lower bound which shows that the exponent $2$ of $\varepsilon^{-1}$ in the upper bound cannot be improved. More precisely, for every $0<\alpha<1$ and fixed $00$ and $\varepsilon_{\alpha,A}>0$ such that, for every $0<\varepsilon<\varepsilon_{\alpha,A}$ and every integer $d$ satisfying \[ A\varepsilon^{-\alpha}\le d\le B\varepsilon^{-\alpha}, \] one has \[ n^\ast(d,\varepsilon) \ge c_{\alpha,B}\,d\,\varepsilon^{-(2-\alpha)}. \] Along these polynomial strips the right-hand side is of order $\varepsilon^{-2}$. Consequently, every uniform polynomial upper estimate $n^{\ast}(d,\varepsilon)\le C d^q\varepsilon^{-p}$ must satisfy $p\ge2$. Together with the lower bound of Hinrichs (2004), which forces $q\ge1$, this proves that the exponents $p=2$ and $q=1$ in the Heinrich--Novak--Wasilkowski--Wo\'{z}niakowski upper bound are individually optimal. In particular, the optimal exponent $p^\ast = 2$.
Source:https://arxiv.org/abs/2607.23571PreviousLGNO: A Local-Global Neural Operator for Hyperbolic Conservation LawsNextOpen Benchmark of AI Impact on Humans (ImpactBench): an expert-guided, open platform for the holistic evaluation of AI impact on humans
Related posts
Hybrid retrieval with reciprocal rank fusion: notes from a RAG prototype
0dev.to
It is in co-creating, together. As humans do.
0dev.to
C64 Basic Dungeon Crawler: Stairs, Levels and Levelling Up (Part 11)
0Hacker News
Anthropic's internal AI use, at retail prices, now exceeds its employee pay
0Hacker News
Launch HN: Momentic (YC W24) – Agents that catch bugs by using your app
0Hacker News

Behavioral Design Unpacked: Nudges, Funnels & Persuasion | UX Unpacked #3
0dev.to UX