2019/12/03 by Abhishek Roy, Yifang Chen, Roy, Abhishek +5 · 3 citations
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Optimization and Search Problems #Risk and Portfolio Optimization #Statistics Theory (math.ST) #cs.DS #math.OC #math.ST #stat.ML #stat.TH
paper · pdf · doi:10.48550/arxiv.1912.01698
arxiv created 2019/12/03 · openalex publication_date 2019/12/03 · arxiv updated 2019/12/05 · openalex created_date 2019/12/13 · openalex updated_date 2026/07/28
Saddle-point optimization problems are an important class of optimization problems with applications to game theory, multi-agent reinforcement learning and machine learning. A majority of the rich literature available for saddle-point optimization has focused on the offline setting. In this paper, we study nonstationary versions of stochastic, smooth, strongly-convex and strongly-concave saddle-point optimization problem, in both online (or first-order) and multi-point bandit (or zeroth-order) settings. We first propose natural notions of regret for such nonstationary saddle-point optimization problems. We then analyze extragradient and Frank-Wolfe algorithms, for the unconstrained and constrained settings respectively, for the above class of nonstationary saddle-point optimization problems. We establish sub-linear regret bounds on the proposed notions of regret in both the online and bandit setting.