Author name cluster

Carmen Strassle

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.

5 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 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