Hoeffding's Inequality for Markov Chains under Generalized Concentrability Condition

• URL: http://arxiv.org/abs/2310.02941v1
• Date: Wed, 4 Oct 2023 16:21:23 GMT
• Title: Hoeffding's Inequality for Markov Chains under Generalized Concentrability Condition
• Authors: Hao Chen, Abhishek Gupta, Yin Sun, and Ness Shroff
• Abstract summary: This paper studies Hoeffding's inequality for Markov chains under the generalized concentrability condition defined via integral probability metric (IPM) The flexibility of our framework allows Hoeffding's inequality to be applied beyond the ergodic Markov chains in the traditional sense.
• Score: 15.228649445346473
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper studies Hoeffding's inequality for Markov chains under the generalized concentrability condition defined via integral probability metric (IPM). The generalized concentrability condition establishes a framework that interpolates and extends the existing hypotheses of Markov chain Hoeffding-type inequalities. The flexibility of our framework allows Hoeffding's inequality to be applied beyond the ergodic Markov chains in the traditional sense. We demonstrate the utility by applying our framework to several non-asymptotic analyses arising from the field of machine learning, including (i) a generalization bound for empirical risk minimization with Markovian samples, (ii) a finite sample guarantee for Ployak-Ruppert averaging of SGD, and (iii) a new regret bound for rested Markovian bandits with general state space.

Related papers

• Stochastic Gradient Descent under Markovian Sampling Schemes [3.04585143845864]
  We study a variation of vanilla gradient descent where the only has access to a Markovian sampling scheme. We focus on obtaining rates of convergence under the least restrictive assumptions possible on the underlying Markov chain.
  arXiv  Detail & Related papers  (2023-02-28T09:18:00Z)
• Offline Estimation of Controlled Markov Chains: Minimaxity and Sample Complexity [8.732260277121547]
  We develop sample complexity bounds for the estimator and establish conditions for minimaxity. We show that achieving a particular statistical risk bound involves a subtle and interesting trade-off between the strength of the mixing properties and the number of samples.
  arXiv  Detail & Related papers  (2022-11-14T03:39:59Z)
• Stability and Generalization for Markov Chain Stochastic Gradient Methods [49.981789906200035]
  We provide a comprehensive generalization analysis of MC-SGMs for both minimization and minimax problems. We establish the optimal excess population risk bounds for both smooth and non-smooth cases. We develop the first nearly optimal convergence rates for convex-concave problems both in expectation and with high probability.
  arXiv  Detail & Related papers  (2022-09-16T15:42:51Z)
• On the Equity of Nuclear Norm Maximization in Unsupervised Domain Adaptation [53.29437277730871]
  Nuclear norm has shown the power to enhance the transferability of unsupervised domain adaptation model. Two new losses are proposed to maximize both predictive discriminability and equity, from the class level and the sample level.
  arXiv  Detail & Related papers  (2022-04-12T07:55:47Z)
• Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
  We study the problem of estimating the fixed point of a contractive operator defined on a separable Banach space. We establish non-asymptotic bounds for both the operator defect and the estimation error.
  arXiv  Detail & Related papers  (2022-01-21T02:46:57Z)
• 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)
• Comparison of Markov chains via weak Poincar\'e inequalities with application to pseudo-marginal MCMC [0.0]
  We investigate the use of a certain class of functional inequalities known as weak Poincar'e inequalities to bound convergence of Markov chains to equilibrium. We show that this enables the derivation of subgeometric convergence bounds for methods such as the Independent Metropolis--Hastings sampler and pseudo-marginal methods for intractable likelihoods.
  arXiv  Detail & Related papers  (2021-12-10T15:36:30Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  We introduce the expected co-coercivity condition, explain its benefits, and provide the first last-iterate convergence guarantees of SGDA and SCO. We prove linear convergence of both methods to a neighborhood of the solution when they use constant step-size. Our convergence guarantees hold under the arbitrary sampling paradigm, and we give insights into the complexity of minibatching.
  arXiv  Detail & Related papers  (2021-06-30T18:32:46Z)
• Three rates of convergence or separation via U-statistics in a dependent framework [5.929956715430167]
  We put this theoretical breakthrough into action by pushing further the current state of knowledge in three different active fields of research. First, we establish a new exponential inequality for the estimation of spectra of trace class integral operators with MCMC methods. In addition, we investigate generalization performance of online algorithms working with pairwise loss functions and Markov chain samples.
  arXiv  Detail & Related papers  (2021-06-24T07:10:36Z)
• A Unified Joint Maximum Mean Discrepancy for Domain Adaptation [73.44809425486767]
  This paper theoretically derives a unified form of JMMD that is easy to optimize. From the revealed unified JMMD, we illustrate that JMMD degrades the feature-label dependence that benefits to classification. We propose a novel MMD matrix to promote the dependence, and devise a novel label kernel that is robust to label distribution shift.
  arXiv  Detail & Related papers  (2021-01-25T09:46:14Z)
• GenDICE: Generalized Offline Estimation of Stationary Values [108.17309783125398]
  We show that effective estimation can still be achieved in important applications. Our approach is based on estimating a ratio that corrects for the discrepancy between the stationary and empirical distributions. The resulting algorithm, GenDICE, is straightforward and effective.
  arXiv  Detail & Related papers  (2020-02-21T00:27:52Z)

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.