{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T21:02:53Z","timestamp":1768338173808,"version":"3.49.0"},"publisher-location":"Cham","reference-count":55,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030226282","type":"print"},{"value":"9783030226299","type":"electronic"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-22629-9_8","type":"book-chapter","created":{"date-parts":[[2019,6,12]],"date-time":"2019-06-12T00:02:42Z","timestamp":1560297762000},"page":"97-114","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":26,"title":["Gradient Methods for Problems with Inexact Model of the Objective"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9250-4438","authenticated-orcid":false,"given":"Fedor S.","family":"Stonyakin","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1757-1021","authenticated-orcid":false,"given":"Darina","family":"Dvinskikh","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1201-2343","authenticated-orcid":false,"given":"Pavel","family":"Dvurechensky","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3321-6409","authenticated-orcid":false,"given":"Alexey","family":"Kroshnin","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7124-9423","authenticated-orcid":false,"given":"Olesya","family":"Kuznetsova","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9314-8634","authenticated-orcid":false,"given":"Artem","family":"Agafonov","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7386-039X","authenticated-orcid":false,"given":"Alexander","family":"Gasnikov","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4963-8227","authenticated-orcid":false,"given":"Alexander","family":"Tyurin","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7080-9724","authenticated-orcid":false,"given":"C\u00e9sar A.","family":"Uribe","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1208-1659","authenticated-orcid":false,"given":"Dmitry","family":"Pasechnyuk","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4063-7407","authenticated-orcid":false,"given":"Sergei","family":"Artamonov","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,6,12]]},"reference":[{"key":"8_CR1","unstructured":"Altschuler, J., Bach, F., Rudi, A., Weed, J.: Approximating the quadratic transportation metric in near-linear time. arXiv:1810.10046 (2018)"},{"key":"8_CR2","unstructured":"Altschuler, J., Weed, J., Rigollet, P.: Near-linear time approxfimation algorithms for optimal transport via sinkhorn iteration. In: Guyon, I., et al. (eds.) Advances in Neural Information Processing Systems 30, pp. 1961\u20131971. Curran Associates, Inc. (2017)"},{"key":"8_CR3","unstructured":"Arjovsky, M., Chintala, S., Bottou, L.: Wasserstein GAN. arXiv:1701.07875 (2017)"},{"key":"8_CR4","unstructured":"Ben-Tal, A., Nemirovski, A.: Lectures on modern convex optimization (lecture notes). Personal web-page of A. Nemirovski (2015). http:\/\/www2.isye.gatech.edu\/~nemirovs\/Lect_ModConvOpt.pdf"},{"issue":"2","key":"8_CR5","doi-asserted-by":"publisher","first-page":"A1111","DOI":"10.1137\/141000439","volume":"37","author":"JD Benamou","year":"2015","unstructured":"Benamou, J.D., Carlier, G., Cuturi, M., Nenna, L., Peyr\u00e9, G.: Iterative bregman projections for regularized transportation problems. SIAM J. Sci. Comput. 37(2), A1111\u2013A1138 (2015)","journal-title":"SIAM J. Sci. Comput."},{"key":"8_CR6","unstructured":"Bigot, J., Klein, T., et al.: Consistent estimation of a population barycenter in the Wasserstein space. arXiv:1212.2562 (2012)"},{"key":"8_CR7","unstructured":"Blanchet, J., Jambulapati, A., Kent, C., Sidford, A.: Towards optimal running times for optimal transport. arXiv:1810.07717 (2018)"},{"key":"8_CR8","unstructured":"Bogolubsky, L., et al.: Learning supervised PageRank with gradient-based and gradient-free optimization methods. In: NIPS 2016 (2016). http:\/\/papers.nips.cc\/paper\/6565-learning-supervised-pagerank-with-gradient-based-and-gradient-free-optimization-methods.pdf"},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"Cartis, C., Gould, N.I.M., Toint, P.L.: Improved second-order evaluation complexity for unconstrained nonlinear optimization using high-order regularized models. arXiv:1708.04044 (2018)","DOI":"10.1080\/10556788.2019.1678033"},{"issue":"3","key":"8_CR10","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1137\/0803026","volume":"3","author":"G Chen","year":"1993","unstructured":"Chen, G., Teboulle, M.: Convergence analysis of a proximal-like minimization algorithm using bregman functions. SIAM J. Optim. 3(3), 538\u2013543 (1993)","journal-title":"SIAM J. Optim."},{"key":"8_CR11","unstructured":"Cohen, M.B., Diakonikolas, J., Orecchia, L.: On acceleration with noise-corrupted gradients. arXiv:1805.12591 (2018)"},{"key":"8_CR12","unstructured":"Cuturi, M.: Sinkhorn distances: lightspeed computation of optimal transport. In: Burges, C.J.C., Bottou, L., Welling, M., Ghahramani, Z., Weinberger, K.Q. (eds.) Advances in Neural Information Processing Systems 26, pp. 2292\u20132300. Curran Associates, Inc. (2013)"},{"key":"8_CR13","unstructured":"Cuturi, M., Doucet, A.: Fast computation of Wasserstein barycenters. In: Xing, E.P., Jebara, T. (eds.) Proceedings of the 31st International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 32, Bejing, China, 22\u201324 June 2014, pp. 685\u2013693. PMLR (2014). http:\/\/proceedings.mlr.press\/v32\/cuturi14.html"},{"issue":"3","key":"8_CR14","doi-asserted-by":"publisher","first-page":"1171","DOI":"10.1137\/060676386","volume":"19","author":"A d\u2019Aspremont","year":"2008","unstructured":"d\u2019Aspremont, A.: Smooth optimization with approximate gradient. SIAM J. Optim. 19(3), 1171\u20131183 (2008). https:\/\/doi.org\/10.1137\/060676386","journal-title":"SIAM J. Optim."},{"key":"8_CR15","unstructured":"Del Barrio, E., Lescornel, H., Loubes, J.M.: A statistical analysis of a deformation model with Wasserstein barycenters: estimation procedure and goodness of fit test. arXiv:1508.06465 (2015)"},{"issue":"1","key":"8_CR16","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/s10107-013-0677-5","volume":"146","author":"O Devolder","year":"2014","unstructured":"Devolder, O., Glineur, F., Nesterov, Y.: First-order methods of smooth convex optimization with inexact oracle. Math. Program. 146(1), 37\u201375 (2014). https:\/\/doi.org\/10.1007\/s10107-013-0677-5","journal-title":"Math. Program."},{"key":"8_CR17","unstructured":"Devolder, O., Glineur, F., Nesterov, Y., et al.: First-order methods with inexact oracle: the strongly convex case. CORE Discussion Papers 2013016 (2013)"},{"key":"8_CR18","unstructured":"Drusvyatskiy, D., Ioffe, A.D., Lewis, A.S.: Nonsmooth optimization using taylor-like models: error bounds, convergence, and termination criteria. arXiv:1610.03446 (2016)"},{"key":"8_CR19","unstructured":"Dvurechensky, P.: Gradient method with inexact oracle for composite non-convex optimization. arXiv:1703.09180 (2017)"},{"key":"8_CR20","unstructured":"Dvurechensky, P., Dvinskikh, D., Gasnikov, A., Uribe, C.A., Nedi\u0107, A.: Decentralize and randomize: faster algorithm for Wasserstein barycenters. In: Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., Garnett, R. (eds.) Advances in Neural Information Processing Systems 31, pp. 10783\u201310793. NeurIPS 2018, Curran Associates, Inc. (2018). arXiv:1802.04367"},{"issue":"1","key":"8_CR21","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/s10957-016-0999-6","volume":"171","author":"P Dvurechensky","year":"2016","unstructured":"Dvurechensky, P., Gasnikov, A.: Stochastic intermediate gradient method for convex problems with stochastic inexact oracle. J. Optim. Theory Appl. 171(1), 121\u2013145 (2016). https:\/\/doi.org\/10.1007\/s10957-016-0999-6","journal-title":"J. Optim. Theory Appl."},{"key":"8_CR22","unstructured":"Dvurechensky, P., Gasnikov, A., Gorbunov, E.: An accelerated directional derivative method for smooth stochastic convex optimization. arXiv:1804.02394 (2018)"},{"key":"8_CR23","unstructured":"Dvurechensky, P., Gasnikov, A., Gorbunov, E.: An accelerated method for derivative-free smooth stochastic convex optimization. arXiv:1802.09022 (2018)"},{"key":"8_CR24","doi-asserted-by":"crossref","unstructured":"Dvurechensky, P., Gasnikov, A., Kamzolov, D.: Universal intermediate gradient method for convex problems with inexact oracle. arXiv:1712.06036 (2017)","DOI":"10.1007\/s10957-016-0999-6"},{"key":"8_CR25","unstructured":"Dvurechensky, P., Gasnikov, A., Kroshnin, A.: Computational optimal transport: complexity by accelerated gradient descent is better than by Sinkhorn\u2019s algorithm. In: Dy, J., Krause, A. (eds.) Proceedings of the 35th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 80, pp. 1367\u20131376 (2018). arXiv:1802.04367"},{"key":"8_CR26","unstructured":"Dvurechensky, P., Gasnikov, A., Stonyakin, F., Titov, A.: Generalized Mirror Prox: Solving variational inequalities with monotone operator, inexact oracle, and unknown H\u00f6lder parameters (2018). https:\/\/arxiv.org\/abs\/1806.05140"},{"key":"8_CR27","unstructured":"Dvurechensky, P., Gasnikov, A., Tiurin, A.: Randomized similar triangles method: a unifying framework for accelerated randomized optimization methods (coordinate descent, directional search, derivative-free method) (2017). https:\/\/arxiv.org\/abs\/1707.08486"},{"key":"8_CR28","unstructured":"Ebert, J., Spokoiny, V., Suvorikova, A.: Construction of non-asymptotic confidence sets in 2-Wasserstein space (2017). https:\/\/arxiv.org\/abs\/1703.03658"},{"key":"8_CR29","unstructured":"Gasnikov, A.: Universal gradient descent (2017). https:\/\/arxiv.org\/abs\/1711.00394"},{"key":"8_CR30","unstructured":"Gasnikov, A., et al.: Universal method with inexact oracle and its applications for searching equillibriums in multistage transport problems (2015). https:\/\/arxiv.org\/abs\/1506.00292"},{"issue":"7\u20138","key":"8_CR31","first-page":"227","volume":"37","author":"L Kantorovich","year":"1942","unstructured":"Kantorovich, L.: On the translocation of masses. Doklady Acad. Sci. USSR (N.S.) 37(7\u20138), 227\u2013229 (1942)","journal-title":"Doklady Acad. Sci. USSR (N.S.)"},{"key":"8_CR32","unstructured":"Kroshnin, A., Dvinskikh, D., Dvurechensky, P., Gasnikov, A., Tupitsa, N., Uribe, C.: On the complexity of approximating Wasserstein barycenter (2019). https:\/\/arxiv.org\/abs\/1901.08686"},{"key":"8_CR33","unstructured":"Kroshnin, A., Spokoiny, V., Suvorikova, A.: Statistical inference for bures-Wasserstein barycenters (2019). https:\/\/arxiv.org\/abs\/1901.00226"},{"issue":"3\u20134","key":"8_CR34","doi-asserted-by":"crossref","first-page":"901","DOI":"10.1007\/s00440-016-0727-z","volume":"168","author":"T Gouic Le","year":"2017","unstructured":"Le Gouic, T., Loubes, J.M.: Existence and consistency of Wasserstein barycenters. Probab. Theory Relat. Fields 168(3\u20134), 901\u2013917 (2017)","journal-title":"Probab. Theory Relat. Fields"},{"key":"8_CR35","doi-asserted-by":"crossref","unstructured":"Lee, Y.T., Sidford, A.: Path finding methods for linear programming: solving linear programs in o (vrank) iterations and faster algorithms for maximum flow. In: 2014 IEEE 55th Annual Symposium on Foundations of Computer Science Foundations of Computer Science (FOCS), pp. 424\u2013433 (2014)","DOI":"10.1109\/FOCS.2014.52"},{"issue":"1","key":"8_CR36","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1137\/16M1099546","volume":"28","author":"H Lu","year":"2018","unstructured":"Lu, H., Freund, R.M., Nesterov, Y.: Relatively smooth convex optimization by first-order methods, and applications. SIAM J. Optim. 28(1), 333\u2013354 (2018)","journal-title":"SIAM J. Optim."},{"key":"8_CR37","unstructured":"Mairal, J.: Optimization with first-order surrogate functions. In: International Conference on Machine Learning, pp. 783\u2013791 (2013)"},{"key":"8_CR38","unstructured":"Monge, G.: M\u00e9moire sur la th\u00e9orie des d\u00e9blais et des remblais. Histoire de l\u2019Acad\u00e9mie Royale des Sciences de Paris (1781)"},{"key":"8_CR39","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8853-9","volume-title":"Introductory Lectures on Convex Optimization: A Basic Course","author":"Y Nesterov","year":"2004","unstructured":"Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers, Massachusetts (2004)"},{"key":"8_CR40","doi-asserted-by":"crossref","unstructured":"Nesterov, Y.: Implementable tensor methods in unconstrained convex optimization. CORE Discussion Papers 2018005, Universit\u00e9 catholique de Louvain, Center for Operations Research and Econometrics (CORE), March 2018. https:\/\/ideas.repec.org\/p\/cor\/louvco\/2018005.html","DOI":"10.1007\/s10107-019-01449-1"},{"key":"8_CR41","unstructured":"Nesterov, Y.: Soft clustering by convex electoral model. CORE Discussion Papers 2018001, Universit\u00e9 catholique de Louvain, Center for Operations Research and Econometrics (CORE), January 2018. https:\/\/ideas.repec.org\/p\/cor\/louvco\/2018001.html"},{"issue":"1","key":"8_CR42","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/s10107-006-0706-8","volume":"108","author":"Y Nesterov","year":"2006","unstructured":"Nesterov, Y., Polyak, B.: Cubic regularization of Newton method and its global performance. Math. Program. 108(1), 177\u2013205 (2006)","journal-title":"Math. Program."},{"issue":"1","key":"8_CR43","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/s10957-018-01452-0","volume":"181","author":"P Ochs","year":"2019","unstructured":"Ochs, P., Fadili, J., Brox, T.: Non-smooth non-convex bregman minimization: unification and new algorithms. J. Optim. Theory Appl. 181(1), 244\u2013278 (2019)","journal-title":"J. Optim. Theory Appl."},{"key":"8_CR44","doi-asserted-by":"crossref","unstructured":"Pele, O., Werman, M.: Fast and robust earth mover\u2019s distances. In: 2009 IEEE 12th International Conference on Computer Vision, pp. 460\u2013467 (2009)","DOI":"10.1109\/ICCV.2009.5459199"},{"issue":"5\u20136","key":"8_CR45","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1561\/2200000073","volume":"11","author":"G Peyr\u00e9","year":"2019","unstructured":"Peyr\u00e9, G., Cuturi, M.: Computational optimal transport. Found. Trends Mach. Learn. 11(5\u20136), 355\u2013607 (2019)","journal-title":"Found. Trends Mach. Learn."},{"key":"8_CR46","volume-title":"Introduction to Optimization","author":"B Polyak","year":"1987","unstructured":"Polyak, B.: Introduction to Optimization. Optimization Software, New York (1987)"},{"key":"8_CR47","unstructured":"Quanrud, K.: Approximating optimal transport with linear programs. In: 2nd Symposium on Simplicity in Algorithms (SOSA 2019), vol. 69, pp. 6:1\u20136:9. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2018)"},{"key":"8_CR48","unstructured":"Schmitzer, B.: Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems (2016). https:\/\/arxiv.org\/abs\/1610.06519"},{"issue":"2","key":"8_CR49","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1090\/S0002-9939-1974-0357434-8","volume":"45","author":"R Sinkhorn","year":"1974","unstructured":"Sinkhorn, R.: Diagonal equivalence to matrices with prescribed row and column sums. II. Proc. Amer. Math. Soc. 45(2), 195\u2013198 (1974)","journal-title":"Proc. Amer. Math. Soc."},{"key":"8_CR50","unstructured":"Solomon, J., Rustamov, R.M., Guibas, L., Butscher, A.: wasserstein propagation for semi-supervised learning. In: Proceedings of the 31st International Conference on International Conference on Machine Learning, vol. 32, pp. 306\u2013314. PMLR (2014)"},{"key":"8_CR51","doi-asserted-by":"crossref","unstructured":"Stonyakin, F., et al.: Gradient methods for problems with inexact model of the objective. arXiv:1902.09001 (2019)","DOI":"10.1007\/978-3-030-22629-9_8"},{"key":"8_CR52","unstructured":"Stonyakin, F., et al.: Inexact Model: A Framework for Optimization and Variational Inequalities (2019). https:\/\/arxiv.org\/abs\/1902.00990"},{"issue":"1","key":"8_CR53","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."},{"key":"8_CR54","doi-asserted-by":"crossref","unstructured":"Tyurin, A., Gasnikov, A.: Fast gradient descent method for convex optimization problems with an oracle that generates a $$(\\delta , {L}) $$ -model of a function in a requested point. Comput. Math. Math. Phys. (2019, accepted). https:\/\/arxiv.org\/abs\/1711.02747","DOI":"10.1134\/S0965542519070078"},{"key":"8_CR55","doi-asserted-by":"crossref","unstructured":"Uribe, C.A., Dvinskikh, D., Dvurechensky, P., Gasnikov, A., Nedi\u0107, A.: Distributed computation of Wasserstein barycenters over networks. In: 2018 IEEE Conference on Decision and Control (CDC), pp. 6544\u20136549 (2018)","DOI":"10.1109\/CDC.2018.8619160"}],"container-title":["Lecture Notes in Computer Science","Mathematical Optimization Theory and Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-22629-9_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,20]],"date-time":"2022-09-20T12:20:09Z","timestamp":1663676409000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-22629-9_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030226282","9783030226299"],"references-count":55,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-22629-9_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"12 June 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"MOTOR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Mathematical Optimization Theory and Operations Research","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ekaterinburg","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 July 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 July 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"motor2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/motor2019.uran.ru","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}