Probabilistic Submodular Maximization in Sub-Linear Time
Authors: Serban Stan, Morteza Zadimoghaddam, Andreas Krause, Amin Karbasi
ICML 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We demonstrate the effectiveness of our approach on several real-world applications where running the maximization problem on the reduced ground set leads to two orders of magnitude speed-up while incurring almost no loss.In this section, we describe our experimental setting. We offer details on the datasets we used and the baselines we ran Replacement Greedy against. |
| Researcher Affiliation | Collaboration | Serban Stan 1 Morteza Zadimoghaddam 2 Andreas Krause 3 Amin Karbasi 1 Yale University, New Haven, Connecticut, USA 2Google Research, New York, NY 10011, USA 3ETH Zurich, Zurich, Switzerland. |
| Pseudocode | Yes | Algorithm 1 Replacement Greedy |
| Open Source Code | No | The paper does not explicitly state that their source code is open-source or provide a link to it. It only thanks other authors for providing their implementation for a baseline. |
| Open Datasets | Yes | For this application we use a subset of the VOC2012 dataset (Everingham et al., 2014) where we consider n = 150 with m = 20 categories. We test the performance of Replacement Greedy on a movie dataset where movies should be recommended to users with user-specific utility functions. The dataset consists of user ratings on a scale of 1 to 5, along with some movie information. |
| Dataset Splits | No | We split the users in half. We use the first 100 of them as a training set for the algorithms to built up their reduced ground set S of size ℓ. We then compare submodular maximization with cardinality constraint k = 3 on the reduced sets S (returned by the baselines) and that of the whole ground set Ω. To this end, we sample 20 users from the test group and compute their average values. The paper specifies train/test splits but no explicit validation split. |
| Hardware Specification | Yes | The experiments were ran in a Python 2.7 environment on a OSX 10.12.13 machine. The processor was a 2.5 GHz Intel Core i7 with 16 GB 1600 MHz DDR3 memory. |
| Software Dependencies | No | The paper mentions 'Python 2.7 environment' but does not specify versions for other key software components, libraries, or solvers. |
| Experiment Setup | Yes | In our experiments, we use ϵ = 0.2. We initialize S by incrementally picking ℓelements such that at each step we maximize the sum of marginal gains for the m functions fi. For this task, we reproduce the experiment from Balkanski et al. (2016) on Wikipedia articles for Machine Learning. Fig. 1a and 1b show the objective values for a fix k = 5 (and varying ℓ) and a fixed ℓ= 20 (and varying k). We split the users in half. We use the first 100 of them as a training set for the algorithms to built up their reduced ground set S of size ℓ. We then compare submodular maximization with cardinality constraint k = 3 on the reduced sets S... |