Research map / Learning theory and algorithms / Submodular and game algorithms

A Unified Approach to Submodular Maximization Under Noise

NeurIPS 2025 · Learning theory and algorithms › Submodular and game algorithms · approach: Monotone submodular maximization · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives a meta-algorithm that turns any robust exact submodular maximization algorithm into one for persistent multiplicative-noise oracles via a randomly sampled smoothing surrogate, yielding (1-1/e) monotone and 1/e non-monotone matroid results and a 1/2 unconstrained result under noise.

Problem

Maximizing a submodular function given only a persistent noisy value oracle (unbiased multiplicative noise), under unconstrained or matroid constraints.

Approach

Reduce noisy submodular maximization to exact maximization by running any robust algorithm on a randomly smoothed surrogate F^{H,t}(S), the average of f(S∪H') over t-subsets of a random smoothing set H drawn from a basis, with the surrogate estimated by sampling without replacement; the reduction loses only o(1) in the ratio.

Key results

• Meta-algorithm with measured continuous greedy gives (1-1/e-O(eps)) for monotone matroid-constrained noisy maximization, improving prior (1-1/e)/2.
• Meta-algorithm with double greedy gives 1/2-O(eps) for unconstrained noisy non-monotone maximization, matching the noiseless tight ratio.
• In simulations (n=50), the surrogate method with m=200 reaches 0.735 of optimum versus 0.601 for double greedy on the noisy oracle directly and 0.550 for random subset.

Measured effects reported in the paper

Surprising findings

• Running double greedy directly on the noisy oracle performs only slightly better than picking a random subset.

Limitations

• Non-monotone matroid result is 1/e, not the best known 0.401 with exact oracle; robustness of that algorithm is left open.
• High-probability guarantees are established only for monotone functions; non-monotone case left open.
• Query complexity increases by a factor of m (about n^5/eps^2), which is large.

Experimental setup

Benchmarks: synthetic weighted quadratic-cost submodular function (n=50, 100)

Metrics: ratio of obtained value to optimum standard deviation

Baselines: Hassidim and Singer 2017 greedy Huang et al. matroid algorithm double greedy with noisy oracle random subset

Builds on: Hassidim and Singer 2017 smoothing surrogate measured continuous greedy double greedy pipage rounding

Closest papers by meaning

• Efficient Submodular Optimization under Noise: Local Search is Robust (NeurIPS 2022 · similarity 0.96)
• Improved Dynamic Algorithm for Non-monotone Submodular Maximization under Cardinality Constraint (ICML 2026 · similarity 0.92)
• Consistent Submodular Maximization (ICML 2024 · similarity 0.90)
• An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale (ICML 2025 · similarity 0.90)
• Online Two-Stage Submodular Maximization (NeurIPS 2025 · similarity 0.89)
• Discretely beyond $1/e$: Guided Combinatorial Algortihms for Submodular Maximization (NeurIPS 2024 · similarity 0.89)