7
$\begingroup$

Can we apply momentum to projected gradient descent? If so, how should we do that?

In the domain I'm working on, momentum greatly speeds up gradient descent. However, I want to do projected gradient descent, rather than plain-old gradient descent. In project gradient descent, after each update step, we project $x$ to a convex set $\mathcal{C}$. If I apply momentum naively to projected gradient descent, things seem to work poorly. I'm guessing this is because the projection changes the input to the next iteration of gradient descent and the algorithm doesn't expect this.

Is there a suitable update rule for projected gradient descent with momentum? How should we modify the standard rule for momentum to incorporate the projection operation?

$\endgroup$
1
  • 1
    $\begingroup$ Do a Google search for "Accelerated Proximal Gradient Descent". There is a lot of work in this area. $\endgroup$ – Michael Grant Jul 21 '16 at 21:28
5
$\begingroup$

It appears that there are methods for accelerated projected/proximal gradient descent, though no one seems to have worked out how to combine the state-of-the-art best methods for accelerated gradient descent (e.g., Adam, RMSprop, etc.) with projected/proximal gradient descent yet -- so you can choose either projected/proximal gradient descent with a sub-par method of acceleration, or normal gradient descent with a method of acceleration that works better in practice.

In other detail... there are multiple methods of acceleration: e.g., simple momentum, Nesterov acceleration, Adagrad, Adadelta, RMSprop, Adam. In practice, experience (with ordinary gradient descent) suggests that some of these perform better than others. For instance, for some machine learning tasks, right now Adam appears to be the most effective of those.

When you move from ordinary gradient descent to projected/proximal gradient descent, there has been some work on combining some of those methods of acceleration to proximal gradient descent... but the literature lags a bit. For instance, it appears that no one has worked out how to apply Adam-style momentum to projected or proximal gradient descent. Perhaps in time the literature will catch up.

$\endgroup$
1
$\begingroup$

Yes. You simply replace the proximal mapping based update rule in FISTA 1 with the projection update rule. That is, replace

$$x_{k+1} = \text{prox}_{h,t}(x_k - t_k\nabla g(x_k))$$

with

$$x_{k+1} = P_C(x_k-t_k\nabla g(x_k))$$

where $t$ is your step size.

[1] A. Beck, M. Teboulle, "A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems", SIAM Journal on Imaging Sciences, vol. 2, no. 1, pp. 183-202, Jan 2009.

$\endgroup$
7
  • $\begingroup$ Does this have some prerequisites? e.g., that the objective function can be expressed as $F(x)=f(x)+g(x)$ where $f,g$ are convex and $\nabla f$ is Lipschitz with a known upper bound on the Lipschitz constant, or something like that? $\endgroup$ – D.W. Dec 10 '20 at 16:18
  • $\begingroup$ Yes but for projected gradient descent we have a function we want to minimize $f$ subject to a constraint. This is written as $\min_x F(x) = f(x) + I_C(x)$, where $I_C$ is an indicator function that penalizes values outside the constraint. The assumption that $f$ is $L$-smooth is already made in normal projected GD. Equivalently, we can use the projection $P_C$ for the update step instead of minimizing with the indicator. Then we are just inputting the function $f(x)$ into FISTA which has to be $L$-smooth by previous asssumption. $\endgroup$ – Matt Hough Dec 11 '20 at 8:04
  • $\begingroup$ In the notation for my answer, I have $F(x) = g(x) + h(x)$. The prox mapping is dependent on an input $h(x)$. In the case of projected gradient descent, $h(x)$ is the indicator, which is covered with the projection. So $h(x)$ is implicit and our only input is the function $g(x)$ itself. $\endgroup$ – Matt Hough Dec 11 '20 at 8:09
  • $\begingroup$ It looks like projected gradient descent does not require prior knowledge of the Lipschitz constant to be able to run the algorithm, but FISTA does. Is that correct or incorrect? $\endgroup$ – D.W. Dec 11 '20 at 20:00
  • 1
    $\begingroup$ Ahh, thank you. Looks like I need to keep reading. I appreciate it. $\endgroup$ – D.W. Dec 12 '20 at 7:25

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.