Seminars

View all Seminars  |  Download ICal for this event

On MAP Inference of Ferromagnetic Potts models and Nonsymmetric Determinantal Point Processes

Series: Bangalore Theory Seminars

Speaker: Aravind Reddy, Northwestern University

Date/Time: May 24 11:00:00

Location: CSA Lecture Hall (Room No. 112, Ground Floor)

Abstract:
In the Maximum-a-Posteriori (MAP) Inference problem, for any given probability distribution, the goal is to find the point in the support of that distribution with the highest probability. Potts models and Determinantal Point Processes (DPPs) are probabilistic models that were introduced in the context of statistical physics several decades ago. They have been extensively used in several computer science applications like computer vision, recommender systems, and document summarization. Exact MAP Inference in these models corresponds to NP-hard combinatorial optimization problems and so approximate inference algorithms have been extensively studied. For MAP Inference in Ferromagnetic Potts models, we provide a strong justification for the excellent performance of a linear programming relaxation approach by going beyond worst-case analysis (appeared in AISTATS 2021). For MAP Inference in Nonsymmetric Determinantal Point Processes, we provide the first one-pass streaming and online algorithms (appeared in ICML 2022).

Microsoft teams link:

Link


We are grateful to the Kirani family for generously supporting the theory seminar series


Hosts: Rameesh Paul, KVN Sreenivas, Rahul Madhavan, Debajyoti Kar