BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//132.216.98.100//NONSGML kigkonsult.se iCalcreator 2.20.4//
BEGIN:VEVENT
UID:20260406T010052EDT-2819VAkZT0@132.216.98.100
DTSTAMP:20260406T050052Z
DESCRIPTION:Title: Consistency of Lloyd's Algorithm Under Perturbations\n\n
 Abstract: In the context of unsupervised learning\, Lloyd's algorithm is o
 ne of the most widely used clustering algorithms. It has inspired a pletho
 ra of work investigating the correctness of the algorithm under various se
 ttings with ground truth clusters. In particular\, Lu and Zhou(2016) have 
 shown that the mis-clustering rate of Lloyd's algorithm on n independent s
 amples from a sub-Gaussian mixture is exponentially bounded after O(\log(n
 )) iterations\, assuming proper initialization of the algorithm. However\,
  in many applications\, the true samples are unobserved and need to be lea
 rned from the data via pre-processing pipelines such as spectral methods o
 n appropriate data matrices. We show that the mis-clustering rate of Lloyd
 's algorithm on perturbed samples from a sub-Gaussian mixture is also expo
 nentially bounded after O(\log(n)) iterations under the assumptions of pro
 per initialization and that the perturbation is small relative to the sub-
 Gaussian noise. In canonical settings with ground truth clusters\, we deri
 ve bounds for algorithms such as k-means++ to find good initializations an
 d thus leading to the correctness of clustering via the main result. We sh
 ow the implications of the results for pipelines measuring the statistical
  significance of derived clusters from data such as SigClust (Liu et al.\,
  2008) We use these general results to derive implications in providing th
 eoretical guarantees on the misclustering rate for Lloyd's algorithm in a 
 host of applications\, including high-dimensional time series\, multi-dime
 nsional scaling\, and community detection for sparse networks via spectral
  clustering.\n\n \n\nReference: https://arxiv.org/pdf/2309.00578.pdf\n\n 
 \n
DTSTART:20231122T180000Z
DTEND:20231122T190000Z
LOCATION:Room 1214\, Burnside Hall\, CA\, QC\, Montreal\, H3A 0B9\, 805 rue
  Sherbrooke Ouest
SUMMARY:Hui Shen (McGill University)
URL:https://www.mcgill.ca/mathstat/channels/event/hui-shen-mcgill-universit
 y-352823
END:VEVENT
END:VCALENDAR