Information-Theoretic Generalization Bounds for Transductive Learning and its Applications

• URL: http://arxiv.org/abs/2311.04561v3
• Date: Tue, 21 Jan 2025 02:18:46 GMT
• Title: Information-Theoretic Generalization Bounds for Transductive Learning and its Applications
• Authors: Huayi Tang, Yong Liu,
• Abstract summary: We establish generalization bounds for transductive learning algorithms in the context of information theory and PAC-Bayes. First, we show that the transductive generalization gap can be controlled by the mutual information between training label selection and the hypothesis. We further establish transductive PAC-Bayesian bounds with weaker assumptions on the type of loss function and the number of training and test data points.
• Score: 16.408850979966623
• License:
• Abstract: In this paper, we establish generalization bounds for transductive learning algorithms in the context of information theory and PAC-Bayes, covering both the random sampling and the random splitting setting. First, we show that the transductive generalization gap can be controlled by the mutual information between training label selection and the hypothesis. Next, we propose the concept of transductive supersample and use it to derive transductive information-theoretic bounds involving conditional mutual information and different information measures. We further establish transductive PAC-Bayesian bounds with weaker assumptions on the type of loss function and the number of training and test data points. Lastly, we use the theoretical results to derive upper bounds for adaptive optimization algorithms under the transductive learning setting. We also apply them to semi-supervised learning and transductive graph learning scenarios, meanwhile validating the derived bounds by experiments on synthetic and real-world datasets.

Related papers

• A Smooth Transition Between Induction and Deduction: Fast Abductive Learning Based on Probabilistic Symbol Perception [81.30687085692576]
  We introduce an optimization algorithm named as Probabilistic Symbol Perception (PSP), which makes a smooth transition between induction and deduction. Experiments demonstrate the promising results.
  arXiv  Detail & Related papers  (2025-02-18T14:59:54Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  In this paper, we propose a distributed sampling scheme based on the alternating direction method of multipliers. We provide both theoretical guarantees of our algorithm's convergence and experimental evidence of its superiority to the state-of-the-art. In simulation, we deploy our algorithm on linear and logistic regression tasks and illustrate its fast convergence compared to existing gradient-based methods.
  arXiv  Detail & Related papers  (2024-01-29T02:08:40Z)
• Disentangled Representation Learning with Transmitted Information Bottleneck [57.22757813140418]
  We present textbfDisTIB (textbfTransmitted textbfInformation textbfBottleneck for textbfDisd representation learning), a novel objective that navigates the balance between information compression and preservation.
  arXiv  Detail & Related papers  (2023-11-03T03:18:40Z)
• Hypothesis Transfer Learning with Surrogate Classification Losses: Generalization Bounds through Algorithmic Stability [3.908842679355255]
  Hypothesis transfer learning (HTL) contrasts domain adaptation by allowing for a previous task leverage, named the source, into a new one, the target. This paper studies the learning theory of HTL through algorithmic stability, an attractive theoretical framework for machine learning algorithms analysis.
  arXiv  Detail & Related papers  (2023-05-31T09:38:21Z)
• Information Theoretic Lower Bounds for Information Theoretic Upper Bounds [14.268363583731848]
  We examine the relationship between the output model and the empirical generalization and the algorithm in the context of convex optimization. Our study reveals that, for true risk minimization, mutual information is necessary. Existing information-theoretic generalization bounds fall short in capturing the capabilities of algorithms like SGD and regularized, which have-independent dimension sample complexity.
  arXiv  Detail & Related papers  (2023-02-09T20:42:36Z)
• 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)
• Label Propagation Through Optimal Transport [0.0]
  We tackle the transductive semi-supervised learning problem that aims to obtain label predictions for the given unlabeled data points. Our proposed approach is based on optimal transport, a mathematical theory that has been successfully used to address various machine learning problems.
  arXiv  Detail & Related papers  (2021-10-01T11:25:55Z)
• A Scaling Law for Synthetic-to-Real Transfer: A Measure of Pre-Training [52.93808218720784]
  Synthetic-to-real transfer learning is a framework in which we pre-train models with synthetically generated images and ground-truth annotations for real tasks. Although synthetic images overcome the data scarcity issue, it remains unclear how the fine-tuning performance scales with pre-trained models. We observe a simple and general scaling law that consistently describes learning curves in various tasks, models, and complexities of synthesized pre-training data.
  arXiv  Detail & Related papers  (2021-08-25T02:29:28Z)
• InteL-VAEs: Adding Inductive Biases to Variational Auto-Encoders via Intermediary Latents [60.785317191131284]
  We introduce a simple and effective method for learning VAEs with controllable biases by using an intermediary set of latent variables. In particular, it allows us to impose desired properties like sparsity or clustering on learned representations. We show that this, in turn, allows InteL-VAEs to learn both better generative models and representations.
  arXiv  Detail & Related papers  (2021-06-25T16:34:05Z)
• Perturbation Theory for the Information Bottleneck [6.117084972237769]
  Information bottleneck (IB) method formalizes extracting relevant information from data. nonlinearity of the IB problem makes it computationally expensive and analytically intractable in general. We derive a perturbation theory for the IB method and report the first complete characterization of the learning onset.
  arXiv  Detail & Related papers  (2021-05-28T16:59:01Z)
• Information Complexity and Generalization Bounds [0.0]
  We show a unifying picture of PAC-Bayesian and mutual information-based upper bounds on randomized learning algorithms. We discuss two practical examples for learning with neural networks, namely, Entropy- and PAC-Bayes- SGD.
  arXiv  Detail & Related papers  (2021-05-04T20:37:57Z)

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.