Zobrazeno 1 - 10
of 61
pro vyhledávání: '"BLANC, GUY"'
Autor:
Blanc, Guy, Valiant, Gregory
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
Externí odkaz:
http://arxiv.org/abs/2410.13548
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
Externí odkaz:
http://arxiv.org/abs/2409.11597
Consider the expected query complexity of computing the $k$-fold direct product $f^{\otimes k}$ of a function $f$ to error $\varepsilon$ with respect to a distribution $\mu^k$. One strategy is to sequentially compute each of the $k$ copies to error $
Externí odkaz:
http://arxiv.org/abs/2405.16340
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 deci
Externí odkaz:
http://arxiv.org/abs/2310.01551
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$ s
Externí odkaz:
http://arxiv.org/abs/2307.04039
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 $\mathcal{D}$. The efficiency of our transformation scales wit
Externí odkaz:
http://arxiv.org/abs/2303.16208
Autor:
Blanc, Guy
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 comm
Externí odkaz:
http://arxiv.org/abs/2302.08661
In the certification problem, the algorithm is given a function $f$ with certificate complexity $k$ and an input $x^\star$, and the goal is to find a certificate of size $\le \text{poly}(k)$ for $f$'s value at $x^\star$. This problem is in $\mathsf{N
Externí odkaz:
http://arxiv.org/abs/2211.02257
We investigate the computational efficiency of multitask learning of Boolean functions over the $d$-dimensional hypercube, that are related by means of a feature representation of size $k \ll d$ shared across all tasks. We present a polynomial time m
Externí odkaz:
http://arxiv.org/abs/2209.03112
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
Externí odkaz:
http://arxiv.org/abs/2207.07072