# Using largest gradient at every iteration: good strategy?

Assume you have access to an oracle, which, given a set of labeled data $D = \{(x_1, y_1), ..., (x_n, y_n))\}$ returns a single data point $d^j_{max} = (x_i, y_i)$ with the property that its gradient is largest among all elements in $D$ for the current gradient descent iteration $j$.

Setting aside computational costs, it is not clear to me wether optimizing a function by greedily using the largest gradient at each iteration would be a good strategy or not.

I would assume that if the function is convex then it's a good strategy. But what about non-convex functions, such as a typical loss in a feed forward net?

$\newcommand{\R}{\mathbb R} \DeclareMathOperator*{\argmin}{argmin}$Consider a stupidly simple (convex) problem: your model class is $f_\theta(x) = \theta$ for $\theta \in \R$ (it totally ignores the input $x$). Use squared loss $(f_\theta(x) - y)^2$. Now suppose your dataset has $y_1 = \dots = y_9 = 0$ and $y_{10} = 10$; the $x_i$ are irrelevant.
The optimal solution is $$\argmin_{\theta \in \R} 9 (\theta - 0)^2 + (\theta - 10)^2 = \argmin_{\theta \in \R} 9 \theta^2 + \theta^2 - 20\, \theta + 100$$ which, taking derivatives, happens when $20 \, \hat\theta = 20$, i.e. $\hat\theta = 1$.
But what does your algorithm do? Say our current model is $\theta$. Then points 1 through 9 each have gradient $-2\theta$, and point 10 has gradient $20 - 2\theta$. So:
• If $\theta < 5$, the largest gradient (for $y_{10}$) will point to the right, and we'll increase $\theta$.
• If $5 < \theta$, the largest gradients (for $y_1$ through $y_9$) will point to the left, and we'll decrease $\theta$.
So the algorithm will end up oscillating around $5$, a point which is nowhere near the true optimal solution of 1.