Towards a combinatorial characterization of bounded memory learning

• URL: http://arxiv.org/abs/2002.03123v1
• Date: Sat, 8 Feb 2020 09:04:21 GMT
• Title: Towards a combinatorial characterization of bounded memory learning
• Authors: Alon Gonen and Shachar Lovett and Michal Moshkovitz
• Abstract summary: We develop dimensions that characterize bounded memory learning. We prove both upper and lower bounds for our candidate solution. We conjecture that our characterization holds in a much wider regime of parameters.
• Score: 21.031088723668486
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Combinatorial dimensions play an important role in the theory of machine learning. For example, VC dimension characterizes PAC learning, SQ dimension characterizes weak learning with statistical queries, and Littlestone dimension characterizes online learning. In this paper we aim to develop combinatorial dimensions that characterize bounded memory learning. We propose a candidate solution for the case of realizable strong learning under a known distribution, based on the SQ dimension of neighboring distributions. We prove both upper and lower bounds for our candidate solution, that match in some regime of parameters. In this parameter regime there is an equivalence between bounded memory and SQ learning. We conjecture that our characterization holds in a much wider regime of parameters.

Related papers

• Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
  We take inspiration from Kearns' SQ oracle and Valiant's weak evaluation oracle. We introduce an extensive yet intuitive framework that yields unconditional lower bounds for learning from evaluation queries.
  arXiv  Detail & Related papers  (2023-10-26T18:23:21Z)
• Optimal Learners for Realizable Regression: PAC Learning and Online Learning [52.37726841759983]
  We aim to characterize the statistical complexity of realizable regression both in the PAC learning setting and the online learning setting. We first introduce a minimax instance optimal learner for realizable regression and propose a novel dimension that both qualitatively and quantitatively characterizes which classes of real-valued predictors are learnable. In the context of online learning we provide a dimension that characterizes the minimax optimal instance optimal cumulative loss up to a constant factor and design an optimal online learner for realizable regression.
  arXiv  Detail & Related papers  (2023-07-07T21:39:25Z)
• A Combinatorial Characterization of Supervised Online Learnability [20.291598040396302]
  We study the online learnability of hypothesis classes with respect to arbitrary, but bounded loss functions. We give a new scale-sensitive dimension, named the sequential minimax dimension, and show that it gives a tight quantitative characterization of online learnability.
  arXiv  Detail & Related papers  (2023-07-07T20:11:07Z)
• Impossibility of Characterizing Distribution Learning -- a simple solution to a long-standing problem [11.39656079889941]
  We show that there is no notion of dimension that characterizes the sample complexity of learning distribution classes. In particular, we show that there is no notion of characterizing dimension (or characterization of learnability) for any of the tasks.
  arXiv  Detail & Related papers  (2023-04-18T03:23:39Z)
• Learning Log-Determinant Divergences for Positive Definite Matrices [47.61701711840848]
  In this paper, we propose to learn similarity measures in a data-driven manner. We capitalize on the alphabeta-log-det divergence, which is a meta-divergence parametrized by scalars alpha and beta. Our key idea is to cast these parameters in a continuum and learn them from data.
  arXiv  Detail & Related papers  (2021-04-13T19:09:43Z)
• The role of feature space in atomistic learning [62.997667081978825]
  Physically-inspired descriptors play a key role in the application of machine-learning techniques to atomistic simulations. We introduce a framework to compare different sets of descriptors, and different ways of transforming them by means of metrics and kernels. We compare representations built in terms of n-body correlations of the atom density, quantitatively assessing the information loss associated with the use of low-order features.
  arXiv  Detail & Related papers  (2020-09-06T14:12:09Z)
• A Functional Perspective on Learning Symmetric Functions with Neural Networks [48.80300074254758]
  We study the learning and representation of neural networks defined on measures. We establish approximation and generalization bounds under different choices of regularization. The resulting models can be learned efficiently and enjoy generalization guarantees that extend across input sizes.
  arXiv  Detail & Related papers  (2020-08-16T16:34:33Z)
• Can Temporal-Difference and Q-Learning Learn Representation? A Mean-Field Theory [110.99247009159726]
  Temporal-difference and Q-learning play a key role in deep reinforcement learning, where they are empowered by expressive nonlinear function approximators such as neural networks. In particular, temporal-difference learning converges when the function approximator is linear in a feature representation, which is fixed throughout learning, and possibly diverges otherwise.
  arXiv  Detail & Related papers  (2020-06-08T17:25:22Z)

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.