Solving variational inequalities with stochastic mirror-prox algorithm
We consider iterative methods for <i>stochastic variational inequalities</i> (s.v.i.) with monotone operators. Our basic assumption is that the operator possesses both smooth and nonsmooth components. Further, only noisy observations of the problem data are available. We develop a novel...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Institute for Operations Research and the Management Sciences (INFORMS)
2011-01-01
|
| Series: | Stochastic Systems |
| Subjects: | |
| Online Access: | http://www.i-journals.org/ssy/viewarticle.php?id=11&layout=abstract |
| _version_ | 1817977604899078144 |
|---|---|
| author | Anatoli B. Juditsky Arkadi S. Nemirovski Claire Tauvel |
| author_facet | Anatoli B. Juditsky Arkadi S. Nemirovski Claire Tauvel |
| author_sort | Anatoli B. Juditsky |
| collection | DOAJ |
| description | We consider iterative methods for <i>stochastic variational inequalities</i> (s.v.i.) with monotone operators. Our basic assumption is that the operator possesses both smooth and nonsmooth components. Further, only noisy observations of the problem data are available. We develop a novel Stochastic Mirror-Prox (SMP) algorithm for solving s.v.i. and show that with the convenient stepsize strategy it attains the optimal rates of convergence with respect to the problem parameters. We apply the SMP algorithm to Stochastic composite minimization and describe particular applications to Stochastic Semidefinite Feasability problem and Eigenvalue minimization. |
| first_indexed | 2024-04-13T22:18:35Z |
| format | Article |
| id | doaj.art-bee5445522784b3dad3f745ea5a9ad59 |
| institution | Directory Open Access Journal |
| issn | 1946-5238 |
| language | English |
| last_indexed | 2024-04-13T22:18:35Z |
| publishDate | 2011-01-01 |
| publisher | Institute for Operations Research and the Management Sciences (INFORMS) |
| record_format | Article |
| series | Stochastic Systems |
| spelling | doaj.art-bee5445522784b3dad3f745ea5a9ad592022-12-22T02:27:22ZengInstitute for Operations Research and the Management Sciences (INFORMS)Stochastic Systems1946-52382011-01-01111758Solving variational inequalities with stochastic mirror-prox algorithmAnatoli B. JuditskyArkadi S. NemirovskiClaire TauvelWe consider iterative methods for <i>stochastic variational inequalities</i> (s.v.i.) with monotone operators. Our basic assumption is that the operator possesses both smooth and nonsmooth components. Further, only noisy observations of the problem data are available. We develop a novel Stochastic Mirror-Prox (SMP) algorithm for solving s.v.i. and show that with the convenient stepsize strategy it attains the optimal rates of convergence with respect to the problem parameters. We apply the SMP algorithm to Stochastic composite minimization and describe particular applications to Stochastic Semidefinite Feasability problem and Eigenvalue minimization.http://www.i-journals.org/ssy/viewarticle.php?id=11&layout=abstractVariational inequalities with monotone operatorsstochastic convex-concave saddle-point problemlarge scale stochastic approximationreduced complexity algorithms for convex optimization |
| spellingShingle | Anatoli B. Juditsky Arkadi S. Nemirovski Claire Tauvel Solving variational inequalities with stochastic mirror-prox algorithm Stochastic Systems Variational inequalities with monotone operators stochastic convex-concave saddle-point problem large scale stochastic approximation reduced complexity algorithms for convex optimization |
| title | Solving variational inequalities with stochastic mirror-prox algorithm |
| title_full | Solving variational inequalities with stochastic mirror-prox algorithm |
| title_fullStr | Solving variational inequalities with stochastic mirror-prox algorithm |
| title_full_unstemmed | Solving variational inequalities with stochastic mirror-prox algorithm |
| title_short | Solving variational inequalities with stochastic mirror-prox algorithm |
| title_sort | solving variational inequalities with stochastic mirror prox algorithm |
| topic | Variational inequalities with monotone operators stochastic convex-concave saddle-point problem large scale stochastic approximation reduced complexity algorithms for convex optimization |
| url | http://www.i-journals.org/ssy/viewarticle.php?id=11&layout=abstract |
| work_keys_str_mv | AT anatolibjuditsky solvingvariationalinequalitieswithstochasticmirrorproxalgorithm AT arkadisnemirovski solvingvariationalinequalitieswithstochasticmirrorproxalgorithm AT clairetauvel solvingvariationalinequalitieswithstochasticmirrorproxalgorithm |