Session: Multiagent Optimization and Games
Chair: Songtao Lu
Cluster: Multi-agent Optimization and Games
Talk 1: A Single-Loop Algorithm for Decentralized Bilevel Optimization
Speaker: Shiqian Ma
Abstract: Bilevel optimization has gained significant attention in recent years due to its broad applications in machine learning. In this talk we focus on bilevel optimization in decentralized networks. In particular, we propose a novel single-loop algorithm for solving decentralized bilevel optimization with a strongly convex lower-level problem. Our approach is a fully single-loop method that approximates the hypergradient using only two matrix-vector multiplications per iteration. Importantly, our algorithm does not require any gradient heterogeneity assumption, distinguishing it from existing methods for decentralized bilevel optimization and federated bilevel optimization. Our analysis demonstrates that the proposed algorithm achieves the best-known convergence rate for bilevel optimization algorithms. We also present experimental results on hyperparameter optimization problems using both synthetic and MNIST datasets, which demonstrate the efficiency of our proposed algorithm.
Talk 2: Optimal No-Regret Learning in Repeated First-Price Auctions
Speaker: Zhengyuan Zhou
Abstract: First-price auctions have very recently swept the online advertising industry, replacing second-price auctions as the predominant auction mechanism on many platforms for display ads bidding. This shift has brought forth important challenges for a bidder: how should one bid in a first-price auction, where unlike in second-price auctions, it is no longer optimal to bid one's private value truthfully and hard to know the others' bidding behaviors? In this paper, we take an online learning angle and address the fundamental problem of learning to bid in repeated first-price auctions. We discuss our recent work in leveraging the special structures of the first-price auctions to design minimax optimal no-regret bidding algorithms.
Talk 3: A Primal-Dual Framework for Decentralized Bilevel Optimization
Speaker: Songtao Lu
Abstract: In this talk, I will introduce our recently proposed primal-dual framework for decentralized bilevel optimization. This framework addresses settings where multiple agents collaborate to solve nested optimization problems through neighborhood communication. While most existing approaches rely heavily on gradient tracking to manage data heterogeneity, they often overlook other effective techniques such as EXTRA or Exact Diffusion. Moreover, applying the same decentralized strategy to both the upper- and lower-level problems misses the potential of leveraging distinct methods for each level. Our unified primal-dual algorithm framework fills these gaps, allowing for the integration of various heterogeneity-correction strategies and the application of different decentralized algorithms at each level. I will present convergence results for our proposed algorithms, which achieve state-of-the-art convergence rates across all variants. Our findings also demonstrate that EXTRA and Exact Diffusion are particularly well-suited for decentralized bilevel optimization, and that combining different strategies across the bilevel hierarchy offers significant advantages over relying solely on gradient tracking.
