Point Process Estimation with Mirror Prox Algorithms

Niao He, Zaid Harchaoui, Yichen Wang, Le Song

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Pages (from-to)919-947
Number of pages29
JournalApplied Mathematics and Optimization
Volume82
Issue number3
DOIs
StatePublished - Dec 1 2020

Keywords

  • Mirror Prox
  • Point process
  • Proximal algorithm
  • Saddle point problem

ASJC Scopus subject areas

  • Control and Optimization
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Point Process Estimation with Mirror Prox Algorithms'. Together they form a unique fingerprint.

Cite this