PaperlayerView exact revision on arXiv

Source-linked AI summary

Gradient Methods for Submodular Maximization

Hamed Hassani, Mahdi Soltanolkotabi, Amin Karbasi

arXiv:1708.03949v2cs.LGmath.OC

TL;DR

The paper studies how to maximize continuous submodular functions despite their nonconvexity, especially when objectives are stochastic and constraints are convex. It analyzes projected gradient and mirror methods and proves approximation guarantees for monotone DR-submodular objectives. Fixed points achieve a 1/2 approximation, while stochastic methods reach OPT/2 − ε in O(1/ε^2) iterations, with experiments demonstrating effectiveness on real data.

  • Problem

    The paper asks whether projected gradient methods can provide provably good solutions for continuous submodular maximization with general convex constraints despite nonconcavity.

  • Method

    The paper analyzes projected gradient, stochastic gradient, and mirror methods for stochastic continuous submodular objectives over bounded convex sets.

  • Results

    Fixed points of projected gradient ascent provide a 1/2 approximation, while stochastic gradient and mirror methods achieve OPT/2 − ε in O(1/ε^2) iterations.

  • Takeaways & Limitations

    The framework applies projected methods to stochastic submodular optimization and connects discrete monotone submodular problems to continuous relaxations.

  • Takeaways & Limitations

    The stated iteration bounds can become impractical when smoothness depends on the ambient dimension, and the paper primarily studies convex constraints.

Abstract

from arXiv · show

In this paper, we study the problem of maximizing continuous submodular functions that naturally arise in many learning applications such as those involving utility functions in active learning and sensing, matrix approximations and network inference. Despite the apparent lack of convexity in such functions, we prove that stochastic projected gradient methods can provide strong approximation guarantees for maximizing continuous submodular functions with convex constraints. More specifically, we prove that for monotone continuous DR-submodular functions, all fixed points of projected gradient ascent provide a factor $1/2$ approximation to the global maxima. We also study stochastic gradient and mirror methods and show that after $\mathcal{O}(1/ε^2)$ iterations these methods reach solutions which achieve in expectation objective values exceeding $(\frac{\text{OPT}}{2}-ε)$. An immediate application of our results is to maximize submodular functions that are defined stochastically, i.e. the submodular function is defined as an expectation over a family of submodular functions with an unknown distribution. We will show how stochastic gradient methods are naturally well-suited for this setting, leading to a factor $1/2$ approximation when the function is monotone. In particular, it allows us to approximately maximize discrete, monotone submodular optimization problems via projected gradient descent on a continuous relaxation, directly connecting the discrete and continuous domains. Finally, experiments on real data demonstrate that our projected gradient methods consistently achieve the best utility compared to other continuous baselines while remaining competitive in terms of computational effort.

1 Introduction

The paper asks whether projected gradient methods can reliably maximize continuous submodular functions despite nonconvexity, and answers affirmatively under general convex constraints. It establishes approximation guarantees for deterministic, stochastic, and weakly DR-submodular settings.

  • Problem and framework: Projected gradient methods provide competitive solutions for monotone, smooth, weakly DR-submodular functions over bounded convex bodies.The paper studies stochastic objectives formed from continuous submodular functions under generally unknown distributions.
  • Main guarantees: All stationary points of a DR-submodular function over K provide a 1/2 approximation to the global maximum.Consequently, sufficiently small-step projected gradient ascent has the same 1/2 guarantee.
  • Main guarantees: O(L2/ε^2) projected gradient iterations produce an objective value exceeding OPT/2 − ε.Here, L2 measures smoothness in the ℓ2 norm.
  • Main guarantees: O(L* / ε^2) projected mirror-ascent iterations produce a solution exceeding OPT/2 − ε, using smoothness measured in a potentially better norm.The relevant smoothness parameter can be substantially smaller in norms such as ℓ1 than in ℓ2.
  • Extensions: For weakly DR-submodular functions with parameter γ, the approximation guarantee becomes γ^2/(1 + γ^2).The special case γ = 1 corresponds to ordinary submodular functions.
  • Stochastic applications: Stochastic projected gradient methods remain stable in expectation and provide a 1/2 guarantee for unknown-distribution submodular objectives.The framework also applies to general monotone submodular set functions through continuous relaxations.

2 Continuous submodular maximization

The paper extends submodularity from sets to continuous domains using lattice and diminishing-returns formulations. Continuous submodular functions are generally neither convex nor concave, while DR-submodularity supplies the structure used for optimization guarantees.

  • Continuous submodularity: A continuous submodular function satisfies a lattice inequality involving componentwise maxima and minima.This formulation includes set functions and integer-lattice functions as special cases.
  • Continuous submodularity: For twice-differentiable functions, continuous submodularity is equivalent to non-positive cross-second derivatives.This condition captures diminishing returns across distinct coordinates.
  • Geometry: Continuous submodular functions are generally neither convex nor concave, although some functions can satisfy submodularity together with either property.Affine functions are simultaneously submodular, convex, and concave.
  • DR-submodularity: DR-submodularity strengthens submodularity by requiring diminishing returns when increasing a coordinate from smaller vectors rather than larger ones.For differentiable DR-submodular functions, the gradient is an antitone mapping.
  • Weak DR-submodularity: For differentiable DR-submodular functions, the weak-submodularity parameter satisfies γ = 1.The paper uses γ to generalize its guarantees to weakly DR-submodular functions.
  • Problem setting: The paper focuses on monotone weakly DR-submodular functions over general bounded convex sets, not necessarily down-closed sets.The feasible set has bounded diameter R.

3 Background and related work

Submodular optimization connects discrete combinatorial structure with continuous extensions, enabling approximate maximization despite nonconvexity. Prior work established strong guarantees for multilinear extensions under polytope constraints and reductions for integer-lattice variants.

  • Applications: Submodular set functions originated in combinatorial optimization and now support applications across machine learning.Applications include viral marketing, dictionary learning, network monitoring, sensor placement, recommendation, and summarization.
  • Continuous extensions: The Lovasz extension is convex exactly when its corresponding set function is submodular, and discrete minimization equals minimization of that extension.
  • Continuous extensions: The multilinear extension links approximate discrete maximization to continuous optimization but is generally neither concave nor convex.
  • Maximization methods: Continuous greedy and multiplicative-weight methods provide approximation guarantees for monotone DR-submodular maximization under polytope constraints.The cited multiplicative-weight result achieves (1 − 1/e − ε) after ˜O(n^2/ε^2) steps for twice differentiable functions.
  • Generalizations: Integer-lattice DR-submodular maximization can be efficiently reduced to submodular set-function maximization.

4 Algorithms and main results

The paper analyzes projected gradient and mirror methods for monotone weakly DR-submodular maximization over convex sets. It proves that stationary points and stochastic iterates achieve factor-1/2-type guarantees, while mirror methods reduce dimension dependence when smoothness is better in another norm.

  • Setup: Projected gradient methods are studied for weakly DR-submodular functions over convex constraint sets.
  • Stationary points: A stationary point is a feasible point whose gradient has no positive feasible first-order ascent direction.
  • Stationary points: γ^2/(1+γ^2) is the approximation ratio guaranteed for stationary points of monotone weakly DR-submodular functions.For γ = 1, this becomes OPT/2, and the bound is tight.
  • Gradient ascent: A step size below 1/L makes gradient ascent converge to a stationary point for L-smooth objectives.
  • Computational considerations: A limitation of gradient methods is that the smoothness prefactor L can be large, making the required iteration count impractical.
  • Mirror methods: Mirror methods address cases where Euclidean smoothness depends on dimension by adapting to smoothness in general norms.For the discussed setting, the iteration dependence on dimension becomes logarithmic.

5 Experiments

Experiments on MovieLens evaluate stochastic gradient, stochastic mirror, Frank-Wolfe, and greedy methods for stochastic movie recommendation objectives. The proposed stochastic methods achieve competitive utility with smaller batches and fewer computations than key baselines.

  • Problem setup: The stochastic recommendation objective averages user-specific utilities and can be optimized through an empirical objective built from sampled users.
  • Discrete application: Projected stochastic methods yield a continuous solution with at least a 1/2 approximation, which can be rounded into a discrete set retaining that guarantee.Randomized Pipage rounding does not require access to the objective value, and projection onto P_k can be performed in O(n) time.
  • Dataset and objectives: The experiments use MovieLens, containing 1 million ratings from 6041 users over 4000 movies.
  • Dataset and objectives: The evaluation studies facility-location and concave-over-modular user valuation functions whose multilinear extensions are generally neither concave nor convex.
  • Comparisons: With equal batch size and iteration count, SG, SM, and FW have similar computational complexity, while smaller batches reduce effort.
  • Comparisons: After a few hundred iterations, SG and SM with B = 20 obtain almost the same utility as Greedy with B = 1000.

6 Conclusion

The paper concludes that projected gradient methods can effectively maximize submodular functions despite nonconvexity. Fixed points provide factor-1/2 guarantees, stochastic methods reach OPT/2 − ε in O(1/ε^2) iterations, and experiments support their effectiveness on real data.

  • Main conclusions: Fixed points of projected gradient ascent provide a factor 1/2 approximation to global maxima.
  • Main conclusions: Stochastic gradient and mirror methods achieve objective value OPT/2 − ε in O(1/ε^2) iterations.
  • Empirical evidence: Experiments on real data demonstrate the effectiveness of the proposed methods.
  • Scope and future work: The framework is developed for convex constraints, while extensions to nonconvex constraints and approximate projections are left as future possibilities.

7 Proofs

The proofs establish approximation guarantees for projected gradient and mirror methods, including extensions to weakly submodular functions. They combine smoothness, projection, stochastic-gradient, and mirror-descent arguments.

  • Mirror descent analysis uses Bregman divergences, strong convexity of the mirror map, and stochastic-gradient estimates.The argument sums one-step inequalities, takes expectations, and samples iterates to obtain an expected objective guarantee.
  • The guarantees extend to weakly submodular functions with a bound parameterized by the submodularity ratio γ.The extension replaces the submodular guarantee with a γ-dependent approximation expression.

A A DR-Submodular Function that Attains OPT/2 + ϵ on a local maximum

This construction gives a monotone submodular coverage function whose multilinear extension has a local maximum approaching half of the global optimum. Thus, the 1/2 guarantee for stationary points is essentially tight.

  • The example defines a monotone submodular coverage function on V = {1,2,...,2k + 1}.Each set S_i specifies the elements covered by selecting i, and f(A) is the size of their union.
  • The constructed point xloc is a stationary point and becomes a local maximum within a sufficiently small neighborhood.Its function value is F(xloc) = k + 1.
  • F(xloc)/F(x∗) = 1/2 + 1/(2k), so for sufficiently large k the local maximum approaches OPT/2 from above.The construction shows a local maximum with value OPT/2 + ε for suitable k.

B An Example for Deficiency of the Frank-Wolfe Type Algorithm of [16] in the Stochastic Setting

The stochastic Frank-Wolfe variant can fail badly because noisy linear maximization repeatedly selects the wrong coordinates. In the example, its approximation ratio decreases to zero as the dimension grows.

  • With exact gradients, the Frank-Wolfe-type algorithm achieves F(xT) ≥ (1 − 1/e)OPT for large T.The algorithm starts at the origin and uses a gradient-based linear maximization step.
  • Using unbiased single-sample gradients, the stochastic algorithm never assigns mass to the nth coordinate and converges to x∞ with zero nth coordinate.Each sampled gradient selects one of the first n − 1 coordinate vectors in the linear maximization step.
  • F(x∞)/F(x∗) = 2/(n − 1), which can become arbitrarily small as n increases.The optimum instead places all mass on the nth coordinate.
  • The failure extends to Frank-Wolfe with any fixed batch size because expectation and arg max are not interchangeable under noisy gradients.A fixed number of independent samples does not remove the example’s instability.

C DR-submodular Functions with Large Smoothness Parameter in ℓ2 But Reasonable Smoothness Parameter in ℓ1

The multilinear extension of a submodular set function can be poorly smooth in the ℓ2 norm while remaining reasonably smooth in the ℓ1 norm. For monotone functions, the ℓ1 smoothness is bounded by the maximum singleton value.

  • The multilinear extension F can be O(n)-smooth under the ℓ2 norm.This follows from a construction where the Hessian quadratic form at the origin scales linearly with n.
  • For a monotone submodular function, F is mf-smooth under the ℓ1 norm, where mf is the maximum singleton value.The bound is dimension-independent when mf does not grow substantially with n.
  • Submodularity makes the Hessian entries nonpositive and bounds their magnitude by the maximum singleton value.The Hessian representation uses evaluations of F after setting pairs of coordinates to zero or one.

D How to Construct an Unbiased Estimator of the Gradient in Multilinear Extensions

The paper constructs unbiased gradient estimators for multilinear extensions by sampling sets according to the current point and evaluating marginal gains. A shared sampled set yields estimates for all coordinates, while batching reduces variance through averaging.

  • ∇Fθ(x) is an unbiased estimator of ∇F(x) when θ is sampled from D.The stochastic objective is defined as F(x) = Eθ∼D[Fθ(x)].
  • For a multilinear extension G, sample each element independently with probability x_i to construct a gradient estimator at x.The sampled set follows the coordinate-wise probabilities specified by x.
  • g(S∪{i})−g(S∖{i}) provides an unbiased estimator for the i-th partial derivative.This marginal-gain expression is applied after sampling S according to x.
  • One sampled set can estimate all coordinates using n function computations, and a batch of size B averages B repetitions.The shared-sample procedure avoids independently sampling a separate set for every coordinate.
Loading 1708.03949v2…