EECS Department Colloquium Series
Learning Submodular Functions
 |
Wednesday, April 29, 2015 Maria Florina Balcan
|
ABSTRACT:
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 functions with bounded complexity used in modeling bidder valuation functions in combinatorial auctions and probabilistic coverage functions that can be used to model the influence function in classic models of information diffusion in networks, as well as an application of our algorithms for learning the influence functions in social networks.
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 is currently a board member of the International Machine Learning Society and was recently Program Committee chair for COLT 2014.
| Return to EECS Joint Colloquium |