{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,26]],"date-time":"2026-06-26T02:05:19Z","timestamp":1782439519773,"version":"3.54.5"},"reference-count":52,"publisher":"American Mathematical Society (AMS)","issue":"348","license":[{"start":{"date-parts":[[2025,3,8]],"date-time":"2025-03-08T00:00:00Z","timestamp":1741392000000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>The blocky optimization has gained a significant amount of attention in far-reaching practical applications. Following the recent work (M. Nikolova and P. Tan [SIAM J. Optim. 29 (2019), pp.\u00a02053\u20132078]) on solving a class of nonconvex nonsmooth optimization, we develop a stochastic alternating structure-adapted proximal (s-ASAP) gradient descent method for solving blocky optimization problems. By deploying some state-of-the-art variance reduced gradient estimators (rather than full gradient) in stochastic optimization, the s-ASAP method is applicable to nonconvex optimization whose objective is the sum of a nonsmooth data-fitting term and a finite number of differentiable functions. The sublinear convergence rate of s-ASAP is built upon the proximal point algorithmic framework, whilst the linear convergence rate of s-ASAP is achieved under the error bound condition. Furthermore, the convergence of the sequence produced by s-ASAP is established under the Kurdyka-\u0141ojasiewicz property. Preliminary numerical simulations on some image processing applications demonstrate the compelling performance of the proposed method.<\/p>","DOI":"10.1090\/mcom\/3867","type":"journal-article","created":{"date-parts":[[2024,3,8]],"date-time":"2024-03-08T12:11:47Z","timestamp":1709899907000},"page":"1677-1714","source":"Crossref","is-referenced-by-count":4,"title":["Stochastic alternating structure-adapted proximal gradient descent method with variance reduction for nonconvex nonsmooth optimization"],"prefix":"10.1090","volume":"93","author":[{"given":"Zehui","family":"Jia","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wenxing","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xingju","family":"Cai","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Deren","family":"Han","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"14","published-online":{"date-parts":[[2024,3,8]]},"reference":[{"issue":"2","key":"1","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1137\/040605266","article-title":"Convergence of the iterates of descent methods for analytic cost functions","volume":"16","author":"Absil, P.-A.","year":"2005","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"issue":"1-2","key":"2","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/s10107-007-0133-5","article-title":"On the convergence of the proximal algorithm for nonsmooth functions involving analytic features","volume":"116","author":"Attouch, Hedy","year":"2009","journal-title":"Math. Program.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5610","issn-type":"print"},{"issue":"2","key":"3","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1287\/moor.1100.0449","article-title":"Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-\u0141ojasiewicz inequality","volume":"35","author":"Attouch, H\u00e9dy","year":"2010","journal-title":"Math. Oper. Res.","ISSN":"https:\/\/id.crossref.org\/issn\/0364-765X","issn-type":"print"},{"key":"4","doi-asserted-by":"crossref","unstructured":"J. F. Aujol, G. Gilboa, T. Chan, and S. Osher, Structure-texture image decomposition\u2014modeling, algorithms, and parameter selection, Int. J. Comput. Vis. 67 (2006), 111\u2013136.","DOI":"10.1007\/s11263-006-4331-z"},{"issue":"3","key":"5","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/BF00940050","article-title":"Asymptotic properties of the Fenchel dual functional and applications to decomposition problems","volume":"73","author":"Auslender, A.","year":"1992","journal-title":"J. Optim. Theory Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0022-3239","issn-type":"print"},{"key":"6","isbn-type":"print","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/978-3-642-45780-7_3","article-title":"Coupling the logarithmic-quadratic proximal method and the block nonlinear Gauss-Seidel algorithm for linearly constrained convex minimization","author":"Auslender, Alfred","year":"1999","ISBN":"https:\/\/id.crossref.org\/isbn\/3540663231"},{"issue":"1","key":"7","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1137\/070709013","article-title":"A fast method for finding the global solution of the regularized structured total least squares problem for image deblurring","volume":"30","author":"Beck, Amir","year":"2008","journal-title":"SIAM J. Matrix Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0895-4798","issn-type":"print"},{"issue":"3","key":"8","doi-asserted-by":"publisher","first-page":"1129","DOI":"10.1137\/15M1017557","article-title":"An alternating semiproximal method for nonconvex regularized structured total least squares problems","volume":"37","author":"Beck, Amir","year":"2016","journal-title":"SIAM J. Matrix Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0895-4798","issn-type":"print"},{"key":"9","series-title":"Athena Scientific Optimization and Computation Series","isbn-type":"print","volume-title":"Nonlinear programming","author":"Bertsekas, Dimitri P.","year":"1999","ISBN":"https:\/\/id.crossref.org\/isbn\/1886529000","edition":"2"},{"issue":"67","key":"10","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/BF02699126","article-title":"Semianalytic and subanalytic sets","author":"Bierstone, Edward","year":"1988","journal-title":"Inst. Hautes \\'{E}tudes Sci. Publ. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0073-8301","issn-type":"print"},{"issue":"4","key":"11","doi-asserted-by":"publisher","first-page":"1205","DOI":"10.1137\/050644641","article-title":"The \u0141ojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems","volume":"17","author":"Bolte, J\u00e9r\u00f4me","year":"2006","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"issue":"1-2","key":"12","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/s10107-013-0701-9","article-title":"Proximal alternating linearized minimization for nonconvex and nonsmooth problems","volume":"146","author":"Bolte, J\u00e9r\u00f4me","year":"2014","journal-title":"Math. Program.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5610","issn-type":"print"},{"key":"13","doi-asserted-by":"crossref","unstructured":"S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn. 3 (2011), no. 1, 1\u2013122.","DOI":"10.1561\/2200000016"},{"issue":"1","key":"14","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1214\/10-AOAS388","article-title":"Coordinate descent algorithms for nonconvex penalized regression, with applications to biological feature selection","volume":"5","author":"Breheny, Patrick","year":"2011","journal-title":"Ann. Appl. Stat.","ISSN":"https:\/\/id.crossref.org\/issn\/1932-6157","issn-type":"print"},{"key":"15","doi-asserted-by":"crossref","unstructured":"R. Cabral, F. De la Torre, J. Paulo Costeira, and A. Bernardino, Matrix completion for weakly-supervised multi-label image classification, IEEE Trans. Pattern Anal. Mach. Intell. 37 (2014), no. 1, 121\u2013135.","DOI":"10.1109\/TPAMI.2014.2343234"},{"issue":"1","key":"16","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/s10851-010-0251-1","article-title":"A first-order primal-dual algorithm for convex problems with applications to imaging","volume":"40","author":"Chambolle, Antonin","year":"2011","journal-title":"J. Math. Imaging Vision","ISSN":"https:\/\/id.crossref.org\/issn\/0924-9907","issn-type":"print"},{"issue":"6","key":"17","doi-asserted-by":"publisher","first-page":"4654","DOI":"10.1137\/080732213","article-title":"An efficient iterative approach for large-scale separable nonlinear inverse problems","volume":"31","author":"Chung, Julianne","year":"2009","journal-title":"SIAM J. Sci. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/1064-8275","issn-type":"print"},{"key":"18","unstructured":"D. Davis, The asynchronous PALM algorithm for nonsmooth nonconvex problems,  arXiv:1604.00526, 2016."},{"key":"19","unstructured":"A. Defazio, F. Bach, and S. Lacoste-Julien, SAGA: a fast incremental gradient method with support for non-strongly convex composite objectives, NIPS, 2014, pp. 1646\u20131654."},{"key":"20","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1002\/nav.3800060105","article-title":"A convex programming procedure","volume":"6","author":"D\u2019Esopo, D. A.","year":"1959","journal-title":"Naval Res. Logist. Quart.","ISSN":"https:\/\/id.crossref.org\/issn\/0028-1441","issn-type":"print"},{"issue":"4","key":"21","doi-asserted-by":"publisher","first-page":"1932","DOI":"10.1137\/20M1387213","article-title":"A stochastic proximal alternating minimization for nonsmooth and nonconvex optimization","volume":"14","author":"Driggs, Derek","year":"2021","journal-title":"SIAM J. Imaging Sci."},{"key":"22","series-title":"Springer Series in Operations Research","isbn-type":"print","volume-title":"Finite-dimensional variational inequalities and complementarity problems. Vol. I","author":"Facchinei, Francisco","year":"2003","ISBN":"https:\/\/id.crossref.org\/isbn\/0387955801"},{"issue":"10","key":"23","doi-asserted-by":"publisher","first-page":"4420","DOI":"10.1109\/TIP.2012.2206037","article-title":"Variational algorithms to remove stationary noise: applications to microscopy imaging","volume":"21","author":"Fehrenbach, J\u00e9r\u00f4me","year":"2012","journal-title":"IEEE Trans. Image Process.","ISSN":"https:\/\/id.crossref.org\/issn\/1057-7149","issn-type":"print"},{"key":"24","isbn-type":"print","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/978-94-017-9054-3_4","article-title":"On alternating direction methods of multipliers: a historical perspective","author":"Glowinski, Roland","year":"2014","ISBN":"https:\/\/id.crossref.org\/isbn\/9789401790536"},{"key":"25","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1051\/m2an\/197509R200411","article-title":"Sur l\u2019approximation, par \u00e9l\u00e9ments finis d\u2019ordre un, et la r\u00e9solution, par p\u00e9nalisation-dualit\u00e9, d\u2019une classe de probl\u00e8mes de Dirichlet non lin\u00e9aires","volume":"9","author":"Glowinski, R.","year":"1975","journal-title":"Rev. Fran\\c{c}aise Automat. Informat. Recherche Op\\'{e}rationnelle S\\'{e}r. Rouge Anal. Num\\'{e}r.","ISSN":"https:\/\/id.crossref.org\/issn\/0397-9342","issn-type":"print"},{"key":"26","doi-asserted-by":"crossref","unstructured":"M. Guillaumin, J. Verbeek, and C. Schmid, Multimodal semi-supervised learning for image classification, IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2010, pp. 902\u2013909.","DOI":"10.1109\/CVPR.2010.5540120"},{"key":"27","series-title":"Fundamentals of Algorithms","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718874","volume-title":"Deblurring images","volume":"3","author":"Hansen, Per Christian","year":"2006","ISBN":"https:\/\/id.crossref.org\/isbn\/9780898716184"},{"key":"28","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1002\/nav.3800040113","article-title":"A quadratic programming procedure","volume":"4","author":"Hildreth, Clifford","year":"1957","journal-title":"Naval Res. Logist. Quart.","ISSN":"https:\/\/id.crossref.org\/issn\/0028-1441","issn-type":"print"},{"key":"29","series-title":"Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]","isbn-type":"print","volume-title":"Convex analysis and minimization algorithms. I","volume":"305","author":"Hiriart-Urruty, Jean-Baptiste","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/3540568506"},{"key":"30","unstructured":"R. Johnson and T. Zhang, Accelerating stochastic gradient descent using predictive variance reduction, NIPS, vol. 26, 2013, pp. 315\u2013323."},{"key":"31","doi-asserted-by":"crossref","unstructured":"R. Kimmel, M. Elad, D. Shaked, R. Keshet, and I. Sobel, A variational framework for retinex, Int. J. Comput. Vis. 52 (2003), no. 1, 7\u201323.","DOI":"10.1023\/A:1022314423998"},{"issue":"3","key":"32","doi-asserted-by":"publisher","first-page":"769","DOI":"10.5802\/aif.1638","article-title":"On gradients of functions definable in o-minimal structures","volume":"48","author":"Kurdyka, Krzysztof","year":"1998","journal-title":"Ann. Inst. Fourier (Grenoble)","ISSN":"https:\/\/id.crossref.org\/issn\/0373-0956","issn-type":"print"},{"key":"33","doi-asserted-by":"publisher","first-page":"3400","DOI":"10.1109\/TSP.2020.2991801","article-title":"Blind audio source separation with minimum-volume beta-divergence NMF","volume":"68","author":"Leplat, Valentin","year":"2020","journal-title":"IEEE Trans. Signal Process.","ISSN":"https:\/\/id.crossref.org\/issn\/1053-587X","issn-type":"print"},{"key":"34","first-page":"87","article-title":"Une propri\u00e9t\u00e9 topologique des sous-ensembles analytiques r\u00e9els","author":"\u0141ojasiewicz, S.","year":"1963"},{"issue":"1","key":"35","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/BF00939948","article-title":"On the convergence of the coordinate descent method for convex differentiable minimization","volume":"72","author":"Luo, Z. Q.","year":"1992","journal-title":"J. Optim. Theory Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0022-3239","issn-type":"print"},{"issue":"2","key":"36","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1137\/S0895479898345813","article-title":"Fast structured total least squares algorithm for solving the basic deconvolution problem","volume":"22","author":"Mastronardi, Nicola","year":"2000","journal-title":"SIAM J. Matrix Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0895-4798","issn-type":"print"},{"issue":"495","key":"37","doi-asserted-by":"publisher","first-page":"1125","DOI":"10.1198\/jasa.2011.tm09738","article-title":"SparseNet: coordinate descent with nonconvex penalties","volume":"106","author":"Mazumder, Rahul","year":"2011","journal-title":"J. Amer. Statist. Assoc.","ISSN":"https:\/\/id.crossref.org\/issn\/0162-1459","issn-type":"print"},{"key":"38","series-title":"Applied Optimization","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8853-9","volume-title":"Introductory lectures on convex optimization","volume":"87","author":"Nesterov, Yurii","year":"2004","ISBN":"https:\/\/id.crossref.org\/isbn\/1402075537"},{"key":"39","unstructured":"L. M. Nguyen, J. Liu, K. Scheinberg, and M. Tak\u00e1\u010d, SARAH: a novel method for machine learning problems using stochastic recursive gradient, International Conference on Machine Learning, 2017, pp. 2613\u20132621."},{"key":"40","unstructured":"M. Nikolova, Optimization, Applications to Image Processing, Citeseer, Philadelphia, Pennsylvania, 2014."},{"issue":"3","key":"41","doi-asserted-by":"publisher","first-page":"2053","DOI":"10.1137\/17M1142624","article-title":"Alternating structure-adapted proximal gradient descent for nonconvex nonsmooth block-regularized problems","volume":"29","author":"Nikolova, Mila","year":"2019","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"issue":"4","key":"42","doi-asserted-by":"publisher","first-page":"1018","DOI":"10.1137\/S0895479801395446","article-title":"Blind deconvolution using a regularized structured total least norm algorithm","volume":"24","author":"Pruessner, Armin","year":"2003","journal-title":"SIAM J. Matrix Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0895-4798","issn-type":"print"},{"key":"43","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1214\/aoms\/1177729586","article-title":"A stochastic approximation method","volume":"22","author":"Robbins, Herbert","year":"1951","journal-title":"Ann. Math. Statistics","ISSN":"https:\/\/id.crossref.org\/issn\/0003-4851","issn-type":"print"},{"key":"44","first-page":"233","article-title":"A convergence theorem for non negative almost supermartingales and some applications","author":"Robbins, H.","year":"1971"},{"key":"45","unstructured":"R. Tyrrell Rockafellar and R. J. Wets, Variational Analysis, Springer, 2009."},{"issue":"1","key":"46","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1137\/110854989","article-title":"A low patch-rank interpretation of texture","volume":"6","author":"Schaeffer, Hayden","year":"2013","journal-title":"SIAM J. Imaging Sci."},{"key":"47","series-title":"Applied Mathematical Sciences","isbn-type":"print","volume-title":"Variational methods in imaging","volume":"167","author":"Scherzer, Otmar","year":"2009","ISBN":"https:\/\/id.crossref.org\/isbn\/9780387309316"},{"issue":"1","key":"48","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/100781894","article-title":"Recovering low-rank and sparse components of matrices from incomplete and noisy observations","volume":"21","author":"Tao, Min","year":"2011","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"issue":"3","key":"49","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1023\/A:1017501703105","article-title":"Convergence of a block coordinate descent method for nondifferentiable minimization","volume":"109","author":"Tseng, P.","year":"2001","journal-title":"J. Optim. Theory Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0022-3239","issn-type":"print"},{"issue":"1-2","key":"50","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/s10107-007-0170-0","article-title":"A coordinate gradient descent method for nonsmooth separable minimization","volume":"117","author":"Tseng, Paul","year":"2009","journal-title":"Math. Program.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5610","issn-type":"print"},{"issue":"3","key":"51","doi-asserted-by":"publisher","first-page":"1364","DOI":"10.1137\/070709967","article-title":"On the complexity of nonnegative matrix factorization","volume":"20","author":"Vavasis, Stephen A.","year":"2009","journal-title":"SIAM J. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/1052-6234","issn-type":"print"},{"issue":"1","key":"52","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10107-015-0892-3","article-title":"Coordinate descent algorithms","volume":"151","author":"Wright, Stephen J.","year":"2015","journal-title":"Math. Program.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5610","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2024-93-348\/S0025-5718-2024-03867-X\/S0025-5718-2024-03867-X.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T05:20:25Z","timestamp":1776835225000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2024-93-348\/S0025-5718-2024-03867-X\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,8]]},"references-count":52,"journal-issue":{"issue":"348","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["S0025-5718-2024-03867-X"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3867","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2024,3,8]]}}}