c_{i} = 1

means that changing only coordinate

i

changes

f

by at most one:

∣ f (x) - f (x^{'}) ∣ \leq 1

whenever

x_{j} = x_{j}^{'}

for all

j \neq = i

g

-certifiable when, whenever

f (x) = k

, there is a coordinate set

I

with

∣ I ∣ \leq g (k)

such that every

y

agreeing with

x

I

satisfies

f (y) \geq k

. The coordinates in

I

form a certificate for the assertion that the value is at least

k

b

Solution

The lower-tail form of the entropy method for certifiable functions states that a unit-bounded-difference,

g

-certifiable nonnegative integer-valued function satisfies

lo g E e^{- λ (Z - E Z)} \leq \frac{λ ^{2}}{2} E [g (Z)] (λ \geq 0) .

It follows by applying entropy tensorization to a minimal certificate: only its at most

g (Z)

coordinates can contribute to the one-sided variance proxy, and changing any one contributes at most one.

The Chernoff bound therefore gives

P (Z - E Z \leq - t) \leq in f_{λ > 0} exp (- λ t + \frac{λ ^{2}}{2} E [g (Z)]) .

Choosing

λ = t / E [g (Z)]

proves

P (Z - E Z \leq - t) \leq exp (- \frac{t ^{2}}{2 E [ g ( Z )]}) .

There are no discussions about this article yet.

There are currently no matching articles.