# Gradient descent with linear perturbation

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$: $$\hat{f} : x \mapsto f(x) + \langle x, w \rangle$$ ($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 !

• 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\|$. – Michael Grant Jul 9 '15 at 17:32
• Of course, if $\hat{f}(\hat{x}^*)+w=0$, then $\|\hat{f}(\hat{x}^*)\|=\|w\|$. – Michael Grant Jul 9 '15 at 21:03
• 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. – 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\|$.