A Caltech Library Service

Convex Analysis for Minimizing and Learning Submodular Set Functions


Stobbe, Peter (2013) Convex Analysis for Minimizing and Learning Submodular Set Functions. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/1A1J-SA64.


The connections between convexity and submodularity are explored, for purposes of minimizing and learning submodular set functions.

First, we develop a novel method for minimizing a particular class of submodular functions, which can be expressed as a sum of concave functions composed with modular functions. The basic algorithm uses an accelerated first order method applied to a smoothed version of its convex extension. The smoothing algorithm is particularly novel as it allows us to treat general concave potentials without needing to construct a piecewise linear approximation as with graph-based techniques.

Second, we derive the general conditions under which it is possible to find a minimizer of a submodular function via a convex problem. This provides a framework for developing submodular minimization algorithms. The framework is then used to develop several algorithms that can be run in a distributed fashion. This is particularly useful for applications where the submodular objective function consists of a sum of many terms, each term dependent on a small part of a large data set.

Lastly, we approach the problem of learning set functions from an unorthodox perspective---sparse reconstruction. We demonstrate an explicit connection between the problem of learning set functions from random evaluations and that of sparse signals. Based on the observation that the Fourier transform for set functions satisfies exactly the conditions needed for sparse reconstruction algorithms to work, we examine some different function classes under which uniform reconstruction is possible.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:Convexity, Submodularity, Machine Learning
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Applied And Computational Mathematics
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Krause, R. Andreas
Thesis Committee:
  • Tropp, Joel A. (chair)
  • Chandrasekaran, Venkat
  • Abu-Mostafa, Yaser S.
  • Krause, R. Andreas
Defense Date:13 May 2013
Record Number:CaltechTHESIS:05312013-151014984
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:7798
Deposited By: Peter Stobbe
Deposited On:17 Jun 2013 22:10
Last Modified:04 Oct 2019 00:01

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page