2019/07/09 by James P. Bailey, Bailey, James P., Gauthier Gidel +3 · 5 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Computer Science and Game Theory (cs.GT) #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning and Algorithms #Optimization and Control (math.OC) #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1907.04392
openalex publication_date 2019/07/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Gradient descent is arguably one of the most popular online optimization methods with a wide array of applications. However, the standard implementation where agents simultaneously update their strategies yields several undesirable properties; strategies diverge away from equilibrium and regret grows over time. In this paper, we eliminate these negative properties by introducing a different implementation to obtain finite regret via arbitrary fixed step-size. We obtain this surprising property by having agents take turns when updating their strategies. In this setting, we show that an agent that uses gradient descent obtains bounded regret -- regardless of how their opponent updates their strategies. Furthermore, we show that in adversarial settings that agents' strategies are bounded and cycle when both are using the alternating gradient descent algorithm.