AI Paper Atlas

Research map / Learning theory and algorithms / Submodular and game algorithms

A Field Guide for Pacing Budget and ROS Constraints

Santiago R. Balseiro, Kshipra Bhawalkar, Zhe Feng, Haihao Lu, Vahab Mirrokni, Balasubramanian Sivan, Di Wang

ICML 2024 · Learning theory and algorithms › Submodular and game algorithms · approach: Learned auction design · 2 citations (OpenAlex)

Read the paperCheck your idea against 137,217 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Compares three decoupled/coupled pacing architectures for value-maximizing bidders under budget and ROS constraints, proving min-pacing matches dual-optimal O(sqrt T) guarantees while sequential pacing can fail linearly.

Problem

Budget pacing and ROS pacing systems are often run by different units, so bids are adjusted independently; the paper asks how decoupled (sequential or min-combined) pacing compares to fully coupled dual-based pacing for value maximizers facing budget and return-on-spend constraints.

Approach

Proposes min pacing, which takes the minimum of the ROS-pacing bid and the budget-pacing bid (each from its own dual feedback loop), and proves it achieves the same O(sqrt T) regret and constraint violation as joint dual-optimal pacing, while sequential bid-lowering can incur linear violation or regret.

Measured effects reported in the paper

What was changedWhereMeasuredEffect
Use min pacing instead of dual-optimal pacingBudget and ROS pacing · Semi-synthetic campaigns, ROS violation ≤ 0.15cumulative total value (normalized): 0.81 -> 0.86Improved
Use sequential pacing instead of dual-optimal pacingBudget and ROS pacing · Semi-synthetic campaigns, ROS violation ≤ 0.15cumulative total value (normalized): 0.81 -> 0.30Hurt
Use sequential pacing instead of dual-optimal pacingBudget and ROS pacing · Semi-synthetic campaigns, ROS violation ≤ 0.20fraction of campaigns: 0.80 -> 0.26Hurt
Use min pacing instead of dual-optimal pacingBudget and ROS pacing · Semi-synthetic campaigns, ROS violation ≤ 0.20fraction of campaigns: 0.80 -> 0.80No clear effect

Limitations

Experimental setup

Datasets: semi-synthetic dataset from online advertising platform auction data (10,000 campaigns)

Benchmarks: semi-synthetic advertising campaign dataset (10,000 campaigns)

Metrics: ROS relative constraint violation cumulative conversion value relative to fluid benchmark regret constraint violation

Baselines: dual-optimal pacing sequential pacing

Builds on: Balseiro et al. dual-based pacing Aggarwal et al. optimal auto-bidding online mirror descent

Closest papers by meaning

Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy