SQ Lower Bounds for Learning Mixtures of Linear Classifiers
Authors: Ilias Diakonikolas, Daniel Kane, Yuxin Sun
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main result is a Statistical Query (SQ) lower bound suggesting that known algorithms for this problem are essentially best possible, even for the special case of uniform mixtures. In particular, we show that the complexity of any SQ algorithm for the problem is npoly(1/ ) log(r), where is a lower bound on the pairwise ℓ2-separation between the vℓ s. The key technical ingredient underlying our result is a new construction of spherical designs that may be of independent interest. |
| Researcher Affiliation | Academia | Ilias Diakonikolas University of Wisconsin-Madison ilias@cs.wisc.edu Daniel M. Kane University of California, San Diego dakane@cs.ucsd.edu Yuxin Sun University of Wisconsin-Madison yxsun@cs.wisc.edu |
| Pseudocode | No | The paper does not contain any pseudocode or clearly labeled algorithm blocks. |
| Open Source Code | No | The paper is theoretical, proving lower bounds and constructing mathematical objects. It does not describe an implemented method or provide any statements about releasing source code for its own methodology. |
| Open Datasets | No | The paper is theoretical and focuses on proving lower bounds. It does not conduct empirical experiments or use datasets, and therefore does not mention public dataset availability. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with dataset splits. It does not provide information about training/test/validation dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental setup or hardware used. |
| Software Dependencies | No | The paper is theoretical and does not describe any experimental setup or software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on mathematical proofs and lower bounds. It does not describe an experimental setup with hyperparameters or system-level training settings. |