{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,25]],"date-time":"2026-09-25T10:42:28Z","timestamp":1790332948287,"version":"4.1.0"},"reference-count":56,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>We consider minimization of stochastic functionals that are compositions of a (potentially) nonsmooth convex function $h$ and smooth function $c$ and, more generally, stochastic weakly convex functionals. We develop a family of stochastic methods---including a stochastic prox-linear algorithm and a stochastic (generalized) subgradient procedure---and prove that, under mild technical conditions, each converges to first order stationary points of the stochastic objective. We provide experiments further investigating our methods on nonsmooth phase retrieval problems; the experiments indicate the practical effectiveness of the procedures.<\/jats:p>","DOI":"10.1137\/17m1135086","type":"journal-article","created":{"date-parts":[[2018,11,27]],"date-time":"2018-11-27T15:37:40Z","timestamp":1543333060000},"page":"3229-3259","source":"Crossref","is-referenced-by-count":69,"title":["Stochastic Methods for Composite and Weakly Convex Optimization Problems"],"prefix":"10.1137","volume":"28","author":[{"given":"John C.","family":"Duchi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Feng","family":"Ruan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,11,27]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"J.P. Aubin and A. Cellina,\n                      Differential Inclusions: Set-Valued Maps and Viability Theory\n                      , Springer-Verlag, Berlin, 1984.","DOI":"10.1007\/978-3-642-69512-4"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012904439301"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/BF00934819"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/060670080"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-09-05048-X"},{"key":"atypb6","unstructured":"V. Borkar,\n                      Stochastic Approximation\n                      , Cambridge University Press, Cambridge, UK, 2008."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584377"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"E. Cand\u00e8s, T. Strohmer, and V. Voroninski,\n                      PhaseLift: Exact and stable signal recovery from magnitude measurements via convex programming\n                      , Comm. Pure Appl. Math., 66 (8), 2013.","DOI":"10.1002\/cpa.21432"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2399924"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"Y. Chen and E. Cand\u00e8s,\n                      Solving random quadratic systems of equations is nearly as easy as solving linear systems\n                      , Comm. Pure Appl. Math., 2015, to appear.","DOI":"10.1002\/cpa.21638"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"A. R. Conn, N. I. M. Gould, and P. L. Toint,\n                      Trust Region Methods\n                      , MOS-SIAM Ser. Optim., Philadelphia, 2000.","DOI":"10.1137\/1.9780898719857"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"D. Davis and D. Drusvyatskiy,\n                      Stochastic subgradient method converges at the rate ${O}(k^{-1\/4})$ on weakly convex functions\n                      , preprint,arXiv:1802.02988[cs.LG], 2018.","DOI":"10.1007\/s10208-018-09409-5"},{"key":"atypb13","unstructured":"D. Davis and D. Drusvyatskiy,\n                      Stochastic model-based minimization of weakly convex functions\n                      , preprint,arXiv:1803.06523[cs.LG], 2018."},{"key":"atypb14","unstructured":"D. Davis and B. Grimmer,\n                      Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems\n                      , preprint,arXiv:1707.03505[cs.LG], 2017."},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"D. Davis, D. Drusvyatskiy, S. Kakade, and J. D. Lee,\n                      Stochastic subgradient method converges on tame functions\n                      , preprint,arXiv:1804.07795[cs.LG], 2018.","DOI":"10.1007\/s10208-018-09409-5"},{"key":"atypb16","unstructured":"A. Dembo, Probability Theory: STAT310\/MATH230, lecture notes, Stanford University, Stanford, CA, 2016,http:\/\/statweb.stanford.edu\/~adembo\/stat-310b\/lnotes.pdf."},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(85)90051-5"},{"key":"atypb18","unstructured":"D. Drusvyatskiy,\n                      The proximal point method revisited\n                      , preprint,arXiv:1712.06038[math.OC], 2018,http:\/\/www.arXiv.org\/abs\/1712.06038."},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2017.0889"},{"key":"atypb20","unstructured":"D. Drusvyatskiy and C. Paquette,\n                      Efficiency of minimizing compositions of convex functions and smooth maps\n                      , preprint,arXiv:1605.00125[math.OC], 2016."},{"key":"atypb21","unstructured":"D. Drusvyatskiy, A. Ioffe, and A. Lewis,\n                      Nonsmooth optimization using Taylor-like models: Error bounds, convergence, and termination criteria\n                      , preprint,arXiv:1610.03446[math.OS], 2016."},{"key":"atypb22","unstructured":"J. C. Duchi and F. Ruan,\n                      Stochastic methods for composite and weakly convex optimization problems\n                      , preprint,arXiv:1703.08570[math.OC], 2017."},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"J. C. Duchi and F. Ruan.\n                      Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval\n                      , Inf. Inference, 2018, to appear.","DOI":"10.1093\/imaiai\/iay015"},{"key":"atypb24","first-page":"2121","volume":"12","author":"Duchi J. C.","year":"2011","journal-title":"J. Mach. Learning Res."},{"key":"atypb25","first-page":"72","volume":"2","author":"Ermoliev Y. M.","year":"1969","journal-title":"Kibernetika"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1007\/BF02742069"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1023\/B:CASA.0000012091.84864.65"},{"key":"atypb28","first-page":"67","author":"Fletcher R.","year":"1982","journal-title":"Berlin"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588325"},{"key":"atypb30","unstructured":"A. M. Gupal,\n                      Stochastic Methods for Solving Nonsmooth Extremal Problems\n                      , Naukova Dumka, Kiev, 1979 (In Ukrainian)."},{"key":"atypb31","unstructured":"M. Hardt and T. Ma,\n                      Identity matters in deep learning\n                      , in Proceedings of the Fifth International Conference on Learning Representations, 2017."},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"T. Hastie, R. Tibshirani, and J. Friedman,\n                      The Elements of Statistical Learning\n                      , 2nd ed., Springer, New York, 2009.","DOI":"10.1007\/978-0-387-84858-7"},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"J. Hiriart-Urruty and C. Lemar\u00e9chal,\n                      Convex Analysis and Minimization Algorithms I & II\n                      , Springer, New York, 1993.","DOI":"10.1007\/978-3-662-02796-7"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-08-09101-6"},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"A. D. Ioffe,\n                      Variational Analysis of Regular Mappings\n                      , Springer, New York, 2017.","DOI":"10.1007\/978-3-319-64277-2"},{"key":"atypb36","doi-asserted-by":"crossref","unstructured":"M. Kunze,\n                      Non-Smooth Dynamical Systems\n                      , Lect. Notes Math. 1744, Springer, New York, 2000.","DOI":"10.1007\/BFb0103843"},{"key":"atypb37","unstructured":"H. J. Kushner and G. Yin,\n                      Stochastic Approximation and Recursive Algorithms and Applications\n                      , 2nd ed., Springer, New York, 2003."},{"key":"atypb38","unstructured":"A. S. Lewis and S. J. Wright,\n                      A proximal method for composite minimization\n                      , preprint,arXiv:0812.0423[math.OC], 2018."},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1977.1101561"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1137\/070704277"},{"key":"atypb41","doi-asserted-by":"crossref","unstructured":"Y. Nesterov,\n                      Introductory Lectures on Convex Optimization\n                      , Kluwer Academic Publishers, Dordrecht, the Netherlands, 2004.","DOI":"10.1007\/978-1-4419-8853-9"},{"key":"atypb42","unstructured":"J. Nocedal and S. J. Wright,\n                      Numerical Optimization\n                      , Springer, New York, 2006."},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-96-01544-9"},{"key":"atypb44","first-page":"233","author":"Robbins H.","year":"1971","journal-title":"New York"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(69)90104-8"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1137\/0314056"},{"key":"atypb47","doi-asserted-by":"crossref","unstructured":"R. T. Rockafellar and R. J. B. Wets,\n                      Variational Analysis\n                      , Springer, New York, 1998.","DOI":"10.1007\/978-3-642-02431-3"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1287\/moor.12.1.32"},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2014.2352673"},{"key":"atypb50","first-page":"2510","volume":"27","author":"Su W.","year":"2014","journal-title":"Advances in Neural Information Processing Systems"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1996.tb02080.x"},{"key":"atypb52","first-page":"18","author":"Udell M.","year":"2014","journal-title":"NJ"},{"key":"atypb53","first-page":"1714","volume":"29","author":"Wang M.","year":"2016","journal-title":"Advances in Neural Information Processing Systems"},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-1017-3"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-35-00138-7"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1614734113"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1135086","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:52:48Z","timestamp":1787338368000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1135086"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":56,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1135086"],"URL":"https:\/\/doi.org\/10.1137\/17m1135086","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}