If your function was strictly convex and $C^3$ (let's say on a compact interval $I$) and you had bounds on the third derivative there, it might be possible to prove its convexity on $I$ by evaluating it at sufficiently many points of $I$. If not, it's impossible to distinguish any convex function from one whose second derivative has a narrow "blip" taking it below zero between some of the points where you evaluated it. EDIT: Here's what I had in mind. Suppose you know that $|f'''| \le B$ on interval $I$. Evaluate $f$ at points $x_j = x_0 + j \delta$, $j = 0 \ldots n$ so that $I = [x_0, x_n]$, and compute $L_j = f(x_{j-1}) - 2 f(x_{j}) + f(x_{j+1})$, $j = 1 \ldots n-1$. Note that $L_j = \int_{x_{j-1}}^{x_{j+1}} (\delta - |t - x_j|) f''(t)\; dt$. If $x_{j-1} \le s \le x_{j+1}$, since $f''(s) \ge f''(t) - B |t - s|$ we have $$ \delta^2 f''(s) \ge L(j) - B \int_{x_{j-1}}^{x_{j+1}} (\delta - |t - x_j|)|t - s|\; dt \ge L(j) - B \delta^3$$ since $$ \max_{s \in [-1,1]} \int_{-1}^1 (1 - |t|)|t-s|\; dt = 1$$ Thus if $L_j \ge B \delta^3$ for all $j = 1 \ldots n-1$ you can conclude that $f'' \ge 0$ and $f$ is convex. On the other hand, if some $L_j < 0$, $f$ is not convex. If $f''$ is bounded away from $0$, this method is guaranteed to succeed as long as $\delta$ is sufficiently small. In fact if $f'' \ge c > 0$ on $I$, we will have $L_j \ge c \delta^2$, so we just need $0 < \delta < c/B$. Note that you don't need to know $c$ beforehand, you just keep taking smaller and smaller $\delta$ until you succeed.