Comparing Comparators in Generalization Bounds
We derive generic information-theoretic and PAC-Bayesian generalization bounds involving an arbitrary convex comparator function, which measures the discrepancy between the training and population loss. The bounds hold under the assumption that the cumulant-generating function (CGF) of the comparator is upper-bounded by the corresponding CGF within a family of bounding distributions. We show that the tightest possible bound is obtained with the comparator being the convex conjugate of the CGF of the bounding distribution, also known as the Cram\'er function. This conclusion applies more broadly to generalization bounds with a similar structure. This confirms the near-optimality of known bounds for bounded and sub-Gaussian losses and leads to novel bounds under other bounding distributions.
Code (1)
Tasks
Generalization BoundsSimilar Papers 제목 키워드 기반
Price Stability of Cryptocurrencies as a Medium of Exchange
We present positive evidence of price stability of cryptocurrencies as a medium of exchange. For the sample years from 2016 to 2020, the prices of major cryptocurrencies are found to be stable, relative to major financia…
Dynamic Time WarpingGeneralization bounds for deep convolutional neural networks
We prove bounds on the generalization error of convolutional networks. The bounds are in terms of the training loss, the number of parameters, the Lipschitz constant of the loss and the distance from the weights to the i…
Generalization BoundsA closer look at temporal variability in dynamic online learning
This work focuses on the setting of dynamic regret in the context of online learning with full information. In particular, we analyze regret bounds with respect to the temporal variability of the loss functions. By assum…
Data Dependent Regret Guarantees Against General Comparators for Full or Bandit Feedback
We study the adversarial online learning problem and create a completely online algorithmic framework that has data dependent regret guarantees in both full expert feedback and bandit feedback settings. We study the expe…
Multi-Armed BanditsFrom Mutual Information to Expected Dynamics: New Generalization Bounds for Heavy-Tailed SGD
Understanding the generalization abilities of modern machine learning algorithms has been a major research topic over the past decades. In recent years, the learning dynamics of Stochastic Gradient Descent (SGD) have bee…
Generalization Bounds