Analysis of the Alternating Mirror Descent for Constrained Min-Max Games

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=cJ5svEUAf8E


Duration: 1:00:30
783 views
13

Andre Wibisono (Yale University)
https://simons.berkeley.edu/talks/tbd-372
Learning in the Presence of Strategic Behavior

We study the alternating mirror descent algorithm for a two-player constrained bilinear zero-sum game. We highlight the connection between alternating mirror descent as a symplectic discretization of a Hamiltonian flow in the dual space. We show a regret bound for alternating mirror descent under decreasing step size. We also study when we can show a regret bound with constant step size, similar to the unconstrained case (alternating gradient descent).



Other Videos By Simons Institute for the Theory of Computing


2022-04-06Panel | Quantum Colloquium
2022-04-06On the Limits for Certifying Quantum Speedups for Noisy Circuits | Quantum Colloquium
2022-04-02Inference on Auctions with Weak Assumptions on Information
2022-04-02Reinforcement Learning for Complex Security Games and Beyond
2022-04-02Communicating with Anecdotes
2022-04-01The Invisible Hand of Prediction
2022-04-01How (Not) to Run a Forecasting Competition: Incentives and Efficiency
2022-04-01The Challenge of Understanding What Users Want: Inconsistent Preferences and Engagement Optimization
2022-04-01Learning, Incentivizing Improvement, and Fairness in the Presence of Strategic Agents
2022-03-31The Transfer Performance of Economic Models
2022-03-31Analysis of the Alternating Mirror Descent for Constrained Min-Max Games
2022-03-31In Praise of Game Dynamics
2022-03-31Experimental Evidence of Individual Human Learning in Games
2022-03-30Aggregating Conflicting Forecasts
2022-03-30Beyond Open Loop Algorithm Design: Learning from Decision-Dependent Data
2022-03-30Predicting Cooperation Rates With A Learning Model
2022-03-30Optimal No-Regret Learning in General Games via Clairvoyant MWU
2022-03-29Forecast Hedging, Calibration, And Game Equilibria
2022-03-29Mechanisms To Procure Information Without Verification
2022-03-29Identification Analysis In Models With Set Valued Predictions
2022-03-29What Does It Take To Be a Good Fisherman?


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Learning in the Presence of Strategic Behavior
Andre Wibisono