December 6, 2023December 6, 2023 by alkhwarizmi

Zaïneb Bel Afia

Uncategorized

$\begin{quote} \begin{center} \textbf{Chebyshev varieties} \end{center} Chebyshev varieties are algebraic varieties parametrized by Chebyshev polynomials. They arise when solving polynomial equations expressed in the Chebyshev basis. Chebyshev polynomials are widely used in optimization and numerical analysis, and their analytic aspects have been studied intensively. On the other hand, their algebraic properties remain relatively unexplored. This talk aims to bridge this gap. I will discuss defining equations of Chebyshev varieties and give some key properties. Through examples, I will motivate their use in effective computations. This is ongoing work with Chiara Meroni (Harvard University) and Simon Telen (MPI MiS). \end{quote}$

December 6, 2023December 6, 2023 by alkhwarizmi

Ziva Urbancic

Uncategorized

$\begin{quote} \begin{center} \textbf{Morphism Induced Matchings between Persistence Barcodes} \end{center} \medskip The output of persistent homology is an algebraic object called a persistence module. This object admits a decomposition into a direct sum of interval persistence modules described entirely by the barcode invariant. We often equate an interval in the barcode with a topological feature of the input space. In this talk, we will describe some methods for comparing barcodes belonging to related persistence modules. In particular, we will consider cases when there is a morphism between the involved persistence modules that associates topological features in the respective input spaces. \end{quote}$

December 6, 2023December 6, 2023 by alkhwarizmi

Reda Ouhemma

Uncategorized

$\begin{quote} \begin{center} \textbf{Finite-time Convergence for Decentralized Payoff-based Two-Player Zero-Sum Markov Games under weak reachability assumptions} \end{center} \medskip We consider decentralized learning for two-player zero-sum Markov games, where players have limited feedback in the form of their own payoff information without knowledge of each other's actions. Convergence to a Nash equilibrium in this setting was proven under strong reachability assumptions, namely that the induced Markov chain of any stationary policy pair is irreducible and aperiodic. It remained an open problem whether, under weaker assumptions, it would be possible to achieve an approximate Nash equilibrium efficiently. In this work, we answer this question positively and present a value-iteration-based algorithm with a Tsallis-entropy smoothing that can learn an approximate Nash equilibrium in polynomial time. Our method requires only the existence of a policy pair that induces an irreducible and aperiodic Markov chain, a considerably weaker assumption compared to previous literature. Our analysis utilizes Lyapunov drift inequalities and novel properties of Tsallis entropy that we believe to be of independent interest. \end{quote}$

December 6, 2023December 6, 2023 by alkhwarizmi

Achour El Mehdi

Uncategorized

$\begin{quote} \begin{center} \textbf{The loss landscape of deep linear neural networks: a second-order analysis} \end{center} \medskip We study the optimization landscape of deep linear neural networks with the square loss. It is known that, under weak assumptions, there are no spurious local minima and no local maxima. However, the existence and diversity of non-strict saddle points, which can play a role in first-order algorithms' dynamics, have only been lightly studied. We go a step further with a full analysis of the optimization landscape at order $2$. We characterize, among all critical points, which are global minimizers, strict saddle points, and non-strict saddle points. We enumerate all the associated critical values. The characterization is simple, involves conditions on the ranks of partial matrix products, and sheds some light on global convergence or implicit regularization that have been proved or observed when optimizing linear neural networks. In passing, we provide an explicit parameterization of the set of all global minimizers and exhibit large sets of strict and non-strict saddle points. \end{quote}$

December 6, 2023December 6, 2023 by alkhwarizmi

Rida Laraki

Uncategorized

$\begin{quote} \begin{center} \textbf{Online Learning in Identical-Interest and Zero-Sum Discounted Stochastic Games} \end{center} \medskip This presentation combines two recent articles where we extend a popular decentralized discrete-time learning procedure called fictitious play (Brown, 1951; Robinson, 1951) to discounted stochastic games (Shapley, 1953). We prove the convergence of our online learning algorithms to the set of stationary Nash equilibria in identical-interest and zero-sum discounted stochastic games. The two articles in question are: \smallskip \begin{itemize} \item[1] Lucas Baudin and Rida Laraki, ``Fictitious Play and Best-Response Dynamics in Identical Interest and Zero-Sum Stochastic Games", \textit{Proceedings of the 39th International Conference on Machine Learning}, PMLR 162:1664-1690, 2022. \smallskip \item[2] Lucas Baudin and Rida Laraki. ``Smooth Fictitious Play in Stochastic Games with Perturbed Payoffs and Unknown Transitions." \textit{Advances in Neural Information Processing Systems} 35 (2022): 20243-20256. \end{itemize} \end{quote}$

December 6, 2023December 6, 2023 by alkhwarizmi

Ali Aouad

Uncategorized

$\begin{quote} \begin{center} \textbf{A nonparametric framework for online stochastic matching with correlated arrivals} \end{center} \medskip Matching decisions are important operational controls for online marketplaces, with applications including order fulfillment, ride-hailing, and service platforms. Existing stochastic models often rely on an assumption of ``serial independence" which implies that demand is approximately Poisson-distributed and low-variance. By relaxing this assumption, we develop a nonparametric framework for online matching that can represent high-variance and correlated arrivals, which are prevalent in real-world demand predictions. Specifically, we propose models that combine a nonparametric distribution for the demand with standard assumptions on the arrival patterns -adversarial or random-order. We demonstrate that fluid relaxations, which rely solely on expected demand information, have arbitrarily bad performance guarantees. Instead, we propose tighter linear programming relaxations that leverage distribution knowledge and use a novel rounding scheme to obtain matching algorithms that achieve optimal (worst-case) performance guarantees. This is joint work with Will Ma (Columbia GSB), and ongoing work with Weizhong Zhang (Tepper, CMU) \end{quote}$

December 6, 2023December 6, 2023 by alkhwarizmi

Omar El Housni

Uncategorized

$\begin{quote} \begin{center} \textbf{Joint Inventory Optimization and Assortment Personalization} \end{center} \medskip In this talk, we give approximation algorithms for a joint inventory allocation and assortment personalization problem motivated by an online retail setting. In our problem, we have a limited amount of storage capacity that needs to be allocated among multiple products to serve customers that arrive over a selling horizon. At the beginning of the selling horizon, we decide how many units of each product to stock. Over the selling horizon, customers arrive at the platform one by one to make a purchase. Based on the remaining inventories of the products and the information available on the arriving customer, we offer a personalized assortment of products to each customer. The customer either makes a choice within the offered assortment or leaves without a purchase. Our goal is to decide how many units of each product to stock at the beginning of the selling horizon and to find a policy to figure out which personalized assortment to offer to each arriving customer to maximize the total expected revenue over the selling horizon. Allocating the storage capacity among the products requires tackling a combinatorial optimization problem, whereas finding an assortment personalization policy requires approximating a dynamic program with a high-dimensional state variable. We develop an algorithmic approximation framework that gives the first theoretical guarantees for this class of problems. Our framework builds on techniques from submodular optimization and dynamic programming. \end{quote}$

December 6, 2023December 6, 2023 by alkhwarizmi

Mohammed Ndaoud

Uncategorized

$\begin{quote} \begin{center} \textbf{A gentle introduction to robust mean estimation} \end{center} \medskip During this talk we will cover the topic of robust mean estimation under the existence of finite variance. We will first review the existing literature around some classical robust estimators including the median of means (MOM) and the trimmed mean estimators . We will then present a new estimator of the mean that is robust and enjoys some features that were lacking in the previous ones. \end{quote}$

December 6, 2023December 10, 2023 by alkhwarizmi

Stéphane Gaubert

Uncategorized

$\begin{quote} \begin{center} \textbf{Nonnegative tensors, games of entropy, and geometric programming} \end{center} \medskip We show that the logarithm of the spectral radius of a nonnegative tensor can be represented as the value of a stochastic control problem, in which one player maximizes a relative entropy. This is related to generalizations of inequalities of Donsker-Varadhan, Friedland-Karlin, and Karlin-Ost. Then, computing the spectral radius of a nonnegative tensor turns out to be a special case of a general geometric programming problem, consisting in minimizing the maximum of finitely many log-Laplace transforms of nonnegative measures with finite supports. We show that an approximate solution of this problem can be obtained in polynomial time in the bit-model of computation, the complexity being controlled by a condition number depending on the geometry of the support sets. This entails the polynomial-time approximability of the spectral radius. We also discuss another application, to the class of entropy games, in which two players wish to maximize or minimize a topological entropy. The results on geometric programming and nonnegative tensors are from a joint work with Shmuel Friedland. The application to entropy games is from a joint work with Marianne Akian, Julien Grand-Clément and Jérémie Guillaud. \end{quote}$

December 6, 2023December 6, 2023 by alkhwarizmi

Irem Portakal

Uncategorized

$\begin{quote} \begin{center} \textbf{Game Theory of undirected graphical models} \end{center} \medskip Game theory is an area that has historically benefited greatly from outside ideas. In 1950, Nash published a very influential two-page paper proving the existence of Nash equilibria for any finite game. The proof uses an elegant application of the Kakutani fixed-point theorem from the field of topology. This opened a new horizon not only in game theory, but also in areas such as economics, computer science, evolutionary biology, and social sciences. In this talk, we model different notions of equilibria in terms of undirected graphical models.The vertices of the underlying graph of the graphical model represent the players of the game and the dependencies of the choices of the players are depicted with an edge in the graph.This approach brings game theory in contact with the field of algebraic statistics for the first time, which offers a strong foundation for utilizing algebro-geometric tools to solve interesting problems in game theory. This is joint work with Javier Sendra-Arranz and Bernd Sturmfels. \end{quote}$