Nikita Zhivotovskiy
Department of Mathematics ETH, Zurich
 
Abstract: The first part of the talk is devoted to robust algorithms for the k-means clustering problem where a quantizer is constructed based on N independent observations. I will present recent sharp non-asymptotic performance guarantees for k-means that hold under the two bounded moments assumption in a general Hilbert space. These bounds extend the asymptotic result of D. Pollard (Annals of Stats, 1981) who showed that the existence of two moments is sufficient for strong consistency of an empirically optimal quantizer. In the second part of the talk I discuss a dimension-free version of the result of Adamczak, Litvak, Pajor, Tomczak-Jaegermann (Journal of Amer. Math. Soc, 2010) for the sample-covariance matrix in log-concave ensembles. The proof of the dimension-free result is based on a duality formula between entropy and moment generating functions.