Following the Perturbed Leader for Online Structured Learning
Authors: Alon Cohen, Tamir Hazan
ICML 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We complete our investigation with an online shortest path experiment and empirically show that our algorithm is both statistically and computationally efficient. |
| Researcher Affiliation | Academia | Alon Cohen ALONCOH@CSWEB.HAIFA.AC.IL University of Haifa, University of Haifa, Dept. of Computer Science, 31905 Haifa, Israel Tamir Hazan TAMIR@CS.HAIFA.AC.IL University of Haifa, University of Haifa, Dept. of Computer Science, 31905 Haifa, Israel |
| Pseudocode | Yes | Algorithm 1 Follow the perturbed leader Input: η > 0, set X {0, 1}d Set Θ1 0 for t = 1 to T do Sample γt N(0, I) Predict xt arg minx X x, Θt + ηγt Suffer loss xt, θt and accumulate Θt+1 Θt + θt end for |
| Open Source Code | No | The paper does not provide any links to or explicit statements about the release of source code for the methodology described. |
| Open Datasets | No | The paper states 'We constructed a directed graph with 53 vertices and 201 edges.' and describes how the adversary was built, but it does not refer to or provide access information for a publicly available or open dataset. |
| Dataset Splits | No | The paper describes an online learning setting and mentions evaluating algorithms with varying T, but it does not specify train/validation/test dataset splits. The experimental setup involves an online process rather than static data splits. |
| Hardware Specification | No | The paper does not specify any hardware details (e.g., GPU models, CPU types, memory) used for running the experiments. |
| Software Dependencies | No | The paper does not provide specific version numbers for any software components or libraries used. |
| Experiment Setup | Yes | The three algorithms we compare require to tune a parameter η. The minimax optimal choice of η depends on k, which in this case is the length of the longest s t path which is NP-hard and even NP-hard to approximate (Bj orklund et al., 2004). Therefore, we resort to choosing η based on the empirical performance of each of the algorithms against our adversary. We choose a nominal η by evaluating each algorithm on our problem with T = 100 on values of η ranging from en where n an integer is between 0 and 10 (we choose η from e n for Koolen et al. s algorithm). We run our experiments with horizons T between 1 and 100. We choose the nominal η and multiply it by p T/100 (divide by p T/100 for Koolen et al. s algorithm). |