• 8 May 2021: Paper with Georgios Piliouras, "Online Optimization in Games via Control Theory: Connecting Regret, Passivity and Poincaré Recurrence", is accepted to ICML 2021. In July 2020, I gave a talk on this paper in SUTD. The slides are available here. [More/Less]
  
  Recently in the popular topic of learning in games, we have seen a number of interesting results in the form of: in a game G, if both players learn to play using algorithm A, then some phenonmenon happens. Most analyses apparently require careful coupling of the properties of the game G and the learning algorithm A. In 2013, the seminal work of Fox and Shamma presented a framework which amazingly suggests how game and learning algorithm can be decoupled via the control-theoretic concept of feedback interconnection, and how they can be analyzed separately (!) via the control-theoretic notion of passivity and its generalizations.
  
  In this paper, we show that the famous family of continuous Follow-The-Regularized-Leader (FTRL) learning algorithm is lossless passive. Also, the family of lossless passive learning algorithms is convex -- informally, given any two lossless passive learning algorithm, we can take a convex combination (say 50-50) of them to form another new lossless passive learning algorithm. This yields a whole new family of learning algorithms that guarantee constant total regret. When they are applied to zero-sum games with an interior Nash equilibria, Poincaré Recurrence can be shown.
  
  
• 29 April 2021: Paper with Stefanos Leonardos and Georgios Piliouras, "Learning in Markets: Greed Leads to Chaos but Following the Price is Right", is accepted to IJCAI 2021. [More/Less]
  
  Consider the following game in multi-cryptocurrency mining with a large number of individual miners. Each miner has a limited amount of computing time, constrained by the hardware she possesses. Depending on the value of each cryptocurrency and the chance of successful mining in each cryptocurrency, she faces the strategic problem of how to optimality allocating her computing time to mining different cryptocurrencies, so as to maximize her own benefit. Such games have been studied under the name of Tullock contests. In the Internet era, we can see analogous production economies in crowdsourcing and P2P network applications.
  
  In these large and distributed production economies, we desire stability. We ask: is there any distributed protocol the players can use to adjust their strategic choices, so that the economy eventually reaches a stable state, e.g. (approximate) Nash equilibrium?
  
  The first choices of such protocols are game-theoretic motivated, e.g. Gradient Ascent and Best Response. However, we formally prove that Gradient Ascent can lead to unstable and even chaotic behavior, via the rigorous notion of Li-Yorke chaos. The chaos can occur even in the very simple instance with only 2 homogeneous players and 1 cryptocurrency.
  
  To remedy this, we observe that when such production economies becomes large, i.e. there are a large number of miners and none of them has superior amount of computing time, we may model it as a Fisher market with quasilinear utilities instead. Then by using the market-motivated protocol of Proportional Response, which was shown to be remarkably stable in many markets via techniques in Numerical Optimization, the players will reach the market equilibrium of the Fisher market, while the largeness guarantees the market equilibrium is an approximate Nash equilibrium.
  
  
• 13 January 2021: Paper with Yixin Tao, "Chaos of Learning Beyond Zero-sum and Coordination via Game Decompositions", is accepted to ICLR 2021. [More/Less]
  
  In earlier work with Georgios (COLT 2019, NeurIPS 2020), we showed that Multiplicative Weights Update (MWU) is Lyapunov chaotic in two-person zero-sum games and have bad behaviors via volume analysis. Analogous results are extended to different algorithms (FTRL, Optimistic MWU) and other games (coordination game, generalized Rock-Paper-Scissors). But really, when we talk about "learning in games", we want to understand the behaviors of learning algorithms in general games. In the ICLR paper with Yixin, we extend the volume analysis argument to two-person general games via a canonical game decomposition into zero-sum and coordination components. This elegantly decouples the volume-changing behavior into opposing competition between the two components. We propose measures that compare the strengths of the two components and characterizes games in which MWU is Lyapunov chaotic (almost) everywhere. We also share some insights into general games with three or more players.
  
  
• 18 November 2020: Paper with Richard Cole and Yixin Tao, "Parallel Stochastic Asynchronous Coordinate Descent: Tight Bounds on the Possible Parallelism", is accepted to SIAM Journal on Optimization (SIOPT). [More/Less]
  
  This is a companion work of an earlier paper accepted to Mathematical Programming Series A (MPA). In the SIOPT paper, we provide an explicit construction to show that when the number of cores used for asynchronous implementation of stochastic coordinate descent exceeds a certain limit, the process can diverge from the minimal point quickly. The limit we show matches asymptotically with the lower bound presented in the MPA paper.
  
  
• 15 November 2020: Prototype video of volume expansion in game dynamics, generated via GPU computing. [More/Less]
  
  For generating high-quality animations of volume changes in learning dynamical system, we need to simulate the system with a lot of starting points. This took a long time with CPU. Recently, I have learnt that GPU can accelerate this process by hundreds of times. Via GPU programming with Python, I generate a prototype video below when both players in Matching-Pennies game (left) and a tiny perturbation of Matching-Pennies game (right) learn using Multiplicative Weights Update (MWU). You will see that the volume expands in both cases, but the shapes in the later stages are very different, even when the underlying games are very similar. The video length is 4 minutes. The first 2 minutes is a bit boring; be patient (or you can skip it...).
  
  
  
• 16 October 2020: Program Committee, ACM EC 2021.
• 25 September, 2020: Paper with Georgios Piliouras, "Chaos, Extremism and Optimism: Volume Analysis of Learning in Games", is accepted to NeurIPS 2020. [More/Less]
  
  We prove that Multiplicative Weights Update (MWU) in two-person zero-sum game is chaotic and have bad behaviors (named extremism) via volume analysis.
  
  Lyapunov Chaos: Briefly, the volume of a learning system quantities its possibilities. By proving the volume expands quickly, we show that the learning system becomes more unpredictable in the long run, which can be formally captured as Lyapunov chaos. See a short video for volume expansion in 3D, of MWU in a cyclic Matching Pennies game.
  
  Extremism: To explain what extremism is, it is best to use the popular game of Rock-Paper-Scissors. There are two players, each employing MWU to learn in playing the game. Extremism means: eventually the players get stuck at an abnormal situation for a long period of time, say Player 1 keeps choosing Paper (with high probability), but Player 2 stubbornly keep choosing Rock (with high probability), and hence Player 2 keeps losing.
  
  
• 1 August, 2020: Paper with Richard Cole and Yixin Tao, "Fully Asynchronous Stochastic Coordinate Descent: a Tight Lower Bound on the Parallelism Achieving Linear Speedup", is accepted to Mathematical Programming Series A. [More/Less]
  
  In numerical optimization, it is natural to consider parallel and asynchronous implementations of first-order methods, e.g. gradient descent. Ideally, we hope that a speedup in proportion to the number of cores (processors) can be achieved. This is called linear speedup. But linear speedup can only be guaranteed when the number of cores is less than a limit that depends on the convexity parameters of the function being minimized. We present the asymptotic tight lower bound of the limit.
  
  Such implementations without any synchronization overhead can cause subtle asynchrony effects, which make a rigorous analysis difficult. Prior works have bypassed some of these difficulties via assumptions. Our analysis makes essentially no assumption, except that a thread can only overlap with a bounded number of other threads.
  
  

Theses and Book Chapter