Unfortunately, to state precisely the question, I need some formal preliminaries.

Let $d \in \mathbb{N}$.

For each $d^* \in \{1,\dots,d\}$, define $\mathcal{M}_{d^*}$ be the set of probability measures whose support is contained in a $d^*$-dimensional submanifold of $[0,1]^d$.

For each $L>0$, define $\mathcal{F}_L:=\{\eta \colon [0,1]^d\to[0,1] \mid \eta \text{ is } L\text{-Lipschitz continuous}\}$.

Let $(X,Y), (X_1,Y_1), (X_2,Y_2), \dots$ be a family of $[0,1]^d\times[0,1]$-valued random variables.

Assume that for each $L>0$ and each $d^*\in\{1,\dots,d\}$ we have a family $\mathfrak{P}_{L,d^*}$ of probability measures on the sample space where the previous random variables are defined, such that $\mathbb{P} \in \mathfrak{P}_{L,d^*}$ if and only if there exist $\eta \in \mathcal{F}_L$ and $\mu \in \mathcal{M}_{d^*}$ for which:

  • $(X,Y), (X_1,Y_1), (X_2,Y_2), \dots$ is a $\mathbb{P}$-i.i.d. sequence.
  • The distribution of $X$ with respect to $\mathbb{P}$ is $\mathbb{P}_X = \mu$.
  • $\eta(X)$ is (a version of) the conditional expectation of $Y$ given $X$ with respect to $\mathbb{P}$, i.e. $\mathbb{E}_{\mathbb{P}}[Y\mid X] = \eta(X)$.

End of the preliminaries.

I'm looking for the holy-grail of data-driven nonparametric regression. Precisely: does there exist a sequence of measurable functions $(A_t)_{t\in\mathbb{N}}$ such that

  1. $\forall t \in \mathbb{N}, A_t : \big([0,1]^d\times[0,1]\big)^{t} \times[0,1]^d \to [0,1]$
  2. $\exists C>0, \forall L>0, \forall d^* \in\{1,\dots,d\}, \forall \mathbb{P}\in \mathfrak{P}_{L,d^*}, \forall t \in \mathbb{N}, \mathbb{E}_{\mathbb{P}} \big[ \big| A_t(X_1,Y_1,\dots,X_{t},Y_t,X) - \mathbb{E}_{\mathbb{P}}[Y\mid X] \big|^2 \big] \le C\big(\frac{L^{d^*}}{t}\big)^{\frac{2}{2+d^*}}?$

The second point basically requires that the data-driven regressor determined by the sequence $(A_t)_{t \in \mathbb{N}}$ is minimax-optimal in the mean-square sense (the reason why I suspect that those should be the dependencies on the dimension and on the Lipschitz constant can be found for example in Theorem 3.2 in the book by Györfi, Kohler, Krzyzak, Walk - A Distribution-Free Theory of Nonparametric Regression) adapting automatically to the actual Lipschitz constant $L$ of the actual regression function $\eta$, and to the effective dimension $d^*$ of the manifold where the actual distribution $\mu$ of the features lives, without knowing these parameters in advance.

I didn't manage to find anything in the literature and I strongly suspect that something like this should be too good to exist (maybe some kind of no free-lunch theorem?). Does anyone know if this problem was tackled anywhere and what could be the answer?

  • $\begingroup$ It seems that "Fast, smooth and adaptive regression in metric spaces" by Samory Kpotufe may be a starting point toward a solution. $\endgroup$
    – Bob
    Commented Apr 15, 2022 at 10:00


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.