5 papers
Algorithms with Smoothed Polynomial-Time Complexity for Deterministic Discounted-sum and Mean-payoff Games
Ali Asadi, Krishnendu Chatterjee, Ruichen Luo
Turn-based deterministic games on graphs are two-player zero-sum games played on finite directed graphs, where the vertex set is partitioned between the Max and the adversarial Min…
Efficient Gradient Methods for Distributed Saddle Problems
Ruichen Luo, Anton Rodomanov, Sebastian U. Stich
The distributed setting for Saddle Problems (SPs) has recently emerged as a framework for various modern applications in machine learning and multiagent systems. Despite its releva…
Monotone Near-Zero-Sum Games: A Generalization of Convex-Concave Minimax
Ruichen Luo, Sebastian U. Stich, Krishnendu Chatterjee
Zero-sum and non-zero-sum (aka general-sum) games are relevant in a wide range of applications. While general non-zero-sum games are computationally hard, researchers focus on the…
Revisiting LocalSGD and SCAFFOLD: Improved Rates and Missing Analysis
Ruichen Luo, Sebastian U Stich, Samuel Horváth +1
LocalSGD and SCAFFOLD are widely used methods in distributed stochastic optimization, with numerous applications in machine learning, large-scale data processing, and federated lea…
Linear Equations with Min and Max Operators: Computational Complexity
Krishnendu Chatterjee, Ruichen Luo, Raimundo Saona +1
We consider a class of optimization problems defined by a system of linear equations with min and max operators. This class of optimization problems has been studied under restrict…