Summary
This paper considers the online display ads and generalized assignment problems under free disposal in the "algorithms with predictions setting". In the display ads problem there are offline advertisers $a$ with budgets $B_a$. A sequence of impressions arrive online with differing values to each advertiser (impression $t$ has value $w_{at}$ to advertiser $a$). The algorithm must either allocate each impression to an advertiser, earning its value and consuming one unit of the advertiser's capacity, or reject the impression entirely. Decisions are made irrevocably, but in the free disposal model the algorithm may assign more impressions to an advertiser than their capacity allows but the algorithm only gains the value of the most valuable impressions that fit within the capacity. The generalized assignment problem generalizes the display ads problem by allowing impression $t$ to instead consume $u_{at}$ units of advertiser $a$'s capacity.
In the "algorithms with predictions" setting the online algorithm also has access to potentially noisy predictions about the optimal solution. In particular, this paper assumes that the algorithm may access a prediction $PRD(t)$ when impression $t$ arrives which gives a hint about which advertiser to allocate impression $t$ to in an optimal solution in hindsight. The prediction may be incorrect, so two quantities are analyzed: consistency and robustness. Consistency is given by the worst-case ratio of $ALG/PRD$, where $ALG$ is the algorithms solution quality and $PRD$ is the predictions solution quality. Robustness is given by the worst -case ratio of $ALG/OPT$, where $OPT$ is the optimal solution in hindsight.
Theoretically, this paper gives algorithms with non-trivial tradeoffs between robustness and consistency. The algorithm is based off of the primal-dual algorithm used by Feldman et al. 2009, but modified to account for the predictions. Proving their consistency bound needed new techniques since a local analysis as is typically used in the primal-dual method is insufficient here.
The authors complement the theoretical results with an experimental analysis on both real and synthetic data of their proposed algorithm using various predictions as input. The experiments compare to the worst-case baseline of Feldman et al. 2009 and the simple random-mixture algorithm they discuss in the introduction.
Strengths
This paper considers online allocation problems motivated by advertising applications in the algorithms with predictions setting. Prior work has considered related problems in this setting. This paper considers more general versions of these problems and also considers the free-disposal setting, which has not yet been considered in the algorithms with predictions literature. The paper gives strong theoretical guarantees for their algorithm and complements this with a thorough experimental analysis.
Weaknesses
- Some of the presentation of the results in the experiment section could be clarified/improved. See comments/questions below.
- The improvement over the worst-case baseline using "more realistic" predictions is somewhat narrow (although in practice this smaller improvement could matter in some cases).
- Theoretically, it is not clear if the trade-off between robustness and consistency is tight. Giving tight guarantees has become of interest recently, see the two references below:
- Wei, A., Zhang, F., "Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms." NeurIPS 2020.
- Jin, B., Ma, W., "Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model." NeurIPS 2022. (this paper may also be good to discuss in the related work).
Questions
## Questions
- Can you
- Please clarify what is meant by "prediction competitiveness" in the plots in Figure 4.
- What was observed experimentally for the competitive ratio of the worst case baseline?
- In Figures 3 and 5 the average competitive ratio across 5 trials is reported in parentheses for different predictors. Since there is a hypereparameter $\alpha$ that is varied can you clarify which value of $\alpha$ was used to produce these numbers?
## Comments
- For the plots in figure 2, it might be helpful to visually compare with the consistency/robustness guarantees that would be guaranteed by the random-mixture algorithm as well as the algorithm due to Mahdian et al. 2007.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Limitations
I believe the authors have adequately addressed potential limitations and there is not a high potential for negative societal impacts from this work.