You are all cordially invited to the next AMLab colloquium next **Tuesday, October 27 at 16:00 in C3.163,** where **Yash Satsangi** will give a talk titled “Probably Approximately Correct Greedy Maximization”.

**Abstract**: *Submodular* function maximization finds application in a variety of real-world optimisation problems. However, most existing methods, based on greedy maximization, assume it is computationally feasible to evaluate F, the function being maximized. Unfortunately, in many realistic settings F is too expensive to evaluate exactly even once. We present *probably approximately correct greedy maximization*, which requires access only to cheap anytime confidence bounds on F and uses them to prune elements. We show that, with high probability, our method returns an approximately optimal set. Furthermore, we propose novel, cheap confidence bounds for *conditional entropy*, which appears in many common choices of F and for which it is difficult to find unbiased or bounded estimates. Finally, results from a real-world dataset from a multi-camera tracking system in a shopping mall demonstrate that our approach performs comparably to existing methods, but at a fraction of the computational cost.