Past Data Science Seminar

Sparse neural networks, where a substantial portion of the components are eliminated, have widely shown their versatility in model compression, robustness improvement, and overfitting mitigation. However, traditional methods for obtaining such sparse networks usually involve a fully pre-trained, dense model. As foundation models become prevailing, the cost of this pre-training step can be prohibitive. On the other hand, training intrinsic sparse neural networks from scratch usually leads to inferior performance compared to their dense counterpart. 

In this talk, I will present a series of approaches to obtain such fantastic sparse neural networks by training from scratch without the need for any dense pre-training steps, including dynamic sparse training, static sparse with random pruning, and only masking no training. First, I will introduce the concept of in-time over-parameterization (ITOP) (ICML2021) which enables training sparse neural networks from scratch (commonly known as sparse training) to attain the full accuracy of dense models. By dynamically exploring new sparse topologies during training, we avoid the costly necessity of pre-training and re-training, requiring only a single training run to obtain strong sparse neural networks. Secondly, ITOP involves additional overhead due to the frequent change in sparse topology. Our following work (ICLR2022) demonstrates that even a naïve, static sparse network produced by random pruning can be trained to achieve dense model performance as long as our model is relatively larger. Moreover, I will further discuss that we can continue to push the extreme of training efficiency by only learning masks at initialization without any weight updates, addressing the over-smoothing challenge in building deep graph neural networks (LoG2022).

Data that have an intrinsic network structure can be found in various contexts, including social networks, biological systems (e.g., protein-protein interactions, neuronal networks), information networks (computer networks, wireless sensor networks),  economic networks, etc. As the amount of graphical data that is generated is increasingly large, compressing such data for storage, transmission, or efficient processing has become a topic of interest. 

In this talk, I will give an information theoretic perspective on graph compression. The focus will be on compression limits and their scaling with the size of the graph. For lossless compression, the Shannon entropy gives the fundamental lower limit on the expected length of any compressed representation. 
I will discuss the entropy of some common random graph models, with a particular emphasis on our results on the random geometric graph model. 
Then, I will talk about the problem of compressing a graph with side information, i.e., when an additional correlated graph is available at the decoder. Turning to lossy compression, where one accepts a certain amount of distortion between the original and reconstructed graphs, I will present theoretical limits to lossy compression that we obtained for the Erdős–Rényi and stochastic block models by using rate-distortion theory.

The tremendous success of the Machine Learning paradigm heavily relies on the development of powerful optimization methods, and the canonical algorithm for training learning models is SGD (Stochastic Gradient Descent). Nevertheless, the latter is quite different from Gradient Descent (GD) which is its noiseless counterpart. Concretely, SGD requires a careful choice of the learning rate, which relies on the properties of the noise as well as the quality of initialization.

 It further requires the use of a test set to estimate the generalization error throughout its run. In this talk, we will present a new SGD variant that obtains the same optimal rates as SGD, while using noiseless machinery as in GD. Concretely, it enables to use the same fixed learning rate as GD and does not require to employ a test/validation set. Curiously, our results rely on a novel gradient estimate that combines two recent mechanisms which are related to the notion of momentum.

Finally, as much as time permits, I will discuss several applications where our method can be extended.

Learning to process and analyze the raw weight matrices of neural networks is an emerging research area with intriguing potential applications like editing and analyzing Implicit Neural Representations (INRs), weight pruning/quantization, and function editing. However, weight spaces have inherent permutation symmetries – permutations can be applied to the weights of an architecture, yielding new weights that represent the same function. As with other data types like graphs and point clouds, these symmetries make learning in weight spaces challenging.

This talk will overview recent advances in designing architectures that can effectively operate on weight spaces while respecting their underlying symmetries. First, we will discuss our ICML 2023 paper which introduces novel equivariant architectures for learning on multilayer perceptron weight spaces. We first characterize all linear equivariant layers for their symmetries and then construct networks composed of these layers. We then turn to our ICLR 2024 work, which generalizes the approach to diverse network architectures using what we term Graph Metanetworks (GMN). This is done by representing input networks as graphs and processing them with graph neural networks. We show the resulting metanetworks are expressive and equivariant to weight space symmetries of the architecture being processed. Our graph metanetworks are applicable to CNNs, attention layers, normalization layers, and more. Together, these works make promising steps toward versatile and principled architectures for weight-space learning.

The COVID-19 pandemic has brought a spotlight to the field of infectious disease modelling, prompting widespread public awareness and understanding of its intricacies. As a result, many individuals now possess a basic familiarity with the principles and methodologies involved in studying the spread of diseases. In this presentation, I aim to deliver a somewhat comprehensive (and hopefully engaging) overview of the methods employed in infectious disease modelling, placing them within the broader context of their significance for government and public health policy.

I will navigate through applications of Spatial Statistics, Branching Processes, and Binary Trees in modelling infectious diseases, with a particular emphasis on integrating machine learning methods into these areas. The goal of this presentation is to take you on a broad tour of methods and their applications, offering a personal perspective by highlighting examples from my recent work.

Mathematical methods are developed to characterize the asymptotics of recurrent neural networks (RNN) as the number of hidden units, data samples in the sequence, hidden state updates, and training steps simultaneously grow to infinity. In the case of an RNN with a simplified weight matrix, we prove the convergence of the RNN to the solution of an infinite-dimensional ODE coupled with the fixed point of a random algebraic equation. 
The analysis requires addressing several challenges which are unique to RNNs. In typical mean-field applications (e.g., feedforward neural networks), discrete updates are of magnitude O(1/N ) and the number of updates is O(N). Therefore, the system can be represented as an Euler approximation of an appropriate ODE/PDE, which it will converge to as N → ∞. However, the RNN hidden layer updates are O(1). Therefore, RNNs cannot be represented as a discretization of an ODE/PDE and standard mean-field techniques cannot be applied. Instead, we develop a fixed point analysis for the evolution of the RNN memory state, with convergence estimates in terms of the number of update steps and the number of hidden units. The RNN hidden layer is studied as a function in a Sobolev space, whose evolution is governed by the data sequence (a Markov chain), the parameter updates, and its dependence on the RNN hidden layer at the previous time step. Due to the strong correlation between updates, a Poisson equation must be used to bound the fluctuations of the RNN around its limit equation. These mathematical methods allow us to prove a neural tangent kernel (NTK) limit for RNNs trained on data sequences as the number of data samples and size of the neural network grow to infinity.

When the data is large, or comes in a streaming way, randomized iterative methods provide an efficient way to solve a variety of problems, including solving linear systems, finding least square solutions, solving feasibility problems, and others. Randomized Kaczmarz algorithm for solving over-determined linear systems is one of the popular choices due to its efficiency and its simple, geometrically intuitive iterative steps. 
In challenging cases, for example, when the condition number of the system is bad, or some of the equations contain large corruptions, the geometry can be also helpful to augment the solver in the right way. I will discuss our recent work with Michal Derezinski and Jackie Lok on Kaczmarz-based algorithms that use external knowledge about the linear system to (a) accelerate the convergence of iterative solvers, and (b) enable convergence in the highly corrupted regime.

Deep learning has revolutionised many scientific fields and so it is no surprise that state-of-the-art solutions to several inverse problems also include this technology. However, for many inverse problems (e.g. in medical imaging) stability and reliability are particularly important.

Furthermore, unlike other image analysis tasks, usually only a fairly small amount of training data is available to train image reconstruction algorithms.

Thus, we require tailored solutions which maximise the potential of all ingredients: data, domain knowledge and mathematical analysis. In this talk we discuss a range of such hybrid approaches and will encounter along the way connections to various topics like generative models, convex optimization, differential equations and equivariance.

How can we find and apply the best optimization algorithm for a given problem?   This question is as old as mathematical optimization itself, and is notoriously hard: even special cases such as finding the optimal learning rate for gradient descent is nonconvex in general. 

In this talk we will discuss a dynamical systems approach to this question. We start by discussing an emerging paradigm in differentiable reinforcement learning called “online nonstochastic control”. The new approach applies techniques from online convex optimization and convex relaxations to obtain new methods with provable guarantees for classical settings in optimal and robust control. We then show how this methodology can yield global guarantees for learning the best algorithm in certain cases of stochastic and online optimization. 

No background is required for this talk, but relevant material can be found in this new text on online control and paper on meta optimization.

Prof. Elad's Bio

TBA

Optimization problems constrained on manifolds are prevalent across science and engineering. For example, they arise in (generalized) eigenvalue problems, principal component analysis, and low-rank matrix completion, to name a few problems. Riemannian optimization is a principled framework for solving optimization problems where the desired optimum is constrained to a (Riemannian) manifold.  Algorithms designed in this framework usually require some geometrical description of the manifold, i.e., tangent spaces, retractions, Riemannian gradients, and Riemannian Hessians of the cost function. However, in some cases, some of the aforementioned geometric components cannot be accessed due to intractability or lack of information.

In this talk, we present methods that allow for overcoming cases of intractability and lack of information. We demonstrate the case of intractability on canonical correlation analysis (CCA) and on Fisher linear discriminant analysis (FDA). Using Riemannian optimization to solve CCA or FDA with the standard geometric components is as expensive as solving them via a direct solver. We address this shortcoming using a technique called Riemannian preconditioning, which amounts to changing the Riemannian metric on the constraining manifold. We use randomized numerical linear algebra to form efficient preconditioners that balance the computational costs of the geometric components and the asymptotic convergence of the iterative methods. If time permits, we also show the case of lack of information, e.g., the constraining manifold can be accessed only via samples of it. We propose a novel approach that allows approximate Riemannian optimization using a manifold learning technique.

Transfer learning is an emerging and popular paradigm for utilizing existing knowledge from  previous learning tasks to improve the performance of new ones. In this talk, we will first present transfer learning in the early diagnosis of eye diseases: diabetic retinopathy and retinopathy of prematurity.  

We will discuss how this empirical  study leads to the mathematical analysis of the feasibility and transferability  issues in transfer learning. We show how a mathematical framework for the general procedure of transfer learning helps establish  the feasibility of transfer learning as well as  the analysis of the associated transfer risk, with applications to financial time series data.

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.

We consider the problem of parameter estimation for a McKean stochastic differential equation, and the associated system of weakly interacting particles. The problem is motivated by many applications in areas such as neuroscience, social sciences (opinion dynamics, cooperative behaviours), financial mathematics, statistical physics. We will first survey some model properties related to propagation of chaos and ergodicity and then move on to discuss the problem of parameter estimation both in offline and on-line settings. In the on-line case, we propose an online estimator, which evolves according to a continuous-time stochastic gradient descent algorithm on the asymptotic log-likelihood of the interacting particle system. The talk will present our convergence results and then show some numerical results for two examples, a linear mean field model and a stochastic opinion dynamics model. This is joint work with Louis Sharrock, Panos Parpas and Greg Pavliotis. Preprint: https://arxiv.org/abs/2106.13751

We study sampling from a target distribution $e^{-f}$ using the unadjusted Langevin Monte Carlo (LMC) algorithm. For any potential function $f$ whose tails behave like $\|x\|^\alpha$ for $\alpha \in [1,2]$, and has $\beta$-H\"older continuous gradient, we derive the sufficient number of steps to reach the $\epsilon$-neighborhood of a $d$-dimensional target distribution as a function of $\alpha$ and $\beta$. Our rate estimate, in terms of $\epsilon$ dependency, is not directly influenced by the tail growth rate $\alpha$ of the potential function as long as its growth is at least linear, and it only relies on the order of smoothness $\beta$.

Our rate recovers the best known rate which was established for strongly convex potentials with Lipschitz gradient in terms of $\epsilon$ dependency, but we show that the same rate is achievable for a wider class of potentials that are degenerately convex at infinity.

The success of operator splitting techniques for convex optimization has led to an explosion of methods for solving large-scale and non convex optimization problems via convex relaxation. 

This success is at the cost of overlooking direct approaches to operator splitting that embrace some of the more inconvenient aspects of many model problems, namely nonconvexity, non smoothness and infeasibility.  I will introduce some of the tools we have developed for handling these issues, and present sketches of the basic results we can obtain.

The formalism is in general metric spaces, but most applications have their basis in Euclidean spaces.  Along the way I will try to point out connections to other areas of intense interest, such as optimal mass transport.

One of the great challenges of neural networks is to understand how they work.  For example: does a neuron encode a meaningful signal on its own?  Or is a neuron simply an undistinguished and arbitrary component of a feature vector space?  The tension between the neuron doctrine and the population coding hypothesis is one of the classical debates in neuroscience. It is a difficult debate to settle without an ability to monitor every individual neuron in the brain.

Within artificial neural networks we can examine every neuron. Beginning with the simple proposal that an individual neuron might represent one internal concept, we conduct studies relating deep network neurons to human-understandable concepts in a concrete, quantitative way: Which neurons? Which concepts? Are neurons more meaningful than an arbitrary feature basis? Do neurons play a causal role? We examine both simplified settings and state-of-the-art networks in which neurons learn how to represent meaningful objects within the data without explicit supervision.

Following this inquiry in computer vision leads us to insights about the computational structure of practical deep networks that enable several new applications, including semantic manipulation of objects in an image; understanding of the sparse logic of a classifier; and quick, selective editing of generalizable rules within a fully trained generative network.  It also presents an unanswered mathematical question: why is such disentanglement so pervasive?

In the talk, we challenge the notion that the internal calculations of a neural network must be hopelessly opaque. Instead, we propose to tear back the curtain and chart a path through the detailed structure of a deep network by which we can begin to understand its logic.

Many machine learning applications involve non-Euclidean data, such as graphs, strings or matrices. In such cases, exploiting Riemannian geometry can deliver algorithms that are computationally superior to standard(Euclidean) nonlinear programming approaches. This observation has resulted in an increasing interest in Riemannian methods in the optimization and machine learning community.

In the first part of the talk, we consider the task of learning a robust classifier in hyperbolic space. Such spaces have received a surge of interest for representing large-scale, hierarchical data, due to the fact that theyachieve better representation accuracy with fewer dimensions. We present the first theoretical guarantees for the (robust) large margin learning problem in hyperbolic space and discuss conditions under which hyperbolic methods are guaranteed to surpass the performance of their Euclidean counterparts. In the second part, we introduce Riemannian Frank-Wolfe (RFW) methods for constrained optimization on manifolds. Here, we discuss matrix-valued tasks for which such Riemannian methods are more efficient than classical Euclidean approaches. In particular, we consider applications of RFW to the computation of Riemannian centroids and Wasserstein barycenters, both of which are crucial subroutines in many machine learning methods.

From latent variable models in machine learning to inverse problems in computational imaging, tensors pervade the data sciences.  Often, the goal is to decompose a tensor into a particular low-rank representation, thereby recovering quantities of interest about the application at hand.  In this talk, I will present a recent method for low-rank CP symmetric tensor decomposition.  The key ingredients are Sylvester’s catalecticant method from classical algebraic geometry and the power method from numerical multilinear algebra.  In simulations, the method is roughly one order of magnitude faster than existing CP decomposition algorithms, with similar accuracy.  I will state guarantees for the relevant non-convex optimization problem, and robustness results when the tensor is only approximately low-rank (assuming an appropriate random model).  Finally, if the tensor being decomposed is a higher-order moment of data points (as in multivariate statistics), our method may be performed without explicitly forming the moment tensor, opening the door to high-dimensional decompositions.  This talk is based on joint works with João Pereira, Timo Klock and Tammy Kolda. 

One of the most successful methods in topological data analysis (TDA) is persistent homology, which associates a one-parameter family of spaces to a data set, and gives a summary — an invariant called "barcode" — of how topological features, such as the number of components, holes, or voids evolve across the parameter space. In many applications one might wish to associate a multiparameter family of spaces to a data set. There is no generalisation of the barcode to the multiparameter case, and finding algebraic invariants that are suitable for applications is one of the biggest challenges in TDA.

The use of persistent homology in applications is justified by the validity of certain stability results. At the core of such results is a notion of distance between the invariants that one associates to data sets. While such distances are well-understood in the one-parameter case, the study of distances for multiparameter persistence modules is more challenging, as they rely on a choice of suitable invariant.

In this talk I will first give a brief introduction to multiparameter persistent homology. I will then present a general framework to study stability questions in multiparameter persistence: I will discuss which properties we would like invariants to satisfy, present different ways to associate distances to such invariants, and finally illustrate how this framework can be used to derive new stability results. No prior knowledge on the subject is assumed.

The talk is based on joint work with Barbara Giunti, John Nolan and Lukas Waas. 

Learning a representation from data that disentangles different factors of variation is hypothesized to be a critical ingredient for unsupervised learning. Defining disentangling is challenging - a "symmetry-based" definition was provided by Higgins et al. (2018), but no prescription was given for how to learn such a representation. We present a novel nonparametric algorithm, the Geometric Manifold Component Estimator (GEOMANCER), which partially answers the question of how to implement symmetry-based disentangling. We show that fully unsupervised factorization of a data manifold is possible if the true metric of the manifold is known and each factor manifold has nontrivial holonomy – for example, rotation in 3D. Our algorithm works by estimating the subspaces that are invariant under random walk diffusion, giving an approximation to the de Rham decomposition from differential geometry. We demonstrate the efficacy of GEOMANCER on several complex synthetic manifolds. Our work reduces the question of whether unsupervised disentangling is possible to the question of whether unsupervised metric learning is possible, providing a unifying insight into the geometric nature of representation learning.

Low rank orthogonal tensor approximation (LROTA) is an important problem in tensor computations and their applications. A classical and widely used algorithm is the alternating polar decomposition method (APD). In this talk, I will first give very a brief introduction to tensors and their decompositions. After that, an improved version named iAPD of the classical APD will be proposed and all the following four fundamental properties of iAPD will be discussed : (i) the algorithm converges globally and the whole sequence converges to a KKT point without any assumption; (ii) it exhibits an overall sublinear convergence with an explicit rate which is sharper than the usual O(1/k) for first order methods in optimization; (iii) more importantly, it converges R-linearly for a generic tensor without any assumption; (iv) for almost all LROTA problems, iAPD reduces to APD after finitely many iterations if it converges to a local minimizer. If time permits, I will also present some numerical experiments.

Magnitude is an isometric invariant of metric spaces that was introduced by Tom Leinster in 2010, and is currently the object of intense research, since it has been shown to encode many invariants of a metric space such as volume, dimension, and capacity.

Magnitude homology is a homology theory for metric spaces that has been introduced by Hepworth-Willerton and Leinster-Shulman, and categorifies magnitude in a similar way as the singular homology of a topological space categorifies its Euler characteristic.

In this talk I will first introduce magnitude and magnitude homology. I will then give an overview of existing results and current research in this area, explain how magnitude homology is related to persistent homology, and finally discuss new stability results for magnitude and how it can be used to study point cloud data.

This talk is based on  joint work in progress with Miguel O’Malley and Sara Kalisnik, as well as the preprint https://arxiv.org/abs/1807.01540.