FREEDMAN'S INEQUALITY FOR MATRIX MARTINGALES

By Joel A. Tropp. 2011

246 citations recorded by the source corpus.

Freedman's inequality is a martingale counterpart to Bernstein's inequality. This result shows that the large-deviation behavior of a martingale is controlled by the predictable quadratic variation and a uniform upper bound for the martingale difference sequence. Oliveira has recently established a natural extension of Freedman's inequality that provides tail bounds for the maximum singular value of a matrix-valued martingale. This note describes a different proof of the matrix Freedman inequality that depends on a deep theorem of Lieb from matrix analysis. This argument delivers sharp constants in the matrix Freedman inequality, and it also yields tail bounds for other types of matrix martingales. The new techniques are adapted from recent work by the present author.

Subfields: Applied Mathematics, Computational Theory and Mathematics, Mathematical Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Computational Theory and Mathematics

In Mathematical Physics

Citations in the corpus

Efficiently Breaking the Curse of Horizon in Off-Policy Evaluation with Double Reinforcement Learning (2019, methodology): “each case. For brevity, we only consider our estimator with cross-trajectory-tting; nite sample results for other estimators can be similarly derived. Here, we mainly leverage Freedman’s inequality (Tropp, 2011, Theorem 1.1) since the estimator has a martingale dierence structure. Theorem 12 (Finite”
User-Friendly Tail Bounds for Sums of Random Matrices (2010, background): “To obtain fully detailed results for martingales, one must use a fundamentally different style of argument [39, 55].”
Online Clustering of Bandits (2014, methodology): “Setting for brevity X s = ¯ x s ¯ x s , and Theorem 1.2 in (Tropp, 2011) implies where || W t || denotes the operator norm of matrix W t .”
On the Theory of Reinforcement Learning with Once-per-Episode Feedback (2021, methodology): “Next we state a matrix concentration theorem (Tropp, 2011, Theorem 1.1).”
Time-uniform, nonparametric, nonasymptotic confidence sequences (2018, background): “[69]), which show that (St ) is sub-gamma with variance process (Vt ), scale c = b/3, and l0 = d .”
Escaping Saddle Points with Adaptive Gradient Methods (2019, methodology): “from Tropp [2011]) with bounds on how fast the sequence moves, we arrive at the following result, proved in Appendix F: Theorem 4.”
Randomized numerical linear algebra: Foundations and algorithms (2020, methodology): “J. A. Tropp (2011b), ‘Improved analysis of the subsampled randomized Hadamard transform’, Adv.”
Noncommutative martingale deviation and Poincaré type inequalities with applications (2012, methodology): “Tropp [57] obtained better constants for tail estimate of random matrix martingales by using Lieb’s concavity theorem.”
The Masked Sample Covariance Estimator: An Analysis via Matrix Concentration Inequalities (2011, methodology): “This paper provides a new analysis of the masked sample covariance estimator using some recent ideas from random matrix theory [1, 21, 26, 29, 33, 34, 36–38].”
Time-uniform Chernoff bounds via nonnegative supermartingales (2018, methodology): “This “Freedman-style” bound has been generalized to other settings in many subsequent works (de la Peña, 1999; Khan, 2009; Tropp, 2011; Fan et al., 2015).”
A Limit Theorem for Scaled Eigenvectors of Random Dot Product Graphs (2013, background): “More recently, general bounds for the operator norm of the difference between the adjacency matrix and its expectation have been proved in Oliveira (2010) and Tropp (2011).”
On Some Extensions of Bernstein's Inequality for Self-adjoint Operators (2011, methodology): “ the product (3.2), note that by Lieb’s theorem Y k:= trexp(S k ˚()W k) is a supermartingale with initial value d(which can be shown similar by repeating conditioning argument of Theorem2.1, or see [13] for details), so that Etr exp(S n ˚()W n) d: Together with (3.1), this gives trEg(S n ˚()W n) = t”