Exploration of Last Iterate Convergence for Optimistic FTRL Algorithm

Recent advancements in GANS and reinforcement learning are through applications of monotone and Lipschitz variational inequalities, an important problem in optimization. This has spurred interest in proving last-iterate convergence rates of certain algorithms, namely EG and OGDA. This problem has been partially tackled with best-iterate guarantees, and recently the two types of convergence has been shown to be equivalent by way of computationally discovered monotonic potential functions. Both (Cai et al., 2022) and (Gorbunov et al., 2022) have shown separate computational proof methods to solve for these potential functions, reducing a proof search to a proof verification. Inspired by one of the methods, SOS programming, we explore the monotonicity of similar potential functions under OFTRL update rules and demonstrate the necessity for a larger SOS program for this algorithm.