Author name cluster

Guy Blanc

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.

19 papers

2 author rows

STOC Conference 2025 Conference Paper

Adaptive and Oblivious Statistical Adversaries Are Equivalent

Guy Blanc
Gregory Valiant

We resolve a fundamental question about the ability to perform a statistical task, such as learning, when an adversary corrupts the sample. Such adversaries are specified by the types of corruption they can make and their level of knowledge about the sample. The latter distinguishes between sample-adaptive adversaries which know the contents of the sample when choosing the corruption, and sample-oblivious adversaries, which do not. We prove that for all types of corruptions, sample-adaptive and sample-oblivious adversaries are equivalent up to polynomial factors in the sample size. This resolves the main open question introduced by Blanc et al. (COLT, 2022) and further explored in Canonne et al. (FOCS, 2023). Specifically, consider any algorithm A that solves a statistical task even when a sample-oblivious adversary corrupts its input. We show that there is an algorithm A ′ that solves the same task when the corresponding sample-adaptive adversary corrupts its input. The construction of A ′ is simple and maintains the computational efficiency of A : It requests a polynomially larger sample than A uses and then runs A on a uniformly random subsample. One of our main technical tools is a new structural result relating two distributions defined on sunflowers which may be of independent interest.

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).

FOCS Conference 2025 Conference Paper

Instance-Optimal Uniformity Testing and Tracking

Guy Blanc
Clément L. Canonne
Erik Waingarten

In the uniformity testing task, an algorithm is provided with samples from an unknown probability distribution over a (known) finite domain, and must decide whether it is the uniform distribution, or, alternatively, if its total variation distance from uniform exceeds some input distance parameter. This question has received a significant amount of interest and its complexity is, by now, fully settled. Yet, we argue that it fails to capture many scenarios of interest, and that its very definition as a gap problem in terms of a prespecified distance may lead to suboptimal performance. To address these shortcomings, we introduce the problem of uniformity tracking, whereby an algorithm is required to detect deviations from uniformity (however they may manifest themselves) using as few samples as possible, and be competitive against an optimal algorithm knowing the distribution profile in hindsight. Our main contribution is a polylog(opt)-competitive uniformity tracking algorithm. We obtain this result by leveraging new structural results on Poisson mixtures, which we believe to be of independent interest.

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.

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.

NeurIPS Conference 2023 Conference Paper

Harnessing the power of choices in decision tree learning

Guy Blanc
Jane Lange
Chirag Pabbaraju
Colin Sullivan
Li-Yang Tan
Mo Tiwari

We propose a simple generalization of standard and empirically successful decision tree learning algorithms such as ID3, C4. 5, and CART. These algorithms, which have been central to machine learning for decades, are greedy in nature: they grow a decision tree by iteratively splitting on the best attribute. Our algorithm, Top-$k$, considers the $k$ best attributes as possible splits instead of just the single best attribute. We demonstrate, theoretically and empirically, the power of this simple generalization. We first prove a greediness hierarchy theorem showing that for every $k\in \mathbb{N}$, Top-$(k+1)$ can be dramatically more powerful than Top-$k$: there are data distributions for which the former achieves accuracy $1-\epsilon$, whereas the latter only achieves accuracy $\frac{1}{2}+\epsilon$. We then show, through extensive experiments, that Top-$k$ outperforms the two main approaches to decision tree learning: classic greedy algorithms and more recent ``optimal decision tree'' algorithms. On one hand, Top-$k$ consistently enjoys significant accuracy gains over greedy algorithms across a wide range of benchmarks. On the other hand, Top-$k$ is markedly more scalable than optimal decision tree algorithms and is able to handle dataset and feature set sizes that remain far beyond the reach of these algorithms. The code to reproduce our results is available at https: //github. com/SullivanC19/pydl8. 5-topk.

STOC Conference 2023 Conference Paper

Lifting Uniform Learners via Distributional Decomposition

Guy Blanc
Jane Lange
Ali Malik
Li-Yang Tan

We show how any PAC learning algorithm that works under the uniform distribution can be transformed, in a blackbox fashion, into one that works under an arbitrary and unknown distribution ‍ D . The efficiency of our transformation scales with the inherent complexity of ‍ D , running in ( n , ( md ) d ) time for distributions over n whose pmfs are computed by depth- d decision trees, where m is the sample complexity of the original algorithm. For monotone distributions our transformation uses only samples from ‍ D , and for general ones it uses subcube conditioning samples. A key technical ingredient is an algorithm which, given the aforementioned access to D , produces an optimal decision tree decomposition of D : an approximation of D as a mixture of uniform distributions over disjoint subcubes. With this decomposition in hand, we run the uniform-distribution learner on each subcube and combine the hypotheses using the decision tree. This algorithmic decomposition lemma also yields new algorithms for learning decision tree distributions with runtimes that exponentially improve on the prior state of the art—results of independent interest in distribution learning.

STOC Conference 2023 Conference Paper

Subsampling Suffices for Adaptive Data Analysis

Guy Blanc

Ensuring that analyses performed on a dataset are representative of the entire population is one of the central problems in statistics. Most classical techniques assume that the dataset is independent of the analyst’s query and break down in the common setting where a dataset is reused for multiple, adaptively chosen, queries. This problem of adaptive data analysis was formalized in the seminal works of Dwork et al. (STOC, 2015) and Hardt and Ullman (FOCS, 2014). We identify a remarkably simple set of assumptions under which the queries will continue to be representative even when chosen adaptively: The only requirements are that each query takes as input a random subsample and outputs few bits. This result shows that the noise inherent in subsampling is sufficient to guarantee that query responses generalize. The simplicity of this subsampling-based framework allows it to model a variety of real-world scenarios not covered by prior work. In addition to its simplicity, we demonstrate the utility of this framework by designing mechanisms for two foundational tasks, statistical queries and median finding. In particular, our mechanism for answering the broadly applicable class of statistical queries is both extremely simple and state of the art in many parameter regimes.

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.

ICML Conference 2022 Conference Paper

Popular decision tree algorithms are provably noise tolerant

Guy Blanc
Jane Lange
Ali Malik
Li-Yang Tan

Using the framework of boosting, we prove that all impurity-based decision tree learning algorithms, including the classic ID3, C4. 5, and CART, are highly noise tolerant. Our guarantees hold under the strongest noise model of nasty noise, and we provide near-matching upper and lower bounds on the allowable noise rate. We further show that these algorithms, which are simple and have long been central to everyday machine learning, enjoy provable guarantees in the noisy setting that are unmatched by existing algorithms in the theoretical literature on decision tree learning. Taken together, our results add to an ongoing line of research that seeks to place the empirical success of these practical decision tree algorithms on firm theoretical footing.

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.

FOCS Conference 2021 Conference Paper

Multiway Online Correlated Selection

Guy Blanc
Moses Charikar

We give a 0. 5368-competitive algorithm for edge-weighted online bipartite matching. Prior to our work, the best competitive ratio was 0. 5086 due to Fahrbach, Huang, Tao, and Zadimoghaddam (FOCS 2020). They achieved their breakthrough result by developing a subroutine called online correlated selection (OCS) which takes as input a sequence of pairs and selects one item from each pair. Importantly, the selections the OCS makes are negatively correlated. We achieve our result by defining multiway OCSes which receive arbitrarily many elements at each step, rather than just two. In addition to better competitive ratios, our formulation allows for a simpler reduction from edge-weighted online bipartite matching to OCSes. While Fahrbach et al. used a factor-revealing linear program to optimize the competitive ratio, our analysis directly connects the competitive ratio to the parameters of the multiway OCS. Finally, we show that the formulation of Farhbach et al. can achieve a competitive ratio of at most 0. 5239, confirming that multiway OCSes are strictly more powerful.

FOCS Conference 2021 Conference Paper

Properly learning decision trees in almost polynomial time

Guy Blanc
Jane Lange
Mingda Qiao
Li-Yang Tan

We give an $n^{O(\log\log n)}$ -time membership query algorithm for properly and agnostically learning decision trees under the uniform distribution over $\{\pm 1\}^{n}$. Even in the realizable setting, the previous fastest runtime was $n^{O(\log n)}$, a consequence of a classic algorithm of Ehrenfeucht and Haussler. Our algorithm shares similarities with practical heuristics for learning decision trees, which we augment with additional ideas to circumvent known lower bounds against these heuristics. To analyze our algorithm, we prove a new structural result for decision trees that strengthens a theorem of O'Donnell, Saks, Schramm, and Servedio. While the OSSS theorem says that every decision tree has an influential variable, we show how every decision tree can be “pruned” so that every variable in the resulting tree is influential.

NeurIPS Conference 2021 Conference Paper

Provably efficient, succinct, and precise explanations

Guy Blanc
Jane Lange
Li-Yang Tan

We consider the problem of explaining the predictions of an arbitrary blackbox model $f$: given query access to $f$ and an instance $x$, output a small set of $x$'s features that in conjunction essentially determines $f(x)$. We design an efficient algorithm with provable guarantees on the succinctness and precision of the explanations that it returns. Prior algorithms were either efficient but lacked such guarantees, or achieved such guarantees but were inefficient. We obtain our algorithm via a connection to the problem of {\sl implicitly} learning decision trees. The implicit nature of this learning task allows for efficient algorithms even when the complexity of~$f$ necessitates an intractably large surrogate decision tree. We solve the implicit learning problem by bringing together techniques from learning theory, local computation algorithms, and complexity theory. Our approach of “explaining by implicit learning” shares elements of two previously disparate methods for post-hoc explanations, global and local explanations, and we make the case that it enjoys advantages of both.

SODA Conference 2021 Conference Paper

Query strategies for priced information, revisited

Guy Blanc
Jane Lange
Li-Yang Tan

We consider the problem of designing query strategies for priced information, introduced by Charikar et al. In this problem the algorithm designer is given a function f: {0, 1} n → {±1} and a price associated with each of the n coordinates. The goal is to design a query strategy for determining f 's value on unknown inputs for minimum cost. Prior works on this problem have focused on specific classes of functions. We analyze a simple and natural strategy that applies to all functions f, and show that its performance relative to the optimal strategy can be expressed in terms of a basic complexity measure of f, its influence. For ∊ ∊ (0, ½), writing opt to denote the expected cost of the optimal strategy that errs on at most an ∊ -fraction of inputs, our strategy has expected cost opt · Inf( f )/ ∊ 2 and also errs on at most an O(∊) -fraction of inputs. This connection yields new guarantees that complement existing ones for a number of function classes that have been studied in this context, as well as new guarantees for new classes. Finally, we show that improving on the parameters that we achieve will require making progress on the longstanding open problem of properly learning decision trees.

NeurIPS Conference 2020 Conference Paper

Estimating decision tree learnability with polylogarithmic sample complexity

Guy Blanc
Neha Gupta
Jane Lange
Li-Yang Tan

We show that top-down decision tree learning heuristics (such as ID3, C4. 5, and CART) are amenable to highly efficient {\sl learnability estimation}: for monotone target functions, the error of the decision tree hypothesis constructed by these heuristics can be estimated with {\sl polylogarithmically} many labeled examples, exponentially smaller than the number necessary to run these heuristics, and indeed, exponentially smaller than information-theoretic minimum required to learn a good decision tree. This adds to a small but growing list of fundamental learning algorithms that have been shown to be amenable to learnability estimation. En route to this result, we design and analyze sample-efficient {\sl minibatch} versions of top-down decision tree learning heuristics and show that they achieve the same provable guarantees as the full-batch versions. We further give ``active local'' versions of these heuristics: given a test point $x^\star$, we show how the label $T(x^\star)$ of the decision tree hypothesis $T$ can be computed with polylogarithmically many labeled examples, exponentially smaller than the number necessary to learn~$T$.

ICML Conference 2020 Conference Paper

Provable guarantees for decision tree induction: the agnostic setting

Guy Blanc
Jane Lange
Li-Yang Tan

We give strengthened provable guarantees on the performance of widely employed and empirically successful {\sl top-down decision tree learning heuristics}. While prior works have focused on the realizable setting, we consider the more realistic and challenging {\sl agnostic} setting. We show that for all monotone functions $f$ and $s\in \mathbb{N}$, these heuristics construct a decision tree of size $s^{\tilde{O}((\log s)/\varepsilon^2)}$ that achieves error $\le \mathsf{opt}_s + \varepsilon$, where $\mathsf{opt}_s$ denotes the error of the optimal size-$s$ decision tree for $f$. Previously such a guarantee was not known to be achievable by any algorithm, even one that is not based on top-down heuristics. We complement our algorithmic guarantee with a near-matching $s^{\tilde{\Omega}(\log s)}$ lower bound.

NeurIPS Conference 2020 Conference Paper

Universal guarantees for decision tree induction via a higher-order splitting criterion

Guy Blanc
Neha Gupta
Jane Lange
Li-Yang Tan

We propose a simple extension of {\sl top-down decision tree learning heuristics} such as ID3, C4. 5, and CART. Our algorithm achieves provable guarantees for all target functions $f: \{-1, 1\}^n \to \{-1, 1\}$ with respect to the uniform distribution, circumventing impossibility results showing that existing heuristics fare poorly even for simple target functions. The crux of our extension is a new splitting criterion that takes into account the correlations between $f$ and {\sl small subsets} of its attributes. The splitting criteria of existing heuristics (e. g. Gini impurity and information gain), in contrast, are based solely on the correlations between $f$ and its {\sl individual} attributes. Our algorithm satisfies the following guarantee: for all target functions $f: \{-1, 1\}^n \to \{-1, 1\}$, sizes $s\in \N$, and error parameters $\eps$, it constructs a decision tree of size $s^{\tilde{O}((\log s)^2/\eps^2)}$ that achieves error $\le O(\opt_s) + \eps$, where $\opt_s$ denotes the error of the optimal size-$s$ decision tree for $f$. A key technical notion that drives our analysis is the {\sl noise stability} of $f$, a well-studied smoothness measure of $f$.

ICML Conference 2018 Conference Paper

Adaptive Sampled Softmax with Kernel Based Sampling

Guy Blanc
Steffen Rendle

Softmax is the most commonly used output function for multiclass problems and is widely used in areas such as vision, natural language processing, and recommendation. A softmax model has linear costs in the number of classes which makes it too expensive for many real-world problems. A common approach to speed up training involves sampling only some of the classes at each training step. It is known that this method is biased and that the bias increases the more the sampling distribution deviates from the output distribution. Nevertheless, almost all recent work uses simple sampling distributions that require a large sample size to mitigate the bias. In this work, we propose a new class of kernel based sampling methods and develop an efficient sampling algorithm. Kernel based sampling adapts to the model as it is trained, thus resulting in low bias. It can also be easily applied to many models because it relies only on the model’s last hidden layer. We empirically study the trade-off of bias, sampling distribution and sample size and show that kernel based sampling results in low bias with few samples.