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
2766153148 2790417304 2963005234 2517669009
The usual approach to developing and analyzing first-order methods for non-smooth (stochastic or deterministic) convex optimization assumes that the objective function is uniformly Lipschitz continuous with parameter @math . However, in many settings the non-differentiable convex function @math is not uniformly Lipschitz continuous -- for example (i) the classical support vector machine (SVM) problem, (ii) the problem of minimizing the maximum of convex quadratic functions, and even (iii) the univariate setting with @math . Herein we develop a notion of "relative continuity" that is determined relative to a user-specified "reference function" @math (that should be computationally tractable for algorithms), and we show that many non-differentiable convex functions are relatively continuous with respect to a correspondingly fairly-simple reference function @math . We also similarly develop a notion of "relative stochastic continuity" for the stochastic setting. We analysis two standard algorithms -- the (deterministic) mirror descent algorithm and the stochastic mirror descent algorithm -- for solving optimization problems in these two new settings, and we develop for the first time computational guarantees for instances where the objective function is not uniformly Lipschitz continuous. This paper is a companion paper for non-differentiable convex optimization to the recent paper by Lu, Freund, and Nesterov, which developed similar sorts of results for differentiable convex optimization. We consider an algorithm that successively samples and minimizes stochastic models of the objective function. We show that under weak-convexity and Lipschitz conditions, the algorithm drives the expected norm of the gradient of the Moreau envelope to zero at the rate @math . Our result yields new complexity guarantees for the stochastic proximal point algorithm on weakly convex problems and for the stochastic prox-linear algorithm for minimizing compositions of convex functions with smooth maps. Moreover, our result also recovers the recently obtained complexity estimate for the stochastic proximal subgradient method on weakly convex problems. The purpose of this paper is to establish the almost sure weak ergodic convergence of a sequence of iterates @math given by @math where @math is a collection of maximal monotone operators on a separable Hilbert space, @math is an independent identically distributed sequence of random variables on @math and @math is a positive sequence in @math . The weighted averaged sequence of iterates is shown to converge weakly to a zero (assumed to exist) of the Aumann expectation @math under the assumption that the latter is maximal. We consider applications to stochastic optimization problems of the form @math , where @math is a normal convex integrand and @math is a collection of closed convex sets. In this case, the iterations are closely related to a stochastic proximal algorithm recently proposed by Wang and Bertsekas [Increment... In stochastic convex optimization the goal is to minimize a convex function @math over a convex set @math where @math is some unknown distribution and each @math in the support of @math is convex over @math . The optimization is commonly based on i.i.d. samples @math from @math . A standard approach to such problems is empirical risk minimization (ERM) that optimizes @math . Here we consider the question of how many samples are necessary for ERM to succeed and the closely related question of uniform convergence of @math to @math over @math . We demonstrate that in the standard @math setting of Lipschitz-bounded functions over a @math of bounded radius, ERM requires sample size that scales linearly with the dimension @math . This nearly matches standard upper bounds and improves on @math dependence proved for @math setting by Shalev- (2009). In stark contrast, these problems can be solved using dimension-independent number of samples for @math setting and @math dependence for @math setting using other approaches. We further show that our lower bound applies even if the functions in the support of @math are smooth and efficiently computable and even if an @math regularization term is added. Finally, we demonstrate that for a more general class of bounded-range (but not Lipschitz-bounded) stochastic convex programs an infinite gap appears already in dimension 2.