Learning-Augmented Online Bidding in Stochastic Settings

We are thankful to the reviewer for their constructive comments and helpful feedback.

Response to questions

1. From the upper bound point of view, the difficulty is finding the structure of optimal solutions, a task that is already difficult even with one-side stochasticity, as shown in our LP-based approach. From the lower bound point of view, the difficulty is that the proof must be based on an entire family of adversarial distributions that should be tailored to the stochastic oracle; again this task is highly complex even for one adversarial distribution, as shown in the proof of our single-prediction bound. One should also take into consideration that the competitive ratio of this problem is a constant, hence the margins for theoretical improvements are quite small. It should be emphasized that our lower bound of Section 3 shows that any improvement due to randomization quickly dissipates as $r$ increases. This implies that studying the full model will be a hard theoretical problem, but will not lead to significant improvements to our Algorithm 1, under a worst-case analysis. To make such a future study more accessible, one could start with a limited randomness model, in which the algorithm has access to only a few random bits: this limited randomness can be incorporated into the LP, at the expense of a much more complex proof approach.

Additional comments

1. Our main contribution in Section 3 is the lower bound of Theorem 13, which shows that the improvement that can be obtained from randomization becomes marginal, as $r$ increases.

2. In regards to the complexity of Algorithm 1: If $k$ is too large, then Theorem 8 shows how to reduce complexity via distributional quantization, thus obtaining improved, non-trivial runtime guarantees. We also refer to the discussion in lines 181-183. The runtime analysis in this theorem depends on the dynamic range of the distribution, but is independent of $k$.

3. There are no established real benchmarks for online bidding, hence we used synthetic data which suffice to show a large performance gap between our algorithm and state-of-the-art heuristics, considering that our Algorithm 1 is theoretically optimal on any distribution. We note that even for concrete applications that can be modeled as the online bidding problem, the experimental analysis is often based on robust synthetic data. Consider, e.g., the problem of job submissions to busy data centers, such as the Amazon AWS computing platform, which can be modeled as an application of online bidding (See point 4 in the response to Reviewer C7xM for a formal definition of the setting). In [Aupy et al, 2019], the experimental analysis is based, likewise, on synthetic data, using distributions that can adequately simulate real settings. Our aim was to obtain an algorithm of optimal performance under any current, or future stochastic oracle that may become available. This is the broader objective in the emerging subfield of learning-augmented algorithms with distributional predictions.

[Aupy et al, 2019] Aupy, Guillaume, Ana Gainaru, Valentin Honoré, Padma Raghavan, Yves Robert, and Hongyang Sun. "Reservation strategies for stochastic jobs." In 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 166-175. IEEE, 2019.

Thank you for your response! I have another question regarding the time complexity of Theorem 8.

• The consistency approximation is $e^{1/c}$.
• From the proof of Theorem 8, $\prod_{i=2}^k (j_i-j_{i-1})\leq (\frac{M}{m})^{2c\log(4C/c)}$, which implies that the time complexity is polynomial to $(\frac{M}{m})^{2c\log(4C/c)}$.
• By letting $\epsilon = e^{1/c} - 1>0$, we can see that
  • The consistency approximation is $1+\epsilon$.
  • The time complexity is polynomial to $(\frac{M}{m})^{\frac{2}{\log(1+\epsilon)}\log(4C/c)}\geq (\frac{M}{m})^{\frac{2}{\epsilon}\log(4C/c)}$, which is exponential in $\frac{1}{\epsilon}$.

I will discuss with the AC and other reviewers about that. Thank you for your response!

We are thankful to the reviewer for their constructive comments and helpful feedback.

Response to questions

1. The main challenge in Section 2 is that, unlike the deterministic setting where simple geometric strategies of the form $(\lambda b^i)_{i \geq 0}$ suffice, in the stochastic setting such strategies can be extremely inefficient even on trivial distributions. Hence one needs to search a much larger space of candidate strategies which have no obvious structure. We introduce a novel approach based on Linear Programming formulations to achieve this goal. But to do so, we need to address two technical difficulties: 1) Prune the solution space: this is achieved by using "tight" strategies as defined in (5), and by relying on Proposition 2; 2) Show necessary and sufficient conditions so as to extend a partial, finite strategy to a full, infinite strategy with robustness guarantees : this is accomplished in Lemmas 5 and 6. All these are novel approaches that have applications to other settings, such as contract scheduling with dynamic predictions and search games for a hidden target, as we show in Section 4.

2. Theorem 8 provides strict, theoretical guarantees both on the performance of the quantized algorithm and its runtime, where the latter does not depend anymore on $k$. As we note in lines 181-183, in practical settings when we expect the distributional advice to have reasonably small dynamic range (otherwise the oracle gives very inefficient information), the algorithm has provably fast runtime guarantees.

3. Figure 3 shows that even for very simple distributions over only two points, the $\zeta_2$ and $r/2$ heuristics can be as bad as almost 2-consistent, whereas our solution is 1-consistent, i.e., they are almost 100% worse than our solution. But the improvement we obtain can be much more dramatic, as we mention in lines 337-338, and as we show in Proposition 18 in the Appendix: namely as $r$ increases, the gap between these heuristics and our optimal solution is provably unbounded, even on distributions defined over two points. Hence, the two heuristics are provably very inefficient even for simple, yet adversarial data sets.

4. For a concrete application of online bidding, consider the example of job submissions to busy data centers, such as the Amazon AWS computing platform. A user submits a job to be processed by the platform, but does not know in advance how much time it will require for its completion. The user thus proposes a walltime $t$, and pays cost equal to $t$. If the job is not completed within time $t$, the user must resubmit the job with a new walltime $t'>t$, and the total cost payed by the user is the sum of all walltimes until the job is finally completed. How should the user decide the sequence of submitted walltimes so as to minimize the ratio between the cost it pays, and the optimal cost that would be paid if the required time was known to the user in advance? This is precisely the formulation of online bidding, and it is at the core of scheduling problems in cloud computing, see for example [Aupy et al, 2019] .

We will add a discussion of this application, as an example of the many applications we already mentioned in lines 32-37 and Section 4 (that is, interruptible systems, search problems, incremental clustering etc).

[Aupy et al, 2019] Aupy, Guillaume, Ana Gainaru, Valentin Honoré, Padma Raghavan, Yves Robert, and Hongyang Sun. "Reservation strategies for stochastic jobs." In 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 166-175. IEEE, 2019.

We are thankful to the reviewer for their constructive comments and helpful feedback.

Response to questions

1. Brittleness is mainly a byproduct of "single-point" prediction oracles, combined with deterministic algorithms and deterministic analysis. In stochastic settings, brittleness intuitively is much less of an issue, as was shown formally in [20]. Notwithstanding this observation, there are various ways we can enhance Algorithm 1 to make it more robust to prediction errors. First, note that we can detect a potentially brittle solution by observing whether any of the bids is very close to one of the $k$ probability masses. Then we can rerun the algorithm using one of the following two approaches: either based on a "tolerance" parameter $\delta$, in which each of the $k$ "critical" bids must be at least a function of $\delta$ larger than the corresponding $\mu_i$ (this action can be encoded in the LP); or by introducing some randomized "perturbation" of the solution, and specifically of the size of the $k$ critical bids, along the lines of [20]. In what concerns the randomized setting, the strategy of Theorem 10 is inherently more robust to brittleness thanks to randomization.

   Furthermore, in regards to error measures, one may be able to obtain an EMD-based analysis, by generalizing the approach of [7], which studied the contract scheduling problem with distributional predictions for robustness $r=4$. But to obtain a general result for Pareto-optimal algorithms will require some realistic assumptions on the distribution (e.g., that is has continuous, smooth and bounded density). Otherwise, we know from [7] that any Pareto-optimal algorithm is brittle against single-point predictions, and also against single-point distributional predictions with very small error (measured by the EMD).

2. Considering that our algorithm is guaranteed to be optimal on all distributions, our goal was to evaluate it, in comparison to known baselines, on distributions that do not need to be overly complex. As shown in the experiments, even a relatively small value such as $k = 4$ allows us to draw very useful conclusions about the comparative performance of all algorithms.

3. Compared to previous work that focused on deterministic models and algorithms, our main novel technical ideas are as follows:

• For distributional predictions (Section 2): The main challenge in Section 2 is that, unlike the deterministic setting where simple geometric strategies of the form $(\lambda b^i)_i$ suffice, in the stochastic setting such strategies can be extremely inefficient even on trivial distributions. Hence one needs to search a much larger space of candidate strategies which have no obvious structure. We introduce a novel approach based on Linear Programming formulations to achieve this goal. But to do so, we need to address two other technical points: 1) Prune the solution space: this is achieved by using "tight" strategies as defined in (5), and by relying on Proposition 2; 2) Show necessary and sufficient conditions so as to extend a partial, finite strategy to a full, infinite strategy with robustness guarantees : this is accomplished in Lemmas 5 and 6. All these are novel approaches that have applications in other settings such as contract scheduling with dynamic predictions and search games for a hidden target, as we show in Section 4.

• For randomized algorithms (Section 3), the main challenge is the lower bound for two reasons: First, Yao’s principle (the main tool for randomized lower bounds) does not immediately apply, since we have two objectives in a tradeoff relation; Second, while deterministic $r$-robust strategies have a very clear characterization and known properties from previous work, there is no known characterization of the structure of randomized $r$-robust strategies. We introduce two novel ideas: A lower bound on a linear combination of the objectives ($rob+\lambda \cdot cons$), in Theorem 12, which allows us to give lower bounds on the trade-off between the two objectives; and an explicit, adversarial target distribution that allows us to properly quantify both consistency and robustness. In contrast, past work on randomized bidding without prediction used a very complex approach based on LP duality [26] which cannot incorporate predictions in any obvious way. Last, concerning the upper bound of Theorem 10, the novelty is to trade randomness for variability in performance: this allows us to obtain actual consistency/robustness tradeoffs, whereas with full randomness an algorithm has the same performance across all targets, and cannot use the prediction to the benefit of the consistency.

Thank you to the authors for their reply, and in particular for their helpful and interesting comments on the brittleness of the algorithm.

We are thankful to the reviewer for their constructive comments and helpful feedback.

Response to questions

1. It may indeed be possible to obtain such guarantees via an EMD-based analysis, by generalizing the approach of [7], which studied the contract scheduling problem with distributional predictions for robustness $r=4$. But to obtain a general, theoretical result for Pareto-optimal algorithms will require some realistic assumptions on the distribution (e.g., that is has continuous, smooth and bounded density). Otherwise, we know from [7] that any Pareto-optimal algorithm is brittle against single-point predictions, and also against single-point distributional predictions with very small error (measured by the EMD). While this is an interesting theoretical problem, we should note that the consistency/robustness tradeoffs that one obtains from distributional prediction analysis are much more robust, in practice, than single-point oracles and "deterministic" analysis.

Concerning the future study of an extension with double-sided stochasticity, there are several challenges. From the upper bound point of view, the difficulty is finding the structure of optimal solutions, a task that is already difficult even with one-side stochasticity, as shown in our LP-based approach. From the lower bound point of view, the difficulty is that the proof must be based on an entire family of adversarial distributions that should be tailored to the stochastic oracle; again this task is highly complex even for one adversarial distribution, as shown in the proof of our single-prediction bound. But in the context of our lower bound of Theorem 13, any improvement due to randomization quickly dissipates as $r$ increases. This implies that studying the full model will be a hard theoretical problem, but will not lead to significant improvements to our Algorithm 1, under a worst-case analysis. To make such a future study more accessible, one could start with a limited randomness model, in which the algorithm has access to only a few random bits: this limited randomness can be incorporated into the LP, at the expense of a much more complex proof approach.