Game theoretic approach to numerical analysis and algorithm design.
The process of scientific discovery is oftentimes based on a process of trail and error, plain guesswork and brilliant insight.Can this process be, to some degree, facilitated, in the design of numerical solvers, through an Uncertainty Quantification approach to numerical approximation? It turns out that the three main approaches to uncertainty quantification (worst case, bayesian, adversarial game/decision theory)can be translated into three main approaches to numerical analysis and algorithm design. The worst case approach is the classical approach of numerical analysis. The bayesian approach is the average case approach of information based complexity and bayesian numerical analysis which is currently reemerging as probabilistic numerics. The game theoretic approach stems from the observation that to compute fast one must compute with partial information over hierarchies of levels of complexity. This process of computing with partial information can be turned into a process of playing repeated adversarial games against the missing information. The optimal (mixed/randomized) strategies for playing such games can be used to automate the process of discovery in numerical analysis and algorithm design. In the game theoretic approach errors have a dual worst case and bayesian interpretation that provide rigorous complexity/accuracy guarantees on algorithms and enable natural couplings between model uncertainties and numerical discretization uncertainties.For more see the following mini-tutorial [ Part I| Part II| Part III] and the following [ paper]
During the past century the need to solve large complex problems in applications such as fluid dynamics, neutron transport or ballistic prediction drove the parallel development of computers and numerical methods for solving ODEs and PDEs. It is now clear that this development lead to a paradigm shift. Before: each new PDE required the development of new theoretical methods and the employment of large teams of mathematicians and physicists; in most cases, information on solutions was only qualitative and based on general analytical bounds on fundamental solutions. After: mathematical analysis and computer science worked in synergy to give birth to robust numerical methods (such as finite element methods) capable of solving a large spectrum of PDEs without requiring the level of expertise of an A.~L.~Cauchy or level of insight of a R.~P.~Feynman. This transformation can be traced back to sophisticatedcalculations performed by arrays of human computers organized as parallel clusters such as in the pioneering work of Lewis Fry Richardson, who in 1922 had a room full of clerks attempt to solve finite-difference equations for the purposes of weather forecasting, and the 1947 paper by John Von Neumann and Herman Goldstine on Numerical Inverting of Matrices ofHigh Order.Although Richardson's predictions failed due to the use of unfiltered data/initial conditions/equations and large time-steps not satisfying the CFL stability condition, his vision was shared by Von Neumann in his proposal of the Meteorology Research Project to the U.S. Navy in 1946, qualified by Platzman as ``perhaps the most visionary prospectus for numerical weather prediction since the publication of Richardson’s book a quarter-century earlier.''The past century has also seen a steady increase in the need of estimating and predicting complex systems and making (possibly critical) decisions with limited information. Although computers have made possible the numerical evaluation of sophisticated statistical models, these models are still designed by humans through the employment of multi-disciplinary teams of physicists, computer scientists and statisticians. Contrary to the original human computers(such as the ones pioneered by L. F. Richardson or overseen by R. P. Feynman at Los Alamos), these human teams do not follow a specific algorithm (such as the one envisioned in Richardson's Forecast Factory where 64,000 human computers would have been working in parallel and at high speed to compute world weather charts) because there is currently no known recipe or algorithm for dividing the design of a statistical model into a sequence of arithmetic operations. Furthermore, while human computers were given a specific PDE or ODE to solve, these human teams are not given a wellposed problem with a well defined notion of solution. As a consequence different human teams come up with different solutions to the design of the statistical model along with different estimates on uncertainties.Indeed enabling computers to think as humans have the ability to do when faced with uncertainty is challenging in several major ways: (1) There is currently no known recipe or algorithm for dividing the design of a statistical model into a sequence of arithmetic operations (2) Formulating the search for an optimal statistical estimator/model as a wellposed problem is not obvious when information on the system of interest is incomplete and comes in the form of a complex combination of sample data, partial knowledge of constitutive relations and a limited description of the distribution of input random variables. (3) The space of admissible scenarios along with the space of relevant information,assumptions, and/or beliefs, tend to be infinite dimensional, whereas calculus on a computer is necessarily discrete and finite.The purpose of this research is to explore and develop the foundations of a rigorous/rational framework for the scientific computation of optimal statistical estimators/models and the optimal quantification of uncertaintiesfor complex systems. The emerging questions lead to many challenging problems in Decision Theory, Machine Learning, Bayesian Inference, Stochastic Optimization, Robust Optimization, and Information Based Complexity, the most fundamental of these being the simultaneous emphasis on computation and performance as in Machine Learning initiated by Valiant.For more see the following talks [ talk 1| talk 2 | talk 3 | talk 4 ] and the following papers [ paper 1, paper 2,paper 3 ]
Stochastic and Multiscale analysis.
Anomalous diffusion in systems characterized by an infinite number of scales. Homogenization and inverse homogenizationwith a continuum of scales. Geometric integration of stochastic Hamiltonian systems. Structure preserving integrationof (possibly stochastic) multiscale systems with hidden slow variables. Super-resonnance. Control via parametric resonance.Davies’ and periodization conjectures in homogenization. For more see [ slides | slides| slides| slides]
Fast solvers, theory and algorithms.
Scalable linear solvers play an important role in science and industry and are characterized by a large degreeof diversity. Although, as affirmed by Sard, no numerical approximation method can be universal, one may wonder if some degree of universality could be achieved for a large class of linear operators?The game theoretic approach appears to provide a positive answer to this question by leading toscalable (of rigorous near-linear complexity) numerical solvers for a large class of linear operators that include arbitrary continuous linear bijections on Sobolev spaces and dense kernel matrices.Surprisingly these solvers also perform, for a large of operators, an approximate PCA/eigen-subspace decompositionin near-linear complexity, For positive symmetric matrices, this corresponds to a diagonalization into uniformlywell conditioned and sparse blocks.For more see the following mini-tutorial [ Part I| Part II| Part III] and the following papers [ paper 1, paper 2,paper 3]
Operator adapted wavelets.
The application of the game theoretic approach to the problem of approximating solutions of linear operatorsleads to the identification of elementary gambles/bets (gamblets) for playing such games. These gamblets are essentially operator adapted wavelets (gamblets) satisfying three properties: (1) scale orthogonality (in operator scalar product, which leads to a a block-diagonalization of the operator) (2) well-conditioned linear systems (which leads to blocks of uniformly bounded condition numbers) (3) localization or exponential decay (which leads to sparse blocks).These gamblets, which can also be interpreted as Wannier functions, i.e. linear combinations of eigenfunctions concentrated around given eigenvalues that also remain concentrated in space, can be used to compress the operator and its inverse into sums of sparse/localized factors.For more see the following mini-tutorial [ Part I| Part II| Part III] and the following [ paper]
Stochastic and derandomization calculus in infinite dimensional spaces.
The worst case, bayesian and decision theory approaches to Uncertainty Quantification require development of a form of calculus enabling the manipulation of infinite dimensional information structures involving the resolution of optimization (min, max and minimax) problems over spaces of measures and functions and spaces of measures over measures and functions.Another motivation for the development of this calculus is its potential application to (1) the design of fast, robust and scalable numerical solvers and the analysis of partial differential equations (2) model form uncertainty quantification and design (3) model reduction. Although these applications may appear, at first glance, dissimilar, they are all based on the efficient processing of incomplete information with limited computational resources (i.e., complexity management capabilities constraints): (1) fast and robust computation requires computation with partial information (this concept forms the core of Information Based Complexity where it is also augmented by concepts of contaminated and priced information associated with, for example, truncation errors and the cost of numerical operations) (2) model form UQ and design require the management and processing of epistemic uncertainties and limited data (3) model reduction requires the approximation of the full state of a complex system through operations performed on a few (coarse/reduced) variables. Examples of applications include Optimal Uncertainty Quantification and the reduction of infinite dimensional optimization problems over measures and functions to finite dimensional ones [ slides], the identification of new Selberg identities [ slides],the quantification of the robustness of Bayesian inference under finite information [ slides], the identification ofGaussian fields as optimal mixed strategies for the game theoretic approach to numerical approximation [ slides].
Research supported by
“Technology, in common with many other activities, tends toward avoidance of risks by investors. Uncertainty is ruled out if possible. People generally prefer the predictable. Few recognize how destructive this can be, how it imposes severe limits on variability and thus makes whole populations fatally vulnerable to the shocking ways our universe can throw the dice.” Frank Herbert (Heretics of Dune)