Is there a formal way to characterise strong convexity about the optimum value of a strictly convex function? I have an objective that looks something like this: $J(p,q) = \sum_{i=1}^{n}d(\pi_{i},q_{i}) + \alpha\sum_{i,j}w_{ij}d(p_{i},q_{j})$ where d is a jointly convex Bregman divergence (like KL or squared Euclidean) and $\pi_{i}$'s and $w_{ij}$'s and $\alpha$ are given parameter values. At the optimal value $(\bar{p}, \bar{q})$, neither the first term, nor the second term becomes zero (this comes from the practical usage of this objective). Is it possible to show strong convexity of this function around $(\bar{p}, \bar{q})$. My objective is to show positive definiteness of the Hessian around $(\bar{p}, \bar{q})$ and I think it is easier to prove strong convexity compared to proving positive definiteness of Hessian.
[Math] Local strong convexity of a strictly convex function
convexity
Related Solutions
It is definitely not true that the homogenization of a convex polynomial is convex. In fact, any convex polynomial that is not nonnegative will no longer be convex after homogenization. (This is because homogenization preserves lack of nonnegativity and convex homogeneous polynomials are always nonnegative.)
But even if the polynomial is nonnegative, the statement is still not true. Take e.g. the univariate polynomial $10x_1^4-5x_1+2$, which is convex and nonnegative, but its homogenization $10x_1^4-5x_1x_2^3+2x_2^4$ is not convex.
(Of course, for your specific polynomial the statement can be true, but I'm answering the general question that you raised.)
What is true generally is that the homogenization of a polynomial of degree d is convex if and only if the d-th root of the polynomial is convex. See Proposition 4.4 on p. 13 of the following nice paper of Reznick for the precise statement and a proof: http://www.math.uiuc.edu/~reznick/blenders2.pdf
Time to start typing. As I said, this is going to be long and boring and I have only limited amount of free time nowadays so I'll type in chunks. If you see a flaw somewhere, comment immediately, but if everything looks like a chain of correct stupid computations leading nowhere, just keep patient and wait until it is finished.
Before passing to the proof, I should say that I slightly disagree with Pietro on what is the main issue with this problem. IMHO, it is its non-generic nature: some combinations like that are convex and some are not. Moreover, the really beautiful and structured ones aren't for simple symmetry reasons. So, I do not believe there is any good underlying mechanism for the result to be true. It is just correct by an accident and grows in the mathematical forest like an occasional mushroom that is there for no apparent reason. You can still pick it up if you can reach it, and it is edible, but it would be a futile task to search nearby for more or to come to the same spot again a month later: you'll find nothing there.
So, since no deep idea seems to be lurking behind the scenes, let us just resort to a (reasonably) careful bookkeeping. We shall merely take the second derivative and show that it is positive.
Identity 1: $$ \frac{d^2}{dx^2}\log(1\pm x^p)=\pm px^{p-2}\left[\frac p{(1\pm x^p)^2}-\frac 1{1\pm x^p}\right]\,. $$ Now let $m=2n+1$. Put $u=x^m$ and consider $$ \Phi(x)=\log[(1+x^{2m-1})(1+x^{2m-3})] $$ (those are just the first 2 factors in the full product). We have $$ \Phi''(x)=(2m-1)(2m-2-x^{2m-1})\frac {x^{2m-3}}{(1+x^{2m-1})^2} +(2m-3)(2m-4-x^{2m-3})\frac {x^{2m-5}}{(1+x^{2m-3})^2} \\ \ge (2m-1)(2m-2-u)\frac {x^{2m-3}}{(1+u)^2} +(2m-3)(2m-4-u)\frac {x^{2m-5}}{(1+u)^2} $$ (we need that $m\ge 3$ here).
Think of this as our supply of positivity consisting of $(2m-1)(2m-2-u)$ silver units $\frac {x^{2m-3}}{(1+u)^2}$ and $(2m-3)(2m-4-u)$ golden units $\frac {x^{2m-5}}{(1+u)^2}$.
Now it is time to look at $\Psi(x)=\log\left[\frac{(1+x^{m-1})(1-x^m)}{(1+x^{m})(1-x^{m+1})}\right]$. We would like to reduce the logarithm of every factor just to its leading term in the Taylor expansion. Let's take the expressions one by one and see what correction is needed for that.
The power $x^{m-3}$ (the top left factor).
The actual contribution to $\Psi''(x)$ is $(m-1)x^{m-3}\left[\frac{m-1}{(1+x^{m-1})^2}-\frac 1{(1+x^{m-1})}\right]$. To raise it to $(m-1)(m-2)x^{2m-3}$, we need to add
$$
\frac{x^{m-3}}{(1+x^{m-1})^2}\left[(m-1)^2(2x^{m-1}+x^{2(m-1)})-(m-1)x^{m-1}(1+x^{m-1})\right]
\\ =\frac{x^{2m-4}}{(1+x^{m-1})^2}[(2m-3)(m-1)+(m-1)(m-2)x^{m-1}]
\le (3m-5)(m-1)\frac{x^{2m-4}}{(1+x^{m-1})^2}\,.
$$
We want to dominate it by our units. Note that the golden ones have the power $2m-5$ while the silver ones have the power $2m-3$, so averaging one gold and one silver, we can dominate the power $2m-4$ in the estimates. Thus the cost of this upgrade is $(3m-5)(m-1)$ units (the denominator we have is larger than $(1+u)^2$, so it works in our favor)
Let us check that we have enough gold supply to pay, i.e., that
$$
\frac 12 (3m-5)(m-1)\le (2m-3)(2m-4-u)\,.
$$
Even in the worst case scenario $u=1$, this reduces to $(3m-5)(m-1)\le (4m-6)(2m-5)$, which works for $m\ge 4$ (each factor is larger). Note however that we cannot afford paying in pure gold for $m=4,5$ and have to mix at least partially there. However, this is the only case where the difference between gold and silver units matters. Everywhere else the power will be always in our favor.
The power x^{m-2} (bottom left factor) Exactly the same argument applies to that factor (replacing $m-1$ by $m$, of course), except in this case we do not lose but, conversely, get a gain towards our positivity supply. The formula for the gain is pretty much the same as the loss formula before: our advantage is $$ \frac{x^{2m-2}}{(1+x^{m})^2}[(2m-1)m+m(m-1)x^m]\ge \frac{x^{2m-2}}{(1+u)^2}m(m-1)(2+u)=:x^{2m-2}G\,. $$ The last rough estimate (just losing $m$ for no apparent reason) looks a bit idiotic at the moment, but the only way we shall use this gain will be to offset a certain loss term, so I just put it in the most convenient form for that future step.
The factors with minuses Here we need another identity: $$ \frac{d^2}{dx^2}\log(1- x^p)+p(p-1)x^{p-2}=-px^{2p-2}\left[\frac p{(1- x^p)^2}+\frac {p-1}{1- x^p}\right]\,. $$ For the proof just take Identity 1 and play a bit with algebra. If you want to run a quick mental sanity check, note that the denominators are of the same kind, the pole at $1$ has the same order and asymptotics, the asymptotics of the whole thing near $x=0$ agrees with that coming from the second term in the Taylor expansion of the corresponding logarithm, and that these requirements together with the order of decay near $\infty$ in the complex plane allow one to recover the whole formula in a unique way. Applying it with $p=m$ and $p=m+1$, we see that the loss we need to compensate for is $x^{2m-2}$ times $$ \left[\frac{m^2}{(1-x^m)^2}+\frac{m(m-1)}{1-x^m}\right]-x^2\left[\frac{(m+1)^2}{(1-x^{m+1})^2}+\frac{(m+1)m}{1-x^{m+1}}\right] \\ =\left[\frac{m^2}{(1-x^m)^2}-x^2\left(\frac{(m+1)^2}{(1-x^{m+1})^2}+\frac{m+1}{1-x^{m+1}}\right)\right] \\ +(m-1)\left[ \frac{m}{1-x^m}-x^2\frac{m+1}{1-x^{m+1}} \right]=:L_1+L_2\,. $$
Now comes the first interesting estimate: $G\ge L_2$. We shall use a simple inequality $\frac{m+1}{1-x^{m+1}}\ge \frac{m}{(1-x^m)}$ (I'll skip the proof for now because we shall prove a stronger result a few lines below) to estimate $L_2$ from above by $m(m-1)\frac{1-x^2}{1-x^m}$. Thus, it will suffice to show that $$ (2+x^m)(1-x^m)=2-x^m-x^{2m}\ge (1+x^m)^2(1-x^2)\,. $$ Note that the LHS increases and the RHS decreases as $m$ goes up, so it will suffice to consider $m=3$, i.e., to check that (after division by $1-x$) $$ (2+x^3)(1+x+x^2)-(1+x+2x^3+2x^4+x^6+x^7)\\ =1+x+2x^2-x^3-x^4+x^5-x^6-x^7\ge 0\,. $$ However $2x^2\ge x^3+x^4$ and $x+x^5\ge x^6+x^7$. Thus, we can forget about $L_2$ and $G$ from now on and concentrate on $L_1$.
We start with the following
Lemma $$ \frac{m+1}{1-x^{m+1}} - \frac{m}{(1-x^m)} \ge \frac 12 $$ Using the common denominator $(1-x^{m+1})(1+x+\dots+x^{m-1})=(1-x^m)(1+x+\dots+x^{m})$, we see that we need to prove that $$ 2(1+x+\dots+x^{m-1}-mx^m)\ge 1+x+\dots +x^{m-1}-x^{m+1}-x^{m+2}-\dots-x^{2m}\,, $$ i.e., $\sum_{k=0}^{m-1} (x^k+x^{2m-k}-2x^{m})\ge 0$, which is OK by Cauchy-Schwarz.
Now, if $B\ge A+\frac 12$, then $$ A^2-x^2 B^2= A^2(1- x^2)-x^2(B-A)(B+A)\le A^2(1-x^2)-\frac 12(B+A)\le A^2(1-x^2)-A\,. $$ So, replacing one more $B=\frac{m+1}{1-x^{m+1}}$ with $A=\frac m{1-x^m}$, we end up with $$ L_1\le \frac{m^2(1-x^2)} {(1-x^m)^2} -\frac{2x^2m}{1-x^m}=m\frac{m-(m+2)x^2+2x^{m+2}} {(1-x^m)^2} \,. $$
Now we have to assess the cost of this in our units, i.e., to find the best $\beta$ such that $$ \frac{\beta}{(1+x^m)^2}\ge m\frac{m-(m+2)x^2+2x^{m+1}} {(1-x^m)^2} $$ or, equivalently $$ \beta (1-x^{m})^2\ge m (1+x^m)^2(m-(m+2)x^2+2x^{m+1} )\,. $$ Plugging in $x=0$ (in a trivial way) and $x=1$ (after taking the second derivative), we see that $\beta\ge\max(m^2,4(m+2))$. Now let us show that this maximum really works. Dividing by $(1-x)^2$, we can rewrite it as $$ \beta(1+x+\dots+x^{m-1})^2\ge m(1+2x^m+x^{2m})(m+2mx+(2m-2)x^2+(2m-4)x^3+\dots+4x^{m-1}+2x^m) $$ Notice now that the coefficients of the LHS (after opening the parentheses) first go up by $\beta$ and then, after position $m-1$, start dropping by $\beta$ at each step. On the other hand, on the RHS we cannot go up faster than by $m^2$ up to position $m-1$ and beyond that position, the largest drop is $4$ throughout the whole sequence. Thus the coefficient sequence of the LHS dominates at least up to position $m-1$ and then, once it starts going down, there may be at most one crossing. Also the total sum of coefficients for the LHS is at least that for the RHS (that's guaranteed by our checking the second derivative at $x=1$). But if we have any two polinomials like that, the left one dominates the right one on $[0,1]$, so we are done here. Since $4(m+2)\le m^2+3$ for $m\ge 5$ (the range we are aiming at), let us put $\beta=m^2+3$ always to keep the formulae neat.
This was the first fancy estimate. Let me know if anything is unclear.
Meanwhile, let us bring the results we had so far together. We had $(2m-1)(2m-2-u)+(2m-3)(2m-4-u)$ units total and used $(3m-5)(m-1)+m^2+3$. In the worst case scenario ($u=1$) we are left with $4m^2-16m+10$ units. If $u<1$, we have extra $4(m-1)(1-u)$ units available. From now on, we can forget all fancy different denominators and just need to figure out how many (silver) units we need to add to $x^{m-3}Q(x)$ with $Q(x)=(m-1)(m-2)-2m(m-1)x+(m+1)m x^2$ to make the resulting expression non-negative. Since our unit is $\frac{x^{2m-3}}{(1+u)^2}$, we need to find some decent number $\alpha$ (possibly, depending on $m$) such that $$ (1+u)^2 Q(x)+\alpha u\ge 0 $$ (recall that $u=x^m$). If $\alpha\le 4m^2-16m+10$, the story ends.
Write $$ Q(x)=m(m+1)\left[x-\frac{m-1}{m+1}\right]^2-2\frac{m-1}{m+1} $$ Note that $Q(x)\ge -2\frac{m-1}{m+1}$, so $[2u+u^2]Q(x)\ge -6\frac{m-1}{m+1}u$. Also put $x=\frac{m-1-t}{m+1}$ (clearly, we are in more trouble if we go left from the parabola vertex: the value of the quadratic form is the same as at the corresponding distance on the right but $u$ is smaller). Thus, it will suffice to ensure that $$ \left(\alpha-6\frac{m-1}{m+1}\right)\left[\frac{m-1-t}{m+1}\right]^m\ge (2-t^2)\frac{m-1}{m+1} $$ Hence, we can take $\alpha=\frac{m-1}{m+1}\left(6+\max_t (2-t^2)\left[\frac{m+1}{m-1-t} \right]^m\right)$. Now observe that the RHS is a decreasing function of $m$ for a fixed $t$. Indeed, the Taylor expansion of $\dfrac{ \log(1+\frac 1m)-\log(1-\frac{1+t}m)}{\frac 1m}$ in $\frac 1m$ has all the coefficients positive. Thus we can take $m=4$. This value is nice because the equation for the critical point becomes $\frac{2t}{2-t^2}=\frac 4{3-t}$ and its root $t=1$ is obvious (of course, we should also check that it is the only positive root afterwards but it rewrites as $3t+t^2=4$). Plugging $t=1$ in, we get $[\frac 52]^4=\frac{625}{16}\le 40$. Thus we are always happy with $\alpha=46\frac {m-1}{m+1}$ units. The actual reserve is $4m^2-16m+10=4(m-4)m+10$. If $m\ge 6$, this is at least $58$, which is more than enough regardless of $m$. For $m=5$, we have $30$ and it looks like we need $30\frac 13$. However notice that if $u\ge\frac 12$, say, then $24u$ is already way above $2$, so we can safely assume that $u\le \frac 12$, which immediately frees up $8$ extra units in this case.
This takes care of $n=2,3,\dots$ in the original question. Now it remains just to type a special argument for $n=1$. In principle, the above argument can be tightened to dispose of $(1+x^{2m-1})$ but I cannot bring that one down to the requested $m=5$ yet (so far it is more like $m=9$, perhaps $7$). The reserve to tap is $G$ and it is quite a strong one. The way I used it here was ridiculously sloppy (if you have both gold and silver, all the copper just goes to charity).
Now, as promised, the special case $n=1$. Again, I'll make no clever steps, just one insolent one.
The function in this case reduces to $\log\left[(1+x^5)\frac{1-x^3}{1-x^2}\right]$. Honestly taking the second derivative, we see that we need to check that $$ \frac{20-5x^5}{(1+x^5)^2}x^3-\frac{6+3x^3}{(1-x^3)^2}x+\frac{2+2x^2}{(1-x^3)^2}\ge 0\,. $$ Now I would like to multiply by the common denominator, but it will take the computational skills of Euler to multiply 3 squares of binomials, so, I'll just reduce the first term to $x^3$ (not even $3x^3$: I want to keep my numbers small, because otherwise an arithmetic error is inavoidable somewhere and I do not want to use any CAS here). I'll spare you from the exercise of multiplying out 4 binomials once and 3 binomials twice (takes about 15 minutes) and just write the result: you need to show that the polynomial with the (infinite) integer coefficient sequence $$ [2,-6,2,9,-3,-12,6,1,3,1,-2,-2,0,1,\bar 0] $$ is non-negative on $[0,1]$.
Now I know just one human-friendly criterion for such problems: start replacing sequences by their partial sums like crazy until you either get a negative tail (failure) or a non-negative sequence (success). In order to make sure that one of the two occurs, you should factor out rational roots on $(0,1)$, of course, but you normally just start and see what happens.
We get successively $$ \begin{aligned} &[2,-4,-2,7,4,-8,-2,-1,2,3,1,-1,-1,\bar 0] \\ &[2,-2,-4,3,7,-1,-3,-4,-2,1,2,1,\bar 0] \\ &[2,0,-4,-1,6,5,2,-2,-4,-3,-1,\bar 0] \\ &[2,2,-2,-3,3,8,10,8,4,1,\bar 0] \\ &[2,4,2,-1,2,10,\bar +] \\ &[2,6,8,7,9,\bar+] \end{aligned} $$ Success!
Conclusion
Formally the question is now answered in full as originally posted. I don't expect you to like this solution (it certainly lacks in uplift) but, alas, I don't expect anyone to find a nice way to handle this problem (some steps can be done in a more elegant way, as I see now, but to retype them would be too much trouble, so I'll not do it unless somebody requests it). As usual, nothing will give me more pleasure than being proved wrong in my pessimistic predictions. :-)
Best Answer
Well, not a full answer, but in general a strictly convex function does not need to be strongly convex around its minimizer. An obvious example is $f(x) = x^4$ in the real axis. While this is "locally strongly convex" away from $x=0$, its "local modulus of strong convexity" decreases to zero for $x\to 0$.
However, I am not sure if one can produce this situation in is your case of Bregman divergences but I would guess it could be possible.