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; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1]
Online Linear Classification with Massart Noise
Authors: Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis
ICML 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the task of online learning in the presence of Massart noise. Specifically, instead of assuming that the online adversary chooses an arbitrary sequence of labels, we assume that the context x is selected adversarially but the label y presented to the learner disagrees with the groundtruth label of x with unknown probability at most η. We focus on the fundamental class of γ-margin linear classifiers and present the first computationally efficient algorithm that achieves mistake bound ηT + o(T). We point out that the mistake bound achieved by our algorithm is qualitatively tight for computationally efficient algorithms; this follows from the fact that, even in the offline setting, achieving 0-1 error better than η requires super-polynomial time under standard complexity assumptions. |
| Researcher Affiliation | Academia | 1Department of Computer Sciences, University of Wisconsin-Madison, Madison, USA 2Department of Computer Science, University of Texas-Austin, Austin, USA 3Department of Computer Science, University of Athens, Athens, Greece. Correspondence to: Vasilis Kontonis <EMAIL>, Nikos Zarifis <EMAIL>. |
| Pseudocode | Yes | Algorithm 1 Online Learning Massart Halfspaces Algorithm 2 Compute G(w; X, v, r, α), where w is the argument and X, v, r, α are parameters. Algorithm 3 Bandits with Monotone Rewards |
| Open Source Code | No | The paper does not contain any statement about releasing source code, nor does it provide any links to code repositories. |
| Open Datasets | No | The paper describes theoretical models and algorithms (e.g., Massart Noise, Monotone Reward Distributions, contextual bandits) but does not mention the use of any specific public or open datasets for empirical evaluation. It defines the 'context space' X and 'reward distributions' D within its theoretical framework. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments using specific datasets. Therefore, there is no mention of dataset splits such as training, validation, or test sets. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithm design and proofs; it does not describe any experimental setup or specific hardware used for computations. |
| Software Dependencies | No | The paper is theoretical and does not report experimental results, thus it does not list any specific software dependencies or their version numbers. |
| Experiment Setup | No | The paper is theoretical, presenting algorithms and their theoretical guarantees. It does not include an experimental setup section with details like hyperparameter values or training configurations. |