Fast rates for prediction with limited expert advice
Authors: El Mehdi Saad
Gilles Blanchard
Venue: NeurIPS 2021 Poster (2021)
Keywords: Online Learning
prediction with expert advice
high probability bounds
budgeted learning

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 consider that the learner has only 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 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 ${\Omega}(1/\sqrt{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 $\mathcal{O}(1/T)$ can be achieved. We design novel algorithms achieving this rate in this setting, and in the setting where the learner have a budget constraint on the total number of observed experts advices,  and give precise instance-dependent bounds on the number of training rounds needed to achieve a given generalization error precision.

Fast rates for prediction with limited expert advice
EI Mehdi Saad', Gilles Blanchard 1:2
"Laboratoire de Mathématiques O'Orsay, CNRS, Université Saclay; ?Inria
Abstract
We investigate the problem of minimizing the excess generalization error with respect to the best expert prediction in 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 the test phase, the worst-case excess risk 2211////// 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 O1/TT) can be achieved. We design novel algorithms achieving this rate in this setting, and the setting where the learner has budget constraint on the total number of observed expert advices, and give precise instance-depender bounds on the number training rounds and queries needed to achieve a given generalization error precision.
with probability lower bounded by
Keywords: Online Learning, Budgeted Learning, Prediction with expert advice.
1 Introduction and setting
We consider a generic prediction problem in a stochastic setting: 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 closed convex subset X' of IR... The mismatch between the two is measured via loss function I(F,Y, Y). The quality of the agent's 's output is measured by its generalization risk
R(F) = [()
To assist in this task, the forecast "advice" of number of "experts" (Fi...., Fx) (also modeled as random variables) can be requested. The agent's objective to achieve a risk as close as possible to the risk of the best expert R' = mi] R(P:) (for nonnegative integer n, denote [n] {I..... 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 sequence of forecasts F, followed by observation of the target variable Y, and incurring the loss 1(F,, Y,), t 1...., .. In the present work we will separate observation (or training) phase and forecast phase: the user allowed to observe (some of) the expert's predictions and the target variable for number of independent, identically distributed rounds (Y,, Fi,t..... FKAIISIST following certain rules to be specified. After the observation phase, the user must decide of prediction strategy, namely convex combination of the experts f Σ F.FF, where the weights W; be chosen based on the information gathered in the training phase. The risk of this strategy is R(F), where the risk is evaluated 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 1)th, independent, round.
35th Conference on Neural Information Processing Systems (NcurIPS 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 total limit on how much we can spend. In a different context, is unrealistic to ask for the advice of all available doctors or to run 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 fixed prediction method F; = fi(X) (using the information a covariate X), where the predictor functions fi have been already trained in advance, albeit based on different sets of parameters 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 's goal is to achieve 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(L/C), where C' is the total query budget). These are possible under 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 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 F 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-independer (agnostic) and instance- dependent (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. Vy E V:: x E X' C Rdd + 1(x, y) is L-Lipschitz and p-strongly convex.
Recall that function f X' + is L- L-Lipschitz if Vr,y E xx1f(()) - f(y)) s L||= yll. and p-strongly convex if the function: + fxx o ||0|| is convex.
Remarks. Assumption implies that the diameter of X' is bounded by 8L/p² and the quantity supz.z'ex.ye (zz y) -Tax', [[))))] is bounded by B == SL2 /p² (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 Lemme[]ss[ and subsequent discussion for details). It satisfied, for example, in the following setting: least square loss I(x, y) (y )²² where x E X' and y E y with A' and ) are bounded subsets of IRd, Prior knowledge on p is not necessary if L and an upper bound on the the 1x norm of the target variable Y and the experts are known.
2 Discussion of related Work
Games with limited feedback (slow rates): Our work investigates what happens between the full information and single-poin feedback games. Learning with a restricted access to information was considered under various settings in (6). 19. [2). 20 [5]. A setting close to ours considered in [II] 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 O(V1/T) in the limited feedback setting and O (T)((C)/C) in the budgeted case with budget C.
Refeernnces starting with pretix 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 a-priori defined budget C. In the stochastic setting, UCB UCB-type procedure gives bound for the cumulative regret of O -1
min log(C)/CC /C) that holds only in expectation, where A min denotes the gap between the best choice of arms and the second best choice. This bound leads to an instance dependent bound of O D(ylog(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 cumulattve 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 regret dependence on T better than the rate of (1/VTT).
Fast rates 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 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" " (logg(K) (K) )/T) [13] 9 4), which, combined with the online-to-biie 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 22, that is, their excess risk takes 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 improper learning rule. Thus negative and positive "large" deviations can compensate each other so that the expectation small. The inefficiency of EWA in deviation is a significant drawback, and alternatives to the EWA progressive mixture rule that achieve ([log(K) /T")) excess prediction risk with high probability were proposed by (17 and 3. In 117. 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 33, 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.
conversion principle 88 4 (also known as progressive
Linear regression with partially observed attributes: Other related work is that of 100 and 14 on learning linear regression models with partially observed attributes. The most related setting to ours the local budget setting, where the learner allowed 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 (6)). Moreover, while we want to predict as well as the best expert, in [00] the objective is to be as good as the best linear combination of features with small additive term (the optimal rate, in this case, is (11 (/TT)). 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 []]. and (22).. It was shown that in the setting where the adversary chooses a loss function in each round if the player is allowed query this function in two points, it is possible achieve minimax rates that are close to those achievable in the full information setting. The key idea is to build 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.
3

---

3 The full information case
In this section, revisit the "classical" where there is constraint the number of expert queries per observation round; assume the output of all experts are observed for I' rounds (in other words, I' i.idd training examples), which is the full information or "batch" setting. We want output a final prediction rule with prediction risk controlled with high probability over the training phase.
We start with putting forward 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 union of segments. The underlying principle will guide us to construct budget efficient expert selection rule in the sequel.
Define R(FF)) := T El= (FFi,, Yt) the empirical loss of expert i, and d.j := (T- " (Fs, F)a) the empirical T2 distance between experts i and j over 7 rounds. Finally let = a(o) (log(4K6-1)/TT) where å (0,1) fixed confidence parameter. Define
Au = R(F,) R(F)) 6a max (Ldig, Ba].
(1)
The quantity Aiy be interpreted test statistic: if Aij > O, then have guarantee that R(F,) > ((F.), 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
S { E [K]
sup Au =0}
(2)
jE[K]
Our new full information setting rule is the following:
1 choose i S arbitrarily: pick Arg Maxdij predict F == 2 g + Fy). jES
(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 possible (in terms of empirical L 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 Asssumption 7 holds and ā E (0, 1) is fixed, then for the prediction rule F defined by 3 it holds with probability - 35 over the training phase (c is an absolute constant):
log log(4K8-1)
R(F) S R² cB
Proof. Let di = R[F; F2)21. The result hinges on the following high confidence control of risk differences, established in Corollary S as direct consequence of the empirical Bernstein's s inequality: with probability at least - 36, it holds:
For all i,j E [K]
A, S (R₃ - R2) S Aij + 32a (Ldj.. Ba).
(4)
Let i" E Arg [K R2 be an optimal expert. Since RG, - RR S 0 for all j E [K]] it follows that holds, then i" E S, from the definition of S. So if (4) holds, we have
F +
Fj
p² di
R
Rg + R3)
2
8
p²
R² + (RRg Ri-) (Rz R.-))
8
p² d
< R²
A + Ajr)) 16a (max (Ldji. Ba) + max(Ldis Ba))
p² ed
$ Rd + 32Ba + 48Lodgj
where we have used strong convexity of the loss (and therefore of R(-) with respect the L 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 dz.- S dzk + dg.- S 2dzz by construction of j. Finally upper bounding the value of the last bound by its maximum possible value as a function of dgz and recalling = ST.2 / we obtain the statement.
O

---

Budgeted Setting
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 the agent. The player then pays a unit for each observed expert's '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 Aji for each pair (i,j) j) after each allocation. If any round an expert [K] fails any of these tests (i.e Aj- Aji > 0), 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 A.j > are performed after each allocation, we introduce the following modification on the definition of A.j. for concentration inequalities to hold uniformly over the runtime of the procedure. We define Aig (t, 6) as follows:
(ty = R(j. t) R(i, - ( 1)) max (t), Balt, 6/(t(t + 1))}
Algorithm 1 Budgeted aggregation
Input 8, and p.
Initialization: S [K]. for T= 1,2.... do
Jointly query all the experts in S and update Aij > 0 for all é.j. For all i,j E [K]. Aij > O, eliminate j: S S (i).
if the budget is consumed then
let k E S, and argmax dey. jES
Return [(F + Fi). end if end for
Let S* Arg [ R(F,) denote the set of optimal experts. For i, E [[], denote by dy = (F "1)
1/2
the L2 distance between the experts F; and Fj. For i E [K], we introduce
the following quantity:
L2d [R(F)) - R(FF-)) R(F:) R(F,-)
B
A min max
Define the following set of experts:
A₂ > S. = [E
1 e
and let S. be its complementary.
Theorem 4.1. (Instance dependent bound) Suppose Assumption 7 holds. Let C 2 K denote the global budget on queries and denote 9 the output of Algorithm with imputs (6, L. p) when the budget C' runs out. For any 2 0, if:
C> 578C, log (ogg(K88 (K).
where
C. = Σ A4+ min =;A-
1ESE
where A m8x As. then, with probability at least 1 8:
R(ğ)= < R + cBe,
where is absolute constant.
5

---

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 < O. in which case the required expert query budget is of order Lisd,+t A; up 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 is of order EEAAe+ As (15), where
A, (R(())) R(F Since the diameter of X bounded by B/L L (see Lemma S S... it holds Ar S A, H best expert identification, the bound of Theorem 4. improves upon the best arm identification bound, potentially by significant margin (in particular concerning the contribution of suboptimal but close to optimal experts for which dii- < BB and R₂ R&- < B). Again, the improvement is due to the Assumption on the loss and the possibility query several experts per round, which are not used when casting the problem as a classical bandit setting.
5 Two queries per round (m= = p 2)
In this section, we suppose that the decision-maken is constrained to see only two experts' advice per round (m 2). We suppose that the horizon unknown; when the game 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 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 uniform way, where S is the of non-eliminated experts. Then the tests D'; S 0 and D I 0 are performed, where A' is defined by (5). If i or fail the test, which means that 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-climinated experts the mean of two experts from S that are distant enough. This rule allows our algorithm's 's output to enjoy the best of converge rates of the two methods.
We introduce the following notations: round f, denote (t) the number of samples where predictions of experts and j were jointly queried and (t( the number of rounds where the prediction of expert i queried. Denote R.y (j.t) the empirical loss of expert i calculated using
only the T.y (t) samples queried for (i,j) jointly. We define aty(t, 6) [og(4R8-1) if (.)
T.y())
and (t) = oo otherwise. Let di (t) be the empirical L2 distance between experts and based on the Tij (f) queried samples. Denote 6, 5/(t(t 1)). For i j [K] we define:
(,,(t,))= = Riy(i,t) Riy(i, t) - 6 max Lai (t. (t), (t, (t)
(5)
Algorithm Two-point feedback
Input 8, L and Initialization; S - [K]. for T T= 1,,2... do
Let (i.j) Arg Min Tuv-
Query the advice of experts and j and update the corresponding quantities.
For all e: If A.. > 0: S + S (w).
end for
On interrupt: Let e S and let + argmax dzz
JES
Let denote the empirical risk minimizer on S. if Ti > Moog(TT--YDD then Return (F F:).
else
Return Eg.
end

---

Our first result in this setting is an empirical bound. At any interruption time, it gives 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 worst-case bound on these quantities to develop an instance independent bound in Corollary 5.2
Theorem 5.1. (Empirical bound) Suppose Assumption 7 holds. Let T 2 2K2, and denote the oulput of Algorithm with inputs (6, L, P) in round Then with probability at least 36:
log (TK8-))
log(TKō- (T(
R()) S R + B min
(Ti(T)
where k, and are the experts in Algorithm 2 and is an absolute constant.
Proof Sketch of Theorem 5.1 We start by noting that when running Algorithm 2 the optimal experts S Arg Min R.) are never eliminated with high probability (Lemmaa S-5). This shows in particular, that when the procedure is terminated, we have S C ST, where Sy is the set of non-eliminated experts at round T'.
Then we show the following key result: in each round S T, for any expert E Sr, let j E Arg Maxies, (t), we have with probability at least 8:
F
P3 2
log (og(Ko,))
R
S R + cB
(t,
For the second bound, recall that i belongs ST with high probability. Therefore, performing empirical risk minimization over the set of non-climinated experts leads to the bound / /log(KTT-1 through a simple concentration argument using Hoeffding's 's inequality.
T.(7)
Corollary 5.2. (Instance independent bound) Suppose assumption 1 holds. Let T 2 2K2 and denote 9 the output of Algorithm 2 with inputs (ō, L. p) in round T. Then with probability at least 1- 1-36:
K2 Kelog(TKe (TK())
K Mog(TKö-
R(O) S R + min
T
where e is an absolute constant.
Proof. We develop elementary bound Ti. and T3. then we inject these bounds into inequality
(
Note that: q, 1" Sr, hence T,. (T)
T 2K
Moreover, have:
T
(T)(T) 2
K
Using inequality (6). we obtain the result.
Remarks. Observe that all the considered settings (full information, budgeted and limited advice), the number of jointly sampled pairs (F; F2) to attain excess risk of O(e) is of the order of O(K²/c) /c). Being able to ask set of m experts simultaneously in training round allows to sample m(m 1)/2 pairs for 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 higher cost overall.
Theorem 5.3. (Instance dependent bound) Suppose Assumption holds. Let 9 denote the output of Algorithm 2 with input (6, L, p) and T denote the total number of rounds. Let e > 0, if:
T T2 578 C. log(o CC))
where
C
K K
A. + 2
min -,A"
RES:
where A == maxxA Ao then, with probability at least 1 - 8:
R(g) S R + cB e,
where is 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 i the supplemental. and prove that it leads rate of O (K/m)² log (KKK///6)))))) which interpolates for intermediate values of m.
First, we develop instance-dependen upper and lower bound for (t,(), for any i.j E [K] such that: R(F;) + R(F)). To do this we introduce the following lemma
Proof Sketch of Theorem 5.3
(see Lemma S in the supplemental):
Lemma 5.4. Let i.j J [K] such that R(F)) + R(F3), With probability at least - for all 1 2 1.
if
L2d.,
B
(t,(t) 2 289 log (og( max
(R(F)) - R(FF)) R(F:) R(F,)
then have either 1/3 0 S
O: furthermore,
d2 [R(F.) R(F)))? [R(F.) - R(F))
B
3lo0))3 max
then we have: 4 < 0 and f S 0.
This lemma gives in particular an upper bound on the number of allocations needed for an expert to be eliminated by an optimal expert 1" (i.e. fail the A < 0). Then, we derive a bound on the number of rounds T, required to eliminate all the experts in Se and we conclude by showing that
T - T. is large enough ensure that the experts i and in algorithm 2 satisfy Tūi 1/c with high probability.
Lower Bounds for m or p
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 excess risk (1/vTT) in deviation.
Lemma 6. is a direct consequence of a more general lower bound [88] which proved that if the closure of the experts class 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 (1/vT)..
Lemma 6.1. (p- 1) Consider the squared loss function. For K = m 2 and = for any T O, and for any convex combination of the experts ğ output after training rounds, there exists probability distribution for experts {F1, F2) and target variable Y (all bounded by 1) such that, with probability at least 0.1,
Rr(9) R²
VT
where e > 0 is an absolute constant.
The second result shows that the same lower bound holds for the bandit feedback (m = 1) setting, if the learner is allowed predict using 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 = 2, and m = 1, for any T > for any convex combination of the experts 9 output after T training rounds, there exists probability distribution for experts { F1, F2} and target variable Y (all bounded by 1) such that with probability least 0.1,
R (g) R" N 2VT
8

---

7 Conclusion
We discussed the impact of restricted access information in generalization 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 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 limited number of expert advices 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 the loss sequence is dropped, which necessitates deriving new concentration for the key quantities.
Acknowledgements
We acknowledge support from the Agence Nationale de la Recherche (ANR), ANR-I9-CHIA--002-- 01 "BiSCottE"; and the Franco-German University (UFA) through the binational Doktorandenkolleg CDFA 01-18.
References
[1] A. Agarwal, O. Dekel, and L. Xiao. Optimal algorithms for online convex optimization with multi-point bandit feedback. COLT, pages 28-40, 2010.
[2] J.-Y. Audibert. Progressive mixture rules are deviation suboptimal. In J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems, vol- ume 20, 2008.
[3] J.-Y. Audibert. Progressive mixture rules deviation suboptimal / Supplemental "Proof of the optimality of the empirical star algorithm". In J. Platt, D. Koller, Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems, volume 20, 2008
[4] J.-Y. Audibert. Fast learning rates in statistical inference through aggregation. The Annals of Statistics, 3794):19 2009.
[5] J.-Y. Audibert and S. Bubeck. Regret bounds and minimax policies under partial monitoring. The Journal of Machine Learning Research, 11:2785-2838 2010.
[6] S. Ben- Sen-David and E. Dichterman. Learning with restricted focus of attention. Journal of Computer and System Sciences, 56(3):277-298, 1998.
[7] O. Catoni. A mixture approach to universal model selection. Technical Report LMENS-97-300 Ecole Normale Supérieure, 1997.
[8] N. Cesa-Bianchi, A. Conconi, and C. Gentile. On the generalization ability of on-line learning algorithms. IEEE Transactions on Information Theory, 50(9): -057, 2004.
[9] N. Cesa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[10] N. Cesa-Bianchi, S. Shalev-Shwartz, and O. Shamir. Efficient learning with partially observed attributes. Journal of Machine Learning Research, 12(10), 2011.
[11] S. Gerchinovitz and T. Lattimore. Refined lower bounds for adversarial bandits. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 1198- 1206, 2016.
[12] S. Guha and K. Munagala. Approximation algorithms for budgeted learning problems. In Proceedings the the thirty-ninth annual ACM symposium on Theory of computing, pages 104-113, 2007.
[13] D. Haussler, J. Kivinen, and M. K. Warmuth. Sequential prediction of individual sequences under general loss functions. IEFE Transactions on Information Theory, 44(5):1906-1925, 1998.

---

[14] E. Hazan and T. Koren. Optimal algorithms for ridge and lasso regression with partially observed attributes. arXiv preprint arXiv: 1eXiv:1108.430 4559, 2011.
[15] E. Kaufmann, O. Cappé, and A. Garivier. On the complexity best-arm identification in
multi-armed bandit models. The Journal of Machine Learning Research, 17(1):1-42 2016.
[16] G. Lecué. Suboptimality of penalized empirical risk minimization in classification. In Interna- tional Conference on Computational Learning Theory, pages 142-156. Springer, 2007.
[17] G. I Lecué and S. Mendelson. Aggregation via empirical risk minimization. Probability theory and related fields, 145(3-4):591-613, 2009.
[18] W. S. Lee, Bartlett, and R. Williamson. The importance of convexity in learning with squared loss. IEEE Transactions on Information Theory, 4455)1974-1188 1998.
[19] O. Madani, D. J. Lizotte, and R. Greiner. Active model selection. In Proceedings of the 20th conference on Uncertainty artificial intelligence, pages 357-365, 2004.
[20] S. Mannor and O. Shamir. From bandits to experts: on the value of side-observations. In Proceedings of the 24th International Conference on Neural Information Processing Systems, pages
2011.
[21] Y. Seldin, P. Bartlett, K. Crammer, and Y. Abbasi- Yadkori. Prediction with limited advice and multiarmed bandits with paid observations. In International Conference on Machine Learning. pages 280-287. PMLR, 2014.
[22] O. Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. The Journal of Machine Learning Research, 18(1):10331713, 2017.
[23] T. Thune and Y. Seldin. Adaptation to easy data in prediction with limited advice. In Proceedings the 32nd International Conference Neural Information Processing Systems, pages 2914-2923, 2018.
[24] Y. Xia, T. Qin, W. Ma, N. Yu, and T.-Y. Liu. Budgeted multi-armed bandits with multiple plays. In IJCAI, pages 2210-2216, 2016.
[25] Y. Yang and A. Barron. Information-theorete determination of minimax rates ofconvergence. The Annals of Statistics, 27(5):1564 - 1599, 1999.
[26] D. Zhou and C. Tomlin. Budget-constrained multi-armed bandits with multiple plays. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
10


Reviews:
[{"review_id": "zTgzfSWk2qR", "reviewer": "Reviewer_4EKs", "summary": "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.\n\n---\n\nThe paper considers aggregation of a finite set of K predictors\n(experts) in the (batch) statistical learning setting, when the loss is\nLipschitz and strongly convex. It presents learning algorithms that\nperform one sequential pass through the training data, and satisfy one\nof the following constraints:\n* no constraint: full information\n* budget constraint: algorithms can query at most C experts in total\n  during their run\n* query and output constraint: algorithms can query at most m experts\n  per round, and output a convex combination of at most p experts. The\n  following specific cases are considered:\n  - m=p=2 (and extension m>2,p=2)\n  - m=1 and p=2\n  - m=2 and p=1. \nIn all cases (near-)optimal bounds are obtained in probability.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\nThe result for the full information case alone justifies acceptance. This\nsetting is really of fundamental importance, because of its application\nto model selection (see [3] and [17]) and because it is known that\nneither ERM over the predictors nor ERM over the convex hull of the\npredictors achieves the optimal rate (see [17]). Thm 1 in the paper does\nachieve the optimal rate previously obtained by [3] and [17], but with a\nmuch simpler and easier to understand analysis. At first sight, this\ndoes appear to come at the cost of the assumption that the loss is\nstrongly convex, which is much stronger than the assumptions in [3] and\ndoes not cover many cases of practical interest, but inspection of the\nproof appears to show that this assumption can be relaxed to assuming\nonly strong convexity of the risk, which is a much more liberal\nassumption. -- Can the authors comment on whether this is correct?\n\nThe other types of constraints considered in the paper are all\nvariations on the approach for the full information case, but each of\nthem requires an additional new idea and corresponding non-trivial\nchoice of algorithm.\n\nAll in all, there are multiple new ideas in this paper that will be of\ninterest to the learning community.\n\nWeaknesses:\n\nUnfortunately, the presentation of Sections 1 and 2 could be improved:\n\nMost notably, I found section 1 to be very vague, both with respect to\nmotivation and related work (note that it contains no references at\nall!) and in the sense that it did not contain sufficient technical\ndetails of the setting, which is not quite standard. I therefore could\nnot understand the discussion of related work in section 2 before\nreading the formal definition of the setting in section 3.\n\nThe reference to 'expert advice' in the terminology, while defensible,\nis perhaps not ideal, since this is not the standard prediction with\nexperts setting. Terminology and motivation in [3] and [17] seem much\nclearer to me. I also get the impression that you are secretly thinking\nof experts as having chosen a function f_i from some function class and\nmaking predictions by F_{i,t} = f_i(X_t) based on some underlying\nfeature vector X_t. This is the only way I can link the discussion in\nSection 7 to [18] and make sense of the statement that the \"closure of\nthe experts class is non-convex\".\n\nMinor comments:\n\nThere are occasional grammatical mistakes. For instance, in the statement of Theorem 1. While the meaning is clear, it would be good to do another round of proofreading before the final version.\n\nIn (2): supremum should be w.r.t. i instead of j.\n\nProof of Thm 1, second displayed equation: why is there a division by 8\nin the first inequality? I would expect a division by 2 based on strong\nconvexity. It would also be convenient to define strong convexity via\nthe inequality that you actually use here.\n\nProof of Thm 1: please spell out the last step of maximizing over\nd_{\\bar k, \\bar j} in sufficient detail that the reader can verify the\nresult without redoing the calculations themselves. \n\nEnd of Section 5, remarks: this discussion is incorrect, because for\nepsilon=0 the set S_epsilon^c does contain i such that Lambda_i =\ninfinite. (I suspect that this will be fixable.)\n\nSection 6: it shouldn't be necessary for the notation \\hat{R}_{ij}(j,t)\nto refer to 'j' twice.\n\nAlgorithm 3: based on the discussion, I would expect the argmin in the\nselection of j to be restricted to the set S. (Note that the same argmin\nalso appears in the discussion below Algorithm 3.)\n\nCorollary 4: Please mention/discuss worse dependence on K compared to\nTheorem 1.\n\nTheorem 5: Please state explicitly that the result holds for any fixed\nepsilon.\n\nSection 7: when citing [18], it is recommended to also cite the\ncorrection in W. S. Lee, P. L. Bartlett and R. C. Williamson,\n\"Correction to “The importance of convexity in learning with squared\nloss”\", 2008. And possibly also S. Mendelson, \"Lower bounds for the\nempirical minimization algorithm\", IEEE Transactions on Information\nTheory, 2008.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. This is a theoretical paper, for which limitations have been adequately discussed.\nSocietal impact is too indirect to discuss.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical issues.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "qWmcIoiK2GN", "reviewer": "Reviewer_pnAv", "summary": "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. \n\nThey 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. \nTo 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.\nThey 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.\n\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is overall quite complete, as the authors study two versions of the prediction with limited expert advice problem, one with a global budget, and one with a per round fixed budget. They do also provide lower bounds which justify the interest of using two queries per round rather than 1. \nFurthermore, both problem dependent and problem independent bounds are provided.\nA special case of the budgeted setting also relates to the problem of best arm identification in multi-armed bandits, where the assumptions on the loss function and the capacity to query several arms at each round are used to achieve improvements compared to the standard Best arm identification results that are subjected to a stricter problem setting.\n\nOverall, the problem seeting seems novel and the contributions significant as they prove some fast rate convergences.  This being said, I don't know whether the assumption that the loss function is L-Lipschitz and \\rho strongly convex is realistic.\n\n==== After Rebuttal changes\nAfter reading the rebuttal, I rose the rating to a 7. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Concerning the limitations, I could not find a proper discussion on whether Assumption 1 is reasonable in practice.\nThe interest of using limited advice was properly discussed, and efficient ressource management can be seen as a positive social impact.\n\nBesides that, the societal impact was not really discussed, but it does not necessartily make sense for such a theoretical problem.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "pHY-y7_2fGQ", "reviewer": "Reviewer_bhrD", "summary": "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).\nThe 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.\nMoreover, for m=p=1 the authors provide a lower bound of 1/sqrt{T}.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Significance: The setting of expert advice is classic and important. \nExtending it with limited access seems also interesting and natural.\nThe results show a separation -- what is the amount of access necessary for the learner in order to achieve fast generalization rates.\n \nOriginality/novelty: \nThe main algorithm/technique seems novel to me.\nHowever, I'm not familiar with results on other related models with limited feedback. \n\nClarity and relation to prior work: \nThe literature review is thorough.\nAltogether, the overall method is presented clearly.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "VBIZM9-85W", "reviewer": "Reviewer_YBCx", "summary": "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.\n\nThe key features are:\n\n1. On every round, the learner chooses a limited number of experts to observe.\n2. After T rounds, the learner outputs a function on experts' predictions that to be used on the next round.\n3. The experts and the outcome are stochastic.\n\n\nThe framework seems to naturally fit a scenario where obtaining an expert prediction (e.g., by running a computationally expensive program) is costly.\n\nThe 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.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think this is an interesting learning paradigm and the paper provides a thorough investigation.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers are excited about the results of the paper and unanimously recommend acceptance.
Decision: Accept (Poster)