Large Deviations of Vector-valued Martingales in 2-Smooth Normed Spaces

By Anatoli B. Juditsky, Arkadi Nemirovski. 2008

102 citations recorded by the source corpus.

In this paper, we derive exponential bounds on probabilities of large deviations for “light tail” martingales taking values in finitedimensional normed spaces. Our primary emphasis is on the case where the bounds are dimension-independent or nearly so. We demonstrate that this is the case when the norm on the space can be approximated, within an absolute constant factor, by a norm which is differentiable on the unit sphere with a Lipschitz continuous gradient. We also present various examples of spaces possessing the latter property.

Subfields: Finance, Management Science and Operations Research, Numerical Analysis

How researchers see this paper

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

In Finance

In Management Science and Operations Research

In Numerical Analysis

Citations in the corpus

Regularization Techniques for Learning with Matrices (2009, background): “We can summarize the contributions of this work as follows: • We show how the framework based on strong convexity/strong smoothness duality (see Shalev-Shwartz [2007], Kakade et al. [2008]) provides a methodology for analyzing matrix based learning methods, which are of much recent interest.”
A Stochastic Semismooth Newton Method for Nonsmooth Nonconvex Optimization (2018, methodology): “The first result in part (i) is well-known, see [41, 31, 39].”
Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization (2013, background): “We need the following well-known large deviation theorem of vector-valued martingales to derive the large deviation results of the 2-RSPG algorithm (see [17] for a general result using possibly non-Euclidean norm).”
Projection-Free Optimization on Uniformly Convex Sets (2020, background): “It also relates to concentration inequalities in Banach Spaces (Juditsky and Nemirovski, 2008) and hence implications (Ivanov) for approximate versions of the Carathéodory theorem (Combettes and Pokutta, 2019).”
Optimal Affine-Invariant Smooth Minimization Algorithms (2018, methodology): “…4.7, there exists a norm P ∗(x) such that P ∗(x)2/2 has a Lipschitz continuous gradient with constant µ with respect to the norm P ∗(x), and Proposition 3.2 in Juditsky and Nemirovski (2008) shows by conjugacy that the prox function Φ(x) := (P ∗(x)2/2)∗ = P (x)2/2 (where P is the norm conjugate…”
An Optimal Affine Invariant Smooth Minimization Algorithm (2013, methodology): “We then recall the regularity definition in Juditsky and Nemirovski [2008].”
Linear Algorithms for Online Multitask Classification (2010, methodology): “A more general bound has independently been derived in Juditsky and Nemirovski (2009, Proposition 3.1) and used in Kakade et al. (2009), where the unitarily invariant norms of our analysis are replaced by general convex functions.”
Dual Averaging Methods for Regularized Stochastic Learning and Online Optimization (2009, methodology): “This is the dual averaging version of the exponentiated gradient algorithm (Kivinen and Warmuth, 1997); see also Tseng and Bertsekas (1993) and Juditsky et al. (2005). We note that this example is also covered by Nesterov’s dual averaging method.”