서울대학교SSK사업단(사회과학 연구지원 사업 - AI 시대의 사회기술적 전환: 인간 전문성과 알고리즘을 잇는 협력적 의사결정 체계 설계와 정책 연구)에서 아래와 같이 해외 연사 초청 세미나를 개최합니다. 

관심 있는 분들의 많은 참여를 부탁드립니다.

 

일시: 2026년 3월 16일 (월) 13시30분 - 15시

장소: 59동 304호

발표자: Professor Yehua Wei (Duke University - Fuqua School of Business)

 

Title: Constant Regret Primal-Dual Algorithm in Dynamic Optimization

 

The primal–dual algorithm is a class of popular policies in dynamic optimization, valued for its simplicity, interpretability, and robustness across a wide range of applications. The intuition of the primal-dual algorithm is straightforward: in each period, the primal control decisions are guided by a set of dual variables that relax a set of key constraints, and these dual variables are updated dynamically based on past decisions and unfolding uncertainty. The classical studies of primal-dual algorithms typically has the dual variables initialized at an arbitrary point, leading to a regret that grows with the horizon length, T, that scales with either o(T) or o(\sqrt{T}), depending on the step-size of the dual update. In this talk, we show that we can significantly improve the regret with a simple yet powerful idea. When the dual variables are initialized at the optimal Lagrangian dual solution, then under a stability condition on the Lagrangian dual problem, the primal-dual algorithm would naturally create a negative drift that drives the primal solutions toward feasibility, where the strength of the drift is independent of the stepsize of the dual update. As a result, the regret bound collapses to a constant that is independent of T when the step-size of the dual update is chosen to be small. We show that this idea is applicable to the classical dynamic matching and online resource allocation problems. It also leads to new regret bounds for more challenging variations of these problems, including dynamic matching with unknown arrival rates.

 

주최: 서울대학교SSK사업단(사회과학 연구지원 사업 - AI 시대의 사회기술적 전환: 인간 전문성과 알고리즘을 잇는 협력적 의사결정 체계 설계와 정책 연구); 연구책임자: 임재현 (서울대학교)