Department of Mathematics

Search

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.

Autumn Semester 2024

Date / Time Speaker Title Location
17 September 2024
14:15-15:15 		Daniil Dmitriev
ETH Zurich
Details

DACO Seminar

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
HG G 19.1
24 September 2024
14:15-15:15 		Vanessa Piccolo
ENS Lyon, FR
Details

DACO Seminar

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
HG G 19.1
29 October 2024
14:15-15:15 		Lucas Pesenti
Bocconi University, IT
Details

DACO Seminar

Title Understanding iterative algorithms with Fourier diagrams
Speaker, Affiliation Lucas Pesenti, Bocconi University, IT
Date, Time 29 October 2024, 14:15-15:15
Location HG G 19.1
Abstract We study a broad class of nonlinear iterative algorithms applied to random matrices, including power iteration, belief propagation, approximate message passing, and various forms of gradient descent. We show that the behavior of these algorithms can be analyzed by expanding their iterates in an appropriate basis of polynomials, which we call the Fourier diagram basis. As the dimension of the input grows, this basis simplifies to the tree-shaped diagrams, that form a family of asymptotically independent Gaussian vectors. Moreover, the dynamics of the iteration restricted to the tree diagrams exhibit properties reminiscent of the assumptions of the cavity method from statistical physics. This enables us to "implement" heuristic cavity-based reasoning into rigorous arguments, including a new simple proof of the state evolution formula. Based on joint work with Chris Jones (https://arxiv.org/abs/2404.07881)
Understanding iterative algorithms with Fourier diagramsread_more
HG G 19.1
26 November 2024
14:15-15:15 		Prof. Dr. Evita Nestoridi
Stony Brook University, US
Details

DACO Seminar

Title Limit Profiles of Reversible Markov chains
Speaker, Affiliation Prof. Dr. Evita Nestoridi, Stony Brook University, US
Date, Time 26 November 2024, 14:15-15:15
Location HG G 19.1
Abstract It all began with card shuffling. Diaconis and Shahshahani studied the random transpositions shuffle; pick two cards uniformly at random and swap them. They introduced a Fourier analysis technique to prove that it takes $1/2 n \log n$ steps to shuffle a deck of $n$ cards this way. Recently, Teyssier extended this technique to study the exact shape of the total variation distance of the transition matrix at the cutoff time from the stationary measure, giving rise to the notion of a limit profile. In this talk, I am planning to discuss a joint work with Olesker-Taylor, where we extend the above technique from conjugacy invariant random walks to general, reversible Markov chains. I will also present a new technique that allows us to study the limit profile of star transpositions, which turns out to have the same limit profile as random transpositions, and I will discuss open questions and conjectures.
Limit Profiles of Reversible Markov chainsread_more
HG G 19.1
3 December 2024
14:15-15:15 		Prof. Dr. Michael Multerer
USI Lugano, CH
Details

DACO Seminar

Title Samplets: Construction and applications to scattered data
Speaker, Affiliation Prof. Dr. Michael Multerer, USI Lugano, CH
Date, Time 3 December 2024, 14:15-15:15
Location HG G 19.1
Abstract We introduce the concept of samplets, extending the Tausch-White multi-wavelet construction to scattered data. This results in a multiresolution analysis of discrete signed measures with vanishing moments, enabling efficient data compression, feature detection, and adaptivity. The cost for constructing the samplet basis and applying the fast samplet transform is linear in the number of data sites N. We apply samplets to compress kernel matrices for scattered data approximation, achieving sparse matrices with only O(N log N) non-zero entries in the case of quasi-uniform data. The approximation error is controlled by the number of vanishing moments. We demonstrate two applications: a multiscale interpolation scheme for improved conditioning of kernel matrices and a dictionary learning approach with sparsity constraints.
Samplets: Construction and applications to scattered dataread_more
HG G 19.1

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

JavaScript has been disabled in your browser