2022/01/19 by Guy Blanc, Blanc, Guy, Caleb Koch +5 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2201.07736
openalex publication_date 2022/01/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the problem of \sl certification: given queries to a function f : \0,1\n → \0,1\ with certificate complexity ≤ k and an input x^⋆, output a size-k certificate for f's value on x^⋆. 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(k8 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.