Risk-Monotonicity in Statistical Learning

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.

arXiv commentTo appear in NeurIPS 2021 as Oral presentation

References in corpus (15)

• The generalization error of random features regression: Precise asymptotics and double descent curve
• Empirical Bernstein Bounds and Sample Variance Penalization
• Time-uniform Chernoff bounds via nonnegative supermartingales
• A Primer on PAC-Bayesian Learning
• Optimal Regularization Can Mitigate Double Descent
• More Data Can Hurt for Linear Regression: Sample-wise Double Descent
• Multiple Descent: Design Your Own Generalization Curve
• Minimizing The Misclassification Error Rate Using a Surrogate Convex Loss
• Triple descent and the two kinds of overfitting: Where & why do they appear?
• Combining Adversarial Guarantees and Stochastic Fast Rates in Online Learning
• On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities
• Parameter-Free Online Convex Optimization with Sub-Exponential Noise
• Lipschitz and Comparator-Norm Adaptivity in Online Learning
• On the Peaking Phenomenon of the Lasso in Model Selection
• Non-exponentially weighted aggregation: regret bounds for unbounded loss functions