Properly learning monotone functions via local correction

We give a $2^{\tilde{O}(\sqrt{n}/\varepsilon)}$-time algorithm for properly learning monotone Boolean functions under the uniform distribution over $\{0, 1\}^{n}$. Our algorithm is robust to adversarial label noise and has a running time nearly matching that of the state-of-the-art improper learning algorithm of Bshouty and Tamon (JACM 96) and an information-theoretic lower bound of Blais et al (RANDOM ’15). Prior to this work, no proper learning algorithm with running time smaller than $2^{\Omega(n)}$ was known to exist. The core of our proper learner is a local computation algorithm for sorting binary labels on a poset. Our algorithm is built on a body of work on distributed greedy graph algorithms; specifically we rely on a recent work of Ghaffari (FOCS’22), which gives an efficient algorithm for computing maximal matchings in a graph in the LCA model of Rubinfeld et al and Alon et al (ICS’II, SODA’12). The applications of our local sorting algorithm extend beyond learning on the Boolean cube: we also give a tolerant tester for Boolean functions over general posets that distinguishes functions that are $\varepsilon$/3-close to monotone from those that are $\varepsilon-$far. Previous tolerant testers for the Boolean cube only distinguished between $\varepsilon/\Omega(\sqrt{n}$)-close and $\varepsilon-$far.

Authors

• Jane Lange
• Ronitt Rubinfeld
• Arsen Vasilyan

Keywords

• Computer science
• Boolean functions
• Computational modeling
• Sorting
• Information theory
• Learning Algorithms
• Running Time
• Generation Algorithm
• Local Algorithm
• Maximum Matching
• Sorting Algorithm
• Boolean Function
• Label Noise
• Proper Learning
• Correction Algorithm
• Global View
• Generalization Error
• Partial Order
• Global Algorithm
• Memoryless
• Local Implementation
• Naive Approach
• Fraction Of Elements
• Standard Reduction
• Maximum Independent Set
• Random Bits
• property testing
• local reconstruction
• monotone functions
• local computation algorithms