## A problem about the relation between 1-oracle and 2-oracle PAC model

2

This problem is about two-oracle variant of the PAC model. Assume that positive and negative examples are now drawn from two separate distributions $$\mathcal{D}_{+}$$ and $$\mathcal{D}_{-} .$$ For an accuracy $$(1-\epsilon),$$ the learning algorithm must find a hypothesis $$h$$ such that: $$\underset{x \sim \mathcal{D}_{+}}{\mathbb{P}}[h(x)=0] \leq \epsilon \text { and } \underset{x \sim \mathcal{D}_{-}}{\mathbb{P}}[h(x)=1] \leq \epsilon$$

Thus, the hypothesis must have a small error on both distributions. Let $$\mathcal{C}$$ be any concept class and $$\mathcal{H}$$ be any hypothesis space. Let $$h_{0}$$ and $$h_{1}$$ represent the identically 0 and identically 1 functions, respectively. Prove that $$\mathcal{C}$$ is efficiently PAC-learnable using $$\mathcal{H}$$ in the standard (one-oracle) PAC model if and only if it is efficiently PAC-learnable using $$\mathcal{H} \cup\left\{h_{0}, h_{1}\right\}$$ in this two-oracle PAC model.

However, I wonder if the problem is correct. In the official solution, when showing that 2-oracle implies 1-oracle, the author returns $$h_0$$ and $$h_1$$ when the distribution is too biased towards positive or negative examples. However, in the problem, it is required that only in 2-oracle case we can return $$h_0$$ and $$h_1$$. Therefore, in this too-biased case, it seems that there may not exist a 'good' hypothesis at all.

Is this problem wrong? Or I make some mistake somewhere?

Can we decompose probabilities like done in the 'so called' proof? From $D$ to $D^+$ and $D^-$. – DuttaA – 2020-03-17T22:48:33.367
{"ft_lang_label":"__label__en","ft_lang_prob":0.8265397,"math_prob":0.9998335,"size":1536,"snap":"2021-43-2021-49","text_gpt3_token_len":446,"char_repetition_ratio":0.12663186,"word_repetition_ratio":0.0,"special_character_ratio":0.29622397,"punctuation_ratio":0.098305084,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9999958,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-10-25T01:55:33Z\",\"WARC-Record-ID\":\"<urn:uuid:aeb0f7f5-a6ec-45b0-b7cd-089c6af0555d>\",\"Content-Length\":\"8011\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:b28a230b-ee0c-4216-96a8-6a722686ebbf>\",\"WARC-Concurrent-To\":\"<urn:uuid:20db9f3a-7d6c-4e78-8b4b-b2c498923838>\",\"WARC-IP-Address\":\"195.154.156.115\",\"WARC-Target-URI\":\"https://library.kiwix.org/ai.stackexchange.com_en_all_2020-10/A/question/17537.html\",\"WARC-Payload-Digest\":\"sha1:MULSL6TSKZWBOSTNVJPOYI2AXVYFJTJZ\",\"WARC-Block-Digest\":\"sha1:I4BM5VQPMUJTEE5LDPLRWP46VLYYFRYE\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-43/CC-MAIN-2021-43_segments_1634323587608.86_warc_CC-MAIN-20211024235512-20211025025512-00337.warc.gz\"}"}