Online Learning for Min Sum Set Cover and Pandora’s Box
Authors: Evangelia Gergatsouli, Christos Tzamos
ICML 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our work presents a simple but powerful framework for designing online learning algorithms for PANDORA S BOX, MSSC and other related problems. Our framework yields approximately low-regret algorithms for these problems through a three step process: 1. We first obtain convex relaxations of the instances of every round. 2. We then apply online-convex optimization to obtain good fractional solutions to the relaxed instances achieving low regret. 3. We finally round the fractional solutions to integral solutions for the original instances at a small multiplicative loss. Through this framework, we obtain a 9.22-approximate no-regret algorithm for the problem of selecting 1 box. O(1)-approximate no-regret algorithm for the problem of selecting k boxes. O(log k)-approximate no-regret algorithm for the problem of selecting a rank k matroid basis. |
| Researcher Affiliation | Academia | 1Department of Computer Sciences, University of Wisconsin Madison, Madison, WI, USA. |
| Pseudocode | Yes | Algorithm 1: Algorithm A for the full information case. Algorithm 2: AP A minimizing regret against PA Algorithm 3: Algorithm AF for minimizing regret vs NA |
| Open Source Code | No | The paper does not contain any statements about making source code openly available, nor does it provide links to a code repository. |
| Open Datasets | No | This paper is theoretical and does not conduct empirical studies using datasets, thus no training dataset information or access is provided. |
| Dataset Splits | No | This paper is theoretical and does not conduct empirical studies. Therefore, no information regarding dataset splits for training, validation, or testing is provided. |
| Hardware Specification | No | The paper focuses on theoretical algorithms and their guarantees; it does not describe any experiments that would require specific hardware, and thus no hardware specifications are mentioned. |
| Software Dependencies | No | The paper describes theoretical algorithms and does not specify any software dependencies with version numbers, as no empirical experiments were conducted that would require such details. |
| Experiment Setup | No | The paper presents theoretical algorithms and their properties rather than empirical experiments. Therefore, no experimental setup details, such as hyperparameters or training configurations, are provided. |