12 citations · 21 across the 7 of their papers we have counts for
7 papers
SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions
Ilias Diakonikolas, Daniel Kane, Lisheng Ren +1
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…
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…
SQ Lower Bounds for Learning Single Neurons with Massart Noise
Ilias Diakonikolas, Daniel M. Kane, Lisheng Ren +1
We study the problem of PAC learning a single neuron in the presence of Massart noise. Specifically, for a known activation function , the learner is…
Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models
Ilias Diakonikolas, Daniel M. Kane, Yuxin Sun
We establish optimal Statistical Query (SQ) lower bounds for robustly learning certain families of discrete high-dimensional distributions. In particular, we show that no efficient…
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…
Contraction: a Unified Perspective of Correlation Decay and Zero-Freeness of 2-Spin Systems
Shuai Shao, Yuxin Sun
We study complex zeros of the partition function of 2-spin systems, viewed as a multivariate polynomial in terms of the edge interaction parameters and the uniform external field.…
What can be sampled locally?
Weiming Feng, Yuxin Sun, Yitong Yin
The local computation of Linial [FOCS'87] and Naor and Stockmeyer [STOC'93] concerns with the question of whether a locally definable distributed computing problem can be solved lo…