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
- 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) - Low-Rank Factorization for Rank Minimization with Nonconvex Regularizers [0.0]
Minimizing the convex relaxation to the nuclear norm is of interest in recommender systems and robust principal component analysis.
We develop efficient algorithms for the rank factorization of nuclear programs put forth by Buriro and nucleariro.
arXiv Detail & Related papers (2020-06-13T19:04:37Z) - Robust Matrix Completion with Mixed Data Types [0.0]
We consider the problem of recovering a structured low rank matrix with partially observed entries with mixed data types.
Most approaches assume that there is only one underlying distribution and the low rank constraint is regularized by the matrix Schatten Norm.
We propose a computationally feasible statistical approach with strong recovery guarantees along with an algorithmic framework suited for parallelization to recover a low rank matrix with partially observed entries for mixed data types in one step.
arXiv Detail & Related papers (2020-05-25T21:35:10Z)
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.