Buying Information for Stochastic Optimization
Authors: Mingchen Ma, Christos Tzamos
ICML 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Assuming the learner has an oracle for the original optimization problem, we design a 2-competitive deterministic algorithm and a e/(e 1)-competitive randomized algorithm for buying information. We show that this ratio is tight as the problem is equivalent to a robust generalization of the ski-rental problem, which we call super-martingale stopping. |
| Researcher Affiliation | Academia | Mingchen Ma 1 Christos Tzamos 1 ... 1Department of Computer Sciences, University of Wisconsin-Madison, Madison, WI, USA. |
| Pseudocode | Yes | Algorithm 1 DETERMINISTICSTOPPING (2-competitive deterministic algorithm for super-martingale stopping) ... Algorithm 2 RANDOMIZEDSTOPPING ( e e 1-competitive algorithm for super-martingale stopping) ... Algorithm 3 GREEDY (4-competitive Learner for MSSC with Time Dependent Feedback) ... Algorithm 4 GREEDYBUYING (8-competitive learner for MSSC with Feedback) |
| Open Source Code | No | The paper does not provide any concrete links or statements about the availability of open-source code for the described methods. |
| Open Datasets | No | The paper is a theoretical work focusing on algorithm design and competitive analysis. It does not involve empirical training on datasets, thus no training data is mentioned or made available. |
| Dataset Splits | No | The paper is a theoretical work on algorithms and competitive analysis. It does not conduct empirical experiments involving validation datasets or splits. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithm design and competitive analysis; it does not mention any specific hardware used for running experiments. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithm design and competitive analysis. It does not mention any specific software dependencies with version numbers that would be required for empirical reproduction. |
| Experiment Setup | No | The paper is theoretical, presenting algorithms and their competitive analysis. It does not detail an experimental setup with hyperparameters or training configurations. |