We study the task of agnostically learning halfspaces under the Gaussian distribution.
Specifically, given labeled examples $(\\mathbf {x}, y) $ from an unknown distribution on …

We study the problem of agnostic learning under the Gaussian distribution in the Statistical
Query (SQ) model. We develop a method for finding hard families of examples for a wide …

There are many important high dimensional function classes that have fast agnostic learning
algorithms when strong assumptions on the distribution of examples can be made, such as …

Statistical query (SQ) algorithms are algorithms that have access to an\em SQ oracle for the
input distribution $ D $ instead of iid samples from $ D $. Given a query function $ φ: X\to [-1 …

We study the problem of PAC learning halfspaces on ℝ d with Massart noise under the
Gaussian distribution. In the Massart model, an adversary is allowed to flip the label of each …

We consider the well-studied problem of learning intersections of halfspaces under the
Gaussian distribution in the challenging\emph {agnostic learning} model. Recent work of …

We give strengthened provable guarantees on the performance of widely employed and
empirically successful {\sl top-down decision tree learning heuristics}. While prior works …

We give a new lower bound on the query complexity of any non-adaptive algorithm for
testing whether an unknown Boolean function is a k-junta versus epsilon-far from every k …

This paper studies the statistical query (SQ) complexity of estimating d-dimensional
submanifolds in ℝ n. We propose a purely geometric algorithm called Manifold Propagation …

Abstract We establish optimal Statistical Query (SQ) lower bounds for robustly learning
certain families of discrete high-dimensional distributions. In particular, we show that no …