Résumés approximation

This talk discusses the sampling complexity of learning with ReLU neural networks and neural operators. For mappings belonging to relevant approximation spaces, upper bounds on the best-possible convergence rate of any learning algorithm are discussed, with respect to the number of samples. In the finite-dimensional case, these bounds imply a « theory-to-practice »-gap between parametric and sampling complexities. This result is extended to the infinite-dimensional setting of operator learning, with application to DeepONets and the Fourier neural operator. It is shown that the best-possible convergence rate in a Bochner Lp-norm is bounded by Monte-Carlo rates of order 1/p.

Gaussian processes (GPs) have gained popularity as flexible machine learning models for regression and function approximation with an in-built method for uncertainty quantification. GPs suffer when the amount of training data is large or when the underlying function contains multiscale features that are difficult to represent by an isotropic kernel. The training of GPs with large scale data is often performed through inducing point approximations (also known as sparse GP regression), where the size of the covariance matrices in GP regression is reduced considerably through a greedy search on the data set. Deep Gaussian processes have recently been introduced as hierarchical models that resolve multi-scale features by composing multiple Gaussian processes. Whilst GPs can be trained through a simple analytical formula, deep GPs require a sampling or, more usual, a variational approximation. Variational approximations lead to large-scale stochastic, non-convex optimisation problems and the resulting approximation tends to represent uncertainty incorrectly.

In this work, we combine variational learning with MCMC to develop a particle-based expectation-maximisation method to simultaneously find inducing points within the large-scale data (variationally) and accurately train the Gaussian processes (sampling-based). The result is a highly efficient and accurate methodology for deep GP training on large scale data. We test the method on standard benchmark problems.

Randomized Kaczmarz methods form a family of linear system solvers that converge by repeatedly projecting their iterates onto randomly sampled equations. While effective in some contexts, such as highly over-determined least squares, Kaczmarz methods are traditionally deemed secondary to Krylov subspace methods, since this latter family of solvers can exploit outliers in the input’s singular value distribution to attain fast convergence on many ill-conditioned systems. In this talk, we introduce an accelerated randomized block Kaczmarz algorithm that exploits outlying singular values in the input to attain a fast Krylov-style convergence. Moreover, we show that our approach captures large outlying singular values provably faster than popular Krylov methods. We also develop an optimized variant for positive semidefinite systems, demonstrating empirically that it is competitive in arithmetic operations with both CG and GMRES on a collection of benchmark problems. To attain these results, we introduce several novel algorithmic improvements to the Kaczmarz framework, including adaptive momentum acceleration, Tikhonov-regularized projections, and a memoization scheme for reusing information from previously sampled equation blocks. This work is joint with Michał Dereziński, Elizaveta Rebrova, and Jiaming Yang.

A fundamental problem in artificial intelligence is the question of how to simultaneously deploy data from different sources such as audio, image, text and video; such data is known as multimodal. In this talk I will focus on the canonical problem of aligning image and text data, and describe some of the mathematical ideas underlying the challenge of allowing them to communicate. I will describe the encoding of text and image in Euclidean spaces and describe contrastive learning methods to identify and learn embeddings which align these two modalities; I will also describe the attention mechanism, a form of nonlinear
correlation in vector-valued sequences. Attention turns out to be useful beyond this specific context, and I will show how it may be used to design and learn maps between Banach spaces or between spaces of probability measures.

based models to long sequences. To address this, we present Fast Multipole Attention (FMA), a new attention mechanism that uses a divide-and-conquer strategy to reduce the time and memory complexity of attention for sequences of length n from O(n^2) to O(n \log n) or O(n), while retaining a global receptive field. The hierarchical approach groups queries, keys, and values into O( \log n) levels of resolution, where groups at greater distances are increasingly larger in size and the weights to compute group quantities are learned. As such, the interaction between tokens far from each other is considered in lower resolution in an efficient hierarchical manner. This multi-level divide-and-conquer strategy is inspired by fast summation methods from n-body physics and the Fast Multipole Method. We perform evaluation on autoregressive and bidirectional language modeling tasks as well as on image classification. We find empirically that the Fast Multipole Transformer performs much better than other efficient transformers and state-of-the-art vision transformers in terms of memory size and accuracy. The FMA mechanism has the potential to empower large language models with much greater sequence lengths, taking the full context into account in an efficient, naturally hierarchical manner during training and when generating long sequences.

Algorithmic stability holds when our conclusions, estimates, fitted models, predictions, or decisions are insensitive to small changes to the training data. Stability has emerged as a core principle for reliable data science, providing insights into generalization, cross-validation, uncertainty quantification, and more. Whereas prior literature has developed mathematical tools for analyzing the stability of specific machine learning (ML) algorithms, we study methods that can be applied to arbitrary learning algorithms to satisfy a desired level of stability. First, I will discuss how bagging is guaranteed to stabilize any prediction model, regardless of the input data. Thus, if we remove or replace a small fraction of the training data at random, the resulting prediction will typically change very little. Our analysis provides insight into how the size of the bags (bootstrap datasets) influences stability, giving practitioners a new tool for guaranteeing a desired level of stability. Second, I will describe how to extend these stability guarantees beyond prediction modeling to more general statistical estimation problems where bagging is not as well known but equally useful for stability. Specifically, I will describe a new framework for stable classification and model selection by combining bagging on class or model weights with a stable, “soft” version of the argmax operator. This is joint work with Jake Soloff and Rina Barber.

Jakob Zech (Heidelberg University)

Statistical Learning Theory for Neural Operators