Fast and Simple Optimization for Poisson Likelihood Models
This work addresses a bottleneck in Poisson modeling for domains like imaging and social networks, offering faster convergence, but it is incremental as it builds on existing optimization frameworks.
The paper tackled the challenge of optimizing Poisson likelihood models, which lack Lipschitz-continuity, by proposing a saddle point reformulation and gradient-based algorithm with an O(1/t) convergence rate, outperforming existing methods on synthetic and real-world datasets like social network estimation and temporal recommendation.
Poisson likelihood models have been prevalently used in imaging, social networks, and time series analysis. We propose fast, simple, theoretically-grounded, and versatile, optimization algorithms for Poisson likelihood modeling. The Poisson log-likelihood is concave but not Lipschitz-continuous. Since almost all gradient-based optimization algorithms rely on Lipschitz-continuity, optimizing Poisson likelihood models with a guarantee of convergence can be challenging, especially for large-scale problems. We present a new perspective allowing to efficiently optimize a wide range of penalized Poisson likelihood objectives. We show that an appropriate saddle point reformulation enjoys a favorable geometry and a smooth structure. Therefore, we can design a new gradient-based optimization algorithm with $O(1/t)$ convergence rate, in contrast to the usual $O(1/\sqrt{t})$ rate of non-smooth minimization alternatives. Furthermore, in order to tackle problems with large samples, we also develop a randomized block-decomposition variant that enjoys the same convergence rate yet more efficient iteration cost. Experimental results on several point process applications including social network estimation and temporal recommendation show that the proposed algorithm and its randomized block variant outperform existing methods both on synthetic and real-world datasets.