Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Efficient Submodular Optimization under Noise: Local Search is Robust
Authors: Lingxiao Huang, Yuyi Wang, Chunxue Yang, Huanjian Zhou
NeurIPS 2022 | Venue PDF | 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 EMAIL Yuyi Wang Swiss Federal Institute of Technology EMAIL Chunxue Yang Nanyang Technological University EMAIL Huanjian Zhou The University of Tokyo EMAIL |
| 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. |