Source-linked AI summary
On the Approximation Relationship between Optimizing Ratio of Submodular (RS) and Difference of Submodular (DS) Functions
Pierre Perrault, Jennifer Healey, Zheng Wen, Michal Valko
TL;DR
RS optimization has bounded approximation guarantees, whereas DS optimization is inapproximable in the worst case. The paper proves an FPTAS relationship between their approximation versions and analyzes greedy optimization for a broader family of objectives. Its central result is that RS and DS are equivalent under a weaker-than-classical DS guarantee.
Problem
RS has bounded approximation factors, but DS is inapproximable in the worst case, motivating a study of their relationship under weaker approximation guarantees.
Source: §1 · p. 3Method
The paper gives FPTAS reductions between α-approximation of general ratio and difference problems and analyzes greedy maximization of Ψ(f, g) for quasiconvex Ψ nondecreasing in its first variable.
Source: §1 · p. 3, §2.1 · p. 5Results
α-approximation of Difference and α-approximation of Ratio are equivalent via FPTAS reductions, yielding a weaker-than-classical DS approximation guarantee from an RS guarantee.
Source: §1 · p. 3, §2.1 · p. 5Takeaways & Limitations
The paper connects RS and DS approximability and extends greedy analysis to objectives including f/g and f − g.
Source: §1 · p. 3, §5 · p. 9The stated RS and DS problems assume non-negative monotone submodular f and g, with g positive.
Source: §1 · p. 2
Abstract
from arXiv · showhide
We demonstrate that from an algorithm guaranteeing an approximation factor for the ratio of submodular (RS) optimization problem, we can build another algorithm having a different kind of approximation guarantee -- weaker than the classical one -- for the difference of submodular (DS) optimization problem, and vice versa. We also illustrate the link between these two problems by analyzing a \textsc{Greedy} algorithm which approximately maximizes objective functions of the form $\Psi(f,g)$, where $f,g$ are two non-negative, monotone, submodular functions and $\Psi$ is a {quasiconvex} 2-variables function, which is non decreasing with respect to the first variable. For the choice $\Psi(f,g)\triangleq f/g$, we recover RS, and for the choice $\Psi(f,g)\triangleq f-g$, we recover DS. To the best of our knowledge, this greedy approach is new for DS optimization. For RS optimization, it reduces to the standard \textsc{GreedRatio} algorithm that has already been analyzed previously. However, our analysis is novel for this case.
1. Introduction
Submodular functions model diminishing returns and appear in applications such as feature selection, data summarization, and active learning. This paper studies ratio and difference objectives, whose approximation properties differ despite their connection.
Background
- Submodular functions have diminishing marginal returns and arise in settings including feature selection, data summarization, and active learning.The introduction defines submodularity through the set-function inequality and its equivalent diminishing-returns characterization.Source: §1 · p. 1
RS and DS optimization problems
- RS and DS objectives combine a gain function f with a positive cost function g, respectively by maximizing f/g or f − g.Both use non-negative, monotone, submodular functions; g is positive for RS.Source: §1 · p. 2
The RS–DS connection
- Although both RS and DS optimization are NP-hard, RS has bounded approximation factors while DS is inapproximable in the worst case.The cited results give RS an O(√n log(n)) approximation factor, tight up to the log factor; DS inapproximability follows because any set-function maximization problem can be written as DS.Source: §1 · p. 3
Contributions
- The paper establishes an approximability connection between RS and DS, including a weaker-than-classical approximation guarantee for DS.It also extends a greedy analysis to quasiconvex objectives Ψ(f, g) that are nondecreasing in their first variable.Source: §1 · p. 3
2. Approximability of general difference and ratio optimization problems
The paper studies how approximation algorithms for general ratio and difference optimization can be converted into one another. It proves an FPTAS equivalence for their α-approximation versions and applies this relationship to RS and DS.
2. Approximability of general difference and ratio optimization problems
- The equivalence applies to general optimization over X when the function classes permit efficient maximization of f and minimization of g.The framework allows non-negative functions f and positive functions g, with the stated optimization access.Source: §2 · pp. 3–4
- An exact Difference algorithm can solve Ratio to additive ε accuracy by binary search in O(log(1/ε)) calls.Each step halves an interval containing the optimal ratio.Source: §2 · p. 4
2.1. FPTAS connection between Difference and Ratio approximation
- α-approximation of Difference and α-approximation of Ratio are mutually reducible with an FPTAS.The reverse reduction adjusts an additive constant c in g toward the optimal difference value c*, while the other direction adjusts a multiplicative parameter.Source: §2.1 · p. 5
- The paper calls the resulting DS guarantee weak DS approximability and derives it from an RS approximation guarantee.The cited RS guarantee is α = O(n^-1/2 log(n)^-1).Source: §2.1 · p. 5
3. RS and DS problems through GREEDY algorithms
Algorithm 1 applies a common greedy strategy to RS and DS by choosing Ψ, with approximation guarantees under stated assumptions and exactness for modular functions. The section also extends the approach to knapsack constraints and gives examples beyond the ratio and difference objectives.
Curvature
- The greedy guarantee depends on g’s curvature; curvature measures departure from modularity, and equals zero exactly for modular monotone submodular functions.Source: §3 · p. 6
Greedy algorithm
- Algorithm 1 generalizes GREEDRATIO: before its final step, it is the standard algorithm, while the same loop supports multiple choices of Ψ.Source: §3 · p. 6
Exact modular case
- For modular f and g, Algorithm 1 is exact for both the difference and ratio objectives, even when the functions are not monotone.Source: §3 · p. 6
General approximation guarantee
- Under Theorem 2’s assumptions, Algorithm 1 provides approximation guarantees for both Ψ(f,g)=f−g and Ψ(f,g)=f/g.The guarantee applies when f and g are non-negative, monotone, submodular functions and Ψ is quasiconvex and non-decreasing in its first variable.Source: §3 · pp. 6–7
Further objectives
- With modular g, Ψ(f,g)=f−√g can use the zero-curvature guarantee for g, and the same improvement extends to f/√g and non-decreasing concave replacements of √g.The text contrasts this with treating √g as a submodular term, whose curvature need not be small.Source: §3 · p. 7
Knapsack constraint
- Under a knapsack constraint g(S)≤B, Algorithm 2 uses partial enumeration for initialization and has a guarantee for Ψ non-decreasing in its first variable and non-increasing in its second.Source: §3 · p. 7
4. Experiments
In influence maximization with costly influencers, the experiments compare Algorithm 1 for DS maximization with ModMod on a Facebook subgraph. Algorithm 1 performs better in the reported comparisons, while computation times are similar overall.
Experimental setting
- The evaluation uses influence maximization with costly influencers, where f measures expected spread and modular g represents seed-influencer costs.The objective is to maximize f−g.Source: §4 · p. 8
- The study uses a 333-node, 5,038-edge Facebook subgraph, 10 independent-cascade instances, and 50 simulations per λ value with randomly chosen costs and weights.Source: §4 · p. 8
Compared methods
- The greedy implementation uses lazy evaluations of marginal gain per cost; ModMod iteratively maximizes a modular lower bound on f minus g until its set stops changing.The lazy method maintains upper bounds on marginal gains and uses submodularity to identify the largest one.Source: §4 · p. 8
Results
- Algorithm 1 outperforms ModMod in every reported comparison, with the performance gap increasing with λ; computation times are similar, though ModMod tends to be faster at larger λ.Figure 1 compares performance and computation-time differences; its plus signs mark mean points and time differences are in seconds.Source: §4 · p. 8, Figure 1 · p. 9
5. Conclusion
The paper establishes a weaker-approximation equivalence between RS and DS, gives a way to switch between them, and generalizes GREEDRATIO to objectives including both. It identifies broader combinations of submodular functions and weaker assumptions on Ψ as open questions.
Main conclusions
Future directions
- Open questions include extending the results to more than two submodular functions and reducing the assumptions on Ψ in Theorem 2.Source: §5 · p. 9
Appendix A. Proof of Theorem 1
The proof transfers approximate solutions between Difference and Ratio using binary-search procedures. Their interval invariants and halving updates yield logarithmic dependence on the target error.
Proof invariants
- Algorithm 3 maintains a lower bound on the returned difference and an α-scaled upper bound on every feasible difference; Algorithm 4 maintains corresponding bounds for ratios.Source: Appendix A · p. 13
Convergence
- Both transfer procedures halve their uncertainty interval at each iteration, so each takes O(log(1/ε)) iterations.The intervals track bounds on difference values or ratio values, depending on the transfer direction.Source: Appendix A · p. 13
Guarantee boundary
- Using an approximation algorithm for Difference to seek a factor on g via f−c is not assured to preserve nonnegativity of the modified function.Source: Appendix A · p. 14
Appendix B. Proof of Proposition 1
The proof shows that the greedy ordering contains an exact maximizer for both the difference and ratio objectives. For the ratio, it uses a difference objective with the optimal ratio as its parameter.
Appendix B. Proof of Proposition 1
- For Ψ(f,g)=f−g, a maximizer is a prefix of the element ordering and is inspected by Algorithm 1.The algorithm therefore outputs a maximizer of the difference objective.Source: Appendix B · p. 14
- The prefix property ensures that the relevant maximizers are among the sets examined at the end of Algorithm 1.This applies to the stated difference and ratio cases.Source: Appendix B · p. 14
- For Ψ(f,g)=f/g, set λ to the maximum ratio; a maximizer of f−λg is also a ratio maximizer.The proof notes that the maximum of f−λg is 0 and that this set is inspected by Algorithm 1.Source: Appendix B · p. 14
Appendix C. Proof of Theorem 2
The proof compares the algorithm’s output with the two greedy sets whose g-values bracket the optimum’s g-value. It uses the proof’s inequality bounds and Ψ’s monotonicity and quasiconvexity to relate those sets to the optimum.
Appendix C. Proof of Theorem 2
- The inequality chain invokes submodularity, monotonicity, g’s curvature, and 1−x≤e^(−x) to establish the claimed bound.The passage identifies these as the justifications for the intermediate inequalities and rearrangement.Source: Appendix C · p. 15
- The proof interpolates between S_ℓ and S_{ℓ+1} at g(S*) and applies Ψ’s quasiconvexity to bound the resulting value by the better neighboring set.It also uses that Ψ is non-decreasing in its first variable.Source: Appendix C · p. 16
- The output maximizes Ψ(f(S_k),g(S_k)) over the greedy sequence, so it is at least as good as either set bracketing g(S*).The proof locates ℓ with g(S_ℓ)≤g(S*)≤g(S_{ℓ+1}) and compares the maximum over those neighbors with the output.Source: Appendix C · pp. 15–16
Appendix D. Proof of Theorem 3
The proof selects a greedy set near the optimum’s g-value, then uses a candidate element and properties of Ψ to establish the result while retaining knapsack feasibility.
Appendix D. Proof of Theorem 3
- The proof places g(S*) in an ε-sized interval and uses the greedy set at that interval boundary, with a candidate x* chosen by maximum marginal f-to-g ratio.The candidate is selected from elements of S* not already in the greedy set.Source: Appendix D · p. 16
- The proof transfers the neighboring-set argument using that Ψ is non-decreasing in its first variable and non-increasing in its second.It replaces an equality in the earlier proof with an inequality for the candidate-element construction.Source: Appendix D · p. 16
- The selected greedy set satisfies the knapsack constraint because g(S_G)≤bε≤B.The proof uses this feasibility to conclude the desired result.Source: Appendix D · p. 16
Appendix E. Optimality of the approximation when g is modular
The section argues that the 1−1/e approximation factor is optimal when g is modular. It shows that an improved factor would yield an improved algorithm for randomized cardinality-constrained submodular maximization.
Appendix E. Optimality of the approximation when g is modular
- An α>1−1/e approximation for the stated DS problem would give an α-factor solution to randomized cardinality-constrained submodular maximization.The proof constructs this implication using approximate maximizers of f(S_λ′)−λ′|S_λ′|.Source: Appendix E · p. 17
- A linear search defines λ′=h(λ) by maximizing f(S_λ′)−λ|S_λ′| among the described α-approximate maximizers.The search is part of the reduction from the assumed improved approximation algorithm.Source: Appendix E · p. 17
- The function λ↦max_{λ′} f(S_λ′)−λ|S_λ′| is continuous and non-increasing, enabling a binary search for a cardinality threshold.The proof uses the maximizers’ cardinalities at branching points to determine which maximizer dominates as λ changes.Source: Appendix E · p. 17
- The search error can be made smaller than ε, contradicting the claimed optimality of the 1−1/e factor.The contradiction follows from the reduction to the cardinality-constrained problem.Source: Appendix E · p. 17