A Universal Analysis of Large-Scale Regularized Least Squares Solutions
A problem that has been of recent interest in statistical inference, machine learning and signal processing is that of understanding the asymptotic behavior of regularized least squares solutions under random measurement matrices (or dictionaries). The Least Absolute Shrinkage and Selection Operator (LASSO or least-squares with 1 regularization) is perhaps one of the most interesting examples. Precise expressions for the asymptotic performance of LASSO have been obtained for a number of different cases, in particular when the elements of the dictionary matrix are sampled independently from a Gaussian distribution. It has also been empirically observed that the resulting expressions remain valid when the entries of the dictionary matrix are independently sampled from certain non-Gaussian distributions. In this paper, we confirm these observations theoretically when the distribution is sub-Gaussian. We further generalize the previous expressions for a broader family of regularization functions and under milder conditions on the underlying random, possibly non-Gaussian, dictionary matrix. In particular, we establish the universality of the asymptotic statistics (e.g., the average quadratic risk) of LASSO with non-Gaussian dictionaries.
The paper studies the universality of high-dimensional regularized least squares problems with respect to the distribution of the design matrix. The main result of the paper is that, under moment conditions on the entries of the design matrix A, the optimal value of the least squares problem, and characteristics of the optimal solution are independent of the details of the distribution of the A_ij’s. 
The proof uses the Lindeberg interpolation method, in a clever incremental way, to transform the problem to its Gaussian counterpart while preserving the characteristics of the optimization, then uses Gaussian comparison theorems (variants of Gordon’s escape through a mesh result) to analyze the Gaussian setting. 
The consequences are nice formulas predicting the exact values of the cost, the limiting empirical distribution of the entries of the solution and of the error vector. 
These formulas were previously known to be correct only in restricted settings. 
These exact asymptotic characterizations of random estimation problems have been studied by several authors and in different settings. There are similarities, at least in spirit, to the work of El Karoui [1], and Donoho-Montanari [2] on robust high-dimensional regression (a problem that could be seen as the dual of the one considered here), and to many papers that have appeared in the information-theory community on “single letter formulas” characterizing the MMSE of various estimation channels (linear regression, noisy rank-one matrix estimation, CDMA,…) See e.g., [3,4,5] and references therein. 
Although most of these efforts have mainly dealt with the Gaussian design setting, some have proved “channel universality”, which is essentially the focus of this paper. The authors should probably fill this bibliographic gap. 
Second, I would like to point out a different approach to the problem, inspired by rigorous work in statistical physics, and that will make the connection to the above mentioned work clearer: one could consider the log-sum-exp approximation to the optimization problem, with a “inverse temperature” parameter \beta. And one recovers the optimization in the limit \beta -> \infty. One could study the convergence of log-partition function obtained in this way, and obtain a formula for it, which in this setting would bare the name of “the replica-symmetric (RS) formula”.
The “essential optimization” problem found by the authors is nothing else but the zero-temperature limit of this RS formula. (One would of course have to justify swapping the limits n \to \infty and \beta \to \infty.) 
This being said, the techniques used in this work seem to be of a different nature, and add to the repertoire of approaches to compute asymptotic values of these challenging problems.      
[1] Asymptotic behavior of unregularized and ridge-regularized high-dimensional robust regression estimators : rigorous results https://arxiv.org/abs/1311.2445
[2] High Dimensional Robust M-Estimation: Asymptotic Variance via Approximate Message Passing https://arxiv.org/abs/1310.7320
[3] The Mutual Information in Random Linear Estimation : https://arxiv.org/abs/1607.02335                    
[4] Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula https://arxiv.org/abs/1606.04142
[5] Fundamental limits of symmetric low-rank matrix estimation : https://arxiv.org/abs/1611.03888