A generic online acceleration scheme for optimization algorithms via relaxation and inertia

References

• F. Alvarez, Weak convergence of a relaxed and inertial hybrid projection-proximal point algorithm for maximal monotone operators in Hilbert space, SIAM J. Optimiz. 14(3) (2004), pp. 773–782. doi: 10.1137/S1052623403427859
   Web of Science ®Google Scholar
• F. Alvarez and H. Attouch, An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping, Set-Valued Anal. 9(1–2) (2001), pp. 3–11. doi: 10.1023/A:1011253113155
   Google Scholar
• H. Attouch and J. Peypouquet, The rate of convergence of Nesterov's accelerated forward–backward method is actually faster than 1/k2, SIAM J. Optimiz. 26(3) (2016), pp. 1824–1834. doi: 10.1137/15M1046095
   Web of Science ®Google Scholar
• H.H. Bauschke, J.Y. Bello Cruz, T.T.A. Nghia, H.M. Phan and X. Wang, Optimal rates of linear convergence of relaxed alternating projections and generalized Douglas–Rachford methods for two subspaces, Numer. Algorithms 73(1) (2016), pp. 33–76. doi: 10.1007/s11075-015-0085-4
   Web of Science ®Google Scholar
• H.H. Bauschke and P.L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, Springer, New York, 2011.
   Google Scholar
• A. Beck and M. Teboulle, A fast iterative shrinkage–thresholding algorithm for linear inverse problems, SIAM J. Imaging. Sci. 2(1) (2009), pp. 183–202. doi: 10.1137/080716542
   Web of Science ®Google Scholar
• P. Bianchi, W. Hachem and F. Iutzeler, A coordinate descent primal–dual algorithm and application to distributed asynchronous optimization, IEEE Trans. Autom. Control 61(10) (2016), pp. 2947–2957. doi: 10.1109/TAC.2015.2512043
   Web of Science ®Google Scholar
• R.I. Boţ and E.R. Csetnek, An inertial alternating direction method of multipliers, Minimax Theor. Appl. 1 (2016), pp. 29–49.
   Google Scholar
• R.I. Boţ, E.R. Csetnek and C. Hendrich, Inertial Douglas–Rachford splitting for monotone inclusion problems, Appl. Math. Comput. 256 (2015), pp. 472–487.
   Web of Science ®Google Scholar
• S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations Trends Mach. Learn. 3(1) (2011), pp. 1–122. doi: 10.1561/2200000016
   Google Scholar
• A. Chambolle and C. Dossal, On the convergence of the iterates of ‘fista’, J. Optimiz. Theory App. 166(3) (2015), pp. 968–982. doi: 10.1007/s10957-015-0746-4
   Web of Science ®Google Scholar
• L. Condat, A primal–dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms, J. Optimiz. Theory App. 158(2) (2013), pp. 460–479. doi: 10.1007/s10957-012-0245-9
   Web of Science ®Google Scholar
• J. Eckstein and D.P. Bertsekas, On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program. 55(1–3) (1992), pp. 293–318. doi: 10.1007/BF01581204
   Web of Science ®Google Scholar
• N. Flammarion and F. Bach, From averaging to acceleration, there is only a step-size, in Conference on Learning Theory, 2015, pp. 658–695.
   Google Scholar
• E. Ghadimi, A. Teixeira, I. Shames and M. Johansson, Optimal parameter selection for the alternating direction method of multipliers (ADMM): Quadratic problems, IEEE Trans. Autom. Control 60(3) (2015), pp. 644–658. doi: 10.1109/TAC.2014.2354892
   Web of Science ®Google Scholar
• P. Giselsson, M. Fält and S. Boyd, Line search for averaged operator iteration, in 2016 IEEE 55th Conference on Decision and Control (CDC), IEEE, 2016, pp. 1015–1022.
   Google Scholar
• T. Goldstein, B. O'Donoghue, S. Setzer and R. Baraniuk, Fast alternating direction optimization methods, SIAM J. Imaging Sci. 7(3) (2014), pp. 1588–1623. doi: 10.1137/120896219
   Web of Science ®Google Scholar
• R.A. Horn and C.R. Johnson, Matrix Analysis, Cambridge University Press, New York, NY, 2007.
   Google Scholar
• F. Iutzeler, P. Bianchi, P. Ciblat and W. Hachem, Explicit convergence rate of a distributed alternating direction method of multipliers, IEEE Trans. Autom. Control. 61(4) (2013), pp. 892–904. doi: 10.1109/TAC.2015.2448011
   Web of Science ®Google Scholar
• F. Iutzeler, P. Bianchi, Ph. Ciblat and W. Hachem, Asynchronous distributed optimization using a randomized alternating direction method of multipliers, in Proc. IEEE Conf. Decision and Control (CDC), Florence, Italy, December 2013.
   Google Scholar
• F. Iutzeler, P. Ciblat and W. Hachem, Analysis of sum-weight-like algorithms for averaging in wireless sensor networks, IEEE Trans. Sig. Process. 61(11) (2013), pp. 2802–2814. doi: 10.1109/TSP.2013.2256904
   Web of Science ®Google Scholar
• P. Johnstone and P. Moulin, A Lyapunov analysis of fista with local linear convergence for sparse optimization, preprint (2015). Available at arXiv preprint arXiv:1502.02281.
   Google Scholar
• H. Lin, J. Mairal and Z. Harchaoui, A universal catalyst for first-order optimization, in Advances in Neural Information Processing Systems, 2015, pp. 3384–3392.
   Google Scholar
• Q. Lin and L. Xiao, An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization, Comput. Optim. Appl. 60(3) (2014), pp. 633–674. doi: 10.1007/s10589-014-9694-4
   Web of Science ®Google Scholar
• P.-L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal. 16(6) (1979), pp. 964–979. doi: 10.1137/0716071
   Web of Science ®Google Scholar
• D. Lorenz and T. Pock, An inertial forward–backward algorithm for monotone inclusions, J. Math. Imaging Vis. 51(2) (2014), pp. 311–325. doi: 10.1007/s10851-014-0523-2
   Web of Science ®Google Scholar
• P.-E. Maingé, Convergence theorems for inertial km-type algorithms, J. Comput. Appl. Math. 219(1) (2008), pp. 223–236. doi: 10.1016/j.cam.2007.07.021
   Web of Science ®Google Scholar
• Z. Mu and Y. Peng, A note on the inertial proximal point method, Stat. Optim. Inf. Comput. 3(3) (2015), pp. 241–248. doi: 10.19139/124
   Google Scholar
• Yu. Nesterov, A method of solving a convex programming problem with convergence rate o (1/k2), Soviet Math. Dokl. 27(2) (1983), pp. 372–376.
   Google Scholar
• Yu. Nesterov, Smooth minimization of non-smooth functions, Math. Program. 103(1) (2005), pp. 127–152. doi: 10.1007/s10107-004-0552-5
   Web of Science ®Google Scholar
• B. O'Donoghue and E. Candes, Adaptive restart for accelerated gradient schemes, Found. Comput. Math. 15(3) (2013), pp. 715–732. doi: 10.1007/s10208-013-9150-3
   Web of Science ®Google Scholar
• B.T. Polyak, Some methods of speeding up the convergence of iteration methods, USSR Comput. Math. Math. Phys. 4(5) (1964), pp. 1–17. doi: 10.1016/0041-5553(64)90137-5
   Google Scholar
• L.F. Richardson, The approximate arithmetical solution by finite differences of physical problems involving differential equations, with an application to the stresses in a masonry dam, Philos. Trans. R. Soc. Lond. 201 (1911), pp. 307–357. doi: 10.1098/rsta.1911.0009
   Google Scholar
• Y. Saad, Iterative Methods for Sparse Linear Systems, Siam, 2003.
   Google Scholar
• W. Shi, Q. Ling, K. Yuan, G. Wu and W. Yin, On the linear convergence of the ADMM in decentralized consensus optimization, IEEE Trans. Signal Process. 62(7) (2014), pp. 1750–1761. doi: 10.1109/TSP.2014.2304432
   Web of Science ®Google Scholar
• E. Shiu, Cyclically monotone linear operators, Proc. Am. Math. Soc. 59(1) (1976), pp. 127–132. doi: 10.1090/S0002-9939-1976-0410417-3
   Web of Science ®Google Scholar
• S. Tao, D. Boley and S. Zhang, Local linear convergence of ista and fista on the Lasso problem, SIAM J. Optimiz. 26(1) (2016), pp. 313–336. doi: 10.1137/151004549
   Web of Science ®Google Scholar
• A. Taylor, J. Hendrickx and F. Glineur, Smooth strongly convex interpolation and exact worst-case performance of first-order methods, Math. Program. 161(1–2) (2017), pp. 307–345. doi: 10.1007/s10107-016-1009-3
   Web of Science ®Google Scholar
• P. Tseng, On accelerated proximal gradient methods for convex–concave optimization, submitted, 2008.
   Google Scholar
• E. Wei and A. Ozdaglar, On the O(1/k) convergence of asynchronous distributed alternating direction method of multipliers, In IEEE Global conference on signal and information processing (GlobalSIP), 2013, pp. 551–554.
   Google Scholar