Online Learning with Primary and Secondary Losses
Authors: Avrim Blum, Han Shao
NeurIPS 2020 | Conference PDF | Archive PDF | Plain Text | 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 avrim@ttic.edu Han Shao Toyota Technological Institute at Chicago han@ttic.edu |
| 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. |