1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

$\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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.