Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Multiclass Learnability and the ERM Principle
Authors: Amit Daniely, Sivan Sabato, Shai Ben-David, Shai Shalev-Shwartz
JMLR 2015 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the sample complexity of multiclass prediction in several learning settings. For the PAC setting our analysis reveals a surprising phenomenon: In sharp contrast to binary classification, we show that there exist multiclass hypothesis classes for which some Empirical Risk Minimizers (ERM learners) have lower sample complexity than others. Furthermore, there are classes that are learnable by some ERM learners, while other ERM learners will fail to learn them. We propose a principle for designing good ERM learners, and use this principle to prove tight bounds on the sample complexity of learning symmetric multiclass hypothesis classes classes that are invariant under permutations of label names. We further provide a characterization of mistake and regret bounds for multiclass learning in the online setting and the bandit setting, using new generalizations of Littlestone s dimension. |
| Researcher Affiliation | Collaboration | Amit Daniely EMAIL Dept. of Mathematics, The Hebrew University, Givat-Ram Campus, Jerusalem 91904, Israel Sivan Sabato EMAIL Dept. of Computer Science, Ben-Gurion University of the Negev, Beer Sheva 8410501, Israel Shai Ben-David EMAIL David R. Cheriton School of Computer Science, University of Waterloo, 200 University Avenue West, Waterloo, Ontario, Canada, N2L 3G1 Shai Shalev-Shwartz EMAIL School of Computer Science and Engineering, The Hebrew University, Givat-Ram Campus, Jerusalem 91904, Israel |
| Pseudocode | Yes | Algorithm: Standard Optimal Algorithm (SOA) Algorithm: Learning with Expert Advice (LEA) Algorithm: Bandit Standard Optimal Algorithm (BSOA) |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code or links to code repositories. |
| Open Datasets | No | The paper is theoretical and does not describe experiments that use specific datasets. While it mentions common practical examples like 'document categorization, object recognition in computer vision, and web advertisement', these are general domains and not specific datasets used in the research. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments using datasets, thus there is no information about dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental setup or hardware used for computation. |
| Software Dependencies | No | The paper is theoretical and does not describe any software or libraries with specific version numbers used for experiments. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup, hyperparameters, or training configurations. |