## 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 .