[Math] Quadratic upper bound of a convex function

convex-analysishessian-matrixinequalityupper-lower-bounds

Let $f: \mathbb{R}^d \to \mathbb{R}$ be a convex function. For some $a \in \mathbb{R}^d$, does the following hold

$$f(x) \le f(a) + \nabla f(a)^\top (x-a) + \frac{1}{2}(x-a)^\top H (x-a)$$

for some matrix $H$?

If we have $\|x^* – a\| \le \epsilon$, where $x^*$ is the minimizer of $f$, can we get some stronger results?

Best Answer

What you want is known as Lipschitz gradient or smoothness parameter. A convex function $f$ is $\beta$-smooth if it satisfies $$ f(x) \leq f(a) + \nabla f(a)^\top (x-a) + \frac{1}{2} (x-a)^\top H (x-a) $$ for $H = \beta I$. You can see other properties of smooth function here. Your second question is related to strong convex function. Please see here for more details.

Related Question