Archimedes Workshop on the Foundations of Modern AI

Abstract: We revisit classical non-clairvoyant scheduling problems where the processing time of each job is not known until the job finishes. We adopt the framework of learning-augmented algorithms and we study the question of whether (possibly erroneous) predictions may help design algorithms with a competitive ratio which is good when the prediction is accurate (consistency), deteriorates gradually with respect to the prediction error (smoothness), and not too bad and bounded when the prediction is arbitrarily bad (robustness).
Short Bio: Evripidis Bampis has received his Diploma of Electrical Engineering from the National Technical University of Athens in 1989, and his Msc and PhD from the University of Paris-Sud (Orsay) in 1990 and 1993, respectively. He joined the department of Computer Science of the University of Evry (France) in September 1993, and he served as an Assistant Professor from 1993 to 1998 and then as a Professor. He was leading the Optimization and Algorithms group at the IBISC laboratory from 1998 to 2010. He was also the director of the School of Doctoral Studies. Since September 2010, he has been appointed at UPMC, now Sorbonne University, as a Professor, and he is a member of the Operations Research group of the laboratory LIP6. He served as the Director of the Department of the Master in Computer Science at Sorbonne University from 2017 to 2020. His main research interests concern the design and the analysis of algorithms for scheduling and graph problems. He is in particular interested in approximation and on-line algorithms, algorithmic game theory, and learning augmented algorithms. He was the coordinator or participant of various national, european, or international projects.

Abstract: The past decade has witnessed a surge in the development and adoption of machine learning algorithms to solve day-a-day computational tasks. Yet, a solid theoretical understanding of even the most basic tools used in practice is still lacking, as traditional statistical learning methods are unfit to deal with the modern regime in which the number of model parameters are of the same order as the quantity of data – a problem known as the curse of dimensionality. Curiously, this is precisely the regime studied by Physicists since the mid 19th century in the context of interacting many-particle systems. This connection, which was first established in the seminal work of Elisabeth Gardner and Bernard Derrida in the 80s, is the basis of a long and fruitful marriage between these two fields.
The goal of this tutorial is to provide an in-depth overview of these connections, from the early days to more recent developments. After a brief historical summary, we will introduce some useful techniques from the statistical physics toolbox through the paradigmatic study of shallow neural works, starting from their generalisation properties at initialisation (and its connection to kernel methods) to the feature learning regime after few steps of training.
Short Bio: Bruno Loureiro is currently a CNRS researcher based at the Département d’Informatique of the Ecole Normale Supérieure in Paris, working on the crossroads between machine learning and statistical mechanics. After a PhD at the University of Cambridge, he held postdoctoral positions at IPhT in Paris and EPFL in Lausanne. He is interested in Bayesian inference, theoretical machine learning and high-dimensional statistics more broadly. His research aims at understanding how data structure, optimisation algorithms and architecture design come together in successful learning.

Abstract: A hierarchical Bayesian framework is introduced for developing rich mixture models for real-valued time series, partly motivated by important applications in financial time series analysis. The model construction combines information- theoretic ideas originally developed in the context of the context-tree weighting algorithm, with standard statistical models for time series. We call the overall construction the Bayesian Context Trees State Space Model (or BCT-X) framework. Efficient algorithms are introduced that allow for effective, exact Bayesian inference, and which can be updated sequentially, facilitating effective forecasting. The utility of the general framework is illustrated on real-world financial data, where the BCT-X framework revealed novel, natural structure present, in the form of an enhanced leverage effect that had not been identified before. This is joint work with Ioannis Papageorgiou.
Short Bio: Ioannis Kontoyiannis was born in Athens, Greece, in 1972. He studied mathematics at Imperial College and Cambridge, and he received the M.S. degree in statistics, and the Ph.D. degree in electrical engineering, both from Stanford University. In 1995 he worked at IBM Research, on a NASA-IBM project. From 1998 to 2001 he was with Purdue University. Between 2000 and 2005 he was with the Division of Applied Mathematics and the Department of Computer Science at Brown University. Between 2005 and 2021 he was with the Athens University of Economics and Business. In 2009 he was a visiting professor with the Department of Statistics at Columbia University. Between 2018 and 2020 he was with the Department of Engineering of the University of Cambridge, where he was Head of the Signal Processing and Communications Laboratory. In 2020 he joined the Department of Pure Mathematics and Mathematical Statistics at the University of Cambridge, where he is the Churchill Professor of Mathematics of Information. He is a Fellow of Darwin College, Cambridge, and an Associate Member of the Signal Processing and Communications Laboratory, at the Information Engineering Division within the Department of Engineering. He has been awarded a Manning endowed assistant professorship (Brown University), a Sloan Foundation Research Fellowship, an honorary Master of Arts Degree Ad Eundem (Brown University) and a Marie Curie Fellowship. He is a Fellow of the IEEE (Institute of Electrical and Electronic Engineers), of the AAIA (Asia-Pacific Artificial Intelligence Association), and of the IMS(Institute of Mathematical Statistics).

Abstract: The notion of distortion has received much attention in recent years by the computational social choice community. In general, distortion quantifies how the lack of complete information affects the quality of the social choice outcome. Ideally, a distortion of 1 means that the social choice outcome is the most efficient one.
In the talk, we will consider two related scenarios. The first one is inspired by voting under the impartial culture assumption. We assume that agents have random values for the alternatives, drawn from a probability distribution independently for every agent-alternative pair. We explore voting rules that use a limited number of queries per agent in addition to the agent's ordinal information. For simple distributions, we present rules that always select an alternative of social welfare that is only a constant factor away from the optimal social welfare (i.e., rules of constant distortion).
The second scenario is motivated by the practice of sortition. Here, we assume that agents correspond to points on a metric space. Our objective is to select, in a fair manner, a subset of the agents (corresponding to a citizens' assembly) so that for every election with alternatives from the same metric space, the most preferred alternative of the citizens' assembly has a social cost that is very close to that of the optimal alternative for the whole agent population. Our positive results indicate that assemblies of size logarithmic in the number of alternatives are sufficient to get constant distortion in this model.
The talk is based on two papers that are joint works with Karl Fehrs, and with Evi Micha and Jannik Peters, respectively.
Short Bio: Ioannis Caragiannis (Computer Scientist and Engineer; Diploma, 1996; PhD, 2002, University of Patras, Greece) is a Professor at the Department of Computer Science of Aarhus University, Denmark, where he also serves as the Head of the research group on Computational Complexity and Game Theory. His research interests include design and analysis of algorithms (including approximation and online algorithms), economics and computation (computational aspects of fair division, voting, matching problems, auctions, and strategic games), and foundations of machine learning and artificial intelligence (including strategic aspects of learning tasks and data processing). He has more than 190 publications in conference proceedings, journals, or as book chapters. For his research, he has received the 2024 Prize in Game Theory and Computer Science in honour of Ehud Kalai, the 2022 Artificial Intelligence Journal Prominent Paper Award, and a Distinguished Paper Honorable Mention at IJCAI 2019.

Abstract: In many interactive decision-making settings, there is latent and unobserved information that remains fixed. This is in fact the case in any interactive system where the decision-maker interacts over a time horizon with another user (or system), but does not (or cannot) know everything about that user - the unknown elements make this a partially observed problem, but a special one, since they remain fixed over each interaction horizon with the same user. Thus this is one of the fundamental unsolved settings of Reinforcement Learning.
Examples of this setting abound. Consider, for example, a dialogue system, where complete information about a user (e.g., the user's preferences) is not given. Similarly, we might consider the medical treatment of a patient over a period of time, where again not everything about the patient, the patient's preferences or response to a given course of medical treatment, is known. In such an environment, the latent information remains fixed throughout each episode, since the identity of the user does not change during an interaction. This type of environment can be modeled as a Latent Markov Decision Process (LMDP). This is a special instance of Partially Observed Markov Decision Processes (POMDPs). However, as we discuss in this tutorial, in many cases of interest, using results from POMDPs typically does not work.
In this tutorial, we consider this important setting within the Reinforcement Learning paradigm. We are interested in understanding the modeling framework of LMDPs, the known information-theoretic lower bounds, and the established achievability results.
Short Bio:Constantine Caramanis is a Professor in Electrical and Computer Engineering at UT Austin. He received the Ph.D. degree in EECS from MIT. He is a recipient of a NSF CAREER award, and is an IEEE Fellow. His research interests focus on optimization, machine learning and statistics.

Abstract: This talk will introduce the model of "learning-augmented mechanism design" (or "mechanism design with predictions"), which is an alternative model for the design and analysis of mechanisms in strategic settings. Aiming to complement the traditional approach in computer science, which analyzes the performance of algorithms based on worst-case instances, recent work on "algorithms with predictions" has developed algorithms that are enhanced with machine-learned predictions regarding the optimal solution. The algorithms can use this information to guide their decisions and the goal is to achieve much stronger performance guarantees when these predictions are accurate (consistency) while also maintaining good worst-case guarantees, even if these predictions are very inaccurate (robustness). This talk will focus on the adaptation of this framework into mechanism design and provide an overview of some results along this line of work.
Short Bio: Vasilis Gkatzelis is an associate professor of computer science at the College of Computing & Informatics of Drexel University, and he is a recipient of the NSF CAREER award. Prior to joining Drexel, he held positions as a postdoctoral scholar at the computer science departments of UC Berkeley and Stanford University, and as a research fellow at the Simons Institute for the Theory of Computing. He received his PhD from the Courant Institute of New York University and his research focuses on problems in algorithmic game theory and approximation algorithms.