Ruiwen Shu : Flocking hydrodynamics with external potentials
- Applied Math and Analysis ( 118 Views )We study the large-time behavior of hydrodynamic model which describes the collective behavior of continuum of agents, driven by pairwise alignment interactions with additional external potential forcing. The external force tends to compete with alignment which makes the large time behavior very different from the original Cucker-Smale (CS) alignment model, and far more interesting. Here we focus on uniformly convex potentials. In the particular case of \emph{quadratic} potentials, we are able to treat a large class of admissible interaction kernels, $\phi(r) \gtrsim (1+r^2)^{-\beta}$ with `thin' tails $\beta \leq 1$ --- thinner than the usual `fat-tail' kernels encountered in CS flocking $\beta\leq\nicefrac{1}{2}$: we discover unconditional flocking with exponential convergence of velocities \emph{and} positions towards a Dirac mass traveling as harmonic oscillator. For general convex potentials, we impose a necessary stability condition, requiring large enough alignment kernel to avoid crowd dispersion. We prove, by hypocoercivity arguments, that both the velocities \emph{and} positions of smooth solution must flock. We also prove the existence of global smooth solutions for one and two space dimensions, subject to critical thresholds in initial configuration space. It is interesting to observe that global smoothness can be guaranteed for sub-critical initial data, independently of the apriori knowledge of large time flocking behavior.
Haomin Zhou : Optimal Transport on Graphs with Applications
- Applied Math and Analysis ( 127 Views )In this talk, I will present the optimal transport theory on discrete spaces. Various recent developments related to free energy, Fokker-Planck equations, as well as Wasserstein distance on graphs will be presented, some of them are rather surprising. Applications in robotics as well as Schrodinger equation on graphs will be demonstrated.
Rong Ge : Learning Two-Layer Neural Networks with Symmetric Inputs
- Applied Math and Analysis ( 110 Views )Deep learning has been extremely successful in practice. However, existing guarantees for learning neural networks are limited even when the network has only two layers - they require strong assumptions either on the input distribution or on the norm of the weight vectors. In this talk we give a new algorithm that is guaranteed to learn a two-layer neural network under much milder assumptions on the input distribution. Our algorithms works whenever the input distribution is symmetric - which means two inputs $x$ and $-x$ have the same probability.
Based on joint work with Rohith Kuditipudi, Zhize Li and Xiang Wang
Haizhao Yang : Approximation theory and regularization for deep learning
- Applied Math and Analysis ( 127 Views )This talk introduces new approximation theories for deep learning in parallel computing and high dimensional problems. We will explain the power of function composition in deep neural networks and characterize the approximation capacity of shallow and deep neural networks for various functions on a high-dimensional compact domain. Combining parallel computing, our analysis leads to an important point of view, which was not paid attention to in the literature of approximation theory, for choosing network architectures, especially for large-scale deep learning training in parallel computing: deep is good but too deep might be less attractive. Our analysis also inspires a new regularization method that achieves state-of-the-art performance in most kinds of network architectures.
Ying Cui : Modern ``Non-Optimization for Data Science
- Applied Math and Analysis ( 155 Views )We have witnessed a lot of exciting development of data science in recent years. From the perspective of optimization, many modern data-science problems involve some basic ``non’’-properties that lack systematic treatment by the current approaches for the sake of the computation convenience. These non-properties include the coupling of the non-convexity, non-differentiability and non-determinism. In this talk, we present rigorous computational methods for solving two typical non-problems: the piecewise linear regression and the feed-forward deep neural network. The algorithmic framework is an integration of the first order non-convex majorization-minimization method and the second order non-smooth Newton methods. Numerical experiments demonstrate the effectiveness of our proposed approach. Contrary to existing methods for solving non-problems which provide at best very weak guarantees on the computed solutions obtained in practical implementation, our rigorous mathematical treatment aims to understand properties of these computed solutions with reference to both the empirical and the population risk minimizations. This is based on joint work with Jong-Shi Pang, Bodhisattva Sen and Ziyu He.
Jonathan Hermon : Mixing and hitting times - theory and applications
- Applied Math and Analysis ( 108 Views )We present a collection of results, based on a novel operator maximal inequality approach, providing precise relations between the time it takes a Markov chain to converge to equilibrium and the time required for it to exit from small sets. These refine results of Aldous and Lovasz & Winkler. Among the applications are: (1) A general characterization of an abrupt convergence to equilibrium phenomenon known as cutoff. Specializing this to Ramanujan graphs and trees. (2) Proving that the return probability decay is not geometrically robust (resolving a problem of Aldous, Diaconis - Saloff-Coste and Kozma). (3) Random walk in evolving environment
Courtney Paquette : Algorithms for stochastic nonconvex and nonsmooth optimization
- Applied Math and Analysis ( 123 Views )Nonsmooth and nonconvex loss functions are often used to model physical phenomena, provide robustness, and improve stability. While convergence guarantees in the smooth, convex settings are well-documented, algorithms for solving large-scale nonsmooth and nonconvex problems remain in their infancy.
I will begin by isolating a class of nonsmooth and nonconvex functions that can be used to model a variety of statistical and signal processing tasks. Standard statistical assumptions on such inverse problems often endow the optimization formulation with an appealing regularity condition: the objective grows sharply away from the solution set. We show that under such regularity, a variety of simple algorithms, subgradient and Gauss Newton like methods, converge rapidly when initialized within constant relative error of the optimal solution. We illustrate the theory and algorithms on the real phase retrieval problem, and survey a number of other applications, including blind deconvolution and covariance matrix estimation.
One of the main advantages of smooth optimization over its nonsmooth counterpart is the potential to use a line search for improved numerical performance. A long-standing open question is to design a line-search procedure in the stochastic setting. In the second part of the talk, I will present a practical line-search method for smooth stochastic optimization that has rigorous convergence guarantees and requires only knowable quantities for implementation. While traditional line-search methods rely on exact computations of the gradient and function values, our method assumes that these values are available up to some dynamically adjusted accuracy that holds with some sufficiently high, but fixed, probability. We show that the expected number of iterations to reach an approximate-stationary point matches the worst-case efficiency of typical first-order methods, while for convex and strongly convex objectives it achieves the rates of deterministic gradient descent.
Javier Gomez Serrano : The SQG equation
- Applied Math and Analysis ( 113 Views )There has been high scientific interest to understand the behavior of the surface quasi-geostrophic (SQG) equation because it is a possible model to explain the formation of fronts of hot and cold air and because it also exhibits analogies with the 3D incompressible Euler equations. It is not known at this moment if this equation can produce singularities or if solutions exist globally. In this talk I will discuss some recent works on the existence of global solutions.
Lei Li : Some algorithms and analysis for first order interacting particle systems
- Applied Math and Analysis ( 112 Views )We focus on first order interacting particle systems, which can be viewed as overdamped Langevin equations. In the first part, we will look at the so-called random batch methods (RBM) for simulating the interacting particle systems. The algorithms are motivated by the mini-batch idea in machine learning. For some special cases, we show the convergence of RBMs for the first marginal under Wasserstein distance. In the second part, we look at the Coulomb interaction in 3D space. We show that as the number of particles go to infinity, almost surely, the empirical measure converges in law to weak solutions of the limiting nonlinear Fokker-Planck equation. This talk is based on joint works with Shi Jin (Shanghai Jiao Tong), Jian-Guo Liu (Duke University) and Pu Yu (Peking University).
Qin Li : Low rankness in forward and inverse kinetic theory
- Applied Math and Analysis ( 112 Views )Multi-scale kinetic equations can be compressed: in certain regimes, the Boltzmann equation is asymptotically equivalent to the Euler equations, and the radiative transfer equation is asymptotically equivalent to the diffusion equation. A lot of detailed information is lost when the system passes to the limit. In linear algebra, it is equivalent to being of low rank. I will discuss such transition and how it affects the computation: mainly, in the forward regime, inserting low-rankness could greatly advances the computation, while in the inverse regime, the system being of low rank typically makes the problems significantly harder.
Mateusz Michalek : Algebraic Phylogenetics
- Applied Math and Analysis ( 117 Views )Phylogenetics is a science that aims at reconstructing the history of evolution. Phylogenetic tree models are generalizations of well-known Markov chains. In my talk I will present so-called group-based models and their relations to algebra and combinatorics. To a model of evolution one associates an algebraic variety that is the Zariski closure of points corresponding to probability distributions allowed by the model. Many important varieties arise by this construction, e.g. secant varieties of Segre products of projective spaces. It turns out that group-based models provide toric varieties. In particular, they may be studied using tools from toric geometry relating to combinatorics of lattice polytopes.
Elina Robeva : Orthogonal Tensor Decomposition
- Applied Math and Analysis ( 107 Views )A symmetric tensor is orthogonally decomposable if it can be written as a linear combination of tensor powers of n orthonormal vectors. Such tensors are interesting because their decomposition can be found efficiently. We study their spectral properties and give a formula for all of their eigenvectors. We also give equations defining all real symmetric orthogonally decomposable tensors. Analogously, we study nonsymmetric orthogonally decomposable tensors, describing their singular vector tuples and giving polynomial equations that define them. In an attempt to extend the definition to a larger set of tensors, we define tight-frame decomposable tensors and show that for certain equiangular tight frames they too can be decomposed via the tensor power method.
Tom Beale : Finite Difference Methods for Boundary Value Problems: Using Interface Problems
- Applied Math and Analysis ( 109 Views )Finite difference methods are awkward for solving boundary value problems, such as the Dirichlet problem, with general boundaries, but they are well suited for interface problems, which have prescribed jumps in an unknown across a general interface or boundary. The two problems can be connected through potential theory: The Dirichlet boundary value problem is converted to an integral equation on the boundary, and the integrals can be thought of as solutions to interface problems. Wenjun Ying et al. have developed a practical method for solving the Dirichlet problem, and more general ones, by solving interface problems with finite difference methods and iterating to mimic the solution of the integral equation. We will describe some analysis which proves that a simplified version of Ying's method works. A recent view of classical potential theory leads to a finite difference version of the theory in which, remarkably, the crude discrete operators have much of the structure of the exact operators. This simplified method produces the Shortley-Weller solution of the Dirichlet problem. Details can be found at arxiv.org/abs/1803.08532 .
Noé Cuneo : Non-Equilibrium Steady States for Networks of Oscillators
- Applied Math and Analysis ( 99 Views )Non-equilibrium steady states for chains of oscillators interacting with stochastic heat baths at different temperatures have been the subject of several studies. In this talk I will discuss how to generalize these results to multidimensional networks of oscillators. I will first introduce the model and motivate it from a physical point of view. Then, I will present conditions on the topology of the network and on the interaction potentials which imply the existence and uniqueness of the non-equilibrium steady state, as well as exponential convergence to it. The two main ingredients of the proof are (1) a controllability argument using Hörmander's bracket criterion and (2) a careful study of the high-energy dynamics which leads to a Lyapunov-type condition. I will also mention cases where the non-equilibrium steady state is not unique, and cases where its existence is an open problem. This is joint work with J.-P. Eckmann, M. Hairer and L. Rey-Bellet, Electronic Journal of Probability 23(55): 1-28, 2018 (arXiv:1712.09413).
Weijie Su : Taming the Devil of Gradient-based Optimization Methods with the Angel of Differential Equations
- Applied Math and Analysis ( 135 Views )This talk introduces a framework that uses ordinary differential equations to model, analyze, and interpret gradient-based optimization methods. In the first part of the talk, we derive a second-order ODE that is the limit of Nesterovs accelerated gradient method for non-strongly objectives (NAG-C). The continuous-time ODE is shown to allow for a better understanding of NAG-C and, as a byproduct, we obtain a family of accelerated methods with similar convergence rates. In the second part, we begin by recognizing that existing ODEs in the literature are inadequate to distinguish between two fundamentally different methods, Nesterovs accelerated gradient method for strongly convex functions (NAG-SC) and Polyaks heavy-ball method. In response, we derive high-resolution ODEs as more accurate surrogates for the three aforementioned methods. These novel ODEs can be integrated into a general framework that allows for a fine-grained analysis of the discrete optimization algorithms through translating properties of the amenable ODEs into those of their discrete counterparts. As the first application of this framework, we identify the effect of a term referred to as gradient correction in NAG-SC but not in the heavy-ball method, shedding insight into why the former achieves acceleration while the latter does not. Moreover, in this high-resolution ODE framework, NAG-C is shown to boost the squared gradient norm minimization at the inverse cubic rate, which is the sharpest known rate concerning NAG-C itself. Finally, by modifying the high-resolution ODE of NAG-C, we obtain a family of new optimization methods that are shown to maintain the accelerated convergence rates as NAG-C for smooth convex functions. This is based on joint work with Stephen Boyd, Emmanuel Candes, Simon Du, Michael Jordan, and Bin Shi.
Guillaume Bal : Topological Insulators and obstruction to localization
- Applied Math and Analysis ( 127 Views )Topological insulators (TIs) are materials characterized by topological invariants. One of their remarkable features is the asymmetric transport observed at the interface between materials in different topological phases. Such transport is itself described by a topological invariant, and therefore ``protected" against random perturbations. This immunity makes TIs extremely promising for many engineering applications and actively researched.
In this talk, we present a PDE model for such TIs, introduce a topology based on indices of Fredholm operators, and analyze the influence of random perturbations. We confirm that topology is an obstruction to Anderson localization, a hallmark of wave propagation in strongly heterogeneous media in the topologically trivial case and to some extent quantify what is or is not protected topologically. For instance, a quantized amount of transmission is protected while back-scattering, a practical nuisance, is not.
Anna Mazzucato : Optimal mixing and irregular transport by incompressible flows
- Applied Math and Analysis ( 99 Views )I will discuss transport of passive scalars by incompressible flows (such as a die in a fluid) and measures of optimal mixing and stirring under physical constraint on the flow. In particular, I will present recent results concerning examples of flows that achieve the optimal theoretical rate in the case of flows with a prescribed bound on certain Sobolev norms of the associated velocity, such as under an energy or an enstrophy budget. These examples are related to examples of (instantaneous) loss of Sobolev regularity for solutions to linear transport equations with non-Lipschitz velocity.
Almut Burchard : Geometry in Wasserstein Space: Geodesics, Gradients, and Curvature, from an Eulerian Point of View
- Applied Math and Analysis ( 95 Views )The optimal transportation problem defines a notion of distance in the space of probability measures over a manifold, the *Wasserstein space*. In his 1994 Ph.D. thesis, McCann discovered that this space is a length space: the distance between probability measures is given by the length of minimizing geodesics called *displacement interpolants*. A surprising number of important functionals in physics and geometry turned out to be geodesically convex. In contrast with classical function spaces, the Wasserstein space is not a linear space, but rather an infinite-dimensional analogue of a Riemannian manifold. This analogy has motivated new functional inequalities and new methods for studying evolution equations; however, it has rarely been used in rigorous proofs. I will describe recent work with Benjamin Schachter on differentiating functionals (such as the entropy or the Dirichlet integral) along displacement interpolants. Starting from an Eulerian formulation for the underlying optimal transportation problem, we take advantage of the system of transport equations to compute derivatives of arbitrary order, for probability densities that need not be smooth.
Jiequn Han : Deep Learning-Based Numerical Methods for High-Dimensional Parabolic PDEs and Forward-Backward SDEs
- Applied Math and Analysis ( 108 Views )Developing algorithms for solving high-dimensional partial differential equations (PDEs) and forward-backward stochastic differential equations (FBSDEs) has been an exceedingly difficult task for a long time, due to the notorious difficulty known as the curse of dimensionality. In this talk we introduce a new type of algorithms, called "deep BSDE method", to solve general high-dimensional parabolic PDEs and FBSDEs. Starting from the BSDE formulation, we approximate the unknown Z-component by neural networks and design a least-squares objective function for parameter optimization. Numerical results of a variety of examples demonstrate that the proposed algorithm is quite effective in high-dimensions, in terms of both accuracy and speed. We furthermore provide a theoretical error analysis to illustrate the validity and property of the designed objective function.
Ilse Ipsen : An Introduction to Randomized Algorithms for Matrix Computations
- Applied Math and Analysis ( 135 Views )The emergence of massive data sets, over the past twenty or so years, has lead to the development of Randomized Numerical Linear Algebra. Fast and accurate randomized matrix algorithms are being designed for applications like machine learning, population genomics, astronomy, nuclear engineering, and optimal experimental design. We give a flavour of randomized algorithms for the solution of least squares/regression problems. Along the way we illustrate important concepts from numerical analysis (conditioning and pre-conditioning), probability (concentration inequalities), and statistics (sampling and leverage scores).
Jun Kitagawa : Free discontinuity regularity and stability in optimal transport
- Applied Math and Analysis ( 91 Views )Regularity of solutions in the optimal transport problem requires very rigid hypotheses (e.g., convexity of certain sets). When such conditions are not available, one can consider the question of partial regularity, in other words, the in-depth analysis of the structure of singular sets. In this talk, I will discuss the regularity of the set of ``free singularities`` which arise in an optimal transport problem with inner product cost, from a connected set to a disconnected set, along with the stability of such sets under suitable perturbations of the data involved. Some of these results are proven via a non-smooth implicit function theorem for convex functions, which is of independent interest. This talk is based on joint work with Robert McCann.
Wencai Liu : Spectral transitions for Schr\odinger operators with decaying potentials and Laplacians on asymptotically flat (hyperbolic) manifolds
- Applied Math and Analysis ( 108 Views )We apply piecewise constructions and gluing technics to construct asymptotically flat (hyperbolic) manifolds such that associated Laplacians have dense embedded eigenvalues or singular continuous spectra. The method also allows us to provide various examples of operators with embedded singular spectra, including perturbed periodic operators, periodic Jacobi operators, and Stark operators. We establish the asymptotic behavior (WKB for example) of eigensolutions under small perturbations, which implies certain rules for the absence of singular spectra. As a result, several sharp spectral transitions (even criteria) for a single (finitely many or countably many) embedded eigenvalues, singular continuous spectra and essential supports of spectral measures are obtained. The talk is based on several papers, some joint with Jitomirskaya and Ong.
Dana Mendelson : Random data Cauchy theory for some nonlinear dispersive equations
- Applied Math and Analysis ( 96 Views )In this talk, I will discuss several problems on nonlinear wave and dispersive equations with random initial data, including the energy critical nonlinear wave and Schroedinger equations, and derivative nonlinear wave equations. I will present several almost sure well-posedness and scattering results for these equations and contrast the ways in which random data techniques can be exploited in these different contexts.
Roman Shvydkoy : Topological models of emergent dynamics
- Applied Math and Analysis ( 105 Views )In this talk we will introduce a new class of flocking models that feature emergence of global alignment via only local communication. Such models have been sought for since the introduction of Cucker-Smale dynamics which showed global unconditional alignment for models with substantially strong non-local interaction kernels. We introduce a set of new structural components into the communication protocol, including singular kernel, and topological adaptive diffusion, that enhance alignment mechanisms with purely local interactions. We highlight some challenges that arise in the problem of global well-posendess and stability of flocks.
Alexander Cloninger : Dual Geometry of Laplacian Eigenfunctions and Anisotropic Graph Wavelets
- Applied Math and Analysis ( 87 Views )We discuss the geometry of Laplacian eigenfunctions on compact manifolds and combinatorial graphs. The `dual' geometry of Laplacian eigenfunctions is well understood on the torus and euclidean space, and is of tremendous importance in various fields of pure and applied mathematics. The purpose of this talk is to point out a notion of similarity between eigenfunctions that allows to reconstruct that geometry. Our measure of `similarity' between eigenfunctions is given by a global average of local correlations, and its relationship to pointwise products. This notion recovers all classical notions of duality but is equally applicable to other (rough) geometries and graphs; many numerical examples in different continuous and discrete settings illustrate the result. This talk will also focus on the applications of discovering such a dual geometry, namely in constructing anisotropic graph wavelet packets and anisotropic graph cuts.
Andrej Zlatos : On Universal Mixers
- Applied Math and Analysis ( 122 Views )The problem of mixing via incompressible flows is classical and rich with connections to several branches of analysis including PDE, ergodic theory, and topological dynamics. In this talk I will discuss some recent developments in the area and then present a construction of universal mixers - incompressible flows that asymptotically mix arbitrarily well general solutions to the corresponding transport equation - in all dimensions. This mixing is in fact exponential in time (i.e., essentially optimal) for any initial condition with at least some degree of regularity, while there exists no uniform mixing rate for all measurable initial conditions.
Kui Ren : Inverse problems to system of diffusion equations with internal data
- Applied Math and Analysis ( 102 Views )We will consider some inverse coefficient problems to system of linear and semilinear diffusion equations where the aim is to recover unknown parameters in the equations from partial information on the solutions to the systems. We present some recent theoretical and numerical results, and point out possible applications of such problems in imaging.
Mengdi Wang : Primal-Dual Pi Learning Using State and Action Features
- Applied Math and Analysis ( 92 Views )We survey recent advances on the complexity and methods for solving Markov decision problems (MDP) and Reinforcement Learning (RL) with finitely many states and actions - a basic mathematical model for reinforcement learning.
For model reduction of large scale MDP in reinforcement learning, we propose a bilinear primal-dual pi learning method that utilizes given state and action features. The method is motivated from a saddle point formulation of the Bellman equation. The sample complexity of bilinear pi learning depends only on the number of parameters and is variant with respect to the dimension of the problem.
In the second part we study the statistical state compression of general Markov processes. We propose a spectral state compression method for learning the state features from data. The state compression method is able to sketch a black-box Markov process from its empirical data and output state features, for which we provide both minimax statistical guarantees and scalable computational tools.
Yifei Lou : Nonconvex Approaches in Data Science
- Applied Math and Analysis ( 95 Views )Although big data is ubiquitous in data science, one often faces challenges of small data, as the amount of data that can be taken or transmitted is limited by technical or economic constraints. To retrieve useful information from the insufficient amount of data, additional assumptions on the signal of interest are required, e.g. sparsity (having only a few non-zero elements). Conventional methods favor incoherent systems, in which any two measurements are as little correlated as possible. In reality, however, many problems are coherent. I will present a nonconvex approach that works particularly well in the coherent regime. I will also address computational aspects in the nonconvex optimization. Various numerical experiments have demonstrated advantages of the proposed method over the state-of-the-art. Applications, ranging from super-resolution to low-rank approximation, will be discussed.
Rongjie Lai : Understanding Manifold-structured Data via Geometric Modeling and Learning
- Applied Math and Analysis ( 105 Views )Analyzing and inferring the underlying global intrinsic structures of data from its local information are critical in many fields. In practice, coherent structures of data allow us to model data as low dimensional manifolds, represented as point clouds, in a possible high dimensional space. Different from image and signal processing which handle functions on flat domains with well-developed tools for processing and learning, manifold-structured data sets are far more challenging due to their complicated geometry. For example, the same geometric object can take very different coordinate representations due to the variety of embeddings, transformations or representations (imagine the same human body shape can have different poses as its nearly isometric embedding ambiguities). These ambiguities form an infinite dimensional isometric group and make higher-level tasks in manifold-structured data analysis and understanding even more challenging. To overcome these ambiguities, I will first discuss modeling based methods. This approach uses geometric PDEs to adapt the intrinsic manifolds structure of data and extracts various invariant descriptors to characterize and understand data through solutions of differential equations on manifolds. Inspired by recent developments of deep learning, I will also discuss our recent work of a new way of defining convolution on manifolds and demonstrate its potential to conduct geometric deep learning on manifolds. This geometric way of defining convolution provides a natural combination of modeling and learning on manifolds. It enables further applications of comparing, classifying and understanding manifold-structured data by combing with recent advances in deep learning.