PaperlayerView exact revision on arXiv

Source-linked AI summary

Constrained Submodular Maximization via New Bounds for DR-Submodular Functions

Niv Buchbinder, Moran Feldman

arXiv:2311.01129v1cs.DScs.DM

TL;DR

The paper addresses the gap between the 0.385 current-best approximation for non-negative non-monotone submodular maximization over a general down-closed solvable polytope and the 0.478 inapproximability bound [49]. The paper designs FW-guided-MCG and proves a new DR-submodular damage bound that improves on the previous bound of. 0.401 approximation is obtained for non-negative submodular and DR-submodular maximization over the stated convex constraints.

  • Problem

    The paper addresses the gap between the 0.385 current-best approximation for non-negative non-monotone submodular maximization over a general down-closed solvable polytope and the 0.478 inapproximability bound [49].

  • Method

    The paper designs FW-guided-MCG and proves a new DR-submodular damage bound that improves on the previous bound of.

  • Results

    0.401 approximation is obtained for non-negative submodular and DR-submodular maximization over the stated convex constraints.

  • Takeaways & Limitations

    The new bound reduces the gap to the 0.478 inapproximability result and may support further applications and improvements.

  • Takeaways & Limitations

    The main theorem is restricted to meta-solvable down-closed convex bodies, while broader solvable bodies yield only almost-feasible extensions.

Abstract

from arXiv · show

Submodular maximization under various constraints is a fundamental problem studied continuously, in both computer science and operations research, since the late $1970$'s. A central technique in this field is to approximately optimize the multilinear extension of the submodular objective, and then round the solution. The use of this technique requires a solver able to approximately maximize multilinear extensions. Following a long line of work, Buchbinder and Feldman (2019) described such a solver guaranteeing $0.385$-approximation for down-closed constraints, while Oveis Gharan and Vondrák (2011) showed that no solver can guarantee better than $0.478$-approximation. In this paper, we present a solver guaranteeing $0.401$-approximation, which significantly reduces the gap between the best known solver and the inapproximability result. The design and analysis of our solver are based on a novel bound that we prove for DR-submodular functions. This bound improves over a previous bound due to Feldman et al. (2011) that is used by essentially all state-of-the-art results for constrained maximization of general submodular/DR-submodular functions. Hence, we believe that our new bound is likely to find many additional applications in related problems, and to be a key component for further improvement.

1 Introduction

The paper develops a solver for non-negative submodular and DR-submodular maximization over down-closed convex constraints, improving the approximation ratio to 0.401. Its analysis uses a new DR-submodular damage bound that strengthens prior guarantees and applies through multilinear extensions.

  • 1 Introduction: The approach relaxes feasibility to a convex body, approximately maximizes the multilinear extension fractionally, and then rounds the solution with bounded loss.Rounding is lossless for matroid polytopes and incurs arbitrarily small constant loss for a constant number of knapsack constraints.
  • 1 Introduction: For non-monotone objectives under down-closed constraints, the previous best approximation was 0.385, while no algorithm can exceed 0.478 even for partition-matroid polytopes [49].Down-closedness is necessary for constant-factor approximation in the general setting, although many natural constraints satisfy it.
  • 1.1 Our Contribution: Multilinear extensions of submodular set functions are DR-submodular, so the continuous optimization result yields improved submodular maximization algorithms.A corollary gives a polynomial-time 0.401-approximation under a matroid constraint or a constant number of knapsack constraints.
  • 1.1 Our Contribution: 0.401 approximation is achieved for maximizing non-negative DR-submodular functions over meta-solvable down-closed convex bodies, up to an O(δD^2L) error term.The algorithm runs in polynomial time in |N| and δ^-1.
  • 1.2 Techniques and Paper Structure: The novel FW-guided-MCG algorithm is a continuous-greedy method whose analysis uses a stronger damage bound that accounts for all directions previously used to increase the solution.The bound is always at least as strong as the earlier bound of and is strictly stronger in most cases.

2 Preliminaries

This section defines the vector operations, DR-submodular objectives, and meta-solvable down-closed feasible regions used throughout the paper. It also summarizes algorithmic components, including local search, Frank-Wolfe optimization, and a generalized Double-Greedy procedure.

  • Vector operations: The paper uses coordinate-wise maximum, minimum, product, inner product, and probabilistic sum operators, with a⊕b = 1−(1−a)⊙(1−b).The probabilistic sum is symmetric and associative, so it extends naturally to multiple vectors.
  • The objective function: DR-submodularity means diminishing coordinate-wise returns, equivalently an antitone gradient for differentiable functions; multilinear extensions satisfy this property.For twice differentiable functions, it is also characterized by the Hessian condition stated in the paper.
  • Useful properties: DR-submodularity supplies concavity along non-negative directions and gradient inequalities that bound changes in F using inner products.The listed properties also relate coordinate-wise joins, meets, probabilistic sums, and products.
  • Problem definition: The studied problem maximizes a non-negative differentiable DR-submodular function over a meta-solvable down-closed convex body P, with optimal solution o and diameter D.The function is assumed evaluable together with its derivatives, and F(o)>0 excludes the trivial case.
  • Algorithmic components: The algorithmic toolkit includes approximate local maximization, a Frank-Wolfe variant that does not require knowing smoothness L, and generalized Double-Greedy procedures.The generalized Double-Greedy method uses O(n log(nε^-1)) function evaluations and does not require Lipschitz continuity.
  • Algorithmic components: Box-Maximization produces a vector y ≤ x with a guaranteed value for a non-negative DR-submodular function, supporting the paper’s broader optimization framework.The construction relies on the DR-submodular lower bound associated with the generalized Double-Greedy procedure.

3 Our Algorithm

The section presents FW-guided-MCG and embeds it in a recursive algorithm that returns the best candidate across recursive levels. Its analysis guarantees a successful recursive call and establishes polynomial running time for fixed auxiliary parameters.

  • 3 Our Algorithm: The recursive algorithm applies Box-Maximization and FW-guided-MCG at each level, then returns the vector maximizing F among all produced z′ and y vectors.Each unsuccessful heir call supplies a vector x(j) to a deeper recursive call.
  • 3 Our Algorithm: The algorithm uses 1 + ⌈2/ε⌉ recursion levels and has polynomial running time in |N| and δ^-1 for constant ε.The full running-time bound follows because each call is polynomial and the recursion depth is constant for fixed ε.
  • 3.1 Proof of Theorem 1.1: At least one recursive call is successful, so the algorithm obtains a candidate satisfying the successful FW-guided-MCG outcome.The proof uses the bounded recursion depth and non-negativity of F to show that unsuccessful heir calls cannot continue through every level.
  • 3.1 Proof of Theorem 1.1: The analysis combines lower bounds for the successful call's y∗ and z′∗ outputs, and any convex combination of those bounds lower-bounds the final output.The parameters α, ts, and sufficiently small constant ε are chosen to obtain the theorem's final guarantee.

4 New Bounds for DR-Submodular Functions

The section develops two sets of new DR-submodular bounds: stylized bounds for continuous-time analysis and analogous bounds tailored to discrete-time algorithms.

  • 4 New Bounds for DR-Submodular Functions: The paper proves novel DR-submodular bounds in two forms, one for continuous-time analysis and one designed for discrete-time algorithms.The discrete-time bounds can be viewed as analogs of the continuous-time bounds, but are more natural for discrete-time algorithms.
  • 4.1 Bounds Designed for Continuous Time Algorithms: Lemma 4.1 gives a basic bound for a non-negative DR-submodular function, an integrable trajectory x, and a vector a.Its proof proceeds by induction on a finite truncation of the bound and then uses monotone convergence.
  • 4.1 Bounds Designed for Continuous Time Algorithms: Lemma 4.2 generalizes Lemma 4.1 to multiple vector arguments by constructing an auxiliary function G on disjoint copies of the ground set.The proof verifies that G remains non-negative and DR-submodular before applying the basic bound.

5 Our Main Algorithmic Component (FW-guided-MCG)

FW-guided-MCG continuously grows a feasible solution by selecting local-maximizing directions within a dynamically defined convex body. Its analysis establishes feasibility and guarantees either a strong solution or a locally maximal vector with reduced value after combining continuous and discrete-time arguments.

  • Guarantee: The continuous-time algorithm outputs y ∈ P and x(τ) ∈ P such that either y satisfies the theorem’s guarantee or some x(τ) is locally maximal with respect to o and has reduced F(x(τ) ⊕ o).Theorem 5.1 applies to non-negative DR-submodular F over a meta-solvable down-closed convex body P.
  • Algorithm: FW-guided-MCG grows y(τ) continuously, choosing each direction as a local maximum inside the convex body Q(τ).Q(τ) is defined so every selected direction increases F(y(τ)) at a rate of at least V(τ) − F(y(τ)).
  • Analysis: When Q(τ) is nonempty throughout, the analysis derives lower bounds on F(y(τ)) over both time ranges, including the bound at τ = t_s.The first-range bound at t_s is F(y(t_s)) ≥ (1 − e^-t_s) · F(o) − (1 − e^-t_s) · F(z ⊙ o) − (1 − (1 + t_s)e^-t_s) · F(z ⊕ o).
  • Analysis: If Q(τ) becomes empty, there is a later τ′ ∈ [t_s, 1) where x(τ′) is locally maximal with respect to o and F(x(τ′) ⊕ o) ≤ F(z ⊕ o) − ε · F(o).The algorithm still defines x(τ) by selecting an arbitrary vector in P whenever Q(τ) is empty.
  • Discrete Time Version: The implementable discrete-time version returns y ∈ P and vectors x(1), …, x(m) ∈ P, with m = O(δ^-1 + ε^-1), satisfying the corresponding local-maximum or reduced-value alternative.For constant t_s and ε, its running time is Poly(|N|, δ^-1).

6 Concluding Remarks

The paper achieves a 0.401 approximation for non-negative submodular and DR-submodular maximization over convex constraints, surpassing 0.4 and narrowing the gap to the 0.478 inapproximability bound. The techniques may yield slightly better guarantees in selected settings, but the stated improvements are limited.

  • The result significantly reduces the gap between the state-of-the-art approximation ratio and the 0.478 inapproximability bound.
  • Allowing FW-guided-MCG to use ratio-dependent t_s improves the guarantee only in the fourth decimal place.
  • For some convex bodies, running FW-guided-MCG beyond time 1 can yield a somewhat improved guarantee.

A Technical Details of Proving Theorem 1.2

The proof of Theorem 1.2 transfers the main algorithm to multilinear extensions by approximating function values and derivatives and by controlling the extension's smoothness. A new polynomial smoothness bound follows under a down-closed convex-body assumption that every singleton vector is feasible.

  • Theorem 1.2 requires sampling to approximate both the multilinear extension and its derivatives because only the set function is directly available.
  • The error term δD^2L is made negligible by polynomial bounds on the polytope diameter D and smoothness parameter L.
  • The multilinear extension of a non-negative submodular function is L-smooth with L = 2|N| · M.
  • The singleton-vector assumption is without loss of generality because infeasible singleton elements can be removed without changing the optimum.
  • If P is down-closed and contains every singleton vector 1_u, then L ≤ 2|N|^2 · max_{S⊆N,1_S∈P} f(S).

B Frank-Wolfe Variant

The Frank-Wolfe variant constructs feasible iterates by repeatedly optimizing a linearization over the convex body and taking small convex-combination steps. For L-smooth DR-submodular functions, this yields an approximate stationarity guarantee with an additional smoothness-dependent error term.

  • Theorem 2.4 outputs x ∈ P such that ⟨y − x, ∇F(x)⟩ ≤ δ[max_{y′∈P} F(y′) + D^2L/2] for every y ∈ P.
  • All iterates remain in P because each update is a convex combination of points in the convex body.
  • Each iteration chooses z^(i) maximizing the linear objective ⟨y, ∇F(x^(i−1))⟩ over P and sets x^(i) to a δ-weighted convex combination with z^(i).
  • For DR-submodular F, the stationarity inequality implies a bound involving F(x ∨ y) + F(x ∧ y) and the same smoothness error term.

C Algorithm for Unconstrained DR-Submodular Maximization

The unconstrained DR-submodular algorithm is a continuous Double-Greedy procedure that starts from 0 and 1, aligns one coordinate per iteration, and returns a common solution. Its function-access cost is O(n log(nε^-1)), using concavity and binary search for coordinate updates.

  • The discretized coordinate choices approximate the continuous maxima within an additive 2ε error.
  • Algorithm 5 starts x at 0 and y at 1, then makes one coordinate agree per iteration until both vectors coincide.
  • O(n log(nε^-1)) function evaluations suffice to implement the entire algorithm.
  • Each coordinate subproblem is concave in its scalar step, so binary search finds a maximizing discretized value in O(log(nε^-1)) evaluations.
  • The analysis tracks a hybrid vector o^(i) that transitions from the comparator o to the algorithm's final common solution.

D Guessing the Necessary Values

The proof constructs a constant-size set of triples guaranteed to contain values satisfying Lemma 5.12. It first guesses the optimal value geometrically, then builds compatible sets for the remaining values using down-closedness and DR-submodularity.

  • D Guessing the Necessary Values: A constant-size set G of non-negative triples is guaranteed to contain a triple satisfying Lemma 5.12, with size depending only on ε.The construction combines guesses for g, g⊙, and g⊕.
  • D Guessing the Necessary Values: An approximate value v with c · F(o) ≤ v ≤ F(o) enables a geometric-guess set Go whose size depends only on ε and c.The proof obtains v by running any constant-approximation algorithm for maxx∈P F(x).
  • D Guessing the Necessary Values: The geometric sequence contains a guess g satisfying g ≤ F(o) while its predecessor is at least F(o), establishing the required bounds for g.The sequence starts at v/c ≥ F(o) and reaches v ≤ F(o).
  • D Guessing the Necessary Values: Given g, polynomial-time constructions produce constant-size sets G⊙(g) and G⊕(g) containing values satisfying the lemma’s respective inequalities.The G⊕ construction replaces Inequality (15) with F(z ⊙ o) ≤ F(o), using down-closedness of P.
Loading 2311.01129v1…