On Greedy Maximization of Entropy

Abstract

Submodular function maximization is one of the key problems that arise in many machine learn-ing tasks. Greedy selection algorithms are the proven choice to solve such problems, where prior theoretical work guarantees (1 − 1/e) ap-proximation ratio. However, it has been empiri-cally observed that greedy selection provides al-most optimal solutions in practice. The main goal of this paper is to explore and answer why the greedy selection does significantly better than the theoretical guarantee of (1 − 1/e). Applica-tions include, but are not limited to, sensor se-lection tasks which use both entropy and mutual information as a maximization criteria. We give a theoretical justification for the nearly optimal approximation ratio via detailed analysis of the curvature of these objective functions for Gaus-sian RBF kernels. 1.