Past Data Science Seminar

Principal Component Analysis (PCA) is a fundamental and ubiquitous tool in statistics and data analysis.
The bare-bones idea is this. Given a data set of n points y_1, ..., y_n, form their sample covariance S. Eigenvectors corresponding to large eigenvalues--namely directions along which the variation within the data set is large--are usually thought of as "important"  or "signal-bearing"; in contrast, weak directions are often interpreted as "noise", and discarded along the proceeding steps of the data analysis pipeline. Principal component (PC) selection is an important methodological question: how large should an eigenvalue be so as to be considered "informative"?
Our main deliverable is ScreeNOT: a novel, mathematically-grounded procedure for PC selection. It is intended as a fully algorithmic replacement for the heuristic and somewhat vaguely-defined procedures that practitioners often use--for example the popular "scree test".
Towards tackling PC selection systematically, we model the data matrix as a low-rank signal plus noise matrix Y = X + Z; accordingly, PC selection is cast as an estimation problem for the unknown low-rank signal matrix X, with the class of permissible estimators being singular value thresholding rules. We consider a formulation of the problem under the spiked model. This asymptotic setting captures some important qualitative features observed across numerous real-world data sets: most of the singular values of Y are arranged neatly in a "bulk", with very few large outlying singular values exceeding the bulk edge. We propose an adaptive algorithm that, given a data matrix, finds the optimal truncation threshold in a data-driven manner under essentially arbitrary noise conditions: we only require that Z has a compactly supported limiting spectral distribution--which may be a priori unknown. Under the spiked model, our algorithm is shown to have rather strong oracle optimality properties: not only does it attain the best error asymptotically, but it also achieves (w.h.p.) the best error--compared to all alternative thresholds--at finite n.

This is joint work with Matan Gavish (Hebrew University of Jerusalem) and David Donoho (Stanford). 

Invariance under selected transformations has recently proven to be a powerful inductive bias in several machine learning models. One class of such models are tensor train networks. In this talk, we impose invariance relations on tensor train networks. We introduce a new numerical algorithm to construct a basis of tensors that are invariant under the action of normal matrix representations of an arbitrary discrete group. This method can be up to several orders of magnitude faster than previous approaches. The group-invariant tensors are then combined into a group-invariant tensor train network, which can be used as a supervised machine learning model. We applied this model to a protein binding classification problem, taking into account problem-specific invariances, and obtained prediction accuracy in line with state-of-the-art invariant deep learning approaches. This is joint work with Brent Sprangers.

Accurately predicting turbulent fluid mechanics remains a significant challenge in engineering and applied science. Reynolds-Averaged Navier–Stokes (RANS) simulations and Large-Eddy Simulation (LES) are generally accurate, though non-Boussinesq turbulence and/or unresolved multiphysical phenomena can preclude predictive accuracy in certain regimes. In turbulent combustion, flame–turbulence interactions lead to inverse-cascade energy transfer, which violates the assumptions of many RANS and LES closures. We survey the regime dependence of these effects using a series of high-resolution Direct Numerical Simulations (DNS) of turbulent jet flames, from which an intermediate regime of heat-release effects, associated with the hypothesis of an “active cascade,” is apparent, with severe implications for physics- and data-driven closure models. We apply adjoint-based data assimilation method to augment the RANS and LES equations using trusted (though not necessarily high-fidelity) data. This uses a Python-native flow solver that leverages differentiable-programming techniques, automatic construction of adjoint equations, and solver-in-the-loop optimization. Applications to canonical turbulence, shock-dominated flows, aerodynamics, and flow control are presented, and opportunities for reacting flow modeling are discussed.

Generative AI has seen tremendous successes recently, most notably the chatbot ChatGPT and the DALLE2 software creating realistic images and artwork from text descriptions. Underlying these and other generative AI systems are usually neural networks trained to produce text, images, audio, or video from text inputs. The aim of this talk is to develop an understanding of the fundamental capabilities of generative neural networks. Specifically and mathematically speaking, we consider the realization of high-dimensional random vectors from one-dimensional random variables through deep neural networks. The resulting random vectors follow prescribed conditional probability distributions, where the conditioning represents the text input of the generative system and its output can be text, images, audio, or video. It is shown that every d-dimensional probability distribution can be generated through deep ReLU networks out of a 1-dimensional uniform input distribution. What is more, this is possible without incurring a cost—in terms of approximation error as measured in Wasserstein-distance—relative to generating the d-dimensional target distribution from d independent random variables. This is enabled by a space-filling approach which realizes a Wasserstein-optimal transport map and elicits the importance of network depth in driving the Wasserstein distance between the target distribution and its neural network approximation to zero. Finally, we show that the number of bits needed to encode the corresponding generative networks equals the fundamental limit for encoding probability distributions (by any method) as dictated by quantization theory according to Graf and Luschgy. This result also characterizes the minimum amount of information that needs to be extracted from training data so as to be able to generate a desired output at a prescribed accuracy and establishes that generative ReLU networks can attain this minimum.

This is joint work with D. Perekrestenko and L. Eberhard


 

Tbc

The data revolution has changed the landscape of computational mathematics and has increased the demand for new numerical linear algebra tools to handle the vast amount of data. One crucial task is data compression to capture the inherent structure of data efficiently. Tensor-based approaches have gained significant traction in this setting by exploiting multilinear relationships in multiway data. In this talk, we will describe a matrix-mimetic tensor algebra that offers provably optimal compressed representations of high-dimensional data. We will compare this tensor-algebraic approach to other popular tensor decomposition techniques and show that our approach offers both theoretical and numerical advantages.

Sparse inversion and classification problems are ubiquitous in modern data science and imaging. They are often formulated as non-smooth minimisation problems. In sparse inversion, we minimise, e.g., the sum of a data fidelity term and an L1/LASSO regulariser. In classification, we consider, e.g., the sum of a data fidelity term and a non-smooth Ginzburg--Landau energy. Standard (sub)gradient descent methods have shown to be inefficient when approaching such problems. Splitting techniques are much more useful: here, the target function is partitioned into a sum of two subtarget functions -- each of which can be efficiently optimised. Splitting proceeds by performing optimisation steps alternately with respect to each of the two subtarget functions.

In this work, we study splitting from a stochastic continuous-time perspective. Indeed, we define a differential inclusion that follows one of the two subtarget function's negative subdifferential at each point in time. The choice of the subtarget function is controlled by a binary continuous-time Markov process. The resulting dynamical system is a stochastic approximation of the underlying subgradient flow. We investigate this stochastic approximation for an L1-regularised sparse inversion flow and for a discrete Allen-Cahn equation minimising a Ginzburg--Landau energy. In both cases, we study the longtime behaviour of the stochastic dynamical system and its ability to approximate the underlying subgradient flow at any accuracy. We illustrate our theoretical findings in a simple sparse estimation problem and also in low- and high-dimensional classification problems.

I will describe algorithms for regularizing and training deep neural networks. Soft constraints, which add a penalty term to the loss, are typically used as a form ofexplicit regularization for neural network training. In this talk I describe a method for efficiently incorporating constraints into a stochastic gradient Langevin framework for the training of deep neural networks. In contrast to soft constraints, our constraints offer direct control of the parameter space, which allows us to study their effect on generalization. In the second part of the talk, I illustrate the presence of latent multiple time scales in deep learning applications.

Different features present in the data can be learned by training a neural network on different time scales simultaneously. By choosing appropriate partitionings of the network parameters into fast and slow parts I show that our multirate techniques can be used to train deep neural networks for transfer learning applications in vision and natural language processing in half the time, without reducing the generalization performance of the model.

Characterising intractable high-dimensional random variables is one of the fundamental challenges in stochastic computation. We develop a deep transport map that is suitable for sampling concentrated distributions defined by an unnormalised density function. We approximate the target distribution as the push-forward of a reference distribution under a composition of order-preserving transformations, in which each transformation is formed by a tensor train decomposition. The use of composition of maps moving along a sequence of bridging densities alleviates the difficulty of directly approximating concentrated density functions. We propose two bridging strategies suitable for wide use: tempering the target density with a sequence of increasing powers, and smoothing of an indicator function with a sequence of sigmoids of increasing scales. The latter strategy opens the door to efficient computation of rare event probabilities in Bayesian inference problems.

Numerical experiments on problems constrained by differential equations show little to no increase in the computational complexity with the event probability going to zero, and allow to compute hitherto unattainable estimates of rare event probabilities for complex, high-dimensional posterior densities.
 

Topological signals associated not only to nodes but also to links and to the higher dimensional simplices of simplicial complexes are attracting increasing interest in signal processing, machine learning and network science. However, little is known about the collective dynamical phenomena involving topological signals. Typically, topological signals of a given dimension are investigated and filtered using the corresponding Hodge Laplacians. In this talk, I will introduce the topological Dirac operator that can be used to process simultaneously topological signals of different dimensions.  I will discuss the main spectral properties of the Dirac operator defined on networks, simplicial complexes and multiplex networks, and their relation to Hodge Laplacians.   I will show that topological signals treated with the Hodge Laplacians or with the Dirac operator can undergo collective synchronization phenomena displaying different types of critical phenomena. Finally, I will show how the Dirac operator allows to couple the dynamics of topological signals of different dimension leading to the Dirac signal processing of signals defined on nodes, links and triangles of simplicial complexes. 

In this talk, I will discuss and introduce deep insight from the dynamical system perspective to understand the convergence guarantees of first-order algorithms involving inertial features for convex optimization in a Hilbert space setting.

Such algorithms are widely popular in various areas of data science (data processing, machine learning, inverse problems, etc.).
They can be viewed discrete as time versions of an inertial second-order dynamical system involving different types of dampings (viscous damping,  Hessian-driven geometric damping).

The dynamical system perspective offers not only a powerful way to understand the geometry underlying the dynamic, but also offers a versatile framework to obtain fast, scalable and new algorithms enjoying nice convergence guarantees (including fast rates). In addition, this framework encompasses known algorithms and dynamics such as the Nesterov-type accelerated gradient methods, and the introduction of time scale factors makes it possible to further accelerate these algorithms. The framework is versatile enough to handle non-smooth and non-convex objectives that are ubiquituous in various applications.

While there have been substantial successes of actor-critic methods in continuous control, simpler critic-only methods such as Q-learning often remain intractable in the associated high-dimensional action spaces. However, most actor-critic methods come at the cost of added complexity: heuristics for stabilisation, compute requirements as well as wider hyperparameter search spaces. To address this limitation, we demonstrate in two stages how a simple variant of Deep Q Learning matches state-of-the-art continuous actor-critic methods when learning from simpler features or even directly from raw pixels. First, we take inspiration from control theory and shift from continuous control with policy distributions whose support covers the entire action space to pure bang-bang control via Bernoulli distributions. And second, we combine this approach with naive value decomposition, framing single-agent control as cooperative multi-agent reinforcement learning (MARL). We finally add illustrative examples from control theory as well as classical bandit examples from cooperative MARL to provide intuition for 1) when action extrema are sufficient and 2) how decoupled value functions leverage state information to coordinate joint optimization.

Numerical optimization is an indispensable tool of modern data analysis, and there are many optimization problems where it is difficult or impossible to compute the full gradient of the objective function. The field of derivative free optimization (DFO) addresses these cases by using only function evaluations, and has wide-ranging applications from hyper-parameter tuning in machine learning to PDE-constrained optimization.

We present two projects that attempt to scale DFO techniques to higher dimensions.  The first method converges slowly but works in very high dimensions, while the second method converges quickly but doesn't scale quite as well with dimension.  The first-method is a family of algorithms called "stochastic subspace descent" that uses a few directional derivatives at every step (i.e. projections of the gradient onto a random subspace). In special cases it is related to Spall's SPSA, Gaussian smoothing of Nesterov, and block-coordinate descent. We provide convergence analysis and discuss Johnson-Lindenstrauss style concentration.  The second method uses conventional interpolation-based trust region methods which require large ill-conditioned linear algebra operations.  We use randomized linear algebra techniques to ameliorate the issues and scale to larger dimensions; we also use a matrix-free approach that reduces memory issues.  These projects are in collaboration with David Kozak, Luis Tenorio, Alireza Doostan, Kevin Doherty and Katya Scheinberg.

I will discuss the use of partitioned schemes for neural networks. This work is in the tradition of multrate numerical ODE methods in which different components of system are evolved using different numerical methods or with different timesteps. The setting is the training tasks in deep learning in which parameters of a hierarchical model must be found to describe a given data set. By choosing appropriate partitionings of the parameters some redundant computation can be avoided and we can obtain substantial computational speed-up. I will demonstrate the use of the procedure in transfer learning applications from image analysis and natural language processing, showing a reduction of around 50% in training time, without impairing the generalization performance of the resulting models. This talk describes joint work with Tiffany Vlaar.

A common observation that wider (in the number of hidden units/channels/attention heads) neural networks perform better motivates studying them in the infinite-width limit.

Remarkably, infinitely wide networks can be easily described in closed form as Gaussian processes (GPs), at initialization, during, and after training—be it gradient-based, or fully Bayesian training. This provides closed-form test set predictions and uncertainties from an infinitely wide network without ever instantiating it (!).

These infinitely wide networks have become powerful models in their own right, establishing several SOTA results, and are used in applications including hyper-parameter selection, neural architecture search, meta learning, active learning, and dataset distillation.

The talk will provide a high-level overview of our work at Google Brain on infinite-width networks. In the first part I will derive core results, providing intuition for why infinite-width networks are GPs. In the second part I will discuss challenges and solutions to implementing and scaling up these GPs. In the third part, I will conclude with example applications made possible with infinite width networks.

The talk does not assume familiarity with the topic beyond general ML background.

4th IMA Conference on The Mathematical Challenges of Big Data

The 4th Ima Conference on The Mathematical Challenges of Big Data is issuing a Call For Papers for both contributed talks and posters. Mathematical foundations of data science and its ongoing challenges are rapidly growing fields, encompassing areas such as: network science, machine learning, modelling, information theory, deep and reinforcement learning, applied probability and random matrix theory. Applying deeper mathematics to data is changing the way we understand the environment, health, technology, quantitative humanities, the natural sciences, and beyond ‐ with increasing roles in society and industry. This conference brings together researchers and practitioners to highlight key developments in the state‐of‐the art and find common ground where theory and practice meet, to shape future directions and maximize impact. We particularly welcome talks aimed to inform on recent developments in theory or methodology that may have applied consequences, as well as reports of diverse applications that have led to interesting successes or uncovered new challenges.

Contributed talks and posters are welcomed from the mathematically oriented data science community. Contributions will be selected based on brief abstracts and can be based on previously unpresented results, or recent material originally presented elsewhere. We encourage contributions from both established and early career researchers. Contributions will be assigned to talks or posters based on the authors request as well as the views of the organizing committee on the suitability of the results. The conference will be held in person with the option to attend remotely where needed.

Inducement of sparsity, Heather Battey
Sparsity, the existence of many zeros or near-zeros in some domain, is widely assumed throughout the high-dimensional literature and plays at least two roles depending on context. Parameter orthogonalisation (Cox and Reid, 1987) is presented as inducement of population-level sparsity. The latter is taken as a unifying theme for the talk, in which sparsity-inducing parameterisations or data transformations are sought. Three recent examples are framed in this light: sparse parameterisations of covariance models; systematic construction of factorisable transformations for the elimination of nuisance parameters; and inference in high-dimensional regression. The solution strategy for the problem of exact or approximate sparsity inducement appears to be context specific and may entail, for instance, solving one or more partial differential equation, or specifying a parameterised path through transformation or parameterisation space.

Confirmed Invited Speakers
Dr Heather Battey, Imperial College London
Prof. Lenka Zdebrova, EPFL (Swiss Federal Institute Technology)
Prof. Nando de Freitas, Google Deep Mind
Prof. Tiago de Paula Peixoto, Central European University

Please follow the link below for Programme and Registration:

https://ima.org.uk/17625/4th-ima-conference-on-the-mathematical-challen…

Predicting a protein’s structure from its primary sequence has been a grand challenge in biology for the past 50 years, holding the promise to bridge the gap between the pace of genomics discovery and resulting structural characterization. In this talk, we will describe work at DeepMind to develop AlphaFold, a new deep learning-based system for structure prediction that achieves high accuracy across a wide range of targets. We demonstrated our system in the 14th biennial Critical Assessment of Protein Structure Prediction (CASP14) across a wide range of difficult targets, where the assessors judged our predictions to be at an accuracy “competitive with experiment” for approximately 2/3rds of proteins. The talk will cover both the underlying machine learning ideas and the implications for biological research as well as some promising further work.

Cryo-Electron Microscopy (cryo-EM) is an imaging technology that is revolutionizing structural biology. Cryo-electron microscopes produce many very noisy two-dimensional projection images of individual frozen molecules; unlike related methods, such as computed tomography (CT), the viewing direction of each particle image is unknown. The unknown directions and extreme noise make the determination of the structure of molecules challenging. While other methods for structure determination, such as x-ray crystallography and NMR, measure ensembles of molecules, cryo-electron microscopes produce images of individual particles. Therefore, cryo-EM could potentially be used to study mixtures of conformations of molecules. We will discuss a range of recent methods for analyzing the geometry of molecular conformations using cryo-EM data.

We consider the problem of finding the best memoryless stochastic policy for an infinite-horizon partially observable Markov decision process (POMDP) with finite state and action spaces with respect to either the discounted or mean reward criterion. We show that the (discounted) state-action frequencies and the expected cumulative reward are rational functions of the policy, whereby the degree is determined by the degree of partial observability. We then describe the optimization problem as a linear optimization problem in the space of feasible state-action frequencies subject to polynomial constraints that we characterize explicitly. This allows us to address the combinatorial and geometric complexity of the optimization problem using tools from polynomial optimization. In particular, we estimate the number of critical points and use the polynomial programming description of reward maximization to solve a navigation problem in a grid world. The talk is based on recent work with Johannes Müller.

Non-smooth optimization is a core ingredient of many imaging or machine learning pipelines. Non-smoothness encodes structural constraints on the solutions, such as sparsity, group sparsity, low-rank and sharp edges. It is also the basis for the definition of robust loss functions such as the square-root lasso.  Standard approaches to deal with non-smoothness leverage either proximal splitting or coordinate descent. The effectiveness of their usage typically depend on proper parameter tuning, preconditioning or some sort of support pruning. In this work, we advocate and study a different route. By over-parameterization and marginalising on certain variables (Variable Projection), we show how many popular non-smooth structured problems can be written as smooth optimization problems. The result is that one can then take advantage of quasi-Newton solvers such as L-BFGS and this, in practice, can lead to substantial performance gains. Another interesting aspect of our proposed solver is its efficiency when handling imaging problems that arise from fine discretizations (unlike proximal methods such as ISTA whose convergence is known to have exponential dependency on dimension). On a theoretical level, one can connect gradient descent on our over-parameterized formulation with mirror descent with a varying Hessian metric. This observation can then be used to derive dimension free convergence bounds and explains the efficiency of our method in the fine-grids regime.

Given two probability distributions in R^d, a transport map is a function which maps samples from one distribution into samples from the other. For absolutely continuous measures, Brenier proved a remarkable theorem identifying a unique canonical transport map, which is "monotone" in a suitable sense. We study the question of whether this map can be efficiently estimated from samples. The minimax rates for this problem were recently established by Hutter and Rigollet (2021), but the estimator they propose is computationally infeasible in dimensions greater than three. We propose two new estimators---one minimax optimal, one not---which are significantly more practical to compute and implement. The analysis of these estimators is based on new stability results for the optimal transport problem and its regularized variants. Based on joint work with Manole, Balakrishnan, and Wasserman and with Pooladian.

The alchemists wanted to create gold, Hilbert wanted an algorithm to solve Diophantine equations, researchers want to make deep learning robust in AI, MATLAB wants (but fails) to detect when it provides wrong solutions to linear programs etc. Why does one not succeed in so many of these fundamental cases? The reason is typically methodological barriers. The history of  science is full of methodological barriers — reasons for why we never succeed in reaching certain goals. In many cases, this is due to the foundations of mathematics. We will present a new program on methodological barriers and foundations of mathematics,  where — in this talk — we will focus on two basic problems: (1) The instability problem in deep learning: Why do researchers fail to produce stable neural networks in basic classification and computer vision problems that can easily be handled by humans — when one can prove that there exist stable and accurate neural networks? Moreover, AI algorithms can typically not detect when they are wrong, which becomes a serious issue when striving to create trustworthy AI. The problem is more general, as for example MATLAB's linprog routine is incapable of certifying correct solutions of basic linear programs. Thus, we’ll address the following question: (2) Why are algorithms (in AI and computations in general) incapable of determining when they are wrong? These questions are deeply connected to the extended Smale’s 9th and 18th problems on the list of mathematical problems for the 21st century. 

Blind deconvolution problems are ubiquitous in many areas of imaging and technology and have been the object of study for several decades. Recently, motivated by the theory of compressed sensing, a new viewpoint has been introduced, motivated by applications in wireless application, where a signal is transmitted through an unknown channel. Namely, the idea is to randomly embed the signal into a higher dimensional space before transmission. Due to the resulting redundancy, one can hope to recover both the signal and the channel parameters. In this talk we analyze convex approaches based on lifting as they have first been studied by Ahmed et al. (2014). We show that one encounters a fundamentally different geometric behavior as compared to generic bilinear measurements. Namely, for very small levels of deterministic noise, the error bounds based on common paradigms no longer scale linearly in the noise level, but one encounters dimensional constants or a sublinear scaling. For larger - arguably more realistic - noise levels, in contrast, the scaling is again near-linear.

This is joint work with Yulia Kostina (TUM) and Dominik Stöger (KU Eichstätt-Ingolstadt).

Volumetric X-ray tomography is used in many areas, including applications in medical imaging, many fields of scientific investigation as well as several industrial settings. Yet complex X-ray physics and the significant size of individual x-ray tomography data-sets poses a range of data-science challenges from the development of efficient computational methods, the modelling of complex non-linear relationships, the effective analysis of large volumetric images as well as the inversion of several ill conditioned inverse problems, all of which prevent the application of these techniques in many advanced imaging settings of interest. This talk will highlight several applications were specific data-science issues arise and showcase a range of approaches developed recently at the University of Southampton to overcome many of these obstacles.