On Tail Probabilities for Martingales

By David Freedman. 1975

How researchers see this paper

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

Citations in the corpus

Doubly Robust Policy Evaluation and Optimization (2014, background): “sion of Freedman’s inequality Freedman’s (1975). Let y1, .”
Stochastic Primal-Dual Q-Learning (2018, positive): “To do so, ﬁrst deﬁne and E (2) Then, G T is written by where The next step is to use the Berstein inequality for Martingales (Freedman, 1975; Fan et al., 2012; Bercu et al., 2015) to prove the convergence of G T /T , in (33).”
Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling (2010, positive): “xi(t)), thereby completing the proof. Proving the last statement of the theorem—the concentration result with uncorrelated noise at each node—requires a martingale extension of Bernstein’s inequality [Fre75]. Indeed, one form of Freedman’s inequality states that if X1,...,XT is a martingale diﬀerenc”
User-Friendly Tail Bounds for Sums of Random Matrices (2010, background): “4; his proof involves a matrix extension of the martingale techniques from [17].”
Minimax Regret Bounds for Reinforcement Learning (2017, background): “Theorem 1 is significant in that, for large T , it improves the regret dependence from S to √ S, compared to the best known bound of Jaksch et al. (2010). The main intuition for this improved S-dependence is that we bound the estimation error of the next-state value function directly, instead of the”
Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting (2009, methodology): “1) Concentration of Martingales: In our analysis, we use the following Bernstein-type concentration inequality for martingale differences, due to Freedman [32] (see also Theorem 3.”
Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation (2020, methodology): “In the following, we analyze the large-deviation behavior of E 1 with Freedman’s inequality (Freedman, 1975).”
Degenerate $$U$$- and $$V$$-statistics under ergodicity: asymptotics, bootstrap and applications in statistics (2013, methodology): “Gregory (1977) and Serfling (1980). This method has been adopted for mixing random variables by Eagleson (1979), Carlstein (1988) and Borisov and Volodko (2008) as well as for associated random variables by Dewan and Prakasa Rao (2001) and Huang and Zhang (2006).”
Exponential inequalities for martingales with applications (2013, methodology): “Following the work of Freedman [17], Shorack and Wellner [35], Van de Geer [36] and De la Peña [9], we develop some new methods, based on changes of probability measure, to establish some general Bernstein type exponential inequalities for supermartingales.”
Efficient Optimal Learning for Contextual Bandits (2011, background): “It can be viewed as a version of Freedman’s Inequality (Freedman, 1975).”
Model-Based Reinforcement Learning with Value-Targeted Regression (2020, methodology): “We will use the Freedman concentration inequality as follows. Theorem 3 (Freedman et al. (1975)) LetX1, · · · , XT be a martingale difference sequence adapted to filtration F1, · · · ,FT (X1, · · · , Xt−1 are Ft-measurable and E[Xt|Ft] = 0).”
Time-uniform Chernoff bounds via nonnegative supermartingales (2018, methodology): “This strengthens Bennett’s and Freedman’s inequalities (Bennett, 1962; Freedman, 1975) [B; C or D] for scalars and the corresponding matrix bounds from Tropp (2011, 2012) [B].”
Extensions to McDiarmid's inequality when dierences are bounded with high probability (2002, background): “There have been a number of generalizations of Chernoff’s inequality, such as the HoeffdingAzuma inequality [9, 1, 7] for martingale difference sequences.”
Stochastic Linear Optimization under Bandit Feedback (2008, methodology): “In our analysis, we use the following Bernstein-type concentration inequality for martingale differences, due to Freedman [1975] (see also [McDiarmid, 1998, Theorem 3.”