We study the extension of the proximal gradient algorithm where only a stochastic gradient estimate is available and a relaxation step is allowed. We establish convergence rates for function values ...in the convex case, as well as almost sure convergence and convergence rates for the iterates under further convexity assumptions. Our analysis avoid averaging the iterates and error summability assumptions which might not be satisfied in applications, e.g. in machine learning. Our proofing technique extends classical ideas from the analysis of deterministic proximal gradient algorithms.
This paper deals with the study of weak sharp solutions for nonsmooth variational inequalities and finite convergence property of the proximal point method. We present several characterizations for ...weak sharpness of the solutions set of nonsmooth variational inequalities without using the gap functions. We show that under weak sharpness of the solutions set, the sequence generated by proximal point methods terminates after a finite number of iterations. We also give an upper bound for the number of iterations for which the sequence generated by the exact proximal point methods terminates.
For a finite/infinite family of closed convex sets with nonempty intersection in Hilbert space, we consider the (bounded) linear regularity property and the linear convergence property of the ...projection-based methods for solving the convex feasibility problem. Several sufficient conditions are provided to ensure the bounded linear regularity in terms of the interior-point conditions and some finite codimension assumptions. A unified projection method, called Algorithm B-EMOPP, for solving the convex feasibility problem is proposed, and by using the bounded linear regularity, the linear convergence results for this method are established under a new control strategy introduced here.
We study mean field games and corresponding
N
-player games in continuous time over a finite time horizon where the position of each agent belongs to a finite state space. As opposed to previous ...works on finite state mean field games, we use a probabilistic representation of the system dynamics in terms of stochastic differential equations driven by Poisson random measures. Under mild assumptions, we prove existence of solutions to the mean field game in relaxed open-loop as well as relaxed feedback controls. Relying on the probabilistic representation and a coupling argument, we show that mean field game solutions provide symmetric
ε
N
-Nash equilibria for the
N
-player game, both in open-loop and in feedback strategies (not relaxed), with
ε
N
≤
constant
N
.
Under stronger assumptions, we also find solutions of the mean field game in ordinary feedback controls and prove uniqueness either in case of a small time horizon or under monotonicity.