Universal Online Learning: an Optimistically Universal Learning Rule

• URL: http://arxiv.org/abs/2201.05947v1
• Date: Sun, 16 Jan 2022 02:13:47 GMT
• Title: Universal Online Learning: an Optimistically Universal Learning Rule
• Authors: Mo\"ise Blanchard
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the subject of universal online learning with non-i.i.d. processes for bounded losses. The notion of an universally consistent learning was defined by Hanneke in an effort to study learning theory under minimal assumptions, where the objective is to obtain low long-run average loss for any target function. We are interested in characterizing processes for which learning is possible and whether there exist learning rules guaranteed to be universally consistent given the only assumption that such learning is possible. The case of unbounded losses is very restrictive, since the learnable processes almost surely visit a finite number of points and as a result, simple memorization is optimistically universal. We focus on the bounded setting and give a complete characterization of the processes admitting strong and weak universal learning. We further show that k-nearest neighbor algorithm (kNN) is not optimistically universal and present a novel variant of 1NN which is optimistically universal for general input and value spaces in both strong and weak setting. This closes all COLT 2021 open problems posed by Hanneke on universal online learning.

Related papers

• A Theory of Optimistically Universal Online Learnability for General Concept Classes [15.830099254570955]
  We provide a full characterization of the concept classes that are optimistically universally online learnable with $0, 1$ labels. The notion of optimistically universal online learning was defined in [Hanneke, 2021] in order to understand learnability under minimal assumptions.
  arXiv  Detail & Related papers  (2025-01-15T03:20:16Z)
• A Unified Framework for Neural Computation and Learning Over Time [56.44910327178975]
  Hamiltonian Learning is a novel unified framework for learning with neural networks "over time" It is based on differential equations that: (i) can be integrated without the need of external software solvers; (ii) generalize the well-established notion of gradient-based learning in feed-forward and recurrent networks; (iii) open to novel perspectives.
  arXiv  Detail & Related papers  (2024-09-18T14:57:13Z)
• Can Learned Optimization Make Reinforcement Learning Less Difficult? [70.5036361852812]
  We consider whether learned optimization can help overcome reinforcement learning difficulties. Our method, Learned Optimization for Plasticity, Exploration and Non-stationarity (OPEN), meta-learns an update rule whose input features and output structure are informed by previously proposed to these difficulties.
  arXiv  Detail & Related papers  (2024-07-09T17:55:23Z)
• Learning to Cover: Online Learning and Optimization with Irreversible Decisions [50.5775508521174]
  We find that regret grows sub-linearly at a rate $Thetaleft(mfrac12cdotfrac11-2-Tright)$, thus converging exponentially fast to $Theta(sqrtm)$. These findings underscore the benefits of limited online learning and optimization, in that even a few rounds can provide significant benefits as compared to a no-learning baseline.
  arXiv  Detail & Related papers  (2024-06-20T23:00:25Z)
• Adversarial Rewards in Universal Learning for Contextual Bandits [32.14208422566497]
  We study the limits of learning in contextual bandits, where a learner's rewards depend on their actions and a known context. We show that optimistic universal learning for contextual bandits with adversarial rewards is impossible in general.
  arXiv  Detail & Related papers  (2023-02-14T16:54: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)
• 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 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)
• Learning Implicitly with Noisy Data in Linear Arithmetic [94.66549436482306]
  We extend implicit learning in PAC-Semantics to handle intervals and threshold uncertainty in the language of linear arithmetic. We show that our implicit approach to learning optimal linear programming objective constraints significantly outperforms an explicit approach in practice.
  arXiv  Detail & Related papers  (2020-10-23T19:08:46Z)
• Tighter Generalization Bounds for Iterative Differentially Private Learning Algorithms [95.73230376153872]
  This paper studies the relationship between generalization and privacy preservation in iterative learning algorithms by two sequential steps. We prove that $(varepsilon, delta)$-differential privacy implies an on-average generalization bound for multi-Database learning algorithms. We then investigate how the iterative nature shared by most learning algorithms influence privacy preservation and further generalization.
  arXiv  Detail & Related papers  (2020-07-18T09:12:03Z)

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.