Minimizing a Submodular Function from Samples
Authors: Eric Balkanski, Yaron Singer
NeurIPS 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper we consider the problem of minimizing a submodular function from training data. ... We show that even learnable submodular functions cannot be minimized within any non-trivial approximation when given access to polynomially-many samples. Specifically, we show that there is a class of submodular functions with range in [0, 1] such that, despite being PAC-learnable and minimizable in polynomial-time, no algorithm can obtain an approximation strictly better than 1/2 o(1) using polynomially-many samples drawn from any distribution. Furthermore, we show that this bound is tight via a trivial algorithm that obtains an approximation of 1/2. |
| Researcher Affiliation | Academia | Eric Balkanski Harvard University ericbalkanski@g.harvard.edu Yaron Singer Harvard University yaron@seas.harvard.edu |
| Pseudocode | Yes | Algorithm 1 A learning algorithm for f 2 F which combines classification and linear regression. |
| Open Source Code | No | The paper does not provide any explicit statements or links indicating that the source code for the described methodology is publicly available. |
| Open Datasets | No | This paper is theoretical and focuses on mathematical proofs and algorithms; it does not conduct empirical studies with datasets. While it discusses 'training data' conceptually in the context of learning functions, it does not refer to specific datasets used for empirical evaluation nor provide access information for such datasets. |
| Dataset Splits | No | This paper is theoretical and does not describe empirical experiments, thus no dataset splits for training, validation, or testing are provided. |
| Hardware Specification | No | This paper is theoretical and does not describe empirical experiments, therefore no hardware specifications are mentioned. |
| Software Dependencies | No | This paper is theoretical and does not describe empirical experiments, therefore no specific software dependencies with version numbers are mentioned. |
| Experiment Setup | No | This paper is theoretical and does not describe empirical experiments or their setup, thus no hyperparameter values or training configurations are provided. |