For a function observed through point evaluations, is there an optimal way to recover it or merely to estimate a dependent quantity? I will give an affirmative answer to this data-focused question, especially  under the assumption that the function belongs to a model set defined by approximation capabilities.  In fact, I will uncover computationally implementable linear recovery maps that are optimal in the worst-case setting. I will present some recent and ongoing works extending the theory in several directions, with particular emphasis put on observations that are inexact---adversarially or randomly.

Recent theoretical understanding of neural networks has connected their training and generalization to associated kernel matrices. Due to the nonlinearity of the activation function, at random initialization, these kernel matrices are non-linear random matrices.  We consider the limiting spectral distributions of conjugate kernel and neural tangent kernel matrices for two-layer neural networks with deterministic data and random weights. When the width of the network grows faster than the size of the dataset, a deformed semicircle law appears. In this regime, we can also calculate the asymptotic testing and training errors for random feature regression. Joint work with Zhichao Wang https://arxiv.org/abs/2109.09304.

Over the last couple of decades, the theory of interacting particle systems has found some unexpected connections to orthogonal polynomials, symmetric functions, and various combinatorial structures. The asymmetric simple exclusion process (ASEP) has played a central role in this connection. Recently, Cantini, de Gier, and Wheeler found that the partition function of the multispecies ASEP on a circle is a specialization of a Macdonald polynomial $P_{\lambda}(X;q,t)$. Macdonald polynomials are a family of symmetric functions that are ubiquitous in algebraic combinatorics and specialize to or generalize many other important special functions. Around the same time, Martin gave a recursive formulation expressing the stationary probabilities of the ASEP on a circle as sums over combinatorial objects known as multiline queues, which are a type of queueing system. Shortly after, with Corteel and Williams we generalized Martin's result to give a new formula for $P_{\lambda}$ via multiline queues.

The modified Macdonald polynomials $\widetilde{H}_{\lambda}(X;q,t)$ are a version of $P_{\lambda}$ with positive integer coefficients. A natural question was whether there exists a related statistical mechanics model for which some specialization of $\widetilde{H}_{\lambda}$ is equal to its partition function. With Ayyer and Martin, we answer this question in the affirmative with the multispecies totally asymmetric zero-range process (TAZRP), which is a specialization of a more general class of zero range particle processes. We introduce a new combinatorial object in the flavor of the multiline queues, which on one hand, expresses stationary probabilities of the mTAZRP, and on the other hand, gives a new formula for $\widetilde{H}_{\lambda}$. We define an enhanced Markov chain on these objects that lumps to the multispecies TAZRP, and then use this to prove several results about particle densities and correlations in the TAZRP.

In joint work with E Kosygina and J Peterson, the

"natural" diffusive scaling is considered for the recurrent case

and the convergence to Brownian motion perturbed at extrema is shown.  The key ideas are coarse graining and

the Ray Knight approach.

Clustering is a fundamental data scientific task with broad application. This talk investigates a simple clustering problem with data from a mixture of Gaussians that share a common but unknown, and potentially ill-conditioned, covariance matrix. We start by considering Gaussian mixtures with two equally-sized components and derive a Max-Cut integer program based on maximum likelihood estimation. We show its solutions achieve the optimal misclassification rate when the number of samples grows linearly in the dimension, up to a logarithmic factor. However, solving the Max-cut problem appears to be computationally intractable. To overcome this, we develop an efficient spectral algorithm that attains the optimal rate but requires a quadratic sample size. Although this sample complexity is worse than that of the Max-cut problem, we conjecture that no polynomial-time method can perform better. Furthermore, we present numerical and theoretical evidence that supports the existence of a statistical-computational gap. Finally, we generalize the Max-Cut program to a k-means program that handles multi-component mixtures with possibly unequal weights and has similar guarantees.