Events Calendar

CS Colloquium: Nina Balcan (CMU) - Learning Submodular Functions

Speaker: Nina Balcan , Carnegie Mellon University

Talk Title: Learning Submodular Functions

Series: CS Colloquium

Abstract: This lecture satisfies requirements for CSCI 591: Computer Science Research Colloquium

Submodular functions are discrete functions that model laws of diminishing returns and enjoy numerous applications in many areas, including algorithmic game theory, machine learning, and social networks. For example, submodular functions are commonly used to model valuation functions for bidders in auctions, and the influence of various subsets of agents in social networks. Traditionally it is assumed that these functions are known to the decision maker; however, for large scale systems, it is often the case they must be learned from observations.

In this talk, I will discuss a recent line of work on studying the learnability of submodular functions. I will describe general upper and lower bounds on the learnability of such functions that yield novel structural results about them of interest to many areas. I will also discuss even better guarantees that can be achieved for important classes that exhibit additional structure. These classes include probabilistic coverage functions that can be used to model the influence function in classic models of information diffusion in networks and functions with bounded complexity used in modeling bidder valuation functions in auctions.

I will also discuss an application of our algorithms for learning the influence functions in social networks, that outperforms existing approaches empirically in both synthetic and real world data.

This event will be available to stream HERE.

Biography: Maria-Florina Balcan is an Associate Professor in the School of Computer Science at Carnegie Mellon University. Her main research interests are machine learning, computational aspects in economics and game theory, and algorithms. Her honors include the CMU SCS Distinguished Dissertation Award, an NSF CAREER Award, a Microsoft Faculty Research Fellowship, a Sloan Research Fellowship, and several paper awards. She was a Program Committee Co-chair for COLT 2014, and is currently a board member of the International Machine Learning Society and a Program Committee Co-chair for ICML 2016.


Host: Yan Liu

Location: Henry Salvatori Computer Science Center (SAL) - 101

Audiences: Everyone Is Invited

Contact: Assistant to CS chair