Eigenfunctions Seminar

Title: Understanding Wolfe’s Heuristic: Submodular Function Minimization and Projection onto Polytopes
Speaker: Deeparnab Chakrabarty (Microsoft Research, Bangalore)
Date: 26 February 2016
Time: 3:30 – 4:30 pm
Venue: LH-1, Mathematics Department

Owing to several applications in large scale learning and vision problems, fast submodular function minimization (SFM) has become a very important problem. Theoretically, unconstrained SFM is polynomial time solvable, however, these algorithms are not practical. In 1976, Wolfe proposed a heuristic for projection onto a polytope, and in 1980, Fujishige showed how Wolfe’s heuristic can be used for SFM. For general submodular functions, this Fujishige-Wolfe heuristic seems to have the best empirical performance. Despite its good practical performance, very little is known about Wolfe’s projection algorithm theoretically.

In this talk, I will describe the first analysis which proves that the heuristic is polynomial time for bounded submodular functions. Our work involves the first convergence analysis of Wolfe’s projection heuristic, and proving a robust version of Fujishige’s reduction theorem.

Contact: +91 (80) 2293 2711, +91 (80) 2293 2265 ;     E-mail: chair.math[at]iisc[dot]ac[dot]in
Last updated: 22 Feb 2019