Deep Neural Networks Are Congestion Games: From Loss Landscape to Wardrop Equilibrium and Beyond

Since the very seeding of the machine learning (ML) field, the ML researchers has constantly drawn inspiration from other areas of science both to develop novel approaches and to better understand the existing ones. One such notable example is a longstanding fruitful relationship of ML with game theory (GT) that manifested itself by the novel insights regarding the analysis of such different learning settings as reinforcement learning [Peshkin et al., 2000, Hu and Wellman, 2003, Claus and Boutilier, 1998], boosting [Freund and Schapire, 1996] and adversarial classification [Liu and Chawla, 2009, Brückner and Scheffer, 2011, Dritsoula et al., 2017] to name a few. While the interplay between ML and GT in the above-mentioned cases is natural, ie, reinforcement learning is a game played between the agent and the environment, boosting is a repeated game with rewards and adversarial learning can be seen as a traditional minimax game, very few works studied the connection between the deep neural networks (DNNs) and GT despite the omnipresence of the former in the ML field. Indeed, in recent years, deep learning has imposed itself as the state of the art ML method in many real-world tasks, such as computer vision or natural language processing to name a few [Goodfellow et al., 2016]. While achieving impressive performance in practice, training DNNs requires optimizing a non-convex non-concave objective function even in the case of linear activation functions and can potentially lead to local minima that are arbitrary far from global minimum. This, however, is not the typical behaviour observed in practice, as several works [Dauphin et al., 2014, Goodfellow and Vinyals, 2015] showed empirically that even in the case of training the state-of-the-art convolutional or fully-connected feedforward neural networks one does not converge to suboptimal local minima. Such a mysterious behaviour made studying the loss surface of DNNs and characterizing their local minima one of the topics of high scientific importance for the ML community. In this paper, we propose a novel approach for analyzing DNNs' behaviour by modelling them as congestion games, a popular class of games first studied by [Rosenthal, 1973] in the context of traffic routing.