Submodular + Concave
Authors: Siddharth Mitra, Moran Feldman, Amin Karbasi
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We provide a suite of Frank-Wolfe style algorithms, which, depending on the nature of the objective function (i.e., if G and C are monotone or not, and non-negative or not) and on the nature of the set P (i.e., whether it is downward closed or not), provide 1 1/e, 1/e, or 1/2 approximation guarantees. We then use our algorithms to get a framework to smoothly interpolate between choosing a diverse set of elements from a given ground set (corresponding to the mode of a determinantal point process) and choosing a clustered set of elements (corresponding to the maxima of a suitable concave function). Additionally, we apply our algorithms to various functions in the above class (DR-submodular + concave) in both constrained and unconstrained settings, and show that our algorithms consistently outperform natural baselines. 4 Experiments In this section we describe some experiments pertaining to our algorithms for maximizing DRsubmodular + concave functions. |
| Researcher Affiliation | Academia | Siddharth Mitra School of Engineering & Applied Science Yale University New Haven, CT 06520 8292 siddharth.mitra@yale.edu Moran Feldman Department of Computer Science University of Haifa Haifa 3498838 , Israel moranfe@cs.haifa.ac.il Amin Karbasi School of Engineering & Applied Science Yale University New Haven, CT 06520 8292 amin.karbasi@yale.edu |
| Pseudocode | Yes | Algorithm 1: GREEDY FRANK-WOLFE (ε) ... Algorithm 2: MEASURED GREEDY FRANK-WOLFE (ε) ... Algorithm 3: GRADIENT COMBINING FRANK-WOLFE (ε) ... Algorithm 4: NON-OBLIVIOUS FRANK-WOLFE (ε) |
| Open Source Code | Yes | Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [Yes] It is in the supplemental material. |
| Open Datasets | Yes | On Jeopardy Dataset. ... taken from https://www.j-archive.com/ ... The DR-submodular objective function for the D-optimal experimental design problem is G(x) = log det Pn i=1 xi Y i Yi . Here, Yi is an n dimensional row-vector in which each entry is drawn independently from the standard Gaussian distribution. (From checklist) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [Yes] It is in the supplemental material. |
| Dataset Splits | No | The paper states it specifies all parameter details, but Section 4 (Experiments) does not provide specific training/test/validation dataset splits, percentages, or absolute sample counts. It describes how the data is generated or used, but not how it is split for training, validation, or testing. |
| Hardware Specification | Yes | All experiments are done on a 2015 Apple Mac Book Pro with a quad-core 2.2 GHz i7 processor and 16 GB of RAM. |
| Software Dependencies | No | The paper mentions using a 'pretrained BERT model' but does not provide specific version numbers for any software, libraries, or frameworks used in the experiments. |
| Experiment Setup | Yes | In the current experiment, we let n {8, 12, 16} and m {0.5n, n, 1.5n}, and run each algorithm for 50 iterations. Note that having fixed the number of iterations, the maximum step size for Algorithms 1 and 2 is upper bounded by (number of iterations) 1 = 1/50 to guarantee that these algorithms remain within the polytope. To ensure consistency, we set the step sizes for the other algorithms to be 1/50 as well, except for Algorithm 4 for which we set to the value of ε given by solving e 1 β(ε)/ε2 = 50. We start Algorithms 1 and 2 from the starting point their pseudocodes specify, and the other algorithms from the same arbitrary point. ... The step sizes and starting points used by the algorithms are set exactly like in Section 4.2.1. |