Submodular Function Minimization with Noisy Evaluation Oracle
Authors: Shinji Ito
NeurIPS 2019 | Conference PDF | Archive PDF | Plain Text | 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 i-shinji@nec.com |
| 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. |