The interplay of statistics, optimization, and geometry for modern data science

We develop a versatile framework for statistical learning in non-stationary environments. In each time period, our approach applies a stability principle to select a look-back window that maximizes the utilization of historical data while keeping the cumulative bias within an acceptable range relative to the stochastic error. Our theory and numerical experiments showcase the adaptivity of this approach to unknown non-stationarity. We prove regret bounds that are minimax optimal up to logarithmic factors when the population losses are strongly convex, or Lipschitz only. At the heart of our analysis lie two novel components: a measure of similarity between functions and a segmentation technique for dividing the non-stationary data sequence into quasi-stationary pieces. 

Iterative algorithms are the workhorses of modern statistical signal processing and machine learning. While the choice of an algorithm and its hyperparameters determines both the speed and fidelity of the learning pipeline, it is common for this choice to be made heuristically, either by expensive trial-and-error or by comparing upper bounds on convergence rates of various candidate algorithms. Motivated by these issues, I will present a toolbox for deriving "state evolutions" for a wide variety of algorithms with random data. These are non-asymptotic, near-exact predictions of the statistical behavior of the algorithm, which apply even when the underlying optimization problem is nonconvex or the algorithm is randomly initialized. We will showcase these predictions on deterministic and stochastic variants of complex algorithms employed in some canonical statistical models. 

Regularization is a classical approach for statistical inference and inverse problems. Modern data-driven approaches parameterize regularizers via deep neural networks and learn task-dependent regularizers, showcasing impressive empirical performance. In particular, critic-based regularizers integrate information about the measurements and ground-truth data in an unsupervised loss function, and a regularizer is learned that attributes low values to likely data and high values to unlikely data. However, there is little theory about the structure of regularizers learned via this process. In this talk, we will study this critic-based approach for a particular family of regularizers: Minkowski functionals of star-shaped bodies. By leveraging tools from star geometry and dual Brunn-Minkowski theory, we derive exact expressions for the optimal regularizer in certain cases. We also study the relationship between this class of regularizers and neural network architectures, as well as illustrate their potential practical application with empirical studies.  

In this talk, we address the top-$K$ ranking problem with a monotone adversary. We consider the scenario where a comparison graph is randomly generated and the adversary is allowed to add arbitrary edges. The statistician's goal is then to accurately identify the top-$K$ preferred items based on pairwise comparisons derived from this semi-random comparison graph. The main contribution of this paper is to develop a weighted maximum likelihood estimator (MLE) that achieves near-optimal sample complexity, up to a $\log^2(n)$ factor, where $n$ denotes the number of items under comparison. This is made possible through a combination of analytical and algorithmic innovations. On the analytical front, we provide a refined $\ell_\infty$ error analysis of the weighted MLE that is more explicit and tighter than existing analyses. It relates the $\ell_\infty$ error with the spectral properties of the weighted comparison graph. Motivated by this, our algorithmic innovation involves the development of an semi-definite-program-based (SDP-based) approach to reweight the semi-random graph and meet specified spectral properties. Additionally, we propose a first-order method based on the Matrix Multiplicative Weight Update (MMWU) framework. This method efficiently solves the resulting SDP in nearly-linear time relative to the size of the semi-random comparison graph.