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?
 A: 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.
A: 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.
A: 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


*

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


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


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