Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.

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.
main_review: I think this is an interesting learning paradigm and the paper provides a thorough investigation.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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).
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}.

main_review: Significance: The setting of expert advice is classic and important. 
Extending it with limited access seems also interesting and natural.
The results show a separation -- what is the amount of access necessary for the learner in order to achieve fast generalization rates.
 
Originality/novelty: 
The main algorithm/technique seems novel to me.
However, I'm not familiar with results on other related models with limited feedback. 

Clarity and relation to prior work: 
The literature review is thorough.
Altogether, the overall method is presented clearly.
limitations_and_societal_impact: -
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 

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.



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. 
Furthermore, both problem dependent and problem independent bounds are provided.
A 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.

Overall, 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.

==== After Rebuttal changes
After reading the rebuttal, I rose the rating to a 7. 
limitations_and_societal_impact: Concerning the limitations, I could not find a proper discussion on whether Assumption 1 is reasonable in practice.
The interest of using limited advice was properly discussed, and efficient ressource management can be seen as a positive social impact.

Besides that, the societal impact was not really discussed, but it does not necessartily make sense for such a theoretical problem.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.

---

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.

main_review: Strengths:

The result for the full information case alone justifies acceptance. This
setting is really of fundamental importance, because of its application
to model selection (see [3] and [17]) and because it is known that
neither ERM over the predictors nor ERM over the convex hull of the
predictors achieves the optimal rate (see [17]). Thm 1 in the paper does
achieve the optimal rate previously obtained by [3] and [17], but with a
much simpler and easier to understand analysis. At first sight, this
does appear to come at the cost of the assumption that the loss is
strongly convex, which is much stronger than the assumptions in [3] and
does not cover many cases of practical interest, but inspection of the
proof appears to show that this assumption can be relaxed to assuming
only strong convexity of the risk, which is a much more liberal
assumption. -- Can the authors comment on whether this is correct?

The other types of constraints considered in the paper are all
variations on the approach for the full information case, but each of
them requires an additional new idea and corresponding non-trivial
choice of algorithm.

All in all, there are multiple new ideas in this paper that will be of
interest to the learning community.

Weaknesses:

Unfortunately, the presentation of Sections 1 and 2 could be improved:

Most notably, I found section 1 to be very vague, both with respect to
motivation and related work (note that it contains no references at
all!) and in the sense that it did not contain sufficient technical
details of the setting, which is not quite standard. I therefore could
not understand the discussion of related work in section 2 before
reading the formal definition of the setting in section 3.

The reference to 'expert advice' in the terminology, while defensible,
is perhaps not ideal, since this is not the standard prediction with
experts setting. Terminology and motivation in [3] and [17] seem much
clearer to me. I also get the impression that you are secretly thinking
of experts as having chosen a function f_i from some function class and
making predictions by F_{i,t} = f_i(X_t) based on some underlying
feature vector X_t. This is the only way I can link the discussion in
Section 7 to [18] and make sense of the statement that the "closure of
the experts class is non-convex".

Minor comments:

There 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.

In (2): supremum should be w.r.t. i instead of j.

Proof of Thm 1, second displayed equation: why is there a division by 8
in the first inequality? I would expect a division by 2 based on strong
convexity. It would also be convenient to define strong convexity via
the inequality that you actually use here.

Proof of Thm 1: please spell out the last step of maximizing over
d_{\bar k, \bar j} in sufficient detail that the reader can verify the
result without redoing the calculations themselves. 

End of Section 5, remarks: this discussion is incorrect, because for
epsilon=0 the set S_epsilon^c does contain i such that Lambda_i =
infinite. (I suspect that this will be fixable.)

Section 6: it shouldn't be necessary for the notation \hat{R}_{ij}(j,t)
to refer to 'j' twice.

Algorithm 3: based on the discussion, I would expect the argmin in the
selection of j to be restricted to the set S. (Note that the same argmin
also appears in the discussion below Algorithm 3.)

Corollary 4: Please mention/discuss worse dependence on K compared to
Theorem 1.

Theorem 5: Please state explicitly that the result holds for any fixed
epsilon.

Section 7: when citing [18], it is recommended to also cite the
correction in W. S. Lee, P. L. Bartlett and R. C. Williamson,
"Correction to “The importance of convexity in learning with squared
loss”", 2008. And possibly also S. Mendelson, "Lower bounds for the
empirical minimization algorithm", IEEE Transactions on Information
Theory, 2008.

limitations_and_societal_impact: Yes. This is a theoretical paper, for which limitations have been adequately discussed.
Societal impact is too indirect to discuss.
review_title: null

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