List Update with Prediction
Authors: Yossi Azar, Shahar Lewkowicz, Varun Suriyanarayana
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Finally, the experiments we have made show that our algorithms perform better than the standard competitive algorithms for this problem. ... We describe below the input generation, the algorithms we evaluated and the results. ... Experimental Results. In our experiments, we vary on various parameters: In generating the sequence, we vary on the 4 parameter: n the number of elements, m the length of the sequence, B the size of a block, The updated probability gamma. |
| Researcher Affiliation | Academia | Yossi Azar*1, Shahar Lewkowicz*1, Varun Suriyanarayana*2 1Department of Computer Science, Tel-Aviv University 2School of Operations Research and Information Engineering, Cornell University EMAIL, EMAIL, EMAIL |
| Pseudocode | Yes | Algorithm 1 PRED performs free swaps only ... Algorithm 2 PRED performs a paid swap |
| Open Source Code | No | The paper does not provide an explicit statement or a link to its source code. While it mentions |
| Open Datasets | No | The paper describes its own |
| Dataset Splits | No | The paper describes generating synthetic request sequences for experiments ( |
| Hardware Specification | Yes | For completeness, the machine used was an HP Omen 15 with an i7-8750H CPU with 16 GB DDR4-2666 SDRAM. The GPU was a GTX 1060 6GB but was unused for this experiment |
| Software Dependencies | No | The paper does not specify any software names with version numbers used for the experiments. |
| Experiment Setup | Yes | Input Generation. We create sequences on n elements (the default value is n= 100 but we also tried n= 30 and n= 50). The length of the sequence is m requests (the default value is m= 10000 but we also tried m= 1000 and m= 3000). We start with a uniform distribution on the elements. At any time, we have our distribution on the elements, and we sample one request. We repeat sampling for a block of requests of certain length B (where B is between 1 and 100). At the end of the block, we update the distribution by updating the probability of B random elements (and renormalize). We call this element the chosen element. Updating to the chosen element is done either through exponential decay or multiplicative weights. Specifically, in the exponential decay, we multiply the vector of probabilities by gamma < 1 and add 1/gamma to the chosen element (where gamma ranges between 0.9 and 0.99). In the multiplicative weights, we multiply the weight of the chosen element by gamma (and renormalize, where gamma ranges between 1.01 and 1.25). Overall, we have four parameters: n, m, B, gamma. ... The parameter we have here is epsilon (where epsilon ranges between 0.01 to 0.2). |