Beyond the low-degree algorithm: mixtures of subcubes and their applications

© 2019 Association for Computing Machinery. We introduce the problem of learning mixtures of k subcubes over (0,1)n, which contains many classic learning theory problems as a special case (and is itself a special case of others). We give a surprising nO(log k)-time learning algorithm based on higher...

Full description

Bibliographic Details
Main Authors: Chen, Sitan, Moitra, Ankur
Format: Article
Language:English
Published: ACM 2021
Online Access:https://hdl.handle.net/1721.1/138050