Department seminar by Nikita Zhivotovskiy

Friday, February 4, 2022 10:00 am - 10:00 am EST (GMT -05:00)

Please Note: This seminar will be given online.

Department seminar

Nikita Zhivotovskiy
ETH Zürich

Link to join seminar: Hosted on Zoom

Recent results on algorithmic stability and robust k-means clustering

Algorithmic stability is one of the central ideas in statistical learning theory for proving that certain algorithms can generalize the observed data. This approach can be used to analyze the performance of Stochastic Gradient Descent, Ridge Regression and more general problems of stochastic convex optimization. In the first part of the talk I will cover some of our recent results in this direction. The second 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.