Multi-View Majority Vote Learning Algorithms: Direct Minimization of PAC-Bayesian Bounds

• URL: http://arxiv.org/abs/2411.06276v1
• Date: Sat, 09 Nov 2024 20:25:47 GMT
• Title: Multi-View Majority Vote Learning Algorithms: Direct Minimization of PAC-Bayesian Bounds
• Authors: Mehdi Hennequin, Abdelkrim Zitouni, Khalid Benabdeslem, Haytham Elghazel, Yacine Gaci,
• Abstract summary: We extend PAC-Bayesian theory to introduce novel PAC-Bayesian bounds based on R'enyi divergence. These bounds improve upon traditional Kullback-Leibler divergence and offer more refined complexity measures. We also propose first and second-order oracle PAC-Bayesian bounds, along with an extension of the C-bound for multi-view learning.
• Score: 0.8039067099377079
• License:
• Abstract: The PAC-Bayesian framework has significantly advanced our understanding of statistical learning, particularly in majority voting methods. However, its application to multi-view learning remains underexplored. In this paper, we extend PAC-Bayesian theory to the multi-view setting, introducing novel PAC-Bayesian bounds based on R\'enyi divergence. These bounds improve upon traditional Kullback-Leibler divergence and offer more refined complexity measures. We further propose first and second-order oracle PAC-Bayesian bounds, along with an extension of the C-bound for multi-view learning. To ensure practical applicability, we develop efficient optimization algorithms with self-bounding properties.

Related papers

• Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learning [50.92957910121088]
  This work designs and analyzes a novel set of algorithms for multi-agent reinforcement learning (MARL) based on the principle of information-directed sampling (IDS) For episodic two-player zero-sum MGs, we present three sample-efficient algorithms for learning Nash equilibrium. We extend Reg-MAIDS to multi-player general-sum MGs and prove that it can learn either the Nash equilibrium or coarse correlated equilibrium in a sample efficient manner.
  arXiv  Detail & Related papers  (2024-04-30T06:48:56Z)
• Learning-to-Optimize with PAC-Bayesian Guarantees: Theoretical Considerations and Practical Implementation [4.239829789304117]
  We use the PAC-Bayesian theory for the setting of learning-to-optimize. We present the first framework to learn optimization algorithms with provable generalization guarantees. Our learned algorithms provably outperform related ones derived from a (deterministic) worst-case analysis.
  arXiv  Detail & Related papers  (2024-04-04T08:24:57Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  The sequential decision-making problem is statistically learnable if it admits a low-rank structure modeled by predictive state representations (PSRs) This paper proposes the first known UCB-type approach for PSRs, featuring a novel bonus term that upper bounds the total variation distance between the estimated and true models. In contrast to existing approaches for PSRs, our UCB-type algorithms enjoy computational tractability, last-iterate guaranteed near-optimal policy, and guaranteed model accuracy.
  arXiv  Detail & Related papers  (2023-07-01T18:35:21Z)
• Federated Compositional Deep AUC Maximization [58.25078060952361]
  We develop a novel federated learning method for imbalanced data by directly optimizing the area under curve (AUC) score. To the best of our knowledge, this is the first work to achieve such favorable theoretical results.
  arXiv  Detail & Related papers  (2023-04-20T05:49:41Z)
• Scalable PAC-Bayesian Meta-Learning via the PAC-Optimal Hyper-Posterior: From Theory to Practice [54.03076395748459]
  A central question in the meta-learning literature is how to regularize to ensure generalization to unseen tasks. We present a generalization bound for meta-learning, which was first derived by Rothfuss et al. We provide a theoretical analysis and empirical case study under which conditions and to what extent these guarantees for meta-learning improve upon PAC-Bayesian per-task learning bounds.
  arXiv  Detail & Related papers  (2022-11-14T08:51:04Z)
• PAC-Bayesian Learning of Optimization Algorithms [6.624726878647541]
  We apply the PAC-Bayes theory to the setting of learning-to-optimize. We learn optimization algorithms with provable generalization guarantees (PAC-bounds) and explicit trade-off between a high probability of convergence and a high convergence speed. Our results rely on PAC-Bayes bounds for general, unbounded loss-functions based on exponential families.
  arXiv  Detail & Related papers  (2022-10-20T09:16:36Z)
• PAC-Bayesian Domain Adaptation Bounds for Multiclass Learners [13.33450619901885]
  We propose the first PAC-Bayesian adaptation bounds for multiclass learners. For divergences dependent on a Gibbs predictor, we propose additional PAC-Bayesian adaptation bounds. We apply our bounds to analyze a common adaptation algorithm that uses neural networks.
  arXiv  Detail & Related papers  (2022-07-12T17:07:59Z)
• Embed to Control Partially Observed Systems: Representation Learning with Provable Sample Efficiency [105.17746223041954]
  Reinforcement learning in partially observed Markov decision processes (POMDPs) faces two challenges. It often takes the full history to predict the future, which induces a sample complexity that scales exponentially with the horizon. We propose a reinforcement learning algorithm named Embed to Control (ETC), which learns the representation at two levels while optimizing the policy.
  arXiv  Detail & Related papers  (2022-05-26T16:34:46Z)
• Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximation [92.3161051419884]
  We study reinforcement learning with linear function approximation. Existing algorithms only have high-probability regret and/or Probably Approximately Correct (PAC) sample complexity guarantees. We propose a new algorithm called FLUTE, which enjoys uniform-PAC convergence to the optimal policy with high probability.
  arXiv  Detail & Related papers  (2021-06-22T08:48:56Z)
• Self-Bounding Majority Vote Learning Algorithms by the Direct Minimization of a Tight PAC-Bayesian C-Bound [0.0]
  We derive self-bounding majority vote learning algorithms based on PAC-Bayesian guarantees on the C-Bound. Our algorithms are scalable and lead to accurate predictors paired with non-vacuous guarantees.
  arXiv  Detail & Related papers  (2021-04-28T08:23:18Z)
• A General Framework for the Practical Disintegration of PAC-Bayesian Bounds [2.516393111664279]
  We introduce new PAC-Bayesian generalization bounds that have the originality to provide disintegrated bounds. Our bounds are easily optimizable and can be used to design learning algorithms.
  arXiv  Detail & Related papers  (2021-02-17T09:36:46Z)

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.