<p>How would I prove that if there is an efficient algorithm for PAC learning in the presence of classification noise by an algorithm that is given a noise rate upper bound <span class="math-container">$\eta_0$</span> (<span class="math-container">$1/2 &gt; \eta_0 \geq \eta \geq 0$</span>) and whose running time depends polynomially on <span class="math-container">$1/(1 - 2\eta_0)$</span>, then there is an an efficient algorithm that is given no information about the noise rate and whose running time depends polynomially on <span class="math-container">$1/(1 - 2\eta)$</span>.</p>

CC BY-SA 4.0
2023-05-05T10:50:54.360Z
Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking.
Community
CC BY-SA 4.0
2023-05-05T13:40:43.760Z
I disagree with the Bot. However, do you know that what you're asking to prove is true? Also, you still know $\eta < 1/2$, right?
mathworker21
CC BY-SA 4.0
2023-05-05T17:13:25.883Z
@mathworker21 - I saw this problem in the Kearns-Vazarani textbook, but I can't figure out how to solve it. It seems to be a looser bound and I'm not sure how the given assumption helps us prove the looser bound
aome
<machine-learning><lg.learning><pac-learning>
Proving existence of efficient PAC learning algorithm without noise info given poly-time algorithm with noise upper bound
aome
# Proving existence of efficient PAC learning algorithm without noise info given poly-time algorithm with noise upper bound

(Asked by: username_0 on 2023-05-05)

How would I prove that if there is an efficient algorithm for PAC learning in the presence of classification noise by an algorithm that is given a noise rate upper bound $\eta\_0$ ($1/2 > \eta\_0 \geq \eta \geq 0$) and whose running time depends polynomially on $1/(1 - 2\eta\_0)$, then there is an an efficient algorithm that is given no information about the noise rate and whose running time depends polynomially on $1/(1 - 2\eta)$.

**Tags:** machine-learning, lg.learning, pac-learning
> **Comments:**
> **username_1**: Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking.  
> **username_2**: I disagree with the Bot. However, do you know that what you're asking to prove is true? Also, you still know $\eta < 1/2$, right?  
> **username_0**: @mathworker21 - I saw this problem in the Kearns-Vazarani textbook, but I can't figure out how to solve it. It seems to be a looser bound and I'm not sure how the given assumption helps us prove the looser bound  

---

## 0 answers

