The Differential Inclusion Modeling FISTA Algorithm and Optimality of Convergence Rate in the Case b $\leq3$
Apidopoulos Vassilis, Jean–François Aujol, Charles Dossal · SIAM Journal on Optimization · 2018
In this paper we are interested in the differential inclusion $0\in \ddot{x}(t)+\frac{b}{t}\dot{x}(t)+\partial F(x(t))$ in a finite-dimensional Hilbert space $\mathbb{R}^{d}$, where $F$ is a proper, convex, lower semicontinuous function. The motivation of this study is that the differential inclusion models the FISTA algorithm as considered in [A. Chambolle and C. Dossal, J. Optim. Theory Appl., 166 (2015), pp. 968--982]. In particular, we investigate the different asymptotic properties of solutions for this inclusion for $b>0$. We show that the convergence rate of $F(x(t))$ towards the minimum of $F$ is of order of $O\mathopen{}(t^{-\frac{2b}{3}})$ when $03$ this order is of $o\mathopen{}({t^{-2}})$ and the solution-trajectory converges to a minimizer of $F$. These results generalize the ones obtained in the differential setting (where $F$ is differentiable) in [H. Attouch, Z. Chbani, J. Peypouquet, and P. Redont, Math. Program., 2016, pp. 1--53], [H. Attouch, Z. Chbani, and H. Riahi, arXiv:1706.05671, 2017], [J. Aujol and C. Dossal, Optimal Rate of Convergence of an ODE Associated to the Fast Gradient Descent Schemes for $b> 0$, 2017], and [W. Su, S. Boyd, and E. J. Candes, J. Mach. Learn. Res., 17 (2016), pp. 1--43]. In addition, we show that the order of the convergence rate $O\mathopen{}(t^{-\frac{2b}{3}})$ of $F(x(t))$ towards the minimum is optimal, in the case of low friction $b<3$, by making a particular choice of $F$.