The purpose of this paper is to study the dynamical behavior of the sequence produced by a forward-backward algorithm involving two random maximal monotone operators and a sequence of decreasing step sizes. Defining a mean monotone operator as an Aumann integral, and assuming that the sum of the two mean operators is maximal (sufficient maximality conditions are provided), it is shown that with probability one, the interpolated process obtained from the iterates is an asymptotic pseudo trajectory in the sense of Bena " m and Hirsch of the differential inclusion involving the sum of the mean operators. The convergence of the empirical means of the iterates towards a zero of the sum of the mean operators is shown, as well as the convergence of the sequence itself to such a zero under a demipositivity assumption. These results find applications in a wide range of optimization or variational inequality problems in random environments.
The algorithm can also be used to solve a variational inequality problem. Let @math where @math are closed and convex sets in @math . Consider the problem of finding @math that solves the variational inequality [ x C, F(x_ ), x - x_ 0 , , ] where @math is a monotone single-valued operator on @math @cite_2 @cite_9 . Since the projection on @math is difficult, one can use the simple stochastic algorithm @math , where the random variables @math are distributed on the set @math . The variant where @math is itself an expectation can also be considered , @math . The work @cite_2 addresses this context. @cite_2 , it is assumed that @math is strongly monotone and that the stochastic Lipschitz property @math holds, where @math is a positive constant. In our work, the strong monotonicity of @math is not needed, and the Lipschitz property is essentially replaced with the condition @math , where @math is a subgradient of @math at @math (for instance, the least norm one), and @math satisfies a moment condition.
@cite_9 @cite_2
1516681311 2039696315
Preface to the SIAM edition Preface Glossary of notations Introduction Part I. Variational Inequalities in Rn Part II. Variational Inequalities in Hilbert Space Part III. Variational Inequalities for Monotone Operators Part IV. Problems of Regularity Part V. Free Boundary Problems and the Coincidence Set of the Solution Part VI. Free Boundary Problems Governed by Elliptic Equations and Systems Part VII. Applications of Variational Inequalities Part VIII. A One Phase Stefan Problem Bibliography Index. We consider the solution of strongly monotone variational inequalities of the form @math F ( x ? ) ? ( x - x ? ) ? 0 , for all @math x ? X . We focus on special structures that lend themselves to sampling, such as when @math X is the intersection of a large number of sets, and or @math F is an expected value or is the sum of a large number of component functions. We propose new methods that combine elements of incremental constraint projection and stochastic gradient. These methods are suitable for problems involving large-scale data, as well as problems with certain online or distributed structures. We analyze the convergence and the rate of convergence of these methods with various types of sampling schemes, and we establish a substantial rate of convergence advantage for random sampling over cyclic sampling.