Main content

SS 2024

18.06.2024 um 14:00 Uhr in 69/125

Dr. Karel Devriendt (Max Planck Institute for Mathematics, Leipzig)

Spanning trees, effective resistances and curvature on graphs

Kirchhoff's celebrated matrix tree theorem expresses the number of spanning trees of a graph as the maximal minor of the Laplacian matrix of the graph. In modern language, this determinantal counting formula reflects the fact that spanning trees form a regular matroid. In this talk, I will discuss some consequences of this matroidal perspective for the study of a related quantity from electrical circuit theory: the effective resistance. I will give a characterization of effective resistances in terms of a certain polytope associated with the spanning tree matroid and discuss applications to recent work on discrete notions of curvature based on the effective resistance.

25.06.2024 um 14:00 Uhr in 69/125

M.Sc. Harsha Kumar (Universität Osnabrück)

Data Compression using Rank-1 Lattices for Parameter Estimation in Machine Learning

Calculating mean squared error and its regularized versions in supervised machine learning can be computationally demanding, especially with large datasets. In this talk, I will present our recent work, which builds on an approach by J. Dick and M. Feischl, to address this challenge. We have developed algorithms that significantly reduce the size of extensive datasets using rank-1 lattices, a type of quasi-Monte Carlo (QMC) point set that, when carefully chosen, is well-distributed in a multi-dimensional unit cube. Our compression strategy involves a preprocessing step that assigns each lattice point a pair of weights based on the original data and responses, reflecting their relative importance. This compression makes iterative loss calculations in optimization steps much faster. I will also discuss our analysis of the errors associated with these QMC data compression algorithms and the computational cost of the preprocessing step, particularly for functions with fast-decaying Fourier coefficients in Wiener algebras or Korobov spaces. Notably, our approach can achieve arbitrarily high convergence rates for sufficiently smooth functions.