Poster
Learning Time-Varying Coverage Functions
Nan Du · Yingyu Liang · Maria-Florina F Balcan · Le Song

Tue Dec 9th 07:00 -- 11:59 PM @ Level 2, room 210D #None

Coverage functions are an important class of discrete functions that capture laws of diminishing returns. In this paper, we propose a new problem of learning time-varying coverage functions which arise naturally from applications in social network analysis, machine learning, and algorithmic game theory. We develop a novel parametrization of the time-varying coverage function by illustrating the connections with counting processes. We present an efficient algorithm to learn the parameters by maximum likelihood estimation, and provide a rigorous theoretic analysis of its sample complexity. Empirical experiments from information diffusion in social network analysis demonstrate that with few assumptions about the underlying diffusion process, our method performs significantly better than existing approaches on both synthetic and real world data.

Author Information

Nan Du (Georgia Tech)
Yingyu Liang (Princeton University)
Maria-Florina F Balcan (Georgia Tech)
Le Song (Georgia Institute of Technology)

More from the Same Authors