Approximation Guarantees of Local Search Algorithms via Localizability of Set Functions
Authors: Kaito Fujii
ICML 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We conduct experiments in sparse regression and structure learning of graphical models to confirm the prac tical efficiency of the proposed local search algorithms. |
| Researcher Affiliation | Academia | 1National Institute of Informatics, Tokyo, Japan. Correspon dence to: Kaito Fujii <fujiik@nii.ac.jp>. |
| Pseudocode | Yes | Algorithm 1 Local search algorithms for a matroid con straint. ... Algorithm 2 Local search algorithms for a p-matroid inter section or p-exchange system constraint (p 2). |
| Open Source Code | No | The paper does not contain an explicit statement or link providing concrete access to the source code for the methodology described. |
| Open Datasets | No | The paper mentions generating synthetic datasets (e.g., "We generate synthetic datasets with a partition matroid constraint.") but does not provide concrete access information such as a link, DOI, or a citation to a publicly available dataset. |
| Dataset Splits | No | The paper does not provide specific dataset split information (e.g., percentages or sample counts for training, validation, and test sets) to reproduce the data partitioning. |
| Hardware Specification | Yes | We conduct the experiments in a machine with Intel Xeon E3 1225 V2 (3.20 GHz and 4 cores) and 16 GB RAM. |
| Software Dependencies | No | All the algorithms are implemented in Python 3.6. ... We use the L-BFGS-G solver in scipy.optimize li brary for evaluating the value of f. ... max-weight matching problem solver in Netwerk X library. The paper specifies Python 3.6, but does not provide version numbers for the other mentioned libraries (scipy.optimize, Netwerk X). |
| Experiment Setup | Yes | We set (n, d, nc, np) = (200, 50, 5, 5) in one setting and (n, d, nc, np) = (1000, 100, 10, 10) in the other setting. ... We apply these methods to a partition matroid constraint with capacity n0 p for each n0 2 {1, , 10}. ... We set (|V |, d) = (10, 5) in one setting and (|V |, d) = (20, 7) in the other setting. ... We apply these methods to pseudo-log-likelihood maximization under a b-matching constraint for each b 2 {1, , d}. |