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.

Spring Semester 2025

Date / Time Speaker Title Location
20 March 2025
14:15-15:15 		Dr. Léo Mathis
Goethe University Frankfurt, DE
Details

DACO Seminar

Title Non centered Gaussian determinants with Gaussian zonoids
Speaker, Affiliation Dr. Léo Mathis, Goethe University Frankfurt, DE
Date, Time 20 March 2025, 14:15-15:15
Location HG G 19.1
Abstract A Theorem of Vitale, Molchanov and Wespi, states that the expected absolute determinant of a random matrix with independent columns is equal to the mixed volume of some convex bodies called zonoids. In the case where the columns of the matrix are centered Gaussian, the corresponding zonoids are ellipsoids and this was studied by Kabluchko and Zaporozhets. The case of non centered Gaussian vectors, however, remains relatively unstudied. The convex bodies we obtain in this case, which I call Gaussian zonoids, are not ellipsoids. In this talk, I will show you what a Gaussian zonoid looks like and how one can approximate it with an ellipsoid. At the level of random determinants, this allows to approximate expectation of non centered Gaussian determinants with centered ones. If time allows, I will show how this applies to Gaussian random fields. Namely, I will show how one can give a quantitative estimate of the concentration of a small Gaussian perturbation of a hypersurface.
Non centered Gaussian determinants with Gaussian zonoidsread_more
HG G 19.1
27 March 2025
14:15-15:15 		Prof. Dr. Irene Waldspurger
CEREMADE (Université Paris-Dauphine)
Details

DACO Seminar

Title Correctness guarantees for the Burer-Monteiro heuristic on MaxCut-type problems
Speaker, Affiliation Prof. Dr. Irene Waldspurger, CEREMADE (Université Paris-Dauphine)
Date, Time 27 March 2025, 14:15-15:15
Location HG G 19.1
Abstract Since numerically solving high-dimensional semidefinite programs is challenging, solvers should exploit the structure of the problem at hand, when it allows for speedups. In this talk, we will consider the setting where we have the a priori information that the solution is of low rank (for instance, rank 1). A standard way to exploit this information is through the Burer-Monteiro factorization: we represent the unknown matrix as a product of "thin" matrices (i.e. with few columns); then, we optimize the factors instead of the whole square matrix. This technique reduces the dimensionality of the problem, allowing for important computational savings. However, it makes the problem non-convex, thereby possibly introducing non-optimal critical points which can cause the solver to fail. With Faniriana Rakoto Endor, we have considered the specific category of so-called "MaxCut-type" semidefinite problems. We have exhibited a simple property which guarantees that the resulting non-convex problem has no non-optimal critical point, and hence ensures the success of the algorithm.
Correctness guarantees for the Burer-Monteiro heuristic on MaxCut-type problemsread_more
HG G 19.1
10 April 2025
14:15-15:15 		Dr. Mitchell Taylor
ETH Zurich, Switzerland
Details

DACO Seminar

Title Recent advances in the phase retrieval problem
Speaker, Affiliation Dr. Mitchell Taylor, ETH Zurich, Switzerland
Date, Time 10 April 2025, 14:15-15:15
Location HG G 19.1
Abstract In many physical experiments, detectors are only able to measure the intensity of a signal and hence lose access to the phase. The phase retrieval problem deals with the reconstruction of a signal from magnitude measurements, assuming certain physical constraints are satisfied. In this talk, I will briefly discuss the history of this problem and overview some recent progress on proving rigorous stability bounds in infinite dimensions.
Recent advances in the phase retrieval problemread_more
HG G 19.1
7 May 2025
14:00-15:00 		Dr. Pedro Abdalla Teixeira
UC Irvine, US
Details

DACO Seminar

Title LLM Watermarking Using Mixtures and Statistical-to-Computational Gaps
Speaker, Affiliation Dr. Pedro Abdalla Teixeira, UC Irvine, US
Date, Time 7 May 2025, 14:00-15:00
Location HG G 19.1
Abstract Given a text, can we determine whether it was generated by a large language model (LLM) or by a human? Watermarking is a prominent method used to address this question. In this talk, we will analyze two different watermarking settings from a statistical perspective, focusing in particular on how mixtures and statistical-to-computational gaps can be useful for watermarking. This is a joint work with Roman Vershynin.
LLM Watermarking Using Mixtures and Statistical-to-Computational Gapsread_more
HG G 19.1
21 May 2025
10:15-11:00 		Prof. Dr. Shahar Mendelson
Details

DACO Seminar

Title Do we really need the Rademacher complexities?
Speaker, Affiliation Prof. Dr. Shahar Mendelson,
Date, Time 21 May 2025, 10:15-11:00
Location HG F 26.1
Abstract The sample complexity of learning in a convex class and with respect to the squared loss is arguably the most important question in Statistical Learning Theory. The state-of-the-art estimates in this setting rely on Rademacher complexities, and those are generally difficult to control. I will explain why (contrary to prevailing belief) and under minimal assumptions, the Rademacher complexities are not really needed: the sample complexity is actually governed by the behaviour of the limiting gaussian process. In particular, all such learning problems that have the same L_2 structure - even those with heavy-tailed distributions - share the same sample complexity as if the problem were light-tailed. At the heart of the proof is the construction of uniform mean estimation procedures for some natural function classes. I will show how such uniform mean estimation procedures can be derived by combining optimal mean estimation techniques for real-valued random variables with Talagrand's generic chaining method.
Do we really need the Rademacher complexities?read_more
HG F 26.1
22 May 2025
14:15-15:00 		Rares-Darius Buhai
ETH Zurich
Details

DACO Seminar

Title The Quasi-Polynomial Low-Degree Conjecture is False
Speaker, Affiliation Rares-Darius Buhai, ETH Zurich
Date, Time 22 May 2025, 14:15-15:00
Location HG F 26.1
Abstract There is a growing body of work on proving hardness results for average-case optimization problems by bounding the low-degree likelihood ratio (LDLR) between a null distribution and a related planted distribution. Such hardness results are now ubiquitous not only for foundational average-case problems but also central questions in statistics and cryptography. This line of work is supported by the low-degree conjecture of Hopkins [Hop18], which in its extended form postulates that a vanishing degree-D LDLR implies the absence of any noise-tolerant distinguishing algorithm with runtime n^{D / polylog(D)} whenever (1) the null distribution is product and (2) the planted distribution is permutation invariant. We disprove this conjecture. Specifically, we show that for all sufficiently small ε > 0, there is a planted distribution on {0, 1}^{n(n-1)/2} that has a vanishing degree-n^{1-O(ε)} LDLR with respect to the uniform distribution on {0, 1}^{n(n-1)/2} even as an n^{O(log n)}-time algorithm solves the corresponding ε-noisy distinguishing problem. Our construction relies on algorithms for list-decoding for noisy polynomial interpolation in the high-error regime. Joint work with Jun-Ting Hsieh, Aayush Jain, and Pravesh Kothari.
The Quasi-Polynomial Low-Degree Conjecture is Falseread_more
HG F 26.1
* 22 May 2025
15:15-16:15 		Jiaheng Chen
University of Chicago, US
Details

DACO Seminar

Title Sharp concentration of simple random tensors
Speaker, Affiliation Jiaheng Chen, University of Chicago, US
Date, Time 22 May 2025, 15:15-16:15
Location HG F 26.1
Abstract Tensors are fundamental objects in mathematics, physics, statistics, and computer science, and they play an important role in a wide range of applied sciences and engineering disciplines. In this talk, we will focus on concentration inequalities for simple random tensors. We establish sharp dimension-free concentration inequalities and expectation bounds for the deviation of the sum of simple random tensors from its expectation. As part of our analysis, we use generic chaining techniques to obtain a sharp high-probability upper bound on the suprema of multi-product empirical processes. In so doing, we generalize classical results for quadratic and product empirical processes to higher-order settings.
Sharp concentration of simple random tensorsread_more
HG F 26.1
24 June 2025
16:15-17:30 		Prof. Dr. Alex Wein
UC Davis
Details

DACO Seminar

Title Overcomplete Tensor Decomposition via Koszul-Young Flattenings
Speaker, Affiliation Prof. Dr. Alex Wein, UC Davis
Date, Time 24 June 2025, 16:15-17:30
Location HG 19.1
Abstract An order-3 tensor is an n-by-n-by-n array of real numbers. We consider the task of decomposing a given tensor as the sum of rank-1 tensors, using the minimal number of terms. This task has various applications in statistics and data science, such as learning the latent parameters of certain statistical models from the empirical third moment tensor. Under the standard assumption that the tensor components are "generic," a classical method called simultaneous diagonalization or "Jennrich's algorithm" can decompose tensors of rank up to r <= n in polynomial time. A recent result of Koiran (2024) improves this to r <= 4n/3, and we improve this further to r <= 2n. The algorithm is based on a non-trivial procedure for "flattening" tensors to matrices. We also give a matching impossibility result, showing that no flattening of the style we consider can surpass 2n. This may suggest a fundamental barrier for fast algorithms.
Overcomplete Tensor Decomposition via Koszul-Young Flatteningsread_more
HG 19.1

Notes: events marked with an asterisk (*) indicate that the time and/or location are different from the usual time and/or location.

Archive: SS 25 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
OSZAR »