Maximization of Approximately Submodular Functions

1 Introduction

• The motivating question is whether approximate objectives retain optimization guarantees, since errors in evaluating a submodular function can make the available objective non-submodular.Prior work shows hardness for constant ε; this paper focuses on the alternative of subconstant error.Source: §1 · pp. 1–2
• The optimization model uses value queries to an oracle for F and seeks a size-at-most-k set with value close to the best feasible set.The introduction also notes applications of approximate submodularity in learning and sketching.Source: §1 · p. 2

1.1 Overview of the results

• For general monotone submodular functions, ε = 1/n^(1/2−β) permits no polynomial-query approximation better than O(1/n^β); coverage functions have a related lower bound at ε = 1/n^(1/3−β).The authors conclude that these guarantees remain unachievable even as the objective becomes arbitrarily close to submodular.Source: §1.1 · pp. 2–3
• The paper also gives positive approximation results: greedy works in a small-error regime, while bounded curvature supports an algorithm with a stated approximation ratio.The greedy guarantee is tight in that it ceases to be constant when ε = 1/k^(1−β).Source: §1.1 · p. 3

1.2 Discussion and additional related work

• The error model is deterministic and worst-case, and multiplicative evaluation error of a submodular function produces an approximately submodular objective.The discussion contrasts this setting with consistent and inconsistent stochastic noise models.Source: §1.2 · p. 3
• The discussion connects sampling-based estimation to approximate submodularity and interprets the results as bounds on tolerable estimation error.Averaging independent samples can produce relative error guarantees with high probability; the discussion relates the resulting error range to greedy guarantees and inapproximability.Source: §1.2 · p. 4

2 Query-complexity lower bounds

• The lower-bound strategy makes polynomial-query optimization imply distinguishing a hidden randomly chosen submodular function from a comparison function, despite their different cardinality-constrained optima.The construction chooses f with max_{|S|≤k} f(S) ≥ ρ(n) max_{|S|≤k} g(S), where ρ(n)=o(1); indistinguishability then rules out approximation better than ρ(n).Source: §2 · p. 4

2.1 Monotone submodular functions

• The hard-function construction handles small and large queried sets differently: it makes the functions coincide on small sets and uses concentration to establish closeness on large sets.For small S under the stated conditions, f_H(S)=g(S)=|S|; for large S, the intersections with H and its complement concentrate near their expected sizes.Source: §2.1 · pp. 4–5
• The comparison function g is monotone submodular, and its maximum under the cardinality constraint is separated from the maximum of f_H.The paper writes g(S)=G(|S|), with G the minimum of two non-decreasing linear functions, and notes that the maximum of f_H is k when α≤k≤h.Source: §2.1 · p. 5
• For ε ≥ 1/n^(1/2−β), fewer than 2^{Ω(n^(β/2))} queries cannot guarantee a nontrivial approximation for general monotone submodular functions.Theorem 3 states that some ε-approximately submodular objective forces the algorithm's approximation ratio to be at most 2 n^(β/2), with probability at least 1 − 1/2^{Ω(n^(β/2))}.Source: §2.1 · p. 6

2.2 Coverage functions

• For ε ≥ 1/n^(1/3−β), the exponential query lower bound also holds when the objective ε-approximates a coverage function.Theorem 4 uses the same proof structure as Theorem 3 but a different function class and comparison function.Source: §2.2 · p. 7

3.1 Greedy algorithm

• When ε ≤ 1/k, greedy achieves a constant approximation ratio, and this error threshold is tight for greedy even on additive functions.The paper presents the ε ≤ 1/k result as one relaxation of the exponential query-complexity lower bound.Source: §3 · p. 7, §3.1 · p. 8
• The greedy result follows from an inductive inequality that bounds the value of successive sets against an optimal solution.The proof applies submodularity, approximate submodularity, greedy selection, and the cardinality bound.Source: §3.1 · pp. 7–8
• For an ε-approximately submodular function, the greedy algorithm’s returned set has a constant approximation ratio, at least 1/2 − 2δ, when k ≥ 2, 0 ≤ δ < 1, and ε = δk.Source: §3.1 · pp. 7–8

3.2 Bounded curvature

• With bounded curvature, a polynomial-time algorithm achieves a constant approximation for constant ε.The paper gives an explicit ratio in Proposition 8, but the supplied passage truncates its formula.Source: §3.2 · p. 8

A Proof of Theorem 4

• The construction uses f_H and g that can both be realized as coverage functions.The set-intersection and set-size terms are additive, while a shared offset supplies α.Source: A Proof of Theorem 4 · p. 10
• The maximum of f_H is attained by a size-k subset of H and is k + α or greater, while g depends only on set size.For sets of size k, g has value kh/n + α.Source: A Proof of Theorem 4 · p. 10
• The proof draws H uniformly among size-h sets and handles the concentration inequality in separate cases according to |S|.For |S| ≤ εα, the relevant inequality is deterministic; the proof combines its bounds with the other case to conclude Theorem 4.Source: A Proof of Theorem 4 · p. 10

B Proof of Lemma 1

• The Chernoff bound used in Lemma 1 does not follow from the standard independent-variable bound, but it holds under negative association.The appendix states the bound for [0,1]-valued negatively associated variables and their sum.Source: B Proof of Lemma 1 · p. 10
• Negative association is defined through non-decreasing functions on disjoint subsets of the variables.This is the dependence condition used to justify the concentration argument.Source: B Proof of Lemma 1 · p. 10
• For a uniformly sampled size-h set H, its element-indicator variables are negatively associated.The proof writes |S ∩ H| as the sum of those indicators, with each indicator having probability h/n of being one.Source: B Proof of Lemma 1 · p. 11

C Proofs for Section 3.1

• The additive representative partitions the ground set into A, B, and C, and F differs from it only on sets A ∪ {c} for c in C.The proof describes the three groups by their element values and defines F using that exceptional case.Source: C Proofs for Section 3.1 · p. 11
• Greedy obtains O(k^(1−β)) on the constructed instance while the optimum is Ω(k), so its approximation ratio tends to zero as k grows.The construction fixes ε = 1/k^(1−β) for β > 0.Source: C Proofs for Section 3.1 · p. 11
• The matroid adaptation greedily considers elements in order of marginal F-value and adds an element only when independence is preserved.Its proof pairs an optimal basis with the returned basis using the matroid basis-exchange property.Source: C Proofs for Section 3.1 · pp. 11–12

• The additive surrogate Fa(S), defined as the sum of F's singleton values, is bounded relative to F using ε and the bounded-curvature parameter c.Source: D Proofs for Section 3.2 · p. 12
• The bound's proof uses approximate submodularity on both sides, subadditivity for the lower bound, and bounded curvature for the upper bound.Source: D Proofs for Section 3.2 · p. 12
• Proposition 8 finds the best size-at-most-k set for Fa by querying F on each singleton and selecting the top k, with the ratio following from Lemma 12.Source: D Proofs for Section 3.2 · p. 12