Stochastic Forward–Backward Splitting for Monotone Inclusions
We propose and analyze the convergence of a novel stochastic algorithm for monotone inclusions that are sum of a maximal monotone operator and a single-valued cocoercive operator. The algorithm we propose is a natural stochastic extension of the classical forward–backward method. We provide a non-as...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer US
2016
|
| Online Access: | http://hdl.handle.net/1721.1/103419 https://orcid.org/0000-0001-6376-4786 |
| _version_ | 1811083012872339456 |
|---|---|
| author | Villa, Silvia Vũ, Bang Công Rosasco, Lorenzo Andrea |
| author2 | Massachusetts Institute of Technology. Laboratory for Computational and Statistical Learning |
| author_facet | Massachusetts Institute of Technology. Laboratory for Computational and Statistical Learning Villa, Silvia Vũ, Bang Công Rosasco, Lorenzo Andrea |
| author_sort | Villa, Silvia |
| collection | MIT |
| description | We propose and analyze the convergence of a novel stochastic algorithm for monotone inclusions that are sum of a maximal monotone operator and a single-valued cocoercive operator. The algorithm we propose is a natural stochastic extension of the classical forward–backward method. We provide a non-asymptotic error analysis in expectation for the strongly monotone case, as well as almost sure convergence under weaker assumptions. For minimization problems, we recover rates matching those obtained by stochastic extensions of the so-called accelerated methods. Stochastic quasi-Fejér’s sequences are a key technical tool to prove almost sure convergence. |
| first_indexed | 2024-09-23T12:17:53Z |
| format | Article |
| id | mit-1721.1/103419 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:17:53Z |
| publishDate | 2016 |
| publisher | Springer US |
| record_format | dspace |
| spelling | mit-1721.1/1034192022-09-28T00:57:34Z Stochastic Forward–Backward Splitting for Monotone Inclusions Villa, Silvia Vũ, Bang Công Rosasco, Lorenzo Andrea Massachusetts Institute of Technology. Laboratory for Computational and Statistical Learning McGovern Institute for Brain Research at MIT Rosasco, Lorenzo Andrea Vũ, Bang Công Villa, Silvia We propose and analyze the convergence of a novel stochastic algorithm for monotone inclusions that are sum of a maximal monotone operator and a single-valued cocoercive operator. The algorithm we propose is a natural stochastic extension of the classical forward–backward method. We provide a non-asymptotic error analysis in expectation for the strongly monotone case, as well as almost sure convergence under weaker assumptions. For minimization problems, we recover rates matching those obtained by stochastic extensions of the so-called accelerated methods. Stochastic quasi-Fejér’s sequences are a key technical tool to prove almost sure convergence. Italy. Ministero dell'istruzione, dell'università e della ricerca (FIRB project RBFR12M3AC) Vietnam. National Foundation for Science and Technology Development (Grant No. 102.01-2014.02) 2016-07-01T18:13:14Z 2017-03-01T16:14:49Z 2016-02 2016-05-23T12:16:20Z Article http://purl.org/eprint/type/JournalArticle 0022-3239 1573-2878 http://hdl.handle.net/1721.1/103419 Rosasco, Lorenzo, Silvia Villa, and Bang Công Vũ. “Stochastic Forward–Backward Splitting for Monotone Inclusions.” Journal of Optimization Theory and Applications 169, no. 2 (February 18, 2016): 388–406. https://orcid.org/0000-0001-6376-4786 en http://dx.doi.org/10.1007/s10957-016-0893-2 Journal of Optimization Theory and Applications Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. Springer Science+Business Media New York application/pdf Springer US Springer US |
| spellingShingle | Villa, Silvia Vũ, Bang Công Rosasco, Lorenzo Andrea Stochastic Forward–Backward Splitting for Monotone Inclusions |
| title | Stochastic Forward–Backward Splitting for Monotone Inclusions |
| title_full | Stochastic Forward–Backward Splitting for Monotone Inclusions |
| title_fullStr | Stochastic Forward–Backward Splitting for Monotone Inclusions |
| title_full_unstemmed | Stochastic Forward–Backward Splitting for Monotone Inclusions |
| title_short | Stochastic Forward–Backward Splitting for Monotone Inclusions |
| title_sort | stochastic forward backward splitting for monotone inclusions |
| url | http://hdl.handle.net/1721.1/103419 https://orcid.org/0000-0001-6376-4786 |
| work_keys_str_mv | AT villasilvia stochasticforwardbackwardsplittingformonotoneinclusions AT vubangcong stochasticforwardbackwardsplittingformonotoneinclusions AT rosascolorenzoandrea stochasticforwardbackwardsplittingformonotoneinclusions |