TY - JOUR
T1 - Point Process Estimation with Mirror Prox Algorithms
AU - He, Niao
AU - Harchaoui, Zaid
AU - Wang, Yichen
AU - Song, Le
N1 - Funding Information:
This work was first presented at the Fifth International Conference on Continuous Optimization (ICCOPT) in August 2016. This work was supported by NSF CMMI-1761699, NCSA Faculty Fellowship, NSF CCF-1740551, the project Titan (CNRS-Mastodons), the MSR-Inria joint centre, the project Macaron (ANR-14-CE23-0003-01), the program “Learning in Machines and Brains” (CIFAR), and faculty research awards. The authors would like to thank Anatoli Juditsky, Julien Mairal, Arkadi Nemirovski, and Joseph Salmon for fruitful discussions. The authors are also grateful to the reviewers and the editor for their valuable remarks and thoughtful comments.
Funding Information:
This work was first presented at the Fifth International Conference on Continuous Optimization (ICCOPT) in August 2016. This work was supported by NSF CMMI-1761699, NCSA Faculty Fellowship, NSF CCF-1740551, the project Titan (CNRS-Mastodons), the MSR-Inria joint centre, the project Macaron (ANR-14-CE23-0003-01), the program ?Learning in Machines and Brains? (CIFAR), and faculty research awards. The authors would like to thank Anatoli Juditsky, Julien Mairal, Arkadi Nemirovski, and Joseph Salmon for fruitful discussions. The authors are also grateful to the reviewers and the editor for their valuable remarks and thoughtful comments.
Publisher Copyright:
© 2019, Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2020/12/1
Y1 - 2020/12/1
N2 - 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.
AB - 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.
KW - Mirror Prox
KW - Point process
KW - Proximal algorithm
KW - Saddle point problem
UR - http://www.scopus.com/inward/record.url?scp=85075863197&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85075863197&partnerID=8YFLogxK
U2 - 10.1007/s00245-019-09634-6
DO - 10.1007/s00245-019-09634-6
M3 - Article
AN - SCOPUS:85075863197
SN - 0095-4616
VL - 82
SP - 919
EP - 947
JO - Applied Mathematics and Optimization
JF - Applied Mathematics and Optimization
IS - 3
ER -