13 października 2026 11:00
[Seminarium ZOK] Yongho Shin: Optimal learning-augmented algorithm for online bidding
Recent advances in machine learning have spurred significant
interest in learning-augmented algorithms, particularly for online
optimization. A growing body of work has studied online bidding in
this framework, aiming to characterize the trade-off between
robustness and consistency. While this trade-off is fully understood
for deterministic algorithms, a gap between upper and lower bounds
remains in the randomized setting. In this work, we close this gap by
presenting a Pareto-optimal randomized learning-augmented algorithm
for this problem. Our approach introduces the notion of a bidding
profile, a novel framework for representing the distribution over bids
generated by an algorithm. We show that any bidding algorithm can be
reduced, without loss of generality, to one driven by a bidding
profile, and we characterize the optimal profile via a system of
delayed differential equations.
Joint work with Changyeol Lee (Yonsei), Dahoon Lee (NYU), Jongseo Lee
(KAIST), and Changki Yun (UMD), and will appear in NeurIPS 2026.