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..
Submodular Function Minimization with Noisy Evaluation Oracle
Authors: Shinji Ito
NeurIPS 2019 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | This paper considers submodular function minimization with noisy evaluation oracles that return the function value of a submodular objective with zero-mean additive noise. For this problem, we provide an algorithm that returns an O(n3/2/T)additive approximate solution in expectation, where n and T stand for the size of the problem and the number of oracle calls, respectively. There is no room for reducing this error bound by a factor smaller than O(1/n). Indeed, we show that any algorithm will suffer additive errors of Ω(n/T) in the worst case. Further, we consider an extended problem setting with multiple-point feedback in which we can get the feedback of k function values with each oracle call. |
| Researcher Affiliation | Collaboration | Shinji Ito NEC Corporation, The University of Tokyo EMAIL |
| Pseudocode | Yes | Algorithm 1 An algorithm for submoudular function minimization with noisy evaluation oracle |
| Open Source Code | No | The paper does not provide any statement about releasing source code, nor does it include a link to a code repository for the described methodology. |
| Open Datasets | No | The paper describes theoretical algorithms and analyses, and does not involve empirical evaluation on datasets. Therefore, no information about publicly available datasets used for training is provided. |
| Dataset Splits | No | As a theoretical paper, it does not describe empirical experiments or dataset usage, and thus provides no information about training, validation, or test dataset splits. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithm design and proofs, rather than empirical experiments. Therefore, it does not specify any hardware used for running experiments. |
| Software Dependencies | No | The paper focuses on theoretical algorithm design and analysis. It does not describe an implementation or empirical experiments that would necessitate the listing of specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not conduct experiments. Therefore, it does not provide details on an experimental setup, such as specific hyperparameter values or system-level training settings. |