Concentration Phenomenon for Random Dynamical Systems: An Operator Theoretic Approach

• URL: http://arxiv.org/abs/2212.03670v2
• Date: Tue, 30 May 2023 21:20:33 GMT
• Title: Concentration Phenomenon for Random Dynamical Systems: An Operator Theoretic Approach
• Authors: Muhammad Abdullah Naeem and Miroslav Pajic
• Abstract summary: This paper formalizes the concentration phenomenon for a given observable. It turns out that even if the observable/ reward function is unbounded, but for some. for some $q>2$, $|er|_q. The role of emphreversibility in concentration phenomenon is demystified.
• Score: 10.051309746913512
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Via operator theoretic methods, we formalize the concentration phenomenon for a given observable `$r$' of a discrete time Markov chain with `$\mu_{\pi}$' as invariant ergodic measure, possibly having support on an unbounded state space. The main contribution of this paper is circumventing tedious probabilistic methods with a study of a composition of the Markov transition operator $P$ followed by a multiplication operator defined by $e^{r}$. It turns out that even if the observable/ reward function is unbounded, but for some for some $q>2$, $\|e^{r}\|_{q \rightarrow 2} \propto \exp\big(\mu_{\pi}(r) +\frac{2q}{q-2}\big) $ and $P$ is hyperbounded with norm control $\|P\|_{2 \rightarrow q }< e^{\frac{1}{2}[\frac{1}{2}-\frac{1}{q}]}$, sharp non-asymptotic concentration bounds follow. \emph{Transport-entropy} inequality ensures the aforementioned upper bound on multiplication operator for all $q>2$. The role of \emph{reversibility} in concentration phenomenon is demystified. These results are particularly useful for the reinforcement learning and controls communities as they allow for concentration inequalities w.r.t standard unbounded obersvables/reward functions where exact knowledge of the system is not available, let alone the reversibility of stationary measure.

Related papers

• Isochronous oscillator with a singular position-dependent mass and its quantization [6.412262542272846]
  We present an analysis of the equation $ddotx - (1/2x) dotx2 + 2 omega2 x - 1/8x = 0$, where $omega > 0$ and $x = x(t)$ is a real-valued variable. The dynamics is exactly solvable for both the branches and so for definiteness, we stick to the $x > 0$ branch.
  arXiv  Detail & Related papers  (2025-01-14T20:33:16Z)
• Tensor network approximation of Koopman operators [0.0]
  We propose a framework for approximating the evolution of observables of measure-preserving ergodic systems. Our approach is based on a spectrally-convergent approximation of the skew-adjoint Koopman generator. A key feature of this quantum-inspired approximation is that it captures information from a tensor product space of dimension $(2d+1)n$.
  arXiv  Detail & Related papers  (2024-07-09T21:40:14Z)
• The Dirac Delta as a Singular Potential for the 2D Schrodinger Equation [0.0]
  In the framework of distributionally generalized quantum theory, the object $Hpsi$ is defined as a distribution. The significance is a mathematically rigorous method, which does not rely upon renormalization or regularization of any kind. The distributional interpretation resolves the need to evaluate a wave function at a point where it fails to be defined.
  arXiv  Detail & Related papers  (2023-12-23T00:43:06Z)
• Thermalization of closed chaotic many-body quantum systems [0.0]
  We investigate thermalization of a chaotic many-body quantum system by combining the Hartree-Fock approach and the Bohigas-Giannoni-Schmit conjecture. We show that in the semiclassical regime, $rm Tr (A rho(t))$ decays with time scale $hbar / Delta$ towards an equilibrium value.
  arXiv  Detail & Related papers  (2023-10-04T11:16:35Z)
• Quantum and classical low-degree learning via a dimension-free Remez inequality [52.12931955662553]
  We show a new way to relate functions on the hypergrid to their harmonic extensions over the polytorus. We show the supremum of a function $f$ over products of the cyclic group $exp(2pi i k/K)_k=1K$. We extend to new spaces a recent line of work citeEI22, CHP, VZ22 that gave similarly efficient methods for learning low-degrees on hypercubes and observables on qubits.
  arXiv  Detail & Related papers  (2023-01-04T04:15:40Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Uncertainties in Quantum Measurements: A Quantum Tomography [52.77024349608834]
  The observables associated with a quantum system $S$ form a non-commutative algebra $mathcal A_S$. It is assumed that a density matrix $rho$ can be determined from the expectation values of observables. Abelian algebras do not have inner automorphisms, so the measurement apparatus can determine mean values of observables.
  arXiv  Detail & Related papers  (2021-12-14T16:29:53Z)
• On the Self-Penalization Phenomenon in Feature Selection [69.16452769334367]
  We describe an implicit sparsity-inducing mechanism based on over a family of kernels. As an application, we use this sparsity-inducing mechanism to build algorithms consistent for feature selection.
  arXiv  Detail & Related papers  (2021-10-12T09:36:41Z)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
  We show that the eigenspectrum of $bf K$ is independent of the distribution of the i.i.d. entries of $bf w$. We propose a novel random technique, called Ternary Random Feature (TRF) The computation of the proposed random features requires no multiplication and a factor of $b$ less bits for storage compared to classical random features.
  arXiv  Detail & Related papers  (2021-10-05T09:33:49Z)
• Superharmonic double-well systems with zero-energy ground states: Relevance for diffusive relaxation scenarios [0.0]
  Relaxation properties of the Smoluchowski diffusion process on a line can be spectrally quantified. A peculiarity of $hatH$ is that it refers to a family of quasi-exactly solvable Schr"odinger-type systems.
  arXiv  Detail & Related papers  (2021-04-24T08:11:54Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP) We show that the number of samples needed to yield an entrywise $varepsilon$-accurate estimate of the Q-function is at most on the order of $frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$ up to some logarithmic factor.
  arXiv  Detail & Related papers  (2020-06-04T17:51:00Z)

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.