Seminars
Title: Zeroth-Order Methods for Convex-Concave Minmax Problems: Learning from Strategically Generated Data
Abstract: Min-max optimization is emerging as a key framework for analyzing problems of robustness to strategically and adversarially generated data. In this talk, the focus will be on a class of convex-concave min-max problems possessing a finite sum structure, and we will discuss a zero-th order variant of Optimistic Gradient Descent-Ascent (OGDA) that exploits random reshuffling to obtain fast convergence. The algorithm enjoys the same convergence rate as that of zeroth-order algorithms for convex minimization problems. This particular game structure arises in applications wherein a decision-maker seeks to minimize its empirical risk given that the data distribution it is optimizing over is dependent on its action either due to adversarial or otherwise strategic behavior. In much of the decision-dependent optimization literature, a model for the adversarial/strategic behavior is assumed known. Yet in practice, this is unrealistic. Without precise knowledge of the decision-dependence, gradient information is not readily available. Moreover, to build in robustness to model misspecification we formulate the learning problem as a distributionally robust decision-dependent risk minimization problem. Leveraging a clever transformation we show that it is possible to obtain an equivalent finite-dimensional convex-concave minmax problem. We will also demonstrate through illustrative examples how OGDA with random-reshuffling outperforms existing methods for such problems including strategic classification and prediction. The talk will be concluded with open questions and discussion on interesting directions of future work for this area.
Venue: C3.ai Digital Transformation Institute. Spring 2022 Colloquim series
Title: Decentralized, Communication- and Coordination-free Learning in Structured Matching Markets
Abstract: We study the problem of online learning in competitive settings in the context of two-sided matching markets. In particular, one side of the market, the agents, must learn about their preferences over the other side, the firms, through repeated interaction while competing with other agents for successful matches with preferred firms. We propose a class of decentralized, communication- and coordination-free algorithms that agents can use to reach their stable match in structured matching markets. In contrast to prior works, the proposed algorithms make decisions based solely on an agent’s own history of play and require no foreknowledge of the firms’ preferences. Our algorithms are constructed by splitting up the statistical problem of learning one’s preferences, via noisy observations, from the problem of competing for firms. We present two specific algorithms — one based on Upper Confidence Bounds and other based on Thompson sampling — both of which, under realistic structural assumptions on the underlying preferences of the agents and firms, incur a regret which grows at most logarithmically in the time horizon. Our results show that, in the case of matching markets, competition need not drastically affect the performance of online learning algorithms.