Optimal Polynomial Tractability Exponents for the Inverse Star Discrepancy

Resumo Técnico: Expoentes de Tractabilidade Polinomial Ótimos para a Discrepância Estrela Inversa

Enunciado do Problema
O artigo aborda o problema de determinar os expoentes de tractabilidade polinomial ótimos para a discrepância estrela inversa, denotada por $n^*(d, \varepsilon)$. Esta quantidade representa o número mínimo de pontos $N$ necessários em um cubo unitário $d$-dimensional $[0, 1)^d$ para alcançar uma discrepância estrela $D^*_N(P) \le \varepsilon$.

Trabalhos anteriores estabeleceram que $n^*(d, \varepsilon)$ depende linearmente da dimensão $d$ e polinomialmente de $\varepsilon^{-1}$. Especificamente, Heinrich, Novak, Wasilkowski e Woźniakowski (2001) provaram o limite superior $n^*(d, \varepsilon) \lesssim d \varepsilon^{-2}$, enquanto Hinrichs (2004) estabeleceu o limite inferior $n^*(d, \varepsilon) \gtrsim d \varepsilon^{-1}$. Embora a dependência linear em $d$ tenha sido confirmada, o expoente exato de $\varepsilon^{-1}$ no limite superior permaneceu uma questão em aberto: poderia o expoente 2 ser reduzido para um valor menor $p < 2$?

Metodologia
O artigo resolve esta questão provando que o expoente 2 no limite superior é ótimo, mesmo ao permitir uma dependência polinomial arbitrária e fixa em relação à dimensão. A metodologia central envolve:

1. Análise do Regime Polinomial: Em vez de tentar fortalecer o limite inferior uniformemente para todos os $d$ e $\varepsilon$, o autor analisa o comportamento de $n^*(d, \varepsilon)$ em "faixas polinomiais" específicas onde a dimensão cresce como uma potência da inversa do erro, isto é, $d \asymp \varepsilon^{-\alpha}$ para $0 < \alpha < 1$.
2. Construção de Matriz de Gram: A prova utiliza um argumento de matriz de Gram. O autor constrói uma família de produtos tensoriais de uma função degrau unidimensional centrada $h(t) = 3\mathbb{1}_{[0, 1/3)}(t) - 1/\sqrt{2}$.
   • Estas funções são escolhidas de tal forma que seus produtos tensoriais sobre conjuntos de coordenadas distintos são ortogonais em relação à medida de Lebesgue.
   • Uma pequena discrepância estrela implica que os produtos internos empíricos destas funções sobre o conjunto de pontos $P$ devem estar próximos de seus produtos internos teóricos de Lebesgue.
3. Desigualdade de Traço-Posto (Trace-Rank): Avaliar estas funções tensoriais em $N$ pontos gera um conjunto de vetores em $\mathbb{R}^N$. Mostra-se que a matriz de Gram destes vetores possui um traço grande e um traço do seu quadrado controlado. Ao aplicar a desigualdade elementar de traço-posto, $\text{rank}(G) \ge (\text{tr } G)^2 / \text{tr}(G^2)$, o autor deriva um limite inferior para o posto, que corresponde ao número de pontos $N$.

Contribuições Principais e Resultados
O resultado primário é o Teorema 1.1, que estabelece um novo limite inferior para $n^*(d, \varepsilon)$ no regime onde $A\varepsilon^{-\alpha} \le d \le B\varepsilon^{-\alpha}$. Especificamente, para qualquer $0 < \alpha < 1$, existem constantes tais que:
$$n^*(d, \varepsilon) \ge c_{\alpha, B} \, d \, \varepsilon^{-(2-\alpha)}$$
Ao longo destas faixas, o lado direito comporta-se como $\varepsilon^{-2}$.

Isto leva ao Teorema 1.2, que define os expoentes de tractabilidade polinomial ótimos:

• O expoente de precisão $p^* = \inf \{ p : n^*(d, \varepsilon) \le C d^q \varepsilon^{-p} \}$ é exatamente 2.
• O expoente de dimensão $q^* = \inf \{ q : n^*(d, \varepsilon) \le C d^q \varepsilon^{-p} \}$ é exatamente 1.

Consequentemente, o limite superior $n^*(d, \varepsilon) \le C d \varepsilon^{-2}$ fornecido por Heinrich et al. (2001) é individualmente ótimo em ambos os expoentes.

Significância e Alegações
O artigo alega que o expoente 2 para $\varepsilon^{-1}$ não pode ser melhorado, mesmo se permitirmos uma dependência polinomial arbitrária e fixa na dimensão $d$. Isto resolve a lacuna entre o limite inferior previamente conhecido ($\varepsilon^{-1}$) e o limite superior ($\varepsilon^{-2}$) em relação ao expoente de precisão.

O autor observa várias nuances relativas ao escopo destes resultados:

• Complementaridade com Hinrichs: O novo limite de matriz de Gram é mais forte que o limite de Hinrichs ($d\varepsilon^{-1}$) especificamente no regime intermediário onde $d$ cresce polinomialmente com $\varepsilon^{-1}$ (isto é, $d \ll \varepsilon^{-1}$). Para dimensões fixas ou quando $d \gg \varepsilon^{-1}$, o limite de Hinrichs permanece a estimativa mais forte.
• Não Melhoria Pontual: O resultado não implica um limite inferior pontual de $n^*(d, \varepsilon) \gtrsim d\varepsilon^{-2}$ para cada par $(d, \varepsilon)$. Para $d$ fixo, construções clássicas de baixa discrepância mostram que $n^*(d, \varepsilon)$ pode ser tão baixo quanto $O(\varepsilon^{-1} (\log \varepsilon^{-1})^{d-1})$, o que é $o(\varepsilon^{-2})$. A otimalidade do expoente 2 é uma propriedade da tractabilidade polinomial uniforme através de todas as dimensões.
• Problema Aberto: Embora os expoentes tenham sido determinados como ótimos, a dependência mista precisa entre $d$ e $\varepsilon$ dentro de regimes conjuntos específicos (as constantes exatas e termos de ordem inferior) permanece um problema aberto.

Em resumo, o artigo demonstra que o limite superior de Heinrich–Novak–Wasilkowski–Woźniakowski é apertado em termos de seus expoentes assintóticos, confirmando que a discrepância estrela inversa não pode ser computada com uma taxa melhor que $\varepsilon^{-2}$ em um sentido polinomial uniforme.