Anatoli B Juditsky
email: juditsky@imag.fr

Arkadi S Nemirovski
email: nemirovs@isye.gatech.edu

LARGE DEVIATIONS OF VECTOR-VALUED MARTINGALES IN 2-SMOOTH NORMED SPACES

Keywords: large deviations, matrix-valued martingales, deviations of vector norms

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.

1. Introduction. It is well-known that for a sequence of independent zero mean random reals {ξ i } ∞ i=1 with light tail distributions (e.g., such that E exp{|ξ i | α σ -α i } ≤ exp{1} for certain α ∈ [START_REF] Azuma | Weighted sums of certain dependent random variables[END_REF][START_REF] John | Extremum problems with inequalities as subsidiary conditions" -in: Studies and Essays presented to R[END_REF] and deterministic σ t > 0), a "typical magnitude" of the sum S t = t i=1 ξ i is "at most of order of The question we focus on in this paper is to which extent the above large deviation bound is preserved when passing from scalar random variables to independent zero mean random variables taking values in a normed space (E, • ) of (possibly, large) dimension n < ∞. Now our "light tail" condition reads

(1)

E exp{ ξ i α σ -α i } ≤ exp{1}
for some α ∈ [START_REF] Azuma | Weighted sums of certain dependent random variables[END_REF][START_REF] John | Extremum problems with inequalities as subsidiary conditions" -in: Studies and Essays presented to R[END_REF], and what we want to get is a bound of the form

∀γ ≥ 0 : Prob    t i=1 ξ i > [θ + γ] t i=1 σ 2 i    ≤ O(1) exp{-O(1)γ α } ( * )
with a "moderate" value of the constant θ. It is immediately seen that our goal is not always attainable. For instance, let (E, • ) be ℓ n 1 (i.e., R n equipped with the norm x 1 = n i=1 |x i |), and let ξ i take values ±e i with probability 1/2, 1 ≤ i ≤ n, where e i are the standard basic orths in R n . Then (1) holds true with σ i = 1, while S k 1 ≡ k whenever k ≤ n. We see that in order for ( * ) to be true, θ should be as large as O(1)

√ n. On the other hand, with θ = O(1) √ dim E, ( * ) indeed is true independently of the norm • in question (see Example 3.1 in Section 3.1). Our major goal in this paper is to show that a sufficient condition for ( * ) to be valid with certain θ is θ 2 -regularity of the space (E, • ). The latter means, essentially, that • can be approximated within an absolute constant factor by a norm p(•) which is continuously differentiable outside of the origin and possesses Lipschitz continuous, with the Lipschitz constant θ 2 , derivative on its unit sphere: Norms p(•) satisfying (2) play important role in the theory of Banach spaces (where they are called norms with smoothness modulus of power 2). In particular, a number of results on the properties of martingales taking values in Banach spaces with smooth norms (see, e.g., [START_REF] Garling | Functional Central Limit Theorems in Banach Spaces[END_REF][START_REF] Garling | Convexity, smoothness and martingale inequalities[END_REF]) are available. However, we were unable to locate in the literature a result equivalent to Theorem 2.1 which establishes the validity of (somehow refined) bound ( * ) in the case of a θ 2 -regular space (E, • ). Thus, the main result of this paper, to the best of our (perhaps incomplete) knowledge, is new. The preliminary and slightly less accurate, version of Theorem 2.1 was announced in [START_REF] Nemirovski | On tractable approximations of randomly perturbed convex constraints[END_REF] and proved in the preprint [START_REF] Nemirovski | Regular Banach spaces and large deviations of random sums[END_REF].

imsart-aap ver. 2007/12/10 file: LD-5-5-2008.hyper25752.tex date: September 3, 2008 While the question we address seems to be important by its own right, our interest in it stems mainly from various applications of (somehow rudimentary) bounds of type ( * ) we have encountered over the years. These applications include investigating performance of Euclidean and non-Euclidean stochastic approximation [START_REF] Nemirovski | Problem complexity and method efficiency in optimization[END_REF][START_REF] Juditsky | Functional aggregation for nonparametric regression[END_REF], nonparametric statistics [START_REF] Nemirovskii | Rate of convergence for nonparametric maximum likelihood estimates[END_REF][START_REF] Juditsky | Functional aggregation for nonparametric regression[END_REF][START_REF] Nemirovskii | Nonparametric estimation of functions satisfying differential inequalities[END_REF], optimization under uncertainty [START_REF] Nemirovski | On tractable approximations of randomly perturbed convex constraints[END_REF], investigating quality of semidefinite relaxations of some difficult combinatorial problems [START_REF] Nemirovski | Sums of random symmetric matrices and quadratic optimization under orthogonality constraints[END_REF], etc.

Our paper is organized as follows: the main result on large deviations (Theorem 2.1) is formulated in Section 2. Section 3.1 contains instructive examples and characterizations of κ-regular spaces, along with a kind of "calculus" of these spaces. All proofs are placed in the appendix.

In what follows, if not explicitly stated otherwise, we suppose all the relations between random variables to hold a.s..

Main result.

2.1. Regular spaces. We start with the following

Definition 2.1. Let (E, • ) be a finite-dimensional normed space and let κ ≥ 1. (i) The function p(x) = x 2 called κ-smooth if it is continuously differen- tiable and (3) ∀x, y ∈ E : p(x + y) ≤ p(x) + Dp(x)[y] + κp(y).
(ii) Space (E, • ) (and the norm • on E) is called κ-regular, if there exists κ + ∈ [1, κ] and a norm

• + on E such that (E, • + ) is κ + -smooth and • + is κ/κ + -compatible with • , that is, (4) ∀x ∈ E : x 2 ≤ x 2 + ≤ κ κ + x 2 . (iii) The constant κ(E, • ) of regularity of E, • is the infinum (clearly achievable) of those κ ≥ 1 for which (E, • ) is κ-regular.
As an immediate example, an Euclidean space (R n , • 2 ) is 1-smooth and thus 1-regular.

Main result. Assume that we are given

• a finite-dimensional space (E, • ),

• a Polish space Ω with Borel probability measure µ, and

• a sequence F 0 = {∅, Ω} ⊂ F 1 ⊂ F 2 ⊂ ... of σ-sub-algebras of the Borel σ-algebra of Ω.
We denote by E i , i = 1, 2, ... the conditional expectation w.r.t. F i , and by E ≡ E 0 the expectation w.r.t. µ.

We further assume that we are given an

E-valued martingale-difference sequence ξ ∞ = {ξ i } ∞ i=1 of Borel E-valued functions on Ω such that ξ i is F i -measurable and E i-1 {ξ i } ≡ 0, i = 1, 2, ...
An immediate consequence of Definition 2.1 of the regular norm is as follows: assume that an

E-valued martingale-difference ξ = {ξ t } ∞ t=1 is square- integrable: E ξ t 2 ≤ σ 2 t < ∞. Then E S n 2 ≤ κ n t=1 σ 2 t .
Indeed,

• + is κ + -smooth, we have p(S t+1 ) ≤ p(S t ) + Dp(S t )[ξ t+1 ] + κ + p(ξ t+1 )
whence, taking expectations and making use of the fact that ξ is a martingaledifference,

E {p(S t+1 )} ≤ E {p(S t )} + κ + E {p(ξ t+1 )} ≤ E {p(S t )} + κE ξ t+1 2
by the right inequality of (4). Then, by the left inequality of ( 4),

E S n 2 ≤ E S n 2 + ≤ κ n t=1 E ξ t 2 ≤ κ n t=1 σ 2 t .
Our primary objective is to establish exponential bounds on the probabilities of large deviations for an E-valued martingale difference {ξ i }. To this end, we impose on {ξ i } a "light tail" assumption as follows. Let α ∈ [1, 2] and a sequence σ ∞ = {σ i > 0} ∞ i=1 of (deterministic) positive reals be given. We introduce the following condition on the sequence ξ ∞ :

∀i ≥ 1 : E i-1 exp{ ξ i α σ -α i } ≤ exp{1} almost surely (C α [σ ∞ ])
Our main result is the large deviation bound for S N = N i=1 ξ i as follows: (i) for 1 ≤ α ≤ 2, one has for all N ≥ 1 and γ ≥ 0: (5)

Theorem 2.1. Let (E, • ) be κ-regular, let E-valued martingale-difference ξ ∞ satisfy (C α [σ ∞ ]), and let S N = N i=1 ξ i , σ N = [σ 1 ; ...; σ N ].
Prob    S N ≥ √ 2eκ + √ 2γ N i=1 σ 2 i    ≤ 2 exp - 1 64 min γ 2 ; γ 2-α * γ α , where (6)
γ * ≡ γ * (α, ν N ) =                32 8α * 2 α * α-1 2-α ν N 2 ν N α * α 2-α ≥ 16 ν N 2 ν N α * α 2-α ≥ 16, α * = α α-1 , ν N = [ν 1 ; ...; ν N ] , 1 < α < 2, lim α→1+0 γ * (α, ν N ) = 16 ν N 2 ν N ∞ , α = 1, lim α→2-0 γ * (α, ν N ) = +∞, α = 2.
(ii) When α = 2, the bound (42) improves to (7)

(∀N ≥ 1, γ ≥ 0) : Prob    S N ≥ √ 2κ + √ 2γ N i=1 σ 2 i    ≤ exp{-γ 2 /3}. (iii) When the condition E i-1 exp{ ξ i 2 σ -2 i } ≤ exp{1} in (C 2 [σ ∞ ]) is strengthened to ξ i ≤ σ i almost surely, i = 1, 2, ..., the bound (42) improves to (8) (∀N ≥ 1, γ ≥ 0) : Prob    S N ≥ √ 2κ + √ 2γ N i=1 σ 2 i    ≤ exp -γ 2 /2 .
3. Regular spaces. To make Theorem 2.1 meaningful, we need to point out a spectrum of interesting κ-smooth/regular spaces, and this is the issue we consider in this Section.

Basic examples.

Let E be an n-dimensional linear space, and let • be a norm on E. It is well known [START_REF] John | Extremum problems with inequalities as subsidiary conditions" -in: Studies and Essays presented to R[END_REF] that there exists an ellipsoid Q centered at the origin such that Q ⊂ {x ∈ E : x ≤ 1} ⊂ √ nQ, or, equivalently, there exists a Euclidean norm

• + on E such that x 2 ≤ x 2 + ≤ n x 2 . Since the Euclidean space (E, • + ) is 1-smooth, we conclude that Example 3.1. . Every finite-dimensional normed space (E, • ) is (dim E)- regular.
We are about to present a number of less trivial examples, those where the regularity parameter κ is dimension-independent (or nearly so).

Example 3.2. Let 2 ≤ p ≤ ∞. The space (R n , • p ) with n ≥ 3 is κ p (n)-regular with (9) κ p (n) = min 2≤ρ≤p ρ<∞ (ρ -1)n 2 ρ -2 p ≤ min[p -1, 2 ln(n)] Example 3.3. Let 2 ≤ p ≤ ∞.
The norm |X| p = σ(X) p on the space R m×n of m × n real matrices, where σ(X) is the vector of singular values of X, is κ p (m, n)-regular, with

(10) κ p (m, n) = min 2≤ρ<∞ ρ≤p max[2, ρ -1](min(m, n)) 2 ρ -2 p ≤ min [max[2, p -1], (2 ln(min[m, n] + 2) -1) exp{1}] .
The proof of the bound ( 10) is based upon the fact which is important by its own right: Proposition 3.1. Let ∆ be an open interval on the axis, and f be a C 2 function on ∆ such that for certain θ ± , µ ± ∈ R one has (11)

∀(a < b, a, b ∈ ∆) : θ - f ′′ (a) + f ′′ (b) 2 +µ -≤ f ′ (b) -f ′ (a) b -a ≤ θ + f ′′ (a) + f ′′ (b) 2 +µ +
Let, further, X n (∆) be the set of all n × n symmetric matrices with eigenvalues belonging to ∆. Then X n (∆) is an open convex set in the space S n of n × n symmetric matrices, the function

F (X) = Tr(f (X)) : X n (∆) → R
is C 2 , and for every X ∈ X n (∆) and every H ∈ S n one has

(12) θ -Tr(Hf ′′ (X)H)+µ -Tr(H 2 ) ≤ D 2 F (X)[H, H] ≤ θ + Tr(Hf ′′ (X)H)+µ + Tr(H 2 ).
3.2. Dual characterization of smoothness and regularity. The following well-known fact can be seen as dual characterization of κ-smoothness: Proposition 3.2. Let (E, • ) be a finite-dimensional normed space, E * be the space dual to E, • * be the norm on E * dual to • ; and let ξ, x stand for the value of a linear form ξ ∈ E * on a vector x ∈ E. Let also

f (x) = 1 2 x 2 : E → R and f * (ξ) = 1 2 ξ 2 * : E * → R.
The following properties are equivalent to each other: (ii) ∂f (x) = {f ′ (x)} is a singleton for every x, and

(i) (E, • ) is κ-smooth;
(13) f ′ (x) -f ′ (y), x -y ≤ κ x -y 2 ∀x, y ∈ E;
(iii) f is continuously differentiable, and f ′ (•) is Lipschitz continuous with constant κ:

(14) f ′ (x) -f ′ (y) * ≤ κ x -y ∀x, y ∈ E;
(iv) One has

∀(ξ, η ∈ E * , x ∈ ∂f * (ξ), y ∈ ∂f * (η)) : ξ -η, x -y ≥ κ -1 ξ -η 2 * ; (v) One has ∀(ξ, η ∈ E * , x ∈ ∂f * (ξ), y ∈ ∂f * (η)) : x -y ≥ κ -1 ξ -η * ; (vi) One has ∀(ξ, η ∈ E * , x ∈ ∂f * (ξ)) : f * (ξ + η) ≥ f * (ξ) + η, x + 1 2κ η 2 * .
Another characterization of regular spaces is as follows:

Proposition 3.3. Let (E,
• ) be a finite-dimensional normed space, E * be the space dual to E, • * be the norm on E * dual to • , and let ξ, x stand for the value of a linear form ξ ∈ E * on a vector x ∈ E. Let also B * be the unit

• * -ball of E * . (i) If (E, •
) is κ-regular, then the exists a continuous function V : B * → R which is strongly convex, with coefficient 1 w.r.t. • * , on B * , that is, possesses the following equivalent to each other properties:

(15) (a) ∀(ξ, η ∈ intB * , x ∈ ∂v(ξ), y ∈ ∂v(η)) : ξ -η, x -y ≥ ξ -η 2 * , (b) ∀(ξ, η : ξ, ξ + η ∈ intB * , x ∈ ∂v(ξ)) : v(ξ + η) ≥ v(ξ) + η, x + 1 2 η 2 * ;
and, in addition, is such that

(16) max B * v -min B * v ≤ κ 2 (ii) Assume that the unit ball B * of (E * , • * ) admits a function v satisfy- ing (15), (16). Then (E, • ) is O(1)
κ-regular with an appropriately chosen absolute constant O(1).

"Calculus" of smooth and regular spaces.

Proposition 3.4. Let (E, • E ) be a finite-dimensional normed space, L be a linear subspace of E, and F = E/L be the factor-space of E equipped with the factor-norm Example 3.2:. Let 2 ≤ ρ < ∞. We claim that in this case the space (R n , • ρ ) is (ρ-1)-smooth. Indeed, the function p(x) = • 2 ρ is convex, continuously differentiable everywhere and twice continuously differentiable outside of the origin; for such a function, (3) holds true if and only if

f F = min f ∈ f f E . If (E, • E ) is κ-smooth (κ- regular), then (L, • E ) and (F, • F ) also are κ-smooth, respectively, κ- regular. Proposition 3.5. (i) Let p ∈ [2, ∞], and let (E i , • i ) be finite-dimensional κ-smooth spaces, i = 1, ..., m > 2. The space E = E 1 × ... × E m equipped with the norm (x 1 , ..., x m ) = m i=1 x i p i 1/p (the right hand side is max i x i i when p = ∞) is κ + -regular with (17) κ + = min 2≤ρ≤p [κ + ρ -1]m 2 ρ -2 p ≤ min[κ + p -1, [κ + 2 ln(m) -1] exp{1}]. (ii) Let • i be κ-smooth norms on E. Then the norm x = m i=1 x i is mκ-regular on E. Proposition 3.6. (i) Let p ∈ [2, ∞], and let (E i , • i ) be finite-dimensional κ-regular spaces, i = 1, ..., m > 2. The space E = E 1 × ... × E m equipped with the norm (x 1 , ..., x m ) = m i=1 x i p i 1/p (the right hand side is max i x i i when p = ∞) is κ ++ -regular with (18) κ ++ = 2 min 2≤ρ≤p [κ + ρ -1]m 2 ρ -2 p ≤ 2 min[κ + p -1, [κ + 2 ln(m) -1] exp{1}]. (ii) Let • i be κ-regular norms on a finite-dimensional space E. Then the norm x = m i=1 x i is 2mκ-regular on E.
(19) D 2 p(x)[h, h] ≤ 2κ + p(h) ∀(x, h ∈ E, x = 0); since p(•)
is homogeneous of degree 2, the validity of ( 19) for all x, h is equivalent to the validity of the relation for all h and all x normalized by the requirement p(x) = 1. Given such an x and h and assuming ρ > 2, we have

Dp(x)[h] = 2 i |x i | ρ 2 ρ -1 i |x i | ρ-1 sign(x i )h i D 2 p(x)[h, h] = 2 2 ρ -1 ≤0 i |x i | ρ 2 ρ -2 i |x i | ρ-1 sign(x i )h i 2 +2 i |x i | ρ =1 2 ρ -1 i (ρ -1)|x i | ρ-2 h 2 i ≤ 2(ρ -1) i |x i | ρ-2 h 2 i ≤ 2(ρ -1) i (|x i | ρ-2 ) ρ ρ-2 ρ-2 ρ i (|h i | 2 ) ρ 2 2 ρ = 2(ρ -1) h 2 ρ = 2(ρ -1)p(h) as required in (19) when κ + = ρ -1. In the case of ρ = 2 relation (19) with κ + = ρ -1 = 1 is evident. Now, when ρ ∈ [2, p] and x ∈ R n , one has x 2 ρ / x 2 p ∈ [1, n 2 ρ -2 p ], so that (R n , • p ) is κ-regular with κ = (ρ -1)n 2 ρ -2
p , and (9) follows.

Example 3.3:. 1 0 . We start with the following

Lemma 1. Let ρ ≥ 2. Then the space S n of symmetric n × n matrices with the norm |X| ρ is κ-smooth with (20) κ = max[2, ρ -1].
Proof. The statement is evident when ρ = 2; thus, from now on we assume that ρ > 2. Let us apply Proposition 3.1 to ∆ = R, f (t) = |t| ρ with θ -= µ -= 0, µ + = 0 and θ + = max 2 ρ-1 , 1 (this choice, as it is immediately seen, satisfies [START_REF] Nemirovski | Regular Banach spaces and large deviations of random sums[END_REF]). By Proposition, the function F (X) = |X| ρ ρ on S n is twice continuously differentiable, and (21)

∀X, H : 0 ≤ D 2 F (X)[H, H] ≤ θ + Tr(f ′′ (x)H 2 ), θ + = max 2 ρ -1 , 1 . It follows that the function p(X) = |X| 2 ρ = (F (X)) 2
ρ is continuously differentiable everywhere and twice continuously differentiable outside of the origin. For X = 0 we have Dp(

X)[H] = 2 ρ (F (X)) 2 ρ -1 DF (X)[H], whence (22) X = 0 ⇒ D 2 p(X)[H, H] = 2 ρ 2 ρ -1 <0 (F (X)) 2 ρ -2 (DF (X)[H]) 2 + 2 ρ (F (X)) 2 ρ -1 D 2 F (X)[H, H] ≤ 2 ρ (F (X)) 2 ρ -1 θ + Tr(f ′′ (x)H 2 ). Setting Z = 1 ρ(ρ-1) (F (X)) 2 ρ -1 f ′′ (X), p = ρ ρ-2 , it is immediately seen that |Z| p = 1. From (22) we have (23) D 2 p(X)[H, H] ≤ 2Θ + (ρ -1) Tr(ZH 2 ) ≤ 2θ + (ρ -1)|Z| p |H 2 | p p-1 = 2θ + (ρ -1)|H 2 | ρ 2 = 2θ + (ρ -1)|H| 2 ρ .
Now, if X, Y ∈ S n are such that the segment [X; X + Y ] does not contain the origin, then

∃γ ∈ (0, 1) : p(X + Y ) ≤ p(X) + Dp(X)[Y ] + 1 2 D 2 p(X + γY )[Y, Y ],
and (23) implies that for the outlined X, Y one has

p(X + Y ) ≤ p(X) + Dp(X)[Y ] + θ + (ρ -1)p(Y ).
Since p is C 1 , the resulting inequality, by continuity, is valid for all X, Y . 2 0 . Now we can complete the justification of Example 3.3. W.l.o.g. we may whence, by Lemma 1 and due to the fact that the mapping X → S(X) : R m×n → S m+n is linear, the norm

assume that m ≤ n. Given an m × n matrix X, let S(X) = X X T ∈ S m+n . One clearly has σ(X) ρ = |X| ρ = 2 -1/ρ |S(X)| ρ ,
| • | ρ , treated as a norm on R m×n , is max[2, ρ -1]-smooth whenever ρ ≥ 2. Since σ(X) ∈ R m for X ∈ R m×n , for every ρ ∈ [2, ∞) such that ρ ≤ p one has |X| 2 p ≤ |X| 2 ρ ≤ m 2 ρ -2 p |X| 2 p . Thus, the space (R m×n , |•| p ) is κ-regular with κ = min 2≤ρ<∞ ρ≤p max[2, ρ-1]m 2 ρ -2 p ,
and we arrive at [START_REF] Nemirovski | On tractable approximations of randomly perturbed convex constraints[END_REF].

4.1.2. Proof of Proposition 3.1. Let {f k (t)} be a sequence of polynomials converging to f , along with the first and the second derivatives, uniformly on every compact subset of ∆. For a polynomial p(t) = N j=0 p j t j the function P (X) = Tr( j p j X j ) is a polynomial on S n . Let now X, H ∈ S n , let λ s = λ s (X) be the eigenvalues of X, X = U Diag{λ}U T be the eigenvalue decomposition of X, and let H be such that H = U HU T . We have ( 24)

P (X) = n s=1 p(λ s (X)) (a) DP (X)[H] = Tr( N j=1 N -1 s=0 X s HX N -s-1 = Tr(p ′ (X)H) = n s=1 p ′ (λ s (X)) H ss (b)
Further, let γ be a closed contour in the complex plane encircling all the eigenvalues of X. Then

DP (X)[H] = Tr(p ′ (X)H) = 1 2πı γ p ′ (z) Tr((zI -X) -1 H)dz ⇒ D 2 P (X)[H, H] = 1 2πı γ p ′ (z) Tr((zI -X) -1 H(zI -X) -1 H)dz = 1 2πı γ n s,t=1 H 2 st p ′ (z) (z-λs)(z-λt) dz.
Computing the residuals, we get

(25) D 2 P (X)[H, H] = s,t Γ s,t [p] H 2 st , Γ s,t [p] = p ′ (λs)-p ′ (λt) λs-λt , λ s = λ t p ′′ (λ s ), λ s = λ t
Substituting p = f k into (24.a, b) and (25), we see that the sequence of polynomials F k (X) = Tr(f k (X)) converges, along with the first and the second order derivatives, uniformly on compact subsets of X n (∆); by (24.a), the limiting function is exactly F (X). We conclude that F (X) is C 2 on X n (∆) and that the first and the second derivatives of this function are limits, as k → ∞, of the corresponding derivatives of F k (X), so that for X = U Diag{λ}U T ∈ X n (∆) (where U is orthogonal) and every So far, we did not use [START_REF] Nemirovski | Regular Banach spaces and large deviations of random sums[END_REF]. Invoking the right inequality in [START_REF] Nemirovski | Regular Banach spaces and large deviations of random sums[END_REF], we get

H = U HU T ∈ S n we have (26) DF (X)[H] = s f ′ (λ s ) H ss = Tr(f ′ (X)H) D 2 F (X)[H, H] = s,t Γ s,t [f ]
D 2 F (X)[H, H] ≤ s,t θ + f ′′ (λs)+f ′′ (λt) 2 + µ + H 2 st = θ + s f ′′ (λ s ) t H 2 st + µ + s,t H 2 st = θ + Tr(Diag{f ′′ (λ 1 ), ..., f ′′ (λ n )} H 2 ) + µ + Tr( H 2 ) = θ + Tr(f ′′ (X)H 2 ) + µ + Tr(H 2 ),
which is the right inequality in [START_REF] Nemirovski | Sums of random symmetric matrices and quadratic optimization under orthogonality constraints[END_REF]. The derivation of the left inequality in ( 12) is similar. (i)⇒(iii). : We are in the situation when f is continuously differentiable.

Convolving f (•) with smooth nonnegative kernels δ k (•) with unit integral and support shrinking to origin as k → ∞, we get a sequence f k (•) of smooth functions converging to f (•), along with first order derivatives, uniformly on compact sets. We have

f k (x + y) = f (x -z + y)δ(z)dz ≤ [f (x -z) + f ′ (x -z), y + κf (y)]δ(z)dz = f k (x) + f ′ k (x)
, y + κf (y) From the resulting inequality combined with smoothness and convexity of

f k it follows that 0 ≤ D 2 f k (x)[h, h] ≤ κ h 2 ∀x, h ∈ E. Thus, if h = d = 1, then 4D 2 f k (x)[h, d] = D 2 f k (x)[h+d, h+d]-D 2 f k (x)[h-d, h-d] ≤ κ h+d 2 ≤ 4κ . Whence D 2 f k (x)[h, d] ≤ κ whenever h = d = 1
, or, which is the same by homogeneity,

|D 2 f k (x)[h, d]| ≤ κ h d ∀x, h, d. Consequently, | f ′ k (y)-f ′ k (x), h | = | 1 0 D 2 f k (x+t(y-x))[y-x, h]dt| ≤ 1 0 κ y-x h dt ≤ κ y-x h ,
whence, taking maximum over h with h = 1,

f ′ k (y) -f ′ k (x) * ≤ κ y -x . As k → ∞, f ′ k (x) converge to f ′ (x)
, and we conclude that f ′ (•) possesses the required Lipschitz continuity. (iii)⇒(ii):. evident (ii)⇒(i):. A convex function on R n with a singleton differential at every point clearly is continuously differentiable, so that in the case of (ii) f is continuously differentiable. Besides this, in the case of (ii) we have

f (x + y) = f (x) + f ′ (x), y + 1 0 f ′ (x + ty) -f ′ (x), y dt ≤ f (x) + f ′ (x), y + 1 0 κt y 2 dt = f (x) + f ′ (x), y + κf (y), which immediately implies (3) (recall that • 2 = 2f (•)).
(iii)⇔(v):. The functions f (•), f * (•) are the Legendre transforms of each other, so that x ∈ ∂f * (ξ) if and only if ξ ∈ ∂f (x). Now let (iii) be the case, and let ξ, η ∈ E * and x ∈ ∂f * (ξ), y ∈ ∂f * (η). Then ξ = f ′ (x), η = f ′ (y) and therefore, due to (iii), ξη * ≤ κ xy , so that (v) takes place. Vice versa, let (v) take place, and let x, y ∈ E, ξ ∈ ∂f (x), η ∈ ∂f (y). Then x ∈ ∂f * (ξ), y ∈ ∂f * (y), and therefore (v) says that ξη * ≤ κ xy .

We conclude that if x = y, then ξ = η, that is, ∂f (x) always is a singleton, meaning that f is continuously differentiable, and that the inequality in (iii) takes place, that is, (iii) holds true.

(iv)⇔(iii):. Let (iv) take place. If there exists x ∈ E such that ∂f (x) is not a singleton, then, choosing ξ, η ∈ ∂f (x) with ξ = η, we would have x ∈ ∂f * (ξ), x ∈ ∂f * (η), whence by (iv) we should have

ξ -η, x -x ≥ κ -1 ξ -η 2 * ,
which is impossible. Thus, ∂f (x) is a singleton for every x, so that f is continuously differentiable. Besides this, with x, y ∈ E and ξ = f ′ (x), η = f ′ (y) we have x ∈ ∂f * (ξ), y ∈ ∂f * (η), whence, by (iv),

ξ -η, x -y ≥ κ -1 ξ -η 2 * . Since ξ -η, x -y ≤ ξ -η * x -y , we get ξ -η * x -y ≥ κ -1 ξ -η 2 * , whence ξ -η * = f ′ (x) -f ′ (y) * ≤ κ x -y ,
and thus (iii) takes place. Now let (iii) take place, and let us prove that (iv) takes place as well, or, which is the same in the case of (iii), that f

′ (x)-f ′ (y), x-y ≥ κ -1 f ′ (x)- f ′ (y) 2 . Setting g(u) = f (u) -f ′ (y), u -y ,
we get a continuously differentiable convex function on E such that g ′ (x)g ′ (y) * ≤ κ xy and g ′ (y) = 0. Due to these relations,

g(y + h) ≤ g(y) + κ 2 h 2
for all h. Now let e ∈ E be such that g ′ (x), e = g ′ (x) * and e = 1. Due to

g ′ (u) -g ′ (v) * ≤ κ u -v , we have g(x - g ′ (x) * κ e) ≤ g(x) -g ′ (x), g ′ (x) * κ e + κ 2 g ′ (x) κ e 2 = g(x) - g ′ (x) 2 * κ + g ′ (x) 2 * 2κ = g(x) - g ′ (x) 2 * 2κ .
On the other hand, g attains its global minimum at y, so that

g(x) - g ′ (x) 2 * 2κ ≥ g(x - g ′ (x) * κ e) ≥ g(y).
We now have

g(y) + κ 2 h 2 ≥ g(y + h) ≥ g(x) + g ′ (x), y + h -x ≥ g(y) + g ′ (x) 2 * 2κ + g ′ (x), y + h -x , whence g ′ (x), x -y ≥ g ′ (x) 2 * 2κ + g ′ (x), h - κ 2 h 2 .
This inequality is valid for all h; setting h = g ′ (x) * κ e, the right hand side becomes g ′ (x) 2 * κ . Thus, (iv) ⇒(vi):. Let (iv) take place, let ξ, η ∈ E * and x ∈ ∂f * (ξ). Setting ξ t = ξ + tη, φ(t) = f * (ξ t ), 0 ≤ t ≤ 1, we get an absolutely continuous function on [0, 1] with the derivative which is almost everywhere given by φ ′ (t) = η, x t , with x t ∈ ∂f * (ξ t ). We have

f ′ (x) -f ′ (y), x -y = g ′ (x), x -y ≥ g ′ (x) 2 * κ = f ′ (x) -f ′ (y)
f * (ξ + η) = φ(1) = φ(0) + 1 0 φ ′ (t)dt = φ(0) + 1 0 η, x t dt = φ(0) + 1 0 [ η, x + η, x t -x ]dt = φ(0) + η, x + 1 0 t -1 (ξ + tη) -ξ, x t -x dt ≥ φ(0) + η, x + 1 0 t -1 κ -1 [ξ + tη] -ξ 2 * dt = φ(0) + η, x + 1 2κ η 2 * = f * (ξ) + η, x + 1 2κ η , *
where the inequality is given by (iv). We end up with the inequality required in (vi).

(vi)⇒(i):. Let (vi) be the case, let x ∈ E and ξ ∈ ∂f (x), so that x ∈ ∂f * (ξ). We have

f (x + y) = max η∈E * [ ξ + η, x + y -f * (ξ + η)] ≤ max η∈E * ξ + η, x + y -f * (ξ) -η, x - 1 2κ η 2 * = max η∈E * ξ, x + y + η, y -f * (ξ) - 1 2κ η 2 * = ξ, x -f * (ξ) f (x) + ξ, y + max η η, y - 1 2κ η 2 * = f (x) + ξ, y + κ 2 y 2 .
This relation along with the relation f (x+y) ≥ f (x)+ ξ, y implies that ξ is the Frechet derivative of f at x, whence f is convex and differentiable, and thus -continuously differentiable function on E which satisfies the inequality

f (x + y) ≤ f (x) + f ′ (x), y + κ 2 y 2 .
We have proved that (i)⇔(ii)⇔(iii)⇔(iv)⇔(v) and (iv)⇒(vi)⇒(i), meaning that all 6 properties in question are equivalent to each other. (i):. Let (E, • ) be κ-regular, and let κ + ∈ [1, κ] and • + be such that (E, • + ) is κ-smooth and (4) holds true, and let • +, * be the norm on

E * dual to • + ; note that (27) κ + κ • 2 * ≤ • 2 +, * ≤ • 2 * due to (4). Invoking Proposition 3.2, the function v(ξ) = κ 2 ξ 2 * ,+ : B * → R satisfies ∀(ξ, η ∈ intB * , x ∈ ∂v(ξ), y ∈ ∂v(η)) : ξ -η, x -y ≥ κ κ + ξ -η 2 +, * ,
and thus satisfies (15.a) due to (27). At the same time, max

B * v -min B * v = κ 2 max ξ * ≤1 ξ 2 +, * ≤ κ 2 ,
where the concluding inequality is due to (27). (i) is proved.

(ii):. Let v(•) satisfy ( 15) and ( 16); clearly, the function 1 2 [v(ξ) + v(-ξ)]v(0) also satisfy these relations; thus, we can assume w.l.o.g. that v(ξ) = v(-ξ) and v(0

) = 0. Let V be the Legendre transform of v(•) B *
, that is,

V (x) = max ξ * ≤1 [ ξ, x -v(x)] .
By the standard properties of the Legendre transform, (15) implies that V is a continuously differentiable convex function on E such that

V ′ (x) = argmin ξ∈B * [ ξ, x -v(ξ)] ∈ B * and V ′ (x) -V ′ (y) * ≤ x -y ∀x, y.
In addition, we clearly have V (x) = V (-x) and x -κ 2 ≤ V (x) ≤ x for all x by (16). Convolving V with a smooth symmetric w.r.t. the origin nonnegative kernel with unit integral and small support and subtracting a constant to make function vanish at the origin, we see that for every ǫ > 0 there exists a C ∞ convex function W = W ǫ on E such that for all x ∈ E one has x ≤ κr(x) ≤ 10 9

(28) (a) W ǫ (x) = W ǫ (-x), W ǫ (0) = 0; (b) x -κ 2 -ǫ ≤ W ǫ (x) ≤ x + ǫ (c) W ′ (x) * ≤ 1 (d) 0 ≤ W ′′ (x)dx, dx ≤ dx 2 ∀dx ∈ E.
x .

Setting L(x) = p 2 (x), observe that the function L is given by the equation

V (x/ L(x)) = κ.
It follows immediately from the Implicit Function Theorem that L is C ∞ outside of the origin, and since this function is the square of a norm, it is therefore C 1 on the entire space. Let us compute the second order differential of L at a point x = 0. Differentiating twice the equation specifying L, we get

DL(x)[dx] = 2L W ′ , dx W ′ , x , D 2 L(x)[dx, dx] = 2L W ′ , dx W ′ , x 2 + 2L 1/2 W ′ , x W ′′ dx - W ′ , dx W ′ , x x , dx - W ′ , dx W ′ , x x , where L = L(x), W ′ = W ′ (L -1/2 x), W ′′ = W ′′ (L -1/2 x).
We claim that (31)

x = 0 ⇒ 0 ≤ D 2 L(x)[dx, dx] ≤ 27 κ dx 2 .
Indeed, D 2 L(x)[dx, dx] is homogeneous of degree 0 in x, so that it suffices to verify the required relation when L(x) = 1, i.e., when W (x) = κ. In this case, the required bound is readily given by the expression for D 2 L combined with (28.c, d) and the following observations: (1) for x in question, we have W ′ , x ≥ W (x) -W (0) = κ, and (2) x ≤ 5 2 κ by (29). Setting x + = 5 2 κr(x) and invoking (29), we have (32)

• 2 ≤ • 2 + ≤ O(1) • 2 ,
while from (31) it follows that the function which combines with (32) to imply that

f (x) = x 2 + satisfies f ′ (x) -f ′ (y) * ≤ O(1)κ x -y ,
f ′ (x) -f ′ (y) +, * ≤ O(1)κ x -y * .
Thus, (E, • ) is O(1)κ-smooth, whence, by (32), (E, • ) is O(1)κ-regular.

4.1.5. Proof of Proposition 3.4. The fact that a subspace of a κ-smooth/regular space equipped with the induced norm is κ-smooth/regular is evident. As about the factor-space F = E/L, note that the space dual to (F, • F ) is nothing but the subspace L ⊥ = {ξ : ξ, x = 0 ∀x ∈ L} in E * equipped by the norm induced by • * . Now assume that (E, • E ) is κ-smooth. By Proposition 3.2, it follows that • * possesses property (iv) and therefore its restriction on L ⊥ possesses the same property. Applying Proposition 3.2 again, we conclude that (F, • F ) is κ-smooth. We see that passing to a factor-space preserves κ-smoothness, and since this transformation preserves also relations like (4), it preserves κ-regularity as well. (i):. To prove (i), let

p i (x i ) = x i 2 i . A.. Let ρ ∈ [2, ∞) be such that ρ ≤ p, and let r = ρ/2. Our local goal is to prove Lemma 2. The norm • on E = E 1 × ... × E m defined as (x 1 , ..., x m ) = ( x 1 1 , ..., x m m ) ρ is κ + -smooth, with (33)
κ + = κ + ρ -2
Proof. We have

p(x 1 , ..., x m ) ≡ ( x 1 1 , ..., x m m ) 2 ρ = (p 1 (x 1 ), ..., p m (x m )) r .
From this observation it immediately follows that p(•) is continuously differentiable. Indeed, ρ ≥ 2, whence r ≥ 1, so that the function y r is continuously differentiable everywhere on R m + except for the origin; the functions p i (x i ) are continuously differentiable by assumption. Consequently, p(x) is continuously differentiable everywhere on E = E 1 ×...×E m , except, perhaps, the origin; the fact that p ′ is continuous at the origin is evident. Invoking Proposition 3.2, in order to prove Lemma 2 it suffices to verify that (34) p ′ (x)p ′ (y) * ≤ 2κ + xy for all x, y. Since p ′ is continuous, it suffices to prove this relation for a dense in E × E set of pairs x, y, for example, those for which all blocks x i ∈ E i in x are nonzero. With such x, the segment [x, y] contains finitely many points u such that at least one of the blocks u i is zero; these points split [x, y] into finitely many consecutive segments, and it suffices to prove that

p ′ (x ′ ) -p ′ (y ′ ) * ≤ 2κ + x ′ -y ′
when x ′ , y ′ are endpoints of such a segment. Since p ′ is continuous, to prove the latter statement is the same as to prove similar statement for the case when x ′ , y ′ are interior points of the segment. The bottom line is as follows: in order to prove (34) for all pairs x, y, it suffices to prove the same statement for those pairs x, y for which every segment [x i , y i ] does not pass through the origin of the corresponding E i . Let x, y be such that [x i , y i ] does not pass through the origin of E i , i = 1, ..., m. Same as in the item "(i)⇒(iii)" of the proof of Proposition 3.2, for every i there exists a sequence of C ∞ convex functions {p t i (•) > 0} ∞ t=1 on E i converging to p i (•) along with first order derivatives uniformly on compact sets and such that (35)

|D 2 p t i (u i )[h i , h i ]| ≤ 2κ h i 2 i ∀(u i , h i ∈ E i ). Functions p t (u) = (p t
1 (u 1 ), ..., p t m (u m )) r clearly are convex, C ∞ (recall that p t i (•) > 0) and converge to p(•), along with their first order derivatives, uniformly on compact sets. It follows that

(36) p ′ (y) -p ′ (x), h = lim t→∞ 1 0 D 2 p t (x + t(y -x))[y -x, h]dt.
Setting F (y 1 , ..., y m ) = y r 1 +...+y r m , y ≥ 0, we have p t (u) = F 1 r (p t 1 (u 1 ), ..., p t m (u m )). Now let u ∈ [x, y], and let v ∈ E. We have

Dp t (u)[v] = r -1 F 1 r -1 (p t 1 (u 1 ), ..., p t m (u m )) i r(p t i (u i )) r-1 Dp t i (u i )[v i ] ⇒ D 2 p t (u)[v, v] = 1 r 1 r -1 ≤0 F 1 r -2 (p t 1 (u 1 ), ..., p t m (u m )) i r(p t i (u i )) r-1 Dp t i (u i )[v i ] 2 +F 1 r -1 (p t 1 (u 1 ), ..., p t m (u m )) i (r -1)(p t i (u i )) r-2 (Dp t i (u i )[v i ]) 2 + (p t i (u i )) r-1 D 2 p t i (u i )[v i , v i ] ≤ F 1 r -1 (p t 1 (u 1 ), ..., p t m (u m )) i (r -1)(p t i (u i )) r-2 (Dp t i (u i )[v i ]) 2 + 2κ(p t i (u i )) r-1 p i (v i ) whence (37) 0 ≤ D 2 p t (u)[v, v] ≤ F 1 r -1 (p t 1 (u 1 ), ..., p t m (u m )) i (r -1)(p t i (u i )) r-2 (Dp t i (u i )[v i ]) 2 + 2κ(p t i (u i )) r-1 p i (v i ) .
Taking into account that p i (•) are bounded away from zero on [x, y] and that p t i (•) converge, along with first order derivatives, to p i (•) uniformly on compact sets as t → ∞, the right hand side in bound (37) converges, as

t → ∞, uniformly in u ∈ [x, y] and v, v ≤ 1, to Ψ(u, v) = i u i ρ i 2 ρ -1 i (r -1) u i ρ-4 i (Dp i (u i )[v i ]) 2 + 2κ u i ρ-2 i v i 2 i . By evident reasons, |Dp i (u i )[v i ]| ≤ 2 u i v i , whence (38)
Ψ(u, v) ≤ i u i ρ i 2 ρ -1 i 4(r -1) u i ρ-2 i v i 2 i + 2κ u i ρ-2 i v i 2 i = [2ρ + 2κ -4] 2κ + i u i ρ i 2 ρ -1 i u i ρ-2 i v i 2 i When ρ > 2, we have i u i ρ-2 i v i 2 i ≤ i ( u i ρ-2 i ) ρ ρ-2 ρ-2 ρ i ( v i 2 i ) ρ 2 2 ρ = i u i ρ i ρ-2 ρ i v i ρ i 2 ρ
, and (38) implies that Ψ(u, v) ≤ 2κ + v 2 . This inequality clearly is valid for ρ = 2 as well. Recalling the origin of Ψ(•, •), we conclude that for every ǫ > 0 there exists t ǫ such that

t ≥ t ǫ , u ∈ [x, y], v ≤ 1 ⇒ 0 ≤ D 2 p t (u)[v, v] ≤ 2κ + v 2 + ǫ.
The resulting inequality via the same reasoning as in the proof of item "(i)⇒(iii)" of Proposition 3.2 implies that

t ≥ t ǫ , u ∈ [x, y] ⇒ |D 2 p t (u)[v, w]| ≤ (2κ + + ǫ) v w ∀v, w.
In view of this bound and (36), we conclude that

p ′ (y) -p ′ (x), h ≤ (2κ + + ǫ) y -x h
for all h, whence p ′ (y)-p ′ (x) * ≤ (2κ + + ǫ) yx . Since ǫ > 0 is arbitrary, we arrive at (34). A useful lemma.. We start with the following fact:

Lemma 3. Let (E, • ) be a finite-dimensional κ-regular space. Then there exists κ-smooth norm

• + on E such that (39) ∀(x ∈ E) : x 2 ≤ x 2 + ≤ 2 x 2 .
Proof. By definition, there exists κ + ∈ [1, κ] and a norm π(•) on E which is κ + -smooth and such that

∀(x ∈ E) : x 2 ≤ π 2 (x) ≤ µ x 2 , µ = κ/κ + ,
or, which is the same,

(40) ∀ξ ∈ E * : π 2 * (ξ) ≥ ξ 2 * ≥ 1 µ π 2 * (ξ),
where E * is the space dual to E and π * , • * are the norms on E * conjugate to π, • , respectively. In the case of µ ≤ 2, let us take • + ≡ π(•), thus getting a κ + -smooth (and thus -κ-smooth as well) norm on E satisfying (39). Now let µ > 2, so that γ = 1/(µ -1) ∈ (0, 1). Let us set q * (ξ) = γπ 2 * (ξ) + (1γ) ξ 2 * , so that q * (•) is a norm on E * . We have (41) ∀ξ ∈ E * : q 2 Further, by Proposition 3.2 we have

∀(ξ, η ∈ E * , x ∈ ∂π 2 * (ξ)) : π 2 1 κ q 2 * (η).
By the same Proposition 3.2, it follows that the norm • + ≡ q(•) on E such that q * (•) is the conjugate of q(•) is κ-smooth. At the same time, (41) implies (39).

Proof of Proposition 3.6. is readily given by Lemma 3 combined with the corresponding items of Proposition 3.5. E.g., to prove (i), note that by Lemma 3 we can find κ-smooth norms q i (•) on E i such that q 2 i (x i ) ≤ x i 2 i ≤ 2q 2 i (x i ) for every i and all x i ∈ E i . Applying Proposition 3.5.(i) to the spaces (E i , q i (•)), we get that the norm q(x 1 , ..., x m ) = m i=1 q p i (x i )

1/p on E 1 × ... × E m is κ + -regular with κ + given by (17). Taking into account the evident relation

q 2 (x 1 , ..., x m ) ≤ (x 1 , ..., x m ) 2 ≤ 2q 2 (x 1 , ..., x m )
and recalling the definition of regularity, we conclude that • is κ ++ -regular, as required.

4.2. Proof of Theorem 2.1.

4.2.1.

Reduction to the case of a smooth norm. We intend to reduce the situation to the one where (E, • ) is κ-smooth rather than κ-regular. Specifically, we are about to prove the following fact:

i) When 1 ≤ α ≤ 2, one has for all N ≥ 1 and γ ≥ 0: (42) Prob    S N ≥ exp{1}κ + γ N i=1 σ 2 i    ≤ 2 exp - 1 64 min γ 2 ; γ 2-α * γ α , where (
γ * ≡ γ * (α, σ N ) =              32 8α * 2 α * α-1 2-α σ N 2 σ N α * α 2-α ≥ 16 σ N 2 σ N α * α 2-α ≥ 16, α * = α α-1 , 1 < α < 2, lim α→1+0 γ * (α, σ N ) = 16 σ N 2 σ N ∞ , α = 1, lim α→2-0 γ * (α, σ N ) = +∞, α (43)
(ii) When α = 2, the bound (42) improves to

(44) (∀N ≥ 1, γ ≥ 0) : Prob    S N ≥ √ κ + γ N i=1 σ 2 i    ≤ exp{-γ 2 /3}. (iii) When the condition E i-1 exp{ ξ i 2 σ -2 i } ≤ exp{1} in (C 2 [σ ∞ ]) is strengthened to ξ i ≤ σ i almost surely, i = 1, 2, ..., the bound (42) improves to (45) (∀N ≥ 1, γ ≥ 0) : Prob    S N ≥ √ κ + γ N i=1 σ 2 i    ≤ exp{-γ 2 /2}.
i , i = 1, ..., N , be Borel functions on Ω such that ψ i is F i -measurable, let α ∈ [1, 2]
, and let µ i , ν i > 0 be deterministic reals. Assume that almost surely one has

(46) E i-1 {ψ i } ≤ µ i , E i-1 {exp{|ψ i | α /ν α i }} ≤ exp{1}, 1 ≤ i ≤ N.
It is easily seen that

0 ≤ t ≤ 1/4 ⇒ exp{t|s|}s 2 ≤ exp{|s| α } ∀s,
whence under the premise of Lemma 4 one has

0 ≤ t ≤ 1/4 ⇒ f ′′ (t) ≤ exp{1} (recall that ν = 1). It follows that 0 ≤ t ≤ 1/4 ⇒ f (t) ≤ 1 + tE{ψ} + exp{1} 2 t 2 ≤ exp{tE{ψ} + exp{1} 2 t 2 }.
Thus, one has

(51) (a) 0 ≤ t ≤ 1/4 ⇒ ln f (t) ≤ tE{ψ} + exp{1} 2 t 2 , (b) t ≥ 0 ⇒ ln f (t) ≤ α -1 (1/2) α + α -1 * (2t) α * .
Since 8t 2 ≥ exp{1} 2 t 2 and 8t 2 ≥ α -1 (1/2) α when t ≥ 1/4, (51) implies (50). 2 0 .. Since α > 1, we have for all t ≥ 0

E {exp{t n i=1 ψ j }} = E exp{t n-1 i=1 ψ j }E n-1 {exp{tψ n }} ≤ E exp{exp{t n-1 i=1 ψ j } exp{µ n t + 8(tν n ) 2 + α -1 * 2 α * (tν n ) α * }, whence ln E{t N i=1 ψ i } ≤ A N t + B N t 2 + C N t α α-1 , A N = N i=1 µ i , B N = 8 N i=1 ν 2 i , C N = α -1 * 2 α * N i=1 ν α * i .
3 0 .. Recall that we are in the situation N i=1 ν 2 i = 1. We have for all t > 0: where φ * is the Legendre transform of φ, Domφ = [0, ∞). Let t * = t * (α) be the unique positive root of the equation

Prob {Ψ N > A N + γν} = Prob {exp{tΨ N } > exp{tA N + tγ}} ≤ E {exp{tΨ N }} exp{-tA N -tγ} ≤ exp{B N t 2 + C N t α α-1 -tγ}, whence Prob{Ψ N > A N + γ} ≤ inf t>0 exp{B N t 2 + C N t α α-1 -tγ}. whence also ln (Prob{Ψ N > A N + γ}) ≤ ln(2) + inf t>0 max[2B N t 2 , 2C N t α α-1 ] φ(t) -γt ≡ ln(2) -φ * (γ),
B N t 2 = C N t α * , that is, t * = (B N /C N ) α-1 2-α .
The function φ(t) is strongly convex on [0, ∞), equals 2B N t 2 to the left of t * and equals 2C N t α * to the right of t * . Let γ -= γ -(α) be the left, and γ + = γ + (α) be the right derivative of φ at t * , so that

4B N t * = γ -≤ γ + = 2C N α * t 1 α-1 * .
The function φ * (γ) is as follows: since φ is strongly convex on [0, ∞), φ ′ (0) = 0 and φ(t)/t → ∞ as t → ∞, φ * is continuously differentiable and convex on [0, ∞); when 0 ≤ γ ≤ γ -, φ * coincides with the Legendre transform φ * ,-(γ) = 1 0 : Preparations.. Given κ-smooth space (E, • ), let us set

V (ξ) = 1 2 ξ 2 , ξ ≤ 1 ξ -1 2 , ξ ≥ 1 , V β (ξ) = βV (ξ/β) [β > 0], v(x) = 1 2 x 2 * .
Observe that 2. V (•) is continuously differentiable with V ′ (ξ) -V ′ (η) * ≤ κ ξη and is Lipschitz continuous, with constant 1, w.r.t. • ;

The second claim is evident. To prove the first, note that the function v(•) on the entire R n is strongly convex w.r.t. • * with parameter κ -1 , whence, of course, so is the function v which is equal to v in the unit ball and is +∞ outside of this ball. Given ξ, η and setting x = V ′ (ξ), y = V ′ (η), we have ξ ∈ ∂v(ξ), η ∈ ∂v(y), whence ξη xy * ≥ xy, ξη ≥ κ -1 xy 2 * , so that V ′ (ξ) -V ′ (y) * = xy * ≤ κ ξη .

3. One has

(53) (a) |V β (ξ + η) -V β (ξ)| ≤ η (b) V β (ξ + η) -V β (ξ) ≤ V ′ β (ξ), η + κ 2β η 2 .
It clearly suffices to consider the case of β = 1, that is, V β ≡ V .

E n-1 {ψ n } ≤ E n-1 a n , ξ n + κ 2β ξ n 2 = E n-1 a n , ξ n + κ 2β ξ n 2 = E n-1 κ 2β ξ n 2
[since a n is F n-1 -measurable and E n-1 {ξ n } = 0] ≤ κ 2β σ 2 n exp{1}.

≤ O( 1 )

 1 exp{-O(1)γ α } for all γ ≥ 0; here in what follows, all O(1) are positive absolute constants.

( 2 )

 2 p(x) = p(y) = 1 ⇒ p * (p ′ (x)p ′ (y)) ≤ θ 2 p(xy) (here p * is the norm on the dual space E * , which is dual to p). Examples of κregular norms with "moderate" κ include the spaces (R n , • p ) (L p on an npoint set with unit masses of points) and the spaces (R m×n , |•| p ), 2 ≤ p ≤ ∞, of m × n matrices with the Shatten norms |X| p = σ(X) p , σ(X) being the vector of singular values of a matrix X; in both cases, p ∈ [2, ∞]. The spaces of the first series are κ-regular with κ = O(1) min[p, ln(n + 1)], while the spaces of the second series are κ-regular with κ = O(1) min[p, ln(m + 1), ln(n + 1)].

  imsart-aap ver. 2007/12/10 file: LD-5-5-2008.hyper25752.tex date:September 3, 2008

4 . 1 . 4 . 1 . 1 .

 41411 imsart-aap ver. 2007/12/10 file: LD-5-5-2008.hyper25752.tex date: September 3, 2008 4. Appendix: Proofs. Proofs for Section 3.1. Justifying the Examples.

  imsart-aap ver. 2007/12/10 file: LD-5-5-2008.hyper25752.tex date:September 3, 2008

H 2 st

 2 imsart-aap ver. 2007/12/10 file: LD-5-5-2008.hyper25752.tex date:September 3, 2008

4. 1 . 3 .

 13 Proof of Proposition 3.2.

  imsart-aap ver. 2007/12/10 file: LD-5-5-2008.hyper25752.tex date:September 3, 2008

4. 1 . 4 .

 14 Proof of Proposition 3.3. imsart-aap ver. 2007/12/10 file: LD-5-5-2008.hyper25752.tex date: September 3, 2008

  imsart-aap ver. 2007/12/10 file: LD-5-5-2008.hyper25752.tex date: September 3, 2008 Assuming ǫ ≤ κ/10, let us set B = {x : W (x) ≤ κ}. Then B is a closed convex set symmetric w.r.t. the origin and such that (29) {x : x ≤ 9 10 κ} ⊂ B ⊂ {x : x ≤ 5 2 κ} due to (28.b). B is the unit ball of certain norm r(x) on E; by (29) we have (30) 2 5

  imsart-aap ver. 2007/12/10 file: LD-5-5-2008.hyper25752.tex date:September 3, 2008

4. 1 . 6 .

 16 Proof of Proposition 3.5.

  imsart-aap ver. 2007/12/10 file: LD-5-5-2008.hyper25752.tex date:September 3, 2008

Theorem 4 . 1 .

 41 Let (E, • ) be κ-smooth, let E-valued martingale-difference ξ ∞ satisfy (C α [σ ∞ ]),and let S N = N i=1 ξ i , σ N = [σ 1 ; ...; σ N ]. Then imsart-aap ver. 2007/12/10 file: LD-5-5-2008.hyper25752.tex date: September 3, 2008

  imsart-aap ver. 2007/12/10 file: LD-5-5-2008.hyper25752.tex date:September 3, 2008

1 8B N γ 2 1 8B N γ 2 ,-

 1212 of the function 2B N t 2 on the axis; when γ ≥ γ + , φ * coincides with the Legendre transform φ * ,+ (γ) = (2C N ) 1-α α γ α of the function 2C N |t| α * on the axis. In the segment [γ -, γ + ] φ * is linear with the slopeφ ′ * ,-(γ -) = φ ′ * ,+ (γ + ) = t * . Now let θ = φ * ,-(γ -)/φ * ,+ (γ -), and let ω(γ) = θφ * ,+ (γ). Observe that ω(γ) ≤ φ * (γ) when γ ≥ γ -.Indeed, at the point γ+ the functions φ * ,+ and φ * have equal values and equal derivatives, and since φ * is linear in ∆ = [γ-, γ+], we conclude from convexity of φ * ,+(•) that φ * ,+(γ) ≥ φ * (γ) on ∆, while 0 ≤ φ ′ * ,+ (γ) ≤ φ ′ * (γ) ≡ φ ′ * ,+ (γ+) on ∆. Therefore θ ≤ 1, and since φ ′ * is nondecreasing, we have ω ′ (γ) ≤ φ ′ * (γ) on ∆. Since ω(γ-) = φ * (γ-), we conclude that ω ≤ φ * everywhere on ∆. Since θ < 1 and φ * ,+ is positive, when γ ≥ γ+ we have ω(γ) ≤ φ * ,+(γ) = φ * (γ).The bottom line is thatφ * (γ) ≥ 0 ≤ γ ≤ γ - D N γ α , γ ≥ γ - , D N = φ * ,-(γ -) γ αRecalling the definition of A N , B N . C N , we arrive at (47) -(48).

4 0 4 . 2 . 3 .

 0423 .. We have proved the assertion of Proposition in the case of 1 < α < 2. This combines with the standard approximation arguments to yield the assertion in the cases of α = 1 and α = 2. Completing the proof of Theorem 4.1.

2 +

 2 imsart-aap ver. 2007/12/10 file: LD-5-5-2008.hyper25752.tex date: September 3, 2008 1. V β (•) is the Legendre transform of the restriction of βv(•) on the • *unit ball, whence V ′ β (ξ) * ≤ 1 for all β > 0 and all ξ, and(52)x * ≤ 1 ⇒ x, ξ ≤ βv(x) + V β (ξ) ≤ β V β (ξ) ∀ξ.

  By the second claim in item 2, V is Lipschitz continuous with constant 1 w.r.t. the norm • , which implies (53.a). Relation (53.b) is readily given by the Lipschitz continuity of V ′ , see the first claim in item 2.

2 0 :

 0 Proof of Theorem 4.1.(i).. Let us fix β > 0 and setS n = n i=1 ξ i , a n = V ′ β (S n-1 ), ψ n = V β (S n ) -V β (S n-1 ),so that a n is F n-1 -measurable, and ψ n is F n -measurable. By (53.a) we have|ψ n | ≤ ξ n , whence (54) E n-1 {exp{|ψ n | α /σ α n }} ≤ exp{1},while by (53.b) we have

  To prove (ii), consider the norm|(x 1 , ..., x m )| = m 1/2 x 1 2 1 + ... + x m 2 m on E × E × ... × E. As it is immediately seen, this norm is κ-smooth. If, further, (x 1 , ..., x m ) † = whence • † is mκ-regular. The norm in (ii) isnothing but the restriction of • † on the image of E under the embedding x → (x, ..., x) of E into E × ... × E, and it remains to use Proposition 3.4. 4.1.7. Proof of Proposition 3.6.

	B.. When ρ ≤ p, we have
	( x 1	1 , ..., x m	m ) 2 p ≤ ( x 1	1 , ..., x m	m ) 2 ρ ≤ m	2 ρ -2 p ( x 1	1 , ..., x m	m ) 2 p ,
	which combines with Lemma 2 to imply that the norm in (i) is κ-regular
	with κ = [ρ + κ -2]m	2 ρ -2 p , for every ρ ∈ [2, p], and (i) follows.
	(ii):. i	x i i , then
			x 2 † ≤ |x| 2 ≤ m x 2 † ∀x ∈ E × ... × E,
	imsart-aap ver. 2007/12/10 file: LD-5-5-2008.hyper25752.tex date: September 3, 2008

  It is immediately seen that Theorem 4.1 implies Theorem 2.1. Indeed, if (E, • ) is κ-regular, by Lemma 3 there exists a norm • + on E such that (E, • + ) is κ-smooth and (39) holds true. Setting σ i = √ 2σ i , observe that (39) combines with (C α [σ ∞ ]) to imply that E i-1 exp{ ξ i Applying Theorem 4.1.(i) to the κ-smooth space (E, • + ) and σ i in the role of σ i and taking into account that S N ≤ S N + , we see that Theorem 2.1.(i) is an immediate corollary of Theorem 4.1.(i), and similarly for Theorem 2.1.(ii-iii). 4.2.2. Proof of Theorem 4.1: preliminaries. In the sequel, we need the following (essentially, well-known) fact.

	exp{1}. Proposition 4.1. Let ψ	2 + σ -2 i } ≤

imsart-aap ver. 2007/12/10 file: LD-5-5-2008.hyper25752.tex date:September 3, 2008

* Research of this author was partly supported by the NSF award DMI-0619977. AMS 2000 subject classifications: Primary 60F10; secondary 60B12, 90C15

Then for every γ ≥ 0 one has

To make the text self-contained, here is the proof. 0 0 .. Till item 4 0 of the proof, we restrict ourselves with the case when 1 < α < 2. Besides this, by evident homogeneity reasons we may assume w.l.o.g. that ν ≡ N i=1 ν 2 i = 1. 1 0 .. We start with the following Lemma 4. Let α ∈ (1, 2), ν > 0 and ψ be a real-valued random variable such that (49)

E{exp{|ψ/ν| α }} ≤ exp{1}.

Proof. 1) Let t ≥ 0 be fixed. W.l.o.g. we can assume that ν = 1. By Young inequality, we have

The concluding inequality above can be justified as follows: setting

for all s, and since (α exp{1}/2)

Invoking (52), we get

Taking into account (54), (55) and applying Proposition 4.1, we arrive at

given by (48). Optimizing this bound in β > 0, we arrive at (42). Theorem 4.1.(i) is proved.

3 0 : Proof of Theorem 4.1.(ii-iii).. These results are given by exactly the same reasoning as above, with the role of Proposition 4.1 played by the following statement: Proposition 4.2. Let ψ i , i = 1, ..., N , be Borel functions on Ω such that ψ i is F i -measurable, and let µ i ≥ 0, ν i > 0 be deterministic reals. Assume that almost surely one has ∀i : E i-1 {ψ i } ≤ µ i , and either (56)

∀i

Then for every γ ≥ 0 one has (58)

, case of (56) exp{-γ 2 /2}, case of (57) . Proof. Let (56) be the case. It is immediately seen that exp{s} ≤ s + exp{9s 2 /16} for all s. We conclude that if 0 ≤ t ≤ 4 3ν i , then

Besides this, we have tx ≤

and the latter quantity is ≤ exp(

) when t ≥ 4 3ν i . Invoking (59), we arrive at

It follows that

Therefore for γ ≥ 0 we get

, as required in the first bound in (58). In the case of (57), by Azuma-Hoeffding's inequality [START_REF] Azuma | Weighted sums of certain dependent random variables[END_REF], we have ∀t ≥ 0 : E n-1 {exp{tφ i }} ≤ exp{tµ i + σ 2 i /2}; with this relation in the role of (60), the above reasoning results in the second bound in (58).