A Caltech Library Service

Universality Laws and Performance Analysis of the Generalized Linear Models


Abbasi, Ehsan (2020) Universality Laws and Performance Analysis of the Generalized Linear Models. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/873c-ej41.


In the past couple of decades, non-smooth convex optimization has emerged as a powerful tool for the recovery of structured signals (sparse, low rank, etc.) from noisy linear or non-linear measurements in a variety of applications in genomics, signal processing, wireless communications, machine learning, etc.. Taking advantage of the particular structure of the unknown signal of interest is critical since in most of these applications, the dimension p of the signal to be estimated is comparable, or even larger than the number of observations n. With the advent of Compressive Sensing there has been a very large number of theoretical results that study the estimation performance of non-smooth convex optimization in such a high-dimensional setting.

A popular approach for estimating an unknown signal β₀ ϵ ℝ in a generalized linear model, with observations y = g(Xβ₀) ϵ ℝ, is via solving the estimator β̂ = arg minβ L(y, Xβ + λf(β). Here, L(•,•) is a loss function which is convex with respect to its second argument, and f(•) is a regularizer that enforces the structure of the unknown β₀. We first analyze the generalization error performance of this estimator, for the case where the entries of X are drawn independently from real standard Gaussian distribution. The precise nature of our analysis permits an accurate performance comparison between different instances of these estimators, and allows to optimally tune the hyperparameters based on the model parameters. We apply our result to some of the most popular cases of generalized linear models, such as M-estimators in linear regression, logistic regression and generalized margin maximizers in binary classification problems, and Poisson regression in count data models. The key ingredient of our proof is the Convex Gaussian Min-max Theorem (CGMT), which is a tight version of the Gaussian comparison inequality proved by Gordon in 1988. Unfortunately, having real iid entries in the features matrix X is crucial in this theorem, and it cannot be naturally extended to other cases.

But for some special cases, we prove some universality properties and indirectly extend these results to more general designs of the features matrix X, where the entries are not necessarily real, independent, or identically distributed. This extension, enables us to analyze problems that CGMT was incapable of, such as models with quadratic measurements, phase-lift in phase retrieval, and data recovery in massive MIMO, and help us settle a few long standing open problems in these areas.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:Generalized Linear Models, Convex Optimization, Performance Analysis, Machine Learning, Statistical Learning
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Electrical Engineering
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Hassibi, Babak
Thesis Committee:
  • Vaidyanathan, P. P. (chair)
  • Tropp, Joel A.
  • Chandrasekaran, Venkat
  • Hassibi, Babak
Defense Date:18 May 2020
Record Number:CaltechTHESIS:06092020-005908250
Persistent URL:
Related URLs:
URLURL TypeDescription adapted for Chapter 2. adapted for Chapter 2. adapted for Chapter 2. adapted for Chapter 9. adapted for Chapter 2. adapted for Chapter 3. adapted for Chapter 7. adapted for Chapter 6. adapted for Chapter 5.
Abbasi, Ehsan0000-0002-0185-7933
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:13804
Deposited By: Ehsan Abbasi
Deposited On:09 Jun 2020 22:15
Last Modified:19 Jun 2020 18:44

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page