Author name cluster

Caleb Koch 0001

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers

1 author row

FOCS Conference 2025 Conference Paper

Computational-Statistical Tradeoffs from NP-hardness

Guy Blanc
Caleb Koch 0001
Carmen Strassle
Li-Yang Tan

A central question in computer science and statistics is whether efficient algorithms can achieve the information-theoretic limits of statistical problems. Many computational-statistical tradeoffs have been shown under average-case assumptions, but since statistical problems are average-case in nature, it has been a challenge to base them on standard worst-case assumptions. In PAC learning where such tradeoffs were first studied, the question is whether computational efficiency can come at the cost of using more samples than informationtheoretically necessary. We base such tradeoffs on NP-hardness and obtain: ◦ Sharp computational-statistical tradeoffs assuming NP requires exponential time: For every polynomial $p(n)$, there is an n-variate class $\mathcal{C}$ with VC dimension 1 such that the sample complexity of time-efficiently learning $\mathcal{C}$ is $\Theta(p(n))$. ◦ A characterization of RP vs. NP in terms of learning: RP = NP iff every NP-enumerable class is learnable with $O(\operatorname{VCdim}(\mathcal{C}))$ samples in polynomial time. The forward implication has been known since (Pitt and Valiant, 1988); we prove the reverse implication. Notably, all our lower bounds hold against improper learners. These are the first NP-hardness results for improperly learning a subclass of polynomial-size circuits, circumventing formal barriers of Applebaum, Barak, and Xiao (2008).

Details

FOCS Conference 2024 Conference Paper

Fast Decision Tree Learning Solves Hard Coding-Theoretic Problems

Caleb Koch 0001
Carmen Strassle
Li-Yang Tan

We connect the problem of properly PAC learning decision trees to the parameterized Nearest Codeword Problem (k-NCP). Despite significant effort by the respective communities, algorithmic progress on both problems has been stuck: the fastest known algorithm for the former runs in quasipolynomial time (Ehrenfeucht and Haussler 1989) and the best known approximation ratio for the latter is $O$ ( $n$ /log n ) (Berman and Karpinsky 2002; Alon, Panigrahy, and Yekhanin 2009). Research on both problems has thus far proceeded independently with no known connections. We show that any improvement of Ehrenfeucht and Haussler's algorithm will yield $O$ (logn)-approximation algorithms for k-NCP, an exponential improvement of the current state of the art. This can be interpreted either as a new avenue for designing algorithms for k-NCP, or as one for establishing the optimality of Ehrenfeucht and Haussler's algorithm. Furthermore, our reduction along with existing inapproximability results for k - NCP already rule out polynomial-time algorithms for properly learning decision trees. A notable aspect of our hardness results is that they hold even in the setting of weak learning whereas prior ones were limited to the setting of strong learning.

Details

FOCS Conference 2024 Conference Paper

The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem

Guy Blanc
Alexandre Hayderi
Caleb Koch 0001
Li-Yang Tan

Smooth boosters generate distributions that do not place too much weight on any given example. Originally introduced for their noise-tolerant properties, such boosters have also found applications in differential privacy, reproducibility, and quantum learning theory. We study and settle the sample complexity of smooth boosting: we exhibit a class that can be weak learned to $\gamma$. -advantage over smooth distributions with $m$ samples, for which strong learning over the uniform distribution requires $\tilde{\Omega}(1/\gamma^{2}{)}\cdot m$, samples. This matches the overhead of existing smooth boosters and provides the first separation from the setting of distribution-independent boosting, for which the corresponding overhead is $O(1/\gamma)$. Our work also sheds new light on Impagliazzo's hardcore theorem from complexity theory, all known proofs of which can be cast in the framework of smooth boosting. For a function $f$ that is mildly hard against size-s circuits, the hardcore theorem provides a set of inputs on which $f$ is extremely hard against size- $s^{\prime}$ circuits. A downside of this important result is the loss in circuit size, i. e. that $s^{\prime}\ll s$. Answering a question of Trevisan, we show that this size loss is necessary and in fact, the parameters achieved by known proofs are the best possible.

Details

FOCS Conference 2023 Conference Paper

A strong composition theorem for junta complexity and the boosting of property testers

Guy Blanc
Caleb Koch 0001
Carmen Strassle
Li-Yang Tan

We prove a strong composition theorem for junta complexity and show how such theorems can be used to generically boost the performance of property testers. The $\varepsilon$-approximate junta complexity of a function f is the smallest integer r such that f is $\varepsilon$-close to a function that depends only on r variables. A strong composition theorem states that if f has large $\varepsilon$-approximate junta complexity, then $g \circ f$ has even larger $\varepsilon^{\prime}$-approximate junta complexity, even for $\varepsilon^{\prime} \gg \varepsilon$. We develop a fairly complete understanding of this behavior, proving that the junta complexity of $g \circ f$ is characterized by that of f along with the multivariate noise sensitivity of g. For the important case of symmetric functions g, we relate their multivariate noise sensitivity to the simpler and well-studied case of univariate noise sensitivity. We then show how strong composition theorems yield boosting algorithms for property testers: with a strong composition theorem for any class of functions, a large-distance tester for that class is immediately upgraded into one for small distances. Combining our contributions yields a booster for junta testers, and with it new implications for junta testing. This is the first boosting-type result in property testing, and we hope that the connection to composition theorems adds compelling motivation to the study of both topics.

Details

FOCS Conference 2023 Conference Paper

Properly learning decision trees with queries is NP-hard

Caleb Koch 0001
Carmen Strassle
Li-Yang Tan

We prove that it is NP-hard to properly PAC learn decision trees with queries, resolving a longstanding open problem in learning theory (Bshouty 1993; Guijarro–Lavín–Raghavan 1999; Mehta–Raghavan 2002; Feldman 2016). While there has been a long line of work, dating back to (Pitt–Valiant 1988), establishing the hardness of properly learning decision trees from random examples, the more challenging setting of query learners necessitates different techniques and there were no previous lower bounds. En route to our main result, we simplify and strengthen the best known lower bounds for a different problem of Decision Tree Minimization (Zantema—Bodlaender 2000; Sieling 2003). On a technical level, we introduce the notion of hardness distillation, which we study for decision tree complexity but can be considered for any complexity measure: for a function that requires large decision trees, we give a general method for identifying a small set of inputs that is responsible for its complexity. Our technique even rules out query learners that are allowed constant error. This contrasts with existing lower bounds for the setting of random examples which only hold for inverse-polynomial error. Our result, taken together with a recent almost-polynomial time query algorithm for properly learning decision trees under the uniform distribution (Blanc–Lange–Qiao–Tan 2022), demonstrates the dramatic impact of distributional assumptions on the problem.

Details

SODA Conference 2023 Conference Paper

Superpolynomial lower bounds for decision tree learning and testing

Caleb Koch 0001
Carmen Strassle
Li-Yang Tan

We establish new hardness results for decision tree optimization problems, adding to a line of work that dates back to Hyafil and Rivest in 1976. We prove, under the randomized exponential time hypothesis, superpolynomial runtime lower bounds for two basic problems: given an explicit representation of a function f and a generator for a distribution D ○ construct a small decision tree approximator for f under D, and ○ decide if there is a small decision tree approximator for f under D. Our results imply new lower bounds for distribution-free PAC learning and testing of decision trees, settings in which the algorithm only has restricted access to f and D. Specifically, we get that: ○ n -variable size- s decision trees cannot be properly PAC learned in time n Õ(log log s), and ○ depth- d decision trees cannot be tested in time exp( d O(1) ). For learning, the previous best lower bound only ruled out poly( n )-time algorithms (Alekhnovich, Braverman, Feldman, Klivans, and Pitassi, 2009). For testing, recent work gives similar though incomparable lower bounds in the setting where f is random and D is nonexplicit (Blais, Ferreira Pinto Jr. , and Harms, 2021). Assuming a plausible conjecture on the hardness of SET-COVER, we show that our lower bound for properly PAC learning decision trees can be improved to n Ω(log s ), matching the best known upper bound of n O(log s ) due to Ehrenfeucht and Haussler (1989). We obtain our results within a unified framework that leverages recent progress in two different lines of work: the inapproximability of SET-COVER and XOR lemmas for query complexity. Our framework is versatile and yields results for related concept classes such as juntas and DNF formulas. ∗ The full version of the paper can be accessed at https: //arxiv. org/abs/2210. 06375

Details

ICML Conference 2022 Conference Paper

A query-optimal algorithm for finding counterfactuals

Guy Blanc
Caleb Koch 0001
Jane Lange
Li-Yang Tan

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(\Delta_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 $\Delta_f(x^\star)$ is the distance from $x^\star$ to its nearest counterfactuals. The previous best known query complexity was $d^{\, O(\Delta_f(x^\star))}$, achievable by brute-force local search. We further prove a lower bound of $S(f)^{\Omega(\Delta_f(x^\star))} + \Omega(\log d)$ on the query complexity of any algorithm, thereby showing that the guarantees of our algorithm are essentially optimal.

Details

STOC Conference 2022 Conference Paper

The query complexity of certification

Guy Blanc
Caleb Koch 0001
Jane Lange
Li-Yang Tan

We study the problem of 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 ⋆ . 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.

Details