Dual Mirror Descent for Online Allocation Problems
Authors: Santiago Balseiro, Haihao Lu, Vahab Mirrokni
ICML 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 6. Numerical Experiment Here, we present a numerical experiment on proportional matching with high entropy (Section 5.2) to verify our results. Figure 1 plots the regret versus horizon T, from which we can clearly see that the regret grows at the rate of T, which verifies the results in Theorem 1. Figure 2 plots the relative reward (ratio between the reward collected by the online algorithm and the offline optimal) versus horizon T. |
| Researcher Affiliation | Collaboration | Santiago Balseiro 1 2 Haihao Lu 2 Vahab Mirrokni 2 ... 1Columbia University, New York, USA 2Google Research, New York, USA. |
| Pseudocode | Yes | Algorithm 1 Dual Mirror Descent Algorithm for (1) ... Algorithm 2 Online Dual Mirror Descent Algorithm for Bidding in Repeated Auctions ... Algorithm 3 Online Dual Mirror Descent Algorithm for Proportional Matching Problems with High Entropy |
| Open Source Code | Yes | The details of the numerical experiment and data generation are presented in Appendix H, and the code to reproduce the results is in supplementary materials. |
| Open Datasets | Yes | The dataset is generated following the procedures stated in Balseiro et al. (2014). |
| Dataset Splits | No | The paper describes generating '100,000 samples' and using '20 random datasets with size T uniformly randomly chosen from 100,000 samples' for experiments, but it does not specify explicit train/validation/test splits for these datasets. |
| Hardware Specification | No | The paper does not provide any specific hardware details used for running experiments. |
| Software Dependencies | No | The paper does not provide specific ancillary software details with version numbers. |
| Experiment Setup | Yes | For all experiments, we start from µ0 = 0, utilize h(x) = 1/2 x 2 2 as our reference function (thus the algorithm is dual sub-gradient descent), and choose η = 1/T as the step-size. ... We incorporate the entropy regularizer H(x) to the objective with parameter λ = 0.0002 |