2
$\begingroup$

Is the Chi-squared divergence $\sum_{i} \frac{(x(i)-y(i))^2}{x(i)}$ a Bregman divergence? I.e., can it be written as $\phi(x) - \phi(y) - \langle\phi'(y),x-y\rangle$?

If so, what is the potential function $\phi(x)$ from which it is generated? If not, does there exists a Bregman divergence which bounds Chi-square divergence from above?

$\endgroup$
  • 2
    $\begingroup$ This seems more appropriate for Math, but still, why the downvote? $\endgroup$ – Sasho Nikolov Oct 12 at 15:37
  • $\begingroup$ Not a proof, but since this paper introduces a generalization of Bregman divergences and then show this generalization includes the chi-squared divergence, it's fair to assume the "usual" Bregman divergences do not. As for the last question: KL divergence? $\endgroup$ – Clement C. Oct 12 at 18:41
  • $\begingroup$ Thanks! I it an interesting work.. however, I didn't spot there proof of non-existence (they indeed show their generalization includes the chi-squared, however, they don't show -- as far I understood -- it cannot be realized as a Bregman divergence). + I think that the Chi square upper bounds the KL and not vice-versa: cstheory.stackexchange.com/questions/30693/… $\endgroup$ – Yonatan Oct 13 at 2:04
  • $\begingroup$ @Yonatan Of course, my bad :( $\endgroup$ – Clement C. Oct 13 at 17:17
4
$\begingroup$

$\chi^2$-divergence is not a Bregman divergence.

I'll show it for sample size $n=1$. We would have $$ (x-y)^2/x=f(x)-f(y)-f'(y)(x-y)$$ If $y=0$ and $x>0$ this says $$x=f(x)-f(0)-xf'(0),$$ $$1=\frac{f(x)-f(0)}x-f'(0).$$ Taking $x\to 0^+$ this gives the contradiction $1=0$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.