Suppose we are given $\nabla f(x)$ and $\nabla g(y)$, where $x, y\in \mathbb{R}^n$ and $f(x)$ and $g(y)$ are two convex functions. Also, suppose we are to decide which one has less value $f(x_{k+1}), y(y_{k+1})$ at $x_{k+1} = x_k -\alpha \nabla f(x) $ or $y_{k+1} = y_k -\alpha \nabla g(y)$ ($\alpha$ is the same for both). If it helps, suppose we have access to Hessian as well. Notice that the functions are not given.
Is there any way to make this decision?
My thoughts:
Suppose $f(x) = ax^2$ and $y(x) = bx^2$ so Hessians are $H(f(x)) = 2a$, $H(g(y)) = 2b$. Therefore, Hessian and gradient tell us, if we were to pick the one that has greater value of coefficient, gives less value but how it goes in higher dimension? Should we look at the norm of $\|H(f(x))\nabla f(x)\|$?
Suppose that $\newcommand{\reals}{{\bf R}}f:\reals^n\to\reals$. Assume that $x, v\in\reals^n$ and $\alpha >0$. Then the first-order Taylor approximation implies that \begin{equation} f(x-\alpha v) \simeq f(x) - \alpha \nabla f(x)^T v. \end{equation}
Therefore, \begin{equation} f(x_{k+1}) = f\left(x_k-\alpha \nabla f(x_k)\right) \simeq f(x_k) - \alpha \|\nabla f(x_k) \|_2^2. \end{equation}
Thus, you just need to inspect this quantity with $f(x_k)$ and $\|\nabla f(x_k)\|_2$ (without needing to evaluate the Hessian).
If you want to use Hessian, we can look at the second-order Taylor approximation: \begin{equation} f(x-\alpha v) \simeq f(x) - \alpha \nabla (x)^T v + \frac{1}{2} \alpha^2 v^T \nabla^2 f(x) v. \end{equation}
This implies that \begin{equation} f(x_{k+1}) = f\left(x_k-\alpha \nabla f(x_k)\right) \simeq f(x_k) - \alpha \|\nabla f(x_k) \|_2^2 + \frac{\alpha^2}{2} \nabla f(x_k)^T \nabla^2 f(x_k) \nabla f(x_k). \end{equation} Note, though, that this does not (necessarily) always give better approximation than the first one.