论文标题
通过本地重建正确学习单调功能
Properly learning monotone functions via local reconstruction
论文作者
论文摘要
我们给出了$ 2^{\ tilde {o}（\ sqrt {n}/ε）} $ - 适当地学习单调布尔值的时间算法，该算法在$ \ {0,1 \}^n $的均匀分布下。我们的算法对对抗性标签噪声非常强大，并且运行时间几乎与Bshouty和Tamon（JACM '96）的最新学习算法的运行时间与Blais等人的信息理论下限（Random '15）。在此工作之前，已知存在的运行时间小于$ 2^{ω（n）} $的适当学习算法存在。 我们适当的学习者的核心是\ emph {本地计算算法}，用于对poset上的二进制标签进行排序。我们的算法建立在分布式贪婪的图形算法上的大量作品上。具体而言，我们依靠Ghaffari（focs'22）的最新作品，该工作具有有效的算法，用于计算Rubinfeld等人和Alon等人的LCA模型中的最大匹配（ICS'11，Soda'12）。我们本地排序算法的应用不仅仅是在布尔数据集上学习的扩展：我们还为布尔函数提供了宽容的测试仪，而不是将$ε/3 $ close的功能与单调的函数区分开的一般posets，而不是$ε$ -FAR。 布尔立方体的先前耐受测试仪仅区分$ε/ω（\ sqrt {n}）$ - 关闭和$ε$ -FAR。
We give a $2^{\tilde{O}(\sqrt{n}/ε)}$-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^{Ω(n)}$ was known to exist. The core of our proper learner is a \emph{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'11, 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 $ε/3$-close to monotone from those that are $ε$-far. Previous tolerant testers for the Boolean cube only distinguished between $ε/Ω(\sqrt{n})$-close and $ε$-far.
