Segmentation of high dimensional means over multi-dimensional change points and connections to regression trees

• URL: http://arxiv.org/abs/2105.10017v1
• Date: Thu, 20 May 2021 20:29:48 GMT
• Title: Segmentation of high dimensional means over multi-dimensional change points and connections to regression trees
• Authors: Abhishek Kaul
• Abstract summary: This article provides a new analytically tractable and fully frequentist framework to characterize and implement regression trees. The connection to regression trees is made by a high dimensional model with dynamic mean vectors over multi-dimensional change axes. Results are obtained under a high dimensional scaling $slog2 p=o(T_wT_h), where $p$ is the response dimension, $s$ is a sparsity parameter, and $T_w,T_h$ are sampling periods along change axes.
• Score: 1.0660480034605242
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: This article is motivated by the objective of providing a new analytically tractable and fully frequentist framework to characterize and implement regression trees while also allowing a multivariate (potentially high dimensional) response. The connection to regression trees is made by a high dimensional model with dynamic mean vectors over multi-dimensional change axes. Our theoretical analysis is carried out under a single two dimensional change point setting. An optimal rate of convergence of the proposed estimator is obtained, which in turn allows existence of limiting distributions. Distributional behavior of change point estimates are split into two distinct regimes, the limiting distributions under each regime is then characterized, in turn allowing construction of asymptotically valid confidence intervals for $2d$-location of change. All results are obtained under a high dimensional scaling $s\log^2 p=o(T_wT_h),$ where $p$ is the response dimension, $s$ is a sparsity parameter, and $T_w,T_h$ are sampling periods along change axes. We characterize full regression trees by defining a multiple multi-dimensional change point model. Natural extensions of the single $2d$-change point estimation methodology are provided. Two applications, first on segmentation of {\it Infra-red astronomy satellite (IRAS)} data and second to segmentation of digital images are provided. Methodology and theoretical results are supported with monte-carlo simulations.

Related papers

• High-dimensional optimization for multi-spiked tensor PCA [8.435118770300999]
  We study the dynamics of two local optimization algorithms, online gradient descent (SGD) and gradient flow. For gradient flow, we show that the algorithmic threshold to efficiently recover the first spike is also of order $Np-2$. Our results are obtained through a detailed analysis of a low-dimensional system that describes the evolution of the correlations between the estimators and the spikes.
  arXiv  Detail & Related papers  (2024-08-12T12:09:25Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimization [90.87444114491116]
  This paper studies minimax optimization problems defined over infinite-dimensional function classes of overparametricized two-layer neural networks. We address (i) the convergence of the gradient descent-ascent algorithm and (ii) the representation learning of the neural networks. Results show that the feature representation induced by the neural networks is allowed to deviate from the initial one by the magnitude of $O(alpha-1)$, measured in terms of the Wasserstein distance.
  arXiv  Detail & Related papers  (2024-04-18T16:46:08Z)
• High-dimensional limit theorems for SGD: Effective dynamics and critical scaling [6.950316788263433]
  We prove limit theorems for the trajectories of summary statistics of gradient descent (SGD) We show a critical scaling regime for the step-size, below which the effective ballistic dynamics matches gradient flow for the population loss. About the fixed points of this effective dynamics, the corresponding diffusive limits can be quite complex and even degenerate.
  arXiv  Detail & Related papers  (2022-06-08T17:42:18Z)
• Exponential Family Model-Based Reinforcement Learning via Score Matching [97.31477125728844]
  We propose an optimistic model-based algorithm, dubbed SMRL, for finitehorizon episodic reinforcement learning (RL) SMRL uses score matching, an unnormalized density estimation technique that enables efficient estimation of the model parameter by ridge regression.
  arXiv  Detail & Related papers  (2021-12-28T15:51:07Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer. In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph. Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.
  arXiv  Detail & Related papers  (2021-09-10T07:01:15Z)
• Inference for Change Points in High Dimensional Mean Shift Models [10.307668909650449]
  We consider the problem of constructing confidence intervals for the locations of change points in a high-dimensional mean shift model. We develop a locally refitted least squares estimator and obtain component-wise and simultaneous rates of estimation of the underlying change points. The results are established under a high dimensional scaling, allowing in the presence of diverging number of change points and under subexponential errors.
  arXiv  Detail & Related papers  (2021-07-19T20:56:15Z)
• Graph Gamma Process Generalized Linear Dynamical Systems [60.467040479276704]
  We introduce graph gamma process (GGP) linear dynamical systems to model real multivariate time series. For temporal pattern discovery, the latent representation under the model is used to decompose the time series into a parsimonious set of multivariate sub-sequences. We use the generated random graph, whose number of nonzero-degree nodes is finite, to define both the sparsity pattern and dimension of the latent state transition matrix.
  arXiv  Detail & Related papers  (2020-07-25T04:16:34Z)
• Inference on the change point in high dimensional time series models via plug in least squares [2.7718973516070684]
  We study a plug in least squares estimator for the change point parameter where change is in the mean of a high dimensional random vector. We obtain sufficient conditions under which this estimator possesses sufficient adaptivity against plug in estimates of mean parameters.
  arXiv  Detail & Related papers  (2020-07-03T18:08:12Z)
• A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, a Precise Phase Transition, and the Corresponding Double Descent [85.77233010209368]
  This article characterizes the exacts of random Fourier feature (RFF) regression, in the realistic setting where the number of data samples $n$ is all large and comparable. This analysis also provides accurate estimates of training and test regression errors for large $n,p,N$.
  arXiv  Detail & Related papers  (2020-06-09T02:05:40Z)
• Inference on the Change Point for High Dimensional Dynamic Graphical Models [9.74000189600846]
  We develop an estimator for the change point parameter for a dynamically evolving graphical model. It retains sufficient adaptivity against plug-in estimates of the graphical model parameters. It is illustrated on RNA-sequenced data and their changes between young and older individuals.
  arXiv  Detail & Related papers  (2020-05-19T19:15:32Z)

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.