Dimension-free analysis of k-means clustering, stochastic convex optimization and sample covariance matrices in log-concave ensembles

Job Candidate Talk
Tuesday, January 25, 2022 - 11:00am for 1 hour (actually 50 minutes)
Nikita Zhivotovskiy – ETH Zurich – https://sites.google.com/view/nikitazhivotovskiy/
Mayya Zhilova

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. Finally, I will briefly discuss a recent bound on an empirical risk minimization strategy in stochastic convex optimization with strongly convex and Lipschitz losses.

Link to the online talk: https://bluejeans.com/958288541/0675