Estimation with norm regularization

Arindam Banerjee, Sheng Chen, Farideh Fazayeli, Vidyashankar Sivakumar

Research output: Contribution to journalConference articlepeer-review


Analysis of non-asymptotic estimation error and structured statistical recovery based on norm regularized regression, such as Lasso, needs to consider four aspects: the norm, the loss function, the design matrix, and the noise model. This paper presents generalizations of such estimation error analysis on all four aspects. We characterize the restricted error set, where the estimation error vector lies, establish relations between error sets for the constrained and regularized problems, and present an estimation error bound applicable to any norm. Precise characterizations of the bound is presented for a variety of design matrices, including sub-Gaussian, anisotropic, and dependent samples, noise models, including both Gaussian and sub-Gaussian noise, and loss functions, including least squares and generalized linear models. Gaussian width, a geometric measure of size of sets, and associated tools play a key role in our generalized analysis.

Original languageEnglish (US)
Pages (from-to)1556-1564
Number of pages9
JournalAdvances in Neural Information Processing Systems
Issue numberJanuary
StatePublished - 2014
Externally publishedYes
Event28th Annual Conference on Neural Information Processing Systems 2014, NIPS 2014 - Montreal, Canada
Duration: Dec 8 2014Dec 13 2014

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing


Dive into the research topics of 'Estimation with norm regularization'. Together they form a unique fingerprint.

Cite this