TL;DR
This paper introduces ACQ, a novel two-stage framework for optimizing online ad creative generation. ACQ dynamically allocates creative quotas to advertisers to maximize platform revenue by predicting ad costs and solving a large-scale allocation problem, achieving a 9.34% increase in cost.
What Problem Does This Paper Address?
In online advertising, Demand-Side Platforms (DSPs) allow advertisers to create numerous ad creatives from a single photo to increase their chances of winning bids and thus their ad spend. However, this practice creates two significant challenges for DSPs: 1) there's a limit to how many creatives can be generated and managed, and 2) the effectiveness (and thus cost) of each additional creative diminishes due to audience overlap and ad fatigue. The paper tackles the problem of automatically managing the creation and deactivation of ad creatives to maximize the ad platform's revenue, a problem that has not been adequately addressed in existing research.
Methods
ACQ employs a two-stage approach:
- Prediction Module (Unbalanced Binary Tree Model - UBTM): This module estimates the cost of a photo for a given number of ad creatives. To handle the extreme imbalance in ad cost data (where most photos have zero cost), they propose UBTM, a multi-task learning model built on an unbalanced binary tree. This model incorporates specific components to ensure monotonicity, submodularity, and smoothness in its predictions, making them more interpretable and aligned with real-world ad dynamics.
- Allocation Module (Lagrangian Dual Method with Bisection): This module formulates the problem of allocating creative quotas across advertisers as a Multiple-Choice Knapsack Problem (MCKP). To efficiently solve this large-scale problem (involving millions of ads), they relax it into a linear programming problem and then use a Lagrangian dual method combined with a binary search approach (DBSSolver) to find the optimal solution.
Datasets
The study utilizes a real-world dataset from Kuaishou's advertising intelligent delivery platform. This dataset comprises 60 million entries with sparse and dense features, including "creative cost" and "target cost." The paper does not introduce new benchmarks but uses this existing large-scale dataset for training and evaluation.
Key Insights and Ideas
- The "Diminishing Returns" of Ad Creatives: The paper highlights that simply creating more ad creatives from a single photo isn't always optimal. Beyond a certain point, the marginal increase in ad cost decreases, and managing a vast number of creatives can lead to data sparsity issues.
- Unbalanced Data is a Major Hurdle: The extreme imbalance in ad cost data (over 98% zero cost) poses a significant challenge for traditional predictive models. The UBTM's design, particularly its unbalanced binary tree structure and multi-task learning approach, is crucial for handling this.
- Interpretable Predictions Matter: By explicitly modeling properties like monotonicity and submodularity, the UBTM not only improves prediction accuracy but also makes the model's behavior more understandable, which is vital for practical applications.
- Efficient Large-Scale Optimization is Key: The allocation problem involves millions of ads. The paper's innovation lies in adapting a Lagrangian dual method with binary search (DBSSolver) to efficiently solve this complex optimization problem, outperforming standard solvers.
Key Results
- Increased Ad Cost: The ACQ framework achieved a significant increase in ad cost by 9.34% compared to a rule-based baseline in online A/B tests.
- Improved Resource Allocation: Offline experiments showed that ACQ created a similar number of creatives but increased the total expected cost, indicating more efficient budget utilization.
- Prediction Performance: The UBTM model demonstrated excellent performance across various metrics (AUC, MSE, PAUC, GAUC), outperforming standard DNN models and other specialized methods. The inclusion of monotonicity and submodularity components in UBTM improved its performance.
- Solver Efficiency: The DBSSolver was significantly more efficient than the GLPK solver for the allocation problem, solving large instances much faster while maintaining comparable solution quality.
Limitations and Future Work
- Smoothness Impact: The paper notes that incorporating smoothness constraints into the UBTM did not improve performance. They hypothesize this might be due to the relatively small number of creative bins used in their business context, leading to "mutation points" in the function.
- Future Work: While not explicitly detailed, the success of ACQ in a real-world platform like Kuaishou suggests potential for broader adoption and further refinement of the prediction and allocation modules. Exploring more sophisticated methods for handling the discretization of creative counts or investigating alternative optimization techniques could be future directions.
Summary updated