Regularized Regression in High Dimensions: Asymptotics, Optimality and Universality

Abstract

Regularized regression is a classical method for statistical estimation and learning. It has now been successfully used in many applications including communications, biology, astronomy, where the sizes and amounts of available data have increased substantially over the recent years. However, the theoretical understanding of this method in the high dimensional setting is still incomplete, although many remarkable findings have been made. This dissertation presents some recent results on analyzingregularized regression in high dimensions, organized in three main strands:

(1) Exact asymptotic characterizations: We study two regularized regression algorithms. The first one is the sorted l1 norm penalized estimator (SLOPE) for sparse regression. We establish an asymptotic separability property of the SLOPE estimator. This yields a precise characterization of SLOPE in high dimensions via a one-dimensional representation. The second one is the box-relaxation decoder for binary signal recovery. We show that under certain regime, the asymptotic distribution of the number of wrong bits converges to a Poisson law. A distinctive feature of the above results is that they are exact and free of unknown constants.

(2) Optimal design: The exact performance characterizations enable a principled way of optimally designing the regularized regression algorithms to reach the fundamental performance limits. Based on our exact characterizations of SLOPE, we address the question about its optimal regularization. Our results reveal that finding the optimal regularization in high dimensions is equivalent to solving an optimal denoising problem in one dimension. This turns out to be an infinite-dimensional convex problem, which can be solved efficiently.

(3) Universality: It has long been observed that diverse high-dimensional probabilistic systems can share universal macroscopic behavior irrespective of their distinct detailed distributions. This universality phenomenon allows us to analyze some complicated models by establishing their equivalence to other simpler models. We prove a universality conjecture that has been utilized to study the learning performance of regularized regression in random feature model.

More broadly speaking, these three strands are interwoven: universality makes the precise characterization, usually obtained in ideal theoretical models (e.g., i.i.d. Gaussian ensemble), be applicable to broader realistic models (e.g., tight frames) and eventually, the exact and universal characterizations enable the systematic way of optimally design the algorithms for various large-scale systems.