{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T18:37:24Z","timestamp":1775068644975,"version":"3.50.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2014,11,20]],"date-time":"2014-11-20T00:00:00Z","timestamp":1416441600000},"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,1]]},"DOI":"10.1007\/s10107-014-0839-0","type":"journal-article","created":{"date-parts":[[2014,11,21]],"date-time":"2014-11-21T15:19:19Z","timestamp":1416583159000},"page":"105-145","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":89,"title":["Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization"],"prefix":"10.1007","volume":"155","author":[{"given":"Shai","family":"Shalev-Shwartz","sequence":"first","affiliation":[]},{"given":"Tong","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,11,20]]},"reference":[{"key":"839_CR1","volume-title":"Estimate Sequence Methods: Extensions and Approximations","author":"M Baes","year":"2009","unstructured":"Baes, M.: Estimate Sequence Methods: Extensions and Approximations. Institute for Operations Research, ETH, Z\u00fcrich (2009)"},{"issue":"1","key":"839_CR2","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(1), 183\u2013202 (2009)","journal-title":"SIAM J. Imaging Sci."},{"key":"839_CR3","first-page":"1775","volume":"9","author":"M Collins","year":"2008","unstructured":"Collins, M., Globerson, A., Koo, T., Carreras, X., Bartlett, P.: Exponentiated gradient algorithms for conditional random fields and max-margin markov networks. J. Mach. Learn. Res. 9, 1775\u20131822 (2008)","journal-title":"J. Mach. Learn. Res."},{"key":"839_CR4","unstructured":"Cotter, A., Shamir, O., Srebro, N., Sridharan, K.: Better mini-batch algorithms via accelerated gradient methods. arXiv preprint arXiv:1106.4574 (2011)"},{"key":"839_CR5","first-page":"265","volume":"2","author":"K Crammer","year":"2001","unstructured":"Crammer, K., Singer, Y.: On the algorithmic implementation of multiclass kernel-based vector machines. J. Mach. Learn. Res. 2, 265\u2013292 (2001)","journal-title":"J. Mach. Learn. Res."},{"issue":"3","key":"839_CR6","doi-asserted-by":"crossref","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)","journal-title":"SIAM J. Optim."},{"key":"839_CR7","doi-asserted-by":"crossref","unstructured":"Devolder, O., Glineur, F., Nesterov, Y.: First-order methods of smooth convex optimization with inexact oracle. Math. Program. 146(1\u20132), 37\u201375 (2014)","DOI":"10.1007\/s10107-013-0677-5"},{"key":"839_CR8","first-page":"2899","volume":"10","author":"J Duchi","year":"2009","unstructured":"Duchi, J., Singer, Y.: Efficient online and batch learning using forward backward splitting. J. Mach. Learn. Res. 10, 2899\u20132934 (2009)","journal-title":"J. Mach. Learn. Res."},{"key":"839_CR9","doi-asserted-by":"crossref","unstructured":"Duchi, J., Shalev-Shwartz, S., Singer, Y., Chandra, T.: Efficient projections onto the l 1-ball for learning in high dimensions. In: Proceedings of the 25th International Conference on Machine Learning, pp. 272\u2013279. ACM (2008)","DOI":"10.1145\/1390156.1390191"},{"key":"839_CR10","unstructured":"Duchi, J., Shalev-Shwartz, S., Singer, Y., Tewari, A.: Composite objective mirror descent. In: Proceedings of the 23rd Annual Conference on Learning Theory, pp. 14\u201326 (2010)"},{"key":"839_CR11","unstructured":"Fercoq, O., Richt\u00e1rik, P.: Accelerated, parallel and proximal coordinate descent. Technical report. arXiv:1312.5799 (2013)"},{"issue":"4","key":"839_CR12","doi-asserted-by":"crossref","first-page":"1469","DOI":"10.1137\/110848864","volume":"22","author":"S Ghadimi","year":"2012","unstructured":"Ghadimi, S., Lan, G.: Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework. SIAM J. Optim. 22(4), 1469\u20131492 (2012)","journal-title":"SIAM J. Optim."},{"key":"839_CR13","unstructured":"Hu, C., Weike, P., Kwok, J.T.: Accelerated gradient methods for stochastic optimization and online learning. In: Advances in Neural Information Processing Systems, pp. 781\u2013789 (2009)"},{"key":"839_CR14","unstructured":"Lacoste-Julien, S., Jaggi, M., Schmidt, M., Pletscher, P.: Stochastic block-coordinate frank-wolfe optimization for structural svms. arXiv preprint arXiv:1207.4747 (2012)"},{"key":"839_CR15","unstructured":"Langford, J., Li, L., Zhang, T.: Sparse online learning via truncated gradient. In: NIPS, pp. 905\u2013912 (2009)"},{"key":"839_CR16","unstructured":"Roux, N.L., Schmidt, M., Bach, F.: A Stochastic Gradient Method with an Exponential Convergence Rate for Strongly-Convex Optimization with Finite Training Sets. arXiv preprint arXiv:1202.6258 (2012)"},{"issue":"2","key":"839_CR17","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1137\/100802001","volume":"22","author":"Y Nesterov","year":"2012","unstructured":"Nesterov, Y.: Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM J. Optim. 22(2), 341\u2013362 (2012)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"839_CR18","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(1), 127\u2013152 (2005)","journal-title":"Math. Program."},{"key":"839_CR19","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":"839_CR20","doi-asserted-by":"crossref","unstructured":"Richt\u00e1rik, P., Tak\u00e1\u010d, M.: Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function. Math. Program. 144(1\u20132), 1\u201338 (2014)","DOI":"10.1007\/s10107-012-0614-z"},{"key":"839_CR21","unstructured":"Schmidt, M., Roux, N.L., Bach, F.: Convergence rates of inexact proximal-gradient methods for convex optimization. Technical report. arXiv:1109.2415 (2011)"},{"key":"839_CR22","first-page":"1865","volume":"12","author":"S Shalev-Shwartz","year":"2011","unstructured":"Shalev-Shwartz, S., Tewari, A.: Stochastic methods for l 1-regularized loss minimization. J. Mach. Learn. Res. 12, 1865\u20131892 (2011)","journal-title":"J. Mach. Learn. Res."},{"key":"839_CR23","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781107298019","volume-title":"Understanding Machine Learning: From Theory to Algorithms","author":"S Shalev-Shwartz","year":"2014","unstructured":"Shalev-Shwartz, S., Ben-David, S.: Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, Cambridge (2014)"},{"key":"839_CR24","doi-asserted-by":"crossref","unstructured":"Shalev-Shwartz, S., Tewari, A.: Stochastic methods for l 1-regularized loss minimization. In: ICML, p. 117 (2009)","DOI":"10.1145\/1553374.1553493"},{"key":"839_CR25","unstructured":"Shalev-Shwartz, S., Zhang, T.: Proximal stochastic dual coordinate ascent. arXiv:1211.2717 (2012)"},{"key":"839_CR26","first-page":"567","volume":"14","author":"S Shalev-Shwartz","year":"2013","unstructured":"Shalev-Shwartz, S., Zhang, T.: Stochastic dual coordinate ascent methods for regularized loss minimization. J. Mach. Learn. Res. 14, 567\u2013599 (2013)","journal-title":"J. Mach. Learn. Res."},{"key":"839_CR27","doi-asserted-by":"crossref","unstructured":"Shalev-Shwartz, S., Singer, Y., Srebro, N.: Pegasos: primal estimated sub-GrAdient SOlver for SVM. In: ICML, pp. 807\u2013814 (2007)","DOI":"10.1145\/1273496.1273598"},{"issue":"6","key":"839_CR28","doi-asserted-by":"crossref","first-page":"2807","DOI":"10.1137\/090759574","volume":"20","author":"S Shalev-Shwartz","year":"2010","unstructured":"Shalev-Shwartz, S., Srebro, N., Zhang, T.: Trading accuracy for sparsity in optimization problems with sparsity constraints. SIAM J. Optim. 20(6), 2807\u20132832 (2010)","journal-title":"SIAM J. Optim."},{"key":"839_CR29","unstructured":"Tak\u00e1c, M., Bijral, A., Richt\u00e1rik, P., Srebro, N.: Mini-batch primal and dual methods for SVMs. In: ICML (2013)"},{"key":"839_CR30","first-page":"2543","volume":"11","author":"L Xiao","year":"2010","unstructured":"Xiao, L.: Dual averaging method for regularized stochastic learning and online optimization. J. Mach. Learn. Res. 11, 2543\u20132596 (2010)","journal-title":"J. Mach. Learn. Res."},{"key":"839_CR31","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1023\/A:1012498226479","volume":"46","author":"T Zhang","year":"2002","unstructured":"Zhang, T.: On the dual formulation of regularized linear systems. Mach. Learn. 46, 91\u2013129 (2002)","journal-title":"Mach. Learn."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-014-0839-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-014-0839-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-014-0839-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,17]],"date-time":"2019-08-17T17:53:12Z","timestamp":1566064392000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-014-0839-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11,20]]},"references-count":31,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["839"],"URL":"https:\/\/doi.org\/10.1007\/s10107-014-0839-0","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,11,20]]}}}