Submodularity is one of the most important properties in combinatorial optimization and many applications of machine learning, with strong implications for guaranteed optimization However, many practical objectives do not exhibit the submodularity property, these include classes of non-submodular set functions and non-convex functions In this talk I will present some of my efforts in providing guarantees and provable algorithms for optimizing a significantly larger class of objectives They mainly lie in two directions: approximate submodularity and continuous submodularity Approximate submodularity utilizes refined characterizations (e g , submodularity ratio and curvature) to give guarantees for maximizing generally non-submodular set functions, thus theoretically verifying the empirical success of Greedy algorithm on a larger class of applications, such as feature selection and Bayesian experimental design Continuous submodularity is derived by advancing the notion of submodularity to a lattice It defines a category of provable non-convex non-concave objectives with a wide spectrum of applications I will elaborate on guaranteed algorithms on maximizing continuous submodular functions and discuss intriguing geometric properties therein

Mr. An Bian is a PhD candidate in the Institute for Machine Learning at ETH Zürich. He is currently working on provable algorithms for machine learning and data mining. Other than that, he is also interested in topics from computer vision, natural language understanding and decentralized artificial intelligence. An Bian received his bachelor and master degrees from Shanghai Jiao Tong University in 2011 and 2014, respectively.