Applied Math Colloquium

Abstract: The tropical semiring consists of the real numbers and infinity along with two binary operations: addition defined by the max or min operation and multiplication. Tropical algebra is the tropical analogue of linear algebra, working with matrices with entries on the extended real line. There are analogues of eigenvalues and singular values of matrices, and matrix factorizations in the tropical setting, and when combined with a valuation map these analogues offer `order of magnitude' approximations to eigenvalues and singular values, and factorizations of matrices in the usual algebra. What makes tropical algebra a useful tool for numerical linear algebra is that these tropical analogues are usually cheaper to compute than those in the conventional algebra. They can then be used in the design of preprocessing steps to improve the numerical behaviour of algorithms. In this talk I will review the contributions of tropical algebra to numerical linear algebra and discuss recent results on the selection of Hungarian scalings prior to solving linear systems and eigenvalue problems.

Abstract: In this talk, I will present some new results on controlling the Liouville (or continuity) equation for the probability density of the state of a smooth controlled dynamical system starting from a random initial state. This problem, first formulated and studied by Roger Brockett, makes contact with the theory of optimal transportation and with nonlinear controllability. I will discuss two settings: (1) controllable linear systems with finite-dimensional states and controls and (2) nonlinear controlled systems defined on smooth manifolds. For the latter, I will sketch the analysis of the complexity of implementing orientation-preserving diffeomorphisms by means of piecewise constant feedback controls. This estimate, which provides a quantitative version of a key result of Agrachev and Caponigro, can be used to assess the complexity of approximating smooth dynamical systems by means of continuous-time neural nets (so-called neural ODEs).

Abstract: Particle methods are a fundamental tool for computing flows in the space of probability measures, whether the flow describes the evolution of fluid in a porous medium, agents in a robotic swarm, or samples transported to a desired target distribution. As a counterpoint to classical stochastic particle methods, such as Langevin dynamics, in today’s talk, I will present recent progress on deterministic particle methods, including (1) a nonlocal approximation of dynamic optimal transport, with state and control constraints, and (2) a nonlocal approximation of general nonlinear diffusion equations.

Abstract: The main building block of large language models is matrix multiplication, which is often bottlenecked by the speed of loading these matrices from memory. A possible solution is to trade accuracy for speed by storing the matrices in low precision ("quantizing" them). In recent years a number of quantization algorithms with increasingly better performance were proposed (e.g., SmoothQuant, Brain compression, GPTQ, QuIP, QuIP#, QuaRot,SpinQuant). In this work, we prove an information theoretic lower bound on achievable accuracy of computing matrix product as a function of compression rate (number of bits per matrix entry). We also construct a quantizer (based on nested lattices) achieving this lower bound.

Based on a joint work with Or Ordentlich (HUJI), arXiv:2410.13780.

Abstract: Sampling high-dimensional probability distributions is a common task in Science, Engineering, and Statistics. Monte Carlo (MC) samplers are the methods of choice to perform these calculations, but they are often plagued by slow convergence properties. I will discuss recent advances in generative modeling that can be used to assist nonequilibrium MC methods and improve their performance. These approaches are based on using MC data to learn how to dynamically transport a measure towards the target of interest, then use use this transport to generate more data, in a positive feedback loop. As a specific illustration, I will present a variant of Neals’ annealed importance sampling (AIS), in which the stochastic differential equation used to generate the data in AIS is augmented with an additional drift term that enhance the method’s capabilities. This drift can be learned variational via minimization of a tractable objective function that can be shown to control the Kullback-Leibler divergence of the estimated distribution from its target. I will also illustrate the method on standard benchmarks, such as high-dimensional Gaussian mixture distributions, and a model from statistical lattice field theory.

This is joint work with Michael Albergo.