142 citations · 752 across the 110 of their papers we have counts for
133 papers
SQ Lower Bounds for Learning Mixtures of Linear Classifiers
Ilias Diakonikolas, Daniel M. Kane, Yuxin Sun
We study the problem of learning mixtures of linear classifiers under Gaussian covariates. Given sample access to a mixture of distributions on of the form $(\ma…
New Lower Bounds for Testing Monotonicity and Log Concavity of Distributions
Yuqian Cheng, Daniel M. Kane, Zhicheng Zheng
We develop a new technique for proving distribution testing lower bounds for properties defined by inequalities involving the bin probabilities of the distribution in question. Usi…
Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials
Ilias Diakonikolas, Daniel M. Kane
We study the problem of PAC learning a linear combination of ReLU activations under the standard Gaussian distribution on with respect to the square loss. Our ma…
Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise
Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane +2
We study the problem of learning general (i.e., not necessarily homogeneous) halfspaces with Random Classification Noise under the Gaussian distribution. We establish nearly-matchi…
Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise
Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane +2
We study the problem of PAC learning -margin halfspaces with Random Classification Noise. We establish an information-computation tradeoff suggesting an inherent gap between the…
SQ Lower Bounds for Learning Bounded Covariance GMMs
Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas +1
We study the complexity of learning mixtures of separated Gaussians with common unknown bounded covariance matrix. Specifically, we focus on learning Gaussian mixture models (GMMs)…