More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity

• URL: http://arxiv.org/abs/2306.12214v4
• Date: Tue, 4 Jun 2024 14:09:44 GMT
• Title: More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity
• Authors: Borja Rodríguez-Gálvez, Ragnar Thobaben, Mikael Skoglund,
• Abstract summary: We present new high-probability PAC-Bayes bounds for different types of losses. For losses with a bounded range, we recover a strengthened version of Catoni's bound that holds uniformly for all parameter values. For losses with more general tail behaviors, we introduce two new parameter-free bounds.
• Score: 27.87324770020133
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we present new high-probability PAC-Bayes bounds for different types of losses. Firstly, for losses with a bounded range, we recover a strengthened version of Catoni's bound that holds uniformly for all parameter values. This leads to new fast-rate and mixed-rate bounds that are interpretable and tighter than previous bounds in the literature. In particular, the fast-rate bound is equivalent to the Seeger--Langford bound. Secondly, for losses with more general tail behaviors, we introduce two new parameter-free bounds: a PAC-Bayes Chernoff analogue when the loss' cumulative generating function is bounded, and a bound when the loss' second moment is bounded. These two bounds are obtained using a new technique based on a discretization of the space of possible events for the ``in probability'' parameter optimization problem. This technique is both simpler and more general than previous approaches optimizing over a grid on the parameters' space. Finally, using a simple technique that is applicable to any existing bound, we extend all previous results to anytime-valid bounds.

Related papers

• A note on generalization bounds for losses with finite moments [28.102352176005514]
  The paper derives a high-probability PAC-Bayes bound for losses with a bounded variance. It extends results to guarantees in expectation and single-draw PAC-Bayes.
  arXiv  Detail & Related papers  (2024-03-25T12:15:55Z)
• PAC-Bayes-Chernoff bounds for unbounded losses [9.987130158432755]
  We introduce a new PAC-Bayes oracle bound for unbounded losses that extends Cram'er-Chernoff bounds to the PAC-Bayesian setting. Our approach naturally leverages properties of Cram'er-Chernoff bounds, such as exact optimization of the free parameter in many PAC-Bayes bounds.
  arXiv  Detail & Related papers  (2024-01-02T10:58:54Z)
• Closing the Gap Between the Upper Bound and the Lower Bound of Adam's Iteration Complexity [51.96093077151991]
  We derive a new convergence guarantee of Adam, with only an $L$-smooth condition and a bounded noise variance assumption. Our proof utilizes novel techniques to handle the entanglement between momentum and adaptive learning rate.
  arXiv  Detail & Related papers  (2023-10-27T09:16:58Z)
• Exactly Tight Information-Theoretic Generalization Error Bound for the Quadratic Gaussian Problem [16.04977600068383]
  We provide a new information-theoretic generalization error bound that is exactly tight (i.e., matching even the constant) Most existing bounds are order-wise loose in this setting. A refined bound is then proposed for decomposable loss functions, leading to a tight bound for the vector setting.
  arXiv  Detail & Related papers  (2023-05-01T15:22:58Z)
• STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
  We investigate non-batch optimization problems where the objective is an expectation over smooth loss functions. Our work builds on the STORM algorithm, in conjunction with a novel approach to adaptively set the learning rate and momentum parameters.
  arXiv  Detail & Related papers  (2021-11-01T15:43:36Z)
• Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizers [31.102181563065844]
  Quantile (and, more generally, KL) regret bounds relax the goal of competing against the best individual expert to only competing against a majority of experts on adversarial data. More recently, the semi-adversarial paradigm (Bilodeau, Negrea, and Roy 2020) provides an alternative relaxation of adversarial online learning by considering data that may be neither fully adversarial nor adversarial. We achieve the minimax optimal regret in both paradigms using FTRL with separate, novel, root-logarithmic regularizers, both of which can be interpreted as yielding variants of NormalHedge.
  arXiv  Detail & Related papers  (2021-10-27T22:38:52Z)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  We consider non- Hilbert optimization using first-order algorithms for which the gradient estimates may have tails. We show that a combination of gradient, momentum, and normalized gradient descent convergence to critical points in high-probability with best-known iteration for smooth losses.
  arXiv  Detail & Related papers  (2021-06-28T00:17:01Z)
• Universal Online Convex Optimization Meets Second-order Bounds [74.0120666722487]
  We propose a simple strategy for universal online convex optimization. The key idea is to construct a set of experts to process the original online functions, and deploy a meta-algorithm over the linearized losses. In this way, we can plug in off-the-shelf online solvers as black-box experts to deliver problem-dependent regret bounds.
  arXiv  Detail & Related papers  (2021-05-08T11:43:49Z)
• Tighter expected generalization error bounds via Wasserstein distance [23.52237892358981]
  We introduce several expected generalization error bounds based on the Wasserstein distance. We present full-dataset, single-letter, and random-subset bounds on both the standard setting and the randomized-subsample setting. We show how various new bounds based on different information measures can be derived from the presented bounds.
  arXiv  Detail & Related papers  (2021-01-22T20:13:59Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  We consider algorithm-independent lower bounds for the problem of black-box optimization of functions having a bounded norm. We provide a novel proof technique for deriving lower bounds on the regret, with benefits including simplicity, versatility, and an improved dependence on the error probability.
  arXiv  Detail & Related papers  (2020-08-20T03:48:14Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  A fundamental component of neural network verification is the computation of bounds on the values their outputs can take. We propose a novel approach based on Lagrangian Decomposition. We show that we obtain bounds comparable with off-the-shelf solvers in a fraction of their running time.
  arXiv  Detail & Related papers  (2020-02-24T17:55:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.