Source author record

Caleb Koch

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Machine Learning

Catalog footprint

Research overview

2works

3topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

A Query-Optimal Algorithm for Finding Counterfactuals

We design an algorithm for finding counterfactuals with strong theoretical guarantees on its performance. For any monotone model $f : X^d \to \{0,1\}$ and instance $x^\star$ , our algorithm makes ${S(f)^{O(Δ_f(x^\star))}\cdot \log d}$ queries to $f$ and returns {an {\sl optimal}} counterfactual for $x^\star$ : a nearest instance $x'$ to $x^\star$ for which $f(x')\ne f(x^\star)$ . Here $S(f)$ is the sensitivity of $f$ , a discrete analogue of the Lipschitz constant, and $Δ_f(x^\star)$ is the distance from $x^\star$ to its nearest counterfactuals. The previous best known query complexity was $d^{\,O(Δ_f(x^\star))}$ , achievable by brute-force local search. We further prove a lower bound of $S(f)^{Ω(Δ_f(x^\star))} + Ω(\log d)$ on the query complexity of any algorithm, thereby showing that the guarantees of our algorithm are essentially optimal.

preprint2022arXiv

The Query Complexity of Certification

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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.