Computational Mathematics and Applications Seminar

Dr Peter Braam is going to talk about; 'State time geometry: causal performance profiles and optimal data transport in parallel execution'

The increasing complexity of parallel architectures and heterogeneous microarchitectures makes predicting and optimising program performance notoriously difficult. For Optimal Data Transport, we present a discrete variant of the Wasserstein–Fisher–Rao metric that quantifies the true cost of data layout transformations and movement across memory hierarchies. For Causal Performance Profiles, we introduce the Lyons–Gregg Signature, which combines the ideas of Terry Lyons' rough path signatures with hardware performance counters (eBPF) to capture cross-correlated, causal bottlenecks in execution streams. Both arose from State Time Geometry (STG), a model for stateful program execution on computing infrastructure, first modelled as a dynamical system governing state-values over the space of memory addresses. The address space generalises to geometric objects defining infrastructure and leads to the metric. The state transitions of parallel executions become a Grothendieck quantum field theory over the infrastructure and carry the statistical model for the Lyons-Gregg Signature. The central theme is that an intuitive faithful model is not doomed by complexity but forms a geometric domain in which both theoretical and engineering perspectives are simplified.

(In a companion lecture in the Computing Laboratory at 11:00 on Nov 13, we will discuss STG's underlying categorical and geometric structure and its relationship to programming languages and formal methods)

Professor Rob Scheichl will talk about: 'Efficient localised model reduction for multiscale PDEs via Grassmannian Interpolation'

Multiscale Spectral Generalized Finite Element Methods (MS-GFEM) are a powerful new discretisation method for general variational problems that satisfy a Gårding-type inequality, including strongly non-Hermitian problems. The construction of optimal approximation spaces is localised and requires no a priori regularity assumptions. The global approximation error is controlled by the local errors, which are rigorously shown to decay nearly exponentially. The optimality hinges on an SVD of the local restriction operator in a suitable, coefficient-dependent inner product on an oversampled patch. Compactness of this operator in the space of a-harmonic functions guarantees spectral accuracy akin to Weyl asymptotics for the Laplacian. As such, MS-GFEM can be seen as an “hp-version” of Localized Orthogonal Decomposition (LOD). Given the coefficient function the local approximation spaces can be constructed efficiently. In this talk, I will show how we can use Grassmannian interpolation of the resulting local approximation spaces on sparse grids in high dimensions to derive localized model order reduction methods that inherit the nearly exponential spatial and parametric convergence of MS-GFEM and of sparse grids, respectively. I will show some numerical experiments confirming the theoretical results in the context of elliptic problems.

Assistant Professor Dominik Stöger will give a talk about: 'Which Sparse Solution Does Gradient Descent Find? Implicit Bias and Convergence Rates for Diagonal Linear Networks Under General Initialization'

Modern machine learning models are often overparametrized, with more parameters than training samples. The implicit bias of gradient descent determines which of the many solutions that fit the data is selected. Diagonal linear networks, in which a linear predictor is parametrized as an entrywise product of several weight vectors, are a tractable model for studying this bias in underdetermined linear regression. A well-known result states that gradient descent converges to the solution with minimum l1-norm as the scale of initialization tends to zero. This connects training dynamics to sparse recovery. However, the result assumes that all parameters are initialized to the same value. In this talk, we remove this assumption and address two questions: (a) What is the implicit bias when parameters are not initialized identically? (b) How fast is the implicit bias approached as the scale of initialization decreases?

For (a), we show that gradient flow converges to the minimizer of a weighted l1-type penalty whose weights depend on both the initialization and the sign of each coordinate of the solution. Our proof relies on a new characterization of the gradient dynamics in terms of a Bregman divergence. For (b), we derive tight convergence rates. In particular, we show that for two-layer networks the limit of gradient flow converges to this minimizer at a sublinear rate in the scale of initialization, whereas for more layers the rate of convergence is linear. Surprisingly, the constants governing these rates are connected to the null-space constants of compressed sensing. Our rates improve on previous results in the identical initialization setting and are, to our knowledge, the first in the general initialization setting.

Joint work with Hannes Matt (KU Eichstätt-Ingolstadt).

Smoothed analysis has become a central tool in computer science, often allowing for significant improvements to worst-case running times if we settle for a solution to a small random perturbation of the problem instance. This is closely related to the classical concept of backward error in numerical analysis, which allows an algorithm to return a solution to a small arbitrary perturbation of the problem.

Despite the qualitative similarity of these concepts, we show that they can exhibit large quantitative differences. Notably, we prove that, while a linear system with any n × n matrix A can be solved to backward error ε using O(log n / ε) matrix-vector products with A, any algorithm that solves a random ε-sized perturbation of A requires Ω(n) matrix-vector products.

This means that a useful perturbation for solving a linear system in backward error must be adaptive to the input. We use this as a starting point to explore the role of adaptivity and randomness in designing perturbations for solving numerical linear algebra problems in backward error.

Based on joint works with Yuji Nakatsukasa, Elizaveta Rebrova, Raphael Meyer, Michael Mahoney, and Christopher Musco.

TBA; hosted at RAL. 

TBA

TBA

TBA

TBA

TBA

TBA

TBA