Online Prediction with Limited Selectivity
Authors: Licheng Liu
Mingda Qiao
Venue: NeurIPS 2025 spotlight ()
Keywords: Online prediction
selective prediction
Primary area: theory
TL;DR: We introduce a model of prediction with limited selectivity, and prove instance-dependent bounds on the optimal error rate.

Abstract: Selective prediction [Dru13, QV19] models the scenario where a forecaster freely decides on the prediction window that their forecast spans. Many data statistics can be predicted to a non-trivial error rate *without any* distributional assumptions or expert advice, yet these results rely on that the forecaster may predict at any time. We introduce a model of Prediction with Limited Selectivity (PLS) where the forecaster can start the prediction only on a subset of the time horizon. We study the optimal prediction error both on an instance-by-instance basis and via an average-case analysis. We introduce a complexity measure that gives instance-dependent bounds on the optimal error. For a randomly-generated PLS instance, these bounds match with high probability.

Online Prediction with Limited Selectivity
Licheng Liu Imperial College London licheng. www22@impmeaaa.............aaaaa acc. uk
Mingda Qiao
University of Massachusetts Amherst mqi mqiaouussss. edu
Abstract
Selective prediction [Dru13, QV19) models the scenario where forecaster freely decides the prediction window that their forecast spans. Many data statistics can be predicted to a non-trivial error rate without any distributional assumptions expert advice, yet these results rely on that the forecaster may predict at any time. We introduce a model of Prediction with Limited Selectivity (PLS) where the forecaster can start the prediction only a subset of the time horizon. We study the optimal prediction error both on an instance-by- sestanceby-innstncc basis and via an average-case analysis. We introduce complexity measure that gives instance- dependent bounds on the optimal error. For randomly these bounds match with high probability.
uundollyggenerate generated PLS instance,
Introduction
In selective prediction [Dru13, QV19), forecaster observes numbers in [0, one by one. At any time I, having observed the first numbers, the forecaster may predict the average of the next S n unseen numbers. Both the stopping time i and the window length the forecaster, and only one such prediction needs to be made. The goal is to minimize the expected prediction error-the expected squared difference between the forecast and the actual average. How small can this error be?
freely chosen by
Surprisingly, Drucker [Dru13] showed that the forecaster can guarantee error that vanishes as n + +00, even though the sequence might be arbitrarily and adversarially chosen. Specifically, this result holds without any distributional assumption on the sequence (other than boundedness), and is thus robust to any misspecification, non-stationarityy or adversarial corruption in the data. Moreover, it directly addresses the prediction error, rather than regret with respect to class of experts.
In this paper, we study a variant of the selective prediction model where the forecaster only has limited selectivity. Concretely, the forecaster is given subset of the time horizon, which specifies the timesteps on which they are allowed to make prediction. This model captures many natural scenarios where predictions are either infeasible unnecessary during certain time periods. For example, people tend to care about weather forecasts primarily when they have plans for outdoor activities. An investor may be restricted from trading specific commodities during particular seasons, making market predictions less relevant at those times. Similarly, epidemic forecasts are most critical before and during pandemics.
The main contributions of this work are summarized as follows:
We introduce a theoretical model of Prediction with Limited Selectivity (PLS), which generalizes the selective prediction models of [Dru13, QV19].
We define a complexity measure termed "approximate uniformity". which gives instance-dependdnt bounds on the optimal error that a forecasting algorithm can achieve on PLS instance.
For PLS instances that randomly generated according k-monotone sequence (Definition 4), we show that the instance-dependent bounds match up to a constant factor with high probability.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

1.1 Problem Formulation
Definition (Prediction with limited selectivity). The forecaster is given and a stopping time set 1,, and the nature secretly chooses a sequence z E [0, 1|" At each timestep T, after seeing 21....,21. L the
= 1.2....... ..,,, n. the forecaster observes 2t. At any timestep forecaster may optionally choose window length w E 21,2..... - and make prediction on the average 1 wi -i=1 It+is Once a prediction made, the game ends and the forecaster incurs an error of (ā u)).. The forecaster must make one prediction before all n numbers are revealed.
An instance of PLS consists of a sequence length and a stopping time set T. When the forecaster is felly-selective (namely, T = {0, 1.2..... n of [Drul3, QV19]. For simplicity, captures most of the interesting aspeets of PLS. Nevertheless, the problem setup and our results can be easily extended to the more general prediction settings in [QV19]; see Section 5 for more details.
1)), ) PLS recovers the selective mean prediction setup focus the special case of mean prediction, which already
Following prior work on selective prediction, we measure the performance worst-case error over all possible choices of the sequence E [0. 1)".
forecaster using its
Definition 2. The worst-case enror of algorithm A is error (A) = sup=E (0,1) error x)) where error(A, (A, x) denotes the expected squared error that A incurs sequence E [0, 1]".
We will frequently use the following equivalent yet more convenient representation for PLS instance. Definition 3. The block representation of PLS instance with sequence length and stopping time set T is
L= -h, (41,,2....,11 (t2 t3 11,,,tttt .., I 1 (mn);
where = [T] and 1 < <t2
t. the elements of T in ascending order.
In the rest of the paper, we will use the stopping time set T and the block representation L inter- changeably to represent PLS instance. Intuitively, each block length I corresponds to l; consecutive timesteps 4 + 1, 4 + .,..., 4 + 4 li+1 between adjacent stopping times in T. During these timesteps, the forecaster observes new data but cannot make predictions.
The fully-selective setup of [Drul3, QV19] corresponds to the block representation & that is an all-one sequence. When L consists of block lengths of various magnitudes, naturally expect that the PLS instance becomes harder in the sense that the optimal forecaster has a higher worst-case error. We will formalize this intuition and derive instance-depe dependend error bounds for every PLS instance L in terms of a simple and combinatorial complexity measure of L.
In addition to the instance-deppnndett analysis, will also study settings where the stopping time set is randomly generated. Concretely, we consider a setup where each timestep between and n 1 gets included in the stopping time set T independently, possibly with different probabilities.
Definition 4 (Random stopping time set). For integer n 2 1 and p" random stopping time set is random subset of {0, 1,..., 1} obtained by independently including each element t with probability Pt.
E [0, "
1.2
Our Results
We prove both upper and lower bounds on the optimal worst-case error in PLS, both on an instance- by-instance basis and via an average-case analysis.
Approximate uniformity. We introduce complexity measure, termed approximate uniformity, that captures the hardness of a PLS instance.
Definition 5. The approximate uniformity of PLS instance L = (1 .1.,,, is
+1+1 + lj isisism max 1411...... 4/
Ü(C)
max
For the fully-selective case that L (1, 1,..,,, 1), we have U(C) captures the "effective horizon length" in instance L. As we show in the following, the approximate uniformity roughly characterizes the lowest worst-case error that forecasting algorithm can achieve.
More generally, Ú(C)

---

Instance-dependent error bounds. Our main algorithmic contribution is a forecasting algorithm with a worst-case error upper bounded in terms of (C). This generalizes the O1/ log n. error bound of [Dru13] for the fully-selective case.
Theorem 1. For every PLS instance L, there is a forecasting algorithm with a worst-case error of 0(1/log (()).
We prove Theorem in two steps. First, we establish an O(1/ lo)m) upper bound for the special case that the m block lengths are approximately uniform in the sense of being within constant factor. Then, we reduce a general PLS instance L to the special case by merging the blocks into longer blocks with approximately uniform lengths. We show that at least (U longer blocks can be obtained in this way, so the result for the special case implies the OLL log Ü (C)) upper bound.
Complementary to Theorem 1, we give two lower bounds on the worst-case error. Theorem 2. For every PLS instance L = (1, .,,,,.,,mm. every forecasting algorithm has a worst- case error of (L) 1/ log m)).
While the first lower bound of S2(1/Ü²) does not match the upper bound in Theorem 1, it already has some interesting applications. The following corollary (proved in Appendix A) presents concrete examples where both the sequence length n and the number of blocks m tend to infinity, yet the worst-case error remains lower bounded by a constant. In the first example, the block lengths are geometrically increasing, so m is at most logarithmic in the sequence length n. The second example, inspired by the Cantor set, shows that an (1) error is still unavoidable even if m is polynomial in n.
Corollary 3. For every m Z 1, on the PLS instance Lm = (2", 22, ,2 ,2,...,," 2mm1) with sequence length 2m - 1 and m blocks, every forecasting algorithm has an 22(1) worst-case error. Furthermore, for every k 2 L, there is a PLS instance C32 with sequence length n = 3 and m 2 - blocks, on which every forecasting algorithm has an (1) worst-case error.
The second lower bound of 211/ m)) shows that an m-block PLS instance is the easiest when all blocks have the same length: An O log m) worst-case error can be achieved when 4 l2 = Lm. while no algorithm can achieve a worst-case error < 1/ log m on any instance with m blocks. While this result might sound intuitive, our proof of the (2(1/ log m) bound is non-trivial. The proof involves a novel hierarchical decomposition of the m blocks into ternary tree and the design of random process on the resulting tree. This extends a construction of [QV19] for m blocks of equal lengths, which is based on representing the m blocks as a full binary tree of depth log m.
An average-case analysis. While the mnstance-depende upper and lower bounds do not match on every PLS instance, they do match with high probability when the instance is randomly generated. A sequence is k-monotone if it be partitioned into most l contiguous monotone subsequences. Our next result states that, if T is a ap" p' -random stopping time set (Definition 4) for a k-monotone sequence p", both [T] and Ü (T) can be bounded in terms of ||p" [|2 with high probability.
Theorem 4. Suppose that p* [0, 1]Th is k-monotone and T is p* -randdoo stopping time set Let mg >i. pt. The following two hold simultaneously with probability 1 e mm//3 1/n over the randomness in T: (1) [T] = O (mo); (2) (T) = 2(mo log" n))).
As a direct corollary, our bounds on the optimal worst-case error are tight up to a constant factor with high probability. We prove this corollary in Appendix A.
Corollary 5. If k-monotone sequence px E [o, 1]" satisfies Σi=o PÊ 2 Q((k log 1))++) for some constant e O, with high probability over the randomness in the p" random stopping time set T, the forecasting algorithm from Theorem I has worsf-cuse error that is optimal up to constant factor.
Concretely, if k O(1) is constant, Corollary 5 applies whenever the expected number of stopping times, Σ P7, is at least po)ylog(n). If k O(n²) ) is polynomial in n for some (0, 1), we have nearly-tight bounds as long as -²-1 pt = 2(x for some (a, 1].
1.3 Related Work
Most closely related to our study is the prior work on selective prediction. Drucker [Dru13] introduced the problem of selective mean prediction under the name of "density prediction game" and proved an
3

---

(11/log n) upper bound on the expected error. Qiao and Valiant [QV19] proved matching lower bound, and extended the positive result of [Dru13] to the setting predicting more general functions.
Chen, Valiant, and Valiant [CVV20] introduced a more general framework that encompasses selective prediction well other data-collection procedures including importance sampling and snowball sampling. Brown-Cohen [BC21] subsequently obtained a faster algorithm under this framework. Qiao and Valiant [QV21] studied "learning" variant of selective prediction, in which the learner observes multiple sequences and aims to identify the sequence with the highest average inside prediction window of their choice.
All the positive results above are based on the Ramsey-theoree observation that a sufficiently long, bounded sequence must be "predictable" or "repetitive" at some scale. This allows selective forecaster to randomly select timescale and achieve a vanishing error as the sequence length goes to infinity. Similar observations have been made in different contexts [Fei15, FKT17, MHO25].
More broadly, our setting is related the recent work on online prediction with abstention, where the forecasting algorithm is allowed to occasionally abstain from making predictions at an additional cost [ZC16, CDG 18, NZ20, GKCS21, GHMS23, 22]+
2 Instance-Dependent Upper Bounds
2.1 Special Case: Approximately Uniform Block Lengths
Recall from Definition that PLS instance can be represented by list of block lengths L (2.,4....,, ). Towards proving Theorem we start with the case that the block lengths do not vary drastically and prove O log m) upper bound the worst-case error. Our algorithm is defined in Algorithm It calls RandomSelect (Algorithm 1) to obtain a randomized prediction position and length j. The algorithm then reads the first i blocks of the sequence, and uses the mean of the last j blocks (namely, blocks - j, i j + ,,...,, 1) to predict the mean of the next j blocks through - 1).
Algorithm (RandomSelect(ss k)) a recursive procedure that prescribes prediction position and a window length within 2 consecutive blocks (with indices s to 2 1). With probability 1/k, it outputs (s + 2 i.e., predicting the average of the last 2 blocks using that of the first 2 Otherwise, it computes p. the proportion of the total length of the first 2 blocks within the 2 blocks. then recurses on one of the two halves with probability and p, respectively.
Algorithm 1: RandomSelect(s,
Input: Integers 8, k 2 Output:
A pair (i,j) such that S i - and i 2
With probability 1/k, return (s + +2 2- 2
p ->it 1o4s)
2 [ 1o+1)
return RandomSelect(s.. k with probability p, and RandomSelect(s + +2=-1,10 the remaining probability pt
1 k
1) with
Proposition 6. On PLS instance C = (11, ,., that satisfies max(h drn...mmk < C, Algorithm has worst-case error of OCC/ log.). m))
min(h Ja....tn)
This extends the result of [Drul3] for = 1, i.c., all blocks have the same length. The proof is similar those in prior work and deferred to Appendix B. We provide brief proof sketch below.
Proof sketch. For & 2 1 and μ E [o, 1], let L(k, (1) be the maximum squared error that Algorithm incurs on a sequence of 2* blocks with average J.. We prove by induction that L(k,, (1) & (C/kk) u(1 - μ). The proposition then follows from C/k OCC/ log m) and y(1 μ) O(1). 0

---

Algorithm 2: Prediction with Limited Selectivity on Approximately Uniform Blocks
Input: Instance C. (11; 12, (2,....,mm bm). Sequential access to sequence [0, 1] of length n1 = 1 + 12 + ... + Im.
e- [log m|
(i,j) RandomSelect(LLA))
3 t 4 1 + 12 .....444-. 4-11
Read æ1, ,,,,,.,,
5 we f li-j + 11--+11 + 4-11
6 j + 1 (o) + It-1 + ..... + Tt att-wo+11 +);;
7 w + 1 + 1441 +... 4+j-1;
Predict the mean of 21+1, Fotw as p
2.2 The General Case
To prove Theorem 1, we merge the m blocks of possibly different lengths into =: Ü(C) blocks with lengths within a constant factor, so that Proposition 6 can be applied to obtain an O / log (C)) error bound. Formally, obtained from by merging consecutive blocks and taking a contiguous subsequence.
say that PLS instance L' is merge of another instance L. if L can be
Definition 6. L' = (I', 12, .',""..''"!
!mm)) is a merge of =
if there are 1 1 i1 < is <
2m < im/+ +1 S + 1 such that 1/ b, + +1y+11 +... -1 every j [m'].
For instance, (5,9) is merge of 2,,,3,4,5, 6) witnessed by (i1, i2, (2,4, 4, 6): merge consecutive elements to obtain (1, 5, 9, 6) and take the contiguous subsequence (5, 9). Naturally, the merge of PLS instance can be solved with low worst-case error, can the original instance. We prove the following lemma in Appendix B.
Lemma 7. If L' is a merge of L, the minimum worst-case error that can be obtained on C is smaller than equal to that on L'
The next lemma states that any instance has merge of length ((ū(C)) that consists of elements within a constant factor.
Lemma 8. For every C >>> every PLS instance C has a merge L' (1i, 12 .......,,, V'n) such that: (1) m' 2 1/C1 U(C]: (2) max(V, U2 .,, 1/ min 1 ./....,..... m S C.
Proof. By definition of Ü, there exist indices S in S jo S m such that
Li thg 10
max dug 30
ÜC). Using the shorthands L = Lt + 1o0t1 + ....... 44 and M = max 11011...................111..1.. 4. we
have (C) .M. Then, we construct L' by merging the block lengths 4o lio+1....... 420 We
T = M/(C - 1) and greedily form longer blocks of length ss T'. Formally, we run the following
procedure:
Start with i, = in and counter ent- 1.
Check whether 4i.. liema + ... + 1jo T. If so, set m' ent 1, L' 12,,2,..... Nmm)) and end the procedure.
3. Otherwise, find the smallest ls E (Jent, fent + .j... such that Iin. + 4in + + 4. 2 T.
4. Set l'mt. = 4i... + 14met11 +... + 17 and lent+1 k + 1. Increment ent by and return to Step 2.
Clearly, the resulting L' (11 12 ......... U' ('m) is merge of L witnessed by indices .,, The construction ensures that 12 E [T,T" + M) for every j E [m'']. Therefore,
max 12 ................................ I'm
T + M M/(C - 1) + =.
<
min (1 12, ........ }
T
M/(C-1)
The size of the merge is at least
Ú
= (1-1//)
T+M
17CC-1)+1
5

---

Theorem directly follows from Proposition 6, Lemma 7, and Lemma 8.
Proof of Theorem 1. Applying Lemma with C = 2 shows that L has merge L (11 1/2........ ('m))
such that m' 2 [ and max(41.22 "..i,,,...,, / min(21,44 .....,,, h - 2. By Proposition 6, there is forecasting algorithm for L' with worst-case error of O log m') = 0(1 (4)).
Then, Lemma 7 gives a forecasting algorithm for with the same error bound.
Instance-Dependent Lower Bounds
3.1 Lower Bound Terms of Approximate Uniformity
Theorem (First part of Theorem 2). For every PLS instance L, every forecasting algorithm A has worst-case error of eeror (A) 16(U()))*
Recall from Definition 3 that the block representation L (4 12,12....0 ....................... (mm corresponds to a PLS
instance with sequence length n = 1 +2 +........................ mm The timesteps are naturally divided into m E [4]]. We
blocks, where each block E [m]] consists of timesteps B, == {11 + l/2 +... 4-1
prove Theorem 9 using the following observation: Regardless of the prediction window + 1, l w)
chosen by the forecasting algorithm, 92 (C) fraction of the timesteps within the window must come from the same unseen block.
Lemma 10. Let C = (1,, 12,,2..... ................................ (.)))) be a PLS instance with sequence length n and stopping time set T. Then, for every in E [m], = I l2 i {io, in + +1....,m, m such that B. 1, will 20(4)'
lio-1 E T and w E [n- - -.,, there exists
The proof is deferred to Appendix C. Next, show how Theorem follows from Lemma 10.
Proof of Theorem assuming Lemma 10, Consider the random sequence x E {0, 1) constructed by setting all entries within each block to the same bit chosen independently and uniformly at random. Formally, we draw P1, , ~ Bernoulli(1/2) independently. Then, for each E [m]] and j B,, we set z M4.
Fix forecasting algorithm A. For E and w [n - t), let & denote the event that A makes prediction at time on Xt, Ei= Zt+s- We will show that, conditioning on event &,,w and any observation Z1:: = (#1, .,,..., ). the conditional variance of Xt, is at least 22(1 (C))?) This would imply that the conditional expectation the squared error incurred by is lower bounded by (C)).. and the theorem would then follow from the law of total expectation.
Recall that E T must be of form I + 12 + ......... + li for some in E [m]. Then, X can be equivalently written as Xt,w Li= O; " where a; == wi B; n +, 1- w|l denotes the fraction of timesteps in jt + 1, + w] that fall into block B,. Since we sample .1..... pm independently. conditioning on event ε and the observations both of which are solely determined by the
randomness in f1, ......., , and each of / Mig.t....,,M still follows Bernoulli(1 /2 independently and has variance 1/4. Therefore, the conditional variance of X is given by
m
m Σ
Var (x E,,w,, F14]] = Var
Σ
ai - 14 Ei,w, Fidt
a
1=10
By Lemma 10, there exists E (io, io + 1, I,...,,.,.................. ........) m) such that a; 20(C)
Var [Xe, EE, Tia))
is at least } 20(())
16(0
Herr and in the following, we assume that E T in the PLS instance. If not, we note that the forecasting algorithm is not allowed to predict until timestep la == min T, so the analysis goes through after shifting the timesteps to.

---

3.2 Hard Instance via Tree Construction
Theorem 11 (Second part of Theorem 2). For every PLS instance = forecasting algorithm A has worst-case error of error (A) 2 Q (1/log l)g
every
Similar to the proof of Theorem 9, we randomly generate sequence by first choosing J E [0, 1Jmh. and setting every entry within the i-th block to p4. The key difference is that, instead of drawing each 14 independently, we carefully design the correlation between different entries of μ. This correlation structure is specified by a Iree construction similar to [QV19]: We build a tree whose leaves correspond to the m entries Pi..... Hm. We assign noise to each edge of the tree, and the value of a leaf is set to the sum of noises on the root-to-leaf path. Again, we will argue that for every possible prediction window [t 1, w]. even after seeing the first & entries, the conditional variance in the average of Tt+1. Tz+= is still sufficiently high.
A key difference between construction and that of [QV19] is that they focused on the special case where 1 l2 = to handle the general case, our construction involves ternary tree in which every internal node has either two or three children, depending on whether the current subtree contains a long block whose length dominates the total block length.
Im = 1, so that a full binary tree of depth log2 m suffices. In contrast,
We formally introduce our tree construction as follows. Definition 7 (Tree construction). Given PLS instance (4, .2....,,hn, Im). we construct tree using the following recursive procedure:
Ifm= 1, return free with single leaf node that corresponds to 1i.
Let S 1 + l2 +... lm- If there exists i E [m] such that 1,- > S/2, such index i' must be unique, and we construct ternary tree where: (1) The left subtree of the root node the tree construction for (...:.:b++-::: (2) The middle subtree is single leaf node corresponding to the ithth block; (3) The right subtree the tree construction for (lx+41....,,m))
Otherwise, every 4 is at most S/2. We choose the cutoff i E [m]] as the smallest index such that 1 +..1++....0.. 2 S/4. Note that we must have I +12 +... +...41 1.+ = (11 + 12 +...... ................................ + 41 + +1-- < S/4 + 5/2 = 35/4. recursively build two trees for (2,,12..... Le-) and (l, 12, 1m and return the tree obtained from joining these two subtrees.
By construction, the tree has m leaf nodes, each of which corresponds to one of the m blocks. For each node e in the tree, let I(v) denote the set of block indices that correspond to one of the leaves in the subtree rooted at v. is clear that every [(v) is of form {ú, i I,...,J j.} for some 1 S S S m. We write size(u) (v) = [Z() as the number of leaves in the subtree rooted at v.
Next, assign noise magnitude to each node in the tree.
Definition 8. The noise magnitude at node u set to a(v) ==
(nsize((1)
ln 122
The noise magnitude is always in [0, 1]: it takes value O at the root node and takes value at every leaf node. Then, we assign random values in [0, 1] to the nodes in the tree construction as follows. Definition 9 (Node value). The root node r is assigned value p. = 1/2 deterministically. Then, for every edge (u, v) the tree, after pa is determined, we independently draw be such that:
1+ Me E { (1-0 (vv)
and IE [p4 pm] = Pa
2
Note that the above is well-defined: By Definition 8, it always holds that (u) < ((v). So, regardless of whether Mr equals 1w)(w) or 1+a(u) we always have μaa E [--(()) [ta(e) Therefore, there
exists unique distribution over { 1-a(0) 1+a()) } with an expectation of pa.
Finally, we construct the hard instance by setting the value of each block to the corresponding node value in the tree construction.
Definition 10 (Hard instance). Given a PLS instance f. (11, 12....,,m) we construct tree following Definition 7 and assign values to its nodes following Definitions 8 and 9, For each i [m].
7

---

let pt denote the value of the leaf node that corresponds to the i-th block. Finally, the sequence consists l copies of hr. l2 copies of p2. ... Im copies of pmm in order.
3.3 Structural Properties
Towards proving Theorem 11 using the hard instance from Definition 10, we make some observations on the tree structure as well as the node values. We first note that, for each edge (u, v) in the tree, the
conditional variance of Me given M4, takes simple form. Indeed, this is the main motivation behind the choices of the noise magnitudes and node values.
Lemma 12. For every edge (u, 8) in the tree and conditioning on any realization of pu. it holds that Var [uv [a] In(sime(w)) (w)))ln(s)sen (simee[)))
Iin m
Proof. Since adding a constant does not change the variance, Var [uge |ul = Var Jug - 1/2 | [ul = E [Ap 1/2)² [u]] [E Ja+e 1/2 p.]]². By Definition 9, we have E [ue [u] Muu so the
second term [E [Mg - 1/2 p=,]²² reduces to (Mu, 1/2)2. Then, we note that [p,, - 1/2) = a alu)/2 and [,4 1/2 = a (v)/2 always hold, which further simplifies Var [M | [uu] into (o))
[o(u)] /4. Finally, the lemma follows from the choices of of or (u) and a(v) in Definition 8. O
The next technical lemma (which prove in Appendix C) states that, for any sisj m, there exists an edge (u, v)) in the tree such that: (1) Observing the first i - blocks does not reveal the value of Mui (2) The remaining variance of By has a significant contribution to the average of blocks i, + 1.....j. j. To state the lemma succinctly, we define the "total length" of a set S. We will mostly use this notation for S I(v) (where v a node in the tree) or S [i.]] (where S S i m).
Definition 11. The total length of set S is totlen(S) = En L 1 [i S).
Lemma 13. For any 1 S S S m. there exists an edge (u, v) the tree such that: (1) I(w) n (1.2.... ,
.1.........111. 1 = 0; (2) totlen(I(w)) 2 2(1) totlon i)); (3) size(v) S size(u)/2.
3.4 Lower Bound in Terms of Number of Blocks
We prove Theorem 11 by putting together Lemmas 12 and 13, As in the proof of Theorem 9, we can decompose any prediction window [t + 1, + w) into several complete blocks ig. in + :o 1 and possibly incomplete block jo- If the complete blocks constitute least half of the window, we apply Lemma 13 to identify an edge (u, v) in the tree, such that the noise in Muy Mu, contributes an (11/ log variance to the average to be predicted. Otherwise, we lower bound the variance directly by considering the edge above the leaf that corresponds to block jo-
Proof of Theorem II. We consider the random sequence x E {0, 1}" constructed in Definition 10 and fix forecasting algorithm A. For E T and w E [n E). let E,,. denote the event that A Σ Lt+i. We will show that, conditioning on any event Er as well as the observations I1:: = (21, , T.)). the conditional variance of X2,w is at least 2(1 l)).). This would lower bound the conditional expectation of the squared error incurred by A by 12(1/ log m), and the theorem would then follow from the law of total expectation.
makes a prediction at time on X1,
Recall that E T must be of form 4 + + + 46-1 for some in E [m]. Let jo E [m]] be the smallest number such that 4o + hig+1 +... ... + 4. 2 w. Let 8 = w - (li, + lig-11 + ..... + (jo-)). Consider the following two cases, depending on whether ô exceeds half of the window length w:
Case 1: 8 > w/2. Let v be the leaf that corresponds to the jo-th block in the tree construction, and be the parent of v. Note that size(v) and size(u) 2 2. By Lemma 12, Var [av |a]] is given by lnfsize(u]) (u)zee))))-
Furthermore, since event & and 3i: only depend on the realization of μ1,, .2,.... Mig 11. the value of Mio (namely, pw)) still has an 2(1/ log m) variance conditioning on E, and T1.t. Then, since 2 w/2 entries among It- Z1+2. Ittw are set to Mjo- Var [X E I1a] is at least 1 Var [Mi E,, x1.]] 2 211 m).
In
Ω
4
Tlmm
log 192
Case 5 < w//2 In this case, we have totlen([io- Jo - 1]) = lig + lio + ... + 110-1 = 5 2 w/2. Applying Lemma 13 with i in and j jo -1 gives an edge (u, v) such
8

---

that: I(x) n 21, size(e) _ size(u)) /2)
20 1 = 0; (2) totlen
2 22(1 totlen((io. 3o 1)); (3)
By Lemma 12, Var [Mu E and the observation of 21:t only depend on the realization of μ/1. (M2. M and none of these in - leaves is inside the subtree rooted at v, fy still has an 22 log m) conditional variance. Furthermore, within the length-w prediction window, the number of entries that are affected by fy is exactly (o()e)(Z(v)) 2 2(1) totlen([io.jo 1]) 2 2(1) w. Therefore, the conditional variance of Xt, e is least (11 Var [uv &t,w, 2 Q(1/ ((1/logm) log m).
[u] is equal to (nfaize(u))-i((zzzeete 4n m
2n - S2(1/ log lo) Since event In
An Average-Case Analysis
As warm-up towards proving Theorem analyze the special case that pz consists of identical entries. The full proof is presented in Appendix D.
Proposition 14. Let T be a p -random stopping time set for p (p. ..... .p) [0, 1|a With probability at least Ü(T) 2 m/
ap/3 - 1/n over the randomness in T: (1) [T| S 2mp = O(n)); (2) = (/mpp log n).
Proof. We first note that [T] follows (inomial(n,))) p). so a multiplicative Chernoff bound gives Pr [[T] > 2np] I emp/3 Towards lower bounding (TT), let L = .2.,,,..... ,,,mm be the block representation of T and let Lo == [(2In))/p]. By definition, (TT is at least 1 1 max
n-min max 2m.dd If we additionally have 12.
S Lo and min T S Lo. we would
1. Thus, it remains to show that, with probability at least 1 1/n, both max .2. mm) S Lu and min T s Lg hold.
have (T) 2 L- = n/
Lo
Consider the complementary event: for either max(1ı, 12. l2....... .........mm) 1m) > Lo or min Lo to hold, there must be some / E {0, 1, 1,..,.., n Lo 1} such that T + 1, 1 Lo] =0. 0. For each fixed I, 1+1, 142, ...,......44.......... T. get included T independently with probability p. Thus, /
= holds with probability (1 - -p) fa. By the union bound, Pr [max 22,.2....,,u, 1m) > Ln V min T Lo]
is at most (n Lo) (1 - p) Lo which is further upper bounded by ne pLo < ne 2lan 1/n using
1 p e and Lo 2 (2 In nppp This completes the proof.
Our proof of Proposition 14 implies that, when pa consists of copies of the same value p [0, 1]. the resulting value of Ü is at least as np/ log with high probability. Furthermore, the proof of this lower bound still holds if each entry of p" is lower bounded by instead of exactly equal to To prove Theorem the addition step is then to show that, within each k-monotone sequence p", we can always find consecutive subsequence of length n' such that each entry is at least p', and n'p' at least Σ P (k log This done by identifying monotone subsequence in pd that contributes at least (1/ki)-facttion of the sum, and then finding an appropriate prefix or suffix of that subsequence.
Discussion
An obvious open problem is tighten the instance-dependent error bounds (Theorems 1 and 2). Since the optimal error is (11/logn) for the full-selectivity case [Dru13, QV19), one might hope to strengthen the (2)]2 lower bound to 1/ log (L). or at least 1 1/polylog(( (C)). Unfortunately, as we show Proposition 16 (Appendix E), this is not possible: there exists a family of instances (Cx))t such that (Cx) > too as l + +oc, but a worst-case error of ((I/Ū(C.)) can be achieved on each L.-
Therefore, to obtain tighter instance-dependent bounds, we need to identify complexity measure that characterizes the hardness of PLS more exactly. A concrete starting point is to examine the instance family from Proposition 16, which is based on a construction that resembles the Cantor set. Roughly speaking, these instances suggest that sharper complexity measure should account for

---

the number of approximately uniform blocks that can be obtained via not only merging consecutive blocks, but also "skipping" some shorter blocks the cost of additional term in the prediction emvor.
While we focus on predicting the average of number sequence, our results be easily extended to the setting of predicting more general functions (including smooth and concatenation-concavy functions studied by [QV19]). In particular, they imply an ( log' /2 (()) upper bound (on the worst-case absolute error) for predicting smooth functions and O log (()) bound (on the squared error) for concatenation-concav functions. Since the average function is both smooth and concalenation--ooccee,, the lower bounds in Theorem 2 also apply these broader function classes.
Yet another natural direction is to revisit other classic online learning settings (such as the experts problem) from the perspective of limited selectivity, i.e., when the learner is only allowed to change its prediction or action on some given timesteps. The approximate uniformity measure as well as some of our proof techniques would be natural first steps towards understanding these models.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers, whose suggestions have helped improved this paper.
References
[BC21] Jonah Brown-Cohen Faster algorithms and constant lower bounds for the worst-case expected error. In Advances in Neural Information Processing Systems (NeurIPS), pages 27709-27719, 2021.
(CDG+18) Corinna Cortes, Giulia DeSalvo, Claudio Gentile, Mehryar Mohri, and Scott Yang. Online learning with abstention. In International Conference on Machine Learning (ICML), pages 1059-1067, 2018.
[CVV20] Justin Chen, Gregory Valiant, and Paul Valiant. Worst-case analysis for randomly collected data. In Advances Neural Information Processing Systems (NeurIPS), pages 18183-18193, 2020.
[Dru13] Andrew Drucker. High-confidence predictions under adversarial uncertainty. Transac- tions on Computation Theory, 5(3):12, 2013.
[Fei15] Uriel Feige. Why are images smooth? In Innovations in Theoretical Computer Science (ITCS), pages 229-236, 2015.
[FKT17] Uriel Feige, Tomer Koren, and Moshe Tennenholtz. Chasing ghosts: competing with stateful policies. SIAM Journal on Computing, 46(1):190-223, 2017.
[GHMS23] Surbhi Goel, Steve Hanneke, Shay Moran, and Abhishek Shetty. Adversarial resilience in sequential prediction via abstention. In Advances in Neural Information Processing Systems (NeurIPS), pages 8027-8047, 2023.
[GKCS21] Aditya Gangrade, Anil Kag, Ashok Cutkosky, and Venkatesh Saligrama. Online selective classification with limited feedback. In Advances in Neural Information Processing Systems (NeurIPS), pages 14529-14541, 2021.
[MHO25] Theodore MacMillan, James P. Hilditch, and Nicholas T. Ouellette. Expected correlation in time-series analysis. Physical Review E, 111(2):024121, 2025.
[NZ20] Gergely Neu and Nikita Zhivotovskiy. Fast rates for online prediction with abstention. In Conference on Learning Theory (COLT), pages 3030-3048, 2020.
[PRT+24] Stephen Pasteris, Alberto Rumi, Maximilian Thiessen, Shota Saito, Atsushi Miyauchi, Fabio Vitale, and Mark Herbster. Bandits with abstention under expert advice. In Advances Neural Information Processing Systems (NeurIPS), pages 126059-126087, 2024.
10

---

[QV19] Mingda Qiao and Gregory Valiant. A theory of selective prediction. In Conference on Learning Theory (COLT), pages 2580-2594, 2019.
[QV21] Mingda Qiao and Gregory Valiant. Exponential weights algorithms for selective learning. In Conference on Learning Theory (COLT), pages 3833-3858, 2021.
[ZC16] Chicheng Zhang and Kamalika Chaudhuri. The extended littlestone's dimension for learning with mistakes and abstentions. In Conference on Learning Theory (COLT), pages 1584-1616, 2016.

---

A Proofs of Corollaries
A.1 Proof of Corollary
(20 ........22-7 with sequence Corollary 3. For every m. 2 1, on the PLS instance Lm = Lm
length 2m -1 and blocks, every forecasting algorithm has 21(1 worst-case error. Furthermore, for every k 2 1, there is PLS instance C with sequence length 3 and m = 2 1 blocks, which every forecasting algorithm has an (2(1) worst-case error.
Proof. In light of the ((0/((())) lower bound in Theorem it suffices to show that each of these instances has an (1) approximate uniformity.
The first family. Fix 2 and consider L. (20, 21 ; we have
) For every S iiijj m,
4 + h41 + ... + 1 max14,444,,.....
2: + + .... 2
2
$ 2 = 2.
2)
follows that U(Cm) =0))))))
The second family. We construct the instances , C2.... recursively: & is set to (1, (,1,1) 1). For each & 2 2, L is defined as f o (3h-1) - fk- where denotes sequence concatenation. Then, we prove by induction on l that: (1) each C corresponds to PLS instance with = 3 and my 2 1; (2) Ü (C,) 33
For the base case that = 1, we indeed have n = 3* my = = and Ü(11) For k 2 2. assuming that the statements hold for - we have n. = - + +3 + n 3
and mi ma-1 + m (2* 1) + 1 (2# 1) 2 1. To upper bound Ü (Ct)). consider an arbitrary contiguous subsequence (4,,441,.... ...,, 1,) in G. If this subsequence contains the entry 3*-1 in the middle, we have
4 + 1++1 max (4, 441...... b
1/
71
3
3.
3
3
If the subsequence does not contain the middle entry, it must be a contiguous subsequence of C/-11 so the upper bound
4 + 1i+1 + + max (1, 1.41....,117 b/
<3
would follow from the induction hypothesis. This completes the proof.
A.2 Proof of Corollary 5
Corollary follows from Theorems 1, 2 and 4.
Corollary 5. If k-moootonee sequence p E 10, satisfies Ei= P 2 10((klog' n))+t) for some constant e with high probability over the randomness in the p pr-ramdom stopping time set T, the forecasting algorithm from Theorem I has a worst-case error that is optimal up to constant factor.
Proof. Let mg == 1t= p.. Assuming that ma 2 O0(K log" n) +)), we have mo = w(log n) and k llog2 n = 0m mm 1/(2t))) By Theorem 4, holds with probability -3 -1/n = (11/))
1-
that [T| O(mo) and
Ú 2 Ω
mg
2
mg
2m 1/ (1(0))
l: log2
1/(1+c)
mg
By Theorem 1, there is forecasting algorithm with a worst-case error of at most
1
=0
logü ((T)
log
mm c((+0)
log mo
12

---

on the PLS instance T. By Theorem 2, the upper bound [7| & O(ma) implies that every forecasting algorithm must have an ( log mo) worst-case error on instance This completes the proof. 0
B Proofs for Section 2
B.1 Proof of Proposition 6
Proposition 6. On PLS instance (11, 12,,..,, bm) that satisfies maxih bom has worsl-case error of (C/ m).
S C, Algorithm min da...imm
Proof. For integer k Z and μ E [0, 1], let L(k, μu) denote the maximum expected squared loss that Algorithm 2 incurs sequence of 2 blocks with average μ.. Let (C+1)² and Φ(x:) == xx(1 - =)).
We prove by induction that L(k, (4) _ o(()). The proposition would then follow from the above together with the observations that = OCC), 1/k O(1/ log m), and ((μ) O1)).
The base case. When & = 1, Algorithm 2 calls RandomSelect(1, 1), which always returns (i, = (2, 1). Then, Algorithm 2 sets
t=
4.
w l2
h, i
(I1 + x2 + 21,).
1
and predict that the average of #1 through -1,-1 equal to ft. Then, the resulting error given by ( - 222)² where
1 (1h + 21, + ... 21, +1,
A1 [ (2) + 2 + + +x,) and
P2 =
12
are the averages of the two blocks. Let c == 12/12 Note that we have
h pn la μ12
22 x4tt (1 12) μr.
Dividing both sides by 4 gives μn + cp2 (e+ 1)μ. Then, the squared error can be upper bounded follows:
L(I,)) S
sup
(M1 12222
[10.1 #rtop==ct1)jp
For any #1 A2 E [0, 1], e > and / = 14 + Tia holds that
②(H)= Itc ((1)) + (12)) + (1+ (1+ (1s -22)2
c
(I)
Itc
Rearranging the above gives
(μ) -2)² (1 c)
(6w))
1 Mm)) 1 +
< (1 c)2 p(u),
where the second step holds since @(u1) and 2(u)) are nen-negative for any M1. E [0, 1].
Noting that E [1/C, C] and that the function (=+1)² is increasing on (00+ and decreasing on (0, 1), we obtain the base case
L(I,)) (c+ 1)2
(C+1)2 C
(())
((w) = d(u).
Inductive step. Now, consider the case that k 2 2, assuming that the induction hypothesis holds for L(k: 1, p1). Shorthand N := -1 for brevity. When Algorithm 2 calls RandomSelect(1, k), with probability 1/k: the pair (N + 1, N)) is returned, causing Algorithm 2 to predict that the average of blocks N through 2/N (denoted by μ2) the same as the average of the first N blocks (denoted by 41). In this case, the squared loss is given by (M) 2
13

---

With the remaining probability k=1 RandomSelect recurses on either the first N blocks or the last N blocks. Note that the resulting behavior of Algorithm 2 exactly identical when the algorithm runs on either the instance Li (1,,1,,...,44 ,....., or the instance L2 = (IN+1, IN + 122N). which can be controlled using Lik- - 1, -) Let c = 2 lN+s Note that we have E [1/C, C?. since the
assumption that max 12..1/1............ d2...dm min la.........
C' implies
1 C C4SN-min(hsble
min(11 2.. 1m
Σ N+i S N. max .... mm SC. Σ4 4.
Dividing the above by Ei= 4 gives 1/C c C. The probability of recursing on the first half
is given by (1 - t) I+c and that of recursing on the second half is (1 t) Itf. Then, by the induction hypothesis, the conditional expectation of the squared loss in this case is at most
1
L(k 12 - (1t
c_ (((22)) 1 Itc
1 1+ L(k: 1, +
Then, we get
11 3
sup 11.02 (ctl))
1 ( (11 12)² 2
h
k -
k k- l+c 1 1+c (((())
(1t p(m1)
(c+ 1)2 (11 (11--11101 -22) -22) a ( i [-oo)) + I+c ((t))
c
sup
+
[0.1]
in ou
(c 1c+1)2l11 (11 122 + c+1 c+1 ((m))
c
Mun) c
sup 12
M1 M1+ewa I
p(p),
(Equation (1))
where the second step applies = (C+1)² > (e+1)² which follows from E CJ. This completes the inductive step and thus the proof.
B.2 Proof of Lemma 7
Lemma 7. If L' is a merge of L, the minimum worst-case error that can be obtained on C is smaller than or equal to that on C².
Proof. Let C' (1, 12 ................................ ( be merge of L = (11, 12.
1m) witnessed by indices
i,, i., fmm411 Let n = 1 + + Lm and n' == 1/ + 1/2 + 1 denote the sequence lengths in L and L', respectively.
Suppose that forecasting algorithm A' has worst-case error of e L' Then, the following is forecasting algorithm for L, which we denote by A:
Let to = 11 + 12 +... +... 4, Read the first to elements in the sequence and disregard them.
Simulate A'. Whenever A' tries to read the next element in the sequence, read the next element and forward to A'.
When A' predicts ÿ as the average of the next w elements, make the same prediction.
Clearly, whenever A runs on sequence E [0, 1J", it has the same behavior A' running on the length-n' sequence x' = (Iig F +2, Ftg tx) Therefore, the expected error of A on x exactly the expected error of A' on x', which is further upper bounded by e.
14

---

C Proofs for Section
C.1 Proof of Lemma 10
.m)....)))))))))) be a PLS instance with sequence length n and stopping time set T. Then, for every is E [m], l + l2
Lemma 10. Let -
i E (io, in + +1...., ..) such that B, nl [t + 1, + will 2 1 E 'T and E fl.. there exists w
20()))
11 + 12 + + 1i-11 and w E [n - t]. Recall that the i-th block is defined as B; = {11 + 12 + 1i-1 + +j:3 E [[.]]. Let jo be the index of the last block that intersects [t + 1, + ws]. Formally, jo the smallest number in {io, io + l,..., m) such that l1 + +1+11 + .... 400 w.
Proof. Fix in E [m].
(4g 1o+11 +... + 111)) ). Note that the prediction window + 1, + w| consists of jo op complete blocks (Br, through - along with the first ó timesteps in block Bj. We consider the following two cases, depending on whether exceeds half of the window length w:
Let
Case 1: 8 2 w/2. In this case, block jo would satisfy the lemma. This is because jo (io. lu + 1...., m3 and
BB n + 1, w/ 8 21)
where the last step holds since Ü(C) for every L.
Case 2: 8 < w/2. In this case, we have Lo + 1i011 + by definition of (C),
+ 10-11 w - w/2. Furthermore,
Ú(4)
4+441 + 1 2 10 + +1111
10 -
max Isisism 4-- 1/} max(lig -10-11111100 1..... 4
It follows that
max to 10-1) 2 (1i + li0+1 +... + 10-1) 2
w
Ú(C)
20 (C)
particular, there exists E (io, in + 10. 1} such that
[L 11,4+ w|ll 2 w
(C)
C.2 Proof of Lemma 13
Lemma 13, For any 1 < i < < m, there exists an edge (u, 3) in the tree such that: (1) I(v)
= 0: (2) totlen(I(v)) 2 2(1) totlen [i. i)); (3) size(w) sizelu)/2.
Proof. Let un be the deepest node in the tree such that {i, + 1, ......) C I(u)). Note that such a node must exist, since the root node satisfies I(r) {1, 2, ...,, mm] fi,i+1,... 1........... J}. Then, consider two cases, depending on whether I(ui) contains a long block that constitutes more than half of the total length.
Case 1: I(u1) contains a long block. Let 1" E ((1)) be the unique index such that 4.- > totlen(I(u,)) /22 Then, by construction of the tree (Definition 7), uj has a child u2 that is leaf node corresponding to the i*-th block. We claim that must be in [i.j]. Otherwise, by Definition 7, i has two other children: one corresponding to blocks I(u,) n [1, to I(u1) n E + 1, m... Then, one of these two children must contain the set {i, + 1, .,....}}. contradicting
and the other corresponding
choice of u1.
Then, (ui, U2) would be the desired edge. For the first condition, since I(wz) = (i*) and it > i, we have I(w2) O 21,2....., 1) 0. For the second, we have totlen(I(uz)) = 1.- > totlen(Z(m) )2 2 totlen((i. (). Finally, since size(u1) 2 and size(u2) 1, holds that size(ug) (1/22
15

---

Case 2: I(u1) has no long blocks. By Definition 7, ui has two children and such that I(u)) can be partitioned into [(u)) and I(uz). It follows that {i, i + ......j} ..} is partitioned into
I(w2) O [1,]] and [(us) n [ In particular, we must have max(totlen [ (22) n [E,j],, totlen(Z(ua) n [k,5])] 2 (o.)en((s.)))/2
Without loss of generality, we assume that (o(le)(Z(ua) n [E:j]) is at least totlen ((i, f1)/2 in the following; the other case can be handled in a symmetric way.
Let i' be the smallest number in I(us). Then, we have I(us) n [i.j] = denote the deepest node in the subtree rooted at u3 such that {t', 1 + l.....It E I(vi). Then, we further consider the following two subcases, depending on whether I(v)) contains long block (compared to totlen (I(1))
................................ }}. Let 0i
Case 2a: There exists i* I(U)) such that 4-- >> totlen(Z(e)) /)/ By Definition 7, 2 has child 02 that is leaf node corresponding to the i"-th block. Furthermore, we claim that i* must be in [] otherwise,
have i 2 j + and in has another child with index set that contains {i' 1, j). which contradicts our choice of ti
( +1, +1,...,," - 1
Then, (ci,vg) would be the desired edge: I(r2) }i*} and 1" 2 i' 2 together give the first = 0. For the second condition, we note that totlen(Z(v>)) = 4. > totlen (1)))())))))))))))))))((( (2)))/22222) 2 totlen((?". 5i)// 2 totlen(li, j))/4. Finally, the third condition follows
condition I(22) (1,2,... ...i. i..ii-i
from size(U2) = 1 1 size(v1)/2.
Case 2b: Every block in I(v1) ) has length of at most totlen (Z11)) By Definition 7, 82 has a left child V2 that satisfies
totlen(I(v)) totlen(Z(v1))
Since I(vi) contains (i','' + +,, jJ. we have
totlen(I(w1)) 2 totlen((' ..)) tot.en((i..))
Combining the above gives totlen(Z(vz)) 2 totlen( (otten((é,,))/3 [i.j))/8.
At this point, the edge (V1, U2) already satisfies the first two conditions: For the first, we note that (12) S 1,...,J and is thus disjoint from 21,2...., 1}. For the second, we have already shown that totlen (I(oz)) totlen([i. f1)/8. However, the last condition sizc(U2) S size(U)) /22 might not hold in general.
Fortunately, this issue can be resolved via yet another case analysis. If B2 is a leaf node, we immediately have the third condition, size(uz) such that 4, > totlen (I(v2))/ 22 would have a child ny that is a leaf corresponding to the i i' block. In this case, (12, 13)) would be the desired edge, since totlen(I(v))) totlen (lé, j))/ 16 and size(vs) = 1 < (1z)(2)/22 Finally, if I(v2) does not contain long block, U2 must have two children U3 and v4 such that
I size(vn)/2. If there exists i E I(w²)
totlen([(v))) 2
size(us) + size(vi) = size(vz) and min ((otlen([(vx))) totlen(I(v..)) (otlen(I(vz))
4
Without loss of generality, assume that size(vs) S size edge, since totlen(I(ws)) 2 totlen([(v2))/4 2 totlen (i, /))33.
size(1z)) 12) Then, (12, U3) gives the desired
D Proof of Theorem 4
We prove Theorem in this appendix. Compared to the proof for constant probability sequences (Proposition 14), our analysis essentially reduces the k-monotone case to the constant pz case by showing that every k-monotone p" contains a sufficiently long subsequence, such that the length of the subsequence times the minimum value almost matches Σn-1 p4-
Again, such node must exist, since ug satisfies (i','' 1, 1,.....) j} C I(us).
16

---

Lemma 15. For any k-monotone sequence p" = (Po. P .T. [0, 1]", there exists a contigu-
ous subsequence (p, P Pit.......... such that
-i++1) min(p, Pl DJ} ( log n.)
1==
Proof. By definition of k-monotone sequences, p* can be partitioned into most it contiguous subsequences, each of which is monotone. Therefore, there exist 0 S ip I jo S n - such that: (1)
1n-1 (Poy:Po+11:-- ................................ Pj.) is monotone; (2) S == Σ Pi 2t= Pj.
Without loss of generality, we assume that (p% Pig.t........................... .,jo) is non-decreasing: the non-increasing case can be handled symmetrically. We claim that there exists E {0o, io - ,.. such that
S
(i -
H
where Hn := + + + Oloog n). Assuming this claim, (pi.P4+1.... .pj.........p............p...... gives the desired subsequence, as it non-decreasing and satisfies
s Et= Pi O(k log
(io - 1+ min(p). P P/ (jo 1)
Hn
To prove this claim, suppose towards a contradiction that, for every E fio. to + ........ jo), it holds that (jo- - - 1): p H.,
S It then follows that
jo S
S
S 30 -0+111
P
jot- S
Hn
11,
1=
1=10
a contradiction.
Finally, we prove Theorem 4 using Lemma 15 and an argument similar to that of Proposition 14.
Proof of Theorem 4. We start with the high-probability upper bound on [T]. Let mi := >1= Pł. Since IT| is the sum of independent Bernoulli random variables with means pū, Pi...., P have [[ = my, and multiplicative Chernoff bound gives
Pr [[T] > 2mro] S mmo/3
To lower bound ÜT), we apply Lemma 15 to obtain contiguous subsequence (Vig, P1..1......... of px such that
Er PT
mo
(jo io + 1). Pmin
O log
O log
where Pmin min Pi, pi ....... P denotes the minimum entry in the subsequence. Let Lo
O(k log" (jo in + 3). Note that we may assume jo in + 2 2T. without loss of
Pai
mo
generality; otherwise, we would have ma = (k log? n), in which case the 22mo/ (k: log2 n:) lower bound on (T) would trivially follow from Ü(T) > 1.
Good event E. Next, we define "good event" which will be shown to imply lower bound on U(T) and happen with high probability. For each /. (in, + 1.....jo Lo + 1}, let &, denote the event that T [t, + Lo 1] o Let E = n jo- Lo+1 E, be intersection of these events. In other words, the event that (io. in + ,o. contains no To consecutive elements such that none of them is included in T.
17

---

Event & implies lower bound on Ü. When event & happens, both
T [io; in Lo 1] and
Tn Ló To + 1, 1o
are non-empty. Thus, if we list the elements in T n jol in increasing order:
to < t
fm':
must have ln S + and lmm 2 1 Lo Furthermore, for every neighboring entries 4-11 and 4 (i E (m']) we must have 4-44-1 S Lo: otherwise, 44-1+1,44 44-1+1,4--+22..... (+ E (4-1,44 would give Lo consecutive elements that outside T, contradicting event E.
Let C = (41, .......... subsequence
.mm .e......m............. the block representation of instance T. Note that & contains a contiguous
(f2 - to, l2 11.-.., lmm - imm-1)
that corresponds the m' 1 stopping times (lo, .y,..., (.))...mm)).... Then, event & implies that every entry 4 4--1 is at most Lg. Furthermore, the sum of these mn' entries is given by
m
(t. - (i-1) = tm - to 2 (50 Lo + (6o + Lo 1) Cio i0 + 1) 2Lo + 1.
1=1
Therefore, by definition of U, & implies that
Σ/ (1 - (4-1)
2Lo + (jo - i0 1)
30 - i0 +
Ú(T)= 2 max - to 12 tl,..., m'm mm
2.
Lo
Lo
Finally, since Lu =
O(k log m) (5o - io + 1). the above gives a lower bound of Ω
my log" x2
mo
A
Event & happens with high probability. fio, to + -1....:o -o Lo + 1}. For each E {0, I..... Lo 1}, we have + i E [o]. which
remains show that Pr [8] 2 1/n, Fix
implies pi+: min Pig +1 ... = Pmin follows that
Pr Ed = Pr n ft, Lu - 1] =
II (1 pi++) s
II
(1
Pmin)
(pi+s 2 Pmii)
1=0
i=0
exp(
Pmin
To) S
(1 - 1-pSSeT S Ln 2 (2 Priin)
n²
By the union bound, have
do Lo+1
1
1
Pr
n
n
t=
This completes the proof.
E
Instance with O(1/((C)) Worst-Case Error
Proposition 16. For every k 2, there PLS instance such that: (1) (I)Ū(L) 2k; (2) There is forecasting algorithm with an O(1kk) worst-case error on L.
Proof. Fix A: 2 2. We construct a sequence instances L1, C2.... as follows:
Li = 1,.....) 1) is the all-one sequence of length 2k.
For every h 2 we set
LA ((k 1 (2k)^-1) ((k 1)Lh-1);
where denotes sequence concatenation, and (I: Ca denotes the sequence obtained from Lz-1 by multiplying every entry by A -- 1.
18

---

By simple induction on h, the sum of entries in each LA is given by ny (2k)": When h = 1, we indeed have n1 = 2k: = (2k)² For each h 2 2, assuming PA-1 = (2k)n-1 we have
n 2(k: 1) nh + (2k) (2k)
Therefore, for each 2 2, the middle entry in Lr. 2 (2k)"=1, constitutes (1/k:)-fraction of the copies of Lh-1 scaled up
entire sequence length n4. Before and after this middle entry factor of k - 1.
In the rest of the proof, show that Ü (Cx)) 2/ for every h 2 1. Furthermore, for all sufficiently large h, CA admits a forecaster with an (L/kk) worst-case error. These two claims would then prove the proposition.
Analyze the approximate uniformity. We start with the direction that ((C)) 2 2k. By construc- ......... 12x). .2.............. are exactly given by (k: (1-1) times L1. Thus, the
tion, the first 2h entries of Lh, (11,
definition of U gives
+ la + l2a
Ü(C))= 2 max (1, .,,,,.,,,...
2k.
For the other direction, we show that ((Cs) s 2k by induction on h. When h = 1, we clearly have (f1) 2k. Assuming (fn-)) I 2k, we analyze Lu. Consider an arbitrary contiguous subsequence (4,, (4.4441....144) in Ln. If the subsequence contains the middle entry 2 (2k)* >2k))=11 we would have
+ 4+1 + max 44......... 4 2 (2k)
n1h
(2h)
2. (2k)--1 = k $ 2k.
must be contiguous subsequence of Lx-1 scaled up by factor 1. It then follows from the induction hypothesis that
Otherwise, (4,, .............. (1)
4 + 1.+1 + ................................ +1
max 4441.... < (((r-)) < 2k.
Therefore, Ü(C)) 2k holds for every h 2 1.
Upper bound the worst-case error. Next, we give a forecasting algorithm for Cr, which is similar to both the algorithms of [Drul3, QV19] as well as our Algorithm 2:
If h 1, there are 2k blocks of equal length. Predict that the average of the last & blocks is the same as that of the first blocks.
h > 1, La consists of three parts: the left half, the middle entry (2k)^-1, and the right half. With probability 1/h, predict that the average of the right half is the same that of the left half. With the remaining probability 1/h, run the same algorithm recursively on either the left or the right half, with equal probability.
For each h 2 1 and j [0, 1), let L(h, 14) denote the highest possible squared error that the algorithm above incurs on instance LA when the sequence has an average of μ. We will prove by induction that
L(h, 1) I (()) + K'
where d(x) x(1 z). It then follows that, for every h k. there is forecasting algorithm for Cn. with worst-case error of (1/k) (L)))
Base case. For the base case that h = 1, let Ya and μl2 be the averages of the two halves, respectively.
Clearly, lh #12 2p and the algorithm incurs squared error of (μ1 22)2. 2 It follows that
L(I,)) <
sup (p1 =22)
in #1-02E10.11 #222222
We note the identity
+
((a) + ((b)
(a b)2
Φ
+
(2)
2
2
4
19

---

which is a special case of Equation (1) when c 1. Therefore, for any fl. R2 E [0, 1] that satisfy
Ni + H2 2μ.. have
11 + 12
(w) p2) =40 40
2((((1)) + [(22)] S 46(1).
2
Thus, verified the base case that
5. - x(H)
Inductive step. Consider h 2 2 and assume that the induction hypothesis holds for L(h 1, pr). Recall that Ln consists of a left half, a middle block that constitutes (1/k)-fraction of the total length, and right half. Moreover, the two halves are scaled copies of L Let f41 and μl denote the averages of the two halves, respectively. Let fo denote the average of the middle block. Then, we have
1
P1 +
M22
1
/1
140-
k
2
k.
It follows that
M1 + 122
(1) + M2) 140
11
2
Therefore, have
(M) u2)² h-1
L(h - 1, + L(h 1, 122
L(h,p) S
MI |
h
h
2
Iag lug
2//52/k
Plugging the induction hypothesis L(h 1, S --1 x(() + &/4 into the above gives
(in n2)²
x(m) + x(u2)
h 1 4
I(h, 14)
sup 100 les 101t122 3//
+
h
k
Applying Equation (2) to the supremum above shows that
f1 +
h - 1
4
L(h, $
sup Plo 1 2u
+
2
h k.
Finally, since (bx)) xx(1 x)) is i-Lipschitz on [0, 1), the constraint I 112 that @i t is (1/k))close to (M)). Therefore, conclude that
2pl S 2/k implies
L(h, - n. (own + 1 +
4 k
4 k
This completes the inductive step and thus finishes the proof.
20

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims made in the abstract and introduction are formally stated in Section 1.2, and they apply to the problem setting formally introduced in Section 1.1. They accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
The discussion in Section 5 discusses the remaining gap in the theoretical results, and suggests directions for future work.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
21

---

Answer: [Yes]
Justification: The assumptions are clearly stated either as part of the problem formulation (Section 1.1) in the theorem statements (Section 1.2). All the theoretical results have proofs, in either the main paper or the appendices.
Guidelines:
The answer NA means that the paper does include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
22

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: wtips.cc/ppblcc//eeeccc hwt.diiciggiie...eeeee /CodeSubmia ossoiicy)))) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
23

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips:
lnes??
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work is purely theoretical and there is no immediate societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
25

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
26

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https (https://neet http:///eeuu/eeeeeeeeeeee http://uuripscccoooeeeeeeeeeeeee / for what should or should be described.
27


Reviews:
[{"review_id": "28NAlvtGl7", "reviewer": "Reviewer_KCsM", "summary": "The paper addresses the following problem. In an on-line fashion, $n$ numbers from $[0,1]$ arrive one after the other. The learning agent chooses a moment $t$ to stop and a time horizon $w$ and then tries to guess the average of the next $w$ numbers. No assumption is made about the numbers, so the framework is adversarial.\n\nIt is known from the earlier work that this problem has a solution with $o(1)$ loss as $n\\to\\infty$ (which is quite surprising). This paper deals with the situation when there is a restricted set of possible stopping moments. The result is an upper and lower bound in terms of a combinatorial characteristic of the sequence of stopping moments. If the sequence is exponentially sparse, the worst-case error is $\\Omega(1)$.\n\nThere is also a study of a probabilistic setup, where every moment can be a stopping moment with some probability. Matching upper and lower bounds are obtained for this case.", "questions": "None", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "I believe the paper neatly resolves a nice and clearly defined problem.\n\n\nThe problem is not very popular in the community and the literature review is, correspondingly, quite short. The problem, to my knowledge, has no immediate applications. Still I believe the result is nice and warrants publication.", "was_revised": true, "final_justification": "Based on the discussion, I would keep my assessment of the paper.", "rebuttal": "Thank you for your review!"}, {"review_id": "hNDYS0bWK7", "reviewer": "Reviewer_2Tme", "summary": "This paper studies the problem of prediction with limited selectivity (PLS), where a forecaster observes a sequence and must choose when and over what window to predict the future mean, using a restricted set of stopping times. The paper introduces approximate uniformity and show that the worst-case prediction error can be bounded in terms of it. The paper provides matching upper and lower bounds up to logarithmic factors, and show that these bounds are tight with high probability when stopping times are randomly generated from a k-monotone distribution.", "questions": "1. The algorithm predicts the mean of future blocks by using the mean of past blocks. Is there any assumptions on stationarity of data that supports this? Why should we expect the past data be indicative of the future data?\n2. Lemma 8: The lemma only says that there exist a merge that satisfy this, but how could this merge be found? \n3. Proof of Lemma 8: T appears to be an tuning parameter to control the max/min ratio of merged block lengths to C. Why is T = M/(C-1) the right choice? \n4. Section 4 mentions that this is a warm up, but it would help to highlight what challenges arise when $p^\\ast$ is not uniform, and how these uniform-case techniques will generalize.", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I am not an expert on online learning with prediction, so I may not have assessed the strength and weakness appropriately. From what I can tell, the results and the analysis techniques are new. The techniques developed in this paper has potentials to be applied elsewhere. The high level idea of connecting locally random structure to approximate uniformity may also be useful in other online learning problems.\n\nThe main issues are 1. the algorithm seems to assume access to the block partitioning of the input (i.e., the sequence of block lengths), this is often unrealisitic in applications. 2. Theorem 1 seems to be established under some merge. But it is unclear to me how this merge might be found.", "was_revised": true, "final_justification": "The paper has audience at NeurIPS and based on my knowledge of the literature, the results are new and may inspire followup works. Thus I think the work deserves acceptance.", "rebuttal": "Thank you for your review!\n\n---\n\nRegarding 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.\n\nRegarding 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.\n\n---\n\nWe answer your questions in the following:\n\n1. 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]).\n\n    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.\n\n2. 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.)\n\n3. 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)$.\n\n4. Thank you for the comment! We will add the following explanation on the transition from uniform $p^\\star$ to general $k$-monotone $p^\\star$.\n\n    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."}, {"review_id": "htf8JzUalA", "reviewer": "Reviewer_Y8tU", "summary": "This paper introduces a new theoretical model called Prediction with Limited Selectivity (PLS), which is a generalization of the existing selective prediction framework. In this model, a forecaster predicts the average of future values in a sequence but can only initiate a prediction at specific, predetermined times. The authors introduce a complexity measure called \"approximate uniformity\" to provide instance-dependent upper and lower bounds on the worst-case prediction error. The paper shows that for randomly generated instances, these bounds match with high probability, making them nearly tight.", "questions": "Questions for Authors:\n1. In the proof of Lemma 8, the procedure for merging blocks seems central to the main result. Could you provide a small, concrete example of this greedy procedure to help solidify the reader's understanding?\n2. The ternary tree construction in Definition 7 is a key innovation for the lower bound proof. Is there an intuitive reason why a ternary, as opposed to a binary, structure is necessary to handle blocks of varying lengths? Does it relate to the three cases a sub-problem can fall into (left, right, or dominated by a single large block)?\n3. The average-case analysis focuses on k-monotone sequences for the inclusion probabilities p*. What is the motivation behind this specific choice? Does this structure arise in practical scenarios, or is it chosen primarily for its analytical tractability?", "limitations": "No serious limitation", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\nThis is a well-written and theoretically sound paper that addresses a novel and practical extension of the selective prediction problem. The key strengths are:\n1. Novel Problem Formulation: The PLS model is a natural and well-motivated generalization of selective prediction. The examples provided, such as weather forecasting for outdoor activities or market predictions during specific trading seasons, effectively illustrate the real-world relevance of limited prediction opportunities.\n2. Significant Theoretical Contributions: The introduction of the \"approximate uniformity\" measure, Ũ(L), is a key contribution that provides an intuitive way to quantify the difficulty of a given PLS instance. The main results (Theorems 1 and 2) provide both upper and lower bounds on the worst-case error in terms of this measure, which is a strong theoretical result.\n3. Rigorous Analysis: The proofs are detailed and build upon prior work in a non-trivial way. For instance, the proof of the Ω(1/log m) lower bound involves a novel hierarchical decomposition using a ternary tree, extending the binary tree construction used in previous work.\n4. Average-Case Analysis: The paper doesn't stop at worst-case instance analysis. It provides an average-case analysis for randomly generated stopping time sets, showing that the derived bounds are tight with high probability under these conditions. This significantly strengthens the results.\n\nWeaknesses and Areas for Improvement:\nWhile the paper is strong, there are a few areas where it could be improved:\n\n1. Clarity on \"Hard\" Instances: The paper proves an Ω(1) worst-case error for specific PLS instances, such as those with geometrically increasing block lengths or a Cantor set-like structure. While this is a powerful result, it would be beneficial to provide more intuition as to why these structures are inherently difficult to predict. A brief discussion on how the lack of \"uniformity\" prevents the forecaster from finding a predictable scale would be helpful.\n2. Gap Between Bounds: The authors correctly point out the gap between the upper bound of O(1/log Ũ(L)) and the lower bound of Ω(1/[Ũ(L)]²). While they prove this gap is unavoidable for their complexity measure, it remains the central open question. The discussion in Section 5 is good, but it could be slightly expanded to speculate on what a more exact complexity measure might look like, perhaps drawing more from the properties of the Cantor set-based instances mentioned.\n\nMinor Notational Clarifications: The paper is generally very clear, but some notations could be briefly reiterated. For example, when discussing the proof of Theorem 11, a quick reminder of what µi (the value of the i-th block) represents would aid readability as the reader navigates complex proofs.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review!\n\n---\n\nRegarding 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.\n\nRegarding 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.\n\n---\n\nWe answer your questions in the following:\n\n1. 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$.\n\n    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:\n\n    - 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$.\n\n    - We continue at index $4$: Merging $(4, 1)$ gives a total length of $l'_2 = 5$.\n\n    - Starting at index $6$, we merge $(1, 5)$ to obtain a total length of $l'_3 = 6$.\n\n    - 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.\n\n    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$.\n\n2. 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.\n\n3. 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])\n\n---\n\n[DDS12] Constantinos Daskalakis, Ilias Diakonikolas, and Rocco A. Servedio. Learning k-Modal Distributions via Testing. SODA 2012\n\n[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"}, {"review_id": "wb4B5Iex62", "reviewer": "Reviewer_HA5F", "summary": "This paper introduces Prediction with Limited Selectivity (PLS), a variant of selective prediction where forecasters can only make predictions on a predetermined subset of timesteps (rather than any time). The authors develop a complexity measure called \"approximate uniformity\" and establish instance-dependent upper and lower bounds on the optimal error. They also provide an average-case analysis on k-monotone sequences.", "questions": "See Weaknesses.", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\n1.  The proposed PLS model addresses realistic constraints where forecasters have limited selectivity, extending selective prediction to practical scenarios. The provided examples (weather forecasting, trading restrictions) are compelling and demonstrate clear real-world relevance.\n\n2. The author provides a clean theoretical framework. The introduced \"approximate uniformity\" naturally extends the fully-selective to the limited-selective scenarios and captures the hardness of a PLS instance. Using this notation, the paper establishes matching upper and lower bounds.\n\n\n### Weaknesses\n\n1. The paper is entirely theoretical with lack of empirical evidence. The motivating examples (weather, trading restrictions) are compelling, but there is no simulation demonstrating the algorithm's behavior on synthetic or real sequences. Even small-scale experiments on synthetic or real sequences would help readers gauge convergence speed and constant factors.\n\n2. There is a still large gap between upper ($O(1 / \\log (\\tilde{U}))$) and lower bounds ($\\Omega (1 / \\tilde{U}^2)$) on individual instances, which might limit the understanding on worst-case's precision. A short empirical illustration (toy instances displaying the gap) or discussion could strengthen intuition.", "was_revised": false, "final_justification": "", "rebuttal": "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."}]

Author rebuttal:

Meta-review: This paper considers a novel setting of online prediction with limited selectivity (PLS), wherein there is a pre-defined set of time steps at which the learner is allowed to optionally terminate the game and make a prediction about the average over a number of the next time steps that the learner can decide. This setting generalizes the fully-selective case that was studied earlier and is well motivated by real-world situations. The paper provides the following scientific claims and findings: First, a novel complexity measure that captures the hardness of PLS, in the sense that characterizes both an upper bound and a lower bound of the worst-case instance-dependent prediction error. They also show that their upper and lower bounds match up to a constant factor with high probability when the problem instance is generated randomly according to a $k$-monotone sequence. 

**Strengths**: Novel theoretical model of problem for online prediction with limited selectivity, solid theoretical results that give new understanding to PLS via worst-case analysis and average-case analysis. The technical proof ideas and analysis in the paper could potentially helpful for the ML community. 

**Weaknesses**: Some concerns about the lack of empirical evaluations and the consideration of a model general model such as unknown stopping times, these are not major concerns and out of scope of the setting that the paper begins with. 

Important reasons for accept: See Strengths. 

During the review and discussion, all the reviewers appreciate the solid theoretical and conceptual contributions of the paper. All the points raised by the reviewers during the review (mostly minor to my understanding) were well clarified by the authors. The paper easily make a cut.
Decision: Accept (spotlight)