Hotelling Lecture: Yurii Nesterov; CORE, Catholic University of Louvain

Soft clustering by convex electoral model

Wednesday, April 10th, 2019

In this talk, we analyze an electoral model based on random preferences of participants. Each voter can choose a party with certain probability depending on the divergence between his personal preferences and current position of the party. Our model represents a rare example of a community detection model (or, soft clustering) with unique equilibrium state. This is achieved by allowing the flexible positions for the parties (centers of clusters). We propose an efficient algorithm for finding the equilibrium state with linear rate of convergence. It can be interpreted as an alternating minimization scheme. Again, this is a rare example when such a scheme has provable global linear rate of convergence.