A Short Note on the Relationship of Information Gain and Eluder Dimension

• URL: http://arxiv.org/abs/2107.02377v1
• Date: Tue, 6 Jul 2021 04:01:22 GMT
• Title: A Short Note on the Relationship of Information Gain and Eluder Dimension
• Authors: Kaixuan Huang, Sham M. Kakade, Jason D. Lee, Qi Lei
• Abstract summary: We show that eluder dimension and information gain are equivalent in a precise sense for reproducing kernel Hilbert spaces. We show that this is not a coincidence -- eluder dimension and information gain are equivalent in a precise sense for reproducing kernel Hilbert spaces.
• Score: 86.86653394312134
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Eluder dimension and information gain are two widely used methods of complexity measures in bandit and reinforcement learning. Eluder dimension was originally proposed as a general complexity measure of function classes, but the common examples of where it is known to be small are function spaces (vector spaces). In these cases, the primary tool to upper bound the eluder dimension is the elliptic potential lemma. Interestingly, the elliptic potential lemma also features prominently in the analysis of linear bandits/reinforcement learning and their nonparametric generalization, the information gain. We show that this is not a coincidence -- eluder dimension and information gain are equivalent in a precise sense for reproducing kernel Hilbert spaces.

Related papers

• Adversarial Estimation of Topological Dimension with Harmonic Score Maps [7.34158170612151]
  We show that it is possible to retrieve the topological dimension of the manifold learned by the score map. We then introduce a novel method to measure the learned manifold's topological dimension using adversarial attacks.
  arXiv  Detail & Related papers  (2023-12-11T22:29:54Z)
• Relative intrinsic dimensionality is intrinsic to learning [49.5738281105287]
  We introduce a new notion of the intrinsic dimension of a data distribution, which precisely captures the separability properties of the data. For this intrinsic dimension, the rule of thumb above becomes a law: high intrinsic dimension guarantees highly separable data. We show thisRelative intrinsic dimension provides both upper and lower bounds on the probability of successfully learning and generalising in a binary classification problem.
  arXiv  Detail & Related papers  (2023-10-10T10:41:45Z)
• Sample-Efficient Reinforcement Learning in the Presence of Exogenous Information [77.19830787312743]
  In real-world reinforcement learning applications the learner's observation space is ubiquitously high-dimensional with both relevant and irrelevant information about the task at hand. We introduce a new problem setting for reinforcement learning, the Exogenous Decision Process (ExoMDP), in which the state space admits an (unknown) factorization into a small controllable component and a large irrelevant component. We provide a new algorithm, ExoRL, which learns a near-optimal policy with sample complexity in the size of the endogenous component.
  arXiv  Detail & Related papers  (2022-06-09T05:19:32Z)
• On the Benefits of Large Learning Rates for Kernel Methods [110.03020563291788]
  We show that a phenomenon can be precisely characterized in the context of kernel methods. We consider the minimization of a quadratic objective in a separable Hilbert space, and show that with early stopping, the choice of learning rate influences the spectral decomposition of the obtained solution.
  arXiv  Detail & Related papers  (2022-02-28T13:01:04Z)
• Quadric hypersurface intersection for manifold learning in feature space [52.83976795260532]
  manifold learning technique suitable for moderately high dimension and large datasets. The technique is learned from the training data in the form of an intersection of quadric hypersurfaces. At test time, this manifold can be used to introduce an outlier score for arbitrary new points.
  arXiv  Detail & Related papers  (2021-02-11T18:52:08Z)
• Recursive Generation of The Semi-Classical Expansion in Arbitrary Dimension [0.0]
  We present a procedure based on the small time expansion of the propagator. We generate a semi-classical expansion of the textitquantum action for a quantum mechanical potential in arbitrary dimensions.
  arXiv  Detail & Related papers  (2020-12-11T00:06:26Z)
• Manifold Learning via Manifold Deflation [105.7418091051558]
  dimensionality reduction methods provide a valuable means to visualize and interpret high-dimensional data. Many popular methods can fail dramatically, even on simple two-dimensional Manifolds. This paper presents an embedding method for a novel, incremental tangent space estimator that incorporates global structure as coordinates. Empirically, we show our algorithm recovers novel and interesting embeddings on real-world and synthetic datasets.
  arXiv  Detail & Related papers  (2020-07-07T10:04:28Z)
• Fuzzy Integral = Contextual Linear Order Statistic [0.0]
  The fuzzy integral is a powerful parametric nonlin-ear function with utility in a wide range of applications. We show that it can be represented by a set of contextual linear order statistics.
  arXiv  Detail & Related papers  (2020-07-06T16:37:36Z)

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.