Robust Guarantees of Stochastic Greedy Algorithms
Authors: Avinatan Hassidim, Yaron Singer
ICML 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We applied the algorithms to an ego-network from (Leskovec & Krevl, 2014). This network has 333 nodes and 5038 edges. The submodular function we used is coverage, which models influence in social networks. In order to emphasize the implications of having results w.h.p, the graphs do not depict the average of many runs, but instead each graph is a single run of the algorithm. In greedy, we present the value of the solution at each iteration k. |
| Researcher Affiliation | Collaboration | 1Bar Ilan University and Google 2Harvard University. |
| Pseudocode | Yes | Algorithm 1 STOCHASTIC-GREEDY; Algorithm 2 STOCHASTIC-MATROID-GREEDY |
| Open Source Code | No | The paper does not provide any statement or link indicating that source code for the described methodology is publicly available. |
| Open Datasets | Yes | We applied the algorithms to an ego-network from (Leskovec & Krevl, 2014). This network has 333 nodes and 5038 edges. The submodular function we used is coverage, which models influence in social networks. |
| Dataset Splits | No | The paper does not explicitly mention training, validation, or test dataset splits. |
| Hardware Specification | No | The paper does not provide specific details about the hardware used to run the experiments. |
| Software Dependencies | No | The paper does not provide specific version numbers for any software dependencies used in the experiments. |
| Experiment Setup | Yes | When running stochastic greedy, we first sample a value ξ D, and then pick a random element out of the elements that have marginal contribution at least ξ maxa f S(a). The distribution D varies between the different lines. In the leftmost pane, APX (red line) depicts a D which is the constant distribution 0.5. In Stochastic greedy with mean 0.75, D is the uniform distribution on [0.5, 1] (purple line), and in Stochastic greedy with mean 0.5, D is the uniform distribution on [0, 1]. ... In the second pane, The purple line (exponential) depicts D as an exponential distribution with λ = 4, which gives a mean of 0.25. The red line is uniform in [0, 5], and the yellow is a Gaussian with µ = 0.25 and σ = 0.1. |