Об одной многопараметрической задаче из теории информационной сложности

На семинаре планируется кратко рассказать о недавно сформировавшейся теории информационной сложности (Information-Based Complexity, [6]) и о ее интенсивно развивающемся направлении теории трактабильности многопараметрических задач аппроксимации (Tractability of multivariate problems, [2]-[5]). В качестве примера мы рассмотрим задачу аппроксимации в вероятностной постановке гауссовского элемента из $L_2([0,1]^d)$ с нормой $\|\cdot\|_d$, где параметрическая размерность $d$ может быть сколь угодно велика. Более конкретно, нас будет интересовать поведение при $d\to\infty$ следующей характеристики:
\begin{eqnarray*} n_d(\varepsilon,\delta)=\min\bigl\{n\in N: P \bigl(\|X_d-X_{d,n}\|_d^2>\varepsilon^2\, E \|X_d\|_d^2\bigr)\leqslant \delta \bigr\}, \end{eqnarray*}
где $\varepsilon, \delta\in(0,1)$, а $X_{d,n}$ — $n$-ранговая аппроксимация для $X_d$. С помощью неравенств концентрации мы покажем, что, например, для случайного поля Винера-Ченцова величина $n_d(\varepsilon,\delta)$ растет экспоненциально по $d$. Это “негативное” (с практической точки зрения) называется проклятием размерности (curse of dimensionality, [1]).

Список литературы

1. Lifshits M. A., Tulyakova E. V., Curse of dimensionality in approximation of random fields.— Probab. Math. Stat., 26 (2006), 1, 97–112.  
2. Novak E., Sloan I. H., Traub J. F., Wózniakowski H., Essays on the Complexity of Continuous Problems. European Mathematical Society Publishing House, Zürich (2009).  
3. Novak E., Wózniakowski H., Tractability of Multivariate Problems. Volume I: Linear Information, EMS Tracts Math. 6, European Mathematical Society Publishing House, Zürich (2008).  
4. Novak E., Wózniakowski H., Tractability of Multivariate Problems. Volume II: Standard Information for Functionals, EMS Tracts Math. 12, European Mathematical Society Publishing House, Zürich (2010).  
5. Novak E., Wózniakowski H., Tractability of Multivariate Problems. Volume III: Standard Information for Operators, EMS Tracts Math. 18, European Mathematical Society Publishing House, Zürich (2012).  
6. Traub J. F., Wasilkowski G. W., Wózniakowski H., Information-Based Complexity, Academic Press, New York (1988).