{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:25:55Z","timestamp":1740122755413,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,4,8]],"date-time":"2021-04-08T00:00:00Z","timestamp":1617840000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,4,8]],"date-time":"2021-04-08T00:00:00Z","timestamp":1617840000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1618717","CMMI-1663256"],"award-info":[{"award-number":["CCF-1618717","CMMI-1663256"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2021,6]]},"DOI":"10.1007\/s10589-021-00269-4","type":"journal-article","created":{"date-parts":[[2021,4,8]],"date-time":"2021-04-08T11:03:49Z","timestamp":1617879829000},"page":"369-404","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Fast and safe: accelerated gradient methods with optimality certificates and underestimate sequences"],"prefix":"10.1007","volume":"79","author":[{"given":"Majid","family":"Jahani","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Naga Venkata C.","family":"Gudapati","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chenxin","family":"Ma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8011-1442","authenticated-orcid":false,"given":"Rachael","family":"Tappenden","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Tak\u00e1\u010d","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,4,8]]},"reference":[{"key":"269_CR1","unstructured":"Allen-Zhu, Z., Qu, Z., Richtarik, P., Yuan, Y.: Even faster accelerated coordinate descent using non-uniform sampling. In: Balcan, M.F., Weinberger, K.Q. (eds.) Proceedings of The 33rd International Conference on Machine Learning, Volume\u00a048 of Proceedings of Machine Learning Research, pp. 1110\u20131119, New York, USA (2016). PMLR"},{"key":"269_CR2","unstructured":"Baes, M.: Estimate sequence methods: extensions and approximations. Technical Report Optimization-Online 2372, Universit\u00e9 Catholique de Louvain (2009)"},{"key":"269_CR3","unstructured":"Bubeck, S., Lee, Y.T., Singh, M.: A geometric alternative to Nesterov\u2019s accelerated gradient descent. Technical report, Microsoft Research (2015). arXiv:1506.08187 [math.OC]"},{"key":"269_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1961189.1961199","volume":"2","author":"C-C Chang","year":"2011","unstructured":"Chang, C.-C., Lin, C.-J.: LIBSVM: a library for support vector machines. ACM Trans. Intell. Syst. Technol. 2, 1\u201327 (2011)","journal-title":"ACM Trans. Intell. Syst. Technol."},{"key":"269_CR5","first-page":"636","volume-title":"Advances in Neural Information Processing Systems","author":"S Chen","year":"2017","unstructured":"Chen, S., Ma, S., Liu, W.: Geometric descent method for convex composite minimization. In: Guyon, I., Luxburg, U.V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., Garnett, R. (eds.) Advances in Neural Information Processing Systems, vol. 30, pp. 636\u2013644. Curran Associates Inc, Red Hook (2017)"},{"key":"269_CR6","first-page":"1647","volume-title":"Advances in Neural Information Processing Systems","author":"A Cotter","year":"2011","unstructured":"Cotter, A., Shamir, O., Srebro, N., Sridharan, K.: Better mini-batch algorithms via accelerated gradient methods. In: Shawe-Taylor, J., Zemel, R.S., Bartlett, P.L., Pereira, F., Weinberger, K.Q. (eds.) Advances in Neural Information Processing Systems, vol. 24, pp. 1647\u20131655. Curran Associates Inc., Red Hook (2011)"},{"issue":"1","key":"269_CR7","doi-asserted-by":"publisher","first-page":"660","DOI":"10.1137\/18M1172314","volume":"29","author":"J Diakonikolas","year":"2019","unstructured":"Diakonikolas, J.: The approximate duality gap technique: a unified theory of first-order methods. SIAM J. Optim. 29(1), 660\u2013689 (2019)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"269_CR8","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1137\/16M1072528","volume":"28","author":"D Drusvyatskiy","year":"2018","unstructured":"Drusvyatskiy, D., Fazel, M., Roy, S.: An optimal first order method based on optimal quadratic averaging. SIAM J. Optim. 28(1), 251\u2013271 (2018)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"269_CR9","doi-asserted-by":"publisher","first-page":"1997","DOI":"10.1137\/130949993","volume":"25","author":"O Fercoq","year":"2015","unstructured":"Fercoq, O., Richt\u00e1rik, P.: Accelerated, parallel, and proximal coordinate descent. SIAM J. Optim. 25(4), 1997\u20132023 (2015). https:\/\/doi.org\/10.1137\/130949993","journal-title":"SIAM J. Optim."},{"issue":"2","key":"269_CR10","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/s10589-018-9984-3","volume":"70","author":"K Fountoulakis","year":"2018","unstructured":"Fountoulakis, K., Tappenden, R.: A flexible coordinate descent method. Comput. Optim. Appl. 70(2), 351\u2013394 (2018)","journal-title":"Comput. Optim. Appl."},{"issue":"4","key":"269_CR11","doi-asserted-by":"publisher","first-page":"1469","DOI":"10.1137\/110848876","volume":"22","author":"S Ghadimi","year":"2012","unstructured":"Ghadimi, S.: Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization I: A generic algorithmic framework. SIAM J. Optim. 22(4), 1469\u20131492 (2012). https:\/\/doi.org\/10.1137\/110848876","journal-title":"SIAM J. Optim."},{"key":"269_CR12","first-page":"3068","volume-title":"Advances in Neural Information Processing Systems","author":"M Jaggi","year":"2014","unstructured":"Jaggi, M., Smith, V., Takac, M., Terhorst, J., Krishnan, S., Hofmann, T., Jordan, M.I.: Communication-efficient distributed dual coordinate ascent. In: Ghahramani, Z., Welling, M., Cortes, C., Lawrence, N.D., Weinberger, K.Q. (eds.) Advances in Neural Information Processing Systems, vol. 27, pp. 3068\u20133076. Curran Associates Inc, Red Hook (2014)"},{"key":"269_CR13","first-page":"315","volume-title":"Advances in Neural Information Processing Systems","author":"R Johnson","year":"2013","unstructured":"Johnson, R., Zhang, T.: Accelerating stochastic gradient descent using predictive variance reduction. In: Burges, C.J.C., Bottou, L., Welling, M., Ghahramani, Z., Weinberger, K.Q. (eds.) Advances in Neural Information Processing Systems, vol. 26, pp. 315\u2013323. Curran Associates Inc., Red Hook (2013)"},{"key":"269_CR14","unstructured":"Kingma, D., Ba, J.: Adam: A method for stochastic optimization. In: Proceedings of the 3rd International Conference on Learning Representations (ICLR), 7\u20139 May 2015, San Diego, USA (2014). arXiv:1412.6980"},{"key":"269_CR15","first-page":"3384","volume-title":"Advances in Neural Information Processing Systems","author":"H Lin","year":"2015","unstructured":"Lin, H., Mairal, J., Harchaoui, Z.: A universal catalyst for first-order optimization. In: Cortes, C., Lawrence, N.D., Lee, D.D., Sugiyama, M., Garnett, R. (eds.) Advances in Neural Information Processing Systems, vol. 28, pp. 3384\u20133392. Curran Associates Inc, Red Hook (2015)"},{"key":"269_CR16","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1007\/s10107-014-0800-2","volume":"152","author":"Z Lu","year":"2015","unstructured":"Lu, Z., Xiao, L.: On the complexity analysis of randomized block-coordinate descent methods. Math. Program. 152, 615\u2013642 (2015). https:\/\/doi.org\/10.1007\/s10107-014-0800-2","journal-title":"Math. Program."},{"key":"269_CR17","unstructured":"Ma, C., Jaggi, M., Curtis, F.E., Srebro, N., Tak\u00e1\u010d, M.: An accelerated communication-efficient primal-dual optimization framework for structured machine learning. Technical Report, Lehigh University, USA (2017). arXiv:1711.05305 [math.OC]"},{"key":"269_CR18","unstructured":"Ma, C., Smith, V., Jaggi, M., Jordan, M., Richtarik, P., Takac, M.: Adding vs. averaging in distributed primal-dual optimization. In: Bach, F., Blei, D. (eds.) Proceedings of the 32nd International Conference on Machine Learning, Volume\u00a037 of Proceedings of Machine Learning Research, pp. 1973\u20131982, Lille, France, 07\u201309 (2015). PMLR"},{"issue":"2","key":"269_CR19","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1137\/100802001","volume":"22","author":"Yu Nesterov","year":"2012","unstructured":"Nesterov, Yu.: Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM J. Optim. 22(2), 341\u2013362 (2012)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"269_CR20","first-page":"543","volume":"269","author":"Y Nesterov","year":"1983","unstructured":"Nesterov, Y.: A method for solving the convex programming problem with convergence rate $$o(1\/k^2)$$. Dokl. Akad. Nauk SSSR 269(3), 543\u2013547 (1983)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"269_CR21","doi-asserted-by":"publisher","unstructured":"Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course, volume 87 of Applied Optimization. Springer (Originally published by Kluwer Academic Publishers), Berlin (2004). https:\/\/doi.org\/10.1007\/978-1-4419-8853-9","DOI":"10.1007\/978-1-4419-8853-9"},{"issue":"1","key":"269_CR22","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/s10107-004-0552-5","volume":"103","author":"Y Nesterov","year":"2005","unstructured":"Nesterov, Y.: Smooth minimization of non-smooth functions. Math. Program. 103(1), 127\u2013152 (2005). https:\/\/doi.org\/10.1007\/s10107-004-0552-5","journal-title":"Math. Program."},{"key":"269_CR23","unstructured":"Nesterov, Y.: Gradient methods for minimizing composite objective function. CORE Discussion Paper 2007\/76, Universit\u00e9 Catholique de Louvain (2007)"},{"issue":"1","key":"269_CR24","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/s10107-006-0089-x","volume":"112","author":"Y Nesterov","year":"2008","unstructured":"Nesterov, Y.: Accelerating the cubic regularization of newton\u2019s method on convex problems. Math. Program. 112(1), 159\u2013181 (2008)","journal-title":"Math. Program."},{"issue":"1","key":"269_CR25","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s10107-012-0629-5","volume":"140","author":"Y Nesterov","year":"2013","unstructured":"Nesterov, Y.: Gradient methods for minimizing composite functions. Math. Program. 140(1), 125\u2013161 (2013). https:\/\/doi.org\/10.1007\/s10107-012-0629-5","journal-title":"Math. Program."},{"key":"269_CR26","first-page":"1574","volume-title":"Advances in Neural Information Processing Systems","author":"A Nitanda","year":"2014","unstructured":"Nitanda, A.: Stochastic proximal gradient descent with acceleration techniques. In: Ghahramani, Z., Welling, M., Cortes, C., Lawrence, N.D., Weinberger, K.Q. (eds.) Advances in Neural Information Processing Systems, vol. 27, pp. 1574\u20131582. Curran Associates Inc, Red Hook (2014)"},{"issue":"3","key":"269_CR27","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1007\/s10208-013-9150-3","volume":"15","author":"B O\u2019Donoghue","year":"2015","unstructured":"O\u2019Donoghue, B., Candes, E.: Adaptive restart for accelerated gradient schemes. Found. Comput. Math. 15(3), 715\u2013732 (2015)","journal-title":"Found. Comput. Math."},{"issue":"1\u20132","key":"269_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-012-0614-z","volume":"144","author":"P Richt\u00e1rik","year":"2014","unstructured":"Richt\u00e1rik, P., Tak\u00e0\u010d, M.: Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function. Math. Program. 144(1\u20132), 1\u201338 (2014)","journal-title":"Math. Program."},{"key":"269_CR29","doi-asserted-by":"crossref","unstructured":"Robbins, H., Monro, S.: A stochastic approximation method. Ann. Math. Stat. 400\u2013407 (1951)","DOI":"10.1214\/aoms\/1177729586"},{"issue":"1\u20132","key":"269_CR30","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/s10107-016-1030-6","volume":"162","author":"M Schmidt","year":"2017","unstructured":"Schmidt, M., Roux, N.L., Bach, F.: Minimizing finite sums with the stochastic average gradient. Math. Program. 162(1\u20132), 83\u2013112 (2017). https:\/\/doi.org\/10.1007\/s10107-016-1030-6","journal-title":"Math. Program."},{"key":"269_CR31","unstructured":"Shalev-Shwartz, Shai, Zhang, T.: Accelerated mini-batch stochastic dual coordinate ascent. In: Burges, C.J.C., Bottou, L., Welling, M., Ghahramani, Z., Weinberger, K.Q. (eds.) Advances in Neural Information Processing Systems, vol. 26, pp. 378\u2013385. Curran Associates Inc, Red Hook (2013)"},{"key":"269_CR32","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/s10957-016-0867-4","volume":"170","author":"R Tappenden","year":"2016","unstructured":"Tappenden, R., Richt\u00e1rik, P., Gondzio, J.: Inexact coordinate descent: complexity and preconditioning. J. Optim. Theory Appl. 170, 144\u2013176 (2016)","journal-title":"J. Optim. Theory Appl."},{"issue":"1","key":"269_CR33","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/s10957-016-0867-4","volume":"170","author":"R Tappenden","year":"2016","unstructured":"Tappenden, R., Richt\u00e1rik, P., Gondzio, J.: Inexact coordinate descent: complexity and preconditioning. J. Optim. Theory Appl. 170(1), 144\u2013176 (2016)","journal-title":"J. Optim. Theory Appl."}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-021-00269-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-021-00269-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-021-00269-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,6]],"date-time":"2021-05-06T16:16:55Z","timestamp":1620317815000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-021-00269-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,8]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["269"],"URL":"https:\/\/doi.org\/10.1007\/s10589-021-00269-4","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"type":"print","value":"0926-6003"},{"type":"electronic","value":"1573-2894"}],"subject":[],"published":{"date-parts":[[2021,4,8]]},"assertion":[{"value":"17 February 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 February 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 April 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}