Learning Time-Varying Coverage Functions

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.

Authors

• Nan Du Tencent Hunyuan
• Yingyu Liang
• Maria-Florina Balcan School of Computer Science, Carnegie Mellon University
• Le Song

Keywords

No keywords are indexed for this paper.