CaltechTHESIS
A Caltech Library Service

Universality Laws and Performance Analysis of the Generalized Linear Models

Citation

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. https://resolver.caltech.edu/CaltechTHESIS:06092020-005908250

Abstract

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: https://resolver.caltech.edu/CaltechTHESIS:06092020-005908250
DOI: 10.7907/873c-ej41
Related URLs:
URL URL Type Description
http://papers.nips.cc/paper/5739-lasso-with-non-linear-measurements-is-equivalent-to-one-with-linear-measurements Publisher Article adapted for Chapter 2.
https://arxiv.org/pdf/1601.06233 arXiv Article adapted for Chapter 2.
https://arxiv.org/pdf/1510.01413 arXiv Article adapted for Chapter 2.
https://arxiv.org/pdf/1801.06609 arXiv Article adapted for Chapter 9.
http://papers.nips.cc/paper/9369-the-impact-of-regularization-on-high-dimensional-logistic-regression Publisher Article adapted for Chapter 2.
https://doi.org/10.1109/ITW.2016.7606820 DOI Article adapted for Chapter 3.
https://doi.org/10.1109/ICASSP.2019.8683890 DOI Article adapted for Chapter 7.
http://papers.nips.cc/paper/9404-universality-in-learning-from-linear-measurements Publisher Article adapted for Chapter 6.
https://doi.org/10.1109/ISIT.2019.8849405 DOI Article adapted for Chapter 5.
ORCID:
Author ORCID
Abbasi, Ehsan 0000-0002-0185-7933
Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code: 13804
Collection: CaltechTHESIS
Deposited By: Ehsan Abbasi
Deposited On: 09 Jun 2020 22:15
Last Modified: 19 Jun 2020 18:44

Thesis Files

[img]
Preview
PDF - Final Version
See Usage Policy.

2MB

Repository Staff Only: item control page