Efficient Submodular Optimization under Noise: Local Search is Robust
Authors: Lingxiao Huang, Yuyi Wang, Chunxue Yang, Huanjian Zhou
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | This paper considers the problem of constrained monotone submodular maximization with noisy oracles introduced by [11]. For a cardinality constraint, we propose an algorithm achieving a near-optimal 1 − 1 e − O(ε) -approximation guarantee (for arbitrary ε > 0) with only a polynomial number of queries to the noisy value oracle, which improves the exponential query complexity of [20]. For general matroid constraints, we show the first constant approximation algorithm in the presence of noise. Our main approaches are to design a novel local search framework that can handle the effect of noise and to construct certain smoothing surrogate functions for noise reduction. |
| Researcher Affiliation | Collaboration | Lingxiao Huang Huawei TCS Lab -> Nanjing University huanglingxiao1990@126.com Yuyi Wang Swiss Federal Institute of Technology yuyiwang920@gmail.com Chunxue Yang Nanyang Technological University chunxue001@e.ntu.edu.sg Huanjian Zhou The University of Tokyo zhou@ms.k.u-tokyo.ac.jp |
| Pseudocode | Yes | Algorithm 1: Noisy local search (NLS(cˆφh, I(M), λ)) ... Algorithm 2: Noisy local search under a small cardinality constraint ... Algorithm 3: Noisy local search under large cardinality constraint |
| Open Source Code | No | Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [N/A] |
| Open Datasets | No | The paper is theoretical and does not conduct empirical studies with datasets. |
| Dataset Splits | No | The paper is theoretical and does not conduct empirical studies, thus no dataset splits are provided. |
| Hardware Specification | No | The paper is theoretical and does not conduct empirical studies, therefore no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not conduct empirical studies, so no software dependencies with version numbers are listed. |
| Experiment Setup | No | The paper is theoretical and does not conduct empirical studies, so no experimental setup details like hyperparameters are provided. |