PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal approximation for submodular and supermodular optimization with bounded curvature

Maxim Sviridenko, Jan Vondrák, Justin Ward

arXiv:1311.4728v3cs.DS

TL;DR

The paper studies approximation of submodular maximization and supermodular minimization under a matroid constraint when curvature is bounded. It develops modified continuous-greedy methods and reductions to a general submodular-plus-linear objective, while establishing matching value-oracle lower bounds.

  • Problem

    Curvature measures how far a submodular function is from linear, motivating improved approximation guarantees for matroid-constrained optimization.

  • Method

    The paper modifies continuous greedy and reduces both bounded-curvature optimization problems to maximizing a nonnegative, nondecreasing submodular function plus a possibly negative linear function.

  • Results

    No polynomial-value-query algorithm can achieve a (1 −ce−1 + δ)-approximation for monotone submodular maximization with curvature at most c, even under a cardinality constraint.

  • Takeaways & Limitations

    The approximation guarantees are optimal among algorithms using only a polynomial number of function evaluations, including for uniform matroids.

  • Takeaways & Limitations

    For supermodular minimization, the result requires curvature c to be bounded away from 1 by a constant.

Abstract

from arXiv · show

We design new approximation algorithms for the problems of optimizing submodular and supermodular functions subject to a single matroid constraint. Specifically, we consider the case in which we wish to maximize a nondecreasing submodular function or minimize a nonincreasing supermodular function in the setting of bounded total curvature $c$. In the case of submodular maximization with curvature $c$, we obtain a $(1-c/e)$-approximation --- the first improvement over the greedy $(1-e^{-c})/c$-approximation of Conforti and Cornuejols from 1984, which holds for a cardinality constraint, as well as recent approaches that hold for an arbitrary matroid constraint. Our approach is based on modifications of the continuous greedy algorithm and non-oblivious local search, and allows us to approximately maximize the sum of a nonnegative, nondecreasing submodular function and a (possibly negative) linear function. We show how to reduce both submodular maximization and supermodular minimization to this general problem when the objective function has bounded total curvature. We prove that the approximation results we obtain are the best possible in the value oracle model, even in the case of a cardinality constraint. We define an extension of the notion of curvature to general monotone set functions and show $(1-c)$-approximation for maximization and $1/(1-c)$-approximation for minimization cases. Finally, we give two concrete applications of our results in the settings of maximum entropy sampling, and the column-subset selection problem.

1 Introduction

The paper develops curvature-sensitive approximation algorithms for submodular maximization and supermodular minimization under matroid constraints, improves prior guarantees, and establishes matching value-oracle hardness results. It also extends curvature-based guarantees to general monotone functions and gives applications to maximum entropy sampling and column-subset selection.

  • 1.1 Our Contribution: (1 − c/e − O(ε))-approximation improves the prior (1 − e^−c)/c guarantee for nondecreasing submodular maximization under any matroid constraint.The result improves the cardinality-constraint guarantee of Conforti and Cornuéjols and the corresponding arbitrary-matroid result.
  • 1.1 Our Contribution: Two techniques achieve the submodular guarantee: a modified continuous greedy algorithm and a variant of non-oblivious local search.
  • 1.1 Our Contribution: (1 + c/(1 − c) O(ε))-approximation is obtained for nonincreasing supermodular minimization under a matroid constraint, improving existing algorithms except at c = 0 and c = 1.The paper plots the relevant maximization and inverse minimization ratios for comparison.
  • 1.1 Our Contribution: Polynomial-query value-oracle algorithms cannot achieve better approximation guarantees, even under a cardinality constraint.The hardness results cover both curvature-bounded submodular maximization and supermodular minimization.
  • 1.1 Our Contribution: Bounded curvature alone yields (1 − c)-approximation for maximizing and 1/(1 − c)-approximation for minimizing general monotone functions under a matroid constraint.The stronger submodular and supermodular guarantees require the respective structural assumptions.
  • 1.2 Applications: The applications include maximum entropy sampling and column-subset selection, where curvature connects to matrix eigenvalues or the condition number.For column-subset selection, the resulting approximation factor is κ^2.

2 Preliminaries

This section defines submodularity, supermodularity, monotonicity, matroid notation, and curvature-related lemmas used in the paper’s analyses.

  • Submodular functions have decreasing marginal values, while supermodular functions have increasing marginal values.
  • Monotone increasing functions have nonnegative marginals, whereas monotone decreasing functions have nonpositive marginals.
  • Matroids: A matroid consists of a ground set and independent sets; its bases are inclusion-wise maximal independent sets.
  • Matroids: The dual matroid’s bases are complements of the original matroid’s bases, and restriction retains only independent sets contained in a specified subset.
  • Bounded curvature: Two curvature lemmas relate bounded curvature to monotone submodular maximization and monotone supermodular minimization under matroid constraints.

3 Submodular + Linear Maximization

The paper introduces a matroid-constrained meta-problem: maximize a nonnegative monotone submodular function plus a possibly negative linear function over a base.

  • The meta-problem maximizes g(S) + ℓ(S) over a matroid base, allowing the linear function ℓ to take negative values.
  • The functions’ singleton values bound every set value by n·v̂, enabling efficient computation of the relevant scale parameter.
  • For every ε > 0, the main theorem provides a polynomial-time algorithm producing a base satisfying its stated joint approximation guarantee for every comparison base.
  • The paper presents two algorithms for the meta-problem: modified continuous greedy and modified non-oblivious local search.

4 A Modified Continuous Greedy Algorithm

The modified continuous greedy algorithm approximately maximizes a monotone submodular function plus a possibly negative linear function over a matroid polytope.

  • Algorithm design: The algorithm modifies continuous greedy by requiring directions that satisfy both a linear-value threshold and a residual submodular-value threshold.
  • Algorithm design: The multilinear extension represents set-function values as expectations over independently sampled random subsets.
  • Analysis: The discretized solution remains feasible because it is a convex combination of matroid-polytope points, while the analysis separately tracks linear and submodular gains.
  • Rounding and guarantee: Pipage rounding preserves the combined objective guarantee even when the linear component may be negative.
  • Implementation: The implementation guesses ℓ(O), estimates the multilinear-extension gradient by sampling, solves a linear program, and discretizes time with δ = ε/n^2.

5 Non-Oblivious Local Search

The second approach uses non-oblivious local search with an auxiliary potential to jointly optimize the submodular and linear components over matroid bases.

  • Overview: Unlike modified continuous greedy, modified local search neither guesses ℓ(O) nor solves the associated continuous optimization problem.
  • Matroid exchanges: Matroid basis exchange supplies feasible single-element swaps used to compare the current base with an arbitrary base.
  • Potential function: The method evaluates local improvements using an auxiliary potential h derived from g and a modified potential ψ combining h with ℓ.
  • Approximation analysis: If no single-element exchange significantly improves ψ, the analysis guarantees relatively high values for both g(S) and ℓ(S).
  • Implementation: The algorithm estimates the potential by sampling, requires additive improvement δ = ε/(n·v̂), and bounds the number of improvements to obtain polynomial-time convergence.
  • Guarantee: With high probability, the resulting locally optimal solution satisfies the approximation guarantee established by the main theorem.

6 Submodular Maximization and Supermodular Minimization

The section reduces bounded-curvature submodular maximization and supermodular minimization over matroids to optimizing a nonnegative monotone submodular function plus a linear function. It establishes polynomial-time approximation guarantees for both settings, with a curvature-dependent boundary near c=1 for minimization.

  • 6.1 Submodular Maximization: The reduction represents the objective using a nonnegative monotone submodular function g and a linear function ℓ.This representation enables application of the section’s general optimization theorem.
  • 6.1 Submodular Maximization: Submodular maximization with curvature c admits a polynomial-time approximation guarantee stated in Theorem 6.1.The guarantee holds for every ε > 0 and every matroid constraint, with high probability.
  • 6.2 Supermodular Minimization: Supermodular minimization with curvature c admits a polynomial-time approximation guarantee stated in Theorem 6.2.The guarantee applies to monotone decreasing supermodular functions over matroids and holds with high probability.
  • 6.2 Supermodular Minimization: The minimization reduction optimizes g(S) + ℓ(S) = −f(X \ S) in the dual matroid, using complements of bases.Because the linear term is nonpositive, the analysis uses partial enumeration to bound the relevant scale parameter.
  • 6.2 Supermodular Minimization: The minimization result requires curvature c to be bounded away from 1 by a constant.The stated reason is that the error term depends on 1−c.

7 Inapproximability Results

The section proves that the paper’s curvature-dependent approximation guarantees cannot be improved with only polynomially many value-oracle evaluations. The hardness already holds under a cardinality constraint, via transformations preserving monotonicity, curvature, and submodular or supermodular structure.

  • 7.3 Optimality: The resulting guarantees are optimal in the value-oracle model even for the special case of a uniform matroid.The lower bounds use only polynomially many function evaluations as the computational resource being restricted.
  • 7.1 Submodular Maximization: No polynomial-query algorithm achieves a (1 − c/e + δ)-approximation for monotone increasing submodular maximization under a cardinality constraint.This is stated for every constant δ > 0 and c ∈ (0, 1).
  • 7.1 Submodular Maximization: The hardness constructions transform cardinality-constrained submodular instances into bounded-curvature objectives while preserving monotonicity and submodularity.The transformed function is shown to be monotone increasing, submodular, nonnegative, and of curvature at most c.
  • 7.2 Supermodular Minimization: A complementary transformation yields a monotone decreasing, supermodular, nonnegative function of curvature at most c for minimization hardness.Each evaluation of the transformed function requires only one evaluation of the original function, enabling the contradiction with the cardinality lower bound.

8 Optimizing Monotone Nonnegative Functions of Bounded Curvature

The section extends bounded-curvature optimization to arbitrary monotone functions under a matroid constraint and establishes greedy-based guarantees and matching oracle lower bounds.

  • Generalized curvature: A generalized curvature notion applies to arbitrary monotone increasing or decreasing nonnegative functions, without requiring submodularity or supermodularity.The framework considers maximization for increasing functions and minimization for decreasing functions under a single matroid constraint.
  • Greedy algorithms: The standard greedy maximization algorithm repeatedly adds the feasible element with largest marginal gain, while minimization selects the feasible element with smallest marginal gain.Both procedures terminate at a matroid base.
  • Reduction for decreasing functions: Monotone decreasing objectives are handled by complementing sets, producing f*(S) = f(X \ S), which preserves monotonicity and curvature.The transformed problem can be solved on the dual matroid using standard greedy maximization or minimization.
  • Approximation guarantees: 1 − c and 1/(1 − c) are the approximation factors for maximization and minimization, respectively, and are best possible as functions of curvature.The corresponding results apply to monotone increasing and decreasing functions under matroid constraints.
  • Oracle optimality: Polynomial-query algorithms cannot improve these curvature-dependent guarantees, even for cardinality-constrained instances.The maximization lower bound uses a hidden random optimal set whose identity is not revealed by polynomially many queries.

9 Application: the Column-Subset Selection Problem

The column-subset selection problem is formulated as minimizing projection error over a fixed number of matrix columns, and its curvature is linked to the matrix condition number.

  • Problem formulation: Column-subset selection chooses k columns of A to minimize the squared Frobenius projection error f_A(S).The nearest matrix whose columns lie in the span of the selected columns is obtained by projecting every column onto that span.
  • Problem formulation: The objective f_A is non-increasing, making column-subset selection a special case of non-increasing minimization under a cardinality constraint.Adding columns cannot increase the projection residual.
  • Curvature analysis: For nonsingular A, the curvature of f_A is controlled by the condition number κ(A), because marginal projection errors vary by at most a factor related to κ^2(A).The proof compares residual components orthogonal to the span of selected columns with norms of matrix products.
  • Approximation guarantee: κ^2(A)-approximation is obtained for column-subset selection using the standard greedy minimization algorithm.This follows by applying the bounded-curvature minimization guarantee to f_A.
  • Tightness: The curvature-condition-number relationship is asymptotically tight: some matrices with condition number κ have curvature 1 − O(1/κ^2).The construction uses one canonical-basis column and remaining columns perturbed by a common component.

A Proofs and Claims Omitted from the Main Body

The appendix supplies reductions that convert bounded-curvature submodular and supermodular objectives into nonnegative monotone submodular functions plus linear terms, preserving the relevant curvature bounds.

  • Supporting inequalities: For bounded-curvature submodular objectives, the appendix establishes inequalities relating total function value to sums of marginal values.These inequalities support the reductions used by the approximation framework.
  • Submodular reduction: For a monotone increasing submodular f, subtracting a linear function of full-set marginals yields a nonnegative monotone increasing submodular function.The construction is used to separate the linear component from the original objective.
  • Supermodular reduction: For a monotone decreasing supermodular f, complementing the set and subtracting an appropriate linear term produces a nonnegative monotone increasing submodular function.The resulting function is submodular, monotone increasing, and nonnegative by supermodularity.
  • Curvature-preserving construction: Adding a nonnegative linear term to a monotone increasing nonnegative submodular function preserves submodularity, monotonicity, nonnegativity, and bounded curvature.The construction increases marginals by a curvature-dependent linear contribution.
  • Curvature-preserving construction: The analogous complement-based construction for decreasing objectives is supermodular, decreasing, nonnegative, and has curvature at most c.Its value at the full ground set is zero, supporting nonnegativity.
Loading 1311.4728v3…