  Jensen's inequality is ubiquitous in measure and probability theory,
statistics, machine learning, information theory and many other areas of
mathematics and data science. It states that, for any convex function $f\colon
K \to \mathbb{R}$ defined on a convex domain $K \subseteq \mathbb{R}^{d}$ and
any random variable $X$ taking values in $K$, $\mathbb{E}[f(X)] \geq
f(\mathbb{E}[X])$. In this paper, sharp upper and lower bounds on
$\mathbb{E}[f(X)]$, termed ``graph convex hull bounds'', are derived for
arbitrary functions $f$ on arbitrary domains $K$, thereby extensively
generalizing Jensen's inequality. The derivation of these bounds necessitates
the investigation of the convex hull of the graph of $f$, which can be
challenging for complex functions. On the other hand, once these inequalities
are established, they hold, just like Jensen's inequality, for \emph{any}
$K$-valued random variable $X$. Therefore, these bounds are of particular
interest in cases where $f$ is relatively simple and $X$ is complicated or
unknown. Both finite- and infinite-dimensional domains and codomains of $f$ are
covered as well as analogous bounds for conditional expectations and Markov
operators.
