Universal Online Learning with Bounded Loss: Reduction to Binary Classification

• URL: http://arxiv.org/abs/2112.14638v1
• Date: Wed, 29 Dec 2021 16:38:57 GMT
• Title: Universal Online Learning with Bounded Loss: Reduction to Binary Classification
• Authors: Mo\"ise Blanchard and Romain Cosson
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study universal consistency of non-i.i.d. processes in the context of online learning. A stochastic process is said to admit universal consistency if there exists a learner that achieves vanishing average loss for any measurable response function on this process. When the loss function is unbounded, Blanchard et al. showed that the only processes admitting strong universal consistency are those taking a finite number of values almost surely. However, when the loss function is bounded, the class of processes admitting strong universal consistency is much richer and its characterization could be dependent on the response setting (Hanneke). In this paper, we show that this class of processes is independent from the response setting thereby closing an open question (Hanneke, Open Problem 3). Specifically, 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. Consequently, any output setting with bounded loss can be reduced to binary classification. Our reduction is constructive and practical. Indeed, we show that the nearest neighbor algorithm is transported by our construction. For binary classification on a process admitting strong universal learning, we prove that nearest neighbor successfully learns at least all finite unions of intervals.

Related papers

• Harnessing Superclasses for Learning from Hierarchical Databases [1.835004446596942]
  In many large-scale classification problems, classes are organized in a known hierarchy, typically represented as a tree. We introduce a loss for this type of supervised hierarchical classification. Our approach does not entail any significant additional computational cost compared with the loss of cross-entropy.
  arXiv  Detail & Related papers  (2024-11-25T14:39:52Z)
• Bisimulation Learning [55.859538562698496]
  We compute finite bisimulations of state transition systems with large, possibly infinite state space. Our technique yields faster verification results than alternative state-of-the-art tools in practice.
  arXiv  Detail & Related papers  (2024-05-24T17:11:27Z)
• A Hard-to-Beat Baseline for Training-free CLIP-based Adaptation [121.0693322732454]
  Contrastive Language-Image Pretraining (CLIP) has gained popularity for its remarkable zero-shot capacity. Recent research has focused on developing efficient fine-tuning methods to enhance CLIP's performance in downstream tasks. We revisit a classical algorithm, Gaussian Discriminant Analysis (GDA), and apply it to the downstream classification of CLIP.
  arXiv  Detail & Related papers  (2024-02-06T15:45:27Z)
• Class-Incremental Learning: A Survey [84.30083092434938]
  Class-Incremental Learning (CIL) enables the learner to incorporate the knowledge of new classes incrementally. CIL tends to catastrophically forget the characteristics of former ones, and its performance drastically degrades. We provide a rigorous and unified evaluation of 17 methods in benchmark image classification tasks to find out the characteristics of different algorithms.
  arXiv  Detail & Related papers  (2023-02-07T17:59:05Z)
• Chaos is a Ladder: A New Theoretical Understanding of Contrastive Learning via Augmentation Overlap [64.60460828425502]
  We propose a new guarantee on the downstream performance of contrastive learning. Our new theory hinges on the insight that the support of different intra-class samples will become more overlapped under aggressive data augmentations. We propose an unsupervised model selection metric ARC that aligns well with downstream accuracy.
  arXiv  Detail & Related papers  (2022-03-25T05:36:26Z)
• 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 with Unbounded Losses: Memory Is All You Need [10.839359285994636]
  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.
  arXiv  Detail & Related papers  (2022-01-21T22:03:18Z)
• 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)
• A Boosting Approach to Reinforcement Learning [59.46285581748018]
  We study efficient algorithms for reinforcement learning in decision processes whose complexity is independent of the number of states. We give an efficient algorithm that is capable of improving the accuracy of such weak learning methods.
  arXiv  Detail & Related papers  (2021-08-22T16:00:45Z)
• Multi-Class Classification from Single-Class Data with Confidences [90.48669386745361]
  We propose an empirical risk minimization framework that is loss-/model-/optimizer-independent. We show that our method can be Bayes-consistent with a simple modification even if the provided confidences are highly noisy.
  arXiv  Detail & Related papers  (2021-06-16T15:38:13Z)
• Affinity-Based Hierarchical Learning of Dependent Concepts for Human Activity Recognition [6.187780920448871]
  We show that the organization of overlapping classes into hierarchies considerably improves classification performances. This is particularly true in the case of activity recognition tasks featured in the SHL dataset. We propose an approach based on transfer affinity among the classes to determine an optimal hierarchy for the learning process.
  arXiv  Detail & Related papers  (2021-04-11T01:08:48Z)

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.