Applied Math Colloquium

Abstract: Constraint satisfaction problems (CSPs in short) are among the most important computational problems studied in Theoretical Computer Science. This talk will focus on a recent line of study addressing the complexity of approximating satisfiable instances of CSPs, and connections of this study to multi-player parallel repetition theorems, property testing and combinatorics.

Based mostly on joint works with Amey Bhangale, Subhash Khot and Yang P. Liu.

Abstract: Analysis of real-world physical and engineering systems is characterized by unique computational challenges associated with high dimensionality of parameter spaces, large cost of simulations or experiments, as well as existence of uncertainty. For a wide range of these problems the goal is to either quantify uncertainty and compute risk for critical events, optimize parameters or control strategies, and/or making decisions. In this talk we will discuss two aspects related to the modeling of extreme events: i) optimal sampling of data for the characterization of extreme events, and ii) extreme-event aware learning, i.e. learning methods that do not necessarily assume the existence of extreme events in the training data.

In the first part of the talk, we will discuss how Bayesian active learning provides a flexible framework for i) identifying the most informative data for extremes, which is relevant for engineering problems where optimal experimental design is feasible, or ii) quantify the value of data in a prescribed dataset, e.g. relevant for climate modeling. Despite its attractive properties, the Bayesian framework is often prohibitively expensive in terms of the required simulations or experiments, even in the active learning setting. We introduce a new class of acquisition functions that utilize a likelihood-weighted ratio that accounts for the importance of the output relative to the input. This ratio acts essentially as a probabilistic sampling weight and guides the sampling algorithm towards regions of the input space where the objective function assumes abnormal values, resulting in significant savings of computational or experimental resources needed for convergence. We show that the adopted acquisition functions can be rigorously derived as the asymptotic limit of an optimal acquisition function that has a minimax form over a functional space. Subsequently, we demonstrate their favorable properties compared to standard methods on benchmark functions commonly used in the optimization community as well as real world applications involving turbulence, fluid-structure interaction problems and optimal sensor placement.

In the second part of the talk, we examine the problem of learning for extremes without the assumption of extreme events in the training data. We introduce the framework of Extreme Event Aware (e2a or eta) or $\eta$-learning which does not assume the existence of extreme events in the available data. $\eta$-learning reduces the uncertainty even in `unchartered' extreme event regions, by enforcing the extreme event statistics of a few observables during training, which can be available or assumed through qualitative arguments or other forms of analysis. This type of statistical regularization results in models that fit the observed data, but also enforces consistency with the prescribed or assumed statistics of some observables, enabling the generation of unprecedented extreme events even when the training data lack extremes therein. A series of theoretical results based on optimal transport theory offers a rigorous justification and highlights the optimality of the introduced method. The favorable properties $\eta$-learning are demonstrated in synthetic examples as well as a real world example involving modeling extreme precipitation events.

Abstract: Pentamode materials are a class of materials that are useful for guiding stress. In particular, they have been proposed for acoustic cloaking by guiding stress around objects and have been physically constructed. A key feature of pentamode materials is that each vertex in the material is the junction of 4 double cone elements. Thus, the tension in one element determines the tension in the other elements, and by extension uniquely determines the stress in the entire metamaterial. Here we show how this key feature can be extended to discrete wire networks, supporting forces at the terminal nodes and which may have internal nodes where no forces are applied. In usual wire or cable networks, such as in a bridge or bicycle wheel, one distributes the forces by adjusting the tension in the wires. Here our discrete networks provide an alternative way of distributing the forces through the geometry of the network. In particular the network can be chosen so it is uniloadable, i.e. supports only one set of forces at the terminal nodes. Such uniloadable networks provide the natural generalization of pentamode materials to discrete networks. We extend such a problem to compression-only 'strut nets' subjected to fixed and reactive nodal loads. These systems provide discrete element models of masonry bodies. In particular, we solve the arch problem where one wants the strut net to avoid a given set of obstacles and also allow some of the forces to be reactive ones. This is joint work with Ada Amendola, Guy Bouchitte, Andrej Cherkaev, Antonio Fortunato, Fernando Fraternali, Ornella Mattei, and Pierre Seppecher.