Generalization Error Bounds on Deep Learning with Markov Datasets

• URL: http://arxiv.org/abs/2201.11059v1
• Date: Thu, 23 Dec 2021 11:14:43 GMT
• Title: Generalization Error Bounds on Deep Learning with Markov Datasets
• Abstract summary: We derive upper bounds on generalization errors for deep neural networks with Markov datasets. New symmetrization inequalities in high-dimensional probability for Markov chains is a key element in our extension.
• Score: 16.3460693863947
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we derive upper bounds on generalization errors for deep neural networks with Markov datasets. These bounds are developed based on Koltchinskii and Panchenko's approach for bounding the generalization error of combined classifiers with i.i.d. datasets. The development of new symmetrization inequalities in high-dimensional probability for Markov chains is a key element in our extension, where the pseudo-spectral gap of the infinitesimal generator of the Markov chain plays as a key parameter in these inequalities. We also propose a simple method to convert these bounds and other similar bounds on traditional deep learning and machine learning to Bayesian counterparts for both i.i.d. and Markov datasets.

Related papers

• Neural Autoregressive Flows for Markov Boundary Learning [12.567367940875073]
  This paper investigates a framework for efficient boundary discovery by integrating conditional entropy from information theory as a scoring criterion.<n>A parallelizable greedy search strategy in time is proposed, supported by analytical evidence.<n> Comprehensive evaluations on real-world and synthetic datasets demonstrate the scalability and superior performance of our method in both boundary discovery and causal discovery tasks.
  arXiv  Detail & Related papers  (2026-03-21T12:31:21Z)
• Additive Multi-Step Markov Chains and the Curse of Dimensionality in Large Language Models [0.0]
  We explore a theoretically feasible approximation of dynamics using N-order additive Markov chains.<n>The main result of the work is the establishment of a correspondence between an additive multi-step chain and a chain with a step-wise memory function.
  arXiv  Detail & Related papers  (2026-02-03T16:38:26Z)
• Attention (as Discrete-Time Markov) Chains [76.61244121046035]
  We introduce a new interpretation of the attention matrix as a discrete-time Markov chain.<n>Key observation is that tokens linked to semantically similar regions form metastable states, i.e., regions where attention tends to concentrate, while noisy attention scores dissipate.<n>Finally, we define TokenRank -- the steady state vector of the Markov chain, which measures global token importance.
  arXiv  Detail & Related papers  (2025-07-23T16:20:47Z)
• Unbiased Max-Min Embedding Classification for Transductive Few-Shot Learning: Clustering and Classification Are All You Need [83.10178754323955]
  Few-shot learning enables models to generalize from only a few labeled examples. We propose the Unbiased Max-Min Embedding Classification (UMMEC) Method, which addresses the key challenges in few-shot learning. Our method significantly improves classification performance with minimal labeled data, advancing the state-of-the-art in annotatedL.
  arXiv  Detail & Related papers  (2025-03-28T07:23:07Z)
• Generalization Bounds for Equivariant Networks on Markov Data [18.548000339222234]
  We introduce a new McDiarmid's inequality to derive a generalization bound for neural networks trained on Markov datasets. This bound provides practical insights into selecting low-dimensional irreducible representations, enhancing generalization performance for fixed-width equivariant neural networks.
  arXiv  Detail & Related papers  (2025-03-01T01:53:48Z)
• Uncertainty quantification for Markov chains with application to temporal difference learning [63.49764856675643]
  We develop novel high-dimensional concentration inequalities and Berry-Esseen bounds for vector- and matrix-valued functions of Markov chains. We analyze the TD learning algorithm, a widely used method for policy evaluation in reinforcement learning.
  arXiv  Detail & Related papers  (2025-02-19T15:33:55Z)
• Doubly Stochastic Adaptive Neighbors Clustering via the Marcus Mapping [56.57574396804837]
  Clustering is a fundamental task in machine learning and data science, and similarity graph-based clustering is an important approach within this domain. We study the relationship between the Marcus mapping and optimal transport. We prove that the Marcus mapping solves a specific type of optimal transport problem and demonstrate that solving this problem through Marcus mapping is more efficient than directly applying optimal transport methods.
  arXiv  Detail & Related papers  (2024-08-06T03:34:43Z)
• Disentangled Representation Learning with the Gromov-Monge Gap [65.73194652234848]
  Learning disentangled representations from unlabelled data is a fundamental challenge in machine learning. We introduce a novel approach to disentangled representation learning based on quadratic optimal transport. We demonstrate the effectiveness of our approach for quantifying disentanglement across four standard benchmarks.
  arXiv  Detail & Related papers  (2024-07-10T16:51:32Z)
• A Probabilistic Semi-Supervised Approach with Triplet Markov Chains [1.000779758350696]
  Triplet Markov chains are general generative models for sequential data. We propose a general framework based on a variational Bayesian inference to train parameterized triplet Markov chain models.
  arXiv  Detail & Related papers  (2023-09-07T13:34:20Z)
• Semi-Supervised Laplace Learning on Stiefel Manifolds [48.3427853588646]
  We develop the framework Sequential Subspace for graph-based, supervised samples at low-label rates. We achieves that our methods at extremely low rates, and high label rates.
  arXiv  Detail & Related papers  (2023-07-31T20:19:36Z)
• Covariate shift in nonparametric regression with Markovian design [0.0]
  We show that convergence rates for a smoothness risk of a Nadaraya-Watson kernel estimator are determined by the similarity between the invariant distributions associated to source and target Markov chains. We extend the notion of a distribution exponent from Kpotufe and Martinet to kernel transfer exponents of uniformly ergodic Markov chains.
  arXiv  Detail & Related papers  (2023-07-17T14:24:27Z)
• Generalized Precision Matrix for Scalable Estimation of Nonparametric Markov Networks [11.77890309304632]
  A Markov network characterizes the conditional independence structure, or Markov property, among a set of random variables. In this work, we characterize the conditional independence structure in general distributions for all data types. We also allow general functional relations among variables, thus giving rise to a Markov network structure learning algorithm.
  arXiv  Detail & Related papers  (2023-05-19T01:53:10Z)
• Discriminative Entropy Clustering and its Relation to K-means and SVM [9.394359851234201]
  Maximization of mutual information between the model's input and output is formally related to "decisiveness" and "fairness" of the softmax predictions. We propose a new self-labeling formulation of entropy clustering for general softmax models. Our algorithm improves the state of the art on several standard benchmarks for deep clustering.
  arXiv  Detail & Related papers  (2023-01-26T20:35:30Z)
• Detection and Evaluation of Clusters within Sequential Data [58.720142291102135]
  Clustering algorithms for Block Markov Chains possess theoretical optimality guarantees. In particular, our sequential data is derived from human DNA, written text, animal movement data and financial markets. It is found that the Block Markov Chain model assumption can indeed produce meaningful insights in exploratory data analyses.
  arXiv  Detail & Related papers  (2022-10-04T15:22:39Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  We propose a novel semi-supervised subspace clustering method, which is able to simultaneously augment the initial supervisory information and construct a discriminative affinity matrix. Comprehensive experimental results on six commonly-used benchmark datasets demonstrate the superiority of our method over state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-05-21T01:47:17Z)
• Semi-Supervised Clustering via Markov Chain Aggregation [9.475039534437332]
  We introduce Constrained Markov Clustering (CoMaC) for semi-supervised clustering. Our results indicate that CoMaC is competitive with the state-of-the-art.
  arXiv  Detail & Related papers  (2021-12-17T09:07:43Z)
• Learning Gaussian Mixtures with Generalised Linear Models: Precise Asymptotics in High-dimensions [79.35722941720734]
  Generalised linear models for multi-class classification problems are one of the fundamental building blocks of modern machine learning tasks. We prove exacts characterising the estimator in high-dimensions via empirical risk minimisation. We discuss how our theory can be applied beyond the scope of synthetic data.
  arXiv  Detail & Related papers  (2021-06-07T16:53:56Z)

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.