Stochastic Gradient Langevin Dynamics (SGLD) is a combination of a Robbins-Monro type algorithm with Langevin dynamics. In this paper, the SGLD method with fixed step size @math is considered in order to sample from a logconcave target distribution @math , known up to a normalisation factor. We assume that unbiased estimates of the gradient from possibly dependent observations are available. It is shown that, for all @math , the Wasserstein- @math distance of the @math th iterate of the SGLD algorithm from @math is dominated by @math with appropriate constants @math and @math , whereas for the case of i.i.d. data the upper bound is improved to @math .
The convergence rate of the Euler-Maruyama scheme ) to its stationary distribution is comparable to that of the Langevin SDE ), see @cite_20 or the discussion after Proposition 3.2 of @cite_23 . However, @cite_23 proved the exponential convergence of ) under condition that the inverse temperature parameter @math satisfies @math , where @math appears in the dissipativity condition @math of @cite_23 , [ m >0, b 0: , h ( ,z) m | |^2 -b, R ^ d . ] Let us consider the same setting with strongly convex @math and @math . The constant @math , which controls the quadratic term, plays a similar role to @math in our Assumption . In @cite_23 , @math has to be larger than @math , i.e., outside a compact set, the function @math should be sufficiently convex. From the present paper it becomes clear that for the approximation ) to work, strong convexity ( @math ) is enough. Our result is stronger and not included in @cite_23 , however, it requires global convexity. Note also that the dimension @math has different effects on convergence rate: it is @math in @cite_23 and @math in our case, see Lemma .
@cite_23 @cite_20
1549918636 2806580934 2000931246 2038497950
The formulation @math minx,yf(x)+g(y),subjecttoAx+By=b,where f and g are extended-value convex functions, arises in many application areas such as signal processing, imaging and image processing, statistics, and machine learning either naturally or after variable splitting. In many common problems, one of the two objective functions is strictly convex and has Lipschitz continuous gradient. On this kind of problem, a very effective approach is the alternating direction method of multipliers (ADM or ADMM), which solves a sequence of f g-decoupled subproblems. However, its effectiveness has not been matched by a provably fast rate of convergence; only sublinear rates such as O(1 k) and @math O(1 k2) were recently established in the literature, though the O(1 k) rates do not require strong convexity. This paper shows that global linear convergence can be guaranteed under the assumptions of strong convexity and Lipschitz gradient on one of the two functions, along with certain rank assumptions on A and B. The result applies to various generalizations of ADM that allow the subproblems to be solved faster and less exactly in certain manners. The derived rate of convergence also provides some theoretical guidance for optimizing the ADM parameters. In addition, this paper makes meaningful extensions to the existing global convergence theory of ADM generalizations. We study the directed polymer model in dimension @math when the environment is heavy-tailed, with a decay exponent @math . We give all possible scaling limits of the model in the weak-coupling regime, i.e., when the inverse temperature temperature @math vanishes as the size of the system n goes to infinity. When @math , we show that all possible transversal fluctuations @math can be achieved by tuning properly @math , allowing to interpolate between all super-diffusive scales. Moreover, we determine the scaling limit of the model, answering a conjecture by Dey and Zygouras [cf:DZ] - we actually identify five different regimes. On the other hand, when @math , we show that there are only two regimes: the transversal fluctuations are either @math or @math . As a key ingredient, we use the Entropy-controlled Last Passage Percolation (E-LPP), introduced in a companion paper [cf:BT_ELPP]. Let f be a random Boolean formula that is an instance of 3-SAT. We consider the problem of computing the least real number k such that if the ratio of the number of clauses over the number of variables of f strictly exceeds k , then f is almost certainly unsatisfiable. By a well-known and more or less straightforward argument, it can be shown that kF5.191. This upper bound was improved by to 4.758 by first providing new improved bounds for the occupancy problem. There is strong experimental evidence that the value of k is around 4.2. In this work, we define, in terms of the random formula f, a decreasing sequence of random variables such that, if the expected value of any one of them converges to zero, then f is almost certainly unsatisfiable. By letting the expected value of the first term of the sequence converge to zero, we obtain, by simple and elementary computations, an upper bound for k equal to 4.667. From the expected value of the second term of the sequence, we get the value 4.601q . In general, by letting the U This work was performed while the first author was visiting the School of Computer Science, Carleton Ž University, and was partially supported by NSERC Natural Sciences and Engineering Research Council . of Canada , and by a grant from the University of Patras for sabbatical leaves. The second and third Ž authors were supported in part by grants from NSERC Natural Sciences and Engineering Research . Council of Canada . During the last stages of this research, the first and last authors were also partially Ž . supported by EU ESPRIT Long-Term Research Project ALCOM-IT Project No. 20244 . †An extended abstract of this paper was published in the Proceedings of the Fourth Annual European Ž Symposium on Algorithms, ESA’96, September 25]27, 1996, Barcelona, Spain Springer-Verlag, LNCS, . pp. 27]38 . That extended abstract was coauthored by the first three authors of the present paper. Correspondence to: L. M. Kirousis Q 1998 John Wiley & Sons, Inc. CCC 1042-9832r98r030253-17 253 For the problem of minimizing a lower semicontinuous proper convex function f on a Hilbert space, the proximal point algorithm in exact form generates a sequence @math by taking @math to be the minimizes of @math , where @math . This algorithm is of interest for several reasons, but especially because of its role in certain computational methods based on duality, such as the Hestenes-Powell method of multipliers in nonlinear programming. It is investigated here in a more general form where the requirement for exact minimization at each iteration is weakened, and the subdifferential @math is replaced by an arbitrary maximal monotone operator T. Convergence is established under several criteria amenable to implementation. The rate of convergence is shown to be “typically” linear with an arbitrarily good modulus if @math stays large enough, in fact superlinear if @math . The case of @math is treated in extra detail. Applicati...