Question about strong convexity

Question

Let $f:\mathbb R^n\to\mathbb R$ be $C^1$-smooth over $\mathbb R^n$. Let $l\in\mathbb R$ be a constant with $l>0$. Prove that if, for all $x,y\in\mathbb R^n$, $$\|\nabla f(y)-\nabla f(x)\|_2^2\ge l|f(y)-f(x)|$$ then $f$ is strongly convex.

I don't really know how to begin. I tried substituting $x + h$ for $y$ and taking the Taylor approximation of $f(x + h)$ around $f(x)$. The RHS becomes $$h^{\mathrm T}\nabla f(x) + \phi(x)$$ Where $\phi$ is our remainder function. Since $f$ is only $C^1$-smooth, the remainder function isn't well conditioned and this is sort of where I hit a wall. My friends in similar classes recommended finding something to integrate, but I don't really know what.

Furthermore, this sort of fails some sanity checks. Like if you take a convex function and negate it, the result shouldn't be convex; however, negating a function doesn't affect whether it satisfies $$\|\nabla f(y) - \nabla f(x)\|_2^2 \ge l |f(y) - f(x)|\text.$$

Answer 1

The claim as stated is false: $f=0$ is an obvious counter-example. And, as you already mentioned, if $f$ satisfies the inequality then also $-f$.

In addition, every smooth function satisfying the inequality has to be a constant:

If $f$ satisfies the inequality and $\nabla f$ is Lipschitz, then necessarily $f$ is constant: $$ |f(x+h)-f(x)|\le l \|\nabla f(x+h)-\nabla f(x)\|^2 \le l \cdot L \cdot \|h\|^2. $$ Dividing by $\|h\|$ and letting $h\to 0$ proves $\nabla f(x)=0$.

Hence, the claimed statement is not even wrong.

Edit: Also every convex $C^1$ function satisfying the inequality is constant. I found a result of Rockafellar ('Second-order convex analysis', Journal of Nonlinear and Convex Analysis 1 (1999), 1-16, available at https://sites.math.washington.edu/~rtr/papers/rtr176-SecondOrderConvexAnalysis.pdf), which could be of use here:

Let $f$ be $C^1$ and convex. Then for almost all $x$ the map $\nabla f$ satisfies a Lipschitz estimate. Then all such functions $f$ satisfying the inequality above have $\nabla f=0$ almost everywhere. Hence, almost all points in $\mathbb R^n$ are global minimizers of $f$, so $f$ has to be constant.