  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.
