A non-asymptotic distributional theory of approximate message passing for sparse and robust regression

• URL: http://arxiv.org/abs/2401.03923v1
• Date: Mon, 8 Jan 2024 14:34:35 GMT
• Title: A non-asymptotic distributional theory of approximate message passing for sparse and robust regression
• Authors: Gen Li, Yuting Wei
• Abstract summary: This paper develops non-asymptotic distributional characterizations for approximate message passing (AMP) AMP is a family of iterative algorithms that prove effective as both fast estimators and powerful theoretical machinery.
• Score: 20.830017611900832
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Characterizing the distribution of high-dimensional statistical estimators is a challenging task, due to the breakdown of classical asymptotic theory in high dimension. This paper makes progress towards this by developing non-asymptotic distributional characterizations for approximate message passing (AMP) -- a family of iterative algorithms that prove effective as both fast estimators and powerful theoretical machinery -- for both sparse and robust regression. Prior AMP theory, which focused on high-dimensional asymptotics for the most part, failed to describe the behavior of AMP when the number of iterations exceeds $o\big({\log n}/{\log \log n}\big)$ (with $n$ the sample size). We establish the first finite-sample non-asymptotic distributional theory of AMP for both sparse and robust regression that accommodates a polynomial number of iterations. Our results derive approximate accuracy of Gaussian approximation of the AMP iterates, which improves upon all prior results and implies enhanced distributional characterizations for both optimally tuned Lasso and robust M-estimator.

Related papers

• Non-asymptotic bounds for forward processes in denoising diffusions: Ornstein-Uhlenbeck is hard to beat [49.1574468325115]
  This paper presents explicit non-asymptotic bounds on the forward diffusion error in total variation (TV) We parametrise multi-modal data distributions in terms of the distance $R$ to their furthest modes and consider forward diffusions with additive and multiplicative noise.
  arXiv  Detail & Related papers  (2024-08-25T10:28:31Z)
• A Random Matrix Approach to Low-Multilinear-Rank Tensor Approximation [24.558241146742205]
  We characterize the large-dimensional spectral behavior of the unfoldings of the data tensor and exhibit relevant signal-to-noise ratios governing the detectability of the principal directions of the signal. Results allow to accurately predict the reconstruction performance of truncated multilinear SVD (MLSVD) in the non-trivial regime.
  arXiv  Detail & Related papers  (2024-02-05T16:38:30Z)
• Approximate message passing from random initialization with applications to $\mathbb{Z}_{2}$ synchronization [25.511475484340156]
  This paper is concerned with the problem of reconstructing an unknown rank-one matrix with prior structural information from observations. We provide the first non-asymotic characterization of Approximate Message Passing (AMP) in this model.
  arXiv  Detail & Related papers  (2023-02-07T18:58:08Z)
• A Non-Asymptotic Framework for Approximate Message Passing in Spiked Models [24.786030482013437]
  Approximate message passing (AMP) emerges as an effective iterative paradigm for solving high-dimensional statistical problems. Prior AMP theory fell short of predicting the AMP dynamics when the number of iterations surpasses $obig(fraclog nloglog nbig)$. This paper develops a non-asymptotic framework for understanding AMP in spiked matrix estimation.
  arXiv  Detail & Related papers  (2022-08-05T17:59:06Z)
• Efficient CDF Approximations for Normalizing Flows [64.60846767084877]
  We build upon the diffeomorphic properties of normalizing flows to estimate the cumulative distribution function (CDF) over a closed region. Our experiments on popular flow architectures and UCI datasets show a marked improvement in sample efficiency as compared to traditional estimators.
  arXiv  Detail & Related papers  (2022-02-23T06:11:49Z)
• On the Double Descent of Random Features Models Trained with SGD [78.0918823643911]
  We study properties of random features (RF) regression in high dimensions optimized by gradient descent (SGD) We derive precise non-asymptotic error bounds of RF regression under both constant and adaptive step-size SGD setting. We observe the double descent phenomenon both theoretically and empirically.
  arXiv  Detail & Related papers  (2021-10-13T17:47:39Z)
• Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
  We consider the task of heavy-tailed statistical estimation given streaming $p$ samples. We design a clipped gradient descent and provide an improved analysis under a more nuanced condition on the noise of gradients.
  arXiv  Detail & Related papers  (2021-08-25T21:30:27Z)
• Instance-Optimal Compressed Sensing via Posterior Sampling [101.43899352984774]
  We show for Gaussian measurements and emphany prior distribution on the signal, that the posterior sampling estimator achieves near-optimal recovery guarantees. We implement the posterior sampling estimator for deep generative priors using Langevin dynamics, and empirically find that it produces accurate estimates with more diversity than MAP.
  arXiv  Detail & Related papers  (2021-06-21T22:51:56Z)
• PCA Initialization for Approximate Message Passing in Rotationally Invariant Models [29.039655256171088]
  Principal Component Analysis provides a natural estimator, and sharp results on its performance have been obtained in the high-dimensional regime. Recently, an Approximate Message Passing (AMP) algorithm has been proposed as an alternative estimator with the potential to improve the accuracy of PCA. In this work, we combine the two methods, initialize AMP with PCA, and propose a rigorous characterization of the performance of this estimator.
  arXiv  Detail & Related papers  (2021-06-04T09:13:51Z)
• Approximate Message Passing with Spectral Initialization for Generalized Linear Models [35.618694363241744]
  We focus on estimators based on approximate message passing (AMP) We propose an AMP algorithm with a spectral estimator. We also provide numerical results that demonstrate the validity of the proposed approach.
  arXiv  Detail & Related papers  (2020-10-07T14:52:35Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  We study the problem of solving strongly convex and smooth unconstrained optimization problems using first-order algorithms. We devise a novel, referred to as Recursive One-Over-T SGD, based on an easily implementable, averaging of past gradients. We prove that it simultaneously achieves state-of-the-art performance in both a finite-sample, nonasymptotic sense and an sense.
  arXiv  Detail & Related papers  (2020-08-28T14:46:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.