Inferring Change Points in High-Dimensional Regression via Approximate Message Passing

• URL: http://arxiv.org/abs/2404.07864v2
• Date: Fri, 18 Oct 2024 15:23:26 GMT
• Title: Inferring Change Points in High-Dimensional Regression via Approximate Message Passing
• Authors: Gabriel Arpino, Xiaoqi Liu, Julia Gontarek, Ramji Venkataramanan,
• Abstract summary: We propose an Approximate Message Passing (AMP) algorithm for estimating both the signals and the change point locations. We rigorously characterize its performance in the high-dimensional limit where the number of parameters $p$ is proportional to the number of samples $n$. We show how our AMP iterates can be used to efficiently compute a Bayesian posterior distribution over the change point locations in the high-dimensional limit.
• Score: 9.660892239615366
• License:
• Abstract: We consider the problem of localizing change points in a generalized linear model (GLM), a model that covers many widely studied problems in statistical learning including linear, logistic, and rectified linear regression. We propose a novel and computationally efficient Approximate Message Passing (AMP) algorithm for estimating both the signals and the change point locations, and rigorously characterize its performance in the high-dimensional limit where the number of parameters $p$ is proportional to the number of samples $n$. This characterization is in terms of a state evolution recursion, which allows us to precisely compute performance measures such as the asymptotic Hausdorff error of our change point estimates, and allows us to tailor the algorithm to take advantage of any prior structural information on the signals and change points. Moreover, we show how our AMP iterates can be used to efficiently compute a Bayesian posterior distribution over the change point locations in the high-dimensional limit. We validate our theory via numerical experiments, and demonstrate the favorable performance of our estimators on both synthetic and real data in the settings of linear, logistic, and rectified linear regression.

Related papers

• Semi-Supervised Deep Sobolev Regression: Estimation, Variable Selection and Beyond [3.782392436834913]
  We propose SDORE, a semi-supervised deep Sobolev regressor, for the nonparametric estimation of the underlying regression function and its gradient. We conduct a comprehensive analysis of the convergence rates of SDORE and establish a minimax optimal rate for the regression function. We also derive a convergence rate for the associated plug-in gradient estimator, even in the presence of significant domain shift.
  arXiv  Detail & Related papers  (2024-01-09T13:10:30Z)
• Refining Amortized Posterior Approximations using Gradient-Based Summary Statistics [0.9176056742068814]
  We present an iterative framework to improve the amortized approximations of posterior distributions in the context of inverse problems. We validate our method in a controlled setting by applying it to a stylized problem, and observe improved posterior approximations with each iteration.
  arXiv  Detail & Related papers  (2023-05-15T15:47:19Z)
• Mixed Regression via Approximate Message Passing [16.91276351457051]
  We study the problem of regression in a generalized linear model (GLM) with multiple signals and latent variables. In mixed linear regression, each observation comes from one of $L$ signal vectors (regressors), but we do not know which one. In max-affine regression, each observation comes from the maximum of $L$ affine functions, each defined via a different signal vector.
  arXiv  Detail & Related papers  (2023-04-05T04:59:59Z)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  We derive an approximate message-passing algorithm (AMP) for the inhomogeneous problem. We identify in particular the existence of a statistical-to-computational gap where known algorithms require a signal-to-noise ratio bigger than the information-theoretic threshold to perform better than random.
  arXiv  Detail & Related papers  (2023-02-13T19:57:17Z)
• Sparse high-dimensional linear regression with a partitioned empirical Bayes ECM algorithm [62.997667081978825]
  We propose a computationally efficient and powerful Bayesian approach for sparse high-dimensional linear regression. Minimal prior assumptions on the parameters are used through the use of plug-in empirical Bayes estimates. The proposed approach is implemented in the R package probe.
  arXiv  Detail & Related papers  (2022-09-16T19:15:50Z)
• 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)
• Variance-Aware Off-Policy Evaluation with Linear Function Approximation [85.75516599931632]
  We study the off-policy evaluation problem in reinforcement learning with linear function approximation. We propose an algorithm, VA-OPE, which uses the estimated variance of the value function to reweight the Bellman residual in Fitted Q-Iteration.
  arXiv  Detail & Related papers  (2021-06-22T17:58:46Z)
• Piecewise linear regression and classification [0.20305676256390928]
  This paper proposes a method for solving multivariate regression and classification problems using piecewise linear predictors. A Python implementation of the algorithm described in this paper is available at http://cse.lab.imtlucca.it/bemporad/parc.
  arXiv  Detail & Related papers  (2021-03-10T17:07:57Z)
• Slice Sampling for General Completely Random Measures [74.24975039689893]
  We present a novel Markov chain Monte Carlo algorithm for posterior inference that adaptively sets the truncation level using auxiliary slice variables. The efficacy of the proposed algorithm is evaluated on several popular nonparametric models.
  arXiv  Detail & Related papers  (2020-06-24T17:53:53Z)
• Asymptotic Analysis of an Ensemble of Randomly Projected Linear Discriminants [94.46276668068327]
  In [1], an ensemble of randomly projected linear discriminants is used to classify datasets. We develop a consistent estimator of the misclassification probability as an alternative to the computationally-costly cross-validation estimator. We also demonstrate the use of our estimator for tuning the projection dimension on both real and synthetic data.
  arXiv  Detail & Related papers  (2020-04-17T12:47:04Z)

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.