Optimal Polynomial Tractability Exponents for the Inverse Star Discrepancy

技術要約：逆スター不一致性の最適多項式束縛指数

問題設定
本論文は、逆スター不一致性（inverse star discrepancy）として表される $n^*(d, \varepsilon)$ の最適な多項式束縛指数を決定する問題に取り組んでいる。この量は、$d$ 次元の単位立方体 $[0, 1)^d$ 内において、スター不一致性 $D^*_N(P) \le \varepsilon$ を達成するために必要な最小の点数 $N$ を表す。

先行研究では、$n^*(d, \varepsilon)$ が次元 $d$ に対して線形に、また $\varepsilon^{-1}$ に対して多項式的に依存することが確立されていた。具体的には、Heinrich, Novak, Wasilkowski, and Woźniakowski (2001) は上界 $n^*(d, \varepsilon) \lesssim d \varepsilon^{-2}$ を証明し、一方で Hinrichs (2004) は下界 $n^*(d, \varepsilon) \gtrsim d \varepsilon^{-1}$ を確立した。次元 $d$ に関する線形依存性は確認されていたが、上界における $\varepsilon^{-1}$ の正確な指数、すなわち、べき乗 2 をより小さい値 $p < 2$ に低減できるかどうかが未解決の問いであった。

手法
本論文は、任意の固定された次元に対する多項式依存性を許容した場合でも、上界における指数 2 が最適であることを証明することで、この問いを解決する。核心となる手法は以下の通りである：

1. 多項式領域の解析： すべての $d$ と $\varepsilon$ に対して一様に下界を強めるのではなく、著者は、次元が逆誤差の累乗として増大する、すなわち $d \asymp \varepsilon^{-\alpha}$ ($0 < \alpha < 1$) である特定の「多項式ストリップ」における $n^*(d, \varepsilon)$ の挙動を分析する。
2. グラム行列の構成： 証明にはグラム行列の議論を用いている。著者は、中心化された一次元のステップ関数 $h(t) = 3\mathbb{1}_{[0, 1/3)}(t) - 1/\sqrt{2}$ のテンソル積の族を構成する。
   • これらの関数は、異なる座標集合上のテンソル積が、ルベーグ測度に関して直交するように選択されている。
   • 小さなスター不一致性は、これらの関数の点集合 $P$ 上での経験的な内積が、それらの理論的なルエーグ内積に近いことを意味する。
3. トレース・ランク不等式： これらのテンソル関数を $N$ 個の点で評価することで、$\mathbb{R}^N$ 内のベクトルの集合が生成される。このベクトルのグラム行列は、大きなトレースと制御された二乗のトレースを持つことが示される。基本的なトレース・ランク不等式 $\text{rank}(G) \ge (\text{tr } G)^2 / \text{tr}(G^2)$ を適用することで、著者らはランクの下界を導出し、それが点数 $N$ に対応することを示す。

主な貢献と結果
主要な結果は定理 1.1 であり、これは $A\varepsilon^{-\alpha} \le d \le B\varepsilon^{-\alpha}$ という領域における $n^*(d, \varepsilon)$ の新しい下界を確立している。具体的には、任意の $0 < \alpha < 1$ に対して、以下の関係を満たす定数が存在する：
$$n^*(d, \varepsilon) \ge c_{\alpha, B} \, d \, \varepsilon^{-(2-\alpha)}$$
これらのストリップにおいて、右辺は $\varepsilon^{-2}$ として振る舞う。

これにより、定理 1.2 が導かれ、最適な多項式束縛指数が定義される：

• 精度指数 $p^* = \inf \{ p : n^*(d, \varepsilon) \le C d^q \varepsilon^{-p} \}$ は、正確に 2 である。
• 次元指数 $q^* = \inf \{ q : n^*(d, \varepsilon) \le C d^q \varepsilon^{-p} \}$ は、正確に 1 である。

したがって、Heinrich et al. (2001) による上界 $n^*(d, \varepsilon) \le C d \varepsilon^{-2}$ は、両方の指数において個別に最適である。

意義と主張
本論文は、次元 $d$ に対する任意の固定された多項式依存性を許容したとしても、$\varepsilon^{-1}$ の指数 2 を改善することはできないと主張している。これにより、既知の下界（$\varepsilon^{-1}$）と上界（$\varepsilon^{-2}$）の間の、精度指数に関するギャップが解消された。

著者は、これらの結果の範囲に関するいくつかの細かな点についても述べている：

• Hinrichs との補完性： この新しいグラム行列による下界は、次元が $\varepsilon^{-1}$ に対して多項式的に増大する中間領域（すなわち $d \ll \varepsilon^{-1}$）において、Hinrichs の下界 ($d\varepsilon^{-1}$) よりも強い。しかし、固定された次元や $d \gg \varepsilon^{-1}$ の場合においては、Hinrichs の下界の方が強い推定値となる。
• 点別での改善の不在： この結果は、すべての $(d, \varepsilon)$ のペアに対して $n^*(d, \varepsilon) \gtrsim d\varepsilon^{-2}$ という点別の下界を意味するものではない。固定された $d$ に対しては、古典的な低不一致構成法により、$n^*(d, \varepsilon)$ は $O(\varepsilon^{-1} (\log \varepsilon^{-1})^{d-1})$、すなわち $o(\varepsilon^{-2})$ まで低くなり得る。指数 2 の最適性は、すべての次元にわたる「一様な」多項式束縛性の特性である。
• 未解決問題： 指数は決定されたものの、特定の結合領域における $d$ と $\varepsilon$ の正確な混合依存性（正確な定数や低次項）は、依然として未解決の問題である。

要約すると、本論文は、Heinrich–Novak–Wasilkowski–Woźniakowski の上界がその漸近的指数においてタイトであることを示し、逆スター不一致性が一様な多項式的な意味において $\varepsilon^{-2}$ よりも優れたレートで計算できないことを裏付けている。