Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization

1 Introduction

• The problem is to maximize a nonnegative, non-monotone continuous submodular function over the hypercube when its value is accessible only through point queries.Applications include non-concave quadratic programming, DPP map inference, mean-field inference, and revenue maximization over social networks.Source: §1 · p. 2
• A 1/2-approximation matches the best possible guarantee for maximizing a submodular function over the hypercube with polynomially many queries.The algorithm uses polynomially many function queries under mild continuity assumptions.Source: §1 · pp. 2–3
• The first algorithm adapts bi-greedy by choosing each shared coordinate through a zero-sum game whose geometry bounds the game value.The algorithm maintains solutions initialized at 0 and 1, makes them agree one coordinate at a time, and seeks sufficient value gain relative to the optimum at each iteration.Source: §1 · p. 3
• For DR-submodular functions, the paper gives a significantly faster bi-greedy 1/2-approximation based on a monotone equilibrium condition and binary search.DR-submodularity adds concavity along each coordinate; a 1/2-approximation was already known on integer lattices [Soma and Yoshida, 2017].Source: §1 · p. 3
• Experiments report performance matching prior work while providing either a better guaranteed approximation or a better running time.Source: §1 · p. 3
• Some later results require mild technical assumptions on coordinate-wise Lipschitz continuity.This condition concerns the univariate functions obtained by fixing all but one coordinate.Source: §1 · p. 4

2 Weak DR-SM Maximization: Continuous Randomized Bi-Greedy

• The vanilla continuous randomized bi-greedy algorithm achieves a 1/2-approximation for nonnegative continuous submodular functions, up to additive error δ.It assumes black-box access to univariate optimization and envelope-computation oracles; the paper states these can be approximately implemented in polynomial time when F is coordinate-wise Lipschitz.Source: §2 · p. 4

2.1.2 Analyzing the zero-sum games.

• ALG chooses a two-point mixed strategy from the positive-orthant concave envelope, using its intersection with a line to make the adversary’s positive region cover the entire curve.The strategy mixes the two curve points whose convex combination gives the intersection point, ensuring nonnegative expected utility against any adversary strategy.Source: §2 · p. 6, §2.1.2 · p. 9

2.1.1 Reduction to coordinate-wise zero-sum games.

• If ALG’s expected utility is nonnegative against every adversary strategy in each coordinate game, the coordinate-wise guarantees combine to a 1/2-approximation.The utility compares half the combined value increase of X and Y against a bound on the optimum’s decrease; per-game additive slack δ/n sums to δ.Source: §2.1.1 · p. 7

2.1 Analysis of the Continuous Randomized Bi-Greedy (proof of Theorem 1)

• The proof tracks X(i), Y(i), and the optimum as they converge to the algorithm’s final point, then telescopes their value changes to establish the guarantee.The tracked vectors begin at all-zeroes, all-ones, and the optimum, respectively.Source: §2.1 · p. 6, §2.1.1 · p. 7

2.1.2 Analyzing the zero-sum games.

• The curve’s difference d(z) = h(z) − g(z) is monotone non-increasing, a property used to characterize the adversary’s positive region.For the chosen two-point strategy, the paper’s main technical lemma establishes that this region contains the adversary’s strategy point.Source: §2.1.2 · pp. 9–10
• The zero-sum-game analysis establishes curve coverage by showing Q1 lies above h′ = β and Q2 lies to the right of g′ = α.This suffices to cover the upper concave envelope of r with the ADV’s positive region.Source: §2.1.2 · pp. 11–12

2.2 Polynomial-time Implementation under Lipschitz Continuity: Overview

• Under coordinate-wise Lipschitz continuity with constant C, Algorithm 1 has an implementation running in O(n^2/ϵ) time that returns a randomized point.It uses ϵ-spaced samples of univariate projections to approximate optimization and the upper-concave envelope; the sampled maximum is at most ϵC below the actual maximum.Source: §2.2 · p. 12

3 Strong DR-SM Maximization: Binary-Search Bi-Greedy

• Coordinate-wise concavity yields a monotone equilibrium condition, which the algorithm searches for by binary search at each iteration.Monotonicity makes binary search possible when the endpoint conditions require it; the equilibrium condition suffices for the approximation guarantee.Source: §3 · p. 13
• The algorithm deterministically achieves a 1/2-approximation up to O(ϵ) additive error for nonnegative DR-submodular functions, in total time O(n log(n/ϵ)).The theorem assumes coordinate-wise Lipschitz continuity; the binary-search method is restricted to strong DR-SM functions.Source: §3 · p. 13

3.1 Analysis of the Binary-Search Bi-Greedy (proof of Theorem 2)

• The analysis recasts each coordinate choice as a two-player zero-sum game and relates the algorithm's equilibrium condition to the game's value.The proof lower-bounds the game value to establish the approximation guarantee.Source: §3.1 · pp. 14–15
• The proof combines the game-value bound with its lemma to complete the approximation analysis, using coordinate-wise concavity and strong DR-SM properties.Lipschitz continuity links binary-search precision to additive error.Source: §3.1 · pp. 15–16

4 Experimental Results

• The three algorithms obtained very similar objective values across all three experiments, with mean values differing by less than 1 in weak-DR NQP.The weak-DR NQP upper and lower quartiles were about 10 apart.Source: §4 · p. 16, Table 1 · p. 16
• The experiments compared GAME, BINARY, and BMBK on 100-dimensional functions over 20 repeated trials.The application settings were non-concave quadratic programming under strong-DR and weak-DR, and softmax-extension DPP MAP inference.Source: §4 · p. 16
• Figure 2 presents box-and-whisker plots of the experimental results.The prose associates these plots with the three experiments and reports similar objective values for the algorithms.Source: §4 · p. 16, Figure 2 · p. 17

5 Conclusion

• The paper proposes a tight approximation algorithm for continuous submodular maximization and a quasilinear-time tight approximation algorithm for DR-submodular maximization.The experiments verify applicability in practical machine-learning domains.Source: §5 · p. 18
• Generalizing the techniques to arbitrary separable convex sets is identified as future work that could broaden application domains.Source: §5 · p. 18
• The paper's conclusion characterizes the experiments as verifying practical applicability in machine-learning domains.Source: §5 · p. 18

• For continuous, twice-differentiable functions on [0,1]^n, weak DR-SM is equivalent to continuous submodularity and nonpositive off-diagonal Hessian entries.Source: Equivalent definitions of weakly and… · p. 20
• The equivalences are stated for continuous, twice-differentiable functions whose values lie in [0,1] on the hypercube.Source: Equivalent definitions of weakly and… · p. 20
• Strong DR-SM is equivalent to continuous submodularity with coordinate-wise concavity, or equivalently to all Hessian entries being nonpositive.Source: Equivalent definitions of weakly and… · p. 20

Strong-DR Non-concave Quadratic Programming (NQP)

• The Strong-DR NQP experiment draws H entries uniformly from [−1, 0], symmetrizes H, draws h from [0, +1]^n, and sets c so F(0) + F(1) = 0.Source: Strong-DR Non-concave Quadratic… · p. 20

Weak-DR Non-concave Quadratic Programming (NQP)

• The Weak-DR NQP experiment changes the diagonal entries of H to uniform draws from [0, +1], making F weak DR-submodular.The passage describes this as the same experiment as the preceding subsection apart from the diagonal-entry distribution.Source: Weak-DR Non-concave Quadratic… · p. 20

Softmax extension of Determinantal Point Processes (DPP)

• The DPP instances use F(x) = log det(diag(x)(L − I) + I), with L generated as a positive semidefinite matrix having specified eigenvalues.The eigenvalues are obtained by exponentiating uniform draws from [−0.5, 1.0], and L is formed using a random unitary matrix.Source: Softmax extension of Determinantal… · p. 21

Special Class of Non-Concave Quadratic Programming (NQP)

• Quadratic submodular objectives model communication-system and MIMO detection problems, while demand-forecasting price optimization is described as weak-DR minimization.Source: More application domain details · p. 21

Revenue Maximization over Social Networks

• In social-network revenue maximization, fractional trial-product assignments yield a non-monotone Weak DR-submodular objective that is nonnegative at 0 and 1.The objective combines nonnegative, nondecreasing revenue from buyers without free products with nonpositive, nonincreasing revenue from recipients.Source: More application domain details · p. 21

Map Inference for Determinantal Point Processes (DPP) & Its Softmax-Extension

• DPP MAP inference maximizes log det(AS) over feasible sets; its non-monotone submodular objective requires det(A) ≥ 1 for the stated bi-greedy algorithms.DPPs are also used as generative models for text summarization, human pose estimation, and news threading.Source: More application domain details · pp. 21–22
• The softmax extension is Strong DR-submodular and non-monotone; regularizing the log-likelihood with λ∥x∥2 can yield a Weak DR-submodular problem when λ is large enough.The extension uses an independent distribution with marginals x; some prior approaches need fractional solutions in conv(P), which can take optimization outside the hypercube and complicate rounding.Source: More application domain details · p. 22

Log-Submodularity and Mean-Field Inference

• Mean-field inference approximates a log-submodular distribution p(S) ∼ exp(f(S)) with a product distribution, and its objective H(x) − E[log p(S)] is Strong DR-submodular.Source: More application domain details · p. 22

Cone Extension of Continuous Submodular Maximization

• For a proper cone K, K-DR-submodularity extends DR-submodularity; logistic regression with a particular non-separable, non-convex regularizer is given as an application.Adding a K-ℓ2-norm regularizer λ∥Ax∥2 makes the function Weak DR-submodular; A has generators of K as columns.Source: More application domain details · pp. 22–23

More application domain details

• For several machine-learning objectives, Strong- or Weak-DR functions may fail positivity or F(0) + F(1) ≥ 0; adding a positive constant can fix this, but weakens the multiplicative guarantee.The paper notes that this adjustment tends to work in practice because the algorithms tend to be near optimal.Source: More application domain details · p. 23