0
$\begingroup$

I have fundamental confusion about gradient descent (with line search) and the reason it works. I try to explain my view here, and please tell me where it goes wrong.

Let $f: \mathbb{R}^n \to \mathbb{R}$ be a convex function.

I think gradient descent (with line search) can be viewed as an alternating descent procedure as below

$1. \,$ Initialize $$ t=0, a_t = 1, x_t=0$$

$2. \,$While not converged

$\quad 2.1\,$Select steepest descent direction $$D_{t+1} = -\nabla f \approx \lim_{r\to0}\text{argmin}_{D: D\in{\mathbb{R}}^n, \|D\|^2=r} f(x_t + a_tD)$$ $\quad 2.2 \,$ Select the best step size (line search) $$a_{t+1}=\text{argmin}_{a: a\in \mathbb{R}, a>0} f(x_t + aD_{t+1})$$ $\quad 2.3 \,$ Update the current point $$x_{t+1}= x_t + a_{t+1} D_{t+1}$$ $\quad 2.4 \,$ Proceed to the next step $$t =t+1 $$

Now I noticed that while $f$ is convex in its input, it is not jointly convex in $a$ and $D$. Then why such an alternating procedure is guaranteed to converge to a global minimum at all?

$\endgroup$
17
  • 1
    $\begingroup$ In what way is 2.1 equivalent to computing the negative gradient? I'm not seeing it. $\endgroup$ Aug 6 '14 at 22:16
  • 1
    $\begingroup$ @user25004 : This is not what the gradient descent algorithm does ; the gradient descent algorithm changes the base point, and with the description you give me (and from what I understood from it) the base point doesn't change. All you change is the direction in which you look (starting at that base point) and the distance at which you think the solution is from the basepoint, in that direction. That's why I argued. $\endgroup$ Aug 6 '14 at 22:21
  • 1
    $\begingroup$ Yeah, I missed the fact that the base point isn't changing either. There's something missing here. This simply isn't the gradient method. $\endgroup$ Aug 6 '14 at 23:21
  • 1
    $\begingroup$ By the way, dear voters! It is not a good practice to vote for closing a question that contains some confusion, Especially when the goal of asking is specified as, resolving the confusion! $\endgroup$
    – user25004
    Aug 7 '14 at 6:09
  • 1
    $\begingroup$ In gradient descent, $D_{t+1}$ is $-\nabla f(x_t)$. This isn't equivalent to the formula you've given. I'm not sure it's very helpful to try to view gradient descent as an alternating minimization procedure. There are relatively short convergence proofs for gradient descent, but I think they use different ideas. Note that gradient descent also converges using a sufficiently small fixed step size (under certain mild assumptions). $\endgroup$
    – littleO
    Aug 7 '14 at 6:29
1
$\begingroup$

As I understand it, the confusion is that the problem is convex in terms of $x$, but not (understood to be) convex in terms of the step size $\alpha$ (given the statement about not jointly convex).

However, when we do a line search, we restrict $f$ to another convex set (the line). This, then, is also a convex problem, for which we find the minimum (to give us the step size). This must also bring us closer to the minimum of the original problem. If it does not, then the gradient is zero and we are at the minimum already.

So if this process converges, it must converge to the global minimum. I believe convergence follows from the convergence of ordinary gradient descent, simply because we are choosing the step size to be optimal.

$\endgroup$
1
  • $\begingroup$ Actually I see that $f$ is convex in terms of $D$ given a fixed $\alpha$, and $\alpha$ given a fixed $D$. However, I say it is not jointly convex in terms of the two variable together. $\endgroup$
    – user25004
    Aug 10 '14 at 14:57

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.