Given a convex, differentiable function $f$ (from a Hilbert space to $\mathbb{R}$) with a minimum (say $x^*$), I know you can find $x^*$ using gradient descent. Suppose now that you apply gradient descent to a linear perturbation of $f$: \begin{equation} \hat{f} : x \mapsto f(x) + \langle x, w \rangle \end{equation} ($w$ being a small vector in the Hilbert space). I know both the infimum value of $\, \hat{f}$ and its minimum point (if it exists at all) may be very different from that of $f$ but it seems to me that the difference between the gradients at each iteration $\|\nabla f (x_n) - \nabla \hat{f} (\hat{x}_n)\| $ should stay of the order of $\mathcal{O} (\|w\|)$.

Any idea if this is indeed the case and why ? I would be forever grateful !

  • 1
    $\begingroup$ I must be missing something. Why would the gradient be on the order of $\|w\|$? After all, the gradient is exactly $\nabla f(x) + w$. What is preventing $\|\nabla f(x)\|\gg\|w\|$, or for that matter $\|\nabla f(x)+w\|\ll\|w\|$? Indeed, when near a solution, you're going to want the gradient to be zero, not on the order of $\|w\|$. $\endgroup$ – Michael Grant Jul 9 '15 at 17:32
  • $\begingroup$ Of course, if $\hat{f}(\hat{x}^*)+w=0$, then $\|\hat{f}(\hat{x}^*)\|=\|w\|$. $\endgroup$ – Michael Grant Jul 9 '15 at 21:03
  • $\begingroup$ Sorry, you're right. I meant: the difference between the gradients $\|\nabla f(x_n) - \nabla\hat{f}(\hat{x}_n)\|$ should stay small ($\mathcal{O} (\|w\|)$), hopefully. I edited the question. $\endgroup$ – Steve Jul 10 '15 at 0:18

Indeed for any $x$, we have $\nabla \hat{f}(x) = \nabla f(x) + w$ and so $\|\nabla f(x) - \nabla \hat{f}(x)\| = \|-w\| = \|w\|$.

| cite | improve this answer | |

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.