Limites sur

Si est une fonction convexe, l'inégalité de Jensen indique que , et mutatis mutandis lorsque est concave. De toute évidence, dans le pire des cas, vous ne pouvez pas dépasser la limite en termes de pour un convexe , mais existe-t-il une limite qui va dans ce sens si est convexe mais "pas trop convexe"? Existe-t-il une borne standard qui donne des conditions sur une fonction convexe (et éventuellement la distribution aussi, si nécessaire) qui vous permettrait de conclure que , où $f$ $f(\textbf{E}[x]) \le \textbf{E}[f(x)]$ $f$ $\textbf{E}[f(x)]$ $f(\textbf{E}[x])$ $f$ $f$ $f$ $\textbf{E}[f(x)] \le \varphi(f)f(\textbf{E}[x])$ $\varphi(f)$ est une fonction de la courbure / degré de convexité de ? Quelque chose qui ressemble à un état de Lipschitz, peut-être? $f$

randomness pr.probability randomized-algorithms Ian
la source

Voter pour fermer comme hors sujet. math.stackexchange.com peut-être?

Aryabhata du

Je pense que cette question doit rester ouverte; c'est le genre d'inégalité que de nombreux théoriciens du travail trouveraient régulièrement utile.

Aaron Roth

Je sais que c'est plus proche des mathématiques pures que la plupart des questions posées jusqu'à présent, mais je dirais que c'est sur le sujet car ce genre de chose revient fréquemment dans l'analyse des algorithmes randomisés (qui est l'application que j'ai dans esprit). Je pense que les mathématiques qui sont fortement utilisées en informatique devraient être considérées comme un jeu équitable pour les questions.

Ian

voter pour rester ouvert. définitivement sur le sujet

Suresh Venkat

Je vote également pour rester ouvert.

Jeffε

EDIT: la version originale a manqué une valeur absolue. Pardon!!

Salut Ian. Je décrirai brièvement deux exemples d'inégalités, l'un utilisant une borne de Lipschitz, l'autre utilisant une borne sur la dérivée seconde, puis je discuterai de certaines difficultés de ce problème. Bien que je sois redondant, car une approche utilisant un dérivé explique ce qui se passe avec plus de dérivés (via Taylor), il s'avère que la deuxième version dérivée est assez agréable.

Tout d'abord, avec une limite de Lipschitz: retravaillez simplement l'inégalité standard de Jensen. La même astuce s'applique: calculer l'expansion de Taylor à la valeur attendue.

Plus précisément, Soit mesure correspondante et fixons . Si a la constante Lipschitz , alors par le théorème de Taylor $X$ $\mu$ $m := \textrm E(x)$ $f$ $L$

f (x) = f (m) + f^{'} (z) (x - m) \leq f (m) + L | x - m |,

$f(x) = f(m) + f'(z)(x-m) \leq f(m) + L|x-m|,$

où (notez que et sont possibles). En utilisant cela et en retravaillant la preuve Jensen (je suis paranoïaque et j'ai vérifié que la norme était bien sur wikipedia), $z \in [m, x]$ $x\leq m$ $x> m$

\begin{aligned} E (f (X)) & = \int f (x) d μ (x) \leq f (m) \int d μ (x) + L \int | x - m | d μ (x) \\ = f (E (X)) + L E (| X - E (X) |) . \end{aligned}

$\begin{align} \operatorname{E}(f(X)) & = \int f(x) \, d\mu(x) \leq f(m) \int d\mu(x) + L\int |x-m| \, d\mu(x) \\[6pt] & = f(\operatorname{E}(X)) + L \operatorname{E} (|X-\operatorname{E}(X)|). \end{align}$

Maintenant, supposons . Dans ce cas, $|f''(x)| \leq \lambda$

\begin{aligned} f (x) & = f (m) + f^{'} (m) (x - m) + f^{″} (z) \frac{(x - m)^{2}}{2} \\ \leq f (m) + f^{'} (m) (x - m) + λ \frac{(x - m)^{2}}{2}, \end{aligned}

$\begin{align} f(x) & = f(m) + f'(m)(x-m) + f''(z) \frac{(x-m)^2} 2 \\[6pt] & \leq f(m) + f'(m)(x-m) + \lambda \frac{(x-m)^2} 2, \end{align}$

et donc

\begin{aligned} E (f (X)) & \leq f (m) + f^{'} (m) (E (X) - m) + \frac{λ E ((X - m)^{2})}{2} \\ = f (E (X)) + \frac{λ Var (X)}{2} . \end{aligned}

$\begin{align} \operatorname{E}(f(X)) & \leq f(m) + f'(m)(\operatorname{E}(X) - m) + \frac {\lambda \operatorname{E}((X-m)^2)}{2} \\[6pt] & = f(\operatorname{E}(X)) + \frac {\lambda \operatorname{Var}(X)}2. \end{align}$

Je voudrais mentionner brièvement quelques éléments. Désolé s'ils sont évidents.

La première est que vous ne pouvez pas simplement dire "wlog " en décalant la distribution, car vous changez la relation entre et . $\operatorname{E}(X) = 0$ $f$ $\mu$

Ensuite, la limite doit dépendre de la distribution d'une manière ou d'une autre. Pour voir cela, imaginez que et . Quelle que soit la valeur de , vous obtenez toujours . En revanche, $X \sim \textrm{Gaussian}(0, \sigma^2)$ $f(x) = x^2$ $\sigma$ $f(\operatorname{E}(X)) = f(0) = 0$ . Ainsi, en changeant , vous pouvez rendre arbitraire l'écart entre les deux quantités! Intuitivement, plus de masse est éloignée de la moyenne, et donc, pour toute fonction strictement convexe, augmentera. $\operatorname{E}(f(X)) = \operatorname{E}(X^2) = \sigma^2$ $\sigma$ $\operatorname{E} (f(X))$

Enfin, je ne vois pas comment obtenir une borne multiplicative comme vous le suggérez. Tout ce que j'ai utilisé dans ce post est standard: le théorème de Taylor et les bornes dérivées sont du pain et du beurre dans les bornes statistiques, et ils donnent automatiquement des erreurs additives et non multiplicatives.

Je vais y penser cependant et poster quelque chose. Une intuition vague est qu'il aura besoin de conditions très strictes sur la fonction et la distribution, et que la limite additive est en fait au cœur de celle-ci.

matus
la source

Chaque fois que je modifie, la réponse se heurte. Je vais donc souligner: la deuxième limite dérivée est serrée pour l'exemple que j'ai donné.

matus

Je pense que vous avez raison en ce que les limites additives sont les meilleures possibles sans conditions beaucoup plus fortes sur la fonction.

Ian

f (E (X)) = 0

$f(\textrm E(X))= 0$

E (f (X)) > 0

$\textrm E (f(X)) > 0$

matus

@Ian: Les preuves des inégalités de Chernoff et Azuma-Hoeffding utilisent des arguments qui rappellent cela, vous pouvez donc les lire pour vous inspirer. Voir par exemple le livre de Mitzenmacher et Upfal sur la randomisation en informatique.

Warren Schudy

Limites sur

Réponses: