Let $f$ be convex, and $g$ be a convex surrogate of $f$. Does a Lipschitz-smooth $g-f$ imply $f$ and $g$ have the same subgradients?

Question

Let $f,g : \mathbb{R}^N \to \mathbb{R}$ be convex functions, but not necessarily differentiable. Suppose $g$ is a 'majorant' or 'surrogate' of $f$ at $\xi$ with the following properties:

1. $g(x) \geq f(x)$ for all $x$.
2. The error function $h(x) = g(x) - f(x)$ is differentiable with a Lipschitz continuous gradient. Moreover,
   • $h(\xi) = 0$
   • $\nabla h(\xi) = 0$

In simple words, $g$ is an upperbound of $f$ that is equal at $\xi$, and if they were to be differentiable, would match gradients at $\xi$, too.

My question: Do $f$ and $g$ share the same set of subgradients at $\xi$? If not, is there a simple counter example?

The inclusion $\partial f(\xi) \subseteq \partial g (\xi)$ follows from condition 1. For a subgradient $u \in \partial f(\xi)$,

$g(x) \geq f(x) \geq f(\xi) + u^T (x - \xi) = g(\xi) + u^T (x - \xi),$

for all $x$.

Is condition 2 enough to prove $\partial f(\xi) \supseteq \partial g (\xi)$?

Answer 1

I think that $\nabla h(\xi) = 0$ is enough to conclude equality of the subdifferentials. Indeed, this implies that the directional derivatives coincide, i.e., $f'(\xi;h) = g'(\xi;h)$ for all directions $h$. Moreover, the subdifferential can be reconstructed from the directional derivatives $$ \partial f(\xi) = \{ u \in \mathbb R^N \mid u^\top h \le f'(\xi; h) \;\forall h\}. $$