PaperlayerView exact revision on arXiv

Source-linked AI summary

Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications

Christopher Harshaw, Moran Feldman, Justin Ward, Amin Karbasi

arXiv:1904.09354v1cs.DScs.LGmath.OC

TL;DR

Discrete machine-learning objectives often use submodularity, but extending optimization guarantees to broader function classes remains challenging. This paper studies utility minus cost and gives algorithms, hardness results, and experimental evidence, including reported improvements over greedy heuristics.

  • Problem

    Submodular optimization techniques can perform arbitrarily poorly when objectives are not submodular, motivating study of broader function classes for discrete machine-learning tasks.

    Source: §1 · p. 1

  • Method

    The paper optimizes a monotone, non-negative γ-weakly submodular utility minus a non-negative modular cost using fast algorithms and a surrogate objective that changes the relative importance of utility and cost.

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

  • Results

    The paper reports matching value-oracle hardness and experimental results in which its algorithms outperform the greedy heuristic on Bayesian A-Optimality with costs and directed vertex cover with costs.

    Source: §6 · p. 26

  • Takeaways & Limitations

    The results support using utility-minus-cost objectives for cardinality-constrained and unconstrained optimization when utility is monotone, non-negative, and γ-weakly submodular and cost is non-negative modular.

    Source: §1 · p. 2, §6 · p. 26

    The guarantees apply to a non-negative monotone γ-weakly submodular utility and a non-negative modular cost.

    Source: §1 · p. 2

Abstract

from arXiv · show

It is generally believed that submodular functions -- and the more general class of $\gamma$-weakly submodular functions -- may only be optimized under the non-negativity assumption $f(S) \geq 0$. In this paper, we show that once the function is expressed as the difference $f = g - c$, where $g$ is monotone, non-negative, and $\gamma$-weakly submodular and $c$ is non-negative modular, then strong approximation guarantees may be obtained. We present an algorithm for maximizing $g - c$ under a $k$-cardinality constraint which produces a random feasible set $S$ such that $\mathbb{E} \left[ g(S) - c(S) \right] \geq (1 - e^{-\gamma} - \epsilon) g(OPT) - c(OPT)$, whose running time is $O (\frac{n}{\epsilon} \log^2 \frac{1}{\epsilon})$, i.e., independent of $k$. We extend these results to the unconstrained setting by describing an algorithm with the same approximation guarantees and faster $O(\frac{n}{\epsilon} \log\frac{1}{\epsilon})$ runtime. The main techniques underlying our algorithms are two-fold: the use of a surrogate objective which varies the relative importance between $g$ and $c$ throughout the algorithm, and a geometric sweep over possible $\gamma$ values. Our algorithmic guarantees are complemented by a hardness result showing that no polynomial-time algorithm which accesses $g$ through a value oracle can do better. We empirically demonstrate the success of our algorithms by applying them to experimental design on the Boston Housing dataset and directed vertex cover on the Email EU dataset.

1 Introduction

The paper studies maximizing a monotone, non-negative γ-weakly submodular utility minus a non-negative modular cost, a setting where existing techniques lack nontrivial guarantees. It presents fast algorithms, a matching value-oracle hardness result, and experimental validation.

1 Introduction

  • Submodularity is useful for discrete machine-learning objectives because it encodes diminishing returns and has established optimization techniques.The introduction cites applications including sensor placement, summarization, speech subset selection, influence maximization, information gathering, and image segmentation.Source: §1 · p. 1
  • Existing techniques lack nontrivial guarantees for g(S) − c(S), which may be negative and non-monotone even when g is monotone and non-negative.The paper formulates the objective with γ-weakly submodular g and non-negative modular cost c; costs can model penalties, regularizers, soft constraints, or item costs.Source: §1 · p. 2
  • The paper gives algorithms for cardinality-constrained and unconstrained maximization, including randomized variants and a method for unknown γ.For known γ, the deterministic cardinality-constrained algorithm guarantees g(S) − c(S) ≥ (1 − e^−γ)g(OPT) − c(OPT); randomized variants incur an additive ε loss in the approximation factor.Source: §1 · p. 2
  • No algorithm making polynomially many value-oracle queries to g can improve on the stated approximation guarantees.The authors describe this as the first hardness result of this kind for γ-weakly submodular functions.Source: §1 · p. 2
  • The algorithms are experimentally evaluated on experimental design with Boston Housing data and directed vertex cover with Email EU data, both with costs.Source: §1 · p. 2
  • Earlier work on g + ℓ for monotone submodular g gave a randomized cardinality-constrained guarantee, but its continuous optimization and OPT-contribution guessing made it practically intractable.A later surrogate-objective approach removed the guessing step, but still required expensive sampling and did not handle γ-weakly submodular functions.Source: §1 · p. 3

2 Preliminaries

The preliminaries define marginal gain, monotonicity, submodularity, weak submodularity, and modularity, then specify the value-oracle model used for runtime analysis.

2 Preliminaries

  • The marginal gain of adding e to S is g(e | S) = g(S ∪ {e}) − g(S), and monotonicity means g(A) ≤ g(B) whenever A ⊆ B.Source: §2 · p. 3
  • Submodularity formalizes diminishing returns: an element’s marginal gain does not increase as the current set grows.The equivalent formulation bounds the combined gain from adding a set by the sum of its individual marginals.Source: §2 · p. 3
  • A monotone function is γ-weakly submodular when the sum of marginals bounds the gain from adding a set up to the submodularity ratio γ; γ = 1 recovers submodularity.Source: §2 · pp. 3–4
  • A modular cost is additive over elements and is non-negative exactly when all its coefficients are non-negative.The algorithms use a value oracle that returns g(S), and runtime is measured by the number of function evaluations.Source: §2 · p. 4

3 Algorithms

The algorithms optimize a changing distorted objective that initially weights cost more heavily and increases utility’s relative importance over time. Random sampling and a geometric sweep extend the approach to faster variants and unknown γ.

3 Algorithms

  • The distorted objective changes over the algorithm’s trajectory, initially emphasizing modular cost more and gradually increasing the relative weight of utility.The paper says this design is intended to avoid getting stuck in poor local optima; randomized subsampling provides further computational speedups.Source: §3 · p. 4

3.1 Distorted Greedy

  • Distorted Greedy selects the element with the largest distorted-objective increase and accepts it only when its contribution is positive; it uses O(nk) evaluations and returns a set of size at most k.Source: §3.1 · pp. 4, 6

3.2 Stochastic Distorted Greedy

  • Stochastic Distorted Greedy searches a random sample instead of the full ground set, using O(n log(1/ε)) evaluations.The sampling analysis uses the chance that the sample contains an optimal element to obtain sufficient potential gain in expectation.Source: §3.2 · p. 7

3.3 Unconstrained Distorted Greedy

  • Unconstrained Distorted Greedy samples one random element per iteration and requires O(n) function evaluations.Its analysis works with the average gain directly, rather than showing that the best element beats an average element.Source: §3.3 · pp. 10–11

3.4 Guessing Gamma: A Geometric Sweep

  • When γ is unknown, γ-Sweep runs the algorithm at geometrically decreasing guesses and returns the best set, preserving nearly the known-γ guarantees.A known lower bound on γ reduces the number of guesses; the sweep loses an additive δ factor in the approximation ratio.Source: §3.4 · pp. 11–12
  • For k = 5, 10, and 20, Stochastic Distorted Greedy with γ-Sweep usually has higher average objective values and greater variation than Distorted Greedy with γ-Sweep.The paper suggests subsampling may help avoid a single bad element, while variation means additional γ guesses can produce a good solution; Figure 1 reports SDG means and standard-deviation bars over 20 trials.Source: §3.4 · p. 13, Figure 1 · p. 13

4 Hardness Result

This section establishes a value-oracle hardness threshold for cardinality-constrained monotone γ-weakly submodular maximization, including when c = 0. The proof bounds f∅(S) and specifies when fT agrees with f∅ or equals 1.

4 Hardness Result

  • For every ε > 0 and γ ∈ (0, 1], no polynomial-time value-oracle algorithm achieves a (1 − e^-γ + ε)-approximation for cardinality-constrained monotone nonnegative γ-weakly submodular maximization.The proof establishes the bound first for γ-weakly DR functions, which are also γ-weakly submodular.Source: §4 · pp. 13–14
  • Proposition 14 constructs nonnegative monotone γ-weakly DR functions f_T on a ground set of size ⌈3k/ε′⌉, bounded by 1 and attaining 1 at T when |T| = k.For |S| ≤ k, f_∅(S) ≤ 1 − e^-γ + 12ε′; f_T(S) = f_∅(S) when |S| ≥ 3k − g or |S ∩ T| ≤ g.Source: §4 · p. 14
  • A random hidden k-element set yields hard instances: polynomially many queries almost always match a baseline function, leaving deterministic and randomized algorithms with expected value at most 1 − e^-γ + ε.The construction makes f_T agree with f_∅ with high probability on each queried set; Yao’s principle extends the deterministic lower bound to randomized algorithms.Source: §4 · pp. 15–16

4.1 Proof of Proposition 14

  • For every |S| ≤ k, the constructed baseline satisfies f_∅(S) ≤ 1 − e^-γ + 8ε′.This bound proves the construction’s baseline-value property used in the hardness argument.Source: §4.1 · p. 19
  • f∅(S) ≤ 1 − e^-γ + 8ε′.This follows by combining the preceding bounds in the proof of Proposition 14.Source: §4.1 · p. 20
  • When |S ∩ T| ≤ g, fT and f∅ agree on S.Under this condition, tT(S) = |S| = t∅(S).Source: §4.1 · p. 20
  • The passage states that fT(S) = 1 − fT,1(S) · fT,2(S) · fT,3(S) = 1, so the supported result is simply fT(S) = 1.Source: §4.1 · p. 20

5 Experiments

Across two cost-aware applications, the algorithms improved constrained results, while unconstrained comparisons ranged from a greedy win to similar performance.

5.1 Bayesian A-Optimal Design

  • Claim 29 establishes the Bayesian A-optimal design utility as non-negative, monotone, and γ-weakly submodular.Source: §5.1 · p. 22
  • For Bayesian A-optimal design, the implementation updates the matrix inverse using the matrix inversion lemma, improving code efficiency.This avoids repeatedly constructing and inverting the matrix when computing marginal gains.Source: §5.1 · pp. 23–24
  • On Boston Housing, the proposed methods improved on greedy for non-extreme cost penalties, but greedy outperformed the proposed method in the unconstrained instance.For fixed α = 0.8, greedy reached a local maximum at k = 7, while the proposed methods found higher-objective solutions; stochastic Distorted Greedy performed better for larger k.Source: Figure 2 · p. 24, §5.1 · p. 25

5.2 Directed Vertex Cover with Costs

  • At q = 6, Distorted Greedy led across cardinalities, stochastic Distorted Greedy used fewer g evaluations at k = 130, and unconstrained performance was similar to greedy.The evaluation used directed vertex cover on the EU Email Core network.Source: §5.2 · pp. 25–26, Figure 3 · p. 26

6 Conclusion

The paper presents fast algorithms for maximizing a monotone, non-negative γ-weakly submodular function minus a non-negative modular cost, with matching oracle hardness and experiments where the algorithms outperform greedy.

6 Conclusion

  • The paper presents fast algorithms for both cardinality-constrained and unconstrained maximization of a non-negative monotone γ-weakly submodular function minus a non-negative modular cost.It also gives a matching hardness result: no algorithm can do better with only polynomially many oracle queries to g.Source: §6 · p. 26
  • Experiments on Bayesian A-Optimality with costs and directed vertex cover with costs show that the algorithms outperform the greedy heuristic.Source: §6 · p. 26
  • The paper does not report CPU time for this experiment because its behavior differs from the number of function evaluations.The passage attributes this difference to the implementation of the data structure used to store lazy evaluations.Source: §6 · p. 26

A Greedy Performs Arbitrarily Poorly

A directed-star instance with non-negative costs illustrates how greedy can choose a bad vertex first, terminate, and perform arbitrarily poorly under a cardinality constraint.

A Greedy Performs Arbitrarily Poorly

Related papers

Loading 1904.09354v1…