Tata Institute of Fundamental Research
Understanding Wolfeʼs Heuristic: Submodular Function Minimization and Projection onto Polytopes
STCS Colloquium
Speaker:
Deeparnab Chakrabarty (Microsoft Research
#9, Lavelle Road
Bangalore 560001)
Organiser:
Prahladh Harsha
Date:
Tuesday, 3 May 2016, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract: 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.
| Speaker: | Deeparnab Chakrabarty (Microsoft Research #9, Lavelle Road Bangalore 560001) |
| Organiser: | Prahladh Harsha |
| Date: | Tuesday, 3 May 2016, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract: 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.
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.