A Caltech Library Service

Regularized Linear Regression: A Precise Analysis of the Estimation Error

Thrampoulidis, Christos and Oymak, Samet and Hassibi, Babak (2015) Regularized Linear Regression: A Precise Analysis of the Estimation Error. Proceedings of Machine Learning Research, 40 . pp. 1683-1709. ISSN 1938-7228.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


Non-smooth regularized convex optimization procedures have emerged as a powerful tool to recover structured signals (sparse, low-rank, etc.) from (possibly compressed) noisy linear measurements. We focus on the problem of linear regression and consider a general class of optimization methods that minimize a loss function measuring the misfit of the model to the observations with an added structured-inducing regularization term. Celebrated instances include the LASSO, Group-LASSO, Least-Absolute Deviations method, etc.. We develop a quite general framework for how to determine precise prediction performance guaranties (e.g. mean-square-error) of such methods for the case of Gaussian measurement ensemble. The machinery builds upon Gordon’s Gaussian min-max theorem under additional convexity assumptions that arise in many practical applications. This theorem associates with a primary optimization (PO) problem a simplified auxiliary optimization (AO) problem from which we can tightly infer properties of the original (PO), such as the optimal cost, the norm of the optimal solution, etc. Our theory applies to general loss functions and regularization and provides guidelines on how to optimally tune the regularizer coefficient when certain structural properties (such as sparsity level, rank, etc.) are known.

Item Type:Article
Related URLs:
URLURL TypeDescription
Thrampoulidis, Christos0000-0001-9053-9365
Additional Information:© 2015 C. Thrampoulidis, S. Oymak & B. Hassibi.
Subject Keywords:Linear Regression, mean-square-error , structured signals, sparsity, LASSO, Gaussian min-max Theorem, convexity
Record Number:CaltechAUTHORS:20200221-130234534
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:101462
Deposited By: Tony Diaz
Deposited On:21 Feb 2020 21:26
Last Modified:21 Feb 2020 21:26

Repository Staff Only: item control page