1

Can somebody help me to prove that entropic regularizer $R(\mathbf{w})= \frac{1}{\eta}\mathbf{w}^T\log \mathbf{w}$ is strongly convex with respect to $l_1$ norm.

My attempt: To show if a function $f$ is strongly convex w.r.t $\|\cdot\|_1$, I have to show if the hessian $\partial^2 f / \partial f^2 >= ss^T$, where $s$ is sign vector,i.e., $[\pm1,...,\pm 1]$. In order to proceed, I tried to calculte hesisan of entropic function but stuck as first derivative of entropic function involves division of vectors. Are their other way to prove strong convexity of entropic regularizer?

CKM
  • 1,594

1 Answers1

2

Yes, your $R$ is indeed $\frac{1}{2}$-strongly convex. The particular result you want to prove is a trivial application of Theorem 16 of this paper. To use the aforesaid theorem, simply take $X := diag(w)$, so that the eigenvalues of $X$ are the $w_i$'s and its trace norm is simply $\|w\|_1$.

In fact the aforementioned paper shows a much bigger result, Theorem 6 (it's fairly possibly this result was known earlier, but this is another debate...): a closed convex function $R$ is $\beta$-strongly convex w.r.t to a norm $\|.\|$ iff its Fenchel-Legendre transform (aka convex conjugate) $R^*$ is $\frac{1}{\beta}$-strongly smooth w.r.t the dual norm $\|.\|_*$.

dohmatob
  • 9,535