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..
A Unified Approach to Submodular Maximization Under Noise
Authors: Kshipra Bhawalkar, Yang Cai, Zhe Feng, Christopher Liaw, Tao Lin
NeurIPS 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this paper, we design a meta-algorithm that allows us to take any robust algorithm for exact submodular maximization as a black box and transform it into an algorithm for the noisy setting while retaining the approximation guarantee. By using the meta-algorithm with the measured continuous greedy algorithm, we obtain a (1 1/e)-approximation (resp. 1/e-approximation) for monotone (resp. non-monotone) submodular maximization subject to a matroid constraint under noise. Furthermore, by using the meta-algorithm with the double greedy algorithm, we obtain a 1/2-approximation for unconstrained (non-monotone) submodular maximization under noise. Section 5: Simulation Results In this section, we present simulation results to compare the performances of our proposed algorithm (Algorithm 1) and some heuristic algorithms for the noisy submodular maximization problem. We run 1000 simulations. In each simulation, we first sample f (namely, the weights wi) and the noisy function f (the multipliers ξS), then run each of the above four algorithms once. Table 2 shows the means E f(ALG) f(O ) and standard deviations of the true values of the obtained sets, as a fraction of the optimal value. |
| Researcher Affiliation | Collaboration | Kshipra Bhawalkar Google Mountain View, CA EMAIL Yang Cai Yale University New Haven, CT EMAIL Zhe Feng Google Mountain View, CA EMAIL Christopher Liaw Google Mountain View, CA EMAIL Tao Lin Harvard University Cambridge, MA EMAIL |
| Pseudocode | Yes | Algorithm 1: Meta-algorithm for noisy submodular maximization under matroid constraints Algorithm 2: Measured continuous greedy [9] with approximate value oracle Algorithm 3: Double greedy [3] with approximate value oracle |
| Open Source Code | Yes | Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: The code is uploaded. |
| Open Datasets | No | We focus on the simple yet underexplored case of unconstrained non-monotone noisy submodular maximization. We consider an example where the submodular function is a weighted additive function with quadratic cost in the subset size: S N, f(S) = P i S wi c|S|2, where each element i has weight wi Uniform[0, 20], with cost parameter c = 10/n, so the ground set N has expected value 0. When sampling wi, we ensure that f is non-negative. The noisy value function is f(S) = ξSf(S) where ξS Normal(µ = 1, σ2 = 0.1). |
| Dataset Splits | No | We run 1000 simulations. In each simulation, we first sample f (namely, the weights wi) and the noisy function f (the multipliers ξS), then run each of the above four algorithms once. The paper describes a simulation setup where data is generated for each run, rather than using predefined splits of a larger dataset. |
| Hardware Specification | No | The paper does not provide specific details about the hardware used for the simulations. While the NeurIPS checklist indicates 'Yes' for hardware resources, the justification is empty in the provided text, and no specific models or configurations are present in the main body. |
| Software Dependencies | No | The paper does not provide specific version numbers for any software dependencies. It refers to algorithms and theoretical concepts without detailing their implementation environment beyond general terms. |
| Experiment Setup | Yes | We focus on the simple yet underexplored case of unconstrained non-monotone noisy submodular maximization. We consider an example where the submodular function is a weighted additive function with quadratic cost in the subset size: S N, f(S) = P i S wi c|S|2, where each element i has weight wi Uniform[0, 20], with cost parameter c = 10/n, so the ground set N has expected value 0. When sampling wi, we ensure that f is non-negative. The noisy value function is f(S) = ξSf(S) where ξS Normal(µ = 1, σ2 = 0.1). After simple tuning, we set the parameters to h = 20, t = 4, and vary m. We run 1000 simulations. |