Suppose we have a convex function $f(x)$ defined on some compact convex set $X \subset \mathbb R$ with minimiser $x^* \in X$. Without loss of generality $X$ contains the origin.
We run some algorithm to find a point $y^* \in X$ with $f(y^*)-f(x^*) < \epsilon$ where $\epsilon$ is a known small quantity.
Is it possible to find a nearby function $g_\epsilon(x)$ such that $y^*$ minimises $g_\epsilon(x)$? By nearby I mean we can bound $\max \{|f(x)-g_\epsilon(x)|:x \in X\}$ in terms of $\epsilon$ and for $\epsilon=0$ we have $g_\epsilon \equiv 0$.
In the special case of a quadratic $f(x) = b\|x-a\|^2$ for $a \in X$ the answer is yes. If $f(y^*)-f(x^*) < \epsilon$ then $b \|y^*-a\| < \epsilon$ and since $\|\nabla^2 f(x)\|= bI$ we have $\|\nabla f(y^*)\| \le b \|y^*-x^*\| =b \|y^*-a\|\le \epsilon$. Hence we can take $g(x) = f(x) - \nabla f(y^*) \cdot x$ which has zero gradient at $y^*$. Also we have $$\max \{|f(x)-g_\epsilon(x)|:x \in X\} = \max \{|\nabla f(y^*) \cdot x|:x \in X\} $$ $$\le \max \{\|\nabla f(y^*)\| \|x\|:x \in X\} \le \epsilon\max \{\|x\|: x \in X\} \le \epsilon \,\text{diam}(X).$$
Yes. Given $f$ and $y^*$ define $g(x) = \max \{ f(x), f(y^*)\}$. This is convex as the max of two convex functions. It collapses the convex region $C = \{x \in X: f(x) \le f(y^*)\}$ into a flat section. The min and max of the original function over that region are $f(x^*)$ and $f(y^*)$. From this we see $\max |f(x)-g(x)| \le f(y^*)$ for all $x \in C$. For $x \in X-C$ we have $f(x)=g(x)$ and so $\max |f(x)-g(x)| \le f(y^*)$ for all $x \in X$.