• Speaker: Simone Brugiapaglia, Concordia University
• Title: The curse of dimensionality and the blessings of sparsity and Monte Carlo sampling: From polynomial to deep neural network approximation in high dimensions
• Date: 05/13/2021
• Time: 2:30 PM - 3:30 PM
• Place: Online (virtual meeting) (Virtual Meeting Link)
• Contact: Olga Turanova (turanova@msu.edu)

Approximating multi-dimensional functions from pointwise samples is a ubiquitous task in data science and scientific computing. This task is made intrinsically difficult by the presence of four contemporary challenges: (i) the target function is usually defined over a high- or infinite-dimensional domain; (ii) generating samples can be very expensive; (iii) samples are corrupted by unknown sources of errors; (iv) the target function might take values in a function space. In this talk, we will show how these challenges can be substantially overcome thanks to the "blessings" of sparsity and Monte Carlo sampling. First, we will consider the case of sparse polynomial approximation via compressed sensing. Focusing on the case where the target function is smooth (e.g., holomorphic), but possibly highly anisotropic, we will show how to obtain sample complexity bounds only mildly affected by the curse of dimensionality, near-optimal accuracy guarantees, stability to unknown errors corrupting the data, and rigorous convergence rates of algebraic and exponential type. Then, we will illustrate how the mathematical toolkit of sparse polynomial approximation via compressed sensing can be employed to obtain a practical existence theorem for Deep Neural Network (DNN) approximation of high-dimensional Hilbert-valued functions. This result shows not only the existence of a DNN with desirable approximation properties, but also how to compute it via a suitable training procedure in order to achieve best-in-class performance guarantees. We will conclude by discussing open research questions. The presentation is based on joint work with Ben Adcock, Casie Bao, Nick Dexter, Sebastian Moraga, and Clayton G. Webster.

• Speaker: Akram Aldroubi, Venderbilt University
• Title: Dynamical Sampling: A Sampling Tour
• Date: 05/27/2021
• Time: 2:30 PM - 3:30 PM
• Place: Online (virtual meeting) (Virtual Meeting Link)
• Contact: Olga Turanova (turanova@msu.edu)

Dynamical sampling is a term describing an emerging set of problems related to recovering signals and evolution operators from space-time samples. For example, one problem is to recover a function f from space-time samples {(A_{t_i}f)(x_i)} of its time evolution f_t = (A_t f)(x), where {A_t}_{t∈T} is a known evolution operator and {(xi,ti)} ⊂ R^d × R^+ . Another example is a system identification problem when both f and the evolution family {A_t}_{t∈T} are unknown. Applications of dynamical sampling include inverse problems in sensor networks, and source term recovery from physically driven evolutionary systems. Dynamical sampling problems are tightly connected to frame theory as well as more classical areas of mathematics such as approximation theory, and functional analysis. In this talk, I will describe a few problems in dynamical sampling, some results and open problems.

• Speaker: Piotr Indyk, MIT
• Title: Learning-Based Sampling and Streaming
• Date: 06/10/2021
• Time: 2:30 PM - 3:30 PM
• Place: Online (virtual meeting) (Virtual Meeting Link)
• Contact: Olga Turanova (turanova@msu.edu)

Classical algorithms typically provide "one size fits all" performance, and do not leverage properties or patterns in their inputs. A recent line of work aims to address this issue by developing algorithms that use machine learning predictions to improve their performance. In this talk I will present two examples of this type, in the context of streaming and sampling algorithms. In particular, I will show how to use machine learning predictions to improve the performance of (a) low-memory streaming algorithms for frequency estimation (ICLR’19), and (b) sampling algorithms for estimating the support size of a distribution (ICLR’21). Both algorithms use an ML-based predictor that, given a data item, estimates the number of times the item occurs in the input data set. The talk will cover material from papers co-authored with T Eden, CY Hsu, D Katabi, S Narayanan, R Rubinfeld, S Silwal, T Wagner and A Vakilian.

• Speaker: Qiang Ye, University of Kentucky
• Title: Batch Normalization and Preconditioning for Neural Network Training
• Date: 06/24/2021
• Time: 2:30 PM - 3:30 PM
• Place: Online (virtual meeting) (Virtual Meeting Link)
• Contact: Olga Turanova (turanova@msu.edu)

Batch normalization (BN) is a popular and ubiquitous method in deep neural network training that has been shown to decrease training time and improve generalization performance. Despite its success, BN is not theoretically well understood. It is not suitable for use with very small mini-batch sizes or online learning. In this talk, we will review BN and present a preconditioning method called Batch Normalization Preconditioning (BNP) to accelerate neural network training. We will analyze the effects of mini-batch statistics of a hidden variable on the Hessian matrix of a loss function and propose a parameter transformation that is equivalent to normalizing the hidden variables to improve the conditioning of the Hessian. Compared with BN, one benefit of BNP is that it is not constrained on the mini-batch size and works in the online learning setting. We will present several experiments demonstrating competitiveness of BNP. Furthermore, we will discuss a connection to BN which provides theoretical insights on how BN improves training and how BN is applied to special architectures such as convolutional neural networks. The talk is based on a joint work with Susanna Lange and Kyle Helfrich.

• Speaker: Yaniv Plan, University of British Columbia
• Title: A family of measurement matrices for generalized compressed sensing
• Date: 07/22/2021
• Time: 2:30 PM - 3:30 PM
• Place: Online (virtual meeting) (Virtual Meeting Link)
• Contact: Olga Turanova (turanova@msu.edu)

We consider the problem of recovering a structured signal x that lies close to a subset of interest T in R^n, from its random noisy linear measurements y = B A x + w, i.e., a generalization of the classic compressed sensing problem. Above, B is a fixed matrix and A has independent sub-gaussian rows. By varying B, and the sub-gaussian distribution of A, this gives a family of measurement matrices which may have heavy tails, dependent rows and columns, and singular values with large dynamic range. Typically, generalized compressed sensing assumes a random measurement matrix with nearly uniform singular values (with high probability), and asks: How many measurements are needed to recover x? In our setting, this question becomes: What properties of B allow good recovery? We show that the “effective rank” of B may be used as a surrogate for the number of measurements, and if this exceeds the squared Gaussian complexity of T-T then accurate recovery is guaranteed. We also derive the optimal dependence on the sub-gaussian norm of the rows of A, to our knowledge this was not known previously even in the case when B is the identity. We allow model mismatch and inexact optimization with the aim of creating an easily accessible theory that specializes well to the case when T is the range of an expansive neural net.

• Speaker: Andrea Bertozzi, UCLA
• Title: TBA
• Date: 08/12/2021
• Time: 2:30 PM - 3:30 PM
• Place: Online (virtual meeting) (Virtual Meeting Link)
• Contact: Olga Turanova (turanova@msu.edu)

TBA