The Last-Iterate Convergence Rate of Optimistic Mirror Descent in Stochastic Variational Inequalities
In this paper, we analyze the local convergence rate of optimistic mirror descent methods in stochastic variational inequalities, a class of optimization problems with important applications to learning theory and machine learning. Our analysis reveals an intricate relation between the algorithm's rate of convergence and the local geometry induced by the method's underlying Bregman function. We quantify this relation by means of the Legendre exponent, a notion that we introduce to measure the growth rate of the Bregman divergence relative to the ambient norm near a solution. We show that this exponent determines both the optimal step-size policy of the algorithm and the optimal rates attained, explaining in this way the differences observed for some popular Bregman functions (Euclidean projection, negative entropy, fractional power, etc.).
Code (0)
등록된 구현이 없습니다.
Tasks
Learning TheoryRelationSimilar Papers 제목 키워드 기반
Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes
In a recent series of papers it has been established that variants of Gradient Descent/Ascent and Mirror Descent exhibit last iterate convergence in convex-concave zero-sum games. Specifically, \cite{DISZ17, LiangS18} sh…
The Power of Regularization in Solving Extensive-Form Games
In this paper, we investigate the power of {\it regularization}, a common technique in reinforcement learning and optimization, in solving extensive-form games (EFGs). We propose a series of new algorithms based on regul…
counterfactualFormLast-iterate Convergence Separation between Extra-gradient and Optimism in Constrained Periodic Games
Last-iterate behaviors of learning algorithms in repeated two-player zero-sum games have been extensively studied due to their wide applications in machine learning and related tasks. Typical algorithms that exhibit the …
Adaptively Perturbed Mirror Descent for Learning in Games
This paper proposes a payoff perturbation technique for the Mirror Descent (MD) algorithm in games where the gradient of the payoff functions is monotone in the strategy profile space, potentially containing additive noi…
Forward Looking Best-Response Multiplicative Weights Update Methods for Bilinear Zero-sum Games
Our work focuses on extra gradient learning algorithms for finding Nash equilibria in bilinear zero-sum games. The proposed method, which can be formally considered as a variant of Optimistic Mirror Descent \cite{DBLP:co…