Positive Semidefinite Matrix Supermartingales
We explore the asymptotic convergence and nonasymptotic maximal inequalities of supermartingales and backward submartingales in the space of positive semidefinite matrices. These are natural matrix analogs of scalar nonnegative supermartingales and backward nonnegative submartingales, whose convergence and maximal inequalities are the theoretical foundations for a wide and ever-growing body of results in statistics, econometrics, and theoretical computer science. Our results lead to new concentration inequalities for either martingale dependent or exchangeable random symmetric matrices under a variety of tail conditions, encompassing now-standard Chernoff bounds to self-normalized heavy-tailed settings. Further, these inequalities are usually expressed in the Loewner order, are sometimes valid simultaneously for all sample sizes or at an arbitrary data-dependent stopping time, and can often be tightened via an external randomization factor.
Code (0)
등록된 구현이 없습니다.
Tasks
EconometricsvalidSimilar Papers 제목 키워드 기반
PSDBoost: Matrix-Generation Linear Programming for Positive Semidefinite Matrices Learning
In this work, we consider the problem of learning a positive semidefinite matrix. The critical issue is how to preserve positive semidefiniteness during the course of learning. Our algorithm is mainly inspired by LPBoost…
Positive Semidefinite Metric Learning with Boosting
The learning of appropriate distance metrics is a critical problem in classification. In this work, we propose a boosting-based technique, termed BoostMetric, for learning a Mahalanobis distance metric. One of the primar…
General ClassificationMetric LearningFixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data
Several important applications, such as streaming PCA and semidefinite programming, involve a large-scale positive-semidefinite (psd) matrix that is presented as a sequence of linear updates. Because of storage limitatio…
Deterministic Symmetric Positive Semidefinite Matrix Completion
We consider the problem of recovering a symmetric, positive semidefinite (SPSD) matrix from a subset of its entries, possibly corrupted by noise. In contrast to previous matrix recovery work, we drop the assumption of a …
Matrix CompletionConvergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
We address the rectangular matrix completion problem by lifting the unknown matrix to a positive semidefinite matrix in higher dimension, and optimizing a nonconvex objective over the semidefinite factor using a simple g…
Matrix Completion