Point Process Estimation with Mirror Prox Algorithms

  • PDF / 1,153,009 Bytes
  • 29 Pages / 439.37 x 666.142 pts Page_size
  • 86 Downloads / 227 Views

DOWNLOAD

REPORT


Point Process Estimation with Mirror Prox Algorithms Niao He1 · Zaid Harchaoui2 · Yichen Wang3 · Le Song3

© Springer Science+Business Media, LLC, part of Springer Nature 2019

Abstract Point process models have been extensively used in many areas of science and engineering, from quantitative sociology to medical imaging. Computing the maximum likelihood estimator of a point process model often leads to a convex optimization problem displaying a challenging feature, namely the lack of Lipschitz-continuity of the objective function. This feature can be a barrier to the application of common first order convex optimization methods. We present an approach where the estimation of a point process model is framed as a saddle point problem instead. This formulation allows us to develop Mirror Prox algorithms to efficiently solve the saddle point problem. We introduce a general Mirror Prox algorithm, as well as a variant appropriate for large-scale problems, and establish worst-case complexity guarantees for both algorithms. We illustrate the performance of the proposed algorithms for point process estimation on real datasets from medical imaging, social networks, and recommender systems. Keywords Mirror Prox · Proximal algorithm · Point process · Saddle point problem

B

Niao He [email protected] Zaid Harchaoui [email protected] Yichen Wang [email protected] Le Song [email protected]

1

Department of Industrial & Enterprise Systems Engineering, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA

2

Department of Statistics, University of Washington, Seattle, WA 10003, USA

3

Department of Computational Science and Engineering, Georgia Institute of Technology, Atlanta, GA 30332, USA

123

Applied Mathematics & Optimization

The last decade has witnessed a tremendous growth of interests and successes in point process modeling for event data analysis. Applications range from the classical imaging sciences such as nuclear medicine and microscopy using homogeneous Poisson processes (see, e.g., [1] for a comprehensive survey on this topic), stock and option pricing using marked point processes [2,3], all the way to the recent studies of information diffusion over social networks using Hawkes processes [4–8]. A recurring theme of these applications is the requirement of efficient statistical estimation from real-time and large-scale event data. Penalized maximum likelihood estimation has been a mainstream approach to learn estimators for point process models from data. However, existing optimization tools for computing these estimators are far from being optimal and remain a major obstacle to their applicability in practice. In this work, we present a general form of penalized maximum likelihood estimation for point process models. The problem of interest writes as follows: minn f (x) := L(x) + h(x), where L(x) := s T x −

x∈R+

m i=1

ci log(aiT x).

(1)

Here m is the number of observations, Rn+ := {x ∈ Rn : x ≥ 0} stands for the set of nonnegative vectors, the coefficients {c, ai , i = 1, . . . m} are gi