Online Prediction with Limited Selectivity

Thank you for your review! We agree that the empirical evaluation of our methods on synthetic or real sequences as well as the empirical illustration of our error bounds are important directions that would further add to our theory. We restrict the scope of this work to the theoretical aspect of PLS for its conceptual simplicity and the new theoretical insights that it might contribute to selective prediction and online prediction in general. We also note that many prior work on or related to selective prediction (e.g., [Drucker13, Feige15, FKT17, QV19] in Section 1.3) were also purely theoretical.

Thank you for your review!

Regarding your comment on the intuition behind the hard instances, it would be the most informative to follow the proof of Theorem 9 on the instance with geometrically increasing block lengths (i.e., $\mathcal{L} = (1, 2, 4, 8, \ldots)$). Suppose that the nature chooses a random sequence $x$ by setting the bits within each block to either $0$ or $1$ with equal probability, and the choices for different blocks are independent. Then, since the forecaster is only allowed to predict when a block ends, the prediction window must consists of several consecutive blocks, say, $(2^3, 2^4, \ldots, 2^{10})$. Since $2^{10} > 2^3 + 2^4 + \cdots + 2^9$, the last block constitutes more than half of the prediction window. It follows that the randomness of the last block alone contributes an $\Omega(1)$ amount to the variance of the average to be predicted. Therefore, no forecaster can achieve a sub-constant error on this instance.

Regarding your comment on Section 5, our discussion in Appendix E suggests that a sharper complexity measure should not only account for the number of approximately uniform blocks that can be obtained via merging consecutive blocks, but also allow "skipping" some shorter blocks at the cost of an additional term in the prediction error. We appreciate your suggestion and will expand this discussion in the revision.

We answer your questions in the following:

1. Here is a concrete example of the greedy procedure in Lemma 8: Suppose that we are given a block length sequence $L = (2, 1, 3, 4, 1, 1, 5, 1)$, and wish to merge it under a ratio bound $C = 2$.

   The maximum block length is $M = 5$, so the threshold for merging is: $T = M / (C - 1) = 5$. We now run the greedy merging algorithm:

   • Starting at index $1$, we merge the subsequence $(2, 1, 3)$ that has a total length $6 > 5$. We create a merged block of length $l'_1 = 6$.

   • We continue at index $4$: Merging $(4, 1)$ gives a total length of $l'_2 = 5$.

   • Starting at index $6$, we merge $(1, 5)$ to obtain a total length of $l'_3 = 6$.

   • Now we are at index $7$, and the remaining total length (i.e., $1$) is not enough to form a new block of length $\ge 5$, so we stop here.

   The resulting merged sequence is $L' = (6, 5, 6)$, where each merged block length lies in the interval $[T, T + M] = [5, 10]$. The resulting ratio between block lengths also satisfies $(\max l'_j) / (\min l'_j) = 6 / 5 < 2 = C$.

2. Thank you for this thoughtful observation! Yes, the ternary tree structure in Definition 7 is closely tied to the structure of the lower bound proof. Roughly speaking, the goal of our decomposition is to ensure that, at every split, the total block lengths are divided evenly. When the block lengths are the same (i.e., the setting of [Qiao and Valiant, COLT'19]), doing so is easy. When the lengths can be different, the issue arises when one of the blocks constitutes the vast majority (say, 99.99%) of the total block lengths. In this case, we need to allow a third child that only corresponds to this long block, and use the other two children for the two intervals obtained after removing this long block.

3. The $k$-monotonicity assumption is a natural way of interpolating between monotone (i.e., $k = 1$) and arbitrary (i.e., $k = n$) sequences. From a practical perspective, it includes all sequences obtained from concatenating $k$ constant sequences, and naturally models scenarios in which the underlying inclusion probability changes periodically (e.g., with a different value for each month / season / year). From a theoretical perspective, being $k$-monotone (sometimes termed "$k$-modal") is a natural assumption in the learning theory literature (e.g., [Daskalakis, Diakonikolas, and Servedio, SODA 2012] and [Canonne, Grigorescu, Guo, Kumar, and Wimmer, Theory of Computing 2019])

[DDS12] Constantinos Daskalakis, Ilias Diakonikolas, and Rocco A. Servedio. Learning k-Modal Distributions via Testing. SODA 2012

[CGGKW19] Clément L. Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, and Karl Wimmer. Testing $k$-Monotonicity: The Rise and Fall of Boolean Functions. Theory of Computing, 2019

Thank you for your review!

Thank you for your review!

Regarding the assumption that the block partitioning (i.e., the stopping time set) is known, we agree that extending our model to scenarios where the stopping times are unknown (e.g., revealed in an online fashion) is a very interesting direction for future work. That said, we believe that this assumption is realistic in some scenarios. For example, in our motivating example of weather forecasts, one tends to have a good idea of when they need to travel / commute in the near future. Similarly, in the trading example, the trading windows are typically announced ahead of time.

Regarding your comment on Theorem 1, we find the merge by applying Lemma 8, the proof of which we summarize below. By definition of the approximate uniformity (Definition 5), we can find a consecutive subsequence of blocks with total length $L$ and maximum length $M$ such that $L / M = \widetilde U$. Then, we set parameter $T \coloneqq M / (C - 1)$ and try to merge the blocks greedily from left to right. Whenever the blocks form a longer block of length $\ge T$, we start a new longer block. In this way, we obtain several longer blocks. The length of each longer block is at least $T$, since we never finish a longer block before its length reaches $T$. Each length is at most $T + M$, since the last block added to the longer block is of length $\le M$, i.e., we "overshoot" by at most $M$. This guarantees that the maximum ratio between the lengths of two longer blocks is at most $(T + M) / T = C$ as desired. Furthermore, we form at least $\approx L / (T + M) = (1 -1/C) \cdot (L / M) = (1 - 1/C) \cdot \widetilde U$ longer blocks in this way.

We answer your questions in the following:

1. No stationarity assumption is needed for this prediction algorithm to be accurate. At a high level, this is due to the Ramsey-type fact that we mentioned on Line 139: a sufficiently long, bounded sequence must be "predictable" or "repetitive" at some scale. This observation is key to the prior results on selective prediction (e.g., [Drucker, TOCT 2013] and [Qiao and Valiant, COLT 2019]).

   As a thought experiment, imagine that the nature is trying to make the sequence as unpredictable as possible for a forecaster that always chooses a window of length $1$. To this end, the nature would draw each number $x_t$ from $\mathsf{Bern}(1/2)$ independently. However, the resulting sequence would be very predictable at a larger time scale, e.g., the mean of the entire length-$n$ sequence would be $1/2 \pm O(1/\sqrt{n})$. Conversely, if the nature tries to make the mean of the entire sequence $x$ maximally unpredictable, it would choose $x$ between $(0, 0, \ldots, 0)$ and $(1, 1, \ldots, 1)$ uniformly at random. If this were the case, when the forecaster chooses a short window length $w \ll n$, the average of each length-$w$ window would be exactly that of the past $w$ observations. The takeaway is: the nature cannot choose $x$ in a way such that it is simultaneously unpredictable for all window lengths.

2. Our proof of Lemma 8 is constructive and algorithmic: the proof gives an explicit algorithm (Lines 186--193) that runs in linear time in the number of blocks and finds the desired merge. (The algorithm is summarized in the above.)

3. As discussed above, when $T$ is set as the threshold at which we start a new longer block, the length of each longer block is between $T$ and $T + M$, where $M$ is the maximum length of blocks (before merging). Then, the ratio between the lengths of longer blocks would be at most $(T + M) / T = 1 + M / T$. We want this bound to be $C$, so solving $1 + M / T = C$ gives $T = M / (C - 1)$.

4. Thank you for the comment! We will add the following explanation on the transition from uniform $p^\star$ to general $k$-monotone $p^\star$.

   Our proof of Proposition 14 implies that, when $p^\star$ consists of $n$ copies of $p$, the resulting value of $\widetilde U$ is at least $\approx np / \log n$ with high probability. Furthermore, the proof of this lower bound still holds if each entry of $p^\star$ is lower bounded by $p$ instead of exactly equal to $p$. To prove Theorem 4, the addition step is then to show that, within each $k$-monotone sequence $p^\star$, we can always find a consecutive subsequence of length $n'$ such that each entry is at least $p'$, and $n'p'$ is at least $\approx \sum_{t=1}^{n}p^{\star}_t / (k\log n)$. This is done by identifying a monotone subsequence in $p^\star$ that contributes at least a $(1/k)$-fraction of the sum, and then finding an appropriate prefix or suffix of that subsequence.