PaperlayerView exact revision on arXiv

Source-linked AI summary

Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains

Andrew An Bian, Baharan Mirzasoleiman, Joachim M. Buhmann, Andreas Krause

arXiv:1606.05615v5cs.LGcs.DS

TL;DR

The paper asks how generally non-convex and non-concave submodular continuous functions can be characterized and maximized efficiently. It introduces weak DR for a unified characterization and proposes two approximation algorithms, obtaining guarantees for monotone and non-monotone settings. Experiments on real-world applications report that the proposed methods outperform baselines.

  • Problem

    The paper addresses tractable optimization of generally non-convex and non-concave submodular continuous functions across continuous domains.

  • Method

    The paper introduces weak DR and develops a Frank-Wolfe variant and a DoubleGreedy algorithm for constrained continuous submodular maximization.

  • Results

    The proposed methods achieve (1 - 1/e) and 1/3 approximation guarantees in their respective constrained monotone and non-monotone settings, and outperform baselines in experiments.

  • Takeaways & Limitations

    Continuous submodularity supplies structural characterizations and approximation algorithms applicable to budget allocation, revenue maximization, and multi-resolution summarization.

  • Takeaways & Limitations

    The monotone down-closed-polytope problem is NP-hard and cannot be approximated within (1 - 1/e + ϵ) in polynomial time unless RP = NP.

Abstract

from arXiv · show

Submodular continuous functions are a category of (generally) non-convex/non-concave functions with a wide spectrum of applications. We characterize these functions and demonstrate that they can be maximized efficiently with approximation guarantees. Specifically, i) We introduce the weak DR property that gives a unified characterization of submodularity for all set, integer-lattice and continuous functions; ii) for maximizing monotone DR-submodular continuous functions under general down-closed convex constraints, we propose a Frank-Wolfe variant with $(1-1/e)$ approximation guarantee, and sub-linear convergence rate; iii) for maximizing general non-monotone submodular continuous functions subject to box constraints, we propose a DoubleGreedy algorithm with $1/3$ approximation guarantee. Submodular continuous functions naturally find applications in various real-world settings, including influence and revenue maximization with continuous assignments, sensor energy management, multi-resolution data summarization, facility location, etc. Experimental results show that the proposed algorithms efficiently generate superior solutions compared to baseline algorithms.

1. Introduction

The paper studies submodular continuous functions, which are generally non-convex and non-concave, and develops approximation algorithms for efficiently maximizing them. It introduces a unified characterization and two guaranteed maximization approaches.

  • Submodularity, traditionally associated with set functions, has applications in variable selection, dictionary learning, sparsity, summarization, and variational inference.
  • The paper extends submodular optimization from discrete and lattice domains to continuous functions, addressing both maximization and characterization.
  • The weak DR property provides a necessary and sufficient diminishing-returns characterization across set, integer-lattice, and continuous functions.
  • A Frank-Wolfe and continuous-greedy-based method achieves a (1 - 1/e) approximation for monotone DR-submodular functions under general down-closed convex constraints.
  • A coordinate-ascent-style DoubleGreedy method achieves a 1/3 approximation for arbitrary submodular continuous functions under box constraints.

2. Background and related work

Prior work established submodular optimization across discrete, lattice, and selected continuous settings, while non-convex optimization broadly seeks tractable guarantees. This paper positions continuous submodular maximization as a general problem and claims efficient algorithms with strong guarantees.

  • Submodularity provides computational structure that makes many discrete optimization problems efficiently solvable or approximable.
  • Prior results include a deterministic 1/3 approximation and randomized 1/2 approximation for unconstrained non-monotone submodular set-function maximization.
  • Continuous submodular work previously covered special monotone piecewise-linear concave functions, multilinear extensions, minimization, and discretization-based approaches.
  • Non-convex optimization research includes tensor methods, stationary-point analysis, and assumptions such as star-convexity, gradient dominance, or nice-function structure.
  • The paper claims to be the first to address general monotone and non-monotone submodular maximization over continuous domains and to provide strong approximation guarantees.

3. Characterizations of submodular continuous functions

The paper develops structural characterizations of submodular continuous functions and relates weak DR, DR-submodularity, coordinate-wise concavity, and Hessian conditions. These results unify discrete, lattice, and continuous viewpoints while distinguishing DR-submodularity as a stricter class.

  • Submodular continuous functions are defined over product domains whose coordinates may be finite sets, integer lattices, or intervals.
  • For twice-differentiable functions, submodularity is characterized by nonpositive off-diagonal Hessian entries.
  • Submodular continuous functions include convex, concave, and indefinite quadratic examples, so the class is generally neither convex nor concave.
  • The DR property requires diminishing returns under coordinate increases, and differentiable DR-submodular functions have antitone gradients.
  • The weak DR property is equivalent to submodularity for set, integer-lattice, and continuous functions.
  • DR-submodularity is stronger than weak DR; it is equivalent to submodularity together with coordinate-wise concavity.
  • For twice-differentiable functions, DR-submodularity requires all Hessian entries, including diagonal entries, to be nonpositive.

4. Maximizing monotone DR-submodular continuous functions

The section presents a Frank-Wolfe variant for monotone DR-submodular maximization over down-closed convex constraints, with approximation guarantees and sub-linear convergence despite NP-hardness.

  • 4. Maximizing monotone DR-submodular continuous functions: The problem maximizes a monotone DR-submodular continuous function over a general down-closed convex constraint in the positive orthant.The formulation includes a lower bound and can be translated to the positive orthant without loss of generality.
  • 4. Maximizing monotone DR-submodular continuous functions: The guarantee is essentially tight because no polynomial-time algorithm can achieve (1 − 1/e + ε) for the corresponding polytope-constrained problem unless RP = NP.The hardness result applies to maximizing monotone DR-submodular continuous functions subject to a general down-closed polytope constraint.
  • 4. Maximizing monotone DR-submodular continuous functions: Algorithm 1 uses a Frank-Wolfe variant that linearizes f and moves toward a surrogate maximizer.Its update direction is v_k rather than the conventional v_k − x_k.
  • 4. Maximizing monotone DR-submodular continuous functions: DR-submodularity makes f concave along non-negative and non-positive directions, supporting the algorithm’s nonstandard update direction.The associated one-dimensional function g_x,v(ξ) is concave for non-negative directions.
  • 4. Maximizing monotone DR-submodular continuous functions: The analysis assumes Lipschitz continuity of the derivative of the one-dimensional auxiliary function to control nonlinearity and approximation error.This assumption yields a quadratic bound relating function improvement to the linearized gain.
  • 4. Maximizing monotone DR-submodular continuous functions: (1 − 1/e) is the error-free worst-case guarantee as the constant stepsize tends to zero, and the method has a sub-linear convergence rate.The algorithm reaches an ε-close solution in O(1/ε) iterations in the error-free case.

5. Maximizing non-monotone submodular continuous functions

The section addresses non-monotone submodular continuous maximization under box constraints with a DoubleGreedy procedure based on coordinate-wise one-dimensional optimization.

  • 5. Maximizing non-monotone submodular continuous functions: The target problem maximizes a generally non-monotone submodular continuous function over a box constraint.The setting includes applications such as revenue maximization with continuous assignments and multi-resolution summarization.
  • 5. Maximizing non-monotone submodular continuous functions: The DoubleGreedy algorithm provides a 1/3-approximation and performs coordinate-ascent on two solutions.It is inspired by discrete double greedy methods.
  • 5. Maximizing non-monotone submodular continuous functions: The method starts with x_0 = u and y_0 = ū, then processes coordinates in an arbitrary order through paired one-dimensional subproblems.At each coordinate, it evaluates the marginal gains of optimizing the corresponding coordinate in each solution.
  • 5. Maximizing non-monotone submodular continuous functions: Each iteration updates both solutions toward the candidate with the larger local marginal gain, and the two solutions meet after n iterations.The procedure tolerates additive error δ in each one-dimensional subproblem.
  • 5. Maximizing non-monotone submodular continuous functions: The guarantee assumes submodularity, f(u) + f(ū) ≥ 0, and approximate solvability of the one-dimensional subproblems.The proof bounds objective loss between consecutive iterations and then across all n iterations.
  • 5. Maximizing non-monotone submodular continuous functions: O(n ∗ cost_1D) is the time complexity, and one-dimensional subproblems are usually cheap; non-convex/non-concave quadratic programs have closed-form solutions.The algorithm’s approximation guarantee includes an additive error term proportional to δ for each one-dimensional subproblem.

6. Examples of submodular continuous objective functions

The paper instantiates submodular continuous objectives across budget allocation, revenue maximization, sensor energy management, summarization, facility location, and related problems. These models use continuous assignments or scales while retaining submodular structure, including monotone DR-submodularity and non-monotone submodularity.

  • Optimal budget allocation: Continuous budget allocation distributes advertising resources across channels or advertisers to maximize expected customer influence under assignment and budget constraints.The resulting objective is monotone DR-submodular.
  • Revenue maximization with continuous assignments: Revenue maximization models product assignments to users through gains from free trials and losses during trial periods, producing a generally non-convex/non-concave, non-monotone submodular objective.The model is subject to box constraints and can be approximately maximized with DoubleGreedy.
  • Sensor energy management: Sensor energy management chooses continuous energy levels so sensors detect contamination events quickly, with the expected saved detection time forming a monotone DR-submodular objective.Cost constraints determine the feasible energy assignments.
  • Multi-resolution summarization: Multi-resolution summarization assigns nonnegative item scores and obtains summaries at user-selected thresholds instead of selecting one fixed discrete set.Items whose scores exceed threshold τ form the resulting summary.
  • Facility location: Facility location extends facility decisions to continuous scales, with each customer served by its highest-value facility and total service represented by a monotone submodular function.Facility scale lies in the interval [0, ¯u].

7. Experimental results

Experiments evaluate the Frank-Wolfe variant and DoubleGreedy on synthetic quadratic programs and real-world influence and revenue tasks. The proposed methods generally outperform baselines, while ProjGrad is sensitive to step-size selection and cannot be applied to the non-smooth revenue objective.

  • Monotone maximization: 50 iterations are used for both Frank-Wolfe and ProjGrad in the monotone experiments covering synthetic NQP and influence maximization.Figure 2 varies constraint parameters and advertising budgets.
  • Monotone maximization: Frank-Wolfe outperforms the other baselines on Yahoo! Search Marketing influence maximization across advertising-volume and advertiser-budget settings.ProjGrad performance highly depends on the chosen step size.
  • Non-monotone maximization: DoubleGreedy shows strong approximation performance on non-monotone NQP as upper bounds vary, whereas ProjGrad depends on step size and matches it only with careful tuning.The NQP experiment averages results over 20 repeated experiments.
  • Non-monotone maximization: DoubleGreedy outperforms other baselines on YouTube revenue experiments across upper bounds and parameter combinations, while SingleGreedy obtains lower utility.The dataset contains the top 500 largest YouTube communities.
  • Non-monotone maximization: The revenue objective is generally non-smooth and discontinuous at points containing zero, so subgradient-based ProjGrad comparison is unavailable.The subdifferential can be empty.

8. Conclusion

The paper characterizes submodular continuous functions and develops guaranteed algorithms for maximizing them. Its conclusion reports a (1 −1/e)-approximation for monotone DR-submodular maximization and a 1/3-approximation for non-monotone maximization, with experiments outperforming baselines.

  • Conclusion: The paper proposes a (1 −1/e)-approximation algorithm for monotone DR-submodular continuous functions under general down-closed convex constraints.This is the monotone optimization guarantee reported in the conclusion.
  • Conclusion: The paper proposes a 1/3-approximation algorithm for non-monotone submodular continuous functions subject to box constraints.This is the non-monotone optimization guarantee reported in the conclusion.
  • Conclusion: The experiments cover budget allocation, revenue maximization, and non-convex/non-concave quadratic programming, with proposed methods outperforming baselines in all experiments.The conclusion presents these results as evidence for guaranteed optimization in continuous settings.
  • Conclusion: The weak DR property is introduced as an equivalent characterization of submodularity across set, integer-lattice, and continuous functions.The paper’s proof section develops equivalent formulations of weak DR.

A.2 Proof of Proposition 1

The proof establishes equivalence between weak DR and submodularity, then uses this result to relate DR-submodularity to coordinate-wise concavity. It proceeds by translating lattice inequalities into submodular comparisons and summing coordinate-wise bounds.

  • Weak DR equivalence: Submodularity implies the weak DR inequality by applying the lattice inequality to x = l′χi + b and y = k′χi + a.The coordinate-wise meet and join become l′χi + a and k′χi + b.
  • Weak DR equivalence: Weak DR implies submodularity by increasing coordinates one at a time from x ∧y to y and from x to x ∨y.Summing the resulting inequalities yields the submodular inequality.
  • DR-submodularity characterization: Submodularity together with coordinate-wise concavity implies DR-submodularity through a comparison of shifted one-coordinate increments.The proof uses submodularity to establish inequality (12) after applying coordinate-wise concavity.
  • DR-submodularity characterization: DR-submodularity implies weak DR and therefore submodularity, while setting b := a+lχi yields coordinate-wise concavity.Thus DR-submodularity is connected to both properties used in the characterization.

B.1 Proof of Proposition 3

The proof reduces continuous monotone DR-submodular maximization to monotone submodular set-function maximization, then transfers NP-hardness and the 1−1/e inapproximability bound.

  • Π1 is monotone submodular set-function maximization under cardinality constraints, while Π2 is monotone DR-submodular continuous maximization over down-closed polytopes.
  • A polynomial-time algorithm for Π1 uses polynomially many calls to an algorithm for Π2.
  • The reduction maximizes a multilinear extension over the associated matroid polytope, then rounds the fractional solution using pipage rounding.
  • Π2 is NP-hard because Π1 is NP-hard and the reduction transfers solutions between the two problems.
  • 1−1/e is an inapproximability threshold for Π2 unless RP = NP.
  • The proof of the approximation analysis uses concavity along a nonnegative direction and the down-closedness and monotonicity of the feasible problem.

C.1 Proof of Proposition 5

The proof reduces unconstrained non-monotone set-function maximization to box-constrained continuous maximization and analyzes DoubleGreedy through coordinate-wise updates and objective-loss bounds.

  • Π1 is unconstrained non-monotone submodular set-function maximization, while Π2 is box-constrained non-monotone submodular continuous maximization.
  • The multilinear extension evaluates the expected set-function value under independent element selection with probabilities given by x.
  • The reduction maximizes the multilinear extension over [0,1]^E and returns a random set whose expected value equals the continuous solution value.
  • The reduction transfers hardness from unconstrained non-monotone submodular set-function maximization to the continuous problem.
  • DoubleGreedy analysis: DoubleGreedy alternates coordinate updates of x and y according to the larger marginal choice, with an equivalent two-step formulation used for analysis.
  • DoubleGreedy analysis: The proof bounds objective loss across 2n intermediate updates by comparing each intermediate solution with an optimal reference vector.
  • Application model: The revenue model combines nonnegative submodular revenue components with a modular component, yielding a submodular objective.

D.2 Proof of Lemma 2

The proof establishes submodularity of the application objective by decomposing it into submodular and modular components, while also handling a nonsmooth one-dimensional optimization subproblem.

  • The function g is shown submodular using monotonicity of the nonnegative submodular components and the lattice inequality.
  • A second component h is shown submodular using the non-increasing behavior of its constituent functions.
  • The full objective is submodular because it is the sum of two submodular functions and one modular function.
  • One-dimensional optimization: For x_j>0, the one-dimensional subproblem is concave and smooth, but the objective is nonsmooth and discontinuous at x_j=0.
  • One-dimensional optimization: The one-dimensional solver maximizes the smooth extension and compares its optimum with the value at x_j=0.
  • Applications: Continuous maximum coverage uses confidence levels under a budget constraint, producing a monotone submodular objective over a down-closed polytope.
  • Applications: Continuous-confidence text summarization models covered concepts with a monotone submodular continuous objective.
Loading 1606.05615v5…