A Unified Approach to Submodular Maximization Under Noise

Kshipra Bhawalkar, Yang Cai, Zhe Feng, Christopher Liaw, Tao Lin

TL;DR

This paper introduces a unified meta-algorithm for submodular maximization under persistent noise, transforming "robust" noiseless algorithms into noisy-setting variants with almost no loss in approximation guarantees. By leveraging a novel random surrogate smoothing technique, the authors achieve optimal approximation ratios for both monotone and non-monotone functions under matroid constraints and unconstrained settings.

What Problem Does This Paper Address?

Submodular maximization—maximizing functions that exhibit a "diminishing returns" property—is a cornerstone of machine learning (e.g., data summarization, viral marketing) and combinatorial optimization. Traditionally, algorithms assume access to an exact "value oracle" that perfectly reports the function's value for any given set. In reality, however, evaluations are often noisy, such as when estimating a model's true loss from a finite validation dataset.

The authors tackle the challenging setting of persistent noise, where querying the same set multiple times yields the exact same noisy value. This means you cannot simply average out the noise by repeatedly querying the same input. Prior works designed bespoke, complex algorithms for specific constraints (like cardinality), but lacked a general framework. This paper asks a fundamental question: Can we design a unified framework to reuse existing noiseless algorithms for noisy submodular maximization while retaining their theoretical guarantees?

Methods

The core innovation is a meta-algorithm that acts as a reduction framework, treating existing "robust" exact submodular optimization algorithms as black boxes.

  1. Random Surrogate Function: Prior approaches used deterministic smoothing (averaging over fixed neighborhoods), which required problem-specific analyses. This paper introduces a random surrogate function $F^{H,t}(S)$ that evaluates the function by taking the expectation over a randomly sampled "smoothing set" $H$.
  2. Black-Box Reduction: The meta-algorithm randomly samples a smoothing set $H$ from a basis of a matroid constraint, contracts the matroid around $H$, and runs the robust noiseless algorithm on an empirically sampled average of the noisy surrogate function.
  3. Robustness Definition: The authors formally define what it means for an algorithm to be "robust" against an $\epsilon$-approximate oracle, showing that classic algorithms like the Measured Continuous Greedy and Double Greedy naturally tolerate small errors and can be plugged directly into the framework.

Datasets

As a primarily theoretical paper, no real-world datasets were used. However, the authors evaluated their framework using a synthetic simulation setup:

  • Objective Function: A non-monotone weighted additive function with a quadratic cost: $f(S) = \sum_{i \in S} w_i - c|S|^2$, where weights $w_i$ are drawn from a $\text{Uniform}[0, 20]$ distribution.
  • Noise Model: Multiplicative persistent noise $\tilde{f}(S) = \xi_S f(S)$, where $\xi_S \sim \text{Normal}(\mu=1, \sigma^2=0.1)$.

Key Insights and Ideas

  • Randomization Overcomes Deterministic Limits: The key "aha moment" is that a random surrogate function can approximate the true submodular function well across all matroid constraints simultaneously, bypassing the need for the highly tailored, deterministic smoothing functions used in previous literature.
  • Algorithmic Robustness is Ubiquitous: Many classic submodular maximization algorithms are inherently robust to small perturbations. Instead of reinventing the wheel for noisy environments, researchers just need to verify an algorithm's tolerance to an $\epsilon$-approximate oracle.
  • First Non-Monotone Noisy Results: By decoupling the noise-handling mechanism from the optimization logic, the authors provide the first-ever approximation guarantees for noisy non-monotone submodular maximization (both unconstrained and matroid-constrained).

Key Results

The framework successfully closes the gap between noisy and noiseless submodular maximization performance, achieving optimal ("tight") bounds in multiple settings with only a negligible $o(1)$ loss:

  • Monotone + Matroid Constraint: Achieves a tight $1 - 1/e$ approximation, significantly improving the previous best result of $(1 - 1/e)/2$.
  • Non-Monotone + Unconstrained: Achieves a tight $1/2$ approximation using the Double Greedy algorithm.
  • Non-Monotone + Matroid Constraint: Achieves a $1/e$ approximation.

The performance improvements and comparisons are summarized in Table 1 from the paper:

Table 1: Our work compared with previous works on noisy submodular maximization. (tight) means optimal approximation ratios achievable by polynomial-time algorithms even without noise.

In empirical simulations, their surrogate-value-based algorithm outperformed standard Double Greedy with a noisy oracle by roughly 15% (at sample size $m=50$) to 25% (at $m=200$), demonstrating that naive application of noiseless algorithms fails under persistent noise.

Limitations and Future Work

  • Tightness for Non-Monotone Matroid Constraints: For non-monotone functions under matroid constraints, the meta-algorithm yields a $1/e \approx 0.367$ approximation. However, the optimal noiseless ratio is $0.401$. It remains an open question whether more technical algorithms can be proven robust and integrated into this framework to close this small gap.
  • High-Probability Bounds for Non-Monotone Functions: While the authors provide high-probability guarantees for monotone functions by repeating the algorithm and using a specialized comparison surrogate, this technique breaks down for non-monotone functions because removing elements can unpredictably increase or decrease the objective value.
  • Extension to Minimization: The framework is strictly designed for maximization; exploring noisy submodular minimization remains an open frontier.

Summary updated

Abstract

We consider the problem of maximizing a submodular function with access to a noisy value oracle for the function instead of an exact value oracle. Similar to prior work, we assume that the noisy oracle is persistent in that multiple calls to the oracle for a specific set always return the same value. In this model, Hassidim and Singer (2017) design a $(1-1/e)$-approximation algorithm for monotone submodular maximization subject to a cardinality constraint, and Huang et al (2022) design a $(1-1/e)/2$-approximation algorithm for monotone submodular maximization subject to any arbitrary matroid constraint. 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.
BibTeX
@inproceedings{bhawalkar2025unified,
  author = {Kshipra Bhawalkar and Yang Cai and Zhe Feng and Christopher Liaw and Tao Lin},
  title = {{A Unified Approach to Submodular Maximization Under Noise}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=d6RH6W6cul},
}
Figure