AroundConnect

2008

Solving variational inequalities with Stochastic Mirror-Prox algorithm

Juditsky, Anatoli, Nemirovskii, Arkadii S., Tauvel, Claire

Understand

In this paper we consider iterative methods for stochastic variational inequalities (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.

Built on

  • Juditsky, A., Nemirovski, A. (2008), Large Deviations of Vector-valued Martingales in 2-Smooth Normed Spaces E-print: http://www.optimization-online.org/DB_HTML/2008/04/1947.html

    1947

    Earlier work this paper cites.

  • Azuma, K. Weighted sums of certain dependent random variables. Tökuku Math. J

    1967

    Earlier work this paper cites.

  • Korpelevich, G. “Extrapolation gradient methods and relation to Modified Lagrangeans” Ekonomika i Matematicheskie Metody

    1983

    Earlier work this paper cites.

  • Nemirovski, A., Yudin, D., Problem complexity and method efficiency in Optimization

    1983

    Earlier work this paper cites.

  • Grigoriadis, M.D., Khachiyan, L.G. A sublinear-time randomized approximation algorithm for matrix games. Operations Research Letters

    1995

    Earlier work this paper cites.

Similar

  • A. Nemirovski, “Prox-method with rate of convergence O ⁡ ( 1 / t ) O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems” – SIAM J. Optim

    2004

    Cited alongside, same era.

  • Ben-Tal, A., Nemirovski, A. “Non-Euclidean restricted memory level method for large-scale convex optimization” – Math. Progr

    2005

    Cited alongside, same era.

  • Nesterov, Yu. “Smooth minimization of non-smooth functions”, Math. Progr

    2005

    Cited alongside, same era.

  • Nesterov, Yu. “Excessive gap technique in nonsmooth convex minimization”, SIAM J. Optim

    2005

    Cited alongside, same era.

  • Rubinfeld, R., Sublinear time algorithms. – Marta Sanz-Solé, Javier Soria, Juan Luis Varona, Joan Verdera, Eds. International Congress of Mathematicians, Madrid 2006

    2006

    Cited alongside, same era.

Then

  • Lu, Z., Nemirovski A., Monteiro, R. “Large-Scale Semidefinite Programming via Saddle Point Mirror-Prox Algorithm”, Math. Progr

    2007

    Later among the works it cites.

  • Nemirovski, A., Onn, S., Rothblum, U. (2007), “Accuracy certificates for computational problems with convex structure” – submitted to Mathematics of Operations Research

    2007

    Later among the works it cites.

  • Nesterov, Yu. “Dual extrapolation and its applications to solving variational inequalities and related problems”, Math. Progr

    2007

    Later among the works it cites.

  • Juditsky, A. Lan, G., Nemirovski, A., Shapiro, A., Stochastic Approximation Approach to Stochastic Programming, SIAM Journal on Opt. 19

    2009

    Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…