Audio note: this article contains 108 uses of latex notation, so the narration may be difficult to follow. There's a link to the original text in the episode description.

Imagine that you’re looking for buried treasure on a large desert island, worth a billion dollars. You don’t have a map, but a mysterious hermit offers you a box with a button to help find the treasure. Each time you press the button, it will tell you either “warmer” or “colder”. But there's a catch. With probability <span>_2^{-100},_</span> the box will tell you the truth about whether you’re closer than you were last time you pressed. But with the remaining probability of .9999999999999999999999999999992, the box will make a random guess between “warmer” and “colder”. Should you pay $1 for this box?

Keep this in mind as we discuss the closely related problem of parity learning.

In my experience [...]

---

Outline:

(02:23) What is the parity learning problem?

(05:57) This 'hidden guessing' game is about P vs. NP, isn't it?

(08:42) Polynomial-time non 'learning-algorithmic' solution

(11:23) Handwavy proof of non-learnability

(15:53) Alternative point of view: lack of incremental pathways

(17:08) Does this mean that neural nets are weak?

(19:05) Not weak, but also not optimal

(20:40) Acknowledgments

The original text contained 5 footnotes which were omitted from this narration.

---

First published:
January 3rd, 2025

Source:
https://www.lesswrong.com/posts/Mcrfi3DBJBzfoLctA/the-subset-parity-learning-problem-much-more-than-you-wanted

---

Narrated by TYPE III AUDIO.

“The subset parity learning problem: much more than you wanted to know” by Dmitry Vaintrob

LessWrong (30+ Karma)