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:
URLURL TypeDescription
http://papers.nips.cc/paper/5739-lasso-with-non-linear-measurements-is-equivalent-to-one-with-linear-measurementsPublisherArticle adapted for Chapter 2.
https://arxiv.org/pdf/1601.06233arXivArticle adapted for Chapter 2.
https://arxiv.org/pdf/1510.01413arXivArticle adapted for Chapter 2.
https://arxiv.org/pdf/1801.06609arXivArticle adapted for Chapter 9.
http://papers.nips.cc/paper/9369-the-impact-of-regularization-on-high-dimensional-logistic-regressionPublisherArticle adapted for Chapter 2.
https://doi.org/10.1109/ITW.2016.7606820DOIArticle adapted for Chapter 3.
https://doi.org/10.1109/ICASSP.2019.8683890DOIArticle adapted for Chapter 7.
http://papers.nips.cc/paper/9404-universality-in-learning-from-linear-measurementsPublisherArticle adapted for Chapter 6.
https://doi.org/10.1109/ISIT.2019.8849405DOIArticle adapted for Chapter 5.
ORCID:
AuthorORCID
Abbasi, Ehsan0000-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