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 '19 at 13:10
  • $\begingroup$ My loss is pointwise, at each $x$; I updated the question. $\endgroup$ – Aryeh Dec 23 '19 at 13:45
  • $\begingroup$ I see, thanks for the clarification! $\endgroup$ – Clement C. Dec 23 '19 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 '19 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 '19 at 2:17

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, privacy policy and cookie policy

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