Strong convexity definition based on subgradient

95 Views Asked by At

Suppose that we have $f: \mathbb R^d \to \mathbb R$ is convex and satisfies $$f(\textbf y) \geq f(\textbf x) + \nabla f(\textbf x)^\top(\textbf y - \textbf x) + \frac{\mu}{2} \| \textbf x - \textbf y \|^2 $$ $\forall \textbf x$ such that $\nabla f(\textbf x)$ exists and $\forall \textbf y$. Prove that $$f(\textbf y) \geq f(\textbf x) + \textbf g_{\textbf x}^\top(\textbf y - \textbf x) + \frac{\mu}{2} \| \textbf x - \textbf y \|^2 $$ for all $\textbf x, \textbf g_{\textbf x} \in \partial f(\textbf x)$ and all $\textbf y$

My attempt: I'm trying to utilize the fact that convex function $f$ is differentiable almost everywhere, which means I can find $\textbf v$ with arbitrary small norm that at $\textbf x + \textbf v$, $f$ is diferentiable. My calculation try to find a $\textbf v$ that has nice properties, but I'm stuck with term like $\nabla f(\textbf x + \textbf v)$.

I'm glad if anyone can tell if my direction is right, or if not, how can I tackle this problem. Thanks in advance