Linear Lower Bounds and Conditioning of Differentiable Games
12. července 2020
Řečníci
Adam Ibrahim
Řečník · 0 sledujících
Waïss Azizian
Řečník · 0 sledujících
Gauthier Gidel
Řečník · 0 sledujících
Ioannis Mitliagkas
Řečník · 0 sledujících
O prezentaci
Recent successes of game-theoretic formulations in ML have caused a resurgence of research interest in differentiable games. Overwhelmingly, that research focuses on methods and upper bounds. In this work, we approach the question of fundamental iteration complexity by providing lower bounds to complement the linear (i.e. geometric) upper bounds observed in the literature on a wide class of problems. We cast saddle-point and min-max problems as 2-player games. We leverage tools from single-objective convex optimisation to propose new linear lower bounds for convex-concave games. Notably, we give a linear lower bound for n-player differentiable games, by using the spectral properties of the update operator. We then propose a new definition of the condition number arising from our lower bound analysis. Unlike past definitions, our condition number captures the fact that linear rates are possible in games, even in the absence of strong convex-concavity.Recent successes of game-theoretic formulations in ML have caused a resurgence of research interest in differentiable games. Overwhelmingly, that research focuses on methods and upper bounds. In this work, we approach the question of fundamental iteration complexity by providing lower bounds to complement the linear (i.e. geometric) upper bounds observed in the literature on a wide class of problems. We cast saddle-point and min-max problems as 2-player games. We leverage tools from single-objec…
Kategorie
Umělá inteligence a data science
Kategorie · 10,8k prezentací
Programování a vývoj software
Kategorie · 1,0k prezentací
O organizátorovi (ICML 2020)
The International Conference on Machine Learning (ICML) is the premier gathering of professionals dedicated to the advancement of the branch of artificial intelligence known as machine learning. ICML is globally renowned for presenting and publishing cutting-edge research on all aspects of machine learning used in closely related areas like artificial intelligence, statistics and data science, as well as important application areas such as machine vision, computational biology, speech recognition, and robotics. ICML is one of the fastest growing artificial intelligence conferences in the world. Participants at ICML span a wide range of backgrounds, from academic and industrial researchers, to entrepreneurs and engineers, to graduate students and postdocs.
Baví vás formát? Nechte SlidesLive zachytit svou akci!
Profesionální natáčení a streamování po celém světě.
Sdílení
Doporučená videa
Prezentace na podobné téma, kategorii nebo přednášejícího
Robust One-Bit Recovery via ReLU Generative Networks
Zhlédnout později
Shuang Qiu, …
Why bigger is not always better: on finite and infinite neural networks
Zhlédnout později
Adversial Learning of Prescribed Generative Models
Zhlédnout později
Solving Heterogeneous AutoML Problems with AutoGOAL
Zhlédnout později
Learning Normlizing Flows from Entropy-Kantorovich potentials
Zhlédnout později
