On the unreasonable effectiveness of the Sinkhorn algorithm

Abstract: This talk concerns Sinkhorn algorithm, broadly understood as the iterative scaling of a matrix that realizes the solution of an entropy regularized linear program subjected to row and column constraints. I will present new theoretical and applied results that demonstrate the effectiveness of this procedure in two contexts: first, Sinkhorn algorithm implements the solution of an entropy regularized version of optimal transport. I will show this regularization substantially improves sample complexity over the unregularized case, a result that helps explain the popularity of this algorithm in machine learning. Additionally, I will describe how Sinkhorn algorithm can be used to estimate the entropy of convolutions and the parameters of statistical models corrupted by noise. Second, Sinkhorn algorithm provides an approximation for the permanent of a matrix. I will show how this approximation leads to new variational methods for probabilistic models involving permutations. Specifically, I will describe an application involving the inference of probabilistic inference of neural identity in the worm C.elegans, under the novel NeuroPAL technology. Finally, I will describe applications to deep learning, for the structured prediction of permutations and for the generation of objects from their pieces.

Posted on Jan 9, 2020 in Seminario Aprendizaje de Máquinas, Seminars