1
$\begingroup$

Let $\mathcal{H}$ be ahypothesis class, $h\in \mathcal{H}$ be a function a model that maps an input space $\mathcal{X}$ to $\{0,1\}$, and $\epsilon > 0$, let $\mathcal{D}$ denotes the distribution which generates elements of $\mathcal{X}$ Let $ B(h,\epsilon)$ denote the ball centered in $h$ of radius $\epsilon$.

We denote $\mathcal{A}_h(S_q) = \hat{h}$ a learning algorithm that takes as input the query $S_q$ and output a hypothesis $h \in \mathcal{H}$: $\mathcal{A}_h(S_q) = \hat{h}$.

Let $S_q = \{X_1, \dots, X_q \}$ (random vector), We sat that $S_q \in \mathcal{Agg} \Big( B(h,\epsilon)\Big)$ if:

$$\forall i \in \{1, \dots, q\}, \forall f_1,f_2 \in B(h,\epsilon): f_1(X_i) = f_2(X_i)$$

Now consider the event: $$\mathcal{G}_h = \{S: ||\mathcal{A}(S_q) - h|| < \epsilon \}$$

I'm interested in the following expectation:

$$\mathbb{E} \Big[\mathbb{1}_{\mathcal{G}_h}(S_q)|S_q \in \mathcal{Agg} \Big( B(h,\epsilon)\Big) \Big]$$

Is this a zero quantity?

I am not sure if my argument is correct, but since the mass is concentrated on a region where infinite elements agree with $h$, then the algorithm should output a candidate hypothesis inside the ball $B(h,\epsilon)$.

$\endgroup$
3
  • $\begingroup$ @IosifPinelis, re, it is defined to be the ball of radius $\epsilon$ centred at $h$. But, since I don't know what a hypothesis class is, I couldn't answer the follow-up question of, with respect to what metric? $\endgroup$
    – LSpice
    Commented Jan 7 at 19:01
  • $\begingroup$ (i) $B(h,\epsilon)$ is a ball in what space and w.r.t. what norm? (ii) What is $S$ in $\mathcal{G}_h = \{S: ||\mathcal{A}(S_q) - h|| < \epsilon \}$? (iii) What is the norm (?) $||\cdot||$ in the latter expression? $\endgroup$ Commented Jan 7 at 19:07
  • $\begingroup$ I'm considering the norm: $||f-g||_{\mathcal{L}_2} = \mathbb{E}[ \sqrt{f^2 - g^2}]$, which is also the norm for tha ball. $\endgroup$
    – rivana
    Commented Jan 7 at 19:13

0

Browse other questions tagged or ask your own question.