Convex Conditions for Strong Convexity
December 30, 2013 Leave a comment
An important concept in online learning and convex optimization is that of strong convexity: a twice-differentiable function is said to be strongly convex with respect to a norm if
for all (for functions that are not twice-differentiable, there is an analogous criterion in terms of the Bregman divergence). To check strong convexity, then, we basically need to check a condition on the Hessian, namely that . So, under what conditions does this hold?
For the norm, the answer is easy: if and only if (i.e., is positive semidefinite). This can be shown in many ways, perhaps the easiest is by noting that .
For the norm, the answer is a bit trickier but still not too complicated. Recall that we want necessary and sufficient conditions under which . Note that this is equivalent to asking that for each coordinate of , which in turn is equivalent to for each coordinate vector (these are the vectors that are 1 in the th coordinate and 0 everywhere else).
More generally, for any norm , there exists a dual norm which satisfies, among other properties, the relationship . So, in general, is equivalent to asking that for all with . But this is in turn equivalent to asking that
for all such that .
In fact, it suffices to pick a subset of the such that the convex hull consists of all with ; this is why we were able to obtain such a clean formulation in the case: the dual norm to is , whose unit ball is the simplex, which is a polytope with only vertices (namely, each of the signed unit vectors ).
We can also derive a simple (but computationally expensive) criterion for strong convexity: here the dual norm is , whose unit ball is the -dimensional hypercube, with vertices given by all vectors of the form . Thus if and only if for all sign vectors .
Finally, we re-examine the case; even though the -ball is not a polytope, we were still able to obtain a very simple expression. This was because the condition manages to capture simultaneously all dual vectors such that . We thus have the general criterion:
Theorem. for if and only if is strongly convex with respect to the norm whose dual unit ball is the convex hull of the transformed unit balls , , where is the unit ball whose dimension matches the number of columns of .
Proof. if and only if . Now note that . If we define , it is then apparent that the dual norm unit ball is the convex hull of the .