DACO seminar

Modal title

Modal content

Please subscribe here if you would you like to be notified about these events via e-mail. Moreover you can also subscribe to the iCal/ics Calender.

Date / Time

Speaker

Title

Location

17 September 2024
14:15-15:15

Daniil Dmitriev
ETH Zurich

Details

Title	Robust Mixture Learning when Outliers Overwhelm Small Groups
Speaker, Affiliation	Daniil Dmitriev, ETH Zurich
Date, Time	17 September 2024, 14:15-15:15
Location	HG G 19.1
Abstract	We study the problem of estimating the means of well-separated mixtures when an adversary may add arbitrary outliers. While strong guarantees are available when the outlier fraction is significantly smaller than the minimum mixing weight, much less is known when outliers may crowd out low-weight clusters - a setting we refer to as list-decodable mixture learning (LD-ML). In this case, adversarial outliers can simulate additional spurious mixture components. Hence, if all means of the mixture must be recovered up to a small error in the output list, the list size needs to be larger than the number of (true) components. We propose an algorithm that obtains order-optimal error guarantees for each mixture mean with a minimal list-size overhead, significantly improving upon list-decodable mean estimation, the only existing method that is applicable for LD-ML. Although improvements are observed even when the mixture is non-separated, our algorithm achieves particularly strong guarantees when the mixture is separated: it can leverage the mixture structure to partially cluster the samples before carefully iterating a base learner for list-decodable mean estimation at different scales.

Robust Mixture Learning when Outliers Overwhelm Small Groupsread_more

24 September 2024
14:15-15:15

Vanessa Piccolo
ENS Lyon, FR

Details

Title	Dynamics of optimization in high dimensions for multi-spiked tensor PCA
Speaker, Affiliation	Vanessa Piccolo, ENS Lyon, FR
Date, Time	24 September 2024, 14:15-15:15
Location	HG G 19.1
Abstract	We will study the high-dimensional statistical problem of multi-spiked tensor PCA, where the goal is to infer a finite number of unknown, orthogonal signal vectors (or spikes) from noisy observations of a p-tensor. I will present our recent results on the sample complexity required for stochastic gradient descent to efficiently recover the signal vectors from natural initializations. In particular, we will show that it is possible to recover a permutation of all spikes provided a number of sample scaling as N^{p-2}, aligning with the computational threshold identified in the rank-one tensor PCA problem. The recovery process is governed by a sequential elimination phenomenon. As one correlation exceeds an explicit critical threshold, all correlations that share a row or column index become sufficiently small to be negligible, allowing the subsequent correlation to grow and become macroscopic. The order in which correlations become macroscopic is determined by their initial values and the associated signal-to-noise ratios. Based on recent joint work with Gérard Ben Arous (NYU) and Cédric Gerbelot (NYU).

Dynamics of optimization in high dimensions for multi-spiked tensor PCAread_more

Archive: AS 24 SS 24 AS 23 SS 23 AS 22 SS 22 AS 21 SS 21 AS 20 SS 20