Optimal Polynomial Tractability Exponents for the Inverse Star Discrepancy

Resumen Técnico: Exponentes de Tractabilidad Polinomial Óptimos para la Discrepancia Estelar Inversa

Planteamiento del Problema
El artículo aborda el problema de determinar los exponentes de tractabilidad polinomial óptimos para la discrepancia estelar inversa, denotada como $n^*(d, \varepsilon)$. Esta cantidad representa el número mínimo de puntos $N$ requeridos en un cubo unitario de $d$ dimensiones $[0, 1)^d$ para lograr una discrepancia estelar $D^*_N(P) \le \varepsilon$.

Trabajos previos establecieron que $n^*(d, \varepsilon)$ depende linealmente de la dimensión $d$ y polinomialmente de $\varepsilon^{-1}$. Específicamente, Heinrich, Novak, Wasilkowski y Woźniakowski (2001) demostraron que el límite superior es $n^*(d, \varepsilon) \lesssim d \varepsilon^{-2}$, mientras que Hinrichs (2004) estableció el límite inferior $n^*(d, \varepsilon) \gtrsim d \varepsilon^{-1}$. Si bien la dependencia lineal de $d$ fue confirmada, el exponente exacto de $\varepsilon^{-1}$ en el límite superior seguía siendo una cuestión abierta: ¿podía reducirse el exponente 2 a un valor menor $p < 2$?

Metodología
El artículo resuelve esta cuestión demostrando que el exponente 2 en el límite superior es óptimo, incluso permitiendo una dependencia polinomial arbitraria fija respecto a la dimensión. La metodología central consiste en:

1. Análisis del Régimen Polinomial: En lugar de intentar fortalecer el límite inferior de manera uniforme para todos los valores de $d$ y $\varepsilon$, el autor analiza el comportamiento de $n^*(d, \varepsilon)$ en "franjas polinomiales" específicas donde la dimensión crece como una potencia del inverso del error, es decir, $d \asymp \varepsilon^{-\alpha}$ para $0 < \alpha < 1$.
2. Construcción de la Matriz de Gram: La demostración utiliza un argumento de matriz de Gram. El autor construye una familia de productos tensoriales de una función escalón unidimensional centrada $h(t) = 3\mathbb{1}_{[0, 1/3)}(t) - 1/\sqrt{2}$.
   • Estas funciones son elegidas de tal manera que sus productos tensoriales sobre conjuntos de coordenadas distintos son ortogonales con respecto a la medida de Lebesgue.
   • Una discrepancia estelar pequeña implica que los productos internos empíricos de estas funciones sobre el conjunto de puntos $P$ deben estar cerca de sus productos internos teóricos de Lebesgue.
3. Desigualdad de Traza-Rango: La evaluación de estas funciones tensoriales en $N$ puntos genera un conjunto de vectores en $\mathbb{R}^N$. Se demuestra que la matriz de Gram de estos vectores tiene una traza grande y una traza de su cuadrado controlada. Al aplicar la desigualdad elemental de traza-rango, $\text{rank}(G) \ge (\text{tr } G)^2 / \text{tr}(G^2)$, el autor deriva un límite inferior para el rango, lo cual corresponde al número de puntos $N$.

Contribuciones Clave y Resultados
El resultado principal es el Teorema 1.1, que establece un nuevo límite inferior para $n^*(d, \varepsilon)$ en el régimen donde $A\varepsilon^{-\alpha} \le d \le B\varepsilon^{-\alpha}$. Específicamente, para cualquier $0 < \alpha < 1$, existen constantes tales que:
$$n^*(d, \varepsilon) \ge c_{\alpha, B} \, d \, \varepsilon^{-(2-\alpha)}$$
A lo largo de estas franjas, el lado derecho se comporta como $\varepsilon^{-2}$.

Esto conduce al Teorema 1.2, que define los exponentes de tractabilidad polinomial óptimos:

• El exponente de precisión $p^* = \inf \{ p : n^*(d, \varepsilon) \le C d^q \varepsilon^{-p} \}$ es exactamente 2.
• El exponente de dimensión $q^* = \inf \{ q : n^*(d, \varepsilon) \le C d^q \varepsilon^{-p} \}$ es exactamente 1.

Consecuentemente, el límite superior $n^*(d, \varepsilon) \le C d \varepsilon^{-2}$ proporcionado por Heinrich et al. (2001) es individualmente óptimo en ambos exponentes.

Significancia y Afirmaciones
El artículo afirma que el exponente 2 para $\varepsilon^{-1}$ no puede mejorarse, incluso si se permite una dependencia polinomial arbitraria fija respecto a la dimensión $d$. Esto resuelve la brecha entre el límite inferior previamente conocido ($\varepsilon^{-1}$) y el límite superior ($\varepsilon^{-2}$) respecto al exponente de precisión.

El autor señala varios matices respecto al alcance de estos resultados:

• Complementariedad con Hinrichs: El nuevo límite de la matriz de Gram es más fuerte que el de Hinrichs ($d\varepsilon^{-1}$) específicamente en el régimen intermedio donde $d$ crece polinomialmente con $\varepsilon^{-1}$ (es decir, $d \ll \varepsilon^{-1}$). Sin embargo, para dimensiones fijas o cuando $d \gg \varepsilon^{-1}$, el límite de Hinrichs sigue siendo la estimación más fuerte.
• Sin Mejora Puntual: El resultado no implica un límite inferior puntual de $n^*(d, \varepsilon) \gtrsim d\varepsilon^{-2}$ para cada par $(d, \varepsilon)$. Para una $d$ fija, las construcciones clásicas de baja discrepancia muestran que $n^*(d, \varepsilon)$ puede ser tan bajo como $O(\varepsilon^{-1} (\log \varepsilon^{-1})^{d-1})$, lo cual es $o(\varepsilon^{-2})$. La optimalidad del exponente 2 es una propiedad de la tractabilidad polinomial uniforme a través de todas las dimensiones.
• Problema Abierto: Aunque los exponentes están determinados como óptimos, la dependencia mixta precisa de $d$ y $\varepsilon$ dentro de regímenes conjuntos específicos (los constantes exactos y los términos de orden inferior) sigue siendo un problema abierto.

En resumen, el artículo demuestra que el límite superior de Heinrich–Novak–Wasilkowski–Woźniakowski es ajustado en términos de sus exponentes asintóticos, confirmando que la discrepancia estelar inversa no puede computarse con una tasa mejor que $\varepsilon^{-2}$ en un sentido polinomial uniforme.