PaperlayerView exact revision on arXiv

Source-linked AI summary

Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions

Rishabh Iyer, Stefanie Jegelka, Jeff Bilmes

arXiv:1311.2110v1cs.DScs.DMcs.LG

TL;DR

Learning submodular functions, approximating them everywhere, and minimizing them under constraints have known hardness bounds that do not distinguish function curvature. The paper uses curve normalization and curvature-modulated constructions to derive refined upper and lower bounds, showing that curvature sharpens the complexity picture for all three problems.

  • Problem

    Prior bounds for approximating, learning, and constrained minimization do not account for curvature, although curvature had already tightened bounds for submodular maximization.

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

  • Method

    The paper uses curve normalization to separate modular and polymatroid components and applies curvature-aware surrogate functions and constructions to analyze the three problems.

    Source: §2.2 · p. 5, §5 · p. 16

  • Results

    Curvature-dependent upper and almost-matching lower bounds refine prior results for approximation, learning, and constrained minimization.

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

  • Takeaways & Limitations

    Curvature provides a unifying measure of how submodular problem bounds vary between functions closer to modularity and harder cases.

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

    The analysis assumes elements with f(j) = 0 can be removed from the ground set without changing the cost function.

    Source: §2.1 · p. 3

Abstract

from arXiv · show

We investigate three related and important problems connected to machine learning: approximating a submodular function everywhere, learning a submodular function (in a PAC-like setting [53]), and constrained minimization of submodular functions. We show that the complexity of all three problems depends on the 'curvature' of the submodular function, and provide lower and upper bounds that refine and improve previous results [3, 16, 18, 52]. Our proof techniques are fairly generic. We either use a black-box transformation of the function (for approximation and learning), or a transformation of algorithms to use an appropriate surrogate function (for minimization). Curiously, curvature has been known to influence approximations for submodular maximization [7, 55], but its effect on minimization, approximation and learning has hitherto been open. We complete this picture, and also support our theoretical claims by empirical results.

1 Introduction

Submodular functions have broad applications, but learning them and minimizing them under constraints can be hard even when only constant- or logarithmic-factor approximations are sought. The paper shows that curvature helps distinguish easier subclasses and tightens bounds for approximation, learning, and constrained optimization.

1 Introduction

  • Submodularity is important across combinatorial optimization, economics, operations research, game theory, and increasingly machine learning.It is defined by a diminishing-marginal-returns condition on a set function.Source: §1 · p. 1
  • Learning submodular functions and constrained minimization can lack constant- or logarithmic-factor polynomial-time approximations in the general case.The authors contrast these hardness results with empirical observations suggesting that they concern contrived function classes, while better results may be possible for practically relevant cases.Source: §1 · p. 1
  • Curvature refines upper and lower bounds for learning and constrained optimization, improving function-independent bounds for many practically relevant functions.Curvature depends on marginal gains rather than a specific functional form and ranges between easier and harder subclasses.Source: §1 · p. 2

2 Problem statements, definitions and background

The paper studies approximation, PMAC learning, and constrained minimization of nonnegative submodular functions, using curvature to sharpen their bounds. It defines curvature as deviation from modularity, introduces curve normalization to separate a function into modular and polymatroid parts, and modulates hard instances to derive curvature-dependent lower bounds.

2 Problem statements, definitions and background

  • The three problems are approximating a function everywhere, PMAC-learning it from samples, and minimizing it over feasible sets.The stated setting assumes a nonnegative submodular function on a finite ground set with f(∅) = 0; the constrained problems include lower cardinality bounds and combinatorial families such as paths, cuts, trees, and matchings.Source: §2 · pp. 2–3

2.1 Curvature of a Submodular function

  • Curvature measures deviation from modularity: modular functions have curvature 0, while matroid rank functions have maximal curvature 1.The paper distinguishes curvature, which measures closeness to modularity, from the submodularity ratio, which measures closeness to submodularity.Source: §2.1 · p. 4

2.2 The Curve-normalized Polymatroid function

  • Curve normalization decomposes f into a curvature-scaled polymatroid part and a modular part weighted by 1 − κ_f.The normalized function has curvature 1; the construction also allows curvature modulation while preserving the underlying polymatroidal structure.Source: §2.2 · p. 5

2.3 A framework for curvature-dependent lower bounds.

  • Curvature modulation applies a common modular component to hard instances, making their information-theoretic lower bounds depend explicitly on curvature.The constructed functions retain the specified curvature, extending prior curvature-independent lower-bound arguments.Source: §2.3 · p. 5
  • For approximating submodular functions (Problem 1), the paper replaces the known O(√n log n) bound with an improved curvature-dependent upper bound of O(√n log n / (1 + (√n log n − 1)(1 − κ_f))).It also says it complements this with a lower bound.Source: §2.3 · p. 5
  • For PMAC learning, the O(√n) bound becomes curvature-dependent; across the studied problems, bounds refine prior results and often yield a constant factor when κ_f < 1.The paper says its decomposition and curve-normalized function also support tight algorithms that achieve lower bounds up to logarithmic factors.Source: §2.3 · pp. 5–6

3 Approximating submodular functions everywhere

Curvature-specific approximation improves general guarantees by approximating only the curved component while retaining the modular component exactly. A simple modular bound can be preferable for small sets, while the ellipsoidal approximation is better for larger sets.

3 Approximating submodular functions everywhere

  • Theorem 3.1 approximates the curve-normalized function and combines it with the modular part, which is retained exactly.The transformation converts an approximation of the curved component into an approximation of the original function.Source: §3 · p. 6
  • For curvature κf < 1, the ellipsoidal approximation can be tightened, and it is exact when κf = 0.The zero-curvature case is modular, so it can be inferred exactly within O(n) oracle calls.Source: §3 · pp. 7–8
  • A curvature-dependent hardness bound refines earlier lower bounds and is tight up to logarithmic factors.The lower-bound construction perturbs hard instances to have the desired curvature.Source: §3 · p. 8
  • The modular upper bound is better for |X| ≤ √n, whereas the ellipsoidal approximation is better for larger sets and is best possible there.The modular approximation is also especially simple to compute.Source: §3 · p. 9
  • For any κ > 0, some monotone submodular function cannot be approximated more tightly by any modular upper bound than the stated curvature-dependent factor.This establishes a tightness boundary for modular upper bounds.Source: §3 · p. 9
  • For concave-over-modular functions, a modular upper bound has an O(|X|^(1−a)) approximation bound, including the square-root case when a = 1/2.The improved curvature-dependent bounds also apply to this function class.Source: §3 · pp. 10–11

4 Learning Submodular functions

The paper adapts PMAC learning to exploit curvature, using a transformed function or a modular approximation. The resulting guarantees depend on curvature and set size, with distinct bounds for product distributions and concave-over-modular functions.

4 Learning Submodular functions

  • With known curvature upper bound and singleton weights, PMAC learning achieves a curvature-dependent factor; under a product distribution, a separate bound depends on log(1/ϵ).The general guarantee is stated as (√n+1)/[1+(√n+1−1)(1−κf)]; the product-distribution guarantee is O(log(1/ϵ)/[1+(log(1/ϵ)−1)(1−κf)]).Source: §4 · p. 11
  • The learner estimates the curve-normalized function and combines it with the singleton-weight modular component to form the final estimate.The approach adapts the Balcan–Harvey reduction and uses the approximation transformation from Theorem 3.1.Source: §4 · pp. 11–12
  • The paper states that the general curvature-dependent learning bound is tight.Its lower-bound result rules out a polynomial-time guarantee for every function in the specified curvature class.Source: §4 · p. 12
  • A local-curvature learning bound is better for small sets and needs only an upper bound on curvature, not the singleton weights.The general bound from Lemma 4.1 is better outside the small-set regime.Source: §4 · p. 12
  • Concave-over-modular functions can be PMAC-learned within min{√n + 1, 1 + |X|^(1−a)}.This is an immediate corollary of the local-curvature result.Source: §4 · p. 12

5 Constrained submodular minimization

The section develops curvature-dependent surrogate methods for constrained submodular minimization and derives upper and lower bounds for several combinatorial problems. Experiments on cardinality lower bounds closely follow the theoretical bounds and show better approximation factors at lower curvature.

5 Constrained submodular minimization

  • The methods decompose f into a curvature-dependent part and a modular part, then retain the modular part while approximating the other with MUB or EA.A surrogate's optimization guarantee transfers to f when the surrogate is efficiently optimized over the feasible sets.Source: §5 · pp. 13–14
  • For cardinality lower bounds, MUB and EA improve prior guarantees when κf < 1; MUB is preferable for small k, while EA's bound is tight up to polylog factors.For κf < 1, no polynomial-time algorithm achieves an approximation factor better than n^1/2−ϵ.Source: §5 · p. 15
  • For shortest submodular paths, EA is tighter on sparse graphs and MUB on dense graphs, while a curvature-dependent hardness bound remains.The lower bound rules out approximation factors better than n^2/3−ϵ when κf > 0.Source: §5 · p. 15
  • For cooperative cuts, PNA has a curvature-dependent worst-case guarantee and is theoretically tighter than EA on dense graphs.PNA uses a generalized-flow algorithm and remains applicable when a modular term is added to its surrogate.Source: §5 · p. 16
  • For spanning trees, MUB's curvature-dependent guarantee is optimal, and EA gives a slightly worse guarantee.The MUB guarantee depends on the number of vertices and connected components.Source: §5 · p. 16
  • Perfect matching and edge cover have curvature-dependent MUB guarantees with nearly matching hardness bounds; matching hardness transfers because every perfect matching is an edge cover.The stated MUB guarantee for perfect matching is n/[2+(n−2)(1−κf)].Source: §5 · p. 17

5.1 Experiments

  • As κ decreases, theoretical and empirical approximation factors improve significantly, and empirical upper bounds closely follow theory; for β = 1 and α ≥ n^(2/3), EA finds the optimal solution.Source: Figure 1 · p. 17, §5.1 · p. 18

6 Conclusion and Discussion

The paper establishes curvature-dependent upper and nearly matching lower bounds for approximation, learning, and constrained minimization. It identifies unifying quantities for these problems and curvature-like measures for subadditive functions as open questions.

6 Conclusion and Discussion

  • The paper studies curvature's role in approximation, learning, and constrained minimization, proving curvature-dependent upper bounds with almost matching lower bounds.Source: §6 · p. 18
  • Whether one quantity can unify curvature and the similarly functioning submodularity ratio remains open.Source: §6 · p. 18
  • The authors identify curvature-dependent regret bounds for constrained online submodular minimization as a possible extension of their techniques.Source: §6 · p. 18
Loading 1311.2110v1…