142 citations · 752 across the 110 of their papers we have counts for
9 papers · 2 filters
Realizable Learning is All You Need
Max Hopkins, Daniel M. Kane, Shachar Lovett +1
The equivalence of realizable and agnostic learnability is a fundamental phenomenon in learning theory. With variants ranging from classical settings like PAC learning and regressi…
Outlier-Robust Sparse Estimation via Non-Convex Optimization
Yu Cheng, Ilias Diakonikolas, Rong Ge +3
We explore the connection between outlier-robust high-dimensional statistics and non-convex optimization in the presence of sparsity constraints, with a focus on the fundamental ta…
Learning General Halfspaces with General Massart Noise under the Gaussian Distribution
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis +2
We study the problem of PAC learning halfspaces on with Massart noise under the Gaussian distribution. In the Massart model, an adversary is allowed to flip the labe…
Forster Decomposition and Learning Halfspaces with Noise
Ilias Diakonikolas, Daniel M. Kane, Christos Tzamos
A Forster transform is an operation that turns a distribution into one with good anti-concentration properties. While a Forster transform does not always exist, we show that any di…
Boosting in the Presence of Massart Noise
Ilias Diakonikolas, Russell Impagliazzo, Daniel Kane +3
We study the problem of boosting the accuracy of a weak learner in the (distribution-independent) PAC model with Massart noise. In the Massart noise model, the label of each exampl…
Agnostic Proper Learning of Halfspaces under Gaussian Marginals
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis +2
We study the problem of agnostically learning halfspaces under the Gaussian distribution. Our main result is the {\em first proper} learning algorithm for this problem whose sample…
Bounded Memory Active Learning through Enriched Queries
Max Hopkins, Daniel Kane, Shachar Lovett +1
The explosive growth of easily-accessible unlabeled data has lead to growing interest in active learning, a paradigm in which data-hungry learning algorithms adaptively select info…
The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals
Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas +1
We study the problem of agnostic learning under the Gaussian distribution. We develop a method for finding hard families of examples for a wide class of problems by using LP dualit…
Outlier-Robust Learning of Ising Models Under Dobrushin's Condition
Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart +1
We study the problem of learning Ising models satisfying Dobrushin's condition in the outlier-robust setting where a constant fraction of the samples are adversarially corrupted. O…