<p>Well, we wrote a paper on it, so now it's definitely known:
<a href="https://arxiv.org/abs/2010.09886" rel="nofollow noreferrer">https://arxiv.org/abs/2010.09886</a></p>

CC BY-SA 4.0
2020-10-22T18:53:37.987Z
2020-10-22T18:53:37.987Z
Aryeh
<p>Let <span class="math-container">$(\mathcal{X},\rho)$</span> be a metric space (say, <span class="math-container">$\mathcal{X}=[0,1]$</span> with the Euclidean metric). Let <span class="math-container">$\alpha:\mathcal{X}\to[0,1]$</span> be unknown. Suppose that <span class="math-container">$\mathcal{X}$</span> is endowed with a distribution <span class="math-container">$\mu$</span> from which <span class="math-container">$(X_1,\ldots,X_n)$</span> is sampled iid. Further, for each <span class="math-container">$X_i$</span>, we observe <span class="math-container">$Y_i\sim\mathrm{Bernoulli}(\alpha(X_i))$</span>.</p>

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

<p>Obviously, there is no hope of recovering <span class="math-container">$\alpha$</span> without some regularity condition, such as Lipschitz continuity.</p>

<p>Does this problem fall under some known framework?</p>

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

CC BY-SA 4.0
2019-12-23T13:10:07.563Z
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]$?
Clement C.
CC BY-SA 4.0
2019-12-23T13:45:10.337Z
My loss is pointwise, at each $x$; I updated the question.
Aryeh
CC BY-SA 4.0
2019-12-23T14:23:25.180Z
I see, thanks for the clarification!
Clement C.
CC BY-SA 4.0
2019-12-23T14:52:25.933Z
I'm really just looking for related keywords. So far "passive Lipschitz bandits" comes to mind -- anything else?
Aryeh
CC BY-SA 4.0
2019-12-23T21:35:05.767Z
To be clear, we are given the list of pairs $\{(X_i,Y_i)\}$?
Lior Silberman
CC BY-SA 4.0
2019-12-23T21:36:25.187Z
By the way, the triple $(X,\rho,\mu)$ is called a metric measure space.
Lior Silberman
CC BY-SA 4.0
2019-12-23T21:42:26.097Z
@LiorSilberman (1) yes, you get to observe $(X_i,Y_i)$ for $i=1,\ldots, n$. (2) yes, I know
Aryeh
CC BY-SA 4.0
2019-12-25T02:17:20.173Z
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] https://arxiv.org/abs/1802.09680
usul
CC BY-SA 4.0
2019-12-25T08:30:52.673Z
@usul Sure, would be happy to discuss this! I'd send you an email but your identity is non-obvious, so feel free to shoot me one. https://www.cs.bgu.ac.il/~karyeh/
Aryeh
<machine-learning><lg.learning><st.statistics><pac-learning>
Is this a known learning problem?
Aryeh
# Is this a known learning problem?

(Asked by: username_0 on 2019-12-23)

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

**Tags:** machine-learning, lg.learning, st.statistics, pac-learning
> **Comments:**
> **username_1**: 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]$?  
> **username_0**: My loss is pointwise, at each $x$; I updated the question.  
> **username_1**: I see, thanks for the clarification!  
> **username_0**: I'm really just looking for related keywords. So far "passive Lipschitz bandits" comes to mind -- anything else?  
> **username_2**: To be clear, we are given the list of pairs $\{(X_i,Y_i)\}$?  
> **username_2**: By the way, the triple $(X,\rho,\mu)$ is called a metric measure space.  
> **username_0**: @LiorSilberman (1) yes, you get to observe $(X_i,Y_i)$ for $i=1,\ldots, n$. (2) yes, I know  
> **username_3**: 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] https://arxiv.org/abs/1802.09680  
> **username_0**: @usul Sure, would be happy to discuss this! I'd send you an email but your identity is non-obvious, so feel free to shoot me one. https://www.cs.bgu.ac.il/~karyeh/  

---

## 1 answers

### Answer by username_0 on 2020-10-22. Score: 3 | Accepted answer

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


---

