A tight analysis of the Submodular–Supermodular Procedure

Narasimhan and Bilmes introduced the Submodular–Supermodular Procedure (SSP) for finding a local minimizer of the function h=f−gh=f−g where ff and gg are both submodular functions. In their original analysis the authors left the worst case complexity of SSP as an open question. We provide a tight analysis of SSP by demonstrating a family of examples where SSP can require 2n−2−12n−2−1 iterations before converging (although it reaches a global optimum). We also consider the related Supermodular–Submodular Procedure of Iyer and Bilmes and demonstrate an example that requires ≥⌊16∗3(n−8)/3−3⌋≥⌊16∗3(n−8)/3−3⌋ iterations to converge, and converges to a local, not global, optimum.