As an introduction to the school, I will give an elementary introduction to some exciting topics related to algorithms and PDE of relatively recent origin (some as far back as the 1980's) and some from the current decade. These include the development, on one hand, of mathematical theories for Hamilton-Jacobi equations, optimal transport, and gradient flows, and on the other, of novel algorithms and computational frameworks like ADMM, stochastic gradient descent, and diffusion models. After a superficial survey of these topics I will discuss some broad analytical and computational challenges and how they might relate to one another. My hope is this might serve as motivation for the topics of the week's lectures and research talks, and point to the untapped potential collaboration across these various fields.

The notion of viscosity solution was introduced in 1983 by M. G. Crandall and P. L. Lions as a generalization of the classical concept of solution for certain first order partial differential equations called Hamilton-Jacobi equations. This mini-course is an introduction to the theory of viscosity solutions later developed for degenerate elliptic and parabolic equations. In the first lecture I will define the notion of viscosity (sub,super-)solution and describe the class of equations treated within the theory. In the second lecture I will present the comparison principle between viscosity sub and super-solutions. Existence through the Perron's method will be then discussed in Lecture 3. Finally, Lecture 4 will be devoted to an overview of the regularity theory.

In the middle of the last century, the so-called direct methods of the calculus of variations which was developed by Charles Bradfield Morrey, aims to study multiple integral variational problems. Morrey introduced the concept of quasiconvexity and proved that it is the right notion to guaranty existence of solutions for a class of variational problems in PDEs. Since it is hard to check whether or not a function is quasiconvex, Morrey introduced a new concept, called rank-one-convexity which is weaker than quasiconvexity but easier to handle. He also introduced the concept of polyconvexity which is stronger than quasiconvexity but also easier to handle. The first three lectures serve as an introduction to multiple integral variational problems. As a preamble, we will provide a brief introduction to Sobolev functions, which are unavoidable in the study of problems arising in nonlinear elasticity theory.

In 1987, D. L. Burkholder proposed a very simple looking and explicit energy functionals $I_p$ defined on $\mathbb{S}$, the set of smooth functions on the complex plane. A question of great interest is to know whether or not $\sup_{\mathbb{S}} I_p \leq 0$. Since, the function $I_p$ is homogeneous of degree $p$, it is very surprising that it remains a challenge to prove or disprove that $\sup_{\mathbb{S}} I_p \leq 0$. Would $\sup_{\mathbb{S}} I_p \leq 0$, the so-called Iwaniec's conjecture on the Beurling-Ahlfors Transform in harmonic analysis would hold. Would $\sup_{\mathbb{S}} I_p > 0$, the so-called Morrey's conjecture in elasticity theory would hold. Therefore proving or disproving that $\sup_{\mathbb{S}} I_p \leq 0$ is equally important. Since the computational capacity of computers has increased exponentially over the past decades, it is natural to hope that computational math could help settle down these two conjectures at once.

Gradient descent or dual gradient ascent are perhaps the fundamental methods for solving optimization problems. The classical setting for these gradient methods is a finite dimensional Euclidean space equipped with the $L^2$ inner product. On the other hand, optimization problems arising from PDEs are necessarily infinite dimensional. Furthermore, the optimization may occur over a space that does not have a natural inner product, forcing the user to make a nontrivial choice. In this mini-course, we will investigate how to best apply gradient methods in infinite dimensions, focusing on examples from optimal transport (computing the $W_2$ and $W_1$ Wasserstein distances), gradient flows (minimizing movements/JKO scheme), and image processing (TV compressed sensing). We shall also discuss when one should consider solving the dual problem instead of the primal problem, or consider a mixed primal-dual gradient method.

Prerequisites: Basic linear algebra and probability theory. Graph theory. Control theory, optimization theory, signal processing, and machine learning knowledge is helpful.

Course Rationale: Intro 4-lecture mini-course on modern design and analysis methods for distributed and decentralized algorithms with applications to signal processing, optimization, control, and machine learning.

Summary: This course will provide an introductory presentation of modern design and analysis methods for distributed and decentralized algorithms for signal processing, optimization, control, and machine learning applications. The course will focus on mathematical analysis techniques for the iteration, computational, and communication complexity of distributed data processing methods over networks, where data is generated, stored, or processed by groups of computational units or agents connected via communication channels over networks. The contents of this course lie in the intersection of network science, optimization, and machine learning.

Contents

Lecture 1: The (distributed) optimization problem

Lecture 2: Consensus, gossip, and random walks

Lecture 3: Distributed optimization algorithms

Lecture 4: Applications: optimal transport, statistical estimation, opinion dynamics

In this talk, we present sequences of graphs satisfying the finite-time consensus property (i.e., iterating through such a finite sequence is equivalent to performing global or exact averaging) and their use in Gradient Tracking. We provide an explicit weight matrix representation of the studied sequences and prove its finite-time consensus property. Moreover, we incorporate the studied finite-time consensus topologies into Gradient Tracking and present a new algorithmic scheme called Gradient Tracking for Finite-Time Consensus Topologies (GT-FT). We analyze the new scheme for nonconvex problems with stochastic gradient estimates. Our analysis shows that the convergence rate of GT-FT does not depend on the heterogeneity of the agents' functions or the connectivity of any individual graph in the topology sequence. Furthermore, owing to the sparsity of the graphs, GT-FT requires lower communication costs than Gradient Tracking using the static counterpart of the topology sequence.

Adversarial training is a framework widely used by practitioners to enforce robustness of machine learning models. During the training process, the learner is pitted against an adversary who has the power to alter the input data. As a result, the learner is forced to build a model that is robust to data perturbations. Despite the importance and relative conceptual simplicity of adversarial training, there are many aspects that are still not well-understood (e.g. regularization effects, geometric/analytic interpretations, tradeoff between accuracy and robustness, etc...), particularly in the case of multiclass classification. In this talk, I will show that in the non-parametric setting, the adversarial training problem is equivalent to a multimarginal optimal transport problem that can be viewed as a generalized version of the Wasserstein barycenter problem. The connection between these problems allows us to completely characterize the optimal adversarial strategy and to bring in tools from optimal transport to analyze and compute optimal classifiers. This also has implications for the parametric setting, as the value of the generalized barycenter problem gives a universal upper bound on the robustness/accuracy tradeoff inherent to adversarial training.

Generative Adversarial Networks (GANs) was one of the first Machine Learning algorithms to be able to generate remarkably realistic synthetic images. In this presentation, we delve into the mechanics of the GAN algorithm and its profound relationship with optimal transport theory. Through a detailed exploration, we illuminate how GAN approximates a system of PDE, particularly evident in shallow network architectures. Furthermore, we investigate the phenomenon of mode collapse, a well-known pathological behavior in GANs, and elucidate its connection to the underlying PDE framework through an illustrative example.

From its origins in work by Monge and Kantorovich, the Wasserstein distance has played an important role in the theory of mathematics. In the current era, the strong and increasing connection between optimization and machine learning has brought new applications of theWasserstein distance to the fore. In these applications, the focus is on learning the probability distributions underlying the Wasserstein distance formulation. However, the Wasserstein distance has been known to suffer from expensive computation and the curse of dimensionality. It creates several hurdles of using theWasser- stein distance in statistical machine learning applications. A well-known approach to overcome the statistical and computational limits of the Wasserstein distance is by projecting the probability distributions into the one-dimensional manifold, which refer to as the sliced Wasserstein distance. The sliced Wasserstein distance leverages the closed-form expression of the Wasserstein distance in one dimension; therefore, its computational complexity is only linear in the number of supports of the probability distributions while the statistical rate is parametric for learning probability distributions. Despite these advantages of the sliced Wasserstein distance, it still suffers from two fundamental challenges in large-scale high dimensional statistical machine learning settings: (1) High projection complexities, namely, the number of projections to approximate the value of the sliced Wasserstein distance is huge and scales with the dimension of the problem; (2) Uninformative projecting directions, namely, there are several redundant projections to approximate the value of the sliced Wasserstein distance.

In this talk, we propose two fundamental approaches to tackle the above challenges of the sliced Wasserstein distance. Our first approach hierarchically projects probability measures into low dimensional spaces before projecting them to one-dimensional space. The hierarchical projections lead to an improvement in projection complexity and enhance the expressiveness of the projection of the sliced Wasserstein distance. Our second approach considers sequential sampling for projecting directions to allow the sharing of information on new projecting directions based on the previous directions. It increases the quality of projections in terms of highlighting the difference between the probability measures and leads to a smaller number of projections, which improves the computational complexity of the sliced Wasserstein distance.

Markov Chain Monte Carlo (MCMC) is a simple, generic strategy for sampling from a probability distribution $\pi(x)$, $x\in\mathbb{R}^n$, in any dimension $n$. The Gibbs sampler is the natural MCMC algorithm to use when the one-dimensional conditional distributions of each coordinate $x_i$ of $x$ are known and easy to sample from. Although an asymptotic guarantee of convergence for this sampler has existed for some time, non-asymptotic guarantees that identify the dimension dependence of its convergence behavior have only just begun to emerge. Building on the recent work of Aditi Laddha and Santosh Vempala, in which they establish a mixing time bound for Gibbs sampling from a uniform distribution over a convex body that is polynomial in $n$, we will discuss a high-probability mixing time bound for the same sampler for log-smooth log-concave distributions.

Some recent results have shown that the so-called sliced Wasserstein distances have wildly different geometric properties from those of classical optimal transport metrics, as such they are often not suitable as direct replacements. In this talk I will discuss some of these differences, and then introduce the family of disintegrated Monge-Kantorovich metrics defined on general metric fiber bundles. These metrics may be a more suitable alternative to the sliced ones in certain settings, and are of mathematical interest in their own right, generalizing the linear optimal transport metric, and being related to measure differential equations. This talk is based on joint work with Asuka Takatsu (Tokyo Metropolitan University).

In this talk, we introduce LOT Wassmap, a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space. The algorithm is motivated by the observation that many datasets are naturally interpreted as probability measures rather than points in $\mathbb{R}^n$, and that finding low-dimensional descriptions of such datasets requires manifold learning algorithms in the Wasserstein space. Most available algorithms are based on computing the pairwise Wasserstein distance matrix, which can be computationally challenging for large datasets in high dimensions. Our algorithm leverages approximation schemes such as Sinkhorn distances and linearized optimal transport to speed-up computations, and in particular, avoids computing a pairwise distance matrix. Experiments demonstrate that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size. We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.

Generative modeling is a rapidly growing area of machine learning wherein a model is trained on samples from a probability distribution (i.e., data) so as to learn the ability to produce new (approximate) samples from the distribution. The mathematical techniques that underlie many successful approaches can be broadly categorized under information theoretic, optimal transport, and dynamical methods. Many approaches use more than one of these tools, either explicitly or implicitly. In this talk I will introduce these different mathematical tools and discuss their use in several different approaches to training generative models.

In the current stage of numerical PDE, the primary challenge lies in addressing the complexities of high dimensionality while maintaining physical fidelity in our solvers. In this presentation, I will introduce deep learning assisted particle methods aimed at mitigating some of these challenges. Two scenarios will be considered, one is for general nonlinear Wasserstein-type gradient flow, and the other is for the Landau equation in plasma physics.

We investigate the impact of multiscale data on machine learning algorithms, particularly in the context of deep learning. A dataset is multiscale if its distribution shows large variations in scale across different directions. We show that the empirical loss will inherit certain multiscale properties from the data, even if the individual loss function does not have such properties. Correspondingly, we introduce a novel gradient descent approach, drawing inspiration from multiscale algorithms used in scientific computing.