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? 
 A: $\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.
