Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies the problem of risk monotonicity, that is, the property that the population loss decreases monotonically with increasing data points. The paper proposes an algorithm that converts any consistent base algorithm into a risk-monotonic algorithm while maintaining consistency under two assumptions: (1) an assumption on the generation of samples which is weaker than i.i.d. (2) an assumption on the base algorithm requiring its posterior to not have KL divergence to a fixed prior growing super-linearly in the sample size.

The approach presented in the paper is pretty straightforward: the base algorithm is run for $k=1, \ldots, n$ times and iteratively the current hypothesis is updated to be the base learner's output only if the risk reduces from the previous step, else it remains unchanged. Finally the hypothesis at step $n$ is returned. The main challenge here is to be able to confidently account for this change using the samples. For this, the authors derive a new concentration inequality for this using an online algorithm's guarantees.


main_review: Developing risk monotonic algorithms has gained interest in the last few years due to the 'double descent' phenomenon observed in deep learning making the topic of the paper is pretty relevant to the community. I think the paper takes a good step in this direction. There are some new ideas in the paper though the algorithm itself is pretty straightforward. My main concerns are the practicality of the algorithm and the validity of the assumptions in practice. The paper would greatly benefit from an experimental evaluation to support the approach on some real-world problems.

Comments/Questions/Typos:
1. Typos:
	Line 2: populating -> population
	Line 175: continues -> continuous
2. Definition 2, 'converges in probability' is not clear.
3. Why is $\rho$ needed for the theorem statements? Can you not replace it by a constant?
4. Assuming access to the distribution and being able to calculate the expectation for the algorithm $B$ efficiently requires further discussion. For a randomized algorithm B, you would not expect to have access to the distribution over hypothesis, so you'll have to estimate that and run B another $\log(n/\delta)$ times?
5. Since you use the FreeGrad guarantee on a scalar, are there more direct ways to prove the desired inequaity. It seems to resemble a self-normalizing Martingale bounds.
6. The proofs using the ESI notation require more description. It would be good to add what basic operations hold under this operator and further eleaborate on the proofs.
limitations_and_societal_impact: The authors should add more discussions about the practicality of the algorithm and its limitations in practice.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper provides a wrapper algorithm that, for bounded loss functions, operates on any base learning algorithm B and outputs a learning algorithm whose risk decreases monotonically with access to more samples (a very desirable property in practice). The wrapper function is based on a new concentration inequality for martingale difference sequences which is derived using the regret bounds for a particular parameter free online learning algorithm. 


main_review: I think the paper is fairly complete in terms of the results, and provides sufficient theoretical results and new proof ideas. I recommend it for acceptance.  I have a few questions: 

* Can you provide some examples where Assumption 1 holds but data is not i.i.d. ? Typically, we would like the behavior of the learning algorithm to be invariant to the order in which the samples are provided. Thus, we would like the property to hold independent of the order of samples. What kind of learning setting do you hope to use your monotonic algorithm where Assumption 1 holds for data is not i.i.d.?
 
* Can you provide some intuition on why we could not use empirical Bernstein inequalities for setting the value of \zeta_k ? Why is it natural to look at the problem of risk monotonicity in the PAC-Bayes setting ? 

*  The results provided in the paper hold for all N >= N_\Delta. Is it possible to show that for every N_\Delta, there exists some distribution for which learning monotonically is impossible when N < N_\Delta? 

* (Minor) In lines 128-129, the authors claim that the results of [49] could not be extended to hold in expectation. Can the authors discuss why ? 

The paper is well written otherwise. I skimmed through the proofs and they seem to be correct. 
The proof ideas in Appendix B are quite interesting! 

Minor comments: 
* References [22] and [23] are identical. 
* Lines 36-40 regarding discussion of connections to neural networks seem to be opposite to the empirical observations. 
limitations_and_societal_impact: No social negative impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Risk monotonicity has raised many research interest since the pioneer work of Belkin, Mikhail, et al., as this contradicts the classical understanding that the risk decreases as we see more samples. The non-monotonic behavior of the risk curve stress that we lack a clear understanding of generalization. As a result, this paper aims to addressing the problem of how to obtain an algorithm that returns an estimator with monotonic risk behavior. 

In addressing the above mentioned question, the authors make the following contributions:

The authors first derive a new concentration inequality for Martingale Difference Sequences. The bound drops the traditional assumption of i.i.d data and is time-uniform. In addition, the bound improves over the standard concentration inequalities by a factor of $\log n$.

On top of the concentration inequality bound, the authors also propose a "wrapper" algorithm which returns a consistent estimator that is proved to demonstrate monotonic risk curve. In addition, the algorithm does not hurt the excess risk convergence rate.
main_review: Clarity: The paper is clearly structured and well-written, though the authors are encouraged to carefully proof-read the manuscript to avoid some typos.

Quality \& Significance: I am not an expert on PAC-Bayesian analysis. However, as mentioned before, the non-monotonic risk behavior is a very important research question in the machine learning community and many papers have been published in understanding this phenomenon. Hence, this question that the authors study in this paper is of significant importance.

I do have some major concerns for the proposed algorithm. My first question is that, if I understand correctly, the proposed algorithm trades the monotonic risk curve with the computation time? If this is the case, then what exactly is the trade-off between the computation time and the monotonic risk behavior? 

My second question is that can the authors design some simple numerical experiments to explore the efficacy of the proposed algorithm. In particular, it would be more convincing to show experimentally that the algorithm indeed return an estimator with monotonic risk behavior.
limitations_and_societal_impact: Not Applicable
review_title: null

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: This work derives several novel concentration inequalities and uses them to derive the first risk monotonic algorithms for general statistical learning with bounded loss. 
main_review: General recommendation

This paper works on the important problem of risk-monotonic learning which has gotten much renewed interest since the discovery of the double descent phenenoma which is much more widely spread than previously throught. This paper, incredibly, manages to build a risk monotonic learning algorithm for the very general setting of bounded losses, for _any_ base learning algorithm. The algorithm is shown to be risk monotone in expectation and high probability, depending on the choice of the gaps. It remains very novel and surprising to me that it is at all possible to derive an algorithm which is risk monotonic in expectation for such a general setting. As such, I expect this to be a high impact paper on which future papers will build to further construct improved risk monotonic algorithms, which may open up a whole new field of study for machine learning algorithms and theory. 

Sadly I am not an well-versed enough in concentration inequalities so I could not check the proofs in the limited time I have for reviewing this paper, I hope another reviewer can step in for this. If the math checks out, I definitely vote to accept this paper.  I did find a few minor issues and possibly misstakes, but I'm sure these issues can be resolved through the review process. See below.   

Most important feedback

1) Assumption 2: can this assumption not be at odds with consistency? Or actually.... If we assume that the KL distance of an algorithm B is finite to the prior, can we not always adapt the algorithm B to satisfy this assumption? I mean, if the assumption is violated, we can just instead of using B's output, use the output of B in the previous round, until the condition is actually satisfied. So this seems to indicate that consistency will not be violated? I guess though that an essential condition is that the risk minimizer should be in an area of P_0 with > 0 probability? Maybe it would be good to clarify that explicitly.

2) Proposition 9: the point mass assumption seems incompatible to Assumption 2 to me, which is a condition of Theorem 8. So is there a misstake here?

3) Line 341: but for \beta = 0 (e.g. bounded losses), there is a cost to pay? Then I find in Line 173-174 the statement 'with essentially the same excess risk rate' slightly misleading. It only is shown that under the Bernstein condition beta > 0 the risk rate does not get worse significantly, right? Similairly for the statement in line 340 "risk monotonicity need not come at the price ....". 

4) It strikes me that we need to resort to a randomized algorithm that fullfills Assumption 2. Can you provide some intuition why this was necessary? Furthermore, I do appreciate that the current algorithm works with non-i.i.d. data, but is the complicated new concentration inequality necessary? Why can we not use good old existing results? E.g. is Theorem 6 really necessary, or can I also drop in another inequality here?  If so, which would I choose? What makes it essential that we need this one? Is it that for this specific one we can analyze the algorithm under the Bernstein condition, but could we also obtain risk monotone algorithms with a simpler technique and or inequality? If you can come to a simpler version of the algorithm, or provide a recipe to come to that, that would be much appreciated :). But of course, if this is unfeasible, I would really include some more arguments to justify the current approach. 

5) It is never reflected on what the intuition of \rho is. Do you have any idea what the consequence of this parameter is? How would you set it, or would you somehow tune it on the fly? I guess you may want to choose the largest or smallest value possible that still satisfies Assumption 2? Can you give some small explenation.

Small issues

6) Algorithm 1 is a bit misleading, since the sequence of gaps cannot be generated beforehand, as the gaps depend on the outputs of the base algorithm (e.g. on B(Z_{1:k}) and the P_k's). Would be good to squeeze it in between line 1 and 2: "compute \epsilon_k according to (eq. 9) for (\delta,n_\delta)-risk monotonicity, and to eq. X for risk-monotonicity for in expectation". Please also indicate the dependence of the gaps on the P_0, Q_k's, P_k's, P_{k-1}, rho, delta, ...). Would also be nice if it is indicated that rho, delta may be inputs to the Algorithm. 

7) Line 364-366: this remark is a bit too much info in too little space, I could not understand it. Can this be explained in a bit more detail? Perhaps in the appendix. Why is convexity in the first argument enough for this construction and how would the construction go exactly? What kind of OCO algorithm would we need; e.g. one with sublinear regret is enough or we need something more advanced? 

8) Line 193: it is never clarified what is meant by easier. Does it mean the gaps are bigger for the expectation case? Or is there somehow a cost in the rate of convergence? 

9) Lines 298-300: I think this could definitely be non-trivial. Also, tuning the regularization or limiting the optimization may break guarantees of the base algorithm (e.g. a fast rate). So it seems there may be a trade-off still between learning speed and monotonicity....?

10) In the related work, you could consider 
Viering, Tom, and Marco Loog. "The Shape of Learning Curves: a Review." arXiv preprint arXiv:2103.10948 (2021).
as it discusses even more causes of non-monotonic learning curves besides dipping and peaking.
Furthermore, you may be interested to know that peaking can be traced back historically already to 1989, see also
Loog, Marco, et al. "A brief prehistory of double descent." Proceedings of the National Academy of Sciences 117.20 (2020): 10625-10626.

11) Definition 2 seems a bit confusing; is this now a Theorem or Proposition or a definition? It seems like almost a theorem or proposition, but it cannot be correct. I guess it should be "Under Assumption 1 and Consistency of the Base Algorithm A is consistent" ?  But then probably it should also mention Assumption 2, and how the gaps are specified. Anyhow, it seems clear that if B is consistent, A must also be consistent, under Assumption a 1 & 2 and for both formula's of the gaps, correct? 
limitations_and_societal_impact: not that I can see
review_title: null

Meta-review: This work makes a novel, surprising, and significant contribution to the area of risk monotonicity, a topic of great interest to the machine learning community. A key consequence of the authors results are a positive resolution of one of the open problems in Viering et al.'s COLT 2019 open problem paper, which is the question of whether it is possible to avoid non-monotonicity of the risk. The authors manage to achieve this in quite a general setting via a wrapper procedure which converts any base algorithm to a new algorithm that achieves risk monotonicity both in expectation and in high probability. That this would be possible at all in expectation was considered to be very surprising. The key to the authors’ approach is a novel concentration inequality for martingale difference sequences which is derived using a guarantee for the recent FreeGrad algorithm; the concentration inequality result itself may be of independent interest and could have impact in the future. In addition, I believe the risk monotonicity results themselves in this paper also may have great impact.

I also want to summarize some of the weaker points of the paper, as well as my and the reviewers' takes from the discussion:
- One point was raised about the validity of the assumptions, and the authors gave a convincing response on how Assumption 1 is quite weak and how Assumption 2 can be removed when one operates in the oft-studied i.i.d. setting.
- Multiple reviewers asked about practicality of the approach; given the theoretical progress made in this work, I myself view practicality as secondary, but even so, I encourage the authors to further discuss practicality/computational issues in the discussion section of their paper, as they have suggested they will do.
- A couple of reviewers also mentioned doing experimental validation, but I find that the theoretical contribution stands regardless of experiments, and if extra space was there, I imagine such extra space could instead be used to get into the ("quite interesting", as one reviewer put it) proof of the novel concentration inequality via FreeGrad.
- Finally, the question of whether randomization is needed came up, and whether we really need the novel concentration inequality. On this point, I found that the authors gave a convincing answer for why they use a novel concentration inequality (avoiding $\log n$, achieving fast rates when possible, etc.), and I do hope they will follow through with the showing a simple example in the appendix where there is no Assumption 2 and no randomization (no need for PAC-Bayes).

I have one comment regarding terminology:
- I disagree that the Bernstein condition with $\beta = 1$ is the Massart noise condition. The Massart noise condition is the best case of the Tsybakov margin condition (the best case), and the latter requires realizability (the Bayes optimal classifier must belong to the class $\mathcal{H}$); moreover, I am almost certain that the name "Massart noise condition" is exclusively used in the context of 0-1 loss. The authors may want to do a quick literature review to get the terminology right.

In conclusion, this is a solid paper that I expect will have high impact both from resolving an open problem and from the novel concentration inequality. This paper should definitely appear at NeurIPS.
Decision: Accept (Oral)