Fast rates for prediction with limited expert advice
Year: 2021

Abstract:
We investigate the problem of minimizing the excess generalization error with respect to the best expert prediction in a finite family in the stochastic setting, under limited access to information. We assume that the learner only has access to a limited number of expert advices per training round, as well as for prediction. Assuming that the loss function is Lipschitz and strongly convex, we show that if we are allowed to see the advice of only one expert per round for T rounds in the training phase, or to use the advice of only one expert for prediction in the test phase, the worst-case excess risk is Ω(1/ √ T ) with probability lower bounded by a constant. However, if we are allowed to see at least two actively chosen expert advices per training round and use at least two experts for prediction, the fast rate O(1/T ) can be achieved. We design novel algorithms achieving this rate in this setting, and in the setting where the learner has a budget constraint on the total number of observed expert advices, and give precise instance-dependent bounds on the number of training rounds and queries needed to achieve a given generalization error precision.

text: √ T ) with probability lower bounded by
a constant. However, if we are allowed to see at least two actively chosen expert advices per training round and use at least two experts for prediction, the fast rate O(1/T ) can be achieved. We design novel algorithms achieving this rate in this setting, and in the setting where the learner has a budget constraint on the total number of observed expert advices, and give precise instance-dependent bounds on the number of training rounds and queries needed to achieve a given generalization error precision.
Keywords: Online Learning, Budgeted Learning, Prediction with expert advice.

heading: 1 Introduction and setting
text: We consider a generic prediction problem in a stochastic setting: a target random variable Y taking values in Y is to be predicted by a user-determined forecast F , also modeled as a random variable, taking values in a closed convex subset X of Rd. The mismatch between the two is measured via a loss function l(F, Y ). The quality of the agent’s output is measured by its generalization risk
R(F ) := E [ l(F, Y ) ] .
To assist us in this task, the forecast or “advice” of a number of “experts” (F1, . . . , FK) (also modeled as random variables) can be requested. The agent’s objective is to achieve a risk as close as possible to the risk of the best expert R∗ = mini∈JKKR(Fi) (for a nonnegative integer n, we denote JnK = {1, . . . , n} ). We measure the performance of the user’s forecast via its excess risk (or average regret) with respect to that best expert.
The literature on expert advice generally considers the cumulative regret over a sequence of forecasts Ft followed by observation of the target variable Yt and incurring the loss l(Ft, Yt), t = 1, . . . , T . In the present work we will separate observation (or training) phase and forecast phase: the user is allowed to observe (some of) the expert’s predictions and the target variable for a number of independent, identically distributed rounds (Yt, F1,t, . . . , FK,t)1≤t≤T following certain rules to be specified. After the observation phase, the user must decide of a prediction strategy, namely a convex combination of the experts F̂ = ∑k i=1 ŵiFi, where the weights ŵi can be chosen based on the information gathered in the training phase. The risk of this strategy is R(F̂ ), where the risk is evaluated on new, independent data. In other words, if the training phase takes place over T independent rounds, the forecast risk is the expected loss over the (T + 1)th, independent, round.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
In some situations, it may be overly expensive to query the advice of all experts at each round. The cost can be monetary if each expert demands to be paid to reveal his opinion, possibly because they have access to some information that others do not. In this case we may have a total limit on how much we can spend. In a different context, it is unrealistic to ask for the advice of all available doctors or to run a large battery of tests on each patient. In this case, we may be have a strong limit on the number of expert opinions that can be consulted for each training instance. In a more typical machine learning scenario, each “expert” might be a fixed prediction method Fi = fi(X) (using the information of a covariate X), where the predictor functions fi have been already trained in advance, albeit based on different sets of parameters or methodology; the goal then amounts to predictor selection or aggregation, in a situation where the computation of each single prediction constitutes the bottleneck cost, rather than data acquisition. Overall the agent’s goal is to achieve a risk close to optimal while sparing on the number of experts queries – both at training time and for forecast.
Motivated by these questions we investigate several scenarios for prediction with limited access to expert advice. Furthermore, our emphasis is on obtaining fast convergence rates guarantees on the excess risk (i.e. O(1/T ) or O(1/C), where C is the total query budget). These are possible under a strong convexity assumption of the loss, specified below. Our contributions are the following.
• As a preliminary, we revisit (Section 3) the full information setting, with no limitations on queries. Maybe surprisingly, we contribute a new algorithm that is both simpler than existing ones and for which the proof of the fast convergence rate for excess risk is also elementary. Furthermore, for forecast we only need to consult 2 experts. The general principle of this algorithm will be reused in the limited observation settings.
• We then investigate (Section 4) the budgeted setting where we have a total query budget constraint C for the training phase; then (Section 5) the two-query setting where the agent is limited to m = 2 queries per training round. In both cases, we give precise efficiency guarantees on the number of training expert queries needed to achieve a given precision for forecast. The obtained bounds come both in instance-independent (agnostic) and instancedependent (depending on the experts’ structure) flavors.
• Finally, we give some lower bounds (Section 6) were we show that fast rates cannot be achieved if the agent is only allowed to consult one single expert per training round or for forecast.
The following assumption on the loss will be made throughout the paper: Assumption 1. ∀y ∈ Y: x ∈ X ⊆ Rd 7→ l(x, y) is L-Lipschitz and ρ-strongly convex.
Recall that a function f : X → R is L-Lipschitz if ∀x, y ∈ X :|f(x)− f(y)| ≤ L‖x− y‖, and ρ-strongly convex if the function: x→ f(x)− ρ 2
2 ‖x‖ 2 is convex.
Remarks. Assumption 1 implies that the diameter of X is bounded by 8L/ρ2 and the quantity supx,x′∈X ,y∈Y |l(x, y)− l(x′, y)| is bounded by B := 8L2/ρ2 (this notation shorthand will be used throughout the paper). Consequently, without loss of generality we can assume that the loss is bounded by B (see Lemma1 S-1 and subsequent discussion for details). It is satisfied, for example, in the following setting: least square loss l(x, y) = (y − x)2 where x ∈ X and y ∈ Y with X and Y are bounded subsets of Rd. Prior knowledge on ρ is not necessary if L and an upper bound on the the l∞ norm of the target variable Y and the experts are known.

heading: 2 Discussion of related Work
text: Games with limited feedback (slow rates): Our work investigates what happens between the full information and single-point feedback games. Learning with a restricted access to information was considered under various settings in [6], [19], [12], [20], [5]. A setting close to ours was considered in [21], where the agent chooses in each round a subset of experts to observe their advice, then follows the prediction of one expert. To minimize the cumulative regret in the adversarial setting, they used an extension of the Exp3 algorithm, which allows to have an excess risk of O( √ 1/T ) in the limited
feedback setting and O( √ log(C)/C) in the budgeted case with a budget C.
1References starting with a prefix S- point to the supplemental material.
The differences in the setting considered here is that (a) we are interested in the generalization error in the stochastic setting rather than the cumulative regret in an adversarial setting and (b) our assumptions of the convexity of the loss allow for the possibility of fast excess risk convergence. Moreover, we consider the more general case where the player is allowed to combine p out of K experts for prediction. The possibility of playing a subset of arms was considered in the literature of Multiple Play Multi-armed bandits. It was treated with a budget constraint in [26] for example (see also [24]), where at each round, exactly p out of K possible arms have to be played. In addition to observing the individual rewards for each arm played, the player also learns a vector of costs which has to be covered with an a-priori defined budget C. In the stochastic setting, a UCB-type procedure gives a bound for the cumulative regret of O(∆−1min log(C)/C) that holds only in expectation, where ∆−1min denotes the gap between the best choice of arms and the second best choice. This bound leads to an instance dependent bound of O( √ log(C)/C) in the worst case. In the adversarial setting, an
extension of Exp3 procedure gives a bound of O( √
log(C)/C) for the cumulative regret that holds with high probability. In another online problem, where the objective is to minimize the cumulative regret in an adversarial setting with a small effective range of losses, [11] have shown the impossibility of regret scaling with the effective range of losses in the bandit setting, while [23] showed that it is possible to circumvent this impossibility result if the player is allowed one additional observation per round. However, in the settings considered, it is impossible to achieve a regret dependence on T better than the rate of O(1/ √ T ).
Fast rates in the full information setting: The learning task of doing as well as the best expert of a finite family in the sense of generalization error has been studied quite extensively in the full information case. In an adversarial setting, it is well-known that under suitable assumptions on the loss function (typically related to strong convexity), an appropriately tuned exponential weighted average (EWA) strategy has cumulative regret bounded by the “fast rate” O(log(K)/T ) [13, 9, 4], which, combined with the online-to-batch conversion principle [8, 4] (also known as progressive mixture rule, [7, 25]), yields a bound of the same order for the expected excess prediction risk in the stochastic case. However, it was shown that progressive mixture type rules are deviation suboptimal for prediction [2], that is, their excess risk takes a value larger than c/ √ T with constant positive probability over the training phase. To lift the apparent contradiction between the two last statements, consider that the excess risk of the EWA can take negative values, since it is an improper learning rule. Thus negative and positive “large” deviations can compensate each other so that the expectation is small. The inefficiency of EWA in deviation is a significant drawback, and alternatives to the EWA progressive mixture rule that achieve O(log(K)/T ) excess prediction risk with high probability were proposed by [17] and [3]. In [17], the strategy consists in whittling down the set of experts by elimination of obviously suboptimal experts, and performing empirical risk minimization (ERM) over the convex combinations of the remaining experts. In [3], the empirical star algorithm consists in performing an ERM over all segments consisting of a two-point convex combination of the ERM expert and any other expert. Note that the empirical star algorithm has the advantage that the final prediction rule is a convex combination of (at most) two experts.
Linear regression with partially observed attributes: Other related work is that of [10], and [14] on learning linear regression models with partially observed attributes. The most related setting to ours is the local budget setting, where the learner is allowed to output a linear combination of features for prediction. The key idea is to use the observed attributes in order to build an unbiased estimate of the full information sample, then to use an optimization procedure to minimize the penalized empirical loss. In our setting, the minimization of penalized empirical loss was shown to be suboptimal (see [16]). Moreover, while we want to predict as well as the best expert, in [10], the objective is to be as good as the best linear combination of features with a small additive term (the optimal rate, in this case, is O ( 1/ √ T ) ). Finally, we consider that the restriction on observed attributes (experts advice) does not apply only to the training samples but also to the testing data.
Online convex optimization with limited feedback: The idea of using multiple point feedback to achieve faster rates appeared in the online convex optimization literature (see [1], and [22]). It was shown that in the setting where the adversary chooses a loss function in each round if the player is allowed to query this function in two points, it is possible to achieve minimax rates that are close to those achievable in the full information setting. The key idea is to build a randomized estimate of the gradients, which are then fed into standard first-order algorithms. These ideas are not convertible into our setting because we consider a non-convex set of experts.

heading: 3 The full information case
text: In this section, we revisit the “classical” case where there is no constraint on the number of expert queries per observation round; assume the output of all experts are observed for T rounds (in other words, T i.i.d. training examples), which is the full information or “batch” setting. We want to output a final prediction rule with prediction risk controlled with high probability over the training phase.
We start with putting forward an apparently new rule , simpler than existing ones [17, 3], for the full information setting which, like the empirical star [3], outputs a convex combination of two experts. In contrast to the latter, our rule does not need any optimization over a union of segments. The underlying principle will guide us to construct a budget efficient expert selection rule in the sequel.
Define R̂(Fi) := T−1 ∑T t=1 l(Fi,t, Yt) the empirical loss of expert i, and d̂ij := (T −1∑T t=1(Fi,t − Fj,t) 2) 1 2 the empirical L2 distance between experts i and j over T rounds. Finally let α = α(δ) := (log(4Kδ−1)/T ) 1 2 , where δ ∈ (0, 1) is a fixed confidence parameter. Define
∆ij := R̂(Fj)− R̂(Fi)− 6αmax { Ld̂ij , Bα } . (1)
The quantity ∆ij can be interpreted as a test statistic: if ∆ij > 0, then we have a guarantee that R(Fj) > R(Fi), so that expert j is sub-optimal; this guarantee holds for all (i, j) uniformly with probability (1− δ). It therefore makes sense to reduce the set of candidates to
S := { j ∈ JKK : sup
j∈JKK ∆ij ≤ 0
} . (2)
Our new full information setting rule is the following:
choose k̄ ∈ S arbitrarily ; pick j̄ ∈ Arg Max j∈S
d̂k̄j ; predict F̂ := 1
2 (Fk̄ + Fj̄). (3)
In words, the above rule consists in eliminating all experts that are manifestly outperformed by another one, and, among the remaining experts, pick two that disagree as much as possible (in terms of empirical L2 distance ) and output their simple average for prediction. The next theorem establishes fast convergence rate for the excess risk of this rule:
Theorem 3.1. If Assumption 1 holds and δ ∈ (0, 1) is fixed, then for the prediction rule F̂ defined by (3), it holds with probability 1− 3δ over the training phase (c is an absolute constant):
R(F̂ ) ≤ R∗ + cB log(4Kδ −1)
T .
Proof. Let d2ij = E [ (Fi − Fj)2 ] . The result hinges on the following high confidence control of risk differences, established in Corollary S-4 as a direct consequence of the empirical Bernstein’s inequality: with probability at least 1− 3δ, it holds:
For all i, j ∈ JKK : ∆ij ≤ (Rj −Ri) ≤ ∆ij + 32αmax(Ldij , Bα). (4) Let i∗ ∈ Arg Mini∈JKKRi be an optimal expert. Since Ri∗ −Rj ≤ 0 for all j ∈ JKK, it follows that if (4) holds, then i∗ ∈ S, from the definition of S. So if (4) holds, we have
R
( Fk̄ + Fj̄
2
) ≤ 1
2
( Rk̄ +Rj̄ ) − ρ 2
8 d2k̄j̄
= R∗ + 1
2
( (Rk̄ −Ri∗) + (Rj̄ −Ri∗) ) − ρ 2
8 d2k̄j̄
≤ R∗ + 1 2
( ∆k̄i∗ + ∆j̄i∗ ) + 16α ( max ( Ldj̄i∗ , Bα ) + max(Ldk̄i∗ , Bα) ) − ρ 2
8 d2k̄j̄
≤ R∗ + 32Bα2 + 48Lαdk̄j̄ − ρ2
8 d2k̄j̄ ;
where we have used strong convexity of the loss (and therefore ofR(.) with respect to the L2 distance) in the first line; the right-hand side of (4) in the third line; and, in the last line, the fact that j̄, k̄, i∗ are all in S along with dj̄i∗ ≤ dj̄k̄ + dk̄i∗ ≤ 2dj̄k̄ by construction of j̄. Finally upper bounding the value of the last bound by its maximum possible value as a function of dk̄j̄ and recalling B = 8L
2/ρ2, we obtain the statement.

heading: 4 Budgeted Setting
text: In this section, we consider the budgeted setting. More precisely, given an a-priori defined budget C, at each round the decision-maker selects an arbitrary subset of experts and asks for their predictions. The choice of these experts may of course depend on past observations available to the agent. The player then pays a unit for each observed expert’s advice. The game finishes when the budget is exhausted, at which point the player outputs a convex combination of experts for prediction.
We convert the batch rule defined in the full information setting to an "online" rule by performing the test ∆ji > 0 for each pair (i, j) after each allocation. If at any round an expert i ∈ JKK fails any of these tests (i.e ∃j : ∆ji > 0), it is no longer queried. This extension allows us to derive instance dependent bounds, which cover the rates obtained in the batch setting in the worst case.
Since the tests ∆ij > 0 are performed after each allocation, we introduce the following modification on the definition of ∆ij , for concentration inequalities to hold uniformly over the runtime of the procedure. We define ∆ij(t, δ) as follows:
∆ij(t, δ) := R̂(j, t)− R̂(i, t)− 6α(t, δ/(t(t+ 1)) max { Ld̂ij(t), Bα(t, δ/(t(t+ 1)) } .
Algorithm 1 Budgeted aggregation Input δ, L and ρ. Initialization: S ← JKK. for T = 1, 2, . . . do
Jointly query all the experts in S and update ∆ij > 0 for all i, j. For all i, j ∈ JKK, if ∆ij > 0, eliminate j: S ← S \ {j}. if the budget is consumed then
let k̄ ∈ S, and l̄← argmax j∈S d̂k̄j .
Return 12 (Fk̄ + Fl̄). end if
end for
Let S∗ := Arg Mini∈JKKR(Fi) denote the set of optimal experts. For i, j ∈ JKK, we denote by dij := (E[(Fi − Fj)2])1/2 the L2 distance between the experts Fi and Fj . For i ∈ JKK, we introduce the following quantity:
Λi := min i∗∈S∗ max
{ L2d2ii∗
|R(Fi)−R(Fi∗)|2 ;
B
R(Fi)−R(Fi∗)
} .
Define the following set of experts: S = { i ∈ JKK : Λi > 1 } ,
and let Sc be its complementary. Theorem 4.1. (Instance dependent bound) Suppose Assumption 1 holds. Let C ≥ K denote the global budget on queries and denote ĝ the output of Algorithm 1 with inputs (δ, L, ρ) when the budget C runs out. For any ≥ 0, if:
C > 578C log ( Kδ−1C ) ,
where
C := ∑ i∈Sc Λi + |S | min { 1 ; Λ∗ } ,
where Λ∗ := maxi:Λi<+∞ Λi, then, with probability at least 1− δ: R(ĝ) ≤ R∗ + cB ,
where c is an absolute constant.
Remarks. Observe that the above result gives in particular a query budget bound for the problem of best expert identification in our setting, by taking = 0, in which case the required expert query budget is of order ∑ i:Λi<+∞ Λi up to logarithmic terms. We can compare this to the problem of best arm identification in a bandit setting (one arm pull/query per round); our setting can be cast into that framework by considering each expert as an arm and only recording the information of the loss of the asked expert. The known optimal query bound for best arm identification in the classical multi-armed bandits setting with loss/reward bounded by B is of order ∑ i:Λi<+∞ Λ̃i [15], where Λ̃i = B 2(R(Fi)−R(Fi∗))−2. Since the diameter of X is bounded byB/L (see Lemma S-1), it holds Λi ≤ Λ̃i. Hence, for best expert identification, the bound of Theorem 4.1 improves upon the best arm identification bound, potentially by a significant margin (in particular concerning the contribution of suboptimal but close to optimal experts for which dii∗ B/L and Ri −Ri∗ B). Again, the improvement is due to the Assumption 1 on the loss and the possibility to query several experts per round, which are not used when casting the problem as a classical bandit setting.

heading: 5 Two queries per round (m = p = 2)
text: In this section, we suppose that the decision-maker is constrained to see only two experts’ advice per round (m = 2). We suppose that the horizon is unknown; when the game is halted, the player outputs a convex combination of at most two experts (p = 2). We will show that the rates obtained are as good as in the full information case in its dependence on the number of rounds T .
Algorithm 2 works as follows. To circumvent the limitation of observing only two experts per round, in each round, we sample a pair (i, j) ∈ S×S in a uniform way, where S is the set of non-eliminated experts. Then the tests ∆′ji ≤ 0 and ∆′ij ≤ 0 are performed, where ∆′ij is defined by (5). If i or j fail the test, which means that it is a suboptimal expert, it is eliminated from S.
Finally, when the algorithm is halted, depending on the number of allocated samples, we choose either an empirical risk minimizer over the non-eliminated experts or the mean of two experts from S that are distant enough. This rule allows our algorithm’s output to enjoy the best of converge rates of the two methods.
We introduce the following notations: In round t, denote Tij(t) the number of samples where predictions of experts i and j were jointly queried and Ti(t) the number of rounds where the prediction of expert i was queried. Denote R̂ij(j, t) the empirical loss of expert i calculated using
only the Tij(t) samples queried for (i, j) jointly. We define αij(t, δ) := √
log(4Kδ−1) Tij(t) if Tij(t) > 0
and αij(t) =∞ otherwise. Let d̂ij(t) be the empirical L2 distance between experts i and j based on the Tij(t) queried samples. Denote δt := δ/(t(t+ 1)). For i, j ∈ JKK we define:
∆′ij(t, δ) := R̂ij(j, t)− R̂ij(i, t)− 6 max { Lαij(t, δt)d̂ij(t), Bα 2 ij(t, δt) } . (5)
Algorithm 2 Two-point feedback Input δ, L and ρ. Initialization: S ← JKK. for T = 1, 2, . . . do
Let (i, j) ∈ Arg Min(u,v)∈S×S Tuv . Query the advice of experts i and j and update the corresponding quantities. For all u, v: If ∆′uv > 0: S ← S \ {v}.
end for On interrupt: Let k̂ ∈ S and let l̂← argmax
j∈S d̂k̂j .
Let q̂ denote the empirical risk minimizer on S. if Tk̂l̂ > √ log(KTδ−1)Tq̂ then
Return 12 ( Fk̂ + Fl̂ ) .
else Return Fq̂ . end if
Our first result in this setting is an empirical bound. At any interruption time, it gives a bound on the excess risk, only depending on quantities available to the user, using the number of queries resulting from the querying strategy in Algorithm 2. We then use a worst-case bound on these quantities to develop an instance independent bound in Corollary 5.2. Theorem 5.1. (Empirical bound) Suppose Assumption 1 holds. Let T ≥ 2K2, and denote ĝ the output of Algorithm 2 with inputs (δ, L, ρ) in round T . Then with probability at least 1− 3δ:
R(ĝ) ≤ R∗ + c Bmin
{ log ( TKδ−1 ) Tk̂l̂(T ) , √ log(TKδ−1) Tq̂(T ) } , (6)
where k̂, l̂ and q̂ are the experts in Algorithm 2 and c is an absolute constant.
Proof Sketch of Theorem 5.1 We start by noting that when running Algorithm 2, the optimal experts S∗ = Arg Mini∈JKKR(Fi) are never eliminated with high probability (Lemma S-5). This shows in particular, that when the procedure is terminated, we have S∗ ⊆ ST , where ST is the set of non-eliminated experts at round T .
Then we show the following key result: in each round t ≤ T , for any expert i ∈ St, let j ∈ Arg Maxl∈St d̂il(t), we have with probability at least 1− δ:
R
( Fi + Fj
2
) ≤ R∗ + cB log(Kδ −1 t )
Tij(t) .
For the second bound, recall that i∗ belongs to ST with high probability. Therefore, performing an empirical risk minimization over the set of non-eliminated experts leads to the bound √
log(KTδ−1) Tq(T )
, through a simple concentration argument using Hoeffding’s inequality. Corollary 5.2. (Instance independent bound) Suppose assumption 1 holds. Let T ≥ 2K2, and denote ĝ the output of Algorithm 2 with inputs (δ, L, ρ) in round T . Then with probability at least 1− 3δ:
R(ĝ) ≤ R∗ + c Bmin
{ K2 log ( TKδ−1 ) T , √ K log(TKδ−1) T } ,
where c is an absolute constant.
Proof. We develop an elementary bound on Tk̂l̂ and Tq̂, then we inject these bounds into inequality (6).
Note that: q̂, i∗ ∈ ST , hence Tq̂(T ), Ti∗(T ) ≥ T2K . Moreover, we have:
Tk̂l̂(T ) ≥ T
K2 .
Using inequality (6), we obtain the result.
Remarks. Observe that in all the considered settings (full information, budgeted and limited advice), the number of jointly sampled pairs (Fi, Fj) to attain an excess risk of O( ) is of the order of O(K2/ ). Being able to ask a set of m experts simultaneously in a training round allows to sample m(m− 1)/2 pairs for a query cost of m: this is the advantage of the budgeted setting, while we have to query each pair in succession under the strict m = 2 constraint, resulting in a higher cost overall. Theorem 5.3. (Instance dependent bound) Suppose Assumption 1 holds. Let ĝ denote the output of Algorithm 2 with input (δ, L, ρ) and T denote the total number of rounds. Let > 0, if :
T ≥ 578 C log ( δ−1C ) ,
where
C := K ∑ i∈Sc Λi + 2|S |2 min { 1 ,Λ∗ } ,
where Λ∗ := maxi:Λi<+∞ Λi, then, with probability at least 1− δ: R(ĝ) ≤ R∗ + cB ,
where c is an absolute constant.
Remarks. If the algorithm is allowed to query m > 2 expert advices per round, then it can be modified to attain an improved excess risk. We present this extension in Section S-8 in the supplemental, and prove that it leads to a rate of O ( (K/m)2 T log(KT/δ) )
, which interpolates for intermediate values of m.
Proof Sketch of Theorem 5.3 First, we develop instance-dependent upper and lower bound for Tij(t), for any i, j ∈ JKK such that: R(Fi) 6= R(Fj). To do this we introduce the following lemma (see Lemma S-7 in the supplemental):
Lemma 5.4. Let i, j ∈ JKK such that R(Fi) 6= R(Fj). With probability at least 1− 4δ, for all t ≥ 1, if
Tij(t) ≥ 289 log ( Kδ−1t ) max
{ L2d2ij
|R(Fi)−R(Fj)|2 ;
B
|R(Fi)−R(Fj)|
} ,
then we have either ∆′ij > 0 or ∆ ′ ji > 0; furthermore, if
Tij(t) ≤ 3 log ( Kδ−1t ) max
{ L2d2ij
|R(Fi)−R(Fj)|2 ;
B
|R(Fi)−R(Fj)|
} ,
then we have: ∆′ij ≤ 0 and ∆′ji ≤ 0.
This lemma gives in particular an upper bound on the number of allocations needed for an expert i to be eliminated by an optimal expert i∗ (i.e. to fail the test ∆ii∗ ≤ 0). Then, we derive a bound on the number of rounds T required to eliminate all the experts in Sc and we conclude by showing that T − T is large enough to ensure that the experts k̂ and l̂ in algorithm 2 satisfy Tk̂l̂ > 1/ with high probability.

heading: 6 Lower Bounds for m = 1 or p = 1
text: This section considers the case where the agent is restricted to selecting one expert at the end of the procedure (p = 1), and the case where the learner is restricted to see only one feedback per round (m = 1). We show that in either case it is impossible to do better than an excess risk O ( 1/ √ T )
in deviation.
Lemma 6.1 is a direct consequence of a more general lower bound in [18], which proved that if the closure of the experts class is non-convex, and a single expert must be picked at the end (“proper” learning rule), then even under full information access during training the best achievable rate with high probability is O ( 1/ √ T ) .
Lemma 6.1. (p = 1) Consider the squared loss function. For K = m = 2 and p = 1, for any T > 0, and for any convex combination of the experts ĝ output after T training rounds, there exists a probability distribution for experts {F1, F2} and target variable Y (all bounded by 1) such that, with probability at least 0.1,
R̂T (ĝ)−R∗ ≥ c1√ T ,
where c1 > 0 is an absolute constant.
The second result shows that the same lower bound holds for the bandit feedback (m = 1) setting, even if the learner is allowed to predict using a convex combination of all the experts at the end. To the best of our knowledge, this is the first lower bound for deviations in this setting.
Lemma 6.2. (m = 1) Consider the squared loss function. For K = p = 2, and m = 1, for any T > 0, for any convex combination of the experts ĝ output after T training rounds, there exists a probability distribution for experts {F1, F2} and target variable Y (all bounded by 1) such that with probability at least 0.1,
R̂T (ĝ)−R∗ ≥ 1
2 √ T .

heading: 7 Conclusion
text: We discussed the impact of restricted access to information in generalization error minimization with respect to the best expert. As many classical methods, such as progressive mixture rules (and randomized versions thereof) are deviation suboptimal, we proposed a new procedure achieving fast rates with high probability. We focused on the global budget setting, where a constraint on the total number of expert queries is made, and the local budget, where a limited number of expert advices are shown per round. Moreover, we proved fast rates are impossible to achieve if the agent is allowed to see just one expert advice per round or choose just one expert for prediction.
An interesting future direction is allowing experts to learn from data during the process. In this case, the i.i.d. assumption on the loss sequence is dropped, which necessitates deriving a new concentration for the key quantities.

heading: Acknowledgements
text: We acknowledge support from the Agence Nationale de la Recherche (ANR), ANR-19-CHIA-002101 “BiSCottE”; and the Franco-German University (UFA) through the binational Doktorandenkolleg CDFA 01-18.

Review summaries:
UPDATE: The authors have addressed my questions in their response, and confirmed my initial positive view of the paper. Their plan for improving the presentation of the introduction seems satisfactory.  ---  The paper considers aggregation of a finite set of K predictors (experts) in the (batch) statistical learning setting, when the loss is Lipschitz and strongly convex. It presents learning algorithms that perform one sequential pass through the training data, and satisfy one of the following constraints: * no constraint: full information * budget constraint: algorithms can query at most C experts in total   during their run * query and output constraint: algorithms can query at most m experts   per round, and output a convex combination of at most p experts. The   following specific cases are considered:   - m=p=2 (and extension m>2,p=2)   - m=1 and p=2   - m=2 and p=1.  In all cases (near-)optimal bounds are obtained in probability. 

In this paper, the authors consider the problem of prediction with limited expert advice, with the goal of minimizing the excess generalization error, in the stochastic regime. They study a setting where they assume that the loss function is L-Lipschitz and \rho strongly convex.   They show that if the learner is only allowed to either make one observation per round in the prediction phase or query the advice of only one expert in the test phase, then there is a probability bounded by a constant that the worst case excess risk has a slow convergence.  To circumvent this issue, they study the impact of changing the number of observations and the number of expert queries, showing that in particular using at least two observations and two expert queries instead of one is sufficient to achieve a fast rate convergence of the excess generalization error. They consider a budgeted setting, where the learner has global budget constraint, and a more classic limited expert's predictions setting, which fixes the number of observed expert advices at each round.   

The paper proposes a novel learning framework, which seems to me to be a cross between prediction with expert advice and bandit framework ported to stochastic off-line settings.  The key features are:  1. On every round, the learner chooses a limited number of experts to observe. 2. After T rounds, the learner outputs a function on experts' predictions that to be used on the next round. 3. The experts and the outcome are stochastic.   The framework seems to naturally fit a scenario where obtaining an expert prediction (e.g., by running a computationally expensive program) is costly.  The upper and lower bounds on the expectation of the learner's loss on the (T+1)th round are provided (lower bounds without proofs). The cases where m, the number of experts we are allowed to observe, is equal to the total and less than the total are treated separately.

The setting in the paper is a prediction with expert advice in the stochastic setting, while the learner observes a limited number of experts each round (denoted by m), and is limited on how many experts to choose in prediction (denoted by p). The main result is providing an algorithm with fast rates convergence if 1/T, as long as the learner is allowed to see two experts per round and to use two experts for prediction. Moreover, for m=p=1 the authors provide a lower bound of 1/sqrt{T}.