Convergence rate of inertial proximal algorithms with general extrapolation and proximal coefficients. (English) Zbl 1446.37099
The authors study the convergence properties of the inertial proximal algorithm:
\[
\text{(IP)}_{\alpha_k,\beta_k}: \qquad \left \{
\begin{array}{lll}
y_k & = & x_k + \alpha_k(x_k-x_{k-1}), \\
x_{k+1} & = & \text{prox}_{\beta_k} \phi (y_k).
\end{array} \right .
\]
Here the sequences \(\alpha_k\) and \(\beta_k\) play the role of parameters.
Proximal methods can be derived by implicit discretization of gradient-type continuous evolution systems. The authors study the convergence properties when \(\phi\) is continuously differentiable, using the relationship between the proximal algorithm \(\text{(IP)}_{\alpha_k,\beta_k}\) and the continuous second-order evolution equation \[ \text{(IGS)}_{\alpha_k,\beta_k}: \qquad \ddot{x}(t) \gamma(t) + \dot{x}(t) + \beta(t) \nabla \phi(x(t)) = 0. \] Here \(\gamma (t)\) is a positive damping coefficient, and \(\beta(t)\) is a time scale coefficient.
Depending on the behavior of the sequences \(\alpha_k\), and \(\beta_k\), the convergence rates are given for the values of the sequences \(x_k\) generated by the algorithm \(\text{(IP)}_{\alpha_k,\beta_k}\). Furthermore the convergence rate of the velocities is analyzed. General conditions on the sequences \(\alpha_k\) and \(\beta_k\) which guarantee the weak convergence of the iterates are given.
The authors study also compare their results with the accelerated proximal algorithm in [O. Güler, SIAM J. Control Optimization 29, No. 2, 403–419 (1991; Zbl 0737.90047)] and provide a dynamical interpretation of this algorithm.
Proximal methods can be derived by implicit discretization of gradient-type continuous evolution systems. The authors study the convergence properties when \(\phi\) is continuously differentiable, using the relationship between the proximal algorithm \(\text{(IP)}_{\alpha_k,\beta_k}\) and the continuous second-order evolution equation \[ \text{(IGS)}_{\alpha_k,\beta_k}: \qquad \ddot{x}(t) \gamma(t) + \dot{x}(t) + \beta(t) \nabla \phi(x(t)) = 0. \] Here \(\gamma (t)\) is a positive damping coefficient, and \(\beta(t)\) is a time scale coefficient.
Depending on the behavior of the sequences \(\alpha_k\), and \(\beta_k\), the convergence rates are given for the values of the sequences \(x_k\) generated by the algorithm \(\text{(IP)}_{\alpha_k,\beta_k}\). Furthermore the convergence rate of the velocities is analyzed. General conditions on the sequences \(\alpha_k\) and \(\beta_k\) which guarantee the weak convergence of the iterates are given.
The authors study also compare their results with the accelerated proximal algorithm in [O. Güler, SIAM J. Control Optimization 29, No. 2, 403–419 (1991; Zbl 0737.90047)] and provide a dynamical interpretation of this algorithm.
Reviewer: Bülent Karasözen (Ankara)
MSC:
| 37N40 | Dynamical systems in optimization and economics |
| 46N10 | Applications of functional analysis in optimization, convex analysis, mathematical programming, economics |
| 65K05 | Numerical mathematical programming methods |
| 65K10 | Numerical optimization and variational techniques |
| 65P10 | Numerical methods for Hamiltonian systems including symplectic integrators |
| 90B50 | Management decision making, including multiple objectives |
| 90C25 | Convex programming |
Keywords:
inertial proximal algorithms; general extrapolation coefficient; Lyapunov analysis; Nesterov accelerated gradient method; nonsmooth convex optimization; time rescalingCitations:
Zbl 0737.90047References:
| [1] | Alvarez, F.; Attouch, H., An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping, Set-Valued Anal., 9, 3-11 (2001) · Zbl 0991.65056 · doi:10.1023/A:1011253113155 |
| [2] | Álvarez, F.; Attouch, H.; Bolte, J.; Redont, P., A second-order gradient-like dissipative dynamical system with Hessian-driven damping. Application to optimization and mechanics, J. Math. Pures Appl., 81, 747-779 (2002) · Zbl 1036.34072 · doi:10.1016/S0021-7824(01)01253-3 |
| [3] | Apidopoulos, V., Aujol, J.-F., Dossal, Ch.: Convergence rate of inertial forward-backward algorithm beyond Nesterov’s rule. Math. Program. 10.1007/s10107-018-1350-9. HAL-01551873 (2018) · Zbl 1439.90055 |
| [4] | Attouch, H.; Cabot, A., Asymptotic stabilization of inertial gradient dynamics with time-dependent viscosity, J. Differ. Equ., 263, 5412-5458 (2017) · Zbl 1405.37092 · doi:10.1016/j.jde.2017.06.024 |
| [5] | Attouch, H.; Cabot, A., Convergence rates of inertial forward-backward algorithms, SIAM J. Optim., 28, 849-874 (2018) · Zbl 1387.49047 · doi:10.1137/17M1114739 |
| [6] | Attouch, H.; Cabot, A.; Chbani, Z.; Riahi, H., Inertial forward-backward algorithms with perturbations: application to Tikhonov regularization, J. Optim. Theory Appl., 179, 1-36 (2018) · Zbl 1417.90114 · doi:10.1007/s10957-018-1369-3 |
| [7] | Attouch, H.; Chbani, Z.; Riahi, H., Fast proximal methods via time scaling of damped inertial dynamics. SIAM, J. Optim., 29, 2227-2256 (2019) · Zbl 07105235 |
| [8] | Attouch, H.; Chbani, Z.; Peypouquet, J.; Redont, P., Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity, Math. Program. Ser. B, 168, 123-175 (2018) · Zbl 1395.34068 · doi:10.1007/s10107-016-0992-8 |
| [9] | Attouch, H., Chbani, Z., Riahi, H.: Rate of convergence of the Nesterov accelerated gradient method in the subcritical case α ≤ 3. ESAIM-COCV, 25 (2019). 10.1051/cocv/2017083 · Zbl 1437.49045 |
| [10] | Attouch, H.; Peypouquet, J., The rate of convergence of Nesterov’s accelerated forward-backward method is actually faster than 1/k2. SIAM, J. Optim., 26, 1824-1834 (2016) · Zbl 1346.49048 |
| [11] | Aujol, J-F; Dossal, Ch, Stability of over-relaxations for the forward-backward algorithm, application to FISTA, SIAM J. Optim., 25, 2408-2433 (2015) · Zbl 1357.49123 · doi:10.1137/140994964 |
| [12] | Aujol, J.-F., Dossal, Ch.: Optimal rate of convergence of an ODE associated to the Fast Gradient Descent schemes for b > 0. https://hal.inria.fr/hal-01547251v2 (2017) |
| [13] | Bauschke, HH; Combettes, PL, Convex Analysis and Monotone Operator Theory in Hilbert Spaces. CMS Books in Mathematics (2011), Cham: Springer, Cham · Zbl 1218.47001 |
| [14] | Beck, A.; Teboulle, M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2, 183-202 (2009) · Zbl 1175.94009 · doi:10.1137/080716542 |
| [15] | Boţ, R. I., Csetnek, E.R., László, S. C.: A second-order dynamical approach with variable damping to nonconvex smooth minimization. Appl. Anal. (2018). 10.1080/00036811.2018.1495330 · Zbl 1428.90129 |
| [16] | Bonettini, S.; Porta, F.; Ruggiero, V., A variable metric forward-backward method with extrapolation. SIAM, J. Sci. Comput., 38, A2558-A2584 (2016) · Zbl 1348.65092 |
| [17] | Burger, M., Sawatzky, A., Steidl, G.: First order algorithms in variational image processing. In: Glowinski, R., Osher, S., Yin, W (eds.) Splitting Methods in Communication, Imaging, Science, and Engineering, pp 345-407. Springer, Cham (2016) · Zbl 1372.65053 |
| [18] | Calatroni, L.; Chambolle, A., Backtracking strategies for accelerated descent methods with smooth composite objectives, SIAM J. Optim., 29, 1772-1798 (2019) · Zbl 1427.90215 · doi:10.1137/17M1149390 |
| [19] | Chambolle, A.; Dossal, Ch, On the convergence of the iterates of the “Fast Iterative Shrinkage/Thresholding Algorithm”, J. Optim. Theory Appl., 166, 968-982 (2015) · Zbl 1371.65047 · doi:10.1007/s10957-015-0746-4 |
| [20] | Combettes, P.L., Glaudin, L.E.: Proximal activation of smooth functions in splitting algorithms for convex image recovery. SIAM J. Imaging Sci. (2019). To appear · Zbl 1443.90269 |
| [21] | Combettes, PL; Wajs, VR, Signal recovery by proximal forward-backward splitting., Multiscale Model Simul., 4, 1168-1200 (2005) · Zbl 1179.94031 · doi:10.1137/050626090 |
| [22] | Güler, O., On the convergence of the proximal point algorithm for convex optimization, SIAM J. Control Optim., 29, 403-419 (1991) · Zbl 0737.90047 · doi:10.1137/0329022 |
| [23] | Güler, O., New proximal point algorithms for convex minimization, SIAM J. Optim., 2, 649-664 (1992) · Zbl 0778.90052 · doi:10.1137/0802032 |
| [24] | Kim, D.; Fessler, JA, Optimized first-order methods for smooth convex minimization, Math. Program., 159, 81-107 (2016) · Zbl 1345.90113 · doi:10.1007/s10107-015-0949-3 |
| [25] | Liang, J., Fadili, J., Peyré, G.: Local linear convergence of forward-backward under partial smoothness. In: Ghahramani, Z., et al. (eds.) Advances in Neural Information Processing Systems 27, pp 1970-1978. Curran Associates Inc. (2014) |
| [26] | Lorenz, DA; Pock, Th, An inertial forward-backward algorithm for monotone inclusions, J. Math. Imaging Vis., 51, 311-325 (2015) · Zbl 1327.47063 · doi:10.1007/s10851-014-0523-2 |
| [27] | May, R., Asymptotic for a second-order evolution equation with convex potential and vanishing damping term, Turk. J. Math., 41, 681-685 (2017) · Zbl 1424.34186 · doi:10.3906/mat-1512-28 |
| [28] | Nesterov, Y., A method of solving a convex programming problem with convergence rate O(1/k2). Soviet, Math. Dokl., 27, 372-376 (1983) · Zbl 0535.90071 |
| [29] | Nesterov, Y., Introductory Lectures on Convex Optimization: A Basic Course. Applied Optimization, vol. 87 (2004), Boston: Kluwer Academic Publishers, Boston · Zbl 1086.90045 |
| [30] | Opial, Z., Weak convergence of the sequence of successive approximations for nonexpansive mappings, Bull. Am. Math. Soc., 73, 591-597 (1967) · Zbl 0179.19902 · doi:10.1090/S0002-9904-1967-11761-0 |
| [31] | Parikh, N., Boyd, S.: Proximal algorithms. Foundations and Trends in optimization, vol. 1, pp. 127-239 (2013) |
| [32] | Peypouquet, J., Convex Optimization in Normed Spaces: Theory, Methods and Examples (2015), Cham: Springer, Cham · Zbl 1322.90004 |
| [33] | Peypouquet, J.; Sorin, S., Evolution equations for maximal monotone operators: asymptotic analysis in continuous and discrete time, J. Convex Anal., 17, 1113-1163 (2010) · Zbl 1214.47080 |
| [34] | Polyak, BT, Some methods of speeding up the convergence of iteration methods, USSR Comput Math. Math. Phys., 4, 1-17 (1964) · Zbl 0147.35301 · doi:10.1016/0041-5553(64)90137-5 |
| [35] | Polyak, B.T.: Introduction to Optimization. New York: Optimization Software (1987) · Zbl 0708.90083 |
| [36] | Scheinberg, K.; Goldfarb, D.; Bai, X., Fast first-order methods for composite convex optimization with backtracking, Found. Comput. Math., 14, 389-417 (2014) · Zbl 1304.90161 · doi:10.1007/s10208-014-9189-9 |
| [37] | Shi, B., Du, S.S., Jordan, M.I., Su, W.J.: Understanding the acceleration phenomenon via high-resolution differential equations. arXiv:1810.08907 (2018) |
| [38] | Schmidt, M., Le Roux, N., Bach, F.: Convergence rates of inexact proximal-gradient methods for convex optimization. NIPS’11 - 25th Annual Conference on Neural Information Processing Systems, Dec 2011, Grenada, Spain. HAL-inria-00618152v3 (2011) |
| [39] | Su, W.J., Boyd, S., Candès, E.J.: A Differential Equation for Modeling Nesterov’s Accelerated Gradient Method: Theory and Insights. In: Ghahramani, Z., et al. (eds.) Advances Neural Information Processing Systems 27, pp 2510-2518. Curran Associates Inc. (2014) |
| [40] | Villa, S.; Salzo, S.; Baldassarre, L.; Verri, A., Accelerated and inexact forward-backward algorithms, SIAM J. Optim., 23, 1607-1633 (2013) · Zbl 1295.90049 · doi:10.1137/110844805 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
