# Is this a known learning problem?

Let $$(\mathcal{X},\rho)$$ be a metric space (say, $$\mathcal{X}=[0,1]$$ with the Euclidean metric). Let $$\alpha:\mathcal{X}\to[0,1]$$ be unknown. Suppose that $$\mathcal{X}$$ is endowed with a distribution $$\mu$$ from which $$(X_1,\ldots,X_n)$$ is sampled iid. Further, for each $$X_i$$, we observe $$Y_i\sim\mathrm{Bernoulli}(\alpha(X_i))$$.

Our goal is to recover $$\alpha$$ from the finite sample, under some loss function (I tend to favor the pointwise loss $$\ell(\hat\alpha,\alpha)=$$ $$KL(\hat\alpha||\alpha) = \hat\alpha\log(\hat\alpha/\alpha) + (1-\hat\alpha)\log[(1-\hat\alpha)/(1-\alpha)] ,$$ but other loss functions can be considered also.)

Obviously, there is no hope of recovering $$\alpha$$ without some regularity condition, such as Lipschitz continuity.

Does this problem fall under some known framework?

Edit: Following Clement's comment, a clarification. The loss I defined above is pointwise, at each $$x$$ --- so it should really be $$\ell(\hat\alpha(x),\alpha(x))$$. The overall risk is then $$R(\alpha)=E_X[\ell(\hat\alpha(X),\alpha(X))].$$

• Based on your description, $\alpha$ is a function to be learnt, but your suggested loss seems to treat it as a single parameter in $[0,1]$? Dec 23, 2019 at 13:10
• My loss is pointwise, at each $x$; I updated the question. Dec 23, 2019 at 13:45
• I see, thanks for the clarification! Dec 23, 2019 at 14:23
• I'm really just looking for related keywords. So far "passive Lipschitz bandits" comes to mind -- anything else? Dec 23, 2019 at 14:52
• We investigated a version of this setup in , but not from this PAC perspective. Didn't come across any relevant PAC literature. The issue we were looking at is that loss functions such as yours are not necessarily "identifiable" from samples $(x_i,y_i)$. Happy to explain more.  arxiv.org/abs/1802.09680
– usul
Dec 25, 2019 at 2:17