Universal Online Learning with Unbounded Losses: Memory Is All You Need

• URL: http://arxiv.org/abs/2201.08903v1
• Date: Fri, 21 Jan 2022 22:03:18 GMT
• Title: Universal Online Learning with Unbounded Losses: Memory Is All You Need
• Authors: Moise Blanchard, Romain Cosson, Steve Hanneke
• Abstract summary: A given learning rule is said to be optimistically universal if it achieves a low long-run average loss. Hanke posed as an open problem whether, for every unbounded loss, the family of processes admitting universal learning are precisely those having a finite number of distinct values. As a consequence, this also offers a dramatically simpler formulation of an optimistically universal learning rule for any unbounded loss.
• Score: 10.839359285994636
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We resolve an open problem of Hanneke on the subject of universally consistent online learning with non-i.i.d. processes and unbounded losses. The notion of an optimistically universal learning rule was defined by Hanneke in an effort to study learning theory under minimal assumptions. A given learning rule is said to be optimistically universal if it achieves a low long-run average loss whenever the data generating process makes this goal achievable by some learning rule. Hanneke posed as an open problem whether, for every unbounded loss, the family of processes admitting universal learning are precisely those having a finite number of distinct values almost surely. In this paper, we completely resolve this problem, showing that this is indeed the case. As a consequence, this also offers a dramatically simpler formulation of an optimistically universal learning rule for any unbounded loss: namely, the simple memorization rule already suffices. Our proof relies on constructing random measurable partitions of the instance space and could be of independent interest for solving other open questions. We extend the results to the non-realizable setting thereby providing an optimistically universal Bayes consistent learning rule.

Related papers

• Probably Approximately Precision and Recall Learning [62.912015491907994]
  Precision and Recall are foundational metrics in machine learning. One-sided feedback--where only positive examples are observed during training--is inherent in many practical problems. We introduce a PAC learning framework where each hypothesis is represented by a graph, with edges indicating positive interactions.
  arXiv  Detail & Related papers  (2024-11-20T04:21:07Z)
• Ticketed Learning-Unlearning Schemes [57.89421552780526]
  We propose a new ticketed model for learning--unlearning. We provide space-efficient ticketed learning--unlearning schemes for a broad family of concept classes.
  arXiv  Detail & Related papers  (2023-06-27T18:54:40Z)
• The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning [80.1018596899899]
  We argue that neural network models share this same preference, formalized using Kolmogorov complexity. Our experiments show that pre-trained and even randomly language models prefer to generate low-complexity sequences. These observations justify the trend in deep learning of unifying seemingly disparate problems with an increasingly small set of machine learning models.
  arXiv  Detail & Related papers  (2023-04-11T17:22:22Z)
• Contextual Bandits and Optimistically Universal Learning [32.14208422566497]
  We focus on consistency -- vanishing regret compared to the optimal policy. We show that for large classes of non-i.i.d. contexts, consistency can be achieved regardless of the time-invariant reward mechanism.
  arXiv  Detail & Related papers  (2022-12-31T16:15:28Z)
• Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterization [39.51923275855131]
  We present a minimax optimal learner for the problem of learning predictors robust to adversarial examples at test-time. In particular, we show, in a strong negative sense, the suboptimality of the robust learner proposed by Montasser, Hanneke, and Srebro.
  arXiv  Detail & Related papers  (2022-09-15T15:32:42Z)
• Universal Regression with Adversarial Responses [26.308541799686505]
  We provide algorithms for regression with adversarial responses under large classes of non-i.i.d. instance sequences. We consider universal consistency which asks for strong consistency of a learner without restrictions on the value responses.
  arXiv  Detail & Related papers  (2022-03-09T22:10:30Z)
• Universal Online Learning: an Optimistically Universal Learning Rule [0.0]
  We study the subject of universal online learning with non-i.i.d. processes for bounded losses. We show that k-nearest neighbor algorithm (kNN) is not optimistically universal and present a novel variant of 1NN.
  arXiv  Detail & Related papers  (2022-01-16T02:13:47Z)
• Universal Online Learning with Bounded Loss: Reduction to Binary Classification [0.0]
  We study universal consistency of non-i.i.d. processes in the context of online learning. We show that the class of processes that admit universal online learning is the same for binary classification as for multiclass classification with countable number of classes.
  arXiv  Detail & Related papers  (2021-12-29T16:38:57Z)
• Constrained Learning with Non-Convex Losses [119.8736858597118]
  Though learning has become a core technology of modern information processing, there is now ample evidence that it can lead to biased, unsafe, and prejudiced solutions.
  arXiv  Detail & Related papers  (2021-03-08T23:10:33Z)
• Dimension Free Generalization Bounds for Non Linear Metric Learning [61.193693608166114]
  We provide uniform generalization bounds for two regimes -- the sparse regime, and a non-sparse regime. We show that by relying on a different, new property of the solutions, it is still possible to provide dimension free generalization guarantees.
  arXiv  Detail & Related papers  (2021-02-07T14:47:00Z)
• Supervised Learning: No Loss No Cry [51.07683542418145]
  Supervised learning requires the specification of a loss function to minimise. This paper revisits the sc SLIsotron algorithm of Kakade et al. (2011) through a novel lens. We show how it provides a principled procedure for learning the loss.
  arXiv  Detail & Related papers  (2020-02-10T05:30: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.