@inproceedings{sharma2015on,
author = {Sharma, Dravyansh and Kapoor, Ashish and Deshpande, Amit},
title = {On Greedy Maximization of Entropy},
booktitle = {Proceedings of The 32nd International Conference on Machine Learning},
year = {2015},
month = {July},
abstract = {Submodular function maximization is one of the key problems that arise in many machine learning tasks. Greedy selection algorithms are the proven choice to solve such problems, where prior theoretical work guarantees (1 - 1/e) approximation ratio. However, it has been empirically observed that greedy selection provides almost 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). Applications include, but are not limited to, sensor selection 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 Gaussian RBF kernels.},
url = {http://approjects.co.za/?big=en-us/research/publication/greedy-maximization-entropy/},
pages = {1330-1338},
journal = {Journal of Machine Learning Research},
edition = {Proceedings of The 32nd International Conference on Machine Learning},
}