BEGIN:VCALENDAR VERSION:2.0 PRODID:-//Memento EPFL// BEGIN:VEVENT SUMMARY:Algorithms for Constrained Determinantal Point Processes using Mix ed Discriminants DTSTART:20180724T121500 DTEND:20180724T141500 DTSTAMP:20260407T043641Z UID:bc3f9733ce5ddd0ae244aa790d38543e27d06bde6e99d6b7c0253326 CATEGORIES:Conferences - Seminars DESCRIPTION:Vijay Keswani\nEDIC candidacy exam\nExam president: Prof. Patr ick Thiran\nThesis advisor: Prof. Nisheeth Vishnoi\nCo-examiner: Dr. Olivi er Levêque\n\nAbstract\nDeterminantal Point Processes (DPPs) are probabil ity distributions defined over subsets of a ground set of elements\, with the property that the subsets that are more “diverse” have highe r probability. They occur in many areas of theoretical computer science\, machine learning\, optimization and physics\, and for certain simple setti ngs\, are known to have efficient algorithms. Anari\, Gharan and Rezaei (2 016) gave one such Monte Carlo Markov Chain algorithm for sampling from St rongly Rayleigh distributions\, a generalisation of DPPs\, when there is a simple cardinality constraint on the elements of the support of the DPP d istribution. However\, when more complex constraints are considered\, the problem becomes intractable. Celis et. al (2017) gave a polynomial time al gorithm for sampling from DPPs with partition constraints when the descrip tion of the constraints is in unary\, but also showed that when the descri ption is in binary\, sampling from such DPPs is #P-hard and reduces to com puting mixed discriminants. For special cases though\, mixed discriminants can be approximated within a polynomial factor\, as shown by Barvinok (20 15) in the case of well-conditioned matrix tuples\, and this result can po tentially be used to derive polynomial-approximation sampling algorithms f or certain settings of constrained DPPs. The algorithms for sampling from DPPs with partition constraints can also potentially be extended to partit ion-group constraints\, where there can be non-empty overlap between the v arious divisions of the ground set. Such constraints more accurately depic t the real-world data\, where each individual can belong to multiple group s\, for example\, by gender and race.\n\nBackground papers\n\nMonte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and D eterminantal Point Processes\nOn the Complexity of Constrained Determinant al Point Processes\nConcentration of the mixed discriminant of well-condit ioned matrices LOCATION:BC 129 https://plan.epfl.ch/?room==BC%20129 STATUS:CONFIRMED END:VEVENT END:VCALENDAR