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