Mathematical Sciences Colloquium

Traditional numerical methods based on expensive matrix factorizations struggle with the scale of modern scientific applications. For example, kernel-based algorithms take a data set of size N, form the kernel matrix of size N x N, and then perform an eigendecomposition or inversion at a cost of O(N^3) operations. For data sets of size N >= 10^5, kernel learning is too expensive, straining the limits of personal workstations and even dedicated computing clusters. Randomized iterative methods have emerged as faster alternatives to the classical approaches. These algorithms combine random exploration of matrix structures with information about which structures are most important, leading to significant speed-ups.

In this talk, I review recent developments concerning two randomized algorithms. The first is "randomized block Krylov iteration", which uses an array of random Gaussian test vectors to probe a large data matrix in order to provide a randomized principal component analysis. Remarkably, this approach works well even when the matrix of interest is not low-rank. The second algorithm is "randomly pivoted Cholesky decomposition", which iteratively samples columns from a positive semidefinite matrix using a novelty metric and reconstructs the matrix from the randomly selected columns. Ultimately, both algorithms furnish a randomized approximation of an N x N matrix with a reduced rank k << N, which enables fast inversion or singular value decomposition at a cost of O(N k^2) operations. The speed-up factor from N^3 to N k^2 operations can be 3 million. The newest algorithms achieve this speed-up factor while guaranteeing performance across a broad range of input matrices.

Time-harmonic scattering in variable media can often be modeled by linear elliptic partial differential equations. Such equations pose several numerical challenges. For example, they can be intrinsically ill-conditioned, necessitate the imposition of radiation conditions, and produce pollution errors when discretized with standard finite difference or finite element methods.

To avoid these issues, it is often convenient to first reformulate the differential equation as an integral equation.  The tradeoffs are that an integral operator with a singular kernel must be discretized and that the resulting linear system that must be inverted is dense. Sometimes, the latter issue can be handled using a fast matrix-vector product algorithm (e.g., the fast Fourier transform or the fast multipole method) paired with an iterative solver (e.g., GMRES). However, this approach can be prohibitively slow when there is a large amount of backscattering and when multiple incident fields are of interest. In these cases, it is better to use direct solvers.

In this talk, I describe some recent projects on developing direct solvers in this regime with applications to acoustic scattering and metasurface design.

Optimization problems involving uncertainty are central to various domains, including modern statistics and data science. Despite their ubiquity, finding efficient algorithms which provide a solution to these problems remains a major challenge. Interestingly, many random optimization problems share a common feature, dubbed as a statistical-computational gap: while the optimal value can be pinpointed non-constructively, known polynomial-time algorithms find strictly sub-optimal solutions and no better algorithm is known.

In this talk, I will discuss a theoretical framework for understanding the fundamental computational limits of such problems. This framework is based on the Overlap Gap Property (OGP), an intricate geometrical property which is known to be a barrier for large classes of algorithms. I will first focus on the symmetric binary perceptron (SBP), a model for classifying/storing random patterns as well as a random constraint satisfaction problem, widely studied in probability, computer science, and statistical physics. I will show how the OGP framework yields nearly sharp lower bounds against the classes of stable algorithms and online algorithms for the SBP. These classes capture the best known algorithms for the SBP and many other random models. I will then demonstrate how the same framework extends to other models, including the random number balancing problem, which is closely related to the design of randomized controlled trials, as well as its planted counterpart.

Our results for online algorithms are the first essentially tight unconditional lower bounds in the online setting, and our results for stable algorithms are the first applications of Ramsey Theory in the study of the limits of algorithms. More importantly, our techniques yield new toolkits for studying statistical-computational gaps in other random models.

Abstract: Sparse coding is a technique of representing data as a sparse linear combination of a set of vectors. This representation facilitates computation and analysis of high-dimensional data that is prevalent in many applications. We study sparse coding in the setting where the set of vectors define a unique Delaunay triangulation. We propose a weighted l1 regularizer and show that it provably yields a sparse solution. Further, we show stability of sparse codes using the Cayley-Menger determinant. We make connections to dictionary learning, manifold learning and computational geometry. We discuss an optimization algorithm to learn the sparse codes and optimal set of vectors given a set of data points. Finally, we show numerical experiments to show that the resulting sparse representations give competitive performance in the problem of clustering.  

Neuronal network connectivity demonstrates sparsity on multiple spatial scales and natural stimuli also possess sparse representations in numerous domains. In this talk, we underline the role of sparsity in the efficient encoding of network connectivity and inputs through nonlinear neuronal network dynamics. Addressing the fundamental challenge of recovering the structural connectivity of large-scale neuronal networks, we leverage properties of the balanced dynamical regime and compressive sensing theory to develop a theoretical framework for efficiently reconstructing sparse network connections through measurements of the network response to a relatively small ensemble of random stimuli. We further utilize sparse recovery ideas to probe the neural correlates of binocular rivalry through dynamic percept reconstructions based on the activity of a two-layer network model with competing downstream pools driven by disparate image stimuli. The resultant model dynamics agree with key experimental observations and give insights into the excitation/inhibition hypothesis for autism.

Abstract: Multi-agent machine learning has seen tremendous achievements in recent years; yet, translation of single-agent optimization technique to multi-agent domain may not be straightforward. Two of the basic models for multi-agent machine learning -- minimax optimization problem and variational inequality problem -- are both computationally intractable in general. However, the gains from leveraging the special structures can be huge and understanding the optimal structure-driven algorithm is important from both theoretical and practical viewpoints. In this talk, I will provide the results on the optimal structure-driven algorithm design for (1) convex-concave and highly unbalanced minimax optimization problems and (2) monotone and highly smooth variational inequality problems. In particular, I explain why the accelerated proximal point scheme and the adaptive closed-loop scheme perfectly fit the unbalanced structure and the highly smooth structure, respectively, leading to optimal acceleration in our problem of interest.

Abstract:
Submodularity is an important concept in integer and combinatorial optimization. Submodular set functions capture diminishing returns, and for this desirable property, they are found in numerous real-world applications. A submodular set function models the effect of selecting items from a single ground set, and whether an item is chosen can be modeled using a binary variable. However, in many problem contexts, the decisions consist of choosing multiple copies of homogenous items, or heterogenous items from multiple sets. These scenarios give rise to generalizations of submodularity that require mixed-integer variables or multi-set functions. We call the associated optimization problems Generalized Submodular Optimization (GSO). GSO arises in numerous applications, including infrastructure design, healthcare, online marketing, and machine learning. Due to the mixed-integer decision space and the often highly nonlinear (even non-convex and non-concave) objective function, GSO is a broad subclass of challenging mixed-integer nonlinear programming problems. In this talk, we will consider two subclasses of GSO, namely k-submodular optimization and Diminishing Returns (DR)-submodular optimization. We will discuss the polyhedral theory for the mixed-integer set structures that arise from these problem classes, which leads to exact solution methods. Our algorithms demonstrate effectiveness and versatility in experiments with real world datasets, and they can be readily incorporated into the state-of-the-art optimization solvers.

Abstract: Many statistical machine learning problems, where one aims to recover an underlying low-dimensional signal, are based on optimization. Existing work often either overlooked the computational complexity in solving the optimization problem, or requires case-specific algorithm and analysis -- especially for nonconvex problems. This talk addresses the above two issues from a unified perspective of conditioning. In particular, we show that once the sample size exceeds the intrinsic dimension, (1) a broad class of convex and nonsmooth nonconvex problems are well-conditioned, (2) well conditioning, in turn, ensures the efficiency of out-of-box optimization methods and inspires new algorithms. Lastly, we show that a conditioning notion called flatness leads to accurate recovery in overparametrized matrix factorization models.

Abstract:

Solving partial differential equations (PDEs) and PDE-based model reduction are challenging problems, particularly when PDEs have multiscale features. The data-driven approach has become an excellent option for some scientific computing problems. It becomes even more effective for some engineering applications with available data. There are various data-driven treatments for PDE-related problems. Many of them can be implemented in the operator learning framework as the underlying mathematical computation problems construct the operator. I will focus on and discuss operator learning. In particular, I will introduce a new framework: basis enhanced learning (Bel). Bel does not require a specific discretization of functions and achieves great prediction accuracy. Some applications, including some newly proposed engineering applications, will be discussed.

Abstract:

Modern data science applications require solving high dimensional optimization problems with large number of data points. Min-max optimization provides a unified framework for many problems in this context ranging from empirical risk minimization in machine learning to medical imaging and nonlinear programming. This talk will present two approaches for using randomization to design simple, practical and adaptive optimization algorithms that improve the best-known complexity guarantees for convex-concave optimization. I will describe first order primal-dual algorithms with random coordinate updates and discuss their complexity guarantees as well as practical adaptivity properties. I will then present an extragradient algorithm with stochastic variance reduction that harnesses the finite-sum min-max structure to obtain sharp complexity bounds.

Abstract: Natural selection in complex biological and social systems can simultaneously operate across multiple levels of organization, ranging from genes and cells to animal groups and complex human societies. Such scenarios typically present an evolutionary conflict between the incentive of individuals to cheat and the collective incentive to establish cooperation within a group. In this talk, we will explore this conflict by considering a game-theoretic model of multilevel selection in a group-structured population featuring two types of individuals, cooperators and defectors. Assuming that individuals compete based on their payoff and groups also compete based on the average payoff of group members, we consider how the distribution of cooperators within groups changes over time depending on the relative strength of within-group and between-group competition. In the limit of infinitely many groups and of infinite group size, we can describe the state of the population through the probability density of the fraction of cooperators within groups, and derive a hyperbolic partial differential equation for the changing composition of the population. We show that there exists a threshold relative selection strength such that defectors will take over the population for sufficiently weak between-group competition, while cooperation persists in the long-time population when the strength of between-group competition exceeds the threshold. Surprisingly, when groups are best off with an intermediate level of within-group cooperation, individual-level selection casts a long shadow on the dynamics of multilevel selection: no level of between-group competition can erase the effects of the individual incentive to defect. This is joint work with Yoichiro Mori.