Zobrazeno 1 - 10
of 394
pro vyhledávání: '"Kane, Daniel P."'
We characterize the power of constant-depth Boolean circuits in generating uniform symmetric distributions. Let $f\colon\{0,1\}^m\to\{0,1\}^n$ be a Boolean function where each output bit of $f$ depends only on $O(1)$ input bits. Assume the output dis
Externí odkaz:
http://arxiv.org/abs/2411.08183
Publikováno v:
"Testable Learning of General Halfspaces with Adversarial Label Noise." In The Thirty Seventh Annual Conference on Learning Theory, pp. 1308-1335. PMLR, 2024
We study the task of testable learning of general -- not necessarily homogeneous -- halfspaces with adversarial label noise with respect to the Gaussian distribution. In the testable learning framework, the goal is to develop a tester-learner such th
Externí odkaz:
http://arxiv.org/abs/2408.17165
The replicability crisis is a major issue across nearly all areas of empirical science, calling for the formal study of replicability in statistics. Motivated in this context, [Impagliazzo, Lei, Pitassi, and Sorrell STOC 2022] introduced the notion o
Externí odkaz:
http://arxiv.org/abs/2406.02628
We study the efficient learnability of low-degree polynomial threshold functions (PTFs) in the presence of a constant fraction of adversarial corruptions. Our main algorithmic result is a polynomial-time PAC learning algorithm for this concept class
Externí odkaz:
http://arxiv.org/abs/2404.00529
We study Gaussian sparse estimation tasks in Huber's contamination model with a focus on mean estimation, PCA, and linear regression. For each of these tasks, we give the first sample and computationally efficient robust estimators with optimal error
Externí odkaz:
http://arxiv.org/abs/2403.10416
We study the complexity of Non-Gaussian Component Analysis (NGCA) in the Statistical Query (SQ) model. Prior work developed a general methodology to prove SQ lower bounds for this task that have been applicable to a wide range of contexts. In particu
Externí odkaz:
http://arxiv.org/abs/2403.04744
We study the problem of estimating the mean of an identity covariance Gaussian in the truncated setting, in the regime when the truncation set comes from a low-complexity family $\mathcal{C}$ of sets. Specifically, for a fixed but unknown truncation
Externí odkaz:
http://arxiv.org/abs/2403.02300
Spurred by the influential work of Viola (Journal of Computing 2012), the past decade has witnessed an active line of research into the complexity of (approximately) sampling distributions, in contrast to the traditional focus on the complexity of co
Externí odkaz:
http://arxiv.org/abs/2402.14278
We study the power of query access for the task of agnostic learning under the Gaussian distribution. In the agnostic model, no assumptions are made on the labels and the goal is to compute a hypothesis that is competitive with the {\em best-fit} fun
Externí odkaz:
http://arxiv.org/abs/2312.16616
We study the clustering problem for mixtures of bounded covariance distributions, under a fine-grained separation assumption. Specifically, given samples from a $k$-component mixture distribution $D = \sum_{i =1}^k w_i P_i$, where each $w_i \ge \alph
Externí odkaz:
http://arxiv.org/abs/2312.11769