Online Learning Algorithms in Hilbert Spaces with $β-$ and $φ-$Mixing Sequences

• URL: http://arxiv.org/abs/2502.03551v1
• Date: Wed, 05 Feb 2025 19:09:07 GMT
• Title: Online Learning Algorithms in Hilbert Spaces with $β-$ and $φ-$Mixing Sequences
• Authors: Priyanka Roy, Susanne Saminger-Platz,
• Abstract summary: We study an online algorithm in a reproducing kernel Hilbert spaces based on a class of dependent processes, called the mixing process. We analyze a strictly stationary Markov chain, where the dependence structure is characterized by the (beta-) and (phi-)mixing coefficients. Our findings extend existing error bounds for i.i.d. observations, demonstrating that the i.i.d. case is a special instance of our framework.
• Score: 1.1510009152620668
• License:
• Abstract: In this paper, we study an online algorithm in a reproducing kernel Hilbert spaces (RKHS) based on a class of dependent processes, called the mixing process. For such a process, the degree of dependence is measured by various mixing coefficients. As a representative example, we analyze a strictly stationary Markov chain, where the dependence structure is characterized by the \(\beta-\) and \(\phi-\)mixing coefficients. For these dependent samples, we derive nearly optimal convergence rates. Our findings extend existing error bounds for i.i.d. observations, demonstrating that the i.i.d. case is a special instance of our framework. Moreover, we explicitly account for an additional factor introduced by the dependence structure in the Markov chain.

Related papers

• 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)
• Covariance estimation using Markov chain Monte Carlo [2.209921757303168]
  We show that when $pi$ satisfies a Poincar'e inequality and the chain possesses a spectral gap, we can achieve similar sample complexity using MCMC. We provide guarantees regarding isotropic rounding procedures for sampling uniformly on convex bodies.
  arXiv  Detail & Related papers  (2024-10-22T16:27:29Z)
• Logistic-beta processes for dependent random probabilities with beta marginals [58.91121576998588]
  We propose a novel process called the logistic-beta process, whose logistic transformation yields a process with common beta marginals. It can model dependence on both discrete and continuous domains, such as space or time, and has a flexible dependence structure through correlation kernels. We illustrate the benefits through nonparametric binary regression and conditional density estimation examples, both in simulation studies and in a pregnancy outcome application.
  arXiv  Detail & Related papers  (2024-02-10T21:41:32Z)
• Ito Diffusion Approximation of Universal Ito Chains for Sampling, Optimization and Boosting [64.0722630873758]
  We consider rather general and broad class of Markov chains, Ito chains, that look like Euler-Maryama discretization of some Differential Equation. We prove the bound in $W_2$-distance between the laws of our Ito chain and differential equation.
  arXiv  Detail & Related papers  (2023-10-09T18:38:56Z)
• Rosenthal-type inequalities for linear statistics of Markov chains [20.606986885851573]
  We establish novel deviation bounds for additive functionals of geometrically ergodic Markov chains. We pay special attention to the dependence of our bounds on the mixing time of the corresponding chain.
  arXiv  Detail & Related papers  (2023-03-10T10:24:46Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• Deterministic Gibbs Sampling via Ordinary Differential Equations [77.42706423573573]
  This paper presents a general construction of deterministic measure-preserving dynamics using autonomous ODEs and tools from differential geometry. We show how Hybrid Monte Carlo and other deterministic samplers follow as special cases of our theory.
  arXiv  Detail & Related papers  (2021-06-18T15:36:09Z)
• Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC [83.48593305367523]
  Hybrid Monte Carlo is a powerful Markov Chain Monte Carlo method for sampling from complex continuous distributions. We introduce a new approach based on augmenting Monte Carlo methods with SurVAE Flows to sample from discrete distributions. We demonstrate the efficacy of our algorithm on a range of examples from statistics, computational physics and machine learning, and observe improvements compared to alternative algorithms.
  arXiv  Detail & Related papers  (2021-02-04T02:21:08Z)
• Kernel Autocovariance Operators of Stationary Processes: Estimation and Convergence [0.5505634045241288]
  We consider autocovariance operators of a stationary process on a Polish space embedded into a kernel reproducing Hilbert space. We investigate how empirical estimates of these operators converge along realizations of the process under various conditions. We provide applications of our theory in terms of consistency results for kernel PCA with dependent data and the conditional mean embedding of transition probabilities.
  arXiv  Detail & Related papers  (2020-04-02T09:17:32Z)
• Convergence of Recursive Stochastic Algorithms using Wasserstein Divergence [4.688616907736838]
  We show that convergence of a large family of constant stepsize RSAs can be understood using this framework. We show that convergence of a large family of constant stepsize RSAs can be understood using this framework.
  arXiv  Detail & Related papers  (2020-03-25T13:45:16Z)
• Distributed Learning with Dependent Samples [17.075804626858748]
  We derive optimal learning rate for distributed kernel ridge regression for strong mixing sequences. Our results extend the applicable range of distributed learning from i.i.d. samples to non-i.i.d. sequences.
  arXiv  Detail & Related papers  (2020-02-10T14:03:45Z)

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.