Statistical Query Hardness of Multiclass Linear Classification with Random Classification Noise
Authors: Ilias Diakonikolas, Mingchen Ma, Lisheng Ren, Christos Tzamos
ICML 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | As our main contribution, we show that the complexity of MLC with RCN becomes drastically different in the presence of three or more labels. Specifically, we prove super-polynomial Statistical Query (SQ) lower bounds for this problem. In more detail, even for three labels and constant separation, we give a super-polynomial lower bound on the complexity of any SQ algorithm achieving optimal error. |
| Researcher Affiliation | Academia | 1Department of Computer Sciences, University of Wisconsin-Madison, Madison, USA 2University of Athens and Archimedes AI, Athens, Greece. Correspondence to: Mingchen Ma <EMAIL>, Lisheng Ren <EMAIL>. |
| Pseudocode | No | The paper describes methods and proofs using mathematical notation but does not include any explicitly labeled pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not contain any explicit statements or links indicating that open-source code for the described methodology is provided. |
| Open Datasets | No | This paper is theoretical and focuses on proving complexity lower bounds. It does not conduct experiments on specific datasets, therefore no datasets are mentioned as publicly available. |
| Dataset Splits | No | This paper is theoretical and does not involve experimental evaluation on datasets, so there is no mention of dataset splits. |
| Hardware Specification | No | This paper is theoretical and does not involve running experiments; therefore, no hardware specifications are provided. |
| Software Dependencies | No | This paper is theoretical and does not involve implementation or execution of code for experiments, so no specific software dependencies or versions are listed. |
| Experiment Setup | No | This paper is theoretical and focuses on mathematical proofs and lower bounds rather than empirical experiments. Therefore, no experimental setup details like hyperparameters or training configurations are provided. |