Timezone: »

 
Poster
On the convergence of single-call stochastic extra-gradient methods
Yu-Guan Hsieh · Franck Iutzeler · Jérôme Malick · Panayotis Mertikopoulos

Wed Dec 11 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #160
in Optimization -- Stochastic Optimization »
Variational inequalities have recently attracted considerable interest in machine learning as a flexible paradigm for models that go beyond ordinary loss function minimization (such as generative adversarial networks and related deep learning systems). In this setting, the optimal O(1/t) convergence rate for solving smooth monotone variational inequalities is achieved by the Extra-Gradient (EG) algorithm and its variants. Aiming to alleviate the cost of an extra gradient step per iteration (which can become quite substantial in deep learning), several algorithms have been proposed as surrogates to Extra-Gradient with a single oracle call per iteration. In this paper, we develop a synthetic view of such algorithms, and we complement the existing literature by showing that they retain a $O(1/t)$ ergodic convergence rate in smooth, deterministic problems. Subsequently, beyond the monotone deterministic case, we also show that the last iterate of single-call, stochastic extra-gradient methods still enjoys a $O(1/t)$ local convergence rate to solutions of non-monotone variational inequalities that satisfy a second-order sufficient condition.
Keywords: Optimization · Stochastic Optimization · Optimization -> Convex Optimization; Optimization
[ Paper]  [ Slides] 

Author Information

Yu-Guan Hsieh (Univ. Grenoble Alpes)
Franck Iutzeler (Univ. Grenoble Alpes)
Jérôme Malick (CNRS and LJK)
Panayotis Mertikopoulos (CNRS (French National Center for Scientific Research))

More from the Same Authors