# Projected gradient descent with momentum

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?

• Do a Google search for "Accelerated Proximal Gradient Descent". There is a lot of work in this area. Commented Jul 21, 2016 at 21:28
• Commented May 13, 2022 at 16:12

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.

• Hello, if you have followed the literature these years, I would like to know if there have been any new developments regarding ADAM (or other adapive gradient methods) and the interaction with projected gradient descent?
– a06e
Commented May 9, 2022 at 23:15
• For what it is worth, the AMSgrad (a variant of ADAM) paper (arxiv.org/abs/1904.09237) presents a convergence proof with projected gradient descent.
– a06e
Commented May 9, 2022 at 23:27
• Also AdaBelief considers projection in the proof: arxiv.org/abs/2010.07468
– a06e
Commented May 10, 2022 at 10:21

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.

• 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?
– D.W.
Commented Dec 10, 2020 at 16:18
• 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.
– user496277
Commented Dec 11, 2020 at 8:04
• 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.
– user496277
Commented Dec 11, 2020 at 8:09
• 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?
– D.W.
Commented Dec 11, 2020 at 20:00
• Ahh, thank you. Looks like I need to keep reading. I appreciate it.
– D.W.
Commented Dec 12, 2020 at 7:25

See the Accelerated proximal gradient method:1,2

\begin{align} y &= x_k + a_k (x_k - x_{k-1}) \\ x_{k+1} &= P_\mathcal{C}(y - t_k \nabla g(y)) \end{align}

This uses a difference of positions (both of which lie in $$\mathcal{C}$$) to reconstruct a quasi-velocity term. This is reminiscent of position based dynamics.3

1. Ryan Tibshirani. Proximal gradient descent and acceleration. Convex optimization (machine learning 10-725 / statistics 36-725). Spring 2015. Page 22.

2. Lieven Vandenberghe. Accelerated proximal gradient methods. Optimization methods for large-scale systems (ECE236C). Spring 2020. Page 8.

3. Matthias Müller, Bruno Heidelberger, Marcus Hennix, John Ratcliff. Position based dynamics. April 2007.