Risk Monotonicity in Statistical Learning
Authors: Zakaria Mhammedi
Venue: NeurIPS 2021 Oral (2021)
Keywords: Statistical Learning
Risk Monotonicity
Concentration Inequalities
PAC-Bayesian Bounds

Abstract: Acquisition of data is a difficult task in many applications of machine learning, and it is only natural that one hopes and expects the population risk to decrease (better performance) monotonically with increasing data points. It turns out, somewhat surprisingly, that this is not the case even for the most standard algorithms that minimize the empirical risk. Non-monotonic behavior of the risk and instability in training have manifested and appeared in the popular deep learning paradigm under the description of double descent. These problems highlight the current lack of understanding of learning algorithms and generalization. It is, therefore, crucial to pursue this concern and provide a characterization of such behavior. In this paper, we derive the first consistent and risk-monotonic (in high probability) algorithms for a general statistical learning setting under weak assumptions, consequently answering some questions posed by Viering et. al. 2019 on how to avoid non-monotonic behavior of risk curves. We further show that risk monotonicity need not necessarily come at the price of worse excess risk rates. To achieve this, we derive new empirical Bernstein-like concentration inequalities of independent interest that hold for certain non-i.i.d.~processes such as Martingale Difference Sequences. 

Risk-Monotonicity in Statistical Learning
Zakaria Mhammedi"
Massachusetts Institute of Technology mhanmedi @mi .ddu
Abstract
Acquisition of data is difficult task in many applications of machine learning, and it is only natural that one hopes and expects the population risk to decrease (better performance) monotonically with increasing data points. It turns out, somewhat surprisingly, that this is not the case even for the most standard algorithms that minimize the empirical risk. Non-monotonic behavior of the risk and instability in training have manifested and appeared in the popular deep learning paradigm under the description of double descent. These problems highlight the current lack of understanding of learning algorithms and generalization. It is, therefore, crucial to pursue this concern and provide characterization of such behavior. In this paper, we derive the first consistent and risk-monotonic (in high probability) algorithms for general statistical learning setting under weak assumptions, consequently answering some questions posed by [53] on how to avoid non-monote monmoonoooiic behavior of risk curves. We further show that risk monotonicity need not necessarily come at the price of worse excess risk rates. To achieve this, we derive new empirical Bernstein-lid like concentration inequalities of independent interest that hold for certain non-i.i.d. processes such as Martingale Difference Sequences.
1 Introduction
Guarantees on the performance of machine learning algorithms are desirable, especially given the widespread deployment. A traditional performance guarantee often takes the form of a generalization bound, where the expected risk associated with hypotheses returned by an algorithm is bounded in terms of the corresponding empirical risk plus an additive error which typically converges zero as the sample size increases. However, interpreting such bounds is not always straight forward and can be somewhat ambiguous. In particular, given that the error term in these bounds goes to zero, is tempting to conclude that more data would monotonically decrease the expected risk of an algorithm such as the Empirical Risk Minimizer (HRM). However, this not always the case; for example, 33 showed that increasing the sample size by one, can sometimes make the test performance worse in expectation for commonly used algorithms such as ERM in popular settings including linear regression. This type of non-monotonic behavior is still poorly understood and indeed not desirable feature an algorithm since it is expensive to acquire more data in many applications.
Non-monotonic behavior of risk curves 47 the curve of the expected risk as a function of the sample size-ha has been observed in many previous works [8
(see also B3 52 for
nice accounts of the literature). At least two phenomena have been identified as being the cause behind such behavior. The first one, coined peaking (30 or double descent according to more is the phenomenon where the risk curve peaks at a certain sample size n. This sample size typically represents the cross-over point from an over-pare parametraeteee to paddr-pprameterizee model. For example, when the number of data points is less than the number of parameters of a model (over-parameterized model), such as Neural
recent literature 6 49 7
17
15
37
40
41
16
12
11
14 42
Work done while at the Australian National University.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Networks, the expected risk can typically increase until the number of data points exceeds the number of parameters
model). The second phenomenon is known as dipping [2] 31]. where the risk curve reaches a minimum at a certain sample size n and increases after that never reaching the minimum again even for very large n. This phenomenon typically happens when the algorithm is trained on surrogate loss that differs from the one used to evaluate the risk {8]
is becoming more apparent that the two phc- nomena just mentioned (double descent and dipping) do not fully characterize when non- monotonic risk behavior occurs [34]. [33]
0.89
Expected risk of ERM h, risk of best model in H
showed that non-monotonic risk behavior could happen outside these settings and formally prove that the risk curve of ERM is non-monotonic in linear regression with prevalent losses. The most striking aspect of their findings is that the risk curves in some of the cases they study can display a perpetual "oscillating" behavior; there is no sample size beyond which the risk curve becomes monotone- see Figure |I In such cases, the risk's 'ss non non-monotonicity cannot be attributed to the peaking/double descent phe- nomenon. Moreover, they rule out the dipping phenomenon by studying the ERM on the actual loss (not a surrogate loss).
0.88
Expected risk
0.86-
0.83
0.81
20
100
Sample size n
Figure 1: Expected risk of ERM on ld lin- ear regression problem with absolute loss and two instances 21 (I1. //1 = (1, and 22 = (22, 22) = 1) such that P 21] 0.1 and P ] 0.9.. The set of hypotheses is the real line, i.c. H IR. The ERM solution h. admits a closed form in this case see 33 for details.
The findings of (33] stress our current lack un- derstanding of generalization. This was echoed more particularly by (53), who posed the follow- ing question part of COLT open problem:
How can we provably avoid non-monotonic behavior?
While excess risk bounds are typically monotonic, this does not guarantee the monotonicity of the actual risk. In this work, we study under which assumptions on the learning problem there exist consistent and risk monotonic algorithms. We also aim to quantify the price to pay, in terms of corresponding excess risk rates, for achieving risk monotonicity.
Contributions. In this work, we answer some questions posed by 53 by presenting an algorithm that is both consistent and risk-monotonic in high probability under weak assumptions on the learning problem. Our algorithm is technically "wrapper" that takes as input any base learning algorithm B and makes up new algorithm A that risk monotonic in high probability and enjoys essentially the same excess risk rate as B. Crucially, our results show that risk monotonicity need not come the expense of worse excess risk rates. In fact, we show that fast rates are achievable under Bernstein condition (Definition 3)
Our results hold under the general statistical learning setting with a bounded loss. We even go beyond the standard i.i.d. assumption on the loss process. Our relaxed technical condition on the loss process, which is formalized in Assumption [ below, is reminiscent of the condition characterizing Martingale Difference Sequences (MDS). In nutshell, we will assume setting where the instance random variables Z,, Zz.... and the loss satisfy, for all hypotheses h, E[ Z,) Z Z--1] = L(h), for some risk function L.. This is trivially satisfied in the i.i.d. case, where I, corresponds to the standard risk function. In general, this condition may be satisfied even if Z1, Zz.... are dependent or have different marginal distributions. We argue that our relaxed assumption the loss process is the weakest assumption under which studying mask-monotonicity still makes sense.
To achieve risk monotonicity under our loss process assumption, we derive new concentration oegualiitygenerraliztionn bound of PAC- MAC-Bayesian flavor for MDS (see Proposition
5). This concentra- tion inequality may be thought of as an empirical Freedman's 's inequality [23] or as an extension of the empirical Bernstein inequality 35 to MDS. Our concentration inequalities also have the advantage of being fime-uniform with the optimal dependence on the number of samples. Here, time-uniform means that the inequalities hold for all sample sizes simultaneously. While standard concentration inequalities can be turned into time-unifom ones using union bound over the number of samples

---

n, the resulting bounds will have a sub-optimal In n factor instead of the optima In In n that we are able to get. Finally, our concentration bounds are easily derived using the guarantee of a recent parameter-free online learning obtaining new concentration inequalities through the design of online learning algorithms.
39. Our approach opens up the door for
Approach Overview. Our approach to deriving the new concentration inequalities based on the guarantee of the recent FREEGRAD algorithm. The algorithm operates in rounds, where at each round t. FREEGRAD outputs W in some convex set W. say IR, then observes a vector 9, e R typically the sub-gradient of loss function at the iterate WG The algorithm guarantees a regret bound of the form Σ g. (w; w) Ö([w VQT), for all w E W. where Qr Σi=1 l19.1". What is
more, FREEGRAD'S 's outputs (w:) ensure the following (see [39 Theorem 5)):
1 9. (Se. Qi) s ( Qi-1).
V 1,
(1)
where S 1 9.ll. Q₂ = Σl- l1..1? and ((S = exp( 7*+V+ 12
7-+ ) for any ? > O.
Instantiating this guarantee in 1d with (g.) set an MDS (X,) and taking (conditional) expectation in (1) shows that क; ((Ei_, X, (._1x?) is non-negative supermartingale, from which concen- tration results can be obtained via Ville's inequality (a generalization of Markov's 's inequality- -ee Lemma [8]. Our proof technique is similar to the one introduced in 28 with the difference that use the specific shape of FREEGRAD'S potential function to build our supermartingale, which leads desirable empirical variance term in the final concentration bound.
On the side of risk monotonicity, given n samples, the key idea behind our approach is to iteratively generate sequence of distributions P1, P2. ... leading up to P. over hypotheses, where we only allow consecutive distributions, say Pk-1 and P& to differ we can guarantee (with high enough confidence) that the risk associated with Ps is lower than that of Pa-1- To test for this, we compare the average empirical losses of hypotheses sampled from PA-1 versus ones sampled from Px. taking into account the potential gap between empirical and population expectations. Applying our new concentration bounds to quantify this gap not only allows us to achieve risk monotonicity under non-i.i.d. loss process but also enables condition. For the latter, it was crucial to have an empirical loss variance term in the concentration inequality.
achieve fast excess risk rates under the Bernstein
Related Works. Much work has already been done in efforts to mitigate the non- monooonic behavior of risk curves (3). For example, in the supervised learning setting with the zero-one loss, (9] introduced the "memorize" algorithm that predicts the majority label on any test instance that was observed during training; otherwise, default label is predicted. [9] showed that this algorithm is mak-monot. However, it is unclear how their result could generalize beyond the particular setting they considered. Risk-monotonic algorithms are also known for the case where the model correctly specified (see 33 for an overview); in this paper, we do not make such an assumption.
Closer our work is that of (54] who, like us, also used the idea of only updating the current predictor for sample size n if it has lower risk than the predictor for sample size n-1. They determine whether this is the case by performing statistical tests on a validation set (or through cross- pross-validation). They introduce algorithm wrappers that ensure that the risk curves of the final algorithms are monotonic with high probability. However, their results are specialized to the 0-1 loss and they do not answer the question by 53 on the existence of learners that guarantee a monotonic risk in expectation.
On the side of concentration bounds for non-i.i.d. processes, our results are somewhat similar to those found in e.g. [27 26). However, our technique for deriving them, which relies on the guarantee of a parameter-free online learning algorithm, entirely different. The theoretical link between online regret and concentration inequalities was previously drawn-see e.g. [45] 22). However, our approach is slightly different as we use the monotonicity of an online algorithm's 's potential function to get our concentration results. Thus, new concentration inequalities may be derived similarly by modifying the explicit potential function directly. Our approach is more similar that of (28) who also derived concentration incqualities using guarantees of online betting algorithms that bet fractions smaller than one of their wealth at each round.
"One can not improve on the In In factor by the law of iterated logarithm
B3
3

---

We allow for a parameter h é H. in our concentration bounds to make the results useful in the statistical learning setting. These bounds are of -AC-sssesi type and are somewhat reminiscent of those in We refer the reader to 25 for an overview of existing PAC-Bayesian bounds.
50 38
Outline. In Section we introduce the setting, notation, and relevant definitions. In Section B] we present our new concentration inequalities for Martingale Difference Sequences and loss processes we are interested in (those that satisfy Assumption (ebloow.. In Section we present our risk-monotonic algorithm wrapper and show that it achieves risk monotonicity in high probability. We conclude with a discussion in Section [ The proofs of the new concentration inequalities and risk monotonicity are
differed to Appendices B Man respectively. Appendix A presents existing and new technical results
needed in some of our proofs.
Preliminaries
In this section, we present the setting, notation, and relevant definitions for the rest of the paper.
Setting and Notation. Throughout, we will assume an underlying probability space (2, F,F,P) Let 2 [resp. H] be an arbitrary feature [resp. hypothesis] space, and let é H x 2 [o, 1] be a bounded loss function. We denote by A (H) the set of probability measures on H. Data is represented by random variables Z1, Zz.... Z that we assume fashion. We use the concise notation Zı for the tuple (Zi,..,, Ze) and denote by G, the o-algebra generated by the random variables Zi,...,24 Zz, with the convention that Go
accessible to learning algorithm in a sequential
We will write
E.-1[-]== == E( [6-1]. for 2
We will not assume that the random variables (Z,) are independent and identically distributed. Instead, we will make the following weaker assumption on the loss process Zt)):
Assumption 1 (Process Assumption). There exists a risk function L: [0, 1] such that the sequence of random variables Z,, Zy,... satisfy Et-1 Z.)] L(h), for all h H and t 2 1.
When the random variables Z1, Zz..... are i..dd and Z, Pz, i N, then Assumption D trivially holds with the standard risk function L(h) EE (2) [[(h, =)]. In Assumption] I the conditional distribution of Z, given Gi-1 may be arbitrary as long as the corresponding conditional expectation E,-1 of the loss of a given hypothesis h is the same (equal to L(h)) for all / 2 1. Arguably, Assumption [ represents the weakest condition under which studying risk monotonicity in the statistical learning setting still makes sense. We touch more on this point after defining risk monotonicity below. To simplify notation for the rest of this paper, we let
I(Q)= ((o()[[(A)) for all Q (H))
where L is as in Assumption !
A learning algorithm A is map from U. 2' to A (HH); given data Z the output A A(Z1:)) of the algorithm is a distribution over hypotheses in H. This definition includes deterministic algorithms for which the distribution A is Dirae at some h = h (. We will use the notation A(- Z1:)) = A( A(Zz=)().
Throughout, we will make use of fixed "prior" distribution Po over hypotheses in H. In Section 4 we will present an algorithm wrapper that takes any base algorithm as input and makes a miskmmonotonic algorithm out of it with essentially the same excess risk rate. The results of this paper are useful for base algorithms that output distributions that are absolutely continuous w.r.. our choice of prior Po; that is B Zux) << Po. for all t 2 O In practice, if H Rd Po may be multivariate Gaussian around the origin and B(Zi.) may also be a multivariate Gaussian around the ERM hn é arg in Σ E(h, Z:), in which case B( ((.a) < Po holds for all t 2 1. We now define the notion of risk monotonicity we will work with:
Definition 1 (Risk Monotonicity). For 5 E (0.1) and N 1, we say that learning algorithum A: U 2 + A (?L) is (6, ( risk---oooioooooiiiiiii if, with probability at least 1 1-5, 5,
Vt N,
EA [Er[e(h. Z+-1]] EA(H)Z)))) [E.-[[(h,, Z,)
'e inherit this restriction from the PAC- -CC-Baysiaan approach that we use to quantify generalization. In Appendix() D we show how this restriction can be removed in the i.i.d. setting (see also Remark 7

---

Note that since the loss é is positive, Fubini's theorem implies that E EAcllZaa 1) [Br-I[((h,Z,) 2,]]]= Et-1
Zu- Zn (e((,, ].]]] for all t 1. Thus, the condition in (2) requires the expected loss of algorithm A on the next sample, conditioned on the past data, to decrease with the size of the data. We note that if Assumption fashion, then requiring (2) would be too strong. Thus, we will restrict our attention to processes that satisfy Assumption ! We stress that the condition in this assumption weaker than i..dd, and allows the random variables Z1 Zz.... to have different (conditional) distributions as long as the moment constraint [,-,, Z.)] L(h) satisfied for all H. and t 2 1.
| does not hold and Ee Ze+1)] depends on in an arbitrary
The notion of monotonicity presented in 33 53
concerned only i.idd random variables, and requires the risk to be monotonic in expectation opposed to in high probability. In particular, the strongest notation of monotonicity in [33. which they refer to as global Z-monotonicity, can be expressed as
vt 2 1, E [[AAM) & E
(3)
where L(h) == [(((h))((h,2)) and Z2...... Lid. Pz. We will show that achieving risk- monotonicity in expectation to a small fast rate term is as easy as achieving )-risk- monotonicity-at least for bounded losses. In fact, we will show how our risk-monotonic (in the sense of Def. ① algorithm can easily be turned into one that satisfies (3) up to fast rate term.
Monotonicity alone is rather easy to achieve; it suffices output fixed hypothesis h H. regardless of the training dataset. In this case, the risk would be constant, and so risk monotonicity is achieved by definition. In practice, it is important generate hypotheses with low risk, and so a fixed hypothesis that does not dependent on data is likely to be useless. Formally, we want algorithms that are risk monotonic and consistent:
Definition 2 (Consistency). Under Assumption 7 we say that algorithm consistent for any <> 0, nom P
[T[h]] - inf [(h)] > c]
We will go beyond the notation of consistency and study the rate of convergence of the risk of our algorithm to the optimal risk. We do this under the assumption that the loss process E(h, Z.) satisfies the Bernstein condition for h E Hc:
Definition 3 (Bemstein Condition). For B [0. 1] and B > O, the (8, B)-BBBBBle Berrssstei condition holds if the random variables Z1, Zz.... and the loss E satisfy, for all 2 and all h e H.
E (e(h, 2,) - -Ehh., 2,)) BE,
2,) ,(hh,,,)]* Z,)
for h. e arg her E.- [E(h, Z.)].
The Bernstein condition 3 4
21 29] essentially characterizes the easiness of the learning problem. In particular, it implies that the conditional variance of the excess-loss random variable E(h, 2,) - E(h,, Z.) vanishes when the risk associated with the hypothesis / E H gets closer to the H-optimal risk L(h.). ). For bounded loss functions, the Bernstein condition with / 0 always holds, and so the results of this paper are always true for 3= = O. The Bernstein condition with 3 1 corresponds to the easiest learning setting. The case where 3 E (0, 1) interpolates naturally between these two extremes, where intermediate excess-risk rates are achievable. We refer the reader to 29 Section 3] for examples of learning settings where Bernstein condition holds.
5
Additional useful definitions.
For p > and 8 (0, 1). we define
= K21 (k 2 3.2;
(n) == c/p 110++111n,0 1(m,, (n) 1) In² (I, + +2;
(4)
and n1 sup e (n)()
(5)
Note that ng is not too large as a function of 1/5. In fact, the definitions of o, and ns imply that ns ((m(118)) In the next section, we present some new concentration inequalities of independent interest that will be useful in achieving risk- misttnnntyy under Assumption I while maintaining good excess risk rates.
3 New (PAC-Bayesian) Concentration Inequalities
In this section, we present some new concentration inequalities of PAC-Bayesian flavor that will be crucial to deriving our risk monotonic algorithm wrapper under Assumption I
These concentration
5

---

inequalities hold for non-ii.d. data (which we require to accommodate Assumption D and are so- called time-uniform; the inequalities hold for all sample sizes simultaneously given fixed confidence level. We explain below the advantage that this has in our setting.
We start by a new concentration inequality for Martingale Difference Sequences, from which derive the bound we need under Assumption I First, we give the formal definition of an MDS:
Definition Lei (Fi) sell be a filtration w.r.t. the underlying probability space (S,, P), L.e. (Fi) teN is a sequence of non-decreasing sub-a-algebras of F. A sequence of random variables (Xt) is an MDS w.r.t. (Fi) for all 2 1, X₃ is F-mmesuurable; E[|X,[] <o; and E| Fc-1] ] 0 a.s.
With this in hand, we present our first concentration inequality:
Proposition& 5 (PAC-Bayes for MDS). Let > 1 and Op be as in 4 Further, let (X,) be a family of random variables taking values in [-1,1] and (Fi) be a filtration such that (X²) is an MDS
w.r. to (Fi) 1o, for all h H. Then, for any distribution Po on H and all 8 (0, 1), we have
Er(, [|
(n) 8
P Yn 1,P,, 2(p+ 1)) V. + 2E [[S
S <KI(P)P))
2 11 6, (6)
where 8hh Ei X and Vit = 1 Σ (X/)
The proof of the theorem is in Appendix B The bound in Proposition 5 does not look like the typical PAC-Bayesian bound. However, simple algebra reveals that for any C> 0,
EP( 12 2(p 1)E [VP] + (EP()) SC EpgN[[S s 2C + / 1)) [VA]] C.
Combining this with the fact that [EP()] [PS)) (by Jensen's inequality), and (6) we obtain, under the same conditions as Proposition that
P 22 E A (71), [P(M[[ s 2C, (P) + v2(0+ 1VP) CC. CC.))) 2 1 (7)
where CP) KI(P)P) + In
(n)o). When H. is singleton, the concentration inequality in (7) can be viewed as an empirical version of Freedman's 's inequality [23 for MDS. The inequality is also reminiscent of the PAC-Bayesian empirical Bernstein inequality due to (50). In addition to it holding for MDS, another advantage 7 is that is time-uniform-itt holds for all sample sizes n, simultancously. While standard concentration inequalities that hold for a fixed sample size can be turned into Lime-uniform ones by applying a union bound over sample sizes, the resulting inequalities will have sub-optimal In factors under the main square-root error term. In contrast, the concentration inequality in 7 has a In(,,(n) = O(I In term, which matches the optimal dependence in n according the law of iterated logarithm [13 MDS is central concept in probability theory 44 and machine learning 10. and so our result in Proposition 5 is of independent interest.
Interestingly, the concentration inequality in Proposition is derived using the guarantee of parameter-free online Aggrithm-FREEGRRM This opens the door for new ways of deriving such concentration inequalities through online learning algorithms, adding to existing results due to
45 22 28
Using the result of Proposition 5) we are now going to derive time-uniform "Empirical Bernstein" concentration inequality that holds under Assumption I
Theorem 6. Let 8 E (0,1). p 1, and op be as in Further, for Po (H) define en
2(p=1) (KL(PIP) + In de(n) and Pa == (P: e.. > 0}. Under Assumplion we have
Ven(P) Pn(PP) + p+l
Sn(P))
1 Σ
P Vn ns. VP n
Ep(n [e(h,Z)) [(hh]
2 1 8,
1-En(P)
where (P( = 1 Σi EP(N) (((h, ΣL, Ep(O) [((0,))1))] and ns is as in
The restriction that P Pr in the theorem merely ensures that the denominator in the concentration bound remains positive. The set P,, is guaranteed to be non-empty for all 2 nz. In this case, P is in

---

Pn. whenever 8(p+1 1) ( n. which is a fairly weak condition on the distribution P; even for large models such as Neural Networks the KL-divergence P)) does not typically grow superlinearly with the size of the sample used to generate the posterior P [55 Nevertheless, we note that if one only cares about the i.i.d. setting then other concentration inequalities may be used to achieve risk monotonicity without restrictions on the posterior P (see Appendix D
The concentration inequality in Theorem O can be viewed as an extension of the empirical Bernstein inequality in [35, 50] that holds under the non-i.i.d. condition described in Assumption | Our new bound is also time-uniine uniform with the optimal dependence in the sample size n. As mentioned before, simply applying union bound to a standard (non-tine time- concentration inequalities to obtain its time-uniform version will lead to a sub- sub-optimal dependence in n. When H. a singleton (i.e. no learning), the concentration inequality becomes reminiscent of an existing one due to [26]. However, the latter has term that looks like, but is different than, the empirical variance, and so it is not directly comparable to ours. The proof of Theorem iss postponed to Appendix B
Finally, we note that for any sample size n the value of p Theorem 6 that minimizes the bound would typically fall within the interval (1, 2). One can tune as a function of the data by treating P as an extra "hypothesis" parameter. In the case of finite grid & (1, +00) of p's. the result of Theorem 6 would hold for all G inside the probability event as long as any ())P instance is replaced by (I) In [g).
We now move on to describing our risk monotonic procedure that makes use of our new concentration inequality.
Risk Monotonicity in Statistical Learning
In this section, we combine the concentration inequality from Theorem with a novel "greedy" procedure for selecting distributions over hypotheses to derive risk monotonic algorithm in the statistical learning setting. With the right choice of gap sequence (E.), the procedure we present in Algorithm takes as input a base learning algorithm B : - Z + A (H) together with samples Zim. whose generating process satisfies Assumption [ and returns a distribution over H that has monotonic risk as function of n. with high probability. By leveraging our new concentration inequality in Theorem 6 to specify the gap sequence (S.), we further show that achieving risk monotonicity need not deteriorate rates of convergence to the optimal risk in he T.hh). In fact, we show that it is possible to attain fast rates under the Bernstein condition (Definition B To arrive at this result, it was crucial for our concentration inequality to have an empirical variance term.
Algorithm A Risk Monotonic Algorithm Wrapper Require:
A base learning algorithm B: B: Z' (HH). Samples Zi,..., Zn-
A sequence of gap functions (Ex), where & = Ex (ZiR, B) for all k.
(Ex) will be set
according to [resp. [II] for misk-monooynicity in probability [resp. expectation].
1: for k
do
& Σ
2:
if
E EB(h Z. [((,, 2,)]
Er (.),(())(( 2,)] -Ex then i-1
h: 1-1
3:
Set Ps = B (.
4:
else
5:
Set P& = Pk-1-
6:
Return Pn.
To simplify our analysis, we will focus our attention on base algorithms that are restricted in the following way:
Assumption (Base Algorithm Restriction). We assume access to a base algorithm B: U Z A (H) such that for p> 1, prior distribution Po on H. and all i 2 1,
B(Zr*) E Q2 == {Q (H)) 16(p 1) KL) s kk.
(8)
7

---

In other words, we are restricting our attention to algorithms whose posteriors given samples of size do not have a KL divergence the prior Po that grow too quickly with k. We make this assumption to satisfy the technical conditions needed for the concentration bound in Theorem be non-vacuous. Assumption
reasonable even for large Neural Network models [55
In practice, if H is RR, an option for B is the algorithm that outputs a multivariate Gaussian distribution around a regularized ERM. The KL-divergence between the outputs of B and Po can be controlled by tuning the regularisation parameter(s) and/or the co-variance matrix of the multivariate Gaussian.
Remark 7. If one only cares about i.i.d. loss processes, Assumption 2 can be removed by using generalization bounds based on the standard Bernstein concentration inequality, e.g. 150, 36%, which would also enable our risk decomposition in Theorem / below (and thus fast rates). We make Assumption Iatiiioonnnnlyyyl only to bound the denominator in our (non-i.i.d) concentration in Theorem 6 aaway from zero, which is not needed for other concentration bounds in the i..dd setting such as those in 150 36 (see Appendix fioor more detail).
To specify the sequence of gaps (En) that our wrapper Algorithm [ requires, we will use our concentration bound in Theorem 6 We recall that using this concentration bound instead of other existing ones allows us to I) achieve risk monotonicity under a weaker condition than i.i.d. on the loss process (Assumption in this case); and If) to achieve potentially fast excess risk rates under the Bernstein condition. The latter is made possible by the fact that the concentration bound in Theorem has empirical loss variance term that allows particularly useful decomposition of the excess risk under the Bernstein condition (see Theorem | below).
To give a concise expression of the gaps (E*), we let Qx == B(Z2.)) x Pk-1, where (Pk) are the intermediate distributions generated internally by Algorithm 1/0 +00, we define
!
With this, and the convention that
VEL. VE +
2eB A+1
2 2KL Po x Po) +2 (2(1) o
E =
where
C₁ ==
and
(9)
11 -e
k. +.( + 1)-1
Σ Equ(h.n) D2- = T: [=1
(((h, E(, (2)
E Equ(h.) E=1
[e(h, 2x) E(,, 2,)1
We note that our Assumption 2 Jensures that 6, S. 1/2 (which in turn ensures that the gaps (En) are not
too large), for all 2 nsg where n& is as in ( This follows from the fact that KL Q+ Po Po) (..B)...)l (P)+KKLA ( Pa- Po). and that there exists m < k such that Pa-1 B(Z E 2m S O
(by definition of (Px) in Algorithm D. Furthermore, 2n + Ø for all 2 nzg-
Before presenting our results for this section, we also note that Algorithm | asssmmes we can evaluate expectations over the output distributions of B. Such expectations can be approximated via Monte Carlo sampling, and any approximation errors need be added to the gaps (Ex) to maintain the guarantees present. Alternatively, one can avoid estimating expectations by applying recent derandomization techniques, see e.g. 46 51 or by using other, non PAC- MAC-Bayesian generalization bounds (see Appendix D)
We now state the guarantees of Algorithm I proof is postponed to Appendix C
We start by the statement of risk-monotonicity (the
Theorem 8 (Risk Monotonicity). Let 5 E (0,1) and ns be as in (). Under Assumptions 7 and
Algorithm 7 with (Ex) as in (9) is (5, riss))))skmooooon according Definition] 7
We now show that risk monotonicity need not come at a worse excess risk rate. Under the Bernstein condition, we have the following excess risk decomposition for the output of Algorithm I
Theorem 9 (Risk Decomposition). Let B > 1, 3 E [0, 1]. and suppose that the (3, B)erneBennt condition holds. Further, for p > and ō (0, 1), let rıs and en be as in (5) and (2) respectively.
Then, under Assumptions 1 and the outputs (Px) of Alg. satiisfy with probability at least 1 - 28,
Yn nig, L(P.) - L(h.) s 3(L L(h))) O (En)
(10)
where h. E ang L(h).
'Besides, when the KL divergence is very large, it is often very hard to infer non-vacuous generalization bounds (which one may view as prerequisite to achieving risk monotonicity) using PAC Bayesian approach.
8

---

We stress that this risk decomposition was only made possible by the fact that our concentration bound in Theorem 6 has an empirical loss variance term.
Theorem D shows that the excess risk of Algorithm Dis is at most a constant times the excess risk of the
base algorithm B, plus potentially lower-order term O Z-3 ). To appreciate what this additional term is doing, consider the case of finite hypothesis class H. In this case, the definition of e, in ?
implies that C, s O In B Thus, G1 interpolates between the fast A/ In In rate under the
best Bernstein condition with 3 1 and the standard (up to log-log Log-log-factors) rate V 1 In Ha under the Bernstein condition with 8 O, which we recall always holds for bounded losses. What is more, if H. is finite and algorithm B is the ERM, i.e. if B Z1.x) is Dirac at h. arg inf Σ E(h, Ze), then we have the following explicit excess risk rate for Algorithm [
7
Proposition 10. Under the setting of Theorem 2 H is finite, Po set to the uniform prior over H. and B (1)) is a point mass around the ERM h arg min Σi=1 E(h, Z.), Vn 1, then Alg. is risk monotonic according to Def. 7 and its oulputs (Pk) satisfy, with probability at least 1 26,
In 17 lun
Vn ns (16(p+1)ln In))))) T(P.)- T(h.) s so
n
The story is not much different for a continuous set H. The standard excess risk rate one would expect from algorithm B is (BL(((())))))) +ln(1/6)//; which can dominate the right-most term in our risk decomposition 10 since
(En) I 2 maxksn (L(B(Z(a))P)) In lan 2-8
T2
Together, the above inequality and Theorem show that fast rates for algorithm I are achievable whenever the Bernstein condition holds with 5 O and the base algorithm B itself achieves a fast rate (when is finite and B the ERM, Proposition shoswws that it sufficient that 3 0). Thus, risk monotonicity need not come at the price of worse rate of convergence to the optimal risk. Finally, we note that the factor 3 in our risk decomposition (1O) is just an artifact of our analysis. In fact, by slightly modifying achievable at the cost of a larger lower-order term in (10).
proof of Theorem g one can show that any factor in the interval (1,3] is
Risk monotonicity in expectation. The original open problem due to 53 was around risk mono- (3) Our algorithm wrapper also allows us to almos achieve this
tonicity in expectation- notion of monotonicity with slight modification of the sequence (Ex) in (9); we essentially set the confidence level as a function of k. In fact, the next result shows that risk monotonicity in expectation is achievable up to an additive fast-rate term:
Theorem 11. Let 2 1, p> 1, and o, be as in (4). Under Assumptions 7 and 2 Algorithm 7 with the sequence of gaps (Ex) given by
[| 1- (V4. Vi+ 26/
Ea = E
(11)
p+
with e == gorithm satisfies, for all 12 N = sup (n: 8In(n' (n) > n)
1(p=1) (KL(B(ZIa) P Po x Po) + 2 222 (k)) + 2b knk) and (Pt) being as in Al-
k
E (n [L))]]
E E [L + 1/t².
(12)
We note that N need not be too large since (n) s 0 n). However, while taking large will make the additive 1/th term in 112 small, it will increase the sample size N beyond which (12 holds.
$ We note that it is typical that max4s. KL(B(Z 1 PP) O(KL(B(Z)..) Pb)). for 1. 'We thank Olivier Bousquet and his colleagues for pointing out mistake in the original proof of Theorem 11 The theorem originally claimed that [ achieves monotonitty in expection without the additive 1/th term in [2 which turns not be correct.

---

Ignoring the additive 1/t" term, the notion of risk monotonicitt in theorem 11 corresponds to the notion of weak Z Z-monotonicity in [33] one of their strongest notions of risk monotomicity since holds for all data generating distributions (granted Assumption I holds, or the data is i.i.d.). We can modify Algorithm to make globally Z-monotonic, where (12) would hold for all 2 (instead of t 2 N), by forcing the outputs Pk of the algorithm to be Po for all & < N.
With the same choice of gap sequence (Ex) in Theorem 11 it is easy to show (following almost the same proof steps as in our previous results) that the excess risk rates in Theorem 9 and Proposition 10 will hold with probability 1/n" (instead 8) for every sample size n.
5
Discussion and Future Work
The primary goal of this paper was to answer the fundamental question around the existence of consistent, risk-monotonic algorithm in the general statistical learning setting. We answer this in the affirmative for notation of monotonicity that holds with high probability and further show that there is virtually no cost for achieving this when it comes to excess-rie rxcess-risk rates. We believe this is an important milestone in the search for risk- monoooncc algorithmss It remains to see if mistttoooty in expectation is achievable; i.c. achieving (12) without the additive term.
From a computational perspective, the main setback of Algorithm iis that returning the distribution Pa Pr, (Zim) requires n-calls to the base algorithm B. This implies that 1 may run times slower than B in the worst case. However, when the base algorithm outputs distributions centered at ERMs, may be possible to efficiently generate the sequence of distributions (B( Zi:)) )) by leveraging the fact that ERM solutions for sample sizes l and l: + 11 can be close to each other.
When the loss l is convex in the first argument, there is no need for randomized algorithm (i.e. we do not need B(Z < Po), and it is possible to efficiently generate a sequence of predictors (h,,) with monotonic risk using an online convex optimization algorithm as the base algorithm B. However, in general, it is unclear whether risk monotonicity can be achieved without the (greedy) for-loop procedure of Algorithm [ We note also that if one only wants decreasing risk after some sample size N, then computing the distributions (Px) (e=) is unnecessary. this case, the for-loop in Algorithm ② need only start at k = 8; the resulting hypotheses would satisfy the monotonicity condition Definition for all 2 8 v Tig-
D
Through Theorem 9 we showed that the excess risk of Algorithm I iss at most three times that of the base algorithm plus a lower-order term. remains evaluate the empirical performance of the algorithm to identify for which applications the additional cost in the excess risk is worth it to achieve risk monotonicity.
Some important questions remain open along the axes of assumptions. In particular, can we remove the boundedness condition on the loss while retaining fisomoonttoiccity? It might be possible to achieve this for unbounded convex losses using the non-exponential weighted aggregation techniques recently suggested by (2). Lifting the boundedness assumption may be key in resolving another COLT open problem (24) regarding achievable risk rates of log-loss Bayesian predictors. Our results build foundations for these avenues, which are promising subjects for future work.
Finally, would be interesting to explore what other concentration inequalities for non-i.i.d. processes can be derived using other parameter-free frree online learning algorithms. An obvious starting point is to look at MATRIX- -REEEGRD 339
"Randomization is also not needed if one is only interested in i.i.d. processes (see Appendix D
10

---

Acknowledgments and Disclosure of Funding
We would like thank Hisham Husain for instrumental discussions during the early phases of the project. We thank Olivier Bousquet and his colleagues for pointing out a mistake in the original proof of Theorem [T] We also thank anonymous reviewers for their valuable feedback. This work was supported by the Australian Research Council and Data61.
References
[1] Amir Ahmadi-Javid. Entropic value-at-risk: A new coherent risk measure, Journal of Optimiza- tion Theory and Applications, 155(3):1005-1122 2012.
[2] Pierre Alquier. Non-exponentiially weighted aggregation: regret bounds for unbounded loss functions. arXiv preprint arXiv:2009.038: 03017, 2020.
[3] Yean-Yves Audibert. PAC-Bayesian statistical learning theory. These de doctorat de I' l'Université Paris, 6:29, 2004.
[4] Peter L. Bartlett, Michael I. Jordan, and Jon D. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138-136 2006.
[5] Peter L. Bartlett and Shahar Mendelson. Empirical minimization. Probability Theory and Related Fields, 135(3)3311-334, 2006.
[6] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine learning and the birs-variance trade-off. arXiv preprint arXiv:1812.11111 2018.
[7] Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. arXiv preprint arXiv: 190300777,, 2019.
[8] Shai Ben-David, David Loker, Nathan Srebro, and Karthik Sridharan. Minimizing the misclas- sification error rate using surrogate convex loss. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pages 83-90, 2012.
[9] Shai Ben-David, Nathan Srebro, and Ruth Urner. Universal learning vs. no free lunch results. In Philosophy and Machine Learning Workshop NIPS, 2011.
[10] Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[11] Prasad Cheema and Mahito Sugiyama. A geometric look at double descent risk: Volumes, singularities, and distinguishabilitiss. arXiv preprint arXiv:2006. 04366, 2020.
[12] Lin Chen, Yifei Min, Mikhail Belkin, and Amin Karbasi. Multiple descent: Design your own generalization curve. arXiv preprint N0X::20000000336 2020.
[13] DA Darling and Herbert Robbins. Iterated logarithm inequalities. Proceedings of the National Academy of Sciences of the United States of America, 57(5):1188) 1967.
[14] Stéphane d' Ascoli, Levent Sagun, and Giulio Biroli. Triple descent and the two kinds of overfitting: Where & why do they appear? arXiv preprint 20xXi:20006033500 2020.
[15] Zeyu Deng, Abla Kammoun, and Christos Thrampoulidis. model of double descent for high-dimensional binary linear classification. arXiv preprint (91.::/9 2019.
[16] Michal Derezinski, Feynman T Liang, and Michael W Mahoney, Exact expressions for double descent and implicit regularization via surrogate random design. Advances in Neural Information Processing Systems, 33, 2020.
[17] Michat Dereziński, Feynman Liang, and Michael W. Mahoney. Exact expressions for double descent and implicit regularization via surrogate random design, 2019.
[18] Robert P.W. Duin. Small sample size generalization. In Proceedings of the Scandinaviar Conference Image Analysis, volume 2, pages 957-964, 1995.

---

[19] Robert P.W. Duin. Classifiers in almost empty spaces. In Proceedings 15th International Conference on Pattern Recognition. ICPR-2000, volume 2. pages 1-7. IEEE, 2000.
[20] Robert P.W. Duin. Learning to generalize. Frontiers of Life. 3(part 2):763-775, 2001.
[21] Tim Van Erven, Nishant A. Mehta, Mark D. Reid, and Robert C. Williamson. Fast rates in statistical and online learning. Journal of Machine Learning Research, (6:1793-1861, 2015.
[22] Dylan J. Foster, Alexander Rakhlin, and Karthik Sridharan. Online learning: Sufficient statistics and the Burkholder method. In Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018., pages 3028-3064 2018.
[23] David A Freedman. On tail probabilities for martingales. the Annals of Probability, pages 100-118 1975.
[24] Peter D Grünwald and Wojciech Kotlowski. Bounds on individual risk for log-loss predictors. In Proceedings of the 24th Annual Conference Learning Theory, pages 813-816, 2011.
[25] Benjamin Guedj. primer on pac-bayesian learning. arXiv preprint arXiv: 1901.00000.05000 003053,5533,.0 2019.
[26] Steven R Howard, Aaditya Ramdas, Jon McAuliffe, and Jasject Sckhon. Time-uniform. nonparametric, nonasymptotic confidence sequences. The Annals of Statistics, 1952):0055-1080, 2021.
[27] Steven Howard, Aaditya Ramdas, Jon McAuliffe, Jasject Sekhon, et al. Time-uniform cherooff bounds via nonnegative supermartingales. Probability Surveys, 17:257-317, 2020.
[28] Kwang-Sung Jun and Francesco Orabona. Parameter-free online convex optimization with sub-exponential noise. In Conference on Learning Theory, pages 1802-1823, 2019.
[29] Wouter M. Koolen, Peter D. Grünwald, and Tim Van Erven. Combining adversarial guarantees and stochastic fast rates in online learning. In Advances in Neural Information Processing Systems, pages 4457-4465, 2016.
[30] Nicole Krämer. On the peaking phenomenon of the lasso in model selection. arXiv preprint vrXiv:0904.4416, 2009.
[31] Marco Loog.
Contrastive pessimistic likelihood estimation for semi-supervised classification. IEEE transactions pattern analysis and machine intelligence, 38(3):462-47, 2015.
[32] Marco Loog and Robert P.W. Duin. The dipping phenomenon. In Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR), pages 310-317. Springer, 2012.
[33] Marco Loog, Tom Viering, and Alexander Mey. Minimizers of the empirical risk and risk monotonicity. In Advances in Neural Information Processing Systems, pages 7476-7485, 2019.
[34] Marco Loog, Tom Viering, Alexander Mey, Jesse H. Krijthe, and David M. J. Tax. A brief prehistory of double descent. Proceedings of the National Academy of Sciences, 116(5)):00225- 10626, 2020.
[35] Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penalization. arXiv preprint vrXXiv00077.744: 2009.
[36] Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample-variang penalization. In COLT 2009 The 22nd Conference on Learning Theory, Montreal, Quebec, Canada, June 18-21, 2009, 2009.
[37] Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and double descent curve. arXiv preprint arXiv:1908.05355, 2019.
[38] Zakaria Mhammedi, Peter Grünwald, and Benjamin Guedj. Pac-bayes un-expected bernstein inequality. In Advances in Neural Information Processing Systems, pages 12202-12213, 2019.
12

---

[39] Zakaria Mhammedi and Wouter M. Koolen. Lipschitz and comparator-nont norm adaptivity in online learning. In Conference on Learning Theory. COLT 2020, 9-12 July 2020, Virtual Event (Graz, Austria], volume 125 of Proceedings of Machine Learning Research, pages 2020.
PMLR,
[40] Preetum Nakkiran. More data can hurt for linear regression: Sample-wise double descent. arXiv preprint arXiv:1912.0722: 2019.
[41] Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. In International Conference on Learning Representations, 2020.
[42] Preetum Nakkiran, Prayaag Venkat, Sham Kakade, and Tengyu Ma. Optimal regularization can mitigate double descent. arXiv preprint arXiv:2003.01897 2020.
[43] Manfred Opper and Wolfgang Kinzel. Statistical mechanics of generalization. In Models of neural networks III, pages 151-209. Springer, 1996.
[44] V.H. Peña, T.L. Lai, and Q.M. Shao. Self-Normalized Processes: Limit Theory and Statistical Applications. Probability and Its Applications. Springer Berlin Heidelberg, 2008
[45] Alexander Rakhlin and Karthik Sridharan. On equivalence of martingale tail bounds and deterministic regret inequalities. In Conference on Learning Theory, pages 1704-1722. PMLR, 2017.
[46] Omar Rivasplata, Iija Kuzborskij, Csaba Szepesvári, and John Shawe-Taylor. Pac-bayes analysis beyond the usual bounds. In NeurIPS, 2020.
[47] Shai Shalev-Shward and Shai Ben-David, Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[48] Alexander Smola, Peter Bartlett, Dale Schuurmans, and Bernhard Schölkopf. Advances in large margin classifiers. MIT press, 2000.
[49] Stefano Spigler, Mario Geiger, Stéphane d' Ascoli, Levent Sagun, Giulio Biroli, and Matthieu Wyart. A jamming transition from under-to over-parandn paaa--rammtezzaioonn affects loss landscape and generalization. arXiv preprint arXiv: arXiv:/810.0000 1810.09665 2018
[50] Ilya O. Tolstikhin and Yevgeny Seldin.
sanyes-empiricalll bernstein inequality. In Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe,
Nevada, United States, pages 109-117, 2013.
[51] Paul Viallard, Pascal Germain, Amaury Habrard, and Emilie Morvant. A general framework for the disintegration of pac- bayebia bounds, 2021.
[52] Tom Viering and Marco Loog. The shape of learning curves: a review. arXiv preprint 1034922003.10948, 2021.
[53] Tom Viering, Alexander Mey, and Marco Loog. Open problem: Monotonicity of learning. In Conference on Learning Theory, pages 3198-3201, 2019.
[54] Tom J. Viering, Alexander Mey, and Marco Loog. Making learners (more) monotone, 2019,
[55] Wenda Zhou, Victor Veitch, Morgane Austern, Ryan P. Adams, and Peter Orbanz. Non-vacuous generalization bounds at the imagenet scale: pac-bayesian compression approach. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA. May 6-9, 2019, 2019.
13


Reviews:
[{"review_id": "k6qUJdZRoxA", "reviewer": "Reviewer_qjbn", "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.\n\nThe 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.\n\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": "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.\n\nComments/Questions/Typos:\n1. Typos:\n\tLine 2: populating -> population\n\tLine 175: continues -> continuous\n2. Definition 2, 'converges in probability' is not clear.\n3. Why is $\\rho$ needed for the theorem statements? Can you not replace it by a constant?\n4. 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?\n5. 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.\n6. 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors should add more discussions about the practicality of the algorithm and its limitations in practice.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "gzABbnrmN-", "reviewer": "Reviewer_mLBe", "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. \n\nIn addressing the above mentioned question, the authors make the following contributions:\n\nThe 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$.\n\nOn 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.", "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": "Clarity: The paper is clearly structured and well-written, though the authors are encouraged to carefully proof-read the manuscript to avoid some typos.\n\nQuality \\& 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.\n\nI 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? \n\nMy 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not Applicable", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "15"}, "extra_text": {}}, {"review_id": "brozjunpOtj", "reviewer": "Reviewer_kfNz", "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. ", "questions": "", "limitations": "", "rating": 9, "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": "General recommendation\n\nThis 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. \n\nSadly 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.   \n\nMost important feedback\n\n1) 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.\n\n2) 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?\n\n3) 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 ....\". \n\n4) 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. \n\n5) 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.\n\nSmall issues\n\n6) 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. \n\n7) 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? \n\n8) 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? \n\n9) 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....?\n\n10) In the related work, you could consider \nViering, Tom, and Marco Loog. \"The Shape of Learning Curves: a Review.\" arXiv preprint arXiv:2103.10948 (2021).\nas it discusses even more causes of non-monotonic learning curves besides dipping and peaking.\nFurthermore, you may be interested to know that peaking can be traced back historically already to 1989, see also\nLoog, Marco, et al. \"A brief prehistory of double descent.\" Proceedings of the National Academy of Sciences 117.20 (2020): 10625-10626.\n\n11) 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? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "not that I can see", "review_text": "", "extra_scores": {"ethical_concerns": "not that I can see", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "O9Mj8x6rJY0", "reviewer": "Reviewer_99EG", "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. \n\n", "questions": "", "limitations": "", "rating": 7, "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": "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: \n\n* 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.?\n \n* 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 ? \n\n*  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? \n\n* (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 ? \n\nThe paper is well written otherwise. I skimmed through the proofs and they seem to be correct. \nThe proof ideas in Appendix B are quite interesting! \n\nMinor comments: \n* References [22] and [23] are identical. \n* Lines 36-40 regarding discussion of connections to neural networks seem to be opposite to the empirical observations. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No social negative impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10+ hours"}, "extra_text": {}}]

Author rebuttal:

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)