{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,6]],"date-time":"2026-04-06T09:16:47Z","timestamp":1775467007668,"version":"3.50.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2015,5,16]],"date-time":"2015-05-16T00:00:00Z","timestamp":1431734400000},"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":["Math. Program."],"published-print":{"date-parts":[[2016,7]]},"DOI":"10.1007\/s10107-015-0911-4","type":"journal-article","created":{"date-parts":[[2015,5,15]],"date-time":"2015-05-15T04:48:46Z","timestamp":1431665326000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["OSGA: a fast subgradient algorithm with optimal complexity"],"prefix":"10.1007","volume":"158","author":[{"given":"Arnold","family":"Neumaier","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,5,16]]},"reference":[{"key":"911_CR1","unstructured":"Ahookhosh, M.: Optimal subgradient algorithms with application to large-scale linear inverse problems, Submitted. http:\/\/arxiv.org\/abs\/1402.7291 (2014)"},{"key":"911_CR2","unstructured":"Ahookhosh, M., Neumaier, A.: High-dimensional convex optimization via optimal affine subgradient algorithms. In: ROKS workshop, 83\u201384 (2013)"},{"key":"911_CR3","unstructured":"Ahookhosh, M., Neumaier, A.: An optimal subgradient algorithm with subspace search for costly convex optimization problems. Submitted. http:\/\/www.optimization-online.org\/DB_FILE\/2015\/04\/4852 (2015)"},{"key":"911_CR4","unstructured":"Ahookhosh, M., Neumaier, A.: Solving nonsmooth convex optimization with complexity $$O(\\varepsilon ^{-1\/2})$$ O ( \u03b5 - 1 \/ 2 ) . Submitted. http:\/\/www.optimizationonline.org\/DB_HTML\/2015\/05\/4900.html (2015)"},{"key":"911_CR5","unstructured":"Ahookhosh, M., Neumaier, A.: An optimal subgradient algorithms for large-scale bound-constrained convex optimization. Submitted. http:\/\/arxiv.org\/abs\/1501.01497 (2015)"},{"key":"911_CR6","unstructured":"Ahookhosh, M., Neumaier, A.: An optimal subgradient algorithms for large-scale convex optimization in simple domains. Submitted. http:\/\/arxiv.org\/abs\/1501.01451 (2015)"},{"key":"911_CR7","doi-asserted-by":"crossref","first-page":"697","DOI":"10.1137\/S1052623403427823","volume":"16","author":"A Auslender","year":"2006","unstructured":"Auslender, A., Teboulle, M.: Interior gradient and proximal methods for convex and conic optimization. SIAM J. Optim. 16, 697\u2013725 (2006)","journal-title":"SIAM J. Optim."},{"key":"911_CR8","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1007\/BF01389448","volume":"48","author":"O Axelsson","year":"1986","unstructured":"Axelsson, O., Lindskog, G.: On the rate of convergence of the conjugate gradient method. Numer. Math. 48, 499\u2013523 (1986)","journal-title":"Numer. Math."},{"issue":"2","key":"911_CR9","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1137\/100786721","volume":"22","author":"NS Aybat","year":"2012","unstructured":"Aybat, N.S., Iyengar, G.: A first-order augmented Lagrangian method for compressed sensing. SIAM J. Optim. 22(2), 429\u2013459 (2012)","journal-title":"SIAM J. Optim."},{"key":"911_CR10","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1016\/j.orl.2010.08.005","volume":"38","author":"A Beck","year":"2010","unstructured":"Beck, A., Ben-Tal, A., Guttmann-Beck, N., Tetruashvili, L.: The CoMirror algorithm for solving nonsmooth constrained convex problems. Oper. Res. Lett. 38, 493\u2013498 (2010)","journal-title":"Oper. Res. Lett."},{"key":"911_CR11","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1137\/080716542","volume":"2","author":"A Beck","year":"2009","unstructured":"Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2, 183\u2013202 (2009)","journal-title":"SIAM J. Imaging Sci."},{"key":"911_CR12","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/s12532-011-0029-5","volume":"3","author":"SR Becker","year":"2011","unstructured":"Becker, S.R., Cand\u00e8s, E.J., Grant, M.C.: Templates for convex cone problems with applications to sparse signal recovery. Math. Program. Comput. 3, 165\u2013218 (2011)","journal-title":"Math. Program. Comput."},{"key":"911_CR13","doi-asserted-by":"crossref","first-page":"598","DOI":"10.1137\/110854400","volume":"24","author":"J Chen","year":"2014","unstructured":"Chen, J., Burer, S.: A first-order smoothing technique for a class of large-scale linear programs. SIAM J. Optim. 24, 598\u2013620 (2014)","journal-title":"SIAM J. Optim."},{"key":"911_CR14","doi-asserted-by":"crossref","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, 37\u201375 (2014)","journal-title":"Math. Program."},{"key":"911_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s12532-013-0063-6","volume":"6","author":"K Fountoulakis","year":"2014","unstructured":"Fountoulakis, K., Gondzio, J., Zhlobich, P.: Matrix-free interior point method for compressed sensing problems. Math. Program. Comput. 6, 1\u201331 (2014)","journal-title":"Math. Program. Comput."},{"key":"911_CR16","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/s10107-012-0541-z","volume":"138","author":"CC Gonzaga","year":"2013","unstructured":"Gonzaga, C.C., Karas, E.W.: Fine tuning Nesterov\u2019s steepest descent algorithm for differentiable convex programming. Math. Program. 138, 141\u2013166 (2013)","journal-title":"Math. Program."},{"key":"911_CR17","doi-asserted-by":"crossref","first-page":"1939","DOI":"10.1137\/110836602","volume":"23","author":"CC Gonzaga","year":"2013","unstructured":"Gonzaga, C.C., Karas, E.W., Rossetto, D.R.: An optimal algorithm for constrained differentiable convex optimization. SIAM J. Optim. 23, 1939\u20131955 (2013)","journal-title":"SIAM J. Optim."},{"key":"911_CR18","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/s11075-012-9668-5","volume":"64","author":"M Gu","year":"2013","unstructured":"Gu, M., Lim, L.-H., Wu, C.J.: PARNES: a rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals. Numer. Algorithm. 64, 321\u2013347 (2013)","journal-title":"Numer. Algorithm."},{"issue":"1","key":"911_CR19","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1214\/10-SSY010","volume":"4","author":"A Juditsky","year":"2014","unstructured":"Juditsky, A., Nesterov, Y.: Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization. Stoch. Syst. 4(1), 44\u201380 (2014)","journal-title":"Stoch. Syst."},{"key":"911_CR20","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-013-0737-x","author":"G Lan","year":"2013","unstructured":"Lan, G.: Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization. Mathematical Programming (2013). doi: 10.1007\/s10107-013-0737-x","journal-title":"Mathematical Programming"},{"key":"911_CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10107-008-0261-6","volume":"126","author":"G Lan","year":"2011","unstructured":"Lan, G., Lu, Z., Monteiro, R.D.C.: Primal-dual first-order methods with $$O(1\/\\varepsilon )$$ O ( 1 \/ \u03b5 ) iteration-complexity for cone programming. Math. Program. 126, 1\u201329 (2011)","journal-title":"Math. Program."},{"key":"911_CR22","unstructured":"Meng, X., Chen, H.: Accelerating Nesterov\u2019s method for strongly convex functions with Lipschitz gradient, Arxiv preprint arXiv:1109.6058 (2011)"},{"key":"911_CR23","volume-title":"Problem Complexity and Method Efficiency in Optimization","author":"AS Nemirovsky","year":"1983","unstructured":"Nemirovsky, A.S., Yudin, D.B.: Problem Complexity and Method Efficiency in Optimization. Wiley, New York (1983)"},{"key":"911_CR24","unstructured":"Nesterov, Y.: A method of solving a convex programming problem with convergence rate $$O(1, k^2)$$ O ( 1 , k 2 ) (in Russian), Doklady AN SSSR 269 (1983), 543\u2013547. Engl. translation: Soviet Math. Dokl. 27(1983), 372\u2013376"},{"key":"911_CR25","doi-asserted-by":"crossref","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, Dordrecht (2004)"},{"key":"911_CR26","doi-asserted-by":"crossref","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, 127\u2013152 (2005)","journal-title":"Math. Program."},{"key":"911_CR27","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1080\/10556780701550059","volume":"23","author":"Y Nesterov","year":"2008","unstructured":"Nesterov, Y.: Rounding of convex sets and efficient gradient methods for linear programming problems. Optim. Method. Softw. 23, 109\u2013128 (2008)","journal-title":"Optim. Method. Softw."},{"key":"911_CR28","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1287\/moor.1080.0348","volume":"34","author":"Y Nesterov","year":"2009","unstructured":"Nesterov, Y.: Unconstrained convex minimization in relative scale. Math. Oper. Res. 34, 180\u2013193 (2009)","journal-title":"Math. Oper. Res."},{"key":"911_CR29","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/s10107-007-0149-x","volume":"120","author":"Y Nesterov","year":"2009","unstructured":"Nesterov, Y.: Primal-dual subgradient methods for convex problems. Math. Program. 120, 221\u2013259 (2009)","journal-title":"Math. Program."},{"key":"911_CR30","doi-asserted-by":"crossref","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 objective function. Math. Program. 140, 125\u2013161 (2013)","journal-title":"Math. Program."},{"key":"911_CR31","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0790-0","author":"Y Nesterov","year":"2014","unstructured":"Nesterov, Y.: Universal gradient methods for convex optimization problems. Math. Programming (2014). doi: 10.1007\/s10107-014-0790-0","journal-title":"Math. Programming"},{"key":"911_CR32","doi-asserted-by":"crossref","first-page":"1141","DOI":"10.1137\/090747142","volume":"21","author":"P Richtarik","year":"2011","unstructured":"Richtarik, P.: Improved algorithms for convex minimization in relative scale. SIAM J. Optim. 21, 1141\u20131167 (2011)","journal-title":"SIAM J. Optim."},{"key":"911_CR33","unstructured":"Tseng, P.: On accelerated proximal gradient methods for convex-concave optimization, Technical report, Math. Dept., Univ. of Washington. http:\/\/pages.cs.wisc.edu\/~brecht\/cs726docs\/Tseng.APG (2008)"},{"key":"911_CR34","first-page":"1145","volume":"11","author":"J Yu","year":"2010","unstructured":"Yu, J., Vishvanathan, S.V.N., G\u00fcnter, S., Schraudolph, N.N.: A Quasi\u2013Newton approach to nonsmooth convex optimization problems in machine learning. J. Mach. Learn. Res. 11, 1145\u20131200 (2010)","journal-title":"J. Mach. Learn. Res."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-015-0911-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-015-0911-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-015-0911-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T10:00:07Z","timestamp":1559124007000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-015-0911-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,16]]},"references-count":34,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2016,7]]}},"alternative-id":["911"],"URL":"https:\/\/doi.org\/10.1007\/s10107-015-0911-4","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,5,16]]}}}