Translator Disclaimer
February 2022 Fundamental barriers to high-dimensional regression with convex penalties
Michael Celentano, Andrea Montanari
Ann. Statist. 50(1): 170-196 (February 2022). DOI: 10.1214/21-AOS2100

## Abstract

In high-dimensional regression, we attempt to estimate a parameter vector ${\beta _{0}}\in {\mathbb{R}^{p}}$ from $n\lesssim p$ observations ${\{({y_{i}},{\boldsymbol{x}_{i}})\}_{i\le n}}$, where ${\boldsymbol{x}_{i}}\in {\mathbb{R}^{p}}$ is a vector of predictors and ${y_{i}}$ is a response variable. A well-established approach uses convex regularizers to promote specific structures (e.g., sparsity) of the estimate $\widehat{\beta }$ while allowing for practical algorithms. Theoretical analysis implies that convex penalization schemes have nearly optimal estimation properties in certain settings. However, in general the gaps between statistically optimal estimation (with unbounded computational resources) and convex methods are poorly understood.

We show that when the statistican has very simple structural information about the distribution of the entries of ${\beta _{0}}$, a large gap frequently exists between the best performance achieved by any convex regularizer satisfying a mild technical condition and either: (i) the optimal statistical error or (ii) the statistical error achieved by optimal approximate message passing algorithms. Remarkably, a gap occurs at high enough signal-to-noise ratio if and only if the distribution of the coordinates of ${\beta _{0}}$ is not log-concave. These conclusions follow from an analysis of standard Gaussian designs. Our lower bounds are expected to be generally tight, and we prove tightness under certain conditions.

## Funding Statement

The first author was supported in part by NSF Grants DGE – 1656518, CCF – 1714305, IIS – 1741162, and ONR N00014-18-1-2729.

## Citation

Michael Celentano. Andrea Montanari. "Fundamental barriers to high-dimensional regression with convex penalties." Ann. Statist. 50 (1) 170 - 196, February 2022. https://doi.org/10.1214/21-AOS2100

## Information

Received: 1 April 2019; Revised: 1 June 2021; Published: February 2022
First available in Project Euclid: 16 February 2022

Digital Object Identifier: 10.1214/21-AOS2100

Subjects:
Primary: 62J05 , 62J07
Secondary: 62F12

Keywords: approximate message passing , computational to statistical gaps , convex , high-dimensional regression , M-estimation , Penalty

Rights: Copyright © 2022 Institute of Mathematical Statistics

JOURNAL ARTICLE
27 PAGES
{"ft_lang_label":"__label__en","ft_lang_prob":0.86354357,"math_prob":0.9319686,"size":1651,"snap":"2022-40-2023-06","text_gpt3_token_len":340,"char_repetition_ratio":0.09653916,"word_repetition_ratio":0.0,"special_character_ratio":0.21259843,"punctuation_ratio":0.11678832,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.98080534,"pos_list":[0,1,2,3,4],"im_url_duplicate_count":[null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-09-27T02:24:46Z\",\"WARC-Record-ID\":\"<urn:uuid:e188dc05-c6a1-46b3-9d47-2518f6d92d1a>\",\"Content-Length\":\"161552\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:034779e0-bca4-4dfc-920c-bfb0e5d22a03>\",\"WARC-Concurrent-To\":\"<urn:uuid:ea225217-ff6e-4b70-a73b-0ba72bbcd2f5>\",\"WARC-IP-Address\":\"107.154.79.145\",\"WARC-Target-URI\":\"https://projecteuclid.org/journals/annals-of-statistics/volume-50/issue-1/Fundamental-barriers-to-high-dimensional-regression-with-convex-penalties/10.1214/21-AOS2100.short\",\"WARC-Payload-Digest\":\"sha1:XBJFKNWOC7MLEBI5KTJNYMM76W6XNP6D\",\"WARC-Block-Digest\":\"sha1:2CWPIANSGJ7UBHVY6NDHNTUE4ASONX5Y\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-40/CC-MAIN-2022-40_segments_1664030334974.57_warc_CC-MAIN-20220927002241-20220927032241-00173.warc.gz\"}"}