Learning Time-Varying Coverage Functions
Coverage functions are an important class of discrete functions that capture the law of diminishing returns arising naturally from applications in social network analysis, machine learning, and algorithmic game theory. In this paper, we propose a new problem of learning time-varying coverage functions, and develop a novel parametrization of these functions using random features. Based on the connection between time-varying coverage functions and counting processes, we also propose an efficient parameter learning algorithm based on likelihood maximization, and provide a sample complexity analysis. We applied our algorithm to the influence function estimation problem in information diffusion in social networks, and show that with few assumptions about the diffusion processes, our algorithm is able to estimate influence significantly more accurately than existing approaches on both synthetic and real world data.
This paper defines temporal coverage functions, a generalization of coverage functions with dependence. It introduces a method to learn them from previous time history. It also includes experimental validation on real data sets.The paper is well written, and clear. It is also very technical, and was not an easy read for me. Judging its quality is even harder. I think it would help if the authors could demonstrate with an example what a time-varying coverage function means in practice, for a given data set. That would help me refine the quality score I given in my review.It is not clear to me which of the baseline algorithms in section 7.1 were also using time information, so it would be great it the authors could clarify this? I believe that for a fair comparison the baseline algorithm should use time information as well.