¿Qué tan intrínseco es el término

Un -net para un espacio de rango es un subconjunto de tal que no es vacío para todos tal que.( X , R ) N X N ∩ R R ∈ R | X ∩ R | ≥ ε | X $\varepsilon$$(X,\mathcal{R})$$N$$X$$N\cap R$$R\in \mathcal{R}$$|X\cap R| \ge \varepsilon |X|$

Dado un espacio de rango de dimensión VC , un -net de tamaño se puede calcular en el tiempo(ver [1], Thm 4.6).d ε O ( $(X,R)$$d$$\varepsilon$O(d)3d($O\left(\frac{d}{\varepsilon}\log\left(\frac{d}{\varepsilon}\right)\right)$$O(d)^{3d}\left(\frac{1}{\varepsilon^2}\log\left(\frac{d}{\varepsilon}\right)\right)^d|X|$

¿En qué medida el término intrínseco a este problema? Específicamente, ¿se puede mejorar a ? ¿Se conocen límites inferiores? 2 O ( d $O(d)^{3d}$$2^{O(d)}$

Una pregunta relacionada: ¿existen condiciones generales en para las cuales se sabe que existe tal mejora?$(X,R)$

[1] Bernard Chazelle. El método de discrepancia. 2000.

Si está de acuerdo con un algoritmo aleatorio, entonces puede muestrear aleatoriamente puntos , y este será un -net con probabilidad de al menos . ϵ 1 - $O((d/\epsilon) \log (d/\epsilon \delta))$$\epsilon$$1-\delta$

Para el algoritmo determinista, creo que el término proviene de la siguiente razón. Primero particiona su conjunto completo en subconjuntos de tamaño sobre donde es el tamaño de la -net que espera obtener al final. Luego, combina dos de estos subconjuntos y reduce a la mitad ese tamaño. (Básicamente, esto se repite hasta que quede un conjunto). El paso de reducción esencialmente considera todos los rangos interesantes del conjunto combinado de tamaño . Según los límites de VC, hay aproximadamente rangos , y debe "verificar" cada uno de estos para ver si se ha alcanzado. El tiene un en él. El s = O ( ( d / ϵ ) log ( d / ϵ ) ) s ϵ 2 s O ( ( 2 s ) d ) s d d O ( d ) d s $d^{O(d)}$$s = O((d/\epsilon) \log (d/\epsilon))$$s$$\epsilon$$2s$$O((2s)^d)$$s^d$$d^{O(d)}$$d$en el término es necesario. Entonces, para reducir este límite, utilizando este marco determinista, de alguna manera necesitaría "verificar" implícitamente todos los rangos sin enumerarlos explícitamente. Esto parece difícil de hacer de manera determinista, pero no estoy seguro de conocer un límite inferior explícito: la mayoría del trabajo en este campo supone que es constante y abusa en gran medida. $s$$d$