PaperlayerView exact revision on arXiv

Source-linked AI summary

Black Box Submodular Maximization: Discrete and Continuous Settings

Lin Chen, Mingrui Zhang, Hamed Hassani, Amin Karbasi

arXiv:1901.09515v2cs.LGcs.DSmath.OCstat.ML

TL;DR

Constrained continuous DR-submodular maximization is challenging when gradients are difficult or inaccessible and projections are expensive. The paper proposes Black-box Continuous Greedy, extending it to stochastic and discrete settings. It establishes tight approximation guarantees and reports similar practical utility to Continuous Greedy with greater evaluation efficiency.

  • Problem

    The paper addresses constrained continuous DR-submodular maximization when gradients are difficult or inaccessible and projection operations may be computationally prohibitive.

    Source: §1 · p. 2

  • Method

    Black-box Continuous Greedy uses only function values and combines zeroth-order information with linear programs, with extensions to stochastic and discrete settings.

    Source: §1 · p. 2, §4 · p. 7

  • Results

    BCG achieves the tight [(1 − 1/e)OPT −ϵ] guarantee with O(d/ϵ3) evaluations deterministically and O(d3/ϵ5) evaluations in the stochastic continuous setting.

    Source: §1 · p. 2

  • Takeaways & Limitations

    On synthetic and real data, BCG practically achieves the same utility as Continuous Greedy while using substantially fewer function evaluations.

    Source: §6 · p. 11

    More recent variance-reduction techniques might reduce the required number of function evaluations.

    Source: §1 · p. 3

Abstract

from arXiv · show

In this paper, we consider the problem of black box continuous submodular maximization where we only have access to the function values and no information about the derivatives is provided. For a monotone and continuous DR-submodular function, and subject to a bounded convex body constraint, we propose Black-box Continuous Greedy, a derivative-free algorithm that provably achieves the tight $[(1-1/e)OPT-\epsilon]$ approximation guarantee with $O(d/\epsilon^3)$ function evaluations. We then extend our result to the stochastic setting where function values are subject to stochastic zero-mean noise. It is through this stochastic generalization that we revisit the discrete submodular maximization problem and use the multi-linear extension as a bridge between discrete and continuous settings. Finally, we extensively evaluate the performance of our algorithm on continuous and discrete submodular objective functions using both synthetic and real data.

1 Introduction

The introduction motivates derivative-free optimization for constrained continuous DR-submodular maximization, where gradients can be costly or inaccessible and projection can be prohibitive. It presents Black-box Continuous Greedy and its continuous, stochastic, and discrete extensions as zeroth-order alternatives.

1 Introduction

  • BCG combines zeroth-order information with linear programs, avoiding projections that can be computationally prohibitive for constraints such as flow or matroid polytopes.The focus is constrained continuous DR-submodular maximization over a bounded convex body.Source: §1 · p. 2
  • BCG achieves the tight [(1 − 1/e)OPT −ϵ] guarantee with O(d/ϵ3) function evaluations for deterministic continuous maximization.The setting is a monotone continuous DR-submodular function over a bounded convex body.Source: §1 · p. 2
  • The stochastic continuous and discrete variants retain the tight [(1 − 1/e)OPT −ϵ] guarantee with O(d3/ϵ5) and O(d5/ϵ5) function evaluations, respectively.The discrete result is for Discrete Black-box Greedy (DBG).Source: §1 · pp. 2–3
  • In discrete maximization, the theoretical query bound is larger than the cited best-known O(d5/2/ϵ3) bound, although experiments report often fewer evaluations and less running time at practically similar utility.The comparison is attributed to Mokhtari et al. [2018a,b].Source: §1 · p. 3
  • Earlier constrained DR-submodular methods assumed (stochastic) gradients, while this work provides a first rigorous analysis using only (stochastic) function values.The smoothing-based unbiased gradient estimator has O(d2/δ2) variance, which may cause Frank-Wolfe-type methods to diverge; the approach builds on a momentum method.Source: §1 · p. 3
  • Transforming the domain and constraint set lets the zeroth-order method avoid evaluating outside the domain near its boundary while retaining O(T −1/3) convergence.This addresses the vanilla smoothing trick's failure when perturbed points fall outside domains such as the unit cube.Source: §1 · p. 3

1.1 Further Related Work

  • The introduction identifies a gap in prior work: to the authors' knowledge, no existing work had developed a zeroth-order algorithm for maximizing monotone continuous DR-submodular functions.Related work includes first-order methods and bandit maximization.Source: §1.1 · p. 4

2 Preliminaries

The preliminaries define discrete and continuous submodularity through diminishing returns and introduce DR-submodularity as a stronger continuous property. They also explain how smoothing preserves useful structure while enabling gradient estimation from function values.

  • A submodular set function has diminishing returns: adding an element to a set gives at least as much gain as adding it to a superset.Source: §2 · p. 4
  • A continuous submodular function satisfies a lattice inequality on pairs of points, using component-wise maximum and minimum.Source: §2 · p. 4
  • A DR-submodular function has coordinatewise nonincreasing gradients and is concave along nonnegative directions.Source: §2 · p. 4
  • A function is monotone when its value does not decrease as its input increases coordinatewise.Source: §2 · p. 4
  • Averaging the function over a radius-δ ball produces a smoothed version that preserves monotonicity and submodularity under the stated Lipschitz condition.A single function query can provide an unbiased estimate of the smoothed function's gradient.Source: §2 · p. 4

3 DR-Submodular Maximization

The section develops a derivative-free continuous greedy method for constrained DR-submodular maximization, using function evaluations and variance reduction. It also extends the method to noisy evaluations and addresses domain-boundary issues introduced by smoothing.

  • The method targets constrained optimization over a convex compact set using linear optimization steps rather than projection operations.The section notes that Frank-Wolfe-style updates avoid the projection oracle.Source: §3 · p. 5
  • Black-box Continuous Greedy estimates the smoothed objective's gradient from function queries, then uses two-point minibatch estimates and momentum to reduce variance.The momentum estimate is biased, but its error approaches zero over time.Source: §3 · pp. 5–6
  • Shrinking the domain by δ keeps smoothing queries inside the original domain, and translating the constraint set yields a feasible region for optimization.The smoothed and original optima are close when δ is sufficiently small.Source: §3 · p. 5
  • O(d/ε^3) function evaluations suffice for O(ε) error with T=O(1/ε^3), B_t=d, and δ=ε/d in the deterministic setting.Source: §3 · p. 6
  • O(d^3/ε^5) noisy function evaluations suffice for O(ε) error with T=O(1/ε^3), B_t=d^3/ε^2, and δ=ε/d.The noisy oracle is assumed unbiased with uniformly bounded variance.Source: §3 · p. 7

4 Discrete Submodular Maximization

The discrete method applies Black-box Continuous Greedy to the multilinear extension of a monotone submodular set function under a matroid constraint. It estimates extension values by sampling sets and provides an evaluation bound for the resulting algorithm.

  • The multilinear extension expresses the set function's expected value when each element is independently included with probability x_i, and is monotone and DR-submodular.Source: §4 · p. 7
  • Matroid-constrained discrete optimization is bridged to continuous optimization over the matroid polytope, with lossless rounding recovering a feasible set whose expected value is at least the fractional objective.Source: §4 · p. 7
  • The algorithm estimates extension values by sampling random sets and evaluating the set function, rather than computing the exact expectation over all subsets.Source: §4 · p. 8
  • O(d^5/ε^5) evaluations suffice for O(ε) error with T=O(d^3/ε^3), B_t=1, l=d^2/ε^2, and δ=ε/d.Source: §4 · p. 8

5 Experiments

The experiments compare BCG and DBG with zeroth- and first-order baselines on continuous and discrete submodular tasks. Across the tasks, the proposed methods trade function value that is comparable to first-order methods for lower running time and, in discrete settings, fewer function evaluations.

Non-convex/non-concave Quadratic Programming (NQP)

  • On the synthetic 100-dimensional non-convex/non-concave quadratic program, BCG’s value is only slightly below SCG’s and similar to ZGA’s.The quadratic objective uses a 100-by-100 random matrix with entries distributed as the negated absolute value of a standard normal.Source: §5 · p. 9

Summary

  • At least twice faster than SCG and ZGA in all tasks, BCG/DBG’s running-time comparisons are normalized to BCG or DBG, respectively.Figure 2 covers the first two continuous tasks and last two discrete tasks.Source: Figure 2 · p. 10, §5 · p. 11

Topic Summarization

  • BCG’s topic-summarization value matches SCG and exceeds ZGA and GA, and BCG is the most efficient method in that experiment.The task selects articles from 120 Reuters-21578 articles represented by 10 topics.Source: §5 · pp. 9–10

Running Time

  • Projection-based ZGA and GA take significantly more time than projection-free BCG, DBG, and SCG, while zeroth-order methods are faster than first-order counterparts.The paper attributes the difference to quadratic optimization for projections versus linear optimization, and to faster zeroth-order evaluations.Source: §5 · p. 11

Summary

  • DBG requires remarkably fewer function evaluations in discrete tasks; it outperforms ZGA but is slightly worse than SCG and GA on active set selection and influence maximization.SCG and GA require significantly more function value queries in these tasks.Source: §5 · pp. 10–11
  • BCG/DBG achieve objective values comparable to SCG and GA while saving function evaluations.BCG/DBG run notably faster with only slightly inferior function values in three tasks; topic summarization has similar objective values for BCG, SCG, and GA.Source: §5 · p. 11

Running Time

  • Although SCG needs only half as many first-order queries as BCG, BCG runs significantly faster because zeroth-order evaluations are faster.The runtime comparison concerns the continuous experiments in Figures 2a and 2b.Source: §5 · p. 11

6 Conclusion

The paper presents BCG for monotone continuous DR-submodular maximization under a general convex body constraint, with a tight approximation guarantee and O(d/ϵ^3) function evaluations. It extends the approach to stochastic continuous and discrete submodular maximization, and reports experiments on synthetic and real data.

Conclusion

  • BCG is derivative-free and projection-free, and achieves the tight [(1 − 1/e)OPT −ϵ] guarantee with O(d/ϵ^3) function evaluations.The target is maximizing a monotone continuous DR-submodular function under a general convex body constraint.Source: §6 · p. 11

A Proof of Lemma 1

The proof shows that the smoothed function ˜F retains monotonicity and continuous DR-submodularity. This preserves the structural properties needed in the argument.

A Proof of Lemma 1

  • The proof concludes that ˜F is monotone continuous DR-submodular, with non-increasing gradients across ordered points.The preceding statements establish differentiability and compare function and gradient values for ordered points.Source: A Proof of Lemma 1 · p. 17

B Proof of Theorem 1

The proof of Theorem 1 invokes variance-reduction lemmas and uses monotone DR-submodular structure in its argument. It also verifies that the final iterate, after an additive adjustment, satisfies the constraint.

B Proof of Theorem 1

  • Theorem 1’s proof draws on variance-reduction lemmas, including a stated slight improvement over earlier lemmas.The cited earlier works are [Shamir, 2017, Chen et al., 2018b] and [Mokhtari et al., 2018a] and [Mokhtari et al., 2018b].Source: B Proof of Theorem 1 · p. 17
  • The final iterate x_(T+1) + δ1 resides in the constraint K because x_(T+1) is a convex combination of feasible vectors in K − δ1.The proof also establishes that the iterates are nonnegative and nondecreasing.Source: B Proof of Theorem 1 · p. 18
  • The proof uses that ˜F is monotone continuous DR-submodular, concave along non-negative directions, and has entry-wise nonnegative gradients.These properties are invoked in the subsequent inequality argument.Source: B Proof of Theorem 1 · p. 18

C Proof of Theorem 2

The proof uses unbiasedness and Lemma 4 to bound the estimator’s conditional mean-squared error, then follows the proof of Theorem 1 to derive a bound.

C Proof of Theorem 2

  • The proof invokes unbiasedness of ˆF and Lemma 4 to establish the conditional error bound.Source: C Proof of Theorem 2 · p. 21
  • The estimator’s conditional mean-squared error is bounded by a gradient-estimation term and two noise terms proportional to d²σ0²/(4δ²).The derivation conditions on the prior filtration and the sampled direction.Source: C Proof of Theorem 2 · p. 21
  • The remaining argument is described as similar to the proof of Theorem 1 and concludes with a bound involving Q and Bt.Source: C Proof of Theorem 2 · p. 22

D Proof of Lemma 3

The proof addresses Lipschitz properties of the multilinear extension, using multilinearity to examine its gradients.

D Proof of Lemma 3

E Proof of Theorem 3

The proof of Theorem 3 uses z_t = x_t + δ1 and combines intermediate bounds, including one that relies on lossless rounding.

E Proof of Theorem 3

Loading 1901.09515v2…