The Milonga Tango Night is a popular social event in Buenos Aires, Argentina, where tango enthusiasts gather to dance, socialize, and enjoy live music. However, attending a Milonga Tango Night presents a dilemma: how can individuals balance their desire for an enjoyable evening with the potential negative consequences of overcrowding the dance floor and diminishing the experience for everyone?
In this presentation, we will explore the dynamics of this problem, also known as the El Farol Bar Problem in game theory, and the various strategies that individuals might use to decide whether or not to attend. These strategies can range from following the crowd to adopting a contrarian approach. We will analyze how these strategies can lead to either beneficial or detrimental outcomes for the group as a whole and explain why such settings exhibit Li-Yorke chaos under certain conditions. Li-Yorke chaos means that the behavior of the agents' system is unpredictable and sensitive to small changes in the initial conditions.
Finally, by studying such coordination problems in the context of machine learning, we aim to gain new insights into the modern challenges of designing and optimizing large multi-agent reinforcement learning systems, where each agent (dancer) is part of a multi-agent reinforcement learning system trying to maximize their reward (enjoyment) while avoiding intrinsic penalties (crowding).

Back in the day, machine learning problems were a drag. Either classification or data-generation, the main tasks of artificial intelligence, had been classified as computationally hard problems. Decades later, with subsequent computing innovation, machines have transformed into their ultra-smart, self-learning, automated versions that are sweeping the human landscape. This unreasonable effectiveness of modern machine learning algorithms has thrown down the gauntlet to algorithms researchers, and there is perhaps no other problem domain with a more urgent need for the beyond worst-case approach. In this talk, we will discuss a series of recent results in the area of Local Search, Continuous Optimization and Game Dynamics.

Motivated by recent advances in both theoretical and applied aspects of multiplayer games, spanning from e-sports to multi-agent generative adversarial networks, we focus on min-max optimization in team zero-sum games. In this class of games, players are split into two teams with payoffs equal within the same team and of opposite sign across the opponent team. Unlike the textbook two-player zero-sum games, finding a Nash equilibrium in our class can be shown to be CLS-hard, i.e., it is unlikely to have a polynomial-time algorithm for computing Nash equilibria. Moreover, in this generalized framework, we establish that even asymptotic last iterate or time average convergence to a Nash Equilibrium is not possible using Gradient Descent Ascent (GDA), its optimistic variant, and extra gradient. Specifically, we present a family of team games whose induced utility is \emph{non} multi-linear with \emph{non} attractive \emph{per-se} mixed Nash Equilibria, as strict saddle points of the underlying optimization landscape. Leveraging techniques from control theory, we complement these negative results by designing a modified GDA that converges locally to Nash equilibria. Finally, we discuss connections of our framework with AI architectures with team competition structures like multi-agent generative adversarial networks.

Motivated by recent advances in both theoretical and applied aspects of multiplayer games, spanning from e-sports to multi-agent generative adversarial networks, a surge of different studies has been focused on the core problem of understanding the behavior of game dynamics in general N-player games. From the seminal settings of two competitive players and Min-Max Optimization to the complete understanding of how the day-to-day behavior of the dynamics correlates to the game’s different notion of equilibria is much more limited, and only partial results are known for certain classes of games (such as zero-sum or congestion games).
In this talk, we study from two different perspectives arguably the most well-studied class of no-regret dynamics, “Follow-the-regularized-leader” (FTRL) and Discretizations of Gradient Flow (GDA/OGDA/EG), and we establish a sweeping negative result showing that the notion of mixed Nash equilibrium is antithetical to no-regret learning. Specifically, we show that any Nash equilibrium which is not strict (in that every player has a unique best response) cannot be stable and attracting under the dynamics of FTGL. This result has significant implications for predicting the outcome of a learning process as it shows unequivocally that only strict (and hence, pure) Nash equilibria can emerge as stable limit points thereof.
For a final happy end story, we present either structural examples of families where convergence is possible providing the last-iterate convergence rates or even new methods inspired from other areas like control theory & planning.

Abstract: Understanding the Nash equilibrium convergence properties of no-regret learning in general N-player games is a fundamental question in online learning and game theory. In this talk, we focus on the archetypal “follow the regularized leader” (FTRL) family of algorithms, and we consider a wide spectrum of uncertainty that the players may encounter - from noisy, oracle-based feedback,to bandit, payoff-based information.
We present a succinct equivalence between the stability of a Nash equilibrium and its support: A Nash equilibrium is stable and attracting with arbitrarily high probability if and only if it is strictly pure (i.e., each equilibrium strategy has a unique best response).

Abstract: We show that the smoothed complexity of the FLIP algorithm for local Max-Cut is at most ϕn^O(√logn), where n is the number of nodes in the graph and ϕ is a parameter that measures the magnitude of perturbations applied on its edge weights. This improves the previously best upper bound of ϕn^O(logn) by Etscheid and Röglin. Our result is based on an analysis of long sequences of flips, which shows that it is very unlikely for every flip in a long sequence to incur a positive but small improvement in the cut weight. We also extend the same upper bound on the smoothed complexity of FLIP to all binary Maximum Constraint Satisfaction Problems

Abstract: Understanding the behavior of no-regret dynamics in general N-player games is a fundamental question in online learning and game theory. A folk result in the field states that, in finite games, the empirical frequency of play under no-regret learning converges to the game’s set of coarse correlated equilibria. By contrast, our understanding of how the day-to-day behavior of the dynamics correlates to the game’s Nash equilibria is much more limited, and only partial results are known for certain classes of games (such as zero-sum or congestion games). In this paper, we study the dynamics of follow the regularized leader (FTRL), arguably the most well-studied class of no-regret dynamics, and we establish a sweeping negative result showing that the notion of mixed Nash equilibrium is antithetical to no-regret learning. Specifically, we show that any Nash equilibrium which is not strict (in that every player has a unique best response) cannot be stable and attracting under the dynamics of FTRL. This result has significant implications for predicting the outcome of a learning process as it shows unequivocally that only strict (and hence, pure) Nash equilibria can emerge as stable limit points thereof.

Abstract: We study the fundamental task of estimating the median of an underlying distribution from a finite number of samples, under pure differential privacy constraints. We focus on distributions satisfying the minimal assumption that they have a positive density at a small neighborhood around the median. In particular, the distribution is allowed to output unbounded values and is not required to have finite moments. We compute the exact, up-to-constant terms, statistical rate of estimation for the median by providing nearly-tight upper and lower bounds. Furthermore, we design a polynomial-time differentially private algorithm which provably achieves the optimal performance. At a technical level, our results leverage a LipschitzExtension Lemma which allows us to design and analyze differentially private algorithms solely on appropriately defined “typical” instances of the samples.

Abstract: Greece, a nation that has been the cradle of Western civilization, has in recent years faced a significant challenge: the emigration of its skilled and educated young professionals, commonly referred to as 'brain drain'. This phenomenon has profound implications for the nation's socioeconomic growth, sustainability, and cultural preservation. However, the solution may lie in a realm previously underemphasized in traditional educational systems – the cultivation of soft skills, the mastery of the art of learning, and the nurturing of imagination from a young age.

Abstract: Amidst the COVID-19 crisis, the dynamics of societal responses have been under the spotlight. The established rationalism of science, which promotes evidence-based understanding and decision-making, has been increasingly confronted by the proliferation of conspiracy theories. This juxtaposition stems from the inherent difficulty humans face in managing uncertainty. As the pandemic ushered in unprecedented challenges and ambiguous scenarios, many sought explanations that offered simpler, albeit often misleading, narratives. Conspiracy theories, which tend to provide clear-cut culprits and reasons, catered to this psychological need. Consequently, this scenario underscores the tension between scientific rationalism and the innate human desire for certainty amidst chaos. It is a reminder of the critical role of education, transparent communication, and trust in institutions in navigating such crises..

In this episode, we dive deep into the crossroads of culture and academia, juxtaposing the vibrant history of Greece with the prestigious corridors of Columbia University. Our guest, a proud Greek and Columbia PhD alumni, shares their unique journey, shedding light on the challenges, triumphs, and learnings they encountered along the way. How does one's Hellenic roots influence the pursuit of knowledge in the heart of New York City? From the ancient philosophies of Greece to the modern classrooms of Columbia, join us for a rich discussion on the global odyssey of academic pursuit. Discover the intertwining narratives of heritage, identity, and scholarly adventure..

Abstract: The fusion of Quantum Technology (QT) and Machine Learning (ML) is poised to revolutionize our world in the coming years. Dubbed as Quantum Technology and Machine Learning (QTML), this groundbreaking synergy promises advancements that were once the realm of science fiction. QTML is not just an academic curiosity; it's a gateway to unprecedented computational capabilities, tackling complex problems ranging from climate modeling to drug discovery. As QTML evolves, it will redefine industries, enhance artificial intelligence, and potentially reshape our daily lives with solutions that are faster, more efficient, and previously unimaginable. The next 5 to 6 years could witness the dawn of a new era where QTML's influence extends beyond laboratories, directly impacting society in transformative ways.

Abstract: As we approach 2024, the landscape of Artificial Intelligence (AI) faces both unprecedented opportunities and challenges, particularly in the context of Greek academia. This discussion delves into the critical issues of AI development and application, exploring how evolving legislation around university privatization in Greece could impact innovation and research. We examine the potential implications for academic freedom, commercial partnerships, and the broader societal and ethical considerations of AI in a changing educational environment. This conversation aims to shed light on the complex interplay between technology, policy, and education, providing insights into the future of AI and its role in shaping Greek academia and society at large.