The Dimension of Self-Directed Learning

• URL: http://arxiv.org/abs/2402.13400v1
• Date: Tue, 20 Feb 2024 21:59:41 GMT
• Title: The Dimension of Self-Directed Learning
• Authors: Pramith Devulapalli and Steve Hanneke
• Abstract summary: We study the self-directed learning complexity in both the binary and multi-class settings. We develop a dimension, $SDdim$, that exactly characterizes the self-directed learning mistake-bound for any concept class. We demonstrate several learnability gaps with a central focus on self-directed learning and offline sequence learning models.
• Score: 18.701165230774325
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Understanding the self-directed learning complexity has been an important problem that has captured the attention of the online learning theory community since the early 1990s. Within this framework, the learner is allowed to adaptively choose its next data point in making predictions unlike the setting in adversarial online learning. In this paper, we study the self-directed learning complexity in both the binary and multi-class settings, and we develop a dimension, namely $SDdim$, that exactly characterizes the self-directed learning mistake-bound for any concept class. The intuition behind $SDdim$ can be understood as a two-player game called the "labelling game". Armed with this two-player game, we calculate $SDdim$ on a whole host of examples with notable results on axis-aligned rectangles, VC dimension $1$ classes, and linear separators. We demonstrate several learnability gaps with a central focus on self-directed learning and offline sequence learning models that include either the best or worst ordering. Finally, we extend our analysis to the self-directed binary agnostic setting where we derive upper and lower bounds.

Related papers

• MODL: Multilearner Online Deep Learning [23.86544389731734]
  Existing work focuses almost exclusively on exploring pure deep learning solutions. We propose a different paradigm, based on a hybrid multilearner approach. We show that this approach achieves state-of-the-art results on common online learning datasets.
  arXiv  Detail & Related papers  (2024-05-28T15:34:33Z)
• Impact of Decentralized Learning on Player Utilities in Stackelberg Games [57.08270857260131]
  In many two-agent systems, each agent learns separately and the rewards of the two agents are not perfectly aligned. We model these systems as Stackelberg games with decentralized learning and show that standard regret benchmarks result in worst-case linear regret for at least one player. We develop algorithms to achieve near-optimal $O(T2/3)$ regret for both players with respect to these benchmarks.
  arXiv  Detail & Related papers  (2024-02-29T23:38:28Z)
• A Trichotomy for Transductive Online Learning [32.03948071550447]
  We present new upper and lower bounds on the number of learner mistakes in the transductive' online learning setting of Ben-David, Kushilevitz and Mansour (1997). This setting is similar to standard online learning, except that the adversary fixes a sequence of instances to be labeled at the start of the game, and this sequence is known to the learner.
  arXiv  Detail & Related papers  (2023-11-10T23:27:23Z)
• Self-Directed Linear Classification [50.659479930171585]
  In online classification, a learner aims to predict their labels in an online fashion so as to minimize the total number of mistakes. Here we study the power of choosing the prediction order and establish the first strong separation between worst-order and random-order learning.
  arXiv  Detail & Related papers  (2023-08-06T15:38:44Z)
• 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)
• Multiclass Online Learning and Uniform Convergence [34.21248304961989]
  We study multiclass classification in the adversarial online learning setting. We prove that any multiclass concept class is agnostically learnable if and only if its Littlestone dimension is finite.
  arXiv  Detail & Related papers  (2023-03-30T21:35:48Z)
• Decentralized model-free reinforcement learning in stochastic games with average-reward objective [1.9852463786440127]
  We show that our algorithm achieves both sublinear high probability regret of order $T3/4$ and sublinear expected regret of order $T2/3$. Our algorithm enjoys a low computational complexity and low memory space requirement compared to the previous works.
  arXiv  Detail & Related papers  (2023-01-13T15:59:53Z)
• Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games [36.969021834291745]
  We propose a proper learning algorithm which gets a near-optimal mistake bound in terms of the sequential fat-shattering dimension of the hypothesis class. This result answers a question as to whether proper learners could achieve near-optimal mistake bounds. For the real-valued (regression) setting, the optimal mistake bound was not even known for improper learners.
  arXiv  Detail & Related papers  (2021-11-17T05:24:21Z)
• Exploring the Common Principal Subspace of Deep Features in Neural Networks [50.37178960258464]
  We find that different Deep Neural Networks (DNNs) trained with the same dataset share a common principal subspace in latent spaces. Specifically, we design a new metric $mathcalP$-vector to represent the principal subspace of deep features learned in a DNN. Small angles (with cosine close to $1.0$) have been found in the comparisons between any two DNNs trained with different algorithms/architectures.
  arXiv  Detail & Related papers  (2021-10-06T15:48:32Z)
• Adversaries in Online Learning Revisited: with applications in Robust Optimization and Adversarial training [55.30970087795483]
  We revisit the concept of "adversary" in online learning, motivated by solving robust optimization and adversarial training problems. We establish a general approach for a large variety of problem classes using imaginary play.
  arXiv  Detail & Related papers  (2021-01-27T14:23:06Z)
• Online Learning with Imperfect Hints [72.4277628722419]
  We develop algorithms and nearly matching lower bounds for online learning with imperfect directional hints. Our algorithms are oblivious to the quality of the hints, and the regret bounds interpolate between the always-correlated hints case and the no-hints case.
  arXiv  Detail & Related papers  (2020-02-11T23:06:09Z)

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.