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].
Online Learning with Primary and Secondary Losses
Authors: Avrim Blum, Han Shao
NeurIPS 2020 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the problem of online learning with primary and secondary losses. For example, a recruiter making decisions of which job applicants to hire might weigh false positives and false negatives equally (the primary loss) but the applicants might weigh false negatives much higher (the secondary loss). We consider the following question: Can we combine expert advice to achieve low regret with respect to the primary loss, while at the same time performing not much worse than the worst expert with respect to the secondary loss? Unfortunately, we show that this goal is unachievable without any bounded variance assumption on the secondary loss. More generally, we consider the goal of minimizing the regret with respect to the primary loss and bounding the secondary loss by a linear threshold. On the positive side, we show that running any switching-limited algorithm can achieve this goal if all experts satisfy the assumption that the secondary loss does not exceed the linear threshold by o(T) for any time interval. If not all experts satisfy this assumption, our algorithms can achieve this goal given access to some external oracles which determine when to deactivate and reactivate experts. |
| Researcher Affiliation | Academia | Avrim Blum Toyota Technological Institute at Chicago EMAIL Han Shao Toyota Technological Institute at Chicago EMAIL |
| Pseudocode | Yes | Algorithm 1 A1 1: Input: T, H, and a learner L 2: Initialize f(h) = h for all h 2 H. 3: Start an instance ASL(L). 4: for t = 1, . . . , T do 5: Get expert ht from ASL(L). 6: Select expert f(ht). 7: Feed e (1) t to ASL(L). 8: For all h with f(h) 2 Ht, set f(h) = h0, where h0 is any expert in Ht+1. 9: end for |
| Open Source Code | No | The paper does not provide any information about open-source code availability or links to code repositories. |
| Open Datasets | No | The paper is theoretical and uses a 'binary classification example' for theoretical proofs, not a real-world dataset. There is no mention of a publicly available dataset or access information. |
| Dataset Splits | No | The paper does not describe experiments with real datasets, therefore, there is no mention of training, validation, or test splits. |
| Hardware Specification | No | The paper describes theoretical models and algorithms. No hardware specifications are mentioned as part of the research. |
| Software Dependencies | No | The paper is theoretical. It does not mention any specific software dependencies or versions. |
| Experiment Setup | No | The paper is theoretical and presents algorithms and proofs. It does not detail any experimental setup, hyperparameters, or training configurations. |