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))].$$

  • 1
    $\begingroup$ 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]$? $\endgroup$
    – Clement C.
    Dec 23, 2019 at 13:10
  • $\begingroup$ My loss is pointwise, at each $x$; I updated the question. $\endgroup$
    – Aryeh
    Dec 23, 2019 at 13:45
  • $\begingroup$ I see, thanks for the clarification! $\endgroup$
    – Clement C.
    Dec 23, 2019 at 14:23
  • $\begingroup$ I'm really just looking for related keywords. So far "passive Lipschitz bandits" comes to mind -- anything else? $\endgroup$
    – Aryeh
    Dec 23, 2019 at 14:52
  • 1
    $\begingroup$ We investigated a version of this setup in [1], 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. [1] arxiv.org/abs/1802.09680 $\endgroup$
    – usul
    Dec 25, 2019 at 2:17

1 Answer 1


Well, we wrote a paper on it, so now it's definitely known: https://arxiv.org/abs/2010.09886


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.