Timeline for Is KL divergence $D(P||Q)$ strongly convex over $P$ in infinite dimension
Current License: CC BY-SA 4.0
30 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 6, 2018 at 22:14 | comment | added | Maziar Sanjabi | I have not seen any satisfactory proof that would be as general as your proof. All the arguments in the literature follow the lines of proof provided here: cs.cmu.edu/~yaoliang/mynotes/sc.pdf Note that it only proves the strong convexity on the relative interior of the probability simplex. | |
| Aug 5, 2018 at 13:22 | comment | added | Iosif Pinelis | Can you give references to the fact that you mentioned that the KL divergence is strongly convex in $P$ in finite dimensions? | |
| Aug 2, 2018 at 1:01 | vote | accept | Maziar Sanjabi | ||
| S Aug 2, 2018 at 1:01 | history | bounty ended | Maziar Sanjabi | ||
| S Aug 2, 2018 at 1:01 | history | notice removed | Maziar Sanjabi | ||
| Jul 31, 2018 at 14:05 | answer | added | Iosif Pinelis | timeline score: 9 | |
| Jul 31, 2018 at 11:22 | comment | added | Aryeh Kontorovich | @MaziarSanjabi can you point me to a proof that negentropy is strongly convex infinite dimensions? Then I can try to work out a proof for the countable (and maybe even continuous) case. | |
| Jul 31, 2018 at 0:36 | comment | added | Maziar Sanjabi | @Arash You can assume that we are only considering $P$'s that are absolutely continuous with respect to a fixed measure $Q$. I believe the strong convexity, if true, would be with respect to $1$-norm which is not a Hilbertian norm (does not come from an inner product). | |
| Jul 30, 2018 at 23:16 | comment | added | Arash | Moreover your KL divergence is defined only over the set of measures that are absolutely continuous w.r.t. Q; Similar care is required for the definition of entropy for general measures (what is $dP$ inside the logarithm for example in case of singular measures?) | |
| Jul 30, 2018 at 23:12 | comment | added | Arash | @MaziarSanjabi, regarding the characaterization of KL-divergence above, how do you define an inner product over the infinite dimensional space of measures (not in general a Hilbert space and not even a Banach one) ? You can still use another defintion of strong convexity which can be adapted to metric spaces. | |
| Jul 30, 2018 at 22:59 | history | edited | Maziar Sanjabi |
added some more tags
|
|
| S Jul 30, 2018 at 21:50 | history | bounty started | Maziar Sanjabi | ||
| S Jul 30, 2018 at 21:50 | history | notice added | Maziar Sanjabi | Authoritative reference needed | |
| Jul 30, 2018 at 20:04 | comment | added | Maziar Sanjabi | I am interested in the uncountable case. Plus, I do not follow your argument here. | |
| Jul 30, 2018 at 20:04 | history | edited | Maziar Sanjabi | CC BY-SA 4.0 |
added 207 characters in body
|
| Jul 29, 2018 at 22:00 | comment | added | Aryeh Kontorovich | Why can't you argue the convexity of negentropy by continuity, at least in the case of countable dimension? Approximate a distribution $P$ with countable support by truncating to $P_n$ with support of size $n$. The entropy limits should work, no? | |
| Jul 29, 2018 at 15:25 | comment | added | Maziar Sanjabi | The coefficient does not depend on the dimension. But it is not obvious to me why it should be true. Do you know of any references? | |
| Jul 29, 2018 at 15:22 | comment | added | Aryeh Kontorovich | If the coefficient of strong convexity doesn’t depend on the dimension, it should carry over to infinite dimensions. | |
| Jul 29, 2018 at 15:15 | comment | added | Maziar Sanjabi | yes. In finite dimension it is true. | |
| Jul 29, 2018 at 14:23 | comment | added | Aryeh Kontorovich | Oh I see. Do you know that this holds in finite dimensions? | |
| Jul 29, 2018 at 14:15 | comment | added | Maziar Sanjabi | But that only proves strict convexity at best. I’m looking for strong convexity. | |
| Jul 29, 2018 at 8:51 | comment | added | Aryeh Kontorovich | See Theorem 11 in the paper I linked. | |
| Jul 29, 2018 at 8:07 | comment | added | Maziar Sanjabi | In the problem that I was working on, the set of $P$'s comes from transport plans between two marginal distributions $p$ and $q$ with bounded entropy. Thus, the lower bound is obvious and the set of bounded entropy $P$'s could be convex. So, it seems that above argument could be used to prove strong convexity of negative entropy on the convex set of tranports with bounded H. | |
| Jul 29, 2018 at 8:02 | comment | added | Maziar Sanjabi | It suffices to prove the statement for the negative entropy $H(P) = \int dP log(dP)$. It seems that for $P$ and $Q$ with bounded negative entropy, $H(P)-H(Q)-\langle H'(Q), P-Q\rangle = KL(P||Q)$ (I am not sure if this equality could be proved for general $P$ and $Q$). With this equality, one can use Pinsker's inequality to derive the lower bound $H(P)-H(Q)-\langle H'(Q), P-Q\rangle \geq \frac{1}{2}\|P-Q\|_1^2$. But this does not prove the strong convexity unless one knows that on the space of possible $P$ and $Q$'s there is a fixed lower bound on the H. No fixed upper bound on $H$ is needed. | |
| S Jul 29, 2018 at 0:03 | history | suggested | Ali Taghavi |
I add a tag.
|
|
| Jul 29, 2018 at 0:01 | review | Suggested edits | |||
| S Jul 29, 2018 at 0:03 | |||||
| Jul 28, 2018 at 22:21 | comment | added | Maziar Sanjabi | Which result in this paper are you referring to? | |
| Jul 28, 2018 at 22:10 | comment | added | Aryeh Kontorovich | See the proofs here -- arxiv.org/pdf/1206.2459.pdf -- they hold in infinite dimensions (though the paper formally deals with finite dimensions). | |
| Jul 28, 2018 at 21:49 | review | First posts | |||
| Jul 28, 2018 at 23:21 | |||||
| Jul 28, 2018 at 21:47 | history | asked | Maziar Sanjabi | CC BY-SA 4.0 |