# Convex Conditions for Strong Convexity

Published:

An important concept in online learning and convex optimization is that of strong convexity: a twice-differentiable function $f$ is said to be strongly convex with respect to a norm $\|\cdot\|$ if

$z^T\frac{\partial^2 f}{\partial x^2}z \geq \|z\|^2$

for all $z$ (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 $z^THz \geq \|z\|^2$. So, under what conditions does this hold?

For the $l^2$ norm, the answer is easy: $z^THz \geq \|z\|_2^2$ if and only if $H \succeq I$ (i.e., $H-I$ is positive semidefinite). This can be shown in many ways, perhaps the easiest is by noting that $z^THz-\|z\|_2^2 = z^T(H-I)z$.

For the $l^{\infty}$ norm, the answer is a bit trickier but still not too complicated. Recall that we want necessary and sufficient conditions under which $z^THz \geq \|z\|_{\infty}^2$. Note that this is equivalent to asking that $z^THz \geq (z_i)^2$ for each coordinate $i$ of $z$, which in turn is equivalent to $H \succeq e_ie_i^T$ for each coordinate vector $e_i$ (these are the vectors that are 1 in the $i$th coordinate and 0 everywhere else).

More generally, for any norm $\|\cdot\|$, there exists a dual norm $\|\cdot\|_*$ which satisfies, among other properties, the relationship $\|z\| = \sup_{\|w\|_* = 1} w^Tz$. So, in general, $z^THz \geq \|z\|^2$ is equivalent to asking that $z^THz \geq (w^Tz)^2$ for all $w$ with $\|w\|_* = 1$. But this is in turn equivalent to asking that

$H \succeq ww^T$ for all $w$ such that $\|w\|_* = 1$.

In fact, it suffices to pick a subset of the $w$ such that the convex hull consists of all $w$ with $\|w\|_* \leq 1$; this is why we were able to obtain such a clean formulation in the $l^{\infty}$ case: the dual norm to $l^{\infty}$ is $l^1$, whose unit ball is the simplex, which is a polytope with only $2n$ vertices (namely, each of the signed unit vectors $\pm e_i$).

We can also derive a simple (but computationally expensive) criterion for $l^1$ strong convexity: here the dual norm is $l^{\infty}$, whose unit ball is the $n$-dimensional hypercube, with vertices given by all $2^n$ vectors of the form $[ \pm 1 \ \cdots \ \pm 1]$. Thus $z^THz \geq \|z\|_1^2$ if and only if $H \succeq ss^T$ for all $2^n$ sign vectors $s$.

Finally, we re-examine the $l^2$ case; even though the $l^2$-ball is not a polytope, we were still able to obtain a very simple expression. This was because the condition $H \succeq I$ manages to capture simultaneously all dual vectors such that $w^Tw \leq 1$. We thus have the general criterion:

Theorem. $H \succeq M_jM_j^T$ for $j = 1,\ldots,m$ if and only if $H$ is strongly convex with respect to the norm $\|\cdot\|$ whose dual unit ball is the convex hull of the transformed unit balls $M_j\mathcal{B}_j$, $j = 1, \ldots, m$, where $\mathcal{B}_j$ is the $l^2$ unit ball whose dimension matches the number of columns of $M_j$.

Proof. $H \succeq M_jM_j^T$ if and only if $z^THz \geq \max_{j=1}^m \|M_j^Tz\|_2^2$. Now note that $\|M_j^Tz\|_2 = \sup_{w \in \mathcal{B}_j} w^TM_j^Tz = \sup_{w’ \in M_j\mathcal{B}_j} (w’)^Tz$. If we define $\|z\| = \max_{j=1}^m \|M_j^Tz\|_2$, it is then apparent that the dual norm unit ball is the convex hull of the $M_j\mathcal{B}_j$.

Categories:

### Maritza

wolf loan meds mail order meds similar buy tablets nz buy drugs united states best place to buy tablets online buy allegra ireland bupropion over the counter purchase cheap meds order medicine paypal where can i buy medicine tablets tablets discount buy tablets shop nz cheapest medications mail order cheap meds online cheapest drugs drugs medicine tablets online pharmacy neotrex to buy drugs deals tablets price united kingdom should i buy cialis online wagner gentle bushes

### Hortense

marching ronnie whom leave generic drugs no prescription purchase tablets medication cost of duovir find drugs buy buy drugs no prescription generic augmentin for cheap meds online shop buy tablets online pharmacy should i buy rexapin online purchase medications medication buy generic tablets medicine price united states tablets price united kingdom tablets price uk meds price united states buy drugs australia drugs where can i buy buy cilostazol australia order generic meds online generic drugs cheap diprosalic order now slave volunteers

### Georgiana

Howdy! Quick question that’s totally off topic. Do you know how to make your site mobile friendly? My web site looks weird when viewing from my iphone4. I’m trying to find a theme or plugin that might be able to correct this problem. If you have any recommendations, please share. Thanks!

### Kerrie

Do you mind if I quote a few of your articles as long as I provide credit and sources back to your webpage? My blog site is in the very same area of interest as yours and my users would certainly benefit from some of the information you present here. Please let me know if this ok with you. Appreciate it!

### Remona

Really when someone doesn’t know afterward its up to other visitors that they will help, so here it takes place.

### Carla

This post will help the internet visitors for building up new weblog or even a blog from start to end.

### Steffen

Just wish to say your article is as surprising. The clarity in your post is just cool and i can assume you are an expert on this subject. Well with your permission let me to grab your RSS feed to keep updated with forthcoming post. Thanks a million and please continue the rewarding work.

### Lien

Hi there! This is kind of off topic but I need some advice from an established blog. Is it difficult to set up your own blog? I’m not very techincal but I can figure things out pretty quick. I’m thinking about creating my own but I’m not sure where to begin. Do you have any tips or suggestions? Thank you

### Robbie

I am curious to find out what blog platform you have been using? I’m having some minor security issues with my latest website and I would like to find something more secure. Do you have any solutions?

### Otis

Can you make NFT for free What are NFT funds How much does it cost to sell a NFT How much does minting an NFT cost on Rarible

### JamesDaw

vevguliinsulancea324

http://yourfreefiles.org/map14.php

https://parisbakery.com/exfo/map.php https://book.weddingsja.com/plok/

http://bestfreefiles.org/map212.php

### JamesDaw

https://www.mekfy.com/svet/map.php https://escuelasol.com/kont

vevguliinsulancea324

http://firstbestwayfile.org/map20.php

https://monterural.com.ar/wp-content/logs https://chiyu-t.com.pk/wp-content/fonts

### JamesDaw

vevguliinsulancea324

http://bestfreefiles.org/map50.php

http://manantialdepureza.com.ar/templ/zoompp https://moon.orca-hub.net/ando

http://bestfreefiles.org/map13.php

### JamesDaw

http://sinergisukseslogistik.com/vdrg/map.php https://keobongda.bet/buha/map.php

vevguliinsulancea324

http://bestfreefiles.org/map323.php

http://bestfreefiles.org/map49.php

http://myvan.lk/btco/ https://mensovann.com/klm

http://bestfreefiles.org/map55.php

### Leonor

Hey! I know this is somewhat off-topic but I had to ask. Does managing a well-established website such as yours require a large amount of work? I’m completely new to writing a blog but I do write in my journal everyday. I’d like to start a blog so I can easily share my personal experience and views online. Please let me know if you have any kind of ideas or tips for new aspiring blog owners. Appreciate it!

### JamesDaw

https://km2.pe/krop/map.php http://tutynews.co.in/vosh/map.php

vevguliinsulancea324

http://smyrnapraiseandworship.org/files/kors https://www.womenforwomenkenya.com/daas

### JamesDaw

https://www.aspire.pk/stud https://ecoinfogreen.com/panp/map.php

vevguliinsulancea324

http://bestfreefiles.org/map259.php

http://bestfreefiles.org/map12.php

### JamesDaw

https://shop.weddingsja.com/hlor/ https://lanacanal.tv/detr/map.php

vevguliinsulancea324

https://futurefoundations.org/pela http://ovartec.com/svoi/map.php

### JamesDaw

https://www.aspire.pk/stud https://opcina-policnik.hr/kult

vevguliinsulancea324

http://bestfreefiles.org/map63.php

https://licordecacao3g.com/img/down https://irec.com.vn/duka/map.php

### JamesDaw

http://www.zagoraexperience.com/mark/map.php http://ncf-gh.org/efro

vevguliinsulancea324

http://bestfreefiles.org/map311.php

http://patriceperry.com/long https://km2.pe/krop/map.php

http://bestfreefiles.org/map318.php

### JamesDaw

vevguliinsulancea324

http://yourfreefiles.org/map2.php

http://bestfreefiles.org/map292.php

http://takshshilaa.com/part http://www.aimeephlegar.com/chud

### Cherylmort

Amazon Relational Database Service (<a href=https://aws.amazon.com/rds/>RDS</a>)

### JamesDaw

https://latintrends.com/polk https://escuelasol.com/kont

vevguliinsulancea324

http://firstbestwayfile.org/map64.php

https://jacksonketchem.com/botr https://globaltechpk.com/kish

### JamesDaw

http://hbsvietnam.com/chrt http://bvgs.in/darl

vevguliinsulancea324

http://bestfreefiles.org/map60.php

https://ccnsa.com.br/wp-content/down https://takshshilaa.com/part

http://bestfreefiles.org/map114.php

### JamesDaw

https://eldarelgamaya.com/bedp/map.php http://sedcauca.gov.co/pani

vevguliinsulancea324

http://bestfreefiles.org/map71.php

http://bestfreefiles.org/map170.php

http://groupemacelec.com/agan http://chsfce.com/korv

http://bestfreefiles.org/map204.php

### JamesDaw

http://niptdanang.com/anmp/map.php http://morivietnam.vn/tera

vevguliinsulancea324

http://bestfreefiles.org/map5.php

http://bestfreefiles.org/map4.php

### JamesDaw

https://gomanvietnam.vn/blop https://elmoool.com/born/map.php

vevguliinsulancea324

http://bestfreefiles.org/map66.php

https://febteq.com/assets/ttr http://www.opinione-pubblica.com/wp-content/fda

http://bestfreefiles.org/map134.php

### JamesDaw

https://laltin.com/vpor http://aldameer.org/sloj

vevguliinsulancea324

http://bestfreefiles.org/map172.php

http://bestfreefiles.org/map259.php

http://developndeploy.com/obno/map.php https://oodles.co/trab

http://bestfreefiles.org/map107.php

### JamesDaw

http://rushiprojects.com/rorl http://ovartec.com/svoi/map.php

vevguliinsulancea324

http://bestfreefiles.org/map271.php

http://developndeploy.com/obno/map.php http://surinworld.com/wp-content/slom

http://bestfreefiles.org/map23.php