{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:34:21Z","timestamp":1787340861209,"version":"build-2736575974"},"reference-count":26,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2016,1]]},"abstract":"<jats:p>We consider convex optimization problems with structures that are suitable for sequential treatment or online sampling. In particular, we focus on problems where the objective function is an expected value, and the constraint set is the intersection of a large number of simpler sets. We propose an algorithmic framework for stochastic first-order methods using random projection\/proximal updates and random constraint updates, which contain as special cases several known algorithms as well as many new algorithms. To analyze the convergence of these algorithms in a unified manner, we prove a general coupled convergence theorem. It states that the convergence is obtained from an interplay between two coupled processes: progress toward feasibility and progress toward optimality. Under suitable stepsize assumptions, we show that the optimality error decreases at a rate of $\\mathcal{O}(1\/\\sqrt{k})$ and the feasibility error decreases at a rate of $\\mathcal{O}(\\log k\/k)$. We also consider a number of typical sampling processes for generating stochastic first-order information and random constraints, which are common in data-intensive applications, online learning, and simulation optimization. By using the coupled convergence theorem as a modular architecture, we are able to analyze the convergence of stochastic algorithms that use arbitrary combinations of these sampling processes.<\/jats:p>","DOI":"10.1137\/130931278","type":"journal-article","created":{"date-parts":[[2016,3,10]],"date-time":"2016-03-10T10:48:29Z","timestamp":1457606909000},"page":"681-717","source":"Crossref","is-referenced-by-count":33,"title":["Stochastic First-Order Methods with Random Constraint Projection"],"prefix":"10.1137","volume":"26","author":[{"given":"Mengdi","family":"Wang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dimitri P.","family":"Bertsekas","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2016,3,10]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2182178"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/S1570-579X(01)80023-9"},{"key":"atypb3","unstructured":"H. H. Bauschke,\n                      Projection Algorithms and Monotone Operators\n                      , Ph.D. thesis, Simon Frazer University, Burnaby, BC, Canada, 1996."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144593251710"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/204\/02620"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0472-0"},{"key":"atypb7","unstructured":"D. P. Bertsekas, A. Nedic\u0301, and A. E. Ozdaglar,\n                      Convex Analysis and Optimization\n                      , Athena Scientific, Belmont, MA, 2003."},{"key":"atypb8","unstructured":"V. S. Borkar,\n                      Stochastic Approximation: A Dynamical Systems Viewpoint\n                      , Cambridge University Press, Cambridge, UK, 2008."},{"key":"atypb9","unstructured":"D. P. Bertsekas and J. N. Tsitsiklis,\n                      Parallel and Distributed Computation: Numerical Methods\n                      , Athena Scientific, Belmont, MA, 1989."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/070698750"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/j.jat.2006.02.005"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/j.jat.2006.02.006"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/j.jat.2008.04.001"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(67)90113-9"},{"key":"atypb15","first-page":"96","volume":"23","author":"Halperin I.","year":"1962","journal-title":"Acta Sci. Math."},{"key":"atypb16","unstructured":"H. J. Kushner and G. Yin,\n                      Stochastic Approximation and Recursive Algorithms and Applications\n                      . Springer, New York, 2003."},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0456"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1070.0291"},{"key":"atypb19","first-page":"263","author":"Nedic\u0301 A.","year":"2000","journal-title":"New York"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623499362111"},{"key":"atypb21","first-page":"7655","author":"Nedic\u0301 A.","year":"2010","journal-title":"GA"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0468-9"},{"key":"atypb24","unstructured":"O. Shamir and T. Zhang,\n                      Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes\n                      , in Proceedings of the 30th International Conference on Machine Learning, 2013, pp. 71-79."},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"P. Tseng,\n                      Successive Projection Under a Quasi-Cyclic Order\n                      , Report LIDS-P-1938, MIT, Cambridge, MA, 1990.","DOI":"10.21236\/ADA458804"},{"key":"atypb26","unstructured":"J. von Neumann,\n                      Functional Operators\n                      , Princeton University Press, Princeton, NJ, 1950."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0769-x"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/130931278","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:52:55Z","timestamp":1787338375000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/130931278"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["10.1137\/130931278"],"URL":"https:\/\/doi.org\/10.1137\/130931278","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1]]}}}