I was born in Hong Kong before 1997, a time before the abyss.

**Natural Algorithms in Economics**(including**Learning Algorithms/Dynamics in Games**and**Market Dynamics**),**Asynchronous Optimization and Iterative Systems**and**Graph Sparsification, Partitioning and Clustering**.

- 13 January 2021: Our paper with Yixin Tao, "Chaos of Learning Beyond Zero-sum and Coordination via Game Decompositions", is accepted to ICLR 2021. In an 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, 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: Our 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). This is a companion work of an earlier paper accepted to Mathematical Programming Series A (MPA). In the SIOPT paper, we use 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: 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...).

- 25 September, 2020: Our paper with Georgios Piliouras, "Chaos, Extremism and Optimism: Volume Analysis of Learning in Games", is accepted to NeurIPS 2020. We prove that Multiplicative Weights Update (MWU) in two-person zero-sum game is chaotic and have bad behaviors (named
*extremism*) via volume analysis. 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. - 1 August, 2020: Our 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. 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. - 24 July, 2020: I gave a talk in SUTD on "Online Optimization in Games via Control Theory", a joint work with Georgios Piliouras. The slides are available here.

with Stefanos Leonardos, Shyam Sridhar and Georgios Piliouras. Working Paper, appeared in WINE 2020 Workshop on Blockchain.

with Yixin Tao. To appear in

with Richard Cole and Yixin Tao. Accepted to

with Richard Cole and Yixin Tao. In

with Georgios Piliouras.

with Richard Cole and Nikhil R. Devanur.

Full journal version in

with Georgios Piliouras.

with Martin Hoefer and Paresh Nakhe.

with Richard Cole and Yixin Tao.

with L. Sunil Chandran and Davis Issac.

with Richard Cole.

with Bhaskar Ray Chaudhury, Jugal Garg, Naveen Garg, Martin Hoefer and Kurt Mehlhorn.

with Gramoz Goranci and Monika Henzinger.

with Monika Henzinger, Martin Hoefer and Martin Starnberger.

with Richard Cole and Ashish Rastogi.

with Mordecai Golin.

with Philippe Flajolet, Mordecai Golin, C.Y. James Lee.

with Mordecai Golin. To appear as a chapter in