The upper envelope for

ψ

implies

e^{ψ (θ x)} \leq 1 + θ x + \frac{θ ^{2} x ^{2}}{2} .

μ_{i} = E [X_{i}]

, taking expectations, and using

1 + u \leq e^{u}

gives

E e^{ψ (θ X_{i}) - θ μ_{i}} \leq e^{- θ μ_{i}} (1 + θ μ_{i} + \frac{θ ^{2}}{2} E [X_{i}^{2}]) \leq exp (\frac{θ ^{2}}{2} E [X_{i}^{2}]) .

E exp {i = 1 \sum n (ψ (θ X_{i}) - θ E [X_{i}])} \leq exp {\frac{θ ^{2}}{2} i = 1 \sum n E [X_{i}^{2}]} .

Applying the lower envelope to

- ψ (θ x)

similarly gives

E exp {i = 1 \sum n (θ E [X_{i}] - ψ (θ X_{i}))} \leq exp {\frac{θ ^{2}}{2} i = 1 \sum n E [X_{i}^{2}]} .

b

Solution

P {\frac{1}{θ} \sum_{i = 1}^{n} (ψ (θ X_{i}) - θ μ) \geq t} \leq exp (- θt + \frac{θ ^{2} σ ^{2} n}{2}) .

The second bound controls the lower tail. The union bound therefore gives

P {\frac{1}{θ} \sum_{i = 1}^{n} (ψ (θ X_{i}) - θ μ) \geq t} \leq 2 exp (- θt + \frac{θ ^{2} σ ^{2} n}{2}) .

Since

μ_{θ} - μ = \frac{1}{n θ} \sum_{i = 1}^{n} (ψ (θ X_{i}) - θ μ),

putting

L = lo g (2/ δ)

θ = \frac{2 L}{σ ^{2} n}, t = 2 σ^{2} n L

makes the exponent equal to

- L

P (∣ μ_{θ} - μ ∣ \geq σ \frac{2 lo g ( 2/ δ )}{n}) \leq δ .

There are no discussions about this article yet.

There are currently no matching articles.