论文标题
认证的查询复杂性
The Query Complexity of Certification
论文作者
论文摘要
我们研究了{\ sl认证}的问题：对函数$ f的查询$ f：\ {0,1 \}^n \ to \ {0,1 \} $带证书复杂性$ \ le k $和输入$ x^\ star $，输出$ f $ f $ f $ f $ f $ f $ f $ x^$ x^\ x^star $ x^^star $ x^y size-k $证书。这抽象地将可解释的机器学习中的一个核心问题模拟，我们认为$ f $是我们寻求解释预测的黑盒模型。 对于单调函数，Angluin的经典本地搜索算法通过$ n $ Queries来完成此任务，我们显示的对于本地搜索算法是最佳的。我们的主要结果是一种新算法，用于用$ o（k^8 \ log n）$ Queries认证单调功能，该功能接近匹配$ω（k \ log n）$的信息理论下限。我们算法的设计和分析基于与单调函数中阈值现象的新连接。 当$ f $是非单调的时，我们进一步证明了指数级$ k $下限，而当$ f $是单调的，但该算法仅给出$ f $的随机示例。这些下限表明，对$ f $的结构和查询访问的假设都是对我们实现的$ k $的多项式依赖性所必需的。
We study the problem of {\sl certification}: given queries to a function $f : \{0,1\}^n \to \{0,1\}$ with certificate complexity $\le k$ and an input $x^\star$, output a size-$k$ certificate for $f$'s value on $x^\star$. This abstractly models a central problem in explainable machine learning, where we think of $f$ as a blackbox model that we seek to explain the predictions of. For monotone functions, a classic local search algorithm of Angluin accomplishes this task with $n$ queries, which we show is optimal for local search algorithms. Our main result is a new algorithm for certifying monotone functions with $O(k^8 \log n)$ queries, which comes close to matching the information-theoretic lower bound of $Ω(k \log n)$. The design and analysis of our algorithm are based on a new connection to threshold phenomena in monotone functions. We further prove exponential-in-$k$ lower bounds when $f$ is non-monotone, and when $f$ is monotone but the algorithm is only given random examples of $f$. These lower bounds show that assumptions on the structure of $f$ and query access to it are both necessary for the polynomial dependence on $k$ that we achieve.
