×

The inexact cyclic block proximal gradient method and properties of inexact proximal maps. (English) Zbl 07846598

Summary: This paper expands the cyclic block proximal gradient method for block separable composite minimization by allowing for inexactly computed gradients and pre-conditioned proximal maps. The resultant algorithm, the inexact cyclic block proximal gradient (I-CBPG) method, shares the same convergence rate as its exactly computed analogue provided the allowable errors decrease sufficiently quickly or are pre-selected to be sufficiently small. We provide numerical experiments that showcase the practical computational advantage of I-CBPG for certain fixed tolerances of approximation error and for a dynamically decreasing error tolerance regime in particular. Our experimental results indicate that cyclic methods with dynamically decreasing error tolerance regimes can actually outpace their randomized siblings with fixed error tolerance regimes. We establish a tight relationship between inexact pre-conditioned proximal map evaluations and \(\delta\)-subgradients in our \((\delta, B)\)-Second Prox theorem. This theorem forms the foundation of our convergence analysis and enables us to show that inexact gradient computations can be subsumed within a single unifying framework.

MSC:

90C30 Nonlinear programming

References:

[1] Beck, A., First-Order Methods in Optimization, 2017, Philadelphia: SIAM, Philadelphia · Zbl 1384.65033 · doi:10.1137/1.9781611974997
[2] Beck, A.; Tetruashvili, L., On the convergence of block coordinate descent type methods, SIAM J. Optim., 23, 4, 2037-2060, 2013 · Zbl 1297.90113 · doi:10.1137/120887679
[3] Broughton, R.; Coope, I.; Renaud, P.; Tappenden, R., A box constrained gradient projection algorithm for compressed sensing, Signal Process., 91, 8, 1985-1992, 2011 · Zbl 1217.94036 · doi:10.1016/j.sigpro.2011.03.003
[4] d’Aspremont, A., Smooth optimization with approximate gradient, SIAM J. Optim., 19, 3, 1171-1183, 2008 · Zbl 1180.90378 · doi:10.1137/060676386
[5] Devolder, O., Glineur, F., Nesterov, Y.: Intermediate gradient methods for smooth convex problems with inexact oracle. Technical report CORE-2013017 Center for Operations Research (2013)
[6] Devolder, O.; Glineur, F.; Nesterov, Y., First-order methods of smooth convex optimization with inexact oracle, Math. Program., 146, 1, 37-75, 2014 · Zbl 1317.90196 · doi:10.1007/s10107-013-0677-5
[7] Donoho, D., Compressed sensing, IEEE Trans. Inf. Theory, 52, 4, 1289-1306, 2006 · Zbl 1288.94016 · doi:10.1109/TIT.2006.871582
[8] Dvurechensky, P.; Gasnikov, A., Stochastic intermediate gradient method for convex problems with stochastic inexact oracle, J. Optim. Theory Appl., 171, 1, 121-145, 2016 · Zbl 1351.90150 · doi:10.1007/s10957-016-0999-6
[9] Frongillo, R., Reid, M.: Convergence analysis of prediction markets via randomized subspace descent. In: Cortes, C., Lawrence, N., Lee, D., Sugiyama, M., Garnett, R. (eds.) Advances in Neural Information Processing Systems, vol. 28 (2015)
[10] Hiriart-Urruty, J.; Lemaréchal, C., Convex Analysis and Minimization Algorithms II: Advanced Theory and Bundle Methods, 2013, Berlin: Springer, Berlin
[11] Hua, X.; Yamashita, N., Block coordinate proximal gradient methods with variable Bregman functions for nonsmooth separable optimization, Math. Program., 160, 1, 1-32, 2016 · Zbl 1352.49032 · doi:10.1007/s10107-015-0969-z
[12] Leventhal, D.; Lewis, A., Randomized methods for linear constraints: convergence rates and conditioning, Math. Oper. Res., 35, 3, 641-654, 2010 · Zbl 1216.15006 · doi:10.1287/moor.1100.0456
[13] Lu, H.; Freund, R.; Nesterov, Y., Relatively smooth convex optimization by first-order methods, and applications, SIAM J. Optim., 28, 1, 333-354, 2018 · Zbl 1392.90090 · doi:10.1137/16M1099546
[14] Nesterov, Y., Efficiency of coordinate descent methods on huge-scale optimization problems, SIAM J. Optim., 22, 2, 341-362, 2012 · Zbl 1257.90073 · doi:10.1137/100802001
[15] Qin, Z.; Scheinberg, K.; Goldfarb, D., Efficient block-coordinate descent algorithms for the group lasso, Math. Program. Comput., 5, 2, 143-169, 2013 · Zbl 1275.90059 · doi:10.1007/s12532-013-0051-x
[16] Richtárik, P., Takáč, M.: Efficient serial and parallel coordinate descent methods for huge-scale truss topology design. In: Klatte, D., Lüthi, H., Schmedders, K. (eds.) Operations Research Proceedings, vol. 2011 (2012) · Zbl 1306.74043
[17] Richtárik, P.; Takáč, M., Parallel coordinate descent methods for big data optimization, Math. Program., 156, 1-2, 433-484, 2016 · Zbl 1342.90102 · doi:10.1007/s10107-015-0901-6
[18] Salzo, S.; Villa, S., Inexact and accelerated proximal point algorithms, J. Convex Anal., 19, 4, 1167-1192, 2012 · Zbl 1283.90030
[19] Schmidt, M., Roux, N., Bach, F.: Convergence rates of inexact proximal-gradient methods for convex optimization. In: Shawe-Taylor, J., Zemel, R., Bartlett, P., Pereira, F., Weinberger, K. (eds.) Advances in Neural Information Processing Systems, vol. 24 (2011)
[20] Shefi, R.; Teboulle, M., On the rate of convergence of the proximal alternating linearized minimization algorithm for convex problems, EURO J. Comput. Optim., 4, 1, 27-46, 2016 · Zbl 1338.90306 · doi:10.1007/s13675-015-0048-5
[21] Simon, N.; Tibshirani, R., Standardization and the group lasso penalty, Stat. Sin., 22, 2, 983-1002, 2012 · Zbl 1257.62080
[22] Tappenden, R.; Richtárik, P.; Gondzio, J., Inexact coordinate descent: complexity and preconditioning, J. Optim. Theory Appl., 170, 1, 144-176, 2016 · Zbl 1350.65062 · doi:10.1007/s10957-016-0867-4
[23] Villa, S.; Salzo, S.; Baldassarre, L.; Verri, A., Accelerated and inexact forward-backward algorithms, SIAM J. Optim., 23, 3, 1607-1633, 2013 · Zbl 1295.90049 · doi:10.1137/110844805
[24] Wright, S.; Nowak, R.; Figueiredo, M., Sparse reconstruction by separable approximation, IEEE Trans. Signal Process., 57, 7, 2479-2493, 2009 · Zbl 1391.94442 · doi:10.1109/TSP.2009.2016892
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.