Structured Matrix Learning under Arbitrary Entrywise Dependence and Estimation of Markov Transition Kernel

• URL: http://arxiv.org/abs/2401.02520v1
• Date: Thu, 4 Jan 2024 20:13:23 GMT
• Title: Structured Matrix Learning under Arbitrary Entrywise Dependence and Estimation of Markov Transition Kernel
• Authors: Jinhang Chai, Jianqing Fan
• Abstract summary: This paper considers a general framework of noisy low-rank-plus-sparse matrix recovery. We propose an incoherent-constrained least-square estimator and prove its tightness both in the sense of deterministic lower bound and matching minimax risks. We then showcase the applications of our framework to several important statistical machine learning problems.
• Score: 4.360281374698232
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The problem of structured matrix estimation has been studied mostly under strong noise dependence assumptions. This paper considers a general framework of noisy low-rank-plus-sparse matrix recovery, where the noise matrix may come from any joint distribution with arbitrary dependence across entries. We propose an incoherent-constrained least-square estimator and prove its tightness both in the sense of deterministic lower bound and matching minimax risks under various noise distributions. To attain this, we establish a novel result asserting that the difference between two arbitrary low-rank incoherent matrices must spread energy out across its entries, in other words cannot be too sparse, which sheds light on the structure of incoherent low-rank matrices and may be of independent interest. We then showcase the applications of our framework to several important statistical machine learning problems. In the problem of estimating a structured Markov transition kernel, the proposed method achieves the minimax optimality and the result can be extended to estimating the conditional mean operator, a crucial component in reinforcement learning. The applications to multitask regression and structured covariance estimation are also presented. We propose an alternating minimization algorithm to approximately solve the potentially hard optimization problem. Numerical results corroborate the effectiveness of our method which typically converges in a few steps.

Related papers

• Optimal Estimation of Shared Singular Subspaces across Multiple Noisy Matrices [3.3373545585860596]
  This study focuses on estimating shared (left) singular subspaces across multiple matrices within a low-rank matrix denoising framework. We establish that Stack-SVD achieves minimax rate-optimality when the true singular subspaces of the signal matrices are identical. For various cases of partial sharing, we rigorously characterize the conditions under which Stack-SVD remains effective, achieves minimax optimality, or fails to deliver consistent estimates.
  arXiv  Detail & Related papers  (2024-11-26T02:49:30Z)
• Tailed Low-Rank Matrix Factorization for Similarity Matrix Completion [14.542166904874147]
  Similarity Completion Matrix serves as a fundamental tool at the core of numerous machinelearning tasks. To address this issue, Similarity Matrix Theoretical (SMC) methods have been proposed, but they suffer complexity. We present two novel, scalable, and effective algorithms, which investigate the PSD property to guide the estimation process and incorporate non low-rank regularizer to ensure the low-rank solution.
  arXiv  Detail & Related papers  (2024-09-29T04:27:23Z)
• A general error analysis for randomized low-rank approximation with application to data assimilation [42.57210316104905]
  We propose a framework for the analysis of the low-rank approximation error in Frobenius norm for centered and non-standard matrices. Under minimal assumptions, we derive accurate bounds in expectation and probability. Our bounds have clear interpretations that enable us to derive properties and motivate practical choices.
  arXiv  Detail & Related papers  (2024-05-08T04:51:56Z)
• Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning [53.445068584013896]
  We study matrix estimation problems arising in reinforcement learning (RL) with low-rank structure. In low-rank bandits, the matrix to be recovered specifies the expected arm rewards, and for low-rank Markov Decision Processes (MDPs), it may for example characterize the transition kernel of the MDP. We show that simple spectral-based matrix estimation approaches efficiently recover the singular subspaces of the matrix and exhibit nearly-minimal entry-wise error.
  arXiv  Detail & Related papers  (2023-10-10T17:06:41Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  This paper proposes a flexible algorithmic framework for graph learning under low-rank structural constraints. The problem is expressed as penalized maximum likelihood estimation of an elliptical distribution. We leverage geometries of positive definite matrices and positive semi-definite matrices of fixed rank that are well suited to elliptical models.
  arXiv  Detail & Related papers  (2022-10-21T13:19:45Z)
• The Dynamics of Riemannian Robbins-Monro Algorithms [101.29301565229265]
  We propose a family of Riemannian algorithms generalizing and extending the seminal approximation framework of Robbins and Monro. Compared to their Euclidean counterparts, Riemannian algorithms are much less understood due to lack of a global linear structure on the manifold. We provide a general template of almost sure convergence results that mirrors and extends the existing theory for Euclidean Robbins-Monro schemes.
  arXiv  Detail & Related papers  (2022-06-14T12:30:11Z)
• Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
  We study the problem of estimating the fixed point of a contractive operator defined on a separable Banach space. We establish non-asymptotic bounds for both the operator defect and the estimation error.
  arXiv  Detail & Related papers  (2022-01-21T02:46:57Z)
• Probabilistic Simplex Component Analysis [66.30587591100566]
  PRISM is a probabilistic simplex component analysis approach to identifying the vertices of a data-circumscribing simplex from data. The problem has a rich variety of applications, the most notable being hyperspectral unmixing in remote sensing and non-negative matrix factorization in machine learning.
  arXiv  Detail & Related papers  (2021-03-18T05:39:00Z)
• Learning Mixtures of Low-Rank Models [89.39877968115833]
  We study the problem of learning computational mixtures of low-rank models. We develop an algorithm that is guaranteed to recover the unknown matrices with near-optimal sample. In addition, the proposed algorithm is provably stable against random noise.
  arXiv  Detail & Related papers  (2020-09-23T17:53:48Z)

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.