CaltechTHESIS
  A Caltech Library Service

Convex analysis for minimizing and learning submodular set functions

Citation

Stobbe, Peter (2013) Convex analysis for minimizing and learning submodular set functions. Dissertation (Ph.D.), California Institute of Technology. http://resolver.caltech.edu/CaltechTHESIS:05312013-151014984

Abstract

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:http://resolver.caltech.edu/CaltechTHESIS:05312013-151014984
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:7798
Collection:CaltechTHESIS
Deposited By: Peter Stobbe
Deposited On:17 Jun 2013 22:10
Last Modified:13 Apr 2015 19:55

Thesis Files

[img]
Preview
PDF - Final Version
See Usage Policy.

1725Kb

Repository Staff Only: item control page