“Greedy Adapts to Sharpness”

Speaker: Alfredo Torrico
Ph.D. Candidate, Georgia Tech

Abstract: Submodular maximization has been widely studied over the past decades, mostly because of its numerous applications in real-world problems. It is well known that the standard greedy algorithm guarantees a worst case approximation factor of 1-1/e when maximizing a monotone submodular function under a cardinality constraint. However, empirical studies show that its performance is substantially better in practice. This raises a natural question of explaining this improved performance of the greedy algorithm.   In this work, we define sharpness for submodular functions as a candidate explanation for this phenomenon. The sharpness criteria is inspired by the concept of strong convexity in convex optimization. We show that the  greedy algorithm provably performs better as the sharpness of the submodular function increases.    

Bio: Alfredo Torrico is a fifth-year Ph.D. student in Operations Research at Georgia Tech under supervision of Professors Mohit Singh and Sebastian Pokutta. He is broadly interested in combinatorial optimization, online optimization and machine learning, with a focus on subset selection and resource allocation problems.

Hosted by Amin Karbasi